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

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

Щепал ов„Сер гей Владимирович

МАТЕМАТИЧЕСКИЕ МОДЕЛИ И МЕТОДЫ АВТОМАТИЗИРОВАННЫХ СИСТЕМ ПЛАНИРОВАНИЯ ПРОИЗВОДСТВА ПИЛОМАТЕРИАЛОВ

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

Автореферат

диссертации на соискание ученой степени кандидата технических наук

0034Э3397

Петрозаводск - 2010

003493397

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

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

заслуженный деятель науки РК Кузнецов Владимир Алексеевич

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

Колесников Геннадий Николаевич кандидат технических наук, Тарасенко Андрей Юрьевич

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

лесотехническая академия им. С. М. Кирова

Защита диссертации состоится 12 "марта" 2010 года в 15 часов на заседании Диссертационного Совета Д 212.190.03 в Петрозаводском государственном университете (185910, Республика Карелия, г. Петрозаводск, пр. Ленина, д. 33). Факс: (8142)71-10-00.

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

Автореферат разослан «£_» февраля 2010 года.

Ученый секретарь диссертационного совета, (приказ №5 от 11.01.2010)

А. А. Рогов

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

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

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

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

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

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

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

Основные задачи диссертационного исследования:

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

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

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

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

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

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

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

Научная новизна диссертационного исследования:

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

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

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

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

Личное участие автора. Все основные результаты работы получены лично автором.

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

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

Разработка программной системы проводилась в среде разработки приложений MS Visual Studio 2003, в качестве языка программирования использовался С#, в качестве платформы - MS Framework 1.1.

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

Апробация работы. Результаты диссертационного исследования были представлены на Международных научно-технических конференциях «Новые информационные технологии в ЦБП и энергетике» в 2006, 2008 гг., научных семинарах ПетрГУ и КНЦ, научной конференции «Передовые методы информационных и коммуникационных технологий» в 2009 г. Программа планирования работы лесопильного предприятия используется в ЗАО «Ладожский ЛЗ» (г. Сортавала).

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

На защиту выносятся следующие основные результаты.

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

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

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

4. Комплекс программ, реализующих предложенные методы.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и 1 приложения. Основной материал изложен на 190 страницах, включая 2 таблицы и 23 рисунка. Библиографический список содержит 109 наименований.

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

В первой главе изложена история вопросов, связанных с применением математических моделей и методов к задаче оптимального раскроя круглого лесосырья, рассмотренных X. Л. Фельдманом, А. С. Барсовым, Г. Д. Власовым, В. И. Черновой, А. Н. Песоцким, Р. Е. Калитеевским, Л. В. Канторовичем, В. А. Залгаллером, В. М. Лозовым, В. И. Соболевым, М. Я. Бравым и В. А. Кузнецовым. Проведен анализ, выявлены недостатки доступных ранее разработанных моделей и программных систем, выделены структурные элементы объекта исследования.

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

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

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

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

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

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

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

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

Мр- множество индексов ограничений г'-й категории и множество индексов приоритетной продукции, выпускаемой ву-м периоде; Хц, х[р - количество единиц 1-го вида сырья, подвергаемого раскрою у'-й схемой, для произвольного периода и для А'-го периода;

- значение нарушения /то ограничения и штрафной коэффициент; а.ц5, - нормально распределенная случайная величина выхода продукции ¿•-го вида при применении к единице сырья ¿-го вида у'-й схемы раскроя, и объем единицы 5-го вида продукции;

С'гц, 9Г - ценность г-го вида единицы объема сырья для у'-й схемы раскроя /-го вида сырья и лимит совокупной г-й оценки плана раскроя; д, - нижняя граница совокупного расхода сырья и расхода г-го вида сырья; Qi> С?- ~ нижняя и верхняя граница объема выпуска пилопродукции 1-го вида и нижняя и верхняя граница совокупного объема пилопродукции;

- объем пиломатериалов /-го вида, подлежащий выработке с первым приоритетом в у'-м плановом отрезке и совокупный объем выработки;

близкий нулю объем производства в у-м периоде пиломатериалов /-го сечения, не имеющих первого приоритета;

V', VI - верхняя граница совокупного расхода сырья и расхода ¡'-го вида сырья;

У(, V* - объем единицы г-го вида сырья и минимальный объем сырья, для которого допустима перенастройка пиловочного оборудования; Д; - доля использования г-го вида сырья, 0 < Д,< 1; а( - вероятность выполнения г-го ограничения (ограничения на расход сырья носят детерминированный характер);

- индекс пиломатериала, входящего в схему раскроя на г'-й позиции, величина объемного выхода имеет распределение /У(тиг, си;), = (1.

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

(1)

„ (4)

( N Шц 1^=1..с1 вЪ ),..., N (..а ти ; ^ ¡Е/=1.м Ощ

I Х,"« £/¡=1 и 1=1 у \ ' "(=п ч1=п

Ограничения на оценочные показатели:

Р(ЕГ=1 Ц Т.%г с'гцХц > вг) > «г- (2)

Ограничения на параметры материального расхода сырья:

У^%гХц<Г. (3)

Ограничения на пропорциональный расход сырья:

МТ^У^их^ -у^х^ = о Прямое ограничение на объем каждого вида используемого сырья:

(5)

Ограничения на параметры материального выхода производства:

<(?;)> кем3. (6)

Ограничения на общий объем производимой продукции:

Ф < И?=11Т=г 1%г афХц <<?')> ак. ке М4. (7)

Ограничения на объемный выпуск приоритетной продукции на примере первого периода:

> >ак, к 6 М5> з е /(8)

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

P{7ZiHjU aUs^ Я?) * а*< к е 5 е /(1)" <9>

Ограничение на минимальный совокупный объем производства пиломатериалов в периоде на примере первого периода:

P(lWLT=i aijsXl? > Q(1)) >ак, к е М7. (10)

В случае, когда разрешен переход продукции из первого периода только во второй:

^ + ^ «fc. fc 6 Ma. s e /W. P{miZjUaißXi? < Q?) > «fc, /с 6 Mg, s g /«. Ограничение на минимальный объем схемы раскроя:

V^j е {0, [V*,+oo)}. (12)

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

FW = rs=i l?=i Vt If=1 C'rijx\f -> min. (13)

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

• минимизация отклонения решения от граничных значений ограничений:

min-, (14)

• максимизация минимального ненулевого объема схемы раскроя:

minViXtjWiXij] max. (15)

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

т, п - количество строк и столбцов в матрице ограничений; Pj, bj, atj - нижняя граница вероятности выполнения у'-го ограничения, значение правой части ограничения и коэффициент при управляемой переменной N (mtj-, Оц );

а - коэффициент доверительности, определяющий вероятность выполнения /'-го ограничения задачи, и критерий сходимости; М', М"- множество индексов нижних и верхних ограничений задачи; Х^, Хк, Сг - управляемые переменные, решение на к-м шаге и коэффициенты целевой функции задачи.

Рассмотрим следующую задачу:

2"= г ^ С£ -» тах

Р(ЕГ=1а^<Ь,)>Р;, уем".

Решение задачи (16) осуществляется итерационно, на к-й итерации решается следующая задача:

тах

ГЕГ=1 М(ау)Х( > Ь) + ^т, } б М; М(аи)х1 < Ь} - Щ{хк1 ) е М";

= ШгМ2, Ь, = ФЕШ ФО{х)=^=^ехр(-х-)йх.

Критерий сходимости алгоритма: \ц(Хк) — <т;(Хк < а. В работе доказано:

Утверждение 1: Для любой задачи вида (16) найдется задача линейной оптимизации с эквивалентной целевой функцией и усредненными значениями случайных коэффициентов, решение которой совпадает с решением исходной задачи.

Метод (16 - 17) сходится даже в случае несовместных ограничений. Механизм обратной связи реализован в виде проверки нарушения условий оптимальности в линеаризованной задаче календарного планирования. Введем обозначения:

В, А - вектор правых частей задачи линейной оптимизации и матрица базисных столбцов;

Д - вектор приращений правых частей ограничений задачи. Условие равновесия имеет следующий вид:

^АТ/^-Ад^О, ] = 1..т. (18)

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

10

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

Введем обозначения: т,п,Ь - количество видов сырья, видов пилопродукции и строк в матрице ограничений;

11ц, Р/у - вектор раскроя и вектор первых т элементов вектора раскроя; У - вектор двойственных переменных задачи;

- матрица множителей и матрица разложения коэффициентов для ограничений и целевой функции. Вектор раскроя имеет следующий вид:

Рц = \ 0.....0,1,0.....0,а1[;-.....аш7 ). (19)

Задача поиска плана раскроя записывается в субканонической форме: № = 1,7 СиХи = 1и{р'Р;;ЛРи)Хи - тах;

Ы№,Гри)Хч = вВ работе доказано:

Утверждение 2: Двойственная оценка линейно зависит от параметров соответствующего управляемой переменной раскроя 1-го вида сырья и справедлива следующая формула:

д = - Ат+1)) + (21)

+ -РиЛи-

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

(N (риГи + Ри 1?=1 Га,™«М(Р^+т), ри^и У1т+5°(РцмтУ

Л\

( I-^ ' ^^

,5+772

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

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

и

Введем обозначения: п, т - количество разновидностей деталей и количество искомых схем; а, Ь— некоторые траектории (раскрои); L, d-i - длина объекта раскроя и длина /-й детали; /(b), pQj) - доходность и длина траектории Ь;

hf - ширина большей из сторон сечения детали на /'-й позиции в схеме раскроя а;

W" — ширина меньшей из сторон сечения детали на г-й позиции в схеме раскроя а;

7Г- множество всех возможных траекторий объекта длины L\ Г-упорядоченное индексированное множество искомых траекторий; М - упорядоченное индексированное множество списков индексов деталей, состоящего из L элементов (списков), Мк хранит индексы последних (справа) деталей оптимальных и отклоненных подтраекторий длины к;

Q - упорядоченное индексированное множество списков доходностей частей траекторий, состоящего из L элементов (списков), причем содержимое списков соответствует спискам из М\ pJ+1 - индекс элемента множества М на j-м шаге; / - множество, по структуре аналогичное множествам М и Q, элемент 4 [Я хранит индекс позиций индекса предыдущей детали траектории в списке Mk-.w(lkU]), к - w{lk\j}) > 0;

t(J,r) = (iv ..., tn) - вектор, характеризующий часть траектории длины г, прочитанную от позиции j до г из множеств М и Q, - количество единиц детали к-го вида;

w(j) - функция, отображающая множество индексов деталей j на множество толщин пиломатериалов с соответствующими индексами; vi> msk> cs ~ объем единицы детали г'-го вида, средний объемный выход пиломатериала на позиции к в траектории и доход от производства единицы объема данной детали;

S, Push(S, b), Pop(S) - стек индексов деталей и операторы вставки элемента Ъ в стек и извлечения элемента из вершины стека.

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

T:f(bi) > /(а), а Е п\Т, \Т\<тп; (L > p(b) > L - min(=1.n{d,}, Ь е Т;

J hf > wl hf > hf+v b G T; { )

Af = hf+1 => wf > ivf+1, beT.

Вставка индекса 5 детали в список Мк возможна только случае выполнения условия пнПдем^^О/} ^ 5. Поиск индекса / детали, располагающейся слева от добавляемой, осуществляется так, чтобы полученная подтраектория была оптимальной:

; = Ш1П£=о.|М)[_1¥М_1|{0. 1к *- к и О'}- (24)

Доходность полученной траектории сохраняется в множестве (}к:

«- <2к и К?*-«**)У) + т^с,}. (25)

Для заполненных множеств М и £ справедливо следующее:

101 = |М| = I, = |М;|, (]№] > (¡¿к + 1], 1 < £ < ¿. (26)

В работе доказано:

Утверз/сдеыие 3: По множеству М можно восстановить все возможные траектории.

На каждом]-и шаге бэктрекинга вычисляется вектор I = £(/,г), так же вычисляется доходность прочитанного участка траектории / = /(<:), а сама траектория сохраняется в стеке 5:

Р]+1 = Р) ~ ^мдк]. Ци = {»¡[к] + 1. / = / + смдк], РияЦ5,р]+1). (27) Положение индекса к предыдущей детали в списке МР}+1 вычисляется по формуле:

к = 1Р][к]. (28) Замена частей траектории выполняется путем перемещения указателя в обратном направлении по правилу:

г = Рор($), р] = р]+1 - <4 ь = - 1, f = f-ci. (29)

Ветка подтраекторий отсекается, если в позиции (¿.А:) верно:

<2; И + /(0 > пнпа6Г{/(а)}, |Г| = т. (30)

Траектория / прочитана, если ру = 1, после этого производится вставка ее в множество Тесли выполнено условие:

Г+ {£] = ( гим. |Г|<т;

14 1(7-\Ы) и {О, |Г| = т, < ДО, д £ т.

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

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

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

1. расчет оптимального решения линейной модели;

2. фильтрация компонент решения;

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

Введем обозначения:

X* - оптимальное решение задачи (16);

Ф(Х) - вектор-функция фильтрации вектора Х\

X** - оптимальное решение задачи квадратичной оптимизации;

X*** - искомое приближенное решение задачи (16), удовлетворяющее

условию (12);

/ - множество индексов управляемых переменных;

/?,• - искусственная переменная, соответствующая /-му ограничению

линейной модели;

к, Iпй{]) — количество управляемых переменных и отображение множества индексов управляемых переменных на множество индексов видов сырья;

в] - минимально допустимое значение управляемой переменной, соответствующее у'-му виду сырья;

5 - матрица ограничений, составленная из столбцов исходной матрицы, индексы которых, составляют множество I.

Оптимальное решение X' задачи (16) фильтруется в соответствии с условием (12):

Ф(Х) = (хг.....**). х1£Ш = , / = > ОД < ( < к]. (32)

Допуская, что ограничения задачи (16) при наборе / управляемых переменных несовместны, рассмотрим задачу минимизации невязок:

Р = Е.ем, ((^(1% ЗД - В,))+) + Ъ1еМг ((Л*(В, - Т.% ЗД))+)

^ Вд * «.•' »' е м1>

> В,) > а„ I £ М2;

гХ-.БХ = В; Х} > 0, 1 < ) < |/|.

14

Теорема 1: Детерминированная задача вида (33) при любых свойствах Гессиана целевой функции Р и отсутствии решения линейной задачи (16) сводится к выпуклой задаче квадратичного программирования, целевая функция которой либо выпукла, либо вогнута.

Справедлива следующая замена целевой функции:

Р = 1.1 Р* тт. (34)

Метод решения задачи (33) основан на методе (16-17), в силу утверждения 1 промежуточная задача (17) имеет целевую функцию (34) и линейные ограничения, а в случае несовместных ограничений для ее решения применяется метод Франка-Вулфа.

Пусть получено оптимальное решение X" задачи (33), тогда искомое приближенное решение задачи (16) вычисляется по формуле:

Л"** = Ф(Х**). (35)

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

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

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

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

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

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

7г - множество индексов всевозможных схем раскроя бревен любых толщин;

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

г„ ¡11 - нарушение нижних и верхних ограничений соответственно общих ограничений (фактически это значения искусственных переменных ограничений), т^ > > 0;

Wa

(j, \pj - значения нарушений нижних и верхних ограничений для /-го заказа, гр) >0, (} > 0; Х(Х) - функция Хевисайда;

Ws - обозначение .v-й целевой функции или .v-й характеристики особи; W(J), p(J~) — фитнесс-функция (вектор-функция) и функция выживаемости особи

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

i j i

1. Величина нарушения нижних ограничений для заказа первого приоритета:

min;

j

3. Величина нарушения нижних ограничений для заказа с /--м приоритетом:

Wr+1(J) = -> min-,

i

4. Величина нарушения верхних ограничений для всех заказов:

W'cO) = Ya ßl + ^ 2 <р{ min-, i j i

5. Число применяемых схем раскроя:

Wr+3Ü) = min-,

iej

6. Расход сырья:

*(/) = ^ V'nd(i)Xi min-, ¿ey

7. Минимальный объем схемы раскроя:

Wr+s(J) = гшп{Х,} -» max. Xi> о

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

задачи (33) из сгенерированного множества методом (24-31). Характеристики особи вычисляются на основе решения построенной подзадачи.

Фитнесс-функция имеет лексикографический порядок сравнения:

ЮЦ) = (ИЪУ),1У2(/).....И^ШЖсШ.И^зОт^Ш.^г+БШ)- (36)

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

Процесс мутации имеет место в том случае, если это не приводит к ухудшению выживаемости особи.

Введем обозначения: ], У - хромосома до и после процедуры мутации;

6 я - случайный индекс управления (схемы раскроя).

Попадание гена в хромосому означает его присутствие в базисе решения с ненулевым значением управления наравне с остальными генами для задачи локальной оптимизации (33), управления которой определяются множеством ] и {д}. Решение (33) в виде набора генов /' и значений ЛГзаменяет решение для /, если выполнены условия:

х„ > вш{я), рСЛ > рО).

Возможна следующая ситуация:

У = 0ЩЬ )и<7' и/Целью операции кроссинговера является передача хромосоме-потомку лучших родительских генов. Введем обозначения: У1,/2 — наборы генов двух особей популяции; У* - множество генов потомка.

Множество родительских генов и множество генов потомка:

/ =71 иу2. Г = 0-

Операция кроссинговера выполняется по следующему алгоритму:

1. выбирается схема раскроя:;' Е], } *-У\{у'};

2. пусть У'- решение задачи (33), для множества управлений ]* и {/};

3. если р(/') > рО*), тоу* *-у4и{/};

4. если У = 0, то вернуть новую особь У*, иначе переход на шаг 1.

Управления популяцией производится по следующему алгоритму:

1. для каждой особи У находится значения и рЦ);

2. для скрещивания случайным образом выбираются ^'"'/50 паР особей;

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

4. новая особь ]' остается в популяции, если выполнено неравенство:

)' £ Е, рС/0 > тт{р(/)} => £ <- ~ и {/'};

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

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

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

Сырье поступает партиями, данные по которым имеются за некоторый период времени, это позволяет вычислить следующие показатели:

• количество поставок, необходимое для реализации всех заказов;

• распределение объемов поставок сырья по заказам.

Целью оптимизации в задаче объемно-календарного планирования является наискорейшее выполнение заказов в порядке их приоритета. Введем обозначения: тп - количество видов сырья;

ц - случайная величина объема сырья /-го вида в одной поставке сырья и случайная величина совокупного объема сырья;

/? - вероятность выполнения верхнего ограничения на расход сырья г-го вида из поставки и вероятность выполнения нижнего ограничения на совокупный расход сырья поставки;

, ц' - правые части детерминированных ограничений, эквивалентных соответствующим стохастическим ограничениям на расход сырья поставки;

р,(х). - функция плотности случайной величины и функция обратная к функции распределения случайной величины ¡¡¡.

Ограничения на расход сырья поставки записывается в виде:

Р(£№Хи<Ь)>а11 1 <1<т,

Р&Ъ ЪХц > (г) >/3, (37)

Хц > 0, 0 < а^р < 1, 1 < I < т.

18

Стохастическим ограничениям (37) соответствует следующая система детерминированных неравенств:

¿ = 1.. т;

(38)

ХЦ > 0.

Ср^х) = = 1 -щ, Ь'Ч 1 - ад = 1 < I < т.

41

Теорема 2: Форма зависимости случайных величин при сохране-

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

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

Л« В^ - матрица коэффициентов ограничений, вектор управляемых переменных и правые части ограничений для /-го заказа; z¡ - количество всех схем раскроя /-го вида сырья и совокупное количество схем раскроя;

ц' - правые части детерминированных ограничений на объем расхода сырья каждого вида из поставки и ограничений на совокупный объем расхода сырья;

М - список значений номера заказа и поставки, ¿-й элемент которого является парой целых чисел (/,/'), где / - номер заказа,/ - номер поставки сырья, соответствующей /-му заказу;

Ас1с1(М, и) - функция добавления пары и=И,/) в конец списка М\ еи) _ вектор размерности любая компонента которого равна значению объема единицы сырья /'-го вида;

Б - ступенчатая подматрица коэффициентов ограничений, /-я строка подматрицы соответствует ограничению на объемный расход сырья /'-го вида из поставки для одного заказа;

X - управляемые переменные, соответствующие /-му заказу; Ь - вектор, /-я компонента которого соответствует значению объема складского остатка сырья /-го вида, (т + 1)-я компонента - совокупный объем;

У - управляемая переменная, соответствующая количеству поставок сырья.

Алгоритм распределения заказов по поставкам сырья представлен на рис. 1. _

Рис. 1. Алгоритм распределения заказов по поставкам сырья.

Допустим, на некотором шаге алгоритма учитывается только один заказ, М={(1,1)}, необходимо найти минимальное количество поставок, необходимых для его выполнения:

Y -»min

Л(1) 0 \„> (<)ва) S О О (J) < Ь . (39)

О 5 (-Ь')7 < О /eW 0 - 0 \

.9. .9. .dira(e«)=zi, V 0 о -ei»)/

eV> = {Vj.....Vj), 1 < j < т.

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

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

1. подматрицы общих ограничений (одинаковы для всех групп);

2. подматрицы ограничений заказа;

3. подматрицы поставки (одинаковы для всех групп).

Для решения задачи используется метод генерации столбцов. Введем обозначения:

А = {«¿у}[=1..ТТ1 - подматрица коэффициентов общей части ограничений ;=1..п

блока, каждый столбец соответствует некоторой схеме раскроя;

(а1; ...,ат)т, с - некоторый столбец матрицы А и соответствующий

коэффициент целевой функции;

{(], у], {/?с, ус} - субканонические формы для столбца матрицы ограничений и коэффициента целевой функции;

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

Я; - двойственная переменная, соответствующая 1-му ограничению; С[ - коэффициент целевой функции при управляемой переменной; и - вектор раскроя, сИт(и) = /с;

а, {Ра,уа} - вектор при управляемой переменной и его субканоническая форма.

Множитель перед управляемой переменной в задаче локальной оптимизации можно записать в следующем виде:

Теорема 3 (об устойчивости субканонической формы к линейным преобразованиям): Результат матричных линейных операций (40) для столбцов матрицы А, представимой в виде субканонической формы, также представляется с помощью субканонической формы. Рассмотрим выражение (40) для одного столбца матрицы А:

(40)

а = Яаа[ - с, Рги = (ах.....ат)т.

Из последних выражений следует:

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

сс~(Ра,ГаХ Ра = 1, Га = (Уй.....У&).

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

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

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

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

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

3. Разработана модель задачи объемно-календарного планирования на основе данных о поставках сырья. Предложен метод ее решения.

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

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

В приложении содержится копия акта о внедрении АСУ на Ладожском лесопильном заводе (г. Сортавала).

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

1. Щепалов С. В. Преодоление проблемы NP сложности в задаче генерации набора наиболее доходных схем раскроя отрезка конечной длины / C.B. Щепалов // Естественные и технические науки № 4 (42). Москва: Изд-во «Компания Спутннк+», 2009. С. 429-430.

2. Кузнецов В. А. Задача распределения заказов по поставкам сырья и складским остаткам / В. А. Кузнецов, С. В. Щепалов // Естественные н технические науки № 5 (42). Москва: Изд-во «Компания Спутник+», 2009. С. 339-341. (Степень авторского участия 70 %).

3. Щепалов С. В. Раскрой длинномерных объектов с учетом потерь материала / С. В. Щепалов // Естественные и технические науки № 6 (26). Москва: Изд-во «Компания Спутник+», 2006. С. 273-274.

4. Щепалов С. В. Структуры данных и алгоритм для генерации раскроя пиловочного бревна / С. В. Щепалов // Естественные и технические науки № 1 (27). Москва: Изд-во «Компания Спутник+», 2007. С. 179-181.

5. Щепалов С. В. Геометрический подход к генерации раскроя пиловочного бревна / C.B. Щепалов // Естественные и технические науки № 2 (28). Москва: Изд-во «Компания Спутник+», 2007. С. 278-280.

6. Щепалов С. В. Непрерывная математическая модель пиловочного бревна / С. В. Щепалов // Естественные и технические науки № 3 (29). Москва: Изд-во «Компания Спутник+», 2007. С. 25-27.

7. Кузнецов В. А. О реализации метода генерации столбцов в приложении к задаче оптимизации производства обрезных пиломатериалов /

B. А. Кузнецов, С. В. Щепалов // Материалы VII Международной научно-технической конференции «Новые информационные технологии в целлюлозно-бумажной промышленности и энергетике». Петрозаводск: Изд-во РЦНИТ ПетрГУ, 2006. С. 66-68. (Степень авторского участия 50 %).

8. Щепалов С. В. Метод разработки универсального интерфейса для приложений, использующих базу данных / С. В. Щепалов // Труды Петрозаводского государственного университета. Серия «Прикладная математика и информатика». Вып. 12. Петрозаводск: Изд-во: ПетрГУ, 2007.

C. 138-142.

9. Щепалов С. В. Бесконтактный измеритель геометрии поверхности древесного ствола / С. В. Щепалов // Труды Петрозаводского государственного университета. Серия «Прикладная математика и информатика». Вып. 12. Петрозаводск: Изд-во: ПетрГУ, 2007. С. 122-130.

10. Щепалов С. В. Применение линейной оптимизации в задаче комплектации на примере лесопильного производства / С. В. Щепалов //

Аспирант и соискатель № 3 (40). Москва: Изд-во «Компания Спутник», 2007. С. 144-145.

11. Щепалов С. В. Метод выполнения плана производства пиломатериалов в случае периодических поступлений малых объемов сырья / С. В. Щепалов // Материалы VIII Международной научно-технической конференции «Новые информационные технологии в целлюлозно-бумажной промышленности и энергетике». Петрозаводск: Изд-во РЦНИТ ПетрГУ, 2008. С. 59-61.

12. Shchepalov S. V. The task of lumber dressing plan optimization, its versions and applications / S.V. Shchepalov // Передовые методы информационных и коммуникационных технологий. Петрозаводск: Изд-во ПетрГУ, 2009. (Труды AMICT'2008; Т. 10). С. 95-97.

Подписано в печать 05.02.10. Формат 60x84 '/,„• Бумага офсетная. Уч.-изд. л. 1. Тираж 100 экз. Изд. № 28.

Государственное образовательное учреждение

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

Типография Издательства ПетрГУ 185910, г. Петрозаводск, пр. Ленина, 33

Введение.

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

§1. Некоторые особенности технологии процесса лесопиления и планирования работы лесопильного предприятия.

§2. Обзор литературы.

2.1 Модель X. JI. Фельдмана.

2.2 Модель JI. В. Канторовича.

2.3 Модель И. В. Соболева, М. Я. Бравого и др.

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

§4. Постановка задачи оптимального раскроя круглого лесосырья.

4.1 Модель единицы продукции.

4.2 Модель единицы сырья и сортировочной группы.

4.3 Модель объемного выхода обрезного пиломатериала при применении постава к единице сырья.

4.4 Детерминированная модель задачи объемно календарного планирования.

4.5 Целевые функции задачи.

4.6 Общая запись задачи ОКП и метод решения.

§ 5. Стохастическая модель задачи раскроя пиловочного сырья и метод ее решения.

§ 6. Анализ устойчивости решения.

Выводы.

Глава 2. Универсальная методика аналитической записи задачи, связанной с раскроем. Метод расчета оперативного плана нелинейной задачи.

§1. Основные закономерности линейных оптимизационных моделей и типовая схема симплексного алгоритма.

1.1 Метод решения и свойства линейных моделей.

1.2 Аналитическая форма основных показателей и преобразований

§2. Субканоническая форма записи многомерной раскройной задачи линейного программирования.

2.1 Векторное представление столбцов матрицы ограничений линейной раскройной задачи.

2.2 Генерация оптимального раскроя пиловочного бревна.

2.3 Вычисление стохастических характеристик столбца матрицы ограничений на основе раскроя и СКФ.

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

2.5 Расширения субканонических форм.

§3. Методы генерации колонок матрицы линейных ограничений на основе двойственных переменных задачи JIO.

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

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

3.3 Задача генерации оптимального линейного раскроя с контролем порядка расположения деталей в схеме раскроя.

3.4 Генерация набора наиболее доходных траекторий с контролем порядка деталей в траекториях.

3.5 Генерация набора наиболее доходных схем раскроя пиловочного бревна.

3.6 Генерация решений близких к произвольному решению для задачи линейной оптимизации.

§4. Метод понижения размерности решения задачи поиска оптимального плана раскроя круглого лесосырья.

4.1 Применение фильтрации и метода Франка-Вулфа для поиска приближенного решения задачи линейной оптимизации.

4.2 Улучшение промышленного плана при помощи расширения схем раскроя.

4.3 Метод решения задачи стохастического программирования с несовместными ограничениями.

§5. Генетический алгоритм поиска решения задачи оперативного планирования с ограничением на объем схем раскроя.

5.1 Структура генетического алгоритма в приложении к задаче оперативного планирования

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

5.3 Описание хромосомы.

5.4 Фитнес функция.

5.5 Мутация хромосомы.

5.6 Кроссинговер.

5.7 Стратегия управления популяцией.

Выводы.

Глава 3. Объемно-календарное планирование.

§1. Структура задачи объемно-календарного планирования.

§2. Динамика поступления сырья в приложении к планированию оптимальных поставов.

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

2.2 Детерминированная задача линейного программирования, эквивалентная задаче линейного программирования со случайными свободными членами ограничений.

2.3 Решение задачи стохастической линейной оптимизации с разными видами ограничений.

§ 3. Задача распределения заказов по поставкам сырья и складским остаткам

§4. Выражение задачи ОКП в терминах СКФ.

§5. Метод декомпозиции Данцига-Вулфа в терминах СКФ для решения задачи ОКП.

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

5.2 Использование метода генерации столбцов для решения локальной задачи линейного программирования в методе Данцига-Вулфа

§6. Переход от календарного планирования к оперативному планированию

§7. Обратная связь.

Выводы.

Глава 4. Инструментальные средства для успешного внедрения ПО расчета оптимальных поставов.

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

§2. Проблема потребительских качеств программного продукта и проблема интеграции

Выводы.

г

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

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

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

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

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

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

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

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

Основные задачи диссертационного исследования:

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

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

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

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

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

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

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

Научная новизна диссертационного исследования:

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

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

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

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

Личное участие автора. Все основные результаты работы получены лично автором.

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

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

При проектировании программной системы была применена теория объектно-ориентированного программирования и модульной разработки приложений. Разработка программной системы проводилась в среде разработки приложений MS Visual Studio 2003, в качестве языка программирования использовался С#, в качестве платформы - MS Framework 1.1.

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

Апробация работы. Результаты диссертационного исследования были представлены на Международных научно-технических конференциях «Новые информационные технологии в ЦБП и энергетике» в 2006, 2008 гг., научных семинарах ПетрГУ и КНЦ, научной конференции «Передовые методы информационных и коммуникационных технологий» в 2009 г.

Программа планирования работы лесопильного предприятия используется на Ладожском лесопильном заводе (г. Сортавала).

Публикации. По результатам исследований опубликовано 12 печатных работ, из них - две статьи в рецензируемых журналах ВАК РФ. На защиту выносятся следующие основные результаты.

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

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

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

4. Комплекс программ, реализующих предложенные методы.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и 1 приложения. Основной материал изложен на 190 страницах, включая 2 таблицы и 23 рисунка. Библиографический список содержит 109 наименований.

Выводы

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

2. Одним из лучших средств конструирования способа переноса данных в единый файл из разнородных источников является подсистема DTS из полного программного пакета MS SQL Server.

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

Заключение

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

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

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

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

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

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

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

1. Shchepalov S. V. The task of lumber dressing plan optimization, its versions and applications. Передовые методы информационных и коммуникационных технологий. Петрозаводск: Изд-во ПетрГУ, 2009. (Труды AMICT'2008; Т. 10). С. 95 - 97.

2. Авербах И. Л. Оптимизация в блочных задачах с целочисленными переменными / Авербах И. Л., Цурков В. И. М.: Наука: Физматлит, 1995.

3. Акоф Р., Сасиени Р. Основы исследования операций. М.: Мир, 1971.

4. Акулич И. Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов экон. спец. вузов. 2-е изд., испр. и доп. - М.: Высш. шк., 1993.

5. Алексеев, А. Е. Ресурсосберегающие технологии раскроя пиловочного сырья: автореферат диссертации на соискание ученой степени д-ра техн. наук: 11.00.11. Архангельск, 1998.

6. Асанов М. О. Дискретная оптимизация: Учеб. пособие. Екатеринбург, 1998.

7. Асанов М. О. Методы дискретной оптимизации: Учеб. пособие. -Екатеринбург, 1992.

8. Ахо А. В., Хопкрофт Д. Э., Ульман Д. Д. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.

9. Ахо А. В., Хопкрофт Д. Э., Ульман Д. Д. Структуры данных и алгоритмы., М.: Вильяме. 2003

10. Ю.Беллман Р. Динамическое программирование. М.: Мир, 1960.

11. П.Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. Пер. с англ. М.: Наука, 1965.

12. Белоусов А. И. Лекции по дискретной математике: Учеб. пособие/ Белоусов А. И., Мартынов Б. В., Щетинин А. Н.: Под ред. А. И. Белоусова. М.: Изд-во МГТУ им. Н. Э. Баумана, 1994.

13. Вагнер Г. Основы исследования операций: В Зт. М.: Мир, 1972-1973.

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

15. Вероятностные методы дискретной математики: Тр. третьей Петрозав. конф., 12-15 мая 1992 г. Петрозаводск, Россия / Под ред. В. Ф. Колчина и др. М.: "ТВП"; Утрехт: "VSP", 1993.

16. Воронин А. В., Кузнецов В. А. Математические модели и методы планирования и управления предприятием ЦБП. Петрозаводск: Изд-во ПетрГУ, 2000.

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

18. Воронин А. В., Кузнецов В. А., Чернецкий В. И. и др. Математическое моделирование и программное обеспечение задач АСУ ЦБК: Отчет о НИР (заключит.). Петрозаводск: Изд-во ПетрГУ, 1989. 164 с.

19. Воронов А. А. Исследование операций и управление. М.: Наука, 1970.

20. Воронов Р. В. Генетический алгоритм для задачи линейного раскроя. Сб. статей. Труды Петрозаводского государственного университета, серия «Прикладная математика и информатика», вып. 12. -Петрозаводск: Изд-во ПетрГУ, 2007. стр. 35-49.

21. Воронов Р. В. Математические модели и методы автоматизированных систем планирования производства бумаги: автореферат диссертации на соискание ученой степени канд. техн. наук: 05.13.18. -Петрозаводск, 2004.

22. Вотяков А. А. Математические основы "административно-командного метода": Алгоритмы решения массовых задач линейного программирования. М., 1994.

23. Вьюков И. Е., Зорин И. П. Автоматизация предприятия ЦБП. М.: Лесн. пром-ть 1982.

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

25. Гимади 3. X. Дискретные экстремальные задачи принятия решений: Учеб. пособие. Новосибирск, 1991.

26. Голыитейн А. Л. Исследование операций: многокритериальные задачи: Конспект лекций. -Пермь, 1995.

27. Громова Н. Б. Методы исследования операций в моделировании органзационно-экономических задач: Учеб. пособие для студентов инж. спец. целевой интенсивной подготовки специалистов в вузах / Громова Н. Б., Минько Э. В., Прохоров В. И. М.: Изд-во МАИ, 1992.

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

29. Данциг Д. Линейное программирование, его применения и обобщения. М., «Прогресс», 1966.31 .Дискретная математика и математические вопросы кибернетики // По ред. Яблонского С. В. и Лупанова О. Б., М. Наука, 1974.

30. Дискретные системы и их программное обеспечение: Межвуз. сб. / Под ред. М. К. Чиркова, С. П. Маслова. Л.: Изд-во ЛГУ, 1990.

31. Дискретный анализ: Сб. ст. / Отв. ред. А. Д. Коршунов. Новосибирск, 1994.

32. Духовин Ю. И., Павлов Ю. Г., Марков В. А. Оптимальное планирование в лесной, целлюлозно-бумажной и деревообрабатывающей промышленности. М.: Лесн. пром-ть, 1984.

33. Емельянова С. В, Коровина С. К. Нелинейная динамика и управление. Выпуск 1.-М.: ФИЗМАТЛИТ, 2001.

34. Ершов А. П. Введение в теоретическое программирование. М.: Наука, 1977.

35. Исследование операций (модели, системы, решения): Сб. / Рос. АН, ВЦ; Отв. ред. Ю. П. Иванилов. М., 1994.

36. Исследование операций и математическое программирование. -Кишинев, 1992.

37. Исследование операций и статистическое моделирование / Санкт-Птербург. гос. ун-т; Под ред. И. В. Романовского Вып. 6. 1994.

38. Калитеевский Р. Е. Проектирование лесопильных потоков. М.: Лесная промышленность, 1972.41 .Калитеевский Р. Е., Юдин С. Б., Шевелев JI. Е. Оборудование и технологические процессы ленточнопильных потоков. М.: ГОСЛЕСБУМИЗДАТ, 1962.

39. Калитеевский Р.Е. Лесопиление в XXI веке. С-Пб., 2005.

40. Калитеевский, Р. Е. Теория и организация лесопиления: монография. М.: Экология, 1995.

41. Канторович Л. В., Залгаллер В. А. Рациональный раскрой промышленных материалов. Издание второе. Новосибирск: изд-во «Наука», 1971.

42. Канторович Л., Лассман В., Шилар X., Шварц К., Брентьес С. Экономика и оптимизация. М.: Наука, 1990.

43. Карманов В. Г. Математическое программирование. М.: Физматлит, 2001.

44. Кнут Д. Искусство программирования для ЭВМ, т. 1-3, М.: Мир, 1977.

45. Коган Д. И. Дискретные многокритериальный задачи распределительного типа: Учеб. пособие. Н. - Новгород, 1991.

46. Колоколов А. А. Регулярные разбиения и отсечения в целочисленном программировании: Автореферат диссертации на соискание ученой степени д-ра физ.-мат. наук: 01.01.09. Иркутск, 1995.

47. Комбинаторные модели и методы: Сб. ст. / Рос. АН. ВЦ; Отв. ред. Н. А. Соколов. М.: ВЦ РАН, 1995.51 .Красовская М. А. Методы и алгоритмы линейного программирования в АСУ: Учеб. пособие. М.: Изд-во МАИ, 1994.

48. Кузнецов В. А. Задачи раскроя в целлюлозно-бумажной промышленности. Спб.: СПбЛТА, 2000.

49. Кузнецов В. А., Левина И. В. Элементы исследования операций. / В. А. Кузнецов, И. В. Левина. Часть 2. Петрозаводск: Изд-во ПетрГУ, 1984.

50. Кузнецов В. А., Щепалов С. В. Задача распределения заказов по поставкам сырья и складским остаткам. Естественные и технические науки № 5 (42). Москва: Изд-во «Компания Спутник+», 2009. С. 339 -341.

51. Курициын А. К., Соболев И. В., Шемелин А. И. Управление качеством обработки пиломатериалов. / А. К. Курициын, И. В. Соболев, А. И. Шемелин. М.: «Лесная промышленность», 1983.

52. Лебедва Л. А. Модели целочисленного программирования: Учеб. пос. -Новосибирск, 1994.

53. Летова Т. А. Задачи линейного и целочисленного программирования: Уч. пос. М.: Изд-во МАИ, 1996.

54. Лозовой В. М. Автоматическая оптимизация раскроя пиловочного сырья. М.: Изд-во ВНИПИЭИлеспром, 1975.

55. Лэсдон Л. С. Оптимизация больших систем. М.: Изд-во Наука, 1975.

56. Малиновский Ю. Г. Элементы математического программирования: Уч. пос. Челябинск: Изд-во ЧГТУ, 1995.

57. Меламед И. И. Некоторые задачи дискретного программирования с двумя и тремя критериями. М.: ВЦ РАН, 1998.

58. Моргунов И. Б. Основы дискретной оптимизации некоторых задач упорядочения: На прим. учеб. процесса. М., 1994.

59. Морз Ф. М., Кимбелл Д. Е. Методы исследования операций. М.: Изд-во Наука, 1956.

60. Неймарк Ю. И. Лекции по теории управления. Уч. пос. Горький: Изд-во Горьковского государственного университета им. Н. И. Лобачевского, 1973.

61. Нефедов В. Н. Дискретные задачи оптимизации: Учеб. пособие. М.: Изд-во МАИ, 1993.

62. Песоцкий А. Н. Обработка дерева. Изд-е 4-е исправленное. Мысль, 1925.

63. Песоцкий А. Н., Ясинский В. С. Рациональное использование древесины в лесопилении. -М.: Лесная промышленность, 1977.

64. Песоцкий В. С. Автоматическая оптимизация раскроя древесных стволов. -М.: Лесная промышленность, 1970.

65. Проектирование и реализация баз данных Microsoft SQL Server 2000. Учебный курс MSCE/ Пер. с англ. М.: Издательско-торговый дом «Русская редакция», 2001.

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

67. Романовский И. В. Дискретный анализ. СПб: Невский диалект, 1999.

68. Романовский И. В. Субоптимальные решения. Петрозаводск: Изд-во ПетрГУ, 1998.

69. Сачков В. Н. Введение в комбинаторные методы дискретной математики. М.: Наука, 1982.

70. Симонян, С. X. Совершенствование технологии раскроя пиломатериалов: автореферат диссертации на соискание ученой степени канд. техн. наук: 05.21.05. СПб., 2004.

71. Соболев И. В. Управление производством пиломатериалов. -Петрозаводск: изд-во «Карелия», 1976.

72. Соболев И. В., Гончаренко Н. А. Алгоритм составления плана раскроя пиловочного сырья. Изв. вузов. Лесной журнал, 1965, № 5, с. 154-161.

73. Солопахо А. В. Математика в экономике. Учебно-практическое пособие/ Солопахо. Тамбов: изд-во Тамб. гос. тех. ун-та, 2001. Ч 1.

74. Степаков Г. А. Оптимизация производства круглых лесоматериалов. -М.: Лесная промышленность, 1974.

75. Тим Джонс М. Программирование искусственного интеллекта в приложениях. М.: ДМК, 2006.

76. Тимофеев Е. К. Целочисленное программирование: Учеб. пос. для студентов экон. спец. / Тимофеев Е. К., Бессарабов Н. И. -Новочеркасск, 1994.

77. Тимофеева Л. К. Элементы математического программирования. Уч. пос. Куйбышев: Куйбышевский плановый институт, 1976.

78. Уголев Б. Н. Древесиноведение с основами лесного товароведения. Изд-е второе. -М.: Лесная промышленность, 1986.

79. Уласовец, В. Г. Теоретическое обоснование раскроя боковой зоны пиловочника на пиломатериалы: автореферат диссертации на соискание ученой степени д-ра техн. наук :05.21.05. Екатеринбург, 2006.

80. Фельдман X. JI. Система максимальных поставов на распиловку. М., Гостехиздат, 1932.

81. Фролов А. В., Фролов Г. В. Визуальное проектирование приложений С# / А. В. Фролов, Г. В. Фролов. М.: КУДИЦ-образ, 2003.

82. Хачатуров В. Р. Комбинаторные методы и алгоритмы решения задач дискретной оптимизации большой размерности / Хачатуров В. Р., Веселовский В. Е., Золотов А. В. и др. М.: Наука, 2000.

83. Хухрянская Е. С. Математические модели раскроя лесоматериалов: автореферат диссертации на соискание ученой степени канд. техн. наук: 05.21.05. Воронеж, 1998.

84. Царев Е. Г. Совершенствование процессов продольного раскроя пиловочного сырья: автореферат диссертации на соискание ученой степени канд. техн. наук: 05.21.05. СПб., 1993.

85. Чернецкий В. И. Математическое моделирование динамических систем. Петрозаводск: Изд-во ПетрГУ, 1996.

86. Чернецкий В. И. Математическое моделирование стохастических систем. Петрозаводск: Изд-во ПетрГУ, 1994.

87. Шалаев В. С. Совершенствование теории раскроя древесного сырья на пилопродукцию заданных размеров и качества: автореферат диссертации на соискание ученой степени д-ра техн.наук: 05.21.05. -М, 1995.

88. Шевченко В. Н. Качественные вопросы целочисленного программирования. М.: Наука, 1995.

89. Шерстобитов В. В. Математическое, программирование. Часть 1. Элементы линейной алгебры. Уч. пос. Ленинград: Ленинградская ордена Ленина лесотехническая академия имени С. М. Кирова, 1969.

90. Шетько, С. В. Разработка ресурсосберегающей технологии сортировки и раскроя круглых лесоматериалов на пилопродукцию целевого назначения: автореферат диссертации на соискание ученой степени канд. техн. наук: 05.21.05. Минск, 2003.

91. Ширяев В. И Исследование операций и численные методы оптимизации: Уч. пос. Челябинск: Изд-во ЧГТУ, 1993.

92. Щепалов С. В. Геометрический подход к генерации раскроя пиловочного бревна. Естественные и технические науки № 2 (28). Москва: Изд-во «Компания Спутник+», 2007. С. 278 280.

93. Щепалов С. В. Непрерывная математическая модель пиловочного бревна. Естественные и технические науки № 3 (29). Москва: Изд-во «Компания Спутник+», 2007. С. 25 27.

94. Щепалов С. В. Преодоление проблемы NP сложности в задаче генерации набора наиболее доходных схем раскроя отрезка конечнойдлины. Естественные и технические науки № 4 (42). Москва: Изд-во «Компания Спутник+», 2009. С. 429 430.

95. Щепалов С. В. Применение линейной оптимизации в задаче комплектации на примере лесопильного производства. Аспирант и соискатель № 3 (40). Москва: Изд-во «Компания Спутник+», 2007. С. 144-145.

96. Щепалов С. В. Раскрой длинномерных объектов с учетом потерь материала. Естественные и технические науки № 6 (26). Москва: Изд-во «Компания Спутник+», 2006. С. 273 — 274.

97. Щепалов С. В. Структуры данных и алгоритм для генерации раскроя пиловочного бревна Естественные и технические науки № 1 (27). Москва: Изд-во «Компания Спутник+», 2007. С. 179-181.

98. Юдин Д. Б., Голынтейн Е. Г. Новые направления в линейном программировании. М. «Сов. радио», 1966.1°Й