[Список тем] [Вступление к этой теме] страницы темы: [1] [2] [3] [4]
Рассмотрим формально две задачи I и II линейного программирования,
представленные в табл. 6.1, абстрагируясь от содержательной интерпретации
параметров, входящих в их экономико-математические модели. Обе задачи обладают
следующими свойствами:
1. В одной задаче ищут максимум линейной функции, в другой - минимум.
2. Коэффициенты при переменных в линейной функции одной задачи являются
свободными членами системы ограничений в другой.
3. Каждая из задач задана в стандартной форме, причем в задаче максимизации
все неравенства вида "≤", а в задаче минимизации - все неравенства
вида "≥".
4. Матрицы коэффициентов при переменных в системах ограничений обеих задач
являются транспонированными друг к другу:
для задачи I A =
для задачи II А' =
5. Число неравенств в системе ограничений одной задачи совпадает с числом
переменных в другой задаче.
6. Условия неотрицательности переменных имеются в обеих задачах.
Две задачи I и II линейного программирования, обладающие указанными
свойствами, называются симметричными взаимно двойственными задачами. В дальнейшем для простоты будем называть их просто двойственными задачами.
Исходя из определения, можно предложить следующий алгоритм составления
двойственной задачи.
1. Привести все неравенства системы ограничений исходной задачи к одному
смыслу: если в исходной задаче ищут максимум линейной функции, то все
неравенства системы ограничений привести к виду
"≤", а если минимум - к виду
"≥". Для этого неравенства, в которых
данное требование не выполняется, умножить на -1.
2. Составить расширенную матрицу системы А1, в
которую включить матрицу коэффициентов при переменных А, столбец
свободных членов системы ограничений и строку коэффициентов при переменных в
линейной функции.
3. Найти матрицу А'1, транспонированную к
матрице А1.
4. Сформулировать двойственную задачу на основании полученной матрицы
A'1 и условия неотрицательности переменных.
[Список тем] [Вступление к этой теме] страницы темы: [1] [2] [3] [4] [В начало страницы]