книги / Математические методы принятия решений
..pdfпослать оба самолета в одном и том же коридоре или направить их по разным коридорам. Сторона В может разместить свои четыре зенитки в пределах рассматриваемых коридоров разными способа ми. Каждая зенитка может произвести только один выстрел. Этот выстрел с вероятностью, равной 1, поражает самолет, если тот ока зался в данном коридоре.
Сторона А имеет две чистые стратегии: стратегия А\ — самоле ты посылаются в разные воздушные коридоры (безразлично, какие именно), стратегия А 2 —оба самолета посылаются в какой-то один из коридоров. Возможные стратегии стороны В следующие: В\ — поставить по зенитке в каждом коридоре, В 2 —поставить по две зе нитки в каких-то двух коридорах (остальные два коридора остаются неохраняемыми), Вз — поставить две зенитки в одном из коридоров и по одной зенитке еще в двух коридорах, S 4 — поставить три зе нитки в одном из коридоров и одну зенитку еще в одном коридоре, Bs — поставить все четыре зенитки в одном из коридоров. Страте гии В4 и Bs заведомо невыгодны хотя бы потому, что три, а тем более четыре зенитки в пределах одного коридора не нужны, по скольку сторона А имеет всего два самолета. Поэтому ограничимся рассмотрением стратегий By, В 2, S 3.
Предположим, что сторона А выбрала стратегию А \, а сторо на S — стратегию By. Ясно, что тогда ни один самолет не прорвется к объекту — выигрыш стороны А равен нулю (ац = 0). Пусть выбра ны стратегии Ау и Вг. Допустим при этом, что зенитки находятся
вкоридорах I и II. Самолеты летят в разных коридорах, причем равновероятны шесть вариантов: они летят в коридорах I и II, летят
вкоридорах I и III, в коридорах I и IV, в II и III, в II и IV, в III и VI. Только в одном из указанных шести случаев ни один из самолетов не прорвется к объекту (когда они летят в коридорах I и И). Ка кие бы два коридора ни выбирала сторона В для размещения пары зениток, всегда для самолетов существуют шесть равновероятных вариантов, и только один из них проигрышный. Таким образом, при выборе стратегий А\ и Bj вероятный выигрыш стороны А состав ляет 5/6 (ап = 5/6). Рассуждая подобным образом, нетрудно най ти остальные элементы платежной матрицы данной игры, которая приведена в табл. 4.10, это есть матрица размерностью 2 x 3 . За метим, что элементы матрицы — вероятностные выигрыши; здесь
Таблица 4.10
Платежная матрица
Стратегии |
В) |
В г |
Вг |
ott |
Л, |
0 |
5 /6 |
1/2 |
0 |
Л2 |
1 |
1/2 |
3 /4 |
1/2 |
Pi |
1 |
5 /6 |
3 /4 |
|
уже чистые стратегии включают в себя случайность. Нижняя це на игры равна 1/2, верхняя равна 3/4. Максиминной стратегией является А 2, минимаксной — В^. Седловой точки нет, оптимальное решение игры лежит в области смешанных стратегий.
Чтобы найти оптимальную смешанную стратегию, воспользу
емся |
видом платежной |
матрицы и соотношениями (4.7) и (4.8). |
|||
В данном случае эти соотношения принимают вид |
|
||||
|
5 |
1 |
1 |
3 |
(4.9) |
|
x 2 ^ l , j X ! |
+ j x 2 ^ l , |
j x i |
+ j x 2 ^ l , |
|
|
|
x i + x 2 = |
|
|
(4.10) |
Решением, соответствующим оптимальной смешанной страте |
|||||
гии, |
является xi = 3/5, |
х 2 = 1. Отсюда |
находим v = 5/8, р\ = 3/8, |
р2 = 5/8. Итак, оптимальная смешанная стратегия стороны А пред полагает использование стратегии Ai с вероятностью 3/8 и страте гии А 2 — с вероятностью 5/8.
Как воспользоваться этой рекомендацией на практике? Если иг ра происходит один раз, то стороне А следует, по-видимому, избрать стратегию А 2, так как р2 >р\. Если данная игра совершается мно гократно (например, по отношению к многим объектам, подлежа щим бомбардировке) — N раз (N » 1), то в 37V/8 случаях сторона А должна избрать стратегию Л ь а в 57V/8 случаях — стратегию А 2.
При выборе стороной А оптимальной смешанной стратегии ее средний выигрыш оказывается в пределах между верхней ценой иг ры, равной 3/4, и ценой игры v = 5/8. При неразумном поведении стороны В выигрыш стороны А может оказаться равным верхней цене игры (и даже может стать больше). Если же сторона В, в свою очередь, будет придерживаться оптимальной смешанной стратегии, то выигрыш стороны А окажется равным цене игры v. Оптимальная
смешанная стратегия стороны В сводится к тому, что эта сторо на вообще не применяет стратегию Вз, стратегию В\ использует с вероятностью 1/4, а стратегию Вз с вероятностью 3/4. Нецелесо образность применения стратегии Вз видна из того, что прямая
1 |
3 |
= 1 |
— Xi + — Х2 |
не принадлежит области допустимых значений D системы (4.9). Для определения вероятностей, с которыми должны применяться стратегии В\ и Вг, воспользуемся уже найденным значением цены игры (V = 5/8):
9 1 - 0 + О — <?,)-£- = у .
Отсюда видно, что q\ = 1/4, qi = 1 —q\ = 3/4.
На практике часто не возникает необходимость находить точное решение игры и решать задачи ЛП большой размерности, достаточ но бывает найти приближенное решение, обеспечивающее средний выигрыш, близкий к цене игры. Например, если нижняя и верхняя цены игры (а и (3) близки, то достаточно взять чистые минимакс ные стратегии; если а и (3 не близки, то можно воспользоваться методом итераций. Здесь один из игроков, например игрок А, выбирает стратегию Ai, игрок В отвечает стратегией B j, которая наименее выгодна для игрока А , т. е. обращает выигрыш страте гии А{ в минимум. Игрок А отвечает стратегией Д fc, которая дает ему максимальный выигрыш при стратегии B j, и т.д. Этот про цесс сходится, но сходимость медленная. Однако в то же время сложность метода практически не возрастает с увеличением раз мерности платежной матрицы.
Мы рассмотрели антагонистические игры двух лиц, т. е. игры, в которых интересы сторон прямо противоположны. Однако реаль ные задачи принятия решения в условиях конфликта характеризу ются большим числом участников и, как следствие этого, неантагонистичностью конфликтной ситуации. Даже для двух игроков их интересы могут пересекаться, что может приводить к ситуациям, взаимовыгодным обоим игрокам. Это приводит к выбору согла сованного решения, приводящего к увеличению выигрыша обоих игроков. Поэтому в неантогонистических играх различают бескоа лиционное поведение, когда соглашения между игроками запрещены
правилами, и кооперативное поведение игроков, когда разрешает ся кооперация: выбор совместных стратегий, совершение побочных платежей.
Обобщением случаев, когда число ходов в игре становится бес конечным и игроки имеют возможность принимать решения непре рывно, занимаются в разделе теории игр, называемом дифферен циальные игры. Здесь траектории движения игроков представляют собой решения систем обыкновенных дифференциальных уравне ний, правые части которых зависят от параметров, находящихся под контролем игроков. Рассматриваются две системы обыкновенных дифференциальных уравнений
X = f(x, |
и), |
(4.11) |
У = 9(У, |
«) |
(4.12) |
с начальными условиями (хо, уо).
Игрок А (или В) начинает движение из фазового состояния хо (или уо) и перемещается в фазовом пространстве Rn согласно (4.11) (или (4.12)), выбирая в каждый момент времени значение параметра u e U (или V e V) в соответствии со своими целями и информацией, доступной в каждом текущем состоянии.
Г л а в а 5
О РАЗВИТИИ МЕТОДОВ РЕШЕНИЯ ЗАДАЧ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ
§5.1. Основные направления развития методов решения задач математического программирования
Можно построить математические модели, описывающие доста точно широкий круг явлений. Однако мы выяснили, что не всякую математическую задачу возможно решить, во-первых, по причине большой ее размерности, во-вторых, из-за наличия нелинейных целевых функций и условий-ограничений. Кроме того, нам хоте лось бы, не решая заново задачу, иметь метод, который позволял бы изменить решения при небольших вариациях исходных данных (па раметров целевой функции и условий-ограничений). Поскольку такие изменения исходных данных происходят случайно, то сле довало бы определить и доверительные границы для решений реальной задачи. Однако тогда мы выйдем за рамки темы насто ящей книги, поскольку решение таких задач относится к области
стохастического программирования.
Тем не менее, удается, пусть и достаточно громоздкими метода ми, установить в задачах линейного программирования, как будет изменяться решение задачи, если известны функциональные зави симости, описывающие изменение исходных данных. Подобные за дачи решают методами параметрического программирования.
Несмотря на то, что разработано много методов решения сете вых задач, трудности в их решении остаются. В ш. 3 мы упоминали, что из-за большой размерности некоторые сетевые задачи строгими методами решить не удается; в подобных случаях применяют эври стические методы, которые позволяют получить пусть и не строго оптимальное решение, но приемлемое в практических приложе ниях.
Вгл. 3 мы рассмотрели сетевые задачи для однородного потока.
Вреальных условиях по сети требуется транспортировать (переда вать) различные «продукты»: например, телефонные разговоры, те леграммы, телевизионные передачи и другое, т. е. необходимо иметь алгоритмы, которые позволяли бы решать задачи о многопродукто вых потоках в сетях. Методы решения многопродуктовых сетевых задач сложны, и поэтому применяемые алгоритмы позволяют ре шить задачу только приближенно.
Естественно стремление исследователей создавать универсаль ные алгоритмы, которые можно было бы применять к достаточно широкому кругу задач математического программирования. К ним относят алгоритмы, реализующие метод проекции градиента и ме тоды штрафных (барьерных) функций: метод внутренней точ
ки, метод внешней точки и комбинированный метод внутренней и внешней точки. Методами штрафных функций можно решать за дачи как линейного, так и нелинейного программирования, хотя вряд ли экономно использовать их для решения линейных задач.
Особое место в практике занимают многокритериальные зада чи и задачи целевого программирования, которые более адекватно описывают реальные явления.
§ 5.2. Понятие о параметрическом программировании
Исходные данные, необходимые для численной постановки реальных задач математического программирования, определяют довольно часто неточно, приближенно. Это связано не только с на личием погрешностей измерений, но и с желанием описать в ма тематической постановке задачи возможное изменение исходных данных, чтобы в дальнейшем для оптимизации решения использо вать наилучшие их значения.
Исследование таких математических проблем, как анализ изме нения решения при вариации исходных данных, оценка устойчиво сти решения, требует разработки методов, учитывающих неопреде ленность задания исходных данных.
Как было показано ранее, к настоящему времени наиболее доступны для решения задачи линейного программирования. Ал горитм, учитывающий неопределенности исходных данных, мы
рассмотрим на примере решения задач линейного программирова ния, так как в других случаях это может оказаться крайне сложной проблемой. Раздел математического программирования, в котором может быть решена данная проблема, называют параметрическим программированием. В этом разделе изучают в основном задачи, которые являются естественным обобщением задач линейного про граммирования, когда исходные данные (коэффициенты) в целевой функции и условиях-ограничениях предполагают не постоянны ми величинами, а функциями, зависящими определенным образом (чаще всего линейно) от некоторых параметров. Всякой задаче пара метрического программирования можно поставить в соответствие некоторую задачу линейного программирования, называемую ис ходной. От того, как именно трактуется исходная задача, зависит трактовка параметрической задачи. Введение параметра обычно от ражает некоторую реальную ситуацию.
Приведем несколько задач параметрического программирова ния, которые наиболее естественным образом могут быть сопостав лены принятой исходной задаче. Рассмотрим, помимо этого, одну из интерпретаций задачи параметрического программирования.
Пусть коэффициенты целевой функции исходной задачи линей ного программирования (2.2) зависят от одного параметра. В зада че (2.2) коэффициенты целевой функции представляют собой цены разных продуктов, а координаты векторов-ограничений могут быть истолкованы как запасы различных ресурсов.
Постановка рассматриваемой задачи параметрического програм мирования может иметь (в простейшем случае) следующий вид:
fix ) = (aoi + b\t)x 1 + + (oon + bnt)xn —►max,
где aoi, ...,aon —исходные (старые) коэффициенты задачи линей ного программирования, Ь\, . . . , Ьп — новые коэффициенты, t — па раметр, t е К 1.
Зависимость коэффициентов этой функции от параметра t мож но понимать как зависимость цены единицы продукта от времени. Различные новые коэффициенты Ь\, ...,Ъ п отражают индивидуаль ный характер зависимости цен разных продуктов от параметра t. Значение целевой функции исходной задачи равно стоимости выпу щенной продукции, а значение целевой функции соответствующей
параметрической задачи показывает, чему равна стоимость выпус каемой продукции при условии изменения цен разных продуктов, когда закон изменения этих цен (от времени, от качества продукции и т. п.) задан.
Рассмотрим случай, когда от параметра зависят координаты си стемы ограничений. Условия-ограничения принимают вид
(оц + c\\t)x\ + |
+ (ain + c\nt)xn ^ aio + d\t, |
||
(ü>ml "b ^Vnl 1"b |
"b (®mn + |
|
^ QmO + dmt, |
x\, ... ,x n ^ 0 , |
te |
R 1. |
|
Здесь aij, i = 1,2, ... , m, j |
= 1,2,..., n, — исходные коэффициенты |
||
из условий-ограничений задачи, а Cÿ |
и |
сЦ —новые коэффициен |
ты, определяющие зависимость исходных коэффициентов от пара метра t
Задача параметрического программирования с s независимыми параметрами t \ , . . . , t a, или s-параметрическая задача, записывает
ся следующим образом: найти максимум функции |
|
|
f{x) = (aoi + bn t i + + b\sts)xi + |
|
|
|
+ (ûon + bn\t\ + ... + bnsta)xn + e\t\ 4- |
+ eats |
при ограничениях |
|
|
(оц + ciii^i |
+ ... + Cns£s)æi + ... 4- (ain 4- c\n\t\ 4- ... + c\nata)xn ^ |
|
|
^ aïo + d\\t\ + |
+ d\ata, |
(®ml |
“b — 4"Cmls^s)3'l 4"• ••"b(ûmn “bCmnl^l 4” — 4_Cmns^s)**'n^ |
|
|
^ ÛmO + dm\t\ + ... + dfnsta, |
|
|
x\, . . . , x n ^ 0, t ] , . . . , t ae R 1. |
|
Рассмотрим метод решения конкретной задачи линейного па раметрического программирования, в которой все коэффициенты целевой функции линейно зависят от некоторого действительного
параметра t :
f(x) = (2 + t)x 1 + (3 —t)x2 + t —►max;
—x\ |
+ 2 x 2 |
^ 4, |
|
|
X \ |
+ |
^ |
5 , |
(5.1) |
2x\ — X2 |
^ |
8, |
|
|
xi ^ 0 , |
X 2 ^ 0 , |
|
t e R 1 |
|
В матрично-векторной форме эта задача записывается следую щим образом:
f(x) = (ао• + Ы)Тх —*• шах, А х ^ а.о, х ^ 0, t е R 1,
где
Для каждого фиксированного значения t задача (5.1) становится задачей линейного программирования, которую называют принад лежащей значению t.
Решением параметрической задачи (5.1) называют явным обра зом заданную функцию
/(t) = m ax{/(x) = (ао- + b tf x \ A x ^ a.o; x ^ 0},
являющуюся решающей функцией задачи (5.1), и набор решающих отношений х \ ( t ) , x n(t), каждое значение которых при данном t равно значениям переменных х\,Х 2, . . . , х п, образующих оптималь ное решение задачи, принадлежащей данному значению t (если это решение существует). Доказано, что г-я критическая область К Т задачи (5.1), г = 1,2,..., определяемая условием
К т= {t | ûojW = a o j + bTjt ^ |
0> 3 = 1,2, . . . , n + m}, |
является отрезком (замкнутым интервалом). Область определения Q |
|
Л |
Л |
решающей функции f(t) выпукла; решающая функция f(t) выпукла в своей области определения.
При любом г = 1,2,... для всех значений t из критической об ласти К г решающая функция является линейной и в силу этого непрерывной в области Q.
В критической области К г при любом г = 1,2,... множества значений решающих отношений Xj(t), j = 1,2, ...,п, ограничены постоянными величинами; сами эти отношения полунепрерывны сверху.
Для построения решающей функции будем пользоваться сим плекс-методом в следующей его модификации. Под последней стро кой первой симплекс-таблицы, полученной при t = to = 0 и со держащей некоторое допустимое базисное решение, приписывают еще одну строку коэффициентов Ь^Ч = —bjt, j = 1, 2, . . . , п + т, где bj = 0 для j = n + l , . . . , n + m. Полученная строка подверга ется тем же преобразованиям, что и остальные (табл. 5.1; г = 1). Естественно, что в задаче (5.1) мы предварительно перешли к огра ничениям-равенствам и ввели новые переменные хз, Х4, Х5. За три итерации (г = 1, 2,3) мы получили оптимальное решение при t = О (в табл. 5.1 для каждой итерации справа выделены разрешающие элементы).
Коэффициенты в целевой функции для выбора разрешающего элемента задаются двумя последними строками при фиксирован ном (заданном) значении t = to. Для данного допустимого базисного решения необходимо построить соответствующую критическую об ласть — множество всех значений t, при которых это решение будет оптимальным. Это множество будет замкнутым интервалом, грани цы которого находят по формулам
аг _ |
\ |
{ — j j j r , - о о |
b j > 0 , j = l , 2 , . . . , n + m j , |
a r ' |
\ |
{ - - ^ f , + о о |
brj < 0 , j = l , 2 , . . . , n + m f . |
Если нижней (верхней) границей этого интервала является —оо (+оо), то найдена нижняя (верхняя) граница области Q. В про тивном случае по крайней мере один из коэффициентов целевой функции ÜQj(t) = OQj + bjt равен нулю. При значениях t = tp, обра щающих выражение + bjt в нуль и называемых критическими,