Wednesday, May 3, 2017

Teori Dualitas | Primal-Dual

teori dualitas
Tidak lama susudah program linear berkembang, baru disadari bahwa setiap kali sebuah persoalan porgram linear dirumuskan selalu terdapat sebuah persoalan program linear lainya yang mempunyai hubungan sangat erat dengan persoalan pertama.

Konsep Dualitas

Konsep dualitas meruapakan suatu konsep bagian dari program linear yang sangat penting dan menarik untuk dibahas. Konsep ini menyatakan dalam setiap masalah program linear mempunyai dua bentuk yang saling berhubungan dan keterkaitan.

Dapat pula diartikan sebagai "lawan dari", maksudnya apabila terdapat persamaan mula-mula dalam bentuk promal maka mempunyai lawan dalam bentuk dual, jika bentuk dual itu dianggap sebagai primal maka bentuk dualnya adalah persamaan mula-mula tersebut diatas.

Bentuk pertama (asli) dinamakan primal, sedangkan bentuk kedua adalah dual. Apabila dalam solusi optimum pada tabel simpleks bentuk asli (primal) telah terpecahkan, maka tabel simpleks optimum tersebut dapat juga menjawab permasalahan dualnya.


Ketentuan Bentuk Primal-Dual

Terdapat beberapa ketentuan awal yang harus dipahami sebelum masuk dalam konsep primal-dual untuk kasus program linear maksimasi dan minimasi.

Adapun ketentuan primal dan dualnya sebagai berikut :
No.Bentuk PrimalBentuk Dual
1Umumnya notasi fungsi tujuan adalah ZUmumnya notasi fungsi tujuan adalah W
2Umumnya notasi variabel keputusan dalam bentuk XUmumnya notasi variabel keputusan adalah Y
3Unsur koefisien matriks pembatasTranspose koefisien matriks pembatas
4Vektor ruas kanan pada kendalaKoefisien fungsi tujuan
5Koefisien fungsi tujuanVektor ruas kanan pada kendala
6Pembatas ke-i berupa "="Yi tidak terbatas dalam tanda
7Xj tidak terbatas dalam tandaPembatas ke-j berupa "="

Fungsi tujuan berbentuk maksimasi : 
No.Bentuk PrimalBentuk Dual
1Fungsi tujuan berbentuk maksimasiFungsi tujuan berbentuk minimasi
2Pembatas ke-i berupa "≤"Yi ≥ 0
2Pembatas ke-i berupa "≥"Yi ≤ 0
4Xj ≥ 0Pembatas ke-j berupa "≥"
5Xj ≤ 0Pembatas ke-j berupa "≤"

Fungsi tujuan berbentuk minimasi : 
No.Bentuk PrimalBentuk Dual
1Fungsi tujuan berbentuk minimasiFungsi tujuan berbentuk maksimasi
2Pembatas ke-i berupa "≤"Yi ≤ 0
2Pembatas ke-i berupa "≥"Yi ≥ 0
4Xj ≥ 0Pembatas ke-j berupa "≤"
5Xj ≤ 0Pembatas ke-j berupa "≥"

Hubungan persoalan primal dengan dual :

  1. Koefisien fungsi tujuan primal menjadi konstantan ruas kanan persoalan dual. Sedangkan konstanta ruas kanan primal menjadi koefisien fungsi tujuan bagi dual.
  2. Untuk setiap pembatas primal ada satu variabel dual. Dan untuk setiap variabel primal ada satu pembatas dual.
  3. Setiap variabel primal berkorespondensi dengan pembatas dual. Dan setiap pembatas primal berkorespondensi dengan variabel dual.
  4. Fungsi tujuan berubah bentuk yaitu maksimasi menjadi minimasi dan sebaliknya. Sedangkan tanda ketidaksamaan bergantung pada fungsi tujuan yaitu maksimum dual bertanda ≤, minimum dual bertanda ≥.
  5. Dual dari dual adalah primal.

Contoh :


Contoh 1 :

Primal : 
Kendala :
4 X1 + 8 X2 + 5 X3 ≤ 80
9 X1 + 6 X2 + 8 X3 ≤ 108
X1, X2, X3 ≥ 0

Bentuk standar :
Maksimumkan : Z = 5 X1 + 8 X2 + 6 X3 + 0S1 + 0 S2
Kendala :
4 X1 +8 X2 +5 X3 +S1= 80
9 X1 +6 X2 +8 X3+ S2 = 108
X1, X2, X3, S1, S20

Dual :
Minimumkan : W = 80 Y1 + 108 Y2
Kendala :
4 Y1 + 9 Y2 ≥ 5
8 Y1 + 6 Y2 ≥ 8
5 Y1 + 8 Y2 ≥ 6
Y1 ≥ 0
Y2 ≥ 0

Contoh 2 :

Primal :
Maksimumkan : Z = 4 X1 + 6 X2 + 5 X3
Kendala :
2 X1 + 4 X2 + X3 ≤ 40
X1 + X2 + 3 X3 = 48
X1, X2, X3 ≥ 0

Bentuk Standar :
Maksimumkan : Z = 4 X1 + 6 X2 + 5 X3 + 0 S1
Kendala :
2 X1 +4 X2 +X3 +S1= 40
X1 +X2 +3 X3= 48
X1, X2, X3, S10

Dual :
Minimumkan : W = 40 Y1 + 48 Y2
Kendala :
2 Y1 + Y2 ≥ 4
4 Y1 + Y2 ≥ 6
Y1 + 3 Y2 ≥ 5
Y1 ≥ 0
Y2 tidak terbatas dalam tanda


EmoticonEmoticon