Министерство образования Российской Федерации
Ростовский государственный университет
ЛОГИСТИКА
Методическое пособие по проведению практических занятий
для студентов экономического факультета
Специальность 061100 – «Менеджмент организации»
Выпуск 1. Транспортная логистика
Ростов-на-Дону
Печатается по решению кафедры теории и технологий менеджмента
экономического факультета РГУ
Протокол № от марта 2003 г.
Автор: канд. техн. наук, доц. Григан А.М.
Научный редактор: д-р экон. наук, проф. Чернышев М.А.
Ответственный за выпуск: д-р экон. наук, проф. Солдатова И.Ю.
Рецензент: канд. воен. наук, доц. Болошин Г.А.
Решение транспортной задачи
Цель транспортной логистики – обеспечение доставки грузов потребителю в заданном объеме, в заданный срок и с минимальными затратами. Рассмотрим классический вариант транспортной задачи – рациональное планирование перевозок, с точки зрения поиска оптимального способа взаимодействия поставщиков материальных ресурсов с потребителями, обеспечивающего минимальную сумму транспортных расходов.
|
|
Постановка задачи: имеется “m” пунктов отправления А1, А2, …, А m, в которых сосредоточены запасы каких-то однородных грузов в количестве соответственно а 1 , а 2 , …, а m единиц. Имеется “n” пунктов назначения В1, В2, …, Вn, подавших заявки соответственно на b1 , b2, …, bn единиц груза. Сумма всех заявок равна сумме всех запасов: . Известны стоимости сij перевозки единицы груза от каждого пункта отправления Аi до каждого пункта назначения Вj (i = 1, 2,.., m; j = 1, 2, …, n).
Все числа сij, образующие прямоугольную таблицу (матрицу), заданы: .
Считается, что стоимость перевозки нескольких единиц груза пропорциональна их числу.
Требуется: составить такой план перевозок (откуда, куда и сколько единиц везти), чтобы все заявки были выполнены, а общая стоимость всех перевозок была минимальна.
Обозначим xij – количество единиц груза, отправляемого из i-го пункта отправления Ai в j-й пункт назначения BJ. Неотрицательные переменные xij можно тоже записать в виде матрицы .
Совокупность чисел xij будем называть “планом перевозки”, а сами величины xij – “перевозками”.
Переменные xij должны удовлетворять следующим условиям.
1. Суммарное количество груза, направляемого из каждого пункта отправления во все пункты назначения, должно быть равно запасу груза в данном пункте. Это можно записать в виде:
2. Суммарное количество груза, доставляемого в каждый пункт назначения из всех пунктов отправления, должно быть равно заявке, поданной данным пунктом. Запишем это в виде:
3. Суммарная стоимость всех перевозок, то есть сумма величин xij умноженных на соответствующие стоимости сij должна быть минимальной:
|
|
Будем называть любой план перевозок допустимым, если он удовлетворяет условиям (1) и (2) – все заявки удовлетворены, все запасы исчерпаны.
Допустимый план будем называть опорным, если в нем отличны от нуля не более m+n+1 базисных перевозок, а остальные перевозки равны нулю.
План будем называть оптимальным, если он, среди допустимых планов, приводит к минимальной суммарной стоимости перевозок (F = min)
Для нахождения оптимального плана строится транспортная таблица, состоящая из “m” строк и “n” столбцов. В правом верхнем углу каждой клетки записывается стоимость сij перевозки единицы груза из Аi в Вj, а в центре клетки записывается сама переменная xij. Для удобства вычислений, к транспортной таблице добавляется вспомогательный столбец, содержащий величины запасов грузов в пунктах отправления, и вспомогательная строка, содержащая величины заявок, поданных пунктами назначения.
Для решения задачи могут применяться различные методы, такие как: метод линейного программирования; метод потенциалов; сетевой метод; венгерский метод; метод ветвей и границ; метод северо-западного угла.