BAB 1 PENDAHULUAN
1.1. Latar Belakang Dalam keadaan dimana menghadapi persoalan program linier yang besar, maka akan berusaha untuk mencari penyelesaian optimal dengan menggunakan algoritma komputasi, seperti algoritma simpleks dengan biaya sekecil mungkin. Salah satu variasi model program linier adalah pemrograman separabel. Pemrograman separabel adalah pemrograman tak linear yang fungsi objektif dan fungsi kendalanya dapat diekspresikan sebagai penjumlahan fungsi dan setiap fungsinya hanya terdiri atas satu variabel. Secara umum model dasar dari suatu pemrograman separabel adalah sebagai berikut: n
Optimumkan
Z f x1 , x2 ,..., xn f j x j j 1
Fungsi kendala : n
gi x1 , x2 ,..., xn gij x j atau bi j 1
xj 0
Untuk i = 1,2,..,m j = 1,2,..,n Banyak aplikasi masalah yang dapat diselesaikan dengan pemrograman separabel antara lain masalah fitting, ekonometrik, analisis jaringan listrik, desain dan manajemen sistem suplai air, logistik, dan statistik.
Universitas Sumatera Utara
2
Pemrograman separabel hanya digunakan untuk menganalisis persoalanpersoalan yang memiliki fungsi-fungsi kontinu dengan perubahan gradien yang kecil. Jika fungsi kontinu mengalami perubahan besar pada gradiennya, maka dapat menerapkan program integer tercampur. Sifat lainnya adalah pemrograman separabel memberikan optimum pada fungsi nonlinear, sedangkan program integer dapat memberikan global optimum. Pada umumnya masalah pemrograman separabel dapat diselesaikan dengan menggunakan kondisi Karush-Kuhn-Tucker. Selain itu dapat juga diselesaikan dengan menggunakan hampiran fungsi linier piecewise, atau dengan metode lain seperti metode cutting plane, program dinamik, dan lain-lain. Pada tulisan ini akan membahas masalah pengoptimuman yang menghampiri masalah pemrograman separabel. Hampiran dilakukan dengan mengganti setiap fungsi nonlinier dengan fungsi linier piecewise. Suatu fungsi tujuan f j ( x j ) dalam pemrograman separabel dikatakan putusbersambung (piece-wise) karena segmen-segmen dari fungsi f j ( x j ) tersebut secara sendiri-sendiri (terputus-putus) dipisah-pisahkan dan membentuk fungsi yang linier sehingga diperoleh f1 ( x1 ), f 2 ( x2 ), f 3 ( x3 ) , dan seterusnya. Jika fungsi yang diputusputus tersebut disambung, maka hasilnya diperkirakan akan mendekati fungsi nonlinier. Pada pemrograman separabel, ada tiga kondisi yaitu fungsi tujuannya nonlinier, fungsi kendalanya linier, atau fungsi tujuan dan kendalanya nonlinier. Sehingga pada ketiga kondisi tersebut dapat diganti dengan fungsi linier yang dianggap sama atau mendekati keadaan nonlinier, yaitu dengan cara membagi suatu bidang fungsi nonlinier menjadi beberapa sub bidang atau segmen. Setelah membagi suatu bidang fungsi nonlinier menjadi beberapa sub bidang, ada dua cara untuk memformulasikan fungsi linier piecewise, yaitu dengan formulasi lambda dan formulasi delta.
Universitas Sumatera Utara
3
Penyelesaian masalah hampiran fungsi linier piecewise dapat juga diselesaikan metode simpleks dengan restricted basis entry rule (variabel terbatas). Jika fungsi objektifnya merupakan fungsi konveks sempurna dan fungsi kendalanya merupakan konveks, maka aturan variabel terbatas pada metode simpleks dapat dihilangkan dan bisa digunakan hanya dengan metode simpleks biasa. Keakuratan dari hampiran fungsi linier piecewise dipengaruhi oleh banyaknya titik kisi. Jika titik kisi bertambah, maka variabel pada masalah hampiran pemrograman linier akan bertambah. Untuk mengatasi hal tersebut, dapat digunakan modifikasi metode hampiran yang menggunakan sedikit titik kisi diawal perhitungan. Misalkan
f ( x) dan g ( x) memenuhi semua asumsi dari pemrograman
separabel dan fungsi linier bagian demi bagian yang diperoleh, dapat dituliskan kembali sebagai fungsi linier dengan menghapus indeks khusus pada suatu model pemrograman linier, maka penyelesaian optimalnya secara otomatis memenuhi suatu batasan yang diberikan. Cara efisien dan cepat untuk menyelesaikan model tersebut adalah dengan menggunakan jenis tertentu dari metode simpleks yang berhubungan dengan batas atas kendala. Kemudian setelah memperoleh suatu penyelesaian optimal dari model nj
tersebut, maka hitunglah secara berurutan x j x jk , dengan j=1,2,...,n untuk k 1
melihat penyelesaian yang optimal dari pemrograman separabel sebelumnya (yang didekati secara bagian demi bagian). Dari uraian di atas, maka penulis memilih judul ” Penyelesaian Pemrograman
Separabel
Menggunakan
fungsi
linier
Piecewise
dengan
Formulasi Delta”.
Universitas Sumatera Utara
4
1.2. Perumusan Masalah Permasalahan yang akan diuraikan dalam tulisan ini adalah bagaimana cara mengoptimumkan masalah pada pemrograman separabel. Di mana pada pemrograman ini, fungsi yang nonlinier dapat diselesaikan dengan hampiran fungsi linier piecewise dengan menggunakan formulasi delta.
1.3. Pembatasan Masalah Ada dua cara untuk memformulasikan fungsi linier piecewise, yaitu dengan formulasi lambda dan formulasi delta. Pada formulasi lambda, variabel didefinisikan untuk setiap titik kisi, sedangkan formulasi delta, variabel didefinisikan untuk setiap interval diantara titik kisi. Akan tetapi pada tulisan ini untuk membatasi persoalan, maka hanya akan membahas fungsi linier piecewise dengan formulasi delta. Karena, untuk formulasi lambda telah dibahas pada tulisan sebelumnya.
1.4. Tujuan Penelitian Tujuan
penelitian
pemrograman
dari
separabel
penulisan dengan
ini
adalah
hampiran
menyelesaikan
fungsi
linier
permasalahan
piecewise
dengan
menggunakan formulasi delta tanpa harus mengabaikan kendala yang ada, kemudian mengoptimalkan fungsi tujuan dari pemrograman separabel.
1.5. Manfaat Penelitian Dengan adanya penelitian ini diharapkan dapat bermanfaat untuk menyelesaikan permasalahan pengoptimalan pada pemrograman separabel dengan menggunakan hampiran fungsi linier piecewise dengan formulasi delta. Permasalahan pengoptimalan
Universitas Sumatera Utara
5
yang dimaksud adalah memaksimumkan atau meminimumkan fungsi tujuan dari pemrograman separabel.
1.6. Metode Penelitian Untuk melancarkan penelitian ini, maka metode yang dilakukan adalah dengan studi literatur. Oleh karena itu, ada beberapa tahap yang dilakukan dalam pemecahan masalah yang dihadapi, yaitu: 1. Menjelaskan pengertian dasar pemrograman separabel, 2. Menjelaskan pemrograman separabel dengan menggunakan hampiran fungsi linier piecewise, 3. Menjelaskan pengertian formulasi lambda dan formulasi delta, 4. Menyelesaikan suatu masalah sebagai aplikasi dari hampiran fungsi linier piecewise dengan formulasi delta.
1.7. Tinjauan Pustaka Hiller dan Liberman (1990) mengatakan pemrograman separabel dapat diasumsikan bahwa fungsi objektif f ( x) disebut konkaf, dan fungsi konstrain g i ( x) disebut konfek merupakan fungsi-fungsi dari pemrograman separabel. Model dasar program separabel adalah sebagai berikut: Optimumkan ( maksimumkan atau minimumkan ): n
Z f x1 , x2 ,..., xn f j x j j 1
Fungsi kendala : n
gi x1 , x2 ,..., xn gij x j atau bi j 1
xj 0
Untuk i = 1,2,..,m dan j = 1,2,..,n dimana fungsi g ij ( x j ) adalah konveks (cembung) dan f j ( x j ) adalah konkaf (cekung).
Universitas Sumatera Utara
6
Contoh : Min
Z 30 x1 35 x2 212 3 x22
Kendala
x12 2 x22 250
x1 x2 20 x1 , x2 0 Untuk persoalan pengoptimuman contoh tersebut yang merupakan sebuah persoalan pemrograman separabel dengan : f1 ( x1 ) 30 x1 2 x12
f 2 ( x2 ) 35 x2 3 x22
g11 ( x1 ) x12
g12 ( x2 ) 2 x22
g 21 ( x1 ) x1
g 22 ( x2 ) x2
b1 250
b2 20
B.D. Nasendi dan Affendi Anwar (1984) menjelaskan jenis-jenis variasi model program linier, menjelaskan pengertian program separabel dan model dasar dari suatu pemrograman separabel. Fungsi f(x) dikatakan dapat dipisahkan (separabel) jika dapat menuliskan fungsi tersebut sebagai jumlah dari n buah fungsi yang terpisah-pisah. Secara sistematis, pernyataan tersebut adalah sebagai berikut: Z f ( x) f ( x1 , x2 ,..., xn ) adalah separabel, Jika
f ( x1 , x2 ,..., xn ) f1 ( x1 ) f 2 ( x2 ) ... f n ( xn )
Suatu fungsi tujuan
f j (xj )
dalam program separabel disebut putus-
bersambung (piece-wise) karena segmen-segmen dari fungsi f j ( x j ) tersebut secara sendiri-sendiri, dipisah-pisahkan dan membentuk fungsi yang linier sehingga dapat f1 ( x1 ), f 2 ( x2 ), f 3 ( x3 ) , dan seterusnya. Jika fungsi yang diputus-putus tadi disambung, maka hasilnya diperkirakan akan mendekati fungsi nonlinier. Jurnal dari Andrew dan Wolsey (2001) dengan judul Discrete Lot-Sizing and Convex Integer Program menjelaskan bahwa setelah membagi suatu bidang fungsi
Universitas Sumatera Utara
7
nonlinier ke dalam beberapa sub-bidang, ada dua cara untuk memformulasikan fungsi linier putus-bersambung, yaitu dengan formulasi lambda dan formulasi delta. Buku lain karangan Winston (1995) menjelaskan bahwa fungsi yang didefinisikan oleh rumus yang berlainan dibagian yang berbeda dari daerah asalnya dinamakan fungsi putus-bersambung. F.S.Hiller, G.J.Lieberman, E.Gunawan, A.W.Mulia (1994) menjelaskan bahwa dalam pemrograman separabel diasumsikan fungsi tujuannya yaitu f ( x) adalah cekung dan semua fungsi kendalanya yaitu gi ( x) cembung serta semua fungsifungsinya yang terlibat adalah fungsi separabel (fungsi yang dapat dibuat dari bentukbentuk yang hanya memuat satu peubah). Pendekatan suatu fungsi dengan fungsi linier bagian demi bagian merupakan cara pendekatan yang sangat dibutuhkan pada masalah pemrograman separabel.
Universitas Sumatera Utara
