Metode simpleks

Polihedron dari algoritma simpleks dalam tiga dimensi.

Metode simpleks (simplex method) adalah algoritma yang populer digunakan untuk memecahkan masalah dalam pemrograman linear. Nama dari algoritma ini berasal dari kata simpleks, perumuman dari konsep segitiga atau tetrahedron pada sebarang dimensi; dan diusulkan oleh T. S. Motzkin. 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. 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. Perkembangan metode simpleks adalah sebuah inovasi dan terjadi hanya dalam kurun waktu sekitar satu tahun.

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.

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$