Содержание к диссертации
Введение
Глава 1. Задачи раскроя и комплектовки в моделировании технологических процессов 16
1.1 Терминология и обозначения 17
1.2 Содержание моделей раскроя и комплектовки 19
1.3 Прикладные задачи поиска оптимального плана раскроя и комплектовки 27
1.4 Задачи оптимизации состава планов раскроя и комплектовки 37
1.5 Критерии эффективности в рассматриваемых задачах . 40
1.6 Краткая характеристика рассматриваемых задач . 48
1.7 Идентификация моделей и их параметров 51
1.8 Выводы 55
Глава 2. Особенности применения математических методов при решении задач раскроя и комплектовки 56
2.1 Особенности применения динамического программирования 56
2.2 Метод декомпозиции и синтеза планов раскроя и комплектовки 62
2.3 Особенности решения задач линейного программирования 67
2.4 Задачи ЛП специальной структуры 76
2.5 Генерация столбцов в задачах раскроя и комплектовки . 81
2.6 Дискретность и нелинейность связей в задачах оптимизации 84
2.7 Двойственные оценки и расчет эффективности технологий 92
2.8 Комплексы задач планирования производственного процесса 94
2.9 Выводы 96
Глава 3. Задачи оптимизации планов раскроя и методы их решения 99
3.1 Варианты задачи планирования раскроев 99
3.2 Обобщенная модель оптмизации планов раскроя 104
3.3 Использование модели в условиях стохастики производственного процесса 108
3.4 Метод решения обобщенной задачи 111
3.5 Модели формирования объемно-календарного плана 114
3.6 Методы решения задачи ОКП 117
3.7 Выводы 127
Глава 4. Прикладные задачи раскроя материалов 128
4.1 Задача планирования раскроев и распределения заявок между БДМ 128
4.2 Задача планирования производства гофротары 140
4.3 Задача выбора транспортных средств и размещения продукции 149
4.4 Особенности планирования погрузки водного транспорта 160
4.5 Задача планирования производства пиломатериалов . 165
4.6 Задача разработки горного массива 168
4.7 Выводы 169
Глава 5. Прикладные задачи комплектовки материалов 171
5.1 Задача планирования работы фанерного производства 171
5.2 Задача комплектовки оборудования производства щепы 175
5.3 Комплектовка оборудования многофазного производства 179
5.4 Задача расчета оптимальных схем комплектовки поддонов 186
5.5 Задача компоновки нестандартных съемов тамбуров 189
5.6 Выводы 193
Заключение 194
Библиографический список 195
- Прикладные задачи поиска оптимального плана раскроя и комплектовки
- Генерация столбцов в задачах раскроя и комплектовки
- Использование модели в условиях стохастики производственного процесса
- Задача выбора транспортных средств и размещения продукции
Введение к работе
В основу диссертационного исследования положен многолетний опыт разработки и применения математического моделирования, методов и комплексов программ для решения задач планирования производства, прежде всего, предприятий лесопромышленного комплекса, (ЛПК) и целлюлозно-бумажной промышленности (ЦБП).
Диссертационная работа охватывает вопросы построения математических моделей планирования производственных процессов, разработки методов решения соответствующих оптимизационных задач и комплексов программ, в которых тесно переплетаются научные и прикладные проблемы.
Актуальность темы. Сложная социально-экономическая ситуация в России, обострение конкуренции среди промышленных предприятий и необходимость снижения себестоимости производимой продукции все настоятельнее требуют повышения эффективности производства, более рационального расходования имеющихся в его распоряжении финансовых и материальных средств и ресурсов, повышения производительности труда. Учитывая сложное финансовое положение многих предприятий и проблемы поиска инвестиций, часто не удается добиться повышения эффективности производства за счет экстенсивных факторов или расширения производства, его существенной реструктуризации и модернизации, освоения новой, более совершенной и конкурентоспособной продукции.
В значительной степени данные проблемы проявляются в перерабатывающих отраслях промышленности (лесной, деревообрабатывающей, целлюлозно-бумажной, металлургической, горноперерабатыва-ющей и др.), где кроме общеэкономических присутствуют специфические, отраслевые проблемы: истощение наиболее продуктивных и каче б ственных сырьевых баз, непропорционально высокий рост транспортных и топливно-энергетических расходов, повышение требовательности заказчиков к качеству производства и оформлению готовой продукции, снижение платежеспособного покупательского спроса, колебания цен на продукцию на внутреннем и внешнем рынках. В сложившихся условиях, одним из наиболее эффективных способов решения вышеуказанных проблем заключается в качественно новом уровне планирования и управления предприятием и его подразделениями, используя современные организационные и информационно-аналитические методы, математическое моделирование, современные автоматизированные системы управления технологическими процессами и интегрированные системы управления предприятиями, системы поддержки принятия решений. При этом повышение эффективности производства может достигаться за счет оптимизации производственных процессов, то есть за счет принятия рациональных управленческих решений, позволяющих повысить согласованность работы отдельных агрегатов, входящих в состав технологической системы. В результате этого сокращается время простоя оборудования, достигается значительная экономия сырья и энергии, повышаются объемы и качество выпускаемой продукции при аналогичных трудовых и производственных затратах.
Исследование производственных технологических процессов в перерабатывающих отраслях промышленности показало, что многие из них связаны с раскроями и комплектовкой материалов. Являясь очень важными, с точки зрения экономии используемых ресурсов, и, в то же время, одними из наиболее сложных для решения, эти задачи способны обеспечить возможность оптимального планирования и управления производственными процессами, сократить расход сырья и переделов, снизить себестоимость продукции и, в конечном счете, принести высокий экономический эффект. Для решения данных задач можно эффективно использовать методы математического моделирования и опти мизации с применением компьютерных технологий.
Следует отметить, что использование классических методов решения задач раскроя и комплектовки, как правило, не применимо для оптимизации многих реальных производственных процессов из-за необходимости учета их специфических особенностей, в частности - связей между объектами и предметами раскроя и комплектовки, а также - многочисленных дополнительных ограничений, обусловленных конкретными технологиями раскроя. Указанное обстоятельство требует разработки комплекса моделей, методов и программных систем для решения обобщенного класса задач раскроя и комплектовки с учетом дополнительных ограничений, что подтверждает актуальность выбранной темы диссертационного исследования.
Основная цель диссертационного исследования — разработка математических моделей, методов и комплексов программ для решения задач раскроя и комплектовки материалов в производственных системах.
В соответствии с поставленной целью в диссертации решаются следующие задачи:
1. Обоснование необходимости решения класса задач, связанных с оптимизацией планирования раскроев и комплектовок при наличии дополнительных ограничений;
2. Постановка и исследование комплекса математических моделей обобщенной задачи раскроя и комплектовки материалов.
3. Разработка методов решения обобщенной задачи раскроя и комплектовки с учетом большой размерности.
4. Определение схем декомпозиции прикладных многокритериальных задач расчета объемного и объемно-календарного планов, разработка методов расчета динамических параметров формирования производственных планов раскроя и комплектовки.
5. Разработка комплекса программ для решения прикладных задач раскроя и комплектовки материалов. 6. Разработка рекомендаций по использованию предложенных моделей, методов и программных систем в организации планирования и управления производственными процессами, создании систем поддержки принятия решений.
Объектом исследования являются производственные технологические процессы, связанные с раскроями и комплектовкой материалов.
Предметом исследования — математические модели и методы решения задач раскроя и комплектовки.
Методы исследования. Теоретической и методологической основой исследования являются методы исследования операций и математического программирования. Системный анализ и методы оптимизации используются для анализа производственных процессов, построения математических моделей производственных процессов и разработки алгоритмов решения соответствующих экстремальных задач.
Методы линейного, динамического и дискретного программирования, теория двойственности, а также различные схемы декомпозиции задач используются для решения линейных и нелинейных задач сложной структуры и высокой размерности, элементы теории вероятности и математической статистики — для идентификации параметов и исследовании стохастических факторов.
Для разработки алгоритмов и программных комплексов использовались теория алгоритмов и структур данных, современные технологии проектирования программных систем, методы структурного и объектно-ориентированного программирования, проектирования баз данных. Для разработки программ использовались языки и системы программирования Fortran, C++, Pascal, Delphi, Clipper и ORACLE.
Научная новизна. В диссертации предложены новые и модифицированы известные методы решения прикладных задач, названных обобщенными задачами раскроя, предложены принципы классификации исследуемых моделей, разработаны новые методы и схемы декомпозиции задач.
К числу результатов исследования, обладающих научной новизной и выносимых на защиту, относятся следующие:
• Сформулирован и исследован класс задач оптимизации для моделирования процессов, содержащих операции раскроя и комплектовки материалов.
• Определен класс обобщенных задач раскроя, объединяющий рассматриваемые модели. Предложена классификация задач указанного класса.
• Разработаны схемы декомпозиции обобщенных задач раскроя и методы решения вспомогательных задач, связанных с ними;
• Разработаны методы расчета динамических параметров формирования производственных планов раскроя и комплектовки.
• Разработаны и протестированы эффективные методы и алгоритмы решения этих задач;
Практическая значимость и реализация результатов работы.
Полученные в диссертации результаты использовались при выполнении госбюджетных и хоздоговорных научно-исследовательских работ, выполненных под руководством и при личном участии автора на кафедре прикладной математики и кибернетики, в Центре ПетрГУ-Метсо систем автоматизации Петрозаводского государственного университета в 1981-2004г.г.
В работе приведены результаты вычислительных экспериментов, которые подтверждают применимость разработанных алгоритмов и программ для решения задач с размерностью, требуемой на практике. Представленные в работе математические модели, методы и алгоритмы решения, программные комплексы используются на ряде крупных предприятий (ОАО "Архангельский ЦБК", ОАО "Сегежский ЦБК", ОАО "Кондопога", ОАО "КотласскийЦБК", ОАО "Карелэнерго", АХК "Кареллеспром" и др.). В результате эксплуатации программных систем на предприятиях повысилась эффективность управления производством, получен реальный экономический эффект. На основании результатов внедрения программных комплексов в промышленное производство, разработаны рекомендации по использованию предложенных моделей и методов в организации планирования и управления производственными процессами.
Рассмотренные в диссертации математические модели и методы решения задач обладают достаточной общностью и могут использоваться для планирования и управления производствами в других отраслях промышленности.
Полученные результаты используются в учебном процессе, курсовых и дипломных работах студентов, исследованиях аспирантов, отражены в учебно-методической разработке "Исследование операций в планировании и управлении предприятием ЛПК" (С.-Петербург: Изд-во СПбГЛТА, 2001).
Апробация работы. Основные результаты диссертационной работы докладывались автором на I съезде лесопромышленников Республики Карелия (Петрозаводск, 2004), Международной научно-технической конференции «Лесопромышленная логистика и информационные системы лесного комплекса» (Санкт-Петербург, 2003), Всероссийской научно-практической конференции «Проблемы лесопромышленных регионов» (Москва, 2002), IV Международном форуме «Лесопромышленный комплекс России XXI века» (Санкт-Петербург, 2002), I-V Международных научно-технических конференциях «Новые информационные технологии в ЦБП и энергетике» (Петрозаводск, 1994, 1996, 1998, 2000, 2002), Научно-практических конференциях АХК «Кареллеспром» (Петрозаводск, 1998-2003), Международной конференции «Но вые технологии и устойчивое управление в лесах Северной Европы» (Петрозаводск, 2001); Республиканской научно-практической конференции «Устойчивое развитие региона: лесопромышленный комплекс» (Петрозаводск, 2000 г.), Республиканской научно-практической конференции «Актуальные проблемы лесного комплекса» (Петрозаводск, 1999 г.), XXV международной конференции «Экономическая наука: Теория, методология, направления развития» (Санкт-Петербург,1998), Республиканской научно-практической конференции «Ресурсосберегающие технологии лесного комплекса» (Петрозаводск, 1998), Международной научно-технической конференции «Проблемы развития лесного комплекса Северо-западного региона» (Петрозаводск, 1996), Всероссийской научно-практической конференции «Новые информационные технологии в образовании и управлении» (Петрозаводск, 1993 г.) и других конференциях и семинарах.
Структура и объем работы. Диссертация состоит из введения, 5 глав основного материала, заключения, библиографического списка и 3 приложений. Основной материал изложен на 218 стр., включая 26 рисунков и 17 таблиц. Библиографический список включает 198 наименований. Приложения содержат материалы, связанные с практическим использованием результатов диссертации.
Публикации. Основные результаты диссертационной работы опубликованы в 77 печатных работах, в т.ч. 6 монографиях, 67 статьях и материалах Международных, Всероссийских и региональных конференций и семинаров, 4 учебных пособиях.
Содержание работы
Во введении обоснована актуальность темы диссертации, указаны цель и задачи исследования, обсуждены научная новизна и практическая значимость работы.
В начале первой главы представлена терминология, необходимая для описания математических моделей и методов решения соответ ствующих оптимизационных задач. Вводятся задачи раскроя и комплектовки, устанавливается их содержание, приводится классификация связанных с ними моделей. Исследование наиболее часто встречающихся на практике задач выявляет основные особенности рассматриваемого в последующих главах класса моделей — большое количество разнообразных дополнительных ограничений и возможность декомпозиции планов раскроя.
Рассматривается проблема критерия оптимальности. Практически все прикладные задачи являются многокритериальными, что вызывает необходимость использования соответствующих средств их решения. Заключительные разделы главы посвящены идентификации моделей планирования и управления производством и исследованию связей задач комплекса математических моделей. Первую главу диссертации, как и последующие, завершают выводы.
Вторая глава содержит описание разработанных автором методов и технических приемов решения задач раскроя и комплектовки. Эти задачи весьма неоднородны не только по своему назначению и месту в планировании и управлении производством, но и по структуре используемой модели, переменным, связям между ними, критериям эффективности и целевым функциям. Ввиду сложности- прикладных задач этого класса, большая их часть реализуется комплексом взаимосвязанных моделей.
Решение большого количества весьма разнообразных по форме и содержанию оптимизационных задач требует использования определенного набора средств, инструментария постановщика модели и разработчика алгоритмов. Содержание главы посвящено особенностям применения методов линейного, дискретного, динамического программирования (ДП), методов декомпозиции и эвристик в решении рассматриваемых экстремальных задач.
В третьей главе конструируется класс задач раскроя и ком плектовки, который удачно сочетает многообразие приложений в области управления производством и возможность использования единого математического инструментария алгоритмов решения.
Для этого исследуются прикладные задачи и выделяются два класса взаимосвязанных моделей: формирования планов и оптимизации их состава. Изучение особенностей этих задач приводит к обобщенной задаче оптимизации планов раскроя, для решения которой удается применить эффективный метод генерации столбцов. Задача носит достаточно общий характер, на практике встречаются ее частные случаи, признаки которых позволяют классифицировать широкий класс моделей оптимизации планов, достаточно полно представляющих большое количество прикладных задач раскроя и комплектовки.
Исследуемый класс задач составляют детерминированые модели. Их практическую значимость и адекватность ситуации управления можно повысить, используя представленные в следующем разделе приемы, которые позволяют в рамках данного класса задач учесть некоторые стохастические факторы, включая случайный характер появления продукции пониженного качества или неопределенность сроков переналадки оборудования. Главу завершает исследование связей объемного (ОП) и объемно-календарного планов (ОКП) производств, а также методы построения ОКП на основе рассчитанного ОП.
В четвертой и пятой главах рассматриваются прикладные задачи оптимизации планов раскроя и комплектовки, среди которых расчет планов и распределение заявок с учетом режимов работы группы бумагоделательных машин, формирование ОП и ОКП производства го-фротары, оптимизация погрузки продукции предприятия ЦБП в транспортные средства (ТС), выбор оборудования для заготовки и транспортировки древесины и технологической щепы, комплектовка оборудования лесозаготовительного предприятия и другие. Эти задачи являются частными случаями обобщенной модели, представленной в 3 главе, они охватывают разные аспекты управления предприятиями и характерны для комплексной системы управления производством предприятий различных отраслей промышленности.
В заключении представлены основные результаты работы.
Диссертацию завершают библиографический список из 197 наименований. Приложения содержат материалы, связанные с практическим использованием результатов диссертации.
Автор благодарит за поддержку и полезные советы при подготовке и оформлении диссертации, проф. Чернецкого В. И. — основателя научной школы прикладной математики ПетрГУ, доц. СПбГУ Шала-бина Г. В., проф. И.Р.Шегельмана, доц. Воронина А. В.
Прикладные задачи поиска оптимального плана раскроя и комплектовки
Подобная постановка задачи черезвычайно широка, поскольку любой ресурс, включая финансовые средства или промежуток времени, можно считать своебразным материалом, подлежащим раскрою — делению на части. Поэтому ее конкретизация, построение математической модели и выбор метода решения связаны с уточнением понятий: А1. объектов раскроя Фу (г Є 1..m); А2. предметов раскроя Фу (j Е 1..п); A3, группы движений G, определяющей размещение предметов на объектах; А4. схемы построения возможных (допустимых) способов размещения; А5. цели задачи — КЭ при выборе способа размещения; А6. дополнительных требований к решению задачи.
Исследование объектов и предметов раскроя, способов их размещения, КЭ позволяет точнее сформулировать содержание данных задач, упорядочить и классифицировать их по определенным признакам. Известный способ классификации моделей раскроя и упаковки Н. Dickhoff [193], часто используемый многими авторами [14, 138, 140, 141], не всегда отражает особенности рассматриваемых прикладных задач, в частности — связи между объектами и предметами раскроя и дополнительные ограничения технологического характера.
Несмотря на то, что задача раскроя не обязательно предполагает физическое деление некоторых фигур на части, ее логично связать с определенными геометрическими объектами.
При этом, независимо от реальной формы и физических характеристик этих объектов, следуя технологии производственного процесса, в математической модели могут рассматриваться один, два или три размера объектов и предметов раскроя (длина, ширина и высота). Сложность и метод решения полученной задачи во многом определяются учитываемой размерностью объекта раскроя, который может соответствовать отрезку (одномерный предмет), плоской (ограниченной или нет) фигуре или объемному телу. Размерность фигур: объектов и предметов раскроя — должна быть одинакова и является важнейшим признаком классификации задач раскроя В1—ВЗ.
Важны формы объектов и предметов раскроя. В задачах планирования раскроев в рассматриваемых отраслях промышленности, характерны фигуры, обладающие определенной симметрией: прямоугольники и круги, параллелепипеды и цилиндры. Их математическая характеристика: связанные и замкнутые, измеримые, чаще всего — выпуклые множества точек с непустой внутренностью. Каждой фигуре Ф можно сопоставить численное значение д(Ф) — меру, в зависимости от размерности задачи: длину, площадь или объем. В одномерном случае требование связности исключает предметы раскроя, отличные от отрезка прямой, поэтому такие раскрои называют линейными. Гораздо больше возможностей в двухмерном — плоском и трехмерном — объемном, пространственном случаях.
Размеры фигур могут быть фиксированными, переменными или условно-бесконечными. К примеру, прямоугольник обычно характеризуется длиной и шириной, хотя при расчете диаметра съема тамбура бумагоделательной машины (БДМ) длина намотанного на него бумажного полотна — неизвестная, переменная величина. При производстве изделий из гофрокартона (ГК) предметы раскроя — прямоугольники заданных размеров, а объект раскроя, полотно — полоса, длину которой можно считать бесконечной. В задаче наиболее плотной укладки объектом раскроя может быть вся плоскость или трехмерное пространство. Практический интерес к подобным задачам связан с построением приближенных решений или оценкой их точности.
Размеры плоской или пространственной фигуры соответствуют ее определенным осям. Технология раскроя обычно связана с определенной ориентацией этих осей в некоторой системе координат. Размерность, форма, характеристика размеров фигур и ориентация ее осей задают тип объекта или предмета раскроя. Конкретный геометрический объект определяется его типом и набором числовых па 22 раметров: углов, размеров, пропорций и пр., выбор которых дополняет тип до типоразмера. Типоразмер объекта установлен, если заданы все его параметры, и он характеризует множество конгруэнтных геометрических фигур на прямой, плоскости или в пространстве. Необходимо отметить, что перечень параметров предмета раскроя не ограничивается описанием его геометрических свойств. В математической модели могут использоваться другие числовые характеристики: физические свойства (плотность, вес), экономические показатели (рентабельность продукции, возможный доход от ее продажи). 2. Рассматриваются следующие варианты задачи раскроя: 81. Единственного объекта Ф; 82. Заданного количества объектов одного типоразмера Ф; 83. Неизвестного количества объектов одного типоразмера Ф; 84. Объектов некоторого множества типоразмеров Фг- (г Є М = l..m). Количество экземпляров объектов каждого вида может быть известным, произвольным или определяться границами. Математическая модель и метод решения задачи раскроя существенно зависят от номера варианта и каждый из них сложнее предшествующих, поскольку является их обобщением. Кроме того, увеличивается возможность выбора функции цели. Раскрой единственного объекта можно представить как последовательный процесс выкраивания предметов или деления этого объекта на части, из которых в дальнейшем будут получены заготовки. Выделим такие задачи, назвав их задачами построения оптимального плана раскроя. Моделирование последовательным процессом составляет основу эффективного метода ДП решения этих задач.
Генерация столбцов в задачах раскроя и комплектовки
Задачи поиска комбинаций планов раскроя, сочетание которых обеспечивает все необходимые предметы в количествах, заданных точно или границами, особенно характерны для систем планирования и управления предприятями ЦБП и других отраслей промышленности, о чем свидетельствуют следующие примеры: 1) В задаче планирования раскроев и распределения заявок между БДМ объектами раскроя являются съемы тамбуров продукции, а предметами — форматы продукции. Производительность каждой БДМ и выработка в течение периода планирования считаются ограниченными, также, как и потребность в каждом из форматов. Требуется подобрать планы раскроя, которые обеспечат выпуск заданного ассортимента и объемов продукции с минимальными отходами. В классическом варианте задачи рассматриваются однотипные БДМ, в стандартном — неодинаковые по длине тамбура и другим характеристикам. Общий вариант предусматривает управление скоростью работы БДМ и плотностью бумаги с учетом качества продукции. . 2) Задача становится сложнее, если учесть, что рулон бумаги или картона кроме формата характеризуется диаметром. В этом случае объект раскроя — прямоугольник, ширина которого равна длине тамбура. Длина этого прямоугольника X ограничена снизу и сверху, пропорциональна объему продукции и определяется моментом съема тамбура. Предметам соответствуют прямоугольники, ширина аг- ка 38 ждого из которых определяется форматом продукции, а длина 6,- — диаметром рулона. Задача сводится к поиску длины прямоугольника, который кроится на полосы, составляющие величину, близкую к размеру тамбура, но не большую его, а длина, по возможности, близка к величине, кратной длинам присутствующих в раскрое форматов. .3) В задаче планирования выпуска продукции цеха ГТ предметы раскроя — прямоугольные заготовки деталей тарных ящиков или листы ГК, вырабатываемые ГА. Цель задачи — выработка необходимой продукции с наименьшим расходом материала. Суммарная площадь требуемых изделий постоянна и экономия обеспечивается только за счет сокращения производственных потерь. 4) Трехмерная задача размещения грузов возникает при составлении планов погрузки в ТС (контейнеры, вагоны, трюмы теплоходов) продукции бумажного производства. Объектом раскроя является пространство внутри ТС, которое в случае контейнера имеет форму параллелепипеда, вагона — закругленной сверху фигуры, трюма теплохода — многогранной невыпуклой области. Единицей продукции бумажного производства обычно является параллелепипед (кипа бумаги, картона или листовой целлюлозы, упаковка сложенных ящиков или мешков) или круговой цилиндр (рулон бумаги или картона). Задачу усложняют многочисленные ограничения технологического характера, включая жесткость конструкции, условия погрузки и крепления последних единиц, балансировку груза, обеспечение удобства разгрузки. В отличие от предыдущих, объекты раскроя в этой задаче дискретны. 5) К числу трехмерных задач раскроя можно отнести также задачу формирования поддонов, на которые слоями укладывают пачки листов или сложенных ящиков. Прочность конструкции обеспечивается чередованием слоев, связывающих пачки подобно кирпичной кладке. Слои могут несколько выходить за пределы площади поддона, иметь внутренние пустоты и неодинаковые размеры. Размеры кипы опреде 39 ляются наибольшими размерами слоев. Цель задачи — поиск укладки наибольшей объемной плотности. Структура слоя необязательно соответствует гильотинному раскрою. 6) В задаче компоновки ячеек на, складе готовой продукции требуется не только плотно разместить запланированную номенклатуру единиц продукции, но и обеспечить требуемую очередность доступа к каждой из них. 7) Современные системы управления качеством обеспечивают непрерывный продольный и поперечный контроль параметров полотна Б ДМ или картоноделательной машины (К ДМ), что позволяет рассматривать более сложную задачу распределения форматов вдоль ширины тамбура, а накатов — рулонов конечной продукции с повышенным требованием качества — по длине полотна. Эта задача, вследствие неоднородности объекта раскроя, находится несколько в стороне от рассматривемого класса задач, однако заслуживает внимания ввиду очевидного экономического эффекта. Бе решение не сложно в отличие от реализации расчетов: перенастройки продольно-резательных машин, организации упаковки, складирования и учета.продукции. 8) Несмотря на большое количество имеющихся программных комплексов, остается актуальной проблема выбора планов раскоя круглой древесины, обеспечивающих требуемые ассортимент и количество пиломатериалов. Выработка продукции ведется параллельно с сортировкой древесины, что создает проблему неопределенности имеющегося количества пиловочника. Перечислим некоторые из рассматриваемых в диссертации задачи комплектовки материалов. 9) В главе 5 рассматривается задача оптимального выбора ком плекта оборудования, которое может выполнять одну или несколько последовательных операций, определения режимов их работы и специ ализации. Цель этой задачи — комплектовка необходимых произвол 40 ственных мощностей с наименьшими затратами на приобретение или эксплуатацию оборудования. 10) К задачам комплектовки относится также проблема обеспечения сырьем лесопромышленного предприятия, которая включает задачу распределения оборудования и очередности освоения лесосырьевых баз. Предметы и объекты комплектовки при этом неоднородны ввиду возможных различий технологий оборудования или породо-возрастного состава лесного фонда лесосырьевых баз.
Использование модели в условиях стохастики производственного процесса
В прикладных задачах, наряду с линейными, появляются нелинейные функции и соотношения, а области допустимых значений переменных могут быть невыпуклыми или разрывными. Главными источниками дискретности в рассматриваемых в диссертации математических моделях, близких к задаче ЛП (2.4.1-3), являются: D1. Целочисленность или дискретность всех или части переменных задачи; D2. Разрывность области определения переменной, которая может принимать значениие, равное нулю или ограниченное снизу и сверху положительными числами; D3. Неоднородность — разрывность в нуле слагаемого 4 J{XJ) в формуле (2.2.1); D4. Дополнительные требования к множеству N переменных, которые могут принимать ненулевое значение, к примеру, \N \ к. Решение задачи рассматриваемого класса обычно начинают с решения задачи ЛП, полученной из исходной исключением условий дискретности, в надежде получить полезную информцию об оптимальном решении исходной и некоторые оценки столбцов и строк матрицы А.
В случае дискретности [Dl, D2] иногда достаточно решить задачу ЛП. Например, при планировании работы цеха ГТ (раздел 4.2), вполне достаточно округлить объемы выработки до ближайщего десятка, поскольку условия планирования не требуют большей точности.
Обобщением идеи округления является предложенный и активно используемый автором [30, 25, 25] метод агрегации управляемых факторов, суть которого — объединение близких по своей структуре столбцов А дискретных переменных в группы и решение задачи ЛП относительно таких групповых переменных с последующим распределением полученного «агрегированного» плана посредством вторичных задач распределения внутри группы. Метод позволяет получить бли-кие к оптимальному решения, если размерность задачи оптимизации достаточно велика.
Так бывает не всегда. В задачах планирования раскроев бумаги (раздел 4.1) и погрузки продукции (4.3) округление оптимального плана задачи ЛП чаще всего не приводит к приемлемому решению задачи. Своеобразная форма округления, характерная для методов отсева (см. [135, 168]), позволяет находить приближенное решение задачи с дискретностью [D3], однако в оставшихся случаях это удается редко. Для решения таких задач приходится применять переборные алгоритмы.
Отсутствие теории двойственности ДП, необходимой для организации эффективных алгоритмов решения задач этого класса в общем виде, является причиной появления множества разнообразных приемов и методов их решения. Изложение этих методов представлено в обзорных работах [83, 75, 168, 194, 195] и многих других публикациях.
Следуя работе [195], отметим, что большая часть идей и методов решения задач ДП основаны на дроблении и ослаблении исходной. Эти понятия позволяют сформулировать понятие задачи ДП в виде, наиболее удобном для описания и классификации алгоритмов. Задачу Р минимизации функционала fp(x) —У min на множестве х Є Гір назовем элементарной, если ее решение занимает приемлемое время. Сложность решения элементарной задачи является линейной (задача поиска), квадратичной («жадные» алгоритмы) или кубической (разумная реализация симплексного метода) по отношению к ее размерности (количеству переменных и ограничений). Введем понятие разбиения условной задачи оптимизации. Задачи оптимизации Pi, Р2, . -., Pfc вида: назовем разбиением P на множество частичных задач (подзадач), если fip = U?ei..fc g и fq = fp\o,pq- 0,q — множества решений задач Pq образуют разбиение множества Clp, а функционалы fq — являются сужениями /р на соответствующие подмножества. Примерами служат задачи СЦЛП и ЦЛП как общего вида, так и специальной структуры, задачи с невыпуклой целевой функцией или разрывными множествами допустимых значений переменных. Задачи дискретного программирования характеризуются возможностью разбиения на конечное множество элементарных. Практически все точные методы решения задач ДП основаны на сочетании какой-либо формы перебора частичных вплоть до элементарных задач с ведением рекорда — лучшего среди найденных решений и ослаблении задачи, замены ее более простой, дающей информацию о решении исходной. Задачу Рд : /Рд —У min при условиях х Є lpR назовем ослат блением задачи Рд, если fPR(x) fp{x) для каждого х Є ІЇР и Qp С ПРд. Стандартные способы ослабления задач с дискретностью [bf D1-D2] — исключение условия целочисленности, отказ или замена части ограничений их выпуклой комбинацией, задач с невыпуклой целевой функцией — замена целевой функции наименьшей выпуклой, не превосходящей ее, задач с невыпуклой областью Qp — замена ее выпуклой оболочкой.
Задача выбора транспортных средств и размещения продукции
Учитывая массовость производства и практически неизбежные производственные потери точно непредсказуемого объема, необходимо первоначально решить задачу ЛП (3.2.1-11) без условия целочислен-ности, достраивая методом ветвей и границ с использованием метода уточнения оцнок полученное решение до приближенного решения (3.2.1-12). Это не всегда достигается простым округлением оптимальных значений базисных переменных.
При решении задачи ЛП (3.2.1-12), следует учитывать: 1) Количество ограничений задачи Р, как правило, не превосходит несколько сотен, что позволяет использовать стандартные алгоритмы для ее решения, например, мультипликативный симплексный метод со сжатием столбцов (см. раздел 2.2, [156]). Верхние и нижние границы переменных задачи и линейных форм условий, во избежание роста размерности, лучше учитывать алгоритмически, за счет некоторого усложнения реализации симплексного метода [115]. 2) Множество столбцов матрицы ограничений задачи Р состоит из двух частей. Столбцы раскроев iV1, составляющит блоки задачи. Эти столбцы Aj[M] переменных (XJ j Є iV1), расширенные коэффициентами ограничений aij ограничений (3.3.5), характеризуют задачи рассматриваемого класса. Все остальные — вспомогательные столбцы составляют множество N2. 3) Множество основных столбцов iV1 очень велико. Однако, поскольку вспомогательная информация ац либо содержит одинаковые значения для всех столбцов Щ (чаще всего, единицы) в строках баланса производительности оборудования, либо числа, пропорциональные количествам или весовым коэффициентам объектов раскроя, для проверки оптимальности этой части матрицы можно использовать метод генерации столбцов. Проверка оптимальности столбцов этой части матрицы для текущего плана основана на решении задач поиска оптимального плана раскроя. 4) Количество вспомогательных переменных обычно сравнительно мало, что позволяет проверять условие оптимальности для столбцов этой части матрицы их полным просмотром. Еще предпочтительнее использовать эффективный метод барьера (см. [156, 125]). 5) В случае линейной задачи раскроя размеры объектов и предметов раскроя редко различаются более, чем на порядок, что позволяет эффективно использовать «метод скачков». 6) Эффективность метода скачков существенно зависит от порядка слияния списков. Поэтому перед решением задачи линейного раскроя элементы множества М\. лучше упорядочить по убыванию отношения двойственной оценки к длине предмета раскроя. 7) При наличии памяти сливаемые списки целесобразно хранить и пересчитывать по мере надобности, используя ранее найденное решение задачи линейного раскроя. 8) Блочность прикладных задач рассматриваемого класса, как правило, достаточно велика. Однако при выполнении очередной итерации алгоритма можно решать лишь часть вспомогательных задач раскроя и использовать представленный в главе 2 метод формирования списка перспективных столбцов. При его формировании не требуется решение задач Lk к Є К, для которых: двойственные переменные столбцов множества Mk после пересчета базисного плана не меняются; изменения соответствующих двойственных переменных достаточно малы (см. [173]); при решении предшествующих задач раскроя найден подходящий для ввода в базис столбец. 9) Варьируя веса дополнительных или искусственных переменных, необходимых для построения начального базисного плана, удается установить: — очередность учета ограничений исходной задачи в случае отсутствия ее допустимого решения (искусственные переменные); — предпочтительность нижней и верхней границ в значениях двустронне ограниченных переменных или линейных форм (дополнительные переменные). Эти приемы используются для перехода от решения задачи ЛП Рд к решению исходной задачи Р. Основная проблема решения задачи Р в общем виде — обеспечение дискретности требуемых наборов переменных. Там, где пренебречь ею невозможно, для получения приближенного решения применяется метод уточнения оценок дискретной задачи (см. главу 2) как средство усиления метода ветвей и границ в совокупности с округлением значений, близких к допустимому. Высокая эффективность алгоритма решения Р необходима, поскольку эта задача является вспомогательной и многократно используется при составлении рассматриваемого далее ОКП. Задача планирования раскроев сводится к выбору TV С TV — оптимального множества планов раскроя и расчету # [TV ] — объемов реализации этих планов (считается, что [TV\ TV ] = 0) без указания очередности или сроков реализации раскроев TV и относится к классу задач ОП.
