Переменные xij могут принимать значения равные либо 0, либо 1
– целевая функция
ограничения:
– условие въезда в город j только один раз
– условие выезда из города i только один раз
, где n = 5, т.е. , i ≠ j, i, j = 2,…, n.
Исходные данные в рабочей книге Excel приведены на рис. 2. Здесь же приведены формулы для вычисления ограничений и целевой функции.
Рис. 2. Исходные данные в задаче коммивояжера |
На панели Поиск решения установить следующие параметры решения задачи:
Целевую ячейку – $B$10
Равной минимальному значению
Изменяя ячейки: $B$4:$F$8;$C$11:$F$11 – здесь заносятся не только ячейки, которые будут изменяться, и в которых будут занесены решение задачи (ячейки с адресами $B$4:$F$8), но и ячейки $C$11:$F$11, содержащие переменные ui , которые также являются изменяемыми.
Ограничения:
$B$21:$E$24≤3
$B$4:$F$8 = двоичное
$B$9:$F$9=1
$G$4:$G$8=1
$B$4=0
$C$5=0
$D$6=0
$E$7=0
$F$8=0
Параметры: линейная модель, неотрицательные значения, автоматическое масштабирование
После нажатия кнопки Выполнить на диалоговой панели Поиск решения. На рабочем листе Excel появляются результаты решения задачи (рис. 3).
ЗАДАЧА КОММИВОЯЖЕРА |
|
|
|
|
| |||
| Матрица переменных |
|
| Ограничения | ||||
| 1 | 2 | 3 | 4 | 5 |
| ||
1 | 0 | 0 | 0 | 1 | 0 | 1 | ||
2 | 1 | 0 | 0 | 0 | 0 | 1 | ||
3 | 0 | 0 | 0 | 0 | 1 | 1 | ||
4 | 0 | 0 | 1 | 0 | 0 | 1 | ||
5 | 0 | 1 | 0 | 0 | 0 | 1 | ||
Ограничения | 1 | 1 | 1 | 1 | 1 |
| ||
Целевая функция в B10 | 18 |
|
|
|
|
| ||
Переменные u в C11:F11 | 3 | 1 | 0 | 2 |
| |||
| Матрица расстояний
|
|
|
| ||||
| 1 | 2 | 3 | 4 | 5 |
| ||
1 | 10000 | 9 | 8 | 4 | 10 |
| ||
2 | 6 | 10000 | 4 | 5 | 7 |
| ||
3 | 5 | 3 | 10000 | 6 | 2 |
| ||
4 | 1 | 7 | 2 | 10000 | 8 |
| ||
5 | 2 | 4 | 5 | 2 | 10000 |
| ||
Формулы для Ограничений по дополнительным переменным u |
|
| ||||||
| u2 | u3 | u4 | u5 |
|
| ||
u2 | 0 | 2 | 3 | 1 |
|
| ||
u3 | -2 | 0 | 1 | 3 |
|
| ||
u4 | -3 | 3 | 0 | -2 |
|
| ||
u5 | 3 | 1 | 2 | 0 |
|
|
Рис. 3. Результаты решения задачи коммивояжера
Итак, оптимальное решение таково: целевая функция F = 18, получившийся маршрут: 1 – 4 – 3 – 5 – 2 – 1.
Индивидуальные задания:
Вариант № 1.
Распределить работы таким образом, чтобы минимизировать временные затраты на выполнение всех работ при условии, что каждый из претендентов получит одну и только одну из работ. Матрица временных затрат каждого претендента на выполнение каждой из работ приведена ниже.
Работники | Номера работ | |||||||||
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
Иванов | 17 | 9 | 1 | 15 | 1 | 9 | 3 | 4 | 6 | 3 |
Петров | 4 | 14 | 11 | 11 | 4 | 12 | 2 | 3 | 5 | 3 |
Сидоров | 0 | 17 | 18 | 16 | 9 | 16 | 4 | 6 | 7 | 1 |
Копылов | 4 | 17 | 10 | 12 | 16 | 14 | 3 | 7 | 3 | 1 |
Минин | 2 | 5 | 18 | 8 | 18 | 5 | 1 | 6 | 1 | 3 |
Резько | 7 | 17 | 0 | 8 | 8 | 17 | 7 | 3 | 2 | 7 |
Власов | 3 | 1 | 1 | 3 | 2 | 3 | 4 | 5 | 3 | 0 |
Демченко | 6 | 0 | 2 | 1 | 1 | 5 | 4 | 0 | 1 | 1 |
Серёгин | 0 | 1 | 3 | 7 | 4 | 3 | 5 | 2 | 2 | 4 |
Панин | 3 | 3 | 5 | 0 | 3 | 0 | 3 | 1 | 1 | 0 |
Вариант № 2.
Необходимо решить задачу на назначение: распределить вакансии таким образом, чтобы минимизировать временные затраты на выполнение работ при условии,что каждый из претендентов получит одну и только одну из работ. Матрица временных затрат каждого претендента на выполнение заданной работы:
№ вак. раб. | 1 | 2 | 3 | 4 | 5 | 6 |
Качурова | 0 | 2 | 8 | 9 | 4 | 3 |
Панова | 8 | 12 | 14 | 7 | 1 | 3 |
Стевко | 9 | 10 | 0 | 0 | 4 | 8 |
Санин | 12 | 2 | 1 | 1 | 7 | 0 |
Пинских | 9 | 14 | 2 | 4 | 6 | 13 |
Петров | 10 | 3 | 3 | 7 | 8 | 2 |
Вариант № 3.
Необходимо решить задачу на назначение: распределить вакансии таким образом, чтобы минимизировать временные затраты на выполнение работ при условии,что каждый из претендентов получит одну и только одну из работ.
Матрица временных затрат каждого претендента на выполнение заданной работы:
№ вак. раб. | 1 | 2 | 3 | 4 | 5 | 6 |
Володин | 3 | 5 | 4 | 9 | 10 | 13 |
Ганшин | 15 | 7 | 3 | 9 | 5 | 7 |
Попов | 5 | 5 | 1 | 3 | 2 | 11 |
Сидоров | 2 | 8 | 6 | 11 | 17 | 14 |
Хаджиев | 18 | 11 | 3 | 5 | 14 | 6 |
Зорин | 12 | 16 | 8 | 11 | 8 | 10 |
Вариант № 4.
Необходимо решить задачу на назначение: распределить вакансии таким образом, чтобы минимизировать временные затраты на выполнение работ при условии,что каждый из претендентов получит одну и только одну из работ.
Матрица временных затрат каждого претендента на выполнение заданной работы:
№ вак. раб. | 1 | 2 | 3 | 4 | 5 | 6 |
Чертков | 15 | 19 | 11 | 4 | 3 | 13 |
Демичев | 14 | 6 | 5 | 7 | 0 | 9 |
Фурцева | 16 | 7 | 19 | 13 | 3 | 7 |
Токин | 0 | 10 | 9 | 1 | 14 | 16 |
Столяров | 1 | 14 | 18 | 4 | 14 | 6 |
Носов | 0 | 4 | 1 | 13 | 10 | 0 |
Вариант № 5.
Необходимо решить задачу на назначение: распределить вакансии таким образом, чтобы минимизировать временные затраты на выполнение работ при условии,что каждый из претендентов получит одну и только одну из работ.
Матрица временных затрат каждого претендента на выполнение заданной работы:
№ вак. раб. | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Суслов | 17 | 9 | 1 | 3 | 1 | 8 | 1 | 9 | 15 |
Ларин | 4 | 14 | 4 | 0 | 0 | 5 | 6 | 12 | 11 |
Выгонова | 0 | 17 | 5 | 0 | 7 | 6 | 9 | 16 | 16 |
Петров | 4 | 5 | 6 | 5 | 4 | 2 | 1 | 14 | 12 |
Васин | 2 | 17 | 7 | 4 | 3 | 7 | 0 | 5 | 8 |
Титов | 7 | 9 | 5 | 1 | 1 | 4 | 2 | 17 | 8 |
Шохин | 1 | 5 | 4 | 6 | 0 | 3 | 3 | 9 | 11 |
Чапкина | 2 | 17 | 6 | 7 | 5 | 1 | 5 | 10 | 16 |
Беликова | 4 | 9 | 7 | 8 | 3 | 7 | 5 | 12 | 12 |
Вариант № 6.
Необходимо решить задачу на назначение: распределить вакансии таким образом, чтобы минимизировать временные затраты на выполнение работ при условии,что каждый из претендентов получит одну и только одну из работ. Матрица временных затрат каждого претендента на выполнение заданной работы:
|
|
№ вак. раб. | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
Беляев | 2 | 6 | 5 | 8 | 4 | 8 | 1 | 8 |
Сидоров | 4 | 9 | 5 | 8 | 2 | 8 | 2 | 7 |
Ваничкин | 5 | 9 | 5 | 2 | 6 | 7 | 9 | 7 |
Зайцева | 5 | 2 | 7 | 2 | 6 | 7 | 4 | 9 |
Ватагин | 6 | 2 | 8 | 5 | 5 | 7 | 8 | 6 |
Родин | 2 | 4 | 5 | 5 | 3 | 3 | 2 | 3 |
Шмыглов | 7 | 6 | 9 | 6 | 5 | 5 | 4 | 7 |
Петренко | 7 | 1 | 9 | 11 | 6 | 7 | 6 | 1 |
Вариант № 7.
Необходимо решить задачу на назначение: распределить вакансии таким образом, чтобы минимизировать временные затраты на выполнение работ при условии,что каждый из претендентов получит одну и только одну из работ.
Матрица временных затрат каждого претендента на выполнение заданной работы:
№ вак. раб. | 1 | 2 | 3 | 4 | 5 | 6 |
Шорин | 2 | 5 | 1 | 0 | 3 | 0 |
Волков | 3 | 4 | 4 | 1 | 5 | 1 |
Чайников | 7 | 3 | 5 | 6 | 8 | 9 |
Летвинов | 5 | 7 | 3 | 5 | 10 | 2 |
Дорина | 1 | 6 | 7 | 4 | 3 | 5 |
Быкова | 0 | 4 | 6 | 3 | 5 | 4 |
Вариант № 8.
Необходимо решить задачу на назначение: распределить вакансии таким образом, чтобы минимизировать временные затраты на выполнение работ при условии,что каждый из претендентов получит одну и только одну из работ. Матрица временных затрат каждого претендента на выполнение заданной работы:
№ вак. раб. | 1 | 2 | 3 | 4 | 5 | 6 |
Скляров | 12 | 2 | 4 | 2 | 1 | 0 |
Данин | 5 | 9 | 6 | 6 | 3 | 7 |
Панина | 7 | 2 | 2 | 3 | 4 | 5 |
Шолохов | 2 | 8 | 8 | 9 | 0 | 2 |
Власенко | 0 | 4 | 4 | 8 | 6 | 4 |
Сытин | 4 | 3 | 1 | 5 | 2 | 3 |
Вариант № 9.
Необходимо решить задачу на назначение: распределить вакансии таким образом, чтобы минимизировать временные затраты на выполнение работ при условии,что каждый из претендентов получит одну и только одну из работ. Матрица временных затрат каждого претендента на выполнение заданной работы:
№ вак. раб. | 1 | 2 | 3 | 4 | 5 | 6 |
Тыквин | 3 | 8 | 5 | 10 | 3 | 0 |
Болшев | 4 | 1 | 8 | 9 | 0 | 1 |
Строгина | 7 | 7 | 3 | 5 | 3 | 6 |
Жданов | 2 | 4 | 6 | 6 | 5 | 3 |
Чёрный | 5 | 2 | 8 | 4 | 2 | 7 |
Ногина | 4 | 0 | 1 | 2 | 6 | 9 |
Вариант № 10.
Необходимо решить задачу на назначение: распределить вакансии таким образом, чтобы минимизировать временные затраты на выполнение работ при условии,что каждый из претендентов получит одну и только одну из работ. Матрица временных затрат каждого претендента на выполнение заданной работы:
|
|
№ вак. раб. | 1 | 2 | 3 | 4 | 5 | 6 |
Костина | 2 | 4 | 5 | 7 | 8 | 1 |
Кузнецов | 3 | 1 | 0 | 2 | 3 | 6 |
Швындин | 4 | 5 | 5 | 7 | 9 | 7 |
Петров | 5 | 3 | 10 | 5 | 5 | 2 |
Сидоров | 1 | 4 | 3 | 8 | 7 | 1 |
Иваненко | 3 | 2 | 5 | 4 | 4 | 2 |
Вариант № 11.
Необходимо решить задачу на назначение: распределить вакансии таким образом, чтобы минимизировать временные затраты на выполнение работ при условии,что каждый из претендентов получит одну и только одну из работ. Матрица временных затрат каждого претендента на выполнение заданной работы:
№ вак. раб. | 1 | 2 | 3 | 4 | 5 | 6 |
Никитин | 4 | 3 | 4 | 0 | 1 | 2 |
Коткова | 6 | 12 | 5 | 6 | 3 | 7 |
Равин | 2 | 7 | 0 | 8 | 8 | 3 |
Глатерман | 8 | 1 | 3 | 5 | 5 | 5 |
Чуйкова | 4 | 5 | 2 | 4 | 8 | 9 |
Санченко | 9 | 0 | 5 | 3 | 4 | 1 |
Вариант № 12.
Необходимо решить задачу на назначение: распределить вакансии таким образом, чтобы минимизировать временные затраты на выполнение работ при условии,что каждый из претендентов получит одну и только одну из работ.
Матрица временных затрат каждого претендента на выполнение заданной работы:
№ вак. раб. | 1 | 2 | 3 | 4 | 5 | 6 |
Сеченов | 3 | 7 | 3 | 3 | 0 | 9 |
Кудрявцев | 5 | 5 | 5 | 9 | 5 | 2 |
Попкова | 2 | 9 | 2 | 8 | 3 | 6 |
Танин | 7 | 8 | 8 | 6 | 5 | 4 |
Воловик | 1 | 2 | 6 | 5 | 1 | 2 |
Пьянова | 9 | 4 | 3 | 6 | 2 | 4 |
Вариант № 13.
Необходимо решить задачу на назначение: распределить вакансии таким образом, чтобы минимизировать временные затраты на выполнение работ при условии,что каждый из претендентов получит одну и только одну из работ. Матрица временных затрат каждого претендента на выполнение заданной работы:
№ вак. раб. | 1 | 2 | 3 | 4 | 5 | 6 |
Иванов | 2 | 11 | 5 | 14 | 4 | 9 |
Петров | 4 | 8 | 9 | 9 | 5 | 6 |
Сидоров | 6 | 7 | 3 | 2 | 8 | 2 |
Васин | 3 | 9 | 0 | 7 | 3 | 9 |
Лорин | 9 | 3 | 5 | 6 | 8 | 5 |
Борисова | 12 | 0 | 8 | 5 | 4 | 4 |
Вариант № 14.
Необходимо решить задачу на назначение: распределить вакансии таким образом, чтобы минимизировать временные затраты на выполнение работ при условии,что каждый из претендентов получит одну и только одну из работ. Матрица временных затрат каждого претендента на выполнение заданной работы:
№ вак. раб. | 1 | 2 | 3 | 4 | 5 | 6 |
Вырин | 3 | 2 | 4 | 9 | 2 | 2 |
Карина | 4 | 1 | 6 | 2 | 6 | 6 |
Рожнев | 8 | 3 | 4 | 8 | 9 | 9 |
Суслова | 6 | 5 | 8 | 5 | 2 | 4 |
Пинкин | 2 | 4 | 10 | 4 | 8 | 0 |
Лапин | 0 | 9 | 4 | 2 | 3 | 7 |
Вариант № 15.
Необходимо решить задачу на назначение: распределить вакансии таким образом, чтобы минимизировать временные затраты на выполнение работ при условии,что каждый из претендентов получит одну и только одну из работ. Матрица временных затрат каждого претендента на выполнение заданной работы:
№ вак. раб. | 1 | 2 | 3 | 4 | 5 | 6 |
Анукин | 2 | 4 | 4 | 3 | 5 | 1 |
Павлова | 5 | 8 | 7 | 9 | 6 | 5 |
Динченко | 9 | 8 | 6 | 6 | 8 | 3 |
Волохов | 4 | 5 | 9 | 8 | 2 | 0 |
Ританин | 0 | 4 | 2 | 4 | 1 | 8 |
Бобова | 2 | 4 | 0 | 3 | 5 | 6 |
Вариант № 16.
Необходимо решить задачу на назначение: распределить вакансии таким образом, чтобы минимизировать временные затраты на выполнение работ при условии,что каждый из претендентов получит одну и только одну из работ. Матрица временных затрат каждого претендента на выполнение заданной работы:
№ вак. раб. | 1 | 2 | 3 | 4 | 5 | 6 |
Говорухин | 3 | 6 | 8 | 6 | 5 | 1 |
Панюшкин | 5 | 9 | 5 | 6 | 5 | 2 |
Попков | 7 | 7 | 4 | 8 | 7 | 6 |
Ратникова | 4 | 2 | 8 | 5 | 8 | 4 |
Капин | 9 | 5 | 9 | 4 | 2 | 0 |
Мастерова | 10 | 4 | 0 | 2 | 9 | 3 |