2020-05-25
319
Переменные 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 |
