Добавил:

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

Вуз:

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

Предмет:

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

Файл:

Зад лин прогр и мет их решения 16 12 08

.pdf

Скачиваний:

Добавлен:

29.03.2016

Размер:

7.61 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 > Следующая >>>

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 ]. ( p1: 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		−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		−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

4) Способы задания графов

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

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

в) матричный

в1) матрица инциденций графа M, N,T

a[M, N ]: a i(u),u =−1,

a j(u),u =1, остальные элементы столбца и равны нулю

в2) матрица смежностей графа M, N,T

a[M,M ]: a[i, j]=числовая

характеристика дуг из i в j (например, число дуг, идущих из i в j − Ni− ∩N+j )

г) Списковый г1) Список дуг состоит из записей,

состоящих из названия дуги, названия ее начала и названия ее конца

г2) Список вершин (вариант сжатого задания матрицы смежностей).

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

а вершины числами от 1 до m = M таким

образом, чтобы дуги, выходящие из i-ой вершины, предшествовали в этой нумерации дугам, выходящим из j-ой вершины при i<j.

Далее вводится целочисленный массив j[1: n] концов дуг, который размечается с

помощью целочисленного массива lst[0: m]

(lst[i] указывает место в массиве j[1: n],

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

5) Связность (M, N,T = M, N )

а) Путь в графе M, N - пара

последовательностей

					i
						e
				с		a				f	b 5
				с						f
	1				2				3	4		6
			h						d		g
											g
M =1: m, N =1: 2m−3
Tu =		(					)		для u 1: m−1
Tu =			u,u +1 ,						для u 1: m−1
Tu =		(	u−m							)	для u m : 2m−3
Tu =			u−m				+3,u−m+1 ,				для u m : 2m−3
(m=6)
	a			b			c
1	-1			1			0
2	1			0			-1
3	0			-1			1
4	0			0			0			a	2
										a
	1		2		3		4			1	c	4

1	0		1		0			0		b	3
2	0		0		1			0			3
2	0		0		1			0
3	1		0		0			0
4	0		0		0			0

(a,1,3)(b,4,5)(c,2,1)(d,2,4)(e,1,3)

(f ,4,3)(g,5,1)(h,1,4)(i,3,1)

Вершины: 1, 2, 3, 4, 5, 6 Дуги: a, e, h, c, d, i, f, b, g,

1, 2, 3, 4, 5, 6, 7, 8, 9

j[1: 9]=3,3,4,1,4,1,3,5,1

lst[0: 6]=0,3,5,6,8,9,9

(Заметим, что т. к. N6− = , то lst[6]=lst[5])

1 a	2	e	5
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

199

7.14.3. Решение однородных систем с матрицей инциденций

Пусть M ', N ' - цикл с заданной на нем

ориентацией (направлением обхода). Дуги цикла разбиваются на два непересекающихся подмножества

N' = N '+ N '−

N'+ - положительные дуги цикла

(проходимые по ориентации)

N '− - отрицательные дуги цикла (проходимые против ориентации)

	1,	u N '	+
			+

Вектор		u N '−
Вектор	w[N ]: w[u]= −1,	u N '−

		u N \ N '
	0,	u N \ N '

называется	циклическим вектором цикла

M ', N '

Пусть M ', N ' связывающее дерево в графе M, N . Цикл, в котором только одна

дуга не принадлежит N ' называется основным циклом, а его циклический вектор – основным циклическим вектором.

Теорема (Кирхгоф)

Решение z[N ] системы (≈) представимо в

виде	линейной	комбинации основных
циклических векторов
Следствие
Любое	решение		системы	(≈),
неотрицательное		вне	дуг дерева	N ',

представимо в виде конической комбинации основных циклических векторов (коническая комбинация – линейная комбинация с неотрицательными коэффициентами)

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

		3
	6	3	4
	6
	5		6
0	5		6	4
0		2		4
		2

1	2	7

положительные дуги N '+

цикл

M ', N '

−

отрицательные дуги N '−

w[N ]=(−1,0,0,1,0,1,−1,0)

циклический вектор

	3
	3	4
	3	связывающее
		связывающее
0	2	дерево
	2
	1

3основной цикл

		2	(дуга 6 не
0		2	принадлежит
0	2		принадлежит
1	2		дереву)
			дереву)
		1

w[N ]=(−1,−1,−1,0,0,1,0)

основной циклический вектор

	4
1	2
	3

С помощью любого из этих четырех основных циклов можно улучшить решение ТЗ.

<<< < Предыдущая 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 > Следующая >>>

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

#
28.03.2016327.17 Кб77Думин И.В. Другая Русь.doc
#
29.03.2016114.03 Кб212Е.А. Шевченко УМКРУНТ фольклор русский.docx
#
28.03.2016159.74 Кб82Евгений Онегин статья Маймина.doc
#
28.03.2016748.03 Кб16Еколе русс.doc
#
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