- •§2. Математические модели и методы их расчета
- •2.1. Понятие операционного исследования
- •Основные этапы операционного исследования:
- •2.2. Принципы построения математических моделей
- •2.3. Оптимизационные модели
- •§3. Постановка задачи линейного программирования
- •3.1. Примеры задач линейного программирования
- •3.2 Общая формулировка задачи линейного программирования
- •3.3 Каноническая форма задачи линейного программирования
- •§4. Графический метод решения задач лп
- •§ 5. Метод последовательного уточнения плана (симплекс-метод)
- •Алгоритм симплексного метода задачи на максимум
- •§6. Прямая и двойственная задача линейного программирования.
- •6.1 Постановка задачи
- •Правила построения двойственной задачи по имеемой прямой задаче:
- •6.2 Геометрическая интерпретация двойственных задач.
- •6.3. Основные теоремы двойственности
6.2 Геометрическая интерпретация двойственных задач.
Если число переменных в прямой и двойственной задачах, образующих данную пару, равно двум, то, используя геометрическую интерпретацию задачи линейного программирования, можно легко найти решение данной пары задач.
При этом имеет место один из следующих трех взаимно исключающих друг друга случаев: 1) обе задачи имеют планы; 2) планы имеет только одна задача; 3) для каждой задачи двойственной пары множество планов пусто.
Пример.
Для задачи, состоящей в определении максимального значения функции при условиях
составить двойственную задачу и найти решение обеих задач.
Решение.
Прямая задача |
Двойственная задача |
Целевая функция |
|
|
|
Функциональные ограничения |
|
|
|
Прямые ограничения |
|
|
|
Решение |
|
Х=(2, 6); |
Y=(1; 4); |
6.3. Основные теоремы двойственности
Первая теорема двойственности:
Если одна из двойственных задач имеет оптимальное решение, то и другая задача имеет оптимальное решение, причем экстремальные значения целевых функций совпадают F(X)=F'(Y). Если одна из двойственных задач неразрешима вследствие неограниченности целевой функции на множестве допустимых решений, то система ограничений другой задачи противоречива.
Экономическое содержание первой теоремы двойственности: если задача определения оптимального плана, максимизирующего выпуск продукции, разрешима, то разрешима и задача определения и оценок ресурсов, при этом полная стоимость продукта, полученного в результате реализации оптимального плана, совпадает с суммарной оценкой ресурсов. Совпадения, значений целевых функций для соответствующих решений пары двойственных задач достаточно для того, чтобы эти решения были оптимальными. Это значит, что план производства и вектор оценок ресурсов являются оптимальными только тогда, когда полная стоимость произведенной продукции и суммарная оценка ресурсов совпадает.
Оценки выступают как инструмент сбалансирования затрат и результатов. Двойственные оценки обладают тем свойством, что они гарантируют рентабельность оптимального плана, т.е. равенство общей стоимости продукции и ресурсов обуславливает убыточность всякого другого плана отличающегося от оптимального. Двойственные оценки позволяют сопоставлять и сбалансировать затраты и результаты производства.
Вторая теорема двойственности:
Для того чтобы план Х и Y пары двойственных задач были оптимальными, необходимо и достаточно выполнение условий:
Эти условия называются условиями дополняющей нежесткости. Из них следует, что если какое-либо неравенство системы ограничений в одной из задач не обращается в строгое равенство оптимальным планом этой задачи, то соответствующий элемент оптимального плана двойственной задачи должен равняться нулю. Если какой-либо элемент оптимального плана одной из задач положителен, то соответствующее ограничение в двойственной задаче её оптимальным планом должно обращаться в строгое равенство, т.е.
если bj, то ;
если 0, то .
Аналогично,
если
если 0 то
Экономически это означает, что если по некоторому оптимальному плану X*= производства расход j-го ресурса меньше его запаса bj, то в оптимальном плане соответствующая двойственная оценка единицы этого ресурса равна нулю. Если же в некотором оптимальном плане оценок его j-й элемент больше нуля, то в оптимальном плане производства расход соответствующего ресурса равен его запасу. Отсюда следует вывод: двойственные оценки могут служить мерой дефицитности ресурсов. Дефицитный ресурс, т.е. полностью используемый по оптимальному плану производства, имеет положительную оценку, а избыточный ресурс, т.е. не используемый полностью имеет нулевую оценку.
Третья теорема двойственности:
Двойственные оценки показывают приращение функции цели, вызванное малым изменением свободного члена соответствующего ограничения задачи линейного программирования, т.е.
В последнем выражении дифференциалы заменим приращениями. Тогда получим выражение:
,
если , тогда , Экономическое содержание третьей теоремы двойственности: двойственная оценка численно равна изменению целевой функции при изменении соответствующего ресурса на единицу. Двойственные оценки yj часто называются скрытыми теневыми или маргинальными оценками ресурсов.
Следствия. Объективно обусловленные оценки выступают как мера дефицитности ресурсов. Если объективно обусловленная оценка больше нуля, то этот ресурс полностью без остатка расходуется в процессе выполнения оптимального плана. Если в оптимальном плане какой-то ресурс используется не полностью, то его объективно обусловленная оценка обязательно равна нулю.
Связь между задачами двойственной пары в том, что, решая симплексным методом одну из них, автоматически получаем решение другой. Для этого достаточно воспользоваться соответствием переменных прямой и двойственной задач в последней симплекс-таблице
-
x1
x2
…
xn
S1
S2
…
Sm
S1
S2
…
Sm
y1
y2
…
ym