Литература
Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов вузов. М.: Высш. шк., 1986. с.47-55.
Исследование операций в экономике: Учебн. пособ. Для вузов /Н.Ш.Кремер, Б.А. Путко и др.; Под. ред. проф. Н.Ш.Кремера. М.: Банки и биржи, ЮНИТИ, 1997. 94-98.
Деордица Ю.С., Нефедов Ю.М. Исследование операций в планировании и управлении: Учебн. пособ. К.: Вища школа, 1991. с.36-39.
Зайченко Ю.П., Шумилова С.А. Исследование операций: сборник задач,2-е изд. К.: Вища школа, 1990.с.20-23
ЗАДАЧА 3
Построить задачу двойственную исходной и найти решение для пары двойственных задач.
Рекомендации к выполнению задания
Каждой задаче линейного программирования соответствует другая задача, называемая двойственной или сопряженной по отношению к исходной. Теория двойственности полезна для проведения качественных исследований задач линейного программирования.
Взаимно двойственные задачи линейного программирования обладают следующими свойствами:
В одной задаче ищут максимум линейной функции, в другой —минимум.
Коэффициенты при переменных в линейной функции одной задачи являются свободными членами системы ограничений в другой.
Каждая из задач задана в стандартной форме, причем, в задаче максимизации все неравенства вида»», а в задаче минимизации — все неравенства вида ””.
Матрицы коэффициентов при переменных в системах ограничений обоих задач являются транспонированными друг к другу
Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой.
Условием неотрицательности обладают переменные двойственной задачи, которым соответствует ограничение вида «» исходной задачи. Если же переменной двойственной задачи соответствует ограничение вида “=” исходной задачи, то эта переменная может принимать как отрицательные, так и положительные значения.
ПРИМЕР построения двойственной задачи.
Составить задачу, двойственную следующей задаче:
при ограничениях:
Решение.
Так как исходная задача на максимизацию, то приведем все неравенства системы ограничений к виду «», для чего обе части первого и четвертого неравенства умножим на -1. Получим
Составим расширенную матрицу системы:
. Найдем матрицу А1’ , транспонированную к А
Сформулируем двойственную задачу:
при ограничениях
Перейдём в данной задаче от стремления к минимуму к стремлению к максимуму:
при ограничениях
Построим псевдоплан в канонической форме:
Составим первую симплекс таблицу:
|
у1 |
у2 |
у3 |
у4 |
у5 |
у6 |
Ві |
у5 |
2 |
1 |
-1 |
1 |
1 |
0 |
1 |
у6 |
-1 |
-4 |
1 |
1 |
0 |
1 |
-2 |
Z |
-1 |
24 |
3 |
-5 |
0 |
0 |
0 |