PEMROGRAMAN INTEGER DENGAN FUNGSI OBJEKTIF LINEAR SEPOTONG - SEPOTONG
Oleh : FEBIANA RESI SAPTA G54102037
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR 2008
ABSTRACT FEBIANA RESI SAPTA. Integer Programming with Piecewise Linear Objective Function. Supervised by PRAPTO TRI SUPRIYO and SISWANDI. Integer Linear programming (ILP/IP) can not be used to finish problems containing piecewise linear objective function, because basically piecewise linear function is not representing a linear function. This article give an method to express piecewise linear function as linear function, so that problem ILP with piecewise linear objective function can be expressed as ILP in the standard form. This matter can be done with two steps, the first step is to change the piecewise linear objective function ( f ( x ) ) becomes z1 f (b1 ) + z 2 f (b2 ) + ... + zn f (bn ), where b1 , b2 , ..., bn represent break points. The Second step is adding new constraints so that the formula at step one can be used.
ABSTRAK FEBIANA RESI SAPTA. Integer Programming dengan Fungsi Objektif Linear SepotongSepotong. Dibimbing oleh PRAPTO TRI SUPRIYO dan SISWANDI. Integer Linear Programming (ILP) tidak dapat digunakan untuk menyelesaikan permasalahan yang mengandung fungsi objektif linear sepotong-sepotong, karena pada dasarnya fungsi linear sepotong-sepotong bukan merupakan fungsi linear. Tulisan ini memberikan suatu metode untuk menyatakan fungsi linear sepotong-sepotong sebagai fungsi linear, sehingga masalah ILP dengan fungsi objektif linear sepotong-sepotong dapat dinyatakan sebagai ILP dalam bentuk standar. Hal ini dapat dilakukan dengan dua langkah, langkah pertama adalah merubah fungsi objektif linear sepotong-sepotong ( f ( x ) ) menjadi z1 f (b1 ) + z 2 f (b2 ) + ... + zn f (bn ), dimana
b1 , b2 , ..., bn merupakan break point. Kemudian langkah kedua menambahkan kendala-kendala baru sedemikian sehingga formula pada langkah satu dapat berfungsi.
PEMROGRAMAN INTEGER DENGAN FUNGSI OBJEKTIF LINEAR SEPOTONG - SEPOTONG
Skripsi Sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains Pada Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Pertanian Bogor
Oleh : FEBIANA RESI SAPTA G54102037
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2008
Judul :
Pemrograman Integer dengan Fungsi Objektif Linear Sepotong- Sepotong Nama : Febiana Resi Sapta NIM : G54102037
Menyetujui:
Pembimbing I,
Pembimbing II,
Drs. Prapto Tri Supriyo, M.Kom. NIP 131878952
Drs. Siswandi, M.Si. NIP 131957320
Mengetahui Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Pertanian Bogor
Dr. drh. Hasim, DEA. NIP 131578806
Tanggal Lulus :
RIWAYAT HIDUP Penulis dilahirkan di Ciamis pada tanggal 18 februari 1984, penulis merupakan putra keempat dari pasangan Bapak Djuarman Tanuwirya dan Ibu Tarsini Yahya. Pada tahun 2002 penulis lulus dari SMU Negri 1 Cibadak Sukabumi, dan diterima untuk melanjutkan kuliah di Institut Pertanian Bogor mengambil jurusan Matematika dan Ilmu Pengetahuan Alam. Selama menempa ilmu perkuliahan, penulis juga menjalani aktifitas lain, yaitu berorganisasi di dalam dan luar kampus. Di dalam kampus penulis pernah menjabat sebagai Ketua GUMATIKA (Himpunan Mahasiswa Matematika), Dewan Pembina HIMASI (Himpunan Mahasiswa Sukabumi), Dewan Pembina KBMGJ (Himpunan Mahasiswa Ciamis Jabodetabek), dan menjadi kepanitian di berbagai kegiatan BEM FMIPA. Sedangkan di luar Kampus penulis aktif sebagai Sekretaris Jendral di DAMAS (Daya Mahasiswa Sunda) cabang Bogor, Kordinator Wilayah VI (Bogor, Sukabumi, Cianjur) BARA SUNDA (Barisan Putra Sunda), Kordinator Wilayah Bogor GEMA JABAR (Gerakan Masyarakat Jawa Barat), Pengurus Widang Pariwisata DPD KNPI Kota Bogor, dan sering terlibat serta diberi tanggung jawab untuk melaksanakan sebuah kegiatan oleh Pemda Kabupaten dan Kota Bogor.
PRAKATA Puji syukur penulis haturkan ke hadirat Allah SWT yang telah memberi nikmat sehat jasmani maupun rohani sehingga penulis dapat menyelesaikan skripsi ini. Shalawat serta salam tercurah kepada junjungan nabi besar Muhammad SAW yang telah memberikan contoh teladan agar tidak tersesat dalam menjalani hidup. Pada kesempatan ini penulis ingin mengucapkan banyak terima kasih kepada semua pihak yang telah membantu penulis dalam menyelesaikan skripsi ini, diantara lain : • Bapak Drs. Prapto Tri Supriyo, M.Kom dan Bapak Drs. Siswandi, M.Si Selaku dosen pembimbing yang senantiasa sabar memberikan bimbingan dan arahan sampai skripsi ini dapat selesai. • Bapak Donny Citra Lesmana, M.Sc sebagai dosen penguji atas saran dan masukannya. • Keluarga tercinta, mamih, kaka, aa, emas, eneng, serta bi mamah yang telah memberikan dorongan moril dan materil yang mungkin sampai kapanpun takan terbalaskan. • Dhita Swaditra sebagi sumber inspirasiku • Seluruh dosen beserta staf Departemen Matematika atas ilmunya yang tak ternilai. • Teman-teman angkatan 39 terutama irwan, kabul, arip, fitrah yang sekian lama senasib sepenanggungan. • Rekan-rekan seperjuangan angkatan 35, 36, 37, 38, 40 dan 41. • Dulur-dulur di DAMAS • Seluruh pihak yang telah membantu terselesaikannya skripsi ini yang tidak dapat disebutkan satu per satu. Penulis sadar sepenuhnya bahwa banyak sekali kekurangan dalam penyusunan skripsi ini. Harapan penulis adalah bahwa karya ilmiah ini akan dapat memberikan banyak manfaat bagi penulis maupun para pembacanya.
Bogor,
Agustus 2008
FEBIANA RESI SAPTA
DAFTAR ISI I.
II.
Halaman PENDAHULUAN 1.1 Latar Belakang ............................................................................................. 1 1.2 Tujuan .......................................................................................................... 1 LANDASAN TEORI 2.1 Pemrograman Linear.................................................................................... 2.2 Pemrograman Linear Bilangan Bulat........................................................... 2.3 Metode Branch and Bound untuk menyelesaikan masalah Pemrograman Linear Bilangan Bulat ..................................................................................
2
III.
PEMBAHASAN ................................................................................................
5
IV.
CONTOH KASUS.............................................................................................
7
V.
SIMPULAN DAN SARAN 5.1 Simpulan ..................................................................................................... 5.2 Saran ...........................................................................................................
9 9
DAFTAR PUSTAKA...................................................................................................
9
LAMPIRAN .................................................................................................................
10
1 2
I PENDAHULUAN 1.1 Latar Belakang Banyak masalah dalam dunia nyata yang dapat diformulasikan ke dalam model matematika. Misalnya masalah dalam pendistribusian barang, penentuan rute kendaraan, penjadwalan mata pelajaran dan masih banyak lagi. Riset operasi merupakan salah satu metode yang sering digunakan untuk memformulasikan, menganalisa, dan menentukan solusi optimum dari masalahmasalah tersebut. Tahap-tahap yang harus dilalui untuk melakukan sebuah studi riset operasi mencakup: (1) Definisi masalah; (2) Pengembangan model; (3) Pemecahan
model; (4) Pegujian keabsahan model; (5) Implementasi hasil akhir. Pada karya ilmiah ini akan dibahas mengenai pemodelan dalam bentuk integer programming dengan fungsi objektif linear sepotong-sepotong (piecewise linear functions). 1.2 Tujuan Tujuan penulisan karya ilmiah ini adalah memberikan metode untuk menyelesaikan masalah integer programming dengan fungsi objektif linear sepotong-sepotong.
II LANDASAN TEORI 2.1 Pemrograman Linear Pemrograman linear adalah pemodelan secara matematis dari suatu masalah nyata untuk mencari solusi optimum yang memenuhi sejumlah kendala tertentu. Fungsi yang dioptimalkan disebut dengan fungsi objektif yang merupakan suatu fungsi linear. Kendalanya dapat berupa persamaan atau pertidaksamaan linear. Dalam bentuk matriks-vektor masalah pemrograman linear standar dapat dituliskan sebagai berikut : Maksimumkan Dengan kendala
f ( x1 , x2 , ..., xn ) = c1x1 + c2 x2 + ... + cn xn .
Dengan
c1 , c2 , ..., cn adalah konstanta. (Winston, 1995)
Fungsi yang Terdefinisi SepotongSepotong Fungsi yang didefinisikan oleh rumus yang berlainan di bagian yang berbeda dari daerah asalnya dinamakan fungsi yang terdefinisi sepotong-sepotong.
z = cT x
Ax = b x≥0 dengan x dan c berupa vektor berukuran n, b berupa vektor berukuran m, sedangkan A berupa matriks berukuran m × n yang disebut juga matriks kendala.
Definisi 1 (Fungsi Linear) Misalkan f ( x1, x2 , ..., xn ) menyatakan suatu fungsi dalam variabel - variabel f ( x1 , x2 , ..., xn ) dikatakan x1 , x2 ,..., xn , fungsi linear jika dan hanya jika f dapat disajikan sebagai
Contoh 1: Fungsi f didefinisikan oleh :
f ( x) =
{
x
jika x ≥ 0
− x jika x < 0
Definisi 2 (Pertidaksamaan Linear) Untuk sembarang fungsi linear f ( x1 , x2 ,..., xn ) dan sembarang bilangan b, pertidaksamaan
f ( x1 , x2 ,..., xn ) ≤ b
f ( x1 , x2 ,..., xn ) ≥ b
dan
dinamakan
pertidaksamaan linear. (Winston, 1995)
2
Definisi 3 (Daerah Fisibel) Daerah fisibel pemrograman linear adalah daerah yang memenuhi semua kendala pada pemrograman linear. (Nash & Sofer, 1996) Definisi 4 (Solusi Fisibel) Suatu solusi disebut fisibel jika memenuhi semua kendala pada pemrograman linear. (Nash & Sofer, 1996) Definisi 5 (Solusi Optimum) Solusi optimum (terbaik) adalah suatu solusi dalam daerah fisibel yang menyebabkan nilai fungsi objektif terkecil (dalam masalah minimisasi), untuk masalah maksimisasi solusi optimum suatu pemrograman linear adalah suatu solusi dalam daerah fisibel yang menyebabkan nilai fungsi objektif terbesar. (Winston, 1995) 2.2 Integer Linear Programming Model pemrograman linear bilangan bulat (integer linear programming/ILP) atau disebut juga integer programming (IP), adalah suatu model pemrograman linear dengan variabel yang digunakan berupa bilangan bulat (integer). Jika semua variabel harus berupa integer, maka masalah tersebut disebut pure integer programming. Jika hanya sebagian yang harus integer maka disebut mixed integer programming. IP dengan semua variabelnya harus bernilai 0 atau 1 disebut 0-1 ILP. Definisi 6 (Pemrograman Linear Relaksasi) Pemrograman linear relaksasi dari suatu IP merupakan pemrograman linear yang diperoleh dari IP tersebut dengan menghilangkan kendala integer atau kendala 0-1 pada variabelnya. (Winston, 1995) 2.3 Metode Branch and Bound untuk menyelesaikan masalah Integer Programming Dalam penulisan karya ilmiah ini, untuk memperoleh solusi optimal dari masalah IP digunakan software LINGO 8.0 yaitu sebuah program yang didesain untuk membangun dan menentukan solusi model linear, nonlinear, dan optimisasi integer menjadi lebih cepat, mudah, dan lebih efisien dari pada penyelesaian secara manual, dengan
prinsip pemecahannya berdasarkan metode branch and bound. Prinsip dasar metode branch and bound adalah memecah daerah fisibel dari masalah LP-relaksasi dengan membuat subproblemsubproblem. ¾ Branch Membuat partisi daerah solusi ke dalam subproblem. Tujuannya untuk menghapus daerah solusi yang tidak fisibel. Hal ini dicapai dengan menentukan kendala yang penting untuk menghasilkan solusi IP, secara tidak langsung titik integer yang tidak fisibel terhapus. Dengan kata lain, hasil pengumpulan dari subproblem – subproblem yang lengkap menunjukkan setiap titik integer yang fisibel dari masalah asli. Karena sifat alami partisi itu, maka proses tersebut dinamakan Branching. ¾ Bound Misalkan masalahnya diasumsikan merupakan tipe maksimisasi, nilai objektif yang optimal untuk setiap subproblem dibuat dengan membatasi pencabangan dengan batas bawah dari nilai objektif yang dihubungkan dengan sembarang nilai integer yang fisibel. Hal ini sangat penting untuk mengatur dan menempatkan solusi optimum. Operasi ini yang menjadi alasan dinamakan Bounding. (Taha, 1975) Langkah-langkah dari metode branch and bound adalah sebagai berikut : Langkah 1 : Periksa apakah IP memenuhi kondisi berikut: (1) Subproblem tidak fisibel. (2) Subproblem menghasilkan solusi optimal dengan semua variabel bernilai integer. (3) Nilai optimal untuk subproblem lebih kecil dari (dalam masalah memaksimumkan) batas bawah (lower bound/LB). Jika kondisi tersebut terpenuhi, maka cabang subproblem tidak diperlukan. Langkah 2 : Sebuah subproblem mungkin dapat dihapuskan dari pertimbangan dengan kondisi sebagai berikut : (1) Subproblem tidak fisibel. (2) Batas bawah (yang menunjukkan nilai optimal dari kandidat terbaik) setidaknya lebih besar dari nilai optimal subproblem.
3
Contoh 2: Misalkan diberikan masalah integer programming berikut: Maksimumkan z = 5 x1 + 4 x2 terhadap x1 + x2 ≤ 5
• Subproblem 3 : Subproblem 1 + kendala ( x1 ≥ 4) , yaitu : Maksimumkan z = 5 x1 + 4 x2 Terhadap kendala : x1 + x2 ≤ 5
10 x1 + 6 x2 ≤ 45 x1 , x2 ≥ 0 dan integer
10 x1 + 6 x2 ≤ 45 x1 , x2 ≥ 0 dan integer
Daerah fisibel untuk masalah IP di atas diberikan pada gambar berikut:
( x1 ≥ 4)
x2
5
Daerah fisibel untuk subproblem 2 dan subproblem 3 diberikan pada gambar berikut:
4
x2
7 6
7
3
6
2
5
1
x1 1
2
3
4
Gambar 1 Daerah fisibel IP.
5
Metode Branch and Bound dimulai dengan menentukan solusi LP-relaksasi (subproblem 1 : maksimumkan dengan kendala z = 5 x1 + 4 x2 x1 + x2 ≤ 5 , 10 x1 + 6 x2 ≤ 45 , x1 , x2 ≥ 0 ). Solusi LP-relaksasi untuk masalah di atas adalah x1 = 3, 75 , x2 = 1, 75 , dan
z = 23, 75 . Solusi tersebut tidak memenuhi kendala bilangan bulat. Oleh karena itu harus dibuat subproblem yang baru dengan memilih variabel yang tidak memenuhi kendala bilangan bulat. Dengan memilih diketahui bahwa daerah x1 = 3, 75 , ( 3 < x1 < 4) dari daerah fisibel subproblem 1 tidak akan memuat solusi IP yang fisibel karena tidak memenuhi kendala integer. Subproblem yang baru adalah sebagai berikut: • Subproblem 2 : Subproblem 1 + kendala ( x1 ≤ 3) , yaitu : Maksimumkan z = 5 x1 + 4 x2 Terhadap kendala : x1 + x2 ≤ 5
10 x1 + 6 x2 ≤ 45 x1 , x2 ≥ 0 dan integer
( x1 ≤ 3)
4 3 2 1 1
2
3
4
5
x1
Gambar 2 Daerah fisibel untuk subproblem 2 dan subproblem 3.
Pada subproblem 2 diperoleh solusi LPrelaksasi x1 = 3 , x2 = 2 , dan z = 23 . Karena semua variabel bernilai bilangan bulat (solusinya memenuhi kendala bilangan bulat), maka tidak perlu dibuat subproblem baru. Pada subproblem 3 diperoleh solusi LP-relaksasi x1 = 4 , x2 = 0.8333 , dan z = 23, 3333 .
Karena variabelnya tidak memenuhi kendala bilangan bulat, maka harus dibuat subproblem baru. Subproblem yang baru adalah sebagai berikut: • Subproblem 4 : Subproblem 3 + kendala ( x2 ≥ 1) , yaitu : Maksimumkan z = 5 x1 + 4 x2 Terhadap kendala : x1 + x2 ≤ 5
10 x1 + 6 x2 ≤ 45 x1 , x2 ≥ 0 dan integer
( x1 ≥ 4) ( x2 ≥ 1)
4
• Subproblem 5 : Subproblem 3 + kendala ( x2 ≤ 0) , yaitu :
baru. Pada subproblem 5 diperoleh solusi LP-relaksasi x1 = 4,5 , x2 = 0 , dan z = 22,5 . Karena variabelnya tidak memenuhi kendala bilangan bulat, maka seharusnya dibuat subproblem baru., akan tetapi karena nilai z maksimum yang akan dihasilkan lebih kecil dari batas bawah, maka tidak perlu dibuat subproblem baru. Branching Subproblem untuk masalah IP di atas diberikan pada Gambar 3, sedangkan solusi lengkapnya dapat dilihat pada lampiran 1.
Maksimumkan z = 5 x1 + 4 x2 Terhadap kendala : x1 + x2 ≤ 5
10 x1 + 6 x2 ≤ 45 x1 , x2 ≥ 0 dan integer
( x1 ≥ 4) ( x2 ≤ 0)
Pada subproblem 4 diperoleh solusi tak fisibel, maka tidak perlu dibuat subproblem
Subproblem 1 x1 = 3, 75 , x2 = 1, 25 dan z = 23, 75
x1 > 4
x1 < 3
Subproblem 3
Subproblem 2*
x1 = 4, x2 = 0, 8333 dan z = 23, 3333
x1 = 3, x2 = 2 dan z = 23 Batas bawah (optimum)
Subproblem 4 Solusi takfisibel
Subproblem 5 x1 = 4, 5 , x2 = 0 dan z = 22, 5
Gambar 3 Branching dan Subproblem masalah IP pada contoh 2.
5
III PEMBAHASAN Grafik fungsi linear sepotong-sepotong (piecewise linear function) terdiri dari beberapa segmen garis yang kontinu. Fungsi linear sepotong–sepotong pada Gambar 4 terdiri dari tiga segmen garis. Nilai x yang membuat kemiringan dari fungsi linear sepotong – sepotong berubah (atau titik yang membuat fungsi tersebut tidak linear) disebut break point. Jadi x = 0, x = 20, x = 40, x = 50 adalah break point dari fungsi pada Gambar 4.
C(x)
x 10
20
30
40
50
Gambar 4
akan memberikan diskon harga kepada pabrik tahu tersebut, yang besarannya disesuaikan dengan banyaknya pembelian kedelai, dengan rincian sebagai berikut : • biaya pembelian 500 karung kedelai pertama seharga $25 per karung. • biaya pembelian 500 karung kedelai berikutnya seharga $20 per karung. • biaya pembelian 500 karung kedelai berikutnya seharga $15 per karung. Semakin banyak pabrik tahu tersebut membeli, maka harga kedelainya menjadi semakin murah. Andaikan pemasok hanya memiliki persediaan kedelai sebanyak 1500 karung. Misalkan x adalah banyaknya karung kedelai yang dibeli dan c ( x ) adalah biaya pembelian tiap x karung kedelai untuk : Untuk 0 ≤ x ≤ 500, c ( x ) = 25 x Untuk 500 < x ≤ 1000, c ( x ) = biaya pembelian 500 karung kedelai pertama yaitu $25 per karung ditambah biaya pembelian berikutnya yaitu x − 500 karung kedelai dengan harga $20 perkarung = 25(500) + 20( x − 500) = 12500 + 20( x ) − 1000 = 20 x + 2500 Untuk 1000 < x ≤ 1500, c ( x ) = biaya pembelian 1000 karung kedelai pertama ditambah biaya pembelian berikutnya yaitu x-1000 karung kedelai dengan harga $15 per karung = 20(1000) + 2500 + 15( x − 1000)
30000 24000 18000 12000
= 20(1000) + 2500 + 15( x ) − 15(1000)
6000
= 15 x + 2500 + 5(1000)
500
1000
1500
Gambar 5 Biaya pembelian bahan baku tahu Sebagai ilustrasi mengenai bagaimana fungsi linear sepotong-sepotong dapat terjadi dan sangat berguna dalam aplikasi nyata dapat dilihat pada Gambar 5. Misalkan dalam pembelian bahan baku pada sebuah pabrik tahu. Pemasok bahan baku (kedelai)
= 15 x + 7500 Sehingga fungsi biaya pembelian tiap x karung kedelai dapat dituliskan dalam bentuk: (0 ≤ x ≤ 500) ⎧ 25 x ⎪ c ( x ) = ⎨ 20 x + 2500 (500 < x ≤ 1000) ⎪15 x + 7500 (1000 < x ≤ 1500) ⎩
6
Pada pembelian sejumlah tertentu pabrik tahu akan mendapatkan diskon harga dari si pemasok, hal ini menyebabkan fungsi pembelian bahan baku tahu menjadi tidak linear, akan tetapi termasuk dalam fungsi linear sepotong-sepotong. Sehingga dapat disimpulkan bahwa c ( x ) memiliki break point b1 = 0, b2 = 500, b3 = 1000, b4 = 1500. Fungsi linear sepotong-sepotong sebenarnya bukan merupakan fungsi linear, maka pemrograman linear tidak dapat digunakan untuk memecahkan masalahmasalah optimisasi dengan melibatkan fungsi ini. Namun demikian ternyata fungsi linear sepotong-sepotong dapat direpresentasikan ke dalam bentuk linear dengan menambah kendala-kendala linear tertentu. Misalkan f ( x ) adalah fungsi linear sepotong-sepotong, yang memiliki break point b1, b2, b3, …, bn. Untuk suatu k ( k = 1, 2, ..., n -1), bk ≤ x ≤ bk +1 . Selanjutnya untuk z k (0 ≤ z k ≤ 1), x
suatu dapat
bilangan dituliskan
sebagai :
f ( x) = f (1100) =
4
f (1000) +
1
f (1500) 5 5 4 1 = (22500) + (30000) 5 5
= 24000
Ada dua langkah utama yang harus kita lakukan ketika menemukan suatu masalah yang mengandung fungsi linear sepotongsepotong, yaitu : •
Langkah Pertama Nyatakan f ( x ) dalam bentuk f ( x ) = z1 f (b1 ) + z 2 f (b2 ) + ... + z n f (bn )
•
Langkah Kedua Untuk menjamin formula di atas dapat berfungsi, selain kendala-kendala yang telah ada pada permasalahan tersebut, tambahkan kendala-kendala baru : z1 ≤ y1 z 2 ≤ y1 + y2
x = zk bk + (1 − zk )bk +1
z 3 ≤ y 2 + y3
M
karena f ( x ) merupakan fungsi linear untuk
z n −1 ≤ yn − 2 + yn −1
bk ≤ x ≤ bk +1 , sehingga dapat dituliskan :
z n ≤ yn −1
f ( x ) = f (z k bk + (1 − z k )bk +1 ) = z k f (bk ) + (1 − z k ) f (bk +1 )
Untuk mengilustrasikannya, lihat lagi contoh pembelian kedelai pada Gambar 5, ambil x = 1100, sehingga kita memiliki b3 = 1000 ≤ 1100 ≤ 1500 = b4, dan dapat dituliskan: x=
4 5
(1000) +
1 5
(1500)
y1 + y2 + ... + yn −1 = 1 z1 + z 2 + ... + z n = 1 x = z1b1 + z 2 b2 + ... + z n bn yi = 0 atau 1, (i = 1, 2, ..., n − 1) zi ≥ 0, (i = 1, 2, ..., n )
(y merupakan variabel tambahan). Dari langkah satu dan dua akan didapatkan sebuah fungsi objektif yang linear dengan kendala-kendalanya yang dapat diselesaikan dengan menggunakan pemrograman linear.
7
IV CONTOH KASUS Euing Gas memproduksi 2 jenis gas (gas 1 dan gas 2) dari 2 jenis minyak (minyak 1 dan minyak 2). Setiap galon gas 1 harus berisi minimal 50% minyak 1, dan setiap galon gas 2 harus terisi sedikitnya 60% minyak 1. Setiap galon gas 1 dapat terjual $12 dan gas 2 terjual seharga $14 per galon. Saat ini telah tersedia 500 galon minyak 1 dan 1000 galon minyak 2. Sebanyak 1500 galon lebih minyak 1 dapat dibeli dengan harga berikut : 500 galon pertama seharga $25 per galon, 500 galon berikutnya $20 per galon, dan 500 galon berikutya $15 per galon. Formulasikan Integer Programming yang dapat memaksimalkan keuntungan Euing Gas. Penyelesaian : Terlihat bahwa biaya pembelian minyak 1merupakan fungsi linear sepotongsepotong, kita misalkan : c ( x ) = fungsi pembelian minyak 1 x = banyaknya minyak 1 yang dibeli xij
= banyaknya
minyak
i
yang
digunakan untuk memproduksi gas j (i,j = 1,2) Keuntungan Euink Gas (Z) = total pendapatan – biaya pembelian minyak 1 Z = 12( x11 + x21 ) + 14( x12 + x22 ) − c ( x )
Dengan :
(0 ≤ x ≤ 500) ⎧ 25 x ⎪ c( x) = ⎨ 20 x + 2500 (500 < x ≤ 1000) ⎪15 x + 7500 (1000 < x ≤ 1500) ⎩ Fungsi objektifnya adalah memaksimumkan Z = 12( x11 + x21 ) + 14( x12 + x22 ) − c ( x ) dengan kendala : 1. Euink Gas dapat menggunakan paling banyak x + 500 galon minyak 1. x11 + x12 ≤ x + 500 2.
Euing Gas dapat menggunakan paling banyak 1000 galon minyak 2. x21 + x22 ≤ 1000
3.
Campuran minyak untuk membuat gas 1 minimal mengandung 50% minyak 1.
4.
campuran minyak untuk membuat gas 2 minimal mengandung 60% minyak 1.
5. 6.
x11 ≥ 0.5 atau x11 + x21 0.5 x11 − 0.5 x21 ≥ 0
x12 ≥ 0.6 atau x12 + x22 0.4 x12 − 0.6 x22 ≥ 0
xij ≥ 0 0 ≤ x ≤ 1500
Karena c ( x ) merupakan fungsi linear sepotong-sepotong, fungsi objektifnya bukanlah fungsi linear dari x, dan optimisasi ini bukanlah suatu pemograman linear. Akan tetapi sesuai dengan penjelasan pada materi ini, kita dapat mengubah bentuk masalah ini menjadi masalah pemograman bilangan bulat. Setelah mengetahui break points untuk c ( x ) adalah b1 = 0, b2 = 500, b3 = 1000, b4 = 1500, langkah selanjutnya adalah: Langkah 1 . Nyatakan c ( x ) dalam bentuk c ( x ) = z1c (0) + z 2 c (500) + z3 c (1000) + z 4 c (1500) Langkah 2. Tambahkan kendala baru
x = 0 z1 + 500 z2 + 1000 z3 + 1500 z4 z1 ≤ y1 , z2 ≤ y1 + y2 z3 ≤ y2 + y3 , z4 ≤ y3 z1 + z2 + z3 + z4 = 1 , y1 + y2 + y3 = 1 , zi ≥ 0, (i = 1, 2,3, 4) yi = 0 atau 1, (i = 1, 2,3) Persamaan baru yang merupakan masalah pemograman linear yaitu : max z = 12( x11 + x21 ) + 14( x12 + x22 ) − z1c (0) − z 2 c (500) − z3 c (1000) − z 4 c (1500) dengan kendala :
8
x11 + x12 ≤ x + 500
(1)
z = z = 0. Kemudian masukan ke kendala
x21 + x22 ≤ 1000
(2)
(5) 800 = x = 500 z
0.5 x11 − 0.5 x21 ≥ 0
(3)
0.4 x12 − 0.6 x22 ≥ 0
(4)
dipenuhi dengan z2 ≤ 1. Serupa juga jika diambil y3=1 pada x = 800 tidak akan terpenuhi. Jika kita coba y2=1 dari (6)&(9) memaksa z = z = 0. Kemudian (7)&(8)
3
x = 0 z1 + 500 z 2 + 1000 z3 + 1500 z 4 (5) z1 ≤ y1
(6)
z 2 ≤ y1 + y2
(7)
z 3 ≤ y 2 + y3
(8)
z 4 ≤ y3
(9)
z1 + z 2 + z3 + z 4 = 1
(10)
y1 + y2 + y3 = 1
(11)
yi = 0 atau 1, (i = 1, 2, 3)
(12)
zi ≥ 0, (i = 1, 2, 3, 4)
(13)
xij ≥ 0
(14)
1
perhatikan
(6)-(11)
z2 =
3
jika
1
4
memaksa z = z = 0 dan membiarkan z2 1
4
dan z3 menjadi bilangan tak negatif kurang dari atau sama dengan 1. Selanjutnya pilih suatu nilai x sembarang, misalkan x = 800. Catatan bahwa b = 500 ≤ x ≤ 1000 = b . 2
Untuk
x = 800
3
nilai
dimungkinkan, karena jika
y1 = 1
z3 =
dan
3
.
Sekarang
fungsi
2c (500) 5
3c (1000) 5
dengan kendala(1)-(14)
perhatikan
2
2
−
(6)-(9) menjadi z ≤ 0, z ≤ 1, z ≤ 1, z ≤ 0. Kendala ini 1
yang tidak dapat
z = 12 x11 + 12 x21 + 14 x12 + 14 x22 −
semua zi yang lain harus sama dengan 0, misalkan jika y2 = 1, maka y = y = 0, 3
,
4
5 5 objektifnya menjadi :
yi = 1, kemudian zi dan zi+1 positif, tapi
kemudian
2
menjadi z2 ≤ 1 dan z3 ≤ 1 sekarang masukan ke kendala (5) 800 = x = 500z2 + 1000z3. karena z 2 + z3 = 1 , kita peroleh
Untuk melihat kenapa formula ini bekerja, karena y1 + y2 + y3 = 1 dan
yi = 0 atau 1,
4
tidak
y1 = 1 maka
y2 = y3 = 0, kemudian (8)&(9) memaksa
Karena c (800) =
2c (500)
+
3c (1000)
5 5 Fungsi objektif kita menghasilkan nilai yang tepat untuk Euing Gas, jika dilakukan perhitungan maka solusi optimal untuk masalah maksimisasi pada perusahaan Euing Gas adalah sebagai berikut : Z = $12500 x = 1000 galon x12 = 1500 galon x22 = 1000 galon x11 = 0 galon x21 = 0 galon terlihat bahwa untuk mendapat keuntungan yang optimal Euing Gas harus membeli 1000 galon minyak 1 dan memproduksi 2500 galon gas 2. Solusi lengkapnya dapat dilihat pada lampiran 2.
9
V SIMPULAN DAN SARAN
5.1 Simpulan Langkah pertama yang harus dilakukan untuk menyelesaikan masalah integer programming dengan fungsi objektif linear sepotong-sepotong yaitu dengan cara menyatakan fungsi linear sepotong-sepotong tersebut menjadi sebuah fungsi linear secara utuh. Sehingga dengan demikian masalah pemrograman integer dengan fungsi objektif linear sepotong-sepotong dapat ditransformasikan menjadi pemrograman linear integer, dengan cara menyatakan f ( x ) dalam bentuk
z1 f (b1 ) + z 2 f (b2 ) + ... + z n f (bn ).
Kemudian tambahkan beberapa kendala baru yang menjamin fungsi objektif menjadi linear. 5.2 Saran Pada pembahasan skripsi ini hanya dipelajari mengenai transformasi fungsi linear sepotong-sepotong yang kontinu, bagi yang berminat meneruskan, disarankan untuk menggali lagi apakah metode ini dapat digunakan untuk fungsi linear sepotongsepotong yang tidak kontinu.
DAFTAR PUSTAKA Nash, S.G. & A. Sofer. 1996. Linear and Nonlinear Programming. McGrawHill, New York. Taha, H. A. 1975. Integer Programming : Theory, Aplications, and Computations Academic Press, New York.
Winston, W.L. 1995. Introduction to Mathematical Programming 2nd ed. Duxbury, New York. Winston, W.L. 2004. Operation Research Applications and Algorithms. Brooks /Cole-Thomson Learning. New York.
10
LAMPIRAN
11
Lampiran 1 Syntax Program LINGO 8.0 untuk Menyelesaikan LP dengan Metode Branch and Bound Dari LP pada Contoh 2 Misalkan diberikan masalah integer programming berikut: Maksimumkan z = 5 x1 + 4 x2 terhadap x1 + x2 ≤ 5
10 x1 + 6 x2 ≤ 45 x1 , x2 ≥ 0 dan integer Penyelesaian: Daerah fisibel untuk masalah IP di atas diberikan pada gambar berikut:
x2 7 6 5 4 3 2 1
x1 1
2
3
4
Gambar 1 Daerah fisibel IP
5
Anggap LP tersebut sebagai subproblem 1. 1. Cari solusi LP-Relaksasi dari subproblem 1 Syntax program LINGO 8.0: max=5*x1+4*x2; x1+x2<=5; 10*x1+6*x2<=45; x1>=0; x2>=0; Hasil yang diperoleh: Global optimal solution found at iteration: 2 Objective value: 23.75000 Variable Value Reduced Cost X1 3.750000 0.000000 X2 1.250000 0.000000 Row Slack or Surplus Dual Price 1 23.75000 1.000000 2 0.000000 2.500000 3 0.000000 0.2500000 4 3.750000 0.000000 5 1.250000 0.000000 Karena solusi yang didapat belum memenuhi kendala integer maka harus dibuat subproblem baru, yaitu: • Subproblem 2 : Subproblem 1 + kendala ( x1 ≤ 3) • 2.
Subproblem 3 : Subproblem 1 + kendala ( x1 ≥ 4 )
Cari solusi LP dari subproblem 2 Syntax program LINGO 8.0: max=5*x1+4*x2; x1+x2<=5; 10*x1+6*x2<=45; x1>=0; x2>=0; x<=3;
12
Hasil yang diperoleh: Global optimal solution found at iteration: 2 Objective value: 23.00000 Variable Value Reduced Cost X1 3.000000 0.000000 X2 2.000000 0.000000 Row Slack or Surplus Dual Price 1 23.00000 1.000000 2 0.000000 4.000000 3 3.000000 0.000000 4 3.000000 0.000000 5 2.000000 0.000000 6 0.000000 1.000000 Karena hasilnya sudah memenuhi kendala integer maka subproblem 2 kita jadikan batas bawah.
3.
Cari solusi LP dari subproblem 3 Syntax program LINGO 8.0: max=5*x1+4*x2; x1+x2<=5; 10*x1+6*x2<=45; x1>=0; x2>=0; x1>=4; Hasil yang diperoleh: Global optimal solution found at iteration: 3 Objective value: 23.33333 Variable Value Reduced Cost X1 4.000000 0.000000 X2 0.8333333 0.000000 Row Slack or Surplus Dual Price 1 23.33333 1.000000 2 0.1666667 0.000000 3 0.000000 0.6666667 4 4.000000 0.000000 5 0.8333333 0.000000 6 0.000000 -1.666667 Karena solusi yang didapat belum memenuhi kendala integer maka harus dibuat subproblem baru, yaitu: • Subproblem 4 : Subproblem 3 + kendala ( x2 ≥ 1) •
4.
Subproblem 5 : Subproblem 3 + kendala ( x2 ≤ 0 )
Cari solusi LP dari subproblem 4 Syntax program LINGO 8.0: max=5*x1+4*x2; x1+x2<=5; 10*x1+6*x2<=45; x1>=0; x2>=0; x1>=4; x2>=1; Hasil yang diperoleh
13
Daerah subproblem 4 merupakan daerah tidak fisibel maka subproblem 4 tidak memiliki solusi fisibel. 5.
Cari solusi LP dari subproblem 5 Syntax program LINGO 8.0: max=5*x1+4*x2; x1+x2<=5; 10*x1+6*x2<=45; x1>=0; x2>=0; x1>=4; x2<=0; Hasil yang diperoleh Global optimal solution found at iteration: 3 Objective value: 22.50000 Variable Value Reduced Cost X1 4.500000 0.000000 X2 0.000000 0.000000 Row Slack or Surplus Dual Price 1 22.50000 1.000000 2 0.5000000 0.000000 3 0.000000 0.5000000 4 4.500000 0.000000 5 0.000000 0.000000 6 0.5000000 0.000000 7 0.000000 1.000000 Karena solusi yang didapat belum memenuhi kendala integer maka harus dibuat subproblem baru, yaitu: • Subproblem 6: Subproblem 5 + kendala ( x1 ≥ 5) Subproblem 7 : Subproblem 5 + kendala ( x1 ≤ 4 ) Akan tetapi karena hasilnya (22.5) kurang dari batas bawah (23)maka tidak perlu lagi melakukan perhitungan, karena sudah pasti nilai dari pencabangan berikutnya akan kurang dari batas bawah, sehingga dapat kita simpulkan bahwa subproblem 2 sebagai solusi optimum. •
Lampiran 2 Penyelesaian solusi pada contoh kasus permasalahan perusahaan Euing Gas menggunakan software LINGO 8.0
Syntax program LINGO 8.0: MODEL: ! solusi pada permasalahan Euink Gas; SETS: PRODUK / GAS1, GAS2/: HARGA_JUAL; BAHAN_BAKU / MINYAK1, MINYAK2/: KAPASITAS, BELI; DECISION_VARIABLES(BAHAN_BAKU, PRODUK): PRODUKSI; DUMMY1 / Z1..Z4/: BETA, COST, BREAK_POINT; DUMMY2 / Y1..Y3/: GAMMA; ENDSETS DATA: KAPASITAS = 500 1000;
14
HARGA_JUAL = 12 14; COST = 0 12500 22500 30000;!lengkapnya hitung dari c(0) sampai c(1500); BREAK_POINT = 0 500 1000 1500; ENDDATA !Fungsi objektif; Max = @sum(DECISION_VARIABLES(I, J): HARGA_JUAL(J)*PRODUKSI(I,J)) @SUM(DUMMY1(I): BETA(I)*COST(I)); !Kendala 1; @FOR(BAHAN_BAKU(I)|I#EQ#1: @SUM(PRODUK(J): PRODUKSI(I,J)) <= BELI(I) + KAPASITAS(I)); !Kendala 2; @FOR(BAHAN_BAKU(I)|I#EQ#2: @SUM(PRODUK(J): PRODUKSI(I,J)) <= KAPASITAS(I)); !kendala 3; @FOR(PRODUK(J)|J#EQ#1: @SUM(BAHAN_BAKU(I)|I#EQ#1: 0.5*PRODUKSI(I,J) 0.5*PRODUKSI(I+1,J))>= 0); !kendala 4; @FOR(PRODUK(J)|J#EQ#2: @SUM(BAHAN_BAKU(I)|I#EQ#1: 0.4*PRODUKSI(I,J) 0.6*PRODUKSI(I+1,J))>= 0); !kendala 5; @FOR(BAHAN_BAKU(I)|I#EQ#1: @SUM(DUMMY1(J): BREAK_POINT(J)*BETA(J)) = BELI(I)); !kendala tambahan, memaksa pembelian untuk minyak 2 tidak ada; @FOR(BAHAN_BAKU(I)|I#EQ#2: BELI(I)=0); !kendala 6; @FOR(DUMMY1(I)|I#EQ#1: @SUM(DUMMY2(J)|J#EQ#1:GAMMA(J))>= BETA(I)); !kendala 7; @FOR(DUMMY1(I)|I#EQ#2: @SUM(DUMMY2(J)|J#LT#3:GAMMA(J))>= BETA(I)); !kendala 8; @FOR(DUMMY1(I)|I#EQ#3: @SUM(DUMMY2(J)|J#GT#1:GAMMA(J))>= BETA(I)); !kendala 9; @FOR(DUMMY1(I)|I#EQ#4: @SUM(DUMMY2(J)|J#EQ#3:GAMMA(J))>= BETA(I)); !kendala 10; @SUM(DUMMY1(I):BETA(I))=1; !kendala 11; @SUM(DUMMY2(I):GAMMA(I))=1;
15
!kendala biner atau kendala 12; @FOR( DUMMY2: @BIN( GAMMA)); ! kendala 13 dan 14 tidak perlu ditulis, sudah default Lingo untuk set up variabel yang dicari nilainya >=0;
END
Hasil yang didapat: Global optimal solution found at iteration: Objective value:
32 12500.00
Variable
Value
Reduced Cost
HARGA_JUAL( GAS1) HARGA_JUAL( GAS2) KAPASITAS( MINYAK1) KAPASITAS( MINYAK2) BELI( MINYAK1) BELI( MINYAK2) PRODUKSI( MINYAK1, GAS1) PRODUKSI( MINYAK1, GAS2) PRODUKSI( MINYAK2, GAS1) PRODUKSI( MINYAK2, GAS2) BETA( Z1) BETA( Z2) BETA( Z3) BETA( Z4) COST( Z1) COST( Z2) COST( Z3) COST( Z4) BREAK_POINT( Z1) BREAK_POINT( Z2) BREAK_POINT( Z3) BREAK_POINT( Z4) GAMMA( Y1) GAMMA( Y2) GAMMA( Y3)
12.00000 14.00000 500.0000 1000.000 1000.000 0.000000 0.000000 1500.000 0.000000 1000.000 0.000000 0.000000 1.000000 0.000000 0.000000 12500.00 22500.00 30000.00 0.000000 500.0000 1000.000 1500.000 0.000000 0.000000 1.000000
0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 3.500000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 -10000.00 -2500.000 0.000000
Row 1 2 3 4 5 6 7 8 9 10 11 12 13
Slack or Surplus 12500.00 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 1.000000 0.000000 0.000000
Dual Price 1.000000 15.00000 12.50000 -6.000000 -2.500000 -15.00000 0.000000 -7500.000 -2500.000 0.000000 0.000000 -7500.000 0.000000
