Program Linear: Metode Titik Pojok Langkah demi Langkah

Menemukan Titik Pojok Maksimum

Nilai maksimum suatu fungsi linear umumnya terjadi di perpotongan garis-garis kendala. Bayangkan kamu sedang mematok batas-batas pagar untuk sebidang lahan. Setiap pertidaksamaan kendala adalah pagar pembatas, sementara titik pojok adalah patok-patok kayu yang tertancap tepat di sudut pertemuannya. Nilai dari fungsi tujuan paling tinggi atau paling rendah selalu berlabuh di salah satu patok sudut ini.

Pada permasalahan kita, fungsi tujuan yang ingin dimaksimalkan adalah $f(x, y) = x + y$, dan diketahui nilai maksimumnya adalah $5$. Artinya, garis level capaian tertinggi yang masih menyentuh batas lahan adalah $x + y = 5$. Titik sudut maksimum ini terjadi akibat pertemuan antara garis fungsi tujuan tersebut dengan garis pembatas lahan $3x + y = 9$.

Kita dapat menemukan koordinat patok sudut tersebut secara aljabar menggunakan metode eliminasi dan substitusi:

Dengan demikian, patok sudut yang memberikan nilai maksimum berada di koordinat $(2, 3)$. Hasil perhitungan aljabar ini membuktikan bahwa Opsi B pada soal bernilai benar.

Mencari Konstanta yang Hilang

Titik pojok yang valid pasti terletak pada garis batas yang menyertakan konstanta tak diketahui. Setelah mengetahui patok sudut maksimum berada di koordinat $(2, 3)$, kita bisa mencari nilai konstanta $c$ yang belum terisi pada kendala $x + 3y \le c$.

Karena titik $(2, 3)$ merupakan titik potong garis pembatas, maka titik tersebut wajib memenuhi persamaan garis pembatasnya secara tepat, yaitu $x + 3y = c$. Kita cukup mensubstitusikan koordinat $(2, 3)$ secara langsung ke dalam persamaan:

$$\begin{aligned} x + 3y &= c \\ 2 + 3(3) &= c \\ 2 + 9 &= c \\ c &= 11 \end{aligned}$$

Dengan demikian, nilai konstanta yang memenuhi kondisi tersebut adalah $c = 11$.

Menguji Titik dalam Daerah Penyelesaian

Suatu titik dikonfirmasi berada di dalam daerah penyelesaian jika memenuhi semua pertidaksamaan kendala. Kembali ke analogi pagar lahan: jika kamu meletakkan sebuah benda di dalam pekarangan, benda itu harus berada di sisi dalam dari seluruh pagar pembatas tanpa melanggar satu pun sisi pagar.

Sekarang kita sudah melengkapi seluruh sistem pertidaksamaan kendala dengan nilai $c = 11$:

1. $x \ge 0$

2. $y \ge 0$

3. $3x + y \le 9$

4. $x + 3y \le 11$

Untuk memeriksa apakah titik $(1, 2)$ berada di dalam daerah penyelesaian seperti yang dinyatakan pada Opsi C, kita uji koordinat $x = 1$ dan $y = 2$ ke setiap pertidaksamaan:

Karena semua pertidaksamaan bernilai benar secara serentak, titik $(1, 2)$ sah berada di dalam daerah penyelesaian. Hal ini membuktikan bahwa Opsi C bernilai benar.