Merekayasa Balik Sistem Pertidaksamaan

Titik Pojok dengan Variabel Misterius

Daerah penyelesaian tetap dapat dianalisis dan titik pojoknya dapat ditentukan secara aljabar meskipun salah satu batasnya memuat variabel yang belum diketahui.

Dalam program linear, kita sering menemui situasi seperti membuat paket makanan: bayangkan garis batas adalah batas maksimal stok bahan, misalnya beras dan ayam. Walaupun batas stok ayam ($b$) belum kita ketahui angka pastinya, aturan batas stok lainnya sudah jelas. Kita tetap bisa memetakan bentuk daerah penyelesaian dan merumuskan titik-titik sudutnya sebagai fungsi dari variabel $b$ tersebut.

Sistem pertidaksamaan pada kuadran pertama ($x \ge 0$ dan $y \ge 0$) memiliki dua garis pembatas:

  1. Batas pasti: $2x + y \le 8$

  2. Batas dengan variabel: $x + 2y \le b$

Titik-titik pojok yang membatasi daerah ini berada pada perpotongan garis pembatas dengan sumbu-sumbu koordinat dan perpotongan antargaris itu sendiri:

Untuk mencari titik potong antara garis $2x + y = 8$ dan $x + 2y = b$, kita gunakan metode eliminasi-substitusi:

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

Substitusikan nilai $x$ kembali ke persamaan $y$:

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

Meskipun nilai $b$ belum diketahui, koordinat titik pojok persekutuan telah berhasil kita kunci secara pasti dalam bentuk aljabar: $\left(\frac{16 - b}{3}, \frac{2b - 8}{3}\right)$.

Sebuah daerah penyelesaian dibatasi oleh $x \ge 0$, $y \ge 0$, dan garis $x + y \le c$. Manakah koordinat titik potong garis batas tersebut dengan sumbu $y$?

  • (c, 0)
  • (0, c)
  • (0, 0)
  • (c, c)

Jawaban: (0, c)

Titik potong suatu garis dengan sumbu $y$ selalu terjadi saat absis $x = 0$. Substitusikan $x = 0$ ke persamaan garis $x + y = c$, diperoleh $0 + y = c \implies y = c$. Jadi, koordinat titik potongnya adalah $(0, c)$. Pilihan $(c, 0)$ merupakan titik potong sumbu $x$, $(0, 0)$ adalah titik asal, dan $(c, c)$ bukan perpotongan sumbu.

Menentukan titik pojok ketika ada variabel batas yang tidak diketahui

Merekayasa Balik Batas

Variabel batas dapat dicari dengan mensubstitusikan koordinat titik pojok yang memuat variabel tersebut ke fungsi tujuan, lalu menyamakannya dengan nilai maksimum yang diketahui.

Banyak yang mengira nilai optimum selalu dihitung di langkah paling akhir setelah semua angka lengkap. Padahal, jika total porsi paket maksimal yang bisa dibuat sudah dipatok sebesar $5$, kita dapat melakukan rekayasa balik (reverse-engineering) untuk membongkar nilai batas $b$. Pola ini sangat lazim dalam optimasi produksi dan ekonomi ketika target laba maksimum sudah ditentukan, tetapi batasan kapasitas salah satu mesin perlu dihitung mundur.

Kita uji fungsi tujuan $f(x, y) = x + y$ pada seluruh kandidat titik pojok yang telah kita temukan sebelumnya:

$$\begin{aligned} f(0, 0) &= 0 + 0 = 0 \\ f(4, 0) &= 4 + 0 = 4 \\ f\left(0, \frac{b}{2}\right) &= 0 + \frac{b}{2} = \frac{b}{2} \\ f\left(\frac{16 - b}{3}, \frac{2b - 8}{3}\right) &= \frac{16 - b}{3} + \frac{2b - 8}{3} = \frac{8 + b}{3} \end{aligned}$$

Karena nilai maksimum yang diketahui adalah $5$, kandidat titik potong kedua garis memberikan nilai terbesar:

$$\frac{8 + b}{3} = 5 \implies 8 + b = 15 \implies b = 7$$

Dengan diperolehnya $b = 7$, pernyataan pada Opsi A bernilai benar.

Mari kita verifikasi nilai $b = 7$ ke dalam koordinat titik potong tersebut:

$$x = \frac{16 - 7}{3} = \frac{9}{3} = 3, \quad y = \frac{2(7) - 8}{3} = \frac{6}{3} = 2$$

Koordinat titik pojok yang memberikan nilai maksimum tersebut tepat berada di $(3, 2)$, sehingga pernyataan pada Opsi B terbukti bernilai benar. Titik pojok lainnya, $\left(0, \frac{7}{2}\right)$, menghasilkan $f(0; 3{,}5) = 3{,}5$, yang lebih kecil dari $5$. Ini menegaskan bahwa nilai maksimum $5$ memang dicapai di $(3, 2)$.

Fungsi tujuan suatu masalah program linear adalah $f(x, y) = 2x + 3y$. Titik pojok yang menghasilkan nilai maksimum berada pada koordinat $(k, 1)$. Jika nilai maksimum fungsi tersebut adalah $13$, berapakah nilai $k$?

  • 4
  • 6
  • 5
  • 10

Jawaban: 5

Substitusikan titik pojok $(k, 1)$ ke dalam fungsi tujuan: $f(k, 1) = 2(k) + 3(1) = 2k + 3$. Karena nilai maksimum diketahui bernilai $13$, buat persamaannya: $2k + 3 = 13 \implies 2k = 10 \implies k = 5$. Pilihan 4 terjadi akibat kekeliruan aritmatika, pilihan 6 akibat salah pindah ruas $13 - 1 = 12$ lalu dibagi 2, dan pilihan 10 akibat lupa membagi dengan koefisien 2.

Menyamakan ekspresi fungsi tujuan bersimbol dengan nilai ekstrem yang diketahui

Uji Akhir dan Pemeriksaan Titik

Setelah batasan terungkap secara utuh, kita bisa menguji posisi sembarang titik dan memverifikasi nilai fungsi dengan substitusi langsung.

Dengan ditetapkannya nilai $b = 7$, sistem pertidaksamaan kita sekarang lengkap: $x \ge 0$, $y \ge 0$, $2x + y \le 8$, dan $x + 2y \le 7$. Layaknya mengecek apakah sebuah pesanan paket khusus masih muat dalam kapasitas stok bahan dan anggaran, kita cukup memasukkan koordinatnya ke dalam batas-batas yang ada.

Diagram daerah penyelesaian linear dengan b = 7, menunjukkan titik asal 0,0 , titik potong 3,2 , dan titik 2,3 yang terletak di luar daerah arsiran.

Mari kita periksa tiga pernyataan tersisa: