METODE SIMPLEKS
Metode simpleks adalah salah satu teknik penyelesaian pemrograman linier selain menggunakan metode grafis. Metode simpleks diaplikasikan pada komputer dan metode tersebut sangat membantu untuk permasalahan pemrograman linier yang rumit karena menggunakan fungsi dan variabel yang banyak dan tak mampu diselesaikan oleh metode grafis.
Kita selesaikan contoh di bawah ini.
Min z = 21x1 + 18x2 + 15x3
Terhadap 90x1 + 20x2 + 40x3≥200 30x1 + 80x2 + 60x3≥180
Metode Simpleks, oleh Hotniar Siringoringo, 7
10x1 + 20x2 + 60x3≥150 x1, x2, x3≥0
semua kendala menggunakan pertidaksamaan ≥. Kendala dengan pertidaksamaan ≥ dapat diubah ke pertidaksamaan ≤ dengan mengalikan pertidaksamaan dengan -1. Bentuk umum PL di atas berubah menjadi:
Min z = 21x1 + 18x2 + 15x3
Terhadap -90x1 - 20x2 - 40x3≤-200 -30x1 - 80x2 - 60x3≤-180 -10x1 - 20x2 - 60x3≤-150 x1, x2, x3≥0
Semua fungsi kendala sudah dalam bentuk pertidaksamaan ≤, maka kita kita hanya perlu menambahkan variabel slack untuk mengubah bentuk umum ke bentuk baku/standar. Variabel slack akan berfungsi sebagai variabel basis awal.
Bentuk Baku/standar:
Min z = 21x1 + 18x2 + 15x3 + 0s1 + 0s2 + 0s3
Terhadap
|
-90x1 - 20x2 - 40x3 + s1 = -200
| ||||||
-30x1
|
- 80x2 - 60x3 + s2 = -180
| ||||||
-10x1
|
- 20x2 - 60x3 + s3 =
|
-150
| |||||
x1, x2, x3, s1, s2, s3 ≥ 0
| |||||||
Tabel di atas optimal tapi tidak layak (ingat, untuk fungsi tujuan minimisasi, tabel sudah optimal jika semua koefisien baris tujuan sudah negatif atau 0). Untuk membuat tabel tersebut layak, kita harus gunakan metode dual simpleks. Langkah-langkah penyelesaian simpleks menggunakan metode dual adalah:
1. Tentukan baris pivot. Baris pivot adalah baris dengan nilai kanan negatif terbesar. Jika negatif terbesar lebih dari satu, pilih salah satu sembarang.
2. Tentukan kolom pivot. Kolom pivot diperoleh dengan terlebih dahulu membagi nilai baris z dengan baris pivot. Dalam hal ini, semua nilai baris pivot dapat menjadi pembagi kecuali nilai 0. Kolom pivot adalah kolom dengan rasio pembagian mutlak terkecil. Jika rasio pembagian mutlak terkecil lebih dari satu, pilih salah satu secara sembarang.
3. Pembentukan tabel berikutnya sama dengan prosedur dalam primal simpleks.
Gunakan tabel awal simpleks di atas.
METODE DUA FASE
Dalam menyelesaiakan suatu persoalan dimana variabelnya lebih dari dua, juga menggunakan suatu metode yang bertahap. Metode ini disebut sebagai metode dua phase.
Pada dasarnya Metode dua fase (phase) sama seperti metode big M yang juga digunakan untuk menyelesaikan persoalan pemrograman linier yang memiliki bentuk yang tidak standar. Berikut ini adalah prosedur menggunakan metode dua fase.
1. Inisialisasi
Menambahkan variabel-variabel artifisal pada fungsi kendala yang memiliki bentuk tidak standar. Variabel artificial ini ditambahkan pada fungsi batasan yang pada mulanya memiliki tanda (³). Hal ini digunakan agar dapat mencari solusi basic fesibel awal.
2. Fase 1
Digunakan untuk mencari basic fesibel awal. Pada fase 1 memiliki langkah-langkah dimana tujuannya adalahm meminimalkan variabel artifisial ( Min Y= Xa)
s.t : Ax = b
X = 0
Pada fase pertama bertujuan untuk memperoleh penyelesaian yang optimum dari suatu permasalahan. Pada fase pertama fungsi tujuan selalu minimum variabel artificial, meskipun permasalahan yang ada adalah permasalahan yang maksimum. Dalam meyelesaiakan pada fase pertama, yaitu membuat nilai nol dulu pada variabel artifisial, kemudian melanjutkan iterasi seperti proses iterasi biasanya(dengan aturan meminimumkan). Berhenti ketika pada baris ke-0 bernilai £ 0.
Fase pertama dianggap telah selesai atau memperoleh penyelesaian yang optimal adalah apabila variabel artifisial adalah merupakan variabel basis. Sedangkan apabila variabel artifisial adalah variabel non basis, maka masalah dianggap tidak mempunyai penyelesaian yang optimal, sehingga harus dilanjutkan ke fase yang kedua.
Pada fase kedua, tujuannya sama seperti fase pertama, yaitu untuk mendapatkan penyelesaian yang optimal dari suatu permasalahan yang ada. Fase dua berhenti sesuai dengan tujuan awal permasalahan.
3. Fase 2
Digunakan untuk mencari solusi optimum pada permasalahan riil. Karena variabel artifisial bukan merupakan termasuk variabel dalam permasalahan riil, variabel artifisial tersebut dapat dihilangkan ( Xa=0). Bermula dari solusi BF yang didapatkan dari akhir fase 1. Pada fase 2 ini memiliki langkah-langkah sebagai berikut:
1. Fungsi tujuan bisa memaksimalkan dan juga bisa meminimalkan tergantung pada permasalahan yang dihadapi.
2. Menggunakan fungsi batasan (s.t) dari fase 1, melakukan proses iterasi seperti biasanya dan berhenti sesuai funsi obyektif awal.
Perhatikan kasus berikut:Tahap 1
Min A = A1 + A2
Terhadap: x1 + x2 + A1 = 90
0.001x1 + 0.002x2 + s1 = 0.9
0.09x1 + 0.6x2 -s2 + A2 = 27
0.02x1 + 0.06x2 + s3 = 4.5
x1, x2, s1, s2, s3 ≥ 0
karena A1 dan A2 berfungsi sebagai variabel basis pada solusi awal, maka koefisiennya pada fungsi tujuan harus sama dengan 0. untuk mencapai itu, gantikan nilai A1 dari fungsi kendala pertama (kendala yang memuat A1) dan nilai A2 dari fungsi kendala ketiga (kendala yang memuat A2).
Dari kendala -1 diperoleh :
A1 = 90 - x1 - x2
Metode Simpleks, oleh Hotniar Siringoringo, 5
Dari kendala-3 diperoleh:
A2 = 27 - 0.09x1 - 0.6x2 + s2 Maka fungsi tujuan tahap-1 menjadi:
Min A = (90 - x1 - x2) + (27 - 0.09x1 - 0.6x2 + s2) =117 - 1.09x1 - 1.6x2 + s2
Solusi awal
Tahap 2
Min z = 2 x1 + 5.5 x2
Terhadap:
|
tabel optimal tahap pertama
| |
Dari tabel optimal tahap 1 diperoleh:
| ||
X1
|
= 52.94 – 17/12s2
| |
X2
|
= 37.059 + 1.7542s2
| |
Maka fungsi tujuan adalah:
Min z = 2(52.94 – 17/12s2) + 5.5 (37.059 + 1.7542s2)
= -17/6s2 + 9.6481s2 + 309.7045 = 6.814767s2 + 309.7045
Tabel di atas sudah optimal. Solusi optimalnya adalah:
X1 = 52.94; x2 = 37.059; dan z = 309.7045
METODE BIG M
Metode Big M digunakan untuk menyelesaikan fungsi-fungsi dalam program linier yang tidak berada dalam bentuk baku atau standar ( bentuk standar adalah memaksimalkan Z sesuai dengan kendala fungsional dalam bentuk ≤ dan kendala nonegativitas di semua variabel) dan salah satu contoh masalah dalam kendala funsional adalah bila fungsi dalam bentuk-bentuk = atau ≥ atau bahkan ruas kanan yang negatif.
Masalah ini akan muncul bila kita akan mencari basis fesibel awal sehingga sebelum mencari variabel apa yang akan menjadi variabel nonbasis bahkan basis perlu dilakukan suatu teknik pendekatan khusus untuk mengubah fungsi tersebut ke bentuk baku atau standar. Teknik pendekatan khusus tersebut dengan cara menambahkan variabel dummy (variabel artifisial) pada kendala fungsional dan teknik ini disebut dengan teknik variabel artifisial.
Ada pun prosedur mendapatkan BF awal pada kendala fungsional adalah
a. Gunakan teknik variabel artifisial
Tambahkan variabel artifisal nonegatif pada fungsi kendala yang belum baku, dan anggaplah variabel artifial tersebut sebagai salah satu variabel slack
b. Tugaskan pinalty yang besar
Berilah nilai variabel artifisial dengan nilai > 0 sehingga koefisien variabel artifisial menjadi M (big m) secara simbolik yang menunjukkan bahwa variabel artifisial tersebut memiliki angka positif raksasa ( dan pengubahan atas variabel artifisial bernilai 0 (variabel nonbasis) dalam solusi optimal disebut metode big m).
Perhatikan contoh di bawah ini. Bentuk Umum :
Min. z = 4 x1 + x2 Terhadap: 3x1 + x2
= 3
4x1 + 3x2≥6 x1 + 2x2≤4
x1, x2 ≥ 0
Bentuk Baku:
Min. z = 4 x1 + x2 Terhadap: 3x1 + x2 = 3
4x1 + 3x2 - s1 = 6
Metode Simpleks, oleh Hotniar Siringoringo, 2
x1, x2, s1, s2≥0
Kendala 1 dan 2 tidak mempunyai slack variables, sehingga tidak ada variabel basis awal. Untuk berfungsi sebagai variabel basis awal, pada kendala 1 dan 2 ditambahkan masing-masing satu variabel buatan (artificial variable). Maka bentuk baku Big M-nya adalah:
Min. z = 4 x1 + x2 + MA1 + MA2
Terhadap: 3x1 + x2 + A1 = 3
4x1 + 3x2 - s1 + A2 = 6 x1 + 2x2 + s2 = 4
x1, x2, s1, s2 ≥ 0
1. Nilai A1 digantikan dari fungsi kendala pertama. A1 = 3 - 3x1 - x2
MA1 berubah menjadi M(3 - 3x1 - x2) 3M-3Mx1-Mx2
2. Nilai A2 digantikan dari fungsi kendala ketiga.
A2 = 6 - 4x1 - 3x2 + s1
MA2 berubah menjadi M(6 - 4x1 - 3x2 + s1) 6M- 4Mx1 - 3Mx2 + Ms1
3. Fungsi tujuan berubah menjadi
Min z = 4x1 + x2 + 3M-3Mx1-Mx2 +6M-4Mx1-3Mx2+Ms1
= (4 -7M)x1+(1 - 4M)x2 + Ms1 +9M
4. Tabel awal simpleks
Metode Simpleks, oleh Hotniar Siringoringo, 3
5. Perhitungan iterasinya sama dengan simpleks sebelumnya.
Metode Simpleks, oleh Hotniar Siringoringo, 4
