teori dualitasradiasari.lecture.ub.ac.id/files/2017/11/9-dualitas-dan-dual-simplex.pdf · konsep...
Post on 23-Oct-2020
9 Views
Preview:
TRANSCRIPT
-
Teori Dualitas
2
-
Konsep Dualitas
3
• Setiap permasalahan LP mempunyaihubungan dengan permasalahan LP lain
• Masalah dual adalah sebuah masalah LP yang diturunkan secara matematis dari satumodel LP primal
-
1
Bentuk Standar
Masalah Primal Masalah Dual
4
njx
mibxa
ST
xcZ
j
i
n
j
jij
n
j
jj
,...,2,1,0
,...,2,1,
:
,max
1
1
dibatasi tak
,...,2,1,
:
,min
1
1
i
j
m
i
iij
m
i
ii
y
njcya
ST
ybW
-
1
Bentuk Standar
Masalah Primal Masalah Dual
5
njx
mibxa
ST
xcZ
j
i
n
j
jij
n
j
jj
,...,2,1,0
,...,2,1,
:
,min
1
1
dibatasi tak
,...,2,1,
:
,max
1
1
i
j
m
i
iij
m
i
ii
y
njcya
ST
ybW
-
Aturan-aturan (Hillier & Lieberman)
6
• Koefisien fungsi tujuan dari permasalahanprimal adalah ruas kanan kendalafungsional pada permasalahan dualnya
• Ruas kanan kendala fungsional padapermasalahan primal merupakan koefisienfungsi tujuan pada permasalahan dualnya
• Koefisien variabel kendala fungsional padapermasalahan primal menjadi koefisienpada kendala fungsional padapermasalahan dualnya
-
Aturan-aturan (Taha)
7
• Untuk setiap batasan primal terdapatsebuah variabel dual
• Untuk setiap variabel primal terdapatsebuah batasan dual
• Koefisien batasan dari sebuah variabelprimal membentuk koefisien sisi kiri daribatasan dual yang bersesuaian; dankoefisien tujuan dari variabel yang samamenjadi sisi kanan dari batasan dual
-
Masalah dual diperoleh secarasimetris dari masalah primal
8
Variabel Primal
x1 x2 … xj … xn
Sisi kanan daribatasan dual
c1 c2 … cj … cn
Koefisien sisi kiridari batasan dual
a11 a12 … a1j … a1n b1 y1
Variabeldual
a21 a22 … a2j … a2n b2 y2
: : : : : :
am1 am2 … amj … amn bm ym
↑
Batasan dual ke-j↑
tujuan dual
-
Hubungan Primal-Dual
9
TujuanPrimalStandar
Dual
Tujuan Batasan Variabel
Maksimisasi
Minimisasi ≥Tidak
dibatasi
MinimisasiMaksimisas
i≤
Tidakdibatasi
-
Contoh:
10
• Primal
Max z = 5 x1 + 12 x2 + 4 x3
x1 + 2 x2 + x3 ≤ 10
2 x1 - x2 + 3 x3 = 8
x1, x2, x3 ≥ 0
-
Contoh:
11
• Primal Standar
Max z = 5 x1 + 12 x2 + 4 x3
x1 + 2 x2 + x3 + s1 = 10
2 x1 - x2 + 3 x3 = 8
x1, x2, x3, s1 ≥ 0
-
Contoh:
12
• Dual
Min W = 10 y1 + 8 y2
y1 + 2 y2 ≥ 5
2 y1 - y2 ≥ 12
y1 + 3 y2 ≥ 4
y1 + 0 y2 ≥ 0 (y1 ≥ 0)
y1, y2 tak dibatasi
-
Pemecahan Masalah Dual
13
Nilai tujuan dalam satu pasangan masalah primal dan dual harus memenuhi hubungan berikut
1. Untuk setiap pasangan pemecahan primal dan dual yang layak
(nilai tujuan dalammasalah maksimisasi)
≤ (nilai tujuan dalammasalah minimisasi)
2. Di pemecahan optimum untuk kedua masalah
(nilai tujuan dalammasalah maksimisasi)
= (nilai tujuan dalammasalah minimisasi)
-
1
Contoh
Primal Dual
14
Min z = 5 x1 + 2 x2
ST
x1 – x2 ≥ 3
2 x1 + 3 x2 ≥ 5
x1, x2 ≥ 0
Max w = 3 y1 + 5 y2
ST
y1 + 2 y2 ≤ 5
- y1 + 3 y2 ≤ 2
- y1 ≤ 0 (y1 ≥ 0)
- y2 ≤ 0 (y2 ≥ 0)
-
1
Contoh
Primal (min) Dual (max)
15
Pemecahan Layak
x1 = 3
x2 = 0
Nilai tujuan
z = 15
Pemecahan Layak
y1 = 3
y2 = 1
Nilai tujuan
w = 14
-
1
Contoh
Primal (min) Dual (max)
16
Pemecahan Tak Layak
x1 = 3
x2 = 1
Nilai tujuan
z = 17
Pemecahan Tak Layak
y1 = 4
y2 = 1
Nilai tujuan
w = 17
-
1
Contoh
Primal Dual
17
Pemecahan Optimal
x1 = 3
x2 = 0
Nilai tujuan
z = 15
Pemecahan Optimal
y1 = 5
y2 = 0
Nilai tujuan
w = 15
-
Programa Dual
Hubungan antara PRIMAL dan DUAL adalah sebagai berikut :
PRIMAL DUAL
RHS Fungsi Tujuan
MAX MIN
Constrain Variable
-
Programa Dual
x1 x2 xn RHS
y1 a11 a12 a1n b1
y2 a21 a22 a2n b2
ym am1 am2 amn bm
c1 c2 cn
Koefisien Fungsi Objektif
(Maksimisasi)
Ko
efi
sie
n F
un
gs
i
Ob
jek
tif
(Min
imis
as
i)
PRIMALD
UA
L
-
Contoh Programa DualPRIMAL : Max 3x1 + 5x2
s.t.
x1 4
2x2 12
3x1 + 2x2 18
x1, x2 0
DUAL : Min 4y1 + 12y2 + 18y3s.t.
y1 + 3y3 3
2y2 + 2y3 5
y1, y2 , y3 0
DUAL dari DUAL adalah PRIMAL
-
Primal of Diet problem
-
Diet Problem – Dual
-
PRIMAL – DUAL
Secara umum hubungan antara DUAL dan PRIMAL dapat digambarkan seperti pada tabel di bawah ini
MINIMASI MAKSIMASI
Unrestricted =
= Unrestricted
Vari
ab
le
Va
ria
ble
Co
nstr
ain
t
Co
nstr
ain
t
-
Contoh 2
Primal: Max. z = 3x1 + 2x2 (Obj. Func.)
subject to
2x1 + x2 100 (Finishing constraint)
x1 + x2 80 (Carpentry constraint)
x1 40 (Bound on soldiers)
x1, x2 0
Optimal Solution: z = 180, x1 = 20, x2 = 60
Dual : Min. w = 100y1 + 80y2 + 40y3 (Obj. Func.)
subject to
2y1 + y2 + y3 3
y1 + y2 2
y1, y2, y3 0
-
Hubungan PRIMAL – DUAL
Bila x adalah feasible terhadap PRIMAL dan yfeasible terhadap DUAL, maka cx yb
Nilai objektif problem Max Nilai objektif problem Min
DUAL Constraint y A c
x 0 y Ax cx
Ax b y b cx
-
Teorema Dualitas
● Bila x* adalah penyelesaian dari PRIMAL dan y*
adalah penyelesaian dari DUAL, maka cx* = y*b
● Bila x0 feasible terhadap PRIMAL dan y0 feasible terhadap DUAL sedemikian hingga cx0 = y0b, maka x0 dan y0 adalah penyelesaian optimal
Menyelesaikan
PRIMAL
Menyelesaikan
DUAL
zDUAL FR
PRIMAL FR
Optimal
(PRIMAL – DUAL FEASIBLE)
-
Teorema Dualitas
1. P optimal D optimal
2. P tak terbatas
D tak terbatas
D tidak feasible
P tidak feasible
3. P tidak feasible
D tidak feasible
D tak terbatas/tidak feasible
P tak terbatas/tidak feasible
-
Dual Simplex
-
Dual Simplex• Sekelompok masalah LP yang tidak memiliki
pemecahan dasar awal yang layak dansemuanya adalah variabel slack, tetapi dapatdipecahkan tanpa menggunakan variabelbuatan yaitu dengan menggunakan metodedual simplex
• Dalam prosedur dual simplex, pemecahandimulai tidak layak dan optimal (sebagaimanadiperbandingkan dengan metode primal simplex yang memulai layak tetapinonoptimal)
-
Dual Simplex• Gagasan umum dari prosedur dual simplex
adalah bahwa sementara iterasi dimulai tidaklayak dan (lebih baik daripada) optimal, iterasiberikutnya bergerak ke arah ruang layak tanpakehilangan sifat optimalitas (simpleks biasamempertahankan kelayakan sementarabergerak ke arah optimalitas)
• Pada iterasi dimana pemecahan menjadi layakuntuk pertama kalinya, proses tersebutberakhir
-
Dual Simplex• Kondisi Kelayakan:
– Variabel keluar adalah variabel dasar yang memiliki nilaipaling negatif (jika sama, tentukan secara sembarang).
– Jika semua variabel dasar adalah nonnegatif, proses berakhir.
• Kondisi Optimalitas:– Variabel masuk adalah variabel nondasar yang berkaitan
dengan rasio terkecil jika meminimumkan atau nilai absolutterkecil dari rasio jika memaksimumkan (jika sama, tentukan sembarang).
– Rasio ditentukan dengan membagi koefisien sisi kiripersamaan z dengan koefisien negatif yang bersesuaiandalam persamaan dengan koefisien negatif yang bersangkutan dengan variabel keluar.
– Jika semua penyebut adalah nol atau positif, tidak terdapatpemecahan yang layak
-
Contoh 1Min z = 3 x1 + 2 x2
3 x1 + x2 ≥ 3
4 x1 + 3 x2 ≥ 6
x1 + x2 ≤ 3
x1, x2 ≥ 0
-
Contoh 1Min z - 3 x1 - 2 x2 = 0
-3 x1 - x2 + s1 = -3
-4 x1 - 3 x2 + s2 = -6
x1 + x2 + s3 = 3
x1, x2, s1, s2, s3 ≥ 0
-
Contoh 1Dasar z x1 x2 s1 s2 s3 RHS
z 1 -3 -2 0 0 0 0
s1 0 -3 -1 1 0 0 -3
s2 0 -4 -3 0 1 0 -6
s3 0 -1 1 0 0 1 3
3/4 2/3 ~ ~ ~
Dasar z x1 x2 s1 s2 s3 RHS
z 1 -1/3 0 0 -2/3 0 4
s1 0 -5/3 0 1 -1/3 0 -1
x2 0 4/3 1 0 -1/3 0 2
s3 0 -1/3 0 0 1/3 1 1
1/5 ~ ~ 2 ~
Dasar z x1 x2 s1 s2 s3 RHS
z 1 0 0 -1/5 -3/5 0 21/5
x1 0 1 0 -3/5 1/5 0 3/5
x2 0 0 1 4/5 -3/5 0 6/5
s3 0 0 0 -1/5 2/5 1 6/5
rasio
rasio
-
1
Contoh 1
• X1 = 3/5
• X2 = 6/5
• Z = 21/5
-
Contoh 2Max z = 2 x1 - x2
x1 + x2 = 1
2 x2 ≥ 1
x1, x2 ≥ 0
-
Contoh 2Max z - 2 x1 + x2 = 0
x1 + x2 = 1
- 2 x2 + s1 = -1
x1, x2 , s1 ≥ 0
========================================
x1 = 1 – x2, sehingga:
z – 2 (1 – x2) + x2 = 0
z + 3 x2 = 2
-
1
Contoh 2
• X1 = ½
• X2 = ½
• Z = ½
Dasar z x1 x2 s1 RHS
z 1 0 3 0 2
x1 0 1 1 0 1
s1 0 0 -2 1 -1
~ 1 1/2 ~
Dasar z x1 x2 s1 RHS
z 1 0 0 1 1/2 1/2
x1 0 1 0 1/2 1/2
x2 0 0 1 -1/2 1/2
rasio
top related