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

UptoLike

ВУЗ: 

ТПУ | Томск

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

Рубрика: 

96
при ограничениях
0
ij i j ij
y u v c
,
1,im
,
1,jn
,
т.е.
j i ij
v u c
,
1,im
,
1,jn
.
Пусть
[]
ij m n
Xx
– оптимальное решение транспортной задачи. Тогда на
основании теоремы двойственности двойственная задача имеет оптимальное
решение
* * * *
11
, ..., ; , ...,
mn
u u v v
.
Убедимся, что эти числа являются потенциалами соответствующих пунк-
тов транспортной задачи. Действительно, все
**
,
ij
uv
как опорное решение двой-
ственной задачи удовлетворяют неравенствам (7,8).
Если
, то по второй теореме двойственности соответствующее огра-
ничение
* * *
0
ij i j ij
y u v c
двойственной задачи обращается в строгое равенство
**
j i ij
v u c
.
Алгоритм метода потенциалов
Алгоритм метода потенциалов состоит из предварительного этапа и по-
вторяющегося основного этапа.
Предварительный этап.
Каким-либо способом ищется допустимый план
X
(методом северо-
западного угла или минимального элемента).
1. Для полученного плана строится система m+n чисел
1
,...,
m
uu
,
1
, ...,
n
vv
, таких, что
j i ij
v u c
,
0
ij
x
.
2. Построенная система
i
u
и
j
v
исследуется на потенциальность (то
есть план
X
исследуется на оптимальность). Для этого проверяется
j i ij
v u c
,
0
ij
x
.
Если система непотенциальна, то переходят к основному этапу (т.к. план
не оптимален), иначе оптимальный план найден.
Основной этап.
1. Улучшаем план, то есть от плана
X
переходим к плану
'X
такому,
что
( ) ( ')Q X Q X
.
2. Для плана
'X
строим новую систему
''
,
ij
uv
,
1,im
,
1,jn
, такую,
что
''
j j ij
v u c
,
0
ij
x
.
3. Исследуем систему
''
,
ij
uv
на потенциальность. Если система непо-
тенциальна, то переходим на п.1. Иначе найден оптимальный план.

Страницы