ANALISIS METODE KARMARKAR UNTUK MENYELESAIKAN MASALAH PROGRAM LINIER

Abstract

Penelitian ini bertujuan mengetahui dasar matematis dalam metode Karmarkar, mengetahui penyelesaian masalah program linier dengan metode Karmarkar, serta menganalisis penyelesaian masalah program linier dengan metode simpleks dan metode Karmarkar. Penelitian ini dilakukan dengan studi literatur. Penyelesaian program linier dengan metode Karmarkar, mula-mula harus diubah dalam bentuk kanonik Karmarkar, kemudian diselesaikan dengan metode Karmarkar. Penyelesaian program linier dengan metode Karmarkar dilakukan secara manual dan dengan menggunakan program Matlab, kemudian hasil dari keduanya dilakukan analisis. Kesimpulannya adalah bahwa metode Karmarkar adalah suatu metode titik interior yang menembus dari daerah fisibel untuk mencapai suatu solusi optimum sedangkan metode simpleks bergerak dari titik ekstrim menuju ke penyelesain optimum. Titik interior dilambangkan dengan banyaknya variabel. Menyelesaikan masalah dengan metode Karmarkar yaitu dengan mengubah bentuk dasar program linier ke bentuk kanonik Karmarkar, dilanjutkan dengan perhitungan iterasi hingga nilai  minimum (kanonik Karmarkar) kurang dari 0,05. Metode Karmarkar membutuhkan perhitungan yang relatif lebih besar untuk persoalan program linier yang berukuran kecil dan lebih cepat diselesaikan dengan metode simpleks, sedangkan untuk kendala yang lebih besar metode Karmarkar lebih efisien dibandingkan metode simpleks.

This research purpose is to determine the basic mathematical Karmarkarmethods, to know the solving linear programs with Karmarkar method, and to analyze the problem solving linear program with the simplex method and Karmarkar method. This research was literature study. The completion of linear programs with Karmarkar method was done manually by using Matlab program, then the results of both was analyzed. The conclusion is the Karmarkar method is a method that penetrates the interior point of the feasible region to achieve an optimum solution while the simplex method moves from the extreme point toward the optimum completion. The interior point is denoted by is the sum of variable. To resolve the problem with the Karmarkar method is to change the basic shape into a canonical form linear program of Karmarkar, it is followed by the calculation of iterations until a minimum value of Z (canonical of Karmarkar) is less than 0,05. Linear programming problems are usually small, Karmarkar method requires the calculation of a relatively larger and more quickly solved by the simplex method. Karmarkar method is faster than the simplex method.