PEMODELAN DAN OPTIMASI
(Modelling and optimization)
Peranan rekayasa sistem (system engineering) adalah untuk
mendapatkan metodologi yang sisitematik dalam melakukan studi
(mempelajari) dan menganalisis berbagai aspek sistem, baik struktural
maupun non struktural menggunakan model matematik atau fisik.
Rekayasa sistem juga membantu proses pembuatan keputusan
dengan cara seleksi kebijakan alternatif terbaik menggunakan simulasi
dan Teknik optimasi.
Model matematik : Satu set persamaan yang menggambarkan dan
mempresentasikan sistem nyata (real system).
Model matematik umumnya digunakan untuk mendapatkan cara
terbaik dalam mengatur (controlling) atau mengelola (management)
sebuah sistem fisik.
Persamaan-persamaan dalam model matematik menunjukkan
rumusan berbagai aspek persoalan, mengidentifikasikan hubungan
fungsional diantara komponen dan elemen dalam sistem, menetapkan
ukuran efektifitas dan kendala, serta menunjukkan data yang
diperlukan terkait dengan persoalan secara kuantitatif.
1
Untuk itu model matematik yang dibuat harus semirip/sedekat mungkin
dengan sistem yang dimodelkan. Kriteria umum untuk hal ini adalah
keluaran model dan keluaran sistem nyata harus identik.
Actual system Model predicted
respond system respond
Real physical Mathematical
system model
Non-modeled
Modeled input
input
Solution strategy
(Optimization and Simulation)
Gambar 1. Representasi skema proses pemodelan dan optimasi
sistem
Solusi yang diperoleh dari penyelesaian model matematik dapat
diaplikasikan pada sistem fisik yang sesungguhnya. Dalam
menerapkan stategi penyelesaian persoalan kita dapat menempuh
dengan pendekatan optimasi, simulasi atau gabungan keduanya.
Hasil akhir dari prosedur di atas hádala keputusan optimal terkait
dengan pengendalian dan/atau pengelolaan sebuah sistem.
2
Ungkapan matematik secara umum dikatakan sebagai prosedur
optimasi (optimalisasi), yaitu:
Prosedur penetapan nilai sejumlah variable keputusan
(decision variables) sesuai dengan fungís tujuan
(objective function) yang diinginkan (maximize or
minimize) dan memenuhi batasan-batasan (contraints)
yang berlaku pada sistem yang ditinjau.
3
Prinsip Dasar “Mathematical Programming”
Prosedur umum penyelesaian “mathematical programming” diawali
dengan mendefinisikan komponen persoalan berikut ini.
Decision Variables : sebagai besaran yang akan dicari nilainya.
Parameters : ukuran-ukuran bernilai tetap dan dapat
diterapkan dalam perhitungan seperti harga,
biaya, benefit dan lain-ain.
Constraints : sebagai faktor pembatas/kendala yang perlu
dirumuskan secara matematis.
Objective Function : adalah pernyataan kuantitatif dari kasus
optimasi, sebagai contoh: memaksimumkan
benefit, menentukan biaya operasi minimum.
4
Teknik Optimasi
Setiap algoritme dari “Operations Research” diturunkan dengan prinsip
yang sama, yaitu untuk mencapai penyelesaian yang optimal atau
dengan kata lain solusi terbaik dapat diperoleh melalui penggunaan
teknik optimasi. Beberapa teknik optimasi yang termasuk dalam
kelompok “Mathematical Programming” adalah:
1. Calculus Method,
2. Linier Programming (LP),
3. Non Linear Programming (NLP),
4. Integer Programming (IP),
5. Dynamic Programming (DP),
6. Integer Linear Programming (ILP).
Optimasi dengan menggunakan metode kalkulus merupakan cara
klasik yang dapat dipergunakan untuk menentukan nilai optimal dari
suatu fungsi kontinyu dan diferensiable (dapat
diturunkan/dideferensialkan). Metode analitis ini menggunakan prinsip
diferensial kalkulus untuk menemukan lokasi titik-titik optimum. Dengan
algoritme tersebut, metode ini terbatas keberlakuannya hanya untuk
pemakaian praktis, oleh karena beberapa persoalan dapat melibatkan
fungsi tujuan yang tidak bersifat kontinyu atau tidak dapat
dideferensialkan.
5
SOLUTION?
Environmental Problems
(air, water, soil, wastes, noise, etc.)
As
Environmental
io
se
at System
ul
ss
m
m
Si
en
t
Optimization
Modeling Decision Making Implementation Engineering
Approaches Techniques
Sustainable Development
5
© Bing Chen, 2007
1.2 What is “Optimization”?
¾ Mathematical Programming
A mathematical procedure for performing constrained optimization
Typically used to determine an optimal allocation of scarce resources
¾ Components
Decision variables ==> what can we change?
Constraints ==> restrict the set of alternatives
Objective function ==> how do we measure the quality of a solution?
¾ Goal ==> Assign values to decision variables to find the best
solution, subject to the constraints
profit maximization with cost / resource constraints
cost minimization with benefit imperatives
¾ Significant impact ==> optimal solution to the complex systems
Cost-efficiently solve environmental problems
Save lots of money by optimally allocating scarce resource
6
© Bing Chen, 2007
Model Matematik Standar
Penerapan model matematik untuk optimasi pengelolaan sumberdaya
air pada daerah aliran sungai atau pada satuan wilayah sungai
umumnya mempunyai bentuk perumusan yang kompleks, sehingga
penyelesaian secara numeris perlu digunakan alat bantu hitung yang
memadai. Penggunaan program komputer sekarang ini sudah
merupakan keharusan untuk memperoleh penyelesaian model
matematik yang efisien dengan akurasi yang memuaskan.
Masing-masing algoritme dari “operations research” (program linier,
program dinamik, simulasi, teknik penelusuran dan lain-lain) telah
banyak dibuat paket program yang dapat dipergunakan untuk kasus
optimasi di bidang sumberdaya air. Secara umum bentuk standar
model akan mengikuti perumusan matematik sebagai berikut ini.
Fungsi tujuan dapat berupa pernyataan upaya memaksimumkan atau
meminimumkan perolehan manfaat pengelolaan sistem sumberdaya.
OF : max Z = f ( X1, X2, X3, ... , Xn ) atau min Z = f ( X1, X2, X3, ... , Xn )
dengan kendala : gi ( X1, X2, X3, ... , Xn ) ≥ bi ; i = 1,2, ... , m
dimana :
Xi = decision variables,
f dan gi = fungsi yang tergantung dari nilai Xi,
bi = parameter model,
m = banyaknya rumusan kendala.
6
Examples: Water Resource Systems
¾ Key concepts based on words: “water”, “resource”, and “system”:
¾ Water is viewed as a valued resource, to be beneficially managed.
¾ Management frequently must deal with a complex “system” composed of
many interconnected parts –
It is often difficult to subdivide the original problem into independent sub-
problems.
How do we define the “system”? How large? Over what time scale? How much
detail? Should it include social and political institutions?
We often try to find the “best” solution – but how do we define “best”?
¾ Examples of water resource systems problems:
Watershed management – select facilities (reservoirs, aqueducts, irrigation
infrastructure, etc.) to maximize benefit from resource
Aquifer management – installation and operation of wells and recharge areas
Capacity expansion – how much should facilities be expanded, when?
Real-time operations – what to do today, considering impacts on the future
Remediation – select best mix of remedies for cleaning up contamination
3
© Bing Chen, 2007
Other Examples
¾ Air Pollution Control System
Source (point, line, and area sources) reduction, emission control, and
health protection
¾ Sewerage System
Generation (industrial, commercial, and residential sources), collection
(pipeline networks), and treatment
¾ Waste Management System
Generation, collection, transport, storage, treatment and disposal
¾ Water Quality Management System
Drinking water sources protection, water treatment, and delivery
¾ Cleaner production systems
Production process, emission sources, and clearer production technologies
¾ Urban and rural systems
Economical (various industries), social and environmental development
4
© Bing Chen, 2007
Problem Formulation and Components
Maximize F (x1, x2, …, xn) Max F = CX
s.t. (subject to or such that) s.t.
OR
gi (x1, x2, …, xn) = 0 (i = r, …, r) AX ≤ B
gi (x1, x2, …, xn) ≤ 0 (i = r +1, …, m) X≥0
¾ Objective Function (F): (“want”)
An output function that you want to maximize or minimize.
E.g. Maximize profit, yield, flow; Minimize cost, space used, time taken, or risk
¾ Decision Variables (xi): (“should”)
A set of input variables whose values you can change.
E.g. the volume of raw water we should take; the level of treatment we should
do; the amount of product we should produce
¾ Constraints (gi): (“can’t”)
A set of restrictions on the permissible values (or combinations of values) of
the input variables.
E.g. cannot override water quality standards; cannot withdraw more than
1,000 mgd from a river. 7
© Bing Chen, 2007
Examples in Environmental Engineering
(Loucks et al., 1981)
EXAMPLE 1.1:
Improved factor for quality
index ==>
Site 1-2: 0.025 /unit
Site 1-3: 0.0125 /unit
Site 2-3: 0.025 /unit
At least 30% removal is
required at both sites and
the max removal eff. is 95%
The cost of treatment = cost coefficient * fraction of waste removed (C1 = 10 and C2 = 6)
EXAMPLE 1.2:
(Mohammed, 2006)
Total hardness
requirement = 1200
(lbs/mgd)
Total water demand = 150
mgd
8
© Bing Chen, 2007
Examples in Environmental Engineering
EXAMPLE 1.3:
Water distribution
problem
(Mohammed, 2006)
EXAMPLE 1.4:
City 2 City 3
Waste management
problem
WTE 2
(WTE: waste to energy WTE 1
facility)
Landfill City 1
9
© Bing Chen, 2007
Major Types of Optimization Problems
¾ Linear Programming
min F = x1 + 1.5x2 F = 2.25
Linear objective function
x1 + 3x2 ≥ 3 x1 = 1.5
Linear constraints
x1 + x2 ≥ 2
Continuous variables x2 = 0.5
x≥0
¾ Integer Programming
max f = x1 + 3x2
Linear objective function F = 14
5x1 + 10x2 ≤ 50
Linear constraints x1 + x2 ≥ 1 x1 = 2
Integer variables x2 ≤ 4 and integer x2 = 4
x ≥ 0 and integer
¾ Non-linear Programming
Non-linear objective function max f = 8x1 + 10x2 - x12 - x22 F = 21.3
Non-linear constraints 3x1 + 2x2 ≤ 6 x1 = 0.3
Continuous or Integer variables x≥0 x2 = 2.5
10
© Bing Chen, 2007
CONTOH APLIKASI PROGRAM LINIER
UNTUK OPTIMALISASI
Bentuk Perumusan Standar
Program linier merupakan salah satu model matematik yang
cukup populer dan telah lama diterapkan dalam analisis optimasi
bidang sumberdaya air. Paket program yang dibuat berdasarkan
algoritme simplex untuk penyelesaian hitungan telah banyak
dijumpai, seperti LINDO, Excel Solver dan lain-lain, sehingga
model ini cukup mudah penggunaannya.
Model program linier dapat diterapkan untuk kasus optimasi
dengan jumlah variabel dan perumusan kendala yang cukup
banyak. Hanya saja model ini terbatas pada kasus yang
perumusan fungsi tujuan dan kendalanya mempunyai bentuk
hubungan linier.
Untuk kasus dengan n variabel dan m fungsi kendala
bentuk standar perumu-san model matematik adalah sebagai
berikut ini.
Max Z = C1 X 1 + C2 X 2 + L + Cn X n
sedemikian hingga dipenuhi:
a11 X 1 + a12 X 2 + L + a1n X n ≤ b1
a 21 X 1 + a 22 X 2 + L + a 2 n X n ≤ b2
a m1 X 1 + a m 2 X 2 + L + a mn X n ≤ bm
X i ≥ 0; i = 1,2,L n
1
Contoh 1
Besaran Z yang merupakan fungsi variabel X1 dan X2
mempunyai bentuk hubungan sebagai berikut:
Z = 3X1 + 5X2
Keterbatasan sumberdaya X1 dan X2 ditunjukkan pada
beberapa persamaan kendala sebagai berikut ini.
a. X1 ≤ 4
b. 2X2 ≤ 12
c. 3X1 + 2X2 ≤ 18
d. X1 ≥ 0
e. X2 ≥ 0
Untuk memperoleh nilai variabel X1 dan X2 yang memberikan
harga Z maksimal, maka dapat dituliskan perumusan fungsi tujuan
sebagai berikut ini.
OF : max Z = 3X1 + 5X2
Penyelesaian untuk kasus di atas dapat dicapai dengan
prosedur grafis seperti ditunjukkan pada gambar berikut ini.
X2
(X*1 = 2, X*2 = 6)
10
8 X1 = 4
2X2 = 12
6
4
Feasible Z* = 36 = 3X*1 + 5 X*2
solution
2
3X1 + 2X2 = 18
X1
0 2 4 6 8 10 12 14
Z = 10
2
Dari gambar grafik di atas dapat diperoleh titik optimal adalah
(2,6) yang memberikan nilai Z maksimal, yaitu sebesar 36.
Memperhatikan letak titik optimal dengan penyelesaian cara
grafis akan diperoleh ciri solusi optimal, yaitu:
1. titik optimal terletak pada batas daerah “feasible solution”,
2. titik optimal terletak pada perpotongan garis-garis dari “active
constraints”, yaitu garis memenuhi persamaan untuk nilai
variabel optimal, atau dengan kata lain apabila nilai variabel
optimal disubstitusikan ke dalam rumusan kendala, akan
menjadi persamaan (tanda ≤ atau ≥ akan menjadi = ).
Berdasarkan sifat tersebut dikembangkan algoritme simplex
untuk mencari solusi yang lebih umum keberlakuannya dengan
cara iterasi.
Contoh 2
Tiga orang petani bekerja sama harus menetapkan jenis
tanaman dan luas areal yang ditanam untuk 3 macam tanaman.
Data tentang ketersediaan lahan, air, benefit, kebutuhan air dan
batas maksimum luas lahan untuk tiap jenis tanaman disajikan
seperti pada tabel di bawah ini. Kesepakatan yang mereka
tetapkan adalah luas tanaman dan luas ketersediaan lahan
masing-masing petani harus proporsional.
Tabel Ketersediaan Lahan dan Air
Petani Lahan tersedia Ketersediaan air (1000 m3)
(ha)
1 400 600
2 600 800
3 300 375
3
Tabel Benefit, Maksimum Luas Tanam dan Kebutuhan Air
Tanaman Benefit Max. area Kebutuhan Air
(US$/ha) (ha) (1000 m3)
1 400 600 3
2 300 500 2
3 100 325 1
Untuk menyelesaikan persoalan di atas, perlu dirumuskan
model matematiknya sebagai berikut ini.
Decision variables
Xij = luas tanaman petani i untuk tanaman j dalam ha (i = 1,2,3)
Objective function
max Z = 400 (X11 + X21 + X31 ) + 300 (X12 + X22 + X32 )
+ 100 (X13 +X23 + X33)
Z = total benefit.
Constraints
Lahan : X11 + X12 + X13 ≤ 400
X21 + X22 + X23 ≤ 600
X31 + X32 + X33 ≤ 300
Air : 3X11 + 2X12 + X13 ≤ 600
3X21 + 2X22 + X23 ≤ 800
3X31 + 2X32 + X33 ≤ 375
Luas tanam : X11 + X21 + X31 ≤ 600
4
X12 + X22 + X32 ≤ 500
X13 + X23 + X33 ≤ 325
Proporsonality :
X11 + X12 + X13 X21 + X22 + X23 X31 + X32 + X33
= =
400 600 300
Non Negativity
Xij ≥ 0 ; i = 1,2,3 dan j = 1,2,3
Penyelesaian kasus optimasi di atas tidak dapat diselesaikan
secara grafis, akan tetapi dengan iterasi mengikuti algoritme
simplex. Dengan software untuk program linier berdasarkan
algoritme simplex diperoleh hasil optimal seperti pada tabel berikut.
Tabel Solusi Optimal
Petani Luas tanaman (ha) Total area
1 2 3 (ha)
1 133,3 100 0 250,3
2 100 250 0 350
3 25 150 0 175
Jumlah 258,3 500 0
Dengan nilai-nilai variabel optimal (ada 9 variabel) seperti
pada tabel di atas, dapat diperoleh harga total benefit maksimum
sebagai berikut :
Z* = 400 x 258,3 + 300 x 500 + 100 x 0
= 103.333,3 + 150.000 + 0 = 253.333,3 US$
5
Contoh 3
Sebuah pabrik yang telah dilengkapi dengan instalasi
pengolah limbah akan menyusun rencana produksi dengan
memperhatikan batasan syarat kualitas air dari buangan limbah.
Produk pabrik tersebut dapat dijual dengan harga $ 10 per unit
dengan biaya produksi $ 3 per unit. Untuk satu unit barang yang
diproduksi akan menghasilkan 2 unit limbah. Kapasitas instalasi
pengolah limbah adalah 10 unit limbah dengan efisiensi
penghilangan limbah 80%. Biaya pengolahan limbah per unit
limbah adalah $ 0,6. Pengusaha pabrik juga dikenai pajak sebesar
$ 2 per unit limbah yang sampai di badan sungai (tempat
pembuangan limbah). Di lokasi pembuangan limbah (sungai)
berlaku ketentuan bahwa limbah yang sampai di badan sungai
tidak boleh lebih dari 4 unit.
Dengan latar belakang persoalan tersebut bagian produksi
pabrik harus menentukan kapasitas unit produksi dan limbah yang
harus diolah di instalasi pengolah limbah (sebagian dibuang
langsung ke sungai), agar mendapat keuntungan maksimal serta
tidak melanggar ketentuan batas kualitas air buangan limbah.
Rumuskanlah model optimasi dengan metode Program Linier serta
berikan solusi optimalnya.