- •Предмет курса. Основные понятия. Общая схема решения задач. Производственная задача.
- •Графический метод.
- •Каноническая задача. Базисный план. Формула приращений
- •Формула приращений целевой функции
- •Критерий оптимальности.
- •Достаточное условие неограниченности. Алгоритм обратной м-цы.
- •Итерация. Симплекс-метод (алгоритм).
- •Конечность. Геометрическая интерпретация.
- •Двухфазный симплекс-метод.
- •Выводы и следствия двухфазного симплекс-метода.
- •Приведение задач к канонической форме. Табличная реализация симплекс-метода.
- •Двойственная задача. Взаимодвойственность.
- •Соотношения двойственности 1,2.
- •Соотношения двойственности 3,4.
- •Соотношения двойственности 5,6. Следствия соотношения 6
- •Теоремы Фаркаша.
- •Двойственный симплекс-метод. Определения. Формула приращений.
- •Критерий оптимальности. Условие пустоты.
- •Итерация. Задача о диете.
- •Транспортная задача. Условие общего баланса. Условия дефицита и перепроизводства.
- •Особенности. Транспортная задача. Лемма 1. Следствия.
- •Лемма 2. Базисный план перевозок.
- •Базисный план. Метод минимального элемента.
- •Метод потенциалов транспортной задачи.
Выводы и следствия двухфазного симплекс-метода.
(1)
С учётом симплекс алгоритма можно сделать для задачи (1) следующий вывод.
Пусть требуется решить каноническую задачу. Применим к ней двухфазный симплекс-метод. Возможны следующие исходы:
а) , то есть ограничения задачи (1) несовместны, и у неё нет ни одного плана, а значит, нет оптимального плана (случай первой фазы);
б) у задачи будет построен – оптимальный базисный план (случаи 2 и 3 первой фазы и теорема 1 симплекс-метода);
в) будет доказана неограниченность целевой функции (случаи 2 и 3 первой фазы и выполнение теоремы 2 на второй фазе).
Других случаев для задачи (1) быть не может.
Следствие 1. Если у задачи (1) есть планы, то у неё обязательно есть и базисные планы.
Доказательство. Действительно, в этом случае возможен либо случай 2, либо случай 3 на первой фазе и оба они заканчиваются построением базисного плана.
Ч.т.д.
Следствие 2. Если у задачи (1) существует решение, то у неё обязательно будет и оптимальный базисный план.
Доказательство. Действительно, если не выполняется в случаях а) и в) вывода, то остаётся лишь случай б).
Ч.т.д.
Следствие 3. Для того чтобы у задачи (1) существовал оптимальный план необходимо и достаточно, чтобы её целевая функция была ограничена сверху на непустом множестве планов.
Доказательство. Необходимость. Если – оптимальный план задачи (1), то целевая функция ограничена сверху числом и множество планов задачи непустое.
Достаточность. Пусть множество задачи (1) непустое и известно, что на этом множестве целевая функция ограничена сверху некоторым числом. Тогда возможен лишь исход б) вывода, то есть у задачи существует оптимальный план.
Приведение задач к канонической форме. Табличная реализация симплекс-метода.
Определение. Две задачи оптимизации называться эквивалентными, если либо у них одинаковый оптимальный план, либо отсутствует решение по одной и той же причине. Соответствующие преобразования одной задачи в другую называется эквивалентными.
Теорема 4. Любую задачу линейного программирования можно свести к эквивалентной задаче в канонической форме.
Доказательство (конструктивное). Возможны следующие случаи не каноничности и их эквивалентного преобразования:
если в задаче целевая функция имеет вид: , то это эквивалентно , то есть эквивалентное преобразование состоит в умножении на (-1). Эквивалентность задач целевыми функциями и вытекает из определения максимума и минимума.
пусть среди основных ограничений имеется ограничение неравенства: , тогда оно эквивалентно паре (основному равенству и прямому ограничению):
,
где новая неотрицательная переменная, которая для каждого плана указывает, каково отклонение в нашем пространстве от числа . То есть для сведения неравенства к уравнению вводится дополнительная неотрицательная переменная, которая называется свободной или балансовой и она на каждом плане указывает, какой неотрицательной части не хватает до равенства в неравенстве. Если неравенство имеет вид: , то свободную переменную нужно вычесть:
пусть на переменную задачи линейного программирования не накладываются условия неотрицательности, то есть эта переменная может принимать и положительные, и отрицательные, и нулевые значения. Тогда совершаем замену:
(19)
то есть, представляем эту переменную в виде разности двух неотрицательных новых переменных. Так как любое число всегда представимо в виде разности двух неотрицательных чисел, то задачи эквивалентны.
Замечание. Если хотя бы в одном основном ограничении задачи, коэффициент при отличен от нуля, то можно вместо замены (19) исключить переменную из задачи: выразить её из этого основного ограничения через остальные и подставить в целевую функцию и оставшиеся основные ограничения.
Теорема доказана, так как других неканонических элементов в задачах линейного программирования быть не может.
Ч.т.д.
Производственная задача (20) (все основные ограничения – неравенства) называется задачей линейного программирования в нормальной форме и она эквивалентна канонической задаче (21)
, – вектор свободных переменных. Свободные не следует путать с искусственными переменными. Они имеют физический смысл.
– это неиспользованное количество -ого ресурса на производственном плане . У производственной задачи сразу строится начальный базисный план, а именно и, следовательно, для задачи в нормальной форме не требуется первая фаза.