METODE PERLUASAN PENDEKATAN KUHN-TUCKER DAN ALGORITMA BRANCH AND BOUND UNTUK PENYELESAIAN MASALAH PEMROGRAMAN BILEVEL LINIER

ATIKA, Prof. Dr. Salmah, M.Si.

2016 | Skripsi | S1 MATEMATIKA

Masalah pemrograman bilevel linier (Linear Bilevel Programming (BLP) Problem) merupakan masalah multi-level dengan dua tingkat, yang terdiri dari masalah tingkat atas (leader) dan masalah tingkat bawah (follower). Untuk menyelesaikan permasalahan tersebut, diawali dengan merumuskan model masalah BLP linier menjadi masalah pemrograman one-level menggunakan metode pendekatan Kuhn-Tucker. Proses ini dilakukan dengan mengganti masalah follower dengan kondisi Kuhn-Tucker, kemudian menambahkan sistem yang dihasilkan ke dalam masalah leader. Formula yang terbentuk memuat kendala non-linier berupa persamaan complementary slackness. Selanjutnya, formula tersebut diselesaikan dengan algoritma branch and bound untuk mengatasi kondisi complementary. Algoritma akan mencapai solusi optimal jika kondisi complementary terpenuhi. Selanjutnya, terdapat kelemahan dari metode Kuhn-Tucker dan algoritmabranch and bound dalam menyelesaikan masalah BLP linier dengan kondisi tertentu. Hal ini dapat dilihat dari keluaranya yang berupa solusi infisibel dengan menggunakan program LINGO, yang berarti bahwa solusi optimal dari masalah BLP linier tersebut tidak berada pada daerah induksi. Oleh karena itu, dibentuk definisi baru untuk solusi masalah BLP linier dengan menambahkan tiga asumsi, yaitu himpunan daerah kendala dari masalah BLP linier S merupakan himpunan yang tak kosong dan kompak, himpunan reaksi rasional follower P(x) bernilai tunggal, dan P(x) merupakan pemetaan dari titik ke titik. Berdasarkan definisi ini, diperoleh syarat perlu dan cukup yang menjamin eksistensi solusi optimal dari masalah BLP linier. Selanjutnya, berdasarkan syarat tersebut diperoleh metode perluasan pendekatan Kuhn-Tucker dan algoritma branch and bound, sehingga solusi yang dihasilkan adalah solusi optimal global. Pada akhir pembahasan, diberikan contoh penyelesaian masalah BLP linier menggunakan metode perluasan pendekatan Kuhn-Tucker dan algoritma branch and bound.

The linear bilevel programming (BLP) problem is two grade of multi-level problem, consisting of upper-level (leader) and lower-level (follower). To solve this problem, it is begun by formulating a model of linear BLP problem into a one-level programming problem using Kuhn-Tucker approaches. This process firstly is conducted by replacing the follower�s problem with his Kuhn-Tucker conditions and add the yielded system to leader�s problem. The formed formula contains a nonlinear problem, a complementary slackness equation constraint. At the final stage, it is solved by branch and bound algorithm to suppress the complementary term. The algorithm will achieve the optimal solution if complementary condition is fulfilled. Then, there are deficiency of Kuhn-Tucker method and branch and bound algorithms in solving the BLP problem with particular cases. This can be seen from the infeasibility in the output of it using LINGO tools, which means that the solution of it is not occur in the inducible region. Therefore, it is formed new definition for linear BLP problem solution by adding three assumtions that is the constraint region of the linear BLP problem S is nonempty and compact, follower�s reactional reaction set P(x) is single-valued and P(x) is a point-to-point map. Based on this definition, it is gained the condition of necessary and sufficient which guarantee the existence of the solution of the linear BLP problem. Then, based on these conditions obtained by the extended method of Kuhn-Tucker approach and branch and bound algorithm, so that the resulting solution is the global optimal solution. In the last of this paper, it is also give the solution of one example for linear BLP problem using the extended Kuhn-Tucker approach and branch and bound algorithm.

Kata Kunci : Pemrograman bilevel linier, Kondisi Kuhn-Tucker, Algoritma branch and bound, Optimisasi