Лекция 6. Двойственные задачи линейного программирования


Содержание лекционного занятия:

· Прямая задача

· Двойственная задача

Одним из центральных и наиболее значительных мест в теории линейного программирования является двойственность, которая состоит в том, что каждой исходной (прямой) задаче, в которой целевая функция стремится к максимуму (минимуму):

F = c1,x1,+с2х23х3+... + сnхnmax(min), (1)

система функциональных ограничений представляет собой систему неравенств:

(2)

система прямых ограничений также представляет собой систему неравенств:

(3)

соответствует двойственная задача, в которой:

· целевая функция стремится к минимуму (максимуму):

Z(y) = y1,b1, +y2b2+...+ ymbm →min(max) (4)

· система функциональных ограничений, представляет собой систему неравенств:

(5)

система прямых ограничений также представляет со­бой систему неравенств:

у1³0,У2³0,Уз³0...Уm³0. (6)

Общим для прямой и двойственной задач является то, что в каждой из них отыскивается экстремум линейной функции, а искомые переменные должны удовлетворять системам функциональных и прямых ограничений. Кроме того, в обеих задачах используются одни и те же парамет­ры: элементы матрицы А, вектор В, вектор С.

Отличие между прямой и двойственной задачей состоит в том, что в прямой задаче определяются значения n пере­менных x1,x2,...,xn, а в двойственной — m переменных: y1, y2,…, ym в исходной задаче ищется максимум, а в двой­ственной — минимум целевой функции, знаки неравенств в этих задачах противоположны, компоненты вектора огра­ничений в одной из задач являются коэффициентами при переменных в целевой функции другой задачи.

Чтобы к заданной прямой задаче сформировать двойст­венную, целесообразно пользоваться определенной систе­мой формальных правил.

1. Число переменных в двойственной задаче равно коли­честву функциональных ограничений в прямой задаче (т.е., если в прямой задаче вектор переменных записывается, как n-мерный вектор-столбец, то в двойственной задаче вектор переменных будет представлять собой m-мерный вектор — строку и наоборот).

2. Если прямая задача ставится как задача максимизации, то двойственная — как задача минимизации и наоборот.

3. Компоненты вектора функциональных ограничений В=(bi,b2,...bm) в прямой задаче становятся коэффициентами целевой функции в двойственной задаче.

Применение этих трех правил позволяет сформировать целевую функцию двойственной задачи:

Z(y) = y1 b1 + у2b2 +...+ yrabm → min .


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

5. Знак неравенств функциональных ограничений в прямой задаче меняется на обратный в двойственной, т.е. « £» на «³ ».

6. Коэффициенты целевой функции прямой задачи c1,c2,...,cn, становятся вектором ограничений в двойственной задаче.

Применяя правила 4, 6 мы можем сформировать систему функциональных ограничений обратной задачи:

7. Прямые ограничения на неотрицательность перемен­ных для двойственной задачи сохраняются.

У1³0,у2³0,у3³0...уm³0

Таким образом, исходную и двойственную к ней задачу можно представить следующим образом:

Прямая и двойственная задача, построенная в соответствии с рассмотренными выше правилами, называются сим­метричными взаимодвойственными задачами.

Если к двойственной задаче снова построить двойствен­ную задачу, то получим прямую (т.е. исходную) задачу. Необходимо отметить, что ни одна из двойственных задач не является основной, так как если поставлена одна из за­дач, то другая может быть сформулирована как двойствен­ная и каждая из них является двойственной по отношению к другой.

Вопросы для самоконтроля:

1.Понятие о двойственных задачах ЛП.

2.Теорема двойственности.

Рекомендуемая литература:

1.Измаилов А.Ф., Солодов М.В. Численные методы оптимизации. М.: Физматлит, 2003.

2.Банди Б. Методы оптимизации. Вводный курс. М.: Радио и связь, 1988.