Содержание к диссертации
Введение
1. Обзор методов решения задач дискретной оптимизации 8
2. Метод последовательного исследования плоскостей уровня для задачи ЦШ1 общего вида 19
2.1. Постановка задачи и описание метода 19
2.2. Результаты вычислительных экспериментов 34
2.3. Применение метода для решения задачи замены оборудования 37
3. Приближенное решение задачи ДЛИ с матрицей ограничений специального вида 44
3.1. Постановка задачи и анализ применимости метода вектора спада для ее решения 44
3.2. Метод замен 49
3.3. Выводы и результаты вычислительного эксперимента 61
4. Задачи перспективного планирования в угольной промышленности 67
4.1. Задача перспективного развития действующих шахт .... 67
4.2. Задача оптимального проектирования шахты 87
ЗАКЛЮЧЕНИЕ 100
ЛИТЕРАТУРА 102
ПРИЛОЖЕНИЕ III
- Применение метода для решения задачи замены оборудования
- Постановка задачи и анализ применимости метода вектора спада для ее решения
- Задача перспективного развития действующих шахт
Введение к работе
В "Основных направлениях экономического и социального развития СССР на І98І-І985 гг. и период до 1990 г.", принятых на ХХУІ съезде KQCC, указано, что для ускорения перевода экономики на путь интенсивного развития, повышения эффективности общественного производства необходимо, в частности, направить усилия на "совершенствование вычислительной техники, ее элементной базы и математического обеспечения..." /33/.
В математическом программировании теория и методы оптимизации являются одним из наиболее эффективных разделов прикладной ма-тематики.
В последние годы большое внимание уделяется разработке и внедрению методов решения задач дискретной оптимизации.
Целью диссертационной работы является: изучить и обобщить опыт решения дискретных задач оптимизации, отраженный в отечественной и зарубежной литературе; разработать и исследовать новые методы решения задач полностью целочисленного линейного программирования (ЦЛП) общего и некоторых специальных видов; разработать программное обеспечение для решения задач ЦЛП "Библиотеки программ оптимизации и исследования операций для
СМ ЭВМ"; используя созданное программное обеспечение, решить задачу о замене оборудования машиностроительного завода; разработать комплекс программ для решения задач ЦЛП по перспективному планированию в угольной промышленности.
Предметом исследований стали следующие классы задач: задача ЩП общего вида с двусторонними ограничениями на неизвестные; задача ЦЛП, матрица ограничений которой наряду с ограни-
4 чениями-неравенствами содержит ограничения-равенства специального вида; - задачи оптимального планирования, которые по математической постановке являются задачами ЦЛП с булевыми неизвестными и матрицей ограничений специального вида, отнесенной к предыдущему классу.
Методологическую основу работы составляют методы построения последовательности решений и вектора спада.
Диссертация состоит из введения, 4 глав, списка литературы, заключения и приложения.
В первой главе приводится обзор методов решения задач дискретной оптимизации: подчеркивается актуальность рассматриваемых задач, обосновывается возрастающий интерес к исследованиям в этой области оптимизации, выделены наиболее распространенные классы задач, освещены вопросы вычислительной сложности этих задач, основанные на теории NP - полных задач, проанализированы существующие точные и приближенные методы, указаны основные направления развития теории и практики решения задач дискретной оптимизации.
Во второй главе рассмотрен точный метод решения задачи ЦЛП с матрицей ограничений общего вида и двусторонними ограничениями на неизвестные, относящийся к классу методов построения последовательности решений. Метод заключается в замене исходной допустимой области расширенным множеством с последующим анализом точек расширенной области, попадающих на плоскости уровня функции. Приведены алгоритмы, реализующие метод, перечислены и обоснованы пути ускорения работы алгоритма. Рассмотрена возможность построения ограничения-фильтр, сужающего область поиска решений. Для нахождения точек уровня построена серия алгоритмов направленного перебора. Приведены результаты вычислительного эксперимента по исследованию эффективности алгоритма на задачах различной размерности (максимальное число неизвестных - 200) и по решению реальной задачи замены оборудования машиностроительного завода.
В третьей главе рассмотрена задача ЦЛЇЇ, матрица ограничений которой содержит наряду с ограничениями-неравенствами ограничения-равенства специального вида. Проанализирована возможность применения метода вектора спада к задачам данного вида. Выделены свойства, которыми должна обладать задача, чтобы к ней был применим метод вектора спада (на основании требований невырожденности окрестностей). Изложен метод замен, являющийся модификацией метода вектора спада и позволяющий эффективно решать задачи рассматриваемого вида. Приведено сравнение методов, оценка их сложности. Приведены результаты вычислительного эксперимента по решению задач различной размерности (максимальное число неизвестных - 400).
В четвертой главе рассмотрены две задачи перспективного планирования в угольной промышленности. Описаны экономико-математические модели задач, отмечет актуальность задач. Для решения предложены два алгоритма - точный и приближенный, являющиеся реализациями методов, изложенных во второй и третьей главах, с учетом специфики задач. Приведены результаты по решению на ЭВМ тестовых задач, а так же серии задач, предложенных производственным объединением "Донецкуголь".
Материалы диссертационной работы внедрены в ряде организаций. Автором был разработан комплекс из 18 программ на языке ФОРТРАН для решения задач ЦЛП и решения диофантовых уравнений, в который, наряду с известными алгоритмами, включены программы, реализующие методы, изложенные во второй и третьей главах. Указанный комплекс вошел в созданную на кафедре прикладной математики Донецкого политехнического института "Библиотеку программ оптимизации и исследования операций" (общий объем около 100 программ), являющуюся частью "Библиотеки программ численного анализа и статистики для СМ ЭВМ" (архитектурная линия CM-I, СМ-2), разработанной научно-производственным объединением "Импульс" (г.Северодонецк), а также включенной в базовое математическое обеспечение ЭВМ CM 1210. Ожидаемый экономический эффект от внедрения разработанных автором программ - 36,5 тыс.руб. "Библиотека программ оптимизации и ЙСО" также внедрена в учебный процесс в Ленинградском механическом институте.
С помощью разработанных программ решена задача замены оборудования (металлорежущих станков) в механосборочных цехах завода "Славтяжмаш", экономический эффект от использования программ, разработанных автором - 10 тыс.руб.
Комплекс программ ЦЛП с булевыми переменными по перспективному развитию действующих шахт ( по методам изложенным в четвертой главе) включен в "Комплекс программ для выбора оптимальных технических решений по перспективному развитию действующих шахт Донбасса", созданный Донецким научно-исследовательским угольным институтом совместно с институтом Центрогипрошахт (г.Москва). Разработанные алгоритмы и программы позволили получить оптимальные перспективные планы развития трех производственных объединений Донбасса по добыче угля. Ожидаемый народнохозяйственный эффект - 200 тыс.руб.
Комплекс программ по оптимальному проектированию шахт передан Московскому горному институту.
В приложении приведены справки, подтверждающие внедрение.
По результатам работы имеется 13 публикаций. Алгоритмы и постановки задач ВДЇЇ вошли в методические пособия для студентов специальности 0647 (прикладная математика): 'Ч^уководство к практическим занятиям по курсу "Теория игр и исследование операций" (Донецк, ДІЙ, 1980 г.)."Методические указания к практическим занятиям по курсу "Исследование операций" (Донецк, ДОИ, 1983). Материалы диссертационной работы были доложены на: семинарах кафедры прикладной математики Донецкого политехнического института (Донецк, 1976-1984 г.); научно-технической конференции Донецкого политехнического института (Донецк, 1977 г.); республиканском семинаре "Математическое обеспечение автоматизированных систем обработки данных и пакетов прикладных программ" (институт кибернетики АН УССР, Киев, 1980 г.); республиканском семинаре "Методы решения и математическое обеспечение задач дискретной оптимизации (институт кибернетики АН УССР, Киев - 1982, 1983 г.);
П Всесоюзной школе по дискретной оптимизации (Кишинев, 1983 г.);
Всесоюзной школе молодых ученых и специалистов "Проблемы оптимизации в машиностроении" (Харьков - Алушта, 1983 г.); республиканском семинаре "Математическое обеспечение ЭВМ для решения экономических задач" (институт экономики промышленности АН УССР, Донецк, 1983 г.);
Всесоюзном семинаре "Дискретная оптимизация: методы и приложения" (Севастополь, 1984 г.);
Всесоюзном научно-техническом семинаре "Программное обеспечение мини- и микро-ЭВМ семейства СМ ЭВМ" (Москва, 1984).
Применение метода для решения задачи замены оборудования
Метод последовательного исследования плоскостей уровня был применен для решения задачи совершенствования структуры парка металлорежущих станков (МРС) завода "Славтяжмаш", предложенной НИИ ПТмаш (г.Краматорск). Рассматривается следующая задача. Учитывая ограниченность ресурсов, разработать план обновления парка МРС, обеспечивающий выполнение производственной программы с максимальным омоложением (снижением среднего возраста) парка. Математическая модель задачи разработана совместно с экономистом Большаковой Н.Ю. /5/.
Парк МРС состоит из I технологических групп станков. Каждая из групп содержит некоторую совокупность металлорежущих станков - W{ которая включает jfl\ моделей взаимозаменяемых станков. Известно базовое количество станков каждой модели CLca (tyl; /С—і, /It . ) Число станков, относящихся к совокупности Wi , равняется Z1 &ік По каждой модели станков из совокупности Wi известны следующие данные: &U " производственная площадь, занимаемая одним станком і -й группы Ц -й модели ( i-lyl y К.— і, Ґіі ), иг; J" X режимный фонд времени работы одного станка і -й группы /С -й модели ( І-І,І К,— і7 ПІ ), станко-ч.; Л-ік " средний возраст станков /С -й модели Ь -й грушш ( i-dyli = У, ПІ ), лет.
Каждый станок {, -й группы может быть заменен любым станком из совокупности Vi , включающей tUi моделей взаимозаменяемых станков. Среди станков из совокупности Wi и 2/; могут быть одинаковые модели разного года выпуска. По каждой модели станков совокупности lli известны следующие данные:
Постановка задачи и анализ применимости метода вектора спада для ее решения
Для приближенного решения задач ЦЛП с матрицей ограничений произвольного вида могут быть применены известные методы вектора спада и направляющих окрестностей, предложенные в /50/. Эффективность использования этих методов (точность получаемых решений, быстродействие, универсальность, надежность, простота реализации) для решения задач с ограничениями-неравенствами не вызывает сомнений. Подтверждением этому служит глубокий обзор результатов вычислительных экспериментов по решению большого числа тестовых и практических задач различной размерности с использованием указанных методов, приведенный в / 50 / и в последующих работах /37, 49 /. Наличие ограничений-равенств усложняет задачу. Теоретически методы вектора спада и направляющих окрестностей для решения задач ЦЛП рассчитаны на линейные ограничения любого вида. Однако при наличии даже одного ограничения-равенства могут встретиться существенные затруднения. Рассмотрим их на примере задачи ЦЛП общего вида:
Задача перспективного развития действующих шахт
Угольная промышленность, как объект планирования, имеет ряд характерных особенностей, связанных в первую очередь с ее высокой народнохозяйственной значимостью и огромной масштабностью производства, длительностью сроков отдачи, что предопределяет актуальность перспективного планирования в угольной промышленности. Для обеспечения высокого уровня планирования, нацеленного на повышение эффективности производства, качества работы, необходимо сочетание отраслевого и территориального подходов, комплексное решение перспективных и текущих проблем. Основная цель перспективного плана заключается в разработке оптимальной схемы развития отрасли, структуры добычи угля и размещения фонда угольных предприятий, которые бы в перспективе наиболее полно удовлетворяли потребностям народного хозяйства в углях с наилучшими показателями, по их качеству, производительности труда в отрасли и себестоимости продукции. Один из возможных подходов в решении этой задачи - дискретный подход, заключающийся в составлении нескольких вариантов развития каждого предприятия, а также вариантов добычи и переработки угля в определенном районе /47/. На основании этих вариантов, для которых определены соответствующие технико-экономические показатели, и экономико-математических моделей могут быть выполнены оптимизационные расчеты по выботу вариантов развития угольных предприятий по бассейнам и по отраслям.
В данной работе рассматривается одна из задач перспективного развития действующих шахт, предложенная институтом Центргипро-шахт (г.Москва) и сформулированная в /47/.
Рассматривается группа шахт, которые либо относятся к одному производственному объединению, либо являются группой шахт, добывающих единую по потребности марку угля. Пусть число этих шахт L . Каждая шахта имеет несколько возможных вариантов развития, пусть для t ой шахты имеется tie. вариантов {=1,1, ). В дальнейшем будем использовать следующие обозначения.
Xpf - интенсивность использования в плане L -го варианта развития -ой шахты; СІ - добыча р -ого сорта угля t -ой шахты по 1 -ому варианту развития в рубежный год Г (например с = 1980, 1985, 1990); 2L - потребность в угле р -ого сорта в год t (по данной группе шахт); А-; - потребность . -ой шахты в капиталовложениях в і -ый период, если -ая шахта развивается по Р -ому варианту; CL- - оценка Р -ого варианта развития -й шахты; Д.. - потребность в СМР в L -ый период, если -ая шах
