Teori dualitas merupakan konsep penting dalam matematika dan optimasi, khususnya dalam program linear. Meski terlihat rumit, dualitas sebenarnya dapat dipahami dengan mudah jika dipelajari secara bertahap dan disertai contoh soal yang jelas. Dalam artikel ini, kamu akan mendapatkan pemahaman lengkap mengenai teori dualitas, cara menyusun dual dari primal, serta contoh soal beserta pembahasan yang mudah dipahami. Artikel ini juga cocok untuk kamu yang sedang belajar matematika, ekonomi, manajemen, atau teknik industri.
Baca juga:Contoh Soal Perhitungan Pondasi Menerus dan Cara Penyelesaiannya Step by
Teori dualitas pada dasarnya menyatakan bahwa setiap masalah optimasi memiliki pasangan masalah lain yang disebut dual. Masalah awal disebut primal. Hubungan antara primal dan dual sangat kuat, terutama pada program linear. Jika kamu dapat menyelesaikan salah satu masalah, maka kamu juga dapat mengetahui informasi penting dari masalah pasangannya. Misalnya, nilai optimum pada primal sama dengan nilai optimum pada dual. Hal ini dikenal sebagai prinsip dualitas kuat. Selain itu, solusi optimal dari primal dan dual saling memengaruhi melalui konsep slack dan shadow price.
Secara umum, bentuk primal dan dual pada program linear dapat ditulis sebagai berikut. Jika primal berupa masalah maksimalisasi dengan kendala berbentuk “≤”, maka dualnya berupa masalah minimisasi dengan kendala berbentuk “≥”. Sebaliknya, jika primal minimisasi dengan kendala “≥”, maka dualnya adalah maksimalisasi dengan kendala “≤”. Perubahan ini bukan hanya pada tujuan, tetapi juga pada posisi koefisien dan variabel. Secara ringkas, aturan dasar dualitas dapat dituliskan sebagai berikut. Pertama, koefisien pada fungsi tujuan primal menjadi konstanta pada fungsi tujuan dual. Kedua, koefisien pada sisi kanan kendala primal menjadi koefisien pada fungsi tujuan dual. Ketiga, koefisien pada matriks kendala primal ditransposisikan pada dual. Keempat, tanda kendala dan sifat variabel mengikuti aturan tertentu berdasarkan bentuk kendala pada primal.
Sebelum masuk ke contoh soal, penting untuk memahami istilah yang sering muncul dalam dualitas. Pertama, variabel dual biasanya dilambangkan dengan y. Variabel ini memiliki arti ekonomi, misalnya harga bayangan atau shadow price. Shadow price menunjukkan berapa nilai tambahan yang diperoleh jika sumber daya tertentu ditambah satu unit. Kedua, slack variable adalah variabel yang menunjukkan selisih antara sisi kiri dan sisi kanan kendala pada primal. Ketiga, complementary slackness adalah kondisi yang menghubungkan primal dan dual. Kondisi ini menyatakan bahwa pada solusi optimal, untuk setiap kendala primal yang tidak aktif, variabel dual terkait harus nol, dan sebaliknya. Pemahaman konsep ini akan membantu kamu menguji kebenaran solusi optimal pada primal maupun dual.
Sekarang kita masuk ke contoh soal. Contoh soal pertama akan membahas bagaimana menyusun dual dari primal yang berbentuk maksimalisasi dengan kendala “≤”. Soal ini sering muncul dalam ujian atau tugas karena termasuk bentuk paling dasar dan mudah dipahami. Contoh soal kedua akan menunjukkan kasus minimisasi dengan kendala “≥”. Contoh soal ketiga akan menggabungkan kedua bentuk kendala, sehingga kamu bisa melihat bagaimana variabel dual memiliki tanda berbeda. Contoh soal keempat akan membahas penyelesaian primal dan dual secara lengkap hingga mencapai solusi optimal, sehingga kamu dapat melihat hubungan nilai optimum antara kedua masalah.
Contoh Soal 1: Tentukan Bentuk Dual dari Primal Maksimalisasi
Tentukan bentuk dual dari masalah primal berikut. Maksimalkan Z = 4×1 + 3×2 dengan kendala 2×1 + x2 ≤ 8 dan x1 + 2×2 ≤ 10 serta x1, x2 ≥ 0. Untuk menyusun dual, kita ikuti aturan dasar dualitas. Karena primal berupa maksimalisasi dan semua kendala bertanda “≤”, maka dual akan berupa minimisasi dengan variabel dual y1 dan y2 yang bernilai tidak negatif. Koefisien pada sisi kanan kendala primal yaitu 8 dan 10 akan menjadi koefisien fungsi tujuan dual. Matriks koefisien pada kendala primal ditransposisikan sehingga pada dual, koefisien pada kendala pertama adalah 2y1 + y2 dan pada kendala kedua adalah y1 + 2y2. Karena tujuan dual minimisasi, maka kendala dual berbentuk “≥”. Sehingga bentuk dualnya adalah minimalkan W = 8y1 + 10y2 dengan kendala 2y1 + y2 ≥ 4 dan y1 + 2y2 ≥ 3 serta y1, y2 ≥ 0. Dengan contoh ini, kamu dapat melihat transformasi langsung dari primal ke dual secara sistematis.
Contoh Soal 2: Dual dari Primal Minimasi dengan Kendala ≥
Tentukan dual dari masalah primal minimisasi. Misalkan minimalkan Z = 5×1 + 2×2 dengan kendala x1 + x2 ≥ 6 dan 2×1 + x2 ≥ 8 serta x1, x2 ≥ 0. Pada soal ini, primal adalah minimisasi dan semua kendala berbentuk “≥”. Berdasarkan aturan dualitas, dual akan berupa maksimalisasi dengan variabel dual yang tidak positif atau lebih tepatnya y1, y2 ≤ 0. Koefisien sisi kanan kendala primal yaitu 6 dan 8 menjadi koefisien fungsi tujuan dual. Koefisien matriks kendala ditransposisikan sehingga kendala dual menjadi y1 + 2y2 ≤ 5 dan y1 + y2 ≤ 2. Karena tujuan dual maksimalisasi, tanda kendala pada dual menjadi “≤”. Maka dualnya adalah maksimalkan W = 6y1 + 8y2 dengan kendala y1 + 2y2 ≤ 5, y1 + y2 ≤ 2, dan y1, y2 ≤ 0. Contoh ini penting untuk memahami bahwa tanda kendala dan sifat variabel dual berubah ketika primal berbentuk minimisasi dengan kendala “≥”.
Contoh Soal 3: Dual dari Primal Campuran (≥ dan ≤)
Bentuk dual dari primal campuran. Misalnya maksimasikan Z = 3×1 + 2×2 dengan kendala x1 + 3×2 ≥ 9 dan 2×1 + x2 ≤ 8 serta x1, x2 ≥ 0. Pada soal ini, primal adalah maksimalisasi, namun kendala pertama berbentuk “≥” dan kendala kedua berbentuk “≤”. Maka dualnya akan berupa minimisasi dengan variabel dual yang sifatnya campuran. Untuk kendala pertama yang “≥”, variabel dual terkait akan ≤ 0. Untuk kendala kedua yang “≤”, variabel dual terkait akan ≥ 0. Koefisien sisi kanan 9 dan 8 menjadi koefisien fungsi tujuan dual. Setelah mentransposisikan matriks koefisien kendala, diperoleh kendala dual yaitu y1 + 2y2 ≥ 3 dan 3y1 + y2 ≥ 2. Dengan aturan tanda variabel dual, maka dualnya adalah minimalkan W = 9y1 + 8y2 dengan kendala y1 + 2y2 ≥ 3, 3y1 + y2 ≥ 2, y1 ≤ 0, dan y2 ≥ 0. Contoh ini membantu kamu memahami bahwa dual dapat memiliki variabel dengan tanda berbeda sesuai bentuk kendala pada primal.
Contoh Soal 4: Penyelesaian Primal dan Dual Lengkap
Penyelesaian lengkap primal dan dual. Misalkan primal berupa maksimasikan Z = 2×1 + 3×2 dengan kendala x1 + x2 ≤ 4 dan 2×1 + x2 ≤ 5 serta x1, x2 ≥ 0. Langkah pertama adalah menyusun dual. Karena primal maksimalisasi dan kendala “≤”, maka dualnya minimisasi dengan y1, y2 ≥ 0. Fungsi tujuan dual menjadi minimalkan W = 4y1 + 5y2. Kendala dual diperoleh dari transpos matriks koefisien yaitu y1 + 2y2 ≥ 2 dan y1 + y2 ≥ 3. Langkah kedua adalah menyelesaikan primal dengan metode grafik. Pada grafik, garis x1 + x2 = 4 dan 2×1 + x2 = 5 menjadi batas wilayah feasible. Titik potong kedua garis diperoleh dengan substitusi sehingga didapat x1 = 1 dan x2 = 3. Titik ekstrem lainnya adalah (0,0), (0,4), dan (4,0). Evaluasi fungsi tujuan Z pada titik ekstrem menghasilkan nilai Z terbesar pada titik (0,4) yaitu Z = 12. Jadi solusi optimal primal adalah x1 = 0, x2 = 4, Z = 12. Langkah ketiga adalah menyelesaikan dual. Karena nilai optimum primal adalah 12, maka nilai optimum dual juga 12 berdasarkan prinsip dualitas kuat. Dengan menyelesaikan kendala dual, diperoleh bahwa solusi optimal dual adalah y1 = 3, y2 = 0 sehingga W = 12. Hubungan ini membuktikan bahwa dualitas memberikan informasi yang saling menguatkan antara primal dan dual.
Untuk memperdalam pemahaman, kamu bisa menggunakan konsep complementary slackness. Pada contoh soal 4, kendala pertama pada primal x1 + x2 ≤ 4 menjadi aktif pada solusi optimal karena x1 + x2 = 4. Artinya slack pada kendala pertama adalah nol. Sedangkan kendala kedua 2×1 + x2 ≤ 5 tidak aktif karena 2(0) + 4 = 4 yang kurang dari 5. Dari prinsip complementary slackness, variabel dual terkait kendala yang tidak aktif harus nol. Oleh karena itu y2 = 0. Sedangkan y1 tidak nol karena kendala pertama aktif. Kondisi ini membantu memastikan bahwa solusi dual yang diperoleh sudah benar. Dengan memahami konsep ini, kamu akan lebih mudah mengecek kebenaran solusi tanpa harus melakukan perhitungan panjang.
Teori dualitas juga memiliki aplikasi nyata dalam dunia ekonomi dan manajemen. Misalnya dalam perencanaan produksi, kendala sumber daya seperti bahan baku, tenaga kerja, dan waktu dapat dimodelkan sebagai kendala pada program linear. Variabel dual kemudian menunjukkan nilai tambahan yang diperoleh jika sumber daya ditambah satu unit. Dengan kata lain, dual membantu manajer menentukan prioritas alokasi sumber daya. Selain itu, dualitas juga digunakan dalam analisis biaya, penjadwalan, dan optimasi jaringan. Dengan memahami dualitas, kamu tidak hanya menguasai teori matematika, tetapi juga mendapatkan alat praktis untuk pengambilan keputusan.
Agar lebih mahir, kamu bisa mencoba latihan soal tambahan dengan variasi bentuk kendala dan tujuan. Latihan ini penting karena aturan dualitas sering membingungkan pada kasus campuran atau ketika ada variabel bebas (tanpa batasan tanda). Pada variabel bebas, dualnya memiliki kendala yang bentuknya sama, tetapi variabel dual tidak memiliki batasan tanda. Semakin sering kamu berlatih, semakin cepat kamu bisa menyusun dual secara otomatis tanpa harus berpikir panjang.
Kesimpulannya, teori dualitas adalah konsep yang sangat berguna dalam program linear. Dengan memahami aturan dasar dualitas dan sering berlatih contoh soal, kamu bisa menyusun dual dengan mudah dan mengecek solusi optimal dengan lebih cepat. Contoh soal yang sudah dibahas menunjukkan cara menyusun dual dari primal, serta hubungan nilai optimum antara primal dan dual. Semoga artikel ini membantu kamu memahami teori dualitas secara lengkap dan mudah dipahami.
Penulis:Loveytha
Post Comment