=========================preview======================
(ielm201)[2004](f)final~PPSpider^_10354.pdf
Back to IELM201 Login to download
======================================================
IEEM 201 Operations Research I
Final Exam
December, 2004
Name Student ID
1. Solve the following problem by the two-phase method. [15 points]
Maximize
Subject to
And
2. The Cost-Less Corp. supplies its four retail outlets from its four plants. The shipping cost per shipment from each plant to each retail outlet is given below.
Unit Shipping Cost (in hundreds)
Retail Outlet
Plant
1
2
3
4
1
$5
$6
$4
$2
2
$2
$9
$1
$3
3
$3
$4
$2
$1
4
$2
$1
$3
$2
Plants 1, 2, 3 and 4 make 10, 20, 20, and 10 shipments per month, respectively. Retail outlets 1, 2, 3, and 4 need to receive 20, 10, 10, and 20 shipments per month, respectively.
The distribution manager, Randy Smith, now wants to determine the best plan for how many shipments to send from each plant to the respective retail outlets each month. Randys objective is to minimize the total shipping cost.
(a) By treating this problem as a transportation problem, construct an appropriate parameter table. [3 points]
(b) Use the northwest corner rule to construct an initial basic feasible solution. [3 points]
(c) Starting with the initial basic feasible solution from part (b), apply the transportation simplex method to obtain an optimal solution. [9 points]
3. Blue Star Company is allocating 4 machines to 3 factories belonging to Blue Star. Factory k will generate profit gk(uk) million dollars if it has uk machines. How to allocate the machines so that Blue Star can get maximum profit?
factory k
# machines uk gk(uk)
1
2
3
0
0
0
0
1
4
2
3
2
4
5
5
3
7
6
7
4
7
8
8
(a) Formulate this problem as a dynamic programming problem. Please specify clearly the stages, states, decisions, state transitions, and recursive relationship. [5 points]
(b) Solve the dynamic programming problem formulated in part (a). [10 points]
4. Consider a network represented by the matrix below. The matrix shows the length of the arcs between nodes. For example, the first row means, there are two arcs going from node 1 to node 2 and to node 4, with length 6 and 10, respectively (trivially there is zero distance from node 1 to itself, which is stated by 0 in the first diagonal position).
(a) Draw the network. [5 points]
(b) Determine the shortest path from node 1 to node 7. [10 points]
5. Consider the following linear programming problem:
Maximize
Subject to
And
(a) Compute the basic feasible solution in which
and
are basic variables. [3 points]
(b) Compute the basic feasible solution in whichand
are basic variable. [3 points]
(c) For each solution computed in the above two parts, determine whether it is optimal to the problem and explain your reason. [8 points]
6. Consider the following linear programming p