x_k 0 ( k = 1(1)17)

Для решения задачи методом искусственных переменных добавим в ограничения и целевую функцию переменные x₁₈ , x₁₉ , x₂₀ , x₂₁ , x₂₂ :

,

при ограничениях:

x_k 0 ( k = 1(1)22)

3. Краткие сведения о методе решения задачи

3.1 Табличный симплекс-метод

Основная идея симплекса-метода состоит в переходе от одного допустимого базисного решения к другому таким образом, что значения целевой функции при этом непрерывно возрастают (для задач максимизации). Предположим, что ограничения задачи сведены к такому виду, что в матрице А имеется единичная подматрица и все свободные члены положительные. Иными словами, пусть матрица ограничений имеет вид

A_1x1 +...+A_n x_n +e₁ x_n +e₁ x_n +1+…+e_m x_n +m=A₀ =[a_i0 ],

где

. - единичный базис, a_i0 ≥ 0

для всех i = 1, 2,..., n. Применим одну итерацию метода полного исключения к расширенной матрице ограничений A_p =[A₁ , ., A_n , e₁ , ., e_m , A₀ ].

Преобразование Гаусса называют симплексным преобразованием, когда направляющий элемент определяют по следующим правилам:

a) направляющий столбец j выбирают из условия, что в нем имеется хотя бы один положительный элемент;

б) направляющую строку i выбирают так, чтобы отношение было минимально при условии, что a_ij >0.

При таком преобразовании в базис вводится вектор A_j и выводится вектор А_i . Теперь надо определить, как выбрать вектор, вводимый в базис, чтобы при этом значение целевой функции увеличилось.

Для этого используют так называемые оценки векторов ∆_j :

(2.2.21)