Учебное пособие 764

	Находим разрешающий элементx1								и меняемx2 « x4 .
Заполним новую таблицу.
				bi		x1			x4		x3
	L1			96		-12	-6	-8	-8	-6
				120						-6
	x2			12		1	1	-1	-1	0
				12						0
	x5			-8		-1	1	0	0	-1
				-8						-1
	x6			8		1	0	-1	-1	-1
				0						1
	Далее заменим x3 « x5
				bi		x1			x4		x5
	L1			144		-6			-8		-6
	x2			12		1			-1		0
	x3			8		1			0		-1
	x6			0		0			-1		1
	Так как	в первой			строке			все свободные переменны
отрицательны, то L1min = 144 при x1 = 0 , x2									= 12 , x3 = 8 .
	Математическая модель относительно								оси y	запишется в
виде				L2 = 10 y1 + 8 y2 + 6 y3 +10 y4 ;
	y1 + y4			³ 15; y1 + y3		³ 10;	y2 + y3 ³ 6; y2 + y4 ³ 11.
	Через базисные переменные

L2 = 0 - (-10 y1 - 8 y2 - 6 y3 -10 y4 ),

y5 = -15 - (-y1 - y4 ); y6 = -10 - (-y1 - y3 ); y7 = -6 - (-y2 - y3 ); y8 = -11 - (-y2 - y4 ).

Составим таблицу

9

			bi				y1			y2		y3			y4
	L2	0			-10		-10		-8	-8		-6			-10
		100										4			-10
	y5	-15			-1		-1		0	0		0			-1
		-5										1			-1
	y6	-10			-1		-1		0	0		-1			0
		10										1			0
	y7	-6			0		0		-1	-1		-1			0
		-6										-1			0
	y8	-11			0		0		-1	-1		0			-1
		-11										0			-1
	Делаем замену y1			« y6
			bi				y6			y2		y3			y4
	L2		100			-10	0	-8		-8		4		-10
			150									-6		-10
	y5		-5	5		-1	1	0		0		1		-1
												-1		-1
	y1		10			-1	-1	0		0		1		0
			10									1		0
	y7		-6	-6		0	0	-1		-1		-1		0
												-1		0
	y8		-11	-6		0	1	-1		-1		0		-1
												-1		-1

10

Еще раз заменяем y4 « y5

		bi		y6	y2		y3			y5
L2		150		0	-8	-2	-6	6	-10
		186		0						-10
y4		5		1	0	1	-1	-1	-1	-1
		11		1
y1		10		-1	0	-1	1	1	0	0
		4		-1
y7		-6		0	-1	1	-1	-1	0	0
		6		0
y8		-6		1	-1	0	-1	1	-1	-1
		0		1
Отсюда		имеем:		L = 186	при y1 =		4; y2	= 0;		y3 = 6;
y4 = 11.		Следовательно, минимум				пробега		транспорта в
горизонтальном и				вертикальном		направлениях				составляет

L = 144 +186 = 330 км.

3. РАСЧЕТ ОПТИМАЛЬНОГО ЧИСЛА РАБОТНИКОВ НА ПРЕДПРИЯТИИ

1 °. Характерной особенностью ряда предприятий является неравномерность поступления нагрузки по часам суток, дням

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

Обозначим через x j — число работников, работающих

по j - му графику,		bi - нагрузку в i - й		рабочий день,
выраженную	в	числе	требуемых	работников; a -
				ij

11

коэффициент, равный единице, если по j - му графику предусматривается работа в i - й день, и нулю, если в тот день предусматривается выходной. Задача может быть сформулирована так: требуется найти минимум целевой функции L = x1 + x2 + ... + xn при выполнении следующих ограничений

a11 x1 + a12 x2 + ... + a1n xn ³ b1 ;

a21 x1 + a22 x2 + ... + a2n xn ³ b2 ;

……………………………….

am1 x1 + am 2 x2 + ... + amn xn ³ bm .

	2°. Для		простоты		вычислений		рассмотрим			пример
четырехдневной			рабочей		недели		с	двумя	выходным,
исходные данные для которого приведены в таблице
	Число				Дни недели
	работников
			1		2		3	4
	x1		В		В
	x2						В	В
	x3		В					В
	x4				В		В
	x5		В				В
	x6				В			В
	bi		100		80		40	60

Запишем задачу линейного программирования следующим образом

12

				L = x1 + x2 + x3 + x4 + x5 + x6
	при следующих ограничениях
				x2 + x4 + x6 ³ 100; x2					+ x3 + x5		³ 80;
			x1 + x3 + x6			³ 40; x1 + x4			+x5 ³ 60;		x j	³ 0.
	Введем базисные переменные и перепишем ограничения в
виде, удобном для использования симплекс-метода
	y1 = -100 - (-x2 - x4					- x6 );	y2 = -80 - (-x2				- x3 - x5 );
		y5 = -40 - (-x1 - x3 - x6 ); y4 = -60 - (x1 - x4 - x5 );
				L = 0 - (-x1 - x2 - x3 - x4 - x5 - x6 ).
	Запишем решение в виде таблицы
		bi		x1		x2		x3			x4	x5	x6
		0		-1		-1		-1		-1		-1	-1
L		60		0		-1			-1		-1	0	-1
		-100		0		0		-1		-1		0	-1
y1		-40		1		0			-1		-1	0	-1
		-80		0		-1		-1		0		-1	0
y2		-80		0		-1			-1		0	-1	0
		-40		-1		0		-1		0		0	-1
y3		-40		-1		0			-1		0	0	-1
		-60		-1		0		0				-1	0
y4		60		1		0			0	-1		1	0

Выбираем разрешающий элемент, находим l = -1и

переводим базисную переменную y4 в разряд свободной

x4 .Перепишем таблицу заменяя y4 « x4 .

13

				bi			x1			x2		x3				y4		x5		x6
	L		60			0			-1		-1				-1		0		-1
			120					1	-1		-1				0		1		0
	y1		-40			1		1	-1		-1				-1		0		-1
			40						-1		-1				-1		1		-1
	y2		-80			0		1	-1		-1				0		-1		0
			-40						-1		-1				0		-1		0
	y3		-40			-1		1	0		-1				0		0		-1
			40						0						0		0		1
	x4		60			1		1	0		1				-1		1		0
			60						0		-1				-1		1		0
	Выберем разрешающий элемент и перепишем таблицу,
заменяя				y3 « x3
				bi				x1		x2		y3				y4		x5		x6
	L			100				1		-1		-1				0		1		0
				140						1
	y1			-40	0			1		-1		0				-1		1		-1
										1
	y2			-40	40		1	-1		-1		-1	1			0		-1		0
																0		-1		0
	x3			40	40			1		0		-1				0		0		1
										0
	x4			60	60			1		0		0				-1		1		0
										0
	Выберем разрешающий элемент и перепишем таблицу,
заменяя				y2 « x2

14

	bi		x1		y2	y3		y4		x5	x6
L	140		2		1	0		0		2	0
y1	0		2		1	1		-1		1	-1
x2	40		-1	- 1		- 1		0		-1	0
x3	40		1		0	-1		0		1	1
x4	60		1		0	0		- 1		1	0
Целевая		функция			Lmin =140 при			x2 = 40,		x3	= 40,
x4 = 60, x1 = x5 = x6 =0.

4. ЗАДАЧА НАХОЖДЕНИЯ КРАТЧАЙШЕГО ПУТИ

1°. Граф задается конечным множеством вершин или узлов ( a1 , a2 ,..., an ) и множеством дуг или ребер ( l1 , l2 ,...,lm ),

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

ориентированным графом. Если ребра графа не имеют ориентации, то граф называютнеориентированным. Каждая

дуга может быть задана упорядоченной парой вершин(ai a j ) ,

где ai - называется начальной, а a j — конечной вершиной дуги.

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

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

15

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

2°. Пусть требуется найти кратчайшие пути от одной вершины ко всем остальным вершинам сети.

Алгоритм Флойда. 1) Введем матрицу Cij , в которой

записаны длины всех дуг сети

ì0, если i=j

ï

С = íдлине дуги между вершинами ai и a j

ïî¥, если дуги между ai и a j нет.

Положим k = 1 .

2)Для всех i ¹ k и j ¹ k осуществить операцию

Cij := {Cij , Cik + Ckj }.

3)Если k = m, вычисления закончены, иначе перейти к п. 4.

4) k := k +1 и перейти к шагу 2.

Алгоритм применим и для отрицательных длин ребер.

3°. Алгоритм Дейкстры. Алгоритм позволяет найти

кратчайшие	пути	от	заданной			вершины	до
остальных. Обозначим: Сij - расстояние от узла ai до a j							;
li¢ — временная		пометка		для		вершиныai , li	—
постоянная пометка для вершины ai ;					m — число вершин
в сети.
Полагаем:
1. ls = 0, li	= ¥ для i = 1,..., m;			i ¹ s;	k = 1; p = s.

2. Для всех соседей вершины a p с временными пометками

16

изменить пометки по формуле

li¢ = min( li¢, l p + C pi ).

3. Для всех вершин, имеющих временные пометки, найти lr = min li¢.

4. Положить p = r, k := k +1. Если k = m , вычисления закончены, иначе перейти к шагу 2.

4.1. Пусть дана сеть (рис. 31.3). Найти кратчайшие пути между всеми узлами.

Рис. 3 Решение. Составим исходную матрицу

	1	2	3		4	5	6
1	0	1	¥		¥	¥	5
2	1	0	3	¥		6	2
3	¥	3	0	5		1	3
4	¥	¥	5	0		1	¥
5	¥	6	1	1		0	3
6	5	2	3	¥		3	0

При k =1 матрица не меняется, поэтому рассмотрим

случай, когда k = 2.
C13	= min( C13 ,C12	+ C23 ) = min( ¥,1 + 3) = 4;
C14	= min( C14 ,C12	+ C24 ) = min(¥,1 + ¥) = ¥;
C15	= min(C15 , C12	+ C25 ) = min( ¥,1 + 6) = 7;
C16	= min( C16 ,C12	+ C26 ) = min(5,1 + 2) = 3.
Найдем элементы матрицы во второй строке матрицы
C21	= min(C21 , C22	+ C21 ) = min(1,1) = 1;
C22	= 0;

17

C23 = min(C23 ,C22 + C23 ) = min(3,3) = 3;

C24	= min(C24 ,C22	+ C24 ) = min( ¥, ¥) = ¥;
C25	= min(C25 , C22	+ C25 ) = min( 6,6) = 6;
C26	= min(C26 ,C22	+ C26 ) = min( 2,2) = 2.
Для третьей строки найдем
C31	= min( C31 ,C32	+ C21 ) = min( ¥,3 +1) = 4;
C32	= min(C32 ,C32	+ C22 ) = min(3,3) = 3;
C33 = 0 ;
C34	= min(C34 ,C32	+ C24 ) = min(5,3 + ¥) = 5;
C35	= min(C35 ,C32	+ C25 ) = min(1,3 + 6) = 1;
C36	= min(C36 ,C32	+ C26 ) = min(3,3 + 2) = 3;
Для четвертой строки
C41	= min(C41 , C42	+ C21 ) = min( ¥, ¥ +1) = ¥;
C42	= min(C42 ,C42	+ C22 ) = ¥;
C43	= min(C43 ,C42	+ C23 ) = min(5, ¥ + 3) = 5;
C44	= 0;
C45	= min(C45 , C42	+ C25 ) = min(1, ¥ + 6) = 1;
C46	= min(C46 ,C42	+ C26 ) = min( ¥, ¥ + 2) = ¥.
Пятая строка примет вид
C51	= min( C51 , C52	+ C21 ) = min( ¥,6 +1) = 7;
C52	= min(C52 ,C52	+ C22 ) = min( 6,6) = 6;
C53	= min(C53 ,C52	+ C23 ) = min(1,6 + 3) = 1;
C54	= min(C54 ,C52	+ C24 ) = min(1,6 + ¥) = 1;
C55	= 0;
C56	= min(C56 ,C52	+ C26 ) = min(3,6 + 2) = 3.
Элементы шестой строки
C61	= min(C61 , C62	+ C21 ) = min(5,2 +1) = 3;
C62	= min(C62 , C62	+ C22 ) = min( 2,2) = 2;
C63	= min(C63 ,C62	+ C23 ) = min(3,2 + 3) = 3;

18