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