Linear optimization: Upper and lower bounds 2

Theory

Linear optimization can be used for set of different problems, which have restrictions such as a given amount of resources or a certain budget. The lower bound is the smallest possible value, and the upper bound is the highest possible value.

Linear programming is the most commonly used optimisation technique in embedded industrial applications. There are many reasons for this. Linear programs are relatively easy to formulate, use and understand. The LP optimisation techniques are also relatively efficient and well developed. A surprisingly large set of real-life problems can be represented as linear programs, or approximated sufficiently well with linear programs. Finally, a number of more advanced modelling and solution techniques are based on linear programming, such as quadratic programming, fractional programming, integer programming, mixed integer programming, constraint logic programming, etc.

Lower bounds are classified like: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{j}\geq l_{j}

Upper bounds are classified like: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{j}\leq l_{j}

Of course you can implement these upper and lower bounds as specific constraints in a simplex tableau. But this is far too complicated. The other possibility is to transform the simplextableau, i.e. modifying the simplex tableau.

Example

Consider the sample model with upper bounds Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 0\leq x_{1}\leq 8 , and Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 0\leq x_{2}\leq 4 . The simplex table is

|

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

The $x^{B}/y_{i}$ –ratios would allow an increase of $x_{2}$. However, in this case the minimum Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Theta

= 4 corresponding to the entering variable itself.

The upper bound substitution can be done very easily on the simplex table. A non-basic variable is substituted by subtracting $x_{j}^{max}$ times the variable column from the solution vector and negating then the column. Substituting Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{2}=4-x_{2}^{*}

in the previous table gives

|

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Comparing this solution with the previous example after the first iteration we observe that the basis is different, but the solution is essentially the same (same values for $z,x_{1},x_{2},s_{1}$ and $s_{2}$). Next we enter $x_{1}$ and remove $s_{2}$ from row 2 with minimum Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Theta = 4

|

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

This table is not optimal because the reduced cost of Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{2}^{*}

is 1. Because $y_{2}$ is negative and the corresponding basic variable 1 has a finite upper bound of 8, we must compute the ratio as (Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 4-8)/-2 = 2

. This time the ratio for the first row is smallest. Thus, we enter Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{2}^{*}

and remove $s_{1}$ from row 1 with minimum Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Theta = 1

.

|

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

This table is optimal. To obtain the solution in terms of the original variables, we can substitute the Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{2}^{*}

with Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 4-x_{2}

. Because Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{2}^{*}

is basic, this substitution affects only the $x_{2}$ row.

|

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

However, negating the column of $x_{2}$ has made the identity matrix element -1. To restore the identity matrix, the row must yet be multiplied by -1.

|

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

So now we have the optimal solution for the tableau.