Program Linear: Memaksimalkan Laba Terbatas
Mengubah Resep Jadi Persamaan
Setiap sumber daya yang memiliki batas (seperti tepung dan mentega) harus dibuatkan satu model pertidaksamaan tersendiri.
Bayangkan kita sedang mengelola inventaris di game simulasi dapur: bahan mentah adalah resource yang terbatas, sedangkan pesanan roti adalah crafting item yang akan kita buat. Setiap tangki bahan baku punya batas kapasitas maksimal yang tidak boleh ditembus.
Untuk bahan tepung: Roti Keju ($x$) membutuhkan $200$ gram dan Roti Cokelat ($y$) membutuhkan $100$ gram. Stok tepung di gudang tersedia sebanyak $5$ kg ($5.000$ gram). Karena pemakaian tidak boleh melebihi persediaan gudang, hubungan ini ditulis:
$$200x + 100y \le 5.000$$
Bagi kedua ruas dengan $100$ agar angkanya ringkas:
$$2x + y \le 50$$
Penyederhanaan ini langsung memvalidasi bahwa Opsi A benar untuk kendala tepung.
Lakukan hal serupa untuk bahan mentega: $1$ Roti Keju butuh $100$ gram dan $1$ Roti Cokelat butuh $100$ gram dari total $4$ kg ($4.000$ gram) mentega:
$$100x + 100y \le 4.000 \implies x + y \le 40$$
Tanda pertidaksamaan $\le$ dipakai karena kita boleh menyisakan bahan baku di dapur, tetapi mustahil memakai bahan melampaui stok yang ada.
Melihat Daerah Penyelesaian
Kombinasi produksi yang mungkin dilakukan berada di area yang diarsir oleh seluruh pertidaksamaan secara bersamaan.
Setelah batas inventaris diubah menjadi model matematika, langkah berikutnya adalah memetakannya ke bidang koordinat kartesius (sumbu-$x$ untuk jumlah Roti Keju dan sumbu-$y$ untuk Roti Cokelat).
Mari gambar kedua garis batas tersebut:
Garis kendala tepung: $2x + y = 50$. Garis ini memotong sumbu-$x$ di $(25, 0)$ dan sumbu-$y$ di $(0, 50)$. Arsir area di bawah garis karena tanda pertidaksamaannya $\le$.
Garis kendala mentega: $x + y = 40$. Garis ini memotong sumbu-$x$ di $(40, 0)$ dan sumbu-$y$ di $(0, 40)$. Arsir area di bawah garis.
Wilayah yang terkena irisan dari kedua arsiran serta memenuhi batas non-negatif ($x \ge 0, y \ge 0$) disebut Daerah Penyelesaian. Setiap pasangan koordinat $(x, y)$ di dalam wilayah ini merupakan kombinasi produksi yang sah dan aman dikerjakan oleh dapur. Jika kita memilih titik di luar daerah ini, salah satu atau kedua bahan baku kita akan langsung tekor.
Dalam grafik batas area parkir suatu gedung, kendala kapasitas mobil dan motor saling berpotongan. Jika ada suatu titik koordinat yang posisinya masuk di dalam arsiran batas mobil, namun berada di luar arsiran batas motor, apa arti kondisi tersebut?
- Kapasitas parkir motor jebol alias terlampaui sehingga titik itu bukan penyelesaian
- Titik tersebut tetap bisa dipilih asalkan memuat lebih banyak mobil yang untungnya lebih besar
- Area parkir motor otomatis menyesuaikan diri sehingga kombinasi kendaraan tetap aman digunakan
- Kombinasi itu merupakan titik impas produksi karena salah satu syarat lahan parkir telah terpenuhi
Jawaban: Kapasitas parkir motor jebol alias terlampaui sehingga titik itu bukan penyelesaian
Daerah penyelesaian dari suatu sistem pertidaksamaan linear mewajibkan semua kendala terpenuhi secara serentak (hubungan logika 'DAN'). Jika suatu titik berada di luar batas motor, artinya daya tampung motor telah terlampaui (defisit kapasitas) sehingga titik tersebut mustahil menjadi penyelesaian yang sah, meskipun kapasitas mobil masih mencukupi. Keuntungan besar tidak bisa mengabaikan batasan fisik sumber daya.
Kombinasi titik yang aman harus memenuhi irisan area seluruh kendala
Mencari Titik Paling Cuan
Keuntungan maksimum hampir selalu berada di titik perpotongan batas terluar daerah penyelesaian, yang dicari dengan eliminasi.
Di dalam Daerah Penyelesaian, ada banyak kombinasi produksi yang sah. Jika kita memilih titik di tengah-tengah area secara sembarangan, bahannya memang cukup, tetapi persediaan bahan mentah tidak termanfaatkan secara penuh sehingga omzet atau koin emas (gold) yang diraih belum maksimal.
Secara matematis, nilai optimal suatu fungsi tujuan linear pada daerah tertutup selalu berada di sudut terluar atau Titik Pojok. Sudut-sudut terluar ini berada di $(0, 40)$, $(25, 0)$, dan titik perpotongan kedua garis kendala.
Untuk menemukan titik potong antara garis tepung dan garis mentega, gunakan metode eliminasi:
$$\begin{aligned} 2x + y &= 50 \\ x + y &= 40 \\ \hline x &= 10 \end{aligned}$$
Substitusikan nilai $x = 10$ ke persamaan $x + y = 40$:
$$10 + y = 40 \implies y = 30$$
Hasil ini membuktikan bahwa Opsi C benar: produsen harus memproduksi $10$ Roti Keju dan $30$ Roti Cokelat.
Sekarang, masukkan semua kandidat Titik Pojok ke fungsi pendapatan $f(x, y) = 10.000x + 7.000y$:
Titik $(0, 40)$: $10.000(0) + 7.000(40) = \text{Rp}280.000$
Titik $(25, 0)$: $10.000(25) + 7.000(0) = \text{Rp}250.000$
Titik perpotongan $(10, 30)$: $10.000(10) + 7.000(30) = \text{Rp}310.000$
Pendapatan tertinggi tercapai pada titik $(10, 30)$ sebesar Rp$310.000{,}00$, yang sekaligus memastikan bahwa Opsi B benar.
Tentukan BENAR atau SALAH untuk setiap pernyataan mengenai posisi keuntungan maksimum pada pembuatan rak sepatu berbahan kayu dan paku!
- Kita cukup menguji titik-titik di bagian paling tengah area penyelesaian untuk mencari untung maksimal. — Salah
- Titik perpotongan antara batas kayu dan paku adalah kandidat terkuat untuk menghasilkan kombinasi produksi yang optimal. — Benar
Pernyataan 1 Salah: Menurut Teorema Fundamental Program Linear, titik optimum fungsi linear selalu tercapai di tepi terluar atau titik pojok (ekstrem), bukan di bagian tengah daerah penyelesaian. Mengambil titik tengah berarti menyisakan bahan yang tidak terpakai secara optimal. Pernyataan 2 Benar: Persimpangan dua garis kendala aktif (kayu dan paku) membagi dan membatasi daerah secara ketat, menjadikannya salah satu titik sudut utama yang paling berpotensi memaksimalkan seluruh kapasitas yang tersedia.
Titik optimum selalu berada pada titik pojok (perpotongan) batas kelayakan