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

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

Мезенцев Юрий Анатольевич

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

Специальность: 05.13.01 - Системный анализ, управление и обработка информации (промышленность)

АВТОРЕФЕРАТ диссертации на соискаиие ученой степени доктора технических наук

31 ОКТ 2013

005536454

Новосибирск

-2013

005536454

Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Новосибирский государственный технический университет»

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

Авдеенко Татьяна Владимировна

Официальные оппоненты: Фроловский Владимир Дмитриевич, доктор технических наук, профессор, Новосибирский государственный технический университет, профессор кафедры автоматизированных систем управления

Окольнишников Виктор Васильевич, доктор технических наук, Конструкторско-

технологический институт вычислительной техники СО РАН, ведущий научный сотрудник лаборатории информационных систем

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

Ведущая организация: Федеральное государственное бюджетное обра-

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

Защита состоится « 5» ноября 2013 г. в 10.00 часов на заседании совета по защите докторских и кандидатских диссертаций Д 212.173.05 при Новосибирском государственном техническом университете по адресу 630073, г. Новосибирск, пр. К. Маркса, д. 20.

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

Автореферат разослан « » < О 2013 г.

Ученый секретарь диссертационного совета, д.т.н., профессор

Юркевич Валерий Дмитриевич

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблемы и цель работы

История развития современного аппарата дискретной оптимизации (ДО) началась с работ Балаша, Беллмана, Бендерса, Данцига, Гомори, Канторовича, Ху, ряда других авторов (конец 50-х, начало 60-х годов XX века). Позднее появилась теория вычислительной сложности задач дискретной оптимизации, и выделились основные направления развития алгоритмов их решения. Определились, ставшие классическими, сферы приложений: дискретные задачи управления производством (календарное планирование), дискретные задачи оптимального проектирования (размещение, комплектация), дискретные задачи управления логистикой (раскрой и упаковка, транспортировка, выбор поставщиков, ассортимента, определение маршрутов, управление запасами). Список можно существенно расширить. В настоящее время теоретические исследования в большинстве своем направлены на создание эффективных алгоритмов приближенного решения отдельных подклассов задач ДО с хорошими априорными либо апостериорными оценками точности. Под вычислительной эффективностью (или просто эффективностью) алгоритма понимается полиномиальная трудоемкость поиска решения задач ДО, что для практических применений зачастую важнее точности.

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

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

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

з

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

В работе над диссертацией использованы как классические труды в области дискретной оптимизации и смежных разделах, так и работы современных авторов, теоретиков и практиков. В частности, главы, связанные с теорией расписаний, опираются на труды Гимади Э.Х., Гордона B.C., Jonson S.M., Загидуллина P.P., Конвей Р.В., Коффмана Э.Г., Левина В.И., Максвелла B.JL, Миллера JI.B., Мироносецкого Н.Б., Севастьянова C.B., Сотскова Ю.Н., Струсевича В.А., Танаева B.C., Фролова Е.Б., Шафранского Я.М., Шкурбы В.В. При разработке алгоритмов решения нелинейных оценочных задач использованы результаты Boyd S., Евтушенко Ю.Г., Немировского A.C., Нестерова Ю.Е., Vandenberghe L., Vanderbei, R. J. Алгоритмы, основанные на лагранжевой декомпозиции, либо на неполной декомпозиции опираются на работы Бахтина

A.Е., Гилл Ф., Гольштейна Е.Г., Gondzio J., Лэсдона Л.С., Малкова У.Х., Муртаф Б., Мюррей У., Райт М. При создании новых методов и алгоритмов решения общей задачи линейного программирования с булевыми переменными учтены достижения в этой области Алексеева О.Г., Гомори P.E., Емеличева

B.А., Забиняко Г.И., Заславского A.A., Колоколова A.A., Комлик В.И., Körte В., Корбут A.A., Кочетова Ю.А., Лебедева С.С., Леонтьева В. К., Лихтенштейна В.Е., Михалевича B.C., Пападимитриу X., Сергиенко И.В., Стайглиц К., Ху Т., Vygen J. Работы Дикина И.И., Frisch R.A., Gonzio J., Евтушенко Ю.Г., Жадан В.Г., Зоркальцева В.И., Jansen В., Karmarkar N. К., Немировского A.C. Нестерова Ю.Е., Ye Y., Roos С., Terlaky Т., Todd M.J., Vial J.- Р. послужили основой для разработки эффективной модификации алгоритма следования центральному пути, применяемого для решения последовательности оценочных подзадач в алгоритмах дискретной оптимизации.

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

4

ем попадают в интервал 0-5%, что может служить предварительной количественной оценкой степени достижения поставленной цели.

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

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

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

Задачи исследований

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

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

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

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

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

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

Область исследования

Содержание диссертации соответствует положениям п.п. 1,2,3,4,5 областей исследований паспорта специальности 05.13.01.

Объект и предмет исследования

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

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

Методы исследования

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

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

Научная новизна

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

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

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

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

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

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

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

Практическая ценность и значимость

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

Результаты диссертационной работы были использованы производственными компаниями ООО «СофтМастер» и ООО ТК «Маркет Регион», а также ИЭОПП СО РАН при выполнении договора № 2010/08/0134 от 01.08.2010 на тему «Разработка перспективной программы оптимизации издержек ООО «Газпром добыча Надым» на базе инновационных технологий» по заказу ООО «Газпром добыча Надым» (г. Надым), что подтверждается соответствующими актами внедрения разработок. Часть практических результатов получена при поддержке грантов: Минобрнауки, «ТП-8.536.2011, Разработка интеллектуальных технологий, средств компьютерного моделирования и эффективных методов оптимизации, как функционального наполнения информационно-аналитических систем поддержки принятия решений», РГНФ «09-02-00093а, Разработка и исследование моделей планирования производства изделий, основанных на нанотехнологиях».

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

Достоверность

Обоснованность и достоверность научных положений и выводов, содержащихся в диссертационной работе, подтверждается вычислительными экспериментами. Получены апостериорные оценки точности и быстродействия всех разработанных в рамках диссертационной работы алгоритмов оптимизации. Сгенерированы и просчитаны тестовые задачи в широком диапазоне размерностей. Результаты тестирования программных модулей, реализующих разработанные алгоритмы, проверены с использованием IBM ILOG CPLEX Studio (v:12.1-12.5).

Апробация работы

Основные положения и результаты диссертационной работы докладывались и обсуждались на следующих научно-технических конференциях и симпозиумах: Международной научной конференции «Моделирование 2010» (Киев, Украина, 2010); на международном индо-российском совместном семинаре по

компьютерному интеллекту и современным эвристикам в автоматизации и робототехнике «DST-RFBR Sponsored Indo-Russian Joint Workshop on Computational Intelligence and Modern Heuristics in Automation and Robotics» (Сурат, Индия, 2010); на международном российско-индийском совместном семинаре по компьютерному интеллекту и современным эвристикам в автоматизации и робототехнике «RFBR-DST Sponsored Russian-Indian Joint Workshop on Computational Intelligence and Modern Heuristics in Automation and Robotics» (Новосибирск, Россия, 2011); XV международной открытой конференции «Современные проблемы информатизации в экономике и обеспечении безопасности». (Воронеж, Россия, 2010); Международной научно-практической конференции «Агропромышленный комплекс, как фактор развития национальной экономики республики Казахстан» (Семипалатинск, Казахстан, 2004); VI международной конференции «Актуальные проблемы электронного приборостроения» (Новосибирск, Россия, 2002); Международной научно-технической конференции «Информационные системы и технологии» (Новосибирск, Россия, 2003); X Международной научно-практической конференции «Методы и алгоритмы прикладной математики в технике, медицине и экономике» (Новочеркасск, Россия, 2010).

Публикации

По результатам выполненных в диссертации исследований опубликовано 35 печатных работ, в том числе 2 монографии, 18 статей в журналах из перечня ведущих рецензируемых научных журналов и изданий, в которых должны быть опубликованы основные научные результаты диссертаций на соискание учёной степени доктора наук, 4 статьи в научных периодических журналах и тематических сборниках, 7 докладов в материалах и трудах международных и всероссийских конференций, 4 свидетельства о государственной регистрации программного обеспечения.

Научные положения, выносимые на защиту

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

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

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

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

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

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

Личный вклад автора в проведённых исследованиях

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

Структура и объём диссертации

Диссертация состоит из введения, шести глав и заключения, изложенных на 307 страницах основного текста, включая 37 рисунков, 59 таблиц, список использованных источников отечественных и зарубежных авторов из 120 наименований, дополненного приложениями.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

Вторая часть «Быстрые методы решения общей задачи целочисленного программирования» посвящена разработке алгоритмов решения общей задачи дискретной оптимизации и состоит из двух глав (главы 5 и 6). Ее тесная взаи-

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

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

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

Для каждого прибора ; ПОС определено время обслуживания каждой заявки у (0</, у <оо). Прерываний обслуживания одних заявок в пользу других не допускается, приоритеты заявок и приборов в общем случае не определены, дисциплина обслуживания очередей - произвольная. Показано, что за полиномиальное время ПОС вида «сборка» и «разузлование» приводятся к виду «линейное обслуживание». Поэтому основные исследования в рамках главы сосредоточились на ПОС данной разновидности.

Тогда в общем случае модель, описывающая процесс функционирования ПОС, представима в виде:

¿^=1,7=17, (1)

1=1

1, если заявка / назначается на прибор г, „ —— . —— О в противном случае,

= - Ж/ + >/,/К/' = ] = и, (2)

1=1

= ти + уи > 0, / = й, У = и, (3)

J J _

Здесь задержка поступления у-й заявки в ПОС (Т° = |г° || - расписание на входе системы), ] - время обслуживания заявки у прибором г ( Т = у^- компенсирующие переменные, которые вводятся для того, чтобы избежать

появления отрицательных задержек (г,- ■)• f,- . имеет смысл фактической задержки начала выполнения j-й заявки г'-м прибором после завершения обслуживания им предшествующей заявки. Пусть также Т1 = ||г]| - расписание на

выходе системы. Система ограничений может дополняться ресурсными ограничениями вида:

1 J _

Z Z аи + *и )хи -br > r = \,R, (5)

1=1 j=l

где a- j норматив расхода ресурса r-го вида при обслуживании г'-м прибором j-й

заявки, br - лимит г-го ресурса в рассматриваемом временном интервале. Если при этом определен критерий качества (эффективности) расписания, например Z = Я —» min, (6)

то (1)-(6) определяют задачу синтеза оптимальных по быстродействию расписаний параллельной системы с задержками на входе. (4) и (6) реализуют минимаксный критерий, имеющий смысл критерия максимального быстродействия. Кроме (6) определены и некоторые альтернативные критерии.

Условия (2)-(6) содержат рекурсивные функции фактических задержек ri ■. Для решения поставленных задач в общем случае требуется раскрытие рекурсий и линеаризации получаемых при этом условий. В четвертом разделе главы эта операция выполнена. В результате получена модель ПОС с задержками поступления заявок следующего вида:

/ __J _ _

<=1 j=1

1, если заявка j закрепляется за прибором г;

''' 1 0 в противном случае;

7-1 _

_ 11, при истинности выражения/. х,.^!,...,^.!) = х, ]Х(к хи

иШ | ' 1=к+\

О в противном случае;

Уи> 0, / =й, ] = = = (7)

7-1 _ _ _

-К + 2<хи+хкк- £ хи-Киш<1,К = ]-к + и = 1,1,] = и,к = и, (8)

/=/1+1 7-1

= У и + т° - + Ь,к) "и,к > 0, или

к=1

7-1 _ _

-Уи + + 'аКм * т% 1 =1 '7' 1 = Ы, (9)

к=1

: J J у-1 _

1>7° +'и)*и + ТУ,./ - Е2>° + кк) 41,к < Я,/ = 1,7. (10)

7=1 7=1 7=1 к=\

При использовании критерия (6): Л —»min получаем задачу частично-целочисленного программирования с булевыми переменными. Представленная задача NP-трудна и относительно исходной (1)-(6) имеет размерность, большую

в J/2 раз и по числу булевых переменных (за счет uij к ), и по числу ограничений (8), (9). Ее вычислительная сложность для сколько-нибудь реальных объектов такова, что попытки прямого (точного) решения существующими средствами вычислений не имеют перспектив.

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

¿х,.,.=1, j=U, v^IX; /=й,

1=1 }= 1

Г1, если заявка/ назначается на прибор /, — ——

= . i = \,I,j = \,J (11)

[О в противном случае,

j _ J _

YjT°jxij -ß> i = ^Jijxij *' = 1>/, Я —»min, ß —>min.

j=l ' j=l

Из контекста понятно, что данный подход к распределению заявок между приборами предполагает компромиссное решение по «чистому» быстродействию ОС без учета задержек (Л) и по равномерности распределения задержек между приборами (ß).

Упрощенная задача (11) NP - трудна в сильном смысле, поскольку кроме ограничений задачи о назначениях, содержит также 2 I ранцевых ограничений. Разработан алгоритм ее решения, включающий построение Парето-оптимального множества расписаний (параметрического решения, при котором один из критериев вводится в состав ограничений с параметром в правой части). Далее получаемое множество Парето - оптимальных решений упрощенной задачи (11) оценивается в терминах задачи (6)-(10) непосредственной подстановкой в условия последней. Таким образом, из Парето - оптимального множества решений упрощенной задачи выбирается наилучшее решение исходной задачи (1)-(6). Тестирование алгоритма определило среднее 5.5% отклонение от оптимума значений целевой функции, что в большинстве случаев вполне приемлемо.

Обеспечение большей точности решения потребовало модификаций алгоритма (разделы 7-9). Для этого применены разбиения расписания на входе Т° на ряд подмножеств, а также разбиения соответствующих задач на ряд подзадач с решением получаемой последовательности. Декомпозиция осуществлена на основе метода динамического программирования. Разработанный при этом алгоритм синтеза расписаний на основе точной (6)-(10) и упрощенной (11) постановок является асимптотически точным, позволяет снизить размерности реша-

12

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

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

Для описания процессов бурения и строительства скважин НГКМ потребовалось дополнение моделей (1)-(5) и (7)-(10) условиями: 1 _ ./ 1

£х,.у< 1, у = 1Х-]>Х,>Я, (12)

¿=1 ]=\ ¿=1

где с!]- дебит у - й скважины (куста скважин), О - совокупный спрос на продукты НГКМ, и расширение понятия задержек поступления заявок в систе-„ „ (г60 если г60 > тс0

тО 0 0 ' >ксл" Ч 'у '

му. 1 = II г; у |1, г, - = < п — исходная задержка начала бурения

' 11 ' [ту,если ту >т,

куста скважин у на БУ г. ПОС, которым соответствуют такие условия, названы системами с задержками начала обслуживания заявок.

Кроме этого расширен состав критериев эффективности показателями

I J

затрат на бурение ->тт и прибыли

¡=\м

J I I J

г^с/у^х, ;у —> тах, где с, у- затраты, связанные с бурением

]=\ 1=1 ' /=1 у=1

скважин 7-го куста /-й буровой, определяемые как эксплуатационные расходы и амортизационные отчисления за время бурения, и г - оптовая цена реализации 1м3 газа.

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

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

Вторая глава посвящена исследованию и разработке моделей и алгоритмов синтеза расписаний многостадийных систем. Рассматриваемые объекты

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

Рис. 1. Параллельно-последовательная обслуживающая система

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

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

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

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

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

Задача синтеза расписаний для подобных систем является ЫР-трудной, может интерпретироваться, например, как задача календарного планирования деятельности производственного участка (цеха) и известна в литературе, как

14

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

Рис. 2. Последовательная многостадийная обслуживающая система

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

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

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

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

-

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

Далее в разделах (6-10) главы на основе алгоритмов оптимизации расписаний одностадийных параллельных систем с задержками на входе (результаты первой главы) и алгоритма неполной декомпозиции задач оптимизации расписаний последовательных систем разработан общий декомпозиционный алгоритм синтеза оптимальных расписаний параллельно-последовательных систем.

Формальная запись условий общей задачи оптимизации расписаний ППОС приведена ниже.

1, если заявка у закрепляется за прибором г

подсистемы р при обращении к на шаге д, (13)

0 в противном случае;

ограничения на назначения заявок на приборы:

шР

Ш'Р'к * 2>,Т* - Я'"*,V /е/„, д = 1,2,...,* = 1,2,...,= й,

переменные, компенсирующие возможные отрицательные значения задержек т''''''к:

у?/'*>0, У/е/р, «7 = 1,2,...,к = 1,2,-,Р = й, 7=17.

Фактические задержки (расписания) поступления заявок в ОС:

^ если — —

[0 в противном случае

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

- зависимости текущих задержек начала обслуживания заявок от предшествующих задержек 7-1

+ ','/)*//•* . V/ 6 = 1,2,... Д = 1,2 ,...,/> = 1,1, = и,

/=1

ту* = У9==1,2,...,4 = 1,2,...,р = м, ] = и,

- компенсированные задержки

r«f'k=t?fk+y?fk>0,VieIp, q = \,2,...,k = 1,2,... ,p = \,n, j = \,J, (14)

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

?Я}Р* -Ttf* + ttfx?j>*ü О, V(i,j,p,h,i'J,p',k')eI(A^0),

iff* -ftf* + (tPf + itfWf > О ,V(i,j,p,k;i'J,p',k') е I(AJU0), (15)

- условия неодновременности выполнения некоторых пар операций

B<tf ~ ttfxlf > fff* - f?f'k > ttfxff* -B(l-wtff),

V(i, j,p,k;i, f,p,k')e I(AJZy),

k<k, [l, если операция i,j,p,k предшествует i,j',p,k' ''J'J [0, если операция i,j',p,k' предшествует i,j,p,k' \/(i,j,p,t,i,j',p,k')<=I(A0v),

- минимаксный критерий быстродействия ППОС

j j

Yslixh + EVie/P' Л -» min. (16)

j=1 j=1

Условия общей задачи оптимизации расписаний (ОЗОР) ППОС (13)-(16) содержат рекурсивные функции (формально идентичные (2)), при раскрытии которых представленная задача редуцируется в задачу частично целочисленного линейного программирования с реализациями сверхбольших (для реальных объектов) размерностей. Упрощенным примером может служить задача (6)-(10) на практике неразрешимая точными методами. Поэтому подобная редукция не имеет практических перспектив, а общий алгоритм решения задачи (13)-(16) может быть реализован без этой процедуры. Для решения ОЗОР ППОС разработаны две модификации декомпозиционного алгоритма: 1) прямой, являющийся обобщением декомпозиционного алгоритма оптимизации расписаний ПМОС; 2) циклический алгоритм оптимизации расписаний многостадийных ППОС. Последний основан на поэтапном решении составляющих подзадач: оптимизации расписаний одностадийных параллельных систем с задержками на входе и подзадач оптимизации расписаний ПМОС.

Прямой алгоритм опирается на представление задачи синтеза расписаний ППОС в виде обобщенной смешанной сети специального вида (рис. 3) и основывается на алгоритмах оптимизации расписаний последовательных систем.

Рис. 3. Графическое представление задачи синтеза расписаний ППОС

17

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

ппос.

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

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

Аналитическое представление задачи приведено ниже.

Пусть Tj время начала бурения скважины (куста скважин) под номером j

{1, если буровая / назначается на куст скважин j ,

— — (17)

О в противном случае, i = 1,1, j = \,J

i __J _ _

2>,.,=1, j = l,J, =

¡=i j=l

i _

Tj.-Tj-^tjjXjj^O, j',j = l,J, если строительство куста j предшествует j' ;=i /

т ,k tx. ,t < Л, V/* e Jk (множество замыкающих кустов),

/=1

Г1, если операция (строительство куста) j предшествует/ —

wj,f = I г. ,j,j = \,J

' [0 в противном случае,

* Tf~rJ * Ъихи-B(JL-Wjj.)J\j = W, (18) i=i i=i

(18) означают неодновременность начала выполнения операций на кустах j',j и являются частным случаем общих, условий характерных для ППОС:

Bwjj. - tu. xuf > ty - tj > tuxu - B( 1 - Wjj.) ,i = TJ,j\j=U. (19)

Условия (19) означают, что кусты скважин j' и j не могут быть пробурены одновременно одной буровой i.

£tijXiJ<A, i=TJ, Л —> min. (20)

j=i

Задачу (17)-(20) можно рассматривать как обобщение JS и частный случай ОЗОР ППОС (13)-(16). Фактически (17)-(20) является формализацией ЗТР, известной как flexible job-shop (FJS). В отличие от ОЗОР ППОС, она не содержит

18

рекурсивных функций и для ее решения могут быть применены все модификации прямого алгоритма решения. Необходимо отметить также существование взаимно однозначного соответствия между графическим представлением задачи синтеза расписаний ППОС (рис. 3) и условиями (17)-(20).

В качестве иллюстрации применения представленных в главе моделей и алгоритмов к реальному объекту, приведен пример формализации и решения задачи оптимизации расписания строительства кустов скважин нефтегазокон-денсатного месторождения. Использованный при этом подход предусматривает явное задание технологических последовательностей бурения скважин в форме (17)-(20). Показана взаимодополняемость поэтапного подхода (задача (7)-(10), (12)), более применимого при оперативном планировании, и подхода на основе обобщенных смешанных сетей (в аналитическом представлении (17)-(20)), целесообразного при среднесрочном планировании. Результаты решения (17)-(20) служат исходными условиями (расписанием на входе) для поэтапного подхода.

В разделах 9 и 10 представлен циклический декомпозиционный алгоритм решения общей задачи (13)-(16). Регулируя параметры декомпозиционного алгоритма, определяющие размерности решаемых подзадач частично целочисленного линейного программирования с булевыми переменными на каждом шаге, можно добиться фактического полиномиального быстродействия. Единственным ограничением, выявленным эмпирическим путем, является ограничение на число булевых переменных в подзадачах, порождаемых алгоритмом, которое не должно превышать тысячи.

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

В последнем разделе главы дано краткое описание программной реализации разработанных алгоритмов оптимизации расписаний ППОС.

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

Решением первой задачи (разделы 2, 3) является: оптимальный выбор параметров входных и выходных материальных потоков.

Формальная запись задачи приведена ниже.

Определить х1! к(1), y¡ j(t), Wj k{t) при условиях:

/

(21)

;=1

а] (о - (ои- к (о > о, у = 1, у, / = 1, т

0<и>м(/)<1, 1^(0-целые, уи]{1)> 0, 1 = Ц] = \= к = 1К,

£[<///) - dj{t)%gjtk{t)wjtk{t)] + AQ(t) - Q(t) = 0,

J=1 k=1

A№)>0,Q(t)>0 t = \J , (22)

&j,i(0> если clj(t) < hjj(t),

gj,2(0. если hj X(0 <dj(t) < hj 2(t), _— —

J — > * — A»-»

s,(0 =

8j,k(1)i если dj(t) > hj K (t),

хш(/)<jw(/), ¿ = l,/,/ = l,L,? = l,7\

i-1 _ _ _ _

¿ = U, l = l,L,k = l,K, t = l,T.

k'=1

y=l /=1 Jfc=l

7=1 /=1 Jfc=l

AQ(t) = Д6(/ -1) + - 1)*,,,* (' -1) - ЛГ(/ -1) -

i=i /=i ¿=1

t=Vf, (23)

j=1 *=1

г r

^a(()Q(0 -> max, при условиях

О < a(t) < = 1,

(=2 1=2

AQ(T +1) max. (24)

Здесь i - индекс продукта, j - поставщика, / - типа потребителя, к - интервала шкалы объемов скидок, t - номер месяца.

)>j j(t) и xuk(t) - входной и выходной потоки, Wjk(t)- булева переменная

выбора интервала шкалы,

С,- j(t) и Puk(t) - заданные коэффициенты (цены, оценки);

hjk(t) - значение правой границы интервала объема потока Д7(0 (рис. 4),

gjk(t) - соответствующая интервалу к шкалы объемов скидка (в долях

единицы),

Sj 1 k(t) - значение правой границы интервала к шкалы функции gj(t). Q(t), AQ(t) и N(t) - заданные значения, О, (?) - остатки запасов.

и

\

1 I

I I

I I

I I

\ V

\ \

(О Ьг(0 Рис 5. Условия поставок

Ы')

Сумма заказа

Показано, что сформулированная задача не имеет точного прямого алгоритма решения, поскольку содержит ограничения (22) и (23), нелинейно зависящие от непрерывных Ду(0 и булевых ю - к(1) переменных. Вместе с тем,

разработан эффективный итерационный алгоритм, позволяющий получать близкие к оптимальным ее решения (разделы 6, 7). Суть алгоритма заключается в итерационном решении релаксированной по отношению (21)-(24) линейной задачи. Релаксация осуществляется по переменным заменой условий

(22) и (23) на ограничения:

у=1 /=1

= де(0+£¿1>,а(0 - N0) - ¿¿[1 - (Г+1)К,У(Г + 1)Уи(г+1) (25)

¡=1 ¡=1 к=1 /=1 у=1

Очевидно, если являются оптимальным выбором для задачи (21)-

(24), то оптимальное решение ее релаксации является также оптимальным решением самой задачи (21)-(24). Быстрая сходимость обеспечивается благодаря тому, что функции скидок gj(t) являются неубывающими кусочно-линейными

зависимостями (рис. 4). Тестирование алгоритма на задачах реальных размерностей подтвердило эффективность предложенного подхода.

В разделе 8 представлена квадратичная модификация задачи, более точно учитывающая условия формирования выходных потоков. Для этого ограничения, определяющие условия формирования выходных потоков, дополнены явно задаваемыми зависимостями ри(хп(г)) следующего вида (рис. 5).

Тогда зависимость Рц{хц{0) определяется в соответствии с:

(А\м(0. если хи(0<*ш(0, — — —

МУ'))= 0м ¡ = 1,1,/ = 1,1, ( = 1,г,

[в,° (0 + </(О*,//), если х,, (0 > (/), где аи(0 = —:--——— _ -; аи (0 =---, и

(0-

1,1,2

(0

Рис. 5. Зависимости цены от объема продаж продукта

уравнения (25) принимают вид: I ь

-де(/+1)+дш-

-ЁА* +1 + !)>-/,>(' +1) = ш, / =

/ /.

£ Ё К/ О*,-,/ (0 + а,1,/ (0(*/,/(0)2]. если .г,.; (?) > , (/),

1=1 /=1 / 1

1=1 /=1

ЕЕл,/,1('К/(0, если

(26)

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

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

Другая формальная постановка, представленная в третьей главе (разделы 4,5), определена как динамическая задача управления входным потоком промышленного предприятия. Формальная запись представлена ниже.

Определить хи](/), уи1 (/), I = 1,Т, г е /, у е У, I еЬ, при условиях:

X арj (i-D+X a j £ xu (t)<E(t),t = l,T,

jeJ jeJ iel

¿Хм < ZIX^w, /=й\ ie/,

jej j&J Ï&L

xu(t) > 0, t = 1J\ iel, je J,

yu{t) >0,целые, t = \J, iel JeL, (27)

Z = IŒIW) ZAy(0Oy(0.+^(0} ->min, (28)

1=1 Ш jsj Ш IgL j&J

0 = (29)

ie/ jsj

где / - индекс поставщика, j- материала, 1 - вида транспорта, t - номер временного интервала, xt j (t) - размер потока, yt l (t) - варианты доставки; с,- j, Çjj -цена и оценка качества; s,-, - затраты на единицу вида / ;

el j— вместимость единицы вида / для элемента потока j ;

Pj (/), Оу (/), и hj(t) - потребность, остаток, страховой резерв и

штраф за хранение запаса; Oj - площадь на единицу элемента j ;

E{t), d(t), N(t) - площадь складских помещений, средняя цена единицы входного потока, издержки;

Ограничения (27) с критерием эффективности (28), либо (29) составляют NP - трудную задачу частично-целочисленного линейного программирования.

Ее разбиение на подзадачи меньших размерностей и решение генерируемой последовательности подзадач осуществляется с помощью специального алгоритма (раздел 9). Алгоритм решения основан на схеме неполной декомпозиции. Декомпозиция осуществляется по целочисленным переменным уп( t), t = l,T, iel ; leL, по индексу интервала времени t (время дискретно).

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

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

В четвертой главе осуществлена формальная постановка общей задачи оптимальной комплектации (ЗОК) технической системы, относящейся к классу задач оптимального проектирования. В общем случае ЗОК представима в виде:

Яоб = X X ->тах,

(30)

уеГ/ уе/

(31)

уеК/ уеУ'

0(*у.у,и;) = 0, и(>Хл„ = {0У1}, УуеК/, ;е/,/е/,

(32)

где ^ значимость у—го показателя качества комплекта (подсистемы), значение у—го показателя качества при V - м варианте реализации, и = ЩЦ--набор дискретных количественных характеристик, от которых зависит качество комплектации, х^ у переменные выбора варианта комплектации,

с-_„(и) затраты на достижение у-го показателя качества при V - м варианте

реализации, Р - общие затраты на комплектующие.

(32) задают все возможные логические ограничения, связывающие переменные ЗОК. В простейшем случае переменные выбора X] у

Во втором и третьем разделах главы определены основные особенности базовой ЗОК (30)-(32). Во-первых, это единственность ресурсного ограничения

(31). Если положить Сду (и) константами, то (31) - ранцевое ограничение. Во-

вторых, посредством эквивалентных преобразований множество логических ограничений (32) можно привести к линейному относительно переменных виду (материалы раздела 3) и показать, что в большинстве случаев коэффициенты при переменных такой линеаризованной подсистемы образуют фрагмент абсолютно унимодулярной базисной матрицы системы (31)-(32), в связи с чем ограничения (32) не оказывают влияния на вычислительную сложность ЗОК (30)-

(32). И, в-третьих, ограничения ЗОК системы образуют блочную матрицу, что позволяет применить известные методы лагранжевой декомпозиции при решении. Также в третьем разделе приведены правила, используемые для линеаризации ЗОК относительно булевых переменных ху- у.

В четвертом разделе осуществлена декомпозиция линеаризованной задачи оптимальной комплектации (ЛЗОК) и изложены основные постулаты, позволившие заменить булевы переменные х. у непрерывными. В частности использованы положения теоремы Эверетта о целочисленности решений задач рассматриваемого класса в седловых точках функции Лагранжа при замене дискретных переменных непрерывными. Там же предложен алгоритм параметрического решенця выделенных подзадач ЛЗОК для всех седловых точек функции Лагранжа. В качестве параметра рассматривается значение Р^ (правая

х

1, если выбирается V - вариант комплектации у -й подсистемы , 0, в противном случае,

удовлетворяют условию

часть (31) для подсистемы у). Параметру на каждом интервале устойчивости соответствует множитель Лагранжа (двойственная оценка, или предельная полезность) ЯДР,). Результаты параметрического анализа подзадач выбора

подсистем ЛЗОК представимы, например, в виде таблиц:

Таблица 1.

pJ pmrn , p ^ p2 j j ~ J ps <p.< ps+1 ij j-ij p > pmax j j

4pj) дтах я; 0

XJ,V xJAPj)

QjiPj) Q)(Pj) Qj(Pj) QJ(Pj)

В табл. 1 xsjv, Л*, Qj(Pj) значения переменной выбора, двойственной оценки затрат и критерия качества для подсистемы j на интервале устойчивости s, s = \,m; Áj(Pj)- невозрастающая функция предельной полезности (ФПП), т.е. Я™ах >...>Áj >...>0, и Áj - константы; xsjv(P¡)- параметрические

решения на интервале s.

Разработанный алгоритм, основой которого является двойственный симплекс-метод, позволяет построить локальные ФПП всех подсистем комплектуемой системы. Тем самым реализуется декомпозиционная схема решения ЛЗОК, завершает которую алгоритм построения общей ФПП затрат на комплектацию системы и оптимизации по критерию качества, т.е. решения линеаризованной задачи (30)-(32). л?)

1!.7 0.6 0 S

м

о,? о.: од о

п:о i ¡70 i::o i2?u 1320 13"о í-eo 14?и r

Рис. 6. Пример ФПП ЛЗОК

На рис. 6 изображен график ФПП приведенного в разделе 4 примера задачи комплектации системы пятью подсистемами (от 15 до 22 вариантов комплектации каждой). Маркеры на рисунке соответствуют седловым точкам функции Лагранжа. В этих точках алгоритм определяет точные оптимальные решения ЗОК. Цифры над интервалами устойчивости ФПП отображают номера комплектуемых подсистем.

Алгоритм является асимптотически точным по размерности задач оптимальной комплектации. Этот факт иллюстрируется рис. 7, отображающим соотношение качество-цена О(Р) для одной из тестовых ЛЗОК, содержащей 104 булевых переменных. Маркеры на рисунке также соответствуют седловым точкам функции Лагранжа, наглядно демонстрируя точность разработанного алгоритма оптимизации для ЛЗОК больших размерностей.

Программная реализация созданного алгоритма оптимизации ЛЗОК позволила получить также апостериорные оценки точности и быстродействия для задач оптимальной комплектации в широком диапазоне размерностей (разделы 57). Табл. 2 содержит результаты решения 30 тестовых примеров, сгенерированных программой-генератором исходных данных ЛЗОК.

Для проведения вычислительных экспериментов были сгенерированы три группы тестовых задач разной размерности (по 10 тестов в группе с числом булевых переменных 1000, 10000 и 100000 соответственно).

Таблица 2.

Результаты тестирования алгоритма__

Группа Число тестов Число подсистем шах число переменных ПС Всего булевых переменных С шах ^шах (%) Время решения (сек.)

1 10 10 123 1000 0.096337 0.0252 0.000001

2 10 10 1230 10000 0.236492 0.0386 0.000191

3 10 10 12300 100000 0.024639 0.0040 0.187240

Графа «шах число переменных ПС» отображает максимальное число переменных выбора альтернативных вариантов комплектации одной из подсистем. Общее же число таких вариантов определяется количеством булевых переменных ЛЗОК (следующая графа). В колонках <5тах и Дтах отображены максимальные возможные абсолютные и относительные отклонения от оптимума по всем десяти тестам каждой группы, в колонке «время решения» указано максимальное время вычислений также по всем тестам группы.

Из таблицы видно, что возможные отклонения от теоретических оптимумов крайне незначительны и уже при 1000 переменных пренебрежимо малы. С ростом числа булевых переменных растет и точность алгоритма, что подтверждает вывод об асимптотической точности последнего. Данный вывод хорошо иллюстрируется графиком <2(Р) для одного из тестов второй группы (рис. 7).

650

2100 2300 2500 2700 2900 3100 3300 3500 3700 $900 Рис. 7. Соотношение качество-цена для ЛЗОК (104 булевых переменных)

Маркеры на рисунке соответствуют сёдловым точка функции Лагранжа. С ростом размерности число седловых точек пропорционально возрастает.

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

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

Объект исследования - задача вида

являющаяся задачей линейного программирования с булевыми переменными (ЗЛПБП). Условия х е определяют принадлежность решения одной из вершин единичного гиперкуба размерности п, с,х, 0,1 - векторы той же размерности (0 - нулевой вектор, 1 - вектор, состоящий из единиц).

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

Рассматриваются дополняющие задачу (33)-(34) неравенства следующего

где Д, = [Д0] ид:0 - оптимальное решение задачи (33)-(34). Если вводимое ограничение является неравенством - следствием базисной системы неравенств (34), то оно именуется правильным сильным отсечением. Такие отсечения являются частным случаем отсечений Гомори и не всегда могут быть построены в силу условия а. е {—1, 0, 1}.

Введены ключевые понятия правильного слабого отсечения и соответствующего порождающего неравенства. Первое определяется как любое неравенство (36), отсекающее от ОДР (34) область, не содержащую целых точек. В отличие от сильных, всегда существует множество слабых отсечений (36). Порождающими могут являться любые активные ограничения (34), т.е. неравенства образующие базисную систему при оптимальном решении текущей задачи, а также неравенства — следствия базисной системы неравенств. На этой же основе определены бинарные отсечения (БО), являющиеся частным случаем слабых отсечений вида (36). Введены они для упрощения изложения и обоснования алгоритмов оптимизации посредством нижеследующих преобразований. Слабому БО не соответствует никакое отсечение Гомори. Теоретически, любое

(33)

(34)

(35)

вида: (ат,х)< Д,, <5,-е{-1, 0, 1} ,j = \,п, Д0 = (йг,х°),

(36)

такое отсечение можно построить только с помощью некоторой конечной последовательности отсечений Гомори.

Нормализуем задачу (33)-(35) таким образом, чтобы коэффициенты целевой функции (33) были неотрицательны с . > 0, у = 1, и. Тогда в выражении (36)

можно положить ауе{ О, 1},у' = 1 ,п. Это преобразует (36) в неравенства, известные, как отсечения покрытия (обычно применяемые при решении задачи о покрытии).

Редуцированная подобным образом задача (33)-(35):

у(х) = (ст,х) + С шах, (37)

Ах<Ь,0<х<Т, (38)

*е/2", (39)

— (х/, если с, > О Г с.-, если с, > О где с > 0,у = \,п, х • = •! с = 1

[1-ху, если су. <0 ' I-су, если су < 0

_ Г а,-у, если с. > 0

у|уСу<0 _/|Усу<о [-а, у, если су < 0

В этом случае коэффициенты левой части любого г'-го отсечения (36) обладают свойством: ау. е { 0, 1 },у' = 1,«. Обозначив через х° решение задачи (37)-(39), определим БО по отношению к системе (38):

{ат,х)<р0, йу.е{0, 1},у=ТЯ Д,=[Д,], Д, = (аГ,*0), (40)

а также дополняющую систему БО к системе ограничений (38)

А °х<р, (41)

где А° = а1. ,а' е { 0, 1 },у = 1,и - матрица коэффициентов дополняющей

II 3 \\тихп у

системы, и вектор правых частей отсечений р определяется в соответствии с (40).

Если А° обладает свойством абсолютной унимодулярности и все отсечения (41) правильные (А°- часть базисной матрицы системы (38),(41)), то при т° > п, А° включает базисную матрицу и оптимальное решение задачи ЛП (37),(38),(41) является оптимальным решением ЗЛПБП (37)-(39).

Определим условия, которым правильные БО должны удовлетворять. Рассмотрим вспомогательную задачу:

Р{г) = {аТ шах, (42)

Аг<Ь,Ъ<г<\, (43)

Р = [№*)]• (44)

где г° оптимальное решение задачи (42) - (43) и р - правая часть (40). Возможны три исхода.

1. г° = х°. В этом случае (40) является сильным отсечением.

2. 2° * х° и ^(аг,х°)] Тогда (40) - соответственно слабое правильное отсечение.

3. Iй Ф х° и ^(аг,х0)] < . При данных обстоятельствах имеет место

положительная целочисленная невязка // = ->0 и неравен-

ство (ат,х) < ^(аг,х°)] - неправильное отсечение. Тогда (ат,х) < ¡3 с правой

частью (44) не имеет смысла, поскольку не будет активным при дополнении им задачи (37)-(38).

1.5

о

0.5

°0 0.5 1 1.5

0< х, < 1

Рис. 8. Пример «слабого» правильного бинарного отсечения

Графическая иллюстрация построения слабого БО на примере: у(х) = Зх, + 2х2 —> тах, 2х1 + х2 < 2.3, 2.5^ +3х2 <3.325, х,-х,<0.8,

хих2 е ¡2 представлена на рис. 8.

В релаксированной задаче последнее условие заменено на: Q<Xj<\,j = \,2. Ее оптимальное решение: (х°)г=(0.85, 0.6) и /^=3.75. Целевая функция задачи (42)-(44) р{г) = + —» шах .

Решение вспомогательной задачи (г°)г =(0.53, 1) не совпадает с л:0, однако отсечение х1 + х2 <1 является правильным (выполнено условие 2).

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

Для определения правильности БО кроме (42)-(44) можно воспользоваться альтернативным признаком. Определим:

(ат,х)>Р(х°) +1, (45)

где /?(х°) = [(<5г,3с0)] и х°- решение задачи (37)-(38).

Т^.х^З^+^-г-тах

'•'Vх.. V 2х,+^2.3 "\Л?Лх|+2х2<3.'Ц5^ Г=3х1+2х2->тах

\ЛАЗХ1+2Х2= Ч" 1\5

Если задача (37)-(38), (45) имеет решение, то отсечение (ат,х) < /?(х°) неправильное. И напротив, если (37)-(38), (45) решения не имеет из-за противоречивости системы (38), (45), то (ат,х) < /?(х°) - правильное БО.

Так, для рассмотренного примера (рис. 8) легко убедиться в том, что дополнительное ограничение х1+х2^.2 делает систему неравенств несовместной и X] + х2 < 1 - правильное отсечение.

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

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

1) Правило ненулевых координат предшествующей релаксации. Коэффициенты левой части БО вычисляются по правилу:

II, если x°j > О О, если х] = О

Правая часть вычисляется в соответствии с (40).

2) Правило ближайшего отсечения к порождающему неравенству. Сводится к решению следующей задачи:

найти коэффициенты а у е { 0, 1 },j = 1,и, максимизирующие выражение

*(«) = ПТ? <46>

Иг Иг

Для точного решения этой задачи разработан алгоритм трудоемкости 0(п log п), основой которого является сортировка.

3) Выбор на множестве оценок переменных текущей релаксации.

Пусть Лу- оценки переменных Ху задачи (37)-(38), определяемые как оптимальные двойственные оценки ограничений ху<\, 7 = 1,п. iоценки ограничений задачи двойственной к (37)-(38). Из условий дополняющей нежесткости следует: Л° = 0, если х" < 1 и Л*} > 0, если х° = 1. Причем случай Лу = 0 и

Xj = 1 может иметь место, только при наличии альтернативных оптимумов в текущей релаксации. В качестве оценок базисных переменных ху для случая 0 < х® < 1 используем штрафы за увеличение ху до единицы (hj) и за уменьшение до нуля (hj).

Если обозначить через а} у коэффициенты строки разложения / - й базисной переменной в оптимальной таблице, а соответствующий коэффициент

столбца правых частей через х/°(< 1), то для точной оценки штрафа за снижение х, до нуля, в преобразованную задачу необходимо добавить ограничение

п

< , где небазисные переменные в оптимальной таблице. Для

>1

точной оценки штрафа за увеличение х1 до единицы, в преобразованную задачу

п

необходимо добавить ограничение Обе такие оценки требуют

М

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

Ш

= -тах<

<о -о

■ Х[ ,

Ъ{ = - шах

■и.

•(1-х?).

В общем случае оба штрафа вычислим в соответствии с выражениями: Я®, если х? = 1,

х,°, если 0<х,° <1,

(1-х,0), если 0<Х/°<1, Vесли х;°=0.

Тогда приоритет координаты х, в отсечении можно определить, например, как показано ниже (47). Посредством (47) можно оценить все координаты и ввести в соответствии с hj,j = 1 ,п отношение нестрогого порядка на всем множестве ху,у = 1 ,п. Благодаря этому возможны построение и оценка целого ряда альтернативных отсечений (40), а не единственного, как при использовании первой и второй эвристик.

Л!, если х1 = 1,

-тах <|

<о

3

I 3

■ х, + тах

<° К-.

•(1-Х/0), если 0< х;° < 1,

(47)

если х;°=0.

В соответствии с (47) разобьем все множество переменных на три непересекающихся подмножества и упорядочим по убыванию. Пусть щ, п2, и3 - число

элементов в каждом из них. Причем первому принадлежат все х^] = 1 ,п{, второму- Ху,у = и, + 1,и,+и2 , третьему - + п2 +\,п

Рассмотрим совокупность А из п2 векторов, размерности п а1 = (1,1,...,1,0,0,...,0) (содержит и, +1 начальных единиц), а1 = (1,1,...,1,1,0,...,0) (содержит щ + 2 начальных единиц),

а"1 =(1,1,...,1,1,1,...,0) (содержит щ+п2 начальных единиц), Каждому вектору соответствует невозрастающая оценка hj,j = 1 ,п2. Поэтому для поиска коэффициентов наилучшего отсечения (40) на совокупности А достаточно последовательно синтезировать от одного до п2 БО, до выполнения условий, присущих правильным отсечениям, либо до исчерпания элементов А.

4) Выбор на множестве ближайших отсечений.

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

о^ад...,«)),

й2=(1,1,0,...,0),

=(1,1,...,1,0,0,...,0) (содержит у начальных единиц), а"=(1,1,...,1).

Каждому а1 поставим в соответствие к(а]) из (46). Тогда дискретная функция к {а') однозначно определит приоритет каждого из (альтернативных)

(сТ а]) —

отсечений с коэффициентами а'. Здесь к{а])= .' . ,у = 1,и. Данная функ-

И2Г|2

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

На основе бинарных отсечений и предложенных эвристических правил их построения можно создать ряд алгоритмов решения ЗЛПБП, нормализованной (37)-(39) и, опосредованно, исходной (33)-(35).

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

32

ции дополняющая матрица Аи коэффициентов, составляющих БО, всегда является частью базисной матрицы системы ограничений (38), (41).

В этом случае построение А° полного ранга гарантирует оптимальность решения ЗЛПБП (37)-(39). Рис. 9 иллюстрирует результаты работы циклического алгоритма при решении следующей нормализованной ЗЛПБП. у(х) = 3х{ +2х2 ->шах, 2х1 +х2 <2.3, 2х,+3х2 <3.5, х1 -х2 <0.8, хих2 е12. В релаксированной задаче последнее условие заменяется на 0 < х} < = 1,2.

Т(^)1)^)=3х1+2х2->тах

1.5

0.5

ч \ 2^+^2.3 ;

\ ^ Г=3х1+2х2-^тах

\ V

1 \

Ж \

Рис. 9. Построение полной системы бинарных отсечений

Схема формирования подсистемы (41) в данном случае выглядит следующим образом (/ - номер шага алгоритма): /:=!-»(а'т,х):= х1 +х2Д = 1 —>х, +х2 < 1;

/:=2->(а'г ,х):=х1г Ь2= 0-

л:, <0. Тогда Аи =

"1 1" "1" * , х = "0"

1 0 0 1

Га

= 2.

Оптимальное решение найдено за два шага с построением А полного ранга. Схема и результат полностью совпадает с аналогичной схемой и результатом решения рассмотренного выше примера (рис. 8).

Вместе с тем циклический алгоритм обнаружил ряд отрицательных свойств. Во-первых, это необходимость на каждом его шаге обеспечивать активность подсистемы введенных ранее отсечений. Во-вторых, циклический алгоритм приводит к вырожденности формируемой задачи (37)-(38), (41) до построения дополняющей подсистемы полного ранга, что, в свою очередь, приводит к существенному усложнению алгоритма. В-третьих, при фиксации величины ц для обеспечения эффективности алгоритма, существует опасность исключения из рассмотрения оптимумов ЗЛПБП (37)-(39).

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

Свойства программной реализации АБОВ исследованы в разделах 7 и 8. В табл. 3 приведены апостериорные оценки, полученные в результате расчетов 30 сгенерированных тестовых примеров различной размерности. Апробированы простейшие варианты процедуры синтеза бинарных отсечений. Эффективность предложенных производных процедур (3 и 4) требует дополнительного анализа, что отмечено в табл. 3 звездочками.

Экспериментально подтверждены надежность алгоритма бинарных отсечений и ветвлений и его применимость для решения смешанных частично-целочисленных задач оптимизации. Последнее свойство также является преимуществом АБОВ перед циклическим алгоритмом.

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

Верхняя оценка трудоемкости решения ЗЛПБП, общая для всех переборных алгоритмов, составляет: N = 2", где N - число релаксированных подзадач, которые нужно решить для гарантированного определения оптимума, п - число булевых переменных в задаче. Такую оценку трудоемкости обеспечивают, например, метод полного перебора и динамического программирования.

Таблица 3.

Эффективность применения эвристических процедур синтеза БО

Наименование процедуры Число правильных отсечений в общем количестве (%)

минимум максимум в среднем

1) По ненулевым координатам предшественника 31 63 50

2) выбор ближайшего отсечения 15 40 30

3) выбор на множестве оценок переменных _* 91*

4) выбор на множестве ближайших отсечений 75*

В МВГ N соответствует максимальному числу концевых вершин дерева решений. Поскольку длина любой ветви древа от начальной вершины до концевой составляет 0{п), то верхняя оценка трудоемкости МВГ выше, чем у полного перебора: Иьь = 0(п)2".

Определим ИЬс - верхнюю оценку трудоемкости АБОВ. Верхняя оценка числа бинарных отсечений, необходимых для нахождения оптимума ЗЛПБП, при условии, что все отсечения правильные, равна 0(п2). Доля правильных БО

34

в общем количестве является мерой эффективности эвристики, применяемой в рассматриваемых алгоритмах. Обозначим эту величину через S, 0 < ö < 1. Тогда Nbc = 0(n2)2(>~S)" - верхняя оценка трудоемкости АБОВ. Обратимся вновь к табл. 3, из которой следует апостериорная оценка гарантированного числа правильных БО 30% от общего числа отсечений. Таким образом, имеем оценку эффективности первой эвристики £ = 0,3, откуда общая оценка Л/^ = 0(п2)20'7".

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

сравним Nhh и N..: Nbb/Nbc =-\ П1 =-г- Если положить и = 1000,

Г ЬЬ Ьс ЬЬ ос 0(п)

получим трудоемкость Nbc на 86 порядков ниже чем Nbb.

Заметим также, что при стремлении S к единице, АБОВ становится вычислительно эффективным алгоритмом целочисленного программирования. Этот вывод справедлив и для циклического алгоритма.

Материалы шестой главы обеспечивают необходимый фундамент решения оценочных задач линейного и полуопределенного программирования, используемых в вычислительных методах, разработанных в рамках прикладного раздела (первая часть работы, главы 1-4), а также в рамках пятой главы. Глава посвящена разработке эффективной модификации барьерного алгоритма следования центральному пути (АСЦП), входящего в группу методов внутренних точек. Алгоритм имеет полиномиальную сходимость при решении задач линейного и полуопределенного программирования. Разработанная модификация включает ряд усовершенствований, содержащих выбор наилучших комбинаций процедур выбора длины шага, вида барьерной функции, модификаций прямого и итерационного алгоритмов решения порождаемых последовательностей систем линейных алгебраических уравнений (СЛАУ).

Пара задач ЛП, решаемых АСЦП с учетом ослабляющих переменных: Ps: найти max{crx: Ах + у = Ь, х>0,_у>0},и

Ds: найти min{bTu: ATu-v = с, u>0,v>0}, задается в виде однородной самодвойственной задачи (с учетом обозначений b =b — Ах°, с = с — Аги° - s°, z=cTx° + l-bTu°):

найти min ((х°)г+ \)в при ограничениях

(x,S,U,6)

-cT x +bTu +16 > 0,

cr -ATu -св > о,

-br +Ax +ьв = 0,

~zx +cT x -bTu = -((*0)V+D,

(r,x) > 0,

{и,в) свободные.

Обозначим также:

' 0 AT -c х 's(x) V

M = -A 0 +b , X = и , s =s(x)= s(u) = У

+cT -bT 0 J(T)_ P_

s(x) = Mx.

Решение исходной пары задач Ps и D определяется как — ,—

т т

Мх > 0; х > 0;

х и

Если определить вектор г = е-Ме, матрицу

M

-гт

, число Л = п + \ и

дополнить переменные задачи парой 9 и м>, то система, определяющая центральный путь, запишется следующим образом: М г!

-гт 0

X s 0 x >0, X s це

+ = =

У w Л ■У w ¿1 w

(48)

В качестве стартовой точки можно выбрать единичный вектор (х°,5°,?°,м;0) = (е,1,е,1), который всегда является допустимым решением (48), т.к. принадлежит центральному пути. Начальное значение параметра ц = 1.

Шаг метода Ньютона состоит в поиске приращений (А^Д^?, Д?,ДиО после редукции параметра ц, таких, что:

Г О I Гт + Лх I Г.? + д.?

>0,

' M r x +Ax s+ As "0" x +Ax s + As

.S ». .9 + Д.9 + w + Aw _л_ s 5 + Д5 w + Aw

x + Aï s + A? ne

5 +Ai9 w + Aw

Пренебрегая квадратичными слагаемыми AXAS и A^Aw системы уравнений, получаем ее линейную аппроксимацию:

-МАх -гА9 +Д? = 0

гтАх SAx

+Aw = 0

+ХД? = /ie-Xs

wA& +i9Aw = fi — 3w

После определения (Дх,Д<9,Ду,Аи'), следует скорректировать текущее решение, используя при необходимости ослабляющий фактор а: х := х + аАх,9\= 9 + аАЗ := I + аА$ м> + аМ>.

Основные параметры, с которыми оперирует модифицированный АСЦП в раках диссертационной работы, определены таким образом, чтобы добиться универсальности относительно используемых барьерных функций (БФ):

1. В качестве меры близости к центральному пути используется любое из выражений:

, а - любая са-

^ = ¿4^,) и где

}=\ 1 V Р

мосогласующаяся одномерная БФ, - градиент Ч'(и) и 5(р) по

определению являются самосогласующимися многомерными БФ).

2. Трансформируется система (49):

-МАх -г Ад +Д? = О

гт Ах +Ач> =

5Дх +ХД?

1

/

.Чм; 12

ч/А9 +5Д\у =

(50)

3. Определяется окрестность центрального пути для всех у., посредством решения уравнения = /? - предельная мера близости к центральному пути. Вычисленные корни уравнения 0 < у, < 1, 1 < уц < оо определяют допустимую окрестность центрального пути. Тем самым задаются условия Г/<и,.<гн,У/ = и + 1.

4. Критерии останова алгоритма.

Критерий останова классического АСЦП (п +1)// < е) имеет скорее теоретическое, чем прикладное значение. Данное условие при больших п на конечных итерациях опосредует столь малые значения барьерного параметра /л, что на фоне вычислительных возмущений алгоритм теряет устойчивость. Это может привести к нулевой длине шага с зацикливанием и плохой обусловленности матрицы А. Причиной является погрешность метода, заключающаяся в образования на завершающих шагах как близких нулю, так и машинной бесконечности элементов диагональной матрицы Х~1Б (при оптимальном решении х и ^ ортогональны). На этот естественный процесс накладываются ошибки округления, из чего вытекает потребность в двух вспомогательных критериях останова:

а < £х, и Дг < е2, ег > ^ > е. (51)

Обычно в практике применения МВТ используется совокупность критериев - невязок решений пары Р1 и й* , либо свертка невязок. В частности, в МаЙаЬ в качестве критерия останова модуля Пряв! применяется

37

ы2

\ст х-Ьти\

шах(1,||Ь||2) шах(1,|с||2) тах(1,|сг.х|,|г>7'м|)

где, гь= Ах + у-Ь, гс= Аги - V - с.

Условия Куна - Таккера для Р5 и О5 опосредуют: для активных ограничений Р*: 17(Ь - Ах) = ре => 1/гь = ре => гь = Vх ре; для активных ограничений : Х(Ати - с) = //е => Л>с = ре =>гс = Х~хре.

^ II II А I Г .7" I т

' гс ? = 1ЛГ~' г " Тогда критерии останова

ПОЭТОМУ |К||2-НМ,-е„2 ||х|ь ,

(52) применительно к АСЦП будет выглядеть следующим образом:

_ >" __ V__Р

шах(1, ||м||2, ||й||2 ||м||2 ) шах(1, ||х||2, ||с||2 ||х||2) шах(1, |сгх|, |йгм|) Очевидно:

<Е.

(53)

тах(1,||и||2)||й||2||м||2) тах(1,||х||2,||с||2||х||2) тах(1,|с7'д:|,|бгм|) Н'

Поскольку р также пропорционально р, то, по сути дела, критерий останова (53) эквивалентен рк < е , где к > 1 - некоторая константа. Несмотря на то, что (53) не зависит от размерности и много мягче (и + Х)р < е, он не исключает употребление дополнительных условий останова (51).

В разделе 6 представлена процедура определения оптимальной длины шага АСЦП. Показано, что ослабляющий параметр длины шага а определяется, как результат совместного решения в общем случае т + п +1 следующих одномерных задач оптимизации.

Найти а = шт(шах( а .),тах( а^)) при условиях

2 ру$(уА

ах/+-~-— «X/ +

1 ] г

ру${у}~) X]

рУ^)

*

Ах ,. Ас,

AXjSj Аху

/ \ Х1 2 2 , /'У/ \

АС; т АС , Ах,-

V У у /

/ > 2 2 \

+

АС ; V У У Ах^. Ас-

<0, V/ = 1 ,п,

>0, V/ = 1 ,п.

При этом доказано, что БФ должны обладать свойством: и2: — и$ (и^ > у] Тогда:

2*уДх, 1

ри$'(У]) х]

25',АХ,. АХ. V } ] ) У

> И

=—-—----— V/ = 1 ,п.

а ■ =——-а-

Для рассматриваемой модификации АСЦП по результатам анализа (разделы 6 и 7) определены две наилучшие БФ (из 9 рассмотренных разновидностей, принадлежащих классам саморегулируемых и самосогласующихся барьерных функций): 4*9(0 > включающая, как частный случай ф4(0 и являющаяся, по сути, семейством функций, и классическая логарифмическая (?)

I1 -1 1Р+Х-1 и-а

= ,Ф9(0 = -Ц—-+-7—О <р<\^>\).

2 р{р + \) 9(9-1) р.?

В разделах 8 и 9 разработаны модификации прямого и итерационного алгоритмов решения последовательности СЛАУ специального вида (50), порождаемой АСЦП. Прямой алгоритм основан на разновидности треугольного разложения, максимально учитывающей специфику матрицы системы и имеющую минимальную для прямых методов трудоемкость. При этом система (50) приводится к квазисимметричному виду, что и позволяет получить совокупную трудоемкость прямого алгоритма решения рассматриваемых СЛАУ, не превышающую трудоемкость метода квадратного корня (для симметричных систем).

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

В совокупности разработанная модификация АСЦП включает все перечисленные усовершенствования и выглядит следующим образом:

1. Выбор: 1) самосогласующейся БФ ф(0 и ее параметров, удовлетворяющих условиям процедуры определения оптимальной длины шага; 2) собственно процедуры вычисления длины шага а\ 3) предельной меры близости к центральному пути р; 4) параметров точности решения е,ех,ег > 0,е2 < £\ < £', 5) декремента барьерного параметра в, 0 < в < 1;

2. Задание начальной точки (х°,5°), и /л° < 1, таких, что ^(х0,?0,//0) < /7;

3. х := х ; 5 := 5 \ ц .= ц ;

и ц р

4. Если--—I........— +-. ,. . < е,

тах(1, ||и||2, ||г>||2 ||и||2) тах(1, ||х||2, |с|[2 ||х||2 ) тах(1,\стх\ ,\Ьти\)

или а<Е\, или Дт < е2, конец работы алгоритма, иначе:

5.

6. Если ^(х,?,^) < /?, возврат к п. 4, иначе:

7. Решение системы (50), (определение Ах, А?);

8. Вычисление параметра длины шага а;

9. х := х + а&х; ? := 5 + аД?; возврат к п. 6. ■

Программная реализация и тестирование алгоритма подтвердили его высокую эффективность. Так быстродействием программная реализация многократно превзошла модуль Ма^аЬ \ipsol и почти в 1.5 раза реализацию барьерного алгоритма в СРЬЕХ для однопроцессорного (без распараллеливания вычислений) варианта. При этом алгоритм, протестированный на множестве сгенериро-

39

ванных задач больших размерностей, обнаружил высокую численную устойчивость. Одним из результатов проведенного эмпирического анализа является вывод о фактической независимости числа шагов АСЦП от размерности решаемых задач, которое принадлежит интервалу [16 24] (размерности тестов менялись в диапазоне [400x300 10000x5000] при плотной заполненности матрицы ограничений).

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

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

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

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

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

4. Разработаны алгоритмы оптимизации расписаний классической задачи job shop: точный алгоритм (на основе метода ветвей и границ) и приближенные алгоритмы, основанные на неполной декомпозиции, фактически являющиеся эффективными при соблюдении регулируемых ограничений на размерности подзадач, порождаемых в процессе счета.

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

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

6. В рамках концепции параллельно-последовательных систем рассмотрен подход к формализации и решению задачи календарного планирования строительства скважин НГКМ с явным заданием последовательности бурения. Результирующая формальная постановка позволяет эффективно применить разработанные прямые алгоритмы оптимизации расписаний ППОС для нефтегазо-конденсатных месторождений.

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

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

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

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

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

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

Статьи в журналах из перечня ведущих рецензируемых научных журналов и изданий, в которых должны быть опубликованы основные научные результаты диссертаций:

1. Мезенцев Ю.А. Алгоритмы синтеза расписаний многостадийных обслуживающих систем в календарном планировании. Омский научный

вестник. Омск, Изд-во ОГТУ 2006. №3(36) С. 97-102.

2. Мезенцев Ю.А. Декомпозиционный метод решения одного класса задач оптимального проектирования. Научный вестник НГТУ. Новосибирск, Изд-во НГТУ 2006. №3(24), С. 67-100.

3. Мезенцев Ю.А. Практические аспекты эффективности алгоритма следования центральному пути метода внутренних точек. Научный вестник НГТУ. Новосибирск, Изд-во НГТУ 2006. №4(25) С. 67-104.

4. Иванов Л.Н., Мезенцев Ю.А. Модели синтеза расписаний параллельных обслуживающих систем. Омский научный вестник. Омск, Изд-во ОГТУ 2006. №9(46) С. 164-167.

5. Иванов Л.Н., Мезенцев Ю.А. Методы оптимизации расписаний параллельных обслуживающих систем. Программные продукты и системы. Тверь, Изд-во МНИИПУ и НИИ «Центрпрограммсистем» 2008. №1 С. 72-74.

6. Мезенцев Ю.А. Оптимизация расписаний параллельных динамических систем в календарном планировании. Информационные технологии. М., Изд-во «Новые технологии» 2008. №2 С. 24-33.

7. Мезенцев Ю.А. Математические модели управления подсистемами логистики на предприятиях. Журнал «Автоматизация и современные технологии», М, Изд-во «Машиностроение» 2008. №8. С. 46-55.

8. Мезенцев Ю.А. Оптимизация расписаний последовательно- параллельных обслуживающих систем. Программные продукты и системы. Тверь, Изд-во МНИИПУ и НИИ «Центрпрограммсистем» 2009. №1 С. 22-26.

9. Мезенцев Ю.А. Неполная факторизация и вопросы эффективности алгоритма центрального пути. Научный вестник НГТУ. Новосибирск, Изд-во НГТУ 2009. №1(34), С. 69-85.

10. Мезенцев Ю.А, Эффективный алгоритм целочисленного программирования. Научный вестник НГТУ. Новосибирск, Изд-во НГТУ 2009. №2(35), С. 91-114.

11. Мезенцев Ю.А. Оптимизация расписаний параллельно-последовательных систем в календарном планировании // Информационные технологии. М., Изд-во «Новые технологии» 2009. №6 С. 35-41.

12. Авдеенко Т.В., Кравченко A.B., Мезенцев Ю.А. Модели планирования производства изделий, основанных на нанотехнологиях // Программные продукты и системы. Тверь, Изд-во МНИИПУ и НИИ «Центрпрограммсистем» 2009. №4 С. 22-25.

13. Мезенцев Ю.А. Метод бинарных отсечений и ветвлений целочисленного программирования // Доклады академии наук высшей школы РФ. Новосибирск: Изд-во НГТУ 2011. № 1(16) С. 12-25.

14. Мезенцев Ю.А., Павлов U.C. Реализация алгоритма решения специальных задач полуопределенного программирования с использованием IBM ILOG CPLEX // Научный вестник НГТУ. Новосибирск, Изд-во НГТУ 2011. №4(45), С. 25-34.

15. Мезенцев Ю.А., Павлов П.С. К программной реализации декомпозиционного алгоритма решения одного класса задач дискретной оптимизации с полуопределенной релаксацией // Информационные технологии. М., Изд-во «Новые технологии» 2012. №2 С. 54-59.

16. Мезенцев Ю.А. Эффективный алгоритм решения одного класса задач целочисленного программирования. // Доклады академии наук высшей школы РФ. Новосибирск: Изд-во НГТУ 2012. № 2(19) С.42- 53.

17. Мезенцев Ю.А., Павлов П.С. Практические аспекты решения одной задачи оптимального планирования обустройства нефтегазоконденсатных месторождений // Научный вестник НГТУ. Новосибирск, Изд-во НГТУ 2012. №4(49), С. 48-55.

18. Мезенцев Ю.А. Практические аспекты реализации эффективного алгоритма решения задач оптимальной комплектации. // Доклады академии наук высшей школы РФ. Новосибирск: Изд-во НГТУ 2013. № 1(20) С. 2634.

Свидетельства об официальной регистрации программных систем разработанных на основе результатов диссертации:

19. Программная реализация прямо-двойственного барьерного алгоритма следования центральному пути для решения задач линейного программирования большой размерности / Мезенцев. Ю.А. // Свидетельство о государственной регистрации № 2012611589 (Россия). Зарегистрировано 10.02.2012. Приоритет от 14.12.2011. Заявка № 2011619552.

20. Программный комплекс быстрого решения задач оптимальной комплектации систем / Мезенцев Ю.А. // Свидетельство о государственной регистрации № 2012617398 (Россия). Зарегистрировано 16.08.2012. Приоритет от 19.06.2012. Заявка № 2012615085.

21. Программный комплекс оптимального планирования закупок и сбыта продукции / Мезенцев Ю.А., Павлов П.С. II Свидетельство о государственной регистрации № 2012611279 (Россия). Зарегистрировано 31.01.2012. Приоритет от 02.12.2011. Заявка № 2011619206.

22. Программный комплекс оптимального управления поставками сырья и комплектующих на предприятии / Мезенцев Ю.А., Павлов П.С. И Свидетельство о государственной регистрации № 2012617400 (Россия). Зарегистрировано 16.08.2012. Приоритет от 19.06.2012. Заявка № 2012615087.

Монографии:

23. Наумов A.A., Мезенцев Ю.А. Оптимальное управление инвестиционным портфелем. Новосибирск: Издательская компания Лада, 2002,192 с.

24. Мезенцев Ю.А. Математические задачи оптимального управления реализацией проектов. Новосибирск: Изд-во НГТУ, 2013, 142 с.

Доклады на международных конференциях:

25. Avdeenro T.V., Mezentsev Y.A. Time-table optimization for parallel-serial production systems on the basis of heuristics methods // Proceedings of DST-RFBR Sponsored Indo-Russian Joint Workshop on Computational Intelligence and Modern Heuristics in Automation and Robotics, 20-22 September 2010, Su-rat, India, pp. 25-29.

п

26. Авдеенко Т.В., Мезенцев Ю.А. Задачи синтеза оптимальных расписаний нанотехнологических производств // Материалы международной научной конференции «Моделирование 2010» Том 1, Изд-во Института проблем моделирования в энергетике, Киев, 2010., С. 88-96.

27. Мезенцев Ю.А. Задачи и алгоритмы оптимизации расписаний параллельных обслуживающих систем с динамическим входом // Материалы X Международной научно-практической конференции «Методы и алгоритмы прикладной математики в технике, медицине и экономике». Новочеркасск, Изд-во ЮРГТУ 2010., С. 13-17.

28. Мезенцев Ю.А. Об одной задаче математической логистики // Сборник трудов XV международной открытой конференции «Современные проблемы информатизации в экономике и обеспечении безопасности». Воронеж, Изд-во «Научная книга» 2010. вып.15, С. 22-29.

29. Avdeenko Т. V., Mezentsev Y.A. Models and algorithms for calendar production planning // Proceedings of RFBR and DST Sponsored "The 2-nd Russian-Indian Joint Workshop on Computational Intelligence and Modern Heuristics in Automation and Robotics", 10 - 13 September, 2011, Additional vol., pp.11-15.

30. Мезенцев Ю.А. Об одном алгоритме решения задач теории расписаний в приложении к календарному производственному планированию // Материалы VI международной конференции «Актуальные проблемы электронного приборостроения» (АПЭП-2002), т.7. Новосибирск 2002, С. 184-190.

31. Мезенцев Ю.А., Преображенская Т.В. Модель оптимального выбора проекта по критерию цена/качество (на основе функционально-стоимостного анализа) // Материалы Международной научно-технической конференции «Информационные системы и технологии» ИСТ"2003 Том 1 НГТУ 2003, С. 95-96.

Отпечатано в типографии Новосибирского государственного технического университета 630073, г. Новосибирск, пр. К. Маркса, 20, тел./факс (383) 346-08-57

формат 60x84/16, объем 2.75 п. л., тираж 120 экз.,

заказ № 1223, подписано в печать 01.10.2013 г.

Новосибирский государственный технический университет

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

05201352061

Мезенцев Юрий Анатольевич

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

Специальность 05.13.01 - Системный анализ, управление и обработка

информации (промышленность)

Диссертация на соискание учёной степени доктора технических наук

Научный консультант д.т.н., проф. Т.В. Авдеенко

Новосибирск - 2013

СОДЕРЖАНИЕ

Введение 8

I. Специальные прикладные задачи дискретной оптимизации и методы синтеза управляющих воздействий 24 Глава 1. Модели и алгоритмы синтеза расписаний одностадийных обслуживающих систем 25

1.1. Модели теории расписаний и оперативно - календарное планирование производства 25

1.2. Постановка задачи синтеза оптимальных расписаний параллельно-последовательной обслуживающей системы 28

1.3. Постановка задачи оптимизации расписаний параллельной системы с задержками поступления заявок 30

1.4. Редукция задачи оптимизации расписаний параллельной системы в задачу частично-целочисленного линейного программирования 35

1.5. Бикритериальная упрощенная формулировка задачи синтеза расписаний параллельной системы и алгоритм решения 40

1.6. Числовой пример синтеза расписаний параллельной системы с задержками поступления заявок 43

1.7. Оценка эффективности релаксации задачи синтеза расписаний параллельной системы 47

1.8. Декомпозиционные приближенные алгоритмы оптимизации расписаний параллельной системы с задержками поступления заявок 50

1.9. Числовой пример использования декомпозиционных алгоритмов оптимизации расписаний параллельной системы с задержками поступления заявок 58

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

нефтегазоконденсатного месторождения (поэтапный подход)

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

1.12. Выводы, некоторые обобщения и нерешенные вопросы

Глава 2. Модели и алгоритмы синтеза расписаний многостадийных обслуживающих систем в календарном производственном планировании

2.1. Последовательные многостадийные обслуживающие системы. Модели на смешанных сетях

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

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

2.4. Числовой пример применения алгоритмов синтеза расписаний последовательной системы

2:5. Оценки эффективности моделей и алгоритмов синтеза расписаний последовательной системы

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

2.7. Прямой алгоритм оптимизации расписаний параллельно-последовательных обслуживающих систем

2.8. Числовой пример применения прямого алгоритма оптимизации расписаний

2.9. Декомпозиционный алгоритм оптимизации расписаний многостадийных параллельно-последовательных обслуживающих систем

2.10. Иллюстративный пример применения циклического декомпозиционного алгоритма

2.11. Приложение моделей и алгоритмов оптимизации расписаний многостадийных параллельно-последовательных систем.

Оптимизация календарного плана строительства скважин нефтегазоконденсатного месторождения (подход на основе обобщенных сетей) 113

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

2.13. Комплекс программ оптимизации расписаний параллельно-последовательных систем 124

2.14. Результаты, обобщения и направления развития 125 Глава 3. Дискретные задачи управления взаимодействием предприятий с внешней средой и специальные численные методы их решения 128

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

3.2. Содержательная постановка задачи управления материальными потоками предприятия 130

3.3. Формальная постановка задачи оптимизации управления входными и выходными материальными потоками 132

3.4. Задача оптимизации поставок сырья и комплектующих на предприятии. Содержательная постановка 136

3.5. Формальная постановка задачи оптимизации поставок 138

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

3.7. Иллюстративный пример. Решение задачи оптимизации закупок

и сбыта продукции 143

3.8. Определение оптимальных цен продаж 147

3.9. Декомпозиционный алгоритм решения задачи оптимизации поставок 156

3.10. Численный пример применения декомпозиционного алгоритма оптимизации поставок 159

3.11. Программные средства оптимизации управления входными и выходными материальными потоками предприятия 163

3.12. Результаты и выводы 167 Глава 4. Задачи оптимальной комплектации и эффективные алгоритмы их решения 170

4.1. Содержательная постановка задач оптимальной комплектации 170

4.2. Формальная постановка задачи оптимальной комплектации 173

4.3. Редукция систем логических ограничений. Линеаризация задач оптимальной комплектации 178

4.4. Декомпозиционный алгоритм решения задач оптимальной комплектации 183

4.5. Экспериментальное исследование быстродействия и точности алгоритма 189

4.6. Теоретическая оценка трудоемкости декомпозиционного алгоритма оптимальной комплектации 193

4.7. Программная реализация алгоритмов решения задач оптимальной комплектации 193

4.8. Выводы и некоторые обобщения 195 II. Эффективные методы решения задач линейного и целочисленного программирования 197 Глава 5. Метод бинарных отсечений целочисленного линейного программирования 197

5.1. Современное состояние и проблемы теории и практики дискретной оптимизации 197

5.2. Постановка задачи и основные понятия метода бинарных отсечений 199

5.3. Бинарные отсечения и алгоритмы их формирования 211

5.4. Циклический алгоритм оптимизации, базирующийся на бинарных отсечениях 222

5.5. Примеры применения циклического алгоритма бинарных отсе-

чений 227

5.6. Оценка трудоемкости возможных модификаций циклического алгоритма 232

5.7. Алгоритм бинарных отсечений и ветвлений 234

5.8. Оценка трудоемкости возможных модификаций алгоритма бинарных отсечений и ветвлений 238

5.9. Результаты и выводы 240 Глава 6. Эффективные вычислительные методы линейного и выпуклого программирования 241

6.1. Современное состояние исследований в области линейного и выпуклого программирования 241

6.2. Алгоритмы центрального пути в линейном программировании 243

6.3. Техника вычислений классического алгоритма следования центральному пути 249

6.4. Некоторые свойства барьерных функций 253

6.5. Модифицированный алгоритм следования центральному пути 257

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

6.7. Экспериментальное исследование влияния вида и параметров барьерных функций на сходимость алгоритма следования центральному пути 268

6.8. Прямые алгоритмы решения линейных систем специального вида в алгоритме следования центральному пути 272

6.9. Итерационный алгоритм решения линейных систем специального вида 280

6.10. Эмпирический анализ свойств алгоритмов центрального пути и решения порождаемых линейных систем 287

6.11. Особенности программной реализации модифицированного 290 алгоритма следования центрального пути

6.12. Результаты и выводы 291

Заключение 293

Список использованных источников 297

Приложение 1. Тестирование алгоритмов синтеза расписаний параллельных систем 308

Приложение 2. Тестирование алгоритмов синтеза расписаний многостадийных систем 314

Приложение 3. Графическое представление и результаты работы прямых алгоритмов оптимизации расписаний ППОС 316

Приложение 4. Графическая иллюстрация работы декомпозиционного алгоритма оптимизации расписаний ППОС 318

Приложение 5. Дополнение к иллюстрации алгоритма определения оптимальных цен продаж в задаче управления закупками и сбытом продукции 326

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

Приложение 7. Численная иллюстрация шага модифицированного алгоритма следования центральному пути 359

Приложение 8. Результаты тестирования программной реализации модифицированного алгоритма следования центральному пути 361

Приложение 9. Сравнение вариантов прямого алгоритма решения СЛАУ специального вида в модифицированном алгоритме следования центральному пути 364

Приложение 10. Свидетельства о регистрации программ. Акты внедрения 366

ВВЕДЕНИЕ

Актуальность проблемы и цель работы

История развития современного аппарата дискретной оптимизации (ДО) началась с работ Балаша, Беллмана, Бендерса, Данцига, Гомори, Канторовича, Ху, ряда других авторов (конец 50-х, начало 60-х годов XX века). Позднее появилась теория вычислительной сложности задач дискретной оптимизации, и выделились основные направления развития алгоритмов их решения. Определились, ставшие классическими, сферы приложений: дискретные задачи управления производством (календарное планирование), дискретные задачи оптимального проектирования (размещение, комплектация), дискретные задачи управления логистикой (раскрой и упаковка, транспортировка, выбор поставщиков, ассортимента, определение маршрутов, управление запасами). Список можно существенно расширить. В настоящее время теоретические исследования в большинстве своем направлены на создание эффективных алгоритмов приближенного решения отдельных подклассов задач ДО с хорошими априорными либо апостериорными оценками точности. Под вычислительной эффективностью (или просто эффективностью) алгоритма понимается полиномиальная трудоемкость поиска решения задач ДО, что для практических применений зачастую важнее точности.

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

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

на этой основе.

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

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

В работе над диссертацией использованы как классические труды в области дискретной оптимизации и смежных разделах, так и работы современных авторов, теоретиков и практиков. В частности, главы, связанные с теорией расписаний, опираются на труды Гимади Э.Х., Гордона B.C., Jonson S.M., Загидуллина P.P., Конвей Р.В., Коффмана Э.Г., Левина В.И., Максвелла В.Л.,

Миллера Л.В., Мироносецкого Н.Б., Севастьянова C.B., Сотскова Ю.Н., Струсевича В.А., Танаева B.C., Фролова Е.Б., Шафранского Я.М., Шкурбы В.В. При разработке алгоритмов решения нелинейных оценочных задач использованы результаты Boyd S., Евтушенко Ю.Г., Немировского A.C., Нестерова Ю.Е., Vandenberghe L., Vanderbei, R. J. Алгоритмы, основанные на лагранжевой декомпозиции, либо на неполной декомпозиции опираются на работы Бахтина

A.Е., Гилл Ф., Гольштейна Е.Г., Gondzio J., Лэсдона Л.С., Малкова У.Х., Муртаф Б., Мюррей У., Райт М. При создании новых методов и алгоритмов решения общей задачи линейного программирования с булевыми переменными учтены достижения в этой области Алексеева О.Г., Гомори P.E., Емеличева

B.А., Забиняко Г.И., Заславского A.A., Колоколова A.A., Комлик В.И., Körte В., Корбут A.A., Кочетова Ю.А., Лебедева С.С., Леонтьева В. К., Лихтенштейна В.Е., Михалевича B.C., Пападимитриу X., Сергиенко И.В., Стайглиц К., Ху Т., Vygen J. Работы Дикина И.И., Frisch R.A., Gonzio J., Евтушенко Ю.Г., Жадан В.Г., Зоркальцева В.И., Jansen В., Karmarkar N. К., Немировского A.C. Нестерова Ю.Е., Ye Y., Roos С., Terlaky Т., Todd M.J., Vial J.- Р. послужили основой для разработки эффективной модификации алгоритма следования центральному пути, применяемого для решения последовательности оценочных подзадач в алгоритмах дискретной оптимизации.

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

ем попадают в интервал 0-5%, что может служить предварительной количественной оценкой степени достижения поставленной цели.

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

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

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

Задачи исследований

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

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

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

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

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

5. Разработка алгоритмов и программ решения по�