Program Linear dengan Parameter

Teorema Titik Pojok

Nilai optimum fungsi linear pada daerah penyelesaian yang tertutup pasti selalu berada di titik pojok.

Bayangkan kamu sedang mencari titik tertinggi di dalam ruang bersudut (poligon cembung). Lantai di ruangan ini tidak memiliki undakan, cekungan, ataupun bukit di tengahnya, melainkan miring secara konstan (linear). Karena kemiringannya datar sempurna ke satu arah, titik paling tinggi atau paling rendah di ruangan tersebut pasti menempel di dinding sudut ruangan (titik pojok), tidak mungkin melayang bebas di tengah ruangan.

Secara matematis, sebuah fungsi tujuan linear $f(x, y) = c_1 x + c_2 y$ membentuk bidang datar. Bidang ini memiliki gradien konstan dan tidak memiliki turunan bernilai nol di bagian dalam (interior). Oleh karena itu, kurva ketinggiannya (level curves) berupa garis-garis sejajar yang terus bertambah nilainya ke satu arah vektor normal.

Secara geometris, ketika garis selidik digeser searah peningkatan nilai, titik kontak terakhir dengan daerah penyelesaian cembung akan selalu menyentuh batas terluar—tepatnya di persimpangan batas atau titik pojok.

Artinya, untuk mencari nilai optimum, kita tidak perlu menguji titik-titik di bagian dalam daerah. Cukup kumpulkan koordinat semua titik potong batas, lalu evaluasi nilainya secara deduktif.

Mencari Titik Pojok Parametrik

Titik potong antar garis batas dapat dihitung dalam bentuk fungsi dari suatu parameter, tanpa harus mengetahui nilai pasti parameter tersebut dari awal.

Ketika menghadapi sistem pertidaksamaan dengan koefisien yang belum diketahui, jangan terjebak melakukan tebak angka secara numerik. Pola geometris pembatas tetap bekerja secara eksak. Sistem pertidaksamaan pada soal dibatasi oleh:

• Sumbu-sumbu koordinat: $x \ge 0$ dan $y \ge 0$

• Garis batas pertama: $2x + y \le 8$

• Garis batas kedua: $x + 2y \le b$

Perpotongan garis-garis pembatas ini membentuk sudut-sudut poligon. Tiga titik pojok dapat langsung diidentifikasi dari titik potong sumbu:

• Titik asal: $(0, 0)$

• Titik potong $2x + y = 8$ dengan sumbu-$x$ (saat $y = 0$): $(4, 0)$

• Titik potong $x + 2y = b$ dengan sumbu-$y$ (saat $x = 0$): $\left(0, \frac{b}{2}\right)$

Satu titik pojok krusial lainnya adalah titik potong antara garis $2x + y = 8$ dan $x + 2y = b$. Kita dapat menyelesaikannya menggunakan aljabar deduktif eliminasi-substitusi dengan mempertahankan $b$ sebagai konstanta simbolik:

$$\begin{aligned} 2x + y &= 8 \quad \implies y = 8 - 2x \\ x + 2y &= b \end{aligned}$$

Substitusikan ekspresi $y$ ke dalam persamaan garis kedua:

$$\begin{aligned} x + 2(8 - 2x) &= b \\ x + 16 - 4x &= b \\ -3x &= b - 16 \\ x &= \frac{16 - b}{3} \end{aligned}$$

Selanjutnya, substitusikan kembali nilai $x$ tersebut untuk mendapatkan koordinat $y$:

$$y = 8 - 2\left(\frac{16 - b}{3}\right) = \frac{24 - 32 + 2b}{3} = \frac{2b - 8}{3}$$

Diperoleh koordinat perpotongan kedua garis batas dalam bentuk parametrik:

$$\left(\frac{16 - b}{3}, \frac{2b - 8}{3}\right)$$

Mengevaluasi dan Menemukan b

Mensubstitusi tiap kandidat titik pojok ke fungsi tujuan memungkinkan kita membandingkan dan menyelesaikan nilai parameter.

Setelah seluruh sudut ruang poligon dinyatakan secara analitik, kita evaluasi fungsi tujuan $f(x, y) = x + y$ pada keempat titik pojok yang ada:

1. Titik $(0, 0)$:

   $$f(0, 0) = 0 + 0 = 0$$

2. Titik $(4, 0)$:

   $$f(4, 0) = 4 + 0 = 4$$

3. Titik $\left(0, \frac{b}{2}\right)$:

   $$f\left(0, \frac{b}{2}\right) = 0 + \frac{b}{2} = \frac{b}{2}$$

4. Titik potong $\left(\frac{16 - b}{3}, \frac{2b - 8}{3}\right)$:

   $$f\left(\frac{16 - b}{3}, \frac{2b - 8}{3}\right) = \frac{(16 - b) + (2b - 8)}{3} = \frac{8 + b}{3}$$

Himpunan kandidat nilai fungsi tujuan adalah $\left\{0, 4, \frac{b}{2}, \frac{8 + b}{3}\right\}$.

Diketahui dari soal bahwa nilai maksimum fungsi adalah $5$. Nilai $0$ dan $4$ jelas bukan nilai maksimum karena $4 < 5$. Maka, nilai maksimum $5$ harus berasal dari salah satu ekspresi yang memuat $b$:

• Jika kandidat maksimum adalah $\frac{8 + b}{3} = 5$:

  $$8 + b = 15 \implies b = 7$$

• Uji verifikasi untuk nilai $b = 7$:

  • Nilai pada titik potong: $\frac{8 + 7}{3} = 5$

  • Nilai pada titik sumbu-$y$: $\frac{b}{2} = \frac{7}{2} = 3{,}5$

  • Nilai pada titik sumbu-$x$: $4$

Karena $5 > 3{,}5$ dan $5 > 4$, maka nilai maksimum benar-benar tercapai sebesar $5$ saat $b = 7$. Hal ini secara formal membuktikan bahwa Opsi A bernilai benar.

Pola optimasi parametrik seperti ini sering muncul pada soal program linear tingkat lanjut di mana posisi batas atau kemiringan fungsi tujuan dikendalikan oleh suatu variabel tak tentu.