Методы принятия управленческих решений: для менеджеров

94 уравнений (число занятых клеток /и + и - I) на единицу меньше числа неизвестных, поэтому одному неизвестному (обычно U)) придают нулевое значение. Тогда остальные потенциалы определяются одно­ значно. Если в транспортной задаче число положительных компо­ нент опорного плана к <т + п~ \ ,jo его называют вырожденным. Алгоритм метода потенциалов. 1. Находят первоначальный опорный план одним из рас­ смотренных методов. 2. Проверяют, будет ли число занятых клеток (п + т-]). Если это условие не выполнено, то опорный план вырожденный, не­ достающее число клеток заполняют нулевыми перевозками .Vy = О. 3. Вычисляют потенциалы Uj и Vj из условия, что для за­ нятых клеток и j +V j =Cjj , при этом приравнивают нулю. 4. Для каждой свободной клетки огтределяют величину Ду = Су -((/,•+V j ) . Если все Ду > О, полученный план является оптимальным. Если Ду > 0 , этот план единственный. Если хотя бы одно Д у = 0 , задача имеет бесконечное множество оптимальных планов. Если хотя бы одна оценка Ду < О , переходят к пункту 5. 5. Находят значение Ду < О , максимальное по модулю. Для соответствующей свободной клетки сфоят замкнутый цикл пере­ счета. Пусть П1ах ]д,, 1= Д;^ . Построенный цикл обходят против Д/,<о' ' часовой стрелки, присваивая вершинам по очереди знаки и начиная с клетки (1,к). Среди клеток с отрицательным знаком вы­ бирают ту, в которую поставляется меньше всего груза. Пусть min |ху |= 0 . Тогда количество ф у з а , равное 0 , вычи­ тают из клеток, отмеченных знаком и прибавляют в клетках,