Linear optimization: Upper and lower bounds 2: Unterschied zwischen den Versionen

Version vom 27. Juni 2013, 09:08 Uhr

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 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 0\leq x_{2}\leq 4. The simplex table is

The xB/yi –ratios would allow an increase of 6 in x2. However, in this case the minimum  = 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 xjmax times the variable column from the solution vector and negating then the column. Substituting x2 = 4-x2* in the previous table gives

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, x1, x2, s1 and s2). Next we enter x1 and remove s2 from row 2 with minimum  = 4

This table is not optimal because the reduced cost of x2* is 1. Because y2 is negative and the corresponding basic variable x1 has a finite upper bound of 8, we must compute the ratio as (4-8)/-2 = 2. This time the ratio for the first row is smallest. Thus, we enter x2* and remove s1 from row 1 with minimum  = 1.

This table is optimal. To obtain the solution in terms of the original variables, we can substitute the x2* with 4-x2. Because x2* is basic, this substitution affects only the x2 row.

However, negating the column of x2 has made the identity matrix element –1. To restore the identity matrix, the row must yet be multiplied by –1.

This same solution was found in the previous example without the upper bounds technique.

Presentation of the problem

Detailed solution process with explanation

Sources

First of all you have to transform the old variable ${\displaystyle {x}'_{j}}$ into: ${\displaystyle x_{j}}$.

That means:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): {x}'_{j}= x_{j}-l_{j}

But you have to take care of, that the lower bound is not allowed to be negative.

${\displaystyle {x}'_{j}>0}$

Example

Consider the linear program

Minimize

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): Z = -2 x - 3 y - 4 z\,

Subject to

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \begin{align} 3 x + 2 y + z &\le 10\\ 2 x + 5 y + 3 z &\le 15\\ x,\,y,\,z &\ge 0 \end{align}

With the addition of slack variables s and t, this is represented by the canonical tableau

${\displaystyle {\begin{bmatrix}1&2&3&4&0&0&0\\0&3&2&1&1&0&10\\0&2&5&3&0&1&15\end{bmatrix}}}$

where columns 5 and 6 represent the basic variables s and t and the corresponding basic feasible solution is

${\displaystyle x=y=z=0,\,s=10,\,t=15.}$

Columns 2, 3, and 4 can be selected as pivot columns, for this example column 4 is selected. The values of x resulting from the choice of rows 2 and 3 as pivot rows are 10/1 = 10 and 15/3 = 5 respectively. Of these the minimum is 5, so row 3 must be the pivot row. Performing the pivot produces

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \begin{bmatrix} 1 & -\tfrac{2}{3} & -\tfrac{11}{3} & 0 & 0 & -\tfrac{4}{3} & -20 \\ 0 & \tfrac{7}{3} & \tfrac{1}{3} & 0 & 1 & -\tfrac{1}{3} & 5 \\ 0 & \tfrac{2}{3} & \tfrac{5}{3} & 1 & 0 & \tfrac{1}{3} & 5 \end{bmatrix}

Now columns 4 and 5 represent the basic variables z and s and the corresponding basic feasible solution is

${\displaystyle x=y=t=0,\,z=5,\,s=5.}$

For the next step, there are no positive entries in the objective row and in fact

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): Z = -20 + \tfrac{2}{3} x + \tfrac{11}{3} y + \tfrac{4}{3} t

so the minimum value of Z is −20.