Matematik Tambahan notesnota, bab 7

Pengaturcaraan Linear

Notes made with reference toNota dibuat dengan rujukan kepada TextbookBuku teks Matematik Tambahan Tingkatan 5 (KSSM), pageshalaman 232–249

What this chapter coversMatlamat bab ini

Saya boleh membentuk model pengaturcaraan linear bagi suatu situasi dengan menentukan pemboleh ubah keputusan, fungsi objektif dan kekangan (7.1.1)
Saya boleh mewakilkan ketaksamaan linear dalam dua pemboleh ubah secara grafik, menggunakan garis padu atau garis sempang, dan melorekkan rantau yang betul (7.1.1)
Saya boleh mengoptimumkan fungsi objektif k = ax + by dengan menggerakkan garis lurus yang selari merentasi rantau tersaur atau dengan menguji titik bucu (7.1.1)
Saya boleh menyelesaikan masalah pengaturcaraan linear secara graf dalam situasi perniagaan, pengeluaran dan perancangan (7.2.1)

7.1Model pengaturcaraan linear

Pengaturcaraan linear membantu kita mengagihkan sumber yang terhad (wang, tenaga manusia, bahan mentah, masa) dengan cara yang terbaik, supaya kos diminimumkan atau keuntungan dimaksimumkan. Hasilnya ialah model matematik yang terdiri daripada kekangan dan fungsi objektif.

Suatu model pengaturcaraan linear dibentuk dalam tiga langkah (m.s. 234).

Langkah	Apa yang dibuat	Contoh: pembuat kek menghasilkan x biji kek coklat dan y biji kek keju
1. Kenal pasti pemboleh ubah keputusan	Wakilkan keputusan yang perlu dibuat dengan huruf x dan y	x = bilangan kek coklat, y = bilangan kek keju
2. Kenal pasti fungsi objektif	Tuliskan fungsi yang hendak dimaksimumkan atau diminimumkan, k = ax + by	Kos k = 4x + 5y (RM4 dan RM5 sebiji)
3. Kenal pasti kekangan	Tuliskan setiap had sebagai persamaan atau ketaksamaan linear (=, <, ≤, >, ≥) dalam sebutan x dan y sahaja	x + y ≤ 40 (tidak lebih daripada 40 biji)

Menukar perkataan kepada simbol

Perkataan	Simbol	Garis pada graf
sekurang-kurangnya, tidak kurang daripada	≥	garis padu
selebih-lebihnya, tidak lebih daripada, tidak melebihi	≤	garis padu
melebihi, lebih daripada, kurang daripada	> atau <	garis sempang

Contoh 1 (m.s. 235): menulis model matematik

(a) Perimeter sebuah bingkai gambar segi empat tepat mestilah tidak lebih daripada 180 cm.
Katakan x dan y ialah lebar dan panjang bingkai. Maka 2x + 2y ≤ 180.
(b) Seorang penjaja menjual bayam (RM3.50 sekilogram) dan sawi (RM4.50 sekilogram). Jumlah jualan sehari sekurang-kurangnya RM350.
Katakan x dan y ialah bilangan kilogram bayam dan sawi. Maka 3.50x + 4.50y ≥ 350.

Contoh 3 (m.s. 236): dua kekangan daripada satu masalah

Encik Andy membina rumah jenis A (100 m² tanah sebuah) dan jenis B (75 m² sebuah) di atas tanah seluas 10 000 m². Dia mahu membina sekurang-kurangnya 200 buah rumah. Katakan x ialah bilangan rumah A dan y ialah bilangan rumah B.
Kekangan I (luas tanah): 100x + 75y ≤ 10 000
Kekangan II (bilangan rumah): x + y ≥ 200

Kekangan hanya ditulis dengan pemboleh ubah keputusan. Ingat juga kekangan tersirat x ≥ 0 dan y ≥ 0, kerana bilangan barang tidak boleh negatif.

Mewakilkan ketaksamaan linear secara grafik

Garis mengufuk dan garis mencancang ialah kes paling mudah: y < 4 ialah rantau di bawah garis y = 4, dan x ≥ 2 ialah rantau di sebelah kanan garis x = 2 (Rajah 7.1 dan 7.2, m.s. 234).

Dua graf. (a) Garis sempang mengufuk y = 4 dengan rantau di bawahnya berlorek. (b) Garis padu mencancang x = 2 dengan rantau di sebelah kanannya berlorek — (a) y < 4 menggunakan garis sempang; (b) x ≥ 2 menggunakan garis padu.

Bagi garis ax + by = c (m.s. 235):

Jika b > 0, rantau di atas garis memuaskan ax + by ≥ c (atau > c) dan rantau di bawah garis memuaskan ax + by ≤ c (atau < c).
Garis ax = c: rantau di sebelah kanan memuaskan ax ≥ c dan rantau di sebelah kiri memuaskan ax ≤ c.
Simbol ≥ atau ≤ menggunakan garis padu (——); simbol < atau > menggunakan garis sempang (- - - -).

Contoh 2 (m.s. 236): mewakilkan ketaksamaan secara grafik

(a) x − 2y ≥ −4. Di sini b = −2 (< 0), maka rantau berada di bawah garis x − 2y = −4. Garis padu kerana simbolnya ≥.
(b) 5y − 5x < 25. Di sini b = 5 (> 0), maka rantau berada di bawah garis 5y − 5x = 25. Garis sempang kerana simbolnya <.

Dua graf dari −6 hingga 6. (a) Garis padu x − 2y = −4 dengan rantau di bawahnya berlorek. (b) Garis sempang 5y − 5x = 25 dengan rantau di bawahnya berlorek. Titik (0, 0) berada di dalam kedua-dua rantau — Rantau bagi Contoh 2 (berdasarkan m.s. 236). Titik (0, 0) berada dalam kedua-dua rantau: 0 ≥ −4 benar dan 5(0) − 5(0) < 25 benar.

Kaedah alternatif (m.s. 236): pilih satu titik yang tidak terletak pada garis, gantikan ke dalam ketaksamaan. Jika benar, titik itu berada dalam rantau; jika palsu, rantau berada di sebelah lagi. Titik (0, 0) paling mudah digunakan apabila garis tidak melaluinya.

Melorek di atas garis hanya kerana simbolnya > atau ≥. Apabila b negatif, kedudukan rantau terbalik. Uji satu titik, atau bahagikan dengan b dan balikkan simbol dahulu. Semak juga sama ada garis itu padu atau sempang.

Fungsi objektif dan pengoptimuman

Fungsi objektif ditulis sebagai k = ax + by. Rantau tersaur R ialah rantau yang memuaskan semua kekangan serentak. Pengoptimuman ialah mencari nilai maksimum atau minimum k. Nilai optimum berlaku di salah satu bucu rantau tersaur (Sudut Maklumat, m.s. 241).

Dua cara mencari nilai optimum (m.s. 237):

Lukis garis k = ax + by bagi satu nilai k yang sesuai, kemudian gerakkan garis itu selari dengan dirinya merentasi R. Bucu terakhir yang disentuh memberi nilai maksimum; bucu pertama memberi nilai minimum.
Baca koordinat setiap bucu R, gantikan ke dalam k = ax + by, kemudian pilih nilai terbesar atau terkecil.

Tip Pintar (m.s. 238): memilih k. Lihat a dan b (pekali x dan y), cari gandaan sepunya bagi a dan b, dan ambil k sebagai gandaan sepunya itu. Bagi k = 4x + 8y, ambil k = 4 × 8 = 32: pintasan-x ialah 8 dan pintasan-y ialah 4.

Contoh 4 (m.s. 237): menguji bucu

Bucu-bucu rantau berlorek ialah (15, 55), (47, 23) dan (15, 8). Cari nilai maksimum dan minimum bagi k = x + 2y.
(15, 55): k = 15 + 2(55) = 125
(47, 23): k = 47 + 2(23) = 93
(15, 8): k = 15 + 2(8) = 31
Nilai maksimum k ialah 125 dan nilai minimum k ialah 31.

(a) Tulis "bilangan van y tidak melebihi tiga kali bilangan lori x" sebagai ketaksamaan. (b) Adakah garis bagi 2x + y > 8 padu atau sempang? (c) Antara bucu (1, 2), (4, 1) dan (3, 5), bucu manakah memberi nilai terbesar bagi 2x + 3y?

Tunjuk jawapanSembunyi jawapan

(a) y ≤ 3x
(b) Sempang, kerana simbolnya ketat (>)
(c) 2x + 3y memberi 8, 11 dan 21, maka bucu (3, 5)

7.2Aplikasi pengaturcaraan linear

Masalah pengaturcaraan linear diselesaikan secara graf (m.s. 240) dengan langkah berikut.

Baca masalah, pilih pemboleh ubah x dan y, dan kenal pasti kekangan (jadual data membantu).
Tuliskan kekangan sebagai ketaksamaan linear dan lukis garisnya; lorek untuk mendapat rantau tersaur R.
Tentukan fungsi objektif k = ax + by.
Cari nilai optimum dengan menggantikan koordinat bucu R, atau dengan garis selari.

Nilai yang memuaskan semua kekangan ialah nilai tersaur; nilai yang tidak memuaskan kekangan ialah nilai tidak tersaur. Penyelesaian di dalam R (termasuk pada garis padu yang menjadi sempadannya) ialah penyelesaian tersaur.

Contoh 5 (m.s. 240–241): jambak bunga ros dan anggerik

Seorang peniaga menghasilkan x jambak bunga ros dan y jambak bunga anggerik. Masa untuk sejambak ros ialah 30 minit dan untuk sejambak anggerik 20 minit. Kekangan: I bilangan jambak anggerik tidak lebih daripada dua kali bilangan jambak ros; II bilangan jambak anggerik sekurang-kurangnya ¼ daripada bilangan jambak ros; III jumlah masa menyediakan kedua-dua jenis jambak ditunjukkan oleh garis lurus yang melalui (0, 60) dan (40, 0).
Kekangan I dan II: y ≤ 2x dan y ≥ ¼x.
Kekangan III: kecerunan m = (60 − 0)/(0 − 40) = −3/2, maka y = −(3/2)(x − 40), iaitu 3x + 2y = 120. Darab 10: 30x + 20y = 1 200 minit. Maka jumlah masa 30x + 20y ≤ 1 200, iaitu 3x + 2y ≤ 120. (Buku teks menulis "selebih-lebihnya 2 jam", tetapi 1 200 minit ialah 20 jam, dan graf serta persamaan garis itu sepadan dengan 20 jam.)

Graf dengan x dari 0 hingga 50 dan y dari 0 hingga 66. Garis y = 2x, y = x/4 dan 3x + 2y = 120 mengapit rantau segi tiga R. Titik (18, 33) ditanda di dalam R berhampiran bucu atas — Rantau tersaur R bagi Contoh 5 (berdasarkan m.s. 241).

(i) Bilangan minimum jambak anggerik jika ros 30 jambak. Gantikan x = 30 ke dalam y = ¼x: y = 7.5. Maka bilangan minimum ialah 8 jambak (bulatkan ke atas, kerana bilangan mesti nombor bulat).
(ii) Keuntungan maksimum jika untung ros RM35 dan anggerik RM25. k = 35x + 25y. Bucu atas R ialah persilangan y = 2x dengan 3x + 2y = 120, iaitu x = 120/7 ≈ 17.1 dan y ≈ 34.3, yang bukan nombor bulat. Titik bulat terbaik dalam R ialah (18, 33), kerana 3(18) + 2(33) = 120 dan 33 ≤ 36. Maka k = 35(18) + 25(33) = 630 + 825 = RM1 455. (Semak: (17, 34) memberi RM1 445 dan (20, 30) memberi RM1 450, kedua-duanya kurang.)

Contoh 6 (m.s. 242–243): membeli meja

Sebuah sekolah membeli x buah meja P (RM200 sebuah, luas 1 m²) dan y buah meja Q (RM100 sebuah, luas 2 m²). Syaratnya: I jumlah luas permukaan tidak kurang daripada 30 m²; II jumlah wang yang diperuntukkan ialah RM6 000; III bilangan meja Q selebih-lebihnya dua kali bilangan meja P.

	Meja P	Meja Q
Harga	RM200	RM100
Luas	1 m²	2 m²

(a) Kekangan (selain x ≥ 0 dan y ≥ 0)
I: x + 2y ≥ 30
II: 200x + 100y ≤ 6 000, iaitu 2x + y ≤ 60
III: y ≤ 2x

Graf dengan x dari 0 hingga 36 dan y dari 0 hingga 66. Garis x + 2y = 30, 2x + y = 60 dan y = 2x membentuk segi tiga R dengan bucu (6, 12), (15, 30) dan (30, 0). Garis sempang 4x + 8y = 32 dilukis selari dengan garis fungsi objektif — Rantau tersaur R ialah segi tiga (berdasarkan m.s. 243). Garis sempang ialah garis fungsi objektif bagi k = 32.

(c)(i) Julat meja P jika 10 meja Q dibeli. Garis y = 10 bersilang dengan R pada x = 10 (pada x + 2y = 30) dan x = 25 (pada 2x + y = 60). Maka 10 ≤ x ≤ 25.
(c)(ii) Bilangan murid maksimum. Meja P menampung 4 murid dan meja Q 8 murid, maka k = 4x + 8y. Uji bucu:

Bucu	k = 4x + 8y
(6, 12)	24 + 96 = 120
(15, 30)	60 + 240 = 300
(30, 0)	120 + 0 = 120

Bilangan maksimum murid ialah 300, dengan 15 meja P dan 30 meja Q. Titik (20, 20) dalam R memberi 4(20) + 8(20) = 240, iaitu kurang daripada 300.

Koordinat bucu diperoleh dengan menyelesaikan dua persamaan garis yang bersilang di situ. Di sini 2x + y = 60 dan y = 2x memberi 4x = 60, maka x = 15 dan y = 30.

Memasukkan titik pada garis sempang sebagai penyelesaian. Titik pada garis sempang bukan sebahagian rantau, tetapi titik pada garis padu dibenarkan. Semak juga sama ada jawapan masuk akal: kita tidak boleh membeli 2.5 buah meja, maka jawapan mesti nombor bulat.

Sebuah kedai menjual x batang pen (untung RM2 sebatang) dan y buah buku (untung RM5 sebuah). Bucu-bucu rantau tersaur ialah (0, 10), (20, 0) dan (10, 20). Cari keuntungan maksimum dan tempat ia berlaku.

Tunjuk jawapanSembunyi jawapan

k = 2x + 5y: (0, 10) memberi 50, (20, 0) memberi 40, (10, 20) memberi 120.
Keuntungan maksimum ialah RM120 pada (10, 20).

Ringkasan

Ingat	Fakta utama
Model	Pemboleh ubah keputusan x dan y, fungsi objektif k = ax + by, kekangan sebagai ketaksamaan
Jenis garis	≤ dan ≥ garis padu; < dan > garis sempang
Melorek	Uji titik (0, 0) apabila garis tidak melalui asalan
Rantau tersaur R	Tempat semua kekangan benar serentak
Nilai optimum	Di bucu R: uji setiap bucu dalam k, atau gerakkan garis selari
Bucu	Selesaikan dua persamaan garis secara serentak
Nombor bulat	Jika barang tidak boleh dipecahkan, pilih titik bulat dalam R

Istilah penting

Bahasa Melayu	English
Model matematik	Mathematical model
Kekangan	Constraint
Fungsi objektif	Objective function
Rantau tersaur	Feasible region
Pengoptimuman	Optimization