Metode Simpleks
dalam linear programing
sumber :
Pangestu Subagyo
[Link]. Zunaidah. MSi
Metode simpleks
• Merupakan suatu cara yang lazim dipakai
untuk menentukan kombinasi optimal dari 2
variabel atau lebih.
• Mis: Z max = 3X1 + 5X2
• STC 2X1 ≤ 8
3X2 ≤ 15
6X1 + 5X2 ≤ 30
X1, X2 ≥ 0
[Link]. Zunaidah. MSi
Langkah-langkah metode simpleks
1. Mengubah fungsi tujuan dan batasan-batasan
2. Menyusun persamaan-persamaan di dalam tabel
3. Memilih kolom kunci
4. Memilih baris kunci
5. Mengubah nilai-nilai baris kunci
6. Mengubah nilai-nilai selain pada baris kunci
7. Melanjutkan perbaikan-perbaikan/perubahan-
perubahan. Perubahan baru berhenti setelah pada
baris pertama (fungsi tujuan) tidak ada yang bernilai
negatif.
[Link]. Zunaidah. MSi
1. Mengubah fungsi tujuan dan
batasan-batasan
• Fungsi tujuan diubah menjadi fungsi implisit
• Semua batasan harus diubah menjadi kesamaan, caranya dgn
menambah slack variabel ( variabel tambahan yg mewakili
tingkat pengangguran atau kapasitas yg merupakan batasan)
• Fungsi tujuan: Maksimumkan Z – 3X1 – 5X2
• Batasan-batasan: (1) 2X1 + X3 = 8
(2) 3X2 +X4 = 15
(3)6X1 + 5X2 +X5 = 30
[Link]. Zunaidah. MSi
2. Menyusun persamaan-persamaan di
dalam tabel
Variabel Z X1 X2 X3 X4 X5 NK
Dasar
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
[Link]. Zunaidah. MSi
3. Memilih kolom kunci
• Kolom Kunci adalah kolom yang merupakan dasar untuk
mengubah tabel. Pilihlah kolom yang mempunyai nilai yang
pada garis fungsi tujuan yang bernilai negatif dengan angka
terbesar
[Link]. Zunaidah. MSi
Variabel Z X1 X2 X3 X4 X5 NK
Dasar
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
[Link]. Zunaidah. MSi
4. Memilih baris kunci
• Baris kunci adalah baris yang merupakan
dasar untuk mengubah tabel. Untuk itu
terlebih dahulu carilah indeks tiap-tiap baris
dengan cara membagi nilai-nilai pada kolom
NK dengan nilai yang sebaris pada kolom kunci
• Indeks = Nilai Kolom NK
Nilai Kolom Kunci
[Link]. Zunaidah. MSi
Variabel Z X1 X2 X3 X4 X5 NK Keterangan
Dasar
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 min
X5 0 6 5 0 0 1 30 30/5=6
[Link]. Zunaidah. MSi
Variabel Z X1 X2 X3 X4 X5 NK
Dasar
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
[Link]. Zunaidah. MSi
5. Mengubah nilai-nilai baris kunci
• Nilai baris kunci diubah dengan cara
membaginya dengan angka kunci
0/3 =0; 3/3=1; 0/3=0; 1/3 =1/3; 0 ; 15/3
[Link]. Zunaidah. MSi
Variabel Z X1 X2 X3 X4 X5 NK
Dasar
Z 1
X3 0
X4
X2 0 0 1 0 1/3 0 5
X5 0
[Link]. Zunaidah. MSi
6. Mengubah nilai-nilai selain pada baris
kunci
• Nilai-nilai baris yang lain, selain pada baris kunci
dapat diisi dengan rumus:
Baris baru = baris lama – (koefisien pada kolom kunci) X nilai baru baris kunci
Untuk data diatas, nilai baru baris pertama (Z) sebagai berikut:
-3 -5 0 0 0, 0
(-5) 0 1 0 1/3 0, 5 (-)
Nilai baru = -3 0 0 5/3 0, 25
[Link]. Zunaidah. MSi
• Baris ke-2 (batasan 1)
2 0 1 0 0, 8
0 0 1 0 1/3 0, 5 (-)
Nilai baru = 2 0 1 0 0, 8
• Baris ke-4 (batasan 3)
6 5 0 0 1, 30
5 0 1 0 1/3 0, 5 (-)
Nilai baru = 6 0 0 -5/3 1, 5
[Link]. Zunaidah. MSi
Variabel Z X1 X2 X3 X4 X5 NK
Dasar
Z 1 -3 0 0 5/3 0 25
X3 0 2 0 1 0 0 8
X2 0 0 1 0 1/3 0 5
X5 0 6 0 0 -5/3 1 5
[Link]. Zunaidah. MSi
7. Melanjutkan perbaikan-perbaikan/
perubahan-perubahan
• Ulangilah langkah-langkah perbaikan mulai
langkah 3 sampai langkah ke-6 untuk
memperbaiki tabel-tabel yang telah
diubah/diperbaiki nilainya. Perubahan baru
berhenti setelah pada baris pertama (fungsi
tujuan) tidak ada yang bernilai negatif
[Link]. Zunaidah. MSi
Variabel Z X1 X2 X3 X4 X5 NK
Dasar
Z 1 -3 0 0 5/3 0 25
X3 0 2 0 1 0 0 8
X2 0 0 1 0 1/3 0 5
X5 0 6 0 0 -5/3 1 5
[Link]. Zunaidah. MSi
Variabel Z X1 X2 X3 X4 X5 NK
Dasar
Z 1
X3 0
X2 0
X1 0 1 0 0 -5/18 1/6 5/6
[Link]. Zunaidah. MSi
• 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 1/2, 27 1/2
• Baris ke-2
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, 6 1/3
Baris ke-3 tidak berubah, karena nilai pada kolom kunci=0
[Link]. Zunaidah. MSi
Variabel Z X1 X2 X3 X4 X5 NK
Dasar
Z 1 0 0 0 5/6 1/2 27 1/2
X3 0 0 0 1 5/9 -1/3 6 1/3
X2 0 0 1 0 1/3 0 5
X1 0 1 0 0 -5/18 1/6 5/6
[Link]. Zunaidah. MSi
• Kalau dilihat baris pertama (Z) pada tabel
diatas, tidak ada lagi yang bernilai negatif,
semuanya positif. Berarti tabel itu tidak dapat
dioptimalkan lagi, sehingga hasil dari tabel
tersebut sudah merupakan hasil optimal.
• X1 = 5/6, sehingga I1 = 5/6 lusin setiap hari
X2 = 5, sehingga I2 = 5 lusin setiap hari
Z maksimum = 27 ½, artinya laba yang akan
diperoleh = Rp 275.000,- setiap hari.
[Link]. Zunaidah. MSi