Рисунок 5 – Максимальное дерево покрытия Следовательно, получили результирующее максимальное

Применение дискретной в информатике
Рефераты >> Кибернетика >> Применение дискретной в информатике

Рисунок 5 – Максимальное дерево покрытия

Следовательно, получили результирующее максимальное дерево покрытия, вес которого равен сумме весов ребер, включенных в него:

Вес = 10+7+8+6+6+7=44

2.3 Построение минимального остова

В одном большом городе имеется один большой супермаркет(F) и существует множество дорог к нему. Известны затраты на проезд . Требуется найти путь с минимальными затратами.

Для решение этой задачи можно применить алгоритм минимального остова./6/

Алгоритм построения минимального остова: на первом этапе строим подграф, состоящий из двух вершин и ребра, их соединяющего, причем ребро должно быть минимального веса. Далее на каждом последующем этапе присоединяется ребро, обладающее минимальным весом среди рёбер, соединяющих уже построенный фрагмент минимального остова с вершинами, ещё не включенными во фрагмент.

Десять городов поставим в соответствие десяти вершинам графа a, b, c, d, e, f, g, h, i, j,. Цель обозначим F, а начало пути обозначим A.

Решением задачи будет следующая последовательность этапов:

1 этап (H-J), 2 этап: (I-g) , 3 этап: (h-i), 4 этап: (I-f), 5 этап: (g-d), 6 этап: (d-b), 7 этап:(b-a), 8 этап: (b-e). Выполнение алгоритма завешено, так как добавление ребер без образования петель невозможно. Осталось сложить веса ребер, составляющих подграф графа G, который образует минимальный остов. Эта сумма будет следующая: 2+7+4+6+5+7+6+6+4=47. В результате получаем, что существует один путь к F – это AIF и он равен = 10. Построив граф (рисунок 6), можно увидеть, что существует только единственный путь от начала нашего пути до указанной цели.

.

Рисунок 6 –Результирующий граф

2.4 Задача Коммивояжера

Предприятия(A) в целях увеличить свою прибыль решила открыть свои филиалы в 10 городах (B,C,D,E,F,G,I,H,J) и, чтобы минимизировать затраты и сэкономить время экономистам была поставлена задача найти минимальный путь и так чтобы все города были пройдены по одному разу.

Так как этот граф является Гальмитонов, то одним из способов решения будет решение при помощи Коммивояжера./6/

а) В матрице определяем минимальный элемент строки и вычитаем его из элементов соответствующей строки. Таким образом, получаем нулевой элемент в каждой строке. Далее определяем минимальный элемент столбца (не включая и нули) и вычитаем его из элементов соответствующего столбца (рисунок 2).

A1=

Подсчитываем Kпр=1+1+1+1+1+1=6.

б) Для каждого нулевого элемента определяются коэффициенты Кi,j по формуле 2.

(4)

К15=3; К26=3; К34=2; К43=2; К51=3; К62=3; К15=3

Выбираем наибольший из коэффициентов (К1,5=3). Следовательно, в наш гамильтонов граф будет включено ребро, соединяющее 1 и 5 вершины с весом 13. Далее вычеркиваем строку и столбец, соответствующие индексу

A2=

Повторяем шаг под буквой а и получаем:

Kпр=6+3 =9.

A3=

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

К21=1; K26=2; K34=2; K43=1; K53=0; K54=0; K62=3.

Следующим ребром, которое будет включено в граф – это K62=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)