Bab 2 LANDASAN TEORI
2.1 Linear Programming
Linear Programming (LP) merupakan metode yang digunakan untuk mencapai hasil terbaik (optimal) seperti keuntungan maksimum atau biaya minimum dalam model matematika yang melibatkan variable-variabel linear. Linear programming juga dapat dikatakan sebagai teknik untuk mengoptimasi sebuah fungsi objective linear, dengan kendala berbentuk persamaan linear maupun pertidaksamaan linear. Secara umum, linear programming dapat dinyatakan sebagai: Optimalkan komponen dan
,
∈
⊆
dengan
adalah himpunan semua vektor real
merupakan fungsi objektif yang didefinisikan dalam
juga disebut sebagai himpunan kendala. Setiap (feasible solution), sedangkan
∈
∈
atau
disebut sebagai solusi layak
yang memenuhi
∞, ∀ ∈
disebut sebagai solusi optimal (optimal solution). Dalam kehidupan sehari-hari, linear programming merupakan bagian yang sangat penting dalam area matematika yang disebut teknik optimasi. Linear programming
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 jadi. Masalah ini disebut dengan integer linear programming (ILP).
2.1.1 Karakteristik Linear Programming Karakteristik-karakteristik dalam linear programming yang biasa digunakan untuk memodelkan suatu masalah dan memformulasikannya secara matematik yaitu:
a. Variabel Keputusan
Variabel keputusan adalah variabel yang secara lengkap menguraikan keputusan-keputusan yang akan dibuat.
b. Fungsi Tujuan
Fungsi tujuan merupakan suatu hubungan linier dari variabel keputusan yang berupa fungsi maksimum atau minimum.
c. Kendala
Kendala
merupakan
batasan-batasan
dalam
penyelesaian
linear
programming yang harus diperhatikan. Kendala diekspresikan dalam persamaan dan pertidaksamaan yang juga merupakan hubungan linier dari variabel keputusan yang mencerminkan keterbatasan sumberdaya dalam suatu masalah.
2.1.2 Asumsi dalam Linear Programming Model linear programming mengandung asumsi-asumsi implisit tertentu yang harus dipenuhi. Asumsi-asumsi tersebut yaitu:
a. 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 atau menggunakan uji hipotesa. b. Kesetaraan (Proportionality)
i.
Kontribusi setiap variabel keputusan terhadap fungsi tujuan adalah sebanding dengan nilai variabel keputusan.
ii.
Kontribusi suatu variabel keputusan terhadap ruas kiri dari setiap pembatas juga sebanding dengan nilai variabel keputusan itu.
c. Penambahan (Addivity) Sifat penambahan mengasumsikan bahwa tidak terdapat bentuk perkalian silang pada model, baik bagi fungsi tujuan maupun kendala.
d. Pembagian (Divisibility) Solusi dapat berupa bilangan bulat (integer) atau bilangan pecahan.
e. Ketidaknegatifan (Nonnegativity) Nilai variabel keputusan harus lebih besar atau sama dengan nol.
f. 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 linear programming. Jika asumsi-asumsi tersebut tidak dapat terpenuhi, persoalan dapt diselesaikan dengan program matematik lain seperti; integer programming, nonlinear programming, goal programming, atau dynamic programming.
2.2 Integer Programming (IP) Program bilangan bulat (integer programming) merupakan bentuk perluasan dari linear programming. Persoalan IP menginginkan solusi yang didapat berupa bilangan bulat, bukan berupa bilangan pecahan. Contoh persoalan yang sering ditemui misalnya menentukan banyaknya barang elektronik yang harus diproduksi, banyaknya unit rumah yang akan dibangun pada suatu proyek perumahan, banyaknya orang yang diperlukan untuk mengerjakan suatu proyek, dan sebagainya. Integer programming memiliki model matematis yang sama dengan model linear programming pada umumnya, tetapi ditambah batasan bahwa variabelnya harus bilangan bulat. 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)
2.2.1 Pemrograman Bilangan Bulat Murni (Pure Integer Programming) Pure Integer Programming (PIR) merupakan pemrograman bilangan bulat di mana semua nilai variabel keputusan haruslah bilangan bulat. Bentuk umum pure integer programming yaitu: Optimalkan
:
Kendala
:
∑ ∑
, ,
1, 2, … , 1, 2, … , 0,
2.2.2 Pemrograman Bilangan Bulat Campuran (Mixed Integer Programming) Mixed Integer Programming (PIR) 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:
Optimalkan
:
Kendala
:
∑ ∑
∑
∑
, ,
1, 2, … , 1, 2, … , 1, 2, … , 0, 0
2.2.3 Pemrograman Bilangan Bulat Biner (Binary Integer Programming) Bentuk lain dari masalah integer programming 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 yang menyatakan “ya” atau angka 0 yang menyatakan “tidak”.
Bentuk umum dari binary integer programming yaitu: Optimalkan
:
Kendala
:
∑ ∑
, , 1, 2, … , 1, 2, … , 0 atau 1
2.3 Metode Penyelesaian Masalah Integer Programming Tampaknya cukup untuk mendapatkan solusi bulat dari masalah linear programming, dengan menggunakan metode simpleks biasa dan kemudian membulatkan nilai-nilai pecah solusi optimum. Bukan tugas mudah untuk membulatkan nilai-nilai pecah 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 bulat optimum terhadap masalah itu. Beberapa metode yang dapat digunakan untuk menyelesaikan masalah integer programming antara lain: 1. Metode Pendekatan Pembulatan 2. Metode Pendekatan Grafik 3. Metode Branch and Bound 4. Metode Cutting Plane
2.3.1 Metode Pendekatan Pembulatan Suatu pendekatan yang sederhana dalam menyelesaikan masalah integer programming adalah dengan membulatkan nilai variabel keputusan yang telah diperoleh pada penyelesaian linear programming. Pendekatan ini mudah dan praktis dalam usaha, waktu, dan biaya yang diperlukan untuk memperoleh solusi. Pendekatan pembulatan merupakan cara yang sering digunakan untuk masalah integer programming apabila biaya perhitungan sangat tinggi atau untuk masalah yang memiliki nilai-nilai solusi variabel keputusan relatif besar.
Namun demikian sebab utama kegagalan pendekatan ini adalah bahwa solusi yang diperoleh mungkin bukan solusi integer optimum yang sesungguhnya. Dengan kata lain, solusi pembulatab dapat lebih jelek dibandingkan solusi integer optimum yang sesungguhnya atau mungkin merupakan solusi tak layak. Tiga masalah berikut disajikan untuk mengilustrasikan prosedur pembulatan:
Contoh 2.1: Masalah 1: Maksimumkan Kendala
100
90
10
7
70
5
10
50
0
Masalah 2: Minimumkan Kendala
200
400
10
25
100
3
2
12
0
Masalah 3: Maksimumkan Kendala
80
100
4
2
12
5
15
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:
Tabel 2.1 Perbandingan solusi dengan metode pendekatan pembulatan dengan bulat optimum sesungguhnya.
Masalah
Solusi dengan Metode simpleks
1 2
Dengan
Solusi integer
pembulatan
optimum
terdekat
sesungguhnya
5,38
5
7
2,31
2
0
746,15
680
700
1,82
2
3,
5
3,27
3
5,
2
1.672,73 3
1.800
2,14
2
0
1,71
2
3
343
300
Masalah pertama adalah masalah maksimasi, di mana solusi pembulatan menghasilkan keuntungan 680, hanya lebih kecil 20 dibanding yang dihasilkan solusi bulat optimum 700. Masalah kedua adalah masalah minimasi di mana solusi pembulatan adalah tak layak. Ini menunjukkan 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. Sebaliknya, pada masalah maksimasi nilai solusi simpleks semestinya dibulatkan ke bawah. Contohnya, pada masalah kedua jika solusi simpleksnya dibulatkan ke atas akan diperoleh
2 dan
4 dan
merupakan solusi layak. Juga pada masalah ketiga, jika solusi simpleksnya dibulatkan ke bawah akan diperoleh layak.
2 dan
1 dan merupakan solusi
Nilai fungsi tujuan melalui simpleks tanpa pembatasan bilangan bulat akan selalu lebih baik dibanding solusi integer optimum karena terletak pada titik pojok luar dari batas ruang solusi layak. Suatu metode yang serupa dengan pendekatan pembulatan adalah prosedur coba-coba (trial and error). Dengan menggunakan cara ini, pengambil keputusan mengamati solusi integer dan memilih solusi yang mengoptimumkan nilai fungsi tujuan. Cara ini sangat tidak efektif jika masalahnya melibatkan sejumlah besar kendala dan variabel. Terlebih lagi, memeriksa kelayakan setiap solusi yang dibulatkan akan banyak memakan waktu.
2.3.2 Metode Pendekatan Grafik Masalah integer programming yang melibatkan dua variabel dapat diselesaikan dengan metode pendekatan grafik. Metode ini identik dengan metode grafik yang biasa digunakan dalam linear programming. Metode grafik relatif lebih mudah untuk menyelesaikan masalah integer programming dua variabel yaitu dengan menggambar grafik di atas kertas grafik kemudian menggambarkan sekumpulan titik-titik integer dalam ruang solusi layak. Masalah berikut akan diselesaikan dengan pendekatan grafik.
Contoh 2.2: Maksimumkan Kendala
100
90
10
7
70
5
10
50
,
Model ini serupa dengan model linear programming biasa. Perbedaannya terletak pada kendala terakhir yang menginginkan solusi bernilai non negatif integer. Solusi grafik untuk masalah ini ditunjukkan pada gambar di bawah. Ruang solusi layak adalah OABC. Solusi optimum masalah linear programming ditunjukkan pada titik B, dengan
5,38 dan
2,31 serta
746,15.
Untuk meencari solusii intger optiimum masaalah ini, garris Z (slope = -9/10) diigeser secara sejajar dari tittik B menuuju titik asaal. Solusi in nteger optim mum adalah h titik integer peertama yang g bersingguungan dengaan garis Z. Titik itu addalah A, deengan 7 daan
0 seerta
70 00.
Gam mbar 2.1 Peny nyelesaian deengan pendek katan grafik
2.3.3 Metode Cutting Plane (Peendekatan Gomory)
Suatu proosedur sistematik untuuk mempero oleh solusi integer opptimum terh hadap pure integger program mming perttama kali dikemukaka d an oleh R.E E Gomory pada tahun 19558. Ia kemu udian mempperluas prossedur ini un ntuk kasus yang lebih h sulit yaitu mixeed integer programmingg.
Langkah-llangkah pro osedur Gom mory yaitu: 1. Selesaaikan masalah integerr programm ming dengan metodee simpleks. Jika masalaah sederhan na, dapat disselesaikan dengan d pend dekatan graffik.
2. Periksa solusi optimum. Jika semua variabel basis memiliki nilai integer, maka solusi optimum telah diperoleh dan proses berakhir. Jika masih ada satu atau lebih variabel basis memiliki nilai pecah, teruskan ke tahap 3. 3. Buatlah suatu skala Gomory (suatu bidang pemotong atau cutting plane) dan cari solusi optimum melalui proses dual simpleks. Kembali ke tahap 2.
Kendala Gomory dalam Pure Integer Programming Tabel optimum masalah linear programming berikut merupakan solusi optimum kontinu. Tabel 2.2 Solusi optimum masalah linear programming
Basis
Solusi
Z
.
0 ..
0
1 ..
0
.
.
0
1 1, … ,
Di mana variabel 1, … ,
….. ….. .
.
.
menunjukkan variabel basis dan variabel
adalah non basis.
Perhatikan persamaan ke di mana variabel ∑
di mana
Kemudian pisahkan
dan
diasumsikan bernilai non integer.
non integer. menjadi bagian yang bulat dan bagian pecah non
negatif seperti berikut: jadi jadi
, di mana 0 , di mana 0
1 1
Contoh: 3 2 7 8 7 3
1 2 7 8 1 3
1 0 2
7 3 -1 2 5
-3
2 3
-1
0
-1
3 5
Kendala Gomory yang diinginkan yaitu: ,
adalah variabel slack Gomory ke .
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.
Tabel baru setelah penambahan kendala Gomory disajikan pada tabel berikut: Tabel 2.3 Penambahan kendala Gomory
Basis Z
Solusi 0
0 …..
0
1 …..
0
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
0
1
0 ….
0
…..
.
…..
1
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. Berikut ini terdapat persoalan integer programming:
Contoh 2.3: 7
Maksimumkan
9 3
Kendala
6 35
7 ,
Solusi kontinu optimumnya diperoleh dalam tabel berikut:
Tabel 2.4 Solusi optimal contoh 2.3 (iterasi 0)
Basis
Solusi
Z
0
0
28/11
15/11
63
0
1
7/22
1/22
7/2
1
0
-1/22
3/22
9/2
Karena solusi tidak bulat, suatu kendala Gomory ditambahkan pada tabel itu. Kedua persamaan (
dan
) pada masalah ini memiliki nilai
yang sama, yaitu
, sehingga salah satu dapat digunakan, misalkan digunakan persamaan , ini menghasilkan
atau 0
7 22
0
1 22
3
1 2
Sehingga kendala Gomory menjadi: 7 22
1 22
1 2
Tabel baru setelah penambahan kendala Gomory menjadi: Tabel 2.5 Penambahan kendala Gomory contoh 2.3 (iterasi 0)
Basis
Solusi
Z
0
0
28/11
15/11
0
63
0
1
7/22
1/22
0
7/2
1
0
-1/22
3/22
0
9/2
0
0
-7/22
-1/22
1
-1/2
Dengan memakai metode dual simpleks diperoleh tabel baru yaitu:
Tabel 2.6 Solusi optimal contoh 2.3 (iterasi 1)
Basis
Solusi
Z
0
0
0
1
8
59
0
1
0
0
1
3
1
0
0
1/7
-1/7
32/7
0
0
1
1/7
-22/7
11/7
Solusi baru yang didapat masih belum bilangan bulat, akibatnya suatu kendala Gomory baru ditambahkan. Dapat dilihat bahwa persamaan 47), maka 0
ditulis dalam berikut: 1 7
0
6 7
4
4 7
Sehingga dihasilkan kendala Gomory kedua sebagai berikut: 1 7
6 7
4 7
memiliki (
Kemudian ditambahkan pada tabel 2.7 berikut: Tabel 2.7 Penambahan kendala Gomory contoh 2.3 (iterasi 1)
Basis Z
Solusi 0
0
0
1
8
0
59
0
1
0
0
1
0
3
1
0
0
1/7
-1/7
0
32/7
0
0
1
1/7
-22/7
0
11/7
0
0
0
-1/7
-6/7
1
-4/7
Dengan menggunakan dual simpleks diperoleh hasil:
Tabel 2.8 Solusi optimal contoh 2.3 (iterasi 2)
Basis Z
Solusi 0
0
0
0
2
7
55
0
1
0
0
1
0
3
1
0
0
0
-1
1
4
0
0
1
0
-4
1
1
0
0
0
1
6
-7
4
Didapat solusi bulat optimum
4,
3, dan
55.
2.3.4 Metode Branch and Bound Metode branch and bound adalah salah satu metode untuk mendapatkan penyelesaian optimal program linier yang menghasilkan variable-variable keputusan bilangan bulat. Metode ini membatasi penyelesaian optimum yang akan menghasilkan bilangan pecahan dengan cara membuat cabang atas dan bawah bagi masing-masing variable keputusan yang bernilai pecahan agar bernilai bulat sehingga setiap pembatasan akan menghasilkan cabang baru. Metode branch and bound telah menjadi kode computer standar untuk integer programming, 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. Berikut ini adalah langkah-langkah penyelesaian masalah maksimasi dengan metode branch and bound: 1. Selesaikan masalah LP biasa tanpa pembatasan bilangan bulat dengan metode simpleks biasa. 2. Teliti solusi optimalnya. 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
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.
Untuk memperoleh gambaran yang lebih jelas tentang metode Branch dan Bound, perhatikan contoh 2.4 berikut:
Contoh 2.4: 3
Maksimumkan 2
Kendala
5 4
25
8 2 ,
10
Solusi optimum kontinu masalah tersebut adalah
8,
2,25 dan
35,25.
Solusi tersebut merupakan batas awal. Batas bawah merupakan solusi yang dibulatkan ke bawah, yaitu
8,
2 dan
34. Pada metode branch
and bound, masalah tersebut dibagi ke dalam dua bagian untuk mencari nilai solusi bulat yang yang mungkin bagi
dan
. Untuk itu, dipilih variabel dengan
nilai solusi pecah yang memiliki bagian pecah terbesar. Dalam kasus ini hanya yang memiliki bagian pecah, maka ia dipilih. Untuk menghilangkan bagian pecah pada
, dua kendala baru dibuat. Nilai bulat terdekat terhadap 2,25 yaitu 2 dan 3.
Sehingga diperoleh dua kendala baru yang saling mutually exclusive, yaitu
2
3 yang selanjutnya akan diuraikan sebagai bagian A dan bagian B.
dan
Kendala-kendala baru tersebut secara efektif menghilangkan semua nilai pecah yang mungkin
.
Bagian A: 3
Maksimumkan
45
2
Kendala
5 25
8
2
10 2
0
,
Bagian B: 2
Kendala
5
3
Maksimumkan
4
25
8
2
10 3 ,
0
Bagian A dan bagian B diselesaikan dengan metode simpleks tanpa pembatasan bilangan bulat. Solusi simpleksnya yaitu: Bagian A:
8,
Bagian B:
6,5,
2, dan 3, dan
34 34,5
Bagian A diperoleh suatu solusi yang semuanya bulat. Pada bagian A nilai Z yang didapat merupakan nilai batas bawah. Pada solusi bagian B membenarkan pencarian lebih lanjut karena diperoleh nilai Z yang lebih besar. Sangat mungkin bahwa pencarian lebih lanjut dapat menghasilkan suatu solusi yang semuanya bulat dengan nilai Z lebih besar dari 34.
Selanjutnya bagian B dicabangkan ke dalam dua sub bagian, yaitu B1 dan B2. Pada sub bagian B1 ditambah kendala baru yaitu
6, sedangkan pada sub
7. Kedua sub-masalah tersebut dinyatakan
bagian B2 ditambah kendala sebagai berikut:
Sub bagian B1: 3
Maksimumkan 2
Kendala
5 4
25
2
8 10 3 6
,
0
Sub bagian B2: 3
Maksimumkan 2
Kendala
5 4
25
2
8 10 3 7
,
0
Solusi simpleks kedua sub masalah tersebut yaitu: 6,
Sub bagian B1:
3,25, dan
34,25
Sub bagian B2: tidak layak. Sub-bagian B1 menghasilkan nilai fungsi tujuan yang lebih besar dari 34 sehingga harus dicabangkan lagi ke dalam sub-masalah dengan tambahan kendala 3 dan
4. Kedua sub masalah tersebut selanjutnya diberi nama sub-
bagian B1a dan B1b.
Sub bagian B1a: 3
Maksimumkan 2
Kendala
5
4
25
8
2
10 3 6 3 ,
0
Sub bagian B1b: 3
Maksimumkan 2
Kendala
5
4
25
2
8 10 3 6 4
,
0
Solusi optimum dengan metode simpleks adalah: Sub bagian B1a:
6,
Sub bagian B1b:
4,25,
3, dan 4, dan
33. 33,5.
Kedua solusi tersebut memiliki nilai fugsi tujuan (
33 dan
33,5)
yang lebih buruk dibandingkan solusi yang dihasilkan oleh bagian A. Oleh karena itu, proses pencabangan dihentikan. Solusi bulat optimum adalah dan
8,
2,
34 yang dihasilkan oleh bagian A yang memiliki solusi bulat dengan nilai
fungsi tujuan tertinggi (karena kasus maksimasi).
Seluruh prosedur branch and bound untuk masalah ini ditunjukkan pada gambar berikut: Model Awal
inferior
8
2
3
2 8 2,25 35,25
34 3
6
35,25
3,25
4
34,25
6,5 3
6
7 Tak layak
Gambar 2.2 Grafik pencabangan pada metode Branch and Bound
inferior
