Penyelesaian Masalah Integer Programming dengan Metode Relaksasi Lagrange

Abstract

Masalah integer programming (IP) dapat diselesaikan dengan menggunakan metode relaksasi Lagrange. Ide dari permasalahan relaksasi Lagrange berawal dari metode penalti yang merupakan suatu metode yang digunakan untuk mencari solusi hampiran dari masalah pemrograman berkendala. Dalam formulasi masalah relaksasi Lagrange terkait dengan pengali Lagrange. Nilai pengali Lagrange pada masalah relaksasi Lagrange dapat ditentukan dengan menggunakan metode subgradien atau metode branch and bound. Pada karya ilmiah ini, nilai pengali Lagrange diperoleh dengan menggunakan metode subgradien. Pada karya ilmiah ini juga dilakukan pembandingan antara penyelesaian IP dengan relaksasi Lagrange dan penyelesaian IP dengan pemrograman linear relaksasi. Dalam karya ilmiah ini digunakan software LINDO 6.1 untuk memperoleh solusi dari masalah pemrograman linear relaksasi dan masalah relaksasi Lagrange.