Program Linear: Mengapa Nilai Maksimum Ada di Pojok?
Membangun Daerah Penyelesaian
Daerah penyelesaian terbentuk dari irisan semua batasan yang ada, dan setiap titik di dalamnya adalah kemungkinan jawaban yang sah.
Bayangkan kita sedang mencari petak lahan untuk bercocok tanam. Syarat pertama, luas petak tidak boleh bernilai negatif: $x \ge 0$ dan $y \ge 0$. Batasan ini memagari pencarian kita agar tetap berada di kuadran pertama grafik koordinat. Selanjutnya, kita mendirikan dinding pembatas tambahan berupa pertidaksamaan linear, seperti $3x + y \le 9$ dan $x + 3y \le 11$. Wilayah berarsir di dalam pertemuan semua pagar inilah yang disebut Daerah Penyelesaian.
Titik mana pun yang berada di dalam area pagar ini—baik yang terletak persis di garis batas, di sudut pertemuan pagar, maupun di ruang kosong bagian dalam—merupakan solusi yang sah.
Mengapa Harus di Titik Pojok?
Fungsi tujuan bergerak seperti garis lurus menyapu lahan; titik terakhir yang disentuhnya sebelum keluar area pasti merupakan salah satu ujung pagar.
Ketika kita ingin memaksimalkan keuntungan dari petak lahan tersebut, kita menggunakan Fungsi Tujuan. Secara visual, fungsi linear ini bekerja seperti Garis Selidik—sebuah mistar lurus sejajar yang kita geser menyapu seluruh area dari nilai terkecil ke nilai terbesar.
Karena garis selidik ini lurus sempurna tanpa lengkungan, ia tidak mungkin menyentuh titik di tengah area sebagai titik perpisahan terakhir. Garis ini akan meninggalkan area lahan tepat di salah satu ujung pagar, atau menyusuri satu sisi pagar terluar. Oleh karena itu, posisi paling ekstrem (maksimum atau minimum) selalu berada di pertemuan antar-garis pembatas, yaitu Titik Pojok.
Dalam sebuah masalah optimasi rute terpendek yang dibatasi oleh daerah poligon 5 sisi, jika fungsi tujuannya merupakan fungsi linear, di manakah letak titik yang paling mungkin memberikan nilai maksimum?
- Di titik berat atau titik pusat poligon tersebut.
- Pada kelima titik sudut (titik pojok) poligon tersebut.
- Pada titik di dalam area yang memiliki koordinat angka bulat.
- Di garis batas yang letaknya paling dekat dengan pusat koordinat.
Jawaban: Pada kelima titik sudut (titik pojok) poligon tersebut.
Garis selidik dari fungsi tujuan linear selalu menyapu daerah cembung secara paralel. Karena bentuknya lurus tanpa lengkungan, garis tersebut selalu meninggalkan wilayah arsiran di salah satu titik sudut (titik pojok) poligon. Pengecoh A salah karena titik pusat bukan posisi ekstrem fungsi linear. Pengecoh C salah karena titik bulat di tengah tidak memberikan nilai optimal. Pengecoh D salah karena kedekatan dengan titik asal tidak menjamin nilai maksimum.
Fungsi linear mencapai nilai ekstrem (maksimum atau minimum) selalu di titik sudut (titik pojok) daerah penyelesaian yang sah.
Mencari Koordinat Pojok dengan Pasti
Titik pojok ditentukan secara pasti menggunakan eliminasi dan substitusi aljabar, bukan sekadar menebak angka.
Pada soal, diketahui nilai maksimum fungsi $f(x, y) = x + y$ adalah $5$. Artinya, garis selidik $x + y = 5$ menyinggung batas luar lahan tepat di titik potong pagar $3x + y = 9$ dan $x + 3y = c$. Menemukan koordinat titik temu ini tidak boleh mengandalkan tebakan angka (seperti mencoba $x = 1$ dan $y = 4$), melainkan harus diselesaikan secara sistematis.
Melalui substitusi terstruktur, kita mengubah $x + y = 5$ menjadi $y = 5 - x$, lalu memasukkannya ke garis pembatas $3x + y = 9$:
$$3x + (5 - x) = 9 \implies 2x + 5 = 9 \implies 2x = 4 \implies x = 2$$
Dengan nilai $x = 2$, kita peroleh $y = 5 - 2 = 3$. Titik pojok optimum tersebut berada tepat di koordinat $(2, 3)$, yang membuktikan Opsi B benar.
Diberikan dua garis pembatas wilayah dengan persamaan x - y = 1 dan x + y = 3. Bagaimana cara paling pasti untuk menentukan koordinat titik persilangan kedua garis tersebut tanpa perlu menggambar grafiknya?
- Mencoba beberapa pasangan angka bulat positif yang jika dikurangkan menghasilkan selisih 1.
- Menguji substitusi koordinat titik pangkal (0,0) ke dalam salah satu persamaan garis pembatas.
- Menjumlahkan atau mengurangkan kedua persamaan linear tersebut untuk mengeliminasi salah satu variabel.
- Mengambil nilai rata-rata dari konstanta kedua persamaan untuk menetapkan nilai x secara langsung.
Jawaban: Menjumlahkan atau mengurangkan kedua persamaan linear tersebut untuk mengeliminasi salah satu variabel.
Metode eliminasi (misalnya dengan menjumlahkan kedua persamaan: (x - y) + (x + y) = 1 + 3 sehingga 2x = 4 dan x = 2) secara pasti dan sistematis menghasilkan titik temu yang memenuhi kedua batasan sekaligus. Pengecoh A salah karena coba-coba angka bulat berisiko luput bila koordinat berupa pecahan. Pengecoh B salah karena titik (0,0) tidak menentukan perpotongan dua garis. Pengecoh D salah karena rata-rata konstanta bukan operasi aljabar yang sah untuk mencari solusi sistem persamaan linear.
Metode eliminasi atau substitusi aljabar memastikan penemuan titik potong dua garis secara eksak tanpa tebak-tebakan.