Лекция 6. Двойственность в линейной оптимизации

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

План

2. Теоремы двойственности. Анализ дефицитности ресурсов и продукции.

1. В предыдущей лекции был рассмотрен пример 1 о производстве сухих строи-

тельных смесей. Была составлена математическая модель задачи ЛП:

Z = 4 x 1 + 5 x 2 → max;

⎧0, 25 x 1 + 0, 6 x 2 ≤15,

⎪

⎩ 1 2

⎨0, 25 x 1 + 0, 2 x 2 ≤ 7,

⎪0, 5 x + 0, 2 x ≤12;

x 1 ≥ 0, x 2 ≥ 0.

Пусть имеют место другие экономические условия:

• фирма купила сырьё;

• постоянный покупатель строительных смесей разорился;

• быстро организовать сбыт смесей затруднительно;

• другая фирма согласна купить сырьё.

(1) (2) (3)

Необходимо договориться о таких ценах на сырьё, которые бы устраива-

ли обе стороны.

Обозначим цену в тыс. грн. за 1 т для сырья трёх видов через

y 1,

y 2,

y 3.

Для изготовления 1-й смеси используют разное сырьё в объёмах 0,25 т, 0,25 т и

0,5 т, соответственно. Поэтому фирму-продавца устраивает соотношение

0, 25 y 1 + 0, 25 y 2 + 0, 5 y 3 ≥ 4,

т.е. суммарная оплата компонент 1-й смеси будет не менее 4 тыс. грн. за тонну.

Аналогично определим второе ограничение

0, 6 y 1 + 0, 2 y 2 + 0, 2 y 3 ≥ 5.

Фирма-покупатель стремится уменьшить расходы на приобретение сы-

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

F =15 y 1 + 7 y 2 +12 y 3.

Математическая модель новой задачи ЛП:

F =15 y 1 + 7 y 2 +12 y 3 → min;

⎧0, 25 y 1 + 0, 25 y 2 + 0, 5 y 3 ≥ 4,

⎨

⎩0, 6 y 1 + 0, 2 y 2 + 0, 2 y 3 ≥ 5;

y 1 ≥ 0, y 2 ≥ 0, y 3 ≥ 0.

(4) (5)

(6)

Имея решение исходной задачи симплекс-методом, можно определить оптимальный план двойственной задачи.

Объясним на примере 1 предыдущей лекции. Базисными векторами в пер-

вой симплексной таблице были

Б 1 = (A 3,

A 4,

A 5). Эти вектора в последней

симплексной таблице имеют оценки оптимальности

z j − c j: –4,5; –11,5; 0. Взяв

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

y

y

y

* = −(−4, 5) − 0 = 4, 5;

* = −(−11, 5) − 0 =11, 5;

* = −0 − 0 = 0.

Задачи (1)-(3) и (4)-(6) называют симметричной парой двойственных задач ЛП. Их структуры имеют однозначную связь (табл. 1).

Табл. 1. Симметричная пара для примера о строительных смесях

Исходная задача	Двойственная задача
Z = 4 x 1 + 5 x 2 → max; ⎧0, 25 x 1 + 0, 6 x 2 ≤15, ⎪ ⎨0, 25 x 1 + 0, 2 x 2 ≤ 7, ⎪0, 5 x 1 + 0, 2 x 2 ≤12; x 1 ≥ 0, x 2 ≥ 0.	F =15 y 1 + 7 y 2 +12 y 3 → min; ⎧0, 25 y 1 + 0, 25 y 2 + 0, 5 y 3 ≥ 4, ⎨ ⎩0, 6 y 1 + 0, 2 y 2 + 0, 2 y 3 ≥ 5; y ≥ 0, y ≥ 0, y ≥ 0.
JJG* X = (12; 20), Z max =148.	JG* Y = (4,5;11, 5; 0), F min =148.

⎩ 1 2 3

Видно, что фирма-продавец получает одинаковый доход 148 тыс. грн. в обеих ситуациях. Фирма-покупатель получает сырьё в полном объёме.

Данные исходной задачи транспонированы в двойственной задаче, т.е.

числовые данные исходной задачи, записанные строками, стали столбцами в двойственной задаче. Сопоставим их в табл. 2.

Табл. 2. Свойства двойственных задач для примера о строительных смесях

Исходная задача	Двойственная задача
1) на максимум; 2) две переменных; 3) три ограничения; 4) знаки ограничений ≤.	1) на минимум; 2) два ограничения; 3) три переменных; 4) знаки ограничений ≥.

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

Если исходная задача на максимум, то двойственная – на минимум. Ис- ходная имеет n неизвестных, двойственная n ограничений. Исходная задача содержит m ограничений, двойственная – m неизвестных. Коэффициенты це-

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

двойственной задачи, и наоборот. Исходная задача имеет среди ограничений m 1

неравенств и

m − m 1

равенств, двойственная –

m 1 неотрицательных переменных

и m − m 1

переменных произвольного знака. Исходная задача имеет

n 1 неотрица-

тельных переменных и

n − n 1

переменных произвольного знака, двойственная

имеет среди ограничений

n 1 неравенств и

n − n 1

равенств (табл. 3).

Табл. 3. Симметричная пара в общем виде

Исходная задача	Двойственная задача
n Z = ∑ c j x j → max, j =1 ⎧ n ⎪∑ aij x j ≤ bi, i =1, m 1, m 1 ≤ m, ⎪ j =1 ⎨ n ⎪∑ aij x j = bi, i = m 1 +1, m, ⎩ j =1 x j ≥ 0, j =1, n 1, n 1 ≤ n, x j произвольного знака при j = n 1 +1, n.	m F = ∑ bi yi → min, i =1 ⎧ m ⎪∑ aij yi ≥ c j, j =1, n 1, n 1 ≤ n, ⎪ i =1 ⎨ m ⎪∑ aij yi = c j, j = n 1 +1, n, ⎪ ⎩ i =1 yi ≥ 0, i =1, m 1, m 1 ≤ m, yi произвольного знака при i = m 1 +1, m.

⎪

Пример 1. Дана задача линейного программирования:

Z = 3 x 1 + 3 x 2 → min

⎪

⎧ x 1 − 2 x 2 ≥ −6

⎪4 x 1+ 6 x 2 ≤ 24

⎨

⎪ x 1 + x 2 ≥ −4

⎪⎩ x 1 ≤ 2

x 1 ≥ 0.

Требуется: составить математическую модель двойственной задачи.

Решение. Т.к. исходная задача на минимум, то желательно, чтобы все не-

равенства в системе ограничений были записаны со знаком «≥»:

⎧ x 1

⎪

− 2 x 2 ≥ −6

⎪−4 x 1 − 6 x 2 ≥ −24

⎨

⎪ x 1

⎪⎩− x 1

+ x 2 ≥ −4

≥ −2

Сопоставим данные (см. табл. 2).

Табл. 4. Свойства двойственных задач для примера 1

Исходная задача	Двойственная задача
1) на минимум; 2) две переменных; 3) четыре ограничения; 4) знаки ограничений ≥.	1) на максимум; 2) два ограничения; 3) четыре переменных; 4) знаки ограничений ≤.

Добавим к табл. 4 существенный нюанс. Переменная

x 1 ≥ 0, поэтому пер-

вое ограничение двойственной задачи будет неравенством со знаком «≤». Пе-

ременная

x 2 – произвольного знака, поэтому второе ограничение двойственной

задачи будет равенством. Т.к. все ограничения исходной задачи являются нера-

венствами, то все переменные двойственной задачи будут неотрицательными.

*

Окончательный вид двойственной задачи:

F = −6 y 1 − 24 y 2 − 4 y 3 − 2 y 4 → max

⎧ y 1 − 4 y 2 + y 3 − y 4 ≤ 3

⎨

⎩−2 y 1 − 6 y 2 + y 3 = 3

y 1 ≥ 0, y 2 ≥ 0.

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