Введение к работе
Актуальность темы. В настоящее время в различных областях человеческой деятельности на первый план выдвигаются вопросы повышения качества-принимаемых решений. В - связи „с этим возрастает роль методов я 'алгоритмов решения оптимизационных задач в математическом обеспечении автомвтизироьашшх систем различного уровня и назначения.
Среди насущных проблем , наряду с другими, особой остротой отличаются, .проблемы, связанные ,с -процессами, .рационального природопользования,'оптимального использования производственных и трудових ресурсов. ..
Математическое-моделирование такого рода проблем часто приводит к необходимости решения распределительных задач смешанного дискретно-непрерывного типа с нелинейными функциями цели. Как определенное, обобщение линейных .производственно-транспортных задач, данный' тип задач- занимает больаое место среди ' прйло'нений математического программирования.
Вычислительные сложности, возникающие при их реиэнии, связаны с большой размерностью и несвязностью области,допустимых,решений. Но даже если пренебречь дискретностью и найти способ. . сократить размерность,, задача зачастую, остается, невыпуклой, что приводит к трудностям, связанным с многоэкстремальнэстью. .- .,-
Невыпуклые дискретно-непрерывнуе распределительные - -задачи имеют довольно широкий круг приложений, но" из-за .невозможности применения точных эффективных методов ( эти задачи, как правило, принадлежат к классу tfp-трудных задач ) обычно ограничиваются построением приближенных практически приемлемых 'алгоритмов.- Но, если уж такая попытка предпринимается, то для того, чтобы она была успешной, необходимо учесть характерные особенности рассматриваемой задачи, а также применять разумные эвристические правила.ограничивавшие перебор вариантов, локальных экстремумов.
Вот почему для научных и практических целей "несомненный интерес представляет поиск эффективных новых подходов к решению невыпуклых дискретно-непрерывных распределительных задач, что и составляет основное содержание данной работы.
Рассматриваемые в диссертационной работе нелинейные распределительные задачи возникли при решении важных практических в.ліро сов, в.частности, "ри исследовании задачи оптимального иснолы;.-. вани'я находящихся в наличии технологических схем очистки загряз
- г -
ионной воды, которое минимизировало бы затраты водопользов_ітеля на проведение водоочистных мероприятий и-при-этом позволило на выходе получить очищенную воду, удовлетворяющую тробовониям ГОСТа.
'(оль работы. Построение экономико-математических моделей, разработка математических методов і: алгоритмов решения нелинейных распределительных задач применительно к проблемам оптимального обслуживания и оптимизации процесса водоочистки.
Научная н о в и з и а и практическая з начимость. Для дискретно-непрерывной с вогнутой функцией цели распределительной задачи оптимизации процесса водоочистки предложен новый'двухэтапный подход к поиску решения, который состоит в определении нижней оценки минимума и оптимальных значений двойственных оценок на первом этапе и алгоритма получения допустимого решения, близкого к оптимальному, на Етором. Алгоритм первого этапа основан на сочетании декомпозиции по ограничениям с эффективным методом недифференцируемои оптимизации ( г-алгоритмом) для получения решения внешней задачи. Модификация метода последовательного анализа вариантов используется для получения решения внутренней задачи. Эвристический алгоритм второго этапа решения многоэкстремальной распределительной задачи основан на получении допустимого решений, близкого по значению целевой функции к полученной ранее оценке снизу.
Лля дискретной распределительной задачи максимизации качества обслуживания предложен новый алгоритм решения, основанный на селении ее к непрерывному аналогу с последующим 'округлением полученного решения до целочисленного. Алгоритм получения решения непрерывной задачи использует г-алгоритм недчфференцируемой оптимизации для минимизации негладкой функции штрафа.
В случае многоэкстремальной распределительной задачи максимизации качества обслуживания с усложнэнной целевой функцией, учитывающей временные характеристики объектов обслуживания предложен новый подход, основанный не. использовании алгоритма решения упомянутой задачи с последующим определением влияния на конечный результат временных характеристик. Предложен эвристический метод получения компромиссного решения.
С практической точки зрения представляет научный интерес мо-,':я1<икация известного метода последовательного анализа вариантов, ; .'Торчи позволила значительно сократить количество вычислений по гранению с обычной схеме--, динамического программирования.
Рассмотрена)..'} и сисссьтіцнонноГі работе конкретные распредели-
тельные задачи максимизации качества обслуживания и оптимизации процесса водоочистки оформлены з виде конечного программного продукта и ньшли широкое применение в народно-хозяйственной деятельности Украины.
Программный продукт, созданный для решения задачи максимизации качества обслуживания, используется Заказчиком при тестировании и в процессе обучения слушателей.
Программный продукт, созданный для решения задачи оптимизации процесса водоочистки,широко используется во ВНИИВО/г.Харьков/ при проведении расчетов оптимальной загрузки схем водоочистки производственных, шахтных и городских стоков, а такке послужил основной частью программного комплекса оптимизации процесса водоочистки на Вортнической станции аэрации (г.Киев). Методика выполнения исследований При выполнении работы использованы теория двойственности математического программирования, методы определения экстремума недиф-ференцируекых функций, теория и методы дискретной оптимизации, широко использован метод декомпозиции по ограничениям. Для статистической оценки свойств предложенных и воплощенных в программы алгоритмов решения дискретно-непрерывных распределительных задач с нелинейными функциями цели широко использованы вычислительные эксперименты.
Публикации и апробация. Основные результаты диссертации опубликованы в двух работах, а также докладывались и обсуждались на итоговых научных конференциях факультета киОернатики Киевского государственного университета 0983,1984 г.г.), на всесоюзных школах молодых ученых и специалистов по проблемам оптимизации (Кацивели 1984г., Алушта 1988г.), на семинарах по эффективным методам решения сложных экстремальны і задач (рук.чл.-корр. АН'Украины Шор Н.Э., 1988, 1990, 1992 гг.), на семинарах по решений слокных оптимизационных проблем водопользования (ВНИИВО, Херьков. рук. д.т.н. Сухоруков Г.А., 1989г.і, ьн городской научно-технической конференции по проблемам водопользования и водоохраны (Киев.1991г.). на научно-техническом семинара в рамках Первой выставки-ярмарки достижений НТК "ИНСТИТУТ КИБЕРНЕТИКИ им. В.М.ГЛУШКОВА" АН УССР в области программного обеспечения для ПЭВМ (Киев,1990г.).
Структура и объем работы. Диссертации состоит из введения, трех глав, апключпная, списка литературы из 86 наименований, пяти приложений и содержит 128 страниц машино-