Program Bilangan Bulat


Masalah program bilangan bulat (integer programming problem/IP) adalah masalah program linear yang semua atau beberapa variabelnya harus merupakan bilangan bulat nonnegatif.

Macam-macam integer programming:
  1. Program bilangan bulat murni, menghendaki semua variabelnya harus bilangan bulat nonnegatif.
  2. Program bilangan bulat campuran, beberapa variabelnya harus bilangan bulat nonnegatif.
  3. Program bilangan bulan 0-1 adalah IP yang menghendaki semua variabel harus 0 atau 1.

Algoritma cabang dan batas (branch and bound) merupakan salah satu algoritma yang dapat diselesaikan dengan program bilangan bulat murni.

Langkah:
  1. Dibentuk submasalah I, yaitu submasalah yang didapat dari PL dengan syarat mutlak x1 > 0.
  2. Pilih salah satu penyelesaian optimal yang berbentuk pecahan (katakan xi).
  3. Tentukan range dari penyelesaian optimal tersebut, misalkan a < xi < a + 1. Kemudian submasalah I dicabangkan menjadi 2 submasalah, dengan ketentuan:
                          i.      Submasalah 2
Submasalah 1 + kendala xi ≥ a + 1
                        ii.      Submasalah 3
Submasalah 1 + kendala xi ≤ a
            Submasalah tidak dicabangkan jika
-        Infeasibel
-        Penyelesaian optimal sudah integer
-       Nilai optimal z  melebihi z  awal, untuk kasus memaksimalkan sedangkan nilai optimal z  kurang dari z  awal, untuk kasus meminimalkan.
0 Responses