Многокритериальные задачи. Парето-оптимальность

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

1. Невозвратное множество (рис. 3).

Рис. 3. Невозвратное множество

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

2. Возвратное множество (рис. 4).

Рис. 4. Возвратное множество

В этом случае также возможны любые переходы внутри множества. Система может войти в это множество, но не может покинуть его.

3. Эргодическое множество (рис. 5).

Рис. 5. Эргодическое множество

В случае эргодического множества возможны любые переходы внутри множества, но исключены переходы из множества и в него.

4. Поглощающее множество (рис. 6)

Рис. 6. Поглощающее множество

При попадании системы в это множество процесс заканчивается.

Кроме описанной выше классификации множеств различают состояния системы:

а) существенное состояние (рис.7): возможны переходы из   в   и обратно.

Рис. 7. Существенное состояние

б) несущественное состояние (рис. 8): возможен переход из   в  , но невозможен обратный.

Рис. 8. Несущественное состояние

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

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

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

В свою очередь, эргодические цепи могут быть регулярными или циклическими. Циклические цепи отличаются от регулярных тем, что в процессе переходов через определенное количество шагов (циклов) происходит возврат в какое-либо состояние. Регулярные цепи этим свойством не обладают. Если просуммировать все вышесказанные определения, то можно дать следующую классификацию марковских процессов (рис. 9):

Рис. 9. Классификация марковских процессов 

 

 

 

 

 

 

 

3.Классическая  теория оптимизации

 

Классическая теория оптимизации базируется на аппарате дифференциального исчисления.

На рис.1 легко заметить, что первая производная функции f(x) (тангенс угла наклона касательной к графику функции) равна 0 во всех ее экстремальных точках. Однако это условие выполняется и в точках перегиба и седловых точках (x5).

Т.о. xi, являющиеся решениями уравнения f’(x) = 0, – это либо точки экстремума либо точки перегиба. Условие f’(x) = 0 называют необходимым условием наличия экстремума.

Исследование производных высших порядков позволяет убедиться, что точка xi – экстремум и более того, является она точкой максимума или минимума. Для этого необходимо найти вторую производную f”(x) и в нее подставить значения xi, полученные при решении уравнения f’(x) = 0:

- если f”(xi) > 0 – то в точке xi минимум функции;

- если f”(xi) < 0 – то в точке xi максимум функции;

- если f”(xi) = 0 – то необходимо исследовать следующие производные. В этом случае, если первые (n-1) производных равны 0 и f(n)(xi) <> 0, то в точке xi функция имеет:

- точку перегиба, если n – нечетное;

- минимум, если n – четное и f(n)(xi) > 0;

- максимум, если n – четное и f(n)(xi) < 0.

Эти условия называются достаточными.

 

 

 

 

 

Таблица 2.1

Примеры определения экстремумов функции

№ п/п	Функция	Экстремумы	График функции
1	y = f(x) = x2	f’(x) = 2x  2x = 0  x0 = 0 – точка экстремума или перегиба.    f”(x) = 2 → 2 > 0  x0 = 0 – точка минимума.
2	y = f(x) = x3 – 2x2 + x + 1	f’(x) = 3x2 - 4x + 1  3x2 - 4x + 1 = 0  x1 = 1/3 и x2 = 1 – точки экстремума или перегиба.    f”(x) = 6x - 4 →  f”(x1) = 6 * 1/3 – 4 = -2  f”(x1) < 0  x1 = 0 – точка максимума;  f”(x2) = 6 * 1 – 4 = 2  f”(x2) > 0  x2 = 0 – точка минимума.
3	y = f(x) = 2x4	f’(x) = 8x3  8x3 = 0  x0 = 0 – точка экстремума или перегиба.    f”(x) = 24x2  f”(x0) = 24 * 02 = 0.    f(3)(x) = 48x  f(3)(x0)=48 * 0 = 0.    f(4)(x) = 48  48 > 0 и n = 4 – четное  x0 = 0 – точка минимума.
4	y = f(x) = 2x3	f’(x) = 6x2  6x2 = 0  x0 = 0 – точка экстремума или перегиба.    f”(x) = 12x  f”(x0) = 12 * 02 = 0.    f(3)(x) = 12  n = 3 – нечетное  x0 = 0 – точка перегиба.

При наличии ограничений, помимо точек экстремума проверяют граничные значения функции. Например, для функции из 2-ого примера f(x) = x3 – 2x2 + x + 1 требуется найти максимум при ограничениях x ≥ -2 и x ≤ 3. Тогда помимо точек экстремума x1 = 1/3 (f(x1) = 1.15) и x2 = 1 (f(x2) = 1), проверяем значения функции в точках x3 = -2 (f(x3) = -17) и x4 = 3 (f(x4) = 13). Таким образом, искомое оптимальное значение функции в точке x4 = 3.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4.Графы. Построение  минимального остовного дерева. Задача определения кратчайшего  пути.

 

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

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

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

Рассмотрим процедуру построения минимального остовного дерева.

Введем обозначения:

X={ x1, x2, …, xn } - множество узлов сети;

Ck - связное множество узлов сети, соединенных алгоритмом после  выполнения k-й итерации;

   - множество узлов сети, не  соединенных с узлами множества Ck после выполнения k-й итерации;

Алгоритм построения минимального остовного дерева сети:

1.  Взять произвольный узел  сети xi, C1={xi}, = X\{xi};

2.     Выбрать из оставшихся  узлов узел xj, ближайший к множеству  узлов C1, C2={ xi, xj }, = X\{ xi, xj };

3.     Выбрать из множества  узел, ближайший к узлам множества C2, включить его в множество C2 и исключить из множества .

За конечное число шагов будут обработаны все узлы сети и построено минимальное остовное дерево. Cn=X, =f.

Задача нахождения кратчайшего пути

 

Данная задача состоит в определении в транспортной сети кратчайшего пути между заданными исходным пунктом и пунктом назначения. Такая модель может быть использована для описания различных экономических ситуаций.

Введем следующие обозначения:

x1 - исходный узел;

xn - узел назначения;

dij - расстояние на сети между  смежными узлами xi и xj;

Uj - кратчайшее расстояние от  узла x1 до узла xj, U1=0.

Алгоритм нахождения кратчайшего пути состоит в последовательном нахождении значений Uj для каждого узла от исходного узла до узла назначения. Значение Uj для каждого узла рассчитывается по формуле

 

={ Ui  + dij }.

Процедура заканчивается, когда получено значение Un для узла назначения.

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

Сетевое планирование

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

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

Фиктивная работа - это связь между результатами работ (событиями), не требующая затрат времени и ресурсов.

Событие - это результат (промежуточный или конечный) выполнения одной или нескольких предшествующих работ.

Путь - это любая непрерывная последовательность (цепь) работ и событий.

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

При построении сетевых моделей необходимо соблюдать следующие правила:

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

2. Два соседних события могут  объединяться лишь одной работой. Для изображения параллельных  работ вводятся промежуточное  событие и фиктивная работа.

3. В сети не должно быть  тупиков, т.е. промежуточных событий, из которых не выходит ни  одна работа.

4. В сети не должно быть  промежуточных событий, которым  не предшествует хотя бы одна  работа.

5. В сети не должно быть  замкнутых контуров, состоящих из  взаимосвязанных работ, создающих  замкнутую цепь. Для правильной  нумерации событий поступают  следующим образом: нумерация событий  начинается с исходного события, которому дается номер 1.

Из исходного события 1 вычеркивают все исходящие из него работы, на оставшейся сети вновь находят событие, в которое не входит ни одна работа. Этому событию дается номер 2. Затем вычерчивают работы, выходящие из события 2, и вновь находят на оставшейся части сети событие, в которое не входит ни одна работа, ему присваивается номер 3, и так продолжается до завершающего события.

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

Рассмотрим прямой проход.

tiр.н  - ранний срок начала  всех операций, выходящих из события i.

Если i = 0, то  t0 p. н = 0.

tjр.н   -  ранний срок начала  всех операций, входящих в j.

tjр.н  = max { tip.н + tij } для всех (i, j),

где tij  - продолжительность операции (i, j).

Различают два вида резервов времени: полный резерв (rп) и свободный резерв (rсв).

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

r п = tijп.н - tip.н.

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

rсвij = tjp.н - tiр.н - tij.

Используя результаты вычислений при прямом и обратном проходах, можно определить операции критического пути. Операция (i, j) принадлежит критическому пути, если она удовлетворяет условиям:

tiр.н = tiп.о,

tjр.н  = tjп.о,

tjр.н  - tiр.н = tjп.о - tiп.о = ti j.

Стоимостные факторы при реализации сетевого графика учитываются путем определения зависимости "затраты - продолжительность" для каждой операции. При этом рассматриваются прямые затраты, а косвенные типа административных или управленческих расходов не принимаются во внимание.

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

  Этого можно достичь за счет  уменьшения продолжительности какой-либо  критической операции, только критические  операции и следует подвергать  анализу.

Чтобы добиться сокращения продолжительности выполнения работ при минимально возможных затратах, необходимо в максимально допустимой степени сжать ту критическую операцию, у которой наклон кривой "затраты - продолжительность" наименьший. В результате сжатия критической операции получают новый календарный график, возможно, с новым критическим путем. Стоимость работ при новом календарном графике будет выше стоимости предшествующего графика. На следующем этапе этот новый график вновь подвергается сжатию  за счет следующей критической операции  с минимальным наклоном кривой "затраты - продолжительность" при условии, что продолжительность этой операции не достигла минимального значения. Подобная процедура повторяется, пока все критические операции не будут находиться в режиме максимальной интенсивности. Полученный таким образом оптимальный календарный график соответствует минимуму прямых затрат.