Курсовая работа: Сущность и использование транспортных задач

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

Под термином «транспортные задачи» понимается широкий круг задач не только транспортного характера. Общим для них является, как правило, распределение ресурсов, находящихся у mпроизводителей (поставщиков), по nпотребителям этих ресурсов. Различают два типа транспортных задач: но критерию стоимости (план перевозок оптимален, если достигнут минимум затрат на его реализацию) и по критерию времени (план оптимален, если на его реализацию затрачивается минимум времени) [2].

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

- прикрепление потребителей ресурса к производителям;

- привязка пунктов отправления к пунктам назначения;

- взаимная привязка грузопотоков прямого и обратного направлений;

- отдельные задачи оптимальной загрузки промышленного оборудования;

- оптимальное распределение объемов выпуска промышленной продукции между заводами-изготовителями и др.

где n – количество пунктов отправления,

m – количество пунктов назначения,

а_i – запас продукции в пункте отправления A_i () [ед. прод.],

b_j – спрос на продукцию в пункте назначения B_j () [ед. прод.],

c_ij – тариф (стоимость) перевозки единицы продукции из пункта отправления A_i в пункт назначения B_j [руб. / ед. прод.],

x_{ij -} количество продукции, перевозимой из пункта отправления A_i в пункт назначения B_j [ед. прод.],

L(Х) – транспортные расходы на перевозку всей продукции [руб.].

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

Рассмотрим экономико-математическую модель прикрепления пунктов отправления к пунктам назначения. Имеются mпунктов отправления груза и объемы отправления по каждому пункту a₁ , a₂ ,...,a_m . Известна потребность в грузах b₁ , b₂ ,...,b_n по каждому из nпунктов назначения. Задана матрица стоимостей доставки по каждому варианту c_ij , . Необходимо рассчитать оптимальный план перевозок, т.е. определить, сколько груза должно быть отправлено из каждого i-го пункта отправления (от поставщика) в каждый j-ый пункт назначения (до потребителя) x_ij с минимальными транспортными издержками.

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

Таблица 3.1

Исходные данные

Транспортная задача называется закрытой, если суммарный объем отправляемых грузов равен суммарному объему потребности в этих грузах по пунктам назначения :

(3.1)

Если такого равенства нет (потребности выше запасов или наоборот), запасу называют открытой, т.е.:

(3.2)

Для написания модели необходимо все условия (ограничения) и целевую функцию представить в виде математических уравнении.

Все грузы из i-х пунктов должны быть отправлены, т.е.:

, (3.3)

Все j-е пункты (потребители) должны быть обеспечены грузами в плановом объеме: