Исследование операций и методы оптимизации

Исследование операций и методы оптимизации Лекции Содержание 1.Методология системного анализа и исследование операций .......... 4 1.1. Системный анализ, система, оптимизация ..................................... 4 1.2. Схема операционного проекта ........................................................ 5 1.3. Особенности математического моделирования операций ............ 8 1.4. Постановка задачи исследования операций в детерминированном случае и в условиях неопределенности ..... 9 1.5. Пример математического моделирования операции (Задача о краске). ........................................................................................... 10 2. Линейное программирование (ЛП) .......................................................... 13 2.1. Общая и основная задачи ЛП ........................................................ 14 2.2. Геометрическая интерпретация задачи ЛП .................................. 16 2.3. Идея симплекс-метода решения задачи ЛП ................................. 18 2.4. Симплекс-таблица, стандартный алгоритм симплекспреобразования.............................................................................. 20 2.5. Алгоритм отыскания опорного решения задачи ЛП ................... 22 2.6. Алгоритм отыскания оптимального решения задачи ЛП ........... 23 2.7. Алгоритм получения первого базисного решения с использованием симплекс – процедуры (метод искусственного базиса)................................................................. 27 2.8. Вырожденная задача ЛП ................................................................ 29 2.9. Двойственная задача ЛП ................................................................ 30 3. Транспортные задачи (ТЗ) ......................................................................... 33 3.1. Математическая модель ТЗ по критерию стоимости .................. 33 3.2. Нахождение опорного плана транспортной задачи..................... 34 3.3. Оптимизация плана ТЗ, распределительный метод .................... 36 3.4. Метод потенциалов решения ТЗ ................................................... 39 3.5. Решение ТЗ с неправильным балансом ........................................ 42 3.6. ТЗ по критерию времени, типы критериев ................................... 44 4. Дискретное программирование ................................................................ 47 4.1. Особенности задач дискретного программирования ................... 48 4.2. Примеры моделей задач дискретного программирования .......... 49 4.2.1. Задача о покрытии ....................................................................... 53 4.2.2. Задача о коммивояжёре ............................................................... 54 4.2.3. Задача о раскрое материала ........................................................ 54 4.2.4. Задача о ранце .............................................................................. 57 4.3. Алгоритм решения задачи о ранце ................................................ 58 4.4. Решение задач ЛЦП методом отсечений Гомори ........................ 61 4.5. Метод ветвей и границ (МВГ) ....................................................... 66 4.6. Алгоритм МВГ для задачи ЛЦП ................................................... 68 4.7. Алгоритмы решения задач булевского программирования. ...... 71 5. Динамическое программирование (ДП) ................................................... 76 5.1 Принцип оптимальности Р.Беллмана ............................................. 77 5.2. Решение графовых задач на основе принципа Беллмана. ........... 79 5.3. Функциональное уравнение Беллмана .......................................... 80 5.4. Задачи распределения ресурсов..................................................... 81 5.4.1. Классическая задача распределения ресурсов .......................... 81 5.4.2. Неоднородные этапы и распределение ресурсов по n отраслям ......................................................................................... 82 5.4.3. Распределение ресурсов с резервированием ............................. 83 5.4.4. Распределение ресурсов с “вложением доходов” ..................... 85 5.5. Расширение модели задач динамического программирования . 86 6. Нелинейное программирование ................................................................ 93 6.1. Особенности задач нелинейного программирования .................. 93 6.2. Прямые методы одномерной оптимизации нелинейных функций без ограничений ............................................................. 95 6.3. Градиентные методы многомерной оптимизации ....................... 97 6.3.1. Классический градиентный метод ............................................. 97 6.3.2. Покоординатный метод ............................................................... 98 6.3.3. Метод наискорейшего спуска. и его модификации ................ 99 6.4. Метод деформируемого многогранника Нелдера-Мида ............. 99 6.5. Задача НЛП с ограничениями-равенствами. .............................. 101 6.6. Выпуклое НЛП .............................................................................. 104 6.8. Квадратичное программирование ............................................... 107 6.9. Методы возможных направлений ............................................... 112 6.10. Метод проекции градиента ........................................................ 115 6.11. Методы штрафных и барьерных функций ............................... 118 6.12. Метод скользящего допуска ...................................................... 124 7. Особенности современной теории принятия оптимальных решений ................................................................................................ 127 7.3. Многокритериальная оптимизация ............................................. 132 7.4. Определение множества Парето .................................................. 135 2 7.5. Методы условной многокритериальной оптимизации ............. 137 8. Игровые модели принятия решений ...................................................... 142 8.1. Основные понятия теории игр ..................................................... 142 8.2. Платежная матрица антагонистической игры, принцип минимакса .................................................................................... 143 8.3. Решение игр в смешанных стратегиях ....................................... 146 8.4. Упрощение игр и аналитическое решение игр 2*2. .................. 146 8.5. Геометрическое решение игр ...................................................... 148 8.6. Решение игр с многии стратегиями на основе метода линейного программирования ................................................... 151 8.7. Биматричные игры ....................................................................... 154 9. Элементы теории статистических оптимальных решений ................. 157 9.1. Принятие решений при известных априорных вероятностях . 158 9.2. Методы принятия решений в условиях априорной неопределенности ....................................................................... 160 9.3. Планирование эксперимента при принятии решений ............... 160 9.4. Многоэтапное принятие решений ............................................... 162 10. Экспертные процедуры для принятия решений .................................. 166 10.1. Общая схема экспертизы ........................................................... 166 10.2. Задача оценивания ...................................................................... 167 10.3. Подготовка экспертизы .............................................................. 167 10.4. Методы обработки экспертной информации ........................... 168 10.5. Метод Делфи для численной оценки ........................................ 170 10.6. Строгое ранжирование ............................................................... 171 10.7. Нестрогое ранжирование ........................................................... 172 10.8. Метод попарных сравнений ...................................................... 172 Список литературы ...................................................................................... 174 3 1.Методология системного анализа и исследование операций 1.1. Системный анализ, система, оптимизация В середине двадцатого века во многих областях деятельности человека сформировалась необходимость изучения и совершенствования сложных систем, в том числе систем организационного типа: систем обороны; производственных систем, отраслей, предприятий и др.). Оказалось: 1) в сложных системах взаимосвязь между элементами играет большую роль, чем свойства самих элементов 2) в таких системах элементы могут быть разнородны (оборудование, персонал, материалы, транспорт, условия поставок и сбыта и т.д.). Термины системный анализ и исследование операций возникли, когда были образованы группы по исследованию военных операций в армии США и Англии во время второй мировой войны. К этому времени, во-первых, был накоплен опыт применения математических методов для моделирования и решения некоторых задач экономики (В.Леонтьев, Л.В.Канторович), была теоретически обоснована возможность решения задач большой размерности на ЭВМ. Позже были созданы первые образцы таких машин. Совпали необходимость и возможность. Возникли новые идеи совершенствования организационных систем на основе математической теории игр (Нейман – Моргенштерн). Методология, сформулированная тогда и вобравшая в себя все научные достижения в области изучения сложных систем оказалась применимой не только к боевым операциям, но и к другим сферам. Но термин «исследование операций» остался. Системный (операционный) подход – основа для изучения и совершенствования сложных систем . Применительно к специалистам инженерам в области применения математики и информационных технологий в промышленности исследование операций формирует определенную технологию совершенствования существующих и создания новых систем как технических, так и организационных. Система – множество элементов с определенными способами взаимодействия между ними, которые все вместе выполняют цель системы. Процесс – все, что происходит в системе. Система работает, значит в ней происходит процесс. Операция – часть процесса, которая наделена свойствами всей системы. Операция – это управляемое мероприятие, выполняющее определенную цель, сопоставимую с целью всей системы. Например, операция со4 ставления расписания учебных занятий для учебного процесса в системе «университет». При исследовании сложных организационных систем: 1) невозможен экспериментальный метод исследования; 2) невозможно описание поведения систем только на основе какой – либо естественно-научной теории; 3) при описании таких систем количество факторов, которые необходимо учитывать, велико. Поэтому очевидно, что такие системы невозможно моделировать, изучать и совершенствовать без использования компьютерных средств и технологий. 1.2. Схема операционного проекта Весь комплекс работ по изучению и совершенствованию системы (операции) проводит операционная группа системных аналитиков. Этот проект проводится в интересах лица, принимающего решения (ЛПР). ЛПР может отвергнуть проект, а может принять. На рис.1 изображена примерная схема этапов операционного проекта. 1. Фиксация симптомов проблемы 4. Качественный системный анализ 2. Определение тенденции 5. Количественный системный анализ 6. Математическое моделирование не удовл Методы оптимизации 7. Решение на модели 3. Формулировка проблемы 8. Проверка решения на корректность удовл 9. Подготовка документов ЛПР ЭВМ Дадим краткую характеристику этапов операционного исследования. 5 1. В самом общем случае поводом для изучения и совершенствования системы служат зафиксированные симптомы, обнаруживающие проблемные вопросы в работе системы. 2.Установленные симптомы проблемы могут образовывать связанную цепочку фактов (тенденцию), которая помогает сформулировать проблему. 3.Важнейшим этапом исследования системы является четкая формулировка проблемы, которая присутствует на данном уровне жизнедеятельности системы. 4.Качественный системный анализ – это расщепление целостной системы (операции) на отдельные элементы (сущности). Для этого нужно: -- выделить изучаемую систему (операцию) из вышестоящей системы (операции), -- сформулировать цель, выполняемую системой ( операцией), -- перечислить факторы, которые влияют на достижение цели. -- определить возможные ограничения, в рамках которых можно совершенствовать систему (операцию). 5.Количественный системный анализ предполагает описать все перечисленные факторы, которые участвуют в операции на количественном уровне, т.е. на основе измеримых параметров. Для этого -- устанавливается критерий К – величина, количественно измеряющая степень достижения цели системы (операции). -- вводятся количественные внутренние параметры системы, которые измеряют факторы, участвующие в описании системы (операции). -- все множество этих параметров необходимо разбить на две части: а) неуправляемые параметры (константы), которые мы в данной конкретной системе (операции) менять не можем (производительность, нормы расхода материалов и т.п.), их обозначают как коэффициенты А = (а1, а2, …, ак). б) управляемые параметры (переменные) – величины, которые мы можем менять Х = (х1, х2, …, x n). 6.Суть математического моделирования – установление количественных связей между введенными величинами К, А, и X в виде так называемой операционной модели. Первая часть операционной модели - это модель целевой функции, она устанавливает функциональную зависимость критерия К от неуправляемых параметров А и управляемых величин X в виде K = f(X, A). f – может быть функция, заданная аналитически, таблично или алгоритмом. ( В ряде практических задач в качестве элементов множества X выступают функции. В этом случае f - функционал. Задачи такого рода называются вариационными и в данном пособии не рассматриваются.). Для целевой функции указывается направление улучшения критерия 6 K = f(X, A) → min(max). (1.1) Этим выражением и определяется смысл оптимизации системы (операции). Вторая часть операционной модели – математическое описание ограничений на выбор переменных Х. Все ограничения в общем виде можно записать в виде неравенств (равенств): φi(X, A) ≤ 0, i  1, m (1.2 ) Каждая функция φi(X,A) называется функцией ограничения. В некоторых задачах имеются требования на сам вид переменных Х или К. X D  (1.3) . K M  Например часто возникает требование, чтобы X или К должны быть целыми. В некоторых случаях они должны принадлежать некоторому стандартному множеству значений. Модель в виде 1.1, 1.2, 1.3 – модель операционного вида или оптимизационная модель (неоптимизационная – без целевой функции). Модель 1.1, 1.2, 1.3 позволяет поставить задачу оптимизации системы (операции) как математическую задачу: найти такие управляемые переменные Х, которые удовлетворяли бы системе ограничений 1.2, 1.3 и обеспечивали бы наилучшее значение критерия К. 7.Решение поставленной математической задачи требует привлечения методов оптимизации, включающих кроме классических математических методов также и специальные методы исследования операций. Реальные задачи приводят к большой размерности (до десятков тысяч). Поэтому современные методы нахождения оптимальных решений ориентированы на использование компьютерных средств. 8.Сопоставляя полученное решение с содержательной постановкой задачи можно обнаружить противоречия или какие-нибудь некорректные элементы решения. Причиной некорректности могут быть ошибки в математической модели или неучет некоторых существенных ограничений. На этом этапе может принимать участие лицо, принимающее решение (ЛПР). Если полученное решение приемлемо – оно принимается, если нет - необходимо вернуться на этап математического моделирования или даже на более ранние этапы исследования. 9.Найденное оптимальное решение X* позволяет подготовить управляющее решение в форме документа для ЛПР. Таким образом, операционное исследование – итерационный процесс, который сходится к определенному оптимальному решению. Рассмотренная схема является примерной. Она позволяет лучше понять смысл систем7 ного анализа и исследования операций как науки. Исследование операций (ИСО) - это наука о количественном обосновании оптимальных решений на основе построения и использования математической модели. К сожалению, процесс перевода на количественное описание сложных систем и операций не является технологией. Математическая модель может получиться удачной или неудачной для получения практических решений. Вот почему знаменитый операционист Томас Саати иронично определил науку «Исследование операций» как « искусство давать плохие советы в тех практических случаях, в которых другие науки ничего не могут посоветовать». 1.3. Особенности математического моделирования операций Математическое моделирование – самый сложный этап ИСО. Математическая модель – это такое описание системы, которое позволяет специалисту выполнить цель исследования и оптимизации системы. Для одной и той же системы можно построить различные модели, чтобы выявить различные свойства: например аэродинамическая модель, прочностная модель и т.д. Модель должна быть адекватной реальной задаче, т.е. решения, полученные в рамках построенной модели должны обладать такими же свойствами, что и реальная система. К сожалению, не существует какого-либо алгоритма, по которому необходимо создать модель. Можно руководствоваться лишь принципами моделирования: 1. Необходимо решить вопрос размерности модели. Если число параметров увеличить, то мы более точно отобразим реальное событие, но в модели будет трудно выявить основные свойства (наиболее значимые). Задача становится необозримой и может не иметь решения. Поэтому число переменных по возможности стараются уменьшать, оставляя главные, существенные. Но уменьшая число переменных, мы можем опустить существенные, и модель становится неадекватной. 2. Модель зависит от точности, с которой нужно получить решение. 3. Модель зависит от того, насколько мы знаем исходные данные. 4. Подход к построению модели может быть двояким: 4.1.Создание оригинальной модели (не учитывая предыдущей модели в этой области), т.е. разработка «с чистого листа». Это может дать, а может не дать хороший результат. Преимущество: «свежий взгляд на вещи», нет чужих ошибок. Но это может быть дороже и потребует большого времени. 4.2.Использование типовых моделей для моделирования конкретных операций. В настоящее время существует большое число типовых моделей, описывающих наиболее распространенные виды операций и систем: - модель линейного программирования (ЛП); - модель динамического программирования ; 8 - игровые модели; - модель массового обслуживания; - модель систем управления запасами; и многие другие. Такой подход наиболее подходит для обучения специалистов, так как дает им инструмент для математического моделирования реальных систем в их предметной области. 1.4. Постановка задачи исследования операций в детерминированном случае и в условиях неопределенности Если в операционной модели: K  f ( X , A)  min(max) i ( X , A)  0, i  1, m ( 1.4) (1.5) все неуправляемые переменные А – заранее точно известные величины (const), а f – детерминированная функция, то такая модель называется детерминированной. В некоторых задачах это не выполняется. Среди неуправляемых переменных есть такие Z = (z1, z2, …, zl), которые меняются случайно. В этом случае говорят, что операция проходит в условиях неопределенности. K = f(X, A, Z). K меняется не только с изменением Х и и задача на максимум K становится некорректной. В этом случае ставится задача выбора такой критериальной величины, которая менялась бы только от Х. В простейшем случае, когда f – линейная функция, можно искусственно свести задачу к детерминированной, заменив Z на M[Z], т.к. в этом случае M[K] = f(X, A, M[Z]). Это же можно сделать, если f слабо меняется от Z. Но в общем случае это не так. В общем случае усреднение проводят по всем правилам: M [ K ]  ..  ( z1 ..zl )  f ( X , A, Z )dz1 ..dzl  max , где функция … - плот-   l штук ность распределения вероятностей величин Z. Вид целевой функции после такого преобразования существенно усложняется. Поэтому усложняется задача отыскания решения. 9 1.5. Пример математического моделирования операции (Задача о краске). Для демонстрации существа операционного подхода рассмотрим простой пример. Содержательное описание задачи. Для окраски помещения необходимо купить 15 кг краски. Эту краску можно купить в банках двух типов: по 1,5 кг стоимостью 10 рублей каждая или банках весом 0,9 кг стоимостью 8,5 рублей. Для перевозки используется ящик, в который может уместиться 8 банок первого типа или 25 банок второго типа. Необходимо дать математическую формулировку задачи минимизации стоимости покупки. Найти, сколько целых банок каждого типа надо купить. Необходимо дать графическую интерпретацию решения. Сравнить с решением, которое получится, если банка краски первого типа будет стоить 17 рублей. Решение Обозначим x1 - количество банок первого типа, x 2 - количество банок второго типа. Так как количество купленной краски не должно быть меньше 15 кг, то 1,5x 1  0,9x 2  15 . Каждая банка первого типа занимает 1/8 объема ящика, а второго 1/25 часть, поэтому ограничение на объем ящика можно выразить следующим 1 1 образом: x 1  x 2  1. 8 25 Стоимость покупки обозначим L, она равна L  10x 1  8,5x 2  min Получаем задачу, принадлежащую к классу задач линейного программирования (ЛП):  L  10x  8,5x  min; 1 2   1,5x 1  0,9x 2  15;  1  8 x1  1 25 x 2  1. (1.6) (1.7) (1.8) Если банки вскрывать нельзя, то необходимо добавить ограничения: x1 - целое, x 2 - целое (1.9) Задача 1.6, 1.7, 1.8, 1.9 – это задача линейного целочисленного программирования (ЛЦП). Если количество переменных в задачах ЛП и ЛЦП большое, то их необходимо решать с использованием специальных алгоритмов (которые 10 мы изучим) и компьютерных программ. В нашем случае – две переменные, следовательно, можно использовать простое геометрическое решение. Рассмотрим равенства (1.7) и (1.8). 1,5x 1  0,9x 2  15 - уравнение прямой линии. Делим на 15 правую и левую части уравнения: x 1 10  x2 16,6 1. Это каноническое уравнение прямой. Построим его. Х2 . . 17.С 25 10 Область допустимых решений Целое оптимальное решение Оптимальное решение . В .А L=170 . 4 . 8 .10 Х1 1 1 x1  x 2  1. 8 25 Проверяя допустимость какой-нибудь точки для неравенств (1.7) и (1.8), например, точки (0; 0), определяем область допустимых решений, удовлетворяющих (1.7) и (1.8). Изобразим линию постоянного уровня целевой функции L=const. возьмем, например, L=170, получим уравнение прямой 170  10x 1  8,5x 2 . x x Приведем его к канонической форме и построим 1 17  2 20  1 . Убеждаемся, что если L→min, то эта прямая движется параллельно самой себе к началу координат. Оптимальной точкой будет точка выхода этой прямой из области допустимых решений. Уравнение (1.8) имеет вид 11 Очевидно, что точка А является оптимальной для случая, когда банки можно вскрывать ( x1 и x 2 могут быть нецелыми), а точка В – оптимальная точка для целого решения. Найдем координаты точки А, решив совместно уравнения (1.7) и (1.8) :  1,5x 1  0,9x 2  15;   1/8x 1  1/25x 2  1. Получим x1*  5,8; x*2  7,1; L*  118,35. Заметим, что «округленное» решение x1 =6; x 2 =7 не является допустимым. Оптимальное решение, которое является последним при выходе прямой L, находим из целых допустимых. Это точка В с координатами x 1  4; x 2  10; L  125. Если стоимость банки краски первого типа повысится до 17 рублей, то целевая функция будет L  17x 1  8,5x 2  min . x x  1. Построим прямую для L=170. 1  2 10 20 Очевидно, что оптимальная точка будет в точке С: x1 =0; x 2 =16,6. Целое оптимальное решение будет x1 =0; x 2 =17; L’=144,5. Ответ: 1) Если банки можно вскрывать, то необходимо взять  5,8 банок первого типа;  7,1 банок второго типа, стоимость L*  118,35 . 2) Если банки вскрывать нельзя, то необходимо взять  4 банки первого типа;  10 банок второго типа, стоимость L=125. 3) Если стоимость банки первого типа станет 17 рублей, то оптимальное решение изменится: x1 =0; x 2 =17; L’=144,5. 12 2. Линейное программирование (ЛП) ЛП - наиболее распространенный и хорошо изученный раздел исследование операций. Изучение ЛП можно проводить в двух направлениях: 1) как развитие линейной алгебры (чисто математическое) 2) изучение конкретных моделей, приводящих к ЛП. Впервые задача ЛП была сформулирована Л.В.Канторовичем, который применил математическую модель задачи ЛП для экономики (1939 г.). Впоследствии, в 1947 г. американец Джон Данциг разработал алгоритм решения этой задачи. С этого момента ЛП стало основным методом в системном анализе и в первую очередь в задачах экономики. В 1975г. Л.В.Канторович получил Нобелевскую премию как основоположник ЛП. Задача ЛП – такая задача исследования операций, когда целевая функция и все функции ограничений линейны, а все переменные – действительные числа: n L   c j x j  min (max) j 1 n a j 1 ij x j  bij ,i  1, m x j  R, j  1, n Пример: Задача о диете. Имеются четыре вида продуктов П1, П2, П3, П4. Известна стоимость каждого продукта с1, с2, с3, с4. В рационе должно быть белков не менее b1; жиров не менее b2; углеводов не менее b3 . Известно удельное содержание каждого вещества в единице продукта. Необходимо рассчитать рацион, содержащий необходимое количество полезных веществ и при этом чтобы стоимость всего рациона была минимальной.. Построим математическую модель. j – номер продукта ; i – номер вещества aij – удельное количество в j – ом продукте i – го вещества (например., а23 =30г/кг). Введем величину хj – количество j-го продукта в рационе (управляемая переменная), величины сj , аij , bi неуправляемые параметры–константы. Выберем критерий L – общая стоимость рациона. Тогда целевая функция и ограничения имеют вид L=с1х1+с2 х2+с3 х3+с4 х4 → min (2.1) 13 а11 х1+а12 х2+а13 х3+а14 х4 ≥ b1 а21 х1+а22 х2+а23 х3+а24 х4 ≥ b2 ( 2.2) а31 х1+а32 х2+а33 х3+а34 х4 ≥ b3 Математически эту задачу можно сформулировать так: найти такие значения х1, х2, х3, х4, чтобы они удовлетворяли системе линейных неравенств и при этом линейная функция L была бы минимальной. В компактном виде это можно записать 4 L   c j x j  min (2.3) a (2.4) j 1 ij x j  b j , i  1, m(i  1,3) j xj  0 (2.5) Термин ЛП буквально означает линейное планирование. 2.1. Общая и основная задачи ЛП Моделируя реальную задачу, мы можем получить задачу ЛП с некоторыми особенностями : 1) в одном случае L → min , в другом- L → max. 2) в ограничениях могут быть знаки : ≥ , ≤ , =, >, < 3) переменные могут быть любыми (как положительными, так и отрицательными ). Рассмотрим стандартную (основную) форму задачи ЛП , будем сокращенно называть ее ОЗЛП. В ней : 1) целевая функция минимизируется : L → min; 2) ограничения только равенства; 3) все переменные неотрицательны : x j  0,  j ; Любую задачу ЛП в общем виде можно привести к ОЗЛП, для чего необходимо выполнить следующие действия : 1. Если L → max, необходимо ввести L‫ – = ׀‬L , тогда если L → max , то L ‫ → ׀‬min ,и при этом arg min L‫ = ׀‬arg max L. 2. Чтобы привести неравенство к равенству, необходимо : - перенести все части неравенства в одну сторону (ту, которая ≥ 0); - полученную функцию обозначить новой дополнительной переменной, которая ≥ 0; Это обозначение является равенством, эквивалентным неравенству. Пример: 14 2 x1  x2  x3  4 x1  x2  3x3 Введем дополнительные переменные у1  0, y 2  0 : ; y1  0 y1  2 x1  x2  x3  4 ; y2  0 Ясно, что за переход к равенству приходится платить увеличением числа переменных. 3. Пусть xk – переменная с любым знаком. Представим ее разностью двух положительных переменных. Тогда, если вместо xk подставить разность х k  х к/  х к// , то остаются только неотрицательные переy2  x2  3x3  x1 менные: Пример: L  х  3х  х  max 1 2 3 х1  2 х 2  х3  3 x1  x 2 x1  0; x 2  0, x3  любое 1. L   L   х1  3х 2  х3  min 2. y1  3  х1  2 х 2  х3 3. х3  х4  х5 y 2  х1  х 2 Получили ОЗЛП: L/   х1  3х 2  х 4  х5  min y1  3  х1  2 х 2  х 4  х5 y 2  х1  х 2 ; ( х1 , х 2 , х 4 , х5 , y1 , y 2 )  0 Таким образом, ОЗЛП в общем виде можно записать так: L   c j х j  min (2.6) а (2.7) i jхj  bi , i  1, m х j  0, j  1, n (2.8) В матричном виде: СX min , AX=B, X>=0. Известно, что система линейных уравнений (СЛУ) (2.7) совместна, когда ранг матрицы А равен рангу АВ; A = {aij}, B = {bi}. Но допустимыми решениями задачи ЛП являются не все, а только ≥ 0 решения, т.к. должно 15 выполняться (2.8). Если m = n, то может быть только одно решение; если m < n – то может быть бесчисленное множество решений, но таких, которые удовлетворяют системе (2.7). Эти точки образуют так называемую область допустимых решений (ОДР). 2.2. Геометрическая интерпретация задачи ЛП Рассмотрим частный случай n-m=2. Тогда m переменных выбираются базисными, а (n – m) – свободными . Рассмотрим такую систему, где х1 , х2  свободные х3 , х4  базисные х3   31 х1   32 х 2   3  х 4   41 х1   42 х 2   4     х n   n1 х1   n 2 х 2   n  (2.9) L   1 х1   2 х2   0  min Рассмотрим (2.9). Пусть х3  0 : 31х1   32х2  3  0 – уравнение прямой. Значит для x3>0 точки лежат по одну сторону от этой прямой. Покажем это штриховкой. Аналогично для других равенств (2.9). Очевидно, точки, где все штриховки пересекаются и есть ОДР. Область допустимых решений (ОДР) содержит все точки, удовлетворяющие задаче. Рассмотрим теперь целевую функцию L: Пусть L  C1 :  1 х1   2 х 2  C1   0 -уравнение прямой; Пусть L  C 2  C1 :  1 х1   2 х 2  C 2   0 - уравнение прямой; Точки на прямой L = C2 лучше, чем L = C1 (в области), т.к. они дают меньшее значение целевой функции. Оптимальное решение получается в точке выхода линии уровня целевой функции L (точка А) из ОДР. Отсюда ясно, что в задаче ЛП внутри ОДР не может быть оптимальной точки. Выводы из геометрической интерпретации ОЗЛП 16 1)ОЗЛП не обязательно имеет решение. Нет допустимого решения. 2) ОДР всегда выпуклый многоугольник: 3)Если есть допустимое решение, то не обязательно есть оптимальное решение. ОДР может быть открытой, в этом случае оптимальной точки может не быть, если целевая функция изменяется как показано в I (движемся в открытую область). Но если область открыта, то это не значит, что нет оптимального решения. Для целевой функции II оптимальное решение находится в точке А. 4)В задаче может быть бесчисленное множество оптимальных решений. Оптимальное решение будет в любой точке АВ. 5)Если оптимальное решение есть, то его необходимо искать в вершине многоугольника. Признаком вершины является пересечение двух прямых, т.е. при равенстве нулю двух переменных. 6)Если n-m=2, т.е. в ОЗЛП две свободные переменные. Тогда, чтобы попасть в вершину, можно приравнять к нулю две свободные переменные. 17 7)Если взять две переменные равными нулю, то мы можем попасть в недопустимую вершину (т.1). т.1 ((х3=0) и (х5=0)). Чтобы перейти в соседнюю вершину т.2, нужно вместо x5 =0 взять x4=0, а x5 не равно нулю. Получаем т.2 ((х3=0) и (х4=0)). Допустимую вершину назовем опорной. Рассмотрим случай, когда n – m = 3. х 4   41 х1   42 х 2   43 х3   4  х4  0  плоскость х4  0  полупространство Тогда ОДР – выпуклый многогранник. L   0   1 х1   2 х2   3 x3 –> min - целевая функция (при L= const – плоскость). Допустимые решения находятся во внутренних точках многогранника, а оптимальное, очевидно, может находиться только в вершине многогранника в точке «последнего» касания плоскости – целевой функции и многогранника, где пересекаются 3 плоскости, т.е. 3 переменных равны нулю. Если в общем случае n – m = k, то у задачи k свободных переменных. Следовательно, нужно искать оптимальное решение там, где k переменных равно нулю. Т.к. в вершине в особом случае может пересекаться и большее число плоскостей, то в оптимальной точке  k переменных должны быть равны нулю. Заметим, что это является необходимым условием оптимального решения для задачи ЛП. 2.3. Идея симплекс-метода решения задачи ЛП Рассмотрим ОЗЛП, где базисные переменные xk+1,…,xn разрешены относительно свободных x1,x2,…,xk . Например: L  2 x1  3x2  ...  5 xk  6  min, xk 1  2 x1  3x2  x3  ...  6 xk  4, xk  2  x1  x2  x3  ...  7 xk  7, ..... xn  2 x1  2 x2  3x3  ...  xk  2. (х1=х2=…хk=0) – вершина, при этом базисные переменные 18 хk+1=4, хk+2= - 7, хn= 2. В ОЗЛП все переменные должны быть ≥0, следовательно, эта вершина недопустима. Признаком недопустимости вершины является наличие отрицательных свободных членов в ограничениях равенствах. Если отрицательный свободный член есть, то надо перейти в другую вершину, для чего одну базисную переменную сделать свободной и приравнять к нулю, а какую-то свободную превратить в базисную. Следовательно, переход из одной вершины в другую осуществляется путем замены базисной переменной на свободную. Это называется симплекс преобразованием. Если мы будем переходить из вершины в вершину «в сторону ОДР», то за конечное число таких переходов попадем в допустимую вершину. Назовем ее опорной вершиной, а соответствующее решение опорным решением. Пусть получено опорное решение, например, для следующей задачи. Проверим, оптимально оно или нет. x3  2  x1  x2 x4  4  x1  x2 L  3  2 x1  x2  min x1  x2  0; x3  2; x4  4; L  3. Видно, что если все коэффициенты при свободных переменных в целевой функции положительны, то никакие увеличения свободных переменных от 0 вверх не уменьшают L, следовательно, это L является оптимальным значением. Если же есть отрицательные коэффициенты при свободных переменных, (в нашем примере при x2 ), то ее надо сделать базисной, т.к. если она будет положительной, то L будет меньше. Но х2 может увеличиваться не бесконечно, так как в ограничениях есть отрицательный коэффициент при x2. Видно, что увеличивать x2 можно только до х2=2, так как в противном случае х3 будет отрицательным, а это невозможно. Так мы нашли базисную переменную x3 , которую надо поменять со свободной x2. Поиск этой пары для симплекс-преобразования и является основным элементом симплекс-метода. Таким образом симплекс-метод – это метод решения задач ЛП, который основывается на процедуре перехода от одной вершины к другой до тех пор, пока не придем в оптимальную вершину. Он состоит из трех алгоритмов: 1) Алгоритм перехода из одной вершины в другую, когда известна пара преобразования. Он пересчитывает коэффициенты системы уравнений для нового базиса. Назовем его алгоритмом симплекспреобразования. 19 2) Алгоритм нахождения такой пары преобразования, чтобы при переходе в новую вершину мы приближались к ОДР. Это алгоритм отыскания опорного решения. 3)Алгоритм нахождения такой пары преобразования, чтобы новая опорная вершина давала лучшее значение целевой функции. Это алгоритм отыскания оптимального решения. В симплекс-методе начинают со стандартной вершины (все свободные переменные равны нулю), т.е. с точки 1 ( это недопустимая вершина, смотри рисунок). Дальше последовательно переходим из одной вершины в другую (2,3) и попадаем в опорную вершину 4. Найдя опорное решение, мы движемся по вершинам ОДР так, чтобы целевая функция улучшалась, и при этом эти вершины были опорными (5 и 6 –оптимальная). Эти три алгоритма гарантируют либо отыскание оптимального решения, либо доказательство отсутствия допустимого решения, либо доказательство отсутствия оптимального решения. 2.4. Симплекс-таблица, стандартный алгоритм симплекс-преобразования Существует много форм симплекс–таблиц (СТ). Мы рассмотрим наиболее компактную форму, в которой строки – базисные переменные, а столбцы свободные переменные. Каждая СТ содержит коэффициенты модели задачи ЛП.. Для записи СТ необходимо представить ОЗЛП в стандартной форме: L   0  ( 1 х1   2 х2   y1  b1  (11х1  12 х2   y2  b2  ( 21х1   22 х2    y n  bn  ( n1 х1   n 2 х2   , т.е. на первом месте свободный член, а коэффициенты при свободных переменных меняют знак. 20 Пример: L  2 x1  x3  4 y1  2 x1  x2  x3 y 2  3x1  x2  x3  1 y3  2 x1  x2  2 Стандартная форма: L  4  (2 x1  0 x2  1x3 ) y1  0  (2 x1  1x 2  1x3 ) y 2  1  (3x1  1x2  1x3 ) y3  2  (2 x1  1x2  0 x3 ) Записываем коэффициенты этой формы в левый верхний угол соответствующей клетки СТ. В нижней части будем писать промежуточные результаты вычислений (см. ниже). 1 L y1 y2 y3 x1 4 x2 -2 -2 -1 1 -1 -3 -2 -1 -1 -1 3 -2 1 1 3 -1 x3 -1 1 -1 1 -3 -1 1 1 Табл. 1 Каждое решение, соответствующее CТ выглядит так: Свободные = 0, базисные = свободным членам. x1  x2  x3  0 y1  0; y 2  1; y3  2 L= 4. Рассмотрим порядок вычислений для перехода в новую вершину. 21 Пусть нам необходимо выполнить симплекс – преобразование xi ↔ xj. Тогда нужно получить новую симплекс-таблицу. Для этого выполним алгоритм. Алгоритм 1: 1. Отыскиваем в СТ элемент  ij и объявляем его генеральным. Тогда i – ая строка и j – ый столбец – генеральные. Вычисляем величину, обратную генеральному элементу и записываем ее в нижней части генеральной клетки. 2.  1 aij Все элементы генеральной строки умножаем на λ. Результат записываем в нижней части соответствующих клеток. Все элементы генерального столбца умножаем на -λ. Результат записываем в нижней части клеток. Отмечаем верхние элементы генеральной строки и нижние элементы генерального столбца. В каждой клетке, не принадлежащей ни генеральному столбцу, ни генеральной строке, в нижнюю часть записываем произведение отмеченных элементов, стоящих в том же столбце и той же строке, что и данная клетка. Переписываем СТ, заменяя: 3. 4. 5. 6. 7. 1 L y1 y2 y3 x1 x2 x3 4 -2 1 -1 1 -1 -2 -1 3 -1 -1 -1 -5 1 1 Табл. 2  обозначение базисной переменной xi обозначением свободной переменной xj.  элементы генеральной строки и генерального столбца нижними элементами.  все оставшиеся элементы суммой нижнего и верхнего числа. 2.5. Алгоритм отыскания опорного решения задачи ЛП Этот алгоритм выполняется сразу после записи симплекс-таблицы. Алгоритм 2: 22 1) Просматриваем столбец свободных членов (не смотря на свободный член строки L). Если все свободные члены ≥0, то данная таблица уже соответствует опорному решению, иначе переходим к п. 2. 2) В столбце свободных членов выбираем первый по порядку отрицательный элемент и в этой строке находим еще один отрицательный элемент. Если такого элемента нет, то задача ЛП не имеет решения, если есть, то переходим к п. 3. 3) Столбец с найденным отрицательным элементом объявляем генеральным. 4) В генеральном столбце фиксируем элементы, имеющие такой же знак, что и знак соответствующих свободных членов, и среди них в качестве генерального элемента выбираем тот, отношение к которому соответствующего свободного члена минимально. b min  i i a  ij  , знак bi = знак a ij   5) По выбранному генеральному элементу выполняем стандартное симплекс- преобразование (алгоритм 1) и переходим к п. 1. Если при вычислениях нет ошибок, то количество отрицательных свободных членов должно уменьшаться или должна уменьшаться их абсолютная величина. Примечание к пункту 2: Задача ЛП не имеет решения, когда соответствующая строка СТ имеет, например, вид: y4  1  (2 x1  x2  4 x3 ) , которая не удовлетворяется ни при каких неотрицательных переменных. 2.6. Алгоритм отыскания оптимального решения задачи ЛП Этот алгоритм выполняется после того, как найдено опорное решение, то есть в симплекс-таблице все свободные члены ≥0. Алгоритм 3: 1) Просматриваем элементы строки L (не смотря на свободный член). Если все элементы ≤0, то данная симплекс-таблица уже соответствует оптимальному решению, иначе переходим к п. 2. 2) В строке L выбираем наибольший положительный элемент и соответствующий столбец объявляем генеральным. 3) В генеральном столбце находим положительные элементы. Если таких нет, то задача не имеет оптимального решения, иначе переходим к п. 4. 23 4) Среди положительных элементов генерального столбца выбирается тот, отношение к которому соответствующего свободного члена минимально. b min  i i a  ij  , bi  0 , aij  0   5) По выбранному генеральному элементу осуществляем симплекс преобразование (алгоритм 1) и переходим к п. 1. Примечание к п.2. Если в генеральном столбце нет положительных элементов, то задача не имеет оптимального решения – целевая функция уменьшается неограниченно (движется в открытую область). Это значит, что в исходной модели не учтено какое-то важное ограничение. Схема алгоритмов решения задач ЛП имеет вид: ОЗЛП Симплекс-таблица Нет допустимого решения Алгоритм отыскания опорного решения Получено опорное решение Алгоритм симплекс преобразования Алгоритм отыскания оптимального решения Нет оптимального решения Пример: Решить задачу ЛП 24 Алгоритм симплекс преобразования Получено решение L= х1+х2→max х2≤х1+2 х2≥1 х1≤4 (х1,х2)≥0 Решение: Приведем задачу к ОЗЛП: L’= -х1-х2→min у1= х1-х2+2 у2= х2-1 у3= 4-х1 1 L’= 0 - ( х1 + х2 ) у1= 2 - ( - х1 + х2 ) у2= -1 - ( 0х1 - х2 ) у3= 4 - ( х1 + 0х2 ) 2 1 1 Х1 1 L’ У1 2 У2 -1 У3 4 1 -1 1 -1 -1 1 1 1 1 -1 1 Х2 -1 25 Х1 1 2/1=2; -1/-1=1(min) 2/1=2; -1/-1=1(min) В таблице 2 получено опорное решение: х1=у2=0, y1=1, х2=1, у3=4, L’=-1. В таблице 2 выполняем алгоритм отысоптимального решения: 3 L’ -1 У1 1 Х2 1 У3 4 1 У2 1 -4 -1 -1 1 4 1 -1 1 4 1 кания 1 У3 У1 4 У3 1 L’ У1 Х2 Х1 -5 -1 -5 5 1 -1 1 5 1 L’ 1 У2 1 Х2 -1 1 1 -1 1 1 5 4 У2 -10 -2 1 5 1 1 6 1 1 4 1 Х1 В таблице 4 получено оптимальное решение: у3 = у1= 0, у2= 5, х2= 6, х1= 4, L’= -10, Lmax= 10. Так как в данной задаче всего две свободных переменных, то можно рассмотреть ее геометрически на плоскости. Так как у1= 0, у3 = 0, то решение находится в точке, в которой выполняются равенства: х1-х2+2= 0 и 4 - х1 = 0 . На рисунке показана последовательность перехода от 26 вершины к вершине в соответствии с работой алгоритма симплекс-метода. Цифрами обозначены соответствующие симплекс-таблицы. 2.7. Алгоритм получения первого базисного решения с использованием симплекс – процедуры (метод искусственного базиса) Выше было показано, что алгоритмы симплекс-метода требуют, чтобы исходная система ограничений равенств была приведена к базису, т.е. какие-нибудь базисные переменные должны быть выражены через свободные. Оказывается, что первый базис можно так же получить, используя алгоритм симплекс-метода. Для этого для каждого ограничения-равенства вводится искусственная переменная zi,( i=1,m). Каждое ограничениеравенство i - (gi1 x1 + ... + gin xn) = 0 формально записывается так: zi =i - (gi1 x1 + ... + gin xn), i=1,m , т.е. переменные zi тождественно равны нулю. Последнее равенство определяет так называемый искусственный базис. Вводим в рассмотрение дополнительную целевую функцию Lo = z1 + z2 + ... + zm  min , для чего суммируем коэффициенты при переменных xj всех равенств zi и получаем ОЗЛП, готовую для решения симплекс-методом. Решая эту задачу на основе вышеприведенных алгоритмов последовательно выводим из базиса все искусственные переменные zi. При этом, как только переменная zr становится свободной, то столбец zr исключается из симплекс-таблицы. ПРИМЕР. Пусть исходную задачу ЛП мы привели к форме ОЗЛП и получили систему ограничений-равенств x1 + 2 x2 = 4 x1 - x2 + 2 x3 = 2 Найдем первый базис, т.е. разрешим базисные переменные (их всего будет 2) относительно свободных (n-m=3-2=1). Для этого запишем z1 = 4 - (x1 + 2 x2) z2 = 2 - (x1 - x2 + 2 x3) Lo = z1 + z2 = 6 - (2 x1 + x2 + 2 x3)  min (2.10) 27 Запишем симплекс-таблицу Таблица 1 L0 Z1 Z2 1 6 X1 2 X2 1 -4 4 -2 1 2 2 -2 2 X3 2 -1 (1) -4 1 -1 -2 2 2 1 -1 2 В Таблице 1 находим генеральный элемент по алгоритму нахождения оптимального решения, получаем пару для симплекс преобразования и переходим к Таблице 2, в которой исключаем столбец z2 Таблица 2 1 X2 2 L0 -2 2 Z1 -2 -1 2 (3) 2/3 2 Х1 X3 3 -2 1/3 -2/3 -1 2/3 2 1/3 -2/3 В таблице 2 находим генеральный элемент и пару z1 ↔ x2, переходим к таблице 3. Таблица 3 1 L X2 X1 28 X3 2/3 -2/3 8/3 4/3 Таблица 3 соответствует оптимальному решению вспомогательной задачи (2.10) и дает выражение базисных переменных x1, x2 относительно свободной переменной x3, а именно: x2 = 2/3 + 2/3x3; x1 = 8/3 - 4/3x3. Теперь можно приступать к выполнению симплекс - алгоритма, записав вместо строки Lo целевую функцию задачи, выраженную через свободные переменные. Чтобы такая запись получалась автоматически можно в таблицу 1 кроме строки Lo записать строку целевой функции исходной ОЗЛП и выполнять описанный выше алгоритм, помня, что генеральный элемент не может быть ни в строке Lo, ни в строке ЦФ. 2.8. Вырожденная задача ЛП При использовании симплекс-метода некоторые свободные члены могут быть равны нулю. Это значит, что в вершине, которой соответствует CТ, равны нулю не k переменных, а больше (равна нулю и базисная). В этом случае при выборе генерального элемента отношение bi/aij будет минимальным именно для этой строки. Ясно, что соответствующую свободную переменную увеличить никак нельзя и целевая функция при переходе в новую вершину не меняется, т.к. мы остаемся фактически в этой же вершине, хотя формально перешли в новую.. Такая задача называется вырожденной задачей. Вырождение отрицательно сказывается на эффективности вычисления. Признаком вырожденности является равенство 0 некоторых свободных членов. В этом случае может произойти 2 отрицательных явления: 1) «Пробуксовка». Переходим в новую вершину, где равна нулю другая совокупность переменных, а на самом деле остаемся в той же точке. Значение ЦФ не меняется. 2) «Зацикливание» алгоритма. Через некоторое количество операций мы можем прийти к первоначальной таблице, следовательно, если алгоритм не менять, то зацикливаемся. Существует несколько способов борьбы с зацикливанием: Использование степени свободы алгоритма. Например, если в алгоритме сказано: «берем первый по порядку…» - то, если обнаруживается зацикливание, можно взять «второй по порядку». Аналогично, если сказано «берем любой…». 2. «Зашумление» коэффициентов задачи ЛП. Прибавляем матрицу малых случайных величин к матрице А. Получаем А + ξ, где А – матрица коэффициентов; ξ – матрица очень малых случайных величин. Тогда матрица коэффициентов СТ не будет содержать одинаковых чисел и после 1. 29 вычислений появление нулей будет маловероятным. Подробнее этот сложный вопрос освещен в специальной литературе. 2.9. Двойственная задача ЛП Важным вопросом анализа полученного решения ЛП является анализ чувствительности решения к параметрам модели (коэффициентам целевой функции, свободным членам ограничений, коэффициентам аij). Теория этого вопроса тесно связана с так называемой двойственной задачей ЛП. Двойственная задача ЛП получается из прямой и она имеет физический смысл, когда прямая задача – задача об использовании ресурсов. Имеются ресурсы m типов в колчестве b1, … bm. Для изготовления одного изделия j – го типа расходуется aij сырья i-го типа. Каждое j – ое изделие продается по цене сj. Ставится задача максимизации стоимости проданных изделий. n L   c j x j  max (2.11) j 1 n a j 1 ij x j  b j , i  1, m (2.12) x j  0, j Можно рассмотреть эту проблему по-другому. Пусть некоторые величины ∆i – стоимости единицы i – го ресурса. Нужно определить эти стоимости так, чтобы выполнялись неравенства, выражающие то, что стоимость затраченного ресурса на j – е изделие была бы не меньше стоимости изделия и при этом общие затраты на ресурсы были минимальны. m L*   bi  i  min (2.13) i 1 m a  i 1 ij i  cj (2.14) j=1,…n Задача (2.13), (2.14) называется двойственной по отношению к задаче (2.11), (2.12) Она получается из прямой (2.11), (2.12) так: коэффициенты целевой функции двойственной задачи – это правые части прямой задачи и наоборот; а коэффициенты aij – суммируются по другому индексу (Матрица коэффициентов двойственной задачи это транспонированная матрица прямой задачи). Направление оптимизации целевой функции меняется на противоположное. 30 Основное свойство задачи ЛП: оптимальное значение целевой функции прямой и двойственной задачи ЛП совпадают. n L*опт   c j x *j   bi *i j 1 i 1 Оптимальное решение задачи ЛП находится в седловой точке: * max L по хj = min L по ∆i. Существует и двойственный симплекс – метод решения задачи ЛП, который в ряде случаев эффективнее прямого [1, 10]. Экономический смысл двойственной задачи: какова цена единицы каждого ресурса ∆i, чтобы при заданных количествах ресурсов bi и стоимости единицы продукции сj обеспечит минимум общей стоимости затрат. ∆i называется двойственной оценкой или теневой ценой. Если решение прямой найдено, то ∆i – есть коэффициенты, стоящие с троке L в последней оптимальной CТ. Если ∆i > 0, то она показывает насколько увеличивается значение целевой функции прямой задачи, если соответствующие запасы сырья i – го типа увеличиваются на единицу. Соответствующая дополнительная переменная yi при этом равна нулю. Это означает, что i – ое ограничение выполняется точно (как равенство) и весь ресурс bi тратится полностью. При малом изменении коэффициентов модели оптимальное решение задачи ЛП не меняется, такое свойство называется устойчивостью. На рисунке показано, что для ЦФ1 решением является точка А, для ЦФ3 *(при малом изменении коэффициентов cj также- точка А, а для ЦФ2 решением уже будет точка В. Существуют специальные программы, которые позволяют проанализировать пределы изменения коэффициентов cj , при которых оптимальное решение не изменяется, а значение целевой функции меняется. Аналогично проводится анализ по правым частям bi . Современные алгоритмы ЛП способны с использованием современных компьютеров решать задачи ЛП очень большой размерности. Многие из них учитывают архитектуру компьютера. Наиболее широко известны блочные методы ЛП. При большой размерности матрица А будет содержать много нулей. В этом случае задачу можно решать по блокам. Вот почему параметрами сложности решаемой зада31 чи ЛП являются: число переменных, число ограничений и число ненулевых коэффициентов ограничений. Число итераций симплекс- метода, за которое находится решение в большей степени зависит от числа ограничений. Современные программы ЛП имеют удобный интерфейс, позволяющий моделировать и решать небольшие задачи в удобной «математической» или табличной форме. Для решения задач ЛП большой размерности используются режимы работы с крупными базами исходных данных. (Смотри программы LINDO, а также приложение «Поиск решения» (SOLVER) программы Microsoft EXCEL. 32 3. Транспортные задачи (ТЗ) 3.1. Математическая модель ТЗ по критерию стоимости Симплекс – метод является общим для любой задачи ЛП. Но существуют специальные задачи ЛП, которые имеют более простой и наглядный способ решения. Постановка транспортной задачи: Имеется m пунктов А1 ...Аm отправления, в каждой из которой сосредоточено определенное количество груза ( а1 ...аm ). Груз однородный, ве- аi называется запасом. Имеются n пунктов назначения B1,…Bn, где требуется количество груза ( b1 ...bn ); величина bi - заявка. Известна стоимость перевозки c ij - из i – го пункта в j – й пункт. личина Требуется так перевезти грузы , чтобы запасы не были превышены, заявки выполнены и общая стоимость перевозки была бы минимальной. Введем дополнительное требование – так называемое условие правильного баланса: m n  a  b i 1 i j 1 j Модель: x ij - количество груза, перевозимого из i – го в j – ый. m n L   cij xij  min (3.1)  ai , i  1, m   j 1  m xij b j , j  1, n   i 1 (3.2) i 1 j 1 n x ij xij  0, i, j m n i 1 j 1  a i  b j (3.3) Особенности модели ТЗ: 33 1. 2. 3. 4. Наличие условия баланса (3.3) приводит к тому, что задача ТЗ всегда имеет решение. Просуммировав левые части (3.2), получим (3.3), следовательно одно уравнение в (3.2) линейно зависимо, значит ранг системы (3.2) будет (n + m – 1). Коэффициенты при переменных в (3.2) все равны единице. Подсчитаем число свободных и базисных переменных. Всего переменных m  n . Базисных ( m  n  1 ). Свободных переменных будет m  n  m  n  1  k , k  (m  1)  (n  1) . Т.е. практически все переменные свободные. Т.к. ТЗ является задачей ЛП , то в оптимальном решении все свободные переменные должны быть равны нулю, т.е. большинство маршрутов не будут задействованы. Если m=100; n=100; всего маршрутов (переменных) 10 000, но не более 199 будут задействованы. 3.2. Нахождение опорного плана транспортной задачи Все условия транспортной задачи можно записать в так называемой транспортной таблице. В ней выполняются и все необходимые вычисления. Пример : Стоимость перевозки I B1 B2 B3 ai A1 4 5 3 11 6 A2 Перевозка (кол-во единиц в маршруте) 1 2 5 2 7 7 4 8 5 4 7 A3 3 A4 2 3 5 4 4 bj 5 16 9 30 Таблица 1 Назовем x ij «перевозкой». Решение ТЗ, также как и ЛП решается в 2 этапа: 1. 34 Находится опорный план, т.е. допустимый план соответствующий условию «вершины». В нем отличных от нуля перевозок не более (m+n-1). Путем последовательного перехода от одного опорного плана к другому получаем оптимальный план. Метод «северо-западного угла» (СЗУ) для нахождения опорного плана ТЗ. Он заключается в заполнении плана перевозок, начиная с самих верхних (северных) пунктов отправления за счет самых левых (западных) пунктов назначения. Величина перевозки определяется выражением: 2. xij  min{ ai , bj } (3.4) ai и b j - остатки запаса и заявки после предыдущей итерации. Этот способ обеспечивает линейную независимость столбцов. Свойство допустимого плана: сумма перевозок по строке равна запасу, а по столбцу – заявке. План называется невырожденным если отличных от нуля перевозок ровно m+n-1. В вышеприведенном примере: m + n – 1 = 4 +4 – 1 = 7=7, т.е. план невырожденный. Выполненные действия показаны в таблице 1 Определим стоимость плана: L  4  5  5  4  14  2  2  3 1  5  3  5  2  76 Часто бывают такие транспортные задачи, где количество ненулевых перевозок (базисных клеток) меньше, чем m + n – 1. Пример: Базисных клеток 4, а должно быть 5. Задача вырожденная. Будем дополнять план до невырожденного: в опреA1 3 4 (0) 7 +0 деленных местах проставим символическую бесконечно малую величину A2 1 1 (0), чтобы выполнялась линейная независимость столбцов и условие невыA3 2 2 рожденности. Чтобы автоматически определять место для дополнения плаbj 3 4 3 на будем избавляться от вырожденности в процессе заполнения плана в соответствии с выражением (3.4). Вырожденность появляется тогда, когда в формуле (3.4) будет ai\=bj\ . В этом случае будем считать, что в строке ai\=ai\ + (0). Метод минимального элемента. В методе СЗУ мы не использовали стоимость перевозок. Существуют методы, которые позволяют получить первый план сразу близким к оптимальному (т.е. с достаточно малой общей стоимостью перевозок). Метод минимального элемента состоит в том, что порядок заполнения плана соответствует возрастанию стоимости. Но при этом запас исчерпыB1 B2 B3 ai 35 вается полностью, т.е. перевозка ставится в соответствии с формулой (3.4) в клетке с минимальной стоимостью в строке, если не исчерпали запас или в столбце, если не выполнили заявку. Метод не обязательно гарантирует лучшее решение, чем метод С ЗУ, но, как правило, дает лучшие результаты. Способ борьбы с вырождением такой же, как и в предыдущем методе. Пример: Начинаем с самого дешевого маршрута (А1В4), далее в столбце В4 ищем самый дешевый ( А4В4) , затем в строке А4 минимальная стоимость 2 в маршруте (А4В2) и т.д. B1 5 A1 A2 A3 B2 B3 4 B4 3 ai 1 9 2 4 1 2 9 1 3 2 8 7 3 5 4 A4 2 3 4 bj 4 2 1 6 5 10 9 3 8 5 25 L  9 1  1 2  2  4  3  8  5 1  4  2  1 2  58 3.3. Оптимизация плана ТЗ, распределительный метод Если в плане есть свободные клетки, для которых стоимость меньше, чем в базисных клетках, то можно передвинуть какую – либо перевозку в эту свободную клетку, но чтобы баланс не нарушался, нужно из строки или столбца, где будет новая базисная клетка, убрать такое же количество груза. Будем ставить (+) там, где перевозка увеличивается и (-) там, где уменьшается. Пример: Т.О 36 -   1  5 103  10 1 5   511 5 L  553 + 4 5 5 6 4 10 + 1 3 - 5 6 необходим перенос по циклу. Назовем циклом замкнутый маршрут, который показывает перенос груза по некоторым клеткам таблицы. В цикле всегда четное число вершин. Назовем ценой цикла алгебраическую сумму стоимостей перевозок c ij , стоящих в вершинах цикла с соответствующими знаками. Цена показывает, насколько увеличится стоимость перевозок в плане, если по данному циклу переносится единица груза. Если   0 , то стоимость уменьшается. При переносе по циклу величины груза k стоимость уменьшается на L  k   . Будем рассматривать только правильные циклы: одна вершина в свободной клетке, а все остальные в базисных. В свободной клетке, знак всегда «+», в остальных вершинах цикла знаки чередуются.. Для невырожденной транспортной таблицы с независимыми столбцами справедлива теорема о том, что для любой свободной клетки существует правильный цикл и при том только один. Таким образом для любой свободной клетки можно построить правильный цикл и вычислить его цену. Если она больше нуля, то переходим к другой свободной клетке. Если   0 , то строим цикл. Очевидно, по циклу нужно перенести наибольшее количество груза. Эта величина k определяется как наименьшая из перевозок, стоящих в вершинах цикла со знаком «-». Для нижеприведенного примера цена цикла 1-5+3-10 = -11. Величина k=5. Значит перенеся 5 единиц, мы уменьшаем общую стоимость на величину 5(-11)=-55 единиц. - 10 + 1 10 5 + 1 5 3 - 4 5 3 6 9 5 1 Перенос груза по циклу соответствует симплекс–преобразованию. Метод непосредственного отыскания циклов с отрицательной ценой называется распределительным методом. Рассмотрим пример решения ТЗ этим методом Пример: Т1 B1 B2 B3 B4 ai 37 A1 4 5 2 A2 A3 2 + 4 2 1 3 1 + bj 2 1 2 4 3 1 1 3 + 1 - 2 3 5 Т2 A1 4 5 6 B1 1 4 A3 Для первой таблицы m + n -1 = 3 + 4 – 1 = 6; B3 2 5 1 4 2 + 1 bj B4 3 3 1 2 1 4 - 5 2 ai 1 + 2 2 A2 5 B2 4 3 5 B3 B4 3 5 6 L  2  4  1 2  3  4  2  3  11  5  4  49 Строим правильный цикл для свободной клетки (3,1).  31  1  4  2  4  3  1  3 k 31  1; L  3 Для второй таблицы L  4  4  8  9  1  20  46 Строим цикл для (1,4) получаем таблицу 3, далее строим цикл для клетки (3,3) и переходим к таблице 4. В таблице 4 строим цикл для клетки (2,4).  24  2  4  1  3  4; B1 Т3 4 A1 bj 2 4 + 2 2 5 A2 A3 B2 2 1 2 1 3 1 + 2 4 1 + 2 1 3 4 - 4 3 ai 3 5 6 5 k 24  1; L  4; L  34 Дальнейшее решение предлагается проделать самостоятельно. Очевидно, для того, чтобы процесс остановился необходимо проверить все свободные клетки и убедиться, что цена циклов для каждой такой клетки больше нуля или равна нулю. С учетом того, что количество свободных клеток этот процесс очень трудоемок. (m  1)  (n  1) и т.д. Т4 A1 B1 B2 4 B3 2 B4 1 1 3 38 ai 3 .Т.о недостатком распредели5 4 - 3 2 A2 5 тельного метода является необхо4 1 + димость перебирать циклы до 1 2 + 1 4 A3 6 встречи цикла с отрицательной 2 2 2 ценой. Для доказательства оптиbj 2 4 3 5 мальности нужно перебрать и построить правильные циклы для всх свободных клеток. Если n=100, m=100, то свободных клеток будет 9801. Рассмотрим метод, в котором автоматически находятся циклы с отрицательной ценой. 3.4. Метод потенциалов решения ТЗ Пусть каждый пункт отправления Ai платит за вывоз единицы груза платеж αi. И каждый пункт назначения Вj платит за привоз единицы груза βj. Эти платежи передаются посреднику. Таким образом, на маршруте ij он ~ . Назовем эту величину псевдостоимостью. Оказыполучает  i   j  c ij вается, что суммарная псевдостоимость плана перевозок есть величина постоянная (не меняется с изменением плана). В этом заключается теорема о платежах. Для доказательства запишем формулу псевдостоимости и перегруппируем слагаемые: m n m n n m m n ~m n L  c~ij xij   ( i   j )  xij    i  xij    j  xij    i ai    j b j  const i 1 j 1 i 1 j 1 i 1 j 1 j 1 i 1 i 1 xij j 1 Теорема о потенциальном плане ТЗ. Пусть в базисных клетках стоимость перевозок равна псевдостоимости c  c~ , x  0 c~  c , xij  0 ij ij ij перевозок ij , а в свободных клетках ij гда такой план является оптимальны и улучшен быть не может. , то- cij  c~ij , xij  0   c~ij  cij , xij  0  (*) Доказательство: m n L*   cij xij* , Знак (*) означает , что выполняется условие (*). i 1 j 1 Т.е. необходимо показать, что стоимость плана X* является нижней границей и определяется только исходными данными задачи. 39 L*   c~ij xij*  const (т.к. в базисной cij  c~ij , а в пустой равно { xij } нулю). Перейдем к другому произвольному плану m n {xij* }  {xij } : L   cij xij i 1 j 1 В этом плане перевозка из базисной клетки попала в свободную, где m n cij  cij  L  L*   c~ij xij*  const . i 1 j 1 * Т.е. любое изменение плана от { x ij } приводит к увеличению стоимости, следовательно план {x*ij} является оптимальным. Идея метода потенциалов основывается на этой теореме и заключается в следующем. 1)Составим любой опорный план и, если это необходимо, то дополним до невырожденного. ~ . Запишем в левом верхнем уг2)Потребуем в базисной клетке cij  c ij лу базисной клетки величины псевдостоимостей, равные стоимостям, стоящим в правом верхнем углу. Таких клеток m + n – 1. 3)Находим неизвестные нам платежи  i и  j из условий, что их сумма известна для каждой базисной клетки.  i   j  сij   изв.  неизв. m  n  1    В такой системе в каждой строке две неизвестных, а всего их (m + n). Т.к. равенств всего (m + n -1), то решений бесконечное множество. Поэтому будем брать произвольное  1 и полагать, например, 1  0 . Тогда можно начать решение со строки, где содержится  1 .и так последовательно переходя в строки с известным платежом найти все платежи. 4)Найдя все платежи, подсчитываем  i   j  сij для свободных клеток. ~  c , сво5)Проверяем условие (*) для свободных клеток. Там, где c ij ij бодная клетка дает цикл с отрицательной ценой, т.к. 40  ij  cij  c~ij . 6)Выбираем цикл с наименьшим (наиболее отрицательным)  ij и со- ставляем цикл. По циклу переносим k единиц груза и т.д. до выполнения условия (*). Пример. Опорный план построим по методу минимального элемента, вычисляем платежи и определяем псевдостоимости в свободных клетках. Видим, что в клетке (3,2) цена цикла отрицательная. Строим цикл, переходим в таблицу 2. Т1 B1 -2 4 A1 A2 A3 -1 5 1 2 1 B2 B3 B4 3 2 -2 1 4 4 6 + 4 2 -1 3 1 3 1 1 3 2 1 4 1 1 2 + 4 - bj 2 4 3 5 βj -2 3 -2 1 Т2 A1 A2 A3 B1 B2 B3 B4 2 4 3 2 2 1 3 5 4 3 3 1 2 1 4 3 2 1 2 1 3 1 1 3 2 2 1 +0 2 4 bj 2 4 3 5 βj 2 3 2 1 ai αi 3 5 1 6 2 ai αi 3 5 1 6 -1  32  4 k 32  1; L  3 Заметим, что если при вычислении k минимальных перевозок две и более, то при переносе по циклу появятся дополнительные свободные клетки, т.е. план вырождается. Поэтому в этом случае считаем, что в одной такой клетке k, а в других k +(0) (( 0) – лучше поставить там, где дешевле маршрут). 41 B1 Т3 A1 A2 A3 B2 1 4 2 5 1 2 1 B3 B4 2 3 3 2 1 1 4 2 3 2 1 2 1 3 1 1 2 5 1 1 2 4 bj 2 4 3 5 βj 1 2 1 1 ai αi 3 5 1 6 План таблицы 3 оптимальный, т.к. выполняется условие (*). 3.5. Решение ТЗ с неправильным балансом До сих пор мы считали, что в ТЗ выполняется условие правильного баланса, то есть m n i 1 j 1  ai   b j . На практике это никогда не выполняется. Но можно ТЗ с неправильным балансом привести к правильному балансу и показать, что оптимальный план, найденный для ТЗ с правильным балансом, является оптимальным и для ТЗ с неправильным балансом. Рассмотрим 2 случая: 1. ТЗ с избытком запаса: m n i 1 j 1  ai   b j . Будем считать, что излишки запасов якобы перевозятся в некоторый фиктивный пункт назначения. Чтобы учесть фиктивность перевозки, достаточно считать, что стоимость перевозки в фиктивный пункт Вф равны нулю, сiф=0. Тогда, если какие-то перевозки хiф>0, то ciф хiф  0.  Таким образом, чтобы решать ТЗ с избытком запаса, нужно к таблице прибавить дополнительный столбец Вф, заявка которого bф   ai  b j , а сiф=0, i  1, m . Тогда для новой таблицы будет выполняться условие правильного баланса. После этого задача решается любым способом. 42 2. ТЗ с избытком заявок: m n i 1 j 1  ai   b j . Необходимо ввести фиктивный пункт отправления (Аф), в котором якобы есть недостающий запас aф  b j  ai , при этом сфj=0,  j  1, n . После этого задача решается обычным способом. Заметим, что при таком подходе в итоговом оптимальном плане не все заявки будут выполнены. Иногда задача решается по-другому. Пусть m n i 1 j 1  ai   b j . Тогда мож- но вычислить коэффициент дефицита: m k  ai i 1 n . bj j 1 После этого каждую заявку можно скорректировать: b  b k j j  a  i При этом можно решать задачу с учетом приоритетов на заявку. Величина приоритетов j-го пункта назначения (dj) может быть от 0 до 1 (0≤dj≤1). bj n d j  1. j 1 Чем меньше dj, тем выше приоритет.    b j   ai , Δ – величина дефицита. b j  b j  d j  . Пример: ТЗ с избытком запасов (58<68), поэтому введем фиктивный столбец, находим опорный план методом минимального элемента, а далее находим цикл с отрицательной ценой (2,1). 43 Т1 B1 B2 A1 6 A2 4 B3 5 11 + 7 - 4 8 bj 8 Bф 1 35 2 21 4 12 14 10 3 3 + 21 A3 ai 36 14 10 Если цикл с отрицательной ценой видно сразу, то не обязательно применять метод потенциалов. k=8, γ=3 Для таблицы 2 применим метод потенциалов: Т2 B1 A1 6 A2 4 8 4 A3 B2 6 5 11 4 3 13 7 3 12 B3 Bф Ai i 5 1 14 3 -1 1 0 10 2 -2 35 21 -2 3 -1 4 -2 12 -2 bj 8 36 14 10 j 6 5 1 Видно, что во всех свободных клетках псевдостоимости ≤ сij, следовательно, нет цикла с отрицательной ценой. План таблицы 2 оптимальный. 3.6. ТЗ по критерию времени, типы критериев Пусть ТЗ задано время tij, за которое груз можно перевезти из i – го в j – ый пункт. Оно не зависит от количества перевозимого груза. Заданы запасы 44 аi, заявки bj и необходимо составить такой план перевозок, чтобы общее время окончания перевозок было бы минимальным.. Т.к. перевозки осуществляются параллельно, окончание всех перевозок определяется длительностью маршрута с самой большой величиной tij среди занятых маршрутов (базисных клеток). Таким образом, критерий в нашей задаче (3.5) T  (max t )  min ij xij  0 Ограничения те же:   b j , j  1, n   i 1  n xij  ai , i  1, m    j 1 m x m ij n  a  b i 1 (3.6) i j 1 (3.7) j (3.5) – ( 3.7) – математическая модель ТЗ по критерию времени. Видно, что целевая функция T ( xij ) имеет нелинейный вид. При изменении плана {xij} критерий T может не меняться. Критерии такого рода называют гарантирующими или максиминными (минимаксными). Они требуют оптимизации по так называемому «узкому месту». В этом смысле рассмотренный в предыдущих параграфах критерий общей суммарной стоимости перевозок является интегральным критерием. Т.к. целевая функция T ( xij ) имеет нелинейный вид, то для решения ТЗ по критерию времени нельзя применить теорию линейного программирования. Для ее решения можно построить последовательность нескольких задач линейного программирования. Мы рассмотрим более простой эвристический алгоритм. Эвристическими алгоритмами называют такие алгоритмы, которые обеспечивает разумность поиска оптимального решения, но не основываются на строгой математической теории и всвязи с этим не вполне гарантируют результат (не доказана сходимость к оптимальному решению, не изучена точность и т.п.). Тем не менее эвристические процедуры чрезвычайно распространены, например, при игре в шахматы, при составлении компьтерных программ и т.д. Метод запрещенных клеток 45 1. Находим любой опорный план (необязательно невырожденный). 2. Вычисляем величину критерия для полученног плана T1  max t ij . { x1ij } 3. Запрещаем все маршруты в свободных клетках, у которых время t ij  T1 . 4. Зафиксируем в плане занятую клетку с максимальным t ij (узкое место). 5. Ищем цикл, при помощи которого можно «разгрузить» эту клетку и переносим по этому циклу перевозку величиной k. Циклы не обязательно должны быть правильными. Причем может быть, что освободить такую клетку можно только за несколько циклов . 6. Получаем план с новым значением T2  max t ij . Запрещаем сво{ xij2 } бодные клетки , для которых t ij  T2 и переходим к п.4. Повторяем до тех пор, пока будет невозможно составить ни одного цикла, разгружающего занятую клетку с максимальным временем.. Пример. Для нижеприведенной ТЗ по критерию времени составляем первый опорный план, получаем Т1 = 3. Запрещаем все свободные клетки, у которых t ij  3 . Используем неправильный цикл, получаем новый план , в котором Т2 = 2 . Т1 A1 A2 A3 bj B1 + 3 19 2 3 B2 B3 1 1 10 1 + 2 ai + 2 30 1 15 19 11 45 Т1 = 3. 20 40 15 Т2 B1 3 A1 A2 B3 1 1 2 19 ai 19 1 10 3 A3 bj B2 2 11 2 1 15 19 11 45 Т2 = 2 Видно, что перевозку с временем t ij  2 уже нельзя перенести ни в одну строку, ни в один столбец, поэтому последняя таблица является оптимальной. 46 20 40 15 4. Дискретное программирование При моделировании различных задач возникает требование, чтобы какие – то управляемые переменные принадлежали специальному множеству. 1) Множество целых чисел – число людей, число датчиков, число самолетов и т.д. 2) Множество дискретных значений – это стандартные значения в производственных задачах , которые заранее зафиксированы (количество деталей в изделии, мощность электродвигателя и т.п.) В таких задачах приходится искать значения переменных, которые не являются любыми действительными числами. Искомые переменные должны принадлежать заранее зафиксированному множеству значений D. Такого рода задачи принадлежат классу задач дискретного программирования: k  f ( x, a)  min (4.1)  i ( x, a)  0, i  1, m (4.2) xD (4.3) В связи с чрезвычайной сложностью решения таких задач в общем виде, мы рассмотрим только наиболее важные методы. 1) Универсальные методы решения задач линейного целочисленного программирования на основе «классических» алгоритмов. 2) Специальные методы (модели) дискретной оптимизации, которые имеют особое практическое значение. Задачей линейного целочисленного программирования (ЛЦП) называют задачу вида: L   c j x j  min (4.4) a (4.5) ij x j  bi , i  1, m x j  Z , j  1, n (4.6) Если только часть переменных должны быть целыми , то задача называется частично – целочисленной. Тогда в (4.6) вместо n будет n1 0 – всегда! xi  [bi ]  {bi }  [ij ]x j  {ij }x j  [bi ]  [ij ]x j  {bi }  {ij }x j jS jS jS jS (4.23) Покажем, что если решение целое, то {bi }   [ ij ]x j  0 jS . ( 4.24) (4.22) представляет собой запись симплекс – таблицы для оптимального решения, но решение не целое. Рассмотрим строку с нецелым решением. 61 {bi }  0,0  {bi }  1 { ij }  0, x j  0  . Т.к. цательным целым числом. то величина (4.24) может быть только отри- Это необходимый признак целочисленности x i . Это условие можно считать правильным отсечением. Неравенство (4.24) приведем к равенству, введя дополнительную переменную y n1 : yn1  {bi }  {ij }x j jS (4.25) Если это ограничение добавить к предыдущим ограничениям , то оно отсекает полученное непрерывное решение. Т.к. в симплекс – таблице появляется отрицательный свободный член, то надо искать новое опорное и новое оптимальное решение. Алгоритм Гомори: 1. Решаем задачу ЛП. Находим оптимальное решение. Если в оптимальной симплекс – таблице все свободные члены не меньше нуля и целые, то получено оптимальное целочисленное решение. Иначе переходим ко второму пункту. {b } i 2. Находим строку с наибольшей дробной частью и для этой строки по (4.25) составляется правильное сечение и записывается дополнительной строкой в симплекс – таблицу и преходим к п.1. При целых коэффициентах задача ЛП сходится за конечное число шагов к точному решению Если в исходной задаче коэффициенты дробные и ограничения неравенства, то дополнительные переменные yi могут быть дробными и задача не является полностью целочисленной. В этом случае может получиться, что, если потребовать y  Z и построить отсечение (4.25), то целых решений может не быть. Тогда ограничения можно ослабить, считая x  Z , y  R . y n 1  {bi }   { ij }x j   { ij }y l jS lS (4.26) (4.26) – ослабленное условие. Если требуется, чтобы значение целевой функции было целым, то строим условие правильного отсечения по строке L. Пример: Решить задачу 62 L   x1  3x 2  min, 2 x1  x 2  4, 4 x1  3x 2  2,  3x1  2 x 2  3, x1 , x2  0 и целые числа. Сначала решим данную задачу без требования целочисленности симплекс-методом. Для этого запишем задачу в виде основной задачи линейного программирования (ОЗЛП) в стандартной форме: L  0  ( x1  3x 2 )  min, y1  4  (2 x1  x 2 ), y 2  2  (4 x1  3x 2 ), y 3  3  (3x1  2 x 2 ). Далее заполним симплекс-таблицу (табл.1). Т1 x1 1 x2 Это опорное решение, так как в столбце свободных чле3 1 1 L   нов при базисных перемен4 2 4 ных все коэффициенты поло4 2 1 жительны. Но решение не оп3 1 y1 тимально, так как в строке  -1 2 2 функции цели есть положи2 4 -3 тельный коэффициент при 1 1 y2 - 3 свободной переменной. Ищем оптимальное решение. 2 4 4 Делаем все необходимые 3 -3 2 преобразования в симплекс3 3 y3 -9 таблице для замены y 2 на x1 4 2 4 и переходим к табл.2. Это оптимальное решение задачи без требования целочисленности, так как в столбце свободных членов нет отрицательных коэффициентов при базисных переменных, а в строке функции цели L нет положительных коэффициентов при свободных переменных. Таким образом , x1опт  1 ; x 2 опт  0; L   1 . 2 2 Но это решение не удовлетворяет требованию целочисленности. Для построения правильного отсечения и ввода нового ограничения берется первое по номеру нецелочисленная переменная. В данном случае это x1 . 1 -3 63 Выпишем x1 из табл.2: Т2 1 x y L  1 2 y1 3 x1 1 2 y3 9 2  1 4  1 2 1 4 3 4 1 1 3    y 2  x 2 , 2 4 4  1 1  1 1  1       0  , 2 2 2 2 2     x1  2 2 9 4  5 2 1 1  1 1  1       0  , 4 4 4 4 4 3  3 3 1  3            1  . 4 4 4 4 4     3  4 1  4 Таблица 2 Применяя формулу (4.25) , получим y 4   1   1 y 2  1 x 2  - это новое 2  4 4  ограничение, которое определяет правильное отсечение. Перепишем это ограничение в стандартном виде y   1    1 y  1 x  и допишем его в 4 2 2 2  4 4  симплекс-таблицу 3. 1 y2 x2  L 1 2  1 4 1 2 y1 1 2 x1 y3 y4 64 1 2  1 2 1 2  3 4 1 3 4 9 2  5 2 1 4  1 4 -2 4 1 2 9 4 -1  3  3 2  1 4  1 4  3 4 1 4 3   1 4 2 -4 1 Для решения этой расширенной задачи без требования целочисленности необходимо найти опорное решение, так как в столбце свободных членов есть отрицательные элементы при базисных переменных. Делаем необходимые преобразования в табл.3 для нахождения опорного решения и переходим к табл.4. 1 L y1 x1 y3 4 3 y2 2 y4 -1 -2 1 3 -4 x2 -2 3 -1 -1 1 Решение оптимально и целочисленно: x1опт  0; x2опт  0; L  0 . Геометрическая интерпретация примера приведена на рисунке. данного (4.26) . 65 4.5. Метод ветвей и границ (МВГ) Метод ветвей и границ (МВГ) – это наиболее широко применяемый метод дискретного программирования. Он относится к комбинаторным методам. МВГ – метод последовательного анализа вариантов. 1960 г. – Лэнд и Дойг. Широкое распространение получил, когда с помощью этого метода был разработан алгоритм решения задачи коммивояжера. Название МВГ раскрывает основное содержание метода, он состоит из двух процедур: 1) ветвление вариантов решения 2) установление границ возможного для каждого анализируемого подмножества решений. В любой задаче все множество решений представляется в виде дерева вариантов, т.е. вводится принцип разбиения множества вариантов на подмножества вариантов. В каждой задаче может быть свой принцип разбиения. Для МВГ необходимо, чтобы, во-первых, был удобный способ перехода от множества к подмножеству, во-вторых, чтобы варианты не повторялись и чтобы ни один вариант не был упущен. Переход от одного варианта к другому осуществляется в соответствии с некоторым порядком (например, в лексикографическом порядке). Исходя из свойств задачи, физического смысла целевой функции устанавливаются границы возможного (иногда называемых «обещанием») для каждого подмножества, т.е. придумывается формула оценки для заданного подмножества. Оценкой множества вариантов называется такое значение ЦФ, которое не может быть улучшено ни на одном из вариантов оцениваемого множества. Оценка множества всегда не хуже оценки входящего в него подмножества. В частности, если в некоторой задаче добавляется ограничение, то оценка для этой задачи может только ухудшится или остаться неизменной. Оценка должна быть как можно более точной, т.е. приближаться к истинным значениям как можно ближе. Чем точнее оценка, тем чаще отсеиваются варианты. Действительно, если получено некоторое рекордное зна- z* , а наилучшая из оценок оставшихся для проверки подмно* жеств хуже z , то очевидно процесс дальнейшего улучшения z можно пречение ЦФ кратить. Чтобы это произошло как можно раньше, во-первых, надо чтобы первый рекорд был достаточно «хорошим», а во-вторых, оценки были как можно более точными. Рассмотрим МВГ применительно к любой задаче дискретного программирования. 66 z  f (x)  min (4.27) x G (4.28) G – некоторая область, которая определяется системой ограничений неравенств, а также типом переменных. На первом этапе вычисляют нижнюю границу целевой функции. Для этого снимают ограничение на тип переменных. Целевая функция может быть при этом только лучше (или равной), поэтому ее можно принять за оценку. Если  (G) - оценка множества G, то для задачи на min f ( x)   (G) . На втором этапе производится разбиение (ветвление) множества G. Само разбиение идет в процессе решения и зависит от результатов, которые получены в результате разбиения на непересекающиеся подмножества. Рассмотрим k-ую итерацию. Для дальнейшего разбиения выбирают так называемое перспективное подмножество (например то, которое имеет наилучшую оценку). Заметим, что при разбиении на следующем уровне получаемые оценки могут быть только хуже (или те же). Если G1  G0 , то (G1)   (G0 ) Как только на каком-то подмножестве вариантов, получено решение, удовлетворяющее всем ограничениям (в том числе специальному требованию на тип переменной) проверяется условие оптимальности МВГ. (k ) Условие оптимальности МВГ. Если на каком–либо подмножестве G  на * k – ой итерации получено некоторое решение x такое, что значение целе* (k ) (k ) вой функции равно оценке этого подмножества f ( x )   (G ), x  G и при этом сама оценка является наилучшей среди всех оценок ещё не разби(k ) (k ) Gi(k )  G0 тых подмножеств на этой итерации  (G )  min{Gi } , при этом i , * то решение x является оптимальным и улучшено быть не может. Действительно, в самом множестве G лучшего решения быть не мо* жет, а остальные оценки дают «обещание» решений хуже, чем x . В практических задачах можно ограничиться приближённым решением с точностью до ε. Пусть получено некоторое решение x и задана некоторая абсолютная точность решения ε: *   f x '  f x   , где x - неизвестное нам    точное решение.   f ( x)  min{ (G (k ) )}   i Если , то разница между точным оптимальным значением и приближённым тем более меньше ε. 67 Если , то    . 4.6. Алгоритм МВГ для задачи ЛЦП n z   c j x j  min j 1 n a j 1 j ( 4.29) x j  bi , i  1, m (4.30) x j - целое, j  1, n1 , n1  n (4.31) Для задачи ЛЦП (4.29), (4.30), (4.31) оценкой множества решений определяемых (4.30), (4.31) является оптимальное значение для задачи ЛП (4.29), (4.30). На рисунке точка А – решение задачи ЛП, а точка В – решение задачи ЛЦП. Кроме этого, для ЛЦП можно использовать простое правило ветвления вариантов. Получаем следующий алгоритм: 1. Отбросим (4.31) и найдем решение задачи ЛП. Если решение автоматически удовлетворяет (4.31), то оно является оптимальным. Иначе переходим ко второму пункту. 2. Рассмотрим какое–нибудь нецелочисленную переменную полученного решения xl  d l , l  {1, n1 } . По этой переменной производится ветвление, все множество решений разбивается на два: G1(1) : xl  [d l ]  1 G2(1) : xl  [d l ] Пример: x5  4  x5  4 4  7  x5  5 Снова решаем задачу на каждом подмножестве. Если оба решения не удовлетворяют (4.31), то в качестве перспективного выбирают то подмножество, где оценка лучше. Сравнение оценок производится среди всех еще не разбитых подмножеств. Как только на каком-нибудь подмножестве по68 лучено целочисленное решение, проверяем условие оптимальности. Если оно выполняется, то получено оптимальное решение. Если не удовлетворяется, то снова выбирают перспективное подмножество и продолжают поиск решения. 1. Если решения задачи ЛП нет, то соответствующее ее множество Gl   пустое. Ему необходимо приписать оценку +∞ (для z  min ). 2. Если все коэффициенты целевой функции целые, то оценку множества можно заменить на более сильную. Для задачи на min – на величину  (Gl ) - ближайшее целое с избытком. Для z  max на  (Gi ) . Пример: z   x1  x2  min 4.32 2 x1  11x 2  38  x1  x 2  7  4 x1  5 x 2  5  4.33 4.34 x1 , x 2 - целое Решим задачу (4.32, 4.33). Получим x0  ( 40 23 , );  (G0 )  f ( x0 )  7 9 9 G1(1)  {x1  4} G2(1)  {x1  5} Решив эти задачи, получим: x1  4; x 2  2 8 8  ;  (G1(1) )    6   6; G2(1)  O;  (G2 )   11  11 .  G1(1) - перспективное множество. Разбив его на два подмножества по x 2 , получаем: G1(,11) : ( x 2  2) & (1), (2) … G1(,22) : ( x 2  3) & (1), (2) … Переобозначим: G1(,11)  G1( 2) ; G1(,12)  G((22)) ; G2(1)  G((32)) Решим задачу на G1( 2 ) . Получим 3  3 x12  (3 ;2); G1( 2)   5   5 4  4 А на G 2( 2 ) получим : 69 1  1 G2( 2) : x22  (2 ;3), (G2( 2) )   5   5 2  2 G3(2)  O;   . Берем оценку первую по порядку, т.к. одинаковые: G1(,21) : ( x1  3) G1(,22) : ( x1  4) Переобозначим (получим 4 подмножества). (3) (3) (3) Решив задачу на G1  x1  (3;2); (G1 )  5 G2(3)  O; (G2(3) )   1  1 G3(3)  x3(3)  (2 ;3);  (G3(3) )    5   5 2  2 G4(3)  O;  (G4(3) )   Получено целочисленное решение x1(3)  3,2 . Применим условие оптимальности. f(3, 2) = -5 = min{-5, +∞, -5, +∞} = -5.  Выполняется условие оптимальности. Решение x1(3)  (3;2) * является оптимальным z  5 . Изобразим дерево решений: G0 x1  4   7 x1  5     6 (1) 1 G G x1  2   5 x1  3   5 x1  3; x2  2 70 G1(3) x1  3 G2( 2) G1( 2)   5 x1  4 G2(3)   (1) 2 4.7. Алгоритмы решения задач булевского программирования. Задача булевского программирования является наиболее часто встречающейся при проектировании технических средств, автоматизированных систем. Как показано выше любую задачу дискретного программирования, в свою очередь, можно привести к задаче булевского программирования. Для решения задач булевского программирования используется большое число методов прямого поиска. Все они похожи на метод ветвей и границ, так как в них происходит перебор вариантов и анализ подмножеств в целях отсеивания. Большинство алгоритмов используют частичный вид булевской формы. Из-за важности этого существуют специализированные процессоры для решения таких задач. Рассмотрим задачу линейного булевского программирования L   ci xi  max (4.34) i 1 n a x ij j  bi , i  1, m (4.35) i 1 x j  0,1 (4.36) n Существует 2 вариантов решения, часть из которых допустима. Известно, что при большом n придётся проверять все ограничений, каждое ограничение – это матрица. Рассмотрим процедуру перебора, положенную в основу аддитивного алгоритма Балаша [8]. Так как внутри метода всегда будет сравнение с рекордом, то необходимо, чтобы первое рекордное значение было достаточно большим. Поэтому переменные исходной задачи преобразовывают в соответствии с возрастанием (для задачи на максимум) коэффициентов целевой функции. c1  c2  c3  ...  cn В этом случае, мы будем перебирать с нулевого вектора, начиная справа. Пусть существуют правила, по которым можно выстроить ограничения в таком порядке, чтобы сначала было самое жёсткое из них, а далее мягче. Затем выбирают первый вектор списка и проверяют ограничения, если какое – то из ограничений не выполняется, то переходим к следующему вектору и т. д. Если для какого то вектора удовлетворяются все ограничения, то подсчитывается величина целевой функции и она объявляется рекордом. После этого процедура меняется. 71 Балаш предложил добавить некоторое фильтрующее ограничение. Идея его в том, что незачем проверять вектор на допустимость, если он не превосходит рекорда Z* . c x j 1 ij j  Z* (4.37) Если ограничение (4.37) не выполняется, то переходим к следующему вектору, в противном случае – к ограничению (4.35). Если новый вектор удовлетворяет всем ограничениям, то подставляя его в (4.34) получим новый рекорд Z * и формируем новое фильтрующее ограничение, заменяя Z * на Z ** . Если пройден весь список, то последний рекорд даёт решение. При этом мы экономим на проверке ограничений. Пример: z  3x1  x2  2 x3  x4  max 2 x1  x2  4 x3  x4  10  3 x1  2 x 2  x3  2 x 4  1 4 x1  x 2  2 x3  4 x j  {0,1} z   x2  x4  2 x3  3x1  max  x2  x4  4 x3  2 x1  10 (1) 2 x2  2 x4  x3  3x1  1 (2) (3)  x2  0  x4  2 x3  4 x1  4 Составим таблицу и получим первый допустимый вектор (0010) ; z=2. Составляем фильтрующее ограничение (0)  x2  x4  2 x3  3x1  2 . Находим новый рекордный вектор ( 0110); z=3, новое фильтрующее ограничение (0)  x 2  x 4  2 x3  3x1  3 Наконец находим новое рекордное значение (1111); z=5. Т.к. список исчерпан, то последний рекорд –это оптимальное решение. z max  5 x 72 1 1 1 1 1 + + + + 2 + - 3 (0) z 2 + + Эффективность процесса можно 0 1 0 0 оценить количеством значков в таб0 1 0 1 + + 3 лице. В современных алгоритмах 0 1 1 0 + + + + (например, в алгоритме Лемке – 0 1 1 1 + + Шпильберга ) порядок перехода от 1 0 0 0 одного вектора к другому меняется в 1 0 0 1 соответствии с анализом коэффициентов модели задачи: 1 0 1 0 1. критерий недопустимости – за1 0 1 1 + + прещает двигаться к некоторым век1 1 0 0 торам, которые заведомо недопусти1 1 0 1 5 мы. 1 1 1 0 2. Проверяются целевые функции 1 1 1 1 + + + + – множеству дается оценка (подробнее см.[7,10,23] ) В алгоритме Балаша используются и другие ограничения, позволяющие отсечь некоторые решения (см. [7] ). Рассмотрим некоторые из них. Рассмотрим правило, по которому можно отсеивать варианты. Пусть Nмножество индексов всех двоичных векторов. Подмножество множества N, состоящее из таких элементов j , что каждому j поставлено в соответствие x j 0,1 , называется частичным решением, а множество индексов обозначим V. Переменные , номера которых не принадлежат этому подмножеству, называются свободными , множество индексов свободных пременных обозначим S. Пример: Вектор переменных (x1,x2,x3,x4,x5). N=(1,2,3,4,5) (x1,0,1,x4,x5)- частичное решение, V=(2,3) S = N\V S= (1,4,5) - номера свободных переменных Если частичное решение содержит k переменных, то существует 2 nk различных дополнений частичного решения. Пусть каким – то образом выбрано частичное решение, содержащее k nk переменных, тогда проверка 2 его дополнений на допустимость по условию (4.35) называется зондированием. * Если до этого получен рекорд Z и если удаётся установить, что для какого – то частичного решения не существует допустимого дополнения, приводящего к лучшему рекорду, то говорят, что частичное решение прозондировано, т.е. что это подмножество можно отсеять. 73 Балаш установил, что если V определяет переменные зондированного решения, а Z * - ранее достигнутый рекорд, то зондируемое решение x не имеет допустимого дополнения, улучшающего условие:  min( a ,0)  b   a x , ij jS i ij j при любом i  1, m Z * , если выполняется (4.38) jV Например пусть задача содержит ограничения:  x1  2 x2  6 x3  4 x4  x5  0 x1  1, x2  1, x4  0   (1,3,4), N  (1,2,3,4,5), S  2,5 Проверим наличие допустимых дополнений для выбранного частичного решения. min( aij ,0)  1; a1 j x j  5; b1  a1 j x j  5;1  5.  jS  jv  jv Рассмотрим другое правило отсеивания вариантов. Если для некоторой свободной переменной xk имеет место соотношение min( aij ,0)  aik  bi  a1 j x j , i 1, m  jS  jv ,то 0, если  aik  0 xk   1, если  aik  0 (4.39) Кроме этих двух правил можно использовать, так называемый, признак составных ограничений, позволяющий установить факт наличия или отсутствия допустимых дополнений некоторого частичного решения, путём анализа составного ограничения. В общем случае, это комбинация всех строк ограничений. Например, используется суммирование левых и правых частей ограничний. Пример: Пусть задача состоит из такого решения ограничения: -x1- x2 – x3 <= -1 2x2 -2x4+ 2x5 <= 0 xj={0,1} 74 которые имеют Максимизируется функция Z=2x1+x2+x3  max Пусть при некотором частичном решении рекорд составлял z=2. Определить, имеет ли частичное решение x1  0 допустимое дополнение, улучшающее достигнутый рекорд. Прибавим к ограничениям фильтрующее ограничение, то есть 2x1 + x2 + x3 >= 3 , получим новую систему ограничений: - x1 – x2 – x3 <= - 1 2x2 – 2x4 +2x5 <= 0 - 2x1 – x2 – x3 <= - 3 Сформируем составное ограничение и применим к нему признак (4.38) Получаем -4=-4, следовательно, ограничение выполняется, то есть при не существует дополнения, улучшающего рекорд z=2. На основе полученных правил запишем алгоритм. 1. Пуст ли основной список задач? Если «да», то вычисления окончены и переходим к п.5.Если «нет» - присвоим счетчику числа задач основного списка α значение т.е. вычеркиваем одну задачу. Счётчику числа итераций (В начале, очевидно, k = 1). 2. Существует ли допустимое дополнение при выбранном частичном решении, улучшающее значение рекорда ? Проверим условие (4.38). Если «да», то определяем эти значения по формуле (4.39) и переходим к п.3. Если «нет» - положим и переходим к п.1. 3. Содержат ли допустимое дополнение частичного решения и зондируемое решение n переменных? Если «да» - запоминаем решение, значение рекорда и переходим к п.1. Если «нет» - переходим к п.4. 4. Выбираем любую свободную переменную , не входящую в число допустимых переменных. Вводим две задачи в основной список (в одной , в другой ). Положим и переходим к п.1. Печать результата решения: рекорд и значения переменных либо «задача решения не имеет». Конец алгоритма. 75 5. Динамическое программирование (ДП) Это особый метод, который специально приспособлен для оптимизации динамических задач, в которых операция состоит из элементов, сильно влияющих друг на друга. ДП связано с именем Ричарда Беллмана, который сформулировал принцип оптимальности Беллмана. Он позволяет существенно сократить перебор решений в многоэтапных нелинейных задачах. Рассмотрим экономическую задачу распределения ресурсов: пусть есть k 0 . Его начальный капитал можно потратить на несколько предприятий P1 , P2 ,  , Pn . X ij  количество средств вкладываемых в i  ом году, в j  ое предприятие. В результате получается эффект: Wij  f X ij  В общем случае это нелинейная функция. Необходимо распределить Начальный капитал (ресурс) так, чтобы суммарный эффект от всех предприятий за все года был максимальным. W   f X ij   max X ij  k0 Так как функция W нелинейная, то получаем задачу нелинейного программирования при очень большом числе переменных (см. главу 6). Решать X  её сложно, кроме того, часто ij дискретные значения. Возникает вопрос : нельзя ли решить задачу последовательно, т. е. найти оптимальное вложение для первого года, второго и т. д., т. е. провести последовательную оптимизацию?. В большинстве задач так делать нельзя, т. к. решение , принимаемое на одном шаге оказывает влияние на последующие шаги. Рассмотрим простой пример. Проанализируем процесс забега стайеров на 800 метров. Каждый бегун имеет запас энергии x0, который он тратит на каждые 100 метров - величина затрат энергии xi. 76 ti – время бега стайера на отдельном участке i. T – общее время забега на 800м . 8 T   t i  min . i 1 Если уменьшать каждое ti отдельно, то за 800м время стайера будет хуже, так как у него не будет сил продолжать бег. Значит нужно бежать так, чтобы оставались силы на всю дистанцию. Очевидно, каждый бегун решает задачу: Σti(хi) → min; при условии Σхi ≤ х0. Казалось бы, чтобы сумма времен ti была минимальной нужно минимизировать каждое ti , т.е. бежать как можно быстрее первую стометровку, затем как можно быстрее вторую и т.д. Читатель, вспомнив свой опыт бега, конечно, понял, что такой способ оптимизации не верен. Оказывается, оптимальной величиной xi и , соответственно ti ,будет такая, которая обеспечит минимальное общее время бега за все 800 метров. Т.о. мы сформулировали принцип «действуй с прицелом на будущее». Другими словами оптимальность «в малом» необходимо понимать через оптимальность «в большом». Это чрезвычайно важный принцип системного подхода к оптимизации систем. 5.1 Принцип оптимальности Р.Беллмана Метод ДП является наиболее общим методом решения задач оптимального управления . Он применим как для задач с линейной ЦФ, так и с нелинейной , а также в случае, когда управляемые переменные целые числа, при этом сама ЦФ может быть задана таблицей, что наиболее распространено в практических задачах. Процессы называют динамическими, если результаты на одном участке процесса влияют на другие шаги. Рассмотрим принцип оптимального управления Р. Беллмана. Он связан с проблемой оптимизации сложной системы, состоящей из многих взаимосвязанных элементов. Элементами могут быть экономические единицы, которые входят в единую (более общую) систему; узлы сложной технической системы; отдельные участки производства, строительства, боевых операций и т.д.. Возникает вопрос: как нужно управлять отдельными элементами системы, чтобы показатель эффективности всей системы был максимальным? Выше мы на интуитивном уровне показали, что для оптимизации в целом недостаточно оптимизировать каждый элемент отдельно - это приводит к неверному результату. Беллман впервые сформулировал принцип оптимальности для такой задачи. То есть, оптимизируя отдельный шаг, необходимо задумываться о 77 его последствиях, приводящих к общему результату. Для решения подобных задач был разработан метод ДП , основывающийся на уравнении Беллмана, которое математически выражает его принцип. Назовем состоянием системы S один или несколько параметров системы. Например, деньги на лицевом счете предприятия. Обозначим управление на i-том шаге Ui – это некоторое воздействие, которое испытывает система изменяет свое состояние S. Если перед i-ым шагом состояние системы S и мы принимаем управление Ui, то за i-ый шаг мы можем получить некоторый выигрыш, который обозначается ωi(Si, Ui), при этом состояние S переходит в S’ S →S’=i(S, Ui). Считается, что функции ωi(Si, Ui), и i(S, Ui) известны ωi(Si, Ui) S S i+1 Ui Wi+1( S’) ωi(Si, Ui)+Wi+1(S’) Беллман ввел понятие условного оптимального выигрыша Wi(S). Эта функция показывает оптимальный выигрыш (наилучший результат), полученный за все шаги от i-го и до конца, если i-ый шаг начинается с состояния S. Тогда согласно принципу оптимальности Беллмана, принимая решение на i шаге, мы должны выбрать Ui так, чтобы выигрыш был максимальным от i-шага и до конца. Принцип оптимальности Беллмана ставит вопрос о том, что такое оптимальность отдельного элемента системы с точки зрения оптимальности всей системы. Принимая решение на отдельном этапе, мы должны выбирать управление на этом этапе с прицелом на будущее, т. к. нас интересует результат в целом за все шаги. Любой процесс имеет где-то окончание, т. е. говорят, что он имеет «горизонт планирования». Тогда последний этап «не имеет будущего». Вот именно его можно оптимизировать только из условий данного этапа. После этого приступают к оптимизации (m-1)-го этапа. При этом мы задаём состояние, с которого начинается (m-1)-ый шаг (условие). Поэтому функцию Wi S  называют условным оптимальным выигрышем. Таким образом, процесс оптимизации по методу ДП разворачивается сначала от конца к началу, а затем от начала к концу. В различных задачах может быть известно 78 либо начальное состояние, либо конечное, либо то и другое. Принцип Беллмана нашёл практическое применение в так называемом методе программно-целевого планирования (любое действие планируется как элемент некоторого проекта). 5.2. Решение графовых задач на основе принципа Беллмана. Задача о наборе высоты и скорости летательного аппарата. H 5 3 1 2 2 3 4 3 12 5 5 18 4 24 3 11 19 20 4 4 4 7 7 9 5 6 7 1 4 4 5 8 7 6 22 3 3 6 6 17 4 Sk 2 2 8 1 14 4 6 11 12 h0 6 12 17 5 15 2 4 3 11 16 3 19 5 19 S0 v0 Летательный аппарат находится на высоте Необходимо перевести его на высоту h1 V h0 и летит со скоростью v 0 . со скоростью v1 . Причём h1  h0 , v1  v0 . Разобьём участок от h0 до h1 на n частей: h h h  1 0 n v1  v0 v  m Известен расход горючего при переводе системы на h при v  const и на v при h  const . Таким образом, из каждого состояния есть лишь два управления. Начиная с конца помечаем все узлы (состояния) величинами условных (для данного узла) оптимальных расходов горючего от этого узла и до конца, a стрелками условные оптимальные управления . Указанные действия в упрощенном виде демонстрируют рассмотренную процедуру решения на 79 основе уравнения Беллмана.. Дойдя от конечного состояния до начального и получив 22, мы получим минимальную величину потерь горючего. Идя по стрелкам от начального состояния до конечного, мы получаем безусловные оптимальные управления (показаны двойной линией). Видно, что любая задача, сводящаяся к поиску минимального пути в графе, решается методом динамического программирования. 5.3. Функциональное уравнение Беллмана Назовём состоянием системы вектор координат: S  1 , 2 ,..., L . В некоторых задачах состояние - одна величина. Тогда работу системы можно представить как движение в фазовом пространстве - пространстве состояний. Назовём шаговым управлением - управление на i  ом шаге. Рассмотрим процесс управления системой за m шагов. Функция i S,U i  называется выигрышем на i-ом шаге. Здесь S-состояние перед i-ым шагом, а U i  управление на i-ом шаге. Величина i S, U i  должна быть известна до начала динамического программирования. Если состояние перед i-ым шагом было S и мы приняли какое-то управление U i , то система перейдёт в новое состояние S    i S ,U i  . Эта функция должна быть так же известна. Если эти функции не заданы, то их надо сформулировать. Введём функцию Wi(S) условный оптимальный выигрыш. Это выигрыш на всех этапах от i до конца, если iый шаг начинается с состояния S. Рассмотрим m шагов. Пусть с (i+1)-го шага мы системой управляем оптимально, тогда величина выигрыша будет такая- Wi 1 S . Применим на i-ом шаге произвольное управление Ui, тогда ~ Wi S   неоптимальный выиг- рыш, т. к. на i-ом шаге мы применяем неоптимальное управление U i . Чтобы от i-го шага и до конца получить оптимальный выигрыш нужно изменять Ui так, чтобы Wi S   max i S , U i   Wi 1 S ; Ui S    i S , U i    Wi S   max  i S , U i  Wi 1  i S , U i  U i неизв естно неизв естно  изв естно  Это функциональное уравнение Беллмана. Для использования уравнения Беллмана начинают с конца: 1) i=m 80 Wm S   max m ( S , U m ) Um 2) i  m 1 Wm 1 S   max  m 1 ( S , U m 1 )  Wm  m 1 ( S , U m 1 ) U m 1 Итак, идя от конца к началу, мы получаем последовательно: W m S , W m  1 S ,..., W 1 S  U m S ,U m1 S ,..., U1 S  Придя в начальное состояние W1(S), мы можем подставить S = S0 и W1(S0) = Wmax - это безусловный выигрыш. Теперь необходимо получить безусловные оптимальные уравнения, идя от начала к концу по цепочке: S=S0  U 1 S 0   U 1*   S 0 ,U 1*   S1*  U 2 S1*   U 2*   S1* ,U 2*  … Итак, в результате мы получаем оптимальное решение: U 1* ,U 2* ,..., U m* ;Wmax 5.4. Задачи распределения ресурсов. 5.4.1. Классическая задача распределения ресурсов Распределение ресурсов - это едва ли не самая распространённая операция. Под ресурсом в общем случае понимают физическую или абстрактную величину, которую система использует для производства полезного продукта. Например: горючее, деньги, время, объём склада. Как правило ресурс ограничен, поэтому встаёт задача так распределить ресурс между отдельными элементами системы, чтобы суммарный эффект был максимальным. Рассмотрим классическую задачу распределения ресурсов. k Имеется начальное количество ресурсов 0 , которые необходимо распределить между двумя отраслями. Каждая отрасль работает в течении m лет. Если в первую отрасль в i-ый год вкладываются средства X i , то доход 81 f X i  , g Y  Y i . Средства если же во вторую вкладываются i , тогда доход тратятся, принося доход, а новых средств не поступает и полученный доход не вкладывается. m W   f  X i   g Yi  i 1 Нас интересует суммарный доход: . Суммарный выигрыш равен сумме выигрышей на каждом шаге. Состоянием системы является количество средств перед i-ым шагом. Так как новых средств не поступает, то ресурсы «тают». Y  k  X i . После i-го шага в Управление Yi может быть записано как i  Yi    k  X i  . первой отрасли остаются средства   X i  , а во второй Эти функции называются функциями траты. Мы можем составить уравнение Беллмана. В этой задаче на i-ом шаге одно управление X i и одно состояние k Wi k   max  f  X i   g k  X i   Wi 1   X i    k  X i  Xi i  m : Wm k   max  f  X m   g k  X m  и ттд. Xm W1 k , k  k 0 ,W1 k 0   Wmax ; X 1 k 0   X 1* , Y1*  k 0  X 1* Исследуя функции Y траты, получим количество средств после i-го шага: k  X 1*   Y1*   k1* ; X 2 k1*   X 2* и ттд. Задача о распределении ресурсов допускает геометрическую интерпретацию. Y X 1  Y1  k0 Распределение на первом  (Y ) шаге - указание точки на гипотенузе. После этого средства k (X ) X X тратятся. Распределение средств - движение внутрь треугольника. Рассмотрим частные случаи задач о распределении ресурсов. 1 1 1 1 5.4.2. Неоднородные этапы и распределение ресурсов по n отраслям Распределение по неоднородным этапам. Выше мы считали, что все функции одинаковы на всех этапах. Во многих задачах функции меняются от этапа к этапу: 82 f i  X i , g i Yi ;  i  X i , i Yi  . Покажем, что процедура динамического программирования принципиально не меняется. Запишем уравнение Беллмана: Wi k   max f i  X i   g i k  X i   Wi 1  i  X i    i k  X i  Xi Видно, что при решении достаточно на каждом этапе всего лишь подставлять разные функции. Распределение ресурсов между тремя и более отраслями. В этом случае на каждом шаге будет уже n управлений, но одно из них n 1 может быть выражено как: X n  k  X j . В этом случае в правой части  i i j 1 уравнения Беллмана будет две или более переменных, по которым ищется максимум, и задача существенно усложняется. 5.4.3. Распределение ресурсов с резервированием В такой модели если средства распределяются между двумя отраслями, то какое-то количество средств можно оставить до последующего распределения. В этом случае задача имеет смысл даже для одной отрасли. Начальное количество средств разделяется на первом этапе на X1 и на k  X 1 (резерв), на втором этапе подлежат распределению оставшиеся средства и из резерва. Такую задачу можно представить с одной реальной отраслью, а другой фиктивной (не приносящей доход и не расходующей средства). На рисунках показаны графики распределения ресурсов с резервированием и в дополнение к этому с нулевыми функциями трат. Решение такой задачи сводится к классической, задав функции дохода и трат в виде: f  X , g Y   0 - функции дохода;   X , Y   0 - функции трат На рисунках показаны графики распределения ресурсов с резервированием и в дополнении с нулевыми функциями трат. Подставив их в уравнение Беллмана, можно решить задачу как классическую. Задача с резервированием в одной отрасли при нулевых функциях траты.  х   0 i Все функции траты В этом случае задача сводится к более простой. 83  хi   0 m W   f i ( xi )  max i 1  xi  k 0 Рассмотрим более частный случай: все функции одинаковые на всех шагах. f i ( x)  f ( x), i Пусть эти функции неубывающие, тогда недоиспользование средств невыгодно и в ограничении можно поставить равенство. m W   f ( xi )  max x i i 1 (5.1)  k0 (5.2) Эта задача имеет теоретическое решение: 1 Если функция f (x) неубывающая и выпуклая вверх, то оптимальным распределением является равномерное распределение: xi=k0/m. 2 Если функция f (x) неубывающая и выпуклая вниз, то оптимальным распределением является такое: все распределение в один этап (элемент) и ничего в другие:xr=k0, xi=0 для всех i , кроме i=r. Покажем это на графических примерах. 1. Пусть f (x) – выпуклая вверх, например f ( x)  W  x x1  x 2  max x1  x2  k 0 Тогда линии постоянного уровня W – это дуги линий астроид, симметричных относительно биссектрисы координат. Поэтому последнее касание астроиды гипотенузы треугольника при W  max будет в точке xi = k0/2. Очевидно, для m шагов будет xi = k0/m. 2. Пусть f (x) - выпуклая 84 вниз, например f ( x)  x 2 W  x12  x22  max x1  x2  k1 Из рисунка видно, что в этом случае решение будет лежать на оси координат, т.е. xr = k0. 5.4.4. Распределение ресурсов с “вложением доходов” В классической задаче считается, что полученный доход на i-ом шаге в производство не вкладывается, т. е. он отчисляется и подсчитывается как эффект. Во многих задачах полученный эффект можно использовать как ресурс для следующего шага, объединяя его с оставшимся ресурсом. Если ресурс не деньги, то средства нужно привести к единому эквиваленту с оставшимися средствами. Такая модель является развитием классической модели. Так как оставшиеся средства и доход объединяются, то можно ввести единую интегральную функцию - функцию изменения средств F(Xi) количество оставшихся средств плюс доход после i-го шага, если вложили Xi . I. II. F X i  GYi   Gk  X i  Где k -количество средств перед i-м шагом. Выигрыш на i-ом шаге зависит от того, как мы подсчитываем доход (эффект) от управления всеми ресурсами. Поставим задачу: максимизировать доход в конце m-го шага. Тогда на всех шагах i  1, m  1 , доход = 0, Wi  0 . На m-ом шаге выигрыш Wm  Fm  X m   Gm k  X m  . Подставив эти выражения в уравнение Беллмана, мы программируем задачу от начала к концу, если имеется начальное количество средств k . Здесь функция траты: k   Fi  X i   Gi k  X i  . Рассмотрим частный случай: когда F и G неубывающие функции. В этом случае чем больше значение доход + средства получается в конце i-го шага, тем лучшим условием это будет для проведения (i+1)-го шага. Поэтому можно не заботиться о следующих шагах, достаточно обеспечить максимум на каждом шаге. Таким образом, процедура оптимизации возможна в одном направлении от начала к концу, т. е. задача динамического программирования вырождается в задачу последовательной оптимизации. 85 maxF1  X i   G1 k0  X 1   k1* X1 maxF2  X 2   G2 k1*  X 2   k2* X2  * maxFm  X m   Gm km* 1  X m   km* W X max  k m m Рассмотрим задачу распределения ресурсов с вложением доходов в производство и отчислением. Это наиболее общий случай. Разделим f  X i , g Yi  функции дохода и функции траты:   X i , Yi  и максимизируем суммарный отчисленный доход + оставшиеся средства после m-го шага. Введём функцию отчисления ri Di  ; D-доход. Тогда выигрыш на каждом шаге: Wi  ri f X i  g k  X i , i  1, m  1 W m  rm f X m  g k  X m   X m   k  X m  m W  Wi  max (5.3) i 1 k    X i   k  X i  f X i  g k  Xi  ri f X i  g k  X i  Уравнение Беллмана для i-го шага будет выглядеть так: Wi k   maxri  f  X i   g k  X i   Wi 1   X i    k  X i   f  X i   g k  X i   ri  f  X i   g k  X i  Xi i  1, m  1 для i=m надо учесть (5.3). Если ri  1 , то мы получаем классическую задачу. 5.5. Расширение модели задач динамического программирования Учёт предыстории процесса. Мы считали, что все функции, как выигрыша, так и траты, зависят от состояния перед i-ым шагом, т. е. не зависят от более ранних состояний. Такие процессы называются процессами без памяти. Но иногда при рассмотрении некоторых процессов требуется помнить всю историю происходящего (например, в задачах ремонта и замены оборудования). Такая задача более сложна. Введём расширенное состояние: S  S , Si 1 , Si 2 , , Si L  86 S i L  состояние за L шагов до i-го. Тогда, считая аргументы векторами, функции не меняются i S , U i ,  i S , U i  . Но задача становится сложней в вычислительном аспекте. Пусть S имеет k координат и предыстория распространяется на L шагов, тогда в результате число переменных будет k  L . Вот почему подобные задачи практически можно решать если kL 3. ДП для задач со многими ограничениями Пусть в задаче распределения ресурсов есть два ограничения (два ресурса). m  W f  X i   max   i 1  m  a1i X i  b1   i 1  m  a2 i X i  b2  i 1  Введем два параметра состояния K1 и K2. Тогда функции условных оптимальных выигрышей и условных оптимальных управлений будут иметь по два аргумента W(K1, K2) ; xi(K1,K2). Уравнение Беллмана для решения такой задачи имеет вид Wi K1, K 2  max f i  X i   Wi 1 K1  a1i X i ; K 2  a 2i X i  ,      Xi При этом величина Xi на каждом этапе варьируется в пределах от нуля до величины di . di= min(K1/a1i ;K2/a2i) Видно, что для двух ограничений, если каждая из величин K1, K2 может принимать 102 значений, то функцию Wi(K1,K2) приходится табулировать в 104 точках. Таким образом, наиболее серьезным препятствием для практического применения ДП является число параметров задачи, что заставило Р.Беллмана заявить о так называемом «проклятии многомерности». Некоторые способы понижения размерности смотри в [10 ]. Задача с мультипликативным критерием. До сих пор мы считали, что суммарный выигрыш равен сумме выигрышей, полученных на i-х шагах. Но есть задачи, где общий критерий равен произведению критериальных величин на каждом шаге. m W   Wi i 1 87 В этом случае так же можно применить уравнение Беллмана., но вместо этого можно взять функцию W   ln W . Оптимальные решения будут одинаковы ввиду монотонности функций логарифма. Но можно при выводе уравнения Беллмана учесть, что: Wi S   max Wi  Wi 1 S  Ui W  F W1 ,W2 , ,Wn   F W1   F W2     F Wn  Т.о. метод ДП применим в случае, когда аргументы в критериальной функции разделяются (смотри вышеприведенное выражение) k Пример: устройство состоит из n узлов. Имеется некоторый ресурс 0 , который может использоваться для повышения надёжности каждого узла. Необходимо так распределить ресурс, чтобы суммарная надёжность была максимальной. Получаем задачу m q X i   надёжность каждого узла. Q   qi  X i   max i 1 . X i  k0 . Операции не связанные со временем. Во многих задачах распределение ресурсов не связано с временными шагами. Ресурс распределяется по объектам. Например, если рассмотреть распределение ресурсов между n объектами, когда на каждый объект задана функция выигрыша, то такая задача эквивалентна рассмотренной нами задаче о распределении ресурсов с резервированием в одной отрасли по n шагам. Это наиболее распространенная задача распределения ресурсов, поэтому приведем ее полное решение методом ДП. 5.6. Пример решения задачи распределения ресурсов Рассмотрим пример. Завод получил 4 новых станка, которые необходимо распределить между тремя цехами. Известна дополнительная прибыль, которая получится в i-ом цехе, если туда поставят хi станков – f(хi). Состоянием является оставшееся (текущее) количество станков (k). Пусть мы распределяем оставшиеся k станков. Начинаем с третьего (последнего) цеха: 88 6 5 3 f2 f1 4 2 1 1 2 3 4 7 6 5 4 3 2 1 1 2 f3 x1 3 4 x2 8 7 6 5 4 3 2 1 1 2 3 4 x3 W3 (k )  max{ f 3 ( x3 )} x3  k    ~ k Х3 ~ W3 1 1 2 1 2 3 1 2 3 4 1 1 3 1 3 7 1 3 7 2 1 2 3 4 W3 W3 1 3 7 7 89 х3опт 1 2 3 3 k 1 2 3 4 W3 1 3 7 7 Переходим к второму шагу W2 (k )  max{ f 2 ( x2 )  W3 (k  x2 )} x2 k k х2 ~ W2 1 1 1 2 1 2 3 1 2 3 4 1 3 3 4 3 7 6 4 6 2 3 4 k 1 2 3 4 3 4 7 7 10 6 7 1 х2опт 1 1 1 W2 10 W2 3 4 7 10 Переходим к первому шагу W1 (k )  max{ f1 ( x1 )  W2 (k  x1 )} x14 90 k Х1 ~ W1 W1 4 1 2 3 4 10 9 8 8 3 10 Так как начальное состояние известно, то для первого шага не нужно перебирать оставшееся число станков, и берем k=4: Ответ: х1*=0, k1*=4-0=4 (подставляем k1* в табл.4), х2*=1, k2*=4-1=3 (подставляем k2* в табл.2), х3*=3, k3*=4-3=1. 5.7. Эффективность динамического программирования Сравним по числу необходимых операций динамическое программирование с простым перебором всех вариантов для задачи n W=  f ( x )  max i i n a x i i b i Для упрощения расчёта примем a1=a2=…=an=1. При простом переборе число возможных вариантов решений (при условии целочисленности всех переменных) равно числу способов, которыми можно разместить b одинаковых шаров внутри n урн. Оно составляет C b n  b 1  (n  b  1)! . b!(n  1)! При n=5, b=20 имеем С 24  10626 . Оценим число операций, требуемых для решений этой задачи методом динамического программирования. Для вычисления Wi(k) при фиксированном k необходимо провести k+1 вычислений. Поэтому для заполнения одной таблицы Wi(k) необходимо проделать 4 b  (k  1)  k 0 (b  1)(b  2) операций. 2 91 Следовательно, для вычисления всех функций W1(k),…, Wn-1(k) необходимо ( n  1) Wn(b) (b  1)(b  2) операций. С учётом вычисления функции 2! общее число операций (n  1)(b  1)(b  2) (b  1)[( n  1)(n  2)  2] N   (b  1)  . 2! 2! При n=5, b=20 имеем N=945, что в 11 раз меньше, чем при простом переборе. 92 6. Нелинейное программирование 6.1. Особенности задач нелинейного программирования Нелинейное программирование (НЛП) - это такая задача математического программирования , в которой либо целевая функция, либо функции ограничений, либо они вместе представляют собой нелинейные функции. Термин НЛП применяется только тогда, когда все переменные Xдействительные числа. Решение задач НЛП намного сложнее решения задач ЛП, при прочих равных условиях. Рассмотрим особенности задач НЛП, а именно то, где может находиться оптимальное решение. Для Рис.1 этого будем рассматривать целевую функцию двух переменных. В НЛП используют геометрический образ целевой функции как некоторой поверхности, определённой на множестве управляемых переменных. Вид этой поверхности можно описать? изображая в области переменных так называемые линии уровня, (см. рисунок) Особенности задач НЛП проиллюстрируем графически на примере задачи F  x 1  1/2 2  x 2  12  min ,  x 1 x 2  a ,  x 1  x 2  b , 0  x  3; 0  x  3. 1 2  Изобразим графически область допустимых решений (ОДР) и найдем решение для различных значений a и b. Очевидно, что оптимальное решение будет находиться в точке, где линия уровня имеет самую малую величину в области допустимых решений (ОДР). Это можно представить как «последнее касание» линии уровня ОДР по мере уменьшения этого уровня. Линии уровня в этой задаче представляют собой концентрические окружности, а F min соответствует уменьшению их радиуса. 93 1) 2) b=2. (рис. 3) a =2, a =1/2, b=2. (рис. 4) Рис. 2 Рис. 3 Решение задачи на рис. 2 находится в точке С, где линия наименьшего уровня целевой функции касается прямой x 1  x 2  2 . Координаты оптимального решения x 1  3 5 ; x2  можно найти из простых геометриче4 4 ских соображений. Решение задачи на рис. 3 качественно отличается от первого случая, так как здесь получается две несвязанных ОДР, дающих две экстремальные точки А и В, являющиеся точками пересечения линий x1x 2  1 и x1  x 2  2 . 2 Точка B является точкой локального минимума, а точка А точкой глобального минимума. Ее координаты найдем, решив систему уравнений: 1  x 1 x 2  2  x 1  x 2  2 x 1A  1  2  0,3 2 x A2  1  2  1,7 2 . 3) a =2, b=1 рис. 4 Решение на рис. 5 находится в точке Д, являющейся координатами центра концентрических окружностей (линий уровня целевой функции). 94 Из приведенных примеров ясно, что решение задачи НЛП может находиться как внутри ОДР (рис. 5), на одной из границ в произвольной точке (см. рис. 3), так и в вершинах ОДР, являющихся точками пересечений функций ограничений (см. рис. 4), причем может получиться несколько экстремальных точек (см. рис. 4). Графическое изображение ОДР и линий уровня F(x) позволяет решать задачи НЛП с двумя переменными. 6.2. Прямые методы одномерной оптимизации нелинейных функций без ограничений Пусть на множестве U є R определена функция F(X). Под минимизацией функции F(X) на множестве U будем понимать решение следующей задачи: найти хотя бы одну точку минимума x* и минимум F*=F(X*) этой функции на множестве U. Многие приближенные методы минимизации применимы только тогда, когда любой локальный минимум F(X) является одновременно и глобальным. Один из классов функций, удовлетворяющих этому условию, является класс унимодальных функций. Функция F(X) называется унимодальной на отрезке [a;b], если она непрерывна на [a;b] и существуют числа α и β, a≤α≤β≤b, такие, что: 1) если a<α, то на отрезке [a; α] F(X) монотонно убывает; 2) если β0. Разобьем [a;b] на n равных частей точками деления Xi=a+i(b-a)/n, i=0, 1, 2, …, n, где n≥(b-a)/ε. Вычислив значения F(X) в этих точках, путем сравнения найдем точку xm, для которой F(Xm)=min F(Xi). (6.1) 0≤ i≤ n Далее полагаем x*=xm, F*=F(Xm). При этом максимальная погрешность εn определения точки X* равна εn=(b-a)/n. Метод деления отрезка пополам (метод дихотомии) является простейшим последовательным методом минимизации. Он позволяет для любой унимодальной функции F(X) построить последовательность вложенных отрезков [a;b] [a1;b1] … [an-1;bn-1] [an;bn], каждый из которых содержит хотя бы одну из точек минимума X* функции F(X). Рис.6 Рис.7 Пусть ε>0 – требуемая точность определения точки X*. Выбрав δ=2ε, построим последовательности {an}, {bn}, {X1(n)}, { X2(n)}, n=0, 1, … , используя рекуррентные формулы a0=a, b0=b; x1(n-1)=(an-1+ bn-1- δ)/2, x2(n-1)=(an-1+ bn-1+ δ)/2; ( 6.2) (n-1) (n-1) (n-1) an =an-1, bn = x2 , если f(x1 )≤ f(x2 ), an = x1(n-1), bn = bn-1, если f(x1(n-1))> f(x2(n-1)). 96 Переход от отрезка [an-1; bn-1] к отрезку [an; bn] методом деления отрезка пополам иллюстрируется на на рис.3, если F(X1(n-1))< F(X2(n-1)), рис.4, если F(X1(n-1))>F(X2(n-1)). Полагая x* = (an+ bn)/2, находим X* с абсолютной погрешностью, не превосходящей величины εn =(bn- an)/2=(b-a-δ)/2n+1+δ/2 Кроме этих методов известны и другие, более эффективные методы, такие как: метод Фибоначчи, метод золотого сечения, метод поиска по дискретным точкам. [12, 25] 6.3. Градиентные методы многомерной оптимизации Если ограничения в задаче НЛП отсутствуют, то применяют все методы оптимизации нелинейных функций. Причём, если в задаче с ограничениями решение гарантированно находится внутри области, то его можно найти этими методами, так как эти ограничения не являются активными и их можно отбросить. Рассмотрим наиболее широко применяемые методы оптимизации нелинейных функций многих переменных – это так называемые поисковые методы. Здесь поиск оптимальной точки начинают из начальной точки (ее выбирают из некоторых знаний о примерном месте нахождения решения). Далее в соответствии с некоторым разумным правилом переходят в новую точку с лучшим значением ЦФ и т.д. до тех пор, пока не выполнится некоторое заранее заданное правило остановки, например выполнение условия по точности. 6.3.1. Классический градиентный метод В этом методе поиска каждая последующая точка получается путем перехода по вектору градиента, т.е. по нормали к линии уровня. Длина шага, выбирается из двух основных условий: если длина шага очень большая, то можно перейти точку экстремума, если очень маленькая, то количество шагов от начальной точки до оптимальной будет очень велико. Поиск начинается из начальной точки X0. Точка X(k+1) ищется по формуле X(k+1)=X(k)±  g(X(k)) , (+) – если F(X) → max и (-) – если F(X) → min, (k ) 97 g(X(k)) – градиент в точке Xk , шага. В координатах X ( k 1) j (k ) - множитель, определяющий длину (k ) F  X (j k )  ( k ) ( ) x k . Величина  может в проX j стейшем случае не изменяться по мере движения (k ) =  = const . Теоретически окончание поиска определяется следующим условием: X (r ) - точка экстремума, (r ) если g( X ) = 0. На ри- сунке показаны траектории движения для а) – классического градиентного метода, б) – покоординатного метода, в) – метода наискорейшего спуска. Рис.8 Для практических вычислений правила остановки могут быть различr ны. Для простоты можно считать, что X является точкой экстремума , если max ( F ) ( r 1)   , где X j x  - заданная малая величина. Ясно, что этот метод можно применять в том случае, когда можно хотя бы численно вычислить градиент функции в точке. Заметим, что для гладкого оптимума при приближении к оптимальной точке величина градиента автоматически уменьшается, поэтому даже при постоянной величине λ длина шага уменьшается, что является желательным для любого поискового метода. 6.3.2. Покоординатный метод В этом методе движение из начальной точки производится сначала вдоль первой координаты x1. Знак направления совпадает с направлением проекции градиента на эту координату (для F(X) → max) или противополо98 жен ему, если F(X) → min. Конец шага определяется точкой, где F =0. X 1 Затем движение производится по второй координате X 2 , затем по X 3 и т.д., и наконец, по X n . Затем повторяют движение опять по X 1 , X 2 и т.д. Можно использовать следующее правило остановки: max ( F ) X j x ( r 1 )  . 6.3.3. Метод наискорейшего спуска и его модификации В этом методе из некоторой начальной точки движение осуществляется вдоль направления градиента до тех пор, пока производная по этому направлению не будет равна нулю. Далее из этой точки определяем новый градиент и т. д. Отличие здесь в том, что длина шага из точки X ляется из условия, чтобы обеспечить:  k опреде-   min F X k  g X k  0 Эту вспомогательную задачу одномерной оптимизации можно решать на основе рассмотренных методов прямого поиска (дихотомии и т.д.) Наискорейший и покоординатный методы называют методами с длинным шагом. Кроме этого существуют методы, использующие вторую производную для определения длины шага, например, метод Ньютона:    g X , X k 1  X k  F  X k 1 k где [F”(Xk)] -1 обратная матрица вторых производных в точке X 6.4. Метод деформируемого многогранника Нелдера-Мида Современные методы поиска минимума (максимума) нелинейной функции чрезвычайно разнообразны. Одним из наиболее эффективных является метод НелдераМида. Идея метода состоит в том, что для определения направления движения вычисляются значения целевой функции в вершинах сначала правильного, а затем деформируемого многогранника. Многогранник некоторое тело в n-мерном пространстве. Правильный многогранник называется симплексом, в задачах для двух переменных это Рис 9 правильный треугольник. 99 Вычисленные значения целевой функции в вершинах симплекса сравниваются, а затем выполняются операции: 1. отражение - поворот симплекса через одну из сторон; 2. растяжение - если идём в правильном направлении; 3. редукция - возврат назад, если перескочили оптимум; 4. сжатие - уменьшение сторон, чтобы движение было с более мелким шагом. В этом методе не используется понятие производной функции, что расширяет его возможности. Поиск оптимальной точки ведется путем поворота и деформации многогранника (симплекса) на основе анализа вершин в соответствии со следующими вышеприведенными операциями Пусть К – номер итерации, тогда алгоритм Нелдера-Мида заключается в следующем: 1. выбирается начальный симплекс (если в задаче 2 переменные n=2, то 0  симплекс–правильный треугольник). Его вершины X i , i  1, n  1 . Обо- X hk   самая худшая точка, т.е. для значим   F X     min F ( X F X nk   max F ( X ik ); k l k i k  X l(k ) ); . X 0 лучшая - F  X   min , точка, т.е. - центр тяжести всех вершин, исключая k h X , его координаты X 0k   1  n 1 k   k     X ij   X nj ; j  1, n n  i 1   k  2. Осуществляют отражение (проектирование) X h через центр тяжести, новая точка получается так:  X k   X 0k    X 0k   X nk   α- коэффициент отражения. Обычно α=1.  k  Если F X    F X    , то вектор k l раз и получаем:   X bk   X 0k    X аk   X 0k  ;  k  - Если для полученной точки F X b X k   X 0k  растягивается в γ   F X    , то X   k  k l k h заменяется на X b , и переходим к пункту 2. В противном случае заk  меняем X h 100 k  на X а и переходим к пункту 2.  k  - Если F X    F X    , для всех i≠h то вектор k h мается , получаем точку  X сk   X 0   X 0k   X hk  k k  Точка X h  λ раз заменяется на X c , и переходим к выполнению пункта 2 k    F X    , то все векторы k h (обычно X ik   X lk  1  0   1. k  - Если F X  в  X hk   X 0k  сжи- λ=2)- редукция X    X   ; k i X ik   X lk  уменьшаются k l i  1, n  1 . Возвращаемся к пункту 2. Правила остановки могут быть различными, например, 1 2  1 n 1 r r 2 F ( X )  F ( X )     i  1  n i 1   для простоты можно использовать правило: i  1, n  1 max X j ,i , p r i, j Рис.10 j  1, n  X pr , j   p  1, n  1 r  решением будет точка X 0 . Например: F ( X )  6 X 1  2 X 12  2 X 1 X 2  2 X 2  min выберем параметры:   1,   1 ,   2,   2,   0,1 2 решение видно из рисунка 10. Подробнее смотри в [16]. 6.5. Задача НЛП с ограничениями-равенствами. В НЛП особо рассматриваются задачи с ограничениями-равенствами. Это так называемые задачи на условный экстремум. Решение такой задачи производится с использованием функции Лагранжа. Эта функция позволяет построить новую целевую функцию, которая бы в виде штрафа учитывала ограничения: 101 m Ф X ,    F  X    i  i  X   bi  (6.3) i 1 F  X   целевая функция, λ – множители Лагранжа, имеющие смысл i коэффициентов чувствительности ограничений. Таким образом, задача минимизации нелинейной целевой функции с ограничениями-равенствами сводится к минимизации функции Лагранжа без ограничений. Для её решения используется классический приём: записываются необходимые условия существования экстремума: m   Ф  i  F 6.4   0, j  1, n;     i    X j X j i 1  X j    Ф    X   b  0, 6.5 i  1, m; i i   i После выполнения операций дифференцирования получаем систему в общем случае нелинейных уравнений относительно неизвестных Xi и λi множителей Лагранжа. Решение системы 6.4 и 6.5 дает точки подозрительные на экстремум и их ещё надо проверить с помощью достаточных признаков экстремума. Рассмотрим некоторые из этих признаков. * 1) Пусть X - точка подозрительная на экстремум, полученная с помощью выражений 6.4 или 6.5. Рассмотрим матрицу Гесса – матрицу H вторых производных в точке X*: H  2Ф X i X j Если эта матрица определена положительно, то точка X* -минимум, а если определена отрицательно, то максимум. Если же матрица Гесса знаконеопределена, то в этой точке экстремума нет, а если полуопределена, то этот признак не даёт ответа на вопрос. 2) Пусть Dk главный определитель матрицы Гесса k-го порядка. 1. Если D1  0, D2  0, D3  0, - это достаточный признак минимума; 2. Если D1  0, D2  0, D3  0,  - достаточный признак максимума (знаки строгих неравенств чередуются); 3. Если же в определителях знаки  и  , то это необходимый, а не достаточный признак и вопрос об экстремуме не решается. 102 3) Наиболее «сильным» достаточным признаком является следующий. Составим расширенную матрицу Гессе HB, для чего используем матрицу производных от функций ограничений: 1   1 1    X n   X 1 X 2  0 Q   2  2  2   H      Q   X Q H   X  X  1 2 n           n  n   n   X X n   1 X 2 Q  - транспонированная матрица. Матрица HB имеет размерность (m+n)x(m+n). * Признак: точка X соответствует максимуму, если начиная с главного определителя порядка m+1, последние n-m определителей матрицы HB образуют знакопеременный ряд, а знак определителя стоящего на (n-m)-ом месте от конца должен совпадать с знаком: если (1) m1 , то max; если (1) m , то min. Например: n=3, m=2, n-m=1, проверяем n=7, m=4, n-m=3, проверяем D5 D9 Пример: F  X 1 X 2 max X1  X 2  1 Запишем функцию Лагранжа Рис.11 ( X 1 , X 2 ,  )  X 1 X 2   ( X 1  X 2 1)  max Найдем решение, используя необходимые условия    X2   0  X 1     X1    0  X 2     X 1  X 2  1  0   Получаем решение системы 103 X1  X 2 ; 1 1 ;  2 2 B Запишем матрицу H  0 Q 0 1   ; H=  H B =   Q H  1 0 0 1 1   B H =  1 0 1  n=2; m=1; m+1=2; n-m=1 1 1 0   X1  X 2  Начиная со второго определителя (m+1=2) знаки чередуются D1  0 , D2  0 , D3  2  0 , причем (1) m1  (1)11  0 . Проверяем: D3 >0, значит в точке X1=X2=1/2 находится максимум. Геометрически задача на условный экстремум сводится к тому, что решение находится в той точке, где линия (поверхность) определяющая функцию (систему) ограничений, касается какой-нибудь линии уровня (смотри .рисунок примера). 6.6. Выпуклое НЛП Теоретически собственно нелинейное программирование разработано только для одного частного случая выпуклых целевых функций F(X) и ограничений ψ i (X) и соответственно этот раздел называется выпуклым программированием. Выпуклое множество обладает тем свойством, что отрезок, соединяющий любые две точки множества, также принадлежит этому множеству. Таким образом, Рис.12 СEn выпукло, если из (X1, X2)С следует, что =X1+(1-)X2С для любого 01. Важно: если Сi-выпуклое множество, то С=∩ Сi также выпукло. Т.е. если каждое ограничение в задаче НЛП образует выпуклое множество, то и все ограничения дают выпуклое множество. 104 Дважды дифференцируемая функция F(x) является выпуклой в том и только в том случае, когда 2F(X )  X i X j  0 i 1 i 1 X X i j n h Для любых xM, M- выпуклое множество и Δхi и Δхj не обращается в нуль одновременно. Для проверки выпуклости F(X) используется критерий Сильвестра: Функция F(X)- выпукла, если неотрицательны (для строго выпуклой положительна) все главные миноры матрицы Гессе: a11 ... a1k k  ... ; a k1 ... a kk aij  2F ; X i X j k=1,2,…n. Если все Δk>0, то F(X) строго выпукла. Функция F(X) n переменных ||X 1 , X 2 ,…, X n || = X Є G называется выпуклой функцией в выпуклой области G, если для любых двух точек выполняется соотношение F{X (1)  (1   ) X ( 2) }  F ( X (1) )  (1   ) F ( X ( 2) ) , где 0<γ<1. Когда (1)  – переменная, то промежуточная точка пробегает значения ( 2) от X до X . Функция строго выпукла, если знак ≤ можно заменить на <. Т.о. для задачи на min выпуклая функция не может принимать больших значений, чем линейная (для задачи на max меньших значений). Другим важным свойством функций, выполнение которого позволяет гарантировать решение задачи НЛП является так называемое условие Липшица. Говорят, что функция F(X) удовлетворяет на отрезке [a,b] условию Липшица, если существует такое число L>0 (константа Липшица) , что F ( X | )  F ( X ||)  L X |  X || Для всех Х , Х / || (6.7)  a, b 105 Для проверки условия Липшица на практике используют следующий фактор: Если функция F(X) имеет на отрезке [a,b] ограниченную производную , то она удовлетворяет условию (6.7) , где L  max | F | ( X ) | [ a ,b ] 6.7. Теорема Куна-Таккера для выпуклого НЛП Функция Лагранжа является основным инструментом для теоретического обоснования решения задачи НЛП. Если задача такова , что F ( X )  min ( 6.8)  i ( X )  0, i  1, m все функции обладают свойством выпуклости, то справедлива фундаментальная теорема Куна-Таккера о Ф том, что решение (6.8) находится в так называемой седловой точке (Х ,  ,Ф ) функции Лагранжа. Функция Ф(Х,λ) двух векторХ ных переменных Х= ( X 1 ....X n ) и *   (1 ....n ) имеет в ( X * , * ) седловую точку точке , если  * * Рис.13 выполняются соотношения: Ф (X , * )  Ф ( X * , * )  Ф ( X * ,  ) для всех Х и λ из ε-окрестности ( X * , * ) . Для простейшего случая одной переменной X и одного множителя Лагранжа седловая точка геометрически изображена на рисунке ниже. (будем считать, что X  0 и   0 ).В седловой точке максимум функции Лагранжа по λ совпадает с минимумом по X . Необходимыми и достаточными условиями существования седловой точки функции двух векторных переменных являются соотношения 106 Ф X j X i* ( X * ,* 0 ( Ф ) * * 0 X j X , Ф ) * * 0  j X , *i ( Ф ) * * 0  j X , (6.9) *i  0, i  1, n X *j  0, j  1, n Эти соотношения связаны с фундаментальной теоремой нелинейного программирования Куна-Таккера о том, что решение задачи НЛП находится в седловой точке функции Лагранжа. Соотношения (6.9) являются не только необходимыми, но и достаточными, если кроме условий (6.9) выполняются условия регулярности Слейтера: в области допустимых решений существует такая точка X, в которой все ограничения не активны, т.е. i(X)<0 для всех i=1,m (в области есть «внутренние» точки). Теорема Куна-Таккера. Если в задаче НЛП F  X   min; i  X   0, i  1, m; m Ф X ,    F  X    ii  X  i 1 все функции выпуклы, а множество допустимых решений, определяемое ограничениями, удовлетворяет условиям регулярности Слейтера, то для оптимальности точки X* необходимо и достаточно выполнение условий (6.9). Если все ограничения линейные, то условия Слейтера в теореме не обязательны. 6.8. Квадратичное программирование Задачей квадратичного программирования (КП) называется такая задача НЛП, когда целевая функция представляет собой сумму линейной и квадратичной формы (переменные не старше второй степени), а все ограничения линейные. Для решения таких задач используется симплекс-метод. Теорема Куна-Таккера позволяет записать условие Куна-Таккера для задачи КП и найти седловую точку. Рассмотрим задачу КП в виде F  X    p j X j   Ckj X k X j   min n j 1 n n k 1 j 1 n  i  X    aij X j  bi  0, i  1, m, j  1, n, X j  0 j 1 107 В матричном виде: пусть P , X , B - векторы-столбцы: F  p X  X CX  min, AX  b, X  0 C-матрица квадратичной формы, которая должна быть симметрична и положительно-полуопределена, это гарантирует выпуклость F.. Метод Баранкина-Дорфмана непосредственно основан на применении теоремы Куна-Таккера. Запишем функцию Лагранжа в матричной форме для задачи КП : Ф X   pX  X CX    AX  b ;          FX  штраф Ф  V  p  2CX  A ; X  Ф  Y   AX  b  Тогда условие Куна-Таккера можно записать в следующем виде:  AX  V  b    2CX  V  A   p  ()    условие Куна-Таккера X  0; Y  0; V  0;   0  ** XV  Y  0    Неизвестными являются (X,Y,V,λ). (*)-система линейных уравнений относительно неизвестных; решить её, значит найти допустимые решения задачи ЛП. (**)-нелинейное условие. Тогда можно переходить из одного допустимого решения к другому и проверять условие (**). Введём векторы Z= (X,Y,V,λ) и Ž=(X,Y,V,λ), тогда можно записать 1 ~ XV  Y  Z  Z 2 Система (*) также может быть представлена через векторы Z, тогда окончательно условия Куна-Таккера будут иметь следующий вид 0  A E 0  b     Z    , Z  0  2 C  E A    p T Z   Z  Z~  0 6.10 6.11 Метод Баранкина-Дорфмана заключается в следующем: находится допустимый вектор Z , удовлетворяющий выражению (6.10) и проверяется условие (6.11). Далее выбирается новое базисное решение, причём оно выбирается так, чтобы величина 108 T Z  всё время уменьшалась. Для этого ис- пользуется модифицированная симплекс-таблица, в которой генеральный элемент находится из условия минимизации выпуклой функции T Z   Z  Z~  min T Z  : (6.12) т. е. мы решаем задачи (6.10) и (6.12), вместо (6.10) и (6.11). В симплекстаблице записываются в качестве базисных переменных все переменные. Запишем строку базисных переменных: n Z g  d g0   d g h  t h , g  1,2 N h 1 t  где 2 N  2n  m , а h свободные переменные. Если строка соответствует свободным переменным, то в строке одна единица и остальные нули. Для выбора генерального элемента используются дополнительные элементы, которые записываются в дополнительные строки:  j   d ij  d i  N ,0  d i  N , j  d i 0  N i 1 N  j  2 d ij  d i  N , j i 1  j  min g d g0 , при d g j  0 arg min  r  dgj K j  2 j   j  j Можно показать, что новое значение после замены j-ой свободной переменной будет T j  T   j K j : По определению  j  0 , поэтому чтобы T уменьшалось K j должно быть меньше нуля. Рассмотрим величину K j : величина  j - вторая производная функции T(Z), которая выпукла вниз, и поэтому  j  0, значит Kj может быть отрицательной, ес- ли  j  0 , значит в качестве генерального надо выбрать этот j – й столбец, а строку надо выбрать ту, для которой вычисляется величина . Пример: 109 F x   6 x1  2 x12  2 x1 x 2  2 x 22  min x1  x 2  2 x1  0 x2  0 Запишем все матрицы, которые нам нужны:  2  1 ; A  1,1; B  2; C   1 2    6 p   ; n  2; m  1; N  3;  0  Запишем условие Куна-Таккера, определяемое выражением (1):  1 1    4  2    2 4    1  0    0 0 0  1 0     0  1 1   1  x1     x2      2  y1    V    6   1   0      V2     Перемножим матрицы, получим систему x1  x2  y1  2 4 x1  2 x2  V1  1  6  2 x1  4 x2  V2  1  0 Чтобы записать симплекс-таблицу надо выразить базисные переменные через свободные. Для получения первого базисного решения используется любой метод, например, метод Гаусса. Можно использовать метод искусственного базиса (см. главу 2), который использует симплекс-процедуру. Затем нужно получить опорное решение и только после этого записать модифицированную симплекс-таблицу. Для простых задач можно подобрать первое базисное решение так, чтобы сразу получить опорное решение (свободные члены >0). Для нашего примера 110 Y1  2  X 1  X 2 X 1  6  4 X 1  2 X 2  V1 V2  6  6 X 1  6 X 2  V1 Запишем симплекс-таблицу по методу Баранкина-Дорфмана - таблица 1. Таблица 2 Таблица 1 1 X1 V1 X1 1 X1 X2 Y1 X2 2 -1 1 X2 -1 Y1 V1 1 V1 1 V2 X2 V1 1 -1/6 1 1/6 1 1 1/6 -2 -1/6 1 V2 6 -6 6 1 V2 1 1 6 -4 2 1 1 2 2/3 -2 1/3 j 24 -14 4 2 j 4 1 -6 1 j 8 j 8 j 1 j 1/2 Kj -20 Kj -8 Примечание. Алгоритм симплекс-преобразования аналогичен рассмотренному в главе 2, только : «…генеральную строку умножаем на -λ, а столбец на λ, отмечаем в строке нижние элементы, а в столбце верхние». Порядок строк в таблице нарушать нельзя. В первой таблице T= а0=24, а во второй 4. Чтобы не вычислять всю третью таблицу подсчитаем а0 для следующей таблицы по формуле T= 2*4+1/2 (-8)=0, значит следующая таблица оптимальная. Вычислим только необходимые элементы (свободные члены), получим; X1=3/2; X2=1/2; Y1=V1=V2=л1=0; Оптимальное значение F=-11/2. Недостаток метода: иногда встречаются задачи, когда все Kj>0. Значит, мы будем переходить в новую вершину, а значение T будет увеличиваться. В этом случае идём на временное ухудшениеT (проходим через «мёртвую зону»). В методе Франца-Вульфа это учтено [1,7,12,16]. 111 6.9. Методы возможных направлений Наиболее распространенным классом методов решения выпуклых задач НЛП являются градиентные методы, которые отличаются как способом получения последующей точки, так и способом «обработки» ограничений. В методах возможных направлений переход от точки Xk к точке Xk+1 осуществляется по направлению Sk, не обязательно вдоль градиента. При этом движение вдоль Sk должно быть таким, что бы новая точка принадлежала области допустимых решений D. Направление, удовлетворяющее этому условию, называется возможным или допустимым:   X k 1  X k  S k  D (6.13) Таких направлений множество; среди возможных направлений выбирают такое, для которого скалярное произведение градиентов в точке k и этого направления больше нуля ( для задачи минимизации меньше нуля). Такое направление называется подходящим. Таких направлений в общем случае так же множество. Г.Зойтендейк предложил выбирать то, которое максимально увеличивает значение целевой функции. Рассмотрим задачу выпуклого НЛП: , (6.14) (6.15 ) Обозначим область допустимых решений через D, пусть x0- начальная точка, а X*- единственное решение задачи, X0 D, . Переход из точки X(k) в X(k+1) осуществляют по такому направлению S(k), чтобы при луч принадлежал D. Обозначим g0(X) и gi(X) градиенты функций F(X) и φi(X) в точке X соответственно. Обозначим I(X) множество индексов I таких, что φi(X)=0;I(X) указывает номера ограничений, выполняющихся в точке X точно (I(X) - активные ограничения). Пусть S- некоторый вектор, S≠0, такой, что для всех выполняется неравенство . Знак (•)’ обозначает транспортированный вектор (матрицу). Тогда можно определить λ>0, чтобы . Для этого сначала определим , где di - корень уравнения (если нет решения, то где Ci – корень уравнения ( 112 ). Затем определим , ,S)=0 (если нет решения, то Ci= ). Таким образом, λ’ выбирается из условия невыхода из области D, а λ’’ из условия попадания в точку экстремума. Тогда если , то . Направление S, удовлетворяющее условию (6.15), и называют возможным (допустимым) в точке x0. То из возможных направлений, для которого, кроме этого, выполняется условие , называется подходящим, так как при движении в этом направлении значения целевой функции улучшаются, не выходя из D (для задачи на минимум ). Далее находится направление S из подходящих направлений, которое обеспечивает максимально возможное увеличение целевой функции, т.е. на каждом шаге решается вспомогательная задача (6.16) (6.17) Для нормализации длины вектора S используют следующие условия: Видно, что условие (6.17) уже содержится в N5. Точка X*, является решением, как только . Метод Зейтендейка можно применять для любых выпуклых функций F(x) и φi(x), но он может не дать решения за конечное число шагов. Для задачи квадратичного программирования можно с использованием принципа сопряженности обеспечить сходимость за конечное число шагов. Рассмотрим этот случай. Если есть внутренняя точка, т.е. , то новое искомое Рис.14 должно удовлетворять , помимо условия нормировки, еще одному условию сопряженности , где C- положительно полуопределенная матрица квадратичной формы для задачи квадратичного программирования 113 6.18 6.19 (k-1) Если для определения S такое условие уже использовалось, то оно остается, так, что все условия сопряженности имеют вид Сопряженность последующего направления предыдущему и обеспечивает конечность шагов при поиске решения для задачи квадратичного программирования. Это условие позволяет совместить траекторию движения с осями поверхности целевой функции. Рассмотрим пример с нормирующими условиями N5 для задачи квадратичного программирования (6.18), (6.19). Для нее . Длина очередного шага определяется из соотношения падания в экстремум, т.е. Величина определяется из условия по- Подставим выражение градиента, получим Отсюда получаем Величина для N5 всегда равна 1. На рис.14 изображена иллюстрация поиска решения для примера Для решения неквадратичных задач НЛП принцип сопряженности уже неприменим и для построения алгоритма, сходящегося к решению, приходится применять процедуру изменения длины шага. Рассмотрим такой алгоритм по методу возможных направлений Зойтендейка. При выборе подходящего направления будем принимать во внимание не только те ограничения, которые в данной точке выполняются точно, но и те, которые выполняются «почти точно». В противном случае λ может измельчаться вдали от точки минимума. Для 114 и определим теперь – активное индексное множество . Это те i, для которых , а также i=0, т.е. целевая функ- ция F(x). Для выбора λ и S в точке для получения следующей точки в соответствии с методом Зойтендейка необходимо выполнить условия невыхода из D, нормировки длины вектора λS и условия большего возрастания (убывания для задачи на минимум) целевой функции. В алгоритме, излагаемом ниже, последнее требование заменятся требованием выбора направления, имеющего наибольший угол к касательным с ограничениями вблизи точки x(k), что дает возможность двигаться с большим шагом, не выходя за пределы D, а длина этого шага выбирается из условия наибольшего увеличения (уменьшения) F(x). В качестве нормировки выберем N2 . Тогда для задачи минимизации для заданного ε в точке x необходимо определить величину из условия ,где g0(X) – градиент F(X). Более подробно алгоритм решение и примеры можно найти в [7, 16]. , 6.10. Метод проекции градиента На каждой итерации этого метода предусмотрена процедура возврата очередного приближения градиентного спуска на допустимое множество U , если . Такой возврат производится посредством проектирования на U, т.е. замены на ближайшую точку множества U. Опр е де ле н ие. Пусть заданы замкнутое множество . Точка и точка называется проекцией точки z на множество U, если где –расстояние между точками x и y в пространстве Очевидно, для точки проекция совпадает с z. Таким образом , в методе проекции градиента последовательные приближения к точке минимума U вычисляются по формулам целевой функции f(x) на множестве 115 , . (6.20) В зависимости от способа вычисления из (6.20) различают несколько вариантов метода проекции градиента, самыми распространенными из которых являются следующие. 1) находится, как в методе наискорейшего спуска безусловной минимизации, т.е. , где В предположении, что Рис.15 градиент целевой функции удовлетворяет на множестве U условию Липшица, т.е. (6.21) для всех , полагают где α - произвольное число из интервала (0;2/L). Если известна минимальная константа Липшица L из (6.21), то выбирают, как правило, α=1/L. Вычисления по формуле (6.20) завершаются при выполнении одного из неравенств или , где величина определяет точность решения задачи. Окончательно полагают . Отметим, что определение проекции для точки самостоятельной задачей нелинейного программирования: , является (6.22) решение которой может вызвать затруднения. В частном случае, когда множество U определяется лишь линейными ограничениями, задача (6.22) представляет собой задачу квадратичного программирования. Ее решение может быть найдено за конечное число шагов, как описано выше. 116 X3 Z PU(Z) X1 X2 Особый интерес при использовании метода проекции градиента представляют такие множества U, для которых задача проектирования (6.22) решается в явном виде.(U- шар, параллелепипед и т.д.) Иногда, как в примере с шаром, нахождение кратчайшего расстояния приводит к задаче на условный экстремум Рис.16 Ф  0; X j Ф X ,     X j  Z j     X j  R0  ; n 2 j 1 n 2 j 1 Ф 0  j В случае с шаром: n  2 2  Z ,  Z j  R0 ; Z  U  j 1  n R Z PU Z    0 ,  Z 2j  R02 ; Z  U   n 2 j 1  z  j 1 Если область допустимых решений U- параллелепипед, то проекция точки определяется очень просто. Пусть область U определяется условиями : a10 – число, характеризующее точность, k – четное число. Если в задаче (6.24) F(X) – выпуклая квадратичная функция, а gi(X), i=1, … , m, - линейные функции, то точное решение вспомогательной задачи (6.23) можно найти из системы линейных уравнений dF(X)/dXj=0, j=1, … , n, определяющих стационарную точку функции Fk(X). Пример. Минимизировать  x1x2 при ограничениях g1   x1  x  1  0, 2 2 g 2   x1  x2  0. В качестве штрафной функции применим 2 pi ( g i )  ( g i  g i ) / 2 , p ( X )   p i g i ( x) и Pk(X)=k p ( X ). Тогда 2 следующую 2  ( x1  x 22  1   x1  x 22  1 )   ( x1  x 2   x1  x 2 )    k C k ( X )   x1 x 2  k   2 2       будет функцией, минимизируемой методом внешней точки. Значение x (k ) для примера k k1 ,0 k 2 ,0 t2 k ,0 3 k 0,0 4 о птимум 120 1 ,89 2 ,77 3 ,73 1 ,67 x1 (k ) x2 (k ) 0,64 0,62 0,61 0,58 23 3 3 В таблице приведены значения x (k ) для четырёх различных значений k. Из рисунка видно, что при возрастании k они приближаются к оптимуму из недопустимой области. Методы внутренней и внешней точки существенно отличаются друг от друга, и не только тем, что в одном из них движение происходит в допустимой области, а в другом - в недопустимой. Метод барьерных функций. Рис.20 В методе барьерных функций исходная задача НЛП также сводится к последовательности задач безусловной минимизации (6.23), но функции Pk(X) выбираются таким образом, чтобы при больших k функции Ck(X) из (6.23) мало отличались от F(X) во внутренних точках x допустимого множества U. В то же время при приближении точки XєU к границе множества U эти функции должны неограниченно возрастать. Определение. Пусть множество U   n задано. Последовательность функций {Pk ( X )} , определенных во всех внутренних точках множества U, называется последовательностью барьерных функций этого множества, если выполняются условия: 1. lim k  Pk ( X )  0 для любой фиксированной внутренней точки x множества U. 2. lim r  Pk ( X (r ) )   для любой последовательности { X (r ) } внутренних точек множества U, сходящейся к какой либо граничной точке этого множества. Рассмотрим некоторые варианты метода барьерных функций решения следующей задачи нелинейного программирования: F(X)  min (6.26) g i ( X )  0, i  1..., m. Положим Pk ( X )  1 p ( X ), k=1, 2…, k (6.27) 121 где p( X )  i1 g i ( x) m или k , k >0 (6.28)  ( 6.29)  p( X )  i 1 ln  g i ( x ) m Выражения (6.27) – (6.29) определяют последовательности барьерных функций допустимого множества U задачи (6.26) (проверяйте!). (k ) Пусть X – решение задачи безусловной минимизации (6.23), где функция Pk (X ) определена равенствами (6.27), (6.28) или (6.29). Полагая X *  X ( k ) , F *  F ( X (k ) ) для достаточно большого k, находим приближенное решение задачи нелинейного программирования (6.24) методом барьерных функций. Для контроля достигнутой точности решения можно использовать критерий (6.4). Пример. Минимизировать X 1  X 2 при ограничениях g1   X 12  X 2  0 , g2   X1  0 . В качестве функции p(gi) возьмём логарифмическую функцию . Обоm значим 1/k=r. Тогда Pr(X))=rp(X), p X    ln(  g i ( X )) . n 1 C ( X , r )  X 1  X 2  r ln(  X 12  X 2 )  r ln X 1 . Этот простой пример можно решать аналитически, учитывая, что С(X, r) дважды дифференцируема. Необходимые условия первого порядка принимают вид: 1 r (2 X 1 ) r   0, 2  X1  X 2 X1 1 r  0.  X 12  X 2 Решая эту систему, получаем X 1 (r )   1  1  8r . 4 Поскольку значение X 1 (r ) должно быть положительно, будем рассматривать лишь один корень X (r )   1  1  8r . Тогда 1 4 (1  1  8r ) 2 X 2 (r )  r. 16 122 Эти значения X 1 (r ) и X 2 (r ) удовлетворяют достаточным условиям и поэтому дают локальный минимум задачи. В таблице приведены вычисленные значения X (r ) для четырёх различных r. Этот пример изображён на рисунке. В пределе при rk  0 минимизирующие точки приближаются к решению (0,0). Значения r и x(r) из примера r X 1 (r ) X 2 (r ) r1 r2 r3 1,000 0,500 1,250 0,500 0,309 0,595 0,250 0,183 0,283 r4 0,100 0,085 0,107 В этой задаче при каждом значении r существует только один локальный минимум. Это происходит так потому, что исходная задача имела единственное решение. Оказывается, что в задачах со многими локальными минимумами (при выполнении вышеупомянутого условия регулярности Слейтера) существует последовательность безусловных локальных минимумов, сходящаяся к каждому из условных локальных минимумов [24,1,12,22]. На рисунке показан пример решения задачи с помощью безусловной логарифмической функции. Допустимая область заштрихована. Рис.21 123 6.12. Метод скользящего допуска Метод скользящего допуска применяется при общей постановке задачи нелинейного программирования: Минимизировать F  X  , Х  Е n при ограничениях hi ( X )  0 i  1,...., m gi ( X )  0 i  m  1,..., p Где функции F  X  , hi ( X ), g i ( X ) могут быть как линейные, так и нелинейные. Алгоритм скользящего допуска позволяет улучшить значения целевой функции как за счет информации, получаемой в допустимых точках пространства решения, так и за счет информации, которую удается получить при прохождения через точки, лежащие вне допустимой области, но близкие к допустимым. Интервалы, в пределах которых точки можно считать почти допустимыми, в ходе поиска постепенно сокращаются, так что в пределе (по мере приближения к искомому решению) учитываются только  допустимые точки Х . В качестве метода получения последовательности точек, улучшающих значение целевой функции, используется метод Нелдера-Мида (см. п.6.4). При такой стратегии задачу можно заменить более простой, но имеющей то же самое решение задачей минимизации ях F  X  , Х  Е n при ограничени- Ф(к)  Т ( Х )  0 , (к ) где Ф -значение критерия скользящего допуска на к-том этапе; Т ( Х ) -мера степени нарушения ограничений рассматриваемой задачи. В качестве Ф выбирают положительно определенную убывающую функцию координат вершин деформируемого многогранника Нелдера и Мида. Функция Ф служит критерием допуска для нарушения ограничений задачи и прекращения процедуры оптимизации. Варианты выбора Ф многочисленны. Например:  m  1 r 1 ( k )  Ф ( к )  min Ф ( к 1) , X i  X r(k )2   r  1 i 1   Ф ( 0)  2(m  1)t 124 t- размер исходного многогранника (например длина высоты); m- число ограничений равенств; X i(k ) -вектор i-той вершины многогранника; R= (n-m) - число степеней свободы целевой функции F X  в Е n ; X r(k )2 -вектор, задающий «центр тяжести» многогранника при r =n. (к ) По мере приближения к оптимальной точке Ф устремляется к нулю «сверху». В пределе многогранник деформируется в точку lim Ф ( к )  0 x  x* Функционал p m  T ( X )   hi2 ( X )  U i g i2 ( X ) i  m 1  i 1  где 1/ 2 , U i  0 при g i ( X )  0 , и U i  1 при g i ( X )  0 T ( X )  0 при X  E n T ( X ( к ) )  0 , то Х (к ) – допустима, если T ( X ( к ) )  0 ,то Х (к ) – (к ) (к) (к) не допустима, при T ( X )  Ф , и Х почти допустима при 0  T ( X (к) )  Ф(к) Если Это условие и определяет набор точек по допустимости. Общая схема алгоритма выглядит так: при заданном Ф Х ( к 1) (к ) в точке может быть два варианта: Т ( Х ( к 1)  Ф ( к ) -перемещение считается разрешенным. ( к 1) 2) Т ( Х  Ф ( к ) - необходимо найти другую точку Х ( к 1) , ближе к ( к 1) допустимой области , чтобы Т ( Х ) уменьшилась. Для этого можно в 1) алгоритме Нелдера - Мида считать точку Xk+1 худшей, или же возвращать ее на ближайшую границу. Т(Х) не влияет на сходимость алгоритма, так как на заключительных этапах поиска точки Х i (к ) являются внутренними , т.е. Т ( Х i )  0 . (к) Если Х является граничной точкой, то поиск вдоль границы происходит за счет улучшения F ( X ) при условии * Ф ( к )  Т ( Х i( к ) )  0 125 Степень нарушения ограничений по мере приближения к искомому решению уменьшается. К моменту прекращения оптимизационного поиска выполняются условия: Ф (к)   F ( X l( к ) )  F ( X *   )   T ( X l( к ) )  0. 126 7. Особенности современной теории принятия оптимальных решений Методы поиска оптимальных решений рассматриваются в разделах математики (методах оптимизации), исследования операций, математическом программировании и в классическом понимании связаны с поиском экстремумов функций и функционалов при функциональных ограничениях на переменные. Решение здесь - математический объект. Причём здесь вопросы оценки критериев (многих) и изучение того, почему такой то критерий можно считать приемлемым не изучается (о критериях не спорят!). На практике задача выбора решения намного сложнее. 1. В некоторых задачах сами варианты проведения операций представляют собой небольшое число отдельных альтернатив, не всегда однородных. Например: вариант 1 - строить большой завод, вариант 2- строить небольшой завод, а потом расширять производство. Поэтому в теории принятия решений (ТПР) рассматривается как самостоятельный вопрос задания множества альтернатив, на котором ищется оптимальное решение. 2. Во многих задачах множество альтернатив не ясно с самого начала, например, альтернативы при игре в шахматы. Поэтому в ТПР говорят о генерации альтернатив в процессе решения задачи. При игре в шахматы приходится генерировать альтернативы в процессе игры и оценивать их. 3. Оценка ценности каждой альтернативы во многих случаях не сводится к простому сравнению количественного параметра (сравнению чисел). В связи с этим в ТПР применяет специальные методы измерения полезности альтернатив. 4. В большом числе практических задач системы или операции не могут быть оценены единственным показателем эффективности. Сами системы являются очень часто многоцелевыми. Вот почему критерий не может быть скалярной величиной, а является вектором. Оказывается, что когда по одному показателю один вариант лучше, по другому он может оказаться хуже, и поэтому возникает проблема их сравнения. Этот раздел современной ТПР называют многокритериальной или векторной оптимизацией. 5. Во многих задачах, особенно в задачах автоматизации управления, присутствуют так называемые нечёткие переменные, и нечеткие критерии. Появляется специальный раздел ТПР – принятия решений в расплывчатых ситуациях, в котором рассматриваются вопросы «человекоподобного восприятия информации для принятия решения и создаются 127 автоматизированные экспертные системы поддержки принятия решений. 6. Иногда встречаются задачи, в которых присутствуют несколько сторон , преследующих разные интересы (боевые действия, поведение государств, конкурирующие фирмы), которые принимают решения в одной и той же системе. Такие ситуации называются конфликтными. Модель для принятия решений и принцип оптимальности в этих случаях является совершенно иными, чем в рассмотренных задачах математического программирования. Этими вопросами занимается теория игр. 7. На практике одни решения приводят к необходимости принимать следующие решения и т.д , т.е. приходится изучать многоэтапные решения , в том числе и в условиях случайных возмущений. 8. При принятии решений в условиях неопределенности можно поставить и решить задачу устранения части неопределенности за счет проведения «эксперимента». Например, это выражается в виде разведки (военной или экономической), метеонаблюдений, радиолокации и т.п. 9. Во многих задачах принимаются так называемые групповые решения, при этом альтернативы оцениваются группой экспертов – специалистов в данной предметной области. На основе такой экспертизы путем специальной обработки экспертных данных можно принимать решения в случаях когда алтернативы трудно формализуемы. Такой метод получил название метода экспертных оценок. 10. Вот почему современная теория принятия решений представляет собой обобщение всей методологии получения решений в самых общих и практически важных случаях (много критериев; неопределённость принципа оптимальности, нечёткость шкалы ценности, условия риска, неповторимость ситуации, сложная логика предпочтений между альтернативами и другое). Сказанное характерно для анализа оптимальных решений при построении современных автоматизированных систем управления и экспертных систем. 7.1. Общая постановка задачи принятия решения Задачей принятия решения назовём пару (Ω, P) , где Ω – множество вариантов, P – принцип оптимальности. Решением задачи (Ω,P) является множество Ωp ≤ Ω, полученное с помощью принципа оптимальности P. Отсутствие хотя бы одного из элементов лишает смысла задачи в целом. Если нет Ω не из чего выделять Ωp. Если нет P, то найти Ωp невозможно. Математическим выражением принципа оптимальности P служит функция выбора Cp. Она сопоставляет любому подмножеству X≤Ω его часть Cp(X). Решением Ωp исходной задачи и является множество Cp(X). 128 Задачи принятия решений различаются в зависимости от имеющейся информации о множестве Ω и принципе оптимальности P. В общей задаче принятия решений как Ω так и P могут быть неизвестными. Информацию, необходимую для выделения Ωp получают в процессе решения. Задачу с известными Ω называют задачей выбора, а задачу с известными Ω из P - общей задачей оптимизации. Таким образом, задача выбора и задача оптимизации являются частным случаем общей задачи принятия решений. В общем случае для задачи выбора необязательно необходимо полное восстановление принципа оптимальности, а можно ограничится только информацией, достаточной для выделения Ωp. Общая задача оптимизации не обязательно требует минимизации одной или нескольких числовых функций, так как может быть и так что другим способом выделяется множество лучших элементов, то есть выделяются значения Cp(Ω) при заданных Ω и Cp. Если Cp – скалярная функция на множестве Ω, то получаем обычную оптимизационную задачу. Элементы множества Ω называются альтернативами или вариантами. Принцип оптимальности P задаёт понятие лучших альтернатив: лучшими считают альтернативы, принадлежащие Cp(Ω). В практических задачах альтернативы обладают многими свойствами, оказывающими ритение на решение. Пусть некоторое свойство альтернатив из Ω выражается числом, то есть существует отображение φ: Ω→ E1. Тогда такое свойство называется критерием , а число φ(x)-оценка альтернативы x по критерию. Одновременный учёт отдельных свойств может быть затруднительным. При этом можно выделить группы свойств, которые агрегируют в виде аспектов. Аспект – сложное свойство альтернатив, которое одновременно учитывает все свойства, входящих в группу. В частном случае аспект может являться критерием. Пусть все свойства k1,…, km , учитываемые при решении задач (Ω, P) являются критериями. Критериальным пространством называют пространство Em, координаты которого есть оценки соответствующих критериев. Пример: при определении маршрута перевозок альтернативымаршруты. Диспетчер учитывает свойства: протяженность, загрузка, энергоёмкость, безопасность, техническое обслуживание и другое. Техническое обслуживание-это число станций, сроки выполнения ремонтных работ и так далее. Следовательно, техническое обслуживание-это аспект. Стоимость маршрута состоит из стоимости топлива, обслуживания и т.д. То есть это тоже аспект. Однако, так как стоимость можно вычислить, то это критерий (но так будет не всегда). Сформулируем схему процесса принятия решения. 129 Формируется множество Ω, т.е. подготавливают для последующего решения задачи выбора (При назначении на должность сначала готовят список кандидатов, а затем назначают лицо из этого списка). Для формирования Ω используют условие возможности и допустимости альтернатив, которые определяют конкретными ограничениями задачи. При этом считают известным универсальное множество альтернатив Ωy. Таким образом, задача формирования Ω является задача выбора (Ω y, P1) , где P1 – принцип оптимальности, выражающей условия допустимости. Множество Ω=Сp1(Ωy), полученное в результате решения называют исходным множеством альтернатив (ИМА) (Ωy – все специалисты, Ω специалисты, удовлетворяющие требованиям ). Таким образом, общая задача принятия решения сводится к решению двух последовательных задач выбора. В процессе решения участвует лицо принимающее решение (ЛПР), эксперты, консультанты. ЛПР – человек, имеющий цель, служит мотивом постановки задачи. ЛПР имеет полномочия и несёт ответственность. Основная функция ЛПР выделять Ωp. ЛПР даёт информацию о принципе оптимальности P. Эксперт - не несёт ответственности, он даёт оценки альтернатив, необходимые для формирования ИМА и решения задачи выбора. Консультант – специалист по теории выбора и ПР. Он разрабатывает модель, процедуру принятия решений , организует работу ЛПР и экспертов. В простейшем случае задачу (Ω, P) решает непосредственно ЛПР. Прикладные результаты ТПР имеют вид алгоритмов решения задач. Часть алгоритмов может быть реализована вручную, но основная часть ориентирована на диалоговый режим работы ЭВМ или на применение в экспертных системах. 7.2.Классификация задач принятия решений Для классификации задач принятия решений представим более подробно задачу ПР в виде семёрки. ПР = (Z, Ω, K, S , F , G , P) Z - Описание предметной области, в которой принимается решение. Ω - Множество альтернатив K - Множество критериев оценки альтернатив. S - Множество шкал измерения по критериям. F - Отображение множества альтернатив в множество критерий оценок F(X) = Y G - Система предпочтений P - Решающее правило, отображающее систему предпочтений. 130 Любой из элементов этой семёрки может служить классификационным признаком задач ПР. однако, в основном для классификации используются тип отображения F , мощность множества К, тип системы предпочтений G и характеристики области допустимых решений XеΩ. Отображение X в множество криk1 териальных оценок может быть деk=F(X) терминированным, вероятностным либо неопределённым. Поэтому задачи принятия решений можно разделить на x ПР в условиях определённости, риска k2 и неопределённости. k3 ПР в условиях определённости предполагает детерминированное (взаимнооднозначное) соответствие между X и k. k X 1 k=F(x) x k2 k3 ПР в условиях риска соответствует вероятностному отображению X в k. k х 1 K x k ПР в условиях неопределённости не предполагает соответствия X и k. 2 k 3 Если K-скаляр - то это однокритериальная задача ПР. Если K-вектор то это задача многокритериальной (векторной) оптимизации. Отметим, что задача ПР со скалярным критерием является тривиальной задачей оптимизации в случае детерминированного отображения F. Как только решающий элемент имеет дело с ПР при вероятностном характере 131 отображения F, либо априори неизвестном (неопределённом) F, то задача ПР даже со скалярным критерием сразу перестаёт быть тривиальной (см. рисунок). а) rr r(1)=F(x(1') ) (1)) f(r/x б) (2) r(2) =F(x f(r/x(2)) ) r(3) =F(x(3)) f(r/x(3) а) выбор при одном критерии в условиях определённости б) выбор при одном критерии в условиях риска. 7.3. Многокритериальная оптимизация В разделах 1-6 мы рассмотрели задачи, в которых требуется выбрать решение, доставляющее максимум (или минимум) единственного показателя эффективности (критерия) k. На практике часто возникает случай, когда эффективность операции приходится оценивать не по одному, а сразу по нескольким показателям k1 ,k2 ,…,kL. Примеры: 1. Оценка деятельности завода: прибыль, средняя зарплата, обем производственных фондов. 2. Оценка учебы студента: оценки по предметам. 3. Военная операция: потери, вероятность выполнения задачи. Одни из этих показателей необходимо сделать больше, другие меньше. Как правило, эффективность больших по объему, сложных операций, а также сложных многоцелевых систем не может быть исчерпывающим образом охарактеризована с помощью одного показателя: на помощь ему приходится привлекать и другие, дополнительные показатели. Главной особенностью этой ситуации является то, что требования ко всем показателям в реальных системах несовместимы или противоречивы. Как правило требование max k1 не обращает ни в максимум ни в минимум другие показатели k2 ,k3 , …. Поэтому широко распространённая фор132 мулировка «достижения максимального эффекта при минимальных затратах» является не корректной. Корректными являются следующие формулировки: 1. Достижение максимального эффекта при заданных затратах. 2. Достижение заданного эффекта при минимальных затратах. Для удобства сравнения значений векторов k=(k1, k2,…kL) – иногда удобно предварительно привести все показатели k1 , k2 ….kL к стандартному виду, чтобы все критерии минимизировались и чтобы они имели безразмерный масштаб измерения. Векторный критерий k считается стандартным, если он удовлетворяет условию ki≥0 и чем меньше ki, тем лучше операция (система). Таким образом, идеальной является система, у которой ki=0. Нестандартный показатель можно привести к стандартному. Если ki  max , то: kстi= k maxi - ki ; Если k maxi =∞ , то kстi =1 ∕ ki . Стандартный критерий можно задать в виде отношения: kiст=(1 – ki/kiи), где kiи – идеальное значение критерия (либо определенное значение, либо maxki) При этом в L-мерном пространстве задаётся вектор k, каждая компонента которого изменяется от 0 до 1. Полностью идеальной системе соответствует k=0. Прежде всего, анализ векторов, соответствующих альтернативам из области допустимых альтернатив, позволяет заранее отбросить явно нерациональные варианты решений, уступающие лучшим вариантам по всем показателям. Этот этап векторной оптимизации называется безусловной оптимизацией. Пусть анализируется боевая операция, оцениваемая по двум показателям. k1 – вероятность выполнения боевой задачи; k2 – стоимость израсходованных средств. Очевидно, первый показателей желательно обратить в максимум, а второй в минимум. Пусть предлагается на выбор конечное число различных вариантов решения, обозначим их X1 , X2 , .., Xn. Для каждого известны значения k1 ,k2 . Изобразим каждый вариант решения в виде точки на плоскости с координатами k1 , k2. Когда X пробегают ОДР, точки k1, k2 заполняют критериальное пространство решений,. 133 Итак, если некоторая операция оценивается несколькими критериями, каждое из которых число, то такая задача называется задачей многокритериальной или векторной оптимизации. Для стандартных k эта задача имеет вид k=(k1, k2, …, kL) = f ( X , A)  min i ( X , A)  0, i  1...m 7.1 7.2 Существует принципиальная трудность в объективной (безусловной) оценке альтернатив при двух или более критериях. Она связана с проблемой сравнения двух векторов. Безусловным критерием предпочтения называют критерий, основанный на сравнении компонент вектора. Два вектора критериев kA и kB безусловно сравнимы , если для любой l -ой компоненты вектора выполняются неравенства klA >= klB , l=1,2,3,…,L . Если все kl  min, то альтернатива B безусловно предпочтительнее (лучше) A. Это означает, что А никак не может быть оптимальной и поэтому должна быть отброшена. Если же знаки неравенств для различных компонент вектора различны, то такие альтернативы безусловно несравнимы. Рассмотрим пример. Необходимо выбрать лучших по успеваемости студентов А,Б,В,Г,Д. Критериями служат оценки по предметам М,N,O,P. M N O P А 4 4 5 3 Б 5 5 4 3 В 4 5 3 3 Г 5 4 5 4 Д 4 5 4 3 Проведем безусловное сравнение векторов оценок. Студент А не сравним с Б. В безусловно хуже Б – отбросим В. Д безусловно хуже Б – отбросим Д. А безусловно хуже Г – отбросим А. Остались две альтернативы Б и Г, которые безусловно не сравнимы. Определение. Множество безусловно несравнимых альтернатив, оставшихся после отбрасывания всех безусловно худших альтернатив называется множеством Парето . Парето-оптимальное множество еще называют областью компромиссов. Ясно, что множество Парето можно получить в результате анализа критериального пространства. Таким образом векторная оптимизация включает два этапа. 134 1.Безусловная оптимизация. Здесь анализируется критериальное пространство, отсеиваются безусловно худшие варианты и получают множество Парето. 2. Условная оптимизация. Так как множество Парето, как правило, состоит из более чем одной точки, то для получения единственного решения необходимо применить дополнительные принципы оптимальности (условия согласования критериев). 7.4. Определение множества Парето Если целевая функция векторная функция векторного аргумента и каждому малому изменению переменных X соответствует малое изменение каждого критерия, то критериальное пространство – это область с внутренними точками и границей. (не обязательно замкнутая).. Пусть есть только два критерия K1 , K 2  и k1  max ; k2  max Рассмотрим область возможных знаC 3 K2 чений критериев. (рис. а). Ясно, что точки, лежащих на одной вертикали или на A 2 одной горизонтали всегда безусловно B 1 сравнимы (см. точки 1,2,3). Получается, что все внутренние точки можно отсеять. D Дуга АВ состоит из лучших точек по критерию k2 при постоянном k 1. Но K1 часть точек дуги АВ , а именно точки дуги AС можно отбросить, так как они хуже точек СB. . Поэтому точками множества Парето будут являться точки находящиеся на дуге CB. При анализе характерными являются точки касания вертикалей и горизонталей к области критериев (точки А,В,С,D). Существует несколько алгоритмов нахождения множества Парето. Они зависят от того, в каком виде задано множество вариантов критериев. В практических задачах сначала приходится получать само множество критериев, затем получать множество Парето в критериальном пространстве и только затем можно определить Парето -оптимальное множество в области допустимых решений X. Существует два основных метода нахождения множества Парето: 1) Метод обхода конусом. Этот метод применяется для непрерывной области критериев. Назовем конусом пространственный угол, образуемый лучами, идущими из общей вершины и ограниченные в каждой плоскости углом 90 . Направление ограничивающих лучей соответствует направлению оптимизации критериев. 135 Пусть для двух критериев: k1 max( ↑) k2  min ( ↓), тогда конус имеет вид: Для получения множества Парето достаточно установить вершину конуса на все точки границы области критериев, если при этом ни один луч не пересекает область, то вершина лежит в точке Парето, а если пересекает, то нет. и Пример: k1 → min k2 → min Множество [AB]  (CD] Парето: 2.Метод прямоугольников. Этот метод применяют, когда критериальное пространство представляет собой отдельные точки или табличные значения. Сформулируем алгоритм для случая двух критериев, когда k1 → min и k2 → min , а критериальное пространство – точки на плоскости. 1)Фиксируем самые левые точки, если их несколько, выбираем среди них самую нижнюю. Эта точка является точкой Парето, фиксируем ее. 2)Выберем самую нижнюю точку, если их несколько, то выбираем самую левую. Это точка Парето, фиксируем ее. 3)Через полученные точки проводим вертикаль и горизонталь. Отбрасываем сами точки Парето, точки лежащие на границе полученного прямоугольника и точки вне прямоугольника. 4)К внутренним точкам полученного прямоугольника применяем алгоритм с пункта 1. 136 Алгоритм заканчивается тогда, когда внутри прямоугольника не останется ни одной точки. Множество 1,2,3,4,5,6. Парето: Вышеизложенный алгоритм легко обобщается на случай большего числа критериев, при других направлениях оптимизации, а также на случай табличного задания критериев. 7.5. Методы условной многокритериальной оптимизации После нахождения множества Парето, если количество точек в нём  2 , встаёт вопрос о выборе единственного решения.. Так как точки на множестве Парето обладают свойством, что каждая из них лучше по одному критерию, но хуже по другому, то объективно предпочесть эти точки невозможно. Условная оптимизация предполагает введение условия согласованности в компонентах критерия, которое всегда является хотя и разумным, но субъективным. Подобные условия еще называют схемой компромиссов. Рассмотрим несколько простейших из них. Принцип равенства критериев. Рассматривают множество Парето для стандартных критериев. Тогда оптимальной считается та точка множеств Парето, где k1=k2=…=kL (см. рисунок). Принцип равного влияния. Здесь оптимальной считается точка множества Парето, являющаяся точкой касания прямой k1 + k2  min и области Парето (точка С, см. рисунок) Принцип минимакса. Оптимальной считается точка множества Парето, где обеспечивается minmax kiст. (см. ри137 сунок). Кроме указанных простейших приемов применяются более сложные. 1) Метод скаляризации. Здесь формируется некоторая скалярная функция многих переменных: K 0  f K1 , K 2 , , K L  K0 - это скалярная величина, которая обобщает все критерии. Наиболее распространённой разновидностью функции f является линейная функция L K 0    i K i  min(max) i 1  i  вес каждой компоненты критерия, чем эта величина больше, тем большее влияние оказывает этот критерий. Для нестандартных критериев веса могут иметь размерность, причем если Ki→max, то  i  0 , а когда Ki→min , то i  0 . Подобная комплексная оценка зачастую затрудни- тельна. На практике часто используют и другие способы искусственно объединить несколько показателей в один обобщённый показатель ( критерий). В качестве обобщённого критерия, например, берут дробь: K 0 = (k1х k2х...km ) /( km+1х….kL, ) где k1...km – увеличиваются km+1.. kL - уменьшаются Вольное использование подобных критериев чревато опасностями и может привести к неправильным рекомендациям. Общим недостатком «составных критериев» является то, что недостаток эффективности по одному показателю всегда можно скомпенсировать за счёт другого (например, малую вероятность выполнения боевой задачи – за счёт малого расхода боеприпасов и т.п.) На этот счет известна шутка Л.Н.Толстого, что если представить оценку человека в виде дроби: 138 Достоинство _ человека , то можно получить самую высокую оценку Мнение _ о _ себе Мало _ достоинств  Нет _ мнения _ о _ себе 2).Метод главного критерия. В этом методе сначала выбирают главный критерий и объявляют его единственным критерием. Все остальные критерии становятся управляемыми переменными, на которые накладываются ограничения, что бы они были не хуже заданной величины ki0. Например, если все ki  min и главный k1, то получаем однокритериальную задачу математического программирования k1 = f ( X) –> min Фi (X) < 0, i = 1,2,3,…m k2 (X) max , план по ассортименту – выполнен, а себестоимость – не выше заданной. При бомбардировке – понесённый ущерб противника – максимальный, потери и стоимость операции не выходили за известные пределы. Здесь все показатели эффективности, кроме одного, переводятся в разряд ограничений. Варианты решения, не укладывающиеся в заданные границы, сразу же отбрасываются как недопустимые. Такой метод чаще всего используется при оптимизации сложных технических систем (самолетов, автомобилей, бытовой техники и т.д.). 3). Метод последовательных уступок. Проранжируем все критерии и расположим их в порядке убывающей важности: k1, k2 …. kL.. Пусть все критерии нужно максимизировать. Сначала отбросим все критерии кроме k1 и найдем допустимое решение, обращающее в максимум k1 . Как правило при этом другие критерии не получают своих наилучших значений. Поэтому исходя из практических соображений и точности, с какой известны исходные данные назначается уступка ⌂k1 , которую мы согласны допустить для того, чтобы обратить в максимум k2 . Наложим на k1 ограничение, чтобы он был не меньше чем k1*- ⌂k1 (k1*- максимально возможное значение k1 ) и при этом ограничении ищем решение, обращающее в максимум k2 . Далее снова назначается уступка в показателе k2 ценой, которой находится максимум k3 и т.п. в случае K 2  max K1 max  K1  K1  K1 max На втором этапе решаем задачу 139 K 3  max K1max  K1  K1  K1max K 2 max  K 2  K 2  K 2 max И так далее. Такой способ хорош тем, что здесь сразу видно, ценой какой «уступки» в одном показателе приобретается выигрыш в другом. Заметим , что иногда даже при малом ⌂k «свобода» выбора позволяет достичь существенной оптимизации k2 . Это зависит от вида границы критериального пространства. (см. рисунок). F→max k 1 max ⌂ k1 k2' k2 max Очевидно, успех такого метода зависит от того, насколько «тупой» максимум. Процедура может быть повторена для других K . 4. Метод последовательной оптимизации. В некоторых случаях критерии системы не слишком связаны друг с другом, т.е. улучшение одного критерия по крайней мере в ограниченных пределах не «мешает» другому. Это характерно для сложных систем, состоящих из отдельных достаточно автономных подсистем, (например: процессор компьютера, система электропитания, система охлаждения, система отображения), когда отдельные критерии относятся к этим подсистемам. Расположим все критерии в порядке убывания важности. Сначала оптимизируют систему по важнейшему показателю, отбросив все остальные, затем по второму, и т. д. Следует отметить, что в вышеприведенных методах используется процедура упорядочения критериев по важности. Эта самостоятельная про140 блема является достаточно сложной и поэтому решается на основе методов экспертных оценок, изложенных в 10 главе. 141 8. Игровые модели принятия решений Математические модели, рассмотренные нами, выражают стремление получить максимальный результат для какой-то одной системы (фирмы, отрасли, страны). Если эта система состоит из каких-то других элементов (подсистем), то считается, что их целевые функции совпадают, то есть эти подсистемы работают «все как один». Во многих задачах это не так. Приходится анализировать ситуации, когда присутствует несколько сторон, преследующих различные интересы (цели). Это и боевые действия, и внешняя экономическая деятельность государств и многое другое. При переходе к рыночной экономике и возникновении конкуренции как основного рычага развития экономики постановка задачи с отождествлением целей является неполной, а иногда и неправильной. Интересы отдельных фирм сталкиваются на одном рыночном пространстве и иногда настолько различны, что конкуренция приобретает форму борьбы, и поэтому невозможно оценить результат принимаемого решения единообразно. Такого рода ситуации называются конфликтными и могут быть описаны моделями, которые называются играми. Модели конфликтных ситуаций, где присутствуют несколько сторон, преследующих различные интересы, называются игровыми моделями. Игровая модель представляет собой особый вид модели для принятия оптимальных решений. Теория, описывающая конфликтные ситуации с количественной стороны, называется теорией игр. 8.1. Основные понятия теории игр Игра – математическая модель ситуации, некоторая упрощённая схема, где зафиксированы все участвующие стороны, правила развития данной ситуации, определённые выигрыши после каждого хода, правила окончания игры. Из этого следует, что основными в игровой модели являются следующие элементы:  в игре могут быть две или более стороны, называемые игроками, которые преследуют различные интересы;  в игре фиксируют правила игры: возможные действия игроков, ситуация выигрыша и его величина, правила остановки игры;  игры бывают парные, когда есть только две стороны, и множественные, когда участие в игре принимают три и более сторон;  игры бывают коалиционные, когда часть игроков соединяют свои интересы и действуют как один игрок. Мы рассмотрим только парные игры как наиболее важные для моделирования реальных явлений. Результаты анализа таких моделей позволяют 142 сформулировать принципы и подходы к выработке оптимальных решений в условиях конкуренции. В парной игре два игрока: A – это «мы» и B – «противник». Игры называются антагонистическими, или с противоположными интересами, если игрок A выигрывает ровно столько, сколько проигрывает B. В сумме выигрыш равен 0, поэтому такую игру называют игрой с нулевой суммой. Но существуют также парные игры и с ненулевой суммой (неантагонистические). Ходы в игре могут быть личные и случайные. Личный ход зависит от сознательного решения стороны, а случайный ход - результат случайного механизма, который иногда применяется специально, а иногда случайно вовлекается в игру. В ходе проведения игры каждый игрок имеет какие-то альтернативы поведения, которые называют стратегиями игроков. В общем случае стратегия игрока – это совокупность правил, определяющих выбор вариантов действий при каждом личном ходе игрока в зависимости от сложившейся ситуации. Применение в каждой игре стратегии однозначно определяет исход игры. Если количество стратегий конечно - игра конечная, в противном случае - бесконечная игра. В теории игр считается, что игра повторяется многократно и игроков интересует средний выигрыш. Задачей теории игр является обоснование оптимальных стратегий обоих игроков. 8.2. Платежная матрица антагонистической игры, принцип минимакса Будем считать, что у игрока A всего m стратегий, а у игрока B – n стратегий. A 1 A 2 .......... A m B1 B 2 .......... .B n B1 a11 B2 a12 . А1 Bn a1n А2 . Аm a 21 . a m1 a 22 . a11 . a 2n . a mn Если игрок А применяет свою стратегию A i , а В применяет B j , то выигрыш в игре составляет a ij . А старается увеличивать выигрыш, а В – уменьшить эту величину. Величины a ij образуют матрицу, которая называется платежной матрицей . 143 Рассмотрим пример простейшей игры «Поиск». Игрок А прячется в двух местах I и II. Игрок В ищет игрока А в местах I и II. Если В находит А, то А платит ему 1 рубль, если не находит, то В платит 1 рубль игроку А. Платежная матрица тогда имеет вид: Основой для анализа игр является анализ платежной матрицы. Поэтому игры, для которых могут быть построены платежные матрицы, называются матричными играми. Для игр с полной информацией, т. е. когда один игрок знает, как поступил второй, всегда можно построить платёжную матрицу. Основным принципом, которым необходимо пользоваться для объективной оценки игровой ситуации, является следующий подход: противник настолько же разумен, как и мы, и делает все, чтобы использовать свои возможности против нас, т. е. активно противодействует в выборе оптимального решения. Задачей теории игр является обоснование оптимальных стратегий обоих игроков. Если игрок А будет применять любое сколь угодно сложное правило чередования мест I и II, то В все равно разгадает этот закон чередования и будет выигрывать. Ниже мы обоснуем оптимальные стратегии игроков А и В. Рассмотрим другие простые примеры игр. Игра «Три пальца». B1 -1 1 А1 А2 B2 1 -1 Игрок А и игрок В одновременно показывают один, два или три пальца. Выигрыш равен сумме, 4 причём выигрывает А, если сумма очков четная, А 2 и В, если сумма нечетная. Построим платёжную 3 1 4 А - матрицу . Игра «Конкуренты». 3 5 2 6 А 4 А B B B Фирма 5 3 может поставить 1 2 3 1А1 , А 2 , А 3 , А на рынок три товара а 2 2 1 фирма В три своих конкурирующих то1 2 А В1 , В 2 , В 3 вара . Если фирма А поста2 В А А -1 товар j , то в вит товар i , а фирма В 1 3 результате выигрыш в доходах фирм B 1 B 2 B 3 определяется приведенной платежной матрицей. 144 Возникает вопрос – как на основе анализа матрицы найти оптимальное решение игры, и что понимать под оптимальным решением игры? Рассмотрим так называемый принцип минимакса при решении игры. Ясно, что игроки должны действовать с разумной осторожностью, т. е. необходимо, чтобы мы больше всего реагировали на опасные для нас ходы со стороны противника. По отношению к игроку А рассуждаем так, что если он применит стратегию A1 , то можно зафиксировать самый плохой для него выигрыш: a 1  min a 1j . Для стратегии A 2 : a 2  min a 2 j , и так далее. Для A m : a m  min a mj . Тогда естественно, что игрок А выберет ту стратегию, для которой величина a i будет максимальной (по строкам в платежной матрице). Величина a  max min a ij называется нижней ценой игры. Она показыi j вает, меньше какой величины не будет выигрыш игрока А при осторожном подходе к игре. Аналогично рассуждая относительно игрока В, получаем величины: b j  max a ij - максимальные величины в столбцах, и затем b  max min a ij - верхняя цена игры. Эта величина показывает, больше j i какой величины не может быть выигрыш в игре. Получим значения a и b для вышеприведенных игр. Для игры «Поиск» a =-1; b =1. Для игры «Три пальца» a =-3; b =4. Для игры «Конкуренты» a = b =0. Эта игра обладает седловой точкой, так как в ней максимин совпадает с минимаксом. Принятие стратегий, соответствующих седловой точке, взаимоприемлемо для обоих игроков, поэтому их можно принять за оптимальное решение игры. Таким образом, пара стратегий ( A 2 , В 2 ) является оптимальным решением игры «Конкуренты». Оптимальный выигрыш в этой игре называется ценой игры и равен 0. Если игра имеет седловую точку, то говорят, что игра решается в чистых стратегиях. Решение, соответствующее седловой точке, обладает свойством устойчивости: если один игрок примет оптимальную стратегию, то другому невыгодно отклоняться от своей оптимальной стратегии. (Проверьте это, рассмотрев строку A 2 и столбец В 2 ). Такое свойство устойчивости положено в основу понятия оптимального решения любой игры. 145 8.3. Решение игр в смешанных стратегиях Если в игре верхняя и нижняя цена не совпадают ( a не равно b ), то значит, что седловой точки нет, но можно улучшить средний выигрыш игроков А и В путем смешивания их стратегий. Это значит, что игрок А, каждый раз играя игру, чередует свои чистые стратегии A 1 A 2 .......... A m . Вопрос состоит в том, какова должна быть доля случаев применения стратегий игроков. Назовем смешанной стратегией игрока А вектор S A  p1 , p 2 ,  , p m  , в котором показаны вероятности применения соответствующих стратегий. Например: S A  0,1; 0,2; 0,7; 0 ,  p i  1 - свойство полноты. m i 1 Аналогично для игрока В получаем: S B  q1 , q 2 ,  , q m  ,  q j  1 . i 1 Заметим, что чистая стратегия – это частный случай смешанной стратегии. A 3  S A  (0, 0, 1, 0) . Справедлива основная теорема теории игр: любая матричная игра имеет решение в виде пары смешанных стратегий игроков А и В S*A ; S*B , даn   * ющих оптимальное значение цены игры V . Это оптимальное решение обладает следующим свойством: если один игрок придерживается своей оптимальной стратегии, то другому невыгодно отклоняться от своей оптимальной стратегии. 8.4. Упрощение игр и аналитическое решение игр 2*2. Прежде чем решать игру, ее необходимо упростить, т. е. если для игры построена платежная матрица, можно вычеркнуть заведомо невыгодные стратегии для игроков А и В. B1 A1 5 A2 4 2 A3 B2 -1 2 B3 3 2 1 A1 B2 B3 3 A3 2 1 Здесь A 2 уступает по всем компонентам A 1 , а В 1 уступает и В 2 , и В 3 . Заметим, что строки лучше, если элементы больше, а столбцы лучше, если элементы меньше. Если по каждой компоненте стратегии одна строка хуже другой, то ее можно вычеркнуть. При этом решение игры упрощается. 146 В результате остаются такие строки и столбцы, которые нельзя сравнить. Если число оставшихся стратегий хотя бы одного игрока равно двум, то игру можно решить аналитически или геометрически. Рассмотрим игры, в которых у каждого игрока лишь две стратегии. Если в такой игре нет седловой точки, то значит, что все стратегии активны, т. е. они войдут в решение с какой-то вероятностью, не равной нулю. Справедлива теорема об активных стратегиях: если один из игроков придерживается своей оптимальной смешанной стратегии, то выигрыш остается неизменным и равен цене игры V независимо от того, что делает другой игрок, если только тот не выходит за пределы своих активных стратегий. q1 q2 Пусть мы применяем оптимальную смешанB1 B2 ную стратегию S*A , а игрок В отклоняется от своp1 A1 a11 a12 p2 A2 a21 a22 ей оптимальной стратегии S*B и применяет чистую стратегию В 1 или В 2 . По свойству реше-   ния игры это приведет к ухудшению выигрыша для В. Пусть S*A ; S*B дает величину V, тогда если А смешивает A 1 и A 2 , а В применяет одну и ту же стратегию В 1 , то выигрыш, который получится, будет равен математическому ожиданию.   a11 p1  a 21 p 2  v, если S*A , B 2 , то   a12 p1  a 22 p 2  v   p1  p 2  1  (8.1) Так как все стратегии активны, то на основании вышеприведенной теоремы можно решить эту систему при равенстве первых двух строк. p 2  1  p1 ; a11 p1  a 21 (1  p1 )  v; p1 (a11  a12  a 21  a 22 )   a 21  a 22 ; p1  a 22  a 21 a11  a 22  a12  a 21 p2  V a11  a12 a11  a 22  a12  a 21 a11  a 22  a12  a 21 a11  a 22  a12  a 21 8 .2 ; ; . 8 .3 8 .4 . Аналогично можно составить систему и решить ее для игрока В: 147 S S   , A1 : a11 q1  a 21 q 2  v;    , A2 : a 21 q1  a 22 q 2  v;   q1  q 2  1;   (8.5) q1  a22  a12 ; a11  a22  a12  a21 (8.6) q2  a11  a 21 ; a11  a 22  a12  a 21 (8.7) * B * B Например, для платежной матрицы B 1 B 2 А 3 А 2 1 1 2 1 2 1 1  ; q1  ; 0 1 2  3 4 2 3 1 1 p2  ; q2  ; v ; 4 2 4 p1  8.5. Геометрическое решение игр Рассмотрим игру 2x2 . Отложим по оси абсцисс единичный отрезок. Левый конец будет соответствовать чистой стратегии A 1 , а правый – стратегии A 2 . Любая точка внутри отрезка обозначает смешанную стратегию S(p 1 , p 2 ) . На оси ординат будем откладывать выигрыши. На левой вертикали будут выигрыши, полученные при применении чистых стратегий A 1 B1 и A 1 B 2 , а на правой – A 2 B1 и A 2 B 2 . Если А применяет смешанные стратегии, а В - чистые, то выигрыши будут ординатами соответствующих прямых. Решим игру для игрока А: для этого найдем сначала самые маленькие выигрыши при различных смешанных стратегиях – это будет линия минимумов. Затем на этой линии найдем наивысшую точку. Получим максимин. 148 Линия минимумов максимин B1 В2 a112 B a 22 v a12 a 21 A1 p2 В1 А2 p1 Аналогично задача решается для игрока В: находим линию максимумов и минимакс. минимакс A A1 2 Линия максимумов A v 1 B q2 1 q1 B2 A2 По принципу максимина игрок А сначала фиксирует свои минимальные выигрыши, а затем выбирает максимальный выигрыш. Так получаются величины p 1 и p 2 , q1 и q 2 на единичном отрезке и величина цены игры v. Примечания:  решение не обязательно находится на пересечении прямых;  если у одного игрока две стратегии, а у другого три и более стратегий, то игра также может быть решена геометрически. Пример: Все элементы строки A 2 А1 В2 В1 3 А2 1 А3 -1 В3 В4 -1 2 -1 -2 -2 4 -3 меньше элементов строки A 1 , поэтому A 2 можно отбросить как заведомо невыгодную. Все элементы столбца В 1 больше соответствующих 149 элементов столбца В 2 , поэтому стратегию В 1 отбрасываем как заведомо невыгодную. В2 -2 А1 А3 В3 -1 4 В4 2 -3 После вычеркивания столбца В 1 и строки A2 игра упрощается. Тогда останутся В 2 , В 3 , В 4 и А 1 , А 3 . Строим график решения со стороны игрока А. 4 В3 максимин В4 2 Линия минимумов p3 А1 В3 p1 v А3 М -1 -2 В 2 -3 В4 Находим линию минимумов (на рисунке выделено жирной линией) и определяем на ней максимум, точку М. Найдем точное решение, для чего определим координаты точки М. с этой целью зададим уравнения прямых В 2 и В 3 в виде v  f ( p 3 ) . Уравнение прямой построим в виде уравнения с угловым коэффициентом (y  kx  b) . v  kp 3  b , где k – тангенс угла наклона прямой; b – смещение по оси ординат (если прямая возрастает – k>0, если убывает, то k<0).  B 3 : v  5p 3  1; Построим прямую  ;  B 2 : v  2p 3  0. p 1 ;p 6 ;v2 . 7 7 7 150 В 2 3 А 1 4 А 2 1 - В Решим игру со стороны игрока В. Из графика видно, что стратегия В 4 не формирует оптимальное решение – точку М, т. е. не является активной, следовательно, ее отбрасываем 4 (она в согласованном решении не участвует). 4 Линия максимумов q2 q3 В2 N А3 -2 Находим линию максимумов и определяем на ней минимум – т. N. Запишем уравнения прямых A 1 и A 3 : v  6q 3  2; A3 . A1 : v  q 3 ; q 3  2 ; q 2  5 . 7 7 Ответ: Игрок А должен чередовать стратегии A 1 с вероятностью 6/7 и A 3 с вероятностью 1/7. Игрок В должен чередовать стратегии В 2 с вероятностью 5/7 и В 3 с вероятностью 2/7. При этом цена игры v=-2/7. 8.6. Решение игр с многими стратегиями на основе метода линейного программирования Пусть в игре m стратегий у игрока А и n – у В, матрица не упрощается. Такую игру можно свести к двум задачам линейного программирования. Рассмотрим это на примере матрицы для «игры полковника Блотто». В В В 1 2 3 4 В А 4 2 1 А 1 3 - А - 2 1 2 1 2 151 3 4 2 А 1 А - 2 3 1 1 2 4 5 Решение не изменится, если матрицу поднять на одну и ту же величину, чтобы все элементы были больше нуля. Получим: В В В 1 2 3 4 В А 6 4 3 2 А 3 5 2 1 А 4 4 А 1 2 5 3 А 2 3 4 6 1 2 3 4 5 Если мы примем оптимальную смешанную стратегию, и В примет свою оптимальную смешанную стратегию, то получим: *   S A  (p 1 , p 2 , p 3 , p 4 , p 5 );  *   S B  (q 1 , q 2 , q 3 , q 4 , q 5 ). Если А примет оптимальную стратегию, а В – чистую стратегию В 1 , т. е. отклонится от оптимальной, то средний выигрыш будет равен p1  6  p 2  3  p3  0  p 4 1  p 5  2 и будет не меньше v. ( M(x)  152 P X i i - математическое ожидание случайной величины).          S S S S * A * A * A * A  , B  : 4p , B  : 3p , B  : 2p , B1 : 6p 1  3p 2  0p 3  1p 4  2p 5  v; 2 1  5p 2  4p 3  2p 4  3p 5  v; 3 1  2p 2  4p 3  5p 4  4p 5  v; 4 1  1p 2  0p 3  3p 4  6p 5  v; (8.8) p 1  p 2  p 3  p 4  p 5  1. Обозначим pi v  xi; 1  L. v Так как при выборе p i необходимо, чтобы v→ max, то L  x 1  x 2  x 3  x 4  x 5  1  min v  6x 1  3x 2  0x 3  x 4  2x 5  1;   4x 1  5x 2  4x 3  2x 4  3x 5  1;   3x 1  2x 2  4x 3  5x 4  4x 5  1;  2x 1  x 2  0x 3  3x 4  6x 5  1.  (8.9) Получим задачу линейного программирования, которую можно решить симплекс-методом (см. главу 2) , в том числе и с использованием стандартных компьютерных программ, например, в системе LINDO или EXCEL. Аналогичную задачу получаем и со стороны игрока В. qj S*B , A i ;  y j; 1  L . v v При выборе q j игрок В стремится уменьшить v (v→ min), поэтому   L  y1  y 2  y 3  y 4  1  max v  6y 1  4y 2  3y 3  2y 4  1;   3y 1  5y 2  2y 3  y 4  1;   0y 1  4y 2  4y 3  0y 4  1;  y  2y  5y  3y  1; 2 3 4  1  2y 1  3y 2  4y 3  6y 4  1. (8.10) (8.11) Таким образом, решение игры mn сводится к паре задач линейного программирования. Анализируя задачи (8.8), (8.9) и (8.10), (8.11), можно 153 показать, что они всегда имеют решение! Действительно, в качестве допустимого решения (8.8), (8.9) всегда будет: x1 = 1/d ; x2=x3=… = xn=0; где d – самый маленький коэффициент среди aij . При этом оптимальное решение также всегда будет, т.к. линейная форма (8.8.) ограничена нулем (все слагаемые положительны). Этим доказывается основная теорема теории игр. 8.7. Биматричные игры Во многих ситуациях не обязательно, чтобы один игрок выигрывал, а другой столько же проигрывал. Такие игры называются неантагонистическими (с ненулевой суммой). Для двух игроков выигрыши в таких играх приходится записывать не одной, а двумя платежными матрицами, поэтому они имеют название биматричные игры. Интересы игроков здесь не являются полностью противоположными, и их поведение может быть более разнообразным. Различают некооперативные биматричные игры и кооперативные, в зависимости от того, могут ли договариваться игроки, или соглашение невозможно по правилам игры. Рассмотрим классическую модель некооперативной биматричной игры, известной как «Дилемма Заключенного». Два преступника ожидают приговора суда за совершение преступления. Адвокат конфиденциально предлагает каждому из преступников освободить его, если он сознается и даст показания против сообщника, которому грозит угодить в тюрьму на 10 лет. Если никто не сознается, то обоим угрожает получить 1 год за незначительное преступление. Если сознаются оба преступника, то с учетом чистосердечного признания они получат 5 лет. Построим платежные матрицы игроков со стратегиями «сознаться А A 1 », «сознаться В - В 1 », «не сознаваться А - A 2 », «не сознаваться В В 2 ». Первое число – выигрыш А, а второе - выигрыш В. Здесь игроки договориться не могут, поэтому им необходимо руководствоваться принципом здравого пессимизма и выбрать максиминную стратегию. В1 А1 А2 (5; 5) (10; 0) В2 (0; 10) (1; 1) Если А выберет А1, то в худшем случае он получит 5 лет, если A 2 , то в худшем случае он полу- чит 10 лет, поэтому А «из двух зол» выберет меньшее - A 1 . Игрок В если выберет В 1 , то в худшем случае получит 5 лет, а если В 2 , то 10 лет. Поэтому, чтобы не рисковать, он выберет В 1 . Получили «седловую точку» ( A 1 , В 1 ). 154 Таким образом, обоим заключенным лучше вместе сознаться и получить по 5 лет. Здесь ни одному из игроков невыгодно отклоняться от своей оптимальной стратегии в одиночку. Приведенный подход к решению некооперативных биматричных игр подобен принципу «минимакса» для матричных игр и называется нахождением точки равновесия по Нэшу. Нэш показал, что любая биматричная игра имеет решение в чистых или смешанных стратегиях. 8.8.Кооперативные игры Кооперативной игрой называют такую модель ситуации, когда выигрыши игроков не имеют нулевой суммы, и в которой игрокам разрешается обсуждать свои стратегии и договариваться о совместных действиях, т. е. образовывать коалиции. Основной задачей здесь является дележ общего выигрыша между членами коалиции. В случае двух игроков выигрыш в игре – это пара выигрышей, представляющих общие выигрыши. Если игроки будут перебирать всевозможные стратегии (чистые и смешанные), то все пространство выигрышей в игре образует некоторое множество точек, ограниченных некоторой линией (см. рисунок). На рисунке можно указать точку с координатами выигрышей игроков, которые они могут гарантировать себе, не прибегая к договоренностям ( Т 1 , Т 2 ). Такая точка называется точкой угрозы. На множестве выигрышей можно найти множество Парето-оптимальных решений. Парето-оптимальные точки, безусловно, лучше всех других точек множества выигрышей, так как они являются самыми правыми на горизонтали и самыми левыми на вертикали. Очевидно, что Парето-оптимальные точки – это северно-восточная граница множества выигрышей. Точки Парето-оптимального множества, находящиеся одновременно выше и правее точки угрозы Т, образуют переговорное множество. Очевидно, что игрокам выгодно договариваться, если их выигрыш будет лучше, чем тот, который получается в точке Т. На переговорном множестве выделяется точка решения Нэша (равновесная точка), в которой достигается максимум произведения превышения выигрышей над величинами Т 1 , Т 2 : Fm ax  Max (a 1  T1 )(a 2  T2 ) . Рассмотрим пример кооперативной игры «Семейный спор». Муж и жена каждый вечер решают проблему развлечения: пойти на Футбол или пойти на Балет. Муж любит Футбол и терпеть не может Балета. Жена любит Балет и не любит Футбол, но посещение этих зрелищ в одиночку не дает полного удовлетворения. Поэтому если они вместе, то получают удовольствие на 4 единицы на любимом зрелище и 1 единицу на нелюбимом, а если поодиночке, то 2 единицы на любимом и 0 на нелюбимом. 155 Платежные матрицы имеют такой вид (левое число – выигрыш жены, правое – выигрыш мужа): Жена Балет Балет (4; 1) Футбол (0; 0) Футбол (2; 2) (1; 4) Муж Множество возможных выигрышей – треугольник с вершинами, соответствующими чистым стратегиям. Ясно, что гарантированный выигрыш супругов – точка угрозы (2; 2). Множество Парето – точки на стороне ВС. Переговорное множество – точки на DE. Решение Нэша – точка N. Здесь супруги договариваются половину вечеров проводить вместе на Футболе, а половину – на Балете. А2 4 .В F→max .. . . D 3 N Т 2 Е Точка угрозы . C 1 А1 1 2 3 4 Эта точка получается как точка касания линий постоянного уровня величины F  (a 1  T1 )(a 2  T2 ) при F→max. Следовательно, решение такой игры дает супругам выигрыш (2,5; 2,5). 156 9. Элементы теории статистических оптимальных решений Это чрезвычайно развитая область в экономике, в военном деле, в области обработки информации на фоне шумов и т. д. Рассмотрим элементы этой теории как продолжение теории игр. Существуют задачи, в которых B - «бессознательный игрок», который мешает принимать нам принимать правильные решения, но он не противодействует активно, а действует в соответствии с природными случайными явлениями, поэтому такую ситуацию называют игрой с природой. Например, помехи в канале связи для передачи информации, шумы при записи или воспроизведении звука и т. д. Ясно что бессознательное воздействие в целом вредит нам меньше, чем сознательное. С другой стороны эта «бессознательность» приводит к непредсказуемому поведению операции. Можно считать ,что как и в теории игр мы боремся с противником, который не осознанно мешает нам. Например, это погодные условия, или случайный спрос при продаже товара. Вот почему в теории статистических решений, главной проблемой является обоснование принципов оценки различных ситуаций со стороны A . Заметим, что в теории игр был один принцип – принцип минимакса. Мы будем рассматривать дискретные альтернативы (стратегии) природы. Тогда, если у A имеется m стратегий, а у «природы» имеется n альтернатив, то может быть получена матрица выигрышей, при применении каждой пары Ai Pj P P1 P2 Pn A1 a11 a12 a1n A2 a21 a22 a2n . Условия j иногда называются гипотезами.. Если платежная матрица построена, то задача состоит в анализе матрицы с целью получить Am am1 am2 amn A стратегию i , которая наиболее выгодна по отношению к другим. В простейшем случае, если какие-то строки матрицы заведомо невыгодны, то их можно отбросить и оставить только одну, безусловно лучшую. Столбцы платёжной матрицы нельзя отбрасывать, т. к. условия «природы» могут быть и в нашу пользу. При анализе платёжной матрицы можно сделать неверный вывод о качестве нашего решения. 157 Пусть сравниваются два выигрыша, находящихся в разных столбцах akl , причём j  l . Если aij  a kl , то вроде бы решение в i  ой строке лучше, чем решение в k  ой строке, но так просто можно сравниa ij и вать, если выигрыш соответствует одинаковым условиям. Пример: Пусть в Томской области, приняв определенные управляющие решения, получили урожайность пшеницы 20 центнеров с гектара, а в Краснодарском крае - 25. Эти значения сравнивать нельзя, т. к. для Томской области это может быть рекордный (наилучший) результат, а для Краснодарского края – плохой, т.к. рекорд 50 . Решение нужно сравнивать с потенциальными возможностями. Вот почему необходимо преобразовывать платёжную матрицу таким образом, чтобы каждый наш выигрыш соотносился с тем максимумом, который можно достигнуть в данных условиях Pj . Для каждого Pj можно r    aij j найти максимальную величину βj и вычислить величину ij называемую риском. Здесь  j  max aij . Чем риск меньше, тем лучше. i 9.1. Принятие решений при известных априорных вероятностях Будем обозначать вероятности гипотез: Q1  pP1 , Q2  pP2 , , Qn  pPn  . Таким образом, мы считаем, что вероятности известны до того, как мы решили принять решение. Решение - выбор оптимальной стратегии A . Говорят, что это ситуация идеального наблюдателя. Естественно, в качестве критерия выбирается средний выигрыш, котоn A рый мы получим, если выберем стратегию i . ai   aijQ j j 1 . Это аналог математического ожидания. Решение принимается по критерию: max a i (9.1) i Это критерий максимального среднего выигрыша. Если задана матрица n ri   rijQ j j 1 рисков, то можно для каждой строки вычислить средний риск: и оптимальным будет являться решение, которое обеспечивает величину: 158 min ri (9.2) i Покажем, что оптимальное решение можно искать как по (9.1), так и по (9.2). Сложим средний выигрыш и средний риск получим константу ai  ri   aijQ j   rijQ j   aijQ j    j  aij Q j    j Q j  c n n n n n i 1 j 1 j 1 j 1 j 1 тогда: ai  ri  c  ai  c  ri ; max ai  min ri ; arg max ai  arg min ri i i . c  В результате решения выбирается чистая стратегия ai . Есть ли смысл смешивать стратегии? Пусть мы смешиваем наши стратегии с веро- p ятностями i , тогда в результате применения смешанной стратегии мы получим средний выигрыш в таком виде: a  a1 p1  a2 p2    am pm  математическое ожидание Мы знаем, что МО меньше максимального значения , следовательно в игре с природой нет смысла смешивать стратегии; чистая стратегия обеспечивает наилучший результат. Слабым местом в этом подходе является то, что надо знать априорные вероятности. Если они неизвестны, то необходимо их изучить. Это можно делать путём экспериментов, которые изучают условия «природы». Говорят, что этим мы обучаем нашу систему. Такой подход называется принципом адаптации к условиям. Если априорные вероятности изучить не удаётся, то применяется принцип недостаточности основания: если не знаем о вероятности, то считаем, что гипотезы природы равновероятны. После этого применяем критерий идеального наблюдателя. Так как при равных вероятностях энтропия (неопределённость) максимальна, то мы рассчитываем на худший случай , т.е.применяем принцип пессимизма. Если сами значения вероятности неизвестны, но есть информация о предпочтениях гипотез, то существуют методы обработки предпочтений и получения вероятностей. Если вероятности гипотез относятся как: n : n  1 : n  2 :  : 2 : 1  Q1 : Q2 :  : Qn ; n Q j 1 j 1 , то можно подсчитать саму величину вероятности в следующем виде: Qj  2n  j  1 ; j  1, n nn  1 В некоторых случаях учитывается не только средний выигрыш, но также и дисперсия, т. е. величина разброса выигрыша в каждой строке: 159   max ai  k  ai ;  ai  Dai i 9.2. Методы принятия решений в условиях априорной неопределенности Если априорная информация неизвестно или ненадёжна, то применяются другие критерии. Критерий Вальда W : это максиминный критерий, т. е. выбирается я A W  max min aij j i стратегия k , для которой . При таком критерии мы подходим к этой задаче, рассчитывая на самый худший случай, как и в игре с разумным противником. Критерий Сэвиджа S  : это критерий минимаксного риска: S  min max rij i j . Этот критерий не эквивалентен критерию Вальда, т. е. Стратегия, оптимальная по Сэвиджу не обязательно так же будет оптимальна по Вальду. Критерий Гурвица H : это комбинированный критерий, его так же называют критерием пессимизма-оптимизма: H  max   min aij  1    max aij  j i  j  ; 0    1  коэффициент, который выполняет требования критерия быть более или менее оптимистичным. При  1  H  W , а при   0 , H  крайний оптимизм. Существуют другие критерии и однозначный выбор одного критерия невозможен. Но если одну и ту же ситуацию рассматривать по разным критериям и получаются одинаковые решения, то это говорит об устойчивости данной ситуации и однозначности найденного оптимального решения. В противном случае ситуация неустойчивая и необходимо либо изучать априорную информацию, либо доказывать верность лишь одного из критериев. 9.3. Планирование эксперимента при принятии решений Если априорной информации нет или она ненадёжна, то можно путём проведения эксперимента получить более надёжные данные о вероятностях Q Qj j . Под экспериментом понимают систему мероприятий позволяющих уточнить информацию о состоянии «природы». Например, это метеонаблюдения, маркетинговые исследования в экономике, радиолокация, военная или промышленная разведка и т.д. Насколько может помочь в приня160 тии решения эксперимент и как сопоставить стоимость эксперимента с тем оптимальным выигрышем, который мы получим? Соответствующую теорию можно построить исходя из знания вероятностей Q j , а так же на основе критериев при неизвестной априорной информации. Мы рассмотрим случай, когда есть априорная информация, т. е. ситуацию идеального наблюдателя. Рассмотрим вопрос: есть ли смысл проводить эксперимент? Рассмотрим два случая. 1) Идеальный эксперимент. Результат этого эксперимента однозначно определяет каковы условия природы. Пусть заданы выигрыши орные вероятности Qj . Стоимость эксперимента a ij и апри- с сопоставима с выиг- a рышем ij , т. е. эти величины имеют одинаковую размерность. Сравним средний выигрыш без проведения эксперимента со средним выигрышем при проведении эксперимента:  n  max   aijQ j   amax i i  1   Если нет эксперимента мы обеспечим себе . Если мы проведём эксперимент, то мы точно узнаем Pj  Pk , и тогда найдя в k  ом столбце максимальный выигрыш, мы найдём наш выигmax a   k рыш: i ij . Но нам нужно оценить эффективность эксперимента до его проведения, поэтому мы должны ориентироваться на средний ожидаемый выигрыш, который мы получим, если будем проводить эксперимент. Таким образом, перед проведением эксперимента мы можем ожидать выигрыш n Qj   j 1 j . Поэтому чтобы решить, проводить эксперимент или нет, надо определить, что больше: amax или n Q j 1 j   j  c . Получается, что необхо- n Q  j n j  c  max  Q j aij i j 1 димо проводить эксперимент, если: j 1 Преобразовав это неравенство, получим, что идеальный эксперимент проводить нужно, если его стоимость меньше минимального среднего риска c  min ri i 2) Неидеальный эксперимент. В результате проведения неидеального эксперимента мы не находим однозначно Pj , а лишь изменяем вероятности 161 Qj . Пусть проводится неидеальный эксперимент. В результате появляются некоторые несовместные события B1,B2,…BL. Вероятности этих событий P B P  l j зависят от условий, в которых они проводятся. Пусть известны . Эти вероятности называются прямыми. После эксперимента, давшего ис- ход Bl необходимо пересмотреть вероятности Q j , т. е. вместо вероятно- Q Q сти j мы перейдём к вероятности jl . Это так называемые апостериорные вероятности: Q j  PBl Pj  Q jl  PPj Bl   n      Q  P B P  j l j j 1 формула Байеса. Но результаты эксперимента могут быть и B1 и B2 и Bk , поэтому мы можем только ожидать всякие исходы Bl , которые получатся в результате эксперимента. Причём, каждый исход Bl привёл бы к некоторым опти- мальным стратегиям лучилась: * l . A  А величина выигрыша, которая бы при этом по- n ~ a~ l  max a~ il  max  Q jl  aij i i  j 1 a~ l , могут произойти с вероятностью события Bl , т. е. PBl  , которую можно получить по формуле полной веc вероятностью. Эти выигрыши роятности: PBl    Q j PBl Pj  n j 1 Тогда средний ожидаемый выигрыш будет: k a~   al PBl   a~  c  max  Q j aij  a~  c  amax l 1 i Планирование экспериментов можно рассмотреть и для случаев, когда проводят 2,3,4, эксперимента [ ]. 9.4. Многоэтапное принятие решений 162 Мы рассмотрели различные критерии принятия решений в условиях неопределённости. На практике, в таких задачах как, проСлучайная ектирование изделий, управвершина ление процессами, создании сложных программных комплексов, мы можем столкнуться с принятием последовательных решений (цепочкой решений). Особое значение такие многоэтапные решения имеют при создании автоматизированных экспертных систем. Рассмотрим вопрос оптимизации многоэтапных решений. Многоэтапность приводит к тому, что схема принятия решения может быть представлена в виде дерева, в каждой вершине которого осуществляется либо: 1)Сознательный выбор между двумя и более альтернативами 2)Случайный переход из одной ветви в другую под воздействием внешних случайных факторов Рассмотрим пример оптимизации многоэтапных решений на примере экономической задачи. Пример. Фирма может принять решение о строительстве крупного или мелкого предприятия. Строительство крупного предприятия относительно дешевле, в случае если будет высокий спрос на производимые товары, мелкое предприятие можно расширить. Деятельность фирмы рассматривается в течение десяти лет, причём в случае строительства мелкого предприятия, вопрос о расширении будет рассматриваться через два года. Спрос заранее неизвестен. Сознательное принятие решения p=0,75 крупное 1,0 2 p=0,25 0,3 расш 1 p=0,75 мелкое p=0,25 0,2 p=0,75 0,25 p=0,25 0,2 4 p=0,25 2 года 0,9 5 без расш. 3 p=0,75 6 0,2 8 лет Введём градацию случайного спроса: высокий  p  0.75 и низкий  p  0.25 . Затраты и доходы: строительство крупного предприятия - 5 163 млн. $; строительство мелкого - 1 млн. $; затраты на расширение - 4,2 млн. $; крупное предприятие при высоком спросе даёт доход - 1 млн. $ ежегодно, а при низком - 300 тыс. $; мелкое предприятие при высоком спросе 250 тыс. $ ежегодно, при низком - 200 тыс. $; расширенное предприятие в случае высокого спроса приносит доход - 900 тыс. $ в год, и при низком спросе - 200 тыс. $; мелкое предприятие без расширения при высоком спросе на производимый продукт приносит в течение двух лет по 250 тыс. $ ежегодно, а в течение следующих восьми по 200 тыс. $. Нарисуем дерево решений. Применим для решения этой задачи метод динамического программирования. В качестве критерия применим средний выигрыш, т. .е МО выигрыша. Сама величина критерия равна доходу без затрат на строительство. Начнём с последнего четвёртого шага: подсчитаем средний выигрыш: 4 a расш  0,9 * 0,75  0,2 * 0,25 * 8  4,2  1,6 4 aбез расш  0,25 * 0,75  0,2 * 0,25  * 8  1,9 1 aкруп  1* 0,75  0,3 * 0,25 *10  5,0  3,25 1 a м ел к  1,9  2 * 0,25 * 0,75  0,2 *10 * 0,25  1,3 Исходя из полученного результата, оптимальным будет сразу строить крупное предприятие. Другим примером оптимизации многоэтапных операций является известная «задача о секретарше». Директор собирается принять на работу секретаршу. Прежний опыт делит секретарш на три категории: отличных (3 балла), хороших (2 балла) и посредственных (1 балл). Анализ учебных заведений по подготовке секретарш даёт статистику выпускниц заведений: вероятность взять на работу отличную секретаршу - 0,2, хорошую - 0,5, посредственную - 0,3. директор может испытать только трёх претенденток, причём в случае отказа директора кандидат убывает на другую работу. Построим дерево решений. 164 p=0,2 p=0,2 stop a=3 продолжить 1 3 p=0,3 stop p=0,5 stop p=0,3 p=0,3 stop a=1 продолжить stop stop a=3 продолжить 2 p=0,2 stop a=1 продолжить p=0,5 p=0,5 stop a=2 stop a=2 В соответствии с процедурой динамического программирования начнём искать оптимальное решение с последнего шага. Определим математическое ожидание «выигрыша», если мы испытываем третьего кандидата: a3  3 * 0.2  2 * 0.5  1* 0.3  1.9 Далее определим средний выигрыш, если мы испытываем второго и третьего, с учетом того, что если второй будет посредственный, то мы продолжим и получим в среднем 1.9. a2  3 * 0.2  2 * 0.5  1.9 * 0.3  2.17 Поэтому если во втором испытании попалась хорошая секретарша, надо остановиться, т.к. получим 2, а если продолжим , то только 1.9. При первом испытании, надо остановиться только если попалась отличная, а в третьем испытании берём любую. Найдём средний оптимальный выигрыш при оптимальном правиле испытания трех кандидатов: a1  3 * 0.2  2.17 * 0.5  2.17 * 0.3  2.336 Следовательно за чет возможности испытывать трех секретарш мы получаем дополнительный выигрыш 2.336 – 1.9 = 0.436. 165 10. Экспертные процедуры для принятия решений В практических задачах принятия оптимального решения альтернативы не является “математическими объектами”, а чаще представляют собой конкретные физические системы: продукты, технологии, организация технического мероприятия, системы и т.д. Для описания альтернатив и оценки последствий их принятия необходимо решить следующие задачи: – построить множество возможных и допустимых альтернатив; – сформировать набор аспектов, существенных для оценки альтернатив; – определить критериальное пространство; – упорядочить альтернативы по аспектам; – получить оценку альтернатив по критериям, то есть найти отображение Ω в критериальное пространство (см. главу 7). Все эти задачи являются модификацией общей задачи оценивания: сопоставление числа или нескольких чисел рассматриваемой альтернативе. Методы решения задачи оценивания основаны на использовании экспертных процедур, поэтому их называют методами экспертных оценок. 10.1. Общая схема экспертизы В общем случае из-за сложности оценивания систем привлекаются люди – специалисты в данной предметной области – эксперты. Решение задач оценивания называют экспертизой. Вопросы, связанные с экспертизой, рассматриваются и решаются консультантом. Он определяет Ω, а иногда и вспомогательное множество для экспертизы Ωэ и организует всю процедуру экспертизы. 1. Консультант находит множество допустимых оценок Ω, в которых содержится исходная оценка. 2. Он определяет множество допустимых оценок Ωэ, из которого осуществляют выбор эксперты. 3. Каждый эксперт выбирает свою оценку ai  Ci (Ωэ), i= 1,N . При этом эксперты могут взаимодействовать между собой. 4. По заранее разработанному алгоритму (формуле) консультант производит обработку полученной от экспертов информации и находит результирующую оценку, являющуюся решением исходной задачи оценивания.   5. Если полученное решение не устраивает консультанта, то он предоставляет экспертам дополнительную информацию, то есть организует обратную связь, после чего они вновь решают задачу оценивания. 166 10.2. Задача оценивания Смысл оценивания состоит в сопоставлении альтернативе вектора из Еm. Перечислим типичные варианты этой задачи: 1. Пусть X  – альтернатива в задаче принятия решений. Имеются m критериев. Требуется альтернативе X  сопоставить вектор [f1(x),f(x),…fm(x)]  E m . 2. Пусть k1,k2,…km – критерии, учитывающиеся при выборе. Их необходимо  упорядочить по важности. Тогда системе S=(k1,k2,…km) сопоставляется перестановке натуральных чисел от 1 до m , i1,…im ,где ik – номер k-ого критерия при упорядочивании по важности.  3. Пусть множество D разбито на l подмножеств D1,D2,,…Dl. Для элемента х є D необходимо указать, к какому из подмножеств Di (i = 1, l ) он относится. То есть х сопоставляется одно из чисел от 1 до l. Пусть х отрезок, длину которого надо измерить. То есть отрезку надо сопоставить действительное число; f(x) – длина отрезка. Задача №1 – это общая задача многокритериальной оценки.  Задача №2 – это задача ранжирования. Задача №3 – это задача классификации. Задача №4 – это обычная задача измерения. Обозначим Ω – исходное множество допустимых значений оценок (МДО). Ωэ - МДО для экспертов; L – взаимодействие между экспертами; Q – обратная связь; φ – обработка (отображение  э   ) N Назовем схемой экспертизы пятерку параметров (Ω,Ωэ,L,Q,φ). Подготовка экспертизы – это предварительная разработка схем экспертизы и подбор экспертов. Реализация экспертизы – получение от экспертов информации и её обработка. 10.3. Подготовка экспертизы Определение МДО (множества допустимых оценок). Перечислим типы МДО и укажем определяющие их задачи оценивания. 1. Ω ={0,1}. Соответствующая задача попарного сравнения заключается в выявлении лучшего из двух имеющихся объектов a и b: 1, если a лучше b C     0, в противном случае 167 2. Ω={(1,2,…,n)(1.3,…n)…(n, n-1,…1)}. То есть Ω состоит из множества перестановок длины n. Соответствующая задача ранжирования состоит в упорядочивании объектов: C(Ω)=(i1,i2,…,in). 3. Ω={1…l}. Соответствующая задача классификации С(Ω)=i ,если X  Si Определение МДО для экспертов Ωэ. Типы Ωэ те же, что и Ω. Но Ωэ зависит от формы опроса: интервью, анкетирование, метод докладной записки эксперта – высказывание мнения в свободной форме.  Взаимодействие экспертов L. 1.Свободный обмен информацией между экспертами. 2.Обмен регламентирован. 3.Эксперты изолированы. Пункт (2) может иметь вид «Мозговой атаки»: в течение заданного времени любое мнение не может быть отвергнуто и не подлежит обсуждению. Обратная связь. После обработки можно ознакомить экспертов с результатами и попросить дать повторную оценку. Известен метод Делфи. После экспертизы проверяется согласованность, а затем, если она не достаточная, экспертам сообщается дополнительная информация и аргументация других экспертов. Затем экспертиза повторяется. Подбор экспертов. Существуют методы оценки компетентности экспертов. Эксперты могут выставлять свои оценки компетентности себе и другим. Затем эта информация обобщается и используется в алгоритмах оценки. 10.4. Методы обработки экспертной информации Существует три вида методов обработки: – статистические методы; – алгебраические методы; – методы шкалирования. Рассмотрим статистические методы экспертных оценок. Результаты оценок каждого эксперта можно рассматривать как реализацию некоторой случайной величины из Ωэ и применять к ним методы математической статистики. Статистические методы позволяют определить согласованность мнений экспертов, значимость полученных оценок и т.д., то есть качество экспертизы. Численные оценки. Экспертиза Э1. Задача состоит в сопоставлении оцениваемой альтернативе (системе) одного числа. (Ω=E1, Ωэ=E1, L – эксперты изолированы; Q – обратная связь отсутствует) 168 N  x1 , x2 , xN   x i 1 N i  i 1 i a (10.1) i αi – вес (коэффициент компетентности) экспертов xi – числовые оценки экспертов. При отсутствии информации о компетентности экспертов αi=1. Степенью согласованности мнений экспертов служит дисперсия: N 2   a  x   2 i i (10.2) i1 N  i i1 Другая экспертиза Э2 повышает точность оценивания (Ωэ=Е3)  x11 , x12 , x31 , x12 , x22 , x32 , , x1N , x2N , x3N    N  i 1 x1i 1  x2i  2  x3i  3 1 i  N 1   2   3  i 1 (10.3) i x1i , x 2i , x 3i – оптимистическая, наиболее вероятная, и пессимистическая  оценки i-ого эксперта. γ1,γ2,γ3 – определяются эмпирически (например, по одной методике γ1=1, γ2=4, γ3=36, по другой γ1=3, γ2=0, γ3=2, γ4=25, где γ4 – степень неуверенности эксперта в своем ответе.) ( γ1>γ3 , так как человек склонен к занижению оценки) Степень согласованности экспертов определяется дисперсией 2 N  1 x i  x 2i  2  x 3i  3  1 (10.4)  2   i i2  N  a  1 1    i N        1 2 3 i1  i1  i2  x 3i  x1i   2   i  i i1 1 4 В экспертизах Э1 и Э2 можно определить статистическую значимость полученных результатов. Задавшись Рош , укажем интервал, в который оцениваемая величина попадет с вероятностью 1-Рош. ā – Δ