MATH 3170 6.00 A SU 2013

Solutions to selected problems from Sections 6.1-6.3, 6.5-6.9

6.1.1

Typical isoprofit line is 3x1+c2x2=z. This has slope 3/c2.

If slope of isoprofit line is <2, then Point C is optimal. Thus if 3/c22 or c2<1.5 the current basis is no longer optimal.

Also if the slope of the isoprofit line is >1 Point A will be optimal. Thus if 3/c21 or c2>3 the current basis is no longer optimal. Thus for 1.5c23 the current basis remains optimal.

For c2 = 2.5 x1 = 20, x2 = 60, but z = 3(20) + 2.5(60) = $210.

6.1.2

Currently Number of Available Carpentry Hours = b2 = 80. If we reduce the number of available carpentry hours we see that when the carpentry constraint moves past the point (40,20) the carpentry and finishing hours constraints will be binding at a point where x1>40. In this situation, b2<40 + 20 = 60. Thus for b2<60 the current basis is no longer optimal. If we increase the number of available carpentry hours we see that when the carpentry constraint moves past (0,100) the carpentry and finishing hours constraints will both be binding at a point where x1<0. In this situation, b2>100.Thus, if b2>100 the current basis is no longer optimal. Therefore, the current basis remains optimal for 60b2100. If 60b2100, the number of soldiers and trains produced will change.

6.1.3

If b3, the demand for soldiers, is increased then the current basis remains feasible and therefore optimal. If, however, b3<20 then the point where the finishing and carpentry constraints are binding is no longer feasible(it has s3<0). Thus for b3>20 the current basis remains optimal. For b3>20 the point where the carpentry and finishing constraints are still binding remains at (20,60) so producing 20 soldiers and 60 trains remains optimal.

6.1.5

For this problem, please note that each Radio 2 requires 1
(not 2) Laborer-2 hour.

5a. Let c1 = profit from type 1 radio. Slope of isoprofit line is c1/2. Current basis is still optimal if of isoprofit line is steeper than L1 constraint and flatter than L2 constraint or2c1/2.5 or 1c14 or

$23 = 22 + 1Type 1 price22 + 4 = $26.

5b. Current basis remains optimal for 23/c2.5 or 1.5c26 or $21.50Type 2 price26.

5c.Optimal solution still occurs where both constraints are binding or x1 + 2x2 = 30 and 2x1 + x2 = 50. This yields x1 = 70/3, x2 = 10/3, and z = 230/3. Since solution is feasible, it is optimal.

5d. Optimal solution occurs where x1 + 2x2 = 40 and 2x1 + x2 = 60. This yields x1 = 80/3, x2 = 20/3, z = 280/3.

5e. If 40 + ∆ laborer 1 hour are available optimal solution is where x1 + 2x2 = 40 + ∆ and 2x1 + x2 = 50. This yields x1 = 20 ∆/3, x2 = 10 + 2∆/3, z = 80 + ∆/3. Thus laborer 1 shadow price = 1/3.

If 50 + ∆ laborer 2 hours are available optimal solution is where x1+ 2x2 = 40 and 2x1 + x2 = 50 + ∆. This yields x1 = 20 + ∆/3, x2 = 10 ∆/3, z = 80 + 4∆/3. Thus laborer 2 shadow price = 4/3.

6.2.1

BV = {x1,x2} B = B1 = cBV = [3 1]

cBVB1 = [4 5]

Coefficient of s1 in row 0 = 4

Coefficient of s2 in row 0 = 5

Righthand Side of row 0 = cBVB1b = [4 5] = 28

s1 column = B1 =

s2 column = B1 =

x1 column = x2 column =

Righthand Side of Constraints = B1b = =

Thus the optimal tableau is

Z + 4s1+ 5s2 = 28

x1 + s1 + s2 = 6

x2 + s1 + 2s2 = 10

6.2.2

BV = {x2,s1} B = B1 = cBV = [1 0]

cBVB1 = [1 0] = [0 1]

Coefficient of x1 in row 0 = cBVB1a1c1 = [0 1] +1=2

Coefficient of s2 in row 0 = cBVB1= 1

RHS of row 0 = cBVB1b = [0 1] = 2

Column for x1 = B1a1 = =

Column for s2 = B1 =

RHS of Optimal Tableau = B1b = =

Thus, optimal tableau is

z + 2x1+ s2 = 2

x1 + x2+ s2 = 2

x1+ s1s2 = 2.

6.3.2

If c1 = 55 then Δ = 5. Then

cBVB1 = [0 20 55] = [0 12.5 2.5]

cBVB1b = [0 12.5 2.5] = 270

Coefficient of x2 in row 0 = [0 12.5 2.5] 30 = 1.25.

Tableau for current optimal basis is now

z x1 x2 x3 s1 s2 s3 RHS

1 0 1.25 0 0 12.5 2.5 270

0 0 2 0 1 2 8 24

0 0 2 1 0 2 4 8

0 1 1.25 0 0 .5 1.5 2

After pivoting in x2 we obtain the new optimal solution z = 272, s1 = 27.2, x3 = 11.2, x2 = 1.6. Thus reduction in price of desks has resulted in no desks being manufactured.

6.3.3

Denote the RHS of first constraint by 48 + Δ.As long as

B1 the current basis remains optimal.

B1 =

Thus for Δ24 or b14824 = 24 the current basis remains optimal. If b1 = 30 the current basis is still optimal. Thus

= B1 =

and new optimal solution is s1 = 6, x3 = 8, x1 = 2. The new optimal zvalue may be obtained from

z = cBVB1b = [0 10 10] = 280

6.3.5

The coefficient of home computer tables in row 0 will be

[0 10 10] 36 = 4. Thus current solution remains optimal and no home computer tables will be made.

6.5.1

min w = y1 + 3y2 + 4y3

s.t. y1 + y2 + y32

y1 + y22y31

y1, y2, y30

6.5.2

max z = 4x1 + x2 + 3x3

s.t. 2x1 + x2 + x31

x1 + x2 + 2x31

x1, x2, x30

6.5.3

min w = 5y1 + 7y2 + 6y3 + 4y4

s.t. y1 + 2y2+ y44

y1 + y2 + 2y3= 1

y3 + y4 = 2

y1, y20, y30 y4 u.r.s.

6.5.4

max z = 6x1 + 8x2

s.t. x1 + x24

2x1x22

2x2 = 1

x10 x2 u.r.s.

6.5.5

The dual of the LP given in the problem is

min w = 6y1 + 5y2

s.t. 3y1 + 2y21

(1) y1 + y22

y10 y2 u.r.s.

When placed in normal form the LP given in the problem becomes

max z = x1 + 2x2

s.t. 3x1 + x26

(2) 2x1 + x25

2x1x25

x10 x20

From (16) and (17) we find that the dual of (2) may be written as

min w = 6y1 + 5y2'5y2''

s.t. 3y1 + 2y2'2y2''1

(3) y1 + y2' y2''2

y10, y2'0, y2''0

If we let y2 = y2'y2'' then y2 is u.r.s. and (3) is actually the same LP as (1). Thus an equality constraint in the primal does yield a urs variable in the dual.

6.5.6

The dual of the LP given in the problem is

min w = y1 + 2y2

s.t. y1 y23

(1) y1 + y21

y10 y20

When placed in normal form the primal given in the problem becomes

max z = 3x1 + x2

s.t. x1 + x21

(2) x1 x22

x10 x20

The dual of (2) may be written as

_

min w = y12y2

_

s.t. y1 + y23

_

(3) y1y21

_

y10 y20

_

If we define y2 = y2 we see that (1) and (3) are the same LP. _

Also, since y20, y20 will hold.

6.7.1

(a) min w = 100y1 + 80y2 + 40y3

s.t. 2y1 + y2 + y33

y1 + y22

y10 y20 y30

1b. and 1c. y1 = 1 y2 = 1 y3 = 0 w = 180. Observe that this solution has a wvalue that equals the optimal primal zvalue. Since this solution is dual feasible it must be optimal(by Lemma 2) for the dual.

6.7.2

(a) min w = 3y1 + 2y2 + y3

s.t. y1 + y32

y1 + y21

y1 + y2 + y31

y10 y20 y3 u.r.s.

y1 = Coefficient of s1 in optimal row 0 = 0

y2 = Coefficient of e2 in optimal row 0 = 1

y3 = Coefficient of a3 in optimal row 0M = 2

Optimal wvalue = 0

Again note that [0 1 2] is dual feasible and yields a dual objective function value equal to the optimal primal objective function value. Thus [0 1 2] must be the optimal solution to the dual.

6.7.3

The dual objective function is w = .5y1 + .5y2. The optimal dual solution is y1 = 0.4 y2 = 1.4 w = .5(0.4)+ .5(1.4) = 0.9. Thus rhs of optimal primal tableau's row 0 must be 0.9.

6.7.4

The dual is

max z = 4x1 + 20x2 + 10x3

s.t. x1/2 + x2 + x32

x1/4 + 3x2 + x33

x1, x2, x30

The optimal solution to the dual is x1 = 0, x2 = 1/2,x3 = 3/2, z = 4(0) + 20(1/2) + 10(3/2) = 25 cents.

6.8.2

(a) Shadow Price for Sugar Const. = 4 Shadow Price for Chocolate Const. = 1. If 1 extra ounce of sugar were available profits would increase by $4. If 1 extra ounce of chocolate were available profits would increase by $1. Without further information however we cannot determine how much we would pay for an additional ounce of chocolate or sugar.

(b) From Section 6.3 current basis remains optimal if 100/3Available Sugar100. Here Δb1 = 6050 = 10 so

New zvalue = [old zvalue] + 10(4) = 340 cents

(c) Δb1 = 10 Thus [New zvalue] = 30010(4) = 260 cents.

(d) Since current basis is no longer optimal we cannot answer this question without resolving the problem.

6.8.3

Increasing the rhs of a  constraint eliminates points from the feasible region. Thus in a min problem the optimal zvalue will increase or remain the same.

6.8.4

Increasing the rhs of a  constraint adds points to the feasible region. Thus in a min problem the optimal zvalue will decrease or stay the same.

6.8.5

(a) Since labor and raw materials have already been purchased, all we need do is maximize revenue.

(b) Skilled labor Shadow Price = 0

Unskilled Labor Shadow Price = 0

Raw Material Shadow Price = 15

Product 2 Const. Shadow Price = 5

We would be willing to pay $0 for an additional hour of either type of labor. We would pay up to $15 for an extra unit of raw material. Reducing the Product 2 marketing requirement by 1 unit will raise revenues by $5.

(c) Δb3 = 5 so New zvalue = 435 + 5(15) = $510

(d) Since shadow price of skilled labor const. is 0, optimal z value remains unchanged.

(e) For a 5 unit requirement Δb4 = 2. Thus New z value = 435 + 2(5) = $425. For a 2 unit requirement Δb4 = 1. Thus New zvalue = 435 + (1)(5) = $440.

6.8.6

Contribution of Product 1 to Profit = 153(3)2(2)1(1) = $1

Contribution of Product 2 to Profit = 254(3)3(2)2(1)=$5

Thus, firm wishes to maximize z = x1 + 5x2.

(a) If purchased at the given price of $1 an extra unit of raw material increases profits by $2.5. Thus the firm would be willing to pay up to 1 + 2.5 = $3.50 for an extra unit of raw material.

(b) Both the skilled and unskilled labor shadow prices are 0. Also both labor constraints are nonbinding. All we can say is that we are not willing to pay $3 for another hour of skilled labor and are not willing to pay $2 for another hour of unskilled labor. We might, however, pay <$3 for another hour of skilled labor and <$2 for another hour of unskilled labor.

6.9.1

Dual constraint for computer tables is 6y1 + 2y2 + y335. Since

[0 10 10] does not satisfy this constraint the current basis is no longer optimal. Another way of seeing it:a computer table uses $20 worth of finishing time and $10 worth of carpentry time. Since a computer table sells for $35 it pays to make computer tables and the current basis is no longer optimal.

6.9.2

(a) Dual constraint for x1 is y1 + 2y2c1. Since y1 = 4 and y2 = 1 the current basis is still optimal if 6c1.

(b) Dual constraint for Type 1 Candy Bar is now y1/2 + 3y2/43.Since y1 = 4 y2 = 1 does not satisfy this constraint, the current basis is no longer optimal.

(c) The dual constraint for a Type 4 Candy Bar is 2y1 + y210. Since y1 = 4 y2 = 1 does not satisfy this constraint, the current basis is no longer optimal. The new optimal solution would make Type 4 Candy Bars.

6.9.3

Since desks are a basic variable we have changed BV and cBVB1. Thus y1 = 0 y2 = y3 = 10 is no longer the optimal dual solution, and any calculations that assume that cBVB1 = [0 10 10] will be incorrect.