Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






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




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

Двойственная задача – это вспомогательная задача линейного программирования, получаемая с помощью определённых правил непосредственно из условий исходной.

Сформулируем правила построения двойственных задач:

1. Если целевая функция f исходной задачи максимизируется, то целевая функция z двойственной – минимизируется и наоборот.

2. Количество ограничений (m) исходной задачи равно количеству переменных двойственной, а количество переменных (n) исходной равно количеству ограничений двойственной. Переменные двойственной задачи обозначим через yi (i = 1, m).

3. Поскольку переменные исходной задачи связаны с ограничениями двойственной, каждой переменной xj >=0 соответствует в двойственной задаче ограничение вида «<=» (z→max) или «>=» (z→min), и наоборот.

4. Каждой переменной xj, не ограниченной по знаку, соответствует ограничение вида «=» двойственной задачи, и наоборот.

5. Свободные члены ограничений исходной задачи bi (I = 1, m) в двойственной являются коэффициентами при переменных yi (I = 1, m) в целевой функции, а коэффициенты cj (j = 1, n) при переменных xj (j = 1, n) в целевой функции исходной задачи являются свободными членами ограничений двойственной.

6. Матрица A коэффициентов при неизвестных в ограничениях исходной задачи в двойственной транспонируется (Aт ).

 

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

 

f = c1x1 + c2x2 +…+ cnxn → max;

 

a11x1 + a12x2 +…+ a1nxn <= b1,

a21x1 + a22x2 +…+ a2nxn <= b2,

……………………………..

am1x1 + am2x2 +…+ amnxn <= bm,

 

xj >= 0 (j= 1, n).

 

Двойственная к этой задаче будет иметь вид:

z = b1y1 + b2y2 +…+ bmym→min;

a11y1 + a21y2 +…+ am1ym >= c1,

a12y1 + a22y2 +…+ am2ym >=c2,

……………………………..

a1ny1 + a2ny2 +…+ amnym >= cn,

yi >= 0 (i = 1, m).

 

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

В таблице 5 приведены частные виды исходных задач линейного программирования в матричном виде и соответствующие им двойственные задачи. Через Y = (y1, y2,…, ym) обозначена матрица-строка неизвестных двойственной задачи. Матрица-строка Y умножается слева на матрицу-столбец B (в целевой функции) и матрицу A (в ограничениях) исходя из правил умножения двух матриц, а также правил построения двойственных задач (в частности, в двойственной задаче матрица коэффициентов при неизвестных в ограничениях должна быть транспонированной).



 

Исходная задача Двойственная задача
f = CX →max AX<= B X>= 0 z = YB →min YA>= C Y>= 0   Симметричные задачи
f = CX →min AX>= B X>= 0 z = YB →max YA<= C Y>= 0  
f = CX →max AX= B X>= 0 z = YB →min YA>= C   Несимметричные задачи
f = CX →min AX= B X>= 0 z = YB →max YA<= C  

Таблица 5. Правила формирования двойственных задач

Первые две пары взаимно двойственных задач в таблице называются симметричными, вторые две – несимметричными из-за наличия ограничений вида «=».

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

 

Пример 1. Построить задачу, двойственную к данной:

f = x1 –x2 →max;

x1 – x2 <= 1,

x1 – x2 >= 0,

x1 >= 0, x2 >= 0.

 

Чтобы построить двойственную задачу, исходную необходимо привести к форме (1) путем умножения обеих частей второго ограничения на (-1). После этого преобразования исходная задача примет вид:

 

f = x1 –x2 →max;

 
 


x1 – x2 <= 1,

- x1 + x2 >= 0,

 

x1 >= 0, x2 >= 0.



 

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

 

z = y1 →min;

y1 – y2 >= 1,

- y1 + y2 >= -1,

y1 >= 0, y2 >= 0.

Пример 2. Построить задачу, двойственную к данной:

 

f = 7x1 + 6x2 + 3x3 – x4 →min;

2x1 – x2 + 2x3 – 3x4 >= 12,

-x1 + 2x2 – x3 + x4 <= 10,

3x1 + 5x2 + 4x4 = 7,

x2 >= 0, x3 >= 0.

Для построения двойственной задачи воспользуемся формулами (2), (4) и преобразуем данную задачу путем умножения обеих частей второго неравенства на (-1). Тогда исходная задача будет иметь вид:

f = 7x1 + 6x2 + 3x3 – x4 →min;

 

2x1 – x2 + 2x3 – 3x4 >= 12,

x1 - 2x2 + x3 - x4 <= -10,

3x1 + 5x2 + 4x4 = 7,

 

x2 >= 0, x3 >= 0.

 

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

 

z = 12y1 – 10y2 + 7y3 →max;

2y1 + y2 + 3y3 = 7,

-y1 – 2y2 + 5y3 <= 6,

2y1 + y2 <= 3,

-3y1 – y2 + 4y3 = -1,

 

y1 >= 0, y2 >= 0.

 

Используя пример 2, поясним некоторые правила построения двойственных задач. Поскольку количество ограничений исходной задачи m = 3, двойственная задача должна иметь три переменные: y1, y2, y3. Количество переменных исходной задачи n = 4, поэтому двойственная должна иметь четыре ограничения. Переменные x1 и x4 исходной задачи не ограничены по знаку. В силу этого первое и четвертое ограничения двойственной задачи имеют вид равенств. Третье ограничение исходной задачи имеет вид равенства, следовательно, переменная y3 двойственной задачи не ограниченна по знаку.


mylektsii.ru - Мои Лекции - 2015-2019 год. (0.007 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал