Metode Simpleks

Pengertian 

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

Pendahuluan

Metode penyelesaian program linier dengan metode simplekspertamakali dikemukakan oleh George Dantzig pada tahun 1947. Metode ini menjadi terkenal ketika diketemukan alat hitung elektronik dan menjadi popular ketika munculnya computer. Proses perhitungan metode ini dengan melakukan iterasi berulang-ulang sampai tercapai hasil optimal dan proses perhitungan ini menjadi mudah dengan komputer.

Selanjutnya berbagai alat dan metode dikembangkan untuk menyelesaikan masalah program linear bahkan sampai pada masalah riset operasi hingga tahun 1950an seperti pemrogaman dinamik, teori antrian, dan persediaan.

Program Linier merupakan metode matematik dalam mengalokasikan sumber daya yang langka untuk mencapai tujuan tunggal seperti memaksimumkan atau meminimumkan biaya. Program linier banyak diterapkan dalam membantu menyelesaikan masalah ekonomi, industri, militer, social, dan lain-lain.

Karakteristik persoalan dalam program linier adalah sebagai berikut :

1. Ada tujuan yang ingin dicapai

2. Tersedia beberapa alternatif untuk mencapai tujuan

3. Sumberdaya dalam keadaan terbatas

4.Dapat dirumuskan dalam bentuk matematika (persaman/ketidaksamaan)

Contoh pernyataan ketidaksamaan:

Untuk menghasilkan sejumlah meja dan kursi secara optimal, total biaya yang dikeluarkan tidak boleh lebih dari dana yang tersedia. Ada dua metode penyelesaian masalah yang digunakan dalam program linearm program linier, yaitu metodegrafis (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 -1

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 untuk 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 kanannya negatif, dikalikan lagi dengan (-1) dan ditambah artificial variabel (M) Artificial variabel ini secara fisik tidak mempunyai arti, dan hanya digunakan untuk kepentingan perhitungan saja.

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

Metode simplex merupakan prosedur aljabar yang bersifat iteratif, yang bergerak selangkah demi selangkah, dimulai dari satu titik ekstrem pada daerah fisibel (ruang solusi) menuju titik ekstrem optimum.

FORMULASI MODEL PROGRAM LINIER

Masalah keputusan yang sering dihadapi analis adalah mengalokasikan secara optimum keterbatasan/kelangkaan sumber daya dapat berupa uang, tenaga kerja, bahan mentah, kapasitas mesin, waktu, ruang atau teknologi. Tugas analisis adalah mencapai hasil terbaik yang mungkin dengan keterbatasan sumber daya itu. Hasil yang diinginkan mungkin ditunjukan sebagai maksimasi dari beberapa ukuran profit, penjualan dan kesejahteraan, atau minimasi pada biaya, waktu dan jarak. Masalah optimasi ini dapat diselesaikan dengan program linear.

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

1. Definisikan Variabel Keputusan (Decision Variable)

   > Variabel yang nilainya akan dicari
2. Rumuskan Fungsi Tujuan:

   > Maksimisasi atau Minimisasi

   > Tentukan koefisien dari variabel keputusan 

3. Rumuskan Fungsi Kendala Sumberdaya: 

   > Tentukan kebutuhan sumberdaya untuk masing- masing peubah keputusan.

   > Tentukan jumlah ketersediaan sumberdaya sbg pembatas.

4. Tetapkan kendala non-negatif

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

Contoh Persoalan: (Perusahaan Meubel)

Suatu perusahaan menghasilkan dua produk, meja dan kursi yang diproses melalui dua bagian fungsi : perkitan dan pemolesan. Pada bagian perakitan tersedia 60 jam kerja, sedangkan pada bagian pemolesan hanya 48 jam kerja. Untuk menghasilkan 1 meja diperlukan 4 jam perkitan dan 2 jam kerja pemolesan, sedangkan untuk menghasilkan 1 kursi diperlukan 2 jam kerja perakitan dan 4 jam kerja pemolesan. Laba untuk setiap meja dan kursi yang dihasilkan masing-masing Rp. 80.000 dan Rp. 60.000,-

Berapa jumlah meja dan kursi yang optimal dihasilkan ?

Penyelesaian:

Definisi variabel keputusan:

Keputusan yang akan diambil adalah berapakah jumlah meja dan kursi yg akan dihasilkan. Jika meja disimbolkan dengan M dan kursi dengan K, maka definisi variabel keputusan :

M = jumlah meja yang akan dihasilkan (dalam satuan unit)

K = jumlah kursi yang akan dihasilkan (dalam satuan unit) 

Perumusan persoalan dalam bentuk tabel:

Perumusan fungsi tujuan:

Laba untuk setiap meja dan kursi yg dihasilkan masing- masing Rp. 80.000 dan Rp. 60.000. tujuan perusahaan adalah untuk memaksimumkan laba dari sejumlah meja dan kursi yang dihasilkan . dengan demikian, fungsi tujuan dapat ditulis

Fungsi Maks.:

Laba = 8 M + 6 K (dalam satuan Rp.10. 000)

Perumusan fungsi kendala:

Dengan kendala:

4M + 2K ≤ 60

2M + 4K ≤48

Kendala non-negatif:

Meja dan kursi yang dihasilkan tidak memiliki nilai negatif. 

M ≥ 0

K ≥ 0

Ketentuan Penggunaan Tabel Simpleks

1. Fungsi – fungsi batasan menggunakan notasi ≤

2.Fungsi Batasan harus diubah dari ≤ ke bentuk “=“ dengan menambahkan slack variable (variabel surplus) yang dimulai dari Xn+1, Xn+2…. Xn+m

3. Proses pengulangan dihentikan apabila koefisien–koefisien dari fungsi tujuan sudah tidak ada yang negatif

Bentuk tabel simpleks adalah sebagai berikut:

Dimana :

m = Banyaknya fungsi Batasan (kendala)

n = Banyaknya variable Ouput

b₁ = Batasan sumber 1

b₂ = Batasan sumber 2

bm = batasan sumber m

Metode SIimpleks Maksimal

Untuk implementasi metode simpleks maksimisasi, kasus yang diambil adalah contoh pada perusahaan meubel pada bagian 2. Tahapan-tahapannya dijelaskan pada bagian berikut.

Menentukan fungsi tujuan dan fungsi-fungsi kendala

Misalkan x₁  = Meja dan x₂  = Kursi

Fungsi Tujuan : Z = 8x₁  + 6x₂

Fungsi-fungsi Kendala:

4 x₁  + 2 x₂ ≤ 60

2 x₁  + 4 x₂  ≤ 48 

Mengubah fungsi tujuan dan fungsi kendala ke bentuk standar

Bentuk Standar Simpleks:

Z - 8x₁  - 6x₂  = 0

4 x₁  + 2 x₂  + x₃  = 60

2x₁  + 4x₂  + x₄  = 48

Dengan x₃ dan x₄ adalah variabel s

 .

Membuat tabel simpleks awal

Menentukan Kolom Kunci dan Baris Kunci sebagai dasar iterasi.Kolom kunci ditentukan oleh nilai Z yang paling kecil (Negatif)

Baris Kunci ditentukan berdasarkan nilai indeks terkecil.

Cara menentukan indeks = (Nilai kanan (NK))/(Kolom kunci (KK))

Menentukan nilai elemen cell yaitu nilai perpotongan antara kolom kunci dengan baris dan kunci.

Langkah-langkah di atas disajikan pada tabel simpleks berikut ini

Melakukan Iterasi

Dengan menentukan baris kunci baru dan baris- baris lainnya termasuk Z.

Membuat baris kunci baris

baris kunci baru= (baris kunci lama)/(elemen cell)

baris kunci baru 

(x₁ )= [4  2  1  0  60] / 4

        = [1  ½    ¼   0   15]

Membuat baris Z baru

barisbaris Z baru=baris Z lama-(nilai kolom kunci baris

yang sesuai*baris kunci baru)

Baris Z baru = [-8    -6    0   0   0] – (-8)[1     ½    ¼     0    15]

                    =[0   -2    2    0     120]

Membuat baris variabel baru

Baris X₄ Baru = Baris X₄ Lama – (Nilai Kolom Kunci Baris

yang Sesuain* Baris Kunci Baru)

Baris X₄ Baru =[2   4   0  1   48] – 2[1    ½    ¼    0    15]

                      = [0    3     -1/2     1      18]

Baris kunci baru (X₁ ), baris Z baru, baris X₄ baru, nilai-nilainua sidajikan pada tabel simpleks berikut. Tabel simpleks ini adalah tabel simpleks hasil iterasi pertama.

1. Selesaikan linear program berikut ini dengan metode simpleks.
Maksimumkan Z = 400x₁ + 300x₂ 
Fungsi kendala (Batasan) :

4x₁ + 6 x₂ ≤ 1200

4x₁ + 2x₂ ≤ 800

x₁ ≤ 250

x₂ ≤ 300

JAWABAN :

Langkah-langkah :

1) mengubah fungsi tujuan dan fungsi kendala

4x₁ + 6 x₂ ≤ 1200 menjadi  4x₁ + 6 x₂ + x₃ = 1200

4x₁ + 2x₂ ≤ 800 menjadi 4x₁ + 2x₂ +x₄ =  800

x₁ ≤ 250 menjadi x₁ + x₅ = 250

x₂ ≤ 300 menjadi x₂ + x₆ =  300

Z – 400x₁ – 300x₂ = 0 menjadi Z – 400x₁ – 300x₂ + x₃ + x₄ + x₅ + x₆ = 0

2) menyusun persamaan sesuai dengan tabel di bawah ini, kemudian mencari kolom kunci.

kolom kunci adalah kolom yang mempunyai nilai pada baris Z yang bernilai negatif dengan angka terbesar.

setelah mencari kolom kunci maka mencari kolom baris dari index positif yang terkecil.

index = nilai kanan (NK)/nilai kolom kunci.

var	z	x1	x2	x3	x4	x5	x6	nk	index
z	1	-400	-300	0	0	0	0	0	0
x3	0	4	6	1	0	0	0	1200	300
x4	0	4	2	0	1	0	0	800	200
x5	0	1	0	0	0	1	0	250	250
x6	0	0	1	0	0	0	1	300	#DIV/0!

Selanjutnya letak variabel yang menjadi kolom kunci akan masuk dalam variabel baris menggantikan variabel pada baris kunci. angka merah pada tabel merupakan angka kunci

3) mengubah nilai-nilai baris kunci 

mengubah nilai-nilai baris kunci yaitu :

Baris baru kunci = baris kunci : angka kunci 

4) mengubah nilai-nilai selain baris kunci sehingga nilai-nilai kolom kunci selain baris kunci adalah 0.

Baris baru = baris lama - (koefisien angka kolom kunci x nilai baris baru kunci)

tabel barunya adalah :

var	z	x1	x2	x3	x4	x5	x6	nk	index
z	1	0	-100	0	100	0	0	80000	-800
x3	0	0	4	1	-1	0	0	400	100
x1	0	1	0.5	0	0.25	0	0	200	400
x5	0	0	-0.5	0	-0.25	1	0	50	-100
x6	0	0	1	0	0	0	1	300	300

  

  5) Lanjutkan perbaikan-perbaikan tersebut dari langkah 2 sampai 4 hingga nilai baris Z tidak ada yang negatif.

var	z	x1	x2	x3	x4	x5	x6	nk	index
z	1	0	0	25	75	0	0	90000
x2	0	0	1	0.25	-0.25	0	0	100
x1	0	1	0	-0.125	0.375	0	0	150
x5	0	0	0	0.125	-0.375	1	0	100
x6	0	0	0	-0.25	0.25	0	1	200

dari tabel terahir maka dapat simpulkan bahwa :

nilai maksimum (Z) adalah 90.000

dengan nilai x2 adalah 100 dan nilai x1 adalah 150.

Sumber

http://mathematicissofun.blogspot.co.id/2014/01/metode-simpleks_6.html#.WNgGFfmGOMo

http://ridhoanandasmg.blogspot.co.id/2014/11/soal-latihan-metode-simpleks-riset.html