«Анализ и проектирование алгоритма симплекс-метода для решения задач линейного программирования.»

Алгоритм решения
1) Формируем исходный план при свободных переменных; x_j =0, j = m+1(1)n, x_j = β_ф, ф = 1(1)m при β_ф > 0 план x^o допустим Q(x) =x_o.
2) Проверяем этот план на оптимальность, используя значения γ_j коэффициентов ЦФ в последней строке таблицы. Могут быть два случая:
а) все γ_j ≤0, j = m+1(1)n , при этом увеличение никакой переменной (из свободных) не приведёт к уменьшению ЦФ Q, т. е. план x^o улучшить нельзя, и он уже оптимален, таким образом, условием оптимальности плана является – отсутствие в таблице γ_j >0.
б) некоторые γ_j > 0. В этом случае увеличение значений соответствующих свободных переменных x_j (γ_j > 0) будет минимизировать Q, так как

Чтобы Q уменьшалось, такие переменные следует вводить (последовательно) в базис, но, чтобы размерность пространства не изменялась из базиса должны выводиться переменные в число свободных (по одной) формируем множество индексов Г = { j | γ_j >0}. Какая переменная должна первой вводиться в базис? Вообще последовательно перебирая (вершины симплекса) решение отыскивается при произвольном выборе, но для определённости выбираем новую базисную переменную с индексом v = argmax {x_j}, где j ∈ Г. Теперь определим переменную (базисную), которая будет выводиться из базиса.
В системе уравнений

Начинаем увеличивать х_v до тех пор, пока некоторый х_ф станет отрицательным. Первый же х_ф ≤ 0 будет выводиться из базиса. Определение. Столбец с индексом v и строка с индексом ф = i называются направляющими.
3) Проверка существования решения (ограниченность ЗЛП). В выражениях, связывающих х, ∝, β, х_ф = β_ф -∝_фvх_v, ф=1(1)m, могут быть все ∝_фv < 0 и тогда рост х_v будет неограниченно увеличивать все х_ф, т.е. ни одно отрицательное значение не будет принимать. Это случай, когда ЦФ Q  не ограничена снизу и, следовательно, ЗЛП не имеет оптимального решения.
Признаком неограниченности ЦФ является отсутствие в направляющем v- м столбце значений ∝_фv > 0. Пусть ЦФ ограничена и некоторые ∝_фv > 0. Сформируем множество индексов S = { ф | ∝_фv >0}. Из базиса необходимо выводить переменную с индексом i, так как она первая обращается в нуль, i = argmin(β_ф/∝_фv), где ф∈S, таким образом, базисная переменная x_i выводится из базиса.