BAB 2 LANDASAN TEORI
2.1 Program Linier
Program linier adalah suatu cara untuk menyelesaikan persoalan pengalokasian sumber-sumber yang terbatas di antara beberapa aktivitas yang bersaing, dengan cara terbaik yang mungkin dilakukan. Pokok pikiran utama dalam menggunakan program linier adalah merumuskan masalah dengan jelas dengan menggunakan sejumlah informasi yang tersedia. Sesudah masalah terumuskan dengan baik, maka langkah berikut ialah menerjemahkan masalah ke dalam bentuk model matematika (Siagian, 2006). Program linier berkaitan dengan maksimalisasi atau minimalisasi dari fungsi tujuan linier dengan beberapa variabel yang memiliki kesamaan dan ketaksamaan fungsi kendala. Program linier menggunakan model matematis untuk menjelaskan persoalan yang dihadapinya. Sifat “linier” memberi arti bahwa seluruh fungsi matematis dalam model merupakan fungsi yang linier, demikian kata “program” merupakan sinonim untuk perencanaan. Dengan demikian program linier adalah perencanaan aktivitas-aktivitas untuk memperoleh suatu hasil yang optimum, yaitu suatu hasil yang mencapai tujuan terbaik di antara alternatif yang fisibel (Dantzig & Thapa, 1997). Formulasi model matematis dari persoalan pengalokasian sumber-sumber pada permasalahan program linier adalah sebagai berikut (Sitorus, 1997):
maks/min: Z =
kendala: ≤, =, ≥
≥ 0
Universitas Sumatera Utara
di mana:
$ = fungsi tujuan
= koefisien dari variabel keputusan dalam fungsi tujuan = variabel keputusan
= koefisien dari variabel keputusan dalam fungsi kendala = sumber daya yang tersedia dalam fungsi kendala
Dalam kehidupan sehari-hari, program linier merupakan bagian yang sangat penting dalam area matematika yang disebut teknik optimasi. Program linier umumnya diaplikasikan dalam permasalahan yang dapat dimodelkan ke dalam suatu model matematika, misalnya dalam mencari keuntungan suatu usaha, pengoptimalan persediaan, juga dalam beberapa masalah industri maupun ekonomi. Adakalanya dalam situasi tertentu solusi yang diinginkan haruslah dalam bilangan bulat, misalnya pada perusahaan manufaktur, perusahaan tidak bisa memproduksi barang setengah, sepertiga, ataupun seperempat dan sebagainya, jadi masalah ini disebut dengan integer linear programming (Syahputra, 2012).
2.1.1 Syarat Utama Program Linier
Agar dapat menyusun dan merumuskan suatu persoalan atau permasalahan yang dihadapi ke dalam model program linier, maka ada lima syarat yang harus dipenuhi (Sitorus, 1997): 1.
Tujuan Apa yang menjadi tujuan permasalahan yang dihadapi yang ingin dipecahkan dan dicari jalan keluarnya. Tujuan ini harus jelas dan tegas yang disebut fungsi tujuan.
2.
Alternatif Perbandingan Harus ada sesuatu atau berbagai alternatif yang ingin diperbandingkan, misalnya antara kombinasi waktu tercepat dan biaya tertinggi dengan waktu terlambat dan biaya terendah.
3.
Sumber Daya
Universitas Sumatera Utara
Sumber daya yang dianalisis harus berada dalam keadaan yang terbatas. 4.
Perumusan Kuantitatif Fungsi tujuan dan kendala harus dapat dirumuskan secara kuantitatif sesuai dengan yang disebut dalam model matematika.
5.
Keterkaitan Peubah Peubah-peubah yang membentuk fungsi tujuan dan kendala tersebut harus memiliki hubungan fungsional atau hubungan keterkaitan.
2.1.2 Karakteristik Program Linier
Karakteristik-karakteristik dalam program linier yang biasa digunakan untuk memodelkan suatu masalah dan memformulasikannya secara matematik, yaitu (Siswanto, 2006): 1.
Variabel Keputusan Variabel keputusan adalah variabel yang secara lengkap menguraikan keputusan-keputusan yang akan dibuat.
2.
Fungsi Tujuan Fungsi tujuan merupakan suatu hubungan linier dari variabel keputusan yang berupa fungsi maksimum atau minimum.
3.
Fungsi Kendala Fungsi kendala merupakan batasan-batasan dalam penyelesaian program linier yang harus diperhatikan. Kendala diekspresikan dalam persamaan dan pertidaksamaan yang juga merupakan hubungan linier dari variabel keputusan yang mencerminkan keterbatasan sumber daya dalam suatu masalah.
Universitas Sumatera Utara
2.1.3 Asumsi dalam Program Linier
Dalam membangun model dari formulasi suatu persoalan akan digunakan karakteristik-karakteristik yang biasa digunakan dalam persoalan program linier, yaitu (Syahputra, 2012): 1.
Linieritas (Linearity) Fungsi tujuan (objective function) dan kendala – kendalanya (constraints ) dibuat
dalam fungsi linier. Sifat linearitas suatu kasus dapat ditentukan dengan menggunakan beberapa cara, misalnya dengan menggunakan grafik. 2.
Kesetaraan (Propotionality)
a. Kontribusi setiap variabel keputusan terhadap fungsi tujuan adalah sebanding dengan nilai variabel keputusan. b. Kontribusi suatu variabel keputusan terhadap ruas kiri dari setiap pembatas juga sebanding dengan nilai variabel keputusan itu. 3.
Penambahan (Addivity) Sifat penambahan mengasumsikan bahwa tidak terdapat bentuk perkalian silang pada model, baik bagi fungsi tujuan maupun kendala.
4.
Pembagian (Divisibility) Solusi dapat berupa bilangan bulat (integer) atau bilangan pecahan.
5.
Ketidaknegatifan (Nonnegativity) Nilai variabel keputusan harus lebih besar atau sama dengan nol.
6.
Kepastian (Certainty) Koefisien pada fungsi tujuan ataupun fungsi kendala merupakan suatu nilai pasti, bukan merupakan suatu nilai dengan peluang tertentu. Asumsi-asumsi di atas harus dipenuhi apabila ingin menyelesaikan
masalah model program linier. Jika asumsi-asumsi tersebut tidak dapat terpenuhi, persoalan dapat diselesaikan dengan program matematika lain seperti integer programming, nonlinear programming, goal programming dan dynamic programming.
Universitas Sumatera Utara
2.1.4 Metode Simpleks
Cara yang paling sederhana untuk menyelesaikan permasalahan program linier adalah dengan pendekatan grafik. Namun cara tersebut hanya bisa diterapkan untuk program linier dengan dua variabel keputusan. Pada kenyataannya sebagian besar permasalahan program linier mempunyai lebih dari dua variabel keputusan. Hal ini tentu sulit untuk menerapkan pendekatan grafik untuk memperoleh penyelesaian dari permasalahan tersebut. Oleh karen itu, pada tahun 1947 George Dantzig mengajukan suatu metode yang tepat untuk menyelesaiakn permasalahan program linier yang disebut metode simpleks. Metode simpleks merupakan prosedur aljabar yang bersifat iteratif yang bergerak selangkah demi selangkah, dimulai dari titik ekstrim pada daerah feasible menuju titik ekstrim optimum (Siagian, 2006). Berikut langkah-langkah dalam menyelesaikan permasalahan program linier dengan metode simpleks: 1.
Konversikan formulasi persoalan ke dalam bentuk standar. Agar persamaan garis batasan memenuhi persyaratan penyelesaian daerah kelayakan (feasible) maka semua pertidaksamaan diubah menjadi persamaan dengan cara menambahkan slack variable, surplus variable dan variabel buatan (artifisial variabel) pada tiap batasan (constraint) serta memberi harga nol pada setiap koefisien tujuannya. Batasan dapat dimodifikasi sebagai berikut:
a. Untuk batasan bernotasi ≤ diubah ke dalam bentuk persamaan dengan menambahkan variabel slack.
b. Untuk batsan bernotasi ≥ atau = deselesaikan dengan menambahkan variabel surplus dan variabel buatan. Dengan penambahan variabel buatan ini akan merusak sistem batasan, hal ini dapat diatasi dengan membuat suatu bilangan penalty M (M bilangan positif yang sangat besar) sebagai harga dari variabel buatan tersebut dalam fungsi tujuan. Untuk kasus maksimasi maka dibuat –M sebagai harga dari variabel buatan dan untuk
Universitas Sumatera Utara
kasus minimasi dibuat +M sebagai harga dari variabel buatan. Cara pendekatan ini dikenal dengan metode M besar (Big M method). 2.
Susun persamaan-persamaan ke dalam tabel simpleks Tabel 2.1 Bentuk Tabel Simpleks Program Linier
Variabel
Harga
Basis
Basis
,
-
,' ⋮
,
$ − 0
3.
-' ⋮
-
'
...
...
...
...
...
'
,
,'
...
,
Solusi
...
'
...
...
...
...
...
' ''
...
...
...
...
...
'
⋮
⋮
⋮
⋮
⋮
...
...
...
...
...
...
...
...
...
⋮
⋮
...
'
'
...
...
...
⋮
⋮
0-
Pilih kolom kunci, yaitu kolom yang memiliki nilai 1$ − 0 2 yang paling
positif untuk kasus maksimasi atau yang memiliki nilai 1$ − 0 2 yang paling negatif untuk kasus minimasi.
4.
Pilih baris kunci yang memiliki nilai indeks terkecil. Nilai indeks adalah perbandingan nilai kanan dengan kolom kunci,
5.
Tentukan nilai elemen cell, yaitu nilai perpotongan antara kolom kunci dan baris kunci.
6.
Lakukan iterasi dengan menentukan baris kunci baru, baris Z baru dan baris variabel-variabel slack baru. a. Baris kunci baru ditentukan dengan membagi baris kunci lama dengan elemen cell. b. Baris Z baru dan baris-baris lainnya ditentukan dengan cara: Baris lama – (nilai kolom kunci baris yang sesuai × baris kunci baru) c. Letakkan nilai-nilai baris yang baru diperoleh ke dalam tabel.
7.
Lakukan uji optimalisasi. Jika semua koefisien pada baris 1$ − 0 2 sudah tidak ada lagi yang bernilai positif (untuk kasus maksimasi) atau sudah tidak
Universitas Sumatera Utara
ada lagi yang bernilai negatif (untuk kasus minimasi) berarti sudah optiamal. Jika kriteria belum terpenuhi, diulangi dari langkah 3.
2.2 Program Bilangan Bulat
Program bilangan bulat (integer programming) merupakan bentuk perluasan dari program linier. Persoalan program bilangan bulat menginginkan solusi yang didapat berupa bilangan bulat, bukan berupa bilangan pecahan. Contoh persoalan yang sering ditemui misalnya menentukan banyaknya mobil yang harus diproduksi, banyaknya unit rumah yang akan dibangun pada suatu proyek perumahan, banyaknya orang yang diperlukan untuk mengerjakan suatu proyek, dan sebagainya. Program bilangan bulat memiliki model matematis yang sama dengan model program linier pada umumnya, tetapi ditambah batasan bahwa variabelnya harus bilangan bulat sebagai berikut (Syahputra, 2012):
maks/min: Z =
kendala: ≤, =, ≥
di mana:
$ = fungsi tujuan
≥ 0, semua bilangan bulat
= koefisien dari variabel keputusan dalam fungsi tujuan = variabel keputusan
= koefisien dari variabel keputusan dalam fungsi kendala = sumber daya yang tersedia dalam fungsi kendala
Berdasarkan jenis keputusan yang akan diperoleh, persoalan integer programming dapat dibedakan atas tiga jenis, yaitu: 1.
Pemrograman Bilangan Bulat Murni (Pure Integer Programming)
2.
Pemrograman Bilangan Bulat Campuran (Mixed Integer Programming)
3.
Pemrograman Bilangan Bulat Biner (Binary Integer Programming)
Universitas Sumatera Utara
2.2.1 Program Bilangan Bulat Murni (Pure Integer Programming)
Pure Integer Programming (PIP) merupakan pemrograman bilangan bulat di mana semua nilai variabel keputusan haruslah bilangan bulat. Bentuk umum pure integer programming yaitu (Syahputra, 2012):
maks/min: Z =
kendala: ≤, =, ≥
di mana:
≥ 0, semua bilangan bulat
$ = fungsi tujuan
= koefisien dari variabel keputusan dalam fungsi tujuan = variabel keputusan
= koefisien dari variabel keputusan dalam fungsi kendala = sumber daya yang tersedia dalam fungsi kendala
2.2.2 Program Bilangan Bulat Campuran (Mixed Integer Programming)
Mixed Integer Programming (MIP) merupakan pemrograman bilangan bulat di mana nilai variabel keputusannya berupa campuran antara bilangan bulat dan bilangan desimal atau pecahan. Bentuk umum mixed nteger programming yaitu (Syahputra, 2012):
7
5
maks/min: Z = + 45 65
7
kendala: + 85 65 ≤, =, ≥
5
≥ 0, semua bilangan bulat 65 ≥ 0
Universitas Sumatera Utara
di mana:
$ = fungsi tujuan
= koefisien dari variabel keputusan dalam fungsi tujuan = variabel keputusan
= koefisien dari variabel keputusan dalam fungsi kendala = sumber daya yang tersedia dalam fungsi kendala
45 = nilai kontribusi dari variabel keputusan 65
65 = variabel keputusan tidak harus berupa bilangan bulat
85 = koefisien dari variabel keputusan 69 dalam fungsi kendala
2.2.3 Program Bilangan Bulat Biner (Binary Integer Programming)
Bentuk lain dari masalah program bilangan bulat adalah binary integer programming (BIP). Dalam persoalan binary integer programming nilai variabel keputusannya berupa bilangan biner (0 atau 1). Dalam aplikasi sehari-hari, masalah binary integer programming menyangkut masalah pengambilan keputusan, di mana jika solusi yang didapat berupa angka 1 berarti menyatakan “ya” atau angka 0 berarti menyatakan “tidak”. Bentuk umum dari binary integer programming, yaitu (Syahputra, 2012):
maks/min: Z =
kendala: ≤, =, ≥
di mana:
$ = fungsi tujuan
= 0 :; 1
= koefisien dari variabel keputusan dalam fungsi tujuan = variabel keputusan
= koefisien dari variabel keputusan dalam fungsi kendala = sumber daya yang tersedia dalam fungsi kendala
Universitas Sumatera Utara
2.3 Metode Penyelesaian Masalah Program Bilangan Bulat
Dapat kita lihat bahwasanya cukup untuk mendapatkan solusi bulat dari masalah program linier dengan menggunakan metode simpleks biasa dan kemudian membulatkan nilai pecahan pada solusi optimum. Akan tetapi bukan tugas mudah untuk membulatkan nilai pecahan dalam variabel basis yang menjamin tetap memenuhi semua kendala dan tidak menyimpang cukup jauh dari solusi bulat yang tepat. Akibatnya diperlukan prosedur yang sistematis untuk mendapatkan solusi optimum yang berupa bilangan bulat terhadap suatu masalah. Beberapa metode yang dapat digunakan untuk menyelesaikan masalah program bilangan bulat antara lain (Syahputra, 2012): 1.
Metode Pendekatan Grafik
2.
Metode Cutting Plane
3.
Metode Branch and Bound
2.3.1 Metode Pendekatan Grafik
Masalah program bilangan bulat yang melibatkan dua variabel dapat diselesaikan dengan metode pendekatan grafik. Metode ini sama dengan metode grafik yang biasa digunakan dalam program linier. Metode grafik relatif lebih mudah untuk menyelesaikan masalah program bilangan bulat dengan dua variabel yaitu dengan menggambar grafik di atas kertas grafik kemudian menggambarkan sekumpulan titik-titik bilangan bulat dalam ruang solusi layak (Syahputra, 2012). Dalam hal ini ada masalah berikut yang akan diselesaikan dengan pendekatan grafik sebagai berikut: contoh 2.1:
carilah nilai bilangan bulat dan ' dari ketentuan berikut (Wolff, 1985): maks: kendala:
$ = 3 + 20'
+ 8' ≤ 32
2 + ' ≤ 14
, ' ≥ 0 adalah bilangan bulat
Universitas Sumatera Utara
Model ini serupa dengan model program linier biasa. Perbedaannya terletak pada kendala terakhir yang menginginkan solusi bernilai bilangan bulat positif, solusi grafik untuk masalah ini ditunjukkan pada gambar di bawah:
Gambar 2.1 Penyelesaian dengan Pendekatan Grafik Solusi optimum masalah program linier di atas adalah = 5,3333,
' = 3,3333 dan $ = 82,6666. Untuk mencari solusi optimum yang bernilai bilangan bulat pada masalah ini, garis Z digeser secara sejajar dari titik yang menunjukkan solusi optimum menuju titik asal. Solusi optimum berupa bilangan bulat adalah titik bilangan bulat pertama yang bersinggungan dengan garis Z yaitu = 0, ' = 4 dan $ = 80.
2.3.2 Metode Cutting Plane
Metode cutting plane merupakan metode yang digunakan untuk menyelesaikan program linier bilangan bulat, baik bilangan bulat murni maupun campuran dengan penambahan batasan baru yang disebut gomory. Batasan gomory diberikan jika nilai dari variabel keputusan belum bulat (bernilai pecahan). Batasan-batasan tersebut secara efektif akan menyingkirkan beberapa ruang penyelesaian yang tidak berisi titik bilangan bulat yang layak, tetapi tidak pernah menyingkirkan satupun titik bilangan bulat yang layak (Taha, 1996).
Universitas Sumatera Utara
Metode cutting plane dikembangkan untuk menemukan solusi optimum bagi program bilangan bulat. Metode ini dilakukan dengan menambahkan suatu kendala yang dinamakan kendala gomory. Penambahan kendala gomory dilakukan pada tabel optimal sehingga dapat mempersingkat perhitungan (Siagian, 2006). Metode cutting plane digunakan untuk permasalahan yang variabel keputusannya harus bulat. Program linier tidak efektif untuk menyelesaikan permasalahan tersebut sehingga dikembangkan metode cutting plane yang lebih efektif dan memberikan hasil yang lebih baik. Langkah-langkah prosedur gomory diringkas seperti berikut: 1.
Selesaikan masalah program bilangan bulat dengan menggunakan metode simpleks. Jika masalah sederhana, gomory dapat diselesaikan dengan pendekatan grafik, sehingga pendekatan gomory kurang efisien.
2.
Periksa solusi optimum. Jika semua variabel basis memiliki nilai bilangan bulat, solusi optimum yang berupa bilangan bulat telah diperoleh dan proses solusi telah berakhir. Jika satu atau lebih variabel basis masih memiliki nilai pecah, teruskan ke tahap 3.
3.
Buatlah suatu batasan gomory dan cari solusi optimum melalui prosedur dual simpleks. Kembali ke tahap 2 (Taha, 1996). Tabel 2.2 Solusi Optimum Masalah Program Linier
Variabel
Harga
Basis
Basis
,
-
,'
-'
⋮
,
⋮
$ − 0
-
'
...
...
...
...
...
'
,
,'
...
,
Solusi
...
'
...
...
...
...
...
' ''
...
...
...
...
...
'
⋮
⋮
⋮
⋮
⋮
...
...
...
...
...
...
...
...
⋮
...
⋮
...
'
'
...
...
...
⋮
⋮
0-
di mana: = variabel basis
, = variabel nonbasis
Universitas Sumatera Utara
Perhatikan persamaan ke A di mana variabel diasumsikan bernilai tidak bilangan bulat sebagai berikut:
= − ,
di mana: = variabel basis
, = variabel nonbasis
= koefisien dari variabel keputusan dalam fungsi kendala yang berupa noninteger
= sumber daya yang tersedia dalam fungsi kendala yang berupa noninteger
kemudian pisahkan dan menjadi bagian yang bulat dan bagian pecah non negatif seperti berikut: = CB + %
sehingga % = − CB ,
di mana 0 ≤ % ≤ 1
sehingga % = − EEEE DB ,
di mana 0 ≤ % ≤ 1
= EEEE DB + %
dapat kita lihat contoh berikut: CB
3 2 7 8 7 3
1 0 2
% 1 2 7 8 1 3
DB EEEE
%
−1
−1
0
−
−1
−
7 3 2 5
−3
sehingga adapun kendala gomory yang diinginkan sebagai berikut:
2 3 3 5
,G − % , = −%
di mana:
,G = slack gomory variable
% = bagian pecahan dari
% = bagian pecahan dari , = variabel nonbasis
Universitas Sumatera Utara
Pada umumnya, persamaan kendala yang berhubungan dengan solusi pecah dipilih untuk menghasilkan suatu kendala gomory. Namun, sebagai aturan
main biasanya dipilih persamaan yang memiliki % maksimum. Adapun tabel baru setelah penambahan kendala gomory disajikan pada tabel berikut: Tabel 2.3 Penambahan Kendala Gomory
'
...
...
...
...
...
...
'
...
,
,'
...
,
,8
'
...
...
...
...
...
0
...
...
...
...
...
⋮
⋮
⋮
⋮
⋮
...
...
...
...
Variabel
Harga
Basis
Basis
,
-
,'
-'
⋮
⋮
,
,8
A
-
0
$ − 0
' '' ⋮
⋮
' ...
0
0
… 0
...
...
...
...
−% −%' ...
...
...
...
' ⋮
A
0 0
0
...
...
−% 1
Solusi
' ⋮
−% 0-
Karena diperoleh solusi primal optimum tetapi tidak layak maka digunakan metode dual simpleks. Proses pembentukan kendala gomory berakhir jika solusi baru semua berupa bilangan bulat. Jika tidak, suatu kendala gomory baru dibuat lagi dari tabel yang dihasilkan dan metode dual simpleks digunakan lagi untuk mengatasi ketidaklayakan. Jika pada setiap iterasi metode dual simpleks menunjukkan bahwa tidak ada solusi layak, berarti masalah itu tidak memiliki solusi integer yang layak. Metode cutting plane ini mempunyai dua kelemahan sebagai berikut: 1.
Kesalahan pembulatan yang muncul dalam perhitungan otomatis akan mendistorsi data semula terutama dengan bertambahnya ukuran masalah.
2.
Solusi masalah tetap tidak layak, artinya tidak ada solusi integer yang dapat diperoleh sampai solusi integer optimal dicapai. Ini berarti bahwa tidak ada solusi integer yang baik jika perhitungan dihentikan sebelum mencapai solusi integer yang optimal (Taha, 1996). Kelemahan pertama dapat diatasi dengan penggunaan integer murni.
Metode ini dimulai dengan tabel awal yang semuanya terdiri dari integer yang
Universitas Sumatera Utara
sesuai dengan metode dual simpleks. Kemudian dilakukan penambahan gomory sehingga penambahannya ke tabel akan mempertahankan sifat integer dari semua koefisien. Dan kelemahan kedua dapat menggunakan metode cutting plane yang dimulai dengan integer dan layak, tetapi tidak optimal. Iterasi yang berlanjut tetap layak dan integer sampai solusi optimum dicapai (Taha, 1996). Dalam hal ini ada masalah diselesaikan dengan metode cutting plane sebagai berikut: contoh 2.2:
carilah nilai bilangan bulat dan ' dari ketentuan berikut (Syahputra,2012): $ = 7 + 9'
maks:
− + 3' ≤ 6
kendala:
7 + ' ≤ 35
, ' ≥ 0 adalah bilangan bulat
dari permasalahan di atas maka diperoleh solusi optimumnya sebagai berikut berikut: Tabel 2.4 Solusi Optimum Contoh 2.2
7
9
0
0
Harga Basis
'
'
,
,'
Solusi
Variabel Basis
9
0
1
0,3282
0,0455
3,5000
7
1
0
-0,0455
0,1364
4,5000
0
0
2,5455
1,3636
63
$ − 0
sehingga dapat diperoleh solusi optimum sebagai berikut: = 4,5000, ' = 3,5000 dan $ = 63
karena solusi tidak diperoleh bilangan bulat, suatu kendala gomory ditambahkan
pada tabel tersebut. Kedua persamaan ( dan ' ) pada masalah ini memiliki nilai
% yang sama yaitu % = %' = 0,5000, sehingga salah satu dapat digunakan,
misalkan yang digunakan persamaan ' , maka dapat diperoleh sebagai berikut: ' + 0,3282, + 0,0455,' = 3,5000
kemudian kita pisahkan koefisien yang bernilai pecahan menjadi 2 bagian yaitu yang bernilai bilangan bulat dan bilangan pecahan
' + 0 + 0,3282 , + 0 + 0,0455 ,' = 3 + 0,5000
Universitas Sumatera Utara
sehingga kendala gomory menjadi
,8 − 0,3282, − 0,0455,' = −0,5000 1
sehingga dapat dibentuk tabel baru setelah penambahan kendala gomory sebagai berikut: Tabel 2.5 Penambahan Kendala Gomory Pertama
7
9
0
0
0
'
,
,'
,8
Solusi
Variabel
Harga
Basis
Basis
'
9
0
1
0,3282
0,0455
0
3,5000
7
1
0
-0,0455
0,1364
0
4,5000
0
0
0
-0,3282
-0,0455
1
-0,5000
0
0
2,5455
1,3636
0
63
,8
1
$ − 0
1
kemudian permasalahan di atas setelah penambahan kendala gomory diselesaikan dengan memakai metode dual simpleks, maka diperoleh hasilnya sebagai berikut: Tabel 2.6 Solusi Optimum dengan Penambahan Kendala Gomory Pertama
7
9
0
0
0
'
,
,'
,8
Solusi
Variabel
Harga
Basis
Basis
'
9
0
1
0
0
1
3
7
1
0
0
0,1428
-0,1428
4,5714
0
0
0
1
0,1428
3,1428
1,5714
0
0
0
1
8
59
,8
1
$ − 0
1
sehingga dapat diperoleh solusi optimum sebagai berikut: = 4,5714, ' = 1,5714 dan $ = 55
karena solusi tidak diperoleh bilangan bulat, suatu kendala gomory ditambahkan kembali pada tabel tersebut. Dapat dilihat bahwa persamaan memiliki % = 0,5714, sehingga persamaan dapat diperoleh sebagai berikut:
+ 0,1428,' − 0,1428,G = 4,5714
kemudian kita pisahkan koefisien yang bernilai pecahan menjadi 2 bagian yaitu yang bernilai bilangan bulat dan bilangan pecahan
Universitas Sumatera Utara
+ 0 + 0,1428 ,' − 0 + 0,1428 ,G = 4 + 0,5714 sehingga kendala gomory menjadi
,8 − 0,1428,' − 0,1428,8 = −0,5714 2
1
sehingga dapat dibentuk tabel baru setelah penambahan kendala gomory yang baru sebagai berikut: Tabel 2.7 Penambahan kendala Gomory Kedua 0
7
9
0
0
0
0
'
,
,'
,8
,8
Solusi
Variabel
Harga
Basis
Basis
'
9
0
1
0
0
1
0
3
7
1
0
0
0,1428
-0,1428
0
4,5714
1
0
0
0
1
0,1428
3,1428
0
1,5714
2
0
0
0
0
-0,1428
-0,1428
1
-0,5714
0
0
0
1
8
0
59
I8 I8
$ − 0
1
2
kemudian permasalahan di atas setelah penambahan kendala gomory yang baru diselesaikan dengan memakai metode dual simpleks, maka diperoleh hasilnya
sebagai berikut: Tabel 2.8 Solusi Optimum dengan Penambahan Kendala Gomory Kedua
7
9
0
0
0
0
'
,
,'
,8
,8
Solusi
Variabel
Harga
Basis
Basis
'
9
0
1
0
0
1
0
3
7
1
0
0
0
-1
1
4
1
0
0
0
1
0
-4
1
1
2
0
0
0
0
1
6
-7
4
0
0
0
0
2
7
55
,8 ,8
$ − 0
1
2
sehingga dapat diperoleh solusi optimum dengan bilangan bulat sebagai berikut: = 4, ' = 3 dan $ = 55
Universitas Sumatera Utara
2.3.3 Metode Branch and Bound
Metode branch and bound adalah salah satu metode untuk mendapatkan penyelesaian optimal pada program linier yang menghasilkan variable-variabel keputusan bilangan bulat. Metode ini membatasi penyelesaian optimum yang akan menghasilkan bilangan pecahan dengan cara membuat cabang atas dan bawah bagi masing-masing variabel keputusan yang bernilai pecahan agar bernilai bulat sehingga setiap pembatasan akan menghasilkan cabang baru. Metode branch and bound telah menjadi kode komputer standar untuk program bilangan bulat dan penerapan-penerapan dalam praktek tampaknya menyarankan bahwa metode ini lebih efisien dibanding dengan metode cutting plane. Metode branch and bound dapat digunakan untuk menyelesaikan masalah pure maupun mixed integer programming (Syahputra, 2012). Adapun langkah-langkah penyelesaian masalah maksimasi dengan metode branch and bound sebagai berikut (Syahputra, 2012): 1.
Selesaikan masalah program linier biasa tanpa pembatasan bilangan bulat dengan metode simpleks biasa.
2.
Teliti solusi optimumnya. Jika semua variabel basis telah bernilai bulat, maka solusi optimum telah tercapai dan proses berakhir. Jika satu atau lebih variabel basis belum bernilai bulat, lanjut ke tahap 3.
3.
Jadikan solusi pada penyelesaian tahap 1 (relaxed solution) menjadi batas atas dan sebagai batas bawahnya digunakan solusi yang variabel basisnya telah dibulatkan ke bawah (rounded down).
4.
Pilih variabel yang mempunyai nilai pecahan yang terbesar untuk dijadikan pencabangan ke dalam sub-sub masalah. Tujuannya adalah untuk menghilangkan solusi kontinu yang tidak memenuhi persyaratan bulat dalam masalah itu. Pencabangan dilakukan secara mutually exclusive untuk memenuhi persyaratan bulat dengan jaminan tidak ada solusi bulat layak yang tidak diikut sertakan.
5.
Untuk setiap sub masalah, nilai solusi optimum kontinu fungsi tujuan ditetapkan sebagai batas atas. Solusi bulat terbaik menjadi batas bawah (pada
Universitas Sumatera Utara
awalnya, ini adalah solusi kontinu 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 adalah 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 ke langkah 4. Untuk masalah minimasi, solusi yang menjadi batas atas dibulatkan keatas, atau dengan kata lain batas atas dan bawah pada kasus minimasi berlawanan pada kasus maksimasi (Syahputa, 2012). Dalam hal ini ada masalah berikut yang akan diselesaikan dengan metode branch and bound sebagai berikut: contoh 2.3:
carilah nilai bilangan bulat dan ' dari ketentuan berikut (Wolfe,1985): $ = 5 + 2'
maks:
6 + 10' ≤ 69
kendala:
3 + 10' ≤ 60
6 − 15' ≤ 24
, ' ≥ 0 adalah bilangan bulat
dari permasalahan tersebut maka diperoleh solusi optimumnya sebagai berikut berikut: Tabel 2.9 Solusi Optimum Contoh 2.3
5
2
0
0
0
Variabel
Harga
Basis
Basis
'
,
,'
,J
Solusi
'
2
0
1
0,0400
0
-0,0400
1,8000
0
0
0
-0,7000
1
0,2000
16,500
5
1
0
0,1000
0
0,0667
8,5000
0
0
0,5800
0
0,2533
46,100
,'
$ − 0
sehingga dapat diperoleh solusi optimum sebagai berikut: = 8,5000, ' = 1,8000 dan $ = 46,100
Universitas Sumatera Utara
dan solusi tersebut belum diperoleh bilangan bulat maka diterapkan metode
branch and bound, kita ketahui bahwa dan ' belum berupa bilangan bulat, maka kita pilih variabel yang solusinya bernilai pecahan terbesar untuk dicabangkan, yang dalam hal ini merupakan nilai pecahan terbesar, jadi
yang dicabangkan. Untuk menghilangkan bagian pecahan pada , dua kendala baru dibuat. Nilai bulat terdekat terhadap 8,5000 yaitu 8 dan 9. Sehingga
diperoleh dua kendala baru yang saling mutually exclusive, yaitu ≤ 8 dan ≥ 9, kendala-kendala baru tersebut secara efektif akan menghilangkan semua
nilai pecah yang mungkin ada pada . Kemudian akan diuraikan permasalahan tersebut kedalam bagian A dan bagian B sebagai berikut: Bagian A: maks: kendala:
$ = 5 + 2'
6 + 10' ≤ 69
3 + 10' ≤ 60
6 − 15' ≤ 24 1 + 0' ≤ 8 , ' ≥ 0
Bagian B: maks: kendala:
$ = 5 + 2'
6 + 10' ≤ 69
3 + 10' ≤ 60 6 − 15' ≤ 24
1 + 0' ≥ 9
, ' ≥ 0
kemudian bagian A dan bagian B diselesaikan dengan metode simpleks tanpa pembatasan bilangan bulat, adapun solusi optimumnya sebagai berikut:
Universitas Sumatera Utara
Tabel 2.10 Solusi Optimum pada Bagian A
5
2
0
0
0
0
'
,
,'
,J
,K
Solusi
Variabel
Harga
Basis
Basis
,J
0
0
0
1,5000
0
1
-15
7,5000
0
0
0
-1,0000
1
1
3,0000
15
5
1
0
0
0
0
1
8
2
0
1
0,1000
0
0
-0,6000
2,1000
0
0
-0,2000
0
0,2533
3,8000
44,200
,'
'
$ − 0
sehingga dapat diperoleh solusi optimum sebagai berikut: = 8, ' = 2,1000 dan $ = 44,200
dan pada bagian B tidak diperoleh solusi yang layak. Dari solusi pada bagian A belum diperoleh bilangan bulat maka diterapkan metode branch and bound, kita
ketahui bahwa ' belum berupa bilangan bulat maka ' yang dicabangkan. Untuk menghilangkan bagian pecahan pada ' , dua kendala baru dibuat. Nilai bulat
terdekat terhadap 2,1000 yaitu 2 dan 3. Sehingga diperoleh dua kendala baru
yang saling mutually exclusive, yaitu ' ≤ 2 dan ' ≥ 3, kendala-kendala baru
tersebut secara efektif akan menghilangkan semua nilai pecah yang mungkin ada pada ' . Kemudian akan diuraikan permasalahan bagian A kedalam bagian C dan
bagian D sebagai berikut: Bagian C: maks: kendala:
$ = 5 + 2'
6 + 10' ≤ 69
3 + 10' ≤ 60
6 − 15' ≤ 24 1 + 0' ≤ 8 0 + 1' ≤ 2 , ' ≥ 0
Universitas Sumatera Utara
Bagian D:
$ = 5 + 2'
maks:
6 + 10' ≤ 69
kendala:
3 + 10' ≤ 60
6 − 15' ≤ 24 1 + 0' ≤ 8 0 + 1' ≥ 3 , ' ≥ 0
kemudian bagian C dan bagian D diselesaikan dengan metode simpleks tanpa pembatasan bilangan bulat, adapun solusi optimumnya sebagai berikut: Tabel 2.11 Solusi Optimum pada Bagian C
5
2
0
0
0
0
0
'
,
,'
,J
,K
,L
Solusi
Variabel
Harga
Basis
Basis
,
0
0
0
1
0
0
-6
-10
1
0
0
0
0
1
0
-3
-10
16
5
1
0
0
0
0
1
0
8
2
0
1
0
0
0
0
1
2
0
0
0
0
0
1
6
15
6
0
0
0
0
0
5
2
44
,'
' ,J
$ − 0
sehingga dapat diperoleh solusi optimum sebagai berikut: = 8, ' = 2 dan $ = 44
dan terlihat bahwa solusi optimum pada bagian C sudah semua merupakan bilanagan bulat.
Universitas Sumatera Utara
Tabel 2.12 Solusi Optimum pada Bagian D
5
2
0
0
0
0
0
'
,
,'
,J
,K
,L
Solusi
Variabel
Harga
Basis
Basis
5
0
0
0,1667
0
0
0
1,1667
6,5000
0
0
0
-0,5000
1
0
0
5
10,500
0
1
0
-1
0
1
0
-25
30
0
0
1
-0,1667
0
0
1
-1,1667
1,5000
2
0
0
0
0
0
0
-1
3
0
0
0,8333
0
0
0
6,3333
38,500
,' ,J ,J
'
$ − 0
sehingga dapat diperoleh solusi optimum sebagai berikut: = 6,5000, ' = 3 dan $ = 38,5000
dan terlihat bahwa solusi optimum pada bagian D belum semua merupakan bilangan bulat. Dari solusi pada bagian belum diperoleh bilangan bulat maka
diterapkan metode branch and bound, kita ketahui bahwa belum berupa bilangan bulat maka yang dicabangkan. Untuk menghilangkan bagian pecahan
pada , dua kendala baru dibuat. Nilai bulat terdekat terhadap 6,5000 yaitu 6 dan 7. Sehingga diperoleh dua kendala baru yang saling mutually exclusive, yaitu
' ≤ 6 dan ' ≥ 7, kendala-kendala baru tersebut secara efektif akan
menghilangkan semua nilai pecah yang mungkin ada pada . Kemudian akan diuraikan permasalahan bagian D kedalam bagian E dan bagian F sebagai berikut: Bagian E: maks: kendala:
$ = 5 + 2'
6 + 10' ≤ 69
3 + 10' ≤ 60
6 − 15' ≤ 24 1 + 0' ≤ 8 0 + 1' ≤ 2 1 + 0' ≤ 6 , ' ≥ 0
Universitas Sumatera Utara
Bagian F: maks:
$ = 5 + 2'
6 + 10' ≤ 69
kendala:
3 + 10' ≤ 60
6 − 15' ≤ 24 1 + 0' ≤ 8 0 + 1' ≤ 2 1 + 0' ≥ 7 , ' ≥ 0
kemudian bagian E dan bagian F diselesaikan dengan metode simpleks tanpa pembatasan bilangan bulat, adapun solusi optimumnya sebagai berikut: Tabel 2.13 Solusi Optimum pada Bagian E
2
0
0
0
0
'
,
,' ,J ,K ,L ,M
,N
Solusi
5
0
0
0
Variabel
Harga
Basis
Basis
,L
0
0
0
0,1000
0
0
0
-1
1
-0,6000
0,3000
0
0
0
-1
1
0
0
0
0
3
9
0
0
0
1,5000
0
1
0
0
0
-1,5000
37,5000
0
0
0
0
0
0
1
0
0
-1
2
5
0
1
0,1000
0
0
0
0
0
-0,6000
3,3000
2
1
0
0
0
0
0
0
0
1
6
0
0
0,200
0
0
5
0
0
3
36,600
,' ,J ,K
'
$ − 0
sehingga dapat diperoleh solusi optimum sebagai berikut: = 6, ' = 3,3000 dan $ = 36,6000
dan terlihat bahwa solusi optimum pada bagian E belum semua merupakan bilangan bulat, kemudian pada bagian F tidak diperoleh solusi yang layak. Jadi dari solusi pada bagian E belum diperoleh bilangan bulat maka diterapkan metode branch and bound, kita ketahui bahwa ' belum berupa bilangan bulat maka
' yang dicabangkan. Untuk menghilangkan bagian pecahan pada ' , dua kendala
Universitas Sumatera Utara
baru dibuat. Nilai bulat terdekat terhadap 3,3000 yaitu 3 dan 4. Sehingga
diperoleh dua kendala baru yang saling mutually exclusive, yaitu ' ≤ 3 dan ' ≥ 4, kendala-kendala baru tersebut secara efektif akan menghilangkan semua
nilai pecah yang mungkin ada pada ' . Kemudian akan diuraikan permasalahan bagian E kedalam bagian G dan bagian H sebagai berikut: Bagian G: maks: kendala:
$ = 5 + 2'
6 + 10' ≤ 69
3 + 10' ≤ 60
6 − 15' ≤ 24 1 + 0' ≤ 8 0 + 1' ≤ 2 1 + 0' ≤ 6 0 + 1' ≤ 3 , ' ≥ 0
Bagian H: Maks: kendala:
$ = 5 + 2'
6 + 10' ≤ 69
3 + 10' ≤ 60
6 − 15' ≤ 24 1 + 0' ≤ 8 0 + 1' ≤ 2 1 + 0' ≤ 6 0 + 1' ≥ 4 , ' ≥ 0
Universitas Sumatera Utara
bagian G dan bagian H diselesaikan dengan metode simpleks tanpa pembatasan bilangan bulat, adapun solusi optimumnya sebagai berikut: Tabel 2.14 Solusi Optimum pada Bagian G
5
2
0
0
0
0
0
0
0
0
' , ,'
,J
,K
,L
,M
,N
,O
Solusi
Variabel
Harga
Basis
Basis
,
0
0
0
1
0
0
0
0
0
-6
-10
3
0
0
0
0
1
0
0
0
0
-3
-10
12
0
0
0
0
0
1
0
0
0
-6
15
33
0
0
0
0
0
0
1
0
0
-1
0
2
5
0
1
0
0
0
0
0
0
0
1
3
2
1
0
0
0
0
0
0
0
1
0
6
0
0
0
0
0
0
-1
1
0
1
0
0
0
0
0
0
0
0
5
2
36
,' ,J ,K
' ,M
$ − 0
0
sehingga dapat diperoleh solusi optimum sebagai berikut:
= 6, ' = 3 dan $ = 36. Dan terlihat bahwa solusi optimum pada bagian G sudah semua merupakan bilanagan bulat.
Universitas Sumatera Utara
Tabel 2.15 Solusi Optimum pada Bagian H
Variabel Basis ,' ,J ,K
' ,M ,L
$ − 0
5
2
0
0
0
0
0
0
0
0
0
'
,
,'
,J
,K
,L
,M
,N
,O
,P
Solusi
Basis
5
1
0
0,1667
0
0
0
0
0
0
-1,6667
1,6667
4,8333
0
0
0
-0,5000
1
0
0
0
0
0
-5
5
5,5000
0
0
0
-1
0
1
0
0
0
0
25
-25
55
0
0
0
-0,1667
0
0
1
0
0
0
1,6667
-1,6667
3,1667
2
0
1
0
0
0
0
0
0
0
1
-1
4
0
0
0
-0,1667
0
0
0
0
0
1
1,6667
-1,6667
1,1667
0
0
0
0
0
0
-1
1
0
1
-1
1
0
0
0,8333
0
0
0
0
0
-6,3333
6,3333
36,1670
Harga
0
sehingga dapat diperoleh solusi optimum sebagai berikut:
= 4,8333, ' = 4 dan $ = 32,1670 terlihat bahwa solusi optimum pada bagian H belum semua merupakan bilanagan bulat, kita ketahui bahwa solusi optimum pada bagian G dan bagian H memiliki nilai fungsi tujuan yang lebih rendah (buruk) dibandingkan solusi yang dihasilkan pada bagian E, maka proses pencabangan dihentikan. Sehingga solusi optimum yang menghasilkan berupa bilangan bulat terletak pada bagian C dengan = 8, ' = 2 dan $ = 44 .
Universitas Sumatera Utara
36 Solusi Awal
= 8,5000
' = 1,8000
≤ 8
$ = 46,1000
≥ 9
A
B
= 8
TIDAK
' = 2,1000
' ≤ 2
$ = 44,2000
C
LAYAK J ≥ 3
D
= 8
= 6,5000
$ = 44
$ = 38,5000
' = 3
' = 2
≥ 7
≤ 6
E
F
= 6
TIDAK
' = 3,3000
' ≤ 3
G = 3
' = 6
$ = 36,60000
LAYAK ' ≥ 4
H
INFERIOR
$ = 36
Gambar 2.2. Diagram Prosedur Permasalahan dengan Metode Branch and Bound
Universitas Sumatera Utara
