METODE SIMPLEX

Mata Kuliah: Matematika Sistem Informasi 2

Pertemuan Ke - 3

METODE dan TABEL SIMPLEX

Bentuk metode simplex ini yang gw tau adalah mengubah bentuk baku model LP (Linier Programming) kedalam bentuk table cuy, supaya memudahkan kita dalam proses perhitungan simplex. Nih yang gw tau langkah-langkah yang harus dilakukan untuk membuat simplex :

1.       Harus berdasarkan bentuk baku , maksudnya disini tentukan solusi/masalah dari suatu soal nya, dengan menetapkan m-n variable non basis sama dengan nol. “klo kgk ngerti ikutin dolo aja oke!”

2.        

3.       Pilih sebuah entering variable diantara yang sedang menjadi variabel non basis,

yang jika dinaikkan diatas nol, dapat memperbaiki nilai fungsi tujuan. Jika tidak

ada, berhenti, berarti solusi sudah optimal. Jika tidak, melangkah ke langkah 3.

4.       Pilih sebuah leaving variable diantara yang sedang menjadi variabel basis yang

harus menjadi non basis (nilainya menjadi nol) ketika entering variable menjadi

variabel basis.

5.       Tentukan solusi yang baru dengan membuat entering variable dan leaving

variable menjadi non basis. Kembali ke langkah 2.

Contoh :

Maksimumkan Z = 3X1 + 2X2

dengan syarat : X1 + X2 ≤ 15

2X1 + X2 ≤ 28

X1 + 2X2 ≤ 20

X1 , X2 ≥ 0

Bentuk baku model LP diatas adalah :

Z - 3X1 - 2X2 - 0S1 - 0S2 - 0S3 = 0       Persamaan tujuan

X1 + X2 + S1 = 15

2X1 + X2 + S2 = 28                              Persamaan kendala

X1 + 2X2 + S3 = 20

Lihat kembali langkah nomor 1, solusi awal ditentukan dari persamaan kendala

dengan menetapkan 2 (dua) (= 5 – 3) variabel sama dengan nol, yang akan

memberikan solusi yang unik dan layak. Dengan menetapkan X1 = 0 dan X2 = 0,

diperoleh S1 = 15, S2 = 28, S3 = 20. Pada saat ini nilai Z = 0, kita dapat merangkum

informasi diatas ke dalam bentuk tabel simplex awal seperti berikut :

basis               Z          X1           X2           S1           S2           S3       NK

Z                      1          -3         -2         0          0          0         0 

S1                           0           1          1         1          0          0         15  

S2                           0           2          1         0          1          0         28  

S3                           0           1          2         0          0          1         20 

 

 

NK (nilai kanan) adalah solusi dari permasalahan

Informasi pada tabel dibaca seperti berikut :

· Kolom basis menunjukkan variabel yang sedang menjadi basis yaitu S1, S2, S3,

yang nilainya diberikan pada kolom solusi (NK).

· Secara tidak langsung mengatakan bahwa variabel non basis X1 dan X2 (yang tidak

ditunjukkan pada kolom basis) sama dengan nol.

· Nilai fungsi tujuan adalah Z - ((3 x 0) + (2 x 0) + (0 x 15) + (0 x 28) + (0 x 20)) = 0,

seperti terlihat pada kolom NK.

Kapan solusi telah optimum ?

á Dengan memeriksa persamaan Z, terlihat bahwa variabel non basis yaitu X1 dan X2, keduanya memiliki koefisien negatif, yang berarti mempunyai koefisien negatif

pada fungsi tujuan yang asli.

á Karena tujuan kita adalah masalah maksimasi, maka nilai Z dapat diperbaiki dengan

meningkatkan X1 dan X2 menjadi lebih besar dari nol. Yang diutamakan untuk dipilih

adalah variabel yang memiliki nilai negatif terbesar.

á Ringkasnya, optimality condition metode simplex menyatakan bahwa dalam kasus

maksimasi, jika variabel non basis memiliki koefisien non negatif pada persamaan

Z, maka solusi optimum telah tercapai. Jika tidak, variabel non basis dengan

koefisien negatif terbesar dipilih sebagai entering variabel.