PROGRAM LINIER : ANALISIS POST- OPTIMAL Pertemuan 6
Pengantar Biasanya, setelah solusi optimal dari
masalah program linier ditemukan maka peneliti cenderung untuk berhenti menganalisis model yang telah dibuat. Padahal sesungguhnya dengan menganalisis lebih jauh atas solusi optimal akan dapat menghasilkan informasi lain yang berguna
Analisis yang dilakukan terhadap solusi
optimal untuk mendapatkan informasi tambahan yang berguna tersebut dikenal dengan analisis post-optimal Analisis ini dapat dilakukan dengan 2 cara, yaitu:
Analisis Dualitas Analisis Sensitivitas
Analisis Dualitas Dilakukan dengan merumuskan dan
menginterpretasikan bentuk dual dari model. Bentuk dual adalah suatu bentuk alternatif dari model program linier yang telah dibuat dan berisi informasi mengenai nilai-nilai sumber yang biasanya membentuk sebagai batasan model
Analisis Sensitivitas Dilakukan untuk menganalisis dampak yang
terjadi pada solusi optimal terhadap perubahan-perubahan yang terjadi pada koefisien-koefisien batasan model maupun koefisien pada fungsi tujuan
Model program linier memiliki 2 bentuk, yaitu: Model primal
adalah bentuk asli dari suatu model program linier Model dual adalah bentuk alternatif yang dikembangkan dari model primal
Kegunaan bagi pengambil keputusan adalah: Model Primal akan menghasilkan solusi
dalam bentuk jumlah laba yang diperoleh dari memproduksi barang ataupun biaya yang dibutuhkan untuk memproduksi barang. Model Dual akan menghasilkan informasi mengenai nilai (harga) dari sumber-sumber yang membatasi tercapainya laba tersebut.
Solusi pada model dual memberikan
informasi tentang sumber-sumber yang digunakan untuk menentukan apakah perlu menambah sumber-sumber daya, serta berapa biaya yang harus dikeluarkan untuk tambahan tersebut.
Hubungan primal-dual
Hubungan khusus antara primal dan dual adalah : Variabel dual Y1 , Y2 , Y3 berhubungan dengan batasan
model primal. Dimana untuk setia batasan dalam primal terdapat satu variabel dual. Misal, model primal mempunyai 3 batasan, maka dualnya akan mempunyai 3 variabel keputusan. Nilai kuantitas pada sisi kanan pertidaksamaan pada model primal merupakan koefisien fungsi tujuan dual. Koefisien batasan model primal merupakan koefisien variabel keputusan dual. Koefisien fungsi tujuan primal, merupakan nilai kuantitas pada sisi kanan pertidaksamaan pada model dual. Pada bentuk standar, model maksimisasi primal memiliki batasan-batasan <, sedangkan model minimisasi dual memiliki batasan-batasan >.
Contoh 1 :
Contoh 2 : Model Primal
Fungsi tujuan : Maks Z = 160 X1 + 200 X2 Fungsi batasan : 2 X1 + 4 X2 < 40 18 X1 + 18 X2 < 216 24 X1 + 12 X2 < 240 X1 , X2 > 0
Model Dualnya adalah:
Fungsi tujuan : Min Z = 40 Y1 + 216 Y2 + 240 Y3 Fungsi batasan : 2 Y1 + 18 Y2 + 24 Y3 > 160 4 Y1 + 18 Y2 + 12 Y3 > 200 Y1 , Y2 , Y3 > 0
Contoh 3 : Model Primal
Fungsi tujuan : Maks Z = 10 X1 + 6 X2 Fungsi batasan : X1 + 4 X2 < 40 3 X1 + 2 X2 = 60 2 X1 + X2 > 25 X1 , X2 > 0
Perhatian: Untuk mentransformasikan model primal
kedalam bentuk dual adalah bahwa model primal harus dalam bentuk standar. Sehingga, bila model primal belum dalam bentuk standar harus dirubah dulu menjadi bentuk standar. Untuk masalah maksimisasi, bentuk standarnya adalah fungsi batasan mempunyai tanda <. Untuk masalah minimisasi, bentuk standarnya adalah fungsi batasan mempunyai tanda >.
Jadi untuk contoh 3, diperoleh fungsi batasan sbb.: X1 + 4 X2 < 40 X1 + 4 X2 < 40 3 X1 + 2 X2 = 60 3 X1 + 2 X2 < 60 3 X1 + 2 X2 > 60 (-1) (3 X1 + 2 X2 > 60) - 3 X1 - 2 X2 < - 60 2 X1 + X2 > 25 (-1) (2 X1 + X2 > 25) - 2 X1 - X2 < - 25
Sehingga model primal menjadi : Fungsi tujuan : Maks Z = 10 X1 + 6 X2 Fungsi batasan : X1 + 4 X2 < 40 3 X1 + 2 X2 < 60 - 3 X1 - 2 X2 < - 60 - 2 X1 - X2 < - 25 X1 , X2 > 0
Dari model primal yang sudah dalam bentuk standar, maka model dual dapat diformulasikan sebagai berikut : Fungsi tujuan : Min Z = 40 Y1 + 60 Y2 - 60 Y3 - 25 Y4 Fungsi batasan : Y1 + 3 Y2 - 3 Y3 - 2 Y4 > 10 4 Y1 + 2 Y2 - 2 Y3 - Y4 > 6 Y1 , Y2 , Y3 , Y4 > 0
Contoh 4 :
Contoh 4: (masalah primal) I1
I2
Kapasitas Maksimum
1
2
0
8
2
0
3
15
3
6
5
30
Sumbangan laba
3
5
Merek Mesin
Tabel primal-dual X1
X2
Y1
2
0
≤8
Y2
0
3
≤ 15
Y3
6
5
≤ 30
≥3
≥5
Merek Mesin
Tabel primal-dual Merek
X1
X2
Y1
2
0
≤8
Y2
0
3
≤ 15
Y3
6
5
≤ 30
≥3
≥5
Mesin
Fungsi primal-dual Tujuan : Maks Z = 3X1 + 5X2
Tujuan : Min Y = 8Y1 + 15Y2 + 30Y3
Batasan : 2X1 3X2 6X1 + 5X2
Batasan : 2Y1 + 6 Y3 3Y2 + 5 Y3
dan X1 ≥ 0, X2 ≥ 0
≤8 ≤ 15 ≤ 30
≥3 ≥5
dan Y1 ≥ 0, Y2 ≥ 0, Y3 ≥ 0
Interpretasi Ekonomis Fungsi primal n Tujuan : Maks Z = ∑ C j X j j =1
n
Batasan
∑a j =1
Xj Cj Z bi aij
ij
X j ≤ bi
= Tingkat aktivitas ke j = Laba persatuan aktivitas j = Laba total dari seluruh aktivitas = Jumlah sumber i yang tersedia = jumlah sumber i yang “dipakai” oleh setiap satuan aktivitas j
Dengan menggantikan Zj, metode simpleks dapat diartikan mencari nilai Ym Fungsi dual m Tujuan : Min Y0 = ∑ biYi m
Batasan
∑a Y ≥ C i =1
Yi
i =1
ij i
j
= kontribusi persatuan sumber i terhadap laba
Hasil masalah dual Y = 8(0) + 15(5/6) + 30(1/2)
Y = 271/2
Tujuan : Min Y = 8Y1 + 15Y2 + 30Y3 Batasan : 2Y1 + 6 Y3 3Y2 + 5 Y3
≥3 ≥5
dan Y1 ≥ 0, Y2 ≥ 0, Y3 ≥ 0 Analisis Simplex Y1 = 0, Y2 = 5/6, Y3 = 1/2
Hasil masalah dual