Решение транспортной задачи. Министерство образования Российской Федерации

Министерство образования Российской Федерации

Ростовский государственный университет

ЛОГИСТИКА

Методическое пособие по проведению практических занятий

для студентов экономического факультета

Специальность 061100 – «Менеджмент организации»

Выпуск 1. Транспортная логистика

Ростов-на-Дону

Печатается по решению кафедры теории и технологий менеджмента

экономического факультета РГУ

Протокол № от марта 2003 г.

Автор: канд. техн. наук, доц. Григан А.М.

Научный редактор: д-р экон. наук, проф. Чернышев М.А.

Ответственный за выпуск: д-р экон. наук, проф. Солдатова И.Ю.

Рецензент: канд. воен. наук, доц. Болошин Г.А.

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

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

Постановка задачи: имеется “m” пунктов отправления А₁, А₂, …, А _m, в которых сосредоточены запасы каких-то однородных грузов в количестве соответственно а ₁ , а ₂ , …, а _m единиц. Имеется “n” пунктов назначения В₁, В₂, …, В_n, подавших заявки соответственно на b₁ , b₂, …, b_n единиц груза. Сумма всех заявок равна сумме всех запасов: . Известны стоимости с_ij перевозки единицы груза от каждого пункта отправления А_i до каждого пункта назначения В_j (i = 1, 2,.., m; j = 1, 2, …, n).

Все числа с_ij, образующие прямоугольную таблицу (матрицу), заданы: .

Считается, что стоимость перевозки нескольких единиц груза пропорциональна их числу.

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

Обозначим x_ij – количество единиц груза, отправляемого из i-го пункта отправления A_i в j-й пункт назначения B_J. Неотрицательные переменные x_ij можно тоже записать в виде матрицы .

Совокупность чисел x_ij будем называть “планом перевозки”, а сами величины x_ij – “перевозками”.

Переменные x_ij должны удовлетворять следующим условиям.

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

2. Суммарное количество груза, доставляемого в каждый пункт назначения из всех пунктов отправления, должно быть равно заявке, поданной данным пунктом. Запишем это в виде:

3. Суммарная стоимость всех перевозок, то есть сумма величин x_ij умноженных на соответствующие стоимости с_ij должна быть минимальной:

Будем называть любой план перевозок допустимым, если он удовлетворяет условиям (1) и (2) – все заявки удовлетворены, все запасы исчерпаны.

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

План будем называть оптимальным, если он, среди допустимых планов, приводит к минимальной суммарной стоимости перевозок (F = min)

Для нахождения оптимального плана строится транспортная таблица, состоящая из “m” строк и “n” столбцов. В правом верхнем углу каждой клетки записывается стоимость с_ij перевозки единицы груза из А_i в В_j, а в центре клетки записывается сама переменная x_ij. Для удобства вычислений, к транспортной таблице добавляется вспомогательный столбец, содержащий величины запасов грузов в пунктах отправления, и вспомогательная строка, содержащая величины заявок, поданных пунктами назначения.

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