Розв'язок задачі комівояжера використовуючи метод подвійного обходу мінімального кістяка

Перш ніж приступити до розгляду чергового способу рішення задачі комівояжера, давайте нагадаємо собі, що собою являє задача такого типу, а також методи, які нами вже було вивчено. Отже, у найпростішому вигляді задачу комівояжера можна сформулювати наступним чином: треба знайти такий найкоротший маршрут по заданих населених пунктах, щоб кожен з них відвідали тільки один раз і кінцевим опинився пункт, з якого починалося подорож. Дану проблему зручно змоделювати за допомогою зваженого графа, вершини якого представляють населені пункти, а ваги ребер визначають відстані між ними. Після цього задача може бути сформульована як задача пошуку найкоротшого гамільтонового циклу деякого графа.

Далі, у вигляді списку, запишемо методи рішення задачі комівояжера, які нами вже було розглянуто і з теоретичною частиною яких можна ознайомитись, перейшовши по відповідному посиланню:

  1. Метод редукції рядків та колонок.
  2. Метод осереднених коефіцієнтів.
  3. Метод Монте-Карло.
  4. Метод найближчого сусіда.

Відмітимо, що одні з них відносяться до категорії точних методів і в якості розв'язку дають оптимальний маршрут, але їх використання являється недоцільним в тому випадку, коли число населених пунктів задачі є достатньо великим числом. Інші — дозволяють швидко отримати рішення задачі комівояжера будь-якої розмірності, але без гарантії його оптимальності.

Читати повністю

Знаходження ровз'язку задачі комівояжера методом найближчого сусіда

Виходячи з того, що для більшості комбінаторних задач ефективного способу відшукання оптимального рішення не існує, то в такому випадку, приходять до використання евристичних алгоритми, тобто алгоритмів, які дозволяють швидко отримати рішення, але без гарантії його оптимальності.

Особливий інтерес, з практичної точки зору, представляє процес знаходження ровз'язку задачі комівояжера для великої (близько тисячі) кількості пунктів призначення. В цьому випадку, точні методи рішення задач такого типу не дають бажаного результату, так як вимагають величезних обчислювальних витрат, і процес вирішення займає надто багато часу. Тому на практиці, зазвичай, використовуються евристичні методи, серед яких найбільш використовуваним та відомим являється метод найближчого сусіда.

Основна його суть при розв'язку задачі комівояжера полягає в тому, що пункти призначення послідовно включаються в маршрут, причому кожний наступний пункт, що включається, вибирається таким чином, щоб він був найближчим до останнього вже включеному серед усіх пунктів, ще не включених в маршрут. Основним недоліком даного методу є те, що деякі міста «пропускаються» в ході роботи алгоритму, і в результаті доводиться їх включати в кінці маршруту з більш високими тарифами, що в свою чергу негативно впливає на кінцевий результат (збільшенням довжини маршруту, а відповідно, і затрат на переміщення).

Читати повністю

Знаходження розв'язку задачі дробово-лінійного програмування шляхом зведення її до задачі лінійного програмування

Нехай, зновутаки, розглядається задача математичного програмування, яка полягає у відшуканні екстремального (мінімального чи максимального) значення функції мети:

при наступних обмеженнях:

Крім того, передбачається, що в області невід'ємних розв'язків системи рівнянь (2) має місце нерівність .

Відмітимо, що розглядуваний тип задач відноситься до класу задач дробово-лінійного програмування і які ми вже навчилися розв'язувати з допомогою графічного методу. Проте, графічний спосіб рішення задач такого типу (як і будь-якого іншого типу задач математичного програмування) являється не дуже універсальним, тобто використовується в тому випадку, коли кількість невідомих задачі не перевищує число два. Сьогодні розглянемо дещо інший спосіб, який можна вважати більш універсальним, і який базується на зведенні задач з дробово-лінійною цільовою функцією до задачі лінійного програмування і, в подальшому, розв'язку її будь-яким з відомих методів (симплекс методу, двоїстий симплекс метод, метод штучного базису).

Читати повністю

Розв'язок задачі комівояжера методом Монте-Карло в середовищі програмування delphi

Delphi-програма реалізує статистичний алгоритм методу Монте-Карло, з допомогою якого здійснюється розв'язок задачі комівояжера (також відома як задача про бродячого торговця). Тобто, основна суть delphi-проекту зводиться до побудови маршруту таким чином, щоб комівояжер побував у кожному пункті по одному разу і повернувся у початковий. Відмітимо, що в якості критерію оптимальності може слугувати мінімальний час проводений в дорозі, мінімальні витрати на переміщення і, звичайно, мінімальна довжина шляху.

Отже, після запуску проекту, на екрані появиться форма наступного вигляду:

Головне вікно проекту "Розв'язок задачі комівояжера методом Монте-Карло"

Головне вікно проекту "Розв'язок задачі комівояжера методом Монте-Карло"

Тобто для того, щоб знайти розв'язок деякої задачі комівояжера (в нашому випадку розв'язується задача, яку ми розглядали при вивченні теоретичної частини методу Монте-Карло для рішення задач такого типу), від користувача вимагається задати кількість населених пунктів, в яких повинен побувати комівояжер, заповнити таблицю значеннями, які відповідатимуть одному з вищевказаних критеріїв оптимальності та натиснути кнопку "Знайти оптимальний маршрут".

Читати повністю

Рішення задачі комівояжера методом Монте-Карло

Методами Монте-Карло називать будь-яку статистичну процедуру, яка використовує статистичну вибірку. Сьогодні застосуємо дану процедуру, для знаходження розв'язку задачі комівояжера. Для цього припустимо, що у задачі комівояжер повинен проїхати міст, і побудувати свій маршрут таким чином, щоб побувати у кожному місті по одному разу і повернутися у початкове. Відмітимо, що, при цьому, витрати на переміщення між містами повинні бути мінімальними.

Отже, для рішення задачі комівояжера методом Монте-Карло, використовується датчик випадкових чисел. Тобто, на першому кроці, серед міст з зномерами (місто з номером один є початковим, тому його вибирати не потрібно) випадковим чином вибираємо по одному місту і запам'ятовуємо їх послідовність. Відмітимо, що в подальшому дана послідовність вважатиметься за оптимальний маршрут. Для цього маршруту розраховуємо функцію мети і також запам'ятовуємо її.

Зауваження: у середовищі програмування delphi, яке ми зазвичай використовуємо для програмної реалізації розглядуваних на даному сайті алгоритмів та методів, існує стандартна функція Random, яка дозволяє програмно формувати випадкові числа. Фактично ця та аналогічні функції в інших мовах програмування є датчиками випадкових чисел.

Читати повністю

Розв'язок задачі дробово-лінійного програмування графічним методом

При розгляді теоретичної частини задачі дробово-лінійного програмування, а зокрема, при розгляді конкретної задачі такого типу, нами було анонсовано, що в подальшому дану задачу буде розв'язано з допомогою графічного методу та методу, який базується на зведенні задач з дробово-лінійною цільовою функцією до задачі лінійного програмування. Сьогодні розглянемо перший з них, але перш ніж приступити до розв'язку задачі, розглянемо алгоритм даного методу більш детально. Для цього, припустимо, що нам потрібно знайти максимальне (мінімальне) значення функції мети (де ):

при наступних обмеженнях:

Щоб знайти рішення задачі (1) — (3), спочатку, як і у випадку задачі лінійного програмування, знаходимо багатокутник рішень, який визначається обмеженнями (2) і (3). Припускаючи, що цей багатокутник не порожній, покладаємо значення функції (1) рівним деякому числу :

Читати повністю

Задача дробово-лінійного програмування. Математична модель задачі дробово-лінійного програмування

У деяких практичних завданнях критерій прийняття рішень описується відношенням двох економічних або технічних параметрів. У таких ситуаціях необхідно приймати рішення з метою максимізації або мінімізації відношення цих двох параметрів. Якщо кожен з них математично описується лінійною функцією, то в таких випадках необхідно знайти екстремум (максимум чи мінімум) відношення цих двох лінійних функцій. Відношення двох лінійних функцій називають дробово-лінійною цільовою функцією. Задача оптимізації дробово-лінійної функції при лінійних обмеженнях називається задачею дробово-лінійного програмування. Як правило, при максимізації відношення двох економічних показників, показник чисельника прагне досягти максимальне можливе значення, а показник знаменника — мінімальне. При мінімізації — навпаки.

Читати повністю

Наступна сторінка »