Файл: Экономикоматематические методы и модели.pdf

100
∑
(
)
, (5.16) при ограничениях:
1) ограничение на удовлетворение спроса на каждом этапе:
d
n

i
n-1
+ x
n
, n = 1, N ; (5.17)
2) установление объема запаса в конце n-го периода:
i
n
= i
n-1
+ x
n
– d
n
; n=1,N ; x
n
= 0, x
max
; i
n
= 0, i
max
. (5.18)
Выбор метода решения.
В изложенной задаче необходимо учитывать изменение моделируемого процесса во времени и влияние времени на критерий оптимальности. Для решения таких задач используется метод динамического планирования (ди- намическое программирование).
Определим основные компоненты и понятия:
1) этап - календарный период деятельности предприятия, n=1,N;
2) состояние - объем запасов i
n в конце n периода;
3) управление - планируемый объем производства x
n
на n-м периоде;
4) локальный доход - затраты на n-м этапе, связанные с хранением запа- сов и производством новой продукции С
n
(x
n
,i
n-1
);
5) оператор перехода – устанавливает связь между объемом запасов в конце n-1-го и n-го этапов: i
n
= i
n-1
+ x
n
– d
n
Введем функцию:
f
n
(i
n
) = min∑ С
n
(x
n
,i
n-1
) . (5.19)
Функциональное уравнение Беллмана для такой задачи:
f
n
(i
n
) = min(f
n
(i
n-1
) + С
n
(x
n
,i
n-1
)). (5.20)
Если
С
n
(x
n
,i
n-1
) = c
n
(x n
) + h
*
i
n-1
, (5.21) где c
n
(x
n
) – затраты на производство продукции на n-ном этапе в x n
объеме;
h
*
i
n-1
– затраты на хранение продукции на n-ном этапе в объеме i
0
Пусть известны c
0
(x
0
) - затраты на формирование начального запаса.
Тогда на шаге 1 принятия решения уравнение Беллмана (5.20) примет вид:
f
1
(i
1
) = min(f
1
(i
0
) + С
1
(x
1
,i
0
)) = min(f
1
(i
0
) + c
0
(x
0
) + h
*
i
0
) (5.22)
Все переменные в уравнении известны, а значит его можно решить.
На шаге n уравнение (5.20) имеет вид:
f
n
(i
n
) = min(f
n
(i
n-1
) + c
n
(x) + h
*
i
n-1
) (5.23)
Алгоритм решения задачи.
Электронный архив УГЛТУ

101
Для получения оптимального решения нам необходимо разработать ал- горитм решения уравнения Беллмана (5.12) на произвольном шаге принятия решения n.
Для этого целесообразно воспользоваться двумя таблицами. Заполнение таблицы 1 проводится так: столбцы – величина запаса с предыдущего шага, строки – объем производства на текущем этапе. Число столбцов ограничива- ется i
max
, а число строк x
max
. Клетка таблицы делится на две части. В одной части записываются значения состояния в конце текущего этапа (i
n
= i
n-1
+ x
n
– d
n
). Если i
n
< 0 ,то это недопустимое состояние, клетка вычеркивается из рассмотрения. Во второй части клетки записывается значение функции
f
n
(i
n
) = c
n-1
(x
n-1
) + c
n
(x
n
) + h
*
i
n-1
. (5.24)
Среди допустимых клеток находятся клетки с одинаковыми значениями состояний, и выбирается клетка, для которой функция f
n
(i
n
) минимальна, для нее фиксируется оптимальный объем производства. Эти результаты записы- ваются в таблицу 2.
Такие шаги повторяются N раз.
Для нахождения оптимальных объемов производства x
n и оптимальных уровней запасов i
n производится решение задачи в обратном порядке. На по- следнем этапе (n = N) из таблицы 2 выбирается x
n и i
n
, соответствующие оп- тимальной (минимальной) функции затрат f
n
(i
n
). На этапах n < N из таблицы 2 выбираются строки для которых x
n и i
n такие, что бы |d
n
– x
n+1
| = i
n
. Обратное решение задачи производится до этапа n = 1.
Электронный архив УГЛТУ

102
6. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
Как прикладная дисциплина теория графов позволяет описывать и ис- следовать многие технические, экономические, биологические и социальные системы
1
. Задача настоящего материала заключается в том, чтобы изложить основные понятия и результаты теории графов, необходимые для постановки и решения задач управления экономическими системами.
6.1. Основные понятия теории графов
Граф – система, которая интуитивно может быть рассмотрена как мно- жество вершин и множество соединяющих их линий (геометрический способ задания графа – на рис. 6.1). Например, атлас автодорог, где населенные пункты – кружки, а соединяющие линии – автодороги.
Кружки называются вершинами графа, линии со стрелками – дугами, без стрелок – ребрами. Граф, в котором направление линий не выделяется (все линии являются ребрами), называется неориентированным; граф, в котором направление линий принципиально (линии являются дугами) называется
ориентированным.
Рис.6.1. Образец графа
Исходя из теории множеств, можно дать следующее определение графа: задано конечное множество X, состоящее из n элементов (X = {1, 2, ..., n}), называемых вершинами графа, и подмножество V декартова произведения
X

X, то есть V
X
2
, множеством дуг. Тогда ориентированным графом G называется совокупность (X, V). Неориентированным графом называется со- вокупность множества X и множества неупорядоченных пар элементов, каждый из которых принадлежит множеству X.
1
Начало теории графов датируют 1736 г., когда Л. Эйлер решил популярную вто время «задачу о кенигсбергских мостах». Термин «граф» впервые был введен спустя
200 лет (в 1936 г.) Д. Кенигом.
Электронный архив УГЛТУ

103
Дугу между вершинами i и j, i, j є X, будем обозначать (i, j). Число дуг графа будем обозначать m (V = (v
1
, v
2
, ...,v
т
)).
Подграфом называется часть графа, образованная подмножеством вер- шин вместе со всеми ребрами (дугами), соединяющими вершины из этого множества. Если из графа удалить часть ребер (дуг), то получим частичный
граф.
Две вершины называются смежными, если они соединены ребром (ду- гой). Смежные вершины называются граничными вершинами соответствую- щего ребра (дуги), а это ребро (дуга) – инцидентным соответствующим вер- шинам.
Путем называется такая последовательность дуг (в ориентированном графе), когда конец одной дуги является началом другой дуги. Простой путь
– путь, в котором ни одна дуга не встречается дважды. Элементарный путь – путь, в котором ни одна вершина не встречается дважды. Контур – путь, у которого конечная вершина совпадает с начальной вершиной. Длиной пути
(контура) называется число дуг пути (или сумма длин его дуг, если послед- ние заданы).
Граф, для которого из (i, j) є V следует (j, i) є V называется симметриче- ским. Если из (i, j) V следует, что (j, i) V, то соответствующий граф назы- вается антисимметрическим.
Цепью называется множество ребер (в неориентированном графе), кото- рые можно расположить так, что конец (в этом расположении) одного ребра является началом другого. Другое определение: цепь – последовательность смежных вершин. Замкнутая цепь называется циклом. По аналогии с просты- ми элементарным путем, можно определить соответственно простые и эле-
ментарные цепь и цикл. Любой элементарный цикл является простым, об- ратное утверждение в общем случае неверно. Элементарная цепь (цикл, путь, контур), проходящая через все вершины графа называется гамильтоновой
цепью (соответственно – циклом, путем, контуром). Простая цепь (цикл, путь, контур), содержащая все ребра (дуги) графа называется эйлеровой це-
пью (соответственно – циклом, путем, контуром).
Если любые две вершины графа можно соединить цепью, то граф назы- вается связным. Если граф не является связным, то его можно разбить на связные подграфы, называемые компонентами.
Связностью графа называется минимальное число ребер, после удале- ния которых граф становится несвязным. Для ориентированных графов, если любые две вершины графа можно соединить путем, то граф называется силь-
но связным. Cвязность графа не может быть больше, чем [2m / n], где [x] – целая часть числа x; существуют графы с n вершинами и m ребрами, имею- щие связность [2m / n]; в сильно связном графе через любые две вершины проходит контур.
Электронный архив УГЛТУ

104
Связный граф, в котором существует эйлеров цикл, называется эйлеро-
вым графом.
В неориентированном графе степенью вершины i называется число d
i
инцидентных ей ребер. Очевидно, d
i
≤ n – 1, i
X. Граф, степени всех вершин которого равны n – 1, называется полным. Граф, все степени вершин которо- го равны, называется однородным.
Вершина, для которой не существует инцидентных ей ребер (d
i
= 0) называется изолированной. Вершина, для которой существует только одно инцидентное ей ребро (d
i
= 1) называется висячей.
Известно, что
∑
(данное выражение называется «леммой о ру- копожатиях» – поскольку в каждом рукопожатии участвуют две руки, то при любом числе рукопожатий общее число пожатых рук четно (при условии, что каждая рука учитывается столько раз, во скольких рукопожатиях она участво- вала)); в любом графе число вершин нечетной степени четно [13].
Связный граф является эйлеровым тогда и только тогда, когда степени всех его вершин четны (теорема Эйлера). Обозначим n
k
–число вершин, име- ющих степень k, k = 0,1,2,... Тогда:
∑
Для ориентированных графов для каждой вершины можно ввести два числа – полустепень исхода di
+
(число выходящих из нее вершин) и полусте- пень захода d
i
-
(число входящих в нее вершин). В дальнейшем, если не огово- рено особо, будем рассматривать графы без петель, то есть без дуг, у которых начальная и конечная вершины совпадают. Известно, что:
∑
∑
для эйлерова графа имеет место:
̅̅̅̅̅; эйлеров граф является объединением контуров, попарно не имеющих общих ребер.
Определим матрицу смежности графа как квадратную матрицу n

n, элемент a
ij
которой равен единице, если (i, j) єV, и нулю, если (i, j) є V, i, j
є X. Для неориентированного графа матрица смежности всегда симметриче- ская.
Определим матрицу инциденций для ребер графа как прямоугольную матрицу n m, элемент r
ij
которой равен единице, если вершина i инцидент- на ребру j, и нулю в противном случае, i = 1, … , n, j = 1, …, m. Аналогично определяется матрица инциденций для дуг графа – как прямоугольная мат- рица m

n, элемент r
ij
которой равен плюс единице, если дуга U
j
исходит из вершины i, минус единице, если дуга U
j
заходит в вершину i, и нулю в остальных случаях, i = 1,…, n, j = 1,…, m.
Деревом называется связный граф без простых циклов, имеющий не ме- нее двух вершин (дерево можно также понимать как связный граф, не содер- жащий связного частичного графа, состоящего из всех его вершин). Для де- рева m = n – 1, а число висячих вершин равно
∑ ( )
. Легко показать, что в дереве любые две вершины связаны единственной цепью.
Электронный архив УГЛТУ

105
Прадеревом называется ориентированное дерево, у которого одна из вершин, называемая корнем, не имеет заходящих дуг, а степени захода остальных вершин равны единице.
Плоским (планарным) называется граф, который можно изобразить на плоскости так, что различным вершинам соответствуют различные кружки и ни какие два ребра не имеют общих точек, отличных от их границ (не пере- секаются). Для плоского графа существует понятие грани – части плоскости, ограниченной ребрами и не содержащей внутри себя ни вершин, ни ребер.
Для простоты определения грани в дальнейшем в основном будем рассмат- ривать графы без висячих вершин. Например, дерево имеет всего одну внеш- нюю грань – всю плоскость. Степенью грани называется число ее граничных ребер (висячие ребра считаются дважды).
Язык графов оказывается удобным для описания многих технических, экономических, биологических, социальных и других систем.
Используя приложения теории графов можно решать многие задачи
(примеры указаны ниже)
1. Транспортные задачи, в которых вершинами графа являются пункты, а ребрами – дороги (автомобильные, железные и др.) и / или другие транс- портные (например, авиационные) маршруты. Другой пример – сети снабже- ния (энерго-, газоснабжения, снабжения товарами и т.д.), в которых верши- нами являются пункты производства и потребления, а ребрами – возможные маршруты перемещения (линии электропередач, газопроводы, дороги и т.д.).
Соответствующий класс задач оптимизации потоков грузов, размещения пунктов производства и потребления и т. д., иногда называется задачами
обеспечения или задачами о размещении. Их подклассом являются задачи о
грузоперевозках [12].
2. «Технологические задачи», в которых вершины отражают производ- ственные элементы (заводы, цеха, станки и т.д.), а дуги – потоки сырья, мате- риалов и продукции между ними – заключаются в определении оптимальной загрузки производственных элементов и обеспечивающих эту загрузку пото- ков [13].
3. Обменные схемы, являющиеся моделями таких явлений, как бартер, взаимозачеты и т.д. Вершины графа при этом описывают участников обмен- ной схемы (цепочки), а дуги – потоки материальных и финансовых ресурсов межу ними. Задача заключается в определении цепочки обменов, оптималь- ной с точки зрения, например, организатора обмена и согласованной с инте- ресами участников цепочки и существующими ограничениями [12-14].
4. Управление проектами. С точки зрения теории графов проект – сово- купность операций и зависимостей между ними. Хрестоматийным примером является проекты строительства некоторого объекта. Совокупность моделей и методов, использующих языки результаты теории графов и ориентирован- ных на решение задач управления проектами, получила название календарно-
Электронный архив УГЛТУ

106
сетевого планирования и управления (КСПУ) [12]. В рамках КСПУ решаются задачи определения последовательности выполнения операций и распреде- ления ресурсов между ними, оптимальных с точки зрения тех или иных кри- териев (времени выполнения проекта, затрат, риска и др.).
5. Модели коллективов и групп, используемые в социологии, основыва- ются на представлении людей или их групп в виде вершин, а отношений между ними (например, отношений знакомства, доверия, симпатии и т.д.) – в виде ребер или дуг. В рамках подобного описания решаются задачи исследо- вания структуры социальных групп, их сравнения, определения агрегирован- ных показателей, отражающих степень напряженности, согласованности вза- имодействия, и др.
6. Модели организационных структур, в которых вершинами являются элементы организационной системы, а ребрами или дугами – связи между ними
(информационные, управляющие, технологические и др.) [15, 16].