Сущность и использование транспортных задач (стр. 3 из 4)
Решение:
Обозначим изделие каждого вида соответственно a, b, c, f, g. Тогда на изготовление всей продукции уйдет (1,5a+0,08b+0,06c+0,2f+0,2g) м3 древесины Iвида и (0,2a+0,05b+0,04c+0,2f+0,1g) м3 древесины IIвида. Так как запасы этих ресурсов не превышают 350 и 130 м3 соответственно, то
1,5a+0,08b+0,06c+0,2f+0,2g ≤ 350
0,2a+0,05b+0,04c+0,2f+0,1g ≤ 130
Трудоемкость производства этих изделий равна
(3,3a+0,4b+0,3c+1f+1,2g). Значит,
3,3a+0,4b+0,3c+1f+1,2g≤ 1100
Итак, система ограничений имеет вид:
А прибыль будет выражена функцией
F=13000a+1300b+1200c+4300f+4450g
Чтобы найти решение задачи, воспользуемся MSExcel.
Целевую функцию зададим выражением:
=13000*A2+1300*B2+1200*C2+4300*F2+4450*G2
А систему ограничений так:
=1,5*A2+0,08*B2+0,065*C2+0,2*F2+0,2*G2
=0,2*A2+0,05*B2+0,04*C2+0,2*F2+0,1*G2
=3,3*A2+0,4*B2+0,3*C2+1*F2+1,2*G2
Открыв в меню «Сервис» команду «Поиск решения», заполним открывшееся окно: установим целевую ячейку, равную максимальному значению, определим ячейки-переменные, значения которых искомы, установим систему ограничений по имеющимся запасам сырья и располагаемой трудоемкости.
После этого в окне «Параметры» установим флажок в ячейку «Линейная модель» и выберем кнопку «Выполнить».
В результате решения получаем данные об оптимальном ассортименте продукции:
| Переменные | ||||
| 160 | 0 | 20 | 429 | 114 |
| функция цели: | 4456000 | |||
| 349,9 | 350 | |||
| 130 | 130 | |||
| 1099,8 | 1100 | |||
Итак, чтобы получить максимальную прибыль 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), уравнение баланса является обязательным условием решения транспортной задачи. Поэтому, когда в исходных условиях дана открытая задача, то ее необходимо привести к закрытой форме. В случае, если
- потребности по пунктам назначения превышают запасы пунктов отправления, то вводится фиктивный поставщик с недостающим объемом отправления;
- запасы поставщиков превышают потребности потребителей, то вводится фиктивный потребитель с необходимым объемом потребления.
Варианты, связывающие фиктивные пункты с реальными, имеют нулевые оценки. После введения фиктивных пунктов задача решается как закрытая.
Транспортным задачам присущи следующие особенности:
- распределению подлежат однородные ресурсы;
- условия задачи описываются только уравнениями;
- все переменные выражаются в одинаковых единицах измерения;
- во всех уравнениях коэффициенты при неизвестных равны единице;
- каждая неизвестная встречается только в двух уравнениях системы ограничений.
Транспортные задачи могут решаться симплекс-методом. Однако перечисленные особенности позволяют для транспортных задач применять более простые методы решения.
Опорный план является допустимым решением транспортной задачи и используется в качестве начального базисного решения при нахождении оптимального решения методом потенциалов. Существует три метода нахождения опорных планов: метод северо-западного угла, метод минимального элемента и метод Фогеля. «Качество» опорных планов, полученных этими методами, различается: в общем случае метод Фогеля дает наилучшее решение (зачастую оптимальное), а метод северо-западного угла – наихудшее.