![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Правила построения двойственных задач
Каждой задаче линейного программирования, которую назовем исходной, можно поставить с соответствие некоторую другую задачу линейного программирования, называемую двойственной к ней. Вместе взятые, эти задачи образуют пару взаимно-двойственных задач и любую из них можно рассматривать как исходную. Решая одну из этих задач, можно получить решение и другой задачи. Двойственная задача – это вспомогательная задача линейного программирования, получаемая с помощью определённых правил непосредственно из условий исходной. Сформулируем правила построения двойственных задач: 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;
a21x1 + a22x2 +…+ a2nxn < = b2, …………………………….. am1x1 + am2x2 +…+ amnxn < = bm,
xj > = 0 (j= 1, n).
Двойственная к этой задаче будет иметь вид: z = b1y1 + b2y2 +…+ bmym→ min;
a12y1 + a22y2 +…+ am2ym > =c2, …………………………….. a1ny1 + a2ny2 +…+ amnym > = cn, yi > = 0 (i = 1, m).
Если применить правила построения двойственных задач, то получим исходную задачу. В таблице 5 приведены частные виды исходных задач линейного программирования в матричном виде и соответствующие им двойственные задачи. Через Y = (y1, y2, …, ym) обозначена матрица-строка неизвестных двойственной задачи. Матрица-строка Y умножается слева на матрицу-столбец B (в целевой функции) и матрицу A (в ограничениях) исходя из правил умножения двух матриц, а также правил построения двойственных задач (в частности, в двойственной задаче матрица коэффициентов при неизвестных в ограничениях должна быть транспонированной).
Таблица 5. Правила формирования двойственных задач Первые две пары взаимно двойственных задач в таблице называются симметричными, вторые две – несимметричными из-за наличия ограничений вида «=». Используя правила построения двойственных задач и таблицу 5, для любой задачи линейного программирования можно построить двойственную к ней.
Пример 1. Построить задачу, двойственную к данной: f = x1 –x2 → max;
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 > = 0, y2 > = 0. Пример 2. Построить задачу, двойственную к данной:
f = 7x1 + 6x2 + 3x3 – x4 → min;
-x1 + 2x2 – x3 + x4 < = 10, 3x1 + 5x2 + 4x4 = 7, x2 > = 0, x3 > = 0. Для построения двойственной задачи воспользуемся формулами (2), (4) и преобразуем данную задачу путем умножения обеих частей второго неравенства на (-1). Тогда исходная задача будет иметь вид: f = 7x1 + 6x2 + 3x3 – x4 → min;
x1 - 2x2 + x3 - x4 < = -10, 3x1 + 5x2 + 4x4 = 7,
x2 > = 0, x3 > = 0.
Двойственная задача:
z = 12y1 – 10y2 + 7y3 → max;
-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 двойственной задачи не ограниченна по знаку.
|