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

 

Определение 6.1. Цикл – замкнутая ломаная с вершинами в клетках и звеньями, расположенными вдоль строк и столбцов матрицы перевозок. В каждой вершине встречаются два звена, причем одно из них располагается по строке, а другое – по столбцу. Число вершин цикла четно. Циклом может быть самопересекающаяся ломаная, но точки ее самопересечения не могут быть вершинами цикла.

 

Определение 6.2.  Означенный цикл – цикл, в котором некоторой вершине приписан знак “+”, а затем при обходе цикла в каком-либо направлении знаки чередуются.

 

Определение 6.3.  Сдвиг по циклу на число . При этом значения , стоящие в положительных вершинах цикла, увеличиваются на число , а стоящие в отрицательных вершинах, уменьшаются на число .

 

Определение 6.4. Потенциалы – числа  . Каждому пункту хранения  ставится в соответствие число , пункту потребления  – число .

 

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

 

1. Найти начальный план перевозок.   2. Для каждой базисной клетки составить уравнение:. Так как эти уравнения образуют систему уравнений с  неизвестными (она имеет бесконечное множество решений), то для определенности следует положить . Тогда все остальные потенциалы находятся однозначно.   3. Для каждой свободной клетки вычислить относительные оценки:   .   4. Проанализировать относительные оценки:             а) если все относительные оценки неотрицательные, т.е. выполняется условие , то задача решена, и следует выписать полученный оптимальный план перевозок из последней матрицы, подсчитать его стоимость;             б) если среди оценок  есть отрицательные, найти среди них наименьшую отрицательную оценку и пометить знаком.   5. Для свободной клетки  с выбранной оценкой , помеченной, построить означенный цикл. Все его вершины, кроме расположенной в клетке , должны находиться в базисных клетках. Свободная клетка берется со знаком “+”.   6. Выполнить сдвиг по построенному на шаге 5 циклу на величину, равную наименьшему из чисел, стоящих в отрицательных вершинах. При этом числа, стоящие в положительных вершинах, увеличить на, а числа, стоящие в отрицательных вершинах,  уменьшить на.   Если наименьшее значение  достигается в нескольких отрицательных вершинах цикла, то при сдвиге следует поставить базисный нуль во всех таких вершинах, кроме одной. Тогда число базисных клеток сохранится и будет равно , что необходимо проверять при расчетах. Базисный нуль рекомендуется ставить в клетку (клетки) с наименьшей стоимостью перевозок. Элементы матрицы, не входящие в цикл, остаются без изменений.   Перейти к шагу 2.

 

Замечания по процедуре счета.

 

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

 

№2. Значения суммарной стоимости перевозок при переходе от одной матрицы к другой связаны соотношением ,

где – номер итерации, – текущее значение суммарной стоимости перевозок, значения  и  находятся на шагах 3 и 6 соответственно.

 

 

Пример 6.3.

 

Дано. Транспортная задача, заданная матрицей перевозок:

 

Пункты				Запасы
				20
				40
Потребности	10	20	30	60

 

Найти решение задачи методом потенциалов.

 

Решение:

 

1. Найдем начальный план перевозок методом северо-западного угла:

 

Пункты				Запасы
	10	10		20
		10	30	40
Потребности	10	20	30	60

.

 

            (1,1) ,                    (1)

            (1,2) ,                   (2)

            (2,2) ,                  (3)

            (2,3)                     (4).

Положим , тогда получим из (1), из (2) , из (3) из , и из (4)

 

Получим:.

 

3. Вычисляем относительные оценки для свободных клеток:

(1,3)     ;      

(2,1)     .

 

4. Т.к. условие окончания не выполнено, найдём наименьшую отрицательную оценку , она соответствует клетке (1, 3).

 

5. Для клетки (1,3) построим означенный цикл.

6. Найдем значение  . Выполним сдвиг по циклу на число 10.

 

 

2. Составим уравнения для базисных клеток:

            (1,1) ,                    (1)

            (1,2) ,                   (2)

            (2,2) ,                  (3)

            (2,3)                     (4).

Положим , тогда получим из (1), из (2) , из (4) из , и из (3) .

 

 

 

Получим:.

 

3. Вычисляем относительные оценки для свободных клеток:

(1,2)     ;      

(2,1)     .

4. Т.к. условие окончания не выполнено, найдём наименьшую отрицательную оценку , она соответствует клетке (2, 1).

 

5. Для клетки (2,1) построим означенный цикл.

6. Найдем значение  . Выполним сдвиг по циклу на число 10.

2. Составим уравнения для базисных клеток:

            (1,3) ,                   (1)

            (2,1) ,                    (2)

            (2,2) ,                  (3)

            (2,3)                     (4).

Положим , тогда получим из (1) , из (4) , из (3) из , и из (2) .

        

Получим:.

 

3. Вычисляем относительные оценки для свободных клеток:

(1,1)     ;      

(1,2)     .

 

4. Условие окончания выполнено, найден оптимальный план перевозок:

                                                                               

                                                                           

с суммарной стоимостью .