Содержание к диссертации
Введение
Глава 1. Математические модели планирования работы обо рудования производства гофротары 15
1.1 Содержание задачи планирования производства гофротары 17
1.2 Обзор ранее выполненных разработок систем планирования производства гофротары 24
1.3 Базовая математическая модель планирования производства гофротары (один гофроагрегат) 30
1.4 Исследование особенностей и вариантов задачи планирования и управления производством гофротары 32
1.5 Расширенная модель планирования производства ГТ . 41
1.6 Выводы 45
Глава 2. Базовые методы решения задач планирования и управления производством гофрокартона 46
2.1 Динамическое программирование в решении задач раскроя 46
2.2 Особенности решения задач линейного программирования 51
2.3 Генерация столбцов в задаче оптимизации раскроев ГП . 60
2.4 Дискретность и нелинейность связей в задачах оптимизации 63
2.5 Матроиды и жадные алгоритмы 66
2.6 Выводы 71
Глава 3. Специальные методы решения задач планирования и управления производством гофрокартона 72
3.1 Двойственные оценки и расчет потерь материала 73
3.2 Задачи линейного программирования с ограниченным количеством базисных переменных 77
3.3 Простейшие свойства и варианты постановки задачи ОКБП 79
3.4 Матроиды решений задачи ОКБП 84
3.5 Прямые алгоритмы перебора 87
3.6 Приближенные прямые методы 90
3.7 Двойственные алгоритмы 92
3.8 Применение перечисленных алгоритмов для решения других задач 98
3.9 Выводы 100
Глава 4. Вопросы технической реализации и внедрения АСУ на основе алгоритмов планирования и управления производством ГТ 101
4.1 Общие проблемы при внедрении АСУ на предприятии 101
4.2 Эффективность внедрения системы 105
4.3 Требования к автоматизированной системе 106
4.4 Модуль регистрации заявок заказчиков и формирования производственных заказов 108
4.5 Модуль регистрации технологических карт и характеристик оборудования 109
4.6 Модуль объемного планирования 112
4.7 Модуль оперативного планирования работы гофроагрегатов 113
4.8 Модуль оперативного планирования работы технологических линий 114
4.9 Модуль учета выработки производства 116
4.10 Выводы 117
Заключение 118
Библиографический список 118
Приложение 127
- Базовая математическая модель планирования производства гофротары (один гофроагрегат)
- Особенности решения задач линейного программирования
- Задачи линейного программирования с ограниченным количеством базисных переменных
- Модуль регистрации заявок заказчиков и формирования производственных заказов
Введение к работе
В основе диссертационного исследования лежит накопленный опыт разработки и внедрения автоматизированных систем управления, основанных на решении оптимизационных задач планирования производства гофрокартона (ГК) для ряда предприятий России.
Реализация всех систем выполнена с участием автора в рамках разработок Центра ПетрГУ-Метсо систем автоматизации Петрозаводского государственного университета в 2002-2008 гг. и основана на применении исследования операций, математического моделирования, современных средств и методов создания комплексов программ для решения задач планирования производства гофрокартонной упаковки.
В диссертационной работе рассматриваются вопросы построения математических моделей планирования производственных процессов, разработки методов решения соответствующих оптимизационных задач [13, 29, 33, 62, 63] и комплексов программ, в которых научные и прикладные проблемы взаимосвязаны [71, 72, 79].
История рассматриваемой задачи не нова. В 1994-97 годах ею занимались профессора ПетрГУ А.В.Воронин и В.А.Кузнецов, которыми была разработана система планирования производства гофрокартона для ОАО «Архангельский ЦБК». Вопросам исследования этой и других подобных систем посвящен параграф 1.2.
Зарубежные системы оптимизации раскроев гофрополотна (ГП) поставляются в комплекте с самым современных оборудованием, стоят очень дорого и лишь частично соответствуют требованиям российских предприятий. Принципы работы таких систем составляют секрет разработчиков и, как правило, не освещаются более, чем на рекламном уровне. В связи с финансовыми трудностями предприятий и сменой собственников, часто повлекших смену руководства, в течение некоторого периода времени автоматизированные системы планирования производства гофрокартона были не востребованы.
Картина изменилась в 2005 году, когда группа сотрудников ПетрГУ: А.В. Воронин, В.А. Кузнецов, Д.П. Власов и автор, существенно продвинулась в разработке систем такого рода, сравнительно легко адаптируя их к имеющимся на предприятиях бухгалтерским, учетным и информационным системам (1С, SAP R3 и прочие).
В настоящее время Центром ПетрГУ-Метсо систем автоматизации Петрозаводского государственного университета (далее Центр) ведутся переговоры примерно с 20 предприятиями России и зарубежных стран, желающими приобрести разработку.
На автоматизированную систему «Управление гофропроизводством» получено свидетельство об отраслевой регистрации разработки №6562 в ФГНУ «Государственный координационный центр информационных технологий, отраслевой фонд алгоритмов и программ», ее реализацией занимается отдел Центра[15]. В настоящее время разработанные в России и за рубежом системы оказались неконкурентноспособны разработкам Центра ПетрГУ-Метсо систем автоматизации Петрозаводского государственного университета.
Функции рассматриваемой системы определяет решение следующих задач.
Генерации рациональных (по составу заготовок и доле отходов) раскроев.
Оптимизации объемного плана раскроев в целях минимизации затрат материала.
Оценки фактических затрат материала на выпуск комплекта деталей каждого вида с учетом всех элементов конструкции и совместных планов раскроя.
Оптимизации объемного плана с учетом комплектности элементов конструкции ящика.
Оптимизации объемно-календарного плана производства с учетом ожидаемого времени переналадки, производительности и специализации оборудования.
Формирования чертежей заготовок конструкции ящика и калькуляции заявки.
Расчета схем укладки пачек готовых изделий на поддоны, размещения поддонов в транспортных средствах и пр.
Реализация комплекса моделей, методов и программных систем, лежащих в основе этой разработки, связана не только с применением известных, но и с созданием некоторых специальных методов решения оптимизационных задач, что составляет научную новизну диссертационной работы.
Вопросами разработки моделей и методов поиска оптимальных раскроев и созданием соответствующего программного обеспечения (позиции 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%, повысить оперативность и качество планирования и управления производственными процессами, сократить расход сырья, снизить себестоимость продукции и, в конечном счете, принести значительный экономический эффект.
Цели и задачи исследования. Цель работы — повышение эффективности планирования и управления производством гофрокартона и упаковки посредством использования математических моделей и методов планирования и управления раскроем гофрополотна.
Для достижения поставленной цели были сформулированы следую-
щие задачи:
Исследовать технологии планирования и управления раскроями гоф-рополотна на различных производствах.
Разработать расширенную математическую модель задачи планирования работы цеха гофротары.
Исследовать математические задачи, полученные на основании расширенной модели.
Разработать математические методы решения оптимизационных задач, связанных с полученными математическими моделями планирования и управления раскроем гофрополотна.
Реализовать предложенные алгоритмы планирования в виде программных модулей и внедрить автоматизированную систему управления и планирования производства на промышленных предприятиях России.
Объектом исследования являются используемые в современных условиях технологии планирования и управления раскроями гофрополотна.
Предметом исследования являются математические модели и методы решения задач раскроя гофрополотна.
Методы исследования. Теоретической и методологической основой исследования являются методы исследования операций и математического программирования. Системный анализ и методы оптимизации используются для анализа производственных процессов, построения математических моделей и разработки алгоритмов решения соответствующих экстремальных задач.
Используется теория матроидов, методы линейного, динамического и дискретного программирования для решения линейных и нелинейных задач сложной структуры и высокой размерности.
Для разработки алгоритмов и программных комплексов использовались современные технологии проектирования программных систем и баз данных [3, 47, 74], методы структурного и объектно-ориентированного
программирования. Для разработки использовались системы программирования Borland Delphi 4 - 7 и Microsoft Visual Studio .NET 2003, 2005, для проектирования баз данных использовались Paradox и Microsoft SQL Server 2000, 2005.
Научная новизна. В диссертации на основании имеющегося практического опыта обобщены разработанные А.В.Ворониным и В.А.Кузнецовым математические модели раскроя гофрополотна для производства гофрокартона и тары, модифицированы известные методы решения прикладных задач, связанные с этими моделями и предложены новые методы.
Представлены принципы классификации исследуемых моделей.
К результатам исследования, обладающих научной новизной и выносимых на защиту, относятся следующие:
Сформулированы и исследованы задачи оптимизации для моделирования процессов раскроя гофрополотна.
Предложены и исследуются различные методы решения задач линейного программирования с ограниченным количеством базисных переменных.
Разработаны эффективные методы и алгоритмы решения задач оптимизации планирования раскроев гофрополотна.
Предложен метод расчета оценок потерь материала в случае вырожденности или при отсутствии допустимых решений задачи.
Практическая значимость и реализация результатов работы.
Полученные в диссертации результаты использовались при выполнении хоздоговорных научно-исследовательских работ при личном участии автора на кафедре прикладной математики и кибернетики и в Центре ПетрГУ-Метсо систем автоматизации Петрозаводского государственного университета в 2002-2008 годах.
В работе приведены результаты расчетов, которые подтверждают применимость разработанных алгоритмов и программ для решения задач с размерностью, требуемой на практике.
Представленные в работе математические модели, методы и алгоритмы внедрены и используются в составе программных комплексов на ряде крупных предприятий России и Украины.
ОАО «Архангельский ЦБК», г. Новодвинск.
Филиал ОАО «Архбум»в г. Подольске.
ОАО «Киевский картонно-бумажный комбинат», г. Обухов.
ООО «Гранит», г. Павловский Посад.
000 «Ярославский картон», г. Ярославль.
000 «Вереск-1», г. Архангельск, г. Гатчина.
ЗАОр «Народное предприятие Набережночелнинский картонно-бумажный комбинат», г. Набережные Челны.
ОАО «БумСнаб», г. Нижний Новгород.
В результате эксплуатации программных систем на предприятиях повысилась эффективность управления производством, получен реальный экономический эффект в форме экономии до 25% идущего в отходы материала. На основании результатов внедрения программных комплексов в промышленное производство, разработаны рекомендации по использованию предложенных моделей и методов в организации планирования производственными процессами.
Рассмотренные в диссертации математические модели и методы решения задач обладают достаточной общностью и могут использоваться для планирования и управления производством в других отраслях промышленности, где важнейшей операцией является раскрой ленты материала.
Апробация работы. Основные результаты диссертационной работы
докладывались автором на V-VIII Международных научно-технических конференциях «Новые информационные технологии в ЦБП и энергетике» (Петрозаводск, 2002, 2004, 2006, 2008), на Международной школе-конференции по приоритетным направлениям развития науки и техники с участием молодых ученых, аспирантов и студентов (Ялта, Украина, 2006), на конференциях и семинарах ПетрГУ. На Всероссийском конкурсе инновационных проектов аспирантов и студентов по приоритетному
направлению развития науки и техники «Информационно-телекоммуникационные системы» (Московская область, 2005) получен диплом первой степени.
Структура и объем работы. Диссертация состоит из введения, 4 глав основного материала, заключения, библиографического списка и 1 приложения. Основной материал изложен на 118 стр., включая 5 рисунков и 2 таблицы. Библиографический список включает 87 наименований. Приложения содержат материалы, связанные с практическим использованием результатов диссертации. Во введении обоснована актуальность темы диссертации, указаны цель и задачи исследования, обсуждены научная новизна и практическая значимость работы.
В начале первой главы представлена терминология, необходимая для описания математических моделей и методов решения соответствующих оптимизационных задач. Затем идет постановка задачи планирования производства гофротары и исследование ранее выполненных разработок в данной области. Сформулирована базовая модель планирования производства гофротары. По результатам анализа особенностей реализации и внедрения программной системы на различных предприятиях формулируется расширенная модель планирования, которая включает многочисленные технологические особенности процесса кроя гофрополотна. Установлено, что практически важные задачи планирования и управления производством гофротары характеризуются высокой размерностью, присутствием дискретности и нелинейных связей между управляемыми факторами. В конце первой и каждой из последующих глав приводятся выводы по содержанию материала главы.
Во второй главе рассматриваются математические методы, использование которых составляет основу решения поставленных задач. Описаны методы динамического и линейного программирования, особое внимание уделено методу генерации столбцов, использование которого является принципиально важным при решении поставленных задач. Отдельный раздел посвящен теории матроидов, использование которой требуется
для решения задач с ограниченным количеством базисных переменных.
Третья глава содержит основные научные результаты автора, касающиеся решения оптимизационных задач с разнообразными ограничениями, возникающими при практическом внедрении систем планирования на гофропроизводствах. Приводится набор различных, разработанных автором алгоритмов, применение которых позволяет получать субоптимальное решение задачи с требуемой точностью. Представленные алгоритмы разбиты на следующие группы: прямые, приближенные, двойственные.
Четвертая глава посвящена описанию практической реализации разработанной системы. Рассматриваются общие проблемы, с которыми сталкивался автор при внедрении АСУ на предприятии, даны рекомендации по решению этих проблем. Перечисляются основные требования к автоматизированной системе на производстве гофротары, обосновывается эффективность внедрения системы. Описываются возможности созданного программного комплекса
В заключении представлены основные результаты работы.
Диссертацию завершают библиографический список из 87 наименований. В приложении содержится копия свидетельства о регистрации разработки и акты о внедрении автоматизированной системы управления на: ОАО «Архангельский ЦБК», филиал ОАО «Архбум»в г. Подольске, ЗАОр «Народное предприятие Набережночелнинский картонно-бумажный комбинат».
Публикации. Основные результаты диссертационной работы опубликованы в 12 печатных работах, в том числе три в журналах, входящих в «Перечень ведущих рецензируемых научных журналов и изданий, в которых должны быть опубликованы основные научные результаты диссертации на соискание ученой степени доктора и кандидата наук» [65, 66, 67].
Базовая математическая модель планирования производства гофротары (один гофроагрегат)
Перечисленные особенности процесса планирования работы цеха гофротары приводят к следующему комплексу математических моделей [18]. 1. Исходные данные задачи формирования объемного плана. Для построения модели введем: М — множество индексов заготовок для заказов (і Є М); N — множество индексов раскроев (j Є N); Aij — нормативы выработки заготовок для заказов г Є М при раскрое единицы площади гофрополотна по схеме j є N (м2); A ij — количество заготовок для заказов і Є М в составе раскроя по схеме j є N; 5j — доля потерь материала при раскрое по схеме j є TV; Widthi — ширина заготовки для заказа, і Є М (измеряется в мм.); Bendsi — количество необходимых рилевок для заготовки, і Є М\ L — ширина гофрополотна (измеряется в мм.); Кп — количество продольных ножей гофроагрегата; КпВ — количество продольных рилевочных ножей гофроагрегата; S_ — минимально необходимая кромка для отреза с каждой стороны полотна формата L (измеряется в мм.); S — максимально разрешенная кромка для отреза с каждой стороны полотна формата L (измеряется в мм.); 6j, В{ — минимальный и максимальный требуемый объем выпуска заготовки для заказа і Є М (м2); с?, D — минимальная и максимальная возможная производительность гофроагрегата в течение планируемого промежутка времени (измеряется в м2). 2. Оптимизация объемного плана. Введем неизвестные задачи Xj — планируемая выработка гофропо лотна (объем выработки раскроя, м2) в соответствии с раскроем j Є N, тогда математическая модель будет иметь следующий вид: Целевая функция задачи (1.3.1) соответствует суммарным потерям материала, условия (1.3.2) определяют необходимые объемы производства заготовок, условия (1.3.3-1.3.5) задают соответствие раскроя технологии: учет рабочей ширины полотна, количества продольных и рилевоч-ных ножей. Условие (1.3.6) ограничивает производительность гофроаг-регата, а условие (1.3.7) указывает на неотрицательность неизвестных. Для срочных заказов границы 6j и Bj совпадают и равны требуемому объему заказа. Для заказов, которые разрешено использовать в качестве подкроя, но выпуск которых на данный момент не обязателен устанавливается Ь{ — 0.
При использовании метода генерации столбцов, на каждом шаге решения основной задачи приходится решать вспомогательную задачу линейного раскроя [68]. Обозначим: L, L максимальная и минимальная разрешенная для кроя ширина полотна; Vi — текущие значения двойственных переменных условия (1.3.2), і Є М; щ — неизвестные вспомогательной задачи: количество заготовок заказа і Є М в составе нового раскроя. 1) Режим построения раскроев «1 + 1», который допускает поиск рас кроев, состоящих из одной или двух различных заготовок, основан на решении задачи 2) При поиске более сложных раскроев решается общая задача Вспомогательная задача эффективно решается методом ветвей и границ с предварительным упорядочением заготовок по убыванию показателя Vi/Widthi. В таком виде задача оптимизации объемного плана цеха ГТ была реализована В. А. Кузнецовым и А. В. Ворониным в 1995 г., см. [17, 18]. Опыт разработки и внедрения автоматизированных систем планирования и управления производством гофротары на базе представленной выше математической модели показал, что в некоторых случаях этой модели недостаточно и требуется ее серьезное развитие.
Перечислим некоторые особенности технологии планирования и управления данного производства, которые встретились автору в процессе разработки и внедрения таких автоматизированных систем. На крупных производствах, которых сейчас становится все больше, часто устанавливается два и более гофроагрегата, которые могут отличаться по техническим характеристикам: допустимым маркам и профилям вырабатываемой продукции, скорости работы, времени переналадки и т.п.
Большинство заказов могут быть исполнены на любом из агрегатов, остальные требуют выпуска на конкретном оборудовании. При распределении заказов между гофроагрегатами необходимо учитывать их технические характеристики и плановую производительность. Обозначим: С (от слова Corrugators) —множество индексов гофроагрегатов (с Є С); Lc — ширина полотна на гофроагрегате, с Є С (в мм.); Кпс — количество продольных ножей гофроагрегата, с Є С\ КпВс — количество продольных рилевочных ножей гофроагрегата, с Є С\ Sc — минимально необходимая кромка для отреза с каждой стороны полотна формата Lc, с Є С (измеряется в мм.); Sc — максимально разрешенная кромка для отреза с каждой стороны полотна формата Lc, с Є С (измеряется в мм.); dc, Dc — минимальная и максимальная возможная производительность гофроагрегата с Є С в течение планируемого промежутка времени (измеряется в м2); yVc — множество индексов раскроев допустимых для выпуска на гофроагрегате, с Є С (iVc С TV); gcj — флаг исполнения раскроя j на гофроагрегате с Є С, j Є N
Особенности решения задач линейного программирования
Задача линейного программирования [28, 37, 49, 50, 61] (ЛП) — задача условной оптимизации с линейной целевой функцией и линейными ограничениями. Решение задач планирования раскроев ГА связано с модификацией симплексного метода, изложение которых потребует ряда определений, связанных со средствами решения этих задач — линейной алгеброй и теорией двойственности. При описании задачи в общей форме необходимо также указать направление оптимизации, типы ограничений и знаки переменных. Размерность такой задачи ЛП обычно обозначают т х п, где т — число линейных ограничений, an — число переменных. Задачу ЛП часто рассматривают в стандартной, канонической и общей форме [70]. где символ заменяет один из трех возможных знаков =, , , символ 0 означает, что соответствующая переменная Xj 0, Xj 0 или Xj любого знака (в каждом условии — собственные). Линейные ограничения задачи определяют Псйп- множество допустимых решений задачи ЛП. Если рассматривается несколько задач ЛП, то выбор конкретной обозначается верхним индексом этого множества (например, 1Р). Все перечисленные формы задач эквивалентны в том смысле, что любую из них можно привести к любой другой используя дополнительные переменные.
Преобразование реализуется за счет расширения множества переменных дополнительными. Задача ЛП в стандартной форме может рассматриваться как задача поиска вектора линейного векторного пространства Rm — конической комбинации столбцов матрицы ограничений, которому соответствует оптимум линейной функции цели. Поиск разложения вектора b = (61, 62, , bn) по базису, состоящему из векторов Aj = (Aij, A2J, ..., Anj), j є 1 : n сводится к решению квадратной системы линейных уравнений: Решением задачи ЛП (планом) называется вектор Требуется найти х — оптимальное решение (называемое также оптимальным планом) этой задачи: Обозначим N с. N — базисное множество [37] столбцов матрицы А = Л[М, N] как множество линейно-независимых столбцов мощности ранга этой матрицы: Базисное множество столбцов является базисом в подпространстве Rm) образованном векторами N . Подматрицу AN [M, N ], состоящую из базисных столбцов, будем называть базисной. Если задача ЛП сформулирована корректно и адекватно отражает моделируемую ситуацию, то искомое оптимальное решение существует, что гарантируется, например, в случае, когда множество допустимых решений этой задачи: не пусто и ограничено2 в Rn. Если множество Q, не ограничено, то и z может быть равно со. В таком случае (бессмысленном с точки зрения приложений) оптимального решения не существует, то же самое будет и если 2 = 0. В последнем случае логично определить z = —со, а каждый из подобных случаев необходимо идентифицировать. Метод последовательного улучшения плана основан на двух важнейших свойствах задачи ЛП: 1) Конечности множества и алгебраической определенности крайних точек О, соответствующих базисным решениям. 2) Возможности использования теории двойственности для обоснования оптимальности или пересчета решения задачи ЛП.
Если базисное решение x [N] 0 удовлетворяет условию неотрицательности3, его называют допустимым базисным решением (ДБР), а соответствующее базисное множество — допустимым. Значения XN [j] j Є N ДБР могут принимать нулевые или положительные значения. ДБР ждг/ назовем невырожденным, если x lj] O.V j є N . В противном случае будем говорить, что ДБР — вырожденное. Важнейшее следствие заключается в том, что оптимальное решение задачи Р можно искать как ДБР. Для решения задачи ЛП будем использовать метод последовательного улучшения плана (ПУП) и один из способов его реализации — модифицированный симплексный метод, который позволяет построить последовательность ДБР задачи, на каждой итерации не ухудшая значение целевой функции. Представим основные этапы метода последовательного улучшения плана [33, 34].
Задачи линейного программирования с ограниченным количеством базисных переменных
Чтобы сформулировать задачу ЛП с ограниченным количеством базисных переменных (далее ЛП с ОКБП) в общем виде, рассмотрим задачу ЛП Р формирования оптимального плана раскроев с множеством М = 1.-771 ограничений, N = 1..п переменных, матрицей ограничений А (га х п) и векторами Ь 0, с 0 и х соответствующей размерности
Задача (1.5.1 -1.5.8) из первой главы аналогична поставленной задаче. Следуя содержанию задачи, коэффициенты матрицы Ац О, следовательно, можно ограничиться случаем ЬІ О для каждого і Є М. Будем также считать, что ограничения задачи (3.2.1) совместны, х — ее оптимальное решение, z = сх — оптимальное значение целевой функции. Будем считать, что матрица ограничений этой задачи невырождена и имеет полный ранг. Каноническая форма этой задачи такова:
Множество переменных задачи (3.2.1) составляет N — N + М, базисных переменных N С N, где \N \ — га. Среди переменных множества присутствуют как переменные основной задачи Nx С N (основные базисные столбцы), так и орты Ny С М (дополнительные базисные столбцы), N = N x 4- Ny. В силу предположения о невырожденности всех базисных решений задачи ж[Л ], у[Щ] 0 для любого базисного множества N . Важная особенность — целевая функция рассматриваемой задачи обязательно ограничена (снизу).
Цель данного исследования — поиск оптимального плана (ж , у ) этой задачи с дополнительным условием которому соответствует оптимальное значение целевой функции zfky Данное условие соответствует ограничению (1.5.10) для задачи, поставленной в первой главе. Полученную задачу обозначим Р& и будем называть задачей ЛП с ограниченным количеством базисных переменных основной матрицы. Задачу (3.2.1) или (3.2.2) будем называть базовой по отношению к данной задаче ОКБП, число к — рангом базиса задачи. Следует оговорить некоторую условность в названии класса рассматриваемых задач — ранг матрицы определяет лишь \NX\ — количество основных столбцов матрицы ограничений, общее количество базисных переменных (основных столбцов N x и Ny), разумеется, всегда составляет т [66, 67].
Отметим, что если \N X \ к, то решение Pk совпадает с решением Р. Сложности возникают в случае Л „ к, который и будет рассматриваться в данном разделе.
Кроме того, в данном разделе не будут рассматриваться методы, основанные на сведении данной задачи к задаче смешанного целочисленного линейного программирования, с последующим применением стандартных или адаптированных методов решения задач этого класса. Такие алгоритмы, как правило, предполагают использование булевских 0-1 переменных и неэффективны в случае практически интересного большого количества столбцов матрицы ограничений. Необходимо отметить некоторые особенности рассматриваемой задачи.
В основе рассматриваемой задачи понятие базисного плана задачи ЛП, что фактически исключает возможность ее решения без использования средств линейной алгебры и линейного программирования. С другой стороны, исследование базисных решений этой задачи привносит в ее содержание элемент дискретности (количество базисных множеств не превосходит С ), который удобно использовать для организации алгоритмов частичного перебора.
Для любой задачи ЛП (3.2.1) или (3.2.2) имеется целое ко, такое, что рассматриваемая задача имеет допустимое решение только для к ко. Таким образом, необходимо рассматривать подмножества Nx С N для которых ко \NX\ к, что принципиально противоречит концепции независимого множества матроида. В связи с этим необходима определенная, представленная далее, корректировка условий этой задачи. Оптимальное значение целевой функции решения задачи с ОКБП является компромиссом между качеством решения базовой задачи ЛП и рангом базисного плана задачи. С этой точки зрения рассматриваемая задача является двухцелевой с противоречивыми функциями цели [9, 30, 52, 53, 54, 55, 76, 77, 81]. Ограничение количества основных столбцов практически неизбежно приводит к снижению возможностей выбора плана и, тем самым, к увеличению числа дополнительных переменных у, векторная природа которых приводит к появлению целой серии задач оптимизации с различными критериями эффективности и дополнительными ограничениями, среди которых
Модуль регистрации заявок заказчиков и формирования производственных заказов
С использованием модуля автоматизируется ведение поступающих от заказчиков заявок на изготовление продукции и ведение связанных с ними производственных заказов.
Процесс регистрации начинается с получения специалистом отдела логистики и продаж от заказчика заявки на изготовление одного или нескольких изделий из гофрокартона. Пользователь должен создать документ «заявка заказчика» и указать основные характеристики заявки. Затем необходимо заполнить позиции документа для каждой номенклатуры, указанной в заявке. Для каждой позиции заявки пользователь имеет возможность: указать особые условия («без упаковки», «без печати»); изменить предварительную дату отгрузки, отличную от предварительной даты отгрузки всей заявки; запустить автоматический расчет количество изделий исходя из условия упаковки на целое число паллет.
В заявке, в качестве позиции, заказчик может указать номенклатуру, которая является составным изделием, но для планирования работы производства по выполнению заявки необходимо иметь информацию обо всех атомарных изделиях входящих в состав заявки, поэтому автоматически выполняется детализация заявки - на основании состава изделия позиции заявки указывается весь список атомарных изделий (с указанием количества), требующихся для ее выполнения. Алгоритм работы с документом «заявка заказчика» следующий: Шаг 1. Найти или создать новый документ «заявка заказчика». Шаг 2. Редактировать документ «заявка заказчика». Шаг 3. Детализировать позиции документа «заявка заказчика». Шаг 4. Редактировать детализацию документа «заявка заказчика». Шаг 5. Рассчитать количество позиции заявки для выпуска целого числа паллет.
Шаг 6. Сформировать документы «производственный заказ» на основании позиций заявки.
Процесе формирования производственных заказов начинается с подтверждения факта приемки заявки к производству. При формировании заказа, основные характеристики технологической карты изделия копируются в характеристики производственного заказ, так как на этапе планирования некоторые параметры разрешено корректировать, но изменения должны сохраняться только для текущего планирования, и не затрагивать справочные данные. При редактировании кроме технических характеристик можно изменить категорию срочности изделия, количество и планируемую дату отгрузки продукции покупателю. Данные модуля регистрации заявок являются исходными для модулей планирования. В модуль планирования поступает информация о заказах, которые необходимо выпустить в указанный период.
С использованием модуля автоматизируется ведение архива технологических карт и сопутствующих им документов, ведение справочных данным по характеристикам используемого на Предприятии оборудования, обеспечивается актуальное представление документов на изделия или оборудование всем пользователям Системы.
При получении от заказчика заявки на изготовление нового изделия, специалисты отдела логистики перенаправляют ее в производственный отдел для разработки технологической карты изделия. Специалист производственного отдела должен создать новый элемент справочника номенклатуры, в котором указывается наименование нового изделия, тип изделия и имя заказчика. Если в заявке указано изделие с составными элементами (комплект), специалист создает новые элементы в справочнике номенклатуры для каждого элемента комплекта (если это необходимо). Примечание: обычно в комплекте используются стандартные изделия, номенклатура для которых уже создана.
После создания элемента справочника номенклатуры для нового изделия, специалист создает новый элемент справочника технологических карт. Для каждого элемента номенклатуры может быть создана только одна технологическая карта. После создания технологической карты специалист должен ввести основные характеристики нового изделия (размеры изделия, размеры заготовки, необходимое сырье и т. д.), ввести структуру изделия, ввести вид и схему укладки на поддон, указать набор операции и оборудования необходимых для получения готового изделия.
После согласования всех данных технологической карты внутри предприятия и с заказчиком, изделие может быть запущено в производство. Технологическая карта и ее файлы доступны всем заинтересованным лицам предприятия для просмотра и печати. Алгоритм работы с документом «технологическая карта» следующий:
Найти или создать новый документ «технологическая карта». Шаг 2. Редактировать технологическую карту. Шаг 2.1. Ввести характеристики изделия. Запустить автоматический расчет размеров заготовок и значений рилевок. Ввести схему укладки изделия. Шаг 2.4. Ввести структуру изделия.
Ввести операции для получения готового изделия. Шаг 2.6. Прикрепить файлы комплекта документов. Шаг 3. Просмотреть журнал изменений характеристик технологической карты. Шаг 4. Вывести на печать документы по технологической карте.
Справочник «Оборудование» предназначен для хранения характеристик используемого на предприятии оборудования. В целях экономии, на предприятии могут некоторое оборудование объединять в пары и устанавливать на них общие печатные секции. Это означает, что при необходимости печатная секция может быть перемещена с одного оборудования на другое. При определении последовательности заказов, обрабатываемых на таком оборудовании необходимо избегать ситуаций с необходимостью использования общего элемента на двух агрегатах сразу. Алгоритм работы с элементом справочника «оборудование» следующий: Шаг 1. Найти или создать новый элемент «оборудование». Шаг 2. Редактировать характеристики оборудования. Шаг 2.1. Ввести технические характеристики оборудования. Шаг 2.2. Ввести список планово-профилактических работ. Шаг 2.3. Указать зависимое оборудование.
