Program Linear : Metode Simpleks [ Materi 3 ]

Program Linear Metode Simpleks
Metode simpleks digunakan untuk memecahkan permasalahan Program Linier dengan dua atau lebih variabel keputusan

Prosedur Metode Simpleks 

• 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 Linear 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.

LANGKAH2 METODE SIMPLEKS MASALAH MAKSIMASI

• Langkah 1:
  Mengubah fungsi tujuan dan kendala menjadi “bentuk standar”
• Langkah 2:
  Memindahkan bentuk standar ke dalam tabel.
• Langkah 3:
  Memilih entering & leaving Variabel

1. Pilih entering variabel di antara var. non basis yg mempuyai koefisien negatif terbesar pada persamaan / baris untuk maksimasi atau pilih koef. positif terbesar baris Z untuk minimasi.
2. Bagilah RK (kecuali pers. Z) dengan unsur yang bersesuaian pada kolom entering, hasil bagi dinyatakan sebagai Ratio 
3. Pilih leaving var. diantara var. basis yang mempunyai Ratio terkecil, persamaan di mana leaving var. berada disebut pers. poros. Elemen poros merupakan perpotongan antara kolom entering dengan pers. poros.
4. Susun kembali tabel Simpleks berikutnya dengan mengganti variabel leaving dengan var . Entering.
5. Tentukan persamaan poros yang baru (baris dimana entering var. menggantikan leaving var), dengan : Pers. Poros yang baru = Pers. poros yang lama / Elemen poros
6. Tentukan persamaan yang lainnya (termasuk Z) sbb : Pers. yang baru = Pers. yang lama - (koef. Kolom entering) x pers. poros baru
7. Kemudian ulangi kembali langkah 3.1 s/d 3.6 sampai kondisi optimal tercapai (semua koef. pada pers. Z sudah berhargaa positif atau nol untuk maksimal dan berharga negativ atau nol untuk minimasi).

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

Contoh Soal
Perusahaan Mebel Ais memproduksi lemari jenis A, B, dan C. Produk tersebut diproses melalui tiga departemen: pertukangan, pengecatan, dan penyelesaian. Setiap unit lemari A membutuhkan 3 jam tenaga kerja di departemen pertukangan, 2 jam tenaga kerja di departemen pengecatan, dan 1 jam tenaga kerja di departemen penyelesaian. Setiap unit lemari B membutuhkan 4 jam tenaga kerja di departemen pertukangan, 5 jam tenaga kerja di departemen pengecatan, dan 2 jam tenaga kerja di departemen penyelesaian. Dan, setiap unit lemari C membutuhkan 3½ jam tenaga kerja di departemen pertukangan, 1 jam tenaga kerja di departemen pengecatan, dan 1 jam tenaga kerja di departemen penyelesaian. Kapasitas yang tersedia pada departemen pertukangan, departemen pengecatan, dan departemen penyelesaian adalah 400 jam, 360 jam, dan 250 jam, masing-masing. Harga jual masing-masing produk adalah Rp 10 (lemari A), Rp 15 (lemari B), dan Rp 12 (lemari C). Bagaimana usul Anda dalam memproduksi lemari, agar diperoleh keuntungan yang maksimal ?

Formulasikan Fungsi Tujuan dan Fungsi Kendala Dari Permasalahan PL
Variabel keputusan:

  X1 = lemari A yang dijual (diproduksi)

  X2 = lemari B yang dijual (diproduksi)

  X3 = lemari C yang dijual (diproduksi)

Fungsi Tujuan:

  Maks : Z = 10 X1 + 15 X2 + 12 X3

  dengan Z adalah keuntungan.

Fungsi Kendala :

  3 X1 + 4 X2 + 3 1/2 X3   ≤ 400

  2 X1 + 5 X2 + 1 X3         ≤ 360

  1 X1 + 2 X2 + 1 X3         ≤ 250

        X1, X2, X3 ≥ 0

 Mengkonversi Bentuk Pertidaksamaan Fungsi Kendala Menjadi Bentuk Standar
  Z - 10 X1 - 15 X2 - 12 X3    + 0S1 + 0S2 + 0S3   = 0

       3 X1 + 4 X2 + 3 1/2 X3 +  S1                     = 400

       2 X1 + 5 X2 + 1 X3               +    S2           = 360

       1 X1 + 2 X2 + 1 X3                           + S3  = 250

  X1, X2, X3, S1, S2, S3 ≥ 0

Hasil yang dicapai menggunakan metode Simpleks

•           Tampak pada tabel Simpleks awal (iterasi 0), x2 terpilih sebagai entering v. (koef. = -15) dan x5 terpilih sebagai leaving v. (ratio terkecil = 360/5=72). Selanjutnya pada iterasi 1, x3 terpilih sebagai entering v. (koef. = -9) dan x4 terpilih sebagai leaving v. (ratio terkecil = 112/2.7).
•          Selanjutnya tampak pada tabel Simpleks iterasi 2, koef. Pers./baris Z sudah positip atau nol, sehingga masalah PL ini telah optimal dengan Z atau keuntungan yang maksimum sebesar 1453 rupiah (dibulatkan), dengan hanya memproduksi lemari jenis B sebanyak 64 unit (dibulatkan) dan lemari jenis C sebanyak 41 unit (dibulatkan)

LANGKAH2 METODE SIMPLEKS MASALAH MINIMASI

•          Pada umumnya masalah PL dengan fungsi tujuan minimasi mempunyai fungsi kendala bertanda ³ atau kombinasi antara ³, =, dan £, dan ini diselesaikan dengan teknik variabel artifisial.
•          PL dengan fungsi tujuan minimasi, dan koefisiennya bertanda +, diselesaikan dengan metode dual Simpleks, karena pada iterasi 0 telah tercapai kondisi optimal tapi belum fisibel.
•          Untuk menyelesaikan masalah PL dengan fungsi tujuan meminimumkan Z (minimasi), ada 2 cara:

1.         Merubah fungsi tujuan menjadi masalah maksimasi,   kemudian menyelesaikannya  dengan metode Simpleks   masalah maksimasi.
2.         Memodifikasi langkah 3 metode Simpleks : Jika semua variabel non basis pada baris/pers. Z mempunyai   koef. berharga £ 0, maka solusi basis fisibel telah optimal.   Akan tetapi jika baris Z masih ada variabel dengan koef.   positip, pilih salah satu   variabel berharga positip terbesar   sebagai entering variabel.

 Dengan catatan koef. fungsi tujuan   Z masih ada yang bertanda negatip (-), jika tidak gunakan metode dual Simpleks.

Contoh Masalah PL Minimasi

vMinimumkan Z = 2X1 – 3X2

  berdasarkan kendala :

  X1 + X2 < 4

  X1 – X2  < 6

  X1, X2 > 0

vPenyelesaian :

  Jika dilakukan cara 1, fungsi tujuan menjadi

  maksimumkan – Z = - 2X1 + 3X2, dan semua kendala tidak berubah. Selanjutnya diselesaikan menggunakan metode Simpleks masalah maksimasi.

  Jika diselesaikan dengan cara 2, tabel Simpleks masalah itu adalah sbb. :