Yelena Vardanyan

Yelena_Vardanyan

Anahit Sargsyan

Sergey Tumanyan

IE230 Operations Research I

Homework #8 - Due Friday, 21 April 2006

1. Consider the transportation tableau:

dstn
source / V1
1 / V2
2 / V3
3 / V4
4 / V5
5 / Supply
A
U1 / 12 / 8 / 9
5 / 15 / 11
4 / 9
B
U2 / 10
4 / 11 / 12 / 11
3 / 14 / 7
C
U3 / 9 / 7 / 11 / 14
2 / 8
2 / 4
D
U4 / 13 / 12
7 / 13
0 / 12 / 12 / 7
E
U5 / 8 / 9 / 10 / 9 / 10
3 / 3
Demand= / 4 / 7 / 5 / 5 / 9

a. Use the initial basic solution: XA3=5, XA5=4, XB1=4, XB4=3, XC4=XC5=2, XD2=7, XE5=3

& _XD3____ = 0. (Choose one more variable to complete the basis. Any choice is valid except one that would create a “cycle” of basic cells in the tableau!)

b. Compute two different sets of values for the dual variables U & V (simplex multipliers) for this basis (by starting with different choice of the arbitrary initial variable to be assigned a value, e.g., zero.)

I Reduce costs

[c11] = u1+v1 –c11=0 +16 -12 =4

U1 = 0[c12] = u1 + v2 – c12=0+8-8=0

U1 + v3=9, v3= 9[c14] = u1 + v4 –c14 = 0+17 -15 =2

U1 + v5 = 11, v5 =11[c22] = u2 + v2 –c22 = -6 +8 – 11= -9

U3 +v5 = 8, u3 = -3[c23] = u2 +v3 –c23 = -6 + 9 -12 = -9

U3 + v4 = 14, v4 = 17[c25] = u2 + v5 –c25= -6 + 11-14 = -9

U2 +v4 = 11, u2 = -6[c31] = u3 + v1 – c31 = -3 +16 -9 = 4

U2 + v1 = 10, v1 = 16[c32] = u3 + v2 –c32= -3 + 8-7 = -2

U5 + v5 = 10, u5 = -1[c33]= u3 + v3 –c33 = -3 + 9 -11 = -5

U4 + v3 = 13, u4 = 4[c41] = u4 + v1 – c41 = 4 + 16 – 13 = 7

U4 + v2 = 12, v2 = 8[c44] = u4 + v4 – c44 = 4+ 17 – 12 = 9

[c45] = u4 + v5 –c45 = 4+ 11-12=3

[c51] = u5 + v1 –c51= -1 +16 – 8 =7

[c52] = u5 + v2 –c52= -1 + 8 – 9 = -2

[c53] = u5 + v3 – c53 = -1 + 9 -10 = -2

[c54] = u5 + v4 – c54 = -1+17 – 9 = 7

Using each set of simplex multipliers, price all of the nonbasic cells. How do the reduced costs depend upon the choice of dual variables? Select the variable having the “most negative” reduced cost to enter the basis.

II Reduce costs of non basic variable

u2 = 0 [c11] = u1 + v1 – c11 = 6+ 10 -12 =4

u2 + v1 = 10, v1 =10 [c12] = u1 +v2 –c12 = 6+ 2 – 8 =0

u2 + v4 = 11, v4 = 11 [c14] = u1 +v4 –c14 = 6+ 11 – 15=2

u3 + v4 = 14, u3 = 3 [c22] = u2 + v2 –c22 = 0 + 2 – 11 = -9

u3 + v5 = 8, v5 = 5 [c23] = u2 + v3 –c23 = 0 +3 – 12 = -9

u1 + v5 = 11, u1 =6 [c25] = u2 + v5 – c25 = 0 + 5 – 14 = -9

u1 + v3 = 9, v3 = 3 [c31] = u3 + v1 –c31 = 3+ 10 – 9 = 4

u4 + v3 = 13, u4 = 10 [c32] = u3 +v2 –c32 = 3+ 2-7 = -2

u4 +v2 = 12, v2 = 2 [c33] = u3 + v3 – c33 = 3+ 3-11 = -5

u5 + v5 = 10, u5 = 5 [c41] = u4 + v1 –c41 = 10 +10 -13 = 7

[c44] = u4 + v4 –c44 = 10 + 11 -12 =9

[c45] = u4 + v5 –c45 = 10 +5-12 = 3

[c51] = u5 + v1 –c51= 5 +10 -8 = 7

[c52] = u5 + v2 –c52 = 5 +2 – 9 = -2

[c53] = u5 + v3 – c53 = 5+ 3 -10 = -2

[c54] = u5 + v4 –c54 = 5+ 11 – 9 =7

This shows that reduced costs of non basic variables do not depend on different choice of dual variable. The “most negative” reduced cost (in our case “most positive”) is c44=9.

d. What variable will leave the basis as the new variable enters the basis?

When X44 enters the basis X43 will leave the basis. This feasible solution is degenerate.

e. Complete the computation of the optimal solution, using the transportation simplex method.

dstn
source / V1
1 / V2
2 / V3
3 / V4
4 / V5
5 / Supply
A
U1 / 12 / 8 / 9
5 / 15 / 11
4 / 9
B
U2 / 10
4 / 11 / 12 / 11
3 / 14 / 7
C
U3 / 9 / 7 / 11 / 14
2 / 8
2 / 4
D
U4 / 13 / 12
7 / 13 / 12
0 / 12 / 7
E
U5 / 8 / 9 / 10 / 9 / 10
3 / 3
Demand= / 4 / 7 / 5 / 5 / 9

u1 =0 Reduce costs

u1 + v3 = 9, v3 = 9[c11] = u1 +v1 –c11= 0+16-12 = 4

u1 +v5 = 11, v5 =11[c12] =u1 + v2 –c12 = 0+ 17-8 = 9

u3 +v5 = 8, u3 = -3[c14] = u1 + v4 –c14= 0+17- 15=2

u3 + v4 =14, v4 = 17[c22] = u2 + v2 –c22 = -6 +17-11=0

u2 + v4 = 11, u2 = -6[c23] = u2 + v3 –c23= -6+ 9-12 = -9

u2 + v1 = 10, v1 = 16[c25] = u2 + v5 –c25= -6+11-14 = -9

u4 + v4 = 12, u4 = -5[c31] = u3 + v1 –c31 = -3 + 16 -9 = 4

u4 + v2 = 12, v2 =17[c32] = u3 + v2 – c32 = -3 +17 – 7 = 10

u5 + v5 = 10, u5 = -1[c33] = u3 +v3 –c33= -3 +9 -11 = -3

[c41]= u4 + v1 – c41= -5 + 16 -13 = -2

[c43] = u4 + v3 –c43 = -5+ 9 – 13 = -9

[c45]= u4 +v5 – c45 = -5 +11-12 = -6

[c51] = u5 + v1 – c51 = -1 + 16 -8 = 7

[c52] = u5 + v2 – c52 = -1 +17 -9 = 7

[c53] = u5 + v3 –c53 = -1 +9 -10 = -2

[c54] = u5 + v4 – c54 = -1 + 17 -9 = 7

List of reduce costs shows that X32 should enter the basis. X34 will leave the basis.

dstn
source / V1
1 / V2
2 / V3
3 / V4
4 / V5
5 / Supply
A
U1 / 12 / 8 / 9
5 / 15 / 11
4 / 9
B
U2 / 10
4 / 11 / 12 / 11
3 / 14 / 7
C
U3 / 9 / 7
2 / 11 / 14 / 8
2 / 4
D
U4 / 13 / 12
5 / 13 / 12
2 / 12 / 7
E
U5 / 8 / 9 / 10 / 9 / 10
3 / 3
Demand= / 4 / 7 / 5 / 5 / 9

u1 = 0 Reduce costs

u1 + v3 = 9, v3 =9[c11] = u1 +v1 –c11 = 0+ 1-12 = -11

u1 + v5 = 11, v5 = 11[c12] = u1 + v1 –c12 = 0+1-8 = -7

u3 + v5 = 8, u3 = -3[c14] = u1 + v4 –c14 = 0 + 10 – 15 = -5

u3 + v2 = 7, v2 = 10[c22] = u2 + v2 – c22 = 1 + 10 – 11 = 0

u4 + v2 = 12, u4 = 2[c23] = u2 + v3 – c23 = 1 +9 – 12 = -2

u4 + v4 = 12, v4 = 10[c25] = u2 +v5 – c25 = 1 + 11 – 14 =-2

u2 + v4 = 11, u2 = 1[c31] = u3 + v1 – c31 = -3 + 1 -9 = -11

u2 + v1 = 10, v1 = 1[c33] = u3 + v3 – c33 = -3 + 9 -11 = -5

u5 + v5 = 10, u5 = -1[c34] = u3 + v4 – c34 = -3 + 10 – 14 = -7

[c41] = u4 + v1 – c41 = 2 + 1 – 13 = -10

[c43] = u4 + v3 – c43 = 2 + 9 – 13 = -2

[c45] = u4 + v5 – c45 = 2+ 11 – 12 = 1

[c51] = u5 + v1 – c51 = -1 + 1 – 8 = -8

[c52] = u5 + v2 – c52 = -1 + 10 – 9 = 0

[c53] = u5 + v3 –c53 = -1 + 9 – 10 = -2

[c54] = u5 + v4 – c54 = -1 + 10 – 9 = 0

It shows that X45 will enter the basis.X35 will leave the basis.

dstn
source / V1
1 / V2
2 / V3
3 / V4
4 / V5
5 / Supply
A
U1 / 12 / 8 / 9
5 / 15 / 11
4 / 9
B
U2 / 10
4 / 11 / 12 / 11
3 / 14 / 7
C
U3 / 9 / 7
4 / 11 / 14 / 8 / 4
D
U4 / 13 / 12
3 / 13 / 12
2 / 12
2 / 7
E
U5 / 8 / 9 / 10 / 9 / 10
3 / 3
Demand= / 4 / 7 / 5 / 5 / 9

u1 = 0 Reduce costs

u1 + v3 = 9, v3 = 9[c11] = u1 + v1 –c11 = 0 + 10 – 12 = -2

u1 + v5 = 11, v5 = 11[c12] = u1 + v2 – c12 = 0 + 11 – 8 = 3

u4 +v5 =12, u4 = 1[c14] = u1 + v4 – c14 = 0 + 11 – 15 = -4

u5 + v5 = 10, u5 = -1[c22] = u2 + v2 – c22 = 0 + 11 – 11 = 0

u4 + v4 = 12, v4 = 11[c23] = u2 + v3 – c23 = 0 +9 – 12 = -3

u2 + v4 = 11, u2 = 0[c25] = u2 + v5 – c25 = 0 + 11 – 14 = -3

u2 + v1 = 10 , v1 = 10[c31] = u3 + v1 – c31 = -4 + 10 – 9 = -3

u4 + v2 = 12, v2 = 11[c33] = u3 + v3 – c33 = -4 + 9 – 11 = -6

u3 + v2 = 7, u3 = -4[c34] = u3 + v4 –c34 = -4 + 1 – 14 = -17

[c35] = u3 + v5 – c35 = -4 + 11 – 8 = -1

[c41] = u4 + v1 – c41 = 1 + 10 -13 = -2

[c43] = u4 + v3 – c43 = 1 + 9 – 13 = -3

[c51] = u5 + v1 – c51 = -1 + 10 – 8 = 1

[c52] = u5 + v2 – c52 = -1 + 11 -9 = 1

[c53] = u5 + v3 – c53 = -1 + 9 -10 = -2

[c54] = u5 + v4 – c54 = -1 +11 – 9 = 1

It shows that X12will enter the basis.X42 will leave the basis.

dstn
source / V1
1 / V2
2 / V3
3 / V4
4 / V5
5 / Supply
A
U1 / 12 / 8
3 / 9
5 / 15 / 11
1 / 9
B
U2 / 10
4 / 11 / 12 / 11
3 / 14 / 7
C
U3 / 9 / 7
4 / 11 / 14 / 8 / 4
D
U4 / 13 / 12 / 13 / 12
2 / 12
5 / 7
E
U5 / 8 / 9 / 10 / 9 / 10
3 / 3
Demand= / 4 / 7 / 5 / 5 / 9

u1 = 0 Reduce costs

u1 + v2 = 8, v2 = 8 [c11] = u1 + v1 – c11 = 0 + 10 -12 = -2

u1 + v3 = 9 , v3 = 9 [c14] = u1 + v4 – c14= 0 + 11 – 15 = -4

u1 + v5 = 11, v5 = 11 [c22] = u2 + v2 – c22 = 0 + 8 – 11 = -3

u4 + v5 = 12, u4 = 1 [c23] = u2 + v3 – c23 = 0 + 9 – 12 = -3

[c25] = u2 + v5 – c25 = 0 + 11 – 14 = -3

u5 + v5 = 10, u5 = -1 [c31] = u3 + v1 – c31 = -1 + 10 -9 = 0

u4 + v4 = 12, v4 = 11 [c33] = u3 + v3 – c33 = -1 + 9 – 11 = -3

u2 + v4 = 11, u2 = 0 [c34] = u3 + v4 – c34 = -1 + 11 -14 = -4

u2 + v1 =10, v1 = 10 [c35] = u3 + v5 – c35 = -1 + 11 – 8 = 2

u3+ v2 = 7, u3 = -1 [c41] = u4 + v1 – c41 = 1 + 10 – 13 = -2

[c42] = u4 + v2 – c42 = 1 + 8 – 12 = -3

[c43] = u4 + v3 – c43 = 1 + 9 – 13 = -3

[c51] = u5 + v1 –c51 = -1 + 10 – 8 =1

[c52] = u5 + v2 – c52 = -1 + 8 – 9 = -2

[c53] = u5 + v3 – c53 = -1 + 9 – 10 = -2

[c54] = u5 + v4 – c54 = -1 + 11 -9 = 1

It shows that X35will enter the basis.X15 will leave the basis.

dstn
source / V1
1 / V2
2 / V3
3 / V4
4 / V5
5 / Supply
A
U1 / 12 / 8
4 / 9
5 / 15 / 11 / 9
B
U2 / 10
4 / 11 / 12 / 11
3 / 14 / 7
C
U3 / 9 / 7
3 / 11 / 14 / 8
1 / 4
D
U4 / 13 / 12 / 13 / 12
2 / 12
5 / 7
E
U5 / 8 / 9 / 10 / 9 / 10
3 / 3
Demand= / 4 / 7 / 5 / 5 / 9

u1 = 0 Reduce costs

u1 + v2 = 8, v2 = 8 [c11] = u1 + v1 –c11 = 0+8 -12 = -4

u1 + v3 = 9, v3 = 9[c14] = u1 + v4 – c14 = 0 + 9 -15 = -6

u3 + v2 = 7, u3 = -1[c15] = u1 + v5 – c15 = 0+ 9 – 11 = -2

u3 + v5 = 8, v5 = 9[c22] = u2 + v2 –c22 = 2+ 8 – 11 = -1

u4 + v5 = 12, u4 = 3[c23] = u2 + v3 – c23 = 2 + 9 -12 = -1

u4 + v4 = 12, v4 = 9[c25] = u2 + v5 – c25 = 2 + 9 -14 = -3

u5 + v5 = 10, u5 = 1[c31] = u3 + v1 – c31 = -1 + 8 – 9 = -2

u2 + v4 = 11, u2 = 2[c33] = u3 + v3 – c33 = -1 + 9 -11 = -3

u2 + v1 = 10, v1 = 8[c34] = u3 + v4 – c34 = -1 + 9 -14 = -6

[c41] = u4 + v1 – c41 = 3 + 8 – 13 = -2

[c42] = u4 + v2 – c42 = 3 + 8 -12 = -1

[c43] = u4 + v3 – c43 = 3 + 9 – 13 = -1

[c51] = u5 + v1 – c51 = 1 + 8 – 8 =1

[c52] = u5 +v2 - c52 = 1 + 8 – 9 =0

[c53] = u5 + v3 – c53 = 1 + 9 – 10 = 0

[c54] = u5 + v4 – c54 = 1 + 9 -9 = 1

It shows that X54will enter the basis.X15 will leave the basis.

dstn
source / V1
1 / V2
2 / V3
3 / V4
4 / V5
5 / Supply
A
U1 / 12 / 8
4 / 9
5 / 15 / 11 / 9
B
U2 / 10
4 / 11 / 12 / 11
3 / 14 / 7
C
U3 / 9 / 7
3 / 11 / 14 / 8
1 / 4
D
U4 / 13 / 12 / 13 / 12 / 12
7 / 7
E
U5 / 8 / 9 / 10 / 9
2 / 10
1 / 3
Demand= / 4 / 7 / 5 / 5 / 9

u1 = 0 Reduce costs

v2 = 8 [c11] = u1 + v1 – c11 = 0 + 7 – 12 = -5

v3 = 9 [c14] = u1 + v4 – c14 = 0 +8 – 15 = -7

u3 + v2 = 7 , u3 = -1[c22] = u2 + v2 –c22 = 3 + 8 – 11 = 0

u3 + v5 = 8, v5 = 9[c15] = u1 + v5 – c15 = 0 + 9 -11 =-2

u4 + v5 = 12, u4 = 3[c23] = u2 + v3 –c23 = 3 + 9 -12= 0

u5 + v5 = 10, u5 = 1[c25] = u2 + v5 – c25 = 3 + 9 -14 = -2

u5 + v4 = 9, v4 = 8 [c31] = u3 + v1 –c31 = -1 + 7 – 9 = -3

u2 + v4 = 11, u2 = 3[c33] = u3 + v3 – c33 = -1 + 9 – 11= -3

u2 + v1 = 10, v1 = 7[c34] = u3 + v4 –c34 = -1 + 8 – 14 = -7

[c41] = u4 + v1 –c41= 3 + 7 – 13 = -3

[c42] = u4 + v2 – c42 = 3 + 8 -12 = -1

[c43] = u4 + v3- c43 = 3 + 9 -13= -3

[c44] = u4 + v4 – c44 = 3 + 8 – 12 = -1

[c51] = u5 + v1 – c51 = 1 + 7 – 8 = 0

[c52] = u5 + v2 – c52 = 1 + 8 – 9 =0

[c53] = u5 + v3 – c53 = 1 + 9 – 10 = 0

This shows that the tableau is optimal but not unique .

2. Transportation problem. A bank has two sites at which checks are processed. Site 1 can process 9,000 checks per day and site 2 can process 7000 checks per day. The bank processes three types of checks: vendor checks, salary checks, and personal checks. Each day 5000 checks of each type must be processed. The processing cost per check depends on the site at which the check is processed: (1¢ = $0.01)

Type of check / Site #1 / Site #2
Vendor checks / 5¢ / 3¢
Salary checks / 4¢ / 4¢
Personal checks / 2¢ / 5¢

(a.) Formulate a balanced transportation problem to minimize the daily cost of processing checks. (That is, provide the transportation tableau for the problem.) What is the number of basic variables in any basic solution to this problem?

Let denote Xij quantity shipped from source I to destination j

Supply constraints will be the following

X11 + X12 + X13 + X14 = 9000

X21 + X22 + X23 + X24 = 7000

Demand constraint will be the following

X11 + X21 = 5000

X12 + X22 =5000

X13 + X23 = 5000

X14 + X24 = 5000

and using this table

Type of check / Site #1 / Site #2
Vendor checks / 5¢ / 3¢
Salary checks / 4¢ / 4¢
Personal checks / 2¢ / 5¢

We will get

Van. chacks / Sal. chacks / Per. chacks / dummy / Supply
Site I / 5 / 4 / 2 / 0 / 9000
Site II / 3 / 4 / 5 / 0 / 7000
Demand / 5000 / 5000 / 5000 / 1000

Because the number of basic variables is m + n – 1, and in our case m = 2(number of rows),

n = 4(the number of columns)

the number of basic variable will be 2+4-1=5

(b.) Use the Northwest-Corner to find a basic feasible solution to the problem. Compute the total cost for this basic feasible solution.

Van. chacks / Sal. chacks / Per. chacks / dummy / Supply
Site I / 5
5000 / 4
4000 / 2 / 0 / 9000
Site II / 3 / 4
1000 / 5
5000 / 0
1000 / 7000
Demand / 5000 / 5000 / 5000 / 1000

Z = 5000*5 + 4000*4 + 1000*4 + 5000*5+ 1000*0 =70000

(c.)Starting with the Northwest-Corner solution, perform the simplex algorithm to find the optimal solution to this problem. At each iteration, state the values of the dual variables and the reduced costs of each nonbasic "shipment".

Because for basic variables =0 , ui + vj =cij using this we can compute values of the dual variables and the reduced costs of each nonbasic "shipment".

I step

u1 = 0, for nonbasic variables = ui + vj - cij

u1+v1 = 5, v1 = 5 = u2 + v1 – c21= 0+5-3=2

u1 + v2 = 4, v2 =4 = u1 +v3–c13 = 0 + 5 - 2 = 3

u2 + v2 = 4, u2 = 0 = u1 + v4 –c14 = 0+0-0=0

u2 + v3 = 5, v3 = 5

u2 + v4 = 0, v4=0 so X13 will enter the basis

Van. chacks / Sal. chacks / Per. chacks / dummy / Supply
Site I / 5
5000 / 4 / 2
4000 / 0 / 9000
Site II / 3 / 4
5000 / 5
1000 / 0
1000 / 7000
Demand / 5000 / 5000 / 5000 / 1000

II step for nonbasic variables = ui + vj - cij

U1 =0 = u1 + v2 – c12 = 0+1-4=-3

U1 + v1 = 5, v1 = 5

U1 + v3 = 2, v3 = 2 = u2 + v1 – c21 = 3+5-3=5

U2 + v3 = 5, u2 = 3

U2 + v2 =4, v2 = 1 = u1 + v4 – c14=0+(-3)-0=-3

U2 +v4 =0, v4 = -3

So X21 will enter the basis

Van. chacks / Sal. chacks / Per. chacks / dummy / Supply
Site I / 5
4000 / 4 / 2
5000 / 0 / 9000
Site II / 3
1000 / 4
5000 / 5 / 0
1000 / 7000
Demand / 5000 / 5000 / 5000 / 1000

III step

U1 = 0, v1 = 5 for nonbasic variables = ui + vj - cij

U2 + v1 = 3, u2 = -2 =u1 + v2 – c12= 0+6-4=2

U2 + v2 = 4, v2 = 6 = u2 +v3 –c23 =-2+2-5= -5

U1 + v3 =2, v3

U2 + v4 = 0, v4 = 2 = u1 + v4 –c14=0+2-0=2

So X14 will enter the basis

Van. chacks / Sal. chacks / Per. chacks / dummy / Supply
Site I / 5 / 4
4000 / 2
5000 / 0 / 9000
Site II / 3
5000 / 4
1000 / 5 / 0
1000 / 7000
Demand / 5000 / 5000 / 5000 / 1000

IV step

U1 =0,for nonbasic variables = ui + vj - cij

u1 + v2 = 4, v2=4

u1 + v3 = 2, v3 =2 =u1 + v1 –c11= 0+3-5=-2

u2 + v2 = 4, u2 = 0

u2 + v1 = 3, v1=3 =u1 + v4 –c14 =0+0-0=0

u2 + v4 = 0, v4 =0 =u2 +v3 –c23 = 0+2-5=-3

This means that the tableau is optimal and =0 means that tableau has alternative solution.

So,

Min z = 4000*4 +5000*2 +5000*3 + 1000*4 +1000*0 = 45000

IE230: O.R. IHW #8page 1 of 9