Добавил:

Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Сыктывкарский Государственный Университет им. Питирима Сорокина

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

Задачи ЛП и методы их решения

.pdf

Скачиваний:

155

Добавлен:

29.03.2016

Размер:

7.64 Mб

Скачать

☆

<<< < Предыдущая 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1920 / 2820 21 22 23 24 25 26 27 28 > Следующая >>>

													189
														11

															61
												Отход –0			61
												Отход –0		65
												f * = 31
														63
	4		0		0		0			2		0	10	63
	4		0		0		0			2		0	10
	0		5		0			0		0		0	60
2	0	+12	5	+10	0	+5		0	+1	0	+1	0	60		Отход –11
2		+12		+10		+5			+1		+1		=		f * = 31
	0		0		6			0		2		3	65		f * = 31


	0		0		1		10			2		0	62
														10
														10
												Отход –00
												f * = 30		60
														62
														62

														62

Объединенное решение при наличие ограниченного числа бракованных съемов ( K = 40)

Сорок безотходных
бракованных съемов
					0		0
2		0			0		0
	0		1			2		1
	0		1			2		1
	0		0			0		0	Брак
30	0	+	0	+10		0	+	0	30 40 =120 (6L)
	0		0			0		0
	0		0			1		0

(L1)		(L2 )			(L1)		(L2 )

	11		Вектор требований	1
			увеличивается на
		61		1
	65			0
30 (или 31) обычных	65			0
30 (или 31) обычных
раскладок	63			1

							0			2		0	10
	4		0		0
	0		5		0			0		0		0	60
2		+12		+10		+5			+1		+1			Отход –11
													=	f * = 31
	0		0		6			0		2		3	65


	0		0		1		10			2		0	62

10	Вектор требований	0
	уменьшается на
60		0
62		3

62		0

190

Вывод: Полученное решение (с учетом брака шириной 6L ) "не хуже" оптимального решения без брака (т.к. 65+ 6 = 71, т.е. в отходы ушел только брак).

Раскрой при наличие случайного брака на тамбуре

Исходные данные: L	– ширина тамбура
\|M\|	- число форматов
\|N\|	- число раскладок
l[M] – вектор ширин форматов

b0[M] – вектор требований на форматы

Исходная ситуация: Решена целочисленная задача форматного раскроя при заданном векторе требований b[M]. В результате получен набор оптимальных

	раскладок A[M,N0] и целочисленный вектор интенсивностей их
	использования x[N0]. При разрезании очередного съёма на ПРС
	несколько рулонов оказываются бракованными. Необходимо
	поставить новую задачу целочисленного форматного раскроя,
	изменив вектор требований с учетом уже нарезанных рулонов и
	полученного брака.
Пусть	bˆ[M ] - вектор количества нарезанных рулонов (по форматам), а
				b[M ]- вектор
	Тогда bɶ[M ] = bˆ[M ]−		[M ] - выполненная часть вектора
брака.		b		требований, а
b [M ] = b [M ]− bɶ[M ] - текущий остаток вектора требований
1	0

(новый вектор требований).

Формулируем новую целочисленную задачу форматного раскроя при тех же исходных данных и новом векторе требований b1[M ]. Решаем её, и продолжаем разрезание по новому графику (вообще говоря, новый оптимальный набор раскладок и новый вектор

интенсивностей их использования).
Алгоритм решения:
(0)	k:=0			A[M, N0 ] x[N0 ] = bk [M ]
	f (x) = 1[N] x[N] → min		МСМ+ПЕРЕБОР	A[M, N0 ] x[N0 ] = bk [M ]
(1)				x[N \ N0 ] = 0[N \ N0 ]
(1)		A[M, N] x[N] = bk [M ]
		x[N] ≥ 0, целочисл.		N0 = { j1, j2 ,..., js}
		x[N] ≥ 0, целочисл.

(2) Отрезаем очередной съём A[M, jp ]. ( p 1: s).
Если		[M ] = 0[M ] (на съёме нет брака), то bɶ[M ] = A[M, j		], и
	b		p

∑ A[M, jk ] X[ jk ]+ A[M, jp ] (X[ jp ]−1) = bk [M ]− A[M, jp ], иначе на шаг (4)

k=1

k≠ jp

(3)В этом случае график резания не меняем.

bk [M ]:= bk [M ]− A[M, jp ], X[N0 ]:= X[N0 ]− (0,...,0,1,0,...,0).

j p

Переходим на шаг (2).

(4) Если b[M ] ≠ 0[M ], то bk+1[M ]:= bk [M ]− A[M, jp ]+ b[M ], j0 := jp (Запоминаем раскладку, по которой вырезали последний съём) k := k +1. Переходим к шагу (1)

Выше описан алгоритм решения при наличии заказа в посъёмном режиме. Можно предложить модификацию этого алгоритма, заключающегося в другой последовательности решения целочисленных задач форматного раскроя. Сначала нарезаем вектор b0[M], а вектор брака b[M ] только учитываем суммированием

191

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

	для						вектора					требований								b[M ]				и			нарезаем							оставшиеся съёмы. Две эти
	модификации необходимо сравнить .
Рассмотрим пример: L=13, l=(6, 5, 2), l0=(10, 20, 40)																																		240		=18L + 6
Рассмотрим пример: L=13, l=(6, 5, 2), l0=(10, 20, 40)																																	13			=18L + 6
																																	13					19L + 7ост.
	2				1			1		1	1				1	1		0	0	0			0	0		0		0		0		...			0
A =	0				1			1		0	0				0	0		2	2	1			1	1		1		1		0		...			0

	0				1			0		3	2				1	0		1	0	4			3	2		1		0		6		...			1

	(1)				(0)			(2)		(1)	(3)			(5)		(7)		(1)	(3)	(0)			(2)	(4)			(6)	(8)			(1)				(11)

1 0 0						1 0					0					1 0 0					1		0 0							1		0 0					1 0 0
1 0 0						1 0					0					1 0 0					1		0 0							1		0 0					1 0 0
1 2 1						0 1					0					0 1 −3					0		1 −1							0		1 −3					0 1 −1

1 1 4						0 0					1					1 1 4					0		0 1							0		0 7					−1 −1 2


1	0		0					1			0					0
																								3		3	1
0	1		0				−3/7				4/7					−1/7						v =			,		,
0	1		0				−3/7				4/7					−1/7						v =			,		,
0	0			1			−1/7				−1/7					2/7								7		7	7
0	0			1			−1/7				−1/7					2/7


					1						0					0 10							10
x[N0 ]			=		−3/7 4/7											−1/7			20			= 40/7

					−1/7 −1/7											2/ 7 40							50/ 7

									0				0				0			0									0				0						0
			1						0				0				0			0				1					0				0						0
10 1 +1 2 + 7												1			+ 6/7 + 1/7								=10 1				+ 7 1 +1 2 +1											1

		1						1				4				3/7			4/7					1				4				1						1

																								(0)					(0)			(1)						(6)

Получена последовательность из 4-х оптимальных раскладок (на 19 съёмов) с интенсивностями их использования.

1.	Пусть					теперь									бракованным										является первый				формат в	1ом отрезанном съёме
						bɶ
			b			bɶ						b														1		0	0 10		10
			0																							1		0	0 10		10
		10				1					1								10					x[N0 ]		=	−3/7	4 /7 −1/ 7 19			= 1	,
b =			20		−				+				0				=					,		x[N0 ]		=	−3/7	4 /7 −1/ 7 19			= 1	,
b =			20		−	1			+				0				=		19
1																										−1/7		−1/7 2 /7 39			7
		40				1					0								39

								0										0
			1					0										0
	10 1				+ 7		1				+1					2

			1				4									1


2.	Теперь брак второго формата в 11м съёме (12-м от начала).
						bɶ
			b			bɶ					b															1		0	0 0			0
			1																							1		0	0 0			0
		10				10								0						0				x[N0 ]		=	−3/7	4/ 7 −1/7		9	= 11/7
b =					−						+				1				=		9		,	x[N0 ]		=	−3/7	4/ 7 −1/7		9	= 11/7		,
b =			19		−	11					+				1				=		9
2																										−1/7		−1/7	2 /7 25		41/7
		39				14								0						25

		0				0										0							0		0		0	0
	1 2			+ 5 1						+			8/7 +									6/7		= 6	1	+1	2 +1	1

		1				4							4/7								24/7				4		1	0

192

3. В 7-м съёме (19 от начала) брак 3го формата (одного рулона)

	0		0		0
b =		9	−	8	+ 0		- это способ раскроя с остатком 6.
3
	25		25		1


Всего вырезано 20 съёмов. (остаток 7).
	1		0		0			0	11	10	1
11	1	+ 7	1	+1	2	+1		1	= 21	= 20	+ 1

	1		4		1			1	41	40	1

								(1)	(6)

Модификация даёт такой же результат.

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

193

7.14. Сетевая транспортная задача и связанные с ней экстремальные задачи на графах (сетях)

Транспортные задачи (ТЗ) следует рассматривать как задачи линейного программирования со специальными матрицами ограничений (это относится и к классической матричной транспортной задаче). Переходим к рассмотрению транспортных задач на сети (СТЗ).

7.14.1. Основные сведения из теории графов


1) Граф –	тройка M, N,T ,				где M, N -
конечные	множества		( M	-	множество
вершин графа, N - множество дуг графа), а
T : N → M ×M			-		отражение
сопоставляющее		каждой		дуге u N
упорядоченную		пару	вершин		(i(u), j(u)).

Первая называется началом дуги u , а вторая – концом дуги u . (если дуга неориентированная, то для обеих вершин вместе используется термин «граничные вершины»)

2) Части графа M, N,T

а)	M, N ',T (N ' N)		- частичный	граф
графа M, N,T (граф			получающийся из
исходного удалением некоторых дуг)
б)	M ', N (M '),T	-	подграф	графа

M, N,T

(M M, N (M ')={u N i(u), j(u) M '})

(получается удалением из исходного графа некоторого количества вершин и всех дуг, для которых удаленные вершины являются граничными)

в) частичный подграф графа M, N,T - это

частичный граф некоторого его подграфа

3) Инцидентность
N	−		-	Множество		дуг, выходящих	из
	i
вершины i
N	+		- Множество дуг, входящих в вершину
	i
i
N	i	= N+ N−			-	множество	дуг,
	i		i	i
инцидентных вершине i
(i			является граничной вершиной для всех
таких дуг)

M ={1,2,3,4}, N ={a,b,c}.

Ta =(1,2), Tb =(3,1), Tc =(2,3)=(3,2) a, b – ориентированные дуги

с – неориентированная дуга 4 – изолированная вершина

1 c 4

a	2
a	N ' =	{	}
		{	}
			a,b

1	4

a	2	M ' = 1,2,3
a		M ' = 1,2,3
		{ }
1	c	N (M ')={a,b,c}
		N (M ')={a,b,c}

			{ }
a	2	M ' =		1,2,3
	2
		N ' N (M ')
1		N ' N (M ')
1			{	}
b	3	N ' =		a,b
b

Ni+ Ni−

u i	или	i u

i и u инцидентны

(incident – свойственный, присущий)

																194										i
4) Способы задания графов																										e
4) Способы задания графов																								с		a								f		b
																			1					с	2				3					f	4	b		5	6
а) графический (изображаются вершины и																							h							d						g
все инцидентные им дуги)																																				g
все инцидентные им дуги)
б) алгоритмический (задаются правила																	M =1: m,									N =1: 2m−3
формирования дуг и граничных вершин																	Tu =			(		u,u +1 , для u 1: m−1
данной дуги)																				(					)
данной дуги)																				(															)
																	Tu =					u−m+					3,u−m+1 ,									для u			m : 2m−3
																	(m=6)
в) матричный
в1) матрица инциденций графа							M, N,T
	a[M, N ]: a i(u),u =−1,																		a					b		c
	a[M, N ]: a i(u),u =−1,																	1	-1					1		0
	a j(u),u				=1, остальные элементы													2	1					0		-1
	a j(u),u				=1, остальные элементы													3	0					-1		1
столбца и равны нулю																		3	0					-1		1
столбца и равны нулю							M, N,T											4	0					0		0									a			2
в2) матрица смежностей графа																		4	0					0		0												2


		a[M,M ]: a[i, j]=числовая																	1			2			3		4						1					c	4
		a[M,M ]: a[i, j]=числовая																	1			2			3		4											c	4
	характеристика дуг из i в j (например,																	1	0			1			0		0								b		3
	характеристика дуг из i в j (например,																	2	0			0			1		0										3
	число дуг, идущих из i в j −						N		−	∩N		+		)


									i			j						3	1			0			0		0
																		3	1			0			0		0
																		4	0			0			0		0
г) Списковый
г1) Список дуг состоит из записей,
	состоящих из названия дуги, названия
	ее начала и названия ее конца																(				)(				)(						)(					)(
																	(				)(				)(						)(		d,2,4			)(		)
г2) Список вершин (вариант сжатого																		a,1,3						b,4,5				c,2,1					d,2,4				e,1,3
г2) Список вершин (вариант сжатого
	задания матрицы смежностей).																(	f ,4,3						g,5,1					h,1,4			)(		i,3,1
																		f ,4,3						g,5,1					h,1,4					i,3,1
																						)(			)(										)

Дуги нумеруются числами от 1 до n =													N			,

а вершины числами от 1 до m =								M			таким						Вершины: 1, 2, 3, 4, 5, 6
образом, чтобы дуги, выходящие											из	i-ой					Вершины: 1, 2, 3, 4, 5, 6
образом, чтобы дуги, выходящие											из	i-ой					Дуги: a, e, h, c, d, i, f, b, g,
вершины,					предшествовали			в			этой											1, 2, 3, 4, 5, 6, 7, 8, 9
нумерации дугам,						выходящим			из			j-ой										1, 2, 3, 4, 5, 6, 7, 8, 9
нумерации дугам,						выходящим			из			j-ой					j 1: 9				]	=3,3,4,1,4,1,3,5,1
вершины при i<j.																		[			]
вершины при i<j.
Далее				вводится		целочисленный					массив						lst[0: 6]=0,3,5,6,8,9,9
[			]	концов дуг, который размечается с
j 1: n				концов дуг, который размечается с													(Заметим, что т. к.														N		− = ,
помощью целочисленного массива lst[0: m]																																	6
помощью целочисленного массива lst[0: m]																	то lst[6]=lst[5])
[	i	]		указывает место в массиве						[					]	,
(lst	i			указывает место в массиве							j 1: n					,

где заканчивается информация о Ni− )

5) Связность (	M, N,T = M, N )			1 a		e
а) Путь в	графе	M, N	- пара	1 a	2	e	5
а) Путь в	графе	M, N	- пара	b		d	1,2,3,4,2,5
				b		d		путь
последовательностей								путь
последовательностей				3		4	a,b,c,d,e
				3	c	4

195

i1,i2 ,...,ik+1 M

u1,u2,...,uk N, так что

s 1: k, is =i(us ), is+1 = j(us )

(i1 - начало пути, ik+1 - конец пути, k - звенность пути)

Если i1 =ik+1 - путь замкнутый.

Путь простой, если все вершины в нем различны.

Простой замкнутый путь – контур Частичный подграф M ', N ' называется контуром если:

1.M ' = N '

2.Ni'− = Ni'+ =1 (в каждую вершину

одна дуга входит и одна выходит)

3.Никакой собственный подграф этими двумя свойствами не обладает

б) Путь в графе для которого

s 1: k, (is =i(us ), is+1 = j(us )) (is = j(us ), is+1 =i(us ))

называется цепью (т. е. дуги в цепи ориентированы

произвольным образом)

Цепь без самопересечений (все вершины различны) – простая цепь

Простая замкнутая цепь – цикл

	a		e		1,2,5	простой
1		2		5
1		2		5
					a,e	путь
		2			2,3,4,2
	b	d				контур
	3		4		b,c,d
	3	c	4

1	a	2	d	4	1,2,3,1,2,4
1		2		4				цепь
								цепь
	c	b				a,b,c,a,d
	3
1	a	2	d	4	1,2,4
1		2		4			простая цепь
							простая цепь
1 a					a,d
1 a		2		1,2,3,1
				1,2,3,1
	c	b				цикл
	3			a,b,c
	3

в) Граф M, N называется связным, если

любые его две вершины можно соединить цепью.

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

г) В связном графе M, N можно выделить

связный частичный граф M, N '

(связывающее дерево):

N ' = M −1

и перенумеровать вершины (m(M )) и дуги

(n(N ')) таким образом, что

n(u)= max{m(i(u)),m(j(u))}

При этом различным вершинам (дугам) будут соответствовать различные номера.

связные

графы

				несвязный
				граф
a	e		f
b		d	g	h связный граф
b		d

	c

196

Назовем такую нумерацию правильной.

Ранг матрицы инциденций связного графа равен |M|-1.

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

Ранг матрицы инциденций произвольного графа M, N равен |M|-p, где p – число

компонент связности.

Деревья

Деревом называется связный граф, в котором число дуг на единицу меньше числа вершин (т. е. N = M −1)

Эквивалентны следующие определения дерева:

а) связный граф без циклов

б) граф без циклов, так что N = M −1

в) связный граф, так что N = M −1

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

д) связный граф, в котором удаление дуги нарушает связность е) граф в котором любые две вершины

соединены единственной цепью.

2 4 6

2 4 6 связывающее дерево

Матрица инциденций исходного связного графа и его связывающего дерева

	1		2	3	4	5	6	с h
0
0	-1
1	1		-1	1
2			1					-1
3				-1	-1	-1	-1
4					1			1
5						1		1
6							1	-1
	0	1	1			2		5

4 5 3

M		1	=	{ }		M		2	=		{ }		M3 ={5}
M			=		0,1	M			=			2,3,4
N	1		{ }			N	2		=	{		}	N	3	=
N			=		1	N			=			3,4,5	N		=
			1		3	4			5			rangA[M,N]=
0			-1		0	0 0					=M1 −1+M2 −1+M3 −1=
1			1		0	0			0
1			1		0	0			0			=2+3+1−3=3
2			0		-1 -1				0			=2+3+1−3=3
3			0		1	0			0
4			0		0	1			0
5			0		0	0			0

- цепь (дерево)

нарушение связности

порождение

цикла

197

корень

иерархическое дерево

бинарное дерево

7.14.2. Постановка сетевой

C[1,1]

∑

C i, j

x i, j

→m

транспортной задачи

[

]

[

]

i K,j L

x i, j

=αi

,i K

а) Матричная транспортная задача (ТЗ)

∑

[

]

[ ]

К – множество пунктов производства

j L

( i K,

α[i]>0 - объем производства)

∑x[i, j]=β[j], j L

i K

L – множество пунктов потребления

≥0 K,L

x K,L

[

]

[

]

( j L,

β[j]>0

- объем потребления)

C[m,n]

C[i, j] - матрица цен перевозок

Рассмотрим граф

M, N :

C[N ] x[N ]→ min

1. M = K L, (K ∩L = )

−

= )

(*)

∑u Ni+ x[u]=b[i], i L. (Ni

N = K×L, ( u N i(u) K, j(u) L) (**) −∑u Ni− x[u]=b[i], i K. (Ni+ = )

(такой граф называется двудольным)

x[N ]≥0[N ]

Теперь вместо матриц C и X можно

рассмотреть векторы

C[N ]

и X [N] и для

удобства, считать, что

Условия (*) и (**) теперь можно переписать

в виде

[

]

>0,

b[i]

β i

(+)

∑u Ni+ x[u]−∑u Ni− x[u]=b[i], i M

−α[i]<0, i K.

Условие (+) можно трактовать, как баланс

C[N ] x[N ]→ min

потока груза: для каждой вершины разность

втекающего и вытекающего потоков равна

(*)

∑u Ni+ x[u]=b[i],

i L. (Ni− = )

потреблению. Теперь нам надо искать такой

(**) −∑u Ni− x[u]=b[i],

i K. (Ni+ = )

сбалансированный для всех вершин поток с

максимальной стоимостью.

x[N ]≥0[N ]

Сетевая транспортная задача (СТЗ)

В такой постановке устранены особенности

конкретного графа и ТЗ может быть

Задан

граф

M, N,T ,

представляющий

собой транспортную сеть, узлами которой

поставлена для

произвольного

связного

ориентированного графа

M, N,T .

являются вершины M , в которых задано

Рассмотрим основной пример.

потребление.

Пусть

задана

транспортная

сеть

>0−потребитель

исходными данными (числа у вершины –

b[i]=

0−производитель

объемы потребления, у каждой дуги – цены

0−промежуточный пункт

перевозок).

x[N ]≥0[N ]

198

Магистралями сети являются дуги N . Перепишем ограничения (+), используя структуру матрицы инциденций

	1,	u N	+
	1,	u N	i
			i
			−
			−
a[i,u]= −1,		u Ni

	0,	else
	0,	else

или

a[i,u]=δ(u Ni+)−δ(u Ni−)

(δ- символ Кронекера).

Тогда

a[i,N ] x[N ]=b[i], i M

или

a[M, N ] x[N ]=b[M ] (++).

Окончательно СТЗ запишется в виде

[	]	[	N	]	→ min

C	N	x

(~) a[M, N ] x[N ]=b[M ]

Это ЗЛП в стандартной форме с матрицей инциденций в левой части системы ограничений.

Запишем основное соотношение симплексметода при переходе к новому базисному решению

xθ [N ]= x0 [N ]+θ z[N ]

где z[N ] - задает направление улучшения

решения x0 [N ].

Это направление допустимо, если

z[N0 ]≥0[N0 ], N0 ={u x0 [u]=0}

a[M, N ] z[N ]=0[N ] (≈)

Ниже мы получим представление решений (≈) и неотрицательных решений для

случая, когда a[M, N ] - матрица инциденций.

		-1	3		4
			3
	1	1	1	1		2
	1	1
	2		4			1
-3	2		4			1	0
-3		0		2			0
		0	1	2		1
	1	1	1
					1

			2
			2			2
		-7		0	1	2
		-7	2	0	1
			2

Выделим в нем связывающее дерево с правильной нумерацией

		0		7
		1		7
	6		2	7	4
6	6		2		4	4
6		1		2		4
		1	3	2
			3

5 8

Матрицы инциденций связывающего дерева, при этом запишется в виде

	1	2	3	4	5	6	7	8
0	-1
1	1	-1	-1		1	1
2		1		-1			-1
3			1					-1
4				1
5					-1
6						-1
7							1
8								1

Условие баланса потока, например, для вершины 1 выглядит следующим образом (учитываются только потоки по дереву)

x[1]+ x[5]+ x[6]−(x[2]+ x[3])=0

<<< < Предыдущая 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1920 / 2820 21 22 23 24 25 26 27 28 > Следующая >>>

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

#
26.09.2019454.66 Кб35Загайнов Рудольф Максимович Психологическое мас...doc
#
29.03.20167.61 Mб29Зад лин прогр и мет их решения 16 12 08.pdf
#
29.03.2016470.27 Кб20Задания для самостоятельной работы.pdf
#
28.03.201646.84 Кб26Задания о выпуске продукции при ограниченных ресурсах.docx
#
28.03.2016152.06 Кб16Задачи к экзамену.doc
#
29.03.20167.64 Mб155Задачи ЛП и методы их решения .pdf
#
23.11.2018455.17 Кб9ЗАДАЧИ СОКОЛОВ!!!.doc
#
28.03.201697.79 Кб6задачи.doc
#
28.03.2016692.22 Кб17Задачник по статистике (соц.-эконом. стат-ка).doc
#
29.03.201620.99 Mб28Закон Божий. Руководство для семьи и школы.pdf
#
17.09.2019117.25 Кб1Законодательная база рекламной деятельности в Р...doc