AMS 341Final Exam A Prof. TuckerSpring 2012
1. For the following two maximization problems in standard tableau form, determine what variable should become basic and which should become non-basic according to the simplex algorithm (explain your steps). If the current basic solution is optimal or if the l.p.is unbounded, explain why.
a)
Z / x1 / x2 / x3 / s1 / s2 / s3 / RHS1 / -1 / 4 / 0 / 0 / -2 / 0 / 46
0 / 1 / -2 / 0 / 0 / -6 / 1 / 30
0 / 2 / 5 / 1 / 0 / 0 / 0 / 25
0 / -1 / 4 / 0 / 1 / -3 / 0 / 10
b)
Z / x1 / x2 / x3 / s1 / s2 / s3 / RHS1 / 0 / -1 / 5 / 0 / -2 / 0 / 21
0 / 1 / 0 / 6 / 0 / -6 / 0 / 30
0 / 0 / 1 / 5 / 1 / 2 / 0 / 25
0 / 0 / -4 / -4 / 0 / 5 / 1 / 18
2. For the given transportation problem, do the following
a) Use the Northwest corner rule to find an initial basic feasible solution
b) Use the Min Cost rule to find an initial basic feasible solution.
c) Starting with the initial bfs found in a), apply one round of the transportation simplex algorithm to find a better bfs.
Demand123Amount of Supply
Supply 1$9$4$4 40
2$10$7$6 50
3$8$3$7 60
Amount of Demand504555
3. Set-up the following transshipment problem as a transportation tableau (using method in text)
We have 15,000 units in Manhattan and 23,000 units in Buffalo to supply demands of 14,000 units in Los Vegas and 18,000 units in Reno. Possible intermediate cities are Pittsburgh, Chicago, and Dallas. The following table gives the inter-city shipment costs
ToManhBufPittChiDalLVReno
FromManh----334913
Buf----4551112
Pitt----033811
Chi------0458
Dal------025
LV------
Reno------
4. Solve the following assignment problem for finding the min cost matching of letters with numbers.
ABCD(what is this minimum cost)
15694
28355
34485
45673
5. Consider the following project with given precedents, duration (in days), and speed up costs.
ActivityPredecessors DurationSpeed-up Cost per day
A--53
BA34
CA56
DC75
EC34
FD,E66
GB53
HG,F84
a) Draw the project network.
b) Find the early start times for each event node and find the critical path.
c) Suppose the project must be completed in 25 days and any activity can be speeded up by at most 2 days by paying the given speed-up costs. Write the l.p.for solving this problem.
6. Model the following optimization as an integer program; give the objective function, constraints, and indicate the integer values that each variable can assume.
The Armstrong Co. produces three types of bicycles at three different plants. Each plant can space for up to 10 workers. Workers are paid $500 a week at plant one, $600 a week at plant two and $700 a week at plant three. It costs $2000 a week to open up and maintain any of the plants. In a week, a worker can produce the amounts of different bicycles at plant one ( or two or three) given in row one (or two or three) in the following table
Type of BicycleABC
Plant110512
2 7127
3888
Weekly demand for bicycles is: 100 of A, 80 units of B, and 120 units of C.
ALSO, at most one of plants 1 and 3 can be operating.
Minimize costs for meeting this demand.
7. Solve the following knapsack problem by dynamic programming
Max z = 5x1 + 4x2 + 3x3, xi integer
s.t. 4x1 + 3x2 + 2x3 <= 8
AMS 341Final Exam B Prof. TuckerSpring 2012
1. For the following two maximization problems in standard tableau form, determine what variable should become basic and which should become non-basic according to the simplex algorithm (explain your steps). ). If the current basic solution is optimal or if the l.p.is unbounded, explain why.
a)
Z / x1 / x2 / x3 / s1 / s2 / s3 / RHS1 / 0 / -2 / -3 / 0 / 2 / 0 / 26
0 / 1 / 5 / -2 / 0 / -6 / 0 / 32
0 / 0 / 6 / 0 / 1 / 5 / 0 / 26
0 / 0 / -4 / -4 / 0 / 3 / 1 / 18
b)
Z / x1 / x2 / x3 / s1 / s2 / s3 / RHS1 / 0 / -3 / 0 / 0 / 2 / -5 / 40
0 / 1 / -1 / 0 / 0 / 6 / -8 / 32
0 / 0 / 4 / 1 / 0 / 3 / 5 / 22
0 / 0 / 3 / 0 / 1 / -3 / 3 / 16
2. For the given transportation problem, do the following
a) Use the Northwest corner rule to find an initial basic feasible solution
b) Use the Min Cost rule to find an initial basic feasible solution.
c) Starting with the initial bfs found in a), apply one round of the transportation simplex algorithm to find a better bfs.
Demand123Amount of Supply
Supply 1$8$7$5 20
2$6$9$4 50
3$3$5$6 50
Amount of Demand404535
3. Set-up the following transshipment problem as a transportation tableau (using method in text)
We have 25,000 units in the Bronx and 45,000 units in Syracuse to supply demands of 24,000 units in Los Vegas and 38,000 units in Reno. Possible intermediate cities are New Orleans, Chicago, and Dallas. The following table gives the inter-city shipment costs
ToBronxSyrNOChiDalLVReno
From Bronx----4441013
Syr----3751512
NO----033911
Chi------0488
Dal------035
LV------
Reno------
4. Solve the following assignment problem for finding the min cost matching of letters with numbers.
ABCD(what is this minimum cost)
15483
22744
33374
45462
5. Consider the following project with given precedents, duration (in days), and speed up costs.
ActivityPredecessors DurationSpeed-up Cost per day
A--44
BA53
CA33
DC67
EC54
FD,E75
GB64
HG,F43
a) Draw the project network.
b) Find the early start times for each event node and find the critical path.
c) Suppose the project must be completed in 20 days and any activity can be speeded up by at most 3 days by paying the given speed-up costs. Write the l.p.for solving this problem.
6. Model the following optimization as an integer program (give the objective function, constraints, and indicate the values (continuous or integer) that each variable can assume.
The Armstrong Co. produces three types of bicycles at three different plants. Each plant can space for up to 19 workers. Workers are paid $700 a week at plant one, $600 a week at plant two and $500 a week at plant three. It costs $1500 a week to open up and maintain any of the plants. In a week, a worker can produce the amounts of different bicycles at plant one ( or two or three) given in row one (or two or three) in the following table
Type of BicycleABC
Plant112610
2 611 8
3 79 7
Weekly demand for bicycles is: 120 of A, 90 units of B, and 100 units of C.
ALSO, least one of plants 2 and 3 must be operating.
Minimize costs for meeting this demand.
7. Solve the following knapsack problem by dynamic programming
Max z = 6x1 + 4x2 + 5x3, xi integer
s.t. 4x1 + 2x2 + 3x3 <= 8