METODE PATH-FOLLOWING UNTUK MASALAH PROGRAM LINEAR (PATH-FOLLOWING METHOD FOR LINEAR PROGRAMMING PROBLEM)

NURCAHYA YULIAN ASHAR, Dr. Sumardi, M.Si.

2017 | Skripsi | S1 MATEMATIKA

Metode Path-following adalah salah satu metode yang digunakan untuk mencari solusi optimal dari masalah program linear. Metode ini merupakan metode titik interior, yakni algoritma yang memotong daerah fisibel untuk mencari solusi optimal. Dalam algoritmanya, titik awal bergerak menyusuri suatu lintasan yang dinamakan central path untuk mendapatkan solusi optimal yang sesuai. Dalam skripsi ini dibahas teori yang mendasari metode Path-following, yang digunakan untuk pengembangan dan analisis konvergensi algoritmanya. Teori yang mendasarinya yakni Teorema Nilai Rata-rata, Teorema Fungsi Implisit, dan Teorema Lagrange. Dalam skripsi ini akan ditunjukkan bahwa kasus cycling pada masalah program linear, bisa diselesaikan dengan menggunakan metode Path-following.

The Path-following method is one of the methods that is used for searching optimal solution of linear programming problem. This method is an interior point method, in which its algorithm executes by cutting the feasible region to achieve an optimal. In the Path-following algorithm, initial point moves through a path which called by central path to obtain appropriate optimal solution. In this thesis, the main discussion will be the theories underlying Path-following method, which is used to develop and analyze the convergence of its algorithm. Theories underlying this method are Mean Value Theorem, Implicit Function Theorem, and Lagrange Multiplier Theorem. This thesis will show that cycling case on linear programming problem can be solved by using Path-following method.

Kata Kunci : Central path, pengali Lagrange, cycling