Program Linear: Algoritma Praktis Titik Pojok

Apa itu Daerah Penyelesaian?

Dalam matematika, pertidaksamaan seperti $2x + y \le 8$ berfungsi layaknya sebuah pagar pembatas. Garis persamaannya ($2x + y = 8$) adalah wujud fisik pagarnya, sementara tanda $\le$ (kurang dari sama dengan) menentukan sisi "halaman" mana yang boleh kita masuki.

Kumpulan dari semua area yang memenuhi seluruh syarat pertidaksamaan tersebut secara bersamaan dinamakan Daerah Penyelesaian. Di area inilah semua aturan bernilai benar.

Lalu, bagaimana cara gampang mengecek apakah sebuah titik (seperti koordinat $(2, 3)$ di soalmu) benar-benar ada di dalam daerah ini? Sangat mudah: tinggal masukkan nilai $x$ dan $y$ titik tersebut ke semua pertidaksamaannya!

Pada soalmu, ada syarat $x + 2y \le 7$ (kita akan cari tahu kenapa angkanya $7$ nanti). Kalau kamu uji titik $(2, 3)$ ke syarat itu: $2 + 2(3) = 8$ Apakah $8 \le 7$? Tentu saja salah! Oleh karena itu, kita bisa yakin banget kalau Pernyataan III itu bernilai salah.

Berdasarkan syarat pertidaksamaan $2x + y \le 8$ dan $x + 2y \le 7$, apakah titik $(4, 1)$ berada di dalam daerah penyelesaian? Mari kita buktikan!

  • A. Ya, karena $2(4) + 1 = 9$ dan $9 \le 8$
  • B. Ya, karena masuk ke salah satu syarat $4 + 2(1) = 6 \le 7$
  • C. Tidak, karena $2(4) + 1 = 9$, padahal syaratnya harus $\le 8$
  • D. Tidak, karena tidak ada titik yang boleh memiliki nilai $x$ lebih besar dari $3$

Jawaban: C. Tidak, karena $2(4) + 1 = 9$, padahal syaratnya harus $\le 8$

Saat mengecek titik $(4, 1)$ ke $2x + y \le 8$, hasilnya $2(4) + 1 = 9$. Karena $9$ tidak lebih kecil atau sama dengan $8$, syarat ini gagal terpenuhi! Satu syarat gagal saja sudah cukup untuk mengeluarkan titik tersebut dari daerah penyelesaian.

Sebuah titik hanya berada di dalam daerah penyelesaian jika ia memenuhi SEMUA syarat pertidaksamaan yang ada secara bersamaan.

Kenapa Harus Titik Pojok?

Di dalam daerah penyelesaian yang luas itu, ada tak hingga banyaknya titik. Kalau kita mau mencari di mana nilai terbesar (maksimum) atau terkecil (minimum) berada, masa harus mencobanya satu per satu? Jelas tidak mungkin.

Untungnya, para matematikawan punya sebuah pencerahan yang disebut Teorema Titik Pojok. Intinya begini: fungsi tujuan yang nilainya ingin kita maksimalkan (seperti $f(x, y) = x + y$) itu bergerak secara linier atau lurus terus tanpa berbelok.

Bayangkan fungsi itu sebagai garis lurus yang terus kita dorong membesar. Ia akan bergeser terus sampai akhirnya mentok menabrak batas terluar daerah penyelesaian.

Titik terakhir yang disenggol oleh garis tersebut sebelum keluar area selalu berada di sebuah sudut (titik pojok)!

Itulah kenapa, kita tak pernah repot-repot mengecek titik-titik di tengah area. Seluruh 'kandidat pemenang' pasti bisa kita temukan cukup dari titik perpotongan batas-batasnya saja.

Langkah 1: Temukan Titik Pojok (Eliminasi)

Karena kita sudah tahu 'pemenangnya' pasti ada di sudut, langkah praktis pertama kita adalah mencari semua koordinat titik pojoknya. Caranya mudah: cukup anggap tanda pertidaksamaan ($\le$ atau $\ge$) sebagai tanda sama dengan ($=$), dan kita mulai hitung titik potong garisnya.

Titik pojok daerah penyelesaian biasanya ada di perpotongan garis dengan sumbu $X$ (set $y=0$), sumbu $Y$ (set $x=0$), serta perpotongan antar dua garis miring di tengah-tengah.

Untuk mencari perpotongan garis miring $2x + y = 8$ dan $x + 2y = b$, kita gunakan sistem persamaan linear dua variabel (SPLDV) biasa, yaitu eliminasi atau substitusi.

Dengan langkah yang sama seperti di atas, hasil eliminasi $2x+y=8$ dan $x+2y=b$ akan menghasilkan titik pojok yang persis ada di kunci jawaban: $x = \frac{16-b}{3}$ dan $y = \frac{2b-8}{3}$.

Maka, terkumpullah $4$ kandidat titik pojok kita:

Tentukan kebenaran pernyataan berikut terkait langkah mencari titik pojok dari daerah penyelesaian!

  • Titik perpotongan antara suatu garis dengan sumbu Y bisa dicari dengan mensubstitusi nilai $x = 0$ ke persamaan garis tersebut. — Benar
  • Keberadaan huruf variabel (seperti $b$) membuat titik potong dua garis tidak mungkin lagi dicari dengan metode eliminasi. — Salah

Keberadaan variabel huruf (seperti $b$) tidak akan mematikan fungsi metode eliminasi/substitusi, buktinya kamu tetap bisa mendapatkan hasil yang berupa fungsi terhadap $b$.

Titik pojok selalu didapat dengan mengasumsikan garis pembatas sebagai sebuah persamaan, kemudian melakukan operasi aljabar biasa seperti eliminasi atau substitusi ($x=0, y=0$, dsb).