## METODE KARMARKAR SEBAGAI ALTERNATIF PENYELESAIAN MASALAH PEMROGRAMAN LINEAR

## Bayu Prihandono, Meilyna Habibullah, Evi Noviani
Program Studi Matematika Fakultas MIPA Universitas Tanjungpura Jl. Prof. Dr. H. Hadari Nawawi, Pontianak, Kalimantan Barat
Email
: bayuprihandono@math.untan.ac.id , alyn@yahoo.com , evinoviani@math.untan. ac.id
ABSTRAK. Pemrograman linear adalah alat untuk menyelesaikan suatu perencanaan aktivitas yang telah dibentuk dalam suatu model matematis agar tujuan yang diinginkan dapat tercapai. Penelitian ini  bertujuan untuk mengenalkan cara menyelesaikan masalah pemrograman linear dengan menggunakan metode Karmarkar. Pada metode Karmarkar, masalah pemrograman linear dituliskan dalam bentuk khusus yang disebut bentuk kanonik Karmarkar. Jika terdapat masalah pemrograman linear standar akan diselesaikan dengan metode Karmarkar, maka terlebih dahulu masalah tersebut harus dikonversi ke dalam bentuk kanonik Karmarkar. Cara kerja metode Karmarkar dimulai dari penentuan titik awal yang berdasarkan jumlah variabel, kemudian diikuti oleh perhitungan jari-jari, jangkauan penyelesaian, dan nilai kriteria pemberhentian. Iterasi pada metode Karmarkar dapat dihentikan jika nilai fungsi tujuan telah memenuhi kondisi kurang dari kriteria pemberhentian yang telah ditetapkan sebelumnya, sehingga titik solusi optimal telah diperoleh.
Kata kunci : pemrograman linear, algoritma karmarkar dan metode titik interior .

## 1. Pendahuluan
Penerapan pemrograman linear sebagai salah satu alat pengambilan keputusan telah banyak digunakan dalam penjabaran berbagai situasi pada kehidupan nyata, contohnya di bidang industri, pertanian, transportasi, ekonomi, dan lain sebagainya  [7]. Pemrograman linear membantu menyelesaikan suatu masalah yang meliputi perencanaan aktivitas untuk mendapatkan hasil yang optimal, yaitu sebuah hasil terbaik diantara semua kemungkinan solusi yang ada. Penyelesaian masalah pemrograman linear dapat menggunakan beberapa metode, diantaranya metode grafik, metode simpleks, metode dual simpleks, dan metode Karmarkar [5].
Penyelesaian masalah pemrograman linear menggunakan grafik maupun tabel simpleks sudah menjadi hal yang umum, maka dari itu akan diperkenalkan suatu metode yang cara pengerjaannya berbeda dengan kedua metode tersebut. Untuk menyelesaikan masalah pemrograman linear yang mempunyai lebih dari dua variabel tidak dapat dilakukan dengan metode grafik, yang mungkin adalah dengan tabel simpleks. Namun untuk masalah pemrograman linear dengan variabel yang banyak, proses penyelesaiannya akan menghabiskan waktu yang cukup  lama. Hal ini dikarenakan metode simpleks menggunakan waktu eksponensial, yang berarti semakin besar ukuran masalah pemrograman linear
maka semakin lama juga waktu yang digunakan untuk menyelesaikan masalah tersebut [4].
Pada tahun 1984, seorang ilmuan bernama Narendra Karmarkar berusaha mengembangkan suatu metode baru untuk menyelesaikan masalah pemrograman linear berukuran besar dengan waktu pengerjaan yang cepat (efisien) yang dinamakan Metode Karmarkar [5]. Metode ini dimulai dari satu titik yang berada dalam daerah layak, kemudian dilanjutkan ke arah gradien yang diproyeksikan untuk memperoleh titik pemecahan yang baru sehingga diperoleh penyelesaian masalah pemrograman linear yang optimum. Titik itu secara ketat merupakan titik interior yang berarti semua titik koordinatnya harus bernilai positif, maka dari itu metode ini juga disebut metode titik interior [9].
Perbedaan mendasar pada metode Karmarkar dengan metode-metode sebelumnya adalah jika pada metode lain, pencarian titik-titik optimal dilakukan dengan menelusuri titik-titik yang terdapat di batas-batas daerah layak. Sedangkan untuk metode Karmarkar, titik-titik optimal dicari melalui penyelidikkan sebarang titik dalam pada daerah layak. Ide ini lebih menuju pada ada kemungkinan bahwa titik-titik optimal tidak selalu berada pada garis batas di daerah layak namun terdapat pula di dalam daerah layak.

## 2. Tinjauan Pustaka

## 2.1 Titik Dalam (Titik Interior)
Pada bagian latar belakang telah dikatakan bahwa metode Karmarkar juga disebut  sebagai metode titik dalam. Pada penelitian ini titik dalam yang didefinisikan adalah pada ℝ 𝑛𝑛 . Didefinisikan suatu jarak 𝑑𝑑 ( 𝐮𝐮 , 𝐯𝐯 ) pada ℝ 𝑛𝑛 , untuk setiap vektor 𝐮𝐮 dan 𝐯𝐯 ∈ ℝ 𝑛𝑛 , 𝑑𝑑 ( 𝐮𝐮 , 𝐯𝐯 ) dihitung menggunakan Rumus [1]: 𝑑𝑑 ( 𝐮𝐮 , 𝐯𝐯 ) = ‖𝐮𝐮 − 𝐯𝐯‖ = � ( 𝑢𝑢 1 − 𝑣𝑣 1 ) 2 + ( 𝑢𝑢 2 − 𝑣𝑣 2 ) 2 + ⋯ + ( 𝑢𝑢 𝑛𝑛 − 𝑣𝑣 𝑛𝑛 ) 2 . Himpunan pada ℝ 𝑛𝑛 yang dilengkapi dengan jarak 𝑑𝑑 ( 𝐮𝐮 , 𝐯𝐯 ) dituliskan dengan �ℝ 𝑛𝑛 , 𝑑𝑑 ( 𝐮𝐮 , 𝐯𝐯 ) � .
Sebelum berbicara mengenai titik dalam  pada ℝ 𝑛𝑛 ,  terlebih dahulu diberikan suatu definisi persekitaran pada ℝ 𝑛𝑛 , yaitu sebagai berikut:
Definisi 2.1.1 [3]
Jika diberikan �ℝ 𝑛𝑛 , 𝑑𝑑 ( 𝐮𝐮 , 𝐯𝐯 ) � , untuk sebarang vektor 𝐯𝐯 ∈ ℝ 𝑛𝑛 dan konstanta real
𝑟𝑟 > 0 , maka himpunan 𝑁𝑁 𝑟𝑟 ( 𝐯𝐯 ) = { 𝐮𝐮 ∈ ℝ 𝑛𝑛 ∶ 𝑑𝑑 ( 𝐮𝐮 , 𝐯𝐯 ) < 𝑟𝑟 }
disebut persekitaran vektor 𝐯𝐯 dengan  jari-jari 𝑟𝑟 . Definisi 2.1.2 [3] Jika diberikan �ℝ 𝑛𝑛 , 𝑑𝑑 ( 𝐮𝐮 , 𝐯𝐯 ) � , dengan vektor 𝐮𝐮 ∈ ℝ 𝑛𝑛 dan ada sebuah himpunan 𝐴𝐴 ⊂ ℝ 𝑛𝑛 , maka vektor 𝐮𝐮 disebut titik dalam himpunan 𝐴𝐴 jika ada bilangan real 𝑟𝑟 > 0 sehingga memenuhi 𝑁𝑁 𝑟𝑟 ( 𝐮𝐮 ) ⊂ 𝐴𝐴 .

## 2.2 Transformasi Proyektif
Transformasi proyektif merupakan transformasi yang dapat digunakan untuk menggerakkan suatu vektor pada ℝ 𝑛𝑛 dari daerah asal menuju suatu daerah baru. Transformasi ini disebut proyektif karena selalu mengarahkan suatu vektor pada ℝ 𝑛𝑛 menuju ke pusat suatu daerah baru yang juga pada ℝ 𝑛𝑛 , sehingga vektor
tersebut tidak akan pernah keluar dari batas yang telah ditentukan. Ketentuan pada penggunaan transformasi  proyektif  adalah  dengan memberikan suatu vektor 𝐱𝐱 = ( 𝑥𝑥 1 , 𝑥𝑥 2 , … , 𝑥𝑥 𝑛𝑛 ) ,  dengan 𝐱𝐱 ∈ ℝ 𝑛𝑛 dan suatu matriks diagonal ( 𝐷𝐷 𝑘𝑘 ) ,  yang didefinisikan  oleh 𝐷𝐷 𝑘𝑘 = 𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑 { 𝑥𝑥 1 , 𝑥𝑥 2 , … , 𝑥𝑥 𝑛𝑛 } ,  dengan entri-entri dari diagonal matriks tersebut adalah 𝑥𝑥 1 , 𝑥𝑥 2 , … , 𝑥𝑥 𝑛𝑛 , maka hasil transformasi dari 𝐱𝐱 ke 𝐱𝐱 ′ yang ditulis dengan 𝑇𝑇 ( 𝐱𝐱 , 𝐱𝐱 ′ ) adalah sebagai berikut [6]:
𝐱𝐱 ′ = 𝐷𝐷 𝑘𝑘 −1 𝐱𝐱 𝟏𝟏𝐷𝐷 𝑘𝑘 −1 𝐱𝐱 dengan: 𝟏𝟏 = (1,1, … ,1) 𝐷𝐷 𝑘𝑘 −1 = invers dari matriks diagonal 𝐷𝐷 𝑘𝑘 𝐱𝐱 = titik awal yang telah ditentukan 𝐱𝐱 ′ = titik hasil transformasi proyektif dengan 𝟏𝟏 dan 𝐱𝐱 ′ berada pada ℝ 𝑛𝑛
Teorema 2.2.1 [8] Jika suatu vektor 𝐱𝐱 = ( 𝑥𝑥 1 , 𝑥𝑥 2 , … , 𝑥𝑥 𝑛𝑛 ) pada ℝ 𝑛𝑛 ditransformasi menggunakan 𝑇𝑇 ( 𝐱𝐱 , 𝐱𝐱 ′ ) , maka akan menghasilkan vektor 𝐱𝐱 ′ = � 1 𝑛𝑛 , 1 𝑛𝑛 , … , 1 𝑛𝑛 � .
Bukti: Ambil sebarang suatu vektor pada ℝ 𝑛𝑛 , misal 𝐱𝐱 = ( 𝑥𝑥 1 , 𝑥𝑥 2 , … , 𝑥𝑥 𝑛𝑛 ) ∈ ℝ 𝑛𝑛 .
Akan dibuktikan bahwa hasil dari transformasi 𝐱𝐱 adalah 𝐱𝐱 ′ = � 1 𝑛𝑛 , 1 𝑛𝑛 , … , 1 𝑛𝑛 � .
Didefinisikan suatu matriks diagonal sebagai berikut:
𝐷𝐷 𝑘𝑘 −1 = ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ 1 𝑥𝑥 1 0 ⋯ 0 0 1 𝑥𝑥 2 ⋯ 0 ⋮ ⋮ ⋱ ⋮ 0   0       0 1 𝑥𝑥 𝑛𝑛 ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤
kemudian dilakukan perhitungan dengan menggunakan rumus:
𝐱𝐱 ′ = 𝐷𝐷 𝑘𝑘 −1 𝐱𝐱 𝟏𝟏𝐷𝐷 𝑘𝑘 −1 𝐱𝐱 maka 𝐱𝐱 ′ = ⎣ ⎢ ⎢ ⎢ ⎢ ⎡ 1 𝑥𝑥 1 0 ⋯ 0 0 1 𝑥𝑥 2 ⋯ 0 ⋮ ⋮ ⋱ ⋮ 0   0       0 1 𝑥𝑥 𝑛𝑛 ⎦ ⎥ ⎥ ⎥ ⎥ ⎤ � 𝑥𝑥 1 𝑥𝑥 2 ⋮ 𝑥𝑥 𝑛𝑛 � [1 1 ⋯ 1] ⎣ ⎢ ⎢ ⎢ ⎢ ⎡ 1 𝑥𝑥 1 0 ⋯ 0 0 1 𝑥𝑥 2 ⋯ 0 ⋮ ⋮ ⋱ ⋮ 0   0       0 1 𝑥𝑥 𝑛𝑛 ⎦ ⎥ ⎥ ⎥ ⎥ ⎤ � 𝑥𝑥 1 𝑥𝑥 2 ⋮ 𝑥𝑥 𝑛𝑛 �
𝐱𝐱 ′ = � 1 1 ⋮ 1 � [1 1 ⋯ 1] � 1 1 ⋮ 1 � = � 1 1 ⋮ 1 � [1 + 1 + ⋯ + 1]   = � 1 1 ⋮ 1 � 𝑛𝑛 = ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ 1 𝑛𝑛 1 𝑛𝑛 ⋮ 1 𝑛𝑛⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ 𝐱𝐱 ′ = � 1 𝑛𝑛 , 1 𝑛𝑛 , … , 1 𝑛𝑛� .
Berdasarkan hasil perhitungan diperoleh hasil transformasi dari 𝐱𝐱 adalah suatu vektor 𝐱𝐱 ′ = � 1 𝑛𝑛 , 1 𝑛𝑛 , … , 1 𝑛𝑛 � , jadi dapat disimpulkan bahwa Teorema 2.2.1 terbukti.
Transformasi proyektif memiliki invers sebagai berikut:
𝐱𝐱 = 𝐷𝐷 𝑘𝑘 𝐱𝐱 ′ 𝟏𝟏𝐷𝐷 𝑘𝑘 𝐱𝐱 ′ .

## 2.3  Jari – Jari dan Jangkauan Penyelesaian
Pada umumnya jari-jari adalah jarak dari titik pusat ke daerah batas suatu lingkaran di bidang berdimensi dua. Tetapi pada metode Karmarkar, jari-jari yang dimaksud bukanlah jari-jari lingkaran, melainkan jarak antara titik pusat suatu daerah berdimensi 𝑛𝑛 dengan titik batas suatu daerah yang berdimensi setingkat lebih sederhana (daerah berdimensi ( 𝑛𝑛 − 1) ), yang dinotasikan dengan ( 𝑟𝑟 ) . Langkah menghitung jari-jari dimulai dengan mengambil suatu titik pusat pada daerah berdimensi 𝑛𝑛 , yaitu 𝐲𝐲 0 = � 1 𝑛𝑛 , 1 𝑛𝑛 , 1 𝑛𝑛 … , 1 𝑛𝑛 � dan suatu titik yang berada pada daerah berdimensi ( 𝑛𝑛 − 1 ), yaitu 𝐲𝐲 ( 𝑛𝑛−1 ) = � 0, 1 ( 𝑛𝑛−1 ) , 1 ( 𝑛𝑛−1 ) , … , 1 ( 𝑛𝑛−1 ) � .
Sebagai ilustrasi mengenai jari-jari pada metode Karmarkar, diberikan Gambar 2.3.1 sebagai berikut (dengan mengasumsikan daerah tiga dimensi adalah daerah berdimensi 𝑛𝑛 dan daerah dua dimensi adalah daerah berdimensi ( 𝑛𝑛 − 1) ).
Gambar 2.3.1 Ilustrasi jari-jari pada metode Karmarkar
Kemudian dengan menggunakan rumus jarak antara dua vektor pada ℝ 𝑛𝑛 , dilakukan perhitungan sebagai berikut:
𝑑𝑑�𝐲𝐲 0 , 𝐲𝐲 ( 𝑛𝑛−1 ) � = �𝐲𝐲 0 − 𝐲𝐲 ( 𝑛𝑛−1 ) � sehingga rumus jari-jari yang digunakan pada metode karmarkar adalah:
𝑟𝑟 = 1 �𝑛𝑛 ( 𝑛𝑛 − 1) .
Selain ada jari-jari, pada metode Karmarkar juga digunakan sebuah jangkauan penyelesaian, yang dinotasikan dengan 𝛼𝛼 . Jangkauan penyelesaian ini berguna untuk memperkecil nilai dari jari-jari awal pada gambaran bola atau lingkaran yang menjadi daerah layak untuk solusi masalah pemrograman linear. Sehingga gambaran bola yang baru juga menjadi lebih kecil. Ketentuan yang diberikan untuk menghitung jangkauan penyelesaian pada metode Karmarkar adalah sebagai berikut [4]:
𝛼𝛼 = ( 𝑛𝑛 − 1)
3 𝑛𝑛 dengan 𝑛𝑛 adalah jumlah variabel.

## 2.4 Matriks Proyeksi dan Gradien Proyeksi
Dalam metode Karmarkar selain menggunakan matriks untuk proses perhitungan, matriks juga digunakan untuk memindahkan suatu vektor dari bentuk asal ke daerah proyeksinya. Matriks ini disebut matriks proyeksi dan hasil dari proyeksi vektor disebut gradien proyeksi. Pada metode Karmarkar matriks proyeksi (dinotasikan dengan 𝑃𝑃 ), adalah suatu matriks berukuran 𝑚𝑚 × 𝑛𝑛 yang dituliskan sebagai berikut [2]:
𝑃𝑃 = �𝐴𝐴𝐷𝐷 𝑘𝑘 𝟏𝟏 �
dengan:
𝐴𝐴 adalah matriks koefisien dari sistem persamaan pada bentuk kanonik
Karmarkar.
𝐷𝐷 𝑘𝑘 adalah matriks diagonal yang setiap entri pada diagonalnya merupakan elemen dari vektor 𝐱𝐱 = ( 𝑥𝑥 1 , 𝑥𝑥 2 , … , 𝑥𝑥 𝑛𝑛 ) pada ℝ 𝑛𝑛 .
𝟏𝟏 adalah vektor pada ℝ 𝑛𝑛 yang setiap elemennya adalah satu.
Selanjutnya dengan bantuan matriks proyeksi, akan dihitung perpindahan suatu gradien, yang dimaksud gradien pada metode Karmarkar adalah suatu vektor pada ℝ 𝑛𝑛 yang setiap elemennya merupakan koefisien dari fungsi tujuan pada bentuk kanonik Karmarkar (dinotasikan dengan 𝐜𝐜 𝐓𝐓 ) . Cara menentukan gradien proyeksi (dinotasikan dengan 𝐜𝐜 𝑝𝑝 ) pada metode Kararkar adalah sebagai berikut [2]:
𝐜𝐜 𝑝𝑝 = [ 𝐼𝐼 − 𝑃𝑃 𝑇𝑇 ( 𝑃𝑃𝑃𝑃 𝑇𝑇 ) −1 𝑃𝑃 ] 𝐜𝐜̅ 𝑇𝑇
dengan: 𝐼𝐼 adalah suatu matriks identitas,
𝑃𝑃 𝑇𝑇 adalah matriks transpose dari matriks proyeksi,
( 𝑃𝑃𝑃𝑃 𝑇𝑇 ) −1 adalah invers dari perkalian antara matriks proyesi dengan matriks transposnya, dan
𝐜𝐜̅ 𝑇𝑇 adalah suatu vektor dari hasil kali antara vektor koefisien fungsi tujuan ( 𝐜𝐜 𝐓𝐓 ) dengan matriks diagonal ( 𝐷𝐷 𝑘𝑘 ) .

## 3. Metode penelitian
Penelitian  ini merupakan penelitian yang berupa studi literatur. Untuk mempelajari hal-hal yang akan dibahas penulis menggunakan sumber berupa artikel, jurnal, dan buku. Tahapan penelitian ini dimulai dari mempelajari teori tentang titik dalam, masalah pemrograman linear, matriks dan operasi matriks, vektor, dan transformasi proyektif.

## 4. Hasil dan pembahasan

## 4.1 Bentuk Kanonik Karmarkar
Metode Karmarkar menyajikan masalah pemrograman linear dengan suatu bentuk khusus yang disebut bentuk kanonik Karmarkar. Jika terdapat masalah pemrograman linear dalam bentuk standar, maka masalah standar tadi harus dikonversikan menjadi masalah yang setara dengan bentuk kanonik Karmarkar dan kemudian diselesaikan dengan langkah-langkah yang telah ditetapkan [2]. Pada metode Karmarkar, masalah pemrograman linear  ditulis dalam bentuk khusus sebagai berikut:
Minimumkan 𝐜𝐜 𝐓𝐓 𝐱𝐱 kendala
𝐴𝐴𝐱𝐱 = 𝟎𝟎 𝟏𝟏𝐱𝐱 = 1 𝐱𝐱 ≥ 0 dimana 𝒙𝒙 = [ 𝑥𝑥 1 𝑥𝑥 2 … 𝑥𝑥 𝑛𝑛 ] 𝑇𝑇 , 𝐴𝐴 adalah suatu matriks berukuran 𝑚𝑚 × 𝑛𝑛 , 𝐜𝐜 𝐓𝐓 = [ 𝑐𝑐 1 𝑐𝑐 2 … 𝑐𝑐 𝑛𝑛 ] , dan 𝐴𝐴𝐱𝐱 = 𝟎𝟎 adalah sebuah sistem persamaan linear homogen dengan m persamaan linear dan n variabel, 0 adalah suatu vektor kolom yang setiap elemennya adalah nol,  dan 𝟏𝟏 adalah suatu vektor yang setiap elemennya adalah satu. Masing-masing dari 𝐴𝐴 , 𝐜𝐜 𝐓𝐓 , 𝐱𝐱 , 𝟎𝟎 , dan 𝟏𝟏 berada pada ℝ 𝑛𝑛 . Selain itu, keberlakuan metode Karmarkar tergantung pada dua kondisi berikut:
a. Titik awal harus berada di dalam pembatas yang homogen dan nonegatif.
( 𝐱𝐱 0 = � 1 𝑛𝑛 , 1 𝑛𝑛 , … , 1 𝑛𝑛 � berada pada 𝐴𝐴𝐱𝐱 = 𝟎𝟎 dan 𝟏𝟏𝐱𝐱 = 1 ,  dengan n adalah  jumlah variabel).
b. Nilai optimal fungsi tujuan adalah nol.
Adapun cara untuk mengkonversikan masalah pemrograman linear standar ke bentuk kanonik Karmarkar adalah sebagai berikut: [9]. Diberikan suatu masalah pemrograman linear dalam bentuk standar berikut:
Minimumkan 𝐜𝐜 𝐓𝐓 𝐱𝐱 kendala
𝐴𝐴𝐱𝐱 ≥ 𝐛𝐛 𝐱𝐱 ≥ 0
dengan 𝐴𝐴 , 𝐜𝐜 𝐓𝐓 , 𝐱𝐱 , 𝐛𝐛 , dan 𝟏𝟏 berada pada ℝ 𝑛𝑛 .
Langkah mengkonversi masalah pemrograman linear tersebut  ke bentuk kanonik Karmarkar adalah sebagai berikut:
Fungsi kendala pada pemrograman linear distandarisasi menjadi:
Minimumkan 𝐜𝐜 𝐓𝐓 𝐱𝐱
kendala 𝐴𝐴𝐱𝐱 − 𝑆𝑆 = 𝐛𝐛 𝐱𝐱 , 𝑆𝑆 ≥ 0 dengan 𝑆𝑆 adalah variabel slack yang digunakan untuk merubah pertidaksamaan menjadi persamaan pada fungsi kendala masalah pemrograman linear.
Kemudian dipilih nilai batasan yang lebih besar dari semua konstanta nilai kanan pada fungsi kendala, dan dimisalkan nilai ini adalah 𝑈𝑈 . Pemilihan 𝑈𝑈 yang besar diasumsikan akan melebihi ruang pemecahan layak, sehingga tidak merubah ruang solusi pada masalah pemrograman linear. Selain itu, pemilihan nilai 𝑈𝑈 yang sangat besar juga tidak akan merubah nilai fungsi tujuan, hal ini dikarenakan setiap koefisien fungsi tujuan juga akan dikalikan dengan 𝑈𝑈 . Setelah itu didefinisikan:
𝑥𝑥 1 + 𝑥𝑥 2 + 𝑥𝑥 3 + ⋯ + 𝑥𝑥 𝑛𝑛 ≤ 𝑈𝑈 selanjutnya pertidaksamaan tersebut distandarisasi menjadi:
𝑥𝑥 1 + 𝑥𝑥 2 + 𝑥𝑥 3 + ⋯ + 𝑥𝑥 𝑛𝑛 + 𝑥𝑥 𝑛𝑛+1 = 𝑈𝑈 .
Selanjutnya fungsi kendala yang telah distandarisasi dirubah ke bentuk sistem persamaan linear homogen seperti pada bentuk kanonik Karmarkar. Perubahan ini dilakukan dengan cara mengalikan sisi kanan setiap kendala dengan ( 𝑥𝑥 1 + 𝑥𝑥 2 + 𝑥𝑥 3 + ⋯ + 𝑥𝑥 𝑛𝑛 + 𝑥𝑥 𝑛𝑛+1 )/ 𝑈𝑈 .  Koefisien  fungsi tujuan dikalikan dengan nilai U yang telah dipilih sebelumnya  sehingga diperoleh fungsi tujuan baru pada masalah pemrograman linear seperti berikut:
Minimumkan ( 𝑈𝑈𝐜𝐜 𝐓𝐓 ) 𝐱𝐱 .
Setelah diperoleh sistem persamaan homogen dan fungsi tujuan yang baru dari hasil point a-d, hal ini berarti telah dikonversi menjadi bentuk kanonik Karmarkar dan susunan dari hasil konversinya adalah sebagai berikut:
Minimumkan ( 𝑈𝑈𝐜𝐜 𝐓𝐓 ) 𝐱𝐱
batasan 𝑨𝑨𝐱𝐱 = 𝟎𝟎 𝟏𝟏𝐱𝐱 = 1 𝐱𝐱 ≥ 0 .

## 4.2  Langkah-Langkah Penyelesaian Masalah Pemrograman Linear dengan Metode Karmarkar
Setelah bentuk kanonik karmarkar terbentuk, daerah layak dari masalah Karmarkar adalah titik potong daerah berdimensi ( 𝑛𝑛 − 𝑚𝑚 ) yang diberikan oleh sistem persamaan linear homogen 𝐴𝐴𝐱𝐱 = 𝟎𝟎 pada daerah 𝑆𝑆 𝑥𝑥 = { 𝐱𝐱 : 𝟏𝟏𝐱𝐱 = 𝟏𝟏 , 𝐱𝐱 ≥ 0} yang berdimensi ( 𝑛𝑛 − 1) . Hasil dari titik potong ini adalah suatu daerah yang berdimensi ( 𝑛𝑛 − 𝑚𝑚 − 1) . Kemudian titik terbaru 𝐱𝐱 𝑘𝑘 pada daerah 𝑆𝑆 𝑥𝑥 ditransformasikan ke daerah baru 𝑆𝑆 𝑦𝑦 = { 𝐲𝐲 : 𝟏𝟏𝐲𝐲 = 1, 𝐲𝐲 ≥ 0} yang berdimensi ( 𝑛𝑛 − 1) . Hasil dari transformasi ini adalah sebuah titik 𝐲𝐲 0 = � 1 𝑛𝑛 , 1 𝑛𝑛 , … , 1 𝑛𝑛 � yang merupakan pusat dari daerah 𝑆𝑆 𝑦𝑦 .  Daerah layak pada ruang y berlaku sebagai solusi untuk 𝑥𝑥 dalam 𝑆𝑆 𝑥𝑥 , sehingga vektor 𝐱𝐱 dapat diperoleh dengan cara:
𝐱𝐱 = 𝐷𝐷 𝑘𝑘 𝐲𝐲 𝟏𝟏𝐷𝐷 𝑘𝑘 𝐲𝐲 .
Untuk tahap selanjutnya,  masalah  Kamarkar  ditransformasi ke dalam suatu masalah pada ruang 𝑦𝑦 sebagai berikut:
Minimumkan 𝐜𝐜 𝐓𝐓 𝐷𝐷 𝑘𝑘 𝐲𝐲
𝟏𝟏𝐷𝐷 𝑘𝑘 𝐲𝐲 dengan kendala
𝑃𝑃𝐲𝐲 = 𝑃𝑃 0 𝐲𝐲 ≥ 0 dengan: 𝐜𝐜̅ 𝐓𝐓 = 𝐜𝐜 𝐓𝐓 𝐷𝐷 𝑘𝑘 , 𝑃𝑃 = �𝐴𝐴𝐷𝐷 𝑘𝑘 𝟏𝟏 � dan 𝑃𝑃 0 = �𝟎𝟎 1 � .
Solusi terbaik dari masalah  ini  akan menghasilkan sebuah solusi layak yang baru. Untuk menjelaskan batasan ini, dapat dilakukan dengan cara mengasumsikan bola 𝐵𝐵 ( 𝐲𝐲 0 , 𝑟𝑟 ) pada bidang yang berdimensi n dengan pusat di 𝐲𝐲 0 = � 1 𝑛𝑛 , 1 𝑛𝑛 , … , 1 𝑛𝑛 � dan jari-jari r . Titik potong bola ini dengan daerah  batasan { 𝐲𝐲 : 1 𝐲𝐲 = 1} adalah sebuah bola berdimensi ( 𝑛𝑛 − 1) dengan pusat dan jari-jari yang sama, yaitu 𝑟𝑟 =
1 �𝑛𝑛 ( 𝑛𝑛−1 ) .
Telah diketahui  bahwa  masalah yang bertujuan meminimumkan 𝐜𝐜̅ 𝐓𝐓 𝐲𝐲 dengan batasan 𝑃𝑃 𝑦𝑦 = 𝑃𝑃 0 , 𝐲𝐲 ≥ 0 dan 𝐲𝐲 ∈ 𝐵𝐵 ( 𝐲𝐲 0 , 𝛼𝛼𝑟𝑟 ) ,  dengan 0 < 𝛼𝛼 < 1 adalah sebuah konstanta. Pemilihan 𝛼𝛼 yang  tepat dapat memperkecil gambaran bola yang semula sehingga bola yang baru memiliki jari-jari 𝛼𝛼𝑟𝑟 . Karena 𝐲𝐲 ≥ 0 , maka titik potong dari bola 𝐵𝐵 ( 𝐲𝐲 0 , 𝛼𝛼𝑟𝑟 ) dengan daerah batasan { 𝐲𝐲 : 1 𝐲𝐲 = 1} ini setara dengan masalah berikut [4]:
Minimumkan 𝐜𝐜̅ 𝐓𝐓 𝐲𝐲 kendala
𝑃𝑃 𝑦𝑦 = 𝑃𝑃 0 ( 𝐲𝐲 − 𝐲𝐲 0 ) 𝑇𝑇 ( 𝐲𝐲 − 𝐲𝐲 0 ) ≤ 𝛼𝛼 2 𝑟𝑟 2
dengan { 𝐲𝐲 : ( 𝐲𝐲 − 𝐲𝐲 0 ) 𝑇𝑇 ( 𝐲𝐲 − 𝐲𝐲 0 ) ≤ 𝛼𝛼 2 𝑟𝑟 2 } adalah gambaran dari bola 𝐵𝐵 ( 𝐲𝐲 0 , 𝛼𝛼𝑟𝑟 ) dan nilai 𝛼𝛼 yang diperkirakan sebesar 𝛼𝛼 = ( 𝑛𝑛 − 1) 3 𝑛𝑛 ⁄ .
Berdasarkan batasan 𝑃𝑃 𝑦𝑦 = 𝑃𝑃 0 yang  didefinisikan oleh daerah ( 𝑛𝑛 − 𝑚𝑚 − 1) dimensi yang melalui nilai dari pusat bola 𝐵𝐵 ( 𝐲𝐲 0 , 𝛼𝛼𝑟𝑟 ) , maka daerah layak pada masalah tersebut adalah sebuah bola berdimensi ( 𝑛𝑛 − 𝑚𝑚 − 1) yang berpusat di 𝐲𝐲 0 . Hal ini menyatakan bahwa solusi optimal dari Masalah tersebut  terpenuhi oleh proyeksi gradien negatif dari fungsi tujuan, yaitu −𝐜𝐜̅ 𝐓𝐓 , yang berpusat di 𝐲𝐲 0 di atas batasan permukaan dari 𝑃𝑃𝐲𝐲 = 𝑃𝑃 0 dan pergeseran dari 𝐲𝐲 0 mendekati arah proyeksi menuju batas dari bola 𝐵𝐵 ( 𝐲𝐲 0 , 𝛼𝛼𝑟𝑟 ) . Kemudian arah proyeksi dari gradien 𝐜𝐜̅ 𝐓𝐓 dinotasikan sebagai 𝐜𝐜 𝑝𝑝 dan solusi optimalnya  disebut sebagai 𝐲𝐲 𝑘𝑘 , sehingga diperoleh:
𝐲𝐲 𝑘𝑘 = 𝐲𝐲 0 − 𝛼𝛼𝑟𝑟 𝐜𝐜 𝑝𝑝 �𝐜𝐜 𝑝𝑝 �
dengan 𝐜𝐜 𝑝𝑝 = [ 𝐼𝐼 − 𝑃𝑃 𝑡𝑡 ( 𝑃𝑃𝑃𝑃 𝑡𝑡 ) −1 𝑃𝑃 ] 𝐜𝐜̅ 𝑡𝑡 . Setelah diperoleh 𝐲𝐲 𝑘𝑘 sebagai solusi maka perbaharuan vektor 𝐱𝐱 𝑘𝑘+1 dalam ruang 𝑥𝑥 diperoleh sebagai berikut [8]:
𝐱𝐱 𝑘𝑘+1 = 𝐷𝐷 𝑘𝑘 𝐲𝐲 𝑘𝑘 𝟏𝟏𝐷𝐷 𝑘𝑘 𝐲𝐲 𝑘𝑘 .
Karena nilai dari 𝐱𝐱 𝑘𝑘+1 telah diperoleh, berarti sebuah langkah iterasi telah terpenuhi dan langkah-langkah sebelumnya dapat diulang untuk memperoleh 𝑘𝑘 tiap satu tingkat.
Penjelasan mengenai langkah kerja metode Karmarkar  secara ilustrasi dapat dilihat pada Gambar 4.2.1 berikut:
Gambar 4.2.1 Ilustrasi langkah kerja metode Karmarkar
Gambar 4.2.2 Ilustrasi daerah nonegatif pada metode
Karmarkar
Selanjutnya  dicari nilai batasan ini yang  berguna untuk menentukan hingga berapa kali iterasi harus dilakukan [2].
𝐿𝐿 = � 1 + 𝑙𝑙𝑙𝑙𝑑𝑑 2 (1 + �𝑐𝑐 𝑗𝑗𝑗𝑗𝑗𝑗𝑥𝑥 � ) + 𝑙𝑙𝑙𝑙𝑑𝑑 2 (1 + 𝑚𝑚 ) + � � 𝑙𝑙𝑙𝑙𝑑𝑑� 1 + �𝑑𝑑 𝑖𝑖𝑗𝑗 �� 2 𝑛𝑛 𝑗𝑗=1 𝑗𝑗 𝑖𝑖=1 �
dengan keterangan sebagai berikut:
�𝑐𝑐 𝑗𝑗𝑗𝑗𝑗𝑗𝑥𝑥 � = bilangan terbesar dari koefisien fungsi tujuan
𝑚𝑚 = jumlah persamaan homogen pada masalah pemrograman linear
�𝑑𝑑 𝑖𝑖𝑗𝑗 � = bilangan entri matriks baris ke- i dan kolom ke- j.
Setelah diperoleh nilai batasan iterasi diatas, kemudian diperhatikan nilai akhir dari setiap iterasi yang sedang dilakukan, jika nilai dari fungsi tujuan sudah memenuhi kriteria 𝐜𝐜 𝐓𝐓 𝐱𝐱 𝑘𝑘 < 2 −𝐿𝐿 , maka iterasi dapat dihentikan dan hal ini berarti masalah bentuk kanonik Karmarkar telah menemui titik solusi optimal yaitu 𝐱𝐱 𝑘𝑘 .
Contoh Diberikan  suatu masalah pemrograman linear dalam bentuk karmarkar sebagai berikut:
Minimumkan 𝑥𝑥 1 + 𝑥𝑥 2 + 𝑥𝑥 4 + 𝑥𝑥 6 kendala
3 𝑥𝑥 1 − 𝑥𝑥 2 + 4 𝑥𝑥 3 − 5 𝑥𝑥 4 + 2 𝑥𝑥 5 + 𝑥𝑥 6 − 2 𝑥𝑥 7 = 0 𝑥𝑥 1 − 4 𝑥𝑥 3 − 𝑥𝑥 4 − 7 𝑥𝑥 6 + 𝑥𝑥 7 = 0 𝑥𝑥 1 + 𝑥𝑥 2 + 𝑥𝑥 3 + 𝑥𝑥 4 + 𝑥𝑥 5 + 𝑥𝑥 6 + 𝑥𝑥 7 = 1 𝑥𝑥 𝑖𝑖 ≥ 0
Penyelesaian:
Formulasi vektor dan matriks pada fungsi tujuan dan fungsi kendala:
𝐜𝐜 𝐓𝐓 = [1 1 0   1 0   1 0] 𝐴𝐴 = � 3 − 1 4 − 5 2    1 − 2 1 0 − 4 − 1 0 − 7 1 �
Perhitungan titik awal ( 𝐱𝐱 0 ) , jari-jari ( 𝑟𝑟 ) , jangkauan penyelesaian ( 𝛼𝛼 ) , dan nilai batasan iterasi ( 𝐿𝐿 ) , masing-masing sebagai berikut:
𝐱𝐱 0 = � 1 7 , 1 7 , 1 7 , 1 7 , 1 7 , 1 7 , 1 7 � 𝑟𝑟 = 1 �𝑛𝑛 ( 𝑛𝑛 − 1) = 1 √ 42 = 0,1543
𝛼𝛼 = ( 𝑛𝑛 − 1) 3 𝑛𝑛 = 6 21 = 0,2857
𝐿𝐿 = � 1 + 𝑙𝑙𝑙𝑙𝑑𝑑
2 (1 + �𝑐𝑐 𝑗𝑗𝑗𝑗𝑗𝑗𝑥𝑥 � ) + 𝑙𝑙𝑙𝑙𝑑𝑑 2 (1 + 𝑚𝑚 ) + � � 𝑙𝑙𝑙𝑙𝑑𝑑� 1 + �𝑑𝑑 𝑖𝑖𝑗𝑗 �� 2 𝑛𝑛 𝑗𝑗=1 𝑗𝑗 𝑖𝑖=1 � 𝐿𝐿 = 24
Nilai kriteria pemberhentian adalah: 𝐜𝐜 𝐓𝐓 𝐱𝐱 𝑘𝑘 < 2 −𝐿𝐿 = 𝐜𝐜 𝐓𝐓 𝐱𝐱 𝑘𝑘 < 2 −24 = 𝐜𝐜 𝐓𝐓 𝐱𝐱 𝑘𝑘 < 0,000000059605 .
Dengan melakukan iterasi seperti pada penjelasan sebelumnya, proses perhitungan berhenti pada iterasi ke-74. Dari hasil iterasi diperoleh nilai 𝐜𝐜 𝐓𝐓 𝐱𝐱 74 = 0,000000053805 , hal ini berarti kondisi 𝐜𝐜 𝐓𝐓 𝐱𝐱 74 < 0,000000059605 telah terpenuhi. Jadi, titik solusi optimal dari masalah pemrograman linear untuk Contoh 3.2 adalah (0,000000013451, 0,000000013451, 0,14294, 0,000000013451, 0,28561, 0,000000013451, 0,57145) dan solusi optimalnya adalah 0,000000053805 .

## 5. Kesimpulan
1. Jika suatu masalah pemrograman linear standar akan diselesaikan dengan menggunakan metode Karmarkar, maka masalah tersebut harus dikonversi ke dalam bentuk kanonik Karmarkar dengan cara sebagai berikut:
a. Menstandarisasi fungsi kendala.
b. Memilih nilai batasan yang diasumsikan tidak melebihi ruang pemecahan layak.
c. Merubah fungsi kendala yang telah distandarisasi ke bentuk sistem persamaan linear homogen.
d. Mengalikan koefisien fungsi tujuan dengan nilai batasan.
e. Menyusun bentuk kanonik Karmarkar yang terdiri dari satu fungsi tujuan dan beberapa sistem persamaan linear homogen.
2. Langkah-langkah penyelesaian masalah pemrograman linear dengan metode Karmarkar adalah sebagai berikut:
a. Pilih titik awal 𝐱𝐱 0 = � 1 𝑛𝑛 , 1 𝑛𝑛 , … , 1 𝑛𝑛 � , kemudian hitung 𝑟𝑟 = � 1 𝑛𝑛 ( 𝑛𝑛−1 ) , 𝛼𝛼 = ( 𝑛𝑛 − 1)/3 𝑛𝑛 , dan
𝐿𝐿 = � 1 + 𝑙𝑙𝑙𝑙𝑑𝑑 2 (1 + �𝑐𝑐 𝑗𝑗𝑗𝑗𝑗𝑗𝑥𝑥 � ) + 𝑙𝑙𝑙𝑙𝑑𝑑 2 (1 + 𝑚𝑚 ) + � � 𝑙𝑙𝑙𝑙𝑑𝑑� 1 + �𝑑𝑑 𝑖𝑖𝑗𝑗 �� 2 𝑛𝑛 𝑗𝑗=1 𝑗𝑗 𝑖𝑖=1 � dengan 𝑛𝑛 adalah jumlah variabel.
b. Kemudian lakukan iterasi dengan cara:
definisikan,
𝐷𝐷 𝑘𝑘 = 𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑�𝑥𝑥 𝑘𝑘 1 , 𝑥𝑥 𝑘𝑘 2 , . . . , 𝑥𝑥 𝑘𝑘 𝑛𝑛 � dan 𝑃𝑃 = �𝐴𝐴 𝐷𝐷 𝑘𝑘 𝟏𝟏 �
kemudian dihitung,
𝐲𝐲 𝑘𝑘 = � 1 𝑛𝑛 , 1 𝑛𝑛 , … , 1 𝑛𝑛 � 𝑇𝑇 + 𝛼𝛼𝑟𝑟 𝐜𝐜 𝑝𝑝 �𝐜𝐜 𝑝𝑝 �
dengan 𝐜𝐜 𝑝𝑝 = [ 𝐼𝐼 − 𝑃𝑃 𝑡𝑡 ( 𝑃𝑃𝑃𝑃 𝑡𝑡 ) −1 𝑃𝑃 ] �𝐜𝐜 𝐓𝐓 𝐷𝐷 𝑘𝑘 � .
c. Untuk solusi dari iterasi, diperoleh dengan:
𝐱𝐱 𝑘𝑘+1 = 𝐷𝐷 𝑘𝑘 𝐲𝐲 𝑘𝑘 𝟏𝟏𝐷𝐷 𝑘𝑘 𝐲𝐲 𝑘𝑘 .
d. Kemudian diperhatikan nilai akhir pada setiap iterasi. Jika pada proses perhitungan sudah memenuhi kondisi 𝐜𝐜 𝐓𝐓 𝐱𝐱 𝑘𝑘 < 2 −𝐿𝐿 , maka iterasi dapat dihentikan dan solusi optimal telah diperoleh, yaitu 𝐱𝐱 𝑘𝑘 .

## Daftar  Pustaka
[1] Anton, H., dan Rorres, C., 2004, Aljabar Linear Elementer , Erlangga, Jakarta.
[2] Bazaraa, M., Jarvis J., and Suherall, H., 1990, Linear Programming and Network Flows . Wiley, New York.
[3] Darmawijaya, S., 2007, Pengantar Analisis Abstrak. Universitas Gadjah Mada, Yogyakarta.
[4] Franklin, J., 1987, Convergence In Karmarkar’s Algorithm For Linear Programming, Siam J. Number. Anal. , Vol. 24. No. 4: 928-935.
[5] Hillier, S.F dan Lieberman, J.G., 2008, Introduction To Operation Research . Penerbit ANDI, Jakarta.
[6] Karmarkar, N.,  1984, A New Polinomial Time Algorithm For Linear Programming, Journal of Combinatorica., 4: 373-385.
[7] Leon, J.S., 2001, Aljabar Linear dan Aplikasinya. Erlangga, Jakarta.
[8] Martin, K.R., 1999, Large Scale Linear and Integer Optimization , Kluwer Academic Publicers, United States of America.
[9] Taha, A.H., 1996, Riset Operasi , Binarupa Aksara, Jakarta.