Metode Simpleks

Berikut penjelasannya:

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

Bentuk Standar dari program linear

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 negatif.

Mengkonversi Bentuk Pertidaksamaan Fungsi Kendala Menjadi Bentuk Standar dengan cara :

ü  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

v  Maksimumkan Z = 3X₁ + 5X₂

v  Berdasarkan kendala (constrain)             

                                (1)          2X₁                                    £ 8

                                (2)                        3X₂                     £ 15

                                (3)          6X₁ + 5X₂                        £ 30

                                (4)          X₁ ³ 0,  X₂ ³ 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

Tabel Awal Simpleks Awal (Iterasi 0) dan Iterasi 1

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).

 Langkah- Langkah Metode Simpleks  Masalah Minimasi

1. Pada umumnya masalah PL dengan fungsi tujuan minimasi mempunyai fungsi kendala bertanda ³ atau kombinasi antara ³, =, dan £, dan ini diselesaikan dengan teknik variabel artifisialPada umumnya masalah PL dengan fungsi tujuan minimasi mempunyai fungsi kendala bertanda ³ atau kombinasi antara ³, =, dan £, dan ini diselesaikan dengan teknik variabel artifisial
2. PL dengan fungsi tujuan minimasi, dan koefisiennya bertanda +, diselesaikan dengan metode dual Simpleks, karena pada iterasi 0 telah tercapai kondisi optimal tapi belum fisibel.
3. Untuk menyelesaikan masalah PL dengan fungsi tujuan meminimumkan Z (minimasi), ada 2 cara :                                                                                                                                                           v   Merubah fungsi tujuan menjadi masalah maksimasi,  kemudian menyelesaikannya                  dengan metode Simpleks  masalah maksimasi.                                                                  v    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,

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

Contoh Masalah PL Minimasi

v  Minimumkan Z = 2X1 – 3X2

                                berdasarkan kendala :

                                                X1 + X2 < 4

                                                X1 – X2  < 6

                                                X1, X2 > 0

v  Penyelesaian :

                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. :