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

 