Метод дерева решений при многокритериальной оптимизации в цепях поставок



Скачать 169.03 Kb.
Дата22.02.2016
Размер169.03 Kb.


Журнал «Логистика сегодня», №5, 2008.
МЕТОД ДЕРЕВА РЕШЕНИЙ ПРИ МНОГОКРИТЕРИАЛЬНОЙ

ОПТИМИЗАЦИИ В ЦЕПЯХ ПОСТАВОК

Бродецкий Г. Л. — д. т. н., к. ф. –м. н., профессор кафедры логистики ГУ-ВШЭ, профессор кафедры математических методов в экономике РЭА им. Г. В. Плеханова, профессор Международного центра логистики ГУ-ВШЭ (г. Москва).
В данной работе автор обращает внимание менеджеров в области логистики на то, что многокритериальную оптимизацию цепей поставок, когда среди частных критериев формализуются задачи управления рисками, можно реализовать на основе метода дерева решений. В статье рассмотрена специфика процедур указанного метода для выбора наилучшей альтернативы в формате таких задач оптимизации систем логистики при многих критериях.
КЛЮЧЕВЫЕ СЛОВА: управление рисками, поддержка решений, многокритериальная оптимизация в цепях поставок, дерево решений, процедуры свертки и блокировки при многих критериях, выбор наилучшего решения.
ВВЕДЕНИЕ. Управление рисками в формате задач поддержки решений в цепях поставок предполагает использование различных методов и подходов для нахождения наилучших решений. Они должны дать возможность менеджеру находить оптимальное решение с учетом специфики отношения лица, принимающего решения (ЛПР) к риску. При этом в рамках классического подхода теории риска оптимальность понимается в контексте наилучшего для ЛПР баланса между риском и ожидаемым доходом (как случайной величиной). При управлении рисками в логистике одним из наиболее эффективных методов выбора наилучших решений является метод дерева решений. Он позволяет: 1) в простом и удобном, наглядном и доступном для понимания виде формализовать задачу выбора наилучшего решения; 2) синтезировать в одной схеме все случайные факторы, которые ЛПР требует учесть в формате оптимизационной модели; 3) синтезировать в одной схеме все варианты и специфические особенности альтернативных решений, которые ЛПР планирует анализировать в формате оптимизационной модели; 4) выбрать концепцию, в формате которой будет учитываться отношение ЛПР к риску при нахождении наилучшего решения.

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



Атрибуты метода дерева решений. Сначала напомним, кратко, основные положения, относящиеся к методу дерева решений (см., например, [4]). Он реализуется на основе использования специального инструмента, позволяющего представить структуру анализируемых альтернатив и специфику воздействия внешних связей в виде графа, который является «деревом», т.е. не имеет циклов. Такое дерево представляют набором вершин и ребер/дуг, причем циклы в соответствующем графе, как уже отмечалось, отсутствуют. Для удобства интерпретации выделяют три типа вершин в таком графе – «прямоугольные», «круглые» и концевые. Вершинами «прямоугольного» типа представляют ситуации, в формате которых решения принимаются непосредственно самим ЛПР для выбора одной из доступных альтернатив (они будут представлены исходящими из такой вершины ребрами). Вершинами «круглого» типа представляют ситуации, в формате которых требуется учесть возможные случайные сценарии, соотнесенные с такой вершиной и влияющие на дальнейшую траекторию развития процесса реализации конечного экономического результата. Концевыми вершинами представляют события или ситуации, для которых конечный результат представляется конкретным числовым значением или описывается известным вероятностным распределением.

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

При этом процедуры свертки реализуются именно для вершин «круглого» типа. Они реализуются сначала для концевых вершин «круглого» типа соответствующего дерева решений, а также для «круглых» вершин, за которыми следуют концевые вершины с конкретным численным результатом. Суть указанных процедур свертки – заменить заданные распределения вероятностей случайного конечного результата анализируемой альтернативы (применительно к соответствующей «круглой» вершине) на соотносимый с этой вершиной набор параметров, который должен быть достаточным для принятия решения. Например, при нейтральном отношении к риску используется один параметр. В задачах управления рисками в логистике это - средние ожидаемые потери из-за фактора риска. Соответствующий критерий называют EVC-критерием (expected value criterion). Соответствующую концепцию (подход к учету рисков) в теории риска относят к оптимизации «производственных» рисков. В более общем случае, потребуется учет показателя среднего квадратического отклонения для анализируемых случайных потерь (в формате классического подхода теории риска этот показатель выступает мерой измерения риска). Соответствующий критерий учета фактора риска называют MVC-критерием (mean variance criterion), а соответствующую концепцию (подход к учету рисков) в теории риска называют «коммерческими» рисками. В формате такого подхода учитываются не только средние ожидаемые показатели потерь, но и ожидаемый «разброс» их значений. Требуемые в соответствии с принятым критерием (и принятой концепцией учета рисков) параметры, должны быть найдены и «приписаны» к каждой «круглой» вершине дерева решений.

Процедуры блокировки в рамках метода дерева решений реализуются для вершин “прямоугольного” типа. При этом они реализуются пошагово: на каждом отдельном шаге – только для тех вершин “прямоугольного” типа, для которых каждой имеющейся альтернативной возможности развития траектории процесса реализации конечного результата (исходя из такой вершины) уже сопоставлен соответствующий набор параметров и показателей, характеризующих такую альтернативную возможность. Незаблокированной остается только альтернатива с наилучшим показателем баланса между риском и ожидаемым доходом. Соответствующий баланс формализуется на основе конкретного критерия выбора. В частности, при нейтральном отношении к риску (критерий EVC) будет выбрана альтернатива с наибольшим средним ожидаемым доходом/прибылью (несмотря на возможное очень большое отклонение для конечного результата издержек/потерь).



Особенности процедур метода дерева решений в формате задач многокритериальной оптимизации. Рассмотрим особенности реализации метода дерева решений в формате задач многокритериальной оптимизации. Подчеркнем, что при формализации оптимизационной модели далее принимается, что в качестве одного из частных критериев будет формализован критерий оптимизации решения в условиях риска (критерий далее уточняется). Если задача анализа и выбора наилучшего решения будет формализована как задача многокритериальной оптимизации с использованием нескольких частных критериев, то для процедур метода дерева решений потребуются специальные корректировки/уточнения. Прежде всего, это относится к процедурам параметризации самого дерева решений. Действительно, рассмотрим ситуацию, когда ищется наилучшее решение при N заданных частных критериях g(k), где k=1, …, N. Пусть для определенности оценки по указанным частным критериям представляют собой различные виды издержек/потерь (например, годовые издержки поставок, хранения, потери из-за нарушений сроков или срыва поставок и т.п.). Тогда наилучшее решение ищется в формате следующей задачи оптимизации:

g(1) → min

g(2) → min

…………


g(N) → min

Для каждой альтернативы Aj конечный результат следует представлять вектором издержек/потерь с координатами



j1; Пj2; Пj3; … ; ПjN).
Здесь Пjk = g(k)(Aj) представляет потери (вообще говоря, они могут быть случайными) по k-му частному критерию в случае, когда будет реализована альтернатива Aj. Таким образом, в пространстве значений частных критериев (пространство издержек/потерь) каждая альтернатива будет характеризоваться вектором указанного типа. Аналогичные особенности для процедур параметризации дерева решений должны быть учтены при формализации случайных сценариев и соответствующих вероятностных распределений применительно к вершинам круглого типа. А именно, каждому сценарию развития событий должен быть сопоставлен «свой» N- мерный вектор с оценками частных критериев (или «свой» N- мерный закон распределения вероятностей его компонент).

Процедуры свертки при многих критериях. Отметим теперь, как отразится специфика задач многокритериальной оптимизации на процедурах свертки в рамках метода дерева решений. Процедуры свертки в рамках метода дерева решений реализуются для вершин «круглого» типа. Такие вершины отражают специфику воздействия конкретного случайного фактора и подчеркивают следующую особенность дальнейшей траектории реализации конечного экономического результата в формате такого фактора: она зависит не от ЛПР, а от случая. Указанные процедуры сначала реализуются для концевых вершин «круглого» типа, а также для таких «круглых» вершин, за которыми следуют концевые. В формате задач многокритериальной оптимизации суть процедур свертки состоит в следующем. Необходимо заменить заданные N- мерные распределения вероятностей случайного конечного результата (по частным критериям) применительно к соответствующей «круглой» вершине на требуемый набор параметров (в соответствии с используемой концепцией учета таких оценок в условиях риска). Найденный набор параметров будет сопоставлен соответствующей вершине дерева решений. Он должен содержать всю необходимую информацию для сравнения альтернатив как с учетом внешних воздействий (рисков), так и с учетом всех оценок частных критериев (в рамках дальнейшего синтеза наилучшего решения при многих критериях). Отметим, что применительно к критериям EVC и MVC учета фактора внешних воздействий (риска) такими параметрами являются:

  • для критерия EVC – параметр ожидаемых потерь «m» из-за фактора риска;

  • для критерия MVC – соответственно параметры «m» и «σm».

Таким образом, цель реализации процедур свертки для любой «круглой» вершины – синтезировать требуемые по каждому частному критерию показатели, характеризующие такую «круглую» вершину с учетом рисков. На основе найденных или «синтезированных» оценок частных критериев может быть определен соответствующий показатель критерия выбора (обозначим его далее через F) в формате рассматриваемой задачи многокритериальной оптимизации. Найденные параметры и показатели критерия записывают внутри соответствующей «круглой» вершины (или рядом с ней). Они понадобятся при реализации последующих процедур свертки или блокировки, т.е. на следующих шагах или этапах реализации метода дерева решений. После того, как указанные процедуры будут выполнены, дальнейшую траекторию процесса реализации конечного экономического результата (т.е. после такой «круглой» вершины по направлению к концевым вершинам дерева) можно не «замечать». Действительно, все необходимые данные для продолжения процедур выбора наилучшего решения (в том числе и с учетом частного критерия, связанного с управлением рисками) будут уже синтезированы и представлены непосредственно в формате самой такой вершины «круглого» типа.

Приведем формулы, на основе которых реализуется синтез требуемых параметров применительно к критерию MVC. Напомним, что критерий EVC является частным случаем критерия MVC: в его формате потребуются только те из приведенных ниже формул, которые относятся к математическим ожиданиям издержек/потерь из-за вмешательства случая (фактора риска). Рассмотрим различные ситуации для реализации процедур свертки в зависимости от расположения «круглой» вершины на ветвях дерева решений.



Свертка для концевых фрагментов дерева решений. Рассмотрим указанные процедуры в формате так называемого сценарного подхода. Пусть при анализе воздействия некоторого случайного фактора «S» известно следующее. Оценки частных критериев после «воздействия» такого фактора будут зависеть от реализованного сценария. При этом пусть:

  • n - число сценариев, учет которых ЛПР считает достаточным в формате оптимизационной модели для анализируемой системы логистики;

  • p1, p2, …, pn – вероятности соответствующих сценариев (принимается, что);

  • ПSi1; ПSi2; … ; ПSiN – значения оценок частных критериев в формате i-го сценария для конечного результата (издержек/потерь) применительно к соответствующей круглой вершине дерева решений (см. рис. 1);

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

1) средние показатели для оценок частных критериев -

2) показатели разброса их значений - и

(здесь представлен второй момент для ПSk и соответствующая дисперсия).

Подчеркнем, что в общем случае вместо представленного сценарного подхода, формат оптимизационной модели может потребовать учета N- мерных законов распределения вероятностей для конечного результата (как N- мерного вектора с показателями частных критериев). После этого (при необходимости сравнения с другими альтернативами) может быть синтезировано значение соответствующего требуемого показателя критерия выбора F для линии уровня соответствующего семейства в пространстве издержек/потерь. Другими словами, зная набор {ПSk} средних ожидаемых «оценок» частных критериев и набор {} их вторых моментов или набор их дисперсий, после процедуры свертки можно в формате конкретного критерия выбора (в формате задачи многокритериальной оптимизации) определить его результирующий показатель (показатель линии уровня для критерия выбора) применительно к дальнейшей траектории дерева решений. Графическая иллюстрация представлена на рис. 1.

Свертка для «промежуточных» фрагментов дерева решений. Как и в предыдущей ситуации ограничимся сценарным подходом. Пусть в формате некоторого случайного фактора «S» известно следующее. Оценки частных критериев после «воздействия» такого фактора будут зависеть от реализованного сценария. При этом пусть:


  • n - число сценариев, учет которых ЛПР считает достаточным в формате оптимизационной модели для анализируемой системы логистики;

  • p1, p2, …, pn – вероятности соответствующих сценариев ();

  • Si1; ПSi2; … ; ПSiN) и – уже найденные на предыдущих этапах метода средние ожидаемые показатели для оценок частных критериев и их вторые моменты в формате i-го сценария для возможных издержек/потерь применительно к соответствующей ветви дерева решений (в направлении к концевым вершинам).

В такой ситуации (в формате сценарного подхода) синтез требуемых для рассматриваемой «круглой» вершины параметров при свертке в рамках критерия MVC реализуется снова по аналогичным формулам:

1) средний показатель для оценки частного критерия -

2) показатели разброса ее значений - и .

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




Рис. 1. Иллюстрация процедур свертки для концевых вершин дерева круглого типа:

А) фрагмент дерева решений до реализации процедур свертки;

Б) этот фрагмент после реализации процедур свертки.



Процедуры блокировки при многих критериях. Процедуры блокировки в рамках метода дерева решений реализуются для вершин “прямоугольного” типа. Напомним, в формате таких вершин выбор, относящийся к дальнейшей реализации конечного экономического результата, зависит от ЛПР. Процедуры блокировки реализуются пошагово, причем оценки всех частных критериев будут учтены в формате критерия выбора. На каждом отдельном шаге указанные процедуры будут реализованы только для тех вершин “прямоугольного” типа, для которых каждой имеющейся альтернативной возможности развития траектории анализируемого процесса уже сопоставлен соответствующий набор оценок частных критериев. Другими словами, процедуры блокировки выполняются для таких вершин прямоугольного типа, для которых применительно к каждой альтернативной возможности продолжения цепи (по направлению к концевым вершинам дерева) оказывается, что для всех последующих вершин дерева, расположенных на таких цепях дерева, уже реализованы процедуры свертки / процедуры блокировки (на предыдущих шагах метода). Суть процедур блокировки состоит в следующем. Для имеющихся альтернативных возможностей продолжения процесса реализации конечного экономического результата (зависящих от ЛПР) “заблокировать” для реализации все те альтернативные возможности, которые заведомо не приведут к оптимальному решению.

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



Рис. 2. Иллюстрация процедуры блокировки для вершины «прямоугольного» типа:
А) – до ее реализации; Б) – после (здесь F2 < F1 и F2 < F3).

Затем применительно к каждой альтернативной возможности дальнейшего развития процесса следует «перечеркнуть» ребра дерева, исходящие из этой вершины (по направлению к концевым вершинам дерева), для которых значения показателя такого критерия не являются наилучшими. Траектории возможного развития процесса реализации конечного экономического результата, включающие такие «перечеркнутые» ребра, из последующего анализа далее «выбрасываются» (т.к. они заведомо не могут привести к оптимальному для ЛПР решению). При этом набор параметров, характеризующий наилучший возможный результат применительно к рассматриваемой вершине прямоугольного типа (по критерию выбора), «приписывается» к этой вершине и будет участвовать в дальнейших процедурах метода при нахождении наилучшего решения.

Иллюстрация применительно к условной вершине прямоугольного типа, в формате которой анализируются три альтернативы (в качестве фрагмента дерева решений), когда риск учитывается по MVC критерию, приведена на рис. 2. При этом:

- ситуация А) на этом рисунке представляет фрагмент соответствующего дерева решений с вершиной прямоугольного типа до реализации процедуры блокировки;

- ситуация Б) представляет тот же фрагмент после реализации процедуры блокировки, причем для случая, когда показатели критерия выбора для имеющихся альтернативных возможностей у ЛПР связаны неравенствами F2 < F1 и F2 < F3 (соответственно рассматриваемой вершине прямоугольного типа в результате реализованной процедуры блокировки, будут сопоставлены и приписаны оценки частных критериев, характеризующие именно альтернативу 2).

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



Выбор наилучшего решения. Соответствующий заключительный этап в рамках общей схемы рассматриваемого «метода дерева решений» реализуется после того, как будут выполнены все процедуры свертки и блокировки на предыдущих этапах его реализации применительно к выбранной концепции учета риска и функции выбора для оптимизации решений при многих критериях в пространстве издержек/потерь. Все необходимые данные для определения наилучшей стратегии по имеющимся альтернативным возможностям ЛПР применительно к анализируемой модели для рассматриваемой системы логистики с учетом заданного отношения к риску уже будут получены. А именно, синтез наилучшей (оптимальной) стратегии реализуется по соответствующему дереву решений следующим образом (уже в направлении от корневой вершины дерева к его концевым вершинам). Применительно к корневой вершине дерева решений (как правило, это будет вершина прямоугольного типа) выбирается ребро, соответствующее незаблокированной альтернативной возможности, которая представляет наилучший выбор для ЛПР на этом шаге метода. Для наглядности такое ребро специально окрашивают или выделяют «жирной» линией.

Оно приводит соответственно к следующей вершине дерева решений, которую (при желании и для наглядности) также можно «окрасить» или выделить «жирной» линией. В зависимости от типа вершины, которой заканчивается начальное ребро цепи, синтезирующей наилучший выбор для ЛПР, следующее ребро (или ребра) соответствующей искомой цепи дерева (или цепей) строится следующим образом.



  1. Если указанное ребро «привело» снова к вершине прямоугольного типа, то на очередном шаге будет выбрано следующее ребро (по направлению к концевым вершинам дерева), соответствующее незаблокированной альтернативной возможности для ЛПР в формате указанной вершины. Его опять-таки для наглядности окрашивают или выделяют «жирной» линией, как и очередную вершину дерева решений, к которой такое ребро «приводит».

  2. Если начальное ребро «привело» к вершине круглого типа, то синтезируемое для ЛПР наилучшее решение должно учитывать все случайные сценарии в рамках анализируемой модели. Поэтому все исходящие из такой круглой вершины ребра (по направлению к концевым вершинам дерева) для наглядности следует окрасить (как и очередные вершины дерева решений, к которым они «приводят»). Траектория развития процесса реализации конечного экономического результата (после события, представленного указанной вершиной дерева решений) будет развиваться по какому-то одному (любому) из таких «направлений» продолжения интересующей ЛПР цепи в рамках соответствующей задачи многокритериальной оптимизации с учетом рисков.

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

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

  1. Построение дерева решений для задачи управления рисками анализируемой цепи поставок (на основе учета воздействия соответствующих случайных факторов).

  2. Соотнесение параметров исходной задачи и оценок всех частных критериев с параметрами и оценками, приписываемыми к ветвям и к вершинам дерева решений (процедуры параметризации для построенного дерева решений). При этом каждая анализируемая альтернатива будет представлена вектором оценок/параметров в пространстве издержек/потерь (пространство значений частных критериев).

  3. Реализация процедур «свертки» и «блокировки». Они позволяют учитывать отношение ЛПР к риску отклонения оценок частных критериев и важность таких оценок. При этом процедуры свертки реализуются применительно к оценкам каждого частного критерия, а процедуры блокировки реализуются с учетом критерия выбора решений в пространстве издержек/потерь.

  4. Выбор наилучшего (оптимального) решения для анализируемого звена / звеньев цепи поставок с учетом: а) заданного отношения к риску изменения оценок частных критериев; б) предпочтений ЛПР в пространстве значений частных критериев.

В статье представлены материалы гранта: «Индивидуальный исследовательский проект № 08-01-0017 «Проблемы многокритериальной оптимизации систем логистики», выполнен при поддержке ГУ-ВШЭ».
ЛИТЕРАТУРА


  1. Сергеев В.И. Корпоративная логистика. 300 ответов на вопросы профессионалов. –М.: ИНФРА –М, 2004. – 976 с.

  2. Сток Д.Р., Ламберт Д.М. Стратегическое управление логистикой. –М.: ИНФРА – М, 2005. – ХХХII, 797 с.

  3. Управление цепями поставок / Под ред. Дж. Гатторны; Пер. с 5-го англ. изд. – М.: ИНФРА - М, 2008. – XXXIV, 670 с.

  4. Бродецкий Г.Л. Моделирование логистических систем. Оптимальные решения в условиях риска. – М.: Вершина, 2006. – 376 с.



Каталог: data
data -> Программа дисциплины для направления/ специальности подготовки бакалавра/ магистра/ специалиста
data -> Александрова Лада Анатольевна
data -> «Особенности реализации личностно-ориентированного подхода в профессиональной подготовке студентов высших учебных заведений»
data -> Программа «Управление образованием»
data -> Возрастные особенности развития детей
data -> Обретение своего лица. О педагогической программе развития А. Гавралан
data -> Федеральное государственное автономное образовательное


Поделитесь с Вашими друзьями:


База данных защищена авторским правом ©psihdocs.ru 2017
обратиться к администрации

    Главная страница