Metode Simpleks ( Materi 3 )

Program Linier   : Metode Simpleks  ( Materi 3 )

FUNGSI & TUJUAN METODE SIMPLEKS

Metode simpleks merupakan salah satu teknik penyelesaian dalam program linier yang digunakan sebagai teknik pengambilan keputusan dalam permasalahan yang berhubungan dengan pengalokasian sumberdaya secara optimal. Metode simpleks digunakan untuk mencari nilai Optimal dari program linier yang melibatkan banyak constraint (pembatas) dan banyak variabel (lebih dari dua variabel). Penemuan metode ini merupakan lompatan besar dalam riset operasi dan digunakan sebagai prosedur penyelesaian dari setiap program komputer .

Ada dua metode penyelesaian masalah yang digunakan dalam program linier, yaitu metode

grafis (untuk 2 variabel) dan metode simpleks (untuk 2 variabel atau lebih). Beberapa ketentuan

yang perlu diperhatikan dalam penyelesaian metode simpleks:

1. Nilai kanan fungsi tujuan harus nol (0)

2.Nilai kanan fungsi kendala harus positif. Apabila negatif, nilai tersebut harus dikali dengan -

3.Fungsi kendala dengan tanda “≤” harus diubah ke bentuk “=” dengan menambahkan variabel

slack/surplus. Variabel slack/surplus disebut juga variabel dasar. Penambahan slack variabel

menyatakan kapasitas yang tidak digunakan atau tersisa pada sumber daya tersebut. Hal ini

karena ada kemungkinan kapasitas yang tersedia tidak semua digunakan dalam proses

produksi.

4.Fungsi kendala dengan tanda “≥” diubah ke bentuk “≤” dengan cara mengkalikan dengan -1,

lalu diubah ke bentuk persamaan (=) dengan ditambah variabel slack. Kemudian karena nilai

kanan-nya negatif, dikalikan lagi dengan -1 dan ditambah artificial variabel (M).

Artificial variable ini secara fisik tidak mempunyai arti, dan hanya digunakan untuk kepentingan

perhitungan saja.

5.Fungsi kendala dengan tanda “=” harus ditambah artificial variabel (M) .

FORMULASI MODEL PROGRAM LINIER

Masalah keputusan yang sering dihadapi analis adalah mengalokasikan secara optimum

keterbatasan/kelangkaan sumber daya. Sumber daya dapat berupa uang, tenaga kerja, bahan mentah,

kapasitas mesin, waktu, ruang atau teknologi. Tugas analis adalah mencapai hasil terbaik yang

mungkin dengan keterbatasan sumber daya itu. Hasil yang dinginkan mungkin ditunjukkan sebagai maksimasi dari beberapa ukuran profit, penjualan dan kesejahteraan, atau minimisasi pada biaya, waktu dan jarak. Masalah optimasi ini dapat diselesaikan dengan program linier.

Langkah-langkah dalam perumusan model program linier adalah sebagai berikut:

i) Definisikan Variabel Keputusan (Decision Variable)

- Variabel yang nilainya akan dicari

ii) Rumuskan Fungsi Tujuan:

-Maksimisasi atau Minimisasi

-Tentukan koefisien dari variabel keputusan

iii) Rumuskan Fungsi Kendala Sumberdaya:

-Tentukan kebutuhan sumberdaya untuk masing-masing peubah keputusan.

-Tentukan jumlah ketersediaan sumberdaya sbg pembatas.

iv) Tetapkan kendala non-negatif

-Setiap keputusan (kuantitatif) yang diambil tidak boleh mempunyai nilai negatif.

Mengkonversi Bentuk Pertidaksamaan Fungsi Kendala Menjadi Bentuk Standar

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

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

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

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

v  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

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

v  Langkah 2:
Memindahkan bentuk standar ke dalam tabel.

v  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 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 Kasus Pertama:
• Maksimumkan Z = 3X₁ + 5X₂
• Batasan (constrain) 

  (1) 2X₁           ≤  8
  (2)          3X₂  ≤ 15
  (3) 6X₁ + 5X₂  ≤ 30

Penyelesaian dari kasus di atas adalah:

Langkah 1:
Mengubah fungsi tujuan dan batasan-batasan
• Fungsi tujuan
  Z = 3X₁ + 5X₂ diubah menjadi Z - 3X₁ - 5X₂ = 0.
• Fungsi batasan (diubah menjadi kesamaan & di + slack variabel)
  (1) 2X₁           ≤ 8 diubah menjadi     2X₁          +  X₃               =  8
  (2)          3X₂  ≤ 15 diubah menjadi   3X₂                  + X₄         = 15
  (3) 6X₁ + 5X₂  ≤ 30 diubah menjadi       6X₁ + 5X₂               + X₅  = 30
Slack variabel adalah variabel tambahan yang mewakili tingkat pengangguran atau kapasitas yang merupakan batasan
• Fungsi tujuan : Maksimumkan Z - 3X₁ - 5X₂ = 0
• Fungsi batasan
  (1) 2X₁          + X₃                 =  8
  (2)         3X₂         + X₄          = 15
  (3) 6X₁ + 5X₂              + X5    = 30

Langkah 2:

Memasukkan persamaan fungsi tujuan dan fungsi batasan ke dalam tabel.

• NK adalah nilai kanan persamaan, yaitu nilai di belakang tanda sama dengan ( = ). Untuk batasan 1 sebesar 8, batasan 2 sebesar 15, dan batasan 3 sebesar 30.
• Variabel dasar  adalah variabel yang nilainya sama dengan sisi kanan dari persamaan. Pada persamaan 2X₁ + X₃ = 8, kalau belum ada kegiatan apa-apa, berarti nilai X₁ = 0, dan semua kapasitas masih menganggur, maka pengangguran ada 8 satuan, atau nilai X₃ = 8. Pada tabel tersebut nilai variabel dasar (X₃, X₄, X₅) pada fungsi tujuan pada tabel permulaan ini harus 0, dan nilainya pada batasan-batasan bertanda positif

Tabel Simplex Pertama

Langkah 3:

Memilih kolom kunci.

• Kolom kunci adalah kolom yang merupakan dasar untuk mengubah tabel simplek. Pilihlah kolom yang mempunyai nilai pada garis fungsi tujuan yang bernilai negatif dengan angka terbesar. Dalam hal ini kolom X₂ dengan nilai pada baris persamaan tujuan –5. Berilah tanda segi empat pada kolom X₂, seperti tabel berikut:

Tabel Menentukan Kolom Kunci

Langkah 4:

Memilih baris kunci.

• Baris kunci adalah baris yang merupakan dasar untuk mengubah tabel simplek, dengan cara mencari indeks tiap-tiap baris dengan membagi nilai-nilai pada kolom NK dengan nilai yang sebaris pada kolom kunci.
• Indeks = (Nilai Kolom NK) / (Nilai kolom kunci)

Untuk baris batasan 1 besarnya indeks = 8/0 = ~,  baris batasan 2 = 15/3 = 5, dan baris batasan 3 = 30/5 = 6. Pilih baris yang mempunyai indeks positif dengan angka terkecil. Dalam hal ini batasan ke-2 yang terpilih sebagai baris kunci. Beri tanda segi empat pada baris kunci. Nilai yang masuk dalam kolom kunci dan juga masuk dalam baris kunci disebut angka kunci.

Tabel Menentukan Baris Kunci

Jika suatu tabel sudah tidak memiliki nilai negatif pada baris fungsi tujuan, berarti tabel itu tidak bisa dioptimalkan lagi (sudah optimal).

Langkah 5:

Mengubah nilai-nilai baris kunci.

Nilai baris kunci diubah dengan cara membaginya dengan angka kunci, seperti tabel 3. bagian bawah (0/3 = 0; 3/3 = 1; 0/3 = 0; 1/3 = 1/3; 0/3 = 0; 15/3 = 5). Gantilah variabel dasar pada baris itu dengan variabel yang terdapat di bagian atas kolom kunci (X₂).

Tabel Mengubah nilai-nilai baris kunci

Langkah 6: Mengubah nilai-nilai pada baris selain baris kunci

Tabel simplex kedua

Langkah 7:

Ulangilah langkah-langkah perbaikan mulai langkah 3 sampai langkah ke-6 untuk memperbaiki tabel-tabel yang telah diubah/diperbaiki nilainya. Perubahan baru berhenti setelah pada baris pertama (fungsi tujuan) tidak ada yang bernilai negatif .

Tabel Menentukan Kolom Kunci dan baris kunci.

Tabel simplex ketiga

Baris pertama (Z) tidak ada lagi yang bernilai negatif. Sehingga tabel tidak dapat dioptimalkan lagi dan tabel tersebut merupakan hasil optimal.

Maka, diperoleh hasil akhirnya adalah.

X₁ = 5/6, X₂ = 6, dan Z_maximum = 27½.