Разработка и внедрение алгоритма управления развозкой готовой продукции (на примере пищевой промышленности Республики Армения) тема диссертации по экономике, полный текст автореферата

Автореферат диссертации по теме "Разработка и внедрение алгоритма управления развозкой готовой продукции (на примере пищевой промышленности Республики Армения)"

о*

-а

гпч^и\|'иг,из1лъ »шгиги ичьзьиь

«пиБРиизь игБЦ'УРи.ъ-Рг« зиририсмтъ «нииыири'и.'и ш/миччадл* 1гси^пмгц ъъгчтгчтц

слизиизиъг ¿иъгичсзп^э-зи.ъ ШИЛ!» 11Р'>ЗПГ>Ъ11РЬРПЬОЗи.Ъ

89&

¿ГП.ГЫР'Ш^ИЪ зъяиипм^-зиъ пьиз^п^э

Ц.00.00. - ЗЪтЁиш'^шрЬиишОДшЦшЪ 1ГЬ(аП1)1]Ьр ... , 1ГШи^ШЦ^и!^!]?^! Гр .. ..

ЗЧилЬишсфиииодшЪ рЬЦЪшйпф сфшшЦш'Ъ шшл^иЛф

Ьи^д^шЪ штЫ1Ш|ипитр_)шЪ иЬцишг^р

* -• • -•«» „ • ->.-, , _ ■

ЬрЦшЪ - 1996р.

ЕРЁВАНСКЖ ИНСТИТУТ НАРОДНОГО ХОЗЯЙСТВА

ОГАНЕСЯН ТАМАРА АВЕТИСОВНА

РАЗРАБОТКА И ВНЕДРЕНИЕ АЛГОРИТМА УПРАВЛЕНИЯ РАЗВОЗКОЙ ГОТОВОЙ ПРОДУКЦИИ (НА ПРИМЕРЕ ПИЩЕВОЙ ПРОМЫШЛЕННОСТИ РЕСПУБЛИКИ АРМЕНИЯ)

оЛ-00, и

Специальность с.00.08. Экономикс - математические метода

Автореферат диссертации на соискание ученой степени кандидата экономических нз.ук

Ереван - 1996

Работа выполнена на кафедре вычислительной техники и программирования Ереванского института народного хозяйства

Научный руководитель:

Официальные оппоненты:

доктор экономических наук, профессор А.Г.Аршакян

доктор экономических наук, профессор А.А.Митоян

кандидат экономических наук, доцент А.Б.Егиазарян

Ведущая организация:

Институт управления и экономических реформ при министерстве экономики РА

Защита состоится 1996г. в часов

на заседании объединенного Специализированного совета 014 Ереванского института народного хозяйства и института экономических наук HAH РА

'(аДрес: г-; Ерссгп - 37502-ё." Налбандяна-128, ауд. IOI) - -

С диссертацией можно ознакомиться в библиотеке Ереванского института народного хозяйства

Автореферат разослан J*^ ¿¿Дуг/МСЬ- 1996г.

Ученый секретарь Специализированного совета, кандидат экономических наук, доцент Г.М.Тертерян

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

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

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

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

Алгоритм ДП наряду с несомненными достоинствами, независимостью от вида целевой функции, числа и вида ограничений на управляющие переменные, имеют весьма существенные недостатки, а именно, с появлением дополнительных ограничений на фазовые переменные (параметры состояния) резко возрастают требования к памяти ЭВМ, что часто делает

невозможным решение задачи.

В настоящей работе предлагается точный алгоритм решения задач развозки (алгоритм коррекции), представляющий собой комбинацию методов ДП и "ветвей и границ'.

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

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

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

Внедрение результатов работы осуществлялось на Ермолкомби-нате N1 и хлебозаводе N7, где поставлена и решена задача оперативного управления процессами сбыта готовой продукции. Подученный годовой экономический эффект, от внедрения оптимальной схемы перевозок, выражается в экономии, подученной от снижения транспортных расходов вследствии сокращения суммарной протяжённости маршрутов. Для модкомбината N1 в 1991г. экономический эффект составил 400000 рублей, для хлебозавода N7 в 1995г. 9599000 драммов. Акты о внедрениях приложены к диссертации.

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

Апробация работы. Основные положения диссертационной рабо-

ты и ее результаты докладывались на VI, VII, IX, х научных сессиях профессорско-преподавательского состава Ереванского института народного хозяйства (Ереван, 1984, 1986, 1988, 1990, г.), на научной сессии при ВЛКСМ Арм. ССР (Ереван, 1988г.) и в опубликованных статьях по теме диссертации. Диссертационная работа состоит из введения, трех глав, выводов и приложения, общим объемом 151 страница машинописного текста, содержит 7 рисунков, 8 таблиц и список литературы.

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

В наиболее общем виде задачи развозки требуется определить маршруты М транспортных средств, осуществляющих развозку грузов из одного базового пункта в N пунктов назначения. Предполагается, что одно ураысяиртное средство может Ерзт1{ одновре-. менно несколько грузов в разные пункты. Для каждого транспортного средства могут быть заданы характеристики: грузоподъемность, грузовместимость, бюдает эксплуатационного времени, скорость и т.д. Для каждого груза заданы масса, объем, интервал времени, в течение которого груз должен быть доставлен в пункт назначения. Известны также попарные расстояния между этими пунктами.

Обычно рассматривается практически наиболее важный частный случай задачи развозки, в котором требуется посещение одного пункта только одним транспортным средством и один раз. Предполагается также, что грузы нельзя дробить. Максимальное число пунктов в марируте, как правило, ограничивается. Требуется минимизировать грузооборот при условии объязательной перевозки всех грузов.

Математическая модель задачи развозки может быть представлена в следующей форме:

1. Задано множество потребителей J - 11• и центральная база (завод), которой присвоен номер 0 ■

2. Известна несимметричная матрица С = II С (с ¿- ) II ■

I Е J 1) ( 0 } кратчайших расстояний межу всеми пунктами.

3. Определен маршрут 1^= (1к , 1к_2 , • • •, 11 1С (где ■ к - число звеньев маршрута) соответствующие последовательности пунктов (точек) 1К ) - • •, 1е . Если 1К= 10 маршрут превращается в замкнутый маршрут (цикл). Введено также понятие длины маршрута /_, ( Я к) ,для которого

ияк)=± са,

4. Имеется п транспортных средств (автомобилей) грузоподъемность» с/

5. Для каждого потребителя I заданы требования^на продукцию О (I ) и интервалы времени ее доставки . Предполагается, что в случае 0(1)^ с1 , в I - пункт совершается только одна поездка.

6. Зздано максимально возможное число пунктов в маршруте Ктах' .

7. Задано X - среднее время погрузки-разгрузки единицу груза, Ус -средняя скорость движения автомашин, ¡1 - величина допустимого простоя автомашины в случае ее прибытия1 в пуню раньше момента времени £ (I) .

Требуется построить систему замкнутых маршрутов [ К к ) , где = ( 0 )" 1 ' , I) 0 ) , при ограничениях

и^ЛЛО); 1*1 П^ = Ш : г,*£{1/-:М}. ; Ьг(0) + Г С С( ¿1, I] )/Ус +

+ га(1})4Ьи^; €е {//••,къ}; Л/ • <2>

1€(1,---,М) Кг

21 а(1] ) с! (3)

£=4 • ..

Кг«К„цх (4)

для всех Ъ - 1 / '' . При этом должен обеспечиваться ми-

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

Л ¿, ( ) —*- т I л

1 ^

Для точного решения задачи развозки применяются различные методы. К их числу относятся алгоритмы ЛП (целочисленного, смешанного и т.д.), ДД и метод "ветвей и границ'. В ряде случаев используются комбинации этих методов, так называемые, композитные алгоритмы.

Анализ существующих методов точного, приближенного решения задачи развозки, позволяет сделать вывод, что решение таких задач по прежнему остается весьма трудной проблемой, из-за большого числа различных ограничения. Гем большее значение имеет любое продвижение в этой области. В настоящей рэботе предлагается точный алгоритм решения задач развозки, основанный на комбинации методов ДП и "ветвей и границ". ( — •

Главным достоинством алгоритмов ДП являётся их нечувствительность к числу ограничений на управляющие переменные, а также независимость решений от вида целевой и ограничивающих функций. Основной недостаток состоит в чрезмерных требованиях к памяти и экспоненциальном возрастании трудоемкости. В свою очередь, эффективность метода "ветвей и гранил" снижается при введении дополнительных ограничений. Эффективность комбинированного алгоритма, очевидно, зависит от того, насколько удается использовать достоинства и нивелировать недостатки обоих методов.

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

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

Основная идея алгоритма рассмотрена во второй главе на примере решения многоразмерной задачи ДП , которая сама по себе имеет большое пратическое значение.

Рассмотрим задачу ДП с сепарабельными ограничениями на фазовые переменные (параметры состояний). Требуется нэйти вектор эс°- {ос° • • , Х° ) , максимизирующий сумму М функций:

P(xb'",xN)=I Pn(xJ (6)

n = i

причем нэ выбор значений переменных хп наложены условия: NJ

И bnmixn)« im . m=i---)M (7>

n = 1 >

xn e Z? ; ¿me Z ; »>

В соотношениях (6) - (8) Рп(хл) и hnmi^n^ со~ ответственно, целевая функция и функция, отражающая затраты m -го ресурса на стадии П : Z и Z0 - множества целых неотрицательных чисел.

Гак как искомый максимум, очевидно, будет зависеть от 'совокупности величин b rr\ . можно записать

N

т ах ЛРп(осп)= fN ■ • ■, 1М)

Используя принцип оптимальности, получим рекуррентные соотношения:

f,< Г^к+м >■■■>$ ) = max {Рк(хк) + + -

Хк <9>

^к,1 (хк)) ' ' ' > ¿>к + 1,М ~ ^кМ ( хк ^ J )

где fa= 0 и вектор начального состояния + ^ = (SN + iif ' ••• , SN+itM ) перед началом процесса распределения совпадает с вектором начальных ресурсов & = $ N ) .

Получена типичная задача ДП с размерностью М , а так как с увеличением размерности требования к памяти ЭВМ растут экспоненциально, решение задачи алгоритмом (9> для больших М практически невозможно. Следующая процедура, основанная нэ последовательности анализов, позволяет использовать для решения задачи (6) - <8> таблицу функций состояния одномерной задачи.

Итак, на основании функционального уравнения одномерной задачи

К ( 51<н,1 ) = т ах { Рк( хк) + /КЧ [ + м -" ^К1(хк)]1; /взО. = ^ ;

подучены таблицу /к (+ 1 ) для всех К , Я . Строим допустимый план задачи (6)-(8). На входе стадии К имеется подлежащий распределению вектор начальных ресурсов + / =

Всякое увеличение хк изменяет ресурс на выводе - -к- - ой стадии - -~-£к + Г)ГП ~ (""»к. V V

причем пределы изменения определяются условием

¿к,т ) ■ >м (10)

Если на стадии 1С в допустимый план включена переменная х 1{ , то величина функций" Р (х. к _ 4 у "• % )'1 ограничена' числом

= ( ^кл ) ш>

где значения выбираются из уже построенных таблиц. Оп-

ределив для всех допустимых х. к функции

Гк(хк)= Рк(хк) + (хк) (12)

и упорядочим их значения по убыванию, т.е. ' ^ У^2* ^ • •, где верхний индекс величина V к' ; I2- ' обозначает ее порядковый номер. Таким образом:

= гпах 1Рк(хк) + Г1<ч(эск)) (13)

к

где максимум берется по всем х.к , удовлетворяющим условиям (Ю).

Значение х^ , соответствующее ^к , включаем в допустимое решение, после чего делаем переход на стадию к - 4 Следовательно, построение допустимого решения проводится по

формуле (13), начиная со стадии N .

В процессе его получения на каждой стадии к фиксируем неотрицательные числа

л,< = - С); к = /,••■

N

Таким образом, величина 21 Л- к дает отклонение целевой функции Р(х) от верхней границу допустимых планов [f1 (считаем для удобства обозначений А N = 0 ). Допустимое решение

= {х.\- • , x.'N ) задачи (6)-(8) для функции hnm , определяющих затраты ресурсов, очевидно, существует всегда (например ос' - 0 ).

После того, как допустимое решение найдено и определен вектор Л = (Л^ j 1 • * , jLn ) отклонений от верхней границы, можно с помощью предлагаемой систематической процедуры построить оптимальное решение. улучшение допустимого плана начнем со стадии i , где i - •/ - наименьший номер положительной компоненты вектора Л , т.е. t е [3., • • •, N\> 0 } vt£ - 2 - ' ' ' = -Л i = 0} . На стадии I рассмотрим функцию

А - % - V"

и проверим неравенство

£

Л.<Л, + Лр. = z Л, (15)

S=1

Если-(15) не выполнено, дальнейший просмотр функции ^ 4 (С > >2) не нужен, поэтому переходим к стадии -2+4 . При выполнении неравенства (15), начиная со стадии £ — 1 , повторяем процедуру (13) получения допустимого решения. Для этого включаем в решение значение х'^ - Х-# и вычисляем на входе стадии £ - у , используя часть уже полученного допустимого решения.

' к = е

_ ю(Я)

Вычислим также

- ю -

Так как верхняя граница целевой функции у:ке найдена, для каждой новой стадии необходимо проверить условие

е , I

И у1, < И Лл (1б>

Если на некоторой стадии Р соотношение (16) не выполняется,

необходимо вернуться к стадии Р + 4 , восстановив величину г

^А 1 (а)

■Л. с- , и включить в план значение / , соответствующее

следующей по величине функции Тр + /.

При каждом переходе на стадию с большим номером удобно изменить порядковую индексацию функции а именно

= + " / ¿=/, V

Если задача решается на ЭВМ, это равносильно стиранию в пэмяти значения функции 1 и сдвигу строки функции , ^У , 4 ' на одну позицию влево. В этом случае Лк и А.к будут вычисляться по формуле (14), но -Л-к ф к .

Повторение процедуры (13) может привести к двум результатам-.либо соотношение (16) будет справедливо для Р = 1 (допустимое решение улучшено), либо после возвращения на стадию £ неравенство (15) перестанет выполняться. Это означает, что на стадии 2 улучшение решения невозмоашо,. поэтому необходим переход на стадию 2+1 . Очевидно, такой же переход делается, когда просмотрены все функции ^/ ' .

Нз стадии £ + 1 неравенство (15) примет вид

< Е Л ^ ¿-1

а на стадии N » N

Л1 < И <17)

Я = 1

Невыполнение условия (17) означает, что процедура поиска закончена и найдено оптимальное решение задачи (6)-(8), если же получено новое допустимое решение, его можно улучшить по вышеприведенной схеме, заменив компоненты вектора

соответствующими компонентами Л.'

Совокупность всех допустимых решений можно представить в виде дерева вариантнов, уздами которого являются компоненты вектора X.1 . Рассмотренный алгоритм дзет возможность получить оптимальное решение после просмотра лишь некоторых его ветвей. Ветви можно не просматривать, если следование по ним не приведет к улучшению решения. Кроме того, предложенная схема движения по ветвям дерева гарантирует, что оптимальное решение будет найдено.

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

+ < ) = ГП1 Л (к ( ¿к ,т ) )

т

к = 1,' ■■ , Ы-4 ■ т = •/, • • • , М

Нетрудно показать, что для объема необходимой памяти 0 в этом случае получим оценку

" С| =Ты-'?) + Г (2а, + 3") ; •■

ГТ)=) Н=1 'К

-максимально возможное

дии. ^

Отметим также, что в случае линейности функций Р и Ь дадглз' (6).-(8) сводится-клелочисжнной задаче ЛГГс неотряца- ~г тельными переменными.

В главе II Предложенный алгоритм используется для решения задач коммивояжера и развозки. В задаче коммивояжера требуется объехать множество городов 3 {0 } в произвольном порядке. Если рассматривать только элементарные маршруты, в которых вершины дважды не встречаются, можно записать соотношение

^ Ц ; £ Ф Ь • , 1г £ Як (18)

Требуется найти замкнутый маршрут К к , проходящий через каждую вершину ровно по одному разу, для которого

где -максимально возможное значение на к -ой ста-

L(R°n )= min L ( R° )

К

Определим далее функцию состояния Д. (¿j. , '' ' > е -t 1 ) ~ = f^ у г = 1 / •■ как минимально возможную длину маршрута

(i-г ,"'-> 'LZ-e+i /О; •

в котором точки t* , • • • , L* _ £ + i , являющиеся параметрами состояния, фиксированы, а остальные точки , 11

произвольны. Число параметров равно t . Обозначим также для ^ - •/ ; {,1г) = . Таким образом,

г г W

= nun [ 2L С (¿^ J + Z С )J

Яг-г sa/

В соответствии с принципом оптимальности имеем

//= mto С I +'J (19)

где - (iz„ g + j Li-t) ~ ребро, в котором после фикса-

ции параметров состояния вершина iz-€ является переменной. По аналогии с обозначениями (II) и (12) можно записать

ъ

где _ г (1г-v в отличие от (12), в обозначении для у>г необходимо указывать кроме переменной вершины соответствующую комбинацию параметров состояния. Это связано с наличием ограничений (18), согласно.которым производится отбор допустимых комбинаций. Отметим также, что гъ= min , где минимизацию необходимо проводить по всем таким комбинациям.

Уравнение (19) показывает, что процесс построения функций • ъ- j', N действительно представляется как многоста-. дивный. Функции должны вычисляться для всех комбинаций параметров, отличающихся друг от друга либо самими точками , либо порядком их следования.

Для I - 4 требования к памяти ЭВМ при решении задачи ком-

мивояжера пропорциональны ■ Использование предлагаемо-

го алгоритма позволяет резко сократить объем необходимой памяти. На каждой стадии ъ можно ограничиться вычислением N функций (г для N параметров состояния, полагая^что для стадий 1} • • •> Ъ - •/ эти функции уже построены. Три ячейки памяти нужны для заполнения У1г ,-Л.г и . Кроме того, требуется запомнить величины Т^для всех значений параметров и переменной. Если каждая такая функция зависит от одного параметра I ■=. 1 количество функции и значений переменной равно 2 N • Считая, что кэздое число запоминается в одной ячейке памяти, получим

С) - 3 ( N + 1) N

В случае увеличения числа параметров (/>•/) количество функций , требующих запоминания, растет очень быстро. Однако практика показала, что в допустимые и оптимальные маршрута, как правило, входят точки, принадлежащие некоторой окрестности, поэтому на каждой стадии целесообразно запомнить укороченную строку функции для точек из этой окрестности. Если же в процессе оптимизации выяснится, что указанных точек недостаточно, строку можно дополнить рядом новых значений.

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

- По сравнению с проблемой (6)-(8), использование предлагаемого алгоритма для задачи коммивояжера имеет некоторые особенности, связанные с наличием условия (18). Таблицы функций состояния, необходимые для оценки допустимых маршрутов, здесь индуктивно строятся, начиная с первой стадии, по тому же самому алгоритму. Отметим, также, что в решении не используется возможная симметрия элементов матрицы расстояний.

Ляя решения с помощью предлагаемого алгоритма задачи рэз-пила (I)-<5> можно использовать два достаточно очевидных пдноя стороны, ее нетрудно свести к обобщенной задаче >10 кокшьояжера разбиением начального пункта на М различных пунктов. Такой подход, несмотря кз его простоту, ведет к не-¡разданному .увеличению размерности, з значит, и времени реше- -

Другая возможность, реализованная в предложенном алгоритме, заключается в использовании наряду с матрицей С матрицы С' , элементы которой С (£ ,'}) связаны с элементами матрицы С следующим образом:

(20)

CU;¿)= Cil,0) + C(0,¿)

Действительно, нарушение условна (3)-(4) для маршрута ав-

томашины S равносильно требованию закончить маршрут и перейти

к маршруту^ к¿J^* D -ой автомашины. Тогда последнюю точку маршрута R.l<¿ и первую точку убудет связывать расстояние^ ^

С ( > 0) + £СО> Равное величине элемента С (±ks 1 < ) матрицы С . Таким образом, обращение к матрице С в момент ^ нарушения условий (3)-(4) дает возможность маршруты Rlc и ^ объединить в один.

Особенностью задач развозки является то, что при их оперативном решении интервалы времени доставки и элементы матриц С и С остаются постоянными. Следовательно, оцзночные функции, учитывающие параметры транспортной сети и интервалы [ t,'( i ), t (l) J можно построить заранее. Целесообразно также при лычислвнии функции состояния использовать условие (4), ог-р -л'П'вающее число пунктов в маршруте. Отметим далее, что наклонив спроса может привести к появлению фиксированных одноточечных маршрутов. Если, например, для точки i , 0.(i) > d эту точку придется включить в такой маршрут.

Основные результаты главы п нашли практическое применение при оперативном управлении процессами сбыта готовой продукции Ереванского молкомбинэта ni и хлебозавода n7.

Постановка и решениз задачи развозки пищепродукции по часовым графикам на примере транспортной сети г. Еревана составляет содержание третьей главы диссертации .

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

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

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

Сама процедура микрорайонирования свелась к статическому машинному эксперименту, во время проведения которого была решена серия задач развозки на полной транспортной сети с помощью приближенного алгоритма Кларка-Райти. Результаты эксперимента были сведены в таблицу, каждая строка которой имела следующий вид:

где I - номер точки, I = -/,•••, N

I - точка, включенная в один маршрут с точкой

0 к после решения задачи развозки (к = 1,2 , • • • )

Р; - количество задач из серии, закончивщихся таким к результатом.

Данные, в каждой строке таблицы, были упорядочены по величине Р^ , т.е. Р^ Р^ • • • . Затем с помощью этой таблицу проводилось объединение тороговых точек в микрорайоны, каждый из которых содержал но 40-45 пунктов спроса.

Задача развозки готовой продукции от молкомбината и хлебозавода до торгующих организаций ежедневно решается в оперативном режиме. Решение проводится последовательно для

каждого микрорайона. Вычислительное время микрорайон.-) превышает двух минут (ЕС 1036). Уменьшение суммарного пробега машин по сравнению с ранее применявшимся ручным планироьлниом составляет 10-12%.

В диссертации получены следующие основные результат'!,!:

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

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

-многоразмерной задзчи ДП с сепарабельными ограничениями на фазовые переменные:

- многоранцевой задачи целочисленного ЛП :

-задачи развозки и ее модификации.

К достоинствам предложенного метода относится нечувствительность к числу и виду ограничений как на управляющие, так и на фазовые переменные. Отметим также его инвариантность относительно свойств матрицы расстояний.

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

4. Составлены рабочие программы на языке Р L для задач маршрутизации. Вычислительные эксперименты показали большую эффективность предложенных алгоритмов.

5. Программы были использованы в оперативном режиме управления процессами сбыта готовой продукции Ермолкомбината ni и хлебозавода N7. Полученный годовой экономический эффект от внедрения оптимальных маршрутов перевозок готовой продукции Ермолкомбината ni составил в 1991г. около 400000 рублей, для хлебозавода N7 в 1995г. 9599000 дрзммов.

Основное содержание диссертации опубликовано в следующих работах.

1. Оганесян Т.А. Экономико-математическая модель определения оптимального плана развития и размещения производства скоропортящихся продуктов: Тезисы доклада vi научной сессии профессорско-преподавательского состава и аспирантов Института народного хозяйства. - Ереван, 1984.

2. Оганесян I.A. Математико-статистический анализ сбыто-

вых прдассов: Тезисы доклада vn научной сессии профессорско-преподавательского составз и аспирантов Института народного хозяйства. - Еревзн, 1986.

3. Оганесян Т.А. Об одном подходе к решению задачи оптимальной развозки молочной продукции: Тезисы доклада научной сессии при ВЛКСМ Арм. ССР - Ереван, 1388.

4. Оганесян Т.А. Некоторые вопросы оптимизации локальных задач производственно-транспортного комплекса ( на примере г. Еревана). Тезисы доклада ix научной сессии профессорско-преподавательского состава и аспирантов Института народного хозяйстве. - Ереван, 1988.

5. Оганесян Т.А., Зарецкий Л.С., Гендлер М.Б. Oö одном алгоритме решения многомерных задач о ранце. Московский институт стали и сплавов. - Москва, 1989. Деп. в ВИНИТИ, n 2SS7-B90.

6. Оганесян I.A. Решение многократных задач алгоритмом тип; "дерево поиска". Автоматизированные системы планирования и управления ВЦ Госплана Арм. ССР. - Ереван: Айастан, I99G.

7. Оганесян Т.А. О методах решений зздач оптимизации: Тезисы доклада х научной сессии профессорско-преподавательского состава и аспирантов Института народного хозяйства. - Ереван, 1990.

1Л1ГФП011 ,«»»«!*

llmttiujfununipjmli îiujuimml(li fc fcppnuyujtili С límpjpniinmjfiUJ JiAirçJip-libp^g 11Ыф* uijuu^bu Цп^Цшй 1пЬг{шфп|и|ГиЛ1 (uUrjpji jniüifuili himfuip Imp uiiqnp^ifaify шлЬцйпиТр:

Uju Juli^pfi u)p>]{iiijl|uilmip)jni1ip IpujuibnuT t lípuilmaf, пр ЦЬЪш-pnüuigijuiü ицш1л1л(прЦп^ 2n*-4tujuj4u>^>t>^j uligifшЪ фпцпиГ

pmpôpuAifiuf t mlimbunipjuAj 1ЩшЪип|г>р11°шЪ ЦпЪЦрЬт ¡^ЛяфрЪЬр}) jnièiiurt» hiuifuip Ъш[иштЬш|и10 wj1iuj{iu(i ifnrjb^Vifcp[i ï^fcpp, прпЪр шщшИт^ЬЪ i|bpg"ljm-ЦшЪ шртшг}ршЪр(1 uimui{b|ujqmj1> oqiniulptipmpjnL'b It inijjiu^ opjbljmf» «jnp-ùmAibnipjuilj шЛЛшршрйр juihmi^fcLnmpjn^: llju Ь{нГЬш{1Л1Г1(1рЪЬр|> (ni-bnufp щшЬш1)£ПиГ t buijuubpj) Ii opjblpnfi шртшцршиЛипЬишЦиЛ, ifuiu\m)t|n-ршщЬи шртшгцшнлриЛшцпртш^Ъ qnp&nibbnipjujli oininfiifiu{ujgnní, np(i Ьш-ifuip ЦшрЦпр Ií2uj1iujl|nipjnt^j nili(i ifbpnrç}) plimpmpjntlip:

ЦшЬЪш|ипипц>]ш1| (фшшЦшЪ 'Unpmpjm.ljp Цш^иЛншГ t hbuiUjtu^nuf.

- ш?}ш$»шрЦ1|ш0 t rçjibunfjilj èpuiqpunJnpiiuAi ршфГш^шф ияГрпод pi[ni¿ qüuijfi'U ôpujijpuji|npU'uj'lj pujiiiruju{u>jmuujl{uij|rti шЬт^шфп[и1ГшЪ (иЪц[1р1)Ьр{) ¿TjqpJiLn (Tièdu/li пщдпц С LpipbljgfinVD lujtpipfipif:

- uiuib\iui|ununipjru\]riuf инии^шрЦЦшй huitfui!{gt|ujü С l{mfp[rtjuimnpuij|i1i> (u1»)[>ptibp)i (mínfuili ui^i}npj>pifj> h)»fui1) i^jiui шлшдфиЬ bli hbinUjui^ uipi¿-jm'üpljbpp.

it¿> ijini^uJj[lb фпфп(иш1|иЛЛ]Ьр[» ||рш sipijujfr ubiipiípujpbjuijJi'b uujhi/шЪш-фшЦпиГЬЬрт^ г^ЪииГ^Ц frpiuqpuiilnpifurti рил^гГш^шфиЛф |u\ir\p|i pufcnuTp,

(О mifpnr^j I31!"*), ^buyjrtj 5pujqpuli|npifuAj рш!^|Гши{ш^и1шЦ (ulirçpji (nlènufp,

ip шЬг^шфп^ий'ш'Ь {иЪгц)^ ti Ърш linrçjityfilpugjmi'bbpj) jniönu/p,

ip йЪрпгф uin.uii|h^nipjnL\]p IpujujUnuf t \ipui\inui, пр liui цдиут\1 ¿t Jrti¿u{bu ^ЬЦшЦшрг»], uijlnqbu t^ фпцш^Ъ фпф|фш>1{шЪЛ1Ьр|> pi}Ji U. 1лЬиш1ф ЪЦшииАшГр:

- ЬрЦшршЛшЛ(Ьт uuihiTLuliuiiJmityuiibbpfi ЬишГшр !{>m.1il|gtiujj(i шт^пшшЦЪЬрр ЦшптдЦпиГ Ь\» "liuifuuiujbu U (цштршииф intupni^ o^muit^npb-i}riif qnpúu>r¡p(>¿ Со1цЬршш)нр rjblpuiJujpifuiïi ifbj»,

- bppnujuijlrti Cifuip2pnumuj|rtû (lAjTjfipljbpf» Ь[иГшЪ i{pui Цшц^ГЦшд fcli Р L ' tu 2(иштш11 ршj(i1j bpuiqpbp,

- йрш^рЬрр офПшцлрОДшд ÍAi - 17рЬии1ф рЭД 1 Цшрр ЦтГр|>Ъшиф U. pfii^ 7 hujg[i qnpftujpurii|> циллришиф uipuiuirjpmlipfi fipiugJWb ицтдЬиЪЬ-р}> ||Ы(Ш1[шр1ГшЪ tjnpbuj^p[i¿ l^uiprjmif:

Я-пиГшрш^Ъ ишрЬЦшЬ шЪшЬишЦшЪ t^b^mp t рОД 1 Цшрф

ЦгаГр^Ъшш}) huitTuip 19Э1р. 400000 ranipiji, Jiulj pjii^ 7 Ьшд() tjnp!nupui1i[> Ьш|Гшр 1ЭЭ5р. 959ЭООО rçpuitT: