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

на правах рутписи

МАЗАНОВ Павел Георгиевич

ОПТИМИЗАЦИЯ РАСКРОЯ РУЛОННЫХ ТКАНЕЙ (на примере ОАО "Тверская швейная фабрика")

Специальность 05.13.06 - Автоматизация и управление технологическими процессами и производствами (в промышленности)

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

Тверь 2006

Работа выполнена в Тверском государственном техническом университете

Научный руководитель - кандидат технических наук, профессор, Комиссарчик В.Ф.

Официальные оппоненты:

доктор технических наук, профессор Григорьев В.А. кандидат технических наук, доцент Полтавцев А.А.

Ведущая организация: ОАО "Тверская швейная фабрика", г. Тверь

Защита состоится 3 ! ¿¿а^лШ- / 200 £ г. в & часов на заседании диссертационного совета Д 212.262.04 при Тверском государственном техническом университете по адресу: 170026, г.Тверь, наб. Афанасия Никитина, 22, ауд. Ц-212

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

Автореферат разослан / 200^ г

Ученый секретарь диссертационного совета

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

Актуальность темы исследования. Технико-экономические показатели производства определяют конкурентоспособность предприятия в рыночной экономике. Одним из путей повышения технико-экономических показателей швейного производства является оптимизация раскроя ткани за счет уменьшения отходов. Повышение эффективности швейного производства тесно связано с автоматизацией производства и управления, широким использованием экономико-математических методов и ЭВМ. Как показали исследования, использование систем автоматизации подготовительно-раскройного производства не только снижает затраты на производство одежды, но и повышаете ее качество, степень использования материалов - при экономии материалов на 1-2%, прибыль возрастает на 5-7%.

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

1. Математическая постановка задачи оптимального раскроя рулонных тканей на ОАО "Тверская швейная фабрика" (далее ОАО "ТШФ") с учетом особенностей технологии раскроя - наличие различных типов пороков ткани и "красных" полотен, обеспечение равномерности настила и определенной нормированной разности между соседними столами.

2. Разработка модифицированных алгоритмов и методов решения задач целочисленного линейного программирования (ЦЛП) и связанных с ними задач линейного программирования (ЛП).

3. Разработка и реализация программного обеспечения решения задач ЛП и ЦЛП в расширенной постановке.

4. Разработка и реализация комплекса программного обеспечения автоматизации подготовительно-раскройного производства. Диссертационная работа выполнялась в рамках проекта создания

комплексной системы автоматизации производства ОАО "ТШФ В качестве объекта исследования в диссертационной работе выбран технологический процесс раскроя рулонных тканей подготовительно-раскройного производства на ОАО "Тверская швейная фабрика".

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

На защиту выносятся:

1. Формализация задачи оптимального раскроя рулонных тканей на ОАО "ТШФ", учитывающая особенности технологии раскроя.

2. Алгоритмы модифицированных симплекс-метода и метода "ветвей и границ" с применением процедур предварительной обработки и анализа;

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

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

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

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

3. Разработан алгоритм решения формализированных задач оптимального раскроя рулонных чгканей на ОАО "ТШФ" на базе модифицированных алгоритмов решения задач линейного и целочисленного линейного программирования, позволяющий сократить длину концевых остатков, что существенно повышает степень использования материалов.

Достоверность и обоснованность подтверждается грамотным использованием математического аппарата, применением теории математического программирования, методологий создания программного обеспечения, критическим анализом специальной литературы по математическому программированию и по постановкам и методам решения задач раскроя, глубоким изучением технологического процесса раскроя ткани на ОАО "ТШФ", совпадением теоретических расчетов с данными, полученными на расчете реального раскроя ткани.

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

1. Возможность использования разработанных модифицированных алгоритмов решения задач ЛП и ЦЛП с различными типами ограничений.

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

3. Разработанный комплекс программных средств позволяет повысить коэффициент использования материала на 5-10% и сократить количество и длины концевых остатков, результатом чего является снижение отходов производства на 3-7%.

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

Апробация результатов работы. Основные результаты работы докладывались и обсуждались на международной научно-технической конференции "Компьютерные технологии в управлении, диагностике и образовании" (Тверь, 2002), заседаниях и семинарах кафедры "Автоматизации технологических процессов и производств" Тверского государственного технического университета.

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

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

Работа изложена на 142 страницах машинописного текста, кроме того, содержит 39 рисунков и 15 таблиц. Библиографический список включает 111 наименований и занимает 8 страниц.

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

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

В первой главе приводятся краткие сведение об ОАО "ТШФ", выполнено описание объекта исследования, производится классификация задач раскроя на основе известных и общепринятых классификациях Н. ВукЪо!Т и Мухачевой ЭЛ., формализация и математическая постановка задач оптимального раскроя ткани. Также произведен обзор научных работ по решению задач оптимального раскроя и созданию систем автоматизации швейного производства.

Объектом исследования является технологический процесс раскроя рулонных тканей подоотовительно-раскройного производства на ОАО "ТШФ". Задача оптимального раскроя рулонных тканей заключается в минимизации отходов (концевых остатков) при выполнении установленного плана на выпуск изделий. Помимо этого, требуется обеспечить равномерность настила. Равномерность настила обеспечивается определенной разностью толщины соседних столов. Равномерность нашила позволяет минимизировать потери на прогибе ткани. Норма разности высоты столов зависит от типа ткани. При равномерности настила дополнительно достигается наличие так называемых сквозных полотен. Сквозные полотна - это способ настила ткани, при котором количество пустых столов (не настеленных) сводится к нулю, т.е. непрерывный настил нескольких подряд идущих столов. Равномерность настила и наличие сквозных полотен - важные технологические критерии, которые дают

экономический и технологический эффекты. Технологическая схема настила и раскроя ткани на раскройном столе представлена на рис.1.

стол 3

стоп 4

стол 5

РАСКРОЙНЫЙ СТОЛ:

Рис.1. Технология настила ткани на раскройный стол.

Каждому столу соответствует свой тип раскладки. 4-ый настил является сквозным настилом. Общий настил можно считать равномерным - высота настила ткани по столам составляет 4, 3,2,2 и 2.

Исходными данными для задачи раскроя являются:

• паспорта рулонов ткани (информация о длине рулонов, их количество);

• длина и количество отрезов в каждом рулоне;

• длина раскладок и их количество;

• допуски по длине настила раскладки, количество экземпляров данного типа раскладки.

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

Настил ткани на раскройный стол выполняется только с использованием тканей с одинаковыми или близкими характеристиками по составу, текстуре и толщине ткани. Высота стола обычно не превышает 40 полотен, а количество раскладок - 15 (каждому типу раскладки соответствует свой стол). Таким образом, на одном раскройном столе можно произвести раскрой не больше 600 изделий и 15 моделей изделий. Поэтому, если требуемое число изделий заказа превышает максимально возможное число раскраиваемых изделий, то такой заказ разбивается на необходимое количество частей, и каждая часть кроится отдельно.

Для формализации задачи раскроя введем следующие обозначения: п - количество типов раскладок; / - номер типа раскладки, ¡-йп) с, - длина /-го типа раскладки с учетом соответствующего допуска по длине;

m¡ - требуемое количество экземпляров i-то типа раскладки; М - количество рулонов ткани; к - номер рулона ткани, к - 1М; Nk - количество отрезов (участков без порока) в £-ом рулоне ткани;

м

К = ^¡Гл^ - общее количество отрезов во всех М рулонах; i-i

jk - номер отреза в к -ом рулоне ткани, jk = 1 ,Nk;

Lk - длина к -го рулона ткани; lJt - длина jk -го отреза к -го рулона ткани;

ÉU

/Л - длина к -го рулона; I = ]T¿, - длина всех м рулонов; л-1 " »->

- фактическое количество экземпляров i-го типа раскладки на у,-ом отрезе к -ого рулона ткани;

я

£ с, х^ - длина полезно используемой ткани при крое jk- го отреза £-го рулона

ы

ткани для всех типов раскладок;

Ё н

- длина полезно используемой ткани при крое к-го рулона ткани

Л-1 i-I

для всех типов раскладок;

и«. я

£ £ Xе' 'xtj, ~ Длина всей полезно используемой ткани при крое м рулонов *=>1 (-1

ткани для всех типов раскладок.

Задача (ЗАДАЧА I) оптимального раскроя формализируется в следующем виде:

и Д п

maxz'=£ £ (1)

при ограничениях:

(2)

ограничение по длине используемой ткани на -ом отрезе, = 1,//, (К ограничений);

м К

(3)

*-1 1,-1

ограничение на план выпуска для всех типов раскладок на всех рулонах;

х^ег, / = й, * = (4)

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

Введем дополнительные обозначения: А - норма разности высот столов, А = 2+7;

мл -тах{л!) } - максимальная высота настила при крое ^t-гo отреза, л = 1, ; <1Н =тга{*й} - минимальная высота настила при крое -го отреза, }\ = I, Л^ ;

т;л - минимально требуемое количество экземпляров /-го типа раскладки при раскрое у4-го отреза; т"и - максимально требуемое количество экземпляров I-го типа раскладки при раскрое у, -го отреза;

К =к -х>пл\ " разность высот настилов между соседними столами при

1 = 1,11-1.

Тогда равномерность настила обеспечивается при выполнении ряда следующих условий. Минимально требуемое количество экземпляров /-го типа раскладки т* определяется следующим образом:

< =

О, При ! = 1,^=1,^ = 1

(5)

(6)

К-1"Р" />1-Л >!.*>!' а максимально требуемое т) :

И, при » = 1,у„=1,* = 1 т"щ = 0, при нЛ_, = дсй.„/ > 1,л > > 1

.л-*й-1+</л-|» "Ж' «л-1 ^ >>!.*>! Разность высоты настилов между соседними столами не должна превышать нормы разности высот к:

с,.,, <А _

(7)

, при / = 1,и-1.

Задача (ЗАДАЧА II) оптимального раскроя для к-го рулона ткани формализуется следующим образом:

Л "

шах г'' = £

Л-1 '-1

при ограничениях:

(8)

(9)

ограничение по длине используемой ткани на у4-ом отрезе, ¡к = 1, Л'^, л^ ограничений;

Г*. _ _

л л ,при/ = 1>л-1,л=1,лг, (10)

\ - "

ограничение на разность высоты настила между соседними столами при раскрое у,-го отреза к -го рулона, (я -1) ■ Ык ограничений;

'"I

Ё**-Ё

А"1

хми ^ *

, при ¿ = 1,и-1

(П)

+1Л

Л-1

ограничение на разность высоты настила между соседними столами при раскрое к -го рулона, (и-\)-ык ограничений;

дс^ег, ¡ = Т~а. к=ъм (12)

ограничение на целочисленность количества экземпляров каждого типа раскладки.

Каждая задача (ЗАДАЧА Ш) последовательности задач оптимального раскроя ]к -го отреза к -го рулона ткани формализируется следующим образом:

шах z"'

jk

(13)

ы

(И)

.и

ограничение по длине используемой ткани на jt -ом отрезе;

J15)

ограничение на план выпуска для /-го типа раскладки на всех рулонах, / = 1, л, п ограничений;

х — х, < h -

х ' <А'ПРИ' = 1'"-1 (»б)

ограничение на разность высоты настила между соседними столами при раскрое jk-го отреза ¿-го рулона, (и-1) ограничений;

хп eZ, Jk=lNt, i = ü, * = Ш (17)

ограничение на целочисленность количества экземпляров каждого типа раскладки.

Постановка трех задач обусловлена технологическими особенностями задачи раскроя рулонных тканей на ОАО "ТШФ". Задача I соответствует задаче оптимального раскроя ткани для всех типов раскладки для всех рулонов ткани без учета технологических ограничений, т.е. является задачей нахождения глобального оптимума. Т.к. заранее неизвестна конфигурация рулопов ткани (количество и тип пороков и отрезов) и расчет оптимального раскроя производится в интерактивном режиме, то возможно решать только задачу II и задачу III. Задача II соответствует задачи оптимального раскроя одного рулона ткани с учетом технологических ограничений. Для полного контроля расчета со стороны пользователя и обеспечения лучшей равномерности настила и наличия сквозных полотен решается задача I, соответствующая оптимальному раскрою одного чистого отреза одного рулона ткани. Решение задачи I является оценочным для соответствующего набора решений задач II, а решение задачи II - для набора решений задач III.

Для решения задач II как задачи ЦЛП необходимо осуществить переход от двухмерной суммы целевой функции к одномерной. Для перехода введем следующие обозначения:

S~n-Nt - общее количество всех типов раскладок для к -го рулона ткани;

p-(jk-\)n+i - номер типа раскладки, p = l,S, l = п, Jk=\,Nk;

t = jt- номер отреза рулона ткани, t = \,Nt, jk = l,Nk;

qp = c: - длина раскладки, где p = {jk -1) ■ n+i;

yp = xiJt - количество экземпляров раскладки, где р = (jk -1) • я+i.

В итоге получим следующие преобразованные задачи II - задачи II*:

р- I

при ограничениях:

Ё (19)

ограничение по длине используемой ткани на /-ом отрезе, ЛГ,

ограничений;

Р'^^.прн р = (/-1).ц,м.-1, г = Щ" (20)

ограничение на разность высоты настилов между соседними столами при раскрое г -го отреза рулона ткани, (я -1) ■ Л^ ограничений;

' ЛГ, /V,

м

/ . • ■; г 1>.я |-1

,нри р = 1,и-1 (21)

ограничение на разность высоты настила между соседними столами при раскрое рулона, (п-1) ограничений;

к = йм (22)

ограничение на целочисленность количества экземпляров каждого типа раскладки.

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

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

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

пгах г(х) - стх А^-х^Ь1

Л^-хЪЬ1 (23)

с,1,и,Ъ еЛ;*е/г

Задача ЦЛП в наиболее общей постановке формулируется следующим образом:

max z(x) = стх А2-х = Ъ1

A1x^bl (24)

c,l,u,beR; jteZ xJ,l),uj>0J = \,n,i = \,m

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

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

Также в диссертационной работе бьши рассмотрены процедуры предварительной обработки и анализа (Preprocessing & Probing Techniques). Данные процедуры повышают эффективность применения симплекс-метода за счет предварительной обработки и анализа поставленной задачи ЛП.

В третьей главе произведены разработка, полное описание и блок-схемы модифицированных алгоритмов решения задачи ЛП в общей форме и задачи ЦЛП: двухэтапный расширенный модифицированный (ДРМ) симплекс-метод и метод "ветвей и границ" с применением ДРМ симплекс-метода для решения релаксаций (задача без учета целочисленности переменных), процедур предварительной обработки и анализа на предварительном этапе, комбинации различных способов выбора переменной ветвления, осуществления ветвления и возврата по дереву ветвлений.

Основными преимуществами ДРМ симплекс-метода являются:

• применение на предварительном (до итераций симплекс-метода) этапе процедур предварительной обработки и анализа;

• учет верхних и нижних границ на переменные, учет наличия в постановке задачи ограничений типа"=" и ">";

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

• использование сокращенной формы записи симплекс-таблицы. На рис.2 представлена блок-схема алгоритма ДРМ симплекс-метода.

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

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

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

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

Выбор ведущего столбца осуществляется по следующим формулам:

(Ъ. . Ь, [и, -Ъг Щ-Ь,

— = mm,„ . — ——- = min,„„ ,„ ——L

а„ aa , если есть a„ > 0, S2 = -a„ ] " ~aa , если есть aa <0

od oo

где 5 - относительная оценка базисной переменной, и, - верхняя граница базисной переменной г -ой строки (ведущей), и, - верхняя граница свободной переменной «-ого столбца (ведущего).

Если 8 = 8^ то выполнить симплекс преобразование, где ап - ведущий элемент, [/-,5] - ведущая ячейка симплекс-таблицы, г - ведущая строка симплекс-таблицы, 5 - ведущий столбец:

<$j -us, 5 = min{<J,,(S2,iS:

а..—/ ¿s \/ar„i = r,j = s

о.

а„

Л а

) | г*

поменять местами обозначения выводимой и вводимой в базис переменных.

Если 8 = 51, то выполнить симплекс-преобразование, где ап - ведущий элемент, [г,$] - ведущая ячейка симплекс-таблицы, г - ведущая строка симплекс-таблицы, $ - ведущий столбец: а.

а„

а..

IЪ-Ь-

I",---Ьг,1*Г

Ъг1а„,1 = г

а_ :

а.. = -а,.

.54

ап

поменять местами обозначения выводимой и вводимой в базис переменных.

Если 5 - 5г, то выполнить преобразование свободной переменной и базиса по формулам:

Ь1=Ь,-и,-ан а = —а

НАЧАЛО

выполнить ПРОЦЕДУРЫ ПРЕДВАРИТЕЛЬНОЙ ОБРАБОТКИ И АНАЛИЗА

НА1

ведущую СТРОКУ, ИНДЕКС ПЕРВКННОЙ ВЫВОДИМОЙ ИЗ БАЗИС*

ОСТАНОВ РЕШЕНИЕ НАЙДЕНО

ВЕДУЩИЙ СТОЛБЕЦ, ИНДЕКС ПЕРЕМЕННОЙ ВВОДИМОЙ в БАЗИС

НАЧАТЬ I ЭТАП ВВЕСТИ ИСКУССТВЕННЫЕ ПЕРЕМЕННЫЕ И ЦЕЛЕВУЮ •ункимо

__йти

ВЕДУЩИЙ СТОЛБЕЦ, ИНДЕКС ПЕРЕМЕННОЙ ВВОДИМОЙ В БАЗИС

ОПРЕДЕЛИТЬ ВЕДУЩИЙ ЭЛЕМЕНТ выполнить

СИМЛЛЕКС-ПРЕ ОБРАЗОВАНИЕ

ВЫПОЛНИТЬ ПРОЦЕДУРУ ПЕРЕХОДА И ОПРЕДЕЛИТЬ ДОПУСТИМОСТЬ СИМПЛЕКС-ТАБЛИЦЫ

ОСТАНОВ ФУНКЦИЯ НЕ ОГРАНИЧЕНА ДОПУСТИМАЯ ОБЛАСТЬ ОТКРЫТА

ВЕДУЩУЮ СТРОКУ, ИНДЕКС ПЕРЕМЕННОЙ ВЫВОДИМОЙ ИЗ БАЗИСА

ОПРЕДЕЛИТЬ ВЕДУЩИЙ ЭЛЕМЕНТ ВЫПОЛНИТЬ СИМПЛЕКС-ПРЕОБВАЗОВАНИС

Рис.2. Блок-схема алгоритма ДРМ симплекс-метода.

На рис.3 представлена блок-схема алгоритма применения процедур предварительной обработки и анализа.

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

Процедуры предварительной обработки и анализа применяются однократно до начала выполнения ДРМ симплекс-метода при решения задачи ЛП. При решении задачи ЦЛП процедуры предварительной обработки и анализа применяются только для первой релаксации.

На рис.4 представлена блок-схема модифицированного алгоритма метода "ветвей и границ".

рис.4. Блок-схема алгоритма модифицированного метода "ветвей и границ".

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

В таблице 1 представлены основные процедуры выбора переменной, ветвления, и возврата по дереву ветвлений

Таблица 1.

Процедуры и правила ветвления

Процедуры и правила ветвления Процедуры возврата по дереву ветвлений

1. Наибольшее (наименьшее) отклонение от целого, или значение величины дробной части. (Most/Least Infeasible Integer Variable). 1. Поиск преимущественно в глубину ("сначала вглубь ") с переборным возвратом (Depth-First-Search with Backtracking).

2. Штрафы Дриебека-Томлина (Driebeck-Tomlin Penalties). 2. Наилучшая граница (Best-Bound).

3. Псевдо-стоимостные оценки (Pseudo-Cost Estimate). 3. Сумма отклонений от целого (Sum ofInteger lnfeasibilities).

4. Псевдо-теневые стоимости (Pseudo-Shadow Prices). 4. Наилучшая оценка с использованием псевдо-стоимостей (Best-Estimate using Pseudo-Costs).

5. Строгое ветвление (Strong Branching). 5. Наилучшая оценка с использованием псевдо-теневых стоимостей (Best-Estimate using Pseudo-Shadow Prices).

6. Выбор на основании приоритетов (Priorities Selections). 6. Наилучшая проекция (Best Projection).

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

В четвертой главе выполнен обзор программных средств решения задач ЦЛП и задач раскроя, описание и разработка комплекса программного обеспечения автоматизации подготовительно-раскройного производства ОАО "ТШФ ". На рис.5 представлена структурная схема разработанного комплекса программных обеспечения (КПО) "Оптимальный раскрой".

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

входные документы (информационный

поток)

приложения-клиенты:

- учет лиан -нормирование ткани - графнк-гаданве

• расчет раскроя ткан*

выходные

документы (информационный

поток)

сервер расчета оптимального раскроя "ОРПМ CUT SERVER'

сервер приложений DB APPLICATION SERVER'

П

П

Млмша решения мдп ЛП я ЦЛП

БД "INVESTRONICA'

БД "CUT"

Рис.5 Структурная схема КПО "Оптимальный раскрой".

Основными характеристиками КПО "Оптимальный раскрой" являются:

• открытость исходных текстов всех компонентов;

• поддержка сетевого взаимодействия всеми модулями системы;

• единая база данных;

• возможность модернизации и развития;

• возможность интеграция с другим программным обеспечением (бухгалтерское ПО, КПО "Investronica" и др.)

• модульность - состоит из отдельных компонентов, взаимодействующих по промышленным стандартам DCOM/COM/RPC;

• выполнение в среде операционных систем MS Windows;

• графический интерфейс компонентов пользовательского уровня (клиентское ПО);

• дружелюбность и интуитивность интерфейса пользовательского

• простота и удобство развертывания (установки) новых рабочих

В пятой главе произведен анализ и испытания разработанного комплекса программных средств. Преимущества КПО "Оптимальный раскрой":

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

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

программного обеспечения таких, как DCOM/COM, ADO, STL, ATL, T-SQL.

уровня;

мест.

3. Модули КПО "Оптимальный раскрой": сервер приложений "DB Application Server" и сервер расчета "OptimCut Server" - обеспечивают защищенное исполнение реализованных алгоритмов и бизнес-логики для каждого клиентского приложения.

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

5. КПО "Оптимальный раскрой" имеет консолидированный, единый экземпляр базы данных - "CUT", которая реализована на платформе СУБД MS SQL 2000 Server.

6. КПО "Оптимальный раскрой" обеспечивает дополнительные функциональные возможности - АРМ "Оператор-нормировщик", АРМ "Технолог", АРМ "Управление", АРМ "Администратор".

7. КПО "Оптимальный раскрой" интегрирован и взаимодействует с используемым КПО "INVESTRONICA" и "Турбо-бухгалтер".

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

1. Обоснована актуальность постановки и решения задачи оптимального раскроя ткани на ОАО "ТШФ" на базе произведенного анализа рассмотренной в работе литературы.

2. Выполнены математические постановки задач оптимального раскроя рулонных тканей на ОАО "ТШФ" с учетом обеспечения равномерности настила, наличия сквозных и "красных" полотен.

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

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

5. Разработан КПО "Оптимальный раскрой", характеризующийся модульным построением, базирующийся на современных технологиях разработки и реализации СУБД и распределенных программ.

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

7. КПО "Оптимальный раскрой" позволяет повысить коэффициент использования материала на 5-10% и сократить количество и длины концевых остатков, результатом чего является снижение отходов производства на 3-7%.

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

1. Формализация задачи оптимального раскроя рулонных тканей на ОАО "Тверская швейная фабрика", Сборник научных трудов ТГТУ "Компьютерные технологии в управлении, диагностике и образовании", г. Тверь, 2002г., ТГТУ.

2. Об одном алгоритме решения задачи линейного программирования", Сборник научных трудов "Компьютерные технологии в управлении и диагностике", г. Тверь, 2004г., ТГТУ.

3. Модифицикация стандартного алгоритма метода "ветвей и границ", Тверской государственный технический университет, деп. в ВИНИТИ, 2006г. (в печати)

4. Применение процедур предварительной обработки и анализа при решении задач ЦЛП", Тверской государственный технический университет, деп. в ВИНИТИ, 2006г. (в печати)

5. Комплекс программного обеспечения "Оптимальный раскрой", Тверской государственный технический университет, деп. в ВИНИТИ, 2006г. (в печати)

¿роса

№-2796

I

Подписано в печать 31.01.06

Физ.печ.л.1,25_Заказ № 24_Тираж 100 экз.

Типография ТГТУ

ВВЕДЕНИЕ.

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

1.1. Технологическая схема раскроя тканей и существующая система управления (СУ) на ОАО "Тверская швейная фабрика".

1.2. Классификация задач раскроя.

1.3. Обзор литературы по постановкам и методам решения задач раскроя.

1.4. Постановка задачи оптимального раскроя.

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

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

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

2.2.1. Метод ветвей и границ.

2.2.2. Методы отсечений.

2.3. Процедуры предварительной обработки и анализа.

ГЛАВА 3. РАЗРАБОТКА МОДИФИЦИРОВАННОГО АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ ЦЛП.

3.1. Разработка и особенности модифицированного алгоритма решения задачи ЛП.

3.2. Разработка и особенности модифицированного алгоритма решения задачи ЦЛП.

ГЛАВА 4. РАЗРАБОТКА ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ СИСТЕМЫ АВТОМАТИЗАЦИИ ПОДГОТОВИТЕЛЬНО-РАСКРОЙНОГО ПРОИЗВОДСТВА.

4.1. Обзор программных средств по решению задач ЛП и ЦЛП.

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

4.3. Описание комплекса программного обеспечения системы автоматизации подготовительно-раскройного производства на ОАО "ТШФ".

4.4. Разработка комплекса программного обеспечения системы автоматизации подготовительно-раскройного производства.

ГЛАВА 5. СРАВНИТЕЛЬНЫЕ АНАЛИЗ И РЕЗУЛЬТАТЫ ВНЕДРЕНИЯ РАЗРАБОТАННЫХ АЛГОРИТМОВ И ПРОГРАММНЫХ СРЕДСТВ.

5.1. Анализ результатов применения ДРМ симплекс-метода для решения задач ЛП.

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

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

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

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

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

Решение вопросов повышения конкурентоспособности и снижения себестоимости выпускаемой продукции в значительной степени связано с автоматизацией работ на этапе подготовительного производства. Одним из путей повышения технико-экономических показателей швейного производства является оптимизация раскроя ткани за счет уменьшения отходов. Как показали исследования, использование систем автоматизации подготовительно-раскройного производства не только снижает затраты на производство одежды, повышаете ее качество, но существенно повышает степень использования материалов - при экономии материалов на 1-2% прибыль возрастает на 5-7%. По оценке [15] свыше 1500 предприятий швейной промышленности России производят раскрой рулонных тканей и перерабатывают в год на сумму около 30 млрд. рублей. Под данным исследований ведущих фирм по производству настилочно-раскройных комплексов и систем автоматизированного проектирования швейной промышленности, суммарные технологические отходы (потери) швейных изделий составляют в среднем 26%. Данные отходы распределяют:

1. 17,4% - межлекальные отходы;

2. 1,5% - потери по ширине ткани;

3. 1,5% — потери при настилании ткани;

4. 2,9% — потери при расчете кусков ткани в настилы;

5. 2,4% - брак в ткани.

Суммарная стоимость технологических отходов [15] от перерабатываемых в России материалов (при 26% отходов) составляет примерно 7,8 млрд. рублей.

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

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

Данная цель предполагает решение следующих задач:

1. Математическая постановка задачи оптимального раскроя рулонных тканей на ОАО "Тверская швейная фабрика" (далее ОАО "ТШФ") с учетом особенностей технологии раскроя - наличие различных типов пороков ткани и "красных" полотен, обеспечение равномерности настила и определенной нормированной разности между соседними столами.

2. Разработка модифицированных алгоритмов и методов решения задач целочисленного линейного программирования (ЦЛП) и связанных с ними задач линейного программирования (ЛП).

3. Разработка и реализация программного обеспечения решения задач ЛП и ЦЛП в расширенной постановке.

4. Разработка и реализация комплекса программного обеспечения автоматизации подготовительно-раскройного производства.

Диссертационная работа выполнялась в рамках проекта создания комплексной системы автоматизации производства ОАО "Тверская швейная фабрика". В качестве объекта исследования в диссертационной работе выбран технологический процесс раскроя рулонных тканей подготовительно-раскройного производства на ОАО "Тверская швейная фабрика".

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

На защиту выносятся:

1. Формализация задачи оптимального раскроя рулонных тканей на ОАО "ТШФ", учитывающая особенности технологии раскроя.

2. Алгоритмы модифицированных симплекс-метода и метода "ветвей и границ" с применением процедур предварительной обработки и анализа;

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

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

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

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

3. Разработан алгоритм решения формализированных задач оптимального раскроя рулонных тканей на ОАО "ТШФ" на базе модифицированных алгоритмов решения задач линейного и целочисленного линейного программирования, позволяющий сократить длину концевых остатков, что существенно повышает степень использования материалов.

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

1. Использование разработанных модифицированных алгоритмов решения задач ЛП и ЦЛП для решения широкого класса аналогичных задач;

2. Применение подхода проектирования и создания программных средств автоматизации подготовительно-раскройного производства;

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

4. Разработанный комплекс программных средств позволяет повысить коэффициент использования материала на 5-10% и сократить количество и длины концевых остатков, результатом чего является снижение отходов производства на 3-7%;

5. Разработанный комплекс программных средств позволяет быстро и эффективно строить карты расчета и раскроя материала с предоставлением различных вариантов;

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

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

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

Структура и объем диссертации. Данная диссертация состоит из введения, пяти глав, заключения и приложения, включающих табличные результаты, краткое техническое задание. Работа изложена на 142 страницах машинописного текста, кроме того, содержит 39 рисунков и 15 таблиц. Библиографический список включает 111 наименования и занимает 8 страниц.

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

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

Базируясь на разработанной библиотеки решения задач ЛП и ЦЛП "OptimLib", было разработано эффективное программное средство расчета оптимального раскроя рулонных тканей "OptimCut".

В свою программное средство "OptimCut" является модулем разработанного комплекса программных средств "Оптимальный раскрой", которое автоматизировало информационные потоки и процессы подготовительно-раскройного производства на ОАО "Тверская швейная фабрика", объединила информационные системы управления (бухгалтерия, инженерные службы ИТР) "Турбо-Бухгалтер" и АСУ ТП "Investronica".

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

1. Акулич И. JI. Математическое программирование в примерах и задачах. М. Высшая школа, 1986.

2. Аравинд Кореа, Стивен Фрейзер и др. Visual С++.NET: пособие для разработчиков С++. М.: из-во "ЛОРИ", 2003 г.

3. Банди Б. Основы линейного программирования. Пер. с англ. М. Радио и связь, 1989.

4. Бошемин Боб., Основы ADO.NET. М.: изд. д. "Вильяме", 2003г.

5. Буч УГ- Объектно-оринетированный анализ и проектирование м примерами приложений на С++, 2-е изд., Спб., М.: изд-во "Невский диалект", "Бином", 1999г.

6. Валеева А.Ф., Гареев И.Р., Мухачева Э.А. Задача одномерной упаковки: рандомизированный метод динамического перебора и метод перебора с усечением. Информационные технологии. Приложение, 2003г., №2, с.2-3.

7. Вентцель Е.С. Исследование операций. М. "Советское радио", 1972.

8. Вилдермьюс Шон. Практическое использование ADO.NET. Доступ к данным в Internet., М.: изд. д. "Вильяме", 2003г.

9. Еремеев А.В., Заозерская Л.А., Колоколов А.А. Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования. INTAS проект 96-0820, ФМЦ "Интеграция".

10. Золотых Н.Ю. Нахождение вершин выпуклой оболочки целочисленных точек полиэдра. 22 марта 2001, http://www.nic.nnov.ru/~zny.

11. Золотых Н.Ю. О числе крайних точек в задачах целочисленного линейного программирования. НГУ им. Н.И. Лобачевского, 1997, http://www.nic.nnov.ru/~zny.

12. Канторович Л.В., Залгаллер В.А. Расчет рационального раскрой материала. Лениздат. 1951.

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

14. Коммерсант Власть, №44, 6 ноября 2001 г., http://www.inno.ru/projects/show/?id=761.

15. Комплексная система BestCut оптимальный раскрой листовых материалов. http://www.vrsoft.msk.ru/.

16. Кочетов Ю.А., Глебов Н.И., Плясунов А.В. Методы оптимизации. Новосибирск, Новосибирский Государственный Университет, 2000, http://www2.sscc.ru/Publikacii/kvpparalI.htm.

17. Кочетов Ю.А. Вероятностные методы локального поиска для задач дискретной оптимизации. Институт математики им. С.Л. Соболева СО РАН, Новосибирск.

18. Круглински Д., Уингоу С., Шеферд Дж. Программирование на Microsoft Visual С++ 6.0 для профессионалов., М.: изд-во "Русская редакция", 2001г.

19. Лейнекер Р. Энциклопедия Visual С++, Спб. изд-во "Питер", 1999г.

20. Мамаев Е., Шкарина Л. Microsoft SQL Server 2000 для профессионалов, Спб., Питер, 2001г.

21. Муртаф Б. Современное линейное программирование. Пер. с. англ. М. Мир, 1984.

22. Т 23. Мухачев а Э. А.,. Ермаченко А. И, Сиразетдинов Т. М., Жукова Т. Ю. Комплексалгоритмов и программ расчета гильотинного раскроя. Информационные технологии, 2004г., №8, с.18-25.

23. Мухачева А.С. Алгоритмы плотной упаковки прямоугольных объектов на базе аппроксимации линейным раскроем, г.Уфа, УГАТУ, 2001г.

24. Мухачева А.С. Генетический алгоритм поиска минимума в задачах двумерного гильотинного раскроя. Информационные технологии, 2001г., № 3, с.27-31.

25. Мухачева Э.А. Математическое обеспечение расчетов линейного и прямоуголного раскроя, м-лы всесоюз. семинара., г.Уфв, УФАИ, 1981г.

26. Мухачева Э.А. Методы локального поиска в дискретных задачах оптимального распределения ресурса. М-во образования РФ, УГАТУ, 2001г.

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

28. Мухачева Э.А., Валееева А.Ф., Картак В.М., Мухачева А.С. Модели и методы решения задач ортогонального раскроя и упаковки: аналитический обзор и новая технология блочных структур. Информационные технологии. 2004г. №5, приложение №5, с.2.

29. Мухачева Э.А., Верхотуров М.А., Мартынов В.В. Модели и методы рачета раскроя-упаковки геометрических объектов, г.Уфа, УГАТУ, 1998г.

30. Мухачева Э.А., Принятие решений в условиях неопределенности: межвуз. науч. сб., М-во общ. и проф. образ. РФ, г.Уфа, УГАТУ, 1999г.

31. Мухачева Э.А., Рубенштейн Г.Ш. Математическое программирование, АН СССР, Сиб. отд. Ин-т математики, г.Новосибирск, Наука, 1987г.

32. Мюллер Дж. Технология СОМ+: библиотека программиста, Спб., Питер, 2002 г.1. Г'

33. Новикова Н.М. Основы оптимизации: курс лекций. Москва, ВМиК МГУ, РФФИ No. 96-1-00786, 1998.

34. Оберг Роберт Дж., Технология СОМ+. Соновы и программирование. М.: "Вильяме", 2000г.

35. Оберг Роберт Дж., Торстейнсон, Архитектура .NET и программирование с помощью Visual С++, М.: изд. д. "Вильяме", 2002г.

36. Пол А. Объектно-ориентированное пограммировагие на С++, 2-е изд, Спб., М.: изд-во "Невский диалект", "Бином", 1999г.

37. Рихтер Дж., Кларк Дж. Программирование серверных приложений для Microsoft Windows 2000, Спб, питер, М. "Русская редакция", 2001г.

38. Родженсон Д. Основы СОМ, М.: из-во "Русская редакция", 2000г.

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

40. Страуструп Б. Язык программирования С++. М. Binom, 1999г.

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

42. Хендерсон К. Профессиональное руководство по Transact-SQL, Спб, Питер, 2005г.

43. Шайтхауер Г. Планирование одноиерного раскроя материала различной длинны на базе непрервыной релаксации и метода отсекающих плоскостей. Информационные технологии, 2004г., №1, с. 16-26

44. Шаммас Н.К. Основы С++ и объектно-ориентированного программирования., Киев, Диалектика, 1996г.

45. Эш Рофейл, Яссер Щохауд. СОМ и СОМ+. Полное руководство, К.: НТИ, М.: Энтроп, 2000г.

46. A. de Bruin, G.A.P. Kindervater, H.W.J.M. Trienekens. Asynchronous Parallel Branch and Bound and Anomalies. Erasmus University, Department of Computer Science, Rotterdam, The Netherlands, September, 1995.

47. Andersen E.D., Andersen K.D. Presolving in linear programming, Mathematical Programming # 71/2,1995, c.221-245.

48. Barbara M. Smith, Sally C. Brailsford, Peter M. Hubbard. The Progressive Party Problem: Integer Linear Programming and Constraint Programming Compared. Division of Artificial Intelligence. University of Leeds, University of Southampton.I-г

49. Branch and Bound. NEOS Guide Branch and Bound. http://www-fp.rncs.anl.gov/otc/Guide/OptWeb/discrete/integerprog/section2 1 1 .html.

50. Brian Borchers. Improved Branch and Bound Algorithm for Integer Programming. Faculty of Rensselaer Polytechnic Institute, Troy, NY, June 1992.

51. Dr. Ivan Oh. Linear Programming and Extensions. Bohazici University.

52. Dyckhoff H. A typology of cutting and packing problems. F.R. Germany, 1991r.

53. E. Balas, S. Cerria, G. Cornuejols, N. Natraj. Gomory Cuts Revisited. CGIA, Carnegie Mellon University, Graduate school of Business, Columbia University, US West Technologies, Bounlder, August 9,1994, revised April 16,1995.

54. E. Levitin, R. Tichatschke. A Branch-and-Bound Approach for Solving a Class of Generalized Semi-Infinite Programming Problems. Institute of System Analysis, Russian Academy of Science, Department of Mathematics, University of Tier.

55. Erling D. Andersen. Linear Optimization: Theory, Methods, and extensions. Department of Management, Odense University, Denmark, January 13, 1998.

56. Gabrielle Assunta Grun. Improving Integer Programming Branch and Bound Node Selection Techniques through Artificial Intelligence Methods. School of Computing Science, Simon Fraser University, Burnaby, March 14,2001.-r—''

57. H. Marchand, Alexander Martin, Robert Weismantel, Laurence Wolsey. Cutting Planes in Integer and Mixed Integer Programming. Department of Operational Research of London Scholl of Economics, Konrad-Zuse-Zentrum, October, 1999.

58. H. Marchand, Laurence A. Wolsey. Aggregation and Mixed Integer Rounding to Solve MIPs. June, 1998.

59. Harvey J. Greenberg. An Example of Cycling in the Simplex Method. University of Colorado at Denver, December 18,1998, http://www.cudenver.edu/~hgreenbe.

60. Herbert S. Wilf. Algorithm and Complexity. University of Pennsylvania, Philadelphia, Internet Edition, summer, 1994, http://www.cis.upenn.edu/wilf.

61. ILOG CPLEX Optimization Suite, White Paper, ILOG, May 2001, http://www.cplex.com. ■j 65] Integer Programming. NEOS Guide Integer Programming. http://wwwfp.mcs. anl.gov/otc/Guide/SoftwareGuide/Categories/intprog.html.1-у1. Г'

62. Istvan Maros. A General Pricing Scheme for the Simplex Method. Department of Computing Imperial College, London, ISSN 1469-4174, Department Technical Report 2001/3, March 2001.

63. Istvan Maros. A Generalized Dual Phase-2 Simplex Algorithm. Department of Computing Imperial College, London, ISSN 1469-4174, Department Technical Report 2001/2. January, 2001.

64. J. Balasubramanian, L.E. Grossmann. A Novell Branch and Bound Algorithm for Scheduling Flowshop Plants with Uncertain Processing Times. Department of Chemical Engineering, Carnegie Mellon University, Pittsburgh, January 2001 /August 2001.

65. J. Gondzio, R. Sarkissain and J.-Ph. Vial. Parallel implementation of a central decomposition method for solving large-scale planning problems. НЕС Technical Report 98.1 January 19,1998, revised August 12,1999.

66. J.T. Linderoth, M.W.P. Savelsbergh. A Computing Study of Search Strategies for Mixed Integer Programming. School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, October, 1997.

67. Jean-Pierre Goux, Sven Leyffer. Solving Large MINLPs on Computational Grids. Department of Mathematics, University of Dundee, 24 May, 2000.

68. Jens Clausen. Branch and Bounds Algorithm Principles and Examples. Department of Computer Science, University of Copenhagen, March 12, 1999.

69. John E. Mitchell, Eva K. Lee. Branch-and-bound methods for integer programming, in the Encyclopedia of Optimization, Kluwer Academic Publishers, August 2001, http ://www. rpi. edu/~m i tchj/papers .htm 1.

70. John E. Mitchell, Kartik Krishnan. A linear programming approach to semi definite programming problems, May 2001.

71. John Е. Mitchell. Branch-and-cut algorithms for integer programming, in the Encyclopedia of Optimization. Kluwer Academic Publishers, August 2001, http://www.rpi.edu/~mitchj/papers.html.

72. John E. Mitchell. Branch-and-cut methods for combinatorial optimization problems, in the Handbook of Applied Optimization, Oxford University Press, 2002, http://www.rpi.edu/~mitchj/papers.html.

73. John E. Mitchell. Cutting plane algorithms for integer programming, in the Encyclopedia of Optimization. Kluwer Academic Publishers, August 2001, http://www.rpi.edu/~mitchj/papers.html.

74. John E. Mitchell. Polynomial interior point cutting plane methods. Department of Mathematical Sciences, Rensselaer Polytechnic Institute, Troy, NY, July 16, 2001, http://www.rpi.edu/~mitchj/papers.html

75. John W. Chinneck. Practical Optimization: a Gentle Introduction. Carleton University, http://www.sce.carleton.ca/faculty/chinneck/po.html.

76. Jonathan Bard. Summary of Branch and Bound Methodology using LP Relaxation. The University of Texas, November 17,2001.

77. Karen Aardal, Stan van Hoesel. Polyhedral Techniques in Combinatorial Optimization I: Theory. Department of Computer Science, Utrecht University, Department of Quantitative Economics, Limburg University.

78. Katta G. Murty, Feig-Tien Yu. Linear Complementarity, Linear and Nonlinear Programming. Internet Edition. Department of Industrial and Operations Engineering, University of Michigan, 1997, http://www.personal.engin.umich.edu/~murty.

79. Katta G. Murty. Integer Programming and Combinatorial Optimization. IOE 614, http://www.personal.engin.umich.edu/~murtLP Theory, Cambridge University, http://www.statslab.cam.ac.uk/~rrwl/mor.

80. Katta G. Murty. Operations Research. IOE 510, http://www.personal.engin.umich.edu/~murty.

81. Lieven Vandenbergh, Stephen Boy, Mehrdad Nouralishahi. Robust Linear Programming and Optimal Control. Electrical Engineering Department, UCLA, Electrical Engineering Department, Stanford University.

82. Linear Programming Frequently Asked Questions (FAQ). Optimization Technology Center of Northwestern University and Argonne National Laboratory. http://www-unix.mcs.anl.gov/otc/Guide/faq/linear-programming-faq.html

83. LP Book, Princeton University. http://www.princeton.edu/~rvdb/LPbook/probs/index.html.

84. M.W.P. Savelsbergh. Preprocessing and Probing Techniques for Mixed Integer Programming Problems. School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta.

85. NEOS Guide CPLEX. http://www-fp.mcs.anl.gov/otc/Guide/SoftwareGuide/Blurbs/cplex.html.

86. Notes in Applied Integer Programming, April 12,2002.

87. OR-Notes J. E. Beasley. Integer programming formulation examples. http://mscmga.ms.ic.ac.uk/ieb/or/moreip.html.

88. OR-Notes J. E. Beasley. Integer programming, http://mscmga.ms.ic.ac.uk/jeb/or/ip.html.

89. Qun Chen, Michael C. Ferris. FATCOP: A Fault Tolerant Condor-PVM Mixed Integer Program Solver. Department of Industrial Engineering, Department of Computer Sciences, University of Wisconsin-Madison. March 17, 1999.

90. Robert E. Bixby, Mary Fenelon, Ronald Wunderling. Linear & Integer Programming: A Decade of Computation.

91. Robert E. Bixby. MIP: Theory and Practice Closing the Gap. ILOG CPLEX Division, Department of Computational and Applied Mathematics, Rice University, Houston, Mary Fenelon, ILOG CPLEX Division and etc.

92. Robert J. Vanderbei. Linear Programming: Foundation and Extensions. Department of Operations Research and Financial Engineering, Princeton University.

93. Robert J. Vanderbei. ORF 307. Operations Research and Financial Engineering, Princeton University, February 5,2002 http://www.princeton.edu/~rvdb/307/lectures.html.

94. Robert M. Freud, Shinji Mizuno. Interior Point Methods: Current Status and Future Directions. The Institute of Statistical Mathematics, Tokyo, October 1, 1996, revised December 5,1997.

95. S. Ceria, C. Cordier, H. Marchand, L.A. Wolsey. Cutting Planes for Integer Programs with General Integer Variables. Graduate school of Business, Columbia University, December 23,1995.

96. Sourour Elloumi, Martine Labbe, Yves Pochet. New Formulation and Resolution of Method for the p-Center Problem. December, 2001.

97. Stan Lao, Srinivas Devadas. Solving Covering Problems Using LRP-Based Lower Bounds. Advanced Technology Group, Synopsys Inc., Department of EECS, MIT.

98. Steve Hurder. Overview of the simplex method.

99. Ted Ralphs. IE316 Course Advanced Operations Research Techniques. http://www.lehigh.edu/~tkr2.

100. Ted Ralphs. IE418 Course Discrete Optimization, http://www.lehigh.edu/~tkr2.

101. Terno J., Linderman R., Scheithauer G. Zuschinitprobleme und ihre praktische Losung. Leipzig, 1987.

102. Xin Huang. Preprocessing and Postprocessing in Linear Optimiztion. McMaster University, June 2004.r