Теория принятия решений

Министерство образования и науки Российской Федерации Балтийский государственный технический университет «Военмех» Е.Е. ВОРОБЬЕВА, В.Ю. ЕМЕЛЬЯНОВ ТЕОРИЯ ПРИНЯТИЯ РЕШЕНИЙ Учебное пособие Санкт-Петербург 2018 УДК 519.8 Воробьева Е.Е. Теория принятия решений: учеб. пособие / Е.Е. Воробьева, В.Ю. Емельянов; Балт. гос. техн. ун-т. – СПб, 2018. - с. Пособие содержит основные сведения по методам теории принятия решений и исследования операций: методам оптимизации, линейном и нелинейном программировании, методам решения стратегических и статистических матричных игр, методам решения многокритериальных задач, включая применение нечеткой логики. Приводятся основные аналитические и расчетные схемы решения практических задач принятия решений в различных областях инженерной и организационной деятельности и большое число расчетных примеров. Пособие соответствует программам учебных дисциплин «Теория принятия решений» и «Исследование операций». Предназначено для студентов, обучающихся по направлениям укрупненной группы 09.00.00 «Информатика и вычислительная техника», а также другим инженерным и экономическим направлениям и специальностям. Рецензент: @ БГТУ, 2018 @ Авторы, 2018 2 ВВЕДЕНИЕ Теория принятия решений – это совокупность математических методов обоснования выбора решений в различных областях целенаправленной человеческой деятельности. Теория принятия решений – сравнительно новый термин. Еще в литературе 70-х гг. ХХ века его трудно встретить. По этой причине и в силу разнообразия практических задач в литературе встречаются разные трактовки ответов на следующие вопросы: - какую область или совокупность областей мы имеем в виду; - какими видами задач мы ограничиваемся. Данное учебное пособие также не охватывает всего спектра задач принятия решений и посвящено основным методам выбора решений в технике и организационной деятельности при достаточном разнообразии с точки зрения формальной постановки задач. С точки зрения выбора решений в организационной деятельности теория принятия решений является частью более общей науки – исследования операций. Операция – это совокупность мероприятий, направленных на достижение определенной цели. Можно выделить прямую и обратную задачи исследования операций. Решение прямой задачи сводится к оценке степени достижения цели при определенном варианте организации операции. Обратная задача состоит в выборе наилучшего варианта организации операции (решения) из некоторой совокупности. В целом же содержание исследования операций соответствует более широкому кругу задач: - формализация операции (составление адекватной математической модели, определение границ множества возможных решений, выбор критериев для количественной оценки возможных решений); 3 - математическое моделирование и получение количественных значений избранных критериев при различных вариантах решения; - применение математических методов выбора наилучшего решения (методов теории принятия решений). Характеризуя место теории принятия решений и исследования операций в практической деятельности, необходимо отметить следующее. С одной стороны, современный уровень сложности создаваемых технических систем и организационных мероприятий, нестационарность условий их применения или проведения, наличие случайных факторов или отсутствие полной информации все чаще просто не позволяют выбрать тот или иной вариант действий или конструкции только на основе опыта, интуиции. Необходим расчет, т.е. математический метод выбора, принятия решения. С другой стороны: 1. Математические методы обоснования выбора решений, очевидно, предусматривают использование математических моделей. Как известно, любая математическая модель обладает свойствами конечности (некоторые особенности исследуемой системы нам неизвестны или мы не умеем их формализовать), упрощенности (чтобы сделать модель более доступной для анализа, мы не учитываем некоторые особенности системы или процесса), приближенности (мы неточно знаем параметры задачи или вид модели позволяет получать результат только с определенным уровнем погрешности, как например, в статистических моделях). Поэтому наши количественные оценки возможных решений могут отличаться от результатов, наблюдаемых в реальных условиях. 2. В ряде случаев известные методы принятия решений не дают однозначного результата, а позволяют только сократить область возможных решений. Поэтому в практической деятельности роль теории принятия решений сводится чаще к формированию рекомендаций по выбору варианта построения 4 технической системы или организации операции. А окончательное слово остается за заказчиком или руководителем, обозначаемым термином – лицо, принимающее решение (ЛПР). 1. ПРИМЕРЫ И КЛАССИФИКАЦИЯ ЗАДАЧ ПРИНЯТИЯ РЕШЕНИЙ. ОБЗОР МЕТОДОВ В условиях широкого разнообразия задач принятия решений их классификация по рассматриваемым ниже признакам облегчает выбор наиболее удобного и эффективного метода. Рассмотрим ряд примеров. Пример 1. Предприятие задерживает возвращение кредита объемом S, имея возможность пустить его в оборот или вложить в производство. Ожидаемая прибыль пропорциональна времени использования средств: A=aSt. За задержку кредита начисляется пеня, увеличивающаяся во времени по квадратичному закону: В=bSt 2 . По истечении же срока t1 в случае невозврата кредита будет начата процедура банкротства предприятия. Определить наиболее выгодное время задержки кредита. Прибыль от использования кредита определяется как разность P=A– B=aSt–bSt 2 и должна с учетом постановки задачи рассматриваться как функция одного аргумента P=P(t). Таким образом, задача сводится к нахождению значения t в пределах диапазона 00 такое, что для любой точки x  C , для которой x  xˆ   , выполняется неравенство f 0  x   f 0  xˆ  . Здесь x  xˆ – расстояние между точками x и x̂ в 16 рассматриваемом пространстве. Иными словами, точка x̂ доставляет функции f0 минимум не во всей области C, а лишь в некоторой окрестности (-окрестности) вокруг себя. Локальным максимумом называется точка xˆ  C , если существует число >0 такое, что для любой точки x  C , для которой x  xˆ   , выполняется неравенство f 0  x   f 0  xˆ  . Для нахождения локальных экстремумов используется система необходимых и достаточных условий. Рассмотрим их сначала для функции одного аргумента. Первое необходимое условие достижения локального экстремума: df0  0. dx Это условие позволяет получить алгебраическое уравнение относительно x, решение которого дает одну или несколько точек, в которых возможен локальный экстремум. Такие точки называют стационарными. Второе необходимое условие: d 2 f0 dx 2  0 для минимума или d 2 f0 dx 2  0 для максимума. Выполнение этого условия проверяется в стационарных точках. Достаточное условие локального экстремума состоит в одновременном выполнении первого и второго необходимых условий при строгом неравенстве во втором. Применение рассмотренных условий иллюстрирует рис. 7, где f 0 '  x   f 0 ' ' x   d 2 f0 dx 2 df0 , dx . На рис. 7, а функция f0(x) достигает минимума, на рис. 7, б – максимума, на рис. 7, в представлен случай выполнения только необходимых условий. Достаточное условие не выполнено, и имеющаяся стационарная точка является не точкой экстремума, а точкой перегиба функции f0(x). 17 Существуют эквивалентные формулировки второго необходимого условия. Например, для минимума требуется выпуклость функции f0(x): для всей окрестности стационарной точки x̂ должно выполняться неравенство f 0 x   f 0 xˆ   df0  x  xˆ  . dx x  xˆ Соответственно для максимума требуется вогнутость функции f0(x), определяемая неравенством f 0 x   f 0 xˆ   df0  x  xˆ  . Такие формулировки оказываются dx x  xˆ полезны в особых случаях. Например, если f0(x) в стационарной точке не является дважды дифференцируемой. Пример   12. Требуется найти абсолютные экстремумы функции f 0  x   x 3 x 2  1 на интервале значений аргумента  1  x  2 . Применим первое необходимое условие достижения локального экстремума и найдем стационарные точки: f 0 '  x   5 x 4  3x 2  0 ; x1=0, x2   3 5 , x3  3 5 . 18 В соответствии со вторым условием проверим знак второй производной в стационарных f 0 ' ' x3   6 f 0 ' '  x   20 x 3  6 x ; точках: f 0 ' '  x1   0 , f 0 ' '  x2   6 3  0; 5 3  0. 5 Таким образом, в точке x2 достигается локальный максимум, в точке x3 – локальный минимум. В результате с учетом отсутствия разрывов функции f(x) множество критических точек в данной задаче включит в себя x2, x3, а также границы допустимой области x4 = –1, x5 = 2. Для поиска абсолютных экстремумов на множестве критических точек вычислим и сравним значения оптимизируемой функции в этих точках: f 0  x2   6 3 6 3 , f 0  x3    , f0(x4) = 0, f0(x5) = 25. 25 5 25 5 Таким образом, в рассмотренной задаче абсолютный максимум величиной Smax=25 S min   достигается в точке xˆ  2 , абсолютный минимум величиной 6 3 3 в точке xˆ  . 5 25 5 Для функции нескольких аргументов f 0 (x 1 ,x 2 ,…,x n ) первое необходимое условие принимает вид f 0 f 0 f   ...  0  0 и позволяет получить систему x1 x2 xn алгебраических уравнений для нахождения стационарных точек. Второе необходимое условие состоит в том, чтобы в стационарной точке матрица вторых частных производных (матрица Гессе) была неотрицательно определенной (синоним - положительно полуопределенной) для минимума или неположительно определенной (отрицательно полуопределенной) для максимума. Достаточное условие локального минимума состоит в положительной определенности матрицы Гессе в стационарной точке. Для локального максимума 19 достаточно, чтобы матрица Гессе в стационарной точке была отрицательно определенной. Матрица Гессе составляется следующим образом:  2 f0 H xi x j  2 f0 x1x1  2 f0  x x 2 1   2 f0 xn x1  2 f0 x1x2  2 f0 x2 x2   2 f0 xn x2  2 f0 x1xn  2 f0  x2 xn .    2 f0  xn xn  Требуемые свойства для нее проверяются с помощью критерия Сильвестра, предусматривающего анализ n угловых миноров матрицы Гессе:  f0  f0 x x ,  2  21 1 1  x1x1  f0 x2 x1 2 2 Условие  2 f0 x1x1  2 f0  2 f0 x1x2 , …,  n  x x 2 1  2 f0  x2 x2  2 f0 xn x1 положительной  2 f0 x1x2  2 f0 x2 x2   2 f0 xn x2 полуопределенности:      2 f0 x1xn  2 f0 x2 xn . (1)   2 f0 xn xn i  0 , i=1,2,…,n; положительной определенности: i > 0, i=1,2,…,n. Условие отрицательной полуопределенности состоит в том, чтобы при всех нечетных i имело место  i  0 , при всех четных i  i  0 . Условие отрицательной определенности требует строгих неравенств и чередования знаков угловых миноров:  1 < 0,  2 > 0,…,  1n  n  0 . Пример 13. Требуется найти абсолютные экстремумы функции f 0  x   2 x12  x22  x32  7 x1  x1 x2  2 x3 на множестве (в пространстве) R3. Применим первое необходимое экстремума: 20 условие достижения локального f f f 0  4 x1  7  x2  0 , 0  2 x2  x1  0 , 0  2 x3  2  0 . x1 x2 x3 В результате решения полученных уравнений находим координаты единственной стационарной точки: x 1 =2, x 2 =1, x 3 =-1. Составим для этой точки матрицу Гессе и найдем угловые миноры: 4 1 4 1  8  1  7 ,  3  2   2  14 . H  1  2 0 , 1  4 ,  2  1 2 0 2 Так как матрица Гессе в стационарной точке является отрицательно определенной, в данной точке находится локальный максимум. Поскольку другие критические точки в рассматриваемой задаче отсутствуют, найденный локальный экстремум оказывается абсолютным. Решение задачи S ma x =8 достигается в точке xˆ  2; 1;  1 . Отметим, что в последнем рассмотренном примере рассматривалась задача на безусловный экстремум. Решение ее на основе рассмотренных условий достижения локального экстремума возможно в случае дифференцируемости оптимизируемой функции по всем аргументам, а также существования вторых производных, образующих матрицу Гессе, в стационарных точках. В предшествующем же примере 12 рассмотрена задача на условный экстремум. В процессе решения это нашло отражение путем учета границ допустимой области в множестве критических точек. Такой прием удается применять только в простейших случаях, когда размерность задачи мала и границы допустимой области заданы явно. В общем же случае, и прежде всего при наличии ограничений в форме равенств (пример 11), для решения задач на условный экстремум применяется принцип неопределенных множителей Лагранжа. Пусть требуется найти экстремумы функции дополнительных условиях f j (x 1 ,x 2 ,…,x n )=0, j=1,2,…,m. 21 f 0 (x 1 ,x 2 ,…,x n ) при m Составляется функция L X ,      j f j  x1, x2 ,..., xn  , Лагранжа где j 0 X=(x 1 ,x 2 ,…,x n ) – вектор аргументов задачи,      m ) – вектор неопределенных множителей Лагранжа, на которые накладывается единственное ограничение: они не могут быть равными нулю одновременно все. Задача поиска условного экстремума функции f0 формально сводится к поиску безусловного экстремума функции Лагранжа L n+m аргументов на основе рассмотренных выше необходимых и достаточных условий. Применение первого необходимого условия для аргументов x 1 ,x 2 ,…,x n дает систему уравнений: L  0 или xi m f j j 0 xi  j  0 , i=1,2,…,n. Применение первого необходимого условия для аргументов      m дает систему уравнений, эквивалентную дополнительным условиям задачи: L  f j x1, x2 ,..., xn   0 , j=1,2,…,m.  j Эти n+m уравнений позволяют найти n координат стационарной точки (или точек) x i , а также значения m коэффициентов  j . Отметим, что неизвестных множителей  j , вообще говоря, вводится m+1. Следует иметь в виду, что в принципе нахождение значений множителей Лагранжа не обязательно, если полученные уравнения и без этого позволяют найти x i . В противном случае обычно рекомендуется переходить к решению системы n+m уравнений с n+m неизвестными, принимая   =0 или   =1. В найденных стационарных точках анализируется матрица Гессе, составляемая для функции L. Более удобной может является другая форма второго необходимого условия: для минимума второй дифференциал 22 функции Лагранжа 2L d L   dxi dx j  x  x j i 1 j 1 i n 2 n должен быть неотрицателен, для максимума – неположителен. Пример 11 (решение). Составим функцию Лагранжа   L x, y,  0 , 1    0 f 0  x, y   1 f1  x, y    0 xy  1 x 2  y 2  4r 2 , применим первое необходимое условие и получим систему уравнений для координат стационарных точек: L   0 y  21 x  0 , x L   0 x  21 y  0 , y f1  x, y   x 2  y 2  4r 2  0 . Нетрудно убедиться, что при   =0 полученная система уравнений оказывается несовместной. Решения существуют при   =1:  1  1 2 1  1 2  1   1 2  1  1 2     x1 :  x  r 2 , x2 :  x  r 2 , x3 :  x  r 2 , x4 :  x   r 2 ,  y  r 2  yr 2  yr 2  y  r 2     причем только x3 принадлежит допустимой области. Применим для x3 второе необходимое условие с учетом  0 =1 1 =-1/2: d 2 L   1  d 2 x  1  dxdy  1  dydx   1  d 2 y  dx  dy2  0 , следовательно, в точке x3 достигается локальный максимум. Помимо x3 в число критических точек должны быть включены точки, расположенные на прямых x=0 и y=0. Для всех таких точек значение оптимизируемой функции f(x,y)=0 и только для x3 получаем f(x,y)= 2r 2 . Таким  образом, решение задачи  xˆ  r 2 , r 2 . 23 S m a x =2r 2 достигается в точке Отметим, что в рассмотренном примере, строго говоря, присутствовали ограничения в форме неравенств, которые в явной форме определяли диапазоны допустимых значений для аргументов задачи. В таком случае ограничения в форме неравенств учитываются путем расширения множества критических точек, что и было выполнено выше. В общем случае неравенства, определяющие допустимую область, могут иметь произвольный вид и не разрешаться относительно аргументов задачи. Порядок аналитического решения задачи на условный экстремум при наличии ограничений в форме неравенств для общего случая представлен, например, в пособии [18]. Там же более подробно изложены рассмотренные в настоящей главе вопросы и содержится большое количество примеров. Следует также отметить, что для большинства практических задач, в силу сложности получаемых при формализации уравнений аналитического решения достичь не удается. В таких случаях применяется метод нелинейного программирования, рассмотренный в разд. 4 настоящего пособия. Контрольные вопросы 1. В чем разница между понятиями локального и абсолютного экстремума? 2. Что такое «множество критических точек», и как оно формируется? 3. Сформулируйте необходимые и достаточные условия достижения локального экстремума для функции одной переменной, нескольких переменных. 4. Чем ограничивается возможность применения рассмотренных необходимых и достаточных условий достижения локального экстремума? 5. Когда возникает необходимость применения принципа неопределенных множителей Лагранжа и в чем он состоит? 3. МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ 24 Математическим программированием принято называть совокупность методов поиска значений аргументов x 1 ,x 2 ,…,x n , обеспечивающих достижение экстремума некоторого показателя качества W(A,x 1 ,x 2 ,…,x n ), где A – вектор параметров задачи. Название сложилось исторически и не вполне соответствует современному понятию «программирование». Тем не менее, его принято использовать как в общем смысле, так и для ряда частных методов: линейное программирование, нелинейное программирование, динамическое программирование и др. 3.1. Линейное программирование: постановка задачи, основные понятия, графическая интерпретация Общая постановка задачи линейного программирования выглядит следующим образом: требуется определить значения переменных состояния системы (аргументов) x 1 ,x 2 ,…,x n , доставляющие экстремум критерию оптимальности (целевой функции) вида n q x1, x2 ,...xn   c0   ci xi  extr (2) i 1 и удовлетворяющие системе ограничений: n  a ji xi  b j ; j=1,2,…m; xi  0 ; i=1,2,…n. (3) i 1 Отметим некоторые особенности такой задачи: - задача является статической (одношаговой) с несколькими аргументами, однокритериальной и детерминированной; - критерий оптимальности линейно зависит от аргументов, что свидетельствует об отсутствии локального экстремума и нецелесообразности решения задачи рассмотренными в подразделе 2 классическими методами; - искомый абсолютный экстремум следует искать на границах допустимой области, определяемой ограничениями (3); 25 - допустимая область задана ограничениями смешанного типа – как в форме равенств, так и неравенств, что затрудняет поиск решения на границах. С целью построения универсальной формальной процедуры решения задача сводится к более простому виду путем преобразования ограничений в форме неравенств в равенства за счет введения дополнительных переменных. n Любое неравенство вида  a ji xi  b j может быть сведено к равенству за i 1 n счет введения новой переменной:  a ji xi  xn  j  b j , причем для сохранения i 1 знака неравенства такая соответствующему (3): переменная xn  j  0 . должна Следовательно, отвечать задача требованию, линейного программирования с k ограничениями в форме равенств и l ограничениями в форме неравенств может быть сведена к задаче c k+l ограничениями только в форме равенств. При этом количество аргументов задачи увеличивается до n+l. Возможность применения такого приема позволяет рассматривать более удобную для решения общую постановку задачи линейного программирования, называемую основной задачей линейного программирования (ОЗЛП): требуется определить значения переменных состояния системы (аргументов) x 1 ,x 2 ,…,x n , доставляющие экстремум критерию оптимальности (целевой функции) вида n q x1, x2 ,...xn   c0   ci xi  extr и удовлетворяющие системе ограничений: i 1 n  a ji xi  b j ; j=1,2,…m; xi  0 ; i=1,2,…n. (4) i 1 Корректной является только задача, в которой m2. В таком случае получаем дополнительную область в n–mмерном пространстве в виде выпуклого многогранника, вершины которого соответствуют допустимым базисным решениям. Выражение для q определяет гиперплоскость. Экстремум q будет достигнут, когда она будет проходить через одну из вершин многогранника. Однако применение графического метода здесь, очевидно, неудобно. Отметим также, что поскольку количество базисных решений в задаче линейного программирования ограничено, решение любой такой задачи в принципе достигается путем их перебора с проверкой допустимости и вычислением значения целевой функции. Но если размерность задачи велика, желателен целенаправленный перебор. Наиболее популярным методом целенаправленного поиска решения задачи линейного программирования, является симплекс-метод. 3.2. Симплекс-метод Общая схема симплекс-метода состоит в следующем: 1. Находится базис, обеспечивающий допустимое базисное решение. 29 2. Производится проверка, доставляет ли найденный базис максимум целевой функции. При положительном результате проверки решение задачи найдено. 3. Если установлено, что максимум целевой функции не достигнут, выбирается новый базис таким образом, чтобы значение целевой функции увеличивалось, а базисное решение оставалось допустимым. Находится соответствующее базисное решение. 4. Пункты 2-3 повторяются до получения решения задачи. В дополнение следует отметить, что ниже, как и в большинстве источников [4, 5, 18], рассматриваются алгоритмы симплекс-метода, ориентированные на достижение максимума целевой функции. 3.2.1. Алгебраический вариант Вернемся к примеру 14. Если выбрать переменные x 1 и x 2 в качестве свободных, то заданное в условиях примера выражение для целевой функции и соотношения (6) будут позволять вычислять целевую функцию и базисные переменные непосредственно по значениям свободных переменных. В таком случае говорят, что получено разложение целевой функции и базисных переменных по свободным. Удобство такого разложения состоит, прежде всего, в том, что его свободные члены дают базисное решение и соответствующее ему значение q без вычислений. Кроме того, разложение целевой функции по свободным переменным обеспечивает достаточно простую проверку достижения экстремума, а в случае необходимости и определение пути необходимого преобразования базиса. Переход к новому базису можно осуществить, сделав одну из свободных переменных базисной. Если такой новый базис даст допустимое базисное решение, эта переменная возрастет (или сохранит нулевое значение в частном случае). Если эта переменная входит в разложение q со знаком «+», такой новый 30 базис даст (за исключением указанного частного случая) увеличение значения q. Следовательно, максимум целевой функции пока не достигнут и новый базис должен быть сформирован путем перевода такой свободной переменной в число базисных. Если все свободные переменные входят в разложение целевой функции со знаком «-», текущий базис (при условии допустимости базисного решения) дает решение задачи. В рассматриваемом примере разложение целевой функции по свободным переменным имеет вид q=x 1 -x 2 . Текущий базис не обеспечивает максимума целевой функции. Ее значение может быть увеличено путем перевода свободной переменной x 1 в число базисных. Очевидно, что в конкретной задаче для любого базиса количества базисных и свободных переменных должны оставаться постоянными. Поэтому необходимо выбрать одну из текущих базисных переменных, которая должна быть переведена в число свободных. Такой выбор можно сделать путем анализа разложения базисных переменных по свободным. Переход к новому базису желательно выполнить так, чтобы получить допустимое базисное решение. Поэтому в качестве новой свободной переменной следует выбрать ту базисную переменную, которая раньше других обратится в ноль при увеличении новой базисной переменной. В рассматриваемом примере новой базисной переменной является x1. Проанализируем на основе разложения базисных переменных (6) их возможное изменение при увеличении x1, имея в виду, что их исходные значения при x1=0 равны свободным членам в правых частях уравнений. Очевидны следующие выводы: - значение переменной x3 может только возрасти, x4 и x5 могут достичь отрицательных значений; 31 - в качестве новой свободной переменной целесообразно выбрать x4, для которой в разложении (6) отношение коэффициента при x1 к свободному члену наибольшее. Таким образом, выбран новый базис: x1, x3, x5. Следующим шагом является переход к разложению целевой функции и новых базисных переменных по свободным переменным x2 и x4: x 1 =2+2x 2 –x 4 , x 3 =2+4+4x 2 –2x 4 –x 2 =6+3x 2 –2x 4 , x 5 =5–2–2x 2 +x 4 –x 2 =3–3x 2 +x 4 , q=2+2x 2 –x 4 –x 2 =2+x 2 –x 4 . Новое базисное решение x 1 =2, x 3 =6, x 5 =3 является допустимым, значение целевой функции увеличилось, но максимум не достигнут (коэффициент при x 2 в выражении для q положителен). Используя полученные выше правила, выбираем новый базис: x1, x2, x3. Перейдем к нему: x2  1  x1  2  2  x4 x5  , 3 3 2 2 x 2 x4  x5  x4  4  4  x5 , 3 3 3 3 x 3 =6+3+x 4 –x 5 –2x 4 =9–x 4 –x 5 , q  2 1 x4 x5 2 x   x4  3  x4  5 . 3 3 3 3 Полученное базисное решение x 1 =4, x 2 =1, x 3 =9 является допустимым. Максимум целевой функции достигнут, q=3. Рассмотренный способ решения задачи линейного программирования непосредственно пригоден для программной реализации, но более удобным с этой точки зрения является табличный вариант симплекс-метода, в рамках которого 32 рассмотренные преобразования уравнений сведены к последовательности простых расчетных операций над коэффициентами. 3.2.2. Табличный вариант Вводится специальная форма записи разложения целевой функции и базисных переменных по свободным. Обозначим через xi , i=1,2,…,m базисные переменные и через xj , j=1,2,…,n–m свободные переменные. Выразим q и xi через xj и введем новые обозначения коэффициентов: q   00  xi  i 0  nm  0 j xj , j 1 nm  ij xj , i=1,2,…,m. j 1 Теперь задача может быть представлена матрицей коэффициентов:  00 10 ...  m0  01 11 ...  m1 ...  0 n  m ... 1n  m . ... ... ...  m n  m (7) Первый столбец данной матрицы содержит свободные члены разложения целевой функции и базисных переменных и дает базисное решение. Признаком допустимости решения является неотрицательность всех элементов данного столбца, кроме 00. Первая строка матрицы содержит коэффициенты разложения целевой функции. Неотрицательность всех элементов первой строки, кроме 00, является признаком оптимальности решения. Остальные строки матрицы содержат коэффициенты разложения базисных переменных. Каждая строка соответствует одной из базисных переменных, номер которой совпадает с первым индексом элементов строки. 33 Отметим также, что каждый столбец матрицы, кроме первого, соответствует одной из свободных переменных, номер которой совпадает со вторым индексом элементов столбца, и содержит коэффициенты разложения при данной переменной, взятой со знаком «-». Каждому базису, выбираемому при решении конкретной задачи, будет соответствовать свой вариант матрицы. Анализ знаков элементов первого столбца и первой строки позволяет проверять допустимость и оптимальность текущего базисного решения. В случае невыполнения рассмотренных условий тот же анализ позволяет выбрать новый базис. Переход к новому базису удобнее выполнять на основе специальной таблицы, соответствующей матрице (7), называемой планом, или линейным планом (таблица 1). В левый верхний угол ячеек плана заносятся коэффициенты разложения, матрицей «старыми» представленные (7). Их Таблица 1. Общий вид линейного плана. называют коэффициентами. В случае перехода к новому плану в правый нижний угол заносятся q промежуточные x1 значения расчетные коэффициентов, называемые «новыми». При анализе - x1 1 00 *01  *00 10 11 * 10 …  xm 01 * 11 … m0 … m1  *m 0 *m1 … - xn- m … 0 n-m *0 n m … 1 n-m 1*n m … … … m n-m *m n  m представленного планом базисного решения и выборе нового плана используются «старые» коэффициенты. Анализ допустимости и оптимальности базисного решения на основе плана выполняется аналогично анализу матрицы (7). Правила выбора нового базиса состоят в следующем: - в базисные переводится свободная переменная коэффициент первой строки отрицателен (j*=j:  0 j <0); 34 xj * , для которой - если базисное решение является недопустимым, в свободные переводится базисная переменная xi* , для которой коэффициент первого столбца отрицателен (i*=i:  i 0 <0); - если базисное решение является допустимым, в свободные переводится базисная переменная, для которой отношение коэффициентов ij* i 0 максимально. Если рассматриваемому условию отвечают две или более переменных, из них обычно рекомендуется выбирать переменную с меньшим индексом. Аналогичная рекомендация используется по отношению ко всему набору свободных переменных, если при недопустимом базисном решении все коэффициенты первой строки плана неотрицательны. Отметим, что данная рекомендация не является строгой и ее не следует применять в том случае, когда она приводит к выбору уже рассмотренного для решаемой задачи базису (при проверке достаточно учесть предшествующий план). Правила перехода к новому плану состоят в следующем: 1. Выделяют строку и столбец, соответствующие выбранным выше базисной xi* и свободной xj * переменным. «Старый» коэффициент в ячейке на их пересечении   i* j * называют генеральным коэффициентом. «Новый» коэффициент для этой ячейки вычисляется как *i* j*  1  . 2. «Новые» коэффициенты выделенной строки получают путем деления «старых» на : *i* j  i * j  . 3. «Новые» коэффициенты выделенного столбца получают путем деления «старых» на -: *ij*   ij*  . 35 4. Для остальных ячеек плана «новые» коэффициенты вычисляются по формуле: *ij  i* j *ij* . 5. В новом плане переменные xj * и xi* меняют местами, сохраняя для остальных переменных прежнее расположение по строкам и столбцам. 6. В i*-ю строку и j*-й столбец нового плана переносят «новые» значения коэффициентов из соответствующих строки и столбца старого плана. 7. В остальные ячейки нового плана заносят суммы «старых» и «новых» коэффициентов из соответствующих ячеек старого плана: ij  *ij . Все полученные коэффициенты заносятся в верхний левый угол ячеек нового плана и используются для анализа нового базисного решения. Вернемся к примеру 14. Исходному базису x3, x4, x5 соответствует план, представленный в таблице 2. Коэффициенты первого столбца неотрицательны. В первой строке содержится отрицательный коэффициент. Соответствующее плану базисное решение допустимо, но не оптимально. В базисные должна быть переведена свободная переменная x1, которой соответствует отрицательный коэффициент первой строки. Соответствующий ей столбец выделен на плане. Отношения коэффициентов выделенного и первого столбцов для базисных переменных x3, x4, x5 составляют соответственно: -1; 0,5; 0,2. В свободные должна быть переведена базисная переменная x4. Соответствующая ей строка также выделена. Полученный по указанным выше правилам новый план представлен в таблице 3. Полученное базисное решение допустимо, но не оптимально. Для следующего преобразования плана аналогично предыдущему случаю выбраны свободная переменная x2 и базисная переменная x5. Следующий план представлен в таблице 4. Полученное базисное решение допустимо и оптимально, следовательно, решение задачи достигнуто: x 1 =4, x 2 =1, x 3 =9, x 4 =x 5 =0, q=3. 36 37 Таблица 2. 1 -x1 Таблица 3. -x2 -1 1 1 -x4 2 q 1 -x2 1 -1 q 2 2 1 -2 1 6 x3 -1/3 2 2 1 2 3 2 x4 -3 -1 5 1 1 1 2 3 x5 -2 -2/3 -1 2 9 1 1 4 1/3 2/3 -1 1 -1/3 1/3 2/3 3 x5 -2 1/3 x1 -2 1 2/3 1 x1 2 3 x3 -4 -2 -x5 1/3 x3 4 -x4 q -2 1 Таблица 4. x2 1 -1/3 1/3 3.3. Решение задач дискретного линейного программирования Задача линейного программирования усложняется, если на все или некоторые переменные накладываются дополнительные ограничения вида xi целая величина, или xi - дискретная величина (с заданным множеством возможных значений). Симплекс-метод в своем исходном рассмотренном выше варианте таких ограничений не учитывает. Развитие симплекс-метода для решения задач целочисленного и дискретного программирования обеспечивается в рамках семейства алгоритмов, или метода, Гомори [18]. 38 Основная идея метода Гомори состоит в исключении из допустимой области оптимальных решений, получаемых стандартным симплекс-методом, но не удовлетворяющих требованию целочисленности или дискретности. Это обеспечивается путем построения дополнительных границ допустимой области. Рассмотрим формальную процедуру решения полностью целочисленной задачи линейного программирования (на все переменные наложено требование целочисленности), называемую также первым алгоритмом Гомори. 1. Задача приводится к форме ОЗЛП и далее к линейному плану. 2. Стандартным симплекс-методом без учета требований целочисленности находится допустимое и оптимальное базисное решение. 3. Если получено целочисленное решение, оно является окончательным. 4. Если полученное решение не является целочисленным, строится дополнительная граница допустимой области – «правильное отсечение» по одной из переменных, для которой найденное значение нецелое. Это приводит к повышению размерности рассматриваемой ОЗЛП, появлению дополнительной базисной переменной и новой строки линейного плана. Принцип построения правильного отсечения таков, что получаемый новый план оказывается заведомо не допустимым. 5. Пункты 2-4 повторяются до получения допустимого и оптимального целочисленного решения. Правильное отсечение по некоторой базисной переменной xl определяется условием:  l 0   nm   lj  xj   0 , (8) j 1 где l0 – свободный член; lj – коэффициенты при свободных переменных в разложении xl по свободным переменным, полученном на шаге 2 алгоритма, то есть коэффициенты строки полученного линейного плана;  - дробная часть 39 числа  (разность данного числа и его целой части – наибольшего целого, не      , : превосходящего 1,25  1,25  1  0,25 ,  1,25  1,25   2  0,75 ). Для учета  1  l 0   xm условия nm (8)   lj   xj , вводится новая базисная переменная  1  0 . Ее появление вызывает добавление к xm j 1 построенному оптимальному нецелочисленному плану дополнительной строки с отрицательным элементом   l 0  в первом столбце, чем и определяется дальнейшая процедура преобразования плана. Если для промежуточного оптимального плана несколько базисных переменных оказались нецелочисленными, наиболее простая рекомендация состоит в выборе в качестве xl нецелочисленной базисной переменной с меньшим индексом, если только она уже не выбиралась для предшествующего отсечения. Пример 15. Определить значения переменных состояния системы x 1 ,x 2 , доставляющие максимум целевой функции q=-x 1 -x 2 с учетом ограничений: 5 x1  x2  12 , x1  3 x2  15 , xi  0 ; i=1,2; x 1 ,x 2 – целые. Преобразуем задачу в форму ОЗЛП с двумя базисными и двумя свободными переменными, вводя две новые переменные: x3  12  5 x1  x2  0 , x4  15  x1  3x2  0 , и составим линейный план (таблица 5). Решение преобразований нецелочисленной плана (таблицы задачи 6,7). симплекс-методом Оптимальное требует базисное двух решение представлено в таблице 7. Оно оказалось нецелочисленным. Правильное отсечение по переменной x1 приводит к дополнению задачи базисной переменной 40 x5 и соответствующей строкой таблицы. Значение x5=-1/2 отрицательно, что требует повторного решения нецелочисленной задачи (таблица 8). Таблица 5. 1 -x1 Таблица 6. -x2 1 1  12 1 q q  12 1 5 -12 1 5 -5 -1 5 -15 1 5 -1 x4 5 5 2 5 1 1 5 9  63 -3 1 4 5 5 2 35 7 1 5 1 10 5 1 14 70 5 x5 12  18 12 x1 1 1 5 -x2 5 x4 12 -x3 5 41 1 5 9 2  14 5 1 14 5 5 14 Таблица 7. 1 -6 -x3 1 7 Таблица 8. -x4 2 1 -x3 -6 7 q 1 2 7 q 2 1 11 3 x1 9 x2 1 14 2 1 x5 3 14 2 2  11 14 3 1 14 x1 5 14 x2 1 14 1 1 x5 1 11 22  11 14 2 7 11 77 3 154 5 14 1 14 2 1 1 14 3 11 22 7 11 3 14 2 3 9 -x4  14 1 154 1 14 11 1 11 В таблицах 9-12 представлены последующие преобразования задачи, связанные с введением дополнительных отсечений (попеременно по x2 и по x1). Окончательное решение представлено таблицей 13. 42 Таблица 9. 1  67 q x1 49 x6 77 3 1  14 11 5 77 5 7 3 1 x2 7 7 x3  11 36 5 x4 7 4 43 1 5 4 5 9 5 1 7 5 35 7 1 5 7 35 7  11 35 7 1 1 7 35 7 5 7 9 1 4 x7 1 35 7 2 4 35 35 7 5 7 9 1 1 2 7 5 7 35 7 7 11 1 1 4 3 35 7 7 4 1 77 8 -x6 7 2 7 1 11 1 7 7 33 4 77 1 x1 11 -x5 4 7 11 77 11 1 q 1 11 1 11 11  44 77 4 4 77 1 3 11 11 1 11 11 5 -x4 3 11 20 7 77 11 5 x2 2 11  15 18 x3 -x5 Таблица 10. 35 7 1 5 Таблица 11. 1  32 q 2 x2 9 8 x3 3 3 x4 1 12 4 3 3 2 -1 3 2 1 -2 2 2 1 2 1 2 1 1 1 2 1 2 2 2 x2 5 5 2 1 2 1 8 3 5 -4 1 2 -4 x4 5 1 5 1 2 5 2 -1 -4 1 5 1 11 3 1 10 1 5 1 2 5 1 2 x1 x3 5 7 3 10 3 1 2 5 4 1 5 3 5 5 1 1 -x8 1 3 10 5 5 -7 5 5 9 5 -x7 q 5 10 1 5 1 10 1 5 2 1 3 10 23 -x6 5 5 5 x1 x8 1 5 3 9 x5 -x7 Таблица 12. 5 3 2 3 5 x6 2 44 3 2 x5 2 2 2 -3 1 1 1 2 3 2 2 -1 5 2 1 2 2 1 2 1 1 2 1 2 2 x9 1 -2 1 Таблица 13. 1 q x1 x2 x3 x4 x5 x6 x7 -x9 -7 2 5 3 2 2 1 1 -1 1 -4 2 -3 1 -2 Полученное -x8 1 1 -2 3 -5 2 -3 1 базисное решение допустимо, оптимально и целочисленно, следовательно, решение задачи достигнуто: x 1 =2, x 2 =5, q=-7. Известны Гомори, другие алгоритмы обеспечивающие решение неполностью и целочисленной задачи, исключение влияния ошибок округления при проверке целочисленности решения, решение дискретных задач общего вида. 3.4. Двойственная задача линейного программирования Рассмотрим две задачи линейного программирования, представленные в форме ОЗЛП. Первая задача с m базисными и l=n-m свободными переменными с записью в алгебраической форме: l q   00    0 j xj  max , j 1 l xi  i 0   aij xj  0 , i=1,2,…,m j 1 или в форме матрицы коэффициентов 45 (9)  00 10 ...  m0  01 11 ...  m1 ...  0 l ... 1l . ... ... ...  m l (10) Вторая задача с l базисными и m свободными переменными с записью в алгебраической форме: m q   00   i 0ui  min , i 1 m uj   0 j   aijui  0 , j=1,2,…,l (11) i 1 или в форме матрицы коэффициентов  00  01 ... 0 l 10 11 ... 1l ...  m 0 ...  m1 . ... ... ...  m l (12) Отметим следующее: 1. Строки и столбцы матрицы (10) совпадают соответственно со столбцами и строками матрицы (12). 2. Как было показано в пункте 3.2.2, неотрицательность элементов первого столбца и первой строки матрицы (10) без учета 00 являются условиями соответственно допустимости и оптимальности представленного матрицей базисного решения первой задачи. 3. Аналогично пункту 3.1.1 нетрудно установить, что для достижения минимума целевой функции достаточно, чтобы все коэффициенты ее разложения по свободным переменным (кроме 00) были положительны. Таким образом, неотрицательность элементов первого столбца и первой строки матрицы (12) без учета 00 являются условиями соответственно допустимости и оптимальности представленного матрицей базисного решения второй задачи. 46 4. С учетом непосредственной связи матриц (10) и (12) можно сделать вывод о том, что решение первой задачи дает и решение второй, и наоборот. Здесь не приводится строгое доказательство обнаруженного свойства задач линейного программирования. Тем не менее, представленных рассуждений достаточно для того, чтобы убедиться в его наличии, по крайней мере, для задач, имеющих единственное решение. Пример 16. Определить значения переменных состояния системы x 1 ,x 2 , x 3 ,x 4 , доставляющие максимум целевой функции q=x 1 -x 2 с учетом ограничений: x3  2  x1  2 x2 , x4  5  x1  x2 , xi  0 ; i=1,2,3,4. Задача представлена в форме разложения целевой функции q и базисных переменных x 3 ,x 4 по свободным переменным x 1 ,x 2 . Исходный линейный план представлен таблицей 14. Таблица 14. 1 -x1 Таблица 15. -x2 -1 1 1 -x3 2 q 2 2 1 1 1 -2 2 x3 2 5 1 1 2 1 3 x4 -2 -1 2 3 -1 1 47 3 1 3 2 4 1 1 1 -x4 1 3 3 3 x1 2 3 3 3 3 1 x4 2 -x3 q -2 2 -2 1 3 1 x1 1 -1 1 -2 -x2 1 q Таблица 16. 3 x2 3 1 3 Решение задачи после двух преобразований плана представлено в таблице 16: x 1 =4, x 2 =1, x 3 =x 4 =0, q=3. Пример 17. Определить значения переменных состояния системы u 1 ,u 2 , u 3 ,u 4 , доставляющие минимум целевой функции q=2u 1 +5u 2 с учетом ограничений: u3  1  u1  u2 , u4  1  2u1  u2 , ui  0 ; i=1,2,3,4. Изменив знак целевой функции q  2u1  5u2 , получим привычную задачу на максимум, представленную разложением целевой функции q  и базисных переменных u 3 ,u 4 по свободным переменным u 1 ,u 2 . Исходный линейный план представлен таблицей 17. Решение задачи после двух преобразований плана представлено в таблице 19: u 1 = 2 , u 2 = 1 , x 3 =x 4 =0, q  3 и соответственно q=3. 3 3 Сравнивая первые строки и столбцы таблиц 16 и 19, можем убедиться в справедливости сформулированных выше выводов. Первую из рассмотренных задач (задачу на максимум целевой функции, пример 16) принято называть основной, вторую (задачу на минимум, пример 17) – двойственной. Очевидно, что несложные позволяют поменять их местами. 48 алгебраические преобразования Таблица 17. 1 -u1 Таблица 18. -u2 2 1 5 -u3 -2 -u2 2 1 3 -2 -1 2 -1 -1 -2 -1 1 u3 1 -1 2 -1 4 1 2 1 1 1 2 3 -1 u4 2 -3 -u4 1 3 u1 3 3 1 3 3 1 u4 -2 2 -1 1 u1 1 -u3 q q q Таблица 19. 2 1 -3 2 3 3 1 1 3 u2 3 2 3 1 3 -2 С практической точки зрения эффект двойственности существенного значения для решения задач линейного программирования не имеет, так как реальных задач, формализуемых в форме двойственных, не много [5]. Тем не менее, это свойство оказывается весьма важным, так дает основу применения симплекс-метода для решения задач теории игр, которые будут рассмотрены ниже. 3.5. Нелинейное программирование Общая постановка задачи нелинейного программирования выглядит следующим образом: требуется определить значения переменных состояния системы (аргументов) x 1 ,x 2 ,…,x n , доставляющие оптимальности (целевой функции) вида 49 экстремум критерию q  f  x1, x2 ,...xn  (13) и удовлетворяющие системе ограничений: z j x1, x2 ,...xn   0 ; j=1,2,…m; xi  0 ; i=1,2,…n, (14) где, по крайней мере, одна их функций f, z j – нелинейная. Последнее требование обуславливает главное отличие такой задачи от задачи линейного программирования – возможность наличия локального экстремума внутри допустимой области, определяемой неравенствами (14), и более сложную форму границ этой области. Очевидно, задача линейного программирования представляет собой частный случай рассматриваемой задачи. Универсального точного алгоритма решения задач нелинейного программирования не существует. Рассмотрим ряд методов их решения, имея в виду, что весь их перечень значительно шире и остается открытым. 3.5.1. Обобщенный метод множителей Лагранжа, условия Куна-Таккера Основная идея обобщенного метода множителей Лагранжа опирается на следующий факт: если точка безусловного экстремума f(X), где X=(x 1 ,x 2 ,…,x n ) – вектор аргументов, не удовлетворяет всем ограничениям задачи или безусловный экстремум отсутствует, то условный экстремум должен достигаться в граничной точке допустимой области. Это означает, что одно или несколько ограничений из общего числа m должны выполняться как точные равенства. На основе этого факта может быть построена процедура поиска экстремума, включающая следующие шаги. 1. Решить задачу без учета ограничений, т.е. найти безусловный экстремум f(X). Если точка полученного экстремума удовлетворяет всем ограничениям, прекратить вычисления, так как все ограничения оказываются избыточными. В противном случае положить k=1 и перейти к шагу 2. 2. Сделать любые k ограничений активными, т.е. превратить их в равенства, и найти экстремум f(X) при наличии k активных ограничений с помощью метода 50 множителей Лагранжа. Если полученное решение окажется допустимым по отношению к остальным ограничениям, то прекратить вычисления; локальный экстремум будет найден. В противном случае сделать активными другие k ограничений и повторить данный шаг. Итоговое решение выбирается из всех экстремумов, полученных в результате решения оптимизационных задач с целевой функцией f(X), возникающих при учете всех комбинаций k ограниченийравенств. Если все подмножества, состоящие из k активных ограничений, не приводят к получению допустимого решения, перейти к шагу 3. 3. Если k=m, прекратить вычисления; допустимых решений не существует. В противном случае положить k=k+1 и перейти к шагу 2. С описанной выше процедурой связано важное обстоятельство, которое часто не принимается во внимание. Процедура не гарантирует получения абсолютного экстремума даже в тех случаях, когда задача имеет единственное оптимальное решение. Не менее важно отметить ошибочность интуитивного представления о том, что при k 1 0, то s 2j  0 . Это означает, что соответствующий рассматриваемому ограничению ресурс дефицитный и, следовательно, исчерпан полностью (ограничение становится равенством). 2. Если s 2j  0 , то j=0. Это означает, что j-й ресурс не дефицитный и, следовательно, изменение его количества не оказывает влияния на значение функции Лагранжа. Из второй и третьей групп уравнений следует:  j z j (X)=0, j=1,2,…m. Теперь можно сформулировать необходимые условия Куна-Таккера, которым должны удовлетворять векторы X и , определяющие стационарную точку в задаче минимизации: j0, j=1,2,…m; m z j L f    j  0 ; i=1,2,…n; xi xi j 1 xi jz j (x 1 ,x 2 ,..,x n )=0, j=1,2,…m; jz j (x 1 ,x 2 ,..,x n )0, j=1,2,…m. Необходимые условия Куна-Таккера являются также достаточными, если целевая функция и область допустимых решений обладают определенными свойствами, связанными с выпуклостью и вогнутостью. 55 Выше изложены основы классической теории поиска точек максимумов и минимумов в нелинейных задачах с ограничениями. Классическая теория мало подходит для практического применения. Однако в ряде случаев теоретические построения Куна-Таккера служат основой для создания эффективных алгоритмов. Следует подчеркнуть, что для нелинейных задач с ограничениями в виде неравенств нет достаточных условий существования экстремума (подобных условиям для задач без ограничений и задач с ограничениями-равенствами). Таким образом, за исключением случаев, когда такие условия можно установить заранее, не существует какого-либо приемлемого способа проверить, какой оптимум получен с помощью того или иного алгоритма нелинейного программирования  локальный или глобальный. Точка экстремума целевой функции совпадает с седловой точкой функции Лагранжа, если рассматривать ее как функцию двух аргументов X, . Подробно понятие седловой точки и условия достижения решения задачи рассмотрим сначала для простейшего случая L(X,)=F(x,), допускающего геометрическую интерпретацию. Для функции двух переменных F(x,) точка (x 0 , 0 ), в которой функция F(x, 0 ) имеет минимум по x, а функция F(x 0 ,) имеет максимум по , называется седловой точкой. Формально это определение можно записать следующим образом: F  x0 ,    F  x0 ,  0   F  x,  0  для некоторой окрестности точки (x 0 , 0 ). Для удобства примем, что допустимая область значений переменных ограничена неравенствами: x  0 и   0 . Седловая точка может быть расположена как внутри, так и на границе допустимой области. Первый вариант показан на рис. 10. Ему соответствуют следующие условия: 56 F F  0,  0.  x0 ,  0 x x0 ,  0 Здесь и далее используется сокращенная запись: (15) F F .  x x0 ,  0 x x  x0 ,    0 Варианты для второго случая приведены на рис. 11. 57 Рис. 11, а соответствуют условия: x 0 =0, F F  0,  0. x x0 ,  0  x0 ,  0 (16)  0 =0, F F  0,  0.  x0 ,  0 x x0 ,  0 (17) Для рис. 11, б: Объединив условия (15)-(17), получим первое необходимое условие достижения седловой точки в форме следующей системы: F F F F  0,  0 , x0   0.  0 , 0   x0 ,  0 x x0 ,  0  x0 ,  0 x x0 ,  0 (18) Второе необходимое условие состоит в выпуклости функции F по аргументу x и вогнутости по : F x,  0   F x0 ,  0   F x F x0 ,    F x0 ,  0   F  x0 ,  0 x0 ,  0   x  x0  ,     0  . (19) Если условия (19) выполняются для всей допустимой области значений аргументов задачи, точка (x 0 , 0 ), найденная в соответствии (18), является глобальной седловой точкой, т.е. дает искомое решение задачи. В противном случае в задаче возможно наличие нескольких локальных седловых точек, для которых условия (19) выполняются в некоторой окрестности. Для функции многих аргументов понятие седловой точки аналогично: если для части аргументов выполняются необходимые условия минимума, для остальных аргументов – максимума. Известно, что большинство задач нелинейного программирования сводится к поиску седловой точки функции Лагранжа, рассматриваемой как функция двух аргументов: L(X,), причем по составляющим вектора X (переменным задачи) 58 требуется достижение минимума, по составляющим вектора  (множителям Лагранжа) – максимума. 3.5.2. Случайный поиск экстремума Если задачу нелинейного программирования требуется решить однократно, наиболее просто это выполнить методом случайного поиска (методом МонтеКарло) [6, 16]. Процедура случайного поиска экстремума может быть сформулирована следующим образом: 1. Путем n независимых обращений к генератору случайных чисел, где n – количество аргументов в задаче, формируется случайная точка x 1 l ,x 2 l ,…,x n l . 2. Вычисляется значение целевой функции ql=f(x 1 l ,x 2 l ,…,x n l ) в данной точке. 3. После многократного повторения пунктов 1,2 в качестве решения задачи выбирается такая из рассмотренных точек, в которой значение q оказалось наибольшим (наименьшим). Такая процедура легко программируется и при достаточно большом количестве опытов (например, 106-107), ограничиваемом лишь производительностью компьютера, позволяет получить достаточно точное решение задачи, независимо от вида функций f, z j . Для повышения точности решения рассмотренная процедура может быть повторена для некоторой малой окрестности найденной точки. Рассмотренная процедура является одним из простейших примеров применения метода Монте-Карло, более подробно рассмотренного в пособии [6]. Там же можно найти рекомендации по построению моделирующих соотношений для п.1 рассмотренной процедуры. Здесь следует особо отметить, что для корректного решения задачи необходимо обеспечивать точное соответствие диапазонов генерируемых случайных значений аргументов задачи границам 59 допустимой области. Если явное определение таких границ по соотношениям (14) затруднительно, рекомендуется генерировать значения аргументов в широком диапазоне, заведомо перекрывающем допустимую область, а п. 2 выполнять только для таких точек x 1 l ,x 2 l ,…,x n l , в которых ограничения (14) выполняются. Несмотря на универсальность и простоту процедуры случайного зондирования, ею нельзя ограничиваться ввиду значительной вычислительной трудоемкости. Поэтому большее распространение получили методы направленного поиска решения. 3.5.3. Методы безусловной оптимизации Необходимые условия достижения экстремума во всех рассмотренных выше формах приводят к решению системы нелинейных уравнений. Решение систем нелинейных уравнений - задача весьма сложная и трудоемкая (даже в вычислительной математике чаще сводят решение нелинейных уравнений к некой задаче оптимизации). Поэтому на практике используют другие подходы к оптимизации функций, рассмотрение которых начнем с так называемых прямых методов. В дальнейшем здесь будем говорить о минимизации, поэтому экстремум – это минимум. В настоящее время разработано множество численных методов для задач как безусловной, так и условной оптимизации. Качество численного метода характеризуется многими факторами: скоростью сходимости, временем выполнения одной итерации, объемом памяти ЭВМ, необходимым для реализации метода, классом решаемых задач и т. д. Решаемые задачи также весьма разнообразны: они могут иметь высокую и малую размерность, быть унимодальными и многоэкстремальными и т. д. Один и тот же метод, эффективный для решения задач одного типа, может оказаться совершенно неприемлемым для задач другого типа. 60 Ниже приводится обзор основных методов решения задач нелинейного программирования. Следует иметь в виду, что весь перечень таких методов весьма широк и остается открытым. Кроме того, для ряда рассматриваемых методов известны различные модификации. Более подробную информацию можно получить, например, в [18, 25]. Начнем с рассмотрения прямых методов безусловной оптимизации, когда ограничения отсутствуют. Смысл прямых методов безусловной оптимизации состоит в построении последовательности точек X[0], X[1], …, X[N], таких, что f(X[0])>f(X[1])>… …>f(X[n]). В качестве начальной точки X[0] может быть выбрана произвольная точка, однако стремятся ее выбрать как можно ближе к точке минимума. Переход (итерация) от точки Х[k] к точке Х[k+1], k=0,1,2,... состоит из двух этапов: - выбор направления движения из точки Х[k]; - определение шага вдоль этого направления. Методы построения таких последовательностей часто называют методами спуска, так как осуществляется переход от больших значений функции к меньшим. Математически методы спуска описываются соотношением: X[k+1]=X[k]+a k p[k], k=0,1,2,..., где p[k] – единичный вектор, определяющий направление спуска; a k – длина шага. Различные методы спуска отличаются друг от друга способами выбора этих двух параметров. На практике применяются только методы, обладающие сходимостью. Они позволяют за конечное число шагов получить точку минимума или подойти к ней достаточно близко. Качество сходящихся итерационных методов оценивают по скорости сходимости. При использовании методов спуска также следует иметь в виду, что в отличие от метода Монте-Карло они в общем случае не гарантируют нахождения 61 абсолютного экстремума в многоэкстремальной задаче. В зависимости от выбора исходной точки в качестве решения задачи формально может быть обнаружен, например, ближайший локальный экстремум. Избежать получения неверных практических выводов в таких ситуациях можно, имея возможность применять для решения задачи разные методы или повторно решать задачу, меняя исходную точку. Теоретически в методах спуска решение задачи получается за бесконечное число итераций. На практике вычисления прекращаются при выполнении некоторых критериев (условий) останова итерационного процесса. Например, это может быть условие малости приращения аргумента X k   X k  1   или функции f  X k   f  X k  1   . Здесь k - номер итерации; ,  - заданные величины точности решения задачи. Методы поиска точки минимума называются детерминированными, если оба параметра перехода от X[k] к X[k+1] (направление движения и величина шага) выбираются однозначно по доступной в точке X[k] информации. Если же при переходе используется какой-либо случайный механизм, то алгоритм поиска называется случайным поиском минимума. Детерминированные алгоритмы безусловной минимизации делят на классы в зависимости от вида используемой информации. Если на каждой итерации используются лишь значения минимизируемых функций, то метод называется методом нулевого порядка. Если, кроме того, требуется вычисление первых производных минимизируемой функции, то имеют место методы первого порядка, при необходимости дополнительного вычисления вторых производных - методы второго порядка. Следует отметить, что при решении задач безусловной минимизации методы первого и второго порядков обладают, как правило, более высокой скоростью сходимости, чем методы нулевого порядка. Однако на практике 62 вычисление первых и вторых производных функции большого количества переменных весьма трудоемко. В ряде случаев они не могут быть получены в виде аналитических функций. Определение производных с помощью различных численных методов осуществляется с ошибками, которые могут ограничить применение таких методов. Кроме того, критерий оптимальности может быть задан не в явном виде, а системой уравнений. В этом случае аналитическое или численное определение производных становится очень сложным, а иногда невозможным. Поэтому наиболее подробно здесь рассматриваются методы нулевого порядка. Методы одномерного поиска. Перечень методов одномерного поиска – численного поиска экстремума функции одного аргумента f(x) – достаточно широк и хорошо освещен в литературе [18]. Поэтому здесь ограничимся рассмотрением только одного метода, который по опыту авторов является одним из наиболее эффективных – метода «золотого сечения». Идея метода состоит в последовательном сокращении интервала неопределенности – интервала значений аргумента x, содержащего искомую точку минимума, – до длины, не превышающей допустимой погрешности результата . В качестве исходного интервала может рассматриваться заданная условиями задачи допустимая область значений аргумента или, в случае, когда последняя не имеет левой и (или) правой границ, некоторая область внутри допустимой, на принадлежность к которой искомого минимума указывает предварительный анализ. Внутри любого интервала [a;b] содержатся две точки x=y 0 и x=z 0 , выполняющие его «золотое сечение» – разбиение на две неравные части такие, что отношение большей части к длине всего интервала совпадает с отношением меньшей части к большей. Очевидно, эти точки расположены симметрично 63 относительно центра интервала (рис. 12). Координаты точек «золотого сечения» могут быть найдены из соответствующих пропорций: b  y0 y0  a z  a b  z0    , 0  , b  a z0  a b  a b  y0 откуда нетрудно получить   1  и придти к уравнению:   В  результате получим относительные доли, определяющие «золотое сечение» интервала: =0,618, 1–=0,382. «Золотое сечение» обладает важным свойством: точка y 0 является одной из точек «золотого сечения» интервала [a;z 0 ], точка z 0 является одной из точек «золотого сечения» интервала [y 0 ;b]. В этом убеждает простой расчет: 0,382/0,618=0,618 и (0,618–0,382)/0,618=0,382. Алгоритм поиска минимума, построенный на основе метода «золотого сечения», предусматривает на каждой итерации выбор в качестве одной из границ сокращенного интервала левой или правой точки «золотого сечения» таким образом, чтобы искомый минимум сохранялся внутри него: 1. Задают k=0, исходный интервал неопределенности [a k;b k], допустимую погрешность результата . 2. Вычисляют координаты точек «золотого сечения»: yk=ak+0,382(bk–ak), zk=ak+0,618(bk–ak). 3. Вычисляют значения целевой функции в найденных точках f(yk) и f(zk). 4. Если f(yk)≤f(zk) (рис. 12 а), присваивают a k + 1 =a k , b k + 1 =z k , z k + 1 =y k , y k + 1 =a k +z k –y k , k=k+1. В противном случае (рис. 12 б) присваивают a k + 1 =y k , b k + 1 =b k , y k + 1 =z k , z k + 1 =y k +b k –z k , k=k+1. 5. Проверяют выполнение условия завершения поиска bk 1  ak 1   . В случае его выполнения в качестве решения выбирают точку xˆ   yk 1  zk 1  2 . В противном случае переходят к шагу 2. 64 Вычислительная эффективность метода «золотого сечения» обусловлена тем, что здесь на каждой итерации требуется только однократное вычисление значения целевой функции. Далее обратимся к методам многомерного поиска. Метод прямого поиска (метод Хука-Дживса). Задаются некоторой начальной точкой Х[0]. Поочередно изменяя компоненты вектора Х, обследуют окрестность данной точки, в результате чего находят точку (новый базис), определяющую направление, в котором происходит уменьшение минимизируемой функции f(Х). В выбранном направлении осуществляют спуск, убеждаясь, что значение функции уменьшается. Процедура циклически повторяется, пока удается находить направление спуска с учетом принятого условия останова. Алгоритм метода прямого поиска в самом общем виде можно сформулировать следующим образом: 1. Задаются значениями координат х i [0], i=1,2,…n, начальной точки (k=0), вектором начальных приращений координат X(х 1 ,х 2 ,…,х n ) в процессе обследования окрестности, наименьшим допустимым значением  компонентов X, ускоряющим множителем   1, масштабным коэффициентом d>1. 65 определяющим скорость спуска, 2. Принимают Х[k] за «старый базис» [15]: Xб=Х[k]. Вычисляют значение f(Xб). 3. Поочередно изменяют каждую координату хбi, i=1,2,…n, точки Xб на величину х i , то есть принимают х i [k]=хбi+х i , затем х i [k]=хбi–х i . Вычисляют значения f(X[k]) в получаемых пробных точках и сравнивают их со значением f(Xб). Если f(X[k])< f(Xб), то соответствующая координата х i [k] приобретает новое значение, вычисленное по одному из приведенных выражений. В противном случае значение этой координаты остается неизменным. Если после изменения последней n-й координаты f(X[k])C 2 >C 3 . Сплошными 66 линиями показаны результаты однократного выполнения пунктов 3-5 (поиск направления уменьшения функции и спуск), пунктирной линией – следующий спуск. Достоинством поиска является метода прямого простота его программирования на компьютере. Он не требует знания целевой функции в явном виде, а также легко учитывает ограничения на отдельные переменные, а также сложные ограничения на область поиска. Недостаток метода прямого поиска состоит в том, что в случае сильно вытянутых, изогнутых или обладающих острыми углами линий уровня целевой функции он может оказаться неспособным обеспечить продвижение к точке минимума в силу ограниченного числа анализируемых направлений. Метод деформируемого многогранника (метод Нелдера—Мида). Данный метод состоит в том, что для минимизации функции n переменных f(X) в n-мерном пространстве строится многогранник, содержащий n+1 вершину. Очевидно, что каждая вершина соответствует некоторому вектору Xi. Вычисляют значения целевой функции f(Xi), i=1,2,…n+1, в каждой из вершин многогранника, определяют максимальное из этих значений и соответствующую ему вершину Xh. Через эту вершину и центр тяжести остальных вершин проводят проецирующую прямую, на которой находится точка Xq с меньшим значением целевой функции, чем в вершине Xh (рис. 14 а). Затем исключают вершину Xh. Из оставшихся вершин и точки Xq строят новый многогранник, с которым повторяют 67 описанную процедуру. В процессе выполнения таких операций многогранник изменяет свои размеры, что и обусловило название метода. Введем следующие обозначения: X[i,k] – вектор координат i-ой вершины многогранника на k-ом шаге поиска, i=1,2,…n+1, k=1,2,…; h – номер вершины, в которой значение целевой функции максимально: f  X h, k   max f  X i, k  ; l – номер вершины, в которой значение целевой i функции минимально: f  X h, k   min f  X i, k  ; X[n+2,k] – центр тяжести всех i вершин, за исключением X[h,k]. Координаты центра тяжести вычисляются по  1  n 1  , j=1,2,…n.       x n  2 , k  x i , k  x h , k формуле j j  j  n  j 1  Примерный алгоритм метода деформируемого многогранника состоит в следующем: 68 1. Задаются коэффициентами отражения , растяжения >1, сжатия , допустимой погрешностью определения координат точки минимума . Выбирают координаты вершин исходного многогранника X[i,k], i=1,2,…n+1, k=1. 2. Вычисляют значения целевой функции во всех вершинах f(X[i,k]), i=1,2,…n+1, и находят точки X[h,k], X[l,k] (на рис. 14 б точки соответственно X2 и X1), а также X[n+2,k]. 3. Осуществляют проецирование точки X[h,k] через центр тяжести: X[n+3,k]=X[n+2,k]+(X[n+2,k]–X[h,k]). 4. Если выполняют f(X[n+3,k])≤X[l,k], операцию растяжения: X[n+4,k]=X[n+2,k]+(X[n+3,k]–X[n+2,k]). В противном случае переходят к пункту 6. 5. Строят новый многогранник: если f(X[n+4,k])f(X[n+3,k])>X[i,k] для всех i, не равных h, выполняют операцию сжатия: X[n+5,k]=X[n+2,k]+(X[h,k]–X[n+2,k]). Строят новый многогранник путем замены X[h,k] на X[n+5,k] и продолжают вычисления с пункта 2 при k=k+1. 7. Если f(X[n+3,k])>X[h,k], то сохраняя вершину X[l,k] строят новый многогранник, подобный текущему, путем уменьшения длин всех ребер в два раза: X[i,k]=X[l,k]+0,5(X[i,k]–X[l,k]) и продолжают вычисления с пункта 2 при k=k+1. В пунктах 6-7 перед переходом к пункту 2 необходима проверка выполнения условия завершения поиска минимума, например, по условию n 1   max  x j i, k   x j n  2, k  2  2 . i j 1 69 С помощью операции растяжения и сжатия размеры и форма деформируемого многогранника адаптируются к топографии целевой функции. В результате многогранник вытягивается вдоль длинных наклонных поверхностей, изменяет направление в изогнутых впадинах, сжимается в окрестности минимума, что определяет эффективность рассмотренного метода. Большинство известных рекомендаций сводятся к выбору =1, 2≤≤3. 0,4≤≤0,6. Метод вращающихся координат (метод Розенброка). Суть метода состоит в последовательных поворотах системы координат в соответствии с изменением направления наиболее быстрого убывания целевой функции (рис. 15). Из начальной точки X[0] осуществляют спуск в точку X[1] по направлениям, параллельным координатным осям. На следующей итерации одна из осей должна проходить в направлении x’1=X[1]–X[0], остальные – в направлениях, перпендикулярных к x’1. Спуск вдоль этих осей приводит в точку X[2], что дает возможность построить новый вектор x’’1=X[2]–X[1] и на его базе новую систему направлений поиска точки минимума X̂ . В отличие от других методов нулевого порядка метод Розенброка ориентирован на отыскание оптимальной точки в каждом направлении, а не просто на фиксированный сдвиг по всем направлениям. Величина шага в процессе поиска непрерывно изменяется в зависимости от рельефа поверхности уровня. Сочетание вращения координат с регулированием шага делает метод Розенброка эффективным при решении сложных задач оптимизации. В частности, данный метод в отличие от многих других эффективен при минимизации так называемых овражных функций (с сильно вытянутыми поверхностями уровня), так как результирующее направление поиска стремится расположиться вдоль оси «оврага». 70 Метод параллельных касательных (метод Пауэлла). Суть метода состоит в последовательном проведении одномерного поиска минимума целевой функции по n+1 направлению каким-либо из известных одномерных методов. На первой итерации в качестве первых n направлений выбираются координатные, в качестве n+1 направления используется первое из них (рис. 16). последующей На каждой итерации поиск начинается со второго направления предшествующей соответственно направлений единицу; итерации, номера уменьшаются n+1 на направление последующей итерации задается вектором X[1]–X[n+1] – из точки минимума, найденной на первом шаге предшествующей итерации, 71 через точку минимума, найденную на последнем ее шаге. На рис. 16 X[1] – исходная точка, n=2. На первой итерации поиск производится последовательно вдоль осей x1, x2, x1. Точки X[1], X[2], X[3] – точки минимума, найденные при последовательных одномерных поисках вдоль исходных направлений. На второй итерации одномерный поиск должен производиться из точки X[3] последовательно вдоль направлений x2, x1, а также вдоль направления, совпадающего с вектором X[1]–X[3], и так далее. Известно, что данный метод наиболее эффективен для минимизации функций, близких к квадратичным по крайней мере вблизи точки минимума. В идеальном случае квадратичной функции n переменных точка минимума X̂ находится точно за n итераций. 3.5.4. Методы безусловной оптимизации первого и второго порядка Градиентом дифференцируемой функции f(X) в точке X[k] называется nмерный f(X[k]), вектор компоненты которого являются частными производными функции f(X), вычисленными в точке X[k]. Этот вектор перпендикулярен к плоскости, проведенной через точку X[k], и касательной к поверхности уровня функции f(X), проходящей через точку X[k] (рис. 17). Вектор-градиент направлен в сторону наискорейшего возрастания функции в данной точке. Вектор –f(X[k]), противоположный градиенту, называется направлен антиградиентом в и сторону 72 наискорейшего убывания функции. В точке минимума градиент функции равен нулю. На свойствах градиента основаны методы поиска первого порядка, называемые также градиентными методами минимизации. Очевидно, что если нет дополнительной информации, то из точки X[k] разумно перейти в точку X[k+1], лежащую в направлении антиградиента. Это приводит к итерационному процессу вида X[k+1]=X[k]–a k . f(X[k]), где a>0 – шаг, k=0,1,2,... В координатной форме этот процесс записывается следующим образом: xi k 1  xi k   ak  f , i=0,1,...,n; k=0,1,2,... xi X  X k  В качестве критерия останова итерационного процесса используют либо выполнение условия малости приращения аргумента X k  1  X k   , либо выполнение условия малости градиента f  X k  1   . Здесь  и  - заданные малые величины. Возможен и комбинированный критерий, состоящий в одновременном выполнении указанных условий. Градиентные методы отличаются друг от друга способами выбора величины шага a k . Достаточно малый постоянный шаг a k обеспечит убывание целевой функции, однако при этом может потребоваться неприемлемо большое количество итераций для достижения точки минимума. С другой стороны, слишком большой шаг может вызвать неожиданный рост функции либо привести к колебаниям около точки минимума. Из-за сложности получения необходимой информации для выбора величины шага методы с постоянным шагом применяются на практике редко. Более экономичны в смысле количества итераций и надежности градиентные методы с переменным шагом, когда в зависимости от результатов вычислений величина шага некоторым образом меняется. 73 Наиболее простым в реализации и в то же время вполне эффективным является метод наискорейшего спуска. Метод наискорейшего спуска. В соответствии с этим методом величина шага a k на каждой итерации выбирается из условия минимума функции f(X) в направлении антиградиента: f  X k   ak  f  X k   min  f  X k   a  f  X k  . a 0 Общий алгоритм метода состоит в следующем: 1. Задают координаты начальной точки X[0], k=0. 2. Вычисляют значение градиента f(X[k]). 3. Выполняют одномерную минимизацию по a функции f(X[k]– a . f(X[k])). 4. Вычисляются координаты точки X[k+1]. 5. Проверяются условие останова итерационного процесса. Если оно выполняется, вычисления прекращают. В противном случае продолжают вычисления с пункта 2 при k=k+1. Градиентные методы сходятся к минимуму с высокой скоростью (со скоростью геометрической прогрессии) для гладких выпуклых функций, так как вектор антиградиента для таких функций, как правило, направлен в окрестность точки минимума (рис. 18). У таких функций наибольшее наименьшее значения m М и собственные матрицы Гессе 74 H 2 f (подраздел 2.2) мало отличаются друг от друга (матрица Н хорошо xi x j обусловлена). Напомним, что собственными значениями матрицы являются корни характеристического уравнения  n =0, где определитель n находится в соответствии с (1). Однако в случае минимизации овражных функций скорость сходимости градиентных методов значительно снижается, так как направление вектора антиградиента существенно отклоняется от направления в точку минимума (рис. 19). Обнаружить такую ситуацию можно путем оценки обусловленности матрицы Гессе минимизируемой функции. Для овражной функции матрица Н плохо обусловлена (m/М<<1). Скорость сходимости градиентных методов существенно зависит также от точности вычислений градиента. Потеря точности, а это обычно происходит в окрестности точек минимума или в овражной ситуации, может вообще нарушить сходимость процесса градиентного спуска. Вследствие перечисленных причин градиентные методы иногда используются в комбинации с другими методами. На начальной стадии решения задачи, когда точки X[k] находятся далеко от точки 75 минимума, шаги в направлении антиградиента позволяют достигать существенного убывания функции. Вблизи же точки минимума переходят к другому методу, эффективному для овражных функций. Метод безусловной оптимизации второго порядка (метод Ньютона). Необходимое условие экстремума функции многих переменных f(X) в точке   Xˆ   xˆ1 , xˆ2 ,...xˆn  , может быть записано для ее градиента в этой точке: f Xˆ  0 . Разложение f(X) в окрестности некоторой точки X[k] в ряд Тейлора с точностью до членов первого порядка позволяет переписать предыдущее     уравнение в виде: f Xˆ  f  X k   H  X k  Xˆ  X k   0 , где Н(X) – матрица вторых производных (матрица Гессе) минимизируемой функции. Решение уравнения дает соотношение, которое может быть проложено в основу поиска точки X̂ : X k  1  X k   H 1  X k f  X k  , где H-1 – обратная матрица для матрицы Гессе, а H 1  X k f  X k   pk  – направление спуска. Отметим, что для квадратичной функции f(X) рассматриваемая точность разложения в ряд Тейлора достаточна для достижения минимума за один шаг. Для других функций полученное выражение может быть положено в основу итерационного процесса поиска минимума. Величина шага вдоль направления р[k] полагается равной единице или может определяться наискорейшего аналогично спуска путем рассмотренному выше одномерной варианту метода минимизации вдоль данного направления. Установлено, что последовательность X[k] сходится к точке X̂ только в том случае, когда матрица Гессе целевой функции является положительно определенной на каждой итерации. Это условие может не выполняться как на начальных итерациях, если минимизируемая функция вблизи начальной точки X[0] существенно отличается от квадратичной зависимости, так и на конечных итерациях за счет накопления ошибок. 76 Поэтому выполнение условия положительной определенности (критерия Сильвестра, подразд. 2.2) должно проверяться на каждой итерации. Если на k-ом шаге матрица H не окажется положительно определенной или не удастся получить H-1, в большинстве модификаций данного метода H-1 заменяют единичной матрицей. Соответственно получается р[k]=f(X[k]), и на рассматриваемом шаге метод Ньютона вырождается в метод наискорейшего спуска. Количество вычислений на итерации методом Ньютона, как правило, значительно больше, чем в градиентных методах первого порядка. Это объясняется необходимостью вычисления и обращения матрицы вторых производных минимизируемой функции. Однако на получение решения с достаточно высокой степенью точности с помощью метода Ньютона обычно требуется намного меньше итераций. Особенно эффективен данный метод при минимизации «овражных» функций. Поэтому часто его используют в сочетании с каким-либо градиентным методом первого порядка для точного и ускоренного достижения точки минимума на завершающем этапе поиска. 3.5.5. Прямые методы условной оптимизации Задачи условной оптимизации соответствуют общей постановке задачи нелинейного программирования (13)-(14). В общем случае численные методы решения таких задач можно разделить на прямые и непрямые. Прямые методы оперируют непосредственно с минимизируемой функцией и представляют собой модификации рассмотренных выше прямых методов безусловной минимизации, позволяющие реализовать спуск к искомой точке минимума X̂ , не выходя за пределы допустимой области G, определяемой соотношениями (14). Метод проекции градиента. Рассмотрим данный метод применительно к задаче оптимизации с ограничениями-неравенствами. В качестве начальной выбирается некоторая точка 77 допустимой области G. Движение от начальной точки осуществляется обычным градиентным методом до выхода на границу допустимой области в некоторой точке X[k]. Дальнейшее движение в направлении антиградиента может вывести за пределы допустимой области. Поэтому антиградиент проецируется на линейное многообразие М, аппроксимирующее участок границы в окрестности точки X[k], и дальнейшее движение осуществляется вдоль такой проекции. Проведем более подробный анализ данной процедуры. В точке X[k] часть ограничений-неравенств удовлетворяется как равенства: z j (X)=z j (x 1 ,x 2 ,…x n )=0; j=1,2,…l; ln+1 вершин. Эти многогранники называют комплексами, что и определило наименование метода. Будем использовать обозначения, введенные выше для метода деформированного многогранника: X[i,k] – j-я вершина комплекса на k-м этапе поиска; X[h,k] - вершина, в которой значение целевой функции максимально; X[n+2,k] – центр тяжести всех вершин, за исключением X[h,k]. Примерный алгоритм комплексного поиска состоит в следующем. 1. В качестве первой вершины начального комплекса выбирается некоторая допустимая точка X[1,0]. Координаты остальных q–1 вершин комплекса определяются соотношением х i [j,0]=а i + i (b i –a i ), I=1,2,...,n; j=2,...,q. Здесь а i ,b i – соответственно нижнее и верхнее ограничения на переменную х i ,  i – 80 псевдослучайные числа, равномерно распределенные на интервале [0;1]. Полученные таким образом точки удовлетворяют ограничениям а i х i  b i , однако ограничения z j (X)0 могут быть нарушены. В этом случае недопустимая точка заменяется новой, лежащей в середине отрезка, соединяющего недопустимую точку с центром тяжести выбранных допустимых вершин. Данная операция повторяется до тех пор, пока не будут выполнены все ограничения задачи. 2. Далее, как и в методе деформируемого многогранника, на каждой итерации заменяется вершина X[h,k], в которой значение целевой функции имеет наибольшую величину. Для этого она отражается относительно центра тяжести X[n+2,k] остальных вершин комплекса. Точка X[n+3,k], заменяющая вершину X[h,k], определяется по формуле X[n+3,k]=(a+1)X[n+2,k]+aX[h,k], где а>0 – некоторая константа, называемая коэффициентом отражения. Наиболее удовлетворительные результаты дает значение а=1,3. При этом новые вершины комплекса отыскиваются за небольшое количество шагов, а значения целевой функции уменьшаются достаточно быстро. 3. Если f(X[n+3,k])f(X[h,k]), то новая вершина оказывается худшей вершиной комплекса. В этом случае коэффициент а уменьшается в два раза. Аналогично поступают, если при отражении нарушаются ограничения z j (X)0, до тех пор, пока точка X[n+3,k] не станет допустимой. Вычисления заканчиваются, если значения целевой функции в центре тяжести комплекса мало меняются в течение пяти последовательных итераций: | f(X[n+2,k+1])–f(X[n+2,k])|, k=1,2....,5, где  – заданная константа. В этом случае центр тяжести комплекса считают решением задачи. Достоинствами комплексного метода Бокса являются его простота, удобство для программирования, надежность в работе. Метод на каждом шаге использует информацию только о значениях целевой функции и функций ограничений задачи. Все это обусловливает успешное применение его для решения различных задач нелинейного программирования. 81 3.5.6. Непрямые методы условной оптимизации Непрямые методы сводят исходную задачу нелинейного программирования к последовательности задач безусловной оптимизации некоторых вспомогательных функций. При этих методах ограничения исходной задачи учитываются в неявном виде. Градиентный метод поиска седловой точки. Пусть для задачи поиска минимума, сформулированной в виде (13)-(14) m введена функция Лагранжа L X ,    f  x1, x2 ,..., xn     j z j  x1, x2 ,..., xn , причем j 1 имеют место условия x i 0, i=1,2,…n; j0, j=1,2,…m. В п. 4.5.1 было отмечено, что решение такой задачи достигается в седловой точке функции L, в которой должны соблюдаться условия (18)-(19). Более удобной для построения численных алгоритмов по сравнению с (18) является запись первого необходимого условия достижения седловой точки в форме условий Куна-Таккера: xi 0  0 при L  0 , i=1,2,…n; xi X 0 , 0 x i 0 =0 при L  0 , i=1,2,…n; xi X 0 , 0  j 0  0 при  j 0 =0 при L  0 , j=1,2,…m;  j X 0 , 0 L  0 , j=1,2,…m.  j X 0 , 0 Частные производные функции Лагранжа выглядят следующим образом: m z j L f    j ; i=1,2,…n; xi xi j 1 xi 82 L  z j ; j=1,2,…m.  j Анализируя представленные соотношения, отметим следующее: 1. Функция Лагранжа линейно зависит от . Поэтому условие вогнутости функции Лагранжа по  выполняется всегда. 2. Условие выпуклости функции Лагранжа по x в силу линейной зависимости ее частных производных по xi от частных производных функций f и zj сводится к выпуклости всех указанных функций. 3. Задачу, для которой выполняется последнее условие, называют задачей выпуклого программирования. В задачах выпуклого программирования условия Куна-Таккера оказываются достаточными для наличия седловой точки. 4. Все условия, на основе которых решается задача, основаны на использовании вектора первых частных производных функции Лагранжа по всем аргументам, т.е. ее градиента, чем и вызвано название метода. 5. Численная проверка выполнения условий выпуклости для всей допустимой области, очевидно, является вычислительной задачей, не уступающей по трудоемкости случайному поиску экстремума. Поэтому в рамках градиентных алгоритмов такая задача не решается, и гарантии того, что найденное решение действительно дает глобальный, а не локальный, экстремум, такие алгоритмы не дают. Рассмотрим простейший вариант градиентного алгоритма: 1. Выбирается некоторая начальная точка, определяемая координатами X[k]=(x 1 [k],x 2 [k],…,x n [k]), [k]  [k]  [k] m [k]), k=0. 2. Вычисляются значения частных производных в данной точке: m z j  L  f       j k  ; i=1,2,…n;         X k ,  k X k ,  k  x  x  x i i  ik j 1 83  L     z j  X k  ; j=1,2,…m.   j  k   3. Рассчитываются координаты следующей точки:  L   ; i=1,2,…n; (движение по координатам xi в сторону xi k  1  xi k   ak    xi  k уменьшения функции L);  L   ; j=1,2,…m; (движение по координатам j в сторону  j k  1   j k   ak     j  k   увеличения функции L). 4. Если значения каких-либо координат новой точки получились отрицательными, им присваиваются нулевые значения (соответствующие границе допустимой области и возможной седловой точке второго вида, рис. 23). 5. Пункты 2-4 повторяются, пока приращения координат при переходе к следующей точке не окажутся достаточно малыми. Известны различные варианты и модификации такого алгоритма, различающиеся способом выбора или изменения коэффициента ak и другими деталями. Методы штрафных функций преобразуют задачу с ограничениями в последовательность задач безусловной оптимизации некоторых вспомогательных функций. Последние получаются путем модификации целевой функции с помощью функций-ограничений таким образом, чтобы ограничения в явном виде в задаче оптимизации не фигурировали. Это обеспечивает возможность применения методов безусловной оптимизации. В общем случае вспомогательная функция имеет вид F(X,a)=f(X)+Ф(X,а). Здесь f(X) – целевая функция задачи оптимизации; Ф(X,а) – “штрафная” функция; параметр а>0. В зависимости от вида Ф(X,а) различают методы внутренних штрафных, или барьерных, функций и методы внешних штрафных функций. 84 Метод внутренних штрафных функций. Этот метод применяется для решения задач нелинейного программирования с ограничениями-неравенствами. В рассматриваемых методах функции Ф(X,а) подбирают такими, чтобы их значения неограниченно возрастали при приближении к границе допустимой области G (рис. 20). Иными словами, приближение к границе “штрафуется” резким увеличением значения функции F(X,а). На границе G построен “барьер”, препятствующий процессе Поиск нарушению безусловной минимума ограничении минимизации вспомогательной в F(X,а). функции Рис. 20. F(X,а) необходимо начинать с внутренней точки области G. При этом в процессе оптимизации траектория спуска никогда не выйдет за пределы допустимой области. Все перечисленные особенности функции Ф(X,а) определили наименование рассматриваемой группы методов. Таким образом, внутренняя штрафная функция Ф(X,а) должна обладать следующими свойствами:    при x  G   X , a    0 при x  G, x  dG, a  0 ,    при x  G, x  dG  где dG – граница области G. m   Внутренние штрафные функции задаются в форме  X , a   a   j z j  X  , j 1 где j – непрерывные дифференцируемые функции, определяемые ограничениями-неравенствами исходной задачи нелинейного программирования. В качестве внутренних штрафных функций используют, например, такие: m   m 1 ,  X , a   a  ln z j  X   X , a   a    z X j 1 j j 1 85 Алгоритм метода внутренних штрафных функций состоит в следующем: 1. В качестве начальной точки X[0] выбирают произвольную внутреннюю точку области G. 2. Задаются некоторой монотонно убывающей сходящейся к нулю последовательностью {ak}, k=1,2,..., положительных чисел. 3. Для первого элемента а1 этой последовательности решают задачу безусловной минимизации функции F(X,а 1 ) одним из рассмотренных выше методов, в результате чего определяют точку X[1]=X(а1). Эту точку используют в качестве начальной для решения задачи поиска минимума функции F(X,а 2 ) и так далее. 4. Вычисления прекращают при выполнении условий |f(X[k])–f(X[k–1])|, ||X[k]–X[k–1]||где ,  – заданные числа, определяющие точность вычислений. Таким образом, метод внутренних штрафных функций предусматривает последовательное решение задач безусловной минимизации функций F(X,а k ), , k=1,2,..., причем решение предыдущей задачи X(аk) используется в качестве начальной точки для поиска последующего вектора X(аk+1). Для задач, содержащих непрерывные функции и имеющих локальные минимумы внутри области G, последовательность полученных таким образом точек сходится к точке локального минимума X̂ . Метод внешних штрафных функций. Данный метод применяется для решения задачи оптимизации в общей постановке, то есть при наличии как ограничений-неравенств, так и ограниченийравенств. В рассматриваемых методах функции Ф(X,а) выбирают такими, что их значения равны нулю внутри и на границе допустимой области G, а вне ее – положительны и возрастают тем больше, чем сильнее нарушаются ограничения (рис. 21). Таким образом, здесь “штрафуется” удаление от допустимой области G. 86 Внешняя штрафная функция в общем случае может быть определена следующим образом:  0 при x  G  X , a      при x  G, a   Поиск минимума вспомогательной функции можно F(X,а) начинать Рис. 21. из произвольной точки. В большинстве случаев она является недопустимой, поэтому траектория спуска располагается частично вне допустимой области. Если минимум целевой функции расположен на границе допустимой области, то эта траектория полностью находится снаружи области G. Перечисленные особенности функции Ф(X,а) определили название данного метода. Общий вид внешней штрафной функции: m2  m1    X , a   a   j g j  X    l hl  X  ,  j 1  l 1    где j, j –  непрерывные дифференцируемые функции, определяемые соответственно ограничениями-неравенствами и равенствами исходной задачи нелинейного программирования. Одна из применяемых на практике внешних  m1 штрафных функций имеет вид  X , a   a  max 0, g j  X   j 1    m2  l 1     hl  X 2  , 2 где  0 при g  0 max 0, g    .  g при g  0 Алгоритм метода внешних штрафных функций формулируется так же, как и алгоритм метода внутренних штрафных функций, и обладает аналогичными свойствами. Однако в этом случае не требуется, чтобы начальная точка X[0]G, а последовательность {ak}, k=1,2,..., положительных чисел должна быть монотонно возрастающей. 87 Анализ методов штрафных функций позволяет сделать следующие выводы об их вычислительных свойствах. В соответствии с методами внутренних штрафных функций ведут поиск решения, не выходя за пределы допустимой области. Это весьма важно в тех случаях, когда целевая функция или ограничения не определены за пределами допустимого множества. Кроме того, прервав вычисления в любой момент времени, мы всегда получим допустимое решение. Однако для задания в качестве начальной некоторой допустимой точки иногда требуется решать задачу, по сложности сравнимую с исходной задачей нелинейного программирования. В этом смысле метод внешних штрафных функций предпочтительнее, так как он обеспечивает решение из любой начальной точки. В результате программирование для ЭВМ алгоритмов внешних штрафных функций существенно упрощается. Общим недостатком методов штрафных функций является сложность вспомогательной функции F(X,а), которая часто имеет овражную структуру, особенно при больших a. Кроме того, при больших значениях а точность вычислений минимума F(X,а) существенно снижается из-за ошибок округления ЭВМ. Комбинированные алгоритмы штрафных функций. Вспомогательная функция F(X,а) включает в себя слагаемые в виде внутренних штрафных функций (X,а) для ограничений-неравенств и внешних штрафных функций (X,а) для ограничений-равенств. При этом для внутренней щтрафной функции используется убывающая последовательность коэффициентов {ak}, k=1,2,..., а для внешней – последовательность {1/ak}, k=1,2,..., удовлетворяющая сформулированным выше требованиям. Например, в качестве внутренней можно использовать логарифмическую штрафную функцию, а в качестве внешней - квадратичную функцию, то есть: m1   m 1 2  X , a   ak  ln g j  X    hl  X 2 . ak l 1 j 1 88 3.5.7. Применение симплекс-метода для решения целочисленных задач нелинейного программирования Особую сложность представляют задачи целочисленного или дискретного нелинейного программирования. Методы их решения в настоящее время наименее развиты. В частном случае, когда целевая функция линейна, а в систему ограничений входят нелинейные уравнения или неравенства, эффективным оказывается применение симплекс-метода. Рассмотрим порядок решения задачи нелинейного программирования в следующей постановке: требуется определить значения целочисленных аргументов x 1 ,x 2 ,…,x n , доставляющие максимум целевой функции вида n q x1, x2 ,...xn   c0   ci xi и удовлетворяющие системе ограничений: i 1 n  a ji xi  b j ; j=1,2,…m; xi  0 ; i=1,2,…n; i 1 z j x1, x2 ,...xn   0 ; j=1,2,…l. (20) Принцип решения такой задачи на основе симплекс-метода является развитием принципа решения линейной целочисленной задачи, рассмотренного в подразд. 4.3. Задача решается в три этапа: как обычная линейная непрерывная задача, как линейная целочисленная задача и в полной постановке с учетом нелинейных ограничений. Укрупненный алгоритм выглядит следующим образом. 1. Строится линейный план без учета условий (20). 2. Стандартным симплекс-методом без учета требований целочисленности находится допустимое и оптимальное базисное решение. 3. Если получено целочисленное решение, переходят к п.6. 4. Если полученное решение не является целочисленным, вводится правильное отсечение по одной из переменных в соответствии с (8). 89 5. Пункты 2-4 повторяются до получения допустимого и оптимального целочисленного решения. 6. Проверяется соответствие полученного решения нелинейным ограничениям задачи (20). Если условия (20) выполняются, полученное в пункте 5 решение является окончательным. 7. Если условия (20) не выполняются, строится отсечение Данцига, вызывающее переход к задаче повышенной размерности с недопустимым базисным решением. 8. Пункты 2-7 повторяются до получения допустимого и оптимального целочисленного решения, соответствующего ограничениям (20). Отсечение Данцига вводится в соответствии с условием nm  xj  1, (21) j 1 где xj - свободные переменные текущего плана. Условие (21) является линейным ограничением в форме неравенства и сводится к равенству путем введения дополнительной базисной переменной:  1  1  xm nm  xj  0 , j 1 что эквивалентно дополнению линейного плана строкой, все элементы которой равны -1. Таким образом, размерность задачи повышается за счет добавления одной базисной переменной, причем текущее базисное решение оказывается недопустимым. Это требует повторного решения линейной задачи (переход к пункту 2 алгоритма). Пример 19. Дополним пример 15, рассмотренный в подразделе 3.3, нелинейным ограничением 0,5  x2 x1  2 . Полученное в примере 15 решение, представленное планом в таблице 13, такому условию не соответствует. Введем отсечение Данцига и новую переменную x10  1  x8  x9  0 . План дополнится 90 соответствующей строкой, причем текущее базисное решение теперь окажется недопустимым (значение базисной переменной x10<0). Требуется дальнейшее преобразование плана по рассмотренным выше правилам (таблица 20). Уже после первого преобразования по правилам, используемым для линейной непрерывной задачи, получен план, представленный в таблице 21. Соответствующее ему базисное решение является допустимым, оптимальным, целочисленным и удовлетворяет нелинейному ограничению. Таким образом, решение задачи получено. Рассмотренный пример демонстрирует высокую эффективность метода. Тем не менее, отметим, что в общем случае решение задачи может потребовать и большего количества преобразований. Таблица 20. 1 q -x9 -7 x1 2 x2 5 x3 3 x4 2 x5 2 x6 1 x7 1 x10 -1 -x8 -1 1 -2 -4 -1 3 -4 2 -2 4 -5 2 -3 3 -2 2 -3 1 -1 3 -3 1 -2 2 q x1 x2 x3 x4 x5 x6 x7 x9 1 1 4 1 1 1 -1 1 -2 -1 1 -1 -1 Таблица 21. 1 2 -1 -1 1 91 -7 3 4 7 5 3 1 -x10 -1 1 -4 2 -3 1 -2 -1 -x8 1 2 -3 7 -7 5 -4 3 1 Контрольные вопросы 1. Классифицируйте задачи линейного и нелинейного программирования по рассмотренным в разделе 1 признакам. 2. Почему для задачи линейного программирования неприменимы способы поиска локального экстремума, рассмотренные в разделе 2? 3. Чем отличается постановка задачи в форме ОЗЛП от общей постановки задачи линейного программирования? 4. При каких условиях возможна графическая интерпретация задачи линейного программирования на плоскости? 5. При каких условиях задача линейного программирования может не иметь решения? 6. При каких условиях задача линейного программирования может иметь бесконечное множество решений? Могут ли они все быть найдены симплексметодом? 7. Общее количество переменных в ОЗЛП – шесть, количество базисных переменных - три. Сколько базисов может быть выбрано в данной задаче? 8. Сформулируйте основные положения симплекс-метода. 9. Формализована ОЗЛП, в которой требуется обеспечить минимум целевой функции. Как применить для нее рассмотренный в настоящем разделе вариант симплекс-метода? 10. Каковы признаки допустимости и оптимальности решения в алгебраическом варианте симплекс-метода? Объясните их. 11. Каковы признаки допустимости и оптимальности решения в табличном варианте симплекс-метода? Объясните их. 12. Для решения каких задач линейного программирования служит метод Гомори? В чем состоит его основная идея? 13. Для решения каких задач служит метод Данцига? В чем состоит его основная идея? 92 14. В чем состоит порядок случайного поиска экстремума? 15. В чем основное преимущество и основной недостаток метода случайного поиска по сравнению с методами целенаправленного поиска экстремума? 16. В чем смысл понятия «порядок метода минимизации»? 17. Поясните смысл понятий «градиент» и «антиградиент». 18. В чем состоит принцип метода «золотого сечения» и чем определяется его вычислительная эффективность? 19. Сформулируйте основной принцип одного из методов многомерного поиска нулевого порядка (по выбору). 20. В чем состоит основная идея градиентных методов поиска экстремума? 21. В чем различие между прямыми и непрямыми методами условной оптимизации? 93 4. СТРАТЕГИЧЕСКИЕ МАТРИЧНЫЕ ИГРЫ Формализация задачи принятия решения в виде стратегической матричной игры удобна в тех случаях, когда результат операции зависит от поведения двух участников с противоположными интересами. Конкретный вариант поведения каждого из участников выбирается перед началом операции, сохраняется в течение операции, определяет условия проведения операции для конкурента и заранее ему неизвестен. В этом случае выбор наилучшего варианта поведения для каждого из участников приходится проводить в условиях неопределенности с учетом того, что конкурент может осознанно применить наилучшую для себя стратегию (гипотеза о наихудших условиях). 4.1. Основные термины и допущения. Формализация задачи. Принципы поиска решения В игре участвуют две стороны (игрока) А и В. Количественная характеристика результата однократного проведения операции (партии игры) трактуется как выигрыш или проигрыш одного из игроков. Для определенности принимается, что сторона А стремится получить максимальный выигрыш (ее называют максимизирующей стороной). Соответственно сторона В стремится получить минимальный проигрыш (ее называют минимизирующей стороной). Ограничимся здесь анализом игр с нулевой суммой, когда выигрыш стороны А совпадает с проигрышем стороны В. В распоряжении стороны А имеется m вариантов поведения А1,А2,…,Аm, называемых также стратегиями или чистыми стратегиями, из которых в очередной партии игры она может применить одну и только одну. В 94 распоряжении стороны В имеется n чистых стратегий В1,В2,…,Вn аналогичного смысла. Применение стороной А некоторой стратегии А i , а стороной В некоторой стратегии В j , в очередной партии игры приводит к получению стороной А выигрыша величиной a i j , а стороной В – проигрыша той же величины. Величины a i j для всех i=1,2,…,m и для всех j=1,2,…,n считаются априорно известными. Однако каждой из сторон неизвестно, какую стратегию выберет другая сторона в очередной партии. Наиболее удобной формой задания игры является матричная - матрица игры (таблица 22). Задается матрица размерностью m  n . Соответственно принять говорить, что игра имеет размерность m  n . Строки матрицы соответствуют чистым стратегиям стороны А, столбцы – чистым стратегиям стороны В. Элементы матрицы – выигрыши стороны А при всех возможных сочетаниях чистых стратегий сторон. Игра считается заданной, если наборы чистых стратегий и все значения a i j (i=1,2,…,m; j=1,2,…,n) заданы априорно. Целью (решения решения игры) оптимальных игровой является задачи определение стратегий сторон для отдельной партии или для многократного повторения партий игры, а также соответствующего им выигрыша стороны А (цены игры). При этом для стороны А оптимальной обеспечивающая считается ей стратегия, Таблица 22. В1 А1 a11 А2 a21 … … Аi ai1 … … Аm am1 В2 a12 a22 … ai2 … am2    … … … … … … … … Вj a1j a2j … aij … amj j … … … … … … … … Вn a1n a2n … ain … amn    … i … m n максимальный гарантированный выигрыш, для стороны В – стратегия, обеспечивающая ей минимальный гарантированный проигрыш. 95 Необходимо отметить, что при решении игровых задач приходится рассматривать и находить экстремумы несколько иного смысла, чем во всех рассмотренных выше задачах. С учетом неопределенности информации о стратегии противоположной стороны и гипотезы о выборе ею наилучшей для себя стратегии стороне А не приходится рассчитывать на получение максимального выигрыша, возможного в рассматриваемой задаче (максимального из заданных значений a i j ). Можно рассчитывать только на достижение максимума гарантированного выигрыша – нижней границы выигрыша при любой своей стратегии. Аналогично приходится решать задачу и для стороны В. Рассмотрим логику поиска максимального гарантированного выигрыша стороны А. Располагая матрицей игры, сторона A для выбора своей стратегии должна провести анализ матрицы в предположении, что сторона B будет действовать наиболее выгодным для себя способом (заранее узнавая или угадывая стратегию стороны A). Так при выборе стороной А некоторой чистой стратегии А i сторона В выберет такую стратегию, которая будет соответствовать минимальному элементу в строке А i :  i  min aij – это и есть гарантированный выигрыш стороны A при ij ой стратегии. При решении стратегической матричной игры гарантированные выигрыши стороны А заносятся в крайний правый столбец матрицы игры (таблица 22). Стороне A целесообразно выбрать такую стратегию Ai, которой будет соответствовать   max i . i При таком выборе сторона A при любой стратегии стороны B будет получать выигрыш не менее . То есть  - гарантированный выигрыш стороны A, максимальный на множестве чистых стратегий. Величина , определяемая, как   max min  ij называется нижней ценой игры. Соответствующая ей стратегия Ai* i j называется максиминной. 96 Выполнив подобный анализ для стороны В, получим  j  max aij i гарантированный проигрыш при j-ой стратегии. Гарантированные проигрыши стороны В заносятся в нижнюю строку матрицы игры (таблица 22). Стороне В целесообразно выбрать такую стратегию Вj, которой будет соответствовать   min  j . Величина , определяемая, как   min max aij представляет собой j j i минимальный гарантированный проигрыш стороны В и называется верхней ценой игры. Соответствующая ему стратегия Bj* называется минимаксной. Нетрудно убедиться в соотношении   . Действительно, в соответствии с рассмотренными правилами определения Таблица 23. нижней и верхней цены игры для всех i и j справедливо: i  ij  j, откуда при i = i* и j = j* получим   . Пример 20. В игре, матрица которой представлена в таблице 23, нижняя цена =2, максиминная стратегия - А2, верхняя А1 А2 А3 А4  В1 В2 В3 -1 1 0 3 2 4 4 -1 1 1 0 -2 4 2 4 В4 3 3 4 4 В5 5 4 1 2 5    -1 -2 цена =2, минимаксная стратегия - В2. Если в первой партии игры стороны применят соответственно максиминную и минимаксную стратегии, сторона А получит выигрыш, а сторона В – проигрыш величиной 2 единицы. Выбирая стратегию для следующей партии, каждая из сторон придет к выводу о нецелесообразности смены стратегии, так как при сохранении стратегии противника это может только ухудшить результат. Таким образом, найденное сочетание стратегий сторон оказывается устойчивым. Обе стороны не заинтересованы в их смене. Получено решение игры, справедливое как для единичной партии, так и для многократного повторения партий игры: оптимальной для стороны А является чистая стратегия А2, для стороны В – чистая стратегия В2, цена игры V=2 (ниже будет предложена другая – универсальная – форма записи решения). 97 Если интерпретировать матрицу игры в рассмотренном примере как форму задания некоторой функции двух аргументов a i j =F(А i ,В j ), то с поправкой на дискретность аргументов графическое отображение такой функции окажется аналогичным рисунку 10. Действительно, a22 в рассмотренном примере выполняет роль седловой точки (элемент a22 минимален в строке и максимален в столбце матрицы). Признаком наличия седловой точки в игре является совпадение нижней и верхней цены игры, седловая точка дает решение игры в чистых стратегиях. Цену игры, соответствующую решению игры в чистых стратегиях называют чистой ценой игры (==V). Пример 21. В игре, матрица которой Таблица 24. представлена в таблице 24, нижняя цена =2, максиминных стратегий две - А2 и А4, верхняя цена =2, минимаксных стратегий две - В2 и В3. В седловых данной точки. игре имеется Решение может четыре быть А1 А2 А3 А4  В1 В2 -1 1 3 2 4 -1 1 2 4 2 В3 2 1 2 2 В4 3 3 4 4 В5 5 4 1 2 5    -1 2 сформулировано следующим образом: оптимальными для стороны А являются чистые стратегии А2 и А4, для стороны В – чистые стратегии В2 и В3, чистая цена игры V=2. Полученное решение позволяет сформулировать следующие рекомендации для сторон: в единичной партии игры можно применить любую из указанных в решении стратегий, при многократном повторении партий игры указанные в решении стратегии можно чередовать в любой последовательности. Пример 22. В игре, матрица которой представлена в таблице 25, нижняя цена =2, максиминная стратегия - А2, верхняя цена =3, минимаксная стратегия - В3. Отметим, прежде всего, что здесь, в отличие от предыдущих примеров, нижняя и верхняя цены игры не совпадают. 98 Предположим, что в первой партии игры стороны применили найденные стратегии. Выигрыш стороны А и проигрыш стороны В составили 3 единицы. Выбирая стратегию для следующей партии, сторона А аналогично рассмотренным Таблица 25. примерам придет к выводу о нецелесообразности А1 А2 А3 А4  В1 В2 -1 1 4 2 3 -1 1 4 4 4 В3 3 1 -2 3 В4 3 3 4 4 В5 5 4 1 2 5    -1 -2 смены стратегии, а сторона В обнаружит возможность повышения своего результата за счет перехода к стратегии В2. Следующая партия игры пройдет при сочетании стратегий А2В2 и принесет результат 2 единицы. В следующей партии свою стратегию сменит сторона А. Дальнейшее развитие игры пройдет следующим образом: третья партия – А4В2, результат 4; четвертая - А4В3, результат -2; четвертая – А2В3, результат 3 и так далее. Можно рассмотреть иные подходы к выбору стратегий сторон в последующих партиях. Но в любом случае будут получены следующие выводы: 1. В рассматриваемой игре не удается найти «устойчивого» сочетания чистых стратегий сторон. При любом сочетании стратегий, примененных в очередной партии, какая-либо из сторон будет заинтересована в изменении стратегии. 2. В матрице игры отсутствует седловая точка, т.е. ни один ее элемент не является одновременно минимальным в строке и максимальным в столбце матрицы. 3. Несовпадение нижней и верхней цен игры позволяет сторонам рассчитывать на достижение результата, превышающего гарантированный ( для стороны А и  для стороны В) и расположенного в пределах между  и . Рассмотренный пример является примером стратегической матричной игры без седловой точки. Признак отсутствия седловой точки – несовпадение нижней и верхней цен игры (). Такая игра не имеет решения в чистых стратегиях, 99 справедливого для единичной партии. Решение может быть найдено только для случая многократного повторения партий игры на множестве смешанных стратегий. Смешанная стратегия предполагает применение в отдельных партиях игры различных чистых стратегий, причем стратегия для очередной партии выбирается случайно среди всех возможных чистых стратегий или их части. Случайность выбора необходима, так как только в этом случае сторона может рассчитывать на получение результата, превышающего гарантированный минимум. Смешанная стратегия определяется распределением вероятностей (частот применения) стороной ее чистых стратегий при многократном повторении партий игры. Смешанную стратегию стороны А принято описывать вектором P=(p1; p2; …; pm), для стороны В используется вектор Q=(q1; q2; …; qn), составляющие которых – вероятности или частоты применения сторонами их чистых стратегий. Очевидно, должны выполняться условия: 0  pi  1 , i=1,2,…,т; m  pi  1; i 1 0  q j  1 , j=1,2,…,n; n  qi  1 . i 1 Обоснование возможности получения решения игры в смешанных стратегиях может быть получено благодаря следующей трактовке: вместо множества чистых стратегий (А1,А2,…,Аm) для стороны А вводится множество смешанных стратегий, элементы которого соответствуют значениям вектора P. Это множество является непрерывным, бесконечным и несчетным. Аналогично видоизменяется множество стратегий стороны В. Логика поиска максиминной и минимаксной стратегий не нарушается, но появляется возможность нахождения седловой точки функции «непрерывных» аргументов. Решение игры без седловой точки сводится к определению оптимальных векторов P*=(p1*; p2*; …; pm*) и Q*=(q1*; q2*; …; qn*), соответствующих оптимальным в рассмотренном выше смысле смешанным стратегиям, и цены 100 игры, определяемой как средний выигрыш стороны А (средний проигрыш стороны В) при многократном проведении партий игры. Прежде чем рассматривать общие методы решения игр без седловой точки отметим следующее: 1. Часть исходных чистых стратегий могут не войти в оптимальную смешанную стратегию. Для них pi*=0 и qj*=0. 2. Чистые стратегии, для которых pi*и qj* оказываются ненулевыми, называют полезными. 3. Оптимальная смешанная стратегия должна доставлять каждой стороне результат, превышающий гарантированный в чистых стратегиях: a l j . В таком случае Аk является доминирующей, Аl – заведомо невыгодной, p*l =0. Пример 22 (продолжение). Рассмотрим пару стратегий В3 и В5. При первой, второй и четвертой чистых стратегиях стороны А стратегия В5 приносит стороне В проигрыш, больший, чем стратегия В3. При третьей стратегии стороны А результат применения В3 и В5 одинаков. Следовательно, стратегия В5 является заведомо невыгодной по сравнению с В3. 106 Аналогично можно обнаружить, что стратегия В4 заведомо невыгодна по Таблица 27. сравнению с В2. После исключения столбцов, соответствующих чистым стратегиям В4 и В5 (таблица 27) перейдем к анализу стратегий стороны А. При всех оставшихся чистых стратегиях стороны В стратегия А1 приносит стороне А выигрыш, меньший, В1 В2 -1 1 4 2 3 -1 1 4 4 4 А1 А2 А3 А4  В3 3 1 -2 3    -1 -2 чем стратегия А2. Следовательно, стратегия А1 является заведомо невыгодной по сравнению с А2. Такой же вывод можно сделать и по отношению к стратегии А3. После исключения строк, соответствующих Таблица 28. чистым стратегиям А1 и А3 (таблица 28) вернемся еще раз к анализу стратегий стороны В и исключим как заведомо невыгодную стратегию В1. В результате А2 А4 игру удалось упростить до размерности  Полученная игра соответствует 2 2 . В1 В2 4 2 1 4 4 4 В3 3 -2 3   -2 рассмотренному выше примеру 23. Остается записать решение исходной игры: P*=(0; 0,857; 0; 0,143), Q*=(0; 0,714; 0,286; 0; 0), V=2,286. Учет дублирующих стратегий. Если для одной из сторон имеется пара стратегий, приносящих одинаковый результат при всех чистых стратегиях противоположной стороны, их называют дублирующими. В процессе решения игры может учитываться только одна из дублирующих стратегий. Полученный итоговый результат может быть распространен на дублирующие стратегии в любой пропорции. В общем случае на основе указанного принципа может обнаруживаться и учитываться и большее, чем две, число дублирующих стратегий. 107 Пример 24 [4]. В игре, матрица которой представлена в таблице 29, нижняя цена =1, верхняя цена =4, седловая точка Таблица 29. отсутствует. Переходя к упрощению игры прежде Стратегии А2 и А4 соответствуют А1 А2 А3 А4 указанному выше признаку, следовательно,  всего исключим заведомо невыгодную по сравнению с В4 стратегию В5. В1 В2 0 5 5 0 5 5 5 0 5 5 В3 4 2 1 2 4 В4 2 4 1 4 4 В5 3 5 2 5 5    1 являются дублирующими. В процессе решения игры может далее рассматриваться только одна из них, например А2. Соответственно размерность задачи снизится. Целесообразно далее наравне с чистыми стратегиями А1 и А3 оперировать новой стратегией, которую можно обозначить как А24 и которая фактически является смешанной, причем исходные чистые стратегии А2 и А4 в рамках этой смешанной стратегии могут применяться с любыми частотами. Условно такой прием отразим следующим образом: A24 : A2  A4 . Упрощенная матрица игры представлена в таблице 30. Дальнейшее упрощение в рассматриваемом примере может быть выполнено на основе следующего приема. Таблица 30. А1 А24 А3  В1 В2 0 5 5 0 5 5 5 5 В3 4 2 1 4 В4 2 4 1 4    1 Учет симметричных фрагментов. Симметричным называют фрагмент матрицы игры, представленный в таблице 31. Рассматривая таблицу 31 как матрицу игры размерностью 2 2 , отметим, что при a  b такая игра не имеет седловой точки и может быть решена в смешанных стратегиях следующим образом: Таблица 31. 108 А1 А2 В1 В2 a b b a p1*  V a b a b  0,5 , q2*  1  q1*  0,5 ;  0,5 , p2*  1  p1*  0,5 ; q1*  a  a bb a a bb ab . 2 Если помимо симметричного фрагмента в образующих его столбцах и строках содержится дублирование или другие симметричные фрагменты, в процессе решения игры размерность ее матрицы может быть сокращена следующим образом: образующие симметричный фрагмент пары чистых стратегий заменяются смешанными с частотами по 0,5; сам фрагмент заменяется одним элементом матрицы игры величиной ab . 2 Вернемся к примеру 24, отметим, что он содержит два симметричных фрагмента, и применим рассмотренный прием. Получаемая в итоге матрица игры представлена в таблице 32. Пары чистых стратегий, Таблица 32. образующих симметричные фрагменты игры заменены смешанными: стратегий А1 и А24 В12: В12 В34  применение А124 2,5 3  с частотами по 0,5 (А124: p 1 =p 2 4 =0,5); А3 5 1 1 В34: q 3 =q 4 =0,5. На пересечении  5 3 А124, q 1 =q 2 =0,5; соответствующих им предусматривающей строк и столбцов помещены рассчитанные по указанному выше правилу выигрыши стороны А. Для новой игры нижняя цена =2,5, верхняя цена =3, седловая точка отсутствует (необходимо отметить, что рассмотренный прием в отдельных случаях может привести к получению седловой точки, так как вместо исходных чистых уже используются смешанные стратегии). Решение игры, представленной таблицей 32 дает следующие результаты: * p124  1 5 4   0,89 , 2,5  1  3  5  4,5 * p3*  1  p124  0,11 ; * * q34  1  q12  0,56 ; V=2,78. 109 * q12  1 3  0,44 ,  4,5 С учетом использованных в процессе решения приемов вернемся к исходному набору чистых стратегий и запишем решение игры для примера 24: P*=(0,445; p*2; 0,11; p*4), p*2 + p*4 = 0,445; Q*=(0,22; 0,22; 0,28; 0,28; 0), V=2,78. Отметим, что особенность записи оптимальной смешанной стратегии для стороны А в данном примере обусловлена наличием дублирующих стратегий и, как следствие, бесконечного множества решений. Оптимальной для стороны А является любая смешанная стратегия, удовлетворяющая записанному выше условию. Графический способ упрощения игр размерностью 2  n и m  2 . Пример 25. В игре, матрица которой представлена в таблице 33, нижняя цена =3, верхняя цена =6, седловая точка отсутствует. Отсутствуют также Таблица 33. заведомо невыгодные и дублирующие стратегии. В первых двух столбцах имеется симметричный фрагмент, но его учет рассмотренным выше способом невозможен из-за оставшейся части произвольного строк. Тем содержания не А1 А2  В1 В2 3 8 8 3 8 8 В3 4 6 6 В4 7 5 7   3 менее, размерность игры может быть снижена на основе графической интерпретации, рассмотренной в пункте 4.2.1. Рисунок формировании 24 показывает, оптимальной что в смешанной стратегии стороны В участвуют только две из четырех ее чистых стратегий, а именно В2 и В3. Действительно, в точке, дающей решение игры (верхней точке геометрического места гарантированных выигрышей стороны А, на рисунке – пересекаются жирной отрезки, ломаной Таблица 34. линии), соответствующие 110 А1 А2  В2 8 3 8 В3 4 6 6   3 только этим чистым стратегиям. Отрезки, соответствующие остальным чистым стратегии стороны В, при оптимальной смешанной стратегии стороны А проходят выше и соответственно приносят стороне В проигрыш, больший цены игры V. Следовательно, стратегии В1 и В4 не входят в число полезных и при дальнейшем решении могут не учитываться. В результате получена игра размерностью 2 2 (таблица 34). Она попрежнему не имеет седловой точки, но может быть решена на основе полученных выше расчетных соотношений: p1*  63 3   0,43 , p2*  1  p1*  0,57 ; 8643 7 q2* Таблица 35. 64   0,29 , q3*  1  q2*  0,71 ; V=5,14. 7 С учетом всего исходного набора чистых стратегий решение примера 25 имеет вид: P*=(0,43; 0,57), Q*=(0; 0,29; 0,71; 0), V=5,14. Пример 26. В игре, матрица которой представлена в таблице 35, нижняя цена =3, верхняя цена =5, седловая А1 А2 А3 А4  В1 В2 3 5 5 0 1 7 4 3 5 7   1 3 точка отсутствует. Отсутствуют также заведомо невыгодные и дублирующие стратегии. Процедура упрощения данной игры иллюстрируется рисунком 25. Рисунок формировании 25 показывает, оптимальной что в смешанной стратегии стороны А участвуют только две ее чистые стратегии, а именно А1 и А4. Это следует из того обстоятельства, что в точке, дающей решение геометрического игры места (нижней точке гарантированных проигрышей стороны В, на рисунке – жирной 111 ломаной линии), пересекаются отрезки, соответствующие только этим чистым стратегиям. Отрезки, соответствующие остальным чистым стратегии стороны А, при оптимальной смешанной стратегии стороны В проходят ниже и соответственно приносят стороне А выигрыш, меньший цены игры V. Следовательно, стратегии А2 и А3 не входят в число полезных и при дальнейшем решении могут не учитываться. В результате получена игра размерностью 2 2 (таблица 36). Она попрежнему не имеет седловой точки, но может быть решена на основе полученных выше расчетных соотношений: Таблица 36. А1 А4  В1 В2 3 5 4 3 4 7 p1*    3 34 1   0,33 , p4*  1  p1*  0,67 ; 3354 3 q1*  35  0,67 , q2*  1  q1*  0,33 ; V=3,67. 3 С учетом всего исходного набора чистых стратегий решение примера 40 имеет вид: P*=(0,33; 0; 0; 0,67), Q*=(0,67; 0,33), V=3,67. В отличие от рассмотренных выше, следующий пример демонстрирует ограниченность метода упрощения и требует для своего решения других методов. Пример 27. В игре, матрица которой представлена в таблице 37, нижняя цена =-3, верхняя цена =4, седловая точка Таблица 37. отсутствует. Заведомо невыгодные и дублирующие стратегии, симметричные фрагменты также отсутствуют. применения графического способа упрощения. Таким А1 А2 А3 образом, методом упрощения получить решение данной  Размерность игры 3 3 , что исключает возможность игры не удается. 112 В1 В2 2 -3 -3 4 4 -5 4 4 В3 4 -5 6 6   -5 -5 4.2.3. Решение стратегических матричных игр методом линейного программирования Сведение стратегической матричной игры без седловой точки к задаче линейного программирования обеспечивается при условии положительности цены игры V. Для этого в соответствии с (22) достаточно   0. Отметим сразу, что если такое условие для рассматриваемой игры не выполняется, достаточно в процессе ее решения найти минимальный элемент матрицы (очевидно, он будет отрицательным) и вычесть его величину из всех элементов матрицы, тем самым сдвигая их в положительном направлении. Полученная матрица игры будет содержать только неотрицательные элементы a i j , включая, очевидно и нижнюю цену игры. Анализируя полученные выше расчетные соотношения (23)-(29), нетрудно убедиться, что такой прием не повлияет на величины оптимальных частот и приведет лишь к смещению величины цены игры V. Эту поправку необходимо будет учесть при записи окончательного результата. Обратимся к соотношениям (28) и условиям, которым подчиняются значения частот применения стороной А ее чистых стратегий: 0  pi  1 , m i=1,2,…,т;  pi  1. Введем новые переменные: i 1 xi  pi , i=1,2,…,т. С учетом V pi  0 и V>0 на все переменные xi накладывается требование неотрицательности, традиционное для аргументов задачи линейного программирования. m Разделим обе части уравнения  pi  1 и неравенств (28) на i 1 положительную переменную V: m m pi 1  V   xi  V , i 1 i 1 113 (30) m  xi aij  1 , j=1,2,…,n. (31) i 1 Целью решения стратегической матричной игры для стороны А является нахождение таких значений частот pi, а следовательно, и связанных с ними значений переменных xi, которые доставят стороне А наибольший средний выигрыш V. Введем на основе (30) целевую функцию m 1 q     xi  max . V i 1 (32) Теперь задача поиска оптимальной стратегии стороны А может быть сформулирована как задача линейного программирования: требуется определить неотрицательные значения переменных x 1 ,x 2 ,…,x m , доставляющие максимум целевой функции (32) и удовлетворяющие системе ограничений (31). Эта задача сводится к форме ОЗЛП с m свободными (в их качестве выступают исходные переменные задачи xi) и n базисными переменными: m q   xi  max ; i 1 m xj  xm  j  1   aij xi  0 , i=1,2,…,n. (33) i 1 Матрица коэффициентов для данной задачи в соответствии с (9)-(10) будет иметь вид: 1  1  a11 ... ...  1  an1 ... 1 ...  a1m . ... ... ...  anm 114 (34) Решение полученной задачи линейного программирования позволит найти V  1 и частоты, определяющие оптимальную смешанную стратегию стороны q А: p*i =x i V, i=1,2,…,т. Отметим, что дополнительно удается установить и полезные стратегии стороны В: для них соответствующие переменные xm+j в решении ОЗЛП будут равны нулю, что соответствуют равенствам в (33) и соответственно в (28). Теперь обратимся к соотношениям (29) и условиям, которым подчиняются значения частот применения стороной В ее чистых стратегий: 0  q j  1 , n j=1,2,…,n;  q j  1. Введем новые переменные: u j  Vi , j=1,2,…,n. q С учетом j 1 qi  0 и V>0 на все переменные ui накладывается требование неотрицательности. n Разделим обе части уравнения  q j  1 и неравенств (29) на V и учитывая, j 1 что целью решения стратегической матричной игры для стороны В является нахождение таких значений частот qj, (и значений переменных uj), которые доставят стороне В наименьший средний проигрыш V, введем целевую функцию. Сведем задачу к форме ОЗЛП введением m дополнительных переменных: n q   uj  min ; i 1 n ui  un  i  1   aijuj  0 , i=1,2,…,m. (35) j 1 Решение полученной задачи линейного программирования позволит найти V  В: 1 и частоты, определяющие оптимальную смешанную стратегию стороны q q*j =u j V, j=1,2,…,n. Нулевым значениям соответствовать полезные стратегии стороны А. 115 переменных xn+i будут Сопоставляя запись задачи (35) с матрицей (34), можно убедиться, что критерий оптимальности и ограничения здесь соответствуют столбцам матрицы, что аналогично связи задачи (11) с матрицей (10). Таким образом, задача (35) является двойственной по отношению к задаче (33). Следовательно, для получения полного решения игровой задачи достаточно решить одну из получаемых задач линейного программирования. Например, после решения задачи (33) помимо цены игры V и оптимальной смешанной стратегии стороны А может быть получена и оптимальная стратегия стороны В – на основе коэффициентов первой строки полученного оптимального линейного плана. Пример 25 (продолжение). Вернемся к примеру, решенному выше методом упрощения. Матрица игры представлена в таблице 33. Составим для данной игры систему неравенств (28): 3 p1  8 p2  V , 8 p1  3 p2  V , 4 p1  6 p2  V , 7 p1  5 p2  V . Введем, как это показано выше, целевую функцию, свободные и базисные переменные ОЗЛП: x1  p1 p  0 , x2  2  0 ; V V q 1   x1  x2  max ; V 3x1  8 x2  1 , 8 x1  3x2  1 , 4 x1  6 x2  1, 7 x1  5 x2  1 ; x3  1  3x1  8 x2  0 , x4  1  8 x1  3x2  0 , x5  1  4 x1  6 x2  0 , 116 x6  1  7 x1  5 x2  0 . (36) Исходный линейный план представлен в таблице 38. Решение задачи симплекс-методом отражено в таблицах 39-41. 117 Таблица 38. 1 -x1 q -1 x4 -1 x5 -1 x6 -6 4 3 3 x5 3 -5 7 3 x6 3 118 8 4 3  41 42 4 55 14 3 3 14 41 82 21 14 3 7 3 7 3  55 21 2 7 3 3 21 3 110 42 5 14 8 16 21 3 21 3 1 14 4 56 5  10 1 3 -x2 3 42 3  55 1 32 3 -7 7 x4 3 1 3 4 5 64 3 -4 4 3 -x3 5 x1 -3 8 3 3 1 8 3 -8 8 q -8 1 3 1 8 3 -3 1 1 1 1 3 -1 x3 -x2 1 1 Таблица 39. 3  41 14 Таблица 40. 1 q 3 14 x4 x2 x6 1 5 1 x1 -x3 1 18 5 14 5 7 2 5 5 14  55 В 1 11 252  11 18 результате применения цена 1 1 12 5 7 x3 605 x2 6 36  55 18 36 9 1 2 9 9 126 5 x6 36  11 18  19 36 252 игры стратегий 36 36  41 14 7 1 12 1  55 9 5 36 84 3 14 7 126 x1 14  55 18 -x5 252 55  55 -x4 1 18 q 7 6 7 36 1 14 7  55 4 7 84 1 5 14 1 18 3 5 -x5 7 252 7 Таблица 41. V  1 36   5,14 , q 7 стороны А оптимальные p1*  x1V  частоты 1 36   0,43 , 12 7 1 36 p2*  x2V    0,57 . 9 7 Обратим внимание на то, что базисные переменные исходного плана (таблица 38) соответствуют столбцам 119 матрицы игры (таблица 33), а следовательно, чистым стратегиям стороны В. А именно: x3  B1 , x4  B2 , x5  B3 , x6  B4 . Решение ОЗЛП дает x 4 =x 5 =0 (свободные переменные). Следовательно, неравенства, соответствующие В2 и В3 в системах (36) и (28) для рассматриваемой задачи обращаются в равенства, что является признаком полезных стратегий. Учитывая же двойственность задач линейного программирования, получаемых на основе стратегической матричной игры, отметим, что для двойственной задачи на основе оптимального плана ОЗЛП (таблица 41) будет иметь место: u 1 =u 4 =0, u2  частоты применения p1*  x1V  5 1 , u3  . Остается рассчитать оптимальные 18 36 стратегий стороны В: q2*  u2V  1 36   0,29 , 18 7 1 36   0,43 , q1*  q4*  0 . 12 7 Результаты совпадают с полученным выше решением рассматриваемого примера. Следует также отметить, что исходный линейный план ОЗЛП, формируемый на основе соотношений (28), может быть получен непосредственно на основе матрицы игры без представленных выше промежуточных преобразований. А именно: - коэффициент на пересечении первых строки и столбца всегда равен нулю; - все остальные коэффициенты первой строки равны единице; - все остальные коэффициенты первого столбца равны «-1»; - в оставшиеся части строк, начиная со второй заносятся выигрыши из столбцов матрицы игры с противоположным знаком. Если ОЗЛП формируется на основе соотношений (29), правила составления исходного плана будуь следующими: 120 - коэффициент на пересечении первых строки и столбца всегда равен нулю; - все остальные коэффициенты первой строки равны «-1»; - все остальные коэффициенты первого столбца равны единице; - в оставшиеся части строк, начиная со второй непосредственно заносится матрица игры. Воспользуемся сформулированными правилами и рассмотрим другой представленный выше пример. Пример 27 (продолжение). Матрица игры представлена в таблице 37. Для обспечения возможности применения метода линейного программирования обеспечим неотрицательность элементов матрицы. Минимальный выигрыш, содержащийся в матрице игры a 2 3 =-5. Вычитание его из всех элементов матрицы игры приводит к получению новой матрицы, представленной в таблице 42. Используя соотношения (29), сведем данную Таблица 42. игровую задачу к задаче линейного программирования. Исходный линейный план представлен в таблице 43. Решение задачи симплекс-методом отражено в таблицах 44-46. На основе полученного решения задачи линейного А1 А2 А3  В1 В2 7 2 2 9 9 0 9 9 В3 9 11 11   программирования (таблица 46) получим решение игры, представленной в таблице 42: V  1  5 (здесь, в отличие от (35), решалась задача обеспечения q максимума целевой функции); q3*  u3V  1  5  0,25 , 20 p3*  u6V  1  5  0,25 . 20 q1*  u1V  p1*  u4V  1 1  5  0,25 , q2*  u2V   5  0,5 , 10 20 1  5  0,25 , 20 121 p2*  u5V  1  5  0,5 , 10 Таблица 43. 1 -u1 q -1 1 9 1 2 u5 9 1 9 9 9 u5 9 11 4 2 81 44  22 1 81 9 9 81 9 9 9 9 9  22 9 2 2 1 9 2 1 81 9 4 81 -u3 -1 81 2 7 1 11 7 9 -u2 9 2 81 9  14 7  22 1 u4 1 7 2  77 9 9 -u6 9 q 9 9 2 9 1 u6 9 2 1 2 7 1 -1 11 9 7 7 -u3 -1 1 9 1 u4 -u2 Таблица 44. 9  22 11 81 81 9 u1 9 122 Таблица 45. 1 16 1 u4 20 11 1 9  59 810 1 81  649 1 4 9 2 1 1 80 649  11 180 720 11 11 40 1 u3 -u4 1 10 1 9 81 20 20 20  59 80 40 80 80 1 10 9 1 81 1 40 20 11 40 u2 40 9  99 1 -u5 q 81 11 5 -u6 20 81  22  11 3240 180 9 1 81 40 9 1 81 90 9 9 80 81 -u3 1 1620  59 2 81 -u5 81  59 81 u2 u1 405 1 7 7 81 q 4 -u6 Таблица 46. 20 80 11 40  99 80 u1 80 Остается внести поправку в значение цены игры и записать решение исходной игровой задачи: V=5-5=0, P*=(0,25; 0,5; 0,25), Q*=(0,25; 0,5; 0,25). 4.2.4. Итерационный алгоритм Брауна-Робинсон Приближенный численный метод решения игр основан на использовании итерационного алгоритма Брауна-Робинсон. Данный алгоритм предусматривает моделирование многократного повторения партий игры с выбором каждой из сторон для очередной партии чистой стратегии, обеспечивающей ей наилучший 123 результат в условиях применения противоположной стороной наблюдаемой смешанной стратегии. Наблюдаемая, или опытная, смешанная стратегия рассчитывается по результатам проведенных партий игры. Установлено, что при увеличении количества смоделированных партий опытные стратегии сторон стремятся к оптимальным, а средний выигрыш стороны А – к цене игры. Проследим работу алгоритма на основе примера 27. Матрица игры представлена в таблице 42. Предположим, что для первой партии игры сторона А выбрала максиминную стратегию А1, сторона В – одну из минимаксных стратегий В2. В результате этой партии выигрыш стороны А составил «–3» единицы. Опытная стратегия стороны А описывается вектором P=(1; 0; 0), опытная стратегия стороны В – вектором Q=(0; 1; 0). Для второй партии игры сторона В выбирает чистую стратегию в условиях применения стороной А чистой стратегии А1. Очевидно, она придет к выводу о целесообразности сохранения стратегии В2. В свою очередь сторона А для второй партии выбирает чистую стратегию в условиях применения стороной В чистой стратегии В2. В этом случае наибольший выигрыш она сможет получить, перейдя к стратегии А2. Итак, сочетание стратегий сторон во второй партии игры А2В2, выигрыш стороны А во второй партии составит 4 единицы. Суммарный накопленный выигрыш стороны А по результатам двух партий игры равен 1, средний выигрыш за две партии составил 0,5. После двух партий опытная стратегия стороны А описывается вектором P=(0,5; 0,5; 0), опытная стратегия стороны В – вектором Q=(0; 1; 0). Для третьей партии игры сторона В выбирает чистую стратегию в условиях применения стороной А опытной смешанной стратегии. Поэтому прогнозируемый результат для каждой из возможных чистых стратегий она должна рассчитывать 124 усреднением соответствующего столбца матрицы игры с учетом опытных частот применения стороной А ее чистых стратегий – элементов полученного по предшествующим партиям вектора P. Наименьший ожидаемый проигрыш соответствует стратегиям В1 и В3. Примем для стороны В правило выбора в таких случаях стратегии с наименьшим номером. Результаты работы алгоритма на рассмотренных и последующих шагах подробно представлены в таблице 47. В первом столбце таблицы приводится номер очередной партии, итог которой и накопленные с учетом которой результаты представлены в соответствующих строках. В столбцах 2 и 9 – чистые стратегии, примененные сторонами в очередной партии, в столбцах 3-5 – опытная смешанная стратегия стороны А после очередной партии, в столбцах 4-6 – ожидаемые проигрыши стороны В при различных ее чистых стратегиях в условиях применения стороной А такой опытной стратегии, в столбцах 10-12 – опытная стратегия стороны В, в столбцах 13-15 – ожидаемые проигрыши стороны А при различных ее чистых стратегиях в условиях применения стороной В текущей опытной стратегии, в столбце 16 – выигрыш стороны А, соответствующий сочетанию чистых стратегий из столбцов 2 и 9, в столбце 17 – суммарный (накопленный) выигрыш стороны А с учетом рассматриваемой партии, в столбце 18 – средний выигрыш стороны А в проведенных партиях игры (отношение накопленного выигрыша к номеру строки). Представленные в таблице 47 результаты в сопоставлении с результатами решения рассматриваемого примера методом линейного программирования подтверждают возможность получения решения игры итерационным методом, причем точность результата, очевидно, определяется количеством смоделированных партий. Трудоемкость решения задачи на основе рассматриваемого алгоритма, по крайней мере, для рассмотренного примера достаточно велика. Впрочем, практика 125 его применения показывает, что большинство задач характеризуется существенно меньшей трудоемкостью. 126 стратегия й проигрыш стороны А стороны В p1 p2 p3 В1 В2 В3 В Опытная Прогнозируемы стратегия й выигрыш стороны В стороны А q1 q2 q3 А1 А2 А3 выигрыш Прогнозируемы Выигрыш Накопленный № А Опытная выигрыш Средний Таблица 47. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1 А1 1 2 -3 4 В2 1 -3 4 -5 -3 -3 -3 2 А2 0,5 0,5 -0,5 0,5 -0,5 В2 1 -3 4 -5 4 1 0,5 3 А2 0,33 0,67 -1,33 1,67 -2 -3 -2 -0,67 4 А2 0,25 0,75 -1,75 2,25 -2,75 В3 0,25 0,5 0,25 -7 -5 -7 -1,75 -2 В1 0,33 0,67 -1,33 1,67 -7 -7 … 100 0,293 0,434 0,273 0,02 0,576 0,404 -0,12 … 103 0,276 0,505 0,219 0,194 0,525 0,281 -0,002 … 104 0,261 0,503 0,236 0,237 0,504 0,259 -0,026 … 105 0,254 0,50 0,246 0,246 0,502 0,252 4,3.10-4 4.3. Примеры решения стратегических матричных игр Рассмотренные ниже примеры позволяют сделать некоторые выводы в плане сравнительного анализа возможностей рассмотренных методов решения стратегических матричных игр, а также практического значения получаемых решений. Пример 28. В игре, матрица которой представлена в таблице 48, нижняя цена =2, верхняя цена =4, седловая точка отсутствует. Решим данную игру тремя рассмотренными выше методами. 127 Метод упрощения. Исключим последовательно Таблица 48. заведомо невыгодные стратегии: А4 как заведомо невыгодную четвертой строки матрицы), А2 как заведомо А1 А2 А3 А4 невыгодную по сравнению с А3 (без учета уже  по сравнению с А1, В3 как заведомо невыгодную по сравнению с В2 (без учета уже исключенной В1 В2 9 4 1 3 1 4 6 4 9 4 В3 6 6 5 2 6 В4 2 4 8 1 8    1 1 исключенного третьего столбца матрицы). Матрица игры после выполненных упрощений представлена в таблице 49. Решение можно продолжить графическим Таблица 49. способом. Из рис. 26 следует, что особенностью рассматриваемой игры является наличие бесконечного множества решений, включающего в себя: а) смешанную стратегию, соответствующую А1 А3  В1 В2 9 4 1 4 9 4 В4 2 8 8   1 левому концу отрезка, показанного на рис. 26 жирной линией (оптимальные частоты применения чистых стратегий для стороны А отмечены на рисунке как p1*max и p3*min , для стороны В полезными являются стратегии В2 и В4); б) смешанную стратегию, соответствующую правому концу отрезка, показанного на рис. 26 жирной линией (оптимальные частоты применения чистых стратегий для стороны А отмечены на p1*min рисунке как и p3* max , для стороны В полезными являются стратегии В1 и В2); в) для стороны А любую смешанную частотами p1*min  p1  p1*max , p3*min  p3  p3*max , p 1 +p 3 =1 (множество точек стратегию с 128 отрезка, показанного на рис. 26 жирной линией), для стороны В – чистую стратегию В2. Учитывая в каждом случае только полезные стратегии, получим аналогично рассмотренным выше примерам численное решение: - для варианта а) p1*max  84 4   0,67 , p3*min  1  p1*max  0,33 ; 8442 6 q2*  82  1 , q4*  1  q2*  0 ; V=4; 6 - для варианта б) p1*min  4 1 3   0,375 , p3*max  1  p1*min  0,625 ; 9  4  4 1 8 q1*  44  0 , q2*  1  q1*  1 ; V=4. 8 В общем виде результат, полученный методом упрощения, можно сформулировать следующим образом: для стороны А оптимальной является любая смешанная стратегия с частотами 0,375  p1  0,67 , p 3 =1-p 1 , для стороны В – оптимальной является чистая стратегия В2. Метод линейного программирования. Отметим сразу, что при использовании данного метода предварительное исключение заведомо невыгодных стратегий позволяет значительно снизить размерность задачи и соответственно трудоемкость решения. Воспользуемся этим и перейдем к задаче линейного программирования для упрощенной игры (таблица 49). Решение получаемой задачи линейного программирования симплекс-методом представлено в таблицах 50-52. 129 Таблица 50. 1 -x1 q -1 x4 -1 x5 9 9 7 -8 2 9 2 x5 9 130 1 4 175 144 1  32 9 8 35 36 32 9 9  70 9 4 9 72 1 2 1 1 32 9 9 9 9 1 288 5 8 36 9 -x2 9 1 5 x4 9 1 9 9 5 4 9 -2 2 x1 -x3 5 1 -4 4 9 9 1 9 -4 4 q -1 1 9 1 1 9 -9 1 1 1 1 9 -1 x3 -x2 1 1 Таблица 51. 32 9  35 16 Таблица 52. 1 1 q 3 x1 5 x2 7 x5 4 32 32 16 -x3 -x4 1 1 8 1 1 9 3 8 4 32 35 4 32 16 В результате цена игры V   стратегий стороны А 1  4 , оптимальные частоты применения q p1*  x1V  3  4  0,375 , 32 p3*  x2V  5  4  0,625 , 32 p2*  p4*  0 (заведомо невыгодные стратегии), оптимальные частоты применения стратегий стороны В q1*  x3V  0 , q2*  x4V  1  4  1, 4 q3*  0 (заведомо невыгодная), q4*  x5V  0 (соответствует свободной переменной двойственной задачи линейного программирования). Таким образом, симплекс-метод позволил получить лишь одно частное решение из бесконечного множества решений, имеющихся в рассматриваемой задаче. Нетрудно убедиться, что графический метод, рассмотренный в подразд. 4.1, позволяет получить здесь все множество решений. Любой же формальный 131 метод решения задачи линейного программирования дает эффект, аналогичный симплекс-методу. Численное решение рассмотренной задачи с помощью итерационнго алгоритма Брауна-Робинсон приводит к следующим результатам: после 105 партий игры опытная стратегия стороны А p1=0,6658; p2=0; p3=0,3342; p4=0; опытная стратегия стороны В q1=0,0004; q2=0,9980; q3=0; q4=0,0016; средний выигрыш стороны А (оценка величины цены игры) V=4,0005. Нетрудно видеть, что алгорим Брауна-Робинсон аналогично симплексметоду также приводит к одному из возможных частных решений задачи. Теперь рассмотрим практический пример, требующий предварительной формализации (пример 8 из раздела 1). Пример 8 (продолжение). Примем, что имеются четыре группы покупателей, выбор из которых конкретной группы любой из сторон равновероятен. Перечислим все возможные чистые стратегии сторон. Для стороны (фирмы) А A1: 1+1+0+0 (имеющиеся партии продукции предлагаются двум разным группам покупателей); A2: 2+0+0+0 (обе партии продукции предлагаются одной группе покупателей). Для стороны (фирмы) В B1: 1+1+1+1 (партии продукции предлагаются четырем разным группам покупателей); B2: 2+2+0+0 (двум разным группам покупателей предлагаются по две партии продукции); B3: 2+1+1+0 (одной произвольно выбранной группе предлагаются две партии продукции, двум по одной партии); B4: 3+1+0+0; B5: 4+0+0+0. 132 покупателей С учетом сформулированных в разделе 1 условий задачи рассчитаем величины вероятности заключения стороной А контракта на реализацию хотя бы одной партии продукции для всех возможных сочетаний стратегий сторон и составим матрицу игры (таблица 53). Нижняя верхняя цена цена отсутствует. =3/4, После игры =1/2, седловая точка данной исключения заведомо Таблица 53. невыгодных стратегий В4 и B5 применение А1 А2 любого из рассмотренных методов приводит к  В1 1 1 В2 5/6 1/2 5/6 В3 1/2 3/4 3/4 В4 B5  5/6 1 0 3/4 3/4 1/2 5/6 1 результату: P*=(0,375; 0,625), Q*=(0,25; 0,75; 0; 0; 0), V=0,625. С практической точки зрения фирме А следует порекомендовать при многократном повторении рассматриваемой ситуации в пяти случаях из восьми направлять обе партии продукции в один регион (на одну биржу и т.п.) из четырех возможных. Однако с учетом величины цены игры (вероятности реализации хотя бы одной партии продукции) немногим более 0,5 предпочтительной представляется рекомендация отказаться от таких торговых операций, так как даже небольшое их количество может привести к банкротству. Контрольные вопросы 1. Как составляется матрица игры? 2. Почему оптимальная стратегия максимизирующей стороны не определяется абсолютным минимумом элементов матрицы игры? 3. Сформулируйте порядок действий при поиске седловой точки матрицы игры. 4. В разница с практической точки зрения между решениями игры в чистых и смешанных стратегиях? 5. По каким признакам выделяются стратегии: заведомо невыгодная, дублирующая, доминирующая, полезная? 133 6. Перечислите основные приемы, или способы, упрощения игр. 7. На каком принципе основан итерационный метод решения игр – метод Брауна-Робинсон? 5. СТАТИСТИЧЕСКИЕ МАТРИЧНЫЕ ИГРЫ Статистической матричной игрой называют одношаговую игровую задачу, в которой одна из сторон может рассматриваться как нейтральная. Она выбирает свою стратегию произвольно или случайно, не преследуя цели получения наилучшего результата в данной игре. Поэтому для статистической матричной игры часто используют название «игра с природой», имея в виду, что целью решения игры является обоснование выбора оптимальной стратегии для стороны А (максимизирующей стороны), а сторона В играет роль нейтральной стороны – «природы» и обозначается буквой «П». Соответственно стратегию стороны П называют состоянием природы. Для игры с природой (таблица 54) можно выделить два основных варианта постановки задачи. Неопределенность: вероятностей состояний распределения природы не существует или учет такого распределения нецелесообразен, например, если требуется выбрать стратегию для единственной партии игры или заведомо Таблица 54. малого количества партий. П1 А1 a11 А2 a21 … … Аi ai1 … … Аm am1 П2 a12 a22 … ai2 … am2 … … … … … … … Пj a1j a2j … aij … amj … … … … … … … Пn a1n a2n … ain … amn    … i … m Случайность: учитывается некоторое априорно известное распределение вероятностей состояний природы, возможно, известное неточно. Рассмотрим некоторые наиболее известные правила (критерии) выбора решения в статистической матричной игре [17]. 134 Далее через i будем обозначать прогнозируемый в соответствии с применяемым критерием выигрыш стороны А при применении ею чистой стратегии Ai, через  - максимальный прогнозируемый выигрыш, определяющий выбор оптимальной стратегии. Для ситуации неопределенности можно выделить следующие критерии или позиции, принимаемые за основу при выборе стратегии: 1а – максиминный критерий Вальда (позиция крайнего пессимизма) основан на гипотезе о том, что при любом выборе стратегии стороны А состояние природы всякий раз оказывается наихудшим из возможных (природа неосознанно ведет себя как игрок с противоположными интересами). В этом случае прогнозируемый выигрыш совпадает с гарантированным выигрышем в стратегической матричной игре,  - с нижней ценой стратегической матричной игры, и для стороны А выбирается максиминная стратегия: А*~   max min  ij . j i 1б – позиция крайнего оптимизма – предполагается, что природа неосознанно «подыгрывает» стороне А: А*~   max max ij . i j 1в – позиция компромисса (между пессимистической и оптимистической   позициями): А*~   max  min ij  max ij  . i  j j  1 n  1г – позиция нейтралитета: А*~   max   ij  .  i n  j 1  1д – критерий пессимизма-оптимизма Гурвица – обобщенный по отношению к критериям 1а, 1б и 1в: А*~   max  c min ij  1  c  max ij  , где c – j i  j  коэффициент пессимизма, выбираемый в диапазоне [0; 1]. В частных случаях: при c=0 приходим к позиции крайнего оптимизма, при c=1 – к позиции крайнего пессимизма, при c=0,5 – к позиции компромисса. 135 1е – критерий минимаксного риска Сэвиджа (позиция относительного пессимизма) оперирует величиной риска – величиной недополученного выигрыша из-за незнания будущего состояния природы и невозможности заранее выбрать соответствующую ему наилучшую стратегию. Величина риска для i-ой стратегии при j-ом состоянии природы определяется следующим образом: rij  max aij  aij . i Пессимизм в рамках данного критерия проявляется в смысле гипотезы о том, что состояние природы всегда оказывается наихудшим, то есть обеспечивает максимально возможный при выбранной стороной А стратегии i-ой недополученный выигрыш. Правило выбора оптимальной стратегии стороны А сводится к его минимизации: А*~   min max rij  min max  max aij  aij  . i i j j  i  Для ситуации случайности рассматривается априорно известное n распределение вероятностей состояний природы  q j  1. (q 1 ,q 2 ,…q n ), j 1 Наиболее известны следующие критерии: 2а – равномерного критерий Байеса-Лапласа: распределения  n  А*~   max   q j  ij  .  i   j 1  вероятностей состояний природы В случае критерий эквивалентен 1г. 2б – критерий Ходжа-Лемана – оперирует коэффициентом доверия к рассматриваемому распределению вероятностей c  0;1:  n  А*~   max  c  q j  ij  1  c  min aij  . В частных случаях при c=1 получаем  j i   j 1  критерий Байеса-Лапласа, при c=0 – критерий Вальда 1а. 2в – критерий Гермейера – ориентирован в основном на экономические задачи и оперирует величинами затрат или потерь стороны А при различных ее стратегиях и различных условиях проведения операции (состояниях природы). 136 Соответственно элементы матрицы игры при применении этого критерия предполагаются неположительными. Поэтому максимальной потере при i-ой стратегии стороны А соответствует минимум по строке матрицы игры, а выбор оптимальной стратегии по критерию минимума потерь (с учетом распределения вероятностей состояний природы) производится по правилу: А*~   max  min aij q j  . i  j  В предыдущем разделе был рассмотрен пример 8 в форме стратегической матричной игры, причем было отмечено, что полученная оптимальная смешанная стратегия не имеет практического смысла в случае, если рассматриваемая операция (партия игры) будет проводиться однократно или малое количество раз. Для формирования обоснованных и более конкретных рекомендаций по выбору стратегии стороны А в подобных задачах более эффективным оказывается рассмотрение статистической матричной игры. В этом случае появляется возможность применения широкого набора рассмотренных критериев. Функция окончательного выбора стратегии при этом передается лицу, принимающему решение (заказчику, директору фирмы), получающему возможность учитывать дополнительные данные или свои субъективные представления о возможном поведении конкурентов, состоянии рынка и т.п. Пример 8 (продолжение). Состояния природы соответствуют рассмотренным ранее для данного примера стратегиям стороны В. В таблице 55 представлена матрица статистической игры, дополненная результатами расчетов и рекомендуемыми стратегиями в соответствии с критериями 1а – 1д. Для критерия Гурвица принято значение коэффициента пессимизма c=0,5. Таблица 55. А1 П1 П2 П3 П4 П5 1а 1б 1в 1г 1д 0 5/6 1/2 5/6 1 1 3,17 0,3 1 137 А2 1 1/2 3/4 3/4 3/4 0,5 1 1,5 3,75 0,65 Рекомендуемые стратегии: А2 А1, А2 А2 А2 А2 В таблице 56 представлена матрица рисков и результаты расчета в соответствии с критерием Сэвиджа. Таблица 56. П1 П2 П3 П4 П5 А1 1 А2 1/3 1/4 max rij  j 1 0 1/12 1/4 1/4 Рекомендуемая стратегия: А2 При применении статистических критериев рассматривалось априорное распределение вероятностей состояний природы Q=(0,3; 0,2; 0,3; 0,1; 0,1). В таблице 57 представлены результаты применения критериев 2а и 2б. Рассматривалось значение коэффициента доверия c=0,5. Таблица 57. П1 П2 П3 П4 П5 2а 2б А1 0 5/6 1/2 5/6 0,5 0,25 А2 1 1/2 3/4 3/4 3/4 0,775 0,638 1 Рекомендуемые стратегии: А2 А2 При применении критерия Гермейера за величину потери примем математическое ожидание количества нереализованных партий продукции, которое в соответствии со смыслом критерия будем учитывать со знаком «-». Например: при стратегии А1 и состоянии природы П1 не будут реализованы обе 138 партии; при стратегии А2 и состоянии природы П1 не будет реализована одна партия; при стратегии А1 и состоянии природы П2 и шести возможных вариантах выбора двух групп покупателей из четырех в одном случае не будут реализованы обе партии продукции, в четырех случаях – одна партия; поскольку по условиям задачи варианты выбора равновероятны, получим математическое ожидание количества нереализованных партий продукции, равное единице и так далее. Получаемая таким образом матрица потерь и результаты применения критерия Гермейера представлены в таблице 58. Таблица 58. П1 П2 П3 П4 П5 ai1q1 ai2q2 ai3q3 ai4q4 ai5q5 min aij q j А1 -2 -1 -1,5 -1 -0,5 -0,6 -0,2 -0,45 -0,1 -0,05 -0,6 А2 -1 -1 -1 -0,75 -0,5 -0,3 -0,2 -0,3 -0,075 -0,05 -0,3 j Рекомендуемая стратегия: А2 Полученные результаты вполне убедительны для выбора стратегии А2. Контрольные вопросы 1. В чем принципиальное отличие постановки статистической игровой задачи от стратегической? 2. Каковы основные варианты постановки статистической игровой задачи? 3. Назовите и кратко сформулируйте критерии выбора оптимальной стратегии в статистической матричной игре. 4. Как следует использовать статистической матричной игры? 139 на практике результаты решения 6. МНОГОКРИТЕРИАЛЬНЫЕ ЗАДАЧИ ПРИНЯТИЯ РЕШЕНИЙ 6.1 Особенности постановки, классификация задач В классическом понимании методы поиска оптимальных решений, включающие в себя аналитические методы оптимизации и математическое программирование, связаны с поиском экстремумов целевых функций или функционалов при функциональных ограничениях на аргументы. Решением является математический возникающие на объект. практике При вопросы, этом не связанные рассматриваются с оценкой часто нескольких качественных критериев, и почему некий критерий можно считать приемлемым, а какой-то не принимать во внимание. При решении реальных проблем в условиях современного уровня сложности операций постановка задач рационального выбора часто характеризуется следующими особенностями: - многокритериальность; антагонистичность и неравнозначность частных критериев; - необходимость учета критериев, основанных на субъективных оценках; - необходимость одновременного учета неопределенностей различной природы. Во многих случаях дополнительной сложностью является иерархичность системы частных критериев. На практике объективно неизвестно, какое решение лучше, если критериев много, и они, возможно, являются конфликтующими (например, максимизация прибыли от продаж с одновременной минимизацией вложений в производство товаров). В этом случае выбор решения становится нетривиальной многокритериальной 140 задачей (МКЗ), связанной с многокритериальным выбором лица, принимающего решение (ЛПР). Этот раздел теории принятия решений называют многокритериальной, или векторной оптимизацией. В зависимости от того, в каком виде проявляется действие различных критериев, многокритериальные задачи могут быть подразделены на несколько классов: Класс 1 – множество качеств. При выборе решения принимаются во внимание несколько характеристик (качеств) системы. Обычно в задачах этого класса частные критерии имеют разную размерность и разную физическую природу. Класс 2 – множество объектов. Здесь система состоит из ряда объектов, качество функционирования каждого из которых описывается своим частным критерием, а эффективность системы определяется совокупностью частных критериев. Эта совокупность и есть векторный критерий оптимальности. Физическая природа и размерность частных критериев в задачах 2-го класса обычно одинаковы. Класс 3 – множество условий. Техническая система должна функционировать в различных условиях, причем для каждого варианта условий качество функционирования характеризуется некоторым частным критерием. Эффективность системы определяется при этом совокупностью величин критериев для каждого варианта условий. Частные критерии имеют в задачах этого класса одинаковую размерность и одинаковую природу. Класс 4 – множество этапов. Система функционирует в течение ряда этапов, как правило, временны̒х. Качество функционирования на каждом этапе характеризуется своим частными критерием. Эффективность системы зависит от этапов её функционирования и выражается векторным составляющими которого будут частные поэтапные критерии. 141 критерием, Класс 5 – множество вариантов постановки задачи. Например, качество функционирования системы зависит от значения некоторого дискретного параметра, для которого известна лишь область его возможного изменения и зависимость частных критериев от численного значения параметра. Если закон изменения этого параметра неизвестен, то эффективность системы будет характеризоваться векторным критерием, составляющими которого будут частные критерии для всех возможных значений неизвестного параметра. Размерность частных критериев в задачах такого класса одинакова. Считается, что наиболее полно специфику многокритериальных задач отражают задачи первого класса, для которых характерно, что составляющие вектора эффективности имеют разную физическую природу и разную размерность. В настоящее время известен ряд методов их решения, основанный на следующих принципах: – определение приоритетов или коэффициентов относительной важности частных критериев; – определение правил или приемов сведе̒ния всей совокупности показателей к единой шкале для случая, когда среди частных критериев встречаются и количественные, и качественные, а также разные по размерности показатели. В любом случае, первая проблема, возникающая при решении МКЗ, заключается в определении области изменения частных критериев, в которой находится оптимальное решение. Проще всего представить суть этой проблемы путем геометрической интерпретации. При этом придётся ограничиться только двухкритериальными задачами, но, как показывает практика, последующий переход к многокритериальному случаю не вызывает принципиальных трудностей. Предположим, что требуется оптимизировать систему, эффективность которой определяется двумя критериями k1 и k2. Будем считать, что эффективность возрастает как при увеличении k1, так и при увеличении k2. Оба критерия при этом 142 неотрицательны. Тогда на плоской системе координат с абсциссой k1 и ординатой k2 каждое решение будет отображаться точкой (k1i, k2i). Эффективность этого решения Эi есть некоторая функция от координат изображающей точки: Эi=f(k1i, k2i). Придать сколь угодно большие значения этим критериям мешают неизбежные в каждой реальной системе ограничения. Наиболее типичны два вида ограничений: физические (абсолютные), и взаимозависимые. Физическими называются такие ограничения величины критерия, которые не зависят от величины других критериев. Для системы, в которой два критерия k1 и k2 имеют только физические ограничения, область изменения частных критериев, или область возможных решений, будет ограничена двумя прямыми линиями на уровнях k1max и k2max, и осями координат (рис. 27а). Оптимальное решение в этом случае очевидно – его отображает точка М. Однако на практике такие системы встречаются крайне редко. Реальные системы имеют ограничения второго вида, проявляющиеся во взаимной зависимости частных критериев. Эта взаимная зависимость, в свою очередь, возникает из-за какого-то общего ограничительного требования. Например, если задан максимальный объем проектируемого космического корабля, то между высотой его подъема и массой поднимаемого оборудования немедленно появляется взаимосвязь. Таким образом, взаимосвязь возникнет и между названными выше частными критериями эффективности системы. В результате область возможных решений для двухкритериальной задачи уже будет иметь вид, показанный на рис.27б, где линия АВС обусловлена взаимной связью критериев. 143 Рис. 27. Подобластью области возможных решений является область допустимых решений. Она определяется такими минимальными значениями критериев k1min и k2min, при переходе через которые эффективность системы становится недопустимо малой, или равной нулю (рис. 27в). Если эффективность системы повышается как при увеличении критерия k1, так и при увеличении критерия k2, то оптимальное решение лежит на ограничительной линии. Можно утверждать, что оно лежит на части ограничительной линии, отмеченной точками на рис. 27г,д,е. Эту часть ограничительной линии называют областью компромисса, потому что именно здесь увеличения одного критерия можно достичь лишь ценой уменьшения другого. Следует заметить, что ограничительная линия вида, представленного на рис. 27г, на практике встречается редко. Наиболее типичный вид ограничительной линии представлен на рис. 27 д,е. Правильный выбор критериев играет существенную роль в определении оптимального решения. В теории принятия решений не установлено общего 144 метода выбора критериев оптимальности; в основном ЛПР руководствуются опытом или рекомендациями экспертов. Однако для любого класса систем существует определенный набор стандартных показателей качества, позволяющих оценивать конкретную систему с некоторых общих для данного класса точек зрения. Так для систем автоматического управления рассматриваются три группы показателей качества: точности, быстродействия и запаса устойчивости. Для систем массового обслуживания рассматриваются пропускная способность и вероятность отказа в обслуживании. Использование стандартных показателей качества полезно, а в процессе проектирования системы – необходимо, так как они тесно связаны не только с ее основными свойствами, но и с применяемым математическим аппаратом. Функционирование любой системы направлено на достижение конкретной цели или совокупности целей. Для оценки качества системы с точки зрения обеспечения цели функционирования или для выбора варианта построения системы, предоставляющего лучшие возможности достижения этой цели, стандартные показатели качества могут оказаться бесполезными. Для оценки соответствия системы ее назначению вводятся показатели эффективности функционирования системы, и можно сформулировать следующие требования к набору критериев, связанному с принятием решений, аналогичные требованиям, предъявляемым к этим показателям: 1. Прямая связь с целью функционирования системы и ясный физический смысл. 2. Чувствительность к изменению структуры и параметров системы. 3. Удобство вычисления, отображения и анализа. Стратегия поиска решения зависит от имеющейся информации о задаче и включает способ выбора вариантов (альтернатив), определяемый предпочтениями ЛПР, и метод (модель) оптимизации, обусловливающий способ совместного учета 145 критериев. Способ выбора альтернатив может предусматривать поиск наилучшего решения, удовлетворительного решения, наиболее предпочтительной альтернативы, недоминируемой альтернативы, возможной альтернативы, и т.п. Метод (модель) оптимизации включает такие подходы, как векторная оптимизация, оптимизация с учетом иерархии критериев, оптимизация с учетом неопределенности 6.2. Обзор методов решения многокритериальных задач 6.2.1. Оптимальность по Парето Ключевую роль в многокритериальной оптимизации играет понятие паретооптимального решения. Пусть Х обозначает множество допустимых решений в некоторой задаче, х Х – допустимое решение. Предположим, что каждое решение х Х оценивается по n критериям (n≥2), подлежащим максимизации. Решение х* X называют парето-оптимальным (оптимальным по Парето, эффективным, недоминируемым или неулучшаемым), если не существует другого возможного решения x X, такого, что ki(х) ki(х*) для всех i = 1, 2,...,n, причем по крайней мере для одного номера j (1, 2,..., n) имеет место строгое неравенство kj(х)>kj(х*). Если каждый критерий ki трактовать как функцию полезности i-го участника принятия решений в социальных и экономических системах, то к понятию паретооптимального решения приводит воплощение идеи социальной справедливости, состоящей в том, что для коллектива всех участников более выгодным будет только то решение, которое не ущемляет интересы ни одного из них в отдельности. При этом при переходе от одного парето-оптимального решения к другому если и происходит улучшение (увеличение) одного из критериев, то обязательно это улучшение будет сопровождаться ухудшением (уменьшением) какого-то другого критерия (или сразу нескольких критериев). Таким образом, 146 переход от одного парето-оптимального решения к другому невозможен без определенного компромисса. Другими словами, парето-оптимальное решение не может быть улучшено ни по какому критерию (ни по какой группе критериев) при условии сохранения значений по всем остальным критериям. Множество всех парето-оптимальных решений часто обозначают Pk(X) и называют множеством Парето (множеством Эджворта-Парето) или областью компромиссов. В частном случае, когда критерий всего один, т.е. n = 1, определение парето-оптимального решения превращается в определение точки максимума функции k=k1 на множестве X. Это означает, что парето-оптимальное решение представляет собой обобщение обычной точки максимума числовой функции. Если требуется получить максимально возможные значения по всем имеющимся критериям, то из пары произвольных решений то из них, которое не является в этой паре парето-оптимальным, никогда выбирать не следует. Так как решения, которые не выбираются из пары, разумно не выбирать и из всего множества возможных решений, то в итоге приходим к так называемому принципу Парето (принципу Эджворта-Парето), в соответствии с которым выбирать (наилучшие) решения следует только среди парето-оптимальных. Существуют два основных метода нахождения множества Парето. 1. Метод обхода конусом. Этот метод применяется для непрерывной области значений критериев. Конус образуется как пространственный угол, ограниченный на плоскости любыми двумя лучами-критериями k1 и k2, идущими под углом 90о. Направление лучей k1 и k2, ограничивающих пространственный конус, соответствует направлению оптимизации этих критериев. На рисунке 28 показан такой конус для k1→max и k2→min. Для получения множества Парето достаточно установить вершину конуса на все точки границы области критериев, как на рисунке 29. Если при этом ни один луч не пересекает область, то вершина лежит в точке Парето. Если хотя бы один луч пересекает область множества 147 вариантов критериев – то вершина в точке Парето не лежит. Метод обхода конусом для k1→min и k2→min дает на рис. 29 множество Парето [AB]U[CD]. Рис. 29. Рис. 28. 2. Метод прямоугольников. Метод применяют для дискретной области значений критериев. Пусть возможным сочетаниям значений двух критериев соответствуют точки на плоскости (рис. 30). Тогда k1→min и k2→min обеспечивается следующим алгоритмом: 1. Выбрать точку по условию k1→min. Если их несколько, оставить одну по условию k2→min. Эта точка является точкой Парето, обозначим её цифрой 1. 2. Выбрать точку по условию k2→min. Если их несколько, оставить одну по условию k1→min. Это – точка Парето, обозначим её Рис. 30. цифрой 2. 3. Через точки 1 и 2 провести вертикали и горизонтали, которые образуют прямоугольник. 4. Исключить из рассмотрения найденные точки Парето, точки, лежащие на границе полученного прямоугольника и все точки вне прямоугольника. 148 5. Повторять пп. 1-4 до тех пор, пока внутри прямоугольника не останется ни одной точки. Множество Парето включит в себя найденные в пп. 1 и 2 точки: {1, 2, 3, 4, 5, 6}. Этот алгоритм легко распространяется на бо́льшее число критериев, а также удобен в случае табличного задания значений критериев. Пример 29. Проведем сравнительный анализ пяти моделей автомобиля на основе их суммарных оценок группой экспертов по семи критериям (таблица 59). Для каждого из семи критериев требуется обеспечить максимум. Таблица 59. Критерий Модель 1 Модель 2 Модель 3 Модель 4 Модель 5 дизайн 75 105 130 120 105 интерьер 35 50 65 60 55 эргономика 100 120 125 125 130 динамика 205 220 205 205 210 управляемость 65 75 80 85 70 плавность 55 65 60 60 60 45 55 45 45 40 хода багажник Табличные значения, составляющие множество Парето, полученное методом прямоугольников, выделены заливкой. Выбор любой модели, кроме первой, будет решением, оптимальным по Парето. Достоинствами оптимального по Парето решения являются гарантия его наличия и сравнительная простота получения в практических задачах. Однако понятие парето-оптимального решения не подразумевает его единственности, чаще всего можно получить лишь множество эффективных решений. Если количество точек во множестве Парето n≥2, остается вопрос о нахождении единственного решения. Объективно предпочесть какую-либо точку на множестве 149 Парето невозможно, т.к. эти точки обладают таким свойством, что каждая из них лучше по одному критерию, но хуже по другому. Поэтому для нахождения наилучшего решения приходится вводить некоторые дополнительные условия или приходится выбирать, какому критерию отдать предпочтение. 6.2.2. Арбитражные решения Пусть есть n критериев для оценки парето-оптимальных альтернатив. Каждый из критериев может быть оценён количественно (возможно, как физическая величина, возможно, по некоей шкале баллов). Идея арбитражных решений состоит в том, чтобы для решения многокритериальной задачи построить некий интегральный критерий, позволяющий выбирать наилучшую альтернативу, рассматривая не n критериев, а один – K(x). Этот критерий определяет некоторый компромисс между заданными критериями, и выбранная альтернатива будет оптимальна только в смысле этого интегрального критерия. Роль этого критерия – поставить в соответствие каждой альтернативе только одно число, или исходную точку. Рассмотрим критерием задачу многокритериальной оптимизации с векторным K(х)=(k1(х),…, ki(x), …, kn(x)), где x X – область или множество допустимых решений. Пусть х0 Х – исходная точка, т.е. некоторое допустимое решение, выбранное из каких-либо соображений в качестве начального приближения к оптимальному и подлежащее улучшению при решении задачи. Метод главного критерия. Рассмотрим задачу многокритериальной оптимизации и некоторую исходную точку х0, в которой K(х0)=(K1(х0),…, Ki(x0), …, Kn(x0)). Выберем в качестве главного, например, критерий k1. Найдем max k1 ( x) для ki(x)≥ki(x0), xX i  2, n . Вектор х* Х, который доставляет такой экстремум, называется оптимальным решением по методу главного критерия при исходной точке K(х0). 150 Таким образом, задача сводится к задаче математического программирования, в качестве целевой функции выбирается главный критерий, а остальные используются в качестве ограничений. Например, в промышленности можно потребовать, чтобы прибыль была максимальной, план по ассортименту выполнен, а себестоимость производства изделий – не выше заданной. Арбитражная схема Нэша Для задачи многокритериальной оптимизации K(х)=(k1(х),…, ki(x), …, kn(x)), x X вводится в рассмотрение функция Нэша (или произведение Нэша) n K ( x)   (ki ( x)  ki ( x0 )) . Находится max K N ( x) при условиях ki(x)≥ki(x0), i  1, n . N i 1 x X Вектор х* Х, который доставляет такой экстремум, называется арбитражным решением Нэша при исходной точке K(х0), Ему соответствует KN(x*) – оценка для арбитражного решения Нэша. К достоинствам арбитражных решений можно отнести простоту и скорость принятия решения. Недостатки: 1. Не всегда можно выделить ярко выраженный главный критерий, иногда это сделать трудно или вообще нельзя. 2. Ограничения для остальных критериев требуют обоснования. 3. Даже если есть критерий ki, который гораздо важнее любого другого, то не факт, что остальные критерии в сумме не окажутся столь же значимыми. Особо ярко это может проявляться в задачах, где n велико. 4. Если задача имеет некоторое множество решений, то это множество может содержать в себе парето-оптимальные решения, но также может содержать решения, не являющиеся парето-оптимальными. Это можно иллюстрировать рисунком 31. На рисунке 31 весь многоугольник ABCD представляет собой множество альтернатив. Отрезок СЕ – множество решений по методу главного критерия, 151 когда в качестве главного принят критерий К1. Однако только альтернатива С является вариантом, оптимальным по Парето. Чтобы это было явно видно, требуется скорректировать метод главного критерия, и ввести корректировочную величину ξ, на несколько порядков меньшую значений критериев. Тем самым направление оптимизации немного поворачивается вверх на величину ξ, как на рисунке 32. Таким образом, для метода главного критерия задача преобразуется n как max (k1 ( x)   ki ( x)) для ki(x)≥ki(x0), i  2, n , а для арбитражной схемы Нэша x X i 1 n – как max ( K ( x)   ki ( x)) при условиях ki(x)≥ki(x0), i  1, n . N x X i 1 K2 K1→max,K2≥2 K2 K1→max,K2≥2 C C E 2 D D B 1 E 2 B 1 A Повернутое направление Исходное направление оптимизации A K1 K1 Рис. 32. Рис. 31. 6.2.3. Целевое программирование В основе методов целевого программирования для решения многокритериальных задач лежит упорядочение критериев по степени важности. Исходная задача решается путем последовательного решения ряда задач с одной целевой функцией таким образом, что решение задачи с менее важной целью не может ухудшить оптимального значения целевой функции с более высоким приоритетом. Методы целевого программирования дают эффективное решение, которое пытается учесть все частные целевые функции, но может не включать их 152 оптимальные значения. Этим оно отличается от линейного программирования, в котором получают оптимальное решение для одной целевой функции. Тем не менее, в результате применения методов целевого программирования для решения многокритериальных задач сужается парето-оптимальное множество альтернатив и получается приемлемое решение рассматриваемой задачи. Простейшим методом целевого программирования является метод рейтинга приоритетов. Реализация метода рейтинга приоритетов проводится в следующем порядке: – определяются критерии, по которым оцениваются альтернативы; – определяется сравнительная важность критериев в весах, общая сумма весов равна единице; – альтернативным решениям присваивается оценка, они оцениваются по шкале от 1 (наихудшее) до 10 (наилучшее) по каждому критерию; – подсчитывается рейтинг приоритетов для рассматриваемых альтернатив путем суммирования произведений значений каждого критерия для альтернативы на весовой коэффициент этого критерия. Альтернатива с наивысшим рейтингом будет приоритетной и может быть выбрана в качестве решения. Используем данные примера 29, исключив модель 1, как не вошедшую в парето-оптимальное множество. Далее примем, что при принятии решения управляемости присваивается весовой коэффициент, например, 0,22 (22% общего веса), динамике – 0,18 (18%), плавности хода – 0,16 (16%), эргономике 0,12 (12% от общего веса), дизайну и интерьеру – по 0,11 (по 11%) и характеристикам багажника – 0,1 (10%). На основе таблицы 59 оценим по шкале от 1 до 10 каждую модель автомобиля по указанным критериям. Подсчитаем рейтинг приоритетов путем суммирования произведений значения каждого критерия на его весовой коэффициент. Для удобства критерии 153 расположены по убыванию их весового коэффициента. Результаты представлены в таблице 60. 154 Таблица 60 Критерий Вес Оценки альтернатив критерия Модель 2 Модель 3 Модель 4 Модель 5 управляемость 0,22 7 8 10 6 динамика 0,18 10 6 6 8 хода 0,16 10 9 9 9 эргономика 0,12 6 8 8 10 дизайн 0,11 5 10 8 5 интерьер 0,11 4 10 8 6 багажник 0,1 Рейтинг 10 6 6 4 СУММА 1 (100%) приоритетов: 7,65 8,4 8,4 6,65 плавность Наибольший рейтинг набрали модели 3 и 4, выбор следует делать именно из них. Однако сужать парето-оптимальное множество до выбранных двух моделей не стоит – разброс в 1-2 балла в рейтинге не слишком велик, кроме того, ни одна альтернатива не получила минимальную оценку (менее 3 по выбранной шкале). Метод рейтинга приоритетов прост в использовании, однако при его применении на практике возникает ряд сложностей при выборе оценочных шкал для разнородных критериев, при выставлении оценок альтернативам и оценке весов критериев. Задачу сравнения альтернатив можно упростить, приведя показатели к безразмерному (нормированному) виду. Если часть показателей приведена в качественном виде, можно воспользоваться шкалой Харрингтона, представленной в таблице 61. 155 Таблица 61 №№ Содержательное описание градаций Числовое значение 1. Очень высокая 0,8-1,0 2. Высокая 0,64-0,8 3. Средняя 0,37-0,64 4. Низкая 0,2-0,37 5. Очень низкая 0,0-0,2 пп Нормализация критериев представляет собой процедуру приведения частных критериев к единому безразмерному масштабу измерения одним из существующих способов. Большинство применяемых способов нормализации основывается на введении понятия идеального решения, обеспечивающего максимум всем компонентам векторного критерия KИ(x). С помощью KИ(x)=( kimax ) вектор критериев K(x) приводится к безразмерной форме: yi  ki kimax , где каждая компонента yi принадлежит диапазону [0; 1]. В зависимости от различных способов выбора идеальных значений, могут быть использованы различные способы нормализации. Способ первый: kimax  kiзад – заданная при постановке задачи принятия решения величина, соответствующая априорным представлениям о располагаемых возможностях обеспечения эффективности системы. Такой подход может быть применен на начальных стадиях проектирования при выработке общей концепции системы, составлении технического задания. Недостатком нормирования к заданным значениям критериев является предположение о том, что авторы технического задания уже нашли оптимальное решение. В то же время в процессе проектирования некоторые из таких заданных 156 значений могут быть превышены. Тогда в зависимости от величины yi  ki kiзад можно сделать следующие выводы: – yi <1 – решение неприемлемо, т.к. не обеспечит заданных требований; – yi =1 – решение обещает получить величину критерия ki именно той величины, которая задана; – yi>1 – требования технического задания превзойдены, можно ожидать, что найдено оптимальное решение. Способ второй – нормирование к максимуму, предусматривающий использование в качестве kimax глобальных максимумов критериев ki. На практике его не всегда признают удобным в случаях большого разброса значений максимумов отдельных критериев. В некоторой степени сгладить названную проблему может третий способ. Для каждого критерия по всем рассматриваемым альтернативам определяются минимум kimin и максимум kimax . Нормированное значение для варианта, когда оптимальное значение критерия соответствует наибольшему значению, будет определяться по формуле yli  kli  kimin kimax  kimin , а для варианта, когда оптимальное значение критерия соответствует минимальному значению – yli  kimax  kli kimax  kimin . Здесь kli – исходное значение i-го критерия для l-той альтернативы. На нормализации критериев основан еще один метод целевого программирования – метод весовых коэффициентов. Обозначим через ωi положительные весовые коэффициенты, которые отражают предпочтения, отдаваемые экспертами каждому критерию, i=1,2,…,п. В методе весовых коэффициентов единая целевая функция (ЕЦФ) для каждой 157 альтернативы формализуется как взвешенная сумма исходных частных целевых функций: n Ln   i yl i , i 1 где весовые коэффициенты, или коэффициенты относительной важности критериев, вводятся в соответствии с условиями нормировки: 0 ≤ωi≤ 1, i = 1, 2, ..., n nи  i  1. Затем из полученного ряда выбирается оптимальная Ln. i 1 Коэффициенты относительной важности критериев обычно определяются методом экспертных оценок в три этапа: - определение приоритетов критериев по какой-либо шкале (10-балльная, 5балльная или др.); - формирование вектора приоритетов показателей решения, элементами которого являются экспертные значения в баллах по принятой шкале; - нормирование вектора приоритетов. Рассмотрим два из возможных способов определения вектора приоритетов. 1. Способ одного эксперта: – составляется перечень показателей, для которых необходимо определить весовые коэффициенты; – выбирается подходящая шкала и для каждого показателя вводится значение Оi, i = 1, 2,…, n; по этой шкале в количественной или качественной форме, соответствующей суждению эксперта относительно приоритетности этого показателя; – если суждения качественные, то осуществляется перевод количественную форму, например по шкале Харрингтона (таблица 61); 158 в – суммируются все значения показателей, и для определения коэффициента относительной важности i-го показателя каждую оценку Оi делят на сумму, т. е. i  Oi n  Oi . i 1 Для получения приоритетного ряда рекомендуется расположить показатели по убыванию коэффициентов относительной важности. 2. Групповая экспертиза: При принятии важного решения, как правило, возникают разногласия. Одним из наиболее распространенных и простых приемов их устранения является усреднение результатов, полученных разными экспертами в группе. Каждым экспертом должна быть выполнена процедура по первому способу. Значения коэффициентов важности, полученные каждым экспертом, нужно сложить и разделить на число экспертов. Вернемся к примеру 29, исключив здесь и ниже из рассмотрения модель 1, как не входящую в парето-оптимальное множество, и одновременно введем субъективные приоритеты для рассматриваемых показателей по произвольной вербально-числовой шкале от 1 до 7 по числу критериев. (таблица 62). Таблица 62. Наименование Модель 2 Модель 3 Модель 4 Модель 5 Приоритет дизайн 105 130 120 105 3 интерьер 50 65 60 55 2 эргономика 120 125 125 130 4 динамика 220 205 205 210 5 управляемость 75 80 85 70 7 плавность хода 65 60 60 60 6 багажник 55 45 45 40 1 критерия 159 Оптимальное значение критерия соответствует наибольшему показателю, следовательно, для расчетов нормированных значений критериев использована формула yli  будет kli  kimin kimax  kimin . Коэффициенты важности критериев (вектор приоритетов) получаются нормированием приоритетов путем деления каждого конкретного балла на их общую сумму. Для получения приоритетного ряда показатели расположены по убыванию коэффициента важности. Расчеты приведены в таблице 63. Таблица 63 Наименование Коэффициенты критерия относительной Нормированные критерии, yli Модель 2 Модель 3 Модель 4 Модель 5 важности, ωi управляемость 0,25 0,33 0,67 1 плавность хода 0,21 1 динамика 0,18 1 0,33 0,33 эргономика 0,14 0,5 0,5 1 дизайн 0,11 1 0,6 интерьер 0,07 1 0,67 0,33 багажник 0,04 1 0,33 0,33 0,43 0,45 0,22 ЕЦФ для n альтернатив, Lj: 0,51 Исходя из субъективной расстановки приоритетов, максимальный обобщенный показатель (ЕЦФ) оказался у автомобиля модели 2, выбрать следует именно его. По сравнению с результатами, которые дал метод рейтинга приоритетов, в парето-оптимальное множество также входят модели 3 и 4. А вот величина ЕЦФ для модели 5 оказалась слишком мала. Окончательный выбор можно произвести, привлекая дополнительные критерии, например, добавив к параметрам выбора стоимость. Оптимальное 160 значение стоимости будет соответствовать наименьшему показателю, и будет рассчитываться по формуле yli  k imax  k li k imax  k imin . ЕЦФ для каждой альтернативы получены путем сложения, поэтому такой показатель называют аддитивным. Это формальный математический приём, придающий задаче удобный для решения вид. При применении аддитивного показателя может происходить взаимная компенсация частных критериев. Это значит, что значительное уменьшение одного из них вплоть до нуля может быть покрыто возрастанием другого критерия. С практической точки зрения это не всегда приемлемо. Например, очевидно, что ухудшение вместимости багажника автомобиля не может быть компенсировано увеличением оценки интерьера. Метод анализа иерархий (МАИ) разработан Т. Саати в 80-х годах прошлого века. Он основан на идее использования взвешенных средних оценок критериев каждой альтернативы, однако в нем применяется более надежный и согласованный метод присвоения оценок и весовых коэффициентов, основанный на попарном сравнении альтернативных решений по каждому критерию. Затем проводится ряд аналогичных сравнений для оценивания относительной важности каждого критерия, чтобы таким образом определить их весовые коэффициенты. Основная процедура выглядит так. 1. Определяются оценки всех альтернатив по каждому критерию следующим образом: – создается матрица попарных сравнений по всем критериям, – полученная матрица нормализуется, – для получения весовых коэффициентов всех альтернатив по каждому критерию усредняются значения в каждой строке, – вычисляются и проверяются коэффициенты согласованности. 2. Определяются весовые коэффициенты самих критериев: – создается матрица попарных сравнений по всем критериям, 161 – полученная матрица нормализуется, – для получения весовых коэффициентов критериев усредняются значения в каждой строке, – вычисляются и проверяются коэффициенты согласованности. 3. Вычисляется взвешенный средний рейтинг для каждого варианта решения и выбирается решение, набравшее наибольшее количество баллов. Вернемся к примеру 29. Первый шаг процедуры МАИ состоит в попарном сравнении альтернатив по каждому критерию. В качестве шкалы сравнения можно выбрать приведенную выше шкалу Харрингтона, или любую другую простую и удобную шкалу. Используем стандартную шкалу сравнения, приведенную в таблице 64. Таблица 64 Оценка Описание 1 Одинаковое предпочтение 3 Умеренное предпочтение 5 Явное предпочтение 7 Очевидное предпочтение 9 Исключительное предпочтение Дополнительно можно присваивать оценки 2, 4, 6 и 8, которые определяются как средние от ближайших оценок. Результаты попарного сравнения альтернатив по критерию "динамика" представлены в таблице 65. Таблица 65 Динамика Модель 2 Модель 3 Модель 4 Модель 5 Модель 2 1 9 9 5 Модель 3 1/9 1 1 1/7 Модель 4 1/9 1 1 1/7 Модель 5 1/5 7 7 1 авто 162 Механизм заполнения таблицы следующий. Таблица всегда квадратная – по горизонтали и вертикали идут названия альтернатив. В главную диагональ вносятся единицы. Далее сравниваются показатели критерия "динамика" у первой пары по строкам. Это модель 2 и модель 3. Если обратиться к примеру 29, значение этого критерия у модели 2 – 220, у модели 3 – 210. Если представить шкалу из таблицы 64 горизонтально, получится следующее: Модель 2 9_7_5_3_1_3_5_7_9 Модель 3 Эксперт рассуждает следующим образом: По критерию "динамика" у модели 2 явное предпочтение перед моделью 3, поэтому нужно отметить 9 на шкале ближе к модели 2. Модель 3 таким образом получает оценку, обратную выставленной модели 2 в соответствующей ячейке таблицы, а именно 1/9. Динамика модели 4 имеет то же значение, что и у модели 3 – соответствующие оценки одинаковы. Рекомендуется сначала заполнить правый верхний или левый нижний угол таблицы до главной диагонали, а оставшуюся часть таблицы заполнить числами, обратными к симметричным относительно главной диагонали. В целом таблица заполняется по следующим правилам: • Если оценка альтернативы находится в левой части шкалы, то в соответствующий элемент матрицы сравнений помещаем ее значение. • Если оценка альтернативы находится в правой части шкалы, то в соответствующий элемент матрицы сравнений помещаем величину, обратную этой оценке. Подобным образом рассчитываются таблицы попарных сравнений по всем альтернативам. Проще всего подобные расчеты вести в среде электронных таблиц, поэтому далее в расчетных таблицах будут представлены не натуральные, а десятичные дроби. 163 Полученные таблицы необходимо нормализовать. Делается это следующему алгоритму. – В отдельной строке подсчитывается сумма всех полученных оценок альтернатив (таблица 66). 164 по Таблица 66 Динамика Модель 2 Модель 3 Модель 4 Модель 5 автомобиля Модель 2 1 9 9 5 Модель 3 0,11 1 1 0,14 Модель 4 0,11 1 1 0,14 Модель 5 0,2 7 7 1 1,42 18 18 6,29 Сумма оценок – Каждый элемент столбца делится на полученную для этого столбца сумму. Результаты операции представлены в таблице 67. Таблица 67 Динамика авто Модель 2 Модель 3 Модель 4 Модель 5 Среднее значение Модель 2 0,7 0,5 0,5 0,8 0,62 Модель 3 0,08 0,06 0,06 0,02 0,05 Модель 4 0,08 0,06 0,06 0,02 0,05 Модель 5 0,14 0,39 0,39 0,16 0,27 Следующий шаг состоит в вычислении весовых коэффициентов всех альтернатив по рассматриваемому критерию путем вычисления среднего значения по каждой строке. Вычисления представлены в таблице 67 в крайнем правом столбце. Этот столбец представляет собой также вектор приоритетов по критерию "динамика", показывающий относительные веса объектов, которые мы сравниваем. Максимальное количество баллов по критерию динамики автомобиля получают модель 2 и модель 5. Далее необходимо вычислить коэффициент согласованности и проверить его значение. Цель этой операции состоит в том, чтобы убедиться в согласованности задания предпочтений, или согласованности суждений, в исходной таблице. Понятие согласованности суждений близко по смыслу к свойству транзитивности. Например, если бы по критерию динамики была задана 165 явная предпочтительность модели 4 перед моделью 5 и умеренная предпочтительность модели 4 перед моделью 2, то при сравнении модели 2 и модели 5 задание одинаковой предпочтительности приведет к несогласованности, еще большая несогласованность возникнет при указании, что модель 3 предпочтительнее модели 2. Вычисление коэффициента согласованности состоит из трех этапов. 1. Вычисляется мера согласованности для каждой модели. Для вычисления меры согласованности средняя оценка каждой альтернативы умножается на соответствующее количество баллов в первой строке, эти произведения суммируются, и сумма делится на среднюю оценку первой альтернативы. 2. Вычисляется среднее значение меры согласованности S. 3. Определяется индекс согласованности ИС по формуле (S-N)/(N-1), где S – среднее значение меры согласованности, N – количество рассматриваемых альтернатив. 4. Выбирается индекс рандомизации ИР, вычисленный Саати, и представленный в таблице 68. Таблица 68 № ИР 1 2 3 0,58 4 0,9 5 6 7 8 9 10 1,12 1,24 1,32 1,41 1,45 1,49 5. Вычисляется коэффициент согласованности как отношение ИС/ИР (таблица 69). 166 Таблица 69 Мера согласованности Модель 2 4,63 Модель 3 4,15 Модель 4 4,15 Модель 5 4,05 S 4,24 ИС 0,08 ИР(4) 0,9 ИС/ИР 0,08 В идеальном случае меры согласованности должны быть равны числу возможных альтернативных решений (в нашем примере 4). В этом случае идеальный коэффициент согласованности (ИС/ИР) равен нулю. Если коэффициент согласованности слишком велик (больше 0,10 по оценке Саати), значит, эксперты были недостаточно последовательны в своих оценках, поэтому следует вернуться назад и пересмотреть результаты попарных сравнений (в большинстве случаев обнаруживается элементарная ошибка). Аналогично соответствующие поступаем таблицы с другими попарных альтернативами, сравнений и заполняя вычисляя меры согласованности. Теперь необходимо проделать тот же самый процесс вычислений для всех критериев, чтобы убедиться в том, что эксперты были достаточно последовательны в своих оценках. Процесс аналогичен предыдущему, но попарно сравниваются не варианты, а критерии. Последний шаг состоит в вычислении взвешенных средних оценок для каждого варианта решения и применении полученных результатов для принятия решения о том, какой автомобиль следует выбрать. Взвешенные средние оценки 167 для всех весов альтернатив вычисляются как сумма произведений взвешенных средних оценок для каждой альтернативы на веса критериев. Результаты расчетов для всех альтернатив по методу анализа иерархий приведены в таблице 70. Таблица 70 Взвешенные средние оценки для каждой альтернативы Веса Критерии критериев Модель 2 Модель 3 Модель 4 Модель 5 Управляемость 0,46 0,13 0,29 0,48 0,09 Динамика 0,33 0,62 0,05 0,05 0,27 Плавность 0,26 0,7 0,1 0,1 0,1 Эргономика 0,14 0,11 0,35 0,35 0,19 Дизайн 0,08 0,06 0,46 0,4 0,07 Интерьер 0,06 0,09 0,51 0,25 0,14 Багажник 0,03 0,7 0,07 0,07 0,16 0,49 0,29 0,36 0,2 Взвешенные средние рейтинги: По методу анализа иерархий выбору подлежит автомобиль модели 2. Метод анализа иерархий представляет собой достаточно эффективную процедуру для нахождения весовых коэффициентов. Однако входящий в его состав критерий отбора экспертов, по меньшей мере, нуждается в подключении дополнительных процедур с соответствующими алгоритмами, требующими специального изучения. Кроме того, остается вопрос о выборе шкалы для экспертного оценивания частных критериев. 6.3. Применение алгебры нечетких множеств Ситуации, которые могут быть неточно охарактеризованы, могут быть рассмотрены при помощи метода нечетких (размытых) множеств. Эта концепция была предложена Л. Заде в середине 1960-х г.г., и с тех пор с использованием 168 аппарата теории нечетких множеств выполнено значительное количество исследований и опробовано много применений. Методы нечетких множеств исходят из тех соображений, что креативное человеческое мышление протекает в рамках нечетких, строго не определенных понятий. Человеческому мышлению не могут полностью соответствовать модели классической математики с однозначной двухпозиционной логикой. Поэтому в методах нечетких множеств (НМ) стараются применять математические подходы и математическую символику в совокупности с нечеткостью оценок и решений, принимая эту нечеткость как важнейшее отражение ситуации, существующей в действительности. Это позволяет связать точное знание с неопределенностью и многозначностью ситуации, включая эмоциональное восприятие окружающего мира. Успешное решение поставленной таким образом задачи позволяет ввести и рационально использовать такие понятия, как нечеткие закономерности, соотношения, алгоритмы. Можно выделить следующие основные классификационные признаки способов формализации нечеткости: 1) по виду представления нечеткой субъективной оценки величины (нечеткого множества); 2) по виду области значений функции принадлежности; 3) по виду области определения функций принадлежности; 4) по виду соответствия между областью определения и областью значений (однозначное, многозначное); 5) по признаку однородности или неоднородности области значений функции принадлежности. Учет фактора неопределенности при решении задач во многом изменяет методы принятия решения: меняется принцип представления исходных данных и параметров модели, становятся неоднозначными понятия решения задачи и оптимальности решения. Наличие неопределенности может быть учтено 169 непосредственно в моделях соответствующего типа с представлением недетерминированных параметров как случайных величин с известными вероятностными характеристиками, в виде нечетких величин с заданными функциями принадлежности или интервальных величин с фиксированными интервалами изменения. Решение задачи осуществляется соответственно с помощью методов стохастического, нечеткого или интервального программирования. В целом алгоритмы на базе методов нечетких множеств хорошо зарекомендовали себя на практике при решении самого разнообразного круга задач. Успешным является и применение теории нечетких множеств в стохастических системах. Это связано с тем, что для многих систем трудно получить точные значения вероятностных характеристик (например, вероятности отказов компонентов). Преимущества методов нечеткой логики по сравнению с другими состоят в возможности: – оперировать в анализе качественными переменными как для входных данных, так и для получаемых выходных данных (результатов); – оперировать нечеткими входными данными, например, непрерывно изменяющимися во времени значениями (динамические задачи), значениями, которые невозможно задать однозначно (результаты статистических опросов, рекламные компании и т.д.); – оперировать лингвистическими критериями, обеспечивающими возможность нечеткой формализации критериев оценки и сравнения (критериями «большинство/меньшинство», «возможно», "примерно", «преимущественно» и т.д.); - быстро моделировать сложные динамические системы и сравнивать их с заданной степенью точности; 170 - преодолевать недостатки и ограничения существующих методов оценки проектных рисков. Таким образом, оценивание поведения системы методами нечеткой логики, во-первых, позволяет не тратить много времени на выяснение точных значений переменных и строгую формализацию задачи, во-вторых, позволяет оценить разные варианты выходных значений. Первоочередная задача теории нечетких множеств - дать "размытое" определение принадлежности некоторого элемента или объекта множеству. Пусть Е – некое множество, А – подмножество E: АE. В классической математике принадлежность некоторого элемента хЕ к подмножеству А однозначно описывается индикаторной функцией lА: 1 при x  A; I A x    0 при x  A. В терминах теории нечетких множеств к концепции нечеткой принадлежности приходят с помощью характеристической функции хμА(х), xЕ. Такая характеристическая функция (ХФ) может принимать большее число значений, в отличие от двузначной ситуации. Тогда нечеткое подмножество А множества Е будет определяться множеством упорядоченных пар: A  ( x, μ A ( x)) x  E. Нормальной называют характеристическую функцию, с диапазоном возможных значений [0; 1]. Принадлежность некоторого элемента хЕ к нечеткому подмножеству А можно теперь в количественной или взвешенной форме символически выразить, например, следующим образом: – x  A означает «х определенно принадлежит А»; 1 – x A означает «х определенно не принадлежит А»; 171 – x  A означает «принадлежность x множеству А определяется степенью 0,8 0,8». Два нечетких множества А и В называются равными, если для всех хЕ имеет место равенство значений ХФ:  A ( x)   B ( x) . В соответствии с положениями теории множеств говорят, что НМ А содержится в НМ В, если для всех хЕ справедливо соотношение  A ( x)   B ( x) Важное положение «нечеткого» анализа состоит в определении связей НМ, аналогичных соответствующим соотношениям алгебры множеств. Связи между НМ, или действия над ними, можно охарактеризовать заданием соответствующих ХФ и определить следующим образом: – пересечение С=А∩В, С ( x)  min(  A ( x),  B ( x)) ; – прямое произведение С=АВ, С ( x)   A ( x)   B ( x) ; – объединение С=АUВ,; С ( x)  max(  A ( x),  B ( x)) ; – алгебраическая сумма С=А  В, С ( x)   A ( x)   B ( x)   A ( x)   B ( x)) ; – дополнение С  А , С ( x)  1   A ( x) . Таким образом, с нечеткими множествами можно оперировать так же, как и с обычными. Кроме того, над нечеткими множествами возможны дополнительные операции, соответствующие логике человеческого мышления и позволяющие оперировать нечеткими (лингвистические) переменными, например: - концентрация (операция «очень»), С ( x)   A ( x) 2 ; - размывание (операция «не очень»), С ( x)  A ( x) . Примеры введения лингвистических переменных (с учетом разнообразия взглядов на описываемые ими интуитивные понятия): - лингвистическая переменная, описывающая понятие «несколько», может быть задана характеристической функцией в табличной форме (таблица 71). 172 Таблица 71 x 1 2 3 4 5 6 7 8 9 10 μА(х) 0,1 0,5 0,9 1 1 0,9 0,6 0,3 - на рис. 33 графически представлены возможные характеристические функции для лингвистических переменных «высокий человек» - 1, «очень высокий человек» - 2. Рис. 33. Применение нечеткого анализа для принятия решений может быть проиллюстрировано следующими примерами [2]. Пусть для ситуации, в которой нужно принять решение, имеются: 1. Множество вариантов решения Е. 2. Ограничивающие дополнительные условия. 3. Одна или несколько целевых функций. Факторы 2 и 3 могут при этом быть нечеткими, т.е. определяться через НМ и ХФ. 173 Пример 30. Требуется подобрать вещественное число, значительно большее 10, но как можно ближе к 11 (считается первым опубликованным примером нечеткого анализа, опубликованным Л. Заде). 1. E=R+, т.е. в качестве вариантов решения выступают все вещественные неотрицательные числа. 2. Нечеткое множество B чисел, характеристической функцией x   В ( x)  близких 1 1   x  114 к 11, можно задать . 3. НМ Z чисел, значительно больших 10, можно задать ХФ 0, x  10,   2 x   Z ( x)  x  10  , x  10. 1   x  10 2  На рис. 34 показан вид ХФ μВ и μZ. Множество решений, удовлетворяющих требованиям задачи, получаем путем образования пересечения: μ С(х)=min(μВ(x), μZ(x)). Это множество соответствует заштрихованной области. Наилучшее решение x* соответствует максимуму ХФ μС(х). Рис. 34. Решим задачу выбора автомобиля из примера 29 с применением алгебры нечетких множеств. Пусть дано множество Е={1, 2, 3, 4} вариантов решения (n=4 174 альтернатив) и набор критериев ki, i=(1, 2, …, 7) одинаковой важности. Тогда для каждого критерия ki может быть рассмотрено нечеткое множество K i с дискретной ХФ μ i ={μ i (E 1 ), μ i (E 2 ), μ i (E 3 ), μ i (E 4 )}, где μ i (E j ) – оценка альтернативы Ej по критерию ki характеризующая степень соответствия альтернативы понятию, определяемому критерием ki. Множество решений, удовлетворяющим условиям выбора, должно получиться путем образования пересечения соответствующих нечетких множеств Ki. В качестве лучшей альтернативы выбирается доставляющая максимум ХФ полученного множества решений. Используем оценки альтернатив Ej по критериям ki, полученные методом анализа иерархий (таблица 70). Последняя строчка этой таблицы содержит      значения характеристической функции множества решений С E j  min i E j i (таблица 72). Таблица 72 Значения ХФ μ i (Ej), i=1,2,…,7 Критерии Е1 – модель 2 Е2 – модель 3 Е3 – модель 4 Е4 – модель 5 k1 – управляемость 0,13 0,29 0,48 0,09 k2 – динамика 0,62 0,05 0,05 0,27 k3 – плавность 0,7 0,1 0,1 0,1 k4 – эргономика 0,11 0,35 0,35 0,19 k5 – дизайн 0,06 0,46 0,4 0,07 k6 – интерьер 0,09 0,51 0,25 0,14 k7 – багажник 0,7 0,07 0,07 0,16 0,06 0,05 0,05 0,07 μС(Ej) Оптимальный вариант E* получается из требования С ( E*)  max С , что xE соответствует автомобилю модели 5. 175 Рассмотренный спектр методов решения многокритериальных задач демонстрирует различные подходы к формированию рекомендуемого решения. В первую очередь ЛПР должно из всех возможных альтернатив выделить паретооптимальное множество. Арбитражные методы помогут ЛПР найти решение в случае, если область принятия решения лежит в промышленной, технической сферах, а количество критериев невелико и из них легко выделяется главный критерий. Методы целевого программирования эффективно сократят выделенное парето-оптимальное множество альтернатив, однако ЛПР должно принять во внимание громоздкость математических выкладок и субъективность экспертных оценок как критериев, так и самих альтернатив. В свою очередь метод нечеткой логики может признать оптимальным вариант, находящийся на границе паретооптимального множества, полностью усредненный по всем критериям, не выделяющийся ни максимальными, ни минимальными оценками экспертов. Поэтому лицу, которое несет ответственность за окончательное принятие решения, полезно иметь представление об особенностях изложенных методов решения многокритериальных задач. Контрольные вопросы 1. В чем состоят особенности задач многокритериальной оптимизации, затрудняющие их решение? 2. Что такое недоминируемое (эффективное, оптимальное по Парето) решение? 3. Какие графические методы нахождения множества Парето Вы знаете? 4. Приводит ли применение принципа оптимальности Парето к нахождению единственного решения в многокритериальной задаче принятия решений? 5. Что такое арбитражная схема? Какие виды арбитражных схем Вы знаете? 6. В чем заключается недостаток арбитражных решений? 176 7. В чем заключаются отличия многокритериальной оптимизации от задачи ЛП? 8. Перечислите известные Вам методы целевого программирования. 9. В чем преимущества МАИ перед другими известными Вам методами целевого программирования? 10. Какие классификационные признаки способов формализации нечеткости Вам известны? 11. Что такое характеристическая функция? В каких случаях два нечетких множества считаются равными? 12. Перечислите возможные операции над нечеткими множествами. Библиографический список 1. Айзекс Р. Дифференциальные игры. – М.: Мир, 1967. 2. Беллман Р., Заде Л. Принятие решений в расплывчатых условиях. М.: Мир, 1976. 3. Брахман Т.Р. Многокритериальность и выбор альтернатив в технике. – М.: Радио и связь, 1984. 4. Вентцель Е.С. Введение в исследование операций. – М.: Сов. радио, 1964. 5. Вентцель Е.С. Исследование операций: задачи, принципы, методология. – М.:. Наука, 1980. 6. Емельянов В.Ю. Методы моделирования стохастических систем управления. – СПб: БГТУ, 2004. 7. Емельянов В.Ю., Кругликов В.К. Теория принятия решений: базовые методы. – СПб: БГТУ, 2007. 8. Есипов Б.А. Методы оптимизации и исследование операций. – Самара: Изд-во СГАУ, 2007. 177 9. Зенкевич Н.А., Марченко И.В. Экономико-математические методы. Рабочая тетрадь №2. СПб: Изд-во МБИ, 2005. 10. Иванов В.А., Фалдин Н.В. Теория оптимальных систем автоматического управления. – М.: Наука, 1981. 11. Кабанов С.А., Александров А.А. Прикладные задачи оптимального управления: учебное пособие к практическим занятиям. – СПб: БГТУ, 2007. 12. Козлов Ю.М. Методы непрерывной оптимизации систем управления летательными аппаратами: учеб. пособие. – Л: ЛМИ, 1972. 13. Королев С.Н. Марковские модели массового обслуживания: учеб. пособие. – СПб: БГТУ, 2002. 14. Коршунов Ю.М. Математические основы кибернетики. - М.: Энергия, 1972. 15. Лейтман Дж. Введение в теорию оптимального управления. – М,: Наука, 1968. 16. Метод статистических испытаний (метод Монте-Карло)/ Под ред. Ю.А. Шрейдера. М.: Физматгиз, 1962. 17. Мушик Э., Мюллер П. Методы принятия технических решений. – М.: Мир, 1990. 18. Пантелеев А.В., Летова Т.А. Методы оптимизации в примерах и задачах. – М.: Высшая школа, 2002. 19. Родин Б.П. Вариационное исчисление: учебное пособие. - СПб: БГТУ, 2015. 20. Саати Т. Принятие решений. Метод анализа иерархий.– М.: Радио и связь, 1993. 21. Таха Хэмди А. Введение в исследование операций. М.: Издательский дом «Вильямс», 2005. 22. Толпегин О.А. Методы решения прикладных задач управления в игровой постановке: учебное пособие. - СПб: БГТУ, 2007. 178 23. Толпегин О.А. Прикладные методы оптимального управления: тексты лекций. – СПб: БГТУ, 2004. 24. Тутыгин А.Г., Коробов В.Б. Преимущества и недостатки метода анализа иерархий. – СПб: Известия РГПУ им.А.И.Герцена, 2010. 25. Химмельблау Д. Прикладное нелинейное программирование. – М.: Мир, 1975. 179 ОГЛАВЛЕНИЕ стр. Введение . . . . . . . . . . . . . . . . . . . 1. Примеры и классификация задач принятия решений. Обзор методов 2. Основные сведения из теории экстремальных задач 2.1. Основные понятия . . . . . . 2.2. Порядок решения экстремальных задач 3. Математическое программирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1. Линейное программирование: постановка задачи, основные понятия, графическая интерпретация . . . . . . . . . . . . . . . . . . . . . . . . 3.2.1. Алгебраический вариант . . . . . . . . . . . 3.2.2. Табличный вариант . . . . . . . . . . . . 3.3. Решение задач дискретного линейного программирования . . . 3.4. Двойственная задача линейного программирования . . . . . 3.5. Нелинейное программирование . . . . . . . . . . . 3.5.1. Аналитический метод . . . . . . . . . . . 3.5.2. Численный метод зондирования пространства параметров . 3.2. Симплекс-метод . . . . . 3.5.3. Методы безусловной оптимизации . . . . . . . . . 3.5.4. Методы безусловной оптимизации первого и второго порядка 3.5.5. Прямые методы условной оптимизации . 3.5.6. Непрямые методы условной оптимизации . . . . . . . . . . . . 3.5.7. Применение симплекс-метода для решения целочисленных задач нелинейного программирования . 4. Стратегические матричные игры . . . . . . . . . . . . . . . . . . . . 4.1. Основные термины и допущения. Формализация задачи. Принципы поиска решения . . . . . 180 . . . . . . . . . . 4.2. Общие методы решения стратегических матричных игр . . . . 4.2.1. Графическая интерпретация решения игры без седловой точки 4.2.2. Способы упрощения стратегических матричных игр . . . 4.2.3. Решение стратегических матричных игр методом линейного программирования . . . . . . . . . . . . . 4.2.4. Итерационный алгоритм Брауна-Робинсон . . . . . . . . . . . 4.3. Примеры решения стратегических матричных игр 5. Статистические матричные игры . . . . . . . . . . . 6. Многокритериальные задачи . . . . . . . . . . 6.1 Особенности постановки, классификация задач . . . . . . . 6.2. Обзор методов решения многокритериальных задач . . . . . . . 6.2.1. Оптимальность по Парето . . . . . . . . . . . 6.2.2. Арбитражные решения . . . . . . . . . . . . 6.2.3. Целевое программирование . . . . . . . . . . . 6.3. Применение алгебры нечетких множеств . . . . . . . . . . . . . . . . Библиографический список . . . . 181 . .