Симплекстік әдіс

Математикалық ықшамдауда, Данцигтің симлекс алгоритмі (немесе симлекстік әдіс) сызықтық программалауда кеңінен таралған алгоритм. Информатика төңiрегiндегi техникалық есептеуiш журналы (The journal Computing in Science and Engineering) бұл алгоритмді 20 ғасырдың он мықты алгоритмдерінің біреуіне жатқызды.Алгоритм аты Т.С.Мотцин айтып кеткендей жеңіл (simplex ) деген сөзден шыққан.Симплекс әдістерде қолданыс таппайды, бірақ ол симплексациялық конустарға ісерін тигізеді, қосымша шектеулермен симплекстерге тиісті болады. Конусты симплексті қарау бұрыш яғни бұрыштарының жаны геометриялық дене, көпжақ.

Cтандартты түрі

Сызықтық программалауды стандартты түрдің ьіреуіне келтіру келесі түрде іске асуы мүмкін. Біріншіден, барлық нөлден басқа мәні кіші мүшеге жаңа мүше енгізілуі мүмкін. Шын мүше жаңа мүше арқылы шеттелуге болады.

$x_{1}\geq 5$

жаға мүше, y₁, былайша жазылады

${\begin{aligned}y_{1}=x_{1}-5\\x_{1}=y_{1}+5\end{aligned}}$

Екінші теңдеу x ₁ мүшесін сызықтық программадан шығарылуы үшін қолданыс табады.Осылайша кіші мәнді шектеулер оң мәнді шектеулерге айналады.

Second, for each remaining inequality constraint, a new variable, called a slack variable, is introduced to change the constraint to an equality constraint. This variable represents the difference between the two sides of the inequality and is assumed to be nonnegative. For example the inequalities

${\begin{aligned}x_{2}+2x_{3}&\leq 3\\-x_{4}+3x_{5}&\geq 2\end{aligned}}$

are replaced with

${\begin{aligned}x_{2}+2x_{3}+s_{1}&=3\\-x_{4}+3x_{5}-s_{2}&=2\\s_{1},\,s_{2}&\geq 0\end{aligned}}$

It is much easier to perform algebraic manipulation on inequalities in this form. In inequalities where ≥ appears such as the second one, some authors refer to the variable introduced as a surplus variable.

Third, each unrestricted variable is eliminated from the linear program. This can be done in two ways, one is by solving for the variable in one of the equations in which it appears and then eliminating the variable by substitution. The other is to replace the variable with the difference of two restricted variables. For example if z₁ is unrestricted then write

${\begin{aligned}&z_{1}=z_{1}^{+}-z_{1}^{-}\\&z_{1}^{+},\,z_{1}^{-}\geq 0\end{aligned}}$

The equation may be used to eliminate z₁ from the linear program.

When this process is complete the feasible region will be in the form

$\mathbf {A} \mathbf {x} =\mathbf {b} ,\,x_{i}\geq 0$

It is also useful to assume that the rank of A is the number of rows. This results in no loss of generality since otherwise either the system Ax >= b has redundant equations which can be dropped, or the system is inconsistent and the linear program has no solution.