4.1 (P130) P1. Giapetto Problem Example 1 of Chapter3

LP of Giapetto’s Woodcarving Problem
From page 52
Max Z = 3X1+2X2
s.t.
2X1+X2≤100 (C1)
X1+X2≤80 (C2)
X1≤40 (C3)
X1,X2≥0 (C4&C5) / Standard Form
Max Z = 3X1+2X2
s.t.
2X1+X2+X3=100
X1+X2+X4=80
X1+X5=40
X1, X2, X3,X4,X5≥0

4.4 (P139) P1. Feasible Region for Giapetto Problem

The feasible region for LP is the shaded region bounded by quadrilateral BCDFG. The extreme points are B=(0,80), C=(0,0), D=(40,0), F=(40,20), and G=(20,60).

Correspondence between Basic Feasible Solution and Corner Points

Basic Variables / Nonbasic Variable / Basic Feasible Solution / Corresponds to Corner Point
X2,X4,X5
X2,X3,X5
X3,X4,X5
X3,X4,X5
X3,X4,X5
X3,X4,X5
X3,X4,X5
X3,X4,X5
X3,X4,X5 / X1,X3
X1,X4
X1,X2
X1,X2
X1,X2
X1,X2
X1,X2
X1,X2
X1,X2 / X1=X3=0, X2=100, X4=-20, X5=40
X1=X4=0, X2=80, X3=20, X5=40
X1=X2=0, X3=100, X4=80, X5=40
X2=X5=0, X1=40, X3=20, X4=40
X2=X3=0, X1=50, X4=30, X5=-10
X3=X5=0, X1=40, X2=20, X4=20
X3=X4=0, X1=20, X2=60, X5=20
X2=X4=0, X1=80, X3=-60, X5=-40
X4=X5=0, X1=40, X2=40, X3=-20 / A, not a bfs because X4<0
B
C
D
E, not a bfs because X5<0
F
G
H, not a bfs because X3,X5<0
I, not a bfs because X3<0

Table above shows that the basic feasible solutions to the standard form of the LP are the LP’s extreme points.

4.5 (P149) P1. 3. Use Simplex Algorithm to solve

Tableau

X1 / X2 / X3 / X4 / X5 / RHS
Z / 3 / 2 / 0 / 0 / 0 / 0
Row 1 / 2 / 1 / 1 / 0 / 0 / 100
Row 2 / 1 / 1 / 0 / 1 / 0 / 80
Row 3 / 1 / 0 / 0 / 0 / 1 / 40
N
0 / N
0 / B
100 / B
80 / B
40 / (0)=(0,0)
1
2 / 1
0 / 0
1 / -2
-1 / -1
-1 / -1
0 / .1=3>0
.2=2>0

Since Z = 3X1+2X2 , increase X1 would be beneficial. Let X1 enter the basis.

1 = Min{100/2=50,80/1=80,40/1=40} = 40, so X5 will leave the basis.

Iteration 1

X1 / X2 / X3 / X4 / X5 / RHS
Z
Row 1
Row 2
Row 3 / 0
0
0
1 / -2
1
1
0 / 0
1
0
0 / 0
0
1
0 / -3
-2
-1
1 / 120
20
40
40
bfs
(1) / B
40 / N
0 / B
20 / B
40 / N
0 / (1)=(40,0)
1
2 / 0
-1 / 1
0 / -1
2 / -1
1 / 0
1 / .1=2>0
.2=-3<0

Since Z = 120 + 2X2 - 3X5 , increase X2 would be beneficial. Let X2 enter the basis.

2 = Min{20/1=20,40/1=40} = 20, so X3 will leave the basis.

Iteration 2

X1 / X2 / X3 / X4 / X5 / RHS
Z
Row 1
Row 2
Row 3 / 0
0
0
1 / 0
1
0
0 / -2
1
-1
0 / 0
0
1
0 / 1
-2
1
1 / 160
20
20
40
bfs
(2) / B
40 / B
20 / N
0 / B
20 / N
0 / (2)=(40,20)
1
2 / 0
-1 / -1
2 / 1
0 / 1
-1 / 0
1 / .1=-2<0
.2=1>0

Since Z = 160 - 2X3 + X5 , increase X5 would be beneficial. Let X5 enter the basis.

3 = Min{20/1=20,40/1=40} = 20, so X4 will leave the basis.

Iteration 3

X1 / X2 / X3 / X4 / X5 / RHS
Z
Row 1
Row 2
Row 3 / 0
0
0
1 / 0
1
0
0 / -1
-1
-1
1 / -1
2
1
-1 / 0
0
1
0 / 180
60
20
20
bfs
(3) / B
20 / B
60 / N
0 / N
0 / B
20 / (2)=(20,60)
1
2 / -1
1 / 1
-2 / 1
0 / 0
1 / 1
-1 / .1=-1<0
.2=-1<0
STOP

Now Z= 180 -X3 -X4, we cannot increaseX3 and X4 to get a better solution, so stop here.

An optimal solution is at (20,60) with the objective value of 180.

4.6 (P151) P3.

Tableau

Min / X1 / X2 / X3 / X4 / RHS
Z / 2 / -5 / 0 / 0 / 0
Row 1 / 3 / 8 / 1 / 0 / 12
Row 2 / 2 / 3 / 0 / 1 / 6
bfs (0) / N
0 / N
0 / B
12 / B
6 / (0)=(0,0)
1
2 / 1
0 / 0
1 / -3
-8 / -2
-3 / .1=2>0
.2=-5<0

Since Z = 2X1-5X2, increase X2 would be beneficial. Let X2 enter the basis.

1 = Min{12/8=1.5, 6/3 = 2} = 1.5, so X3 will leave the basis.

Iteration 1

Tableau

Min / X1 / X2 / X3 / X4 / RHS
Z / 31/8 / 0 / 5/8 / 0 / -7.5
Row 1 / 3/8 / 1 / 1/8 / 0 / 1.5
Row 2 / 7/8 / 0 / -3/8 / 1 / 1.5
bfs
(1) / N
0 / B
3/2 / N
0 / B
3/2 / (1)=(0,3/2)
1
2 / 1
0 / -3/8
-1/8 / 0
1 / -7/8
3/8 / .1=31/8>0
.2=5/8>0
STOP

Since Z = -7.5+31/8*X1 +5/8*X2, we cannot increase x1 and x3 to get a better solution, so stop here.

An optimal solution is at (0,3/2) with the objective value of -7.5.

4.8 (P158) P6.

Tableau

Min / X1 / X2 / X3 / X4 / RHS
Z / -1 / -3 / 0 / 0 / 0
Row 1 / 1 / -2 / 1 / 0 / 4
Row 2 / -1 / 1 / 0 / 1 / 3
bfs (0) / N
0 / N
0 / B
4 / B
3 / (0)=(0,0)
1
2 / 1
0 / 0
1 / -1
2 / 1
-1 / .1=-1<0
.2=-3<0

Since Z = -X1 -3X2, increase X2 would be beneficial. Let X2 enter the basis.

1 = Min{3/1=3} = 3, so X3 will leave the basis.

Iteration 1

X1 / X2 / X3 / X4 / RHS
Z / -4 / 0 / 0 / 3 / -9
Row 1 / -1 / 0 / 1 / 2 / 10
Row 2 / -1 / 1 / 0 / 1 / 3
bfs
(1) / N
0 / B
3 / B
10 / N
0 / (1)=(0,3)
1
2 / 1
0 / 1
-1 / 1
-2 / 0
1 / .1=-4<0
.2=3>0

Z= -9 - 4X1 + 3X4, so increase X1 would be beneficial. So we select X1 to enter the basis.

-X1 = 10 – X3– 2X4X1 = -10 + X3 + 2X4

-X1 = 3 – X2 - X4X1 = -3 + X2 + X4

The current basic variables are X2 and X3. As X1 is increased, both X2 and X3 increased.

This means that no matter how large we make X1, the inequalities X2≥0 and X3≥0 will still be true. Since there is no constraint that limits how large we can make the nonbasic variables, the solution is unbounded.

3.8(p94) P14

LINDO CODE:

MAX 29.49X11+29.49X12+29.49X13+29.49X14+29.49X15+29.49X16 + 31.43X21+31.43X22+31.43X23+31.43X24+31.43X25+31.43X26 – 12.75X11-12.75X12-12.75X13-12.75X14-12.75X15-12.75X16– 12.75X21-12.75X22-12.75X23-12.75X24-12.75X25-12.75X26

ST

! Demand Constraints

! Regular Gasoline

DC1) X11+X12+X13+X14+X15+X16>=9800

! Premium Gasoline

DC2) X21+X22+X23+X24+X25+X26>=30000

! Ration Constraints

! FCG in Regular Gasoline

RC1) 0.62X12-0.38X11-0.38X13-0.38X14-0.38X15-0.38X16<=0

!FCG in Premium Gasoline

RC2) -0.38X21+0.62X22-0.38X23-0.38X24-0.38X25-0.38X26 <=0

! Attribute Requirements

! RON in Regular Gasoline

AR1) 8.9X11+3.2X12-3.9X13+7X14+27X15+8X16>=0

! RON in Premium Gasoline

AR2) 2.9X21-2.8X22-9.9X23+X24+21X25+2X26>=0

! RVP in Regular Gasoline

AR3) -13.52X11-11.40X12+8.34X13-6.67X14-7.73X15+145.81X16=0

! RVP in Premium Gasoline

AR4) -13.52X21-11.40X22+8.34X23-6.67X24-7.73X25+145.81X26=0

! ASTM(70) in Regular Gasoline

AR5) -15X11+47X12+97X13-3X14+88X15+120X16>=0

! ASTM(70) in Premium Gasoline

AR6) -15X21+47X22+97X23-3X24+88X25+120X26>=0

! ASTM(130) in Regular Gasoline

AR7) -4X11+53X12+50X13+23X14+50X15+50X16>=0

! ASTM(130) in Premium Gasoline

AR8) -4X21+53X22+50X23+23X24+50X25+50X26>=0

! Input Availability Constraints

! Reformate

IA1) X11+X21<=15572

! FCG

IA2) X12+X22<=15434

! ISO

IA3) X13+X23<=6709

! POL

IA4) X14+X24<=1190

! MTB

IA5) X15+X25<=748

! Sign Constraints

SC1) X11>=0

SC2) X12>=0

SC3) X13>=0

SC4) X14>=0

SC5) X15>=0

SC6) X16>=0

SC7) X21>=0

SC8) X22>=0

SC9) X23>=0

SC10) X24>=0

SC11) X25>=0

SC12) X26>=0

END

OUTPUT FROM LINDO:

LP OPTIMUM FOUND AT STEP 18

OBJECTIVE FUNCTION VALUE

1) 765808.2

VARIABLE VALUE REDUCED COST

X11 0.000000 0.000000

X12 3724.000000 0.000000

X13 5564.473145 0.000000

X14 0.000000 0.000000

X15 511.527069 0.000000

X16 0.000000 0.000000

X21 15572.000000 0.000000

X22 11710.000000 0.000000

X23 1144.527100 0.000000

X24 1190.000000 0.000000

X25 236.472931 0.000000

X26 2360.930908 0.000000

ROW SLACK OR SURPLUS DUAL PRICES

DC1) 0.000000 -1.940000

DC2) 2213.930908 0.000000

RC1) 0.000000 0.000000

RC2) 531.293701 0.000000

AR1) 4026.586426 0.000000

AR2) 11917.775391 0.000000

AR3) 0.000000 0.128112

AR4) 0.000000 0.128112

AR5) 759796.250000 0.000000

AR6) 728360.437500 0.000000

AR7) 501172.000000 0.000000

AR8) 772808.562500 0.000000

IA1) 0.000000 20.412073

IA2) 0.000000 20.140476

IA3) 0.000000 17.611547

IA4) 0.000000 19.534506

IA5) 0.000000 19.670305

SC1) 0.000000 0.000000

SC2) 3724.000000 0.000000

SC3) 5564.473145 0.000000

SC4) 0.000000 0.000000

SC5) 511.527069 0.000000

SC6) 0.000000 0.000000

SC7) 15572.000000 0.000000

SC8) 11710.000000 0.000000

SC9) 1144.527100 0.000000

SC10) 1190.000000 0.000000

SC11) 236.472931 0.000000

SC12) 2360.930908 0.000000

NO. ITERATIONS= 18

3.8(p94) P14

LINGO CODE:

Model:

[COST] max = 29.49*(x11+x12+x13+x14+x15+x16) + 31.43*(x21+x22+x23+x24+x25+x26) - 12.75*(x11+x12+x13+x14+x15+x16) - 12.75*(x21+x22+x23+x24+x25+x26);

[DC1] X11+X12+X13+X14+X15+X16>=9800;

[DC2] X21+X22+X23+X24+X25+X26>=30000;

[RC1] 0.62*X12-0.38*X11-0.38*X13-0.38*X14-0.38*X15-0.38*X16<=0;

[RC2] -0.38*X21+0.62*X22-0.38*X23-0.38*X24-0.38*X25-0.38*X26 <=0;

[AR1] 8.9*X11+3.2*X12-3.9*X13+7*X14+27*X15+8*X16>=0;

[AR2] 2.9*X21-2.8*X22-9.9*X23+X24+21*X25+2*X26>=0;

[AR3] -13.52*X11-11.40*X12+8.34*X13-6.67*X14-7.73*X15+145.81*X16=0;

[AR4] -13.52*X21-11.40*X22+8.34*X23-6.67*X24-7.73*X25+145.81*X26=0;

[AR5] -15*X11+47*X12+97*X13-3*X14+88*X15+120*X16>=0;

[AR6] -15*X21+47*X22+97*X23-3*X24+88*X25+120*X26>=0;

[AR7] -4*X11+53*X12+50*X13+23*X14+50*X15+50*X16>=0;

[AR8] -4*X21+53*X22+50*X23+23*X24+50*X25+50*X26>=0;

[IA1] X11+X21<=15572;

[IA2] X12+X22<=15434;

[IA3] X13+X23<=6709;

[IA4] X14+X24<=1190;

[IA5] X15+X25<=748;

END

OUTPUT FROM LINGO:

Global optimal solution found.

Objective value: 765808.2

Total solver iterations: 12

Variable Value Reduced Cost

X11 0.000000 0.000000

X12 3724.000 0.000000

X13 5564.473 0.000000

X14 0.000000 0.000000

X15 511.5271 0.000000

X16 0.000000 0.000000

X21 15572.00 0.000000

X22 11710.00 0.000000

X23 1144.527 0.000000

X24 1190.000 0.000000

X25 236.4729 0.000000

X26 2360.931 0.000000

Row Slack or Surplus Dual Price

COST 765808.2 1.000000

DC1 0.000000 -1.940000

DC2 2213.931 0.000000

RC1 0.000000 0.000000

RC2 531.2937 0.000000

AR1 4026.586 0.000000

AR2 11917.78 0.000000

AR3 0.000000 0.1281119

AR4 0.000000 0.1281119

AR5 759796.3 0.000000

AR6 728360.4 0.000000

AR7 501172.0 0.000000

AR8 772808.5 0.000000

IA1 0.000000 20.41207

IA2 0.000000 20.14048

IA3 0.000000 17.61155

IA4 0.000000 19.53451

IA5 0.000000 19.67031

3.9(p97) P4.

LINDO CODE:

MAX 10X1 + 20X2 + 30X3 – 26R0 – X21 – 2X31 – 6X32

ST

! Balance Constraints

BC1) 3R0 –X1–X21 –X31=0

BC2) R0+X21–X2 –X32=0

BC3) X3–X31–X32=0

! Maximum Demand Constraints

! Product 1

DC1) X1<=5000

! Product 2

DC2) X2<=5000

! Product 3

DC3) X3<=3000

! Labor Constraint

LS1) 2R0+2X21+3X31+X32<=25000

! Sign Constraints

SC1) R0>=0

SC2) X1>=0

SC3) X2>=0

SC4) X3>=0

SC5) X21>=0

SC6) X31>=0

SC7) X32>=0

END

OUTPUT FROM LINDO:

LP OPTIMUM FOUND AT STEP 5

OBJECTIVE FUNCTION VALUE

1) 147750.0

VARIABLE VALUE REDUCED COST

X1 5000.000000 0.000000

X2 5000.000000 0.000000

X3 3000.000000 0.000000

R0 3250.000000 0.000000

X21 1750.000000 0.000000

X31 3000.000000 0.000000

X32 0.000000 5.000000

ROW SLACK OR SURPLUS DUAL PRICES

BC1) 0.000000 -6.250000

BC2) 0.000000 -7.250000

BC3) 0.000000 8.250000

DC1) 0.000000 3.750000

DC2) 0.000000 12.750000

DC3) 0.000000 21.750000

LS1) 6000.000000 0.000000

SC1) 3250.000000 0.000000

SC2) 5000.000000 0.000000

SC3) 5000.000000 0.000000

SC4) 3000.000000 0.000000

SC5) 1750.000000 0.000000

SC6) 3000.000000 0.000000

SC7) 0.000000 0.000000

NO. ITERATIONS= 5

3.9(p97) P4.

LINGO CODE:

MODEL:

SETS:

PROCESS;

PRODUCTS: DEMAND, SALES, REVENUE;

MANUFACTURE(PRODUCTS, PROCESS): COST, VOLUME;

ENDSETS

DATA:

PRODUCTS = 1 2 3;

PROCESS = 1 2;

REVENUE = 10 20 30;

COST = 0 0

1 0

2 6;

DEMAND = 5000 5000 3000;

LABOR = 25000;

ENDDATA

MAX = @SUM(PRODUCTS (I): REVENUE (I) * SALES(I)) - (26 * R) - @SUM(MANUFACTURE (I,J): COST (I,J) * VOLUME (I,J));

(3 * R) = SALES (1) + VOLUME (2,1) + VOLUME(3,1);

(R + VOLUME(2,1)) = SALES (2) + VOLUME (3,2);

SALES (3) = VOLUME (3,1) + VOLUME (3,2);

@FOR( PRODUCTS (I): SALES (I) <= DEMAND (I));

(2*R) + (2*VOLUME(2,1)) + (3*VOLUME(3,1))+ VOLUME(3,2) <= LABOR;

R >= 0;

@FOR ( PRODUCTS (I): SALES (I) >= 0);

VOLUME (2,1) >= 0;

VOLUME (3,1) >= 0;

VOLUME (3,2) >= 0;

END

OUTPUT FROM LINGO:

Global optimal solution found.

Objective value: 147750.0

Total solver iterations: 3

Variable Value Reduced Cost

LABOR 25000.00 0.000000

R 3250.000 0.000000

DEMAND( 1) 5000.000 0.000000

DEMAND( 2) 5000.000 0.000000

DEMAND( 3) 3000.000 0.000000

SALES( 1) 5000.000 0.000000

SALES( 2) 5000.000 0.000000

SALES( 3) 3000.000 0.000000

REVENUE( 1) 10.00000 0.000000

REVENUE( 2) 20.00000 0.000000

REVENUE( 3) 30.00000 0.000000

COST( 1, 1) 0.000000 0.000000

COST( 1, 2) 0.000000 0.000000

COST( 2, 1) 1.000000 0.000000

COST( 2, 2) 0.000000 0.000000

COST( 3, 1) 2.000000 0.000000

COST( 3, 2) 6.000000 0.000000

VOLUME( 1, 1) 0.000000 0.000000

VOLUME( 1, 2) 0.000000 0.000000

VOLUME( 2, 1) 1750.000 0.000000

VOLUME( 2, 2) 0.000000 0.000000

VOLUME( 3, 1) 3000.000 0.000000

VOLUME( 3, 2) 0.000000 5.000000

Row Slack or Surplus Dual Price

1 147750.0 1.000000

2 0.000000 -6.250000

3 0.000000 -7.250000

4 0.000000 8.250000

5 0.000000 3.750000

6 0.000000 12.75000

7 0.000000 21.75000

8 6000.000 0.000000

9 3250.000 0.000000

10 5000.000 0.000000

11 5000.000 0.000000

12 3000.000 0.000000

13 1750.000 0.000000

14 3000.000 0.000000

15 0.000000 0.000000

Chapter 5 Review (pp 254-261) P4.

a)Ruby cost change from $100 to $190

Obj coef. ranges for R:

Current coef. = -100Allowable increase = 100Allowable decrease = 100

This means as long as the cost of extra ruby is between $0 and $200 the current basis still optimal. Therefore Zales will still produce the same amount of type 1 and type 2 rings, and buy the same amount of extra rubies.

Zales still purchase rubies and have the same optimal solution.

However the objective value (profit) will change to 19000+15(100-190) = $17650.

b)Now X2>=23

RHS for X2

Current RHS = 25Allowable increase =0 Allowable decrease = 2.5

b = -2  the current basis remains optimal.

Dual price row 6 is -200

For Max problem: new opt z-value = old opt z-value + (constraint shadow price) b

New profit = 19000+(-200*-2) = $19400

c)To keep the same profit

Pay for extra labor hour = extra money made from extra labor = Dual price row 4 = $200

So Zales would be willing to pay for another hour is $200 at most.

d)Pay for another sapphire

Pay for extra sapphire = extra money made from extra sapphire = Dual price row 3 = $0

So Zales would not pay any money for another sapphire. Actually Zales has 10 units surplus amount of sapphire (slack row 3 = 10).

Chapter 5 Review (pp 254-261) P7

Unit of obj value is in thousand dollar

a) Coef of TM changes from $5 to 55-48=$7.

From fig 22

Obj coef ranges for TB

Current coef = 5 Allowable increase = infinity Allowable decrease = 4

Ranges are between 1 and infinity.

Since the change in TM coef is 2, the current basic is still optimal

and optimal solution is unchanged (SM = 45, TM = 0, SB = 5, TB = 50).

new opt z-value/profit = (32*45)+(55*0)+(5*5)+(7*50)=1815$1815000

b)Giapetto would be willing to pay

For extra 100 board feet of lumber = (dual price of row 2)/10 = 0 =$0

For extra 100 labor hours = (dual price of row 3)/10 = 13.50/10=1.35 = 1.35*1000 =$1350

c) if 60,000 labor available.

RHS for labor constraint changes from 90 to 60.

From fig 22

RHS ranges for row 3

Current RHS = 90 Allowable increase = 6.666667Allowable decrease = 90

Dual price = 13.5

Ranges are between 0 and 96.666667.

Since new RHS = 60 which is in the ranges, therefore current basis is still optimal,

For Max problem: new opt z-value = old opt z-value + (constraint shadow price) b

b = -30

new opt z-value/profit = 1715 + (13.5*-30) = 1310 $1310000

d) if 40,000 trains can be sold.

RHS for demand for train constraint changes from 50 to 40.

From fig 22

RHS ranges for row 5

Current RHS = 50 Allowable increase = infinityAllowable decrease = 50

Dual price = 5

Ranges are between 0 and infinity.

Since new RHS = 40 which is in the ranges, therefore current basis is still optimal,

For Max problem: new opt z-value = old opt z-value + (constraint shadow price) b

b = -10

new opt z-value/profit = 1715 + (5*-10) = 1665$1665000

Chapter 5 Review (pp 254-261) Problem 13

a) Coef of X11 changes from $140 to 200-70=$130.

From fig 23

Obj coef ranges for X11

Current coef = 140 Allowable increase = infinity Allowable decrease = 20

Ranges are between 120 and infinity.

Since the change in X11 coef is -10, the current basic is still optimal and optimal solution is unchanged (X11 = 10, X22 = 11.666670, X12=X13=X21=X23=L=0).

new opt z-value/profit = (130*10)+(120*0)+(40*0)+(70*0)+(80*11.66667)+(30*0)-(20*0)=$2233.3336

b) Coef of L changes from $20 to 4.

From fig 23

Obj coef ranges for L

Current coef = -20 Allowable increase = 19.73333Allowable decrease = infinity Ranges are between - infinity and -0.26667.

Since the change in L coef is -16, the current basic is still optimal and optimal solution is unchanged (X11 = 10, X22 = 11.666670, X12=X13=X21=X23=L=0). Not purchase

new opt z-value/profit = (140*10)+(120*0)+(40*0)+(70*0)+(80*11.66667)+(30*0)-(4*0)=$2333.33 (same profit)

c) RHS for row 2 change for +5, RHS is still in the ranges. The current basis is still optimal.

Company would be willing to pay

For extra capacity of 5000 tools = (dual price of row 2)*5 = 86.67*5=$433.35>$400

So company would love to take this offer.

d) If 5 more extra hour available.

RHS for labor constraint changes from 5500 to 5505

From fig 23

RHS ranges for row 4

Current RHS = 5500 Allowable increase = 100Allowable decrease = 3500

Dual price = .266667

Ranges are between 2000 and 5600

Since new RHS = 5505 which is in the ranges, therefore current basis is still optimal,

For Max problem: new opt z-value = old opt z-value + (constraint shadow price) b

b = +5

new opt z-value/profit = 2333.333 + (0.266667*5) = $2334.6664