METODE SIMPLEKS

Muhammad Faisal Ramadhan

14315567

2TA02

Riset Operasi

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 simpleks pertamakali 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. Sumber daya dalam keadaan terbatas

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

Sebelum melakukan perhitungan iteratif untuk menentukan solusi optimal, pertama sekali bentuk umum pemrograman linier dirubah ke dalam bentuk baku terlebih dahulu. Bentuk baku dalam metode simpleks tidak hanya mengubah persamaan kendala ke dalam bentuk sama dengan, tetapi setiap fungsi kendala harus diwakili oleh satu variabel basis awal. Variabel basis awal menunjukkan status sumber daya pada kondisi sebelum ada aktivitas yang dilakukan. Dengan kata lain, variabel keputusan semuanya masih bernilai nol. Dengan demikian, meskipun fungsi kendala pada bentuk umum pemrograman linier sudah dalam bentuk persamaan, fungsi kendala tersebut masih harus tetap berubah.

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

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

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

3.    Fungsi kendala dengan persamaan dalam benttuk umum,ditambahkan satu artificial variabel (variabel buatan).

Perhatikan kasus A berikut  :

Fungsi tujuan : minimumkan z = 2 x₁ + 5.5 x₂

Kendala :

x₁ + x₂ = 90

0.001 x₁ + 0.002 x₂ ≤ 0.9

0.09 x₁ + 0.6 x₂ ≥ 27

0.02 x₁ + 0.06 x₂ ≤ 4.5

x₁, x₂ ≥ 0

Bentuk di atas adalah bentuk umum pemrograman liniernya. Kedalam bentuk baku, model matematik tersebut akan berubah menjadi :

Fungsi tujuan : minimumkan z = 2 x₁ + 5.5 x₂

Kendala :

x₁ + x₂ + s₁ = 90

0.001 x₁ + 0.002 x₂ + s₂ = 0.9

0.09 x₁ + 0.6 x₂ – s₃ + s₄ = 27

0.02 x₁ + 0.06 x₂ + s₅ = 4.5

x₁, x₂ , s₁, s₂, s₃, s₄, s₅  ≥ 0

Fungsi kendala pertama mendapatkan variable buatan (s₁), karena bentuk umumnya sudah menggunakan bentuk persamaan. Fungsi kendala kedua dan keempat  mendapatkan variabel slack (s₂ dan s₅) karena bentuk umumnya menggunakan  pertidaksamaan ≤, sedangkan fungsi kendala ketiga mendapatkan variabel surplus (s₃) dan variabel buatan (s₄) karena bentuk umumnya menggunakan pertidaksamaan ≥.

Perhatikan pula kasus B berikut ini :

Maksimumkan z = 2x₁ + 3x₂

Kendala :

10 x₁ + 5 x₂ ≤ 600

6 x₁ + 20 x₂ ≤ 600

8 x₁ + 15 x₂ ≤ 600

x₁, x₂ ≥

Bentuk di atas juga merupakan bentuk umum. Perubahan ke dalam bentuk baku hanya membutuhkan variabel slack, karena semua fungsi kendala menggunakan bentuk pertidaksamaan ≤ dalam bentuk umumnya. Maka bentuk bakunya adalah sebagai berikut :

Maksimumkan z = 2x₁ + 3x₂ + 0s₁ + 0s₂ + 0s₃

Kendala :

10 x₁ + 5 x₂ + s₁ = 600

6 x₁ + 20 x₂ + s₂ = 600

8 x₁ + 15 x₂ + s₃ = 600

x₁, x₂ , s₁ , s₂ , s₃ ≥ 0

s₁ , s₂ , s₃ merupakan  variable slack.

PEMBENTUKAN TABEL SIMPLEKS

Dalam perhitungan iterative, kita akan bekerja menggunakan tabel. Bentuk baku yang sudah diperoleh, harus dibuat ke dalam bentuk tabel.

Semua variabel yang bukan variabel basis mempunyai solusi (nilai kanan) sama dengan nol dan koefisien variabel basis pada baris tujuan harus sama dengan 0. Oleh karena itu kita harus membedakan pembentukan tabel awal berdasarkan variabel basis awal. Dalam sub bab ini kita hanya akan memperhatikan fungsikendala yang menggunakan variabel slack dalam bentuk bakunya, sedangkan yang menggunakan variabel buatan akan dibahas pada sub bab lainnya.

Gunakan kasus B di atas, maka tabel awal simpleksnya adalah :

VB	X1	X2	S1	S2	S3	solusi
Z	-2	-3	0	0	0	0
S1	10	5	1	0	0	600
S2	6	20	0	1	0	600
S3	8	15	0	0	1	600

LANGKAH-LANGKAH PENYELESAIAN

Langkah-langkah penyelesaian 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 pivot. Penentuan kolom pivot dilihat dari koefisien fungsi tujuan (nilai di sebelah kanan baris z) dan tergantung dari bentuk tujuan. Jika tujuan maksimisasi, maka kolom pivot  adalah kolom dengan koefisien paling negatif. Jika tujuan minimisasi , maka kolom pivot adalah kolom dengan koefisien positif terbesar. Jika kolom pivot ditandai dan ditarik ke atas, maka kita akan mendapatkan variabel keluar. Jika nilai paling negatif (untuk tujuan maksimisasi) atau positif terbesar (untuk tujuan minimisasi) lebih dari satu, pilih salah satu secara sembarang.

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

4.    Tentukan elemen pivot. Elemen pivot merupakan nilai yang terletak pada perpotongan kolom dan baris pivot.

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

6.    Periksa apakah tabel sudah optimal. Keoptimalan tabel dilihat dari koefisien fungsi tujuan (nilai pada baris z) dan tergantung dari bentuk tujuan. Untuk tujuan maksimisasi, tabel sudah optimal jika semua nilai pada baris z sudah positif atau 0. Pada tujuan minimisasi, 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.

Selesaikan kasus berikut ini menggunakan metode simpleks :

Maksimum z = 8 x₁ + 9 x₂ + 4x₃

Kendala :

x₁ + x₂ + 2x₃ ≤ 2

2x₁ + 3x₂ + 4x₃ ≤ 3

7x₁ + 6x₂ + 2x₃ ≤ 8

x₁,x₂,x₃ ≥ 0

Penyelesaian :

Bentuk bakunya adalah :

Maksimum z = 8 x₁ + 9 x₂ + 4x₃ + 0s₁ + 0s₂ + 0s₃ atau

z - 8 x₁ - 9 x₂ - 4x₃ + 0s₁ + 0s₂ + 0s₃ = 0

Kendala :

x₁ + x₂ + 2x₃ + s₁  = 2

2x₁ + 3x₂ + 4x₃ + s₂ = 3

7x₁ + 6x₂ + 2x₃  + s₃ = 8

x₁,x₂,x₃ ,s₁ , s₂ , s₃ ≥ 0

Solusi / table awal simpleks :

VB	X1	X2	X3	S1	S2	S3	NK	Rasio
Z	-8	-9	-4	0	0	0	0
S1	1	1	2	1	0	0	2
S2	2	3	4	0	1	0	3
S3	7	6	2	0	0	1	8

Karena nilai negative terbesar  ada pada kolom X₂, maka kolom X₂ adalah kolom pivot dan X₂adalah variabel masuk. Rasio pembagian nilai kanan  dengan kolom pivot terkecil adalah 1 bersesuaian  dengan  baris s₂, maka baris s₂ adalah baris pivot dan s₂ adalah varisbel keluar. Elemen pivot adalah 3.

VB	X1	X2	X3	S1	S2	S3	NK	Rasio
Z	-8	-9	-4	0	0	0	0
S1	1	1	2	1	0	0	2	2
S2	2	3	4	0	1	0	3	1
S3	7	6	2	0	0	1	8	8/6

Iterasi 1

Nilai pertama yang kita miliki adalah nilai baris  pivot baru (baris x₂). Semua nilai pada baris s₂pada tabel solusi awal dibagi dengan 3 (elemen pivot).

VB	X1	X2	X3	S1	S2	S3	NK	Rasio
Z
S1
x2	2/3	1	4/3	0	1/3	0	1
S3

Perhitungan nilai barisnya :

Baris z :

            -8         -9         -4         0          0          0          0

    -9 (  2/3         1         4/3       0          1/3       0          1 )   -

            -2           0        8         0          3          0          9

Baris s₁ :

            1          1          2          1          0          0          2

     1   (2/3        1          4/3       0          1/3       0          1 ) -

            1/3       0          2/3       1          -1/3      0          1

Baris s3 :

            7          6          2          0          0          1          8

      6 ( 2/3        1          4/3       0          1/3       0          1 ) -

            3          0          -6         0          -2         1          2

Maka tabel iterasi 1 ditunjukkan tabel di bawah. Selanjutnya kita periksa apakah tabel sudah optimal atau belum. Karena nilai baris z di bawah variabel x₁ masih negatif, maka tabel belum optimal. Kolom dan baris pivotnya ditandai pada tabel di bawah ini :

VB	X1	X2	X3	S1	S2	S3	NK	Rasio
Z	-2	0	8	0	3	0	9	-
S1	1/3	0	2/3	1	-1/3	0	1	3
X2	2/3	1	4/3	0	1/3	0	1	3/2
S3	3	0	-6	0	-2	1	2	2/3

Variabel masuk  dengan demikian adalah X₁ dan variabel  keluar adalah S₃ . Hasil perhitungan iterasi ke 2 adalah sebagai berikut :

Iterasi 2 :

VB	X1	X2	X3	S1	S2	S3	NK	Rasio
Z	0	0	4	0	5/3	2/3	31/3
S1	0	0	4/3	1	-1/9	-1/9	7/9
X2	0	1	8/3	0	7/9	-2/9	5/9
X1	1	0	-2	0	-2/3	1/3	2/3

Tabel sudah optimal, sehingga perhitungan iterasi dihentikan !

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/variabel keputusan bernilai nol). Jika titik ekstrim berjumlah n, kemungkinan terburuknya kita akan melakukan perhitungan iteratif sebanyak n kali.

MEMBACA TABEL OPTIMAL

Membaca tabel optimal adalah bagian penting bagi pengambil keputusan. Ada beberapa hal yang bisa dibaca dari table optimal :

1.                  Solusi optimal variable keputusan

2.                  Status sumber daya

3.                  harga bayangan (dual/shadow prices).

Menggunakan table optimal :

VB	X1	X2	X3	S1	S2	S3	NK
Z	0	0	4	0	5/3	2/3	31/3
S1	0	0	4/3	1	-1/9	-1/9	7/9
X2	0	1	8/3	0	7/9	-2/9	5/9
X1	1	0	-2	0	-2/3	1/3	2/3

Solusi optimal X₁ = 2/3,  X₂  = 5/9 , X₃ = 0 dan Z = 31/3, artinya untuk mendapatkan keuntungan maksimum sebesar $ 31/3 , maka perusahaan sebaiknya menghasilkan produk 1 sebesar 2/3 unit dan produk 2  sebesar 5/9 unit.

Status sumber daya :

Sumber daya pertama dilihat dari keberadaan variable basis awal dari setiap fungsi kendala pada table optimal. Dalam kasus di atas, untuk fungsi kendala pertama periksa keberadaan S₁ pada variable basis table optimal. Periksa keberadaan S₂ pada variable basis table optimal untuk fungsi kendala kedua. Periksa keberadaan S₃ pada variable basis table optimal untuk fungsi kendala ketiga.

S₁ = 7/9.  Sumber  daya ini disebut berlebih (abundant)

S₂ = S₃ = 0. Kedua sumber daya ini disebut habis terpakai (scarce).

Harga bayangan :

Harga bayangan dilihat dari koefisien variable slack atau surplus pada baris fungsi tujuan.

Koefisien S₁ pada baris fungsi tujuan table optimal = 0, dengan demikian harga bayangan sumber daya pertama adalah 0

Koefisien S₂ pada baris fungsi tujuan table optimal = 5/3, dengan demikian harga bayangan sumber daya kedua adalah 5/3

Koefisien S₃ pada baris fungsi tujuan table optimal = 2/3, dengan demikian harga bayangan sumber daya kedua adalah 2/3.

Sumber :

http://kampungtembakau.blogspot.co.id/2013/01/metode-simpleks.html

https://bimarb.wordpress.com/2017/03/27/metode-simpleks-riset-operasi/