183894 (584851), страница 7

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 7)

Шаг 15. Из невычеркнутых элементов матрицы максимальным элементом является с_2,5=17. Вторая невеста назначается пятому жениху, вычеркиваем вторую строку.

В табл. 5.1 номер шага, на котором были получены базисные переменные, указан в скобках. После 15 шага получим пробный вариант назначения Х₀: х_1,7=х_2,5= х_3,4=х_4,3=х_5,8=х_6,2= х_7,1=х_8,6=1. Это означает, что первая невеста выходит замуж за седьмого жениха, вторая невеста за пятого жениха, третья невеста за четвертого жениха, четвертая невеста за третьего жениха, пятая невеста за восьмого жениха, шестая невеста за второго жениха, седьмая невеста за первого жениха, восьмая невеста за шестого жениха.

Таблица 5.1.

31	13	11	41	10	17	38	25
			0(7)	0(13)		1(8)
35	20	26	8	17	14	38	36
0(11)	0(14)	0(12)		1(15)		0(7)	0(10)
12	37	38	49	38	22	10	13
			1(1)
28	21	48	43	44	29	26	12
		1(4)
37	22	39	46	26	20	44	49
							1(2)
22	49	19	2	20	30	45	16
	1(3)
45	27	5	21	30	21	34	23
1(6)
43	33	20	29	3	46	33	21
					1(5)

Суммарная эффективность, отвечающая полученному варианту выбора равна:

условных единиц эффективности

Вариант выбора проверим на оптимальность. Для этого вычислим потенциалы и оценки.

Отсюда вычислим потенциалы:

Для небазисных переменных вычислим оценки по соответствующей формуле:

И так далее расчеты по соответствующим формулам и данным приведены в таблице 5.2.

Таблица 5.2

Х0	28	13	19	41	10	44	38	29
	31	13	11	41	10	17	38	25
0				0(7)	0(13)		1(8)
Оценка1	-3	0	8			27		4
	35	20	26	8	17	14	38	36
7	0(11)	0(14)	0(12)		1(15)		0(7)	0(10)
Оценка2				40		37
8	12	37	38	49	38	22	10	13
				1(1)
Оценка3	24	-16	-11		-20	30	36	24
29	28	21	48	43	44	29	26	12
			1(4)
Оценка4	29	21		27	-5	44	41	46
	37	22	39	46	26	20	44	49
20								1(2)
Оценка5	11	11	0	15	4	44	14
	22	49	19	2	20	30	45	16
36		1(3)
Оценка6	42		36	75	26	50	29	49
	45	27	5	21	30	21	34	23
17	1(6)
Оценка7		3	31	37	-3	40	21	23
	43	33	20	29	3	46	33	21
2						1(5)
Оценка8	-6	-11	8	-19	16		7	17

Cреди вычисленных оценок имеются отрицательные, это означает, что выбранный вариант назначения не является оптимальным. Наименьшая из отрицательных оценок Строим цикл пересчета: (3,5), (2,5), (1,7), (1,4), (3,5) замыкающийся на разрешающей клетке. Вычислим величину корректировки . Базисный нуль 0_3,5 перемещается в клетку (1,7), переменная х_1,7 включается в базис, а переменная х_3,5 выходит из базиса. Получим новую комбинацию расстановки единиц и нулей (Табл. 5.3). Суммарная эффективность равна:

условных единиц эффективности

Таблица 5.3

Х0	28	13	19	41	10	44	38	29
	31	13	11	41	10	17	38	25
0				1(7)	0(13)		0(8)
Оценка1	-3	0	8			27		4
	35	20	26	8	17	14	38	36
7	0(11)	0(14)	0(12)		0(15)		1(7)	0(10)
Оценка2				40		37
28	12	37	38	49	38	22	10	13
					1(7)
Оценка3	44	4	9	20		50	56	44
29	28	21	48	43	44	29	26	12
			1(4)
Оценка4	29	21		27	-5	44	41	46
	37	22	39	46	26	20	44	49
20								1(2)
Оценка5	11	11	0	15	4	44	14
	22	49	19	2	20	30	45	16
36		1(3)
Оценка6	42		36	75	26	50	29	49
	45	27	5	21	30	21	34	23
17	1(6)
Оценка7		3	31	37	-3	40	21	23
	43	33	20	29	3	46	33	21
2						1(5)
Оценка8	-6	-11	8	-19	16		7	17

Заново вычисляем потенциалы и оценки.

Характеристики

Список файлов ответов (шпаргалок)