modeling discrete optimization
coolangel
HW2_Solution.pdf
Answer to Math-4410 HW#2 questions
1. The Diet Problem
LINGO model:
MODEL:
SETS:
FOODS/ BREAD, MEAT, VEGGIES/
:CALORIES, COST, VITAMINS, QUANTITY;
ENDSETS
DATA:
CALORIES= 24, 32, 16;
COST= 2, 3, 2;
VITAMINS= 8, 20, 12;
CALORIE_UPPER = 450;
CALORIE_LOWER = 200;
VITAMIN_LOWER = 100;
ENDDATA
!Objective function;
MIN= @SUM(FOODS: QUANTITY*COST);
@SUM(FOODS: QUANTITY*CALORIES) <= CALORIE_UPPER; !Upper limit of calories;
@SUM(FOODS: QUANTITY*CALORIES) >= CALORIE_LOWER; !Lower limit of calories;
@SUM(FOODS: QUANTITY*VITAMINS) >= VITAMIN_LOWER; !Lower limit of vitamins;
END
Global optimal solution found.
Objective value: 17.85714
Infeasibilities: 0.000000
Total solver iterations: 2
Variable Value Reduced Cost
CALORIE_UPPER 450.0000 0.000000
CALORIE_LOWER 200.0000 0.000000
VITAMIN_LOWER 100.0000 0.000000
CALORIES( BREAD) 24.00000 0.000000
CALORIES( MEAT) 32.00000 0.000000
CALORIES( VEGGIES) 16.00000 0.000000
COST( BREAD) 2.000000 0.000000
COST( MEAT) 3.000000 0.000000
COST( VEGGIES) 2.000000 0.000000
VITAMINS( BREAD) 8.000000 0.000000
VITAMINS( MEAT) 20.00000 0.000000
VITAMINS( VEGGIES) 12.00000 0.000000
QUANTITY( BREAD) 3.571429 0.000000
QUANTITY( MEAT) 3.571429 0.000000
QUANTITY( VEGGIES) 0.000000 0.4285714
Row Slack or Surplus Dual Price
OBJ 17.85714 -1.000000
2 250.0000 0.000000
3 0.000000 -0.7142857E-01
4 0.000000 -0.3571429E-01
Ranges in which the basis is unchanged:
Objective Coefficient Ranges
Current Allowable Allowable
Variable Coefficient Increase Decrease
QUANTITY( BREAD) 2.000000 0.2500000 0.8000000
QUANTITY( MEAT) 3.000000 0.6000000 0.3333333
QUANTITY( VEGGIES) 2.000000 INFINITY 0.4285714
Righthand Side Ranges
Row Current Allowable Allowable
RHS Increase Decrease
2 450.0000 INFINITY 250.0000
3 200.0000 100.0000 40.00000
4 100.0000 25.00000 33.33333
2. The following math model can be converted to LINGO:
LINGO Model:
Model:
SETS:
PARTS : OUTCOST, INCOST, BUY, PRODUCE, CUTTIME, SHAPETIME, FABTIME;
!OUTCOST=Cost to buy part.
INCOST=Cost to produce part.
BUY=# of the part to be purchased.
PRODUCE=# of the part to be produced in-house.
CUTTIME=The # of hours required to cut the part.
SHAPETIME=The # of hours required to shape the part.
FABTIME=The # of hours required to fabricate the part.;
DEPTS : CAPACITY;
!CAPACITY=The capacity of the department in hours.;
ENDSETS
DATA:
PARTS= SHAFT, BASE, CAGE;
OUTCOST= 1.21 2.50 1.95;
INCOST= 0.81, 2.30, 1.45;
CUTTIME= 0.04, 0.08, 0.07;
SHAPETIME=0.06, 0.02, 0.09;
FABTIME= 0.04, 0.05, 0.06;
DEPTS= CUTTING, SHAPING, FABRICATION;
CAPACITY= 820, 820, 820;
ENDDATA
MIN = @SUM(PARTS(I): OUTCOST(I)*BUY(I)+INCOST(I)*PRODUCE(I));
!Minimizing costs=sum of buying costs and production costs;
@FOR(PARTS(I):BUY(I)+PRODUCE(I)=6100);
!Sum of amount bought+amount produced of each part has to equal 6100;
@SUM(PARTS(I):CUTTIME(I)*PRODUCE(I))<=820;
@SUM(PARTS(I):SHAPETIME(I)*PRODUCE(I))<=820;
@SUM(PARTS(I):FABTIME(I)*PRODUCE(I))<=820;
!Sum of times has to be less than the total hour capacity of the department
that does that job.;
@FOR(PARTS(I):@GIN(BUY(I)));
FOR(PARTS(I):@GIN(PRODUCE(I)));
END
Global optimal solution found.
Objective value: 29256.40
Objective bound: 29256.40
Infeasibilities: 0.000000
Extended solver steps: 0
Total solver iterations: 3
Variable Value Reduced Cost
OUTCOST( SHAFT) 1.210000 0.000000
OUTCOST( BASE) 2.500000 0.000000
OUTCOST( CAGE) 1.950000 0.000000
INCOST( SHAFT) 0.8100000 0.000000
INCOST( BASE) 2.300000 0.000000
INCOST( CAGE) 1.450000 0.000000
BUY( SHAFT) 0.000000 1.210000
BUY( BASE) 2642.000 2.500000
BUY( CAGE) 1824.000 1.950000
PRODUCE( SHAFT) 6100.000 0.8100000
PRODUCE( BASE) 3458.000 2.300000
PRODUCE( CAGE) 4276.000 1.450000
CUTTIME( SHAFT) 0.4000000E-01 0.000000
CUTTIME( BASE) 0.8000000E-01 0.000000
CUTTIME( CAGE) 0.7000000E-01 0.000000
SHAPETIME( SHAFT) 0.6000000E-01 0.000000
SHAPETIME( BASE) 0.2000000E-01 0.000000
SHAPETIME( CAGE) 0.9000000E-01 0.000000
FABTIME( SHAFT) 0.4000000E-01 0.000000
FABTIME( BASE) 0.5000000E-01 0.000000
FABTIME( CAGE) 0.6000000E-01 0.000000
CAPACITY( CUTTING) 820.0000 0.000000
CAPACITY( SHAPING) 820.0000 0.000000
CAPACITY( FABRICATION) 820.0000 0.000000
Row Slack or Surplus Dual Price
1 29256.40 -1.000000
2 0.000000 0.000000
3 0.000000 0.000000
4 0.000000 0.000000
5 0.4000000E-01 0.000000
6 0.000000 0.000000
7 146.5400 0.000000
3. The following math model can be converted to LINGO:
LINGO Model:
Model:
SETS:
PROFS: TOTTEACH, FTEACH, STEACH, SATEACH, SBTEACH, FATEACH, FBTEACH, ABID,
BBID, MAXS, MAXF;
!TOTTEACH=The total number of courses that must be taught by the professor.
FTEACH=The # of courses the prof teaches in the fall.
STEACH=The # of courses the prof teaches in the spring.
SATEACH=The # of course A the prof teaches in the spring.
SBTEACH=The # of course B the prof teaches in the spring.
FATEACH, F_B_TEACH=Similar to above, but in the fall.
ABID, BBID= The bids for courses A and B the prof has given.
MAXS=The max number of courses the professor wishes to teach in the spring.
MAXF=The max number of courses the prof wishes to teach in the fall.;
COURSES: MINI, MAXI, TOTAL;
!MINI=The minimum # of sections of the course required.
MAXI=The maximum # of sections of the course required.
TOTAL=The total # of sections of the course offered.;
ENDSETS
DATA:
PROFS= X, Y, Z;
TOTTEACH=4, 4, 4;
ABID= 6, 3, 8;
BBID= 4, 7, 2;
MAXS= 3, 2, 3;
MAXF= 1, 3, 1;
COURSES= A, B;
MINI= 3, 2;
MAXI= 7, 8;
ENDDATA
MAX = @SUM(PROFS(I):
ABID(I)*(SATEACH(I)+FATEACH(I))+BBID(I)*(SBTEACH(I)+FBTEACH(I)));
!Compute total teaching;
@FOR(PROFS(I): TOTTEACH(I)-STEACH(I)-FTEACH(I)=0);
!Prof each term to course;
@FOR(PROFS(I): STEACH(I)-SATEACH(I)-SBTEACH(I)=0);
@FOR(PROFS(I): FTEACH(I)-FATEACH(I)-FBTEACH(I)=0);
!Load each term for each prof;
@FOR(PROFS(I): STEACH(I)<=MAXS(I));
@FOR(PROFS(I): FTEACH(I)<=MAXF(I));
!Course coverage;
@FOR(COURSES(J):@BND(MINI(J),TOTAL(J),MAXI(J)));
!Teaching of each course;
@FOR(COURSES(J)|J#EQ#1:
@SUM(PROFS(I):SATEACH(I)+FATEACH(I))= TOTAL(J)
);
@FOR(COURSES(J)|J#EQ#2:
@SUM(PROFS(I):SBTEACH(I)+FBTEACH(I))=TOTAL(J)
);
END
Global optimal solution found.
Objective value: 82.00000
Infeasibilities: 0.000000
Total solver iterations: 4
Variable Value Reduced Cost
TOTTEACH( X) 4.000000 0.000000
TOTTEACH( Y) 4.000000 0.000000
TOTTEACH( Z) 4.000000 0.000000
FTEACH( X) 1.000000 0.000000
FTEACH( Y) 3.000000 0.000000
FTEACH( Z) 1.000000 0.000000
STEACH( X) 3.000000 0.000000
STEACH( Y) 1.000000 0.000000
STEACH( Z) 3.000000 0.000000
SATEACH( X) 2.000000 0.000000
SATEACH( Y) 0.000000 6.000000
SATEACH( Z) 3.000000 0.000000
SBTEACH( X) 1.000000 0.000000
SBTEACH( Y) 1.000000 0.000000
SBTEACH( Z) 0.000000 4.000000
FATEACH( X) 1.000000 0.000000
FATEACH( Y) 0.000000 6.000000
FATEACH( Z) 1.000000 0.000000
FBTEACH( X) 0.000000 0.000000
FBTEACH( Y) 3.000000 0.000000
FBTEACH( Z) 0.000000 4.000000
ABID( X) 6.000000 0.000000
ABID( Y) 3.000000 0.000000
ABID( Z) 8.000000 0.000000
BBID( X) 4.000000 0.000000
BBID( Y) 7.000000 0.000000
BBID( Z) 2.000000 0.000000
MAXS( X) 3.000000 0.000000
MAXS( Y) 2.000000 0.000000
MAXS( Z) 3.000000 0.000000
MAXF( X) 1.000000 0.000000
MAXF( Y) 3.000000 0.000000
MAXF( Z) 1.000000 0.000000
MINI( A) 3.000000 0.000000
MINI( B) 2.000000 0.000000
MAXI( A) 7.000000 0.000000
MAXI( B) 8.000000 0.000000
TOTAL( A) 7.000000 -2.000000
TOTAL( B) 5.000000 0.000000
Row Slack or Surplus Dual Price
1 82.00000 1.000000
2 0.000000 0.000000
3 0.000000 -7.000000
4 0.000000 0.000000
5 0.000000 -4.000000
6 0.000000 -7.000000
7 0.000000 -6.000000
8 0.000000 -4.000000
9 0.000000 -7.000000
10 0.000000 -6.000000
11 0.000000 4.000000
12 1.000000 0.000000
13 0.000000 6.000000
14 0.000000 4.000000
15 0.000000 0.000000
16 0.000000 6.000000
17 0.000000 2.000000
18 0.000000 0.000000
4. Given sets, data and constraints in LINGO, express all of it as usual mathematical terms:
SETS:
BOND/1..2/ : MATAT, PRICE, CAMNT, BUY;
PERIOD/1..15/: NEED, SINVEST;
ENDSETS
DATA:
STRTE = .04;
MATAT = 6, 13;
PRICE = .980, .965;
CAMNT = .060, .065;
NEED = 10, 11, 12, 14, 15, 17, 19, 20, 22, 24,
26, 29, 31, 33, 36;
ENDDATA
@FOR( PERIOD( I)| I #GT# 1:
@SUM( BOND( J)| MATAT( J) #GE# I:
CAMNT( J) * BUY( J)) +
@SUM( BOND( J)| MATAT( J) #EQ# I: BUY( J)) +
( 1 + STRTE) * SINVEST( I - 1) = NEED( I) + SINVEST( I);
);
@FOR( BOND( J): @GIN( BUY( J)););
Data:
