BAB 1
OPTIMASI
&
PROGRAM LINIER (PL)
1
Pendahuluan
Kita mengenal beberapa masalah
keputusan yang butuh sumberdaya
berikut :
Minyak Tanah
Waktu
Uang
Pekerja
Dll.
2
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)
3
Penerapan Optimasi
Penentuan Product Mix
Manufaktur
Transportasi dan Logistik
Perencanaan Finansial
Dll.
4
Karakteristik Masalah Optimasi
Keputusan (Decisions)
Kendala (Constraints)
Tujuan (Objectives)
5
Bentuk Umum Optimasi
MAX (or MIN): f0(X1, X2, …, Xn)
Subject to: 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
6
Masalah Program Linier (PL)
MAX (or MIN): c1X1 + c2X2 + … + cnXn
Subject to: a11X1 + a12X2 + … + a1nXn <= b1
:
ak1X1 + ak2X2 + … + aknXn >=bk
:
am1X1 + am2X2 + … + amnXn = bm
7
Contoh PL
PT. GUNDAR 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.
8
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
9
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
10
Model PL PT. GUNDAR
MAX: 350X1 + 300X2
S.T.: 1X1 + 1X2 <= 200
9X1 + 6X2 <= 1566
12X1 + 16X2 <= 2880
X1 >= 0
X2 >= 0
11
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!
12
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
13
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
14
Plotting Konstrain-2
X2
(0, 261)
250
Garis batas dari konstrain jam kerja
200 9X1 + 6X2 = 1566
150
100
50
(174, 0)
0
0 50 100 150 200 250 X1
15
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
16
Plotting Sebuah Kurva Bertingkat
Dari Fungsi Tujuan
250
X2 200
(0, 116.67) Fungsi Tujuan
150
350X1 + 300X2 = 35000
100
50 (100, 0)
0
0 50 100 150 200 250 X1
17
X2 Kurva Kedua Dari Fungsi Tujuan
250
(0, 175) Fungsi Tujuan
200
350X1 + 300X2 = 35000
Fungsi Tujuan
150 350X1 + 300X2 = 52500
100
(150, 0)
50
0
0 50 100 150 200 250 X1
18
Gunakan Kurva Bertingkat Untuk
X2 Melokalisir Solusi Optimal
250
Fungsi Tujuan
200
350X1 + 300X2 = 35000
150
Solusi Optimal
100
Fungsi Tujuan
350X1 + 300X2 = 52500
50
0
0 50 100 150 200 250 X1
19
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
20
Hitung Nilai Fungsi Tujuan
X2 Setiap Titik Sudut
250 Catt.: Metode ini tak akan berjalan
jika solusinya tak terbatas
obj. value = $54,000
200 (0, 180)
obj. value = $64,000
150
(80, 120)
obj. value = $66,100
100
(122, 78)
50
obj. value = $0 obj. value = $60,900
(0, 0) (174, 0)
0
0 50 100 150 200 250 X1
21
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
22
Selesai … ?
Bersambung !
23