А). Исходные данные

Фирма по ремонту бытовой техники планирует обслуживание клиентов по их заявкам на очередной день. Всего поступило 4 заявки от населения из разных районов города (адресов проживания). Удовлетворение всех заявок требует доставки техники в ремонтную мастерскую. Для доставки техники на очередной день выделен один автомобиль. Известны расстояния от мастерской до каждого пункта проживания заявителей и расстояния между пунктами (табл. 1).

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

Таблица 1.4.

Расстояния от мастерской до мест проживания заявителей

Номера	Номера пунктов
пунктов	1	2	3	4	5
1	10000	10	8	54	10
2	6	10000	4	5	7
3	5	3	10000	6	12
4	1	7	2	10000	8
5	2	35	5	2	10000

Б). Экономико-математическая модель решения задачи

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

Математическая постановка задачи состоит в следующем.

Определить булевы переменные :

;

.

Тогда сама задача заключается в определении минимума целевой функции

, (1.6)

при ограничениях:

,(только один въезд в пункт), (1.7)

,(только один выезд из пункта), (1.8)

В задаче коммивояжера необходимо еще одно условие, а именно:

,. (1.9)

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

В). Решение задачи коммивояжера в Excel

Подготовительный этап

1). Создаем исходную таблицу (рис. 1.13) и вносим в нее имеющиеся исходные данные.

Рис. 1.13. Исходные данные для решения задачи.

2). Создаем таблицу для размещения результатов решения задачи (рис. 1.14).

Рис. 1.14. Таблица для результатов решения задачи.

3). Создаем таблицу для ограничений по дополнительным переменным, исключающим циклы (рис. 1.15).

Рис. 1.15. Таблица для ограничений по дополнительным переменным.

Заполнение таблиц формулами, связывающими план объезда, ограничения и целевую функцию (наименьшее расстояние, время, стоимость и т.д.)

1). Заполняем формулами значения ограничений на въезд и выезд в таблице, где будут размещены результаты решения задачи (рис. 4)

Для этого устанавливаем курсор в ячейку на пересечении строки Ограничения на въезд в j и столбца с номером пункта 1 (ячейка В10) и активируем ее, щелкнув левой кнопкой мыши (рис. 1.16);

Рис. 1.16. Заполнение формулами таблицы результаты решения (ввод ограничений).

вызываем мастер функций, щелкнув по пиктограмме f_x и в категории «математические» выбираем функцию СУММ, нажимаем ОК (рис. 1.17);

в появившемся окне (рис. 1.18) в строку массив 1 вводим данные, которые будут получены в результате решения задачи в столбце 1, выделив в столбце ячейки В5:В9. Для этого необходимо установить курсор в ячейку В5, щелкнуть левой кнопкой мыши и удерживая ее в нажатом положении протащить курсор до ячейки В9 включительно;

Рис. 1.17. Вызов мастера функций и поиск функции СУММ.

Рис. 1.18. Заполнение формулами строки ограничений на въезд.

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

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

2). Вводим формулу для вычисления значения целевой функции (рис. 1.19)

Рис. 1.19. Ввод формулы для определения значения целевой функции.

Для этого активируем свободную ячейку, в которую будет заноситься значение целевой функции (В11 на рис. 1.19);

вызываем мастер функций, щелкнув по пиктограмме f_x, и в появившемся окне в категории «математические» выбираем функцию СУММПРОИЗВ, щелкаем ОК;

в появившемся окне в строку массив 1 вводим адреса ячеек, в которых размещены значения расстояний между пунктами, а в строку массив 2 адреса ячеек, в которых будут размещен план объезда (рис 1.19). Нажимаем ОК.

3). Заполнение формулами таблицы ограничений по дополнительным переменным для вычисления значения целевой функции. Принципы заполнения показаны в таблице 1.5. При этом в качестве данных по дополнительным переменным () используются данные из ячеек последней строки таблицы с результатами решения задачи (рис 1.20).

Таблица 1.5.

Принципы заполнения таблицы ограничений с дополнительными переменными

	U2	U3	U4	U5
U2
U3
U4
U5

Рис. 1.20. Заполнение формулами таблицы ограничений по дополнительным переменным.

Вычислительный этап

1). Запускаем программу «Поиск решения» командой Данные/Анализ/Поиск решения (Excel 2007) или Сервис/Поиск решения (Excel 2003 и ниже).²

2). Заполняем поля в появившемся окне:

в поле «установить целевую ячейку» вводим адрес ячейки ($F$26), в которой будет находиться искомое значение расстояния (рис. 1.21);

в поле «изменяя ячейки» вводим адреса ячеек (рис. 1.21), в которых будут находиться искомые величины плана объезда и ячеек с ограничениями связанности (рис. 1.21);

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

в появившемся окне «добавление ограничения» в поле «ссылка на ячейку» вводим значения ограничений (рис.1.21).

После ввода ограничений нажимаем кнопку «Выполнить» в окне «Поиск Решения».

Рис. 1.21. Работа в окне «Поиск решения».

Анализ результатов расчетов

Данные по решению задачи находятся в таблице «Результаты решения» (рис. 1.22). Так в строках «Номера пунктов» размещены значения искомых переменных. Если они равны 1, то движение осуществляется из номера пункта в троке таблицы в номер пункта в столбце (из пункта 1 в пункт 3, из 3 в 2, из 2 в 5, из 5 в 4, из 4 в 1). В рассматриваемой задаче минимальное

Рис. 1.22. Результаты решения задачи.

расстояние (протяженность) объезда заявителей составит 21 ед. длины и обеспечивается при движении по маршруту 1, 3, 2, 5,4,1.

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

1.4.1. Определение наикратчайшего маршрута развозки автомобилей со склада дилерского центра в автосалоны

Логистическая служба дилерского центра планирует маршрут развозки автомобилей от склада в 4 автосалона. Для доставки автомобилей достаточно выделить один автовоз. Известны расстояния перевозок автомобилей от склада до каждого автосалона и расстояния перевозок между автосалонами (табл. 1.6). Требуется составить наикратчайший маршрут движения автовоза, чтобы автовоз доставил автомобили в каждый автосалон, посетив его только один раз, и вернулся на склад дилерского центра.

Таблица 1.6.

Расстояния от дилерского центра до автосалонов и между автосалонами

Номера	Номера пунктов
пунктов	1	2	3	4	5
1		10	8	54	10
2	6		4	5	7
3	5	3		6	12
4	1	7	2		8
5	2	35	5	2

1.4.2. Определение минимального времени переналадки универсального оборудования для изготовления продукции

Фирма имеет возможность получения заказа на изготовление n разных деталей на принадлежащем ей оборудовании. Изготовление каждой детали требует переналадки оборудования. Длительность переналадки оборудования для обработки j-ой детали после i-ой детали равна . Найти последовательность изготовления деталей, имеющей минимальную суммарную длительность. Данные о продолжительности переналадки оборудования приведены в табл. 1.7.

Таблица 1.7.

Данные о продолжительности переналадки оборудования

Детали	1	2	3	4	5	6
1		20	28	12	39	32
2	21		15	9	17	27
3	30	25		45	29	47
4	7	52	40		15	1
5	60	46	11	5		34
6	11	45	14	21	30

1.4.3. Определение оптимального маршрута туристской поездки

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

Таблица 1.8.

Данные о стоимости проезда на самолете от исходного пункта до каждого из городов и между городами

Города	1	2	3	4	5	6	7	8
1		190	210	680	690	460	780	750
2	190		380	760	790	610	670	450
3	210	380		890	900	340	410	600
4	680	760	890		480	760	510	250
5	690	790	900	480		890	490	560
6	460	610	340	760	890		720	600
7	780	670	410	510	490	720		500
8	750	450	600	250	560	600	500