riset operasi 7
TRANSCRIPT
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.