METODE SIMPLEKS DAN CONTOH SOAL BESERTA PENYELESAIANYA

MANAJEMEN SAINS
METODE SIMPLEKS (CONTOH SOAL)

      Terimakasih sebelumnya karena sudah mampir ke blog ini hehehe....Nah, pada kesempatan ini kali ini saya akan shere ilmu pengetahuan operasi riset dengan judul " Metode Simpleks Dalam Manajemen Sains (Contoh Soal Dan Penyelesaian) "   . Selamat membaca

Metode Simpleks

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

Prosedur Metode Simpleks

1. Formulasi Fungsi Tujuan dan Fungsi Kendala Dari Permasalahan PL

2. Mengkonversi Bentuk Pertidaksamaan Dalam Fungsi Kendala Menjadi Bentuk Standar

3. Membuat Table Simpleks Awal

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

1. Ada tiga bentuk fungsi kendala:  £, ≥, dan =.

2. Konversi fungsi kendala bertanda £: menambahkan slack variable pada fungsi kendala tersebut.

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

4. Slack variable: sumber daya yang mengganggur pada suatu fungsi kendala.

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

LANGKAH-LANGKAH 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 ebagai 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

     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 berharga positip atau nol

          untuk maksimasi dan berharga negatip atau nol untuk minimasi).

Contoh Soal Metode Simpleks :  

Persyaratan Tak-Negatif

Semua variabel yang belum dikendala agar tak-negatif diganti dengan selisih dari 2 variabel baru yang telah terkendala.

Contoh :              

Jika kendala          x1 + 2x2 £  4      (1)

                                                2x1 + 3x2 £ 1       (2)

                                                                x1 ³ 0

                                                                x2 £ 0

Penyelesaian :

misal ® x2 = x3 + x4 disubstitusikan ke (1) dan (2) menjadi :

                                x1 + 2(x3 – x4) £ 4 ®    x1 + 2x3 – 2x4 £ 4

2x1 + 3(x3 – x4) £ 1 ®  2x1 + 3x3 – 3x4 £ 1

dan : semua variabel tak-negatif

Variabel Kurang & Plus

 

Sebuah kendala linier yang berbentuk Saj xj £ bi dapat diubah menjadi suatu persamaan dengan menambahkan sebuah variabel tak-negatif baru pada persamaan lainnya, variabel baru ini disebut variabel kurang (slack variabel).

Contoh :

Dengan kendala :             2x1 + 3x2 £ 5

                                                                 x1 + x2   £ 1

                                                                 x1, x2     ³ 0

menjadi :                             2x1 + 3x2 + S1                      = 5

                                                                 x1 +   x2  + S2  = 1

dan semua variabel tak negatif

sebuah kendala linier yang berbentuk Saij xj ³ bi dapat diubah menjadi persamaan dengan mengurangkan ruas kirinya dengan sebuah variabel baru tak-negatif, variabel baru ini disebut variabel surplus (surplus variabel).

Contoh :

Dengan kendala               4x1 + 3x2 ³ 5

                                                                  x1 + 4x2 ³ 2

                                                                  x1, x2     ³ 0

menjadi :             4x1 + 3x2 - S1                       = 5

                                                  x1 + 4x2 - S2   = 1

                                                dan semua variabel tak-negatif

Pemecahan Awal yang Layak

 

Setelah semua kendala linier (dengan ruas kanan yang tak-negatif) ditransformasikan menjadi persamaan dengan memperkenalkan variabel-variabel kurang dan surplus bila perlu, tambahkan lagi sebuah variabel baru yang disebut variabel buatan (artificial variable / A) dengan demikian tiap persamaan kendala akan mengandung variabel kurang dan variabel buatan.

Rangkuman

• Jika pada kendala linier terdapat tanda ( £ ) maka dalam fungsi kendala perlu ditambah variabel kurang ( + S ).
• Jika pada kendala linier terdapat tanda ( ³ ) maka dalam fungsi kendala perlu ditambah variabel surplus ( - S ) dan variabel buatan ( A ).
• Jika pada kendala linier terdapat tanda ( = ) maka dalam fungsi kendala perlu ditambah  variabel buatan ( A ).

Contoh :

Dengan kendala                 x1 + 2x2 £ 3

                                                                4x1 + 5x2 ³ 6

                                                                7x1 + 8x2 = 15

                                                                 x1, x2     ³ 0

menjadi :               x1 + 2x2 + S1                              = 3

4x1 + 5x2         - S2 + A1                                          = 1

                                                4x1 + 3x2   + A2       = 15

                                                dan semua variabel tak-negatif

Biaya Hukuman

 

Penambahan variabel kuarang dan variabel surplus tidak mengubah sifat kendala maupuntujuan, oleh karena itu, variabel-variabel tersebut diikutsertakan dalam fungasi tujuan dengan koefisien NOL. Sedangkan variabel buatan mengubah sifat kendala, oleh karena itu, variabel buatan diikutsertakan dalam fungsi obyektif tetapi dengan koefisien-koefisien positif yang besar sekali (M) untuk program meminimumkan, atau koefisien-koefisien negatif yang besar sekali (-M) untuk program memaksimumkan.

Contoh :

Min :                                      Z = x1 + 3x2

Dengan kendala               2x1 + 4x2 £ 5

                                                                3x1 + 5x2 £ 2

                                                                x1 + 2x2 ³ 4

                                                                x1, x2      ³ 0

menjadi :              

Min : Z = x1 + 3x2 + 0S1 + 0S2 + 0S3 + MA

Dengan kendala               2x1 + 4x2 + S1                                  = 5

                                                                3x1 + 5x2 + S2           = 2

                                                                 x1 + 2x2 - S3 + A2    = 4

                                                                dan semua variabel tak-negatif

Bentuk Simpleks

Langkah-langkah penyelesaian dengan metode simpleks adalah sebagai berikut :

• Mengubah fungsi tujuan dan batasan

Setelah semua fungsi tujuan dan batasan diubah ke bentuk satndard, maka fungsi tujuan diubah menjadi fungsi implisit, yaitu semua Cj Xij digeser ke kiri.

Contoh :  Z = 3x1 + 5x2 ® Z - 3x1 + 5x2 = 0

• Menyusun persamaan-persamaan ke dalam tabel simpleks

Var dasar	Z	X1	X2	X3	…	xn	Xn+1	Xn+2	…	Xn+m	Nilai kanan (NK)
Z	1	- C1	- C2	- C3	…	- Cn	0	0	…	0	0
Xn+1	0	a11	a12	a13	…	an	1	0	…	0	b1
Xn+2	0	a21	a22	a23	…	a2n	0	1	…	0	b2
…	…	…	…	…	…	…	…	…	…	…	…
Xn+m	0	an1	an2	an3	…	anm	0	0	…	1	bn

Var dasar  = var. kurang dan var buatan

• Memilih kolom kunci

Caranya dengan memilih kolom yang mempunyai nilai pada garis fungsi tujuan yang bernilai negatif dengan angka terbesar.

• Memilih baris kunci

Pilih baris yang mempunyai limit ratio dengan angka terkecil.

      Nilai kolom NK

Limit ratio = 

     Nilai kolom kunci

• Mengubah nilai-nilai baris kunci

Nilai baris kunci diubah dengan cara membaginya dengan angka kunci. Gantilah variabel dasar pada baris kunci dengan variabel yang terdapat di bagian atas kolom kunci.

• Mengubah nilai-nilai selain pada baris kunci

Untuk mengubahnya menggunakan rumus :

Baris baru = baris lama – ( koefisien per kolom kunci * nilai bari baris kunci )

• Melanjutkan perbaikan-perbaikan atau perubahan-perubahan

Ulangi langkah 3 s/d 6, sampai semua nilai pada fungsi tujuan berharga positif.