Kelompok 1 - Materi Linier Programming (Riset Operasi) [PDF]

Citation preview

RISET OPERASI



“LINIER PROGRAMMING” Kelompok 1



LINIER PROGRAMMING Kelompok 1, Anggota



Pembahasan :



◦ Dhea Nabila Tasya ( 20191112009 )



◦ Pengertian program linear (linear programming) ?



◦ Muhdholifah



( 20191112010 )



◦ Amanat Solikah



( 20191112022 )



◦ formulasi model program linear (linear programming)? ◦ asumsi – asumsi daprogramsar linear (linear programming) ? ◦ menyelesaikan masalah program linear (linear programming) dengan metode grafik?



Pengertian Linier Programming ◦ Pemrograman linear merupakan metode matematik dalam mngalokasikan sumber daya yang terbatas untuk mencapai suatu tujuan seperti memaksimumkan keuntungan dan meminimumkan biaya. Tujuan dari penggunaan program linear (linear programming) adalah untuk menyusun suatu model yang dapat dipergunakan untuk membantu oengambilan keputusan dalam menentukan alokasi yang optimal dari sumber daya perusahaan ke berbagai alternative. ◦ T. Hani Handoko



Linear programming ialah suatu metode analitik paling terkenal dan yang merupakan suatu bagian pada kelompok teknik – teknik yang disebut dengan programisasi matematik. ◦ Zulian Yamit Linear programming ialah metode maupun teknis matematis yang digunakan untuk dapat membantu manajer dalam pengambilan keputusan. Ciri khusus dalam penggunaan metode matematis ini ialah berusaha untuk mendapatkan maksimisasi atau juga minimisasi.



Formulasi model program linear Model LP mempunyai tiga unsur utama, yaitu: 1. Variabel keputusan yaitu variabel persoalan yang akan mempengaruhi nilai tujuan yang hendak dicapai. Didalam proses pemodelan, penemuan variabel keputusan harus dilakukan terlebih dahulu sebelum merumuskan fungsi tujuan dan fungsi batasan (kendala-kendalanya). Misalnya dengan mengajukan pertanyaan: keputusan apa yang harus dibuat agar nilai fungsi tujuan menjadi maksimum atau minimum. 2. Fungsi tujuan yaitu fungsi yang menggambarkan tujuan dalam permasalahan LP yang berkaitan dengan pengaturan secara optimal sumber daya - sumber daya, untuk memperoleh keuntungan maksimal atau biaya minimum. Dengan simbol Z. Oleh karena itu hanya ada dua kemungkinan fungsi tujuan, yaitu ◦ Maksimimkan Z = f (X1, X2, ...Xn) ◦ Minimumkan Z = f (X1, X2, ...Xn) 3. Fungsi batasan (kendala) yaitu bentuk penyajian secara matematis batasan-batasan kapasitas yang tersedia yang akan dialokasikan secara optimal ke berbagai kegiatan.



Tabel data model program linier Fungsi tujuan : Maksimumkan/minimumkan: Z = σ C j .X j = C1X1 + C2X2 + ... + CnXn Dengan kendala atau batasan:



Atau: 1. a11X1 + a12X2 + ... + a1nXn



b1



2. a21X1 + a22X2 + ... + a2nXn



b2



m. am1X1 + am2X2 + ... + amnXn



bm



dan Xj ≥ 0 atau X1 ≥ 0, X2 ≥ 0,.......... Xn ≥ 0



◦ Batasan pertama artinya: jumlah hasil (barang/jasa) 1 yang dihasilkan oleh kegiatan 1 dikalikan dengan kebutuhan akan sumber 1 per satuan (berarti total alokasi 1 untuk kegiatan 1) ditambah dengan hasil kegiatan 2 dikalikan dengan kebutuhan tiap satuan keluaran 2 terhadap sumber 1 (dan seterusnya sampai dengan kegiatan ke-n) tidak akan melebihi atau sama dengan atau tidak boleh kurang dari jumlah (kapasitas) tersedianya sumber 1 (yang dinyatakan dengan b1). Hal ini berlaku untuk batasan-batasan lainnya sampai ke m. ◦ Fungsi-fungsi batasan dapat di kelompokkan menjadi 2 macam, yaitu: ◦ Fungsi batasan fungsional, adalah fungsi-fungsi batasan sebanyak m yaitu a11X1 + a12X2 + ... + a1nXn ◦ Fungsi batasan non negatif (non negative constraints) yaitu fungsi-fungsi batasan yang dinyatakan dengan Xi 0 ◦ Variabel Xj disebut sebagai variabel keputusan (decision variables) ◦ aij, bi, Cj, yaitu masukan-masukan input konstan, disebut sebagai parameter model.



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 : ◦ Tentukan variabel yang tidak diketahui dan dinyatakan dalam simbol. ◦ Membentuk fungsi tujuan yang ditunjukkan sebagai suatu hubungan linier dari variabel keputusan. ◦ Menentukan semua kendala masalah tersebut dan mengekspresikannya dalam persamaan atau pertidaksamaan.



Asumsi dasar program linear 1. Proportionality Pada asumsi ini menyatakan bahwa naik turunnya nilai 𝑍 (nilai tujuan) dan juga penggunaan sumber atau fasilitas yang tersedia yang tersedia akan dapat berubah secara sebanding atau sejajar (proposional) pada perubahan tingkat kegiatan. 2. Additivity Pada asumsi ini menyatakan bahwa nilai tujuan pada setiap kegiatan tidak saling mempengaruhi satu sama lain, atau kenaikan dari nilai tujuan 𝑍 yang diakibatkan oleh kenaikan suatu kegiatan dapat ditambahkan tanpa mempengaruhi bagian nilai 𝑍 yang diperoleh dari kegiatan lain. 3. Divisibility Pada asumsi ini menyatakan bahwa suatu keluaran (output) yang dihasilkan oleh suatu kegiatan (proses) dapat berupa suatu bilangan pecahan, demikian juga dengan nilai 𝑍 yang dihasilkan. 4. Deterministic (certainty)



Pada asumsi ini menyatakan bahwa semua parameter yang terdapat di dalam model linear programming (a, b, c) tersebut dapat diperkirakan dengan pasti walaupun jarang digunakan dengan tepat.



Model pemrograman linear metode grafik Metode grafik adalah satu cara yang dapat digunakan untuk memecahkan masalah optimalisasi dalam programasi linier. Keterbatasan metode ini adalah variabel yang bisa digunakan terbatas (hanya dua), penggunaan 3 variabel akan sangat sulit dilakukan. ◦ 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 ◦ Langkah – langkah penyelesaian dengan metode grafik : - Buatlah model matematika / kendala - Tentukan fungsi sasaran 𝑍 - Menyelesaikan fungsi pertidaksamaan dengan cara :



◦ 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.



Contoh soal metode Grafik 1. Perusahaan makanan ROYAL merencanakan untuk membuat dua jenis makanan yaitu Royal Bee dan Royal Jelly. Kedua jenis makanan tersebut mengandung vitamin dan protein. Royal Bee paling sedikit diproduksi 2 unit dan Royal Jelly paling sedikit diproduksi 1 unit. Tabel berikut menunjukkan jumlah vitamin dan protein dalam setiap jenis makanan :



◦ Bagaimana menentukan kombinasi kedua jenis makanan agar meminimumkan biaya produksi. Langkah – langkah : ◦ Menentukan variable 𝑋1 = royal bee 𝑋2 = royal jelly



1. Fungsi tujuan 𝑍𝑚𝑖𝑛 = 100𝑋1 + 80𝑋2 2. Fungsi kendala 2𝑋1 + 𝑋2 ………………………………………….. 8 vitamin 2𝑋1 + 3𝑋2 ………………………………………… 12 protein



𝑋1 ……………………………………………….... 2 𝑋2 ………………………………………………… 1 ◦ Membuat grafik



a. 2𝑋1 + 𝑋2 = 8 𝑋1 = 0, 𝑋2 = 8 𝑋2 = 0, 𝑋1 = 4 b. 2𝑋1 + 3𝑋2 = 12



𝑋1 = 0, 𝑋2 = 4 𝑋2 = 0, 𝑋1 = 6 c. 𝑋1 = 2 d. 𝑋2 = 1



◦ Solusi optimal tercapai pada titik B (terdekat dengan titik origin), yaitu persilangan garis kendala (1) dan (2) 2𝑋1 + 𝑋2 = 8 2𝑋1 + 3𝑋2 = 12



−2𝑋2 = −4 𝑋2 = 2 ◦ Masukkan 𝑋2 ke kendala (1)



2𝑋1 + 𝑋2 = 8 2𝑋1 + 2 = 8 2𝑋1 = 8 − 2 2𝑋1 = 6 𝑋1 = 3



◦ Masukkan nilai 𝑋1 𝑑𝑎𝑛 𝑋2 𝑘𝑒 Z



𝑍𝑚𝑖𝑛 = 100 3 + 80 2 𝑍𝑚𝑖𝑛 = 300 + 160 𝑍𝑚𝑖𝑛 = 460



◦ Kesimpulan : ◦ Untuk meminimumkan biaya produksi, maka 𝑋1 = 3 dan 𝑋2 = 2 dengan biaya produksi Rp. 460.000,00



TERIMAKASIH