Program Linear: Meracik Keuntungan Maksimal

Menerjemahkan Batasan Menjadi Model

Langkah pertama mencari keuntungan maksimal adalah menerjemahkan stok bahan dan resep menjadi bahasa matematika (pertidaksamaan).

Bayangkan kamu sedang memasak di dapur dengan resep dan persediaan bahan yang terbatas. Kamu ingin menentukan berapa banyak dari tiap jenis kue yang harus dibuat agar mendapat uang jajan terbanyak tanpa harus belanja bahan lagi. Di matematika, metode untuk memecahkan persoalan optimasi seperti ini disebut Program Linear.

Tabel pemetaan kebutuhan bahan baku tepung dan mentega untuk roti keju dan roti cokelat terhadap kapasitas persediaan.

Bahan Baku

Roti Keju ($x$)

Roti Cokelat ($y$)

Kapasitas Tersedia

Tepung

$200\text{ gram}$

$100\text{ gram}$

$5.000\text{ gram}$ ($5\text{ kg}$)

Mentega

$100\text{ gram}$

$100\text{ gram}$

$4.000\text{ gram}$ ($4\text{ kg}$)

Dari pemetaan di atas, batasan sumber daya ini kita sebut sebagai kendala. Karena pemakaian bahan tidak boleh melebihi persediaan yang ada, tanda pertidaksamaannya adalah $\le$:

  1. Kendala tepung: $200x + 100y \le 5.000$

  2. Kendala mentega: $100x + 100y \le 4.000$

  3. Kendala non-negatif: $x \ge 0$ dan $y \ge 0$ (karena jumlah roti mustahil bernilai negatif)

Bentuk penyederhanaan ini cocok persis dengan pernyataan pada Opsi A, sehingga Opsi A bernilai benar.

Mencari Titik Ekstrem (Titik Pojok)

Daerah yang memenuhi semua syarat (daerah penyelesaian) dibatasi oleh garis-garis kendala, dan nilai maksimum selalu berada di salah satu titik sudutnya.

Ketika batas-batas kendala $2x + y \le 50$, $x + y \le 40$, $x \ge 0$, dan $y \ge 0$ digambar pada bidang koordinat kuadran pertama, perpotongannya membentuk suatu poligon tertutup yang disebut daerah penyelesaian. Setiap titik di dalam daerah ini menunjukkan kombinasi roti yang halal diproduksi tanpa melanggar stok dapur.

Mencari pendapatan tertinggi ibarat menggeser Garis Pendapatan sejauh mungkin ke arah luar. Garis tersebut akan menyentuh batas terjauh daerah penyelesaian tepat di salah satu sudutnya, yang kita sebut titik pojok.

Untuk menemukan titik potong kedua garis kendala, kita lakukan eliminasi sederhana:

$$\begin{aligned} 2x + y &= 50 \\ x + y &= 40 \\ \hline x &= 10 \end{aligned}$$

Substitusikan $x = 10$ ke dalam $x + y = 40$, diperoleh $y = 30$. Dengan demikian, seluruh titik pojok pembatas daerah penyelesaian adalah $(0, 0)$, $(25, 0)$, $(0, 40)$, dan $(10, 30)$.

Sebuah daerah penyelesaian program linear berbentuk segi empat sembarang yang dibatasi oleh beberapa garis kendala. Jika seseorang ingin mencari nilai minimum dari fungsi biayanya, di manakah ia harus menguji nilai biaya tersebut?

  • Hanya pada keempat titik sudut daerah segi empat tersebut.
  • Pada titik koordinat yang terletak tepat di tengah segi empat.
  • Pada setiap titik koordinat bilangan bulat di dalam segi empat.
  • Hanya pada titik potong segi empat dengan sumbu koordinat saja.

Jawaban: Hanya pada keempat titik sudut daerah segi empat tersebut.

Berdasarkan teorema titik pojok pada program linear, nilai optimum (baik maksimum maupun minimum) dari suatu fungsi objektif linear selalu tercapai di titik-titik sudut (titik ekstrem) pembatas daerah penyelesaian. Kita tidak perlu menguji titik tengah maupun seluruh titik di dalam daerah tersebut, dan titik sudut tidak selalu harus berada di sumbu koordinat.

Nilai optimum (maksimum atau minimum) dari fungsi linear selalu berada di titik-titik pojok daerah penyelesaian.

Mengeksekusi Fungsi Tujuan

Setelah titik-titik pojok diketahui, langkah terakhir adalah mengujinya satu per satu ke dalam fungsi tujuan dengan teliti.

Pendapatan penjualan roti dirumuskan ke dalam fungsi tujuan, yaitu fungsi yang nilainya ingin kita maksimalkan:

$$f(x, y) = 10.000x + 7.000y$$

Sekarang, kita uji setiap kandidat titik pojok yang telah ditemukan:

  1. Titik $(0, 0)$:

    $$f(0, 0) = 10.000(0) + 7.000(0) = \text{Rp}0{,}00$$

  2. Titik $(25, 0)$:

    $$f(25, 0) = 10.000(25) + 7.000(0) = \text{Rp}250.000{,}00$$

  3. Titik $(0, 40)$:

    $$f(0, 40) = 10.000(0) + 7.000(40) = \text{Rp}280.000{,}00$$

  4. Titik $(10, 30)$:

    $$\begin{aligned} f(10, 30) &= 10.000(10) + 7.000(30) \\ &= 100.000 + 210.000 \\ &= \text{Rp}310.000{,}00 \end{aligned}$$

Nilai terbesar adalah Rp310.000,00, yang tercapai saat memproduksi $10$ Roti Keju dan $30$ Roti Cokelat. Perhitungan ini membuktikan bahwa Opsi B benar (pendapatan maksimum Rp$310.000{,}00$) dan Opsi C benar (kombinasi $10$ Roti Keju dan $30$ Roti Cokelat).