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

Aus Operations-Research-Wiki
Wechseln zu: Navigation, Suche
[unmarkierte Version][unmarkierte Version]
(→‎Theory)
(→‎Example)
Zeile 10: Zeile 10:
 
Upper bounds are classified like: <math>x_{j}\leq l_{j}</math>
 
Upper bounds are classified like: <math>x_{j}\leq l_{j}</math>
  
−
== '''Example''' ==
+
===Example===
−
Linear Programming (LP)
+
Suppose that a farmer has a piece of farm land, say ''L'' km<sup>2</sup>, to be planted with either wheat or barley or some combination of the two. The farmer has a limited amount of fertilizer, ''F'' kilograms, and insecticide, ''P'' kilograms. Every square kilometer of wheat requires ''F''<sub>1</sub> kilograms of fertilizer, and ''P''<sub>1</sub> kilograms of insecticide, while every square kilometer of barley requires ''F''<sub>2</sub> kilograms of fertilizer, and ''P''<sub>2</sub> kilograms of insecticide. Let S<sub>1</sub> be the selling price of wheat per square kilometer, and S<sub>2</sub> be the price of barley. If we denote the area of land planted with wheat and barley by ''x''<sub>1</sub> and ''x''<sub>2</sub> respectively, then profit can be maximized by choosing optimal values for ''x''<sub>1</sub> and ''x''<sub>2</sub>. This problem can be expressed with the following linear programming problem in the standard form:
−
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:
+
| colspan="2" | Maximize: <big>''S''<sub>1</sub>''x''<sub>1</sub> + ''S''<sub>2</sub>''x''<sub>2</sub></big>
 +
| (maximize the revenue—revenue is the "objective function")
 +
|-
 +
| Subject to:
 +
| <big>''x''<sub>1</sub> + ''x''<sub>2</sub> ≤ ''L''</big>
 +
| (limit on total area)
 +
|-
 +
|
 +
| <big>''F''<sub>1</sub>''x''<sub>1</sub> + ''F''<sub>2</sub>''x''<sub>2</sub> ≤ ''F''</big>
 +
| (limit on fertilizer)
 +
|-
 +
|
 +
| <big>''P''<sub>1</sub>''x''<sub>1</sub> + ''P''<sub>2</sub>''x''<sub>2</sub> ≤ ''P''</big>
 +
| (limit on insecticide)
 +
|-
 +
|
 +
| <big>''x''<sub>1</sub> ≥ 0, ''x''<sub>2</sub> ≥ 0
 +
| (cannot plant a negative area).
 +
|}
  
−
min 
+
Which in matrix form becomes:
−
s.t. (1)
+
: maximize <math>\begin{bmatrix} S_1 & S_2 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} </math>
−
i=1,…,m
+
: subject to <math>\begin{bmatrix} 1 & 1 \\ F_1 & F_2 \\ P_1 & P_2 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} \le \begin{bmatrix} L \\ F \\ P \end{bmatrix}, \, \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} \ge \begin{bmatrix} 0 \\ 0 \end{bmatrix}. </math>
−
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:
+
−
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).
+
−
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.
+
−
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.
+
−
3 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.
+
−
+
−
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.
+
−
 
+
−
• 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
+
−
s.t. (4)
+
−
Ax + s = b
+
−
0  x  xmax
+
−
0  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’
+
−
s.t.
+
−
A’x’ = b,
+
−
0  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.
+
−
3 x1 + 2 x2 + s1 = 24
+
−
x1 + 2 x2  + s2 = 12
+
−
0  x1  8
+
−
0  x2  4
+
−
0  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.
+
−
 
+
−
• 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)
+
−
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.
+
−
3 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''' ==
 
== '''Presentation of the problem''' ==

Version vom 25. Juni 2013, 17:43 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}


Example

Suppose that a farmer has a piece of farm land, say L km2, to be planted with either wheat or barley or some combination of the two. The farmer has a limited amount of fertilizer, F kilograms, and insecticide, P kilograms. Every square kilometer of wheat requires F1 kilograms of fertilizer, and P1 kilograms of insecticide, while every square kilometer of barley requires F2 kilograms of fertilizer, and P2 kilograms of insecticide. Let S1 be the selling price of wheat per square kilometer, and S2 be the price of barley. If we denote the area of land planted with wheat and barley by x1 and x2 respectively, then profit can be maximized by choosing optimal values for x1 and x2. This problem can be expressed with the following linear programming problem in the standard form:

Maximize: S1x1 + S2x2 (maximize the revenue—revenue is the "objective function")
Subject to: x1 + x2 ≤ L (limit on total area)
F1x1 + F2x2 ≤ F (limit on fertilizer)
P1x1 + P2x2 ≤ P (limit on insecticide)
x1 ≥ 0, x2 ≥ 0 (cannot plant a negative area).

Which in matrix form becomes:

maximize
subject to Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \begin{bmatrix} 1 & 1 \\ F_1 & F_2 \\ P_1 & P_2 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} \le \begin{bmatrix} L \\ F \\ P \end{bmatrix}, \, \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} \ge \begin{bmatrix} 0 \\ 0 \end{bmatrix}.


Presentation of the problem

Detailed solution process with explanation

== Sources ==

Von „https://www.wiwi.uni-kl.de/bisor-orwiki/index.php?title=Linear_optimization:_Upper_and_lower_bounds_2&oldid=4224“