RISET OPERASI

NON LINEAR
PROGRAMMING
PRESENTED BY SITI SABRINA SALQAURA,S.P., [Link]
 OUTLINE
• Ketidaklinearan dalam bidang ekonomi
• Prasyarat dalam mempelajari program non linier (Matriks Hessian,
Fungsi cembung dan cekung, dan set cembung)
• Masalah Optimisasi (constraint dan unconstraint dengan
menggunakan turunan dan Lagrange Multiplier)
• Beda antara program linier dan non linier
PENDAHULUAN
• Masalah Program Linear tujuan maupun kendala-kendalanya
berbentuk fungsi linier.
• Asumsi hubungan linier merupakan pendekatan yang cocok atau
sekurang-kurangnya cukup bagus untuk suatu interval nilai variabel
dari masalah tertentu.
• Namun terdapat persoalan yang bersifat non linear, Kerangka ini
ditemui dalam program non linier, metode-metode yang digunakan
untuk menyelesaikan masalah disebut algoritma program non linier
PENDAHULUAN
• Masalah non linear programming ditandai dengan fungsi –fungsi non
linear diantara tujuan atau kendala-kendalanya, bentuk non linier itu
misalnya :
x2 , ln x, 1/x, ex, sin(x), tg(x) dan lain-lain
• Ketidaklinieran juga dapat timbul sebagai akibat dari interaksi antara
dua atau lebih variabel, seperti :
x1,x2,x3, x1 ln(x2), xy, dan lain-lain.
 Ketidaklinearan dalam bidang ekonomi

• Contoh Struktur Biaya : Biaya total produksi akan meningkat jika output
bertambah.
• Kebutuhan akan tenaga kerja dan atau input-input lain juga akan
bertambah, namun peningkatan biaya total tidak proporsional dengan
peningkatan produksi.
• Karena beberapa alasan : pembelian input-input dalam jumlah lebih banyak
dapat meningkatkan harga input, bertambahnya ukuran unit usaha dapat
memberikan economies of scale kalau bukan diseconomies of scale, limbah
industri yang berlebihan dapat menimbulkan external diseconomies. Semua
faktor ini dapat menimbulkan perlambatan dan percepatan perubahan
biaya total sehingga biaya total bukan lagi fungsi linier dari jumlah output.
 Ketidaklinearan dalam bidang ekonomi

• Sebagai suatu ilustrasi katakan sampai tingkat output tertentu model

matematik biaya total (C), merupakan fungsi dari jumlah produksi (Q),
misalnya saja adalah : C =10 + 2Q, yang masih berbentuk linier.
• Jika produksi terus bertambah fungsi biaya dapat saja berubah,
katakan menjadi C = 10 + 111Q – 7Q2 + 1/3Q2, yang non linier
 Ketidaklinearan dalam bidang ekonomi

• Contoh kedua diambil dari masalah produksi.

• Penerimaan merupakan perkalian antara jumlah output dengan harga output
per unit.
• Jik aunit usaha yang menghasilkan output iti bersifat monopoli, kenaikan
produksi apsar dapat menyebabkan turunnya harga.
• Ini berarti penerimaan bukan fungsi linier dari harga.
• Misalkan hubungan antara harga (P) dengan jumlah output (Q) yang bisa
dinamakan fungsi permintaan adalah :
• P = 100 –Q, maka fungsi penerimaan (R) monopolis adalah
• R=QxP
= Q (100-Q) = 100Q-Q2, yang non linier
 Ketidaklinearan dalam bidang ekonomi

• Contoh ketiga tentang preferensi konsumen.

• Karena marginal rate of substitution suatu barang adalah menurun
maka indifference curve seorang konsumen tidak akan berbentuk linier
melainkan cembung ke arah titik asal.
• Kepuasan konsumen (U) yang merupakan fungsi dari barang-barang
yang dikonsumsi (X,Y) yang ditunjukkan oleh indifference curve, dengan
demikian dapat berbentuk sebagai berikut
U = (X + 2) ( Y +1) = XY + X + 2Y +2, yang non linier
Dari beberpaa contoh diatas terlihat bahwa formulasi non liniear akan
lebih cocok dibanding yang linier.
 Prasyarat dalam mempelajari program non
linier
• Beberapa konsep dalam MATRIKS dan ALJABAR seperti matriks Hessian,
kecekungan dan set cekung merupakan pengetahuan minimum yang
diharapkan diketahui.
Matriks Hessian
• Misalkan terdapat sebuah fungsi n variabel f (x1, x2, . . . . . Xn)
Kemudian dibuat suatu matriks yang merupakan turunan parsial kedua dari
fungsi tersebut dengan susunan seperti berikut :
(H) = maka matriks H dinamakan matriks Hessian.
Prasyarat dalam mempelajari program non
linier
Matriks Hessian (Lanjutan)
• Jika terdapat suatu matriks berukuran (nxn), maka principal minorke k
(k< n) adalah suatu sub matriks dengan ukuran (k x k) yang diperoleh
dengan menghapus (n-k) baris dan kolom yang bersesuaian dari
matriks tersebut.
• Contoh :
•Q= Principal minor ke 1 adalah elemen-elemen diagonal
yaitu 1,5, 9. Principal minor kedua adalah matriks-
matriks (2x2) berikut :
Prasyarat dalam mempelajari program non
linier
Matriks Hessian (Lanjutan)
• Principal minor ke 3 adalah matriks Q itu sendiri.
• Determinan dari suatu principal minor dinamakan principal determinant. Untuk
suatu matriks bujur sangkar (nxn), terdapat 2n-1 principal determinant.
• Leading principal minor ke k dari suatu matriks (n x n) diperoleh dengan
menghapus (n-k) barus terakhir dan kolom yang [Link] matriks Q
sebelumnya leading principal minor ke 1 adalah 1 (hapus dua baris terakhir dan
dua kolom terakhir). Leading principal minor ke 1 adalah

• Sementara yang ke 3 adalah matriks Q itu sendiri. Banyaknya leading principal

determinant dari suatu matriks (n x n) adalah n.
Prasyarat dalam mempelajari program non
linier
Matriks Hessian (Lanjutan)
Ada cara pengujian yang gampang untuk menentukan apakah suatu matriks adalah
positive definite, positive semidefinite, negative definite, negative semidefinite, atau
indefinite. Semua pengujian itu berlaku hanya jika matriks simetris.
Ketentuan uji bagi matriks positive definite adalah :
a. Semua elemen diagonal harus positif
b. Semua leading principal determinant harus positif
Ketentuan uji untuk matriks positive semidefinite adalah :
c. Semua elemen diagonal non negatif
d. Semua leading principal determinant non negative
Prasyarat dalam mempelajari program non
linier
Matriks Hessian
Untuk membuktikan bahwa suatu matriks adalah negative definite
(semidefinite), uji negatif dari matriks menjadi indefinite adalah bahwa
sekurang-kurangnya dua dari elemen diagonalnya memiliki tanda
berlawanan.
Prasyarat dalam mempelajari program non linier
Fungsi Cembung dan Cekung
Suatu fungsi n variabel f(X), dimana X = ( x1, x2, . . . ., xn) diakatakan sebagai
suatu fungsi cembung jika dan hanya jika dua titik Xa dan Xb dengan 0≤θ ≤1,
berlaku : f (θ Xa + (1- θ) Xb ≤ θ f(Xa) + (1- θ) f(Xb).
Suatu fungsi f(X) adalah suatu fungsi cekung jika dan hanya jika – f(x) adalah
suatu fungsi cembung.
Dalam praktek untuk emngetahui fungsi cembung atau cekung digunakan
pengujian sebagai berikut :
Suatu fungsi fadalah fungsi cembung jika matriks Hessian dari fungsi f adalah
definite positive atau semidefinite positive
Prasyarat dalam mempelajari program non linier
Fungsi Cembung dan Cekung
Suatu fungsi f adalah cekung jika matriks Hessian dari fungsi f adalah definite negative atau
semidefinite negative.
Contoh : f (X1, X2, X3) = 3 X12 + 2 X22 – 2 x1x2 – 2x1x3 + 2x2x3-6x1 -4x2-x32
Memiliki (H) = dengan leading principal determinantadalah : H1 = 6, H2=20, dan
H3=16. Sehingga (H) adalah suatu matriks definit positif yang berarti f adalah fungsi
cembung.
Pembuktian secara matematis diatas aritnya secara geometris bahwa jika suatu fungsi
adalah cembung(cekung) dan jika suatu garis ditarik antara setiap dua titik pada
permukaan fungsi, garis yang menghubungkan titik ini seluruhnya terletak di atas
(dibawah) dan fungsi itu. Gambar 1 menunjukkan beberapa contoh kurva fungsi cembung
dan cekung.
Prasyarat dalam mempelajari program non linier
Fungsi Cembung dan Cekung
Dari beberapa kurva tersebut dapat
dibuat kesimpulan :
1. Defenisi suatu fungsi cembung
(cekung) tidak tergantung apakah
suatu fungsi kontinyu atau
diskontinyu.
2. Suatu fungsi dapat cekung pada
suatu daerah dan cembung pada
wilayah lain
3. Suatu fungsi linier adalah
cembung maupun cekung
Prasyarat dalam mempelajari program non linier
Set cembung
Fungsi cembung dan set cembung merupakan dua konsep yang berbeda.
Misalkan S adalah suatu set titik-titik dari suatu bidang (2 dimensi) atau ruang 3
dimensi. Jika untuk setiap dua titik pada set S, garis yang menghubungkan dua
titik itu seluruhnya terletak pada set S, maka S dikatakan set cembung
Perhatikan contoh-contoh set cembung apda gambar 2. Semua set pada gambar
2.a adalah set cembung dan semua pada gambar 2.b. Adalah bukan set
cembung.
Secara umum dapat dikatakan bahwa syarat sebagai set ccembung adalah
bahwa set tidak memiliki lubang dan batas-batasnya harus mulus.
Prasyarat dalam mempelajari program non linier
Set Cembung
MASALAH OPTIMISASI
1. Optimisasi tanpa kendala
Suatu nilai ekstrim dari fungsi menunjukkan suatu nilai maksimum atau
minimum dari fungsi itu. Teori optimisasi klasik menggunakan kalkulus
derivatif untuk menentukan titik ekstrim baik untuk fungsi yang tanpa
kendal amaupun dengan kendala persamaan.
Secara matematis, suatu titik X0 = (x1, x2, . . . ., xn) adalah maksimum jika
f (X0 + D) < f (X0) untuk semua D= (d1, d2, . . ., dn) dimana dj mutlak cukup
kecil untuk semua j. Dengan cara yang sama X0 adalah minimm (untuk
D yang didefenisikan seperti sebelumya ) jika : f (X0 + D) > f (X0)
MASALAH OPTIMISASI
1. Optimisasi tanpa kendala
Gambar 3 memperagakan titik maksimum dan minimum suatu fungsi
variabel f(x) dalam interval (a,b). Interval a≤x ≤ b tidak berarti
menunjukkan pembatas pada f (x).
Titik x1, x2,x3, x4 dan x6 semuanya adalah nilai ekstrim dari f(x). Titik x1,
x3 dan x6 sebgai nilai maksimum dan x2 , x4 sebagai minimum. Karena
f(x6) = maksi ( f(x1), f(x3), f(x6)), maka f(x6) dinamakan maksimu mglobal
atau absolut, dan f(x1), f(x3) adalah maksimum lokal atau relatif. Secara
serupa f(x4) adalah minimum lokal dan f(x2) adalah minimum global
dengan sendirinya juga merupakan optimum lokal.
MASALAH OPTIMISASI
1. Optimisasi tanpa kendala
Meskipun x1 adalah titik maksimum, ia
berbeda dari maksimum lokal yang lain
dalam hal bawah nilai f untuk sekurang-
kurangnya satu titik disekitar x1 sama
dengan f (x1). Dalam kaitan ini, x1
dinamkan maksimum lemah dibanding
x3 misalnya dimana f(x3) menunjukkan
maksimum kuat. Suatu maksimum
lemah berarti jumlah tak terbatas
(alternatif) maksima. Dengan penalaran
yang sama, x4 adalah minimum lemah.
MASALAH OPTIMISASI
1. Optimisasi tanpa kendala
Pada umumnya x0 adalah maksimum lemah jika f(x0 + D) ≤ f(X0) dan maksimum kuat, jika f(X0+D) <
f(X0), dimana D didefenisikan seperti sebelumnya.
Degnan Teori Taylor dapat dibuktikan bahwa :
2. Suatu syarat perlu bagi X0 menjadi suatu tutuk ekstrim dari f(X) adalah bahwa gradient
vectornya atau delta f(x0) =0, titik yang diperolah dari persamaan itu dinamakan titik stastioner
3. Suatu syarat cukup untuk suatu titik stasioner X0 menjadi ekstrim adalah dengan mengevaluasi
matriks Hessian, H pada x0.
1. Suatu titik stasioner menjadi suatu nilai minimum adalah cukup jika leading principal determinant H 1,
H2, . . . .Hn semuanya positif (positif definit)
2. Suatu titik stasioneer menjadi suatu nilai maksimum , adalah cukup jika semua leading principal
determinant genap adalah positif dan semua leading prinsipal determinant ganjil adalah negatif (negatif
definit)
MASALAH OPTIMISASI
2. Optimisasi dengan kendala
• Kendala dapat berbentuk persamaan atau pertidaksamaan
• Berikut ini membicarakan optimisasi fungsi kontinyu dan dapat diturunkan
dengan kendala persamaan
• Untuk mencapai maksud itu tersedia beberapa metode optimisasi, berikut hanya
akan dibahas mengenai Lagrange multiplier
• Teknik Lagrange Multiplier telah dikembangkan untuk mengatasi masalah
optimisasi dengan kendala persamaan dalam suatu bentuk demikian hingga
syarat perlu bagi masalah optimisasi dalam suatu bentuk demikian sehingga
syarat perlu bagi masalah optmisasi tanpa kendala masih dapat diterapkan.
• (Cek multiplier lagrangean di Matematika bisnis atau ekonomi mikro sebelumnya)
 Beda antara program linier (LP) dan non
linier (NLP)
• Teori Kuhn-Tucker dengan tujuan memberikan pengetahuan tentang optimisasi non
linier dengan kendala pertidaksamaan
• Metode simplex dapat digunakan untuk menyelesaikan masalah program linier baik
yang melibatkan dua atau lebih variabel. Metode ini berlaku karena hal-hal berikut
merupakan syarat bagi bekerjanya metode simplex :
1. Solusi layak merupakan set cembung dengan jumlah titik pojok (ekstrim) yang
terbatas (dalam NLP bisa tidak)
2. Jika fungsi tujuan terbatas, nilai optimalnya kana terjadi pada salah satu titik pojok
dari ruang solusi, mungkin pada lebih dari satu titik pojok (dalam NLP bisa tidak)
3. Suatu optimum lokal adalah juga optimal global dari fungsi tujuan (dalam NLP bisa
tidak)
Dalam nonlinear programming beberapa syarat tersebut mungkin tidak berlaku.
REFERENSI
• Mulyani, Sri. 1989. Program Non Linier. Ekonomi dan Keuangan
Indonesia Vol. 37 No. 2 2989.
TERIMA KASIH