ISE 330: Homework 9 Solutions http://www-classes.usc.edu/engr/ise/330

University of Southern California
Daniel J. Epstein Department of Industrial and Systems Engineering
ISE 330: Introduction to Operations Research
Homework 11 Solution: prepared by Jie Liu

Homework 11: 8.2-4(d)(e), 8.2-14, 8.2-17

The shadowed cell is to represent the basic variable, P is to represent the cycle.

8.2-4

d).

0 / Destination / supply / U[i]
1 / 2 / 3 / 4
1 / 7 / 0 / 4 / 0 / 1 / 1 / 4 / 0 / 1 / 0
2 / 4 / 0 / 6 / 0 / 7 / 0 / 2 / 1 / 1 / 0
3 / 8 / 0 / 5 / 1 / 4 / 0 / 6 / 0 / 1 / 0
4 / 6 / 1 / 7 / 0 / 6 / 0 / 3 / 0 / 1 / 0
Demand / 1 / 1 / 1 / 1
V[j] / 0 / 0 / 0 / 0

The variables are chosen in the order, x13, x24, x44, x32, x41, x43,x42

e).

(0)  Interation:

0 / Destination / supply / U[i]
1 / 2 / 3 / 4
1 / 7 / leaving
1 / 4 / -5 / 1 / entering
-7 / 4 / -1 / 1 / 2
2 / 4 / 0 / 6 / 1 / 7 / 2 / 2 / 0 / 1 / -1
P / P
3 / 8 / 5 / 5 / 0 / 4 / 1 / 6 / 5 / 1 / -2
P / P
4 / 6 / 1 / 7 / 0 / 6 / 0 / 3 / 1 / 1 / 0
Demand / 1 / 1 / 1 / 1
V[j] / 5 / 7 / 6 / 5

1)  Iteration:

0 / Destination / supply / U[i]
1 / 2 / 3 / 4
1 / 7 / 7 / 4 / 2 / 1 / 1 / 4 / 6 / 1 / 1
2 / 4 / 0 / 6 / 1 / 7 / 2 / 2 / 0 / 1 / 5
3 / 8 / 5 / 5 / 1 / 4 / 0 / 6 / 5 / 1 / 4
4 / 6 / 1 / 7 / 0 / 6 / 0 / 3 / 1 / 1 / 6
Demand / 1 / 1 / 1 / 1
V[j] / -1 / 1 / 0 / -3

The optimal assignment is (source, destination): (1,3), (2,1), (3,2), (4,4). Cost is equal to 13.

8.2-14

0 / Destination / supply / U[i]
1 / 2 / 3 / 4
1 / 31 / 400 / 45 / 2 / 38 / -M+37 / 0 / -1 / 400 / 31
2 / 29 / 200 / 41 / 400 / 35 / -M+36 / 0 / 1 / 600 / 29
3 / 32 / -2 / 46 / 400 / 40 / -M+36 / 6 / -4 / 400 / 4
4 / 28 / -2 / 42 / 200 / M / 400 / 0 / 0 / 600 / 30
5 / 29 / -1 / 43 / 1 / M / 400 / 0 / 600 / 1000 / 30
Demand / 600 / 1000 / 800 / 600 / Z=800M+61400
V[j] / 0 / 12 / M-30 / -30
0 / Destination / supply / U[i]
1 / 2 / 3 / 4
1 / 31 / 400 / 45 / 2 / 38 / 1 / 0 / M-37 / 400 / 2
2 / 29 / leaving
200 / 41 / 0 / 35 / 400 / 0 / M-35 / 600 / 0
P
3 / 32 / -2 / 46 / 400 / 40 / 0 / 6 / M-40 / 400 / 5
4 / 28 / -2 / 42 / 600 / M / M-36 / 0 / M-36 / 600 / 1
5 / 29 /

Entering

-M+35 / 43 / -M+37 / M / 400 / 0 / 600 / 1000 / M-35
P
Demand / 600 / 1000 / 800 / 600 / Z=400M+75800
V[j] / 29 / 41 / 35 / -M+35
0 / Destination / supply / U[i]
1 / 2 / 3 / 4
1 / 31 / 400 / 45 / -M+37 / 38 / -M+36 / 0 / -2 / 400 / 2
2 / 29 / M-35 / 41 / 0 / 35 / 600 / 0 / M-35 / 600 / -M+35
P / P
3 / 32 / M-37 / 46 / 400 / 40 / 0 / 6 / M-40 / 400 / -M+40
4 / 28 / M-37 / 42 / 600 / M / M-36 / 0 / M-36 / 600 / -M+36
5 / 29 / 200 / 43 / entering
-M+37 / M / 200 / 0 / 600 / 1000 / 0
Demand / 600 / 1000 / 800 / 600 / Z=200M+82800
V[j] / 29 / M+6 / M / 0
0 / Destination / supply / U[i]
1 / 2 / 3 / 4
1 / 31 / 400 / 45 / 0 / 38 / -1 / 0 / -2 / 400 / 45
2 / 29 / 2 / 41 / -200 / 35 / 800 / 0 / 2 / 600 / 41
3 / 32 / 0 / 46 / leaving
400 / 40 / 0 / 6 / entering
-3 / 400 / 46
4 / 28 / 0 / 42 / 600 / M / M-36 / 0 / 1 / 600 / 42
5 / 29 / 200 / 43 / 200 / M / M-37 / 0 / 600 / 1000 / 43
P / P
Demand / 600 / 1000 / 800 / 600 / Z=90200
V[j] / -14 / 0 / -6 / -43
0 / Destination / supply / U[i]
1 / 2 / 3 / 4
1 / 31 / 400 / 45 / 0 / 38 / -1 / 0 / entering
-2 / 400 / 2
P
2 / 29 / 2 / 41 / -200 / 35 / 800 / 0 / 2 / 600 / -2
3 / 32 / 3 / 46 / 3 / 40 / 3 / 6 / 400 / 400 / 0
4 / 28 / 0 / 42 / 600 / M / M-36 / 0 / 1 / 600 / -1
5 / 29 / 200 / 43 / 600 / M / M-37 / 0 / leaving
200 / 1000 / 0
P
Demand / 600 / 1000 / 800 / 600 / Z=89000
V[j] / 29 / 43 / 37 / 0
0 / Destination / supply / U[i]
1 / 2 / 3 / 4
1 / 31 / leaving
200 / 45 / 0 / 38 / entering
-1 / 0 / 200 / 400 / 45
2 / 29 / 2 / 41 / -200 / 35 / 800 / 0 / 2 / 600 / 41
P / P
3 / 32 / 3 / 46 / 3 / 40 / 3 / 6 / 400 / 400 / 45
4 / 28 / 0 / 42 / 600 / M / M-36 / 0 / 1 / 600 / 42
5 / 29 / 400 / 43 / 600 / M / M-37 / 0 / 2 / 1000 / 43
Demand / 600 / 1000 / 800 / 600 / Z=88600
V[j] / 29 / 43 / 37 / 0
0 / Destination / supply / U[i]
1 / 2 / 3 / 4
1 / 31 / 200 / 45 / 0 / 38 / 200 / 0 / 200 / 400 / 44
2 / 29 / 2 / 41 / 0 / 35 / 600 / 0 / 3 / 600 / 41
3 / 32 / 2 / 46 / 2 / 40 / 2 / 6 / 400 / 400 / 44
4 / 28 / 0 / 42 / 600 / M / M-36 / 0 / 2 / 600 / 42
5 / 29 / 600 / 43 / 400 / M / M-37 / 0 / 1 / 1000 / 43
Demand / 600 / 1000 / 800 / 600 / Z=88400
V[j] / -14 / 0 / -6 / -44

The optimal solution is: x13=200, x14=200, x25=600, x34=400, x42=600, x51=600, x52=400.

8.2-17

Northwest Corner Rule:

0 / Destination / supply / U[i]
1 / 2 / 3 / 4
1 / 800 / 20 / 700 / 20 / 400 / 10 / 0 / 100 / 50 / -100
P / P
2 / 600 / entering
-300 / 800 / 0 / 500 / leaving
10 / 0 / 40 / 50 / 0
Demand / 20 / 20 / 20 / 40 / Z=39000
V[j] / 900 / 800 / 500 / 0
0 / Destination / supply / U[i]
1 / 2 / 3 / 4
1 / 800 / leaving
10 / 700 / 20 / 400 / 20 / 0 / entering
-200 / 50 / 0
2 / 600 / entering
10 / 800 / 300 / 500 / leaving
300 / 0 / 40 / 50 / -200
P / P
Demand / 20 / 20 / 20 / 40 / Z=36000
V[j] / 800 / 700 / 400 / 200
0 / Destination / supply / U[i]
1 / 2 / 3 / 4
1 / 800 / 200 / 700 / 20 / 400 / 20 / 0 / 10 / 50 / 0
2 / 600 / 20 / 800 / 100 / 500 / 100 / 0 / 30 / 50 / 0
Demand / 20 / 20 / 20 / 40 / Z=34000
V[j] / 600 / 700 / 400 / 0

Vogel’s Methods:

0 / Destination / supply / U[i]
1 / 2 / 3 / 4
1 / 800 / leaving
10 / 700 / 20 / 400 / 20 / 0 / entering
-200 / 50 / 200
2 / 600 / 10 / 800 / 300 / 500 / leaving
300 / 0 / 40 / 50 / 0
P / P
Demand / 20 / 20 / 20 / 40 / Z=36000
V[j] / 600 / 500 / 200 / 0
0 / Destination / supply / U[i]
1 / 2 / 3 / 4
1 / 800 / 200 / 700 / 20 / 400 / 20 / 0 / 10 / 50 / 0
2 / 600 / 20 / 800 / 100 / 500 / 100 / 0 / 30 / 50 / 0
Demand / 20 / 20 / 20 / 40 / Z=34000
V[j] / 600 / 700 / 400 / 0

Russell’s Method:

0 / Destination / supply / U[i]
1 / 2 / 3 / 4
1 / 800 / 300 / 700 / 0 / 400 / 10 / 0 / 40 / 50 / 0
P / P
2 / 600 / 20 / 800 / 20 / 500 / leaving
10 / 0 / entering
-100 / 50 / 100
Demand / 20 / 20 / 20 / 40 / Z=37000
V[j] / 500 / 700 / 400 / 0
0 / Destination / supply / U[i]
1 / 2 / 3 / 4
1 / 800 / 200 / 700 / entering
-100 / 400 / 20 / 0 / 30 / 50 / 0
P
2 / 600 / 20 / 800 / leaving
20 / 500 / 100 / 0 / 10 / 50 / 0
P
Demand / 20 / 20 / 20 / 40 / Z=36000
V[j] / 600 / 800 / 400 / 0
0 / Destination / supply / U[i]
1 / 2 / 3 / 4
1 / 800 / 200 / 700 / 20 / 400 / 20 / 0 / 10 / 50 / 0
2 / 600 / 20 / 800 / 100 / 500 / 100 / 0 / 30 / 50 / 0
Demand / 20 / 20 / 20 / 40 / Z=34000
V[j] / 600 / 700 / 400 / 0

6