Математические методы в экономике
Главная | Метод потенциалов | Регистрация | Вход
 
Понедельник, 25.09.2017, 18:02
Приветствую Вас Гость
Главное меню
Статистика
Форма входа

Проверка оптимальности плана и перераспределение поставок с помощью метода потенциалов

Для анализа полученных планов и их последующего улучшения удобно ввести дополнительные характеристики пунктов отправления и назначения, называемые потенциалами.

Вычисление потенциалов

Сопоставим каждому поставщику Ai и каждому потребителю Bj величины ui и vj соответственно так, чтобы для всех базисных клеток плана были выполнены соотношения

ui + vj = cij, i = 1,2,...,n, j = 1,2,...,n.

Поскольку число базисных клеток в плане равно m + n - 1 (вырожденные планы должны быть предварительно пополнены), то для определения потенциалов получается система из m + n - 1 уравнений с m + n неизвестными. Такая система имеет бесконечное множество решений. Нам требуется любое ее решение. Обычно для простоты полагают один из потенциалов равным нулю и затем вычисляют остальные. В транспортной таблице для потенциалов v1,v2,...,vn заводится дополнительные строка, а для потенциалов u1,u2,...,un – дополнительный столбец, куда проставляются найденные значения.

Проверка оптимальности плана

Для каждой свободной клетки плана вычислим разности Δсij = cij - (ui + vj) и запишем полученные значения в левых нижних углах соответствующих клеток. Заметим, что для базисных клеток выполнено соотношение Δсij = 0, и этим фактом можно пользоваться для контроля правильности нахождения потенциалов.

План является оптимальным, если все разности Δсij ≥ 0. В противном случае план можно улучшить следующим способом.

Перераспределение поставок

Найдем клетку с наибольшей по абсолютной величине отрицательной разностью Δcij и построим цикл, в котором кроме этой клетки все остальные являются базисными. Такой цикл всегда существует и единственен.

Заметим, что в новом плане суммы элементов по строкам и столбцам должны остаться прежними, поэтому изменение значения в одной клетке цикла повлечет за собой соответствующие изменения значений во всех остальных клетках этого цикла. Так как в свободной клетке значение будет увеличено, то проставим в ее правом нижнем углу знак "+". Теперь пройдем по всей ломаной цикла, проставляя в правых нижних углах клеток поочередно знаки «плюс» и «минус».

Груз будет перераспределен по клеткам цикла на величину Δx = min xij следующим образом. В клетках со знаком «плюс» значение перевозки нужно увеличить на величину Δx , а в клетках со знаком «минус» – уменьшить на величину Δx . Так как после пересчета у нас добавилась лишняя базисная клетка, то их количество необходимо сократить, убрав нуль в одной из клеток цикла. Если таких клеток получилось несколько, то свободной делаем ту из них, в которой тариф перевозок максимален.

После этого полученный план проверяется на оптимальность описанным выше способом. Перераспределение груза производится до тех пор, пока очередной план не станет оптимальным. На этом действие алгоритма завершается.

Пример


Copyright MyCorp © 2017Бесплатный конструктор сайтов - uCoz