pizhurin_a_a_pizhurin_a_a_modelirovanie_i_optimizaciya_proce

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

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

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

значениями переменных. Более того, ближайшее округленное решение может вообще не принадлежать ОДР.

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

+ х2 -> шах;			(4.67)
4^	+3*2 <12;		(4.68)
	х2 ^ 1)8;		(4.69)
*! > 0;		х2 > 0;	(4.70)
х}, х2 -		целые.	(4.71)

Опуская условие (4.71), найдем сначала решение задачи (4.67) - (4.70), являю­ щейся обычной задачей линейного программирования. На рис. 4.21 дана ее геометри­ ческая интерпретация. Четырехугольник ОАВС является областью допустимых реше­ ний задачи. Прямая W описывается уравнением хх+х2 = с , где с - некоторая констан­

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

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

Решив систему (4.72), получаем оптимальное решение ЗЛП: ххот = 1,65;

X2опт — *

Для получения решения исходной задачи, содержащей дополнительно условие целочисленности (4.71), попробуем сначала округлить решение, полученное выше для ЗЛП (4.67) - (4.70). Имеем х} - 2; х2 =2. Это точка Е, координаты которой, очевидно,

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

что оптимальным решением будет точка х{ = 2 ; х2 = 1, для которой значение целевой

функции равно 3.

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

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

первом случае говорят о полностью целочисленной задаче, во втором - о частично целочисленной задаче математического программирования. Для задач, в которых переменные должны принимать дискретные, но не цело­ численные значения, существует способ сведения их к задачам целочис­ ленного программирования. Часто здесь используют нормирование пере­ менных. Так, значения толщины пил для приведенного выше примера можно задать в десятых долях миллиметра и получить для них целочис­ ленные значения 20; 22; 25 и 32.

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

4.5.2. Задача о назначениях

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

тельность монтажа г-го объекта у-й бригадой, где i = 1, ..., и; у = 1, ..., п. Введем переменные xtj, условившись, что каждая из них может принимать

только одно из двух значений: 0 или 1. Переменная х. . равна единице

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

143

£>,.,= 1, j = 1, 2,..., и.	(4.73)
>1

Условие гарантированного закрепления за каждой бригадой какоголибо одного объекта записывается в виде

2 > <у=1, 7=1, 2,..., л.	(4.74)
/=1

Сучетом ограничений (4.73) и (4.74) выражение для суммарного

пп

времени монтажа всех объектов можно записать в виде суммы XX*//*//-

/=1 j=\

Она будет целевой функцией данной задачи:

(4-75)

;=l y=i

Построенная модель похожа на транспортную задачу (3.74) - (3.78), при т=п и я/=£у=1. Единственное отличие - это требование целочисленности переменных xtj. В теории линейного программирования доказано,

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

хи > 0 9 /= 1, ...,и; j = 1,..., п,

(4.76)

получив тем самым модель транспортной задачи, то она все равно будет иметь целочисленное решение. Аналогичное утверждение верно для транспортной задачи общего вида (3.74) - (3.78): она всегда имеет цело­ численное решение, если все а(и bj - целые числа.

Таким образом, для решения задачи о назначениях пригоден любой алгоритм решения транспортной задачи, в частности изложенный выше метод потенциалов (пп. 3.6.2, 3.6.3). В отличие от нее, для решения рас­ сматриваемых ниже оптимизационных задач необходимы специальные ме­ тоды целочисленного программирования.

4.5.3. Задача о реконструкции

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

144

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

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

Ni - количество вариантов реконструкции для /-го предприятия,

1=1,...,Л

ау - объем выпуска продукции i-м предприятием при реализации у-го варианта его реконструкции;

Зу - затраты на реконструкцию по j -му варианту для /-го предпри­ ятия,у=1, ...,М ; /= 1,

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

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

[ руироваться поj -му варианту.

Требование реализации только одного варианта реконструкции для каждо­ го предприятия запишется в виде следующего ограничения:

f > . . = l , /	=	1	,	.	(4.78)
j =1

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

рNi

/=i j=\

Выражение
И з , - ,	(4-79)

1= >1

является минимизируемой целевой функцией задачи.

4.5.4. Вариантная модель задачи о размещении

предприятий

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

£ . , < 1 , /=1,...,/».

(4.80)

7=1

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

4.5.5.Задача о специализации

лесопильно-деревообрабатывающих предприятий (ЛДП) по сечениям вырабатываемых пиломатериалов

Содержательная постановка этой задачи дана во введении. Рас­ смотрим одну из возможных ее математических постановок - вариантную модель. Предположим, что задача решается на уровне производственного объединения, в состав которого входят т ЛДП. Для каждого из них со­ ставлено несколько возможных вариантов специализации. Пусть Rt - число вариантов, разработанных для /-го ЛДП, /=1, 2, ..., т. Обозначим через aris

объем выпуска товарных пиломатериалов 5-го сечения на z-м предприятии согласно г-му варианту. Здесь г =1, 2, ..., Rh s =1, 2, S. Через S обозна­ чено общее число сечений пиломатериалов, вырабатываемых в объедине­ нии. Очевидно, что некоторые aris могут быть равны нулю. Это означает,

что в случае реализации данного варианта специализации пиломатериалы соответствующего сечения не будут вырабатываться на предприятии. На­ ряду с величинами aris будем считать известными затраты на производство

1 м3 пиломатериалов s-rо сечения для /-го предприятия при г-м варианте специализации сГ.

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

		(4-si)
	5=1	р = 1
	r= 1,	/=1,2, ...,ю,
гДе QiP -	объем пиловочного сырья /?-го четного диаметра, поступившего в
	течение года на /-е предприятие;
Р -	число диаметров бревен;

&ср - коэффициент объемного выхода пиломатериалов, усредненный по всем применяемым поставам.

Ограничение (4.81) реализует требование, чтобы общий объем пи- лопродукции /-го предприятия при r-м варианте специализации соответст­ вовал его сырьевым ресурсам. Имеется еще несколько ограничений на ве­ личину ais,r связанных с возможностью выработки пиломатериалов соот­

ветствующей гаммы сечений.

Предположим, что все пиломатериалы, вырабатываемые в объеди­ нении, отправляются потребителям. Обозначим через bjs объем пиломате­ риалов 5-го сечения, на который имеется заявка от j -го потребителя: s =1, ..., S ,j =1, ..., и, где п - число потребителей пиломатериалов, выраба­ тываемых на ЛДП данного объединения.

Пусть xisj - объем пиломатериалов s-ro сечения, поставляемых /-м ЛДПу-му потребителю. Условие того, что выполняется заявка любого по­ требителя по пиломатериалам каждого сечения, имеет вид

1*ц =ЬМ’	(4.82)
Z=1

Введем целочисленные переменные z[. Будем считать, что z\ =+1, если

для z-ro ЛДП принимается г-й вариант специализации, и z\ - 0 - в против­

ном случае, r= 1, ..., R{. Очевидно, что из вариантов, рассматриваемых для z-го предприятия, должен быть выбран только один. Это условие за­ пишется в виде

J ]z r= l, /=1,	(4.83)
г=1

При введении обозначений и условия (4.83) можно записать выра­ жение для объема выпуска пилопродукции 5-го сечения z-м предприятием

в виде А	• Суммарный объем поставок пилопродукции от данного
Г=1

ЛДП по каждому сечению равен объему выпуска товарных пиломатериа­ лов этого сечения, т. е.

i t xisjzr£ aisz i' s= l,...,S ; i= l,...,m .		(4.84)
j= l	r =1

Обозначим через ц затраты на перевозку 1 м3 пиломатериалов от z-ro ЛДП ку-му потребителю. Тогда целевая функция задачи, реализующая критерий минимума суммарных затрат на производство и транспортирова­ ние пиломатериалов, представляется в виде

т Rj S т п S

w =	+	z z z	w	(4-85>
	i=1 Г=1 5=1	1=1 j =1 5=1
Добавив естественные ограничения на неотрицательность пе­
ременных
xbj >0,	г'=1, ...,/я;	s= l,...,S;	j = l , ...,«,	(4.86)

можно сформулировать задачу следующим образом: требуется отыскать значения непрерывных переменных х^ и целочисленных переменных z r ,

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

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

4.5.6. Задача о выборе головного лесопильного оборудования

В качестве головного лесопильного оборудования могут использо­ ваться лесопильные рамы, линии агрегатной переработки бревен (ЛАПБ), фрезерно-пильные, круглопильные, ленточнопильные станки и некоторые другие виды оборудования. Его основными технологическими характери­ стиками можно считать производительность и коэффициент объемного выхода пиломатериалов, которые зависят от размерных характеристик сы­ рья. Так как в лесопильный цех может одновременно поступать сырье не­ скольких размерных групп, оказывается целесообразным иметь в цехе оборудование нескольких видов и закрепить за каждым из них распилива­ ние сырья определенной размерной группы. По результатам решения рас­ сматриваемой задачи для заданного соотношения объемов размерных групп сырья определяется оптимальный состав головного оборудования проектируемого или реконструируемого лесопильного цеха, а также коли­ чество и размерные характеристики сырья, которым должен быть загружен каждый поток.

Приведем основные соотношения, иллюстрирующие возможную идею построения математической модели задачи. (Крылов Г. В. Исследо­ вание и разработка метода определения оптимального сочетания типов го­ ловного оборудования лесопильного цеха. Автореф. дис. на соискание уче­ ной степени канд. техн. наук. - М. 1980).

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

Tljj - производительность j -го вида оборудования по раскрою сырья i-й размерной группы;

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

Введем целочисленные переменные:

I, если сырье /-й размерной группы раскраивается на обо­
рудованииj -то вида;	(4.87)
IО -в противном случае.

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

(4.88)

Выражение для стоимости всей вырабатываемой продукции запи­ шется в виде

Ц с ' Л м .

/=i>i

Оно входит в целевую функцию, реализующую критерий максимума при­ веденного дохода.

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

т

рудования по раскрою сырья z-й размерной группы равна ^ n ijxij .

У=1

Теперь легко получить оценку для количества p t станков, занятых распиливанием этого сырья:

	я ;
P i =	(4.89)

Т ,Щ х к

м

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

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

4.5.7. Методы решения задач целочисленного программирования

Можно выделить три основные группы методов.

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

процесс. Вначале задача решается без условия целочисленности. Если по­ лученное в результате решение будет целочисленным, то исходная задача решена. Если нет, то к ограничениям задачи, решенной на предыдущем этапе, добавляется еще одно линейное ограничение, обладающее следую­ щими двумя свойствами: 1) полученное нецелочисленное решение ему не удовлетворяет; 2) любое допустимое целочисленное решение ему удовле­ творяет. Такое дополнительное ограничение называется правильным от­ сечением. Затем решается полученная ЗЛП с дополнительным ограниче­ нием. В случае, если решение и этой задачи не будет целочисленным, до­ бавляется еще одно линейное ограничение, являющееся правильным отсе­ чением. Решается новая задача линейного программирования и т. д., до получения целочисленного решения.

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

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

Изложим алгоритм решения целочисленной задачи линейного про­ граммирования, разработанный Р. Гомори. Он относится к группе методов отсечения. Рассматривается задача целочисленного линейного программи­ рования общего вида:

W = ^ C jXj -> min (max);	(4.90)
р , '+ 1 р,7 * ,К = ’^ 0’	(4-91>
ху >0, j =	(4.92)
Xj - целые числа.	(4.93)
Предварительно укажем способ построения правильного отсечения.
Предположим, что задача линейного программирования (4.90) -	(4.92)

сведена к ОЗЛП и решена симплекс-методом. В стандартной табл. 4.2 при­

ведено ее оптимальное решение: у х=Ьх\ у 2 =Ь2,...; у к =Ьк,...;	Ут=Ьт;
2i = z 7 = • *• = zn= 0. Здесь через у р..., ут обозначены базисные,	а через

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

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

{ a J z 1+... + { a Jz ,,> { it }.

(4.94)

Можно доказать, что это ограничение обладает всеми свойствами правильного отсечения. Обозначение {а}, присутствующее в неравенстве (4.94), означает дробную часть числа а, т. е. разность между числом а и наибольшим целым числом, не превышающим а. Например, {7,3} = 7,3 - - 7 = 0,3; {- 2,4} = - 2,4 - (- 3) = 0,6.

				Т а б л и ц а 4.2
Базисная пе­	Свободный		Свободные переменные
ременная	член	zi	Z2	zn
•Vi		«и	«12	«1»
У2	*2	«21	«22	«2л
Ук	ьк	«*1	«*2	«Ал
Ут	ьт	«ml	«m2	«/пи
W	с 0	У\	72	Уп

Алгоритм решения задачи целочисленного линейного про­ граммирования (4.90) - (4.93) включает следующие эт^апы.

1. Решить симплекс-методом задачу линейного программирования (4.90) - (4.92). Если полученное решение удовлетворяет условию целочисленности, то оно является оптимальным и для исходной задачи (4.90) - - (4.93). Если ЗЛП (4.90) - (4.92) не имеет решений, то неразрешима и ис­ ходная задача. Если решение ЗЛП не удовлетворяет условиям целочисленности, перейти к п. 2.

2.Среди нецелых компонент оптимального решения ЗЛП выбрать компоненту с наибольшей дробной частью и по соответствующей строке симплексной таблицы с оптимальным решением ЗЛП построить ограниче­ ние (4.94).

3.Неравенство (4.94) преобразовать в равенство введением допол­ нительной неотрицательной переменной и ввести его дополнительно в