Методическая разработка урока «Транспортная задача»

• Повторить составление опорного плана транспортной задачи
• Рассмотреть решение методом северо-западного угла
• Рассмотреть решение методом минимального элемента
• Решить транспортную задачу повышенной сложности в среде MS Excel
• Развивать познавательный потенциал студентов, умения сравнивать, анализировать, делать выводы.
• Воспитание дисциплинированности, целеустремленности.

Оснащение урока: презентация, интерактивная доска, карточки.

Задача ТЗ ассоциируется с перемещением груза от поставщиков к потребителям. Решение данной задачи позволяет разработать наиболее рациональные пути и способы транспортирования товаров, устранить чрезмерно дальние, встречные, повторные перевозки. Всё это сокращает время продвижения товаров, уменьшает затраты предприятий и фирм, связанные с осуществлением процессов снабжения сырьём, материалами, топливом, оборудованием и т. д. Вместе с тем алгоритм и методы решения транспортной задачи могут быть использованы при решении некоторых задач, не имеющих ничего общего с транспортировкой груза. Всё зависит от того, как интерпретируются так называемые тарифы. Так, например, при решении задачи обеспечения материальными ресурсами при производстве продукции товары, находящиеся на складе, физически не перемещаются, но при этом увеличивается их стоимость в результате расходов на хранение. Таким образом, товар как бы перемещается во времени, а значит, задачу по минимизации расходов на осуществление процесса обеспечения ресурсами можно решить с помощью ТЗ. Впервые высказывание о важности решения задач линейного программирования и, в частности, ТЗ было сделано в прошлом веке. Тогда же были предложены методы решения этих задач. У истоков создания теории линейного программирования стоял русский учёный – Л. В. Канторович. Широкое практическое использование этой теории началось после появления вычислительных машин. Это связано с тем, что при реализации методов линейного программирования требуется выполнять многочисленные последовательные арифметические операции. Ошибка в одном действии приводила к неверному результату и поиску верного решения путём повторного утомительного расчёта.

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

На каждом предприятии есть отдел логистики. Его работа заключается в организации рационального процесса продвижения товаров от производителей к потребителям, создания инфраструктуры товародвижения.

Логисты обязательно должны уметь работать в Word, Excel, Access. Так как все эти знания вы имеете, то вполне можете работать логистами в дальнейшем.

Логистов иначе называют «транспортными богами».

Сегодня на уроке нам необходимо разобрать транспортную задачу,  научиться строить математическую модель этой задачи и решать ее.

Как всегда изучение теоретического материала будем сопровождать примерами.

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

А основное продвижение было сделано советским математиком и экономистом Леонидом Канторовичем.

В 1939 году к 26-летнему профессору-математику, обратились за консультацией сотрудники лаборатории планерного треста, которым нужно было решить задачу о наиболее выгодном распределении материала между станками. Эта задача сводилась к нахождению максимума линейной функции, заданной на многограннике. Максимум такой функции достигался в вершине, однако число вершин в этой задаче достигало миллиарда. Поэтому простой перебор вершин не годился. Леонид Витальевич писал: “оказалось, что эта задача не является случайной. Я обнаружил большое число разнообразных по содержанию задач, имеющих аналогичный математический характер: наилучшее использование посевных площадей, выбор загрузки оборудования, рациональный раскрой материала, распределение транспортных грузопотоков… Это настойчиво побудило меня к поиску эффективного метода их решения”. И уже летом 1939 года была сдана в набор книга Л.В.Канторовича “Математические методы организации и планирования производства”.

Поэтому иногда эта проблема называется транспортной задачей Монжа — Канторовича.

В 1975 году академик Л.В.Канторович и американец профессор Т.Купманс получили Нобелевскую премию по экономическим наукам за “вклад в разработку теории и оптимального использования ресурсов в экономике”.

Однородный груз, имеющийся в m пунктах отправления (производства) А1, А2, ..., Аm соответственно в количествах а1, а2, ..., аm единиц, требуется доставить в каждый из n пунктов назначения (потребления) В1, В2, ..., Вn соответственно в количествах b1, b2, ..., bn единиц. Стоимость перевозки (тариф) единицы продукции из Аi в Вj известна для всех маршрутов Ai, Bj и равна c_ij (i = 1, m; j = 1, n).

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

 

Чтобы мы могли решать данную задачу нам необходимо записать ее математическую модель.

Наша задача найти значения х, которые удовлетворяют системе ограничений и целевой функции.

При этом нам понадобятся несколько определений:

Определение: Построенный план называется опорным, если в нем отличны от нуля m+n-1 базисных перевозок, а остальные перевозки равны 0.

Определение: Опорный план называется оптимальным, если он приводит к минимальной суммарной стоимости перевозок.

Перейдем  к решению задачи.

Так как транспортная задача является задачей линейного программирования, то её можно решать симплекс-методом.

Условия задачи удобно располагать в таблице, вписывая в ячейки количество перевозимого груза из Аi в Bj груза X_ij ≥ 0, а в маленькие клетки – соответствующие тарифы C_ij.
 

 

Наша задача заполнить все клетки числами x_ij (количеством перевозимого товара) так, чтобы их сумма по строкам была равна а_i  , по столбцам -b_j.  Затем эти числа умножаем на стоимости перевозок C_ij и складываем. И эта сумма должна принимать минимальное значение.

Сущность метода заключается в том, что на каждом шаге заполняется левая верхняя (северо-западная) клетка оставшейся части таблицы, причем максимально возможным числом: либо полностью выносится груз из Аi, либо полностью удовлетворяется потребность Вj.

Процедура продолжается до тех пор, пока на каком-то шаге не исчерпаются запасы аi и не удовлетворятся все потребности bj.

Задача:  Нужно отправить груз из г.Пенза и г. Н.Ломов в три населенных пункта Мокшан, Наровчат и Пачелма. На складах имеется соответственно 220 и 180 т зерна, в указанные пункты соответственно требуется 160, 100, 140т зерна. Стоимость перевозки приведены в таблице.

Составить опорный план задачи методом северо-западного угла.

 

Все заявки удовлетворены, все запасы израсходованы.

Проверим, является ли полученный план опорным: количество ячеек с ненулевыми перевозками равно m+n-1 = 4.

Вычислим суммарную стоимость перевозок для построенного плана:

F = 1320

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

Задание. Составить опорный план задачи методом наименьшего элемента.

4.  Закрепление нового материала:   ответы на вопросы:

Выполнить проверку.

 

Решить последнюю задачу двумя способами.