Banyak keputusan dibatasi beberapa syarat sekaligus: waktu kerja terbatas, bahan terbatas, permintaan terbatas. Program linear adalah cara mencari pilihan terbaik di dalam batas-batas itu, dan caranya tidak menebak melainkan memeriksa titik-titik sudutnya.
Lihat dulu
LIHAT DULU
Daerah layak dan titik sudut yang menang
Dua kendala memotong bidang menjadi satu daerah yang memenuhi keduanya. Nilai terbaik fungsi objektif selalu ada di salah satu titik sudut daerah itu, dan menggeser garis laba menunjukkan titik sudut mana yang terjauh.
5/5
Nilai terbaik selalu di titik sudut, jadi menguji keempatnya sudah cukup dan tidak perlu memeriksa titik lain.
Konsep
Pertidaksamaan dua variabel
Pertidaksamaan linear dua variabel, misalnya x + y ≤ 6, punya banyak penyelesaian sekaligus. Semuanya terletak pada satu sisi garis x + y = 6, sehingga penyelesaiannya berupa separuh bidang. Sisi mana yang diambil bisa diperiksa dengan menguji satu titik, dan titik asal adalah pilihan termudah.
Daerah layak
Kalau ada beberapa pertidaksamaan, penyelesaiannya harus memenuhi semuanya sekaligus. Irisan semua separuh bidang itu disebut daerah layak. Titik sudut daerah layak berasal dari perpotongan dua garis batas, dan jumlahnya selalu terbatas selama daerahnya tertutup. Titik sudut itulah yang nanti diuji satu per satu.
Fungsi objektif
Yang dicari biasanya nilai terbesar atau terkecil dari sesuatu, misalnya laba 3x + 2y. Bentuk itu disebut fungsi objektif. Untuk satu nilai tetap, persamaannya berupa garis lurus; mengubah nilainya berarti menggeser garis itu sejajar. Membayangkan pencariannya sebagai geseran garis membuat jawabannya terlihat sebelum dihitung.
Kenapa cukup titik sudut
Fungsi objektif berubah secara teratur di seluruh daerah, sehingga nilai terbaiknya tidak mungkin muncul di tengah. Nilai terbesar atau terkecil selalu tercapai di salah satu titik sudut, atau di sepanjang sisi yang menghubungkan dua titik sudut yang nilainya sama. Karena itu menguji seluruh titik sudut sudah cukup, dan tidak perlu memeriksa titik lain.
Rumus yang dipakai
Bentuk kendala
ax + by ≤ c
Ditambah syarat x ≥ 0 dan y ≥ 0.
Fungsi objektif
f = px + qy
Yang dicari nilai terbesar atau terkecilnya.
Garis selidik
px + qy = k
Digeser sejajar; setiap nilai k satu garis.
Uji titik sudut
f dihitung di setiap titik sudut daerah layak
Ambil nilai terbesar atau terkecil, sesuai yang diminta.
Contoh pengerjaan
Mencari nilai terbesar fungsi objektif
Daerah layak punya titik sudut (0, 0), (4, 0), (2, 4), dan (0, 6). Tentukan nilai terbesar dari f = 3x + 2y pada daerah itu, dan di titik mana nilainya tercapai.
Uji tiap titik sudut, karena nilai terbaik selalu di salah satunya.
Di (0, 0): 3 · 0 + 2 · 0 = 0.
Di (4, 0): 3 · 4 + 2 · 0 = 12.
Di (2, 4): 3 · 2 + 2 · 4 = 6 + 8 = 14.
Di (0, 6): 3 · 0 + 2 · 6 = 12.
Nilai terbesarnya 14, dan hanya titik (2, 4) yang mencapainya.
JawabanNilai terbesar 14, dicapai di titik (2, 4)
Poin penting
Satu pertidaksamaan linear dua variabel menggambar separuh bidang.
Daerah layak adalah irisan semua batasnya, dan titik sudutnya dari perpotongan garis.
Nilai terbaik fungsi objektif selalu di titik sudut, bukan di tengah daerah.
Menggeser garis selidik sejajar menunjukkan titik sudut mana yang paling jauh.
Latihan singkat
MudahSoal 1 dari 3
Daerah layak pada program linear adalah …
Layak berarti memenuhi semuanya sekaligus.
PembahasanLayak berarti memenuhi semua syarat sekaligus, jadi daerahnya adalah irisan, bukan gabungan. Gabungan justru memuat titik yang melanggar salah satu syarat. Titik potong dua garis hanyalah salah satu titik sudutnya, sedangkan garis batasnya belum tentu layak, karena sebuah titik pada garis masih harus memenuhi pertidaksamaan yang lain.
SedangSoal 2 dari 3
Urutkan langkah menyelesaikan soal program linear.
Mulai dari syaratnya, dan akhiri dengan memilih nilai.
1Gambar tiap batas, lalu ambil irisan daerahnya.
2Hitung fungsi objektif di setiap titik sudut.
3Tulis semua kendala sebagai pertidaksamaan.
4Ambil nilai terbesar atau terkecil, sesuai yang diminta.
5Tentukan titik sudut daerah layak.
PembahasanKendala ditulis lebih dulu karena daerah layak berasal dari kendala, bukan dari fungsi objektifnya. Setelah daerahnya tergambar, titik sudutnya bisa ditentukan, baru fungsi objektifnya diuji di titik-titik itu. Langkah terakhir memilih jawabannya, dan pilihannya bergantung pada soal mau terbesar atau terkecil.
SulitSoal 3 dari 3
Daerah layak punya titik sudut (0, 0), (4, 0), (2, 4), dan (0, 6). Manakah pernyataan yang benar tentang f = 3x + 2y pada daerah itu?
Hitung f di keempat titik sudut lebih dulu.
PembahasanDi (4, 0): 3 · 4 + 2 · 0 = 12. Di (2, 4): 6 + 8 = 14. Di (0, 6): 0 + 12 = 12, bukan 16, sehingga pernyataan ketiga salah. Di (0, 0) nilainya memang 0. Karena nilai terbesarnya 14 dan itu hanya dicapai di (2, 4), pernyataan terakhir juga salah.