PEMROGRAMAN LINIER Metode Simpleks
Metode Simpleks Metode simpleks digunakan untuk memecahkan permasalahan PL dengan dua atau lebih variabel keputusan.
Prosedur Metode Simpleks: Kasus Maksimisasi a.
Formulasi Fungsi Tujuan dan Fungsi Kendala Dari Permasalahan PL Maksimumkan : 7X1 + 5X2 Dengan kendala : 4X1 + 3X2 ≤ 240 2 X1 + X2 ≤ 100 Xi ≥ 0, i = 1,2
b. Mengkonversi Bentuk Pertidaksamaan Dalam Fungsi Kendala Menjadi Bentuk Standar Ada tiga bentuk fungsi kendala: ≤, ≥, dan =. Konversi fungsi kendala bertanda ≤ menjadi bentuk standar dilakukan dengan menambahkan slack variable pada fungsi kendala tersebut. Slack variable merepresentasikan sumber daya yang mengganggur pada suatu fungsi kendala. Penambahan slack variable dimaksudkan agar pada fungsi kendala tersebut diperoleh solusi fisibel awal (initial feasible solution, sama dengan titik origin pada grafik).
4X1 + 3X2 + S1 = 240 Jika X1 = X2 = 0 (titik origin pada grafik) maka S1= 240 Dengan demikian, formulasi dalam bentuk standar dari permasalahan yang dibahas: Maksimumkan: 7 X1 + 5 X2 + 0 S1 + 0S2 Dengan kendala : 4 X1 + 3 X2 + S1 + 0 S2 = 240 2 X1 + X2 + 0 S1 + S2 =100 Xi , S1 ≥ 0, i = 1, 2
c. Membuat Table Simpleks Awal C Z SXJJ
-
1212
CJ
Basic Variable
7
5
0
0
X1
X2
S1
S2
Right Hand Side
0
S1
4
3
1
0
240
0
S2
2
1
0
1
100
ZJ
0
0
0
0
0
CJ - ZJ
7
5
0
0
Pada dasarnya, semua angka pada formulasi diplotting dalam tabel simpleks awal. Ada dua macam variabel : Variabel Basis (Basic Variable) dan Variabel Non Basis (Non Basic Variable). CJ menotasikan profit per unit (untuk permasalahan maksimisasi) dari masing-masing variabel dalam formulasi. Baris ZJ berisikan angka gross profit (laba kotor). Untuk kolom j, ZJ ditentukan dari jumlah perkalian antara profit per unit variabel basis dan angka pada kolom j. Baris CJ - ZJ disebut baris net profit yang mengindikasikan besarnya net profit tambahan yang akan diperoleh jika variabel pada kolom menjadi variabel basis pada iterasi berikutnya.
d.
Algoritma metode simpleks dengan mengaplikasikan lima langkah berikut ini:
Langkah 1: menentukan variabel kolom yang akan masuk basis Variabel kolom mana yang akan dipilih untuk menggantikan variabel basis pada iterasi berikutnya ditentukan berdasarkan nilai CJ - ZJ terbesar (untuk problem maksimisasi). Selanjutnya, kolom terpilih disebut dengan kolom pivot.
C Z SXJJ
-
1212
7
5
0
0
X1
X2
S1
S2
Right Hand Side
CJ
Basic Variable
0
S1
4
3
1
0
240
0
S2
2
1
0
1
100
ZJ
0
0
0
0
0
CJ - ZJ
7
5
0
0
Langkah 2: menentukan variabel yang akan keluar basis variabel basis yang akan keluar basis pada iterasi berikutnya berdasarkan atas nilai rasio antara Right Hand Side dan angka pada kolom pivot pada Langkah 1. Baris variabel basis yang memiliki nilai rasio dengan angka nonnegatif (positif) terkecil dipilih sebagai baris yang akan digantikan. Baris variabel basis ini disebut baris pivot.
C Z SXJJ
Variabel Basis S1
X1 4
RHS Rasio 240 60
S2
2
100
-
50
1212
CJ
Basic SX Variable
0 0
S1 S2
4 2
3 1
1 0
0 1
Right Hand Side 240 100
ZJ
0
0
0
0
0
CJ - ZJ
7
5
0
0
121
7
5
0
0
X1
X2
S1
S2
Angka pada perpotongan antara kolom pivot dan baris pivot disebut dengan angka pivot.
Langkah 3: menentukan angka baru untuk baris pivot Perhitungan angka baru untuk baris pivot pada iterasi berikutnya: membagi setiap angka pada baris pivot dengan angka pivot, atau
Langkah 4: menentukan angka baru untuk baris lainnya Perhitungan angka baru pada baris selain baris pivot pada iterasi berikutnya: Angka baru = angka pada baris lama – [(angka diatas atau dibawah angka pivot) * (angka baru baris pivot)],
atau
X1
X2
S1
S2
RHS
Angka Lama (1)
2
1
0
1
100
Angka Pivot (2)
2
2
2
2
2
Angka Baru Untuk Baris Pivot (1:2)
1
½
0
½
50
SX1212
Keterangan
Langkah 5: menghitung dan - dan mengevaluasi apakah tabel simpleks memberikan solusi optimal Perhitungan dan - dilakukan dengan cara yang telah digunakan sebelumnya. Pada problem maksimisasi, jika semua - bernilai nol atau negatif (atau-≤ 0) maka solusi optimal telah tercapai. Sebaliknya, jika masih ada kolom dengan-≥ 0 perhitungan masih harus dilanjutkan dan dimulai dari Langkah 1.
Interpretasi Tabel Optimal
Solusi Optimal Interpretasi dari solusi optimal: fungsi tujuan akan optimal jika perusahaan memproduksi 30 unit meja dan 40 unit kursi dan besarnya total profit yang diperoleh dari aktivitas yang menghasilkan kombinasi meja-kursi tersebut adalah 410. Informasi Tentang Resources Informasi tentang resources dapat diketahui dari nilai slack variable (dan juga surplus variable) pada tabel optimal.
Tingkat Substitusi Koefisien negatif mengindikasikan tambahan variabel kolom akan menyebabkan variabel baris meningkat sebesar nilai ab-solut koefisien tersebut; dan Koefisien positif mengindikasikan tambahan variabel kolom akan menyebabkan variabel baris berkurang sebesar nilai ab-solut koefisien tersebut.
Baris Net Profit pada tabel optimal baris ini memberikan informasi tentang shadow price atau opportunity cost dari resources yang dimiliki. Implikasi dari opportunity cost/shadow price ini secara praktikal adalah biaya pengadaan tambahan resources harus tidak melebihi opportunity cost/shadow price.
