Мгновенная связь через Вайбер или ВКонтакте в любое время
и на любом этапе заказа.
Общение с автором работ без посредников.
Опыт работы более 20 лет.
Помощь в решении ваших задач вы можете найти, отправив сообщение Вайбера или ВКонтакте Заполнение формы с личными данными и регистрация на сайте не нужна.
Телефон: 8(968)849-45-98

Решение транспортной задачи

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

В трех пунктах отправления  имеется однородный груз в количестве  соответственно. Этот груз нужно доставить пяти заказчикам . Потребности в грузе в каждом пункте  известны и равны  соответственно. Известны также тарифы перевозки  - стоимость перевозки единицы груза из пункта  в пункт . Нужно найти такой план перевозок, при котором весь груз из пунктов потребления будет вывезен, потребности всех заказчиков будут удовлетворены, и при этом общая стоимость перевозки всего груза будет наименьшей. Данные в таблице,  в клетках которой проставлены элементы матрицы тарифов ; в последнем столбце таблицы указаны значения величин , в последней строке - значения величин .

 

                Заказчики

Пункты

4

9

2

5

3

 23

4

6

2

1

8

 25

6

2

3

4

5

 17

 14

 10

 16

 10

 15

 

Требуется:

  • Составить математическую модель задачи.
  • Найти оптимальное решение транспортной задачи методом потенциалов.

Решение задачи

Математическая модель задачи

Обозначим через  количество груза, перевозимого от  поставщика  потребителю. Тогда общая стоимость перевозок равна:

Ограничения для поставщиков:

Ограничения для потребителей:

Объем суммарных поставок любого поставщика к потребителю не может быть отрицательным числом, поэтому справедливы ограничения:   

Проверка задачи на закрытость модели

Стандартная транспортная задача разрешима только в том случае, когда выполняется условие баланса:

В нашем случае:

Модель транспортной задачи закрытая.

Метод минимального элемента

Заполняем таблицу по правилу минимального элемента.

Просматривая таблицу замечаем, что наименьшие затраты соответствуют маршруту , поэтому в клетку помещаем . В этом случае 4-й столбец в расчет не принимается. Просматриваем оставшиеся таблицы клетки. Наименьший тариф имеет клетка

Далее действуя по аналогичной схеме:

Метод потенциалов

 Решать задачу будем методом потенциалов. Число занятых клеток должно быть . Потенциал 1-й строки принимаем равным нулю. После этого мы можем вычислить остальные потенциалы (если известны потенциал и тариф занятой клетки, то из соотношения v + u =c легко определить неизвестный потенциал).

Найдем оценки свободных клеток по формуле: 

S ( 1, 1)= 4-( 0-1)=  5

S ( 1, 2)= 9-( 0+ 0)=  9

S ( 1, 4)= 5-( 0-4)=  9

S ( 2, 2)= 6-( 5+ 0)=  1

S ( 2, 3)= 2-( 5+ 2)= -5

S ( 3, 1)= 6-( 2-1)=  5

S ( 3, 3)= 3-( 2+ 2)= -1

S ( 3, 4)= 4-( 2-4)=  6

Для клетки ( 2, 3) с минимальной отрицательной оценкой строим цикл.

Перемещаем груз, равный 1 из вершин, помеченных минусом к вершинам цикла, помеченным плюсом.

Вычисляем потенциалы:

Найдем оценки свободных клеток по формуле

S ( 1, 1)= 4-( 0+ 4)=  0

S ( 1, 2)= 9-( 0+ 0)=  9

S ( 1, 4)= 5-( 0+ 1)=  4

S ( 2, 2)= 6-( 0+ 0)=  6

S ( 2, 5)= 8-( 0+ 3)=  5

S ( 3, 1)= 6-( 2+ 4)=  0

S ( 3, 3)= 3-( 2+ 2)= -1

S ( 3, 4)= 4-( 2+ 1)=  1

 

Для клетки ( 3, 3) с минимальной отрицательной оценкой строим цикл.

Перемещаем груз, равный 7 из вершин, помеченных минусом к вершинам цикла, помеченным плюсом.

Вычисляем потенциалы:

Найдем оценки свободных клеток по формуле

S ( 1, 1)= 4-( 0+ 4)=  0

S ( 1, 2)= 9-( 0+ 1)=  8

S ( 1, 4)= 5-( 0+ 1)=  4

S ( 2, 2)= 6-( 0+ 1)=  5

S ( 2, 5)= 8-( 0+ 3)=  5

S ( 3, 1)= 6-( 1+ 4)=  1

S ( 3, 4)= 4-( 1+ 1)=  2

S ( 3, 5)= 5-( 1+ 3)=  1

Оценки свободных клеток не отрицательны, следовательно, полученный план является оптимальным:

Ответ

Пункт      поставляет 8 единиц груза в пункт   и 15 единиц груза в пункт  

Пункт   поставляет 14 единиц груза в пункт  , 1 единицу груза в пункт  и 10 единиц груза в пункт

Пункт      поставляет 10 единиц груза в пункт   и 7 единиц груза в пункт  

Минимальные транспортные издержки оптимального плана:


Сохранить ссылку на страницу в социальной сети:

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


@100task.ru 2009-2017 Москва Спб НН