30 .Двойственная задача линейного программирования. Структура и свойства двойственной задачи.

Структура и свойства двойственной задачи. Почти всякую ЗЛП можно рассматривать как экономическую задачу о распределении ресурсов b₁, b₂,...,b_m между различными. Потребителями, например, между некоторыми технологическими процессами A₁, A₂,...,A_n . Любое Рассмотрим пример. Завод производит три вида продукции x₁, x₂,x₃, каждый из которых требует затрат времени на обработку на токарном, фрезерном и сверлильном станках. Количество машинного времени для каждого из станков ограниченно. Пусть C₁, C₂,C₃ - прибыль от реализации единицы соответствующего вида продукции. Требуется определить, какое количество каждого вида продукции необходимо производить в течение заданного интервала времени, чтобы получить максимальную прибыль.

Формально задача записывается так: найти

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

где a_1j, a_2j, a_3j,- время, необходимое для обработки единицы j-го вида продукции соответственно на токарном, фрезерном и сверлильном станках (j=1,2,3); b₁, b₂, b₃ - ресурс машинного времени соответственно для токарного, фрезерного и сверлильного станков. Сформулированная задача является прямой ЗЛП.

Рассмотрим далее задачу в несколько иной постановке. Обозначим через U₁, U₂, U₃ - цену единицы времени работы на токарном , фрезерном и сверлильном станках соответственно, тогда a₁₁U₁+a₁₂U₂+a₁₃U₃ можно трактовать как расходы на изготовление единицы продукции первого вида, a₂₁U₁+a₂₂U₂+a₂₃U₃ - расходы на изготовление единицы продукции второго вида, a₃₁U₁+a₃₂U₂+a₃₃U₃ - расходы на изготовление единицы продукции третьего вида.

Для величин расходов выполняются следующие соотношения:

(7)

Учитывая, что b₁, b₂,b₃ - использованный ресурс машинного времени для каждого из станков, тогда b₁U₁+b₂U₂+b₃U₃- суммарные расходы на производство.

Требуется найти такие U₁, U₂, U₃, удовлетворяющие условиям (7), при которых минимизируются суммарные расходы на производство. Таким образом, целевую функцию можно записать в виде

(8)

причем U₁, U₂, U₃ 0,

Задачу (8) с ограничениями (7) называют двойственной задачей по отношению к прямой, сформулированной ранее.

31 .Двойственная задача линейного программирования. Соотношение прямой и двойственной задачи.

Соотношение прямой и двойственной задач. Между прямой и двойственной задачами имеет место взаимно однозначное отношение. Имея прямую задачу, всегда можно перейти к двойственной и наоборот. Данное отношение находит выражение в виде следующих правил:

1) если прямая задача является задачей максимизации, то двойственная будет задачей минимизации и наоборот;

2) коэффициенты целевой функции прямой задачи C₁, C₂, C₃ становятся свободными членами ограничений двойственной задачи;

3) свободные члены ограничений прямой задачи b₁, b₂, b₃ становятся коэффициентами целевой функции двойственной задачи;

4) матрицу ограничений двойственной задачи получают транспонированием матрицы ограничений прямой задачи;

5) знаки неравенств в ограничениях изменяются на обратные;

6) число ограничений прямой задачи равно числу переменных двойственной задачи, а число ограничений двойственной задачи равно числу переменных прямой задачи.

Переменные U₁, U₂, U₃ двойственной задачи называют „теневыми ценами ".

Двойственную задачу выгоднее решать, чем исходную прямую, если в прямой задаче при малом количестве переменных (m>n) имеется большое количество ограничений.

Запишем обе задачи в матричном виде.

Прямая задача. Найти при .

Двойственная задача. Найти при .

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

Теорема 1. Если и - допустимые решения прямой и двойственной задач, т. е. если и , то , т. е. значения целевой функции прямой задачи никогда не превышают значений целевой функции двойственной задачи.

Теорема 2. Если и - допустимые решения прямой и двойственной задач и если ,то и - оптимальные решения этих задач.

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

И, наконец, главная сложность, возникающая при решении задач минимизации, - это выбор первоначального базиса. Дело в том, что при решении задач минимизации область допустимых значений ограничивается снизу, т.е. ограничения имеют вид .