Метод потенциалов для решения транспортной задачи

Формулировка транспортной задачи: ,

при ограничениях – удовлетворение запросов пунктов потребления, – отправка грузов не должна превышать запасов (равна для задачи закрытого типа).

– сбалансированная транспортировка.

	В1 …	Вt	Bq …	Bn	ai
A1	c11				a1
As		cs1 xst	csq xsq		as
Ap		cpt	cpq xpq		ap
Am	cm1			cmn	am
bj	b1	bt	bq	bn

Сущность метода состоит в том, что каждому пункту сопоставляют некоторые векторы, называемые потенциалами пункта: A_i®a_i , B_j ®b_j. Для определения потенциалов необходимо иметь одно из допустимых базисных решений. Существуют соотношения, показывающие, что алгебраическая сумма стоимости по циклу пересчета свободной клетки равна разности между стоимостью и суммой потенциалов:

. (7.9)

Свяжем все пункты, соответствующие базисным переменным, уравнениями: a_i +b_j = c_ij , где c_ij –стоимость перевозки единицы груза из i-гопункта в j-й. Объединение всех уравнений для базисных неизвестных образует систему с числом уравнений r = m + n – 1и числом неизвестных потенциалов (m+n).

Система уравнений для рассматриваемого общего случая при базисных клетках x_sl , x_sq , x_pq будет

(7.10)

Решить систему уравнений нетрудно, т.к. ее ранг равен рангу системы ограничений задачи, т.е. r = m + n – 1, и за свободную переменную можно взять любую из неизвестных a_i, b_j .

В качестве свободной переменной, например, можно принять a_S и придать ей произвольное значение (удобно нуль).

Далее рассматривают все базисные неизвестные x_st, которые располагаются в s-й строке матрицы перевозок. Каждой такой неизвестной соответствует в системе определенное уравнение a_s + b_t = c_st.

Т.к. a_s задаются, то из уравнения можно найти b_t (например, a_s=0, b_t= c_st). Так же находятся все остальные b_t из s-й строки, например b_q=с_sq. После этого останавливаются на одном из найденных b, например b_q, и рассматривают все те базисные неизвестные x_pq, которые располагаются в q-м столбце матрицы. Каждой такой неизвестной отвечает уравнение: a_p + b_q = c_pq. Но, т.к. b_q найдено ранее (b_q= с_sq), то из такого уравнения можно найти a_p = c_pq - b_q = c_pq - с_sq. Так находятся все a_p, соответствующие всем базисным неизвестным x_pq из q-го столбца.

Этот процесс продолжается, пока не будут найдены все a_i, b_j, т.е. пока не будут определены потенциалы всех пунктов.