Metode simpleks yaitu salah satu teknik pemecahan aktivitas linear selain metode grafik, Bedanya dengan metode grafik, metode simpleks sanggup dimanfaatkan untuk persamaan yang mempunyai variabel lebih dari 2 sedangkan grafik tidak.
Sama ibarat metode grafik, dibutuhkan juga formulasi aktivitas linear semoga sanggup dipecahkan dengan metode grafiknya. Untuk lebih terperinci perihal metode grafik dan aktivitas linear sanggup dilihat pada :
Sebelum masuk ke cara pemecahan aktivitas linear dengan metode simpleks, perlu anda ketahui sebelumnya perihal bentuk standar model aktivitas linear.
Bentuk Standar Model Program Linear
Seperti yang sudah diuraikan pada artikel sebelumnya pada aktivitas linear, bahwa model aktivitas linear sanggup mempunyai pembatas-pembatas yang bertanda ≤, ≥, dan =. Demikian juga variabel-variabelnya yang sanggup berupa variabel non-negatif, sanggup pula berupa variabel-variabel yang tidak terbatas dalam tanda.
Dalam penyelesaian aktivitas linear dengan metode simpleks, bentuk dasar yang dipakai haruslah bentuk standar. Formulasi bentuk standar mempunyai sifat-sifat sebagai berikut:
- Fungsi tujuannya sanggup berupa maksimasi atau minimasi.
- Seluruh pembatas sudah dalam bentuk persamaan (tanda = ) dengan ruas kanan persamaan yang non-negatif.
- Seluruh variabelnya harus merupakan variabel non-negatif.
Untuk mengubah suatu bentuk formulasi yang belum standar ke dalam bentuk standar sanggup dilakukan dengan cara berikut:
1. Pembatas
- Pembatas yang bertanda ≤ atau ≥ sanggup dijadikan suatu persamaan (tanda = ) dengan menambahkan suatu variabel slack (S) atau mengurangkan dengan suatu variabel surplus (S)
- Contoh 1: X1 + X2 ≤ 8
- Contoh 2: X1 + 2 X2 ≥ 5
- Ruas kanan dari suatu persamaan sanggup dijadikan bilangan non-negatif dengan mengalikan kedua ruas dengan -1.
- Contoh : X1 - 5 X2 = -7, secara matematis yaitu sama dengan persamaan -X1 + 5 X2 = 7.
- Arah ketidaksamaan sanggup berubah apabila kedua ruas dikalikan -1.
- Contoh : X1 - X2 ≤ -8, yaitu sama dengan -X1 + X2 ≥ 8.
Kita tambahkan slack S1 pada ruas kiri persamaan tersebut sehingga diperoleh persamaan: X1 + X2 + S1 = 8
Variabel slack menawarkan banyaknya sumber daya yang tidak terpakai.
Karena bertanda ≥ maka harus dikurangi dengan variabel S2 pada ruas kiri persamaan sehingga diperoleh persamaan: X1 + 2X2 -S2 = 5
Variabel surplus menawarkan kelebihan pemakaian sumber daya.
2. Variabel
Suatu variabel Xi yang tidak terbatas oleh tanda sanggup dinyatakan sebagai dua variabel non-negatif dengan memakai substitusi: Xi = Xi' - Xi" dimana Xi' dan Xi" ≥ 0. Substitusi ibarat ini harus dilakukan pada seluruh pembatas dan fungsi tujuannya.
3. Fungsi tujuan
Maksimasi dari sebuah fungsi yaitu sama dengan minimasi dari negatif fungsi yang sama.
Contoh : Maksimumkan Z = X1 + 2 X2 secara matematis sama dengan : Minimumkan (-Z) = -X1 - 2 X2.
Metode Simpleks
Pada topik sebelumnya perihal metode grafik, sudah dijelaskan pemecahan aktivitas linear yang dipakai untuk menuntaskan masalah 2 variabel. Untuk menuntaskan masalah aktivitas linear berdimensi lebih besar dari 2 dikenal metode yang lazim disebut metode simpleks.
Metode simpleks dikembangkan pertama kali oleh George dantzing pada tahun 1947, sifat dari metode ini yaitu iterative, dimana penyelesaian masalah melalui tahapan perhitungan yang berulang-ulang hingga tercapai solusi optimum.
Untuk lebih jelasnya sanggup dilihat dari tumpuan soal dibawah:
Contoh Metode Simpleks
Maksimumkan : Z = 15 X1 + 18 X2 + 12 X3
Kendala :
10 X1 + 12 X2 + 8 X3 ≤ 120
18 X1 + 15 X2 + 6 X3 ≤ 135
12 X1 + 16 X2 + 6 X3 ≤ 150
X1, X2, X3 ≥ 0
Langkah 1 : Mengubah fungsi tujuan dan fungsi kendala
Fungsi tujuan diubah menjadi bentuk implisit dengan jalan menggeser fungsi tujuan ke Z, yaitu Z = 15 X1 + 18 X2 + 12X3 diubah menjadi Z - 15 X1 - 18 X2 - 12X3 = 0.
Sedangkan fungsi hambatan (selain hambatan non-negatif) diubah menjadi bentuk persamaan dengan menambahkan variabel slack, yaitu suatu variabel yang mewakili tingkat pengangguran kapasitas yang merupakan batasan.
Fungsi hambatan pada soal tersebut diatas menjelma :
| 10 X1 + | 12 X2 + | 8 X3 + | S1 | = | 120 | ||
| 18 X1 + | 15 X2 + | 6 X3 | + S2 | = | 135 | ||
| 12 X1 + | 16 X2 + | 6 X3 | + S3 | = | 150 | ||
| X1, X2, X3, S1, S2, S3 | ≥ | 0 | |||||
Langkah 2 : Mentabulasikan persamaan-persamaan fungsi tujuan dan hambatan yang telah diubah ibarat pada langkah 1 diatas.
| Basis | Z | X1 | X2 | X3 | S1 | S2 | S3 | Solusi |
|---|---|---|---|---|---|---|---|---|
| Z | 1 | -15 | -18 | -12 | 0 | 0 | 0 | 0 |
| S1 | 0 | 10 | 12 | 8 | 1 | 0 | 0 | 120 |
| S2 | 0 | 18 | 15 | 6 | 0 | 1 | 0 | 135 |
| S3 | 0 | 12 | 16 | 6 | 0 | 0 | 1 | 150 |
Kolom basis menawarkan variabel yang sedang menjadi basis yaitu S1, S2, S3 yang nilainya ditunjukkan oleh kolom solusi. Secara tidak pribadi ini menawarkan bahwa variabel non-basis X1, X2, X3 (yang tidak masuk pada kolom basis) sama dengan nol.
Hal ini sanggup dimengerti, alasannya belum ada kegiatan/produksi X1, X2, X3 masing-masing nilainya nol yang berarti juga kapasitas masih menganggur yang ditunjukkan oleh nilai S1, S2, S3.
Langkah 3 : Menentukan kolom pivot
Setelah kita mentabulasikan persamaan menjadi bentuk tabel simpleks, langkah selanjutnya yaitu menentukan kolom pivot. Kolom pivot (entering variabel) dipilih dari baris Z dengan angka negatif terbesar untuk masalah maksimasi. Kaprikornus sesuai soal diatas didapatkan bahwa kolom pivotnya yaitu X2.
Sehingga jikalau digambarkan dalam tabel menjadi :
| Basis | Z | X1 | X2 | X3 | S1 | S2 | S3 | Solusi |
|---|---|---|---|---|---|---|---|---|
| Z | 1 | -15 | -18 | -12 | 0 | 0 | 0 | 0 |
| S1 | 0 | 10 | 12 | 8 | 1 | 0 | 0 | 120 |
| S2 | 0 | 18 | 15 | 6 | 0 | 1 | 0 | 135 |
| S3 | 0 | 12 | 16 | 6 | 0 | 0 | 1 | 150 |
Pada tabel diatas kolom X2 yaitu kolom yang dipilih alasannya mempunyai nilai -18 (nilai negatif terbesar).
Langkah 4 : Menentukan baris pivot
Setelah kita mendapat kolom pivot, langkah selanjutnya yaitu menentukan baris pivot (leaving variabel). Untuk mengetahui baris mana yang pilih sanggup dilakukan dengan membagi solusi dengan kolom pivot pada setiap baris.
Setelah itu dipilihlah angka dengan rasio terkecil, namun jikalau terdapat angka negatif dan tidak hingga kolom pivot maka tidak masuk dalam perhitungan rasio, jadi jikalau terdapat angka negatif atau tak hingga maka diberi tanda strip pada kolom rasio. Setelah mendapat rasio maka kita harus memindahkan variabel pada kolom pivot ke baris pivot.
Sehingga menurut soal diatas menjadi :
| Basis | Z | X1 | X2 | X3 | S1 | S2 | S3 | Solusi | Rasio |
|---|---|---|---|---|---|---|---|---|---|
| Z | 1 | -15 | -18 | -12 | 0 | 0 | 0 | 0 | - |
| S1 | 0 | 10 | 12 | 8 | 1 | 0 | 0 | 120 | 10 |
| X2 | 0 | 18 | 15 | 6 | 0 | 1 | 0 | 135 | 9 |
| S3 | 0 | 12 | 16 | 6 | 0 | 0 | 1 | 150 | 9.375 |
Langkah 5 : Menentukan persamaan pivot baru
Rumus untuk menentukan persamaan pivot gres yaitu = baris pivot lama/elemen pivot. Elemen pivot yaitu perpotongan antara kolom dan baris pivot. Kaprikornus setiap baris pivot yang telah ditentukan dibagi dengan elemen pivot sehingga dihasilkan persamaan pivot baru.
Sehingga dari menurut soal diatas menjadi :
| Basis | Z | X1 | X2 | X3 | S1 | S2 | S3 | Solusi |
|---|---|---|---|---|---|---|---|---|
| Z | 1 | |||||||
| S1 | 0 | |||||||
| X2 | 0 | 18/15 | 1 | 6/15 | 0 | 1/15 | 0 | 9 |
| S3 | 0 |
Berdasarkan tabel diatas semua baris pivot dibagi dengan elemen pivot yaitu 15. Sehingga dihasilkan persamaan pivot yang baru.
Langkah 6 : Menentukan persamaan gres selain persamaan pivot baru
Setelah mendapat persamaan pivot baru, langkah selanjutnya yaitu mengisi persamaan lainya yang masih kosong. Rumus untuk menentukan persamaan gres selain persamaan pivot gres yaitu sebagai berikut :
Persamaan gres = (persamaan lama) - (persamaan pivot gres x koefisien kolom pivot)
Kaprikornus persamaan gres yang dicari dari duduk kasus diatas yaitu persamaan gres untuk basis Z, S1, dan S3. Sedangkan S2 sudah diganti oleh persamaan pivot gres X2.
Persamaan Z gres :
(-15) - (18/15 x -18) = 33/5
(-18) - (1 x -18) = 0
(-12) - (6/15 x -18) = -24/5
(0) - (0 x -18) = 0
(0) - (1/15 x -18) = 6/5
(0) - (0 x -18) = 0
(0) - (9 x -18) = 162
Persamaan S1 gres :
(10) - (18/15 x 12) = -22/5
(12) - (1 x 12) = 0
(8) - (6/15 x 12) = 16/5
(1) - (0 x 12) = 1
(0) - (1/15 x 12) = -4/5
(0) - (0 x 12) = 0
(120) - (9 x 12) = 12
Persamaan S3 gres :
(12) - (18/15 x 16) = -36/5
(16) - (1 x 16) = 0
(6) - (6/15 x 16) = -2/5
(0) - (0 x 16) = 0
(0) - (1/15 x 16) = -16/5
(1) - (0 x 16) = 1
(150) - (9 x 16) = 6
Persamaan pivot baru, Z baru, S1 baru, dan persamaan S3 gres yang sudah dicari nilainya kemudian ditabulasikan dalam tabel simpleks gres sebagai berikut :
| Basis | Z | X1 | X2 | X3 | S1 | S2 | S3 | Solusi |
|---|---|---|---|---|---|---|---|---|
| Z | 1 | 33/5 | 0 | -24/5 | 0 | 6/5 | 0 | 162 |
| S1 | 0 | -22/5 | 0 | 16/5 | 1 | -4/5 | 0 | 12 |
| X2 | 0 | 18/15 | 1 | 6/15 | 0 | 1/15 | 0 | 9 |
| S3 | 0 | -36/5 | 0 | -2/5 | 0 | -16/5 | 1 | 6 |
Langkah 7 : Lanjutkan perbaikan-perbaikan
Periksa kembali tabel simpleks anda, apakah pada baris Z angkanya sudah positif semua (≥ 0) untuk kasus maksimasi, jikalau sudah positif semua berarti solusi optimal sudah didapatkan.
Terlihat pada langkah 6 diatas baris Z masih ada yang negatif yaitu kolom X3. Maka perlu dilakukan perbaikan untuk mencapai nilai optimal.
Maka dari itu dibutuhkan perbaikan. Dalam perbaikan anda hanya perlu mengulangi kembali dari langkah 3 dari tabel yang sudah anda hitung. Lakukan secara terus menerus hingga baris Z bernilai positif semua.
Setelah dilakukan perbaikan, maka tabel optimal dari tumpuan diatas akan didapatkan sebagai berikut :
| Basis | Z | X1 | X2 | X3 | S1 | S2 | S3 | Solusi |
|---|---|---|---|---|---|---|---|---|
| Z | 1 | 0 | 0 | 0 | 3/2 | 0 | 0 | 180 |
| S1 | 0 | -11/8 | 0 | 1 | 5/16 | -1/4 | 0 | 15/4 |
| X2 | 0 | 7/4 | 1 | 0 | -1/8 | 1/6 | 0 | 15/2 |
| S3 | 0 | -31/4 | 0 | 0 | 1/8 | -7/6 | 1 | 15/2 |
Berdasarkan tabel hasil perbaikan diatas sanggup disimpulkan bahwa hasil iterasi ini telah mencapai kondisi optimal, alasannya nilai pada baris fungsi tujuan Z sudah tidak ada yang negatif.
Sehingga dari duduk kasus diatas untuk kasus maksimasi ini didapatkan nilai :
Z = 180,
X1 = 0 (tidak diproduksi),
X2 = 15/2,
X3 =15/4,
S3 = 15/2 (merupakan kapasitas yang menganggur dari batasan ke 3).
Pada soal berikut, sudah diketahui persamaan-persamaan yang ada. Tetapi, perlu anda ketahui, bentuk soal aktivitas linear ada juga yang berbentuk soal cerita, sehingga anda perlu melaksanakan formulasi terlebih dahulu untuk mendapat bentuk persamaan ibarat di atas. Untuk lebih terperinci perihal formulasi aktivitas linear sanggup dilihat pada : Formulasi dan Bentuk Umum Program Linear
Untuk masalah minimasi dibahas pada topik berikutnya di : Masalah minimasi metode simpleks
Menghitung Simpleks Dengan Mudah
Bagi anda yang malas untuk memakai metode simpleks, kini ini sudah ada software yang sanggup anda gunakan untuk menuntaskan persamaan simpleks dengan mudah.
Kaprikornus kita hanya perlu menentukan fungsi tujuan dan kendala, sesudah itu masukkan fungsi-fungsi tersebut ke aktivitas untuk diproses, maka secara otomatis anda sanggup mengetahui langkah-langkah penyelesaian dan hasil dari solusi optimalnya.
Nama salah satu dari software yang cukup populer untuk menuntaskan masalah simpleks yaitu TORA. Selain untuk masalah simpleks, TORA juga sanggup dipakai untuk menuntaskan aktivitas program lainya yang berkaitan dengan riset operasi ibarat transportasi, dan lain sebagainya.
Bahkan kini anda juga sudah sanggup memecahkan masalah simpleks pribadi di web dengan mudahnya. Ada 2 website yang biasa saya gunakan untuk memecahkan masalah simpleks ini yaitu :
Sumber http://www.dounkey.com