Masalah Minimasi
Pada topik sebelumnya wacana : Pemecahan Program Linear Metode Simpleks, pola soal yang dibahas yaitu kasus maksimasi. Bagaimana jikalau masalahnya yaitu kasus minimasi?
Metode minimasi biasanya dipakai untuk mencari biaya minimum dalam suatu produksi perusahaan, sehingga didapatkan biaya terendah untuk memproduksi suatu produk atau jasa.
Untuk metode pemecahannya, kita sanggup mengubah fungsi tujuan minimasi menjadi fungsi maksimasi dengan mengalikan fungsi tujuan minimasi tersebut dengan -1, alasannya yaitu 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 sanggup juga memodifikasi langkah ke 3 simpleks pada pola diatas, yaitu menentukan 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 dipakai sebagai solusi basis awal, sehingga ruas kanan persamaan berharga positif. Berikut ini dibahas cara mengatasi penyimpangan-penyimpangan dari bentuk normal diatas supaya sanggup diselesaikan dengan metode simpleks. Penyimpangan tersebut sanggup berupa tanda sama dengan (=), hambatan bertanda lebih besar sama dengan (≥), atau ruas kanan bernilai negatif.
Contoh :
Minimumkan : 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 hambatan yang pertama, untuk mengubah menjadi persamaan harus ditambah variabel slack, yang sekaligus dipakai sebagai basis pada tabel awal simpleks. Persamaan tersebut menjadi :
4 X1 + 6 X2 + S1 = 36. - Pada fungsi hambatan yang kedua sudah dalam bentuk persamaan, alasannya yaitu belum ada variabel yang merupakan basis pada tabel awal, maka perlu ada variabel dummy (variabel buatan) yang disebut variabel artificial (lambang "R"). Dinamakan artificial alasannya yaitu tidak mempunyai arti nyata, artinya iterasi-iterasi metode simpleks akan secara otomatis menyebabkan variabel artificial tidak muncul lagi (bernilai nol) yaitu apabila problem semula yang telah terselesaikan. Dengan kata lain variabel artificial ini dipakai hanya untuk memulai solusi dan harus menghilangkannya pada final 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 kesudahannya menjadi tanda "=" supaya sanggup diselesaikan dengan metode simpleks. Persamaan tersebut dikalikan (-1) akan menjadi : -8 X1 - 4 X2 ≤ -32. Kemudian, ubah ke tanda sama dengan ibarat yang telah dibahas diatas maka menjadi : -8 X1 - 4 X2 + S2 = -32. Karena bab kanan persamaan ini bertanda negatif (-32), maka harus menjadi
8 X1 + 4 X2 - S2 = 32, tetapi alasannya yaitu S1 bertanda negatif, hal ini tidak memungkinkan dalam metode simpleks alasannya yaitu tidak sanggup dipakai 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 pembahasan mengenai variabel slack dan variabel artificial berkaitan dengan metode simpleks sanggup disimpulkan bahwa :
- Apabila fungsi hambatan bertanda ≤, maka tambahkan variabel slack.
- Apabila fungsi hambatan bertanda =, maka tambahkan variabel artificial R.
- Apabila fungsi hambatan bertanda ≥, maka kurangi dengan variabel slack dan tambahkan variabel artificial R.
- Apabila fungsi hambatan yaitu 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 yaitu :
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, R2 | ≥ | 0 | |||||
Penyelesaian problem yang mengandung variabel artificial ini sanggup 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 berdasarkan pola diatas menjadi :
Minimumkan : 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, R2 | ≥ | 0 | |||||
Untuk memasukkan model matematis problem diatas dalam tabel simpleks, maka terlebih dahulu melaksanakan subtitusi nilai R1 dan R2 pada persamaan hambatan 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 dimasukkan ke dalam 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
Berdasarkan persamaan terakhir ini maka dilakukan penyelesaian dengan metode simpleks ibarat cara penyelesaian yang sudah diuraikan pada bab sebelumnya wacana : pemecahan agenda linear metode simpleks.
Iterasi awal sampai iterasi final optimal penyelesaian problem diatas sanggup dilihat pada tabel berikut :
| Iterasi | Basis | Z | X1 | X2 | S1 | R1 | S2 | R2 | Solusi |
|---|---|---|---|---|---|---|---|---|---|
| 0 | Z | 1 | (15M - 7) | (9M -3) | 0 | 0 | -M | 0 | 67M |
| S1 | 0 | 4 | 6 | 1 | 0 | 0 | 0 | 36 | |
| R1 | 0 | 7 | 5 | 0 | 1 | 0 | 0 | 35 | |
| R2 | 0 | 8 | 4 | 0 | 0 | -1 | 1 | 32 |
| Iterasi | Basis | Z | X1 | X2 | S1 | R1 | S2 | R2 | Solusi |
|---|---|---|---|---|---|---|---|---|---|
| 1 | Z | 1 | 0 | (3M + 1)/2 | 0 | 0 | (7M - 7)/8 | -(15M - 7)/8 | 7M + 28 |
| S1 | 0 | 0 | 4 | 1 | 0 | 1/2 | -1/2 | 20 | |
| R1 | 0 | 0 | 3/2 | 0 | 1 | 7/8 | -7/8 | 7 | |
| X1 | 0 | 1 | 1/2 | 0 | 0 | -1/8 | 1/8 | 4 |
| Iterasi | Basis | Z | X1 | X2 | S1 | R1 | S2 | R2 | Solusi |
|---|---|---|---|---|---|---|---|---|---|
| 2 | Z | 1 | 0 | 0 | 0 | -M - 1/3 | -7/6 | -M + 7/6 | 77/3 |
| S1 | 0 | 0 | 0 | 1 | -8/3 | -11/6 | 11/6 | 4/3 | |
| X2 | 0 | 0 | 1 | 0 | 2/3 | 7/12 | -7/12 | 14/3 | |
| X1 | 0 | 1 | 0 | 0 | -1/3 | -5/12 | 5/12 | 5/3 |
Dari iterasi ke-2 pada tabel diatas merupakan tabel 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 :
- Fase pertama :
Pada fase ini tujuan semula diganti dengan meminimumkan jumlah variabel artificialnya, dan diuji apakah problem yang dihadapi mempunyai solusi feasibel atau tidak. Jika nilai minimum fungsi tujuan gres (r) ini berharga nol (seluruh variabel artificial berharga nol), berarti problem mempunyai solusi feasibel, yang berarti pengerjaan sanggup dilanjutkan ke fase 2. Tetapi jikalau minimum fungsi tujuan gres ini berharga positif, maka problem tidak mempunyai solusi feasible. Berarti stop!. - Fase kedua :
Gunakan solusi basis optimum pada fase 1 sebagai solusi awal bagi problem sebenarnya. Dalam hal ini ubahlah bentuk fungsi tujuan pada fase 1 dengan mengembalikannya pada fungsi tujuan problem sesungguhnya dan fungsi batasan diperoleh dari tabel optimal fase 1 tanpa memasukkan variabel R nya.
Contoh :
Minimumkan : 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 :
Minimumkan : 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, R2 | ≥ | 0 | |||||
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 hambatan 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, R2 | ≥ | 0 | |||||
Setelah itu lakukan persamaan simpleks dengan r sebagai fungsi tujuan gres menggantikan Z. Masukkanlah persamaan fungsi tujuan gres r tersebut dengan fungsi tujuan minimasi serta persamaan kendalanya dimasukkan dalam tabel simpleks sebagai berikut:
| Iterasi | Basis | r | X1 | X2 | S1 | R1 | S2 | R2 | Solusi |
|---|---|---|---|---|---|---|---|---|---|
| 0 | r | 1 | 15 | 9 | 0 | 0 | -1 | 0 | 67 |
| S1 | 0 | 4 | 6 | 1 | 0 | 0 | 0 | 36 | |
| R1 | 0 | 7 | 5 | 0 | 1 | 0 | 0 | 35 | |
| R2 | 0 | 8 | 4 | 0 | 0 | -1 | 1 | 32 |
| Iterasi | Basis | r | X1 | X2 | S1 | R1 | S2 | R2 | Solusi |
|---|---|---|---|---|---|---|---|---|---|
| 1 | r | 1 | 0 | 3/2 | 0 | 0 | 7/8 | -15/8 | 7 |
| S1 | 0 | 0 | 4 | 1 | 0 | 1/2 | -1/2 | 20 | |
| R1 | 0 | 0 | 3/2 | 0 | 1 | 7/8 | -7/8 | 7 | |
| X1 | 0 | 1 | 1/2 | 0 | 0 | -1/8 | 1/8 | 4 |
| Iterasi | Basis | r | X1 | X2 | S1 | R1 | S2 | R2 | Solusi |
|---|---|---|---|---|---|---|---|---|---|
| 2 | r | 1 | 0 | 0 | 0 | -1 | -7/6 | -1 | 0 |
| S1 | 0 | 0 | 0 | 1 | -8/3 | -11/6 | 11/6 | 4/3 | |
| X2 | 0 | 0 | 1 | 0 | 2/3 | 7/12 | -7/12 | 14/3 | |
| X1 | 0 | 1 | 0 | 0 | -1/3 | -5/12 | 5/12 | 5/3 |
Pada iterasi ke-2 terlihat baris r sudah negatif semua dan r bernilai nol, maka problem diatas mempunyai solusi feasibel. Selanjutnya dilanjutkan ke fase 2, tetapi R tidak diikutsertakan lagi.
Fase 2 :
Berdasarkan tabel optimal fase 1 diatas, sanggup 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
Berdasarkan model problem 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 hambatan :
| S1 | - 11/6 S2 | = | 4/3 | ||
| X2 | + 7/12 S2 | = | 14/3 | ||
| X1 | - 5/12 S2 | = | 5/3 | ||
| X1, X2, S1, S2 | ≥ | 0 | |||
Tabel Simpleks fase 2 dengan fungsi tujuan minimasi sebagai berikut :
| Basis | Z | X1 | X2 | S1 | S2 | Solusi |
|---|---|---|---|---|---|---|
| Z | 1 | 0 | 0 | 0 | -7/6 | 77/3 |
| S1 | 0 | 0 | 0 | 1 | -11/6 | 4/3 |
| X2 | 0 | 0 | 1 | 0 | 7/12 | 14/3 |
| X1 | 0 | 1 | 0 | 0 | -5/12 | 5/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 kasus minimasi simpleks ini juga sanggup diselesaikan dengan memakai software komputer ibarat TORA yang sanggup memecahkan agenda linear. Selain untuk agenda linear TORA juga sanggup dimanfaatkan untuk menuntaskan jenis persamaan lainya ibarat transportasi dan yang lainya.
Perlu anda ketahui sebelum mengakhiri bahan simpleks ini, ada beberapa kasus khusus dalam penggunaan simpleks ibarat degenerasi, solusi optimum banyak, solusi tak terbatas, dan tidak ada solusi layak. Untuk lebih jelasnya akan dibahas pada topik berikutnya wacana :
Sumber http://www.dounkey.com