Пример составления двойственной задачи ЛП

Пример 2. ЗАДАЧА 1. Требуется мак­симизировать линейную функцию =2x1 — х2 + Зх3 + х4 — 5x5 на множестве пятимерных векторов х = (х1, х2, х3, х4, х5), удовлетворяющих условиям , , Зх1 + 2х2 - 5х3 + х5 - 70, 3х2 - 4х3 - 2х4 + 1 = 0, 2х1 + 2х3 - 3х4 + х5 0.

Решение. ЗАДАЧА 1^* Требует­ся минимизировать линейную функцию на множестве трехмерных векторов, удовлетворяющих условиям , , 3y1 + 2y3 + 2 0, 2y1 + 3y2 -1 = 0, - 5y1 - 4y2 + 2y3 + 3 0, - 2y2 - 3y3 +1 0, y1 + y3 - 5 = 0.

Связь между задачами 1 и 1^*

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

Для любых допустимых векторов х и у в задачах 1 и 1* выполняются неравенства

µ(x) £(у), (9)

причем (9) выполняется как равенство в том и только в том случае, если справедливы следующие соотношения:

(10)

(11)

Связь между задачами 1 и 1^*

Доказательство. По условию – допустимый вектор в задаче 1.

По условию – допустимый вектор в задаче 1*.

µ (x) £ v (у)

Связь между задачами 1 и 1^*(продолжение)

Доказательство.

Полагаем: ,

Аналогично,

▄

Дата добавления: 2014-01-13