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 19:
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 berhingga, karena hanya terdapat terhingga banyaknya titik ekstrem; walau banyaknya titik ekstrem dapat terlalu besar untuk dapat ditangani.<ref>{{harvtxt|Murty|1983|loc=Section 3.13|p=143}}</ref> Selain itu, juga dapat dibuktikan jika sebuah titik ekstrem tidak memberikan fungsi objektif nilai yang maksimum, maka ada rusuk dari titik tersebut yang "mengarahkan" fungsi objektif ke nilai yang lebih tinggi.<ref name="Murty137">{{harvtxt|Murty|1983|loc=Section 3.8|p=137}}</ref> Jika panjang rusuk terhingga, maka rusuk akan terhubung dengan sebuah titik ekstrem lain yang memiliki nilai fungsi objektif lebih tinggi; namun jika panjang rusuk tak hingga, nilai fungsi objektif tidak terbatas dan program linear tidak memiliki solusi. Algoritma simpleks menerapkan wawasan ini, dengan "berjalan" sepanjang rusuk-rusuk dari politop untuk mencapai titik ekstrem dengan nilai fungsi objektif paling besar; atau berhenti ketika mencapai rusuk dengan panjang tak terbatas. Algoritma selalu berakhir (''terminates'') karena ada terhingg banyaknya rusuk pada politop. Selain itu, karena kita menelurusi rusuk-rusuk dalam "arah yang sama" dengan fungsi objektif, kita berharap hanya sedikit rusuk yang perlu dikunjungi.<ref name="Murty137" />
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 name=":0">{{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 ==
Baris 63:
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>
== Tablo simpleks ==
Sebuah program linear dalam bentuk baku dapat representasikan sebagai sebuah tablo (''tableau'') berikut
: <math>
\begin{bmatrix}
1 & -\mathbf{c}^T & 0 \\
0 & \mathbf{A} & \mathbf{b}
\end{bmatrix}
</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> (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>, dan solusi ini adalah sebuah solusi feasibel sederhana. Intepretasi aljabar kejadian ini adalah 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>
\begin{bmatrix}
1 & -\mathbf{c}^T_B & -\mathbf{c}^T_D & 0 \\
0 & I & \mathbf{D} & \mathbf{b}
\end{bmatrix}
</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>
\begin{bmatrix}
1 & 0 & -\bar{\mathbf{c}}^T_D & z_B \\
0 & I & \mathbf{D} & \mathbf{b}
\end{bmatrix}
</math>
dengan <math>z_B</math> menyatakan nilai fungsi objektif pada solusi feasibel sederhana yang bersangkutan. Koefisien baru <math>-\bar{\mathbf{c}}^T_D</math> menyatakan kerugian relatif (''relative cost''), yakni representasi dari laju perubahan fungsi objektif relatif terhadap variabel-variabel bebas.<ref name=":0" />
== Perumusan ==
| |||