Рассматривается возможность снижения логистических затрат на транспортировку посредством решения задачи коммивояжера. Предлагается алгоритм решения задачи с использованием основной вычислительной мощности надстройки программы "Решатель" OpenOffice Calc.
Аннотация к работе
Практическое применение алгоритма решения задачи коммивояжераТ.к. количество пунктов доставки не слишком велико для решения задачи воспользуемся возможностями надстройки «Решатель» программы OPENOFFICE Calc, который после задания ему условий задачи осуществит полный перебор всех возможных вариантов решения с целью планирования наилучшего маршрута. ООО «Молоко Зауралья» (обозначим как пункт №1) осуществляет поставку продукции для следующих учреждений: ЗАО «Одиссей» (№2), школа №7 (№3), дом ребенка (№4), продовольственный магазин «Трио» (№5), ООО «Вира» (№6), детские сады 116 (№7), 122 (№8), 124 (№9), 126 (№10), 127 (№11), 129 (№12), 130 (№13), 131 (№14), 133 (№15), 134 (№16), 135 (№17), 138 (№18), 141 (№19). На предприятии принят следующий маршрут движения между пунктами: 1) ООО «Молоко Зауралья»; 2) детский сад 127; 3) детский сад 131; 4) детский сад 138; 5) детский сад 141; 6) детский сад 133; 7) продовольственный магазин «Трио»; 8) детский сад 135; 9) детский сад 134; 10) ООО «Вира»; 11) детский сад 130; 12) ЗАО «Одиссей»; 13) детский сад 116; 14) детский сад 129; 15) детский сад 126; 16) дом ребенка; 17) детский сад 124; 18) детский сад 122; 19) школа №7; 20) ООО «Молоко Зауралья». В задаче 4 ограничительных условия: 1) суммы, рассчитываемые по строке «Входит» должны быть равны единице (первое ограничение в «Решателе»); 2) суммы, рассчитываемые по столбцу «выходит» должны равняться единице (второе ограничение); 3) матрица переменных Xij представляет собой булевы числа (третье ограничение); 4) полученные по формуле, прописанной в матрице «Замкнутость маршрута», значения не должны превышать общее количество пунктов задачи, уменьшенное на единицу, т.е. 6) приняли значения от 0 до 17, тем самым показывая конкретный маршрут движения, который представит собой: 1) ООО «Молоко Зауралья»; 2) детский сад 131; 3) детский сад 127; 4) детский сад 138; 5) детский сад 141; 6) продовольственный магазин «Трио»; 7) детский сад 135; 8) детский сад 134; 9) школа №7; 10) ЗАО «Одиссей»; 11) детский сад 130; 12) ООО «Вира»; 13) детский сад 116; 14) детский сад 129; 15) детский сад 122; 16) детский сад 124; 17) детский сад 126; 18) дом ребенка; 19) детский сад 133; 20) исходный пункт, с которого начиналось движение ООО «Молоко Зауралья».