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

Перед запуском алгоритма требуется преобразовать задачу линейного программирования к канонической форме

Ограничения:

Разделим множество переменных данной задачи на свободные и базисные, при этом свободные могут принимать любые значения > 0, а базисные вычисляются через свободные. Пусть в нашем дальнем рассмотрении x — свободные переменные, а y — базисные переменные

Построим симплекс-таблицу (СТ) на основе заданной надписи задачи

Рассмотрим укрупненную схему алгоритма, которая соответствует данному методу

П₄ – критерий оптимальности минимален, если в строке Q все элементы a_j – отрицательные.

П₁ — ограничения совместные, если на каждой итерации в каждой строке симплекс таблице, имеющей отрицательный свободный член “b”, есть хотя бы один отрицательный коэффициент “a”.

П₂ — решение допустимо если в СТ все свободные члены “b” неотрицательны

П₃ — критерий ограничен снизу, если на каждой итерации в каждом столбце СТ, содержащем положительный коэффициент a_j, имеется хотя бы 1 положительное a.

Правило А служит для построения вариантов решения задач путем попарного обмена местами базисного и свободных переменных. Включает следующие действия:

- определить разрешающий элемент в СТ

- разрешающий элемент заменить на

- остальные элементы разрешающей строки умножают на

- остальные элементы разрешающего столбца умножают на

- все другие СТ стоящие на пересеченной l-ой строки S-ого столбца вычисляем по формуле