Program Linear Metode Kompleks

Program Linier : Metode Simpleks
  

•  Metode simpleks digunakan untukmemecahkan permasalahan Program Linier dengan dua atau lebih variabel keputusan

• Formulasi Fungsi Tujuan dan Fungsi Kendala Dari Permasalahan PL
• Mengkonversi Bentuk Pertidaksamaan Dalam Fungsi Kendala Menjadi Bentuk Standar
• Membuat Table Simpleks Awal
• Algoritma metode simpleks

 

 Program Linier : Bentuk Standar

1.Ruas kanan (RK) fungsi tujuan harus nol (0)

2.Ruas kanan (RK) fungsi kendala harus positif, jika negatif kalikan dengan –1.

3.Fungsi kendala dengan tanda “\<” harus diubah ke bentuk “=” dengan menambahkan variabel slack/surplus. Variabel slack/surplus disebut variabel basis.

4.Fungsi kendala dengan tanda “>/” diubah ke bentuk “\< ” dengan cara mengalikan dengan –1, lalu

diubah ke bentuk persamaan dengan menambahkan variabel slack, kemudian RKnya dikalikan dengan –1,

 karena bertanda negatip.

Mengkonversi Bentuk Pertidaksamaan Fungsi Kendala Menjadi Bentuk Standar 

•                 Ada tiga bentuk fungsi kendala: \<, ≥, dan =.
•                 Konversi fungsi kendala bertanda \<: menambahkan slack variable pada fungsi kendala tersebut.
•                 Untuk kendala berbentuk ‘\<’ dan ‘=‘ akan dibahas tersendiri dalam teknik variabel artifisial.
•                 Slack variable: sumber daya yang mengganggur pada suatu fungsi kendala.
•                  Penambahan slack variable dimaksudkan untuk memperoleh solusi fisibel awal (initial feasible solution, sama dengan titik origin pada grafik) pada fungsi kendala.

 
 

Contoh Metode Simpleks Masalah Maksimasi

Maksimumkan Z = 3X1 + 5X2

Berdasarkan kendala (constrain) 

  (1)  2X1  \< 8

  (2)     3X2  \<15

  (3)   6X1 + 5X2  \<30

  (4)  X1 >/ 0,  X2 >/ 0

Langkah-langkah metode simpleks

Langkah 1:
Mengubah fungsi tujuan dan kendala menjadi “bentuk standar” 

Fungsi tujuan

  Z = 3X1 + 5X2 diubah menjadi Z - 3X1 - 5X2 = 0.

Fungsi kendala diubah menjadi persamaan dg menambahkan var. slack, sebagai berikut :

  (1) 2X1  \< 8   menjadi   2X1  +     X3            =  8

  (2) 3X2 \< 15 menjadi             3X2     + X4            = 15

  (3) 6X1 + 5X2  \< 30 menjadi   6X1 + 5X2     + X5= 30

Variabel slack adalah variabel tambahan yang mewakili tingkat pengangguran atau kapasitas yang merupakan batasan

Bentuk Standar :

Fungsi tujuan :

  Maksimumkan Z - 3X1 - 5X2 = 0

Fungsi kendala

  (1)   2X1           + X3      =  8

  (2)               3X2           +  X4      = 15

  (3)   6X1  +   5X2                 + X5    = 30

  (4)  X1 ,X2  ,X3  , X4 , X5  >/0

Langkah 2: Memindahkan bentuk standar ke dalam tabel 

Z = 3X1 + 5X2

               diubah menjadi Z - 3X1 - 5X2 + 0X3 + 0X4 + 0X5  = 0.

(1) 2X1  \< 8   menjadi   2X1           + X3   =  8

(2) 3X2  \< 15 menjadi              3X2          + X4   = 15

(3) 6X1 + 5X2  \< 30 menjadi   6X1 +    5X2      + X5  = 30