Метод потенциалов, его алгоритм

Теорема

Если план транспортной задачи является оптимальным, то ему соответствует система из m+ n чисел и , удовлетворяющих условиям: для , для , . Числа , называются потенциалами соответственно поставщиков и потребителей.

Данная теорема позволяет построить алгоритм нахождения решения транспортной задачи.

АЛГОРИТМ

1. Для ТЗ с правильным балансом находим начальный план перевозок методом северо-западного угла или методом минимального элемента.

2. Для каждой базисной клетки составляем уравнение . Так как число базисных клеток m + n – 1, то система m + n – 1 уравнений с m + n неизвестными имеет бесконечное множество решений. Для определенности положим u₁ = 0. Тогда все остальные потенциалы находятся однозначно. Вносим их в матрицу перевозок.

3. Для свободных клеток находим суммы соответствующих потенциалов, помещаем их в нижний правый угол свободных клеток матрицы.

4. Для всех свободных клеток проверяем выполнение условия оптимальности:

· если для всех свободных клеток ( ), то задача решена; выписываем полученный оптимальный план перевозок из последней матрицы, подсчитываем его стоимость;

· если для одной или нескольких свободных клеток, то переходим к п. 5.

5. Находим ту свободную клетку, для которой имеет наибольшее по модулю отрицательное значение. Строим для нее означенный цикл. Свободной клетке приписываем знак +. Все вершины означенного цикла, кроме расположенной в клетке (i,j), должны находиться в базисных клетках.

6. Выполняем сдвиг по циклу на величину , равную наименьшему из чисел, стоящих в «отрицательных» вершинах цикла. Если наименьшее значение достигается в нескольких «–» клетках, то при сдвиге следует поставить базисный нуль во всех таких клетках, кроме одной. Тогда число базисных клеток сохранится и будет равно m + n – 1, это необходимо проверять при расчетах.

Клетки матрицы, не входящие в цикл, остаются без изменения.

Строим новую матрицу перевозок.

7. Переход к шагу 2.

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

Пример 5. Составить математическую модель ТЗ, решить ТЗ:

Запишем матрицу перевозок (табл. 3.4).

Таблица 3.4

Bj Ai	B1	B2	В3	B4	Запасы ai
A1
A2
A3
Потребности bj

1. Пусть – количество единиц груза, которое нужно перевезти из пункта А_i в пункт B_j .

2. Ограничения:

а) по запасам

б) по потребностям

3. Целевая функция: . Требуется составить план перевозок, чтобы их суммарная стоимость была минимальной.

4. Данная ТЗ с правильным балансом: 15 + 25 + 5 = 5 + 15 + 10; 45 = 45.

5. Начальный план перевозок найден в п. 3.3.2 методом минимального элемента (табл.3.3) Выпишем найденную матрицу перевозок.

6. Находим потенциалы базисных клеток:

Матрица перевозок

	Bj Ai	B1	B2	В3	B4	Запасы ai
u1=0	A1	10		20	11
u2=7	A2	12
u3= -10	A3		14 -10	16 -8	18
	Потребности bj

7. Для свободных клеток находим суммы соответствующих потенциалов, заносим их в матрицу в нижний правый угол свободных клеток.

8. Для свободных клеток проверяем выполнение условия оптимальности: для . Для клеток (1,4) и (2,1) условие не выполнено.

9. , Для свободных клеток строим обозначенный цикл.

10. Производим сдвиг по циклу на Клетка (2,1) становится базисной , а клетка (1,1) – свободной.

11. Переходим к шагу 2 алгоритма метода потенциалов.

12. Строим новую матрицу перевозок.

u1=0 5 0 20 11 u2=7 u3= -5 14 -5 16 -3 18 Матрица перевозок.

Для свободной клетки (1,4) условие оптимальности не выполнено. Строим для нее обозначенный цикл, осуществляем сдвиг по циклу на Клетка (1,4) становится базисной , клетка (2,4) – свободной. Строим новую матрицу перевозок.

u1=0 10 20 u2=7 20 u3= -5 14 -5 16 -3 18 Матрица перевозок

13. Переходим к шагу 2 метода потенциалов:

Для всех свободных клеток .

Полученный план является оптимальным:

.

При данном плане стоимость перевозок:

.

Задачи для самостоятельного решения

3.1 – 3.9. Найти начальное опорное решение методом северо-западного угла

и методом минимального элемента.

3.1		3.2
3.3		3.4
3.5		3.6
3.7		3.8
3.9

3.10-3.24.По указанным ниже данным о ресурсах a_i , потребностях b_j и матрицы коэффициентов затрат с cоставить математические модели и решить соответствующие транспортные задачи.

3.10		3.11
3.12		3.13
3.14		3.15
3.16		3.17
3.18		3.19
3.20		3.21
3.22		3.23
3.24

СЕТЕВЫЕ МОДЕЛИ