Нет комментариев 28.12.2005

In the previous example we considered the solution of linear programming problem using the simplex method. We modified initial problem into the standard maximization problem with non-negative right-hand side of the constraints equations.

Let us consider more general case of solving standard maximization problem with arbitrary right-hand side of the constraints.

Initial linear programming (LP) problem:

4х1 + 15х2 + 12х3 + 2х4 -> min

2x2 + 3x3 + x4 >= 1
x1 + 3x2 + x3 - x4 >= 0
x1, x2, x3, x4 >=0

Convert initial LP problem to maximization LP problem:

-4х1 - 15х2 - 12х3 - 2х4 -> max

-2x2 - 3x3 - x4 <= -1
-x1 - 3x2 - x3 + x4 <= 0
x1, x2, x3, x4 >=0

Let S1, S2 >= 0 are slack variables.
Rewrite the constraint inequalities as equations by adding these variables:

-4х1 - 15х2 - 12х3 - 2х4 -> max (objective function)

0x1 - 2x2 - 3x3 - x4 + 1s1 + 0s2 = -1 (constraint equations)
-x1 - 3x2 - x3 + x4 + 0s1 + 1s2 = 0
x1, x2, x3, x4, s1, s2 >=0

Set up the initial simplex tableau (Click to see full size image):

1. The Cj row consists of the coefficients preceding x1, x2, x3, x4, s1, s2 from the objective function. 1 and 2 rows consist of the coefficients from the constraint equations. The RHS (right-hand side) column consists of -1 and 0 from right-hand side of these equations.
The variables that form an identity matrix are basic variables. S1 and S2 are the basic variables in our case.

2. The CB column consists of the coefficients preceding the basic variables in the objective function, i.e. 0 for S1 (row 1) and 0 for S2 (row 2).

3. The first element of the Zj row (in X1 column) is the sum of the products of multiplying each element in the CB column by each element in the X1 column.
0 (row 1, column CB) * 0 (row 1,column X1) + 0 (row 2, column CB) * (-1) (row 2,column X1) = 0
The subsequent elements of the Zj row (columns X2, X3, X4, S1, S2, RHS) are obtained in a similar way.

4. Compute the row 4 (Cj - Zj) by subtracting each element in the Zj row from each element in the Cj (top) row.

5. If all elements of the RHS (row 1, 2) are NON-NEGATIVE then go to 5''.
else go to 5'.

5'. For each rows (1 and 2) compute the ratios RHS/x, where x runs elements from columns
x1, x2, x3, x4, s1, s2. We seek the MINIMAL POSITIVE number (so we can compute only ratios with numerator and denominator are of the same sign).
Row 1:
column X2: (-1)/(-2)=0,5; column X3: (-1)/(-3)=0,3333(3); column X4: (-1)/(-1)=1
Row 2: all elements are zero

MINIMAL POSITIVE element is 0,33(3) from X3 column. Hence, 0,33(3) (mark green) is the leading element, X3 is the leading column, row 1 is the leading row. Go to 7.

7. Compute the rows 5 and 6: divide the leading row by the leading element and transform the leading column into identity column. Don't forget convert the RHS.

Let us make the next iteration step. In the previous step we compute the rows 5 and 6. Now all the RHS elements (0,33 and 0,33) are non-negative, hence go to 5".

5". We considered this case in the previous example. First, find the
LARGEST STRICTLY POSITIVE element in the (Cj-Zj) row (if there is not then go to the end of algorithm). This element is 2 from X4 column, row 8. So, X4 is new leading column.

6. Compute the ratios RHS/leading column for each row and find the MINIMAL POSITIVE element. This element gives us leading row. Intersection the leading row and the leading column give us leading element.
Row 5, Column X4: 0,33/0,33 = 1;
Row 6, Column X4: 0,33/1,33 = 0,25.
So, 1.33 (mark green) is new leading element. Go to 7.

Repeat iterations until (if the optimal solution exists) we can't find strictly positive leading element at the step 5' or 5" and 6.

In our example:
We form rows 9, 10, 11 and test RHS (rows 9, 10) for non-negativity (step 5). 0,25 and 0,25 are non-negative, hence, go to the step 5". 3,50 is the largest strictly positive number, but we can't find positive elements in this leading row (step 6). Hence, we have find the optimal solution:
X3 = 0,25;
X4 = 0,25;
Objective function value = -3,50 (mark red)

Жми!

 Loading ...