4.1 (P130) P1. Giapetto Problem Example 1 of Chapter3
LP of Giapetto’s Woodcarving ProblemFrom 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 PointX2,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 / RHSZ / 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 / RHSZ
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 / RHSZ
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 / RHSZ
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 / RHSZ / 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 / RHSZ / 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 / RHSZ / -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 / RHSZ / -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