OPTIMASI (Pemrograman Non Linear)

OPTIMASI (Pemrograman Non Linear) 3 SKS – PILIHAN

Arrival Rince Putri, 2013

1

Silabus

I.

Pendahuluan 1. Perkuliahan: Silabus, Referensi, Penilaian 2. Pengantar Optimasi 3. Riview Differential Calculus

II.

Dasar-Dasar Pemrograman Non Linier

III.

Model-Model Pemrograman Non Linier


2

Silabus

IV. Pemrograman Non Linier Tanpa Kendala V.

Pemrograman Non Linier Berkendala

VI. Optimasi Kuadrat Terkecil


3

Referensi 1.

A.L. Peressini, F.E. Sullivan, and J.J. Uhl, Jr, The Mathematics of Non Linear Programming, SpringerVerlag (1998)

2.

Griva, I., Nash, S. G., Sofer, A., Linear and Non Linear Optimization, SIAM, Philadelphia, 2009

3.

Winston, W.L., Operation Research : Applications and Algorithms, Brooks/Cole, USA, 2004.


4

Evaluasi Dan Penilaian

Penilaian: UAS TUGAS KELOMPOK KEHADIRAN


: 50% : 40% : 20%

5

Pengantar Optimisasi

Optimisasi – Definisi Umum  Optimisasi mencakup penentuan cara terbaik untuk melakukan sesuatu.  Optimisasi merupakan proses untuk menentukan himpunan kondisi yang diperlukan untuk mencapai hasil terbaik dengan situasi yang diberikan.


6

Penerapan Metode Optimisasi •

•

Sains, Engineering, Matematika, Ekonomi, Komersial. Contoh persoalan optimisasi : - Perancangan reaktor kimia. - Perancangan enjin pesawat dan struktur pesawat. - Perancangan struktur bangunan, jembatan. - Alokasi sumber, penjadwalan, komposisi produksi, persediaan. - Analisis numerik.


7

Elemen Model Optimisasi •

•

•

Fungsi tujuan (objective function) - Merupakan pernyataan tujuan secara matematik yang akan dioptimisasi, dapat berupa : * Kuantitas yang dihasilkan. * Keuntungan dari suatu sistem operasi. Fungsi pembatas (constraint function) - Variabel yang memiliki daerah kerja. - Hubungan berbagai hal yang dibatasi. Variabel keputusan (decision variables) - Merupakan besaran yang dapat berubah pada sistem operasinya, - Varibel dapat memiliki daerah kerja (batasan).


8

Klasifikasi Model Optimisasi Karakteristik

Properti

Banyak variable keputusan Satu Tipe variable keputusan Tipe fungsi Banyak fungsi objektif Formulasi masalah

Klasifikasi Univariat

Lebih dari satu

Multivariat

Kontinu

Kontinu

Beberapa integer

Integer atau diskret

Linier

Linier

Beberapa nonlinier

Nonlinier

Satu

Single

Lebih dari satu

Multiple

Dengan kendala

Berkendala

Tidak dengan kendala Tak berkendala Kondisi data input

Diketahui

Deterministik

Tidak diketahui

Stokastik


9

Riview Differential Calculus

Arrival Rince Putri, 2013 Arrival Rince Putri, 2013

10


11


12


13

Dasar-Dasar Pemrograman NonLinier Non-Linear Programming (NLP) • Berkendala / Constrained NLP • Tak berkendala / Unconstrained NLP Dalam banyak kasus real baik ekonomi maupun teknologi, fungsi tujuan / kendala adalah nonlinier, yang dapat berbentuk variabel berpangkat, logaritma, eksponensial dan bentuk lain yang bukan linier.


14

Contoh Misalkan h(x) adalah harga pada tingkat penjualan x. K adalah profit/ keuntungan, dihitung dari pendapatan dikali penjualan dikurangi dengan ongkos produksi dan distribusi, ditulis K(x) = x . h(x) – c(x) ; K nonlinier. Permasalahan: memaksimumkan profit dengan batasan sumber-sumber yang diperlukan untuk menghasilkan suatu produk, dimana terdapat elastisitas harga, jumlah yang dapat dijual berbanding terbalik dengan harga yang diberikan (lihat gambar). Arrival Rince Putri, 2012

15

Jika industri tersebut menghasilkan n jenis produk dan apabila xj unit produk dijual (j = 1,2, …, n), maka fungsi tujuan akan menjadi : F ( x)   K j x j  n

j 1

dimana Kj adalah keuntungan (profit) produk ke-j dalam tingkat xj. Penjumlahan ini adalah suatu jumlah fungsi-fungsi nonlinier. Bentuk nonlinier juga muncul pada kendala-kendala.


16

Ilustrasi Grafik Contoh 1 : Jika KL unit produk dapat dihasilkan dengan K sumber pertama (modal) dan L orang pekerja dengan harga sumber pertama Rp 4/unit dan pekerja di bayar Rp 1/orang. Modal yang tersedia Rp 8, maka formulasi problem dengan memaksimumkan jumlah produk yang di buat adalah : Maks :Z=K.L Kendala : 4K + L ≤ 8 K, L ≥ 0 Arrival Rince Putri, 2012

17

L

8

Optimal : K = 1, L = 4, Z = 4

4

Z=4 Z=2 Z=1 1


2

K

18

Contoh 2 : Min : Z = (x – 3)2 + (y – 4)2 Kendala : x ≤ 3 y ≤ 2 y

Z=1

Z=4 4

3

2

Optimal, x=3, y=2; Z=4

x 3


19

Bentuk Umum NLP : Z = f (x1, x2, …, xn) : gj (x1, x2, …, xn) ≤ (atau ≥ atau = ) bj ; j = 1, 2, …, m Dimana f, gj diantaranya adalah fungi nonlinier. Jika NLP diatas dimana gj ≠ ø ; j = 1, 2, …, m , maka nilai NLP tersebut dinamakan NLP berkendala (constrained), dan jika gj = ø ; j = 1, 2, …, m , maka disebut NLP tak berkendala (unconstrained). Maks/Min Kendala

Daerah layak (feasible region) dari NLP sama saja dengan LP biasa. Suatu titik di dalam suatu daerah layak, dimana f  x   f x , x pada daerah layak adalah optimal untuk kasus maksimasi (dan “ ≤ ” untuk kasus minimasi). 


20

Pemrograman Non Linier Berkendala NLP n Variabel dengan Kendala = (Pengali Lagrange) Problem : Max/Min : f (x1, x2, …, xn) Kendala : gi(x1, x2, …, xn) = bi ;

.....(3) i = 1,2,…,m

Jika terdapat 1 , 2 ,..., m sedemikian sehingga n L (x1, x2, …, xn, 1 , 2 ,..., m ) = f (x1, x2, …, xn) +  i bi  g x1 , x2 ,..., xn   0 i 1

maka :

L L L L L L   ...     ...  0 x1 x2 xn1 1 2 m Arrival Rince Putri, 2012

21

Teorema : 1. Problem (3) max, f concav, semua kendala linear, (x1, x2, …, xn) solusi optimal 2. Problem (3) min, f covex, semua kendala linear, (x1, x2, …, xn) solusi optimal Variabel i sebagai harga bayangan dari konstrain ke-i. Bila sisi kanan dari konstrain ke-i dinaikkan dengan sejumlah kecil  (pada masalah max atau masalah min), maka nilai fungsi objektif optimal untuk (3) akan naik dengan pendekatan i Arrival Rince Putri, 2012

22

Contoh : Sebuah perusahaan berencana untuk mengeluarkan biaya $10.000 untuk iklan, yaitu $3.000 / menit untuk iklan di televisi dan $1.000 / menit untuk iklan di radio, pendapatannya dalam $1.000 diberikan oleh

f x, y   2 x  y  xy  8x  3 y 2

2

Bagaimana perusahaan dapat memaksimalkan pendapatannya?


23

Max Kendala

: Z  2 x 2  y 2  xy  8x  3 y : 3x + y = 10

Lx, y, z   2x 2  y 2  xy  8x  3 y   10  3x  y  L L L Kita set :    0 x y 

L Menghasilkan :  4 x  y  8  3  0 x L  2 y  x  3    0 y L  10  3x  y  0 

Subsitusi persamaan-persamaan di atas, sehingga didapatkan : x = 69/28, y = 73/28 Arrival Rince Putri, 2012

24

Hessian untuk f(x,y) adalah :  4 1  H ( x, y )     1  2

Karena semua principal minor pertama (yaitu: -4 dan -2) adalah negatif dan principal minor kedua (yaitu: 7) > 0, maka f(x,y) adalah concav. Konstrain adalah linear, sehingga dari teorema memperlihatkan bahwa pengali Lagrange menghasilkan solusi optimal terhadap NLP. Jadi perusahaan harus membeli 69/28 menit waktu televisi dan 73/28 menit waktu radio. λ = ¼ artinya bahwa perusahaan Mengeluarkan ekstra  (ribuan) untuk  yang kecil, yang akan menaikkan pendapatan perusahaan sebesar $ 0,25  (dalam ribuan). Arrival Rince Putri, 2012

25

Tugas : Tentukan titik ekstrim dan jenisnya: 1. Min : f(x,y) = 2x2 + y2 Kendala : x + y = 10

2. Min : f x1 , x2 , x3   x1  4 x2  16 x3 Kendala : x1 + x2 + x3 = 5 3


2

26

Pemrograman NonLinier Tanpa Kendala NLP Satu Variabel

Bentuk Umum : Max/Min : Z = f(x) (1) Kendala : x є [a, b] Jika b  +∞, daerah yang layak untuk NLP pada persamaan (1) adalah x ≥ a. Jika a  -∞, daerah yang layak untuk NLP pada persamaan (1) adalah x ≤ b.


27

a

b


28

a. Max f(x) Kendala x є (-∞, b]

b. Min f(x) Kendala x є [a, +∞)


29

Terdapat tiga tipe titik-titik dimana bentuk umum NLP pada persamaan (1) dapat memiliki nilai maksimum / minimum lokal (titik ini disebut kandidat ekstrim), yaitu : Kasus 1 : titik dimana a < x < b, dan f’(x) = 0 (disebut titik stationer dari f(x)) Kasus 2 : titik dimana f’(x) tidak ada Kasus 3 : ujung selang dari interval [a, b]

Titik-titik ekstrim (max/min) sebagaimana dalam kalkulus : 1. f’(x) = 0 2. Titik-titik ujung x = a dan x = b 3. f’(x) tidak ada


30

Contoh : 1. Problem NLP Kendala

: Max : f(x) = 5x – x2 : x є [0, 10]

Uji : 1. f’(x) = 5 – 2x = 0 , x = 2,5 є [0, 10] f(x=2,5) = 6,25 2. f’(x) = 5 – 2x, f’(x) ada x є [0, 10] Maka kasus f’(x) tidak ada, tidak ada 3. x = 0  f(0) = 0 x = 10  f(10) = -50 Jadi karena problem max, maka solusi x = 2,5 dengan nilai max = 6,25


31

2. Problem NLP

: Max Kendala

: f(x) = x2 + 2x : -3 ≤ x ≤ 5

Uji : 1. f’(x) = 2x + 2= 0 , x = 1 є [-3, 5] f(x= -1) = -1 2. f’(x) tidak ada, tidak ada 3. x = -3  f(-3) = 3 x = 5  f(5) = 35 Jadi karena problem max, maka solusi x = 5 dengan nilai max = 35 Arrival Rince Putri, 2012

32

3. Problem NLP : Max Kendala

: Z = x - ex : -1 ≤ x ≤ 3

Uji : 1. f’(x) = 1 – ex = 0 , ex = 1 x = 0 є [-3, 5] f(x= 0) = -1 є [-1, 3] 2. f’(x) tidak ada, tidak ada 3. x = -1  f(-1) = -1 – 1/e ≈ -1,333 x = 3  f(3) = 1 – e3 ≈ - 17


33

NLP n Variabel

Bentuk Umum Kendala Asumsi

: Max/Min : Z = f (x1, x2, …, xn) : (x1, x2, …, xn)   b …(2) : turunan parsial pertama dan kedua ada dan kontinu pada semua titik.


34

Teorema :  f x  Jika x adalah ekstrim local untuk problem (2), maka x  0 i i Kondisi keekstriman titik x diuji dengan melibatkan matrik Hessian untuk menentukan apakah x ekstrim max local (cekung / concav) atau min local (cembung / convex). Teorema : 1. Jika H ( x ) ≥ 0  cembung  x min local 2. Jika H( x ), bertanda (-1)k  cekung  x max local 3. Jika H( x ) tidak memenui (1) dan (2), maka ekstrim x tidak max / min. Arrival Rince Putri, 2012

35

Dasar-Dasar Pemrograman NonLinier Convex Set (Himpunan Convex/Daerah Cembung) Definisi : Suatu himpunan convex adalah suatu koleksi titik-titik sedemikian sehingga untuk setiap pasangan titik-titik dalam koleksi itu, keseluruhan segmen garis yang menghubungkan setiap dua titik ini juga di dalam koleksi. Cara menguji suatu kurva dikatakan convex set, yaitu : • Ambil 2 titik (di dalam/di batas) kurva • Semua titik pada garis yang menghubungkan 2 titik tersebut semuanya berada di kurva. Arrival Rince Putri, 2012

36

Contoh : c b

a e

d

A

B

C

D

A : convex set B : convex set C : convex set D : bukan convex set NLP  daerah solusinya harus convex set ( supaya hasilnya optimal)


37

Fungsi Convex (Cembung) dan Fungsi Concave (Cekung) Dalam kalkulus dikenal fungsi dimana nilai kritisnya diuji dengan turunan kedua, jika xo adalah titik kritis pada Df dan f”(xo) ≤ 0, maka xo adalah titik kritis maksimum pada Df dan bila f”(xo) ≥ 0, maka xo adalah titik kritis minimum pada Df, dan apabila : f” (x) =

d2 f 0 dx 2

,

x  D f

maka f dikatakan fungsi cekung (concave)

pada Df d2 f  0 , x  D f maka f dikatakan fungsi cembung (convex) f” (x) = 2 dx

pada Df Arrival Rince Putri, 2012

38

Akibatnya, fungsi linier (f”(x) = 0 x ) dikatakan cembung sekaligus cekung. Fungsi cembung biasa dinamakan juga cekung ke atas dan fungsi cekung sebagai cekung ke bawah.


39

Andaikan sebarang fungsi satu variabel f(x) yang memiliki turunan kedua pada setiap nilai x pada daerah definisinya, maka f(x) pada Df adalah : 1. Cembung (convex)

d2 f   0 x  D f 2 dx

2. Cembung sejati

d2 f  2  0 x  D f dx

3. Cekung (concave)

d2 f   0 x  D f dx 2

4. Cekung sejati

d2 f  2  0 x  D f dx


40

Contoh:

Fungsi cekung

Fungsi cembung sejati


Fungsi cekung sejati

41

Fungsi cekung sekaligus cembung

Fungsi bukan cekung dan bukan cembung


42

Uji kecembungan fungsi dua variabel

Kuantitas  2 f x1 , x 2   2 f x1 , x 2    2 f x1 , x 2  .   2 2 x1 x 2  x1 x 2 

2

Cembung

Cembung Sejati

Cekung

Cekun g Sejati

≥0

>0

≥0

>0

≥0

>0

≤0

<0

≥0

>0

≤0

<0

 2 f x1 , x 2 

x1 2  f x1 , x 2  2

x 2

Nilai-nilai (x1,x2)

2

Semua nilai f yang mungkin


Untuk ilustrasi uji kecembungan fungsi dua variabel, misalkan : f ( x1, x2 )  ( x1  x2 )2  x12  2 x1x2  x22 Dengan demikian : 2 2 2 2 (1)  f x1, x2  .  f x1, x2     f x1, x2   2(2)  (2)2  0 x1

2

x2

2

(2)

 2 f  x1 , x2   20 2 x1

(3)

 2 f  x1 , x2  20 2 x2

 

x1x2

 

maka ketiga kondisi memenuhi tanda ≥, jadi f(x 1,x2) adalah cembung, dan bukan cembung sejati. Arrival Rince Putri, 2012

44

Untuk memperumum ini, dan untuk fungsi yang memiliki lebih dari dua variabel, sebagai contoh dalam ungkapan matematika, f ( x1 , x2 ,..., xn ) adalah cembung jika dan hanya jika matriks Hessian nxn adalah semi definit positif untuk semua nilai (x1, x2, …,xn) yang mungkin, atau bisa dinyatakan bahwa : jika terdapat 2 variabel atau lebih gunakan Hessian Matriks dan ditulis :  2 f  H (x1, x2, …, xn)    i, j ; i, j  1,2,..., n  x i x j  nxn


45

Definisi : Matriks Hessian dari f (x1, x2, …, xn) adalah matriks nxn, dimana elemen ke-ij adalah 2 f xi x j

Contoh : f (x1, x2, x3) = 2x12 + x22 + 2x3  4 0 0 H x1 , x 2 , x 3   0 2 0 0 0 0 3 x3


46

Teorema 1 : Determinan minor utama (Leading Principle Minor) yang ke-k adalah determinan matrik n x n dengan menghapus (n – k) baris dan kolom terakhir.  4 0 0 0 2 0   H x , x , x  Contoh : 1 2 3   0 0 0


47

 4 0 0 0 2 0   0 0 0

, determinan minor utama ke-1 = 4

Ket : bilangan yang digaris bawahi yaitu 2 (n – k = 3 – 1) baris dan kolom terakhir dihapus sehingga yang tersisa adalah 4


48

Teorema 2 : Principal Minor (minor utama) ke-k dari matrik n x n adalah determinan dari matrik k x k yang diperoleh dengan menghapus n – k baris dan n – k kolom yang sesuai dengan matrik.  2  1    1  4  

Contoh : H ( x1 , x 2 )  

Principal minor ke-1 adalah : -4 dan -2 (n=2, k=1, n – k = 1) Principal minor ke-2 adalah : 7 (n=2, k=2, n – k = 0)


49

Teorema 3 : Andaikan f (x1, x2, …, xn) mempunyai turunan parsial kedua kontinu untuk setiap x = (x1, x2,…, xn) di S , maka f (x1, x2, …, xn) adalah suatu fungsi cembung / cekung pada S jika dan hanya jika untuk setiap x є S semua principal minor dari matrik H adalah non negatif (convex) / matrik H yang ≠ 0 mempunyai tanda (-1)k untuk principal minor ke-k (concave).


50

Contoh : 2 0  1. H ( x1 , x 2 )    0  2  

Principal minor ke-1 adalah : 2 dan -2 (tanda (-1)1 : negatif) Principal minor ke-2 adalah : -4 (tanda (-1)2 : positif) Jadi : karena tidak ada yang sesuai dengan teorema 3, maka f tidak cembung dan tidak cekung.


51

6 x1 2 2. H ( x1 , x 2 )    2 2  

Principal minor ke-1 adalah : 2 dan 6x1 Principal minor ke-2 adalah : 12x1 – 4 Karena sudah ada 2 yang positif (2 dan 6x1), maka yang dapat kita tentukan hanya selang untuk f cembung / convex, yaitu : 6x1  0 dan 12 x1  4  0  x1  0 dan x1  1/ 3  x1  1/ 3 sehingga ( x1, x2 x1  1/ 3) f cembung / convex.


52

Soal-soal 1. f x1 , x 2   x1  2 x1 x 2  x 2 , 2

2

x1 , x2  di S  

2

 2 2 H ( x1 , x 2 )     2 2

Karena semua principal minor (ke-1 adalah 2 dan 2, yang ke-2 adalah 0) merupakan non negatif, maka f adalah fungsi cembung pada R2.


53

2. f x1 , x 2    x1  x1 x 2  2 x 2 , 2

2

x1 , x2  di  2

 2  1  H ( x1 , x 2 )     1  4  

Karena principal minor pertama, (-2 dan -4) keduanya negatif, dan principal minor kedua adalah -2(-4) – (-1)(-1) = 7 > 0, jadi f adalah suatu fungsi cekung pada R2.


54

OPTIMASI (Pemrograman Non Linear)

Recommend Documents