Методы решения экстремальных задач размещения многоугольных геометрических объектов в полосе тема диссертации и автореферата по ВАК РФ 08.00.13, кандидат физико-математических наук Магас, Сергей Леонидович

• Магас, Сергей Леонидович
• кандидат физико-математических наук
• 1984

Оглавление диссертации кандидат физико-математических наук Магас, Сергей Леонидович

ВВЕДЕНИЕ.

1. ПОСТАНОВКА ЗАДАЧИ ИССЛЕДОВАНИЯ И АНАЛИЗ НЕКОТОРЫХ МЕТОДОВ ЕЕ РЕШЕНИЯ.

1.1. Характерные признаки и неформальная постановка задач размещения геометрических объектов.

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

1.4. Анализ существующих методов решения основной задачи

1.4.1. Метод последовательного одиночного размещения -основной метод локальной оптимизации.

1.4.2. Методы оптимизации в пространстве перестановок. . 34 ВЫВОДЫ.

2. ПОСТРОЕНИЕ УСЛОВИЙ ВЗАИМНЫХ НЕПЕРЕСЕЧЕНИЙ

Y -МНОГОУГОЛЬНИКОВ С ИСПОЛЬЗОВАНИЕМ СТРУКТУР ЛИНЕЙНЫХ НЕРАВЕНСТВ.

2.1. Структуры неравенств, операции над ними и эквивалентные преобразования.

2.2. Соответствие между структурами линейных неравенств и логическими формулами

2.3. Метод исключения неизвестных при решении структур линейных неравенств

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

ВЫВОДЫ.

3. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ЗАДАЧИ ОПТИМАЛЬНОГО РАЗМЕЩЕНИЯ <f -МНОГОУГОЛЬНИКОВ В ПОЛУБЕСКОНЕЧНОЙ ПОЛОСЕ.

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

3.2. Особенности формирования области допустимых решений

3.3. Свойства дерева решений задачи.

ВЫВОДЫ.

4. ТОЧНЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ РАЗМЕЩЕНИЯ у -МНОГОУГОЛЬНИКОВ В ПОЛОСЕ.

4.1. Решение задачи оптимального размещения у-многоугольников.

4.1.1. Применение метода исключения неизвестных.

4.1.2. Поиск оптимального решения методом ветвей и границ

4.2. Использование метода ветвей и границ для оптимального размещения прямоугольников

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

ВЫВОДЫ.

Введение диссертации (часть автореферата) на тему «Методы решения экстремальных задач размещения многоугольных геометрических объектов в полосе»

Одной из важнейших хозяйственных и политических задач развития страны в одиннадцатой пятилетке является всемерное повышение эффективности производства. На ХХУ1 съезде КПСС были намечены основные пути интенсивного развития народного хозяйства. "Решению задачи интенсификации экономики, обеспечению более высоких результатов производства при меньших затратах и ресурсах должно быть подчинено все - ускорение научно-технического прогресса, совершенствование структуры общественного производства, улучшения планирования и управления" [i ] . Одним из путей ускорения научно-технического прогресса в одиннадцатой пятилетке съезд назвал "расширение автоматизации проектно-конструкторских и научно-исследовательских работ с применением электронно-вычислительной техники" [i]. При этом, важнейшим путем повышения эффективности производства съезд назвал всемерную экономию всех видов ресурсов. Конкретные меры, направленные на коренное улучшение работы по экономии и рациональному использованию сырья, топливно энергетических и других материальных ресурсов во всех звеньях народного хозяйства, были предложены в постановлении ЦК КПСС и Совета Министров СССР от 4 июля 1981 года. Вопрос о рациональном использовании материальных и трудовых ресурсов особенно остро стоял на ноябрьском Пленуме ЦК КПСС 1982 года. Выступая с докладом на ноябрьском 1982 года Пленуме ЦК КПСС Генеральный секретарь ЦК КПСС Ю.В.Андропов назвал рациональное использование материальных и трудовых ресурсов "крупным резервом народного хозяйства". "Ныне экономия, рачительное отношение к . народному добру - это вопрос реальности наших планов" - отметил он в своем докладе.

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

Одним из важных классов задач, направленных на снижение расходов сырья, материалов и других видов ресурсов, является класс задач геометрического проектирования [2]. Задачи эти заключаются в поиске оптимального размещения некоторых геометрических объектов в заданных областях при наличии различных ограничений и некоторых критериев качества размещения. К этому классу относятся задачи оптимального раскроя материалов на фигурные, в частности прямоугольные, заготовки, задачи компоновки схем генпланов промышленных предприятий, задачи трассировки, задачи покрытия и многие другие. К задаче прямоугольного раскроя сводятся некоторые задачи теории расписаний и объемно-календарного планирования. Таким образом, в этих задачах под материалом, который экономится, может пониматься листовой металл, рулон ткани в легкой промышленности, земельные участки, трудовые ресурсы, время, электроэнергия, а значит и топливные ресурсы, и т.д.

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

Наиболее простыми, с точки зрения формализации, являются те задачи, в которых областью размещения является фиксированный набор позиций и при этом можно не учитывать геометрическую форму и размеры размещаемых объектов. Это, к примеру, задачи компоновки радиоэлектронной аппаратуры, когда задан набор приборов (модулей), между которыми в той или иной форме заданы связи, и необходимо так их разместить на допустимом поле позиций, чтобы оптимизировать выбранный критерий качества. По математической постановке эти задачи относятся к дискретным оптимизационным задачам типа квадратичной задачи о назначениях. Методы их решения как для общих, так и для специальных задач изучены достаточно широко [з-б] . Если же математическая постановка этих задач содержит еще и геометрические ограничения, например на взаимное положение размещаемых объектов с учетом их геометрии, то задача оптимизации размещения существенно усложняется. Здесь возникают сложности различного характера, начиная с формализации задачи и заканчивая построением специальных методов решения, которые так или иначе учитывают необходимость переработки значительных объемов геометрической информации.

Одной из первых работ по размещению объектов с учетом их геометрической формы и размеров является книга Л.В.Канторовича и В.А.Залгаллера "Расчет рационального раскроя промышленных материалов" [7 J , в которой для построения оптимальных планов раскроя линейных материалов и прямоугольных листов на прямоугольные заготовки был предложен метод разрешающих множителей (индексов). Расбмотренные в этой работе методы, а также научные результаты, опубликованные в более ранних работах Л.В.Канторовича [8, 9], явились основой для разработки широко известных в настоящее время методов линейного и динамического программирования [10-12]. Дальнейшее свое развитие методы решения задач прямоугольного раскроя получили в работах В.А.Залгаллера [13-16 , а для случая сквозных рядов (задача гильотинного раскроя) - в работах Э.А.Му-хачевой [17-19].

Задачи размещения объектов сложной геометрической формы в зависимости от математической постановки и применяемых методов, в свою очередь, могут быть разбиты на классы регулярного и нерегулярного размещения. К первому классу относятся задачи плотней-шего заполнения плоскости одинаковыми фигурами. Они рассматриваются в дискретной и комбинаторной геометрии. При этом основные результаты получены только для выпуклых фигур и носят характер оценок. Схемы расположения этих фигур , в силу их конгруэнтности, являются регулярными (решетчатыми). Постановки и решения некоторых задач, а также ряд нерешенных проблем комбинаторной геометрии приводятся в работах [20-2l] . Особый интерес в этом плане представляет исследование так называемых "замощающих фигур", способных полностью покрывать плоскость без взаимных налеганий. Исследование этих фигур связано с кристаллографическими группами [25,2б].

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

В силу большой практической значимости задач регулярного раскроя, методы их решения постоянно совершенствуются. Так в работах [28-З2] приведены некоторые интересные результаты в этом направлении.

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

Методы решения задач нерегулярного размещения развиваются по двум направлениям. Первое из них основано на использовании специфики той или иной задачи и может быть условно названо разработкой упрощенных алгоритмов нерегулярного размещения геометрических объектов. Здесь используются либо технологические особенности оборудования раскроя, либо специфические особенности размещаемых объектов, например, возможность аппроксимации их более простыми объектами (прямоугольниками), приводящая к упрощению задачи, либо иные свойства. Среди работ в этом направлении следует выделить работы [33-35]. Второе направление состояло в создании формального математического аппарата и универсальных, в определенном смысле, методов для решения задач нерегулярного размещения. Фундаментом исследований в этом направлении стала разработанная В.Л.Рвачевым теория £-функций [36,3V], которая дала возможность аналитически описывать геометрические объекты сложной формы. Это позволило использовать математический аппарат непрерывного анализа для исследования взаимного положения геометрических объектов, а также для построения ограничений на взаимное положение. В связи с этим появился целый ряд работ [28, 38-4о], в которых задача размещения геометрических объектов ставилась с точки зрения новой теории.

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

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

Диссертационная работа является продолжением исследований, проводимых в Институте проблем машиностроения АН УССР под руководством профессора Ю.Г.Стояна и посвящена разработке точных и приближенных методов решения задачи размещения геометрических объектов, исследованию возможностей и сферы практического применения этих методов,, . - . ---- '

Диссертационная работа выполнялась б период с 1976 г. по 1980 г. в Харьковском институте радиоэлектроники в соответствии с планом обучения в аспирантуре и с 1980 по 1983 в отделе математического моделирования и оптимального проектирования Института проблем машиностроения АН УССР (КПМаш АН УССР) в соответствии с-планом научно-исследовательских работ по:

- госбюдаетной теме "Разработка математических методов размещения ^-объектов и источников физико-механических полей в машиностроении", выполняемой по постановлению Президиума АН УССР № 604 от 25.03.80 (№ ГР 0I8I70I3807);

- хоздоговорной теме "Разработка методов и алгоритмов решения компоновочных задач при проектировании промышленных зданий" от 01.04.81 (№ ГР 0I8290I2355, ин. $ отчета во ВНТИЦ 0283. 0036806, 1983 г.);

- хоздоговорной теме "Разработка алгоритма и программы рационального размещения набора прямоугольных объектов на листах с учетом технологических ограничений" от 03.01.83 ГР 01.83.0028445).

- Новизна научных результатов диссертационной работы состоит в следующем:

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

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

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

- предложен ряд методов точного решения поставленной задачи, исследованы возможности этих методов в зависимости от размерности задачи;

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

Методы и алгоритмы, предложенные в диссертационной работе, реализованы на подмножестве языка Фортран для ЭВМ БЭСМ-6 и ЕС ЭВМ и предназначены для автоматизации процесса построения планов раскроя материалов в различных отраслях машиностроения, легкой промышленности, а также для решения задач оптимального распределения ресурсов, которые могут быть сведены к задачам размещения геометрических объектов. Годовой экономический эффект от внедрения результатов работы в производство составляет 51 тыс. рублей.

Основные результаты работы докладывались автором и обсуждались на I Всесоюзной конференции "Автоматизация поискового конструирования" (Йошкар-Ола, 1978); на III Республиканской конференции "Вычислительная математика в современном научно-техническом прогрессе" (Канев, 1982) ; на Всесоюзном научно-практическом семинаре "Прикладные аспекты управления сложными системами" (Кемерово, 1983) ; на pi Всесоюзной конференции "Автоматизация поискового конструирования и подготовка инженерных кадров" (Иваново, 1983) ; на постоянно действующих семинарах "Методы поисковой оптимизации и размещения геометрических объектов" (Харьков, 19791981), "Прикладные методы математики и кибернетики" (Харьков, 1983), "Математические методы геометрического проектирования" (Харьков, I98I-I982) при Научном совете по проблеме "Кибернетика" АН УССР.

Материалы диссертации являются частью работы Смелякова С.В., Яковлева С.В., Винарского В.Я., Магаса C.JI., 1^ранова И.Н. "Разработка и внедрение в народное хозяйство моделей, методов и алгоритмов решения оптимизационных задач геометрического проектирования", отмеченной Премией ЦК JIKCM Украины и Украинского республиканского совета НТО молодил ученым, специалистам и производственникам - членам НТО - за лучшие разработки в области науки и техники 1983 года.

Основные результаты диссертации опубликованы в работах [46, 75, 76, 77, 80, 85, 86, 89, 91, 92].

Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложения.

Заключение диссертации по теме «Математические и инструментальные методы экономики», Магас, Сергей Леонидович

Выводы

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

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

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

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

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

Г/

- 135 -ЗАКЛЮЧЕНИЕ

1. Проведен анализ задач рационального размещения объектов ; различной физической природы, вццёлены их характерные признаки, осуществлена формальная постановка и построена математическая модель общей задачи оптимального размещения ^-объектов.

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

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Магас, Сергей Леонидович, 1984 год

1.Материалы ХХУ1 съезда КПСС. - М.: Политиздат, 1981.

2. Стоян Ю.Г. Основная задача геометрического проектирования: Харьков, IS83. 37 с.(Препринт / Ин-т пробл.машиностроения АН УССР: 181).

3. Михалевич B.C., Шор H.S., Галустова Л.А. и др. Вычислительные методы выбора оптимальных проектных решений. Киев: Наук, демка, 1977. - 178 с,

4. Сергиенко И.В., Лебедева Т.Т., Рощин В.А. Приближенные методы решения дискретных задач оптимизации. Киев: Наук.думка, 1980. - 272 с.

5. Корбут А.А., Финкелыптейн 10ЛЗ. Дискретное программирование. -М.: Наука, 1969. 368 с.

6. Теория и методы автоматизации проектирования вычислительных систем.(Под ред.М.Брейера. М.: Мир, 1977. - 283 с.

7. Канторович Л.В., Залгаллер В.А. Расчет рационального раскроя промышленных материалов. Л.: Лениздат, 1951. - 197 с.

8. Канторович Л.В. Математические методы в организации и планировании производства. Л.: Изд-во ЛГУ, 1939 (воспроизведено в кн."Применение математики в экономических исследованиях".1. М.: Соцэкгиз, 1959) 60 с.

9. Канторович Л.В. Об одном эффективном методе решения некоторых классов экстремальных задач. Докл.АН СССР, 1940, т.23, J5 3, с.212-215.

10. Данциг Д.Б. Линейное программирование, его применение и обобщение. М.: Прогресс, 1966. - 600 с.

11. Беллман Д. Динамическое программирование. М.: Изд-во иностр. лит., I960. - 400 с.

12. Моисеев И.И., Иванилов Ю.П., Столярова Е.М. Методы оптимизации. М.: Наука, 1978. - 352 с.

13. Залгаллер В.А. Применение математических методов в планировании раскроя материалов. В кн.: Математические методы в технико-экономических расчетах: Материалы научного совещания (Москва, апр.I960). - М., 1961, т.У1, с.80-91.

14. Залгаллер В.А. Рациональный раскрой как средство экономии материалов. В кн.: Использование методов оптимизации в текущем планировании и оперативном управлении производством: Материалы Всесоюзной конференции (Москва, октябрь 1979), -М., 1980, с. 44-47.

15. Залгаллер В.А., Круглов А.И. Рулонный принцип раскроя. В кн.: Математическое обеспечение расчетов линейного и прямоугольного раскроя: Материалы Всесоюз.научн.семинара (Уфа, июнь; 1980). - Уфа, 1981, с.70-76.

16. Дремин С.Ю., Залгаллер В.А. О раскрое листа на равные прямоугольные заготовки. Оптимизация 27 (44), Новосибирск; Наука СО, 1981, с.136-143.

17. Мухачева З.А. Рациональный раскрой прямоугольных листов на прямоугольные заготовки. В кн.: Оптимальное планирование,- Сб.научных трудов СО АН СССР, ИМ, вып.6, Новосибирск, 1966, с.43-115.

18. Мухачева Э.А. Методы условной оптимизации в задаче рационального раскроя листового проката. В кн.: Оптимизация.- Сб.научн.трудов СО АН СССР, Ин-т мат-ки, вып. 22(39). -Новосибирск: Наука СО, 1978, с.83-93.

19. Мухачева Э.А. Расчет рациональных раскроев в системе автоматизированного проектирования технологической подготовкой гильотинного раскроя. -Кузнечно-штамповочное производство,1982, JB 7, с.31-37.

20. Тот Ф. Расположения на плоскости, на сфере и в пространстве.- М.: Физматгиз, 1958. 363 с.

21. Xадвигер Г., Дебрункер Г. Комбинаторная геометрия плоскости.- М.: Наука, 1965. 171 с.

22. Болтянский В.Г., Гохберг. И.Ц. Теоремы и задачи комбинаторной геометрии. М.: Наука, 1965. - 108 с.

23. Роджерс К.А. Укладки и покрытия. М.: Мир, 1968. - 134 с.

24. Шклярский Д.О., Ченцов Н.Н., Яглом И.Н. Геометрические оценки и задачи из комбинаторной геометрии. М.: Наука, 1974. -384 с.

25. Федоров Е.С. Начало учения о фигурах. Зап.минералог.о-ва, 2-я сер., 1885, т.21. - 410 с.

26. Федоров Е.С. Симметрия и структура кристаллов. М.: Изд-во АН СССР, 1949. - 631 с.

27. Залгаллер В.А. Об одном необходимом признаке плотнейшего расположения фигур. Успехи мат.наук, 1953, т.8, вып.4, с.153-162.

28. Глушко А.Г., Рвачев В.Л. Об одной задаче оптимального раскроя. Кибернетика, 1967, J5 I, с. 92-95.

29. Белякова Л.Б. Вопросы оптимального расположения конгруэнтных фигур на плоскости: Автореф. Дис. канд.физ.-мат.наук. -Горький, 1970. 13 с.

30. Стоян Ю.Г., Панасенко А.А. Периодическое размещение геомеаь рических объектов. Киев: Наук.думка, 1978. - 175 с.

31. Фесенко А.Г. Решетчатая укладка плоских геометрических объектов с поворотом на угол ^ . Киев, 1980. - 22 с.(Препринт/ Ин-т кибернетики АН УССР: 80-53).

32. Фесенко А.Г. Двойная решетчатая укладка конгруэнтных многоугольных объектов. Докл.АН УССР, сер.А, 1981, № I, с.80-84.

33. Бабаев Ф.Б. Рациональный раскрой листа на детали сложных геометрических конфигураций в условиях индивидуального мелкосерийного производства. Сварочное пр-во, 1967, lb I, с.12-14.

34. Бабаев ф.Б. Рациональный раскрой листа на детали сложных геометрических конфигураций. Сварочное пр-во, 1968, Г& 8, с.12-14.

35. Краснов Н.М. Рациональный раскрой листовых материалов о применением ЭВМ в условиях судостроительного производства: Авто-реф. Дисс. канд. техн. наук. Л., 1976. - 17 с.

36. Рвачев В.Л. Об аналитическом описании некоторых геометрических объектов. Докл. АН СССР, 1963, т.153, 15 4, с.765-767.

37. Рвачев В.Л. Геометрические приложения алгебры логики. Киев: Техника, 1967. - 212 с.

38. Рвачев В.Л., Стоян Ю.Г. К вопросу об оптимальном раскрое материалов. В кн.:, Вопросы теорет.кибернетики, Киев, 1965, с.189-199.

39. Рвачев В.Л., Стоян Ю.Г. Алгоритмы построения неравенств, которым удовлетворяют параметры размещения непересекающихся тел. Кибернетика, 1966, 1 5, с.82-92.

40. Стоян Ю.Г. Методы R-функций в задачах оптимального раскроя: Автореф. Дис. . канд.физ.-мат.наук. Киев, 1966. -20 с.

41. Канторович Л.В., Залгаллер В.А. Рациональный раскрой промышленных материалов. Новосибирск: Наука, 1971. - 299 с.

42. Жак С.В., Зинченко А.Б., Сантылова Л.И. Оптимизационный выбор планировочных решений промышленных предприятий. В сб. "Применение системного анализа в прикладных задачах", Куйбышев, 1976, с.67-71.

43. Литвинов В.Н., Стоян Ю.Г., Новиков И.Д. Компоновка генеральных планов с помощью математических методов и ЭВМ. Изв. АН

44. СССР. Техническая кибернетика. 1979, J6 4, с.180-187.

45. Рагоалович И.И., Ренжиглова И.А., Зинченко А.Б. Выбор компоновочных решений промышленных зданий. В ж. "На стройках России", В I, 1981, с.48-50.

46. Ноймарк А.П., Шейнман Р.П., Голова В.Г. Расчет и программирование расстановки оборудования в цехах. I.: Судостроение, 1969, с.75-98.

47. Магас С.Л. Об одной задаче оптимального распределения ресурса. В кн.: Прикладные аспекты управления сложными системами: Тез.докл.Всесоюзного научно-практического семинара (Кемерово, 1983), М., 1983, ч.2, с.232.

48. Стоян Ю.Г., Гиль Н.И. Методы и алгоритмы размещения плоских геометрических объектов. Киев: Наук.думка, 1976. - 248 с.

49. Салуквадзе М.Е. Задачи оптимального управления при наличии нескольких критериев качества: Автореф. дисс. д-ра техн. наук. М., 1974. - 24 с.

50. Стоян Ю.Г. Размещение геометрических объектов. Киев: Наук, думка, 1975, - 237 с.

51. Александров П.С. Введение в теорию множеств и общую топологию. М.: Наука, 1977. - 367 с.

52. Стоян Ю.Г. Автоматизац1я об*емно-планувального проектування в машинобудуванн1. BIch.AH УССР, 1979, № 3, с.46-52.

53. Стоян Ю.Г., Винарскии В.Я. Алгебро-топологические свойства-объектов. Харьков, 1981. - 34 с.(Препринт/Ин-т пробл. машиностроения: 166).

54. Фукс Д.В., Фоменко А.Г., Гунтмахер В.Л. Гомотопическая топология. М.: Изд-во МГУ, 1969. - 459 с.

55. Фихтенгольц Г.М. Курс дифференциального и интегрального исчисления: Т.З, 5-е изд.,стереотип. М.: Наука, 1970.-656 с.

56. Энциклопедия элементарной математики: Кн.4-я. Геометрия. -М.: Физматгиз, 1963. 567 с.

57. Рвачев В.Л. Теория R-функций и некоторые ее приложения. -Киев, Наук.думка, 1982. 552 с.

58. Блох А.Ш., Трухан Т.Л. Неравенства. Минск: Нар.асвета, 1972. - 222 с.

59. Стоян Ю.Г. Об одном обобщении функции плотного размещения. ДАН УССР, сер.8, В 8, е.70-74.

60. Никольский С.М. Приближение функций многих переменных и теоремы вложения. М.: Наука, 1969. - 480 с.

61. Стоян Ю.Г., Пономаренко Л.Д. Рациональное размещение геомет>-рических тел в задачах автоматического проектирования. Изв. АН СССР. Техн.кибернетика, 1978, JS I, с.39-47.

62. Гэри М., Джонсон Д. Вычислительная математика и труднорешае-мые задачи. М.: Мир, 1982.

63. Стоян Ю.Г., Черепахин В.М. Об одном способе рационального размещения кругов в полосе. В кн.: Тез.докл.и сообщ. на Всееоюз.межвуз.симпоз.по прикл.математике и кибернетике. Горький, 1967, - с.176.

64. Стоян Ю.Г., Соколовский В.8. Решение некоторых многоэкстремальных задач методом сужающихся окрестностей. Киев: Наук, думка, 1980. - 208 с.

65. Комяк В.М. Об одном способе получения возможных:.вариантов размещения выкроек на материале. Харьков, 1978. - 25 с. (Препринт/Ин-т пробл. машиностроения: 102).

66. Гутер Г.С. Оптимизация методом частичного улучшения по группам переменных. В кн.: Математические методы решения экономических задач. М., 1969, с.21-38.

67. Растригин Л.А. Системы экстремального управления. М.: Наука, 1974. - 630 с.

68. Сергиенко И.В. О применении вектора спада для решения задач оптимизации комбинаторного типа. Упр.системы и машины, 1975, .й 2, с.86-94.

69. Сергиенко И.В. Применение вектора спада для решения задач целочисленного программирования. Упр.системы и машины, 1975, J5 3, с. 92-98.

70. Сергиенко И.В., Каспшицкая М.Ф. Модели и методы решения на ЭВМ комбинаторных задач оптимизации. Киев: Наук.думка, 1981. - 288 с.

71. Ещенко В.Г., Пономаренко Л.Д. Новый комплекс программ для автоматизированного построения карт раскроя промышленных материалов (полос). Харьков, 1979. - 14 с. (Препринт/Ин-т пробл.машиностроения: 122).

72. Комяк В.М. Оптимизация размещения плоских геометрических объектов в областях сложной формы. Автореф. дис. . канд.техн. наук. Харьков, 1980. - 24 с.

73. Стоян Ю.Г., Гиль Н.И. Свойства и способы реализации функции плотного размещения. Киев, 1972. - 46 с. (Препринт / Ин-т кибернетики АН УССР: 72-18).

74. Гиль Н.Й., Ещенко В.Г. Способ построения годографа вектор-функции плотного размещения для одного класса геометрических объектов. Харьков, 1977. - II с. (Препринт / Ин-т пробл. машиностроения: 63).

75. Курош А.Г. Лекции по общей алгебре. М.: Наука, 1976.- 399 с.

76. Стоян Ю.Г., Боидаренко Н.А., Магас С.Л. Об одном способе составления плана раскроя полосового материала. Харьков,1981.-18 с. - Рукопись представлена Ин-том проблм.машиностроения

77. АН УССР. Деп. в ВИНИТИ 17 февраля 1981, J3 1007-81.

78. Магас С.Л. Построение условий взаимных непересечений многогранников g использованием ортогонального проецирования.Автоматизация технологических процессов, 1982, вып.1, с.143-154.

79. Магас С.Л. Определение и свойства структур линейных неравенств. В кн.: Автоматизация проектирования в машиностроении, 1983, вып.З, с.5-11•

80. Колмогоров А.П, Фомин С.В. Элементы теории функций и функционального анализа. М.: Наука, 1972. - 496 с.

81. Рвачев В.Л. Теория R -функций и некоторые ее приложения.-Киев: Наук, думка, 1982. 552 с.

82. Магас С.Л. Об одном способе ортогонального проектирования многогранников. Харьков, 1981. - II с. - Рукопись представлена Ин-том пробл. машиностроения АН УССР. Деп. в ВИНИТИ4 авг. 1981, 1% 4308-81.

83. Черников С.Н. Линейные неравенства. М.: Наука, 1968.-374 с.

84. Кузнецов В.Г. Метод исключения неизвестных в теории линейных неравенств. Изв.вузов. Математика, 1962, J& 4, с.87-92.

85. Ахиезер Н.И., Глазман И.М. Теория линейных операторов в гильбертовом пространстве. Харьков: Вища школа, 1977. - 353 с.

86. Корбут А.А,,Сигал И.Х., Финкелыптейн Ю.Ю. Метод ветвей играниц. -Math. Operationforsc/г. StatistSer. Optimization, 1977, BcL.&,N2.

87. Магас С.Л. О решении задачи размещения многоугольников в по--лосе методом ветвей и границ. Харьков, 1983. - 12 с. - Рукопись представлена Ин-том пробл.машиностроения АН УССР.Деп. в ВИНИТИ 27 янв. 1983, В 287-83.

88. Магас С.Л., Стоян Ю.Г. Опыт применения метода ветвей и границ для решения задачи оптимального раскроя материала на многоугольные заготовки. В кн.: Автоматизация поискового конструирования и подготовка инженерных кадров: Тез.докл. III

89. Всесоюзной конф. Иваново, 1983, с.32-34.

90. Карманов В.Г. Математическое программирование. М.: Наука, 1975. - 272 с.

91. Линейное и нелинейное программирование. Под общей ред.И.Н. Ляшенко. Киев: Вища школа, 1975. - 372 с.

92. Магас С.Л. Об оптимальном раскрое полосы прямоугольными заготовками. В кн.: Вычислительная математика в современном научно-техническом прогрессе: Тез.докл.П'-й Респ.конф. Канев, 1982, с.92-93.

93. Хадвигер Г. Лекции об объеме, площади поверхности и изопери-метрии. М.: Наука, 1966. - 416 с.

94. Бондаренко Н.А., Магас С.Л. Об одном способе размещения геометрических объектов. В кн.: Математические методы кибернетики. Киев, 1978, с.49-55.

95. Бондаренко Н.А., Магас С.Л., Стоян Ю.Г. Об одном способе размещения геометрических объектов и его реализации. В кн.: Автоматизация поискового конструирования: Тез.докл.I Всесоюзной конф. Йошкар-Ола, 1978, с.14-15.