Застосування методів дискретної математики в економіці
Принципи застосування логічних функцій в рішенні економічних задач. Практичне використання методів дискретної математики, поняття теорії графів. Сутність алгоритмів: "жадібного", Дейкстри. Розв’язування задачі "комівояжера", вибір з декількох альтернатив.
| Рубрика | Математика |
| Вид | контрольная работа |
| Язык | украинский |
| Дата добавления | 27.10.2015 |
| Размер файла | 250,4 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
МАРІУПОЛЬСЬКИЙ ДЕРЖАВНИЙ УНІВЕРСИТЕТ
КАФЕДРА МАТЕМАТИЧНИХ МЕТОДІВ ТА СИСТЕМНОГО АНАЛІЗУ
КОНТРОЛЬНА РОБОТА
з дисципліни «Дискретна математика»
Застосування методів дискретної математики в економіці
Виконала студентка I курсу
Білоног Ярослава
Спеціальність «Системний аналіз»
Група СА-13
Викладач Ротаньова Н.Ю.
м. Маріуполь - 2014
Зміст
Вступ
1. Застосування логічних функцій
1.1 Застосування методів дискретної математики в економіці
1.2 Практичне застосування методів математичної логіки
2. Застосування теорії графів
2.1 Практичне застосування «жадібного» алгоритму
2.2 Застосування алгоритму Дейкстри
2.3 Задача «комівояжера»
Висновки
Література
Вступ
Актуальність теми. При дослідженні, аналізі та вирішенні управлінських проблем, моделюванні об'єктів дослідження та аналізу широко використовуються методи формалізованого уявлення, що є предметом розгляду в дискретної математики. До них відносяться методи, засновані на теоретико-множинних уявленнях, графи, алгоритми формальні системи, математична логіка.
В економіці існує безліч галузей, що використовують методи дискретної математики. Це і економетрика, і логістика, і математичне моделювання. Так, в економетриці булеві змінні застосовуються в дослідженні регресійних моделей зі змінною структурою і в побудові регресійних моделей по неоднорідним даним. У цьому випадку розглядається лише одне рівняння регресії, куди вводяться булеві змінні, які характеризують фактор, що досліджується. Даний метод зручний для виявлення залежності моделі від деякого фактора.
Теорія графів широко використовується в логістиці для опису потоків, завдання маршрутів. Так, схему доріг зручніше представити у вигляді орієнтованого графа, і відомими нам методами вибрати найкоротший шлях. В даний час, прокладаючи маршрут, не можна не брати до уваги і пропускну здатність магістралей, інтерпретуючи маршрути в графи, можна отримати економічно вигідне рішення.
Мета роботи: ознайомитися з максимально широким колом понять дискретної математики та виявити її основні методи, які можуть використовуватися в економіці. Розкрити взаємозв'язок понять, їх внутрішню логіку. Навчитися правильно формулювати економічні завдання.
Об'єкт дослідження: дискретні системи, методи дискретної математики та їх застосування в галузі економіки.
Предметом дослідження виступає застосування методів дискретної математики в економіці
Методи дослідження: методологічну і теоретичну основу проведеного дослідження становлять сучасні праці провідних вітчизняних та зарубіжних науковців, періодичні видання за зазначеною темою, інформація мережі Інтернет.
Теоретичне значення полягає в тому, що розглянуті теоретичні відомості деяких розділів дискретної математики, що присвячені елементам математичної логіки та теорії графів.
Практичне значення складається з того, що в курсовій роботі були розглянуті і застосовані методи математичної логіки: метод побудови таблиці істинності, знаходження полінома Жегалкина методом невизначених коефіцієнтів, метод знаходження похідних, метод знаходження кон'юнктівной і діз'юнктівной нормальної форми; методи теорії графів: «жадібний» алгоритм, алгоритм Дейкстри, угорський метод розв'язання задачі комівояжера.
1. Застосування логічних функцій
1.1 Застосування методів дискретної математики в економіці
При дослідженні, аналізі та вирішенні управлінських проблем, моделюванні об'єктів дослідження та аналізу широко використовуються методи формалізованого представлення, що є предметом розгляду в дискретнiй математицi. До них відносяться методи, засновані на теоретико-множинних уявленнях, графи, алгоритми формальні системи, математична логіка.
В економіці існує безліч галузей, що використовують методи дискретної математики. Це і економетрика, і логістика, і математичне моделювання. Так, в економетриці булеві змінні застосовуються в дослідженні регресійних моделей із змінною структурою і в побудові регресійних моделей за неоднорідними даними. В цьому випадку розглядається лише одне рівняння регресії, куди вводяться булевi змінні, які характеризують досліджуваний фактор. Даний метод зручний для виявлення залежності моделі від деякого фактора. Теорія графів широко використовується в логістиці для опису потоків, завдання маршрутів. Так, схему доріг зручніше представити у вигляді орієнтованого графа і відомими нам методами вибрати найкоротший шлях. В даний час, прокладаючи маршрут, не можна не брати до уваги і пропускну здатність магістралей. Інтерпретуючи маршрути в графи, можна отримати економічно вигідне рішення.
За допомогою теорії нечітких множин, методом нечіткого уподобання, можна вибрати конкурентоспроможний товар чи послугу. Тому, дана теорія застосовується в маркетології, при дослідженні ринків різних економічних благ.
1.2 Практичне застосування методу математичної логіки
Будь-яка логічна функція «n» змінних може бути задана таблицею, в лівій частині якої перераховані всі 2n наборів значень змінних (тобто всіляких наборів двійкових векторів довжини «n»), а в правій частині наведені значення функції на цих наборах. При будь-якому фіксованому впорядкуванні наборів значень змінних логічна функція «n» змінніх повністю визначена вектор-стовпцем своїх значень, тобто вектором довжиною 2n.
Тому число різніх логічніх функцій «n» змінних буде . Справді, для одного набору значень своїх змінних (рядок лівої частини таблиці) значення функції може бути або 1 або 0 (дві можливості). Число ж можливих різних наборів аргументів функції, як вже зазначалося, одне 2n, тому число різних логічних функцій буде .
Завданням в даному пункті є побудова таблиці істинності для наступного висловлювання:
.
Висловлюванням називається оповідна пропозиція, про яку можна сказати в даний момент, що воно істинна або хибна, але не те й інше одночасно. "Істинність" або "хибність" пропозиції - це истиннicне значення висловлювання. Кожному вислову зіставляється змінна, рівна 1, якщо висловлювання істинно, і рівна 0, якщо воно помилкове. Ці висловлювання будуть вважатися простими. З простих висловлювань за допомогою логічних зв'язок можуть бути побудовані складові висловлювання. У таблиці 1 наведені деякі логічні зв'язки, використані при завданні даної функції (1).
Таб. 1. Логічні зв'язки
|
Назва |
Позначення |
|
|
Кон'юнкція |
||
|
Імплікація |
||
|
Сума по модулю два |
||
|
Штрих Шеффера |
| |
|
|
Заперечення |
||
|
Диз'юнкція |
||
|
Стрілка Пірса |
Правильно побудовані складові висловлювання називаються (пропозіціонарнимі) формулами. Істиннicне значення формули визначається через істиннісні значення її складових відповідно до єдиної таблицi істинності (Таб.2).
Таб. 2. Істиннісні значення формул висловлювання
|
Х1 |
Х2 |
X1 X2 |
X1 X2 |
X1 X2 |
X1 X2 |
X1 |
X1 X2 |
|
|
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
|
|
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
|
|
1 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
Для того щоб скласти таблицю істинності для формули, необхідно виконати послідовність всіх логічних операцій.
(1)
Після послідовного виконання всіх логічних операцій складається таблиця істинності для даної функції:
Таб. 3. Таблиця iстинностi функції (1)
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
|
x |
y |
z |
& |
|
|
|
||||
|
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
|
|
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
|
|
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
|
|
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
|
|
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
|
|
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
|
|
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
|
|
1 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
Приведення функції до кон'юнктивних і диз'юнктивних нормальних форм. Кон'юнктивною (диз'юнктивною) одночленною від змінних а1, а2, а3,…,аn називається кон'юнкція (диз'юнкція) цих змінних або їх заперечень. Формула, рівносильна даній формулі алгебри висловлювань і є диз'юнкцією елементарних творів (кон'юнктивні одночленів), називається диз'юнктивною нормальною формою (ДНФ) даної формули. Формула, рівносильна даній формулі алгебри висловлювань і є кон'юнкцією елементарних творів (діз'юнктівних одночленів), називається кон'юнктівною нормальною формою (КНФ) даної формули.
Справедливі наступні теореми: будь-яка булева функція, яка тотожно не дорівнює нулю, представима і притому задається єдиним чином у вигляді ДНФ за формулою:
V (2)
Будь-яка булева функція, яка тотожно не дорівнює одиниці, представима і притому єдиним чином у вигляді КНФ.
(3)
Будь-яка булева функція представима формулою, в яку входить тільки кон'юнкція, диз'юнкція і заперечення (2).
Шукана ДНФ для функції (1) має вигляд:
Шукана КНФ для функції (1) буде мати наступний вигляд:
Побудова полінома Жегалкина. Представлення булевої функції над базисом {0,1,v,} називається поліномом Жегалкина.
Таким чином, всяка булева функція подана в вигляді:
Де ? - додавання по модулю два, знак ? позначає кон'юнкцію.
Для функції f(x,y,z)(1) поліном Жегалкина має вигляд:
P(x, y, z)=011x2y3z4xy5xz6yz7xyz
Метод невизначених коефіцієнтів полягає в тому, що шляхом послідовної підстановки змінних x, y, z і відповідних значень функції при цих змінних, з таблиці 1 в даний поліном (4), будується система рівнянь:
0=011020304005006007000
0=011020314005016017001
1=011021304015006107010
0=011021314015016117011
0=011120304105106007100
0=011120314105116017101
0=011121304115106107110
0=011121314115116117111
По властивості суми по модулю два знаходиться :
0=0, 1=0, 2=1, 3=0, 4=1, 5=0, 6=1, 7=1
Поліном Жегалкина матиме вигляд:
(x, y, z) = y xy yz xyz
Правильність побудови полінома перевіряється таблицею істинності:
Таб. 4. Таблиця істинності для полінома Жегалкина
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
|
x |
y |
z |
x&y |
y&z |
x&y&z |
||||
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
|
|
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
|
|
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
|
|
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
Диференціювання функції декількох змінних. Похідною булевої функції (xn) за сукупністю змінних називається функція:
На основі даної формули (5) знаходиться похідна по одній змінній x
Для даної функції (1) похідна по формулі (6) приймає вигляд:
Таб. 5. Похідна ???x для формули (7)
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
|
|
x |
y |
z |
& |
|
|
|
|
||||||
|
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
|
|
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
|
|
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
|
|
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
|
|
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
|
|
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
|
|
1 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
|
|
1 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
Вектор значень функції (7) має вигляд:
Похідна за двома змінним знаходиться також по формулі (5):
Для даної функції (1) похідна приймає вигляд:
Таб. 6. Похідна ?2??(x;y) для формули (9)
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
|
x |
& |
|
|
|
|
|||||||
|
0 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
|
|
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
|
|
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
|
|
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
|
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
|
|
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
|
|
1 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
|
|
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
Вектор значень функції (6) має вигляд:
2. Застосування теорії графів
2.1 Практичне застосування «жадібного» алгоритму
Рис. 1. Графічна інтерпретація задачі про оптимальну структуру мережі
З вищесказаного випливає, що дану економічну задачу можна розв'язати за допомогою теорії графів. Потрібно знайти дерево покриття мінімальної ваги. Задача вирішується за допомогою різновиду «жадібного» алгоритму, алгоритму Краскала.
Нехай є кінцева множина Е, |E|=18, вагова функція w: ER+ і сімейство ?? 2Е. Потрібно знайти ХЕ, таке що:
Нехай Е - непорожня кiнцева множина, w: ER+ - функція, яка ставить у відповідність кожному елементу е цієї множини невід'ємне дійсне число w(e) - вага елемента е. Для Х Е вага w(Х) визначимо як суму ваг усіх елементів множини Х:
Іншими словами, необхідно вибрати в даному сімействі непорожню підмножину найменшої ваги.
Зіставимо кожному пункту мережі вершину графа G. А кожному ребру цього графа зіставимо число, рівне вартості будівництва відповідної комунікації: (Рис. 1.).
Прикладом жадiбного алгоритму служить алгоритм Краскала. Існує теорема, яка стверджує, що алгоритм Краскала завжди призводить до ребра, має мінімальну вагу. Згідно з алгоритмом Краскала, вибирається ребро мінімальної ваги. В даному випадку це буде ребро е1 = {3,5}, отримуємо граф Т1. Будується граф Т2 = Т1 + е2, де е2 - ребро, яке має мінімальну вагу серед ребер, що не входять в Т1 і не становить циклів з ребрами Т1, е2 {8,10}.
Т3 = Т2 + е3, де е3 = {7,9}.
Т4 = Т3 + е4, де е4 = {1,2}.
Т5 = Т4 + е5, де е5 = {1,3}.
Т6 = Т5 + е6, де е6 = {5,6}.
Т7 = Т6 + е7, де е7 = {4,8}.
Т8 = Т7 + е8, де е8 = {9,12}
Т9 = Т8 + е9, де е9 = {2,4}.
Т10 = Т9 +е10, де е10 = {6,7}.
Т11 = Т10 + е11, де е11 = {11,12}.
Знайдено мінімальне дерево покриття зваженого графа, отже, знайдена і оптимальна структура мережі, де загальна вартість витрачена на прокладку комунікацій складе:
І це мінімальна сума витрат з усіх можливих. При прокладанні комунікаційної мережі, що з'єднує всі дані пункти затрачається 200 у.е.
Рис. 2. Розв'язання задачі про оптимальну структуру мережі
Комунікації прокладуть між наступними пунктами: аптека - кафе - завод №2 - магазин №1 - завод №1 - хлібозавод - магазин №2 - продуктовий магазин - взуттєва фабрика - магазин №3 - торговий центр.
2.2 Застосування алгоритму Дейкстри
Фірмі, що займається перевезенням швидкопсувних товарів, необхідно доставити товар з Суйфеньхе в Хабаровськ, причому маршрутів, за якими можна провести доставку декілька. Відстань між Суйфеньхе і містом 2 становить 15 км, між Суйфеньхе і містом 3 - 20 км, між Суйфеньхе і містом 11 - 85 км. Між містом 2 і містом 4 - 25 км, між містом 2 і містом 7 - 65 км. Між містом 3 і містом 5 становить 5 км, між містом 3 і містом 8 - 50 км. Між містом 4 і містом 8 - 20 км. Між містом 5 і містом 6 - 20 км. Між містом 6 і містом 7 - 25 км, між містом 6 і містом 8 - 35 км. Між містом 7 і містом 9 - 15 км, між містом 7 і містом 10 - 40 км. Між містом 9 і містом 12 - 20 км. Між містом 10 і містом 11 - 30 км, між містом 10 і містом 12 - 45 км. Між містом 11 і містом 12 - 25 км. Потрібно знайти найкоротший шлях з Суйфеньхе в Хабаровськ.
Будується граф G, в якому місто Суйфеньхе позначається цифрою 1, Хабаровськ - 12. Інші пункти маршруту позначаються цифрами 2, 3, 4, 5, 6, 7, 8, 9, 10, 11. Кожному ребру графа зіставляється число, яке буде дорівнювати віддалі між пунктами. Потрібно знайти мінімальний маршрут. Алгоритм Дейкстри знаходить найкоротший шлях між двома вершинами в графі. Отже, можна скористатися ним, при розв'язанні даного економічного завдання.
Рис. 3. Графічна інтерпретація задачі про знаходження мінімального маршруту доставки
Якщо вершина v лежить на найкоротшому шляху від початкової вершини до кінцевої, то T [v] - довжина найкоротшого шляху від початкової вершини до кінцевої.
За допомогою алгоритму Дейкстри знаходиться єдиний мінімальний маршрут, що з'єднує вершини 1та 12 графа G (Рис. 3.).
Нехай вершина номер 1 - початкова вершина. Для неї призначається постійний ярлик L (к) = 0. Кінцевою вершиною вважатиметься вершина номер 1. Розглядаються вершини, суміжні з вершиною 12, і призначимо їм тимчасові ярлики: L (2) = 25, L (3) = 20, L (11) = 85.
Потрібно вибирати вершину з найменшим ярликом - це вершина номер 3, і її ярлик L (3) = 20 стає постійним.
Повторюючи цей процес для вершини номер 3, вершинам присвоюються тимчасові ярлики: L (5) = 5, L (8) = 50.
Серед усіх тимчасових ярликів мінімальний буде у L (5) = 5. Цей ярлик стає постійним.
З вершиною 5 суміжно тільки вершина 6. L (6) = 20.
Повторюючи цей процес для вершини номер 6, вершинам присвоюються тимчасові ярлики: L (7) = 25, L (8) = 35.
Серед усіх тимчасових ярликів мінімальний буде у L (7) = 25. Цей ярлик стає постійним.
Повторюючи процес, розглядаються вершини, суміжні з вершиною 7. Це 2, 9 і 10. Для яких тимчасові ярлики будуть: L (2) = 65, L (9) = 15, L (10) = 40. Знаходиться найменший тимчасовий ярлик. Він буде у: L (9) = 20.
З вершиною 9 суміжно тільки вершина 12. L (12) = 20.
Тепер, коли дерево сформовано, ми можемо визначити найкоротший шлях від 1 до 12. Цей шлях дерева, що з'єднує вершини 1 і 12. І він проходить через вершини 3, 5, 6, 7 і 9. Довжина цього шляху - L (v ') = 20 + 5 + + 20 + 25 + 15 + 20 = 105 (км.).
Мал. 3. Розв'язання задачі про знаходження мінімального маршруту доставки
Маршрут з міста Суйфеньхе в Хабаровськ, при якому час доставки товару буде найменшим, включає місто 3, місто 5, місто 6, місто 7 і місто 9. Довжина маршруту складе 105 кілометрів.
2.3 Задача комівояжера
Комівояжер бажає відвідати 6 міст. Вони з'єднані мережею доріг.
Відстань між містом 1 і містом 2 становить 6 км, між містом 1 і містом 3 - 7 км, між містом 1 і містом 4 - 20 км, між містом 1 і містом 5 - 12 км, між містом 1 і містом 6 - 10 км . Відстань між містом 2 і містом 3 становить 5 км, між містом 2 і містом 4 - 7 км, між містом 2 і містом 5 - 9 км, між містом 2 і містом 6 - 16 км. Відстань між містом 3 і містом 4 становить 4 км, між містом 3 і містом 5 - 10 км, між містом 3 і містом 6 - 12 км. Відстань між містом 4 і містом 5 становить 3 км, між містом 4 і містом 6 - 15 км. Відстань між містом 5 і містом 4 становить 6 км, між містом 5 і містом 6 - 4 км, між містом 6 і містом 3 - 11 км, між містом 6 і містом 5 - 21 км. Комівояжер повинен відвідати всі 6 міст по одному разу, повернувшись в той, з якого почав. Потрібно знайти такий маршрут руху, при якому сумарна пройдена відстань буде мінімальна. Дану задачу можна розв'язати угорським методом, методом досконалого паросполучення. Для цього потрібно побудувати матрицю А, отображаючу довжину між містами: aij - відстань від міста i до міста j (i ?j), якщо i = j, то ставиться ? , так як дороги не існує.
Будується наведена матриця з метою отримання в кожному рядку і стовпці, не менше одного найкоротшого маршруту (нульового наведеного значення). Для цього в кожному рядку матриці А від кожного елемента віднімається значення мінімального елемента цього рядка:
Обчислюється коефіцієнт приведення, який дорівнює сумі всіх мінімальних елементів матриці А, які вичитали з рядків і стовпців:
Кпр = 6 +5 + 4 + 3 + 4 + 10 = 32
Обчислюються коефіцієнти значущості для кожного елемента, де aij - елементи наведеної матриці.
К12 = 1 + 1 = 2
К23 = 2
К34 = 1 + 2 = 3
К45 = 2
К56 = 2 + 4 = 6
З наведеної матриці потрібно викреслити рядок і стовпець, містять елемент з максимальним коефіцієнтом значущості. В даному випадку таким елементом є А56: коефіцієнт значущості дорівнює 6. Для елемента А56 встановимо значення 1: а56 = 1.
Коефіцієнт значущості:
К12 = 2
К23 = 2
К45 = 5
К61 = 2
К34 = 3
а45 = 1
Коефіцієнт значущості:
К12 = 2
К61 = 2
К34 = 3
К23 = 2
а45 = 1
Коефіцієнт значущості:
К12 = 7
К61 = 7
К23 = 2
а12 = 1
а61 = 1
а23 = 1
Таким чином, в маршрут увійшли ребра: {5,6}, {4,5}, {3,4}, {1,2}, {6,1}, {2,3}. Все вершини (міста) з'єдналися. Довжина маршруту складає
П= w({5,6}) + w({4,5}) + w({3,4}) +w({1,2}) + w({2,3}) = 4 + 3 + 4 + 6 + 10 + 5 = 32.
Шлях комівояжера включає відстані між містами {1,2},{2,3},{3,4},{4,5},{5,6},{6,1}, і має довжину 32.
Висновки
логічний дискретний математика граф
В цій роботі були розглянуті такі розділи дискретної математики як застосування математичної логіки, теорії графів. Було розглянуто на конкретних прикладах, як алгоритми дискретної математики застосовуються у сфері економіки, зокрема, при вирішенні проблеми вибору з декількох альтернатив.
У першій частині курсової роботи було розглянуто застосування методів дискретної математики та математичного моделювання в економіці і математичній логіці, де розглядаються логічні операції і перетворення логічних функцій, приведення функцій до діз'юнктівной і кон'юнктівной нормальній формі, побудова таблиці істинності, знаходження полінома Жегалкина для заданої функції і її похідних по одній і двох змінним.
У другій частині на конкретних прикладах розглядається практичне застосування теорії графів в економіці. Були вирішені економічні задачі з використанням таких алгоритмів, як «жадібний» (алгоритм Краскала) і алгоритму Дейкстри. Складені математичні моделі даних алгоритмів. За допомогою угорського методу, було отримано рішення для задачі комівояжера. У всіх цих завданнях потрібно знайти оптимальний (в даному випадку мінімальний) маршрут. Більшість понять, що викладаються в даному розділі, широко відомі, бо графи, завдяки своїй наочності і універсальності стали використовуватися в економіці. Теорія графів широко застосовується при вирішенні задач управління виробництвом та економікою в цілому.
Література
1. Галкина В.А. Дискретная математика: комбинаторные методы оптимизации. - М. : Наука, 2003. -232 с.
2. Іванов Б.Н. Дискретна математика. Алгоритми і програми. Розширений курс / Б.М. Іванов. - М. : Известия, 2011. - 512 c.
3. Канцедал С.А. Дискретна математика: Навчальний посібник / С.А. Канцедал. - М. : ИД ФОРУМ, НДЦ ИНФРА-М, 2013. -224 c.
4. Просветов Г.І. Дискретна математика: завдання і рішення. Навчально-практичний посібник / Г.І. Присвятив. -М .: Альфа-Пресс, 2013. -240 c.
5. Тюрін С.Ф. Дискретна математика: Практична дискретна математика і математична логіка. Навчальний посібник / С.Ф. Тюрін, Ю.А. Аляев. -М .: ФиС, ИНФРА-М, 2012. -384 c.
6. Хаггард Г. Дискретна математика для програмістів. Навчальний посібник / Г. Хаггард, Д. Шліпф, С. Уайтсайдс; Пер. з англ. Н.А. Шихова; Під ред. А.А. Сапоженков. -М. : БИНОМ. ЛЗ, 2012. -627 c.
7. Яблонский С.В. Введение в дискретную математику: учеб. пособие / Под ред. В.А. Садовничего. - 3-е изд.; стер. - М.: Высшая школа, 2001. - 384 с.
Размещено на Allbest.ru
...Подобные документы
Зразки вирішення задач по дискретній математиці. Обчислювання череди функцій універсальних множин методами дискретної математиці. Визначення ймовірності послідовного вибору з колоди певних карт. Використання відомих алгоритмів для обчислення шляхів графа.
контрольная работа [42,1 K], добавлен 22.10.2009Суть принципу Діріхле та найпростіші задачі, пов’язані з ним. Використання методів розв’язування математичних задач олімпіадного характеру при вивченні окремих тем шкільного курсу математики та на факультативних заняттях. Індукція в геометричних задачах.
дипломная работа [239,7 K], добавлен 15.03.2013Фінансова математика на кредитно-депозитному банківському та страховому ринку. Аналіз практичного застосування методів фінансової математики на фінансових ринках України. Умови вкладів з щомісячним нарахуванням відсотків. Рівні показників інфляції.
дипломная работа [288,9 K], добавлен 16.06.2013Задачі обчислювальної математики. Алгоритми розв'язування багатьох стандартних задач обчислювальної математики. Обчислення інтерполяційного полінома Лагранжа для заданої функції. Виконання обчислення першої похідної на основі другої формули Ньютона.
контрольная работа [67,1 K], добавлен 27.03.2012Теорія графів та її використання у різних галузях. У фізиці: для побудови схем для розв’язання задач. У біології: для розв’язання задач з генетики. Спрощення розв’язання задач з електротехніки за допомогою графів. Математичні розваги і головоломки.
научная работа [2,1 M], добавлен 10.05.2009Методика викладання теми, що стосується графічних методів розв’язування задач з параметрами. Обережне відношення до фіксованого, але невідомого числа при роботі з параметром. Побудова графічного образу на координатній площині, застосування похідної.
дипломная работа [7,5 M], добавлен 20.08.2010Вивчення методів розв'язання лінійної крайової задачі комбінуванням двох задач Коші. Переваги та недоліки інших методів: прицілювання, колокацій, Гальоркіна, найменших квадратів та ін. Пошук єдиного розв'язку звичайного диференціального рівняння.
курсовая работа [419,2 K], добавлен 29.08.2010Системи лінійних рівнянь з двома змінними з параметром. Тригонометричні рівняння та системи тригонометричних рівнянь з параметрами. Лінійні та квадратні нерівності. Застосування графічних методів паралельного переносу в розв’язанні задач з параметрами.
дипломная работа [1,3 M], добавлен 16.06.2013Історія виникнення лабіринту. Лабіринт крітського царя Міноса - одне із семи чудес світу. Перші здогади "Правило руки". Лабіринти і замкнені криві, розв'язування різних лабіринтних задач, застосування елементів теорії графів і теорії ймовірностей.
реферат [7,3 M], добавлен 29.09.2009Лінійні, квадратичні та кубічні В-сплайни. Отримання форми запису сплайнів, виведення формул для розрахунків інтерполяційних задач. Застосування кубічних В-сплайнів в математичній теорії і обчислювальних задачах. Практичність вивчення кубічних В-сплайнів.
контрольная работа [678,5 K], добавлен 20.11.2010Дослідження предмету і сфери застосування математичного програмування в економіці. Класифікація задач цієї науки. Загальна задача лінійного програмування, деякі з методи її розв’язування. Економічна інтерпретація двоїстої задачі лінійного програмування.
курс лекций [59,9 K], добавлен 06.05.2010Задача Коші і крайова задача. Двоточкова крайова задача для диференціального рівняння другого порядку. Види граничних умов. Метод, заснований на заміні розв’язку крайової задачі розв’язком декількох задач Коші. Розв'язування систем нелінійних рівнянь.
презентация [86,2 K], добавлен 06.02.2014Використання методів розв’язування одновимірних оптимізаційних задач (метод дихотомії, золотого перерізу, Фібоначі) для визначення найменшого значення функції на відрізку. Задача мінімізації за допомогою методу Ньютона і методу найшвидшого спуску.
курсовая работа [739,5 K], добавлен 05.05.2011Побудування графа та матриці інцидентності. Перетворення графа у зважений за допомогою алгоритму Дейкстри, знаходження довжини найкоротшого шляху між двома вершинами та побудування дійсного шляху. Обхід дерева у прямому та зворотному порядках.
курсовая работа [144,1 K], добавлен 03.07.2014Застосування методів математичного аналізу для знаходження центрів мас кривих, плоских фігур та поверхонь з використанням інтегральних числень функцій однієї та кількох змінних. Поняття визначеного, подвійного, криволінійного та поверхневого інтегралів.
курсовая работа [515,3 K], добавлен 29.06.2011Неперервність функцій в точці, області, на відрізку. Властивості неперервних функцій. Точки розриву, їх класифікація. Знаходження множини значень функції та нулів функції. Розв’язування рівнянь. Дослідження функції на знак. Розв’язування нерівностей.
контрольная работа [179,7 K], добавлен 04.04.2012Поняття математичної та арифметичної задачі, ступені у навчанні розв’язування. Аналіз системи математичних задач, які вивчаються в початкових класах. Математична задача як засіб активізації учіння. Індивідуальний підхід до дитини і диференціація завдань.
курсовая работа [46,9 K], добавлен 25.12.2014Розгляд теоретичних основ рівнянь з параметрами. Основні види даних рівнянь. Аналітичний та графічний методи розв’язування задач із використанням формул, властивостей функцій. Ознайомлення із системою розв’язування задач з параметрами для 9 класу.
курсовая работа [605,9 K], добавлен 29.04.2014Розв'язання системи лінійних рівнянь методом повного виключення змінних (метод Гаусса) з використанням розрахункових таблиць. Будування математичної моделі задачі лінійного програмування. Умови для застосування симплекс-методу. Розв'язка спряженої задачі.
практическая работа [42,3 K], добавлен 09.11.2009Ознайомлення з нестандартними методами рішення рівнянь і нерівностей. Відомості з історії математики про рішення рівнянь. Розгляд та застосування на практиці методів рішення рівнянь і нерівностей, заснованих на використанні властивостей функції.
дипломная работа [1,4 M], добавлен 26.01.2011
