Введемо позначення. Нехай і – місто відправлення, j – місто прибуття .
– матриця відстаней між будь- яким містом відправки і будь-якиммістом прибуття. Загалом матриця
не є симетричною
, оскільки задача про комівояжера вважається математичною моделлю, до якої наводяться не тільки задачі транспортування, але і ряд інших оптимізаційних задач. Наприклад, задача календарного планування, звана задачею одного верстата, також наводиться до моделі задачі про комівояжера. Шуканими величинами також будуть компоненти матриці
, кожна з яких приймає значення "1", якщо комівояжер їде з і-го міста в j-ий і дорівнює "0", якщо цього переїзду немає.
Математична модель наступна
Цільова функція досягне свого мінімуму при значеннях хij, які зумовлюють цикл об'їзду міст.
Обмежуючі умови інтерпретується так, обов'язково здійснити виїзд з кожного міста
і обов'язково приїде в будь-яке місто
Шукана величина приймає значення 1 або 0
Приклад.
Є 5 міст. Матриця відстаней наступна
Можливі об'їзди можна подивитися на рис. 7.1.
Рисунок 7.1. Варіанти об'їзду
Оптимальний об'їзд міст на рис. 7.2
Рисунок 7.2. Оптимальний об'їзд
Мінімальна довжина дороги становить 13 одиниць.
Визначення оптимального плану економічних заходів
Сторінки
В нашій електронній бібліотеці ви можете безкоштовно і без реєстрації прочитати «Менеджмент організацій і адміністрування» автора Харічков С.К. на телефоні, Android, iPhone, iPads. Зараз ви знаходитесь в розділі „Задача і математична модель доставки однорідної продукції споживачам через складські приміщення“ на сторінці 2. Приємного читання.
