BAB VI. DUALITAS DAN ANALISIS POSTOPTIMAL HUBUNGAN PRIMAL-DUAL Dual adalah permasalahan PL yang diturunkan secara matematik dari primal PL tertentu. Setiap permasalahan primal selalu mempunyai pasangan dual dan sebaliknya. Solusi optimal pada dual secara otomatis akan menghasilkan solusi optimal pada primal dan sebaliknya. Hal yang harus selalu diingat, penyelesaian baik menggunakan metode primal maupun dual dilakukan dari bentuk standar. Bentuk standar PL secara umum adalah: Maksimumkan atau minimumkan z = Σcjxj Terhadap Σaijxj = bi xj ≥ 0 variabel xj termasuk variabel keputusan, slack, surplus dan artificial. Konversi dual dari primal dilakukan dengan memperhatikan hubungan seperti yang ditunjukkan tabel berikut: Variabel primal x1
x2
…
xj
…
xn
c1
c2
…
cj
…
cn
a11
a12
…
a1j
…
a1m
b1
y1
a21 pembatas .. .
a22 .. .
…
a2j .. .
…
a2m .. .
b2 .. .
y2 .. .
am1
am2
…
amj
…
amn
bm
ym
Nilai kanan pembatas dual
Koefisien dual
Dualitas dan Analisis Postoptimal
Variabel dual
1
Koefisien pembatas dual ke-j
Koefisien tujuan dual
Tabel di atas menunjukkan bahwa dual didapatkan secara simetris dari primal sesuai dengan aturan berikut: 1. Untuk setiap pembatas primal ada variabel dual. 2. Untuk setiap variabel primal ada pembatas dual. 3. Koefisien pembatas variabel primal membentuk koefisien pembatas dual; koefisien fungsi tujuan variabel yang sama dari primal menjadi nilai kanan pembatas dual. Aturan di atas menunjukkan bahwa permasalahan dual akan mempunyai sejumlah m variabel (y1, y2, …, ym) dan sejumlah n pembatas (sesuai dengan x1, x2, …, xn). Elemen lain dari permasalahan dual ditentukan dengan cara seperti yang ditunjukkan tabel di bawah. Dual
Tujuan standar
Tujuan
Pembatas
Variabel
Maksimisasi Minimisasi
≥
Tidak
Minimisasi
≤
terbatas
primal Maksimisasi
Tidak terbatas Contoh: 1. Diberikan bentuk primal di bawah, tentukanlah bentuk dual yang sesuai!! Minimumkan z = 2 x1 + 5.5 x2 Kendala:
x1 + x2 = 90 0.001x1 + 0.002x2 ≤ 0.9
Dualitas dan Analisis Postoptimal
2
0.09x1 + 0.6x2 ≥ 27 0.02x1 + 0.06x2 ≤ 4.5 x1, x2 ≥ 0 Penyelesaian Pertama, bentuk umum di atas diubah menjadi bentuk baku/standar, yaitu: Minimumkan z = 2 x1 + 5.5 x2 + 0x3 + 0x4 + 0x5 Terhadap:
x1 + x2 + 0x3 + 0x4 + 0x5 = 90
y1
0.001x1 + 0.002x2 + x3 + 0x4 + 0x5= 0.9
y2
0.09x1 + 0.6x2 + 0x3 – x4 + 0x5= 27
y3
0.02x1 + 0.06x2 + 0x3 + 0x4 + x5 = 4.5
y4
x1, x2, x3, x4, x5 ≥ 0 Bentuk dualnya terdiri dari 4 variabel dan 2 pembatas, yaitu: Maksimumkan w = 90y1 + 0.9y2 + 27y3 + 4.5y4 Terhadap y1 + 0.001y2 + 0.09y3 + 0.02y4 ≤ 2 y1 + 0.002y2 + 0.6y3 + 0.06y4 ≤ 5.5 0y1 + y2 + 0y3 + 0y4 ≤ 0 0y1 + 0 y2 - y3 + 0y4 ≤ 0 0y1 + 0y2 + 0y3 + y4 ≤ 0 y1, y2, y3, y4 tidak terbatas atau Maksimumkan w = 90y1 + 0.9y2 + 27y3 + 4.5y4 Terhadap y1 + 0.001y2 + 0.09y3 + 0.02y4 ≤ 2 y1 + 0.002y2 + 0.6y3 + 0.06y4 ≤ 5.5 y2, -y3, y4 ≤ 0 y1 tidak terbatas
Dualitas dan Analisis Postoptimal
3
2. Diberikan bentuk primal di bawah, tentukanlah bentuk dual yang sesuai!! Maksimumkan z = 2x1 + 3x2 Terhadap : 10x1 + 5x2 ≤ 600 6x1 + 20x2 ≤ 600 8x1 + 15x2 ≤ 600 x1, x2 ≥ 0 Penyelesaian Bentuk baku/standar primal adalah: Maksimumkan z = 2x1 + 3x2 + 0x3 + 0x4 + 0x5 Terhadap : 10x1 + 5x2 + x3 = 600 6x1 + 20x2 + x4 = 600 8x1 + 15x2 + x5 = 600 x1, x2, x3, x4, x5 ≥ 0 Bentuk dualnya adalah: Minimumkan w = 600y1 + 600y2 + 600y3 Terhadap 10y1 + 6y2 + 8y3 ≥ 2 5y1 + 20y2 + 15y3 ≥ 3 y1 ≥ 0 y2 ≥0 y3 ≥0 3. Ubahlah bentuk dual di bawah ini ke dalam bentuk primalnya!!! Maksimumkan w = 100y1 + 200y2 + 150y3 + 150y4 Terhadap 2y1 + 2y2 + y3 + y4 ≤ 5
Dualitas dan Analisis Postoptimal
4
y1 + 2y2 + 3y3 + 2y4 ≤ 10 2y1 + 2y2 + 4y3 + y4 ≤ 10 y1, y3 ≤ 0 y2 ≥ 0 y4 tidak terbatas Penyelesaian Minimumkan z = 5x1 + 10x2 + 10x3 + 0x4 + 0x5 + 0x6 Terhadap 2x1 + x2 + 2x3 + x4 + 0x5 + 0x6 + 0x7 = 100 2x1 + 2x2 + 2x3 + 0x4 - x5 + 0x6 = 200 x1 + 3x2 + 4x3 + 0x4 + 0x5 + x6 = 150 2x1 + x2 + x3 + 0x4 + 0x5 + 0x6 = 150 x1, x2, x3, x4, x5, x6 ≥ 0 atau dalam bentuk umum PL-nya: Minimumkan z = 5x1 + 10x2 + 10x3 Terhadap 2x1 + x2 + 2x3 ≤ 100 2x1 + 2x2 + 2x3 ≥ 200 x1 + 3x2 + 4x3 ≤ 150 2x1 + x2 + x3 = 150 Minimumkan z = 5x1 + 10x2 + 10x3 + 0x4 + 0x5 + 0x6 Terhadap 2x1 + x2 + 2x3 + x4 + 0x5 + 0x6 + 0x7 = 100 2x1 + 2x2 + 2x3 + 0x4 - 0x5 + 0x6 = 200 x1 + 3x2 + 4x3 + 0x4 + 0x5 + x6 = 150 x1, x2, x3 ≥ 0 4. Diberikan bentuk dual di bawah ini, rubahlah ke dalam bentuk primalnya!!!
Dualitas dan Analisis Postoptimal
5
Minimumkan w = 10y1 + 20y2 Terhadap y1 + y2 ≥ 2 y1 + 2y2 ≥ 3 y1, -y2 ≥ 0 Penyelesaian Maksimumkan z = 2x1 + 3x2 +0x3 + 0x4 Terhadap x1 + x2 + x3 + 0x4 = 10 x1 + 2x2 + 0x3 - x4 = 20 x1, x2, x3, x4 ≥ 0 atau bentuk umum PL-nya adalah: Maksimumkan z = 2x1 + 3x2 Terhadap x1 + x2 ≤ 10 x1 + 2x2 ≥ 20 x1, x2 ≥0 SOLUSI DUAL OPTIMAL Solusi optimal dual dapat diperoleh secara langsung dari tabel primal optimal. Hal ini dapat diperhatikan dari bentuk matriks di bawah ini. Bentuk matriks primal adalah: Maksimumkan/minimumkan z = CIXI + CIIXII Terhadap AXI + IXII = b XI, XII ≥ 0 dan bentuk matriks dualnya adalah: Minimumkan/maksimumkan w = Yb Terhadap
Dualitas dan Analisis Postoptimal
6
YA ≤ / ≥ CI Y ≤ / ≥ CII Y adalah vektor tidak terbatas Misalkan B adalah basis primal optimal dan CB adalah koefisien fungsi tujuan variabel basis tersebut, maka Y = CBB-1 Adalah solusi dual optimal. Solusi optimal fungsi tujuan dual adalah w = Yb = CBB-1b dan solusi optimal fungsi tujuan primal adalah z = CBXB = CBB-1b. Permasalahan primal mencari solusi optimal, sedangkan permasalahan dual mencari solusi layak.
Hal ini menjadi dasar pengembangan dual
simpleks yang sudah anda pelajari pada bab 4. Perhatikan kasus 2.5 PL dari bab 2 dan solusi optimalnya pada bab 4. Maksimumkan z = 2x1 + 3x2 Terhadap : 10x1 + 5x2 ≤ 600 6x1 + 20x2 ≤ 600 8x1 + 15x2 ≤ 600 x1, x2 ≥ 0 Bentuk baku/standar: Maksimumkan z = 2x1 + 3x2 + 0s1 + 0s2 + 0s3 10x1 + 5x2 + s1 = 600 6x1 + 20x2 + s2 = 600 8x1 + 15x2 + s3 = 600 x1, x2, s1, s2, s3 ≥ 0 VB
X1
X2
Dualitas dan Analisis Postoptimal
S1
S2
S3
Solusi
7
z
0
0
0
9/70
1/35
S1
0
0
1
11/7
-17/7 85.7155
X2
0
1
0
8/70
-3/35 17.1329
X1
1
0
0
-3/14
2/7
94.2857
42.857
Bentuk dual dari primal di atas adalah: Minimumkan w = 600y1 + 600y2 + 600y3 Terhadap 10y1 + 6y2 + 8y3 ≥ 2 5y1 + 20y2 + 15y3 ≥ 3 y1 ≥ 0 y2 ≥0 y3 ≥0 Solusi dual adalah w = Yb, dimana Y = CBB-1. y1 = 0; y2 = 9/70 dan y3 = 1/35 Solusi optimal primal juga dapat diperoleh dari solusi optimal dual. Perhatikan kasus primal berikut: Min z = 21x1 + 18x2 + 15x3 Terhadap
90x1 + 20x2 + 40x3 ≥ 200 30x1 + 80x2 + 60x3 ≥ 180 10x1 + 20x2 + 60x3 ≥ 150 x1, x2, x3 ≥ 0
Bentuk dualnya adalah: Maksimumkan w = 200y1 + 180y2 + 150y3 Terhadap 90y1 + 30y2 + 10y3 ≤ 21 20y1 + 80y2 + 20y3 ≤ 18
Dualitas dan Analisis Postoptimal
8
40y1 + 60y2 + 60y3 ≤ 15 y1, y2, y3 ≤ 0 Solusi awal VB
y1
y2
y3
S1
S2
S3
Solusi
w
-200
-280
-150
0
0
0
0
S1
90
30
10
1
0
0
21
S2
20
80
20
0
1
0
18
S3
40
60
60
0
0
1
15
VB
y1
y2
y3
S1
S2
S3
Solusi
w
-130
0
-80
0
7/2
0
63
S1
165/2
0
5/2
1
-3/8
0
57/4
y2
1/4
1
1/4
0
1/80
0
9/40
S3
25
0
45
0
-3/4
1
3/2
VB
y1
y2
y3
S1
S2
S3
Solusi
w
0
0
154
0
-0.4
5.2
70.8
S1
0
0
-146
1
2.1
-3.3
9.3
y2
0
1
-1/5
0
0.02
-0.01
0.21
y1
1
0
9/5
0
-0.03
0.04
0.06
Iterasi-1
Iterasi-2
Tabel sudah optimal. Solusi optimal dualnya adalah: W = 70.8; y1 = 0.06; y2 = 0.21; dan y3 = 0. Solusi optimal primalnya adalah: Z = w = 70.8; x1 = 0; x2 = -0.4;
x3 = 5.2
Solusi optimal primal berdasarkan solusi optimal dual di atas adalah: x1 = 0; x2 = -0.4 ; x3 = 5.2; dan z = 70.8
Dualitas dan Analisis Postoptimal
9
INTERPRETASI EKONOMIS PERMASALAHAN DUAL Harga dual menunjukkan kegunaan per unit sumber daya produksi.
Biaya terkurangi menunjukkan peningkatan pengembalian
marjinal atau pengurangan biaya per unit sumber daya yang dibutuhkan untuk membuat satu aktifitas PL lebih menguntungkan. Hubungan
primal-dual
untuk
menunjukkan
arti
ekonomis
sebenarnya dari harga dual dan biaya terkurangi. Interpretasi harga dual dan biaya terkurangi akan dibuktikan sangat berguna pada dua aspek, yaitu: 1. menyediakan pemahaman fundamental model PL sebagai sistem output-input ekonomis. 2. memungkinkan implementasi efisien analisis sensitivitas atau postoptimal. Ingat kembali bentuk baku/standar primal dan dual dalam model matematik PL (bukan dalam bentuk matriks), seperti yang ditunjukkan di bawah ini untuk maksimisasi. Primal Maksimumkan z = Σ cjxj Terhadap Σ aijxj = bi, i = 1, 2, ..., m xj ≥ 0, j = 1, 2, ..., n Dual Minimumkan w = Σ biyi Terhadap Σ aijyi ≥ cj , j = 1, 2, ..., n yi tidak terbatas, i = 1, 2, ..., m
Dualitas dan Analisis Postoptimal
10
Koefisien cj pada primal menunjukkan keuntungan marjinal aktivitas j dengan level sama dengan xj unit.
Fungsi objektif oleh
karenanya menunjukkan keuntungan total yang dapat diperoleh dari semua aktivitas. Model tersebut mempunyai sejumlah m sumber daya, dimana sumber daya ke-i mempunya level bi yang dialokasikan pada laju aij per unit untuk aktivitas j.
Σ aijxj menunjukkan penggunaan sumber
daya ke-i oleh semua aktivitas.
Variabel dual dari persamaan di atas
adalah yi. Sebelumnya telah ditunjukkan bahwa z = w atau Σ cjxj= Σ biyi. Sisi kiri persamaan menunjukkan uang (pengembalian) dan bi menunjukkan unit (jumlah) sumber daya ke-i, maka yi dengan demikian pasti menunjukkan jumlah uang per unit sumber daya ke-i, sehingga satuan di kiri persamaan menjadi sama dengan satuan di kanan persamaan. Variabel dual yi oleh karenanya menunjukkan kegunaan per unit sumber daya ke-i. Untuk menjelaskan biaya terkurangi, ingat kembali koefisien persamaan fungsi tujuan variabel xj pada setiap iterasi, yaitu : zj – cj = CBB-1Pj - cj atau alternatifnya menggunakan Y= CBB-1 sebagai variabel dual yang bersesuaian, kita dapatkan: zj – cj = YPj - cj = Σ aijyi – cj. Hubungan ini menunjukkan bahwa koefisien persamaan tujuan zj – cj variabel xj pada tabel primal sama dengan perbedaan antara sisi kiri dan kanan pembatas dual ke-j.
persamaan ini menghasilkan interpretasi
ekonomis yang menarik model PL, yang akan ditunjukkan menggunakan analisis dimensional. Karena cj primal menunjukkan pengembalian per unit aktivitas j, unitnya mungkin ditunjukkan sebagai jumlah uang per unit aktivitas j. Dengan konsisten, kuantitas Σ aijyi pasti sama dengan dimensi jumlah uang per unit aktivitas j.
Dualitas dan Analisis Postoptimal
Karena cj dan Σ aijyi mempunyai tanda
11
berlawanan, maka kuantitas Σ aijyi pasti menunjukkan “biaya”. Dengan demikian, aij adalah jumlah sumber daya i yang dikonsumsi 1 unit aktivitas j. sebagai hasilnya, yi, pasti menunjukkan biaya yang dikenakan per unit sumber daya i dan kita dapat pikirkan Σ aijyi sebagai total biaya yang dikenakan untuk semua sumber daya yang digunakan untuk menghasilkan 1 unit aktivitas j. Sekarang, tergantung pada apakah biaya zj = Σ aijyi melebihi pengembalian cj, penjelasan di atas mengarahkan analisis dimensional persamaan zj - cj berikut: Jumlah uang per unit keuntungan/kerugian = jumlah uang per unit biaya – jumlah uang per unit pengembalian. Kondisi optimal maksimisasi metode simpleks (simpleks yang direvisi) menunjukkan bahwa level aktivitas j saat ini yang tidak digunakan (variabel non basis xj = 0) akan dinaikkan di atas level 0 hanya jika koefisien tujuannya zj – cj bernilai negatif. Kondisi ini dipenuhi secara ekonomis dengan cara berikut: dari interpretasi zj – cj , kondisi optimal memaksa bahwa (biaya yang dikenakan untuk penggunaan sumber daya per unit j – pengembalian per unit j) < 0 atau biaya yang dikenakan untuk penggunaan sumber daya per unit j < pengembalian per unit j.
oleh
karena itu, selama pengembalian per unit melebihi biaya yang dikenakan sumber
daya
yang
digunakan,
lebih
banyak
sumber
daya
harus
dialokasikan ke aktivitas untuk mengambil keuntungan potensial. Hal ini berarti bahwa level aktivitas j, xj, harus dinaikkan di atas level 0. Ketika kita memasukkan aktivitas j ke solusi (membuat variabelnya menjadi variabel basis), kita meningkatkan levelnya ke titik dimana zj – cj nya berkurang menuju 0.
Ini sama dengan mengekploitasi aktivitas ke
pemberdayaan paling penuh, karena peningkatan selanjutnya akan menghasilkan peningkatan biaya yang dikenakan di luar pengembalian potensial aktivitas.
Dualitas dan Analisis Postoptimal
12
Sekarang anda dapat melihat mengapa pada model maksimisasi suatu aktivitas dengan zj – cj > 0 akan berada pada level 0. Fakta bahwa biaya yang dikenakan penggunaan sumber daya lebih tinggi dari pengembaliannya membuatnya secara ekonomis tidak menarik. Aktivitas yang mempunyai level 0 pada solusi optimal (variabel non basis), kuantitas zj – cj menunjukkan biaya terkurangi per unit aktivitas j. Berdasarkan penjelasan di atas, kuantitas ini menunjukkan jumlah dimana secara ekonomis aktivitas harus diperbaiki untuk membuat aktivitas lebih atraktif secara ekonomis (menaikkan levelnya dari 0 ke nilai positif). Hasil seperti itu dapat terjadi dalam dua cara, yaitu: 1. Meningkatkan pengembalian marjinal aktivitas, cj. 2. Menurunkan konsumsi aktivitas akan sumber daya terbatas, Σ aijyi. Pilihan pertama mungkin tidak akan selalu layak, karena marjin keuntungan secara normal ditentukan oleh kondisi pasar dan persaingan. Pilihan kedua hanya merefleksikan komitmen entitas ekonomis untuk peningkatan operasinya terutama melalui pengurangan penggunaan sumber daya terbatas. penghilangan
Artinya, pilihan kedua berhubungan dengan
kemungkinan
ketidakefisienan
operasi
sistem
yang
dipertimbangkan. Nilai dual yi dapat digunakan sebagai indikator untuk menentukan dimana pilihan kedua harus diimplementasikan. Pengaruhnya, karena yi menunjukkan biaya terkurangi dari penggunaan 1 unit sumber daya i per unit aktivitas j, sumber daya yang mempunyai nilai tinggi secara relatif yi, harus mendapatkan prioritas dalam perbaikan.
Dualitas dan Analisis Postoptimal
13