Operation Research Program Linear Metode Simplex

Metode Simplex

•      Metode simpleks merupakan prosedur iterasi yang bergerak bertahap dan berulang.

•      Jumlah variabel tidak terbatas

•      Penyelesaian masalah LP dengan metode simplex harus menggunakan bentuk standar.

Bentuk Standar

Bentuk standar LP memiliki sifat sbb. :

2. Seluruh fungsi kendala harus berbentuk persamaan ( bertanda = ).
3. Ruas kanan non negatif.
4. Seluruh variabel merupakan variabel non negatif.
5. Fungsi tujuan dapat berupa maksimasi atau minimasi.

Merubah Ke Bentuk Standar

1. Fungsi Kendala (constraint)
2. Kendala bertanda “≤” diubah menjadi persamaan dengan  menambah  “Variabel Slack” pada ruas kiri fungsi kendala.

Contoh:

_•           X_{1      +      6X2                                       ≤  10}

_•           X_{1      +      6X2     +  S1                          ≤  10}

_{Merubah Ke Bentuk Standar}

2. _Variabel

_{•          Jika variable Xj tidak terbatas dalam tanda, dapat dinyatakan sebagai dua variable non negatif dengan menggunakan subsitusi.}

                _{Xj = Xj‘ − Xj”            ;               dimana : Xj‘ dan Xj” ≥ 0}

_{•          Subsitusi dilakukan pada seluruh fungsi kendala dan fungsi tujuan.}

_{•          Fungsi Tujuan}

_{•          Bentuk maksimasi = nilai negatif dari bentuk minimasi.}

_{•          Berlaku juga untuk sebaliknya.}

_{Penyelesaian Simpleks}

_{•          Metode simpleks: merupakan prosedur aljabar yang bersifat iteratif yang bergerak dengan mengikuti algoritma tertentu}

_{Tahapan prosedur:}

_{1.Inisialisasi: mulai dari suatu titik ekstrem (0,0)}

_{Identifikasi ruang solusi dengan cara merubah sebanyak:}

_{(n – m = kolom – baris) variable, sehingga memiliki nilai nol.}

_{Variabel bernilai nol è variable non basis,}

_{Variabel bukan bernilai nol è variable basis.}

 _{2.Iteratif: bergerak menuju titik ekstrem terdekat yang lebih baik, dan ulangi untuk titik ekstrim lain.}

_{3.Berhenti: jika telah sampai pada titik ekstrim terbaik (titik optimum).}