Пример решения задачи. Решение транспортной задачи

Условие задачи

Поставщики товара - оптовые коммерческие предприятия  имеют запасы товаров соответственно в количестве  и розничные торговые предприятия  -подали заявки на закупку товаров в объемах соответственно: . Тарифы перевозок единицы груза с каждого из пунктов поставки в соответствующие пункты потребления заданы в виде матрицы . Найти такой план перевозки груза от поставщиков к потребителям, чтобы совокупные затраты на перевозку были минимальными.

Поставщики

       \Потребители

Запасы товаров,

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 ед.

 

Методы оптимальных решений
Бесплатное решение задач по линейному программированиюГлавная : Примеры решения : Транспортная задача

Еще примеры решения задач






Готовые примеры решения задач по линейному программированию бесплатно
Последнее обновление сайта: 03.09.2016

@mathminsk.com 2008-2016 Минск