Friday, April 14, 2017

Masalah Minimasi Metode Simpleks

Masalah Minimasi Metode Simpleks

Masalah Minimasi

Pada topik sebelumnya tentang : Pemecahan Program Linear Metode Simpleks, contoh soal yang dibahas adalah masalah maksimasi. Bagaimana jika masalahnya adalah masalah minimasi?

Metode minimasi biasanya digunakan untuk mencari biaya minimum dalam suatu produksi perusahaan, sehingga didapatkan biaya terendah untuk memproduksi suatu produk atau jasa.

Untuk metode pemecahanya,kita dapat mengubah fungsi tujuan minimasi menjadi fungsi maksimasi dengan mengalikan fungsi tujuan minimasi tersebut dengan -1, karena maksimasi merupakan minimasi negatif.

Contoh, minimumkan Z = 3 X1 + 4X2, maka persamaan fungsi tujuan tersebut sama dengan : maksimumkan (-Z) = -3 X1 - 4 X2 dengan seluruh pembatas yang tidak berubah.

Cara lain dapat juga memodifikasi langkah ke 3 simpleks pada contoh diatas, yaitu memilih pada baris Z yang bernilai positif terbesar sebagai entering variabel atau kolom pivot. Jika pada baris sudah tidak ada lagi yang bernilai positif maka solusi sudah optimal.


Persoalan Program Linear Dengan Pembatas Bertanda "≥" dan atau "=".

Dalam pembicaraan mengenai metode simpleks, variabel slack digunakan sebagai solusi basis awal, sehingga ruas kanan persamaan beharga positif. Berikut ini dibahas cara mengatasi penyimpangan-penyimpangan dari bentuk normal diatas agar bisa diselesaikan dengan metode simpleks. Penyimpangan tersebut dapat berupa tanda sama dengan (=), kendala bertanda lebih besar sama dengan (≥), atau ruas kanan bernilai negatif.

Contoh : 
Minimunkan : Z = 7 X1 + 3 X2
Kendala :
4 X1 + 6 X2 ≤ 36
7 X1 + 5 X2 = 35
8 X1 + 4 X2 ≥ 32
X1, X2 ≥ 0

  • Pada fungsi kendala yang pertama, untuk mengubah menjadi persamaan harus ditambah variabel slack, yang sekaligus digunakan sebagai basis pada tabel awal simpleks. Persamaan tersebut menjadi : 
    4 X1 + 6 X2 + S1 = 36.

  • Pada fungsi kendala yang kedua sudah dalam bentuk persamaan, karena belum ada variabel yang merupakan basis pada tabel awal, maka perlu ada variabel dummy (variabel buatan) yang disebut variabel artificial (lambang "R"). Dinamakan artificial karena tidak mempunai arti nyata, artinya iterasi-iterasi metode simpleks akan secara otomatis menjadikan variabel artificial tidak muncul lagi (bernilai nol) yaitu apabila persoalan semula yang telah terselesaikan. Dengan kata lain variabel artificial ini digunakan hanya untuk memulai solusi dan harus menghilangkanya pada akhir solusi. Jika tidak demikian, maka solusi yang diperoleh akan tidak layak. Untuk itu persamaan pembatas kedua diatas akan menjadi : 
    7 X1 + 5 X2 + R1 = 35.

  • Sedangkan fungsi pembatas ketiga yang bertanda "≥", maka harus diubah menjadi tanda "≤" dan akhirnya menjadi tanda "=" agar dapat diselesaikan dengan metode simpleks. Persamaan tersebut dikalikan (-1) akan menjadi : -8 X1 - 4 X2 ≤ -32. Kemudian, ubah ke tanda sama dengan seperti yang telah dibahas diatas maka menjadi : -8 X1 - 4 X2 + S2 = -32. Karena bagian kanan persamaan ini bertanda negatif (-32), maka harus menjadi 8 X1 + 4 X2 - S2 = 32, tetapi karena S1 bertanda negatif, hal ini tidak memungkinkan dalam metode simpleks karena tidak dapat digunakan sebagai basis pada tabel awal. Untuk itu harus ditambahkan variabel artificial R, sehingga persamaan pembatas ketiga tersebut menjadi :
    8 X1 + 4 X2 - S2 + R2 = 32.

  • Dari permbahasan mengenai variabel slack dan variabel artificial berkaitan dengan metode simpleks dapat disimpulkan bahwa :
    1. Apabila fungsi kendala bertanda ≤, maka tambahkan variabel slack.
    2. Apabila fungsi kendala bertanda =, maka tambahkan variabel artificial R.
    3. Apabila fungsi kendala bertanda ≥, maka kurangi dengan variabel slack dan tambahkan variabel artificial R.
    4. Apabila fungsi kendala adalah negatif, maka harus diubah menjadi positif dengan mengalikan (-1) dan sesuaikan dengan ketiga kesimpulan diatas.

Formulasi yang sudah mengalami modifikasi ini disebut formulasi dalam bentuk standar metode simpleks. Sehingga soal diatas bentuk standarnya adalah :
Minimumkan : Z = 7 X1 + 3 X2
Kendala :
4 X1 +6 X2 +S1 += 36
7 X1 +5 X2+ R1 = 35
8 X1 +4 X2- S2+ R2= 32
X1, X2, S1, S2, R1, R20

Penyelesaian persoalan yang mengandung variabel artificial ini dapat dilakukan dengan 2 cara yaitu : metode teknik the big M dan teknik dua fase.

1. Teknik The Big M (Metode Penalty) :

Pada teknik ini, setiap variabel artificial dalam fungsi tujuan diberikan penalty M, dimana M merupakan bilangan positif yang sangat besar. Penalty bertanda negatif (-) apabila fungsi tujuan maksimasi dan bertanda positif (+) apabila fungsi tujuan minimasi.

Persamaan menurut contoh diatas menjadi :
Minimunkan : Z = 7 X1 + 3 X2 + 0 S1 + 0 S2 + MR1 + MR2
Kendala :
4 X1 +6 X2 +S1 += 36
7 X1 +5 X2+ R1 = 35
8 X1 +4 X2- S2+ R2= 32
X1, X2, S1, S2, R1, R20

Untuk memasukan model matematis persoalan diatas dalam tabel simpleks, maka terlebih dahulu melakukan subtitusi nilai R1 dan R2 pada persamaan kendala dan pada persamaan fungsi tujuan Z diatas yaitu :
R1 = 35 - 7 X1 - 5 X2
R2 = 32 - 8 X1 - 4 X2 + S2

Kemudian R1 dan R2 tersebut dimasukan kedalam persamaan Z menjadi :
Z = 7 X1 + 3 X2 + MR1 + MR2
Z = 7 X1 + 3 X2 + M(35 - 7 X1 - 5 X2) + M(32 - 8 X1 - 4 X2 + S2)
Z = (7 - 7M - 8M) X1 + (3 - 5M - 4M) X2 + M S2 + (35M + 32M)
Z = (7 - 15M) X1 + (3 - 9M) X2 + M S2 + 67M
Z + (15M - 7) X1 + (9M -3) X2 - M S2 = 67 M

Bedasarkan persamaan terakhir ini maka dilakukan penyelesaian dengan metode simpleks seperti cara penyelesaian yang sudah diuraikan pada bagian sebelumnya tentang : pemecahan program linear metode simpleks.

Iterasi awal hingga iterasi akhir optimal penyelesaian persoalan diatas dapat dilihat pada tabel berikut :
IterasiBasis Z X1 X2 S1 R1 S2 R2 Solusi
0Z1 (15M - 7)(9M -3)00-M067M
S10 46100036
R10 75010035
R20 8400-1132
IterasiBasis Z X1 X2 S1 R1 S2 R2 Solusi
1Z1 0(3M + 1)/200(7M - 7)/8-(15M - 7)/87M + 28
S10 04101/2-1/220
R10 0 3/2017/8-7/87
X10 11/200-1/81/84
IterasiBasis Z X1 X2 S1 R1 S2 R2 Solusi
2Z1 000-M - 1/3-7/6-M + 7/677/3
S10 001-8/3-11/611/64/3
X20 0 102/37/12-7/1214/3
X10 100-1/3-5/125/125/3

Dari iterasi ke-2 pada tabel diatas merupakantabel optimal sehingga diketahui nilai optimal untuk X1 = 5/3, X2 = 14/3, X3 = 0, S1 = 4/3, dan Z = 77/3.

2. Teknik Dua Fase

Sesuai dengan namanya teknik dua fase terdiri dari 2 fase pengerjaan, yaitu :
  1. Fase pertama :
    Pada fase ini tujuan semula diganti dengan meminimumkan jumlah variabel artificialnya, dan diuji apakah persoalan yang dihadapi memilki solusi feasibel atau tidak. Jika nilai minimum fungsi tujuan baru (r) ini beharga nol (seluruh variabel artificial beharga nol), berarti persoalan memiliki solusi feasibel, yang berarti pengerjaan bisa dilanjutkan ke fase 2. Tetapi jika minimum fungsi tujuan baru ini beharga positif, maka persoalan tidak memiliki solusi feasible. Berarti stop!.

  2. Fase kedua :
    Gunakan solusi basis optimum pada fase 1 sebagai solusi awal bagi persoalan sebenarnya. Dalam hal ini ubahlah bentuk fungsi tujuan pada fase 1 dengan mengembalikannya pada fungsi tujuan persoalan sebenarnya dan fungsi batasan diperoleh dari tabel optimal fase 1 tanpa memasukan variabel R nya.

Contoh :  
Minimunkan : Z = 7 X1 + 3 X2
Kendala :
4 X1 + 6 X2 ≤ 36
7 X1 + 5 X2 = 35
8 X1 + 4 X2 ≥ 32
X1, X2 ≥ 0

Bentuk diatas diubah menjadi :
Minimunkan : Z = 7 X1 + 3 X2 + 0 S1 + 0 S2 + MR1 + MR2
Kendala :
4 X1 +6 X2 +S1 += 36
7 X1 +5 X2+ R1 = 35
8 X1 +4 X2- S2+ R2= 32
X1, X2, S1, S2, R1, R20

Subtitusikan :
R1 = 35 - 7 X1 - 5 X2
R2 = 32 - 8 X1 - 4 X2 + S2

Fase 1 :

Minimumkan : 
r = R1 + R2
r = (35 - 7 X1 - 5 X2) + (32 - 8 X1 - 4 X2 + S2)
r = 67 - 15 X1 - 9 X2 + S2
r + 15 X1 + 9 X2 - S2 = 67

Dengan kendala yang sama :
4 X1 +6 X2 +S1 += 36
7 X1 +5 X2+ R1 = 35
8 X1 +4 X2- S2+ R2= 32
X1, X2, S1, S2, R1, R20

Setelah itu lakukan persamaan simpleks dengan r sebagai fungsi tujuan baru menggantikan Z. Masukkanlah persamaan fungsi tujuan baru r tersebut dengan fungsi tujuan minimasi serta persamaan kedalanya dimasukkan dalam tabel simpleks sebagai berikut:
IterasiBasis r X1 X2 S1 R1 S2 R2 Solusi
0r1 15900-1067
S10 46100036
R10 75010035
R20 8400-1132
IterasiBasis r X1 X2 S1 R1 S2 R2 Solusi
1r1 03/2007/8-15/87
S10 04101/2-1/220
R10 0 3/2017/8-7/87
X10 11/200-1/81/84
IterasiBasis r X1 X2 S1 R1 S2 R2 Solusi
2r1 000-1-7/6-10
S10 001-8/3-11/611/64/3
X20 0 102/37/12-7/1214/3
X10 100-1/3-5/125/125/3

Pada iterasi ke-2 terlihat baris r sudah negatif semua dan r bernilai nol, maka persoalan diatas memiliki solusi feasibel. Selanjutnya dilanjutkan ke fase 2, tetapi R tidak diikutsertakan lagi.

Fase 2 :

Bedasarkan tabel optimal fase 1 diatas, dapat dituliskan persamaan :
S1 - 11/6 S2 = 4/3
X2 + 7/12 S2 = 14/3 ⇒ X2 = 14/3 - 7/12 S2
X1 - 5/12 S2 = 5/3 ⇒ X1 = 5/3 + 5/12 S2

Bedasarkan model persoalan sebenarnya, dengan mensubtitusikan persamaan X1 dan X2 diatas diperoleh Z :
Minimumkan :
Z = 7 X1 + 3 X2
Z = 7(5/3 + 5/12 S2) + 3(14/3 - 7/12 S2
Z = 77/3 + 7/6 S2
Z - 7/6 S2 = 77/3

Dengan kendala :
S1 - 11/6 S2 = 4/3
X2+ 7/12 S2 = 14/3
X1- 5/12 S2 = 5/3
X1, X2, S1, S20

Tabel Simpleks fase 2 dengan fungsi tujuan minimasi sebagai berikut :
Basis Z X1 X2 S1S2 Solusi
Z10 00-7/677/3
S10 001-11/64/3
X20 0 107/1214/3
X10 100-5/125/3

Pada tabel diatas, baris Z tidak ada yang positif. Karena fungsi tujuan minimasi berarti telah tercapai kondisi optimal dengan nilai X1 = 5/3, X2 = 14/3, S1 = 4/3. Z = 77/3.

Alternatif pemecahan masalah minimasi simpleks ini juga dapat diselesaikan dengan menggunakan software komputer seperti TORA yang dapat memecahkan program linear. Selain untuk program linear TORA juga bisa dimanfaatkan untuk menyelesaikan jenis persamaan lainya seperti transportasi dan yang lainya.

Perlu anda ketahui sebelum mengakhiri materi simpleks ini, ada beberapa kasus khusus dalam penggunaan simpleks seperti degenerasi, solusi optimum banyak, solusi tak terbatas, dan tidak ada solusi layak. Untuk lebih jelasnya akan dibahas pada topik berikutnya tentang :


EmoticonEmoticon