pertemuan 4
DESCRIPTION
Pertemuan 4. Teori Dualitas. Teori Dualitas. Cara merubah primal dual. Pada primal jadikan bentuk normal Jk f.tujuan = max, maka seluruh pembatas jadikan = F. tujuan berubah bentuk primal max, maka dual min - PowerPoint PPT PresentationTRANSCRIPT
bilqis 1
Pertemuan 4
Teori Dualitas
bilqis 2
Teori Dualitas
bilqis 3
Cara merubah primal dual• Pada primal jadikan bentuk normal
– Jk f.tujuan = max, maka seluruh pembatas jadikan <=
– Jk f. tujuan = min, maka seluruh pembatas jadikan >=
• F. tujuan berubah bentuk– primal max, maka dual min– Primal min, maka dual max
• Kons. Kanan primal koef.f.tujuan dual• Koef.f.tujuan primal kons. Kanan dual
bilqis 4
Cara merubah primal dual
• Untuk tiap pembatas primal ada 1 var dual• Untuk tiap var.primal ada 1 pembatas dual• Tanda pembatas pada dual akan
tergantung pada f.tujuannya– f.tujuan max, maka pembatas <=– F.tujuan min, maka pembatas >=
• Dual dari dual primal
bilqis 5
Primal Perusahaan PT Sayang Anak
• max Z = 3x1 + 2x2• batasan :
2x1 + x2 <= 100X1 + x2 <= 80X1 <= 40X1, x2 >= 0
• X1 = boneka• X2 = kereta api• Waktu poles max 100 jam• Waktu kayu max 80 jam
Primal mencari keuntungan max
Berapa boneka dan kereta api yangHarus di produksi agar keuntungan max
Dual mencari berapa kebutuhan optimalDari sumber daya yang ada
Berapa jam waktu poles dan waktu kayuYang dipakai sesungguhnya, agar hasil tetapoptimal
bilqis 6
Dengan grafis
bilqis 7
Dengan simpleks
1. Jadikan standard– max Z = 3x1 + 2x2 + 0S1 + 0S2 + 0S3
z – 3x1 – 2x2 = 0
– batasan 2x1 + x2 + S1 = 100X1 + x2 + S2 = 80X1 + S3 = 40X1, x2, S1, S2, S3 >= 0
2. BV S1, S2, S3NBV x1, x2
bilqis 8
3. table
pivotEV
pivot
pivot
LV
1 -1 0 20
bilqis 9
• Optimal x1 = 20X2 = 60 Z = 3.20 + 2.60 = 180
• Keuntungan maksimum adalah 180• X1 = boneka yang diproduksi sebanyak 20
buah• X2 = kereta api yang di produksi sebanyak
60 buah
bilqis 10
Dual dari Primal
• Min w =100 y1 + 80 y2 + 40 y3• Batasan
2 y1 + y2 + y3 >= 3y1 + y2 >= 2
y1, y2, y3 >= 0
bilqis 11
Dual TORA
bilqis 12
bilqis 13
Bahasan• Min w =100 y1 + 80 y2 + 40 y3• Batasan
2 y1 + y2 + y3 >= 3y1 + y2 >= 2
Jawaban :y1 = 1y2 =1
Maka min w = 100.1 + 80.1 = 180Hasil sama dengan max Z = 180Artinya sumber daya poles perlu 100 jam dan sumber
daya kayu perlu 80 jam agar mendapat hasil optimum
bilqis 14
Contoh Soal
bilqis 15
Primal dengan TORA
bilqis 16
Primal dengan TORA
bilqis 17
Dual dengan TORA
bilqis 18
Dual dengan TORA
bilqis 19
Dual dengan TORA
bilqis 20
Model Primal :
memaksimumkan Z = $160x1 + 200x2
terbatas pada2x1 + 4x2 ≤ 40 jam tenaga kerja
18x1 + 18x2 ≤ 216 pon kayu
24x1 + 12x2 ≤ 240 M2 tempat penyimpanan
x1, x2 ≥ 0
dimanax1 = jumlah meja yang diproduksi
x2 = jumlah kursi yang diproduksi
bilqis 21
bilqis 22
• Hasil optimum• X1 = meja 4• X2 = kursi 8• Jadi keuntungan max adalah :
– Max Z =2.240
bilqis 23
Model primal : maks Model dual : min • Model DUAL :
meminimumkan Z = 40y1 + 216y2 + 240y3
terbatas pada2y1+ 18y2 + 24y3 ≥ 160
4y1 + 18y2 + 12y3 ≥ 200
y1, y2, y3 > 0
bilqis 24
bilqis 25
• Hasil optimum• y1 20• y2 6,67• Jadi min w =2.240
bilqis 26
Contoh 2 :
meminimumkan Z = 6x1 + 3x2
terbatas pada 2x1 + 4x2 ≥ 16 pon nitrogen
4x1 + 3x2 ≥ 24 pon phospate
x1, x2 ≥0
dimanax1 = jumlah sak pupuk Super‑gro
x2 = jumlah sak pupuk Crop‑quik
Z = total biaya pembelian pupuk
bilqis 27
Dual :
memaksimumkan Zd = 16y1 + 24y2
terbatas pada2y1 + 4y2 ≤ 6, biaya dari Super‑gro
4y1 + 3y2 ≤ 3, biaya dari Crop‑quik
y1 , y2 ≥0
dimanay1 = nilai marjinal nitrogen
y2 = nilai marjinal phospate
bilqis 28
Contoh 3:
memaksimumkan Z = 10x1 + 6x2
terbatas pada x1 + 4x2≤ 40
3x1 + 2x2 = 60 2x1 + x2 ≥ 25
x1, x2 ≥0
bilqis 29
Shg Perubahan Batasan :
memaksimumkan Zp = 10x1 + 6x2 terbatas pada x1 + 4x2 ≤ 40
3x1 + 2x2 ≤ 60
‑3x1 – 2x2 ≤ ‑60
‑2x1 – x2 ≤ -25
x1, x2 ≥ 0
bilqis 30
• Bentuk dual :
meminimumkan Zd = 40y1 + 60y2 – 60y3 – 25y4
terbatas pada y1 + 3y2 –3y3 – 2y4 ≥ 10
4y1 + 2y2 –2y3 – y4 ≥ 6
y1, y2, y3, y4 ≥ 0
bilqis 31
primal
• Max z = 5 x1 + 12 x2 + 4 x3• Batasan
x1 + 2 x2 + x3 <= 102 x1 – x2 + 3 x3 = 8x1, x2, x3 >= 0
bilqis 32
Primal normal
• Max z = 5 x1 + 12 x2 + 4 x3• Batasan
x1 + 2 x2 + x3 <= 102 x1 – x2 + 3 x3 <= 8
- 2 x1 + x2 - 3 x3 <= - 8x1, x2, x3 >= 0
bilqis 33
dual
• Min W = 10 y1 + 8 y2 - 8 y3’• Batasan y1 + 2 y2 - 2 y3 >= 5
2 y1 – y2 + y3 >= 12 y1 + 3 y2 - 3 y3 >= 4 y1 , y2 , y3 >= 0
bilqis 34
Primal dengan TORA
bilqis 35
bilqis 36
Dual dengan TORA
bilqis 37
bilqis 38
bilqis 39
Primal dengan manual
Itr BV x1 x2 x3 s1 R2 Solusi
0 z -(2M+5) M-12 -(3M+4) 0 0 -8M
s1 1 2 1 1 0 10
R2 2 -1 3 0 1 8
1 z -7/3 -40/3 0 0 4/3+M 32/3
x2 1/3 7/3 0 1 -1/3 22/3
s2 2/3 -1/3 1 0 1/3 8/3
2 z -3/7 0 0 40/7 -4/7+M 368/7
x2 1/7 1 0 3/7 -1/7 22/7
x1 5/7 0 1 1/7 2/7 26/7
bilqis 40
Itr BV x1 x2 x3 s1 R2 Solusi
3 z 0 0 3/5 29/5 -2/5+M 54 4/5
x2 0 1 -1/5 2/5 -1/5 12/5
x1 1 0 7/5 1/5 2/5 26/5
Primal (cont’d)
bilqis 41
Dual dengan manual
bilqis 42
Contoh LainReddy Mikks model :Primal Dualmax z = 5x1+4x2 min w = 24y1+6y2+y3+2y4
st:st:6x1 + 4x2 ≤ 24 (M1) 6y1+y2-y3 ≥5x1 + 2x2 ≤ 6 (M2) 4y1+2y2+y3+y4 ≥4-x1 + x2 ≤ 1 y1, y2, y3, y4 ≥ 0
x2 ≤ 2 x1, x2 ≥ 0
Optimal solution : Optimal solution :x1 = 3, x2 = 1.5, z = 21 y1=0.75, y2=0.5, y3=y4=0, w=21
bilqis 43
PR
• Cari bentuk dual dari primal berikut ini dan cari jawaban primal dan dual
• Max Z = -5x1 + 2x2• Batasan
-x1 + x2 <= -22x1 + 3x2 <= 5X1, x2 >=0