Общая характеристика метода потенциалов

Транспортная задача, в которой имеет место равенство (4), называется закрытой и может быть решена как задача линейного программирования с помощью симплексного метода. Однако благодаря особенностям переменных задачи и системы ограничений разработаны специальные, менее громоздкие методы ее решения. Наиболее применяемым методом является метод потенциалов, при котором для каждой i- й строки (i -го поставщика) определяется потенциал u_i, а для каждого столбца j - потенциал v_j. Сумма потенциалов для перевозки груза от i -го поставщика к j -му потребителю должна быть равна величине транспортных расходов c_ij, т.е. быть оценена с точки зрения критерия решаемой задачи:

c_ij=v_j+u_i (5)

Если баланс (4) не выполняется, то ограничения (1) или (2) имеют вид неравенств типа «меньше или равно»; транспортная задача в таком случае называется открытой. Для решения открытой транспортной задачи методом потенциалов ее сводят к закрытой задаче путем ввода фиктивного потребителя, если в неравенства превращаются условия (2), или фиктивного поставщика в случае превращения в неравенства ограничений (1).

Рассмотрим этапы реализации метода потенциалов для закрытой транспортной задачи. Прежде всего следует отметить, что при условии баланса (4) ранг системы линейных уравнений (1), (2) равен т + п - 1; таким образом из общего числа (m ´ n) неизвестных базисных неизвестных будет (т + п – 1). Вследствие этого при любом допустимом базисном распределении в матрице перевозок, представленной в общем виде в табл. 9, будет занято ровно т + п - 1 клеток, которые будем называть базисными в отличие от остальных свободных клеток. Коэффициент целевой функции в занятых клетках будем выделять полукругом.

Первым этапом алгоритма метода потенциалов является составление начального распределения (начального плана перевозок); для реализации этого начального этапа используются методы северо-западного угла, наименьших стоимостей, аппроксимаций Фогеля. На втором этапе выполняется построение системы потенциалов на основе равенства (5) и проверка начального плана на оптимальность; в случае его неоптимальности переходят к третьему этапу, содержание которого заключается в реализации так называемого цикла перераспределения, после чего переходят опять ко второму этапу. Совокупность процедур третьего и второго этапов образует одну итерацию; эти итерации повторяются, пока план перевозок не станет оптимальным по критерию (1). Решение транспортной задачи выполняется в матричном виде. Матрица планирования приведена в таблице 9.

Таблица 9 – Матрица планирования перевозок груза

Вj Ai	B1	B2	……	Bn
b1	b2	……	bn
А1	a1	c11 x11	c12 x12	……	c1n x1n
А2	a2	c21 x21	c22 x22	……	c2n x2n
……	……	……	……	……	……
Аm	am	cm1 xm1	cm2 xm2	……	cmn xmn

Дата добавления: 2014-01-05