Формулировка транспортной задачи: ,
при ограничениях – удовлетворение запросов пунктов потребления, – отправка грузов не должна превышать запасов (равна для задачи закрытого типа).
– сбалансированная транспортировка.
В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 |
Сущность метода состоит в том, что каждому пункту сопоставляют некоторые векторы, называемые потенциалами пункта: Ai®ai, Bj ®bj. Для определения потенциалов необходимо иметь одно из допустимых базисных решений. Существуют соотношения, показывающие, что алгебраическая сумма стоимости по циклу пересчета свободной клетки равна разности между стоимостью и суммой потенциалов:
. (7.9)
Свяжем все пункты, соответствующие базисным переменным, уравнениями: ai +bj = cij, где cij –стоимость перевозки единицы груза из i- гопункта в j- й. Объединение всех уравнений для базисных неизвестных образует систему с числом уравнений r = m + n – 1и числом неизвестных потенциалов (m+n).
|
|
Система уравнений для рассматриваемого общего случая при базисных клетках xsl, xsq, xpq будет
(7.10)
Решить систему уравнений нетрудно, т.к. ее ранг равен рангу системы ограничений задачи, т.е. r = m + n – 1, и за свободную переменную можно взять любую из неизвестных ai, bj.
В качестве свободной переменной, например, можно принять aS и придать ей произвольное значение (удобно нуль).
Далее рассматривают все базисные неизвестные xst, которые располагаются в s- й строке матрицы перевозок. Каждой такой неизвестной соответствует в системе определенное уравнение as + bt = cst.
Т.к. as задаются, то из уравнения можно найти bt (например, as =0, bt = cst). Так же находятся все остальные bt из s- й строки, например bq = сsq. После этого останавливаются на одном из найденных b, например bq, и рассматривают все те базисные неизвестные xpq, которые располагаются в q -м столбце матрицы. Каждой такой неизвестной отвечает уравнение: ap + bq = cpq. Но, т.к. bq найдено ранее (bq= сsq), то из такого уравнения можно найти ap = cpq - bq = cpq - сsq. Так находятся все ap, соответствующие всем базисным неизвестным xpq из q- го столбца.
Этот процесс продолжается, пока не будут найдены все ai, bj, т.е. пока не будут определены потенциалы всех пунктов.