9. Выводы и следствия двухфазного симплекс-метода.

(1)

С учётом симплекс алгоритма можно сделать для задачи (1) следующий вывод.

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

а) , то есть ограничения задачи (1) несовместны, и у неё нет ни одного плана, а значит, нет оптимального плана (случай первой фазы);

б) у задачи будет построен – оптимальный базисный план (случаи 2 и 3 первой фазы и теорема 1 симплекс-метода);

в) будет доказана неограниченность целевой функции (случаи 2 и 3 первой фазы и выполнение теоремы 2 на второй фазе).

Других случаев для задачи (1) быть не может.

Следствие 1. Если у задачи (1) есть планы, то у неё обязательно есть и базисные планы.

Доказательство. Действительно, в этом случае возможен либо случай 2, либо случай 3 на первой фазе и оба они заканчиваются построением базисного плана.

Ч.т.д.

Следствие 2. Если у задачи (1) существует решение, то у неё обязательно будет и оптимальный базисный план.

Доказательство. Действительно, если не выполняется в случаях а) и в) вывода, то остаётся лишь случай б).

Ч.т.д.

Следствие 3. Для того чтобы у задачи (1) существовал оптимальный план необходимо и достаточно, чтобы её целевая функция была ограничена сверху на непустом множестве планов.

Доказательство. Необходимость. Если – оптимальный план задачи (1), то целевая функция ограничена сверху числом и множество планов задачи непустое.

Достаточность. Пусть множество задачи (1) непустое и известно, что на этом множестве целевая функция ограничена сверху некоторым числом. Тогда возможен лишь исход б) вывода, то есть у задачи существует оптимальный план.

10. Приведение задач к канонической форме. Табличная реализация симплекс-метода.

Определение. Две задачи оптимизации называться эквивалентными, если либо у них одинаковый оптимальный план, либо отсутствует решение по одной и той же причине. Соответствующие преобразования одной задачи в другую называется эквивалентными.

Теорема 4. Любую задачу линейного программирования можно свести к эквивалентной задаче в канонической форме.

Доказательство (конструктивное). Возможны следующие случаи не каноничности и их эквивалентного преобразования:

1. если в задаче целевая функция имеет вид: , то это эквивалентно , то есть эквивалентное преобразование состоит в умножении на (-1). Эквивалентность задач целевыми функциями и вытекает из определения максимума и минимума.

2. пусть среди основных ограничений имеется ограничение неравенства: , тогда оно эквивалентно паре (основному равенству и прямому ограничению):

,

где новая неотрицательная переменная, которая для каждого плана указывает, каково отклонение в нашем пространстве от числа . То есть для сведения неравенства к уравнению вводится дополнительная неотрицательная переменная, которая называется свободной или балансовой и она на каждом плане указывает, какой неотрицательной части не хватает до равенства в неравенстве. Если неравенство имеет вид: , то свободную переменную нужно вычесть:

3. пусть на переменную задачи линейного программирования не накладываются условия неотрицательности, то есть эта переменная может принимать и положительные, и отрицательные, и нулевые значения. Тогда совершаем замену:

(19)

то есть, представляем эту переменную в виде разности двух неотрицательных новых переменных. Так как любое число всегда представимо в виде разности двух неотрицательных чисел, то задачи эквивалентны.

Замечание. Если хотя бы в одном основном ограничении задачи, коэффициент при отличен от нуля, то можно вместо замены (19) исключить переменную из задачи: выразить её из этого основного ограничения через остальные и подставить в целевую функцию и оставшиеся основные ограничения.

Теорема доказана, так как других неканонических элементов в задачах линейного программирования быть не может.

Ч.т.д.

Производственная задача (20) (все основные ограничения – неравенства) называется задачей линейного программирования в нормальной форме и она эквивалентна канонической задаче (21)

, – вектор свободных переменных. Свободные не следует путать с искусственными переменными. Они имеют физический смысл.

– это неиспользованное количество -ого ресурса на производственном плане . У производственной задачи сразу строится начальный базисный план, а именно и, следовательно, для задачи в нормальной форме не требуется первая фаза.