![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Среди всех клеточек (і,j), для присоединяется к совокупности базисных клеточек. которых не выполняется критерий оптимума, избирают клеточку с наибольшим модулем оценки D ij. Пометим такую клеточку через (i0,j0).
Пусть клеточка (i0,j0), для которой
Находится цикл, что образуется этими клеточками. Цикл разбивается на положительный (C+) и отрицательный (C–) полуциклы, клеточки которых чергуються одна из одною, причем клеточка (i0,j0) относится к положительному полцикла. Вычисляются величины
q1 = min{ xij } по C–,
q2 = min{rij – xij } по C+
q = min{ q1q2 }.
Увеличивают на значение q перевозка xij в клеточках полцикла C+ и уменьшают их на то же значение в клеточках C –.
Для клеточки (i0,j0) такой, что отмена заключается в том, что она относится к отрицательному полцикла.
В результате выполнения указанных процедур клеточка (i0,j0) вводится к множеству базисных, а клеточка, связанная с q, становится небазисной. Если q достигается на клеточке (i0,j0), то множество базисных клеточек не изменяется после перераспределения перевозок вдоль цикла на постоянную q и новый ДБР будет иметь ту же самую систему потенциалов и те же самые оценки, что и предыдущий. Поэтому в этом случае после вычисления нового ДБР непосредственно переходят к проверке его на оптимум.
Дата публикования: 2014-11-04; Прочитано: 295 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!