Metode simpleks: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
Rescuing 1 sources and tagging 0 as dead.) #IABot (v2.0.8.6 |
Fitur saranan suntingan: 2 pranala ditambahkan. |
||
| (2 revisi perantara oleh 2 pengguna tidak ditampilkan) | |||
Baris 1:
{{about|algoritma untuk pemrograman linear|optimisasi heuristik non-linear|Metode Nelder–Mead}}
[[File:Simplex-method-3-dimensions.png|thumb|Polihedron dari algoritma simpleks dalam tiga dimensi.]]
'''Metode simpleks''' (''simplex method'') adalah [[algoritme|algoritma]] yang populer digunakan untuk
Nama dari algoritma ini berasal dari == Sejarah ==
Pada masa Perang Dunia II [[George Dantzig]] bekerja di AU [[Amerika Serikat]] untuk mengurus metode penjadwalan. Selama tahun 1946, rekan kerjanya menantang dia untuk menstandarkan (''mechanize'') proses penjadwalan, untuk mengalihkan perhatiannya dari mengambil pekerjaan-pekerjaan lain. Terinspirasi dari karya [[Wassily Leontief]], Dantzig memformulasi masalah sebagai sistem pertidaksamaan linear. Namun pada saat itu ia tidak mengikutkan objektif sebagai bagian dalam formulasi. Tanpa sebuah objektif, ada banyak solusi yang mungkin; sehingga untuk mencari solusi yang "optimal", aturan-aturan militer perlu digunakan untuk menjelaskan objektif yang diinginkan. Pencerahan yang didapatkan Dantzig adalah banyak dari aturan-aturan militer tersebut dapat disusun menjadi sebuah fungsi objektif linear yang perlu dimaksimumkan.<ref>{{Cite journal|
Setelah Dantzig mengikutsertakan fungsi objektif dalam formulasinya pada sekitar tahun 1947, permasalahan menjadi lebih mudah secara matematis. Dantzig menyadari satu dari pertanyaan belum terpecahkan yang tidak sengaja dia selesaikan, karena [[George Dantzig|ia pikir itu adalah pekerjaan rumah]] dari profesornya [[Jerzy Neyman]], dapat digunakan untuk menemukan algoritma bagi program linear. Pertanyaan itu melibatkan proses mencari eksistensi [[Pengali Lagrange|pengali Langrange]] untuk program linear secara umum. Program linear ini dapat terdiri dari banyak variabel, masing-masing terbatas (''bounded'') diantara nol dan satu, dan memenuhi kendala linear yang dinyatakan dalam bentuk [[integral Lebesgue]]. Dantzig kemudian mempublikasikan "pekerjaan rumah"-nya sebagai [[tesis]] untuk mendapatkan gelar doktor. Geometri yang digunakan dalam tesis ini memberikan Dantzig wawasan bahwa metode simpleks dapat sangat efisien.<ref>{{Cite
== Gambaran umum ==
Baris 17 ⟶ 20:
Dalam bentuk ini, vektor <math>\mathbf{c} = (c_1,\, \dots,\, c_n)</math> adalah koefisien dari fungsi objektif, <math>(\cdot)^\mathrm{T}</math> adalah operasi [[transpos]], dan <math> \mathbf{x} = (x_1,\, \dots,\, x_n)</math> adalah variabel-variabel dari masalah. Selain itu, <math>A</math> adalah matriks berukuran <math>p\times n</math> dan <math> \mathbf{b} = (b_1,\, \dots,\, b_p)</math>. Ada cara mudah untuk menyusun sebarang program linear menjadi bentuk bakunya, sehingga penggunaan bentuk ini tidak mengurangi keumuman dari pembahasan. Dalam konteks geometri, daerah feasibel nilai <math>\mathbf{x}</math> yang memenuhi kendala <math display="inline">A\mathbf{x} \le \mathbf{b}</math> dan <math>\forall i, x_i \ge 0 </math> adalah sebuah [[Politop cembung|politop konveks]], yang mungkin tidak terbatas (''unbounded''). Sebuah titik ekstrem atau rusuk dari politop ini dikenal sebagai solusi feasibel sederhana (''basic feasible solution,'' BFS).
Dapat ditunjukkan untuk program linear dalam bentuk baku, jika fungsi objektif mempunyai nilai maksimum di daerah feasibel, maka nilai maksimum ini terletak di (setidaknya satu) titik ekstrem.<ref>{{harvtxt|Murty|1983|loc=Theorem 3.3}}</ref> Hal ini menyederhanakan program linear menjadi sebuah masalah komputasi yang
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 nilai fungsi tidak terbatas dari atas).<ref name="DantzigThapa12">[[George B. Dantzig]] and Mukund N. Thapa. 1997. ''Linear programming 1: Introduction''. Springer-Verlag.</ref><ref name=":0">{{Cite book|last=D. Nering|first=Evar|last2=W. Tucker|first2=Albert|date=1993|title=Linear Programs and Related Problems|url=https://archive.org/details/linearprogramsre0000neri|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>▼
▲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 nilai fungsi tidak terbatas dari atas).<ref name="DantzigThapa12">
== 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 selisih antara variabel asal dan 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
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.
Baris 34 ⟶ 35:
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
\end{align}</math>
akan diubah bentuknya menjadi
\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 berisi variabel-variabel lain, lalu menghilangkan semua kemunculannya di program linear dengan subtitusi. Cara lain adalah dengan menyatakan variabel tersebut sebagai selisih dua variabel yang terbatas nilainya. Sebagai contoh jika nilai <math>z_1</math> tidak dibatasi, nilainya dapat ditulis sebagai
\end{align}</math>
Baris 60 ⟶ 61:
Setelah proses-proses tersebut dilakukan, daerah feasibel akan memiliki bentuk
Dalam pembahasan, umumnya berguna untuk mengasumsikan bahwa [[Rank (aljabar linear)|rank]] dari <math>\mathbf{A}</math> sama dengan banyak 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>
Baris 67 ⟶ 68:
Sebuah program linear dalam bentuk baku dapat representasikan sebagai sebuah tablo (''tableau'') berikut
</math>
Baris pertama matriks di atas mendefinisikan fungsi objektif, sedangkan sisanya mendefinisikan kendala-kendala dari program. Nol pada kolom pertama merepresentasikan [[vektor nol]] dengan dimensi yang sama dengan vektor <math>\mathbf{b}</math> (beberapa penulis menggunakan konvensi tablo yang berbeda). Jika kolom dari matriks <math>\mathbf{A}</math> diatur agar mengandung [[matriks identitas]] berukuran <math>p</math> (yakni banyaknya baris di <math>\mathbf{A}</math>) maka tablo dikatakan dalam ''bentuk kanonik''.<ref>{{harvtxt|Murty|1983|loc=section 2.3.2}}</ref> Variabel-variabel yang bersesuaian dengan kolom-kolom dari matriks identitas disebut dengan ''variabel sederhana'' (''basic variables''), sedangkan variabel yang tersisa disebut ''variabel bebas'' (''free variables,'' atau ''nonbasic'').
Jika nilai dari variabel bebas ditetapkan sama dengan 0, maka nilai dari variabel sederhana dapat dengan mudah ditentukan sebagai entri dari <math>\mathbf{b}</math>. Lebih lanjut, solusi ini adalah sebuah solusi feasibel sederhana. Intepretasi aljabar kejadian ini terlihat dengan memandang koefisien-koefisien dari [[persamaan linear]] yang direpresentasikan setiap baris, dapat bernilai <math>0</math>, <math>1</math>, atau suatu bilangan lainnya. Setiap baris akan memiliki <math>1</math> kolom bernilai <math>1</math>, <math>p-1</math> kolom dengan nilai koefisien <math>0</math>, sedangkan kolom yang tersisa berisi nilai koefisien lainnya (kolom-kolom ini merepresentasikan variabel-variabel bebas). Dengan membuat nilai setiap variabel bebas sama dengan nol pada setiap baris, kita memastikan setiap variabel yang direpresentasikan oleh <math>1</math> pada kolom dari <math>\mathbf{A}</math>, akan sama dengan nilai <math>\mathbf{b}</math> pada baris tersebut. Sebaliknya, jika diberikan sebuah solusi feasibel sederhana, kolom yang berkorespodensi dengan variabel yang bernilai tidak nol, dapat dikembangkan menjadi sebuah matriks tak singular. Jika tablo yang bersangkutan dikalikan dengan invers dari matriks ini, maka tablo tersebut berubah menjadi bentuk kanoniknya.<ref>{{harvtxt|Murty|1983|loc=section 3.12}}</ref>
Misalkan
</math>
adalah sebuah tablo dalam bentuk kanoniknya. [[Matriks dasar|Operasi baris dasar]] dapat diterapkan pada baris pertama untuk menghilangkan koefisien <math>\mathbf{c}_B^\text{T}</math> dari fungsi objektif. Hasil akhir dari proses ini adalah sebuah tablo bentuk kanonik dalam format
</math>
Baris 109 ⟶ 110:
Jika ada lebih dari satu entri pada baris fungsi objektif (terletak di baris pertama pada tablo) yang bernilai positif, ada kebebasan dalam memilih kolom yang akan menjadi variabel sederhana; beberapa aturan pemilihan<ref name="Murty66">{{harvtxt|Murty|1983|p=66}}</ref> seperti algoritma Devex<ref>Harris, Paula MJ. "Pivot selection methods of the Devex LP code." Mathematical programming 5.1 (1973): 1–28</ref> dikembangkan untuk memilih kolom. Jika semua entri objektif bernilai 0 atau kurang dari itu, maka tidak ada kolom pivot yang dapat pilih, dan solusi yang didapat sudah optimal. Keoptimalan dapat terlihat karena baris fungsi objektif setara dengan persamaan dengan bentuk
Mengubah aturan pemilihan agar memilih entri bernilai negatif dari baris fungsi objektif, akan membuat algoritma mencari
=== Pemilihan baris pivot ===
Baris 123 ⟶ 124:
: Minimumkan <math>Z = -2 x - 3 y - 4 z\,</math>
: Dengan kendala
:
\end{align}</math>
Dengan menambah variabel lempai <math>s</math> dan <math>t</math>, program linear akan memiliki tablo bentuk kanonik
</math>
dengan kolom ke-5 dan ke-6 menandakan variabel sederhana <math>s</math> dan <math>t</math>. Solusi feasibel sederhana yang berkorespodensi dengan tablo ini adalah
Selanjutnya, kolom ke-2, ke-3, dan ke-4 dapat digunakan sebagai kolom pivot. Untuk contoh ini akan dipilih kolom ke-4. Nilai dari <math>b_r / a_{rc}\,</math>untuk baris ke-2 dan baris ke-3 secara berurutan adalah 10/1 = 10 dand 15/3 = 5. Karena minimum dari kedua nilai ini adalah 5, baris ke-3 dipilih sebagai baris pivot. Setelah menerapkan operasi pivot pada tablo, akan dihasilkan tablo
</math>
Sekarang kolom ke-4 dan ke-5 merepresentasikan variabel sederhana <math>z</math> dan <math>s</math>. Solusi feasibel sederhana dari tablo tersebut adalah<math display=block>x=y=t=0,\,z=15/3,\,s=15/3.</math>
Tidak ada entri positif di baris fungsi objektif, sehingga operasi pivot tidak dapat dilakukan. Lebih lanjut, fungsi objektif yang berkorespondensi dengan tablo,
sudah optimal, dengan nilai minimum dari <math>Z</math> adalah −20 (hasil subtitusi <math>x=y=t=0</math>).
Baris 173 ⟶ 172:
Minimumkan <math>Z = -2 x - 3 y - 4 z\,</math>
Dengan kendala:<math display="block">\begin{align}
\end{align}</math>
Hal ini dapat direpresentasikan dengan sebuah tablo (belum berbentuk kanonik):
:<math display="inline">▼
\begin{bmatrix}▼
1 & 2 & 3 & 4 & 0 \\ ▼
▲ 0 & 3 & 2 & 1 & 10 \\
0 & 2 & 5 & 3 & 15▼
\end{bmatrix}▼
\begin{bmatrix}▼
0 & 0 & 3 & 2 & 1 & 1 & 0 & 10 \\▼
0 & 0 & 2 & 5 & 3 & 0 & 1 & 15▼
\end{bmatrix}▼
</math>
Bentuk dua variabel buatan baru <math>u</math> dan <math>v</math>, dan fungsi objektif baru <math>W=u+v</math>. Hal ini akan membentuk tablo baru<math display="block">
\begin{bmatrix} 1 & 0 & 0 & 0 & 0 & -1 & -1 & 0 \\ 0 & 1 & 2 & 3 & 4 & 0 & 0 & 0 \\ 0 & 0 & 3 & 2 & 1 & 1 & 0 & 10 \\ 0 & 0 & 2 & 5 & 3 & 0 & 1 & 15 \end{bmatrix} </math>Persamaan-persamaan yang mendefinisikan masalah yang sebenarnya tetap dipertahankan untuk Tahap II. Dari konstruksinya, <math>u</math> dan <math>v</math> adalah variabel sederhana karena mereka adalah bagian dari matriks identitas. Namun, fungsi objektif <math>W</math> saat ini mengasumsikan <math>u</math> dan <math>v</math> keduanya bernilai 0. Untuk mengoreksi nilai dari fungsi objektif, dengan <math>u=10</math> dan <math>v=15</math>, Baris ketiga dan keempat pada tablo ditambahkan ke baris pertama, menghasilkan tablo </math>
Pilih kolom ke-5 sebagai kolom pivot; sehingga baris pivot yang dipilih haruslah baris ke-4. Tablo baru yang terbentuk adalah<math display="block">
\begin{bmatrix}▼
0
0
\end{bmatrix}▼
</math>
Lalu pilih kolom-3 sebagai kolom pivot; hal ini mengharuskan baris ke-3 sebagai baris pivot. Langkah ini akan menghasilkan<math display="block">
\begin{bmatrix}▼
0
0
0 & 0 & 0 &
\end{bmatrix}▼
</math>
Nilai fungsi objektif saat ini bernilai 0 (sudah minimum), dan variabel-variabel buatan dapat dihilangkan agar menghasilkan tablo kanonik yang ekuivalen dengan masalah yang sebenarnya. Tablo tersebut adalah:<math display="block">
0
</math>
| |||