Теория графов в моделировании экономических процессов

1. ТЕОРИЯ ГРАФОВ В МОДЕЛИРОВАНИИ ЭКОНОМИЧЕСКИХ ПРОЦЕССОВ

2. Граф

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

3. Теория графов

Леонард Эйлер

4. Жадный алгоритм

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

5. Пример

Стоимость
проведения
Пусть на территории
некоторого города N
размещены заводы,
которые поставляют
свою продукцию в
магазины. В
результате
разработки были
определены
возможные трассы
для прокладки
коммуникаций и
оценена стоимость
их создания для
каждой трассы
Первый объект
Второй объект
заводом №1
зоомагазином
20
магазином № 1
заводом №3
90
заводом №1
пекарней
25
хозяйственным магазином
заводом№2
30
хозяйственным магазином
текстильной фабрикой
70
пекарней
магазином канцтоваров
10
пекарней
кафе
55
заводом №2
кафе
25
магазином канцтоваров
продуктовым магазином
25
продуктовым магазином
текстильной фабрикой
30
текстильной фабрикой
магазином №3
у.е.
20
продуктовым магазином
кафе
40
текстильной фабрикой
аптекой
45
кафе
аптекой
15
магазином №3
торговым комплексом
25
аптекой
заводом №3
35
аптекой
торговым комплексом
50
заводом №3
торговым комплексом
30
коммуникаций,

6.

Необходимо, чтобы коммуникации
связали все объекты, но затраты на
прокладку данных коммуникаций
должны быть минимальными.
V1 - завод №1
V
5
-
магазин
V9 - магазин №3
канцтоваров
V2
-хозяйственный
магазин
V3 - пекарня
V6
-продуктовый
V10 - аптека
магазин
V7
-
текстильная
V11 -завод №3
фабрика
V4 -завод №2
V 8 -кафе
V12
комплекс
-
торговый

7. е1 = {3; 5} ребро, имеющее минимальный вес

Т2 = Т2 + е2, где е2 – ребро
Т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}.
ГЦ = Т10 + ец, где ец = {11; 12}.
общая стоимость
затраченная на
прокладку
коммуникаций

8. Коммуникации необходимо проложить между следующими пунктами

аптека
торговый комплекс
кафе
завод №2
магазин №3
хозяйственный магазин
текстильная фабрика
завод №1
пекарня
продуктовый магазин
магазин канцтоваров

9. Матрица смежности 

,
Формулы, используемые
для прямого счета,
следующие
Матрица смежности графа

10. Схема информационной модели

11. Экономические задачи

1) о соединении городов;
2) о кратчайшем маршруте;
3) о пропускной способности сети дорог;
4) о назначениях;
5) о выборе оптимальной стратегии поведения
в условиях неопределенности.