Содержание к диссертации
Введение
1. Постановка задачи исследования и анализ некото рых методов ее решения 15
1.1. Характерные признаки и неформальная постановка задач размещения геометрических объектов 15
1.2. Формальная постановка математической модели основ ной задачи исследования 27
1.4. Анализ существующих методов решения основной задачи 31
1.4.1. Метод последовательного одиночного размещения -основной метод локальной оптимизации 32
1.4.2. Методы оптимизации в пространстве перестановок. 34
ВЫВОДЫ 38
2. Построение условий взаимных непересечений многоугольников с использованием структур линейных неравенств 39
2.1. Структуры неравенств, операции над ними и эквивалентные преобразования 40
2.2. Соответствие между структурами линейных неравенств и логическими формулами 48
2.3. Метод исключения неизвестных при решении структур линейных неравенств 55
2.4. Построение условий взаимных непересечений с использованием метода исключения неизвестных 64
Выводы 77
3. Математическая модель задачи оптимального размещения ^-многоугольников в полубесконеч ной полосе 78
3.1. Построение области допустимых решений и постановка задачи 78
3.2. Особенности формирования области допустимых решений 88
3.3. Свойства дерева решений задачи 92
Выводы 95
4. Точные методы решения задачи размещения у -многоугольников в полосе 97
4.1. Решение задачи оптимального размещения у-много угольников 97
4.1.1. Применение метода исключения неизвестных 98
4.1.2. Поиск оптимального решения методом ветвей и границ 100
4.2. Использование метода ветвей и границ для оптимального размещения прямоугольников 104
4.3. Поиск локальных экстремумов задачи с использованием методов линейного программирования 123
Выводы 133
Заключение 135
Литература
- Метод последовательного одиночного размещения -основной метод локальной оптимизации
- Соответствие между структурами линейных неравенств и логическими формулами
- Особенности формирования области допустимых решений
- Поиск оптимального решения методом ветвей и границ
Введение к работе
Одной из важнейших хозяйственных и политических задач развития страны в одиннадцатой пятилетке является всемерное повышение эффективности производства. На ХХУІ съезде КПСС были намечены основные пути интенсивного развития народного хозяйства. "Решению задачи интенсификации экономики, обеспечению более высоких результатов производства при меньших затратах и ресурсах должно быть подчинено все - ускорение научно-технического прогресса, совершенствование структуры общественного производства, улучшения планирования и управления" [i ] . Одним из путей ускорения научно-технического прогресса в одиннадцатой пятилетке съезд назвал "расширение автоматизации проектно-конструкторских и научно-исследовательских работ с применением электронно-вычислительной техники" [ij. При этом, важнейшим путем повышения эффективности производства съезд назвал всемерную экономию всех видов ресурсов. Конкретные меры, направленные на коренное улучшение работы по экономии и рациональному использованию сырья, топливно энергетических и других материальных ресурсов во всех звеньях народного хозяйства, были предложены в постановлении ЦК КПСС и Совета Министров СССР от 4 июля 1981 года. Вопрос о рациональном использовании материальных и трудовых ресурсов особенно остро стоял на ноябрьском Пленуме ЦК КПСС 1982 года. Выступая с докладом на ноябрьском 1982 года Пленуме ЦК КПСС Генеральный секретарь ЦК КПСС Ю.В.Андропов назвал рациональное использование материальных и трудовых ресурсов "крупным резервом народного хозяйства". "Ныне экономия, рачительное отношение к . народному добру - это вопрос реальности наших планов" - отметил он в своем докладе.
В крупных научных центрах нашей страны под руководством Л.В.Канторовича, А.А.Дородницына, В.С.Михалевича, а также других известных советских ученых рассматриваются различные аспекты повышения эффективности использования материальных ресурсов. Проблема эта неисчерпаема и ее задачи являются актуальными не только на ближайшую перспективу, но и в обозримом будущем.
Одним из важных классов задач, направленных на снижение расходов сырья, материалов и других видов ресурсов, является класс задач геометрического проектирования [2J. Задачи эти заключаются в поиске оптимального размещения некоторых геометрических объектов в заданных областях при наличии различных ограничений и некоторых критериев качества размещения. К этому классу относятся задачи оптимального раскроя материалов на фигурные, в частности прямоугольные, заготовки, задачи компоновки схем генпланов промышленных предприятий, задачи трассировки, задачи покрытия и многие другие. К задаче прямоугольного раскроя сводятся некоторые задачи теории расписаний и объемно-календарного планирования. Таким образом, в этих задачах под материалом, который экономится, может пониматься листовой металл, рулон ткани в легкой промышленности, земельные участки, трудовые ресурсы, время, электроэнергия, а значит и топливные ресурсы, и т.д.
Возможность сведения большого числа важных народнохозяйственных задач; связанных с оптимальным распределением ресурсов, к классу задач геометрического проектирования вызвала необходимость всестороннего изучения задач этого класса и разработки эффективных методов их решения.
Наиболее простыми, с точки зрения формализации, являются те задачи, в которых областью размещения является фиксированный
набор позиций и при этом можно не учитывать геометрическую форму и размеры размещаемых объектов. Это, к примеру, задачи компоновки радиоэлектронной аппаратуры, когда задан набор приборов (модулей), между которыми в той или иной форме заданы связи, и необходимо так их разместить на допустимом поле позиций, чтобы оптимизировать выбранный критерий качества. По математической постановке эти задачи относятся к дискретным оптимизационным задачам типа квадратичной задачи о назначениях. Методы их решения как для общих, так и для специальных задач изучены достаточно широко (_3—б J . Если же математическая постановка этих задач содержит еще и геометрические ограничения, например на взаимное положение размещаемых объектов с учетом их геометрии, то задача оптимизации размещения существенно усложняется. Здесь возникают сложности различного характера, начиная с формализации задачи и заканчивая построением специальных методов решения, которые так или иначе учитывают необходимость переработки значительных объемов геометрической информации.
Одной из первых работ по размещению объектов с учетом их геометрической формы и размеров является книга Л.В.Канторовича и В.А.Залгаллера "Расчет рационального раскроя промышленных материалов" [7] , в которой для построения оптимальных планов раскроя линейных материалов и прямоугольных листов на прямоугольные заготовки был предложен метод разрешающих множителей (индексов). Расбмотренные в этой работе методы, а также научные результаты, опубликованные в более ранних работах Л.В.Канторовича [8, 9J, явились основой для разработки широко известных в настоящее время методов линейного и динаїлического программирования [ІО-І2]. Дальнейшее свое развитие методы решения задач прямоугольного раскроя получили в работах В.А.Залгаллера I13-16 , а для случая
_ 7 -
сквозных рядов (задача гильотинного раскроя) - в работах Э.А.Му-хачевой[г7~19].
Задачи размещения объектов сложной геометрической формы в зависимости от математической постановки и применяемых методов, в свою очередь, могут быть разбиты на классы регулярного и нерегулярного размещения. К первому классу относятся задачи плотней-шего заполнения плоскости одинаковыми фигурами. Они рассматриваются в дискретной и комбинаторной геометрии. При этом основные результаты получены только для выпуклых фигур и носят характер оценок. Схемы расположения этих фигур , в силу их конгруэнтности, являются регулярными (решетчатыми). Постановки и решения некоторых задач, а также ряд нерешенных проблем комбинаторной геометрии приводятся в работах [20-21] . Особый интерес в этом плане представляет исследование так называемых "замощающих фигур", способных полностью покрывать плоскость без взаимных налеганий. Исследование этих фигур связано с кристаллографическими группами [25,2б].
Выявленные свойства плотных укладок фигурных заготовок позволили успешно решать более сложные задачи, когда область размещения имеет фиксированную форму, а размеры этой области являются оптимизируемыми переменными. Так в работе j_27J была решена задача о заключении фигуры или группы конгруэнтных фигур в прямоугольник наименьшей площади.
В силу большой практической значимости задач регулярного раскроя, методы их решения постоянно совершенствуются. Так в работах [28-32J приведены некоторые интересные результаты в этом направлении.
Наибольшую сложность,как с точки зрения формализации, так и решения,представляют задачи нерегулярного размещения геометричес-
-8П
ких объектов в заданных областях. Дело в том, что область размещения и размещаемые объекты могут иметь достаточно сложную геометрическую форму. Поэтому геометрические ограничения, определяющие условия размещения объектов в области, а также условия взаимных размещений объектов между собой, могут быть достаточно сложными и построение их является серьезной математической задачей.
Методы решения задач нерегулярного размещения развиваются по двум направлениям. Первое из них основано на использовании специфики той или иной задачи и может быть условно названо разработкой упрощенных алгоритмов нерегулярного размещения геометрических объектов. Здесь используются либо технологические особенности оборудования раскроя, либо специфические особенности размещаемых объектов, например, возможность аппроксимации их более простыми объектами (прямоугольниками), приводящая к упрощению задачи, либо иные свойства. Среди работ в этом направлении следует выделить работы ІЗЗ-35І. Второе направление состояло в создании формального математического аппарата и универсальных, в определенном смысле, методов для решения задач нерегулярного размещения. Фундаментом исследований в этом направлении стала разработанная В.Л.Рвачевым теория -функций j_36,37J, которая дала возможность аналитически описывать геометрические объекты сложной формы. Это позволило использовать математический аппарат непрерывного анализа для исследования взаимного положения геометрических объектов, а также для построения ограничений на взаимное положение. В связи с этим появился целый ряд работ [28, 38-40J, в которых задача размещения геометрических объектов ставилась с точки зрения новой теории.
Широта области практического приложения задач размещения
обусловила возникновение большого числа различных подходов к их' решению. Анализ значительного числа таких работ содержится в обзоре, который приведен в [4l]. Следует отметить, что для задач с достаточно большим числом размещаемых объектов применяемые методы в абсолютном большинстве являются приближенными. Это объясняется не только увеличением размерности задачи с ростом числа объектов, но и гораздо более быстрым увеличением количества геометрических ограничений, которые достаточно сложны в построении и описывают, вообще говоря, невыпуклые неограниченные множества. Таким образом, задача размещения геометрических объектов является задачей математического программирования с невыпуклой областью допустимых решений. Конструктивные методы решения общей задачи математического программирования достаточно большой размерности еще не разработаны. Поэтому естественншл является стремление разработать специальные методы, учитывающие специфические свойства решаемой задачи.
Приближенные методы решения задач размещения геометрических объектов в обозримом будущем не утратят своей актуальности, в особенности для задач с большим числом размещаемых объектов. Поэтому очевидна необходимость совершенствования имеющихся приближенных методов, а также разработки новых методов с оценками близости получаемого решения к глобальному или локальным экстремумам задачи. Кроме этого, принципиально важным является создание методов точного решения для тех задач размещения, размерность которых позволяет получить такое решение.
Диссертационная работа является продолжением исследований, проводимых в Институте проблем машиностроения АН УССР под руководством профессора Ю.Г.Стояна и посвящена разработке точных и приближенных методов решения задачи размещения геометрических
- 10 -
' объектов, исследованию возможностей и сферы практического приме
нения этих методов», . - --- '-'..
Диссертационная работа выполнялась б период с 1976 г. по 1980 г. в Харьковском институте радиоэлектроники в соответствии с планом обучения в аспирантуре и с 1980 по 1983 в отделе математического моделирования и оптимального проектирования Института проблем машиностроения АН УССР (КПМаш АН УССР) в соответствии с-планом научно-исследовательских работ по:
госбюдаетной теме "Разработка математических методов размещения tp-объектов и источников физико-механических полей в машиностроении", выполняемой по постановлению Президиума АН УССР № 604 от 25.03.80 (№ ГР 0І8І70І3807);
хоздоговорной теме "Разработка методов и алгоритмов решения компоновочных задач при проектировании промышленных зданий" от 01.04.81 (№ ГР 0І8290І2355, ин. $ отчета во ВНТЩ 0283. 0036806, 1983 г.);
хоздоговорной теме "Разработка алгоритма и программы рационального размещения набора прямоугольных объектов на листах с учетом технологических ограничений" от 03.01.83
(* ГР 01.83.0028445).
- Новизна научных результатов диссертационной работы состоит в следующем:
введено понятие структур линейных неравенств, позволяющее, во-первых, описывать невыпуклые многогранные множества, во-втсн-рых,- пересечение и объединение конечного числа таких множеств и, в-третьих, позволяющее строить аналитически ортогональные проекции любого такого множества на подпространства меньшей размерности;
на базе введенного понятия структур линейных нера-
- II -
венств предложен аналитический метод построения условий взаимных непересечений геометрических объектов, имеющий не только практическое значение, но и являющийся инструментом для изучения основных свойств этих условий;
- предложена математическая модель некоторых задач оптимального размещения геометрических объектов в виде задачи оптимизации линейного функционала на некотором невыпуклом многогранном множестве, заданном структурой линейных неравенств, что создало предпосылки для построения различных методов точного решения этих задач;
предложен ряд методов точного решения поставленной задачи, исследованы возможности этих методов в зависимости от размерности задачи;
в тех случаях, когда отыскание глобального экстремума задачи не представляется возможным, предложен метод приближенного решения, состоящий в поиске локальных экстремумов и их ограниченном переборе.
Методы и алгоритмы, предложенные в диссертационной работе, реализованы на подмножестве языка Фортран для ЭВМ БЭСМ-6 и ЕС ЭВМ и предназначены для автоматизации процесса построения планов раскроя материалов в различных отраслях машиностроения, легкой промышленности, а также для решения задач оптимального распределения ресурсов, которые могут быть сведены к задачам размещения геометрических объектов. Годовой экономический эффект от внедрения результатов работы в производство составляет 51 тыс. рублей.
Основные результаты работы докладывались автором и обсуждались на I Всесоюзной конференции "Автоматизация поискового конструирования" (Йошкар-Ола, 1978); на III Республиканской конференции "Вычислительная математика в современном научно-техническом
прогрессе" (Канев, 1982) ; на Всесоюзном научно-практическом семинаре "Прикладные аспекты управления сложными системами" (Кемерово, 1983) ; на Р> Всесоюзной конференции "Автоматизация поискового конструирования и подготовка инженерных кадров" (Иваново, 1983) ; на постоянно действующих семинарах "Методы поисковой оптимизации и размещения геометрических объектов" (Харьков, 1979-1981), "Прикладные методы математики и кибернетики" (Харьков, 1983), "Математические методы геометрического проектирования" (Харьков, I98I-I982) при Научном совете по проблеме "Кибернетика" АН УССР.
Материалы диссертации являются частью работы Смелякова СВ., Яковлева СВ., Винарского В.Я., Магаса С.Л., Іуранова Й.Н. "Разработка и внедрение в народное хозяйство моделей, методов и алгоритмов решения оптимизационных задач геометрического проектирования", отмеченной Премией ЦК ЛКСМ Украины и Украинского республиканского совета НТО молодым ученым, специалистам и производственникам - членам НТО - за лучшие разработки в области науки и техники 1983 года.
Основные результаты диссертации опубликованы в работах [46, 75, 76, 77, 80, 85, 86, 89, 91, 92].
Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложения.
Первая глава - "Постановка задачи исследования и анализ некоторых методов ее решения" - посвящена построению формальной математической модели задачи оптимального размещения геометрических объектов, анализу особенностей этой задачи и существующих методов ее решения. Исследование характерных особенностей поставленной задачи привело к необходимости выделения класса геометрических объектов, называемых у-объектами и являющихся ма-
- ІЗ -
тематическим аналогом реальных объектов различной физической природы. Задача оптимального размещения уз-объектов поставлена в виде общей задачи математического программирования. Исследованы свойства этой задачи, показана ее многоэкстремальность. Проанализированы существующие методы ее решения, показан их приближенный характер.
Вторая глава - "Построение условий взаимных непересечений у? -многоугольников с использованием структур линейных неравенств" - посвящена разработке математического аппарата структур линейных неравенств и использованию его для аналитического построения геометрических ограничений на взаимное положение у> -объектов (условий взаимных непересечений). Исследованы конструктивные свойства структур линейных неравенств в плане описания невыпуклых многогранных множеств, множеств, лежащих в пересечении и объединении таких множеств, а также в плане аналитического построения ортогональных проекций невыпуклых многогранных множеств на подпространства меньшей размерности.
Третья глава - "Математическая модель задачи оптимального размещения w -многоугольников в полубесконечной полосе" - посвящена постановке и исследованию особенностей задачи оптимального размещения конечного числа ориентированных у?-многоугольников в полубесконечной полосе. Задача ставится в форме минимизации линейной функции цели на некотором невыпуклом многогранном множестве, заданном структурой линейных неравенств. Исследованы свойства этого множества. Показана возможность выделения из него выпуклых многогранных множеств и предложена схема усеченного перебора этих множеств.
В- четвертой главе - "Точные методы решения задачи размещения у -многоугольников в полосе" - предложены методы, которые
позволяют находить глобальный экстремум в задачах размещения конечного числа <р -многоугольников.
Основная идея предлагаемых методов состоит в построении локальных экстремумов задачи и организации усеченного перебора этих экстремумов. Если количество локальных экстремумов задачи столь велико, что даже усеченный их перебор невозможен, то предлагаемые методы позволяют получить приближенное решение, являющееся локальным экстремумом задачи с рекордным значением длины занятой размещенными (^-многоугольниками части полубесконечной полосы.
Список литературы включает 92 наименования.
Приложение содержит документы, подтверждающие внедрение результатов работы в производство.
Метод последовательного одиночного размещения -основной метод локальной оптимизации
Основным из применяемых методов локальной оптимизации является метод последовательного одиночного размещения, описанный впервые математически в [62J и получивший свое развитие в работах [бО,63,64]. В основе этого метода лежит естественный способ размещения всех геометрических объектов, устанавливая их по одному в области размепіеиия, с учетом условий взаимных непересечений с каждюл ранее установленным объектом. При этом параметры размещения каждого устанавливаемого объекта выбираются так, чтобы оптимизировать некоторую функцию цели 36 , адекватную функции цели основной задачи.
Таким образом, если с/? -многоугольники Ь JZJ ..., Ь _у установлены и имеют параметры размещения Л , Л ,..., Л , то при размещении -многоугольника S/ решается задача вида: найти cxtr X...! - . 1) (I.I3) в области, которая задана системой неравенств
Тогда метод последовательного одиночного размещения состоит в последовательном решении 1Ъ задач вида (І.ІЗ), (I.I4).
Из математического описания метода последовательного одиночного размещения видно, что он является одной из реализаций метода Гаусса-Зайделя (методн частичного улучшения по группам переменных [б5] ). Отличие состоит в том, что для получения некоторого решения методом последовательного одиночного размещения начальная точка из области решений (г не нужна. Достаточно знать лишь последовательность перебора групп переменных. Кроме того, в силу (І.ІЗ), (I.I4), метод ориентирован на получение решения за один цикл "просмотра" последовательности групп переменных. Отсюда, в частности, следует основное достоинство данного метода, состоящее в близкой к линейной зависимости времени решения от количества Празмещаемых f-многоугольников. Так для достаточно больших гь этот метод является пока единственным, позволяющим решить задачу. Однако метод носит приближенный характер и является детерминированным, то есть каждой последовательности перебора групп переменных соответствует одно решение. Эти свойства определяют следующие недостатки метода:
1. При последовательном размещении if -многоугольников происходит фактически последовательное усечение области допустимых решений задачи и когда эта область ограничена, не исключено, что метод вовсе не даст решения, хотя оно и существует.
2. Из детерминированности метода следует, что с его помощью можно получить не более гь! различных решений. А поскольку количество локальных экстремумов основной задачи может значительно превышать значение гь! , то использование его, вообще говоря, не гарантирует отыскания глобального экстремума даже при решении гь! задач последовательного размещения.
3. Метод не гарантирует отыскания локального экстремума основной задачи, а значит в окрестности полученного решения может существовать лучшее решение.
Из специфики метода последовательного одиночного размещения понятно, что успех его реализации существенно зависит от выбора перестановки из 1Ъ символов, отвечающей выбору последовательности групп переменных. Поскольку перебор всех гъ! перестановок для достаточно больших гь как правило невозможен, возникает проблема организации целенаправленного перебора, дающего некоторые вероятностные качественные оценки полученного рекордного решения. Некоторые из методов такого целенаправленного перебора рассмотрены ниже.
Методы оптимизации в пространстве перестановок
Для достаточно больших гь величина гь! является настолько большой, что можно говорить о пространстве перестановок. А поскольку это пространство дискретное, то вполне оправдан выбор случайных методов для оптимизации в этом пространстве. Рассмотрим наиболее характерные из них.
I. Метод сужающихся окрестностей [63j , который представляет собой направленный случайный поиск. На пространстве перестановок П выбирается метрика Р (цепная, транспозиционная, лексикографическая, инверсная, алфавитная или другие) и для любой точки ро П вводится понятие окрестности радиуса Q , содержащей некоторые точки р из пространства П , для которых
Соответствие между структурами линейных неравенств и логическими формулами
Под логической формулой ЦА1г r zf-1 "пъ/ как извест но j_79 J , понимается строка символов, среди которых присутству ют, ВО-ПерВЫХ, СИМВОЛЫ МНОЖеСТВ Л/ , /-=-/,2,..,,/77- f БО вторых, символы операций пересечения, объединения и дополнения (вычитания) и, в-третьих, открытые и закрытые скобки, определяющие последовательность применения операций. Например, выражение является логической формулой.
Из определения структур неравенств видно, что они существенно отличаются от логических формул. Это отличие прежде всего в том, что для их задания не надо знать последовательности применения операций, необходимо лишь задать вид операции для каждой пары множеств (пары соответствующим им неравенств). Таким образом структуры неравенств не могут быть отнесены к классу логических формул. Однако, как будет показано ниже, между структураїли неравенств и логическими формулами можно установить взаимнооднозначное соответствие. Установление такого соответствия позволяет утверждать, что структуры неравенств обладают свойством полноты при описании множеств с конечным числом компонент, поскольку таким свойством обладают логические формулы.
Дадим необходимые определения. Определение 2.6. Структура неравенств называется подструк турой структуры , если она получена из послед ней выделением неравенств с сохранением операций между ними. Определение 2.7. Блоком структуры $ (Ffo), А, пъ) называется такая ее подструктура 5(/( ), & , т ) , что все неравенства из f (х,) связаны с любым из оставшихся в / "(эс) неравенств операцией одного типа: либо операцией конъюнкции, либо операцией дизъюнкции.
Свойство 2.3 позволяет представить, если это возможно,структуру неравенств объединением или пересечением входящих в нее подструктур. Предположим, что каждая из этих подструктур состоит из нескольких неравенств и может быть представлена объединением или пересечением входящих в нее подструктур. Перепишем их согласно такому представлению. Продолжая последовательно эту процедуру разбиения каждой из подструктур на блоки придем к некоторому выражению исходной структуры в виде последовательности объединений и пересечений ее подструктур, обусловленной наличием скобок.
Определение 2.8. Структура неравенств называется блочной, если для нее можно найти такую последовательность делений на блоки, затем блоков на блоки и т.д., при которой будут получены только подструктуры, состоящие из одного неравенства.
Например, не трудно убедиться, что структура (2.8) является блочной. Действительно, если обозначить через S (FL(OC), А, І) подструктуру, порожденную неравенством j-. (1=-1 ,..., 6) , то структура (2.8) может быть преобразована в процессе деления к виду Свойство 2.4. Объединение блочных структур и их пересечение являются блочными структурами. Свойство 2.5. Для всякой структуры SfFfoC) /]j гтъ) можно найти по крайней мере одну эквивалентную ей блочную структуру. Свойство 2.5 следует из теоремы 2.2. Действительно, поскольку любую структуру можно представить объединением систем, и каждая система является блочной структурой, то структура в правой части равенства (2.6) является блочной, т.е. одна из эквивалентных блочных структур найдена. Свойство 2.6. Если структура S {( (оо)t J\1-/) , где F(cc)-\ f (ос) 0) определяет в пространстве R замкнутую область X) , то область /Q \J) может быть задана структу рой 5(Г (ОСУ)7 &\ і) , где F (x,)={f(vo) о) , а область R \LntD может быть задана структурой S(FVfX ) /Ґ,і) Свойство 2.7. Если некоторая область,) задана логичес кой формулой L{AffAz,..., г гп) и каВДое из множеств All может быть описано неравенством, то существует блочная структу ра, задающая эту область.
Приведем алгоритм построения одной из таких блочных структур. Прежде всего, воспользовавшись правилами де Моргана [79 J преобразуем логическую формулу L(Ai) /\г,..., Д / к формуле L (Ai,f\z -.. ггь » У которой под каждым знаком дополнения может находиться только одно из множеств r\i, =4,2,,..., Гги Формула L ( А у, . - - 7 Ат) определяет последовательность пересечений и объединений множеств, каждое из которых, в силу свойства 2,6, может быть описано некоторым неравенством. Подставим в формулу L ( Afr Az,..., г)/TV/ вместо этих множеств определяю-щие их структуры, состоящие из одного неравенства. После пересечения и объединения этих структур, согласно имеющейся последовательности применения операций, получим искомую блочную структуру неравенств.
Например, воспользовавшись этим алгоритмом можно перейти от логической формулы (2.7) к структуре (2.12), а от нее к блочной структуре (2.8).
Таким образом, свойство 2.7 и свойство полноты для логических формул позволяют утверждать, чта любой логической формуле с конечным числом членов можно поставить во взаимно-однозначное соответствие определенную блочную структуру неравенств. А значит, на основании свойства 2.5 установлено соответствие между любой логической формулой и структураїли неравенств из некоторого класса эквивалентности структур.
Особенности формирования области допустимых решений
Процедуру построения множества . Lr , с другой стороны, можно представить себе как процедуру последовательного усечения некоторого многогранного множества другими множествами, которые являются невыпуклыми и могут быть представлены объединениями выпуклых множеств. В качестве начального множества здесь выбирается выпук-лок множество, которое задано структурой а пересекаются с ним последовательно множества, заданные структу рами , (1=1,2,,.., CJ . Иллюстрация этой процедуры приведена на рис.14. Последовательность усечений здесь схематично представлена повышением густоты заштриховки мно жества и утолщением линий, обозначающих границу множества, лежа щего в пересечении.
Такой подход к формированию Q- позволяет представить в виде дерева процедуру формирования множеств Ьг , д = /, 2,..., р из соотношения (3.13). Или, что одно и то же, - позволяет представить в виде дерева процедуру формирования систем неравенств в структуре (3.12). Для этого введем переменные величины к, , КОТО-рые определяют номер системы, выделенной из структур
Обозначим через п величину С , т.е./? = . Тогда из изложенного выше видно, что любая из систем неравенств в структуре (3.12) образована из системы П S((Pl(X\ Ъ) Д, ч) и систем, номера которых определяются фиксированными значениями переменных У ЛУ,... ,Y Пусть А - корень дерева, вершины первого уровня, обозначим их п I у J , определяют значения величин
У 6 р,2,.,,, pi j . Вершины следующего уровня определяют после довательности фиксированных значений из переменных fa , У , где ур,2,... , pzj . И так далее. Вершинам Q v0 уровня дерева решений соответствуют все возможные последовательности из фиксированных значений переменных У , Y , -- У Обозначим через А1у,,У2,..., ] вершину fr-vo уровня ( 1,2,...,/])
Тогда, если корню А дерева поставить в соответствие систему Г) 5(Фі(Хі }тЄ\/\І,4) , вершине А [у, J - систему, полученную добавлением к последней системы с номером у , а вершине AtY , Y ] -" систему, полученную добавлением к системе, соответствующей вершине АіуУ ...,У J .системы с номером у -, то-вершине AiY,Y ..., У,] » являющейся концевой, будет соответствовать одна из систем структуры (3.12).
Построенное дерево- называется деревом решений. На рис.15 изображен фрагмент дерева решений. Таким образом, дерево решений позволяет получить все системы в структуре (3.12) и, тем самым,, представить множество Q. в виде (3.13). Отсюда следует, что задача (3.5) может быть преобразована к следующей. Найти где 2&г=Пъ1гьЪ. (3.15) Т.е., поскольку Gv :есть выпуклое многогранное множество, задача сводится к решению р задач линейного программирования(3.15).
Как было показано в предыдущем параграфе,задача (3.5) сводится к решению р задач линейного программирования. Однако, из равенства (ЗЛІ) видно, что при достаточно больших значениях величины ґь значение р может быть настолько большим, что о решении всех р задач не может быть и речи, а значит и получение оптимального решения задачи при таком подходе невозможно..Поэтому необходимо выявить некоторые свойства области решений (т , которые были бы конструктивны в плане уменьшения количества перебираемых задач линейного программирования.. Для этого исследуем свойства построенного в параграфе 3.2 дерева решений.
Обозначим через 1т(fa , 1,,.,, }fL) многогранное множест во, заданное системой, соответствующей вершине A LY4,Y±,...,Кр J (Будем говорить, что множество (j-j У Y, ..., ) соответ ствует вершине A[yitY2t...ty ] ). Предположим нал известен вариант размещения всех гь у- многоугольников в полосе и Ъ - длина занятой части этой полосы.Тогда из неравенства (3.20) видно, что если выполняется неравенство то при любых дальнейших ветвлениях из вершины Al ft...tYq J будут получены лишь такие выпуклые многогранные множества fo...., , ,...,3 ) минимальное значение переменной на которых не меньше значения Ъ . Т.е.,другими словами, не может быть получен вариант решения лучший (с меньшей длиной занятой части полосы), чем известный вариант с длиной .
Таким образом, перечисленные особенности выделения выпуклых многогранных множеств из множества Q- позволяют на этапе промежуточного анализа отбросить часть бесперспективных многогранных множеств, т.е. организовать усеченный перебор вершин дерева решений. Это говорит о возможности применения метода ветвей и границ 84J к решению задачи (3.13), а значит и задачи (3.5).
Необходимо обратить внимание на еще. одну особенность множества Q. . Так из способа построения систем в структуре (3.12) видно, что среди них существует множество пар систем, которые отличаются друг от друга небольшим количеством неравенств, а значит существуют пары систем с непустым пересечением заданных ими множеств, т.е.
Поиск оптимального решения методом ветвей и границ
Основные идеи применения метода ветвей и границ для решения задачи размещения Ч -многоугольников в полосе, изложенные в работах [_85,8б] ., опираются на возможность построения и конструктивные свойства дерева решений. Схема построения дерева решений, .а также его свойства были достаточно подробно изложены в предыдущей главе. Поэ.тому здесь мы рассмотрим конкретную вычислительную схему решения задачи методом ветвей и границ.
Опишем прежде всего способ получения оценок, т.е. границ интервала, в котором будет вестись поиск оптимального значения Ж, длины Ъ занятой (/?-многоугольниками части полосы з с Обозначим эти оценки и . Значение оценки т пьи естественно получить из выражения 101 V где 5L - площадь p многоугольника SL {L-i,Z,.., , ґь) , а в качестве величины гтъа х- БЫ( Рать ДЛИНУ занятой части полосы О для некоторого известного варианта размещения всех многоугольников в полосе. предположим, что І тлих, топ,» тогда, поскольку в процессе решения мы будем искать варианты размещения с длиной занятой части полосы меньшей величины ггимс » то интервал изменения величины 35- имеет вид: /пии тало Способ построения дерева решений описан в параграфе 3.2. Для организации усеченного перебора вершин этого дерева восполь зуемся выделенными в параграфе 3.3 признаками того, что вершина Д[к К # # /Г Vty ) является концевой. Проверка этих призна ков включает проверку непустоты множества &(К7У ,..., У ) проверку включения (3.16), а таюке решение задачи (3.17) с анали зом Принадлежности ВеЛИЧИНЫ 2L Интервалу Пз&яшь, %пъл С-] Выберем следующую систему нумерации структур неравенств, определяющих условия взаимных непересечений L -го и г0 Ф - многоугольников: 1 = 1, ,.,.,/ъ /; f=is+i,L+Z7.„,ns . Тогда множество Щ , ,--, V ) задано системой неравенств, зависящих от перемен ных Х „-#;,&,,,%,.„, 3 ,- ,, . а значит (у(у У ) С R + Таким образом, проверка перечис ленных выше признаков предполагает анализ определенных свойств выпуклых многогранных множеств достаточно большой размерности. Это может существенно увеличить длительность анализа каждой вершины. Поэтому необходимо упростить процедуры проверки этих признаков. Решение последней задачи можно осуществить понижением размерности анализируемого многогранного множества. А именно.
Пусть необходимо проанализировать вершину A [kt...; К} . Отметим, что эта вершина получена из вершины А 1 }... 7 Ja_f J добавлением элемента У (К Є уі, ,..., рд, \) , Т. е., соот ветствующая ей система неравенств получена добавлением к систе ме, соответствующей вершине А іУ, ..., У.,, J системы У , Неравенства системы У зависят от четырех переменных Х ;{/[7 V V а значит анализ вершин Ф-то уровня дерева решений достаточно проводить лишь в пространстве /х изменения пяти следующих переменных: 3. , Ъ . , эо , U-. ,Ъ . Для этого не обходимо исключить из системы неравенств, соответствующей верши не ntjj ... , У.і J Бсе переменные кроме пяти перечис ленных. Полученную при этом систему обозначим т-Ь/ . Затем,до бавляя К СИСТеме Яга, ПООЧЄрЄДНО СИСТеМЫ У,, СУ=Ь , чРсґ будем получать системы неравенств от пяти переменных, соответствующие вершинам OL/ -го уровня дерева решений. Таким образом, если через ) обозначить множество, за-данное системой 4 L , а через 2) (У) множество, заданное системой под номером %а , выделенной из структуры Ъ[/2и(Ки}){ )7Ад ,/тЪсИ , то каждой вершине Ф-го уровня,по лученной из вершины АіУ Ґсу-і соответствует не которое множество D(K) У =/,2,...,Рсу кз пространства R . А значит, перечисленные в параграфе 3.3 признаки концевой вершины можно переписать в следующем виде. Вершина А[у уЛ является концевой, если вы полняется по крайней мере одно-из следующих условий:
Для проверки условий (4.2) и (4.4) можно воспользоваться методами линейного программирования [87,88]. Проверка условия (4.3) не столь проста. Как будет показано ниже она сводится к проверке совместности конечного числа систем линейных неравенств. Пусть множества Dfj J и 1)( ) заданы системами, состоящишиз неравенств /-- .(0 ) 0,1- = ,2,..., 1 и / ={TI (XJ O, =/,2,..., К- ] , соответственно, где 2С--(зОі, %,» »%- v Обозначим через ЯР набор неравенств из г , не входящих в F . Положим ЧЭ [1р. (oo) 0} L-i,Z,..,,rrv) . /г Тогда если через / обозначить систему, состоящую из системы / и неравенства (р (ос) 0 , ІЄ \L-,Z,.,, 7 rru J , то спра ведлива следующая теорема Теорема 4.1. Для выполнения соотношения (4.3) необходимо и достаточно, чтобы все системы неравенств A = /.,..,,/72/ С- j 7 были несовместны. Необходимость. Пусть имеет место включение (4.3). Тогда, если точка X такова, что CCX)(j ) , то OCCJDfj ) Значит эта точка удовлетворяет всем неравенствам и? (оо) ,0 і U-i2,...,hb Но тогда X не удовлетворяет ни одному из нера г венств (f.(x) 0 L =/,,,,, гть а значит системы г І , L = -f,Z,,.., iris несовместны. о Достаточность. Пусть все системы г , L -f,Z,..., гп не совместны. Следовательно, ни одна точка множества -Z) (J J не удовлетворяет ни одному из неравенств у? (эо) О7 L = Y7 Z,..., гтъ-. А поскольку (оси @ » то все точки этого множества удов летворяют неравенствам Ц . (х) 6\, L = -f,Z,,.. ,ПЪ . Следовательно выполняется включение (4.3).
Таким образом, осуществляя проверки условий (4.2), (4.3) и (4.4), при ЭС %т 2уЯУ будет получена вершина А [у ..., А ]» для которой решением задачи (4.4) будет получено значение Ъ„ длины занятой части полосы для нового варианта размещения. При этом %п ггимо Решив задачу линейного программирования (3.17) для этой вершины получим координаты параметров размещения для нового варианта.
Если % л - пгіп, » то процесс решения можно остановить, поскольку оптимальное решение найдено. Если же л %ггшъ , то решение продолжается. При этом величина %тссх принимает значение Ъп
Процесс решения заканчивается после перебора всех вершин. При этом в качестве решения выбирается вариант с последним из полученных значений тсих,
Предложенная вычислительная схема с использованием ветвей и границ позволяет решать задачи оптимального размещения большего числа (р - многоугольников, чем схема с использованием метода исключения. Так для отдельных задач количество размещаемых у?-многоугольников может доходить до 20. Наиболее ощутимый эффект от применения этой ихемы наблюдается при размещениии прямоугольников. Специфические свойства этой задачи рассмотрены в следующем параграфе.
