Формализация задач поиска оптимальных решений

1 ВОРОНЕЖСКИЙ ИНСТИТУТ ВЫСОКИХ ТЕХНОЛОГИЙ – АНОО ВО КУРС ЛЕКЦИЙ По дисциплине «Теория оптимизации и принятия решений в автоматизированных системах» ТЕМА1: ФОРМАЛИЗАЦИЯ РЕШЕНИЙ ЗАДАЧ ПОИСКА ОПТИМАЛЬНЫХ Лекция 1 Постановка задач оптимизации Под оптимизацией будем понимать процедуру определения в соответствии с установленными критериями наилучшего (оптимального) варианта из множества допустимых. При этом объектами оптимизации могут быть различные технические и механические конструкции, системы, технологические и производственные процессы, информационные потоки, грузопотоки, маршруты и т.д. Будем в дальнейшем называть их просто объектами, оптимальный вариант которых необходимо определить. Каждый объект характеризуется набором параметров. При этом различают внешние, внутренние и выходные параметры. Выходные параметры – величины, характеризующие свойства объекта и определяющие степень выполнения им своего функционального назначения (мощность, коэффициент усиления). Внешние параметры - величины, характеризующие свойства внешней по отношению к объекту среды и оказывающие влияние на его функционирование (температура окружающей среды, параметры входных сигналов, напряжение источников питания). Внутренние параметры - величины, характеризующие свойства отдельных элементов проектируемого объекта. Совокупность внутренних и внешних параметров называется входными параметрами объекта. Например, для вычислительной системы выходные параметры – производительность системы, коэффициенты нагрузки оборудования, вероятность решения поступающих задач и т. д.; внутренние параметры – емкость ЗУ, быстродействие процессоров; внешние параметры – интенсивность поступления задач и т. д. Входные параметры делятся на управляемые (варьируемые) и неуправляемые. Варьируемые параметры в процессе оптимизации изменяются, вызывая, в свою очередь, изменение выходных параметров. В дальнейшем мы будем говорить только о варьируемых параметрах объекта. Обозначим их: X  (x1,..., x n ) Различают задачи параметрической и структурной оптимизации. Структурная оптимизация связана с определением оптимальной структуры объекта (т. е. входящих в него элементов и их взаимосвязей). При параметрической оптимизации определяются значения параметров объекта заданной структуры, при которых достигается наилучшее сочетание его свойств. Например, при структурной оптимизации вычислительной системы осуществляется выбор количества и типов 2 оборудования, определение топологии сети и т. д. Параметрическая оптимизация может быть связана с определением оптимальной интенсивности поступления задач на обслуживание. В этом случае соответствующие интенсивности будут являться варьируемыми параметрами при оптимизации. Решение задачи оптимизации начинается с формирования математической оптимизационной модели. Обобщенно такая модель может быть записана следующим образом: f (X)  min(max) g i ( X )  ( ) b i , i  1, m h k (X)  d k , k  1, s (1.1) x min  x j  x max , j  1, n j j Здесь X  (x1,..., x n ) – вектор варьируемых параметров объекта; f(X) – целевая функция, т. е. функция, характеризующая наиболее важные и существенные свойства объекта и являющаяся критерием оценки качества каждого из вариантов. Целевая функция в оптимизационной модели может стремиться к максимуму или к минимуму. Ее еще называют критерием оптимальности, критерием эффективности, показателем качества объекта и т. д. На основании вычисления значений целевой функции f(X) анализируются и сравниваются между собой различные варианты объектов. В процессе оптимизации объект должен удовлетворять различным требованиям (конструктивным, техническим, экономическим), которые формализуются в виде системы ограничений. Ограничения на варьируемые параметры называют прямыми ограничениями. Здесь x min и x max – нижx min  x j  x max j j j j ние и верхние допустимые значения для управляемого параметра x j , которые зависят от решаемой оптимизационной задачи. Ограничения вида gi (X)  ()bi , h k (X)  d k называют функциональными ограничениями. Функциональные ограничения являются какими-либо функциями от варьируемых параметров и формулируются в виде системы равенств и неравенств. Совокупность функциональных и прямых ограничений образует допустимую область или область допустимых решений D. Таким образом, решение задачи оптимизации сводится к определению значений управляемых параметров X  (x1,..., x n ) , обеспечивающих оптимальное значение (максимум или минимум) целевой функции f(X) и удовлетворяющих системе ограничений. Такой вектор X  (x1,..., x n ) называется оптимальным решением. Задачи определения оптимальных значений параметров на допустимом множестве D называются еще задачами математического программирования. Рассмотренная математическая оптимизационная модель является обобщенной и конкретизируется при решении практических задач оптимизации. 3 Обобщенная схема процесса оптимального выбора 4 Несмотря на то, что задачи оптимизации решаются в разных предметных областях и характеризуются многообразием постановок и методов решения, можно выделить некоторую обобщенную последовательность типовых этапов поиска оптимальных вариантов (рисунок). Рассмотрим эти этапы более подробно. На этапе формирования задания на оптимизацию осуществляется содержательная постановка задачи, т. е. определяется набор варьируемых параметров и требования к ним, выбираются критерии оптимальности. Исходной информацией при этом являются данные о назначении, условиях применения и режимах функционирования объекта оптимизации, а также его описание. Эти данные позволяют определить цели оптимизации и в дальнейшем формализовать технические требования, предъявляемые к объекту, в виде оптимизационной модели. Формирование оптимизационной модели связано с формализацией содержательной постановки задачи, т. е. с ее математической записью в форме (1.1). При этом необходимо определить взаимосвязи между входными и выходными параметрами и сформулировать критерии оптимальности и функциональные ограничения в аналитической или алгоритмической форме. Этот этап связан также с нормированием (нормализацией) варьируемых параметров, если они имеют различную физическую размерность. При этом различают линейную и логарифмическую нормализацию: x iн  x i / i (линейная нормализация), x iн  ln( x i / i ) (логарифмическая нормализация), где i – константа, равная единице измерения параметра x i . Типизация модели связана с ее преобразованием и приведением к типовому виду, допускающему использование стандартных оптимизационных процедур. Одним из важнейших этапов поиска оптимальных вариантов является рациональный выбор метода оптимизации. Как уже было отмечено в п. 1.1, задачи оптимизации делятся классы, для каждого из которых разработаны свои методы и алгоритмы решения. Отнесение задачи к определенному классу и определение соответствующего класса методов осуществляется на основании оценки свойств задачи (числа критериев и ограничений, характера изменения параметров и т. д.) и, как правило, сложности не представляет. Однако в рамках каждого класса методов существуют множество различных оптимизационных процедур, выбор которых является достаточно сложной проблемой, так как один и тот же алгоритм при решении различных задач может показывать разную эффективность. Поэтому на практике часто используется многометодный режим решения задач оптимизации. Далее в зависимости от выбранного метода оптимизации определяются его параметры, а также выбирается начальное приближение. От рационального выбора этих величин также во многом зависят результат и трудоемкость решения оптимизационной задачи. Сам процесс оптимизации представляет собой итерационную последовательность процедур синтеза, анализа и принятия решений. На этапе синтеза в со- 5 ответствии с выбранным алгоритмом определяются очередные значения варьируемых параметров (т. е. синтезируется очередной вариант сочетания значений параметров). Этап анализа связан с оценкой полученного варианта, т. е. с вычислением значений критериев и ограничений, соответствующих полученным значениям варьируемых параметров. На этапе принятия решений определяется, является ли данный вариант удовлетворительным. Если получен приемлемый вариант, процесс оптимизации заканчивается, в противном случае – продолжается, т. е. осуществляется переход к следующей итерации. Обычно в вычислительных процедурах оптимизации проверка качества получаемого варианта осуществляется автоматически. При этом на начальном этапе оптимизации определяется требуемая точность вычислений, при достижении которой алгоритм заканчивает работу. Если при завершении оптимизационного процесса полученный вариант не устраивает проектировщика, можно выполнить следующие действия: изменить начальное приближение; изменить параметры метода; выбрать другой метод оптимизации; скорректировать оптимизационную модель. После внесения соответствующих изменений оптимизационный процесс продолжается до получения оптимального результата. Необходимо заметить, что все этапы рассмотренного итерационного процесса, кроме непосредственно оптимизации, выполняются проектировщиком. Таким образом, решение каждой практической задачи, связанной с поиском оптимальных вариантов, требует индивидуального подхода и во многом зависит от опыта и интуиции проектировщика. Поэтому при разработке современных систем оптимизации большое внимание уделяется вопросам принятия оптимальных решений в интерактивном режиме, когда пользователь имеет возможность оперативно взаимодействовать с ЭВМ на любом этапе решения своей задачи. Классификация задач оптимизации. 1. В зависимости от числа управляемых параметров различают задачи одномерной и многомерной оптимизации. В задачах одномерной оптимизации имеется один варьируемый параметр, а в задачах многомерной оптимизации – несколько параметров. 2. По характеру искомого оптимума различают задачи локальной и глобальной оптимизации (унимодальные и многоэкстремальные задачи). 3. В зависимости от наличия ограничений выделяют задачи безусловной и условной оптимизации. В задачах безусловной оптимизации ограничения отсутствуют, и варьируемые параметры могут изменяться в любых пределах. 4. В зависимости от количества критериев оптимальности различают задачи однокритериальной (скалярной) и многокритериальной (векторной) оптимизации. В задачах многокритериальной оптимизации имеется несколько критериев оптимальности. 5. По виду целевой функции и ограничений различают задачи линейной и нелинейной оптимизации. В задачах линейной оптимизации целевая функция и все 6 функции-ограничения линейны. Если хотя бы одна из функций является нелинейной, задача относится к классу задач нелинейной оптимизации. 6. По характеру изменения варьируемых параметров различают задачи непрерывной и дискретной оптимизации. В задачах непрерывной оптимизации параметры изменяются непрерывно в пределах, установленных функциональными ограничениями. В задачах дискретной оптимизации варьируемые параметры принимают дискретные значения. Частными случаями задач дискретной оптимизации являются задачи целочисленной и булевой оптимизации. В задачах целочисленной оптимизации варьируемые параметры могут принимать только целочисленные значения. В задачах булевой оптимизации x j  {0,1} . Если D – дискретное конечное множество точек, то такая дискретная задача называется комбинаторной. Если при оптимизации часть параметров дискретна, а часть имеет непрерывный характер, то рассматривается задача частично дискретной (непрерывно-дискретной) оптимизации. Необходимо заметить, что одна и та же оптимизационная задача может относиться к нескольким типам (например, являться однокритериальной, линейной и непрерывной). Для различных типов оптимизационных задач разработаны соответствующие методы их решения, классификация которых является аналогичной. При этом данные методы, как правило, инвариантны к предметной области их приложения. 7 ТЕМА 2: РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОЙ ОПТИМИЗАЦИИ Лекции 2,3 Постановка задачи линейной оптимизации Задача линейной оптимизации (ЛО) — это задача оптимизации, в которой целевая функция и все функциональные ограничения линейны. Задача ЛО состоит в определении максимума (минимума) линейной функции на допустимом множестве, описываемом системой линейных ограничений. В общем виде задача ЛО может быть записана следующим образом: n F   c j x j  max (min); j1 n  a ij x j  (, )b i , i  1, m; j1 x k  0, k  1, s, s  n. Стандартной (или симметричной) задачей ЛО называется задача: n F   c j x j  max (min); j1 n  a ij x j  b i , i  1, m; j1 x j  0, j  1, n. Для разработки вычислительных методов в качестве стандарта принята каноническая форма записи задачи ЛО: n F   c j x j  min; j1 n  a ij x j  b i , i  1, m; j1 x j  0, j  1, n. Каноническая форма ЛО характеризуется следующими условиями: 1. Целевая функция подлежит минимизации. 2. Все переменные должны быть неотрицательны. 3. Правые части ограничений должны быть неотрицательны. 4. Все ограничения записываются в виде равенств. Указанные выше три формы записи задачи ЛО можно привести друг к другу с помощью эквивалентных преобразований. 8 Прикладные линейные модели Рассмотрим основные приёмы построения математической модели для типовой задачи линейной оптимизации - задачи определения оптимального производственного плана (такие задачи решаются в автоматизированных системах управления производством). Для изготовления n видов продукции A1,…,An необходимы ресурсы S1,…,Sm (сырье, рабочая сила, оборудование и т.д.). Заданы значения a ij, которые характеризуют количество ресурса Si , необходимого для выпуска единицы продукции Aj. Запас каждого ресурса Si ограничен и равен bi . От реализации единицы продукции Aj может быть получена прибыль cj. Необходимо так составить производственный план (т.е. определить, сколько продукции каждого вида необходимо выпустить), чтобы общая прибыль от производства всей продукции была максимальной. Исходные данные задачи можно удобно представить в виде табл. 2.1: Таблица 2.1 Ресурсы S1 S2 … Sm Прибыль Виды продукции A1 A2 … a11 A12 ... a21 a22 ... ... ... ... am1 am2 ... c1 c2 … Запасы ресурсов An A1n b1 a2 n b 2 ... ... amn bm cn Обозначим через xj количество продукции Aj, которое необходимо выпустить по плану. Тогда математическая модель данной задачи имеет следующий вид: c1x1+ c2x2+...+ cnxn max; n  a ij x j  b i , i  1, m; j1 x j  0, j  1, n. Здесь целевая функция – это общая прибыль от производства всей продукции. Каждое i-е ограничение характеризует общее количество ресурса Si для производства всей продукции, которое не должно превышать величины bi. Кроме ограничения по ресурсам, в условия задачи (а, следовательно, и в ее математическую модель) могут вводиться дополнительные ограничения на планируемый выпуск продукции (ограничения по ассортименту, условия комплектности и т.д.). Пример. Требуется определить, в каком количестве необходимо выпускать продукцию четырех типов Прод1, Прод2, Прод3, Прод4 для изготовления которой требуются ресурсы трех видов: трудовые ресурсы, сырье, финансы. Нормы расхода ресурсов каждого вида для выпуска единицы продукции, а также прибыль, получаемая от реализации единицы каждого типа продукции, приведены в 9 табл. 2. Количество расходуемых ресурсов не должно превышать имеющихся запасов. Таблица 2.2 Ресурсы Трудовые Сырье Финансы Прибыль Виды продукции Прод. 1 Прод. 2 3 1 1 8 1 4 7 3 Запасы ресурсов Прод.3 Прод.4 2 6 7 6 4 2 2 12 440 200 320 Математическая модель для решения данной задачи будет иметь следующий вид: F=7x1+3x2+6x3+12x4max; 3x1+x2+2x3+4x4 440; x1+8x2+6x3+2x4 200; x1+4x2+7x3+2x4 320; xj 0, j=1,4 . Симплекс-метод решения задач линейной оптимизации Симплекс-метод является основным методом решения задач линейной оптимизации. Перед его использованием задачу необходимо привести к канонической форме записи. При этом используются следующие приемы: 1. Для перехода от задачи максимизации к задаче минимизации целевую функцию необходимо умножить на –1. 2. Переменные, на которых не наложено ограничение неотрицатель-ности, заменяются во всех ограничениях и в целевой функции разностью двух неотрицательных переменных xj = uj- wj uj, wj  0. 3. Переход к ограничениям с неотрицательными правыми частями осуществляется умножением левой и правой частей ограничений с отрицательными правыми частями на –1. При этом знаки соответствующих неравенств меняются на противоположные. 4. Переход от ограничений-неравенств к ограничениям-равенствам производится путем введения дополнительных неотрицательных переменных. При этом если знак неравенства , дополнительная переменная прибавляется к левой части ограничения, а если , то вычитается. Таким образом, ограничениенеравенство ai1x1 + ai2x2 +…+ ainxn  bi преобразуется в ограничение-равенство ai1x1 + ai2x2 +…+ ainxn + xn+1 = bi (xn+1  0), 10 где xn+1 – дополнительная переменная, xn+10. Ограничение-неравенство: ai1x1 + ai2x2 +…+ ainxn  bi преобразуется в ограничение-равенство следующим образом: ai1x1 + ai2x2 +…+ ainxn - xn+1 = bi (xn+1  0) В каждое ограничение-неравенство вводится своя дополнительная переменная. Число вводимых дополнительных неотрицательных переменных равно числу преобразуемых неравенств. Рассмотрим Задачу ЛО в канонической форме: n F   C j x j  min; j1 n  a ij x j  b i , i  1, m; j1 x j  0, j  1, n. Вектор X = (x1,…, xn), удовлетворяющий системе ограничений задачи, называется допустимым решением или планом. План, X*=(x1*,…,xn*), при котором целевая функция принимает оптимальное значение, называется оптимальным. Перепишем задачу в векторной форме. n F   C j x j  min; j1 n  A i x j  B, i  1, m; j1 x j  0, j  1, n , где A1,…,An – m-мерные вектор-столбцы, составленные из коэффициентов при переменных в системе ограничений:  a11   a1n  a  a  A1   21   A n   2n  .       a  a   m1   mn  B – вектор-столбец свободных членов системы ограничений:  b1  b  B   2 .    b   m 11 План X = (x1,…, xn) называется опорным планом задачи ЛО, если система векторов Аj, входящих в разложение n  A jx j  B с положительными коэффици- j1 ентами xj , линейно независима. Так как векторы Аj являются m-мерными, то из определения опорного плана следует, что число его положительных компонент не может быть больше, чем m. Симплекс-метод решения задачи ЛО основан на переходе от одного опорного плана к другому, при котором значение целевой функции убывает. Указанный переход возможен, если известен какой-нибудь исходный опорный план. Такой план можно легко указать, если ЗЛП записана в форме: F  c1 x 1  c 2 x 2    c n x n  min; x 1  a 1m 1 x m 1    a 1n x n  b1 ; x 2  a 2m 1 x m 1    a 2n x n  b 2 ;  x m  a mm 1 x m 1    a mn x n  b m ; x j  0, j  1, n. Векторная форма данной задачи имеет вид: n F   c j x j  min; j1 A1 x 1  A 2 x 2    A m 1 x m 1    A n x n  B; x j  0 , j  1, n, где  a1m 1   a1n   b1  1 0  0 a  a  b   0 1  0 A1    , A 2    , A m    , A m 1   2m 1  , A n   2n  , B   2  .           0 0  0  0 0 1 a  a  b         mm 1   mn   m Переменные, которые входят только в одно уравнение системы ограничений с коэффициентом равным 1, называют базисными переменными (в рассматриваемом примере это переменные x1… xm). Остальные переменные называются свободными. Тогда, приравнивая базисные переменные соответствующим правым частям ограничений, а свободные переменные нулю, получим опорный план X = (b1, b2,…, bm,0 ,…,0), определяемый системой единичных векторов, А1,…, Аm , которые образуют базис m-мерного пространства. Для удобства расчетов в симплексном методе все данные по задаче заносят в симплекс-таблицу: 12 Таблица 2.3 x с B x1 x2 … xm c1 c2 … cm b1 b2 … bm F с1 x1 A11 A21 … Am1 1 c2 x2 a12 a22 … am2 2 … … … … … … … cn xn a1n a2n … amn n В верхнюю строку таблицы заносятся коэффициенты при всех переменных в целевой функции. В первом столбце таблицы записываются базисные переменные в той последовательности, в которой они входят в систему ограничений, во втором – коэффициенты целевой функции при базисных переменных, в третьем – правые части всех ограничений, в последующих столбцах – коэффициенты при соответствующих переменных в системе ограничений. В нижней строке таблицы записываются оценки по каждой переменной, определяемые следующим обраm зом:  j   c i a ij  c j . Очевидно, что для базисных переменных оценки равны i 1 нулю. На каждой итерации симплекс-метода осуществляется вывод из базиса какой-либо переменной и включение в него другой переменной с соответствующим пересчетом элементов таблицы. Перед решением задачи ее необходимо привести к канонической форме. Основные шаги симплекс – метода: 1. Определение начального опорного плана. 2. Составление симплекс-таблицы. m 3. Вычисление оценок  j   c i a ij  c j . i 1 4. Анализ оценок. 4.1. Если  j  0 j  1, n , то получено оптимальное решение. 4.2. Если существует хотя бы одна оценка j > 0 , для которой a ij  0i  1, m , то целевая функция не ограничена снизу на множе- стве допустимых решений (ЗЛП не имеет решения).   max  j 4.3. Из всех оценок j > 0 выбирается максимальная: k j : j  0 Переменная xk, которой соответствует максимальная оценка, становится на текущей итерации базисной, а k-й столбец объявляется ведущим столбцом. 5. Определение ведущей строки. Для этого находятся отношение правых частей ограничений к положительным элементам ведущего столбца и среди них выбирается минимальное: 13 bs b  min i a sk a ik . i : a ik  0 S-я строка объявляется ведущей строкой. Элемент, находящийся в симплекс-таблице на пересечении s-й строки и k-го столбца ask, называется ведущим элементом. 6. Пересчет элементов симплекс-таблицы. При этом элементы ведущей строки as1,…, asn, bs делятся на ведущий элемент ask. Пересчет остальных элементов осуществляется по правилу прямоугольника. j-й столбец s-я строка k-й столбец ask i-я строка aik аij аsj Пусть ask – ведущий элемент. Элемент aij – пересчитывается следующим образом: a sk a ij  a ik a sj a ij  . a sk 7. Переход к шагу 3 Оптимальное решение определяется следующим образом: базисные переменные приравниваются соответствующим правым частям, остальные нулю. Пример x1-x2-3x3min 2x1-x2+x3  1 4x1-2x2+x3  -2 3x1+x3  5 x1, x2, x3  0 Приведем задачу к канонической форме x1-x2-3x3min 2x1-x2+x3+x4 = 1 -4x1+2x2-x3+x5 = 2 3x1+ x3+x6 = 5 x1, x2, x3  0 Составим симплекс-таблицу и решим задачу 14 xб Сб b x4 x5 x6 1 2 5 x3 x5 x6 -3 1 3 4 -3 x3 x2 x6 -3 -1 x3 x2 x1 -3 -1 1 4 3 1 -15 4 11/3 1/3 -46/3 1 x1 2 -4 3 -1 2 -2 1 -7 -2 3 1 1 -1 x2 -1 2 1 -1 1 1 4 1 1 -3 x3 1 -1 1 3 1 1 1 x4 1 1 1 -1 -3 2 1 -2 -7 2 -1/3 -2/3 -19/3 x5 1 1 1 1 -1 -4 1 1/3 -1/3 -11/3 x6 1 1 1 2/3 1/3 -1/3 Оптимальное решение: x1=1/3; x2=11/3; x3=4; x4=0; x5=0; x6=0. Метод искусственного базиса Как было указано выше, решение задачи ЛО симплекс-методом начинается с указания какого-либо первоначального опорного плана. Для задачи ЛО, записанной в канонической форме, можно непосредственно указать опорный план, если среди векторов Aj, компонентами которых служат коэффициенты при переменных в системе ограничений данной задачи, есть m единичных (т.е., имеются m базисных переменных). Однако для многих ЗЛП, записанных в канонической форме, не всегда можно сразу определить опорный план. Рассмотрим задачу n F   C j x j  min; j1 n  A i x j  B, i  1, m; j1 x j  0, j  1, n. Пусть в данной задаче среди векторов 15  a 11   a 1n    A1    , ..., A n      a   a mn  m1      нет единичных.    В данном случае к каждому i-му уравнению системы ограничений добавляется неотрицательная переменная xn+i , называемая искусственной переменной. Так как введение искусственных переменных, в отличие от дополнительных, меняет множество решений задачи, то они вводятся также и в выражение для целевой функции с очень большим коэффициентом M > 0 (тогда в процессе решения задачи минимизации искусственные переменные будут стремиться к нулю). В результате получается задача, называемая расширенной по отношению к исходной: n F   c jx j  M j1 n  a ij x j j1 nm  x j  min ; j n 1  x n i  b i , i  1, m ; x j  0, j  1, n  m . В результате может быть указан первоначальный опорный план. Искусственные переменные приравниваются к правым частям (xn+i=bi), остальные – нулю ( x j  0 j  1, n ). Тогда целевая функция примет вид: n m j1 i 1 F   c j x j  M  b i  min , а оценки j в данном случае будут складываться из двух частей, одна из которых зависит от М, а другая не зависит: m m j1 i 1  j   c i a ij  c j  M  a ij  c j . Исходные данные расширенной задачи заносят в симплекс-таблицу, которая содержит на строку больше, чем обычная. В последнюю, (m + 2)-ю строку оценок таблицы записывают коэффициенты при M, а в (m + 1)-ю - слагаемые, не содержащие M. Так как знак j определяется знаком коэффициента, стоящего при M, ведущий столбец (и соответственно базисную переменную) выбирают по наибольшему положительному элементу (m + 2)-й строки таблицы. Пересчет симплекстаблицы при переходе от одного опорного плана к другому производят по общим правилам симплексного метода. Итерационный процесс по (m + 2)-й строке ведут до тех пор, пока 1) либо все искусственные переменные не будут исключены из базиса; 2) либо не все искусственные переменные будут исключены, но (m + 2)-я строка не содержит больше положительных элементов. В первом случае полученное базисное решение соответствует некоторому опорному плану исходной задачи, (m+2)-я строка таблицы вычеркивается и ре- 16 шение задачи продолжают обычным симплексными методом. Во втором случае, если элемент, стоящий в (m + 2)-й строке столбца B положителен, задача не имеет решения, если он равен нулю, то базис содержит по крайней мере один из векторов искусственного базиса. Если в процессе решения задачи какая-либо искусственная переменная выводится из базиса, то соответствующий столбец симплекс-таблицы можно вычеркнуть и не пересчитывать (т.к. эту переменную не имеет смысла вводить ни в один из последующих базисов). Рассмотренный метод построения начального опорного плана называется методом искусственного базиса. Таким образом алгоритм метода включает следующие шаги: 1. Составляется расширенная задача 2. Находится опорный план решения задачи 3. С использованием симплекс-метода искусственные переменные исключаются из базиса. В результате получается некоторый опорный план исходной задачи. 4). Нахождение оптимального плана исходной задачи с использованием симплекс-метода. Пример:  2x1  3x 2  6x 3  x 4  min 2x1  x 2  2x 3  x 4  24  2x1  3x 2  6x 3  x 4  Mx 7  min  x1  2x 2  4x 3  22 x1  x 2  2x 3  10 xб Сб b x4 x5 x7 -1 M x4 x5 x3 -1 -6 x4 x6 x3 -1 -6 24 22 10 -24 10 34 2 5 -64 35 1 11/2 -68 2x1  x 2  2x 3  x 4  24 x1  2x 2  4x 3  x 5  22 x1  x 2  2x 3  x 6  x 7  10 -2 x1 2 1 1 1 3 -1 1/2 -4 5/2 -1/2 1/4 -2 3 x2 1 2 -1 -4 -1 4 -1/2 2 2 1/2 -8 Ответ: x*=(0; 0; 11/2; 35; 0; 1). -6 x3 -2 4 2 8 2 1 1 -1 x4 1 1 1 x5 1 1 1/2 1/2 1/4 -2 x6 -1 -1 -1 2 -1/2 4 1 M x7 1 17 Двойственность в линейной оптимизации Каждой задаче ЛО можно поставить в соответствие двойственную в соответствии с следующими правилами: 1) если целевая функция F исходной задачи стремится к минимуму, то целевая функция Ф двойственной задачи – к максимуму и наоборот; 2) Каждому i-му ограничению исходной задачи соответствует переменная yi двойственной задачи (двойственная переменная), а каждой j-й переменной исходной задачи соответствует j-е ограничение исходной задачи; 3) коэффициентами при переменных целевой функции двойственной задачи являются правые части ограничений исходной задачи, а правыми частями ограничений двойственной задачи являются коэффициенты при целевой функции в исходной задаче; 4) матрица коэффициентов при двойственных переменных в системе ограничений двойственной задачи является транспонированной матрицей коэффициентов при переменных в ограничениях исходной задачи; 5) для удобства построения двойственных задач рекомендуется в исходной задаче ограничения-неравенства записывать со знаком “ ” при максимизации и со знаком “ ” при минимизации; 6) каждому i-му ограничению – неравенству исходной задачи соответствует в двойственной задаче условие неотрицательности (yi0), а ограничению равенству - переменная yi произвольного знака; 7) неотрицательной переменной исходной задачи xj0 соответствует в двойственной задаче j-е ограничение – неравенство, а произвольной переменной xj - равенство. При этом если двойственная задача подлежит минимизации, неравенство записывается со знаком “ ”, а если двойственная задача подлежит максимизации – со знаком “ ”. Рассмотренные правила задач иллюстрируются табл. 2.4. Таблица 2.4 Исходная задача Двойственная задача n m  C j x j  max  b i y i  min j1 i 1 n  a ij x j  b i , (i  1, m1 ) j1 n  a ij x j  b i , (i  m1 , m 2 ) j1 x j  0, ( j  1, n1 ) x j  любого знака, ( j  n1 , n 2 ) y i  0, (i  1, m1 ) y i  любого знака, (i  m1 , m 2 ) m  a ij y i  C j , ( j  1, n1 ) i 1 m  a ij y i  C j , ( j  n1 , n 2 ) i 1 18 Пример. Построить двойственную задачу к задаче определения производственного плана, приведенной в примере 1: определить, сколько продукции каждого вида xj необходимо изготовить, чтобы при заданной прибыли от реализации единицы продукции cj и заданных размерах имеющихся ресурсов bi максимизировать общую прибыль. Математическая модель задачи из примера 1 формулировалась следующим образом: F=7x1+3x2+6x3+12x4max; 3x1+x2+2x3+4x4 440; x1+8x2+6x3+2x4 200; x1+4x2+7x3+2x4 320; xj 0, j=1,4 . Введя три двойственные переменные y1 , y2 , y3 , в соответствии с приведенными выше правилами построим двойственную задачу: Ф=440у1+200y2+320у3min; 3y1+y2+y3 7; y1+8y2+4y3 3; 2y1+6y2+7y36; 4y1+2y2+2y3 12; yi 0, j=1,4 . Отсюда видно, что двойственная задача заключается в определении стоимости единицы ресурса yi, чтобы при заданных количествах ресурсов bi и заданной прибыли cj от реализации единицы продукции минимизировать общую стоимость ресурсов. Интерпретация двойственных задач Рассмотрим экономическую интерпретацию двойственных задач. Обратимся к задаче составления производственного плана. Исходная задача: сколько и какой продукции хj (j=1, n) необходимо произвести, чтобы при заданной прибыли от выпуска единицы каждого вида продукции Cj и размерах имеющихся ресурсов bi максимизировать общую прибыль n  C j  x j  max j1 C j -прибыль от единицы продукции j-го вида, х j - количество единиц продукции j-го вида, max - доход (прибыль) n  a ij  x j  b i j 1 i  1, m , где aij - затраты i-го ресурса на производство единицы продукции j-го вида, xj - 19 количество единиц продукции j-го вида, bi - запас i-го ресурса, n  a ij  x j -общие затраты i-го ресурса на производство всей продукции. j1 Двойственная задача m  bi  yi  min i 1 где, bi - запас i-го ресурса; yi - стоимость единицы i-го ресурса; min - общая стоимость всех ресурсов. m  а ij  yi  C j i 1 аi - затраты i-го ресурса на производство продукции j-го вида; yj - стоимость единицы i-го ресурса; Cj - прибыль от продукции j-го вида; m  а ij  y i да. i 1 -цена всех ресурсов, идущих на изготовление продукции j-го ви- Двойственная задача: Какова должна быть стоимость единицы каждого из ресурсов yj i = 1,m , чтобы при заданных количествах ресурсов bi и заданных величинах дохода Cj от производства каждого вида продукции минимизировать общую стоимость ресурсов? Переменные yj называются учетными, неявными, фиктивными, теневыми ценами. В теории двойственности важное значение имеют теоремы, определяющие связь между решениями прямой и двойственной задач. Теорема двойственности. Если из пары двойственных задач одна имеет оптимальный план, то и вторая тоже имеет оптимальный план, причем оптимальные значения целевых функций обеих задач равны между собой: max F  min Ф * . m m i 1 i 1 При этом max F   b i y i   y i b i . Отсюда следует, что двойственная переменная yi является коэффициентом при bi и, следовательно, показывает, как изменится целевая функция при изменении i- го ресурса на единицу. В литературе двойственные переменные часто называют двойственными оценками. Теорема равновесия. План x *  (x1* ,..., x *n ) прямой задачи и план y*  ( y1*,..., y*n ) соответствующей двойственной задачи являются оптимальными при выполнении следующих условий: - если при подстановке компонент оптимального плана x *  (x1* ,..., x *n ) в систему ограничений исходной задачи i-е ограничение обращается в неравенство, то i-я компонента оптимального плана двойственной задачи y *i равна нулю. 20 - если i-я компонента оптимального плана двойственной задачи y *i положительна, то i-е ограничение исходной задачи удовлетворяется ее оптимальным решением как строгое равенство. Таким образом, в парах соотношений x *j  0, m  a ij y *i  c j i 1 и y *i  0, n  a ij x *j )  b i j1 из знака строгого неравенства во одном соотношении каждой пары следует знак строгого равенства в другом. Условия теоремы равновесия часто записывают в виде m x *j (  a ij y *i  c j )  0, j  1, n; i 1 n y *i (b i   a ij x *j )  0,i  1, m. j1 и называют условиями дополняющей нежесткости. Из рассмотренных теорем можно сделать следующие выводы: А) Всякий раз, когда i-е ограничение прямой задачи обращается в строгое неравенство, i-я компонента решения двойственной задачи обращается в 0. Аналогично, всякий раз, когда i-е ограничение двойственной задачи выполняется как строгое неравенство, j-ая компонента оптимального плана обращается в ноль. Б) Обратно, если i-я компонента оптимального плана двойственной задачи положительна, i-е ограничение исходной задачи выполняется как строгое равенство. Верно и для двойственной задачи. m x *j (C j   a ij  y*i )  0 i1 n y*i (b i   a ij  x *j )  0 j1 Отсюда следует: а) Если двойственная оценка yi* = 0, то сырье i-го вида не полностью используется при производстве продукции. б) Если j-е ограничение двойственной задачи выполняется как строгое неравенство, то j-ый вид продукции выпускать экономически нецелесообразно, хj =0 (т.е. в двойственной задаче цена всех ресурсов больше прибыли) в) Если yi  0, то сырье i-го типа полностью используется при производстве. 21 Связь между решением прямой и двойственной задач Значения двойственных оценок можно определить по симплексной таблице решения прямой задачи следующим образом: -(  j  c j ), где j-номера столбцов единичных векторов из исходной симплекс-таблицы (на начальной итерации);  j -окончательные оценки из последней симплекс-таблицы, соответствующие этим векторам. При этом индексы двойственных оценок определяются номером ограничения, которому они соответствуют. Необходимо заметить, что если в качестве канонической формы рассматривается задача максимизации, то сумма  j  c j берется без знака “-“. Двойственный симплекс-метод Двойственный симплекс-метод используется при нахождении решения задачи ЛО, записанной в канонической форме, для которой среди векторов Аj , составленных из коэффициентов при неизвестных в системе ограничений, имеются m единичных. Вместе с тем этот метод можно применять при решении ЗЛП, правые части ограничений которой могут быть отрицательными числами. Рассмотрим задачу ЛО, записанную в канонической форме и предположим, что выбран такой базис (A1,...,Am), при котором хотя бы одна из правых частей ограничений отрицательна, но для всех переменных xj оценки  j  0 . n F   c jx j  min j1 n  a ijx j  bi , i  1, m j1 x j  0, j  1, n. Тогда решение X=(b1,…,bm,0,…,0) системы линейных алгебраических уравнений, задающей ограничения, называется псевдопланом ЗЛП. Псевдоплан не является планом исходной ЗЛП, т. к. некоторые его компоненты отрицательны. Очевидно, что для получения оптимального плана исходной ЗЛП необходимо исключить из правых частей ограничений симплекс-таблицы все отрицательные элементы. При этом должно выполняться условие  j  0 j  1, n . Основные шаги двойственного симплекс-метода. 1. Нахождение псевдоплана задачи. 2. Составление симплекс- таблицы. 3. Проверка псевдоплана на оптимальность. Если псевдоплан оптимален (все правые части bi≥0, а все оценки ∆j≤ 0), решение задачи найдено. В противном случае необходимо перейти к следующему шагу. 22 4. Выбор ведущей строки. При этом в столбце правых частей ограничений выбирается наименьший отрицательный элемент, и строка, которой он соответствует, объявляется ведущей строкой. bs  min bi i : bi  0 или bs  max | bi | i : bi  0 Если в ведущей строке s все элементы неотрицательны, то целевая функция двойственной задачи не ограничена на множестве допустимых значений (задача не имеет решения). Если в s-й строке существуют элементы asj < 0, то осуществляется выбор ведущего столбца. 5. Выбор ведущего столбца. При этом для s-й ведущей строки определяются j отношения для asj < 0, среди них выбираются минимальное, и столбец, коa sj торому оно соответствует, объявляется ведущим j k  min a sk a sj 0 a sj 6. Пересчет элементов симплекс-таблицы по правилу прямоугольника. Переход к шагу 3. Замечание 1. Если имеется исходная задача, среди правых частей ограничений которой имеются отрицательные, то условие j≤0 можно не учитывать до исключения всех отрицательных правых частей. Затем оптимальный план можно определить обычным симплекс-методом. Замечание 2. Двойственный симплекс-метод может применяться: - для решения задач линейной оптимизации, правые части ограничений которых могут быть отрицательны (при этом двойственный симплекс-метод позволяет в ряде случаев упростить решение исходной задачи и обойтись без использования искусственных переменных); - для решения задач линейной оптимизации с возрастающим числом ограничений. Пример. Решить задачу линейной оптимизации: F  x1  x 2  2x 3  max x1  x 2  x 3  8  x1  x 2  4 x  2 x  6 2  1 x1, x 2 , x 3  0 Решение. Приведем задачу к канонической форме, введя три дополнительные переменные: x 3 , x 4 , x 5 . 23 F   x1  x 2  2x 3  min x1  x 2  x 3  8  x1  x 2  x 4  4 x  2 x  x  6 2 5  1 x1, x 2 , x 3 , x 4 , x 5  0 В системе ограничений данной задачи имеется только одна базисная переменная x3. Умножаем второе и третье ограничения на (–1), в результате чего в системе ограничений появятся еще 2 базисные переменные x4 и x5  x1  x 2  2x 3  min x1  x 2  x 3  8   x1  x 2  x 4  4  x  2x  x  6 2 5  1 x1, x 2 , x 3 , x 4 , x 5  0 Так как правые части второго и третьего ограничений отрицательны, для решения данной задачи используем двойственный симплекс-метод. Составим симплекс-таблицу: xБ cБ B x3 x4 x5 -2 8 -4 -6 -16 -1 x1 1 -1 -1 -1 -1 x2 1 1 -2 -1 -2 x3 1 x4 1 x5 1 Псевдоплан задачи X = (0, 0, 8, -4, -6) не является оптимальным, т. к. имеет отрицательные компоненты. Определяем ведущую строку. Для этого в столбце правых частей выбираем отрицательные элементы и среди них определяем минимальный. Следовательно, ведущей строкой будет третья строка. Для определения ведущего столбца определяем отношения оценок к отрицательным элементам ведущей строки и среди них выбираем минимальное. Для первого столбца отношение 1 1 1  1 . Для второго столбца  . Следова1 2 2 тельно, ведущим столбцом будет второй столбец. Элементы таблицы пересчитываем по правилу прямоугольника. 24 xБ cБ x3 x4 x2 -2 -1 -1 x1 5 1/2 -7 -3/2 3 1/2 -13 -1/2 B -1 x2 1 -2 x3 1 x4 1 x5 1/2 1/2 -1/2 -1/2 В качестве ведущей строки выбирается вторая (т. к. в столбце находится единственный отрицательный элемент –7), в качестве ведущего столбца – первый. В результате симплекс-таблица примет вид: -1 -1 -2 xБ cБ B x1 x2 x3 x4 x5 x3 -2 8/3 1 1/3 2/3 x1 -1 14/3 1 -2/3 -1/3 x2 -1 2/3 1 1/3 -1/3 -32/3 -1/3 -2/3 Так как условия оптимальности выполнены, получен оптимальный план исходной задачи: x1*  14 / 3; x *2  2 / 3; x *3  8 / 3; x *4  0; x *5  0 . 25 ТЕМА 3. НЕЛИНЕЙНАЯ ОПТИМИЗАЦИЯ Лекции 4,5 Постановка задачи нелинейной оптимизации В общем виде задача нелинейной оптимизации может быть сформулирована следующим образом: extr f (X); g i (X)  (, )bi , i  1, m; x j  0, j  1, n, где хотя бы одна из функций f(x), g i ( x ) является нелинейной. Здесь X  (x1,..., x n ) – вектор варьируемых параметров. На переменные xj также могут накладываться ограничения: d j  x j  D j , где d j и D j – нижняя и верхняя границы для каждой j-й переменной. Задача без ограничений называется задачей безусловной оптимизации, задача с ограничениями – задачей условной оптимизации. Основные подходы к решению задач нелинейной оптимизации с ограничениями. Преобразование задач с ограничениями к задачам безусловной оптимизации Одним из наиболее распространенных и часто используемых на практике приемов решения задач нелинейной оптимизации с ограничениями является их преобразование к задачам безусловной оптимизации. При этом для учета прямых и функциональных ограничений могут быть использованы различные подходы. Рассмотрим задачу нелинейной оптимизации с прямыми и функциональными ограничениями: f (X)  min g i (X)  (, )b i , i  1, m (3.1) x min  x j  x max j j , j  1, n Прямые ограничения на варьируемые параметры можно исключить из данной задачи с помощью замены переменных: x j  V j (z j ), j  1, n , -  zj   , где Z  (z1,..., z n ) – вектор новых варьируемых параметров. Тогда целевая функция задачи может быть переформулирована следующим образом: 26 f (X )  f (V1 ( Z),..., Vn ( Z))  f̂ ( Z)  min . Аналогичным образом переформулируются и функциональные ограничения: gi (X)  gi (V1(Z),..., Vn (Z))  ĝi (Z)  (, )bi Переформулированная в новых переменных задача примет вид: f̂ ( Z)  min ĝ i ( Z)  (, )bi , i  1, m При этом прямые ограничения из задачи исключаются, так как новые переменные Z  (z1,..., z n ) могут изменяться в любых пределах. В случае, если границы изменения всех варьируемых параметров одинаковы, замена переменных может иметь вид: x j  V(z j ), j  1, n , -   z j   Существует большое количество стандартных функций замены переменных, использующихся для учета прямых ограничений различных видов. Например, ограничения x j  0 могут быть учтены с помощью замены переменных x j  z 2j . Рассмотрим теперь основные подходы к учету функциональных ограничений. Пусть решается задача минимизации целевой функции f(X) с функциональными ограничениями, представленными в виде системы неравенств (3.2) и равенств (3.3): f (X)  min g i (X)  b i , i  1, m (3.2) h j (X)  d j , j  1, r (3.3) Для учета функциональных ограничений обычно используется метод штрафных функций. При этом осуществляется переход от исходной целевой функции f(X) к следующей функции: P(X, )  f (X)    S(X) . Здесь S(X) – штрафная функция (функция штрафа), отличная от нуля вне допустимой области D;   0 – коэффициент штрафа, значение которого может быть постоянным или меняться на различных итерациях. Во втором случае па- 27 раметр  k  0 настраивается в ходе оптимизационного процесса (k – номер итерации). В результате решение задач с ограничениями сводится к решению последовательности задач безусловной оптимизации вспомогательной функции P(X). При этом штрафная функция S(X) формируется таким образом, чтобы при нарушении ограничений задачи производился некоторый “штраф” за их нарушение. При решении задачи минимизации “штраф” заключается в том, что к целевой функции прибавляется некоторое положительное число, “отбрасывая” тем самым оптимизационный процесс от оптимальной точки. Существует два метода построения штрафных функций: - метод внутренних штрафных функций (барьерных функций); - метод внешних штрафных функций. Метод внутренних штрафных функций предназначен для учета только ограничений-неравенств и характеризуется следующей основной функцией штрафа: m 1 . S(X)   g ( X )  b i i 1 i При этом предполагается, что ограничения-равенства (3.3) в задаче отсутствуют. Тогда целевая функция оптимизационной задачи примет вид: m m 1 1 или P(X,  )  f (X)   k   . P ( X,  )  f ( X )     g ( X )  b g ( X )  b i i i 1 i i 1 i При этом параметр  k  0 выбирается таким образом, чтобы его значения стремились к нулю при k   (k – номер итерации). При использовании внутренних штрафных функций поиск оптимума следует начинать с внутренней точки допустимой области, то есть с точки, в которой все ограничения выполнены как строгие неравенства. При выходе на границу допустимой области значение штрафной функции S(X) (штраф) будет бесконечным, следовательно, оптимизационный процесс никогда не выйдет за пределы допустимой области. Недостатком данного метода является то, что он не позволяет решать задачи с ограничениями-равенствами. Кроме того, для их использования необходимо знать начальную допустимую точку. В этой связи более целесообразным является использование внешних штрафных функций. С помощью метода внешних штрафных функций учитываются как ограничения-неравенства g i (X) bi , так и ограничения-равенства h j (X)  d j . Наибольшее распространение получили штрафные функции следующего вида: m r S(X)   (min{0; g i (X)  bi }) 2   (h j (X)  d j ) 2 , i 1 m j1 r S(X)   | min{0; g i (X)  bi } |   h j (X)  d j . i 1 (3.4) j1 (3.5) 28 При этом если ограничения не нарушаются, т. е. g i (X) bi и h j ( X )  d j , то S(X)=0. Если ограничения нарушаются, то величина “штрафа” зависит от степени нарушения ограничения. Может быть использована также комбинированная штрафная функция, в которой ограничения-неравенства учитываются с помощью внешних штрафных функций, а ограничения-равенства – с помощью внутренних (барьерных) функций. m r 1 S(X)     (h j ( X)  d j ) 2 . i 1g i ( x )  b i j1 Таким образом, задачи с ограничениями с помощью замены переменных и методов штрафных функций могут быть преобразованы к задачам безусловной оптимизации. После соответствующих преобразований полученные задачи решаются с использованием методов безусловной оптимизации. Принципы построения и классификация методов безусловной нелинейной оптимизации Рассмотрим задачу безусловной оптимизации: f (X)  f ( x1,..., x n )  min XR n Алгоритмы безусловной оптимизации составляют основу алгоритмического обеспечения, предназначенного для решения оптимизационных задач. Они представляют собой итерационные процедуры, реализующие последовательное приближение к искомому экстремуму: X k 1  X k   k H k , где k – номер итерации, Hk – направление движения на k-й итерации,  k – величина шага в данном направлении. При этом  x k 1   xk  hk   1   1  1 k 1  k k X  ...  , X   ...  , H   ...  .  k 1   k  k  xn   xn  hn        Процесс поиска начинается с некоторой начальной точки X0, которая называется начальным приближением и задается пользователем. Получаемая в процессе поиска последовательность точек X 0 , X1,..., X k называется траекторией поиска и должна сходиться к оптимальной точке X*. Таким образом, алгоритмы безk условной оптимизации различаются по способам выбора направления поиска H и величины шага  k . 29 В зависимости от способа выбора направления поиска методы безусловной оптимизации делятся на методы 0, 1 и 2-го порядка. Методы нулевого порядка – методы, в которых для определения направления поиска используются только значения целевой функции. Производные в данном случае не вычисляются. Этот класс алгоритмов называется еще методами прямого поиска или поисковыми методами оптимизации. К ним относятся метод переменного многогранника и различные алгоритмы покоординатной оптимизации и случайного поиска. Особенностью методов поисковой оптимизации является то, что они могут быть использованы при алгоритмическом задании критериев оптимальности и ограничений. Методы первого порядка – методы, в которых для определения направления поиска используются первые производные целевой функции по управляемым параметрам. Эти методы называют также градиентными. В качестве направления поиска на каждой итерации в них выбирается градиент (в задачах максимизации) или антиградиент (в задачах минимизации) оптимизируемой функции. Методы второго порядка – методы, в которых для определения направления используются вторые производные целевой функции. К этому классу относят метод Ньютона и его модификации. Необходимо заметить, что все рассматриваемые методы являются локальными и способны находить только локальный оптимум. Поисковые методы оптимального выбора Методы оптимизации нулевого порядка (поисковые методы оптимизации) используют в процессе оптимизации только значения целевой функции. Все они являются эвристическими и реализуют различные стратегии направленного перебора. В зависимости от способа выбора направления поиска методы нулевого порядка делятся на следующие основные группы: 1. Методы покоординатной оптимизации. В данных методах поиск осуществляется вдоль координатных направлений. К этому классу относятся: - алгоритм покоординатного спуска с постоянным шагом; - релаксационный метод Гаусса-Зейделя; - метод конфигураций Хука-Дживса; - процедура вращения осей Розенброка; - алгоритм сопряженных направлений Пауэлла. 2. Алгоритмы переменного многогранника. В эту группу входит метод переменного многогранника Нелдера-Мида и его модификации. Методы базируются на стратегии поиска, заключающейся в построении в n-мерном пространстве многогранника из n+1-й вершины и перемещении его в направлении оптимальной точки с помощью трех основных операций: отражения, растяжения и сжатия. 3. Методы случайного поиска. При использовании данных методов направление поиска на каждой итерации выбирается случайным образом. Методы отличаются друг от друга способами генерации случайных векторов, а также стратегиями анализа текущей информации и перестройки шага поиска. Достоинством этой группы методов является возможность определения глобального оптимума, 30 так как использование случайного механизма повышает вероятность выхода поискового процесса из зон локальных экстремумов. Алгоритмы покоординатного поиска В методах покоординатной оптимизации в качестве направлений поиска выбираются координатные оси пространства варьируемых параметров. При этом на каждой k-й итерации выполняется n шагов циклического покоординатного спусk ка из текущей точки X вдоль каждой из n координатных осей. Покоординатный спуск сводится к поочередному изменению переменных вдоль одной из осей: X k 1  X k  ki  ei , i  1 n , где e i – i -й координатный n-мерный вектор, у которого i-й элемент равен 1, а остальные элементы равны 0: 1   0 e1    ...   0 0 0     1   0 e2    … en    , ... ...     0 1 ki – длина шага поиска по i -й переменной на k -ой итерации. Таким образом, в координатной форме шаги циклического спуска имеют следующий вид:  x k 1   1   ...    k 1  xn    xk  1  1    ...   k  ...  ( i=1 – первая координатная ось) , 1  k 0 xn      …  x k 1   x k  0  1   1    ...    ...   kn  ...  ( i=n – n-я координатная ось).  k 1   k  1 xn  xn        Геометрической интерпретацией траектории покоординатного поиска является ломаная, состоящая из отрезков, параллельных осям координат (рис. 4.1). На рис. 3.1 изображены также линии уровня целевой функции двух переменных. Каждая линия уровня соответствует некоторому постоянному значению целевой функции f ( X )  const (в случае большего числа переменных речь идет о поверхностях уровня целевой функции). Таким образом, процесс минимизации заключается в последовательном переходе от одной линии уровня f ( X )  C i к линии уровня с меньшим значением целевой функции f (X)  Ci1 , ( Ci 1  Ci ). 31 Необходимо заметить, что для нелинейной целевой функции линии уровня часто имеют овражный характер. При этом целевая функция сильно меняется по одним направлениям и слабо – по другим. Такие овражные ситуации создают значительные трудности для оптимизации. Рис. 3.1 К простейшим алгоритмам покоординатной оптимизации можно отнести алгоритм покоординатного спуска с постоянным шагом и релаксационный метод Гаусса-Зейделя. Различия между этими двумя алгоритмами заключается в спосоk бе выбора шага поиска  i . Покоординатный спуск с постоянным шагом В этом методе на каждой k-й итерации циклический покоординатный спуск k заключается в следующем. Сначала осуществляется движение из точки X с шаk гом 1 вдоль 1-й координатной оси: X k  k1 e1 . Если это приводит к уменьшению значения целевой функции: f (X k  k1 e1 )  f (X k ) , осуществляется переход в точку X k  k1 e1 . В противном случае производится пробный шаг в противоположном направлении: X k  k1 e1 . В случае уменьшения значения целевой функции осуществляется переход в точку X k  k1 e1 , в противном случае переход в новую точку не производится. Затем рассматривается следующая координатная ось. Аналогичные действия повторяются для всех координатных осей. Если в результате движения вдоль всех координатных осей значение целевой функции не уменьшилось, осуществляется k дробление шага, и циклический покоординатный спуск повторяется из точки X 32 с уменьшенной длиной шага. Итерационный процесс заканчивается, когда длины шагов вдоль координатных направлений уменьшатся до некоторого числа  . Релаксационный алгоритм Гаусса-Зейделя Отличие данного алгоритма от предыдущего заключается в том, что в нем на k каждой k-й итерации определяются оптимальные длины шагов  i , i  1, n в результате решения вспомогательных задач одномерной оптимизации. Эта процедура образует внутренний цикл, в процессе которого осуществляется одномерная минимизация функции f ( x1,..., x n ) по каждой переменной x i , i  1...n : f ( x1k 1 , x k2 ,..., x kn )  min f ( x1 , x k2 ,..., x kn ) , x1 f ( x1k 1, x k2 1,..., x kn )  min f ( x1k 1, x 2 ,..., x kn ) , x2 …. f ( x1k 1, x k2 1,..., x kn 1 )  min f ( x1k 1, x k2 1,..., x n ) . xn Метод конфигураций Хука-Дживса Дальнейшим развитием методов покоординатной оптимизации является метод конфигураций Хука-Дживса. В данном методе этап циклического покоординатного поиска вдоль координатных осей чередуется с этапом экстраполяции, т.е. движения в направлении, соединяющем две перспективные точки X k и X k 1 на двух последовательных шагах (рис. 3.3). Первый этап называется в методе ХукаДживса исследующим поиском вокруг базисной точки, а второй этап – поиском по образцу. Поиск по образцу X k 1* Исследующий поиск X k 1 Xk Рис. 3.3. 33 На этапе исследующего поиска из базисной точки X k осуществляется движение вдоль координатных осей в соответствии с общей схемой покоординатного спуска, в результате чего будет получена точка X k 1 . Если этот этап не приводит к уменьшению значения целевой функции, длина шага уменьшается и исследующий поиск повторяется. Если этап исследующего поиска оказывается успешным, т.е. f (X k 1)  f (X k ) , реализуется этап поиска по образцу. При этом производится движение из точки X k 1 в направлении X k 1  X k , после чего осуществляется исследующий поиск вокруг полученной точки X k 1* . Если полученное при этом значение целевой функции меньше, чем значение в точке X k 1 , поиск по образцу считается удачным. В противном случае (если поиск по образцу неудачен) осуществляется возврат в точку X k 1 и исследующий поиск продолжается вокруг нее. Алгоритм заканчивает работу, когда текущая длина шага становится меньше заданной точности  . Метод вращения осей Розенброка Идея метода состоит во вращении системы координат в соответствии с изменением скорости убывания целевой функции. Новые направления координатных осей определяются таким образом, чтобы одна из них соответствовала направлению наиболее быстрого убывания целевой функции, а остальные находятся из условия ортогональности. Напомним, что линейно независимые векторы p1,...,p n , по норме равные единице, называются взаимно ортогональными, если для всех i, j  1,..., n справедливо условие: piT p j  0, j  i . Работа метода Розенброка проиллюстрирована на рис. 3.4. Из начальной точки X[0] осуществляют спуск в точку X[1] по направлениям, параллельным координатным осям. На следующей итерации одна из осей должна проходить в направлении y1 = X[1] -X[0], а другая – в направлении, перпендикулярном к у1 . В общем случае данный метод эффективен при минимизации овражных функций, так как результирующее направление поиска стремится расположиться вдоль оси оврага. 34 Рис. 3.4. Метод переменного многогранника Нелдера-Мида Метод основан на построении последовательности n+1 точек, которые являются вершинами выпуклого многогранника, и последующем перемещении полученного многогранника в направлении оптимальной точки с помощью трех основных операций: отражения, растяжения и сжатия. В результате многогранники деформируются в зависимости от структуры поверхностей уровня целевой функции. Работа алгоритма заканчивается, когда значения целевой функции в вершинах текущего многогранника отличаются от значения целевой функции в центре тяжести многогранника не больше, чем на  . Основные шаги алгоритма : 1. Задаются исходные данные для работы алгоритма: начальное приближение X1  ( x11 ,..., x1n ) ; требуемая точность  ; длина шага  для построения исходного многогранника; коэффициенты отражения  , растяжения  и сжатия  . 2. Строится многогранник, состоящий из n+1 точек. При этом в качестве первой вер1 шины многогранника выбирается начальная точка X , а остальные вершины формируются по следующей схеме: X i 1  X1  e i , i  1...n После построения многогранника вычисляются значения целевой функции в его вер- шинах: f (X1 ),..., f (X n 1 ) . 3. Осуществляется сортировка значений целевой функции. При этом находится наибольшее значение целевой функции f h , следующее за наибольшим значением функции f g , наименьшее значение функции f m и соответствующие им точки X h , X g и X m . 35 4. Вычисляется центр тяжести Xc всех точек, за исключением X h , 1 Xc   Xi n ih и значение целевой функции в этой точке f (X c )  f c . 5. Процедура отражения. “Наихудшая” точка X h отражается относительно центра тяжести Xc по следующей схеме: X r  X c  ( X c  X h ) , где X r – точка, полученная в результате отражения;   0 - коэффициент отражения (рекомендуемое значение   1 ). Операция отражения иллюстрируется на рис. 3.5. Рис. 3.5 После получения точки X r находится значение целевой функции f r  f (X r ) . 6. Анализ отражения. Сравниваются значения функции f r и f m . 6.1. Если f r  f m , то получено наименьшее значение функции. Направление из точки X c в точку X r является перспективным и делается попытка движения в данном направлении с большим шагом. При этом производится растяжение многогранника по следующей схеме: X e  X c  (X r  X c ) , где Xe – точка, полученная в результате растяжения;   1 - коэффициент растяжения (рекомендуемое значение   2 ). Операция растяжения иллюстрируется на рис. 3.6. Рис. 3.6. 36 После получения точки Xe находится значение целевой функции fe  f (Xe ) . Далее производится анализ растяжения. 6.1.1. Если f e  f m , то этап растяжения признается удачным. “Наихудшая” точка X h заменяется на точку X e , после чего осуществляется переход к шагу 10 (проверка сходимости). 6.1.2. Если fe  f m , точка Xe отбрасывается (этап растяжения признается неудачным). При этом “наихудшая” точка X h заменяется на точку X r , полученную в результате отражения. Далее осуществляется переход к шагу 10. 6.2. Если f m  f r  f g , то точка X r является лучшей точкой по сравнению с двумя “наихудшими” вершинами многогранника. При этом точка X h заменяется на точку X r , после чего осуществляется переход к шагу 10. 6.3. Если f r  f g , то очевидно, что мы переместились слишком далеко от точки X h в направлении Xc . Этап отражения признается неудачным и производится сжатие многогранника (шаг 7). 7. Процедура сжатия. 7.1. Если f r  f h , то процедура сжатия проводится по следующей схеме: X p  X c   (X h  X c ) , где X p – точка, полученная в результате сжатия; 0    1 – коэффициент сжатия (рекомендуемое значение   0.5 ). 7.2. Если f r  f h , то перед сжатием осуществляется замена точки X h на X r , а значения f h на f r . При этом процедура сжатия проводится следующим образом: X p  X c   (X r  X c ) . Обе описанные процедуры иллюстрируются на рис. 3.7. Рис.3.7. После получения точки X p находится значение f p  f (X p ) . 8. Анализ сжатия. Сравниваются значения функция f p и f h . 8.1. Если f p  f h , то процедура сжатия признается удачной. При этом точка X h заменяется точкой X p и осуществляется переход к шагу 10. 37 8.2. Если f p  f h , то очевидно, что все попытки улучшить значение f h закончились неудачей. В данном случае происходит переход к шагу 9. 9. Редукция (усечение) многогранника. На этом шаге осуществляется уменьшение размерности многогранника делением пополам расстояния от каждой точки многогранника до X m – точки, определяющей наименьшее значение функции. i Таким образом, каждая точка X заменяется на точку 1 X i  (X i  X m ) , i  1, m . 2 Затем вычисляются значения f i  f (X i ) для всех i  1...m и осуществляется переход к шагу 10. 10. Проверка сходимости. Она основана на том, чтобы среднее квадратическое отклонение значений функции было меньше некоторого заданного малого значения  . В этом случае вычисляется значение  по формуле : n 1  (f i  f ) 2  i 1 , где f   fi . n 1 n 1 Если    , то все значения функции очень близки друг к другу, и поэтому они, возможно, лежат вблизи точки минимума X* . Если сходимость не достигнута (    ), осуществляется возврат к шагу 3. Градиентные методы оптимизации В методах первого порядка используются первые производные целевой функции f(X). В качестве направления поиска на каждой итерации выбирается градиент целевой функции (в задачах максимизации) или антиградиент (в задачах минимизации) Поэтому эти методы называют также градиентными. Итерационный процесс в градиентных методах реализуется по следующей схеме: X k 1  X k   k f (X k ) (максимизация); (3.6) X k 1  X k   k f (X k ) (минимизация). (3.7) Здесь f (X) – градиент (вектор частных производных) целевой функции:  f (X)     x1  f (X)   ...  .  f (X)   x  n   38 Таким образом, координатной форме градиентная процедура имеет вид (для задачи минимизации): f (X k ) k 1 k , xi  xi  k x i i  1,..., n или  f (X k )     x k 1   x k   x1   1   1  ...    ...    k  ...  .    k 1   k  f (X k )  xn  xn        x n    Градиентные методы различаются в зависимости от способов выбора и корректировки величины шага  k . Существует много различных способов регулировки шага, но наиболее распространены два метода. Первый называется методом с дроблением шага и связан с проверкой на каждой итерации некоторого неравенства, обеспечивающего убывание целевой функции, и уменьшением шага в случае его невыполнения. Второй метод называется методом наискорейшего спуска и обеспечивает выбор на каждой итерации оптимальной длины шага в результате решения вспомогательной задачи одномерной оптимизации. Градиентный метод с дроблением шага В данном методе перед началом поиска пользователем задается начальная величина шага 0 . На каждой итерации проверяется выполнение условия убываk 1 )  f (X k ) . Если данное условие не выполняется, ния целевой функции: f ( X осуществляется дробление шага до тех пор, пока оно не окажется истинным. Для регулировки шага может быть использовано также более жесткое условие: 2 (3.8) f (X k 1 )  f ( X k )   k f (X k ) , где 0    1 - произвольно выбранная константа, неизменная на всех итерациях. Геометрическая интерпретация градиентного метода с дроблением шага представлена на рис. 3.8. Здесь изображены линии уровня целевой функции, причем C1  C2  C3 , и зигзагообразная траектория поиска x 0 , x1, x 2 ...x k . В качестве направления поиска в каждой точке x k выбирается направление антиградиента, ортогональное касательной к линии уровня целевой функции в этой точке. 39 Рис. 3.8. Очевидно, что сходимость градиентных методов наиболее высока, когда линии уровня целевой функции имеют вид концентрических окружностей. Метод наискорейшего спуска В методе наискорейшего спуска на каждой итерации определяется оптимальная длина шага в результате решения вспомогательной задачи одномерной оптимизации min f (X k  f (X k )) .  0 Таким образом, этап градиентного метода (переход в новую точку поиска) чередуется с этапом определения оптимальной длины шага. Геометрическая интерпретация метода наискорейшего спуска представлена на рис. 3.9. В этом методе, в отличие от обычного градиентного спуска, направле- ние движения из точки X k касается линии уровня в точке X k 1 . Последовательность точек X 0 , X1,..., X k зигзагообразно приближается к точке минимума X * , причем звенья этого ломаной ортогональны между собой. Действительно, шаг  выбирается из условия минимизации по  функции ()  f (X k  f (X k ) . Поэтому должно выполняться условие: d( k )  f (X k 1 )f (X k )  0 . d Таким образом, направления поиска на двух последовательных итерациях ортогональны между собой. 40 Рис. 3.9 Метод наискорейшего спуска является более эффективным, чем градиентные методы с дроблением шага, так как обеспечивает движение с оптимальной длиной шага. Однако он является также и более трудоемким, так как его реализация предполагает решение на каждой итерации довольно трудоемкой вспомогательной задачи одномерной минимизации. Методы второго порядка Методы второго порядка используют в процессе поиска вторые производные целевой функции. К этому классу относят метод Ньютона и его модификации. Основная стратегия данных методов заключается в следующем: X k 1  X k   k [ 2 f (X k )]1 f (X k ) , (3.9) где f (X k ) – градиент целевой функции f(X) в точке Xk, [ 2 f (X k )]  G (X k ) – матрица вторых производных (матрица Гессе) целевой функции f(X) в точке Xk. Методы данного класса отличаются друг от друга способами выбора и настройки шага  k . Метод Ньютона В методе Ньютона величина шага на каждой итерации выбирается равной единице:  k  1 . Итерационная схема поиска в данном случае имеет вид: X k 1  X k  [ 2 f (X k )]1 f (X k ) или X k 1  X k  G 1 (X k )f (X k ) . Основная сложность реализации метода Ньютона заключается в необходимости обращения матрицы Гессе, так как процедура вычисления обратной матрицы является достаточно трудоемкой. Поэтому на практике часто используется подход, при котором направление поиска H k 1  G 1 (X k )f (X k ) 41 определяется в результате решения системы линейных уравнений: G (X k )H k 1  f (X k ) . k После определения направления поиска H новая ночка находится по схеме: X k 1  X k  H k . Метод Ньютона-Рафсона Метод Ньютона-Рафсона отличается от метода Ньютона тем, что в нем шаг поиска не выбирается равным единице на всех итерациях, а настраивается в ходе оптимизационного процесса. Итерационная схема поиска имеет вид: X k 1  X k   k G 1 (X k )f (X k ) . Методы с регулировкой шага сходятся независимо от начального приближения. На практике обычно используются два способа выбора длины шага. Первый из них связан с проверкой неравенства, аналогичного неравенству (4.8): f (X k 1 )  f (X k )   k (f (X k ), H k ) , где H k  G 1 (X k )f (X k ) - направление поиска на k-й итерации; 0    1 - не2 которая константа, неизменная на всех итерациях. Если это неравенство выполняется при  k  1 , то шаг принимается равным единице и осуществляется следующая итерация. В противном случае шаг дробится до тех пор, пока неравенство не выполнится. В случае, если проверка данного неравенства оказывается слишком трудоемкой, может быть использовано упрощенное условие: f (X k 1 )  f (X k ) . Второй способ определения длины шага, как и в методе наискорейшего спуска, состоит определении на каждой итерации оптимальной длины шага в результате решения задачи одномерной минимизации: min f (X k  G 1 (X k )f (X k )) .  При этом этап перехода в новую точку поиска чередуется с этапом определения оптимальной длины шага. 42 ТЕМА 4. МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ Лекции 6,7 Постановка задач дискретной оптимизации, основные приёмы преобразования моделей Задачей дискретной оптимизации называется задача оптимизации, в которой на варьируемые параметры наложено требование дискретности: f (X)  min(max) g i (X)  (, )bi , x j  D j, i  1, m (4.1) j  1, n, где D j – множество допустимых значений каждого параметра x j . При этом предполагается, что хотя бы один параметр x j может принимать дискретные значения. Классификация задач дискретной оптимизации 1. В зависимости от вида целевой функции и ограничений задачи дискретной оптимизации делятся на линейные и нелинейные. Наиболее изученным в настоящее время является класс линейных задач дискретной оптимизации. 2. В зависимости от характера изменения варьируемых параметров различают задачи: - полностью дискретные; - частично дискретные (дискретно-непрерывные); - целочисленные задачи; - задачи с булевыми переменными. При этом если целевая функция принимает действительные значения, то задачи оптимизации с булевыми переменными называют задачами псевдобулевой оптимизации. 3. В зависимости от физического смысла варьируемых параметров выделяются следующие классы задач: 3.1. Задачи с неделимостями, в которых переменные представляют собой физические неделимые величины (например, количество выпускаемых изделий). К ним относятся все рассмотренные выше задачи оптимизации, в которых на переменные дополнительно наложены условия целочисленности. 3.2. Задачи с альтернативными переменными (или с логическими условиями). В этих задачах вводятся альтернативные переменные, отражающие логические условия задачи. Как правило, к этому классу относятся задачи булевой оптимизации. 43 Наиболее распространенными являются задачи целочисленной (в частности, булевой) оптимизации, так как любую дискретную задачу с помощью дополнительных преобразований можно привести к целочисленной. Такое преобразование может быть произведено, например, следующим образом. Пусть x j  {q1j , ... , q mj} , где {q1 j , ... , q mj} – дискретный ряд значений переменной x j . Введем бинарную переменную y ij , принимающую значения 0, 1 и представим каждую переменную x j следующим образом: m x j   q ij y ij при условиях: i 1 m  yij  1, yij  {0, 1} . i 1 Таким образом, можно перейти от произвольных дискретных переменных к бинарным переменным, которые являются частным случаем целочисленных переменных. Поэтому в дальнейшем будем рассматривать задачи целочисленной оптимизации. Прикладные дискретные модели Задача о ранце Имеются предметы n видов, причем для каждого предмета j-го вида (j=1,n) известны его объем a j  0 и стоимость c j  0 . Необходимо определить такой набор предметов, суммарный объем которых не превышал бы заданного числа b, а суммарная ценность была бы максимальной. Эта задача интерпретируется как задача загрузки ранца объема b и называется одномерной задачей о ранце. Введем целочисленные переменные x j ( j  1, n ) , значения которых характеризует количество предметов j-го вида, помещенных в ранец. Тогда математическая модель данной задачи имеет вид: n  c j x j  max; j1 n  a j x j  b; j1 x j  0, j  1, n , x j - целые . Если ограничениями могут быть не только объем ранца, но и другие его характеристики b i , то получим многомерную задачу о ранце: 44 n  c j x j  max; j1 n  a ij x j  b i ,i  1, m; j1 x j  0, j  1, n, x j - целые В случае, если количество предметов j-го вида ограничено и равно d j , к задаче добавляется ограничение x j  d j . Если d j =1, то получим задачу о ранце с булевыми переменными. Тогда x j  {0,1} , причем x j  1 , если j-й предмет помещен в ранец, x j  0 в противном случае. К задаче о ранце сводится широкий класс задач дискретной оптимизации с ограниченными ресурсами. Пример. Для оценки работоспособности систем перед эксплуатацией производится проверка их функционирования. При проверке контролируются отдельные параметры системы, каждый из которых характеризуется вероятностью отказа проверяемых элементов q j и временем контроля t j . Так как допустимое время контроля всей системы T ограничено, то для проверки необходимо выбрать параметры, контролирующие наиболее ненадежные элементы и требующие для контроля наименьшего времени. Пусть n – общее количество параметров. Введем альтернативные бинарные переменные: 1, если выбирается j - й параметр xj   в противном случае  0 Тогда математическую модель задачи можно сформулировать как одномерную задачу о ранце: n  q jx j  max; j1 n  t jx j  T; j1 x j  {0,1}. Задача о назначениях Имеется n исполнителей и n видов работ, которые они могут выполнять. Пусть c ij – производительность i-го исполнителя при выполнении j работы. Каждый исполнитель может выполнять один вид работ, а каждый вид работ может быть выполнен одним исполнителем. Требуется таким образом распределить ис- 45 полнителей по видам работ, чтобы общая производительность была максимальной. Введем альтернативные переменные x ij : 1, если i - й исполнитель назначается на j - ю работу x ij    0 в противном случае Тогда математическая модель задачи имеет вид: n n   cijx ij  max; i 1 j1 n  x ij  1,i  1, n; j1 n  x ij  1, j  1, n; i 1 x ij  {0,1}. Иногда линейная задача о назначениях формулируется как задача минимизации, если в качестве c ij выбирается время, затраченное i-м исполнителем на выполнение j-й работы. Необходимо заметить, что условие целочисленности переменных в задаче о назначениях можно не накладывать, т. к. эта задача является частным случаем транспортной задачи, и при целочисленности правых частей ограничений целочисленность решения обеспечивается автоматически. К задаче о назначениях сводится широкий круг задач дискретной оптимизации (распределение исполнителей по видам работ, закрепление за станками операций, распределение задач между различными ЭВМ, назначение претендентов на вакантные должности при формировании штатного расписания и т. д). Пример. При передаче сообщений по каналу с шумом необходимо каждой букве передаваемого алфавита поставить в соответствие букву принимаемого таким образом, чтобы сумма вероятностей правильности принимаемых букв была бы максимальна. Пусть p ij – вероятность соответствия принимаемой j-й буквы передаваемой iй букве. Введем альтернативные переменные: 1, если j - я принимаемая буква соответствует i - й передаваемой x ij   случае  0 в противном Тогда математическая модель будет иметь следующий вид: 46 n n   p ijx ij  max; i 1 j1 n  x ij  1,i  1, n; j1 n  x ij  1, j  1, n; i 1 x ij  {0,1}. Задача о покрытии Пусть имеется n предметов, каждый из которых обладает некоторым числом признаков из заданного множества m признаков, а в совокупности эти n предметов обладают всеми m признаками. Необходимо выбрать минимальное число предметов, которые в совокупности обладали бы m признаками. Условия задачи задаются матрицей A с элементами 1, если j - й предмет обладает i - м признаком a ij   в противном случае  Введем бинарные переменные: 1, если j - й предмет выбран xj    0 в противном случае Тогда математическая модель задачи имеет следующий вид: n  x j  min; j1 n  a ijx j  1,i  1, m; j1 x j  {0,1}, j  1, n Каждое i-е ограничение в данном случае показывает, что должен быть выбран хотя бы один предмет, обладающий i-м признаком. Если каждому j-му предмету приписывается вес c j , может быть сформулирована взвешенная задача о покрытии: 47 n  c jx j  min j1 n  a ijx j  1, i  1, m, j1 x j  {0,1}, j  1, n Пример. Пусть некоторое количество информации хранится в n массивах (файлах) длины c j , j  1, n , причем на каждую единицу информации отводится по крайней мере один массив. Задана матрица T с элементами 1, если в j - м массиве находится i - я информация t ij    0 в противном случае Получена заявка на m типов единиц информации. Необходимо определить подмножество массивов минимальной длины, необходимых для удовлетворения заявки. Введем бинарные переменные: 1, если j - й массив выбирается xj    0 в противном случае Модель задачи формализуется в виде задачи о покрытии: n  cijx j  min; j1 n  t ijx j  1, i  1, m; j1 x j  {1,0}, j  1, n Задача о разбиении Задача о разбиении аналогична задачи о покрытии с тем отличием, что признаки у различных предметов не должны совпадать: n  x j  min; j1 n  a ijx j  1,i  1, m; j1 x j  {1,0}, j  1, n Задача о взвешенном разбиении формулируется в виде: 48 n  c jx j  min; j1 n  a ijx j  1,i  1, m; j1 x j  {1,0}, j  1, n Методы решения задач дискретной оптимизации Методы решения задач дискретной оптимизации делятся на следующие основные группы: - методы отсечений (предназначены для решения только линейных целочисленных и частично целочисленных задач); - комбинаторные методы; - приближенные методы. Метод отсечений Гомори Рассмотрим задачу целочисленной линейной оптимизации: n F   c jx j  min j1 n  a ijx j  bi , i  1, m j1 (4.2) x j  0 , j  1, n x j  целые , j  1, k Если все переменные задачи должны принимать целочисленные значения (k = n), задача называется полностью целочисленной. Если требование целочисленности предъявляется не ко всем переменным (k < n), задача называется частично целочисленной. Обозначим задачу (4.2) через Z, а область ее допустимых решений D z . Обозначим задачу (4.2) без учета условий целочисленности через P, а ее допустимую область D. Оптимальное решение целочисленной задачи будем обозначать X*z , оптимальное решение соответствующей непрерывной задачи P обозначим X* . Область Dz представляет собой дискретное множество точек с целочисленными координатами, которые принадлежат D: D z  D (рис. 5.1). 49 A B C E Рис. 4.1 Задачи Z и P характеризуются следующими свойствами: 1. Минимальное значение целевой функции в задаче Z не превышает минимального значения этой же целевой функции в задаче P: F(X *Z )  F(X * ) . Таким образом, значение целевой функции в точке непрерывного оптимума является нижней границей значения целевой функции в точке дискретного оптимума. 2. Если оптимальное решение задачи P оказывается целочисленным, то оно является оптимальным решением задачи Z. 3. Если не имеет решений задача Р, то не имеет решений и соответствующая целочисленная задача Z. Решение задач целочисленной линейной оптимизации с использованием метода отсечений сводится к решению специальным образом построенных задач линейной оптимизации: P0 , P1 ,…, Ps. Первая задача P0 образуется из исходной задачи целочисленной оптимизации Z путем отбрасывания ограничений целочисленности переменных. Каждая последующая задача P1 ,…, Ps получается из предыдущей путем добавления к ее условиям дополнительного линейного ограничения-неравенства, называемого правильным отсечением (или сечением). При этом r-м сечением называется линейное ограничение, вводимое в задачу Pr-1 и соответствующее следующим двум условиям: 1. Любое целочисленное решение задачи Pr-1 ему удовлетворяет. 2. Хотя бы одно из нецелочисленных решений задачи Pr-1 ему не удовлетворяет (отсекается). Таким образом, к исходной задаче P0 последовательно добавляются дополнительные ограничения (отсечения), не исключающее целочисленных допустимых точек и отсекающие нецелочисленные решения решаемой задачи целочисленной оптимизации (рис. 4.2). 3-е отсечение A 1 opt B 2 opt 1-е отсечение C 3 opt E 2-е отсечение Рис. 4.2 50 Методы отсечения различаются между собой способами формирования дополнительных ограничений. Наиболее распространенным является метод отсечения Гомори. Пусть задача Pr-1 решена симплексным методом и ее решение не удовлетворяет условиям целочисленности. Введем обозначения: [a] – целая часть числа a, т.е. наибольшее целое число, не превосходящее a; {a} = a-[a] – дробная часть числа a; Bas – множество индексов базисных переменных из последней симплекстаблицы; S – номер строки из последней симплексной таблицы, которой соответствует переменная с наибольшей дробной частью из оптимального решения. При определении данного номера S в столбце правых частей ограничений выбирается наибольшее значение {bS}. Тогда сечение Гомори для решения полностью целочисленной задачи запишется в виде:  {a Sj }x j  {bS } jBas Основные шаги метода Гомори: 1. Определяется оптимальное решение задачи (4.2) без учета условий целочисленности. При этом ограничения на целочисленность переменных отбрасываются, и задача решается обычным симплекс-методом. 2. Если полученное решение является целочисленным, работа алгоритма заканчивается (оптимальное решение найдено), в противном случае осуществляется переход к шагу 3. 3. На основании последней симплекс-таблицы, полученной при решении ЗЛП, формируется сечение Гомори (I или II). 4. Дополнительное ограничение, построенное на предыдущем этапе, добавляется к условиям решаемой задачи. Для этого данное ограничение преобразуется в уравнение  {a Sj }x j  x d  {bS } (для I сечения) j Bas   Sj x j  x d  {bS } (для II сечения), j Bas где x d – дополнительная неотрицательная переменная. Затем полученное уравнение умножается на –1   {a Sj }x j  x d  {bS } (для I сечения) j Bas    Sj x j  x d  {bS} (для II сечения) j Bas 51 и добавляется к последней симплекс-таблице. Далее полученная задача решается двойственным симплекс-методом. 5. Переход к шагу 1. Пример. Решить задачу целочисленной линейной оптимизации методом Гомори:  x1  4 x 2  min  x1  2 x 2  x 3  2  3x1  2 x 2  x 4  6 x1, x 2 , x 3 , x 4  0 x1, x 2 , x 3 , x 4 целые. Решение. Решаем данную задачу симплекс-методом без учета условий целочисленности . -1 -4 cБ xБ B x1 x2 x3 x4 x3 2 -1 1 2 x4 6 3 2 1 0 1 4 x2 -4 1 -1/2 1 1/2 x4 4 -1 1 4 -4 3 -2 x2 -4 3/2 1 3/8 1/8 x1 -1 1 1 -1/4 1/4 -7 0 -5/4 -3/4 Полученное решение ( x1*  1; x *2  3 / 2; x *3  0; x *4  0 ) не является целочисленным. Поэтому переходим к построению дополнительного ограничения. Для этого необходимо выбрать ту строку таблицы, которой соответствует переменная с наибольшей дробной частью. В данном случае единственной такой строкой является первая строка (S = 1). Записываем первое сечение Гомори: 1 1  3 1   3  или 3 x  x  x  x    3   4   3 4 8 8 2 8  8  2 Умножив левую и правую часть на 2, получим: 3 1 x1  x 4  1 4 4 52 Введем в левую часть дополнительную переменную x5 и умножим полученное равенство на (–1). В результате будем иметь следующее равенство: 3 1  x 3  x 4  x 5  1 4 4 Добавим полученное ограничение к последней симплекс-таблице и решим полученную задачу с использованием двойственного симплекс-метода xБ cБ B x2 x1 x5 -4 -1 x2 x1 x3 -4 -1 3/2 1 -1 -7 1 4/3 4/3 -16/3 -1 x1 1 1 -4 x2 1 1 x3 3/8 -1/4 -3/4 -5/4 1 x4 1/8 1/4 -1/4 -3/4 1/3 1/3 -1/3 x5 1 ½ -1/3 -4/3 -5/3 В результате получено следующее оптимальное решение: x1*  4 / 3; x *2  1; x *3  4 / 3; x *4  0 Полученное решение не является целочисленным, поэтому опять переходим к построению сечения Гомори. Так как значения дробных частей у переменных x1 и x 3 одинаковы, строку для построения дополнительного ограничения выбираем произвольно (например, S = 2). Тогда ограничение записывается в виде 1 2 1 1   1 4  x 4   x 5    или x 4  x 5  3 3 3 3  3 3 После соответствующих преобразований получим  x 4  2x 5  x 6  1 Добавим данное ограничение к последней симплекс-таблице и решим полученную задачу двойственным симплекс-методом xБ cБ B x2 x1 x3 x6 -4 -1 x2 x1 x3 x4 -4 -1 1 4/3 4/3 -1 -16/3 1 1 1 1 -5 -1 x1 1 1 -4 x2 1 1 x3 1 1 x4 1/3 1/3 -1 -1/3 1 x5 1/2 -1/3 -4/3 -2 -5/3 -1/2 -1 -6 2 -1 x6 1 1/3 1/3 -1 -1/3 53 Полученное целочисленное решение является оптимальным решением исходной задачи: x1*  1; x*2  1; x*3  1; x*4  1 . Метод ветвей и границ Метод ветвей и границ относится к комбинаторным методам решения задач дискретной оптимизации и может использоваться для решения как линейных, так и нелинейных задач. Он основан на использовании конечности множества допустимых вариантов и замене полного перебора сокращенным направленным перебором. При этом полного перебора удается избежать за счет отбрасывания неперспективных множеств вариантов, т. е. тех множеств, где заведомо нет оптимального решения. В методе ветвей и границ все множество допустимых вариантов последовательно делится на все меньшие подмножества. При этом вычисляются оценки (границы), которые позволяют сделать вывод о том, какое из полученных подмножеств может быть отброшено при условии сохранения подмножества, содержащего оптимальное решение. Для иллюстрации работы метода ветвей и границ используется дерево, называемое деревом перебора или деревом вариантов (рис. 5.3). Каждой вершине дерева вариантов соответствует какая-либо подзадача Z i исходной задачи Z. Z Z1 Z3 Z2 Z4 Рис. 4.3 Перед рассмотрением метода ветвей и границ введем некоторые определения. 1. Для задачи min f (X) подзадачами будем называть задачи следующего виXD ~ да: min~ f (X) , где D  D . Таким образом, подзадача – это задача с той же целеXD вой функцией f (X) , но с меньшей допустимой областью, которая входит в исходную область D. Так как при сужении допустимой области результат решения задачи ухудшается, то в общем случае выполняется следующее соотношение между оптимальными решениями исходной задачи и ее подзадач: min f (X)  min~ f (X) . XD XD 54 2. Релаксациией задачи (или подзадачи) будем называть переход от задачи min f (X ) к задаче с той же целевой функцией, но с некоторой допустимой обXD ластью D  , включающей исходную область D в качестве подмножества: min f ( X ) , где D  D (одним из примеров релаксации является, в частности, XD отбрасывание условий целочисленности в задаче целочисленной оптимизации). Таким образом, при релаксации задачи происходит расширение ее допустимой области. Поэтому выполняется следующее соотношение между оптимальными решениями исходной задачи и ее релаксации: min f (X)  min f (X) . XD XD Таким образом, оптимальное решение задачи min f (X) будет являться нижXD ней границей оптимального решения исходной задачи. 3. Ветвлением будем называть разбиение допустимой области на непересекающиеся подмножества и получение таким образом новых оптимизационных подзадач. При этом каждой подзадаче будет соответствовать вершина дерева вариантов. 4. Нижней оценкой (нижней границей)  i оптимального значения целевой функции в вершине i будем называть оптимальное решение задачи, полученной в результате релаксации подзадачи Zi . 5. Верхней оценкой (верхней границей)  i оптимального решения в вершине i будем называть значение целевой функции, обеспечиваемое некоторым допустимым решением подзадачи Zi (например, для задачи целочисленной оптимизации это целочисленное допустимое решение). 6. Значение минимальной верхней оценки в вершинах дерева вариантов называется рекордом. 7. Прозондированные вершины – это вершины дерева вариантов, в которых дальнейшее ветвление невозможно или нецелесообразно. Пусть решается задача целочисленной минимизации целевой функции min f (X) , которую в дальнейшем обозначим Z. При этом D z – область допу- XD z стимых решений исходной задачи, включающая условия целочисленности переменных. Рассмотрим основные этапы метода ветвей и границ при решении данной задачи. 1. Вычисление нижней оценки оптимального решения исходной задачи Z. С этой целью осуществляется релаксация задачи Z (например, в результате отбрасывания условий целочисленности) и формируется расширенная допустимая область D. Построенная задача решается с использованием одного из методов непрерывной оптимизации (например, с использованием симплекс-метода при ли- 55 нейности целевой функции и ограничений), после чего осуществляется анализ * полученного результата X . 1.1. Если оптимальное решение X* целочисленное, то оно является оптимальным решением исходной задачи Z. 1.2. Если X * нецелочисленное, то необходимо продолжить решение. При * этом  Z  f ( X ) – нижняя граница оптимального целочисленного решения исходной задачи. 2. Ветвление, т. е. разбиение области допустимых решений D z исходной задачи Z на два подмножества: D z и D z . При этом исходная задача Z разбива1 2 ется на две подзадачи: Z1 и Z2. Для организации ветвления может быть использована следующая схема. * Пусть x j – какая-либо нецелочисленная переменная из полученного на преды* дущем этапе оптимального решения X . При этом область D z формируется 1 путем добавления к области D z следующего дополнительного ограничения: x j  [ x *j ] , где [ x *j ] – целая часть числа x *j . Область D z образуется путем добавления к D z ограничения: 2 x j  [ x *j ]  1 . При этом формируется задача Z1 с допустимой областью D z1 и задача Z2 с допустимой областью D z . 2 3. Вычисление нижних оценок  z и  z для подзадач Z1 и Z2. Для этого 1 2 осуществляется релаксация подзадач Z1 и Z2 и их решение. При этом  z1  f ( X1* ) ,  z 2  f ( X *2 ) , где X1* и X *2 – оптимальные решения полученных задач. Если какая-либо из подзадач не имеет решения, ее нижняя оценка считается равной бесконечности. 4. Из двух подзадач Z1 и Z2 выбирается подзадача для дальнейшего ветвления. 5. Ветвление выбранной подзадачи (аналогично п. 2). После ветвления снова вычисляются нижние оценки для полученных подзадач и т. д. Процесс ветвления продолжается до получения целочисленного оптимального решения для одной из подзадач, например Zk. При этом значение целевой функции на полученном целочисленном решении задачи Z k представляет собой верх* нюю границу оптимального решения:  z  f ( X k ) . Минимальная из полученk ных верхних границ будет являться рекордом. После получения верхних границ определяются прозондированные вершины. Вершина является прозондированной, если она удовлетворяет одному из следующих условий: 1) оптимальное решение в этой вершине целочисленно; 56 2) значение нижней границы в этой вершине больше текущего значения рекорда (дальнейшее ветвление этой вершины нецелесообразно, так как в процессе ветвления значение целевой функции будет только увеличиваться); 3) подзадача, соответствующая данной вершине, не имеет допустимых решений. При этом в случаях 2) и 3) прозондированные вершины отбрасываются. Процесс продолжается до тех пор, пока все вершины не будут прозондированы. Прозондированная вершина, соответствующая целочисленному решению с наилучшим значением целевой функции, определяет оптимальное решение исходной задачи. Пример. Для иллюстрации основных принципов метода ветвей и границ рассмотрим следующую задачу целочисленной линейной оптимизации:  7 x1  3x 2  min 5x1  2x 2  20 8x1  4x 2  38 x1 , x 2  0, x1 , x 2  целочисленные Начальный шаг решения этой задачи методом ветвей и границ состоит в нахождении решения задачи линейного программирования, получаемой при отбрасывании условий целочисленности x1 и x2. Обозначим эту задачу через ЛП-1. Решим задачу ЛП-1 с использованием симплекс-метода. Ее оптимальное решение * * имеет вид: x1  1; x 2  7.5 , оптимальное значение целевой функции f1=-29.5. Найденное значение f1 представляет собой нижнюю границу истинного оптимального целочисленного значения, поскольку при выполнении требования целочисленности x2 значение оптимальное значений целевой функции может лишь увеличиться. Следующий шаг метода ветвей и границ состоит в разбиении задачи ЛП-1 на две подзадачи, первая из которых (ЛП-2) образуется в результате добавления к задаче ЛП-1 ограничения x 2  7 , а вторая (ЛП-3) – в результате добавления ограничения x 2  8 . ЛП-2 ЛП-3  7 x1  3x 2  min  7 x1  3x 2  min 5x1  2x 2  20 5x1  2x 2  20 8x1  4x 2  38 8x1  4x 2  38 x 2  7(новое ограничение) x 2  8(новое ограничение) x1 , x 2  0 x1 , x 2  0 57 * * Оптимальное решение задачи ЛП-3: x1  0.75; x 2  8 , где * * тимальное решение задачи ЛП-2: x1  1.2; x 2  7 , где f3=-29.4. Дерево возможных вариантов представлено на рис. 4.4. f2=-29.25. Оп- X1=1 X2=7.5 Z2=-29.5 ЛП-1 X2 7 X1=1.2 X2=7 Z2=-29.4 ЛП-2 X11 ЛП-4 X28 ЛП-3 X1=0.75 X2=8 Z2=-29.25 X12 X1=1 X2=7 Z4=-28 ЛП-5 X1=2 X2=7 Z5=-29 Рис. 4.4. Для дальнейшего ветвления выберем задачу ЛП-2, т.к. значение целевой функции в ней меньше. К задаче ЛП-2 добавим ограничения x 1  1 , (задача ЛП-4) * * и x1  2 (задача ЛП-5). Результаты решения задачи ЛП-4: x1  1; x 2  7 , где * * f4=-28. Результаты решения задачи ЛП-5: x1  2; x 2  5 , где f5=-29. Таким образом, получены два допустимых (целочисленных) решения исходной задачи целочисленного программирования, которые представляют собой верхние границы оптимального решения, причем значение f5=-29 будет являться рекордом. Даже если исходная задача имеет другие целочисленные решения, значение целевой функции в них не может быть больше -29. Вершины ЛП-4 и ЛП-5 являются прозондированными (так как в них получено целочисленное решение, а в процессе дальнейшего ветвления оно может лишь ухудшаться). Ветвление вершины ЛП-3 также нецелесообразно в связи с тем, что целевая функция исходной задачи может принимать только целочисленные значения (т. к. все переменные и коэффициенты целочисленны), а при дальнейшем ветвлении ее значения будут увеличиваться (т. е., станут больше -29). Следовательно, оптимальное решение задачи: x1*  2; x *2  5 , где f ( x1* , x*2 )  29 . 58 Основные стратегии метода ветвей и границ В рамках обобщенной схемы ветвей и границ может быть построен широкий класс алгоритмов, отличающихся друг от друга способами реализации отдельных шагов. Эффективность конкретного алгоритма в рамках данного класса зависит от выбранной стратегии его формирования для рассматриваемой задачи. Рассмотрим некоторые стратегии реализации различных этапов метода ветвей и границ. 1. Выбор вершины (подзадачи) для ветвления (этап 4). При этом возможны следующие стратегии: - выбирается вершина с минимальной нижней оценкой; - поиск в глубину: всегда выбирается одна из новых, только что полученных подзадач (стратегия LIFO); - поиск в ширину (стратегия FIFO); - вершина для ветвления выбирается случайным образом. 2. Выбор нецелочисленной переменной, по которой осуществляется ветвление (этап 2). Используются следующие стратегии реализации данного этапа: - выбирается переменная с максимальной дробной частью; - переменным присваиваются приоритеты и осуществляется выбор переменной с наибольшим приоритетом (данная переменная играет более важную роль в модели по мнению разработчиков); - переменная для ветвления выбирается произвольным образом, например, переменная с наименьшим номером. 3. Вычисление нижних оценок. Самым простым способом вычисления нижних оценок является отбрасывание условий целочисленности и дальнейшее использование какого-либо метода непрерывной оптимизации (если задача линейная, может использоваться симплекс-метод, если нелинейная – соответствующие нелинейные методы и т. д.). Этот способ позволяет получать достаточно точные значения нижних оценок, однако является достаточно трудоемким. Поэтому на практике часто используются приближенные эвристические процедуры определения оценок, трудоемкость и время вычисления которых значительно ниже. Для задач целочисленной оптимизации специального вида (задачи коммивояжера, задачи о ранце, задачи о покрытии) разработаны специальные методы вычисления нижних границ, учитывающие специфику этих задач. 4. Вычисление верхних оценок. При этом возможны следующие варианты: - верхние оценки специально не вычисляются, а определяются в процессе решения задачи при получении целочисленного результата для одной из вершин; - верхние границы вычисляются перед началом работы алгоритма с помощью какой-либо эвристической процедуры. - вычисление верхних границ с помощью эвристических процедур осуществляется на каждом шаге работы алгоритма (для каждой подзадачи). Последние два способа требуют дополнительных вычислительных затрат, но позволяет более эффективно сокращать перебор. 59 ТЕМА 5. ОСНОВЫ ТЕОРИИ ПРИНЯТИЯ РЕШЕНИЙ Лекции 8,9 Постановка и формальная модель задачи принятия решений Задача принятия решений направлена на определения наилучшего (оптимального) действия для достижения поставленных целей. Под целью понимается идеальное представление желаемого результата. Если фактическое состояние не соответствует желаемому, имеет место проблема. Выработка плана действий по решению проблемы составляет сущность задачи принятия решений. Решение – это выбор определённого сочетания цели, действий, направленных на достижение этой цели, и способов использования имеющихся ресурсов. С технической точки зрения решение – это результат анализа, прогнозирования, оптимизации и выбора альтернативы из множества вариантов достижения конкретной цели. В узком смысле принятие решений – это заключительный акт анализа вариантов, результат выбора. В широком смысле – это процесс, протекающий во времени. Это совокупность всех этапов и стадий по подготовке решения, включая этап непосредственного принятия решения. Субъектом принятия решений является лицо, принимающее решение (ЛПР). Для помощи ЛПР в сборе, анализе информации и формировании решений привлекаются эксперты – специалисты в данной предметной области. Процесс принятия решений может быть укрупненно подразделен на 2 операции: выработка рекомендаций специалистами по выбору лучшего варианта и принятие окончательного варианта непосредственно лицом, принимающим решение (ЛПР). Для ЛПР задача принятия решений может быть записана в следующем виде: <С, Т, Р | Сд, П, Ц, О, А, К, f, А*>, где С – исходная проблемная ситуация; Т – время для принятия решения; Р – потребные ресурсы для принятия решения; Сд – доопределенная проблемная ситуация; П = (П1,…, Пn) – множество предположений о развитии ситуации в будущем; Ц = (Ц1,…, Цk) – множество целей, на достижение которых направлено решение; О = (О1,…, Оl) – множество ограничений; А = (А1,…, Аm) – множество альтернативных вариантов решений; К = (К1,…, Кр) – множество критериев выбора наилучшего варианта; f – функция предпочтения ЛПР (включает объективные критерии К и личные предпочтения ЛПР); А*- оптимальное решение. Рассмотрим более подробно элементы задачи принятия решений. Под проблемой в теории принятия решений понимается разница между фактическим и желаемым состоянием объекта принятия решений. Проблема – неудовлетворительное состояние системы или противоречие, требующее разрешения. Проблема всегда связана с определенными условиями и 60 причинами ее возникновения, которые обобщенно называют ситуацией. Совокупные проблемы и ситуации образуют проблемную ситуацию. Проблемная ситуация формулируется как логическое высказывание, в том числе содержащее неопределенность и нечеткость относительно и целевых параметров, и условий внешней и внутренней среды. В зависимости от того, какая часть целей и условий не определена, возможна дальнейшая структуризация проблемной ситуации. После снятия неопределенности может быть сформулирована управленческая задача. Исходная проблемная ситуация содержательна и, если это возможно, обладает совокупностью количественных характеристик. Время Т влияет на возможность получения полной достоверной информации о проблемной ситуации, обоснования вариантов и определения последствий их реализации. В качестве ресурсов для нахождения оптимального решения могут служить знания и опыт людей, научно-технический и информационный потенциал организации, финансы, и т.д. На начальной стадии проблемная ситуация может быть определена не полностью, что связано с неполнотой информации, недостаточной аналитической проработкой. В таких условиях проблемная ситуация доопределяется до уровня, достаточного для действий по принятию решений (Сд). Множество предположений (гипотез) П о развитии ситуации в будущем характеризует неопределенность многих факторов и внешних и внутренних условий и реализации принимаемого решения. Для формирования целей и выбора варианта решения необходимо ориентироваться на определенный вариант развития ситуации. Возможна подготовка вариантов решений для различных предположений о развитии ситуации в будущем. Для четкого определения вариантов устранения проблемной ситуации необходимо сформулировать множество целей Ц. Реальные задачи, как правило, многоцелевые, кроме того, даже единственная цель может быть разбита на подцели. Цель – это главный системообразующий фактор в любой социальноэкономической системе. Правильно поставленная цель становится инструментом решения проблемы. Цель – это состояние объекта управления, к достижению которого стремится система. Реализация решений всегда осуществляется в условиях различных ограничений: финансовых, кадровых, правовых. Поэтому необходимо четко сформулировать множество ограничений, которые должны учитываться при принятии решения в конкретной проблемной ситуации. Для достижения множества целей формулируется множество альтернативных вариантов решений, из которых должно быть выбрано единственное оптимальное или приемлемое решение А*. Множество критериев К используется для абсолютной и/или сравнительной оценки вариантов решений. Абсолютную оценку удается получить в редких случаях. В реальных задачах удается осуществить лишь сравнительную оценку решений. В результате осуществляют предварительный выбор лучшего решения, А*. Окончательный выбор наилучшего решения проводится ЛПР на основе функции предпочтения f. Содержание задачи принятия решений позволяет сформулировать ее особенности: 1. Неизвестные элементы задачи (ситуация, цели, ограничения, варианты решения, предпочтения) имеют содержательный характер и только частично опре- 61 деляются количественными характеристиками. Число неизвестных элементов задачи много больше числа известных. 2. Определение неизвестных элементов задачи и нахождение наилучшего решения не всегда может быть формализовано, т.к. нет готовых алгоритмов. 3. Часть характеристик может быть измерена субъективно (приоритеты целей, критериев, вариантов решения). 4. Часто решать задачи принятия решений приходится в условиях неопределенности, и в таких условиях большое значение имеет интуиция ЛПР. 5. Принимаемые решения могут непосредственно затрагивать интересы ЛПР и специалистов-аналитиков, поэтому их личные предпочтения и мотивы могут повлиять на выбор решения. Классификация задач принятия решений Существуют некоторые общие признаки, позволяющие классифицировать решения и соответствующие задачи: 1. По степени повторяемости проблемы: 1.1. Традиционные (неоднократно встречающиеся в практике). Решения здесь – выбор из имеющихся альтернатив. 1.2. Нетипичные (нестандартные). Поиск решений здесь связан с генерацией новых альтернатив. 2. По значимости цели: 2.1. Стратегические (самостоятельные). 2.2. Тактические (решения используются в качестве средства достижение цели более высокого порядка). 3. По сфере воздействия: 3.1. Локальные - результат управленческих решений может сказаться на одном или нескольких элементах системы. 3.2. Глобальные – решения влияют на функционировании системы в целом. 4. По длительности реализации: 4.1. Долгосрочные решение – если между принятием решения и завершением его реализации проходит несколько лет. 4.2. Краткосрочные – если срок небольшой. 5. По прогнозируемым последствиям решений: 5.1. Корректируемые - большинство управленческих решений поддаются корректировке в целях устранения отклонений или учета новых факторов. 5.2. Некорректируемые - решения, последствия которых необратимы. 6. По характеру используемой информации, в зависимости от полноты и достоверности информации: 6.1. Детерминированные (принимаемые в условиях определенности) 6.2. Вероятностные (принимаемые в условиях риска и неопределенности). Большинство решений являются вероятностными. 7. По методам разработки решения: 7.1. Формализованные (выполненные с использованием математических методов). 62 7.2. Неформализованные (основанные на интуиции и здравом смысле). На практике большинство решений носит комбинированный характер, т.е. применяются попеременно формальные процедуры и неформальные методы. 8. По числу критериев выбора: 8.1. Многокритериальные решения - если выбранная альтернатива должна удовлетворять нескольким критериям. 8.2. Однокритериальные – если критерий один. 9. По форме принятия: 9.1. Коллегиальные или групповые (такая форма принятия решений снижает оперативность и размывает ответственность, но препятствует грубым ошибкам и злоупотреблениям и повышает обоснованность выбора). 9.2. Единоличные (индивидуальные). 10.По способу фиксации решений: 10.1. Документированные. 10.2. Недокументированные. В теории принятия решений важной является классификация задач принятия решений (ЗПР) по степени определённости информации: - ЗПР в условиях определённости; - ЗПР в условиях риска (вероятностной неопределённости); - ЗПР в условиях неопределённости. В зависимости от особенностей решаемых задач выбираются соответствующие методы принятия решений. Многокритериальные задачи принятия решений Большинство задач принятия решений формируются как многокритериальные задачи. При оптимизации сложных систем формализовать требования к оптимизируемому объекту в виде одного критерия оптимальности бывает достаточно трудно, а зачастую и невозможно. В этом случае оптимизацию производят по нескольким частным критериям fi (X) (i 1,2,..., s) , а полученные задачи называются задачами многокритериальной оптимизации. Набор частных критериев оптимальности в многокритериальных задачах образует векторный критерий (f1(X), f 2 (X),..., fs (X)) , поэтому часто такие задачи называют задачами векторной оптимизации. Обобщенная постановка задачи: f ( x )  (f1 ( x ),..., f s ( x ))  min, x  D. Здесь D – множество допустимых решений, представленная системой прямых и функциональных ограничений. Допустимые векторы X, принадлежащие допустимой области D, называются альтернативами или вариантами. Поэтому множество D называют еще множеством альтернатив, вариантов, планов, стратегий. 63 Для всякого решения (альтернативы) XD набор его оценок по всем критериям, т.е. набор (f1(X), f 2 (X),..., fs (X)) есть векторная оценка решения X. Оценка альтернатив по критериям осуществляется либо в автоматическом режиме, либо в режиме диалога с ЛПР. Лицом, принимающим решения (ЛПР), называют человека (или группу людей), имеющего цель, которая служит мотивом постановки задачи и поиска её решения. ЛПР является компетентным специалистом в своей области и обладает опытом деятельности в ней, наделено необходимыми полномочиями и несёт ответственность за принятое решение. Условия эффективности для задач многокритериальной оптимизации. Множество Парето. Сравнение двух работоспособных вариантов с параметрами X1 и X 2  D производится на основании следующих бинарных отношений, определенных на множестве допустимых решений D: - отношения строгого предпочтения , выполнение которого X1  X2 ( X1 строго превосходит X 2 ) содержательно интерпретируется как: вариант с параметрами X1 лучше варианта с параметрами X 2 (или альтернатива X1 лучше альтернативы X 2 ); - отношения нестрогого предпочтения, выполнение которого X1  X2 ( X1 нестрого превосходит X 2 ) содержательно интерпретируется как: вариант с параметрами X1 не хуже варианта с параметрами X 2 ; - отношения эквивалентности, выполнение которого X1  X2 ( X1 эквивалентен X 2 ) содержательно интерпретируется как: вариант с параметрами X1 равноценен варианту с параметрами X 2 ; Если относительно пары альтернатив нельзя сказать, какая из них лучше, то их называют несравнимыми. Важную роль в многокритериальной оптимизации играет понятие независимости критериев по предпочтению. Смысл его состоит в том, что желательные для ЛПР изменения значений каждого из частных критериев (при неизменных значениях остальных критериев) не должны зависеть от конкретных значений остальных критериев. Рассмотрим многокритериальную задачу с независимыми по предпочтению критериями. Говорят, что альтернатива X1  D доминирует (по Парето) альтернативу X 2  D , (будем обозначать X1  X 2 ) если f i (X1 )  f i (X 2 ), i  1, m и i 0  {1, m} , такое, что f i 0 (X1 )  f i 0 (X 2 ) То есть, альтернатива X1 доминирует по Парето альтернативу X 2 , если по всем критериям оценки альтернативы X1 не хуже, чем альтернативы X1 , а хотя бы по одному критерию оценка X1 . При этом альтернатива X 2 называется доминируемой. 64 В случае доминирования при переходе от X к X ничего не будет проиграно ни по одному из частных критериев, но в отношении частного критерия i 0  {1, m} точно будет получен выигрыш. Говорят, что решение X1 лучше (пред2 1 почтительнее) решения X 2 . Доминируемое решение X 2 называется неэффективным решением. Множество неэффективных решений образует множество отбрасываемых вариантов Точка X*  D называется оптимальной по Парето (эффективной), если не существует альтернативы X  D , доминирующей X* . Эффективные решения будут несравнимы по векторному критерию оптимальности в смысле рассмотренных бинарных отношений строгого предпочтения, нестрогого предпочтения и эквивалентности. Таким образом, эффективное решение- это такой вариант с параметрами X* , относительно которого в области допустимых решений D нельзя найти ни одного безусловно лучшего варианта (не существует ни одного доминирующего решения). Оптимальность по Парето означает, что нельзя уменьшить значения некоторых частных критериев оптимальности, не увеличивая при этом хотя бы одного из остальных. Множество таких точек и называется множеством точек оптимальных по Парето. Множество точек оптимальных по Парето лежат между точками оптимумов, полученных при решении задачи для каждого частного критерия. Множество векторных оценок, соответствующих множеству неэффективных решений, называется областью согласия. Обозначим DC  D область согласия, которая не содержит недоминируемых точек (любая точка из Dc может быть улучшена). Множество векторных оценок, соответствующих множеству эффективных точек, называют областью компромиссов (переговорным множеством) или множеством Парето в области критериев. D k . Эффективная область (множество Парето) Dэ D содержит все оптимальные по Парето точки. Значение векторного критерия оптимальности F(X* )  D k , соответствующего конкретному эффективному решению X* , называется вектором Парето. Для любых двух эффективных решений X * и X ** соответствующие эм вектора Парето являются противоречивыми критериями. Это приводит к необходимости введения соглашения о компромиссе между векторами Парето. Оптимальные решения многокритериальной задачи следует искать только среди элементов множества альтернатив DЭ . В этой области ни один критерий не может быть улучшен без ухудшения хотя бы одного из других. Важным свойством множества Парето DЭ является возможность «выбраковывать» из множества альтернатив D заведомо неудачные, уступающие другим по всем критериям. При этом под оптимально-компромиссным решением будем понимать одну из эффективных точек, являющуюся предпочтительней с точки зрения ЛПР. Основные подходы к алгоритмизации задач многокритериальной оптимизации Все известные методы векторной оптимизации непосредственно или кос- 65 венно сводят решаемые задачи с несколькими критериями к задачам скалярной оптимизации. При этом используются два основных подхода: - свертка локальных критериев в обобщенный интегральный показатель; - сведение многокритериальных задач к последовательности специальным образом сформулированных задач параметрической оптимизации. Формирование обобщенного критерия оптимальности При использовании первого подхода частные критерии f i (X), i  1, s объединяются в составной критерий F(X)  Ф(F1(X),...Fs (X)) , который затем минимизируется или максимизируется. Обобщенный критерий оптимальности может быть использован только в том случае, если частные критерии оптимальности удовлетворяют следующим требованиям: - частные критерии оптимальности соизмеримы по важности, т. е. каждому из них можно поставить в соответствие некоторое неотрицательное число, которое характеризует его относительную важность по отношению к другим частным критериям; - частные критерии являются однородными (нормализованными) критериями, либо имеют единый масштаб измерения. При этом в качестве обобщенных критериев используются функции следующего вида: а) аддитивный критерий оптимальности: s F(X)   w i f i (X) ; i 1 б) мультипликативный критерий оптимальности: s wi F(X)   f i (X) ; i 1 в) среднестепенной обобщенный критерий оптимальности: 1 1 s  p F(X)   w i fip (X) .  S i 1  Здесь wi – весовые коэффициенты, удовлетворяющие условию: s  w i 1. i 1 При этом величина w i определяет важность i-го критерия и задает в количественном измерении предпочтение i-го показателя над другими. Наиболее распространенным на практике является аддитивный критерий оптимальности. При этом решение многокритериальной задачи может быть сведено к минимизации аддитивной функции: s min  w i f i (X) , XD i 1 s где w i 0,  w i 1 . i 1 66 Этот метод свертки векторного критерия, называемый методом взвешенных сумм, позволяет назначать приоритеты более важным частным критериям оптимальности за счет увеличения для них значений w i . Таким образом, при выборе обобщенного критерия оптимальности осуществляется переход от субъективизма при выборе предпочтения между частными показателями к субъективизму, связанному с назначением численных значений весовых коэффициентов w i (i1,2,..., s) . Для равноценных критериев, то есть критериев, для которых невозможно установить приоритет по важности, значения весовых коэффициентов выбираются одинаковыми: 1 w i  , i 1,2,..., s . S Для неравноценных критериев значения весовых коэффициентов определяются в соответствии с важностью критерия. В настоящее время существует большое количество различных способов и приемов, позволяющих по информации о значениях частных критериев оптимальности определять значения весовых коэффициентов w i . Наиболее простой в реализации подход заключается в вычислении для каждого частного критерия оптимальности fi (X), i  1,..., s коэффициента относительного разброса: i  f i  f i f i 1 f i f i , где f i  min f i (X), f i  max f i (X) . XD XD Параметр i определяет максимально возможное отклонение по i-му частному критерию. При этом весовые коэффициенты w i получают наибольшее значение для тех критериев, относительный разброс которых в допустимой области D наиболее значителен: i wi  (i  1,..., s) . s  k k 1 Если все f i  0, i1,2,..., s , можно рассматривать коэффициенты i ( X )  f i (X)  f i , f i которые характеризуют отклонение частного критерия оптимальности от его наименьшего значения. Широкое распространение при определении весовых коэффициентов критериев получили также экспертные методы, основанные на направленном опросе ЛПР с последующей обработкой полученных результатов. При этом используются различные процедуры ранжирования, алгоритмы логического упорядочивания 67 и т. д. Особую роль при агрегировании критериев играет использование аппарата нечетких множеств и нечетких отношений, который используется для формализации нечеткой и неполной информации, а также суждений экспертов, заданных в лингвистической форме. Методы последовательной оптимизации Использование обобщенного интегрированного показателя, как правило, приводит к трудностям при оптимизации, так как значительно усложняется рельеф целевой функции. Поэтому на практике зачастую используются другие соглашения о компромиссе, которые позволяют многокритериальную задачу свести к одной или нескольким задачам параметрической оптимизации, не вводя в рассмотрение тот или иной обобщенный критерий оптимальности. Одним из наиболее распространенных подходов является метод главного критерия. При этом ЛПР (лицо, принимающее решение) среди частных критериев оптимальности f i (X), i  1, s выделяет наиболее предпочтительный показатель (например, f t (X) ). По остальным критериям f i(X), i  t ЛПР устанавливает пороговые значения f ip (X) , которые не должны превышаться, после чего эти критерии переводятся в систему ограничений. В результате оптимизация проводится по одному главному критерию f t (X) , а к системе ограничений задачи добавляются следующие ограничения: f i (X)  f ip (X) , i  t , i  1,..., s . В процессе оптимизации может происходить смена главного критерия на основании субъективных предпочтений ЛПР. Основной трудностью метода главного критерия является назначение пороговых значений fip (X) , от выбора которых зависит окончательное решение задачи. Определение пороговых значений осуществляется в режиме диалога с ЛПР. При решении многокритериальных задач также широко используются методы последовательной оптимизации, в соответствии с которыми критерии предварительно упорядочиваются по важности и осуществляется последовательное решение s задач параметрической оптимизации, начиная с самого главного критерия: f1*  min f1 (X) XD f i*  min f i (X) , i  2, s, XD i где Di  D  Di 1; Di 1  {X |f j(X)  f *j , j  1, i - 1 } (5.1) 68 В качестве оптимально-компромиссного решения принимается оптимальное решение, полученное на s-м шаге итерационного процесса последовательной параметрической оптимизации. При использовании рассмотренного подхода минимизация k-го частного критерия оптимальности начинается только тогда, когда получены минимальные значения всех предыдущих k-1 критериев оптимальности. При этом области допустимых решений Di , i  1, s - 1 образуют сужающиеся подмножества: Ds 1  ...  D2  D1  D . Недостатком данного метода является то, что он не позволяет справедливо учитывать интересы менее важных частных критериев, так как не допускает их уменьшения, если это вызывает хотя бы незначительное увеличение более важных критериев. Этот недостаток в некоторой степени устраняется в методе последовательных уступок. При использовании этого метода на каждом k-м шаге последовательной оптимизации (5.1) вводится уступка f k 1 , характеризующая допустимое отклонение (k-1)-го частного критерия оптимальности от его минимального значения f k*1 : f1*  min f1 (X) XD fi*  min f i (X) , i  2, s, (5.2) XD i где Di  D  Di 1; Di 1  {X |f j(X)  f *j  f j , j  1, i - 1 } Введение уступки по (k-1)-му наиболее важному частному критерию позволяет улучшить значение k-го менее важного частного критерия. Развитием метода последовательных уступок является процедура, в которой уступки f k , k  1, s упорядочиваются по важности с помощью весовых коэффиs циентов  i  0, i  1, s,   i  1 . Реализация данного соглашения о компромиссе, i 1 называемая методом минимизации уступок, может быть сведена к задаче параметрической оптимизации: s min{   k f k } k 1 при условии, что (f k (X)  f k* ) / f k*  f k , k  1, s XD (5.3) 69 Если все критерии являются равноценными (  i  1 / s, i  1, s ), а все уступки одинаковы ( f k  f , k  1, s ), задача параметрической оптимизации (6.3) примет следующий вид: min f k (5.4) при условии, что (f k (X)  f k* ) / f k*  f k , k  1, s XD Решение экстремальной задачи (5.4) позволяет получить оптимальнокомпромиссное решение, которое минимизирует наибольшее отклонение каждого k-го частного критерия оптимальности от его минимально возможного значения: min{ max ((f k (X)  f k* ) / f k* )} XD 1 k s (5.5) Данный подход к определению оптимально-компромиссного решения получил в литературе название метода гарантированного результата. Решение задачи (5.5) обеспечивает наибольшую равномерность отклонения значений частных критериев от их минимально допустимых значений за счет подтягивания “наихудшего” частного критерия до уровня остальных. Вследствие того, что операции проводятся в области компромисса, подтягивание “отстающего” критерия неизбежно приводит к ухудшению значений части остальных критериев. Но при проведении ряда шагов можно добиться определенной степени уравнивания противоречивых (конфликтных) частных критериев. Для несоизмеримых по важности частных критериев можно принять соглашение о том, что они являются равноценными. В этом случае используется принцип равенства частных критериев: min f1 (X) XD при условии, что (5.6) f1(X)  f 2 (X)  ...  fs (X) При использовании данного принципа необходимо учитывать, что в некоторых случаях задача параметрической оптимизации (6.6) может оказаться неразрешимой, либо ее оптимальное решение не будет эффективным для исходной многокритериальной задачи. Из рассмотренных в данной главе подходов к определению оптимальнокомпромиссного решения в задачах векторной оптимизации видно, что с помощью различных преобразований многокритериальные задачи сводятся к задачам скалярной оптимизации. Для решения полученных однокритериальных задач могут использоваться методы, изложенные в предыдущих лекциях. 70 Теоретико-игровые модели принятия решений Теория игр – раздел теории принятия оптимальных решений, который рассматривает вопросы принятия решений в условиях конфликтных ситуаций и неопределенности. Ситуация называется конфликтной, если в ней участвуют стороны, интересы которых полностью или частично противоположны. Игра – это действительный или формальный конфликт, в котором участвуют по крайней мере два участника (игрока), каждый из которых стремится к достижению собственных целей. Допустимые действия каждого из игроков, направленные на достижение некоторой цели, называются правилами игры. Количественная оценка результатов игры называется платежом. Игра называется парной, если в ней участвуют два игрока. При большем количестве игроков игра называется множественной. Парная игра называется игрой с нулевой суммой, если сумма платежей равна нулю, т. е. проигрыш одного игрока равен выигрышу другого. Стратегией игрока называется план, по которому он совершает выбор в любой возможной ситуации. Стратегия называется оптимальной, если при многократном повторении игры она обеспечивает игроку максимально возможный средний выигрыш (или, что то же самое, минимально возможный средний проигрыш). В зависимости от числа возможных стратегий игры делятся на конечные и бесконечные. В дальнейшем будем рассматривать конечные парные игры с нулевой суммой. Пусть имеется два игрока, один из которых может выбрать i-ю стратегию из m своих возможных стратегий ( i  1, m ), а второй, не зная выбора первого, выбирает j-ю стратегию из n своих возможных стратегий ( j  1, n ). Результат характеризуется величиной платежа a ij . Если a ij  0 , выигрывает первый игрок (второй игрок проигрывает), если a ij  0 , выигрывает второй игрок (первый игрок проигрывает). В обоих случаях величина a ij равна выигрышу (проигрышу) соответствующего игрока. Из чисел a ij составляется матрица, называемая платежной матрицей, или матрицей игры.  a11 ... a1n    A   ... ... ...  a   m1 ... a mn  Строки матрицы A соответствуют стратегиям первого игрока, а столбцы – стратегиям второго. Эти стратегии называются чистыми. Нижней ценой игры называется величина: 71   max min a ij j i При этом первый игрок стремится максимизировать свой минимально возможный выигрыш. Соответствующая стратегия первого игрока i 0 называется максиминной. Верхней ценой игры называется величина:   min max a ij j i При этом второй игрок стремится минимизировать свой максимально возможный выигрыш. Соответствующая стратегия второго игрока j0 называется минимаксной. Нижняя цена игры всегда не превосходит верхнюю:    . Если     V , то величина V называется ценой игры. Игра, для которой    называется игрой с седловой точкой, а элемент a i j , который минимален 0 0 в строке i 0 и одновременно максимален в столбце j0 , называется седловым элементом. Седловой точке соответствуют чистые стратегии i 0 и j0 , совокупность которых является решением игры. Пример. Найти оптимальное решение и цену игры, заданной матрицей:  1  1 A  3 2   Решение. Определим нижнюю цену игры:   max(1;2)  2 Определим верхнюю цену игры:   min( 3;2)  2 Так как нижняя цена совпадает с верхней, мы имеем игру с седловой точкой. Седловой элемент 2 находится на пересечении второй строки и второго столбца. Следовательно, для получения оптимального результата игры каждый из игроков должен выбрать вторую стратегию. Цена игры при этом равна 2. Итак, если игра имеет седловую точку, то решение игры известно и определяется в чистых стратегиях. При этом каждый из игроков применяет свою оптимальную стратегию. Если же игра не имеет седловой точки (    ), то поиск оптимального решения состоит в том, что игроки применяют не одну, а несколько стратегий. Выбор стратегий осуществляется случайным образом. В данном случае говорят о смешанных стратегиях игроков. 72 Смешанной стратегией игрока называется вектор, каждая из компонент которого показывает относительную частоту (вероятность) использования игроком соответствующей чистой стратегии. Из данного определения следует, что сумма компонент указанного вектора равна единице, а сами эти компоненты неотрицательны. Пусть U  (u1,..., u m ) – смешанная стратегия первого игрока; Z  (z1,..., z m ) – смешанная стратегия второго игрока. При этом u i  0, i  1, m , z j  0, j  1, n , m  ui  1 i 1 n z j 1 j1 Применение оптимальных стратегий позволяет получить выигрыш, равный цене игры:   V   . * * Если U – оптимальная стратегия первого игрока, а Z – оптимальная стратегия второго игрока, цена игры определяется как математическое ожидание выигрыша и равна: m n V    a iju *iz*j i 1 j1 Основная теорема теории игр: каждая конечная игра имеет, по крайней мере, одно решение, возможно, в области смешанных стратегий. * * Для того, чтобы число V было ценой игры, а U и Z оптимальными стратегиями, необходимо и достаточно выполнение следующих неравенств: m  a iju *i  V, j  1, n , i 1 n  a ijz*j  V, i  1, m . j1 Первое неравенство означает, что применение первым игроком оптимальной * стратегии U должно обеспечить ему при любых действиях второго игрока выигрыш не меньше цены игры. Второе неравенство означает, что применение вто* рым игроком оптимальной стратегии Z должно обеспечить ему при любых действиях первого игрока проигрыш, не превышающий цену игры. В дальнейшем данные соотношения используются для решения игры. Для нахождения решения игр 2×2, 2×n, m×2 может быть использована следующая теорема: Если один из игроков применяет оптимальную смешанную стратегию, то его выигрыш равен цене игры V независимо от того, с какими частотами будет при- 73 менять второй игрок стратегии, вошедшие в оптимальную (в том числе и чистые стратегии). Пример. Найти оптимальное решение и цену игры, заданной матрицей:  2  1 A  3   Решение. Определим нижнюю цену игры:   max( 1;0)  0 Определим верхнюю цену игры:   min( 2;3)  2 Так как нижняя цена не совпадает с верхней, игра не имеет седловой точки и решение необходимо искать в смешанных стратегиях. При этом для цены игры должно выполняться соотношение: 0V2 Для нахождения решения игры 2×2 воспользуемся соответствующей теоремой. Предположим, что для первого игрока стратегия задается вектором U  ( u1, u 2 ) . Тогда на основании теоремы при применении вторым игроком 1-й или 2-й чистой стратегии игрок 1 получит средний выигрыш, равный цене игры V, т. е. 2u1*  V  u1*  3u *2  V (при 1-й стратегии второго игрока); (при 2-й стратегии второго игрока). Кроме того, необходимо обеспечить выполнение условия: u1*  u *2  1 Решая полученную систему трех уравнений с тремя неизвестными, получим: u1*  1 / 2 ; u *2  1 / 2 ; V  1 . Найдем теперь оптимальную стратегию для второго игрока. Пусть смешанная стратегия для данного игрока задается вектором Z  ( z1, z 2 ) . Тогда 2z1*  z1*  V  *  3z 2  V  z*  z*  1 2  1 74 * * Решив систему, получим: z1  2 / 3 ; z 2  1 / 3 ; V  1 . Следовательно, реше* * нием игры являются смешанные стратегии U  (1 / 2;1 / 2) , Z  ( 2 / 3;1 / 3) , а цена игры V  1 . Необходимо заметить, что с использованием рассмотренной технологии можно находить только решение игр 2×2, 2×n, m×2. При другой размерности платежной матрицы необходимо использовать другие подходы к решению. Преобразование задач теории игр к задачам линейной оптимизации Рассмотрим игру m  n , определяемую матрицей  a11 ... a1n    A   ... ... ...  a   m1 ... a mn  Согласно основной теореме теории игр, для оптимальной стратегии первого * игрока U и цены игры V должно выполняться неравенство: m  a iju *i  V, j  1, n i 1 Предположим для определенности, что V  0 . Это всегда может быть достигнуто благодаря тому, что прибавление ко всем элементам матрицы A одного и того же постоянного числа C не приводит к изменению оптимальных стратегий, а лишь увеличивает цену игры на С. Разделив обе части последнего неравенства на V, получим: u *i  a ij  1 V i 1 m ( j  1, n ) Сделаем замену переменных y*i  u *i / V . Тогда m  a ij y*i  1 , ( j  1, n ), i 1 y*i  0 , ( i  1, m ) m Используя введенное обозначение, перепишем условие  u *i  1 в виде: i 1 m  y*i  1 / V . i 1 Так как первый игрок стремится получить максимальный выигрыш, то он должен обеспечить минимум величине 1/V. С учетом этого, определение оптимальной стратегии первого игрока сводится к решению следующей задачи линейного программирования: 75 m  y i  min i 1 m  a ij y i  1 ( j  1, n ) (5.7) i 1 y i  0 (i  1, m) Аналогичные рассуждения показывают, что определение оптимальной стратегии второго игрока сводится к решению следующей задачи линейного программирования: n  x i  max j1 n  a ijx j 1 (i  1, m) j1 (5.8) x j  0 (j  1, n ) Задачи (5.7) и (5.8) составляют пару двойственных задач. В дальнейшем будем считать задачу (5.8) прямой, а задачу (5.7) – двойственной. Используя решение пары двойственных задач, получаем соотношения для определения оптимальных стратегий и цены игры: x *j y*i * * * ui   Vyi , z j   Vx *j m n  y*i  x *j i 1 V 1 m  y*i i 1 j1  1 n ( i  1, m; j  1, n )  x*j j1 Таким образом, процесс нахождения решения игры с использованием методов линейного программирования включает следующие этапы: 1. Построение пары двойственных задач линейного программирования, эквивалентных данной матричной игре. 2. Определение оптимальных планов пары двойственных задач. 3. Определение решения игры, используя соотношение между планами пары двойственных задач и оптимальными стратегиями и ценой игры. Пример. Найти решение игры, заданной матрицей  1 2 0   A  1 0 1  2 1 0   Решение. Составим пару двойственных задач линейного программирования. Прямая задача: x1  x 2  x 3  max 76 x1  2 x 2  1 x1  x 3  1 2 x1  x 2  1 x1 , x 2 , x 3  0 Двойственная задача: y1  y 2  y3  min y1  y 2  2 y 3  1 2 y1  y 3  1 y2  1 y1 , y 2 , y 3  0 Найдем оптимальные планы прямой и двойственной задач. Решим сначала прямую задачу. Приведем ее к канонической форме:  x1  x 2  x 3  min x1  2 x 2  x 4  1 x1  x 3  1 2 x1  x 2  x 5  1 x1 , x 2 , x 3 , x 4 , x 5  0 Решение представлено в симплекс-таблице: 77 Из таблицы видно, что исходная задача имеет оптимальный план * X  (0;1 / 2;1) , а двойственная задача – оптимальный план Y *  (1 / 2;1;0) . Следо1 2  , а оптимальные стратегии игроков вательно, цена игры V  1/ 2  1 3 * * U  (1 / 3;2 / 3;0) и Z  (0;1 / 3;2 / 3) Принятие решений в условиях неопределённости Математическая теория игр дает научно обоснованные рекомендации поведения в конфликтных ситуациях. Характерной особенностью любого конфликта является то, что ни одна из участвующих сторон не знает заранее точно и полностью всех своих возможных решений, а также и другие стороны, их будущее поведение и, следовательно, каждый вынужден действовать в условиях неопределенности. Однако неопределенность исхода может быть обусловлена как сознательными действиями активных противников, так и несознательными, пассивными проявлениями, например, стихийных сил природы: дождя, солнца, ветра, лавины и т.п. В таких случаях исключается возможность точного предсказания исхода. В одних конфликтах противоположной стороной выступает сознательно и целенаправленно действующий активный противник, заинтересованный в нашем поражении, который сознательно препятствует успеху, добивается победы любыми средствами. В других конфликтах такого сознательного противника нет, а действуют лишь так называемые «слепые силы природы»: погодные условия, состояние торгового оборудования на предприятии, болезни сотрудников, нестабильность экономической ситуации, рыночная конъюнктура, динамика курсов валют, уровень инфляции, налоговая политика, изменяющийся покупательский спрос и т.п. В таких случаях природа выступает пассивно, причем иногда во вред человеку, а иногда к его выгоде, однако ее состояние и проявление могут ощутимо влиять на результат деятельности. То есть в задачах подобного рода выбор решения зависит от состояний объективной экономической действительности, называемой в модели «ПРИРОДОЙ». Термин «ПРИРОДА» характеризует некую объективную действительность, которую не следует понимать буквально. Математические модели подобных конфликтных ситуаций называются «ИГРАМИ С ПРИРОДОЙ». В таких играх человек старается действовать осмотрительно, например, используя стратегию, позволяющую получить наименьший проигрыш. Второй игрок (природа) действует совершенно случайно, возможные стратегии его известны (стратегии природы). Такие ситуации исследуются с помощью теории статистических решений. Хотя вполне могут встречаться ситуации, в которых игроком может действительно выступать природа. Например, обстоятельства, связанные с погодными условиями или с природными стихийными силами. Игра человека с природой тоже отражает конфликтную ситуацию, вызванную столкновением интересов человека и неопределенностью действий природы, но без явной антагонистической окраски. Таким образом, термин "природа" в теории игр понимается в широком смысле. Это могут быть действительные природные физические (климатические), 78 биологические, химические, социальные и т.п. процессы, которые сопровождают экономическую деятельность. Под "природой" может также пониматься рынок, противостоящий предпринимателю, конкурирующая среда, монополия и т.п. Матричные игры, в которых одним из игроков является неопределенность, зависящая от объективной действительности (погода, покупательский спрос и т.д.), называются играми с «природой» или статистическими играми. Игрок A в таких играх - это субъекты принятия решений, а игрок B - это "природа". Строки матрицы игры соответствуют стратегиям игрока, а столбцы – состояниям «природы. Пусть игрок A имеет m возможных стратегий Ai , i  1...m , а природа Q может находиться в одном из n возможных состояний Q j , j  1...n , которые можно рассматривать как её стратегии. Тогда матрицу игры с природой можно представить в виде, аналогичном платёжной матрице матричной игры: где a ij - выигрыш игрока A при выборе им стратегии Ai и при состоянии природы Q j . Показателем благоприятности состояния Q j природы Q называется наибольший выигрыш при этом состоянии, то есть наибольший элемент j-го столбца: Для характеристики степени удачности применения игроком стратегии Ai и при состоянии природы Q j вводят понятие риска . Риском r ij игрока A при выборе им стратегии Ai при состоянии природы Q j называется разность между показателем благоприятности  j и выигрышем a ij : Таким образом, риск – это разность между выигрышем, который игрок получил бы, если бы он точно знал, что состоянием среды будет Q j , и выигрышем, который он получит, не имея этой информации. То есть риск r ij игрока A представляет собой упущенную возможность максимального выигрыша (упущенную выгоду) при данном состоянии природы. Для данной матрицы выигрышей A матрица рисков имеет ту же размерность и следующий вид: 79 Пример: Решение. Вычислим показатели благоприятности: Для решения игры с природой требуется выбрать такую чистую (или смешанную) стратегию, которая была бы наиболее выгодной по сравнению с другими. Отметим, что смешанной стратегии у игрока может и не быть, если действия игрока являются альтернативными, например, при выборе альтернативных проектов. Методы принятия решений в игре с природой зависят от того, известны или нет вероятности состояний Q j природы. Если эти вероятности неизвестны, то имеет место ситуация полной неопределённости и это называется принятием решений в условиях полной неопределённости, а если эти вероятности известны априорно, то имеем дело с принятием решений в условиях риска. Принятие решений в условиях полной неопределённости Рассмотрим игру с природой, в которой вероятности состояний природы Q j неизвестны и отсутствует всякая возможность получения о них какой-либо статистической информации. Таким образом, мы находимся в состоянии полной неопределённости, связанной с отсутствием информации о состоянии природы. В таких моделях для определения наилучших решений используются следующие критерии: максимакса, Вальда, Сэвиджа и Гурвица. Критерий максимакса. Это критерий крайнего оптимизма, максимизирующий выигрыши для каждого состояния природы по формуле: Таким образом, критерий максимакса является критерием крайнего оптимизма, так как ориентирует ЛПР на наилучшее состояние природы. 80 Максиминный критерий Вальда. При применении данного критерия природа рассматривается как агрессивно настроенный и сознательно действующий противник. Поэтому выбирается стратегия, гарантирующая выигрыш не меньший, чем “нижняя цена игры с природой”: В соответствии с этим критерием из всех неудачных результатов выбирается самый лучший. Это перестраховочная позиция крайнего пессимизма, рассчитанная на худший случай. Такая стратегия приемлема, например, когда игрок не столько хочет выиграть, сколько не хочет проиграть. Выбранное таким образом решение полностью исключает риск. Критерий минимального риска Сэвиджа. Этот критерий аналогичен критерию Вальда, только игрок в этом случае руководствуется матрицей рисков и выбирает стратегию, при которой достигается минимально возможный из наибольших рисков: Критерий пессимизма-оптимизма Гурвица с показателем пессимизма  [0;1] Этот критерий учитывает как пессимистический, так и оптимистический подходы к решению игры. А именно при   0 получаем критерий крайнего оптимизма и решение совпадает с критерием максимакса, при   1получаем критерий крайнего пессимизма и решение совпадает с критерием Вальда. Для рассматриваемого примера при   0,5 получим: 81 Принятие решений в условиях риска Предположим теперь, что игроку из прошлого опыта известны не только возможные состояния природы Q j , j  1...n , но и соответствующие вероятности p j  P(Q Q j , ) , с которыми природа реализует эти состояния. В этом случае мы отступаем от условий полной неопределённости и будем находиться в ситуации принятия решений в условиях риска. Критерий Байеса (максимального математического ожидания) По этому критерию показателем эффективности стратегии Ai , i  1...m называется среднее значение (математическое ожидание) выигрыша с учётом вероятностей всех возможных стратегий природы: то есть a i представляет собой взвешенное среднее выигрышей i-й строки матрицы выигрышей, взятых с весами p1,...pn . Оптимальной среди чистых стратегий по критерию Байеса будет стратегия с максимальным показателем эффективности, то есть с максимальным выигрышем Следовательно, выбранное таким образом решение является оптимальным не в каждом отдельном случае, а “в среднем”. 82 Пример Критерий Лапласа В критерии Байеса известные вероятности состояний природы могли быть получены, например, на основании статистических исследований. Однако часто складывается такая ситуация, при которой мы лишены возможности определить эти вероятности. Тогда мы можем считать состояния природы равновероятными: То есть мы не можем отдать предпочтение ни одному из состояний природы. Этот принцип называют принципом “недостаточного основания” Лапласа. 83 Для рассматриваемого примера: