Транспортная задача. Применение транспортных задач

Тема: Транспортная задача. Применение транспортных задач.

Цели: рассмотреть решение методом северо-западного угла; рассмотреть решение методом минимального элемента; решить транспортную задачу повышенной сложности; развивать познавательный потенциал студентов, умения сравнивать, анализировать, делать выводы; воспитание дисциплинированности, целеустремленности.

Ход урока

1. Организационное начало.

1. Приветствие.

2. Работа с рапортичкой.

- Давайте проверим явку на уроке (по рапортичке и журналу проверяю отсутствующих).

1. Работа по осмыслению и усвоению нового материала.

1. Сообщение темы и цели урока.

- Тема нашего урока: Транспортная задача. Применение транспортных задач.

- Как вы думаете, что мы будем сегодня изучать на уроке? (ответ учащихся).

2. Первичное восприятие нового материала.

3. Работа с материалом урока.

Целью транспортных методов является определение наилучших путей перевозки груза из нескольких пунктов снабжения (производства) в несколько пунктов назначения (потребления), обеспечивающих наименьшие суммарные затраты по производству и транспортированию товаров. Задача рассматривается как однопродуктовая, т.е. решается применительно к одному или группе однотипных (взаимозаменяемых) товаров. Диктуется это требование тем, что объемы производства разных товаров в различных пунктах производства, а главное – спрос в различных пунктах потребления, сильно различаются.

Обычно в качестве исходных данных задаются мощности каждого из источников товара и потребности в этом товаре (спрос) каждого из пунктов потребления. В качестве пунктов снабжения и потребления могут рассматриваться также центры дистрибьюции, склады, магазины, существующие или предполагаемые к созданию. В качестве путей перевозки груза – транспортные магистрали, существующие или проектируемые, использующие различные виды транспорта.

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

Как и в линейном программировании, процесс решения транспортной задачи с использованием специальных методов начинается с определения допустимого начального решения, которое затем шаг за шагом (итерационный процесс) улучшается до оптимального решения. Транспортные методы просты для решения задач «вручную», ограничителем может являться только размерность задачи.

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

Планом перевозок называют совокупность всех перевозок между парами пунктов

«производитель – потребитель».

Задача может быть поставлена и решена путем построения транспортной матрицы

или построения транспортной сети. Будем использовать применяемую чаще первую – матричную постановку задачи.

Рассмотрим решение на простейшем примере.

Пример. Известно, что фирма производит свою продукцию в трех филиалах, имеющих следующие производственные мощности:

А – 100 ед. продукции;

В – 300 ед. продукции;

С – 300 ед. продукции.

Потребители этой продукции сосредоточены в трех пунктах со следующим спросом:

D – 300 ед. продукции;

Е – 200 ед. продукции;

F – 200 ед. продукции.

Данные о стоимости перевозки единицы груза представлены в таблице 1 (тыс. руб./ед.

продукции):

Требуется построить оптимальный план перевозок продукции, минимизирующий затраты на перевозки.

Обратим внимание на то, что задача сбалансирована, т. е. суммарные мощности производителей равны суммарной потребности потребителей 700 ед.

Решение. Для решения задачи составляется транспортная матрица (Табл. 2), как показано далее, при этом мощности и потребности выражены в единицах продукции, а затраты – в денежных единицах на перевозку единицы продукции из пункта производства в пункт потребления.

Метод «Северо-западного угла» для построения первого допустимого решения

задачи.

Правило «Северо-западного угла» – это систематизированная процедура назначения

величин перевозок из пункта производства (строка) в пункт потребления (столбец), которая

требует, чтобы определение числа перевозимых единиц товара начиналось в левом верхнем

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

1) следует израсходовать всю мощность завода-изготовителя (в строке) прежде, чем

двинуться вниз к следующей строке;

2) следует удовлетворить потребность каждого потребителя в колонке прежде, чем двинуться к следующей колонке вправо;

3) в завершение следует проверить, что все потребности удовлетворены, а мощности

полностью использованы (израсходованы).

Заметим, что правило «Северо-западного угла» – не единственный способ построения

первого допустимого плана.

В рассматриваемом примере в соответствии с этим правилом требуется сделать пять

шагов, чтобы получить начальный план перевозок:

1) назначается 100 единиц для перевозки из А в D (израсходовав всю мощность А);

2) назначается 200 единиц для перевозки из В в D (удовлетворив всю потребность D);

3) назначается 100 единиц для перевозки из В в Е (израсходовав окончательно мощность В);

4) назначается 100 единиц для перевозки из С в Е (удовлетворив полностью потребность Е);

5) назначается 200 единиц для перевозки из С в F (израсходовав окончательно всю мощность С и удовлетворив полностью потребность F).

Первый допустимый (опорный) план перевозок, показан в таблице 3:

Можно подсчитать суммарную стоимость перевозок в соответствии со сделанными

назначениями. Расчет приведен в таблице 4

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

1. Итог урока.

1. Обобщающая беседа.

1. Задавание на дом.