85943 (612612), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

2. Применение теории графов

2.1 Практическое применение жадного алгоритма

На территории некого города N размещены заводы и магазины, в которые поставляется продукция с этих заводов. В результате разработки были определены возможные трассы для прокладки коммуникаций и оценена стоимость их создания для каждой трассы. Стоимость прокладки коммуникаций для трассы между заводом №1 и магазином удобрений составляет 15 у.е., между заводом №1 и заводом №3 – 85 у.е., между заводом №1 и хлебозаводом – 20 у.е. Между магазином №1 и заводом №2 составит 25 у.е., между магазином №1 и обувной фабрикой – 65 у.е. Стоимость прокладки коммуникаций для трассы, соединяющей хлебозавод и магазин №2 - 5 у.е., между хлебозаводом и кафе – 50 у.е., между заводом №2 и кафе - 20 у.е., между магазином №2 и продуктовым магазином - 20 у.е., между продуктовым магазином и обувной фабрикой - 25 у.е, между продуктовым магазином и кафе – 35 у.е., между обувной фабрикой и магазином №3 - 15 у.е, между обувной фабрикой и аптекой – 40 у.е., между кафе и аптекой - 10 у.е., между магазином №3 и торговым центром - 20 у.е., между аптекой и заводом №3 составит 30 у.е, между аптекой и торговым центром – 45 у.е., между заводом №3 и торговым центром, - 25 у.е. Необходимо, чтобы коммуникации связали все объекты, затраты на прокладку данных коммуникаций должны быть минимальны.

Для удобства записи вводятся следующие обозначения:

V₁ – завод №1, V₂ – магазин №1, V₃ – хлебозавод, V₄ –завод №2, V₅ – магазин №2 V₆ –продуктовый магазин, V₇ – обувная фабрика, V₈ –кафе, V₉ – магазин №3, V₁₀ – аптека, V₁₁ –завод №3, V₁₂ – торговый центр.

Если создать графическую интерпретацию данной модели, то видно что получился граф с 12 вершинами и 18 ребрами.

Рисунок 1– Графическая интерпретация задачи о оптимальной структуре сети

Из вышесказанного следует, что данную экономическую задачу можно решить с помощью теории графов. Требуется найти дерево покрытия минимального веса. Задача решается с помощью разновидности «жадного» алгоритма, алгоритма Краскала.

Пусть имеется конечное множество Е, |E|=18, весовая функция w: ER⁺ и семейство ℇ⊂ 2^Е. Требуется найти ХЕ, такое что :

Пусть Е – непустое конечное множество, w: ER⁺ - функция, ставящая в соответствие каждому элементу е этого множества неотрицательное действительное число w(e) – вес элемента е. Для Х Е вес w(Х)определим как сумму весов всех элементов множества Х:

где

Другими словами, необходимо выбрать в данном семействе непустое подмножество наименьшего веса.

Сопоставим каждому пункту сети вершину графа G. А каждому ребру этого графа сопоставим число, равное стоимости строительства соответствующей коммуникации: (рисунок 1).

Примером жадного алгоритма служит алгоритм Краскала /3/.

Существует теорема, которая утверждает, что алгоритм Краскала всегда приводит к ребру, имеющему минимальный вес.

Согласно алгоритму Краскала, выбирается ребро минимального веса. В данном случае это будет ребро е₁ = {3,5}, получаем граф Т₁.

Строится граф Т₂ = Т₁ + е₂, где е₂ - ребро, имеющее минимальный вес среди ребер, не входящих в Т₁ и не составляющий циклов с ребрами Т₁, е₂ {8,10}.

Т₃ = Т₂ + е₃, где е₃ = {7,9}.

Т₄ = Т₃ + е₄, где е₄ = {1,2}.

Т₅ = Т₄ + е₅, где е₅ = {1,3}.

Т₆ = Т₅ + е₆, где е₆ = {5,6}.

Т₇ = Т₆ + е₇, где е₇ = {4,8}.

Т₈ = Т₇ + е₈, где е₈ = {9,12}

Т₉ = Т₈ + е₉, где е₉ = {2,4}.

Т₁₀ = Т₉ +е₁₀, где е₁₀ = {6,7}.

Т₁₁ = Т₁₀ + е₁₁, где е₁₁ = {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/. Следовательно, можно воспользоваться им, при решении данной экономической задачи.

Рисунок 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 (км.).

Рисунок 4 - Решение задачи о нахождении минимального маршрута доставки

Маршрут из города Суйфэньхе в Хабаровск, при котором время доставки товара будет наименьшим, включает город 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 городов по одному разу, вернувшись в тот, с которого начал. Требуется найти такой маршрут движения, при котором суммарное пройденное расстояние будет минимальным

Данную задачу можно решить венгерским методом, методом совершенного паросочетания. Для этого требуется построить матрицу А, отображающую длину между городами: a_ij – расстояние от города i до города j (i ≠j), если i = j, то ставится ∞ ,так как дороги не существует.

Строится приведенная матрица с целью получения в каждой строке и столбце не меньше одного кратчайшего маршрута (нулевого приведенного значения). Для этого в каждой строке матрицы А от каждого элемента отнимается значение минимального элемента этой строки:

Вычисляется коэффициент приведения, равный сумме всех минимальных элементов матрицы А, которые вычитали из строк и столбцов:

К_пр = 6 +5 + 4 + 3 + 4 + 10 = 32

Вычисляются коэффициенты значимости для каждого занулившегося элемента, где a_ij – элементы приведенной матрицы.

К₁₂ = 1 + 1 = 2

К₂₃ = 2

К₃₄ = 1 + 2 = 3

К₄₅ = 5 К₆₁ = 2

К₅₆ = 2 + 4 = 6

Из приведенной матрицы нужно вычеркнуть строку и столбец, содержащие элемент с максимальным коэффициентом значимости. В данном случае таким элементом является а₅₆: коэффициент значимости равен 6. Для элемента а₅₆ установим значение1: а₅₆ = 1.

Коэффициент значимости:

К₁₂ = 2

К₂₃ = 2

К₄₅ = 5

К₆₁ = 2

К₃₄ = 3

5) а₄₅ = 1

Коэффициент значимости:

К₁₂ = 2

К₆₁ = 2

К₃₄ = 3

К₂₃ = 2

а₄₅ = 1

Коэффициент значимости:

К₁₂ = 7

К₆₁ = 7

К₂₃ = 2

а₁₂ = 1, а₆₁ = 1

а₂₃ = 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.

3. Практическое применение теории нечетких множеств

Под конкурентоспособностью понимают комплекс потребительских, стоимостных и социальных характеристик товара (изделия), определяющих его успех на данном рынке, т. е. способность данного товара быть обмененным на деньги на конкретном рынке в условиях широкого предложения к обмену других товаров-аналогов. Конкурентоспособность — это степень соответствия совокупности свойств объекта ценностной системе рынка. Границы понятия конкурентоспособность непрерывно расширяются, переходя от конкурентоспособности изделия к конкурентоспособности предприятий и даже государств. Конкурентоспособность обеспечивается высоким технологическим уровнем и качеством, соответствием требованиям и стандартам стран-импортеров, фирм-покупателей, высоким уровнем технологического обслуживания, патентной чистотой и патентной защитой, приемлемой ценой, льготными условиями платежа и т. д. Фирме, занимающейся реализацией компьютеров, необходимо из шести предложенных марок ноутбуков ASUS L8400, ASUS T9, FUJITSU – SIEMENS LIFEBOOK B, IRU NOVIA 1012DVD, COMPAQ EVO N610C, INTEL JS2310 выбрать модель с оптимальным набором характеристик (дисплей с большим количеством точек, процессор с высокой тактовой частотой, большой объем оперативной памяти, жесткий диск с большим объемом памяти, долгий срок автономной работы, маленький вес, низкая стоимость, большой гарантийный срок ). Известно, что ноутбук ASUS L8400 обладает следующими качествами: дисплей 14.5 точек, процессор 1 ГГц, память 256 Мбайт, жесткий диск 20 Гбайт, привод DVD-ROM, время автономной работы 2,7 часа, вес 2.9 кг, цена 1.5 тыс. долларов США, гарантийный срок 3 года. Ноутбук ASUS T9 обладает следующими качествами: дисплей 14.1 точек, процессор 0.8 ГГц, память 128 Мбайт, жесткий диск 15 Гбайт, привод DVD-ROM, время автономной работы 2.5 часа, вес 2.1кг, цена 1.16 тыс. долларов США, гарантийный срок 2 года. Ноутбук FUJITSU–SIEMENS LIFEBOOK B: дисплей 10.4 точек, процессор 0.7 ГГц, память 256 Мбайт, жесткий диск 30 Гбайт, привод CD-RW, время автономной работы 2.4 часа, вес 1.6кг, цена 2 тыс. долларов США, гарантийный срок 2.5 года. Ноутбук IRU NOVIA 1012DVD: дисплей 12.0 точек, процессор 1.06 ГГц, память 128 Мбайт, жесткий диск 20 Гбайт, привод DVD-CDRW, время автономной работы 2.5 часа, вес 1.7 кг, цена 1.48 тыс. долларов США, гарантийный срок 1 год. Ноутбук COMPAQ EVO N610C: дисплей 14.0 точек, процессор 1.6 ГГц, память 256 Мбайт, жесткий диск 40 Гбайт, привод DVD-CDRW, время автономной работы 2.4 часа, вес 2.1 кг, цена 2 тыс. долларов США, гарантийный срок 3 года. Ноутбук INTEL JS2310: дисплей 14.0 точек, процессор 1.12 ГГц, память 256 Мбайт, жесткий диск 25 Гбайт, привод CD-RW, время автономной работы 2.5 часа, вес 1.9 кг, цена 1.37 тыс. долларов США, гарантийный срок 1 год. Данная задача может быть решена с помощью метода нечеткого отношения предпочтения /3/. Задачу выбора определенной марки ноутбука с учетом наиболее важных критериев качества рассмотрим на примере анализа альтернатив: a₁ – ASUS L8400, a₂ – ASUS T9, a₃ – FUJITSU–SIEMENS LIFEBOOK B, a₄ – IRU NOVIA 1012DVD, a₅ - COMPAQ EVO N610C, a₆ – INTEL JS2310. Для оценки альтернатив используем девять критериев качества, где, на основе данных об основных характеристиках ноутбуков задаются множества значений, которые могут принимать различные характеристики: F₁- дисплей (от 10 до 15 тыс. точек.), интерес представляет дисплей с большим количеством точек; F₂- процессор (от 0,6 до 1,7 ГГц), предпочтение отдается процессору с большей тактовой частотой; F₃- память (от 120 до 300 Мбайт), интерес представляет ноутбук с большим объемом памяти; F₄- жесткий диск (от 10 до 45 Гбайт), предпочтение отдается жесткому диску с большим объемом памяти; F₅- привод (от 1 до 10 баллов), предпочтение составляет большее количество баллов; F₆- время автономной работы (от 2 до 3,5 часов), предпочтительнее большее количество часов автономной работы; F₇- вес (от 1 до 3 кг), интерес составляет ноутбук с меньшим весом; F₈- стоимость (от 1 до 3 тыс. долларов США), предпочтение отдается ноутбуку с меньшей ценой;

Характеристики

Список файлов курсовой работы