blognya komarudin bin sayuti

blognya komarudin bin sayuti header image 2

Teknik Big-M dan teknik Two-phase dalam algoritma simplex

April 1st, 2012 · No Comments

Pada postingan sebelumnya, kita telah membahas secara singkat tentang algoritma simplex. Akan tetapi, ketika fase initialization, kita mengasumsikan bahwa nilai solusi feasible dapat dicapai dengan mudah. Hal ini tidak berlaku umum. Terkadang kita membutuhkan beberapa iterasi tambahan di awal sebagai langkah mendapatkan solusi awal feasible.

Setidaknya ada dua teknik yang dapat kita gunakan untuk mendapatkan solusi awal feasible dalam algoritma simplex, yakni:

  • Metode Big-M
  • Metode dua fase (two-phase)

Akan tetapi, sebelum kita membahas lebih jauh tentang kedua teknik di atas, saya ingin sedikit mengulas tentang cara mengubah kendala simplex sehingga menjadi kendala yang standar. Selain itu, saya ingin menjelaskan tentang variabel-variabel tambahan yang diperlukan dalam simplex. Perhatikan tabel berikut ini:

\(\)
No Kendala awal Hasil transformasi Jenis variable tambahan
1 $$-x_ {1} + 2x_ {3}\leq 5$$ $$-x_{1} + 2x_{3}+S_{1}= 5$$ \(S_1\) : variable slack
2 $$3x_{1}-7x_ {3}\geq 8$$ $$3x_{1}-7x_{3}-S_{2}+S_{3}= 8$$ \(S_2\) : variable surplus

\(S_3\) : variable artificial

3 $$x_ {1} + 4x_{3}= 9$$ $$x_{1} + 4x_{3}+S_{4} =9 $$ \(S_4\) : variable artificial

 

Dalam programa linear, ada tiga pertidaksamaan yang diijinkan, yakni \(\leq\), \(\geq\) dan \(=\). Hal ini sebagaimana ditunjukkan pada tiga baris pada tabel di atas. Tiga keadaan ini akan kita bahas satu-persatu. Sebelumnya perlu diingat bahwa setiap variabel (baik asli maupun tambahan) memiliki kendala implisit \(\geq 0 \).

  • Keadaan  \(\leq\). Ruas kiri pertidaksamaan bernilai kurang dari ruas kanan. Sehingga kita perlu menambahkan bagian ruas kiri sehingga sama dengan ruas kanan. Untuk itu, kita perkenalkan variabel  \(S_1\). Variabel ini disebut variabel slack karena ia merupakan kekurangan dari ruas kiri supaya sama dengan ruas kanan. Bagian ruas kiri akan ditambah (bukan dikurang)  \(S_1\) karena variabel  \(S_1\) memiliki kendala implisit non-negative   (\(\geq 0\)).
  • Keadaan \(\geq\). Ruas kiri pertidaksamaan bernilai lebih dari ruas kanan. Sehingga kita perlu mengurangkan bagian ruas kiri sehingga sama dengan ruas kanan.  Untuk itu, kita perkenalkan variabel  \(S_2\). Variabel ini disebut variabel surplus karena ia merupakan kelebihan dari ruas kiri supaya sama dengan ruas kanan. Akan tetapi, sayangnya kita memerlukan suatu variabel yang memiliki koefisien positif 1 untuk memperoleh solusi awal yang feasibel. Oleh sebab itu, kita perlu memperkenalkan variabel \(S_3\) dengan koefisien +1. Karena variabel ini adalah variabel buatan, maka ia disebut variabel artifical.
  • Keadaaan \(=\). Keadaan ini sudah dalam bentuk persamaan. Akan tetapi, karena kita perlu variabel yang memiliki koefisien +1, diperkenalkanlah variabel \(S_4\) sebagai variabel artificial. Terkadang, ada penulis yang menambahkan variable \(S_5\) agar kendala ini tetap seimbang [1].

Koefisien +1 sebagaimana dijelaskan di atas diperlukan karena kita perlu mendapatkan matriks identitas sebagai basic variable dalam solusi awal. Nilai variabel-variabel lain kita set menjadi nol sehingga persamaan matriks menjadi terpenuhi. Perhatikan contoh tadi yg kita tulis ulang dalam bentuk matriks:

kita tulis ulang sebagai perkalian dua matriks:

kita tukar posisi kolom \(S_1\) dan \(S_2\) menjadi:

terlihat ada matriks identitas 3×3 dan variabel \(S_1\), \(S_3\) dan \(S_4\) menjadi basic variable sebagai solusi awal dengan nilai masing masing \((5, 8, 9)\) sedangkan variabel lain bernilai nol. Dengan demikian solusi awal ini memenuhi persamaan sebelumnya.

Selanjutnya, kita perlu mencermati apa implikasi notasi \(\leq\), \(\geq\) dan \(=\) dan masuknya beberapa variabel tambahan terhadap fungsi objective. Implikasi ini memiliki kaitan erat dengan dua teknik yang kita sebutkan di awal. Without a loss of generality, kita asumsikan permasalahan kita adalah permasalah maksimasi (maximization). Implikasinya adalah:

  • Pada keadaan  \(\leq\),  \(S_1\) hanya perlu bernilai nonnegative supaya kendala pertama terpenuhi. Karena tiap variabel memiliki kendala implisit nonnegative, maka keadaan  \(\leq\) tidak memiliki implikasi terhadap objective function.
  • Pada keadaan  \(\geq\),  \(S_2\) juga hanya perlu bernilai nonnegative supaya kendala kedua terpenuhi sehingga variabel ini tidak memiliki implikasi terhadap objective function. Lain halnya dengan variabel \(S_3\). Variabel ini harus bernilai nol supaya kendala kedua dapat terpenuhi. Sehingga, variabel  \(S_3\) diikutkan ke dalam objective function dengan koefisien bernilai negatif. Nilai negative diperlukan agar memaksimumkan objective function dapat dicapai dengan meminimumkan variabel ini.
  • Pada keadaan \(=\), variabel \(S_4\) harus bernilai nol agar kendala ketiga dapat terpenuhi. Sehingga variabel  \(S_4\) juga diikutkan ke dalam objective function dengan koefisien bernilai negatif.

Nah, kedua teknik yang disebutkan di awal, sebenarnya ditujukan untuk menghilangkan variabel-variabel artificial dalam permasalahan linear programming. Penjelasan kedua teknik tersebut adalah sebagai berikut:

1. Teknik Big-M

Teknik ini memberikan nilai koefisien yang sangat besar kepada variabel-variabel artifisial dalam persamaan objective function. Nilai koefisien ini bertindak sebagai penalty dan disebut Big-M. Nilai ini perlu sangat besar agar algoritma simpleks berusaha memprioritaskan menangani variabel artifisial ini terlebih dahulu. Setelah nilai artifisial ini bernilai nol, maka suatu solusi feasible sudah tercapai dan variabel artifisial dapat dibuang dari tabel simpleks.

Sebagai contoh apabila objective function yang asli sebagai berikut:

$$max\; 2x_1+9x_2$$

maka persamaan tersebut diubah menjadi:

$$max\; 2x_1+9x_2-MS_3-MS_4$$

Keuntungan dari metode ini adalah algoritma simplex dapat dilanjutkan sebagaimana metode simpleks yang biasa. Akan tetapi, penggunaan angka yang sangat besar dapat mengakibatkan iterasi simplex yang tidak stabil karena galat pembulatan.

2. Teknik two-phase (dua fase)

Sebagaimana namanya, teknik ini memiliki dua fase. Fase pertama bertindak untuk menghilangkan variabel artifisial, sedangkan fase kedua bertindak meneruskan algoritma simpleks sebagaimana biasa bilamana suatu solusi feasible dapat dicapai pada fase pertama.

Fase pertama dijalankan dengan meng-assign sebuah angka arbitrary (misal 1) sebagai koefisien objective function dari setiap variabel artifisial. Koefisien untuk variabel-variabel lain kita set menjadi nol pada fase ini. Kemudian algoritma simplex dieksekusi sebagaimana biasa. Fase pertama dikatakan mencapai nilai solusi feasible apabila objective function bernilai nol dan variabel artifisial menjadi variabel non basic dan nilainya nol. Jika fase pertama berhasil, maka algoritma simplex dilanjutkan dengan fase kedua. Pada fase kedua, koefisien untuk variabel selain variabel artifisial dikembalikan ke dalam objective function. Selain itu, variabel artifisial dapat dibuang dalam iterasi simplex berikutnya.

Dengan menggunakan contoh sebelumnya, fase pertama dieksekusi dengan objective function sebagai berikut:

$$max\; 0x_1+0x_2-S_3-S_4$$

sedangkan pada fase kedua, objective function dikembalikan ke awal sbb:

$$max\; 2x_1+9x_2$$

 

olkGUI.version.0.4.1

Panduan pengguna OLK GUI ver.0.4.1

Untuk mencoba dan mempelajari kedua teknik tersebut, kami menyertakan sebuah software yang menerapkan kedua teknik tersebut dalam C++:

 

 

[1] kita bisa mencermati bahwa koefisien variabel \(x_1\) memiliki nilai +1. Sehingga variabel ini bisa langsung menjadi kandidat sebagai variabel basic. Akan tetapi, agar lebih general, saya memilih untuk menambahkan \(S_4\).

Print Friendly, PDF & Email

Tags: Linear Programming · Mathematical programming · Optimization