Question

1. (6 points) Find an optimal solution for the following transportation problem using the minimal cost method and the transportation algorithm: Minimize lahi + 2x12 + 2x13 + 4x21 + 3x22 + 4x23 + 4x31 + 1x32 + 3x33, subject to the constraints X11 + X12 + X13 = 100. x21 +x22 +x23 = 50. r31 + 232 +x33 100 x11 + 2'21 +2'3,-150. 12 22+32-50 x13 + x23 + x33-50. for all i, j = 1.2.3. xij > 0, 3. Consider the same transportation problem as in Question 3. The problem has an optimal solution given by 12 4,1 8, 1 8, 2 10,3 12,3 8 (a) (3 points) Solve the dual problem. Hint: Make use of complementary slackness to obtain a system of linear equations with one free variable. Then consider the equality of objective functions (b) (1 point) Which statement is true? The dual problem has □ a unique olt mal solution □ solutions □ finitely many optimal no optimal solution ם infinitely many optimal solutions

Answer 1

here the variables are denoted as follows:

x11 = x1                   x31 = x7

x12 = x2                  x32 = x8

x13 = x3                  x33 = x9

x21 = x4

x22 = x5

x23 = x6

Min Z = x1 + 2 x2 + 2 x3 + 4 x4 + 3 x5 + 4 x6 + 4 x7 + x8 + 3 x9

subject to

x1 + x2 + x3 = 100 x4 + x5 + x6 = 50 x7 + x8 + x9 = 100 x1 + x4 + x7 = 150 x2 + x5 + x8 = 50 x3 + x6 + x9 = 50

and x1,x2,x3,x4,x5,x6,x7,x8,x9≥0;

The problem is converted to canonical form by adding slack, surplus and artificial variables as appropriate

1. As the constraint-1 is of type '=' we should add artificial variable A1

2. As the constraint-2 is of type '=' we should add artificial variable A2

3. As the constraint-3 is of type '=' we should add artificial variable A3

4. As the constraint-4 is of type '=' we should add artificial variable A4

5. As the constraint-5 is of type '=' we should add artificial variable A5

6. As the constraint-6 is of type '=' we should add artificial variable A6

After introducing artificial variables

Min Z = x1 + 2 x2 + 2 x3 + 4 x4 + 3 x5 + 4 x6 + 4 x7 + x8 + 3 x9 + M A1 + M A2 + M A3 + M A4 + M A5 + M A6

subject to

x1 + x2 + x3 + A1 = 100 x4 + x5 + x6 + A2 = 50 x7 + x8 + x9 + A3 = 100 x1 + x4 + x7 + A4 = 150 x2 + x5 + x8 + A5 = 50 x3 + x6 + x9 + A6 = 50

and x1,x2,x3,x4,x5,x6,x7,x8,x9,A1,A2,A3,A4,A5,A6≥0

Iteration-1		Cj	1	2	2	4	3	4	4	1	3	M	M	M	M	M	M
B	CB	XB	x1	x2	x3	x4	x5	x6	x7	x8	x9	A1	A2	A3	A4	A5	A6	MinRatio XB/x1
A1	M	100	(1)	1	1	0	0	0	0	0	0	1	0	0	0	0	0	100/1=100→
A2	M	50	0	0	0	1	1	1	0	0	0	0	1	0	0	0	0	---
A3	M	100	0	0	0	0	0	0	1	1	1	0	0	1	0	0	0	---
A4	M	150	1	0	0	1	0	0	1	0	0	0	0	0	1	0	0	150/1=150
A5	M	50	0	1	0	0	1	0	0	1	0	0	0	0	0	1	0	---
A6	M	50	0	0	1	0	0	1	0	0	1	0	0	0	0	0	1	---
Z=500M		Zj	2M	2M	2M	2M	2M	2M	2M	2M	2M	M	M	M	M	M	M
		Zj-Cj	2M-1↑	2M-2	2M-2	2M-4	2M-3	2M-4	2M-4	2M-1	2M-3	0	0	0	0	0	0

Positive maximum Zj-Cj is 2M-1 and its column index is 1. So, the entering variable is x1.

Minimum ratio is 100 and its row index is 1. So, the leaving basis variable is A1.

∴ The pivot element is 1.

Entering =x1, Departing =A1, Key Element =1

R1(new)=R1(old)

R2(new)=R2(old)

R3(new)=R3(old)

R4(new)=R4(old) - R1(new)

R5(new)=R5(old)

R6(new)=R6(old)

Iteration-2		Cj	1	2	2	4	3	4	4	1	3	M	M	M	M	M
B	CB	XB	x1	x2	x3	x4	x5	x6	x7	x8	x9	A2	A3	A4	A5	A6	MinRatio XB/x8
x1	1	100	1	1	1	0	0	0	0	0	0	0	0	0	0	0	---
A2	M	50	0	0	0	1	1	1	0	0	0	1	0	0	0	0	---
A3	M	100	0	0	0	0	0	0	1	1	1	0	1	0	0	0	100/1=100
A4	M	50	0	-1	-1	1	0	0	1	0	0	0	0	1	0	0	---
A5	M	50	0	1	0	0	1	0	0	(1)	0	0	0	0	1	0	50/1=50→
A6	M	50	0	0	1	0	0	1	0	0	1	0	0	0	0	1	---
Z=300M+100		Zj	1	1	1	2M	2M	2M	2M	2M	2M	M	M	M	M	M
		Zj-Cj	0	-1	-1	2M-4	2M-3	2M-4	2M-4	2M-1↑	2M-3	0	0	0	0	0

Positive maximum Zj-Cj is 2M-1 and its column index is 8. So, the entering variable is x8.

Minimum ratio is 50 and its row index is 5. So, the leaving basis variable is A5.

∴ The pivot element is 1.

Entering =x8, Departing =A5, Key Element =1

R5(new)=R5(old)

R1(new)=R1(old)

R2(new)=R2(old)

R3(new)=R3(old) - R5(new)

R4(new)=R4(old)

R6(new)=R6(old)

Iteration-3		Cj	1	2	2	4	3	4	4	1	3	M	M	M	M
B	CB	XB	x1	x2	x3	x4	x5	x6	x7	x8	x9	A2	A3	A4	A6	MinRatio XB/x9
x1	1	100	1	1	1	0	0	0	0	0	0	0	0	0	0	---
A2	M	50	0	0	0	1	1	1	0	0	0	1	0	0	0	---
A3	M	50	0	-1	0	0	-1	0	1	0	1	0	1	0	0	50/1=50
A4	M	50	0	-1	-1	1	0	0	1	0	0	0	0	1	0	---
x8	1	50	0	1	0	0	1	0	0	1	0	0	0	0	0	---
A6	M	50	0	0	1	0	0	1	0	0	(1)	0	0	0	1	50/1=50→
Z=200M+150		Zj	1	-2M+2	1	2M	1	2M	2M	1	2M	M	M	M	M
		Zj-Cj	0	-2M	-1	2M-4	-2	2M-4	2M-4	0	2M-3↑	0	0	0	0

Positive maximum Zj-Cj is 2M-3 and its column index is 9. So, the entering variable is x9.

Minimum ratio is 50 and its row index is 6. So, the leaving basis variable is A6.

∴ The pivot element is 1.

Entering =x9, Departing =A6, Key Element =1

R6(new)=R6(old)

R1(new)=R1(old)

R2(new)=R2(old)

R3(new)=R3(old) - R6(new)

R4(new)=R4(old)

R5(new)=R5(old)

Iteration-4		Cj	1	2	2	4	3	4	4	1	3	M	M	M
B	CB	XB	x1	x2	x3	x4	x5	x6	x7	x8	x9	A2	A3	A4	MinRatio XB/x4
x1	1	100	1	1	1	0	0	0	0	0	0	0	0	0	---
A2	M	50	0	0	0	1	1	1	0	0	0	1	0	0	50/1=50
A3	M	0	0	-1	-1	0	-1	-1	1	0	0	0	1	0	---
A4	M	50	0	-1	-1	(1)	0	0	1	0	0	0	0	1	50/1=50→
x8	1	50	0	1	0	0	1	0	0	1	0	0	0	0	---
x9	3	50	0	0	1	0	0	1	0	0	1	0	0	0	---
Z=100M+300		Zj	1	-2M+2	-2M+4	2M	1	3	2M	1	3	M	M	M
		Zj-Cj	0	-2M	-2M+2	2M-4↑	-2	-1	2M-4	0	0	0	0	0

Positive maximum Zj-Cj is 2M-4 and its column index is 4. So, the entering variable is x4.

Minimum ratio is 50 and its row index is 4. So, the leaving basis variable is A4.

∴ The pivot element is 1.

Entering =x4, Departing =A4, Key Element =1

R4(new)=R4(old)

R1(new)=R1(old)

R2(new)=R2(old) - R4(new)

R3(new)=R3(old)

R5(new)=R5(old)

R6(new)=R6(old)

Iteration-5		Cj	1	2	2	4	3	4	4	1	3	M	M
B	CB	XB	x1	x2	x3	x4	x5	x6	x7	x8	x9	A2	A3	MinRatio
x1	1	100	1	1	1	0	0	0	0	0	0	0	0
A2	M	0	0	1	1	0	1	1	-1	0	0	1	0
A3	M	0	0	-1	-1	0	-1	-1	1	0	0	0	1
x4	4	50	0	-1	-1	1	0	0	1	0	0	0	0
x8	1	50	0	1	0	0	1	0	0	1	0	0	0
x9	3	50	0	0	1	0	0	1	0	0	1	0	0
Z=500		Zj	1	-2	0	4	1	3	4	1	3	M	M
		Zj-Cj	0	-4	-2	0	-2	-1	0	0	0	0	0

Since all Zj-Cj≤0

Hence, optimal solution is arrived with value of variables as :
x1=100,x2=0,x3=0,x4=50,x5=0,x6=0,x7=0,x8=50,x9=50

Min Z=500

also the artificial variable A2 appears in the basis