Моделирование конкурентоспособности товара на современном рынке (стр. 5 из 7)

на взаимно непересекающихся подмножествах

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

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

Примеры деревьев:

Начальной вершине 0 соответствует исходное допустимое множество

или исходная задача (1), а любой другой вершине – подмножество , полученное в результате ветвления, или подзадача :

, .

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

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

не производится, если выполнено одно из условий:

. Граница найдена точно: , т.е. получено решение подзадачи . Будем говорить, что в этом случае вместо оценки решения в вершине найдено полное решение , соответствующее этой вершине.

. Множество является пустым.

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

.

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

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

Вершины, удовлетворяющие одному из условий

– , назовем прозондированными. Непрозондированные вершины, из которых ветвление еще не произведено, будем называть активными, а совокупность всех таких вершин – активным множеством .

Процесс ветвления продолжается до тех пор, пока остается хотя бы одна активная вершина, т.е.

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

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

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

· Имеется алгоритм получения нижней границы целевой функции на любом допустимом множестве.

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

3.3.2 Особенности метода в поставленной задаче

Применим метод к нашей задаче:

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

, , от «вложенных в данный параметр средств» .Таблица11.

Вложенные средства(у. е.)		5			10			15			20			25				30		35				40		45			50
Коэффициент теплопроводности,Вт/(м*К)		0.028			0.028			0.028			0.027			0.0265				0.026		0.0258				0.0253		0.025			0.025
Вложенные средства(у. е.)		2			5			8			11			14				17		20				23		26			29
Объемное водопоглощение,%		0.02			0.02			0.019			0.018			0.016				0.015		0.014				0.011		0.01			0.01
Вложенные средства(у. е.)		3			5			7			9			11				13		15				17		19			21
Срок эксплуатации,Лет		>20(22)			24			25			25			25				26		27				28		29			29
Вложенные средства(у. е.)		4			5			6			7			8				9		10				11		12			13
Прочность (диапазон рабочих температур),Градус.		200			200			200			220			240				270		330				400		400			400
Вложенные средства(у. е.)			1			5			9			13			17		21				25		29				33			37
Стоимость продукции,Руб./кг			100			99			97			95			94		92				90		85				80			80
Вложенные средства(у. е.)			5			10			15			20			25		30				35		40				45			50
Стоимость доставки,Руб./кг			30			28			27			25			20		18				16		15				15			15
Вложенные средства(у. е.)	0			2			4			6			8			10			12			14			16			18
Экологическая безопасность	0			0			0			0			0			1			1			1			1			1
Вложенные средства(у. е.)	0			3			6			9			12			15			18			21			24			27
Горючесть(ГОСТ 12.1.044)	0			0			0			0			0			1			1			1			1			1

Вложение средств в нормативные параметры необходимо, только если значение характеристик на данный момент не соответствует нормам и ГОСТ.