Hubungan Antar Variabel Dalam Solusi Optimal Dan Dual Program Linier

𝕸𝖆𝖘 𝕬𝖓𝖉𝖞 𝕯𝖎𝖌𝖎𝖙𝖆𝖑 𝕸𝖊𝖉𝖎𝖆

3 min read

·

Apr 17, 2025

68

Share

Hubungan Antar Variabel Dalam Solusi Optimal Dan Dual Program Linier

Program linier (PL) adalah teknik optimasi matematis yang digunakan untuk menemukan solusi terbaik (optimal) untuk masalah yang dapat dimodelkan sebagai fungsi linier dengan kendala linier. Salah satu konsep kunci dalam PL adalah dualitas, di mana setiap masalah PL primal memiliki masalah PL dual yang terkait. Memahami hubungan antara variabel primal dan dual dalam solusi optimal sangat penting untuk interpretasi hasil dan pemahaman yang lebih dalam tentang masalah optimasi.

Memahami Program Linier Primal dan Dual

Sebelum membahas hubungan antar variabel, mari kita tinjau singkat konsep program linier primal dan dual.

Program Linier Primal (Primal LP): Ini adalah formulasi standar masalah optimasi, biasanya berupa memaksimalkan atau meminimalkan fungsi objektif linier, tunduk pada sejumlah kendala linier. Bentuk umum masalah primal adalah:

• Maksimumkan: Z = c₁x₁ + c₂x₂ + ... + cₙxₙ
• Tunduk pada:
  • a₁₁x₁ + a₁₂x₂ + ... + a₁ₙxₙ ≤ b₁
  • a₂₁x₁ + a₂₂x₂ + ... + a₂ₙxₙ ≤ b₂
  • ...
  • aₘ₁x₁ + aₘ₂x₂ + ... + aₘₙxₙ ≤ bₘ
  • x₁, x₂, ..., xₙ ≥ 0

Program Linier Dual (Dual LP): Setiap masalah primal memiliki masalah dual yang terkait. Masalah dual diperoleh melalui transformasi matematis dari masalah primal. Jika masalah primal memaksimalkan, maka masalah dual meminimalkan, dan sebaliknya. Variabel dual mewakili shadow price atau nilai marginal dari setiap kendala dalam masalah primal.

Hubungan Antar Variabel dalam Solusi Optimal

Teorema Dualitas merupakan landasan pemahaman hubungan antara solusi optimal masalah primal dan dual. Teorema ini menyatakan bahwa:

• Jika masalah primal memiliki solusi optimal, maka masalah dual juga memiliki solusi optimal, dan nilai optimal dari fungsi objektif kedua masalah sama. Ini menunjukkan bahwa nilai optimal yang dicapai dalam masalah primal akan sama dengan nilai optimal yang dicapai dalam masalah dual.

• Keterhubungan Variabel: Hubungan kunci terletak pada variabel-variabelnya. Ada hubungan langsung antara variabel keputusan dalam masalah primal (xᵢ) dan variabel dual (yᵢ) pada solusi optimal. Hubungan ini didasarkan pada kondisi komplementaritas.

Kondisi Komplementaritas

Kondisi komplementaritas menyatakan bahwa untuk setiap kendala dalam masalah primal dan variabel dual yang terkait, hasil kali dari slack (kelebihan sumber daya) pada kendala primal dan variabel dual yang sesuai akan sama dengan nol. Secara matematis, untuk kendala ke-i dalam masalah primal:

(Slack pada kendala ke-i dalam masalah primal) * (Variabel dual ke-i) = 0

Artinya:

• Jika slack pada kendala ke-i > 0 (kendala tidak mengikat), maka variabel dual ke-i = 0. Ini mengindikasikan bahwa sumber daya pada kendala tersebut berlebih, sehingga tidak memiliki nilai marginal (shadow price).

• Jika slack pada kendala ke-i = 0 (kendala mengikat), maka variabel dual ke-i > 0. Ini menunjukkan bahwa kendala tersebut aktif membatasi solusi optimal, dan memiliki nilai marginal (shadow price) positif.

Interpretasi dan Aplikasi

Pemahaman hubungan antara variabel primal dan dual dalam solusi optimal memiliki implikasi praktis yang signifikan:

• Interpretasi Shadow Price: Variabel dual memberikan informasi tentang seberapa banyak nilai fungsi objektif akan berubah jika kendala diperbaiki sedikit. Ini sangat berguna dalam pengambilan keputusan, misalnya, menentukan apakah investasi tambahan pada sumber daya tertentu layak dilakukan.

• Sensitivitas Analisis: Kondisi komplementaritas memungkinkan untuk melakukan analisis sensitivitas, yaitu mengevaluasi bagaimana perubahan parameter dalam masalah primal akan memengaruhi solusi optimal.

Kesimpulan

Hubungan antara variabel dalam solusi optimal program linier primal dan dual, yang dijelaskan oleh teorema dualitas dan kondisi komplementaritas, menyediakan wawasan yang mendalam tentang masalah optimasi. Memahami hubungan ini memungkinkan untuk interpretasi hasil yang lebih komprehensif dan pengambilan keputusan yang lebih baik dalam berbagai aplikasi.