Завдання вибору маршруту або мережеві завдання 3 - Документ - стор
Завдання вибору маршруту або мережеві завдання 3
Транспортні завдання 3
Алгоритм розв'язання транспортного завдання 7
Приклад розв'язання транспортного завдання 7
Мережеві завдання 13
Алгоритм вирішення мережного завдання 19
Знаходження мінімального кістяка у графі з прикладом розв'язання задачі 19
Знаходження найкоротшого шляху у графі з прикладом розв'язання задачі 21
Приклади вирішення завдань у пакетах Microsoft Office Excel 2003 та Mathcad 2001i Professional 24
Список литературы 32
Математика необхідна у повсякденному житті, отже, певні математичні навички потрібні кожній людині. Нам доводиться в житті рахувати, ми постійно використовуємо знання про величини, що характеризують протяжність, площу, обсяги, проміжки часу, швидкості та багато іншого. Все це прийшло до нас на уроках арифметики та геометрії та знадобилося для орієнтації в навколишньому світі.
Математичні знання та навички потрібні практично у всіх професіях, насамперед, звичайно, у тих, що пов'язані з природничими науками, технікою та економікою. Математика є мовою природознавства та техніки і тому професія дослідника природознавства та інженера вимагає серйозного оволодіння багатьма професійними відомостями, заснованими на математиці.
Сьогодні безсумнівна необхідність застосування математичних знань та математичного мислення лікарю, лінгвісту, історику та людям інших спеціальностей. Але особливо знання математики потрібні людям точних професій – фінансистам, економістам. Таким чином, математика та математична освіта потрібні для підготовки до майбутньої професії.
Одним із класів математичних моделей є завдання лінійного програмування. Одним із завдань лінійногопрограмування є транспортне завдання – завдання складання оптимального плану перевезень, що дозволяє мінімізувати сумарний кілометраж.
Мета даної курсової роботи з курсу «Теорія інформаційних процесів та систем» є розбір теоретичної частини, отриманих на лекційному курсі та самостійне застосування на практиці теоретичних знань до вирішення завдань щодо дослідження систем.
У цій роботі мною будуть проведені висновки у виробленні оптимального рішення для знаходження найкоротшого шляху між декількома заданими точками, який був би найефективнішим.
Об'єктом дослідження є перевезення вантажу з пунктів виробництва до пунктів споживання, а також знаходження найкоротшої відстані між точками у графах.
Мета роботи: визначення системи оптимального управління перевезеннями вантажу та знаходження найкоротшого шляху, щоб витратити менше грошей.
Актуальність теми у тому, що завдання вибору маршруту застосовні скрізь, але найчастіше зустрічаються щодо різноманітних процесів на транспорті й у системах зв'язку (комп'ютерні мережі).
Завдання вибору маршруту чи мережеві завдання.
Типовим завданням вибору маршруту є знаходження деякого маршруту проїзду з одного міста до іншого, за наявності безлічі шляхів через різні проміжні пункти. Завдання полягає у визначенні найбільш економічного маршруту за критерієм часу, відстані чи вартості проїзду.
При розгляді низки маршрутів запроваджуються такі обмеження:
- забороняється повертатися до вже пройденого пункту,
- у пунктах мережі можливі затримки (наприклад, через обмежену пропускну здатність). Затримки мають випадковий характер.
Критерії оптимізації: мінімізація загальногочасу проходження маршруту чи мінімізація загальних витрат.
Одним із прикладів таких завдань може бути завдання комівояжера.
Завдання комівояжера (бродячий торговець) є одним із найвідоміших завдань комбінаторної оптимізації. Завдання полягає у відшуканні найвигіднішого маршруту, що проходить через зазначені міста хоча б по одному разу з подальшим поверненням у вихідне місто. В умовах завдання вказуються критерій вигідності маршруту (найкоротший, найдешевший, сукупний критерій тощо) та відповідні матриці відстаней, вартості тощо. Як правило, вказується, що маршрут повинен проходити через кожне місто лише один раз — у такому у разі вибір здійснюється серед гамільтонових циклів.
Существует несколько частных случаев общей постановки задачи, в частности геометрическая задача коммивояжёра (также называемая планарной или евклидовой, когда матрица расстояний отражает расстояния между точками на плоскости), треугольная задача коммивояжёра (когда на матрице стоимостей выполняется неравенство треугольника), симметричная и асимметричная задачи коммивояжёра. Також існує узагальнення завдання, так зване узагальнене завдання комівояжера.
Загальна постановка завдання, втім, як і більшість її окремих випадків, відноситься до класу NP-складних завдань.
Так чи інакше, все зводиться до вирішення транспортного завдання.
Транспортне завдання ділиться на два види: транспортне завдання за критерієм вартості – визначення плану перевезень, за якого вартість вантажу була б мінімальною; транспортне завдання за критерієм часу – найважливішим є виграш за часом.
Транспортна задача за критерієм вартості є окремим випадком завдання лінійного програмування і може бути вирішена симплексним методом. Однак усилу особливостей завдання, вона вирішується набагато простіше.
Це завдання зводиться до визначення такого плану перевезень деякого продукту з пунктів його виробництва до пунктів споживання (xi, jmxn), який мінімізує цільову функцію
на безлічі допустимих планів
за умови дотримання умови балансу
Транспортна задача є представником класу задач лінійного програмування і тому має всі якості лінійних оптимізаційних завдань, але одночасно вона має і низку додаткових корисних властивостей, які дозволили розробити спеціальні методи її вирішення.
Якщо привести умови транспортної задачі до канонічної форми задачі лінійного програмування, то матриця завдання матиме розмірність (m+n) x mn. Матриці систем рівнянь в обмеженнях (3.2) та (3.3) мають ранги, рівні відповідно m та n. Проте, якщо, з одного боку, підсумувати рівняння (3.2) по m, з другого – рівняння (3.3) по n, то з (3.5) отримаємо одне й те значення. З цього випливає, що одне із рівнянь у системі (3.2)-(3.3) є лінійною комбінацією інших. Таким чином, ранг матриці транспортної задачі дорівнює m+n-1 і її невироджений базисний план повинен містити m+n-1 ненульових компонент.
Процес вирішення транспортної задачі зручно оформляти як послідовності таблиць, структура яких представлена на рис.3.1.
Рядки транспортної таблиці відповідають пунктам виробництва (в останній клітині кожного рядка вказано обсяг запасу продукту аi), а стовпці – пунктам споживання (остання клітина кожного стовпця містить значення потреби bj). Усі клітини таблиці (крім тих, які розташовані в нижньому рядку та правому стовпці) містять інформацію про перевезення з i-го пункту до j-го: у лівому верхньому куткуперебуває вартість перевезення одиниці товару, а правому нижньому – значення обсягу перевозимого вантажу даних пунктів. Клітини, які містять нульові перевезення (хi, j = 0), називають вільними, а ненульові – зайнятими (xi, j & gt; 0).
За аналогією коїться з іншими завданнями лінійного програмування рішення транспортної завдання починається з побудови допустимого базисного плану. Найбільш простий спосіб його знаходження ґрунтується на так званому методі північно-західного кута. Суть методу полягає в послідовному розподілі всіх запасів, що є в першому, другому і т. д. пунктах виробництва, за першим, другим і т. д. пунктами споживання. Кожен крок розподілу зводиться до спроби повного вичерпання запасів у черговому пункті виробництва або до спроби повного задоволення потреб у черговому пункті споживання. На кожному етапі q величини поточних нерозподілених запасів позначаються аi(q), а поточних незадоволених потреб – bj(q). Побудова припустимого початкового плану, згідно з методом північно-західного кута, починається з лівого верхнього кута транспортної таблиці, причому вважаємо аi(0) = аi, bj(0) = bj. Для чергової клітини, розташованої в рядку i і стовпці j, розглядаються значення нерозподіленого запасу в i-му пункті виробництва та незадоволеної потреби j-му пункті споживання, з них вибирається мінімальне і призначається як обсяг перевезення між цими пунктами: xi,j = min . Після цього значення нерозподіленого запасу та незадоволеної потреби у відповідних пунктах зменшуються на цю величину:
Вочевидь, що у кожному кроці виконується хоча одне з рівностей: аi(q+1)=0 чи bj(q+1)=0 . Якщо справедливо перше, це означає, що весь запас i-го пункту виробництва вичерпаний інеобхідно перейти до розподілу запасу в пункті виробництва i+1, тобто переміститися до наступної клітини вниз стовпцем. Якщо ж bj(q+1)=0, отже, повністю задоволена потреба для j-го пункту, після чого слідує перехід на клітинку, розташовану праворуч по рядку. Знову обрана клітина стає поточною, й у неї повторюються всі перелічені операції.
Ґрунтуючись на умови балансу запасів і потреб (3.5), неважко довести, що за кінцеву кількість кроків ми отримаємо допустимий план. У силу тієї ж умови кількість кроків алгоритму не може бути більшою, ніж m+n-1, тому завжди залишаться вільними (нульовими) mn-(m+n-1) клітин. Отже, отриманий план є базовим. Ймовірно, що у певному проміжному кроці поточний нерозподілений запас виявляється рівним поточної незадоволеної потреби (аi(q) = bj(q)). У цьому випадку перехід до наступної клітини відбувається в діагональному напрямку (одночасно змінюються поточні пункти виробництва та споживання), а це означає «втрату» однієї ненульової компоненти у плані або, іншими словами, виродженість побудованого плану.
Розглянемо застосування методу північно-західного кута на конкретному прикладі. Транспортна таблиця 3.1 містить умови деякого завдання, а табл. 3.2 показаний процес пошуку допустимого плану, включаючи послідовну зміну обсягу нерозподілених запасів та незадоволених потреб. Стрілки відображають траєкторію переходу по клітинах транспортної таблиці, а цифри, що знаходяться за її межами, – поточні нерозподілені залишки після призначення обсягу чергової клітини.
Особливістю допустимого плану, побудованого методом північно-західного кута, є те, що цільова функція на ньому набуває значення, як правило,далеке від оптимального. Це тому, що з його побудові аж ніяк не враховуються значення сi,j. У зв'язку з цим практично отримання вихідного плану використовується інший спосіб – метод мінімального елемента, у якому за розподілі обсягів перевезень насамперед займаються клітини з найменшими цінами.
Алгоритм розв'язання транспортного завдання.
Завдання можна вирішити, використовуючи алгоритм розв'язання транспортного завдання. Застосування цього алгоритму вимагає дотримання ряду передумов:
1. Має бути відома вартість перевезення одиниці товару з кожного пункту виробництва, у кожен пункт призначення.
2. Запас продуктів у кожному пункті виробництва має бути відомим.
3. Потреби у продуктах у кожному пункті споживання мають бути відомі.
4. Загальна пропозиція має дорівнювати загальному попиту.
Алгоритм розв'язання транспортного завдання складається з чотирьох етапів:
Етап I. Подання даних у формі стандартної таблиці та пошук будь-якого допустимого розподілу ресурсів. Допустимим називається такий розподіл ресурсів, який дозволяє задовольнити весь попит у пунктах призначення та вивезти весь запас продуктів із пунктів виробництва.
Етап 2. Перевірка отриманого розподілу ресурсів на оптимальність
Етап 3. Якщо отриманий розподіл ресурсів не є оптимальним, ресурси перерозподіляються, знижуючи вартість транспортування.
Етап 4. Повторна перевірка оптимальності одержаного розподілу ресурсів.
Цей ітеративний процес повторюється доти, доки не буде отримано оптимальне рішення.
Приклад розв'язання транспортного завдання.
Завдання 1. З трьох холодильників Ai, i=1..3, що вміщають морожену рибу в кількостях ai т, необхідно останнядоставити до п'яти магазинів Bj, j=1..5 у кількостях bj т. Вартість перевезення 1т риби з холодильника Ai до магазину Bj задані як матриці Cij, 3x5.
Написати математичну модель завдання та спланувати перевезення так, щоб їхня загальна вартість була мінімальною.
Складемо математичну модель завдання. Нехай xi,j - кількість т риби, що перевозиться з холодильника (постачальника) Ai до магазину (споживач) Bj. Тоді завдання полягає у мінімізації загальних транспортних витрат
Завдання має закритий тип, т.к. запаси вантажу 320+280+250 = 850 т дорівнюють сумарним потребам магазинів 150+140+110+230+220 = 850 т.
Складемо опорний план за правилом мінімального елемента.