Теми рефератів
> Реферати > Курсові роботи > Звіти з практики > Курсові проекти > Питання та відповіді > Ессе > Доклади > Учбові матеріали > Контрольні роботи > Методички > Лекції > Твори > Підручники > Статті Контакти
Реферати, твори, дипломи, практика » Курсовые проекты » Програмний засіб знаходження найкоротших шляхів в графі

Реферат Програмний засіб знаходження найкоротших шляхів в графі





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

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

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

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

. Вибір типу транспортного засобу

. Вибір виду транспортного засобу

. Спільне планування транспортних процесів зі складськими і виробничими операціями

. Спільне планування транспортних процесів на різних видах транспорту

. Забезпечення технологічної єдності транспортно-складського процесу

. Визначення раціональних маршрутів поставки

Всі вони (крім підзадач пов'язаних зі складськими операціями) будуть порушені в даному дослідженні.


1.3 Підходи до вирішення завдання


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

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

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

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

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

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


1.4 Завдання комівояжера


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

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

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

Загальна постановка задачі, втім, як і більшість її окремих випадків, відноситься до класу NP-складних завдань.

Перелічимо основні методи вирішення цього завдання:

· повний лексичний перебір

· випадковий перебір

· жадібні алгоритми

o метод найближчого сусіда

o метод включення найближчого міста

o метод найдешевшого включення

· метод мінімального остовного дерева


Назад | сторінка 3 з 24 | Наступна сторінка





Схожі реферати:

  • Реферат на тему: Рішення завдання комівояжера за допомогою алгоритму Дейкстри
  • Реферат на тему: Рішення задачі про комівояжера
  • Реферат на тему: Метод потенціалів для вирішення транспортної задачі в матричній формі. Зад ...
  • Реферат на тему: Застосування транспортної моделі до вирішення завдання оптимального закріпл ...
  • Реферат на тему: Дерев'яний алгоритм вирішення задачі комівояжера