Metode Stokastik

Integer ProgrammingMetode Branch and Bound

Fakultas

Teknik

Khamaludin, S.T., M.T

Program Studi

Teknik Industri

Pertemuan:

03

1. Selesaikan masalah linier programming dengan metodesimpleks biasa tanpa pembatas bilangan bulat.

2. Teliti solusi optimumnya. Jika variable yang diharapkanbulat adalah bulat, solusi bulat telah tercapai. Jika salahsatu atau lebih variable basis yang diharapkan bulatternyata tidak nulat, lanjut ke tahap 3.

3. Nilai solusi pecah yang layak dicabangkan ke dalam sub-sub masalah. Tujuannya adalah untuk menghilangkansolusi kontinyu yang tidak memenuhi syarat bulat darimasalah itu. Percabangan itu dilakukan melalui kendala-kendala mutually exclusive yang perlu untuk memenuhipersyaratan bulat dengan jaminan tidak ada solusi bulatlayak yang tidak diikutsertakan.

Algoritma Branch and Bound

4. Untuk setiap sub masalah nilai solusi optimum kontinyufungsi tujuan ditetapkan sebagain batas atas. Suatu solusibulat layak adalah sama baik atau lebih baik dari batasatas untuk tiap sub masalah dengan batas atas terbaikdiplih untuk dicabangkan. Kembali ke langkah 3.

Algoritma Branch and Bound

Contoh:

Maksimasi Z = 2X1 + 3X2

Pembatas 5X1 + 7X2 < 354X1 + 9X2 < 36X1, X2 > 0 dan bilangan bulat

PL-1

PL-1

PL-3PL-2

X2 < 2 X2 > 3

PL-1

PL-3PL-2

X2 < 2 X2 > 3

PL-3

X2 > 3

PL-5PL-4

X1 < 2X1 > 3

PL-3

X2 > 3

PL-5PL-4

X1 < 2X1 > 3

Tidak Layak

PL-7PL-6

X2 < 3 X2 > 4

PL-4

X1 < 2

PL-7PL-6

X2 < 3 X2 > 4

X1 = 0 ,X2 = 4Z = 12

PL-2

X2 < 2

PL-9

X1 < 4 X1 > 5

PL-8

PL-2

X2 < 2

PL-9

X1 < 4 X1 > 5

X1 = 4 ,X2 = 2Z = 14

PL-8

PL-9

X1 > 5

PL-11

X2 < 1 X2 > 2

PL-10

PL-9

X1 > 5

PL-11

X2 < 1 X2 > 2

PL-10

Tidak Layak

X2 < 1

PL-10

PL-13

X1 < 5 X1 > 6

PL-12

X1 = 5 ,X2 = 1Z = 13

PL-13

X1 > 6

PL-15

X2 < 0 X2 > 1

PL-14

X1 = 7 ,X2 = 0Z = 14

Tidak Layak

Dalam permasalahan yang besar memakan waktu yangsangat lama, karena itu dalam prosedur percabangan danpencarian, analisis selanjutnya diberhentikan jika:a. Hasil dari sub problem lebih jelek dibandingkan dengan

batas atas yang sudah diidentifikasi.b. Percabangan selanjutnya menghasilkan solusi tidka

layak.

Kelemahan Metode Branch and Bound

Thanks!!!