автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Методы математической теории оптимального управления в исследовании экстремальных задач геометрии

Введение.

Основные этапы развития и классификация задач раскроя - упаковки

Классификация задач раскроя -упаковки

Особенности задач нерегулярного фигурного раскроя

Последовательность решения задачи размещения.

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

Практическая новизна и актуальность задачи

Научная новизна и актуальность задачи

Краткое содержание работы

Результаты работы

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

Выводы

Глава 1.

1.1 Экстремальные задачи геометрии

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

Теорема о достаточных условиях оптимальности

1.2 Краткое описание методов и этапов решения задачи раскроя

Основные понятия, используемые в задачах раскроя — размещения

Функция плотного размещения

Годограф функции плотного размещения 41 Базовые этапы решения задачи о раскрое - размещении и методы, применяемые для их реализации

Представление информации о геометрических фигурах

Аппроксимация исходных геометрических фигур 43 Способы обеспечения условий взаимного непересечения геометрических фигур

Методы построения области допустимых размещений

Глава 2.

2.1 Решение задачи о нахождении фигуры максимального периметра

Формулировка задачи

Построение оптимальной траектории

Построение минимизирующей последовательности

2.2 Доказательство оптимальности решения, представленного на рис.2.

2.3 Доказательство оптимальности решения, представленного на рис.2.

2.4 Оптимальная траектория при наличии двух не влияющих друг на друга дополнительных ограничений

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

2.6 Решение задачи о нахождении фигуры максимального периметра с альтернативным функционалом

Постановка задачи

Построение оптимальной траектории

2.7 Решение задачи о нахождении фигуры минимального периметра

Формулировка задачи

Построение оптимальной траектории

2.8 Доказательство оптимальности решения, представленного на рис.2.

2.9 Построение фигуры вращения максимальной площади поверхности

Фигуры вращения

Постановка задачи

Построение оптимальной траектории

Глава 3.

3.1 Дискретная аппроксимация задачи оптимального управления

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

Построение симметричной фигуры по функции ширины.

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

Алгоритм построения приближенного оптимального решения

Замечания

Алгоритм с автоматически определяемыми коэффициентами штрафа

Результаты работы методов

3.3 Вариации метода динамического программирования

Алгоритм решения задачи методом динамического программирования

Результаты численного решения задачи

Метод блуждающих трубок

Алгоритм метода блуждающих трубок

3.4 Методы решения задачи нелинейного программирования

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

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

Результаты работы комбинированного метода проекции и внешних штрафных функций

Результаты работы комбинированного метода проекции градиента и барьерных штрафных функций

3.5 Метод Гаусса - Зейделя (последовательного улучшения по группам переменных).

Алгоритм метода последовательных улучшений по одной переменной

Результаты работы метода последовательной проекции градиента

3.6 Результаты применения приведённых численных методов и анализ влияния параметров вычислений на результаты

Сравнение результатов работы различных алгоритмов.

Влияние вычислительных параметров и начальных условий.

Фигуры вращения, восстановленные по опорной функции сечения.

3.7 Результаты работы метода Гаусса — Зейделя для задачи о минимальном периметре с различными начальными условиями

Результаты расчетов фигуры минимального периметра.

3.8 Описание решения задачи раскроя - размещения.

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

I. Формирование аппроксимирующего многоугольника

II. Выбор наилучшего приближения

III. Последовательное размещение фигур

3.9 Модификация основного этапа решения задачи оптимального раскроя на базе алгоритма последовательного- одиночного размещения.

I. Выбор фигуры для размещения.

II. Построение начальной области возможных размещений.

III.Последовательное добавление областей возможных размещений

IV. Преобразование всех областей возможных размещений в область допустимых размещений.

V. Выбор оптимальной точки размещения

VI. Выбор оставшегося параметра размещения 230 Последовательное приближение фигур в ходе нахождения их оптимального размещения.

3.10 Результаты работы модифицированного алгоритма решения задачи о раскрое—размещении.

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

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

Задача подкроя (остаточного размещения).

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

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

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

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

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

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

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

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

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

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

В направлении поиска эффективных методов фигурного оптимального раскроя современными учеными сделано немало [29,30,34,35,36,38,40,41,44,47,.]. На многих предприятиях программное обеспечение соответствует последним достижениям науки в этой области. Однако весьма существенный резерв повышения экономичности раскройно -заготовительных производств лежит в области представления более точными геометрическими моделями заготовок, получаемых в результате раскроя. Изменение традиционной прямоугольной формы заготовки на более обобщенную, в некотором смысле оптимальную, сулит существенное увеличение экономии материала. Безусловно, таковое изменение влечет за собой необходимость пересмотра и модификации методов и алгоритмов оптимального раскроя и соответствующего программного обеспечения, и эта задача с необходимостью встанет перед специалистами. Задача данной диссертационной работы -представить методы определения геометрической формы заготовок, оптимальной по некоторым параметрам.

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

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

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

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

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

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

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

Необходимо заметить, что точные методы решения задачи фигурного раскроя сводятся к перебору всего множества допустимых решений. Различными улучшениями такой перебор современными исследователями доведен до высокоэффективных алгоритмов. В качестве примера можно привести большую группу методов улучшенного перебора, объединенных под названием «метода ветвей и границ», изложение которой, в частности, можно отыскать в публикациях Романовского И.В. [68].

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

Модификация основных процедур, лежащих в основе решения задачи раскроя -размещения любым из существующих ныне способов предлагается в данной работе. При этом в качестве иллюстрации задача в целом решена наиболее известным и широко распространённым на производстве методом, разработанным харьковской школой под руководством СтоянаЮ.Г. [87-90].

Основные этапы развития и классификация задач раскроя - упаковки.

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

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

Впервые задачи раскроя геометрических объектов были рассмотрены великим русским математиком Чебышевым П.Л в 1878 г. Изучение вопросов размещения объектов было продолжено работами Фёдорова Е.С. о симметрии и структуре кристаллов.

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

Начало систематическому исследованию проблемы оптимального размещения плоских фигур было положено работами JI.B. Кантаровича. Классическим подходом к решению задач оптимального линейного раскроя, развитым Канторовичем Л.В. и Залгаллером В.А. [50], является сведение её к задаче линейного программирования.

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

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

В настоящее время достаточно хорошо изучены задачи нефигурного (линейного и прямоугольного гильотинного) раскроя. Это объясняется относительной простотой подобных задач. Однако промышленность, все чаще ставит задачи о фигурном раскрое, который подразумевает решение частных задач о выборе оптимальной формы заготовки. Как показывает анализ, для решения задач раскроя и размещения разработано довольно много математических методов [36,37,61,70,73,74]. В рассмотрении задач по построению оптимальных фигур лежит потенциальная возможность расширения класса задач о раскрое, для которых найдено приближенное или точное решение, численные алгоритмы и применение в производстве.

Задача фигурного раскроя представляет значительный теоретический интерес, так как имеет многочисленные приложения: раскрой в машиностроении, размещение элементов электронных схем на платах, оптимизация раскроя строительных материалов, распределение двумерного ресурса в экономических задачах. Исследования в области фигурного раскроя привели к выводу, что эта задача относится к классу NP - полных [43]. Это побудило к созданию серии приближённых алгоритмов полиномиальной сложности, для которых получены верхние оценки достигаемого качества решения.

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

Класс задач фигурного регулярного раскроя довольно развит и даёт хорошие практические результаты [41]. Наиболее исследованными и доведёнными до внедрения являются задачи построения оптимальных полос с наиплотнейшими однорядными и многорядными укладками в них фигур сложных форм. Эти задачи решены сегодня различными методами.

Задача нерегулярного фигурного раскроя - размещения относится к классу № -трудных задач [43]. Функция цели в таких задачах в общем случае нелинейная. Функции, представляющие собой ограничения, также являются нелинейными, на некоторых участках области они могут быть многозначными и в общем случае - кусочно - гладкими, то есть не всюду дифференцируемыми. Такие особенности задачи резко сужают круг применимых для решения методов. В частности, применяются разновидности метода частичного улучшения по группам переменных (метод Гаусса - Зейделя), заключающийся в последовательном размещении объектов в области упаковки с оптимизацией (по группе переменных, представляющих собой параметры размещения объекта) целевой функции.

Таким образом, процесс решения задачи фигурного нерегулярного раскроя имеет двухуровневую структуру:

1. Генерация списка заготовок, сортированного по приоритетам (внешняя процедура оптимизации);

2. Моделирование плотного движения заготовок в области размещения (внутренняя процедура оптимизации).

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

- аналитические способы (базируются на вычислениях над вещественными числами);

- приближенные способы (базируются на вычислениях над целыми числами или на логических операциях над булевыми переменными).

Аналитические способы дают более точные результаты, хотя и более трудоёмки. Приближённые же способы менее точны, но показывают высокое быстродействие [35,36].

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

Различные методы формирования приоритетного списка для линейного, прямоугольного, фигурного раскроев, а так же другие вопросы, связанные с решением задачи раскроя - размещения или трёхмерной упаковки исследованы в работах, выполненных сотрудниками и аспирантами кафедры вычислительной математики и кибернетики уфимского государственного авиационного технического университета под руководством профессораЭ.А. Мухачёвой [34-36,70-72,.].

Решению задачи нерегулярного фигурного раскроя посвящены работы [29,30,34,35,36,38,40,41,44,47,50,65,70,72,74,76,87-90].

Классификация задач раскроя -упаковки

Толстой линией на представленной диаграмме показаны разновидности общей задачи раскроя - размещения (упаковки), которые рассматриваются в данной работе.

Особенности задач нерегулярного фигурного раскроя

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

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

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

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

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

Последовательность решения задачи размещения.

Достаточно полное представление о методах, применяемых на различных этапах решения задачи о размещении можно найти в работах [36] [65]. Приведём краткую схему последовательного решения задачи раскроя - размещения существующими на данный момент методами:

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

1. Приближение размещаемых фигур геометрическими примитивами, например, кругами.

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

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

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

1. Формирование области допустимых размещений на основе годографа вектор - функции плотного размещения. Этот метод подробно рассматривается в данной работе.

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

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

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

III. Основной процедурой в алгоритмах решения задачи раскроя - размещения является формирование последовательности укладываемых геометрических фигур. Этот этап формирует приближение к локальному (глобальному) экстремуму функции цели. Среди методов решения этой первичной задачи можно выделить:

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

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

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

1. Методы случайного поиска: метод Монте-Карло, метод последовательной статистической оптимизации и др.

2. Метод ветвей и границ. Данный метод является, вероятно, наиболее трудоёмкой вариацией приближенных методов отыскания глобального экстремума функции цели.

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

4. Жадный метод. Данный метод подробно рассмотрен в работе Мартынова В.В. [65] и является, как и методы случайного поиска, по сути, эвристическим, то есть представляет собой «ухудшение» точного метода.

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

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

Практическая новизна и актуальность задачи:

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

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

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

Приведем обобщенную стандартную формулировку задачи о раскрое:

Разместить на листе заданной формы и размера (обычно прямоугольной формы) максимальное число заготовок заданной формы и размеров (обычно прямоугольников).

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

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

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

2. Разместить максимальное количество заготовок оптимальной формы (или формы, близкой к ней с произвольной точностью) на листе материала.

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

1. Наметим пути подхода к определению формы заготовки, оптимальной с некоторой точки зрения.

Во - первых, необходимо учитывать, что деталь, которая будет производится из заготовки в дальнейшем производстве (например, на предприятии - партнере), может иметь сложную форму, в том числе и не известную предприятию, занимающемуся раскройно-заготовительными работами. В таком случае требования к заготовкам естественно сформулировать в терминах опорных функций. Например, «ширина заготовки в любом направлении должна быть не меньше 5 сантиметров». Напомним, что такому требованию удовлетворяет любая фигура, содержащая в себе круг диаметром 5 см. Или: «ширина л заготовки в двух направлениях, угол между которыми — должна быть не меньше 5 см.». 4

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

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

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

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

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

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

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

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

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

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

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

2. Размещение максимального количества заготовок некоторой формы имеет несколько этапов.

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

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

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

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

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

Научная новизна и актуальность задачи:

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

Исследование свойств выпуклых фигур известны с глубокой древности. Все ученые, благодаря которым мы знаем геометрию в ее современном виде так или иначе в своих трудах прикасались к экстремальным свойствам геометрических фигур. Одним из значительнейших вкладов в область исследования экстремальных свойств выпуклых фигур можно считать труды конца позапрошлого- начала прошлого века Вильгельма Бляшке [23], [24]. В. Бляшке ставил перед собой разнообразнейшие задачи относительно круга, шара, тел вращения и их экстремальных свойств. Однако необходимо обратить внимание на то, что при доказательствах геометрических теорем и в разнообразных исследованиях в области геометрии в то время использовались в основном геометрические методы, что в то время казалось вполне естественным. В конце 19 века теория выпуклых тел оформилась как самостоятельная математическая дисциплина. В настоящее время она является наукой, богатой общими методами и отдельными замечательными результатами. Среди них и выработка новых подходов к описанию задачам о фигурах с экстремальными свойствами. Теория выпуклых тел послужила основой созданного в середине прошлого века А.Д. Александровым нового важного направления в наиболее значительной из современных геометрических наук - дифференциальной геометрии.

Формализация задач об экстремальных свойствах геометрических фигур в терминах дифференциальной геометрии и теории выпуклых тел позволила Е. А. Андреевой в сотрудничестве с Р. Клотцлер в 80-х годах 20 века сформулировать и решить аналитически с применением двойственных методов математической теории оптимального управления ряд экстремальных задач геометрии, которые ранее либо не имели решения, либо были решены изобретательными, но громоздкими геометрическими методами.

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

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

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

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

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

Решение задач оптимизации имеет большое значение для различных областей электротехники, среди которых: техника высоких напряжений, электрические машины и аппараты, электрические станции и сети, электрофизика, электромагнитная совместимость и т.д. Задачу поиска оптимальной формы находящихся в электромагнитном поле тел можно рассматривать как задачу оптимального управления электрическими и магнитными свойствами среды. При этом характеристики среды можно называть переменными управления, а потенциалы электромагнитного поля - переменными состояния [83]. Алгоритм поиска оптимума является при таком рассмотрении алгоритмом управления характеристиками среды. Его целесообразно искать методами оптимального управления.

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

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

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

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

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

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

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

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

Краткое содержание работы

1. Andreewa J. A., Klötzler R. Zur analytischen hösung geometrische Optimierungsaufgaben mittas Dualität bei Stenerungsaufgaben. Teil 1. II, ZAMM, (64), 1984.

2. Bonnesen T., Fenchel W. Theorie der konvexen. Körper, Berlin, 1934.

3. Bonnesen T. Über das isoperimetrische Defixit ebener Figuren. Math. Ann., Bd. 91 (1924), S. 252-268.

4. Fabard J. Problèmes d'extremums relatifs aux courbes convexes. 1,11, Ann. Écolenorm, Bd. 46 (1929), S. 845 369, Bd. 47 (1930), S. 313 - 324.

5. Bonnesen T. Über das isoperimetrische Defixit ebener Figuren. Math. Ann., Bd. 91 (1924), S. 252-268.

6. Favard J. Problèmes d'extremums relatifs aux courbes convexes. I, II, Ann. Écolenorm, Bd. 46 (1929), S. 845 369, Bd. 47 (1930), S. 313 - 324.

7. Klötzler R. Globale Optimiezung in der Steuerungs theorie. ZAMM, (63), 1983.

8. Klötzler R., Rudolph H. Zur Behandlung eines geometrischen Optimierungs Problems von J. Steiner. Optimization, 16, (1985), S. 233 845.

9. Klötzler R. Geometrical applications of duality in optimal control. Mathematical method in Operations Research, Sophia, 1983, P. 52-69.

10. Minkowski H. Theorie der konvexen Körper. In Gesammelte Abh. 2 Leipzig, Teubner Verlag, 1911. S. 131-229.

11. Sholander M. On certain minimum problems in the theorie ofconvex curves. Trans, Amer. Math. Soc., 83 (1952), P. 139 173.

12. Андреева E. А. Оптимальное управление динамическими системами. Тверь, 1999.

13. Андреева Е.А. Применение двойственного метода для решения одной экстремальной задачи геометрии Геометрические вопросы теорий функций и множеств Калинин 1985

14. Андреева Е.А. Применение двойственного метода к решению геометрических задач Международная школа по оптимальному управлению Грайсвальд 1983 С. 5-9

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

16. Андреева Е.А., БенкеХ. Оптимизация управляемых систем. Тверь, 1996

17. Андреева Е. А., Надь Е. Двойственность в теории экстремальных задач. Учебное пособие, Калинин, 1985.

18. Андреева Е. А., Цирулёва В. М. Методы оптимизации. Тверь, 1995.

19. Бакушинский А.Б. Гончарский A.B. Итеративные методы решения некорректных задач. Москва, Наука, 1989.

20. Беллман Р., Капаба Р. Динамическое программирование и современная теория управления. Москва, Наука, 1969.

21. Благо датских В.И. Введение в оптимальное управление. Москва, высшая школа, 2001

22. Благодатских В.И. Принцип максимума для дифференциальных включений. Тр. Мат. Ин-та АН СССР 1984 Т. 166

23. Бляшке В. Круг и шар. Москва, Наука, 1977.

24. Бляшке В. Дифференциальная геометрия. Москва, Наука,1971.

25. Болтянский В.Г., Яглом И.М. Выпуклые фигуры М. Наука, 1951

26. Болтянский В.Г. Математические методы оптимального управления Москва. Наука, 1969

27. Боннезен Т. Фенхель В. Теория выпуклых тел Берлин 1934

28. Бураго Д. М., Залгаллер В. А. Геометрические неравенства. Москва, Наука,1980.

29. Бурмистрова Л.В. Анализ и использование адаптивных методов аппроксимации выпуклых тел многогранниками. Диссертация канд. ф. м. наук. Москва, МГУ им. Ломоносова, 2000.

30. Бурнашев М.А. Теория и технология раскроя пакетов машиностроительных текстильных материалов сверхзвуковой струёй жидкости. Диссертация канд. ф. м. наук. Орёл, 1998.

31. Васильев Ф.П. Лекции по методам решения экстремальных задач. Москва, Московский университет, 1974.

32. Васильев Ф.П. Методы решения экстремальных задач. Москва, Наука,1981.

33. Васильев Ф.П. Численные методы решения экстремальных задач. Москва, Гл. ред. физ.-мат. лит., 1980.

34. Верхотуров М.А. Математическое обеспечение автоматических систем нерегулярного размещения двух и трехмерных геометрических объектов. Диссертация канд. ф. м. наук. Уфа, УГАТАУ, 2000.

35. Верхотуров М.А., Верхотурова Г.Н. О способе представления информации для решения некоторых прикладных задач нелинейного программировании: Математическое программирование и приложения. Тезисы докладов. Екатеринбург 1995.

36. Верхотурова Г.Н. Моделирование рационального размещения трехмерных геометрических объектов в системах автоматизированного проектирования раскроя -упаковки. Диссертация канд. ф. м. наук. Уфа, УГАТАУ, 1997.

37. Габасов Р., Кириллова Ф.М. Конструктивные методы оптимизации. Минск, БГУ, 1984.

38. Габитов В.А. Автоматизированная система предпроектного исследования моделей и алгоритмов рационального раскроя. Диссертация канд. ф. м. наук. Уфа, УГАТАУ, 1994.

39. Голыптейн Е.Г., Третьяков Н.В. Модифицированные функции Лагранжа. Москва, Наука, 1989.

40. Горанский Г.К., Бендерева Э.И. Технологическое проектирование в комплексных автоматизированных системах подготовки производства. Москва, Машиностроение, 1981.

41. Грибов А.Б. Алгоритмы решения задачи плоского раскроя. Кибернетика, 1973, №6.

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

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

44. Давыдова И.М. Схемы перебора в задачах размещения. Ленинград, ЛГУ, 1985.

45. Дубовицкий А.Я., Милютин A.A. Задачи на экстремум при наличии ограничений. Москва, ЖВМ и МФ, 1965, -5, №3.

46. Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации. Москва, Наука, 1982.

47. Ефимова Т.Е. Прямоугольный негшьотинныйраскрой на основе поиска оптимальных элементов. Диссертация канд. ф. м. наук. Уфа, УГАТАУ,1999.

48. Зенкевич О., Морган К. Конечные элементы и аппроксимация. Москва, Мир, 1986.

49. Иоффе А.Д., Тихомиров В.М. Теория экстремальных задач. Москва, Наука, 1974.

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

51. Картак В.М. Модели и методы оптимизации упаковки N- мерных параллелепипедов. Авт. реф. дис. канд. ф. м. наук. Уфа, УГАТУ 1999.

52. Красноженов Г. Г. Применение двойственного метода в экстремальных задачах геометрии. Методы и алгоритмы исследования задач оптимального управления: Сборник научных трудов ВЦ РАН, ТВГУ. Тверь: ТВГУ, 1999.

53. Красноженов Г. Г. Применение двойственного метода для решения экстремальных задач геометрии. Ученые записки Тверского государственного университета: Сборник научных трудов. Тверь: ТВГУ,2000.

54. Красноженов Г. Г. Применение двойственного метода в экстремальных задачах геометрии. Применение функционального анализа в теории приближений: Сборник научных трудов. Тверь: ТВГУ, 2000.

55. Красноженов Г. Г. Некоторые применения двойственного метода в экстремальных задачах геометрии. Математическое моделирование в естественных и гуманитарных науках. Тезисы докладов. Воронеж, 2000.

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

57. Краснощеков П.С., Петров A.A. Принципы построения моделей МОСКВА,МГУ, 1983

58. Красовский H.H. Теория управления движением. Москва, Наука, 1968.

59. Кротов В. Ф., Гурман В. И. Методы и задачи оптимального управления. Москва, Наука, 1973.

60. Крылов И.А., Черноусько Ф.Л. Алгоритм метода последовательных приближений для задач оптимального управления. Москва, ЖВМ и МФ, 1972, 12, №1.

61. Лесин В.В. Лисовец Ю.П. Основы методов оптимизации. Москва, МАИ, 1998.

62. Летов A.M. Математическая теория процессов управления. Москва, Наука, 1981.

63. Лионе Ж.Л. Некоторые методы решения нелинейных краевых задач. Москва, Мир, 1972.

64. Любушин A.A., Черноусько Ф.Л. Метод последовательных приближений для расчета оптимального управления. Москва, Извест. АН СССР. Технич. кибернет., 1983, №2.

65. Мартынов В.В. Автоматизированная система управления процессом раскроя геометрических объектов сложной формы. Диссертация доктора ф. м. наук. Уфа, УГАТАУ, 1999.

66. Марчук Г.И. Методы вычислительной математики. Москва, Наука, 1989.

67. Марчук Г.И. Агошков В.И. Введение в проекционно-сеточные методы. Москва, Наука, 1981.

68. Моисеев H.H. Элементы теории оптимальных систем. Москва, Наука, 1975.

69. Моисеев H.H., Иванилов Ю.П., Столярова Е.М. Методы оптимизации. Москва, Гл. ред. физ.-мат. лит., 1978.

70. Мухачева Э.А., Рациональный раскрой промышленных материалов. Применение в АСУ. Москва, Машиностроение, 1984.

71. Мухачева Э.А., Математическое программирование. Москва, Машиностроение, 1987.

72. Мухачева Э.А., Белякова Л.Б. Задачи планирования рационального раскроя и их комплексное решение //Принятие решение в условиях неопределённости. Уфа: УАИ, 1990.

73. Окулевич А.И. Необходимые условия экстремума в задачах оптимального управления с промежуточными ограничениями. Диссертация канд. ф. м. наук. Москва, РУДН, 1995.

74. Окунев Б.В. Разработка алгоритма управления эффективным раскроем сырья. Диссертация канд. ф. м. наук. Москва, 1995.

75. Павлидис Т. Алгоритмы машинной графики и обработки изображений. Москва, Радио и связь, 1986.

76. Перцовский П.Г. Программно методический комплекс для расчёта рационального использования материалов в подготовительно —раскройном производстве обувной промышленности. Диссертация канд. ф. м. наук. Москва, 1999.

77. Поляк Б.Т. Введение в оптимизацию. Москва, Наука, 1983.

78. Понтрягин Л.С., Болтянский В.Г., Гамкрелидзе Р.В., Мищенко Е.Ф. Математическая теория оптимальных процессов. Москва, Наука, 1983.

79. Пирумов У.Г. Численные методы. Москва, МАИ, 1998.

80. Пресняков P.A. Геометрическое моделирование и оптимизация раскроя в САПР заказных корпусных мебельных изделий. Диссертация канд. тех. наук. Воронеж, ВГТУ, 1999.

81. Пшеничный Б.Н. Данилин Ю.М. Численные методы в экстремальных задачах. Москва, Наука, 1975.

82. Романовский И.В. Алгоритмы решения экстремальных задач. Москва, Наука, 1977.

83. Рубина Т.Б. Повышение эффективности раскройно-заготовителъного производства путем оптимизации раскроя длинномерных материалов. Диссертация канд. тех. наук. Москва, МГТУ «СТАНКИН», 2000.

84. Соломещ И.А., Рудерман С.Ю. Минимизация функций, заданных на нормально разворачиваемых, частично упорядоченных множествах. // Модели организации, управления и методы их исследования. Сборник, Уфа, БГУ, 1975.

85. Срочко В. А., Антоник В.Г. К решению задач оптимального управления на основе методов линеаризации. Москва, ЖВМ и МФ, 1992, -32, №7.

86. Станюкова И.В. Исследование итеративной схемы метода конечных элементов, штрафов и градиентного спуска для решения одного класса вариационных задач. Диссертация канд. ф. м. наук. Москва, МГУ им Ломоносова, 1998.

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

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

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

90. Стоян Ю.Г., Яковлев C.B. Математические модели и оптимальные методы геометрического проектирования. Киев, Наук, думка, 1986.

91. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. Москва, Наука, 1986.

92. Сумин М.И. О минимизирующих последовательностях в задачах оптимального управления при ограниченных фазовых координатах. Москва, Дифференциальные уравнения, 1986, -22, №10.

93. Троицкий В.А. О вариационных задачах оптимизации процессов управления. Москва, Приклад, матем. и мех. 1962 -26, №1.

94. Федоренко Р.П. Приближенное решение задач оптимального управления. Москва, Наука, 1978.

95. Фиакко А. Маккормик Г. Нелинейное программирование. Москва, Мир, 1972.

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

97. Шебалдин В.Р. Численное решение задач оптимального управления с фазовыми ограничениями. Диссертация канд. ф. м. наук. Саратов, СГУ им. Чернышевского, 1997.

98. Штаутмайстер Томас Динамическая оптимизация раскроя дискретнопоступающего материала при оперативном управлении (для условий лесоперерабатывающего предприятия). Диссертация канд. тех. наук. Москва, 1998.

99. Эйдемиллер М.В. Применение метода Лагранжа для оптимизации формы тел в электромагнитном поле. Диссертация канд. тех. наук. Санкт-Петербург, С-Пб ГТУ, 2001.

100. Яглом И. М., Болтянский В. Г. Выпуклые фигуры. Москва, 1951.