Linear Programming
Optimasi dengan sumber daya terbatas: formulasi, feasible region, metode grafis, simplex, sensitivitas, dualitas, transportation dan diet problem, integer programming.
Isi materi
- Apa itu Linear Programming
- Dari Cerita ke Model
- Feasible Region
- Garis Iso-Profit & Titik Optimal
- Metode Grafis Interaktif
- Kasus Khusus
- Metode Simplex
- Analisis Sensitivitas
- Dualitas
- Transportation Problem
- Diet/Blending Problem
- Integer Programming
- Decision Guide
- Pitfalls
Istilah penting
- Linear Programming (LP)
- Teknik optimasi untuk memaksimumkan/meminimumkan fungsi linear, dengan kendala-kendala yang juga linear.
- Variabel Keputusan
- Kuantitas yang bisa diatur/diputuskan, mis. berapa unit meja & kursi diproduksi.
- Fungsi Objektif
- Fungsi linear yang ingin dimaksimumkan (mis. profit) atau diminimumkan (mis. biaya).
- Kendala (Constraint)
- Batasan sumber daya atau syarat yang harus dipenuhi, ditulis sebagai pertidaksamaan linear.
- Feasible Region
- Himpunan semua kombinasi variabel keputusan yang memenuhi seluruh kendala sekaligus.
- Titik Sudut (Vertex/Corner Point)
- Titik pojok dari feasible region, tempat dua atau lebih garis kendala berpotongan.
- Garis Iso-Profit/Iso-Cost
- Garis yang menghubungkan semua kombinasi variabel dengan nilai fungsi objektif yang sama.
- Teorema Fundamental LP
- Solusi optimal dari masalah LP (jika ada) selalu bisa ditemukan di salah satu titik sudut feasible region.
- Metode Simplex
- Algoritma aljabar yang bergerak dari satu titik sudut ke titik sudut tetangga yang lebih baik, sampai optimal.
- Variabel Slack
- Variabel tambahan yang mengubah kendala pertidaksamaan (≤) menjadi persamaan, dipakai di metode simplex.
- Tabel Simplex
- Representasi tabular dari sistem persamaan LP yang di-update tiap iterasi simplex.
- Solusi Unbounded
- Kondisi di mana fungsi objektif bisa terus membesar (untuk maksimasi) tanpa batas, tidak ada solusi optimal.
- Solusi Infeasible
- Kondisi di mana tidak ada kombinasi variabel yang memenuhi seluruh kendala sekaligus.
- Solusi Optimal Ganda
- Kondisi di mana lebih dari satu titik (bahkan satu sisi penuh) menghasilkan nilai objektif optimal yang sama.
- Analisis Sensitivitas
- Studi tentang seberapa besar solusi optimal berubah kalau parameter (kendala/koefisien objektif) berubah sedikit.
- Shadow Price
- Seberapa besar nilai objektif optimal berubah kalau batas satu kendala (RHS) ditambah 1 unit.
- Dualitas
- Setiap masalah LP (primal) punya masalah "bayangan" (dual) yang terkait erat, nilai optimalnya selalu sama (strong duality).
- Transportation Problem
- Masalah LP khusus: mengalokasikan barang dari beberapa sumber ke beberapa tujuan dengan biaya minimum.
- Diet/Blending Problem
- Masalah LP khusus: mencampur beberapa bahan dengan biaya minimum, memenuhi syarat kandungan (mis. gizi) minimum.
- Integer Programming
- LP dengan syarat tambahan: sebagian/semua variabel keputusan harus bilangan bulat.
- LP Relaxation
- Versi integer programming yang syarat bilangan bulatnya "dilonggarkan" dulu, diselesaikan sebagai LP biasa.