Geum.ru
Темы диссертаций по экономике » Математические и инструментальные методы экономики

Экономико-математические модели и методы решения специальных классов нелинейных распределительных задач тема диссертации по экономике, полный текст автореферата



Автореферат



Ученая степень кандидат экономических наук
Автор Тукалевский, Сергей Леонидович
Место защиты Киев
Год 1992
Шифр ВАК РФ 08.00.13

Автореферат диссертации по теме "Экономико-математические модели и методы решения специальных классов нелинейных распределительных задач"

Академия наук Украины Институт кибернетики имени В. М. Глушкова

1 На правах рукописи

ТУКАЛЕВСКИЙ Сергей Леонидович

УДК 519.8

ЭКОНОМИКО-МАТЕМАТИЧЕСКИЕ МОДЕЛИ И МЕТОДЫ РЕШЕНИЯ СПЕЦИАЛЬНЫХ КЛАССОВ НЕЛИНЕЙНЫХ РАСПРЕДЕЛИТЕЛЬНЫХ ЗАДАЧ

08.00.13 Ч экономико-математические методы

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

Киев 1992

Работа выпонена в Институте кибернетики имени В. М. Глу-шкова АН Украины.

Научный руководитель: доктор физико-математических наук,

член-кор. АН Украины, профессор ШОР Н. 3.

Официальные оппоненты: доктор экономических наук

КОСТИНА Н. И.,

доктор технических наук СУХОРУКОЕ Г. А.

Ведущая организация: Киевский государственный университет им. Т. Г. Шевченко.

Защита состоится с . в

часов на заседании специализированного совета К 016.45.05 при Институте кибернетики имени В. М. Глушкова АН Украины по адресу:

252207 Киев 207, проспект Академика Глушкова, 40.

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

Автореферат разослан л Ч 19^^года.

Ученый секретарь специализированного совета //

РЕВЕНКО В. Л.

Общая характеристика работы ."Х--

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

Среди насущных проблем , наряду с другими, особой остротой отличаются, .проблемы, связанные ,с процессами, .рационального природопользования,"оптимального использования производственных и трудовых ресурсов. .

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

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

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

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

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

ионной воды, которое минимизировало бы затраты водопользов_)теля на проведение водоочистных мероприятий и при этом позволило на выходе получить очищенную воду, удовлетворяющую требованиям ГОСТа.

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

Научная н о в и з и а и практическая з начимость. Для дискретно-непрерывной с вогнутой функцией цели распределительной задачи оптимизации процесса водоочистки предложен новый'двухэтагошй подход к поиску решения, который состоит в определении нижней оценки минимума и оптимальных значений двойственных оценок на первом этапе и агоритма получения допустимого решения, близкого к оптимальному, на Етором. Агоритм первого этапа основан на сочетании деко?,шозиции по ограничениям с эффективным методом недифференцируомой оптимизации ( г-агоритмом) для получения решения внешней задачи. Модификация метода последовательного анализа вариантов используется для получения решения внутренней задачи. Эвристический агоритм второго этапа решения многоэкстремальной распределительной задачи основан на получении допустимого решений, близкого по значению целевой функции к полученной ранее оценке снизу.

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

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

С практической точки зрения представляет научный интерес мо-.!;я1.кация известного метода последовательного анализа вариантов, ,тория позволила значительно сократить количество вычислений по гркш&ни с обычной схемс-л динамического программирования.

Расомотроникэ a висоо;тационноЯ работе конкретные распредели-

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

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

Программный продукт, созданный для решения задачи оптимизации процесса водоочистки.широко используется во ВНИИВО/г.Харьков/ при проведении расчетов оптимальной загрузки схем водоочистки производственных, шахтных и городских стоков, а такке послужил основной частью программного комплекса оптимизации процесса водоочистки на Бортнической станции аэрации (г.Киев).

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

Публикации и апробация. Основные

результаты диссертации опубликованы в двух работах, а также

докладывались и обсуждались на итоговых научных конференциях факультете кибернетики Киевского государственного университета (1983,1984 г.г.), на всесоюзных школах молодых ученых и специалистов по проблемам оптимизации (Кацивели 1984г., Алушта 1988г.), на семинарах по эффективным методам решения сложных экстремальны 1 задач (рук.чл.-корр. АН'Украины Шор Н.Э., 1988, 1990, 1992 гг.), на семинарах по решения слокных оптимизационных проблем водопользования (ВНИИВО, Харьков, рук. д.т.н. Сухоруков Г.А., 1989г.), ьн городской научно-технической конференции по проблемам водопользования и водоохраны (Киев,1991г.). на научно-техническом семинара в рамках Первой выставки-ярмарки достижений НТК "ИНСТИТУТ КИБЕРНЕТИКИ им. В.М.ГЛУШКОВА" АН УССР в области программного обеспечения для ПЭВМ (Киев,1990г.).

Структура и объем работы. Диссертации состоит из введения, трех глав, апключпняя, списка литературы из 86 наименований, пяти приложений и содержит 128 страниц мшшно-

гшсного текста.

Содержание работы

Глава 1.з1.1. Эта часть диссертационной работы посвящена рассмотрению особенностей постановок и математических моделей не-ш'гйшх распределительных задеч, построение эффективных методов решения которых является центральным объектом исследования в данной диссертационной работе.

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

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

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

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

Одним из первых рассматривася вопрос об оптимальном использовании имеющегося оборудования для изготовления максимального объема нукней продукции в требуомом ассортименте. Данная задача была впервые изучена в. 1939 году в работах Л.3.Канторовича, гдо указан широкий круг сводящейся к ней вопросов и предложен эффек-чиааый метод решония, основанный на ггризжгах оптимальности плана. ': же рассмотрены случаи, когда им-зсгся ряд ограничивающих усло-например, когда о0тн.1 расход аюктроэнергл, годы или других

производственных факторов не дожен превосходить заданных лимитов.

Необходимо отметить, что поставленная математическая задача возникает не только в связи с использованием оборудования, по п во многих других вопросах: при распределении производственной программы между отдельными предприятиями, при планировании строительных и сельскохозяйственных работ,.при распределении посевной, площади между различными культурами и пр. Подобная модель и у задачи о рациональном раскрое. Этой задаче лосвящены специальные исследования Л.В.Канторовича и В.А.Загалера (1951), отражающие как математическую, гак и чисто технологическую сторону вопроса.

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

За рубэаом, в частности в США, широкое применение распределительные задачи получили преадо всяго в воониом дело.

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

Что касается задачи .оптимального распределения и однородных средств ПВО по N воздушным целям, характеризующимся'координатами опасности (важности) р^ и вероятностями ш^, с которыми одно (любое) из распределяемых средств может поразить J-ю цель, то полученная задача представляет собой дискретный аналог известной задачи Купмана оптимального распределения задавного объема в бесконечной полосе, в которой задано распределение плотности вероятности Ь(х) нахождения искомой цели в различных интервалах [х.х+х! искомой полосы.

Говоря о методах решения рассмотренных задач целераспределе-ния, в работах А.Д.Меркулова(1968), в частности, рассматривается несколько различных агоритмов, основанных,в основном, на анализа значений матрицы вероятностей Я и матрицы важности целей V.

Среди большого числа публикаций на тему о решении сложных

распределительных задач следует отмстить работы большой гпуппы советских мзтомзтиксв и экономистов, посвященных решению так называемых обобщенных распределительных задач большой размерности /примером таких задач может служить задача об оптимальном ruiami-pof '..нии производства и распределения труб (В.С.Ыихалевич и др., 1936)/,ь такие работы В.Р.Хачатурова для задач регионального планирования (1989).

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

задают на J-м

технологическом маршруте производства; j - количество единиц изделия 1-го типоразмера, производимого на J-м технологическом м рыруте производства; tjj-' - технологические коэффициенты, укапывающие ресурсные затраты a-вида при производстве единицы изделии {-го типоразмера по J-му технологическому маршруту, то моте-мтг;гчв'.жая модель (1)-(4) соответствует задаче оптимального планирования производства для выпонения заказа Р= pj), jaJ, при ограничениях по ресурсам величинами I . aeA.

з рассмотренной модели хорошо видыы характерные особенности немго класса распределительных задач. Это прежде всего двухиндекс-1ин переменные, первая из которых указывает на определенный вид потребности, я вторая связана с определенным способом (технологией) ое удовлетворения. Отличительной особенностью является также структура системы ограничений. Наличие балансовых ограничений в а. .рме р'-шенств обусловлено необходимостью удовлетворить потребности поностью. Множество технологических ограничений в чрмч неравенств указывают на ограниченность производственных a лиюстйй ьеличштя

Шп F(x) =2 I ctJztJ

при ограничениях

xfj 5= 0 для V tИl и V JtJ,

J f = р{ для v (el,

I I *\j\j<*Q ЛЫЧКА.

til JCJ

Если коэффициенты минимизируемой линейной формы с затраты на производство единицы изделия С-го типоразмера

Следует ткг.о отметить, что все долевые функции pacnpo,w-тельных задч обладая? свойством српарабеяъгосте. т.е. представимы в виде суммы функций одной переменно;;. Это олош> важное свойство, так как око позволяв? при решении распрзд^л талькой задачи широко использовать подход декомпозиции.

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

В диссертации исследуется двойственный метод ранении, нелинейных распределительных задач.

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

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

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

Для упомянутой ранее обобщенной линейной распределители! >! задачи после применения схемы декомпозиции rio огрншг^зни^п получим индувщуп задач;у:

FM - l l ct ztJ 2 ua ( Ta - l l ) лta

ia ja aa ja

pH ограничениях

PtC *') s J 3tj = Pt л"" 4 ieI Х

Xtj > о для v tel и v JeJ .

, Основой различных схем декомпозиции служат теоремы a множителях Лаграниа. (или о двойственных оценках ) типа теоремы Куна-Таккера. .

Для задачи математического программирования следующего вида:

определить min {f_(x):f (х)И0,1=1,.'".. ,яО ( 5 )

xaeEn 0 1

возьмем и-мерный вектор u={u1.... ,\\т) и составим функции Лагран-

ка: ' I(i,u)=r0(x)+ f u{ i((x) . ( б )

Пусть оптимальное значение задачи ( 5 )?равно f* (если система ограничений несовместна, будем полагать Г*=+о). При иХ) для любого допустимого вектора х имеем L(x,u) < Отсюда ф(и) = Inf L(s,u) < f* при

' Для того чтобы получать наиболее точную оценку в данном классе, нукьо решать задачу отыскания ф*= aug ф(и).

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

Итак,использование функции Лагранка позволяет нанврвмя"исклю-читъ ограничешя Г{(2К0 ( 1=Т~~,т). Если задача минимизации L(s,u) по хеХ решается эффективно, то мы получим Ф(и) и значение суперградиента в этой точке. Эта информация является достаточной для применения обобщенных градиентных методов негладкой оптимизации с целью приближения к ф*. Заметим, что функция <р(и) непрерывно дифференцируема в точке и, если х(и) определяется однозначно. Если же при некоторых и ж(и) определяется неоднозначно, то функция Ф(ц) является недифференцируемой.

Используя обобщенные градиентнйе процессы, мы можем приблизиться к ф* и получить оценку снизу для *. Эти оценки

можно применять в сочетании с другими методами, например со

схемами ветвления или отсечения, для получения точного или

приближенного решения первоначальной задачи. При этом для

приближенного решения мы получаем оценку отклонения от

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

что ф*=тсшь(и)=Г*,то получение и* и соответствующего ему х(и*) яо и0 0

всегда дает решение первоначальной задачи, так как х(и ) может оказаться недопустимым. Если же'пара (х(и*),и*) является сеАловоС точкой функции Лагранна, то отсюда следует, что х(а*)-оптимальное решение задачи { 5 ),.

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

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

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

Схема Й1 (использующая двойственные оценки).

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

2. В случае возможного разрыв;, двойственности из-за невьшуклости исходных распределительных задач применить эвристические проеду-ры, использующие двойственные оценки снизу для I* в сочетании с другими методами, например со схемами ветвления или отсечет;.!, для получения точного или приближенного решения поршночальш.п

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

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

Вторая глава посвящена исследованию двух однотипных дискретных 'распределительных задач: типа AI, где необходимо максшшзиро-uj'b вогнутую функцию цели, и задачи типа А2 со слоаной невыпуклой целевой функцией. Д

Сначала рассматриваются акокоыико-математическая модель и численный метод реаэккя распределительной задачи с вогнутой целевой функцией, которая возникает в связи с задачей максимизации качества обслуживания некоторого потока из S заявок на дискретном (из-за булевого вида переменных) множестве Узадача А1/. Итак, пусть необходимо максимизировать

s г a Si

F (s ) шах ^ Aj 1 - fj [1 " "t;) tJ .-j>0, <Ku(^<1. ( 7 ) J=1 (=1

при системе ограиачений 5

(W s t

для V i*1,]f

= 1 st/ > PJ

= 0 v 1

для v ,s

для V (=1,N и V J\.S

в случае,

когда принято решение назначить 1-й обслуживающий" объект на выпонение .7-оЯ заявки и в противном случае).

Несложно видеть, что если u^J есть вероятность обслуживания ] И заявки (-м обслуживающим объектом, а А, - величина вахшости ; й заявки, то_ функционал ( У) характеризует некоторый выигрыш в зависимости от качества удовлетворения всего пакета заявок.

Ограничение ( 8) имеет следующий смысл: каждый 1-й обслуживающий объект не может выпонять более чем ч заявок. В некотором гыысле это ограничение на производственную моадаость 1-го об-0.'! у к и в й Г.!;! 61' о об ъ <а кта.

Во многих задачах pJ в ограничении ( 9) равно целому числу.

ко мйнызому единицы. Е целом ограничение ( 9 ) уквныы;от на необходимость качественного обслуживания J-й эпявки.

Рассмотрим релаксированнуп задачу 7)-(9)/без условия булоеоо ти/, заменив ограничения (10) двухсторонними ограничениями (Ю'). Для простоты изложения введем поренндексащпо:

/=1,3 Tt=1 ,НВ

причем паро индексов (l.J) элемента матрицы X соответствует индек.1 n=i + (/-1 )*№ элемента матрицы X, и сделаем замены

И f - лfy >tj " "IJ

П t1 -иа 0 Х' .

Тогда на RM, w=N*S, исходная задача будет иметь непрерывный аналог вида

q I Zt*U-t)V ln(1 ~ ^ 1=1

G(X)= min ) Af в , Aj>О, 0<u>tj<1 ,

при ограни чениях

Qi(S) 5 l 2t+(/-Off < ДЛЯ V , Х

ff 1=1-

0 < ^ < 1 ' для У . ПО' >

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

Согласно схеме й2 построения агоритма поиска решения нелинейной распределительной задачи, необходимо на первом атаия использовать метод негладких Функций штрафа для сведения исходной зйдочи к задаче безусловной оптимизации. Построив негладкую Фуик-цию штрафа, имеем

R(x,\)=G()+?.л

J иаг( 0,Q{(z)-qt + ]> гааг( O.pj-Рх) ) +

+ ^ mor[ о Дг 1 ) + 2 mar( о ,-x{ ) ' (11)

t=i {=1 J '

где л - фиксированное достаточно большое значение штрафного коэффициенте. (Если л. выбрано недостаточно большим, что можно выявить в результате проведения счета, следует умножить к на некоторую константу, большую единицы, чтобы добиться эквивалентности задач.)

Задача Rix.*,) Ч> min является задачей негладкой выпуклой оптимизации и успешно решается методом обобщенного градиентного спуска с растяжением пространства в направлении разности двух последовательных субградиентов /г-агоритм/.

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

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

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

Определим следующие величины: t(j - как период времени, в течение которого 1-й обслуживающий объект с некоторой вероятностью R2{j(x,xtj) может обслужить J-ю заявку; величину t, которая определяет rot момент ' постановки указания на обслуживание, при котором вероятность дальнейшего обслуживания будет максимальной; величина - время отклонения выдачи

указания на обслуживание от оптимального значения момента принятия решения о назначении 1-го обслуживающего объекта на обслуживание /--ft поступившей заявки. Конкретный математический вид зависимостей, определяющих значения величин t^J, t*(j, tjj. R?fj(x.Axtj), приведен в з2.2 главы 2. (В реферате он не приводится из-за ограниченности его объема.)

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

I I F'(zl^Хшlt) RгiJ(:slJХгxiJ^~ > гяах> с 12 >

на области, определенной системой ограничений задачи ( 7)-(10).

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

1. Поиск решения упрощенней распределительной задачи на основании данных матрицы вероятностей (=Т7Я и 7=Т7?.

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

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

Как с практической, так и с теоретической точки зрения основное место в диссертационной работе занимает поиск эффективного агоритма решения многоэкстремальной распределительное задач1.; оптимизации работы водоочистного комплекса. Различные аспекте этой проблемы рассматриваются в третьей главе.

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

В параграфе з3.1 рассматривается задача оптимизации загрузки технологических схем очистки при заданных ограничениях ня предель* допустимое качество сброса. Ее экономико-математическая модель включает вогнутую функцию затрат на очистку:

I I ы 41 Ч> т(п ' ( 13 >

где > О и Ос < 1 - коэффициенты аппроксимации затрат, и систему ограничений

Tj( z ) ^ ^ I dklJ Xl^bj Для V J-T7I , ( 14 ) fe=1 (=1

г до dfttj ~ коэффициенты, отражавший относительное качество очистки примеси на й-м комплексе по i-fi технологии;

bj- предельно допустимая величине концентрации J-ii примеси у контрольного створа;

Я ' - .

P( х ) 2 2 xft = 1 .. для V h-T7S . ( 15 ) i=1

sfet И СО;t , ]) для v t*T7ff и V ft=T7S - ( 16 )

дискретно-непрерывное ограничение, где - есть доля

сточных вод от объема которая обрабатывается по 1-й

технологии на fe-м комплексе.

Ограничения балансового типа (15) указывают на обязательность учета всего объема водосброса.

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

Имеется обширная литература по поиску глобальных решений ыно-гоэкстремальных задач (R.Hret, H.Tuy, 19S0), однако для реальных задач значительной размерности общие методы являются неэффективными. Для задач указанного типа в работе (С.А.Цыбульник, 1981) использована идея линеаризации функции цели, однако в работе нет оценки точности предложенного решения.

В соответствии с методикой, рассмотренной в первой глава (схема Й1), применим схему декомпозиции по ограничениял. Полученная в результате такого подхода внутренняя задача имеет следующий вид: минимизировать по ж

Б К л Н S К

L(*.u>-2 lAkl*Hl*laj{l lakij*kcbj] ( 17 >Х k=1 t = 1 /= 1 Vi (=1

при ограничениях

Ы * ) э 1

- 1 Щ V ( 18 )

И СО;С хи , )} для V Г.-=ТТ^ и У й=ТТ? Х ( <9 )

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

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

Координирующая задача безусловной максимизации вогнутой функции ф(а)= те 1(5,и) решается ."-агоритмом. Конечным результатом

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

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

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

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

Более современная трехуровневая технологическая структура про цесса водоочистки рассмотрена в параграфе з.3,2. Функционально это представимо как включение в процесс очистки допонительных технологических элементов, создающих подцепочку к старой технологии, что и позволяет получить схему более высокого уровня очистки. Учет взаимосвязей между смежными схемами, а также возможность возникновения "узких мест" при активном использовании смежны?, схем требует вве-гги изменения как в функции цели гксаомико- матемсчтической модели задачи оптимизации работы водоочистного комплекса, тзк к

в систему йо ограничений. ;

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

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

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

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

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

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

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

Для многоэкстрзмшшюй распре целительной задачи оптимизации

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

При решении внутренней задачи отыскания min L(x, u)

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

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

На основании решения ряда реальных задач подтверждено предположение, что функция затрат водопользователя при решении проблемы выбора схем очистки хорошо аппроксимируется вогнутой функцией вида ахЛ, а^О, 0^Я<1.

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

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

Основные результаты диссертации опубликованы в следующих работах:

1. Тукалевский С. Л. О решении многоэкстремальной нелинейной задачи распределительного типа с использованием двойственных оценок // Методы решения экстремальных задач и смежные вопросы. Ч Киев : Ин-т кибернетики им. В. М. Глушкова АН УССР, 1989. Ч С. 39Ч44.

2. Тукалевский С. Л. Решение многоэкстремальной задачи оптимизации работы комплекса очистки загрязненных вод // Методы решения задач нелинейного и дискретного программирования. Ч Киев : Ин-т кибернетик им. В. М. Глушкова АН УССР. Ч 1991. Ч С. 4Ч9.

Подп. в печ. 27.05.92. Формат 60x84/16. Бум. пнсч. цв. Офс. печ. Усл. печ. л. 1,05. Усл. кр.-отт. 1,05. Уч.-нзд. л. 1,0. Тираж 100 экз. Заказ 750. Бесплатно.

Редакцнонно-издательский отдел с полиграфическим участкам Института кибернетики имени В. М. Глушкова АН Украины 252207 Киев 207, проспект Академика Глушкова, 40

Похожие диссертации