CCR314 - Riset Operasional
Materi #2 Ganjil 2015/2016
6623 - Taufiqur Rachman
http://taufiqurrachman.weblog.esaunggul.ac.id
Materi #2
CCR314 – RISET OPERASIONAL
Definisi LP 2
http://taufiqurrachman.weblog.esaunggul.ac.id
6623 - Taufiqur Rachman
Linear Programming/LP (Program Linear) merupakan salah satu teknik dalam Riset Operasional (Operation Research) yang paling luas digunakan dan dikenal dengan baik.
LP merupakan metode matematika untuk mengalokasikan sumber daya untuk mencapai tujuan tunggal seperti memaksimumkan keuntungan atau meminimumkan biaya. CCR314 - Riset Operasional
6623 - Taufiqur Rachman
Materi #2 Ganjil 2015/2016
1
CCR314 - Riset Operasional
Materi #2 Ganjil 2015/2016
Model LP 3
http://taufiqurrachman.weblog.esaunggul.ac.id
6623 - Taufiqur Rachman
Adalah sebuah model matematis yang bersifat umum yang digunakan untuk mengalokasikan faktor produksi atau sumber daya yang jumlahnya terbatas secara optimal, sehingga dapat menghasilkan laba maksimal atau biaya minimal. CCR314 - Riset Operasional
Materi #2 Ganjil 2015/2016
Fungsi-fungsi Dalam LP 4
http://taufiqurrachman.weblog.esaunggul.ac.id
6623 - Taufiqur Rachman
Variabel Keputusan • Variabel persoalan yang akan mempengaruhi nilai tujuan yang hendak dicapai. Fungsi Tujuan (objective function) • Di mana tujuan yang hendak dicapai harus diwujudkan ke dalam sebuah fungsi matematika linear, yang kemudian fungsi tersebut dimaksimumkan atau diminimumkan terhadap kendala-kendala yang ada. CCR314 - Riset Operasional
6623 - Taufiqur Rachman
Materi #2 Ganjil 2015/2016
2
CCR314 - Riset Operasional
Materi #2 Ganjil 2015/2016
Fungsi-fungsi Dalam LP 5
http://taufiqurrachman.weblog.esaunggul.ac.id
6623 - Taufiqur Rachman
Fungsi Kendala (contrains or subject to) • Kendala dalam hal ini dapat diumpamakan sebagai suatu pembatas terhadap kumpulan keputusan yang mungkin dibuat dan harus dituangkan ke dalam fungsi matematika linear yang dihadapi oleh manajemen. Fungsi Status (status function) • Fungsi yang menyatakan bahwa setiap variabel yang terdapat di dalam model programasi linear tidak boleh negatif. CCR314 - Riset Operasional
Materi #2 Ganjil 2015/2016
Asumsi Dasar
6623 - Taufiqur Rachman
6
http://taufiqurrachman.weblog.esaunggul.ac.id
Certainty
• Angka yang diasumsikan dalam fungsi tujuan dan fungsi kendala secara pasti diketahui dan tidak berubah selama waktu dipelajari.
Proporsionality
• Alokasi sumber daya dengan goal/tujuan yang ingin dicapai harus proporsional.
Additivity
• Total dari semua aktivitas adalah sama dengan jumlah dari aktivitas individual
CCR314 - Riset Operasional
6623 - Taufiqur Rachman
Materi #2 Ganjil 2015/2016
3
CCR314 - Riset Operasional
Materi #2 Ganjil 2015/2016
Asumsi Dasar 7
6623 - Taufiqur Rachman
http://taufiqurrachman.weblog.esaunggul.ac.id
Divisibility
• Jumlah produk yang akhirnya direkomendasikan dalam kondisi optimum, dapat berupa pecahan bukan bilangan bulat.
Non-negatif variable
• Semua variabel bukan negatif, bisa nol atau positif (negatif dalam kuantitas fisik a/d mustahil)
CCR314 - Riset Operasional
Materi #2 Ganjil 2015/2016
Formulasi Model
6623 - Taufiqur Rachman
8
http://taufiqurrachman.weblog.esaunggul.ac.id
Permasalahan: mencari nilai-nilai optimal (maksimum atau minimum) dari fungsi linear dengan kendala-kendala tertentu.
Fungsi Tujuan: Fungsi linear yang dioptimumkan.
Fungsi Kendala: Fungsi-fungsi linear (lebih dari satu) yang harus dipenuhi dalam optimalisasi fungsi tujuan.
Bentuk fungsi pertidaksamaan.
CCR314 - Riset Operasional
6623 - Taufiqur Rachman
tujuan:
persamaan
atau
Materi #2 Ganjil 2015/2016
4
CCR314 - Riset Operasional
Materi #2 Ganjil 2015/2016
Tahap Formulasi Model
6623 - Taufiqur Rachman
9
http://taufiqurrachman.weblog.esaunggul.ac.id
Formulasi model matematika, yang meliputi 3 tahap: 1. Tentukan variable keputusan dan nyatakan dalam simbol matematika. 2. Membentuk suatu fungsi tujuan yang ditunjukkan sebagai suatu hubungan linear dari variable keputusan. 3. Menentukan semua kendala masalah dan mengekspresikan dalam persamaan atau pertidaksamaan yang juga merupakan suatu hubungan linear dari variable keputusan. CCR314 - Riset Operasional
Materi #2 Ganjil 2015/2016
Fungsi Matematika LP
6623 - Taufiqur Rachman
10
http://taufiqurrachman.weblog.esaunggul.ac.id
1. Fungsi Tujuan Max/Min Z = c1x1 + c2x2 + ... + cnxn 2. Fungsi Kendala a11x1 + a12x2 + … + a1nxn
a21x1 + a22x2 + … ... ... ... ... ... ... am1x1 + am2x2 + … 3. Fungsi Status x1 ; x2 ……………….. Xn > 0 CCR314 - Riset Operasional
6623 - Taufiqur Rachman
+
+
a2nxn ... ... amnxn
<
b1
<
b2
<
bn
Materi #2 Ganjil 2015/2016
5
CCR314 - Riset Operasional
Materi #2 Ganjil 2015/2016
Metode-metode Dalam LP 11
http://taufiqurrachman.weblog.esaunggul.ac.id
6623 - Taufiqur Rachman
Metode Linear Programming
Metode Aljabar
Metode Grafik
Simpleks Primal
Simpleks M-Besar
Simpleks Dual
Simpleks Dua Fase
CCR314 - Riset Operasional
Materi #2 Ganjil 2015/2016
Perbedaan Metode Solusi
6623 - Taufiqur Rachman
12
http://taufiqurrachman.weblog.esaunggul.ac.id
Karakteristik Formulasi Masalah
Grafis
Simpleks
Simpleks Big – M
Jumlah Variabel
2
>2
>2
Jenis fungsi tujuan
maksimisasi & minimisasi
maksimisasi & minimisasi
maksimisasi & minimisasi
Jenis fungsi kendala
semua bentuk
CCR314 - Riset Operasional
6623 - Taufiqur Rachman
Pertidaksamaan Pertidaksamaan bertanda “>“ atau bertanda “<“ persamaan “=“ Materi #2 Ganjil 2015/2016
6
CCR314 - Riset Operasional
Materi #2 Ganjil 2015/2016
Contoh #1 13
http://taufiqurrachman.weblog.esaunggul.ac.id
6623 - Taufiqur Rachman
Sebuah perusahaan memperkerjakan pengrajin untuk memproduksi mangkok dan cangkir. Sumber daya utama yang digunakan perusahaan adalah tanah liat dan tenaga kerja. Tersedia 40 jam tenaga kerja dan 120 kg tanah liat setiap hari untuk produksi. Dengan keterbatasan sumber daya, perusahaan ingin mengetahui berapa banyak mangkok dan cangkir yang akan diproduksi tiap hari dalam rangka memaksimalkan laba. Parameter kedua produk adalah sebagai berikut: Kebutuhan Sumber Daya Produk
Tenaga Kerja (jam/unit)
Tanah Liat (kg/unit)
Laba ($/unit)
Mangkok
1
4
40
Cangkir
2
3
50
CCR314 - Riset Operasional
Materi #2 Ganjil 2015/2016
Model Contoh #1
6623 - Taufiqur Rachman
14
http://taufiqurrachman.weblog.esaunggul.ac.id
Variabel Keputusan
• X1 = jumlah mangkok yang diproduksi • X2 = jumlah cangkir yang diproduksi
Fungsi Tujuan
• Maksimalkan Z = 40X1 + 50X2 • Z = total laba per hari • 40X1 = laba dari mangkok • 50X2 = laba dari cangkir
Fungsi Kendala
• 1X1 + 2X2 ≤ 40 • 4X1 + 3X2 ≤ 120 • X1 ; X2 ≥ 0
CCR314 - Riset Operasional
6623 - Taufiqur Rachman
(kendala tenaga kerja) (kendala tanah liat) (kendala non negatif)
Materi #2 Ganjil 2015/2016
7
CCR314 - Riset Operasional
Materi #2 Ganjil 2015/2016
Contoh #2
6623 - Taufiqur Rachman
15
http://taufiqurrachman.weblog.esaunggul.ac.id
Seorang petani menyiapkan lahan untuk menanam dan membutuhkan pemupukan. Terdapat dua merek pupuk, Super-grow (SG) dan Cropquick (CQ). Setiap merek menghasilkan jumlah nitrogen dan fosfat tertentu, sebagai berikut: Kontribusi Kimia (kg/kantong)
Merek
Nitorgen
Fosfat
Super-grow (SG)
2
4
Crop-quick (CQ)
4
3
Lahan petani memerlukan paling sedikit 16 kg nitrogen dan 24 kg fosfat. Harga Super-grow $6 per kantong, dan Crop-quick berharga $3. Petani tersebut ingin mengetahui berapa banyak kantong dari setiap merek yang akan dibeli dalam rangka meminimalkan total biaya pemupukan. CCR314 - Riset Operasional
Materi #2 Ganjil 2015/2016
Model Contoh #2
6623 - Taufiqur Rachman
16
http://taufiqurrachman.weblog.esaunggul.ac.id
Variabel Keputusan
• X1 = jumlah pupuk SG yang dibeli • X2 = jumlah pupuk CQ yang dibeli
Fungsi Tujuan
• Minimalkan Z = 6X1 + 3X2 • Z = total biaya pemupukan • 6X1 = harga/biaya dari SG • 3X2 = harga/biaya dari CQ
Fungsi Kendala
• 2X1 + 4X2 ≥ 16 • 4X1 + 3X2 ≥ 24 • X1 ; X2 ≥ 0
CCR314 - Riset Operasional
6623 - Taufiqur Rachman
(kendala nitrogen) (kendala fosfat) (kendala non-negatif) Materi #2 Ganjil 2015/2016
8
CCR314 - Riset Operasional
Materi #2 Ganjil 2015/2016
Contoh #3 17
http://taufiqurrachman.weblog.esaunggul.ac.id
6623 - Taufiqur Rachman
Perusahaan sepatu membuat 2 macam sepatu. Yang pertama merek I1, dengan sol karet, dan merek I2 dengan 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 sedang merek I2=Rp.50.000. Masalahnya adalah menentukan berapa lusin sebaiknya sepatu merek I1 dan merek I2 yang dibuat agar bisa memaksimumkan laba.
CCR314 - Riset Operasional
Materi #2 Ganjil 2015/2016
Contoh #3 (Uraian Bentuk Tabel) 18
http://taufiqurrachman.weblog.esaunggul.ac.id
6623 - Taufiqur Rachman
Merek
I1 (x1)
I2 (x2)
Kapasitas Maksimum
1
?2
?0
?8
2
?0
?3
15 ?
3
?6
?5
30 ?
?3
?5
Mesin
Sumbangan laba CCR314 - Riset Operasional
6623 - Taufiqur Rachman
Materi #2 Ganjil 2015/2016
9
CCR314 - Riset Operasional
Materi #2 Ganjil 2015/2016
Model Contoh #3 19
http://taufiqurrachman.weblog.esaunggul.ac.id
• X1 = jumlah sepatu I1 yang dibuat (lusin) • X2 = jumlah sepatu I2 yang dibuat (lusin)
6623 - Taufiqur Rachman
Variabel Keputusan
Fungsi Tujuan
• Maksimamlkan Z = 3X1 + 5X2 • Z = total laba yang diperoleh • 3X1 = laba setiap lusin sepatu I1 • 5X2 = laba setiap lusin sepatu I2
Fungsi Kendala
• 2X1 ≤8 • 3X2 ≤ 15 • 6X1 + 5X2 ≤ 30 • X1 ; X2 ≥0
CCR314 - Riset Operasional
(kendala mesin 1) (kendala mesin 2) (kendala mesin 3) (kendala non-negatif) Materi #2 Ganjil 2015/2016
Contoh #4
6623 - Taufiqur Rachman
20
http://taufiqurrachman.weblog.esaunggul.ac.id
Produk yang dihasilkan oleh sebuah perusahaan adalah meja dan kursi. Dengan Bahan mentah dalam satu minggu yang tersedia adalah sebanyak 10 gelondong kayu dan jumlah jam kerja buruh yang tersedia adalah 36 jam kerja. Informasi mengenai penggunaan sumber daya dan harga jual per unit, dijelaskan dalam tabel dibawah ini : Jenis Produk Meja Kursi
Kebutuhan sumber daya Buruh(jam/unit)
Bahan(kg/unit)
Harga ($/unit)
6 6
1 2
4 5
Dengan melihat kepada informasi diatas, berapakah jumlah Meja dan Kursi yang harus dihasilkan agar keuntungan yang didapat perusahaan maksimum? CCR314 - Riset Operasional
6623 - Taufiqur Rachman
Materi #2 Ganjil 2015/2016
10
CCR314 - Riset Operasional
Materi #2 Ganjil 2015/2016
Model Contoh #4
6623 - Taufiqur Rachman
21
http://taufiqurrachman.weblog.esaunggul.ac.id
Variabel Keputusan
• X1 = jumlah meja yang dihasilkan • X2 = jumlah kursi yang dihasilkan
Fungsi Tujuan
• Maksimamlkan Z = 4X1 + 5X2 • Z = total laba yang diperoleh • 4X1 = harga meja • 5X2 = harga kursi
Fungsi Kendala
• 6X1 + 6X2 ≤ 36 • X1 + 2X2 ≤ 10 • X1 ; X2 ≥ 0
CCR314 - Riset Operasional
(kendala buruh) (kendala bahan) (kendala non-negatif) Materi #2 Ganjil 2015/2016
6623 - Taufiqur Rachman
http://taufiqurrachman.weblog.esaunggul.ac.id
22
CCR314 - Riset Operasional
6623 - Taufiqur Rachman
Materi #2 Ganjil 2015/2016
11