Teori Dualitas | Primal-Dual

Teori Dualitas Primal-Dual

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

Konsep Dualitas

Konsep dualitas merupakan 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 primal 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 Z Umumnya notasi fungsi tujuan adalah W
2Umumnya notasi variabel keputusan dalam bentuk X Umumnya notasi variabel keputusan adalah Y
3Unsur koefisien matriks pembatas Transpose 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
3Pembatas ke-i berupa “≥”Yi ≤ 0
4Xj ≥ 0Pembatas ke-j berupa “≥”
5Xj ≤ 0Pembatas ke-j berupa “≤”

Fungsi tujuan berbentuk minimasi:

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

Hubungan Persoalam Primal dengan Dual

  1. Koefisien fungsi tujuan primal menjadi konstanta 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 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, S2 ≥ 0

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, S1 ≥ 0

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

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout /  Ubah )

Foto Google

You are commenting using your Google account. Logout /  Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout /  Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout /  Ubah )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.