Пусть 
- потенциалы поставщиков 
, а 
- потенциалы потребителей 
. Сумма потенциалов каждой загруженной клетки равна стоимости перевозки т.е.
(1).
Так как число загруженных клеток равно n+k-1, а число неизвестных равно n+k, то одна неизвестная является свободной и ей можно придать любое числовое значение. Пусть 
, тогда из уравнений можно найти остальные потенциалы. После нахождения потенциалов загруженных клеток, вычисляются оценки пустых клеток по формуле:
(2).
Полученный допустимый план перевозок будет оптимальным, если среди оценок пустых клеток нет положительных чисел. Если же среди оценок есть положительные числа, то строится новый план, при этом загружают клетку с наибольшей, положительной оценкой. Строится путь, соединяющий выбранную клетку с наибольшей положительной оценкой, проходящий через загруженные клетки. В каждой клетке полученного цикла ставятся знаки «+» и «-» поочередно, начиная с пустой клетки. Далее выбирается наименьшее число построенного цикла и прибавляется к поставкам в клетках со знаком «+» и вычитается в клетках со знаком «-». В результате перемещения груза будет получен новый план поставок, который необходимо проверить на оптимальность.
Пример.
На три базы 
поступил однородный груз в количестве 120, 120 и 140 ед. соответственно. Полученный груз необходимо доставить в пять пунктов 
в количестве 70, 60, 70, 30, 150 ед.. Стоимость перевозки пропорциональна количеству груза и расстоянию, на которое этот груз перевозится. Спланировать перевозки так, чтобы общая стоимость перевозок была наименьшей, если расстояния между поставщиками и потребителями заданы матрицей
.
Решение.
Составим таблицу распределения перевозок.
Таблица 1
| 
| 
| 
| 
| Наличие | ||
| |||||||
| |||||||
| |||||||
| Потребность |
Проверим выполнение необходимого условия разрешимости транспортной задачи
:
70+60+70+30+150=380 и 120+120+140=380, задача разрешима.
Для составления математической модели данной задачи, введем неизвестные 
- количество единиц груза, перевозимого от каждого поставщика к каждому потребителю, причем 
0. Справедливы следующие системы ограничений:
система ограничений по поставкам;
система ограничений по потребителям.
Целевая функция, выражающая общую стоимость перевозок имеет вид:
.
Составим опорный план по методу северо-западного угла.
В клетку (1,1) запишем min(70,120)=70,первый столбец закрыт.
В клетку (1,2) запишем min(120-70,60)=50 и первая строка закрыта.
В клетку (2,2) запишем min(60-50,120)=10 и второй столбец закрыт.
В клетку (2,3) запишем min(70,120)=70 и третий столбец закрыт.
В клетку (2,4) запишем min(120-10-70,30)=30, четвертый столбец закрыт.
В клетку (2,5) запишем min(150,10)=10 и вторая строка закрыта.
В клетку (3,5) запишем min(140,140)=140, таблица заполнена.
Таблица 2
|
|
|
|
| 
| Запасы | |
|
|  70
|  50
| 
| 
| 
| |
|
|
|  10
|  70
|  30 
| 10
| |
|
|
| 
|
|
| 140
| |
| Потребность |
Опорное решение запишем в виде матрицы:
Критерий загруженности клеток выполняется т.к. 3+5-1=7, число загруженных клеток тоже равно 7.
Затраты по перевозке составят:
= 560+550+120+980+450+110+1400=4170.
Т.к. при распределении груза по методу северо-западного угла не учитывалась цена по доставке, то выгоднее использовать метод минимального элемента.
Заполнение начнем с клетки с минимальной стоимостью (1,3), 
, запишем min(70,120)=70. Составим новую таблицу.
В клетку (1,1) запишем min(120-70,70)=50, первая строка закрыта.
В клетку (2,1) запишем min(70-50,120)=20 и первый столбец закрыт.
В клетку (3,2) запишем min(60,140)=60, второй столбец закрыт.
В клетку (3,5) запишем min(150,140-60)=80, тогда
в клетку (2,5) запишем 70 и пятый столбец закрыт.
Таблица заполнена.
Таблица 3
|
|
|
| 
|
| Наличие | ||
|
| 
|
| 
|
|
| ||
| 
|
|
| 
| 
| ||
|
|
| 
|
|
| 
| ||
| Потребность |
Новый план запишется в виде:
Вычислим значение целевой функции.
=400+490+160+450+770+540+800=3610, что меньше чем .
Исследуем полученное решение на оптимальность методом потенциалов.
Для заполненных клеток выполнятся равенства:
, 
, 
, 
,
, 
, 
.
Положим , тогда 
, 
, 
, 
,
, 
, 
.
Найдем оценки пустых клеток по формуле .
Среди оценок есть положительные числа, поэтому можно улучшить опорное решение. Выберем цикл, который содержит клетку (1,4), т.к. эта клетка имеет наибольшую, положительную оценку:
(1,1) - + (1,4) 50 - + 0
или
(2,1) + - (2,4) 20 + - 30
т.к. min(50,30)=30, то окончательно получим
20 30
50 0
Новое решение имеет вид:
.
Стоимость перевозок равна: Z= 160+490+390+400+770+540+800=3550.
Проверим полученное решение на оптимальность.
Выпишем равенства, выполняющиеся для загруженных клеток:
, , 
,
, , , 
,
тогда: 
.
Оценки пустых клеток равны:
, 
,
, 
,
, 
,
, 
.
Среди оценок имеется одна положительная, следовательно, можно продолжить улучшение решения.
Построим цикл, включающий клетку с положительной оценкой (1,5).
20 - + 20
50 + - 70 70 50
.Решение задачи приведется к виду:
Затраты по перевозкам составят
Для загруженных клеток выполняются равенства
, , ,
, , ,
,
из которых находим
,
.
Вычислим оценки пустых клеток:
, 
,
, 
,
, 
,
, 
.
Возможно улучшение плана перевозок, т.к. имеется положительная оценка. Построим цикл, содержащий клетку (3,4).
30 - + 20 50
+ - 80 30 50
Новое решение запишем в виде матрицы:
.
Затраты по перевозкам равны:
.
Проверим решение на оптимальность.
Запишем равенства, выполняющиеся для загруженных клеток:
, 
, , 
,
, , .
Откуда находим:
Оценки пустых клеток:
.
Все оценки являются отрицательными, следовательно, получен оптимальный план по перевозкам, который определяется матрицей:
и транспортные издержки составят
Затраты по перевозкам составят 
(у.е.)
Задание 9.
Имеются три пункта поставки однородного груза A1, A2, A3 с возможностями 
, 
, 
и три пункта потребления B1, B2, B3 с данными потребностями 
, 
, 
и матрицей тарифов доставки груза. Найти оптимальный план перевозки груза по данным, приведенным в таблице
Вариант №1
|
Вариант №2
| ||||||||||||||||||||||||||||||||||||||||||||||||||
Вариант №3
| Вариант №4
| ||||||||||||||||||||||||||||||||||||||||||||||||||
Вариант №5
| Вариант №6
| ||||||||||||||||||||||||||||||||||||||||||||||||||
Вариант №7
| Вариант №8
| ||||||||||||||||||||||||||||||||||||||||||||||||||
Вариант №9
| Вариант №10
|