Алгоритм Дейкстра

Kпр=6+3 =9.

A3=
Далее повторяем шаг б:

К₂₁=1; K₂₆=2; K₃₄=2; K₄₃=1; K₅₃=0; K₅₄=0; K₆₂=3.
Следующим ребром, которое будет включено в граф – это K₆₂=3
Повторяем шаг а
A4= A5=

Получаем Kпр=11

Повторяем шаг б:
K21=2; K34=0; K36=3; K43=3; K53=0; K54=0
Получаем, что будет включено ребро K36=3

A6=

Добавляем к графу ребро K21=2

A7=
В ходе решения задачи были выделены элементы матрицы:

К_{1,5 ,} К_6,2, К_{3,6 ,} К_{2,1 ,} К_{5,4 ,}К_4,3, которым соответствуют ребра (1-5), (6-2), (3-6), (2-1), (5-4), (4-3) с весами 3, 3, 3, 2.
Длина маршрута равна 11, что совпадает с суммой всех коэффициентов приведения: 6 + 3 + 2 = 11. Построим граф (рисунок 8) и, если все вершины соединились, следовательно, задача было решена правильно.
Рисунок 8- Результирующий граф

3 Нечеткие множества

Анализу подлежат ряд современных моделей принтеров относящихся к классу не дорогостоящих, для этого воспользуемся многокритериальным выбором альтернатив на основе нечёткого отношения предпочтения. /6/
Модели принтеров, которые будут подлежать анализу.
A1 – Canon S900 ; A2 – EPSON Stylus Photo 830; A3 – Hewlett Packard DeskJet 6122 ; A4 – Lexmark Z65; A5 – Lexmark Z90.
F1 - качество печати (8-10) – чем лучше качество печати, тем больше бал. Также определяются F2,F3,F4,F5,F6,F7,F8.
F2 – скорость печати (6-10)
F3 – удобство в использовании (8-10)
F4 – аксессуары (7-9)
F5 – оправданность цены (6-10)
F6 – дизайн (7-10)
F7 – поддержка USB 2.0 (0-1)
F8 – шумность при работе (6-9)
F9,F10 – чем меньше цена тем больше спрос
F9 - стоимость картриджей (600-1103)
F10 - стоимость принтера (3600-4700)
Рассмотрим характеристики каждого принтера по критериям в задаче.
A1:F1=8,F2=7,F3=8, F4=8, F5=7, F6=9, F7=0, F8=9,F9=600, F10=4700
A2:F1=9, F2=6, F3=8, F4=9, F5=8, F6=7, F7=1, F8=7, F9=900, F10=4700
A3:F1=8,F2=9,F3=10,F4=10,F5=9,F6=9,F7=1, F8=9, F9=1103, F10=3900
A4:F1=8,F2=8,F3=9, F4=7, F5=7, F6=8, F7=1, F8=6, F9=1103, F10=5000
A5:F1=8,F2=6,F3=8, F4=7, F5=8, F6=7, F7=8, F8=6, F9=1100, F10=4700
Рассмотрим график зависимости функции принадлежности от качества печати.







Рисунок 6 – Качество печати Рисунок 7 – Скорость печати


Рисунок 8 – Удобство в использовании Рисунок 9 – Аксессуары
Рисунок 10 – оправданность цены Рисунок 11 - Дизайн
Рисунок 12 – Поддержка USB2.0 Рисунок 13 – уровень шума
Рисунок 14 – Стоимость картриджа Рисунок 15 – Стоимость принтера
На основании рисунков можно составить µFn
µF1 = {1/10; 0,8/9; 0,6/8; 0,6/8; 0,6/8}.
µF2 = {0,4/7; 0,2/6; 0,8/9; 0,6/8; 0,2/6}
µF3 = {0,6/8; 0,6/8; 1/10; 0,8/9; 0,6/8}
µF4 = {0,6/8, 0,8/9; 1/10; 0,4/7; 0,4/7}
µF5 = {0,4/7; 0,6/8; 0,8/9; 0,4/7; 0,6/8}
µF6 = {0,8/9; 0,4/7; 0,8/9; 0,6/8; 0,4/7}
µF7 = {0,8/0; 1/1; 1/1; 1/1; 1/1; 0,8 }
µF8 = {0,8/9; 0,6/7; 1/9; 0,4/6; 0,4/6}
µF9 = {1/600; 0,6/900; 0,8/800; 0,2/1103; 0,2/1100}
µF10 = {1/3600; 0,4/4700; 0,6/3900; 0,2/5000, 0,4/4700}
По этим данным составим матрицы нечётких отношений предпочтения R₁, …, R_n (R₅).

1	1,02	0,4	0,4	0,4
0	1	0,2	0,2	0,2
0	0	1	0	0
0	0	0	1	0
0	0	0	0	1

1	0,2	0	0	0,2
0	1	0	0	0
0,4	0,6	1	0,2	0,6
0,2	0,4	0	1	0,4
0	0	0	0	1

R1=

1	0	0	0	0
0	1	0	0	0
0,4	0,4	1	0,2	0,4
0,2	0,2	0	1	0,2
0	0	0	0	1

1	0	0	0,2	0,2
0,2	1	0	0,4	0,4
0,4	0,2	1	0,6	0,6
0	0	0	1	0
0	0	0	0	1

1 0,4 0 0,2 0,4 0 1 0 0 0 0 0,4 1 0,2 0,4 0 0,2 0 1 0,2 0 0 0 0 1 1 R2= R6= R7= R8= R9= R3= R4= R10= R5=	0	0	0	0
0,2	1	0	0	0,2
0,2	0	1	0	0,2
0,2	0	0	1	0,2
0	0	0	0	1

1 0 0 0 0 0,2 1 0 0 0,2 0,2 0 1 0 0,2 0,2 0 0 1 0,2 0 0 0 0 1 1	0,2	0	0,4	0,4
0	1	0	0,2	0,2
0,2	0,4	1	0,6	0,6
0	0	0	1	0
0	0	0	0	1

1	0,6	0,4	0,8	0,6
0	1	0	0,2	0
0	0,2	1	0,4	0,2
0	0	0	1	0
0	0	0	0,2	1

1	0,4	0,2	0,8	0,8
0	1	0	0,4	0,4
0	0,2	1	0,6	0,6
0	0	0	1	0
0	0	0	0	1

Строим нечёткое отношение Q₁:

Q₁=F₁ F₂ … F_5, получаем матрицу

По экспертной оценке было определена степень важности всех критериев:
W1=0,25; W2=0,19; W3=0,03; W4=0,06; W5=0,095 ; W6=0,02 ; W7=0,02; W8=0,015
W9=0,15; W10=0,1

µ_Q2=1-max{0;0.11;-0.001;0.26;0.337}=0.663
µ_Q2=1-max{0;-0.11;-0.171;0.09;0.155} =0.845
µ_Q2=1-max{0;0.001;0.171;0.261;0.326}=0.674
µ_Q2=1-max{0;-0.26;-0.09;-0.261;0.065}=0.935
µ_Q2=1-max{0;-0.337;-0.155;-0.326;-0.065}=1

Результирующее множество недоминируемых альтернатив есть пересечение множеств μ_Q1^н.д. и μ_Q2^н.д.:

μ_Q1^н.д. μ_Q2^н.д.=||(1 1 1 1)  ( )||=|| ||
Следовательно, рациональным следует считать выбор альтернативы _i , имеющей максимальную степень недоминируемости.
Таким образом, с учетом всех перечисленных критериев и их относительной важности, наилучшим будет выбор принтера Lexmark Z90.

ЗАКЛЮЧЕНИЕ

В курсовой работе было рассмотрено три части дискретной математики, а именно применение ее на практике. Рассмотрены такие темы как математическая логика, графы, нечеткие множества. В первой части было рассмотрено применение дискретной математики в информатике, а именно применение ее в программировании, в построении схем и в криптографии. Также были рассмотрены применение математической логики на практическом примере: составлена таблица истинности, нахождение двух производных, конъюнктивная и дизъюнктивная нормальная функция, а также метод неопределенных коэффициентов для построения полинома Жегалкина. Во второй части рассматривается применение теории графов в экономических задачах, которые подразделяются на: алгоритм построения минимального остова, в результате чего были определены минимальные затрат на проезд от дома до супермаркета; Жадный алгоритм, где была решена задача о максимальной загруженности линий, которые соединяют нефтеперерабатывающие заводы с новым месторождением нефти; Алгоритм Дейкстра – задача о нахождении оптимального пути, нахождения минимальных затрат на обеспечение отдыха своим сотрудникам; Задача Коммивояжера – максимизация прибыли и уменьшения затрат времени. В третьей части рассмотрен метод многокритериального выбора альтернатив на основе нечёткого отношения предпочтения. Среди 5 анализируемых принтеров (Canon S900; EPSON Stylus Photo 830; Hewlett Packard DeskJet 6122 ; Lexmark Z65; Lexmark Z90) были определены более предпочтительный принтер из пяти предложенных принтеров, путем построения математической модели на основе метода многокритериального выбора. В результате чего был найден наиболее предпочтительный принтер (Lexmark Z90).



СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ:

1. 
   Воротников А.П., Практикум по введению в математическую логику.- СПб., 1986 – 300с.
   
2. 
   Новиков Ф.А., Дискретная математика для программистов. – СПб., 2002 – 302с.
   
3. 
   Новиков Ф.А., Введение в крипторафию. – СПб, 1993 – 190 с.
   
4. 
   Логинов Б.М., Лекции по дискретной математике. – Калуга, 1993 – 140с.
   
5. 
   Яблонский С.В., Введение в дискретную математику .-M.:Наука, 1996 – 200с.
   
6. 
   Методические указания по дискретной математике – 30с.