METODE SIMPLEX

METODE SIMPLEX

Apabila suatu masalah Linear Programming hanya mengandung 2 variabel keputusan saja, maka akan dapat diselesaikan dengan metode grafik. Tetapi bila melibatkan lebih dari 2 variabel, maka metode grafik tidak dapat digunakan lagi, sehingga diperlukan metode simplex. Metode simplex merupakan suatu cara yang lazim dipakai untuk menentukan kombinasi optimal dari 3 atau lebih.

Contoh 1 :
Selesaikan dengan metode simplex !
Variabel keputusan :
X1 = Jumlah sepatu KOSOGO yang dibuat setiap hari
X2 = Jumlah sepatu KASAGA yang dibuat setiap hari
Fungsi tujuan :
Kontribusi laba : Zmaks = 3X1 + 5X2
Kendala :
2X1 ≤ 8 (batasan mesin-1)
3X2 ≤ 15 (batasan mesin-2)
6X1 + 5X2 ≤ 30 (batasan mesin-3)
X1 dan X2 ≥ 0

Jawab :
Langkah 1 : merubah formulasi pada fungsi tujuan dan kendala.
Fungsi tujuan Z = 3X1 + 5X2  Z – 3X1 – 5X2 = 0.
Kendala : 2X1 ≤ 8  2X1 + X3 = 8
3X2 ≤ 15  X2 + X4 = 15
6X1 + 5X2 ≤ 30  6X1 + 5X2 + X5 = 30

Langkah 2 :Menyusun persamaan2 di dalam tabel

Var. Dasar
Z
X1
X2
X3
X4
X5
Nk
Indeks
Z
1
-3
-5
0
0
0
0

X3
0
2
0
1
0
0
8
8/0=∞
X4
0
0
3
0
1
0
15
15/3=5
X5
0
6
5
0
0
1
30
30/5=6




Langkah 3 : Menentukan kolom kunci, yaitu kolom yang mempunyai nilai pada fungsi tujuan yang bernilai negatif dengan angka nilai terbesar. Dalam hal ini yaitu kolom X2.

Langkah 4 : Memilih baris kunci, yaitu baris yang memiliki angka indeks yang terkecil dan bukan negatif.
Perhitungan indeks = Nilai kolom Nk / Nilai kolom kunci

Langkah 5 : Merubah nilai2 baris kunci dengan nilai baris kunci dibagi dengan angka kunci.
0/3=0 3/3=1 0/3=0 1/3 0/3=0 15/3=5
[ 0 1 0 1/3 0, 5]

Dan juga gantilah variabel dasar pada baris kunci (X4) dengan variabel yang terdapat di bagian atas kolom kunci (X2).

Langkah 6 : merubah nilai2 selain pada baris kunci.
Baris baru = Baris lama – (koefisien pada kolom kunci) * Nilai baru baris kunci.
Baris pertama (Z) :
[ -3 -5 0 0 0, 0 ]
-5 [ 0 1 0 1/3 0, 5 ]

-3 0 0 5/3 0, 25  Nilai baru

Baris ke-2 :
[ 2 0 1 0 0, 8 ]
0 [ 0 1 0 1/3 0, 5 ]

2 0 1 0 0, 8  Nilai baru

Baris ke-4 :
[ 6 5 0 0 1, 30 ]
5 [ 0 1 0 1/3 0, 5 ]

6 0 0 -5/3 1 5  Nilai baru









Var. Dasar
Z
X1
X2
X3
X4
X5
Nk
Indek
Z
1
-3
-5
0
0
0
0

X3
0
2
0
1
0
0
8

X4
0
0
3
0
1
0
15

X5
0
6
5
0
0
1
30

Z
1
-3
0
0
5/3
0
25

X3
0
2
0
1
0
0
8
8/2=4
X2
0
0
1
0
1/3
0
5
5/0=∞
X5
0
6
0
0
-5/3
1
5
5/6

Langkah 7 : ulangi langkah 3 s.d. langkah 6 sehingga baris pertama (Z) tidak ada yang bernilai negatif.
Baris ke-4 : 6/6 0/6 0/0 -5/3/6 1/6, 5/6
[ 1 0 0 -5/18 1/6, 5/6 ]

Baris ke-1 :
[ -3 0 0 5/3 0, 25 ]
-3 [ 1 0 0 -5/18 1/6, 5/6 ]

0 0 0 5/6 1/2, 27½ Nilai baru

Baris ke-2 :
[ 2 0 1 0 0, 8 ]
2 [ 1 0 0 -5/18 1/6, 5/6 ]

0 0 1 5/9 -1/3, 6¹/3  Nilai baru

Baris ke-3 : tidak berubah karena nilai kolom kunci = 0

Var. Dasar
Z
X1
X2
X3
X4
X5
Nk
Z
1
0
0
0
5/6
1/2
27½
X3
0
0
0
1
5/9
-1/3
6¹/3
X2
0
0
1
0
1/3
0
5
X1
0
1
0
0
-5/18
1/6
5/6

Jadi X1=5/6, X2=5, Zmak=27½













Contoh 2 :
Selesaikan dengan metode Simplek !
Zmak = 40X1 + 30X2
Kendala :
2X1 + 3X2 ≤ 60
2X2 ≤ 30
2X1 + X2 ≤ 40
X1, X2 ≥ 0.
Jawab :
Zmak – 40X1 + 30X2 = 0
Kendala :
2X1 + 3X2 + X3 = 60
2X2 + X4 = 30
2X1 + X2 + X5 = 40
Var. Dasar
Z
X1
X2
X3
X4
X5
Nk
Indeks
Z
1
-40
-30
0
0
0
0

X3
0
2
3
1
0
0
60
60/2=30
X4
0
0
2
0
1
0
30
30/0=∞
X5
0
2
1
0
0
1
40
40/2=20

Nilai Baru Baris kunci :
2/2 1/2 0 0 0 1/2 40/2
[ 1 1/2 0 0 1/2 20 ]

Nilai baru baris ke-2 :
[ 2 3 1 0 0, 60 ]
2 [ 1 1/2 0 0 1/2, 20 ]

0 2 1 0 -1, 20

Nilai baru baris ke-3 :
[ 0 2 0 1 0, 30 ]
0 [ 1 1/2 0 0 1/2, 20 ]

0 2 0 1 0 30

Nilai baru baris ke-1 :
[ -40 -30 0 0 0, 0 ]
-40 [ 1 1/2 0 0 1/2, 20 ]

0 -10 0 0 20, 800



Var. Dasar
Z
X1
X2
X3
X4
X5
Nk
Indeks
Z
1
-40
-30
0
0
0
0

X3
0
2
3
1
0
0
60

X4
0
0
2
0
1
0
30

X5
0
2
1
0
0
1
40

Z
1
0
-10
0
0
20
800

X3
0
0
2
1
0
-1
20
20/2=10
X4
0
0
2
0
1
0
30
30/2=15
X1
0
1
1/2
0
0
1/2
20
20/½=40

Nilai Baru Baris kunci :
0/2 2/2 1/2 0/2 -1/2 20/2
[ 0 1 1/2 0 -1/2 10 ]

Nilai baru baris ke-1 :
[ 0 -10 0 0 20, 800 ]
-10[ 0 1 1/2 0 -1/2, 10 ]

0 0 5 0 15, 900

Nilai baru baris ke-3 :
[ 0 2 0 1 0, 30 ]
2 [ 0 1 1/2 0 -1/2, 10 ]

0 0 -1 1 1, 10

Nilai baru baris ke-4 :
[ 1 1/2 0 0 1/2, 20 ]
1/2 [ 0 1 1/2 0 -1/2, 10 ]

1 0 -1/4 0 3/4, 15

Var. Dasar
Z
X1
X2
X3
X4
X5
Nk
Z
1
0
0
5
0
15
900
X2
0
0
1
1/2
0
-1/2
10
X4
0
0
0
-1
1
1
10
X1
1
1
0
-1/4
0
3/4
15

Jadi X1 = 15, X2 = 10, Z = 900

 