Пример решения задачи. Решение транспортной задачи
Условие задачи
Поставщики товара - оптовые коммерческие
предприятия
имеют запасы товаров соответственно в
количестве
и розничные торговые предприятия
-подали заявки на закупку товаров в объемах
соответственно:
. Тарифы перевозок единицы
груза с каждого из пунктов поставки в соответствующие пункты потребления заданы
в виде матрицы
. Найти такой план
перевозки груза от поставщиков к потребителям, чтобы совокупные затраты на
перевозку были минимальными.
|
Поставщики \Потребители
|
|
|
|
|
Запасы товаров,
|
|
7
|
20
|
3
|
15
|
225
|
|
3
|
14
|
10
|
20
|
250
|
|
15
|
25
|
11
|
19
|
125
|
|
11
|
12
|
18
|
6
|
100
|
Заявки на закупку товаров,
|
120
|
150
|
110
|
235
|
|
Решение задачи
Экономико-математическая модель задачи
Обозначим через
количество
груза, перевозимого от
поставщика
потребителю.
Тогда общая стоимость перевозок равна:
Ограничения
для поставщиков:
Ограничения для потребителей:
Объем суммарных поставок любого
поставщика к потребителю не может быть отрицательным числом, поэтому
справедливы ограничения:
Проверка транспортной задачи на закрытость
Стандартная транспортная задача
разрешима только в том случае, когда выполняется условие баланса:
В нашем случае:
Модель
транспортной задачи открытая. Вводим фиктивного потребителя, которому
требуется 85 единиц груза.
Правило минимального элемента
Заполняем таблицу по правилу
минимального элемента.
Просматривая таблицу замечаем, что
наименьшие затраты соответствуют маршруту
, поэтому в клетку помещаем
. В этом случае 5-й столбец в расчет не принимается.
Просматриваем оставшиеся таблицы клетки. Наименьшие тарифы имеют клетки
и
Далее действуя по аналогичной схеме:
Число занятых клеток должно быть
.
Решение транспортной задачи методом потенциалов
Решать задачу будем методом
потенциалов. Потенциал 1-й строки принимаем равным нулю. После этого мы можем
вычислить остальные потенциалы (если известны потенциал и тариф занятой клетки,
то из соотношения
легко
определить неизвестный потенциал).
Найдем оценки свободных клеток:
|
S ( 1, 1)= 7-( 0+ 10)= -3
|
S ( 1, 2)= 20-( 0+ 21)=
-1
|
|
S ( 2, 3)= 10-(-7+
3)= 14
|
S ( 2, 4)= 20-(-7+
15)= 12
|
|
S ( 2, 5)= 0-(-7+
0)= 7
|
S ( 3, 1)= 15-( 4+
10)= 1
|
|
S ( 3, 3)= 11-( 4+
3)= 4
|
S ( 3, 5)= 0-( 4+ 0)= -4
|
|
S ( 4, 1)= 11-(-9+ 10)= 10
|
S ( 4, 2)= 12-(-9+
21)= 0
|
|
S ( 4, 3)= 18-(-9+
3)= 24
|
S ( 4, 5)= 0-(-9+
0)= 9
|
Для
клетки ( 3, 5) строим цикл.
Найдем оценки свободных клеток:
|
S ( 1, 1)= 7-( 0+ 10)= -3
|
S ( 1, 2)= 20-( 0+ 21)=
-1
|
|
S ( 1, 5)= 0-( 0-4)= 4
|
S ( 2, 3)= 10-(-7+
3)= 14
|
|
S ( 2, 4)= 20-(-7+
15)= 12
|
S ( 2, 5)= 0-(-7-4)= 11
|
|
S ( 3, 1)= 15-( 4+
10)= 1
|
S ( 3, 3)= 11-( 4+
3)= 4
|
|
S ( 4, 1)= 11-(-9+
10)= 10
|
S ( 4, 2)= 12-(-9+
21)= 0
|
|
S ( 4, 3)= 18-(-9+
3)= 24
|
S ( 4, 5)= 0-(-9-4)= 13
|
Для
клетки ( 1, 1) строим цикл.
Найдем оценки свободных клеток:
|
S ( 1, 2)= 20-( 0+
18)= 2
|
S ( 1, 5)= 0-( 0-4)= 4
|
|
S ( 2, 3)= 10-(-4+
3)= 11
|
S ( 2, 4)= 20-(-4+
15)= 9
|
|
S ( 2, 5)= 0-(-4-4)= 8
|
S ( 3, 1)= 15-( 4+
7)= 4
|
|
S ( 3, 2)= 25-( 4+
18)= 3
|
S ( 3, 3)= 11-( 4+
3)= 4
|
|
S ( 4, 1)= 11-(-9+
7)= 13
|
S ( 4, 2)= 12-(-9+
18)= 3
|
|
S ( 4, 3)= 18-(-9+
3)= 24
|
S ( 4, 5)= 0-(-9-4)= 13
|
Оценки
свободных клеток не отрицательны, следовательно, полученный план является
оптимальным:
Минимальные
транспортные издержки оптимального плана:
При
реализации оптимального плана у поставщика
останется нереализованный товар в размере 85
ед.