Pengaturcaraan Linear — Nota JomSkor

Membentuk Model Pengaturcaraan Linear

Suatu model pengaturcaraan linear dibentuk melalui tiga langkah: (1) kenal pasti pemboleh ubah keputusan yang diwakili dengan huruf $x$ dan $y$; (2) kenal pasti fungsi objektif iaitu fungsi yang hendak dimaksimumkan atau diminimumkan; (3) kenal pasti kekangan yang wujud dan wakilkan dalam bentuk persamaan atau ketaksamaan linear ($=, <, \leq, >, \geq$) dalam sebutan semua pemboleh ubah keputusan. Kaedah grafik hanya sesuai digunakan jika masalah tersebut hanya melibatkan dua pemboleh ubah keputusan.

Kedudukan Rantau Berbanding Garis Lurus $ax + by = c$

Bagi garis lurus $ax + by = c$ dengan keadaan $b > 0$: rantau di bahagian atas garis memuaskan ketaksamaan $ax + by \geq c$ dan $ax + by > c$, manakala rantau di bahagian bawah garis memuaskan ketaksamaan $ax + by \leq c$ dan $ax + by < c$. Bagi garis mencancang $ax = c$: rantau di sebelah kanan memuaskan $ax \geq c$ dan $ax > c$, manakala rantau di sebelah kiri memuaskan $ax \leq c$ dan $ax < c$.

$ax + by = c$

Jenis Garisan bagi Graf Ketaksamaan

Jika model matematik melibatkan tanda $\geq$ atau $\leq$, garis padu (garis lurus tanpa putus) digunakan kerana titik pada garis itu sendiri turut memuaskan ketaksamaan tersebut. Jika model matematik melibatkan tanda $<$ atau $>$, garis sempang (garis putus-putus) digunakan kerana titik pada garis tidak termasuk dalam penyelesaian.

Fungsi Objektif

Fungsi objektif ialah suatu ungkapan linear dalam pemboleh ubah $x$ dan $y$ yang hendak dimaksimumkan atau diminimumkan, ditulis secara amnya sebagai $k = ax + by$, dengan $k$ ialah pemalar (nilai fungsi objektif) yang berubah mengikut kedudukan garis.

$k = ax + by$

Kaedah Garis Lurus Bergerak untuk Mencari Nilai Optimum

Nilai bagi fungsi objektif $k = ax + by$ ditentukan dengan menggerakkan garis lurus fungsi objektif secara selari (menggunakan sebarang nilai $k$ yang sesuai sebagai gandaan sepunya bagi $a$ dan $b$) merentasi rantau yang memuaskan semua kekangan. Nilai optimum (maksimum atau minimum) diperoleh apabila garis tersebut melalui titik bucu terjauh rantau tersaur, iaitu dengan menggantikan koordinat titik bucu maksimum atau minimum ke dalam fungsi objektif $k = ax + by$.

Rantau Tersaur dan Nilai Tersaur

Jika suatu sistem kekangan mempunyai penyelesaian, semua kekangan akan membentuk satu rantau sepunya yang dinamakan rantau tersaur. Nilai pemboleh ubah keputusan yang memuaskan semua kekangan dikenali sebagai nilai tersaur, manakala nilai yang tidak memuaskan kekangan dikenali sebagai nilai tidak tersaur. Penyelesaian dalam rantau tersaur dikenali sebagai penyelesaian tersaur.

Langkah Menyelesaikan Masalah Pengaturcaraan Linear Secara Grafik

Masalah pengaturcaraan linear diselesaikan dengan: (1) kenal pasti kekangan yang wujud daripada situasi/jadual yang diberi; (2) tentukan fungsi objektif; (3) bina graf bagi semua persamaan linear berkaitan dan lorekkan rantau tersaur yang memuaskan semua kekangan; (4) tentukan nilai optimum dengan menggantikan koordinat setiap titik bucu rantau tersaur ke dalam fungsi objektif dan bandingkan nilainya.

Titik Optimum Terletak di Bucu Rantau Tersaur

Titik maksimum atau titik minimum bagi suatu fungsi objektif sentiasa terletak di salah satu bucu (titik persilangan) rantau tersaur. Justeru, cara alternatif untuk mencari nilai optimum ialah dengan mengenal pasti semua titik bucu rantau tersaur, menggantikan setiap satu ke dalam fungsi objektif $k = ax + by$, dan memilih nilai $k$ yang terbesar (maksimum) atau terkecil (minimum).

Kekangan Tersirat $x \geq 0$ dan $y \geq 0$

Dalam kebanyakan masalah pengaturcaraan linear berkaitan situasi sebenar (seperti bilangan barang, kos atau kuantiti pengeluaran), pemboleh ubah keputusan $x$ dan $y$ mewakili kuantiti yang tidak boleh bernilai negatif. Oleh itu, kekangan $x \geq 0$ dan $y \geq 0$ selalunya perlu disenaraikan sebagai kekangan tambahan walaupun tidak dinyatakan secara eksplisit dalam soalan.

$x \geq 0, \ y \geq 0$

Contoh soalan

Sebuah kilang menghasilkan dua jenis arca pasu, A dan B, menggunakan mesin P dan mesin Q. Jadual menunjukkan masa yang diambil (minit) untuk menghasilkan setiap jenis arca pasu: Arca pasu A mengambil 40 minit pada mesin P dan 30 minit pada mesin Q; Arca pasu B mengambil 20 minit pada mesin P dan 60 minit pada mesin Q. Kilang menghasilkan $x$ unit arca pasu A dan $y$ unit arca pasu B dalam masa seminggu. Mesin P beroperasi tidak melebihi 2000 minit. Mesin Q pula beroperasi sekurang-kurangnya 1800 minit. Penghasilan arca pasu B tidak melebihi tiga kali ganda penghasilan arca pasu A. (a) Selain $x \geq 0$ dan $y \geq 0$, tuliskan tiga ketaksamaan linear yang memenuhi semua kekangan di atas. (b) Bina dan lorekkan rantau $R$ yang memuaskan semua kekangan itu. (c) Jika keuntungan yang diperoleh daripada satu unit arca pasu A dan satu unit arca pasu B masing-masing ialah RM300 dan RM250, cari jumlah keuntungan maksimum mingguan kilang tersebut.

• Kenal pasti kekangan I daripada had operasi mesin P: masa mesin P ialah $40x + 20y$, dengan kekangan $40x + 20y \leq 2000$, iaitu $2x + y \leq 100$.
• Kenal pasti kekangan II daripada had operasi mesin Q: masa mesin Q ialah $30x + 60y$, dengan kekangan $30x + 60y \geq 1800$, iaitu $x + 2y \geq 60$.
• Kenal pasti kekangan III daripada hubungan penghasilan: $y \leq 3x$.
• Jadi, tiga ketaksamaan linear yang memenuhi semua kekangan ialah $2x + y \leq 100$, $x + 2y \geq 60$ dan $y \leq 3x$.
• Lukis graf bagi garis lurus $2x + y = 100$, $x + 2y = 60$ dan $y = 3x$ pada satah Cartesan, kemudian lorekkan rantau $R$ yang memuaskan ketiga-tiga ketaksamaan bersama $x \geq 0$ dan $y \geq 0$.
• Kenal pasti titik-titik bucu rantau tersaur $R$ dengan mencari titik persilangan pasangan garis yang berkaitan.
• Tulis fungsi objektif $k = 300x + 250y$ dan gantikan koordinat setiap titik bucu rantau $R$ ke dalam $k$.
• Bandingkan semua nilai $k$ yang diperoleh dan pilih nilai yang terbesar sebagai jumlah keuntungan maksimum mingguan.

Jumlah keuntungan maksimum mingguan diperoleh dengan menggantikan koordinat titik bucu optimum rantau $R$ ke dalam fungsi objektif $k = 300x + 250y$; nilai $k$ terbesar yang diperoleh daripada titik bucu tersebut ialah jumlah keuntungan maksimum mingguan kilang itu.