2.1. Транспортная задача
Пример 10
Предположим, что требуется минимизировать стоимость перевозок с четырех фабрик на пять оптовых складов готовой продукции. Фабрики расположены в городах Минске, Гродно, Бресте, Могилеве. Их производственные возможности, соответственно, — 200, 150, 225 и 175 усл. ед. продукции ежедневно. Потребности и возможности для хранения на оптовых складах, соответственно, — 100, 200, 50, 250 и 150 усл. ед. продукции ежедневно. Товары могут доставляться с любой фабрики на любой склад. Известны тарифы на перевозки.
Требуется определить объемы перевозок между каждой фабрикой и оптовым складом, в соответствии с потребностями складов и производственными возможностями фабрик, при которых транспортные расходы минимальны.
Данная модель сбалансирована, т. е. суммарный объем произведенной продукции равен суммарному объему потребности в ней. В противном случае в модель нужно было бы ввести:
в случае перепроизводства — фиктивный оптовый склад;
в случае недопроизводства — фиктивную фабрику.
Для данной задачи: функция цели — это суммарные транспортные расходы; искомые переменные — объемы перевозок; в качестве ограничений примем, что объемы перевозок не могут быть отрицательными, а объемы производства равны объемам потребления.
Создадим таблицу с исходными данными, как показано на рис. 16.
|
A |
B |
C |
D |
E |
F |
G |
H |
1 |
|
Склад1 |
Склад2 |
Склад3 |
Склад4 |
Склад5 |
|
|
2 |
Минск |
1,5 |
2,00 |
1,75 |
2,25 |
2,3 |
|
|
3 |
Гродно |
2,5 |
2,00 |
1,75 |
1,00 |
1,5 |
|
|
4 |
Брест |
2,0 |
1,50 |
1,50 |
1,75 |
1,8 |
|
|
5 |
Могилев |
2,0 |
0,50 |
1,75 |
1,75 |
1,8 |
|
|
6 |
|
|
|
|
|
|
|
|
7 |
Минск |
|
|
|
|
|
|
200 |
8 |
Гродно |
|
|
|
|
|
|
150 |
9 |
Брест |
|
|
|
|
|
|
225 |
10 |
Могилев |
|
|
|
|
|
|
175 |
11 |
|
|
|
|
|
|
|
|
12 |
|
100 |
200 |
50 |
250 |
150 |
|
|
Рис. 16. Исходные данные для расчета
Описание заполнения ячеек таблицы
Исходные данные
B2:F5 — известные значения стоимости перевозок (тарифы) между фабрикой-производителем и оптовым складом.
Н7:Н10 — количество усл. ед. продукции, производимой на каждой фабрике фирмы ежедневно.
В12:F12 — ежедневные потребности складов в количестве усл. ед. продукции.
Функция цели вычисляется в ячейке G11 по формуле
=СУММПРОИЗВ(B2:F5;B7:F10)
т. е. будущие объемы перевозок умножаются на тарифы.
Искомые переменные
В7:F10 — объемы перевозок (неизвестные значения).
B11:F11 — суммы объемов перевозок по каждому оптовому складу. В ячейку В11 вводится формула =СУММ(В7:В10) и выполняется автозаполнение в ячейки С11:F11.
G7:G10 — суммы объемов перевозок по каждой фабрике. В ячейку G7 вводится формула =СУММ(В7:F7) и выполняется автозаполнение в ячейки G8:G10.
Затем в меню Сервис выбирается команда Поиск решения.
Наиболее быстрое решение этой задачи можно получить, если выбрать использование линейной модели перед началом поиска решения. Поэтому в открывшемся окне диалога нажмем на кнопку Параметры и установим флажок Линейная модель.
Заполним окно диалога Поиск решения так, как предложено на рис. 17.
Нажмем на кнопку Добавить и введем ограничения.
Нажмем на кнопку Выполнить и установим переключатель Сохранение найденного решения в открывшемся окне диалога.
Рис. 17. Диалоговое окно Поиск решения для транспортной задачи
В результате решения задачи должна получиться таблица, представленная на рис. 18.
|
A |
B |
C |
D |
E |
F |
G |
H |
1 |
|
Склад1 |
Склад2 |
Склад3 |
Склад4 |
Склад5 |
|
|
2 |
Минск |
1,50 |
2,00 |
1,75 |
2,25 |
2,25 |
|
|
3 |
Гродно |
2,50 |
2,00 |
1,75 |
1,00 |
1,50 |
|
|
4 |
Брест |
2,00 |
1,50 |
1,50 |
1,75 |
1,75 |
|
|
5 |
Могилев |
2,00 |
0,50 |
1,75 |
1,75 |
1,75 |
|
|
6 |
|
|
|
|
|
|
|
|
7 |
Минск |
100 |
0 |
50 |
0 |
50 |
200 |
200 |
8 |
Гродно |
0 |
0 |
0 |
150 |
0 |
150 |
150 |
9 |
Брест |
0 |
25 |
0 |
100 |
100 |
225 |
225 |
10 |
Могилев |
0 |
175 |
0 |
0 |
0 |
175 |
175 |
11 |
|
100 |
200 |
50 |
250 |
150 |
975 |
|
12 |
|
100 |
200 |
50 |
250 |
150 |
|
|
Рис. 18. Оптимальное решение транспортной задачи