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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Головне вікно програми ділиться на три частини:

  1. Панель існтрументів: містить два компоненти типу TSpinEdit (відповідають за розмірність симплекс таблиці) та дві кнопки типу TButton ("Знайти оптимальний план задачі лінійного програмування" та "Очитстити"). Перша з них, реалізує процедуру побудови оптиамльного розв'язку задачі лінійного програмування за симплекс методом і друга — готує проек до нового прикладу.
  2. Робоча область: містить таблицю типу TStringGrid, у комірки якої, способом введення з клавіатури, заносяться дані початкової симплекс таблиці.
  3. Область виводу рузультатів: містить компонент TPageControl, який, по ходу виконання програми доповнюється сторінками TTableSheet та таблицями TStringGrid, кожна з яких містять опорний план, отриманий на кожній ітерації алгоритму (оптимальний план заданої задачі міститься в останній таблиці).

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

Програмна реалізація методу плаваючих зон для побудови опорного плану транспортної задачі

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

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

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

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

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

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

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