Добавил:

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

Вуз:

Башкирский Государственный Аграрный Университет

Предмет:

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

Файл:

книги из ГПНТБ / Большие системы и управление

..pdf

Скачиваний:

Добавлен:

29.10.2023

Размер:

11.27 Mб

Скачать

☆

<<< < Предыдущая 1 2 3 4 5 6 7 8 910 / 2110 11 12 13 14 15 16 17 18 19 20 21 > Следующая >>>

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

Усложненный алгоритм в применении к матрице

*)7 . .	,■	а т
а п , -	•	■ а пп
состоит из следующих шагов*		шаг . На этом шаге про
П о д г о т о в и т е л ь н ы й		шаг . На этом шаге про
изводим следующие операции:

1.Перебираем по очереди все строки матрицы ||д|| , находя независимые элементы* Бели такого элемента в исследуемой стро ке нет» то строка переставляется на последнее место*

2.Матрица перестраивается путем перестановки строк и столб цов таким образом» чтобы найденные независимые элементы рас пространились по главной диагонали, начиная с левого верхнего угла.

Обозначим перестроенную матрицу

а п

а\,

t	*
T	см

Cf22

*- a m

_ *

а1п

«\ п

а'пп

П е р в ы й шаг* Первый шаг усложненного алгоритма не отличается от рассмотренного ранее» но применяется он к матри це IА*|| . Таким образом» как и прежде, начиная с левого верх него угла матрицы, производим подсчет и сравнение сумм вида

*	+	*	и	*	*
а „				а , г + °г; *

*3 3

*п п

а 1 3 +	а	3 1 1
а 1 п ^ ~	0	П 1

добиваясь того,,	чтобы путем перестановки строк и столбцов, по-
лучить матрицу	* *		* *	"	•	*	w * *
	а „	° Т2					а ш
	/у**	п	* *		•	•	п * *
	и г 1						а г п
	а * *	а	* *	•	•	•	а пп
			п г

				91
такую, что для нее выполняются неравенства
	** .		* *		** .
	а 11	+	а гг		0/2	+ 1Ч, .
	*		*	>	а13 + а 31 ’
	а Т1 + а зз				а13 + а 31 ’
	**		**	>	**	X*
	° П + а пп				С,п + *пт
	Отличие от действий,		произведенных ранее,				состоит в том,
что	при возникновении	сомнительных случаев, т .е ,						если
	а	**	+ а чч			**
	а	и	+ а чч			+ а 41 9
делаем перестановку строк и столбцов матрицы \|\|Д**								таким обра-
зом,	чтобы число
	**	-	max		* *
	a s	-	max		п ’	1ЧЧ‘	’	Я* }
					п ’	1ЧЧ‘	’	Я* }

оказалось в левом верхнем углу четырехугольника, образованного

числами	а**,				чтобы число	as поменялось ме
стами с	числом	сгу ) .
Первый шаг заканчивается, как и прежде, тем, что в левом
верхнем	углу перестроенной матрицы оказывается число,						представ
ляющее компоненту искомого вектора.
В т о р о й		ш а г .		Для перехода ко второму шагу, как
и ранее,	вычеркиваем первую строку и первый столбец матрицы,
полученной в результате первого шага, и к этой матрице							(/?- 1)-го
порядка применяем алгоритм,					в точности повторяющий все		наши дей
ствия, проделанные		на	первом шаге, В результате / 7 - 1 шагов оп
ределяем	п чисел, представляющих собой квазиоптимальное или
оптимальное решение (компоненты вектора 6 )•						Используя найден
ные п чисел, перестроим				исходную матрицу \|\|д \|\| таким образом, что
бы эти числа расположились					по главной диагонали. Назовем по
лученную матрицу \|\| д \|\|			. Очень полезно бывает			применить	к этой
матрице	первый и все		последующие шаги алгоритма. Таким путем

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

Проиллюстрируем применение усложненного алгоритма на при мерах.

Пример 2 , Рассмотрим матрицу

		92
13	8	15	6	9
12	II	9	6	8
8	4	7	2	3 .
II	7	6	5	7
9	10	10	4	14

и т е л ь н ы й шаг . Находим независямне элемента. Таких элементов здесь два: число 15, стоящее на пересечении первой строки и третьего столбца, и число 14, стоя щее напересечении последней строки и последнего столбца* Пе рестроим матрицу таким образом, чтобы 15 и 14 оказались распо ложенными в верхней половине главной диагонали* Для этого по меняем местами первый и третий столбцы, а также второй и пятый. Затем поменяем местами вторую и пятую строчки* Преобразованная матрица имеет вид:

15	9	13	6	8
10	14	9	4	10
7	3	8	2	4
6	7	II	5	7
9	8	12	6	II

Подготовительный шаг закончен* Переходим к следующему шагу. П е р в ы й шаг . В соответствии с алгоритмом проверяем

выполнение неравенств

15	+ 14	> 10 + 9,
1 5 +8		> 7 + 1 3 ,
15	+ 5	> 6 + 6 ,
15	+ II	=> 9 + 8 .
Первый шаг закончен. Считаем, что число 15,			стоящее	в
третьем столбце первой строки исходной матрицы,			является ком
понентой искомого решения.
Переходим ко второму шагу, вычеркивая перше строку				и

столбец преобразованной на первом шаге матрицы и рассматривая матрицу

14	9	4	10
3	8	2	4
7	II	5	7
8	12	е	II

В т о р о й шаг . Действуя в точности, как и на первом шаге, проверяем неравенства

			93
14 +		8	>	3 + 9,
14	+ 5		>	7 + 4 ,
14	+	II ^		8 + 10.

Число 14, стоящее в пятом столбце пятой строки исходной матрицы, является второй компонентой искомого решения. Второй

шаг закончен.
Т р е т и й	ш а г . Рассматриваем матрицу
		8	2	4
	I I		5	7
	12		6	I I
Действуя, как прежде, получаем
	8 +	5 -	I I	+	2,
	8 +	I I	>	12	+ 4.

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

Ч е т в е р т ы й ш а г . Рассматриваем матрицу

	II б	7
	Н6	I I
Для нее	имеем
	5 + П 4 >		6	+ 7.
Таким образом, число 5, стоящее				в четвертом столбце четвер
той строки,	и число I I , стоящее	во		втором столбце второй стро

ка исходной матрицы, являются недостающими компонентами иско

мого решения.
Перестроим исходную матрицу		таким образом, чтобы найденное
решение располагалось по главной диагонали:
15	9	13	6	8
10	14	9	4	10
7	3	8	2	4
6	7	I I	5	7
9	8	12	6	II

Полученное решение может быть записано:

S = 15 + 14 ♦ 8 + 5 + I I = 53.

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

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

неравенств алгоритма для этой матрицы дает:

15	+	14	>	10	+	9,	1 4	+ 5 > 7 + 4,
15	+	8	>	7	+	13,	14	+	II > 8 + 10,
15 + 5			>	6 + 6 ,			8 + 5 = I I + 2
15 + II			>	9 + 8 ,			8 +		I I > 1 2 + 4
14 + 8			>	3 + 9 ,			5 +		I I =» 6 + 7

Единственное равенство

8 + 5 = I I + 2

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

Перестроим матрицу, содержащую на главной диагонали найден

ное решение, поменяв местами третью и четвертую строчки. Полу
чим матрицу
15	9	13	6	8
10	14	9	4	10	•
6	7	I I	5	7	•
7	3	8	2	4
9	8	12	6	II

неравенства:
15	+	14	>	10	+ 9,	14	+	2		>	3 + 4,
15	+	I I	>	6	+ 13,	14	+ I I			>	8 + 10
15	+	2	>	7 + 6,		I I +		2	= 8 + 5,
15	+	II	>	9	+ 8,	I I	+	I I		:> 12 + 7,
14 +		I I >		7 + 9,		2 + I I > 6 + 4.

Эти неравенства удовлетворяют условиям алгоритма. Поэтому

S = 15 + 14 + I I 4- 2 + I I = 53.

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

ПРИЛОЖЕНИЕ

Совершенно очевидно, что предлагаемый алгоритм позволяет отыскивать и минимальные решения ( С = m I п) ♦ При этом все опе рации имеют противоположный смысл:

-требуем выполнения неравенств противоположного смысла;

-независимые элементы должны быть минимальными (а не мак симальными) в своих строке и столбце.

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

Пример 3 . Найдем оптимальный (минимальный) план для мат рицы:

13	8	15	6	9
12	II	9	6	8
8	4	7	2	3
II	7	6	5	7
9	10	10	4	14

П о д г о т о в и т • еелль ьнныыйй ш а гг. Найдем независи мые элементы. Таким элементом является число 2f стоящее в чет вертом столбце третьей строки. Преобразуем матрицу таким обра зом, чтобы число 2 оказалось в левом верхнем углу. Для этого

меняем местами первую и третью строки,				а затем первый и чет
вертый столбцы. Преобразованная		матрица имеет вид:
2	4	7	8	3
6	II	9	12	8
6	8	15	13	9
5	7	6	II	7
4	10	10	9	14

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

неравенств (обратного смысла)

2 + I I > 6 + 4.

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

6 +	I I	9	12	8
2	4	7	8	3
6	8	15	13	9
5	7	6	II	7
4	10	10	9	14

Снова составляем неравенства

6 + 4 < 2 + 1 1 ,

но

6 + 15 > 6 + 9.

Меняем местами первую и третыо строки:

6	8	15	13	9
2	4	7	8	3
6	I I	9	12	8
5	7	6	I I	7
4	10	10	9	14

Начинаем сначала:

6		+	4 =	2 + 8,
6	+	9	< 6	+	15,
6	+	П < 5		+	13,

6 + 14 ^ 4 + 9.

Снова перестраиваем матрицу,			меняя местами первую и пятую
строки:
4	10	10	9	14
2	4	7	8	3
6	I I	9	12	8
5	7	6	II	7
6	8	15	13	9
Строим неравенства
4	+	4 <с	2 +	10,
4 + 9		с	6 + 10,

			97
	4	+	I I	^ 5 +	9.
Преходится перестраивать матрицу еще раз» меняя местами
первую и четвертую строки:
5	7		6	I I	7
2	4		7	8	3
6	II		9	12	8
4	10		10	9	14
6	8		15	13	9
Строим соотношения
5					+ 4 = 2 + 7*
но
5	+ 9 > 6			+ 6»
Поэтому перестроим еще раз		матрицу» меняя местами первую и
третыо строки:					8
6	II		9	12	8
2	4		7	8	3
5	7		6	II	7
4	10		10	9	14
6	8		15	13	9
Строим неравенства			•с	2 + и,
	6 + 4		•с	2 + и,
	6 + 6		с	5 + 9»
	6 + 9		< 4 + 12»
	6 + 9		>	6 + 8.
Снова перестраиваем	матрицу:
6	8		15	13	9
2	4		7	8	3
5	7		6	I I	7
4	10		10	9	14
6	I I		9	12	8

Соотношения

6	+ 4 = 2 + 8,
6	+ 6 < 5	+	15,
6	+ 9 < 4	+	13,
6	+ 8 < 6	+	9

выполняются* Итак» считаем, что число 6, стоящее в четвертом столбце

первой строки исходной матрицы, является компонентой искомого

решения.
В т о р о й	ш а г .	Рассматриваем матрицу
	4	7	8		3
	7	6	I I		7
	10	10	9		14
	I I	9	12		8
Для нее неравенства
	4 + 6 <		7	+ 7,
	4 + 9 <10 +				8,
	4 + 8 <11			+ 3.

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

понентой искомого решения.
Т р е т и й	ш а г .	Для матрицы
	6	I I	7
	10	9	14
	9	12	8

неравенства наполняются:
6 + 9	<	10 + I I ,
6 + 8	<	9 + 7.

Следовательно, число 6, стоящее в третьем столбце четвер той строки исходной матрицы, является третьей компонентой иско

мого решения.
Ч е т в е р т ы й	ш а г . Для матрицы
	9	14
	12	8
единственное неравенство	выполняется
9 + 8		-<• 12 + 14.

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

Следовательно» перестроенная матрица, содержащая найден ное решение по главной диагонали» имеет вид:

6	8	15	13	9
2	4	7	8	3
5	7	6	I I	7 .
4	10	10	9	14
6	I I	9	12	8

Полученное решение:

S = 6 + 4 + 6 + 9 + 8 = 33.

Составим для этой матрицы все неравенства алгоритма:

6 + 4 = 2 + 8 ,			4 + 9	<г 10 +		8,
6 + 6 < 5 + 1 5 ,			4 + 8	<	9 +	I I ,
6 + 9 < 4 + 1 3 *			6 + 9	< 10 +		И ,
6 + 8	<* 6 +	9,	6 + 8	<	9 + 7 *
4 + 6	< 7 +	7*	9 + 8 <		12 +	14.

Равенство

6 + 4 = 2 + 8

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

2	4	7	8	3
6	8	15	13	9
5	7	6	I I	7 .
4	10	10	9	14
6	I I	9	12	8
2 + 8 = 6 + 4»			2 + 9 < 4 + 8 ,
2 + 6 < 5 + 7*			2 + 8 > 6 + 3

Перестроим матрицу, меняя месташ[ первую и последнюю строчки:

6	II	9	12	8
6	8	15	13	9
5	7	6	I I	7 .
4	10	10	9	14
2	4	7	8	3

<<< < Предыдущая 1 2 3 4 5 6 7 8 910 / 2110 11 12 13 14 15 16 17 18 19 20 21 > Следующая >>>

Соседние файлы в папке книги из ГПНТБ