Metode simpleks: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
Rescuing 1 sources and tagging 0 as dead.) #IABot (v2.0.8.6 |
Dianasywara (bicara | kontrib) Fitur saranan suntingan: 2 pranala ditambahkan. Tag: VisualEditor Suntingan perangkat seluler Suntingan peramban seluler Tugas pengguna baru Disarankan: tambahkan pranala |
||
Baris 5:
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|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}}{{Pranala mati|date=Januari 2022 |bot=InternetArchiveBot |fix-attempted=yes }}</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>
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 book|last=Dantzig|first=George|date=May 1987|url=http://www.dtic.mil/dtic/tr/fulltext/u2/a182708.pdf|journal=A History of Scientific Computing|isbn=978-0-201-50814-7|pages=141–151|chapter=Origins of the simplex method|doi=10.1145/87252.88081|title=Salinan arsip|access-date=2021-10-31|archive-date=2017-03-29|archive-url=https://web.archive.org/web/20170329041709/http://www.dtic.mil/dtic/tr/fulltext/u2/a182708.pdf|dead-url=yes}}</ref>
== Gambaran umum ==
Baris 76:
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
| |||