DUALITAS
Latihan
1. Mencari u , v , w tidak negatif yang memenuhi
2 u+3 v + 4 w ≤ 8
4 u−v−3 w ≥ 6
Dan memaksimukan f =−8 u+12 v+6 w , tuliskan dualnya!
Penyelesaian:
Primal:
Kendala
2 u+3 v + 4 w ≤ 8
4 u−v−3 w ≥ 6
Memaksimukan f x =−8u+ 12 v+ 6 w
Dan u , v , w ≥ 0
Semua batasan ≥ diubah menjadi ≤ dengan cara mengalikan kedua ruas dengan −1.
Karena yang akan dicari fungsi maksimum maka kendala kedua diubah menjadi:
−4 u+v +3 w ≤−6
Setelah merubah kendala kedua maka dapat disusun tabel dualitas sebagai berikut:
u v w Min g
x 2 3 4 ≤8
y −4 1 3 ≤−6
Maks f ≥−8 ≥ 12 ≥6
Maka dualnya dapat ditulis sebagai
Dual:
Mencari x , y tak negatif yang memenuhi
2 x−4 y ≥−8
3 x+ y ≥ 12
4 x+3 y ≥ 6
Meminimumkan g=8 x −6 y
Soal Latihan Untuk Diskusi
1. Diketahui soal primal:
Meminimumkan f =6 x +10 y+ 15 z
Dengan kendala:
2 x+ y + z ≥30
x +2 y +3 z ≥50
Menggunakan Dalil
x , y , z≥0
Penyelesaian:
Karena yang akan dicari fungsi minimum tidak ada kendala yang diubah, maka dapat disusun tabel
dualitas sebagai berikut:
x y z Max g
u 2 1 1 ≥ 30
v 1 2 3 ≥ 50
Min f ≤6 ≤ 10 ≤ 15
Maka dualnya dapat ditulis sebagai
Dual:
2 u+v ≤ 6
u+2 v ≤ 10
u+3 v ≤ 15
Memaksimumkan g=30u+ 50 v
Setelah soal dual diperoleh, selesaikan menggunakan metode grafik.
Dalam menyelesaikan soal menggunakan metode grafik, buat dua buah garis selidik f =250 dan f =200.
Kemudian didapatkan titik optimumnya yaitu ( u , v )= ( 23 , 143 ) dengan nilai program
g=30 ( 23 )+50 ( 143 )= 603 + 7003 = 7603 .
Selanjutnya, p.o soal primal akan dicari dengan dalil sebagai berikut.
2 14
Masukkan nilai u= dan v= ke dalam kendala-kendala utama pada soal dual.
3 3
(1) 2 ( 32 )+ 143 = 43 + 143 = 183 =6=6 (berupa persamaan)
2 14 2 28 30
(2)
3
+2 ( )
3
= + = =10=10
3 3 3
(berupa persamaan)
2 14 2 42 44
(3) +3 ( )= + = <15 (berupa pertidaksamaan)
3 3 3 3 3
2 14
Sedangkan nilai variabelnya u= >0 dan v= > 0 (berupa pertidaksamaan)
3 3
Dengan menggunakan dalil 4.4 maka keadaan optimum soal primal akan memuat
Soal Dual Soal Primal
Kendala (1) persamaan → Variabel ke-1 memenuhi pertidaksamaan ( x >0)
Kendala (2) persamaan → Variabel ke-2 memenuhi pertidaksamaan ( y >0 )
Kendala (3) pertidaksamaan → Variabel ke-3 memenuhi persamaan ( z=0 )
Variabel ke-1 memenuhi pertidaksamaan → Kendala ke-1 memenuhi persamaan
(u> 0) (2 x+ y+ z =30)
Variabel ke-2 memenuhi pertidaksamaan → Kendala ke-2 memenuhi persamaan
( v> 0) ( x +2 y+ 3 z=50)
Hubungan di atas secara ringkas dapat digambarkan dengan tabel dualitas sebagai berikut:
u>0 v> 0
0< x 2 1 ¿6
0< y 1 2 ¿ 10
0=z 1 3 ¿ 15
¿ 30 ¿ 50
Sehingga untuk penyelesaian bagi ( 4.4)/¿soal dual dapat dicari sebagai berikut:
Dari kendala 1 dan 2 diperoleh:
2 x+ y + z =30 Diperoleh penyelesaian
x +2 y +3 z=50 2 x+ y =30 ×2 4 x+2 y=60
Dari variabel ke-3 x +2 y =50 ×1 x +2 y =50
Diperoleh z=0 3 x=10
10
x=
3
10
Substitusikan x= ke persamaan 2 x+ y =30
3
2 ( 103 )+ y =30
20
+ y=30
3
20
y=30−
3
70
y=
3
Jadi p.o.( x , y , z )= ( 103 , 703 , 0 ), g maks =
760
3
760
Sedangkan berdasarkan Dalil 4.2 , gmaks=f min = .
3
Dengan demikian p.o ( 4.4)/¿dual diperoleh tanpa mengerjakan lewat simpleks.
2. Meminimumkan f =−6 x +12 y+ 6 z
x + y−z 10
−x +3 y−3 z ≥ 20
5 x – y+ 2 z ≤5
x ≥ 0 ; y ≥0 ; z ≥0
Penyelesaian:
Karena soal primal diselesaikan dengan metode simpleks, maka diperoleh tabel optimum sebagai
berikut.
Tabel Optimum
cj −6 12 6 0 0 0 M
ć i xj x y z s1 s2 s3 t bi Ri
x́ i
−6 x 1 0 0 5/ 4 1/4 0 −1/4 5/2 10
12 y 0 1 −1 1/4 −1/4 0 1/4 15/2 −20 /3
0 z 0 0 1 −7 /2 −3/2 1 3/2 0 1
zj −6 12 −12 −3/2 −9 /2 0 9 /2 75
z j −c j 0 0 −18 −3/2 −9 /2 0 9 /2−M 75
Dengan demikian, diperoleh p.o soal primal
( x , y , z )= ( 52 , 152 , 0 )dengan nilai programnya f min =75
Sehingga dapat disusun tabel dualitas dengan variabel dualnya u , v dan w sebagai berikut :
TABEL DUALITAS
x y z maks g
u -1 -1 1 ≥−10
v -1 3 -3 ≥ 20
w -5 1 -2 ≥−5
min f ≤−6 ≤ 12 ≤6
Maka, soal dualnya dapat ditulis sebagai berikut :
Menentukan u , v dan w tidak negatif yang memenuhi
u+ v+ 5 w 6
−u+3 v+ x ≤12
u – 3 v−2 w ≤ 6
Dan memaksimumkan g=−10u+ 20 v−5 w
Untuk menentukan p.o soal dual ini tidak perlu ada pengerjaan simpleks karena p.o tersebut sudah
−3 9
terdapat dalam tabel optimum primal yakni z j −c j= ,− ,0.
2 2
Oleh karena itu, diperoleh p.o soal dual
( −32 ,− 92 0.) Dengan nilai programnya g
(u , v , w)= maks =f min =75