Українські рефератиучбові матеріали на українській мові

RefBaza.com.ua пропонує студентам та абітурієнтам найбільшу базу з рефератів! Також ви можете ділитися своїми рефератами для поповнення бази.

Завдання про коммивояжере

Реферат: Завдання про коммивояжере

Оглавление

Оглавление

Запровадження

Постановка завдання

Алгоритм рішення .

Математична модель завдання .

Опис програмної реалізації алгоритму .

Опис програмного інтерфейсу

Опис програми .

Література .

Запровадження

Нині швидко розвивається науково-технічна революція. З'явившись на в 40-ві роки нашого століття комп'ютери і комп'ютерні технології пройшли цей час шлях від лампових систем з прямим завданням кодів операцій до надшвидких персональних комп'ютерів на монокристальной технології, використовують під час роботи многопользовательские операційні системи з графічним інтерфейсом. Найбільш бурхливий розвиток комп'ютерних технологій сталося протягом останніх 10-15 років, коли розробили технологія виробництва СБИС, але в основі мікрочіпів. Також на початку 80-х почала розвиватися концепція персональної ЕОМ, що згодом конкретизувалася у існування двох найпоширеніших апаратних платформ: Macintosh (виробляється фірмою Apple, процесори фірми Motorola) і IBM PC (виробляється фірмою IBM, процесори фірми Intel).

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

Фірма IBM, на відміну Apple, дотримується концепції відкритої системи, виражену у цьому, що, по-перше, IBM немає ексклюзивного права виробництво та продаж IBM-сумісних комп'ютерів (їх виробляє багато фірм, як-от Hewlett Packard, AT&T, Compaq та інші), і навіть повної сумісності пізніх моделей з більш ранніми, що дозволяло IBM довгий час утримувати ринок збуту, як і раніше, що спочатку 90-х Macintosh-и помітно перевершували PC продуктивністю (зараз, з приходом Pentium і PowerPC, Macintosh-и втратили беззастережне лідерство продуктивністю).

Персональні комп'ютери нині переважно використовують у чотирьох регіонах:

· обробка текстів і їх комп'ютерна верстка;

· зберігання баз даних із можливістю швидкої їх опрацювання;

· управління виробничими процесами;

· аналіз складних процесів;

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

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

Найяскравішим і характерним прикладом застосування завдання "Про коммивояжере" стала оптимізація операцій на конвеєрі: в 1984 року, коли було проведено аналізу послідовності і тимчасових витрат за операції у конвеєрах заводів компанії "General Motors" і прийнято рекомендовані заходи, збільшити загальну продуктивність на 13% за незмінної числі робітників і тому самому устаткуванні. Розрахунки проводилися за комп'ютерами IBM 360gr, які на той час були серед самих продуктивних систем у світі. Прорахунок і оптимізація 200 основних та 87 допоміжних операцій тривав близько 230 годин. Вважається, що це перша комерційне застосування комп'ютерних технологій у галузі управління виробництвом загалом.

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

Тому викладена проблема на сучасному розвитку суспільства" має не найостанніше за значимістю місце.

Постановка завдання

Класична завдання про коммивояжере виглядає так:

Є N міст, що має обійти комівояжер з мінімальними витратами. У цьому з його маршрут накладається два обмеження:

· маршрут може бути замкнутим, тобто комівояжер маю повернутися у той місто, із якої він почав рух;

· у кожному з міст комівояжер повинен побувати точно одного разу, тобто обов'язково обминути всі міста, у своїй не побувши жодного щодо одного місті двічі.

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

Алгоритм рішення

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

Загальна схема методу така (дана програмна реалізація):

1. Усі безліч розбивається на N-1 підмножин, кожна з яких оцінюється верхньої та нижньої оцінками.

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

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

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

Математична модель завдання

N - число міст.

Ci j , і, j=1 N - матриця витрат, де Ci j - видатки перехід із i-го міста, у j-й.

Xi j - матриця переходів з компонентами:

Xi j = 1, якщо комівояжер робить перехід із i-го міста, у j-й,

Xi j = 0, а то й робить переходу,

де і, j = 1 N і i


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

Статистика

[1] 2 3 4 5