metode branch-and-cut untuk menyelesaikan …

i

METODE BRANCH-AND-CUT UNTUK MENYELESAIKAN

PERMASALAHAN RUTE KENDARAAN BERKAPASITAS

Skripsi

Diajukan untuk Memenuhi Salah

Satu Syarat Memperoleh Gelar Sarjana Sains

Program Studi Matematika

Disusun Oleh :

Victor

NIM : 063114001

PROGRAM STUDI MATEMATIKA JURUSAN MATEMATIKA

FAKULTAS SAINS DAN TEKNOLOGI

UNIVERSITAS SANATA DHARMA

YOGYAKARTA

2010

ii

BRANCH AND CUT METHOD TO SOLVE CAPACITATED VEHICLE

ROUTING PROBLEMS

Thesis

Presented as Partial Fulfillment of the Requirements

To Obtain The Sarjana Sains

In Mathematics

By :

Victor

Student Number : 063114001

MATHEMATICS STUDY PROGRAM MATHEMATICS DEPARTMENT

SCIENCE AND TECHNOLOGY FACULTY

SANATA DHARMA UNIVERSITY

YOGYAKARTA

2010

vi

HALAMAN PERSEMBAHAN

Kupersembahkan untuk

Papa dan mama

Keluargaku tercinta

viii

ABSTRAK Permasalahan rute kendaraan berkapasitas (CVRP – Capacitated Vehicle Routing Problems) adalah permasalahan pengiriman dimana setiap konsumen hanya dilayani satu kali, kendaraan yang digunakan identik, hanya terdapat satu sumber, dan terdapat batasan kapasitas pada kendaraan dengan tujuan utama adalah peminimalan total biaya. Dalam penulisan ini akan diperkenalkan suatu metode iterasi untuk menyelesaikan permasalahan di atas, yaitu metode branch-and-cut. Metode branch-and-cut adalah suatu metode iterasi yang digunakan untuk menyelesaikan permasalahan program linear bilangan bulat dengan menyelesaikan permasalahan program linear relaksasi lalu menambahkan kendala cuts dan membuat percabangan jika hasil yang didapat bukan bilangan bulat sampai pada setiap percabangannya menghasilkan bilangan bulat atau tidak mempunyai penyelesaian. Metode branch-and-cut merupakan kombinasi dari dua metode, yaitu metode branch-and-bound dan metode cutting plane.

ix

ABSTRACT

Capacitated vehicle routing problems is distribution problem where each costumer is served once, vehicle that is used are identical, there is only one depot, and only the capacity restriction for the vehicle are imposed and the objective is to minimize the total cost. In this thesis will be introduced a iterate method to solve above problems, which is branch-and-cut method. Branch-and-cut method is a iterate method which is used to solve integer linear programming by solving the relaxation linear programming then add new cuts constraint and make branching if the solution is not integer, until in each branching has integer solution or has not any solution. Branch-and-cut method is a combination from two methods, which is branch-and-bound method and cutting plane method.

x

KATA PENGANTAR

Segala puji dan syukur, penulis panjatkan kepada Tuhan Yesus Kristus,

sang Juru Selamat, sehingga karena kasih dan karunia-Nya skripsi ini dapat

terselesaikan tepat waktu.

Dalam penyusunan skripsi ini penulis membutuhkan bantuan dari

berbagai pihak. Oleh karena itu, pada kesempatan ini ingin mengucapakan terima

kasih atas segala segala bimbingan, bantuan, dorongan dan kerjasama yang telah

diberikan sehingga skripsi ini dapat terselesaikan dengan baik, kepada:

1. Ibu Lusia Krismiyati Budiasih, S.Si., M.Si., selaku dosen pembimbing dan

Kaprodi Matematika FST-USD yang dengan rendah hati mau meluangkan

banyak waktu luang dan penuh kesabaran telah membimbing selama

penyusunan skripsi ini dari awal hingga akhir.

2. Ibu Ch. Enny Murwaningtyas, S.Si., M.Si., selaku dosen penguji yang

telah memberikan saran dan kritik dalam skripsi ini.

3. Bapak St. Eko Hari Parmadi, S.Si., M.Kom., selaku dosen penguji yang

telah memberikan saran dan kritik dalam skripsi ini.

4. Papa, mama, kakak-kakakku, dan keluargaku atas kasih sanyang, doa,

semangat, dan dukungannya.

5. Sahabat-sahabatku seperjuangan angkatan 2006, terima kasih atas

semangat dan dukungannya.

6. Teman-teman kost, terima kasih atas saran-saran dan bantuannya.

xi

7. Semua pihak yang telah membantu penulisan skripsi ini yang tidak dapat

penulis sebutkan satu persatu.

Tak ada gading yang tak retak, penulis menyadari kekurangan dalam skripsi ini,

untuk itu saran serta kritik sangat diharapkan dalam peningkatan kualitas skripsi

ini, dan akhirnya penulis berharap semoga skripsi ini dapat bermanfaat bagi

semua pihak.

Yogyakarta, Juni 2010

Penulis

xii

DAFTAR ISI

Halaman

HALAMAN JUDUL ........................................................................................ i

HALAMAN JUDUL DALAM BAHASA INGGRIS ..................................... ii

HALAMAN PERSETUJUAN PEMBIMBING .............................................. iii

HALAMAN PENGESAHAN .......................................................................... iv

PERNYATAAN KEASLIAN KARYA .......................................................... v

HALAMAN PERSEMBAHAN ...................................................................... vi

LEMBAR PERNYATAAN PERSETUJUAN PUBLIKASI KARYA ILMIAH

UNTUK KEPENTINGAN AKADEMIS ........................................................ vii

ABSTRAK ....................................................................................................... viii

ABSTRACT ..................................................................................................... ix

KATA PENGANTAR ..................................................................................... x

DAFTAR ISI .................................................................................................... xii

DAFTAR GAMBAR ....................................................................................... xiv

BAB I. PENDAHULUAN ............................................................................... 1

A. Latar Belakang Masalah ....................................................................... 1

B. Perumusan Masalah ............................................................................. 3

C. Batasan Masalah .................................................................................. 3

D. Tujuan Penulisan .................................................................................. 4

E. Metode Penulisan ................................................................................. 4

F. Manfaat Penulisan ................................................................................ 4

G. Sistematika Penulisan .......................................................................... 4

xiii

BAB II. METODE BRANCH-AND-BOUND DAN CUTTING PLANE ......... 6

A. Matriks dan Operasi Baris Elementer .................................................. 6

B. Program Linear..................................................................................... 8

C. Metode Simpleks yang Diperbaharui ................................................... 16

D. Metode Branch-and-bound .................................................................. 22

E. Metode Cutting plane ........................................................................... 36

BAB III. METODE BRANCH-AND-CUT PADA PERMASALAHAN RUTE

KENDARAAN BERKAPASITAS ...................................................... 47

A. Permasalahan Rute Kendaraan Berkapasitas (Capacitated Vehicle Routing

Problems - CVRP) ................................................................................ 47

B. Metode Branch-and-cut ....................................................................... 54

C. Perbandingan Metode Branc- and-Cut, Cutting plane, dan Branc-and-

Bound. .................................................................................................. 66

BAB IV. APLIPAKSI METODE BRANCH-AND-CUT DALAM MASALAH

PENDISTRIBUSIAN BUSA PADA PABRIK “Sari Guna” .............. 84

BAB V. PENUTUP

A. Kesimpulan .......................................................................................... 101

B. Saran ..................................................................................................... 102

DAFTAR PUSTAKA ...................................................................................... 103

LAMPIRAN ..................................................................................................... 104

xiv

DAFTAR GAMBAR

Halaman

Gambar 2.4.1. Algoritma Metode Branch-and-bound ..................................... 26

Gambar 2.5.1 Algoritma Metode Cutting plane .............................................. 39

Gambar 3.2.1. Algoritma Metode Branch-and-cut .......................................... 57

Gambar 4.1.1. Graf permasalahan distribusi di pabrik busa “Sari Guna” ....... 85

Gambar 4.1.2. Nama busur-busur pada permasalahan Pabrik “Sari Guna” ..... 86

BAB I

PENDAHULUAN

A. Latar Belakang Masalah

Berkembangnya sebuah perusahaan yang memproduksi barang dapat

menyebabkan perusahaan perlu melakukan perluasan bidang usaha. Dengan

adanya perluasan bidang usaha, perusahaan dituntut untuk dapat memenuhi

kebutuhan konsumen yang ada. Hal ini mengakibatkan biaya operasi perusahaan

semakin besar, terutama pada bidang pengiriman barang. Oleh sebab itu,

belakangan ini banyak terlihat peningkatan kegunaan dari pengoptimalan

pengiriman barang yang berbasis pada riset operasi dan pemograman matematika.

Banyak perusahaan-perusahaan menggunakan pengoptimalan untuk masalah

perencanaan pengiriman barang dan dapat menghemat antara 5% sampai 20% dari

total biaya pengiriman itu sendiri (Paolo T, 2002). Permasalahan seperti

pengiriman barang dari produsen kepada konsumen seperti ini secara umum

disebut permasalahan rute kendaraan (Vehicle Routing Problem).

Dengan menggunakan metode jaringan yang ada pada riset operasi,

pengiriman barang biasanya digambarkan menggunakan graf dengan anak panah

dan simpul. Anak panah menggambarkan jalan atau rute yang dapat dilewati.

Tidak semua anak panah dapat langsung dilewati begitu saja menuju konsumen,

ini semua tergantung dari apakah rute tersebut hanya dapat dilewati satu arah saja

atau dapat dilewati dua arah. Setiap anak panah mempunyai nilainya masing-

masing yang mungkin dapat diartikan sebagai ongkos atau secara umum sering

dianggap sebagai panjang atau waktu tempuh rute tersebut. Simpul

menggambarkan tempat-tempat yang dilewati sewaktu mengirimkan barang dan

simpul terakhir biasanya diartikan sebagai konsumen atau tempat terakhir

pengiriman barang tersebut.

Permintaan-permintaan yang diajukan konsumen dapat berbeda-beda

dan harus dipenuhi. Beberapa bentuk permintaan yang mungkin diajukan

konsumen antara lain adalah banyaknya barang yang mungkin berbeda-beda dan

harus dikirimkan kepada tiap konsumen, adanya periode dari waktu kapan

2

konsumen dapat dilayani yang dikarenakan konsumen sedang tidak ada ditempat,

adanya batasan waktu yang diberikan konsumen untuk memenuhi permintaannya,

dan banyaknya kendaraan yang bisa dipakai untuk melayani konsumen.

Terkadang setiap permintaan konsumen tidak dapat dipenuhi seutuhnya atau tidak

sama sekali. Untuk menghadapi hal seperti ini prioritas atau pinalti yang

berhubungan dengan keterbatasan pengiriman dapat diberikan kepada konsumen.

Permintaan-permintaan konsumen dilayani oleh perusahaan

menggunakan kendaraan. Kendaraan disini mempunyai karakteristik yang

berbeda-beda bergantung pada keperluan konsumen. Beberapa karakteristik dari

kendaraan tersebut adalah sumber (home depot) dan kemungkinan berakhir

ditempat lain setelah menyelesaikan masalah, kapasitas kendaraan yang

mengekspresikan berat atau volum atau banyaknya barang yang dapat dibawa

sebuah kendaraan, jenis barang yang dapat diangkut oleh sebuah kendaraan, jalan

yang mana yang bisa dilalui oleh sebuah kendaraan, dan biaya yang dikenakan

pada kendaraan (jarak, waktu, jalan, dll).

Melihat adanya berbagai macam permintaan dari konsumen dan

karakteristik yang ada pada kendaraan, maka ada banyak masalah pengoptimalan

yang timbul yaitu permasalahan rute kendaraan berkapasitas (Capacitated Vehicle

Routing Problems), yang merupakan bentuk paling dasar dari permasalahan pada

VRP, distance-constained VRP, VRP dengan Time Windows, VRP dengan

Backhauls dan VRP dengan Pickup and Delivery. Dalam penulisan ini hanya akan

dibahas pada permasalahan rute kendaraan berkapasitas (Capacitated Vehicle

Routing Problems).

Permasalahan rute kendaraan berkapasitas adalah masalah pengoptimalan

yang hanya berbasis pada satu tempat awal, permintaan konsumen yang pasti,

semua kendaraan yang dipakai adalah identik, dan terdapat batasan kapasitas pada

kendaraan. Tujuan dari masalah pengoptimalan di atas adalah untuk

meminimumkan total biaya untuk melayani semua komnsumen yang ada.

Permasalahan rute kendaraan berkapasitas dapat digambarkan dengan

graf, dimana semua simpul melambangkan konsumen-konsumen serta anak panah

atau busur melambangkan rute. Terdapat bilangan nonnegatif untuk setiap busur

3

yang melambangkan biaya yang diperlukan dari simpul awal menuju simpul

tujuan. Secara umum perjalanan dari suatu simpul menuju simpul yang sama tidak

diperbolehkan. Untuk menghindari hal ini didefinisikan biaya perjalanan tersebut

adalah ∞ . Setiap konsumen mempunyai suatu bilangan nonnegatife yang

menyatakan permintaan yang harus dikirimkan ke konsumen tersebut, sedangkan

permintaan untuk sumber adalah 0. Pengiriman barang dilakukan dengan

sejumlah kendaraan di sumber yang masing-masing mempunyai kapasitas yang

sama. Untuk menjamin adanya daerah yang memenuhi, perlu diasumsikan bahwa

setaiap permintaan konsumen tidak lebih dari kapasitas kendaraan

Dari graf tersebut, Capacitated Vehicle Routing Problem dapat

dirumuskan sebagai permasalahan program linear bilangan bulat. Untuk

menyelesaikan permasalahan tersebut, dapat menggunakan metode Cutting plane,

metode Branch-and-bound, metode Branch-and-cut, metode Set Covering,

metode Classical Heuristics, metode Metaheuristics, metode implicit

enumeration, dan lain sebagainya. Namun, dalam penulisan ini akan dipaparkan

metode Branch-and-cut untuk menyelesaikan masalah Capacitated Vehicle

Routing Problem.

B. Perumusan Masalah

Berdasarkan latar belakang masalah di atas dapat dirumuskan

permasalahan sebagai berikut:

1. Bagaimana cara menentukan solusi optimal Capacitated Vehicle Routing

Problem dengan menggunakan metode Branch-and-cut.

2. Bagaimana algoritma metode Branch-and-cut dan implementasinya

menggunakan bahasa pemrogaman MATLAB.

C. Batasan Masalah

Pembahasan metode Branch-and-cut dibatasi hanya pada permasalahan

rute kendaraan pada kendaraan yang berkapasitas.

4

D. Tujuan Penulisan

Tujuan penulisannya adalah untuk menyelesaikan permasalahan rute

kendaraan berkapasitas dengan menggunakan metode Branch-and-cut dan untuk

menyusun algoritma Branch-and-cut menggunakan bahasa pemrograman

MATLAB.

E. Metode Penulisan

Metode penulisan ini menggunakan metode studi pustaka, yaitu dengan

menggunakan buku-buku pendukung yang berkitan dengan metode Branch-and-

cut dan menuliskan programnya dengan bahasa pemrograman MATLAB.

F. Manfaat Penulisan

Manfaat penulisan ini adalah untuk memperoleh pengetahuan tentang

metode Branch-and-cut dalam menyelesaikan permasalahan rute kendaraan

berkapasitas serta pemrogramannya dengan bahasa pemrograman MATLAB.

G. Sistematika Penulisan

BAB I PENDAHULUAN

A. Latar Belakang Masalah

B. Perumusan Masalah

C. Batasan Masalah

D. Tujuan Penulisan

E. Metode Penulisan

F. Manfaat Penulisan

G. Sistematika Penulisan

BAB II METODE BRANCH-AND-BOUND DAN CUTTING PLANE

A. Matriks dan Operasi Baris Elementer

B. Program Linear

C. Metode Simpleks yang Diperbaharui

5

D. Metode Branch-and-bound

E. Metode Cutting plane

BAB III METODE BRANCH-AND-CUT PADA PERMASALAHAN RUTE

KENDARAAN BERKAPASITAS

A. Permasalahan Rute Kendaraan Berkapasitas (Capacitated Vehicle Routing

Problems - CVRP)

B. Metode Branch-and-cut

C. Perbandingan Metode Branch-and-bound, Cutting plane, dan Branch-and-

cut.

BAB IV APLIPAKSI METODE BRANCH-AND-CUT DALAM MASALAH

PENDISTRIBUSIAN BUSA PADA PABRIK “Sari Guna”

BAB V PENUTUP

A. Kesimpulan

B. Saran

BAB II

METODE BRANCH-AND-BOUND DAN CUTTING PLANE

A. Matriks dan Operasi Baris Elementer

Definisi 2.1.1

Matriks bujur sangkar A berukuran nn× mempunyai invers jika ada matriks B

sehingga nIBAAB == . Matriks B disebut matriks invers dari A.

Teorema 2.1.2

Jika matriks A berukuran nn× mempunyai invers, maka untuk sebarang matriks

kolom b berukuran 1×n , sistem persamaan bAx = mempunyai penyelesaian

tunggal, yaitu bAx 1−= berukuran 1×n .

Bukti:

Karena A mempunyai invers, maka

bAxbAIxbAAxA

bAx

1

1

11

−

−

−−

====

Selanjutnya akan dibuktikan bahwa bAx = mempunyai penyelesaian tunggal.

Misalkan 1x dan 2x merupakan penyelesaian dari sistem persamaan linear, yang

berarti

7

21

12

12

1211

12

12

21

xxxxο

)xI(xο)xA(xAοA

)xA(xοAxAxο

AxAx

=−=−=

−=−=−=

=

−−

■

Definisi 2.1.3

Matriks yang mempunyai invers disebut matriks tak singular, sedangkan matriks

yang tidak mempunyai invers disebut matriks singular.

Definisi 2.1.4

Operasi baris elementer pada suatu matriks adalah salah satu operasi:

1. Menukar letak dari dua baris tersebut.

2. Mengalikan suatu baris dengan konstanta tak nol.

3. Menganti suatu baris dengan hasil penjumlahan baris tersebut dan

kelipatan baris lain.

Definisi 2.1.5

Sebuah sistem persamaan bAx = terdiri dari tiga matriks, yaitu matriks

koefisien, A, matriks variabel, x, dan matriks ruas kanan, b. Matriks lengkap

adalah matriks yang terdiri dari matriks koefisien dan matriks ruas kanan, yakni

[ ]bA .

8

B. Program Linear

Program linear (Linear Programming - LP) adalah sebuah alat untuk

menyelesaikan permasalahan optimisasi. Pada tahun 1947, George Dantzig

mengembangkan sebuah metode yang efisien, yaitu metode algoritma simpleks

untuk menyelesaikan permasalahan program linear. Sejak pengembangan dari

algoritma simpleks, program linear telah banyak dipakai dalam permasalahan

optimisasi di dalam berbagai industri yang berbeda-beda, seperti pada perbankan,

bidang pendidikan, ilmu kehutanan, bidang perminyakan, dan transportasi.

Dalam sebuah program linear terdiri dari enam faktor, yang pertama

adalah variabel keputusan (decision variable). Dalam program linear, variabel

keputusan haruslah dapat menggambarkan secara utuh keputusan apa saja yang

harus dibuat. Sebagai contoh, yaitu banyaknya kendaraan yang harus dioperasikan

setiap minggunya atau banyaknya pasukan yang diperlukan setiap minggunya.

Faktor kedua adalah fungsi objektif (objective function). Dalam setiap

program linear, keputusan yang dibuat biasanya ingin memaksimalkan (untung)

atau meminimalkan (biaya) sebuah fungsi dari variabel keputusan. Fungsi seperti

inilah yang disebut sebagai fungsi objektif.

Faktor ketiga adalah kendala (constraints). Kendala adalah batasan-

batasan yang diberikan pada variabel keputusan yang dapat berupa persamaan

atau pertidaksamaan dalam variabel keputusan.

Faktor keempat adalah koefisien teknis (technological coefficients).

Koefisien teknis adalah koefisien yang dimiliki oleh variabel keputusan dalam

kendala. Mengapa disebut sebagai koefisien teknis, karena koefisien teknis sering

9

mencerminkan teknologi yang dipakai untuk menghasilkan hasil yang berbeda.

Sedangkan konstanta yang berada pada ruas kanan persamaan atau

pertidaksamaan di dalam kendala yang fungsinya adalah memperlihatkan

banyaknya sumber daya yang tersedia disebut RHS (Right Hand Side), dan ini

merupakan faktor kelima dalam program linear.

Faktor keenam adalah tanda batasan (sign restrictions). Fungsi dari tanda

batasan ini adalah untuk membatasi apakah variabel keputusan dapat bernilai

positif atau negatif, atau variabel keputusan hanya boleh bernilai nonnegatif. Jika

variabel keputusan dapat bernilai positif atau negatif, maka dapat dikatakan bahwa

variabel keputusan tersebut tidak ada batasan tanda (Unrestricted Sign - sering

disingkat dengan urs).

Dari keenam faktor di atas secara umum sebuah program linear

dirumuskan

Maksimumkan/minimumkan ∑=

=n

jjj xcz

1

m

n

jjmj

n

jjj

bxa

bxa

≥=≤

≥=≤

∑

∑

=

=

1

11

1

Kendala

M

dengan z adalah fungsi objektif, jx adalah variabel keputusan,

( )njmiaij ,,1,,,1, KK == , adalah koefisien teknis, dan ( )mibi ,,1, K= , adalah

RHS.

10

Definisi 2.2.1

Sebuah fungsi ( )nxxxf ,,, 21 K disebut fungsi linear jika dan hanya jika untuk

sembarang konstanta naaa ,,, 21 K

( ) nnn xaxaxaxxxf +++= LK 221121 ,,,

Definisi 2.2.2

Untuk sembarang fungsi linear ( )nxxxf ,,, 21 K dan sembarang bilangan b ,

pertidaksamaan ( ) bxxxf n ≤,,, 21 K atau ( ) bxxxf n ≥,,, 21 K disebut

pertidaksamaan linear.

Definisi 2.2.3

Sebuah permasalahan program linear adalah permasalahan pengoptimalan di

mana:

1. bertujuan mengoptimalkan (memaksimalkan atau meminimalkan) fungsi

objektif.

2. nilai dari variabel keputusan harus memenuhi setiap kendala yang ada.

Setiap kendala harus merupakan persamaan linear atau pertidaksamaan

linear.

3. sebuah tanda batasan dihubungkan dengan setiap variabel. Untuk setiap

variabel ix , tanda batasan yang ditetapkan jika bukan nonnegatif ( 0≥ix ),

maka urs.

11

Definisi 2.2.4

Suatu program linear dikatakan mempunyai penyelesaian jika ada titik yang

memenuhi semua kendala yang ada.

Definisi 2.2.5

Daerah penyelesaian atau daerah layak sebuah program linear adalah himpunan

dari semua titik-titik yang memenuhi semua kendala atau batasan yang ada pada

program linear.

Definisi 2.2.6

Untuk permasalahan pemaksimalan (peminimalan), sebuah penyelesaian optimal

untuk program linear adalah titik yang berada pada daerah layak yang jika

substitusikan pada fungsi objektif menghasilkan nilai yang paling besar (kecil).

Ada beberapa metode untuk menyelesaikan permasalahan program

linear. Metode yang paling sering dipakai adalah metode simpleks. Terdapat

beberapa definisi sebelum mengetahui algoritma dari metode simpleks

Definisi 2.2.7

Variabel dasar (Basic Variable – BV) adalah variabel dimana kolom yang

bersesuaian pada tabel optimum hanya mempunyai satu elemen tak nol dan

bernilai satu, sedangkan variabel non dasar (Non-Basic Variable – NBV) adalah

12

variabel dimana kolom yang bersesuaian pada tabel optimum mempunyai lebih

dari satu elemen tak nol.

Definisi 2.2.8

Sebuah penyelesaian dasar untuk bx =A didapat dengan mengatur mn −

variabel non dasar (Bukan Variabel Dasar – NBV) = 0 dan mencari nilai m

variabel dasar (BV) yang tersisa.

Metode Simpleks

Agar sebuah permasalahan program linear dapat diselesaikan menggunakan

metode simpleks, permasalahan tersebut haruslah dirubah menjadi bentuk standar.

Yaitu dengan cara:

1. Ubah fungsi objektif menjadi 01

=−∑=

n

iii xcz .

2. Mengalikan -1 pada kendala dimana 0<ib .

3. Ubah setiap pertidaksamaan linear ( )jnj bxxxf ≤,,, 21 K menjadi

( )jjnj bsxxxf =+,,, 21 K , dengan js adalah variabel pengetat.

4. Ubah setiap pertidaksamaan linear ( )jnj bxxxf ≥,,, 21 K menjadi

( )jjnj bexxxf =−,,, 21 K , dengan je adalah variabel surplus.

5. Tambahkan tanda batasan 0, ≥jj se ( mj K,,21= ).

Tetapi dengan mengubah kendala pertidaksamaan menjadi kendala persamaan

masih terdapat baris yang variabel dasarnya bernilai negatif, yaitu pada persamaan

13

( )jjnj bexxxf =−,,, 21 K dan mungkin terdapat baris yang tidak mempunyai

variabel dasar, yaitu pada persamaan ( )jnj bxxxf =,,, 21 K . Untuk mengatasi

masalah ini, tambahkan variabel semu ja pada setiap persamaan di atas. Tetapi,

setelah menambahkan variabel semu pada persamaan tersebut muncul

permasalahan baru yaitu dengan mengambil ja dan js sebagai variabel dasar

menyebabkan 0== ji ex . Dan jika memasukkan nilai 0=ix , tidak akan

memenuhi kendala awal,

( ) jjnj bbxxxf ≥→≥ 0,,, 21 K

dan ( ) jjnj bbxxxf =→= 0,,, 21 K .

Untuk menyelesaikan masalah tersebut, pada permasalahan peminimalan

ditambahkan bilangan yang sangat besar M pada fungsi objektif sebagai

koefisien dari ja , dan pada permasalahan pemaksimalan ditambahkan bilangan

M− pada fungsi objektif sebagai koefisien dari ja . Hal ini dimaksudkan agar

variabel ja keluar dari variabel dasar menjadi variabel non dasar. Selanjutnya

dibentuk matriks lengkapnya sebagai berikut:

00000000/1000/1000/100

00/1000/1000/10000/1000/1000/1

21

21

222221

111211

21212121

MMMcccbaaa

baaabaaa

RHSaaaeeesssxxx

n

jjnjj

n

n

jjjn

±±±−−−−

−−

LLLL

LLLL

MMOMMMOMMMOMMMOMM

LLLL

LLLL

LLLL

14

Setelah mengubah program linear menjadi bentuk standar, lalu dilakukan

uji optimalitas, dengan melihat koefisien pada baris ke-0 (baris paling bawah pada

matriks lengkap yang merupakan koefisien di fungsi objektif). Pada permasalahan

pemaksimalan (peminimalan), jika semua koefisien NBV pada baris ke-0 tak

negatif (tak positif), maka bfs yang didapat adalah nilai optimal. Hal ini

disebabkan jika salah satu NBV masuk menjadi BV hanya akan mengurangi

(menambahkan) nilai z.

Jika terdapat NBV, jx , yang mempunyai koefisien negatif (positif), pilih

NBV yang koefisiennya paling kecil (besar). Dengan memilih koefisien yang

paling kecil (besar) diharapkan dapat memaksimalkan (meminimalkan) nilai z

paling banyak. Untuk menentukan BV mana yang akan keluar, dilakukan uji rasio

yaitu dengan menghitung

> 0,min ijij

i aab

. Dipilihnya 0>ija adalah agar NBV

yang akan masuk bernilai positif dan diambil yang paling minimum agar saat

membentuk variabel dasar yang baru, yaitu dengan melakukan operasi baris

elementer berhingga kali, tidak membuat nilai variabel dasar yang lain menjadi

negatif. Dengan dipilihnya kj

k

ab

yang paling minimum, maka 0≥

−

kj

k

ij

i

ab

ab

.

Secara umum algoritma metode simpleks untuk permasalahan

pemaksimalan (peminimalan) adalah

1. Mengubah program linear menjadi bentuk standar.

2. Uji optimalitas.

15

3. Menentukan variabel dasar mana yang akan keluar dan variabel non dasar

mana yang akan masuk lalu kembali ke langkah ke-2.

Contoh 2.2.1

Maksimalkan

21 45 xxz +=

Kendala

456105

21

21

≤+≤+

xxxx

Penyelesaian

Iterasi 1

Langkah 1

Ubah menjadi bentuk standar

Maksimalkan

00045 2121 =−−−− ssxxz

Kendala

456105

221

121

=++=++

sxxsxx

Dengan tabel awalnya adalah

00045451061050111

2121

−−

RHSssxx

16

Langkah 2

Dapat dilihat bahwa 45,5,0 21 === ssz merupakan penyelesaian dasar.

Dipilih NBV= 1x karena 1x mempunyai koefisien negatif yang paling kecil.

Rasio 1x yang paling kecil adalah pada baris kendala ke-2, sehingga dengan

menggunakan operasi baris elementer didapat

5.225.00105.41.006.015.01.014.00

2121

−

−RHSssxx

Karena masih terdapat NBV yang negatif, lanjutkan ke langkah ke-2.

Iterasi 2

Langkah 2

Dipilih NBV= 2x karena 2x mempunyai koefisien negatif yang paling kecil.

Rasio 2x yang paling kecil adalah pada baris ke-1, dengan menggunakan operasi

baris elementer didapat

75.2325.05.20075.315.05.10125.125.05.210

2121

−−

RHSssxx

Iterasi 3

Langkah 2

Karena tidak ada NBV yang mempunyai koefisien negatif maka penyelesaian

dasar 25.1,75.3,75.23 21 === xxz merupakan penyelesaian optimal.

17

C. Metode Simpleks yang Diperbaharui

Sebuah program linear dapat juga diselesaikan dengan metode simpleks

yang sudah diperbaharui, yaitu dengan mengubahnya menjadi bentuk matriks.

Perumusan secara umum program linear dalam bentuk matriks adalah

Maksimumkan/minimumkan cx=z

bAx =Kendala

dengan [ ]nccc L21=c ,

=

nx

xx

M2

1

x ,

=

mnmm

n

n

aaa

aaaaaa

L

MMM

L

L

21

22221

11211

A , dan

=

mb

bb

M2

1

b

Misalkan N adalah matrik yang bersesuaian dengan koefisien variabel non dasar,

B adalah matriks yang bersesuain dengan koefisien variabel dasar, Nx adalah

vektor dari variabel non dasar, Bx adalah vektor dari variabel dasar, Nc adalah

vektor koefisien variabel non dasar pada fungsi objektif, dan Bc adalah vektor

koefisien veariabel dasar pada fungsi objektif. Dengan mengubah matriks A

menjadi [ ]BNA M= , vektor c menjadi [ ]BN ccc M= , dan vektor x menjadi

=

B

N

x

xx L , maka akan didapat

18

[ ] BBNN

B

N

BNz xcxcx

xcc +=

= LM (2.3.1)

dan bBxNx =+ BN (2.3.2)

Dari persamaan (2.3.2) dapat dicari nilai dari Bx , yaitu

NB NxBbBx 11 −− −= (2.3.3)

Dengan mensubstitusikan persamaan (2.3.3) ke persamaan (2.3.1) akan

didapat

NBBNNz NxBcbBcxc 11 −− −+=

Atau

NBNBz x)NBcc(bBc 11 −− −+= (2.3.4)

Dengan mensubstitusikan nilai variabel-variabel maka akan didapat

penyelesaian sementara, yaitu

BBz xc )) = , dengan bBx 1−=B)

Misalkan jc) adalah elemen dari vektor )NBcc(c 1−−= BN) yang

bersesuaian dengan Nx∈jx , maka

Nzz xc)) += (2.3.5)

Jika nilai dari variabel non dasar jx bertambah sebesar α , maka nilai dari fungsi

objektifnya akan bertambah sebesar αjc) . Untuk menguji apakah penyelesaian

sementara sudah optimal adalah dengan melihat elemen-elemen pada vektor c) .

19

Teorema 2.3.1

Pada permasalahan pemaksimalan (peminimuman), penyelesaian sementara

BBz xc )) = , dengan bBx 1−=B) dikatakan optimal jika 0≤∈∀ jj c,c c)

( 0≥∈∀ jj c,c c) )

Bukti

Perhatikan persamaan (2.3.5), Nzz xc)) += . Karena diketahui 0≤∈∀ jj c,c c)

( 0≥∈∀ jj c,c c) ) dan 0≥Nx , maka 0ˆ ≤Nxc ( 0ˆ ≥Nxc ). Akibatnya zz ˆ≤

( zz ˆ≥ ). Dengan kata lain nilai z baru akan tidak lebih besar (kecil) dari nilai z

sebelumnya.

■

Jika 0≥∈∃ jj c,c c) ( 0≤∈∃ jj c,c c) ) maka dipilih jc yang paling besar (kecil)

dan jx akan masuk sebagai variabel dasar selanjutnya. Hal ini diharapkan

menambah (mengurangi) nilai z paling banyak.

Perhatikan persamaan (2.3.3), NB NxBbBx 11 −− −= . Jika 0ˆ 1 ≥∈ − NBijc ,

maka nilai ( )iBx akan berkurang seiring dengan bertambahnya nilai ( )iNx . Jika

( ) bBx 1ˆ,ˆ

ˆ−∈= i

ij

iiN b

cb

, maka ( ) 0=iBx . Jika 0ˆ 1 ≤∈ − NBijc , maka nilai ( )iBx

bertambah seiring dengan bertambahnya nilai ( )iNx . Karena terdapat batasan

0≥Bx , maka dipilih untuk menentukan variabel dasar mana yang akan menjadi

variabel non dasar, dilakukan uji rasio, yaitu dengan menghitung

20

( ) NBbBx 11 ,,0:min −− ∈∈

>= ijiijij

iiB cbc

cb ))))

)

Secara umum algoritma metode simpleks berbasis matriks untuk

menyelesaikan permasalahan pemaksimalan (peminimalan) dapat ditulis menjadi

langkah-langkah berikut:

1. Uji program linear, yaitu apakah sebuah program linear mempunyai

penyelesaian atau tidak. Jika B merupakan matriks singular, maka program

linear tersebut tidak mempunyai penyelesaian. Jika B merupakan matriks

tak singular lanjut ke langkah ke-2.

2. Uji optimalitas, yaitu dengan mencari )( 1NBccc −−= BN) .

Jika 0≤∈∀ jj c,c c) ( 0≥∈∀ jj c,c c) ), maka penyelesaian sementara

sudah optimal, jika tidak lanjut ke langkah berikutnya.

3. Pilih elemen c) yang mempunyai nilai positif (negatif) terbesar, lalu hitung

NBbB 11 ,,0:min −− ∈∈

>= ijiijij

ij cbc

cb

x ))))

)

untuk masuk sebagai

variabel dasar baru.

4. Baharui matriks B , Bx , Nx , Bc , dan Nc , dengan menukar variabel dasar

baru dengan variabel non dasar yang baru. Kembali ke langkah pertama.

Walaupun sudah menggunakan bentuk matriks, metode simpleks di atas

masih terdapat kelemahan, yaitu menuntut untuk semua elemen b harus bernilai

positif. Untuk mengatasi hal tersebut akan diperkenalkan metode dual simpleks,

yaitu metode yang dipakai saat terdapat elemen b yang bernilai negatif.

21

Secara umum algoritma metode dual simpleks berbasis matriks untuk

menyelesaikan permasalahan program linear dapat ditulis menjadi langkah-

langkah berikut:

1. Jika setiap elemen b bernilai positif, maka penyelesaian sementara sudah

optimal. Jika terdapat elemen b yang bernilai negatif, maka lanjut ke

langkah selanjutnya.

2. Pilih elemen b yang mempunyai nilai negatif terbesar, agar lalu hitung

NBccc 1ˆ,,0ˆ:ˆ

min −∈∈

<= ijjijij

jj cc

cx ))

)

untuk masuk sebagai variabel

dasar yang baru.

3. Jika terdapat kendala dimana mempunyai RHS bernilai negatif dan setiap

koefisien variabel pada kendala tersebut bernilai positif, maka

permasalahan program linear tersebut tidak mempunyai daerah

penyelesaian karena untuk sembarang variabel non dasar yang akan masuk

menjadi variabel dasar akan selalu bernilai negatif, dan ini melanggar

batasan bahwa setiap variabel dasar harus bernilai positif.

Pada umumnya metode dual simpleks serting digunakan dalam situasi:

1. Mencari penyelesaian optimal baru setelah menambah kendala baru pada

program linear.

2. Mencari penyelesaian optimal baru setelah mengganti nilai RHS program

linear.

22

3. Menyelesaikan permasalahan peminimalan yang setiap kendalanya

mempunyai tanda ≥ .

Definisi 2.2.11

Program linear bilangan bulat adalah permasalahan program linear yang

mengharuskan semua nilai variabelnya bernilai bulat.

Definisi 2.2.12

Program linear yang didapat dengan menghilangkan kendala bilangan bulat pada

variabel disebut Program Linear Relaxation dari pemrogramman linear bilangan

bulat.

Banyak cara yang dapat digunakan untuk menyelesaikan sebuah program linear

bilangan bulat, yaitu dengan menggunakan metode branch-and-bound, metode

cutting plane, metode implicit enumeration, dan metode heuristics. Dalam bab

selanjutnya hanya akan dibahas pada penggunaan metode branch-and-bound dan

metode cutting plane.

D. Metode Branch-and-bound

Metode Branch-and-bound pertama kali dikembangkan pada tahun 1960

oleh A. Land dan G. Doig untuk menyelesaikan permasalahan umum untuk

pemrograman linear bilangan bulat. Setelah munculnya algoritma Branch-and-

bound, mulai bermunculan algoritma-algoritma lain untuk menyelesaikan

23

permasalahan pemrograman linear bilangan bulat. Salah satu contohnya adalah

algoritma additive, dimana komputasi algoritma ini sangat sederhana sehingga

dipercaya dapat memberikan solusi permasalahan pemrograman linear bilangan

bulat secara umum.

Kata Branch pada algoritma Branch-and-bound menandakan adanya

percabangan, yaitu dengan membuang nilai variabel yang tidak bulat dan

memecah permasalahan sebelumnya menjadi dua dan menambahkan kendala pada

permasalahan yang baru. Kendala yang baru ini adalah batasan untuk variabel

agar nilai yang didapat adalah bilangan bulat.

Sedangkan kata Bound pada algoritma Branch-and-bound menandakan

adanya batasan yang harus dipenuhi agar penyelesaian yang didapat dari

permasalahan-permasalahan baru yang dihasilkan pada percabangan adalah

penyelesaian optimal untuk permasalah awal.

Cara kerja dari algoritma Branch-and-bound adalah menyelesaikan

dahulu permasalahan linear awal dan melihat daerah layaknya ( 0LP ), lalu

mengambil salah satu nilai variabel yang tidak bulat ( ix ) dan membuat dua

permasalahan linear baru dengan menambahkan batasan pada daerah layaknya.

Maka permasalahan linear baru yang pertama adalah permasalahan linear awal

dengan tambahan batasan pada daerah layaknya, yaitu ( )ii xxLPLP ≤+= 01

dimana ix adalah bilangan bulat terbesar yang kurang dari atau sama dengan

ix . Persamasalahan linear baru yang kedua adalah permasalahan linear awal

dengan tambahan batasan pada daerah layaknya, yaitu ( )ii xxLPLP ≥+= 02

24

dimana ix adalah bilangan bulat terkecil yang lebih besar atau sama dengan ix .

Setelah itu setiap permasalahan baru tersebut ditentukan penyelesaiannya.

Terdapat tiga kemungkinan yang dapat terjadi pada saat menyelesaikan

permasalahan yang baru, yaitu:

1. tidak mempunyai penyelesaian.

2. mempunyai penyelesaian tetapi bukan penyelesaian bilangan bulat.

3. mempunyai penyelesaian bilangan bulat.

Jika kemungkinan pertama terjadi, maka percabangan tidak akan dilanjutkan pada

permasalahan tersebut. Jika kemungkinan kedua terjadi, maka akan dibentuk dua

permasalahan yang baru dengan menambahkan batasan pada daerah layaknya,

( )iilk xxLPLP ≤+=+1 dan ( )iilk xxLPLP ≥+=+2 , K,3,2,1=l , K6,4,2=k

dan menyelesaikan permasalahan yang baru lagi. Jika kemungkinan ketiga yang

terjadi, maka percabangan tidak akan dilakukan dan mengganti batasan untuk

permasalahan pemaksimalan jika lzz < dan lzz > untuk permasalahan

peminimalan dimana z bernilai ∞+ untuk permasalahan pemaksimalan dan ∞−

untuk permasalahan peminimalan dan lz adalah penyelesaian bilangan bulat

untuk permasalahan ke-l lalu menyelesaikan permasalahan yang tersisa.

Secara umum algoritma Branch-and-bound dapat ditulis dalam langkah-

langkah berikut:

1. Atur 0,,0 =−∞== kzl

2. Selesaikan permasalahan dengan menggunakan lLP , yaitu daerah layak

permasalahan ke-l

25

i. Jika semua variabel bilangan bulat dan zzl ≥ , maka ubah

1, +== llzz l dan lanjutkan ke langkah ke-5

ii. Jika ada variabel yang bukan bilangan bulat lanjutkan ke langkah ke-3

iii. Jika lLP tidak mempunyai daerah layak atau mempunyai penyelesaian

bilangan bulat dengan zzl ≤ , maka ubah 1+= ll dan lanjutkan ke

langkah ke-5

3. Ambil salah satu variabel ix yang bukan bilangan bulat dan bentuk

permasalahan linear baru lainnya dengan daerah layaknya adalah LPk+1 dan

LPk+2 dimana

( ) ( )iilk

iilk

xxLPLPxxLPLP

≥+=

≤+=

+

+

2

1

4. Ubah 1+= ll dan 2+= kk

5. Jika kl > perhitungan berhenti, jika tidak kembali ke langkah ke-2.

Langkah-langkah di atas digunakan khususnya untuk permasalahan

pemaksimalan pemrograman linear bilangan bulat. Untuk permasalahan

peminimalan pemrograman linear bilangan bulat, cukup mengganti nilai awal

,+∞=z dan pada langkah ke-2 diubah menjadi:

2. Selesaikan permasalahan dengan menggunakan lLP , yaitu daerah

layak permasalahan ke-l

i. Jika semua variabel bilangan bulat dan zzl ≤ , maka ubah


26

ii. Jika ada variabel yang bukan bilangan bulat lanjutkan ke

langkah ke-3

iii. Jika lLP tidak mempunyai daerah penyelesaian atau

mempunyai penyelesaian bilangan bulat dengan zzl ≥ , maka

ubah 1+= ll dan lanjutkan ke langkah ke-5

−∞===

zkl

00

iilk

iilk

xxLPLPxxLPLP

≥+=≤+=

+

+

2

1

21+=+=

kkll

1+= ll

zzl >

kl >

1+==

llzz l

lLP

Gambar 2.4.1. Algoritma Metode Branch-and-bound.

27

Berikut diberikan contoh penerapan metode branch-and-bound pada

permasalahan pemrograman linear adalah

Contoh 2.4.1

Maksimalkan

21 45 xxz +=

Kendala

+Ζ∈

≤+≤+

21

21

21

,

456105

xx

xxxx

Penyelesaian:

Iterasi 1

Langkah 1

Atur

0,,0 =−∞== kzl

Langkah 2

Selesaikan permasalahan linear awal dengan daerah layak permasalahan ke-0,

yaitu 0LP

Bentuk standarnya adalah

Maksimalkan

00045 2121 =−−−− ssxxz

28

Kendala

456105

221

121

=++=++

sxxsxx


00045451061050111

2121

−−

RHSssxx

Dengan menggunakan metode simpleks pada bagian B maka diperoleh

penyelesaian optimal untuk masalah di atas adalah:

25.175.375.23

2

1

0

===

xxz

75.2325.05.20075.315.05.10125.125.05.210

2121

−−

RHSssxx

Karena terdapat nilai variabel yang tidak bulat maka lanjut ke langkah ke-3

Langkah 3

Ambil variabel yang bukan bilangan bulat yaitu 1x , lalu bentuk permasalahan

linear baru lainnya dengan daerah layaknya adalah:

43

102

101

≥+=≤+=

xLPLPxLPLP

Langkah 4

Ubah

2

1==

kl

Langkah 5

Karena kl ≤ , maka kembali ke langkah ke-2

29

Iterasi 2

Langkah 2


yaitu 1LP Bentuk standarnya adalah


Maksimalkan

000045 32121 =−−−−− sssxxz

Kendala

3

456105

31

221

121

=+=++=++

sxsxxsxx


000045310001

45010610500111

32121

−−

RHSsssxx

Dengan menggunakan metode simpleks pada bagian A maka diperoleh


2323

2

1

1

===

xxz

2310400310001341600210110

32121

−−−

RHSsssxx

Karena semua nilai variabel bilangan bulat dan zz >1 maka ubah 2,23 == lz

dan lanjutkan ke langkah ke-5

30

Langkah 5


Iterasi 3

Langkah 2


yaitu 2LP


Maksimalkan

000045 32121 =−−−−− sssxxz

Kendala

4

456105

31

221

121

−=+−=++=++

sxsxxsxx


000045410001

45010610500111

32121

−−−−

RHSsssxx

Dengan menggunakan metode dual simpleks pada bagian C maka diperoleh


31

83.0433.23

2

1

2

===

xxz

33.23667.1667.0000410001

833.0667.1167.0010167.0667.0167.0100

32121

−−−

−−RHSsssxx


Langkah 3



10

224

223

≥+=≤+=

xLPLPxLPLP

Langkah 4

Ubah

4

3==

kl

Langkah 5


Iterasi 4

Langkah 2


yaitu 3LP


Maksimalkan

0000045 432121 =−−−−−− ssssxxz

32

Kendala

04

456105

42

31

221

121

=+−=+−

=++=++

sxsxsxxsxx


000004501000104010001

4500106105000111

432121

−−

−−

RHSssssxx

Dengan menggunakan metode dual simpleks pada bagian C maka diperoleh


05.45.22

2

1

3

===

xxz

5.22105.000001000005.46.001.00015.06.011.00005.04.001.0100

432121

−−

−−−−

RHSssssxx


Langkah 3



54

136

135

≥+=≤+=

xLPLPxLPLP

Langkah 4

Ubah

33

64

==

kl

Langkah 5


Iterasi 5

Langkah 2


yaitu 4LP


Maksimalkan

0000045 432121 =−−−−−− ssssxxz

Kendala

14

456105

42

31

221

121

−=+−−=+−

=++=++

sxsxsxxsxx


000004511000104010001

4500106105000111

432121

−−−−−−

RHSssssxx

Karena untuk nilai minimum 41 =x dan 12 =x tidak memenuhi kendala kedua,

maka persamaan linear ke-4 tidak mempunyai penyelesaian, maka ubah 5=l dan

lanjut ke langkah ke-5

34

Langkah 5


Iterasi 6

Langkah 2


yaitu 5LP


Maksimalkan

00000045 5432121 =−−−−−−− sssssxxz

Kendala

404

456105

51

42

31

221

121

=−=+

−=+−=++=++

sxsxsxsxxsxx


00000045410000010010001040010001

450001061050000111

5432121

−−

−−

RHSsssssxx

Dengan menggunakan metode dual simpleks pada bagian C maka diperoleh untuk

masalah di atas adalah:

35

04

20

2

1

5

===

xxz

20540000001010000001000104100000151060100014100100

5432121

−−

−−−−

RHSsssssxx

Karena mempunyai solusi bilangan bulat dengan 235 <z , maka ubah 6=l dan


Langkah 5


Iterasi 7

Langkah 2

Selesaikan permasalahan linear awal dengan 6LP , yaitu daerah layak

permasalahan ke-6


Maksimalkan

00000045 5432121 =−−−−−−− sssssxxz

Kendala

504

456105

51

42

31

221

121

−=−−=+

−=+−=++=++

sxsxsxsxxsxx

36


00000045510000010010001040010001

450001061050000111

5432121

−−−−

−−

RHSsssssxx

Karena untuk nilai minimum 51 =x tidak memenuhi kendala kedua, maka

permasalahan ke-6 tidak mempunyai penyelesaian, maka ubah 7=l dan lanjut ke

langkah ke-5

Langkah 5

Karena kl > , maka perhitungan dihentikan dan nilai optimum untuk

permasalahan linear (2.4.1) adalah 23=z dengan 31 =x dan 22 =x .

E. Metode Cutting plane

Pada bab sebelumnya telah dijelaskan bagaimana menyelesaikan sebuah

program linear bilangan bulat dengan menggunakan metode branch-and-bound.

Selain menggunakan metode branch-and-bound, dapat juga menggunakan metode

cutting plane. Sama seperti dengan metode branch-and-bound, metode cutting

plane juga berawal dari penyelesaian optimal program linear. Sebuah kendala

khusus yang ditambahkan, disebut cuts, pada daerah layak dengan tujuan

membuang titik optimal yang bukan bilangan bulat sehingga menghasilkan

sebuah penyelesaian bilangan bulat yang optimal.

37

Cara kerja dari metode cutting plane adalah dengan mencari penyelesaian optimal

dari program linear dalam bentuk standar dengan daerah layak awal ( 0LP ) dan

melihat apakah terdapat variabel yang bukan bilangan bulat. Jika terdapat variabel

yang bukan bilangan bulat, maka akan dibentuk sebuah program linear dengan

daerah layak baru ( 1LP ), yaitu dengan menambahkan sebuah kendala baru (cuts).

Lalu mencari penyelesaian optimal program linear baru ini.

Definisi 2.5.1

Kendala cuts adalah kendala yang dibentuk dengan memisahkan semua koefisien

fraksional pada salah satu baris di tabel optimal yang RHS bukan bilangan di ruas

kanan dan koefisien bulat di ruas kiri persamaan dan mememenuhi dua syarat,

yaitu

1. sembarang titik penyelesaian untuk program linear bilangan bulat memenuhi

kendala baru.

Kendala cuts yang baru merupakan bagian fraksional dari sebuah kendala pada

tabel optimal yang berbentuk ∑∑==

−=−n

iijijj

n

iiji xffbxa

11. Untuk sembarang

penyelesaian bilangan bulat, ruas kanan akan selau bernilai bulat dan karena

0,1 ≥< ij xf , maka ruas kanan pada persamaan di atas haruslah bilangan bulat

yang lebih kecil dari 1, yaitu 01

≤−∑=

n

iijij xff .

2. penyelesaian optimal yang didapat sebelumnya akan tidak memenuhi kendala

baru.

38

Karena kendala cuts ini dibentuk dari sebuah baris pada tabel optimal dan pada

satu baris hanya terdapat satu variabel dasar, maka ix∀ , ix adalah variabel non-

dasar yang nilainya adalah 0. maka jika penyelesaian optimal yang didapat

dimasukkan pada kendala cuts,

0

001

≤

≤−∑=

j

n

ijij

f

ff

Hal ini bertentangan dengan 10 <≤ jf , maka penyelesaian optimal yang didapat

sebelumnya tidak akan memenuhi kendala cuts ini.

Secara umum algoritma cutting plane dapat ditulis dalam langkah-

langkah berikut ini:

1. Atur 0=k

2. Selesaikan permasalahan dengan menggunakan kLP , yaitu daerah layak

permasalahan ke-k

i. Jika semua variabel bernilai bulat, maka didapat penyelesaian

optimal untuk program linear awal.

ii. Jika terdapat variabel yang bukan bilangan bulat, maka lanjut ke

langkah berikutnya.

3. Ambil sembarang kendala, kendala ke-j pada tabel optimal kLP yang RHS-

nya bukan bilangan bulat.

4. Ubah semua koefisien pada persamaan yang diambil pada langkah ke-3 dalam

bentuk

39

( ) jj

n

iijiji fbxfa +=+∑

=1 (2.5.1)

dimana 1,0 <≤ jij ff , K,2,1=i

5. Bentuk persamaan pada langkah ke-4 menjadi

∑∑==

−=−n

iijijj

n

iiji xffbxa

11.

6. Bentuk kendala baru (cuts), yaitu 01

≤−∑=

n

iijij xff .

7. Ubah 1+= kk dan kembali ke langkah ke-2.

Algoritma tersebut dapat digambarkan dalam flow chart berikut.

0=k

jj

n

ijiji fbfd +=+∑

=1

01

≤−∑=

n

ijij ff

1+= kk

kLP

Gambar 2.5.1. Algoritma Metode Cutting plane.

40

Berikut diberikan contoh penerapan metode cutting plane pada

permasalahan pemrograman linear adalah

Contoh 2.5.1

Maksimalkan

21 45 xxz +=

Kendala

+Ζ∈

≤+≤+

21

21

21

,

456105

xx

xxxx

Penyelesaian

Iterasi 1

Langkah 1

Atur 0=k

Langkah 2


yaitu 0LP


Maksimalkan

00045 2121 =−−−− ssxxz

Kendala

456105

221

121

=++=++

sxxsxx

41


00045451061050111

2121

−−

RHSssxx

Dengan menggunakan metode simpleks pada bagian A maka diperoleh untuk


25.175.375.23

2

1

0

===

xxz

75.2325.05.20075.315.05.10125.125.05.210

2121

−−

RHSssxx

Langkah 3

Ambil kendala yang tidak bulat, yaitu kendala ke-1.

Langkah 4

Ubah kendala ke-1 menjadi

2501750502 22112 ... +=+−++ ssssx

Langkah 5

Bentuk persamaan pada langkah ke-4 menjadi

21212 7505025012 ssssx ... −−=−−+

Langkah 6

Bentuk kendala baru yaitu

075050250 21 ≤−− ss ...

Langkah 7

Ubah 1=k .

42

Iterasi 2

Langkah 2


yaitu 1LP


Maksimalkan

000045 32121 =−−−−− sssxxz

Kendala

25.075.05.0456105

321

221

121

−=+−−=++=++

ssssxxsxx


00004525.0175.05.00045010610500111

32121

−−−−−

RHSsssxx



3333166673666723

2

1

0

.

..

===

xxz

667.23333.00333.200333.1333.00667.210667.3333.00667.101333.0333.11667.000

32121

−−

−RHSsssxx

Langkah 3


43

Langkah 4


3333066670266670 3321 ... =+−+ ssss

Langkah 5


3132 6667066670333302 ssss ... −−=−

Langkah 6


0666706667033330 31 ≤−− ss ...

Langkah 7

Ubah 2=k .

Iterasi 3

Langkah 2


yaitu 2LP


Maksimalkan

0000045 432121 =−−−−−− ssssxxz

44

Kendala

333.0667.0667.025.075.05.0456105

431

321

221

121

−=+−−−=+−−

=++=++

sssssssxxsxx


0000045333.01667.00667.00025.00175.05.0004500106105000111

432121

−−−−−−−−

RHSssssxx



5153523

2

1

0

.

..

===

xxz

5.235.00020012012005.15.0003105.35.0002015.05.110100

432121

−−

−−

RHSssssxx

Langkah 3


Langkah 4


50502 4431 .. =+−+ ssss

Langkah 5


45

4431 50502 ssss .. −=−+

Langkah 6


05050 4 ≤− s..

Langkah 7

Ubah 3=k .

Iterasi 4

Langkah 2


yaitu 3LP


Maksimalkan

00000045 5432121 =−−−−−−− sssssxxz

Kendala

5.05.0333.0667.0667.025.075.05.0456105

54

431

321

221

121

−=+−−=+−−−=+−−

=++=++

sssssssssxxsxx

46


000000455.015.000000

333.001667.00667.00025.000175.05.0004500010610

500001115432121

−−−−

−−−−−−

RHSsssssxx



2323

2

1

0

===

xxz

2310002003100020112100000230101003400120021000310

5432121

−−−−−

RHSsssssxx

Karena semua variabel merupakan bilangan bulat, maka penyelesaian optimal

untuk persamaan linear (2.5.1) adalah 23=z dengan 31 =x dan 22 =x .

BAB III

METODE BRANCH-AND-CUT PADA PERMASALAHAN RUTE

KENDARAAN BERKAPASITAS

A. Permasalahan Rute Kendaraan Berkapasitas (Capacitated Vehicle

Routing Problems - CVRP)

Terdapat banyak kegunaan dari penggunaan riset operasi dalam

kehidupan sehari-hari, dan yang sering dipakai oleh perusahaan-perusahaan

adalah permasalahan pengoptimalan. Pengoptimalan yang berbasis pada program

linear dengan permasalahan perencanaan pengiriman dari produsen kepada

konsumen inilah yang disebut Permasalahan Rute Kendaraan (Vehicle Routing

Problem – VRP). Permasalahan rute kendaraan mempunyai beberapa bentuk dasar

permasalahan, yaitu permasalahan rute kendaraan berkapasitas (Capacitated VRP

– CVRP), yang merupakan bentuk paling dasar dari permasalahan pada VRP,

distance-constained VRP, VRP dengan Time Windows, VRP dengan Backhauls

dan VRP dengan Pickup and Delivery.

Capacitated VRP adalah sebuah bentuk dasar permasalahan rute

kendaraan berkapasitas dengan tambahan kendala khusus, yaitu kendaraan yang

digunakan identik, hanya terdapat satu sumber, dan adanya batasan kapasitas pada

kendaraan yang digunakan dan tujuannya adalah untuk meminimalkan total

pengeluaran.

48

Definisi 3.1.1

Graf adalah sebuah jaringan yang terdiri dari himpunan simpul-simpul dan

himpunan busur-busur.

Definisi 3.1.2

Graf berarah adalah graf yang busur-busurnya mempunyai arah, dengan kata

lain busur ( )ji, , yaitu busur yang menghubungkan simpul i dengan simpul j, tidak

sama dengan busur ( )ij, .

Definisi 3.1.3

Rute dari simpul i ke simpul j adalah suatu urutan simpul ji ,,K

bersama-sama dengan himpunan busur yang menghubungkan simpul pertama

dengan simpul kedua, simpul kedua dengan simpul ketiga, sampai dengan simpul

terakhir.

Secara umum CVRP dapat digambarkan dengan menggunakan graf,

dengan ( )AVG ,= , dimana { }nV ,,0 L= adalah himpunan simpul-simpul dan A

adalah himpunan jalan-jalan yang dapat dilalui. Simpul ni ,...,1= melambangkan

konsumen, { }0\0 VV = , sedangkan simpul 0 melambangkan sumber dan terdapat

bilangan nonnegatif jic untuk setiap rute Aji ∈),( yang melambangkan biaya

yang diperlukan dari simpul i menuju simpul j. Secara umum berjalan dari simpul

i menuju simpul i tidak diperbolehkan. Untuk menghindari hal ini didefinisikan

49

+∞=iic untuk semua Vi∈ . Jika G merupakan graf berarah, maka jiij cc ≠ .

Sebaliknya jika jiij cc = untuk semua Aji ∈),( , maka secara umum himpunan A

digantikan dengan himpunan busur-busur tak berarah, E. Banyaknya jumlah

anggota himpunan E dinyatakan dengan notasi E .

Sebanyak K kendaraan identik yang masing-masing berkapasitas C

dipakai untuk memenuhi setiap permintaan konsumen, ),,1(, nidi K= , dimana

Cdi ≤<0 . Setiap konsumen hanya dilayani oleh satu kendaaran saja dan sebuah

kendaaran tidak dapat melayani beberapa konsumen yang total permintaannya

melebihi kapasitas kendaraan.

Untuk sembarang himpunan 0VS ⊆ , didefinisikan:

1) )(Sd adalah jumlah semua permintaan pada S, ( ) ∑∈

=Si

idSd ,

2) ( )Sδ adalah himpunan busur-busur di E yang tepat satu salah satu titik

ujungnya berada di S ,

3) ( )SE adalah himpunan busur-busur di E yang kedua titik ujungnya

berada di S ,

4) ( )Sr adalah banyaknya kendaraan minimum yang dipakai untuk melayani

semua konsumen di S , ( ) ( )C

SdSr = .

5) ex menunjukkan berapa kali busur Ee∈ dilewati oleh kendaraan.

50

Secara umum CVRP dapat dirumuskan menjadi:

( )( )( )( )( )( ) ( )

{ } ( )( ){ } ( )( )0\1,0

02,1,0)(2

20,,2,12

0

δδ

δδδ

Eexex

VSSrSxKx

niixKendala

xcMin

e

e

Eeee

∈∈∈∈⊆≥

===

∑∈

K

( )5.1.3)4.1.3()3.1.3()2.1.3()1.1.3(

Kendala (3.1.3) pada umumnya disebut dengan pertidaksamaan kapasitas

(capacity inequalities) dan kendala (3.1.1), sering disebut sebagai persamaan

derajat (degree equations) dan menjamin bahwa setiap konsumen dilayani tepat

satu kali. Kendala (3.1.2) memastikan bahwa tepat memakai K kendaraan.

Kendala (3.1.3) dan (3.1.4) merupakan syarat bilangan bulat. Pada kendala (3.1.4)

ex mungkin bernilai 2 jika terdapat rute yang langsung menghubungkan depot

dan konsumen. Dengan menggunakan rumusan di atas, permasalahan CVRP

mempunyai En +2 kendala.

Definisi 3.1.4

Misalkan himpunan S mempunyai n elemen. Banyaknya himpunan bagian S yang

terdiri dari ( )nrr ≤, , disebut kombinasi n objek yang diambil sebanyak r objek

sekaligus. Disimbolkan

rn

, ( )rnC , , atau rn C . Banyaknya kombinasi yang

dimaksud dapat dinyatakan dalam persamaan ( )!!!

rnrn

rn

−=

51

Teorema 3.1.5

+

−

=

+rn

rn

rn

11

nrr ≤<∀ 0,

Bukti:

( ) ( )( ) ( )

( ) ( )( ) ( ) ( )

( ) ( )( )( ) ( ) ( )( )( )

( ) ( )( )( )

( )( )

( )( )( )

( )( )( )( )( )

+=

−++

=

+−+

=

+−+

=

+−+−+

=

−+−−+−+

=

−−+

−+−−=

−−+

+−−=

−+

−−−=

+

−

rn

rnrn

rnrnn

rnrnnnrnr

nrnnnrnrnrnrr

rnnrnrnrr

nrnrnr

nrnrr

nrnr

nrnr

nrnr

nrn

rn

1!1!

!1!1!

1!!1!

!!!1!

!!!!!1!1

1!!!!1

!!1!1

!!!1

!!1!1

!!!

!!1!1

!1

■

Teorema 3.1.6

nn

r rn

20

=

∑=

Bukti

Bukti dengan menggunakan induksi matematis:

1. untuk 0=n

52

0

0

0

2

1

11

!0!0!0

000

=

=

=

=

=

∑=r r

Benar untuk 0=n .

2. Andaikan benar untuk kn = kk

r rk

20

=

∑=

3. Akan dibuktikan benar untuk 1+= kn

[ ] [ ]

1

1

0

2

22

22

112121

11

022

01

11

2111001

11

1211001

111

21

11

011

+

+

=

=

×=

+=

+−+−+=

++

+

−+

−+

+=

++

+

++

+

+

−

++

+

+

+=

++

+

+

−

++

+

+

+

+

+=

++

+

+++

++

++

+=

+∑

k

k

kk

kk

kk

k

r

kkk

kkk

kk

kkkk

kkkkk

kk

kk

kkkkkkk

kk

kkkkk

rk

KK

K

K

■

53

Teorema 3.1.7

Jumlah kendala pada permasalahan rute kendaraan berkapasitas (CVRP) di atas

adalah mn +2 , dengan n adalah konsumen simpul dan m adalah banyaknya rute

yang ada.

Bukti:

Perhatikan bahwa:

i. persamaan (3.1.1) mempunyai sebanyak n kendala atau dapat ditulis

1n

.

ii. persamaan (3.1.2) hanya mempunyai 1 kendala saja atau

0n

iii. persamaan (3.1.3) mempunyai kendala sebanyak ∑=

n

r rn

2.

Jumlah kendala pada persamaan (3.1.4) dan (3.1.5) adalah sebanyak m . Maka

jumlah dari semua kendala adalah

m

mrn

mrnnn

n

n

r

n

r

+=

+

=+

+

+

∑∑==

2

01 02 .

■

Terdapat beberapa metode untuk menyelesaikan CVRP, yaitu dengan

menggunakan metode branch-and-bound, metode branch-and-cut, metode set

covering, metode classical heuristic, dan metode metaheuristic, dan lain

sebagainya. Dalam bab selanjutnya akan dibahas cara penggunaan metode

branch-and-cut.

54

B. Metode Branch-and-cut

Pada bab ini akan dibahas mengenai penggunaan metode branch-and-cut

untuk menyelesaikan program linear bilangan bulat. Metode branch-and-cut

merupakan gabungan dari dua metode, yaitu metode branch-and-bound dan

cutting plane. Kata branch pada metode branch-and-cut menandakan adanya

sebuah percabangan seperti pada metode branch-and-bound. Sedangkan kata cut

menunjukkan adanya tambahan kendala cuts seperti pada metode cutting plane.

Cara kerja metode branch-and-cut sama dengan metode branch-and-

bound, tetapi terdapat perbedaan pada saat percabangannya. Pada metode branch-

and-cut, kendala cuts ditambahkan sebelum terjadi percabangan, sehingga daerah

layak untuk permasalahan linear yang baru adalah illk xcutsLPLP ++=+1 dan

illk xcutsLPLP ++=+2 , K,3,2,1=l , K6,4,2,0=k

Secara umum algoritma branch-and-cut dapat ditulis dalam langkah-

langkah berikut:

1. Atur 0,,0 =−∞== kzl

2. Selesaikan permasalahan dengan menggunakan lLP , yaitu daerah layak

permasalahan ke-l

iv. Jika semua variabel bilangan bulat dan zzl ≥ , maka ubah


v. Jika ada variabel yang bukan bilangan bulat lanjutkan ke langkah ke-3

55

vi. Jika lLP tidak mempunyai daerah layak atau mempunyai penyelesaian

bilangan bulat dengan zzl ≤ , maka ubah 1+= ll dan lanjutkan ke

langkah ke-9

8. Ambil sembarang kendala, kendala ke-j pada tabel optimal lLP yang RHS-nya

bukan bilangan bulat.

9. Ubah semua koefisien pada persamaan yang diambil pada langkah ke-3 dalam

bentuk

( ) jj

n

iijiji fbxfa +=+∑

=1 (3.2.1)

dimana 1,0 <≤ jij gf , K,2,1=i

10. Bentuk persamaan pada langkah ke-4 menjadi

∑∑==

−=−n

iijijj

n

iiji xffbxa

11.

11. Bentuk kendala baru ( lcuts ), yaitu 01

≤−∑=

n

iijij xff .

7. Ambil salah satu variabel ix yang bukan bilangan bulat dan bentuk

permasalahan linear baru lainnya dengan daerah layaknya adalah LPk+1 dan

LPk+2 dimana

( ) ( ) liilk

liilk

cutsxxLPLPcutsxxLPLP

+≥+=+≤+=

+

+

2

1

8. Ubah 1+= ll dan 2+= kk

9. Jika kl > perhitungan berhenti, jika tidak kembali ke langkah ke-2.

56

Sama dengan metode branch-and-bound, algoritma di atas dipakai untuk

permasalahan pemaksimalan, untuk permasalahan peminimalan pemrograman

linear bilangan bulat, cukup mengganti nilai awal ,+∞=z dan pada langkah ke-2

diubah menjadi:

3. Selesaikan permasalahan dengan menggunakan lLP , yaitu daerah

layak permasalahan ke-l

iv. Jika semua variabel bilangan bulat dan zzl ≤ , maka ubah


v. Jika ada variabel yang bukan bilangan bulat lanjutkan ke

langkah ke-3

vi. Jika lLP tidak mempunyai daerah penyelesaian atau

mempunyai penyelesaian bilangan bulat dengan zzl ≥ , maka

ubah 1+= ll dan lanjutkan ke langkah ke-9

57

−∞===

zkl

00

iilk

iilk

xxLPLPxxLPLP

≥+=≤+=

+

+

2

1

21+=+=

kkll

1+= ll

zzl >

kl >

1+==

llzz l

lLP

lcuts

Gambar 3.2.1. Algoritma Metode Branch-and-cut.

Berikut diberikan contoh penerapan metode branch-and-cut pada permasalahan

pemrograman linear adalah

Contoh 3.2.1

Maksimalkan

21 45 xxz +=

58

Kendala

+Ζ∈

≤+≤+

21

21

21

,

456105

xx

xxxx

Penyelesaian

Iterasi 1

Atur

0,,0 =−∞== kzl

Langkah 2


yaitu 0LP


Maksimalkan

00045 2121 =−−−− ssxxz

Kendala

456105

221

121

=++=++

sxxsxx


00045451061050111

2121

−−

RHSssxx

Dengan menggunakan metode simpleks pada Bab II maka diperoleh penyelesaian

optimal untuk masalah di atas adalah:

59

25.175.375.23

2

1

0

===

xxz

75.2325.05.20075.315.05.10125.125.05.210

2121

−−

RHSssxx


Langkah 3


Langkah 4


2501750502 22112 ... +=+−++ ssssx

Langkah 5


21212 7505025012 ssssx ... −−=−−+

Langkah 6

Bentuk kendala baru ( 0cuts ) yaitu

075050250 21 ≤−− ss ...

Langkah 7



( ) ( )( ) ( )4

3

1002

1001

≥++=

≤++=

xcutsLPLPxcutsLPLP

Langkah 8

Ubah

60

2

1==

kl

Langkah 9


Iterasi 2

Langkah 2


yaitu 1LP


Maksimalkan

0000045 432121 =−−−−−− ssssxxz

Kendala

325.075.05.0456105

41

321

221

121

=+−=+−−

=++=++

sxssssxxsxx


00000453100001

25.00175.05.0004500106105000111

432121

−−

−−−

RHSssssxx

Dengan menggunakan metode dual simpleks pada Bab II maka diperoleh


61

2323

2

1

1

===

xxz

231004003100001231050034016002100110

432121

−−−−−

RHSssssxx



Langkah 9


Iterasi 3

Langkah 2


yaitu 2LP


Maksimalkan

0000045 432121 =−−−−−− ssssxxz

Kendala

425.075.05.0456105

41

321

221

121

−=+−−=+−−

=++=++

sxssssxxsxx

62


00000454100001

25.00175.05.0004500106105000111

432121

−−−−

−−−

RHSssssxx



80

4223

2

1

2

.

.

===

xxz

2.234.18.0000041000018.06.12.000102.04.02.110002.06.02.00100

432121

−

−−−

RHSssssxx


Langkah 3


Langkah 4


2.04.08.0 44331 =+−+− sssss

Langkah 5


43431 4.08.02.0 sssss −−=−−

Langkah 6


63

04.08.02.0 43 ≤−− ss

Langkah 7



( ) ( )( ) ( )1

0

2224

2223

≥++=

≤++=

xcutsLPLPxcutsLPLP

Langkah 8

Ubah

4

3==

kl

Langkah 9


Iterasi 4

Langkah 2


yaitu 3LP


Maksimalkan

000000045 65432121 =−−−−−−−− ssssssxxz

64

Kendala

02.04.08.04

25.075.05.0456105

62

543

41

321

221

121

=+−=+−−−=+−

−=+−−=++=++

sxssssxssssxxsxx


0000000450000000102.0014.08.00000400100001

25.0000175.05.00045000010610500000111

65432121

−−

−−−−−

−−−

RHSssssssxx



05.45.22

2

1

3

===

xxz

5.22667.0833.00000000100000100667.0667.10010005.4667.0167.00000010333.0333.10100005.0667.0167.01000005.0333.0167.0000100

65432121

−−

−−

−−−−

RHSssssssxx


Langkah 3


65

Langkah 4


5.0666.0833.0 66551 =+−+− sssss

Langkah 5


65651 666.0833.05.0 sssss −−=−−

Langkah 6


0666.0833.05.0 65 ≤−− ss

Langkah 7



( ) ( )( ) ( )5

4

1236

1235

≥++=≤++=

xcutsLPLPxcutsLPLP

Langkah 8

Ubah

64

==

kl

Langkah 9


66

Iterasi 5

Langkah 2


yaitu 4LP


Maksimalkan

000000045 65432121 =−−−−−−−− ssssssxxz

Kendala

12.04.08.04

25.075.05.0456105

62

543

41

321

221

121

−=+−−=+−−−=+−

−=+−−=++=++

sxssssxssssxxsxx


0000000451000000102.0014.08.00000400100001

25.0000175.05.00045000010610500000111

65432121

−−−−

−−−−−

−−−

RHSssssssxx

Karena untuk nilai minimum 41 =x dan 12 =x tidak memenuhi kendala kedua,

maka persamaan linear ke-4 tidak mempunyai penyelesaian, maka ubah 5=l dan


67

Langkah 9


Iterasi 6

Langkah 2


yaitu 5LP


Maksimalkan

00000000045 8765432121 =−−−−−−−−−− ssssssssxxz

Kendala

45.0666.0833.002.04.08.04

25.075.05.0456105

81

765

62

543

41

321

221

121

=+−=+−−

=+−=+−−−=+−

−=+−−=++=++

sxssssxssssxssssxxsxx


68

00000000045410000000015.001666.0833.0000000000100000102.000014.08.0000040000100001

25.000000175.05.0004500000010610

500000001118765432121

−−

−−−

−−−−−

−−−

RHSssssssssxx



04

20

2

1

3

===

xxz

0000000004501000100000251400000000001000001036041000000410000000014805001000051006000100011010000100

8765432121

−−

−−

−−

−−−−−−

RHSssssssssxx

Karena semua nilai variabel bilangan bulat, ubah 6=l dan lanjutkan ke langkah

ke-9

Langkah 9


69

Iterasi 7

Langkah 2


yaitu 6LP


Maksimalkan

00000000045 8765432121 =−−−−−−−−−− ssssssssxxz

Kendala

55.0666.0833.002.04.08.04

25.075.05.0456105

81

765

62

543

41

321

221

121

−=+−−=+−−

=+−=+−−−=+−

−=+−−=++=++

sxssssxssssxssssxxsxx


00000000045510000000015.001666.0833.0000000000100000102.000014.08.0000040000100001

25.000000175.05.0004500000010610

500000001118765432121

−−−−

−−−

−−−−−

−−−

RHSssssssssxx

70

Karena untuk nilai minimum 51 =x tidak memenuhi kendala kedua, maka

persamaan linear ke-6 tidak mempunyai penyelesaian, maka ubah 7=l dan lanjut

ke langkah ke-9

Langkah 9


permasalahan linear (3.2.1) adalah 23=z dengan 31 =x dan 22 =x .

Contoh 3.2.2

Terdapat 4 konsumen yang akan dilayani dengan menggunakan dua buah

kendaraan, yang mempunyai kapasitas 25. Jarak konsumen dari sumber dan

permintaannya ada pada gambar di bawah ini.

Dengan memisalkan 1x adalah busur yang menghubungkan simpul 0 dan 1, 2x

adalah busur yang menghubungkan simpul 0 dan 2, 3x adalah busur yang

menghubungkan simpul 0 dan 3, 4x adalah busur yang menghubungkan simpul 1

71

dan 4, 5x adalah busur yang menghubungkan simpul 2 dan 4, dan 6x adalah busur

yang menghubungkan simpul 3 dan 4 maka darii permasalahan di atas, dapat

dibentuk permasalahan linearnya menjadi

Minimumkan

654321 41210254 xxxxxxz +++++=

Kendala

kendala pada persamaan (3.1.1)

2222

654

63

52

41

=++=+=+=+

xxxxxxxxx


4321 =++ xxx


8.22

16.22

24.236.1

2.144.136.1

6.144.1

321

432

531

621

654321

543

642

6532

651

6431

5421

≥++≥++≥++≥++≥+++++≥++≥++≥+++≥++≥+++≥+++

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx


[ ]2,0,, 321 ∈xxx

72


[ ]1,0,, 654 ∈xxx

Penyelesaian

Dengan mengubah kendala menjadi pertidaksamaan ≤ dan menambahkan

sebanyak 16 variabel pengetat maka permasalahan di atas siap untuk diselesaikan

menggunakan metode branch-and-cut.

Iterasi 1

Langkah 1

Atur

0,,0 =−∞== kzl

Langkah 2


yaitu 0LP

Dengan menggunakan metode dual simpleks pada Bab II maka diperoleh untuk


108.092.0192.108.108.30

6

5

4

3

2

1

0

=======

xxxxxxz

08.300000001000100

92.000100008.0010000

110000092.100001008.1000001

654321 RHSxxxxxx


73

Langkah 3


Langkah 4


08.015.05.05.0 2721171784421 +=+++−++−− ssssssssx

Langkah 5


2117427178421 5.05.05.008.01 ssssssssx −−−=−+−+−−

Langkah 6


05.05.05.008.0 21174 ≤−−− sss

Langkah 7



( ) ( )( ) ( )1

2

1002

1001

≤++=≥++=

xcutsLPLPxcutsLPLP

Langkah 8

Ubah

2

1==

kl

Langkah 9


74

Iterasi 2

Langkah 2


yaitu 1LP



11011231

6

5

4

3

2

1

1

=======

xxxxxxz

3100300010001001010000110000020000011001010

654321

−

RHSxxxxxx



Langkah 9


Iterasi 3

Langkah 2


yaitu 2LP

Dengan menggunakan metode simpleks pada Bab II maka diperoleh untuk


75

84.016.0116.184.1108.30

6

5

4

3

2

1

2

=======

xxxxxxz

08.3000000016.100010016.001000084.0100000

100000184.1000010

1001000654321 RHSxxxxxx


Langkah 3


Langkah 4


84.012 8532282 +=+++−+ sssssx

Langkah 5


84.012 8532282 =−+++−+ sssssx

Langkah 6


084.0 ≤

Langkah 7



( ) ( )( ) ( )1

2

2224

2223

≤++=≥++=

xcutsLPLPxcutsLPLP

76

Langkah 8

Ubah

43

==

kl

Langkah 9


Iterasi 4

Langkah 2


yaitu 3LP

Karena terdapat batasan 2cuts yang tidak akan dipenuhi untuk semua variable

maka permasalahan ini tidak mempunyai penyelesaian. Ubah 4=l dan lanjut ke

langkah ke-9.

Langkah 9


Iterasi 5

Langkah 2

Karena terdapat batasan 2cuts yang tidak akan dipenuhi untuk semua variable

maka permasalahan ini tidak mempunyai penyelesaian. Ubah 5=l dan lanjut ke

langkah ke-9.

77

Langkah 9


permasalahan linear (3.2.2) adalah 31=z dengan 21 =x , 12 =x , 13 =x , 04 =x ,

15 =x , dan 16 =x .

Proposisi 3.2.1

Percabangan yang dibentuk oleh metode branch-and-cut lebih sederhana atau

sama dengan percabangan yang dibentuk oleh metode branch-and-bound.

Bukti:

Percabangan yang dibentuk oleh metode branch-and-bound hanya menambahkan

batasan pada ix saja, yakni ( )ii xx ≤ atau ( )ii xx ≥ , sedangkan pada metode

branch-and-cut pada setiap percabangan selain menambahkan batasan pada ix

juga menambahkan kendala cuts, yakni ( ) ( )cutsxx ii +≤ atau

( ) ( )cutsxx ii +≥ . Dengan adanya penambahan kendala cuts pada metode

branch-and-cut akan membuat daerah layak menjadi lebih kecil. Karena kendala

cuts tidak membuang semua solusi bilangan bulat (syarat 1), maka kendala cuts

membuang solusi bilangan tak bulat. Berarti metode branch-and-cut membuang

lebih banyak solusi bilangan tak bulat, sehingga membuat metode branch-and-cut

lebih cepat mendapatkan penyelesaian bilangan bulat. Karena untuk batasan ix ,

metode branch-and-cut lebih cepat mendapatkan penyelesaian bilangan bulat,

78

maka secara keseluruhan metode branch-and-cut membuat percabangan lebih

sederhana dari pada metode branch-and-bound.

■

C. Perbandingan Metode Branc- and-Cut, Cutting plane, dan Branc- and-

Bound.

Dalam bab ini akan dibahas tentang perbandingan antara metode branch-

and-cut, cutting plane, dan branch-and-bound dalam dua permasalahan yang telah

ada, yaitu permasalahan program linear bilangan bulat yang sederhana dan

permasalahan rute kendaraan berkapasitas. Pada contoh ( )1.4.2 , ( )1.5.2 , dan

( )1.2.3 telah didapat hasil-hasil setiap iterasinya, dan jika ditulis dalam tabel

menjadi:

nfsnfsnfs

nfsnfsnfsxxzxxz

nfsnfsnfs

nfsnfsnfsxxzxxzxxzxxzxxz

BnCCPBnB

−−−−−−−−−

21212121212121

7

0420

0420

65

05.45.22232305,45,22

4

8,042,235,15,35,2383,04333,23

3

232333,1667,3667,232323

2

25,175,375,2325,175,375,2325,175,375,23

1

Metode

Iterasi

Dengan nfs adalah tidak adanya daerah layak, atau tidak mempunyai penyelesaian.

Dan penyelesaian untuk permasalahan rute berkapasitas adalah sebagai berikut:

1. Branch-and-Bound

• Iterasi 1

79

108.092.0192.108.108.30

6

5

4

3

2

1

0

=======

xxxxxxz

08.300000001000100

92.000100008.0010000

110000092.100001008.1000001

654321 RHSxxxxxx

• Iterasi 2

11011231

6

5

4

3

2

1

0

=======

xxxxxxz

31000000101000010001000001000110000010000102000001

654321 RHSxxxxxx

• Iterasi 3

92.008.0108.192.1104.30

6

5

4

3

2

1

0

=======

xxxxxxz

04.3000000008.1000100

100100008.001000092.010000092.1000010

1000001654321 RHSxxxxxx

• Iterasi 4

Tidak mempunyai penyelesaian di Iterasi ke-4.

• Iterasi 5

80

01121135

6

5

4

3

2

1

0

=======

xxxxxxz

35000000101000020001001001000010000010000101000001

654321 RHSxxxxxx

2. Cutting plane

• Iterasi 1

108.092.0192.108.108.30

6

5

4

3

2

1

0

=======

xxxxxxz

08.300000001000100

92.000100008.0010000

110000092.100001008.1000001

654321 RHSxxxxxx

• Iterasi 2

64.016.084.0184.116.116.30

6

5

4

3

2

1

0

=======

xxxxxxz

08.3000000016.100010016.001000084.0100000

100000184.1000010

1001000654321 RHSxxxxxx

• Iterasi 3

Tidak mempunyai penyelesaian, maka permasalahan diatas tidak dapat

diselesaikan dengan metode Cutting plane.

81

3. Branch-and-Cut

• Iterasi 1.

108.092.0192.108.108.30

6

5

4

3

2

1

0

=======

xxxxxxz

08.300000001000100

92.000100008.0010000

110000092.100001008.1000001

654321 RHSxxxxxx

• Iterasi 2.

11011231

6

5

4

3

2

1

0

=======

xxxxxxz

3100300010001001010000110000020000011001010

654321

−

RHSxxxxxx

• Iterasi 3.

84.016.0116.184.1108.30

6

5

4

3

2

1

0

=======

xxxxxxz

16.100010084.001000016.0100000

100000184.1000010

1001000654321 RHSxxxxxx

• Iterasi 4

Tidak mempunyai penyelesaian di iterasi ke-4.

82

• Iterasi 5

Tidak mempunyai penyelesaian di iterasi ke-5.

Dari dua contoh di atas akan dibandingkan hasil ketiga metode yang telah

dibahas.

1. Metode Branch-and-Bound.

Yang menjadi kekurangan metode branch-and-bound pada kedua contoh

di atas adalah banyaknya iterasi yang diperlukan untuk mencari hasil optimal.

Tetapi jika dibandingkan dengan metode cutting plane, metode branch-and-

bound lebih mudah digunakan karena metode branch-and-bound tidak perlu

membangun kendala cuts dan jika disalah satu iterasi tidak mempunyai

penyelesaian, masih terdapat kemungkinan mencari solusi optimal dari

permasalahan di atas seperti pada contoh permasalahan program linear bilangan

bulat di atas..

2. Metode Cutting plane.

Dalam permasalahan program linear bilangan bulat, metode cutting

plane membutuhkan dua tambahan kendala baru, 1cuts , 2cuts , dan 3cuts , untuk

mendapatkan hasil optimal (4 iterasi). Tetapi dalam permasalahan rute kendaraan

berkapasitas di atas, metode cutting plane tidak dapat menyelesaikannya. Hal ini

disebabkan karena untuk setiap elemen matriks koefisien pada tabel optimal dari

iterasi kedua merupakan bilangan bulat, sehingga tidak dapat dibangunnya

kendala cuts yang baru dan menyebabkan metode cutting plane tidak dapat

diterapkan untuk permasalahan rute kendaaran berpakasitas diatas.

83

3. Metode Branch-and-Cut.

Dalam kedua permasalahan diatas, metode branch-and-cut menghasilkan

solusi yang baik. Dari sudut pandang iterasi, metode branch-and-cut lebih sedikit

dari pada dengan metode branch-and-bound, dan dalam permasalahan program

linear bilangan bulat, metode branch-and-cut juga hanya memerlukan tiga

tambahan kendala cuts . Jika dibandingkan dengan metode cutting plane, metode

branch-and-cut dapat diterapkan pada permasalahan rute kendaraan berkapasitas.

Walaupun kendala 2cuts tidak dapat dibangun, yang menghasilkan iterasi

keempat dan kelima tidak mempunyai penyelesaian, metode branch-and-cut

dapat mencari solusi optimal dari percabangan yang lain.

BAB IV

APLIPAKSI METODE BRANCH-AND-CUT DALAM MASALAH

PENDISTRIBUSIAN BUSA PADA PABRIK “Sari Guna”

Untuk melihat apakah metode branch-and-cut berjalan dengan baik

dalam penerapannya, diambil permasalahan real dari sebuah pabrik busa “Sari

Guna” yang terletak di Jl.Ciu no 18, Telukan, Sukoharjo. Selama ini, dalam

pendistribusian Sari Guna menggunakan dua kendaraan, pick-up Samsung, yang

dapat mengangkut 40 busa. Sari Guna ingin meminimalkan ongkos yang

dikeluarkan dalam pendistribusian, dalam hal ini adalah bahan bakar, ke

konsumen-konsumennya yang berada di kotamadya Surakarta. Sari Guna

mempunyai 7 konsumen yang berada di wilayah Surakarta, yaitu toko “Tomas”,

“Pak Dullah”, “Sinar Abadi”, “Jempol I”, “Sinar Jaya”, “Jempol II”, dan “Kilat”.

Setiap toko mempunya permintaan yang berbeda-beda banyaknya, secara

berurutan masing-masing adalah 15 busa, 10 busa, 2 busa, 10 busa, 5 busa ,21

busa, dan 5 busa.

Toko Permintaan

Tomas 15

Sinar Abadi 10

Pak Dullah 2

Jempol I 10

Sinar Jaya 5

85

Jempol II 21

Kilat 5

Jumlah Permintaan 68

Lokasi ke-7 lokasi tersebut beserta jarak antar toko dan banyaknya permintaan

dapat digambarkan dalam suatu graf, seperti pada gambar 4.1.1

Pabrik

Thomas

Sinar Abadi

Pak Dullah

Jempol I

Jempol II

Sinar Jaya

Kilat

1.51.2

1.3

0.3

2

2.5

2.3

0.4 2.2

1.31.2 2.5

0.6

0.3

15 10

21

5

5210

5.7

5.8

2.9 5.1

4.5

Gambar 4.1.1. Graf permasalahan distribusi di pabrik busa “Sari Guna”

Bilangan pada simpul menunjukan konsumen, bilangan di atas atau di bawah

simpul menunjukkan banyaknya permintaan pada konsumen tersebut, sedangkan

bilangan pada busur adalah jarak yang ditempuh dari satu simpul ke simpul yang

86

lain. Selama ini Sari Guna menggunakan rute Pabrik Jempol I Jempol

II Pabrik dan Pabrik Thomas Sinar Abadi Pak Dullah Sinar

Jaya Kilat Pabrik dengan jarak tempuh total untuk kedua rute tersebut adalah

246 untuk memenuhi semua permintaan yang ada.

Dari gambar di atas, dengan memberikan nama pada busur dan simpul

seperti gambar 4.1.2 di bawah ini:

0

1

2 3

4

6

5

7

x4

x9

x10

x1

x5

x2

x6

x7 x14

x11x3 x8

x13

x12

x18

x19

x15 x17

x16

Gambar 4.1.2. Nama busur-busur pada permasalahan Pabrik “Sari Guna”

Dengan ini dapat dibuat permasalahan linearnya dengan 40,2 == Ck menjadi:

Minimalkan

191817161514131211

10987654321

8.57.51.55.49.22.26.03.03.13.12.15.24.03.225.12.15.23

xxxxxxxxxxxxxxxxxxxz

++++++++++++++++++=

87

Kendala

( )( ) ( )( )( ) ( ) ( )( )( ){ } ( ){ } ( )02,1,0

0\1,040

227,...2,12

δδ

δδδ

∈∈∈∈

=≥≥

==

exEex

xSSrSxiix

e

e

Sehingga permasalahan di atas mempunyai 147 kendala, dengan bentuk standard

seperti yang dituliskan dalam lampiran (Lampiran 2)

Penyelesaian

Iterasi 1

Langkah 1

Atur

0,,0 =−∞== kzl

Langkah 2


yaitu 0LP



88

975.00

45.000

625.00

55.1375.1

15.172

9

8

7

6

5

4

3

2

1

0

==========

xxxxxxxxxz

0025.005.04.06.095.0

1100

19

18

17

16

15

14

13

12

11

10

==========

xxxxxxxxxx

Dengan tabel standar variabel dasarnya adalah

15.1721300000007130903190700025.01100000010000000000

1000000010000000000011000001001000000000

55.1000000000000000001045.00000000000001100100

375.10000000000000010101625.00000000000000001000975.0100000001010000000095.0000001000001001000005.010100000110100100006.000001000000001001004.010010000010010100000

19181716151413121110987654321

−

−

−−−−−−

RHSxxxxxxxxxxxxxxxxxxx


Langkah 3


Langkah 4


89

4.05.05.05.05.05.05.0 13613613513411311341119161086 =+−+++−++−++++ sssssssssxxxxx

Langkah 5


13613513411341136113119161086 5.05.05.05.05.05.04.0 sssssssssxxxxx −−−−−−=−−−++++

Langkah 6


05.05.05.05.05.05.04.0 13613513411341 ≤−−−−−− ssssss

Langkah 7



( ) ( )( ) ( )1

2

1002

1001

≤++=≥++=

xcutsLPLPxcutsLPLP

Langkah 8

Ubah

2

1==

kl

Langkah 9


90

Iterasi 2

Langkah 2


yaitu 1LP

Permasalahan ke-1 tidak mempunyai daerah layak karena terdapat nilai b yang

negatif semua elemen pada baris b yang negatif taknegatif. Ubah 2=l dan lanjut

ke langkah ke-9.

Langkah 9


Iterasi 3

Langkah 2


yaitu 2LP



975.00

075.000

225.0775.015.1

1575.181

9

8

7

6

5

4

3

2

1

2

==========

xxxxxxxxxz

0025.005.08.0975.095.0

1100

19

18

17

16

15

14

13

12

11

10

==========

xxxxxxxxxx

91


575.181130000000713090340000775.00000000000000000100

1000000010000000000010000001001000000000

225.0000000000000000100095.0000001000001000000015.10000000000000010010

075.00000000000001100000100000000000000000018.00001000001010100000

975.01000000010100000000025.0110000001000000000005.01010000001010000000

975.0000010000000011000019181716151413121110987654321

−

−−

−−−−



Langkah 3


Langkah 4


975.05.05.05.05.05.0 157130130129129983221565 =−+−+−+++−+− sssssssssxxx

Langkah 5


130129983215713012921565 5.05.05.05.05.0975.0 sssssssssxxx −−−−−=−−−−+−

Langkah 6


92

05.05.05.05.05.0975.0 1301299832 ≤−−−−− sssss

Langkah 7



( ) ( )( ) ( )1

2

2224

2223

≤++=≥++=

xcutsLPLPxcutsLPLP

Langkah 8

Ubah

4

3==

kl

Langkah 9


Iterasi 4

Langkah 2


yaitu 3LP


negatif semua elemen pada baris b yang negatif taknegatif. Ubah 4=l dan lanjut

ke langkah ke-9.

Langkah 9


93

Iterasi 5

Langkah 2


yaitu 4LP



00

925.0075.0

01011

225.207

9

8

7

6

5

4

3

2

1

4

==========

xxxxxxxxxz

010

925.0075.0

11100

19

18

17

16

15

14

13

12

11

10

==========

xxxxxxxxxx


225.2071000000007100600160400100000000000000100011000000010000000000011000001001000000000

075.01000000001010110100925.00001000000000010100

10000010000010010000925.01000000001011010000

1000000000000000001001000000010100000000

075.01000100001010010000100000000000000010000101000001101001000011100000010000000000

19181716151413121110987654321

−−

−−−−

−

−−−−−


94


Langkah 3


Langkah 4


075.05.05.05.05.05.05.0 13613613513413213213111711719151085 =+−+++−++−++++ sssssssssxxxxx

Langkah 5


13613513413213111713613211719151085 5.05.05.05.05.05.0075.0 sssssssssxxxxx −−−−−−=−−−++++

Langkah 6


05.05.05.05.05.05.0075.0 136135134132131117 ≤−−−−−− ssssss

Langkah 7



( ) ( )( ) ( )0

1

6446

6445

≤++=≥++=

xcutsLPLPxcutsLPLP

Langkah 8

Ubah

65

==

kl

Langkah 9


95

Iterasi 6

Langkah 2


yaitu 5LP

Dengan menggunakan metode simpleks pada Bab II maka diperoleh untuk


000101011210

9

8

7

6

5

4

3

2

1

5

==========

xxxxxxxxxz

0100111100

19

18

17

16

15

14

13

12

11

10

==========

xxxxxxxxxx


210333.2400333.1100007333.240333.2080667.90667.500100000001000000000001100000100100000000010100000000000010100167.00033.00000133.0133.00033.0033.000167.00067.01000067.0067.00033.0067.0001000000000000000011010000000000000000001167.00067.00000067.0067.00033.0133.00010010000000000000000167.00067.00100067.0033.01067.0067.00010000000000000100000

19181716151413121110987654321

−−−−−

−

−−−


96



Langkah 9


Iterasi 7

Langkah 2


yaitu 6LP



00

85.0001

15.01

85.005.208

9

8

7

6

5

4

3

2

1

6

==========

xxxxxxxxxz

0101

15.011100

19

18

17

16

15

14

13

12

11

10

==========

xxxxxxxxxx

97


05.20860000000760200120000100000001000000000001100000100100000000011100000010000000000

85.0100000000101101000001000000010100000000

15.0100010000101001000010000000000000000010

85.0100000000101000000110000000000000001000010000000110100100001001001000001001000011001000001010000000

15.0100000000101001010000000000000000100000

19181716151413121110987654321

−−−−−−

−−−

−−−−



Langkah 3


Langkah 4


2.05.05.05.05.05.05.05.05.0 158156140136136135135133132132131131129511 =−+−+−+−++−+−+++− ssssssssssssssss

Langkah 5


136135133132131129511581561401361351321311 5.05.05.05.05.05.05.02.0 ssssssssssssssss −−−−−−−−=−+−−−−−−

Langkah 6


05.05.05.05.05.05.05.02.0 13613513313213112951 ≤−−−−−−−− ssssssss

98

Langkah 7



( ) ( )( ) ( )0

1

1668

1667

≤++=≥++=

xcutsLPLPxcutsLPLP

Langkah 8

Ubah

87

==

kl

Langkah 9


Iterasi 8

Langkah 2


yaitu 7LP


negatif dan semua elemen pada baris terrsebut di matriks koefisien bernilai positif.

Ubah 8=l dan lanjut ke langkah ke-9.

Langkah 9


99

Iterasi 9

Langkah 2


yaitu 8LP


negatif dan semua elemen pada baris tersebut di matriks koefisien bernilai positif.

Ubah 9=l dan lanjut ke langkah ke-9.

Langkah 9


permasalahan pabrik ”Sari Guna” adalah:

000101011210

9

8

7

6

5

4

3

2

1

==========

xxxxxxxxxz

0100111100

19

18

17

16

15

14

13

12

11

10

==========

xxxxxxxxxx

Jadi rute optimal pada permasalahan di atas dengan menggunakan metode branch-

and-cut adalah 0-1-4-2-0 dan 0-3-5-7-6-0 dengan total jarak yang ditempuh

adalah 210. Hasil yang sama juga ditunjukkan dengan menggunakan metode

branch-and-bound tetapi pada metode branch-and-bound memakai lebih banyak

iterasi dibandingkan dengan metode branch-and-cut. Sedangkan permasalahan di

atas ini tidak dapat diselesaikan dengan menggunakan metode cutting plane

100

karena pada iterasi ke-5 ada elemen dari matriks b yang bernilai negatif tetapi di

baris yang sama pada matriks koefisien tidak ada yang bernilai negatif. Secara

singkat, hasil ketiga metode tersebut disajikan dalam tebel berikut,

2100-6-7-5-3-0

0-2-4-1-09

---5

2100-6-7-5-3-0

0-2-4-1-083

MinimumJarak II RuteI Rute

IterasiJumlah

Metode-cutBranch-andaneCutting Pl-BoundBranch-and

BAB V

PENUTUP

A. Kesimpulan

Berdasarkan pembahasan pada bab-bab sebelumnya, maka dapat ditarik

beberapa kesimpulan berikut:

1. Permasalahan rute kendaraan berkapasitas (CVRP – Capacitated Vehicle

Routing Problems) adalah permasalahan pengiriman dimana setiap

konsumen hanya dilayani satu kali, kendaraan yang digunakan identik,

hanya terdapat satu sumber, dan terdapat batasan kapasitas pada kendaraan

dengan tujuan utama adalah peminimalan total biaya.

2. Permasalahan rute kendaraan berkapasitas (CVRP) dapat diselesaikan

dengan menggunakan metode branch-and-cut. Metode branch-and-cut

adalah suatu metode iterasi yang digunakan untuk menyelesaikan

permasalahan program linear bilangan bulat. Cara kerja metode ini adalah

dengan menyelesaikan permasalahan program linear relaksasi lalu

menambahkan kendala cuts dan membuat percabangan, sampai pada setiap

percabangannya menghasilkan bilangan bulat atau tidak mempunyai

penyelesaian.

3. Metode branch-and-cut membuat percabangan lebih sederhana daripada

metode branch-and-bound.

102

B. Saran

Berikut diberikan saran yang dapat dijadikan permasalahan yang dapat

dibahas lebih lanjut berhubungan dengan rute kendaraan berkapasitas (CVRP)

yaitu mencari solusi optimal rute kendaraan berkapasitas (CVRP) dengan

menggunakan metode set-covering-based.

103

DAFTAR PUSTAKA

Aardal, K., Nemhauser, G.l., dan Weismantel, R. (2005). Handbooks in

Operations Research and Management Science Vol.12 Discrete

Optimization. Amsterdam: Elsevier.

Golden, B., Raghavan, S., dan Wasil, E. (2007). The Vehicle Routing Problem:

Latest Advances and New Challenges. New York: Springer.

Kurniawati, V. (2006). Metode Simpleks Jaringan. Yogyakarta: Fakultas MIPA,

Universitas Sanata Dharma.

Letchford, A.N., Lysgaard, J., dan Eglese, R.W. (2006). A Branch-and-cut

Algorithm for the Capacitated Open Vehicle Routing Problem. England:

Department of Management Science, Lancaster University.

(http://www.hha.dk/bs/wp/log/L_2006_06.pdf . Diakses pada tanggal 19

September 2009)

Taha, H. (2007). Operation Research 8th edition. New Jersey: Pearson Prentice

Hall

Toth, P and Vigo, D. (2000). The Vehicle Routing Problem. Philadelphia: SIAM.

Winston, W.L. (1997). Operation Research Applications and Algorihtms.

Nevada: Wadsworth.

104

LAMPIRAN Lampiran 1 clear clc y=input('Permasalahan max/min:','s'); n=input('banyaknya variabel='); m=input('Banyaknya persamaan='); TOL=0.000000000000001; A=input('Matriks koefisien:'); b=input('RHS:')'; C=input('Koefisien fungsi objektif='); if (m/2-floor(m/2))~=0 mm=1; else mm=0; end k=1; j=1; bul=0; up(1)=99; lo(1)=99; if y=='max' z=-999999999999999; else z=999999999999999; end for i=1:n if length(find(A(:,i)==0))==(m-1) && length(find(A(:,i)==1))==1 cB(j)=C(i); B(:,j)=A(:,i); j=j+1; else cN(k)=C(i); N(:,k)=A(:,i); k=k+1; end end p=1; ppp=1; o=1; while p<=o %Iterasi ke-p metode branch and Cut fprintf('iterasi ke-%d\n',p) for l=1:198 %Iterasi ke-l metode dual simpleks/simpleks. if det(B)==0 penye=0; break; end if y=='max' %penentuan nilai c c=cN-cB*inv(B)*N; else c=-(cN-cB*inv(B)*N); end for i=1:n-m %Pembulatan vektor c

105

if abs(c(i)-floor(c(i)))<TOL c(i)=floor(c(i)); elseif abs(c(i)-ceil(c(i)))<TOL c(i)=ceil(c(i)); else c(i)=c(i); end end bb=inv(B)*b; for i=1:m %Pembulatan vektor b if abs(bb(i)-floor(bb(i)))<TOL bb(i)=floor(bb(i)); elseif abs(bb(i)-ceil(bb(i)))<TOL bb(i)=ceil(bb(i)); else bb(i)=bb(i); end end pp=find(bb<0); AA=inv(B)*N; for i=1:m for j=1:n-m if abs(AA(i,j)-floor(AA(i,j)))<TOL AA(i,j)=floor(AA(i,j)); elseif abs(AA(i,j)-ceil(AA(i,j)))<TOL AA(i,j)=ceil(AA(i,j)); end end end pt=AA(pp,:)<0; if pt==0 %tidak mempunyai penyelesaian untuk dualsimpleks penye=0; break; elseif min(bb)<0 %Dual simpleks. kk=find(bb<0); bk=bb(kk); for i=1:length(kk) k=kk(find(min(bk)==bk)); if length(k)>1 for i=1:length(k) if AA(k(i),:)>=0 k(i)=0; else k=k(i); break; end end end if k==0 k=kk(find(min(bk)==bk)); k=k(1); end if AA(k,:)>=0 bk=-(bk-min(bk)); kk=kk(find(bk<0));

106

else break; end bk=bb(kk); end k=k(1); for j=1:(n-m) if AA(k,j)<0 r(j)=abs(c(j)/AA(k,j)); elseif AA(k,j)>=0 r(j)=99999999; end end j=find(min(r)==r); j=j(1); x=N(:,j); N(:,j)=B(:,k); B(:,k)=x; x=cN(j); cN(j)=cB(k); cB(k)=x; elseif max(c)<=0 %Optimal? break; else %Simpleks j=find(max(c)==c); j=j(1); for i=1:m if AA(i,j)>0 x(i)=bb(i)/AA(i,j); elseif AA(i,j)<=0 x(i)=99999999; end end k=find(min(x)==x); k=k(1); x=N(:,j); N(:,j)=B(:,k); B(:,k)=x; x=cN(j); cN(j)=cB(k); cB(k)=x; end penye=1; end %branch and cut for I=1:1 if penye==1 %jika mempunyai penyelesaian bb=inv(B)*b; As=inv(B)*A; As(abs(As)<TOL)=0; %Pembulatan matriks A As(abs(As-1)<TOL)=1; %Pembulatan matriks A for i=1:m %Pembulatan vektor b if abs(bb(i)-floor(bb(i)))<TOL*10 bb(i)=floor(bb(i)); elseif abs(bb(i)-ceil(bb(i)))<TOL*10

107

bb(i)=ceil(bb(i)); else bb(i)=bb(i); end end zz=cB*bb; cc=C-cB*inv(B)*A; fprintf('z=') fprintf('%6.6f\n',zz) for i=1:n-m if length(find(As(:,i)==0))==(m-1) fprintf('x%d=',i) fprintf('%6.3f\n',bb(find(As(:,i)==1))) else fprintf('x%d=',i) fprintf('%6.3f\n',0) end end if bul==1 && b(m)~=lo(ppp) %Mempunyai penyelesaian untuk batasan upper tetapi nilai z tidak lebih optimal dari z sementara. if y=='max' if zz<=z disp('Upper tidak lebih optimal') b(m)=lo(ppp); A(m,n)=1; A(m,var(ppp))=1; p=p+1; break; end elseif y=='min' if zz>=z disp('Upper tidak lebih optimal') b(m)=lo(ppp); A(m,n)=1; A(m,var(ppp))=1; p=p+1; break; end end elseif bul==1 && b(m)==lo(ppp) %Mempunyai penyelesaian untuk batasan lower tetapi nilai z tidak lebih optimal dari z sementara. if y=='max' if zz<=z disp('lower tidak lebih optimal') if p==o p=p+1; break; end k=1; for i=2:ppp ssu=find(b==-up(i)); ssu=ssu(find((ssu/2)-floor((ssu)/2)>0)); sssu=find(ssu>(m-2*(ppp-1))); if length(sssu)~=0 saup(k)=ssu(sssu(length(sssu)));

108

k=k+1; else saup(k)=0; k=k+1; end end saup=saup(1:(ppp-1)); t=m-max(saup); ppp=ppp-t/2; m=m-t; n=n-t; b=b(1:m); b(m)=lo(ppp); A=A(1:m,1:n); A(m,n)=1; A(m,var(ppp))=1; C=C(1:n); p=p+1; break; end elseif y=='min' if zz>=z disp('lower tidak lebih optimal') if p==o p=p+1; break; end k=1; for i=2:ppp ssu=find(b==-up(i)); ssu=ssu(find((ssu/2)-floor((ssu)/2)>0)); sssu=find(ssu>(m-2*(ppp-1))); if length(sssu)~=0 saup(k)=ssu(sssu(length(sssu))); k=k+1; else saup(k)=0; k=k+1; end end saup=saup(1:(ppp-1)); t=m-max(saup); ppp=ppp-t/2; m=m-t; n=n-t; b=b(1:m); b(m)=lo(ppp); A=A(1:m,1:n); A(m,n)=1; A(m,var(ppp))=1; C=C(1:n); p=p+1; break; end end

109

end for i=1:(n-m) if length(find(As(:,i)==1))==1 && length(find(As(:,i)==0))==(m-1) bar(i)=find(As(:,i)==1); else bar(i)=0; end end bar=bar(find(bar~=0)); if length(bar)==0 d=[]; else e=bb(bar)-floor(bb(bar)); d=find(e~=0); end if length(d)~=0 %membuat vektor variabel yang akan dibatasi dd=find(As(bar(d(1)),:)==1); for i=1:length(dd) if length(find(As(:,dd(i))==0))==(m-1) && length(find(As(:,dd(i))==1))==1 var(ppp+1)=dd(i); end end end if length(d)==0 && b(m)~=lo(ppp) %mempunyai penyelesaian bilangan bulat untuk batasan upper disp('mempunyai penyelesaian bilangan bulat untuk batasan upper') if y=='max' if zz>z z=zz; bul=1; OP=As; bop=bb; mop=m; nop=n; end elseif y=='min' if zz<z z=zz; bul=1; OP=As; bop=bb; mop=m; nop=n; end end if p==o p=p+1; break; end b(m)=lo(ppp); A(m,n)=1; A(m,var(ppp))=1; p=p+1; elseif length(d)==0 && b(m)==lo(ppp) %mempunyai penyelesaian bilangan bulat untuk batasan lower

110

disp('mempunyai penyelesaian bilangan bulat untuk batasan lower') if y=='max' if zz>z z=zz; bul=1; OP=As bop=bb; mop=m; nop=n; end elseif y=='min' if zz<z z=zz; bul=1; OP=As; bop=bb; mop=m; nop=n; end end if p==o p=p+1; break; end k=1; for i=2:ppp ssu=find(b==-up(i)); ssu=ssu(find((ssu/2)-floor((ssu)/2)>0)); sssu=find(ssu>(m-2*(ppp-1))); if length(sssu)~=0 saup(k)=ssu(sssu(length(sssu))); k=k+1; else saup(k)=0; k=k+1; end end saup=saup(1:(ppp-1)); t=m-max(saup); ppp=ppp-t/2; m=m-t; n=n-t; b=b(1:m); b(m)=lo(ppp); A=A(1:m,1:n); A(m,n)=1; A(m,var(ppp))=1; C=C(1:n); p=p+1; else %mempunyai penyelesaian bukan bilangan bulat/branching disp('branching') k=1; cutb=[]; for i=1:m cutf=find((AA(i,:)-floor(AA(i,:)))>0);

111

if length(cutf)~=0 cutb(k)=i; k=k+1; end end cuts=find((bb(cutb)-floor(bb(cutb)))>0); cutb=cutb(cuts); m=m+1; n=n+1; if length(cutb)~=0 b(m)=-(bb(cutb(1))-floor(bb(cutb(1)))); A(m,n)=1; for i=1:n-1 A(m,i)=-(As(cutb(1),i)-floor(As(cutb(1),i))); end else b(m)=-999; A(m,n)=1; end for i=n-m+1:n if A(m,i)~=1 ro=find(A(:,i)==1); fra=A(m,i); A(m,:)=A(m,:)-fra*A(ro,:); b(m)=b(m)-fra*b(ro); end end up(ppp+1)=ceil(bb(bar(d(1)))); lo(ppp+1)=floor(bb(bar(d(1)))); m=m+1; n=n+1; A(m,n)=1; A(m,var(ppp+1))=-1; b(m)=-up(ppp+1); C(n)=0; ppp=ppp+1; p=p+1; o=o+2; end elseif penye==0 && p>1 && b(m)~=lo(ppp) %jika tidak mempunyai penyelesaian untuk batasan upper disp('tidak mempunyai penyelesaian untuk batasan upper') b(m)=lo(ppp); A(m,n)=1; A(m,var(ppp))=1; p=p+1; elseif penye==0 && p>1 && b(m)==lo(ppp) %jika tidak mempunyai penyelesaian untuk batasan lower disp('tidak mempunyai penyelesaian untuk batasan lower') if p==o p=p+1; break; end k=1; for i=2:ppp

112

ssu=find(b==-up(i)); ssu=ssu(find((ssu/2)-floor((ssu)/2)>0)); sssu=find(ssu>(m-2*(ppp-1))); if length(sssu)~=0 saup(k)=ssu(sssu(length(sssu))); k=k+1; else saup(k)=0; k=k+1; end end saup=saup(1:(ppp-1)); t=m-max(saup); ppp=ppp-t/2; m=m-t; n=n-t; b=b(1:m); b(m)=lo(ppp); A=A(1:m,1:n); A(m,n)=1; A(m,var(ppp))=1; C=C(1:n); p=p+1; else disp('Tidak Mempunyai Penyelesaian') p=p+1; end end N=[]; B=[]; cN=[]; cB=[]; j=1; k=1; for i=1:n %pembentukan basis baru if length(find(A(:,i)==0))==(m-1) && length(find(A(:,i)==1))==1 cB(j)=C(i); B(:,j)=A(:,i); j=j+1; else cN(k)=C(i); N(:,k)=A(:,i); k=k+1; end end end fprintf('\n') fprintf('\n') disp('penyelesaian Optimalnya adalah') fprintf('z=%6.3f\n',z) for i=1:nop-mop if length(find(OP(:,i)==0))==(mop-1) fprintf('x%d=',i) fprintf('%1.0f\n',bop(find(OP(:,i)==1))) else

113

fprintf('x%d=',i) fprintf('%1.0f\n',0) end end Lampiran 2 clear clc a1=[1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0]; a2=[0 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0]; a3=[0 0 0 0 1 0 1 1 0 0 0 0 0 1 1 0 0 0 0]; a4=[0 0 0 1 0 1 0 1 1 1 1 0 0 0 0 1 0 0 0]; a5=[0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 1 0 0]; a6=[0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0]; a7=[0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1]; n=7; A=[a1;a2;a3;a4;a5;a6;a7]; b(1)=15; b(2)=10; b(3)=2; b(4)=10; b(5)=5; b(6)=21; b(7)=5; %7 Combinasi 2 for i=1:6 A(7+i,:)=A(1,:)+A(1+i,:); b(7+i)=b(1)+b(1+i); end for i=1:5 A(13+i,:)=A(2,:)+A(2+i,:); b(13+i)=b(2)+b(2+i); end for i=1:4 A(18+i,:)=A(3,:)+A(3+i,:); b(18+i)=b(3)+b(3+i); end for i=1:3 A(22+i,:)=A(4,:)+A(4+i,:); b(22+i)=b(4)+b(4+i); end for i=1:2 A(25+i,:)=A(5,:)+A(5+i,:); b(25+i)=b(5)+b(5+i); end for i=1:1 A(27+i,:)=A(6,:)+A(6+i,:); b(27+i)=b(6)+b(6+i); end %7 Combinasi 3 for i=1:15 A(28+i,:)=A(1,:)+A(13+i,:); b(28+i)=b(1)+b(13+i);

114

end for i=1:10 A(43+i,:)=A(2,:)+A(18+i,:); b(43+i)=b(2)+b(18+i); end for i=1:6 A(53+i,:)=A(3,:)+A(22+i,:); b(53+i)=b(3)+b(22+i); end for i=1:3 A(59+i,:)=A(4,:)+A(25+i,:); b(59+i)=b(4)+b(25+i); end for i=1:1 A(62+i,:)=A(5,:)+A(27+i,:); b(62+i)=b(5)+b(27+i); end %7 Combinasi 4 for i=1:20 A(63+i,:)=A(1,:)+A(43+i,:); b(63+i)=b(1)+b(43+i); end for i=1:10 A(83+i,:)=A(2,:)+A(53+i,:); b(83+i)=b(2)+b(53+i); end for i=1:4 A(93+i,:)=A(3,:)+A(59+i,:); b(93+i)=b(3)+b(59+i); end for i=1:1 A(97+i,:)=A(4,:)+A(62+i,:); b(97+i)=b(4)+b(62+i); end %7 Combinasi 5 for i=1:15 A(98+i,:)=A(1,:)+A(83+i,:); b(98+i)=b(1)+b(83+i); end for i=1:5 A(113+i,:)=A(2,:)+A(93+i,:); b(113+i)=b(2)+b(93+i); end for i=1:1 A(118+i,:)=A(3,:)+A(97+i,:); b(118+i)=b(3)+b(97+i); end %7 Combinasi 6 for i=1:6 A(119+i,:)=A(1,:)+A(113+i,:); b(119+i)=b(1)+b(113+i); end for i=1:1 A(125+i,:)=A(2,:)+A(118+i,:); b(125+i)=b(2)+b(118+i);

115

end %7 Combinasi 7 for i=1:1 A(126+1,:)=A(1,:)+A(125+i,:); b(126+i)=b(1)+b(125+i); end A(A==2)=0; %pembetulan tanda for i=8:127 b(i)=-2*b(i)/25; A(i,:)=-A(i,:); end % Smua jalur yang dari depot b(128)=8; A(128,1)=1; A(128,2)=1; for i=15:19 A(128,i)=1; end %minus'nya smua jalur dari depot b(129)=-b(128); A(129,:)=-A(128,:); %minus'nya derajat konsumen for i=1:7 A(129+i,:)=-A(i,:); b(129+i)=-2; b(i)=2; end %batasan pada jalur for i=1:19 A(136+i,i)=1; b(136+i)=2; end for i=3:14 b(136+i)=1; end Lampiran 3 clear clc a1=[1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0]; a2=[0 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0]; a3=[0 0 0 0 1 0 1 1 0 0 0 0 0 1 1 0 0 0 0]; a4=[0 0 0 1 0 1 0 1 1 1 1 0 0 0 0 1 0 0 0]; a5=[0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 1 0 0]; a6=[0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0]; a7=[0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1]; n=7; A=[a1;a2;a3;a4;a5;a6;a7]; b(1)=15; b(2)=10; b(3)=2; b(4)=10;

116

b(5)=5; b(6)=21; b(7)=5; %7 Combinasi 2 for i=1:6 A(7+i,:)=A(1,:)+A(1+i,:); b(7+i)=b(1)+b(1+i); end for i=1:5 A(13+i,:)=A(2,:)+A(2+i,:); b(13+i)=b(2)+b(2+i); end for i=1:4 A(18+i,:)=A(3,:)+A(3+i,:); b(18+i)=b(3)+b(3+i); end for i=1:3 A(22+i,:)=A(4,:)+A(4+i,:); b(22+i)=b(4)+b(4+i); end for i=1:2 A(25+i,:)=A(5,:)+A(5+i,:); b(25+i)=b(5)+b(5+i); end for i=1:1 A(27+i,:)=A(6,:)+A(6+i,:); b(27+i)=b(6)+b(6+i); end %7 Combinasi 3 for i=1:15 A(28+i,:)=A(1,:)+A(13+i,:); b(28+i)=b(1)+b(13+i); end for i=1:10 A(43+i,:)=A(2,:)+A(18+i,:); b(43+i)=b(2)+b(18+i); end for i=1:6 A(53+i,:)=A(3,:)+A(22+i,:); b(53+i)=b(3)+b(22+i); end for i=1:3 A(59+i,:)=A(4,:)+A(25+i,:); b(59+i)=b(4)+b(25+i); end for i=1:1 A(62+i,:)=A(5,:)+A(27+i,:); b(62+i)=b(5)+b(27+i); end %7 Combinasi 4 for i=1:20 A(63+i,:)=A(1,:)+A(43+i,:); b(63+i)=b(1)+b(43+i); end for i=1:10

117

A(83+i,:)=A(2,:)+A(53+i,:); b(83+i)=b(2)+b(53+i); end for i=1:4 A(93+i,:)=A(3,:)+A(59+i,:); b(93+i)=b(3)+b(59+i); end for i=1:1 A(97+i,:)=A(4,:)+A(62+i,:); b(97+i)=b(4)+b(62+i); end %7 Combinasi 5 for i=1:15 A(98+i,:)=A(1,:)+A(83+i,:); b(98+i)=b(1)+b(83+i); end for i=1:5 A(113+i,:)=A(2,:)+A(93+i,:); b(113+i)=b(2)+b(93+i); end for i=1:1 A(118+i,:)=A(3,:)+A(97+i,:); b(118+i)=b(3)+b(97+i); end %7 Combinasi 6 for i=1:6 A(119+i,:)=A(1,:)+A(113+i,:); b(119+i)=b(1)+b(113+i); end for i=1:1 A(125+i,:)=A(2,:)+A(118+i,:); b(125+i)=b(2)+b(118+i); end %7 Combinasi 7 for i=1:1 A(126+1,:)=A(1,:)+A(125+i,:); b(126+i)=b(1)+b(125+i); end A(A==2)=0; %pembetulan tanda for i=8:127 b(i)=-2*b(i)/40; A(i,:)=-A(i,:); end % Smua jalur yang dari depot b(128)=4; A(128,1)=1; A(128,2)=1; for i=15:19 A(128,i)=1; end %minus'nya smua jalur dari depot b(129)=-b(128); A(129,:)=-A(128,:); %minus'nya derajat konsumen

118

for i=1:7 A(129+i,:)=-A(i,:); b(129+i)=-2; b(i)=2; end %batasan pada jalur for i=1:19 A(136+i,i)=1; b(136+i)=2; end for i=3:14 b(136+i)=1; end %Penambahan slack C=[30 25 12 15 20 23 4 25 12 13 13 3 6 22 29 45 51 57 58]; for i=1:155 C(i+19)=0; A(i,i+19)=1; end c=b'; b=c; y='min'; n=174; m=155; TOL=0.00000001; k=1; j=1; bul=0; up(1)=99; lo(1)=99; if y=='max' z=-999999999999999; else z=999999999999999; end for i=1:n %Pembentukan Basis if length(find(A(:,i)==0))==(m-1) && length(find(A(:,i)==1))==1 cB(j)=C(i); B(:,j)=A(:,i); j=j+1; else cN(k)=C(i); N(:,k)=A(:,i); k=k+1; end end p=1; ppp=1; o=1; while p<=o %Iterasi ke-p metode branch and Cut fprintf('iterasi ke-%d\n',p) for l=1:198 %Iterasi ke-l metode dual simpleks/simpleks. if det(B)==0 penye=0; break;

119

end if y=='max' %penentuan nilai c c=cN-cB*inv(B)*N; else c=-(cN-cB*inv(B)*N); end for i=1:n-m %Pembulatan vektor c if abs(c(i)-floor(c(i)))<TOL c(i)=floor(c(i)); elseif abs(c(i)-ceil(c(i)))<TOL c(i)=ceil(c(i)); else c(i)=c(i); end end bb=inv(B)*b; for i=1:m %Pembulatan vektor b if abs(bb(i)-floor(bb(i)))<TOL bb(i)=floor(bb(i)); elseif abs(bb(i)-ceil(bb(i)))<TOL bb(i)=ceil(bb(i)); else bb(i)=bb(i); end end pp=find(bb<0); AA=inv(B)*N; for i=1:m for j=1:n-m if abs(AA(i,j)-floor(AA(i,j)))<TOL AA(i,j)=floor(AA(i,j)); elseif abs(AA(i,j)-ceil(AA(i,j)))<TOL AA(i,j)=ceil(AA(i,j)); end end end pt=AA(pp,:)<0; if pt==0 %tidak mempunyai penyelesaian untuk dualsimpleks penye=0; break; elseif min(bb)<0 %Dual simpleks. kk=find(bb<0); bk=bb(kk); for i=1:length(kk) k=kk(find(min(bk)==bk)); if length(k)>1 for i=1:length(k) if AA(k(i),:)>=0 k(i)=0; else k=k(i); break; end end end

120

if k==0 k=kk(find(min(bk)==bk)); k=k(1); end if AA(k,:)>=0 bk=-(bk-min(bk)); kk=kk(find(bk<0)); else break; end bk=bb(kk); end k=k(1); for j=1:(n-m) if AA(k,j)<0 r(j)=abs(c(j)/AA(k,j)); elseif AA(k,j)>=0 r(j)=99999999; end end j=find(min(r)==r); j=j(1); x=N(:,j); N(:,j)=B(:,k); B(:,k)=x; x=cN(j); cN(j)=cB(k); cB(k)=x; elseif max(c)<=0 %Optimal? break; else %Simpleks j=find(max(c)==c); j=j(1); for i=1:m if AA(i,j)>0 x(i)=bb(i)/AA(i,j); elseif AA(i,j)<=0 x(i)=99999999; end end k=find(min(x)==x); k=k(1); x=N(:,j); N(:,j)=B(:,k); B(:,k)=x; x=cN(j); cN(j)=cB(k); cB(k)=x; end penye=1; end %branch and cut for I=1:1 if penye==1 %jika mempunyai penyelesaian bb=inv(B)*b;

121

As=inv(B)*A; As(abs(As)<TOL)=0; %Pembulatan matriks A As(abs(As-1)<TOL)=1; %Pembulatan matriks A for i=1:m %Pembulatan vektor b if abs(bb(i)-floor(bb(i)))<TOL*10 bb(i)=floor(bb(i)); elseif abs(bb(i)-ceil(bb(i)))<TOL*10 bb(i)=ceil(bb(i)); else bb(i)=bb(i); end end zz=cB*bb; cc=C-cB*inv(B)*A; fprintf('z=') fprintf('%6.6f\n',zz) for i=1:n-m if length(find(As(:,i)==0))==(m-1) fprintf('x%d=',i) fprintf('%6.3f\n',bb(find(As(:,i)==1))) else fprintf('x%d=',i) fprintf('%6.3f\n',0) end end if bul==1 && b(m)~=lo(ppp) %Mempunyai penyelesaian untuk batasan upper tetapi nilai z tidak lebih optimal dari z sementara. if y=='max' if zz<=z disp('Upper tidak lebih optimal') b(m)=lo(ppp); A(m,n)=1; A(m,var(ppp))=1; p=p+1; break; end elseif y=='min' if zz>=z disp('Upper tidak lebih optimal') b(m)=lo(ppp); A(m,n)=1; A(m,var(ppp))=1; p=p+1; break; end end elseif bul==1 && b(m)==lo(ppp) %Mempunyai penyelesaian untuk batasan lower tetapi nilai z tidak lebih optimal dari z sementara. if y=='max' if zz<=z disp('lower tidak lebih optimal') if p==o p=p+1; break; end

122

k=1; for i=2:ppp ssu=find(b==-up(i)); ssu=ssu(find((ssu/2)-floor((ssu)/2)>0)); sssu=find(ssu>(m-2*(ppp-1))); if length(sssu)~=0 saup(k)=ssu(sssu(length(sssu))); k=k+1; else saup(k)=0; k=k+1; end end saup=saup(1:(ppp-1)); t=m-max(saup); ppp=ppp-t/2; m=m-t; n=n-t; b=b(1:m); b(m)=lo(ppp); A=A(1:m,1:n); A(m,n)=1; A(m,var(ppp))=1; C=C(1:n); p=p+1; break; end elseif y=='min' if zz>=z disp('lower tidak lebih optimal') if p==o p=p+1; break; end k=1; for i=2:ppp ssu=find(b==-up(i)); ssu=ssu(find((ssu/2)-floor((ssu)/2)>0)); sssu=find(ssu>(m-2*(ppp-1))); if length(sssu)~=0 saup(k)=ssu(sssu(length(sssu))); k=k+1; else saup(k)=0; k=k+1; end end saup=saup(1:(ppp-1)); t=m-max(saup); ppp=ppp-t/2; m=m-t; n=n-t; b=b(1:m); b(m)=lo(ppp); A=A(1:m,1:n);

123

A(m,n)=1; A(m,var(ppp))=1; C=C(1:n); p=p+1; break; end end end for i=1:(n-m) if length(find(As(:,i)==1))==1 && length(find(As(:,i)==0))==(m-1) bar(i)=find(As(:,i)==1); else bar(i)=0; end end bar=bar(find(bar~=0)); if length(bar)==0 d=[]; else e=bb(bar)-floor(bb(bar)); d=find(e~=0); end if length(d)~=0 %membuat vektor variabel yang akan dibatasi dd=find(As(bar(d(1)),:)==1); for i=1:length(dd) if length(find(As(:,dd(i))==0))==(m-1) && length(find(As(:,dd(i))==1))==1 var(ppp+1)=dd(i); end end end if length(d)==0 && b(m)~=lo(ppp) %mempunyai penyelesaian bilangan bulat untuk batasan upper disp('mempunyai penyelesaian bilangan bulat untuk batasan upper') if y=='max' if zz>z z=zz; bul=1; OP=As; bop=bb; mop=m; nop=n; end elseif y=='min' if zz<z z=zz; bul=1; OP=As; bop=bb; mop=m; nop=n; end end if p==o p=p+1; break;

124

end b(m)=lo(ppp); A(m,n)=1; A(m,var(ppp))=1; p=p+1; elseif length(d)==0 && b(m)==lo(ppp) %mempunyai penyelesaian bilangan bulat untuk batasan lower disp('mempunyai penyelesaian bilangan bulat untuk batasan lower') if y=='max' if zz>z z=zz; bul=1; OP=As bop=bb; mop=m; nop=n; end elseif y=='min' if zz<z z=zz; bul=1; OP=As; bop=bb; mop=m; nop=n; end end if p==o p=p+1; break; end k=1; for i=2:ppp ssu=find(b==-up(i)); ssu=ssu(find((ssu/2)-floor((ssu)/2)>0)); sssu=find(ssu>(m-2*(ppp-1))); if length(sssu)~=0 saup(k)=ssu(sssu(length(sssu))); k=k+1; else saup(k)=0; k=k+1; end end saup=saup(1:(ppp-1)); t=m-max(saup); ppp=ppp-t/2; m=m-t; n=n-t; b=b(1:m); b(m)=lo(ppp); A=A(1:m,1:n); A(m,n)=1; A(m,var(ppp))=1; C=C(1:n);

125

p=p+1; else %mempunyai penyelesaian bukan bilangan bulat/branching disp('branching') k=1; cutb=[]; for i=1:m cutf=find((AA(i,:)-floor(AA(i,:)))>0); if length(cutf)~=0 cutb(k)=i; k=k+1; end end cuts=find((bb(cutb)-floor(bb(cutb)))>0); cutb=cutb(cuts); m=m+1; n=n+1; if length(cutb)~=0 b(m)=-(bb(cutb(1))-floor(bb(cutb(1)))); A(m,n)=1; for i=1:n-1 A(m,i)=-(As(cutb(1),i)-floor(As(cutb(1),i))); end else b(m)=-999; A(m,n)=1; end for i=n-m+1:n if A(m,i)~=1 ro=find(A(:,i)==1); fra=A(m,i); A(m,:)=A(m,:)-fra*A(ro,:); b(m)=b(m)-fra*b(ro); end end up(ppp+1)=ceil(bb(bar(d(1)))); lo(ppp+1)=floor(bb(bar(d(1)))); m=m+1; n=n+1; A(m,n)=1; A(m,var(ppp+1))=-1; b(m)=-up(ppp+1); C(n)=0; ppp=ppp+1; p=p+1; o=o+2; end elseif penye==0 && p>1 && b(m)~=lo(ppp) %jika tidak mempunyai penyelesaian untuk batasan upper disp('tidak mempunyai penyelesaian untuk batasan upper') b(m)=lo(ppp); A(m,n)=1; A(m,var(ppp))=1; p=p+1; elseif penye==0 && p>1 && b(m)==lo(ppp) %jika tidak mempunyai penyelesaian untuk batasan lower

126

disp('tidak mempunyai penyelesaian untuk batasan lower') if p==o p=p+1; break; end k=1; for i=2:ppp ssu=find(b==-up(i)); ssu=ssu(find((ssu/2)-floor((ssu)/2)>0)); sssu=find(ssu>(m-2*(ppp-1))); if length(sssu)~=0 saup(k)=ssu(sssu(length(sssu))); k=k+1; else saup(k)=0; k=k+1; end end saup=saup(1:(ppp-1)); t=m-max(saup); ppp=ppp-t/2; m=m-t; n=n-t; b=b(1:m); b(m)=lo(ppp); A=A(1:m,1:n); A(m,n)=1; A(m,var(ppp))=1; C=C(1:n); p=p+1; else disp('Tidak Mempunyai Penyelesaian') p=p+1; end end N=[]; B=[]; cN=[]; cB=[]; j=1; k=1; for i=1:n %pembentukan basis baru if length(find(A(:,i)==0))==(m-1) && length(find(A(:,i)==1))==1 cB(j)=C(i); B(:,j)=A(:,i); j=j+1; else cN(k)=C(i); N(:,k)=A(:,i); k=k+1; end end end fprintf('\n') fprintf('\n')

127

disp('penyelesaian Optimalnya adalah') fprintf('z=%6.3f\n',z) for i=1:nop-mop if length(find(OP(:,i)==0))==(mop-1) fprintf('x%d=',i) fprintf('%1.0f\n',bop(find(OP(:,i)==1))) else fprintf('x%d=',i) fprintf('%1.0f\n',0) end end

metode branch-and-cut untuk menyelesaikan …

Documents