Homework SourseConsider the linear program Min z x12x2 3x3 x4 Constraints
Consider the linear program
Min z= -x1-2x2 -3x3 + x4
Constraints x1+2x2 +3x3 = 15
2x1+x2 +5x3 =20
x1+2x2 +x3 + x4 =10
Xj 0, j=1,2,3,4
At an iteration of the simplex, the inverse of the basis(B) is :
B-1 = 5/7 -3/7 0
-1/7 2/7 0
-9/7 4/7 1
a) Continue solving the problem after having identified the table of simplex associated with this B
b) If the right term of the third constraint turns 8 (x1+2x2 +x3 + x4 =8),
Does the solution of the optimal B obtained in a) still be possible?
What is the modification of the optimal value of the economic function?
Solution
if we
Consider the linear program
Min z= -x1-2x2 -3x3 + x4
Constraints x1+2x2 +3x3 = 15
2x1+x2 +5x3 =20
x1+2x2 +x3 + x4 =10
Xj 0, j=1,2,3,4
if we solve this we got optimal solution as below way,
Table #1
==========================================================
x1 x2 x3 x4 s1 s2 s3 s4 s5 s6 z
==========================================================
1 2 3 0 1 0 0 0 0 0 0 15
2 1 5 0 0 1 0 0 0 0 0 20
1 2 1 1 0 0 1 0 0 0 0 10
1 2 3 0 0 0 0 -1 0 0 0 15
2 1 5 0 0 0 0 0 -1 0 0 20
1 2 1 1 0 0 0 0 0 -1 0 10
1 2 3 -1 0 0 0 0 0 0 1 0
Table #2
==========================================================
x1 x2 x3 x4 s1 s2 s3 s4 s5 s6 z
==========================================================
-1 7 0 0 5 0 0 0 3 0 0 15
0 0 0 0 0 1 0 0 1 0 0 0
3 9 0 5 0 0 5 0 1 0 0 30
-1 7 0 0 0 0 0 -5 3 0 0 15
2 1 5 0 0 0 0 0 -1 0 0 20
3 9 0 5 0 0 0 0 1 -5 0 30
-1 7 0 -5 0 0 0 0 3 0 5 -60
Table #3
==========================================================
x1 x2 x3 x4 s1 s2 s3 s4 s5 s6 z
==========================================================
0 0 0 0 1 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0 1 0 0 0
6 0 0 7 0 0 7 9 -4 0 0 15
-1 7 0 0 0 0 0 -5 3 0 0 15
3 0 7 0 0 0 0 1 -2 0 0 25
6 0 0 7 0 0 0 9 -4 -7 0 15
0 0 0 -1 0 0 0 1 0 0 1 -15
Table #4
==========================================================
x1 x2 x3 x4 s1 s2 s3 s4 s5 s6 z
==========================================================
0 0 0 0 1 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0 1 0 0 0
6 0 0 7 -9 0 7 0 -4 0 0 15
-1 7 0 0 5 0 0 0 3 0 0 15
3 0 7 0 -1 0 0 0 -2 0 0 25
6 0 0 7 -9 0 0 0 -4 -7 0 15
0 0 0 -1 -1 0 0 0 0 0 1 -15
Table #5
==========================================================
x1 x2 x3 x4 s1 s2 s3 s4 s5 s6 z
==========================================================
0 0 0 0 1 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0 1 0 0 0
0 0 0 0 0 0 1 0 0 1 0 0
-1 7 0 0 5 0 0 0 3 0 0 15
3 0 7 0 -1 0 0 0 -2 0 0 25
6 0 0 7 -9 0 0 0 -4 -7 0 15
6 0 0 0 -16 0 0 0 -4 -7 7 -90
Table #6
==========================================================
x1 x2 x3 x4 s1 s2 s3 s4 s5 s6 z
==========================================================
0 0 0 0 1 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0 1 0 0 0
0 0 0 0 0 0 1 0 0 1 0 0
-1 7 0 0 0 0 0 -5 3 0 0 15
3 0 7 0 0 0 0 1 -2 0 0 25
6 0 0 7 0 0 0 9 -4 -7 0 15
6 0 0 0 0 0 0 16 -4 -7 7 -90
Table #7
==========================================================
x1 x2 x3 x4 s1 s2 s3 s4 s5 s6 z
==========================================================
0 0 0 0 1 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0 1 0 0 0
0 0 0 0 0 0 1 0 0 1 0 0
-1 7 0 0 0 0 0 -5 3 0 0 15
3 0 7 0 0 0 0 1 -2 0 0 25
6 0 0 7 0 0 7 9 -4 0 0 15
6 0 0 0 0 0 7 16 -4 0 7 -90
Table #8
==========================================================
x1 x2 x3 x4 s1 s2 s3 s4 s5 s6 z
==========================================================
0 0 0 0 1 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0 1 0 0 0
0 0 0 0 0 0 1 0 0 1 0 0
-1 7 0 0 0 -3 0 -5 0 0 0 15
3 0 7 0 0 2 0 1 0 0 0 25
6 0 0 7 0 4 7 9 0 0 0 15
6 0 0 0 0 4 7 16 0 0 7 -90
OPtimal solution:z = -90/7; x1 = 0, x2 = 15/7, x3 = 25/7, x4 = 15/7
B) If the right term of the third constraint turns 8 (x1+2x2 +x3 + x4 =8),
Does the solution of the optimal B obtained in a) still be possible:
yes we see how?
Consider the linear program
Min z= -x1-2x2 -3x3 + x4
Constraints x1+2x2 +3x3 = 15
2x1+x2 +5x3 =20
x1+2x2 +x3 + x4 =8
Xj 0, j=1,2,3,4
then the optimal solution is: see
Table #1
==========================================================
x1 x2 x3 x4 s1 s2 s3 s4 s5 s6 z
==========================================================
1 2 3 0 1 0 0 0 0 0 0 15
2 1 5 0 0 1 0 0 0 0 0 20
1 2 1 1 0 0 1 0 0 0 0 8
1 2 3 0 0 0 0 -1 0 0 0 15
2 1 5 0 0 0 0 0 -1 0 0 20
1 2 1 1 0 0 0 0 0 -1 0 8
1 2 3 -1 0 0 0 0 0 0 1 0
Table #2
==========================================================
x1 x2 x3 x4 s1 s2 s3 s4 s5 s6 z
==========================================================
-1 7 0 0 5 0 0 0 3 0 0 15
0 0 0 0 0 1 0 0 1 0 0 0
3 9 0 5 0 0 5 0 1 0 0 20
-1 7 0 0 0 0 0 -5 3 0 0 15
2 1 5 0 0 0 0 0 -1 0 0 20
3 9 0 5 0 0 0 0 1 -5 0 20
-1 7 0 -5 0 0 0 0 3 0 5 -60
Table #3
==========================================================
x1 x2 x3 x4 s1 s2 s3 s4 s5 s6 z
==========================================================
0 0 0 0 1 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0 1 0 0 0
6 0 0 7 0 0 7 9 -4 0 0 1
-1 7 0 0 0 0 0 -5 3 0 0 15
3 0 7 0 0 0 0 1 -2 0 0 25
6 0 0 7 0 0 0 9 -4 -7 0 1
0 0 0 -1 0 0 0 1 0 0 1 -15
Table #4
==========================================================
x1 x2 x3 x4 s1 s2 s3 s4 s5 s6 z
==========================================================
0 0 0 0 1 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0 1 0 0 0
6 0 0 7 -9 0 7 0 -4 0 0 1
-1 7 0 0 5 0 0 0 3 0 0 15
3 0 7 0 -1 0 0 0 -2 0 0 25
6 0 0 7 -9 0 0 0 -4 -7 0 1
0 0 0 -1 -1 0 0 0 0 0 1 -15
Table #5
==========================================================
x1 x2 x3 x4 s1 s2 s3 s4 s5 s6 z
==========================================================
0 0 0 0 1 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0 1 0 0 0
0 0 0 0 0 0 1 0 0 1 0 0
-1 7 0 0 5 0 0 0 3 0 0 15
3 0 7 0 -1 0 0 0 -2 0 0 25
6 0 0 7 -9 0 0 0 -4 -7 0 1
6 0 0 0 -16 0 0 0 -4 -7 7 -104
Table #6
==========================================================
x1 x2 x3 x4 s1 s2 s3 s4 s5 s6 z
==========================================================
0 0 0 0 1 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0 1 0 0 0
0 0 0 0 0 0 1 0 0 1 0 0
-1 7 0 0 0 0 0 -5 3 0 0 15
3 0 7 0 0 0 0 1 -2 0 0 25
6 0 0 7 0 0 0 9 -4 -7 0 1
6 0 0 0 0 0 0 16 -4 -7 7 -104
Table #7
==========================================================
x1 x2 x3 x4 s1 s2 s3 s4 s5 s6 z
==========================================================
0 0 0 0 1 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0 1 0 0 0
0 0 0 0 0 0 1 0 0 1 0 0
-1 7 0 0 0 0 0 -5 3 0 0 15
3 0 7 0 0 0 0 1 -2 0 0 25
6 0 0 7 0 0 7 9 -4 0 0 1
6 0 0 0 0 0 7 16 -4 0 7 -104
Table #8
==========================================================
x1 x2 x3 x4 s1 s2 s3 s4 s5 s6 z
==========================================================
0 0 0 0 1 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0 1 0 0 0
0 0 0 0 0 0 1 0 0 1 0 0
-1 7 0 0 0 -3 0 -5 0 0 0 15
3 0 7 0 0 2 0 1 0 0 0 25
6 0 0 7 0 4 7 9 0 0 0 1
6 0 0 0 0 4 7 16 0 0 7 -104
Optimal Solution: z = -104/7; x1 = 0, x2 = 15/7, x3 = 25/7, x4 = 1/7.
