BAB 2 LANDASAN TEORI

BAB 2

LANDASAN TEORI

2.1 Linear Programming 2.1.1 Model Linier Programming Pemrograman linier adalah sebuah model matematik untuk menjelaskan suatu persoalan optimasi. Istilah linier menunjukkan bahwa seluruh fungsi matematik di dalam model harus berupa fungsi linier; sedang kata pemrograman dalam istilah ini pada hakekatnya sinonim dengan perencanaan. Oleh karena itu, Pemrograman linier mencakup perencanaan kegiatan-kegiatan untuk memperoleh hasil optimal, yaitu hasil yang memberikan nilai tujuan terbaik ( Siswanto, 1990). Pemrograman linier adalah suatu cara untuk menyelesaikan persoalan pengalokasian sumber-sumber yang terbatas di antara beberapa aktivitas yang bersaing, dengan cara yang terbaik yang mungkin dapat dilakukan (Dimyati dan A. Dimyati, 1987). Pokok pikiran yang utama dalam menggunakan program linier adalah merumuskan masalah dengan jelas dengan menggunakan sejumlah informasi yang tersedia. Sesudah masalah dirumuskan dengan baik, maka langkah berikutnya adalah menerjemahkan masalah ini ke dalam bentuk model matematika, yang terang mempunyai cara pemecahan yang lebih mudah dan rapi guna menemukan jawaban terhadap masalah yang dihadapi ( Siagian, 1987). Sebagai contoh dari pemecahan masalah dengan menggunakan program linier adalah keadaan bagian produksi suatu perusahaan yang dihadapkan pada masalah penentuan tingkat produksi masing-masing jenis produk dengan memperhatikan batasan-batasan faktor produksi: mesin, tenaga kerja, bahan mentah dan sebagainya

Universitas Sumatera Utara

untuk memperoleh tingkat keuntungan maksimal atau biaya yang minimal (Subagyo et al., 1990). Linier programming merupakan suatu model umum yang dapat digunakan dalam pemecahan masalah pengalokasian sumber-sumber yang terbatas secara optimal. Linier programming memakai suatu model matematis yang menggambarkan masalah yang dihadapi. Linier memiliki arti bahwa semua fungsi matematis dalam model harus merupakan fungsi-fungsi linier, sedangkan programming/pemrograman dapat diartikan sebagai perencanaan. Dengan demikian linier programming dapat didefinisikan sebagai membuat rencana kegiatan-kegiatan dengan menggunakan suatu model umum dalam pemecahan masalah pengalokasian sumber daya-sumber daya yang terbatas secara optimal. Model pemrograman linier memiliki tiga unsur dasar, yaitu (1) variabel keputusan merupakan variabel yang akan dicari dan memberi nilai yang paling baik bagi tujuan yang hendak dicapai (2) fungsi tujuan menunjukkan fungsi matematik yang harus dimaksimumkan atau diminimumkan dan mencerminkan tujuan yang hendak dicapai, dan (3) fungsi kendala menunjukkan fungsi matematik yang menjadi kendala bagi usaha untuk memaksimumkan atau meminimumkan fungsi tujuan dan mewakili kendala-kendala yang harus dihadapi oleh organisasi (Siswanto, 1990). Model dasar atau Persamaan linier dapat dirumuskan sebagai berikut : Cari nilai-nilai

yang dapat menghasilkan berbagai kombinasi

optimum (maksimum atau minimum) dari :

Dengan syarat bahwa fungsi tujuan tersebut memenuhi kendala sebagai berikut:


.

.

.

.

.

.

.

.

.

.

.

.

atau dalam bentuk umumnya : optimumkan (maksimumkan atau minimumkan) :

dengan syarat ikatan :

Untuk: = Parameter yang dijadikan kriteria optimasi, atau koefisien peubah pengambilan keputusan dalam fungsi tujuan. = Peubah pengambilan keputusan atau kegiatan (yang ingin dicari; yang tidak diketahui). = Koefisien peubah pengambilan keputusan dalam kendala ke-i. = Sumber daya yang terbatas, yang membatasi kegiatan atau usaha yang bersangkutan; disebut pula konstanta atau “nilai sebelah kanan” dari kendala ke-i. = Nilai skalar kriteria pengambilan keputusan; suatu fungsi tujuan. (B.D. Nasendi dan A. Anwar, 1984)


Konsep linier programming ditemukan dan diperkenalkan pertama kali oleh George Dantzig yang berupa metode mencari solusi masalah linier programming dengan banyak variabel keputusan. Kemudian banyak ahli yang bergabung dengan Dantzig dalam konsep pengembangan linier programming. Paper pertamanya adalah metode solusi yang bernama metode simplex. Dalam pengembangan linier programming, Dantzig bekerjasama dengan Marshal Wood dan Alex O, dan masih banyak para ahli yang lainnya ikut. Kemudian, setelah berhasil diterapkan pada sektor pemerintah dan swasta, akhirnya disadari bahwa linier programming merupakan masalah yang sangat membantu dalam analisis bidang bisnis. Model Linier Programming ini merupakan bentuk dan susunan dalam menyajikan

masalah-masalah

yang

akan

dipecahkan

dengan

teknik

linier

programming. Dalam model linier programming dikenal 2 (dua) macam fungsi, yaitu : 1. Fungsi Tujuan (objective function) adalah fungsi yang menggambarkan tujuan/sasaran di dalam permasalahan linier programming yang berkaitan dengan pengaturan secara optimal, untuk memperoleh keuntungan maksimal atau biaya minimal. Pada umumnya nilai yang akan dioptimalkan dinyatakan sebagai Z. 2. Fungsi Batasan (constraint function) adalah bentuk penyajian secara matematis batasan-batasan kapasitas yang tersedia yang akan dialokasikan secara optimal ke berbagai kegiatan.


Tabel 2.1 Tabel Linier Programming 1

2

3

4

5 1

0

0

0

0

2 1

0

0

0

0

0

................................................ 0

1

3

0

................................................ 0

Kolom 1

: Faktor prioritas

dan bobot

0

1

untuk setiap variabel deviasi positif

(yakni variabel basis) dan memasukkan variabel deviasi artificial seperti ditampilkan dalam kolom 2 Kolom 2

: Nilai total deviasi absolut, yang mewakili jumlah total deviasi dari semua tujuan untuk tiap table sebagai iterasi proses pendapatan

Kolom 3

: Koefisien variabel keputusan

Kolom 4

: Matriks identitas menunjukkan pemasukan variabel deviasi negatif

Kolom 5

: Nilai sebelah kanan

Baris 1

: Variabel keputusan

Baris 2

: Vektor baris dari penunjuk nol pada proses perhitungan

Baris 3

: Bobot

dan variabel deviasi

untuk setiap variabel deviasi yang dimasukkan dalam

fungsi objektif Bentuk standard dari pemrograman linier menurut Taha (1982) mempunyai karakteristik :


1. Seluruh fungsi pembatas nilai ruas kanannya tidak bernilai negatif 2. Seluruh variabel keputusan tidak bernilai negatif 3. Fungsi tujuan dapat berupa maksimasi atau minimasi

2.1.2 Asumsi-Asumsi Dasar Linier Programming Dalam model linier programming terdapat asumsi-asumsi yang harus dipenuhi agar permasalahan linier programming menjadi absah, adapun asumsi linier programming adalah sebagai berikut : 1. Kesebandingan (Proportionality) Asumsi ini menyatakan bahwa naik turunnya nilai Z dan penggunaan sumber atau fasilitas yang tersedia akan berubah secara sebanding (propotional) dengan perubahan tingkat kegiatan. Contoh : a. Setiap pertamabahan 1 unit

akan menaikkan Z sebesar

b. Setiap pertama bahan 1 unit

akan menaikkan penggunaan sumber

sebesar

2. Penambahan (Additivity) Asumsi ini berarti bahwa nilai tujuan setiap kegiatan bersifat independent (bebas/tidak saling bergantung) dan dalam linier programming dianggap bahwa kenaikan nilai tujuan (Z) yang diakibatkan oleh suatu kegiatan dapat langsung ditambahkan tanpa mempengaruhi bagian nilai kegiatan lain. misalnya : Z=3

+5


dengan

= 10 ;

=2

sehingga Z = 30 + 10 = 40 Andaikan

bertambah 1 unit, maka sesuai dengan asumsi pertama,

nilai Z menjadi 40 + 3 = 43. Jadi nilai 3 karena kenaikan

dapat langsung

ditambahkan pada nilai Z mula-mula tanpa mengurangi bagian Z yang diperoleh dari kegiatan 2 ( dan

). Dengan kata lain, tidak ada korelasi antara

.

3. Pembagian (Divisibility) Dalam linier programming diperbolehkan menggunakan angka pecahan. Misalnya : Dari hasil perhitungan didapat nilai

= 4,5 ;

= 7,25 dan Z =

85.000,25. Dalam hal tertentu nilai pecahan ini harus dibulatkan dengan menggunakan integer, misalnya : jumlah mahasiswa diperguruan tinggi tidak mungkin dalam bentuk pecahan. 4. Kepastian (Deteministic) Asumsi ini menyatakan bahwa semua parameter yang terdapat dalam model linier programming yang berupa

,

dan

dapat diketahui secara

pasti.

2.1.3 Terminologi Linier Programming Agar memahami dengan baik bidang yang dipelajari , pembaca selalu harus mengerti istilah-istilah dan lambang-lambang khusus yang digunakan orang dalam bidang studi itu. Berikut ini adalah definisi dari beberapa istilah dan lambang yang biasa digunakan dalam Linier Programming.


1. Variabel Keputusan (decision variable) adalah seperangkat variabel yang tidak diketahui (dilambangkan

, dengan j = 1, 2, . . . , n) yang akan dicari nilainya

(varibel keputusan) 2. Nilai Sebelah Kanan (Right hand side value) adalah nilai-nilai yang biasanya menunjukkan ketersediaan sumber daya (dilambangkan dangan

) yang akan

ditentukan kekurangan atau kelebihan penggunaannya ( nilai sisi kanan ). 3. Variabel Dasar adalah variabel yang nilainya sama dengan sisi kanan dari persamaan. 4. Kolom Kunci adalah kolom yang merupakan dasar untuk mengubah tabel. Pilih kolom yang mempunyai nilai pada garis fungsi tujuan yang bernilai negatif dengan angka terbesar. 5. Baris Kunci adalah baris yang merupakan dasar untuk mengubah tabel tersebut. Untuk itu terlebih dahulu carilah indeks tiap-tiap baris dengan cara membagi nilai-nilai pada kolom RHS dengan nilai yang sebaris pada kolom kunci. 6. Angka kunci (pivot) merupakan perpotongan antara kolom kunci dengan baris kunci. 2.1.4 Unsur-Unsur Linier Programming Setiap model Linier Programming paling sedikit terdiri dari dua komponen yaitu : fungsi tujuan, dan kendala. Fungsi Tujuan Adapun tujuan dalam linier programming, yaitu: Minimumkan/Maksimumkan Dalam hal ini peubah deviasi positif dan deviasi negatif adalah peubah-peubah slek dan surplus. Model Linier Programming, nilai

yang tidak diketahui, tetapi akan

diselesaikan secara tidak langsung melalui minimisasi/maksimasi deviasi negatif dan positif dari nilai RHS kendala tujuan. Linier programming mencari nilai solusi secara langsung melalui minimisasi/maksimasi deviasi-deviasi dari nilai RHSnya.


Kendala Tujuan Ada empat jenis kendala tujuan yang berlainan. Maksud setiap jenis kendala itu ditentukan oleh hubungannya dengan fungsi tujuan. Pada Tabel 2.1 disajikan keempat jenis kendala itu. Terlihat bahwa setiap jenis kendala tujuan harus punya satu atau dua variabel deviasi yang ditempatkan pada fungsi tujuan. Dimungkinkan adanya kendalakendala yang tidak memiliki variabel deviasi. Kendala-kendala ini sama seperti kendala-kendala persamaan linier. Persamaan pertama pada Tabel 2.1 maknanya serupa dengan kendala pertidaksamaan ≤ dalam masalah program linier maksimasi. Persamaan kedua maknanya serupa dengan kendala pertidaksamaan ≥ pada masalah program linier minimisasi. Persamaan ketiga memperbolehkan deviasi dua arah yaitu ≤ dan ≥, tetapi persamaan ini mencari penggunaan sumber daya yang diinginkan sama dengan

. Jika kendala persamaan dianggap perlu dalam perumusan model linier

programming, ia dapat dimasukkan dengan menempatkan sebuah artificial variabel , seperti pada persamaan keempat.

Ada dua cara yang bisa digunakan untuk menyelesaikan persoalan-persoalan pemrograman linier ini, yaitu cara grafis dan metode simpleks (Dimyati dan A.Dimyati, 1992). 1. Metode Grafik Metode grarik dapat digunakan pada pemrograman linier jika masalah yang dihadapi mengandung tidak lebih dari dua variabel (Taha, 1982). Menurut Dimyati dan A.Dimyati (1992), metode grafik telah memberikan satu petunjuk penting bahwa untuk memecahkan persoalanpersoalan pemrograman linier, hanya perlu memperhatikan titik ekstrem (titik terjauh) pada ruang solusi atau daerah fisibel. 2. Metode Simpleks Metode simpleks adalah prosedur pemecahan pemrograman linier yang lebih efisien daripada metode grafik. Penerapan metode simpleks pada masalah program linier dikembangkan untuk pertama kali oleh George Dantzig pada tahun 1947 (Hiller dan Liberman, 1980).


Metode

simpleks

merupakan

teknik

yang

paling

berhasil

dikembangkan untuk memecahkan persoalan pemrograman linier yang mempunyai jumlah variabel keputusan dan pembatas yang besar (Dimyati dan A. Dimyati, 1992). Perhitungan metode simpleks merupakan proses iterasi. Hal ini berarti bahwa untuk mencapai solusi yang optimal, perhitungan dilakukan berulangulang mengikuti pola standard secara sistematik. Karakteristik lain pada metode simpleks adalah pada nilai fungsi tujuannya akan sama atau lebih besar pada solusi terbaru dibandingkan dengan solusi terdahulu (Levin et el, 1982). Di dalam menyelesaikan persoalan pemrograman linier dengan menggunakan metode simpleks, bentuk dasar yang digunakan haruslah bentuk standard (Dimyati dan A. Dimyati). Menurut Gillet (1976), untuk mengubah suatu bentuk formulasi pemrograman linier yang belum standard ke dalam bentuk standard dapat dilakukan cara-cara sebagai berikut : a. Peubah tambahan (slack variable) Konversi fungsi ketidaksamaan lebih kecil sama dengan (≤) pada fungsi pembatas memerlukan tambahan suatu peubah yang disebut peubah

tambahan,

peubah

ini

menggambarkan

tingkat

pengangguran dari sumber daya. Jika ada m fungsi ketidaksamaan (≤) pada fungsi pembatas dan terdapat r peubah kebijaksanaan dalam formulasi permasalahan maka dengan penambahan peubah tambahan, fungsi pembatas mengalami perubahan sebagai berikut:


dimana

adalah

peubah

tambahan

(slack

variable).

Penambahan peubah tambahan juga akan mengubah fungsi tujuan menjadi : maks / min b. Peubah buatan Apabila dalam fungsi pembatas terdapat ketidaksamaan lebih besar sama dengan (≥) maka fungsi pembatas dapat diubah menjadi bentuk persamaan dengan mengurangi pertidaksamaan oleh sebuah peubah positif, sebagai berikut :

Peubah

merupakan suatu peubah yang biasa disebut sebagai

peubah tambahan. Metode simpleks belum dapat diterapkan dengan formulasi seperti di atas karena dalam metode simpleks dibutuhkan kondisi-kondisi berikut: 1. Semua konstanta pada sisi kanan persamaan bernilai lebih besar atau sama dengan nol. 2. Setiap

persamaan

harus

mempunyai

sebuah

peubah

berkoefisien satu pada persamaan tersebut dan nol pada persamaan yang lain. Persamaan di atas, agar dapat diselesaikan dengan metode simpleks, maka harus diubah menjadi :

Akibat penambahan peubah buatan

maka perlu

penambahan suatu bilangan (-M) untuk masalah maksimasi pada fungsi tujuan, sehingga fungsi tujuannya menjadi :


Pada fungsi pembatas yang berbentuk persamaan, peubah buatan perlu ditambahkan untuk memenuhi kondisi (2) pada metode simpleks. Perubahan fungsi pembatas yang berbentuk persamaan dengan adanya penambahan peubah buatan adalah sebagai berikut:

menjadi :

dan fungsi tujuannya menjadi :

2.2 Pemrograman Integer (Integer Programming) Persoalan Integer Programming (IP) adalah persoalan pemrograman (programming) di mana pemecahan optimalnya harus menghasilkan bilangan bulat (integer) jadi bukan pecahan. Dengan perkataan lain dari antara berbagai bilangan bulat, harus dicari nilai-nilai variabel yang fisibel dan membuat fungsi tujuan (Objective function) maksimum (Supranto, 1980). Pemrograman

integer

(Integer

Programming)

adalah

suatu

model

pemrograman linier dengan variabel yang digunakan berupa bilangan bulat. jika semua variabel harus berupa bilangan bulat, maka masalah tersebut dinamakan pure integer programming. Jika hanya sebagian yang harus berupa integer, maka disebut mixed integer programming. Integer programming dengan semua variabelnya harus bernilai 0 atau 1 disebut 0-1 integer programming (Garfinkel dan Nemhauser, 1972).


Program bilangan bulat adalah suatu bentuk dari program linier yang asumsi divisibilitasnya melemah. Bentuk ini muncul karena kenyataannya tidak semua variabel keputusan merupakan suatu angka pecahan (Dimyati dan A. Dimyati 1987). Menurut Taha (1975), optimasi bilangan bulat bukan merupakan sebuah persoalan matematika baru, dan dalam penelitian operasional dikenal sejak tahun 1940. Optimasi bilangan bulat penting digunakan pada pemecahan masalah yang disusun sebagai sebuah hasil perkembangan pada bidang penelitian operasional, terutama sekali pada persoalan program linier. Hal itu diperlukan untuk pemecahan model penyusunan pada beberapa atau semua variabel keputusan agar integer (bilangan bulat). Pemrograman bilangan

bulat

(Integer

programming)

dibutuhkan ketika keputusan harus dilakukan dalam bentuk bilangan bulat (bukan pecahan yang sering terjadi bila kita gunakan metode simpleks). Model matematis dari pemrograman bulat sebenarnya sama dengan model linear programming, dengan tambahan batasan bahwa variabel keputusannya harus bilangan bulat. Integer programming adalah suatu program linier dengan tambahan persyaratan bahwa semua atau beberapa variabel bernilai bulat non negatif, tetapi tidak perlu bahwa parameter model juga bernilai bulat. Secara umum menurut Dimyati dan A. Dimyati (1992), model persoalan pemrograman bilangan bulat (Integer Programming) dapat diformulasikan sebagai berikut: Maks/Min :

Berdasarkan :


bilangan bulat (integer) untuk

Algoritma yang dianggap cukup baik untuk memberikan solusi optimum dalam pemrograman bilangan bulat (Integer Programming) adalah pencabangan dan pembatasan (branch and bound) dan pemotongan bidang datar (cutting plane) (Dimyati dan A. Dimyati, 1992). Ada berbagai pendekatan untuk masalah IP. Pendekatan yang akan dibahas di bawah ini termasuk Pembulatan (Rounding), Cabang dan Batas (Branch and Bound), Pemotongan Bidang Datar (Cutting Plane), Relaksasi Lagrangian (Lagrangian Relaxation) dan Benders Dekomposisi (Benders Decomposition) (Bruce A. McCarl dan T.H.Spreen, 1997). a. Pemotongan Bidang Datar (Cutting Plane) Ada berbagai algoritma yang tersedia untuk penyelesaian masalah IP. Alasan banyaknya inilah bahwa tidak ada algoritma telah terbukti secara komputasi yang efisien untuk semua masalah, dan dengan demikian pencarian kontinu untuk algoritma-algoritma yang lebih efektif. Berdasarkan masalah pure integer programming, yaitu, masalah LP standar dengan pembatasan integer pada semua variabel. Ide fundamental yang mendasari algoritma gomory’s cutting plane adalah untuk menambahkan kendala untuk masalah satu per satu sehingga akhirnya memiliki masalah LP dengan solusi optimal dengan koordinat integer (Paul R. Thie, 1979). Pendekatan yang dilakukan dalam teknik pemotongan bidang datar (Cutting plane) adalah dengan membuat pembatas tambahan yang memotong ruang layak dari LP relaksasi sehingga dapat mengeliminasi solusi yang tidak integer . Proses pemotongan akan terus berlangsung sehingga diperoleh jawab dengan seluruh variabel (yang dikehendaki) berharga bilangan bulat (integer) (Dimyati dan A. Dimyati, 1992). Menurut Dimyati dan A. Dimyati (1992), keberhasilan teknik ini sangat terbatas, bergantung pada struktur persoalan yang dihadapi. Artinya


hanya persoalan tertentu yang dapat diselesaikan dengan teknik ini. Karena itu, sekarang teknik ini hampir tidak pernah lagi digunakan. Algoritma IP pertama kali diselesaikan dengan konsep cutting plane. Cutting plane menghapus bagian dari daerah fisibel tanpa menghapus poin solusi bilangan bulat. Ide dasar di balik sebuah cutting plane adalah bahwa titik bulat yang optimal dekat dengan solusi LP optimal, tetapi tidak jatuh di persimpangan kendala sehingga kendala tambahan perlu dipaksakan. Akibatnya, kendala yang ditambahkan untuk memaksa solusi LP integer menjadi tidak layak tanpa menghilangkan solusi bilangan bulat. Hal ini dilakukan dengan menambahkan kendala memaksa variabel nonbasis lebih besar dari nilai nol kecil (Bruce A. McCarl dan T.H.Spreen, 1997). Beberapa poin yang perlu diperhatikan untuk membuat pendekatan Cutting plane. Pertama banyak pemotongan yang mungkin perlu diperbaiki untuk memperoleh sebuah solusi integer. Kedua solusi integer pertama yang ditemukan adalah solusi optimal. Solusi ini ditemukan setelah pemotongan hanya ditambahkan ke daerah hasil solusi optimal. Akibatnya jika algoritma solusi ditemukan, keluar tanpa sebuah solusi yang dapat diterima (Bruce A. McCarl dan T.H.Spreen, 1997). Algoritma bekerja sebagai berikut, pertama-tama menyelesaikan masalah LP asli dengan mengabaikan pembatasan yang integer. Kemudian, jika solusi ini memiliki semua koordinat integer, maka itu merupakan solusi optimal untuk masalah IP, masalah selesai. jika tidak, buat kendala baru yang akan menambah masalah. Kendala ini akan memiliki dua sifat dasar: pertama, solusi optimal noninteger untuk masalah LP asli tidak akan memenuhi kendala ini, dan kedua, semua solusi layak integer masalah asli akan memenuhi kendala asli baru. Sehingga kendala ini pada dasarnya memotong subset dari himpunan solusi layak untuk masalah LP, tapi subset yang tidak berisi integer yang layak, tambahkan kendala baru lagi (Paul R. Thie, 1979).


Langkah-langkah dari algoritma gomory’s cutting plane untuk masalah IP murni: 1. Memecahkan masalah LP yang sesuai hanya mengabaikan pembatasan integer pada X. Jika solusi ini memiliki semua koordinat integer, maka itu adalah solusi optimal untuk masalah asli. 2. Jika tidak kendala baru ditambahkan ke masalah. a) Untuk membangun kendala ini, memilih baris dari solusi akhir tabel optimal dari masalah LP dengan non terpisahkan konstan istilah bi. (menggunakan baris yang mengandung istilah konstan dengan nilai pecahan terbesar dapat mengurangi jumlah iterasi yang diperlukan untuk konvergensi.) b) Seandainya baris ke-i dipilih dan persamaan yang sesuai adalah

Maka bentuk kendala

Dimana fij = aij – [ aij ] = bagian pecahan dari aij fi = bi – [ bi ] = bagian pecahan dari bi x = sebuah variabel slack baru, terbatas menjadi nonnegatif dan integral c)

Tambahkan kendala ini ke masalah dan kembali ke langkah 1. (Paul R. Thie, 1979). Kelemahan dari algoritma cutting plane adalah kesalahan-kesalahan

pada pembulatan yang dilakukan dalam perhitungan dapat menghasilkan jawaban bilangan bulat yang salah. Selain itu jawaban dari persoalan masih belum fisibel berarti tidak ada jawaban bilangan bulat yang diperoleh sampai jawaban bilangan bulat yang optimal dicapai tadi, dan ini berarti bahwa tidak ada jawaban bilangan bulat yang baik jika perhitungan dihentikan lebih awal sebelum mencapai hasil jawaban yang optimal (Aswan, 1979). b. Pembulatan (Rounding)


Pembulatan adalah pendekatan yang paling naif untuk solusi masalah IP. Pendekatan pembulatan melibatkan pemecahan masalah sebagai masalah LP diikuti dengan upaya untuk membulatkan solusi ke solusi yang integer dengan: a) menghilangkan semua bagian pecahan, atau b) mencari tahu solusi yang memenuhi dimana nilai-nilai variabel yang disesuaikan dengan dekatnya lebih besar atau lebih kecil nilai integer. Pembulatan mungkin adalah pendekatan yang paling umum untuk memecahkan masalah IP. Masalah LP Sebagian besar melibatkan variabel dengan nilai pecahan solusi yang pada kenyataannya adalah integer (yaitu, kursi diproduksi, ayam dipotong). Istilah pecahan dalam solusi tidak masuk akal, tetapi kadang-kadang dapat diterima jika pembulatan memperkenalkan perubahan yang sangat kecil dalam nilai variabel (pembulatan yaitu 1003421,1-1.003.421 atau bahkan 1.003.420 mungkin dapat diterima) (Bruce A. McCarl dan T.H.Spreen, 1997). Secara umum, pembulatan sering praktis, tetapi harus digunakan dengan hati-hati. Salah satu harus membandingkan solusi yang dibulatkan dan tidak dibulatkan untuk melihat apakah setelah pembulatan: a) kendala memenuhi secara memadai, dan b) apakah perbedaan antara LP optimal dan pembulatan nilai fungsi objektif cukup kecil. Jika demikian IP biasanya tidak efektif dan solusi yang bulat dapat digunakan. Di sisi lain, jika ditemukan fungsi tujuan bulat diubah secara bermakna atau kendala melanggar dari sudut pandang pragmatis, maka latihan IP formal perlu dilakukan (Bruce A. McCarl dan T.H.Spreen, 1997). c. Relaksasi Lagrangian (Lagrangian Relaxation) Relaksasi Lagrangian (Geoffrion (1974), Fisher (1981, 1985)) merupakan salah satu bidang pengembangan algoritmik IP. Relaksasi Lagrangian mengacu pada prosedur dimana beberapa kendala yang direlaksasikan ke dalam fungsi tujuan menggunakan sebuah pendekatan yang dibentuk oleh pengganda Lagrangian. Bentuk dasar Relaksasi Lagrangian untuk program bilangan bulat campuran: Maksimum

CX + FY

Kendala

AX + GY ≤ b DX + HY ≤ e


X ≥ 0, Y ≥ 0 dan integer melibatkan penemuan suatu himpunan Lagrange Multiplier untuk beberapa kendala dan merelaksasi himpunan kendala ke dalam fungsi tujuan. Mengingat bahwa yang dipilih untuk direlaksasi himpunan kedua kendala menggunakan lagrange multiplier masalah menjadi: Maksimum CX + FY – λ( DH + HY – e ) AX + GY ≤ b X ≥ 0, Y ≥ 0 dan integer Ide utama adalah untuk menghilangkan kendala yang sulit dari masalah sehingga program integer jauh lebih mudah untuk dipecahkan. Masalah IP dengan struktur seperti itu dari masalah transportasi dapat langsung diselesaikan dengan LP. Caranya kemudian adalah memilih kendala yang tepat untuk direlaksasi dan untuk mengembangkan nilai-nilai untuk pengali lagrange mengarah ke solusi yang tepat. Relaksasi Lagrangian telah digunakan dalam dua pengaturan: 1) untuk meningkatkan kinerja batas pada solusi, dan 2) untuk mengembangkan solusi yang dapat disesuaikan secara langsung atau melalui heuristik sehingga mereka layak dalam keseluruhan masalah (Fisher (1981, 1985)) . Sebuah hasil penting Relaksasi Lagrangian adalah merelaksasi masalah yang memberikan batas atas solusi untuk masalah yang tidak direlaksasi pada setiap tahap. Relaksasi Lagrangian telah banyak digunakan dalam algoritma cabang dan terikat untuk menurunkan batas atas untuk masalah untuk melihat apakah traversal bawah yang dicabangkan layak (Bruce A. McCarl dan T.H.Spreen, 1997). d. Dekomposisi Bender (Benders Decomposition) Algoritma lain untuk IP disebut Dekomposisi Bender. Algoritma ini memecahkan program bilangan bulat campuran melalui eksploitasi struktural. Benders mengembangkan prosedur, selanjutnya disebut Dekomposisi Bender, yang menguraikan masalah mixed integer menjadi dua masalah yang diselesaikan secara iteratif - masalah utama bilangan bulat dan subproblem linier.


Keberhasilan prosedur melibatkan struktur subproblem dan pilihan subproblem tersebut. Prosedur dapat bekerja sangat buruk untuk struktur tertentu. Masalah dekomposisi mixed IP adalah: Maksimum FX + CZ Kendala

GX

≤ b1

HX + AZ

≤ b2

DZ

≤ b3

X integer, Z ≥ 0 Pengembangan dekomposisi masalah ini berlangsung dengan iteratif mengembangkan titik layak X* dan memecahkan subproblem yang: Maksimum

CZ

Kendala

AZ ≤ b2 – HX* (α) DZ ≤ b3 Z

(γ)

≥0

Solusi untuk subproblem ini menghasilkan variabel dual dalam tanda kurung. Q merupakan penafsiran dari CZ. Dalam mengubah "master" Masalah dibentuk sebagai berikut: Maksimum X,α,γ,Q

FX + Q Q ≤ αi (b2 - HX) + γib3 i = 1, 2, . . . p GX ≤ b1 X integer, Q 0

Penggunaan dekomposisi Benders melibatkan penguraian masalah yang tepat dan / atau struktur masalah yang akan menuju kesatu titik dengan cepat. Pernyataan umum yang dapat dibuat adalah: a) Metode dekomposisi tidak bekerja dengan baik ketika variabel X yang dipilih oleh masalah master tidak menghasilkan subproblem layak. Dengan demikian, semakin akurat kendala dalam masalah master menggambarkan kondisi subproblem, semakin cepat akan konvergensi. (Lihat Geoffrion dan Graves, Danok, McCarl dan White (1978), Polito, Magnanti dan Wong, dan Sherali untuk diskusi.)


b) Daerah feasible dari masalah master baik lebih dibatasi. (Lihat Magnanti dan Wong,. Dan Sherali) c) Bila mungkin, kendala harus dimasukkan dalam masalah master menghalangi solusi layak yang belum realistis (suboptimal) untuk keseluruhan masalah. (Lihat kendala mesin minimum di Danok, McCarl dan White, 1978.) (Bruce A. McCarl dan T.H.Spreen, 1997).

2.3 Pencabangan dan Pembatasan (Branch and Bound) Branch and bound bukan sebuah teknik solusi khusus terbatas untuk masalah integer programming. Branch and bound adalah pendekatan solusi yang dapat diterapkan pada beberapa jenis masalah. Pendekatan Branch and bound didasarkan pada prinsip bahwa himpunan total solusi layak dapat dipartisi menjadi subset yang lebih kecil dari solusi. Subset yang lebih kecil ini kemudian dapat dievaluasi secara sistematis sampai solusi terbaik ditemukan. Ketika pendekatan Branch and bound diterapkan untuk masalah integer programming, akan digunakan konjungsi dengan pendekatan solusi noninteger yang normal (Paul R. Thie, 1979). Menurut Taha (1975), untuk melaksanakan teknik pencabangan dan pembatasan (branch and bound) ada dua operasi dasar, yaitu: 1. Pencabangan (Branching), merupakan pembagian persoalan jawab kontinu menjadi subpersoalan di mana semuanya juga kontinu. 2. Pembatasan (Bounding), merupakan pembatasan setiap subpersoalan yang dibuat dengan pencabangan. Batas ini penting untuk tingkatan jawab optimal dari sub persoalan dan penemuan jawab optimal bilangan bulat. Teknik pencabangan dan pembatasan (branch and bound) mencari solusi optimal dari suatu persoalan pemrograman bilangan bulat (Integer Programming) dengan mengenumerasi titik-titik dalam daerah fisibel dari suatu subpersoalan (Dimyati dan A. Dimyati, 1992).


Branch and Bound adalah algoritma umum untuk mencari solusi optimal dari berbagai masalah optimasi. Metode ini pertama kali diperkenalkan oleh A.H. Land dan A.G. Doig pada tahun 1960. Gagasan penting dari cabang-dan-terikat adalah untuk membagi daerah layak dan mengembangkan batas

pada z*. Untuk masalah maksimisasi, batas bawah

adalah nilai tertinggi dari setiap titik bulat layak yang diperoleh. Batas atas diberikan oleh nilai optimal dari program linier yang asli atau dengan nilai terbesar untuk fungsi tujuan pada setiap kotak yang "menggantung". Langkah selanjutnya, harus mencabangkan ke (pindah ke) subdivisi lain dan menganalisanya. Begitu selanjutnya, jika solusi belum diperoleh i) Program linier atas Lj tidak layak ii) Solusi optimal program linier atas Lj adalah integer; atau iii) Nilai dari solusi program linier zj atas Lj memenuhi zj ≤ (jika maksimasi), maka Lj tidak perlu dibagi. Dalam kasus ini, IP terminologi mengatakan bahwa Lj telah terukur (fathomed). kasus (i) disebut fathoming oleh ketidaklayakan, (ii) fathoming oleh kebulatan dan (iii) fathoming oleh batas (Bradley dkk, 1977). Prinsip dasar metode ini adalah memecah daerah fisibel suatu masalah program linier dengan membuat subproblem-subproblem. Ada dua konsep dasar dalam algoritma branch and bound : 1. Branching adalah proses membagi-bagi permasalahan menjadi subproblemsubproblem yang mungkin mengarah ke solusi. 2. Bounding adalah suatu proses untuk mencari/menghitung batas atas (dalam masalah minimisasi) dan batas bawah (dalam masalah maksimisasi) untuk solusi optimal pada subproblem yang mengarah ke solusi. Metode branch and bound diawali dengan menyelesaikan program linier dari suatu masalah program integer. Jika semua nilai variabel keputusan solusi optimal sudah berupa integer, maka solusi tersebut merupakan solusi optimal program linier integer. Jika tidak, dilakukan pencabangan dan penambahan batasan pada program liniernya kemudian diselesaikan.


Winston (2004) menyebutkan bahwa nilai fungsi objektif optimal untuk program linier integer lebih kecil sama dengan nilai fungsi objektif optimal untuk program linier (masalah maksimisasi), sehingga nilai fungsi objektif optimal program linier merupakan batas atas bagi nilai fungsi objektif optimal untuk masalah program linier integer. Diungkapkan pula oleh Winston (2004) bahwa nilai fungsi objektif optimal untuk suatu kandidat solusi merupakan batas bawah nilai fungsi objektif optimal untuk masalah program linier integer asalnya. Suatu kandidat solusi diperoleh jika solusi dari suatu subproblem sudah memenuhi kendala integer pada masalah program linier integer, artinya semua variabelnya sudah bernilai integer. Berikut ini adalah langkah-langkah penyelesaian suatu masalah maksimisasi dengan metode branch and bound : 1) Langkah 0 Didefinisikan z sebagai batas bawah dari nilai fungsi objektif (solusi) program linier integer yang optimal. Pada awalnya ditetapkan z = -∞ dan i = 0. 2) Langkah 1 Subproblem program linier (PL)(i) dipilih sebagai bagian masalah berikutnya untuk dipecahkan. Subproblem PL(i) diselesaikan. a) Jika PL(i) terukur dan solusi program linier yang ditemukan lebih baik maka batas bawah z diperbarui. Jika tidak bagian masalah (subproblem) baru i dipilih dan langkah 1 diulangi. Jika semua subproblem telah dipecahkan, maka proses dihentikan. b) Jika PL(i) tidak terukur, proses dilanjutkan ke langkah 2 untuk melakukan pencabangan PL(i) Suatu subproblem dikatakan terukur (fathomed) jika terdapat kondisi sebagai berikut : 1. Subproblem tersebut tak fisibel, sehingga tidak dapat menghasilkan solusi optimal untuk program linier integer. 2. Subproblem tersebut menghasilkan suatu solusi optimal dengan semua variabelnya bernilai integer. Jika solusi optimal ini mempunyai nilai fungsi


objektif yang lebih baik daripada solusi fisibel yang diperoleh sebelumnya, maka solusi ini menjadi kandidat solusi optimal dan nilai fungsi objektifnya menjadi batas bawah nilai fungsi objektif optimal bagi masalah program linier integer pada saat itu. Bias jadi subproblem ini menghasilkan solusi optimal untuk masalah program linier integer. 3. Nilai fungsi objektif optimal untuk subproblem tersebut tidak melebihi batas bawah saat itu, maka subproblem ini dapat dieliminasi. 3) Langkah 2 Dipilih salah satu variabel xj yang nilai optimalnya adalah

yang tidak

memenuhi batasan integer dalam solusi PL(i). Bidang disingkirkan dengan membuat dua subproblem program linier, yaitu dan

, sehingga diperoleh kendala subproblem baru sebagai

berikut : a. Subproblem baru 1 : kendala subproblem lama + kendala b. Subproblem baru 2 : kendala subproblem lama + kendala dengan dengan

didefinisikan sebagai integer terbesar yang kurang dari atau sama . Selanjutnya kembali ke langkah 1 (Winston, 1975).

Ringkasan langkah-langkah metode branch and bound dalam menentukan solusi integer optimal untuk model maksimisasi adalah sebagai berikut: a) Dapatkan solusi simpleks optimal dari model program linear dengan batasan integer yang dilepaskan b) Tentukan solusi simpleks relaxed sebagai batas atas sedangkan solusi hasil pembulatan ke bawah sebagai batas bawah pada node 1. c) Pilih peubah dengan bagian pecahan yang terbesar untuk percabangan. Ciptakan dua batasan baru untuk peubah ini yang mencerminkan pembagian nilai integer. Hasilnya adalah sebuah batasan ≤ dan sebuah batasan ≥. d) Ciptakan dengan node baru, satu dengan batasan ≤ dan satu dengan batasan ≥ e) Selesaikan model program linear relaxed dengan batasan baru yang ditambahkan pada tiap node


f) Solusi simpleks relaxed adalah merupakan batas atas pada tiap node, dan solusi maksimum integer merupakan batas bawah dari node. g) Jika proses ini menghasilkan solusi integer feasible dengan nilai batas atas terbesar pada akhir node mana saja, maka solusi integer optimal tercapai. Jika tidak muncul suatu solusi integer fisibel, lakukan

percabangan dari node

dengan batas atas terbesar. h) Ulangi langkah c. (Winston, 2004) Suatu bentuk khusus dari algoritma cabang dan terikat untuk nol-satu program yang dikembangkan oleh Balas. Algoritma ini disebut enumerasi implisit. Metode ini juga telah diperluas untuk kasus bilangan bulat campuran seperti yang diterapkan di LINDO (Schrage, 1981b) (Bruce A. McCarl dan T.H.Spreen, 1997).


Inisialisasi pohon ruang

Mulai

solusi Branch and bound

Pohon kosong?

Ambil submasalah

Lakukan iterasi untuk setiap kemungkinan

Apakah a tidak Output solusi

Akhir

Ya

mungkin mengarah ke solusi atau a < b?

Bunuh cabang

Tidak

Ya

Apakah variabel

Buat cabang

bertipe pecahan?

b Tidak Ya Apakah solusi bertipe integer?

b = maks

Tidak Gambar 2.1 Flowchart Algoritma Branch and Bound untuk IP optimasi maksimum


Mulai

Pohon kosong?

Inisialisasi pohon ruang solusi Branch and bound

Ambil submasalah

Lakukan iterasi untuk setiap kemungkinan

Apakah a tidak Output solusi

Akhir

Ya

mungkin mengarah ke solusi atau a > b?

Bunuh cabang

Tidak

Ya

Apakah

Buat cabang

variabel

b Tidak Ya Apakah solusi bertipe integer?

b = min(b,a)

Tidak Gambar 2.2 Flowchart Algoritma Branch and Bound untuk IP optimasi minimum


Keuntungan dari cara pencabangan dan pembatasan adalah cara yang efisien untuk mendapatkan seluruh jawaban layak (fisibel), sedangkan kerugian cara ini adalah ia akan rnencari seluruh jawaban program linier pada setiap titik. Pada persoalan yang besar akan memerlukan waktu yang cukup lama, terutama bila yang dibutuhkan hanya keterangan mengenai nilai objektif yang optimum (Aswan, 1979).


Mulai Data harga perumahan dan ketersediaan bahan baku

Formulasi permasalahan penentuan peubah keputusan Sesuai dengan permasalahan

Formulasi fungsi tujuan Maksimasi keuntungan

Pemrograman linier Solusi optimal dan non integer Pemograman Bilangan Bulat (Integer Programming)

Metode Branch and Bound

Tidak

Solusi integer Ya Selesai

Gambar 2.3 Skema Pengolahan Data


BAB 2 LANDASAN TEORI

Recommend Documents