menyelesaikan metode simplek dengan cara manual

                                                                     Metode Simpleks
 

Metode simpleks digunakan untuk menyelesaikan masalah optimasi yang melibatkan tiga variabel atau lebih yang tidak dapat diselesaikan oleh metode grafik. Metode simpleks adalah metode yang digunakan untuk menyelesaikan permasalahan yang memiliki lebih dari dua variabel.  Metode simpleks didefinisakan sebagai cara menyelesaikan permasalan yang memiliki variabel keputusan minimal dua dengan menggunalkan alat bantu tabel. Metode simpleks dibedakan menjadi dua yaitu, metode simpleks maksimasi untuk mencari keuntungan maksimum dan metode simpleks minimasi untuk mencari biaya minimum.

Apabila suatu persoalan program linier hanya mengandung dua kegiatan (variabel keputusan) saja, maka dapat dipecahkan dengan metode grafik, tetapi jika mengandung tiga atau lebih variabel keputusan, maka metode grafik tidak dapat digunakan lagi, sehingga diperlukan alternatif lain yaitu metode simpleks.

                   Metode simpleks merupakan salah  satu  teknik  penyelesaian dalam program linear yang digunakan sebagai teknik pengambilan keputusan dalam permasalahan yang berhubungan dengan pengalokasian sumber daya 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 dalam riset operasi dan digunakan sebagai prosedur penyelesaian dari setiap program komputer.

                   Penentuan solusi optimal menggunakan simpleks didasarkan pada teknik eliminasi Gauss Jordan. Penentuan solusi optimal dilakukan dengan memeriksa titik ekstrim (ingat kembali solusi grafik) satu per satu dengan cara perhitungan iteratif. Sehingga penentuan solusi optimal dengan simpleks dilakukan tahap demi tahap yang kita sebut dengan iterasi. Iterasi ke-i hanya tergantung dari iterasi sebelumnya (i-1). Ada beberapa istilah yang sangat sering kita gunakan dalam metode simpleks, diantaranya iterasi, variabel non basis, variabel basis, solusi atau nilai kanan, variabel slack, variabel surplus, variabel buatan, kolom kunci, baris kunci, angka kunci, variabel masuk, variabel keluar. Semua istilah ini harus anda ingat baik-baik, karena akan selalu digunakan dalam riset operasional.

Ada beberapa istilah yang sangat sering digunakan dalam metode simpleks, diantaranya :

1.        Iterasi adalah tahapan perhitungan dimana nilai dalam perhitungan itu tergantung dari nilai tabel sebelumnya.

2.        Variabel non basis adalah variabel yang nilainya diatur menjadi nol pada sembarang iterasi. Dalam terminologi umum, jumlah variabel non basis selalu sama dengan derajat bebas  dalam sistem persamaan.

3.        Variabel basis merupakan variabel yang nilainya bukan nol pada sembarang iterasi. Pada solusi awal, variabel basis merupakan variabel slack (jika fungsi kendala merupakan pertidaksamaan ≤ ) atau variabel buatan (jika fungsi kendala menggunakan  pertidaksamaan ≥ atau =). Secara umum, jumlah variabel basis selalu sama  dengan  jumlah fungsi pembatas (tanpa fungsi non negatif).

4.        Solusi atau nilai kanan merupakan nilai sumber daya pembatas yang masih tersedia. Pada solusi awal, nilai kanan atau solusi sama dengan jumlah sumber daya pembatas  awal yang ada, karena aktivitas belum dilaksanakan.

5.        Variabel slack adalah variabel yang ditambahkan ke model matematik kendala untuk mengkonversikan  pertidaksamaan ≤ menjadi persamaan (=). Penambahan variabel ini terjadi pada tahap inisialisasi. Pada solusi awal, variabel slack akan berfungsi sebagai variabel basis.

6.        Variabel surplus adalah variabel yang dikurangkan  dari model matematik kendala untuk mengkonversikan  pertidaksamaan ≥ menjadi persamaan (=). Penambahan ini terjadi pada tahap inisialisasi. Pada solusi awal, variabel surplus tidak dapat berfungsi sebagai variabel basis.

7.        Variabel buatan adalah variabel yang ditambahkan ke model matematik kendala dengan bentuk ≥ atau = untuk difungsikan sebagai variabel basis awal. Penambahan variabel ini terjadi pada tahap inisialisasi. Variabel ini harus bernilai 0 pada solusi optimal, karena kenyataannya variabel ini tidak ada. Variabel hanya ada di atas kertas.

8.        Kolom pivot (kolom kunci) adalah kolom yang memuat variabel masuk. Koefisien pada kolom ini akan menjadi pembagi nilai kanan untuk menentukan baris pivot (baris kunci).

9.        Baris pivot (baris kunci) adalah salah satu baris dari antara variabel basis yang memuat variabel keluar.

10.    Elemen pivot (angka kunci) adalah elemen yang terletak pada perpotongan kolom dan baris kunci. Angka kunci akan menjadi dasar perhitungan untuk tabel simpleks berikutnya.

11.    Variabel masuk adalah variabel yang terpilih untuk menjadi variabel basis pada iterasi berikutnya. Variabel masuk dipilih satu dari antara variabel non basis pada setiap iterasi. Variabel ini pada iterasi berikutnya akan bernilai positif.

12.    Variabel keluar adalah variabel yang keluar dari variabel basis pada iterasi berikutnya dan digantikan oleh variabel masuk. Variabel keluar dipilih satu dari antara variabel basis pada setiap iiterasi. Variabel ini pada iterasi berikutnya akan bernilai nol.

               Ada beberapa hal yang harus diperhatikan dalam membuat bentuk baku atau standar, yaitu:

1.        Nilai kanan fungsi tujuan harus nol (0).

2.        Nilai kanan fungsi kendala harus positif, apabila negatif nilai tersebut dikalikan dengan (-1).

3.        Fungsi kendala dengan pertidaksamaan ≤ dalam bentuk umum, dirubah menjadi persamaan (=) dengan menambahkan satu variabel slack.

4.        Fungsi kendala dengan pertidaksamaan ≥ dalam bentuk umum, dirubah menjadi persamaan (=) dengan mengurangkan satu variabel surplus.

5.        Fungsi kendala dengan persamaan dalam bentuk umum, ditambahkan satu artificial variable (variabel buatan).

                   Perhitungan dalam simpleks menuntut ketelitian  tinggi, khususnya jika angka yang digunakan adalah pecahan. Pembulatan harus diperhatikan dengan baik. Disarankan jangan menggunakan bentuk bilangan desimal, akan lebih teliti jika menggunakan bilangan pecahan. Pembulatan dapat menyebabkan iterasi lebih panjang atau bahkan tidak selesai karena ketidaktelitian dalam melakukan pembulatan.

                   Perhitungan iteratif dalam simpleks pada dasarnya merupakan pemeriksaan satu per satu titik-titik ekstrim layak pada daerah penyelesaian. Pemeriksaan dimulai dari kondisi nol (dimana semua aktivitas atau variabel keputusan bernilai nol). Jika titik ekstrim berjumlah n, kemungkinan terburuknya kita akan melakukan perhitungan iteratif sebanyak n kali.

                     Menyelesaikan Metode Simpleks Secara Manual

                   Langkah-langkah menyelesaikan metode simpleks secara manual adalah sebagai berikut :

1.        Periksa apakah tabel layak atau tidak. Kelayakan tabel simpleks dilihat dari solusi (nilai kanan). Jika solusi ada yang bernilai negatif, maka tabel tidak layak. Tabel yang tidak layak tidak dapat diteruskan untuk dioptimalkan.

2.        Tentukan kolom kunci. Penentuan kolom kunci dilihat dari koefisien fungsi tujuan (nilai di sebelah kanan baris z) dan tergantung dari bentuk tujuan. Jika tujuan berupa maksimisasi, maka kolom kunci adalah kolom dengan koefisien negatif terbesar. Jika tujuan minimisasi, maka kolom kunci adalah kolom dengan koefisien positif terbesar. Perhatikan, kita tidak menggunakan kata-kata nilai terkecil dan terbesar, karena kita memang tidak memilih nilai terkecil dan terbesar. Jika kolom kunci ditandai dan ditarik ke atas, maka kita akan mendapatkan variabel keluar. Jika nilai negatif terbesar (untuk tujuan maksimisasi) atau positif terbesar (untuk tujuan minimisasi) lebih dari satu, pilih salah satu secara sembarang.

3.        Tentukan baris kunci. Baris kunci ditentukan setelah membagi nilai kanan dengan nilai kolom kunci yang bersesuaian (nilai yang terletak dalam satu baris). Dalam hal ini, nilai negatif dan 0 pada kolom kunci tidak diperhatikan, artinya tidak ikut menjadi pembagi. Baris kunci adalah baris dengan rasio pembagian terkecil. Perhatikan, rasio pembagian tidak mungkin bernilai negatif, karena nilai kanan tidak negatif demikian juga dengan nilai kolom kunci. Jika baris kunci ditandai dan ditarik ke kiri, maka kita akan mendapatkan variabel keluar. Jika rasio pembagian terkecil lebih dari satu, pilih salah satu secara sembarang.

4.        Tentukan angka kunci. Angka kunci merupakan nilai yang terletak pada perpotongan kolom dan baris kunci.

5.        Bentuk tabel simpleks baru. Tabel simpleks baru dibentuk dengan pertama sekali menghitung nilai baris kunci baru. Baris kunci baru adalah baris kunci lama dibagi dengan angka kunci. Baris baru lainnya merupakan pengurangan nilai kolom kunci baris yang bersangkutan dikali baris kunci baru dalam satu kolom terhadap baris lamanya yang terletak dalam satu kolom juga.

6.        Periksa apakah tabel sudah optimal. Keoptimalan tabel dilihat dari koefisien fungsi tujuan (nilai pada baris z) dan tergantung dari bentuk tujuan. Untuk tujuan maksimasi, tabel sudah optimal jika semua nilai pada baris z sudah positif atau 0. Pada tujuan minimasi, tabel sudah optimal jika semua nilai pada baris z sudah negatif atau 0. Jika belum, kembali ke langkah no.2, jika sudah optimal baca solusi optimalnya. 

contoh soal......... 

Perusahaan Brilliant menghasilkan 2 jenis sepatu yaitu sepatu dengan merk italy dan felix. Merk italy dibuat dengan sol dari bahan karet. Sedangkan felix dibuat dengan sol dari bahan kulit. Untuk membuat sepatu tersebut diperlukan 3 jenis mesin yaitu A (khusus untuk sol karet), B (khusus untuk sol kulit), dan C (untuk finishing). Untuk setiap lusin sepatu dibutuhkan waktu :

1.        Italy dikerjakan pada mesin A selama 2 jam tanpa melalui mesin B dan di mesin C selama 6 jam.

2.        Felix dikerjakan tanpa melalui mesin A, melalui mesin B selama 3 jam  dan mesin C selama 5 jam.

                   Jam kerja maksimum setiap hari untuk mesin A = 8 jam, melalui mesin B = 15 jam, dan mesin C = 30 jam. Perolehan keuntungan untuk setiap lusin sepatu italy Rp. 30.000,00 dan felix Rp. 50.000,00. Tentukan jumlah produksi sepatu yang menghasilkan laba maksimal.

jawab...... 

1.    Merumuskan masalah

       Tujuan      :           Zmax

       Variabel   :    Italy = x1

                          Felix  = x2

       Kendala   : Waktu dari masing-masing mesin.

2.        Menentukan model matematik

                                 

 

3.        Menentukan persamaan simpleks

   

4.        Membentuk tabel simpleks

 

Dengan demikian, nilai negatif terbesar terletak pada kolom x2, maka kolom kunci terlelak pada kolom x2. Hasil pembagian nilai kanan dengan kolom kunci terdapat nilai positif terkecil pada baris s2, maka baris kunci terletak pada baris s2, dan angka kunci terletak pada kotak x2s2.

a.    Angka baru baris kunci (ABBK)

 

b. Angka baru baris z

 

c.    Angka baru baris s1

                   Angka baru baris s1 ini masih tetap, karena pada persilangan antara baris s1 dengan kolom x2 nilainya sudah nol (0).

       d.    Angka baru baris s3  

  
 

Pada iterasi 1 ini belum optimal, karena nilai pada baris z masih ada yang negatif. Dengan demikian, pengoptimalan masih dilanjutkan. Nilai negatif terbesar terlatak pada kolom x1, maka kolom kunci terletak pada kolom x1. Hasil pembagian antara nilai kanan dangan kolom kunci terdapat nilai positif terkecil pada baris s3, maka baris kunci terletak pada baris s3, dan angka kunci terletak pada kotak x1s3.

   

d.    Angka baru baris x2

                   Angka baru baris x2 ini masih tetap, karena pada persilangan antara baris x2 dengan kolom x1 nilainya sudah nol (0).

 

Pada iterasi 2, nilai pada baris z sudah tidak ada yang bernilai negatif, maka tabel sudah optimal, sehingga perhitungan iterasi dihentikan.

                   Solusi optimal : x1 = 5/6, x2 = 5 dan Z = 275.000, artinya untuk mendapatkan keuntungan maksimum sebesar Rp. 275.000,00, maka perusahaan Brilliant sebaiknya menghasilkan produk sepatu merk italy sebesar 5/6 lusin dan produk sepatu felix sebesar 5 lusin.

                   Status sumber daya dilihat dari keberadaan variabel basis awal dari setiap fungsi kendala pada tabel optimal. Dalam kasus diatas, untuk fungsi kendala pertama, keberadaan s1 pada variabel basis tabel optimal adalah 19/3, maka sumber daya ini disebut berlebihan (abundant), keberadaan s2 dan s3 pada variabel basis tabel optimal adalah 0, maka sumber daya ini disebut habis terpakai (scarce).

                   Harga bayangan ini dilihat dari koefisien variabel slack  atau surplus pada baris fungsi tujuan. Koefisien s1 pada baris fungsi tujuan tabel optimal adalah 0, dengan demikian harga bayangan sumber daya pertama adalah 0. Koefisien s2 pada baris fungsi tujuan tabel optimal adalah 25.000/3, dengan demikian harga bayangan sumber daya kedua adalah 25.000/3. Koefisien s3 pada baris fungsi tujuan tabel optimal adalah 5.000, dengan demikian harga bayangan sumber daya ketiga adalah 5.000.