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

UptoLike

ВУЗ: 

ТПУ | Томск

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

Рубрика: 

101
объем производства которой точно совпадает с суммарными потребностями не-
которой группы пунктов потребления.
Другими словами, это условие означает, что для любых двух систем ин-
дексов
12
, ,...,
t
i i i
,
12
, ,...,
S
j j j
, где
t S n m
, имеет место неравенство
11
kk
tS
ij
kk
ab


. (Доказательство не сложно, от противного.)
Для решения транспортной задачи методом потенциалов строится система
потенциалов
j i ij
v u c
,
0
ij
x
. Если опорное решение невырожденно, то чис-
ло неизвестных на 1 больше числа уравнений. При вырожденном опорном ре-
шении число этих уравнений еще меньше. По аналогии симплекс-методом, в не-
вырожденном решении
0
ij
x
представляют собой базисные переменные, а
0
ij
x
– небазисные. Если опорное решение вырожденно, то часть базисных пе-
ременных принимает нулевые значения.
Пусть первое опорное решение, найденное методом северо-западного угла
или методом минимального элемента, является вырожденным. Тогда, чтобы ре-
шать задачу методом потенциалов необходимо выбрать в качестве базисных пе-
ременных некоторые перевозки
0
ij
x
и для них также составить уравнения
j i ij
v u c
по условию (2) теоремы. Какие перевозки вида
0
ij
x
включать в ба-
зисные? Выбираются такие клетки таблицы с
0
ij
x
, чтобы из базисных пере-
менных нельзя было организовать ни одного цикла!
При переходе к новому улучшенному плану задачи в небазисные перемен-
ные переводится перевозка в отрицательной полуцепи, которая находится сле-
дующим образом
min
ij
x

. В вырожденной задаче это значение может до-
стигаться на нескольких перевозках
ij
x
отрицательной полуцепи. В этом случае
на каждом шаге в небазисные переменные переводится та минимальная перевоз-
ка отрицательной полуцепи, которая связана с пунктом производства, имеющим
меньший номер. Это правило уменьшает вероятность возникновения зациклива-
ния, что само по себе достаточно редкое явление в практических задачах.

Страницы