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

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

(3.5)

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

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

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

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

Транспортным задачам присущи следующие особенности:

- распределению подлежат однородные ресурсы;

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

- все переменные выражаются в одинаковых единицах измерения;

- во всех уравнениях коэффициенты при неизвестных равны единице;

- каждая неизвестная встречается только в двух уравнениях системы ограничений.

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

Опорный план является допустимым решением транспортной задачи и используется в качестве начального базисного решения при нахождении оптимального решения методом потенциалов. Существует три метода нахождения опорных планов: метод северо-западного угла, метод минимального элемента и метод Фогеля. «Качество» опорных планов, полученных этими методами, различается: в общем случае метод Фогеля дает наилучшее решение (зачастую оптимальное), а метод северо-западного угла – наихудшее.

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

1. Диагональный метод, или метод северо-западного угла. При этом методе на каждом шаге построения первого опорного плана заполняется левая верхняя клетка (северо-западный угол) оставшейся части таблицы. При таком методе заполнение таблицы начинается с клетки неизвестного x11 и заканчивается в клетке неизвестного xmn , т. е. идет как бы по диагонали таблицы перевозок.

2. Метод наименьшей стоимости. При этом методе на каждом шаге построения опорного плана первою заполняется та клетка оставшейся части таблицы, которая имеет наименьший тариф. Если такая клетка не единственная, то заполняется любая из них[2] .

Кроме рассмотренных выше способов иногда используется, так называемый метод Фогеля. Суть его состоит в следующем: в распределительной таблице по строкам и столбцам определяется разность между двумя наименьшими тарифами. Отмечается наибольшая разность. Далее в строке (столбце) с наибольшей разностью заполняется клетка с наименьшим тарифом. Строки (столбцы) с нулевым остатком груза в дальнейшем в расчет не принимаются. На каждом этапе загружается только одна клетка. Распределение груза производится, как и ранее.

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

В этом случае в модель вместо искомой целевой функции L(Х) вводится целевая функция

L1( X)=-L(Х),

в которой тарифы умножаются на (-1). Таким образом, максимизация L(Х) будет соответствовать минимизации L1 (Х) [2]. Если в задаче идет речь о том, что из каждого пункта отправления можно перевозить продукцию нескольких видов, то при построении модели можно использовать один из следующих вариантов:

- каждому виду продукции должна соответствовать одна транспортная матрица;

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

3.2 Решение транспортной задачи на примере ООО «Дубровчанка+»

Применяя теорию транспортной задачи к показателям работы ООО «Дубровчанка +», составим следующую транспортную задачу. Итак, на трех складах предприятия (назовем их С1 , С2 , С3 ) сосредоточена продукция вида А в количествах 20, 14 и 38 единиц соответственно. Этот груз необходимо перевезти трем заказчикам – ООО «Пензмебкредит», ЗАО «Кузнецк-дизайн» и ТД «Столица» в количествах 44, 23, 5 единиц соответственно. Тарифы перевозок единицы груза каждого из складов потребителям задаются матрицей:


Cij =

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

Решение:

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