MAKALAH
METODE NUMERIK
OPTIMASI
Oleh:
KELOMPOK
10
ADRIANI LESTARI 1507112793
ALFINO HENDRA
1507117782
ERLIANA NDURU 1507122637
ZARAH
AYU WULANDARI 1507113708
PROGRAM
STUDI TEKNIK KIMIA S1
FAKULTAS
TEKNIK
UNIVERSITAS
RIAU
PEKANBARU
2017
BAB
X
OPTIMASI
Kompetensi:
Setelah mempelajari bab ini, mahasiswa:
1.
Mampu mengidentifikasi berbagai bentuk problem optimasi yang sering ditemukan dalam bidang Teknik Kimia.
2.
Mengenal berbagai metode
penyelesaian problem
optimasi.
3.
Mampu menyelesaikan problem optimasi
dengan metode yang sesuai.
4.
Mampu menginterpretasikan
hasil penyelesaian problem
optimasi untuk aplikasi bidang Teknik Kimia.
10.1 Pendahuluan
Masalah
optimasi muncul di berbagai bidang rekayasa, yaitu saat rekayasawan harus
mengambil keputusan pada situasi dimana beberapa tujuan yang sering kali saling
bertentangan serentak harus dipenuhi secara optimal, sambil mempertimbangkan
terbatasnya sumber daya yang ada. Karenanya diperlukan suatu sistem/proses
untuk mendukung pengambilan keputusan tersebut. Optimasi merupakan suatu
proses untuk mencari kondisi yang optimum, dalam arti paling menguntungkan. Optimasi bisa berupa maksimasi atau
minimasi. Jika berkaitan dengan masalah keuntungan, maka keadaan optimum adalah
keadaan yang memberikan keuntungan maksimum. Jika berkaitan dengan masalah
pengeluaran/pengorbanan, maka keadaan optimum adalah keadaan yang memberikan
pengeluaran/pengorbanan minimum.
Optimasi merupakan suatu proses untuk mencari
kondisi yang optimum, dalam arti paling menguntungkan. Optimasi bisa berupa maksimasi atau minimasi. Jika berkaitan
dengan masalah keuntungan, maka keadaan optimum adalah keadaan yang memberikan
keuntungan maksimum (maksimasi).
Jika berkaitan dengan masalah pengeluaran/pengorbanan, maka keadaan optimum
adalah keadaan yang memberikan pengeluaran/pengorbanan minimum (minimasi).
Optimasi dapat
digunakan untuk desain pompa dan
peralatan perpindahan panas untuk efisiensi maksimum serta untuk desain sistem
pengolahan air limbah untuk menemukan standar kualitas air pada biaya yang
rendah. Adapun hal-hal penting dalam studi optimasi meliputi fungsi
objektif dan decision variables serta kendala (constraints).
Salah satu contoh penerapan optimasi dalam bidang teknik kimia adalah
seperti persoalan
pemilihan diameter pipa untuk mengangkut fluida dari satu proses ke proses yang
lain. Istilah diameter pipa optimum,
didasarkan kepada biaya investasi, dan biaya operasi. Dalam hal ini tentu kita
akan memilih diameter pipa yang optimum dengan pertimbangan dua hal tersebut,
dan salah satu cara adalah dengan menggunakan optimasi. Hal-hal penting dalam studi
optimasi meliputi:
1.
Fungsi
objektif dan decision variables
2.
Kendala (constraints)
Secara umum, fungsi
yang akan dimaksimumkan atau diminimumkan disebut fungsi objektif (objective
function), sedangkan harga-harga yang berpengaruh dan bisa dipilih
disebut variabel perubah atau decision
variable.
Secara analitik, nilai
maksimum atau minimum dari suatu persamaan:y = f (x) dapat
diperoleh pada harga x yang memenuhi:
................................................................. (10.1)
Untuk fungsi yang sulit
diturunkan atau mempunyai turunan yang sulit dicari akarnya, proses optimasi
dapat dilakukan secara numerik.
Contoh
persoalan optimasi dalam bidang engineering:
·
Desain pompa
dan peralatan perpindahan panas untuk efisiensi maksimum
·
Desain sistem
pengolahan air limbah untuk menemukan standar kualitas air pada biaya yang
rendah
·
Perencanaan
optimal dan penyusunan (Optimal planning and scheduling)
·
Jaringan
optimal perpipaan (Optimal pipeline network)
·
Kontrol
Inventori (Inventory control)
·
Perencanaan
perlengkapan untuk meminimalkan biaya (Maintenance planning to minimize cost)
Contoh kendala
(constraints) yang menyertai persoalan optimasi dalam bidang
Teknik Kimia:
·
Maximum process temperature
·
Maximum flow rate limitation
·
Maximum conversion limitation
·
Product purity
·
Strength of materials
·
Environmental factor
·
Safety consideration
·
Availability of utilities
·
Corrosion considerations
·
Availability and characteristics of
feed stocks
·
Market demand for the product
·
Space limitation
·
An upper limit on the capital
investment
Ilustrasi
secara Grafik
Contoh maksimasi satu variabel:
Gambar
10.1
Maksimasi satu variabel
Contoh
maksimum dan minimum lokal dan global:
Gambar
10.2 Maksimum
dan minimum lokal dan global
Contoh perbedaan
antara persoalan optimasi dengan pencarian/penentuan akar persamaan:
Root
|
Root
|
Root
|
Maximum
|
Minimum
|
f'(x) = 0
f"(x) > 0
|
f'(x) = 0
f"(x) < 0
|
Gambar 10.3 Perbedaan
antara persoalan optimasi dengan pencarian/penentuan akar persamaan
Contoh
optimasi dua variabel (maksimasi):
Gambar 10.4 Optimasi
dua variabel (maksimasi)
10.2 Jenis Optimasi
10.2.1 Optimasi Satu
Variabel
Bagian
ini akan menerangkan cara untuk menentukan titik minimum atau maksimum dari
sebuah fungsi dengan satu variabel f(x). Seperti halnya dalam penempatan akar,
optimasi didalam satu dimensi dapat dibagi menjadi metode tertutup dan terbuka.
Ingin dicari harga x yang memberikan harga y maksimum (maksimasi) atau minimum(minimasi).
Dalam hal ini, x yang diperoleh merupakan nilai x optimum fungsi. Beberapa metode yang akan dibahas meliputi:
1.
Metode Golden Section
2.
Metode Newton
3.
Metode Interpolasi kuadrat
1.
Metode
Golden-Section Search
Golden section merupakan salah satu cara atau metode optimasi
numerik yang dapat diterapkan untuk fungsi yang bersifat unimodal. Kedua tipe optimasi, yaitu
maksimasi dan minimasi dapat diselesaikan dengan cara ini. Golden-section (search) method merupakan
metode optimasi satu variabel yang sederhana, dan mempunyai pendekatan yang mirip dengan metode bisection
dalam penentuan akar persamaan tak linier.
Tinjaulah fungsi f(x)
yang akan ditentukan maksimumnya, pada rentang x = xl dan x = xu (perhatikan Gambar 10.5).
Gambar
10.5 Metode
golden section
Mirip dengan bisection,
ide dasar metode ini adalah memanfaatkan nilai yang lama sebagai nilai yang
baru, secara iteratif. Sebagai akibatnya, rentang/ interval awal variabel yang
dipilih semakin lama akan semakin menyempit, karena ada sebagian sub-interval
variabel yang dieliminasi, hingga diperoleh tingkat konvergensi yang
diinginkan.
|
Karena: maka
Ambil kebalikannya dan
kemudian definisikan:
Maka
atau :
atau :
Sehingga :
Nilai akar positifnya adalah sebesar :
(Bilangan R
ini selanjutnya biasa disebut sebagai golden ratioatau golden
number).
Algoritma
(Kasus Maksimasi):
1. Mulailah
dari 2 nilai tebakan awal xl dan xu,
yang mengapit titik maksimum.
(Perhatikan ilustrasi grafik berikut ini!)
2. Tentukan
nilai x1 dan x2 di dalam rentang xl dan xu,
sesuai dengan golden ratio (R), yakni sebesar :
dengan:
3. Berdasarkan
harga f (x) pada 2 titik tersebut (x1 dan
x2),
maka diharapkan ada sebagian interval
yang
dapat dieliminasi, sehingga salah satu titik
lama
bisa dipakai lagi pada evaluasi langkah
berikutnya.
Jadi hanya diperlukan 1 titik baru.
Demikian
seterusnya.
Ada 2 kemungkinan kasus, yaitu:
(a) Jika: f(x1) > f(x2), maka: domain x antara xl
dan x2 dieliminasi
Dengan demikian: x2
lama = xl baru
x1 lama = x2 baru
xu lama = xu baru
x1 baru ditentukan
(b) Jika: f(x2) > f(x1), maka: domain x antara x1
dan xu dieliminasi
Dengan demikian: x1
lama = xu baru
x2 lama = x1 baru
xl lama = xl baru
x2 baru ditentukan
Catatan: Algoritma untuk kasus minimasi merupakan kebalikan
dari algoritma untuk kasus maksimasi
yang telah diuraikan tersebut di atas.
Contoh
soal:
Gunakan metode golden-section
search untuk menentukan maksimum dari fungsi:
Penyelesaian:
Secara grafik,
fungsi f (x) pada interval x sebesar 0 s.d. 4 ditunjukkan pada gambar berikut.
Perhatikanlah
bahwa nilai maksimum fungsi teramati di sekitar harga x = 1,5
Secara numerik,
dengan metode golden-section search, dapat dilakukan langkah-langkah
perhitungan sebagai berikut.
Iterasi pertama:
xl = 0 : f (xl) =
0
xu =
4 : f (xu) = -3,1136
x1
= xl + d = 0 + 2,4721 = 2,4721 : f (x1) = 0,6300
x2 = xu – d =
4 – 2,4721 = 1,5279 : f (x2) = 1,7647
Karena kasus ini merupakan persoalan maksimasi, dan: f (x2) > f (x1),
maka:
xl baru = xl lama
xu
baru = x1 lama
Dengan kata lain,
sub-interval x kanan (yakni
antara x1 dan xu) dieliminasi.
Iterasi kedua:
xl = 0 : f (xl) =
0
xu =
2,4721 : f (xu) = 0,6300
x1 = xl
+ d = 0 + 1,5279 = 1,5279 = x2 lama : f (x1) = 1,7647
x2
= xu – d = 2,4721 – 1,5279 = 0,9443 :
f (x2) = 1,5310
Karena kasus ini merupakan persoalan maksimasi, dan: f (x2) < f (x1), maka:
xl
baru = x2 lama
xu
baru = xu lama
Dengan
kata lain, sub-interval x kiri (yakni
antara xl dan x2) dieliminasi.
Cara perhitungan yang
sama/analog dapat dilakukan pada langkah iterasi berikutnya. Perhitungan dapat
dilakukan secara berulang-ulang hingga mencapai nilai toleransi yang
diinginkan. Perhatikanlah bahwa penyelesaian ini konvergen menuju nilai
maksimum yang sebenarnya (yakni pada x = 1,4276; dengan nilai maksimum f (x) =
1,7757).
Hasil-hasil perhitungan
selengkapnya (hingga langkah iterasi ke-17) disajikan pada tabel berikut ini:
i
|
x1
|
f(x1)
|
x2
|
f(x2)
|
x1
|
f(x1)
|
xu
|
f(xu)
|
D
|
1
|
0,0000
|
0,0000
|
1,5279
|
1,7647
|
2,4721
|
0,6300
|
4,0000
|
-3,1136
|
2,4721
|
2
|
0,0000
|
0,0000
|
0,9443
|
1,5310
|
1,5279
|
1,7647
|
2,4721
|
0,6300
|
1,5279
|
3
|
0,9443
|
1,5310
|
1,5279
|
1,7647
|
1,8885
|
1,5432
|
2,4721
|
0,6300
|
0,9443
|
4
|
0,9443
|
1,5310
|
1,3050
|
1,7595
|
1,5279
|
1,7647
|
1,8885
|
1,5432
|
0,5836
|
5
|
1,3050
|
1,7595
|
1,5279
|
1,7647
|
1,6656
|
1,7136
|
1,8885
|
1,5432
|
0,3607
|
6
|
1,3050
|
1,7595
|
1,4427
|
1,7755
|
1,5279
|
1,7647
|
1,6656
|
1,7136
|
0,2229
|
7
|
1,3050
|
1,7595
|
1,3901
|
1,7742
|
1,4427
|
1,7755
|
1,5279
|
1,7647
|
0,1378
|
8
|
1,3901
|
1,7742
|
1,4427
|
1,7755
|
1,4752
|
1,7732
|
1,5279
|
1,7647
|
0,0851
|
9
|
1,3901
|
1,7742
|
1,4226
|
1,7757
|
1,4427
|
1,7755
|
1,4752
|
1,7732
|
0,0526
|
10
|
1,3901
|
1,7742
|
1,4102
|
1,7754
|
1,4226
|
1,7757
|
1,4427
|
1,7755
|
0,0325
|
11
|
1,4102
|
1,7754
|
1,4226
|
1,7757
|
1,4303
|
1,7757
|
1,4427
|
1,7755
|
0,0201
|
12
|
1,4226
|
1,7757
|
1,4303
|
1,7757
|
1,4350
|
1,7757
|
1,4427
|
1,7755
|
0,0124
|
13
|
1,4226
|
1,7757
|
1,4274
|
1,7757
|
1,4303
|
1,7757
|
1,4350
|
1,7757
|
0,0077
|
14
|
1,4226
|
1,7757
|
1,4256
|
1,7757
|
1,4274
|
1,7757
|
1,4303
|
1,7757
|
0,0047
|
15
|
1,4256
|
1,7757
|
1,4274
|
1,7757
|
1,4285
|
1,7757
|
1,4303
|
1,7757
|
0,0029
|
16
|
1,4256
|
1,7757
|
1,4267
|
1,7757
|
1,4274
|
1,7757
|
1,4285
|
1,7757
|
0,0018
|
17
|
1,4267
|
1,7757
|
1,4274
|
1,7757
|
1,4278
|
1,7757
|
1,4285
|
1,7757
|
0,0011
|
Ket : Bagian yang diarsir merupakan nilai
x dan f(x) terbesar pada setiap langkah iterasi.
Catatan: Secara analitik, nilai maksimum fungsi dapat
ditentukan dengan cukup mudah, karena f(x) berbentuk persamaan yang mudah
diturunkan (atau ditentukan fungsi turunannya). Tentukan fungsi turunan pertama
dari f(x), dan selanjutnya tentukan nilai x yang membuat f’(x) = 0. Untuk
mengecek kebenaran kategori persoalan optimasinya (yakni apakah maksimum atau
minimum) pada nilai x yang ditinjau, tentukan nilai fungsi turunan kedua dari
f(x).
Efektivitas evaluasi dengan metode golden section:
Misal diinginkan pengecilan interval
sampai menjadi 0,001 dari semula, maka jumlah step yang diperlukan (N) adalah:
(0,618)N= 0,001
N =
14,3 ≈ 15
Jumlah
evaluasi = 2 + (N – 1) x 1 = 16
2.
Metode
interpolasi kuadrat
Metode interpolasi
kuadrat dapat digunakan untuk melakukan optimasi secara numerik. Hal ini
disebabkan oleh penggunaan polinomial orde-dua yang menghasilkan pendekatan
cukup baik terhadap bentuk f(x) di dekat titik optimumnya. (Perhatikan gambar di bawah ini)
Jika mula-mula kita
mempunyai tiga buah titik tebakan awal (yakni x0, x1, dan
x2) yang mengapit titik optimumnya, maka sebuah parabola dapat
di-fit-kan melalui ketiganya. Diferensiasikan persamaan yang diperoleh, set
hasilnya menjadi sama dengan nol, dan perkiraan x optimum dapat ditentukan
(dalam hal ini sebagai x3) sbb :
........ (10.2)
Penentuan x3
dilakukan
secara iteratif, melalui strategi yang sama dengan metode golden section,
hingga diperoleh penyelesaian yang konvergen.
Contoh
soal:
Gunakan metode
interpolasi kuadrat untuk menentukan maksimum dari fungsi:
dengan nilai-nilai awal x: x0
= 0; x1 = 1; dan x2 = 4
Penyelesaian:
Iterasi pertama:
x0 = 0 : f (x0) =
0
x1 = 1 : f (x1) =
1,5829
x2 = 4 : f (x2) =
-3,1136
Berdasarkan
nilai-nilai x0, f (x0), x1, f (x1),
x2, dan f (x2), maka x3 dapat dihitung sbb :
Nilai f (x) pada x3:
f (x3)
= 1,7691
Karena kasus ini merupakan persoalan maksimasi, dan:
f (x0) <f (x1)
< f (x3), serta: f (x3) > f (x2)
maka:
x0 lama dieliminasi
x2
baru = x2 lama
Dengan kata lain, sub-interval x kiri dieliminasi, atau
3 buah nilai x lama (yakni x1, x2, dan x3)
akan digunakan dalam perhitungan iterasi berikutnya.
Iterasi kedua:
x0 = 1 : f (x0) =
1,5829
x1 = 1,5055 : f (x1)
= 1,7691
x2 = 4 : f (x2) =
-3,1136
Berdasarkan nilai-nilai x0, f
(x0), x1, f (x1), x2, dan f (x2),
maka: x3 = 1,4903
Nilai f (x) pada x3: f (x3)
= 1,7714
Karena kasus ini merupakan persoalan maksimasi, dan:
f (x0) <f
(x3), serta: f (x3) > f (x1) > f (x2)
maka:
x2 lama dieliminasi
x0 baru = x0 lama
Dengan kata lain, sub-interval x kanan dieliminasi, atau
3 buah nilai x lama (yakni x0, x1,dan x3) akan
digunakan dalam perhitungan iterasi berikutnya.
Demikian seterusnya, untuk langkah
iterasi berikutnya. Perhitungan dapat dilakukan secara berulang-ulang hingga
mencapai nilai toleransi yang diinginkan. Perhatikanlah bahwa penyelesaian ini
konvergen menuju nilai maksimum yang sebenarnya (yakni pada x = 1,4276; dengan
nilai maksimum f(x) = 1,7757). Hasil-hasil perhitungan selengkapnya (hingga
langkah iterasi ke-5) disajikan pada tabel berikut ini:
i
|
x0
|
f(x0)
|
x1
|
f(x1)
|
x2
|
f(x2)
|
x3
|
f(x3)
|
1
|
0,0000
|
0,0000
|
1,0000
|
1,5829
|
4,0000
|
-3,1136
|
1,5055
|
1,7691
|
2
|
1,0000
|
1,5829
|
1,5055
|
1,7691
|
4,0000
|
-3,1136
|
1,4903
|
1,7714
|
3
|
1,0000
|
1,5829
|
1,4903
|
1,7714
|
1,5055
|
1,7691
|
1,4256
|
1,7757
|
4
|
1,0000
|
1,5829
|
1,4256
|
1,7757
|
1,4903
|
1,7714
|
1,4266
|
1,7757
|
5
|
1,4256
|
1,7757
|
1,4266
|
1,7757
|
1,4903
|
1,7714
|
1,4275
|
1,7757
|
3.
Metode
Newton
Metode
ini menggunakan pendekatan yang sama dengan metode Newton dalam penentuan akar
persamaan tak-linier, melalui pendefinisian fungsi:
g(x)
= f’(x) ......................................................................................... (10.3)
Karena pada kondisi optimum berlaku: f
'(x*) = g(x*)
= 0
(dengan x* menyatakan
nilai x optimum)
maka, nilai x*
dapat diperoleh secara iteratif sebagai berikut:
......................................................................... (10.4)
Contoh
soal:
Gunakan metode Newton untuk
menentukan maksimum dari fungsi:
dengan nilai awal x sebesar x0
= 2,5
Penyelesaian:
Pada metode Newton, fungsi turunan
pertama dan kedua harus dievaluasi terlebih dahulu. Untuk fungsi tersebut di
atas:
Iterasi pertama:
x0 =
2,5
(
)
(
)
Dengan demikian,
x1 dapat dihitung dengan cara sbb :
Cara perhitungan yang
sama/analog dapat dilakukan pada langkah iterasi berikutnya. Perhitungan dapat
dilakukan secara berulang-ulang hingga mencapai nilai toleransi yang
diinginkan. Perhatikanlah bahwa penyelesaian ini konvergen menuju nilai
maksimum yang sebenarnya (yakni pada x = 1,42755; dengan nilai maksimum f (x) =
1,77573). Hasil-hasil perhitungan selengkapnya (hingga langkah iterasi ke-5)
disajikan pada tabel berikut ini:
i
|
X
|
f(x)
|
f'(x)
|
f"(x)
|
0
|
2,5
|
0,571944
|
-2,10229
|
-1,39694
|
1
|
0,995082
|
1,578588
|
0,889853
|
-1,87761
|
2
|
1,469011
|
1,773849
|
-0,09058
|
-2,18965
|
3
|
1,427642
|
1,775726
|
-0,0002
|
-2,17954
|
4
|
1,427552
|
1,775726
|
-1,2E-09
|
-2,17952
|
5
|
1,427552
|
1,775726
|
0
|
-2,17952
|
10.2.2 Optimasi Banyak
Variabel
Misal diketahui
sebuah fungsi dengan banyak variabel sebagai
berikut:
Y = f(x1, x2,
x3, ....., xn) ..................................................................... (10.5)
Ingin dicari harga x1,
x2,
x3,
….., xnyang memberikan harga y
maksimum (maksimasi) atau minimum (minimasi). Pengelompokan metodenya secara
garis besar adalah: (1) non-gradientmethods, dan (2) gradient
methods.
Beberapa metode yang akan dibahas
meliputi:
1.
Direct
Method (Random Search)
Sesuai dengan namanya,
metode random search secara berulang-ulang mengevaluasi nilai fungsi
pada nilai-nilai variabel bebas tertentu (selected
values)secara acak (randomly).
Jika banyaknya sampel yang dicoba mencukupi, maka kondisi optimumnya akan
teramati, dan sebaliknya. Dengan demikian, metode ini tidak efisien…!
ü Metode
ini dapat diterapkan untuk fungsi yang discontinuous dan non-differentiable
sekalipun.
ü Pendekatan
ini pada umumnya akan menghasilkan
titik optimum global (bukan optimum lokal).
Contoh
soal:
Gunakan metode random
search untuk menentukan maksimum dari fungsi :
f (x, y)
= y − x − 2x2− 2xy − y2
jika domain nilai x dan y dibatasi pada:
x = -2 hingga 2; dan y = 1 hingga 3
Catatan: Nilai
maksimum fungsi ini adalah 1,25 pada x = -1 dan y = 1,5
Penyelesaian:
Random number generator,
yang dalam hal ini diwakili sebagai bilangan r, secara tipikal dinyatakan dalam
angka-angka di antara 0 dan 1.
Nilai x optimum di antara xl
dan xu secara acak (random)dapat
dinyatakan sebagai:
x = xl + (xu – xl)
r
Karena dalam hal ini: xl = -2
dan xu = 2, maka: x = (-2) + (2 – (-2)) r = -2 + 4 r
Dengan cara yang sama, nilai y optimum
di antara yl dan yu secara acak dapat dinyatakan sebagai:
y = yl + (yu – yl)
r
Karena dalam hal ini: yl = 1
dan yu = 3, maka: y = (1) + (3 – 1) r = 1 + 2 r
Dengan
mensubstitusikan nilai-nilai r yang memenuhi: 0 ≤ r ≤ 1
secara acak ke dalam :
x = -2 + 4 r dan
y = 1 + 2 r
maka dapat
diperoleh nilai maksimum fungsi ini sebesar 1,25 pada: x = -1 dan y = 1,5.
Sebagai contoh, dengan
mengambil nilai-nilai r sebesar 0; 0,25; 0,5; 0,75; dan 1; serta menerapkannya
secara acak terhadap persamaan x dan y sebagai fungsi r tersebut di atas, maka
diperoleh hasil-hasil perhitungan sebagai berikut :
x
|
Y
|
f(x,y)
|
-2
|
1
|
-2
|
-2
|
1,5
|
-0,75
|
-2
|
2
|
0
|
-2
|
2,5
|
0,25
|
-2
|
3
|
0
|
-1
|
1
|
1
|
-1
|
1,5
|
1,25
|
-1
|
2
|
1
|
-1
|
2,5
|
0,25
|
-1
|
3
|
-1
|
0
|
1
|
0
|
0
|
1,5
|
-0,75
|
0
|
2
|
-2
|
0
|
2,5
|
-3,75
|
0
|
3
|
-6
|
1
|
1
|
-5
|
1
|
1,5
|
-6,75
|
1
|
2
|
-9
|
1
|
2,5
|
-11,75
|
1
|
3
|
-15
|
2
|
1
|
-14
|
2
|
1,5
|
-16,75
|
2
|
2
|
-20
|
2
|
2,5
|
-23,75
|
2
|
3
|
-28
|
2.
Metode
Gradien (Metode Steepest Ascent)
Merupakan jenis metode gradien yang paling sederhana.
a. Terminologi:
steepest
ascent untuk pencarian maksimum fungsi
steepest
descent untuk
pencarian minimum fungsi
b. Prinsip pencarian optimum:
Dilakukan serangkaian
proses transformasi untuk mengubah sebuah
fungsi dengan banyak variabel (multi-dimensional function) menjadi sebuah fungsi dengan variabel tunggal (one-dimensional function),
berdasarkan gradien arah
pencarian. Langkah
pencarian optimum ini selanjutnya dilakukan secara berulang-ulang (iteratif), hingga
diperoleh tingkat konvergensi yang diinginkan.
Pencarian optimum:
Sebagai ilustrasi,
tinjaulah fungsi dua variabel f(x,y) yang
akan ditentukan titik maksimumnya. (lihat
gambar berikut ini)
Berdasarkan nilai awal
x = x0 dan y = y0, dapat ditentukan nilai gradien (atau arah steepest ascent)-nya, yakni sebesar h0.
Berdasarkan nilai h0, nilai maksimum fungsi dapat ditentukan,
yaknipada titik “1”. Demikian
seterusnya, proses ini dilakukan berulang-ulang hingga diperoleh
titikoptimum sesungguhnya.
Secara numerik:
Misal untuk sebuah
fungsi dua variabel: f(x,y) yang
akan dicari titik optimumnya, dengan nilai
awal: x = x0dan y = y0,
maka pada langkah iterasi pertama, nilai x dan y yang baru dapat
ditentukandengan:
dan
.......................................... (10.6)
Dengan :
dan
merupakan turunan parsial fungsi f(x,y)
masing-masing terhadap x dan y.
Dalam hal ini, vektor gradien fungsinya dinyatakan sebagai:
................................................................................ (10.7)
Pada kasus ini, sebuah fungsi 2 variabel
dalam x dan y, f(x,y), ditransformasikan menjadi sebuah fungsi satu variabel
dalam h, g(h).
Nilai x dan y yang diperoleh pada
langkah iterasi ini selanjutnya menjadi x0 dan y0 pada langkah iterasi
berikutnya. Demikian seterusnya.
Contoh
soal:
Gunakan metode steepest ascending atau
ascent untuk menentukan maksimum dari fungsi:
f (x, y)
= 2 xy + 2 x − x2− 2 y2
dengan nilai awal x dan y sebesar: x0
= -1 dan y0 = 1
Penyelesaian:
Turunan parsial
fungsi di atas dapat dituliskan sebagai:
dan
Iterasi pertama:
Nilai awal: x0 = -1; y0
= 1
Pada x0 dan y0: f
(x, y) = 2
(−1) (1) + 2 (−1) − (−1)2 − 2 (1)2 = −7
Evaluasi nilai
turunan parsial fungsi pada x0 dan y0:
maka, vektor
gradiennya dapat dituliskan sebagai: ∇f = 6
− 6
Substitusikan nilai x dan y (sebagai
fungsi h) ke dalam f (x,y) di atas:
f
(x,
y) = 2
xy + 2
x − x2− 2 y2
f
(x,
y) = 2
(−1+ 6h) (1− 6h) + 2 (−1+ 6h) − (−1+ 6h)2− 2 (1− 6h)2= g(h)
f
(x,
y) = −180
h2+ 72
h − 7
= g(h)
Fungsi turunan pertama dari g(h): g'(h)
= −360 h + 72
Nilai h yang membuat g(h) maksimum
dicapai pada saat g’(h) = 0, yakni sebesar:
g'(h)
= −360 h + 72 = 0
360
h = 72
h
= 0,2
Dengan demikian, nilai x baru dan y baru
dapat dihitung sebagai berikut:
x
= −1+ 6h = −1+ 6 (0,2) = 0,2
y
=1− 6h =1− 6 (0,2) = −0,2
Cara perhitungan yang sama dapat
dilakukan untuk langkah-langkah iterasi berikutnya. Hasil perhitungan
selengkapnya (hingga langkah iterasi ke-12) disajikan pada tabel berikut ini:
i
|
xi
|
yi
|
(df/dxi)
|
(df/dyi)
|
h
|
xi+1
|
yi+1
|
f(xi,yi)
|
0
|
-1
|
1
|
6
|
-6
|
0,2
|
0,2
|
-0,2
|
-7
|
1
|
0,2
|
-0,2
|
1,2
|
1,2
|
1
|
1,4
|
1
|
0,2
|
2
|
1,4
|
1
|
1,2
|
-1,2
|
0,2
|
1,64
|
0,76
|
1,64
|
3
|
1,64
|
0,76
|
0,24
|
0,24
|
1
|
1,88
|
1
|
1,928
|
4
|
1,88
|
1
|
0,24
|
-0,24
|
0,2
|
1,928
|
0,952
|
1,986
|
5
|
1,928
|
0,952
|
0,048
|
0,048
|
1
|
1,976
|
1
|
1,997
|
6
|
1,976
|
1
|
0,048
|
-0,048
|
0,2
|
1,986
|
0,990
|
1,999
|
7
|
1,986
|
0,99
|
0,010
|
0,010
|
1
|
1,995
|
1
|
2
|
8
|
1,995
|
1
|
0,010
|
-0,010
|
0,2
|
1,997
|
0,998
|
2
|
9
|
1,997
|
1
|
0,002
|
0,002
|
1
|
1,999
|
1
|
2
|
10
|
1,999
|
1
|
0,002
|
-0,002
|
0,2
|
1,999
|
1
|
2
|
11
|
1,999
|
1
|
4E-04
|
0,000
|
1
|
2,000
|
1
|
2
|
12
|
2
|
1
|
4E-04
|
0,000
|
0,2
|
2,000
|
1
|
2
|
Berdasarkan hasil-hasil tersebut di
atas, terlihat bahwa penyelesaian bersifat konvergen menuju ke nilai x optimum
dan y optimum yang sebenarnya, yakni x = 2 dan y = 1, dengan nilai f (x,y)
maksimum sebesar 2.
Catatan:
Anda dapat mengecek hasil ini secara
analitik melalui telaah turunan fungsinya.
Turunan parsial
fungsi ini dapat dituliskan sebagai:
dan
Nilai optimum x dan y dicapai pada
saat
dan
Dapat ditentukan dengan
mudah, nilai-nilai tersebut adalah: x = 2 dan y = 1. Kriteria optimumnya (local minimum,local maximum, atau
saddle point)dapat dicek
melalui penggunaan turunan-kedua fungsi dan dievaluasi pada nilai x dan y
tersebut. Dalam hal ini, turunan parsial tersebut adalah :
Nilai determinan matriks Hessian
(H) dari f :
Karena
nilai det(H) > 0 dan
,
maka
terbukti bahwa titik (2, 1) merupakan titik maksimum lokal.
10.3 Contoh Kasus dalam Bidang Teknik
Kimia
Para
engineer dalam bidang petro maupun oleokimia seringkali menghadapi permasalahan
umum dalam merancang wadah untuk memindahkan liquid ataupun gas. Misalkan Anda
diminta untuk menentukan dimensi dari tangki silinder yang berukuran kecil
untuk memindahkan limbah beracun yang akan dipasang di bagian belakang sebuah
truk pickup. Secara keseluruhan, tujuan dari merancang tangki tersebut untuk
meminimalisir biaya pembuatan tangki. Akan tetapi, disamping biaya, kita juga
harus memastikan dimensi yang dirancang memenuhi kapasitasyang diperlukan dan
tidak melebihi dimensi bagian belakang truk. Perlu juga diperhatikan ketebalan
tangki yang dirancang harus memenuhi spesifikasi yang tentukan karena tangki
tersebut merupakan wadah untuk limbah beracun. Skemadari
tangkidan pelindungnya ditunjukkan pada gambar.
Seperti dapat dilihat, tangki terdiri dari sebuah
silinder dengan
tutup bagian atas dan bawah dilas.
Penghitungan
biaya tangki melibatkan dua komponen: 1. biaya bahan, yang didasarkan ada berat, dan 2. Beban pengelasan berdasarkan
panjang lasan. Perhatikan bahwa yang terakhir melibatkan pengelasan baik interior
dan eksterior lapisan di mana lempeng terhubung dengan silinder. data yang
diperlukan untuk problem tersebut diringkas dalam tabel.
Tabel
10.1 Parameter untuk
menentukan dimensi optimal dari tangki berbentuk silinder yang berfungsi untuk
memindahkan limbah beracun
Parameter
|
Simbol
|
Nilai
|
Satuan
|
Volume yang dibutuhkan
|
Vo
|
0,8
|
m3
|
Ketebalan
|
T
|
3
|
cm
|
Densitas
|
Ρ
|
8000
|
kg/m3
|
Panjang selimut
|
Lmax
|
2
|
m
|
Lebar selimut
|
Dmax
|
1
|
m
|
Biaya material
|
Cm
|
4,5
|
$/kg
|
Biaya pengelasan
|
cw
|
20
|
$/m
|
Penyelesaian:
Tujuan
dari contoh kasus ini adalah untuk merancang tangki dengan biaya minimum.
Biaya ini berhubungan dengan variabel desain (panjang
dan diameter) karena mereka mempengaruhi massa tangki dan panjang
las. Selanjutnya, masalah ini terkendala
karena tangki
harus (1)
sesuai dengan ukuran bak truk dan (2)
membawa volume material yang diperlukan.
Biaya terdiri
dari biaya baha pembuatan tangki dan biaya pengelasan. Sehingga tujuan dari
meminimalisir biaya tersebut dapat dirumuskan menjadi
C = cm m + cw lw ................................................................................ (10.8)
Dimana C = biaya
($), m = massa (kg), lw = panjang pengelasan (m), serta cm
dan cw = faktor biaya untuk massa material yang digunakan ($/kg) dan
panjang pengelasan ($/m).
Selanjutnya,
rumuskan bagaimana massa dan panjang pengelasan dihubungkan ke dimensi dari
tangki yang akan dirancang. Pertama, massa dapat dihitung karena volume material
dapat diketahui dari sensitas material. Volume material digunakan untuk membuat
bagian samping dari tangki (berbentuk silinder) dengan rumus berikut:
Volume untuk
piringan bundar dapat dihitung
Kemudian, massa
material dihitung dengan persamaan
(8.9)
dimana ρ =
densitas (kg/m3)
panjang
pengelasan untuk tiap piringan sama dengan keliling bagian dalam dan luar
lingkaran. Untuk kedua piringan tersebut, total panjang pengelasan menjadi
............................... (10.10)
masukkan nilai D
dan L (ingat bahwa nilai ketebalan t adalah tetap), persamaan (10.8) sampai (10.10) digunakan untuk menghitung biaya. Persamaan (10.9) dan (10.10) disubstitusikan ke persamaan
untuk membuat persamaan non linear yang tidak diketahui. Selanjutnya, dapat
dirumuskan kendala dalam
contoh kasus. Pertama,kita
harusmenghitungberapa volumetangkiyang dibutuhkan.
Nilai ini harus
sama dengan volume yang diinginkan. Salah satu kendala dalam contoh kasus
tersebut adalah
Dimana Vo adalah
volume yang diinginkan (m3)
Kendala selanjutnya diselesikan dengan memastikan bahwa tangki akan cocok dalam dimensi bak truk.
L
≤ Lmax
D
≤ Dmax
Problem dari
contoh kasus ini menjadi lebih spesifik. Substitusikan nilai dari Tabel 8.1,
kemudian dapat disimpulkan bahwa
Cmax
= 4,5m + 20lw
L ≤ 2
D ≤ 1
dimana
dan
lw
= 4π (D + 0,03)
Masalah sekarang dapat diselesaikan
dalam beberapa
cara. Namun, pendekatan yang
sederhana untuk masalah sebesar ini adalah dengan
menggunakan
komputer (Excell).
Untuk kasus yang
ditampilkan,
kita memasuki batas atas untuk D dan L.Untuk
kasus ini, volume lebihdari yang
dibutuhkan
(1,57>0,8).
10.4 Penutup
Optimasi merupakan suatu proses untuk mencari
kondisi yang optimum, dalam arti paling menguntungkan. Optimasi bisa berupa maksimasi atau minimasi. Jika berkaitan
dengan masalah keuntungan, maka keadaan optimum adalah keadaan yang memberikan
keuntungan maksimum (maksimasi).
Jika berkaitan dengan masalah pengeluaran/pengorbanan, maka keadaan optimum
adalah keadaan yang memberikan pengeluaran/pengorbanan minimum (minimasi).
Hal-hal penting dalam
studi optimasi meliputi:
3.
Fungsi
objektif dan decision variables
4.
Kendala (constraints)
Secara umum, fungsi
yang akan dimaksimumkan atau diminimumkan disebut fungsi objektif (objective
function), sedangkan harga-harga yang berpengaruh dan bisa dipilih
disebut variabel perubah atau decision
variable.
Secara analitik, nilai
maksimum atau minimum dari suatu persamaan:y = f (x) dapat
diperoleh pada harga x yang memenuhi:
Untuk fungsi yang sulit
diturunkan atau mempunyai turunan yang sulit dicari akarnya, proses optimasi
dapat dilakukan secara numerik.
DAFTAR PUSTAKA
Budi, N.
1999. Modul Metode Numerik.
Politeknik Elektronika Negeri Surabaya. ITS
Chapra,
S.C., and Canale, R. P. 1998, Numerical Methods for Engineers. McGraw-Hill.
Kubicek,
Milan. et al. 2005. Numerical Methods And Algorithms. Praha
Mark
E. Davis. 2001. Numerical Methods &
Modeling for Chemical Engineers. John Miley and Sons.California Isnstitute
of Technology.
Riggs,
B.J.,1988. An introduce to numerical
methods for chemical engineers. Texas Tech Unviversity Press, Texas.
Smith,
M.J., Ness, V.C.H., Abbott, M.M., 2001. Chemical
Engineering Thermodynamics. McGraw Hill, Singapore.
Steven
C. Chapra & Raymond P. Canale. Metode
Numerik untuk Teknik dengan Penerapan pada Komputer Pribadi, UI-Press,
Jakarta, 1991.
Suryadi
H.S.1990. Pengantar Metode Numerik,
Seri Diktat Kuliah, Gunadarma.