Makalah Riset Operasi Program Linier [PDF]

Citation preview

Makalah Riset Operasi (Program Linear) 27 March 2018 Nur Meutia Annisa   BAB 1 PENDAHULUAN  



LATAR BELAKANG



Pada mulanya Riset Operasi tidak terlepas dari perang dunia ke II. karena terjadinya perang maka terjadi sebuah kebutuhan, iyalah bagaimana cara mengalokasikan sumber sumber daya yang sangat terbatas kepada berbagai elemen operasi militer dalam sebuah kegiatan secara efektif , Karena itulah pemimpin pemimpin perang meminta saran kepada ahli dalam bidang sains untuk melakukan pendekatan ilmiah untuk menghadapi permasalahan dan melakukan upaya pemecahannya secara strategis. Program linier (linear programming) adalah merupakan metode matematik dalam mengalokasikan sumber daya yang langka atau terbatas untuk mencapai tujuan tunggal seperti memaksimumkan keuntungan atau meminimumkan biaya (Taha, 1993). Sumber daya tersebut dapat berupa sumber daya fisik seperti uang, tenaga ahli, material (bahan dan mesin) ataupun bukan fisik. Menurut Ayu (1996), pemrograman linearr berasal dari kata pemrograman dan linear. Pemrograman disini mempunyai arti kata perencanaan, dan linier ini berarti bahwa fungsi-fungsi yang digunakan merupakan fungsi linier. Secara umum arti dari pemrograman linier adalah suatu teknik perencanaan yang bersifat analisis yang analisis-analisisnya memakai model matematika, dengan tujuan menemukan beberapa kombinasi alternatif pemecahan masalah kemudian dipilih yang terbaik di antaranya dalam rangka menyusun strategi dan langkah-langkah kebijaksanaan lebih lanjut tentang alokasi sumber daya dan dana yang terbatas guna mencapai tujuan dan sasaran yang di inginkan secara optimal.   



RUMUSAN MASALAH



1. 2. 3. 4. 5.



Apa yang dimaksud dengan Program Linear? Bagaimana Formulasi Program Linear? Apa saja metode-metode Pemrograman Linear? Bagaimana contoh-contoh soal Program Linear



6. 7. 8. 9.                                        



o TUJUAN Mengetahui pengertian Program Linear Memahami formulasi pada Program Linear Mengetahui metode-metode Program Linear Memahami contoh-contoh soal Program Linear



BAB 2 PEMBAHASAN 2.1     PROGRAM LINEAR Pada tahun 1947, seorang ahli matematika dari AS yang bernama George B. Dantzig menemukan suatu cara untuk memecahkan persoalan-persoalan linear programming. Cara pemecahan ini dinamakan ” Simplex Method”, yang diuraikan dalam bukunya ”LINEAR PROGRAMMING AND EXTENTION”. Selanjutnya teori ini berkembang pesat sekali terutama dibidang kemiliteran yang menyangkut optimisasi dalam strategi perang dan di bidang-bidang lainnya. Setiap perusahaan atau organisasi memiliki keterbatasan atas sumber dayanya, baik keterbatasan dalam jumlah bahan baku, mesin dan peralatan, ruang tenaga kerja, jam kerja, maupun modal. Dengan keterbatasan ini, perusahaan perlu merencanakan strategi yang dapat mengoptimalkan hasil yang ingin dicapai, baik itu berupa keuntungan maksimal atau biaya minimal. Berbagai cara lain telah ditemukan untuk tujuan itu, salah satu diantaranya pemrograman linear (Eddy, 2008). Pemrograman linear (linear proramming) adalah teknik pengambilan keputusan untuk memecahkan masalah mengalokasikan sumber daya yang terbatas diantara berbagai kepentingan seoptimal mungkin. Pemrograman linear merupakan salah satu metode dalam riset operasi yang memungkinkan para manajer mengambil keputusan dengan menggunakan pendekatan analisis kuantitatif. Teknik ini telah diterapkan secara luas pada berbagai persoalan dalam perusahaan, untuk menyelesaikan masalah yang berkaitan dengan penugasan karyawan, penggunaan mesin, distribusi, dan pengangkutan, penentuan kapasitas produk, ataupun dalam penentuan portofolio investasi. Program linier banyak digunakan untuk menyelesaikan masalah optimal didalam industri, perbankan, pendidikan, dan masalah-masalah lain yang dapat dinyatakan dalam bentuk linier.   



FORMULASI PROGRAM LINEAR



Masalah keputusan yang sering dihadapi analisis adalah alokasi optimum sumber daya. Sumber daya dapat berupa uang, tenaga kerja, bahan mentah, kapasitas mesin, waktu, ruangan atau teknologi. Tugas analisis adalah mencapai hasil terbaik dengan keterbatasan sumber daya itu. Setelah masalah diidentifikasikan, tujuan ditetapkam, langkah selanjutnya adalah formulasi model matematika. Formulasi model matematika ada 3 tahap : 1. Tentukan variabel yang tidak diketahui dan dinyatakan dalam simbol. 2. Membentuk fungsi tujuan yang ditunjukkan sebagai suatu hubungan linier dari variabel keputusan. 3. Menentukan semua kendala masalah tersebut dan mengekspresikannya dalam persamaan atau pertidaksamaan.



Contoh kasus yang diselesaikan : 1. Seorang pengrajin menghasilkan satu tipe meja dan satu tipe kursi. Proses yang dikerjakan hanya merakit meja dan kursi. Dibutuhkan waktu 2 jam untuk merakit 1 unit meja dan 30 menit untuk merakit 1 unit kursi. Perakitan dilakukan oleh 4 orang karyawan dengan waktu kerja 8 jam perhari. Pelanggan pada umumnya membeli paling banyak 4 kursi untuk 1 meja. Oleh karena itu pengrajin harus memproduksi kursi paling banyak empat kali jumlah meja. Harga jual per unit meja adalah Rp 1,2 juta dan per unit kursi adalah Rp 500 ribu. Formulasikan kasus tersebut ke dalam model matematiknya ! Jawaban: 1. Langkah Pertama Mengidentifikasi tujuan, alternatif keputusan dan sumber daya yang membatasi. Berdasarkan informasi yang diberikan pada soal, tujuan yang ingin dicapai adalah memaksimumkan pendapatan. Alternatif keputusan adalah jumlah meja dan kursi yang akan diproduksi. Sumber daya yang membatasi  adalah waktu kerja karyawan dan perbandingan jumlah kursi dan meja yang harus diproduksi (pangsa pasar ) 2. Langkah Kedua Memeriksa sifat proporsionalitas, additivitas, divisibilitas dan kepastian. Informasi di atas tidak menunjukkan adanya pemberian diskon, sehingga harga jual per meja maupun kursi akan sama meskipun jumlah yang dibeli semakin banyak. Hal ini mengisyaratkan bahwa total  pendapatan yang diperoleh pengrajin proposional terhadap jumlah produk yang terjual. Penggunaan sumber daya yang membatasi , dalam hal ini waktu kerja karyawan dan pangsa pasar juga proporsional terhadap jumlah meja dan kursi yang diproduksi. Dengan  demikian dapat dinyatakan sifat proporsionalitas dipenuhi. Total pendapatan pengrajin merupakan jumlah pendapatan dari keseluruhan meja dan kursi yang terjual. Penggunaan sumber daya ( waktu kerja karyawan dan pangsa pasar) merupakan penjumlahan waktu yang digunakan untuk memproduksi meja dan kursi. Maka dapat dinyatakan juga sifat additivitas dipenuhi. Sifat divisibilitas dan kepastian juga dipenuhi. 3. Langkah Ketiga Ada dua variabel keputusan dan dua sumber daya yang membatasi. Fungsi tujuan merupakan maksimisasi, karena semakin besar pendapatan akan semakin disukai oleh pengrajin. Fungsi kendala pertama (batasan waktu) menggunakan pertidaksamaan ≤, karena waktu yang tersedia dapat digunakan sepenuhnya atau tidak, tapi tidak mungkin melebihi waktu yang ada. Fungsi kendala yang kedua bisa menggunakan ≤ atau ≥ tergantung dari pendefinisianvariabelnya Definisikan Variabelnya: x₁ = jumlah meja yang akan diproduksi



x₂ = jumlah kursi yang akan diproduksi Fungsi tujuan : Maksimumkan z = 1.2 x₁ + 0.5 x₂ Kendala : 2x₁ + 0.5 x₂≤ 32 x₁/x₂ ≥ ¼ atau 4x₁≥ x₂ atau 4x₁– x₂ ≥ 0 x₁ , x₂ ≥ 0   2.3     METODE-METODE PROGRAM LINEAR 1. METODE GRAFIK Metode grafik hanya bisa digunakan untuk menyelesaikan permasalahan dimana hanya terdapat dua variabel keputusan. Untuk menyelesaikan permasalahan tersebut, langkah pertama yang harus dilakukan adalah memformulasikan permasalahan yang ada ke dalam bentuk Linear Programming (LP). Langkah – langkah penyelesaian dengan metode grafik: 1. Buatlah model matematika / kendala 2. Tentukan fungsi sasaran (Z). 3. Menyelesaikan fungsi pertidaksamaan :    



Jadikan setiap kendala menjadi bentuk persamaan, Buat grafik untuk setiap kendala dan kemudian tentukan daerah penyelesaian atau HP, Setelah grafik dibuat, kemudian tentukan himpunan penyelesaian (HP). Setelah itu, kita menentukan titik – titik terluar yang terdapat didalam grafik tersebut. Setelah titik – titik terluar ditentukan, Uji titik – titik terluarnya untuk menentukan nilai maksimumnya.



1. METODE SIMPLEKS Digunakan untuk proses dengan jumlah variabel lebih dari 2. Tahapan dalam metode simplex ini lebih kompleks dibandingkan dengan metode grafik. Tahapan dalam penyelesaian optimasi dari Linear Programming ini adalah sebagai berikut : 1. 2. 3. 4. 5. 6.



Menentukan fungsi tujuan Mengidentifikasi batasan Menggambarkan dalam bentuk grafik / sistem koordinat Menentukan daerah kemungkinan (feasible) Mencari titik yang paling menguntungkan METODE ALJABAR



Pemecahan persoalan PL dengan metode aljabar adalah pemecahan persoalan dengan cara substitusi antarpersamaan linear pada fungsi pembatas dan fungsi tujuan. Prinsip yang digunakan ialah mencari seluruh kemungkinan pemecahan dasar feasible (layak), kemudian pilih salah satu yang memberikan nilai objektif optimal, yaitu paling besar (maksimum) atau paling kecil (minimum). Pemecahan persoalan Program Linear dengan metode aljabar ini dibagi 3 (tiga) kasus, yaitu: 1. Kasus Maksimisasi. kasus pemecahan persoalan PL yang bertujuan mencari seluruh kemungkinan pemecahan yang memberikan nilai objektif maksimum. 1. Kasus Minimasi Kasus pemecahan masalah program linear yang bertujuan seluruh kemungkinan pemecahan yang memberikan nilai objektif minimum. 1. Kasus-kasus khusus Beberapa kasus khusus selain kasus maksimisasi dan minimisasi adalah kasus solusi optimum ganda dan tidak memiliki solusi yang layak.     2.4     CONTOH-CONTOH SOAL PROGRAM LINEAR 1. PT LAQUNATEKSTIL memiliki sebuah pabrik yang akan memproduksi 2 jenis produk, yaitu kain sutera dan kain wol. Untuk memproduksi kedua produk diperlukan bahan baku benang sutera, bahan baku benang wol dan tenaga kerja. Maksimum penyediaan benang sutera adalah 60 kg per hari, benang wol 30 kg per hari dan tenaga kerja 40 jam per hari. Kebutuhan setiap unit produk akan bahan baku dan jam tenaga kerja dapat dilihat dalam tabel berikut: Jenis Bahan Baku dan Tenaga Kerja Benang Sutra Benang Wol Tenaga Kerja  



Bahan Baku & Jam Tenaga Kerja Kain Sutra Kain Wol 2 3 – 2 2 1



Maksimum Penyediaan 60 kg 30 kg 40 kg



LANGKAH-LANGKAH: 1) Tentukan variabel X1=kain sutera X2=kain wol 2) Fungsi tujuan Zmax= 40X1 + 30X2 3) Fungsi kendala / batasan 1. 2X1 + 3X2 60 (benang sutera) 2. 2X2 30 (benang wol) 3. 2X1 + X2 40 (tenaga kerja) 4) Membuat grafik 1. 2X1 + 3 X 2=60 X1=0, X2 =60/3 = 20 X2=0, X1= 60/2 = 30 2. 2X2 30 X2=15 3. 2X1 + X2 40 X1=0, X2 = 40 X2=0, X1= 40/2 = 20 Cara mendapatkan solusi optimal: 1. Dengan mencari nilai Z setiap titik ekstrim. Titik A X1=0, X2=0 masukkan nilai X1 dan X2 ke Z Z = 40 . 0 + 30 . 0 = 0 Titik B X1=20, X2=0 masukkan nilai X1 dan X2 ke Z Z = 40 . 20 + 30 . 0 = 800 Titik C Mencari titik potong (1) dan (3) 2X1 + 3X2 = 60 2X1 + X2 = 40 2X2=20  X2=10 Masukkan X2 ke kendala (1) 2X1 + 3X2 = 60 2X1 + 3 . 10 = 60 2X1 + 30 = 60 2X1 = 30  X1 = 15 masukkan nilai X1 dan X2 ke Z Z = 40X1 + 30X2 = 40 . 15 + 30 . 10 = 600 + 300 = 900 (optimal) Titik D 2X2 = 30 X2 = 15



masukkan X2 ke kendala (1) 2X1 + 3 . 15 = 60 2X1 + 45 = 60 2X1 = 15  X1 = 7,5      masukkan nilai X1 dan X2 ke Z Z = 40 . 7,5 + 30 . 15 = 300 + 450 = 750 Titik E X2 = 15 X1 = 0      masukkan nilai X1 dan X2 ke Z Z = 40 . 0 + 30 .15 = 450 Untuk memperoleh keuntungan optimal, maka X1 = 15 dan X2 = 10 dengan keuntungan sebesar Rp 900 juta. 2. Budi baru saja membuka sebuah took sepeda didepan rumahnya. Untuk persediaan budi bermaksud membeli  50 sebuah sepeda. Dan sepeda yang ia inginkan ada 3 jenis, yakni sepeda biasa, sepeda balap dan sepeda gunung. Harga ketiga sepeda tersebut masingmasing adalah 80.000/sepeda, 120.000/sepeda dan 100.000/sepeda. Budi merencanakan untuk tidak mengeluarkan uang lebih dari Rp. 5.400.000 dengan mengharapkan keuntungan Rp.12.000 dari setiap sepeda biasanya Rp.20.000 dari setiap sepeda balap, dan Rp.14.000 dari sepeda gunung. Berapakah masing-masing sepeda yang harus dibeli budi untuk persediaan ditokonya agar mendapat keuntungan optimal? PENYELESAIAN: 



Variabel :



Sepeda biasa = X1 Sepeda balap = X2 Sepeda gunung = X3 



Fungsi Tujuan :



Zmax = 12.000X1 + 20.000X2 + 14.000X3 



Fungsi Kendala :



X1 + X2 +X3  ≤  50 80.000X1 + 120.000X2 + 100.000X3 ≤ 5.400.000 X1, X2, X3 ≥ 0  







Bentuk Standard :



Zmax = 12X1 + 20X2 + 14X3 Z – 12X1 – 20X2 – 14X3 = 0 S/t    X1  +  X2  +  X3  +  X4       =  50 80X1 + 120 X2 +100X3 + X5     =  3400 Proses Tabulasi Simplex: Basis X3 X4 Z



X1 X2 X3 X4 X5 RK Ratio 1 1 1 1 0 160 50 80 120 100 0 1 5400 45 -12 -20 -14 0 0 0



  X2 baru : 80/120           120/120           100/100        0/120      1/120           5400/120 0,67                    1                     0,83             0           0,008                45   X3 baru :                                                          Z baru : -1 x   0,67 + 1   = 0,33                                    20 x    0,67  +  (-12)  =  1,4 -1 x     1    + 1   =  0                                        20 x    1       +  (-20)  =   0 -1 x   0,83 + 1   = 0,17                                    20 x  0,83    +  (-14)  =   2,6 -1 x   0      + 1   = 1                                         20 x   0        +   0       =   0 -1 x 0,008 + 0   = -0,008                                20 x   0,008 +   0       =   0,16 -1 x    45   + 50  = 5                                       20 x    45     +   0       =   900   Hasil Interasi I : Basis



X1



X2



X3



X4



X5



RK



X3 X1 Z



0,33 0,67 -1,4



0 1 0



0,17 0,83 2,6



1 0 0



-0,008 5 -0,008 45 0,16 900



  Karena semua komponen pada Z ≥ 0, maka Solusi sudah optimal. Maka diperoleh X1 = 0,    X2 = 45 ,   dan    X3 = 5 Zmax = 12.000 X1 + 20.000 X2 + 14.000 X3 = 12.000(0) + 20.000(45) + 14.000 (5) = 0   + 900.000   + 70.000 = 970.000 Untuk persediaan ditokonya, budi harus membeli sepeda balap sebanyak 45 buah dan sepeda gunung sebanyak 5 buah dengan memperoleh keuntungan sebesar R.p 970.000.                         BAB 3



PENUTUP  3.1     Kesimpulan Pemrograman linear (linear proramming) adalah teknik pengambilan keputusan untuk memecahkan masalah mengalokasikan sumber daya yang terbatas diantara berbagai kepentingan seoptimal mungkin. Pemrograman linear merupakan salah satu metode dalam riset operasi yang memungkinkan para manajer mengambil keputusan dengan menggunakan pendekatan analisis kuantitatif. Teknik ini telah diterapkan secara luas pada berbagai persoalan dalam perusahaan, untuk menyelesaikan masalah yang berkaitan dengan penugasan karyawan, penggunaan mesin, distribusi, dan pengangkutan, penentuan kapasitas produk, ataupun dalam penentuan portofolio investasi. Program linier banyak digunakan untuk menyelesaikan masalah optimal didalam industri, perbankan, pendidikan, dan masalah-masalah lain yang dapat dinyatakan dalam bentuk linier.   3.2     Saran Semoga penulis dan pembaca dapat mengetahui apa pengertian Program Linear dan mengetahui contoh-contoh serta penyelesaian soal-soal pada Program Linear dengan berbagai metode yang ada.     DAFTAR PUSTAKA



http://noviahasdyna07.blogspot.co.id/2012/09/riset-operasional-2-linear-programming.html http://akhlords.blogspot.co.id/2013/12/riset-operasi-contoh-soal.html https://sarahbaniariyandini.wordpress.com/2014/01/14/program-linier/ http://zonakuliahku.blogspot.co.id/2016/02/pemrograman-linear.html   Advertisements Report this ad Report this a d



Riset Operasi - Program Linear Masalah Maksimisasi Program Linear, Riset, Riset Operasi PROGRAM LINEAR Program linear adalah salah satu model matematika yang digunakan untuk menyelesaikan masalah optimisasi, yaitu memaksimumkan atau meminimumkan fungsi tujuan yang bergantung pada sejumlah variabel input. Hal terpenting yang perlu kita lakukan adalah mencari tahu tujuan penyelesaian masalah dan apa penyebab masalah tersebut. Dua macam fungsi Program Linear: Fungsi tujuan : mengarahkan analisa untuk mendeteksi tujuan perumusan masalah Fungsi kendala : untuk mengetahui sumber daya yang tersedia dan permintaan atas sumber daya tersebut.



Masalah Maksimisasi Maksimisasi dapat berupa memaksimalkan keuntungan atau hasil. Contoh: PT LAQUNATEKSTIL memiliki sebuah pabrik yang akan memproduksi 2 jenis produk, yaitu kain sutera dan kain wol. Untuk memproduksi kedua produk diperlukan bahan baku benang sutera, bahan baku benang wol dan tenaga kerja. Maksimum penyediaan benang sutera adalah 60 kg per hari, benang wol 30 kg per hari dan tenaga kerja 40 jam per hari. Kebutuhan setiap unit produk akan bahan baku dan jam tenaga kerja dapat dilihat dalam tabel berikut: Jenis bahan baku Kg bahan baku & Jam tenaga kerja Maksimum dan tenaga kerja Kain sutera Kain wol penyediaan Benang sutera 2 3 60 kg Benang wol - 2 30 kg Tenaga kerja 2 1 40 jam Kedua jenis produk memberikan keuntungan sebesar Rp 40 juta untuk kain sutera dan Rp 30 juta untuk kain wol. Masalahnya adalah bagaimana menentukan jumlah unit setiap jenis produk yang akan diproduksi setiap hari agar keuntungan yang diperoleh bisa maksimal.



Langkah-langkah: 1) Tentukan variabel X1=kain sutera X2=kain wol 2) Fungsi tujuan Zmax= 40X1 + 30X2 3) Fungsi kendala / batasan 1. 2X1 + 3X2 60 (benang sutera) 2. 2X2 30 (benang wol) 3. 2X1 + X2 40 (tenaga kerja) 4) Membuat grafik 1. 2X1 + 3 X 2=60 X1=0, X2 =60/3 = 20 X2=0, X1= 60/2 = 30 2. 2X2 30 X2=15 3. 2X1 + X2 40 X1=0, X2 = 40 X2=0, X1= 40/2 = 20 Cara mendapatkan solusi optimal: 1. Dengan mencari nilai Z setiap titik ekstrim. Titik A X1=0, X2=0 masukkan nilai X1 dan X2 ke Z Z = 40 . 0 + 30 . 0 = 0 Titik B X1=20, X2=0 masukkan nilai X1 dan X2 ke Z Z = 40 . 20 + 30 . 0 = 800 Titik C Mencari titik potong (1) dan (3) 2X1 + 3X2 = 60 2X1 + X2 = 40 2X2=20 X2=10 Masukkan X2 ke kendala (1) 2X1 + 3X2 = 60 2X1 + 3 . 10 = 60 2X1 + 30 = 60 2X1 = 30 X1 = 15 masukkan nilai X1 dan X2 ke Z 40X1 + 30X2 = 40 . 15 + 30 . 10 = 600 + 300 = 900 (optimal) Titik D 2X2 = 30 X2 = 15



masukkan X2 ke kendala (1) 2X1 + 3 . 15 = 60 2X1 + 45 = 60 2X1 = 15 X1 = 7,5 masukkan nilai X1 dan X2 ke Z Z = 40 . 7,5 + 30 . 15 = 300 + 450 = 750 Titik E X2 = 15 X1 = 0 masukkan nilai X1 dan X2 ke Z Z = 40 . 0 + 30 .15 = 450 Kesimpulan : untuk memperoleh keuntungan optimal, maka X1 = 15 dan X2 = 10 dengan keuntungan sebesar Rp 900 juta. 2. Dengan cara menggeser garis fungsi tujuan. Solusi optimal akan tercapai pada saat garis fungsi tujuan menyinggung daerah feasible (daerah yang diliputi oleh semua kendala) yang terjauh dari titik origin. Pada gambar, solusi optimal tercapai pada titik C yaitu persilangan garis kendala (1) dan (3). Titik C Mencari titik potong (1) dan (3) 2X1 + 3X2 = 60 2X1 + X2 = 40 2X2=20 X2=10 Masukkan X2 ke kendala (1) 2X1 + 3X2 = 60 2X1 + 3 . 10 = 60 2X1 + 30 = 60 2X1 = 30 X1 = 15 masukkan nilai X1 dan X2 ke Z 40X1 + 30X2 = 40 . 15 + 30 . 10 = 600 + 300 = 900