Экономико-математические методы

Рассмотрим некоторое конечное множество точек V = { v ₁, v ₂,…, v_n } и конечное множество линий Х, соединяющих некоторые пары из точек множества V. Полученная совокупность точек и линий называется графом и обозначается G = { V, X }.

Элементы множества V называются вершинами графа, а элементы множества Х – ребрами.

Граф можно изобразить при помощи геометрической конфигурации. Вершины обозначаются точками (кружочками), а ребра – линиями, соединяющими соответствующие вершины (рис. 4). При этом несущественным является расположение вершин, форма и длина ребер графа, важно лишь, соединены две данные точки ребром, или нет.

Ребра, соединяющие одну и ту же пару вершин, называются кратными (или параллельными) ребрами (ребра х ₄, х ₅ графа G 1 на рис. 4).

Если х – ребро графа, соединяющее вершины v_i, v_j, то вершины v_i и v_j называются концами ребра х.

Множество ребер графа Х можно задать, как множество пар вершин из множества V. Если пары в этом множестве Х являются упорядоченными, то граф называется ориентированным или орграфом. Ребра орграфа называют дугами и на рисунках помечают стрелками (рис. 4).

Если х = (v_i, v_j) – дуга орграфа, то вершина v_i называется началом дуги х, а вершина v_j – концом дуги х.

При помощи графов удобно изображать связь атомов в молекуле, кристаллические решетки, схемы дорог, маршруты движения, электрические цепи, экономические связи объектов, графики работ и др.

Для того, чтобы задать граф, необходимо задать множества его вершин и ребер(V и X). Иногда граф задают списком ребер (дуг), например, орграф G2, изображенный на рис. 4, можно задать следующим списком дуг:

X = { х ₁, х ₂, х ₃, х ₄, х ₅, х ₆} = {(v ₁, v ₄), (v ₁, v ₄), (v ₄, v ₂), (v ₂, v ₄), (v ₂, v ₃), (v ₃, v ₄)}.

В этом списке каждой из 6-ти дуг орграфа соответствует упорядоченная пара вершин (если граф неориентированный, то порядок записи вершин в каждой паре – произвольный).

Если граф содержит изолированные вершины, т.е. не связанные ни с одной другой вершиной ребрами (дугами) графа (см. вершину v ₅ в графе G1 на рис. 4), то список ребер не даст полного представления о графе. Кроме того, использовать список ребер (дуг) можно только при относительно небольшом количестве вершин графа. Для практического использования более удобен матричный способ задания графов.

Пусть G = { V, X } – граф, где V = { v ₁, v ₂,…, v_n }, X = { x ₁, …, x_m }.

Если вершины графа v_i, v_j являются концами ребра х, то говорят, что вершины v_i, v_j и ребро х инцидентны.

Матрицей инцидентности графа G называется матрица размерности n ´ m B (G), элементы которой

b_ij =

Строки матрицы инцидентности графа соответствуют его вершинам, а столбцы – ребрам.

Для орграфа вершина v_i идуга х_j инцидентны, если v_i является началом или концом дуги х_j. Элементы матрицы инцидентности орграфа определяются по формулам:

b_ij = (1)

Вершины v_i, v_j графа G называются смежными, если существует ребро х = (v_i, v_j)Î X, инцидентное этим вершинам (соединяющее эти вершины).

Матрицей смежности графа G называется квадратная матрица A (G) порядка п, каждый элемент которой a_ij равен количеству ребер, инцидентных вершинам v_i и v_j.

Для орграфа G = { V, X } элементы матрицы смежности определяются по формулам:

a_ij = (2)

Пример. Записать матрицу инцидентности и матрицу смежности для орграфа G2, изображенного на рис. 4.

Решение. Данный граф является ориентированным. Для построения матрицы инцидентности составим таблицу, используя формулы (1). Заполняем таблицу по столбцам, соответствующим дугам орграфа: в j- м столбце ставим в i -й строке

«–1», если вершина v_i является началом дуги х_j,

«1», если вершина v_i является концом дуги х_j,

«0» в остальных случаях (вершина v_i и дуга х_j неинцидентны).

	x 1	x 2	x 3	x 4	x 5	x 6	Получили матрицу инцидентности: В (G 2) = .
v 1	–1	–1
v 2				–1	–1
v 3						–1
v 4			–1

Для построения матрицы смежности составим таблицу, используя формулы (2). Так как граф G 2 ориентированный, то элемент матрицы a_ij равен количеству ребер с началом в i -й вершине, а концом в j -й вершине.

	v 1	v 2	v 3	v 4	Получили матрицу смежности A (G 2) =
v 1
v 2
v 3
v 4

Матрица инцидентности более информативна, чем матрица смежности, т.к. по ней можно восстановить не только нумерацию вершин и связи между ними, но и нумерацию ребер. Однако, при помощи матрицы инцидентности задают только графы, не имеющие изолированных вершин (в матрице смежности изолированной вершине соответствуют нулевая строка и нулевой столбец).

Кроме матриц инцидентности и смежности существуют и другие формы матричного задания графов. Матричный метод задания графов удобен для обработки данных на ЭВМ.

Система управления состоит из управляющего устройства (УУ) и объекта управления (ОУ). Примерами систем управления служат семейный бюджет, экономика отрасли, технологический процесс, научное исследование и т.д.

УУ передает в ОУ сигнал – управление. Управление может быть механическим воздействием, электромагнитным импульсом, потоком инвестиций и др. Под воздействием сигнала u (t), где t – время, u (t) – скалярная или векторная функция, система изменяет свое состояние (возможна обратная связь). Простейшая математическая модель системы управления без учета внешних воздействий включает:

• модель ОУ – оператор, в соответствии с которым осуществляется преобразование входа – управления u (t) в реакцию системы;

• алгоритм управления, который зависит от цели управления и наличия обратной связи.

В общем случае состояние динамической системы управления характеризуется n -мерным вектором (матрицей-столбцом)

,

где x_j (t) для j = 1,2,…, n называют фазовыми координатами, а – фазовым вектором.

Например, положение самолета определяет 6-мерный вектор, в котором 3 координаты задают положение центра масс самолета в пространстве и 3 координаты – его вращение относительно центра масс. Курс самолета – это вектор-функция .

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

(8)

или, в векторной форме: , где – вектор-функция, характеризующая изменение состояния системы, u (t) – функция управления. В реальных условиях множество управлений ограничено: , где U – класс допустимых управлений.

Для того, чтобы процесс управления был определен на некотором промежутке , необходимо задать начальное состояние системы – вектор . Тогда будет соответствовать траектория – вектор-функция , переводящая систему из состояния в – состояние, достижимое из состояния на данном классе управлений U.

Рассмотрим некоторый процесс управления без учета внешних воздействий, заданный системой обыкновенных дифференциальных уравнений , где – заданная вектор-функция, u (t) – функция управления из некоторого класса допустимых управлений U, и соответствует фазовый вектор (траектория).

Если определена цель управления, то имеет смысл искать наилучшее (оптимальное) управление для достижения этой цели. В большинстве случаев цель управления можно задать в форме вариационной задачи – поиска экстремума некоторого функционала I [ u (t)] на классе допустимых управлений U. Тогда задача оптимального управления: найти оптимальное управление u *(t) и соответствующую ему оптимальную траекторию , для которых

(другая форма записи: ),

или ().

Функционал I [ u ] называется критерием качества управления. Например, в так называемой «задаче Лагранжа» роль критерия качества выполняет интегральный функционал вида

(9)

где – заданная функция.

Рассмотрим простейшую задачу управления: задана модель системы управления , где , – непрерывная вектор-функция, – функция управления, и критерий качества управления

.

Пусть каждому управлению соответствует траектория , переводящая систему из состояния в , где и фиксированы.

Требуется найти оптимальное управление u *(t) и соответствующую ему оптимальную траекторию , для которых . Это задача Лагранжа с фиксированным временем и закрепленными концами траекторий: , .

Допустим, существует оптимальное управление и соответствующая ему оптимальная траектория , удовлетворяющие условиям задачи.

Введем вспомогательную вектор-функцию , где – неизвестные функции, кусочно-непрерывные на , и построим функцию Гамильтона-Понтрягина (гамильтониан):

. (10)

Очевидно, что .

При фиксированных гамильтониан является функцией управления. Можно доказать, что если u *(t) – оптимальное управление, то при u = u *(t) гамильтониан достигает максимума по управлению и выполняются условия

Принцип максимума Понтрягина.