Методическое пособие 577

Таблица 60

Редукция строк

Больницы	ВОКБ №1	ОДКБ №2
ГКБ №8	1	0
БСМП №10	0	М

Так как минимальным элементом во всех столбцах является 0, то перейдем к вычислению оценок (табл. 61).

Таблица 61

Вычисление оценок нулевых клеток

Больницы	ВОКБ №1	ОДКБ №2
ГКБ №8	1	0[∞]
БСМП №10	0[∞]	М

Таблица 62

Редукция матрицы

Больницы	ОДКБ №2
ГКБ №8	0

Проведя редукцию матрицы (табл. 62), определили оставшиеся отрезки пути и составили оптимальный маршрут между 5 больницами города Воронежа: ГКБ №8(А) → ОДКБ №2

(B) → БСМП №10 (C) → ВОКБ №1 (D) → БСМП №1 (E) → ГКБ №8 (рис. 20). Длительность маршрута составила 124 мин.

Используем методы решения задачи коммивояжера на еще одном реальном примере. Имеется организация, занимающаяся продажей расходных материалов медицинского назначения. Данная организация «Б. БраунМедикал» расположена по адресу: Воронеж, Купянский переулок, 11. Необходимо доставить ряд расходных материалов в диагностические центры Воронежа, а именно:

1) «МедЭксперт» по адресу: г. Воронеж, улица Генерала Лизюкова, 25;

60

Рис. 20. Итоговый оптимальный маршрут

2)«РусМедЦентр» по адресу: г. Воронеж, Ботанический переулок, 47;

3)«Диагностика плюс» по адресу: Воронеж, Московский проспект, 11;

4)«Медхэлп» по адресу: г. Воронеж, улица Варейкиса, 70;

5)«Медика» по адресу: г. Воронеж, улица Революции

1905 года, 31А;

6)«МедЭксперт» по адресу: г. Воронеж, Пушкинская улица, 4.

Для определения расстояний между намеченными пунктами воспользуемся сервисом «Яндекс Карты». На рис. 21 представлены пункты назначения.

61

Рис. 21. Пункты назначения

	Далее была составлена матрица расстояний									(табл. 63)
и произведено решение.
				Матрица расстояний						Таблица 63
		1	2		3	4		5	6		7
	1	m	7		4,9	5,3		3,8	5,9		4,5
	2	5,1	m		2,6	2,7		4,4	5,6		6,2
	3	3	2,1		m	1,4		2,6	4,3		4,9
	4	4,2	3,3		1,7	m		1,8	3		2,3
	5	2,7	4,1		2,5	2,1		m	2,7		3,3
	6	4,4	7,6		4,9	4,4		3,2	m		2,3
	7	4,1	6,2		4,6	1,9		3	1,9		m

62

Находим минимум по строкам (табл. 64), проводим редукцию строк (табл. 65), определяем минимум по столбцам и выполняем редукцию столбцов (табл. 66). Определим оценки для нулевых ячеек (табл. 67).

Таблица 64

Редукция строк

		1	2		3	4	5		6			7			min
1		m	7		4,9	5,3	3,8		5,9			4,5			3,8
2		5,1	m		2,6	2,7	4,4		5,6			6,2			2,6
3		3	2,1		m	1,4	2,6		4,3			4,9
															1,4
4		4,2	3,3		1,7	m	1,8		3			2,3			1,7
5		2,7	4,1		2,5	2,1		m	2,7			3,3			2,1
6		4,4	7,6		4,9	4,4	3,2		m			2,3			2,3
7		4,1	6,2		4,6	1,9	3		1,9			m			1,9
					Редукция строк								Таблица 65
		1	2		3	4		5		6				7
	1	m	3,2		1,1	1,5		0		2,1				0,7
	2	2,5	m		0	0,1		1,8		3				3,6
	3	1,6	0,7		m	0		1,2		2,9				3,5
	4	2,5	1,6		0	m		0,1		1,3				0,6
	5	0,6	2		0,4	0		m		0,6				1,2
	6	2,1	5,3		2,6	2,1		0,9		m				0
	7	2,2	4,3		2,7	0		1,1		0					m
		0,6	0,7		0	0		0		0				0

			Редукция столбцов						Таблица 66
	1	2		3	4		5	6		7
1	m	2,5		1,1	1,5		0	2,1		0,7
2	1,9	m		0	0,1		1,8	3		3,6

63

Окончание табл. 66

3			1		0		m		0			1,2		2,9	3,5
4			1,9		0,9		0		m			0,1		1,3	0,6
5			0		1,3		0,4		0			m		0,6	1,2
6			1,5		4,6		2,6		2,1			0,9		m	0
7			1,6		3,6		2,7		0			1,1		0	m
						Определение оценок									Таблица 67
		1		2		3			4	5				6	7
1			m	2,5		1,1			1,5	0(0,8)				2,1
															0,7
2		1,9			m	0(0,1)			0,1	1,8				3	3,6
3		1		0(0,9)			m		0(0)	1,2				2,9	3,5
4		1,9		0,9		0(0,1)			m	0,1				1,3	0,6
5		0(1)		1,3		0,4			0(0)			m		0,6	1,2
	6	1,5		4,6		2,6			2,1		0,9			m	0(1,5)
7		1,6		3,6		2,7			0(0)	1,1				0(0,6)
															m

Максимальная оценка соответствует ячейке 6-7. Мы нашли один отрезок пути: 6→7. Вычеркиваем 6-ю строку и 7-й столбец (табл. 68), а в ячейке 7-6 ставим М.

Таблица 68 Результат редукции матрицы и редукции столбцов

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

64

Находим минимум по строкам, проводим редукцию строк, определяем минимум по столбцам и выполняем редукцию столбцов. Определим оценки для нулевых ячеек (табл. 69).

		Редукция матрицы				Таблица 69
	1	2	3	4	5	6
1	m	2,5	1,1	1,5	0(1,2)	1,5
2	1,9	m	0(0,1)	0,1	1,8	2,4
3	1	0(0,9)	m	0(0)	1,2	2,3
4	1,9	0,9	0(0,1)	m	0,1	0,7
5	0(1)	1,3	0,4	0(0)	m	0(0,7)
7	1,6	3,6	2,7	0(1,1)	1,1	m

Как видно из табл. 69, следующий найденный участок пути 1-5. Находим минимум по строкам, проводим редукцию строк, определяем минимум по столбцам и выполняем редукцию столбцов. Определим оценки для нулевых ячеек (табл. 70).

		Редукция матрицы			Таблица 70
	1	2	3	4	6
2	1,9	m	0(0)		2,4
				0,1
3	1	0(0,9)	m		2,3
				0(0)
4	1,9	0,9	0(0,7)	m	0,7
5	m	1,3	0,4	0(0,4)	0(0,7)
7	1,6	3,6	2,7		m
				0(1,6)

Как видно из табл. 70, следующий найденный участок пути 7-4. Находим минимум по строкам, проводим редукцию строк, определяем минимум по столбцам и выполняем редукцию столбцов. Определим оценки для нулевых ячеек (табл. 71).

65

		Редукция матрицы		Таблица 71
	1	2	3	6
2	1,9	m	0(1,9)	2,4
3	1	0(1,9)	m	2,3
4	1,9	0,9	0(0,7)	0,7
5	0(1)	1,3	0,4	0(0,7)

Как видно из табл. 71, следующий найденный участок пути 3-2. Находим минимум по строкам, проводим редукцию строк, определяем минимум по столбцам и выполняем редукцию столбцов. Определим оценки для нулевых ячеек (табл. 72).

		Редукция матрицы		Таблица 72
		1	3	6
	2	1,9	m	2,4
	4	1,9	0(1,1)	0,7
	5		0,4	0(1,1)
		0

Как видно из табл. 72, следующий найденный участок пути 4→3 (в ячейку 2-3 было добавлено М для того, чтобы не возникло преждевременного зацикливания). Находим минимум по строкам, проводим редукцию строк, определяем минимум по столбцам и выполняем редукцию столбцов. Определяем оценки для нулевых ячеек.

Последние найденные участки пути 5-6 и 2-1. В результате был получен оптимальный маршрут 1→5, 5→6, 6→7, 7→4, 4→3, 3→2, 2→1. На рис. 22 представлен полученный оптимальный маршрут на карте.

66

Рис. 22. Проложенный оптимальный маршрут

КОНТРОЛЬНЫЕ ВОПРОСЫ К ГЛАВЕ 5

1.В чем заключается задача коммивояжера?

2.Какие исходные данные необходимо собрать?

3.Почему затраты на время или расстояние участков маршрута 1-2 и 2-1 могут отличаться?

4.Как проводится редукция строк и редукция столбцов?

5.Как высчитываются оценки?

6.Что необходимо делать после отыскания одного из участков маршрута?

7.Почему маршрут может зацикливаться? Как этого избежать?

8.Как определяется итоговый маршрут?

67

ГЛАВА 6. МЕТОДЫ МНОГОКРИТЕРИАЛЬНОЙ ОЦЕНКИ. МЕТОД РЕЙТИНГА ПРИОРИТЕТОВ

Простейшим способом принятия решений в ситуациях с несколькими критериями является присвоение критериям, определяющим качество решения, весовых коэффициентов и вычисление для альтернативных решений оценок по шкале от 1 (наихудшее) до 10 (наилучшее) путем суммирования произведений значений каждого критерия на его весовой коэффициент. Весовые коэффициенты присваиваются каждому критерию исходя из его «важности». В сумме весовые коэффициенты образуют единицу. В итоге решение с наивысшей суммой будет наиболее предпочтительным. Такой метод выбора решения назовем методом рейтинга приоритетов.

Приведем пример использования метода рейтинга приоритетов. Для сравнения были выбраны четыре различных глюкометра: OneToush Select; Сателлит Плюс; Сателлит Экспресс; Accu-Chec Performa Nano. Глюкометры оценивались по четырем критериям: стоимости, стоимости одного комплекта из 25 тестов, внутренней памяти результатов, времени измерения. Стоимость прибора и стоимость тестов являлись более приоритетными критериями, чем другие. Произвели сравнение аппаратов с помощью метода рейтинга приоритетов. Таблица с формулами в EXCEL, а также исходные данные по характеристикам аппаратов приведены на рис. 23. Результат сравнения и выбор наиболее оптимального глюкометра приведены на рис.24.

Рис. 23. Составление таблицы весов, рангов альтернатив и выбор товара с помощью рейтинга приоритетов с формулами

68

Рис. 24. Выбор товара с помощью рейтинга приоритетов

В результате получили, что при сравнении методом рейтинга приоритетов наиболее оптимальным является глюкометр «Сателлит Плюс».

Приведем пример еще одного сравнения с помощью метода рейтинга приоритетов. В этом примере выбираем из трех моделей рефрактометров. Сравнение производится по четырем критериям: стоимости установки, минимальному размеру зрачка, рефрактометрии сферы и цилиндра. Исходные данные представлены на рис. 25.

Рис. 25. Исходные данные для сравнения рефрактометров

Результаты анализа на основе метода рейтинга приоритетов представлены на рис. 26.

69