Рішення задачі комівояжера методом найближчого сусіда в середовищі програмування delphi

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Побудова мінімального кістятка за алгоритмом Борувки в середовищі програмування delphi

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

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

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

Розв'язок задачі нелінійного програмування методом Франка-Вульфа в середовищі програмування delphi

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

Розглядати більш детально процес відшукання розв'яку нелінійних задач методом Франка-Вульфа в даному параграфі не будемо. Його, за бажанням, можна знайти перейшовши за посиланням Розв'язок задач нелінійного програмування з лінійними обмеженнями. А приступимо, до розгляду основних елементів головної форми проекту, та безпосереднь до розв'язку конкретної задачі.

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

Програмна реалізація методу штучного базису в середовищі delphi

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

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

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

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

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

Далі, перейдемо до детального розгляу кожного з елементів головної форми проекту, після чого, з його допомогою, знайдемо розв'язок конкретної задачі лінійного програмування. Отже, головне вікно програми ділиться на три частини:

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

« Попередня сторінкаНаступна сторінка »