Metode simpleks

Metode simpleks adalah algoritme yang digunakan untuk memecahkan masalah dalam pemrograman linier. Metode ini digunakan untuk masalah dengan jumlah variabel lebih dari dua.

Polihedron dari algoritma simpleks dalam tiga dimensi.

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$