1
Simplex Method
.
.
.
-:
Maximize Z = 1.5 x1 + 1.8 x2
3 x1 + 2 x2 15000
)(2
) (3
x1 + 2 x2 1000
) (4
4000
) (5
x2 4500
) (6
x1 0
) (7
x2 0
x1
:
- :
) (1
)(2
) (3
) (4
) (5
Maximize Z = 1.5 x1 + 1.8 x2
3 x1 + 2 x2 15000
x1 + 2 x2 1000
4000
x1
x2 4500
x1 0 x2 0
- :
) ( ) ( ) ( ) (
Slack Variable
= 15000
= 10000
x5 = 4000
x6 = 4500
3 x1 + 2 x2 + x 3
x1 + 2 x2 +
x4
x1 +
x2 +
= X3
= X4
= X5 .
= X6 .
- :
) (
- :
)(1
)(2
)(3
)(4
)(5
Maximize 1.5 X1 + 1.8 X2 + OX3 + OX4 + OX5 + OX6
Subject 3X1 + 2X2 + X3 + OX4 + OX5 + OX6 = 15000
X1 + 2X2 + OX3 + X4 + OX5 + OX6 = 10000
X1 + OX2 + OX3 + OX4 + X5 + OX6 = 4000
OX1 + X2 + OX3 + OX4 + OX5 + X6 = 4500
- :
.
) ( 1
1.5 1.8
X6
X5
X4
X3
X2
X1
) (
) ( X1 , X2 )
(
) ( 4 2
. 4 4
.
) (2
1.8
1.5
X6
X5
X4
X3
X2
X1
0
0
0
1
0
0
1
0
0
1
0
0
1
0
0
0
2
2
0
1
3
1
1
0
15000
10000
4000
4500
- :
.
) (1 ) (5 ) (
.
.
.
-:
) ( Zj )
( ) ( ZjCj
) . ( 3
0
1.8
1.5
X6
X5
X4
X3
X2
X1
)(q
)(cj
)( A
Zj
ZjCj
:
Initial Solution
.
. .
:
X1 = 0 , X2 = 0
Z=0
X3 = 15000
X4 = 10000
X5 = 4000
X6 = 4500
)- : ( 4
0
X6
0
0
0
1
0
0
0
X5
0
0
1
0
0
0
0
X4
0
1
0
0
0
0
0
X3
1
0
0
0
0
0
1.8
X2
2
2
0
1
0
1.8
1.5
X1
3
1
1
0
0
1.5
Cj
0
0
0
0
X3 15000
X4 10000
X5 4000
X6 4000
Zj
0
ZjCj
X1 = 0 , X2 - :
) ( ) (X3 ) ( X3 . .
) ( ) (X4 = .
- :Zj(q) = ( 1500*0 ) + ( 10000*0 ) + ( 4000*0) + ( 4500*0) = 0
Zj ( X1) = ( 3*0 ) + (1* 0 ) + ( 1* 0 ) + ( 0* 0 ) = 0
Zj (X2) = ( 2* 0 ) + ( 2* 0 ) + ( 0 * 0 ) + ( 1 * 0 ) = 0
Zj (X3) = 0
Zj (X4) = 0
Zj (X5) = 0
Zj (X6) = 0
- :( Cj Zj )x1 = 1.5 0 = 1.5
( Cj Zj )x2 = 1.8 0 = 1.8
( Cj Zj )x3 = 0 0 = 0
( Cj Zj ) x4 = 0 0 = 0
( Cj Zj ) x5 = 0 0 = 0
( Cj Zj ) x6 = 0 0 = 0
- :
) (
.
- :
First Basic Solution
1.
.
- :
Optimum Column Pivot Column .
) (X2 ) (X2
.
- :
15000
=
2
10000
= 5000
=
2
4000
=
=
0
4500
= 4500
=
1
= 7500
= ) ( 4500
) ( X6
) ( X6 ) ( X2 )(X5) , (X4) , ( X3
) ( .
2
:
pivot
) (1 :
0
0
0
1
;=0
;=0
= 0; = 1
1
1
1
1
0
;=0
1
1
;=1
1
4500
; = 4500
1
)(5
0
X6
0
X5
0
X4
0
X3
1.8
X2
X1
4500
X2
1.8
.3.
) (X5) , (X4) , (X3 - :
)( X3
15000 2 * 4500 = 6000
32*0=3
22*1=0
12*0=1
02*0=0
02*0=0
0 2 * 1 = -2
) ( X4
10000 2 * 4500 = 1000
12*0=1
22*1=0
02*0=0
12*0=1
02*0=0
0 2 * 1 = -2
) ( X6
4000 0 * 4500 = 4000
10*0=1
00*1=0
00*0=0
00*0=0
10*0=1
00*1=0
) (X2 ) : ( 6
0
X6
0
X5
0
X4
0
X3
1.8
X2
1.5
X1
Cj
-2
-2
0
1
1.8
1.8
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
1.8
0
1
1
0
0
1.5
6000
1000
X3
X4
X5
X2
0
0
1.8
4000
4500
8100
Zj
ZjCj
) ( 6.1
) ( 4500 ) (X2 ) ( 8100
) ( X1
.
Second Basic solution
) ( X1 ) ( X4 ) ( X1
) (X5) , (X3 ) , (X2 ) (7
0
X6
4
0
X5
0
X4
0
X3
1.8
X2
1.5
X1
Cj
-3
3000
X3
-2
1000
X1
1.5
2
1
-1.2
1.2
1
0
0
-1
0
1.5
0
0
0
0
1
1.8
0
0
1.5
3000
4500
9600
X5
X2
0
1.8
-1.5
Zj
ZjCj
) (7
) (1000 ) (4500) . (X1 ) (X2 ) (9600
) . (X6
.
Third Basic Solution
) (x6
) . (x3 ) ( x3 ) (X6
) (X2) , (X5) , (X1 ) (8
:
10
) (8
0
X6
0
X5
0
0
0
0
0
X4
0
X3
3
4
1
2
1
2
3
4
1
4
1
2
1
2
1
4
0.6
-0.6
0.3
-0.3
1.8
X2
1.5
X1
Cj
750
X6
2500
X1
1.5
1500
X5
750
X2
1.8
1.8
0
1.5
0
10500
Zj
ZjCj
- : ) (8
) (2500 X1 ) ( 3750 X2 )(10500
:
X1=2500
X2=3750
X5=1500
X6=750
Z=10500