6s-1 Linear Programming

William J. Stevenson

Operations Management

8th edition

OPERATIONSRESEARCH

Enos

6s-2 Linear Programming

DUALITAS DALAM LINEAR PROGRAMING

6s-3 Linear Programming

KONSEP DUALITAS · Setiap persoalan linear programing mempunyai

suatu linear program yang berkaitan, yang disebut “dual”.

· Solusi dari persoalan asli LP (Primal), juga memberikan solusi pada dualnya

6s-4 Linear Programming

Hubungan primal-dual

Primal Dual

Batasan i Variabel i

Fungsi Tujuan Nilai Kanan

6s-5 Linear ProgrammingContoh :

MerekMesin

I1 I2 Kapasitas Maksimum

1 2 0 82 0 3 153 6 5 30

Sumbangan laba 3 5

MerekMesin

X1 X2

Y1 2 0 ≤ 8Y2 0 3 ≤ 15Y3 6 5 ≤ 30

≥ 3 ≥ 5

Tabel primal-dual

(masalah primal)

6s-6 Linear Programming

Fungsi primal-dualTujuan :Maks Z = 3X1 + 5X2

Batasan :2X1 83X2 156X1 + 5X2 30

danX1 ≥ 0, X2 ≥ 0

Tujuan :Min Y = 8Y1 + 15Y2 + 30Y3

Batasan :2Y1 + 6 Y3 ≥ 33Y2 + 5 Y3 ≥ 5

danY1 ≥ 0, Y2 ≥ 0, Y3 ≥ 0

MerekMesin

X1 X2

Y1 2 0 ≤ 8Y2 0 3 ≤ 15Y3 6 5 ≤ 30

≥ 3 ≥ 5

Tabel primal-dual

Batasan i

Variabel i

Fungsi Tujuan

Nilai Kanan

Kunci 1

Kunci 2

6s-7 Linear Programming Interpretasi EkonomisFungsi primal

n

jjj XCZ

1

Maks:Tujuan

n

jijij bXa

1

Batasan

Dengan menggantikan Zj, metode simpleks dapat diartikan mencari nilai Ym

Fungsi dual

m

iiiYbY

10Min :Tujuan

m

ijiij CYa

1

Batasan

Xj = Tingkat aktivitas ke jCj = Laba persatuan aktivitas jZ = Laba total dari seluruh aktivitasbi = Jumlah sumber i yang tersediaaij = jumlah sumber i yang “dipakai” oleh setiap satuan

aktivitas j

Yi = kontribusi persatuan sumber i terhadap laba

6s-8 Linear ProgrammingHasil masalah dual

Tujuan : Min Y = 8Y1 + 15Y2 + 30Y3

Batasan :2Y1 + 6 Y3 ≥ 33Y2 + 5 Y3 ≥ 5

danY1 ≥ 0, Y2 ≥ 0, Y3 ≥ 0

Y1 = 0, Y2 = 5/6, Y3 = 1/2

Y = 8(0) + 15(5/6) + 30(1/2)

Y = 271/2

Analisis Simplex

6s-9 Linear Programming

SEKIANTERIMAKASIH

6s-10 Linear Programming End of Slide show, clik to exit

6s-11 Linear Programming

Interpretasi dual yang lain :· Marginal Value

· Shadow Price· Surplus Variabel

Tugas !!!! (Tidak di kumpulkan)

6s-12 Linear ProgrammingALAT ANALISIS

· QSB+· AB:QM· AB:POM· QM (DOS/WINDOWS)· LINDO· SAS