Metode Simpleks dengan Big M dan 2 Phase
Metode Simpleks Vs. Simpleks Big-M Perbedaan metode simpleks dengan metode simpleks Big-M adalah munculnya variabel artificial (variabel buatan), sedangkan metode atau langkah-langkahnya sama.
Saat membuat bentuk standar : Jika kendala bertanda “=“, tambahkan ruas kiri satu variabel tambahan berupa variabel artifisial (var. dummy => meaningless) Jika kendala bertanda “>”, kurangkan ruas kiri dgn variabel surplus dan tambahkan juga ruas kiri dgn variabel dummy
Contoh Min Cost Subject to (s/t)
Z = 5X1 + 6X2 X1 + X2 X1 X2 X1 ; X2 > 0
Min Cost Subject to (s/t)
Z = 5X1 + 6X2 + 0S1 + 0S2 + MA1 + MA2 X1 + X2 + A1 = 1000 X1 + S1 < 300 X2 – S2 + A2 > 150 X1 ; X2 ; A1 ; A2 : S1 ; S2 > 0
= 1000 < 300 > 150
Contoh Soal Sebuah perusahaan agroindustri kedelai hendak memproduksi 2 buah produk, yaitu produk susu kedelai bubuk dan susu kedelai cair, yang masing-masing memerlukan biaya produksi per unitnya sebesar Rp.12.000,00 dan Rp.24.000,00. Kedua produk tersebut harus diproses melalui dua buah mesin, yaitu mesin penggiling kedelai dengan kapasitas sebesar minimal 4 jam orang (man hours) dan mesin pengolah susu kedelai dengan kapasitas paling sedikit 5 jam orang (man hours). Setiap unit produk susu kedelai cair mula-mula diproses pada mesin penggiling selama 1 jam orang, lalu pada mesin pengolah susu kedelai selama 4 jam orang. Sedangkan setiap unit produk susu kedelai bubuk diproses pada mesin penggiling dan mesin pengolah susu kedelai masing-masing 3 jam orang. Buatlah formulasi primal dan dual dari persoalan diatas dan hitunglah berapa lama kombinasi penggunaan mesin penggiling dan mesin pengolah susu kedelai untuk memproduksi produk susu kedelai cair dan susu kedelai bubuk yang optimal sehingga biaya produksi yang dikeluarkan perusahaan menjadi minimal ?
Langkah Penyelesaian Metode Simpleks Big - M 1. Ubahlah tanda pertidaksamaan “>” yang ada pada fungsi kendala menjadi tanda “=“, yaitu dengan memasukkan variabel surplus yang bernilai negatif dan variabel artifisial yang bernilai positif (-S dan +A) 2. Masukkan / tambahkan pula variabel-variabel surplus dan artifisial ke dalam fungsi tujuan, dimana koefisien untuk var. surplus = 0 dan koefisien var. artifiasial = M ( M a/d konstanta yang nilainya sangat besar sekali, tapi berhingga, misalnya ribuan, puluhan ribu,dst) 3. Semua variabel tidak boleh negatif 4. Hasil langkah 1 s.d 3, masukkan ke dalam tabel M-Besar
5. Tentukanlah variabel-variabel dasarnya (pada contoh soal A1 dan A2 merupakan variabel dasar dengan koefisien M)
6. Hitunglah nilai-nilai pada baris Z dengan menggunakan perkalian matriks 7. Hitung pula nilai c-z 8. Tentukan variabel masuk (entering variabel), yaitu dengan memilih nilai c-z yang terkecil (bila pada fungsi tujuan a/d untuk minimisasi biaya) Langkah 9 s.d 18 sama dengan penyelesaian metode simpleks yang sebelumnya 9. Tentukanlah kolom kunci, yaitu kolom-kolom yang sejajar dengan variabel masuk
10. Hitunglah nilai rasio masing-masing, dengan rumus : Rasio = ( nilai kanan / kolom kunci ) 11. Tentukan varibel keluar (leaving variabel), yaitu dengan cara memilih nilai rasio yang terkecil dan positif. 12. Tentukan baris kunci 13. Angka yang terdapat pada perpotongan kolom kunci dan baris kunci disebut angka kunci. 14. Hitunglah nilai-nilai pada baris A2 pada iterasi ke-2 ( baris A2 baru ) dengan cara : Baris A2 lama : 4 Baris Pivot : 3(1/3
3 1
0 -1/3
-1 0
0 1/3
1 0
5 4/3)
Baris A2 baru :
0
1
-1
-1
1
1
3
-
15. Hitung kembali nilai-nilai Z yang baru 16. Hitung pula nilai C-Z yang baru 17. Periksalah apakah semua nilai C-Z yang baru sudah tidak ada nilai negatif lagi. Bila iya, maka proses pehitungan dihentikan karena solusi sudah optimal. Tetapi jika tidak, maka dilanjutkan ke langlah 18. 18. Ulangilah langkah sejak langkah 8
ARTIFICIAL VARIABLES -3X1 + 4X2 = -6
Karena sisi kanan pada constraint harus non-negative, maka dikalikan -1
3X1 - 4X2 = 6
5X1 – 8X2 ≤ -10
Untuk pertidaksamaan -5X1 + 8X2 ≥ 10
Jika kendala dalam bentuk persamaan dan pertidaksamaan ≥, maka digunakan artificial variables untuk mendapatkan basis awal. Variabel ini sifatnya hanya sementara dan bukan menjadi bagian dari solusi akhir. Tidak semua menggunakan artificial variables, kendala dengan slack variables tidak perlu.
Contoh Maksimalkan : Z = X1 + 3X2 Kendala : 1. 2X1 – X2 ≤ -1 2. X1 + X2 = 3 X1, X2 ≥ 0 Kendala 1 kalikan -1, diperoleh : -2X1 + X2 ≥ 1 Tambahkan surplus variable : -2X1 + X2 – S1 = 1 Kedua kendala memiliki bentuk standar tetapi tidak memiliki solusi awal yang jelas seperti pada kendala dengan slack variable. Sehingga ditambahkan artificial variables R1 dan R2 : -2X1 + X2 – S1 + R1 =1 X1 + X2 + R2 = 3 dimana X1, X2, S1, R1, R2 ≥ 0
Selain Big-M, untuk menyelesaikan masalah LP yang memiliki artificial variables dapat digunakan metode simplex two-phase. Sebelum melakukan komputasi, harus dipastikan apakah feasible solution ada, dengan artificial variables = 0. Caranya : Pertama, gunakan metode simplex untuk menyelesaikan masalah meminimalkan jumlah dr artificial variables. Jika = 0, berarti ada solusi. Tetapi jika jumlahnya tidak = 0, berarti kendala tidak dapat dipenuhi. Kemudian gunakan solusi akhir sebagai solusi awal untuk masalah yang sebenarnya.
2 fase dari metode ini adalah sbb : Fase 1 : Susun sebuah fungsi objektif baru yang memuat jumlah dari artificial variable. Gunakan metode simplex untuk meminimalkan fungsi objektif yang memenuhi kendala.Jika artificial objective function dapat direduksi menjadi 0, maka setiap (non-negative) artificial variables akan =0. Dalam kasus ini, semua kendala pada permasalahan awal dipenuhi, maka dapat dilanjutkan fase 2. Sebaliknya, berarti infeasible. Fase 2 :Gunakan basic feasible solution dari fase 1 (abaikan artificial variables) sebagai solusi awal untuk permasalahan dengan fungsi objektif yang sebenarnya. Gunakan metode simplex biasa untuk mendapatkan solusi optimal
Maksimalkan : Z = X1 + 3X2 Kendala : -2X1 + X2 – S1 + R1 =1 X1 + X2 + R2 = 3
Minimalkan : ZR = R1 + R2 Maksimalkan : ZR = -R1 - R2 ZR + R1 + R2 = 0 Fase 1 : Basis
, ekivalen dengan
X1
X2
S1
R1
R2 Solution
ZR
0
0
0
1
1
0
R1
-2
1
-1
1
0
1
R2
1
1
0
0
1
3
Lakukan row operation untuk mendapatkan basis awal (yaitu zero coefficient untuk R1 dan R2) X1
X2
S1
R1
R2 Solution
ZR
1
-2
1
0
0
-4
R1
-2
1
-1
1
0
1
R2
1
1
0
0
1
3
X1
X2
S1
R1
-3 -2 3
0 1 0
-1 -1 1
2 1 -1
Lakukan metode simplex sebanyak 2 iterasi. Iterasi 1 : ZR X2 R2
R2 Solution
0 0 1
-2 1 2
Iterasi 2 :
ZR X2
X1
X1 0 0 1
X2 0 1 0
S1 0 -0.33 0.33
R1 1 0.33 -0.33
R2 Solution 1 0 0.67 2.33 0.33 0.67
Hasil tersebut merupakan solusi optimal dari fase 1, dimana R1, R2 = 0 dan nonbasic
Fase 2 : Artificial variables dihilangkan, fungsi objektif kembali pada nilai sebenarnya Z X2
X1 -1 0
X2 -3 1
X1
1
0
X1
X2
0 0 1
0 1 0
S1 Solution 0 0 -0.33 2.33
0.33
0.67
Lakukan row operation untuk mendapatkan baris fungsi objektif yang tepat. basis
Z X2 X1
S1 Solution
-0.67 -0.33 0.33
7.67 2.33 0.67
Lakukan metode simplex, 1 kali iterasi basis Z X2 S1
X1 2 1
X2 0 1
3
0
S1 Solution 0 9 0 3 1
2
Dari tabel di atas dihasilkan : titik optimal X1=0 dan X2=3 dengan Z=9. Bandingkan dengan metode grafik… Feasible region pada garis X1+X2=3, antara titik (0,3) dan (2/3 , 7/3). Pada fase 1, diperoleh solusi feasible awal pada titik (2/3 , 7/3). Sedang pada fase 2 diperoleh solusi optimal pada (0,3)
