Algoritma Simpleks


Langkah-langkah dalam algoritma simpleks untuk mencari solusi optimal dari suatu masalah pemrograman linier adalah sebagai berikut :

Langkah Pertama

Langkah pertama yang dilakukan adalah menentukan kolom kerja (work column). Kolom kerja ditentukan berdasarkan nilai yang paling negatif dari nilai-nilai yang berada pada baris fungsi obyektif (Z) pada tabel simpleks. Variabel yang berada pada kolom kerja ini akan menjadi entering variabel menggantikan salah satu variabel dasar sebelumnya. Variabel dasar mana yang akan digantikan oleh entering variabel ini ditentukan pada langkah kedua.

Langkah Kedua

Langkah kedua adalah membuat nilai perbandingan antara nilai kanan (NK) dengan nilai pada kolom kerja dari setiap baris, kecuali baris fungsi obyektif. Baris dengan nilai perbandingan yang terkecil akan berperan sebagai pivot. Variabel dasar yang berada pada baris pivot akan menjadi leaving variabel yang akan digantikan oleh entering variabel.

Langkah Ketiga

Langkah ketiga adalah langkah pertama dari langkah-langkah perbaikan solusi. Pada langkah ketiga ini dilakukan perubahan nilai pada baris pivot dengan cara membagi setiap elemen dari baris pivot ini dengan nilai pivot dengan kolom kerja.

Langkah Keempat

Langkah keempat adalah merubah variabel dasar, yang berarti entering variabel masuk menggantikan leaving variabel.

Langkah Kelima

Langkah kelima adalah merubah semua nilai pada baris selain baris pivot dengan cara berikut :

Nilai baru = Nilai lama – (Nilai pada kolom kerja x Nilai baru pada baris pivot).

Langkah Keenam

Langkah keenam adalah memeriksa apakah masih terdapat nilai negatif pada baris fungsi obyektif. Bila ternyata masih ada nilai negatif pada baris tersebut, berarti tabel belum optimal, sehingga perlu dilakukan kembali langkah-langkah penyelesaian di atas hingga diperoleh solusi yang optimal.

Iklan

About encuheryanto

Terkadang seseorang itu terlalu sering membicarakan hal yang tidak beguna bagi dirinya .

Posted on September 18, 2012, in Pengetahuan Umum. Bookmark the permalink. Tinggalkan komentar.

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout /  Ubah )

Foto Google+

You are commenting using your Google+ account. Logout /  Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout /  Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout /  Ubah )

w

Connecting to %s

%d blogger menyukai ini: