• Categories
• Optimización matemática
• Métodos matemáticos y cuantitativos (Economía)
• Análisis de sistemas
• Matemática aplicada
• Física y matemáticas

Citation preview

M U

O L

D E

7 Linear Programming: The Simplex Method Teaching Suggestions Teaching Suggestion M7.1: Meaning of Slack Variables. Slack variables have an important physical interpretation and represent a valuable commodity, such as unused labor, machine time, money, space, and so forth. Teaching Suggestion M7.2: Initial Solutions to LP Problems. Explain that all initial solutions begin with X1 = 0, X2 = 0 (that is, the real variables set to zero), and the slacks are the variables with nonzero values. Variables with values of zero are called nonbasic and those with nonzero values are said to be basic. Teaching Suggestion M7.3: Substitution Rates in a Simplex Tableau. Perhaps the most confusing pieces of information to interpret in a simplex tableau are “substitution rates.” These numbers should be explained very clearly for the first tableau because they will have a clear physical meaning. Warn the students that in subsequent tableaus the interpretation is the same but will not be as clear because we are dealing with marginal rates of substitution. Teaching Suggestion M7.4: Hand Calculations in a Simplex Tableau. It is almost impossible to walk through even a small simplex problem (two variables, two constraints) without making at least one arithmetic error. This can be maddening for students who know what the correct solution should be but can’t reach it. We suggest two tips: 1. Encourage students to also solve the assigned problem by computer and to request the detailed simplex output. They can now check their work at each iteration. 2. Stress the importance of interpreting the numbers in the tableau at each iteration. The 0s and 1s in the columns of the variables in the solutions are arithmetic checks and balances at each step. Teaching Suggestion M7.5: Infeasibility Is a Major Problem in Large LP Problems. As we noted in Teaching Suggestion 7.6, students should be aware that infeasibility commonly arises in large, real-world-sized problems. This module deals with how to spot the problem (and is very straightforward), but the real issue is how to correct the improper formulation. This is often a management issue.

M7­1

Copyright ©2015 Pearson, Inc.

Alternative Examples Alternative Example M7.1: Simplex Solution to Alternative Example 7.1 (see Chapter 7 of Solutions Manual for formulation and graphical solution). 1st Iteration Cj  

Solution Mix

3 X1

0 0

S1 S2 Zj Cj – Z j 2nd Iteration Cj  

1 1 0 3 3 X1

9

Solution Mix X2

0

S2

1

Zj

9

Cj – Z j

3

1

4 2 4 4

9 X2

0 S1

4 2 0 9

0 S2

1 0 0 0

0 1 0 0

9 X2 1 0 9 0

Quantity 24 16 0

0 S1 1

4 1 2



0 S2 0

Quantity 6

1

4

0

54

9



4 9 4

0

This is not an optimum solution since the X1 column contains a positive value. More profit remains ($

3

4

per #1).

3rd/Final Iteration Cj   9 3

Solution Mix X2

3 X1 0

9 X2 1

0 S1

0 S2

1

2

 12

X1 Zj

1 3

0 9

1

2

3

3

Cj – Z j

0

0



2 3 2



2 3 2

Quantity 4 8 60

This is an optimum solution since there are no positive values in the Cj – Zj row. This says to make 4 of item #2 and 8 of item #1 to get a profit of $60.

M7­2

Copyright ©2015 Pearson, Inc.

Alternative Example M7.2: Set up an initial simplex tableau, given the following two constraints and objective function: Minimize Z = 8X1 + 6X2 2X1 + 4X2  8

Subject to:

3X1 + 2X2  6 The constraints and objective function may be rewritten as: Minimize = 8X1 + 6X2 + 0S1 + 0S2 + MA1 + MA2 2X1 + 4X2 – 1S1 + 0S2 + 1A1 + 0A2 = 8 3X1 + 2X2 + 0S1 – 1S2 + 0A1 + 1A2 = 6 The first tableau would be: Cj  

Solutio n Mix M A1 M A2 Zj Cj – Z j The second tableau: Cj  

8 X1

6 X2

2 3 5M 8 – 5M

4 2 6M 6 – 6M

8 X1

6 X2

6

Solutio n Mix X2

1

1

M

A2

2

0

Zj

3+ 2M

6

5 – 2M

0

Cj – Z j

0 S1

2

0 S2

–1 0 –M M 0 S1 

1

1

4

3

2

M  12

0 –1 –M M

1 0 M 0

0 S2

M A1

0

1

4  12 3  1 2 2

–1

2

 32 

M A1

1

2

M

–M M

 32 

M A2 0 1 M 0

Quantity 8 6 14M

M A2

M 3

0

Quantity 2

1

2

M

12 + 2M

0

2

M

The third and final tableau: Cj 

8 X1

6 X2

6

Solutio n Mix X2

0

1

8

X1

1

0

Zj

8

6

Cj – Z j

0

0

0 S1

0 S2

M A1

1

3

M A2 Quantity



3

1

8

4 1  4 1 4

4  12  52 5 2

8  14 1 4 1

M–



1 5 4

M7­3

3

2

3

4

2

1

2 2 5

M–

A minimal, optimum cost of 17 can be achieved by using 1 of a type #1 and Copyright ©2015 Pearson, Inc.

1

17 2

of a type #2.

Alternative Example M7.3: Referring back to Hal, in Alternative Example 7.1, we had a formulation of: Maximize Profit = $3X1 + $9X2 Subject to: 1X1 + 4X2  24 clay 1X1 + 2X2  16 glaze where X1 = small vases made X2 = large vases made The optimal solution was X1 = 8, X2 = 4. Profit = $60. Using software (see the printout), we can perform a variety of sensitivity analyses on this solution.

M7­4

Copyright ©2015 Pearson, Inc.

Alternative Example M7.4: Levine Micros assembles both laptop and desktop personal computers. Each laptop yields $160 in profit; each desktop $200. The firm’s LP primal is: Maximize profit = $160X1 + $200X2 subject to: 1X1 + 2X2  20 labor hours 9X1 + 9X2  108 RAM chips 12X1 + 6X2  $120 royalty fees where X1 = no. laptops assembled daily X2 = no. desktops assembled daily Here is the primal optimal solution and final simplex tableau. Cj   200

Solution Mix X2

$160 X1 0

$200 X2 1

0 S1 1

160

X1

1

0

–1

2

0

S3 Zj

0 160

0 200

6 40

Cj – Z j

0

0

–40

0 S2

0 S3 0

Quantity 8

0

4

–2 13 1 3

1 0

24 $2,240

13 1 3

0

 19 9

or X1 = 4, X2 = 8, S3 = $24 in slack royalty fees paid Profit = $2,240/day Here is the dual formulation: Minimize Z = 20y1 + 108y2 + 120y3 subject to: 1y1 + 9y2 + 12y3  160 2y1 + 9y2 + 6y3  200 Here is the dual optimal solution and final tableau. Cj  108 20

Solution Mix y2

y1 Zj Cj – Z j This means

20 y1 0

108 y2 1

120 y3 2

1 20 0

0 108 0

–6 96 +24

0 S1  29 1 –4 +4

0 S2 1

y1 = marginal value of one more labor hour = $40 y2 = marginal value of one more RAM chip = $13.33 y3 = marginal value of one more $1 in royalty fees = $0 M7­5

9

–1 –8 +8

Copyright ©2015 Pearson, Inc.

Quantity 13 1 3 40 $2,240

Solutions to Discussion Questions and Problems M7-1. The purpose of the simplex method is to find the optimal solution to LP problems in a systematic and efficient manner. The procedures are described in detail in Section M7.3. M7-2. Differences between graphical and simplex methods: (1) Graphical method can be used only when two variables are in model; simplex can handle any dimensions. (2) Graphical method must evaluate all corner points (if the corner point method is used); simplex checks a lesser number of corners. (3) Simplex method can be automated and computerized. (4) Simplex method involves use of surplus, slack, and artificial variables but provides useful economic data as a byproduct. Similarities: (1) Both methods find the optimal solution at a corner point. (2) Both methods require a feasible region and the same problem structure, that is, objective function and constraints. The graphical method is preferable when the problem has two variables and only two or three constraints (and when no computer is available). M7-3. Slack variables convert  constraints into equalities for the simplex table. They represent a quantity of unused resource and have a zero coefficient in the objective function. Surplus variables convert  constraints into equalities and represent a resource usage above the minimum required. They, too, have a zero coefficient in the objective function. Artificial variables have no physical meaning but are used with the constraints that are = or . They carry a high coefficient, so they are quickly removed from the initial solution. M7-4. The number of basic variables (i.e., variables in the solution) is always equal to the number of constraints. So in this case there will be eight basic variables. A nonbasic variable is one that is not currently in the solution, that is, not listed in the solution mix column of the tableau. It should be noted that while there will be eight basic variables, the values of some of them may be zero. M7-5. Pivot column: Select the variable column with the largest positive Cj – Zj value (in a maximization problem) or smallest negative Cj – Zj value (in a minimization problem). Pivot row: Select the row with the smallest quantity-to-column ratio that is a nonnegative number. Pivot number: Defined to be at the intersection of the pivot column and pivot row. M7-6. Maximization and minimization problems are quite similar in the application of the simplex method. Minimization problems usually include constraints necessitating artificial and surplus variables. In terms of technique, the Cj – Zj row is the main difference. In maximization problems, the greatest positive Cj – Zj indicates the new pivot column; in minimization problems, it’s the smallest negative Cj – Zj. The Zj entry in the “quantity” column stands for profit contribution or cost, in maximization and minimization problems, respectively. M7-7. The Zj values indicate the opportunity cost of bringing one unit of a variable into the solution mix.

M7­6

Copyright ©2015 Pearson, Inc.

M7-8. The Cj – Zj value is the net change in the value of the objective function that would result from bringing one unit of the corresponding variable into the solution. M7-9. The minimum ratio criterion used to select the pivot row at each iteration is important because it gives the maximum number of units of the new variable that can enter the solution. By choosing the minimum ratio, we ensure feasibility at the next iteration. Without the rule, an infeasible solution may occur. M7-10. The variable with the largest objective function coefficient should enter as the first decision variable into the second tableau for a maximization problem. Hence X3 (with a value of $12) will enter first. In the minimization problem, the least-cost coefficient is X1, with a $2.5 objective coefficient. X1 will enter first. M7-11. If an artificial variable is in the final solution, the problem is infeasible. The person formulating the problem should look for the cause, usually conflicting constraints. M7-12. An optimal solution will still be reached if any positive Cj – Zj value is chosen. This procedure will result in a better (more profitable) solution at each iteration, but it may take more iterations before the optimum is reached. M7-13. A shadow price is the value of one additional unit of a scarce resource. The solutions to the Ui dual variables are the primal’s shadow prices. In the primal, the negatives of the Cj – Zj values in the slack variable columns are the shadow prices. M7-14. The dual will have 8 constraints and 12 variables. M7-15. The right-hand-side values in the primal become the dual’s objective function coefficients. The primal objective function coefficients become the right-hand-side values of dual constraints. The transpose of the primal constraint coefficients become the dual constraint coefficients, with constraint inequality signs reversed. M7-16. The student is to write his or her own LP primal problem of the form: maximize profit = C1X1 + C2X2 subject to A11X1 + A12X2  B1 A21X1 + A22X2  B2 and for a dual of the nature: minimize cost = B1U1 + B2U2 subject to A11U1 + A21U2  C1 A12U1 + A22U2  C2

M7­7

Copyright ©2015 Pearson, Inc.

M7-17. a.

b. The new optimal corner point is (0,60) and the profit is 7,200. c. The shadow price = (increase in profit)/(increase in right­hand side value) = (7,200 – 2,400)/(240 – 80) = 4,800/160 = 30 d. With the additional change, the optimal corner point in part B is still the optimal corner point. Profit doesn’t change. Once the right-hand side went beyond 240, another constraint prevented any additional profit, and there is now slack for the first constraint. M7-18. a. See the table below. Table for Problem M7-18 Cj   0 0

Solution Mix S1 S2 Zj Cj – Z j b.

$900 X1 14 10 0 900

$1,500 X2 4 12 0 1,500

$0 S1 1 0 0 0

$0 S2 0 1 0 0

Quantity 3,360 9,600 0

14X1 + 4X2  3,360 10X1 + 12X2  9,600 X1, X2  0

c.

Maximize profit = 900X1 + 1,500X2

d.

Basis is S1 = 3,360, S2 = 9,600.

e.

X2 should enter basis next.

f.

S2 will leave next.

g.

800 units of X2 will be in the solution at the second tableau.

h.

Profit will increase by (Cj – Zj)(units of variable entering the solution) M7­8

Copyright ©2015 Pearson, Inc.

= (1,500)(800) = 1,200,000 M7-19. a. Maximize earnings = 0.8X1 + 0.4X2 + 1.2X3 – 0.1X4 + 0S1 + 0S2 – MA1 – MA2 subject to X1 + 2X2 + X3 + 5X4 + S1 = 150 X2 – 4X3 + 8X4 + A1 = 70 6X1 + 7X2 + 2X3 – X4 – S2 + A2 = 120 b. See initial simplex tableau in Table M7-19b below. Table for Problem M7-19b Cj  0 –M –M

Solution Mix S1 A1 A2 Zj Cj – Zj

0.8 X1 1 0 6 –6M 0.8 + 6M

0.4 X2 2 1 7 –8M 0.4 + 8M

1.2 X3 1 –4 2 2M 1.2 – 2M

0.1 X4 5 8 –1 –7M –0.1 + 7M

0 S1 1 0 0 0 0

0 S2 0 0 –1 M –M

M A1 0 1 0 –M 0

M A2 0 0 1 –M 0

Quantity 150 70 120 –190M

150, A1 = 70, A2 = 120, all other variables = 0 M7-20. First tableau: Cj   $0 $0

Solution Mix S1 S2 Zj Cj – Z j Second tableau:

$3 X1 0 3 $0 $3

Cj   $5 $0

$5 X2 1 2 $0 $5

$0 S1 1 0 $0 $0

$0 S2 0 1 $0 $0

Quantity 6 18 $0

Quantity 6 6 $30

Solution $3 Mix X1 X2 0 S2 3 Zj $0 Cj – Z j $3 Third and optimal tableau:

$5 X2 1 0 $5 $0

$0 S1 1 –2 $5 –$5

$0 S2 0 1 $0 $0

Cj   $5 $3

$5 X2 1 0

$0 S1 1  23

$0 S2 0

$3 –$3

$1 –$1

Solution Mix X2 X1

$3 X1 0 1

Zj $3 $5 Cj – Z j $0 $0 X1 = 2, X2 = 6, S1 = 0, S2 = 0, and profit = $36

M7­9

Copyright ©2015 Pearson, Inc.

1

3

Quantity 6 2 $36

c. S 1

=

Graphical solution to Problem M7-20:

M7-21. a.

b. Cj   0 0

Solution 10 Mix X1 S1 4 S2 1 Zj 0 Cj – Z j 10 This represents the corner point (0,0).

8 X2 2 2 0 8

0 S1 1 0 0 0

0 S2 0 1 0 0

c. The pivot column is the X1 column. The entering variable is X1. d. Ratios:

Row 1: 80/4 = 20 Row 2: 50/1 = 50

These represent the points (20,0) and (50,0) on the graph. M7­10

Copyright ©2015 Pearson, Inc.

Quantity 80 50 0

e. The smallest ratio is 20, so 20 units of the entering variable (X1) will be brought into the solution. If the largest ratio had been selected, the next tableau would represent an infeasible solution since the point (50,0) is outside the feasible region. f. The leaving variable is the solution mix variable in row with the smallest ratio. Thus, S1 is the leaving variable. The value of this will be 0 in the next tableau. g. Second iteration Solution Cj  Mix  10 X1 0 S2 Zj Cj – Z j Third iteration

10 X1 1 0 10 0

8 X2 0.5 1.5 5 3

0 S1 0.25 –0.25 2.5 –2.5

Cj   10 8

0 S2 0 1 0 0

Quantity 20 30 200

Solution 10 8 0 0 Quantity Mix X1 X2 S1 S2 X1 1 0 0.3333 –0.3333 10 X2 0 1 –0.1667 0.6667 20 Zj 10 8 2 2 260 Cj – Z j 0 0 –2 –2 h. The second iteration represents the corner point (20,0). The third (and final) iteration represents the point (10,20). M7-22. Basis for first tableau: A1 = 80 A2 = 75 (X1 = 0, X2 = 0, S1 = 0, S2 = 0) Second tableau: A1 = 55 X1 = 25 (X2 = 0, S1 = 0, S2 = 0, A2 = 0) Graphical solution to Problem M7-22:

M7­11

Copyright ©2015 Pearson, Inc.

Third tableau:

X1 = 14 X2 = 33

(S1 = 0, S2 = 0, A1 = 0, A2 = 0) Cost = $221 at optimal solution M7-23. This problem is infeasible. All Cj – Zj are zero or negative, but an artificial variable remains in the basis. M7-24. At the second iteration, the following simplex tableau is found: Cj   6 0

Solution Mix X1

6 X1 1

3 X2 –1

S2

0

0

0 S1 1 1

2

0 S2 0

Quantity 1

1

2

2

Zj 6 –6 3 0 6 Cj – Z j 0 9 –3 0 At this point, X2 should enter the basis next. But the two ratios are 1/–1 = negative and 2/0 = undefined. Since there is no nonnegative ratio, the problem is unbounded. M7-25. a. The optimal solution using simplex is X1 = 3, X2 = 0. ROI = $6. This is illustrated in the problem’s final simplex tableau: Tableau for Problem M7-25a Cj   0 2

Solution Mix S1

2 X1 0

3 X2

0 S1

7

3

X1

1

3

2

1

2

2

0 S2 1

M A1 –1

Quantity 6

0

0

3

2

Zj 2 3 1 0 0 $6 Cj – Z j 0 0 –1 0 –M b. The variable X2 has a Cj – Zj value of $0, indicating an alternative optimal solution exists by inserting X2 into the basis. c. The alternative optimal solution is found in the tableau in the next column to be X1 = 3

7

= 0.42, X2 =

12

7

= 1.7, ROI = $6.

Tableau for Problem M7-25c Cj   3 2

Solution Mix X2

2 X1 0

3 X2 1

X1

1

0

Zj

2

3

Cj – Z j

0

0

0 S1

0 S2

M A1

1

2



7  1 21 1 3 1  3

M7­12

Copyright ©2015 Pearson, Inc.



21 1 7

2

3

7

7

0

0

0

–M

Quantity 12 3

7

7

$6

d. The graphical solution is shown below.

Alternative optimums at a and b, Z = $6. M7-26. This problem is degenerate. Variable X2 should enter the solution next. But the ratios are as follows: X 3 row

5 5 1

X 1 row

12  unacceptable 3

S2

10 5 2

Since X3 and S2 are tied, we can select one at random, in this case S2. The optimal solution is shown below. It is X1 = 27, X2 = 5, X3 = 0, profit = $177. Cj  

6 X1

$5

Solutio n Mix X3

3 X2

5 X3

0 S1

0

0

1

1

$6

X1

1

0

0

3

$3

X2

0

1

0

1

Zj Cj – Z j

6 0

3 0

5 0

2 2 2

13 –13

M7­13

0 S2 

1

3 1

2

0 S3 7

2



2



8 –8

Copyright ©2015 Pearson, Inc.

2 1 2 1 2

13 –13

Quantity 0 27 5 $177

M7-27. Minimum cost = 50X1 + 10X2 + 75X3 + 0S1 + MA1 + MA2 subject to 1X1 – 1X2 + 0X3 + 0S1 + 1A1 + 0A2 = 1,000 0X1 + 2X2 + 2X3 + 0S1 + 0A1 + 1A2 = 2,000 1X1 + 0X2 + 0X3 + 1S1 + 0A1 + 0A2 = 1,500 First iteration: Cj  M M 0

Solution Mix

50 X1 1 0 1 M –M + 50

10 X2 –1 2 0 M –M + 10

Solution Mix A1 X3

50 X1 1 0

S1 Zj Cj – Zj

A1 A2 S1 Zj Cj – Zj

75 X3 0 2 0 2M –2M + 75

0 S1 0 0 1 0 0

M A1 1 0 0 M 0

M A2 0 1 0 M 0

10 X2 –1 1

75 X3 0 1

0 S1 0 0

M A1 1 0

M A2 0

1 M

0 –M + 75

0 75

1 0

0 M

0

–M + 50

M – 65

0

0

0

Quantity 1,000 2,000 1,500 3,000M

Second iteration: Cj  M 75 0

1

37 M–

Quantity 1,000 1,000

2

1,500 1,000M + 75,000

1

2 37 1

2

Third iteration: Cj  50 75 0

Solution Mix X1 X3

50 X1 1 0

10 X2 –1 1

75 X3 0 1

0 S1 0 0

M A1 1 0

M A2 0

S1 Zj

0 50

1 25

0 75

1 0

–1 50

0

Cj – Zj

0

–15

0

0

M – 50

X1 X3

50 X1 1 0

10 X2 0 0

75 X3 0 1

0 S1 1 –1

M A1 0 1

M A2 0

X2 Zj

0 50

1 10

0 75

1 –15

–1 65

0

Cj – Zj

0

0

0

15

M – 65

1

2

37 1 2 M–

Quantity 1,000 1,000 500 $125,000

37 1 2

Fourth and final iteration: Cj  50 75 10

Solution Mix

X1 = 1,500, X2 = 500, X3 = 500, Z = $117,500 M7­14

Copyright ©2015 Pearson, Inc.

1

2

37 1 2 M–

37 1 2

Quantity 1,500 500 500 $117,500

M7-28. X1 = number of kilograms of brand A added to each batch X2 = number of kilograms of brand B added to each batch Minimize costs = 9X1 + 15X2 + 0S1 + 0S2 + MA1 + MA2 subject to X1 + 2X2 – S1 + A1 = 30 X1 + 4X2 – S2 + A2 = 80 Cj   M M

Solution Mix A1 A2 Zj Cj – Z j

$9 X1 1 1 2M –2M + 9

$15 X2 2 4 6M –6M + 15

$0 S1 –1 0 –M M

$0 S2 0 –1 –M M

M A1 1 0 M 0

M A2 0 1 M 0

Quantity 30 80 110M

First iteration: Cj   15 M

Solution Mix X2

1

A2 Zj

15

Cj – Z j

3

2

–1

Second iteration: Solution Cj  Mix  15 X2 0

$9 X1

S1 Zj Cj – Z j

–M

2

2

+M

$9 X1 1

4 1  2 15 4 21 4

$15 X2 1

$0 S1 

0 15

 15

0

15

1

$0 S2 0

2

2 2

2

–1 –M

+ 2M

M

– 2M

$15 X2 1

$0 S1 0

$0 S2 

1

0

1



1

15

4

0

0

4

2 15  4 15 4

Third and final iteration: X1 = 0 kg, X2 = 20 kg, cost = $300 M7-29. X1 = number of mattresses X2 = number of box springs Minimize cost = 20X1 + 24X2 subject to X1 + X2  30 X1 + 2X3  40 X1, X2  0 M7­15

Copyright ©2015 Pearson, Inc.

M A1 1

2

–2 15

2

– 2M

3M –

15

M A2 0

Quantity 15

1 M

20 225 + 20M

0

2

M A1 0

M A2

–1

1

0 M

1

4

2 15 4 15

M–

Quantity 20 10 $300 4

Initial tableau: Cj   M M

Solution Mix A1 A2 Zj Cj – Z j Second tableau: Cj   M

Solution Mix A1

$24

X2

$20 $24 X1 X2 1 1 1 2 2M 3M –2M + 20 –3M + 24 $20 X1 1 1

Zj

1

Cj – Z j

 12

2

$0 S1 –1 0 –M M

$0 S1 –1

1

0

24

–M

0

M

2

$24 X2 0

2

M + 12 M + 12

$0 S2 0 –1 –M M $0 S2

1



2

1

2

M A2 0 1 M 0

M A1 1

1



M A1 1 0 M 0

2 1 2

M A2 

0

M – 12 M + 12

1

1

0

 12

0

3

2

2

Quantity 30 40 70M

Quantity 10 20

2

M + 12

10M + 480

M – 12

Final tableau: Cj   $20 $24

Solution $20 Mix X1 X1 1 X2 0 Zj 20 Cj – Z j 0 X1 = 20, X2 = 10, cost = $640

$24 X2 0 1 24 0

$0 S1 –2 1 –16 16

$0 S2 1 –1 –4 4

M A1 2 –1 16 M – 16

M A2 –1 1 4 M–4

Quantity 20 10 $640

M7-30. Maximize profit = 9X1 + 12X2 subject to X1 + X2  10 X1 + 2X2  12 X1, X2  0 Initial tableau: Cj   $0 $0

Solution Mix S1 S2 Zj Cj – Z j

$9 X1 1 1 0 9

$12 X2 1 2 0 12

M7­16

$0 S1 1 0 0 0

Copyright ©2015 Pearson, Inc.

$0 S2 0 1 0 0

Quantity 10 12 $0

Second tableau: Cj   $0

Solution Mix S1

$12

X2

$9 X1

$12 X2 0

$0 S1 1

1

0

1

6 3

12 0

0 0

6 –6

Solution $9 Mix X1 X1 1 X2 0 Zj 9 Cj – Z j 0 X1 = 8, X2 = 2, profit = $96

$12 X2 0 1 12 0

$0 S1 2 –1 6 –6

$0 S2 –1 1 3 –3

1 1

Zj Cj – Z j

2 2

$0 S2 

1

Quantity 4

2

6

2

$72

Final tableau: Cj   $4 $12

Quantity 8 2 $96

M7-31. Maximize profit = 8X1 + 6X2 + 14X3 subject to 2X1 + X2 + 3X3  120 2X1 + 6X2 + 4X3 = 240 X1, X2  0 Initial tableau: Cj   0 –M

Solution Mix S1 A2 Zj Cj – Z j Second tableau: Cj   $0 $6

$8 X1 2 2 –2M 8 + 2M

$6 X2 1 6 –6M 6 + 6M

Solution Mix S1

$8 X1

$6 X2 0

X2

1

Zj Cj – Z j

2 6

5

3 3

$14 X3 3 4 –4M 14 + 4M $14 X3 7

3

1

2

6 0

4 10

M7­17

3

Copyright ©2015 Pearson, Inc.

0 S1 1 0 0 0 0 S1 1 0 0 0

M A1 0 1 –M 0

Quantity 120 240 –240M

M A1 

1

1

6

6

1 –M – 1

Quantity 80 40 $240

Final tableau: Cj   $14

Solution Mix X3

$6

X2 Zj Cj – Z j X 1  0, X 2 

$8 X1 5

7  17 64 7

–1.1

$6 X2 0

$14 X3 1

1

0

6

14

0

0

0 S1

M A1

3



7  27 30 7 30  7

3



(which is X1 = 0, X2 = 17.14, X3 = 34.29, profit = $582.86) M7-32. a. X1 = number of deluxe one-bedroom units converted X2 = number of regular one-bedroom units converted X3 = number of deluxe studios converted X4 = number of efficiencies converted Objective: maximum profit = 8,000X1 + 6,000X2 + 5,000X3 + 3,500X4 subject to 1,100X1 + 1,000X2 + 600X3

+ 500X4  $35,000

700X1

+ 300X4  $28,000

+ 600X2

+ 400X3

2,000X1 + 1,600X2 + 1,200X3 + 900X4  $45,000 1,000X1 + 400X2

+ 900X3

+ 200X4  $19,000

X1 + X2

+ X3

+ X4

 50

X1 + X2

+ X3

+ X4

 25

X1  X 2  0.40( X1  X 2  X 3  X 4 )  

X1  X 2  0.70( X1  X 2  X 3  X 4 )  The last two constraints can be rewritten as: 0.6X1 + 0.6X2 – 0.4X3 – 0.4X4  0 0.3X1 + 0.3X2 – 0.7X3 – 0.7X4  0

M7­18

Copyright ©2015 Pearson, Inc.

14 2 7 2

–M –

120 240 , X3  , profit  $582 6 7 7 7

Quantity

1 14

240

7

120

7 $582 6 7

7

b. Maximize profit = 8,000X1 + 6,000X2 + 5,000X3 + 3,500X4 + 0S1 + 0S2 + 0S3 + 0S4 + 0S5 + 0S6 + 0S7 + 0S8 – MA1 – MA2 subject to 1,100X1 + 1,000X2 + 600X3

+ 500X4 + S1

= 35,000

700X1

+ 300X4 + S2

= 28,000

2,000X1 + 1,600X2 + 1,200X3 + 900X4 + S3

= 45,000

1,000X1 + 400X2

+ 600X2

+ 400X3 + 900X3

+ 200X4 + S4

= 19,000

X1 + X2

+ X3

+ X4

+ S5

= 50

X1 + X2

+ X3

+ X4

– S6 + A1 = 25

0.6X1 + 0.6X2 – 0.4X3 – 0.4X4 – S7 + A2

=0

0.3X1 + 0.3X2 – 0.7X3 – 0.7X4 + S8

=0

M7-33. a. The initial formulation is minimize cost = $12X1 + 18X2 + 10X3 + 20X4 + 7X5 + 8X6 subject to X1

– 3X3

= 100  900

25X2 + X3 + 2X4 + 8X5 2X1 +

X2

+ X6  250

+ 4X4

18X1 – 15X2 – 2X3 – X4 + 15X5

 150

25X6  300  70

2X4 + 6X5

b. Variable X5 will enter the basis next. (Its Cj – Zj value indicates the most improvement, that is, 7 – 21M ) Variable A3 will leave the basis because its ratio (150/15) is the smallest of the three positive ratios. M7-34. a. We change $10 (the Cj coefficient for X1) to $10 +  and note the effect on the Cj – Zj row in the table below. Simplex table for Problem M7-34 Cj   $10 +  $0

Solution $10 +  $30 $0 Mix X1 X2 S1 X1 1 4 2 S2 0 6 –7 Zj 10 +  40 + 4 20 + 2 Cj – Z j 0 –10 – 4 –20 – 2 From the X2 column, we require for optimality that –10 – 4  0

or



2 1 2 M7­19

Copyright ©2015 Pearson, Inc.

$0 S2 0 1 0 0

Quantity 160 200 $1,600 + 160

From the S1 column, we require that –20 – 2  0 Since the   $

2 1 2

7 12

or

  –10

is more binding, the range of optimality is

 Cj (for X1)  

b. The range of insignificance is –  Cj (for X2)  $40 c. One more unit of the first scarce resource is worth $20, which is the shadow price in the S1 column. d. Another unit of the second resource is worth $0 because there are still 200 unused units (S2 = 200). e. This change is within the range of insignificance, so the optimal solution would not change. If the 30 in the Cj row were changed to 35, the Cj – Zj would still be positive, and the current solution would still be optimal. f. The solution mix variables and their values would not change, because $12 is within the range of optimality found in part a. The profit would increase by 160(2) = 320, so the new maximum profit would be 1,600 + 320 = 1,920. g. The right-hand side could be decreased by 200 (the amount of the slack) and the profit would not change. M7-35. a. The shadow prices are: 3.75 for constraint 1; 22.5 for constraint 2; and 0 for constraint 3. The shadow price is 0 for constraint 3 because there is slack for this constraint. This means there are units of this resource that are available but are not being utilized. Therefore, additional units of this could not increase profits. b. Dividing the RHS values by the coefficients in the S1 column, we have 37.5/0.125 = 300 so we can reduce the right-hand-side by 300 units; and 12.5/(–0.125) = –100, so we can increase the right-hand-side by 100 units and the same variables will remain in the solution mix. c. The right-hand-side of this constraint could be decreased by 10 units. The solution mix variable in this row is slack variable S3. Thus, the right-hand-side can be decreased by this amount without changing the solution mix. M7-36. a. Produce 18 of model 102 and 4 of model H23. b. S1 represents unused or slack time on the soldering machine; S2 represents unused or slack time in the inspection department. c. Yes—the shadow price of the soldering machine time is $4. Clapper will net $1.50 for every additional hour he rents. d. No—the profit added for each additional hour of inspection time made available is only $1. Since this shadow price is less than the $1.75 per hour cost, Clapper will lower his profit by hiring the part-timer. M7­20

Copyright ©2015 Pearson, Inc.

M7-37. a. The first shadow price (in the S1 column) is $5.00. The second shadow price (in the S2 column) is $15.00. b. The first shadow price represents the value of one more hour in the painting department. The second represents the value of one additional hour in the carpentry department. c. The range of optimality for tables (X1) is established from Table M7-37c. –5 – 3/2  0 or

  –3.333 from S1 column

–15 + 1/2  0 or

  30 from S2 column

Hence the Cj for X1 must decrease by at least $3.33 to change the optimal solution. It must increase by $30 to alter the basis. The range of optimality is $66.67  Cj  $100.00 for X1. d. The range of optimality for X2. See Table M7-37d. –5 + 2  0 or

  2.5 from S1 column

–15 –   0 or

  –5 from S2 column

The range of optimality for profit coefficient on chairs is from $35 (= 50 – 15) to $52.50 (= 50 + 2.5). e. Ranging for first resource—painting department Quantity 30

S1 3

Ratio 20

2

40 –2 –20 Thus the first resource can be reduced by 20 hours or increased by 20 hours without affecting the solution. The range is from 80 to 120 hours. f. Ranging for second resource—carpentry time. Quantity 30

S2  12

Ratio –60

40 1 40 Range is thus from 200 hours to 300 hours (or 240 – 40 to 240 + 60). Table for Problem M7-37c Cj   70 +  50

Solution Mix X1

70 +  X1 1

50 X2 0

X2 Zj

0 70 + 

1 50

Cj – Z j

0

0

0 S1 2

 12

–2

1

3

5+ –5 –

M7­21

0 S2

3

2

3

2



15 –



–15 +

Copyright ©2015 Pearson, Inc.

1

2 1

Quantity 30

 2



40 $4,100 + 30

Table for Problem M7-37d Cj   70 50 + 

Solution Mix X1

70 X1 1

50 +  X2 0

X2 Zj Cj – Z j

0 70 0

1 50 +  0

0 S1 3

2

–2 5 – 2 –5 + 2

0 S2 

1

2

1 15 +  –15 – 

Quantity 30 40 $4,100 + 40

M7-38. Note that artificial variables may be omitted from the sensitivity analysis since they have no physical meaning. a. Range of optimality for X1 (phosphate): Solution $6 $0 $0 Cj  $5 +  Mix X1 X2 S1 S2  Quantity $0 S2 0 0 –1 1 550 X1 1 0 1 0 300 $5 +  $6 X2 0 1 –1 0 700 Zj 6 0 5+ –1 +  $5,700 + 300 Cj – Z j 0 0 0 1– 1 –   0 or   1 If the Cj value for X1 increases by $1, the basis will change. Hence –  Cj (for X1)  $6. Range of optimality for X2 (potassium): Cj   0 5 6+

Solution 5 0 0 6+ Mix X1 X2 S1 S2 Quantity S2 0 0 –1 1 550 X1 1 0 1 0 300 X2 0 1 –1 0 700 Zj 5 0 6+ –1 –  $5,700 + 700 Cj – Z j 0 0 0 1+ 1 +   0 or   –1 If the Cj value for X2 decreases by $1, the basis will change. The range is thus $5  Cj (for X2)  . b. This involves right-hand-side ranging on the slack variables S1 (which represents number of pounds of phosphate under the 300-pound limit). Quantity S2 Ratio 550 –1 –550 300 1 300 700 –1 –700 This indicates that the limit may be reduced by 300 pounds (down to zero pounds) without changing the solution. The question asks if the resources can be increased to 400 pounds without affecting the basis. The smallest negative ratio (–550) tells us that the limit can be raised to 850 pounds without changing the solution mix. However, the values of X1, X2, and S2 would change. X1 would now be M7­22

Copyright ©2015 Pearson, Inc.

400, X2 would be 600, and S2 would be 450. M7-39. Minimize cost = 4U1 + 8U2 subject to 1U1 + 2U2  80 3U1 + 5U2  75 U1, U2  0 The dual of the dual is the original primal. M7-40. Maximize profit = 50U1 + 4U2 subject to 12U1 + 1U2  120 20U1 + 3U2  250 U1, U2  0 M7-41. U1 = $80, U2 = $40, cost = $1,000 M7-42. Primal objective function: maximize profit = 0.5X1 + 0.4X2 primal constraints: 2X1 + 1X2  120 2X1 + 3X2  240 X1, X2  0 primal solution: X1 = 30, X2 = 60, profit = $39 M7-43. Maximize profit = 10X1 +5X2 + 31X3 subject to

+ 28X4 + 17X5 + 12X5  28

X1 + X2

 53

2X2 –2X3 X2 X1

+ 5X4 + 2X5 + 5X3

– X5

X1, X2, X3, X4, X5

 70  18 0

M7-44. a. Machine 3, as represented by slack variable S3, still has 62 hours of unused time. b. There is no unused time when the optimal solution is reached. All three slack variables have been removed from the basis and have zero values. c. The shadow price of the third machine is the value of the dual variable in column 6. Hence an extra hour of time on machine 3 is worth $0.265. d.  For each extra hour of time made available at no cost on machine 2, profit will  increase by $0.786 (the dual price/value or shadow price). Thus 10 hours of time will  be worth $7.86.

M7­23

Copyright ©2015 Pearson, Inc.

M7-45. The dual is maximize Z = 120U1 + 115U2 + 116U3 subject to 8U1 + 4U2 + 9U3  23 4U1 + 6U2 + 4U3  18 U1, U2, U3  0 U1 = $2.07 is the price of each test 1 U2 = $1.63 is the price of each test 2 U3 = $0 is the price of each test 3 Using the dual objective function: Z = 120U1 + 115U2 + 116U3 = 120(2.07) + 115(1.63) + 116(0) = $248.4 + $187.45 + $0 = $435.85 Thus $435.85 is the maximum the laboratory should be willing to pay an outside resource to conduct the 120 test 1’s, 115 test 2’s, and 116 test 3’s per day. 8U1 + 4U2 + 9U3 is the value of 8, 4, and 9 of tests 1, 2, and 3, respectively, performed per hour by a biochemist. This means that the prices U1, U2, and U3 need to be such that their total value does not exceed the cost per hour to the lab for using one of its own biochemists. Similarly, 4U1 + 6U2 + 4U3 is the value of 4, 6, and 4 of tests 1, 2, and 3, respectively, performed per hour by a biophysicist. Again, the prices U1, U2, and U3 need to be such that the total value does not exceed the cost per hour for the lab to use one of its own biophysicists. M7-46. a. There are 8 variables (2 decision variables, 3 surplus variables, and 3 artificial variables) and 3 constraints. b. The dual would have 2 constraints and 5 variables (3 decision variables and 2 slack variables). c. The dual problem would be smaller and easier to solve. M7-47. a. Rounded to two decimals, the solution is X1 = 27.38 tables, X2 = 37.18 chairs daily, profit = $3775.60. b. Not all resources are used. Shadow prices indicate that carpentry hours and painting hours are not fully used. Also, the 40-table maximum is not reached. c. The shadow prices relate to the five constraints: $0 value to making more carpentry and painting time available; $63.38 is the value of additional inspection/rework hours; $1.20 is the value of each additional foot of lumber made available. d. More lumber should be purchased if it costs less than the $1.20 shadow price. More carpenters are not needed at any price. e. Flair has a slack (X4) of 8.056 hours available daily in the painting department. It can spare this amount. f. Carpentry hours range: 221 to infinity. Painting hours range: 92 to infinity. Inspection/rework hours range:

19 1 2

to 41.

M7­24

Copyright ©2015 Pearson, Inc.

g. Table profit range: $41.67 to $160 Chair profit range: $21.87 to $84. M7-48. Printout 1 illustrates the model formulation. a. Printout 2 provides the optimal solution of $9,683. Only the first product (A158) is not produced. b. Printout 2 also lists the shadow prices. The first, for example, deals with steel alloy. The value of one more pound is $2.71. c. There is no value to adding more workers, since all 1,000 hours are not yet consumed. d. Two tons of steel at a total cost of $8,000 implies a cost per pound of $2.00. It should be purchased since the shadow price is $2.71. e. Printout 3 illustrates that profit declines to $8,866 with the change to $8.88. f. Printout 4 shows the new constraints. Profit drops to $9,380, and none of the A-E products remain. Previously, only A158 was not produced.

M7­25

Copyright ©2015 Pearson, Inc.

M7­26

Copyright ©2015 Pearson, Inc.

M7­27

Copyright ©2015 Pearson, Inc.

M7­28

Copyright ©2015 Pearson, Inc.