11/5/2008
DUALITAS DAN ANALISIS SENSITIVITAS Dr. Mohammad Abdul Mukhyi, SE., MM.
1
Primal Problem P minimize z = cx subject to Ax = b x≥0 Dual Problem maximize subject to
D v = πb πA ≤ c
optimum value is z*
optimum value is v*
Theorem. (Strong Duality) If both P and D are feasible, then z* = v*. 2
1
11/5/2008
Tabel Primal – Dual Linear Programming
X1
X2
Koefisien ……………
Xn
Y1
a11
a12
……………
a1n
Y1
a11
a12
……………
a1n
….
….
…...
….………… …..
Ym
am1
am2
……………. amn
≥ C1
≥ C2
…………… ≥ Cn
NK
NK ≤ b1 ≤ b2
≤ b1
Koefisien fungsi tujuan (maksimisasi)
koefisien
DUAL
PRIMAL
Koefisien fungsi tujuan (maksimisasi)
3
Tabel Hubungan antara primal - dual Primal (atau Dual)
Dual (atau Primal)
Batasan I
Variabel I
Fungsi tujuan
Nilai kanan
4
2
11/5/2008
The min cost flow problem and its dual Minimize
∑(i,j)∈∈A cijxij ∑j xij
-
and
xij ≥ 0 for all (i,j) Î A.
Minimize
∑
n i=1
∑k xki = bi
for all i Î N. Primal
π i bi
Dual
subject to π i − π j ≤ cij for all ( i , j ) ∈ A 5
MASALAH PRIMAL
MASALAH DUAL
MAX : Z = 3X1 + 5X2 S.T.: 2X1 ≤ 8 3X2 ≤ 15 6X1 + 5X2 ≤ 30 X1 >= 0 X2 >= 0
MIN : Y = 8Y1 + 15Y2 + 30Y3 S.T.: 2Y1 + 6Y3 ≥ 3 3Y2 + 5Y3 ≥ 5 Y1 ≥ 0 Y2 ≥ 0 Y3 ≥ 0
6
3
11/5/2008
PENYELESAIAN PRIMAL :
PENYELESAIAN DUAL
OBJECTIVE FUNCTION VALUE
OBJECTIVE FUNCTION VALUE
1)
27.5000000
1)
VARIABLE VALUE X1 .833333 X2 5.000000
REDUCED COST .000000 .000000
ROW SLACK OR SURPLUS DUAL PRICES 2) 6.333333 .000000 3) .000000 .833333 4) .000000 .500000
27.5000000
VARIABLE Y1 Y2 Y3
ROW PRICES 2) 3)
VALUE .000000 .833333 .500000
REDUCED COST 6.333333 .000000 .000000
SLACK OR SURPLUS .000000 .000000
DUAL -.833333 -5.000000
Kendala aktif
7
PENYELESAIAN TABEL DENGAN PRIMAL variabel Z dasar
X1
X2
X3
X4
X5
NK
Z
1
-3
-5
0
0
0
0
X3
0
2
0
1
0
0
8
X1
0
0
3
0
1
0
15
X5
0
6
5
0
0
1
30
Keterangan
8
4
11/5/2008
variabel dasar
Z
X1
X2
X3
X4
X5
NK
Z
1
-3
-5
0
0
0
0
X3
0
2
0
1
0
0
8
8/0 = ~
X1
0
0
3
0
1
0
15
15/3= 5
X5
0
6
5
0
0
1
30
30/5 = 6
variabel dasar
Z
X1
X2
X3
X4
X5
NK
Z
1
-3
0
0
5/3
0
25
X3
0
2
0
1
0
0
8
X2
0
0
1
0
1/3
0
5
X5
0
6
0
0
-5/3
1
5
Keterangan
Keterangan
9
variabel dasar
Z
X1
X2
X3
X4
X5
NK
Z
1
-3
0
0
5/3
0
25
X3
0
2
0
1
0
0
8
8/2 = 4
X1
0
0
1
0
1/3
0
5
5/0 = ~
X5
0
6
0
0
-5/3
1
5
5/6 = 5/6
variabel dasar
Z
X1
X2
X3
X4
X5
NK
Z
1
0
0
0
5/6
1/2
27½ nilai optimal
X3
0
0
0
1
5/9
-1/3
6⅓
X1
0
0
1
0
1/3
0
5
X5
0
1
0
0
-5/18
1/6
5/6
Keterangan
Keterangan
10
5
11/5/2008
Apabila batasan 1 : 3X2 ≤ 15 dirubah menjadi 3X2 ≤ 16 nilai nya akan tetap 6X
1
18X 18X
+ 5X
2
= 30 → x 3
3X
2
= 16 → x 5
1
+ 15 X
2
15X
2
= 90 = 80 = 10
1
10 5 = = 0 , 56 18 9
X1 =
5 ) + 5X 2 = 30 9 3 , 3 + 5 X 2 = 30 6(
5X
= 30 − 3 , 3
2
X
=
2
26 , 7 = 5 , 34 5
Z = (3 x 0,56)
+ (5 x 5,34)
Z = 1,67 + 26,7 = 28 , 37 ∆ Z = 28,37
- 27,5 = 0,87
11
Apabila batasan 3 : 6X1 + 5X2 ≤ 30 dirubah menjadi 6X1 + 5X2 ≤ 31 6X 18X
1
+ 5X
2
= 31 → x 3
3X
2
= 15 → x 5
1
+ 15 X
18X
= 93
2
15X
2
= 75 = 18
1
18 =1 18 = 31
X1 = 6(1) + 5X 6 + 5X
2
5X X
2
= 31 2
2
= 25 =
25 = 5 5
Z = (3 x 1) + (5 x 5) Z = 3 + 25 = 28 ∆ Z = 28 - 27,5 = 0,5
12
6
11/5/2008
Hubungan antara variabel-variabel Primal-Dual dalam Linear Programming Variabel Primal
Variabel Dual
Variabel asli : X1 Variabel Slack : Xn+i
Variabel surplus : Zj - Cj Variabel Asli : Yi Dimana i = 1,2, … m j = 1,2, … n
13
PENYIMPANGAN-PENYIMPANGAN DARI BENTUK STANDAR Konversi Bentuk Bukan Standar Menjadi Bentuk Standar Dalam Model Linear Programming
Bentuk bukan standar :
Bentuk standar :
Minimisasi Z
Maksimisas i - Z
n ∑ a X ≥b j = 1 ij j i n ∑ a X =b j = 1 ij j i Nilai X tidak terbatas j
n ∑ a X ≤ -b i j = 1 ij j n ∑ a X ≤b i j = 1 ij j n − ∑ a X ≤ -b i j = 1 ij j (X ' - X''), X' ≥ 0, X'' ≥ 0 j j j j
14
7
11/5/2008
Mencari bentuk dual dari suatu masalah dual Minimisasi Y0 = b 1 Y1 + b 2 Y2 + ...... + b m Ym s /t : a 11 Y11 + a 21 Y21 + ...... + a m1 Ym1 ≥ c 1 a 12 Y12 + a 21 Y22 + ...... + a m2 Ym1 ≥ c 2 a 1n Y1n + a 2n Y2n + ...... + a mn Ymn ≥ c n dan Y1 ≥ 0; Y2 ≥ 0,....... Ym ≥ 0
Maksimisasi (-Y0 ) = - b1 Y1 − b 2 Y2 − ...... − bm Ym
Perubahan ke dalam benuk standar
s /t : - a11Y11 − a21Y21 − ...... − am1Ym1 ≤ −c 1 - a12 Y12 − a 21Y22 − ...... − am2 Ym1 ≤ −c 2 - a1n Y1n − a 2n Y2n − ...... − amn Ymn ≤ −c n dan Y1 ≥ 0; Y2 ≥ 0,....... Ym ≥ 0 15
Dual dari dual tersebut (primal) Minimisasi (-Z) = - C 1X 1 − C 2 X 2 − ...... − C n X n s /t : - a11 X 11 − a 21 X 21 − ...... − a n1 X n1 ≥ -b 1 - a12 X 12 − a 21 X 22 − ...... − a n2 X n1 ≥ -b 2 - a1m Y1m − a 2m Y2m − ...... − a mn Ymn ≥ -b n dan X 1 ≥ 0; X 2 ≥ 0,....... X m ≥ 0
Minimisasi Z = C 1X 1 + C 2 X 2 + ...... + C n X n
Perubahan ke dalam bentuk standar
s /t : a 11 X 11 + a 21 X 21 + ...... + a n1 X n1 ≤ b1 a 12 X 12 + a 21 X 22 + ...... + a n2 X n1 ≤ b 2 a 1m Y1m + a 2m Y2m + ...... + a mn Ymn ≤ b n dan X 1 ≥ 0; X 2 ≥ 0,....... X m ≥ 0
16
8
11/5/2008
Dual dari suatu masalah dual tidak lain adalah masalah primalnya. Batasan yang mengandung tanda persamaan (=) diperilukan seperti layaknya batasan bertanda ≤; tetapi batasan non-negatif bagi dual variabel yang bersangkutan harus dihilangkan (yaitu variabel yang tidak terbatas nilainya). Menghilangkan batasan non-negatif pada masalah primal akan mengakibatkan perubahan batasan pada masalah dual menjadi bentuk persamaan (=) 17
Hubungan bentuk-bentuk Primal - Dual Masalah Primal (Dual) Max Z (atau Y0) Batasan i bentuk ≤ bentuk = Variabel Xj (atau Yj) Xj ≥ 0 Xj ≥ 0 dihilangkan
Masalah Dual (Primal) Min Y0 (atau Z) Variabel Xj (atau Yj) Yj ≥ 0 Yj ≥ 0 dihilangkan Batasan j bentuk ≥ bentuk =
18
9
11/5/2008
PRIMAL PROBLEM: maximize subject to
z=
3x1 + 4x2 +6x3 + 8x4 x1 + x2 + x3 + x4 2x1 + 3x2 +4x3 + 5x4 x1, x2, x3, x4
= = ≥
1 3 0
Observation 1. DUAL PROBLEM: minimize Subject to
y1 + 3y2 y1 + 2y2 ≥ 3 y1 + 3y2 ≥ 4 y1 + 4y2 ≥ 6 y1 + 5y2 ≥ 8
The constraint matrix in the primal is the transpose of the constraint matrix in the dual. Observation 2. The RHS coefficients in the primal become the cost coefficients in the dual. 19
PRIMAL PROBLEM: maximize subject to
z=
3x1 + 4x2 +6x3 + 8x4 x1 + x2 + x3 + x4 2x1 + 3x2 +4x3 + 5x4 x 1, x 2, x 3, x 4
DUAL PROBLEM: minimize
y1 + 3y2
Subject to
y1 + 2y2 ≥ 3
= = ≥
1 3 0
Observation 3. The cost coefficients in the primal become the RHS coefficients in the dual. Observation 4. The primal (in this case) is a max problem with equality constraints and non-negative variables
y1 + 3y2 ≥ 4 y1 + 4y2 ≥ 6 y1 + 5y2 ≥ 8
The dual (in this case) is a minimization problem with ≥ constraints and variables unconstrained in sign. 20
10
11/5/2008
OBJECTIVE FUNCTION VALUE 1) 4.66666700 VARIABLE X1 X2 X3 X4
VALUE .666667 .000000 .000000 .333333
REDUCED COST .000000 .666667 .333333 .000000
ROW SLACK OR SURPLUS 2) .000000 3) .000000
DUAL PRICES -.333333 1.666667
OBJECTIVE FUNCTION VALUE 1) 4.66666700 VARIABLE X1 X2 X3 X4
VALUE .666667 .000000 .000000 .333333
REDUCED COST .000000 .666667 .333333 .000000
ROW SLACK OR SURPLUS 2) .000000 3) .000000
DUAL PRICES -.333333 1.666667
21
Analisis Sensitivitas Karena terjadi perubahan-perubahan dalam variabelvariabel, apakah fungsi tujuan maupun fungsi kendala dengan cara memanfaatkan kaidah-kaidah primal-dual metode simplek semaksimal mungkin. Karena tujuannya adalah penyelesian optimal, maka analisis ini disebut pula Post Optimality. Perubahan-perubahan yang mungkin terjadi: 1. Keterbatasan kapasitas sumber (fungsi batasan). 2. Koefisien-koefisien fungsi tujuan. 3. Koefisien-koefisien teknis fungsi batasan 4. Penambahan variabel-variabel baru. 5. Penambahan batasan-batasan baru 22
11
11/5/2008
OBJECTIVE FUNCTION VALUE 1)
27.5000000
VARIABLE X1 X2
VALUE .833333 5.000000
REDUCED COST .000000 .000000
ROW SLACK OR SURPLUS 2) 6.333333 3) .000000 4) .000000
DUAL PRICES .000000 .833333 .500000
SENSITIVITY ANALYSIS
VARIABLE X1 X2
ROW 2 3 4
OBJ COEFFICIENT RANGES CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE 3.000000 3.000000 3.000000 5.000000 INFINITY 2.500000
RIGHTHAND SIDE RANGES CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 8.000000 INFINITY 6.333333 15.000000 3.000000 11.400000 30.000000 19.000000 5.000000 23
OBJECTIVE FUNCTION VALUE 1)
27.5000000
VARIABLE Y1 Y2 Y3
VALUE .000000 .833333 .500000
REDUCED COST 6.333333 .000000 .000000
ROW SLACK OR SURPLUS 2) .000000 3) .000000
DUAL PRICES -.833333 -5.000000
SENSITIVITY ANALYSIS? OBJ COEFFICIENT RANGES CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE 8.000000 INFINITY 6.333333 15.000000 3.000000 11.400000 30.000000 19.000000 5.000000
VARIABLE Y1 Y2 Y3
ROW 2 3
RIGHTHAND SIDE RANGES CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 3.000000 3.000000 3.000000 5.000000 INFINITY 2.500000
24
12
