Транспортная компания занимается перевозкой зерна специальными зерновозами от трёх элеваторов к четырём мельницам. В табл. 1 показаны возможности отгрузки зерна элеваторами, а также стоимость перевозки зерна одним зерновозом от элеваторов к мельницам. Стоимость перевозок приведена в ден. ед. [1].
Требуется определить структуру перевозок между элеваторами и мельницами с минимальной стоимостью. Для этого необходимо найти матрицу перевозок, при которой стоимость всех расходов на доставку груза окажется минимальной. Заполним транспортную таблицу (табл. 1).
Начальное решение получим, например, методом северо-западного угла (табл. 2) [3].
Таблица 1
Таблица 2
Суммарная стоимость перевозок равна
(ден. ед.).
Для нахождения оптимального решения используем метод потенциалов [1, 2]. Вычисления обычно выполняются непосредственно в транспортной таблице (табл. 3). Положим 
. Поскольку все потенциалы определены, далее вычислим косвенные стоимости 
для всех свободных клеток и запишем найденные значения в левом верхнем углу каждой незанятой клетки. В левом нижнем углу записываем разности 
для каждой небазисной переменной 
.
Таблица 3
Определив вводимую в базис переменную 
, найдём исключаемую из базиса переменную. Необходимо, чтобы перевозки по маршруту, соответствующему переменной 
, уменьшили общую стоимость перевозок. Какой объём груза можно перевезти по этому маршруту? Обозначим через ε
количество груза, перевозимого по маршруту (3;1) (т. е. 
). Сначала построим замкнутый цикл, который начинается и заканчивается в ячейке, соответствующей вводимой переменной 
. Для ячейки (3;1) определим цикл, включающий клетки с базисными поставками: (3;1), (1;1), (1;2), (2;2), (2;4) и (3;4) (табл. 4).
Для перераспределения поставок по найденному циклу необходимо определить минимальный перевозимый груз ε [1]. Чтобы выполнились ограничения по спросу и предложению, надо поочерёдно отнимать и прибавлять величину ε к значениям базисных переменных, расположенных в угловых ячейках найденного цикла (табл. 5).
Искомую величину следует выбирать среди клеток, содержащих знак «минус», т.е.
.
Переменные 
и 
обращаются в нуль. Поскольку только одна переменная исключается из базиса, то в качестве исключаемой можно выбрать как 
, так и 
. Остановим свой выбор на 
. Тогда 
. Определив значение для вводимой переменной 
, и выбрав исключаемую переменную, откорректируем значения базисных переменных, соответствующих угловым ячейкам замкнутого цикла (табл. 6).
Таблица 4
Таблица 5
Таблица 6
Перевозка единицы груза по маршруту (3;1) уменьшает общую стоимость перевозки на 
ден. ед. Суммарная стоимость перевозок будет на 
ден. ед. меньше, чем в предыдущем решении.
Так как 
, то получим
ден. ед.
Продолжим анализ оптимальности. Вычислим потенциалы нового базисного решения (табл. 7). Новой вводимой в базис переменной будет 
. Замкнутый цикл позволяет найти её значение x14=10 и исключаемую переменную 
.
Новое решение, представленное в табл. 8, уменьшает значение целевой функции на 40 (ден. ед.). Тогда 
ден. ед.
Таблица 7
Таблица 8
Теперь для всех небазисных переменных 
оценки 
. Т.е. выполнился критерий оптимальности на минимум [2]. Таким образом, найденное решение является оптимальным.
,
.
Полученное решение, изложенное в терминах исходной задачи перевозки зерна от элеваторов до мельниц, имеет следующий смысл:
|
От элеватора |
До мельницы |
Количество зерновозов |
|
1 |
2 |
5 |
|
1 |
4 |
10 |
|
2 |
2 |
10 |
|
2 |
3 |
15 |
|
3 |
1 |
5 |
|
3 |
4 |
5 |
Суммарная стоимость перевозок 
ден. ед.