Introduction (Linear Programming) Toha Ardi Nugraha
Optimization=Engineering Engineering is the process of taking the discoveries from science... implementing them as practical devices, and then ... making them better, ... and better, ... and better. This is optimization.
Pendahuluan Mengapa mata kuliah ini diberikan? adalah untuk memberikan wawasan, pengetahuan dan skill bagaimana membuat sistem menjadi optimal. Metode Optimasi adalah cabang ilmu pengetahuan inter disiplin yang berhubungan dengan penyelesaian masalah menggunakan pendekatan matematik dan diolah secara komputatif
Pendahuluan Banyak sekali persoalan-persoalan optimasi dalam kahidupan sehari-hari seperti :
optimasi pengunaan jalan, optimasi bahan bakar minyak, optimasi pemakaian listrik, optimasi pemakaian air, optimasi pemakaian pulsa telpon, dsb,,
Optimasi?? Toha Ardi Nugraha
Nilai terbaik Berdasar Kriteria dan beberapa alternatif
Proses mencari
Optimasi ?????
Tahapan Optimasi Identifikasi Masalah
Metode Approach
Memilih Tujuan
Definisi Sistem
Bangun Fungsi Tujuan/Kendala
Konstruksi, Simulasi, Simplikasi, Verifikasi
Lingkup Materi dalam Metode Optimasi
Analitik
Linier
Numerik
Non Linier
Fibonacci Evolusi
Single Variabel
Dgn Kendala
Multi Variabel
Tanpa Kendala
Complex
Combinasi
Intelijen Fuzzy Logic Neural Network/JST Genetic Algoritm
Linier Programming
Linier Programming Program linier adalah suatu teknik penyelesaian optimal atas suatu problema keputusan dengan cara menentukan terlebih dahulu fungsi tujuan (memaksimalkan atau meminimalkan) dan kendalakendala yang ada ke dalam model matematik persamaan linier.
Mathematical Programming (MP) • MP adalah ilmu manajemen yang menentukan suatu optimasi, atau efisiensi yang sangat tinggi, dengan menggunakan sumber daya untuk mencapai tujuan individu pada suatu bisnis • Kata kunci :Optimasi (Optimization)
Penerapan Optimasi • • • • •
Penentuan Product Manufaktur Transportasi dan Logistik Perencanaan Finansial Dll.
12
Karakteristik Masalah Optimasi • Keputusan (Decisions) • Kendala (Constraints) • Tujuan (Objectives)
Bentuk Umum Optimasi MAX (or MIN): Subject to:
f0(X1, X2, …, Xn) f1(X1, X2, …, Xn)<=b1 : fk(X1, X2, …, Xn)>=bk : fm(X1, X2, …, Xn)=bm
N.B: Jika seluruh fungsi bersifat linier, maka disebut dengan masalah Program Linier/ Linear Programming (LP) problem
Masalah Program Linier (PL) MAX (or MIN): c1X1 + c2X2 + … + cnXn Subject to:
a11X1 + a12X2 + … + a1nXn <= b1 : ak1X1 + ak2X2 + … + aknXn >=bk : am1X1 + am2X2 + … + amnXn = bm
Contoh Penulisan Persamaan PL
Contoh lain Penulisan Persamaan PL dengan lambang penjumlahan
Penulisan dalam bentuk matriks
Asumsi-asumsi yang Harus Dipenuhi dalam Program Linier
Contoh PL Sebuah perusahaan memproduksi 2 jenis pipa, yaitu : Aqua & Hydro, degan rincian sumber daya sbb: Aqua Hydro Pompa 1 1 Jam Kerja 9 jam 6 jam Pipa 12 meter 16 meter Laba/Unit $350 $300 Terdapat 200 pompa, 1566 jam kerja, dan 2880 meter persediaan pipa.
5 Langkah Formulasi Model PL 1. Memahami masalah 2. Identifikasi variabel keputusan X1=jumlah pipa Aqua yang dihasilkan X2=jumlah pipa Hydro yang dihasilkan 3. Penentuan fungsi tujuan sebagai kombinasi linier dari variabel keputusan MAX: 350X1 + 300X2
5 Langkah Formulasi Model PL (sambungan)
4. Menentukan konstrain sebagai kombinasi linier dari variabel keputusan 1X1 + 1X2 <= 200 } pompa 9X1 + 6X2 <= 1566 } jam kerja 12X1 + 16X2 <= 2880 } pipa 5. Identifikasi batas atas atau bawah dari variabel keputusan. X1 >= 0 X2 >= 0
Model PL PT. GUNDAR • MAX: 350X1 + 300X2 S.T.: 1X1 + 1X2 <= 200 9X1 + 6X2 <= 1566 12X1 + 16X2 <= 2880 X1 >= 0 X2 >= 0
Penyelesaian Masalah PL: Pendekatan Intuitif • Ide : Setiap Aqua (X1) menimbulkan laba/unit yg tertinggi ($350), buatlah kemungkinan tersebut! • Seberapa besar hal tsb. dapat terjadi? – Misalkan X2 = 0 • Konstrain-1: 1X1 <= 200 • Konstrain-2: 9X1 <=1566 or X1 <=174 • Konstrain-3: 12X1 <= 2880 or X1 <= 240
• Jika X2=0, nilai maksimum X1 adalah 174 keuntungan totalnya adalah $350*174 + $300*0 = $60,900 • Solusi tersebut layak (feasible), tapi apakah optimal? No!
Penyelesaian Masalah PL:
Pendekatan Grafik
• Beberapa konstrain/kendala suatu PL mendefinisikan daerah feasiblenya • Titik terbaik dari daerah feasible adalah solusi optimal masalah tersebut • Untuk PL dengam 2 variabel, sangatlah mudah untuk memplot daerah feasible dan menentukan solusi optimalnya
Plotting Konstrain-1
X2 250
(0, 200) 200
Garis batas dari konstrain pompa X1 + X2 = 200
150
100
50 (200, 0) 0 0
50
100
150
200
250
X1
Plotting Konstrain-2
X2
(0, 261)
250 Garis batas dari konstrain jam kerja 9X1 + 6X2 = 1566
200
150
100
50 (174, 0) 0 0
50
100
150
200
250
X1
Plotting Konstrain-3
X2 250
(0, 180) 200
150 Garis batas dari konstrain pipa 12X1 + 16X2 = 2880
100 Daerah Feasible
50 (240, 0) 0 0
50
100
150
200
250
X1
Plotting Sebuah Kurva Bertingkat Dari Fungsi Tujuan 250
X2
200 (0, 116.67)
Fungsi Tujuan
150
350X1 + 300X2 = 35000 100 (100, 0)
50
0 0
50
100
150
200
250
X1
Kurva Kedua Dari Fungsi Tujuan
X2 250
(0, 175) 200
Fungsi Tujuan 350X1 + 300X2 = 35000 Fungsi Tujuan 350X1 + 300X2 = 52500
150
100
(150, 0)
50
0 0
50
100
150
200
250
X1
Gunakan Kurva Bertingkat Untuk Melokalisir Solusi Optimal
X2 250
Fungsi Tujuan 350X1 + 300X2 = 35000
200
150 Solusi Optimal 100 Fungsi Tujuan 350X1 + 300X2 = 52500
50
0 0
50
100
150
200
250
X1
Perhitungan Solusi Optimal • Solusi optimal terjadi dimana kendala pompa dan jam kerja beririsan. • Hal ini terjadi ketika: X1 + X2 = 200 (1) dan 9X1 + 6X2 = 1566 (2) • Dari (1) kita dapatkan X2 = 200 -X1 (3) • Subtitusi (3) ke dalam (2), dan kita punyai : 9X1 + 6 (200 -X1) = 1566 yang menghasilkan X1 = 122 • Sehingga solusi optimalnya adalah : X1=122, X2=200-X1=78 Total Keuntungan = $350*122 + $300*78 = $66,100
Hitung Nilai Fungsi Tujuan Setiap Titik Sudut
X2 250
obj. value = $54,000 (0, 180)
200
Catt.: Metode ini tak akan berjalan jika solusinya tak terbatas
obj. value = $64,000
150
(80, 120) obj. value = $66,100 (122, 78)
100
50
obj. value = $60,900 (174, 0)
obj. value = $0 (0, 0)
0 0
50
100
150
200
250
X1
Ringkasan Pendekatan Grafik Pada Masalah PL 1. Plot garis batas setiap konstrain 2. Identifikasi daerah feasible/layak 3. Lokalisasi solusi optimal dengan melakukan: a. Plotting Kurva bertingkat b. Hitung nilai setiap titik sudut
Kondisi Khusus PL • Sejumlah anomali dapat terjadi pada masalah PL, a.l. : – – – –
Solusi optimal bergantian Kendala redundan (mubazir) Solusi tak terbatas Tak layak
Contoh Solusi Bergantian
X2 250
Kurva bertingkat f. tujuan
450X1 + 300X2 = 78300
200
150
100
Solusi optimal bergantian 50
0 0
50
100
150
200
250
X1
Contoh Kendala Redundan X2 250 Garis batas konstrain pipa 200 Garis batas konstrain pompa 150 Garis batas konstrain jam kerja
100 Daerah Layak
50
0 0
50
100
150
200
250
X1
Contoh Solusi Tak Terbatas X2 1000
Fungsi tujuan X1 + X2 = 600
800
-X1 + 2X2 = 400
Fungsi tujuan X1 + X2 = 800
600
400
200 X1 + X2 = 400
0 0
200
400
600
800
1000
X1
Contoh Tak Layak
X2 250
200
X1 + X2 = 200
Daerah layak untuk konstrain-2
150
100 Daerah layak untuk konstrain-1
50
X1 + X2 = 150
0 0
50
100
150
200
250
X1
