Metode Dualitas

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 (X₁), dan yang kedua adalah sepatu dengan sol dari kulit (X₂). 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 X₁ mula-mula dikerjakan di mesin 1 selama 2 jam dan selanjutnya menuju mesin 3 selama 6 jam. Sedangkan X₂ dikerjakan oleh mesin 2 selama 3 jam dan langsung ke mesin 3 selama 5 jam.

Ø  Sumbangan terhadap laba untuk setiap sepatu X₁ = Rp. 30.000 sedangkan sepatu X₂ = Rp. 50.000.

Ø  Untuk mendapatkan hasil yang optimal, berapakah sepatu X₁ dan X₂ 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 = 3X₁ + 5X₂                           Minimumkan : Y₀ = 8Y₁ + 15Y₂ + 30Y₃

Batasan-Batasan :                                        Batasan-Batasan :

2X₁  ≤ 8                                                       2Y₁ + 6Y₃  ≥ 3
3X₂  ≤ 15                                                     3Y₂ + 6\5Y₃  ≥ 5
6X₁ + 5X₂  ≤ 30                                           Y₁ , Y₂ , Y₃  ≥ 0

X₁ , X₂  ≥ 0

  

§  Selanjutnya kita buat perumusan fungsi kendala dari fungsi maksimum :

2X₁  ≤  8                   à      2X₁ + X₃ = 8
3X₂  ≤ 15                 à      3X₂ + X₄ = 15
6X₁ + 5X₂  ≤ 30       à      6X₁ + 5X₂ + X₅ = 30

§  Kemudian kita rubah fungsi Z menjadi fungsi tujuan maks, lihat perumusan dibawah ini :

Fungsi  Z = 3X₁ + 5X₂

Fungsi tujuan maks : Z – 3X₁ – 5X₂

§  Kemudian kita merubah nilai baris kunci(pivot) à S₂

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 (S₁) :

            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 (S₃) :

            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) à S₃

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 (S₁) :

            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 (X₂) :

            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 X₁ dan X₂ sudah bernilai positif (+). Oleh karena itu kita bisa lanjutkan ke proses dualitas dengan cara dibawah ini :

§  Pertama kita masukkan nilai solusi optimal simpleksnya :

Ø  X₁ = 5/6
Ø  X₂ = 5

Ø  Laba = 27 1/2

§  Kemudian dengan cara yang sama, masukkan solusi optimal masalah dualnya :

Ø  Y₁ = 0

Ø  Y₂ = 5/6

Ø  Y₃ = 1/2

§  Terakhir kita masukkan perumusan Fungsi Tujuan Dual :

Minimalkan Y = 8Y₁ + 15Y₂ + 30Y₃

                              = 8(0) + 15(5/6) + 30(1/2)

                              = 27 1/2 → “nilai ini sama dengan yang dihasilkan dari fungsi tujuan primal / simpleks sebelumnya”.

Sumber : http://defri-z.blogspot.com