Описанный механизм является механизмом открытого управления. Действительно, в конечном счете все Потребители делятся на приоритетных (которые получили столько, сколько просили) и неприоритетных (к последним в приведенном примере относятся первый и восьмой Потребители). Приоритетные получают столько, сколько просят, поэтому им не имеет смысла искажать свои реальные потребности. Неприоритетные же, как нетрудно видеть, не могут увеличить выделенный им ресурс ни повышая, ни понижая свою заявку.
Таким образом, при распределении ресурсов в соответствии с описанным механизмом Центр получает достоверную информацию о реальных запросах Потребителей.
Открытое управление и экспертный опрос
Если требуется определить объем финансирования крупного проекта, то часто прибегают к проведению экспертного опроса. Мы рассмотрим следующую процедуру опроса. Каждому из п экспертов предлагается сообщить число s из отрезка [d; D], после чего на основании экспертных оценок определяется итоговое решение х. Задача состоит как раз в том, чтобы определить число x, исходя из заданных si (i = 1, 2,... , п).
На первый взгляд кажется, что наилучшее решение здесь — взять в качестве итогового решения среднее арифметическое мнений экспертов
. (3)
Однако у такого решения есть существенный недостаток.
Дело состоит в следующем. У каждого эксперта есть мнение ri-относительно объема финансирования. И если эксперт каким-либо образом заинтересован в том, чтобы итоговая оценка х совпала с его мнением ri, то он может попытаться добиться этого совпадения, сообщая оценку 
.
Пример 4. Пусть три эксперта имеют следующие мнения:
r1 = 10, r2 = 10, r3 = 40.
Если каждый из них сообщит свое мнение без искажений, то при принятии решения по способу (4) результат будет таким:
.
Однако третий эксперт может (имея представление о мнениях остальных двух экспертов) сообщить оценку s3 = 100. Тогда итоговый результат
как раз совпадет с его истинным мнением г3.
Замечание. В теории коллективного принятия решений такой способ действий называется манипулированием. В свою очередь, если механизм коллективного принятия решений допускает манипулирование с чьей-либо стороны, то он называется манипулируемым. Рассмотренный только что пример показал, что механизм (3) является манипулируемым: искажая свои истинные предпочтения, можно приблизить итоговое коллективное решение к собственному истинному предпочтению.
Пример манипулирования со стороны избирателей можно было наблюдать в первом туре президентских выборов в России в 1996 г. Определенное число избирателей, считавших лучшей кандидатурой Явлинского, голосовали за Ельцина (с целью предотвратить победу Зюганова).
Вернемся к экспертному опросу. Говоря более строго, i-й эксперт решает задачу
т. е. пытается минимизировать разность между итоговым решением х и своим истинным мнением гi путем надлежащего выбора сообщаемой оценки si.
Опишем механизм выработки решения х*, являющийся механизмом открытого управления (т. е. неманипулируемым механизмом).
Напомним, что эксперты сообщают свои оценки
, i = 1, 2,..., п.
Будем считать, не ограничивая общности, что оценки экспертов расположены по неубыванию:
(этого всегда можно добиться перенумерацией экспертов). Вычисляются п вспомогательных чисел
, i = 1, 2,..., п.
(эти числа делят отрезок [d, D] на п равных частей). После этого для каждого i берется меньшее из двух чисел sj и vi.
.
И, наконец, из всех этих минимумов выбирается наибольший, который и является итоговым решением:
.
Можно доказать, что описанный механизм является механизмом открытого управления.
Пример 5. Пусть 6 экспертов сообщили следующие оценки из промежутка [30,90]: 65, 90, 45, 80, 75, 90. Определить итоговое решение в соответствии с описанным механизмом.
Решение. Выпишем числа vi (здесь 
):
v1 = 90, v4 = 9= 60,
v2 = 9= 80, v5 = 9= 50,
v3 = 9= 70, v6 = 9= 40.
Дальнейшее удобно изобразить в виде таблицы, в первой строке которой записаны упорядоченные по неубыванию оценки экспертов:
si: | 45 | 65 | 75 | 80 | 90 | 90 |
vi: | 90 | 80 | 70 | 60 | 50 | 40 |
| 45 | 65 | |70| | 60 | 50 | 40 |
В качестве итогового решения берется максимальное число в последней строке:
x* = 70.
Замечание. Во всех предыдущих рассуждениях квалификация экспертов предполагается одинаковой. Можно в случае необходимости вводить коэффициенты, позволяющие учитывать мнение разных экспертов различным образом — принципиально это ничего не меняет, лишь несколько усложняется вычисление итогового результата x*.
ТЕМА 10. Нелинейное программирование
План темы.
1. Общая формулировка нелинейных задач.
2. Виды нелинейных функций
3. Методы решения задач нелинейного программирования.
4. Метод множителей Лагранжа.
Нелинейное программирование — случай математического программирования, в котором целевой функцией или ограничением является нелинейная функция.
Задача нелинейного программирования ставится как задача нахождения оптимума определенной целевой функции 
при выполнении условий
где 
— параметры, 
— ограничения, 
— количество параметров, 
— количество ограничений.
В отличие от задачи линейного программирования, в задаче программирования нелинейного оптимум не обязательно лежит на границе области, определенной ограничениями.
Виды нелинейных функций.
Квадратичная функция – это функция вида
, где
a, b и c- некоторые числа, причем a ≠ 0. Графиком квадратичной функции является парабола, ветви которой направлены вверх (при a>0) или вниз (при a<0).
Кубическая функция – это функция вида
где
a, b, c и d - некоторые числа, причем a ≠ 0. Графиком кубической функции является кубическая парабола.
К простейшим элементарным функциям относится и функция
, где k≠0.
Графиком этой функции является гипербола.
Показательная функция задается уравнением
, где a > 0, a ≠ 1.
Если даны числовое множество X и правило f¸ позволяющее поставить в соответствие каждому элементу x из множества X определенное число y, что говорят что задана функция y=f(x) с областью определения X: y=f(x), D (f)=X.
Значения переменных, на которых задается функция y=f(x), называют допустимыми значениями переменных.
Многие задачи оптимизации формулируются следующим образом. Решение, которое должен принять субъект, описывается набором чисел х1 ,х2 ,…,хn (или точкой Х=(х1 ,х2 ,…,хn) n-мерного пространства). Достоинства того или иного решения определяются значениями функция f(X) = f(х1, х2 ,…,хn) -- целевой функции. Наилучшее решение -- это такая точка Х, в которой функция f(Х) принимает наибольшее значение. Задача нахождения такой точки описывается следующим образом:
.
Если функция f(X) характеризует отрицательные стороны решения (ущерб, убытки и т. п.), то ищется точка Х, в которой значение f(X) минимально:
.
Минимум и максимум объединяются понятием экстремума. Для определенности мы будем говорить только о задачах максимизации. Поиск минимума не требует специального рассмотрения, поскольку заменой целевой функции f(X) на - f(Х) всегда можно “превратить недостатки в достоинства” и свести минимизацию к максимизации.
Из каких вариантов должен быть выбран наилучший? Иными словами, среди каких точек пространства нужно искать оптимум. Ответ на этот вопрос связан с таким элементом оптимизационной задачи, как множество допустимых решений. В некоторых задачах допустимыми являются любые комбинации чисел х1, х2,…,хn то есть множество допустимых решений - это все рассматриваемое пространство.
В других задачах следует принимать во внимание различные ограничения, означающие, что не все точки пространства доступны при выборе. В содержательных постановках задач это может быть связано, например, с ограниченностью располагаемого количества ресурсов.
Ограничения могут быть представлены в форме равенств вида
g(X) = О
или неравенства
g(X) < О или g(X) > О.
Если условия имеют несколько другую форму, скажем, g1(Х) = g2(X) или g(X) A, то их можно привести к стандартному виду, перенеся в функции и константы в одну из частей равенства или неравенства.
Экстремум, отыскиваемый во всем пространстве, без каких-либо ограничивающих условий, носит название безусловного. Если целевая функция непрерывно дифференцируема, то, необходимое условие безусловного экстремума функции состоит в равенстве нулю всех ее частных производных:
Если же заданы ограничения, то экстремум ищется лишь среди точек, которые удовлетворяют всем ограничениям задачи, так как только такие точки являются допустимыми. В этом случае экстремум носит название условного.
Условным экстремумом функции z = f (х, у) называется экстремум этой функции, достигнутый при условии, что переменные х и у связаны уравнением φ (х, у) = 0 (уравнением связи).
Пусть требуется найти максимумы и минимумы функции f (х, у) при условии, что х и у связаны уравнением φ (х, у) = 0.
При наличии условия φ (х, у) = 0 из двух переменных х и у независимой будет только одна, например, х, так как у определяется из равенства φ (х, у) = 0 как функция от х.
Найдём полные производные 
и 
:
, (1)
. (2)
В точках экстремума 
, то есть 
. (3)
также равна нулю, так как φ (х, у) = 0, то есть
. (4)
Составим линейную комбинацию: 
. Получим:
или
(5)
λ – неопределённый постоянный множитель.
Последнее равенство выполняется во всех точках экстремума. Подберём λ так, чтобы для значений х и у, соответствующих экстремуму функции f (х, у), вторая скобка в равенстве (5) обратилась в нуль (метод Лагранжа).
Для определённости будем предполагать, что в критических точках 
.
Тогда из (5) следует равенство 
.
Таким образом, для отыскания экстремума получим следующую систему уравнений с тремя неизвестными х, у, λ :
(6)
Из этих уравнений определяем х, у и коэффициент λ , который играет только вспомогательную роль и в дальнейшем не потребуется.
Таким образом, уравнения (6) являются необходимыми условиями условного экстремума.
Замечание. В сущности, исследование на условный экстремум функции z = f (х, у), при условии φ (х, у) = 0 сводится к исследованию на обычный экстремум так называемой функции Лагранжа.
u = f (х, у) + λ φ (х, у), (7)
где λ – неопределённый постоянный множитель.
Необходимые условия для неё:
(8)
Сравните с системой (6).
Сформулируем достаточное условие условного экстремума в критической точке M0(x0,y0), предполагая, что функции z = f (х, у) и φ (х, у) = 0 имеют в точке M0 непрерывные частные производные второго порядка.
Составим функцию Лагранжа u = f (х, у) + λ φ (х, у) и определитель:
.
Если определитель
, то M0 есть точка условного минимума, если , то M0 – точка условного максимума.
Пример. Найти экстремумы функции z = x2 – y2 при условии 2x – y = 3.
Решение. Составим систему (6), считая φ (x, y) = 2x – y – 3:.
Исключая 
из первых двух уравнений, получим:
Проверим достаточное условие. Вычислим 
:
Значит, точка (2, 1) не является экстремальной для функции z = x2 – y2, но является точкой условного экстремума (условный максимум) функции z = x2 – y2 при условии 2x - y = 3: zmax = 3.
Матричные игры.
Предметом исследований в теории игр являются модели и методы принятия решений в ситуациях, где участвуют несколько сторон (игроков). Цели игроков различны, часто противоположны. Мы будем рассматривать только игры двух лиц с противоположными интересами.
Игра состоит из последовательности ходов . Ходы бывают личные и случайные. (В шахматах все ходы личные. Рулетка содержит случайный ход).
Результаты ходов оцениваются функцией выигрыша для каждого игрока. Если сумма выигрышей равна 0, то игра называется игрой с нулевой суммой (преферанс). Будем рассматривать только такие игры.
Стратегией называется набор правил, определяющих поведение игрока, т. е. выбор хода.
Оптимальной стратегией называют такую стратегию, при которой достигается максимальный ожидаемый средний выигрыш при многократном повторении игры.
Матричные игры — это игры, где два игрока играют в игру с нулевой суммой, имея конечное число «чистых» стратегий: {1,…, m} и {1,…, n} и ∀ (ij) задан платеж aij второго игрока первому. Матрица (aij) задает выигрыш первого игрока и проигрыш второго, aij ≷ 0 !
Рассмотрим игру, в которой участвуют два игрока, причем каждый из них имеет конечное число стратегий.
Обозначим для удобства одного из игроков через А, а другого – через В. Предположим, что игрок А имеет m стратегий: A1, A2, …, Am, а игрок В – n стратегий: В1, В2, …, Вn.
Пусть игрок А выбрал стратегию Ai, а игрок В – стратегию Вk.
Будем считать, что выбор игроками стратегий Ai и Вk однозначно определяет исход игры – выигрыш aik игрока А и выигрыш bik игрока В, причем эти выигрыши связаны равенством
bik= aik.
Последнее условие показывает, что в рассматриваемых обстоятельствах выигрыш одного из игроков равен выигрышу другого, взятому с противоположным знаком. Поэтому при анализе такой игры можно рассматривать выигрыши только одного из игроков. Пусть это будут, например выигрыши игрока А.
Если нам известны значения aik выигрыша при каждой паре стратегий (в каждой ситуации) {Ai, Bk}, i=1, 2, …, m, k=1, 2. …, n, то их удобно записывать или в виде прямоугольной таблицы, строки которой соответствуют стратегиям игрока А, а столбцы – стратегиям игрока В,
B1 | B2 | … | Bn | |
А1 | a11 | a12 | … | a1n |
А2 | a21 | a22 | … | a2n |
… | …. | … | … | … |
Аm | am1 | am2 | … | amn |
Или в виде матрицы
.
Полученная матрица имеет размер mxn и называется матрицей игры или платежной матрицей (отсюда и название игры – матричная).
Матричные игры относятся к разряду так называемых антагонистических игр, т. е. игр, в которых интересы игроков прямо противоположны.
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 |
