- •Глава 1. Линейное программирование 3
- •Глава 2. Транспортная задача линейного программирования (тз) 68
- •Глава 3. Динамическое программирование 98
- •Глава 1. Линейное программирование
- •1.1. Математическая модель задачи линейного программирования
- •1.2. Формы записи задач линейного программирования
- •Рассмотрим приемы, позволяющие переходить от одной формы записи задачи к другой
- •1.3. Геометрическая интерпретация и графический метод решения задач линейного программирования с двумя переменными
- •Алгоритм графического метода решения злп с двумя переменными
- •1.4. Графический метод решения задач линейного программирования сnпеременными
- •1.5. Симплексный метод решения задач линейного программирования
- •Алгоритм решения злп симплексным методом
- •Нахождение начального опорного плана злп ( )
- •Нахождение начального опорного плана злп методом искусственного базиса
- •Нахождение начального опорного плана злп методом Жордановых исключений
- •Шаг Жордановых исключений осуществляется по следующим правилам:
- •Исследование на оптимальность опорного плана при решении злп на
- •Переход к новому опорному плану
- •1.6. Двойственные задачи линейного программирования
- •Правила построения двойственной задачи.
- •Глава 2. Транспортная задача линейного программирования (тз)
- •2.1. Математическая модель транспортной задачи
- •Закрытая и открытая модели транспортной задачи
- •2.2. Решение транспортной задачи
- •Алгоритм решения транспортной задачи
- •Нахождение начального опорного плана методом «минимального элемента»
- •Нахождение начального опорного плана методом «северо-западного угла»
- •Нахождение начального опорного плана методом Фогеля
- •Проверка на оптимальность невырожденного опорного плана методом потенциалов
- •Переход к новому опорному плану
- •Цикл пересчета
- •Глава 3. Динамическое программирование
- •3.1. Задача оптимального распределения ресурсов
- •I этап. Условная оптимизация.
- •II этап. Безусловная оптимизация.
- •3.2. Задача об оптимальной стратегии замены оборудования
- •I этап. Условная оптимизация.
- •II этап. Безусловная оптимизация.
- •Список использованной литературы
1.6. Двойственные задачи линейного программирования
С каждой ЗЛП, называемой прямой или исходной, тесно связана другая ЗЛП, называемая двойственной. При этом указанные задачи будут образовывать пару взаимно двойственных задач. Решая одну из них, можно найти решение и второй задачи.
Пара двойственных ЗЛП в симметричной форме имеет следующий вид:
прямая задача
|
двойственная задача
|
Рассмотренная пара взаимно двойственных задач может быть экономически интерпретирована, например, так.
Прямая задача: сколько продукции j-го вида надо произвести, чтобы при заданных стоимостях единицы продукции, объемах имеющихся ресурсови нормах расходовмаксимизировать выпуск продукции в стоимостном выражении?
Двойственная задача: какова должна быть оценка единицы каждого из ресурсов , чтобы при заданных стоимостях единицы продукции, объемах имеющихся ресурсови нормах расходовминимизировать общую оценку затрат на все ресурсы?
Чтобы из решения прямой задачи получить решение двойственной задачи нужно записать обе задачи в канонической форме:
прямая задача
|
двойственная задача
|
Между переменными двойственных задач существует следующее соответствие:
Если в оптимальном плане прямой задачи переменная равна нулю, то соответствующая ей переменная двойственной задачи отлична от нуля. Значения целевых функций двойственных задач совпадают, т.е. .
При решении прямой задачи графическим методом для нахождения оптимального плана двойственной задачи необходимо в системе ограничений канонической формы двойственной задачи оставить отличные от нуля переменные и решить ее аналитически.
При решении прямой задачи симплексным методом для нахождения оптимального плана двойственной задачи необходимо воспользоваться симплексной таблицей, в которой записан оптимальный план прямой задачи. Двойственные переменные, соответствующие базисным переменным прямой задачи будут равны нулю, а соответствующие свободным переменным – будут равны абсолютной величине оценок этих столбцов.
Если прямая задача не имеет решения, то и двойственная ей тоже не имеет решения.
Пример 1.23
Составить задачу, двойственную к ЗЛП, рассмотренной в примере 1.3. Дать экономическую интерпретацию прямой и двойственной задач. Из решения прямой задачи (пример 1.6) найти решение двойственной задачи.
Решение
прямая задача ;
|
двойственная задача ;
|
Экономическая интерпретация.
Прямая задача: сколько единиц продукции Пj надо произвести, чтобы при заданной прибыли от единицы продукции, объемах имеющихся ресурсов и нормах расходов максимизировать прибыль от всей выпущенной продукции?
Двойственная задача: какова должна быть оценка единицы каждого из ресурсов , чтобы при заданной прибыли от единицы продукции, объемах имеющихся ресурсов и нормах расходов минимизировать общую оценку затрат на все ресурсы?
В примере 1.6 было получено решение прямой задачи графическим методом. Это ,.
Для нахождения решения двойственной задачи запишем обе задачи в канонической форме:
прямая задача ;
|
двойственная задача ;
|
Между переменными двойственных задач существует следующее соответствие:
Определим из канонической формы прямой задачи, какие переменные равны нулю в оптимальном плане и из приведенного соответствия определим отличные от нуля двойственные переменные. Так
,
,
,
,
.
Для нахождения отличных от нуля двойственных переменных ирешим систему уравнений, полученную из системы ограничений канонической формы двойственной задачи:
Откуда . Таким образом,, или для двойственной задачи в симметричной форме. Причем.
Оценки единицы каждого из ресурсов определяют дефицитность используемых ресурсов и показывают, насколько увеличится целевая функция при увеличении соответствующего ресурса на единицу.
Так как иотличны от нуля, то второй и третий ресурсы (сырье и электроэнергия) являются дефицитными. При этом, следовательно, наиболее дефицитным является второй ресурс (сырье). Поскольку, то ресурс первого вида (время работы оборудования) является избыточным. При увеличении сырья на 1 кг прибыль от всей выпущенной продукции увеличится на 3 руб., а при увеличении электроэнергии на 1 кВтч. прибыль от всей выпущенной продукции увеличится на 1 руб.