Pemrograman Non Linier(nlp): Semester Ganjil 2013/2014

Pemrograman Non Linier(NLP) Semester Ganjil 2013/2014

3/27/2019

Dr. Rahma Fitriani, S.Si., M.Sc

1

Konsep NLP Mencari nilai dari suatu peubah keputusan x1, ..., xn dari permasalahan: max (min) z =f(x1,...xn) s.t. g1 (x1,...xn) (≤,=,≥)b1 . . . gm (x1,...xn) (≤,=,≥)bm di mana z dan gi, i = 1, ..., n suatu fungsi yang non linier. Dimungkinkan maksimisasi/minimisasi tanpa kendala 3/27/2019

Dr. Rahma Fitriani, S.Si., M.Sc

2

Perbedaan antara NLP dan Pemrograman Linier (LP) Himpunan Konveks (Convex set): himpunan titiktitik S di mana sembarang pasangan titik di dalam himpunan S dihubungkan oleh garis yang seluruh titik pada garis tersebut juga di S

3/27/2019

(a) danFitriani, (b) himpunan konveks Dr. Rahma S.Si., M.Sc

3

Definisi daerah feasibel (feasible region): • Himpunan titik (x1,...xn) yang memenuhi seluruh m kendala Definisi solusi optimal bagi NLP Suatu titik di feasible region di mana • Kasus maks: Untuk semua x di feasible region

• Kasus min:

Suatu titik di feasible region di mana Untuk semua x di feasible region

3/27/2019

Dr. Rahma Fitriani, S.Si., M.Sc

4

• Di dalam LP dengan daerah feasibel yang berupa himpunan konveks, solusi optimal adalah salah satu dari titik ekstrim (titik pojok) • Di dalam NLP, walalupun daerah feasibel berupa himpunan konveks, solusi optimal belum tentu pada titik ekstrim (titik pojok)

3/27/2019

Dr. Rahma Fitriani, S.Si., M.Sc

5

Contoh 1: Jika digunakan K unit alat dan L orang tenaga kerja, maka suatu perusahaan dapat memproduksi KL unit suatu produk.

Jika alat dapat dibeli $4 per unit, tenaga kerja harus dibayar $1/orang, dan dimiliki modal $8 untuk membeli alat dan membayar tenaga kerja, bagaimana perusahaan tadi memaksimumkan jumlah barang yang akan diproduksi?

3/27/2019

Dr. Rahma Fitriani, S.Si., M.Sc

6

Fungsi obyektif: memaksimumkan jumlah produksi sebagai fungsi dari alat dan tenaga kerja Kendala modal, dan non negatifitas Daerah feasibel (ABC) berupa himpunan konveks Titik D terkena garis isoprofit paling akhir, tapi bukan titik pojok

3/27/2019

Dr. Rahma Fitriani, S.Si., M.Sc

7

Contoh 2: Kasus di mana fungsi obyektif berupa fungsi kuadratik yang akan dimaksimumkan, dan daerah feasibel adalah selang tertutup di antara 0 sampai dengan 1.

3/27/2019

Dr. Rahma Fitriani, S.Si., M.Sc

8

Garis isoprofit bukan garis lurus (non linier)

• Daerah feasibel berupa selang • Titik ekstrim seharusnya adalah x=0 dan x=1 • Akan tetapi solusinya adalah x=½ yang bukan titik ekstrim 3/27/2019

Dr. Rahma Fitriani, S.Si., M.Sc

9

Ekstremum Lokal (maks/min) Suatu titik feasibel x = (x1, ... , xn) adalah titik maksimum lokal jika - Untuk  relatif kecil dan sembarang titik feasibel x’ = (x’1, ... , x’n) di mana Berlaku:

3/27/2019

Dr. Rahma Fitriani, S.Si., M.Sc

10

Ekstremum Lokal (maks/min) Suatu titik feasibel x = (x1, ... , xn) adalah titik minimum lokal jika - Untuk  relatif kecil dan sembarang titik feasibel x’ = (x’1, ... , x’n) di mana Berlaku:

3/27/2019

Dr. Rahma Fitriani, S.Si., M.Sc

11

Ekstremum Lokal (maks/min) Untuk suatu LP maksimum/minimum lokal pasti solusi optimal, tetapi tidak untuk NLP

3/27/2019

Dr. Rahma Fitriani, S.Si., M.Sc

12

Contoh 3 Fungsi obyektif non linier dengan daerah feasibel berupa selang tertutup di antara 0 sampai dengan 10

3/27/2019

Dr. Rahma Fitriani, S.Si., M.Sc

13

• Titik A dan B adalah titik maksimum lokal • Akan tetapi hanya C yang merupakan solusi optimal karena bersifat maksimum global

3/27/2019

Dr. Rahma Fitriani, S.Si., M.Sc

14

• NLP tidak mempunyai asumsi aditif dan proportionalitas seperti di dalam LP • Pada LP jika nilai peubah keputusan x dinaikkan satu unit, maka fungsi obyektif akan meningkat/menurun secara proporsional • Tidak berlaku bagi NLP

3/27/2019

Dr. Rahma Fitriani, S.Si., M.Sc

15

Contoh 4 • Diberikan NLP berikut ini

• Jika x diperbesar 2 kali lipat, kontribusi terhadap z tidak akan 2 kali lipat ataupun kelipatannya.

3/27/2019

Dr. Rahma Fitriani, S.Si., M.Sc

16