Prinsip Dualitas dalam Linear Programming

Dualitas dalam Linear Programming

1. Dualitas dalam linear programming adalah hubungan dua masalah program linear yang saling terkait.
2. Masalah program linear (masalah primal) memiliki pasangan yaitu masalah dual.
3. Konsep ini untuk menganalisis sensitivitas solusi, memberikan interpretasi ekonomis, dan mengembangkan algoritma penyelesaian yang lebih efisien.

Riset Operasional 4, STIE Indocakti

Contoh Sederhana

Misalnya ingin merencanakan pertemuan keluarga dengan acara meriah. Dan memiliki sedikit anggaran (kendala) namun ingin memaksimalkan kesenangan tamu (fungsi tujuan). Masalah primal yaitu bagaimana mengalokasikan anggaran membeli makanan, minuman, dan dekorasi.

Masalah dualnya mencari harga minimum barang agar pertemuan keluarga terlaksana. Masalah dual mencari harga terendah yang membuat semua kendala primal terpenuhi.

Tujuan Utama Dualitas

1. Interpretasi Ekonomis: memberikan informasi tentang nilai marginal dari setiap kendala. Misalnya, dalam contoh Pertemuan keluarga, variabel dual untuk anggaran makanan menunjukkan berapa tambahan kesenangan yang bisa diperoleh jika anggaran makanan ditambah.
2. Analisis Sensitivitas: bagaimana perubahan pada kendala mempengaruhi nilai optimal dari fungsi tujuan.

Penerapan Dualitas dalam Bisnis

1. Perencanaan Produksi: Menentukan jumlah produk yang optimal untuk diproduksi dengan melihat keterbatasan sumber daya.
2. Transportasi: Menentukan rute pengiriman yang paling efisien untuk meminimalkan biaya transportasi.
3. Portofolio Investasi: Memilih investasi yang memberikan return tertinggi dengan risiko terkendali.
4. Jadwal Produksi: Menentukan jadwal produksi yang optimal untuk memenuhi permintaan pelanggan.

Konsep Dualitas

Jika masalah Primal berbentuk minimisasi, maka masalah Dualnya berbentuk maksimisasi, dan sebaliknya.

Dualitas memiliki hubungan terstruktur:

1. Fungsi tujuan dari masalah primal menjadi kendala pada masalah dual.
2. Kendala primal menjadi variabel pada masalah dual.

Hubungan Dualitas:

1. Jika masalah primal adalah minimisasi, masalah dual akan menjadi maksimisasi, dan sebaliknya.
2. Batasan pada primal dengan tanda "<=" akan menjadi variabel dual dengan tanda ">=".
3. Fungsi tujuan pada primal akan menjadi kendala di dual.

Analisis Hubungan Primal dan Dual

1. Harga Bayangan: Jika Solusi dual memberikan interpretasi seperti nilai ekonomi dari sumber daya yang terbatas (kendala primal).
2. Kondisi Complementary Slackness: kendala pada masalah primal tidak ketat (slack), maka variabel dual yang terkait harus nol, dan sebaliknya.
3. Optimalitas Bersama: Jika solusi primal optimal, solusi dual yang terkait juga akan optimal. Ini berarti bahwa nilai optimal dari kedua masalah adalah sama.

Contoh: Restoran dan Penyedia Bahan Baku

Masalah Primal: Restoran Mengoptimalkan Pengeluaran

1. Restoran ingin meminimalkan biaya pembelian bahan baku (sayuran dan daging) untuk membuat menu harian.
2. Setiap menu membutuhkan sejumlah bahan baku tertentu, seperti tomat dan daging, dan restoran harus memastikan bahwa setiap bahan baku terpenuhi agar bisa menyajikan menu.

Restoran memiliki dua pilihan pemasok:

1. Pemasok A menjual sayuran dengan harga tertentu.
2. Pemasok B menjual daging dengan harga tertentu.

Tujuan restoran

Meminimalkan biaya total membeli bahan yang diperlukan dari dua pemasok, sambil memenuhi kebutuhan bahan baku untuk menyajikan menunya setiap hari.

Masalah Dual: Penyedia Bahan Baku Menilai Nilai Sumber Daya

1. Di sisi lain, penyedia bahan baku (pemasok sayuran dan daging) ingin memaksimalkan keuntungan. Pemasok tahu bahwa restoran sangat membutuhkan sayuran dan daging, sehingga pemasok bisa menaikkan harga untuk mendapatkan keuntungan lebih banyak.
2. Namun, pemasok juga tahu bahwa jika harga terlalu tinggi, restoran bisa mencari pemasok lain. Maka, pemasok ingin memaksimalkan keuntungan dengan menetapkan harga yang tepat untuk bahan baku yang disediakan, sambil memperhatikan batasan permintaan dari restoran.

Hubungan Primal dan Dual

1. Restoran (Primal) ingin mengurangi biaya, tetapi harus tetap memenuhi kebutuhan minimum bahan baku. Setiap unit bahan baku yang dibeli memiliki harga tertentu, dan tujuannya meminimalkan total pengeluaran.
2. Pemasok (Dual) ingin menaikkan harga bahan baku untuk mendapatkan keuntungan sebesar mungkin, tetapi dibatasi oleh berapa banyak restoran bersedia membayar. Pemasok tidak bisa menaikkan harga sembarangan karena restoran akan beralih ke pemasok lain.

Complementary Slackness (Kondisi Pelengkap)

Jika restoran tidak membutuhkan lebih banyak daging (kendala slack), pemasok daging tidak dapat menaikkan harga untuk bahan tersebut. Sebaliknya, jika restoran sangat membutuhkan daging, pemasok daging bisa menaikkan harga, tetapi akan mencapai batas maksimal di mana restoran tidak lagi bersedia membayar lebih.

Inti Restaurant dan Pemasok

1. Restoran (Primal) berusaha mendapatkan bahan baku dengan harga serendah mungkin sambil memenuhi kebutuhan menu.
2. Pemasok (Dual) berusaha memaksimalkan keuntungan dengan menentukan harga bahan baku yang tidak terlalu tinggi sehingga restoran masih mau membelinya.