Составители:
Рубрика:
168
∑
=
==
m
i
jij
njbx
1
.,...,2,1
(4.15)
С целью составления двойственной задачи переменные x
ij
в условии (4.14) заменим
на u
1
, u
2
,…, u
i
,…,u
m
, а переменные условия (4.15) на v
1
, v
2
,…, v
j
,…,v
n
.
Поскольку каждая переменная x
ij
входит в условия (4.14, 4.15) и целевую функцию
(4.13) по одному разу, то двойственную задачу по отношению к прямой транспортной
задаче можно сформулировать следующим образом.
Требуется найти не отрицательные числа v
i
(при i= 1, 2, ..., m) и v
j
(при j=1, 2, ..., п),
обращающие в максимум целевую функцию
∑ ∑
= =
+=
m
i
n
j
jjii
vbuaG
1 1
(4.16)
при условии
u
i
+ v
j
≤
c
ij
i=1,2,…,m; j=1,2,…,n (4.17)
В системе условий (4.17) будет тxп неравенств. По теории двойственности для
оптимальных планов прямой и двойственной задачи для всех i,j должно быть
>=+
=≤+
.0если,
,0если,
ijijji
ijijji
xcvu
xcvu
(4.18)
Эти условия (4.18) являются необходимыми и достаточными признаками
оптимальности плана транспортной задачи.
Числа u
i
и v
j
,
удовлетворяющие условиям (4.18), называются потенциалами. Причем
число u
i
, называется потенциалом поставщика A
i
, а число v
j
— потенциалом потребителя
В
j.
При решении задачи для проверки опорного плана на оптимальность потенциалы
поставщиков и потребителей легко определяются из условия, что для всех базисных
клеток, т. е. клеток с х
ij
>0 должно быть справедливо равенство
u
i
+ v
j
= c
ij
(4.19)
Отсюда
u
i
= c
ij
- v
j
(4.20)
v
j
= c
ij
- u
i
(4.21)
Поскольку как u
i
так и v
j
неизвестны, произвольно принимают один из потенциалов
равным какой-то величине (например, потенциал поставщика с максимальной мощностью
— равным нулю). Затем вычисляются все остальные потенциалы из уравнений (4.20),
(4.21).
Проверка плана на оптимальность производится посредством сопоставления для
каждой свободной клетки суммы потенциалов поставщика и потребителя со стоимостью
поставки в клетке. Для всех свободных клеток сумма потенциалов в оптимальном плане
не должна превышать стоимости поставки, т. е. должно выполняться условие:
u
i
+ v
j
≤
c
ij
(4.22)
Таким образом, план считается оптимальным, если сумма потенциалов для
свободных клеток, меньше или равна стоимости поставок в них.
Если обозначить через
∆
ij
, характеристику свободной клетки A
i
B
j
то ее можно
вычислить из формулы (4.22):
∆
ij
= c
ij
-( u
i
+ v
j
) (4.23)
В оптимальном решении
∆
ij
≥
0. (4.24)
Кроме того, по первой теореме двойственности в оптимальном решении значения
целевых функций прямой и двойственной задач совпадают: F=G.
Страницы
- « первая
- ‹ предыдущая
- …
- 166
- 167
- 168
- 169
- 170
- …
- следующая ›
- последняя »
