Danang Triagus Setiyawan ST.,MT
• Metode ini didasari atas gagasan pergerakan dari satu titik ekstrim ke titik ekstrim yang lain pada satu susunan konvek yang dibentuk oleh set fungsi kendala dan kondisi non-negativitas. • Untuk mendapatkan solusi optimal dalam pemecahan permasalahan, maka perlu dilakukan perbaikan solusi layak basis. Cara yang digunakan adalah menggantikan variabel basis dengan variabel basis baru yang berasal dari variabel non-basis, sehingga didapat solusi layak basis yang baik nilai fungsi tujuannya.
Bentuk standar model PL mempunyai ciri sebagai berikut: • Fungsi tujuan berbentuk maksimasi atau minimasi • Semua fungsi kendala dinyatakan sebagai persamaan • Semua variabel keputusan tidak negatif (nol atau positif) • Konstanta ruas kanan tidak negatif (nol atau positif)
• Fungsi kendala yang berbentuk ketidaksamaan, tanda ketidaksamaan atau harus diubah menjadi persamaan (=). • Untuk mengubahnya perlu ditambahkan variabel baru yang disebut dengan variabel tambahan. • Variabel tambahan untuk fungsi ketidaksamaan bertanda akan ditambahkan variabel slack (kelonggaran), misal: x1 + x2 10
• Fungsi ketidaksamaan tersebut akan diubah menjadi fungsi persamaan dengan menambahkan variabel slack, s1
• Sehingga didapatkan fungsi: x1 + x2 + si = 10, dimana si 0
• Untuk fungsi ketidaksamaan bertanda , akan ditambahkan dengan variabel yang disebut variabel surplus (kelebihan), misal: 20 x1 + 12 x2 180 • Agar tanda ketidaksamaan menjadi =, maka perlu dikurangi dengan variabel surplus, si, sehingga didapatkan fungsi: • 20 x1 + 12 x2 - si = 180, dimana si 0
• Dalam permasalahan ini dikatakan bahwa variabel slack dan surplus merupakan bagian dari permasalahan asal, seperti halnya variabel keputusan dalam model PL. • Variabel tambahan tersebut bernilai tidak negatif (nol atau positif).
Proses algoritma pada permasalahan PL maksimasi yang standar dapat dilakukan sebagai berikut: • Dimulai dengan solusi layak basis awal dalam sistem kanonik • Diperiksa apakah solusi layak basis sudah optimal atau belum? Bila koefisien fungsi tujuan relatif (cj’) dari semua variabel non-basis bernilai nol atau negatif, maka solusi sudah optimal, stop. Bila belum dilanjutkan ke langkah 3. • Memilih variabel non-basis yang akan masuk basis. Dalam pemilihan ini aturan yang digunakan adalah variabel nonbasis yang mempunyai koefisien fungsi tujuan relatif (cj’) positif terbesar. Kolom yang behubungan dengan variabel non-basis yang akan masuk basis disebut kolom pivot.
• Mementukan variabel basis yang akan keluar basis untuk digantikan oleh variabel basis baru. Cara yang digunakan adalah dengan melihat rasio dari elemen ruas kanan dengan elemen dalam kolom pivot. Aturan yang digunakan adalah variabel basis yang mempunyai rasio positif terkecil. • Tentukan sistem kanonik lain dari solusi layak basis dengan operasi pivot, yaitu elemen pivot (elemen dalam kolom pivot yang terdapat pada baris variabel basis yang keluar basis) menjadi 1, dan mengenolkan elemen lain dalam kolom pivot. Selanjutnya kembali ke langkah 2.
Contoh: Maks. Z = 3 x1 + 2 x2 Dengan memperhatikan kendala: x1 + x2 15 2 x1 + x2 28 x1 + 2x2 20 dengan x1, x2 0
• Untuk memecahkan permasalahan di atas model PL tersebut diubah terlebih dahulu dalam bentuk standar. • Agar menjadi bentuk standar tiap fungsi kendala, tanda ketidaksamaan diubah menjadi persamaan (=) dengan menambahkan variabel slack (si). • Dalam fungsi tujuan, koefisien fungsi tujuan untuk variabel slack (si) adalah nol, sehingga bentuk standar permasalahan di atas adalah:
• Maks. Z = 3 x1 + 2 x2 Dengan memperhatikan kendala: x 1 + x2 + s 1 = 15 2 x1 + x2 + s2 = 28 x1 + 2x2 + s3 = 20 dengan x1, x2 0 s1; s2;s3 0
• Bentuk standar dari permasalahan di atas sudah dalam sistem kanonik yang dapat dilihat dengan adanya variabel dalam fungsi kendala yang dapat digunakan sebagai variabel basis, yaitu variabel s1,s2,s3.
Semua (zj, cj ) < 0 kondisi sudah optimal Solusi optimal x1 = 13 x2 = 2 Zmax = 43
