Оставить заявку:

Написать ВКонтакте

Отправить заявку на
e-mail

Телефон:


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

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

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

Поставщики       \Потребители Запасы товаров,
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 ед.

Помощь в решении ваших задач по этому предмету вы можете найти, отправив сообщение в ВКонтакте, на Viber или заполнив форму. Стоимость решения домашней работы начинается от 7 бел.руб. за задачу (200 рос.руб.), но не менее 10 бел.руб. (300 рос.руб.) за весь заказ. Подробное оформление. Стоимость помощи на экзамене онлайн (в этом случае необходима 100% предоплата) - от 30 бел.руб. (1000 рос.руб.) за решение билета.

Последнее обновление сайта:
26.10.2019
@mathminsk.com
2008-2019 Минск