Metode simpleks: Perbedaan antara revisi

Pada masa Perang Dunia II [[George Dantzig]] bekerja untukdi AU Amerika Serikat diuntuk bagianmengurus 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|last1=Dantzig|first1=George B.|date=April 1982|title=Reminiscences about the origins of linear programming|url=http://www.dtic.mil/cgi-bin/GetTRDoc?Location=U2&doc=GetTRDoc.pdf&AD=ADA112060|journal=Operations Research Letters|volume=1|issue=2|pages=43–48|doi=10.1016/0167-6377(82)90043-8}}</ref> Perkembangan metode simpleks adalah sebuah inovasi dan terjadi hanya dalam kurun waktu sekitar satu tahun.<ref>{{Cite journal|last=Albers and Reid|date=1986|title=An Interview with George B. Dantzig: The Father of Linear Programming|url=http://www.phpsimplex.com/en/Dantzig_interview.htm|journal=College Mathematics Journal|volume=17|issue=4|pages=292–314|doi=10.1080/07468342.1986.11972971}}</ref>

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> danddan <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 berhingga, karena hanya terdapat terhingga banyaknya titik ekstrem; walauwalaupun 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> JikaPada kasus 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 akan 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 terhinggterhingga 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 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|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>

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 perbedaanselisih antara variabel asal dengandan batas bawahnya. Variabel asal selanjutnya dapat dihilangkan dengan melakukan subtitusi. Sebagai contoh, misalkan ada kendala

akan diubah bentuknya menjadi

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 dariberisi variabel-variabel lain, lalu menghilangkan semua kemunculannya di program linear lewatdengan subtitusi. Cara lain adalah dengan menyatakan variabel tersebut sebagai selisih dua variabel yang terbatas nilainya. Sebagai contoh jika nilai <math>z_1</math> tidak terbatasdibatasi, nilainya dapat ditulis sebagai

Persamaan ini dapatselanjutnya digunakan untuk mengeliminasi <math>z_1</math> dari program linear.

Dalam pembahasan, umumnya berguna untuk mengasumsikan bahwa [[Rank (aljabar linear)|rank]] dari <math>\mathbf{A}</math> sama dengan banyaknyabanyak 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 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>,. danLebih lanjut, solusi ini adalah sebuah solusi feasibel sederhana. Intepretasi aljabar kejadian ini adalahterlihat 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>

Dengan kendala:
:<math display="block">\begin{align}

\end{align}</math>

Hal ini dapat direpresentasikan dengan sebuah tablo (belum berbentuk kanonik):
:<math display="blockinline">

: <math display="inline">

Pilih kolom ke-5 sebagai kolom pivot; sehingga baris pivot yang dipilih haruslah baris ke-4. Tablo baru yang terbentuk adalah

Lalu pilih kolom-3 sebagai kolom pivot; hal ini mengharuskan baris ke-3 sebagai baris pivot. Langkah ini akan menghasilkan
:<math display="blockinline">