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

[unmarkierte Version]

Aktuelle Version vom 27. Juni 2013, 09:44 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 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.

@@ Zeile 4: / Zeile 4: @@
 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: <math>x_{j}\geq l_{j}</math>
+Upper bounds are classified like: <math>x_{j}\leq l_{j}</math>
+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''' ==
-Linear Programming (LP)
-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.
-Different formulations of LP problems
-The standard formulation of an LP problem is minimization of a linear objective function subject to linear inequality constraints:
-	min
+Consider the sample model with upper bounds <math>0\leq x_{1}\leq 8</math>, and <math>0\leq x_{2}\leq 4</math>. The simplex table is
-s.t.		(1)
-	 	i=1,…,m
-	xj  0	j=1,…,n
-Instead of writing the model using sums and iteration constructs, it is often more convenient to use the vector and matrix notation:
+| [[bild:01_123image123456.jpg]]
-	min z = cx
-s.t.		(2)
-	Ax  b
-	x  0
-z is the linear objective function to be minimized, x = [x1, …, xn] is a column-vector of n non-negative decision variables,  c = [c1, …, cn] is a row-vector of cost coefficients, A is an nm matrix of constraint coefficients, and b = [b1, …, bm] is a column vector of right hand side (RHS) coefficients (sometimes called the resource vector).
+The <math>x^{B}/y_{i}</math> –ratios would allow an increase of <math>x_{2}</math>. However, in this case the minimum <math>\Theta </math> = 4 corresponding to the entering variable itself.
-Other equivalent formulations can also be used:
-•	Maximization: max cx is equivalent to –min –cx.
-•	Greater than inequalities: Ax  b is equivalent to -Ax  -b.
-•	Equality constraints: Ax = b is equivalent to double inequalities Ax  b and Ax  b.
-•	Non-positive variables: y  0 can be substituted by –x where x  0.
-•	Unconstrained variables: unconstrained y can be substituted by difference x1-x2 where x1,x2  0.
-•	Nonzero lower bounds: yymin can be substituted by x=y-ymin where x 0.
-When formulating an LP problem it is convenient to allow a more general formulation
-	min (max) cx
-s.t.		(3)
-	bmin  Ax  bmax	(two sided constraints)
-	xmin  x  xmax	(lower and upper bounds)
-In this form each constraint may be two-sided and decision variables may have non-zero lower bounds and upper bounds. Choosing some bmin= bmax yields equality constraints. Upper bounds can be disabled by choosing  as upper bound.
+The upper bound substitution can be done very easily on the simplex table. A non-basic variable is substituted by subtracting <math>x_{j}^{max}</math> times the variable column from the solution vector and negating then the column. Substituting <math>x_{2}=4-x_{2}^{*}</math> in the previous table gives
-Graphical solution of LP problems
-Small models with two decision variables can be visualized and solved graphically. Each linear inequality constraint divides the plane into two half-planes: the feasible and infeasible side. The feasible region is a convex polygon formed as the intersection of these half-planes. The objective function is a direction in the plane. The optimum solution is always in some corner of this polygon. (In rare cases, two corners may give the same optimal solution. Then also all points on their connecting edge are optimal).
-Example: Consider the problem
-	min z = -2 x1 - 3 x2
-s.t.
-x1 + 2 x2  24
-	x1 + 2 x2  12
-	x2  4
-	x1  8
-	x1, x2  0
-This problem can be is illustrated graphically in Figure 1. The feasible region is the convex polygon with corners (0,0), (0,4), (4,4), (6,3), and (8,0). The dotted line indicates the direction where z is constant. The minimal feasible solution z = -21 is found by shifting the line as far to the Northeast as possible while still touching the feasible region. As seen in the figure, this happens in point (6,3). Similarly, the maximal feasible solution z = 0 is found in (0,0) by shifting the line as far to Southwest as possible.
+| [[bild:02_123image123456.jpg]]
-Transforming an LP problem into the canonical form
-Prior to solving an LP problem numerically, it is normally converted into a format, where each constraint is an equality that includes a unique slack variable. This format may either contain or not contain upper bounds for variables.
-Canonical form with upper bounds
-The following transformations are applied:
-•	Inequality constraints Ax  b are converted to equality constraints by adding non-negative slack variables into Ax + s = b, where s0.
-•	Inequality constraints Ax  b are multiplied by –1 and then converted by adding non-negative slack variables into –Ax + s = –b, where s0.
+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 <math>z, x_{1}, x_{2}, s_{1}</math> and <math>s_{2}</math>). Next we enter <math>x_{1}</math> and remove <math>s_{2}</math> from row 2 with minimum  <math>\Theta = 4</math>
-•	The equality constraints Ax = b are augmented with so called artificial variables into Ax + s = b, where 0  s  0.
-•	Two-sided constraints bmin  Ax  bmax can be efficiently handled by using a combined slack/surplus variable: Ax + s = bmax, where 0  s  bmax-bmin
-After these transformations, the canonical form of the LP problem with upper bounds is obtained:
-	min z = cx
+| [[bild:03_123image123456.jpg]]
-s.t.		(4)
-	Ax + s = b
- x  xmax
- s  smax
-The x-variables are called structural variables. The s-variables are called slacks for short. The only difference between the s-variables and x-variables is that the objective function coefficients of s-variables are known to be zeroes and the constraint coefficients of the s-variables are known to form an identity matrix. If we do not want to highlight these differences, we can extend the x-vector to include the s-variables and augment the c and xmax vectors and the A-matrix correspondingly. Then the LP problem can be written as
-	min z = c’x’
+This table is not optimal because the reduced cost of <math>x_{2}^{*}</math> is 1. Because <math>y_{2}</math> is negative and the corresponding basic variable 1 has a finite upper bound of 8, we must compute the ratio as (<math>4-8)/-2 = 2</math>. This time the ratio for the first row is smallest. Thus, we enter <math>x_{2}^{*}</math> and remove <math>s_{1}</math> from row 1 with minimum <math>\Theta = 1</math>.
-s.t.
-	A’x’ = b,
- x’  x’max.
-In this form the matrix A’ consists of the original A corresponding to the original x-variables and an mm identity matrix I corresponding to the s-variables. Non-zero lower bounds and negative variables can be modelled easily through substitution of variables, as described earlier.
-For example the canonical form with upper bounds of the sample model is
-	min z = -2 x1 - 3 x2
-s.t.
+| [[bild:04_123image123456.jpg]]
-x1 + 2 x2 + s1 = 24
-	x1 + 2 x2  + s2 = 12
- x1  8
- x2  4
- s1, s2  
-Canonical form without upper bounds
-The following transformations are applied:
-•	Upper bounds for variables are treated as inequalities.
-•	Inequality constraints Ax  b are converted to equality constraints by adding non-negative slack variables into Ax + s = b, where s0.
-•	Inequality constraints Ax  b are multiplied by –1 and then converted by adding non-negative slack variables into –Ax + s = –b, where s0.
+This table is optimal. To obtain the solution in terms of the original variables, we can substitute the <math>x_{2}^{*}</math> with <math>4-x_{2}</math>. Because <math>x_{2}^{*}</math> is basic, this substitution affects only the <math>x_{2}</math> row.
-•	Equality constraints Ax = b are treated as two separate inequalities Ax  b and Ax  b.
-•	Two-sided constraints bmin  Ax  bmax are treated as two separate inequalities.
-After these transformations, the canonical form of the LP problem without upper bounds is obtained:
-	min z = cx
-s.t.		(5)
+| [[bild:05_123image123456.jpg]]
-	Ax + s = b
-	x, s  0
-In the canonical form without upper bounds a model is often larger (has more constraints and variables) than with upper bounds. The previous sample model can be written in canonical format without upper bounds as
-	min z = -2 x1 - 3 x2
-s.t.
+However, negating the column of <math>x_{2}</math> has made the identity matrix element -1. To restore the identity matrix, the row must yet be multiplied by -1.
-x1 + 2 x2 + s1 = 24
-	x1 + 2 x2  + s2 = 12
-	x2 + s3 = 4
-	x1 + s4 = 8
-	x1, x2, s1, s2, s3, s4  0
-== '''Presentation of the problem''' ==
-== '''Detailed solution process with explanation''' ==
+| [[bild:06_123image123456.jpg]]
-== '''Sources''' ==
+So now we have the optimal solution for the tableau.

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

Aktuelle Version vom 27. Juni 2013, 09:44 Uhr

Theory

Example

Navigationsmenü

Ansichten

Meine Werkzeuge

Navigation

Suche

Werkzeuge