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

На правах рукописи

СОШКИН РОМАН ВЛАДИМИРОВИЧ

ЗАДАЧИ ОПТИМАЛЬНОГО РАСКРОЯ ГОФРОПОЛОТНА И МЕТОДЫ ИХ РЕШЕНИЯ

Специальность:

05.13.18 — математическое моделирование, численные методы и комплексы программ.

АВТОРЕФЕРАТ ' диссертации на соискание ученой степени кандидата технических наук

Петрозаводск—2009

003471594

Работа выполнена в государственном образовательном учреждении высшего профессионального образования ПЕТРОЗАВОДСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Научный руководитель: доктор технических наук,

профессор Кузнецов Владимир Алексеевич.

Официальные оппоненты: доктор технических наук,

профессор Колесников Геннадий Николаева

кандидат физико-математических наук, доцент Печников Андрей Анатольевич.

Ведущая организация: Санкт-Петербургский государственный технс

логический университет растительных пол! меров.

Защита диссертации состоится «

. 2009 года в........часов

на заседании Диссертационного Совета Д 212.190.03 при Петрозаводском государственном университете по адресу: 185910, г. Петрозаводск, пр. Ленина, д.ЗЗ

С диссертацией можно ознакомиться в научной библиотеке Петрозаводского государственного университета.

Автореферат разослан . .. 2009 года.

Ученый секретарь

.у ченыи секретарь - л?^ ^ диссертационного совета --В.В. Поляков

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ.

Актуальность темы исследования

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

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

С другой стороны, модернизация промышленного производства России, расширение ассортимента выпускаемых товаров и появление большого количества малых предприятий приводят к существенному повышению номенклатуры востребованной упаковки, а, как следствие, — усложнению процесса планирования и управления ее производством. Действительно, если в 1980 году недельный план ОАО «Архангельский ЦБК» включал 10-12 изделий (из них до 60 % составляли стандартные ящики для упаковки рыбы), то в 1990 году — 20-25 (причем доля ящиков для упаковки рыбы снизилась до 35 % ), в 1995 году это количество возросло до 60-80, в 2000 году — до 120, а в настоящее время составляет 150-180 видов изделий. Аналогичная ситуация наблюдается и на других целлюлозно-бумажных комбинатах (ЦБК) и производствах бумажной и картонной тары.

Существенно расширяется и ассортимент сырья. Если гофрокартон-ное производство ОАО «Архангельский ЦБК» в 1980 выпускало изделия из одного материала (бурый трехслойный гофрокартон), то в 2000 году — четыре вида, а Киевский картоннсъбумажный комбинат в настоящее время использует более 100 видов различного исходного материала. Возрастают требования заказчиков к форме и качеству продукции (прочности, точности соединения клапанов, виду внешних слоев, полиграфии, срочности изготовления и пр.).

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

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

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

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

Разработка АСУ на основе решения данной задачи позволяет получить реальный экономический эффект в форме снижения отходов на 15-25%, повысить оперативность и качество планирования и управления производственными процессами, сократить расход сырья, снизить себестоимость продукции и, в конечном счете, принести значительный экономический эффект.

Цель диссертационной работы

Основная цель диссертационной работы — повышение эффективности планирования и управления производством гофрокартона и упаковки посредством разработки математических моделей и методов для создания АСУ планирования и управления раскроем гофрополотна.

Для достижения поставленной цели были сформулированы следующие задачи:

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

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

3. Исследовать математические задачи, полученные на основании расширенной модели.

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

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

Объект исследования

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

Предметом исследования являются математические модели и методы решения задач раскроя гофрополотна.

Научная новизна

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

Представлены принципы классификации исследуемых моделей.

К результатам исследования, обладающих научной новизной и выносимых на защиту, относятся следующие:

• Сформулированы и исследованы задачи оптимизации для моделирования процессов раскроя гофрополотна.

• Предложены и исследуются различные методы решения задач линейного программирования с ограниченным количеством базисных переменных (далее ЛП с ОКБП).

• Разработаны эффективные методы и алгоритмы решения задач оптимизации планирования раскроев гофрополотна.

• Предложен метод расчета оценок потерь материала в случае вырожденности или при отсутствии допустимых решений задачи.

Автором разработаны и выносятся на защиту следующие результаты:

1. Выполнена постановка и исследование задач оптимизации моделирования процессов раскроя гофрополотна.

2. Предложены методы решения этих задач.

3. Сформулирован класс задач ЛП с ограниченным количеством базисных переменных.

4. Разработаны методы решения задач ЛП с ОКБП. Дана классификация этих методов.

5. Все перечисленные методы реализованы в виде комплексов программных средств, используемых при разработке и создании АСУ планирования раскроев гофрополотна (далее ГП), внедренных на ряде промышленных предприятий.

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

Практическая значимость и реализация результатов работы

Полученные в диссертации результаты использовались при выполнении хоздоговорных научно-исследовательских работ кафедры прикладной математики и кибернетики и Центра ПетрГУ-Метсо систем автоматизации Петрозаводского государственного университета в 2002-2008 годах при личном участии автора.

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

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

1. ОАО «Архангельский ЦБК», г. Новодвинск.

2. Филиал ОАО «Архбум»в г. Подольске.

3. ОАО «Киевский картонно-бумажный комбинат», г. Обухов.

4. ООО «Гранит», г. Павловский Посад.

5. ООО «Ярославский картон», г. Ярославль.

6. ООО «Вереск-1», г. Архангельск, г. Гатчина.

7. ЗАОр «Народное предприятие Набережночелнинский картонно-бумажный комбинат», г. Набережные Челны.

8. ОАО «БумСнаб», г. Нижний Новгород.

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

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

Методика исследований

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

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

Для разработки алгоритмов и программных комплексов использовались современные технологии проектирования программных систем

и баз данных, методы структурного h объектно-ориентированного программирования. Для разработки использовались системы программирования Borland Delphi 4 - 7 и Microsoft Visual Studio .NET 2003, 2005, для проектирования баз данных использовались Paradox и Microsoft SQL Server 2000, 2005.

Апробация работы

Основные результаты диссертационной работы докладывались автором на V-VIII Международных научно-технических конференциях «Новые информационные технологии в ЦБП и энергетике» (Петрозаводск, 2002, 2004, 2006, 2008), на Международной школе-конференции по приоритетным направлениям развития науки и техники с участием молодых ученых, аспирантов и студентов (Ялта, Украина, 2006), на конференциях и семинарах ПетрГУ. На Всероссийском конкурсе инновационных проектов аспирантов и студентов по приоритетному направлению развития науки и техники «Информационно-телекоммуникационные системы» (Московская область, 2005) получен диплом первой степени.

На автоматизированную систему «Управление гофропроизводством» получено свидетельство об отраслевой регистрации разработки №6502 в ФГНУ «Государственный координационный центр информационных технологий, отраслевой фонд алгоритмов и программ».

Публикации

Основные результаты диссертационной работы опубликованы в 12 печатных работах, в том числе три в журналах, реферируемых ВАК.

Структура и объем работы

Диссертация состоит из введения, 4 глав основного материала, заключения, библиографического списка и 1 приложения. Основной материал изложен на 118 стр., включая 5 рисунков и 2 таблицы. Библиографический список включает 87 наименований.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность темы диссертации, указаны цель и задачи исследования, обсуждены научная новизна и практическая значимость работы.

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

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

Для построения расширенной модели используются следующие обозначения:

М — множество индексов заготовок для заказов (далее всегда г € М);

Мо — множество индексов заготовок для заказов, для которых разрешен поворот (Мо С М);

г' — индекс заготовки, которая получается из заготовки с индексом г е Мо путем поворота на 90°;

\¥1(Шц — ширина заготовки для заказа г € М (измеряется в мм.);

Вепйвг — количество рилевок заготовки для заказа г £ М;

Рг — флаг необходимости дальнейшей переработки заготовки для заказа г е М;

Ы — объем заготовок на складе по заказу г 6 М (измеряется в м2);

N — множество индексов раскроев (далее всегда ] 6 Лг);

X] — планируемая выработка гофрополотна в м2 в соответствии с раскроем з & N (объем выработки раскроя);

С — множество индексов гофроагрегатов (далее всегда с £ С);

1¥с — множество допустимых различных форматов полотна на гоф-роагрегате с € С;

ДГС — множество индексов раскроев допустимых для выпуска на гоф-роагрегате с & С (Мс С Дг);

ЛГ4 — множество индексов раскроев допустимых для выпуска с использованием формата £ € \¥с (Л^ С 7\ГС С N);

— нормативы выработки заготовок для заказов г € М при раскрое единицы площади гофрополотна по схеме ] 6 ./V;

А^ — количество заготовок для заказов г € М в составе раскроя по схеме ; б

Ь] — доля потерь материала при раскрое по схеме j € ДГ;

БС] — количество «необрезных» заготовок в раскрое ] 6 N1

Кпс — количество продольных ножей гофроагрегата с £ С;

КпВс — количество продольных рилевочных ножей гофроагрегата с € С;

с1С, 13с — минимальная и максимальная возможная производительность гофроагрегата с £ С в течение планируемого промежутка времени (в м2);

Ьг — ширина полотна формата t € (измеряется в мм.);

— минимально необходимая кромка для отреза с каждой стороны полотна формата Ьг (измеряется в мм.);

— максимально разрешенная кромка для отреза с каждой стороны полотна формата (измеряется в мм.);

дс^ € {0,1} — флаг выполнения раскроя j с использованием формата £ гофроагрегата с;

(3 — множество индексов готовых изделий: комплектов картонных ящиков и изделия не входящие в комплекты (далее всегда д £

Мц СМ — множество заготовок в составе комплекта ящика д (Е (2;

К{д — кратность числа предметов с индексом г е Мч в комплекте

д е <?;

Ьд, ВЧ ~ нижняя и верхняя границы требуемого количества в м2 комплекта д € <3-

Уд — планируемый объем производства комплекта д € (в м2);

V — минимальный допустимый для кроя объем раскроя (в м2);

К — максимально разрешенное количество раскроев в оптимальном плане.

В терминах введенных обозначений расширенная модель приобретает следующий вид:

^ тш (1)

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

]Г(Ац + Аез) Хз = учк1я-Ы, ¿еМ,ПМ0, д е <3 , (2)

№

X] Ач хэ = Уч - > ге Мд\ М0, д€С} (3)

— ограничения на объемы выпуска заготовок с учетом комплектности: (2) — заготовки, для которых не важно направление гофры, (3)

— остальные заготовки.

Ьд < Уд <ВЧ, яе<3 (4)

— ограничение на выработку комплектов.

Ьг-2 < 53 < , с € С, í € ] 6 Щ , (5)

¿ем

Л^. < Хпс, з е с € С , (6)

¿€М

Л-_, • Всш1.чг < КпВс , ] е Л^, с е С (7)

г€Л/

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

¿с < Ц 9сц X] < £>с , сеС (8)

— учет производительности гофроагрегатов.

х^- е 0 и [V, оо) , (9)

— ограничение на объемы выпуска каждого из раскроев.

53 вгдп&э) < К (10)

зеи

— условие на допустимое количество раскроев в оптимальном плане.

53 згдп(А^) р{ < 1 , з е ЛГ (11)

¿ел/

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

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

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

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

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

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

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

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

1. Задачи ЛП с ограниченным количеством базисных переменных.

Чтобы сформулировать задачу ЛП с ограниченным количеством базисных переменных в общем виде, рассмотрим задачу ЛП Р формирования оптимального плана раскроев с множеством М = 1..тп ограничений,

N = l..n переменных, матрицей А (тп х п) ограничений и векторами b > О, с > 0 и х соответствующей размерности

Р: сх —> min; Ax>b; х>0. (12)

Следуя содержанию задачи, коэффициенты матрицы Aij > 0, следовательно, можно ограничиться случаем bj > 0 для каждого г 6 М. Будем также считать, что ограничения задачи (12) совместны, х* — ее оптимальное решение, z* = сх* — оптимальное значение целевой функции. Будем считать, что матрица ограничений этой задачи невырождена и имеет полный ранг. Каноническая форма этой задачи такова:

сх + Оу—*тгп; Ах — Еу = Ь; х, у > 0. (13)

Множество переменных задачи (12) составляет N = N+M, базисных переменных N' с N, где |jV'| = тп. Среди переменных множества присутствуют как переменные основной задачи Nx С N (основные базисные столбцы), так и орты Ny С М (дополнительные базисные столбцы), N' — Nx + Ny. В силу предположения о невырожденности всех базисных решений задачи y[N'y\ > О для любого базисного множества N'. Важная особенность — целевая функция рассматриваемой задачи обязательно ограничена снизу.

Цель данного исследования — поиск оптимального плана (х*, у*) этой задачи с дополнительным условием

\N'X. \<k<m, (14)

которому соответствует оптимальное значение целевой функции Полученную задачу обозначим Р^ и будем называть задачей ЛП с ограниченным количеством базисных переменных основной матрицы. Задачу (12) или (13) будем называть базовой по отношению к данной задаче ОКБП, число к — рангом базиса задачи. Следует оговорить некоторую условность в названии класса рассматриваемых задач — ранг матрицы определяет лишь |ЛГХ| — количество основных столбцов матрицы ограничений, общее количество базисных переменных (основных столбцов N'x и Ny), разумеется, всегда составляет т.

Отметим, что если \N'X. | < к, то решение 1\ совпадает с решением Р. Сложности возникают в случае | N'x. | > к, который рассматривается в соответствующем разделе диссертации.

2. Методы решения задач ОКБП.

Отметим некоторые особенности рассматриваемой задачи.

• В основе рассматриваемой задачи понятие базисного плана задачи ЛП, что фактически исключает возможность ее решения без использования средств линейной алгебры и линейного программирования. С другой стороны, исследование базисных решений этой задачи привносит в ее содержание элемент дискретности (количество базисных множеств не превосходит который можно использовать для организации алгоритмов частичного перебора. Обозначим Pjv> задачу ЛП, множество основных базисных столбцов которой содержится в N', zn> — оптимальное значение целевой функции этой задачи.

• Для любой задачи ЛП (12) или (13) имеется целое ко, такое, что рассматриваемая задача имеет допустимое решение только для к > ко. Таким образом, необходимо рассматривать подмножества Nx С N для которых ко < |iVx| < к, что принципиально противоречит концепции независимого множества матроида. В связи с этим необходима определенная, представленная далее, корректировка условий этой задачи.

Дополнив условия исходной задачи (12) требованием ограничения количества базисных (ненулевых) переменных решения этой задачи не более некоторого установленного значения к, получим задачу Рд.. Оптимальное решение этой задачи обозначим х^.

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

Обозначим М = {N, J) однородный матроид ранга к, множество элементов которого N, а семейство независимых множеств J = { А £

\\А\ < к} определяет допустимые множества Nx. Множество баз данного матроида В составляют fc-элементные подмножества N, множество циклов — (к + 1)-элементные подмножества.

Введем также двойственный матроид по отношению к рассматриваемому М' = (JV, J') с семейством независимых множеств J' = {А 6 2n ||Л| > к}. Независимые множества двойственного матроида (кроме баз) соответствуют недопустимым решениям задачи.

Множество баз В каждого из этих матроидов составляют fc-элементные подмножества N. Матроидная структура накладывается на

множество допустимых решений задачи (13) с дополнительным условием (14).

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

Gw + cx + Oy —» min-, bw + Ax-Ey ~Ь\ w > 0; х, у > О, < к, (15)

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

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

Установлено, что любая задача ОКБП (13 — 14), которая имеет допустимое (и оптимальное решение), обязательно имеет оптимальное решение, которое является базисным для задачи ЛП (12). Это позволяет ограничиться рассмотрением конечного множества базисных допустимых решений задачи (12) и, в конечном итоге, использовать структуру матроидов.

Теорема 1 устанавливает связь задачи ОКБП с некоторой специально построенной задачей о покрытии, что указывает на NP сложность рассматриваемой задачи.

Теорема 2 показывает, что оптимальное решение задачи (13 — 14) эквивалентно решению задачи (15) для некоторого значения параметра G и устанавливает его оценку.

Теорема 3 устанавливает свойства целевой функции задачи (12) в случае фиксации значения одной из ее переменных и является основой для вывода в Теореме 4 свойства супермодулярности целевой функции лдг» как функции от множества столбцов базисных переменных, что и является обоснованием представленных далее алгоритмов решения задачи ОКБП.

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

В рамках исследования все алгоритмы решения задачи Р являются:

• Прямыми или двойственными — в зависимости от матроида, в состав независимых множеств которого входит текущий пробный план.

• Точными или приближенными (более конкретно, переборными или жадными) методами.

В диссертации предложены следующие алгоритмы решения задач ЛП с ОКБП:

• Прямые переборные алгоритмы:

— последовательный анализ независимых множеств (алгоритм

А1);

— последовательный анализ баз матроида (А2);

— перебор дополнений циклов двойственного матроида (АЗ).

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

• Прямые приближенные алгоритмы:

— приближенный алгоритм (А4),

— жадный прямой алгоритм (А5).

На практике хороший результат показывает приближенный, не гарантирующий оптимальность полученного плана, алгоритм А4, аналогичный А2. На предварительном этапе этого алгоритма решением задачи (13) находится базисное решение М* = ТУ* + ТУ*, а в процессе перебора множество ТУ заменяется на существенно меньшее ТУ* С ТУ. Алгоритм А5 по своей сути, является незаконченным решением определенной разновидности симплексного метода. Специальным образом формируется базисное множество, далее следует выполнить определенное количество итераций симплексного метода, останавливаясь, (а) — по мере завершения работы симплексного метода, или (б) — как только на следующем шаге |ТУ£| должно превысить к.

• Двойственные алгоритмы:

— алгоритм последовательного отсева (01),

— метод фронтального перебора (D2),

— начальный шаг субоптнмалыюго алгоритма (D3).

Двойственными алгоритмами назовем методы, в которых базисные множества столбцов Nx пробных планов являются независимыми множествами двойственного однородного магроида ранга и — к.

Если при исследовании прямых алгоритмов основой перебора является Nx = 0, то за основу двойственных логично принять Nx = N* — оптимальное решение задачи (12) без ОКБП. В алгоритме D1 после решения задачи (12) происходит последовательное исключение из базисного плана переменных с наихудшими оценками до тех пор, пока в плане не останется к переменных х.

Наиболее удачным при практическом использовании оказался алгоритм D3.

3. Методы решения других задач оптимизации, основанные на использовании матроидов.

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

1. Задача ОКБП по критерию наименьшего суммарного перевыполнения заданий:

Y^Vi-* min •

гем

2. Задача ОКБП с ограниченным суммарным перевыполнением заданий:

ieM

3. Задача ОКБП с ограничениями размеров перевыполнения заданий:

0<Di<di, i€ М.

4. Задача ОКБП по критерию наименьшего суммарного взвешенного перевыполнения заданий:

°гУг min .

¿ем

5. Минимаксная задача ОКБП:

max{yj | г £ М} —> min.

6. Задача ОКБП с комбинированным критерием, например:

^Р Cj-Xj + ^ —i- min je./V ¿ем

и произвольным дополнительным набором ограничений.

7. Задача ОКБП с критериями эффективности и ограничениями, подобными представленным, для некоторого подмножества М' С М дополнительных переменных.

Все перечисленные задачи могут иметь практическое приложение. Поскольку все эти задачи без условия ОКБП сводятся к линейным задачам, представленная в диссертации теория может быть применена и к этим задачам.

4. Методы расчета оценок потерь материала.

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

Эти оценки важны в следующих случаях.

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

2. При оценке себестоимости изделия в зависимости от срочности его изготовления.

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

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

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

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

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

Ъ=Ъ-еЪйея,

где € > 0 — достаточно малое положительное число, а Ъ'1ед — характеристический вектор вырожденных компонент базисного плана Ь^3 — 1, если х* = 0 и Ь^ед = 0, если х* > О для каждого г € Аг*. Возмущение правых частей приводит к смещению оптимального решения из вырожденной точки.

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

6=6 -10*,

где го* — величина невыведенной искусственной переменной исходной задачи ЛП.

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

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

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

2. Модуль регистрации технологических карт и характеристик оборудования.

3. Модуль многодневного объемного планирования.

4. Модуль оперативного планирования работы технологических линий.

5. Модуль оперативного планирования работы гофроагрегатов.

6. Модуль учета выработки производства.

Внедрение системы планирования позволило получить следующие результаты.

1. Сокращение объема расходования материала, идущего в отходы, за счет поиска более рациональных схем раскроя гофрополотна на 15-25%.

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

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

4. Значительное снижение количества ошибок, возникающих при ручном вводе данных. Вручную заносятся только исходные данные по заказам, планы работы рассчитываются автоматически. Как следствие, примерно на 80% сокращается количество ошибок, связанных с устаревшими данными в технологических картах или ручным вводом планов раскроя.

5. Сокращение времени, затрачиваемого на составление планов различных горизонтов времени. Например, составление трехдневного плана работы линий переработки сокращается в среднем с 5 часов до 1 часа.

6. Появилась возможность оперативного пересчета планов в условиях динамически меняющегося списка заказов.

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

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

2. Выявлены некоторые важные классы прикладных нелинейных задач, связанных с производством гофрокартона.

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

4. Установлена возможность использования представленных в диссертации алгоритмов для решения ряда других задач.

5. Все перечисленные методы реализованы в виде комплексов программных средств, используемых при разработке и создании АСУ планирования раскроев гофрополотна.

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

В приложении содержится копия свидетельства о регистрации разработки и акты о внедрении автоматизированной системы управления на: ОАО «Архангельский ЦБК», филиал ОАО «Архбум»в г. Подольске, ЗА-Ор «Народное предприятие Набережночелнинский картонно-бумажный комбинат».

Основные результаты диссертации опубликованы в следующих работах:

1. Сошкин Р.В. Математические модели и алгоритмы решения задач оптимального раскроя полосы / Р.В. Сошкин // Вестник Поморского университета. Сер. Естественные науки. — 2009. — №1. — С.77-82.

2. Сошкин Р.В. Некоторые прикладные задачи раскроя и методы их решения / Р.В. Сошкин // Известия ОрелГТУ. Сер. Фундаментальные и прикладные проблемы техники и технологии. — 2008. — №1. — С.22-28.

3. Сошкин Р.В. О применении математических методов для повышения эффективности производства упаковки из гофрокартона / Р.В. Сошкин // Известия Санкт-Петербургской лесотехнической академии. — 2007. — Вып.181. — С.165—173.

4. Власов Д.П. Новая реализация комплекса программ планирования производства гофротары / Д.П. Власов, В.А. Кузнецов, Р.В. Сошкин // Новые информационные технологии в целлюлозно-бумажной промышленности и энергетике: Материалы VI Международной научно-технической конференции. — Петрозаводск: Изд-во ПетрГУ, 2004. — С.79-81 (вклад диссертанта 33%).

5. Кузнецов В.А. Модели раскроя в планировании и управлении производствами ЦБП / В.А. Кузнецов, Р.В. Сошкин // Новые информационные технологии в целлюлозно-бумажной промышленности и энергетике: Материалы VI Международной научно-технической конференции. — Петрозаводск: Изд-во ПетрГУ, 2004. — С. 104-106 (вклад диссертанта 66%).

6. Сошкин Р.В. Особенности применения метода генерации столбцов при решении задачи раскроя гофрополотна / Р.В. Сошкин // Новые информационные технологии в целлюлозно-бумажной промышленности и энергетике: Материалы VI Международной

научно-технической конференции. — Петрозаводск: Изд-во Петр-ГУ, 2004. - С. 122-124.

7. Власов Д.П. Модели и методы оптимального планирования производства гофротары / Д.П. Власов, В.А. Кузнецов, Р.В. Сош-кин // Сборник материалов Всероссийского конкурса инновационных проектов аспирантов и студентов по приоритетному направлению развития науки и техники «Информационно-телекоммуникационные системы»/ Под ред. А.О. Сергеева. - М.: ГНИИ ИТТ «Информика», 2005. - С.73-74 (вклад диссертанта 33%).

8. Власов Д.П. Автоматизированная система управления производством гофротары / Д.П. Власов, В.А. Кузнецов, Р.В. Сошкин // Новые информационные технологии в целлюлозно-бумажной промышленности и энергетике: Материалы VII Международной научно-технической конференции. — Петрозаводск: ПетрГУ, 2006. — С.50-53 (вклад диссертанта 50%).

9. Власов Д.П. Автоматизированная система оптимального планирования производства гофротары / Д.П. Власов, Р.В. Сошкин // Международная школа-конференция по приоритетным направлениям развития науки и техники с участием молодых ученых, аспирантов и студентов. Тезисы докладов. — М., 2006. — С. 12-13 (вклад диссертанта 50%).

10. Власов Д.П. Автоматизированная система оптимального планирования производства гофротары / Д.П. Власов, Р.В. Сошкин // Новые информационные технологии. Тезисы докладов XIV Международной студенческой школы-семинара — М.: МИЭМ, 2006. — С.224-225 (вклад диссертанта 50%).

11. Власов Д.П. Автоматизированная система управления производством гофротары / Д.П. Власов, Р.В. Сошкин // Федеральная школа-конференция по инновационному малому предпринимательству в приоритетных направлениях науки и высоких технологий. Тезисы докладов. — М., 2006. — С.20-22 (вклад диссертанта 50%).

12. Власов Д.П. Свидетельство об отраслевой регистрации разработки №6562 / Д.П. Власов, Д.П. Косицын, В.А. Кузнецов, Р.В. Сошкин // ФГНУ «Государственный координационный центр информационных технологий, отраслевой фонд алгоритмов и программ». — 2006 (вклад диссертанта 25%).

Подписано в печать 05.05.2009. Формат 60x84 1/16. Бумага офсетная. 1 уч.-изд.л. Тираж 120 экз. Изд. №135.

Государственное образовательное учреждение высшего профессионального образования ПЕТРОЗАВОДСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Отпечатано в типографии Издательства Петрозаводского государственного университета 185910, Петрозаводск, пр. Ленина, 33

Список сокращений.

Введение.

Глава 1. Математические модели планирования работы оборудования производства гофротары.

1.1 Содержание задачи планирования производства гофротары

1.2 Обзор ранее выполненных разработок систем планирования производства гофротары.

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

1.4 Исследование особенностей и вариантов задачи планирования и управления производством гофротары.

1.5 Расширенная модель планирования производства ГТ

1.6 Выводы

Глава 2. Базовые методы решения задач планирования и управления производством гофрокартона.

2.1 Динамическое программирование в решении задач раскроя

2.2 Особенности решения задач линейного программирования

2.3 Генерация столбцов в задаче оптимизации раскроев ГП

2.4 Дискретность и нелинейность связей в задачах оптимизации

2.5 Матроиды и жадные алгоритмы

2.6 Выводы

Глава 3. Специальные методы решения задач планирования и управления производством гофрокартона.

3.1 Двойственные оценки и расчет потерь материала.

3.2 Задачи линейного программирования с ограниченным количеством базисных переменных.

3.3 Простейшие свойства и варианты постановки задачи ОКБП

3.4 Матроиды решений задачи ОКБП.

3.5 Прямые алгоритмы перебора.

3.6 Приближенные прямые методы.

3.7 Двойственные алгоритмы.

3.8 Применение перечисленных алгоритмов для решения других задач.

3.9 Выводы

Глава 4. Вопросы технической реализации и внедрения АСУ на основе алгоритмов планирования и управления производством ГТ.

4.1 Общие проблемы при внедрении АСУ на предприятии

4.2 Эффективность внедрения системы

4.3 Требования к автоматизированной системе.

4.4 Модуль регистрации заявок заказчиков и формирования производственных заказов.

4.5 Модуль регистрации технологических карт и характеристик оборудования.

4.6 Модуль объемного планирования.

4.7 Модуль оперативного планирования работы гофроагрега

4.8 Модуль оперативного планирования работы технологических линий.

4.9 Модуль учета выработки производства.

4.10 Выводы.

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

Реализация всех систем выполнена с участием автора в рамках разработок Центра ПетрГУ-Метсо систем автоматизации Петрозаводского государственного университета в 2002-2008 гг. и основана на применении исследования операций, математического моделирования, современных средств и методов создания комплексов программ для решения задач планирования производства гофрокартонной упаковки.

В диссертационной работе рассматриваются вопросы построения математических моделей планирования производственных процессов, разработки методов решения соответствующих оптимизационных задач [13, 29, 33, 62, 63] и комплексов программ, в которых научные и прикладные проблемы взаимосвязаны [71, 72, 79].

История рассматриваемой задачи не нова. В 1994-97 годах ею занимались профессора ПетрГУ А.В.Воронин и В.А.Кузнецов, которыми была разработана система планирования производства гофрокартона для ОАО «Архангельский ЦБК». Вопросам исследования этой и других подобных систем посвящен параграф 1.2.

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

Картина изменилась в 2005 году, когда группа сотрудников ПетрГУ: А.В. Воронин, В.А. Кузнецов, Д.П. Власов и автор, существенно продвинулась в разработке систем такого рода, сравнительно легко адаптируя их к имеющимся на предприятиях бухгалтерским, учетным и информационным системам (1С, SAP R3 и прочие).

В настоящее время Центром ПетрГУ-Метсо систем автоматизации Петрозаводского государственного университета (далее Центр) ведутся переговоры примерно с 20 предприятиями России и зарубежных стран, желающими приобрести разработку.

На автоматизированную систему «Управление гофропроизводством» получено свидетельство об отраслевой регистрации разработки №6562 в ФГНУ «Государственный координационный центр информационных технологий, отраслевой фонд алгоритмов и программ», ее реализацией занимается отдел Центра[15]. В настоящее время разработанные в России и за рубежом системы оказались неконкурентноспособны разработкам Центра ПетрГУ-Метсо систем автоматизации Петрозаводского государственного университета.

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

1. Генерации рациональных (по составу заготовок и доле отходов) раскроев.

2. Оптимизации объемного плана раскроев в целях минимизации затрат материала.

3. Оценки фактических затрат материала на выпуск комплекта деталей каждого вида с учетом всех элементов конструкции и совместных планов раскроя.

4. Оптимизации объемного плана с учетом комплектности элементов конструкции ящика.

5. Оптимизации объемно-календарного плана производства с учетом ожидаемого времени переналадки, производительности и специализации оборудования.

6. Формирования чертежей заготовок конструкции ящика и калькуляции заявки.

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

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

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

Актуальность темы исследования

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

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

С другой стороны, модернизация промышленного производства России, расширение ассортимента выпускаемых товаров и появление большого количества малых предприятий приводят к существенному повышению номенклатуры востребованной упаковки, а, как следствие, — усложнению процесса планирования и управления ее производством. Действительно, если в 1980 году недельный план ОАО «Архангельский ЦБК» включал 10-12 изделий (из них до 60% составляли стандартные ящики для упаковки рыбы), то в 1990 году — 20-25 (причем доля ящиков для упаковки рыбы снизилась до 35% ), в 1995 году это количество возросло до 60-80, в 2000 году — до 120, а в настоящее время составляет 150-180 видов изделий. Аналогичная ситуация наблюдается и на других целлюлозно-бумажных комбинатах (ЦБК) и производствах бумажной и картонной тары.

Существенно расширяется и ассортимент сырья. Если гофрокартон-ное производство ОАО «Архангельский ЦБК» в 1980 выпускало изделия из одного материала (бурый трехслойный гофрокартон), то в 2000 году — четыре вида, а Киевский картонно-бумажный комбинат в настоящее время использует более 100 видов различного исходного материала. Возрастают требования заказчиков к форме и качеству продукции (прочности, точности соединения клапанов, виду внешних слоев, полиграфии, срочности изготовления и пр.).

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

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

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

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

Разработка АСУ на основе решения данной задачи позволяет получить реальный экономический эффект в форме снижения доли отходов на 15-25%, повысить оперативность и качество планирования и управления производственными процессами, сократить расход сырья, снизить себестоимость продукции и, в конечном счете, принести значительный экономический эффект.

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

Для достижения поставленной цели были сформулированы следующие задачи:

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

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

3. Исследовать математические задачи, полученные на основании расширенной модели.

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

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

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

Предметом исследования являются математические модели и методы решения задач раскроя гофрополотна.

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

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

Для разработки алгоритмов и программных комплексов использовались современные технологии проектирования программных систем и баз данных [3, 47, 74], методы структурного и объектно-ориентированного программирования. Для разработки использовались системы программирования Borland Delphi 4 - 7 и Microsoft Visual Studio .NET 2003, 2005, для проектирования баз данных использовались Paradox и Microsoft SQL Server 2000, 2005.

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

Представлены принципы классификации исследуемых моделей.

К результатам исследования, обладающих научной новизной и выносимых на защиту, относятся следующие:

• Сформулированы и исследованы задачи оптимизации для моделирования процессов раскроя гофрополотна.

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

• Разработаны эффективные методы и алгоритмы решения задач оптимизации планирования раскроев гофрополотна.

• Предложен метод расчета оценок потерь материала в случае вырожденности или при отсутствии допустимых решений задачи.

Практическая значимость и реализация результатов работы.

Полученные в диссертации результаты использовались при выполнении хоздоговорных научно-исследовательских работ при личном участии автора на кафедре прикладной математики и кибернетики и в Центре ПетрГУ-Метсо систем автоматизации Петрозаводского государственного университета в 2002-2008 годах.

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

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

1. ОАО «Архангельский ЦБК», г. Новодвинск.

2. Филиал ОАО «Архбум»в г. Подольске.

3. ОАО «Киевский картонно-бумажный комбинат», г. Обухов.

4. ООО «Гранит», г. Павловский Посад.

5. ООО «Ярославский картон», г. Ярославль.

6. ООО «Вереск-1», г. Архангельск, г. Гатчина.

7. ЗАОр «Народное предприятие Набережночелнинский картонно-бу-мажный комбинат», г. Набережные Челны.

8. ОАО «БумСнаб», г. Нижний Новгород.

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

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

Апробация работы. Основные результаты диссертационной работы докладывались автором на V-VIII Международных научно-технических конференциях «Новые информационные технологии в ЦБП и энергетике» (Петрозаводск, 2002, 2004, 2006, 2008), на Международной школе-конференции по приоритетным направлениям развития науки и техники с участием молодых ученых, аспирантов и студентов (Ялта, Украина, 2006), на конференциях и семинарах ПетрГУ. На Всероссийском конкурсе инновационных проектов аспирантов и студентов по приоритетному направлению развития науки и техники «Информационно-телекоммуникационные системы» (Московская область, 2005) получен диплом первой степени.

Структура и объем работы. Диссертация состоит из введения, 4 глав основного материала, заключения, библиографического списка и 1 приложения. Основной материал изложен на 118 стр., включая 5 рисунков и 2 таблицы. Библиографический список включает 87 наименований. Приложения содержат материалы, связанные с практическим использованием результатов диссертации. Во введении обоснована актуальность темы диссертации, указаны цель и задачи исследования, обсуждены научная новизна и практическая значимость работы.

4.10. Выводы

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

2. Описаны проблемы, возникающие на большинстве предприятий при внедрении АСУ. Даны рекомендации по их решению

3. Указана эффективность внедрения автоматизированной системы управления на основании статистики но завершенным проектам.

4. Указаны основные требования к автоматизированной системе управления производством гофротары.

5. Описана работа основных модулей, реализующих алгоритмы формирования производственных программ.

Заключение

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

В ходе решения поставленных задач получены следующие научные и практические результаты:

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

2. Выявлены некоторые важные классы прикладных нелинейных задач, связанных с производством гофрокартона.

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

4. Установлена возможность использования представленных в диссертации алгоритмов для решения ряда других задач.

5. Все перечисленные методы реализованы в виде комплексов программных средств, используемых при разработке и создании АСУ планирования раскроев гофрополотна.

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

1. Бакиелл Джулиан, М. Профессиональное руководство по SQL Server: хранимые процедуры, XML, HTML / М. Бакиелл Джулиан.- СПб.: ООО «ДиаСофтЮП», 2003. 560 с.

2. Баронов, В.В. Автоматизация управления предприятием / В.В. Баронов и др. — М.: ИНФРА-М, 2000. — 239 с.

3. Беллман, Р. Динамическое программирование / Р. Беллман. — М.: Мир, 1960. 424 с.

4. Вентцель, Е. С. Исследование операций / Е. С. Вентцель — М.: Наука, 1980. — 208 с.

5. Власов, Д.П. Свидетельство об отраслевой регистрации разработки №6562 / Д.П. Власов, Д.П. Косицын, В.А. Кузнецов, Р.В. Сошкин // ФГНУ «Государственный координационный центр информационных технологий, отраслевой фонд алгоритмов и программ». — 2006.

6. Воронин, А. В. Автоматизированная система планирования и управления производством гофротары / А. В. Воронин, В. А. Кузнецов // Труды ПетрГУ. Сер. Прикл. матем. и информ. Вып. 5 Петрозаводск: Изд-во ПетрГУ, 1996. — С .3-11.

7. Воронин, А. В. Математические модели и методы планирования и управления предприятием ЦБП / А. В. Воронин, В. А. Кузнецов.

8. Петрозаводск: Изд-во ПетрГУ, 2000. — 256 с.

9. Воронин, А. В. Прикладные оптимизационные задачи в целлюлозно-бумажной промышленности / А. В. Воронин, В. А. Кузнецов. — Петрозаводск: Изд-во ПетрГУ, 2000. — 152 с.

10. Воронин, А. В. Расчет ресурсов и планирование производства ЦБК: Отчет о НИР (заключит.) / А. В. Воронин, В. А. Кузнецов. — Петрозаводск: ПетрГУ, 1989. — 49 с.

11. Воронин, А. В. Вертикально-интегрированные структуры управления в лесопромышленном комплексе / А. В. Воронин, И. Р. Шегельман. СПб: Изд-во СПб ЛТА, 2003. - 160 с.

12. Гаврилов, Д.В. Управление предприятием на базе стандарта MRPII / Д.В. Гаврилов. — СПб.: Питер, 2002. 320 с.

13. Гасс, С. Линейное программирование: методы и приложения / С. Гасс. — М.: Физматгиз, 1961. — 303 с.

14. Гольштейн, Е.Г. Теория двойственности в математическом программировании и ее приложения / Е.Г. Гольштейн. — М.: Наука. — 1971. 352 с.

15. Гольштейн, Е.Г. Новые направления в линейном программировании / Е.Г. Гольштейн, Д.Б. Юдин. — М.: Советское радио, 1966. — 428 с.

16. Давыдова, И. М. Задачи размещения предприятий / И. М. Давыдова. СПб.: Изд-во ЛГУ, 1978. — 86 с.

17. Данциг Дж. Линейное программирование, его применения и обобщения / Дж. Данциг. — М.: Прогресс, 1966. — 600 с.

18. Деордица, Ю. С. Исследование операций в планировании и управлении / Ю. С. Деордица. — Киев: Выща шк., 1991. — 270 с.

19. Емельянов, С.В. Многокритериальные методы принятия решений / С.В. Емельянов //Математика и кибернетика. —1985.—№10. — 32 с.

20. Ильев, В.П. Оценки погрешности жадных алгоритмов для задач на наследственных системах / В.П. Ильев // Дискретный анализ и исследование операций. — 2008 — Том 15 — М — С.44-57

21. Исследование операций. Современное состояние. / под. ред. Д. Мо-удерат. 1-2, М.: Изд-во Мир, 1989.

22. Канторович, JI.B. Математические методы организации и планирования производства / J1.B. Канторович. — Л.: Издательство ЛГУ, 1939. 68 с.

23. Канторович, JI.B. Математическое оптимальное программирование в экономике / Л.В. Канторович, А.Б. Горстко. — М.: Знание, 1968.- 95 с.

24. Канторович, Л. В. Рациональный раскрой промышленных материалов / Л. В. Канторович, В. А. Залгаллер. — Новосибирск: Наука, 1972. 300 с.

25. Карданская, Н.Л. Системы управления производством / Н.Л. Кар-данская, АД. Чудаков. — М.: Русская Деловая Литература, 1999.- 240 с.

26. Карманов, В.Г. Математическое программирование / В.Г. Карманов. — М.: физмат-лит, 2004. — 264 с.

27. Ковалев, М. М. Матроиды в дискретной оптимизации / М.М. Ковалев. М: Едиториал УРСС, 2003. — 224 с.

28. Кузнецов, В. А. Задачи раскроя в целлюлозно-бумажной промышленности / В. А. Кузнецов. СПб: Изд-во СПб ЛТА, 2000. - 132 с. Липский, В. Комбинаторика для программистов / В. Липский. — М.: Мир, 1988. - 200 с.

29. Лодон, Дж. Управление информационными системами. 7-е изд. / Дж.Лодон, К. Лодон: пер. с англ. под ред. Д. Р. Трутнева. — СПб.: Питер, 2005. — 912 с.

30. Львов, Ю.А. Оптимизация дискретных моделей производственного планирования / Ю.А. Львов. — Л.: Изд-во Ленингр. ун-та, 1975. — 354 с.

31. Львов, Ю.А. Экономико-математические методы и модели: Учеб. пособие/ЛИЭИ / Ю.А. Львов. Л., 1980. — 262 с.

32. Лэсдон, С. Оптимизация больших систем / С. Лэсдон. — М.: Изд-во Мир, 1976. 584 с.

33. Макконнелл, С. Совершенный код. Мастер-класс / С. Макконнелл.

34. М.: Изд-во Русская редакция; СПб.: Питер, 2007. — 896 с.

35. Пападимитриу, X. Комбинаторная оптимизация: Алгоритмы и сложность / X. Пападимитриу, К. Стайглиц. — М.:Мир, 1984. — 512 с.

36. Первозванская, Т.Н. Элементы теории управления запасами: учеб. пособие / Т.Н. Первозванская, А.А. Первозванский. — Л.: Изд-во Ленингр. ун-та, 1983. — 109 с.

37. Первозванский, А.А. Математические модели в управлении производством / А.А. Первозванский. — М.: Наука, 1975. — 616 с.

38. Питеркин, С.В. Точно вовремя для России. Практика применения ERP-систем / С.В. Питеркин, Н.А. Оладов, Д.В. Исаев — М.: Аль-пина Паблишер, 2002. — 368 с.

39. Подиновский, В.В. Многокритериальные задачи с упорядоченными по важности критериями / В.В. Подиновский // Автоматика и телемеханика. 1976. —№11. - С.118-127.

40. Подиновский, В.В. Эффективные планы в многокритериальных задачах принятия решений в условиях неопределенности /В.В. Подиновский // Модели процессов принятия решений/ ДВНЦ АН СССР. Владивосток, 1978. - С.102-113.

41. Подиновский, В.В. Парето оптимальные решения многокритериальных задач / В.В. Подиновский, В.Л. Ногин. — М.: Наука, 1982.- 256 с.

42. Прилуцкий, М.Х. Многокритериальные задачи объемного планирования. Лексикографические схемы / М.Х. Прилуцкий, С.Е. Власов //Информационные технологии. — 2005. — №7. —С.61-66.

43. Райзберг, Б.А. Современный экономический словарь / Б.А. Райз-берг, Л.Ш. Лозовский, Е.Б. Стародубцева. — 2-е изд., испр. — М.: ИНФРА-М, 1999. 479 с.

44. Рейнгольд, Э. Комбинаторные алгоритмы. Теория и практика / Э. Рейнгольд, Ю. Нивергельт, Н. Део. — М.: Мир, 1980. — 476 с.

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

46. Романовский, И. В. Дискретный анализ / И. В. Романовский. — 2-е изд., испр. — СПб.: Невский диалект , 2000. — 240 с.

47. Романовский, И. В. Субоптимальные решения / И. В. Романовский. — Петрозаводск: Издательство Петрозаводского университета, 1998. 96 с.

48. Рувинский, А.А. Математические модели и алгоритмы в системах управления картонно-бумажным производством / А.А. Рувинский, Ю.А. Зак, P.M. Рейдман. — М.: Лесная промышленность, 1971. — 126 с.

49. Саати, Т.Л. Принятие решений — Метод анализа иерархий / Т.Л. Саати. — М:Радио и связь, 1993. — 278 с.

50. Саати, Т.Л. Целочисленные методы оптимизации и связанные с ними экстремальные проблемы / Т.Л. Саати. — М: Мир, 1973. — 302 с.

51. Саломатип, Н.А. Новые информационные технологии в управлении производством / Н.А. Саломатин, А.В. Фель, Н.Г.Шаламова. — М.: ГУУ, 1996. 375 с.

52. Сошкин, Р.В. Математические модели и алгоритмы решения задач оптимального раскроя полосы / Р.В. Сошкин // Вестник Поморского университета. Сер. Естественные науки. — 2009. — №1. — С.77-82.

53. Сошкин, Р.В. Некоторые прикладные задачи раскроя и методы их решения / Р.В. Сошкин j j Известия ОрелГТУ. Сер. Фундаментальные и прикладные проблемы техники и технологии. — 2008. — №1.- С.22-28.

54. Сошкин, Р.В. О применении математических методов для повышения эффективности производства упаковки из гофрокартона /Р.В. Сошкин // Известия Санкт-Петербургской лесотехнической академии. 2007. - Вып.181. - С.165-173.

55. Стивенсон, Дж. Вильям. Управление производством / Дж. Вильям Стивенсон:пер. с англ. — М.: ООО "Издательство "Лаборатория базовых знаний, ЗАО "Издательство ВИНОМ", 1998. 928 с.

56. Схрейвер, А. Теория линейного и целочисленного программирования / А. Схрейвер. — М.Мир, 1991. Т.1,2.

57. Таха, ХемдиА. Введение в исследование операций, 7-е изд. / Хемди А. Тала М.: Вильяме, 2005. — 912 с.

58. Терехов, JI.JI. Математические методы и модели в планировании / Л.Л.Терехов, А.Д. Шарапов, А.С. Берштейн, С.П. Сиднев. — Киев: Высшая школа, 1981. — 282 с.

59. Управление производством: Учебник/ Под ред. Н.А. Соломатина.- М.: ИНФРА-М, 2001. 219 с.

60. Хендерсон, К. Профессиональное руководство по SQL Server: хранимые процедуры, XML, HTML. / К. Хендерсон — СПб.: Питер, 2005. 620 с.

61. Ху, Т. Целочисленное программирование и потоки в сетях / Т. Ху.- М.:Мир, 1974. 1519 с.

62. Царев, В.В. Автоматизация многоцелевого оперативно-производственного планирования на промышленных предприятиях / В.В. Царев. Л.: Изд-во ЛГУ, 1984. - 136 с.

63. Царев, В.В. Внутрифирменное планирование / В.В. Царев. — СПб.: Питер, 2002. 496 с.

64. Шикин, Е.В. Математические методы и модели в управлении: Учеб. пособие / Е.В. Шикин, А.Г. Чхартишвили. — М.: Дело, 2000. — 440 с.

65. Шор, Н.З. Теория оптимальных решений / Н.Э. Шор, В.И. Билец-кий, А.В. Марчук и др. — Киев: Азбука классика, 1975. — 94 с.

66. Экономико-математические методы и модели в управлении производством. Сб. науч. тр./Галкин Л.Г. и др.]. — Ярославль: ЯрГУ, 1987.

67. Юттлер, X. Линейная модель с несколькими целевыми функциями / X. Юттлер // Экономика и матем. методы. — 1967. — №3.

68. Balas, Е. An Additive Algorithm for Solving Linear Program Problems with Zero-One Variables / E. Balas // Oper. Research, 1962. — v.10.- №4. 517-546 pp.

69. V. IVev Hereditary systems and greedy-type algorithms / V. Il'ev // Discrete Appl. Math. 2003. - V. 132. - N 1-3. - P. 137-148

70. V. Il'ev Perfomance guarantees of a greedy algorithm for minimizing a supermodular set function / V. Il'ev, N. Linker // Evropean J. Oper. Res. 2006. - V. 171. - №2. - P. 648-660

71. Benders, J. F. Partitioning Procedures for Solving Mixed Variable Programming Problems / J. F. Benders // Numerische Mathematik.- 1962. V. 4. - PP. 238-252.

72. Geofrion, A. M. Integer Programming Algorithms: a Fraimework and the State-of-Art-Survay / A. M. Geofrion, R. E. Marsten // Management Sci. 1972. - V.18. - №4. - PP.465-491.87. PC-Topp System Overview.http : //www.pctopp.com/en/products/default.mspx