Simplex PDF

Preview

Summary

Simplex summary ...

Description

LINEAR PROGRAMMING – THE SIMPLEX METHOD

(1)

Problems involving both slack and surplus variables

A linear programming model has to be extended to comply with the requirements of the simplex procedure, that is, 1. All equations must be equalities. 2. All variables must be present in all equations. (I) (II)

In the case of ‘ ’ constraints, slack variables are added to the actual variables to make the equation an equality. In the case of ‘ ’ constraints, surplus variables are used to make the equation an equality.

A surplus variable is the difference between the total value of the true (decision) variables and the number (usually, total resource available) on the right-hand side of the equation. Thus, a surplus variable will always have a negative value.

Consider the following linear programming problem: Minimise cost = 6 X 1

8X 2

Subject to X1 X1

X2

5000 1500

X2

750

X1 , X 2

0

There are three constraints, consisting of one equality, one ‘smaller than or equal to’ and one ‘greater than or equal to’.

The model should now be modified as follows:

X1 X1

X2

5000 1500

S1 X2

X 1, X 2 , S 1, S 2

S2

750 0

where S1 is a slack variable and S 2 is a surplus variable.

2 The presence of a surplus variable causes a problem when drawing the first simplex tableau because of its negative value. In any maximisation problem, this tableau must satisfy the following requirements: 1. 2. 3.

All the slack variables (and thus surplus variables as well) must form part of the initial solution mix (basis). The table must contain as many rows as there are constraints. The elements in the columns of variables appearing in the basis must form a unit vector.

If S 2 is included in the basis, the elements of the S 2 will be 0, 0 and –1 and thus not a unit vector. Furthermore, the values of the true variables being 0 in the initial solution, this would imply that S 2 would assume a negative value in the initial solution (it can be easily checked by means of the third equality that, if X 2 = 0, S 2 = –750). This is definitely contrary to the nonnegativity restriction – all variables must have a positive value.

(2)

Artificial variables

This problem is solved by adding an artificial variable (denoted by A i ) to the equation, that is, a variable that has a positive value. Artificial variables are also used in equations which are already equalities in order to comply with the requirements (1) and (2) above. Just remember that an artificial variable has no significance pertaining to the solution of the problem – it is used merely to find a solution mix in the first simplex tableau. Although artificial variables will always form part of the initial solution mix, the objective is to remove them as soon as possible by means of the simplex procedure. As long as an artificial variable still appears in the solution mix, the final solution has not yet been found. As any other variable, artificial variables are included in the objective function but the value attached to them creates another problem. In minimisation problems, since the objective is to find the lowest cost possible, a very large value is allocated to artificial variables. This value is denoted by M where M is a very large positive value. The above linear programming model is thus rewritten as Minimise cost = 6 X 1

8X 2

0 S1

0S 2

MA1

MA2

Subject to 1X 1

1X 2

0S 1

0S 2

1A1

0A2

5000

1X 1

0X 2

1S 1

0S 2

0A1

0 A2

1500

0 X 1 1 X 2 0S 1 1S 2 0 A1 X 1 , X 2 , S 1 , S 2 , A1 , A2 0

1A2

750

before using the simplex procedure.

3 Example 1 (slack variables only) [Maximisation] Linpro Limited, a manufacturing enterprise, produces two products, namely product A and product B. Both products are manufactured from the same raw material and processed by the same machine. The available machine capacity is 600 hours and 10 000 kilogram of raw materials are available. The production of one unit of product A utilises 30 minutes of machine time while one unit of product B takes one hour to produce. To produce one unit of product A, 12.5 kg of raw material is required whereas 10 kg is required for one unit of product B. The marginal income of product A, of which a maximum of 700 units can be sold, amounts to R4 per unit. Product B has a marginal income of R6 per unit. The company wants to determine what combination of product A and product B must be produced in order to obtain maximum profit. Formulate a linear programming model for the above problem and hence find the optimal solution by using the simplex method.

Solution 1 We first identify our decision variables, objective function and thus write down the constraints. Let the decision variables

X 1 = “number of units of product A to be manufactured” and X 2 = “number of units of product B to be manufactured” [Decision variables are normally those which appear in the objective function. It is always better to use similar symbols instead of the traditional x and y to avoid confusion. We can, for example, choose to denote our decision variables by the first letters of the names of the products. However, for the simplex method, it is advisable to use indexed variables.] The objective function may be formulated as follows (it can be obtained from the table below): Maximise Profit = 4 X 1

6X 2

A table may also reveal to be helpful in understanding the problem better and to write down the constraints easily as well. Consider the following:

Machine capacity (hrs) Raw material (kg) Demand (at most) Marginal income

Product A 0.5 12.5 700 R4

Product B 1 10 R6

The constraints follow: X2 600 0.5 X1 X 12.5 1 10 X 2 10000 X1

700

X 1, X 2

0

Total available resource 600 10000

4 Now, we must ‘prepare’ this linear system of inequalities before using the simplex method. We convert all inequalities to equalities by introducing slack variables. The new model is Maximise Profit = 4 X 1

6X 2

0 S1

0S 2

0S 3

subject to 0 .5 X 1

X2

S1

600

12.5 X 1 10 X 2 X1 X1 , X2

S2

10000 700

S3 0

where S1 , S 2 and S 3 are slack variables.

Tableau of the initial solution

Solution mix

Quantity

S1 S2 S3

600 10000 700

X1 0.5 12.5 1

X2 1 10 0

S1 1 0 0

S2 0 1 0

S3 0 0 1

The first simplex tableau

Cj

4

6

0

0

0

Quantity 600

X1

X2

S1

S2

S3

0

Solution mix S1

0.5

1

1

0

0

0 0

S2 S3

10000 700

12.5 1

10 0

0 0

1 0

0 1

Zj

0

0

0

0

0

0

Cj

Zj

4

6

0

0

0

[Explanation for notation C j (row) = coefficients of variables in the objective function C j (column) = coefficients of solution mix variables in the objective function Z j = sum of the products of the C j column elements and corresponding variable column elements. For example, the bold zero in the table is obtained as follows: (0 1) (0 10) ( 0 0) Note that the shaded cell gives the optimal profit.

]

5 The simplex procedure can be summarised as follows: 1.

Find the pivot column – the column that has the greatest positive entry in the C j Z j row. If there are no positive entries in a tableau, it means that the optimal solution has already been reached.

Cj 0 0

0 S1

0 S2

0 S3

Quantity 600 10000

0.5 12.5

1 10

1 0

0 1

0 0

S3 Zj

700

1

0

0

0

1

0

0

0

0

0

0

6*

0

0

0

Cj

Zj

4

Find the pivot row. Divide each solution mix entry in the Quantity column by its corresponding entry in the pivot column and record the result in the Ratio column. The smallest non-negative ratio determines the pivot row.

Cj 0 0 0

4

6

0

0

0

Solution mix S1 S2

Quantity 600 10000

X1

X2

S1

S2

0.5 12.5

1

1

0

S3 0

10

0

1

0

S3 Zj

700

1

0

0

0

1

0

0

0

0

0

0

6

0

0

0

Cj

3.

6 X2

Solution mix S1 S2

0

2.

4 X1

Zj

4

Ratio 600* 1000

Pivot row

Select the pivot element in order to start applying basic row operations. The pivot element is found at the intersection of the pivot row and the pivot column. It indicates which variable will enter the solution mix and which one will leave. In the above table, the pivot element is 1 (indicated in bold). We deduce that X 2 will enter the solution mix and that S1 will leave. Why S1 ? Simply because, it is the solution mix slack variable which is found in the first row.

6 The second simplex tableau

Now, we have to perform basic row operations in order to make the X 2 column entries identical to those in the unit vector that was in the S 1 column. In this context, we will consider only two (out of the possible three) basic row operations: 1. 2.

Multiply a row by a non-zero constant. Add a multiple of a row to another row.

Cj 0 0

4 Solution mix S1 S2

Quantity X 1 600 0.5 10000 12.5

S3 Zj

0 Cj

Zj

6

0

0

0

X2

S1

S2

S3

Ratio

1 10

1 0

0 1

0 0

600* 1000

700

1

0

0

0

1

0

0

0

0

0

0

6

0

0

0

4

Pivot row

For example, if we have to make 10 (indicated in bold above) become 0, we have to take 10 subtract 10 times1 (the pivot element). In so doing, all the entries of the second row must also subtract 10 times the entries in the first. Remember, we only consider the entries in the rows involving the solution mix variables – in this case, S2 and S 3 . The last entry in the pivot column being a zero, we don’t need any further basic row operations – at least one good thing here! The entries of the Z j and C j Z j rows need to be recalculated. The complete second simplex tableau looks like

Cj

4

6

0

0

0

Quantity 600

X1

X2

S1

S2

S3

6

Solution mix X2

0.5

1

1

0

0

0 0

S2 S3

4000 700

7.5 1

0 0

–10 0

1 0

0 1

3600 1

3

6

6

0

0

0

–6

0

0

Zj Cj

Zj

This procedure is repeated until there are no more positive entries in the C j case we would have reached the optimal solution.

Z j row, in which

7 The third simplex tableau

Cj 6 0

4 X1

6 X2

0 S1

0 S2

0 S3

Solution mix X2 S2

Quantity 600 4000

0.5 7.5

1 0

1 –10

0 1

0 0

S3 Zj

700

1

0

0

0

1

3600

3

6

6

0

0

1

0

–6

0

0

0 Cj

Zj

Ratio 1200 533*

Pivot row

700

pivot column The largest positive entry in the last row is 1 so that the pivot column is the X 1 column. The ratios of Quantity: X 1 are recalculated and it is found that 533 is the smallest non-negative value, meaning that the pivot row is the S 2 row. Thus, the pivot element is 7.5 (indicated in bold) so that S 2 has to leave the solution mix for X 1 to enter. Logically, we don’t expect any other tableaus to come up since both decision variables have entered the solution mix! Using basic row operations, we first divide the second row entries by 7.5 to obtain a 1 in its place before converting the 0.5 and 1 in the same column to zeros.

Cj

4

6

0

0

0

Quantity 600

X1

X2

S1

S2

S3

6

Solution mix X2

0.5

1

1

0

0

0 0

S2 S3

533 700

1 1

0 0

–1.33 0

0.13 0

0 1

3600

3 1

6 0

6 –6

0 0

0 0

Zj Cj

Zj

Basic row operations: ‘First row minus half second row’ and ‘third row minus second row’. Cj

4

6

0

0

0

Quantity 333

X1

X2

S1

S2

S3

6

Solution mix X2

0

1

1.67

–0.067

0

4 0

X1 S3

533 167

1 0

0 0

–1.33 1.33

0.13 –0.13

0 1

4130

4 0

6 0

4.67 –4.67

0.13 –0.13

0 0

Zj Cj

Zj

8 As predicted, this is the final simplex tableau since there are no more positive entries in the last row. We have therefore reached the optimal solution! Remember that the slack variable S 3 is not a decision variable.

Interpretation of the final simplex tableau 1.

The final (optimal) solution is X1 533 and X 2 333 so that the optimal profit is R4130. In fact, this solution mix corresponds to a corner-point (vertex) on graph. Note that each number in the columns of the variables occurring in the solution mix represents a unit vector.

2.

The entry at the intersection of the S 1 column and the C j

Z j row, –4.67,

represents the amount by which the total profit will decrease for every unit of S 1 added to the solution mix, that is, R4.67. If the available machine hours are reduced by one hour, X 2 will be reduced by 1.67 units in the solution mix whereas X 1 will be increased by 1.33 units. Decrease in profit = R6 Increase in profit = R4 Net decrease in profit 3.

1.67 = R10.00 1.33 = R 5.33 = R 4.67

The entry at the intersection of the S 1 column and the Z j row, 4.67, represents the amount by which the total profit will increase if one additional machine hour is made available for the production of product A and production B (that is, 601 machine hours). The shadow price with respect of one machine hour is thus R4.67.

4.

The entry at the intersection of the S 2 column and the Z j row, 0.13, is the shadow price with respect to one kilogram of raw material. If the available raw material is increased by one kilogram, the total profit will increase by 13 cents.

5.

The entry at the intersection of the S 3 column and the Z j row, 0, is the shadow price with respect to the demand for product A. Since the current solution mix does not fully satisfy the demand for product A, ( S 3 1 .67) , an increase in the demand for this product will have no influence on the total profit.

9 Example 2 (slack and artificial variables) [Minimisation] A producer of fertiliser receives an order to supply exactly 5000 kg of fertiliser, consisting of a special mixture of phosphate and ammonium nitrate. The mixture must not contain more than 1500 kg of phosphate and not less than 750 kg of ammonium nitrate. The cost per kilogram of phosphate and ammonium nitrate are R6 and R8 respectively. The producer would like to determine the ratio in which raw materials must be combined so as to limit costs to a minimum. Formulate a linear programming model for the above problem and hence find the optimal solution by using the simplex method.

Solution 2 We first identify our decision variables, objective function and thus write down the constraints. Let the decision variables

X 1 = “number of kg of phosphate” and X 2 = “number of kg of ammonium nitrate” The objective function may be formulated as follows: Minimise Cost = 6 X 1

8X 2

The constraints are X1 X1

X2

5000 1500

X2 X1 , X2

700 0

[Note that this the very same example on artificial variables mentioned above.] The above linear programming model is thus modified as Minimise cost = 6 X 1

8X 2

0 S1

0S 2

MA1

MA2

Subject to 1X 1

1X 2

0S 1

0S 2

0A2

5000

1X 1 0X 2 1S 1 0S 2 0A1 0 A2 0 X 1 1 X 2 0S 1 1S 2 0 A1 1A2

1500 750

X 1 , X 2 , S 1 , S 2 , A1 , A2 before using the simplex procedure.

1A1

0

10 Tableau of the initial solution

Solution mix

A1 S1

Quantity 5000 1500

X1 1 1

X2 1 0

S1 0 1

S2 0 0

A1 1 0

A2 0 0

A2

750

0

1

0

–1

0

1

The first simplex tableau

Cj

6

8

0

0

M

M

Quantity 5000

X1

X2

S1

S2

A1

A2

M

Solution mix A1

1

1

0

0

1

0