Prinsip-prinsip Riset Operasi nt ——— | 24 | PENDAHULUAN Sebuah organisasi harus membuat ke putusan mengenai cara mengalokasikan sumber-sumbernya, dan tidak ada organisasi yang beroperasi secara permanen dengan sumber yang tidak terbatas, akibatnya manajemen harus secara terus- menerus mengalokasikan sumber yang langka untuk mencapai tujuan yang optimal. Tlap organisasi mencoba untuk mencapai tujuan tertentu sesuai dengan barasan sumber (tabungan, anggaran, bahan-bahan produksi), Program linier merupakan model matematik untuk mendapatkan alternatif Penggunaan terbaik atas sumber-sumber organisasi. Kata sifatlinier digunakan untuk menunjukkan fungsi-fungsi matematik yang digunakan dalam bentuk linier dalam arti hubungan langsung dan persis proporsional. Program menyatakan penggunaan teknik matematik tertentu, Jadi pengertian program linier adalah suatu teknik perencanaan yang bersifat analitis yang analisisnya menggunakan model matematis, dengan tujuan menemukan beberapa kombinasi alternatif pemecahan optimum tethadap persoalan, seudenisth sou srt ib, —|22} emi ma BENTUK UMUM MODEL PROGRAM LINIER Bentuk umum model program linier: Optimumkan Z= Sox, in dengan batasan: Pi Saye, 25d, untuk i= 12,3 a x, 20, untuk j = 12,3, atau dapat ditulis secara lengkap sebagai berikut Optimumkan Z = Oey + CyXy Hoe FG %y dengan batasan:12 Bab 2m Program Linier: Metode Grafik Ay Xt Xp Hot yh, 2S 4 Ayyky + ayy tot Monk, 2S br Ay hy + igh to + bynty 2S Om Kp po Xap My 20 Kererangan: = fungsi tujuan yang dicari nilai optimalnya (maksimal, minimal) kenaikan nilai Z apabila ada pertambahan tingkac kegiatan x, dengan satu ing 7 acuan unit atau sumbangan setiap satuan keluaran kegiatan j tethadap Z n= macam kegiatan yang menggunakan sumber atau fasilitas yang tersedia m = macam batasan sumber atau fasilitas yang tersedia vy = tingkat kegiatan ke: dq + banyaknya sumber 7 yang diperukan unwuk menghaslkan seap unit keluaran kegiatan j = kapasitas sumber i yang tersedia untuk dialokasikan ke setiap unit kegiatan ‘Terminologi umum untuk model program liniet di atas dapat dirangkum sebagai berikut: 1. Fungsi yang akan dicari nilai optimalnya (Z) disebut fungsi tujuan (objec- tive function) 2. Fungsi-fungsi batasan dapat dikelompokkan menjadi dua macam, yaitu: a. Fungsi batasan fungsional, yaitu fungsi-fungsi batasan sebanyak’ m. b. Fungsi batasan non-negatif (non-negative constrains) yaitu variabel x, 2 0 3. Variabel-variabel x; disebur sebagai variabel keputusan (decision variables). 4. Parameter model yaitu masukan konstan 4,y 6, dan G, ‘Agar penggunaan model program linier di atas memuaskan tanpa terbentur pada berbagai hal, maka diperlukan asumsi-asumsi dasar program linier sebagai berikeut: 1. Proportionality, asumsi ini berarti nai turunnya nilai Z dan penggunean sumber atau fasilitas yang ersedia akan berubah secara sebanding dengan perubahan tingkat kegiatan, Misal:Prinsip-prinsip Riset Operasi 13, & Ze om + ak + oxy +O, Setiap pertambahan 1 unit x, akan menaikkan Z sebesar ¢,. Setiap pertambahan 1 unit x, akan menaikkan Z sebesar cy» dan seterusnya, OX ae + ayy a ta, S by Setiap pertambahan 1 unit x, akan menaikkan penggunaan sumber daya/fasilitas ke 1 sebesar 4,,. Dengan kata lain, setiap ada kenaikan kapasitas rill tidak perlu ada biaya persiapan (set-up cost). Additivity, berarti nilai cujuan tiap kegiatan tidak saling mempengaruhi, atau dalam program linier dianggap bahwa kenaikan suatu kegiatan dapat ditambahkan tanpa mempengaruhi bagian nilai Z yang diperoleh dari kegiaran lain, Misal: Z = 4x, + 7x, di mana x, = 30; x, = 20 sehingga Z = 120 + 140 = 260 Andaikan x, bertambah 1 unit, maka sesuai dengan asumsi pertama, nilai Z menjadi 260 + 4 = 264. Jadi, nilai 4 karena kenaikan x, dapat langsung ditambahkan pada nilai Z mula-mula tanpa mengurangi bagian Z yang diperoleh dari kegiatan ke-2 (x,). Dengan kata lain, tidak ada korelasi antara x, dan x. 3. Divisibility, berarti keluaran yang dihasilkan oleh setiap kegiatan dapat berupa bilangan pecahan. Misalkan nilai Z = 17,5 5 x = 6,1 4, Deterministic (certainty), berarti bahwa semua parameter (a,, b, 9) yang, a py terdapat pada program linier dapat diperkirakan dengan pasti, meskipun dalam kenyataannya tidak sama persis. PEMECAHAN PERSOALAN PROGRAM LINIER DENGAN MENGGUNAKAN METODE GRAFIK Metode grafik merupakan salah satu teknik pemecahan model program linier yang hanya memuat dua variabel keputusan. Langkah-langkah pemecahan dengan metode grafik adalah sebagai berikut: 1. Gambarkan sebuah bidang koordinat dengan kedua variabel sebagai sumbu- sumbu koordinat.14 Bab 2m Program Liniet: Metode Grafik 2. Gambarkan garis-garis fungsi batasan dengan menganggap batasannya sebagai persamaan. 3. Tentukan daerah dalam bidang koordinat yang memenuhi semua batasan, dacrah ini disebut sebagai dacrah layak (feasible region). 4. Tentukan koordinat titike sudut (disebut sebagai titi ekserim). Hitung harga fungsi tujuan untuk semua titik sudut, kemudian pilih harga yang optimal sebagai pemecahan persoalan. Contoh 2.1 y panes Ba a tat PT Dimensi adalah sebuah perusahaan furnitur produsen meja dan kursi yang harus diproses melalui perakitan dan pemolesan. Fungsi proses perakitan memiliki 60 jam kerja dan fungsi proses pemolesan memiliki 48 jam kerja. Untuk meng- hasilkan satu meja dibutuhkan masing-masing 4 jam dan 2 jam untuk perakitan dan pemolesan, sedang satu kursi membucuhkan masing-masing 2 jam dan 4 jam untuk perakitan dan pemolesan. Laba untuk tiap meja $8 dan tiap kursi $6. Sekarang kita harus menentukan kombinasi terbaik dari jumlah meja dan kursi yang harus diproduksi, agar menghasilkan laba maksimal. Penyelesaian: Informasi yang diperlukan untuk memecahkan persoalan ini dapat dirangkum dalam Tabel 2.1 berikut. Tabel 2.1. Informasi Produksi PT Dimensi Wakeu yang diburuhkan =Total jam uuncuke satu unie produk (jas) tersedia " Perakitan 2 60 Pemolesan 2 4 48 Laba/unit 88 36 — Formulasi persoalan: Misalkan: x = jumlah meja yang dibuat y= jumlah kursi yang dibuat Z = jumlah kontribusi laba seluruh meja dan kursi Model program liniernya adalah:Prinsip-prinsip Riset Operasi , 15 Maksimumkan laba: Z = 8x + Gy Dengan batasan: 4x + 2y S60 > fungsi batasan proses perakitan 2e + 4y S48 > funy xdany20 (Fungsi tujuan) gsi batasan proses pemolesan Gambarkan barasan-batasan pada bidang koordinat: Gambar 2.1. Fungsi Batasan-batasan y 30 gee Fungsi perakitan 12 DF _——— Fungsi pemolesan Lee 1524 Gambar 2.2. Daerah Layak J t A(00) 05.0) Dari grail aas ci sud yang diketahul ada A,B, dan Csedangkan ek sudut D dapat dicari dengan eliminasi antara persamaan satu dan dua, yaitu: 4x + 2y = 60 kalikan dengan (2): 8x + 4y = 120 2x + Ay = 48 2x4 dys 48 ~ 6x 2, maka x = 1216 Bab 2m Program Linier: Metode Grafik Substitusikan x = 12 ke dalam persamaan kedua: 2(12) + 4y = 48 4y = 24, schingga y = 6 Jadi titik D adalah (6,12). Langkah berikutnya, hitung nilai empat titik sudut dengan cara men- substitusikan ke dalam fungsi tujuan untuk melihat kombinasi mana yang meng- hasilkan laba terbesar. Titik A (0,0): Z = 8(0) + 6(0) Titik E (0,12) : Z = 8(0) + 6(12) Titik C (15,0) : Z = 8(15) + 6(0) Titik D (12,6) : Z = 8(12) + 6(6) = 132° Ternyata titik yang menghasilkan laba terbesar adalah D($132). Jadi ticik inilah yang paling optimal. Keputusannya meja dibuat sebanyak 12 buah dan kursi 6 buah. Selain cara di atas, ada cara lain untuk menencukan titik yang paling op- timal yaitu dengan menggambarkan gars fungsi ujuan (isproft) tetapi cara ini dirasa kurang praktis schingga tidak penulis jelaskan di sini. BEBERAPA MASALAH TEKNIS DALAM PROGRAM LINIER a. Masalah minimasi Contoh di atas merupakan model program linier di mana tujuan yang dicati adalah maksimasi, yaitu mendapatkan laba yang paling besa. Bila fungsi tujuan- nya minimasi maka alternatif yang optimal adalah alternatif yang dapat me- minimumkan nilai Z. b. Fungsi batasan bertanda “lebih besar atau sama dengan’ (2). Apabila fungsi batasan bertanda 2 maka daerah feasibel akan berada di sebelah kanan atas garis batasan,Prinsip-prinsip Riset Operasi 7 c. Fungsi batasan bertanda “sama dengan” (-) Apabila fungsi batasan bertanda =, maka daerah feasibel akan terletak pada garis yang memiliki tanda sama dengan, d. Redundancy Barasan yang tidak mempengaruhi daerah yang memungkinkan disebut redun- dancy batasan. Misalkan pada permasalahan PT Dimensi di atas ada tambahan batasan dari manajer pemasaran bahwa ia tidak dapat menjual lebih dari 20 kursi (lihat Gambar 2.3). Katena jumlah jumlah kursi maksimum dalam daerah feasibel hanya berjumlah 12 (pada titik E) maka batasan baru manajemen pemasaran itu merupakan kelebihan, Jadi bacasan pemasaran dapat diilangkan guna menghemat waktu pethitungan, Dalam banyak persoalan program linier, Kelebihan barasan tidak dihilangkan karena belum diketahui sebagai kelebihan sampai persoalan dipecahkan. Dengan penggunaan komputer untuk memecahkan persoalan program linier, kelebihan batasan tidak menimbulkan kesulitan. Gambar 2.3. Persoalan PT Dimensi dengan batasan pemasaran (y < 20) y 30 Baasan pemsaran y $ 20 oo Fungsi perakitan en Fungsi pemolesan 20 Eee | 25 | a SOAL-SOAL Soal-soal Telaah dan Penyelesaiannya 1. Sebuah industri keramik membuat dua jenis produk unggulan A dan B. Uneule menghasilkan satu buah jenis A diperlukan wakew pengerjaan 1 jar dan bahan baku 4 kg, sedangkan jenis B membutubkan 2 jam dan bahan18 Bab 2 m Program Linier: Metode Grafik Waktu dan bahan baku yang tersedia masing-masing 40 jam ssh 120 pel tiap unit A dan B masing-masing $40 dan $50, a. Tentukan model program linier untuk persoalan datas, b. Tenrukan dengan metode grafik berapa jumlah yang harus diproduksi untuk masing-masing jenis produk, sehingga keuntungan mencapai maksimum Penyelesaian: Misalkan x, = jumlah yang diproduksi untuk jenis A, dan x)= jumlah yang diproduksi untuk jenis B ‘Tujuan dari persoalan tersebur adalah untuk memaksimumkan total keuntungan dari jumlah produksi masing-masing jenis. Maksimumkan: Z = 40x, + 50x, Model mempunyai batasan sumber daya, x + ay < 40 (batasan wakeu) 4x, + 3x) < 120 (batasan bahan baku) Model lengkap dari persoalan program liniernya adalah, Maksimumkan: Z = 40x, + 50x, Batasan-batasan: x + 2x, <40 4x, + 3x, S120 Xx 20 Titik-titik sudut pada daerah feasibel: Titik sudut O (0,0) berarti tidak m Titik sudut A (0,20) > Z = 40(0) + 50(20) = $1000 Titik sudut C (30,0) + Z = 40(30) + 50(0) = $1200 Perpotongan garis 4x, + 3x, = 120 dan % + 2x, = 40 menghasilkan Titik sudut B (24,8) Z = 40(24) + 50(8) = $1360 emproduksi apa-apa > Z = 0 Grafik Fangsi batasan dan daerah layak sebagai betikuntPrinsip-prinsip Riset Operasi 19 4x, + 3x, < 120 Titik optimal Sehines Keputusannya adalah keuntungan maksimum diperoleh pada nila = $1360, Pada produksi jenis A = 24 buah dan jenis B = 8 buah. Sebuah toko yang menjual keperluan pertanian menyediakan dua merck Pupuk kimia, yaita Super dan Top. Setiap jenis mengandung campuran bahan nitrogen dan fosfat dalam jumlah tertencu, Jenis Kandungan bahan kimia Nitrogen (kg/sal) Fosfat (kg/sak) oped | |) apd Wott lar A) 7 ‘Top 4 3 Seorang petani membutuhkan paling sedikit 16 kg nitrogen dan 24 kg fosfat untuk lahan pertaniannya. Harga pupuk Super dan ‘Top masing- masing $6 dan $3. Petani tersebut ingin mengetahui betapa sak masing- masing jenis pupuk harus dibeli agar total harga pupuk mencapai mini- mum dan kebutuhan pupuk untuk lahannya terpenuhi. Selesaikan dengan metode grafik. Penyelesaian: Formulasi model: Misal x, = banyaknya pupuk merek Super yang dibeli x = banyaknya pupuk merck TOP yang dibeli Model program liniernya: Minimumkan: Z = 6x, + 3%20 —-Bab2. m Program Liner: Metode Grafik Batasan-batasan: 2x, + dx, 216 4x, + 3x, 2 24 xp % 20 Dengan cara yang sama seperti pada Soal no.1, maka diperoleh titik optimal pada titik sudut A, di mana petani sebaikinya tidak perlu membeli merek super sedangkan jumlah pembelian uncuk pupuk merek TOP adalah 8 sak dengan minimum harga total Z = 6(0) + 3(8) = $24, Grafik model program liniernya %) Titik optimal — Daerah feasibel 2x, + dxy = 16 3. Sebuah industri kerajinan kulit membuat tas yang terdiri dati jenis A dan B. Keuntungan masing-masing jenis tas adalah $400 dan $200 dolar per uunit, Industri mendapat kontrak pesanan dati sebuah toko sebesar 30 (A dan B) buah per bulan. Suplai bahan kulic paling sedikit 80 lembar per bulan, dan industri kerajinan ini harus memesan paling tidak 80 lembar per bulan. Setiap barang A membutuhkan 2 lembar kulit sedangkan barang B membutuhkan 8 lembar, Dari pengalaman sebelumnya industt ini tidak bisa membuat barang jenis A lebih dari 20 buah per bulan. Mereka ingin mengetahui berapa jumlah masing-masing jenis A dan B yang harus dibuat supaya keuntungan yang didapat maksimum, Tentukan model program liniemnya dan selesaikan persoalan ini dengan metode graf Penyelesaian: Formulasi model Misalkan x, = produk A dan x, = produk BPrinsip-prinsip Riset Operasi 21 Model program liniernya: Maksimumkan: Z = 400x, + 200x, Batasan-batasan: a+ x = 30 2x, + 8x, 2 80 x, < 20 p20 a x $20 f Titik optimal B(20,10) ay, + 8x, 2 80 Titik sudue yang dibentulk oleh daerah feasibel adalah: © (0,10) menghasilkan Z = 400(0) + 200(10) =2.000 A (0,30) menghasilkan Z = 400(0) + 200(30) = 6.000 B (20,10) menghasilkan Z = 400(20) + 200(10) = 10.000 C (20,5) menghasilkan Z = 400(20) + 200(5) = 9.000 Terlihat bahwa nilai terbesar dari Z adalah 10.000, jadi keuntungan maksimum diperoleh pada produksi jenis A = 20 buah dan jenis B = 10 buah dengan keuntungan maksimum sebesar $10.000.wt: Metode Grafik 22 Bab 2m Program Soal-soal Pilihan Ganda Gunakan gambar berikut untuk menjawab y 4 4 ‘| 3 aa ghee INU SETS Grafik 1 Grafik I Grafik IIL Grafik IV soal nomor 1 s/d 4. 1. Grafik untuk batasan 3x + 4y 2 12 adalah a. Grafik I cc. Grafik IIL b. Grafik IT d. Grafik IV 2. Grafik untuk batasan 4x + 3y S$ 12 adalah a. Grafik I «Grafik IIL b. Grafik IT d. Grafik IV 3. Jika fungsi kendala diberikan sebagai berikut: 2x + Gy S12 4x + By S12 wy20 maka titik sudutnya pada daerah layak didapat: a (0,2):(6,0)5(4/3,2) & (3,0)s(2,4/3)3(0.4) b. (0,2)s(2,4/3)3(3,0) d. (6,0)5(4/3,2);(0,4) 4. Pemecahan model program linier dengan metode grafik digunakan apabila modelnya memuat a, 2 batasan ©. 1 fungsi tujuan b. 2 variabel kepucusan d. 2 kendala 5. Selain metode grafik program linier bisa disclesaikan dengan metode a. Matematis & Minimasi b. Least cost 4. Simpleks 6. Bila titik sudut sudah diperolch maka langkah selanjutnya dalam pemecahan Linear programming dengan metode grafik adalah10. Prinsip-prinsip Riset Operasi 2B Menggambarkan bidang koordinat Tentukan daerah layake Hitung fungsi tujuan Gambarkan garis kendala aoe Pernyataan tentang daerah layak yang benar berikut ini adalah a. Bidang koordinat yang betharga positif b. Koordinat yang memenuhi semua kendala c. Himpunan variabel non-negatif d. Semua benar Bila dua pertidaksamaan < tidak memotong satu sama lain dalam kuadran grafik di mana kedua variabel positif, maka: a. Persoalan mustahil dipecahkan b, Satu dari batasan adalah redundan c. Pemecahan tidak rerbatas dd. Semua salah Bila suacu persoalan mempunyai satu batasan > dan saru batasan S serta keduanya tidak berporongan dalam kuadran grafik di mana kedua variabel positif, maka a. Persoalan mustahil dipecahkan b. Satu dari barasan adalah redundan c. Pemecahan tidak terbatas d. Semua salah Bila semua batasan pertidaksamaan 2 untuk persoalan program linier disertai fungsi tujuan memaksimumkan, maka: a. Persoalan mustahil dipecahkan b. Satu dari batasan adalah redundan c. Pemecahan tidak terbatas d. Semua salah Soal-soal Latihan 1. Dua macam produk dibuar melalui serangkaian proses yaitu mesin pereama, mesin kedua dan mesin ketiga, Masing-masing mesin dibatasi_waktu prosesnya selama 10 jam per havinya, Waktu produkst dan keuntungan per unit barang diberikan dalam tabel sebagai berikut24 Bab 2 = Program Linier: Metode Grafik Produk ‘Menit per unit Keuntungan eee —___— Mesin 1 Mesin 2 Mesin 3 A 10 6 8 $2 B 5 20 15 $3 tt) a. Tentukan model program liniernya b. Dengan metode grafik tentukan berapa masing-masing produk harus dibuat sehingga keuntungan maksimum 2. ‘Tentukan daerah feasibel secara grafis dari pertidaksamaan berikut ini x+ 484 4x, + 3x, $12 x+y 21 x4 <6 xp 20 Manakah yang termasuk batasan redundan? Reduksi sistem sehingga batasan menjadi lebih sederhana. 3. Perhatikan persoalan berikut ini: Maksimumkan: Z = 5x, + 6x, Batasan-batasan: m4 — 2m 22 “2x, + 3x, 22 xy % tidak dibatasi Tentukan solusi optimal dengan metode grafik. 4, Tentukan pemecahan optimal dengan metode grafik untuk model program berikut ini: Minimumban: Z = 25x, + 30%, Batasan-batasan: 4x, + Tx 1 8x, + 5x, 2 3 6x, + 9x, 2-2 xy 20