Konsep Primal - Dual
Teori Dualitas Persoalan Primal dan Dual
Persoalan
Primal (asli) Persoalan Dual (kebalikan dari primal)
PRIMAL A. Fungsi Tujuan 1. Maksimisasi Laba PL gunakan Metode Simpleks (variabel Slack atau +S)
DUAL A. Fungsi Tujuan 1. Minimisasi Biaya PL gunakan Metode Simpleks Big-M (var. buatan atau +A)
Model program linier memiliki 2 bentuk, yaitu: Model
primal adalah bentuk asli dari suatu model program linier Model dual adalah bentuk alternatif yang dikembangkan dari model primal
Latar Belakang Setiap
permasalahan programa linier mempunyai problem yang kedua yang berhubungan dengannya. Satu problem disebut sebagai ‘primal’ dan yang lainnya disebut ‘dual’. Kedua problem sangat dekat berhubungan, sehingga solusi optimal disatu problem menghasilkan informasi yang lengkap untuk solusi optimal yang lainnya.
Kegunaan bagi pengambil keputusan adalah: Model
Primal akan menghasilkan solusi dalam bentuk jumlah laba yang diperoleh dari memproduksi barang ataupun biaya yang dibutuhkan untuk memproduksi barang. Model Dual akan menghasilkan informasi mengenai nilai (harga) dari sumber-sumber yang membatasi tercapainya laba tersebut.
Hubungan khusus antara primal dan dual adalah :
Variabel dual Y1 , Y2 , Y3 berhubungan dengan batasan model primal. Dimana untuk setia batasan dalam primal terdapat satu variabel dual. Misal, dalam kasus di atas model primal mempunyai 3 batasan, maka dualnya akan mempunyai 3 variabel keputusan. Nilai kuantitas pada sisi kanan pertidaksamaan pada model primal merupakan koefisien fungsi tujuan dual. Koefisien batasan model primal merupakan koefisien variabel keputusan dual. Koefisien fungsi tujuan primal, merupakan nilai kuantitas pada sisi kanan pertidaksamaan pada model dual. Pada bentuk standar, model maksimisasi primal memiliki batasan-batasan <, sedangkan model minimisasi dual memiliki batasan-batasan >.
Tabel Primal-Dual PL PRIMAL Koefisien
DUAL
X1
X2
. . . . . . Xn
NK
Y1 Y2 Y3 . Yn
a11 a21 a31 …. am1
a12 a22 a32 …. am2
. . . . . . a1n . . . . . . a2n . . . . . . a3n . . . . . . ….. . . . . . . amn
≤ b1 ≤ b2 ≤ b3 …… ≤ bm
NK
≥ C1
≥ C2 . . . . . . ≥ Cn
KOEFISIEN FUNGSI TUJUAN MAKSIMISASI
KOEFISIEN FUNGSI TUJUAN MINIMISASI
PRIMAL
F/t Max : Z = 2X1 + 3X2 F/k : 5X1 + 7X2 < 35 8X1 + 4X2 < 40 F/s : X 1 ; X2 > 0
F/t Max : Z = 2X1 + 3X2 + 0S1 + 0S2 F/k : 5X1 + 7X2 + S1 < 35 8X1 + 4X2 + S2 < 40 F/s : X 1 ; X 2 ; S 1 ; S2 > 0
DUAL F/t Min : Z* = 35X1 + 40X2 F/k : 5X1 + 8X2 > 2 7X1 + 4X2 > 3 F/s : X 1 ; X2 > 0
PRIMAL 2. Minimisasi Biaya : PL gunakan Simpleks Big-M (var.surplus –S dan var. buatan +A)
F/t Min : Z = 2X1 + 5X2 F/k : 3X1 + 4X2 > 24 5X1 + 6X2 > 30 F/s : X 1 ; X2 > 0
DUAL 2. Maksimisasi Laba : PL gunakan Simpleks (variabel slek +S)
F/t Max : Z = 24X1 + 30X2 F/k : 3X1 + 5X2 < 2 4X1 + 6X2 < 5 F/s : X1 ; X 2 > 0
Keterkaitan Konsep Primal - Dual Pada Analisa Sensitivitas Analisa
Sensitivitas mencakup investigasi pengaruh solusi optimal dalam melakukan perubahan nilai pada parameter model. Perubahan nilai parameter pada problem primal juga berhubungan dengan nilai pada problem dual nya. Dalam banyak hal akan lebih baik menganalisa problem dual secara langsung untuk menentukan pengaruh komplemennya pada problem primal.
Definisi Dari Dual Problem Maksimasi :
n
X0 cjxj j 1
n
Pembatas :
a x j 1
ij
xj 0
j
bi
i = 1, 2, … , m
j = 1, 2, … , n
Dual Problem Dalam Bentuk Kanonik Jika permasalahan mengacu sebagai ‘Primal’, hubungan dalam dualnya adalah sebagai berikut : Minimasi :
m
y0 bi yi i 1
m
Pembatas :
a x i 1
ij i
yj 0
cj
i = 1, 2, … , m j = 1, 2, … , n
y1, y2, … , ym : merupakan variabel dual
Problem Dual Bila Primal Dalam Bentuk Standard n
Maksimasi
x0 c j x j j 1 n
a
Pembatas
j 1
ij
Primal
x j bi
i = 1, 2, … , m
xj 0
j = 1, 2, … , n
Problem
n
Maksimasi
y0 bi yi i 1
Pembatas
m
a i 1
ij
yi c j
j = 1, 2, … , n
yi tidak dibatasi tanda untuk semua i
Dual Problem
Problem Dual Bila Primal Dalam Bentuk Standard n
Maksimasi
x0 c j x j j 1
n
a
Pembatas
j 1
ij
Primal
x j bi
i = 1, 2, … , m
Problem
xi tidak dibatasi tanda untuk semua i n
Maksimasi
y0 bi yi i 1
m
Pembatas
aij yi c j
j = 1, 2, … , n
yi 0
i = 1, 2, … , m
i 1
Dual Problem
Membentuk Dual Problem dari Primal Problem atau Sebaliknya Langkahnya sebagai berikut : 1. Tiap batasan di suatu problem berhubungan dengan variabel pada variabel lainnya. 2. Elemen pada RHS pembatas pada suatu problem sama dengan koefisien fungsi obyektif yang sesuai pada problem lainnya. 3. Satu problem empunyai tujuan maksimasi lainnya minimasi. 4. Problem maksimasi mempunyai pembatas ( ) dan minimasi mempunyai pembatas ( ). 5. Variabel untuk kedua problem adalah non-negatif.
Contoh : Maksimasi : X0 = 5 X1 + 6 X2 Pembatas : X1 + 9 X2 60 y1 2X1 + 3 X2 45 y2 5X1 - 2 X2 20 y3 X2 30 y4 X1, X2 0
Primal Problem
Minimasi : y0 = 60y1 + 45y2 + 20y3 + 30y4
Pembatas : y1 + 2 y2 + 5y3 60 9y1 + 3 y2 – 2y3 + y4 45 y1 ,y2 ,y3 ,y4 0
Dual Problem
Penyelesaian Dual Simplex Maksimasi : X0 = 2 X1 + X2 Pembatas : 3 X1 + X2 3 4 X1 + 3 X2 6 X1 +2 X2 3 X1, X2 0
Minimasi : X0 = 2 X1 + X2 Pembatas : -3 X1 - X2 3 - 4 X1 - 3 X2 6 X1 +2 X2 3 X1, X2 0
Dengan mengubah fungsi obyektif Maksimasi menjadi Minimasi dan fungsi pembatasnya menjadi bertanda , kemudian dibentuk tabel simpleksnya adalah sbb :
Penyelesaian Dual Simplex Metoda
Simpleks yang biasa, memberikan hasil didasarkan pada kondisi optimalitas dan layak (feasibility), sebagai berikut : Kondisi
Layak : ‘Leaving Variabel’ adalah variabel basis yang mempunyai nilai paling negatif. Kondisi Optimalitas : ‘Entering Variabel’ dipilih diantara non-variabel basis dengan cara Rasio
dari koefisien fungsi obyektif dengan koefisien pembatas yang terpilih sebagai ‘leaving var’. ‘Entering Var. adalah salah satu yang mempunyai rasio terkecil untuk problem minimasi, atau nilai terkecil absolut untuk problem maksimasi.
Penyelesaian Dual Simplex Merubah fungsi pembatas dari Ketidaksamaan kedalam bentuk Persamaan Minimasi : X0 = 2 X1 + X2 Pembatas : -3 X1 - X2 + S1 =-3 - 4 X1 - 3 X2 + S2 =-6 X1 +2 X2 + S3 = 3 X1, X2 0
Penyelesaian Dual Simplex Var Basis
X0
bj
S1
0
-3
S2
0
-6
S3
0
3
0
Koefisien dari X1 X2 S1 2 1 0
S2 0
S3 0
-3 -4 1
0 1 0
0 0 0
-2
-1 -3 2 -1
1 0 0 0
0
0
RHS Ratio
Leaving Variabel
Menentukan Rasio
Untuk Mendapatkan Entering Variabel Dengan Memilih Nilai Rasio Variabel
X1
X2
S1
S2
S3
X0 – equation -2
-1
0
0
0
S2 – equation -4
-3
0
1
0 (leaving var)
Rasio
1/2
1/3
X2 terpilih sebagai entering variabel karena merupakan nilai terkecil (minimasi problem)
Penyelesaian Dual Simplex Var Basis
X0
bj
S1 X2
0
-1
1
2
S3
0
Koefisien dari X1 X2 S1 2 1 0
S2 0
S3 0
-1
-5/3 4/3 -5/3
0 1 0
1 0 0
-1/3 -1/3 2/3
0 0 1
2
-2/3
0
0
-1/3
0
RHS Ratio
Leaving Variabel
Hasil optimal tapi belum feasibel maka dengan cara yang sama seperti iterasi sebelumnya dilakukan perhitungan untuk mendapatkan hasil yang optimal dan feasibel.
Penyelesaian Dual Simplex Var Basis
X0
bj
X1 X2
2
3/5
1
6/5
S3
0
Koefisien dari X1 X2 S1 -2 -1 0
S2 0
S3 0
0
1 0 0
0 1 0
-3/5 4/5 -1
1/5 -3/5 1
0 0 1
12/5
0
0
-2/5
-1/5
0
RHS Ratio
Nilai Optimal dan Feasible untuk permasalahan ini adalah : Maks X0 = Min X0 = 12/5, X2 = 3/5, X2 = 6/5
