pertemuan 4

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