Теоремы двойственности
Теоремы двойственности позволяют установить взаимосвязь между оптимальными решениями пары двойственных задач: можно либо найти оптимальное решение другой задачи не решая ее, либо установить его отсутствие.
Возможны следующие случаи:
обе задачи из пары двойственных имеют оптимальные решения;
одна из задач не имеет решения ввиду неограниченности целевой функции, а другая – ввиду несовместности системы ограничений.
Первая теорема двойственности.
Для двойственных задач линейного программирования имеет место один из взаимоисключающих случаев:
В прямой и двойственной задачах имеются оптимальные решения, при этом значения целевых функций на оптимальных решениях совпадают:
В прямой задаче допустимое множество не пусто, а целевая функция на этом множестве не ограничена сверху. При этом у двойственной задачи будет пустое допустимое множество.
В двойственной задаче допустимое множество не пусто, а целевая функция на этом множестве не ограничена снизу. При этом у прямой задачи допустимое множество оказывается пустым.
Обе из рассматриваемых задач имеют пустые допустимые множества.
Вторая теорема двойственности (теорема о дополняющей нежесткости)
Пусть
–
допустимое решение прямой задачи, а
–
допустимое решение двойственной задачи.
Для того, чтобы они были оптимальными
решениями соответствующих взаимодвойственных
задач, необходимо и достаточно, чтобы
выполнялись следующие соотношения:
Эти условия устанавливают связь между оптимальными значениями прямой и двойственной задач и позволяют, зная решение одной из них, находить решение другой задачи.
Теорема об оценках.
Значения
переменных
в оптимальном решении двойственной
задачи представляют собой оценки влияния
свободных членов
системы ограничений – неравенств прямой
задачи на величину
:
.
Диапазон изменения компонент вектора , в котором сохраняется оптимальный базис, называется областью устойчивости оптимальных оценок.
Экономический
смысл первой теоремы двойственности
следующий. План производства
и набор ресурсов
оказываются оптимальными тогда и только
тогда, когда прибыль от реализации
продукции, определенная при известных
заранее ценах продукции
,
равна затратам на ресурсы по «внутренним»
(определяемым только из решения задачи)
ценам ресурсов
.
Для всех других планов прибыль от
продукции всегда меньше или равна
стоимости затраченных ресурсов
,
т.е. ценность выпущенной продукции не
превосходит суммарной оценки затраченных
ресурсов. Значит величина
характеризует производственные потери
в зависимости от рассмотренной
производственной программы и выбранных
оценок ресурсов.
Контрольные вопросы к теме
Понятие математического моделирования.
Задача линейного программирования и ее каноническая форма.
Целевая функция и система ограничений.
Понятие выпуклой линейной комбинации.
Базисное, опорное и оптимальное решения.
Двойственная задача линейного программирования и объективно обусловленные оценки.
Экзаменационные вопросы
Числа и числовые множества. Счетность множеств. Границы и грани.
Отображения.
Перестановки, сочетания. Бином Ньютона.
Комплексные числа. Алгебраическая форма, геометрическое представление, тригонометрическая форма.
Формулы Муавра, Извлечение корня из компл. числа.
Многочлены. Корни многочлена. Разложение многочлена на множители.
Рациональные функции. Представление в виде суммы простейших.
Метод неопределенных коэффициентов.
Матрицы.
Операции над матрицами. Обратная матрица.
Определители, их вычисление и свойства.
Системы линейных уравнений. Матричная запись. Метод Крамера.
Системы линейных уравнений. Метод Гаусса.
Векторы. Базис. Скалярное произведение.
Векторное произведение.
Прямая на плоскости. Способы задания прямой.
Общее уравнение прямой. Линейные неравенства.
Нормальное уравнение прямой. Отклонение точки от прямой.
Плоскость. Способы задания плоскости.
Общее уравнение плоскости. Нормальное уравнение. Отклонение точки от плоскости.
Эллипс. Гипербола. Парабола.
Параллельный перенос и поворот системы координат.
Упрощение уравнения второй степени.