Реферат: Решение задачи о назначениях в программе Microsoft Excel

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

Решение задач средствами Excel.

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

Для этого необходимо нажать в окне Поиск решения кнопку Добавить (добавить ограничения) и в открывшемся диалоговом окне Добавление ограничения в левом поле занести ячейки с изменяемыми переменными, а в среднем поле, нажать на среднюю кнопку и выбрать в предложенных видах ограничений требование двоичности (рис. 1). Дальнейший алгоритм действий остается без изменений (см. Методические пособия к 1-ой и 2-ой Лабораторным работам).

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

Имеется 5 городов, расстояния Cij между которыми приведены в табл.

Номер города	1	2	3	4	5
1	∞	9	8	4	10
2	6	∞	4	5	7
3	5	3	∞	6	2
4	1	7	2	∞	8
5	2	4	5	2	∞

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

Коммивояжер выезжая из города 1, должен посетить все города, побывав в каждом из них только по одному разу и вернуться в исходный город. Необходимо определить такой маршрут объезда городов, при которой длина маршрута будет минимальной.

2. Математическая модель

Переменные xij могут принимать значения равные либо 0, либо 1

– целевая функция

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

– условие въезда в город j только один раз

– условие выезда из города i только один раз

, где n = 5, т.е. , i ≠ j, i, j = 2,…, n .

Исходные данные в рабочей книге Excel приведены на рис. 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