Численные методы оптимизации. Рейзлин В.И. - 92 стр.

UptoLike

ВУЗ: 

ТПУ | Томск

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

Рубрика: 

92
1
1
, 1, ,
, 1, ,
0, 1, , 1, ,
m
ij j
i
n
ij i
j
ij
x b j n
x a i m
x i m j n


,
где
ij
c
– стоимость перевозки единицы продукции из пункта i в пункт j;
ij
x
–
планируемая величина перевозок из пункта i в пункт j (план перевозок
X
– мат-
рица размерности
mn
);
j
b
– потребности в продукте в пункте j;
i
a
– запасы в пункте i.
Предполагается, что модель закрытого типа, то есть
11
nm
ji
ji
ba


.
Если модель открытого типа
, то ее всегда можно привести к
закрытому типу введением фиктивного пункта производства или фиктивного
пункта потребления:
Если
11
nm
ji
ji
ba


, то
1
11
mn
n i j
ij
b a b



,
тогда
1
11
nm
ji
ji
ba


, причем
,1
0
in
ci

.
Если
11
nm
ji
ji
ba


, то
1
11
nm
m j i
ji
a b a



,
1
11
nm
ji
ji
ba


и
1,
0
mj
cj

.
Транспортная задача представляет собой задачу линейного программиро-
вания и, естественно, ее можно решить с использованием метода последователь-
ного улучшения плана или метода последовательного уточнения оценок. В этом
случае основная трудность бывает связана с числом переменных задачи (m
n) и
числом ограничений (m+n). Поэтому специальные алгоритмы оказываются бо-
лее эффективными. К таким алгоритмам относятся метод потенциалов и венгер-
ский метод.
Алгоритм метода потенциалов, его называют еще модифицированным
распределительным алгоритмом, начинает работу с некоторого опорного плана
транспортной задачи (допустимого плана перевозок). Для построения опорного
плана обычно используется один из двух методов: метод северо-западного угла
или метод минимального элемента.

Страницы