Program Linear: Alur Pasti Cari Nilai Maksimum

Menerjemahkan Cerita ke Rumus

Langkah pertama selalu mendata batasan (kendala) yang ada lalu merumuskannya dalam bentuk pertidaksamaan kurang dari atau sama dengan.

Bayangkan kamu sedang membuat paket kombinasi kue: kamu memiliki dua batasan, yaitu jumlah terigu yang tersedia (seperti batas luas lahan) dan daya tampung panggangan (seperti batas kuota kendaraan). Keuntungan maksimal akan ditentukan oleh komposisi yang pas di antara kedua batasan tersebut.

Untuk mengubah cerita soal menjadi bentuk matematika, pisahkan elemen kendaraan dan batasan sumber dayanya:

Tentukan variabel utama: misalkan $x$ = jumlah mobil dan $y$ = jumlah bus.
Kendala Lahan: Setiap mobil memakan tempat $4\text{ m}^2$, dan setiap bus memakan $20\text{ m}^2$. Sementara itu, total lahan beraspal yang ada hanya $176\text{ m}^2$. Hubungan ini ditulis:
$$4x + 20y \leq 176$$
Kedua ruas dapat disederhanakan dengan membaginya dengan $4$, menghasilkan:
$$x + 5y \leq 44$$
Kendala Kapasitas: Pintu gerbang membatasi total kendaraan yang terparkir paling banyak 20 unit, sehingga:
$$x + y \leq 20$$
Jangan lupakan kendala non-negatif, karena jumlah kendaraan tidak mungkin bernilai minus: $x \geq 0$ dan $y \geq 0$.

Simulasi di atas memperlihatkan bagaimana angka batasan pada cerita secara langsung mengisi nilai konstanta pada pertidaksamaan linear. Setiap batasan berdiri sendiri sebagai pagar pembatas alokasi kendaraan.

Sebuah toko memiliki modal Rp500.000 untuk membeli pensil seharga Rp2.000 per buah dan buku seharga Rp5.000 per buah. Kapasitas etalase toko tersebut maksimal hanya memuat 150 barang. Jika x menyatakan banyak pensil dan y menyatakan banyak buku, model matematika yang tepat adalah ...

2.000x + 5.000y <= 500.000 dan x + y <= 150
2.000x + y <= 500.000 dan x + 5.000y <= 150
x + y <= 500.000 dan 2.000x + 5.000y <= 150
2.000x + 5.000y <= 150 dan x + y <= 500.000

Jawaban: 2.000x + 5.000y <= 500.000 dan x + y <= 150

Jawaban A benar karena mengelompokkan nilai uang ke kendala modal (2.000x + 5.000y <= 500.000) dan kuantitas unit barang ke kendala kapasitas fisik (x + y <= 150). Opsi B, C, dan D mencampuradukkan satuan harga dengan batas fisik etalase.

Siswa dapat menyusun pertidaksamaan dari dua jenis kendala yang berbeda (biaya modal dan kapasitas fisik).

Kenapa Gak Pilih yang Paling Mahal?

Keuntungan tertinggi tidak didapat dengan semata-mata memilih kendaraan yang tarifnya paling mahal, karena kendaraan tersebut menghabiskan porsi batasan lahan secara tidak sebanding.

Tarif retribusi parkir bus adalah $\text{Rp}10.000$ per jam, sedangkan mobil $\text{Rp}5.000$ per jam. Sekilas tampak menggiurkan jika seluruh kuota 20 kendaraan diisi oleh bus rombongan saja agar menghasilkan $20 \times \text{Rp}10.000 = \text{Rp}200.000$ (seperti pada Opsi E). Namun, mari kita uji dengan kendala lahan:

$1$ bus memerlukan ruang $20\text{ m}^2$.
$20$ bus akan membutuhkan lahan seluas $20 \times 20\text{ m}^2 = 400\text{ m}^2$.

Kebutuhan $400\text{ m}^2$ melanggar kapasitas fisik lahan beraspal yang hanya tersedia $176\text{ m}^2$. Oleh karena itu, skenario ini mustahil terwujud.

Ilustrasi timbangan neraca klasik yang membandingkan pendapatan tinggi bus dengan pengorbanan luas lahan yang berat.

Bagaimana jika kita memilih memarkir mobil saja sampai kuota 20 unit penuh? $20$ mobil hanya memakan lahan $20 \times 4\text{ m}^2 = 80\text{ m}^2$. Lahannya memang cukup, tetapi pendapatannya hanya $20 \times \text{Rp}5.000 = \text{Rp}100.000$ (Opsi A) dan menyisakan banyak lahan kosong yang tidak termanfaatkan.

Inilah inti dari program linear: kita mencari kombinasi seimbang antara mobil dan bus agar target pendapatan pada Fungsi Objektif $f(x,y) = 5.000x + 10.000y$ mencapai titik tertingginya tanpa menabrak batas lahan maupun batas kuota.

Eksekusi: Titik Pojok Penentu

Langkah pasti untuk mencari pendapatan maksimum adalah dengan mencari titik potong antar kendala, lalu memasukkannya ke rumus Fungsi Objektif.

Dalam matematika optimasi, kombinasi terbaik selalu terletak di batas terluar wilayah yang memenuhi syarat, yang kita sebut sebagai Titik Pojok. Titik ini terbentuk dari pertemuan langsung antara garis batas lahan dan garis batas kuota.

Grafik daerah penyelesaian bidang kartesius yang menunjukkan garis Batas Lahan dan Batas Kapasitas berpotongan di titik pojok 14, 6 .

Mari kita cari titik potong kedua batas tersebut menggunakan metode eliminasi aljabar:

Tuliskan kedua persamaan garis kendalanya:
$$\begin{aligned} x + 5y &= 44 \quad (\text{Batas Lahan}) \\ x + y &= 20 \quad (\text{Batas Kapasitas}) \end{aligned}$$
Kurangkan persamaan pertama dengan persamaan kedua untuk mengeliminasi variabel $x$:
$$\begin{aligned} (x + 5y) - (x + y) &= 44 - 20 \\ 4y &= 24 \\ y &= 6 \quad (\text{banyak bus}) \end{aligned}$$
Substitusikan nilai $y = 6$ ke persamaan $x + y = 20$:
$$x + 6 = 20 \implies x = 14 \quad (\text{banyak mobil})$$

Diperoleh koordinat perpotongan optimal di titik $(14, 6)$. Sekarang kita masukkan nilai ini ke Fungsi Objektif $f(x,y) = 5.000x + 10.000y$:

$$\begin{aligned} f(14, 6) &= 5.000(14) + 10.000(6) \\ &= 70.000 + 60.000 \\ &= \mathbf{130.000} \quad (\textbf{Opsi C yang benar}) \end{aligned}$$

Mengapa kita tidak boleh sekadar menebak kombinasi sembarang?

Jika kamu menebak kombinasi sembarang yang muat 20 unit, misalnya 16 mobil dan 4 bus (kebutuhan lahan: $16(4) + 4(20) = 144\text{ m}^2 \leq 176$), pendapatannya adalah $16(5.000) + 4(10.000) = \text{Rp}120.000$ (Opsi B). Nilai ini belum maksimal.
Jika kamu mencoba memilih 16 bus agar dapat $16 \times \text{Rp}10.000 = \text{Rp}160.000$ (Opsi D), 16 bus membutuhkan lahan $16 \times 20\text{ m}^2 = 320\text{ m}^2$, yang jauh melebihi batas lahan $176\text{ m}^2$.