Peer Revier Publikasi ilmiah

Metode simpleks yang direvisi dengan pemrograman Matlab

Zuhri

Sekolah Tinggi Ilmu Manajemen Sukma

Zuhri_muin@yahoo.com

Abstrak

Metode simpleks yang direvisi adalah suatu metode yang didesain untuk mencapai hal yang tepat sama seperti pada metode simpleks asli, akan tetapi dengan suatu cara yang lebih efisien untuk dilaksanakan. Metode ini merupakan versi yang disempurnakan dari prosedur aslinya. Metode ini menghitung dan menyimpan insformasi yang diperlukan sekarang serta data yang penting disimpan dalam bentuk yang lebih padat.

Metode simpleks yang direvisi secara eksplisit memanipulasi matriks sehingga masalahnya harus dinyatakan dalam bentuk notasi matriks dan dapat dihitung dengan menggunakan pemrograman Matlab( Matrix Laboratory).

Kata Kunci: Metode simpleks, Metode simpleks direvisi, Matlab

A. Pendahuluan

Metode Simpleks Merupakan metode yang umum digunakan untuk menyelesaikan seluruh problem program linier, baik yang melibatkan dua variabel keputusan maupun lebih dari dua variabel keputusan.

Metode simpleks pertama kali diperkenalkan oleh George B. Dantzig pada tahun 1947 dan telah diperbaiki oleh beberapa ahli lain. Salah satu teknik penentuan solusi optimal yang digunakan dalam pemrograman linier adalah metode simpleks.  Penentuan solusi optimal menggunakan metode simpleks didasarkan pada teknik eleminasi Gauss Jordan. Penentuan solusi optimal dilakukan dengan memeriksa titik ekstrim satu per satu dengan cara perhitungan iteratif , sehingga penentuan solusi optimal dengan simpleks dilakukan tahap demi tahap yang disebut dengan iterasi. Iterasi ke-i hanya tergantung dari iterasi sebelumnya (i-1).

Dikarenakan solusi metode simpleks yang rumit dan membutuhkan waktu maka telah dikembangkan sebuah pendekatan yang berorientasi matriks yang disebut dengan metode simpleks revisi (RMS.

Metode simpleks yang direvisi adalah suatu metode yang didesain untuk mencapai hal yang tepat sama seperti pada metode simpleks asli, akan tetapi dengan suatu cara yang lebih efisien untuk dilaksanakan. Metode ini merupakan versi yang disempurnakan dari prosedur aslinya. Metode ini menghitung dan menyimpan insformasi yang diperlukan sekarang serta data yang penting disimpan dalam bentuk yang lebih padat.

Metode simpleks yang direvisi secara eksplisit memanipulasi matriks sehingga masalahnya harus dinyatakan dalam bentuk notasi matriks dan dapat dihitung dengan menggunakan computer kususnya pemrograman Matlab( Matrix Laboratory).

B.METODOLOGI

Pada paper ini pertama sekali ditentukan formulasi model dari metode simpleks yang direvisi dengan menggunakan symbol- symbol. Selanjutnya dari formulasi model yang dibentuk dibuat contoh dan kemudian diselesaikannya dengan Matlab solver.

C. Formulasi Model Metode Simpleks yang direvisi

Dengan menggunakan matriks maka bentuk baku model pemrograman linear sebagai berikut:

Memaksimumkan Z = cx

Dengan kendala:

                            Ax  b dan x  0

Dimana c merupakan vector baris.

c = [ c₁, c₂,…., c_n],

x,b,0 merupakan vector- vector kolom sedemikian rupa sehingga

                                     x =  ;   b = ;   0 =  dan A merupakan matriks koefisien yang berordo mxn.

                                      A= 

Untuk memperoleh masalah dalam bentuk diperluas maka masukkanlah vector kolom dari variable- variable slack yaitu,

x_s  =  

sehingga kendala-kendala menjadi

 [A,I] = b dan  dimana I merupakan matriks identitas m x  m dan vector kosong 0 mempunyai ( n+m) unsur.

D. PENYELESAIAN LAYAK DASAR.

Pendekatan umum dari metode simpleks adalah untuk memperoleh suatu urutan penyelesaian-penyelesaian dasar yang semakin baik sampai tercapai suatu penyelesaian yang optimal.

Salah satu ciri pokok metode simpleks yang direvisi adalah mencakup cara dengan mana setiap penyelesaian layak dasar baru diselesaikan setelah variable-variabel dasar dan tidak dasar diketahui. Jika variable- variable tersebut  sudah tertentu maka penyelesaian dasar yang dihasilkannya merupakan penyelesaian dari dan ke m persamaan.

                                                     [A,I] = b,

dimana ke n variable tidak dasar dari antara ke ( n+m) unsur dari

                                                         

dibuat sama dengan nol. Jika ke n variable ini dieliminasi dengan membuatnya sama dengan nol maka masih ada suatu himpunan m persamaan dengan m variable yang tidak diketahui( variable-variabel dasar). Himpunan persamaan ini dapat dinyatakan dengan

                                                      Bx_B = b,

dimana vector dari variable-variabel dasar.

                                                  x_B =,

diperoleh dengan cara menghilangkan variable-variabel tidak dasar dari

                                                        

dan matriks basisnya,

                                        B =

Diperoleh dengan cara mengeliminasi kolom-kolom yang berkaitan dengan koefisien-koefisien variable-variabel tidak dasar dari [A,I].

Metode simpleks hanya memperkenalkan variable- variable dasar sedemikian rupa sehingga B adalah titik tunggal, sehingga B^-1 akan selalu ada. Oleh karena itu, untuk menyelesaikan Bx_B= b kedua ruas harus dikalikan terlebih dahulu dengan B^-1,

                                             B^-1 Bx_B= B^-1 b.

Karena B^-1B= I maka penyelesaian yang diinginkan untuk variable-variabel dasar adalah

                                             x_B = B^-1 b

Andaikan c_B adalah vector yang unsur-unsurnya merupakan koefisien- koefisien fungsi tujuan

( termasuk nol untuk variable-variabel slack) bagi unsur-unsur x_B yang bersesuaian. Maka nilai fungsi tujuan untuk penyelesaian  dasar ini adalah

                                          Z= c_B x_B = c_B B^-1 b.

Contoh Persoalan: ( Perusahaan Kaca)

Perusahaan PT. ASAHIMAS GLASS LTD merupakan produsen produk kaca berkualitas tinggi, termasuk kaca jendela dan pintu. Perusahaan ini membawahi tiga pabrik. Kerangka aluminium dan barang- barang logam dibuat dipabrik 1, kerangka kayu dibuat dipabrik 2 dan pabrik 3 dipakai untuk memproduksi kaca dan merakit produk akhir.

Karena penghasilan semakin menurun, pimpinan perusahaan telah memutuskan untuk mengubah produksinya. Berbagai produk yang tidak menguntungkan dihentikan produksinya, dan tindakan ini akan memperbesar kapasitas produksi untuk membuat satu atau dua dari produk baru yang potensial yang sedang ada permintaannya dipasar. Salah satu produk yang diusulkan( produk 1) adalah merupakan pintu kaca setinggi delapan kaki dengn kerangka aluminium. Produk satu lagi ( produk 2) merupakan jendela gantung ganda yang besar ( 4x 6 ) kaki dengan kerangka kayu. Bagian pemasaran berpendapat bahwa perusahaan ini dapat menjual kedua produk sebanyak yang dapat dihasilkan dengan kapasitas yang tersedia. Akan tetapi, karena kedua produk akan bersaingan untuk kapasitas produksi yang sama dipabrik 3, maka tidak jelas bauran bagaimana antara kedua produk akan saling menguntungkan. Oleh karena itu, pimpinan perusahaan meminta bagian riset operasi untuk mempelajari masalah ini. Setelah diadakan penelitian, bagian riset operasi menentukan:

1.      Persentasi dari kapasitas produksi setiap pabrik yang akan tersedia untuk produk-produk ini.

2.      Persentasi yang dibutuhkan dari setiap produk untuk setiap unit yang dihasilkan per menit.

3.      Laba per unit dari setiap produk.

Insformasi ini dituangkan dalam table berikut ini:

Tabel I. Data PT. ASAHIMAS GLASS  Co LTD

Kapasitas yang dipakai tingkat produksi
Pabrik	Produk 1                         2	Kapasitas tersedia
1 2 3	1                                                0 0                        2 3                        2	4 12 18
Laba per unit	$3                     $5

Penyelesaian:

Untuk merumuskan model matematis masalah ini sebagai berikut:

Misalkan

X₁ = Jumlah unit produksi unit 1

X₂  = Jumlah unit produksi unit 2

Z = konstribusi yang dihasilkan kepada laba per menit

Maka model matematika sebagai berikut:

Maksimumkan                       Z= 3X₁ + 5X₂

Dengan kendala/batasan 

             1.  X₁  4

             2.   2X₂  12

             3. 3X₁ + 2X₂  18

                  X₁, X₂  0

Dari model matematika diatas, dapatlah dihitung nilai-nilai X₁, X₂ dan Z maksimum dengan menggunakan metode simpleks yang direvisi.

D.1. Solusi Metode simpleks yang direvisi

Untuk implementasi metode simpleks yang direvisi, kasus yang diambil adalah contoh pada perusahaan kaca yang tahapan- tahapan dijelaskan sebagai berikut:

1.Menentukan Koefisien fungsi tujuan

                                    c = [ 3 5]

 2. Menentukan koefisien pada masing- masing kendala dan menambahkan slack variable.

                               [A,I] =  

 3. Menentukan koefisien pada sisi kanan kendala

                               b =  

4. Menentukan variable fungsi

.                             x =

5. menentukan variable slack

                                

6. Menentukan vector dari variable- variable dasar pada iterasi 0

                              x_B = dimana x_B = B^-1 b

B =  = B^-1, maka x_B =  = B^-1 b  

Dengan menggunakan Matlab programe sebagai berikut:

>> A=[1  0 0; 0  1 0; 0  0 1];

>> B=[ 4; 12; 18];

>> C= A*B

C =

     4

    12

    18

Jadi x_B =

7. Menentukan hasil perkalian vector baris dari koefisien- koefisien fungsi tujuan dengan vector kolom dari variable- variable dasar pada iterasi 0

c_B = [ 0  0  0],  maka Z = c_B x_B Z = [ 0  0  0] Z = 0

Dengan Matlab program sebagai berikut:

>> A=[0  0  0];

>> B=[4;12;18];

>> C= A*B

C =

     0

8.  Menentukan kembali vector dari variable- variable dasar pada iterasi 1

    x_B =  ; B = ; B^-1= dihitung dengan menggunakan program matlab sebagai berikut:

>> B=[1  0  0; 0  2  0; 0  2  1];

>> inv(B)

ans =

    1.0000         0         0

         0    0.5000         0

         0   -1.0000    1.0000

atau B^-1= ; maka x_B = B^-1 b

= =

>> inv(B)

ans =

    1.0000         0         0

         0    0.5000         0

         0   -1.0000    1.0000

>> D=[4;12;18];

>> X= inv(B)*D

X =

     4

     6

     6

9. Menentukan kembali hasil perkalian vector baris dari koefisien- koefisien fungsi tujuan dengan vector kolom dari variable- variable dasar pada iterasi 1.

 c_B = [ 0  5  0] maka Z = c_B x_B Z = [ 0  5  0] Z = 30

dengan matlab program sebagai berikut:

>> A=[0  5  0];

>> B=[4;6;6];

>> Z=A*B

Z =

    30

10. Menentukan kembali vector dari variable- variable dasar pada iterasi 2.

x_B =  ; B = ; B^-1= dihitung dengan menggunakan program matlab sebagai berikut:

>> B=[1  0  1; 0  2  0; 0  2  3];

>> inv(B)

ans =

    1.0000    0.3333   -0.3333

         0    0.5000         0

         0   -0.3333    0.3333

Atau B^-1=  maka x_B = B^-1 b =

Dengan matlab program sebagai berikut:

>> B=[1  0  1; 0  2  0; 0  2  3];

>> inv(B)

ans =

    1.0000    0.3333   -0.3333

         0    0.5000         0

         0   -0.3333    0.3333

>> C=[4;12;18];

>> X= inv(B)*C

X =

     2

     6

     2

Atau  

11. Menentukan kembali hasil perkalian vector baris dari koefisien- koefisien fungsi tujuan dengan vector kolom dari variable- variable dasar pada iterasi 2.

 c_B = [ 0  5  3] maka Z = c_B x_B Z = [ 0  5  3] Z = 36

>> A=[ 0 5 3];

>> B=[2;6;2];

>> Z=A*B

Z =

    36

E. Hasil

Karena nilai- nilai pada baris Z sudah optimal yang berarti pada iterasi 2 proses simpleks yang direvisi selesai dan solusi yang diperoleh:

X₃ = slack variable = 2  , nilai X₄ dan X₅ = 0

X₂ = X₂  = Jumlah unit produksi unit 2 = 6 unit,

X₁ =  X₁ = Jumlah unit produksi unit 1 = 2 unit,

Z = konstribusi yang dihasilkan kepada laba per menit adalah $36 artinya untuk memperoleh keuntungan yang maksimum maka perusahaan sebaiknya memproduksi  pintu kaca sebanyak 2 unit dan jendela gantung ganda sebanyak 6 unit per menit.

Test Maksimumkan  Z = 3X₁ + 5 X₂

                                         Z = 3( 2) + 5(6)

                                Z = 36.( Terbukti).

F. Kesimpulan

1. Metode simpleks yang direvisi memberikan cara yang efektif untuk menyesuaikan metode simpleks pada implementasi untuk computer.

2. Metode simpleks yang direvisi secara eksplisit menggunakan manipulasi matriks sehingga masalahnya harus dinyatakan dengan notasi matriks.

3. Metode simpleks yang direvisi merupakan prosedur perhitungan yang lebih efisien dibandingan dengan metode simpleks dalam bentuk asli / standart.

G. Daftar Pustaka

1.Bronson,R; Naadhimutu, G; 1997, Scaum’s Outline of Theory and Problem of Operations Research, 2^nd  Editions, New York: McGraw-Hill.

2.Frederick, S. H and Gerald, Lieberman, L. (1994).  Introduction to operations research McGraw-Hill Book Company, New York; pp: 122- 137.

3. Hua Wenhui; (1990), Application of the revised simplex Method to the farm Planning model, Hangzhou University, Hangzhou) China,  pp:18-26.

4. Taha, Hamdy A; Riset Operasi – Jilid 1, Jakarta: Binarupa Aksara, 1996