Метод потенциалов, его алгоритм
Теорема | Если план ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
Данная теорема позволяет построить алгоритм нахождения решения транспортной задачи.
АЛГОРИТМ
1. Для ТЗ с правильным балансом находим начальный план перевозок методом северо-западного угла или методом минимального элемента.
2. Для каждой базисной клетки составляем уравнение . Так как число базисных клеток m + n – 1, то система m + n – 1 уравнений с m + n неизвестными имеет бесконечное множество решений. Для определенности положим u1 = 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 в пункт Bj .
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 | ![]() | ![]() | ![]() | ||
u2=7 | A2 | ![]() | ||||
u3= -10 | A3 | ![]() | ![]() | ![]() | ||
Потребности bj |
7. Для свободных клеток находим суммы соответствующих потенциалов, заносим их в матрицу в нижний правый угол свободных клеток.
8. Для свободных клеток проверяем выполнение условия оптимальности: для
. Для клеток (1,4) и (2,1) условие не выполнено.
9. ,
Для свободных клеток строим обозначенный цикл.
10. Производим сдвиг по циклу на Клетка (2,1) становится базисной
, а клетка (1,1) – свободной.
11. Переходим к шагу 2 алгоритма метода потенциалов.
12. Строим новую матрицу перевозок.
Матрица перевозок. | ![]() ![]() |
Для свободной клетки (1,4) условие оптимальности не выполнено. Строим для нее обозначенный цикл, осуществляем сдвиг по циклу на Клетка (1,4) становится базисной
, клетка (2,4) – свободной. Строим новую матрицу перевозок.
Матрица перевозок | ![]() |
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.По указанным ниже данным о ресурсах ai , потребностях bj и матрицы коэффициентов затрат с 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 | ![]() |
СЕТЕВЫЕ МОДЕЛИ