Взаимно двойственные задачи линейного программирования
Рассмотрим формально две задачи I и II линейного программирования, представленные в табл. 3.1, абстрагируясь от содержательной интерпретации параметров, входящих в их экономико- математические модели.
Таблица 3.1
| Задача I (исходная) | Задача II (двойственная) |
 (3.1)
при ограничениях
  ,
 , (3.2)
……………………………,
 .
и условии неотрицательности
х1³0, х2³0,…, хn³0 (3.3)
Составить такой план выпуска продукции Х=(х1, х2,…, хn), при котором прибыль от реализации продукции будет максимальной при условии, что потребление ресурсов по каждому виду продукции не превзойдет имеющихся запасов.
|  (3.4)
при ограничениях
  ,
 , (3.5)
…………………………….,
 .
и условии неотрицательности
y1³0, y2³0,…, yn³0 (3.6)
Составить такой набор цен ресурсов Y=(y1, y2,…, yn), при котором общие затраты на ресурсы будут минимальными при условии, что затраты на ресурсы при производстве каждого вида продукции будет не менее прибыли от реализации этой продукции.
|
Обе задачи обладают следующими свойствами:
1. В одной задаче ищут максимум линейной функции, в другой — минимум.
2. Коэффициенты при переменных в линейной функции одной задачи являются свободными членами системы ограничений в другой.
3. Каждая из задач задана в стандартной форме, причем в задаче максимизации все неравенства вида «≤» а в задаче минимизации — все неравенства вида «≥».
4. Матрицы коэффициентов при переменных в системах ограничений обеих задач являются транспонированными друг к другу:
для задачи I А 
для задачи II А¢ 
5. Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой задаче.
6. Условия неотрицательности переменных имеются в обеих задачах.
Две задачи I и II линейного программирования, обладающие указанными свойствами, называются симметричными взаимно двойственными задачами. В дальнейшем для простоты будем называть их просто двойственными задачами.
Исходя из определения, можно предложить следующий алгоритм составления двойственной задачи.
1. Привести все неравенства системы ограничений исходной задачи к одному смыслу: если в исходной задаче ищут максимум линейной функции, то все неравенства системы ограничений привести к виду «≤», а если минимум — к виду «≥». Для этого неравенства, в которых данное требование не выполняется, умножить на (-1).
2. Составить расширенную матрицу системы А1, в которую включить матрицу коэффициентов при переменных А, столбец свободных членов системы ограничений и строку коэффициентов при переменных в линейной функции.
З. Найти матрицу А1′ , транспонированную к матрице А1.
4. Сформулировать двойственную задачу на основании полученной матрицы А1′ и условия неотрицательности переменных.
Дата добавления: 2016-04-19; просмотров: 1485;