penentuan solusi optimal dan nilai optimal … · sistem persamaan linear, matriks, optimasi...

PENENTUAN SOLUSI OPTIMAL DAN NILAI OPTIMAL

ANALISIS PARAMETRIK TERHADAP

OPTIMASI LINEAR

MUHAMAD AVENDI

DEPARTEMEN MATEMATIKA

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM

INSTITUT PERTANIAN BOGOR

BOGOR

2014

iii

PERNYATAAN MENGENAI SKRIPSI DAN

SUMBER INFORMASI SERTA PELIMPAHAN HAK CIPTA*

Dengan ini saya menyatakan bahwa skripsi berjudul Penentuan Solusi

Optimal dan Nilai Optimal Analisis Parametrik Terhadap Optimasi Linear adalah

benar karya saya dengan arahan dari komisi pembimbing dan belum diajukan

dalam bentuk apa pun kepada perguruan tinggi mana pun. Sumber informasi yang

berasal atau dikutip dari karya yang diterbitkan maupun tidak diterbitkan dari

penulis lain telah disebutkan dalam teks dan dicantumkan dalam Daftar Pustaka di

bagian akhir diskripsi ini.

Dengan ini saya melimpahkan hak cipta dari karya tulis saya kepada Institut

Pertanian Bogor.

Bogor, Januari 2014

Muhamad Avendi

NIM G54090031

ABSTRAK

MUHAMAD AVENDI. Penentuan Solusi Optimal dan Nilai Optimal Analisis

Parametrik terhadap Optimasi Linear. Dibimbing oleh BIB PARUHUM

SILALAHI dan MUHAMMAD ILYAS.

Optimasi adalah suatu ilmu dari matematika terapan yang mempelajari

masalah-masalah yang bertujuan mencari nilai minimum atau maksimum dari

suatu fungsi yang memenuhi kendala-kendala. Sedangkan optimasi linear khusus

mempelajari hal-hal yang berkaitan dengan meminimumkan atau

memaksimumkan fungsi-fungsi linear dengan kendala-kendala yang juga linear.

Parameter-parameter dalam model optimasi linear dapat mengalami perubahan.

Oleh karena itu perlu menganalisis perubahan ini dengan menggunakan analisis

parametrik. Analisis parametrik merupakan analisis yang berguna untuk

memeriksa dampak dari perubahan parameter secara kontinu terhadap solusi

optimal. Masalah analisis parametrik memperkenankan parameter terpilih

atau diubah secara kontinu pada interval tertentu. Sifat-sifat dari analisis

parametrik yaitu (1) nilai optimal fungsi berbentuk kontinu, konkaf/konveks dan

piecewise linear, (2) pada suatu interval tertentu perubahan parameter tidak akan

mengubah solusi optimalnya, (3) break point adalah suatu titik di mana solusi

optimal akan berubah bila terjadi perubahan parameter dari sisi kiri break point ke

sisi kanannya, dan (4) terdapat titik ekstrem yang juga merupakan break point.

Kata kunci: Analisis Parametrik, break point, Interval Linear, Optimasi Linear.

ABSTRACT

MUHAMAD AVENDI. Determination of Optimal Solution and Optimal Value of

Parametric Analysis of Linear Optimization. Supervised by BIB PARUHUM

SILALAHI and MUHAMMAD ILYAS.

Optimization is a field of applied mathematics which studies problems to

find the minimum or maximum value of a function that satisfies all of the

constraints. Moreover, linear optimization studies a problem where its objective

function is a linear function and all of its constraints are linear also. The

parameters of a linear optimization problem may have a variation. Therefore, it is

necessary to analyze this variation. The analysis of parametric is a useful analysis

in studying the continuously effects of parameter variations to the optimal solution.

Parametric analysis introduces optional parameters ( ) which are changed

continually at a certain interval. The characteristics of parametric analysis are as

follows; (1) the optimal-value function is continuous, concave/convex and

piecewise linear, (2) at a certain interval, the variations of parameter does not

effect the optimal solution, (3) break point is a point at which the optimal solution

will have a variations if the parameter value change from the left side of the break

point to the right side, and (4) there is an extreme point which is also a break point.

Keywords: Parametric Analysis, break point, Linearity Interval, Linear

Optimization.

v

Skripsi

sebagai salah satu syarat untuk memperoleh gelar

Sarjana Sains

pada

Departemen Matematika

PENENTUAN SOLUSI OPTIMAL DAN NILAI OPTIMAL

ANALISIS PARAMETRIK TERHADAP

OPTIMASI LINEAR

MUHAMAD AVENDI

DEPARTEMEN MATEMATIKA

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM

INSTITUT PERTANIAN BOGOR

BOGOR

2014

vii

Judul Skripsi : Penentuan Solusi Optimal dan Nilai Optimal Analisis Parametrik

Terhadap Optimasi Linear

Nama : Muhamad Avendi

NIM : G54090031

Disetujui oleh

Dr Ir Bib Paruhum Silalahi, MKom

Pembimbing I

Muhammad Ilyas, MSi

Pembimbing II

Diketahui oleh

Dr Toni Bakhtiar, MSc

Ketua Departemen

Tanggal Lulus:

PRAKATA

Puji dan syukur penulis panjatkan kepada Allah SWT atas segala karunia-

Nya sehingga karya ilmiah ini berhasil diselesaikan. Karya ilmiah ini mulai

dikerjakan oleh penulis sejak bulan Januari 2013. Judul karya ilmiah ini adalah

Penentuan Solusi Optimal dan Nilai Optimal Analisis Parametrik terhadap

Optimasi Linear.

Terima kasih penulis ucapkan kepada Bapak Dr Ir Bib Paruhum Silalahi,

MKom. dan Bapak Muhammad Ilyas, MSi selaku dosen pembimbing, serta Bapak

Drs Prapto Tri Supriyo, MKom selaku dosen penguji yang telah banyak memberi

saran. Di samping itu, terima kasih kepada seluruh dosen dan staf Departemen

Matematika atas segala ilmu yang diberikan dan bantuannya selama masa

perkuliahan. Ungkapan terima kasih juga disampaikan kepada kedua orang tua

yakni Ayah Supendi dan Ibu Manzilah (Alm), kakak dan adik-adikku yakni Kak

Eka, Ridwan, Nabila, Diana dan Faraby serta seluruh keluarga besar, atas segala

dukungan, doa dan kasih sayangnya. Tak lupa ucapan terima kasih untuk sahabat

Matematika 46 yakni Galih, Aldi (dio), Adit, Mirna, Rohmat, Qowi dan lainnya,

kakak dan adik kelas, sahabat SMA yakni Andika, teman kos Badoneng Ceria

yakni Fahmi, Arif, Suhe dan Karim serta seluruh pihak yang telah mendukung dan

mendoakan penulis hingga terselesaikannya karya ilmiah ini. Mohon maaf karena

penulis tidak dapat menyebutkannya satu per satu.

Semoga karya ilmiah ini bermanfaat.

Bogor, Januari 2014

Muhamad Avendi

ix

DAFTAR ISI

DAFTAR GAMBAR vi

DAFTAR LAMPIRAN vi

PENDAHULUAN 1

Latar Belakang 1

Tujuan Penelitian 2

TINJAUAN PUSTAKA 2

Sistem Persamaan Linear dan Matriks 2

Optimasi Linear 3

Fungsi Konveks dan Fungsi Konkaf 4

Analisis Parametrik 6

HASIL DAN PEMBAHASAN 6

Nilai Optimal Fungsi Adalah Piecewise Linear 9

Set Optimal pada Interval Linear 11

Set Optimal di Break Point 14

Titik Ekstrem di Interval Linear 17

Prosedur Menentukan Semua Break Point dan Interval Linear 19

Contoh Aplikasi 22

SIMPULAN DAN SARAN 29

Simpulan 29

Saran 29

DAFTAR PUSTAKA 30

LAMPIRAN 31

RIWAYAT HIDUP 35

DAFTAR GAMBAR

1 Ilustrasi himpunan konveks dan bukan himpunan konveks 5

2 Ilustrasi fungsi konveks 5

3 Ilustrasi fungsi konkaf 5

4 Nilai optimasi 10

5 Nilai optimasi 11

6 Hasil analisis untuk contoh aplikasi 1 25

7 Hasil analisis untuk contoh aplikasi 2 29

DAFTAR LAMPIRAN

1 Pembuktian domain dari adalah konveks 31

2 Pembuktian pelengkap dari domain adalah subset terbuka

dari garis real. 32

3 Pembuktian Lema 3 32

4 Algoritme Nilai Optimal Fungsi dan 33

5 Algoritme Nilai Optimal Fungsi dan 34

PENDAHULUAN

Latar Belakang

Optimasi adalah suatu bidang dari matematika terapan yang mempelajari

masalah-masalah yang bertujuan mencari nilai minimum atau maksimum suatu

fungsi, dengan memenuhi kendala-kendala yang ada. Optimasi linear khusus

mempelajari hal-hal yang berkaitan dengan meminimumkan atau

memaksimumkan fungsi-fungsi linear, dengan kendala yang juga linear (berupa

persamaan atau pertidaksamaan). Dalam pemodelan optimasi linear, setiap

parameter yang digunakan dalam model diasumsikan nilainya diketahui dengan

pasti. Parameter-parameter ini terdiri dari koefisien nilai ruas kanan ( ) dan

koefisien fungsi tujuan . Pada kenyataannya, parameter-parameter tersebut

kebanyakan adalah hasil perkiraan pengambil keputusan yang dapat mengalami

perubahan karena faktor-faktor tertentu.

Faktor-faktor yang menyebabkan perubahan-perubahan parameter ini,

umumnya merupakan faktor yang berada di luar kendali para pengambil

keputusan. Faktor-faktor tersebut seperti situasi ekonomi, bencana alam, dan lain

sebagainya. Misalnya, apabila situasi ekonomi mengalami krisis, hal tersebut

dapat menyebabkan terjadinya perubahan pada parameter-parameter koefisien

fungsi tujuan. Demikian juga halnya dengan bencana alam, dapat menyebabkan

terjadinya perubahan pada parameter-parameter nilai ruas kanan.

Pada saat terjadi perubahan, parameter-parameter mungkin ada yang

sensitif terhadap perubahan. Artinya ada parameter-parameter yang bila nilainya

berubah, solusi optimalnya berubah. Sementara itu terdapat juga parameter yang

meskipun nilainya berubah, namun tidak mempengaruhi solusi optimal. Oleh

karena itu perlu menganalisis perubahan ini dengan menggunakan analisis

sensitivitas. Analisis sensitivitas merupakan analisis yang dilakukan untuk

mengetahui pengaruh perubahan yang terjadi pada parameter-parameter model

optimasi linear terhadap solusi optimal yang telah dicapai (Lestaurika 2007).

Roos et al. (2006) menggunakan analisis parametrik sebagai bentuk lain

dari analisis sensitivitas. Analisis parametrik merupakan analisis sensitivitas

sistematis karena perubahan parameter terjadi secara kontinu. Oleh karena itu,

analisis parametrik merupakan analisis sensitivitas lanjutan yang sangat berguna

untuk memeriksa dampak dari hubungan parameter-parameter yang berubah

secara kontinu dan bersamaan. Pada tugas akhir ini, penulis meneliti interval yang

diizinkan dari perubahan parameter-parameter tersebut hingga solusi tetap optimal.

Pada karya ilmiah ini akan dibahas penentuan solusi optimal dan nilai

optimal analisis parametrik terhadap optimasi linear, dengan rujukan utama adalah

Roos et al. (2006) yang berjudul Interior Point Methods for Linear Optimization.

2

Tujuan Penelitian

Tujuan dari karya ilmiah ini ialah sebagai berikut:

1 menjelaskan dan mengonstruksi kembali analisis parametrik,

2 menganalisis perubahan parameter yakni koefisien dari fungsi tujuan

dan/atau nilai ruas kanan kendala terhadap solusi optimal, dengan sifat-

sifat analisis parametrik.

TINJAUAN PUSTAKA

Pada bab ini akan dijelaskan mengenai definisi dari berbagai istilah terkait

analisis parametrik yang akan digunakan pada bab hasil dan pembahasan, seperti

sistem persamaan linear, matriks, optimasi linear, fungsi konveks dan fungsi

konkaf yang juga akan dilengkapi dengan contohnya.

Sistem Persamaan Linear dan Matriks

Berikut ini akan dibahas definisi SPL dan matriks. Suatu persamaan linear

dalam N variabel dinyatakan sebagai berikut

dengan dan b adalah bilangan-bilangan real dan adalah

variabel (Leon 1998). Persamaan linear tersebut disebut sebagai hiperbidang pada

ruang Euclid berdimensi , (Anton & Rorres 2005). Suatu sistem persamaan

linear (SPL) dari persamaan dalam variabel adalah suatu sistem berbentuk

dengan dan adalah bilangan bilangan real dan

adalah variabel. SPL tersebut disebut sebagai SPL berukuran (Leon 1998). Penyelesaian SPL berukuran adalah sebuah vektor

berukuran , yaitu [

], yang memenuhi semua persamaan linear dalam

sistem. Vektor yang demikian disebut sebagai vektor penyelesaian. SPL berukuran

tersebut dapat ditulis dalam bentuk dengan

vektor-vektor kolom dan (maisng-masing berukuran ) adalah

[

] [

] (Anton & Rorres 2005).

Selain itu, SPL berukuran tersebut juga dapat ditulis dalam bentuk

3

dengan matriks A, vektor kolom dan vektor kolom b (masing-masing berturut-

turut berukuran , dan ) adalah

[

] , [

], [

].

Matriks A disebut matriks koefisien, sedangkan vektor kolom b disebut sebagai

vektor konstanta. Suatu SPL dikatakan konsisten jika mempunyai paling sedikit

satu penyelesaiaan, sedangkan suatu SPL yang tidak mempunyai penyelesaiaan

dikatakan takkonsisten (Leon 1998).

Matriks identitas adalah matriks yang berukuran , dengan

{

Suatu matriks A yang berorde dikatakan tak singular jika terdapat matriks B

sehingga AB=BA=I. Matriks B dikatakan invers multiplikatif dari matriks A.

Invers multiplikatif dari matriks taksingular A secara sederhana disebut juga

sebagai invers dari matriks A dan dinotasikan dengan . Transpos dari suatu

matriks yang berukuran adalah matriks yang

berukuran yang terdefinisi oleh

untuk setiap i dan j. Transpos dari A dinotasikan oleh (Leon 1998).

Optimasi Linear

Berikut ini akan dibahas mengenai definisi optimasi, optimasi linear,

daerah fisibel, solusi fisibel, dan solusi optimum. Optimasi adalah suatu bidang

dari matematika terapan yang mempelajari masalah-masalah yang bertujuan

mencari nilai minimum atau maksimum suatu fungsi, dengan memenuhi kendala-

kendala yang ada. Optimasi Linear (OL) khusus mempelajari hal-hal yang

berkaitan dengan meminimumkan atau memaksimumkan fungsi-fungsi linear,

dengan kendala yang juga linear (berupa persamaan atau pertidaksamaan).

Misalkan menyatakan suatu fungsi dalam variable-variabel .

Fungsi dikatakan linear jika dan hanya jika untuk suatu himpunan konstanta

, = (Winston 2004.) Sebagai contoh

merupakan fungsi linear, sedangkan bukan

fungsi linear. Jika f fungsi linear dan d konstanta, maka merupakan

persamaan linear. Untuk sembarang fungsi linear dan sembarang bilangan d,

pertidaksamaan dan adalah pertidaksamaan linear (Winston

2004).

Solusi optimasi linear mempunyai bentuk standar seperti yang

didefinisikan sebagai berikut. Masalah optimasi linear dalam bentuk standar

diberikan sebagai berikut

min{ } dengan vektor , serta adalah matriks berpangkat

baris penuh. Masalah disebut masalah primal.

4

Masalah dual dari masalah primal diberikan sebagai berikut

max { }, dengan dan . Masalah disebut masalah dual. adalah

notasi dari nilai optimal dan . Daerah fisibel dari masalah didefinisikan sebagai

{ } sedangkan daerah fisibel dari didefinisikan sebagai

{ } (Roos et al. 2006).

Daerah fisibel optimasi linear adalah daerah yang memenuhi semua

kendala pada optimasi linear. Suatu solusi disebut fisibel jika memenuhi semua

kendala pada optimasi linear (Nash & Sofer 1996).

Solusi Basis

Solusi dari suatu optimasi linear disebut solusi basis jika memenuhi syarat

berikut:

1 Solusi tersebut memenuhi kendala pada optimasi linear,

2 Kolom-kolom dari matriks kendala yang berpadanan dengan

komponen taknol dari solusi tersebut adalah bebas linear.

Solusi dari suatu optimasi linear disebut solusi basis jika memenuhi

. Vektor disebut solusi basis fisibel jika merupakan solusi

basis dan (Nash & Sofer 1996).

Pada masalah maksimisasi, solusi optimum suatu optimasi linear adalah

suatu titik dalam daerah fisibel dengan nilai fungsi objektif terbesar. Pada masalah

minimisasi, solusi optimum suatu optimasi linear adalah suatu titik dalam daerah

fisibel dengan nilai fungsi objektif terkecil (Winston 2004). Dalam (Roos et al.

2006) setiap sistem persamaan linear dan pertaksamaan linear yang memenuhi

kondisi titik interior jika ada solusi fisibel yang memenuhi semua kendala

ketaksamaan dalam sistem.

Fungsi Konveks dan Fungsi Konkaf

Berikut ini akan dibahas mengenai definisi himpunan konveks, fungsi

konkaf, fungsi konkaf serta ilustrasinya. Sebelum membahas fungsi konveks dan

konkaf, sebaiknya terlebih dahulu dibahas himpunan konveks yang didefinisikan

sebagai berikut.

Misalkan S menyatakan himpunan titik. Himpunan S adalah himpunan

konveks jika segmen garis yang menghubungkan sembarang titik-titik dalam S

seluruhnya termuat dalam S, atau dengan perkataan lain himpunan

dikatakan himpunan konveks jika untuk setiap dan untuk setiap

[ ] berlaku Ilustrasi himpunan konveks dan bukan

konveks diberikan pada Gambar 1 berikut (Maulana 2009).

5

Gambar 1 Ilustrasi himpunan konveks

dan bukan himpunan konveks

Pada Gambar 1, lingkaran (i) dan persegi panjang (ii) merupakan

himpunan konveks, sedangkan bidang (iii) dan cincin (iv) bukan himpunan

konveks. Dalam (Bazaraa et al. 1993), dimisalkan . Maka

∑ dengan ∑

dan untuk disebut kombinasi

konveks dari . Konsep fungsi konveks dan fungsi konkaf yang

digunakan pada karya ilmiah ini meliputi definisi-definisi berikut ini.

Misalkan , dengan S himpunan konveks yang takkosong di .

Fungsi f dikatakan konveks di S jika

untuk setiap dan untuk setiap [ ] Ilustrasi:

Gambar 2 Ilustrasi fungsi konveks

Misalkan , dengan S himpunan konveks yang takkosong di . Fungsi f

dikatakan konkaf di S jika

untuk setiap dan untuk setiap [ ] (Peressini et al. 1988).

Ilustrasi:

Gambar 3 Ilustrasi fungsi konkaf

6

Analisis Parametrik

Berikut ini akan dibahas mengenai definisi analisis parametrik dan sifat

sifat analisis parametrik. Analisis parametrik merupakan analisis sensitivitas

sistematis karena perubahan parameter terjadi secara kontinu. Oleh karena itu,

analisis parametrik merupakan analisis sensitivitas lanjutan yang sangat berguna

untuk memeriksa dampak dari hubungan parameter-parameter yang berubah

secara kontinu dan bersamaan (Lestaurika 2007). Dalam buku yang ditulis Roos C,

Terlaky T, dan Vial J-Ph tahun 2006 dimodelkan hasilnya sifat-sifat dari analisis

parametrik yaitu (1) nilai optimal fungsi dengan adanya perubahan parameter-

parameter pada koefisien fungsi tujuan dan nilai ruas kanan pada masalah

optimasi linear adalah kontinu, konkaf/konveks dan piecewise linear, (2) pada

suatu interval tertentu perubahan parameter tidak akan mengubah solusi

optimalnya, (3) break point adalah suatu titik di mana solusi optimal akan berubah

bila terjadi perubahan parameter dari sisi kiri break point ke sisi kanannya, dan (4)

terdapat titik ektrem yang juga merupakan break point. Untuk lebih lanjut

mengenai sifat-sifat tersebut akan dibahas di Bab Hasil dan Pembahasan.

Proposisi 1 (Dualitas Lemah)

Misalkan adalah solusi fisibel untuk dan adalah solusi fisibel

untuk maka . disebut kesenjangan dualitas.

Akibatnya, adalah batas atas untuk nilai optimal dari , jika ada, serta

adalah batas bawah untuk nilai optimal dari , jika ada. Selanjutnya, jika

kesenjangan dualitas adalah nol maka adalah solusi optimal dari dan

adalah solusi optimal dari (Roos et al. 2006).

Teorema 1.1 (Dualitas)

Jika dan fisibel maka kedua masalah tersebut mempunyai solusi

optimal; kemudian, dan adalah solusi optimal jika dan hanya

jika . Jika tak satu pun dari dua masalah memiliki solusi optimal, maka

keduanya dan tidak fisibel atau salah satu dari dua masalah adalah tidak

fisibel dan yang lain tak terbatas (Roos et al. 2006).

Teorema 1.2 (Goldman-Tucker)

Jika dan fisibel maka terdapat solusi optimal dengan strictly

complementary (pelengkap yang kuat), yaitu suatu pasangan solusi optimal

dengan (Roos et al. 2006).

HASIL DAN PEMBAHASAN

Dalam bab ini akan menyelidiki efek dari perubahan b dan c pada nilai

optimal fungsi . Jadi kita akan mempelajari nilai optimal fungsi yang

dapat ditulis sebagai berikut.

7

sebagai fungsi dari parameter dan , dan dan adalah vektor perturbasi

(pengganggu), vektor b dan c adalah tetap. Karya ilmiah ini mempelajari tentang

kasus-kasus variasi yang hanya terjadi pada salah satu dari dua vektor b dan c. Ini

berarti, jika kita mengambil maka akan diperhatikan variasi dari

demikian pula sebaliknya, jika kita mengambil maka akan diperhatikan

variasi dari .

adalah notasi perturbasi untuk masalah primal dengan dan ( )

untuk masalah dualnya. Daerah fisibel pada kedua masalah diatas dilambangkan

dengan dan . Sebaliknya juga, adalah notasi perturbasi untuk masalah

dual dengan dan ( ) untuk masalah primalnya serta daerah fisibel pada

masalah diatas dilambangkan dengan dan . Perhatikan bahwa daerah fisibel

adalah hanya dan daerah fisibel ( ) hanya . Asumsi yang diberikan

bahwa b dan c sedemikian rupa sehingga (P) dan (D) keduanya fisibel. Oleh

karena itu, adalah didefinisikan ada dan terbatas. Selanjutnya notasi

berikut akan diperkenankan

( )

Disini domain dari parameter dan diambil sebesar mungkin dengan

memperhatikan domain Jika ada maka fungsi ini terdefinisi.

Perhatikan bahwa, ketika bervariasi maka daerah fisibel ( ) adalah konstan,

dan karena diasumsikan bahwa ( ) fisibel untuk , berarti ( ) fisibel untuk

setiap nilai . Oleh karena itu, didefinisikan jika masalah dual ( ) memiliki

solusi optimal dan tidak didefinisikan (atau tak terhingga) jika masalah dual

( ) tak terbatas. Dengan Teorema Dualitas ini berarti bahwa didefinisikan

jika dan hanya jika masalah primal ( ) fisibel. Dengan cara yang sama dapat

dipahami bahwa domain dari terdiri dari semua yang ( ) fisibel dan ( )

dibatasi.

Lema 1

Domain dari dan adalah konveks.

Bukti:

Akan dibuktikan untuk domain dari adalah konveks. Untuk bukti ada

di Lampiran 1. Diberikan , dom dan < < . Kemudian dan adalah terbatas, ini berarti bahwa

dan tidak kosong. Diberikan

dan

. Kemudian dan adalah nonnegatif dan

Sekarang perhatikan

8

Perhatikan bahwa adalah kombinasi konveks dari dan dan karena

adalah nonnegatif maka akan ditunjukkan bahwa Dengan mengurangkan

dengan sehingga mengakibatkan

dengan mengalikan matriks dengan persamaan (2) sehingga

ini membuktikan bahwa ( ) adalah fisibel dan karenanya dom

Domain dari dan dalam interval sebenarnya ditutup pada garis real. ini

mengikuti dari lema di atas, dan fakta bahwa pelengkap dari domain dari dan

adalah subset terbuka dari garis real. Pernyataan terakhir adalah isi dari lema

berikutnya.

Lema 2

Pelengkap dari domain dan adalah subset terbuka pada garis real.

Bukti: Seperti dalam pembuktian sebelumnya, untuk bukti pelengkap dari domain

adalah subset terbuka dan pada garis real terdapat di Lampiran 2 karena mirip

dengan bukti untuk . Kita cukup menunjukkan bahwa pelengkap dari dom adalah terbuka. Diberikan dom . Ini berarti bahwa ( ) adalah takterbatas.

Hal tersebut setara dengan keberadaan vektor sedemikian rupa sehingga

Dengan menetapkan z dan mempertimbangkan sebagai variabel, di

mana himpunan semua yang memenuhi ketidaksetaraan secara sempurna adalah interval terbuka. Untuk semua dalam interval ini ( )

takterbatas. Oleh karena itu, pelengkap dari domain dari adalah terbuka.

Suatu dampak dari dua lema terakhir adalah teorema berikutnya, yang

tidak memerlukan bukti lebih .

Teorema 2

Domain dari dan adalah interval tertutup pada garis real.

Diberikan Contoh 1 yang mengacu pada Lema 2 dan Teorema 2 berikut ini.

Contoh 1

Tentukan dengan masalah

{ }

Dalam kasus ini b = (0, 1) dan c = (1). Perhatikan bahwa (D) adalah daerah

fisibel dan dibatasi. Set dari semua solusi yang optimal terdiri dari setiap ( , 1)

9

dengan . Sekarang mari kita lihat dan mempertimbangkan

efek mengganti b dengan , dan membiarkan sebagaimana

dijelaskan di atas. Kemudian,

{ }

dengan mudah untuk memverifikasi bahwa masalah perturbasi adalah tak terbatas

untuk semua taknol. Karenanya domain dari adalah himpunan singleton yakni

{0}.

Selanjutnya akan dibahas tentang sifat-sifat dari analisis parametrik yaitu

nilai optimal fungsi adalah piecewise linear, set optimal pada interval linear, set

optimal di break point, dan titik ekstrem di interval linear. Keempat sifat-sifat

tersebut disajikan pula teorema, lema, dan corollary beserta buktinya yang

mendukung. Pada subbab terakhir akan disajikan prosedur mencari break point

dan interval linear serta contoh aplikasi.

Nilai Optimal Fungsi Adalah Piecewise Linear

Dalam subbab ini akan ditunjukkan bahwa fungsi dan

piecewise linear pada domainnya. Kita mulai dengan .

Teorema 3

adalah kontinu, konkaf dan piecewise linear.

Bukti:

Menurut definisi,

{ } Untuk setiap dicapai nilai minimum pada solusi sentral dari masalah perturbasi

( ). Solusi ini secara unik ditentukan oleh partisi optimal ( ). Karena jumlah

partisi dari himpunan indeks penuh, { } adalah terbatas maka dapat

dituliskan

{ } di mana T adalah subset terbatas dari P. Untuk setiap x T

yang merupakan fungsi linear dari . Karena adalah minimum dari satu set

fungsi linear terbatas maka adalah kontinu, konkaf dan piecewise linear.

Selanjutnya akan ditunjukkan bahwa fungsi piecewise linear pada

domainnya yang disajikan dalam Teorema 4 berikut ini.

Teorema 4

adalah kontinu, konveks dan piecewise linear.

Bukti:

Buktinya dengan cara yang sama seperti Teorema 3. Menurut definisi,

{ } Untuk setiap β yang nilai maksimum dicapai pada solusi pusat

dari ( ). Sekarang secara unik ditentukan oleh partisi optimal ( ) dan

yang konstan untuk semua yang optimal. Mengaitkan salah satu khususnya

10

dengan setiap kemungkinan slack yang muncul timbul dalam cara ini

didapatkan

{ } di mana S adalah subset terbatas dari . Untuk setiap y , kita memiliki

merupakan fungsi linear dari . Hal ini menjelaskan bahwa adalah

maksimum set terbatas dari fungsi linear. Oleh karena itu, adalah kontinu,

konveks dan piecewise linear, seperti yang dibutuhkan.

Perubahan kemiringan nilai optimal fungsi dari disebut break

points dari dan setiap interval antara dua break point secara berturut-turut

disebut linearity interval (interval linear) dari . Dengan cara yang sama kita

mendefinisikan break point dan interval linear untuk . Berikut ini diberikan

Contoh 2 yang mengacu pada Teorema 3.

Contoh 2

Untuk seti p γ mempertimbangkan masalah ( ) didefinisikan oleh

( )

Dalam hal ini adalah konstan dan vektor perturbasi untuk c = (1, 3, 1) adalah

Masalah Dualnya

( ) { }

Dari sini dijelaslah bahwa nilai optimal diberikan oleh

Grafik dari nilai optimal fungsi digambarkan pada Gambar 4. Perhatikan

bahwa

Gambar 4 Nilai optimal fungsi

adalah piecewise linear dan konkaf. Break point dari terjadi pada

dan

11

Berikut ini diberikan Contoh 3 yang mengacu pada Teorema 4.

Contoh 3

Untuk setiap mempertimbangkan masalah ( ) didefinisikan oleh

( ) { }

Dalam hal ini b adalah konstan dan vektor perturbasi untuk

adalah

Masalah Dualnya ( )

{ } Setara dengan

{ } Dengan misalkan variabel baru yakni , sehingga menjadi

{ } dapat ditulis kembali

{ } Dari sini dijelaslah bahwa nilai optimal diberikan oleh

Grafik dari nilai optimal fungsi digambarkan pada Gambar 4.

Gambar 5 Nilai optimal fungsi

adalah piecewise linear dan konveks. Break point dari terjadi pada

dan .

Set Optimal pada Interval Linear

Untuk setiap di domain kita notasikan set optimal ( ) oleh dan set

optimal ( ) oleh .

Teorema 5

Jika adalah linear pada interval [ , ], di mana < maka set

optimal dualnya adalah konstan untuk ( , ).

12

Bukti:

Ambil ( , ) sembarang dan sembarang. Karena adalah

optimal untuk kita memiliki

( ) ( )

dan, saat adalah masalah dual yang fisibel untuk semua β,

Diperoleh

( ) ( )

( ) ( )

Fungsi berbentuk linear pada [ , ] akan mengakibatkan

( )

( )

Dengan menggunakan aturan dan dapat mengakibatkan

( )

( )

Oleh karena itu, persamaan (11) berubah menjadi pertidaksamaan (12), dan

kemiringan pada interval tertutup [ , ] pada . Ini berarti bahwa turunan

terhadap pada interval terbuka ( , ) memenuhi

( ) Hal tersebut sama artinya dengan,

Dapat disimpulkan bahwa optimal untuk setiap dengan .

Karena adalah sembarang di dapat dikatakan bahwa

Karena adalah sembarang di interval terbuka , argumen di atas berlaku

untuk setiap , maka dapat dibuat

Sehingga dapat disimpulkan bahwa

dan

, maka

.

Bukti di atas menyatakan bahwa harus memiliki nilai yang sama

untuk setiap dan setiap dapat dinyatakan sebagai berikut.

Corollary 5.1

Menurut hipotesis dari Teorema 5,

Dengan kontinuitas dapat ditulis

Dapat menyiratkan konsekuensi lainnya.

Corollary 5.2

Berdasarkan hipotesis dari Teorema 5

untuk perubahan

, kemudian

Dalam hasil selanjutnya dapat sepakati dengan kebalikan dari implikasi

dari Teorema 5 disajikan dalam Teorema 6 berikut ini.

13

Teorema 6

Misalkan dan sedemikian rupa sehingga

.

Kemudian konstan untuk setiap dan linear pada interval

[ ].

Bukti:

Misalkan

. Kemudian

Pertimbangkan fungsi h linear:

[ ] Kemudian bertepatan dengan f di dan . Karena konveks dapat

mengakibatkan

[ ] Jadi fisibel untuk setiap [ ]. Karena adalah nilai optimal dari ,

Oleh karena itu, yang bertepatan dengan di [ ] . Berakibat, linear di

[ ] dan optimal untuk , bila [ ] . Karena sembarang di

berakibat pada

subset dari

untuk setiap .

Berdasarkan Teorema 5 dan Corollary 5.2 juga memiliki pernyataan sebaliknya

(inklusi converse). Set optimal dual di adalah konstan.

Selanjutnya akan ditunjukkan bahwa untuk setiap di domain kita

notasikan set optimal ( ) oleh dan set optimal ( ) oleh

, disajikan dalam

Teorema 7, Corollary 7.1, dan Corollary 7.2 berikut ini.

Teorema 7

Jika adalah linear pada interval [ ], di mana , maka set

optimal primal adalah konstan untuk .

Bukti: lihat Roos et al. 2006

Corollary 7.1 Berdasarkan hipotesis dari Teorema 7,

( )

Corollary 7.2

Berdasarkan hipotesis dari Teorema 7 ( )

untuk sembarang

( ). Maka ( )

( )

Dalam hasil selanjutnya dapat sepakati dengan kebalikan dari implikasi

pada Teorema 7 yang disajikan dalam Teorema 8 berikut ini.

Teorema 8

Misalkan dan sedemikian rupa sehingga

. Kemudian

adalah konstan untuk setiap [ ] dan adalah linear pada interval

[ ].

14

Bukti: lihat Roos et al. 2006.

Diberikan Contoh 4 yang mengacu pada Teorema 7 berikut ini.

Contoh 4

Dengan menggunakan masalah yang sama dengan Contoh 2 untuk setiap

, masalah ( ) didefinisikan sebagai berikut

( )

Kendala

Masalah Dual

( ) { }

Didapat vektor perturbasi untuk adalah Pada masalah ini didapatkan break point terjadi pada dan dan

Gambar 4 menerangkan bahwa adalah linear pada interval [ ]. Sehingga

kita mengambil , di mana yang diambil yakni , dan

.

Misalkan , sehingga menjadi

, Setara dengan

Masalah ini adalah masalah minimisasi maka solusi optimal yang didapat

yakni .


, Setara dengan


yakni .


, Setara dengan


yakni . Sehingga dapat disimpulkan bahwa set optimal

primal adalah konstan untuk .

Set Optimal di break point

Kembali ke fungsi pada bagian sebelumnya, jika bukan

break point maka banyaknya konstan untuk setiap . Jika domain

memiliki titik ekstrem dari kanan maka dapat dipertimbangkan turunan kanan

pada titik yang menjadi , dan jika domain dari memiliki titik ekstrem dari kiri

turunan kiri pada saat diambil . Kemudian adalah break point jika dan

hanya jika turunan kanan dan kiri di berbeda. Ini mengikuti dari definisi break

15

point. Dinotasikan turunan kiri dan kanan yakni dan

. Konveksitas

dari mengimplikasikan bahwa pada break point dapat di tulis

Lema 3

Misalkan , dan memiliki interior pada dom seperti yang

memiliki interval linear terbuka hanya di sebelah kanan dan ke interval

linear terbuka hanya di sebelah kiri Selain itu, dan

kemudian

{

}

{

}

Bukti: lihat Lampiran 3

Berdasarkan Lema 3, akan menjadi bentuk umum yang baik jika berlaku

adalah titik ekstrem pada domain sehingga dapat disajikan dalam Teorema 9

berikut ini.

Teorema 9

Misalkan dom dan akan ada solusi optimal dari . Kemudian

turunan pada β didefinisikan

{ }

{ }


Corollary 9.1

β bukan ekstrem break point dari f dan dan didefinisikan dalam

lema 3 sehingga menjadi

Corollary 9.2

{

}

{

}

Corollary 9.3

Dengan menganalogikan dual dari Lema 3 dan Teorema 9 sehingga dapat

disajikan dalam Lema 4 berikut ini.

Lema 4

Misalkan , dan memiliki interior pada dom( ), hanya interval

linear terbuka sebelah kanan, dan hanya interval linear terbuka sebelah kiri.

Selain itu, dan

. Kemudian menjadi

16

{

}

{

}


Berdasarkan Lema 4 diatas, akan menjadi bentuk umum yang baik jika

berlaku adalah titik ekstrem pada domain sehingga dapat disajikan dalam

Teorema 10 berikut ini.

Teorema 10

Misalkan dan akan ada solusi optimal dari .

Kemudian turunan pada didefinisikan

{ }

{ }


Corollary 10.1

Misalkan bukan ekstrem break point dari dan dan

didefinisikan dalam lema 4 sehingga menjadi

Corollary 10.2

{

}

{

}

Corollary 10.3

Diberikan Contoh 5 yang mengacu pada Lema 4 dan Teorema 10 berikut

ini.

Contoh 5

Dengan menggunakan masalah yang sama dengan Contoh 2 untuk setiap

, masalah ( ) didefinisikan sebagai berikut

( )

Kendala

Masalah Dual

( ) { }

Didapat vektor perturbasi untuk adalah Grafik digambarkan dalam Gambar 4, break point pada terjadi pada

dan Untuk solusi optimal pada ( ) adalah serta

. Pada break point set solusi optimal primal dapat diberikan

sebagai berikut

{ } Nilai ekstrem pada set ini adalah 2 dan 0. Nilai maksimal yang

terjadi untuk dan nilai minimal untuk . Oleh sebab itu,

17

turunan kiri dan kanan pada diberikan nilainya. Jika maka

solusi optimal masalah primal diberikan dan , sehinnga

turunan dari adalah 0 untuk wilayah ini. Pada break point set solusi

optimal primal dapat diberikan sebagai berikut

{ } Nilai ekstrem pada set ini adalah dan . Turunan kiri dan kanan

pada diberikan nilainya. Nilai maksimal yang terjadi untuk

dan nilai minimal untuk . Pada contoh ini, solusi optimal primal

didapatkan untuk setiap break point yang berdimensi satu, serta interval linear

terbuka pada solusi optimalnya selalu unik.

Titik Ekstrem di Interval Linear

Di bagian ini, asumsi yang digunakan yakni memiliki interior interval

linear [ ]. Diberikan solusi optimal akan ditunjukan bagaimana titik

ekstrem dan dari interval linear yang mengandung dapat ditentukan

dengan memecahkan dua masalah Linear Optimasi tambahan.

Teorema 11

Misalkan sembarang dan ( ) akan menjadi solusi optimal dari ( ).

Titik ekstrem dari interval linear [ ] mengandung dapat ditulis sebagai

berikut

{ }

{ }


Selanjutnya akan ditunjukkan bahwa menjadi break point dan ( )

akan menjadi pelengkap solusi optimal dari ( ).

Teorema 12

Misalkan menjadi break point dan ( ) akan menjadi pelengkap

solusi optimal dari ( ). Kemudian dan yang diberikan pada Teorema 11

didapat


Selanjutnya, asumsi yang digunakan yakni memiliki interior interval

linear [ ]. Diberikan solusi optimal akan ditunjukan bagaimana titik

ekstrem dan dari interval linear yang mengandung dapat ditentukan

dengan memecahkan dua masalah linear optimasi tambahan.

18

Teorema 13

Misalkan sembarang dan akan menjadi solusi optimal dari ( ). Titik

ekstrem dari interval linear [ ] mengandung dapat ditulis sebagai berikut

{ }

{ }


Selanjutnya akan ditunjukkan bahwa menjadi break point dan akan

menjadi pelengkap solusi optimal dari ( ).

Teorema 14

Misalkan menjadi break point dan akan menjadi pelengkap solusi

optimal dari ( ). Kemudian dan diberikan pada Teorema 13 didapatkan


Berikut ini diberikan Contoh 6 yang mengacu pada Teorema 13 dan

Teorema 14.

Contoh 6

Dengan menggunakan masalah yang sama dengan Contoh 5, dengan

menggunakan notasi pada Teorema 13 langkah selanjutnya menentukan interval

linear untuk . Dengan memverifikasi bahwa adalah optimal

untuk ( ). Oleh karena itu titik ekstrem dan dari interval linear yang

mengandung diikuti dengan meminimalkan dan memaksimalkan atas

wilayahnya

{ } Kendala terakhir menyiratkan , sehingga mempengaruhi kendala lain untuk

dan , dengan diberikan Oleh karena itu interval

linear mengandung adalah [ ]. Ketika , adalah optimal pada ( ), dan interval linear

mengandung dengan meminimalkan dan memaksimalkan di atas wilayah.

{ } Kendala terakhir menyiratkan , sehingga mempengaruhi kendala lain

untuk γ dan γ , setara dengan Oleh karena itu interval

linear mengandung adalah [ ] Ketika , adalah optimal pada , dan interval linear

mengandung dengan meminimalkan dan memaksimalkan di atas wilayah.

{ } Kendala terakhir menyiratkan , sehingga mempengaruhi kendala lain

untuk dan , setara dengan Oleh karena itu

interval linear mengandung adalah [ ] Perhatikan bahwa interval linear dihitung sesuai dengan Gambar 4.

Akhirnya dapat ditunjukkan penggunaan Teorema 14 pada break point.

19

Mengambil dapat dilihat bahwa adalah optimal untuk ,

dan diperlukan untuk meminimalkan dan memaksimalkan γ atas wilayah tersebut

{ } Kendala terakhir menyiratkan , sehingga mempengaruhi kendala lain untuk

dan , setara dengan dan dapat ditemukan

interval linear [ ] kiri dari 1. Ini karena juga optimal pada

interval ini. Ingat dari Contoh 4 bahwa set optimal pada diberikan oleh

{ } Jadi, bukannya solusi optimal sama baiknya bila menggunakan

strictly complementary solution . Kemudian perlu meminimalkan dan

memaksimalkan γ atas daerah

{ } Terakhir kendala sebesar , subsitusikan pada hasil Kendala

ketiga atau . Karena diiriskan dengan kendala kedua

didapatkan , dari . Dengan demikian, sesuai dengan

Teorema 14.

Prosedur Menemukan Semua break point dan Interval Linear

Dengan menggunakan hasil pada subbab sebelumnya, dalam bagian ini

akan dijelaskan algoritme yang menghasilkan nilai optimal fungsi untuk

perturbasi dimensi satu dari vektor b atau vektor c. Pertama-tama, perturbasi b

yang berdimensi satu dengan kelipatan skalar dari vektor dengan menyatakan

algoritme untuk perhitungan nilai optimal fungsi dan kemudian membuktikan

bahwa algoritme dapat menemukan semua break point dan interval linear.

Kemudian akan jelas bagaimana memperlakukan perturbasi dimensi satu c;

dengan menyatakan algoritme yang sesuai dan hasil konvergensi tanpa bukti lebih

lanjut.

Teorema berikut menyatakan bahwa algoritme ini dapat menentukan break

point dari yang berturut-turut pada garis real taknegatif, serta kemiringan dari

pada interval linear secara berturut-turut.

Teorema 15

Algoritme berakhir setelah jumlah iterasi terbatas. Jika adalah

banyaknya iterasi pada saat terakhir maka adalah break point dari

secara berturut-turut pada garis real taknegatif. Nilai optimal pada didapat dari dan kemiringan dari pada interval

didapat dari

Bukti: dalam iterasi pertama algoritme dimulai dengan langkah sebagai berikut

Di mana adalah vektor slack dalam solusi optimal

yang diberikan dari Masalah ini fisibel, karena (P) memiliki sebuah

solusi optimal dan memenuhi kendala. Oleh sebab itu masalah

tambahan pertama adalah takterbatas atau memiliki solusi optimal Menurut Teorema 11, yakni sama dengan titik ekstrem di sebelah kanan dari

interval linear yang mengandung 0. Jika masalah tak terbatas (ketika )

20

maka adalah linear pada dan algoritme berhenti; dengan kata lain

adalah break point pertama disebelah kanan dari 0. (perhatikan bahwa, apabila

terjadi Hal ini tentu mengakibatkan jika 0 adalah break point dari f dan

solusi dimulai adalah strictly complementary.) Jelas adalah primal

fisibel pada dan , didapat adalah optimal untuk

dengan mengasumsikan bahwa paruh kedua algoritme yang terjadi ketika masalah

ini memiliki solusi optimal, algoritme dapat dilakukan dengan pemecahan

masalah tambahan kedua

{ }

Menurut Teorema 9 nilai maksimal sama dengan turunan dari kanan di

. Jika masalah takterbatas maka adalah break point terbesar dari pada

dan untuk Dalam masalah ini sudah selesai sehingga

algoritme berhenti. Jika tidak, ketika masalah dibatasi, solusi optimal

adalah sedemikian rupa sehingga adalah sama dengan kemiringan pada

interval linear di sebelah kanan , hal ini berdasarkan Lema 3 Selain itu, akibat

dari Corollary 9.2, optimal dual pada interval terbuka linearitas sebelah

kanan . Oleh sebab itu, pada awal iterasi kedua adalah solusi optimal

pada interval terbuka sebelah kanan break point pertama pada [ Dengan

demikian, untuk memulai iterasi kedua dan selanjutnya seperti pada iterasi

pertama. Karena setiap iterasi menghasilkan Interval linear, dan hanya memiliki

banyak interval yang terbatas, maka algoritme berakhir setelah banyaknya iterasi

yang terbatas.

Berikut ini diberikan langkah-langkah untuk menemukan semua break

point dan interval linear pada nilai optimasi fungsi dengan dan

dalam buku (Roos et al. 2006). Untuk algoritme nilai optimasi fungsi secara

lengkap dapat dilihat di Lampiran 4.

Sebelum itu, akan diperkenalkan notasi-notasi untuk iterasi-iterasi yang

berurutan ini. Misalkan vektor adalah titik yang terletak pada daerah fisibel

masalah primal yang dihasilkan saat iterasi ke- . Vektor dan adalah titik

yang terletak pada daerah fisibel masalah dual yang dihasilkan saat iterasi ke- .

Algoritme atau langkah-langkah untuk mendapatkan break point, interval linear,

solusi optimal dan nilai optimal adalah sebagai berikut.adalah sebagai berikut.

Input : Matriks , vektor untuk masalah primal, vektor , vektor

untuk masalah dual, dan vektor .

Output : Menemukan semua break point dan interval linear.

Inisialisasi Misalkan solusi optimal dengan , ,

dan .

Langkah 1. Hitung parameter pada solusi persamaan (29) jika atau

Hitung parameter pada solusi persamaan (28) jika .

Langkah 2. Selama masalah terbatas lanjut ke Langkah 3; selainnya,

BERHENTI .

21

Langkah 3. Hitung pada solusi persamaan (19) untuk atau Hitung

pada solusi persamaan (18) untuk .


BERHENTI.

Langkah 5. Perbarui solusi,

Selanjutnya , kembali ke Langkah 1 (Roos et al. 2006).

Ketika vektor c adalah perturbasi oleh kelipatan skalar dari untuk

hal ini bertujuan untuk menemukan nilai optimal fungsi .

Dengan mengetahui bahwa adalah konkaf. Hal tersebut menyebabkan masalah

tambahan kedua di algoritme ini adalah masalah minimisasi.

Teorema berikut menyatakan bahwa algoritme ini dapat menentukan break

point dari yang berturut-turut pada garis real taknegatif, serta kemiringan dari

pada interval linear secara berturut-turut.

Teorema 16

Algoritme berakhir setelah jumlah iterasi terbatas. Jika K adalah

banyaknya iterasi pada saat terakhir maka adalah break point dari

secara berturut-turut pada garis real taknegatif. Nilai optimal pada didapat dari dan kemiringan dari pada interval

didapat dari

Bukti: seperti Teorema 15

Berikut ini diberikan langkah-langkah untuk menemukan semua break

point dan interval linear pada nilai optimasi fungsi dengan dan

dalam buku (Roos et al. 2006). Untuk algoritme nilai optimasi fungsi secara

lengkap dapat dilihat di Lampiran 6.

Sebelum itu, akan diperkenalkan notasi-notasi untuk iterasi-iterasi yang

berurutan ini. Misalkan vektor adalah titik yang terletak pada daerah fisibel

masalah primal yang dihasilkan saat iterasi ke- . Vektor adalah titik yang

terletak pada daerah fisibel masalah dual yang dihasilkan saat iterasi ke- .

Algoritme atau langkah-langkah untuk mendapatkan break point, interval linear,

solusi optimal dan nilai optimal adalah sebagai berikut.

Input : Matriks , vektor untuk masalah primal dan vektor Perturbasi

Output : Menemukan semua break point dan interval linear.

Inisialisasi Misalkan solusi optimal dengan dan .

22

Langkah 1. Hitung parameter pada solusi persamaan (31) jika atau

Hitung parameter pada solusi persamaan (30) jika .


BERHENTI.

Langkah 3. Hitung pada solusi persamaan (25) untuk atau Hitung

pada solusi persamaan (24) untuk .


BERHENTI.

Langkah 5. Perbarui solusi,

Selanjutnya , kembali ke Langkah 1 (Roos et al. 2006).

Contoh Aplikasi

Selanjutnya akan dibahas mengenai dua contoh aplikasi dari analisis

parametrik pada masalah optimasi linear yang diperoleh dengan menjalankan

algoritme yang diperoleh dari corollary, lema, dan teorema yang dibuktikan dalam

bab Hasil dan Pembahasan.

Contoh Aplikasi 1 (Perubahan Parameter pada Koefisien Fungsi Tujuan)

(P) { } Dan masalah dualnya

(D) { } Didapatkan

[ ], [ ], [ ].

dengan vektor perturbasi yakni

Sehingga dapat ditulis

(P) { } Dan masalah dualnya

(D) { } Dan menghitung interval linear dari Lema 4 dibutuhkan pengetahuan bahwa suatu

solusi optimal primal untuk beberapa interval. Sehingga input pada Contoh

Aplikasi 1 adalah

23

Kasus Nilai Optimal Fungsi

Iterasi ke-1


Langkah 1. Hitung parameter pada solusi persamaan (31)

{ }

Dimulai dengan sebagai calon break point yang pertama serta nilai optimal

pada saat break point ini adalah

Langkah 2. Masalah terbatas maka lanjut ke Langkah 3.

Langkah 3. Hitung pada solusi persamaan (25).

{ }

terlihat bahwa dan adalah minimal jika . Sehingga dapat

ditemukan suatu solusi optimal untuk interval linear yang hanya di sebelah

kanan pada dan kemiringan dari di interval ini.


Langkah 5. Perbarui solusi optimal dengan , dan . Lanjut ke langkah 2.

Iterasi ke-2


{ }

Dengan mudah kita lihat bahwa adalah optimal dengan Sehingga

dapat ditentukan calon break poin kedua dan nilai optimal



{ }

terlihat bahwa dan adalah minimal jika dan .

Sehingga dapat ditemukan suatu solusi optimal untuk interval linear yang

hanya di sebelah kanan pada dan kemiringan dari di interval ini.


24


Iterasi ke-3


{ }

Perhatikan bahwa dan masalah menjadi setara dengan

{ }

Langkah 2. Masalah tidak terbatas maka BERHENTI.


Iterasi ke-1



{ }

karena ini setara dengan

{ }

Dimulai sebagai calon break point pertama dan solusi optimal pada break

point ini diberikan oleh



{ }

terlihat bahwa dan adalah maksimal jika . Sehingga dapat

ditemukan suatu solusi optimal untuk interval linear yang hanya di sebelah

kiri pada dan kemiringan dari di interval ini.



Iterasi ke-2


{ }

karena ini setara dengan

{ }

25

Jadi calon break point kedua dan solusi optimal pada break point ini diberikan

oleh



{ }

kasus ini setara dengan

{ }

Karena adalah maksimal jika dan . Sehingga dapat ditentukan

suatu solusi optimal untuk interval linear yang hanya disebelah kiri dan

kemiringan dari g di interval ini.



Iterasi ke-3


{ }

perhatikan bahwa dan masalah menjadi seperti

{ }


Untuk melengkapi perhitungan nilai optimal fungsi pada contoh ini

dapat dilihat di Gambar 6.

Gambar 6 Hasil analisis dari Contoh Aplikasi 1

26

Contoh Aplikasi 2 (Perubahan Parameter pada Koefisien Nilai Ruas Kanan)

Diberikan masalah primal

(P) { } dan masalah dualnya

(D) { }. Didapatkan

[

], [ ], [

].

Di dapatkan vektor perturbasi b dengan kelipatan skalar yakni

[

]

Sehingga dapat ditulis.

(P) { } (D) { }.

Dengan menggunakan algoritme untuk menentukan break point dan interval linear

dari Sehingga solusi optimal (P) dan (D) diketahui sebagai input.

.


Iterasi ke-1

Inisialisasi Misalkan solusi optimal dengan , dan .


{ }

Dimulai dengan β sebagai calon break point yang pertama serta nilai optimal

pada saat break point ini adalah



{ }

Maka dan adalah maksimum jika

dan . Sehingga dapat ditentukan solusi optimal untuk interval

linear yang hanya disebelah kanan dan kemiringan dari di interval ini:


27

Langkah 5. Perbarui solusi optimal dengan , dan . Lanjut ke langkah 1

Iterasi ke-2


{ }

Dari dapat disimpulkan bahwa dan didapatkan hasil

β sebagai calon break point yang kedua serta nilai optimal pada saat break

point ini adalah



{ }

Maka dan adalah maksimal jika .

Sehingga dapat ditentukan solusi optimal untuk interval linear yang

hanya disebelah kanan β dan kemiringan dari di interval ini:


Langkah 5. Perbarui solusi optimal dengan , dan . Lanjut ke langkah 1

Iterasi ke-3


{ }

setara dengan

{ }



Iterasi ke-1

Inisialisasi Misalkan solusi optimal dengan , dan .


{ }

Dimula β sebagai calon break point yang pertama serta nilai optimal pada

saat break point ini adalah

28



{ }

Maka dan adalah minimal jika

dan . Sehingga dapat ditentukan solusi optimal untuk interval

linear yang hanya disebelah kiri dan kemiringan dari di interval ini,



Iterasi ke-2


{ }

Dari dan didapatkan hasil β sebagai calon break point

yang kedua serta nilai optimal pada saat break point ini adalah



{ }

Setara dengan

{ }

Langkah 4. Masalah tidak terbatas karena Sehingga

BERHENTI.

Untuk melengkapi perhitungan nilai optimal fungsi pada contoh ini dapat

dilihat di Gambar 7

29

Gambar 7 Hasil analisis dari Contoh Aplikasi 2

SIMPULAN DAN SARAN

Simpulan

Berdasarkan pembahasan yang telah diuraikan sebelumnya, dapat

disimpulkan bahwa analisis parametrik adalah analisis sensitifitas sistematis yang

sangat berguna untuk memeriksa dampak dari perubahan parameter secara

kontinu terhadap solusi optimal. Masalah analisis parametrik memperkenankan

parameter terpilih ( atau ) diubah secara kontinu pada interval tertentu dengan

menggunakan sifat-sifatnya. Sifat-sifat dari analisis parametrik adalah (1) nilai

optimal fungsi dengan adanya perubahan parameter-parameter pada koefisien

fungsi tujuan dan nilai ruas kanan pada masalah optimasi linear adalah kontinu,

konkaf/konveks dan piecewise linear, (2) pada suatu interval tertentu perubahan

parameter tidak akan mengubah solusi optimalnya, (3) break point adalah suatu

titik di mana solusi optimal akan berubah bila terjadi perubahan parameter dari

sisi kiri break point ke sisi kanannya, dan (4) terdapat titik ektrem yang juga

merupakan break point. Algoritme yang disajikan dapat menentukan semua break

point dan interval linear dalam suatu optimasi linear.

Saran

Bagi yang berminat untuk memperluas tema dari karya ilmiah ini, penulis

menyarankan untuk membahas penentuan solusi optimal dan nilai optimal analisis

parametrik terhadap optimasi linear menggunakan teknik komputasi berupa

pemakaian software optimasi untuk mempermudah mendapatkan solusi optimal

dan nilai optimal.

30

DAFTAR PUSTAKA

Anton H, Rorres C. 2005. Elementary Linear Algebra. Ed-ke-9. New Jersey (US):

J Wiley.

Bazaraa MS, HD Sherali & CM Shetty. 1993. Nonlinear Programming: Theory

and Algorithms. ed. New Jersey (US): John Wiley.

Dumaria Lestaurika Tambunan. 2007. Menentukan Solusi Optimal Program

Linear Parametrik Dengan Menggunakan Metode Simplex [Skripsi]. Medan

(ID): Universitas Sumatra Utara

Leon SJ. 1998. Linear Algebra with Applications. Ed ke-5. London: Springer.

Nash SG, Sofer A. 1996. Linear and Nonlinear Programming. New York (US):

McGraw-Hill.

Peressini AL, Sullivan FE, Uhl JJ. 1988. The Mathematics of Nonlinear

Programming. New York (US): Springer-Verlag.

Roos C, Terlaky T, Vial J-Ph. 2006. Interior Point Methods for Linear

Optimization. New York (US): Springer.

Winston WL. 2004. Operations Reserch Applications and Algorithms Ed ke-4.

New York (US): Duxbury.

Yusep Maulana. 2009. Penyelesaian Integer Programming Dengan Metode

Relaksasi Lagrange [Skripsi]. Bogor (ID): Institut Pertanian Bogor.

31

Lampiran 1 Pembuktian domain dari adalah konveks

Diberikan , dom dan < < . Kemudian dan adalah terbatas, yang berarti bahwa kedua

dan yang tidak kosong.

Diberikan dan

. Kemudian dan adalah nonnegatif dan

Sekarang perhatikan

Perhatikan bahwa x adalah kombinasi konveks dari dan dan

karenanya adalah nonnegatif. Kita melanjutkan dengan menunjukkan

bahwa . Menggunakan bahwa

Dengan menggunakan persamaan (3) sehingga

Ini membuktikan bahwa ( ) adalah fisibel dan karenanya dom

32

Lampiran 2 Pembuktian pelengkap dari domain adalah subset terbuka dari garis

nyata

Ambil dom . Ini berarti bahwa ( ) adalah takterbatas. Ini setara

dengan keberadaan vektor sedemikian rupa sehingga

Menetapkan z dan mempertimbangkan sebagai variabel, himpunan semua

yang memenuhi ketidaksetaraan secara ketat/sempurna adalah

interval terbuka. Untuk semua dalam interval ini ( ) takterbatas. Oleh karena

itu domain dari g adalah terbuka.

Lampiran 3 Pembutktian Lema 4

Diberikan bukti , dan bukti

tidak dijelaskan karena sama

caranya. Karena adalah optimal untuk didapatkan

Didapatkan juga berdasarkan teorema 5 dan corollary 5.2

mengakibatkan

Mengurangi kedua ruas persamaan ini akan menyebabkan

Dengan membagi kedua ruas oleh bilangan positif didapatkan

ini akan membuktikan bahwa

{ }

Karena berdasarkan corollary 5.1.

33

Lampiran 4 Algoritme Nilai Optimal Fungsi dan

Nilai Optimal Fungsi

Input:

Solusi Optimal dari (D);

Vektor Perturbasi .

begin

k:=1; ; ready: false;

while not ready do

begin

Solve { }

if masalah ini adalah takterbatas: ready:=true

else adalah solusi optimal;

begin

Solve { }

if masalah ini adalah takterbatas: ready:= true


k:=k+1;

end

end

end


Input:

Solusi Optimal dari (D);

Vektor Perturbasi .

begin

k:=1; ; ready: false;

while not ready do

begin

Solve { }



begin

Solve { }



k:=k+1;

end

end

end

34

Lampiran 5 Algoritme Nilai Optimal Fungsi dan


Input:

Solusi Optimal dari (P);

Vektor Perturbasi .

begin

ready: false;

k:=1; while not ready do

begin

Solve { }



begin

Solve { }



k:=k+1

end

end

end


Input:

Solusi Optimal dari (P);

Vektor Perturbasi .

begin

ready: false;

k:=1; while not ready do

begin

Solve { }



begin

Solve { }



k:=k+1;

end

end

end

35

RIWAYAT HIDUP

Penulis dilahirkan di Jakarta pada tanggal 21 Januari 1992 dari ayah

Supendi dan ibu Manzilah (Alm). Penulis merupakan putra kedua dari enam

bersaudara. Pada tahun 2003, penulis lulus dari SD Negeri Duren Tiga 15 pagi

Jakarta. Pada tahun 2006, penulis lulus dari SMP Negeri 238 Jakarta. Pada tahun

2009, penulis lulus dari SMA Negeri 60 Jakarta dan pada tahun yang sama

diterima sebagai mahasiswa IPB melalui jalur Undangan Seleksi Masuk IPB

(USMI). Penulis memilih mayor Matematika minor Kewirausahaan Agribisnis,

Departemen Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam.

Selama mengikuti perkuliahan, penulis menjadi asisten mata kuliah

Analisis Numerik (S1) pada semester ganjil tahun akademik 2012-2013, asisten

mata kuliah Pemrograman Linear (S1) pada semester genap tahun akademik 2012-

2013. Penulis mendapatkan beasiswa dari Bantuan Belajar Mahasiswa (BBM)

IPB pada semester pertama tahun 2009 sampai semester delapan tahun 2013.

Penulis aktif di berbagai kegiatan kemahasiswaan seperti organisasi

maupun kepanitiaan. Kepanitiaan yang perah diikuti yakni menjadi panitia dalam

Masa Perkenalan Kampus Mahasiswa Baru (MPKMB) 2010 dan menjadi panitia

dalam Masa Perkenalan Fakultas MIPA 2011. Dalam berorganisasi, penulis

pernah memegang amanah selama dua periode sebagai Ketua Komisi IV Dewan

Perwakilan Mahasiswa Fakultas Matematika dan Ilmu Pengetahuan Alam Institut

Pertanian Bogor (Dewan Epicentrum dan Dewan Zwiterium) tahun 2011-2012.

penentuan solusi optimal dan nilai optimal … · sistem persamaan linear, matriks, optimasi...

Documents