operations research -...
TRANSCRIPT
Fakultas Teknik
Universitas Pasundan
Jurusan Teknik Industri
Tjutju T Dimyati
OPERATIONS RESEARCH – I
MODEL-MODEL DETERMINISTIK
Jurusan Teknik Industri FT Unpas
PEMROGRAMAN LINIER
Tjutju T. Dimyati
1. Konsep Pemodelan dalam Penelitian Operasional
2. Formulasi Model Pemrograman Linier
3. Konsep Primal-Dual
Jurusan Teknik Industri FT Unpas
Tujuan Pembelajaran
Menguasai perumusan model matematis untuk persoalan Pemrograman Linier
Tjutju T. Dimyati
Jurusan Teknik Industri FT Unpas
Capaian Pembelajaran
Di akhir perkuliahan mahasiswa:
• Dapat mendefinisikan persoalan LP
• Dapat merumuskan variabel dan parameter persoalan LP
• Mampu memformulasikan model persoalan LP
• Mampu memformulasikan bentuk dual dari formulasi persoalan LP
Tjutju T. Dimyati
Jurusan Teknik Industri FT Unpas
Tjutju T. Dimyati
PEMROGRAMAN LINIER (Linear Programming, LP)
LP adalah suatu alat untuk menyelesaikan persoalan optimasi yaitu persoalan yang berkaitan dengan penentuan rancangan dan pengoperasian terbaik dari suatu sistem dengan sumber yang terbatas
Jurusan Teknik Industri FT Unpas
Tjutju T. Dimyati
Sumber Terbatas
• Waktu
• Dana
• Tenaga Kerja
• Minyak Bumi
• Sumber-sumber lain
Jurusan Teknik Industri FT Unpas
Tjutju T. Dimyati
Karakteristik Persoalan Pemrograman Linier
• Keputusan (Decisions)
• Pembatas (Constraints)
• Tujuan (objective)
Jurusan Teknik Industri FT Unpas
Tjutju T. Dimyati
DEFINISI • Fungsi Tujuan
Merupakan fungsi linier dari variabel-variabel keputusan yang akan dimaksimumkan atau diminimumkan
• Fungsi Pembatas
Merupakan persamaan atau pertaksamaan linier, dan akan membatasi nilai dari seluruh variabel keputusan
• Pembatas Tanda
Menyatakan nilai dari setiap variabel keputusan
Jurusan Teknik Industri FT Unpas
Tjutju T. Dimyati
TERMINOLOGI
• Koefisien dari variabel keputusan pada fungsi tujuan disebut koefisien fungsi tujuan
• Koefisien dari variabel keputusan pada fungsi pembatas disebut koefisien teknologikal
• Nilai di ruas kanan dari setiap fungsi pembatas disebut ruas kanan
Jurusan Teknik Industri FT Unpas
Tjutju T. Dimyati
ASUMSI PERSOALAN LP
• Seluruh persamaan, baik fungsi tujuan maupun fungsi pembatas, merupakan fungsi linier. Asumsi ini dikenal sebagai asumsi Linieritas
• Seluruh koefisien berharga konstan
• Peningkatan output bersifat proporsional terhadap peningkatan input. Asumsi ini dikenal sebagai asumsi Proporsionalitas
Jurusan Teknik Industri FT Unpas
Tjutju T. Dimyati
ASUMSI PERSOALAN LP
• Total ongkos atau keuntungan (nilai fungsi tujuan) adalah jumlah dari ongkos atau keuntungan individual, sedangkan total kontribusi terhadap pembatas adalah jumlah kontribusi individual dari kegiatan individual. Asumsi ini dikenal sebagai asumsi Aditivitas
Jurusan Teknik Industri FT Unpas
Tjutju T. Dimyati
ASUMSI PERSOALAN LP
• Seluruh variabel keputusan dapat berupa bilangan bulat ataupun bilangan pecahan. Asumsi ini dikenal sebagai asumsi Divisibilitas
• Seluruh parameter model merupakan konstanta yang sudah diketahui. Asumsi ini dikenal sebagai asumsi Deterministik
Jurusan Teknik Industri FT Unpas
Tjutju T. Dimyati
Bentuk Umum Persoalan LP
MAX (or MIN): c1X1 + c2X2 + … + cnXn
Subject to:
a11X1 + a12X2 + … + a1nXn <= b1
:
ak1X1 + ak2X2 + … + aknXn >=bk
:
am1X1 + am2X2 + … + amnXn = bm
Jurusan Teknik Industri FT Unpas
Tjutju T. Dimyati
FORMULASI PERSOALAN LINEAR PROGRAMMING
Jurusan Teknik Industri FT Unpas
Tjutju T. Dimyati
Sebuah perusahaan memproduksi dua jenis produk, A dan B, yang masing-masing dapat memberikan keuntungan per unit sebesar $5 dan $14. Setiap unit produk A membutuhkan
1 m2 bahan fiber dengan 1 jam pengerjaan, sedang setiap unit produk B membutuhkan
2 m2 bahan fiber dengan 4 jam pengerjaan. Pada setiap hari kerja perusahaan itu hanya dapat membeli paling banyak 6 m2 bahan fiber dan bekerja selama 8 jam. Bagaimanakah formulasi LP untuk rencana produksi anda?
Contoh 1 Persoalan LP
Jurusan Teknik Industri FT Unpas
Tjutju T. Dimyati
5 Langkah Memformulasikan Model LP
1. Pahami persoalan.
2. Tentukan variabel keputusan
X1=jumlah produk A yang diproduksi
X2=jumlah produk B yang diproduksi
3. Nyatakan fungsi tujuan sebagai suatu kombinasi linier dari variabel-variabel keputusan
MAX: 5X1 + 14X2
Jurusan Teknik Industri FT Unpas
Tjutju T. Dimyati
5 Langkah Memformulasikan Model LP
4. Nyatakan fungsi-fungsi pembatas sebagai suatu kombinasi linier dari variabel-variabel keputusan
1X1 + 2X2 <= 6 } fiber
1X1 + 4X2 <= 8 } jam kerja
5. Tentukan batas atas dan batas bawah dari
nilai-nilai variabel keputusan.
X1 >= 0
X2 >= 0
Jurusan Teknik Industri FT Unpas
Tjutju T. Dimyati
Model LP untuk Contoh Soal 1
MAX: 5X1 + 14X2
S.T.: 1X1 + 2X2 <= 6
1X1 + 4X2 <= 8
X1 >= 0
X2 >= 0
Jurusan Teknik Industri FT Unpas
Tjutju T. Dimyati
Contoh 2 Persoalan LP
Sebuah perusahaan memproduksi dua jenis tabung
panas, yaitu jenis Aqua-Spas & Hydro-Luxes. Data
yang terkait dengan kegiatan ini adalah:
Tersedia 200 pompa, 1566 jam kerja, dan 2880
feet tabung. Bagaimana formulasinya?
Aqua-Spa Hydro-Lux
Pompa 1 1
Waktu proses 9 hours 6 hours
Tabung 12 feet 16 feet
Profit/unit $350 $300
Jurusan Teknik Industri FT Unpas
Tjutju T. Dimyati
5 Langkah Memformulasikan Model LP
1. Pahami persoalan.
2. Tentukan variabel keputusan
X1=jumlah Aqua-Spas yang diproduksi
X2=jumlah Hydro-Luxes yang diproduksi
3. Nyatakan fungsi tujuan sebagai suatu kombinasi linier dari variabel-variabel keputusan
MAX: 350X1 + 300X2
Jurusan Teknik Industri FT Unpas
Tjutju T. Dimyati
5 Langkah Memformulasikan Model LP
4. Nyatakan fungsi-fungsi pembatas sebagai suatu kombinasi linier dari variabel-variabel keputusan
1X1 + 1X2 <= 200 } pompa
9X1 + 6X2 <= 1566 } jam kerja
12X1 + 16X2 <= 2880 } tabung
5. Tentukan batas atas dan batas bawah dari
nilai-nilai variabel keputusan.
X1 >= 0
X2 >= 0
Jurusan Teknik Industri FT Unpas
Tjutju T. Dimyati
Model LP untuk Persoalan Tabung Panas
MAX: 350X1 + 300X2
S.T.: 1X1 + 1X2 <= 200
9X1 + 6X2 <= 1566
12X1 + 16X2 <= 2880
X1 >= 0
X2 >= 0
Jurusan Teknik Industri FT Unpas
Tjutju T. Dimyati
KONSEP PRIMAL - DUAL • Setiap formulasi persoalan LP mempunyai
bentuk Dual
• Jika fungsi tujuan Primal adalah Maks maka fungsi tujuan Dual adalah Min dan sebaliknya
• Dual dari Dual adalah Primal
• Solusi optimal persoalan Primal (jika ada) adalah sama dengan solusi optimal persoalan Dual
• Jika persoalan Primal tidak fisibel maka Dual akan unbounded dan sebaliknya
Jurusan Teknik Industri FT Unpas
Tjutju T. Dimyati
KONSEP PRIMAL - DUAL • Jumlah baris pada Primal sama dengan
jumlah kolom pada Dual dan sebaliknya
• Ruas kanan pada Primal akan menjadi koefisien fungsi tujuan pada Dual dan sebaliknya
• Jika pembatas Primal normal maka variabel Dual akan normal dan sebaliknya
• Jika pembatas Primal bertanda = maka variabel Dual akan tidak terbatas dalam tanda dan sebaliknya
Jurusan Teknik Industri FT Unpas
Tjutju T. Dimyati
Contoh Soal
Bagaimanakah bentuk Dual dari:
Maks Z = 3 X1 + 5 X2
dengan pembatas
X1 4
2 X2 = 12
3 X1 + 2 X2 18
X1 URS , X2 0