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

Итак, чтобы получить максимальную прибыль 4 456 000 рублей при имеющихся запасах сырья и существующей трудоемкости получаемой продукции, предприятию следует производить 160 единиц товара вида А, 0 – вида В, 20 – вида С, 429 - вида F и 114 – вида G.

3. ПРИМЕНЕНИЕ ТЕОРИИ ТРАНСПОРТНОЙ ЗАДАЧИ К РАБОТЕ ООО «ДУБРОВЧАНКА+»

3.1 Сущность транспортной задачи

Транспортная

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

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

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

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

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

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

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

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

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

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

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

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

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

xij - количество продукции, перевозимой из пункта отправления Ai в пункт назначения Bj [ед. прод.],

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

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

Рассмотрим экономико-математическую модель прикрепления пунктов отправления к пунктам назначения. Имеются m пунктов отправления груза и объемы отправления по каждому пункту a1, a2 , .,am . Известна потребность в грузах b1, b2 , .,bn по каждому из n пунктов назначения. Задана матрица стоимостей доставки по каждому варианту cij , . Необходимо рассчитать оптимальный план перевозок, т.е. определить, сколько груза должно быть отправлено из каждого i-го пункта отправления (от поставщика) в каждый j-ый пункт назначения (до потребителя) xij с минимальными транспортными издержками.

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

Таблица 3.1

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

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

(3.1)

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

(3.2)

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

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

, (3.3)

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

, (3.4)

Суммарные объемы отправления должны равняться суммарным объемам назначения (3.1). Должно выполняться условие неотрицательности переменных: , , . Перевозки необходимо осуществить с минимальными транспортными издержками (функция цели):

(3.5)

Вместо матрицы стоимостей перевозок (cij) могут задаваться матрицы расстояний. В таком случае в качестве целевой функции рассматривается минимум суммарной транспортной работы. Как видно из выражения (3.1), уравнение баланса является обязательным условием решения транспортной задачи. Поэтому, когда в исходных условиях дана открытая задача, то ее необходимо привести к закрытой форме. В случае, если

- потребности по пунктам назначения превышают запасы пунктов отправления, то вводится фиктивный поставщик с недостающим объемом отправления;

- запасы поставщиков превышают потребности потребителей, то вводится фиктивный потребитель с необходимым объемом потребления.

 Скачать реферат