Постановка и модель двойственной задачи, алгоритм ее составления. Методы решения с использованием двойственной симплекс-таблицы. Особенности теоремы теории двойственности и ее экономическое содержание: двойственность задач линейного программирования.
Аннотация к работе
Связь исходной и двойственной задач заключается, в частности, в том, что решение одной из них может быть получено непосредственно из решения другой. Интерес покупающей стороны заключается в том, чтобы заплатить за ресурсы как можно меньше, а интерес продающей стороны - в том, чтобы получить за ресурсы не меньше того, что она получила бы за реализованный готовый товар. Тогда, в так называемой двойственной модели, целевая функция будет описывать интерес покупающей стороны, система ограничений - интерес продающей стороны (необходимо оценить ресурсы, которые пошли бы на изготовление единицы продукции и стоимость этих ресурсов ограничить ценой реализованной единицы продукции). Сопоставим обе задачи: - первая - задача на максимум (z®max), вторая - на минимум (F®min); коэффициенты в целевых функциях и величины в правых частях неравенств при переходе из одной задачи в другую меняются местами (в первой задаче cj - коэффициенты целевой функции, во второй cj - свободные члены; в первой задаче bi - свободные члены, во второй bi - коэффициенты целевой функции);Обе модели записываются в двойственную симплекс-таблицу следующим образом (таблица 4): Таблица 4 - Двойственная симплексная таблица v1 v2 … vn F прежде чем составлять модель двойственной задачи, необходимо у исходной модели «выровнять» знаки, т.е. если целевая функция стремится к max, то все знаки в системе ограничений должны быть ?, а если к min, то ?. в центр двойственной симплекс-таблицы (таблицы 4) всегда ставится задача на max, вне зависимости от того какова целевая функция исходной задачи. В качестве основной теоремы двойственности выделяют следующую формулировку: если одна из взаимно двойственных задач имеет оптимальное решение, то и другая также имеет оптимальное решение, при этом соответствующие им оптимальные значения целевых функций равны (т.е. max z = min F). Кроме этого варианта возможны следующие взаимоисключающие случаи: - в одной из пары двойственных задач допустимое множество не пусто, а целевая функция на этом множестве не ограничена, то у другой задачи из этой пары будет пустое допустимое множество (т.е.
План
План
1. Постановка и модель двойственной задачи
2. Методы решения
3. Теоремы теории двойственности и ее экономическое содержание