Методы оптимизации: конспект лекций для информатики

Методические указания
Ф СО ПГУ 7.18.2/05
Министерство образования и науки Республики Казахстан
Павлодарский государственный университет им. С. Торайгырова
Кафедра информатики и информационных систем
Опорный конспект лекции
дисциплины «Методы оптимизации и исследование операции»
для специальностей 050602-Информатика,
050703 Информационные системы
Павлодар
Лист утверждения к
методическим указаниям
Форма
Ф СО ПГУ 7.18.1/05
УТВЕРЖДАЮ
Декан ФФМиИТ
_________ Тлеукенов С.К.
"___" __________200__г.
Составители: доцент Даутова А.З.,
преподаватель Оспанова Г.А.
Кафедра «Информатика и информационные системы»
Опорный конспект лекции
по дисциплине «Методы оптимизации и исследование операции»
для студентов специальностей 050602-Информатика,
050703 Информационные системы,
Рекомендована на заседании кафедры от “__28__”_августа__2008г.
Протокол № __1_
Заведующая кафедрой ___________ Ж.К.Нурбекова
Одобрена учебно-методическим советом факультета Физики, математики и
информационных
технологий “_1_”__сентября____2008г. Протокол
№_1__
Председатель УМС__________________________ А.З. Даутова
ВВЕДЕНИЕ
Понятие «оптимальный» прочно вошло в жизнь: если у
рассматриваемой задачи есть множество решений, то естественно
выбирается то из них, которое квалифицируется как лучшее. Математически
проблема оптимальности описывается множеством V и функцией J,
определенной на V со значением в R. Таким образом, речь идет о том, чтобы
найти решение и такое, что
uV
J(u) J(v) vV
(*)
V – множество возможных способов достижения определенной цели
или множество способов функционирования какой-нибудь системы (область
ограничения).
Функция J – критерий, который предопределяет ваш выбор из
множества возможных решений.
В задаче (*) надо выбрать решение u которое минимизирует значение
функции J на множестве V. Если заменить J на –J, то задача преобразуется в
задачу максимизации. На практике функцией J может быть стоимость,
выработка, прибыль, время и т.д.
Решение задачи (*) может не существовать, тогда ищут реализуемое
решение и, такое, чтобы J(u) было «достаточно близко» к inf J(v).
vV
Множество V описывается обычно с помощью уравнений и неравенств,
которые связывают различные параметры системы. Однако сложные
системы с трудом поддаются формализованному описанию, а полученные
модели – численному исследованию. В таком случае довольствуются
моделями, которые представляют собой упрощенное описание физической
реальности.
В общем случае невозможно получить аналитическое выражение для
оптимального решения поставленной задачи оптимизации. Поэтому задача
сводится к поиску численного приближенного решения, поиск же численных
методов тесно связан с возможностями вычислительных машин.
В этих методах основная идея заключается в том, что решение большой
задачи сводится к решению последовательности подзадач, которые обычно
содержат лишь одну переменную.
Многие практические задачи хозяйственной деятельности и ряд
важных вопросов экономической теории связаны с задачами определения
наилучшего, оптимального варианта решения. Таковы, например, задачи
выбора
оптимальной
производственной
программы
предприятия,
транспортные задачи рационального распределения грузопотоков. Для
решения задач такого рода в математической науке созданы и интенсивно
разрабатываются в настоящее время новые математические методы,
объединяемые под общим названием математического программирования.
Теория оптимизации является непосредственной математической базой для
постановки и исследования ряда практических и теоретических вопросов
математической науки.
В течение примерно двух последних десятилетий сформировалась
новая прикладная математическая дисциплина, известная под названием
теории оптимального управления, или математической теории оптимальных
процессов. Развитие этой дисциплины было вызвано потребностями одной из
важнейших областей технических наук - теории автоматического
регулирования. В самой общей постановке проблема регулирования
автоматическими устройствами сводится к выбору значений во времени
некоторых величин, называемых управляющими параметрами, подчиненных
ряду ограничений, при которых достигается экстремум некоторого
функционала.
Математический аппарат современной теории оптимального
управления включает методы вариационного исчисления, метод принципа
максимума и методы динамического программирования.
Динамическое программирование уже нашло немало интересных
приложений и при решении практических экономических задач, например
при создании моделей календарного планирования производства.
Математический аппарат, разработанный применительно к проблемам
микроэкономики, получил в настоящее время всеобщее признание. Без таких
концепции математической экономии, как производственные функции,
предельные значения, экстремумы - максимальные и минимальные значенияи другие, невозможно успешно построить экономико-математические
модели, имеющие своим назначением служить вспомогательным орудием
народнохозяйстенного планирования.
Но
решение
некоторых
отдельных
вопросов
применения
математических методов в микроэкономике нуждается в существенной
корректировке с экономической точки зрения. Это относится, в частности, к
теории личного потребления. Основное понятие в ней "функция полезности".
В дальнейшем эта функция получила различные экономические толкования.
Наиболее важная область её применения отностится к совокупностям
товаров, входящим в потребительский бюджет. И здесь целесообразно
вместо "полезность" применять более, определенный термин "уровень
потребления". Это будет сравнительная характеристика
в результате
фактического потребления той или иной совокупности товаров
составляющих его бюджет.
Формальная постановка задачи.
При
формальной
постановки
задачи
математического
программирования основными являются понятия "инструментальных"
переменных, допустимого множества и целевой функции.
Задача заключается в нахождении значений n переменных х1,х2,….хn,
которые называются здесь "инструментами". Переменные, записанные в виде
вектора-столбца
 x1 
 
x2
x=   =(x1,x2,..xn)
..
 
 xn 
 
(2.1.1)
они составляют вектор инструментальных переменных в n-мерном
евклидовом
пространстве Е n .
Если вектор инструментальных переменных х удовлетворяет
ограничениям задачи, он называется допустимым, а множество всех
допустимых векторов образует множество возможностей Х. Допустимое
множество является подмножеством Е n . Так как задача заключается в выборе
инструментальных переменных из допустимого множества, то в любой
нетривиальной задаче оно является непустым (т.е. система ограничений
совместна) и содержит, по крайней мере две различные точки.
Целевая функция- это краткое математическое изложение цели данной
задачи. Обычно она представляет собой действительную непрерывно
дифференцируемую функцию вектора инструментальных переменных.
F=F(x)=F(x1,x2,..,xn).
(2.1.2)
Общая задача математического программирования состоит в выборе
вектора инструментальных переменных
из множества возможностей,
максимизирующего значение целевой функции:
max F(x) при условии, что x  X
x
где Х-подмножество n-мерного евклидового пространства.
Учитывая, что максимизация F(x) эквивалентна максимизации, а+bF(x),
b>0, или минимизация a+bF(x), b<0, можно сделать вывод, что введение
дополнительного слагаемого или положительного множителя в целевую
функцию не изменяет задачи. В то время как отрицательный множитель
может быть использован для преобразования задачи максимизации в задачу
минимизации и наоборот.
Примеры линейных моделей:
Задача о диете.
Рассмотрим задачу составление наиболее экономного (т.е. наиболее
дешевого рациона) питания, удовлетворяющее определенным медицинским
требованиям (в армии, санаториях и т.д.)
Предполагаем, что известен перечень доступных продуктов из nнаименований (хлеб, сахар, масло, молоко и т.д.), которые обозначают
буквами F1, F2, ...
Рассматриваются характеристики продуктов такие, как витамины,
минеральные вещества, жиры, белки, калорийность и т.д. – N1, N2, ... , Nm.
Пусть для каждого продукта Fi (i=1,2,...,n) известна его медицинская
характеристика, т.е. количественное содержание в одной единице (кг, гр)
продукта указанных компонент.
То можно составить таблицу-справочник, содержащий характеристику
продуктов.
F1 F2 . . . Fn
N1 a11 a12 . . . a1n
N2 a21 a22 . . . a2n
.................
Nm am1 am2 . . . amn
A=
a11 . . . . . a1n
...........
am1 . . . . .amn
Допустим, что составили рацион х=(х1, . . ., хm) на некоторый срок
(месяц), т.е. планируем каждому человеку на месяц х1 единиц (кг, гр)
продукта F1, х2 – F2 и т.д. Нетрудно вычислить, какое количество витаминов,
жиров и т.д. получит человек.
Именно компонента N1 присутствует в этом рационе в общем
количестве:
а11х1+а12х2+ . . . +а1nхn, соответственно и для других.
Допустим, что имеются вполне определенные медицинские
требования, касающиеся необходимого человеку количества каждой из
компонент Ni (i=1, ..., m). Например, количество витаминов С не должна быть
меньше заданного (цинга). Т.е. координаты xi вектора х должны
удовлетворять следующей системе ограничений.
а11х1+а12х2+ . . . +а1nхn b1
......................
(1) (x10, ..., xm0)
аm1х1+аm2х2+ . . . +аmnхn bm
Любой рацион должен удовлетворять условиям (1), но таких рационов
множество.
Пусть цены на F1,..., Fn равны соответственно С1,...,Сn. Следовательно,
стоимость всего рациона x=(x1,...,xn) может быть записана
с1х1+...+ спхп
(1.3)
Окончательная формулировка задачи о диете такова: среди всех
векторов x=(x1,...,xn), удовлетворяющих ограничениям (1) выбран такой, для
которых выражение (1.3) принимает минимальное значение.
Выпуклое программирование.
Выпуклым программированием называется раздел математики, в котором
исследуются задачи минимизации
f ( x )min , x  X
выпуклых
функций
на
(1)
выпуклых
множествах
X
конечномерного
пространства Rn.
Исследование задач выпуклого программирования привело к созданию
выпуклого анализа, в котором детально изучаются свойства выпуклых
функций и множеств.
x
2
При формулировке основной задачи выпуклого программирования (1)
принято множество X задавать в форме = X x; g( x )  0, x  Q, где
Q
и
компоненты m-вектор функции g( x ) - выпуклые множество и функции.
Определение:
Множество X
из n-мерного евклидова пространства Rn
называется выпуклым, если наряду с  двумя своими точками содержит и
весь отрезок, соединяющий их (рис.1) . Другими словами, если x 1, x 2 Х ,то
x   =  x 1+(1-  ) x 2  X при всех   [0,1]
x
1
x3
x
x (
)
R2
x2
x2
x1
x
1
Рис 1.
Определение:
множестве
Функция f ( x ), определенная и конечная на выпуклом
X , называется выпуклой, если для  x 1 и x 2  X при всех
  [0,1] выполняется неравенство
f ( x 1  +(1-  ) x 2)   f ( x 1)+(1-  ) f ( x 2)
Пример: Негладкая функция f ( x )= x , x  R1 , т.к.
  x 1+(1-  ) x 2    x 1+(1-  )  x 2  при  x 1, x 2  R1 ,   [0,1]
Определение:
Если
функция
f ( x ),
x  Rn
,
дважды
непрерывно
дифференцируема f( x )  с2 , то она выпукла тогда и только тогда когда
матрица
 2 f ( x)
0
x 2
x  Rn, её вторых производных неотрицательна.
Критерий Сильвестра: 1) для положительности матрицы А, чтобы все её
последовательные
главные
миноры
Ds
были
положительны:
Ds= deta ij , i  1, S , 0, s  1, n , 2) для неотрицательности матрицы А необходимо
и достаточном , чтобы все её главные миноры были неотрицательными
 i ,...,
det A 1
 j1 ,...,
is 
0
j s 
1  i1<i2<…<is  n, s= 1, n
Свойства выпуклых множеств:
Пересечение  числа выпуклых множеств-выпуклое множество. Выпуклая
k
k
i 1
i 1
комбинация (   i  i ,  i  0, i  1, k ,   i  1 )  элементов x i , i= 1, k выпуклого
множества принадлежит этому множеству.
Свойства выпуклой функции :
Множество уровня x : f ( x )  c выпуклой функции f ( x ) , x  Rn или пусто,
или выпукло.
Если fi( x ), x  Rn , i= 1, k -выпуклые функции, то и
f ( x) =  i f i ( x)
i  0
i= 1, k , f (x)=max f i ( x ) - выпуклые функции.
Выпуклая функция f ( x ) , x  Rn- непрерывна в каждой точке x .
В каждой точке x  Rn выпуклая функция f ( x ) имеет производную по 
направлению L Rn
f ( x )
f ( x  Lt )  f ( x )
 Lim
L
t
t 0
Вектор с  Rn называется субградиентом выпуклой функции f ( x ) , х  Rn в
точке х, если для всех выполняется неравенство:
f (x ) - f ( x )  с(х-х).
Функция f (x ) называется вогнутой, если функция- f () выпукла.
Теорема: Пусть функция f ( x, y ) определена и непрерывна на выпуклых
компактных множествах x  X  Rn , y  Y  Rm.Если функция
f ( x, y ) при
которой y  Y выпукла по, а при каждом х  Х вогнута по y Y, то она имеет
седловую точку  x 0,y0, x 0  X , y0  Y
f ( x 0 , y )  f ( x 0 , y 0 )  f ( x, y 0 ) и для неё справедлива теорема о минимаксе.
min max f ( x , y )  max min f ( x , y )
x X
yY
Функция
yY
f (x ) ,
x X
называется
x  Rn
x 1 , x 2  Rn , x 1  x 2 ,
  0,1
строго
выпуклой,
выполняется
если
строгое
для

неравенство
f (x 1  (1   ) x 2 )  f ( x 1 )  (1   ) f ( x 2 )
Функцию f (x ) , x  Rn
 x 1 , x 2  Rn , x 1  x 2
f(
называют
и
некоторой
сильно
выпуклой,
если
для
 0
выполняется
неравенство
x1 x 2
f ( x1 ) f ( x 2 )

)

  x1  x 2
2
2
2
2
Теорема Куна-Таккера.
Теорема Куна-Таккера в выпуклом программировании называется основной
результат -критерии оптимальности, сформулированный
в терминах
седловой точки функции Лагранжа.
1) Седловая точка функции Лагранжа и решение основной задачи выпуклого
программирования.
ОЗВП: f ( x  min) g( x )  0
x Q
Q - выпуклое множество, f (x ) и компоненты g 1 ( x ),..., g m ( x ) ,
m -вектор функции g( x ) -выпуклые функции.
Каждый
n вектор x удовлетворяет ограничениям задачи(1), называется,
следуя задачи Л.П., планом (допустимыми точкой, вектором, решением).
Решение x0 задачи (1) f ( x0 )  min f ( x ) g( x )  0
x Q
есть оптимальный
план.
Если целевая функция f (x ) - строго выпуклая, то оптимальный план задачи
(1) единственный.
Определение: (2) F ( x,  )  f ( x )   g( x ), x  Q,   Rm ,   0 -функция Лагранжа
Определение: Говорят, что x ,  ,   0 , x  Q - седловая точка функции
Лагранжа (2), если для всех x  Q,   0 выполняется неравенство
F ( x  ,  )  F ( x  ,  )  F ( x ,  )
(3)
Теорема: Если ( x , y ), x  Q ,   0 - седловой точки функции Лагранжа(2),
то
x - оптимальный план задачи (1) и выполняется условие дополняющей
нежесткости
g ( x ) =0
(4)
Определение:
Говорят,
что
множество
планов
(ограничения)
ОЗВП
регулярно (удовлетворяет условие Слейтера), если на некотором плане x
выполняется неравенство g( x )  0 (5)
Теорема ( Куна -Таккера): Для существования оптимального плана x0 ОЗВП
с регулярным множеством планов необходимо и достаточно существование
такого неотрицательного вектора 0  0 ,что пара ( x0 , 0 )- седловая точка
функции Лагранжа и выполняется условие дополняющей нежесткости.
g ( x 0 )0  0 (6)
Метод золотого сечения.
Минимизация функции одной переменной имеет самостоятельный интерес.
От правильной организации одномерного поиска существенно зависит успех
решения всей задачи. Пусть функция f(x), определенная на [a,b]. Функция
f(x) называется унимодальной, если существует единственная точка х *, в
которой функция f(x) принимает экстремальное значение. Унимодальная
функция не может быть гладкой или даже непрерывной. Из определения
унимодальности следует, что если x1  x2  x * , то f(x1) >f(x2). Аналогично,
если x *  x1  x2 , то f(x1) <f(x2). Задача состоит в построении такой
последовательности {xk} , чтобы при некотором i минимальное значение
функции достигалось на интервале
xi 1  x *  xi , которое называется
интервалом неопределенности. Алгоритм выбора абцисс {xk} называется
стратегией поиска. При заданном количестве вычислении функции
оптимальной стратегией является та, которая ведет к наименьшему
интервалу неопределенности.
Алгоритм поиска.
Начальный отрезок [a,b] делим точками x1 и x2 и вычисляем значение f(x1),
f(x2), т.к. f(x1) <f(x2), то минимум располагается или в [a,x1] или в [x1,x2],
поэтому [x2,b] –отбрасываем, тем самым сужаем интервал неопределенности.
Далее рассмотрим [a1,b1], где a1=а, b1=x2, выбираем две внутренние точки, но
x1 осталась из предыдущего шага, достаточно выбрать х3. Поскольку
f(x3)>f(x1), то минимум находится на [x3,b]. Обозначим этот отрезок [a2,b2],
снова выбираем одну точку и повторяем процедуру сужения. Продолжаем до
тех пор , пока длина очередного [an,bn] не станет меньше заданного .
Золотое сечение выбирается следующим образом. Отношения длины
большего отрезка к длине всего интервала равнялось отношению длины
меньшего
отрезка
к
длине
большего.
l1 l 2
l
1 5
  l12  l1l 2  2 
 0.6180339  l1  0.618l , l 2  0.382l
l l1
l1
2
Золотое сечение [a,b] производят две симметрично расположенные точки
x1  a  (1   )(b  a)
x2  a   (b  a), где  0,618
, где x1 производит золотое сечение [a,x2], a
x2
производит золотое сечение [x1,b].
Метод дихотомии. ( Метод половинчатого деления)
Вычислительный алгоритм
1) Проверка условия b  a  2 , -заданная погрешность вычисления xm .
Если условие выполняется, то идём к 6), иначе 2).
2) a, b
делим пополам и вычисляем 2 абсциссы, симметрично
расположенные относительно точек
a b
a b
ba
x2 
x
: x1 
2
3) Вычисляем F ( x 1 ) и F ( x 2 )
2
2
4) Проверка условия F ( x 1 )  F ( x 2 ) . Если оно выполняется то, b  x 2 и идём
к) 1), иначе к 5).
5) a  x 1 и идём к 1).
6) Вывод на печать x m  (a  b) / 2 и вычисляем F ( x m ) .
Задание. Выписать 1 и 2, сравнить данные. Сделать блок-схему.
Метод квадратичной интерполяции-экстраполяции.
Этот метод заключается в замене F (x ) в промежутке x 1  h , где x 1 начальное приближение квадратической параболы, экстремум которой
вычисляется аналитически. После нахождения экстремума x m можно задать
x 1  x~m и повторить поиск.
Т.О., с помощью итерационной процедуры значение x m уточняется до
получения его с заданной погрешностью  .
Алгоритм:
1) Задаём начальное приближение x1
аргумента F (x ) :
x0  x1  h
x 2  x1  h , где
для
x m и вычисляем два смежных
h -полуинтервал интерполяции
2) вычисляем 3 значение F (x ) :
F ( x0 )  F0 , F ( x1 )  F1 и
F ( x 2 )  F2
3)Находим коэффициенты
F
F
F
1
c  02  12  22  2 F0  2 F1  F2 
2h 2h 2h
2h
 F0 ( 2 x 1  h)  4 F1 x 1  F2 ( 2 x 1  h)
2h 2
2
Параболы y( x )  x  bx  c , проходящей через выбранные три угла
F (x ) , и по ним вычисляем аналитически положение
интерполяции
экстремума.
b
b 1 F0 ( 2 x 1  h)  4 F1 x 1  F2 ( 2 x 1  h)
x~ m   
2c 2
F0  2 F1  F2
~
4) Проверяем условие ( x m  x 1 )   , если оно не выполняется, то x 1  x M и
идём к 1).
~
Если выполняется условие, то x m -найдено и вычисляем F ( x m ) и завершаем
счёт.
Многомерная оптимизация заключается в поиске экстремумов функции
многих переменных F ( x 1 , x 2 ,..., x n ) .
Из всего разнообразия методов многомерной оптимизации ограничимся
рассмотрением 3-х относительно простых методов поиска минимума
F ( x 1 , x 2 ,..., x n ) .
~
Метод покоординатного спуска
Этот метод заключается в поочерёдном поиске минимума по координате x 1 ,
затем x2 и т.д. Поиск ведётся с одинаковым шагом, который уменьшается
~
~
~
после нахождения всех значений x1m , x2 m , ..., xnm . Таким образом, алгоритм
реализации этого метода поразрядного приближения и лишь дополняется
x 1 ,..., x n , внутри которой оценивается
циклом задания переменных
погрешность нахождения x im
для каждой переменной.
1)Выбор нулевого приближения.
Фиксируем значение двух координат y  y0 ; z  z 0 , то функция зависит только
от
x , обозначим её через f 1 ( x )  ( x, y0 , z0 ) . Используя методы для
одномерной оптимизации находим минимум функции f 1 ( x ) и обозначим
через x1 . Мы сделали шаг из точки ( x0 , y0 , z 0 ) в точку ( x 1 , y0 , z 0 ) по
направлению, параллельному оси
x на этом шаге значение функции
уменьшилось.
Затем из новой точки сделаем спуск по направлению, параллельному оси y ,
т.е. рассмотрим, f 2 ( y )  ( x 1 , y1 , z 0 ) находим её минимум и обозначаем через
y1 .
Второй шаг приводит к точке ( x 1 , y 1 , z 0 ) .
Затем третий шаг - спуск параллельно оси z и находим min f ( z )  ( x1 , y1 , z )
Переход к точке ( x 1 , y1 , z 1 ) завершает цикл спусков.
Циклы повторяются. На конечном спуске функция не возрастает, и значение
функции снизу ограничены значения в   ( x, y, z)
Метод парабол.
Если - дифференцируема, то x корень уравнения f (x) =0 является точкой
min , если f ( x )  0 и точка max , если f (x )  0.
При нахождении нулей первой производной используем метод линеаризации,
что приводит к итерационному процессу
x s1  x s 
f ( x s )
f ( x s )
(*)
В простейших задачах нулевые значения можно выбрать графически.
f (x ) в точках x s разложим в ряд Тейлора и ограничимся тремя членами,
т.е. аппроксимирование кривую параболой.
1
f ( x )  f ( x s )  ( x  x s ) f ( x s )  ( x  x s ) 2 f ( x s )
2
min этой параболы достигается в точке, определяемой формулой (*)
если f (x ) =0, то сходимость медленная, то
f ( x x  h)  f ( x x  h)
h
x s1  x s 
2 f ( x s  h)  2 f ( x s )  f ( x s  h)
h  0,01
Линейное программирование.
Стандартная задача линейного программирования.
max (c1x1+...+cnxn )
a11x1+...+ a1nxn ≤ b1
.............................
am1x1+...+ amnxn ≤ bm
(x10, ..., xn0)
или матричная форма записи:
max (c,x)
Ах≤b, x≥0, где x=(x1,...,xn), c=(c1,...,cn), b=(b1,...,bn).
A=(aij) – матрица коэффициентов.
Вектор С называют вектором коэффициентов линейной формы, b –
вектор ограничений.
Стандартная задача важна ввиду наличия большого числа прикладных
моделей, сводящихся наиболее естественным образом к этому классу задач
линейного программирования.
Каноническая задача линейного программирования.
max (c1x1+...+cnxn )
a11x1+...+ a1nxn = b1
.............................
am1x1+...+ amnxn = bm
(x10, ..., xn0)
или матричная форма записи:
max (c,x)
Ах=b, x≥0
Основные вычислительные схемы (симплекс-метод и его модификации)
решения задач ЛП разработаны именно для канонической задачи.
Общая задача ЛП
В этой задаче часть ограничений носит характер неравенств, а часть является
уравнениями. Кроме того, не на все переменные положено условие не отрицательности.
max (c1x1+...+cnxn )
a11x1+...+ a1nxn ≤ b1
.............................
aк1x1+...+ aкnxn ≤ bк
aк+1x1+...+ aк+1nxn = bк+1
.............................
am1x1+...+ amnxn= bm
(x10, ..., xr0)
здесь k m, r n.
Ясно, что стандартная задача получается как частный случай общей при k=m,
r=n, каноническая – при k=0, r=n.
Линейная форма ‹cx›=c1x1+...+cnxn – подлежащая максимизации (или
минимизации) называется целевой функцией. Вектор x=(x1,...,xn), удовлетворяющий
всем ограничениям задачи ЛП, называется допустимым вектором или планом. Задачи
ЛП, для которых существуют допустимые вектора, называются допустимой задачей.
Допустимый вектор х*, доставляющий наибольшее значение целевой функции по
сравнению с любым другим допустимым вектором х, т.е. ‹с,х*›≥‹с,х› называется
решением задачи или оптимальным планом. Максимальное значение d=‹с,х*›
целевой функции называется значением задачи.
Квадратичное программирование.
Задача выпуклого квадратичного программирования состоит в
минимизации многочлена второго порядка при наличии конечного числа
ограничении на неизвестные. Предполагается, что квадратичная форма,
входящая в минимизирующую функцию, положительно полуопределена, что
обеспечивает выпуклость этой функции. Пусть квадратичная форма положительна определена.
Решим задачу квадратичного программирования в следующей форме:
f (x) 
n
1 n n
  c x x   d x  min
2 j1 k 1 jk j k j1 j j
n
 a x  bi
j1 ij j
i  1, m
или в матричной форме
f (x) 
1
2
( x , cx )  (d, x )  min
(1)
Ax  b
где c  (c jk ) - симметричная положительно определенная nxn матрица
m*n матрица
A  (a )
ij
d-вектор размерности n
b- вектор размерности m
Функция Лагранжа в нашем случае имеет вид:
L( x ,  ) 
1
2
( x , cx )  (d , x )  ( , b  Ax )
(2)
при этом седловую точку нужно искать при  =0 и свободном x . Поэтому
признак оптимальности


L( x  ,  )  L( x  ,  )  L( x ,  ) приводит к условию


L( x ,  ) x  x  0

x
T 
cx   d  A   0
или
(3)
Левое же неравенство признака оптимальности сводится к
допустимости x  и выполнению условия дополнительности, что означает,
что Ax   b
(4)

 ( b  ( Ax  ) )  0
i i
i
i  1, m
(5)
Кроме этого множители Лагранжа должны быть неотрицательны.

 0
i  1, m
(6)
i
Таким образом, если найдем пару ( x  ,  ), удовлетворяет условию (3)-
(6),то x  будет решением задачи (1), а  - решением соответствующей
двойственной задачи.
Метод: Многогранное множество, описываемое системой ограничении
задачи (1), разбивается на грани различной размерности (включая
внутренность - грань максимальной размерности). Конечная грань состоит из
допустимых точек, удовлетворяет некоторой системе уравнений вида:
AI xbI (7)
где A I -матрица, составленная из строк матрицы А с номерами
i  I  {i1 , i 2 ,.., i k } ,
т.е. A i  {( A) i , i  I} .
Аналогично составлен столбец b. Уменьшив, если нужно, множество I,
можно считать строки матрицы A i линейно независимыми. Наличие граней,
которых описываются линейной системой (7) с зависимыми уравнениями,
мы будем считать вырождением, и конечность метода в этом случае
обосновываться не будет.
Так как искомая точка x  принадлежит (относительной) внутренности
некоторой грани, то она должна доставлять минимум нашей квадратичной
функции на всем множестве решения системы (7).
Поступим следующим образом, будем
перебирать различные
подсистемы (7), находить на множестве их решений минимум нашей
квадратичной функции и проверять, удовлетворяет ли этот минимум
ограничениям и признаку оптимальности. Перебор множества I должен быть
направленным, чтобы избежать полного перебора всех граней (это сделало
бы метод нереализуемым).
Намеченная схема корректна лишь для случая положительноопределенной матрицы C , т.к. иначе для некоторых множеств I минимум
может и не достигать.
Формальное описание метода: Пусть имеется допустимая точка x и
выделено множество I  {i1 ,..., i l } , для которой строки матрицы A i линейно
независимы, а x удовлетворяет системе (7).
Возможны следующие случаи:
А) Точка x доставляет минимум функций f при ограничениях (7).
Согласно классическому признаку Лагранжа существуют множители
 I  { I , i  I} , для которых

x
f (x)   (b  A x)xx  0
I
i
I
или
T
cx  d  A I  I  0
(8)
В силу независимости строк матрицы A i равенством (8) вектор  I
определяется однозначно.
Если найденные значения  I неотрицательны, то определив  I =0 при

i  I , найдём, что при x   x и    выполнены все соотношения (3)-(6), так
что решение найдено.
Если же при некотором i k  I оказалось, что  i k <0, то этот индекс из
множества I удаляется и для той же точки x мы получаем некоторое
множество индексов I  {i 1 ,..., i k 1 ,..., i k  1 ,..., i k } , т.е. переходим к нашей грани,
размерность которой на единицу больше исходной.
В) Функция f достигает минимума на множестве решений системы (7)
в точке x 0  x , то попытаемся сдвинуться в точку x0 или, если помешают
ограничения задачи (1), как можно ближе к x0 .
Алгоритмически это так, положим z  x 0  x
n
g  ( Az)    a z i  I
i
i
j1 ij j
n
  (A x )  b   a x j  b
i
i
i i1 ij
i
определив
 0 по формуле
(9)
iI
 0  min{
(10)
i
; g i  0}
gi
(11)
положим   min{ 0 ,1}
при  =1, то сместились мы в точку x 0 и множество I в дальнейшем
сохраним, если же   1 , то номер i  , на котором реализован минимум (11),
мы включим в множество I , т.е. перейдём к нашему множеству индексов
I  {i1 , i 2 ,..., i l , i} .
В обоих случаях точка x заменяется на точку x  z
Для нахождения точки x 0 нужно решить систему
T
(12)
cx  d  AI i  0
AI x  bI
которая в силу положительной определенности матрицы С и линейной
независимости строк матрицы A i имеет неособенную матрицу.
Метод решения в целом состоит из последовательности шагов
перечисленных двух типов. Поскольку на шаге В) число элементов в
множестве I возрастает, то между двумя соседними шагами типа А) может
располагаться лишь конечное число шагов типа В).
С другой стороны, для конечного шага типа А) значение функции f в
точке x однозначно определяется множеством I , и если окажется, что от
одного шага к другому функция f строго убывает, то одно и то же множество
I на шагах типа А) не может встретиться дважды, и окажется конечным.
Пусть выполняется следующее условие невырожденности: через
точку min функции f на множестве решений конечной системы (7) не
проходит граничных гиперплоскостей - ограничении с номерами i  I . В этом
случае вслед за конечным шагом типа А) должен следовать шаг типа В) с
  0 (поскольку все  i  0 при i  I ) и значение функции f на этом шаге
строго убывает (фактически смещаемся из точки x ). Так как на остальных
шагах значение функции f не возрастает, то конечность метода обеспечена.
1
2
3
4
1
2
3
4
Пример: min{ ( x 1  ) 2  ( x 2  ) 2 : x 1  0; x 2  0; x 1  x 2  1}
Начав с точки (0,0), что соответствует I  {1,2} и системе
x1  0
x2  0
(13)
мы совершаем
шаг типа А), т.к. наша грань состоит из i -той точки и в точке (0,0)
тривиально достигается минимум функции f . Так как в нашем случае
 3
 
d   4
  3 
 4
 0
b i   
 0
1 0

С= 
0 1
1 0

A i  
0
1


3
4
то из (8), находим, что 1   2   , так что оба индекса в I можно взять в
качестве i k . Пусть i k =1 и переход к следующему шагу с x =(0,0) и I  {2} .
Теперь система (7) будет состоять из уравнения x 2  0 и множество её
решений будет совпадать с осью абсцисс. Минимум функции f достигается
в точке (3/4, 0), удовлетворяет системе ограничений. Поэтому в результате
шага типа В) мы сместимся в эту точку, сохранив
I  {2} . В результате
следующим снова оказывается шаг типа А), причём система (8) принимает
вид
3 3
3
 0
0   2  0
4
4 4
3
отсюда  2   и следует положить i k  2
4
3
К следующему шагу переходим с x   и I  . В соответствии с этим
4
f нужно искать на всей плоскости и поэтому
минимум функции
x 0  (3/4,3/4) . Однако точка x0 не удовлетворяет третьему ограничению.
Поэтому двигаясь по направлению к ней, определим z=(0,3/4) и при  =1/3
перейдём к точке x  (3/4,1/4) и множеству I  {3} .
Снова должен совершить шаг типа В), поскольку точка min
x0 =(1/2,1/2) на множестве решения уравнения x 2  x 2  1 не совпадает с x .
Поскольку, однако, эта точка является допустимой, то окажется, что  =1 и
мы получим решение задачи (1/2,1/2) .
X2
1
3/4
1/2
X1
1/4
(0,0)
1/2
3/4
1
Численные методы для задачи выпуклого программирования:
1) Метод условного градиента.
2) Метод проекции градиента.
3) Метод возможного направления.
Динамическое программирование.
В последующих двух параграфах рассматриваются задачи оптимального управления.
Любая задача оптимального управления в соответствии с принятой математической
моделью задается уравнениями состояния и предельными условиями, описывающими
поведение объекта. При этом всегда в уравнениях задачи можно выделить группу
зависимых переменных, описывающими состояние объекта и группу управляющих
функций, которые доступны непосредственному изменению извне и имеют значения,
принадлежащие заданному множеству допустимых управлений. Задача оптимального
управления состоит в том, что требуется из множества допустимых управлений
выбрать такие, которые придают заданному функционалу (зависящему в общем случае
от решения уравнений и управлений) наименьшее возможное значение.
Будем рассматривать задачи оптимального управления на примере
управляемого объекта, поведение которого описывается системой
обыкновенных дифференциальных уравнений:
d
 f (, u ),0  t  T,
dt
(5.1)
 (0) = 0 ,
где
 = {1 , …,n}, f = {f1 , …,fn}, u = {u1 , …,um}.
Допустимыми управлениями будем считать произвольные кусочнонепрерывные измеримые функции u = u(t), принимающие значения из
замкнутой области U Em.
В классе допустимых управлений требуется найти такое управление
u(t) и соответствующее ему решение (t) задачи (5.1), чтобы функционал
T
J[u]=  f 0 (, u )dt = min
0
uU
(5.2)
При этом предполагается, что каждое допустимое управление
определяет единственное решение задачи (5.1).
В основе метода динамического программирования лежит принцип
оптимальности Р. Беллмана, который может быть сформулирован
следующим образом.
Оптимальное управление в любой момент времени не зависит от
предыстории системы и определяется только целью управления и состоянием
системы в этот момент времени.
Если ввести обозначение
T
Q(, t)= min  f 0 (, t )d ,
(5.3)
uU0
То из принципа оптимальности имеем
T
t  t

Q((t), t)= min   f 0 (, u)d  min  f 0 (, u )d ,

u  t
u t  t
(5.4)
Второе слагаемое в скобках, по определению, есть
t  t
Q(  , t  t ) , где    f (, u )d .
t
Предполагая, что возможно разложение обоих членов в скобках по формуле
Тейлора и устремляя затем ∆t→0, получим из (5.4) уравнение в частных
производных (уравнение Беллмана):

Q
Q 

 min f 0 (, u )  (f (, u ), )
t
t 

(5.6)
Q(,T)=0.
Пусть минимум в правой части (5.6) достигается лишь в единственной точке
u*U, тогда u*есть функция от  и
u*= u*( ,
Q
).
t
Q
:
t
(5.7)
Подставляя эту функцию в уравнение (5.6) будем иметь нелинейную систему
уравнений

Q
Q
Q Q
 f 0 (, u * (, ))  (f (, u * (, ), )
t

 
(5.8)
Если считать u* некоторой функцией , t, то система (5.8) будет
гиперболической системой уравнений, характеристики которой направлены
от t=0 к t=Т. Строгое обоснование метода динамического программирования,
применительны к непрерывным задачам оптимального управления, было
дано В.Г. Болтянским, получившим необходимое и достаточное условие
оптимальности в терминах Q(, t).
В основе метода динамического программирования лежит идея погружения
данной конкретной задачи в семейство более простых задач. Нагляднее всего
это можно проиллюстрировать при выводе уравнений динамического
программирования для процессов, описываемых системой разностных
уравнений:
(5.9)
i 1  g(i , u i ) i=0,1,….,N-1
Здесь i Еn – n-мерный вектор состояния, uiЕm – m-мерный вектор
управления.
Разностное уравнение (5.9) могут возникать из физического описания
процесса, так и при дискретизации системы (5.1). На решениях системы
требуется минимизировать функционал вида
N 1
J[u]=  f 0 (i , u i ) 
i 0
(5.10)
min
u 0 ,, u N 1 
Из постановки задачи видно, что оптимальное значение функционала, если
решение задачи (5.9), (5.10) существует, зависит от начального состояния 0
и числа шагов N. Обозначив это оптимальное значение через Q N (0 ) ,
запишем задачу минимизации следующим образом:
N 1


Q N (0 )  min min f 0 (0 , u 0 )   f 0 (i , u i ) . (5.11)
i 1

u 0 u1 ,, u N 1  
Поскольку в силу структуры системы (5.9) изменения (u1,…,uN-1) не влияют
на φ0 и выбор u0, то (5.11) можно переписать следующим образом:
N 1


Q N (0 )  min f 0 (0 , u 0 )  min  f 0 (i , u i )
u 1 ,, u N 1  i 1

u0 
(5.12)
По определению второй член в фигурных скобках есть Q N 1 (1 ) и мы
получаем
Q N (0 )  min f 0 (0 , u 0 )  Q N 1 (1 )
u0
(5.13)
Рассуждая аналогичным образом, получаем следующие реккурентные
соотношения:
0 – задано,

Q N  j ( j )  min f 0 ( j , u j )  Q N  j1 ( j1 )
uj  U
j  0,, N  2  j1  g ( j , u j ),
Q1 ( N 1 )  min f 0 ( N 1 , u N 1 )
u N  1 U
N 1  g(N  2 , u N  2 )

(5.14)
(5.15)
Из системы (5.14), (5.15) следует, что, считая известной N1 и решая
относительно простую задачу минимизации функции m переменных, то
можем из (5.14) последовательно найти u N  2 ,..., u 0 и QN (0 )
Но поскольку система (9) определяет последовательно 1, 2,…, N-1 ,
то на самом деле получается типичная для оптимального управления
двухточечная краевая задача. Уравнения (14)-(15), дающие необходимые и
достаточные условия оптимальности управления (u1, u2,…, uN-1 ), являются
следствиями структуры системы (9) (при известных j, uj ), решение (9) не
зависит от j-1, uj-1,…(так называемые марковские системы) и аддитивности
функционала (10).
Рассмотрим на простом примере использование динамического
программирования.
Процесс
описывается
одним
уравнением
  u (0)   0 , u  1
(16)
T
И
требуется
минимизировать
функционал
Ju     2 dt  min .
0
Уравнение
Беллмана
Q
Q 


 min  2  u
u 1 
t
t 
(16)
запишется
следующим
u
образом
(17)
Поскольку линейная функция достигает минимума на границе отрезка,
Q
то u  sign ( )
(18)

Дискретизируем задачу (16) следующим образом (T=5, N=5, τ=T/N=1):
 i 1   i  u i , i  0,1,..., N  1,
N 1
u i  1 J    i2 
min
i 0
u 0 ,..., u N 1
Выражение
для
Q1(φΝ-1)
2
2
*
Q1 ( 4 )  min  4   4 , u 4  любое , u *4  1.
имеет
(19)
вид
u 4 1
Введение в теорию игр
Жить в обществе и быть свободным от общества нельзя! Живя в
обществе, мы неизбежно сталкиваемся с другими людьми, и интересы
различных людей практически никогда не совпадают между собой. В
обществе неизбежны столкновения интересов различных людей,
противоречия между этими интересами.
В художественной литературе этому столкновению интересов
уделялось не меньше внимания, чем любви и Богу. Это столкновение
политологии. Даже экономическая наука по большому счету изучает
столкновение интересов, так как конкуренция является именно таким
столкновением. Но лишь в 40-е годы двадцатого века это столкновение
интересов стало предметом математического исследования, прежде всего в
области экономики. Первая значительная книга
“Теория игр и экономическое поведение”.
Предмет оказался чрезвычайно сложным, даже для математики. И
сейчас, 60 лет спустя, успехи теории игр довольно ограничены. Тем не менее,
столкновение интересов практически в чистом виде. Организация тыла,
поиски подводных лодок, противовоздушная оборона, дуэль двух
и игр в настоящее время. В
экономике теория игр также находит своё применение.
Определение теории игр
От той теории, которая существует в настоящее время, не следует
ждать чудодейственных рецептов. Она не предписывает поведение, ведущее
к выигрышу. Она лишь указывает, чего может добиться игрок в наихудшей
для него ситуации и как он должен действовать, чтобы в этой наихудшей
ситуации добиться минимального проигрыша (или максимального
дело будущей теории игр.
1. Неформальное описание игры
Всякая игра предполагает следующее:
1. Наличие некоторого числа n участвующих в ней лиц (игроков).
Могут быть игры с одним игроком (пасьянс), двумя игроками игрок получает
доход (если
поведения других игроков.
Наиболее изученным классом игр являются так называемые игры с
нулевой суммой, когда в любой партии имеет место условие
, то
есть если кто-то выигрывает, то кто-то обязательно проигрывает. Это
особенно проявляется в играх двух лиц с нулевой суммой, когда
,
то есть
. В этом случае интересы игроков строго противоположны,
так как выигрыш одного игрока является одновременно проигрышем
другого. Такие игры называют антагонистическими.
Всякая игра состоит из партий, которые начинаются и заканчиваются,
после чего игрокам выплачиваются их выигрыши. В свою очередь, каждая
партия состоит из ходов, которые одновременно или последовательно
делают игроки. Описание игры как последовательности ходов носит название
позиционной формы игры. Теория игр в позиционной форме разработана
очень слабо и ещё ждёт своих Эйлеров и Гауссов.
матричная форма игры. В этом случае считается, что каждый игрок делает
всего лишь один ход, причем все ходы делаются одновременно. После этого
каждому игроку выплачивается выигрыш (или берётся проигрыш) в
зависимости от того, какие ходы были сделаны им и другими игроками.
Вообще говоря, игра в позиционной форме может быть сведена к игре в
матричной форме, однако для реальных игр это сведение настолько сложно,
что практически невыполнимо даже для современных ЭВМ. Однако вполне
возможно, что в будущем такое сведение будет иметь и практический смысл
2. Игры двух лиц с нулевой суммой
Игра двух лиц с нулевой суммой в матричной форме занимает
центральное место в современной теории игр, так как теория таких игр
разработана практически до конца.
Итак, пусть имеется два игрока. В распоряжении первого игрока
имеется всего n возможных ходов i=1,2,3,...,n; в распоряжении второго
игрока имеется m возможных ходов j=1,2,3,...,n. Эти возможные ходы
называются чистыми стратегиями игроков.
Оба игрока делают одновременно по одному ходу, после чего партия
первый игрок получает выигрыш, равный
второго игрока равен
. Очевидно, что выигрыш
.
Эти данные можно записать в виде матрицы
,
второго игрока. Эта матрица носит название платёжной матрицы игры.
Как же должны действовать игроки в такой ситуации? Какие ходы они
должны делать?
3. Игры с седловой точкой
Рассмотрим с этих позиций игру со следующей платёжной матрицей
.
Попробуем порассуждать с точки зрения
i=4
j=3).
Аналогично, при i=3 он в наихудшем случае получит 4 (при j=2), при
j=3 ) и, наконец, при i=5 он в наихудшем случае получит 0 (при
Стремясь сделать свой гарантированный выигрыш как можно больше,
первый игрок должен выбрать ход i=3, так как в этом случае он гарантирует
всего 5).
А теперь попробуем посмотреть на эту же матрицу с точки зрения
проигрыша.
Если он выберет ход j=1, то его максимальный проигрыш будет равен
18 (если первый игрок сделает ход i=1). Аналогично, при j=2 его
и, наконец, при j=4 его
максимальный проигрыш будет равен 25. Стремясь сделать свой
максимальный проигрыш как можно меньше, второй игрок должен выбрать
ход j=2, так как в этом случае его максимальный проигрыш, равный 4, самый
маленький.
Итак, мы пришли к выводу, что первый игрок должен ходить i=3, а
второй j=2. Допустим теперь, что второй игрок, как говорят, “открывает
карты” и заявляет первому игроку: “Я буду делать ход j=2”. Есть ли первому
игроку необходимость менять свой ход? Нет, так как в этом случае его
наилучший ход всё равно i=3.
Аналогично, если первый игрок заявит второму, что он будет ходить
i=3, то второму игроку также нет смысла менять свой ход, так как
наилучшим ответом будет всё равно j=2. Пара i=3, j=2 является, как говорят,
уравновешенной парой, так как “открытие карт” игроками не даёт поводов
противнику менять свою стратегию. Как говорят, пара i=3, j=2 есть решение
игры, а величина выигрыша при этом первого игрока (и одновременно
цена игры.
Оформим всё это математически. Итак, пусть первый игрок выбирает
ход i. В наихудшей для него ситуации он выиграет
.
Стремясь сделать свой минимальный выигрыш максимальным, он
выбирает свой ход из условия
максиминной.
. Такая стратегия называется
Аналогично, второй игрок, выбирая ход j, в наихудшей для себя
ситуации проигрывает
. Стремясь сделать свой максимальный
проигрыш минимальным, он должен выбирать свой ход из условия
.
Такая стратегия называется минимаксной. Каково же соотношение между
и
?
Теорема 1. Пусть имеются два числовых множества и
есть вещественная функция двух переменных при
и
, если
и
;
. Тогда
существуют.
Доказательство
По определению минимума,
имеем
Аналогично, по определению максимума,
.
. Следовательно
. Но заметим, что правая часть этого неравенства не
зависит от x. Поэтому
. Аналогично, левая часть не
зависит от y. Поэтому
доказать.
, что и требовалось
Замечание. Возможность применения этой теоремы к нашей ситуации
основана на том, что платёжную матрицу
можно рассматривать как
функцию двух переменных f (i, j )  aij , где i  A  {1,2,..., n} и j  B  {1,2,..., m} .
Поэтому
.
Обратите
внимание
меньше или равен
на
самую
. У нас же
получилось, что
и
одинаковы и равны 4. Оказывается,
именно в этом равенстве всё дело, именно это равенство обеспечивает и
существование уравновешенной пары и цены игры. Дадим соответствующие
определения и теоремы.
Определение.
Пусть
есть
действительная
функция,
определённая для всех
. Точка
, где
называется Седловой точкой функции
, если выполнены следующие
условия:
1.
;
2.
.
Теорема 2. Пусть
для всех
вительная функция, определённая
и существует
и
. Тогда для
того, чтобы
необходимо
чтобы
имела седловую точку. Кроме того,если
точка функции
и
, то
достаточно,
есть седловая
.
Доказательство
Достаточность.
Пусть
есть
,
Аналогично,
седловая
откуда
точка
следует,
,
функции
что
откуда
.
Тогда
следует,
.
что
. Сводя всё вместе, получаем
. Но так как
,
,
то отсюда следует, что
.
Сравнивая это с результатом теоремы 1, где было доказано обратное
неравенство, получаем, что
.
Необходимость.
Пусть
множества
. Пусть
, при котором
принимает своё максимальное значение,
то есть max min f ( x, y)  f ( x0 , y) . Аналогично, пусть у0- это тот элемент
yB
yB
множества
, при котором
то есть
Покажем, что
принимает своё минимальное значение,
.
- седловая точка функции
о том, что
, имеем
. В силу предположения
.
По определению минимума, имеем
(1)
следует,
(1)
, и поэтому из
что
.
Отсюда
следует,
что
. (2)
Аналогично, по определению максимума,
(1)
следует,
что
, и поэтому из
.
Отсюда
следует,
что
. (3)
Объединяя вместе (2) и (3), получаем
соответствует тому, что
, что
.
Замечание. На основании интерпретации матрицы как функции двух
переменных
отсюда следует, что седловая точка
матрицы определяется условием
платёжной
, то есть седловая точка
матрицы есть элемент, который минимален в своей строке (
максимален в своём столбце (
седловые точки матрицы.
), но
). Это позволяет легко находить
Обратите внимание, что в том примере, с которого мы начинали наш
раздел, точка
была именно седловой точкой. Элемент платёжной
матрицы
характеризовался именно тем свойством, что он был
максимальным в своём столбце и минимальным в своей строке.
Ответим еще на некоторые вопросы, касающиеся седловых точек.
1. Может ли у матрицы быть несколько седловых точек?
две седловых точки (i=1, j=1) и (i=1, j=3).
2. Если седловых точек несколько, то не возникает ли каких-то
противоречий между ними?
Ответ отрицательный. Более того, если (
)и(
) две седловые точки, то
(
) и (i2 j1 ) - тоже седловые точки и ai , j  ai j  ai j  ai j .
1 1
12
21
2 2
Докажем это для произвольной функции
Пусть
и
две седловые точки этой функции. Тогда
имеем
,
следующую цепочку
следует, что на самом деле
следует, например, что
- также седловая точка.
3. Все ли матрицы имеют седловую точку?
Ответ отрицательный. У матрицы
, и мы имеем
, откуда
. Отсюда же
, то есть
седловых точек нет.
5. Нахождение смешанной стратегии
Цена игры
Оформим теперь всё сказанное выше математически. Рассмотрим
сначала ситуацию, когда все
. Это гарантирует нам, что выигрыш
первого игрока (и, соответственно, проигрыш второго) всегда будет
положительным. Пусть в распоряжении первого игрока имеется ходов
и он выбирает их случайным образом, так что ход номер
делается с вероятностью
. Набор чисел
и называется
смешанной стратегией первого игрока. Так как
- вероятности, то
. Пусть есть гарантированный средний выигрыш
первого игрока. Но что значит гарантированный? Это означает, что при
любом ходе второго игрока первый игрок получит в среднем не меньше, чем
. Математически это означает,
что
(4)
Заметим, что
. Перейдём от величин к величинам
все уравнения на , получим систему неравенств
Но у нас есть еще условие нормировки
. Переходя к
. Тогда, деля
, запишем его в
виде
. В чем же заключается задача выбора оптимальной смешанной
стратегии? Она заключается в том, чтобы так выбрать числа
,
чтобы гарантированный средний выигрыш был максимальным. Но тогда
будет минимальным и задача приобретает вид
а11 х1  а21 х2  а31 х3  ...  аn1 xn  1
a12 x1  a22 x2  a32 x3  ...  an 2 xn  1
.........
(5)
a1m x1  a2 m x2  a3m x3  ...  anm xn  1
Это - типичная задача линейного программирования. Решая ее, мы найдем
 и х1 ,..., хn  , откуда затем найдем и pi  xi  . Заметим, что для pi можно
x
написать и другую формулу pi  n i . Встанем теперь на точку зрения
x
j 1
j
второго игрока. Он ведь тоже может применить смешанную стратегию,
выбирая свои ходы случайным образом с вероятностями (q1, q2 ,..., qm ) , для
которых тоже верно
.
Он тоже имеет некоторый максимальный средний проигрыш
; слово
“максимальный” означает, что при любом ходе первого игрока он не должен
проиграть в среднем больше, чем . Математически это означает, что
(6)
Заметим, что
. Перейдём от величин к величинам
все уравнения (6) на , получим систему неравенств
. Тогда, деля
Условие нормировки
примет теперь вид
. Задача выбора
оптимальной смешанной стратегии вторым игроком заключается, очевидно,
в том, чтобы выбрать
так, чтобы было минимальным. Это
приводит к задаче
(7)
Это также стандартная задача линейного программирования. Решая её, мы
найдём
и
, откуда легко найти и интересующие нас величины
:
. Тем самым определяется и оптимальная смешанная
стратегия второго игрока. А теперь обратите внимание на самый важный
момент в этих рассуждениях. Задачи (5) и (7) являются парой двойственных
задач линейного программирования! Но тогда, в силу первой теоремы
двойственности, экстремальные значения линейных форм этих задач должны
быть равны, то есть при оптимальных смешанных стратегиях обеих игроков
должно выполняться соотношение
, или
. Это общее значение и
называется ценой игры. Системы (5) и (7) позволяют, таким образом,
найти оптимальные смешанные стратегии обеих игроков и цену игры, то есть
они позволяют решить игру. Обратите внимание на то, какую задачу мы
решили. От смешанных стратегий средний выигрыш первого игрока (и,
соответственно,
средний
проигрыш
второго)
будет
равен
, где
и
решали задачу
. Находя
, мы
, то есть задачу нахождения
.
,
то
Находя
есть
мы
задачу
решали
задачу
нахождения
. У нас получилось, что
, то есть, что
и
совпадают! Это позволяет говорить о том, что в смешанных
стратегиях всякая игра двух лиц с нулевой суммой имеет седловую
точку. Это положение является основной теоремой, касающейся игр двух лиц
с нулевой суммой.
Как и всякая седловая точка, пара стратегий
и
является уравновешенной парой. Это означает, что если противник знает, что
я применяю стратегию, соответствующую седловой точке, то ему нет смысла
а стратегии ничего не даст.
Игроки, так сказать, могут “играть в открытую”.
В заключение этого раздела отметим, что делать, если не выполняется
условие
. В этом случае следует перейти к игре с платёжной
матрицей
(8)
где
игроков останутся теми же, то есть мы найдём
и
. Что касается цены новой игры , то она связана с ценой
старой игры тем же соотношением, что и (8)
, то есть
,что и решает исходную задачу.
6. Геометрическое решение игры
В случае, когда число чистых стратегий одного из игроков (скажем,
первого) равно двум, возможно геометрическое решение игры, то есть
нахождение её цены и смешанных стратегий каждого игрока.
Рассмотрим идею этого решения на случае n=m=2, когда платёжная
матрица имеет вид
.
Пусть первый игрок применяет смешанную стратегию с
,
так как должно быть
.
. Тогда
Рассмотрим прямоугольную систему координат, где по оси абсцисс
откладывается величина p (она занимает отрезок
величина среднего выигрыша первого игрока. Пусть второй игрок выбирает
ход j=1. Тогда средний выигрыш первого игрока будет равен
,
что является отрезком прямой, соединяющей точки
и
. Если
второй игрок выбирает ход j=2, то средний выигрыш первого игрока будет
равен
, что является отрезком прямой, соединяющей точки
и
. Минимальный выигрыш первого игрока представляет собой
минимальное значение из ординат этих двух прямых и на рисунке он
изображен жирной линией. Из рисунка видно, что максимальное значение
этого минимального выигрыша определяется точкой пересечения этих двух
отрезков
и оптимальная смешанная
стратегия первого игрока есть
.
Аналогично, максимальный проигрыш второго игрока определяется
максимальным значением из ординат этих двух прямых и на рисунке он
изображен штриховой линией. Легко видеть, что минимальное значение
этого максимального проигрыша также равно . Смешанная стратегия
второго игрока есть
, где находится из того условия, чтобы при
любом ходе первого игрока проигрыш второго был бы равен одной и той же
величине
и равен также .
Таким образом, мы нашли и цену игры и оптимальные смешанные стратегии
каждого игрока.
На рисунке приведен лишь самый интересный и стандартный случай.
Возможны и другие варианты, два из которых приведены ниже.
В варианте, приведенном на рис. 2, оптимальной для первого игрока
является чистая стратегия с p=1, то есть первый игрок всегда должен
выбирать первый ход; для второго игрока оптимальным является выбор
второго хода, то есть i=1, j=2 является седловой точкой платёжной матрицы.
В ситуации, приведённой на рис. 3, есть целый отрезок оптимальных
значений
, то есть оптимальная смешанная стратегия
неоднозначна.
Эта методика легко переносится на случай, когда n=2, а m>2. Тогда
платёжная матрица имеет вид
и мы должны нарисовать m отрезков прямых
,
соединяющих точки
и
. Затем нужно построить ломаную линию,
соответствующую минимальному значению ординат всех этих отрезков.
Максимальное значение этой ломаной и даст значение цены игры .
Оптимальное значение p определится как точка пересечения тех прямых,
которая даёт значение .
Рассмотрим это на примере. Пусть платёжная матрица имеет вид
.
Тогда мы должны построить три отрезка прямых
Они изображены на рис. 4, где также жирной линией
выделен минимальный выигрыш первого игрока. Легко видеть, что
максимальное значение этого минимального выигрыша определяется
пересечением прямых, соответствующих j=2 и j=3, то есть определяется из
условия
, откуда следует, что
, так что
оптимальная смешанная стратегия первого игрока есть
.
Цена игры
. Что касается второго игрока, то в
образовании цены игры участвуют только j=2 и j=3. Поэтому ход j=1 он
вообще
не
должен
делать;
,
считая,
что
,
,
получим
то есть как при первом, так и при втором ходе первого игрока проигрыш
второго должен быть равен . Отсюда получаем, что
, то есть
оптимальная смешанная стратегия второго игрока есть
.
Линейные модели исследования операций.
План
1. Задача о диете, задача планирования производства (о распределении
ресурсов), транспортная задача.
2. Задача коммивояжера. Задачи линейного программирования.
3. Двойственные задачи линейного программирования.
4. Устойчивость оптимального плана.
Рассмотрим теперь основные идеи, касающиеся игр двух лиц с
ненулевой суммой. В этом случае игра задаётся двумя матрицами, которые
обычно объединяют в одну и пишут в виде
a11 , b11  a12 , b12   a1m b1m  




a n1 , bn1  a n 2 , bn 2   a nm bnm 
a ij выигрыш первого игрока и
первый игрок делает ход
bij выигрыш второго, если
aij  bij  0
В такой ситуации появляется принципиально новый момент, которого
Когда, то интересы обоих игроков прямо противоположны и возможность
сговора исключена в силу противоположности интересов. Если, то интересы
игроков могут хотя бы частично совпадать, что и определяет возможность
хотя бы частичного сотрудничества между ними.
И эта возможность сговора не упрощает, а сильно усложняет
ситуацию! Потому, что до чего и как договорятся игроки в очень сильной
степени зависит от двух вещей: от самой возможности вести переговоры и от
вещь и математика до неё еще не добралась.
Игры двух лиц с ненулевой суммой принято разбивать на два класса некооперативные и кооперативные. В некооперативных играх игроки не
имеют возможности общаться друг с другом. Как же они могут договориться
тогда возможность
такого сговора появляется в ходе повторения игры, ведь можно наказывать
партнёра, выбирая заведомо плохой для него ход. Но вот что из этого
В кооперативных играх игроки имеют возможность договариваться в
любое удобное для них время и никаких косвенных приёмов для
договорённостей им применять не надо.
Некооперативная игра двух лиц
Пусть задана игра двух лиц с матрицей
a11 , b11  a12 , b12   a1m b1m  




a n1 , bn1  a n 2 , bn 2   a nm bnm 
В теории рассматриваются в основном две стратегии поведения
игроковМаксиминная стратегия
человека, который, рассчитывая на наихудшую ситуацию, хотел бы иметь в
этом случае максимум возможного.
Вт
минимаксная стратегия. При её использовании игрок ставит своей задачей не
выиграть самому, а “наказать” второго игрока, действуя по принципу: “пусть
у меня две коровы сдохнут, лишь бы у соседа корова сдохла”.
Встанем снова на позицию первого игрока. Пусть он снова применяет
смешанную стратегию. Но, применяя её, он считает не свой выигрыш, а
выигрыш второго игрока. Если второй игрок делает ход j, то его средний
выигрыш составит величину.
Рассмотрим подробнее случай n=m=2. Тогда платёжная матрица игры
имеет вид
a11 , b11  a12 , b12  
a , b  a , b 
 21 21
22
22 
Найдём геометрически максиминную стратегию и стратегию угрозы
первого игрока. Начнём с максиминной стратегии. Пусть первый игрок
выбирает ход i=1 с вероятностью p1  p . Тогда p 2  1  p . Если второй
игрок делает ход j=1, то средний выигрыш первого игрока будет равен
a11 p  a 21 (1  p) , что даёт отрезок прямой, соединяющий точки (а 21 ,0) и
(а11 ,1) .
Если второй игрок делает ход j=2, то средний выигрыш первого игрока
будет равен a12 p  a 22 (1  p) , что даёт отрезок, соединяющий точки (а 22 ,0) и
(а12 ,1) . Минимум из этих двух выигрышей на рисунке нарисован жирной
линией, из которой ясно, как определяется гарантированный выигрыш v
первого
игрока
и
оптимальное
значение р  р  :
  a11 p   a 21 (1  p  )  a12 p   a 22 (1  p  ) . Чему равен  и p  в других
случаях расположения этих двух прямых сообразите сами.
Теперь рассмотрим стратегию угрозы первого игрока. Пусть он снова
применяет смешанную стратегию (р, 1-р). Если второй игрок делает ход j=1,
то средний выигрыш второго игрока будет равен b11 p  b21 (1  p) , что даёт
отрезок прямой, соединяющий точки (b21 ,0) и (b11 ,1) . Если второй игрок
делает ход j=2, то его средний выигрыш будет равен b12 p  b22 (1  p).
b22
b11
b21
b12
p*
p
Напомним, что первый игрок считает сейчас не свой выигрыш, а
выигрыш второго игрока. Его
выигрыш. Максимальный выигрыш второго игрока изображен на рис. 6
 и p*:
жирной линией; из рисунка же ясно, как находятся
  b11 p   b21 (1  p  )  b12 p   b22 (1  p  ) .
Проиллюстрируем эти понятия на примере игры, которая имеет
платёжную матрицу
(1,1)
(2,1)
(1,1) (1,2) 


и которая получила название “семейный спор”. Название возникло изза следующей её интерпретации. Муж (игрок 1) и жена (игрок 2) могут
или театр
(i=2, j=2). Согласно обычному стандарту, мужчина предпочитает футбол, а
предпочтительное зрелище. И если они поругаются и пойдут в разные
стороны (i=1, j=2 или i=2, j=1), то оба проиграют, получая (-1,-1).
Найдём стратегии первого игрока (очевидно, что в силу
симметричности платёжной матрицы стратегии второго игрока точно такие
же).
Рассматривая максиминную стратегию первого игрока, когда он
выбирает ход i=1 с вероятностью p, получим, что его выигрыш будет равен
2p-1(1-p) при j=1, -1p+1(1-p) при j=2.
Величина p* находится из условия 2p*-(1-p*)=- p*+(1- p*), откуда имеем
p*=2/5, так что смешанная стратегия первого игрока есть (2/5,3/5) и его
2
2 1
гарантированный выигрыш равен   2   1  (1  )  .
5
5 5
Применяя стратегию угрозы, он считает выигрыш второго игрока,
который будет равен
1p-1(1-p) при j=1,
-1p+2(1-p) при j=2.
Величина p* находится из условия 1p*-(1-p*)=- p*+2(1- p*),
откуда следует, что p=3/5, так что смешанная стратегия первого игрока
есть (3/5,2/5). При этом выигрыш второго игрока будет в любом случае равен
3
3 1
  1   1  (1  )  .
5
5 5
Таким образом, применяя максиминную стратегию первый игрок
может гарантировать себе выигрыш, равный 1/5; применяя стратегию
угрозы он может быть уверен, что второй игрок получит не более 1/5.
9. Кооперативная игра двух лиц. Переговорное множество
Прежде, чем говорить о кооперативных играх, вернёмся еще раз к
семейный спор”. Пусть первый игрок
использует смешанную стратегию (p,1-q). Тогда
средние выигрыши игроков будут равны
  2 pq  1  p(1  q)  1  q(1  p)  1  (1  p)(1  q)
,
  1  pq  1  p(1  q)  1  q(1  p)  2(1  p)(1  q)
Тем самым пара (p, q) превращается в пару ( ,  ).
Рассмотрим плоскость. Перебирая все возможные значения пар (p, q)
мы получим на плоскости некоторую областьОна ограничена прямыми,
1), (2, 1), а также
куском параболы. В ней есть “провал”, ограниченный именно этой
параболой. А теперь вернёмся к общему случаю игры двух лиц с платёжной
матрицей. Допустим, что игроки имеют возможность договариваться о
совместных действиях. А теперь вернёмся к общему случаю игры двух лиц с
платёжной матрицей и допустим, что игроки имеют возможность
договариваться о совместных действиях. В чем выразятся эти совместные
действия? Раньше ход номер i первого игрока выбирался с вероятностью и
ход номер j второго игрока с вероятностью и ходы обоих игроков были
независимы так что комбинация (i, j) появлялась с вероятностью. Сейчас
ходы выбираются совместно и поэтому комбинация ходов появляется с
некоторой совместной вероятностью. Совместная игра сводится таким
образом к выбору совместной смешанной стратегии.
Эту область R можно построить следующим образом. Представим себе,
что на плоскости мы поставили точек с координатами. Тогда R есть так
называемая выпуклая оболочка этих точек. Наглядно её можно представить
так: вообразите себе, что в точках вбиты гвоздики. Далее мы берём кольцо из
резинки, растягиваем его, надеваем снаружи на все эти гвоздики и отпускаем
резинку. Она сократится и обтянет всю эту систему гвоздей, ограничивая как
раз ту область, которая и называется выпуклой оболочкой. Точки окажутся
при этом либо в вершинах получившегося многоугольника, либо внутри
области. Так в игре типа “семейный спор” область R есть выпуклая оболочка
точек (-1,-1), (2, 1) и (1, 2).
Определение 1. Точка называется подчинённой точке если
одновременно и, причем хотя бы одно из этих неравенств строгое.
Очевидно, что если точка подчинена точке, то в процессе торговли
игроки безболезненно откажутся от точки в пользу точки так как при таком
также, что точки, которым подчинена точка, лежат правее и выше на
множестве R.
Определение 2. Множество точек из R, которые не подчинены
никаким другим точкам и для которых выполняется условие     ,     ,
называется переговорным множеством или множеством Парето.
Легко догадаться, что переговорное множество это та часть правой
верхней (или, как еще говорят, северо-восточной) границы множества R, для
которой выполнены условия     ,     . Теперь очевидно, что
собственно торговля и согласование стратегий игроков будут вестись на
переговорном множестве. До чего они там
нельзя, так как на этом множестве интересы игроков прямо противоположны.
Результат зависит от умения вести переговоры и лежит за рамками
математического исследования. Итак, в определённом смысле, решить
кооперативную игру двух лиц означает построить переговорное множество.
Напомним основные этапы его построения.
1. На плоскости ( ,  ) нанести точки,i=1,2,…,n, j=1,…,m.
2. Построить выпуклую оболочку этих точек.
3. Найти максиминные выигрыши обеих игроков (  ,   ) и построить
точку status quo.
4. Нарисовать северо-восточную границу построенного множества,
удовлетворяющего условиям     ,     . На этом работа
типа “семей
соединяющей точки (1, 2) и (2, 1). Вот на нём муж и жена и должны выяснять
свои отношения.
10. Арбитраж
Итак, математик сделал своё дело и уходит в сторону, а игроки
звестно. Хорошо, если они люди
сговорчивые и покладистые. К сожалению, встречаются люди (и не только
люди, а целые государства), которые, желая получит себе возможно больше,
торгуются очень упорно, пуская в ход всё, даже угрозы. В результате
переговоры оканчиваются ничем, угрозы приводятся в исполнение… Чем это
кончается можно очень часто наблюдать в жизни. Одним из выходов из этой
ситуации является приглашение со стороны некоторого арбитра, который бы
одинаково относился к обеим сторонам, и предложить ему указать
совместную стратегию “по справедливости”. Если арбитр действительно
“справедливый” и “беспристрастный”, он может вынести устраивающее
обоих игроков решение. Но что означает “справедливый” и
“беспристрастный”? Достаточно очевидно, что к такому арбитру должны
быть предъявлены следующие требования.
1. Арбитражное решение должно быть элементом переговорного
множества.
2. Арбитражная схема должна быть независимой от имён или
обозначений игроков.
3. Если две игры близки между собой в каком-то смысле, то и
арбитражные решения должны быть близки.
4. Арбитражное решение должно отражать действенность угроз
игроков.
Аксиома 1. (Оптимальность по Парето). Точка должна быть
элементом переговорного множества, то есть
1.  0 ,  0  
2.     ,    
3.  в нет точки  ,   отличной от точки  0 ,  0  такой, что

  ,    .
Аксиома 2. (Симметрия). Пусть игра обладает следующими
свойствами:
1.     
2. если точка  ,     , то и точка  ,    . Тогда должно
выполняться условие  0   0 .
Другими словами, если игроки находятся в совершенно одинаковой
ситуации, то и арбитражное решение должно быть одинаковым. Следующие
две аксиомы далеко не столь очевидны, как предыдущие.
Аксиома 3.
(Инвариантность
относительно
линейного
преобразования). Пусть имеются две игры с одинаковым числом ходов для
каждого игрока и с платёжными матрицами, связанными соотношениями
а ij   1   1 a ij , bij   2   2 bij , i  1,2,.., n j  1,2,..., m
Тогда арбитражные решения для них также должны быть связаны
соотношениями  0   1   1 0 ,  0   2   2 0
Аксиома 4. (Независимость несвязанных альтернатив). Если к игре
добавить новые ходы для игроков с добавлением новых элементов
платёжных матриц таким образом, что точка status quo не меняется, то либо
арбитражное решение также не меняется, либо оно совпадает с одной из
добавленных сделок. Дж. Нэш показал, что существует единственная
арбитражная схема, удовлетворяющая этим четырём аксиомам. Арбитражное
решение должно выносится из условия, то есть “справедливое” решение
арбитра должно удовлетворять условию
переговорному множеству.
для всех точек, принадлежащих
Кстати, в игре “семейный спор”, в силу симметрии обеих игроков,
арбитражным решением должна быть точка (3/2, 3/2), лежащая на середине
отрезка, соединяющего точки (1, 2) и (2, 1). Она получается при следующей
совместной стратегии. Муж и жена должны ходить вместе на футбол или в
театр одинаково часто (например, по очереди).
список литературы
1. Вентцель Е.С. Исследование операции. -М.: Наука, 1980.
2. Основы исследования операций. В 3-х томах. -М.: Мир, 1972.
3. Гермейер Введение в теорию исследования операции
4. Давыдов Э.Г. Исследования операций. Уч. Пособие для вузов по
спец. «Прикладная математика» и «экономическая кибернетика». -М.: ВШ,
1990.
5. Морозов В.В. Исследования операций в задачах и упражнениях. М.: ВШ, 1986.
6. И. С. Бахвалов Численные методы. Ч.1, -М.: Наука, 1973.
7. Дьячко А.Г. Математическое планирование экспериментальных
исследований. -М.: МИСиС, 1982.
8. Л. И. Турчак Основы численных методов. -М.: Наука, 1987.
9. Г. И. Воробьева, А. И. Данилова Практикум по численным
методам. -М.: Наука, 1979.
10. Н. Культин Программирование на Object Pascal в Delphi 5. –Спб:
БХБ, Санкт-Петербург, 1999.
11. Фаронов В.В. Турбо Паскаль 7.0 Учебный курс.-М.: 1998.-433с.
12. Фаронов В.В. DELPHI 4 . Учебный курс.-М.: 1999.-464с.
13. Основы исследования операций. В 3-х томах. -М.: Мир, 1972.
14. Я. И. Перельман «Занимательная математика»
15. Мартин Гарднер «Путешествие во времени». – Москва, «Мир»,
1990
8.У. Болл, Г. Коксетер «Математические эссе и развлечения». –М.:
«Мир», 1986.
9. В. Н. Дубровский, А. Т. Калинин «Математические головоломки». –
М.: «Знание», 1990
10. «Математический цветник» (составитель и редактор Д. А. Кларнер).
– М.: «Мир», 1983