Pertemuan 8 - 9

DUALITAS & SENSITIVITAS

 Masalah Dualitas.
LP  adalah masalah Primal ( bentuk aslinya )

Beberapa hal yang berkaitan dengan Dualitas:

• Menyusun Dual
• Pengertian ekonomis yang terkandung didalamnya
• Interpretasi  analisis masalah aslinya

Asumísi :
– Nilai bi  dapat positif/negatif.
– LP ada dalam bentuk standar
 Masalah Dualitas.

Primal .
Bentuk standar :
Maks Z = ∑ CjXj
Dengan batasan :
∑ aijxj ≤ bi dan Xj ≥ 0

i = 1 …………….m
 Masalah Dualitas.

Dual.
Fungsi Tujuan :
Min Yo = ∑biyi
Dengan pembatas :
∑ aijyi ≥ cj dan yi ≥ 0

dimana: j = 1…………..n
i = 1 ………….m
 Masalah Dualitas.
Tabel Primal – Dual dari LP;

X1 X2 ……… Xn NK

Y1 a11 a12………... a1n ≤b1 M

D in
Y2 a21 a22 ………....a2n ≤b2 i
U m
Koefision
Y3 a31 a32 ………....a3n ≤b3 u [Link]
A m
. .
k
.
L a
Ym am1 am2 . ......... amn ≤bm
n

NK ≥ C1 ≥C2 ≥Cm

Maksimumkan
Contoh:Primal – Dual

Variabel X1 X2 NK
Y1 2 0 ≤8

Y2 0 3 ≤ 15

Y3 6 5 ≤ 30

Z ≥3 ≥5

1. Batasan primal (dual) merupakan koefisien variabel

dual (primal).

2. Koefisien fungsi tujuan primal  nilai kanan dual.

Primal Dual:
Maks. Z = 3X1 + 5X2 Min. Yo = 8Y1 + 15Y2 + 30Y3

Dengan pembatas :

2X1 ≤ 8 2Y1 + 6Y3 ≥ 3

3X2 ≤ 15 3Y2 + 5Y3 ≥ 5
6X1 + 5X2 ≤ 30

X1≥ 0 Y1 ≥ 0
X2 ≥ 0 Y2 ≥ 0
Y3 ≥ 0
Jika masalah dual diselesaikan ; maka diperoleh :
Y1 = 0
Y2 = 5/6  Koefisien slack variabel pada primal
Y3 = ½ ( pada baris I  baris Z ).

Penyelesaian Dual dengan Simpleks.

Min. Yo = 8Y1 + 15Y2 + 30Y3
Maks. (-Yo) = -8Y1 - 15Y2 - 30Y3
Syarat:
2Y1 + 6Y3 ≥ 3
3Y2 + 5Y3 ≥ 5
Y1 ≥ 0
Y2 ≥ 0
Y3 ≥ 0
 Masalah Dualitas.
F. Pembatas:
2Y1 + 6Y3 – Y4 = 3
2Y1 + 6Y3 – Y4 + Y5 = 3

3Y2 + 5Y3 – Y6 = 5
3Y2 + 5Y3 – Y6 + Y7 = 5

Penyesuaian F. Tujuan :
Maks. (-Yo) = -8Y1 - 15Y2 - 30Y3 + 0Y4 - M5 + 0Y6 - MY7.

Maks. (-Yo) + 8Y1 + 15Y2 + 30Y3 - 0Y4 + M5 - 0Y6 + MY7 =0.

Penyesuaian nilai var. Dasar

Y1 Y2 Y3 Y4 Y5 Y6 Y7 NK
Y

8 15 30 0 M 0 M 0

M( ( 2 0 6 -1 1 0 0 3 )

M( ( 0 3 5 0 0 -1 1 5 )

(-2M+8) (-3M+15) (-11M+30) M 0 M 0 -8M

Tabel : 1

VD Y0 Y1 Y2 Y3 Y4 Y5 Y6 Y7 NK

Y0 -1 -2M+8 -3M+15 -11M+30 M 0 M 0 -8M

Y5 0 2 0 6 -1 1 0 0 3

Y7 0 0 3 5 0 0 -1 1 5
 Tabel : 2

VD Y0 Y1 Y2 Y3 Y4 Y5 Y6 Y7 NK

Y0 -1 5/3M-2 -3M+15 0 -5/6M+5 11/6M-5 M 0 -5/2M-15

Y3 0 1/3 0 1 -1/6 1/6 0 0 1/2

Y7 0 -5/3 3 0 5/6 -5/6 -1 1 5/2

Tabel : 3

VD Y0 Y1 Y2 Y3 Y4 Y5 Y6 Y7 NK

Y0 -1 19/3 0 0 5/6 M-5/6 M 0 -27.5

Y3 0 1/3 0 1 -1/6 1/6 0 0 1/2

Y2 0 -5/9 1 0 5/18 -5/18 -1/3 1/3 5/6

 Masalah Dualitas

Jadi :
Y1 = 0
Y2 = 5/6
Y3 = ½

Yo = 8Y1 + 15Y2 + 30Y3

= 8 . 0 + 15 . 5/6 + 30 . ½
= 0 + 12½ + 15
= 27½
Primal
Maks. Z = 3X1 + 5X2

Dengan pembatas :

2X1 ≤ 8
3Y2 + 5Y3 ≥ 5
6X1 + 5X2 ≤ 30

X1≥ 0
X2 ≥ 0
 Simpleks
Langkah pemecahan :
[Link] tujuan diubah menjadi fungsi
implicit dengan mengeser CjXij kekiri
tanda sama dengan (=).
Z = 3X1 + 5X2
Z - 3X1 - 5X2 = 0
2. F. Pembatas diubah menjadi bentuk
persamaan dengan menambah slack
variable ( var. yang menganggur).
 Simpleks
• Slack Var.  Xn+1; Xn+2; ………..Xn+m
• 2 X1 ≤ 8  2X1 + X3 = 8
• 3 X2≤ 15  3 X2 + X4 = 15
• 6X1 + 5X2 ≤ 30  6X1 + 5X2 + X5 = 30
Hasil Primal

VD Z X1 X2 X3 X4 X5 NK

Z 1 -3 -5 0 0 0 0
X3 0 2 0 1 0 0 8
X4 0 0 3 0 1 0 15
X5 0 6 5 0 0 1 30

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

Z Z 0 0 0 5/6 ½ 27 ½
X3 X3 0 0 1 5/9 -1/3 6 1/3
X2 X2 0 1 0 1/3 0 5
X1 X5 1 0 0 -5/18 1/6 5/6
 Masalah Dualitas

Z = 3X1 + 5X2
= 3 . 5/6 + 5 . 5
= 27 ½
 Dasar Teori Dualitas
• Notasi baris 1 (baris tujuan) tabel simpleks

Var. Z X1 X2 .. … Xn Xn+1 Xn+2 . … Xn+m NK

Dasar
Z 1 (Z1- C1) (Z2- C2) … (Zn-Cn) Y1 Y2 .. … Ym Yo