P2 - Linear Programming [PDF]

Citation preview

Linier Programming



LINEAR PROGRAMMING Model umum yang digunakan dalam pemecahan masalah pengalokasian sumbersumber yang terbatas secara optimal Masalah timbul bila seseorang diharuskan untuk memilih/menentukan tingkat setiap kegiatan yang akan dilakukannya, dimana masing-masing kegiatan membutuhkan sumber sama sedangkan jumlah terbatas



Dalam model LP dikenal 2 (dua) macam “fungsi”, 1. Fungsi tujuan  menggambarkan tujuan sasaran di dalam permasalahan LP yang berkaitan dengan pengaturan secara optimal sumberdaya-sumberdaya, untuk memperoleh keuntungan maksimal atau biaya minimal. Dinyatakan sebagai Z. 2. Fungsi batasan (fungsi kendala)  bentuk penyajian secara matematis batasan-batasan kapasitas yang tersedia yang akan dialokasikan secara optimal ke berbagai kegiatan.



Formulasi Model 



Komponen Model : 1. Variabel Keputusan 2. Fungsi Tujuan 3. Batasan Model



4



Variabel Keputusan 



Merupakan simbol matematika yang menggambarkan tingkatan aktifitas perusahaan. Contoh : perusahaan elektronik menginginkan untuk memproduksi x1 radio, x2 bakaran roti, dan x3 jam, dimana x1, x2 dan x3 adalah lambang yang menunjukkan jumlah variabel setiap item yang tidak diketahui. Nilai akhir dari x1, x2, x3, merupakan keputusan (misal x1 = 10 radio adalah keputusan perusahaan untuk memproduksi radio). 5



Fungsi Tujuan 







Merupakan hubungan matematika linier yang menjelaskan tujuan perusahaan dalam terminologi variabel keputusan. Fungsi tujuan selalu mempunyai salah satu target : memaksimumkan atau meminimumkan suatu nilai (memaksimumkan laba atau meminimumkan biaya produksi)



6



Batasan Model 











Menunjukkan keterbatasan perusahaan karena lingkungan operasi perusahaan. Dapat berupa keterbatasan sumber daya atau pedoman. Contoh : hanya 40 jam tenaga kerja tersedia, untuk membuat radio selama proses produksi.



7



Simbol yang Umum Digunakan Z = Nilai dari semua standar performansi xj = Tingkat aktivitas j (untuk j = 1, 2, …, n) cj = Penambahan terhadap Z yang diakibatkan oleh peningkatan tiap unit di tingkat aktivitas j bi = Jumlah sumber daya i yang tersedia untuk aktivitas (untuk i = 1, 2, …, m) aij = Jumlah sumber daya i yang dipakai oleh tiap unit aktivitas j 8



Data yang Diperlukan Penggunaan Sumber Daya per Unit Aktivitas Sumber Daya



1 2 : m Kontribusi terhadap Z per unit aktivitas



Aktivitas



1 a11 a21 … am1 c1



2 a12 a22 … am2 c2



… … … … … …



n a1n a2n … amn cn



Jumlah Sumber Daya yang Tersedia



b1 b2 : bm



9



Bentuk Standar n



n



max Z   c j x j



min Z   c j x j



ST :



ST :



j 1



n



a x j 1



ij



j



 bi ; i  1,2,..., m



x j  0; j  1,2,..., n



j 1



n



a x j 1



ij



j



 bi ; i  1,2,..., m



x j  0; j  1,2,..., n



10



Assumptions of Linear Programming • Proportionality naik turunnya nilai Z dan penggunaan sumber atau fasilitas yang tersedia akan berubah secara sebanding (proportional) dengan perubahan tingkat kegiatan.



11



Assumptions of Linear Programming • Additivity nilai tujuan tiap kegiatan tidak saling memperngaruhi, atau kenaikan dari nilai tujuan (Z) yang diakibatkan oleh kenaikan suatu kegiatan dapat ditambahkan tanpa mempengaruhi bagian nilai Z yang diperoleh dari kegiatan lain.



12



Assumptions of Linear Programming • Additivity Misal : Z = 3X1 + 5X2 Dimana X1 = 10; X2 = 2; Sehingga Z = 30 + 10 = 40  Andaikata X1 bertambah 1 unit, maka nilai Z menjadi 40 + 3 = 43. Jadi, nilai 3 karena kenaikan X1 dapat langsung ditambahkan pada nilai Z mula-mula tanpa mengurangi bagian Z yang diperoleh dari kegiatan 2 (X2).  Dengan kata lain, tidak ada korelasi antara X1 dan X2. 13



Assumptions of Linear Programming Divisibility • Asumsi ini menyatakan bahwa keluaran (output) yang dihasilkan oleh setiap kegiatan dapat berupa bilangan pecahan. Demikian pula dengan nilai Z yang dihasilkan. • Misal : X1 = 6,5; Z = 1.000,75 14



Assumptions of Linear Programming • Certainty/deterministik – Nilai yang diberikan oleh tiap parameter dari model pemrograman linier diasumsikan sebagai konstanta yang diketahui yaitu nilai aij,bi, cj



15



Contoh 1. Perusahaan sepatu Perusahaan sepatu membuat 2 macam sepatu. Yang pertama merek I1, dgn sol karet, dan merek I2 dgn sol kulit. Diperlukan 3 macam mesin. Mesin 1 membuat sol karet, mesin 2 membuat sol kulit, dan mesin 3 membuat bagian atas sepatu dan melakukan assembling bagian atas dengan sol. Setiap lusin sepatu merek I1 mula-mula dikerjakan di mesin 1 selama 2 jam, kemudian tanpa melalui mesin 2 terus dikerjakan di mesin 3 selama 6 jam. Sedang untuk sepatu merek I2 tidak diproses di mesin 1, tetapi pertama kali dikerjakan di mesin 2 selama 3 jam kemudian di mesin 3 selama 5 jam. Jam kerja maksimum setiap hari mesin 1 adalah 8 jam, mesin 2 adalah 15 jam, dan mesin 3 adalah 30 jam. Sumbangan terhadap laba setiap lusin sepatu merek I1 = Rp 30.000,00 sedang merek I2 = Rp 50.000,00. Masalahnya adalah menentukan berapa lusin sebaiknya sepatu merek I1 dan merek I2 yang dibuat agar bisa memaksimumkan laba.



Bentuk Tabel



Mesin



I1 (X1)



I2 (X2)



1 2 3



2 0 6



0 3 5



3



5



Merek



Sumbangan laba (dlm puluhan ribu)



Kapasitas Maksimum perhari (jam) 8 15 30



Bentuk Matematis • Maksimumkan Z = 3X1 + 5X2 • Batasan (constrain) (1) 2X1  8 (kap max/hari mesin 1) (2) 3X2  15 (kap max/hari mesin 2) (3) 6X1 + 5X2  30 (kap max/hari mesin 3) X1  0, X2  0



Fungsi batasan pertama (2 X1  8) X2



2X1 = 8 2X1  8 dan X1  0, X2  0



0



4



X1



Gambar di atas merupakan bagian yang memenuhi batasan-batasan: X1  0, X2  0 dan 2X1  8



Fungsi batasan (2 X1  8); 3X2  15; 6X1 + 5X2  30; X1  0 dan X2  0 X2



2X1 = 8



6X1 + 5X2 = 30



6 5D



C



C



3X2 = 15



Daerah feasible



B 0



A 4



5



X1



MENCARI KOMBINASI YANG OPTIMUM Dengan membandingkan nilai Z pada tiap-tiap alternatif Z = 3X1 + 5X2 OPTIMUM Z=27,5; x1=5/6; x2=5 X2



2X1 = 8



6X1 + 5X2 = 30



Titik C: X2 = 5. Substitusikan batasan (3), maka 6X1 + 5(5) = 30. Jadi nilai X1 = (30 –25)/6 = 5/6. Nilai Z = 3(5/6) + 5(5) = 27,5



Titik D: Pada titik ini nilai X2 = 5; X1 = 0 Nilai Z = 3(0) + 5(5) = 25



D



6



5



C



3X2 = 15



Titik A:



Daerah feasible



Titik B: X1 = 4. Substitusikan batasan (3), maka 6(4) + 5X2 = 30. Jadi nilai X2 = (30 –24)/5 = 6/5. Nilai Z = 3(4) + 5(6/5) =18



Pada titik ini nilai X1 = 4; X2 = 0 Nilai Z = 3(4) + 0 = 12



B 0



A 4



5



X1



Formulasi model pada LINGO



Penyelesaian dengan bantuan LINGO Klik LINGO/Solve



Solusi Untuk mendapatkan keuntungan yang maksimum, maka perusahaan membuat sepatu” Merek I1 sebanyak 5/6 lusin Merek I2 sebanyak 5 lusin Memperoleh keuntungan sebesar 27,5 (dalam ribuan) Abaikan jumlah sepatu yang bilangan pecahan => soal hanya untuk contoh Penyelesaian bisa dengan integer linear programming => materi yang akan datang



CONTOH 2. Perusahaan Mangkok dan cangkir Perusahaan Barang Maju Bersama memproduksi 2 produk setiap hari yaitu mangkok dan cangkir. Perusahaan mempunyai 2 sumber daya yang terbatas jumlahnya yang digunakan untuk memproduksi produk-produk tersebut seperti tanah liat dan tenaga kerja. Dengan keterbatasan sumber daya, perusahaan ingin mengetahui berapa banyak mangkok dan gelas yang akan diproduksi tiap hari dalam rangka memaksimumkan laba. Kedua produk mempunyai kebutuhan sumber daya untuk produksi serta laba per item adalah sebagai berikut: 25



Kebutuhan Sumber Daya



Produk $ / Tenaga Tanah Liat unit Kerja (Jam) (Pon)



Laba



Mangkok



1



4



4



Cangkir



2



3



5



Tersedia 40 jam tenaga dan 120 pon tanah liat setiap hari untuk produksi. Masalah ini akan dirumuskan sebagai model program linier dengan mendefinisikan terpisah setiap komponen model dan menggabungkan komponen-komponen tersebut dalam satu model. 26



Variabel Keputusan 







Keputusan yang dihadapi manajemen dalam masalah ini adalah berapa banyak mangkok dan cangkir yang harus diproduksi tiap hari. Jumlah yang diproduksi untuk tiap jenis produk adalah sebagai berikut : X1 : jumlah mangkok yang diproduksi X2 : jumlah cangkir yang diproduksi



27



Fungsi Tujuan 







Tujuan perusahaan adalah untuk memaksimumkan total laba. Laba perusahaan adalah jumlah dari laba setiap mangkok dan cangkir. memaksimumkan Z = $ 4 x1+ $ 5 x2 dimana Z = total laba tiap hari $4x1 = laba dari mangkok $5x2 = laba dari cangkir 28



Batasan Model-1 







Dalam masalah berikut terdapat 2 sumber daya digunakan : tenaga kerja dan tanah liat BATASAN TENAGA KERJA : Untuk setiap mangkok yang diproduksi memerlukan 1 (satu) jam tenaga kerja dan untuk setiap cangkir diperlukan 2 jam tenaga kerja …….. 1x1 + 2x2  Akan tetapi jumlah tenaga kerja sebesar 1x1 + 2x2 dibatasi sampai dengan 40 jam perhari, maka batasan tenaga kerja menjadi: 1x1 + 2x2 ≤ 40 jam 



29



Batasan Model-2 



BATASAN TANAH LIAT : 











Setiap mangkok memerlukan 4 pon tanah liat. Jumlah tanah liat yang digunakan tiap hari untuk memproduksi mangkok adalah 4 x1 pon Setiap cangkir memerlukan 3 pon tanah liat. Jumlah tanah liat yang digunakan tiap hari adalah 3 x2. Jika diasumsikan bahwa tanah liat yang tersedia tiap hari adalah 120 pon, batasan bahan baku dapat dirumuskan sebagai berikut 4 x1 + 3 x2 ≤ 120 pon 30



Batasan Model-3 



Batasan akhir adalah bahwa jumlah mangkok dan cangkir yang diproduksi bernilai nihil atau positif x1 ≥ 0, x2 ≥ 0



31



Model Program Linier :  



Memaksimumkan Z = $ 4 x1 + $ 5 x2 Terbatas pada 1 x1 + 2 x2 ≤ 40 4 x1 + 3 x2 ≤ 120 x 1, x 2 ≥ 0



32



Formulasi model pada LINGO



Penyelesaian dengan bantuan LINGO Klik LINGO/Solve



Soal 3. • Suatu pabrik menghasilkan 2 jenis produk (A,B) yang diolah dengan tiga mesin (I, II, III). Tiap unit produk A membutuhkan waktu pengolahan 1 menit di mesin I, 3 menit di mesin II, dan 1 menit di mesin III. Sedangkan tiap unit produk B membutuhkan waktu pengolahan 2 menit di mesin I, 1 menit di mesin II, dan 1 menit di mesin III. Kapasitas operasi maksimum mesin 1 = 1600 menit, mesin II = 2400 menit, dan mesin III = 1000 menit. Jika diketahui laba per unit produk A = 1000 dan produks B = 1500, maka berapa kombinasi produk A dan B yang dapat diproduksi agar tercapai laba maksimum ?



Soal 4. Sebuah perusahaan manufaktur memproduksi 4 jenis produk yang dibuat dari 3 jenis bahan baku yang berbeda. Penggunaan masing-masing jenis bahan baku untuk masingmasing jenis produk adalah: Bahan Baku (kg)



1



2



3



Produk A



2



3,5



4



Produk B



4



2



1



Produk C



2,5



2



3



Produk D



1



3,5



2,5



• Selanjutnya untuk memproduksi setiap unit: Produk A diperlukan 5 jam orang (man-hours) Produk B diperlukan 4 jam orang (man-hours) Produk C diperlukan 3 jam orang (man-hours) Produk D diperlukan 6 jam orang (man-hours) • Bahan baku yang tersedia : Bahan baku 1 = 200 kg Bahan baku 2 = 300 kg Bahan baku 3 = 400 kg • Jam orang yang tersedia selama periode produksi adalah 300 jam. Jika keuntungan dari setiap unit produk A, B, C, D adalah Rp7.000; Rp10.000; Rp5.000; Rp6.000. • Formulasikan permasalahan diatas ke dalam model Program Linier jika diharapkan keuntungan maksimum pada periode tersebut