Metode simpleks: Perbedaan antara revisi

← Revisi sebelumnya Revisi selanjutnya →

Konten dihapus Konten ditambahkan

Sebaris

Revisi per 31 Oktober 2021 16.27

Polihedron dari algoritma simpleks dalam tiga dimensi.

Metode simpleks (simplex method) adalah algoritma yang populer digunakan untuk memecahkan masalah dalam pemrograman linear.^[1] Nama dari algoritma ini berasal dari kata simpleks, perumuman dari konsep segitiga atau tetrahedron pada sebarang dimensi; dan diusulkan oleh T. S. Motzkin.^[2] Simpleks sebenarnya tidak digunakan, namun salah satu intepretasi menjelaskan bahwa algoritma ini berkerja pada sinar kerucut (kerucut sederhana, simplicial cones); yang akan menjadi simpleks dengan menambah sebuah konstrain tambahan.^[3]^[4]^[5]^[6] Sinar kerucut yang dimaksud adalah rusuk-rusuk dari bangun geometris yang dikenal dengan politop. Bentuk dari politop ini didefinisikan lewat kendala-kendala yang perlu dipenuhi oleh fungsi objektif.

Sejarah

Pada masa Perang Dunia II George Dantzig bekerja untuk AU Amerika Serikat di bagian 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.^[7] Perkembangan metode simpleks adalah sebuah inovasi dan terjadi hanya dalam kurun waktu sekitar satu tahun.^[8]

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 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 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.^[9]

Gambaran umum

A system of linear inequalities defines a polytope as a feasible region. The simplex algorithm begins at a starting vertex and moves along the edges of the polytope until it reaches the vertex of the optimal solution.

Algoritma simpleks bekerja pada program linear dalam bentuk kanonik (baku):

Maksimumkan

{\textstyle \mathbf {c} ^{\text{T}}\mathbf {x} }

dengan kendala

A\mathbf {x} \leq \mathbf {b}

dan

\mathbf {x} \geq 0

Dalam bentuk ini, vektor $\mathbf {c} =(c_{1},\,\dots ,\,c_{n})$ adalah koefisien dari fungsi objektif, $(\cdot )^{\mathrm {T} }$ adalah operasi transpos, dan $\mathbf {x} =(x_{1},\,\dots ,\,x_{n})$ adalah variabel-variabel dari masalah. Selain itu, $A$ adalah matriks berukuran $p\times n$ dan $\mathbf {b} =(b_{1},\,\dots ,\,b_{p})$ . 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 $\mathbf {x}$ yang memenuhi kendala ${\textstyle A\mathbf {x} \leq \mathbf {b} }$ dand $\forall i,x_{i}\geq 0$ adalah sebuah 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.^[10] 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.^[11] 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.^[12] 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.^[12]

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).^[13]^[14]^[15]

Perumusan

Suatu masalah pemrograman linier dapat dirumuskan sebagai berikut:

Optimasikan fungsi

f=c_{1}x_{1}+c_{2}x_{2}+\ldots +c_{n}x_{n}=\sum _{j=1}^{n}c_{j}x_{j}

Dengan syarat

a_{11}x_{1}+a_{12}x_{2}+\ldots +a_{1n}x_{n}\leq b_{1}

a_{21}x_{1}+a_{22}x_{2}+\ldots +a_{2n}x_{n}\leq b_{2}

\vdots

a_{m1}x_{1}+a_{m2}x_{2}+\ldots +a_{mn}x_{n}\leq b_{m}

Syarat-syarat di atas dapat kita tuliskan dengan lebih singkat sebagai:

\sum _{i=1}^{n}a_{ij}x_{j}\leq b_{j}

;

i=1,2,3,\ldots ,m

.

Selain itu, variabel x₁, x₂, ... x_n harus memenuhi persyaratan:

x_{1},x_{2},\ldots ,x_{n}\geq 0

Referensi

^ Murty, Katta G. Linear programming. John Wiley & Sons Inc.1, 2000.
^ (Murty 1983, Comment 2.2)
^ (Murty 1983, Note 3.9)
^ Stone, Richard E.; Tovey, Craig A. (1991). "The simplex and projective scaling algorithms as iteratively reweighted least squares methods". SIAM Review. 33 (2): 220–237. doi:10.1137/1033049. JSTOR 2031142. MR 1124362.
^ Stone, Richard E.; Tovey, Craig A. (1991). "Erratum: The simplex and projective scaling algorithms as iteratively reweighted least squares methods". SIAM Review. 33 (3): 461. doi:10.1137/1033100. JSTOR 2031443. MR 1124362.
^ Strang, Gilbert (1 June 1987). "Karmarkar's algorithm and its place in applied mathematics". The Mathematical Intelligencer. 9 (2): 4–10. doi:10.1007/BF03025891. ISSN 0343-6993. MR 0883185.
^ Dantzig, George B. (April 1982). "Reminiscences about the origins of linear programming". Operations Research Letters. 1 (2): 43–48. doi:10.1016/0167-6377(82)90043-8.
^ Albers and Reid (1986). "An Interview with George B. Dantzig: The Father of Linear Programming". College Mathematics Journal. 17 (4): 292–314. doi:10.1080/07468342.1986.11972971.
^ Dantzig, George (May 1987). "Origins of the simplex method". A History of Scientific Computing (PDF). hlm. 141–151. doi:10.1145/87252.88081. ISBN 978-0-201-50814-7 http://www.dtic.mil/dtic/tr/fulltext/u2/a182708.pdf. Tidak memiliki atau tanpa |title= (bantuan)
^ (Murty 1983, Theorem 3.3)
^ (Murty 1983, hlm. 143, Section 3.13)
^ ^a ^b (Murty 1983, hlm. 137, Section 3.8)
^ George B. Dantzig and Mukund N. Thapa. 1997. Linear programming 1: Introduction. Springer-Verlag.
^ D. Nering, Evar; W. Tucker, Albert (1993). Linear Programs and Related Problems. Academic Press.
^ Robert J. Vanderbei, 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.

Artikel bertopik matematika ini adalah sebuah rintisan. Anda dapat membantu Wikipedia dengan mengembangkannya.

[Murty-1] Murty, Katta G. Linear programming. John Wiley & Sons Inc.1, 2000.

[Murty22-2] (Murty 1983, Comment 2.2)

[Murty39-3] (Murty 1983, Note 3.9)

[StoneTovey-4] Stone, Richard E.; Tovey, Craig A. (1991). "The simplex and projective scaling algorithms as iteratively reweighted least squares methods". SIAM Review. 33 (2): 220–237. doi:10.1137/1033049. JSTOR 2031142. MR 1124362.

[5] Stone, Richard E.; Tovey, Craig A. (1991). "Erratum: The simplex and projective scaling algorithms as iteratively reweighted least squares methods". SIAM Review. 33 (3): 461. doi:10.1137/1033100. JSTOR 2031443. MR 1124362.

[Strang-6] Strang, Gilbert (1 June 1987). "Karmarkar's algorithm and its place in applied mathematics". The Mathematical Intelligencer. 9 (2): 4–10. doi:10.1007/BF03025891. ISSN 0343-6993. MR 0883185.

[7] Dantzig, George B. (April 1982). "Reminiscences about the origins of linear programming". Operations Research Letters. 1 (2): 43–48. doi:10.1016/0167-6377(82)90043-8.

[8] Albers and Reid (1986). "An Interview with George B. Dantzig: The Father of Linear Programming". College Mathematics Journal. 17 (4): 292–314. doi:10.1080/07468342.1986.11972971.

[9] Dantzig, George (May 1987). "Origins of the simplex method". A History of Scientific Computing (PDF). hlm. 141–151. doi:10.1145/87252.88081. ISBN 978-0-201-50814-7 http://www.dtic.mil/dtic/tr/fulltext/u2/a182708.pdf. Tidak memiliki atau tanpa |title= (bantuan)

[10] (Murty 1983, Theorem 3.3)

[11] (Murty 1983, hlm. 143, Section 3.13)

[Murty137-12] (Murty 1983, hlm. 137, Section 3.8)

[DantzigThapa12-13] George B. Dantzig and Mukund N. Thapa. 1997. Linear programming 1: Introduction. Springer-Verlag.

[14] D. Nering, Evar; W. Tucker, Albert (1993). Linear Programs and Related Problems. Academic Press.

[Vanderbei2-15] Robert J. Vanderbei, 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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

@@ Baris 6: / Baris 6: @@
 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}}</ref>
+== Gambaran umum ==
+{{further|Program linear}}
+[[Berkas:Simplex-description-en.svg|jmpl|240x240px|A [[system of linear inequalities]] defines a [[polytope]] as a feasible region. The simplex algorithm begins at a starting [[Vertex (geometry)|vertex]] and moves along the edges of the polytope until it reaches the vertex of the optimal solution.]]
+Algoritma simpleks bekerja pada program linear dalam bentuk kanonik (baku):
+: Maksimumkan <math display="inline">\mathbf{c}^\text{T} \mathbf{x}</math>
+: dengan kendala <math>A\mathbf{x} \leq \mathbf{b}</math> dan <math>\mathbf{x} \ge 0</math>
+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> dand <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; 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>{{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>
 == Perumusan ==