Metode simpleks: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
Konten dalam edit ini adalah alih bahasa dari artikel Wikipedia Bahasa Inggris en:Simplex_algorithm (oldid 1045092279); Lihat sejarahnya untuk atribusi. |
Konten dalam edit ini adalah alih bahasa dari artikel Wikipedia Bahasa Inggris en:Simplex_algorithm (oldid 1045092279); Lihat sejarahnya untuk atribusi. |
||
Baris 9:
== Gambaran umum ==
{{further|Program linear}}
[[Berkas:Simplex-description-en.svg|jmpl|240x240px|
Algoritma simpleks bekerja pada program linear dalam bentuk kanonik (baku):
Baris 20:
Solusi dari program linear dikerjakan dalam dua tahap. Pada Tahap I, sebuah titik ekstrem ditentukan. Tergantung dari program yang dikerjakan, hal ini dapat dilakukan secara trivial, atau dengan menerapkan algoritma simpleks ke suatu modifikasi dari program semula. Tahap ini dapat menghasilkan sebuah solusi feasibel sederhana, atau tidak sama sekali (karena daerah feasibel kosong). Untuk kasus kedua, program linear dikatakan ''tidak feasibel''. Selanjutnya pada Tahap II, algoritma simpleks diterapkan pada solusi feasibel sederhana yang didapat pada Tahap I sebagai titik mulai pengerjaan. Hasil dari Tahap II adalah sebuah solusi feasibel yang optimal, atau sebuah rusuk dengan panjang terbatas (yang menyebabkan fungsi tidak terbatas dari atas).<ref name="DantzigThapa12">[[George B. Dantzig]] and Mukund N. Thapa. 1997. ''Linear programming 1: Introduction''. Springer-Verlag.</ref><ref>{{Cite book|last=D. Nering|first=Evar|last2=W. Tucker|first2=Albert|date=1993|title=Linear Programs and Related Problems|publisher=Academic Press|url-status=live}}</ref><ref name="Vanderbei2">Robert J. Vanderbei, [http://www.princeton.edu/~rvdb/LPbook/ ''Linear Programming: Foundations and Extensions''], 3rd ed., International Series in Operations Research & Management Science, Vol. 114, Springer Verlag, 2008. {{isbn|978-0-387-74387-5}}. <!-- (Edisi kedua yang daring masih tersedia. Situs milik Vanderbei masih menyimpan koleksi materi yang mendalam.) --></ref>
== Bentuk baku ==
Sebuah program linear dapat diubah ke dalam bentuk baku dengan cara sebagai berikut:<ref>{{harvtxt|Murty|1983|loc=Section 2.2}}</ref> Pertama, untuk setiap variabel dengan nilai batas bawah yang berbeda dengan 0, sebuah variabel baru didefinisikan untuk merepresentasikan perbedaan antara variabel asal dengan batas bawahnya. Variabel asal selanjutnya dapat dihilangkan dengan melakukan subtitusi. Sebagai contoh, misalkan ada kendala
: <math>x_1 \ge 5</math>
Sebuah variabel baru, <math>y_1</math>, didefinisikan sebagai
: <math> \begin{align} y_1 = x_1 - 5\\x_1 = y_1 + 5 \end{align}</math>
Persamaan kedua dapat digunakan untuk menghilangkan semua kemunculan <math>x_1</math> di program linear yang dikerjakan. Dengan cara ini, semua batas bawah dari kendala-kendala dapat diubah agar bernilai nonnegatif.
Kedua, untuk setiap kendala dalam bentuk pertidaksamaan yang tersisa, sebuah variabel baru yang disebut variabel lempai (''slack''), didefinisikan untuk mengubah pertidaksamaan tersebut menjadi sebuah persamaan. Variabel ini merepresentasikan perbedaan antara kedua sisi pertidaksamaan, dan diasumsikan bernilai nonnegatif. Sebagai contoh, dua pertidaksamaan berikut
: <math> \begin{align}
x_2 + 2x_3 &\le 3\\
-x_4 + 3x_5 &\ge 2
\end{align}</math>
diubah bentuknya menjadi
: <math> \begin{align}
x_2 + 2x_3 + s_1 &= 3\\
-x_4 + 3x_5 - s_2 &= 2\\
s_1,\, s_2 &\ge 0
\end{align}</math>
Jauh lebih mudah melakukan manipulasi aljabar pada pertidaksamaan yang disusun dalam bentuk ini. Untuk pertidaksamaan yang melibatkan operator ≥, beberapa penulis merujuk variabel lempai sebagai ''variabel surplus''.
Ketiga, semua variabel yang tidak terbatas nilainya dihapus dari program linear. Hal ini dapat dilakukan dengan dua cara. Cara pertama dilakukan dengan menuliskan variabel tersebut sebagai sebuah persamaan dari variabel-variabel lain, lalu menghilangkan semua kemunculannya di program linear lewat subtitusi. Cara lain adalah dengan menyatakan variabel tersebut sebagai selisih dua variabel yang terbatas nilainya. Sebagai contoh jika nilai <math>z_1</math> tidak terbatas, nilainya dapat ditulis sebagai
: <math>\begin{align}
&z_1 = z_1^+ - z_1^-\\
&z_1^+,\, z_1^- \ge 0
\end{align}</math>
Persamaan ini dapat digunakan untuk mengeliminasi <math>z_1</math> dari program linear.
Setelah proses-proses tersebut dilakukan, daerah feasibel akan memiliki bentuk
: <math>\mathbf{A}\mathbf{x} = \mathbf{b},\, \forall i \ x_i \ge 0</math>
Dalam pembahasan, umumnya berguna untuk mengasumsikan bahwa [[Rank (aljabar linear)|rank]] dari <math>\mathbf{A}</math> sama dengan banyaknya baris dari matriks tersebut. Hal ini tidak mengurangi keumuman karena antara sistem <math>\mathbf{A}\mathbf{x} = \mathbf{b}</math> mengandung persamaan yang redundan (sehingga dapat dihapus), atau sistem tersebut tidak konsisten (sehingga tidak memiliki solusi).<ref>{{harvtxt|Murty|1983|p=173}}</ref>
== Perumusan ==
| |||