PROGRAM LINEAR A. PENGERTIAN PROGRAM LINEAR Program linear adalah aplikasi dari sistem pertidaksamaan linear dua variabel yang digunakan untuk memecahkan masalah optimasi, seperti memaksimalkan atau meminimalkan suatu tujuan. Sasaran program linear disebut fungsi objektif, yakni suatu fungsi untuk menentukan nilai maksimum atau nilai minimum dari suatu kondisi x dan y pada program linear. Fungsi objektif dari program linear dapat dinyatakan dengan: f(x,y)=Z=ax+by. B. NILAIOPTIMUM Langkah-langkah penentuan nilai optimum dengan metode titik pojok (ttik ekstrem): 1. Jika soal berbentuk soal cerita maka harus diubah menjadi model matematika terlebih dahulu. Gambarlah grafik dari model matematika tersebut. Tentukanlah daerah himpunan penyelesaiannya. Tentukaniah titik-titik pojok dari daerah tersebut. Substitusi titik-ttik pojok ke dalam fungsi objektif atau fungsi sasaran yang ditanyakan. Tentukanlah nilai yang diminta, yakni nilai maksimum atau nilai minimum. oy awn Cc. PERSAMAAN GARIS Jika soal berbentuk grafik daerah himpunan penyelesaian maka harus ditentukan sistem persamaan linear dari batas-batas daerah tersebut. 1. Persamaan garis lurus melalui titik A(x,,y,) dan B(x,,y,) adalah 2—¥2 = %—% Ya-Yy %—% 2. Garis yang memotong sumbu-sumbu koordinat ditentukan sebagai berikut. Y ax + by =abCONTOH SOAL DAN PEMBAHASAN A 1. Seorang pedagang khusus menjual produk A dan produk B. Produk A dibeli seharga Rp2.000 per unit, dijual dengan laba Rp800. Produk B dibeli seharga Rp4.000 per unit, dijual dengan laba Rp600. Jika ia mempunyai modal Rp1.600.000 dan gudangnya mampu menampung paling banyak 500 unit, keuntungan terbesar diperoleh bila ia membeli... (SNMPTN 2007) ‘A. 300 unit produk A dan 200 unit produk B B. 200 unit produk A dan 300 unit produk B C. 300 unit produk A dan 300 unit produk B D. 500 unit produk A saja E, 500 unit produk B saja Pembahasan: Batas modal: 2.000A + 4.000B < 1.600.000 => 2A +4B<1.600 Batas gudang: A+B<500 Fungsi keuntungan: Z = f(A,B)= 800A + 600B Persamaan garis lurus dari fungsi pembatas: () 2A+4B< 1.600 = 2x-+4y =1.600 = (0,400),(800,0) (i) A+B<500—> x+y =500=>(0,500),(500,0) Grafik daerah penyelesaian dari fungsi pembatas: Menentukan titik pojok daerah penyelesaian: © Titik A(0, 400) © Titik B:eliminasi (i) dan (i) didapatkan titik 8(200, 300) * Titik (500, 0) Substitusi titik pojok ke fungsi objektif keuntungan: (0,400) = 800(0) + 600(400) = 240.000 (200,300) = 800(200) + 600(300) = 340.000 (500,0) = 800(500) + 600(0) = 400.000 Nilai maksimum didapatkan dari titik potong (500, 0) sehingga keuntungan terbesar akan diperoleh bila pedagang tersebut membeli 500 unit produk A saja Jawaban: D 2. _Nilai maksimum fungsi objektif (tujuan) f(xy) =3x+2y dengan kendala x + 2y < 12, x22, dan y= adalah .... (SNMPTN 2012) A 16Cc 32 D. 36 E 38 Pembahasan: Berdasarkan fungsi kendala atau syarat batas didapatkan tiga persamaan garis: x+2y=12; x=2iy=1 Grafik dari persamaan garis tersebut: 9 1011 127 Berdasarkan grafik didapatkan titik pojok daerah penyelesaian: A (4, 0);B (10, 1); C(2, 5) Substitusi titik pojok yang ada di dalam daerah himpunan penyelesaian ke fungsi objektif: f,(2.=3(2)+2)=8 ,(10,1)=3(10)+2(1)=32 £.(2,5)=3(2)+25)=16 Jadi, nilai maksimum dari f(x,y)=3x+ 2y adalah 32. Jawaban: C UJI PEMAHAMAN Nilai maksimum dari 2=-3x+2y yang ‘A. Fungsi f mempunyai nilai maksimum memenuhi syarat 3x+y <9,5x+4y220, dan nilai minimum. dan x20 adalah... (SNMPTN 2008) B. Fungsi f tidak mempunyai_nilai A. 10 D. 20 maksimum dan nilai minimum. B14 E24 C. Fungsi mempunyai nilai minimum c 18 dan tidak mempunyainilai maksimum. D._Fungsi f mempunyai nilai maksimum. Jika fungsi fixy)=500+x+y dengan dan tidak mempunyai nilai minimum. syarat. x20,y20,2x-y-220 dan E._Nilai maksimum atau nilai minimum x+2y—620, maka ... (SNMPTN 2010) fungsi f tidak dapat ditentukan.252 Seorang penjahit akan membuat 2 model pakaian. Dia mempunyai persediaan kain batik 40 meter dan kain polos 15 meter. Model A memerlukan 1 meter kain batik dan 1,5 meter kain polos, sedangkan model B memerlukan 2 meter kain batik dan 0,5 meter kain polos. Maksimum banyak pakaian yang mungkin dapat dibuat adalah... (SBMPTN 2014) A. 10 D. 25 B. 20 E 30 G 22 Fungsi F = 10x + 15y dengan syarat x > 0, y 2 0, x < 800, y < 600 dan x + y < 1.000 mempunyai nilai maksimum ... (UM UGM 2005) A. 9.000 D. 15,000 B. 11.000 E. 16.000 Cc. 13.000 Nilai_ maksimum dari 2x+y yang memenuhi x-y+320, 3x+2y-620, x20,y20 adalah .... (UMUGM 2006) A 0 DS B 3 EB 6 a 4 Nilai maksimum dari 2=4x+9y dengan syarat_ x+2yS12,2x+yS12,x20,y20 adalah .... (UM UGM 2007) A 24 D. 52 B42 E54 c 48 Nilai minimum — dari. z=6x+9y yang memenuhi syarat 4x+y220,x+y<20,x20, dan y20 adalah .... (UM UGM 2008) A 40 D. 80 B. 50 E120 c 60 10. Nilai maksimum untuk 2=6x+3y-2 yang memenuhi sistem pertaksamaan x+2ys4 x-ys2 xty2l x20,y20 adalah .... (UM UGM 2009) A 4 B. 10 Cc 13 D. 16 EB 19 Untuk membuat barang tipe A diperlukan 4 jam kerja mesin I dan 2 jam kerja mesin Il, sedangkan untuk barang tipe 8, diperlukan 5 jam kerja mesin | dan 3 jam kerja mesin Il, Setiap hari, kedua mesin tersebut bekerja tidak lebih dari 15 jam. Jika setiap hari dapat dihasilkan x barang tipe A dan y barang tipe B maka model matematika yang tepat adalah .... (SIMAK UI 2009) A. 4x+2y<15 dan 5x+3yS15,x20,y20 B 4x+5y<15 dan 2x+3yS15,x20,y20 Cc 3x+2y<15 dan 5x+3y $15,x20,y20 D. 4x+2y<15 dan 3x+3yS15,x20,y20 E. 3x+2y<15 dan 5x+2y S15,x20,y20 Nilai minimum fungsi f(x,y) =500x+1000y pada daerah yang diarsir adalah... (SIMAK U1 2010) YA. 8.000 D. 5.000 13. B. 6.000 E4500 c 5.750 11. Nilai minimum f(x,y)=3+4x—Sy untuk x dan y yang memenuhi -xt+ys1 x+2y25 < 2x+y S10 14 adalah .... (UMUGM 2010) A -19 D3 B -6 EB 23 GAs 12. Pada sistem pertidaksamaan x - y < 0, x+y24, dan -Sy+x2-20 berlaku 2x+3y 2k . Nilai k terbesar adalah .... (UM UGM 2014) A. 25 Ds B12 EB 0 c 10 Nilai_ minimum dari fungsi z=4x+3y pada himpunan penyelesaian dari sistem pertidaksamaan: x20,y20,2x+3y26,3x-2y<9, dan x+5y $20 adalah..... (SIMAK UI 2015) AO D. 12 B 2 E 29 «6 Jika daerah_—_penyelesaian sistem pertidaksamaan x+y 2>4,ax-y <0,-x+5y<20,y20 berbentuk bidang segitiga siku-siku dengan siku-siku pada ttik potong garis x+y =4 dan ax-y=0 maka maksimum f=(3x+2y) dengan kendala sistem pertidaksamaan di atas adalah... (UM UGM 2015) A 8 D. 17 B10 E25 G15 PEMBAHASAN UJI PEMAHAMAN pembatas fungsi 1. Diketahui: fungsi 3x+y$9,5x+4y 220, x20; objektif z=-3x+2y Persamaan garislurus dari fungsi pembatas: () 3x+ys9=3x+y=9=>(0,9),3,0) (ii) Sx+4y220=95x + 4y =20 = (0,5),(4,0) Grafik daerah penyelesaian dari fungsi pembatas: 2 Berdasarkan grafik tersebut didapatkan titik pojok daerah penyelesaian: A (0,5) dan B(0,9) Substitusi titik pojok ke fungsi objektif: 2, (0,5)=3(0)+2(5)=10 2, (0,9) =3(0)+2(9)=18 Jadi, nilai maksimum dari 2=~3x+2y adalah 18. Jawaban: C Diketahui: fungsi pembatas x20,y20,2x-y-220,x+2y-620, fungsi objektif f(x,y)=500+x+y Persamaan garislurus darifungsi pembatas: (i) 2x-y-220=y=2x-2=3(0,-2),(1,0) (i 433031160) x+2y-620=3y= Grafik dari fungsi pembatas:4 Menentukan titik — pojok —daerah penyelesaian: © A(6,0) © Titik B: eliminasi (i) dan (ji) didapatkan titik B (2, 2) © (0,3) Substitusititik pojok ke fungsi objektif: £,(6,0)=500+6+0=506 f,(2,2)=500+2+2=504 £,(0,3) =500+0+3=503 Jadi, fungsi f mempuny dan tidak mempunyai_nil (tidak konvergen). minimum maksimum Jawaban: C Misalkan: x = jumlah pakaian model A, y = jumlah pakaian model B Batas penggunaan kain batik: x+2y < 40 Batas penggunaan ain _polos: 15x +0,5y $15= 3x+y $30 Fungsi objektif_ jumlah_—_pakaian: fixyl=xty Persamaan garislurus dari fungsi pembatas: () x+2y<40=9x+2y =40= (0,20),(40,0) (i) 3x+y<30=53x+y =30= (0,30),(10,0) Grafik dari fungsi pembatas: 30) OE 10 ao Menentukan titik penyelesaian: © Titik A (0, 20) © Titik B: eliminasi (i) dan (ii) didapatkan titik B (4, 18) © Titik (10, 0) Pojok —daerah Substitusi titik pojok ke fungsi objektif: f, (0,20) =0+20=20 (4,18) =4+18=22 f,(10,0)=10+0=10 Jadi, maksimum banyak pakaian yang mungkin dapat dibuat adalah 22. Jawaban: C Diketahui: x20, >0,x<800,y <600, x+y $1000; fungsi objektif F=10x+15y Persamaan garis lurus darifungsipembatas: (i) x+y<1000 x+y =1000=(0,1000),1000,0) Grafik dari fungsi pembatas: ro0y 200 Substitusi titik pojok ke fungsi objektif: 0(0,0)=>F=10(0)+15(0)=0 A(800,0) => F = 10(800)+15(0) = 8.000 B(800,200) => F = 10(800) +15(200)=11.000 C(400,600) => F = 10(400) + 15(600) = 13.000 D(0,600) => F = 10(0)+15(600) = 9.000 Jadi, fungsi F=10x+15y memiliki nila maksimum 13.000. Jawaban: C Diketahui: x-y+320, 3x+2y-620, x20,y20;fungsi objektif fixy)=2x+y Persamaan garis lurus darifungsipembatas: (i) x-y+320>x-y+3=0= (0,3),(-3,0) (ii) 3x+2y-6 20 = 3x+2y- = (0,3),(2,0) Grafik dari fungsi pembata: ySubstitusi ik pojok ke fungsi objektif: £,(2,0)=2(2)+(0)=4 f,(0,3) = 2(0)+3=3 Jadi, nilai maksimum dari 2x+y adalah 4. Jawaban: C Diketahui: X+2y S12,2x+yS12,x20,y20; fungsi objektif 2=4x+9y Persamaan garis lurus darifungsipembatas: () x4+2yS12=x+2y=12= (0,6),(12,0) (il) 2x+y <12=>2x+y=12= (0,12),(6,0) Grafik dari fungsi pembatas: Y Menentukan titik —pojok —daerah penyelesaian: © Titik A (6,0) * Titik B: eliminasi (i) dan (i) didapatkan titik B (4, 4) © Titik (0,6) Substitusi titik pojok ke fungsi objektif: 2, (6,0) = 4(6) +9(0) 24(4,4)=4(4)+9(4)=52 2,(0,6)=4(0) +9(6)=54 Jadi, nilai maksimum dari z=4x+9y adalah 54, Jawaban: E Diketahui: 4x+y>20,x-+y <20,x20, y 20; fungsi objektif z= 6x+9y Persamaan garis lurus dari fungsi pembatas: (i) 4x+y220= 4x+y=20= (0,20),(5,0) (i) x+yS20=>x+y=20=(0,20),(20,0) Grafik dari fungsi pembatas: Y aohe Substitusi titi pojok ke fungsi objektif: A(10,0) =>, =6(10)+9(0)=60 B(20,0) = z, = 6(20) + 9(0)=120 (0,20)=> z¢ = 6(0)+9(20)=180 0(!22Joas=¢(2 (2) 33 3 3 Jadi,nilai minimum dari 2=6x+9y adalah 60. Jawaban: C Diketahui: x +2y <4;x-y<2;x+y21; x20,y20 fungsi objektifz=6x + 3y-2 Persamaan garislurus darifungsipembatas: (i) x+2yS4=x+2y=4 => (0,2),(4,0) (i) x-y<2=>x-y=2= (0,-2),(2,0) Grafik dari fungsi pembatas: Substitusi titik pojok ke fungsi objektif: 2(0,2)=6(0)+3(2)-2=4 82 & 2) 5. GG) Jadi, nilai maksimum untuk 2=6x+3y—2 adalah 16. Jawaban: D9. 10. Diketahui: x = jumlah barang tipe A, y = jumiah barang tipe 8 Batas kerja untuk mesin |: 4x+5y S15. Batas kerja untuk mesin Il: 2x+3y $15 Jumlah barang tidak negatif sehingga didapatkan batas nilai x>0,y 20 Jadi, model matematika yang tepat adalah 4x+5y $15 dan 2x+3y<15,x20,y20 Jawaban: B Diketahui: fungsi objektif f(xy) =500x+1000y Grafik daerah himpunan penyelesaiannya sebagai berikut. Berdasarkan grafik tersebut didapatkan persamaan garis lurus berikut. @) 8x+4y=322x+y (i) 6x+9y=54— 2x+3} (iil), 4x+12y=48= x+3y=12 Menentukan titik —_pojok —daerah penyelesaian: © TitikA (0,8) * Titik B: eliminasi (i) dan (i) didapatkan titik 35) 2 © Titik C:eliminasi (ii) dan (ii) didapatkan titik C (6, 2) (12,0) Substitusi titik pojok ke fungsi objektif: Z,(0,8) =500(0) + 1.000(8)= 8.000 3 35 a(5 Z,(6,2) = 500(6)+ 1.000(2) = 5.000 Z, (12,0) =500(12) +1000(0) = 6.000 ese; } .000(5)=5.750 i. 12. Jadi, nilai minimum fungsi objektif pada daerah yang diarsir adalah 5.000. Jawaban: D Diketahui:-x+yS1x+2y25,2x+y<10, fungsi objektif flx.y)=3+4x-5y Persamaan garis lurus darifungsipembatas: x+y $1 -x+ = (0,1),(-1,0) x+2y 25 =>x+2y =5 => (0;2,5),(5,0) 2x+y S10 =9 2x+y =10=9(0,10),(5,0) Grafik dari seluruh syarat batas tersebut sebagai berikut. Menentukan penyelesaian: © TitikA(5,0) © Titik B: eliminasi (i) dan (ii) didapatkan titik B(1, 2) © Titik C:eliminasi () dan (ii) didapatkan titik C3, 4) titik pojok —daerah Substitusi tik pojok ke fungsi objektif: A(5,0) => 3+4(5)—5(0)=23 8(1,2) = 3+ 4(1)-5(2)=-3 (3,4) =9 3+.4(3)-514) =-5 Jadi, nilai_ minimum yang memenuhi adalah -5. Jawaban:C Diketahui: x-y<0, x+y24, Sy +x2~20 dan berlaku 2x+3y>k Nilai k terbesar berarti nilai maksimum dari 2x-+3y2k sehingga fungsi objektif adalah fy) =2x+3y13. Persamaan garislurus dari fungsi pembatas: @) x-ys0=x-y=0=9(0,0),(1,1) (i) x+y24x+y=4 (0,4),(4,0) (iil) -5y+x2-20=5 Sy +x=-20=9(0,4),-20,0) Grafik daerah penyelesaian dari fungsi pembatas: Menentukan titik pojok —_daerah penyelesaian: * Titik A: eliminasi () dan (ji) didapatkan titik A(2,2) * Titik B: eliminasi_garis (i) dan (ii) didapatkan titik B(5,5) © Titik (0,4) {(0,4) = (0,4) =2(0)+3(4)=12 Nila maksimum — f(xy)=2x+3y=25 berarti 2x+3y2k ek <25 Jadi, nilai maksimum k adalah 25. Jawaban: A Diketahui: x20,y20,2x + 3y 26,3x—2y<9, x-+5y $20, fungsi objektif 2=4x-+3y Persamaan garislurusdarifungsi pembatas: () 2x+3y26 = 2x+3y=6 = (0,2),(3,0) Ww soyssaa-2y=92(0-$ 60 (Ii) x+5y $20=>x-+5y =20=>(0,4),(20,0) 14, Grafik dari fungsi pembatas: Menentukan penyelesaian: © Titik AG,0). © Titik B: substitusi persamaan (II) ke (II) sehingga didapatkan titik B(5,3). © Titik C(0,4) dan titik (0,2). titik — pojok —daerah Substitusi titi pojok ke fungsi objektif: 2, (3,0)=4(3) +3(0)=12 2,(5,3)=4(5) +303) =. 2 (0,4) = 4(0)+3¢ 25(0,2)=4(0)+3(2)=6 Jadi, nilai minimum dari z= 4x+3y adalah 6. Jawaban:C Diketahui: x+y 24,ax-y<0,-x+5yS20,y20, fungsi objektif f =(3x+2y) Daerah penyelesaian berbentuk siku- siku dengan potong pada garis x+y=4danax-y= Pada garis lurus ax+by=c _berlaku gradien Berbentuk siku-siku artinya dua garis tersebut saling tegak lurus sehingga nilai a ditentukan sebagai berikut. -1 () x+y24>m, (W) ax-ym, =Pada dua garis yang tegak lurus berlaku persamaan berikut. m,-m, =-1 (-Na)=-1 ea=l Persamaan garis lurus darifungsipembatas: () x+y24=>xty=4=(0,4),(4,0) (W) x-ys0=x-y=0=(0,0),(11) (Il) -x+5y$20= -x+5y =20= (0,4),(-20,0) Grafik dari fungsi pembatas: Menentukan titik —pojok —daerah penyelesaiai Titik A: eliminasi (1) dan (Il) didapatkan titik A(2,2) © Titik B:eliminasi (ll) dan (Ill) didapatkan titik B(S,5) * Titikc(04) Substitusi titi pojok ke fungsi objektif: f,(2,2)=3(2)+2(2)=10 £,(5,5) =3(5) +2(5)=25 £.(0,4)=3(0)+2(4)=8 Jadi, nilai maksimum dari fungsi tersebut adalah 25. Jawaban: E