Program Linier : Metode Simpleks

Metode simpleks digunakan untuk memecahkan permasalahan Program Linier dengan dua atau lebih

variabel keputusan. 

Prosedur Metode Simpleks yaitu :

vFormulasi Fungsi Tujuan dan Fungsi Kendala Dari Permasalahan PL

vMengkonversi Bentuk Pertidaksamaan Dalam Fungsi Kendala Menjadi Bentuk Standar

vMembuat Table Simpleks Awal

vAlgoritma metode simpleks

Bentuk Standar dari prosedur metode simpleks :

- Ruas kanan (RK) fungsi tujuan harus nol (0)

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

- Fungsi kendala dengan tanda “£ ” harus diubah ke bentuk “=” dengan menambahkan

  variabel slack/surplus. Variabel slack/surplus disebut variabel basis.

- 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

vAda tiga bentuk fungsi kendala:  £, ≥, dan =.

vKonversi fungsi kendala bertanda £: menambahkan slack variable pada fungsi kendala tersebut.

vUntuk kendala berbentuk ‘³’ dan ‘=‘ akan dibahas tersendiri dalam teknik variabel artifisial.

vSlack variable: sumber daya yang mengganggur pada suatu fungsi kendala.

vPenambahan slack variable dimaksudkan untuk memperoleh solusi fisibel awal (initial feasible solution, sama dengan titik origin pada grafik) pada fungsi kendala.

ADAPUNLANGKAH - LANGKAH METODE SIMPLEKS MASALAH MAKSIMASI SEBAGAI BERIKUT :

vLangkah 1:

   Mengubah fungsi tujuan dan kendala menjadi “bentuk standar”

vLangkah 2:

     Memindahkan bentuk standar ke dalam tabel.

vLangkah 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 di mana

     entering var. menggantikan leaving var.), dengan Pers. Poros

      yang baru = Pers. Poros yang lama / Elemen poros

Contoh :

v Maksimumkan Z = 3X1 + 5X2

   v Berdasarkan kendala (constrain) 

                (1)  2X1  £ 8

                (2)     3X2  £ 15

                (3)   6X1 + 5X2  £ 30

                (4)  X1 ³ 0,  X2 ³ 0

PEMECAHAN MASALAH :

vLangkah-langkah metode simpleks

Langkah 1:

   Mengubah fungsi tujuan dan kendala menjadi “bentuk standar” 

vFungsi tujuan

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

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

vFungsi tujuan :

  Maksimumkan Z - 3X1 - 5X2 = 0

vFungsi 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

Beberapa Istilah dlm Metode Simpleks

vRK adalah nilai ruas kanan persamaan, Untuk kendala 1 sebesar 8, kendala 2 sebesar 15, dan kendala 3 sebesar 30.

Variabel basis  adalah variabel yang nilainya sama dengan nilai ruas kanan persamaan. Pada persamaan 2X1 + X3 = 8, kalau belum ada kegiatan apa-apa, berarti nilai X1 = 0, dan semua kapasitas masih menganggur, maka pengangguran ada 8 satuan, atau nilai X3 = 8. Pada tabel tersebut nilai variabel basis (X3, X4, X5) pada fungsi tujuan tabel awal harus 0, selanjutnya variabel yang bukan var. basis disebut var. non basis atau var. yang dinolkan (dalam masalah ini X1 dan X2). 

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

vContoh 1.

  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

vVariabel keputusan:

  X1 = lemari A yang dijual (diproduksi)

  X2 = lemari B yang dijual (diproduksi)

  X3 = lemari C yang dijual (diproduksi)

v

vFungsi Tujuan:

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

  dengan Z adalah keuntungan.

v

vFungsi 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

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

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

PL : LANGKAH2 METODE SIMPLEKS
MASALAH MINIMASI

vPada umumnya masalah PL dengan fungsi tujuan minimasi 

mempunyai fungsi kendala bertanda ³ atau kombinasi antara ³, =, 

dan £, dan ini diselesaikan dengan teknik variabel artifisial.

vPL dengan fungsi tujuan minimasi, dan koefisiennya bertanda +,

 diselesaikan dengan metode dual Simpleks, karena pada iterasi 0

 telah tercapai kondisi optimal tapi belum fisibel.

vUntuk 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

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