Program Linear : Metode Grafik
Halo, Sixtyfourians! Kali ini kita akan membahas salah satu topik penting dalam Program Linier, yaitu cara menentukan solusi optimal menggunakan Metode Grafik. Metode ini sangat cocok untuk permasalahan yang hanya melibatkan dua variabel. Mari kita bedah langkah demi langkahnya!
1. Formulasi Masalah dan Penentuan Daerah Solusi
Fondasi utamanya Sixtyfourians harus mengubah masalah cerita (verbal) ke dalam bahasa matematika.
A. Tentukan Fungsi Tujuan: Apa yang ingin dimaksimalkan (misalnya, keuntungan) atau minimalkan (misalnya, biaya). Ubah fungsi ini ke dalam Model Matematika.
Contoh: F = c₁x₁ + c₂x₂
B. Tentukan Batasan (Fungsi Kendala): Tentukan semua batasan yang ada dalam permasalahan (misalnya, ketersediaan bahan baku, jam kerja). Ubah batasan-batasan ini ke dalam Model Matematika berupa pertidaksamaan. Jangan lupa sertakan Syarat Non-Negatif (x₁ ≥ 0, x₂ ≥ 0).
C. Gambar Batasan-Batasan dalam Sistem Koordinat: Gambarkan setiap pertidaksamaan batasan sebagai sebuah garis lurus.
Tentukan Daerah Penyelesaian (Daerah Layak / Daerah Feasibel), yaitu area yang memenuhi semua batasan dan syarat non-negatif. Daerah ini biasanya merupakan poligon (segi banyak) cembung.
2. Mencari Solusi Optimal
Daerah penyelesaian yang sudah ditemukan memiliki titik-titik sudut (titik ekstrem). Solusi optimal pasti terletak pada salah satu titik sudut tersebut! Ada dua cara utama untuk menemukan titik yang menyebabkan Fungsi Tujuan Optimal:
Cara 1: Metode Uji Titik Pojok
Cara ini adalah yang paling sering digunakan dan seringkali paling mudah.
• Hitung Nilai Fungsi Tujuan pada Setiap Titik Pojok : Identifikasi semua Titik Pojok (titik ekstrem) dari Daerah Penyelesaian.
• Substitusikan koordinat (x, y) dari setiap titik sudut ke dalam Fungsi Tujuan (F = c₁x₁ + c₂x₂).
• Pilih Nilai yang Sesuai: Jika ingin Memaksimalkan (Maksimisasi), pilih nilai F yang Terbesar. Jika ingin Meminimalkan (Minimisasi), pilih nilai F yang Terkecil.
Cara 2: Metode Garis Selidik
Cara ini melibatkan penggambaran visual dari Fungsi Tujuan.
Ambil fungsi tujuan (F = c₁x₁ + c₂x₂) dan buat garis bantu dengan menetapkan nilai F sembarang (misalnya, F = 0). Geser garis bantu ini secara sejajar menuju ke arah optimasi:
• Untuk Maksimum, geser garis sejajar menjauhi titik (0, 0) hingga menyentuh titik sudut terakhir dari daerah penyelesaian.
• Untuk Minimum, geser garis sejajar mendekati titik (0, 0) hingga menyentuh titik sudut pertama dari daerah penyelesaian.
Titik yang menyebabkan fungsi tujuan optimal adalah titik sudut terakhir/pertama yang disentuh oleh garis selidik yang digeser.
3. Berbagai Kemungkinan Hasil (Kejadian Penyelesaian)
Penyelesaian Program Linier tidak selalu berakhir pada satu solusi tunggal. Berikut adalah berbagai kemungkinan hasil yang dapat terjadi:
A. Solusi Optimal Tunggal
Solusi optimum dicapai pada satu titik sudut tertentu dari daerah layak. Ini adalah kasus yang paling umum dan diharapkan.
B. Optimal Alternatif (Pilihan Penyelesaian)
Terjadi ketika nilai optimal (maksimum/minimum) dicapai oleh lebih dari satu titik sudut. Ini disebabkan karena gradien fungsi tujuan sama dengan gradien salah satu ruas garis kendala yang membentuk batas daerah layak. Konsekuensinya, semua titik yang berada pada ruas garis tersebut merupakan solusi optimal yang memberikan nilai F yang sama.
C. Penyelesaian Tak Layak (Non-fisibel)
Terjadi ketika batasan-batasan yang ada saling bertentangan, sehingga tidak ada irisan (himpunan kosong) dari semua setengah bidang kendala. Karena tidak ada Daerah Layak, maka permasalahan PL tersebut tidak mempunyai solusi.
D. Penyelesaian Tak Terbatas (Unbounded)
Terjadi ketika Daerah Layak bersifat terbuka (membentang tanpa batas). Jika garis selidik digeser ke arah optimasi (misalnya ke arah maksimum), nilai F dapat meningkat tanpa batas karena tidak ada titik sudut terakhir yang dicapai. Dalam kasus ini, tidak ada solusi optimal karena nilai F tidak terbatas.
E. Degenerasi (Degeneracy)
Ini adalah kasus struktural di mana lebih dari dua garis kendala berpotongan pada satu titik sudut yang sama. Meskipun jarang mengubah solusi optimal pada metode grafik, ini menunjukkan adanya kendala berlebih atau saling terkait.
Contoh Soal
1. Cari nilai u, v tak negatif yang meminimumkan f = 100 – 20u – 10v dan memenuhi kendala
2u – v ≤ 4
3u + v ≤ 11
u + 2v ≤ 8
–u + 3v ≥ 3
u ≥ 0, v ≥ 0
Buat grafik sebagai berikut:
Perhatikan bahwa garis –u + 3v = 3 memotong sumbu v di A(0, 1), juga garis u + 2v = 8 memotong sumbu v di B(0, 4).
Garis u + 2v = 8 dan 3u + v = 11 berpotongan di C(14/5, 13/5).
Garis 3u + v = 11 dan –u + 3v = 3 berpotongan di D(3, 2).
Adapun 2u – v ≤ 4 merupakan kendala berlebih.
Diperoleh daerah solusinya di dalam segiempat ABCD. Untuk meminimumkan nilai f, diuji titik-titik pojoknya, yaitu:
f(A) = 100 – 20·0 – 10·1 = 90
f(B) = 100 – 20·0 – 10·4 = 60
f(C) = 100 – 20·(14/5) – 10·(13/5) = 18
f(D) = 100 – 20·3 – 10·2 = 20
Nilai minimum f tercapai di titik C(14/5, 13/5).
2. Cari nilai a, b tak negatif yang memaksimumkan T = 4a + 8b dan memenuhi kendala:
a + 2b ≤ 8 (1)
a + b ≤ 5 (2)
a ≥ 0, b ≥ 0
Buat grafik sebagai berikut:
Garis a + 2b = 8 dan a + b = 5 berpotongan di B(2, 3).
Garis a + b = 5 memotong sumbu a di C(5, 0).
Diperoleh daerah solusinya di dalam segiempat ABCO. Untuk memaksimumkan T = 4a + 8b, diuji titik-titik pojoknya, yaitu:
Titik O tidak mungkin maksimum karena jelas T(O) = 0.
T(A) = 4·0 + 8·4 = 32
T(B) = 4·2 + 8·3 = 32
T(C) = 4·5 + 8·0 = 20
Secara sekilas, nilai maksimum T tercapai di titik A(0, 4) dan B(2, 3), selain itu pada kasus ini nilai maksimum T tercapai di sepanjang segmen AB.
3. Cari nilai a, b tak negatif yang memaksimumkan K = 3a + 2b dan memenuhi kendala:
a + b ≤ 2 (1)
a + 2b ≥ 6 (2)
a ≥ 0, b ≥ 0
Buat grafik sebagai berikut:
4. Cari nilai a, b tak negatif yang memaksimumkan W = 4a + 2b dan memenuhi kendala:
2a – b ≤ 10 (1)
a + b ≤ 16 (2)
a ≥ 0, b ≥ 0
Buat grafik sebagai berikut:
Komentar
Posting Komentar