pizhurin_a_a_pizhurin_a_a_modelirovanie_i_optimizaciya_proce

ограничений (4.34). Берут некоторое &=&(0) и с ним решают задачу (4.35). Если для полученного решения хот неравенство

Ф(*опт)^

(4.36)

не выполняется, то задачу (4.35) решают вновь для к = к{1)>А*0), и так до тех пор, пока неравенство (4.36) не окажется выполненным.

4,4.5, Метод перебора (сканирования)

Большинство методов нелинейного программирования представля­ ет собой различные модификации того или иного метода безусловной ми­ нимизации. Для задач небольшой размерности может быть использован метод перебора. Отличие его от одноименного метода безусловной мини­ мизации (п. 4.3.6) заключается лишь в том, что в процессе перебора точек ЗсМ, являющихся узлами сетки, для каждой из них сначала проверяется выполнение ограничений задачи. Если все они удовлетворяются, то для этой точки вычисляется значение целевой функции. В противном случае, то есть при нарушении хотя бы одного из ограничений, сразу осуществля­ ется переход к следующей точке. Этот метод, несмотря на его несовершен­ ство, иногда приходится применять, когда не гарантирована одноэкстремальность задачи, либо при наличии дискретно заданных переменных.

Пример. Требуется решить следующую задачу нелинейного программиро­

вания:

Y(x1, х2) = х \х 2 / Igfa + х2 ) max;

Z(x\>х2)= *1*2 sinfo /х 2) ^ 9;

2 < jcj <4; 2 5 < * 2 <35.

Схема алгоритма, основанного на идее перебора значений переменных х\ и *2, приведена на рис. 4.19. Предварительно выбраны величины шагов по х\ и *2, обеспечи­ вающие удовлетворительную точность решения задачи. Обозначим их d\ и d2, и пусть d\= 0,1; d2= 0,2. Вначале (блок 1) переменные х\ и х2 полагают равными их исходным значениям: *i: =2; х2: =25. (Символ : = - это знак присваивания, поэтому записьх\: =2 означает: «переменной х\ присвоить значение 2»).

Переменная М в дальнейшем на каждой итерации будет принимать значение, равное наибольшей величине целевой функции Y(x\, х2) по всем предыдущим этапам.

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

Далее проверяется, удовлетворяет ли исходная точка {*i=2; х2=25} ограниче­ нию решаемой задачи: Z(x\, х2)<9. С этой целью в блоке 2 вычисляется значение функ­ ции Z(xj, х2) из этого ограничения, а полученное числовое значение присваивается

переменной z.

В блоке проверки условия 3, имеющем на схеме вид ромба, проверяется вы­ полнение записанного внутри него соотношения (в данном случае неравенства z < 9). Если это неравенство оказалось справедливым, т. е. рассматриваемая точка удовлетво-

С Начало )

( Конец )

Рис. 4.19. Схема алгоритма решения задачи

132

ряет данному ограничению, то осуществляется пе­ реход по стрелке «Да» к блоку 4, где вычисляется значение целевой функции в той же точке {х\=2 \

*2=25}. Оно присваивается переменной .у. Невыполнение условия z < 9 в блоке 3 оз­

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

ему действие jci: =*i+ 0,1 означает, что к зафикси­ рованному ранее значению переменной xi добав­ ляется число 0,1. Значит, при первом обращении к блоку 8 х\ примет значение 2+0,1=2,1 и таким об­

разом будет исследоваться точка {*1=2,1; *2=25}. Обратимся к операциям в блоке 5, выпол­

няемым вслед за операциями в блоке 4. Здесь ана­ лизируется выполнение неравенства у>М, то есть

проверяется, будет ли только что найденное значе­ ние целевой функции больше М. При первом об­ ращении к этому блоку М- 0 (блок 7), поэтому не­ равенство у>М в этом случае наверняка будет вы­

полнено, и, следовательно, произойдет переход к блоку 6 . Выполняемое здесь присваивание М:=у означает, что переменная М примет теперь значе­

ние, равное значению целевой функции в анализи­ руемой точке.

Согласно блоку 7 значения аргументов *i и хг присваиваются новым переменным а и Ь, ко­

торые тем самым будут хранить значения пере­ менных *1 и Х2, соответствующие значению целе­ вой функции, равному М. Далее выполняется пе­ реход к следующей точке с большим значением х\ (блок 8) и проверяется, не превысит ли это значе­ ние максимальной для него величины х\ = 4 (блок 9). Если оказалось, что *i< 4, то осуществляется

возврат к блоку 2, т. е. все описанные выше про­ цедуры, начиная с проверки выполнения ограни­ чения Z(x1, *2) < 9, выполняются для новой точки

{хих2}.

Отметим, что при втором и последующих обращениях к блоку 5 уже возможны разные слу­

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

чение, равное очередному возрастающему значе­ нию целевой функции Y(x1, *2)-

Если же в некоторой точке ее величина окажется меньше, чем в предыдущей точке (или

равна ей), то вследствие невыполнения неравенства у>М присваивание М:=у не будет сделано (блоки 6 и 7 обходятся). Благодаря этому переменная М сохраняет значение,

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

Вернемся к блоку 9 и рассмотрим случай, когда записанное в нем условие не выполняется. Это означает, что для данного значения хг=25 перебор по х\ следует за­ вершить и возобновить его вновь, начиная с X i=2, уже для следующего значения х2. По­ этому в блоке 10 реализовано присваивание xj: =2, а согласно блоку 11 значение х2 уве­

личивается на величину ее шага.

После этого осуществляется возврат к блоку 2, т. е. анализируется очередная точка. Невыполнение неравенства хг<35 в блоке 12 свидетельствует о необходимости завершить перебор. В этом случае согласно блоку 13 выводится на печать найденное

оптимальное решение: значение М, равное максимальному значению целевой функции по всем точкам из области допустимых решений, и значения переменных а и Ь, равные аргументам xi и х2 в точке оптимума. Этим завершается работа алгоритма. Реализация его на ЭВМ позволила получить следующие результаты: а =х\ опт =3,7; Ъ =х2 от- =35; М=

=Гопг=301,79.

4.4.6. Метод допустимых направлений

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

Рис. 4.20. Схема метода допустимых направлений

Пример. В задаче с двумя переменными х\ и Х2 начальная точка xQ рас­

положена внутри ОДР, а ограничения линейны (рис. 4.20). Областью допустимых ре­ шений в данном случае служит часть первого квадранта координатной плоскости, ле­ жащая внутри угла ABC. На рис. 4.20 изображены также линии уровня целевой функ­

ции / ( * ) , которую требуется максимизировать. Вначале поиск будет осуществляться

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

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

4.4.7. Математическая модель задач оптимизации режимов механической обработки древесины

Для задач оптимизации режимов механической обработки древеси­ ны разработана общая математическая модель в рамках задачи нелинейно­ го программирования [26]. Она применима, в частности, к процессам свер­ ления, точения, шлифования, пиления древесины круглыми и ленточными пилами. Оптимизационная модель процесса рамного пиления древесины имеет ряд особенностей и поэтому была рассмотрена отдельно (п. 4.1.2). Элементами решения в общей математической модели служат скорость подачи, период стойкости режущего инструмента, а также параметры его формы и геометрические размеры. Общее число переменных не превышает шести.

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

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

СпсР= 30 + 3И.

(4.37)

Эту величину и рассматривают в качестве целевой функции.

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

З о = 'обр ( g + r + ^ + a + b 3 ) + t ^ { g 0 + r + r n + a + b , \

( 4 . 3 8 )

где *обр ~ длительность обработки одной детали, мин; tx - длительность работы станка вхолостую, мин;

g - затраты на электроэнергию, израсходованную на обработку за 1 мин;

go - затраты на электроэнергию за 1 мин при работе станка вхоло­ стую;

г - заработная плата рабочего-станочника за 1 мин; гп - заработная плата подсобных рабочих за 1 мин; а - амортизационные отчисления за 1 мин;

Ьэ - эксплуатационные расходы за 1 мин - техническое обслужива­ ние, ремонты и т. д.

Длительность рабочего хода станка /р. х складывается из длительно­ сти обработки ?обр и длительности tx работы станка вхолостую до входа и после выхода инструмента из заготовки:

' р . * = ' о б р + ' х -	( 4 . 3 9 )
Обозначим через е отношение времени обработки к времени рабо­
чего хода:
е = 'обр/('обр+0-	(4-4°)
Отсюда
l )	(4-41)
Подставив выражение (4.41) в формулу (4.38), получим
3 0 = ?обр [ g - g 0 - 0/s)(go+ r + rп + а + К )]■	(4-42)

Второе слагаемое в формуле (4.37), т. е. затраты, связанные с изно­ сом инструмента, приходящиеся на обработку одной заготовки, равны

Зи =ХЗ/ЛГ,

(4.43)

где N - число заготовок, обработанных инструментом за период стойкости; ^ 3 - сумма всех затрат за период стойкости, связанных с затуплением

инструмента, т. е. его сменой и подготовкой.

	£ 3 =<п(ен£„ + r + a + b3)+ tHr„ + (кСт/гзет)+ &СЮТ,	(4.44)
где tn-	длительность простоя станка при смене и подготовке инструмен­
	та;
tH-	время, затрачиваемое наладчиком на смену и подготовку инстру­
	мента (как правило, tn= /н);
ен -	коэффициент, учитывающий долю холостых ходов станка при его
	подналадке;
гн -	заработная плата наладчика за 1 мин;
Син -	затраты на новый инструмент;
*зат -	число заточек, допускаемое конструкцией инструмента;

136

Сзат - затраты на одну заточку с накладными расходами заточного отде­ ления;

к- число инструментов.

Вчастном случае, когда инструмент сменяется и подготавливается

врабочее время рабочим-станочником, tH= 0. Если смена и подготовка ин­ струмента выполняются рабочим-наладчиком в нерабочее время, то в этой формуле полагают г = 0.

Число заготовок, обработанных инструментом за период стойкости

N = T„m/to6p,

(4.45)

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

	Ta = L J 0 6/LM,	(4.46)
где LM-	путь резца в древесине за 1 мин, мм.
Длительность обработки одной заготовки
	*„бр Ч / к ,	(4.47)
где /0 - длина обрабатываемой заготовки, м;
и -	скорость подачи, м/мин.

Подставив выражения для Гст (4.46) и для fo6p (4.47) в формулу

(4.45), получим

L^mu	,	(4.48)
N = — —	106.
L J0
Тогда формула (4.43) примет вид
3 „ = I 3 I M/0/(V * « -1 0 6).		(4.49)
Подставив выражения для 30 (4.42) и для Зи (4.49) в формулу (4.37)
с учетом (4.47), получим выражение для целевой функции:
С„ер = (/„/u)[g - g 0 + (1/e)(g0 + r + r„+a + b3)] +
+ T . 3L J0/{L„mu-106).		(4.50)

Упростим эту формулу, выделив в ней элементы решения, которы­ ми служат и и LCT:

CtKf= a l/u + bJ(uLet),

(4.51)

137

где a, = l0[g~ So + (l/e) (g„ + r + rn + a + b3)];

* i = I > M/o/(W-106).

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

с пер = а х/ и + ЬJ {u L „ ) + C,i,

(4.52)

где с\ - коэффициент, равный стоимости потерь сырья из расчета на 1 мм толщины пилы.

Рассмотрим теперь вывод формулы для целевой функции по крите­ рию максимума производительности обработки. Штучная производитель­ ность 77 станка за смену при однооперационной обработке определяется по формуле

П = к обТ ш т п / К к + К + *вц )>

( 4 -5 3 )

где tBц - внецикловые потери времени на одну операцию, связанные с из­ носом и затуплением режущего инструмента;

tB- суммарная длительность всех вспомогательных операций;

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

За период стойкости внецикловые потери времени, связанные с из­

носом и затуплением режущего инструмента, равны длительности простоя станка при смене и подготовке инструмента /п- Следовательно, внецикло­ вые потери на одну заготовку равны tm= tn/N. Использовав формулу (4.48), получим

tm = tnL J0/(L„mu-106).

(4.54)

Выражение для tр. х найдем из формулы (4.39), подставив в нее значение Гр. х (4.41): tp x =?обр/е. С учетом (4.47)

' р.* =/<,/«*•

(4-55>

Подставив выражения для tBll (4.54) и для tр. х (4.55) в (4.53), получим искомую формулу для целевой функции

77 = -------------

КобТсмтп-----

-----

(456)

lo/us + tnLJo/[L„mu-l0 j+ tB

Поскольку числитель этого выражения не зависит от элементов ре­ шения, достижение максимума производительности эквивалентно мини­ мизации знаменателя функции (4.56). Его переменную составляющую можно переписать в виде

138
Q = a 2/u + b2/uLCT>	(4.57)

где a2 =lo/& ; b2 = tnL Jo/{m -\0e). Величина Q является целевой функцией, подлежащей минимизации.

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

Покажем это применительно к процессу распиливания бревен на пиломатериалы. Параметр п в формуле (4.56) будет в данном случае озна­ чать число досок, выпиливаемых из одного бревна, а величина т равна 1. Поделив выражение (4.56) на п и умножив его на величину Vn объема пи­ ломатериалов, вырабатываемых из одного бревна, получим выражение для производительности П\ станка в кубометрах вырабатываемых пиломате­ риалов:

	П\ = ПУп/п\	(4.58)
	Vn = V6 - 2VT- 10~3S{s + 2X\	(4.59)
где V6 -	средний объем бревна, м3;
Vr -	средний объем горбыля, м3;
S -	суммарная площадь пропилов в бревне, м2;
X -	величина уширения зубьев пилы на сторону, мм.

Величины V6 и Vr нетрудно вычислить, пользуясь обычными моделями по­ верхности бревен в виде усеченных конусов или параболоидов вращения. Подставив в формулу (4.58) выражения для П (4.56), с учетом т= 1, и для

Vn(4.59), получим

п	а д м[Гб2Гг - 10-3^ + 2Я)]	g} - g 2s
'	l J u e + tnL J o/{LCTu l 0 6) + t s	l J u 6 + taI ^ l e/(LQtu l 0 * ) + t M’

Я. = а д м Ь - 2 К г -2210-35];

£2 = В Д м1(Г35.

Перепишем выражение для Пхв виде

п	gi(g\!8 г~ s)L„u

'{ l J z ) L „ + tnL J 0l \ Q 6 + t BL„u

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

Q2 = --------------------------

> max,

(4.60)

a 2La. + c 2 u L „ + b 2

где c2 = tB; c3 = g j g 2, а коэффициенты a2 и b2 определяют по тем же

формулам, что и для выражения (4.57), с учетом т = 1.

Совокупность ограничений математических моделей процессов ме­ ханической обработки древесины можно разделить на три группы:

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

2)качественные - по точности обработки и качеству обрабатывае­ мой поверхности; применительно к процессу пиления древесины на лесо­ пильных рамах рассмотрены в п. 4.1.2;

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

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

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

w\{x\>xi ) = Aolx\ + я 0/(х1х2)-»тш ;	(4.61)
W2(х,, х2, х ,)= /1, /Х] + В ]/(х1х2)+ С,х3 —>min;	(4.62)
'\>л2>лЗ/~
-> max;	(4.63)

и ограничениями

(4.64)

(4.65)

Здесь целевые функции - это выражения (4.51), (4.57), (4.52), (4.60), пере­ писанные с учетом замены и -» jcj; LCT-» х2; s -» х3. Практически число ограничений вида (4.64) не превышает восьми.

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

Оптимизационные модели, описываемые соотношениями (4.61)- (4.65), относятся к задачам нелинейного, невыпуклого программирования. Последнее означает, что поставленная задача может быть многоэкстре­ мальной и, следовательно, достаточно сложна. Алгоритм, специально раз­ работанный для ее решения [26], учитывает специфику задачи, в частно­ сти тот факт, что ее целевая функция зависит не более чем от трех пере­

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

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

Назовем совокупность значений трех переменных хг, х2, х3, входя­

щих в целевую функцию, допустимой тройкой, если для нее можно найти такие значения остальных переменных, при которых совокупность значе­ ний всех переменных {хр ..., х6} удовлетворяет всем ограничениям зада­

чи. Здесь предполагается, что значения переменных х], х2, х3 берутся из

множества

*< min ^

^ * / max > * = 1, 2 , 3 .

( 4 . 6 6 )

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

Согласно алгоритму на первом этапе выполняется перебор троек {хх, х2, х3} из множества (4.66) с помощью сетки, равномерной по каждой

координате. Для этого каждый из отрезков [xjmin, */max], / = 1, 2, 3, разби­

вается на равные части заданной длины. На втором этапе выполняется проверка каждой тройки на допустимость. Тройка {х{, х2, Зс3} будет до­

пустимой, если система неравенств (4.64), (4.65) окажется совместной при

х{ = х {; х2 = х 2; х3= х 3.

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

4.5. Задачи целочисленного программирования в деревообработке

4.5.1. Общие сведения

При построении математических моделей различных объектов ино­ гда оказывается, что к некоторым переменным следует предъявить допол­ нительные требования дискретности или целочисленности. С моделями таких задач мы, по существу, уже сталкивались. Так, при рассмотрении за­ дачи формирования производственной программы мебельной фабрики (п. 3.1) следовало бы потребовать, чтобы значения переменных х29 х3, по­

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