Линейного программирования и их свойства

Рассмотрим формально две задачи I и II линейного программирования, представленные в табл. 4.1, абстрагируясь от содержательной интерпретации параметров, входящих в их экономико-математические модели. Обе задачи обладают следующими свойствами:

1. В одной задаче ищут максимум линейной функции, в другой - минимум.

2. Коэффициенты при переменных в линейной функции одной задачи являются свободными членами системы ограничений в другой.

3. Каждая из задач задана в стандартной форме, причем в задаче максимизации все неравенства вида « », а в задаче минимизации - все неравенства вида « ».

4. Матрицы коэффициентов при переменных, в системах ограничений обеих задач являются транспонированными друг к другу:

для задачи I ,

для задачи II .

5. Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой задаче.

6. Условия неотрицательности переменных имеются в обеих задачах.

Две задачи I и II линейного программирования, обладающие указанными свойствами, называются симметричными взаимно двойственными задачами. В дальнейшем для простоты будем называть их просто двойственными задачами.

Исходя из определения, можно предложить следующий алгоритм составления двойственной задачи.

1. Привести все неравенства системы ограничений исходной задачи к одному смыслу: если в исходной задаче ищут максимум линейной функции, то все неравенства системы ограничений привести к виду « » , а если минимум — к виду « ». Для этого неравенства, в которых данное требование не выполняется, умножить на - 1.

2. Составить расширенную матрицу системы , в которую включить матрицу коэффициентов при переменных А, столбец свободных членов системы ограничений и строку коэффициентов при переменных в линейной функции.

3. Найти матрицу , транспонированную к матрице .

4. Сформулировать двойственную задачу на основании полученной матрицы и условия неотрицательности переменных.

6.1 составить задачу, двойственную следующей задаче:

при ограничениях:

Решение. 1.Так как исходная задача на максимизацию, то приведем все неравенства системы ограничений к виду « », для чего обе части первого и четвертого неравенства умножим на -1. Получим

2. Составим расширенную матрицу системы

3. Найдем матрицу , транспортированную к А

4. Сформулируем двойственную задачу :

при ограничениях