Linear optimization: Upper and lower bounds 2: Unterschied zwischen den Versionen
[unmarkierte Version] | [unmarkierte Version] |
(→Example) |
(→Theory) |
||
Zeile 12: | Zeile 12: | ||
Of course you can implement these upper and lower bounds as specific constraints in a simplex tableau. | Of course you can implement these upper and lower bounds as specific constraints in a simplex tableau. | ||
But this far too complicated. | But this far too complicated. | ||
− | The other possibility | + | The other possibility is to transform the simplextableau, i.e. modifying the simplex tableau. |
== '''Example''' == | == '''Example''' == |
Version vom 25. Juni 2013, 17:57 Uhr
Inhaltsverzeichnis
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 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
where columns 5 and 6 represent the basic variables s and t and the corresponding basic feasible solution is
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
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.
Presentation of the problem
Detailed solution process with explanation
Sources
Sources