книги / Математические методы принятия решений

послать оба самолета в одном и том же коридоре или направить их по разным коридорам. Сторона В может разместить свои четыре зенитки в пределах рассматриваемых коридоров разными способа­ ми. Каждая зенитка может произвести только один выстрел. Этот выстрел с вероятностью, равной 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

Платежная матрица

уже чистые стратегии включают в себя случайность. Нижняя це­ на игры равна 1/2, верхняя равна 3/4. Максиминной стратегией является А 2, минимаксной — В^. Седловой точки нет, оптимальное решение игры лежит в области смешанных стратегий.

Чтобы найти оптимальную смешанную стратегию, воспользу­

р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. Нецелесо­ образность применения стратегии Вз видна из того, что прямая

не принадлежит области допустимых значений 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, и т.д. Этот про­ цесс сходится, но сходимость медленная. Однако в то же время сложность метода практически не возрастает с увеличением раз­ мерности платежной матрицы.

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

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

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

с начальными условиями (хо, уо).

Игрок А (или В) начинает движение из фазового состояния хо (или уо) и перемещается в фазовом пространстве 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. Значение целевой функции исходной задачи равно стоимости выпу­ щенной продукции, а значение целевой функции соответствующей

параметрической задачи показывает, чему равна стоимость выпус­ каемой продукции при условии изменения цен разных продуктов, когда закон изменения этих цен (от времени, от качества продукции и т. п.) задан.

Рассмотрим случай, когда от параметра зависят координаты си­ стемы ограничений. Условия-ограничения принимают вид

ты, определяющие зависимость исходных коэффициентов от пара­ метра t

Задача параметрического программирования с s независимыми параметрами t \ , . . . , t a, или s-параметрическая задача, записывает­

Рассмотрим метод решения конкретной задачи линейного па­ раметрического программирования, в которой все коэффициенты целевой функции линейно зависят от некоторого действительного

параметра t :

f(x) = (2 + t)x 1 + (3 —t)x2 + t —►max;

В матрично-векторной форме эта задача записывается следую­ щим образом:

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,..., определяемая условием

решающей функции 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, при которых это решение будет оптимальным. Это множество будет замкнутым интервалом, грани­ цы которого находят по формулам

Если нижней (верхней) границей этого интервала является —оо (+оо), то найдена нижняя (верхняя) граница области Q. В про­ тивном случае по крайней мере один из коэффициентов целевой функции ÜQj(t) = OQj + bjt равен нулю. При значениях t = tp, обра­ щающих выражение + bjt в нуль и называемых критическими,