pizhurin_a_a_pizhurin_a_a_modelirovanie_i_optimizaciya_proce

331

0 < х и< а и, ( i , j ) e а;

(11.30)

dtJ>0. (11.31)

Математическая формулировка задачи 1 следующая: максимизиро­ вать F при условиях (11.27) - (11.31). Для решения этой задачи разработан эффективный алгоритм, позволяющий даже вручную отыскивать решение при достаточно сложной сети [12]. Его называют алгоритмом Форда и Фалкерсона.

В задаче 1 не затрагивается вопрос о себестоимости обработки. В связи с этим рассмотрим задачу 2, в которой себестоимость служит крите­ рием оптимальности.

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

Переформулирование этой задачи на математический язык сле­ дующее: дана ориентированная сеть; для каждой дуги (z,y) заданы ее про­ пускная способность dy и стоимость Су доставки единицы потока из узла i в узел j (Су > 0); определить величины потоков для каждой дуги, соответст­ вующие их пропускным способностям и обеспечивающие минимум сум­ марной себестоимости доставки потока от источников к стокам. При этом заданы величины чистых потоков для каждого узла сети. Эту задачу мож­ но формально записать в следующем виде: минимизировать

I

(11. 32)

0'.У')ба

при условиях (11.25), (11.26), (11.30), (11.31). Точно так же, как и задачу 1,

задачу 2 можно переформулировать, сведя ее к случаю только с одним ис­ точником и одним стоком. Все остальные узлы при этом становятся про­ межуточными пунктами.

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

Х С!/ХУ

(11.33)

(/,/)€<*0

при условиях (11.27) - (11.31), где d0 - множество дуг расширенной сети, то есть сети с введенными дополнительно фиктивными узлами 0 и (N+1). Назовем задачу (11.33), (11.27) - (11.31) задачей 2а. Она может рассматри­ ваться как задача линейного программирования с двусторонними ограни­ чениями.

Доказано [12], что задачу 2 или 2а всегда можно свести к эквива­ лентной транспортной задаче. В связи с этим задачи типа 2 и 2а принято называть транспортными задачами в сетевой постановке. Для решения этих задач могут быть использованы модифицированные методы решения обычных транспортных задач. Имеется алгоритм решения этих задач, при­ годный для ручного счета. Он основан на многократном применении алго­

ритма Форда и Фалкерсона для решения задачи о максимальном потоке

[12].

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

При таком построении ориентированной сети возникают дополнительные сложности. Прежде всего, среди элементов исходного множества может оказаться не­ сколько станков, выполняющих одни и те же функции, но отличающихся лишь величи­ нами Су и dy. Дуги, соответствующие этим станкам, должны соединять одни и те же уз­ лы. В то же время при построении ориентированной сети любые два узла могут соеди­ няться не более чем одной дугой. В такой ситуации можно поступить следующим обра­ зом. Пусть имеется / станков, перерабатывающих полуфабрикат, соответствующий узлу s, в продукцию, соответствующую узлу /. Пропускные способности и стоимости доставок для соответствующих дуг равны </ , d {!\ с (1), с (2),..., с (/). Для построе­ ния фрагмента сети, соответствующего этим станкам, введем дополнительно (/-1) узел, а именно: узлы (/+1), (/+2),..., (/+/-1) (рис. 11.2). Каждый из этих узлов символизирует то же состояние продукта, что и узел t. Каждому из / рассматриваемых станков сопос­ тавим по дуге (5, t \ (я, /+1),..., (5, t+ l-1) и припишем им соответствующие величины пропускных способностей и стоимостей доставки:

d —d ^

»

d

—d

d

—d ^

’

с

s, t

—

с

—с

с

—с ^

u s, i и

u s, /+ 1

и

>•••» u s,t+l- 1

w

* Lsyt+ 1

c

»•••» s, l+l—l

L

Введем еще один узел (t+l), интерпретируемый так же, как и узел /. К узлу (t+l) проведем дуги из узлов t, (/+1),..., (/+/-1). Припишем всем этим дугам величины пропу­ скных способностей, равные бесконечности, и величины стоимостей доставки, равные нулю:

dtt t+i —dt+u t+i	—d(+i_\t (+/ = 00;
c t, t+i — c t+1, t+i —	" = £/+/-1, t+i = 0.

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

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

333

Рис. 11.2. Альтернативные варианты в задаче выбора оборудования

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

Построенная таким образом ориентированная сеть включает все возможные варианты использования заданного оборудования. В число условий задачи оптимально­ го выбора оборудования должны войти все соотношения, которые определяют задачу 2, то есть ограничения (11.25), (11.26), (11.30), (11.31) и требование минимизации сум­ марной себестоимости процесса (11.32). Для того чтобы модель отражала необходи­ мость выбора единственного оптимального набора станков из множества имеющихся вариантов, необходимо ввести еще одну группу ограничений. Рассмотрим множество пар дуг, соответствующих конкурирующим вариантам: R = {(г, г); (р, g)}. Станки, соот­ ветствующие дугам (г, t) и (р, g), - взаимоисключающие: при решении задачи следует выбирать какой-либо один из этих двух вариантов. Соответствующее условие имеет следующий вид: xrtxpg = 0. Число таких условий в задаче равно количеству элементов в множестве R, т. е. числу пар конкурирующих станков.

Пусть узел 1 - источник; узел N - сток, символизирующий готовую продук­ цию; множество остальных стоков обозначим через S, а множество всех прочих узлов (промежуточных пунктов) - через L. Тогда, рассмотрев условие (11.25) для каждого из перечисленных множеств, можно записать задачу выбора оборудования в следующем виде:

min. (i/>е сс;

je A { \)

334

£ xy ~TN2.ПЫ;

J e B (N )

E xJS-	%x si =Ts < n s> s s S ;
ieB (s)	je A (s)

E xu -	Z xy/=°> leL ’
Ш (1 )	jc-B(D
	N
	Z ?i= 0;
	/Ы
0£xv £dv, (i,j)ea;
	dtJ>0;
	c,j> 0;

х,,*рг=0, ((r/); (pg)etf)>

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

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

11.4. Статистическое моделирование раскроя пиловочного сырья

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

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

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

Разработанная в результате их применения статистическая модель формирования и раскроя хлыстов и бревен [27] служит эффективным ин­ струментом для решения целого ряда научных и производственных задач лесопиления. Соответствующий пакет машинных программ, реализован­ ный на ЕС ЭВМ, позволяет имитировать процесс раскряжевки хлыстов с получением бревен различных размерных и качественных характеристик, а также процесс раскроя бревен на пиломатериалы. По результатам работы первой части программы моделируется формирование любого заданного количества бревен из хлыстов и сортирование их по диаметрам.

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

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

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

11.4.2 Математические модели поверхности хлыстов и бревен

Рассмотрим уравнение поверхности хлыста с учетом возможной криволинейности его оси, эллиптичности поперечного сечения с образую­ щей заданного вида. Возьмем систему координат oxyz. Пусть хлыст распо­ лагается вдоль оси z\ z=0 - аппликата комлевого сечения; z=Lx - аппликата вершинного сечения, Lx- длина хлыста (рис. 11.3, а).

Рис. 11.3. Модель поверхности хлыста:

а - расположение хлыста в системе координат oxyz; б - поперечное сечение поверхности хлыста

Рассмотрим сечение хлыста плоскостью, перпендикулярной к оси oz, на некотором расстоянии z от начала координат, 0< z <LX. Предполага­ ется, что в сечении хлыста эллипс (рис 11.3, б). Эта модель вполне удовле­ творяет практическим требованиям. Обозначим через f\ и f 2 координаты центра этого эллипса, а через а и Ъ - соответственно большую и малую его полуоси, в дальнейшем будем называть их горизонтальной и вертикальной полуосью.

Уравнение такого эллипса, как известно, имеет вид

rx - f \ '	2	У -	2
	+		= 1	(11.34)
V а )	<	b	j

Условимся, что ось z проходит через центры комлевого и вершин­ ного сечений хлыста. Величиныf и /2 в уравнении (11.34) являются функ­ циями от z:

/i= /i(z );

/2 = / 2(2).

(11.35)

Эти функции задают уравнения оси хлыста в параметрическом ви­ де. Параметром здесь является z. Точно так же будут функциями от z пара­ метры а и Ъв этом уравнении: а - a(z); Ъ= b(z). Уравнение (11.34) теперь примет вид

2

	+	У~ fi(z)	J = 1.	(11.36)
^ a(z ) J		к Kz)

При этом значения z ограничены диапазоном

О< z< L x.

(11.37)

Функциями a(z) и b(z) описываются горизонтальная и вертикаль­ ная образующие хлыста. В большинстве случаев на практике достаточно пользоваться их представлениями в виде многочленов не выше четвертого порядка:

a(z) = ao + £ a,z';		(11.38)
1= 1
b{z) = b 0 + Y	, b j Z ‘ .	(11.39)
i	=1

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

при общем виде горизонтальной и вертикальной образующих хлыста (11.38) и (11.39) и в предположении, что сечение хлыста имеет форму эл­ липса. Требуемая эллиптичность сечения достигается заданием отличаю­ щихся друг от друга значений коэффициентов я, и bt в формулах (11.38) и (11.39). При этом в зависимости от того, какие коэффициенты я, и bt разли­ чаются и насколько, получаются различные законы изменения эллиптич­ ности вдоль оси хлыста. В частном случае, когда а{ = bf для всех /=0, 1,..., 4, в любом сечении хлыста будет круг. Очевидно, что поверхность бревен тоже описывается в общем виде уравнением (11.36). Однако, в отличие от задания функций для хлыстов, функцииf\( z \f 2(z\ a(z) и b(z) здесь следует задавать более простыми. Диапазон изменения z в этом случае, разумеется, сократится до величины L длины бревна.

Рассмотрим способы описания кривых хлыстов и бревен, т. е. по существу, способы задания функций f\(z) и f 2(z) в системе (11.40). Функ­ ции, описывающие кривизну хлыстов, должны быть многоэкстремальны­ ми, так как хлыст может иметь несколько волн кривизны. Величины экс­ тремумов должны быть в общем случае тоже различными. Подобным тре­ бованиям удовлетворяют, например, многочлены достаточно высокой сте­ пени. Другое удобное представление для оси хлыста - функции вида

/ y(z)=(c2z2 +c,z + c0)sin[co(z)+<p], 7 = 1,2.

(11.41)

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

Если использовать уравнение (11.36) для описания поверхности бревен, а не хлыстов, то задача упростится. Чаще всего ось кривого брев­ на - это участок плоской выпуклой (или вогнутой) кривой. Пусть эта кри­ вая располагается в плоскости yoz. Тогдаf(z) = 0, а функциюf 2(z) в первом приближении можно описать уравнением параболы. Часто такое представ­ ление, однако, является слишком грубым, так как при этом оказывается, что наибольшее отклонение от оси всегда будет в середине бревна. Более приемлемо в этом смысле представление оси бревна в виде многочлена третьего порядка: f 2(z) = с0 + cxz + c2z 2 + c3z 3.

Коэффициенты с, разумно задавать так, чтобы обеспечить выполне­ ние двух требований: 1) ось бревна пересекает ось z в заданных точках

z= zK(комлевое сечение) и z = zB(вершинное сечение), при этом zB- z K- L \

2)максимальное отклонение 5 оси бревна от прямой, соединяющей точки z = zKи z = zB, наблюдается в заданной точке z0, причем zB< z0 < zB. Эти

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

c0+c^K+c2zl+c3zl= 0;

С0 + С 12 в +c2Zl + C 3Z b = ° ;

(11.42)

с0 "Ь CjZ0 -ь c2Zq -I-c^Zq —kL.

В последнем уравнении отклонение 5 записано как kL, где к = 5// - величина, называемая в лесопилении кривизной (в относительных едини­ цах).

Легко убедиться, что уравнение (11.36) является обобщением из­ вестных представлений о форме хлыстов и бревен. Так, положив в нем f ( z ) = f 2(z) = 0, пренебрегая возможной эллиптичностью бревна и считая образующие его прямолинейными: a(z) = b(z) = яо+ #i(z)> получим уравне­ ние поверхности бревна, представленного в виде прямого кругового усе­ ченного конуса:

х2 + J/2 = (а0 + fljz)2;

0 < z< L .

Рассмотрим простейшую модель поверхности криволинейного бревна. Предположим, что имеет место случай простой кривизны и наи­ большее отклонение 5 достигается в середине бревна. Величина кривизны к = Ь/Ь предполагается заданной. Тогда ось бревна можно считать плоской кривой, имеющей единственный максимум в точке {z0 = (zB+ zK)/2, f 2(z0)=b = kb} и вернуться к ее представлению в виде уравнения парабо­ лы:

(11.43)

(11.44)

Найдем значения коэффициентов ch i = 0, 1,2. Полагаем, что комле­ вое сечение бревна располагается в плоскости z = 0; вершинное - в плос­ кости z = L, и в этих плоскостях ось бревна пересекается с осью аппликат

OZ (см. рис. 11.3, а). Тогда zK=0; zB= L; f 2(zK) = f 2(0) = 0;/2 (zB) = f 2 (L) = 0.

Кроме того, согласно предыдущему предположению z0 = (zB+ zK)/2 = L/2

и f i (zo)= /2 (£/2) = • Подставив в формулу (11.44) поочередно каждое из трех значений z: z —0; z=L; z = L/2, получим с использованием результатов

проделанных вычислений: со=0; 0= cxL + c2L2; kL = C]L/2 + c2L2/4. Решив систему из последних двух уравнений, найдем:

340
с, = 4 k ;	(11.45)
с2 = - 4 к/L.	(11.46)
Таким образом, в данном случае, уравнение криволинейной оси
бревна имеет вид
/ 2(z)= 4k z - (4k/L)z2.	(11.47)

Предположим далее, что бревно имеет круглое сечение, вершинный диаметр db и постоянный по длине сбег S. Последнее простейшее предпо­ ложение означает, что функции a(z) и b(z), которыми описываются обра­ зующие бревна, являются линейными:

		a(z) = b(z) = ao+ a\z.	(11.48)
Найдем значения ао и ah При z = 0, a{z) = dK/ 2 i а			при z = L,
a(z)=d9/ 2 9 где dK-		комлевой диаметр бревна. Подставив поочередно зна­
чения z =	0 h z = L	b (11.48), получим а0 = d K/ 2; dB/2 = a0 + a]L, откуда
а\ ~ (^в -	)/ 2L. Но по определению сбег S равен: S = (dKdb) / L . По­
этому ах- - S / 2. Следовательно,
		a(z) = b(z) = (ds) / 2 - ( S / 2 ) z .	(11.49)

Воспользовавшись найденными выражениями для /i(z), fi(z\ a(z) и Z>(z), получим для рассматриваемого случая модель поверхности бревна в виде

(11.50)

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

11,4.3. Влияние эллиптичности бревен на объемный выход пиломатериалов

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