teknik riset operasi pertemuan 11

Teknik Riset Operasi

Oleh : A. AfrinaRamadhani H. 13.12.11

1


PERTEMUAN 11 13.12.11

2


13.12.11 Teknik Riset Operasi

3

Dualitas dan Analisis Postoptimal

Hubungan primal-dual

• Dual adalah permasalahan PL yang diturunkan secara matematik dari

primal PL tertentu.

• Setiap permasalahan primal selalu mempunyai pasangan dual dan

sebaliknya.

• Solusi optimal pada dual secara otomatis akan menghasilkan solusi

optimal pada primal dan sebaliknya.

• Penyelesaian bentuk dual sama halnya dengan bentuk primal yaitu

juga dilakukan dari bentuk standar.


4

• Bentuk standar PL secara umum adalah :

Maksimumkan atau minimumkan

Z = ∑cjxj

terhadap

∑aijxj = bi

xj ≥ 0

variabel xj termasuk variabel keputusan, slack, surplus dan artificial


5

Konversi dual dari primal


6

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

Aturan di atas menunjukkan bahwa permasalahan dual akan mempunyai

sejumlah m variabel (y1, y2,..., ym) dan sejumlah n pembatas ( sesuai

dengan x1, x2, …, xn).


7

• Elemen lain dari permasalahan dual ditentukan dengan cara seperti

yang ditunjukkan tabel di bawah.


8

Contoh 1

Diberikan bentuk primal di bawah, tentukanlah bentuk dual

yang sesuai.

Minimumkan z = 2 x1 + 5.5 x2

Kendala: x1 + x2 = 90

0.001x1 + 0.002x2 ≤ 0.9

0.09x1 + 0.6x2 ≥ 27

0.02x1 + 0.06x2 ≤ 4.5

x1, x2 ≥ 0


9

Penyelesaian contoh 1

• Bentuk umum di atas diubah terlebih dahulu menjadi bentuk baku /

standar, yaitu :


10

• Bentuk dualnya terdiri dari 4 variabel dan 2 pembatas, yaitu :


11

Contoh 2

• Diberikan bentuk primal di bawah, tentukanlah bentuk dual yang sesuai .


12

Penyelesaian contoh 2


13

Solusi dual optimal

• Solusi optimal dual dapat diperoleh secara langsung dari tabel primal

optimal. Bentuk matriks primal adalah :


14

• Misal B adalah basis primal optimal dan CB adalah koefisien fungsi

tujuan variabel basis tersebut, maka :

Y = CB B-1

adalah solusi dual optimal.

Solusi optimal fungsi tujuan adalah :

w = Yb = CB B-1 b

Solusi optimal fungsi tujuan primal adalah ;

z = CB XB = CB B-1 b

Permasalahan primal mencari solusi optimal, sedangkan permasalahan

dual mencari solusi layak.

Q & A

Sekian dan Terima Kasih 13.12.11 Teknik Riset Operasi

15

teknik riset operasi pertemuan 11

Documents