Метод потенциалов

1. Каждой строке и каждому столбцу транспортной таблицы поставить в соответствие значение потенциала и соответственно. Для этого положить один из потенциалов равным произвольному значению (обычно полагают ). После этого, исходя из соотношений для занятых (базисных) клеток, последовательно вычислить значения остальных потенциалов.

2. Для исследования плана на оптимальность необходимо вычислить для каждой свободной (незанятой) клетки значение оценки . Если все оценки , то план оптимален. Если при этом все оценки , то полученный оптимальный план единственный. В случае, если хотя бы одна оценка , то имеется бесконечное множество оптимальных планов с одним и тем же значением целевой функции.

3. Если хотя бы для одной клетки оценка удовлетворяет условию , то рассматриваемый план не является оптимальным и его можно улучшить за счет той клетки, для которой . Если таких клеток несколько, то наиболее быстро оптимальное решение может быть получено за счет той клетки, для которой положительное значение оценки наибольшее. Экономически оценка показывает, на сколько единиц уменьшатся транспортные издержки от назначения перевозки единицы продукции в данную клетку. Так, например, если , то при назначении транспортные издержки уменьшатся на 10 единиц.

4. Итак, пусть оценка , т.е. положительное значение переменной позволяет улучшить план. Так как должно быть выполнено условие баланса, то одна из ранее положительных переменных должно обратиться в нуль.

Для того чтобы улучшить план перевозок необходимо построить цикл, который начинается и заканчивается в ячейке . Цикл состоит из последовательности горизонтальных и вертикальных отрезков, соединяющих вершины — занятые (базисные) ячейки в текущем плане, и ячейку, соответствующую вводимой переменной. Для любой вводимой переменной можно построить только один замкнутый цикл. Вершинам этого цикла условно приписываются знаки, которые чередуются: свободной клетке — плюс, следующей (по или против часовой стрелки) — минус, следующей — снова плюс и т.д. Из перевозок, расположенных в вершинах, отмеченных знаком минус выбирается наименьшее значение, обозначим его . Это значение прибавляется к значениям перевозок, расположенным в положительных вершинах и вычитается из перевозок в отрицательных вершинах. В результате этого одна клетка из отрицательных вершин, ранее занятая, освобождается и баланс не нарушится. Если одновременно несколько занятых клеток могут принять нулевые значения, то освобождается только одна из них, а остальные продолжают считаться занятыми, хотя и с нулевыми значениями перевозок.

Задание. В задаче компанииMG Auto (см. 6.3) построить начальное решение, проверить его на оптимальность и найти оптимальное решение с помощью метода потенциалов.

Оптимальное решение в этой задаче гарантирует минимальную стоимость транспортировки продукции равную $313 200 при следующем плане перевозок: , остальные переменные равны нулю.

Дата добавления: 2014-12-29