Teori Dualitas
2
Konsep Dualitas • Setiap permasalahan LP mempunyai hubungan dengan permasalahan LP lain • Masalah dual adalah sebuah masalah LP yang diturunkan secara matematis dari satu model LP primal
3
Bentuk Standar Masalah Primal n
Masalah Dual m
max Z c j x j ,
min W bi yi ,
ST :
ST :
j 1
m
n
a x j 1
ij
i 1
j
bi , i 1,2,..., m
x j 0, j 1,2,..., n
a i 1
ij
yi c j , j 1,2,..., n
yi tak dibatasi 1 4
Bentuk Standar Masalah Primal n
Masalah Dual m
min Z c j x j ,
max W bi yi ,
ST :
ST :
j 1
m
n
a x j 1
ij
i 1
j
bi , i 1,2,..., m
x j 0, j 1,2,..., n
a i 1
ij
yi c j , j 1,2,..., n
yi tak dibatasi 1 5
Aturan-aturan (Hillier & Lieberman)
• Koefisien fungsi tujuan dari permasalahan primal adalah ruas kanan kendala fungsional pada permasalahan dualnya • Ruas kanan kendala fungsional pada permasalahan primal merupakan koefisien fungsi tujuan pada permasalahan dualnya • Koefisien variabel kendala fungsional pada permasalahan primal menjadi koefisien pada kendala fungsional pada permasalahan dualnya 6
Aturan-aturan (Taha) • Untuk setiap batasan primal terdapat sebuah variabel dual • Untuk setiap variabel primal terdapat sebuah batasan dual • Koefisien batasan dari sebuah variabel primal membentuk koefisien sisi kiri dari batasan dual yang bersesuaian; dan koefisien tujuan dari variabel yang sama menjadi sisi kanan dari batasan dual 7
Masalah dual diperoleh secara simetris dari masalah primal Variabel Primal
Sisi kanan dari batasan dual
Koefisien sisi kiri dari batasan dual
x1
x2
…
xj
…
xn
c1
c2
…
cj
…
cn
a11
a12
…
a1j
…
a1n
b1
y1
a21
a22
…
a2j
…
a2n
b2
y2
:
:
:
:
:
am1
am2
amn
bm
ym
: …
amj
…
↑ Batasan dual ke-j
Variabel dual
↑ tujuan dual 8
Hubungan Primal-Dual Tujuan Primal Tujuan Standar Maksimisas Minimisasi i Maksimisas Minimisasi i
Dual Batasan ≥ ≤
Variabel Tidak dibatasi Tidak dibatasi
9
Contoh: • Primal Max z = 5 x1 + 12 x2 + 4 x3 x1 + 2 x2 + x3 ≤ 10 2 x1 x2 + 3 x3 = 8 x1, x2, x3 ≥ 0
10
Contoh: • 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
11
Contoh: • Dual Min W = 10 y1 + y1 + 2 y1 y1 + y1 + y1,
8 y2 2 y2 ≥ 5 y2 ≥ 12 3 y2 ≥ 4 0 y2 ≥ 0 (y1 ≥ 0) y2 tak dibatasi
12
Pemecahan Masalah Dual 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 dalam masalah maksimisasi)
2.
≤
(nilai tujuan dalam masalah minimisasi)
Di pemecahan optimum untuk kedua masalah (nilai tujuan dalam = (nilai tujuan dalam masalah maksimisasi) masalah minimisasi)
13
Contoh Primal Min z = 5 x1 + 2 x2 ST x1 – x2 ≥ 3 2 x1 + 3 x2 ≥ 5 x1, x2 ≥ 0
Dual Max w = 3 y1 + 5 y2 ST y1 + 2 y2 ≤ 5 - y1 + 3 y2 ≤ 2 - y1 ≤ 0 (y1 ≥ 0) - y2 ≤ 0 (y2 ≥ 0) 1 14
Contoh Primal (min) Pemecahan Layak x1 = 3 x2 = 0
Dual (max) Pemecahan Layak y1 = 3 y2 = 1
Nilai tujuan z = 15
Nilai tujuan w = 14 1 15
Contoh Primal (min)
Dual (max)
Pemecahan Tak Layak x1 = 3 x2 = 1
Pemecahan Tak Layak y1 = 4 y2 = 1
Nilai tujuan z = 17
Nilai tujuan w = 17
1 16
Contoh Primal Pemecahan Optimal x1 = 3 x2 = 0
Dual Pemecahan Optimal y1 = 5 y2 = 0
Nilai tujuan z = 15
Nilai tujuan w = 15 1 17
Programa Dual Hubungan antara PRIMAL dan DUAL adalah sebagai berikut : PRIMAL
DUAL
RHS
Fungsi Tujuan
MAX
MIN
Constrain
Variable
Programa Dual x2 a12
xn a1n
RHS b1
y2
a21
a22
a2n
b2
ym
am1 c1
am2 c2
bm
amn cn
Koefisien Fungsi Objektif (Maksimisasi)
Koefisien Fungsi Objektif (Minimisasi)
y1
x1 a11
DUAL
PRIMAL
Contoh Programa Dual PRIMAL : Max s.t.
3x1 + 5x2
4 2x2 12 3x1 + 2x2 18 x1, x2 0 Min 4y1 + 12y2 + 18y3 s.t. y1 + 3y3 3 2y2 + 2y3 5 y1, y2 , y3 0 x1
DUAL :
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
Unrestricted
=
=
Unrestricted
Constraint
MAKSIMASI
Variable
Constraint
Variable
MINIMASI
Contoh PRIMAL : Max s.t.
DUAL :
8x1 + 3x2
x1 – 6x2 4 5x1 + 7x2 = – 4 x1 0 x2 0 Min 4w1 – 4w2 s.t. w1 + 5w2 8 – 6w1 + 7w2 3 w1 0 w2 unrestricted
Contoh 2 Primal: Max. z = 3x1 + 2x2 subject to 2x1 + x2 100 x1 + x2 80 x1 40 x1, x2 0
(Obj. Func.) (Finishing constraint) (Carpentry constraint) (Bound on soldiers)
Optimal Solution: z = 180, x1 = 20, x2 = 60
Dual : Min. w = 100y1 + 80y2 + 40y3 subject to 2y1 + y2 + y3 3 y1 + y2 2 y1, y2, y3 0
(Obj. Func.)
Hubungan PRIMAL – DUAL DUAL Constraint
yAc x 0 y Ax cx
Ax b y b cx Bila x adalah feasible terhadap PRIMAL dan y feasible terhadap DUAL, maka cx yb Nilai objektif problem Max Nilai objektif problem Min
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 z
Menyelesaikan DUAL
DUAL FR PRIMAL FR
Menyelesaikan PRIMAL
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 dan semuanya adalah variabel slack, tetapi dapat dipecahkan tanpa menggunakan variabel buatan yaitu dengan menggunakan metode dual simplex • Dalam prosedur dual simplex, pemecahan dimulai tidak layak dan optimal (sebagaimana diperbandingkan dengan metode primal simplex yang memulai layak tetapi nonoptimal)
Dual Simplex • Gagasan umum dari prosedur dual simplex adalah bahwa sementara iterasi dimulai tidak layak dan (lebih baik daripada) optimal, iterasi berikutnya bergerak ke arah ruang layak tanpa kehilangan sifat optimalitas (simpleks biasa mempertahankan kelayakan sementara bergerak ke arah optimalitas) • Pada iterasi dimana pemecahan menjadi layak untuk pertama kalinya, proses tersebut berakhir
Dual Simplex • Kondisi Kelayakan: – Variabel keluar adalah variabel dasar yang memiliki nilai paling 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 absolut terkecil dari rasio jika memaksimumkan (jika sama, tentukan sembarang). – Rasio ditentukan dengan membagi koefisien sisi kiri persamaan z dengan koefisien negatif yang bersesuaian dalam persamaan dengan koefisien negatif yang bersangkutan dengan variabel keluar. – Jika semua penyebut adalah nol atau positif, tidak terdapat pemecahan yang layak
Contoh 1 Min z = 3 x1 + 2 x2
3 x1 + x2 ≥ 4 x1 + 3 x2 ≥ x1 + x2 ≤ x1, x2 ≥
3 6 3 0
Contoh 1 Min z - 3 x1 - 2 x2 = 0
-3 x1 x2 + s1 = -4 x1 - 3 x2 + s2 = x1 + x2 + s3 = x1, x2, s1, s2, s3 ≥
-3 -6 3 0
Contoh 1 Dasar z s1 s2 s3 rasio
z 1 0 0 0
x1 -3 -3 -4 -1 3/4
x2 -2 -1 -3 1 2/3
s1 0 1 0 0 ~
s2 0 0 1 0 ~
s3 0 0 0 1 ~
RHS 0 -3 -6 3
Dasar z s1 x2 s3 rasio
z 1 0 0 0
x1 -1/3 -5/3 4/3 -1/3 1/5
x2 0 0 1 0 ~
s1 0 1 0 0 ~
s2 -2/3 -1/3 -1/3 1/3 2
s3 0 0 0 1 ~
RHS 4 -1 2 1
Dasar z x1 x2 s3
z 1 0 0 0
x1 0 1 0 0
x2 0 0 1 0
s1 -1/5 -3/5 4/5 -1/5
s2 -3/5 1/5 -3/5 2/5
s3 0 0 0 1
RHS 21/5 3/5 6/5 6/5
Contoh 1 • X1 = 3/5 • X2 = 6/5 • Z = 21/5
1
Contoh 2 Max z = 2 x1 - x2
x1 + x1,
x2 = 1 2 x2 ≥ 1 x2 ≥ 0
Contoh 2 Max 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
Contoh 2 Dasar z x1 s1 rasio
z 1 0 0
x1 0 1 0 ~
x2 3 1 -2 1 1/2
s1 0 0 1 ~
RHS 2 1 -1
Dasar z x1 x2
z 1 0 0
x1 0 1 0
x2 0 0 1
s1 1 1/2 1/2 -1/2
RHS 1/2 1/2 1/2
• X1 = ½ • X2 = ½ • Z=½ 1
