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

 

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

Под термином «транспортные задачи» понимается широкий круг задач не только транспортного характера. Общим для них является, как правило, распределение ресурсов, находящихся у 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-е пункты (потребители) должны быть обеспечены грузами в плановом объеме:

 

, (3.4)

 

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

 

(3.5)

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

L₁₍X)=-L(Х),

 

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

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

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

 

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

 

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

 

 

C_ij =

 

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

Решение:

В качестве начального этапа построения ЭММ исходный объем перевозки от i-го поставщика к j-му потребителю обозначим через аij. Заданные мощности поставщиков и спросы потребителей накладывают ограничения на значения неизвестных a_ij. Так, например, объем груза, отправляемого с первого склада, должен быть равен мощности этого поставщика. Поэтому уравнения баланса имеют вид:

 

 

А чтобы спрос каждого из потребителей был удовлетворен, подобные уравнения баланса имеют вид:

 

 

При этом суммарные затраты F на перевозку составят:

 

F=143а₁₁+135а₁₂+1400а₁₃+104а₂₁+178а₂₂+1362а₂₃+102а₃₁+180а₃₂+1360а₃₃

 

Для решения задачи воспользуемся пакетом MS Excel приложения Microsoft Office, расположив данные следующим образом (выделенные клетки – искомые значения переменных):

 

 

При этом целевая функция будет задана выражением:

 

=В4*У5+А4*П5+В6*У7+А6*П7+В8*У9+А8*П9+Р4*Ш5+Р6*Ш7+Р8*

Ш9

 

А система ограничений примет вид:

 

44=E5+E7+E9

23=G5+G7+G9

5=I5+I7+I9

20=E5+G5+I5

14=E7+G7+I7

38=E9+G9+I9

 

Выберем в меню «Сервис» команду «Поиск решения» и заполним открывшееся окно:

 

 

После этого в диалоговом окне «Параметры» установим флажок в ячейку «Линейная модель» и выберем кнопку «Выполнить».

 

В результате решения получаем оптимальный план перевозок:

Мощности поставщиков	Мощности потребителей			Запасы, к-т
	ООО «Пензмебкредит»	ЗАО «Кузнецк-дизайн»	ТД «Столица»
С1	143 0	135 20	1400 0	20
С2	104 14	178 0	1362 0	14
С3	102 30	180 3	1360 5	38
Потребность, к-т	44	23	5	72

 

Он означает, что с первого склада потребителю ЗАО «Кузнецк-дизайн» будет поставлено 20 единиц продукции, со второго – 14 единиц заказчику ООО «Пензмебкредит». Недопоставленные в соответствии с объемом спроса этого потребителя 30 единиц продукции будут привезены с третьего склада. Оттуда же будет поставлено 3 единицы продукции в ЗАО «Кузнецк-дизайн» и 5 единиц – в ТД «Столица». Затраты на транспортировку по данному плану составят 14 556 рублей.

 

ЗАКЛЮЧЕНИЕ

 

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

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

Изученные теоретические положения были применены на конкретном предприятии – ООО «Дубровчанка+» в построении ЭММ по определению оптимального ассортимента продукции – был рассчитан такой план производства, при котором наблюдалась бы максимальная прибыль при располагаемом запасе ресурсов и трудоемкости технологического процесса.

Постановка и решение транспортной задачи на основе статистических данных ООО «Дубровчанка+» позволила определить оптимальный минимизирующий расходы план перевозок продукции к потребителям.

 

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1. Алесинская Т.В. Учебное пособие по решению задач по курсу «Экономико-математические методы и модели». Таганрог: Изд-во ТРТУ, 2002.

2. Исследование операций в экономике. По ред. Н.Ш. Кремера. – М.: Банки и биржи, ЮНИТИ, 2010.

3. А.И. Орлов Теория принятия решений: Учебное пособие. - М.: Издательство «Март», 2004.

[1] Основные виды изготавливаемой продукции с их габаритными размерами представлены в Таблице 1.

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