Teori dualitas merupakan salah satu materi penting dalam mata kuliah Riset Operasi (Operations Research). Materi ini sering menjadi bagian dari ujian karena konsepnya yang fundamental dalam program linear dan optimasi. Bagi mahasiswa, memahami teori dualitas tidak hanya membantu menjawab soal ujian, tetapi juga memberikan wawasan tentang hubungan antara masalah optimasi dan sumber daya. Dalam artikel ini, kamu akan menemukan latihan dan contoh soal teori dualitas yang sering muncul dalam ujian riset operasi, lengkap dengan pembahasan yang mudah dipahami.
Teori dualitas pada dasarnya menjelaskan bahwa setiap masalah optimasi memiliki pasangan masalah lain yang disebut dual. Masalah awal disebut primal. Dalam program linear, hubungan antara primal dan dual sangat erat. Nilai optimum primal sama dengan nilai optimum dual jika solusi optimal ada dan masalah memenuhi syarat tertentu. Prinsip ini dikenal sebagai dualitas kuat. Selain itu, dualitas juga memberikan informasi tentang harga bayangan (shadow price), yaitu nilai tambahan yang diperoleh jika sumber daya ditambah satu unit. Konsep ini sangat berguna dalam pengambilan keputusan manajemen dan ekonomi.
Sebelum masuk ke latihan soal, penting untuk memahami aturan dasar dalam menyusun dual dari primal. Pertama, jika primal merupakan masalah maksimalisasi dengan kendala “≤”, maka dual adalah minimisasi dengan kendala “≥”. Kedua, jika primal minimisasi dengan kendala “≥”, maka dual adalah maksimalisasi dengan kendala “≤”. Ketiga, jika kendala pada primal berupa “=”, maka variabel dual bebas (tidak terikat tanda). Keempat, koefisien sisi kanan kendala primal menjadi koefisien fungsi tujuan dual. Kelima, koefisien pada fungsi tujuan primal menjadi sisi kanan kendala dual setelah transpos matriks koefisien. Aturan ini akan membantu kamu menyusun dual dengan cepat dan tepat.
Latihan 1: Menentukan Dual dari Primal Maksimalisasi
Latihan pertama ini cocok untuk pemula. Diberikan primal:
Max Z = 3×1 + 5×2
s.t.
x1 + 2×2 ≤ 6
2×1 + x2 ≤ 8
x1, x2 ≥ 0
Tentukan dualnya. Karena primal maksimalisasi dan kendala “≤”, dualnya minimisasi dengan variabel dual y1 dan y2 ≥ 0. Koefisien sisi kanan 6 dan 8 menjadi koefisien fungsi tujuan dual. Setelah transpos, dual menjadi:
Min W = 6y1 + 8y2
s.t.
y1 + 2y2 ≥ 3
2y1 + y2 ≥ 5
y1, y2 ≥ 0
Pembahasan: Dual dapat disusun secara cepat dengan aturan dasar. Latihan ini membantu mahasiswa memahami transformasi primal ke dual.
Latihan 2: Dual dari Primal Minimasi dengan Kendala ≥
Latihan kedua:
Min Z = 4×1 + 2×2
s.t.
x1 + x2 ≥ 7
2×1 + 3×2 ≥ 10
x1, x2 ≥ 0
Dualnya akan menjadi maksimalisasi karena primal minimisasi dan kendala “≥”. Variabel dual y1, y2 ≤ 0. Fungsi tujuan dual:
Max W = 7y1 + 10y2
s.t.
y1 + 2y2 ≤ 4
y1 + 3y2 ≤ 2
y1, y2 ≤ 0
Pembahasan: Latihan ini membantu mahasiswa memahami dual pada kasus minimisasi.
Latihan 3: Dual dengan Kendala Campuran
Latihan ketiga:
Max Z = 2×1 + 4×2
s.t.
x1 + x2 ≥ 5
2×1 + x2 ≤ 6
x1, x2 ≥ 0
Pada soal ini, kendala pertama “≥” menghasilkan variabel dual y1 ≤ 0, sedangkan kendala kedua “≤” menghasilkan y2 ≥ 0. Dualnya:
Min W = 5y1 + 6y2
s.t.
y1 + 2y2 ≥ 2
y1 + y2 ≥ 4
y1 ≤ 0, y2 ≥ 0
Pembahasan: Soal campuran ini sering muncul pada ujian karena menguji ketelitian mahasiswa.
Latihan 4: Penyelesaian Primal dan Dual (Soal Ujian)
Latihan ini dirancang mirip soal ujian. Diberikan primal:
Max Z = 5×1 + 3×2
s.t.
x1 + 2×2 ≤ 6
2×1 + x2 ≤ 8
x1, x2 ≥ 0
Langkah pertama adalah menyusun dual:
Min W = 6y1 + 8y2
s.t.
y1 + 2y2 ≥ 5
2y1 + y2 ≥ 3
y1, y2 ≥ 0
Langkah kedua, selesaikan primal dengan metode grafik. Titik ekstrem feasible adalah (0,0), (0,3), (6,0), dan titik potong kedua kendala. Titik potong didapat dari sistem:
x1 + 2×2 = 6
2×1 + x2 = 8
Menyelesaikan, diperoleh x1 = 2, x2 = 2. Evaluasi fungsi tujuan Z:
(0,3) → Z = 9
(6,0) → Z = 30
(2,2) → Z = 16
Jadi solusi optimal primal adalah x1 = 6, x2 = 0, Z = 30.
Langkah ketiga, nilai optimal dual juga 30. Dengan menyelesaikan kendala dual, diperoleh y1 = 5, y2 = 0. Sehingga W = 30. Hubungan ini menunjukkan dualitas kuat.
Latihan 5: Soal dengan Variabel Bebas
Soal ini lebih sulit karena ada variabel bebas. Contoh:
Max Z = x1 + 3×2
s.t.
x1 + x2 ≤ 4
x1 – x2 = 1
x1 bebas, x2 ≥ 0
Pada kasus variabel bebas, dual harus dibuat dengan memperhatikan bahwa variabel bebas tidak memiliki batasan tanda. Ini akan memengaruhi bentuk kendala dual. Soal seperti ini sering muncul pada ujian riset operasi untuk menguji pemahaman lebih dalam.
Latihan 6: Dual dengan Banyak Variabel dan Kendala
Untuk latihan lanjutan, kamu bisa mencoba soal berikut:
Max Z = 3×1 + 2×2 + 4×3
s.t.
x1 + 2×2 + x3 ≤ 10
2×1 + x2 + 3×3 ≤ 15
x1, x2, x3 ≥ 0
Dualnya adalah minimisasi dengan dua variabel dual y1 dan y2. Fungsi tujuan dual:
Min W = 10y1 + 15y2
s.t.
y1 + 2y2 ≥ 3
2y1 + y2 ≥ 2
y1 + 3y2 ≥ 4
y1, y2 ≥ 0
Soal ini membantu mahasiswa memahami dualitas pada program linear dengan banyak variabel.
Tips Menghadapi Soal Ujian Teori Dualitas
Untuk menghadapi ujian riset operasi, kamu perlu strategi belajar yang tepat. Pertama, hafalkan aturan dasar dualitas, karena soal ujian biasanya menilai ketepatan penyusunan dual. Kedua, latihan soal dengan berbagai bentuk kendala, termasuk kendala campuran dan variabel bebas. Ketiga, pahami konsep complementary slackness agar bisa mengecek solusi optimal. Keempat, pahami interpretasi ekonomi dari variabel dual sebagai shadow price. Kelima, jangan lupa latihan menyelesaikan primal dan dual sekaligus untuk memahami hubungan nilai optimum.
Kesimpulan
Latihan dan contoh soal teori dualitas untuk ujian riset operasi ini dirancang untuk membantu mahasiswa memahami konsep dualitas secara praktis. Dengan berlatih soal yang beragam, kamu akan lebih siap menghadapi ujian dan memahami hubungan antara primal dan dual. Dualitas tidak hanya soal matematika, tetapi juga alat penting dalam pengambilan keputusan dan optimasi sumber daya.
Penulis:Loveytha
Post Comment