OR6205
DETERMINISTIC OPERATIONS RESEARCH

Final Exam – Fall 2006


Instructor: Dr. E. Melachrinoudis Student: ______________________

Justify briefly your answer, where appropriate, and show all work!

Problem 1 (20 points)
A government analyst has identified five critical subsystems that are instrumental to the mission
effectiveness of a new fighter aircraft that has been designed by the Aero-Astro aircraft
company. It has been determined that the overall effectiveness of the aircraft is equal to the
product of effectiveness (Eff) of the five subsystems. Only $100K are available for the
subsystems.
Although numerous bids have been received, Aero-Astro has identified two options (A and B)
for each subsystem that meet the design specifications. The table below provides cost and
effectiveness for each of the two options that are considered for the five critical subsystems. For
example, if the company decides to use option B for the third subsystem (WPNS) it will pay
$25K and the subsystem's effectiveness will be .90.
(a) Formulate a dynamic programming model that maximizes the overall effectiveness that
can be obtained. Define stages, decision variables, state, state transformation, and
recursive relationship.
(b) Solve for the last two stages only.
(c) Based on the information you obtained in part (b),
(i) Which option should the company choose (A or B) for Radar and Navigation,
if the budget for these two subsystems was $50K?
(ii) What is the minimum amount of money the company needs to buy these two
subsystems, regardless of effectiveness?

Options Eff and Cost of the options for the five critical subsystems UHF Radio TACAN WPNS Radar Navigation
A Eff = .95 .90 .95 .90 .95 Cost = 20k 15k 30k 40k 20k
B Eff = .90 .85 .90 .85 .80 Cost = 15k 10k 25k 30k 10k

Solution:
(a)
Stages: The subsystems, n = 1, 2, 3, 4, 5
Decision variables: The chosen option for each subsystem, Xn = A or B
States: $K available for remaining subsystems, Sn, S1 = $100K
State transformation:




Recursive relationship: fn*(Sn) = max {eff(Xn).fn+1*(Sn–Cn(Xn))}


(b)

n = 5 f5(S5,X5) f5*(S5) X5* A B
S5 < 10 - - - -
10 ≤ S5 < 20 - .80 .80 B
20 ≤ S5 .95 .80 .95 A


n = 4 f4(S4,X4) f4*(S4) X4* A B
S4 < 40 - - - -
40 ≤ S4 < 50 - (.85)(.80) = .68 .68 B
50 ≤ S4 (.90)(.80) = .72 (.85)(.95) = .8075 .8075 B


(c) (i) f4*(50) = .8075 with X4* = B for radar
f5*(50–30) = .95 with X5* = A for navigation

(ii) S4 = $40K

Sn Sn – Cn(Xn)
Xn
Xn=A,B
Problem 2 (25 points)
Consider the transportation problem having the following cost and requirements table:

Destination
Source 1 2 3 Supply
1 30 25 30 10
2 25 15 20 20
Demand 12 14 7

(a) Identify an initial basic feasible solution using the Northwest Corner method.
(b) Solve using the transportation simplex algorithm. Write below the optimal solution you
found (values of variables and objective function); also display the optimal solution in a
network representation of the problem by displaying sources, destinations and arcs with
(positive) flows.
x11* = 10 x12* = 0 x13* = 0 x21* = 0 x22* = 14 x23* = 6 z* = 630

(c) Find a basic feasible solution using Vogel's approximation method. Is it optimal?

Solution:
(a)
Destination
1 2 3 Supply
So
ur
ce

1 30 25 30 10 0 10
2 25 15 20 20 18 4 0 2 14 4
3 (D) 0 0 0 3 0 3
Demand 12 2 0 14 0 7 0

→ Initial basic solution: x11 = 10, x21 = 2, x22 = 14, x23 = 4, x33 = 3, z = $640.

(b)
Iteration 1:
Destination
1 2 3 Supply
So
ur
ce

1 30 25 30 10 10 5 5
2 25 15 20 20 2 14 4
3 (D) 0 * 0 0 3 –5 5 3
Demand 12 14 7

For basic variables (ui + vj = cij):
x11: u1 + v1 = 30 for u1 = 0, v1 = 30
x21: u2 + v1 = 25 u2 = –5
x22: u2 + v2 = 15 v2 = 20
x23: u2 + v3 = 20 v3 = 25
x33: u3 + v3 = 0 u3 = –25

For nonbasic variables (cij – ui – vj):
x12: c12 – u1 – v2 = 25 – 0 – 20 = 5 > 0
x13: c13 – u1 – v3 = 30 – 0 – 25 = 5 > 0
x31: c31 – u3 – v1 = 0 – (–25) – 30 = –5 < 0 *** since this is negative, solution is not optimal!
x32: c32 – u3 – v2 = 0 – (–25) – 20 = 5 > 0

→ x31 enters the basis with value min (2, 3) = 2, x21 leaves the basis;
donor cells: (2,1) and (3,3); recipient cells: (3,1) and (2,3).

Iteration 2:
Destination
1 2 3 Supply
So
ur
ce

1 30 25 30 10 10 0 0
2 25 15 20 20 5 14 6
3 (D) 0 0 0 3 2 5 1
Demand 12 14 7

For basic variables (ui + vj = cij):
x11: u1 + v1 = 30 for u1 = 0, v1 = 30
x22: u2 + v2 = 15 v2 = 25
x23: u2 + v3 = 20 u2 = –10
x31: u3 + v1 = 0 u3 = –30
x33: u3 + v3 = 0 v3 = 30

For nonbasic variables (cij – ui – vj):
x12: c12 – u1 – v2 = 25 – 0 – 25 = 0 = 0 (multiple optimal solution – see below)
x13: c13 – u1 – v3 = 30 – 0 – 30 = 0 = 0 (multiple optimal solution – see below)
x21: c21 – u2 – v1 = 25 – (–10) – 30 = 5 > 0
x32: c32 – u3 – v2 = 0 – (–30) – 25 = 5 > 0 *** since all are positive, solution is optimal!

→ Optimal solution #1: x11* = 10, x22* = 14, x23* = 6, x31* = 2, x33* = 1, z* = $630. Network
representation of the optimal solution is given as follows:


→ Since reduced costs are zero (c12���� = c13���� = 0), there are multiple optimal solutions:

1 2 3 S 1 2 3 S
1 30 25 * 30 10 30 25 30 10 10 0 0 9 1
2 25 15 20 20 25 15 20 20 5 14 6 13 7
3
(D)
0 0 0 3 0 0 0 3 2 5 1 3
D 12 14 7 12 14 7

→ Optimal solution #2: x11* = 9, x12* = 1, x22* = 13, x23* = 7, x31* = 3, z* = $630.

1
2
3
1
2
3
Sources Destinations
[10]
[20]
[3]
[-12]
[-14]
[-7]
10
14
6
2
1
1 2 3 S 1 2 3 S
1 30 25 30 * 10 30 25 30 10 10 0 0 9 1
2 25 15 20 20 25 15 20 20 5 14 6 14 6
3
(D)
0 0 0 3 0 0 0 3 2 5 1 3
D 12 14 7 12 14 7

→ Optimal solution #3: x11* = 9, x13* = 1, x22* = 14, x23* = 6, x31* = 3, z* = $630.


(c)
Destination
1 2 3 Supply Row difference
So
ur
ce

1 30 25 30 10 0 5 5 0 9 1
2 25 15 20 20 6 0 5 5 5 14 6
3 (D) 0 0 0 3 0 0 3
dj 12 9 0 14 0 7 1 0

Column
difference
25* 15 20
5 10* 10
5 10*

→ Solution: x11 = 9, x13 = 1, x22 = 14, x23 = 6, x31 = 3, z = $630, which is optimal (same as
optimal solution #3 given in part (b)).

1
2
3
Problem 3 (10 points)
Three federally funded projects are to be assigned to three out of four candidate research labs.
The costs of each possible placement are given in the table below. Use the Hungarian algorithm
to determine the most economical allocation of projects and the associated cost. Find alternative
optimal solutions if they exist.

Existing research laboratories
Project Sandy Lab
Furmy
Lab
Xenonne
Lab
Liverly
Lab
Crygenic Cache Memory (CCM) 12 15 10 14
Pentium Oxide Depletion (POD) 8 10 6 9
Galactic Genome Mapping (GGM) 20 22 18 12


Solution:
12 15 10 14 2 5 0 4 0 3 0 4
8 10 6 9 2 4 0 3 0 2 0 3
20 22 18 12 8 10 6 0 6 8 6 0
0 0 0 0 0 0 0 0 0 0 2 2

→ Four lines needed to cross all zeroes => Optimal solution! So, multiple optimal solutions are
as follows, with z* = 30 (12+6+12+0=30 for optimal solution #1 and 10+8+12+0=30 for
optimal solution #2):

Optimal solution #1 Optimal solution #2
12 15 10 14 12 15 10 14
8 10 6 9 8 10 6 9
20 22 18 12 20 22 18 12
0 0 0 0 0 0 0 0

1 2 3
4
Problem 4 (7 points)
For each statement below (1-10) fill-in the blank with a letter to indicate the most appropriate
choice from alternatives (A-I) shown in the list below. An alternative (letter) may be the most
appropriate choice to more than one statement (number).
1. The assignment problem is a special case of the B .
2. The maximum flow problem is a special case of the F .
3. We cannot solve the E, G by simplex.
4. The critical path of a project network is the I from start to finish.
5. The algorithms for solving the E are greedy in nature.
6. The transshipment problem is a generalization of the B .
7. The G, A is a discrete (having integer solutions) optimization problem.
8. A C problem is solved by dividing it into smaller sub-problems which are solved
sequentially.
9. The basic solutions of the A are highly degenerate.
10. The best algorithm for solving the A is a simplex-based one in which we preserve
primal and dual feasibility in each iteration and we strive for complementary slackness.


A. Assignment problem
B. Transportation problem
C. Dynamic programming
D. Maximum flow problem
E. Minimum spanning tree problem
F. Minimum cost network flow problem
G. Generalized assignment problem
H. Shortest path problem
I. Longest path problem

Problem 5 (23 points)
Consider the directed network below:
(a) Assuming that the numbers on the arcs are distances, use Dijstrar’s algorithm to find the
shortest path(s) from node 1 to node 6.
(b) Using the same numbers for arc capacities,
(i) Find the arc flows that maximize flow from node 1 to node 6.
(ii) Find a cut (e.g. a set of arcs) with total capacity equal to the maximum flow.
(c) Refer to the original figure below, but now the numbers on the arcs represent unit costs of
flow. In addition, nodes 1 and 2 are sources supplying 2 and 3 units, respectively, and
nodes 5 and 6 are sinks requiring 3 and 2 units, respectively. Arcs (1,3) and (5,6) have a
flow capacity of 3 and 2 units, respectively. Formulate a minimum cost network flow
model by writing the objective function and the constraints.








Solution:
(a)
n
Solved nodes
directly
connected to
unsolved nodes
Closest
connected
unsolved
node
Total
distance
involved
nth
nearest
node
Minimum
distance
Last
connection
1 1 2 1 2 1 (1,2)
2 1 2
4
3
3
1+7=8 4 3 (1,4)*
3
1
2
4
3
3
3
6
1+7=8
3+2=5
3 5 (4,3)*
4
2
4
3
5
6
5
1+8=9
3+9=12
5+3=8
5 8 (3,5)*
5 4 5
6
6
3+9=12
8+2=10 6 10 (5,6)*

→ Shortest path is 1 → 4→ 3 → 5 → 6, with a total distance of 10.

2
1 5
1
6 3
3
4 6
3
8
9
7
2 2
(b) (i)
Iteration 1: One of several augmenting paths is 1 → 2 → 5 → 6, which has a residual
capacity of min{1, 8, 2} = 1. By assigning a flow of 1 to this path, the resulting residual
network is as follows:











Iteration 2: Assign a flow of 1 to path 1 → 3 → 5 → 6. The resulting residual network is as
follows:











Iteration 3: Assign a flow of 3 to path 1 → 4 → 6. The resulting residual network is as
follows:











→ There are no more augmenting paths, so the current flow pattern is optimal, with the
maximum flow of 2+3=5.

(ii) Cut = {(1,4),(5,6)}, with a total capacity of 2+3=5 (equal to the maximum flow).

2
1 5
0
6 3
3
4 6
3
7
9
7
2
1
1
1
1
0
0
0
0 0
0
2
1 5
0
5 3
3
4 6
2
7
9
7
2
0
1
1
2
1
0
0
0 0
1
2
1 5
0
5 3
0
4 6
2
7
6
7
2
0
1
1
2
1
0
0
3 3
1
(c)
Min z = X12 + 6X13 + 3X14 + 7X23 + 2X43 + 8X25 + 3X35 + 9X46 + 2X56
subject to
X12 + X13 + X14 = 2 (node 1)
−X12 + X23 + X25 = 3 (node 2)
−X13 − X23 − X43 + X35 = 0 (node 3)
−X14 + X43 + X46 = 0 (node 4)
− X25 − X35 + X56 = −3 (node 5)
− X46 − X56 = −2 (node 6)
X13 ≤ 3, X56 ≤ 2, and all variables ≥ 0


Problem 6 (15 points)
A project involves 7 activities (labeled A, B, …, G) with completion times and precedence
relationships as shown in the table below.
Activity Completion time (days) Predecessors
A 3 -
B 6 -
C 2 D, E
D 6 A, B
E 8 B, F
F 5 A
G 3 B, C, F

(a) Construct a network for the project.
(b) Find the critical path and the associated project time by enumerating all possible paths.

Solution:
(a)















(b)
Path Length
Start → A → F → G → Finish 3 + 5 + 3 = 11
Start → A → F → E → C → G → Finish 3 + 5 + 8 + 2 + 3 =21
Start → A → D → C → G → Finish 3 + 6 + 2 + 3 = 14
Start → B → D → C → G → Finish 6 + 6 + 2 + 3 =17
Start → B → E → C → G → Finish 6 + 8 + 2 + 3 =19
Start → B → G → Finish 6 + 3 = 9

F
3
6
A
G
E
8
5
3
6
D C
2
B
Start
Finish
← Critical path!