if184923 riset operasi pertemuan ke-5 - subakti.com · 2 •batasan • 2x 1 + 4x 2 ≤ 40 →waktu...

IF184923 Riset OperasiPertemuan ke-5

Misbakhul Munir IRFAN SUBAKTI司馬伊凡

Мисбакхул Мунир Ирфан Субакти

Teori Dualitas

• Persoalan dual didefinisikan secara sistematik dari model LP (linear programming) primal (atau program linier aslinya).

• Dua persoalan ini berkaitan erat→ solusi optimal dari satu problem secara otomatis akan menjadi solusi optimal yang lainnya

• Dual didefinisikan untuk berbagai bentuk variasi primal tergantungpada jenis optimisasi (maksimal atau minimal), jenis pembatas (≤, ≥, atau =), dan tanda dari variabel (nonnegatif atau tak terbatas)

2018/2019(1) - IF184923 Riset Operasi - MM Irfan Subakti 2

Primal → Dual

• Primal → bentuk baku• Fungsi tujuan = maks→ seluruh pembatas→ ≤

• Fungsi tujuan = min → seluruh pembatas→ ≥

• Fungsi tujuan berubah bentuk• Primal →maks, maka dual →min

• Primal →min, maka dual →maks

• Konstanta kanan primal → koefisien fungsi tujuan dual

• Koefisien fungsi tujuan primal → konstanta kanan dual


Primal → Dual (lanjutan)

• Untuk tiap pembatas primal → 1 variabel dual

• Untuk tiap variabel primal → 1 pembatas dual

• Tanda pembatas pada dual akan tergantung pada fungsi tujuannya• Fungsi tujuan maks→ pembatas ≤

• Fungsi tujuan min → pembatas ≥


Primal → PT Barbika Indonesia

• Primal →mencari keuntungan optimal (yaitu: maksimal)• Berapa jumlah boneka Barbika dan Kenaka yang harus dihasilkan agar

mendapat keuntungan maksimal

• Dual →mencari berapa kebutuhan optimal (yaitu: minimal) darisumber daya yang ada• Berapa waktu minimal yang dibutuhkan untuk pembuatan boneka dasar dan

waktu minimal untuk penghalusan boneka jadi


Primal → PT Barbika Indonesia (persamaan)

• Maks• Z = 3x1 + 2x2

• Batasan• 2x1 + x2 ≤ 100• x1 + x2 ≤ 80• x1 ≤ 40• x1, x2 ≥ 0

• x1 = Barbika

• x2 = Kenaka

• Pembuatan boneka dasar maksimal 100 jam

• Penghalusan boneka jadi maksimal 80 jam


Primal → Dengan TORA (Grafik)

• Dengan TORA:


Primal → Dengan TORA (Metode Simpleks)

• Transformasi ke bentukbaku:• Maks

• Z = 3x1 + 2x2 + 0S1 + 0S2+ 0S3

• Batasan• 2x1 + x2 ≤ 100• x1 + x2 ≤ 80• x1 ≤ 40• x1, x2, S1, S2, S3 ≥ 0

• BV → S1, S2, S3

• NBV → x1, x2


Primal → Dengan Metode Simpleks (lanjutan)

• Nilai optimal (maksimal)

• Keuntungan optimal (maksimal) adalah180

• x1 = Barbika, diproduksi sebanyak20 buah

• x2 = Kenaka, diproduksi sebanyak60 buah


Dual dari Primal & TORA

• Min• W = 100y1 + 80y2 + 40y3

• Batasan• 2y1 + y2 + y3 ≥ 3

• y1 + y2 ≥ 2

• y1, y2 , y3 ≥ 0


Dual: TORA – Metode Simpleks (Teknik M)


Pembahasan

• Min• W = 100y1 + 80y2 + 40y3

• Batasan• 2y1 + y2 + y3 ≥ 3• y1 + y2 ≥ 2• y1, y2 , y3 ≥ 0

• Jawaban• y1 = 1• y2 = 1

• Maka Min W = 100.1 + 80.1 + 0 →W = 180

• Solusinya (180) sama dengan Max Z = 180• Ini artinya sumber daya (resource) pembuatan boneka dasar memerlukan waktu maksimal

100 jam & pembuatan boneka jadi memerlukan waktu maksimal 80 jam agar mendapatkanhasil optimal (yaitu nilai minimal dari W)


Primal Dual: Contoh 2

• Primal: Maks• Z = 60x1 + 30x2 + 20x3

• Batasan• 8x1 + 6x2 + x3 ≤ 48 → y1 ≥ 0• 4x1 + 2x2 + 1.5x3 ≤ 20 → y2 ≥ 0• 2x1 + 1.5x2 + 0.5x3 ≤ 8 → y3 ≥ 0• x1, x2, x3 ≥ 0

• Dual: Min• W = 48y1 + 20y2 + 8y3

• Batasan• 8y1 + 4y2 + 2y3 ≥ 60• 6y1 + 2y2 + 1.5y3 ≥ 30• y1 + 1.5y2 + 0.5y3 ≥ 20• y1, y2, y3 ≥ 0


Primal: Contoh 2 dengan TORA (Simpleks)

• Primal: Maks• Z = 60x1 + 30x2 + 20x3

• Batasan• 8x1 + 6x2 + x3 ≤ 48 → y1 ≥ 0

• 4x1 + 2x2 + 1.5x3 ≤ 20 → y2 ≥ 0

• 2x1 + 1.5x2 + 0.5x3 ≤ 8 → y3 ≥ 0

• x1, x2, x3 ≥ 0


Primal dengan TORA: Simpleks (lanjutan)


Dual: Contoh 2 dengan TORA (Simpleks T. M)

• Dual: Min• W = 48y1 + 20y2 + 8y3

• Batasan• 8y1 + 4y2 + 2y3 ≥ 60

• 6y1 + 2y2 + 1.5y3 ≥ 30

• y1 + 1.5y2 + 0.5y3 ≥ 20

• y1, y2, y3 ≥ 0


Dual dengan TORA: Simpleks T. M

• Dual: Min• W = 48y1 + 20y2 + 8y3

• Batasan• 8y1 + 4y2 + 2y3 ≥ 60

• 6y1 + 2y2 + 1.5y3 ≥ 30

• y1 + 1.5y2 + 0.5y3 ≥ 20

• y1, y2, y3 ≥ 0


Dual dengan TORA: Simpleks T. M (lanjutan)


Primal Dual: Contoh 3

• Primal: Maks• Z = 160x1 + 200x2

• Batasan• 2x1 + 4x2 ≤ 40 → waktu kerja• 18x1 + 18x2 ≤ 216 → berat bahan kayu• 24x1 + 12x2 ≤ 240 → luasan tempat penyimpanan• x1, x2 ≥ 0 → di mana x1, x2 = jumlah meja & kursi yang diproduksi

• Dual: Min• W = 40y1 + 216y2 + 240y3

• Batasan• 2y1 + 18y2 + 24y3 ≥ 160• 4y1 + 18y2 + 12y3 ≥ 200• y1, y2, y3 > 0


Primal: Contoh 3 dengan TORA (Grafik)

• Primal: Maks• Z = 160x1 + 200x2

• Batasan• 2x1 + 4x2 ≤ 40 → waktu kerja

• 18x1 + 18x2 ≤ 216 → berat bahan kayu

• 24x1 + 12x2 ≤ 240 → luasan tempat penyimpanan

• x1, x2 ≥ 0 → di mana x1, x2 = jumlah meja & kursi yang diproduksi


Primal dengan TORA: Grafik (lanjutan)

• Solusi optimal• x1 = meja→ 4

• x2 = kursi→ 8

• Jadi keuntunganmaksimal• Z = 160x1 + 200x2

• Z = 160.4 + 200.8

• Z = 2240


Dual: Contoh 3 dengan TORA (Simpleks T. M)

• Dual: Min• W = 40y1 + 216y2 + 240y3

• Batasan• 2y1 + 18y2 + 24y3 ≥ 160

• 4y1 + 18y2 + 12y3 ≥ 200

• y1, y2, y3 > 0


Dual dengan TORA: Simpleks T. M (lanjutan)

• Solusi optimal• y1 = 20

• y2 → 6,67

• Jadi sumber dayaminimal• W = 40y1 + 216y2 +

240y3

• W = 40.20 + 216.6,67

• W = 2240


Contoh 4

• Carilah bentuk dual dari bentuk primal di bawah ini.

• Kemudian, carilah jawaban primal dan dual-nya.

• Fungsi Tujuan: Maks Z = -5x1 + 2x2

• Batasan/Kendala:-x1 + x2 ≤ -2

2x1 + 3x2 ≤ 5

x1, x2 ≥ 0


if184923 riset operasi pertemuan ke-5 - subakti.com · 2 •batasan • 2x 1 + 4x 2 ≤ 40 →waktu...

Documents