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




 

В задаче 1 имеется n-переменных и m- ограничений типа (4). В задаче 1* имеется m –переменных и n-ограничений типа (8). Это значит, что каждой переменной в задаче 1 соответствует ограничение в задаче 1* и каждому ограничению в задаче 1 соответствует переменная в задаче 1*.

В задаче 1 требуется максимизировать целевую функцию на множестве заданных ограничений больше 0. В задаче 1* требуется минимизировать целевую функцию на множестве заданных ограничений меньше 0.

Коэффициенты сj линейной функции (1) в задаче 1 являются свободными членами ограничений (8) задачи 1*, свободные члены bi ограничений (4) в задаче 1 являются коэффициентами линейной функции (5) задачи 1*.

Коэффициенты при неизвестных аij в задачах 1 и 1* одни и те же, но матрицы из этих коэффициентов транспонированы по отношению друг к другу.

В задаче 1 все неравенства типа ³, а в задаче 1* все неравенства типа £.

Если на переменную задачи 1 налагается условие неотрицательности, то соответствующее ограничение в двойственной задаче является неравенством, а если условия неотрицательности на переменную нет, то соответствующее ограничение в задаче 1* является уравнением. И наоборот.

 

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

Пример 1. Записать двойственную задачу к следующей задаче линейного программирования. ЗАДАЧА1. Найти х = (х1, х2, х3, х4), удовлетворяющий условиям: Решение. Заметим, что т.е все переменные связаны условием неотрицательности, и все ограничения выполняются как неравенства. Двойственная задача имеет вид: ЗАДАЧА 1* Найти удовлетворяющие условиям:

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

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

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

 

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

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

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

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

(10)

(11)

 

 

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

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

хj ³0 для jÎJ2

(12)

 

Суммируя полученные соотношения, получим с учетом того, что (13)

 

 

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

Доказательство (продолжение). Имеем:

yi 0 для iÎI2

(14)

(15)

Правые части в соотношени­ях (13) и (15) отличаются лишь порядком суммирова­ния и, следовательно, равны между собой, т.е. выполняется µ(x) £ (у) (9). Для достижения равенства в (9), очевидно, не­обходимо и достаточно, чтобы достигались равенства во всех неравенствах (13) и (15). Последнее эквива­лентно выполнению соотношений (10) и (11) ▄

Признак оптимальности в краткой форме

Для оптимальности допустимого вектора х= (х12, …хn,) в задаче 1 достаточно существования допустимого вектора y= (y1,y2,…..yn) в задаче 1*, удовлетворяющего условию

m (х) = n (у)(16)

Тогда допустимый вектор y= (y1,y2,…..yn) также является оптимальным в задаче 1*.

 

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

Пусть вектор х допустимый и существует допустимый вектор у такой, что справедливо (16). Покажем, вектор х оптимальный.

Рассмотрим некоторый другой оптимальный вектор х′ в задаче 1 (х′≠х), тогда имеем пару векторов х′ и у. Для этой пары допустимых векторов справедлива лемма 1, т. е. m (х′) ≤ n (у) =m (хm (х′) ≤m (х). Отсюда следует что х – оптимальный вектор.

Покажем теперь, что вектор у также является оптимальным.

Рассмотрим некоторый другой оптимальный вектор у′ в задаче 1 (у′≠у), тогда имеем пару векторов х и у′. Для этой пары допустимых векторов справедливо лемма 1, т. е. n(у′)≥m(х)= n(у) и n(у)≤ n(у′). Отсюда следует что у – оптимальный вектор.▄



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-04-02 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: