Введение в линейное программирование. Палий И.А. - 78 стр.

UptoLike

ВУЗ: 

СибАДИ | Омск

Составители: 

Рубрика: 

б) не все запасы вывезены (соответственно не все потребности
удовлетворены). Тогда, как следует из (9.19)
∑∑∑∑∑
=−−−−
<+=+==
m
i
i
j
j
i
i
ji
abatjxisxRRrv
1пом пом не пом пом не
**
),(),(),(
.
Отсюда
0
пом пом
>−
∑∑
−− j
j
i
i
ba .
В этом случае решение
y задачи (9.21) – (9.22) можно улучшить так
же, как при решении ЗН.
Прочеркнем в матрице затрат непомеченные строки и помеченные
столбцы. Все допустимые клетки вычеркнутся, в матрице останутся только
такие стоимости
c
ij
, для которых c
ij
> u
i
+ v
j
. Положим
)min(
jiij
vuch −−= , если строка i − помечена, а столбец j − не помечен,
тогда
h>0.
Пересчитаем значения двойственных переменных по правилу
⎩
⎨
⎧
=−
−+
=
′
.,,1 помечена, не строка если ,
помечена; строка если ,
miiu
ihu
u
i
i
i
L
⎩
⎨
⎧
=−
−−
=
′
.,,1 помечен, не столбец если ,
помечен; столбец если ,
njjv
jhv
v
i
i
j
L
, (9.14)
Допустимость нового решения очевидна. Вычислим значение целевой
функции на нем
∑∑
∑∑∑∑∑∑
==
==−−==
+>
>+−+=
′
+
′
n
j
jj
m
i
ii
m
i
n
j
jj
j
j
i
iii
m
i
n
j
jjii
vbua
vbbahuavbua
11
11пом пом 11
.
)(
Итак, на новом решении
),,,,,(
11 nm
vvuuy
′
′
′
′
=
′
LL
целевая функция
двойственной задачи увеличилась.
Снова найдем в матрице стоимостей те клетки, для которых
c
ij
> u
i
+ v
j
,
снова решим задачу о максимальном потоке и т.д. Если
c
ij
– целые числа,
то и значения двойственных переменных (потоки на дугах) можно выбрать
целыми. Тогда значение целевой функции двойственной задачи каждый
раз будет увеличиваться на целое число. Через конечное число шагов
будет найдено оптимальное решение двойственной задачи и максимальное
значение ее функции. Параллельно найдутся оптимальные перевозки,
минимизирующие затраты.

Страницы