Приведенные типы задач решаются средствами Excel также как и обычные транспортные задачи, за одним исключением: так как переменные по смыслу задачи могут принимать только двоичные значения 0 или 1, то в ограничениях, задаваемых в диалоговом окне Поиск решения, необходимо указать, что переменные имеют булевы значения.
Для этого необходимо нажать в окне Поиск решения кнопку Добавить (добавить ограничения) и в открывшемся диалоговом окне Добавление ограничения в левом поле занести ячейки с изменяемыми переменными, а в среднем поле, нажать на среднюю кнопку и выбрать в предложенных видах ограничений требование двоичности.
Решение задачи коммивояжера на Excel.
Имеется 5 городов, расстояния C ij между которыми приведены в табл.
Номер города | 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, должен посетить все города, побывав в каждом из них только по одному разу и вернуться в исходный город. Необходимо определить такой маршрут объезда городов, при которой длина маршрута будет минимальной.