Metode Penghitungan Implisit Masalah Pemrograman Linear Nol-Satu Dengan Algoritma Balas (Implicit Enumeration Method for Zero-One Linear Programming Problems with Balas Algorithm)

Abstract

Pemrograman linear bilangan bulat umum, dapat diselesaikan dengan Metode Gomory atau Metode Cabang dan Batas. Akan tetapi kedua metode ini menjadi kurang efisien jika peubah-peubah pada pemrograman tersebut hanya bernilai nol atau satu. Untuk itu perlu ada metode lain yang digunakan secara khusus untuk menyelesaikan masalah pemrograman linear nol-satu. Penyelesaian pemrograman nol-satu ini dapat dilakukan secara eksplisit atau implisit. Secara eksplisit, penghitungan dilakukan pada setiap titik solusi, kemudian dipilih solusi yang optimum. Sedangkan dengan penghitungan implisit, solusi optimum dapat diperoleh tanpa harus mencari seluruh titik solusi. Balas (1965) membuat suatu algoritma untuk penghitungan implisit, dimana solusi disusun dengan dimulai dari satu peubah, yang kemudian terus bertambah membentuk solusi parsial. Proses ini disebut gerak ke depan. Di dalam proses gerak ke depan ini terjadi peristiwa pemfatoman, yaitu penghentian perhitungan terhadap suatu solusi parsial untuk diganti dengan solusi parsial yang lain. Proses penggantian ini disebut lacak balik. Penghitungan berakhir bila seluruh peubah yang terdapat di dalam solusi parsial telah difatomkan. Metode penghitungan implisit dengan algoritma Balas, dapat menyelesaikan masalah pemrograman linear nol-satu secara lebih efisien.