Tidak usang sesusudah program linear berkembang, gres disadari bahwa setiap kali sebuah kasus jadwal linear dirumuskan selalu terdapat sebuah kasus jadwal linear lainya yang memiliki hubungan sangat dekat dengan kasus pertama.
Konsep Dualitas
Konsep dualitas merupakan suatu konsep bab dari jadwal linear yang sangat penting dan menarik untuk dibahas. Konsep ini menyatakan dalam setiap kasus jadwal linear memiliki dua bentuk yang saling bekerjasama dan keterkaitan.
Dapat pula diartikan sebagai "lawan dari", maksudnya apabila terdapat persamaan mula-mula dalam bentuk primal maka memiliki lawan dalam bentuk dual, bila bentuk dual itu dianggap sebagai primal maka bentuk dualnya ialah persamaan mula-mula tersebut diatas.
Bentuk pertama (asli) dinamakan primal, sedangkan bentuk kedua ialah dual. Apabila dalam solusi optimum pada tabel simpleks bentuk orisinil (primal) telah terpecahkan, maka tabel simpleks optimum tersebut sanggup juga menjawab permasalahan dualnya.
Ketentuan Bentuk Primal-Dual
Terdapat beberapa ketentuan awal yang harus dipahami sebelum masuk dalam konsep primal-dual untuk kasus jadwal linear maksimasi dan minimasi.
Adapun ketentuan primal dan dualnya sebagai berikut :
| No. | Bentuk Primal | Bentuk Dual |
|---|---|---|
| 1 | Umumnya notasi fungsi tujuan ialah Z | Umumnya notasi fungsi tujuan ialah W |
| 2 | Umumnya notasi variabel keputusan dalam bentuk X | Umumnya notasi variabel keputusan ialah Y |
| 3 | Unsur koefisien matriks pembatas | Transpose koefisien matriks pembatas |
| 4 | Vektor ruas kanan pada kendala | Koefisien fungsi tujuan |
| 5 | Koefisien fungsi tujuan | Vektor ruas kanan pada kendala |
| 6 | Pembatas ke-i berupa "=" | Yi tidak terbatas dalam tanda |
| 7 | Xj tidak terbatas dalam tanda | Pembatas ke-j berupa "=" |
Fungsi tujuan berbentuk maksimasi :
| No. | Bentuk Primal | Bentuk Dual |
|---|---|---|
| 1 | Fungsi tujuan berbentuk maksimasi | Fungsi tujuan berbentuk minimasi |
| 2 | Pembatas ke-i berupa "≤" | Yi ≥ 0 |
| 2 | Pembatas ke-i berupa "≥" | Yi ≤ 0 |
| 4 | Xj ≥ 0 | Pembatas ke-j berupa "≥" |
| 5 | Xj ≤ 0 | Pembatas ke-j berupa "≤" |
Fungsi tujuan berbentuk minimasi :
| No. | Bentuk Primal | Bentuk Dual |
|---|---|---|
| 1 | Fungsi tujuan berbentuk minimasi | Fungsi tujuan berbentuk maksimasi |
| 2 | Pembatas ke-i berupa "≤" | Yi ≤ 0 |
| 2 | Pembatas ke-i berupa "≥" | Yi ≥ 0 |
| 4 | Xj ≥ 0 | Pembatas ke-j berupa "≤" |
| 5 | Xj ≤ 0 | Pembatas ke-j berupa "≥" |
Hubungan kasus primal dengan dual :
- Koefisien fungsi tujuan primal menjadi konstanta ruas kanan kasus dual. Sedangkan konstanta ruas kanan primal menjadi koefisien fungsi tujuan bagi dual.
- Untuk setiap pembatas primal ada satu variabel dual. Dan untuk setiap variabel primal ada satu pembatas dual.
- Setiap variabel primal berkorespondensi dengan pembatas dual. Dan setiap pembatas primal berkorespondensi dengan variabel dual.
- Fungsi tujuan berubah bentuk yaitu maksimasi menjadi minimasi dan sebaliknya. Sedangkan tanda ketidaksamaan bergantung pada fungsi tujuan yaitu maksimum dual bertanda ≤, minimum dual bertanda ≥.
- Dual dari dual ialah 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
Sumber http://www.dounkey.com