Program Linear: Aljabar Titik Pojok
Pemodelan dan Daerah Batas
Daerah penyelesaian dibentuk dari irisan semua pertidaksamaan batas stok sumber daya yang ada.
Dalam masalah ini, stok zat A adalah $6\text{ gram} = 6.000\text{ mg}$ dan zat B adalah $4\text{ gram} = 4.000\text{ mg}$. Jika $x$ menyatakan banyaknya racikan pertama dan $y$ menyatakan racikan kedua, batasan stok dimodelkan sebagai sistem pertidaksamaan linear:
Batas Zat A: $400x + 200y \le 6000 \iff 2x + y \le 30$
Batas Zat B: $300x + 100y \le 4000 \iff 3x + y \le 40$
Batas Non-negatif: $x \ge 0$ dan $y \ge 0$ (karena jumlah racikan tidak mungkin bernilai negatif).
Tiap garis batas memotong sumbu koordinat:
Garis $2x + y = 30$ memotong sumbu-$x$ di $(15,0)$ dan sumbu-$y$ di $(0,30)$.
Garis $3x + y = 40$ memotong sumbu-$x$ di $\left(\frac{40}{3}, 0\right)$ dan sumbu-$y$ di $(0,40)$.
Daerah penyelesaian yang sah adalah irisan poligon tertutup yang dibatasi oleh titik $(0,0)$, $\left(\frac{40}{3}, 0\right)$, $(0,30)$, dan satu titik temu kedua garis di bagian tengah.
Pembuktian Titik Pojok
Fungsi objektif berbentuk garis lurus yang bergeser sejajar, sehingga nilai optimumnya pasti tercapai saat garis itu menyentuh titik paling ujung daerah penyelesaian.
Tujuan apoteker adalah memaksimumkan pendapatan $f(x,y) = 8000x + 3200y$. Misalkan kita menargetkan suatu nilai pendapatan tertentu $k$, maka persamaan pendapatan tersebut menjadi $8000x + 3200y = k$. Jika dituliskan dalam bentuk gradien:
$$y = -\frac{8000}{3200}x + \frac{k}{3200} = -\frac{5}{2}x + \frac{k}{3200}$$
Persamaan ini memodelkan sekelompok garis lurus yang memiliki gradien tetap $-\frac{5}{2}$. Nilai $k$ menentukan posisi perpotongan garis terhadap sumbu-$y$. Memperbesar nilai $k$ sama artinya dengan menggeser garis lurus ini menjauhi titik pangkal $(0,0)$ secara sejajar tanpa mengubah kemiringannya.
Ketika garis digeser sejauh mungkin untuk mencari nilai maksimum, garis tersebut akan meninggalkan daerah penyelesaian. Titik singgung terakhir sebelum garis benar-benar lepas selalu berada di batas terluar yang runcing, yaitu sebuah titik pojok. Teorema dasar program linear membuktikan bahwa titik di bagian dalam poligon tidak mungkin menghasilkan nilai yang lebih ekstrem dibanding titik di sudut-sudut batasnya.
Sebuah perusahaan memodelkan batas produksinya dalam bentuk poligon tertutup dan ingin meminimalkan fungsi ongkos $f(x,y) = 500x + 300y$. Secara analitis, di manakah nilai minimum fungsi tersebut pasti tercapai?
- Di pusat massa atau titik tengah geometri dari daerah penyelesaian.
- Pada salah satu titik pojok daerah penyelesaian terdekat dari pangkal.
- Pada titik potong sumbu x atau sumbu y secara spesifik.
- Pada setiap titik sepanjang batas terluar bidang poligon secara acak.
Jawaban: Pada salah satu titik pojok daerah penyelesaian terdekat dari pangkal.
Fungsi objektif berbentuk linear ax + by = k memodelkan garis-garis sejajar. Saat mencari nilai minimum, garis selidik digeser mendekati pangkal koordinat dan titik kontak pertamanya dengan daerah penyelesaian pasti jatuh pada sebuah titik pojok (ekstrem), bukan di tengah daerah atau sembarang titik batas acak. Titik optimum juga tidak selalu berada di sumbu koordinat karena bisa terletak pada perpotongan dua garis batas.
Sifat garis fungsi objektif linear yang menjamin nilai optimum berada di titik pojok ekstrem.
Titik Potong Lewat Eliminasi
Titik pojok di perpotongan dua garis batas dicari secara eksak dengan menyelesaikan sistem persamaan linear secara bersamaan (eliminasi-substitusi).
Selain titik potong terhadap sumbu koordinat, terdapat satu titik pojok di pertemuan antara Garis I ($2x + y = 30$) dan Garis II ($3x + y = 40$). Karena kedua garis memiliki koefisien variabel $y$ yang sama, yaitu $1$, kita dapat mengeliminasi variabel $y$ secara langsung dengan mengurangkan kedua persamaan:
$$\begin{aligned} 3x + y &= 40 \\ 2x + y &= 30 \\ \hline (3x - 2x) + (y - y) &= 40 - 30 \\ x &= 10 \end{aligned}$$
Setelah nilai $x = 10$ ditemukan, lakukan proses substitusi ke salah satu persamaan batas, misalnya ke Garis I:
$$\begin{aligned} 2(10) + y &= 30 \\ 20 + y &= 30 \\ y &= 30 - 20 \\ y &= 10 \end{aligned}$$