Metode Branch & Bound

BAB I

PENDAHULUAN

            1.1.        Latar Belakang Masalah

           Salah satu pendekatan yang dapat dilakukan untuk menyelesaikan masalah program linier adalah metode branch and bound, pengembangan dari Program Linear di mana beberapa atau semua variabel keputusannya harus berupa integer. 

           Pemrograman bulat dibutuhkan ketika keputusan harus dilakukan dalam bentuk bilangan bulat (bukan pecahan yang sering terjadi bila kita gunakan metode simpleks). Model matematis dari pemrograman bulat sebenarnya sama dengan model linear programming, dengan tambahan batasan bahwa variabelnya harus bilangan bulat.

            Untuk lebih jelasnya, dalam makalah ini penulis akan membahas metode branch and bound.

             1.2.       Rumusan Masalah

1.         Apa pengertian Metode Branch and Bound?

2.         Bagaimana langkah-langkah dari metode Branch and Bound?

3.         Bagaimana penetapan batas dari metode Branch and Bound?

4.         Bagaimana penghentian pencabangan dari metode Branch and Bound?

             1.3.      Tujuan Penulis

          Berdasarkan rumusan masalah di atas maka tujuan dalam penulisan makalah ini sebagai berikut:

1.      Untuk mengetahui apa itu Metode Branch and Bound

2.      Untuk mengetahui apa langkah-langkah dari metode Branch and Bound

3.      Untuk mengetahui penetapan batas dari metode Branch and Bound

4.      Untuk mengetahui penghentian pencabangan dari metode Branch and Bound

                             

BAB II

PEMBAHASAN

2.1.         Pengertian Metode Branch and Bound

            Metode Branch and Bound adalah sebuah teknik algoritma yang secara khusus mempelajari bagaimana caranya memperkecil Search Tree menjadi sekecil mungkin.

            Sesuai dengan namanya, metode ini terdiri dari 2 langkah yaitu :

·         Branch yang artinya membangun semua cabang tree yang mungkin menuju solusi.

·         Bound yang artinya menghitung node mana yang merupakan active node (E-node) dan node mana yang merupakan dead node (D-node) dengan menggunakan syarat batas constraint (kendala)..

2.2.         Langkah – Langkah Metode Branch and Bound

      Langkah-langkah metode Branch dan Bound dapat dilakukan seperti berikut :

1.        Selesaikan LP dengan metode simpleks biasa

2.        Teliti solusi optimumnya. Jika variabel basis yang diharapkan bulat adalah bulat, solusi optimum bulat telah tercapai.

3.        Nilai solusi pecah yang layak dicabangkan ke dalam sub-sub masalah. Tujuannya adalah untuk menghilangkan solusi kontinyu yang tidak memenuhi persyaratan bulat dalam masalah itu.

4.        Untuk setiap sub-masalah, nilai solusi optimum kontinyu fungsi tujuan ditetapkan sebagai batas atas. Solusi bulat terbaik menjadi batas bawah (pada awalnya, ini adalah solusi kontinyu yang dibulatkan ke bawah). Sub-sub masalah yang memiliki batas atas kurang dari batas bawah yang ada, tidak diikut sertakan pada analisa selanjutnya. Suatu solusi bulat layak adalah sama baik atau lebih baik dari batas atas untuk setiap sub masalah yang dicari. Jika solusi yang demikian terjadi, suatu sub masalah dengan batas atas terbaik dipilih untuk dicabangkan. Kembali ke langkah 3.

2.3.         Penetapan Batas (Bounding)

     Pada algoritma branch and bound terdapat dua batas yaitu batas atas (upper bound) dan batas bawah (lower bound).

a.       Pada masalah maksimisasi:

Batas atas merupakan solusi ILP relaksasi dari sub masalah tersebut sedangkan batas bawahnya adalah nilai dari sub masalah tersebut ataupun solusi dari sub masalah lain yang semua variabel keputusan yang harus bernilai integer sudah bernilai integer (solusi terbaik yang sejauh ini diperoleh).

b.      Pada masalah minimisasi:

Batas bawah merupakan solusi ILP relaksasi dari sub masalah tersebut sedangkan batas atasnya adalah nilai dari sub masalah tersebut ataupun solusi dari sub masalah lain yang semua variabel keputusan yang harus bernilai integer sudah bernilai integer ( solusi terkecil (terbaik) yang sejauh ini diperoleh ).

2.4.    Penghentian Pencabangan (Fathoming)

   Pencabangan atau pencarian solusi pada suatu sub masalah dihentikan jika:

a.       Infeasible atau tidak mempunyai daerah layak.

b.      Semua variabel keputusan yang harus bernilai integer sudah bernilai integer

c.       Pada masalah maksimisasi, penghentian pencabangan pada suatu sub masalah dilakukan jika batas atas dari sub masalah tersebut tidak lebih besar atau sama dengan batas bawah.

d.      Sedangkan pada masalah minimisasi penghentian pencabangan pada suatu sub masalah dilakukan jika batas bawah tidak lebih lebih kecil atau sama dengan batas atas.

2.5.    Kondisi Optimal

          Kondisi optimal pada Branch and bound antara lain :

a.       Jika tidak ada lagi sub masalah yang perlu dicabangkan lagi maka solusi optimal sudah diperoleh.

b.      Pada masalah maksimisasi solusi optimal merupakan solusi submasalah yang saat ini menjadi batas bawah (lower bound)

c.       Pada masalah minimisasi solusi optimal merupakan solusi submasalah yang saat ini menjadi batas atas (upper bound).

 

Contoh :

Maksimumkan :   Z = 3X₁ + 5X₂

Kendala :           2X₁  ≤ 8

                         3X₂  ≤ 15

                         6X₁ + 5X₂  ≤ 30

Penyelesaian :

1.        Menyelesaikan dengan metode simpleks.

         a.       Mengubah fungsi tujuan dan kendala

          Fungsi tujuan :   Z - 3X₁ - 5X₂ = 0

          Kendala :            2X₁ + X₃ = 8

                                     3X₂ + X₄ = 15

                        6X₁ +  5X₂ + X₅  = 30

                     ( X₃, X₄, X₅  adalah variabel slack) 

         b.      Menyusun persamaan-persamaan ke dalam table :

Var.Dasar	Z	X1	X2	X3	X4	X5	NK
Z	1	-3	-5	0	0	0	0
X3	0	2	0	1	0	0	8
X4	0	0	3	0	1	0	15
X5	0	6	5	0	0	1	30

          c.       Memilih KOLOM KUNCI

Kolom kunci adalah kolom yang mempunyai nilai pada baris Z yang bernilai negatif dengan angka terbesar.

Var.Dasar	Z	X1	X2	X3	X4	X5	NK
Z	1	-3	-5	0	0	0	0
X3	0	2	0	1	0	0	8
X4	0	0	3	0	1	0	15
X5	0	6	5	0	0	1	30

        d.      Memilih BARIS KUNCI

Baris kunci adalah baris yang mempunyai indeks terkecil

Var.Dasar	Z	X1	X2	X3	X4	X5	NK
Z	1	-3	-5	0	0	0	0
X3	0	2	0	1	0	0	8
X4	0	0	3	0	1	0	15
X5	0	6	5	0	0	1	30

        e.       Mengubah nilai-nilai baris kunci dengan cara membaginya dengan pivot sehingga tabel menjadi

                seperti berikut:

Var.Dasar	Z	X1	X2	X3	X4	X5	NK
Z
X3
X2	0	0	1	0	1/3	0	5
X5

        f.       Mengubah nilai-nilai selain baris kunci sehingga nilai-nilai kolom kunci (selain baris kunci) = 0

Baris Baru = Baris Lama – (Koefisien Angka Kolom Kunci × Nilai Baris Baru Kunci)

Baris Z

Baris lama                           [1       -3        -5          0          0        0      0 ]

NBBK                    -5         [ 0        0         1          0         1/3       0      5 ]       

Baris Baru                             1       -3         0          0         5/3        0     25

Baris X₃

Baris lama                           [0        2         0          1          0          0      8 ]

NBBK                      0        [0        0         1          0         1/3         0      5]       

Baris Baru                            0        2         0          1           0          0      8

Baris X₅

Baris lama                           [0        6        5           0          0          1      30 ]

NBBK                     5         [0        0         1          0         1/3         0       5 ]       

Baris Baru                             0        6        0          0        -5/3        1       5

         g.      Masukkan nilai di atas ke dalam tabel, sehingga tabel menjadi seperti berikut:

Var.Dasar	Z	X1	X2	X3	X4	X5	NK
Z	1	-3	0	0	5/3	0	25
X3	0	2	0	1	0	0	8
X2	0	0	1	0	1/3	0	5
X5	0	6	0	0	-5/3	1	5

            

          h.      Melanjutkan sampai baris Z tidak ada nilai negative

Var.Dasar	Z	X1	X2	X3	X4	X5	NK
Z	1	-3	0	0	5/3	0	25
X3	0	2	0	1	0	0	8
X2	0	0	1	0	1/3	0	5
X5	0	6	0	0	-5/3	1	5

Var.Dasar	Z	X1	X2	X3	X4	X5	NK
Z	1	0	0	0	5/6	½	27  1/2
X3	0	0	0	1	5/9	-1/3	6  1/3
X2	0	0	1	0	1/3	0	5
X1	0	1	0	0	-5/18	1/6	5/6

 Diperoleh hasil: X₁ = 5/6   ;   X₂ =5    ;   Z = 27 1/2

       2.      Variabel basis X₁ dan X₂ belum bernilai integer, maka dilakukan tahap Branch and Bound.

Batas atas      : X₁ = 0,83    ;  X₂ = 5         ;  Z = 27,5

Batas bawah : X₁ = 0         ;  X₂ = 5         ;   Z = 25

Maksimumkan :   Z = 3X₁ + 5X₂

Kendala :   2X₁ ≤ 8

                  3X₂  ≤ 15

                  6X₁ +  5X₂  ≤ 30

                

BAB III

PENUTUP

3.1. Kesimpulan

Metode Branch and Bound adalah sebuah teknik algoritma yang secara khusus mempelajari bagaimana caranya memperkecil Search Tree menjadi sekecil mungkin.

Langkah-langkah metode Branch dan Bound dapat dilakukan seperti berikut :

    1.    Selesaikan LP dengan metode simpleks biasa

    2.    Teliti solusi optimumnya. Jika variabel basis yang diharapkan bulat adalah bulat, solusi optimum

          bulat telah tercapai.

     3.    Nilai solusi pecah yang layak dicabangkan ke dalam sub-sub masalah. Tujuannya adalah untuk

          menghilangkan solusi kontinyu yang tidak memenuhi persyaratan bulat dalam masalah itu.

    Untuk setiap sub-masalah, nilai solusi optimum kontinyu fungsi tujuan ditetapkan sebagai batas atas. Solusi bulat terbaik menjadi batas bawah (pada awalnya, ini adalah solusi kontinyu yang dibulatkan ke bawah). Sub-sub masalah yang memiliki batas atas kurang dari batas bawah yang ada, tidak diikut sertakan pada analisa selanjutnya. Suatu solusi bulat layak adalah sama baik atau lebih baik dari batas atas untuk setiap sub masalah yang dicari. Jika solusi yang demikian terjadi, suatu sub masalah dengan batas atas terbaik dipilih untuk dicabangkan. Kembali ke langkah 3.

3.2.  Saran

Adapun saran yang penulis dapat kemukakan adalah apabila pemateri mempresentasikan hasil makalahnya sebaiknya peserta diskusi memperhatikan dengan baik sehingga penjelasannya itu tidak diulang-ulang guna mengefesienkan waktu.

Daftar Pustaka

www.stern.nyu.edu/om/.../Lecture%203.pp

aeunike.lecture.ub.ac.id/files/2012/11/Pertemuan-11-OR.pdf

www.academia.edu/3330553/Branch_and_Bound_Program_Linier_