|
|
| (45 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt) |
| Zeile 1: |
Zeile 1: |
| | == '''Theory''' == | | == '''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. | | 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. |
| | | | |
| − | == '''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. | | 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
| |
| − | 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:
| |
| − | 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 nm 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: yymin 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 s0.
| |
| − | • Inequality constraints Ax b are multiplied by –1 and then converted by adding non-negative slack variables into –Ax + s = –b, where s0.
| |
| − | • 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 mm 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 s0.
| |
| − | • Inequality constraints Ax b are multiplied by –1 and then converted by adding non-negative slack variables into –Ax + s = –b, where s0.
| |
| − | • 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
| |
| − | The Tabular Simplex algorithm
| |
| − | In the tabular Simplex algorithm, the optimisation problem is organized as a table of numbers corresponding to the equality constraints. Equations can, of course, be reordered, multiplied by factors and summed together without affecting their validity. The Simplex algorithm is based on performing such operations in an orderly manner in order to transform the equations into a format where the optimal solution is obvious.
| |
| − | Consider an LP model in the canonical format. Writing also the objective function as equality yields the form
| |
| − | min z
| |
| − | s.t. (6)
| |
| − | z - c1x1 - c2x2 - ... - cnxn = 0
| |
| − | a11 x1 + a12 x2 + … + a1n xn + s1 = b1
| |
| − | a21 x1 + a22 x2 + … + a2n xn + s2 = b2
| |
| − |
| |
| − | am1 x1 + am2 x2 + … + amn xn + sm = bm
| |
| − | 0 x xmax
| |
| − | 0 s smax
| |
| − | During the Simplex algorithm, exactly m variables xB are basic, and the remaining n variables are non-basic. The non-basic variables are set to their lower (or upper) bounds. The m basic variables are then solved from the system of m linear equalities.
| |
| | | | |
| − | Basis x1 x2 … xn s1 s2 … sm Solution
| |
| − | z reduced costs objective
| |
| − |
| |
| − | names of
| |
| − | basic
| |
| − | variables coefficient
| |
| − | matrix current
| |
| − | solution
| |
| − |
| |
| − |
| |
| − | The simplex table for performing the necessary computations is organized as follows:
| |
| − | • To the left of the simplex table is a column showing the names of the variables that form the current basis xB. The current basis may contain any selection of m variables out of the n x-variables and m s-variables. The order in which the basic variables are listed identifies from which equation that variable has been solved.
| |
| − | • The names of each variable are listed on top of the simplex table.
| |
| − | • The first row shows the so-called reduced costs for each variable.
| |
| − | • The current objective function value appears in the upper right hand corner.
| |
| − | • Below the reduced costs is the coefficient matrix.
| |
| − | • The last column shows the current solution, i.e. the values of the basic variables xB.
| |
| − | During the algorithm, the simplex table is maintained in a format where the sub-matrix corresponding to the basic variables is an identity matrix.
| |
| − | In the initial simplex table, all x-variables are non-basic and the basis consists of all the slacks. This is convenient, because the sub-matrix corresponding to the slacks is an identity matrix. The non-basic variables are set to zero (their lower bound). The initial solution vector xB is then equal to the b-vector. For the moment, we are not concerned about the feasibility of the solution.
| |
| | | | |
| − | Basis x1 x2 … xn s1 s2 … sm Solution
| + | Lower bounds are classified like: <math>x_{j}\geq l_{j}</math> |
| − | z -c1 -c2 … -cn 0 0 … 0 0
| + | |
| − | s1 a11 a12 … a1n 1 0 … 0 b1
| + | Upper bounds are classified like: <math>x_{j}\leq l_{j}</math> |
| − | s2 a21 a22 … a2n 0 1 b2
| + | |
| − |
| + | 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 <math>0\leq x_{1}\leq 8</math>, and <math>0\leq x_{2}\leq 4</math>. The simplex table is |
| | + | |
| | + | |
| | + | | [[bild:01_123image123456.jpg]] |
| | + | |
| | + | |
| | + | 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. |
| | + | |
| | + | |
| | + | 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 |
| | + | |
| | + | |
| | + | | [[bild:02_123image123456.jpg]] |
| | + | |
| | + | |
| | + | 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> |
| | + | |
| | + | |
| | + | | [[bild:03_123image123456.jpg]] |
| | + | |
| | + | |
| | + | 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>. |
| | + | |
| | + | |
| | + | | [[bild:04_123image123456.jpg]] |
| | + | |
| | + | |
| | + | 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. |
| | + | |
| | + | |
| | + | | [[bild:05_123image123456.jpg]] |
| | | | |
| − | sm am1 am2 … amn … 1 bm
| |
| − | The initial simplex table corresponding previous sample model in canonical format without upper bounds is
| |
| − | Basis x1 x2 s1 s2 s3 s4 Solution
| |
| − | z 2 3 0 0 0 0 0
| |
| − | s1 3 2 1 0 0 0 24
| |
| − | s2 1 2 0 1 0 0 12
| |
| − | s3 0 1 0 0 1 0 4
| |
| − | s4 1 0 0 0 0 1 8
| |
| − | At each iteration of the Simplex algorithm, we want to enter a new variable to the basis and remove an old variable from the basis so that the value of z improves (decreases) and the feasibility of all feasible variables is maintained.
| |
| − | The entering variable is determined by examining the reduced costs of the non-basic variables. The reduced cost of a variable represents the net decrease in z when the variable in increased. The reduced costs of basic variables are by definition zero.
| |
| − | For example, in the sample table, increasing the value for x2 by +1 would (in order to maintain the equality z-cx=0) decrease z by c2 = 3. Thus, z decreases if the reduced cost for the entering variable is positive. When minimizing, the variable with the largest reduced cost is typically chosen to enter the basis. When all reduced costs are non-positive, the solution is optimal and the algorithm terminates.
| |
| − | The column corresponding to the entering variable is called the pivot column y and it is highlighted in the sample table. The pivot column shows what happens to the basic variables when the (non-basic) entering variable is moved from its bound. When the entering variable increases from its lower bound, a positive y-element indicates that the corresponding basic variable decreases (to maintain the equality), a negative element indicates that the basic variable increases, and a zero indicates that the basic variable is unaffected. For example in the initial table, increasing x2 by +1 decreases s1 by 2, s2 by 2, and s3 by 1, and leaves s4 unaffected.
| |
| − | If the variables are bounded only from below, only the positive y-elements corresponding to decreasing basic variables are of interest. To protect any basic variable from becoming infeasible (negative), the variable that first reaches zero value must leave the basis. This is the variable that corresponds to the smallest ratio xBi/yi for yi>0 and xBi0. Negative xBi indicate already infeasible variables. Protecting them from becoming even more infeasible is not a concern at the moment. This smallest ratio indentifies the pivot row, i.e. the equation from which the entering variable must be solved. If no leaving variable is found (all y-elements are non-positive), that indicates that the model is unbounded and the algorithm terminates.
| |
| − | The following table shows the ratios for determining in the sample model. The smallest ratio is 4 and it appears on the third equation row. Thus, s3 is the variable that must leave the basis.
| |
| − | Basis x1 x2 s1 s2 s3 s4 Solution xBi/yi
| |
| − | z 2 3 0 0 0 0 0
| |
| − | s1 3 2 1 0 0 0 24 12
| |
| − | s2 1 2 0 1 0 0 12 6
| |
| − | s3 0 1 0 0 1 0 4 4
| |
| − | s4 1 0 0 0 0 1 8 -
| |
| − | After the entering and leaving variables have been determined, the so-called pivot step is performed. This step will return the table to a format where the basic variables correspond to an identity matrix. This is done by applying the Gauss-Jordan elimination method on the simplex table in such a manner that the pivot element at the intersection of the highlighted pivot row and column becomes one and the remaining parts of the pivot column become zero.
| |
| − | The Gauss-Jordan method is applied as follows. The pivot row is divided by the pivot element to make the pivot element equal to one. The remaining elements yi of the pivot column are eliminated through row-operations by subtracting yi times the transformed pivot row from each row i, including the reduced cost row (row zero).
| |
| − | The following table shows the necessary Gauss-Jordan elimination operations on our example model. The last column indicates what row operations have been applied. Each cell shows the formula for computing the new value. Observe that the pivot row needs no transformation in this case, because the pivot element y3 is already one. Also, the last row needs no processing, because y4 is already zero. Also, because the pivot row contains zeroes on columns x1, s1, s2 and s4, no operations on these columns are needed.
| |
| − | Basis x1 x2 s1 s2 s3 s4 Solution operation
| |
| − | z 2 3-31 0 0 0-31 0 0-34 -= 3r
| |
| − | s1 3 2-21 1 0 0-21 0 24-24 -= 2r
| |
| − | s2 1 2-21 0 1 0-21 0 12-24 -= 2r
| |
| − | x2 0 1/1 0 0 1/1 0 4/1 /= 1
| |
| − | s4 1 0 0 0 0 1 8 -= 0r
| |
| − | The following table shows the result after the row-operations. The z-value has improved from 0 to –12. The variable x2 is now in the basis on row 3, which is indicated in the basis-column. The reduced cost of x2 is zero and the column of x2 is part of the identity matrix formed by all basic variables. To see the identity matrix, the basic columns would have to be sorted into the order specified in the basis column. Finally, observe that the column of s3 that has been removed from the basis, is no longer a part of the identity matrix.
| |
| − | Basis x1 x2 s1 s2 s3 s4 Solution
| |
| − | z 2 0 0 0 -3 0 -12
| |
| − | s1 3 0 1 0 -2 0 16
| |
| − | s2 1 0 0 1 -2 0 4
| |
| − | x2 0 1 0 0 1 0 4
| |
| − | s4 1 0 0 0 0 1 8
| |
| − | This table is not yet optimal, because the reduced cost for x1 is positive. Choosing x1 as the entering variable and computing the xB/y ratios identifies row 2 as the pivot row and s2 as the leaving variable.
| |
| − | Basis x1 x2 s1 s2 s3 s4 Solution xBi/yi
| |
| − | z 2 0 0 0 -3 0 -12
| |
| − | s1 3 0 1 0 -2 0 16 5.333
| |
| − | s2 1 0 0 1 -2 0 4 4
| |
| − | x2 0 1 0 0 1 0 4 -
| |
| − | s4 1 0 0 0 0 1 8 8
| |
| − | The new table after pivoting is still not optimal, because now the reduced cost of s3 is positive. This time the pivot row is row 1 with leaving variable s1.
| |
| − | Basis x1 x2 s1 s2 s3 s4 Solution xBi/yi
| |
| − | z 0 0 0 -2 1 0 -20
| |
| − | s1 0 0 1 -3 4 0 4 1
| |
| − | x1 1 0 0 1 -2 0 4 -
| |
| − | x2 0 1 0 0 1 0 4 4
| |
| − | s4 0 0 0 -1 2 1 4 2
| |
| − | After the row-operations we obtain an optimal table with z = -21.
| |
| − | Basis x1 x2 s1 s2 s3 s4 Solution
| |
| − | z 0 0 -0.25 -1.25 0 0 -21
| |
| − | s3 0 0 0.25 -0.75 1 0 1
| |
| − | x1 1 0 0.5 -0.5 0 0 6
| |
| − | x2 0 1 -0.25 0.75 0 0 3
| |
| − | s4 0 0 -0.5 0.5 0 1 2
| |
| | | | |
| − | Tabular Simplex with upper bounds
| + | 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. |
| − | Upper bounds of structural variables can be handled as separate inequality constraints, as was done in the previous example. This, however, increases the size of the model unnecessarily. A much more efficient technique is to handle the upper bounds directly in the algorithm.
| + | |
| − | Let us consider a variable with lower bound zero and non-negative upper bound 0xjxjmax. We define a new variable xj* = xjmax-xj. Both variables have the same bounds, but when xj is on its upper bound, xj* is zero and when xj is zero, xj*= xjmax. The idea is to substitute xj with xj* whenever xj reaches its upper bound, and substitute xj* with xj when xj* reaches its upper bound.
| + | |
| − | Determining the pivot row is slightly more complicated when upper bounds are present. It is necessary to check if some variable reaches its upper bound when the entering variable is moved. This is done by checking also the ratios (xB-xB,maxi)/yi for yi<0. Prior to removing a variable from the basis based on the upper bound check, the variable substitution should be applied. The third possibility is that the entering variable xj itself reaches its upper bound before any basic variable reaches its either bound. To allow the algorithm to work also when the current solution is infeasible, the test is omitted for variables that are already on the wrong side of their bound. Thus, the maximum step to make is
| + | |
| − | (7)
| + | |
| − | Consider the sample model with upper bounds 0x18, and 0x24. The simplex table is
| + | |
| − | Basis x1 x2 s1 s2 Solution
| + | |
| − | z 2 3 0 0 0
| + | |
| − | s1 3 2 1 0 24 12
| + | |
| − | s2 1 2 0 1 12 6
| + | |
| − | 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
| + | |
| − | Basis x1 x2* s1 s2 Solution
| + | |
| − | z 2 -3 0 0 -12
| + | |
| − | s1 3 -2 1 0 16 5.333
| + | |
| − | s2 1 -2 0 1 4 4
| + | |
| − | 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.
| + | |
| − | Basis x1 x2* s1 s2 Solution
| + | |
| − | z 0 1 0 -2 -20
| + | |
| − | s1 0 4 1 -3 4 1
| + | |
| − | x1 1 -2 0 1 4 2
| + | |
| − | 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.
| + | |
| − | Basis x1 x2* s1 s2 Solution operation
| + | |
| − | z 0 0 -0.25 -1.25 -21
| + | |
| − | x2* 0 1 0.25 -0.75 1 x2* = 4-x2
| + | |
| − | x1 1 0 0.5 -0.5 6
| + | |
| − | 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.
| + | |
| − | Basis x1 x2 s1 s2 Solution operation
| + | |
| − | z 0 0 -0.25 -1.25 -21
| + | |
| − | x2 0 -1 0.25 -0.75 -3 *= -1
| + | |
| − | x1 1 0 0.5 -0.5 6
| + | |
| − | 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.
| + | |
| − | Basis x1 x2 s1 s2 Solution
| + | |
| − | z 0 0 -0.25 -1.25 -21
| + | |
| − | x2 0 1 -0.25 0.75 3
| + | |
| − | x1 1 0 0.5 -0.5 6
| + | |
| − | This same solution was found in the previous example without the upper bounds technique.
| + | |
| − | Handling Infeasibility
| + | |
| − | So far, we have assumed that the initial solution to the LP problem is feasible, i.e., all non-basic variables are within their bounds. This situation is true for example in models without upper bounds, where all constraints are of less or equal type with non-negative b. The Simplex algorithm will maintain the feasibility, while improving the objective function. If the initial solution is infeasible for some variables, the algorithm will preserve the feasibility of any feasible variables. The algorithm may also accidentally make some or all of the infeasible variables feasible, but cannot guarantee that all variable eventually become feasible.
| + | |
| − | To guarantee that the algorithm always finds a feasible optimal solution, it is necessary to handle the infeasibilities somehow. The so-called two-phase technique is based on first solving a related LP problem whose optimal solution provides a feasible solution for the original problem. In the second phase, the original problem is solved starting from the found feasible solution. If the model is in the canonical form with upper bounds (4) and we start with a slack basis, the infeasibilities are due to some bi>simax or some bi<0. The objective in first phase is then to minimize these infeasibilities:
| + | |
| − | min z’ =
| + | |
| − | s.t. (8)
| + | |
| − | Ax + s = b,
| + | |
| − | 0 x xmax
| + | |
| − | 0 s smax.
| + | |
| − | A more efficient single-pass technique is to use an objective function that is a linear combination of the original objective function and penalty terms:
| + | |
| − | min (fc+F) x (9)
| + | |
| − | Here x is the extended variable vector (including the slacks), f is a non-negative scaling factor (typically in the range [0,1], ideal value depends on problem type), and F is a row-vector of penalty terms
| + | |
| − | (10)
| + | |
| − | The objective function is modified during the algorithm. When a variable gains feasibility, the corresponding F-coefficient is set to zero. When the solution becomes feasible, the original objective function is restored by assigning f = 1. If the algorithm stops with an optimal but infeasible solution, this can mean that f is too large. In such cases f is decreased or set to zero and the algorithm proceeds. If no feasible solution is found even with zero f, this means that the model is infeasible (has no feasible solutions).
| + | |
| − | The penalty method is more efficient than the two-phase method, because it allows searching simultaneously for a feasible and optimal solution. There are additional benefits with the penalty method when solving large or numerically difficult LP problems. Sometimes the feasibility of the problem may be lost during the iterations. The penalty function can be easily reapplied whenever this happens.
| + | |
| − | The Revised Simplex algorithm
| + | |
| − | The tabular Simplex algorithm is suitable only for rather small problems, because the complete Simplex table has to be recomputed and maintained during the iterations. Large problems are usually solved using the so-called revised Simplex algorithm. The idea is to maintain information about the current basis inverse, and to compute only selected parts of the current simplex table.
| + | |
| − | We describe a generic variant of the Revised Simplex algorithm, which is commonly used for solving large LP problems (Taha, 1982, Flannery et al., 1988, Aittoniemi, 1988). The Simplex algorithm improves z iteratively by moving from one basic solution to another. In a basic solution the n-m non-basic variables are set to their lower or upper bounds and the values for the m basic variables are determined so that the constraints are satisfied. A, x and c are partitioned as
| + | |
| − | A = *B | N*, x = , c = *cB | cN*, (11)
| + | |
| − | where B is the non-singular basis matrix, N is the non-basic matrix, xB is the vector of basic variables, xN is the vector of non-basic variables, and cB and cN are the cost coefficients for the basic and non-basic variables. The constraints become then
| + | |
| − | BxB + NxN = b. (12)
| + | |
| − | To satisfy the constraints, xB is solved in terms of xN:
| + | |
| − | xB = B-1(b -NxN). (13)
| + | |
| − | The basic solution is feasible when the basic variables are within their bounds 0*xB*xB,max (any non-basic variable is by definition on its either bound). Introducing row vector * such that
| + | |
| − | * = cBB-1, (14)
| + | |
| − | and substituting xB and into the objective function gives
| + | |
| − | z = cBxB + cNxN = *b + (cN - *N)xN = *b - dxN, (15)
| + | |
| − | where
| + | |
| − | d = *N - cN (16)
| + | |
| − | is the row vector of the reduced costs for non-basic variables. The reduced costs indicate how z changes when non-basic variables are moved away from their bounds. The solution is optimal, if the optimality condition holds:
| + | |
| − | dj * 0 for all non-basic variables that are at their lower bound, and
| + | |
| − | dj * 0 for all non-basic variables that are at their upper bound.
| + | |
| − | Any non-basic variable that does not satisfy the optimality condition will improve the objective function value when entering the basis. Entering the basis means increasing the variable from its lower bound or decreasing it from its upper bound. However, this movement will affect the values of the non-basic variables. If the value of a non-basic variable is changed by , then, according to (13), the basic variable vector changes by , where we have introduced the so-called pivot column
| + | |
| − | y = B-1 Nj. (17)
| + | |
| − | The maximum allowed change for the entering variable must be chosen such that the feasibility of all basic variables is maintained, and one of the basic variables reaches its either bound, i.e., leaves the basis. This means finding the largest (in magnitude) change such that the following inequalities are still satisfied:
| + | |
| − | . (18)
| + | |
| − | The following procedure implements the generic Revised Simplex algorithm.
| + | |
| − | Algorithm summary: Generic Revised Simplex with upper bounds
| + | |
| − | 1. Start from some feasible basic solution (11).
| + | |
| − | 2. Compute the basic variables xB from (13), * from (14), and the reduced costs d from (16).
| + | |
| − | 3. Find a variable to enter the basis such that z improves. For variables at lower bound this condition is dj>0, and at upper bound dj<0. If there is no such variable, stop with optimal xB.
| + | |
| − | 4. Compute the pivot column y from (17).
| + | |
| − | 5. Find the variable to leave the basis such that feasibility is maintained. The leaving variable is the one that according to (18) reaches its upper or lower bound first when the entering is moved away from its bound. If there is no such variable, stop with an unbounded solution.
| + | |
| − | 6. Update the basis and go back to 2.
| + | |
| − | Different variants of the Revised Simplex algorithm use different techniques for representing and maintaining the basis and/or its inverse. For example, in the Product Form of Inverse (PFI) the basis inverse is represented as a product of elimination matrices, and each iteration contributes to one additional factor (B-1 = Ek Ek-1 … E1). In the Elimination Form of Inverse (EFI) a triangular factorisation of the non-inverted basis is maintained instead (B = LU, where L is lower triangular and U is upper triangular).
| + | |
| | | | |
| − | == '''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 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.
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
. 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}^{*}
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
. Because Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{2}^{*}
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
