Сформулируем теоремы двойственности

Первая теорема двойственности. Если одна из задач двойственной пары имеет оптимальное решение, то и другая задача имеет оптимальное решение, причём экстремальные значения целевых функций совпадают:

n m

j =1

c j x j =

∑

bi yi.

Если же целевая функция одной из задач не ограничена, то ОДР другой задачи пустая.

*

x * =12 т;

x 2 = 20

т.;

= 4 ⋅12 + 5⋅ 20 =148 тыс. грн.

грн.;

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

y * = 4, 5

тыс. грн.;

y * =11,5

тыс. грн.;

y * = 0

тыс.

Т.е

Z max

F min =15 ⋅ 4, 5 + 7 ⋅11, 5 +12 ⋅ 0 =148 тыс. грн.

= F min. Первая теорема двойственности выполняется.

Вторая теорема двойственности. Если в оптимальном плане исходной

x * > 0

(j =1, n), то j -е ограничение двойственной

задачи её оптимальным решением обращается в строгое равенство. Если опти-

мальное решение исходной задачи обращает какое-то i -е (i =1, m) ограничение

y * > 0.

Удостоверимся на примере из табл. 1. Рассмотрим выполнение первого утверждения второй теоремы двойственности.

x * =12

(т.е.

x * > 0), то первое ограничение двойственной задачи

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

JG*

должно обращаться её оптимальным решением

Y = (4, 5;11, 5; 0)

в строгое равенство.

Действительно,

0,25⋅ 4,5 + 0,25⋅11,5 + 0,5⋅ 0 = 4.

x * = 20

(т.е.

x * > 0), то второе ограничение двойственной задачи

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

JG*

должно обращаться её оптимальным решением

Y = (4, 5;11, 5; 0)

в строгое равенство.

Действительно,

0,6 ⋅ 4,5 + 0,2 ⋅11,5 + 0,2 ⋅ 0 = 5.

Первое утверждение второй теоремы двойственности выполнилось.

Проверим выполнение второго утверждения теоремы.

JG*

Оптимальное решение исходной задачи

X = (12; 20)

обращает первое ог-

раничение

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

в строгое равенство: 0, 25 ⋅12 + 0,6 ⋅ 20 =15. По-

этому

y * > 0 (y * = 4, 5).

1 1

JG*

Оптимальное решение исходной задачи

X = (12; 20)

обращает второе ог-

раничение

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

в строгое равенство: 0, 25 ⋅12 + 0,2 ⋅ 20 = 7. Поэто-

(y * =11,5).

JG*

Оптимальное решение исходной задачи

X = (12; 20)

не обращает третье

ограничение

0, 5 x 1 + 0, 2 x 2 ≤12

в строгое равенство: 0, 5 ⋅12 + 0,2⋅ 20 =10. Полу-

y * = 0.

Оба утверждения второй теоремы двойственности выполнились для при-

мера из табл. 1.

* (i =1, m) являются

двойственной оценкой или теневой ценой i -го ресурса.

* называют

Если

y * > 0, то ресурс дефицитный и при реализации оптимального пла-

на X

расходуется полностью. Т.е. i -е ограничение исходной задачи обратится

в строгое равенство.

Приобретение дополнительной единицы этого ресурса приведёт к увели-

y *. Чем больше значение теневой

y * = 0.

y * = 4, 5

тыс. грн.,

y * =11,5

тыс. грн.,

y * = 0

тыс. грн. Значит ресурсы цитный.

S 1,

S 2 являются дефицитными, а ресурс

S 3 – не дефи-

Дата добавления: 2014-01-07; Просмотров: 258; Нарушение авторских прав?; Мы поможем в написании вашей работы!