Metode dualitas merupakan alat bantu masalah linear programming
yang secara langsung di definisikan dari persoalan aslinya, dualitas sangat
bergantung pada primal dalam hal tipe kendala, variabel keputusan dan kondisi
optimum.
Contoh Metode Dualitas :
Perusahaan sepatu “IDEAL” membuat 2 macam sepatu. Yang pertama
adalah sepatu dengan sol karet (X1), dan yang kedua adalah sepatu
dengan sol dari kulit (X2). Untuk memproduksi kedua macam sepatu
tersebut perusahaan menggunakan 3 jenis mesin. Mesin 1 = khusus untuk membuat
sepatu karet, dengan kapasitas max = 8 jam. Mesin 2 = khusus untuk membuat
sepatu dari kulit, dengan kapasitas max = 15 jam. Mesin 3 = khusus untuk
assemblim kedua macam sepatu tersebut, dengan kapasitas max = 30 jam.
Ø Setiap lusin X1 mula-mula dikerjakan di
mesin 1 selama 2 jam dan selanjutnya menuju mesin 3 selama 6 jam. Sedangkan X2 dikerjakan oleh mesin 2
selama 3 jam dan langsung ke mesin 3 selama 5 jam.
Ø Sumbangan terhadap laba
untuk setiap sepatu X1 = Rp. 30.000 sedangkan
sepatu X2 = Rp. 50.000.
Ø Untuk mendapatkan hasil
yang optimal, berapakah sepatu X1 dan X2 yang harus diproduksi?
Jawab :
§ Langkah pertama kita
buat tabel dari soal diatas agar lebih mudah penyelesaiannya, lihat tabel
dibawah ini :
|
Variabel
|
X1
|
X2
|
Kapasitas
Maksimum Mesin
|
|
Y1
|
2
|
0
|
≤
8
|
|
Y2
|
0
|
3
|
≤
15
|
|
Y3
|
6
|
5
|
≤
30
|
|
Laba
dalam Rp. 10.000
|
≥
3
|
≥
5
|
|
§ Kemudian kita buat
perumusan fungsi maksimum dan minimum beserta batasan-batasannya, perhatikan
perumusan dibawah ini :
Maksimumkan : Z = 3X1 +
5X2
Minimumkan : Y0 = 8Y1 + 15Y2 + 30Y3
Batasan-Batasan :
Batasan-Batasan :
2X1 ≤ 8
2Y1 + 6Y3 ≥ 3
3X2 ≤ 15
3Y2 + 6\5Y3 ≥ 5
6X1 + 5X2 ≤ 30
Y1 , Y2 , Y3 ≥ 0
X1 , X2 ≥
0
§ Selanjutnya kita buat
perumusan fungsi kendala dari fungsi maksimum :
2X1 ≤
8
à
2X1 + X3 = 8
3X2 ≤
15
à
3X2 + X4 = 15
6X1 + 5X2 ≤ 30 à
6X1 + 5X2 + X5 = 30
§ Kemudian kita rubah
fungsi Z menjadi fungsi tujuan maks, lihat perumusan dibawah ini :
Fungsi Z = 3X1 +
5X2
Fungsi tujuan maks : Z –
3X1 – 5X2
§ Kemudian kita merubah
nilai baris kunci(pivot) à S2
0/3 = 0 , 3/3 = 1 , 0/3 = 0 , 1/3 , 0/3 = 0 , 15/3 = 5
§ Lalu kita hitung baris
ke 1 (Z) :
–3
–5
0
0 0
0
0
1 0
1/3
0
5
(–5) ------------------------------------------------------
–
–3
0 0
5/3
0 25
§ Selanjutnya kita hitung
baris ke 2 (S1) :
2
0
1
0
0 8
0
1
0 1/3
0
5
(0)
------------------------------------------------------ –
2
0
1 0
0 8
§ Kemudian kita hitung
baris ke 4 (S3) :
6 5
0
0
1 30
0
1
0 1/3
0
5
(5)
------------------------------------------------------- –
6
0 0 –5/3 1
5
§ Kemudian kita merubah
nilai baris kunci(pivot) à S3
6/6 = 1 , 0/6 = 0 , 0/6 = 0 , –5/3 / 6 = –5/18 , 1/6 , 5/6
§ Lalu kita hitung baris
ke 1 (Z) :
–3
0 0
5/3 0
25
1
0
0 –5/18 1/6
5/6
(–3)
--------------------------------------------------------- –
0
0 0
5/6
1/2 27 1/2
§ Selanjutnya kita hitung
baris ke 2 (S1) :
2
0 1
0
0 8
1
0 0 –5/18
1/6
5/6
(2)
--------------------------------------------------------- –
0
0 1 5/9 –1/3
6 1/3
§ Kemudian kita hitung
baris ke 3 (X2) :
0
1 0 1/3
0 5
1
0 0
–5/18 1/6 5/6
(0)
--------------------------------------------------------- –
0
1 0 1/3
0 5
§ Setelah itu kita
masukkan hasil perhitungan diatas kedalam tabel simpleks, lihat tabel dibawah
ini :
|
Variabel
Dasar
|
Z
|
X1
|
X2
|
S1
|
S2
|
S3
|
NK
|
|
Z
|
1
|
0
|
0
|
0
|
5/6
|
1/2
|
27 1/2
|
|
S1
|
0
|
0
|
0
|
1
|
5/9
|
–1/3
|
6 1/3
|
|
X2
|
0
|
0
|
1
|
0
|
1/3
|
0
|
5
|
|
X1
|
0
|
1
|
0
|
0
|
–5/18
|
1/6
|
5/6
|
Kesimpulan :
Dari hasil tabel diatas sudah dinyatakan optimal karena nilai pada
kolom X1 dan X2 sudah bernilai positif (+).
Oleh karena itu kita bisa lanjutkan ke proses dualitas dengan cara dibawah ini
:
§ Pertama kita masukkan
nilai solusi optimal simpleksnya :
Ø X1 = 5/6
Ø X2 = 5
Ø Laba = 27 1/2
§ Kemudian dengan cara
yang sama, masukkan solusi optimal masalah dualnya :
Ø Y1 = 0
Ø Y2 = 5/6
Ø Y3 = 1/2
§ Terakhir kita masukkan
perumusan Fungsi Tujuan Dual :
Minimalkan Y = 8Y1 +
15Y2 + 30Y3
= 8(0) + 15(5/6) + 30(1/2)
= 27 1/2 → “nilai ini sama dengan yang dihasilkan dari fungsi tujuan primal
/ simpleks sebelumnya”.
