Элементы теории игр (стр. 2 )

Решение.

Составим функцию Лагранжа:

.

Найдем стационарные точки функции Лагранжа:

Из данной системы получаем: .

Точка (3;1) - точка условного экстремума функции .

Выпуклые множества и выпуклые функции.

Множество М называется выпуклым, если для любых точек выполнено: , при условии, что .

Функция , определенная на выпуклом множестве n-мерного пространства, называется выпуклой на этом множестве, если:

для всех и для всех .

Если в данном определении знак "£" поменять на знак "³", то тем самым определится вогнутая функция.

Если неравенство строгое, то функция строго выпуклая (вогнутая) соответственно.

Геометрически условие выпуклости (вогнутости) функции означает, что отрезок, соединяющий любые две точки плоскости лежит не выше (не ниже) самой линии функции.

 

Алгебраические и аналитические свойства выпуклых функций.

1.  Если - выпуклая функция, то - вогнутая функция.

2.  и являются всюду выпуклыми и всюду вогнутыми.

3.  Если выпуклы, то для любых действительных - выпуклая.

4.  Если выпукла, то любая область решения неравенства является либо выпуклым либо пустым.

5.  Если выпуклы при любых неотрицательных значениях переменных, т область решения системы неравенств является выпуклым множеством или пуста.

6.  Выпуклая (вогнутая) функция, определенная на выпуклом множестве М, непрерывна в каждой внутренней точке этого множества.

7.  Всякая дифференцируемая и строго выпуклая (вогнутая) функция имеет не более одной стационарной точки. При этом стационарная точка всегда является точкой локального и глобального минимума (максимума).

8.  Дважды дифференцируемая функция является выпуклой тогда и только тогда, когда для любых и не обращающихся в ноль одновременно.

Критерий Сильвестра: свойство 8 выполнено тогда и только тогда, когда неотрицательны все главные миноры матрицы вторых частных производных.

Если все главные миноры , то функция строго выпуклая.

Пример 22.

Исследовать функцию на выпуклость .

Решение.

Найдем частные производные :

, следовательно, функция F строго выпуклая.

Задача выпуклого программирования.

Пусть дана функция и система ограничений:

, где

- выпуклые на некотором множестве М;

- либо выпукла, либо вогнута.

Задача выпуклого программирования состоит в отыскании такого решения системы ограничений, при котором целевая выпуклая функция достигает минимального значения или вогнутая максимального. (Условие не отрицательности переменных можно считать включенными в систему ограничений).

Линейное программирование является частным случаем вогнутого.

Выделение задач выпуклого программирования в специальный класс объясняется экстремальными свойствами выпуклой функции:

·  локальный минимум выпуклой функции (максимум - вогнутой) является одновременно глобальным;

·  выпуклая (вогнутая) функция достигает на замкнутом множестве глобального минимума (максимума).

Если целевая функция является строго выпуклой (вогнутой) и если область решений системы ограничений не пуста и ограничена, то задача выпуклого программирования имеет единственное решение.

Минимум выпуклой функции (максимум вогнутой) достигается внутри области решений, если там имеется стационарная точка, или на границе этой области, если внутри нет стационарной точки.

В общем случае множество оптимальных решений задач выпуклого программирования является выпуклым.

Производная по направлению и градиент.

производной функции по направлению l в точке Х называется предел: .

Направление задается вектором .

Если дифференцируема в точке Х, то она имеет в этой точке производную по любому направлению l, которая выражается через частные производные:

.

Абсолютная величина производной по направлению показывает скорость изменения функции в этом направлении, а знак производной показывает характер изменения функции ("+" - возрастание; "-" - убывание).

Градиентом функции называется вектор, проекциями которого на оси координат являются частные производные функции:

.

Своего максимального значения достигает тогда, когда направление l совпадает с направлением вектора градиента :

- максимальная скорость возрастания функции.

Таким образом, в точке Х направление градиента является направлением наибольшего возрастания функции, а длина вектора градиента равна наибольшей скорости возрастания функции в этой точке.[1]

Пример 23.

Найти наибольшую скорость возрастания функции в точке А(0;1;2) и определить характер изменения этой функции в точке А в направлении l=(1;-2;2).

Решение.

Найдем вектор градиент в точке А. Для этого найдем частные производные функции F:

В точке А вектор градиент равен , а его длина .

Получили направление максимально госта функции в точке А и наибольшая скорость возрастания .

Определим характер изменения функции в направлении l:

,

следовательно функция возрастает в точке А в направлении l.

Методы спуска.

Общая схема решения задач математического программирования методом спуска состоит в построении последовательности точек решений системы ограничений данной задачи по принципу: - любая точка области допустимых решений, а , где - некоторое направление (вектор), а - число (длина шага).

и выбираются так, чтобы обеспечить сходимость последовательности к точке (оптимальному решению).

В общем случае процесс построения последовательных приближений бесконечен. в этом случае приближенное значение . Иногда процесс может быть конечен и в задачах выпуклого программирования приводит к глобальному оптимуму.

Находя можно определить "выгодность" или "невыгодность" направления в смысле приближения к оптимуму.

Пример 24.

Точка принадлежит области допустимых решений.

Проверить, приближается ли функция к оптимуму по направлениям:

Решение.

Найдем частные производные целевой функции в точке :

Найдем длину вектора l и вектора t:

Найдем производную функции по направлению l:

.

Следовательно функция приближается к оптимуму в направлении l.

Градиентные методы.

Так как направление градиента целевой функции является направлением наискорейшего роста, то при отыскании максимума вогнутой (минимума выпуклой) функции в качестве направления спуска берется ():

.

Такие методы называются градиентными. Отличия между ними состоят в:

1.  выборе ;

2.  нахождении , если - граничная точка, а выводит за границу области допустимых решений.

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

выбирается так, что при нем достигала максимума. При этом считаются известными. функция одной переменной :

.

Вектор градиент в точке имеет вид .

Получим, что необходимое условие экстремума примет вид:

.

Или, если использовать формулу скалярного произведения векторов:

.

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

Замечание. Для различных шагов k значение будут различными.

Для упрощения написания обозначим .

Пример 25.

Решить задачу методом скорейшего градиентного спуска.

Решение.

Проверим функцию на вогнутость. Для этого введем функцию . Если будет выпукла, то - вогнута.

.

Найдем частные производные функции :

Найдем вторые частные производные функции :

.

Матрица вторых производных:

.

Главные миноры: , следовательно, функция выпуклая, а функция - вогнутая.

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

Найдем вектор градиент функции в обще виде:

.

Вектор градиент в точке равен .

Найдем следующую точку .

Вектор градиент в точке будет равен

Найдем из условия:

Получим:

Поскольку в точке нет направлений роста функции, следовательно, это точка максимума. - наибольшее значение функции.

Задания.

1.  Исследовать функцию на экстремум:

a. 

b. 

c. 

d. 

e. 

f. 

g. 

h. 

2.  Исследовать функции на условный экстремум:

a.  при

b.  при

c.  при

d.  при

e.  при

3.  Найти градиент функции:

a.  z=4-x2-y2 в точке М(1;2)

b.  в точке М(0;3)

c.  z=(x-y)2 в точке М(1;1)

d.  в точке М(1;1)

e.  u=x2+y2-z2 в точке М(1;-1;2)

f.  u=4-x2-y2+z2 в точке М(3;2;1)

g.  u=xyz в точке М(3;-1;2)

h.  в точке М(-1;2;0)

i.  u=x+ln(y2+z2) в точке М(2;1;1)

j.  в точке М(p/2;3p/2;3)

k.  в точке М(1;5;-2)

l.  в точке М(1;1;0)

m.  в точке М(1;1;0)

n.  u=ln(3-x2)+xy2z в точке М(1;3;2)

o.  u=x2y2z-ln(z-1) в точке М(1;1;2)

p.  u=ln(x2+y2) в точке М(1;-1;2)

q.  u=xy-x/z в точке М(-4;3;-1)

r.  в точке М(1;-3;4)

4.  Для функции найти общее выражение градиента; линию уровня, проходящую через точку А(4;1) и градиент в точке А, изобразить их на чертеже; производную по направлению l(-1;-1)

Динамическое программирование.

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

Впервые задача динамического программирования и принцип ее решения были предложены американским ученым Р Беллманом в 50-ые годы XX века.

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

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

Общая постановка задач динамического программирования.

Рассмотрим управляемый процесс. Например, распределение средств между предприятиями, использующими ресурсы в течении ряда лет.

В результате управления система (объект) S переходит из состояния в состояние .

Пусть управление можно разбить на n шагов, то есть решения принимаются последовательно на каждом шаге, а управление, переводящее систему S из в (), представляет собой совокупность n пошаговых управлений.

Пусть - управление на k-ом шаге и удовлетворяет некоторым ограничениям и в этом смысле называется допустимым. может быть числом, точкой, функцией, качественным признаком.

управление, переводящее систему S из .

состояние системы после к-ого шага управления.

Рисунок 3

 

- целевая функция, показатель эффективности рассматриваемой управляемой операции. Целевая функция зависит от начального состояния системы и управления Х.

Предположим:

1.  Состояние зависит только от предыдущего состояния и управления на предыдущем шаге и не зависит от предшествующих состояний и управлений. Это требование называется "отсутствие последствий". - уравнение состояний.

2.  Целевая функция является аддитивной от показателей эффективности на каждом шаге. Обозначим показатель эффективности к-ого шаге через:

Тогда задача динамического программирования (пошаговой оптимизации) формулируется так: определить такое допустимое управление Х, переводящее систему S из , при котором целевая функция принимает наибольшее (наименьшее) значение.

Особенности динамического программирования:

a.  Задача оптимизации интерпретируется как n-шаговый процесс управления.

b.  Целевая функция равна сумме целевых функций на каждом шаге.

c.  Выбор управления на k-ом шаге зависит от состояния системы к этому шагу, не влияет на предшествующие шаги (отсутствие обратной связи).

d.  Состояние после k-ого шага зависит только от предшествующего состояния и управления (нет последствий).

e.  На каждом шаге управление зависит от конечного числа управляющих переменных, а состояние от конечного числа параметров.

Вычислительная схема задач динамического программирования безразлична к способам задания функции и ограничений, связана с принципом оптимальности и использует рекуррентные соотношения.

Принцип оптимальности.

Принцип оптимальности (был предложен Беллманом в 1953 г.): каково бы ни было состояние системы S в результате какого либо числа шагов, на ближайшем шаге надо выбирать управление так, чтобы оно в совокупности с оптимальными управлениями на всех последующих шагах приводило к оптимальному выигрышу на всех оставшихся шагах, включая данный.

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

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

Уравнения Беллмана.

Функциональные уравнения Беллмана – это математическая формулировка принципа оптимальности Беллмана

Будем считать, что мы ищем максимум целевой функции.

На n-ом шаге , то есть выигрыш на n-ом шаге зависит только от управления на этом шаге.

На (n-1)-ом шаге

, то есть на (n-1)-ом шаге надо так подобрать управление , чтобы сумма выигрышей на (n-1) шаге и на n шаге была максимальна. И т. д.

На k-ом шаге то есть k-ом шаге надо так подобрать управление , чтобы сумма выигрышей на k-ом шаге и на n-k последующих шагах была максимальна.

Общая схема решения задач динамического программирования.

Определяем все состояния системы при переходе из начального состояния в конечное состояние . На каждом шаге целевые функции имеют вид: и определено уравнение состояния: .

Из уравнения Беллмана для по находим оптимальное управление на 1-ом шаге . По и определяем состояние системы после 1-ого шага: .

Из уравнения Беллмана для по находим оптимальное управление на 2-ом шаге . По и определяем состояние системы после 2-ого шага: . И так далее.

Условно этот процесс можно представить так:

Задача о распределении средств между предприятиями.

Задача: между 4-мя предприятиями распределяется 60 миллионов рублей. Прирост выпуска продукции на каждом предприятии зависит от выделенной суммы средств X. Значения прироста задаются в виде таблицы . Найти такой план распределения средств между предприятиями, при котором общий прирост выпуска продукции будет максимальным.

Средства Х, млн. руб.	Прирост выпуска продукции, млн. руб.
g1(x)	g2(x)	g3(x)	g4(x)
0	0	0	0	0
20	7	6	14	14
40	23	23	21	20
60	31	30	34	35

Решение: