INTERPRETASI EKONOMI MASALAH PRIMAL-DUAL

CONTOH

Sebuah perusahaan pengolahan kayu menerima pesanan kayu tingkat konstruksi dan tingkat akhir. Kayu dioleh dalam dua tahap, yaitu penggergajian dan penghalusan. Dibutuhkan waktu 2  jam untuk penggergajian  kayu tingkat akhir  dan 5 jam penghalusan kayu  tingkat akhir  untuk setiap 1000 papan. Untuk kayu tingkat konstruksi, dibutuhkan 2 jam proses penggergajian untuk setiap 1000 papan dan 3 jam untuk penghalusan. Mesin penggergajian dapat beroperasi selama 8 jam sehari dan mesin penghalus dapat beroperasi selama 15 jam perhari. Jika keuntungan setiap 1000 papan kayu tingkat akhir $120 dan $100 untuk tingkat konstruksi, berapa banyaknya setiap jenis kayu yang harus dikerjakan untuk menghasilkan keuntungan maksimum ?

Misalkan x=banyaknya kayu tingkat akhir dan y=banyaknya kayu tingkat konstruksi, maka model matematika masalah ini adalah

Memaksimumkan f = 120x + 100y

Dengan kendala 2x + 2y £ 8

                     5x + 3y £ 15

                     x, y ³ 0

Kendala pertama masalah perusahaan pengolahan kayu ini berkaitan dengan banyaknya waktu mesin penggergajian  beroperasi. Kendala kedua berkaitan dengan banyaknya waktu mesin penghalus beroperasi. Secara umum, kendala ke-i berbentuk

 

Kita dapat memandang b_i sebagai total persediaan sumber ke-i, atau bahan baku, atau input. Untuk kendala pertama adalah waktu beroperasi mesin penggergajian.

Secara umum, koefisien a_ij menyatakan banyaknya input per unit yang dibutuhkan oleh produk ke-j, atau output. Sebagai contoh, a₁₂=5 menyatakan 5 jam penghalusan untuk setiap 1000 papan kayu tingkat akhir.

Variabel x_j adalah banyaknya output ke-j yang akan diproduksi (belum diketahui).

Koefisien c_j dalam fungsi tujuan menyatakan keuntungan, atau nilai yang diperoleh dari satu unit output ke-j.

Penyelesaian optimal x=3/2 dan y=5/2  memaksimumkan total nilai semua output f= c₁x + c₂y.

Dual dari masalah ini adalah

Meminimumkan z = 8u + 15v

Dengan kendala 2u + 5v ³ 120

                             2u + 3v ³ 100

                             u, v ³ 0

Koeffisien dari kendala pertama adalah banyaknya input yang dibutuhkan untuk membuat satu unit (1000 papan) dari output pertama. Yaitu, untuk membuat 1000 papan kayu tingkat akhir dibutuhkan 2 jam penggergajian dan 5 jam penghalusan. Suku tetap ruas kanan kendala pertama adalah keuntungan, atau nilai dari satu unit output pertama.

Kendala kedua dari masalah dual menyatakan bahwa untuk membuat 1000 papan kayu tingkat konstruksi dibutuhkan 2 jam proses penggergajian dan 3 jam penghalusan, dan nilai dari produk ini adalah $100.

Penyelesaian optimal dualnya adalah u = 35 dan v = 10.