3.
PROGRAM LINEAR
. 1. Pengertian Program Linear Program Linear adalah suatu cara untuk penyelesaian masalah dengan menggunakan persamaan atau pertidaksamaan linear yang mempunyai banyak penyelesaian, dengan memperhatikan syarat-syarat agar diperoleh hasil yang maksimum/minimum (penyelesaian optimum). Contoh : Diketahuipertidaksamaan linear sebagai berikut : x+ y 3 2 x 5 y 10 x0 y0 Tentukan : a. Grafik dari sistem pertidaksamaan tersebut. b. Nilai maksimumnya jika Z= 3x + 2y
3 B 2 A
-5
C 3
a. Grafik dari pertidaksamaan linear berbentuk suatu daerah yaitu daerah yang diarsir. b. Nilai maksimum dari pertidaksamaan linear dapat diperoleh dari mensubstitusi koordinat-koordinat titik A , B dan C ke persamaan : Z = 3x + 2y sebagai berikut A(0,2) maka Z = 3(0) + 2(2) = 4 C(3,0) maka Z = 3(3) + 2(0) = 9 Untuk koordinat B(x,y) dapat dicari dengan mengeliminasi persamaan linear : x + y = 3 | x5 | 5x + 5y = 15 2x 5y = 10 | x1 | 2x 5y = 10 + 7x = 5 5 x = 7 5 5 16 5 16 x+y=3 +y=3 y=3 = sehingga B( , ) 7 7 7 7 7
5 16 15 32 47 6 ) + 2( ) = + = =6 7 7 7 7 7 7 Dari substitusi A, B , dan C tersebut disimpulkan bahwa nilai maksimumnya adalah 9 yang diperoleh untuk x = 3 dan y = 0 ( atau pada titik B) Z = 3( 2. Model Matematika Model matematika adalah sistim persamaan atau pertidaksamaan yang mengungkapkan semua syarat yang harus dipenuhi oleh x dan y. Model matematika ini merupakan cara sederhana untuk memandang suatu masalah dengan menggunakan persamaan atau pertidaksamaan matematika. Contoh 1 : Jika harga tiga buku dan lima pensil Rp. 30.000,00 sedangkan harga dua buku dan satu pensil Rp. 13.000,00. Buatlah model matematikanya. Penyelesaian: Misalkan satu buku = x Satu pensil = y Maka model matematikanya 3x + 5y = 30.000 2x + y = 13.000 Contoh 2 : Seorang pedagang akan membuat 2 jenis roti dengan menggunakan bahan tepung 200 gram dan mentega 25 gram untuk jenis A. Sedangkan untuk jenis B digunakan bahan 100 gram tepung dan 50 gram mentega. Jika bahan yang tersedia 3 kg tepung dan 1,1 kg mentega, tentukan : a. Model matematikanya b. Sketsa grafiknya c. Fungsi tujuan untuk keuntungan maksimum jika roti A seharga Rp. 3.600,00 dan roti B Rp. 2.400,00. Penyelesaian: Misal roti A = x dan roti B = y Jenis roti A B Persediaan Tepung 200 gr 100 gr 3 kg = 3000 gr Mentega 25 gr 50 gr 1,1 kg = 1100 gr Harga 3600 2400
a. Model matematika: Roti A 200 x + 100 y 3000 2 x + y 30 x + 2 y 44 Roti B 25 x + 50 y 1100 Banyaknya roti A adalah x 0 Banyaknya roti B adalah y 0
b. Sketsa grafik 200 x + 100 y 3000 2 x + y 30 25 x + 50 y 1100 x + 2 y 44 x0 y0
30
22
15
44
Daerah penyelesaiannya adalah daerah yang diarsir. c. Fungsi tujuan Z yang berupa keuntungan maksimum berdasarkan banyaknya roti yang dibuat yaitu : Z = 3600 x + 2400 y 3. Nilai Optimum Nilai optimum diperoleh berdasarkan nilai fungsi tujuan yang dikehendaki, yaitu berupa nilai maksimum atau nilai minimum. Cara mencarinya bias dengan : a. Mensubstitusi koordinat titik-titik sudut dalam daerah penyelesaian terhadap fungsi tujuan. b. Menggunakan garis selidik. a. Mensubstitusi koordinat titik-titik sudut dalam daerah penyelesaian terhadap fungsi tujuan. Contoh : Model matematikanya 2 x + y 12 x + 2 y 12 x0 y0 Fungsi tujuan yang maksimum/minimum , Z = 5 x + y
12 A
B(4,4) C
2x + y 1 2
6 12
Periksa koordinat titik O, A, B dan C sebagai titik-titik sudut dalam daerah penyelesaian (x,y) Z = 5 x + y O(0,0) Z = 5(0) + 0 = 0 (minimum) A(0,6) Z = 5(0) + 6 = 6 B(4,4) Z = 5(4)+4 = 24 C(6,0) Z = 5(6)+0 = 30 (maksimum) Jadi nilai maksimum sebesar 30 dicapai pada x = 6 dan y = 0, sedangkan nilai minimum sebesar 0 dicapai pada x = 0 dan y = 0 b. Menggunakan garis selidik Garis selidik adalah garis yang diperkirakan berpotongan dengan garis lain yang mendekati nilai optimum. Bentuk umum garis selidik : ax + by = k ; k R ax + by diperoleh dari bentuk fungsi tujuan garis selidik ini semakin jauh dari 0 harganya makin besar (maksimum). Contoh : Model matematikanya 2 x + y 12 x + 2 y 12 x0 y0 Fungsi tujuan yang maksimum/minimum , Z = 5 x + y Maka garis selidik ; k = 5 x + y , dengan k R
x + 2y 1 2
12 2 x + y 12 A B(4,4) C 12
5x + y = k x + 2 y 12
Tampak bahwa garis selidik terjauh dari titik O(0,0) adalah garis yang melalui titik C(6,0) yaitu Z = 5(6)+0=30.