Bentuk standar PL secara umum adalah: Maksimumkan atau minimumkan z = Σcjxj Terhadap Σaijxj = bi

Bentuk standar PL secara umum adalah: Maksimumkan atau minimumkan z = Σcjxj Terhadap Σaijxj = bi xj ≥ 0 xj : variabel keputusan, slack, surplus dan artificial. 8/1/2005

created by Hotniar Siringoringo

1

Konversi dual dari primal dilakukan dengan memperhatikan hubungan seperti yang ditunjukkan tabel berikut: Variabel primal

x1

x2

…

xj

…

xn

Nilai kanan pembatas dual

c1

c2

…

cj

…

cn

Koefisien pembatas dual

a11

a12

… a1j … a1m b1

y1

a21

a22

… a2j … a2m b2

y2

. . .

. . .

am1

am2

. . .

. . .

. . .

… amj … amn bm ym

Koefisien pembatas dual ke-j 8/1/2005

. . .


V a r. d u al

Koefisien tujuan dual 2

Tabel di atas menunjukkan bahwa dual didapatkan secara simetris dari primal sesuai dengan aturan berikut: • Untuk setiap pembatas primal ada variabel dual. • Untuk setiap variabel primal ada pembatas dual. • Koefisien pembatas variabel primal membentuk koefisien pembatas dual. • Koefisien fungsi tujuan variabel yang sama dari primal menjadi nilai kanan pembatas dual. Elemen lain dari permasalahan dual ditentukan dengan cara seperti yang ditunjukkan tabel di bawah. 8/1/2005


3

Tujuan Dual standar Pembata Variabel Tujuan primal s Maksimisasi Minimisasi ≥ Tdk terbatas Minimisasi Maksimisasi ≤ Tdk terbatas Contoh: 1. Diberikan bentuk primal di bawah, tentukanlah bentuk dual yang sesuai!! Minimumkan z = 2x1 + 5.5x2 Kendala: x1 + x2 = 90 0.001x1 + 0.002x2 ≤ 0.9 0.09x1 + 0.6x2 ≥ 27 0.02x1 + 0.06x2 ≤ 4.5 x1, x2 ≥ 0 8/1/2005


4

Penyelesaian 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 0.09x1 + 0.6x2 + 0x3 – x4 + 0x5= 27 0.02x1 + 0.06x2 + 0x3 + 0x4 + x5 = 4.5 x1, x2, x3, x4, x5 ≥ 0

8/1/2005


y2 y3 y4

5

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

8/1/2005


6

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 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 8/1/2005


7

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 8/1/2005 created by Hotniar Siringoringo

8

3. Ubahlah bentuk dual di bawah ini ke dalam bentuk primalnya!!! Maksimumkan w = 100y1 + 200y2 + 150y3 + 150y4 Terhadap 2y1 + 2y2 + y3 + y4 ≤ 5 y1 + 2y2 + 3y3 + 2y4 ≤ 10 2y1 + 2y2 + 4y3 + y4 ≤ 10 y1, y3 ≤ 0 y2 ≥ 0 y4 tidak terbatas

8/1/2005


9

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 8/1/2005+ x2 + x3 = 150 created by Hotniar Siringoringo 2x1

10

4. Diberikan bentuk dual di bawah ini, ubahlah ke dalam bentuk primalnya!!! 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, x2created ≥0by Hotniar Siringoringo 8/1/2005

11

Bentuk matriks primal adalah: Maksimumkan/minimumkan z = CIXI + CIIXII Terhadap AXI + IXII = b XI, XII ≥ 0 Bentuk matriks dualnya adalah: Minimumkan/maksimumkan w = Yb Terhadap YA ≤ / ≥ CI Y ≤ / ≥ CII Y adalah vektor tidak terbatas 8/1/2005


12

•

Solusi optimal fungsi tujuan dual adalah w = Yb = CBB-1b • Solusi optimal fungsi tujuan primal adalah z = CBXB = CBB-1b. 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 ≥ 0created by Hotniar Siringoringo 8/1/2005

13

VB

X1

X2

S1

S2

S3

Solusi

z

0

0

0

9/70

1/35

94.2857

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

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; y2created = by9/70 dan y3 = 1/35 8/1/2005 Hotniar Siringoringo

14

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. Primal Maksimumkan z = Σ cjxj Terhadap Σ aijxj = bi, i = 1, 2, ..., m xj ≥ 0, j = 1, 2, ..., n 8/1/2005


15

Dual Minimumkan w = Σ biyi Terhadap Σ aijyi ≥ cj , j = 1, 2, ..., n yi tidak terbatas, i = 1, 2, ..., m cj : keuntungan marjinal aktivitas j dengan level sama dengan xj unit. Fungsi objektif : 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 kei oleh semua aktivitas. Variabel dual dari persamaan di atas adalah yi. 16 8/1/2005 created by Hotniar Siringoringo

z = w atau Σ cjxj= Σ biyi.

Sisi kiri persamaan : uang (pengembalian) bi : unit (jumlah) sumber daya ke-i, yi : jumlah uang per unit sumber daya ke-i. Variabel dual yi : kegunaan per unit sumber daya ke-i. Biaya Terkurangi Jumlah uang per unit keuntungan/kerugian = jumlah uang per unit biaya – jumlah uang per unit pengembalian.

8/1/2005


17

Kondisi optimal maksimisasi metode simpleks (simpleks yang direvisi) menunjukkan bahwa level aktivitas j saat ini yang tidak digunakan 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. Ketika aktivitas masuk j ke variabel basis, kita meningkatkan levelnya ke titik dimana zj – cj nya berkurang menuju 0 mengekploitasi aktivitas ke pemberdayaan paling penuh, karena peningkatan selanjutnya akan menghasilkan peningkatan biaya yang dikenakan dicreatedluar pengembalian potensial18 8/1/2005 by Hotniar Siringoringo aktivitas.

Aktivitas yang mempunyai level 0 pada solusi optimal (variabel non basis), kuantitas zj – cj menunjukkan biaya terkurangi per unit aktivitas j. Kuantitas ini menunjukkan jumlah dimana secara ekonomis aktivitas harus diperbaiki untuk membuat aktivitas lebih atraktif secara ekonomis yang dapat terjadi dalam dua cara, yaitu: 1.Meningkatkan pengembalian marjinal aktivitas, cj. 2.Menurunkan konsumsi aktivitas akan sumber daya terbatas, Σ aijyi.

8/1/2005


19

Bentuk standar PL secara umum adalah: Maksimumkan atau minimumkan z = Σcjxj Terhadap Σaijxj = bi

Recommend Documents