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

Математикалық ықшамдауда, Данцигтің симлекс алгоритмі (немесе симлекстік әдіс) сызықтық программалауда кеңінен таралған алгоритм. Информатика төң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 ₁ мүшесін сызықтық программадан шығарылуы үшін қолданыс табады.Осылайша кіші мәнді шектеулер оң мәнді шектеулерге айналады. Екіншіден, әр бір қалып отырған шектеулер үшін "жалған айнымалы" еніп отыр,олар шектеулерді теңдікке ауыстыру үшін кіргізіледі.Бұл айнымалы теңсіздіктің екі жағындағы айырмашылықты көрсетеді және бұл айнымалы оң болады деп санаймыз.

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

төмендегідей ауысды.

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

Бұл түрде алгебралық тұрғыда амалдар қолдану жеңіл болады. " ≥ " пайда болатын теңсіздіктерде көптеген авторлар "мол айнымалысына" жүгінеді. Үшіншіден,шектеусіз мүше сызықтық программалауда теңсіздіктен шығады. Екі әдіспен іске асыруға болады.Бір жолы мүше кездескен теңсіздікте айнымалы енгізу арқылы, екінші жолы мүшені екі шегі бар мүшемен алмастыру болып табылады. В-третьих, каждый неограниченный переменной выводится из линейного программирования. Мысалы, егер z₁ шектеусіз болса,онда

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

Теңдіктен z₁ сызықты программалауда алып тастау мүмкін болды.

Процесс толық мүмкін ауданға келгенде мынадай түрде жазылады

$\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.