ЗАДАЧА КОММИВОЯЖЕРА В соответствии с номером варианта составить модель задачи линейного программирования, решить ее с помощью Excel. (Решение → 19203)

Заказ №39105

4. ЗАДАЧА КОММИВОЯЖЕРА В соответствии с номером варианта составить модель задачи линейного программирования, решить ее с помощью Excel.                      4 4 7 6 1 6 7 1 4 3 7 3 5 7 2 1 9 4 2 9

РЕШЕНИЕ

Математическая модель данной задачи сводится к заданию двух матриц: X ij  - число прохождений пути из узла i в узел j . Переменная X ij принимает значение 1, если имеет место переход из узла i в узел j и 0 в противном случае. Yij  - расстояния между узлами (в общем случае матрица несимметрична, т.е. ij ji y  y ). Кроме того, должны быть заданы два вектора:   Rin i - ресурс выхода (число выходов из каждого узла);   Rout j - ресурс входа (число входов в каждый узел сети). Целевая функция определяет пройденный путь (маршрут), который должен быть минимальным. Она равна скалярному произведению матриц: F  X ij  Yij  min или в классической постановке min 1 1      n i n j ij ij F x y . Множество допустимых решений ограничивается ресурсами входа и ресурсами выхода:     1 X ij Rin i - число прохождений пути из узла i в узел j не может превышать заданный ресурс выхода из узла i ;     1 X ij Rout j - число прохождений пути из узла i в узел j не может превышать заданный ресурс входа в узел j . Кроме того, для предупреждения петель вводятся дополнительные условия для потенциалов узлов: ui  u j  n 1 xij  n  2 , i, j  2, n. Таким образом, математическая модель задачи: min 1 1      n i n j ij ij F x y ,                               u u n x n i j n x i j n x x i j ij ij j ij i ij 1 2, , 2, 0;1 , , 1, ; 1, 1, Решим задачу в МS Excel Введем матрицу расстояний между узлами Yij  , при этом следует учесть, что целесообразно  заменить на максимальное значение (например, 10000). Также следует сформировать матрицу прохождений путей из узла i в узел j , т.е. матрицу X ij  и целевую функцию в виде суммы всех пройденных путей. Подготовленные таблицы приведены на рис: