Metode simpleks digunakan untuk memecahkan permasalahan
Program Linier dengan dua atau lebih variabel keputusan
Prosedur Metode Simpleks
v
Formulasi
Fungsi Tujuan dan Fungsi Kendala Dari Permasalahan PL
v
Mengkonversi
Bentuk Pertidaksamaan Dalam Fungsi Kendala Menjadi Bentuk Standar
v
Membuat
Table Simpleks Awal
v
Algoritma
metode simpleks
Ketentuan
yang perlu diperhatikan
Contoh
• Maksimumkan Z = 3X1 +
5X2
• Batasan (constrain)
(1)
|
2X1
|
|
8
|
(2)
|
3X2
|
|
15
|
(3)
|
6X1 + 5X2
|
|
30
|
Bagaimana menyelesaikan dengan metode
Simplex ?
Langkah-langkah metode simpleks
Langkah 1:
Mengubah fungsi tujuan dan batasan-batasan
• Fungsi tujuan
Z = 3X1 +
5X2 diubah menjadi Z
- 3X1 -
5X2 = 0.
• Fungsi batasan (diubah menjadi kesamaan & di + slack variabel)
(1) 2X1 8 menjadi
2X1 + X3 =
8
(2) 3X2 15 menjadi 3X2 + X4 =
15
(3) 6X1 +
5X2 30 menjadi 6X1 + 5X2 + X5= 30
Slack variabel
adalah variabel
tambahan yang mewakili
tingkat pengangguran
atau kapasitas yang merupakan batasan
Langkah 2:
Menyusun persamaan-persamaan di dalam tabel
Z = 3X1 + 5X2 diubah menjadi Z - 3X1 - 5X2 = 0.
(1) 2X1 8 menjadi
2X1 + X3 = 8
(2)
3X2 15 menjadi
3X2 + X4 = 15 (3) 6X1 + 5X2
30 menjadi 6X1 + 5X2
+ X5
= 30
1. Tabel simpleks yang pertama
Variabel
Dasar
|
Z
|
X1
|
X2
|
X3
|
X4
|
X5
|
NK
|
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
|
Langkah 3: Memilih kolom kunci
Jika suatu tabel sudah tidak memiliki nilai negatif pada baris fungsi tujuan, berarti
tabel itu tidak bisa dioptimalkan lagi (sudah optimal).
Langkah 4: Memilih baris kunci
Langkah 5: Mengubah nilai-nilai baris kunci
sehingga nilai-nilai kolom kunci (selain baris kunci) = 0
Baris baru = baris lama – (koefisien Angka kolom kunci) x nilai baris
baru
kunci
Masukkan nilai di atas ke dalam tabel,
sehingga tabel menjadi
seperti berikut
Iterasi 1
Langkah 7: Melanjutkan perbaikan

Variabel
Dasar
|
Z
|
X1
|
X2
|
X3
|
X4
|
X5
|
NK
|
Keterangan
(Indeks)
|
||||
Z
|
1
|
-3
|
0
|
0
|
5/3
|
0
|
25
|
|||||
X3
|
0
|
2
|
0
|
1
|
0
|
0
|
8
|
= 8/2 = 4
|
||||
X4
|
0
|
0
|
1
|
0
|
1/3
|
0
|
5
|
|||||
X5
|
0
|
6
|
0
|
0
|
-5/3
|
1
|
5
|
= 5/6
(minimum)
|
||||
Z
|
1
|
|||||||||||
X3
|
0
|
|||||||||||
X2
|
0
|
|||||||||||
X1
|
0
|
6/6
|
0
|
0
|
-5/18
|
1/6
|
5/6
|
|||||











Nilai baru
Baris ke-1
[-3
|
0
|
0
|
5/3
|
0,
|
25 ]
|
|||
(-3)
|
[ 1
|
0
|
0
|
-5/18
|
1/6,
|
5/6]
|
( - )
|
|
Nilai baru
|
=
|
[ 0
|
0
|
0
|
5/6
|
½,
|
271/2]
|
Baris ke-2 (batasan 1)
[ 2
|
0
|
1
|
0
|
0,
|
8 ]
|
|||
(2)
|
[ 1
|
0
|
0
|
-5/18
|
1/6,
|
5/6]
|
( - )
|
|
Nilai baru
|
=
|
0
|
0
|
1
|
5/9
|
-1/3,
|
61/3]
|
Baris ke-3 tidak
berubah karena nilai
pada
kolom kunci = 0
[ 0
|
1
|
0
|
1/3
|
0,
|
5 ]
|
|||
(0)
|
[ 1
|
0
|
0
|
-5/18
|
1/6,
|
5/6]
|
( - )
|
|
Nilai baru
|
=
|
0
|
1
|
0
|
1/3
|
0,
|
5]
|
Tabel simpleks final hasil perubahan
Variabel
Dasar
|
Z
|
X1
|
X2
|
X3
|
X4
|
X5
|
NK
|
Z
|
1
|
0
|
0
|
0
|
5/6
|
½
|
271/2
|
X3
|
0
|
0
|
0
|
1
|
5/9
|
-1/3
|
61/3
|
X2
|
0
|
0
|
1
|
0
|
1/3
|
0
|
5
|
X1
|
0
|
1
|
0
|
0
|
-5/18
|
1/6
|
5/6
|
Baris pertama (Z) tidak ada lagi yang bernilai negatif. Sehingga tabel tidak
dapat dioptimalkan lagi dan tabel tersebut merupakan hasil optimal
|
Dari tabel final didapat
X1 = 5/6
X2 = 5
Zmaksimum = 271/2
Ok.. Terima Kasih atas Postingnya !!!.....
BalasHapus