logo

Решение контрольных по математике!!!

Home Методички по математике Линейное программирование 19. Основные положения теории двойственности

19. Основные положения теории двойственности

Прямая задача

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

не ограничен в знаке

Теорема 4.1. Пусть – планы соответственно прямой и двойственной ЗЛП, тогда:

.

(4.12)

Теорема 4.2. Пусть – планы соответственно прямой и двойственной ЗЛП и , тогда решения соответственно прямой и двойственной задач.

Теорема 4.3. Если прямая (двойственная) ЗЛП имеет конечное решение, то и двойственная (прямая) ЗЛП имеет решение, причем

. (4.13)

Если прямая (двойственная) ЗЛП не имеет решения, то и двойственная (прямая) ЗЛП не имеет решения.

Теорема 4.4. Планы Соответственно прямой и двойственной ЗЛП являются оптимальными тогда и только тогда, когда

. (4.14)

Условия (4.14) называются условиями дополнительной нежесткости.

Примечание 1. Для основной ЗЛП и двойственной к ней ЗЛП условия нежесткости имеют вид:

. (4.15)

Примечание 2. Если прямая ЗЛП записана не в канонической форме, то условия дополнительной нежесткости для этой ЗЛП и двойственной к ней ЗЛП могут быть записаны в следующем виде:

Если хj* > 0, то ,

Если то yi* = 0, (4.16)

Если yi* > 0, то

Если , то хj* = 0.

Получение оптимального плана двойственной задачи на основании теоремы 4.4.

Пример 4.5. Рассмотрим задачу:

(4.17)

Ее решение . Найдем решение задачи, двойственной к (4.17), используя теорему 4.4. Запишем двойственную к (4.17) задачу:

(4.18)

Применяем соотношение (4.16). Так как х1* = 3/2 > 0, то 3у1* + 4у2* + у3* = 2. Далее, так как 3х1* + х2* = 9/2 + 0 > 3, то у1* = 0, и так как х1* + 2х2* = 3/2 + 0 < 3, то у3* = 0. В итоге имеем:

3у1* + 4у2* + у3* = 2, у1* = у3* = 0,

Т. е. вектор является решением задачи (4.18) на основании теоремы 4.4. Вычислим , что соответствует утверждению теоремы 4.3.

Пример 4.6. Найти решение прямой и двойственной задач.

Прямая задача

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

Max= 5Х1 + 12Х2 + 4Х3

Х1 +2Х2 +Х3 ≤ 10

2Х1 Х2 + 3Х3 = 8

Х2,3 ≥ 0

Х1 не ограничена в знаке

Min= 10Y1 + 8Y2

Y1 +2Y2 = 5

2Y1 – Y2 ≥ 12

Y1 + 3Y2 ≥ 4

Y1 ≥ 0

У2 не ограничена в знаке

(а)

(б)

(в)

(г)

Двойственная задача содержит две переменные, т. е. ее можно решать графически (рис. 4.1).

Рис. 4.1

Как видно из рис. 4.1, область допустимых решений – планов двойственной ЗЛП – Q представляет собой отрезок АВ, лежащий на прямой Y1 + 2Y2 = 5, так как первое ограничение задается в виде равенства. Передвигая линию уровня функции 10Y1 + 8Y2 = const в направлении, противоположном вектору = (10; 8), получаем точку А, в которой достигается минимум функции . Находим координаты точки А, которая является пересечением двух прямых:

Y1 + 2 Y2 = 5,

2 Y1 – Y2 = 12,

Откуда

= 29/5; = -2/5 и = 54 .

Ипользуя теорему 4.4, находим решение исходной задачи. Так как > 0 и < 0, то оба ограничения прямой задачи имеют вид строгих равенств:

Х1 + 2Х2 + 3Х3 = 10;

2Х1 – Х2 + 3Х3 = 8. (4.19)

Так как третье ограничение двойственной задачи выполняется в виде строгого неравенства (29/5 – 6/5 = 24/5 > 4), то = 0. Решая систему (4.19), получаем

= 26/5; = 12/5; = 0; f() = 54,8.

Получение оптимального решения двойственной задачи из симплекс-таблицы решения прямой задачи

Пусть прямая задача имеет вид основной ЗЛП:

(4.20)

Двойственная к ней ЗЛП имеет вид:

;

. (4.21)

Предположим, что ЗЛП (4.20) имеет решение. Решения обеих задач могут быть записаны в виде:

= ; = ,

Где = = (, …, )

Матрица, обратная для базисной подматрицы . Матрица подматрицы расположена на месте единичной подматрицы в исходной матрице.

Кроме того, можно показать, что

, , (4.22)

Откуда следует, что i-я компонента решения двойственной ЗЛП есть (n + i)-я симплекс-разность матрицы , определяющей оптимальный план исходной ЗЛП, а j-я симплекс-разность матрицы () равна разности между левой и правой частями ограничений двойственной ЗЛП:

= . (4.23)

Пример 4.7. Решить следующую ЗЛП:

Max (4Х1 + Х2 + 2Х3 + 3Х4);

Х1 +2Х2 + 3Х3 – Х5 + Х7 = 50;

–3Х2 +Х3 + Х4 +2Х5 + 4Х7 = 10;

4Х2 + Х5 + Х6 – 1/2 Х7 = 24;

. (4.24)

Найти решение задачи, двойственной к ЗЛП (4.24).

Так как расширенная матрица

=

Системы линейных уравнений (4.24) является К-матрицей, то ЗЛП (4.24) можно решить симплекс-методом. Результаты решения приведены в таблице:

4

1

2

3

0

0

0

1

4

6

4

3

0

50

10

24

1

0

0

2

–3

4

3

1

0

0

1

0

–1

2

1

0

0

1

1

4

–1/2

25

6

= 230

0

–2

13

0

2

0

16

1

4

2

4

3

1

38

28

6

1

0

0

0

0

1

3

1

0

0

1

0

–3/2

11/4

1/4

–1/2

3/4

1/4

5/4

29/8

–1/8

= 242

0

0

13

0

5/2

1/2

63/4

На первой итерации получен оптимальный план ЗЛП (4.24).

= (1, 4, 2); = (38, 28, 6),

= (38, 6, 0, 28, 0, 0, 0); F() = 242.

Запишем задачу, двойственную к (4.24):

Min(50Y1 + 10Y2 +24Y3);

Y1 ≥ 4;

2Y1 – 3Y2 + 4Y3 ≥ 1;

3Y1 + Y2 + ≥ 2.

(4.25)

Y2 ≥ 3;

–Y1 +2Y2 + Y3 ≥ 0;

Y3 ≥ 0;

Y1 + 4Y2 – 1/2 Y3 ≥ 0.

(4.26)

не ограничены в знаке.

(4.27)

Ограничения (4.27) являются избыточными, следовательно, их можно отбросить.

Находим решение ЗЛП (4.25) по формуле

== (4, 3, 1) = (4, 3, 1/2)

Или (4.22):

= (0 + 4, 0 + 3, + 0) = (4, 3, );

= 50´4 + 10´3 + 24 ´ = 242.

 
Яндекс.Метрика
Наверх