BAB 2 PROGRAM INTEGER
2.1
Program Linear
Program linear merupakan metode matematika untuk mengalokasikan sumber daya yang biasanya terbatas supaya mencapai hasil yang optimal, misalnya memaksimumkan keuntungan atau meminimumkan biaya. Oleh karena itu progam linear banyak dipergunakan dalam menyelesaikan masalah-maslah, antara lain ekonomi dan industri. Para pengambil keputusan sering menghadapi masalah dalam menentukan alokasi sumber daya yang terbatas karena mereka menginginkan hasil yang seoptimal mungkin. Dengan menggunakan model program linear, para pengambil keputusan dapat memprediksi hasil yang akan diperoleh. Bentuk umum model program linear adalah: Max(min)Z =
X
c j xj .
Kendala X
aij xj (≤, =, ≥)bi , (i = 1, 2, ..., m), xj ≥ 0, (j = 1, 2, ..., m).
6 Universitas Sumatera Utara
Di mana xj : banyaknya kegiatan j (j = 1, 2, ..., n), Z : nilai fungsi tujuan, cj : sumber per-unit kegiatan, untuk masalah memaksimalkan cj menunjukkan keuntungan per-unit per-kegiatan, sedangkan untuk kasus meminimalkancj menunjukkan biaya per-unit per-kegiatan, b : besarnya sumber daya i (i = 1, 2, ..., m), aij : banyaknya sumber daya i yang dipakai sumber daya j.
2.2
Program Integer
Pada masalah Program Linear penyelesaian optimalnya dapat berupa bilangan real yang berarti penyelesaian bisa berupa bilangan pecahan. Untuk penyelesaian yang berbentuk pecahan jika mengalami pembulatan ke integer terdekat maka hasil yang diperoleh bisa menyimpang jauh dari yang diharapkan. Akan tetapi banyak permasalahan di kehidupan nyata yang memerlukan penyelesaian variabel keputusannya berupa integer sehingga harus dicari model penyelesaian masalah sehingga diperoleh penyelesaian integer yang optimum. Program Integer merupakan pengembangan dari Program Linear di mana beberapa atau semua variabel keputusannya harus berupa integer. Jika hanya sebagian variabel keputusannya merupakan integer maka disebut Program Integer campuran ( mixed Integer Progamming ). Jika semua variabel keputusannya bernilai integer disebut Program Integer murni ( pure Integer Progamming ). 7 Universitas Sumatera Utara
Sedangkan Program Integer 0-1 merupakan bentuk Program Integer di mana semua variabel keputusannya harus bernilai integer 0 atau 1 (binary). Bentuk umum model Program Integer adalah: Max(min)Z =
X
c j xj .
Kendala X
aij xj (≤, =, ≥)bi , (i = 1, 2, ..., m), xj ≥ 0, (j = 1, 2, ..., m),
xj bernilai integer untuk beberapa atau semua j. Bentuk umum model Program Integer 0-1 adalah: Max(min)Z =
X
c j xj .
Kendala X
aij xj (≤, =, ≥)bi , (i = 1, 2, ..., m),
xj = 0 atau xj = 1, (j = 1, 2, ..., n).
2.3
Metode Solusi Dalam Integer Progamming Pendekatan Pembulatan
Suatu metode yang sederhana dan kadang-kadang praktis untuk menyelesaikan integer progamming adalah dengan membulatkan hasil variabel keputusan yang diperoleh melalui LP. Pendekatan ini mudah dan praktis dalam hal usaha,
8 Universitas Sumatera Utara
waktu dan biaya yang diperlukan untuk memperoleh suatu solusi. Bahkan, pendekatan pembulatan dapat merupakan cara yang sangat efektif untuk masalah integer progamming yang besar dimana biaya-biaya hitungan sangat tinggi atau untuk masalah nilai-nilai solusi variabel keputusan sangat besar. Contohnya, pembulatan nilai solusi jumlah pensil yang harus diproduksi dari 14.250,2 menjadi 14.250,0 semestinya dapat diterima. Namun demikian sebab utama kegagalan pendekatan ini adalah bahwa solusi yang diperoleh mungkin bukan solusi integer optimum yang sesungguhnya. Dengan kata lain, solusi pembulatan dapat lebih jelek dibanding solusi integer optimum yang sesungguhnya atau mungkin merupakan solusi tak layak. Ini membawa konsekuensi besar jika jumlah produk-produk seperti pesawat angkut komersial atau kapal perang yang harus diproduksi dibulatkan ke bilangan bulat terdekat. Tiga masalah berikut disajikan untuk mengilustrasikan prosedur pembulatan: Masalah 1 Maksimumkan
Z
= 100X1 + 90X2
Dengan syarat
10X1 + 7X2 ≤ 70 5X1 + 10X2 ≤ 50 X1 +
X2 ≥ 0
9 Universitas Sumatera Utara
Masalah 2 Minimumkan
Z
= 200X1 + 400X2
Dengan syarat
10X1 + 25X2 ≥ 100 3X1 +
2X2 ≥ 12
X1 +
X2 ≤ 0
Masalah 3 Maksimumkan
Z
Dengan syarat
= 80X1 + 100X2 4X1 + 2X2 ≤ 12 X1 + 5X2 ≤ 15 X1 +
X2 ≤ 0
Perbandingan antara solusi dengan metode simpleks tanpa pembatasan bilangan bulat, pembulatan ke bilangan bulat terdekat dan solusi integer optimum yang sesungguhnya untuk ketiga masalah tersebut adalah:
10 Universitas Sumatera Utara
Masalah
1
2
3
Solusi dengan metode
Dengan pembulatan
Bulat optimum
simpleks
terdekat
sesungguhnya
X1 = 5, 38
X1 = 5
X1 = 7
X2 = 2, 31
X2 = 2
X2 = 0
Z = 746, 15
Z = 680
Z = 700
X1 = 1, 82
X1 = 2
X1 = 3, X2 = 3
X2 = 3, 27
X2 = 3
X1 = 5, X2 = 2
Z = 1.672, 73
Z = tak layak
Z = 1.800
X1 = 2, 14
X1 = 2
X1 = 0
X2 = 1, 71
X2 = 2
X2 = 3
Z = tak layak
Z = 300
Z = 343
Masalah pertama adalah masalah maksimasi, dimana solusi pembulatan menghasilkan keuntungan 680, hanya lebih kecil 20 dibanding yang dihasilkan solusi bulat optimum 700. Masalah kedua adalah masalah minimasi dimana solusi pembulatan adalah tak layak. Ini menunjukan bahwa meskipun pendekatan adalah sederhana, namun kadang-kadang menyebabkan solusi tak layak. Untuk mencegah ketidaklayakan, nilai solusi simpleks dalam masalah minimasi harus dibulatkan ke atas. Misalnya, pada masalah kedua jika solusi dibulatkan ke atas diperoleh X1 = 2 dan X2 = 4 dan merupakan solusi layak. Sebaliknya, pada masalah maksimasi nilai solusi simpleks semestinya dibulatkan ke bawah. Pada msalah ketiga, solusi pembulatan juga tak layak. Namun, seperti dalam masalah minimasi, jika solusi simpleknya X1 = 2, 14 dan X2 = 1, 71 dibulatkan ke bawah menjadi X1 = 2 dan X2 = 1, maka solusinya menjadi
11 Universitas Sumatera Utara
layak. Ini dapat dibuktikan dengan meneliti masing-masing kendala model dengan nilai variabel keputusan yang telah dibulatkan kebawah. Suatu metode yang serupa dengan pendekatan pembulatan adalah prosedur coba-coba (trial and eror ). Dengan menggunakan cara ini, pengambil keputusan mengamati solusi integer dan memilih solusi yang mengoptimumkan nilai fungsi tujuan. Metode ini sangat tidak efektif jika masalahnya melibatkan sejumlah besar kendala dan variabel. Terlebih lagi, memeriksa kelayakan setiap solusi yang dibulatkan banyak memakan waktu.
2.4
Pendekatan Grafik
Masalah Integer Progamming yang melibatkan hanya dua variabel dapat diselesaikan secara grafik. Pendekatan ini identik dengan metode grafik LP dalam semua aspek, kecuali bahwa solusi optimum harus memenuhi persyaratan bilangan bulat. Mungkin pendekatan termdah untuk menyelesaikan masalah integer progamming dua dimensi adalah menggunakan kertas grafik dan mengambarkan sekumpulan titik-titik integer dalam ruang solusi layak. Masalah berikut akan diselesaikan dengan pendekatan grafik. Maksimumkan Dengan syarat
Z
= 100X1 + 90X2 10X1 + 7X2 ≤ 70 5X1 + 10X2 ≤ 50 X1 ; X2 ≥ non negatif integer
12 Universitas Sumatera Utara
Model ini serupa dengan model LP biasa. Perbedaannya hanya pada kendala terakhir yang mengharapkan bahwa variabel terjadi pada nilai non negatif integer. Solusi grafik masalah ini ditunjukkan pada gambar di bawah ini: X2
10 10X1 + 7X2 = 70
Z = 746, 15
5 C
Z = 700 B
A 0
7
5X1 + 10X2 = 50 X1 10
Ruang solusi layak adalah OABC. Solusi optimum masalah LP ditunjukkan pada titik B, dengan X1 = 5, 38 dan X2 = 2, 31 serta Z = 746, 15. Untuk mencari solusi integer optimum masalah ini, garis Z (slope = -9/10) digeser secara sejajar dari titik B menuju titik asal. Solusi integer optimum adalah titik integer pertama yang bersinggungan dengan garis Z. Titik itu adalah A, dengan X1 = 7 dan X2 = 0 serta Z = 700.
13 Universitas Sumatera Utara
2.5
Pendekatan Gomory (Cutting Plane Algorithm)
Suatu prosedur sistematik untuk memperoleh solusi integer optimum terhadap pure integer progamming pertama kali dikemukakan oleh R.E. Gomory. Ia kemudian memperluas prosedur ini untuk menangani kasus yang lebih sulit yaitu mixed integer progamming. Langkah-langkah prosedur Gomory diringkas seperti berikut: 1. Selesaikan masalah integer progamming dengan menggunakan metode simpleks. Jika masalah sederhana, ia dapat diselesaikan dengan pendekatan grafik, sehingga pendekatan Gomory kurang efisien. 2. Periksa solusi optimum. Jika semua variabel basis memiliki nilai integer, solusi optimum integer telah diperoleh dan proses solusi telah berakhir. Jika satu atau lebih variabel basis masih memiliki nilai pecah, teruskan ke tahap 3. 3. Buatlah suatu skala Gomory (suatu bidang pemotong atau cutting plane) dan cari solusi optimum melalui prosedur dual simpleks. Kembali ke tahap 2.
2.6
Kendala Gomory Dalam Pure Integer Progamming
Tabel optimum masalah LP di bawah ini merupakan tabel solusi optimum kontinyu
14 Universitas Sumatera Utara
Basis
X1
Xm
w1
wn
Solusi
Z
0...
0
c1···
cn
b0
X1
1...
0
a11···
a1n
b1
Xm
0
1
am1
amn
b1
• Variabel Xi (i = 1, ..., m) menunjukan variabel basis. • Variabel Xj (j = 1, ..., n) adalah variabel non bebas. Perhatikan persamaan ke i dimana variabel X1 diasumsikan bernilai non integer Xi = bi −
X
aij wj
dimana b non integer
Kemudian pisahkan bi dan aij menjadi bagian yang bulat dan bagian pecah non negatif seperti berikut: bi = bi + fi jadi fi = bi − bi , dimana 0 ≤ fi ≤ 1 aij = aij + fij jadi fij = aij − aij , dimana 0 ≤ fij ≤ 1
2.7
Metode Branch dan Bound
Metode Branch and Bound merupakan kode komputer standar untuk integer progamming, dan penerapan-penerapan dalam praktek tampaknya menyarankan bahwa metode ini lebih efisien dibanding dengan pendekatan Gomory. Teknik ini dapat diterapkan baik untuk masalah pure maupun mixed integer progamming.
15 Universitas Sumatera Utara
Langkah-langkah metode Branch and Bound untuk masalah maksimasi dapat dilakukan seperti berikut: 1. Selesaikan masalah LP dengan metode simpleks biasa tanpa pembatasan bilangan bulat. 2. Teliti solusi optimumnya. Jika variabel basis yang diharapkan bulat adalah bulat, solusi optimum bulat telah tercapai. Jika satu atau lebih variabel basis yang diharapkan bulat ternyata tidak bulat, lanjutkan ke langkah 3. 3. Nilai solusi pecah yang layak dicabangkan ke dalam sub-sub masalah. Tujuannya adalah untuk menghilangkan solusi kontinyu yang tidak memenuhi persyaratan bulat dalam masalah itu. Pencabangan itu dilakukan melalui kendala-kendala mutually exclusive yang perlu untuk memenuhi persyaratan bulat dengan jaminan tidak ada solusi bulat layak yang tidak diikut sertakan. 4. Untuk setiap sub-masalah, nilai solusi optimum kontinyu fungsi tujuan ditetapkan sebagai batas atas. Solusi bulat terbaik menjadi batas bawah (pada awalnya, ini adalah solusi kontinyu yang dibulatkan ke bawah). Sub-sub masalah yang memiliki batas atas kurang dari batas bawah yang ada, tidak diikut sertakan pada analisa selanjutnya. Suatu solusi bulat layak dalah sama baik atau lebih baik dari batas atas untuk setiap sub masalah yang dicari. Jika solusi yang demikian terjadi, suatu sub masalah dengan batas atas terbaik dipilih untuk dicabangkan. Kembali
16 Universitas Sumatera Utara
ke langkah 3. Untuk memperoleh gambaran yang lebih jelas tentang metode Branch and Bound, perhatikan contoh masalah berikut: Maksimumkan Dengan syarat
Z
= 3X1 + 5X2 2X1 + 4X2 ≤ 25 X1
≤8 2X2 ≤ 10
X1 ;
X2 non negatif integer
Solusi optimum kontinyu masalah ini adalah X1 = 8, X2 = 2, 26 dan Z = 35, 25. Solusi ini menunjukan batas awal. Batas bawah adalah solusi yang dibulatkan ke bawah X1 = 8, X2 = 2 dan Z = 34. Dalam metode Branch and Bound, masalah itu dibagi ke dalam dua bagian untuk mencari nilai solusi bulat yang mungkin bagi X1 dan X2 . Untuk melakukan ini, variabel dengan nilai solusi pecah yang memiliki bagian pecah terbesar dipilih. Karena pada solusi ini hanya X2 yang memiliki bagian pecahan, ia dipilih. Untuk menghilangkan bagian pecah dari nilai X2 = 2, 25, dua kendala baru dbuat. Kendala-kendala ini mewakili dua bagian baru dari masalah itu. Dalam hal ini, dua nilai bulat terdekat terhadap 2,25 adalah 2 dan 3. Sehingga diperoleh dua masalah baru melalui dua kendala mutually exclusive, X2 ≤ 2 dan X2 ≥ 3, yang akan diuraikan berikut ini sebagai bagian dari A dan B. Kendala-kendala ini secara
17 Universitas Sumatera Utara
efektif menghilangkan semua nilai pecah yang mungkin bagi X2 , antara 2 dan 3. Pengaruhnya mereka mengurangi ruang solusi layak sedemikian rupa sehingga angka solusi bulat yang diealuasi pada masalah ini makin sedikit. Bagian A Maksimumkan
Z
= 3X1 + 5X2
Dengan syarat
2X1 + 4X2 ≤ 25 X1
≤8 2X2 ≤ 10 (berlebih) X2 ≤ 2
X1 ;
X2 ≥ 0
Bagian B Maksimumkan
Z
Dengan syarat
= 3X1 + 5X2 2X1 + 4X2 ≤ 25 X1
≤8 2X2 ≤ 10 X2 ≤ 3
X1 ;
X2 ≥ 0
Bagian A dan B diselesaikan tanpa pembatasan bilangan bulat dengan metode simpleks. Solusi grafik kedua bagian itu ditunjukkan pada gambar dibawah ini. Solusi simpleknya adalah: 18 Universitas Sumatera Utara
Bagian A : X1 = 8, X2 = 2, dan Z = 34, Bagian B : X1 = 6, 5, X2 = 3, dan Z = 34, 5. Bagian A menghasilkan suatu solusi yang semuanya bulat. Untuk bagian A batas atas dan bawah adalah Z = 34. Solusi pecah bagian B membenarkan pencarian lebih lanjut karena menghasilkan nilai fungsi tujuan yang lebih besar dari batas atas bagian A. Sangat mungkin bahwa pencarian lebih lanjut dapat menghasilkan suatu solusi yang semuanya bulat dengan nilai fungsi tujuan melebihi batas atas bagian A = 34. Bagian B dicabangkan ke dalam dua sub bagian, b1 dan b2 , pertama dengan kendala X1 ≤ 6 dan yang lain dengan X2 ≥ 7. Kedua sub-masalah dinyatakan sebagai berikut: Sub bagian B1 Maksimumkan
Z
= 3X1 + 5X2
Dengan syarat
2X1 + 4X2 ≤ 25 X1
≤ 8 (berlebih) 2X2 ≤ 10 X2 ≥ 3
X1 X1 ;
≤6 X2 ≥ 0
19 Universitas Sumatera Utara
Sub bagian B2 Maksimumkan
Z
= 3X1 + 5X2 2X1 + 4X2 ≤ 25
Dengan syarat
X1
≤8 2X2 ≤ 10 X2 ≥ 3
X1 X1 ;
≥7 X2 ≥ 0
Solusi simpleksnya adalah : Sub-bagian B1 : X1 = 6, X2 = 3, 25 dan Z = 34, 25, Sub-bagian B2 : tidak layak. Karena sub-bagian B1 menghasilkan nilai fungsi tujuan yang lebih besar dari 34 (batas atas bagian A), maka harus dicabangkan lagi ke dalam dua sub masalah, dengan kendala X2 ≤ 3 dan X2 ≥ 4. Kedua kendala sub masalah diberi nama bagian B1 a dan B1 b.
20 Universitas Sumatera Utara
Bagian B1 a Maksimumkan
Z
Dengan syarat
= 3X1 + 5X2 2X1 + 4X2 ≤ 25 2X2 ≤ 10 (berlebih) X2 ≤ 3 X2 ≥ 3 X1 X1 ;
≤6 X2 ≥ 0
Bagian B1 b Maksimumkan
Z
= 3X1 + 5X2
Dengan syarat
2X1 + 4X2 ≤ 25 2X2 ≤ 10 X2 ≥ 3 (berlebih) X2 ≥ 4 X1 X1 ;
≤6 X2 ≥ 0
Solusi optimum dengan metode simpleks adalah : Sub-bagian B1 a : X1 = 6, X2 = 3 dan Z = 33, Sub-bagian B1 b : X1 = 4, 25, X2 = 4 dan Z = 33, 5. Kedua solusi itu memiliki batas atas ( Z = 33 dan Z = 33, 5 ) yang lebih 21 Universitas Sumatera Utara
buruk dibanding dengan solusi yang dihasilkan oleh bagian A. Karena itu, solusi bulat optimum adalah X1 = 8, X2 = 2 dan Z = 34 yang dihasilkan oleh bagian A. Jika pencarian telah diselesaikan, solusi bulat dengan fungsi tujuan tertinggi (dalam masalah maksimasi) dipilih sebagai solusi optimum. Hasil perhitungan diatas dapat digambarkan pada gambar berikut: Solusi bulat optimum X1 = 8 Inferior X2 = 2 Z = 34 X≤3
X2 ≤ 2
2 0
X2 ≥ 4
X1 ≤ 6
X2 ≥ 3 X1 = 8 X2 = 2, 25 Z = 35, 25 1 X1 = 6, 5 X2 = 35 Z = 34, 5
X1 = 6 X2 = 3, 25 Z = 34, 25
Inferior
X1 ≥ 7 Tak layak
22 Universitas Sumatera Utara
