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 / RHS
1 / -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 / RHS
1 / 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 / RHS
1 / 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 / RHS
1 / 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