riset operasi 7

RISET OPERASI

SEMESTER GENAP 2009/2010

UNIVERSITAS JEMBER

Senin, 08-03-10

DUALITAS DAN ANALISIS SENSITIVITAS

SEMESTER GENAP 2009/2010

UNIVERSITAS JEMBER

Senin, 08-03-10

DUALITAS

PengertianDual adalah bentuk lain dari suatu program

linear yang diturunkan dari primal Program Linear (yang sudah kita kenal).

Cara pandang dari sudut lain.

Suatu Primal program linear pasti mempunyai bentuk dual dan sebaliknya. Artinya, Dual dari dual adalah primal.

Solusi optimal pada Primal juga merupakan solusi Optimal pada dual.

KEGUNAAN

Dualitas : sebagai pengujian/pengecekan apakah nilai yang

dihasilkan dalam metode simpleks sudah benar dan hasilnya sudah dapat digunakan dalam pengambilan keputusan manajemen.

Sebagai Dasar dalam memahami analisis sensitivitas Analisis Sensitivitas :

Sebagai pengujian perhitungan apabila terjadi perubahan-perubahan (koefisien f. tujuan,koefisien kendala atau sumberdaya), agar tidak melakukan perhitungan mulai dari awal .

Untuk menentukan selang keoptimalan suatu masalah Program linear

Hubungan Primal-Dual

Hubungan Primal-Dual

Bentuk Primal

fungsi tujuan: maksimumkan

Z 40 1 60 2

fungsi kendala

3 1 2 2 2000

1 2 2 1000

1 2 0

x x

x x

x x

x ,x

Hubungan Primal-Dual

Produk

Proses Keuntungan

I II  

A 3 1 40

B 2 2 60

Kapasitas 2000 1000  

Hubungan Primal-Dual

Misalkan y1 dan y2 sebagai biaya sewa perjam yang harus dibebankan dalam setiap proses I dan II, maka biaya sewa total dari kedua macam proses tersebut adalah

Meminimumkan biaya sewa Maka keuntungan yang diinginkan tadi, merupakan

keuntungan minimal Sehingga permasalahan tersebut dapat dibuat

program linear dalam bentuk lain (Dual)

2000 1 1000 2w y y

Dualfungsi tujuan: minimumkan

2000 1 1000 2

fungsi kendala

3 1 2 40

2 1 2 2 60

1, 2 0

w y y

y y

y y

y y

Hubungan Primal-Dual

Bentuk umum masalah primal-dual

0,...2,1

...321

.........................................................

2...321

1...321

Kendala

...332211

nmaksimumka

Primal

321

2232221

1131211

xnxx

bmxnaxaxaxa

bxnaxaxaxa

bxnaxaxaxa

cnxnxcxcxcZ

mnmmm

n

n

Bentuk umum masalah primal-dual

11 21 31 1

12 22 32 2

1 2 3

Dual

minimumkan

1 1 2 2 3 3 ...

Kendala

1 2 3 ... 1

1 2 3 ... 2

.........................................................

1 2 3 ...

1, 2,.

m

m

n n n mn

w b y b y b y bmym

a x a x a x a xm c

a x a x a x a xm c

a x a x a x a xn cn

y y

.. 0ym

Korespondensi antara primal dan Dual Koefisien f.tujuan primal menjadi RHS dual, dan

RHS primal menjadi koefisien f.tujuan dual. Untuk setiap kendala primal ada satu variable dual,

dan untuk setiap variable primal terdapat satu kendala dual

Tanda ketaksamaan dalam pembatas tergantung fungsi tujuan

Fungsi tujuan berubah (primal : maksimasi, maka Dual:minimasi, sebaliknya)

Setiap kolom primal berkorespondensi dengan baris pada dual, dan sebaliknya

Dual dari dual akan kembali ke bentuk primal

Menentukan Dual dari PL

PL normal PL tidak normal

PL normal dan tidak

PL normal: jika untuk maksimasi, maka semua kendala

berbentuk ketaksamaan ≤ Jika untuk minimasi, semua kendala berbentuk ≥

PL tak normal: Jika untuk maksimasi atau minimasi terdapat

≤,=,atau ≥

Dual Dari PL normal

03,2,1

835,025,112

2035,12214

4832618

nberdasarka

320230160maks

Primal

xxx

xxx

xxx

xxx

xxxZDual

min 48 1 20 2 8 3

berdasarkan

8 1 4 2 2 3 60

6 1 2 2 1,5 3 30

1 1,5 2 0,5 3 20

1, 2, 3 0

w y y y

y y y

y y y

y y y

y y y

Dual Dari PL normalPrimal

min 50 1 20 2 30 3 80 4

berdasarkan

4 1 2 2 1,5 3 5 4 5

3 1 2 2 6

2 1 2 2 4 3 4 4 10

1, 2, 3, 4 0

Z x x x x

x x x x

x x

x x x x

x x x x

Dual

maks 5 1 6 2 10 3

berdasarkan

4 1 3 2 2 3 50

2 1 2 2 2 3 20

1,5 1 4 3 30

5 1 4 3 80

1, 2, 3 0

w y y y

y y y

y y y

y y

y y

y y y

Menentukan Dual dari PL tak Normal Untuk masalah maksimasi, jika kendala primal ke-

i bertanda ≥, maka variable dual ke-i akan memenuhi yi ≤0.

Untuk minimasi, jika kendala primal ke-i bertanda ≤, maka variable dual ke-i berlaku yi ≤0.

Jika kendala ke-i bertanda =, maka variable dual ke-i akan tidak terbatas dalam tanda

Jika variable primal ke-i tak terbatas dalam tanda, maka kendala ke-I dual berbentuk =

Dual PL tak normal

Dual PL tak normal

Untuk mengubah masalah PL yang tak nornal menjadi normal, lakukan langkah berikut: Kalikan dengan -1 untuk setiap kendala yang

bertanda ≥(untuk maksimasi) dan kendala yang bertanda ≤ (untuk minimasi)

Tanda = diganti dengan dua ketaksamaan ≤ dan ≥, kemudian lakukan langkah 1

Ganti variable yang tak terbatas dalam tanda dengan dimana xi’, xi” ≥0"' xixixi

Contoh

Fungsi tujuan : Minimumkan

3 1 2 3

F. Kendala

1 2 2 3 11

4 1 2 2 3 3

2 1 3 1

1, 2, 3 0

Z x x x

x x x

x x x

x x

x x x

tentukan bentuk dual

Contoh Ubah terlebih dahulu ke bentuk PL normal

Bentuk dualnya akan mempunyai 3 kendala dan 3 variable

Fungsi tujuan : Minimumkan

3 1 2 3

F. Kendala

F. Kendala

1 2 2 3 11

4 1 2 2 3 3

2 1 3 1

1, 2, 3 0

Z x x x

x x x

x x x

x x

x x x

Contoh Bentuk Dual

maximumkan w 11 1 3 2 3

kendala

1 4 2 2 3 3

2 1 2 1

1 2 2 3 1

1, 2 0

3 tak terbatas

y y y

y y y

y y

y y y

y y

y

Contoh

tentukan bentuk dual

maksimumkan 2 1 5 5 2

kendala

1 2 90

1 2 2 900

9 1 60 2 2700

2 1 6 2 450

1 2 0

z x , x

x x

x x

x x

x x

x ,x

Contoh Ubah terlebih dahulu ke bentuk PL normal

Bentuk dualnya akan mempunyai 2 kendala dan 4 variable

maksimumkan 2 1 5 5 2

kendala

1 2 90

1 2 2 900

9 1 60 2 2700

2 1 6 2 450

1 2 0

z x , x

x x

x x

x x

x x

x ,x

Contoh Bentuk Dual

minimumkan 90 1 900 2 2700 3 450 4

kendala

1 2 9 3 2 4 2

1 2 2 60 3 6 4 5,5

2, 3, 4 0

1 tak terbatas

w y y y y

y y y y

y y y y

y y y

y

Latihan

Tentukan bentuk dual dari

02,1

60021518

60022016

60025110:

2312

Primal.1

xx

xx

xx

xxsyarat

xxzmaks

2.Primal

min 5 1 6 2

: 1 2 2 5

1 5 2 5

4 1 7 2 8

1, 2 0

z x x

syarat x x

x x

x x

x x

Latihan

Tentukan bentuk dual/primal dari

3.Primal

5 1 12 2 4 3

: 1 2 2 3 10

2 1 2 3 8

1, 2, 3 0

maks z x x x

syarat x x x

x x x

x x x

4.Primal

min 5 1 2 2

: 1 2 3

2 1 3 2 5

1, 2 0

z x x

syarat x x

x x

x x

5.maximumkan 1 2 2 3 3 4 4

kendala

1 2 2 2 3 3 4 25

2 1 2 3 3 2 4 15

1 2, 3, 4 0

z x x x x

x x x x

x x x x

x ,x x x

Latihan

Variable tak terbatas Variable tak terbatas adalah variable yang

bisa bernilai negatif ataupun positif. Dalam metode simpleks, nilai negatif tidak

diperbolehkan, maka setiap masalah yang memiliki variable negatif harus diubah ke dalam suatu masalah dengan variable positif.

Maka untuk variable yang tak terbatas, harus didefinisikan sebagai selisih 2 variable yang positif sebagai berikut:

Xj=Xj’-Xj” dengan Xj’, Xj” ≥ 0

Arti variable dalam dual

yi adalah besaran yang menyatakan peningkatan nilai z-optimal sebagai akibat dari perubahan bi sebesar 1 unit.