METODE AFFINE SCALING SEBAGAI ALTERNATIF PENYELESAIAN MASALAH PROGRAM LINEAR

Abstract

Program linear adalah salah satu teknik riset operasi untuk menyelesaikan suatu perencanaan aktifitas yang  dibentuk dalam suatu model matematika agar tujuan yang diinginkan dapat tercapai. Penelitian ini bertujuan untuk mengenalkan cara menyelesaikan masalah program linear dengan menggunakan metode Affine Scaling. Dalam menyelesaikan permasalahan program linear menggunakan metode Affine Scaling terdapat tiga konsep dasar. Pertama menentukan titik interior awal melalui bagian dalam (interior) daerah layak ke arah solusi yang optimal. Kedua, titik interior bergerak kearah yang meningkatkan nilai fungsi tujuan. Ketiga, mengubah daerah layak untuk memindahkan titik solusi percobaan ke dekat pusatnya sehingga memungkinkan sebuah peningkatan saat konsep kedua diterapkan. Dalam metode Affine Scaling masalah program linear diubah ke dalam bentuk matriks dan vektor. Cara kerja metode Affine Scaling dimulai dari penentuan titik awal yang memenuhi persamaan Ax=b dengan x ≥ 0, x ϵRⁿ dan A merupakan matriks koefisien dari fungsi kendala dan b merupakan matriks batas dari fungsi kendala, transformasi masalah program linear ke ruang transformasi, hitung pemusatan transformasi, arah gradien dan titik solusi baru. Titik solusi baru ditransformasikan lagi ke ruang awal. Iterasi pada metode Affine Scaling dapat dihentikan jika nilai fungsi tujuan telah memenuhi kondisi kurang dari atau sama dengan nilai fungsi tujuan yang telah diperoleh sebelumnya sehingga titik solusi yang optimal diperoleh.

Kata kunci : Program Linear, Algoritma Titik Interior, Metode Affine Scaling