Решение двух классов дискретных задач исследования операций тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат наук Шалбузов Камил Джавид О.

• Шалбузов Камил Джавид О.
• кандидат наук
• 2015

Оглавление диссертации кандидат наук Шалбузов Камил Джавид О.

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

Списки основных обозначений и сокращений

ГЛАВА 1. Модификация метода Гомори решения задачи целочисленного линейного программирования

1.1. Постановка задачи и циклический алгоритм Гомори

1.2. Модифицированный циклический алгоритм

1.2.1. Алгоритм пометок

1.2.2. Алгоритм подбора параметров

1.2.3. Сравнение алгоритма пометок с алгоритмом подбора параметров

1.3. Сравнение модифицированного циклического алгоритма с другими алгоритмами

ГЛАВА 2. Решение матричных игр специального вида

2.1. Алгоритм решения матричных игр

2.2. Дискретная игра «нападение-защита»

2.2.1. Постановка задачи

2.2.2. Решение дискретной игры в смешанных стратегиях

2.2.3. Поиск нижнего и верхнего значений игры

2.2.4. Игра с бюджетными ограничениями

2.3. Игры комбинаторного типа

2.3.1. Игра фермера против природы

2.3.2. Соревнование двух фермерских хозяйств

2.3.3. Взаимодействие двух сторон на нескольких пунктах

ГЛАВА 3. Игровая модель распределения ресурсов при защите

объекта

3.1. Постановка задачи

3.2. Свойства Z-образных функций

3.3. Решение игры в чистых стратегиях

3.4. Использование смешанных стратегий

3.5. Доминирование при поиске максиминных и минимаксных стратегий

3.6. Поиск максиминных и минимаксных стратегий

ЗАКЛЮЧЕНИЕ

ЛИТЕРАТУРА

Приложение 1. Решение вспомогательной задачи в модифицированном циклическом алгоритме при п = 1,2

Приложение 2. Доказательство теорем 2.3 и 2.4

Введение диссертации (часть автореферата) на тему «Решение двух классов дискретных задач исследования операций»

ВВЕДЕНИЕ

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

В качестве оптимизационных задач рассмотрены задачи целочисленного линейного программирования (ЦЛП). Для решения задач ЦЛП в [75] Гомори сформулировал циклический алгоритм (ЦА), который, используя отсечения, за конечное число шагов находит оптимальное решение. Метод отсечений для задачи ЦЛП состоит в добавлении ограничений, не изменяющих множество допустимых целых точек, и последующем решении соответствующих непрерывных задач. Методы отсечений являются одним из классических подходов к решению ЦЛП (см. [28,29,42,47,49,54]). В [76] Гомори определил полностью целочисленный алгоритм (ПЦА), в котором симплекс-таблица на каждом шаге остается целочисленной. В [86] Мартином был предложен алгоритм (АМ), в котором используется специальный метод построения отсечения. Будем называть его отсечением Мартина. При построении отсечения Мартина в данной работе предлагается поиск производящей строки, минимизирующий число преобразований в АМ. Укажем также работы Ба-лаша [62-64], Балинского [66-68], Джерослоу [82-85], Хохлюка [50-53] и Червака [55]. В перечисленных алгоритмах возникают ситуации, когда добавленное отсечение задается гиперплоскостью, не содержащей неотрицательных допустимых решений. В данной диссертационной работе предлагается модификация ЦА (МЦА), в которой строятся отсечения более близкие к многограннику ограничений, чем в ЦА.

} ?

I

В качестве дискретных игровых задач рассмотрены матричные игры специального вида. Алгоритмам решения матричных игр посвящена обширная литература (см. [3,11,12,39,43,56,61]). Отметим метод двойного описания [35] и метод фон Неймана, основанный на решении системы дифференциальных уравнений [27,93]. Однако чаще используется прием сведения решения матричной игры к паре двойственных задач линейного программирования (см., например, [10]). В настоящей работе предлагается алгоритм, основанный на решении подыгр. Алгоритм применяется к дискретному варианту игры «нападение-защита» и к играм комбинаторного типа. В первой игре нападение распределяет средства для прорыва через пункты, обороняемые защитой. Непрерывные игры распределения бесконечно-делимых ресурсов изучались многими авторами (см., например, [18,19,21,70,72,92]). Особо отметим следующие основополагающие работы. Блэккет в [71] дал общее определение игры и исследовал игровую модель выбора маршрута поставки ресурса. В диссертации построены явные формулы решений в смешанных стратегиях для моделей Гросса [27,78,79], Гермейера [11,16] и их обобщения [36,37]. Однако дискретная матричная игра распределения штучных ресурсов в общем случае имеет матрицу больших размеров. Способ построения приближенного решения дискретной игры указан в [69]. Предложенный в диссертации алгоритм позволяет обобщение на игры с бюджетными ограничениями.

Также в работе рассматривается антагонистическая игра нападения против защиты, осуществляющей охрану объекта. В последнее время интерес к играм распределения ресурсов возрос в связи с задачами охраны объектов (см., например, [5,6,13,17,18,21,89]). В рассматриваемой модели обе стороны могут использовать одновременно несколько средств. Вероятность преодоления некоторым средством нападения некоторого средства защиты задается ^-образной функцией, часто используемой в моделях исследования операций [5,6,17].

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

Предмет и объект исследования. Объектом исследования являются задачи ЦЛП, антагонистические и матричные игры, а также методы их решения.

Методика исследований. Методологическую основу исследования составляют

• методы дискретной оптимизации;

• математические методы теории игр;

• элементы теории чисел.

Научная новизна заключается в том, что

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

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

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

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

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

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

Основные положения, выносимые на защиту.

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

• Получено решение дискретной игры «нападение-защита» в чистых и смешанных стратегиях.

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

• На основе свойств ^-образных функций разработан метод поиска мак-симинных стратегий в игре, моделирующей охрану объекта.

Апробация результатов исследования. Основные результаты, полученные в диссертации, докладывались на VI и VII Московской международной конференциях по исследованию операций ОКМ2010 и ОИМ2013, на ежегодных научных конференциях «Ломоносовские чтения 2013» и «Ломоносовские чтения 2014», а также на ежегодной научной конференции «Тихоновские чтения» (Москва, 2013).

Публикации. По теме диссертации имеется восемь публикаций. Основные результаты работы опубликованы в четырех статьях из списка ВАК РФ [32-34,57]. В работах [32-34] Шалбузову К.Д. принадлежат формулировки и доказательства результатов, Морозову В.В. принадлежит постановка задачи и проверка результатов. В работе [57] Морозовым В.В. была предложена модификация метода Гомори при п — 2, Шалбузов К.Д. разработал эту модификацию для произвольного числа переменных п.

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

В первой главе предлагается модификация циклического алгоритма Гомори (МЦА) решения задачи ЦЛП. В МЦА строятся отсечения более близкие к многограннику ограничений. При поиске модифицированного отсечения возникает вспомогательная задача ЦЛП с одним ограничением. В разделе 1.2.1 эта задача решается алгоритмом пометок. В разделе 1.2.2 предлагается другой метод (алгоритм подбора параметров) решения вспомогательной задачи, основанный на формуле общего решения линейного диофантова уравнения. В разделе 1.3 рассмотрены полностью целочисленный алгоритм Гомори (ПЦА), в котором симплекс-таблица на каждом шаге остается целочисленной, и алгоритм Мартина (АМ), в котором отсечение строится специальным способом (отсечение Мартина). В данной работе при построении отсечения Мартина предлагается поиск производящей строки, минимизиру-

ющий число преобразований в АМ. В конце главы приведены результаты численного сравнения МЦА с ЦА, ПЦА и АМ.

Во второй главе предлагается метод решения матричных игр больших размеров специального вида. Чтобы выделить специальный класс матриц в разделе 2.1 рассмотрены вспомогательные задачи игроков, в которых каждый игрок находит наилучшую чистую стратегию в ответ на произвольную смешанную стратегию партнера. В этом же разделе предложен алгоритм решения матричной игры, основанный на решении последовательности подыгр (АРП), соответствующих некоторым подматрицам исходной матрицы игры.

В разделе 2.2 исследуется модель Дрешера дискретной игры «нападение-защита». В разделе 2.2.2 сформулировано условие совпадения значения дискретной и непрерывной игр. В этом же разделе указана вспомогательная задача (ВЗ) для второго игрока, которая сводится к нахождению точки минимума выпуклой сепарабельной функции с использованием критерия Гросса.

В разделе 2.2.3 рассматриваются задачи построения нижнего и верхнего значений игры в модели Дрешера. Для поиска максиминной чистой стратегии используется алгоритм глобального поиска. Минимаксная чистая стратегия ищется с использованием дискретного аналога принципа уравнивания. В разделе 2.2.4 АРП применяется для поиска решения игры с бюджетными ограничениями. В частных случаях получены явные формулы для значения игры и оптимальных стратегий. В разделе 2.3 АРП применяется к следующим матричным играм комбинаторного типа, в которых стратегиями игроков являются всевозможные перестановки последовательности 1 ,...,п: игра фермера против природы [22,25], соревнование двух фермерских хозяйств [26], взаимодействие двух сторон на нескольких пунктах. ВЗ для каждого игрока во второй модели сводятся к упорядочиванию чисел, а в первой и третьей моделях — к решению задачи о назначениях.

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

использовать штучные средства защиты и нападения. Считается, что стратегия нападения преодолело стратегию защиты, если для каждого средства защиты существует средство нападения, которое это средство защиты преодолеет. Вероятность этого события берется в качестве функции выигрыша нападения. В отличие от модели Дрешера главы 2 функция выигрыша в соответствующей непрерывной игре в общем случае не является ни выпуклой, ни вогнутой. В разделах 3.3 и 3.4 формулируются условия существования решений игры в чистых и смешанных стратегиях. В разделах 3.5 и 3.6 обсуждаются условия доминирования и указываются методы поиска максиминных и минимаксных стратегий.

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

В приложении 2 доказаны теоремы 2.3 и 2.4.

Алгоритмы, предложенные в главах 1 и 2, были программно реализованы соответственно в системах MATLAB и MAPLE, а эксперименты осуществлялись на компьютере с процессором Intel Core i3 540 с тактовой частотой 3.07 ГГц и объемом оперативной памяти 4 ГБ. Во всех главах для сравнения алгоритмов генерировалась 1000 задач. В главе 1 элементы матрицы dij. г — 0,1, ...,m, j = 1 ,...,n (ai0, г = 1 ,...,т) выбирались как случайные целые числа, равномерно распределенные на отрезке [0,100] ([100,200]). В главе 2 параметры выбирались как случайные целые числа, равномерно распределенные на отрезке [1,100].

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

Список основных обозначений

• Мп — п-мерное евклидово пространство векторов х = (х\, ...,хп), Е^ = {х в Мп I хг ^ О, Щ. Положим М = М1 и М+ = М^;

• Z (Z+) — множество целых (неотрицательных целых) чисел;

• а+ = тах(а, 0) для любого действительного числа а;

• и {а) целая и дробная части действительного числа а;

• \а] — наименьшее целое Ь ^ а;

• а = Ь(тос1 к) — а сравнимо с Ъ по модулю к, т.е. а и Ь дают одинаковые остатки при делении на к. Если к — 1, то пишем а = Ь;

• НОД(а,1,..., ап) — наибольший общий делитель целых чисел а15...,ап;

• е® е М" - единичный вектор вдоль оси ж7;

• е*7 = X) ег, где 7 С {1, ...,гг};

• жт — вектор-столбец, полученный транспонированием вектора х;

• сопуХ — выпуклая оболочка множества X с Мп;

• С% — число сочетаний из п элементов по к;

• Для 6 М" будем писать х >- у, если х лексикографически больше у,

т.е. первая отличная от нуля компонента разности х — у положительна;

к

• ^а, = 0, если I > к, где а, — произвольные действительные числа;

г=1

• \Х\ — число элементов конечного множества Х\

• ■ — знак окончания доказательства.

Список сокращений

• АМ — алгоритм Мартина;

• АРП — алгоритм, основанный на решении последовательности подыгр;

• ВЗ — вспомогательная задача в АРП;

• ЗЛП — задача линейного программирования;

• ЗР — задача о рюкзаке;

• МБР — метод Брауна-Робинсон;

• МВН — метод возможных направлений;

• МЦА — модифицированный циклический алгоритм;

• ПЦА — полностью целочисленный алгоритм;

• ЦА — циклический алгоритм;

• ЦЛП — целочисленное линейное программирование.

ГЛАВА 1

Модификация метода Гомори решения задачи целочисленного линейного программирования

Для решения задач целочисленного линейного программирования (ЦЛП) Гомори сформулировал циклический алгоритм (ЦА), который за конечное число шагов находит оптимальное решение задачи ЦЛП. В данной главе предлагается модификация циклического алгоритма Гомори (МЦА), в которой строятся отсечения более близкие к многограннику ограничений, чем в ЦА. На рис. 1.1 ломаная ОАВСИ задает допустимую область задачи ЦЛП, пунктирная линия СС соответствует отсечению Гомори, а параллельная ей сплошная линия ЯК' — модифицированному отсечению.

Рисунок 1.1. Взаимное расположение отсечений

При поиске такого модифицированного отсечения возникает вспомогательная задача ЦЛП с одним ограничением. В разделе 1.2.1 эта задача

решается алгоритмом пометок, который применяется при поиске пути в ориентированном графе, соединяющем две заданные вершины [38]. В разделе 1.2.2 предлагается другой метод решения вспомогательной задачи, основанный на формуле общего решения линейного диофантова уравнения [42]. В разделе 1.3 рассмотрены другие известные методы решения задачи ЦЛП, а именно: полностью целочисленный алгоритм Гомори (ПЦА) [76], в котором симплекс-таблица на каждом шаге остается целочисленной, и алгоритм Мартина (АМ) [86], в котором отсечение строится специальным способом (отсечение Мартина). В данной работе при построении отсечения Мартина предлагается поиск производящей строки, минимизирующий число преобразований в АМ. В конце главы приведены результаты численного сравнения МЦА с ЦА, ПЦА и АМ.

1.1. Постановка задачи и циклический алгоритм Гомори

Рассмотрим задачу ЦЛП (см. [54, гл. 13])

х0 Е у = 1,..., п + ш, где а73 — целые числа. Множество допустимых решений х = (жь..., хп+т) задачи (1.1) обозначим через Х0. Запишем соответствующую «непрерывную» задачу (отбросим целочисленность переменных э — 1 ,...,п + т)

п

%о = аоо — ^^ &о1х3 —тах

3=1

- (2?0 СЬу \ X 2 ••• 77 } ^ — ***3 ^^

(1.1)

п

(1.2)

Предположим, что множество X допустимых решений непрерывной задачи (1.2) не пусто и ограничено, а целевая функция гсо на X ограничена сверху. Обозначим а0 = (а0х,..., а0п), Аг = (а10, ...,ат0), 9 = (О,..., 0), А2 = (ау)тхп, 1п — единичная п х п-матрица. В качестве симплекс-таблицы задачи (1.1) будем рассматривать расширенную столбцовую таблицу [54, гл. 13]

соответствующую системе уравнений задачи (1.1). Строки матрицы (в —1п) соответствуют тривиальным уравнениям х3 = —(—х3), ] = 1 и на-

чальным небазисным переменным. Столбцы матрицы А с 1-го по п-й соответствуют небазисным переменным. В столбцовой таблице элементарные преобразования (операции замещения) осуществляются над столбцами, что соответствует эквивалентному преобразованию задачи, двойственной к (1.2). Симплекс-таблица А называется прямо (двойственно) допустимой, если столбец А0 = (вАх)1 (строка а0) содержит неотрицательные компоненты. Если симплекс-таблица А одновременно прямо и двойственно допустима, то ее нулевой столбец содержит компоненты оптимального решения задачи (1.2).

Покажем, как строятся отсечения в ЦА [28, гл. 5]. После решения задачи (1.2) симплекс-методом, используя заключительную таблицу, выразим все переменные через небазисные переменные ждг, э = 1,...,п,

^ = еТ -1п ^ а2

/ (п+т+1)х(п+1)

п

.7=1

Выберем в таблице производящую строку с номером

к = 1шп{а[0 ^ Ж, г = 0,.... п + га}

и построим соответствующее отсечение

7?

(1.3)

Вводя новую переменную s, определим отсечение Гомори

7?

s = (1-4)

j=i

Заметим, что для любого решения х Е Xq выполнено сравнение

п

s = -Ко) + ^2{akj}xNj = 0.

j=i

Алгоритм ЦА состоит в следующем. На каждом шаге добавляем отсечение вида (1.4). Делаем шаг по двойственному симплекс-алгоритму, используя в качестве ведущей строку, соответствующую отсечению Гомори (1.4). После вывода из базиса переменной s ведущая строка соответствует ограничению вида 5 = — (—s) и удаляется. При этом таблица остается двойственно допустимой. Добавление отсечений повторяется до тех пор, пока не будет выполнено а\0 ^ 0, i = 0,...,n + m. Если a'lQ на некотором шаге остается отрицательным, следующий шаг двойственного метода производится без добавления отсечения (1.4).

1.2. Модифицированный циклический алгоритм

В МЦА вместо отсечения (1.4) на каждой итерации ЦА добавляется модифицированное отсечение. Покажем, как оно строится. Рассмотрим вспомогательную оптимизационную задачу

Ii

^ZfkjXN, ^ min

* (xNl....,xNn)

(1.5)

^fkjXNj = Л, XNj £ Z+, j = 1, ...,П,

3=1

где fkj — K?}, fk = KJ — дробные части чисел a'k и a'k0. Отметим, что fkj и fk — рациональные числа.

Нетрудно видеть, что минимальное значение целевой функции в задаче (1.5) равно fk + где — некоторое целое число. Заметим, что

¡1* ^ 0, поскольку целевая функция принимает неотрицательные значения и 0 < /к < 1. Так как для любого решения х е Х0 выполнено сравнение в (1.5), то верно неравенство

п

/¿¿я^-^ л+/Л (1.6)

3=1

которое будем называть модифицированным отсечением. Отсечение Гомо-ри (1.3) в ЦА соответствует неравенству (1.6) при // = 0. В следующем примере показано, что, несмотря на то, что модифицированное отсечение строятся более близко к многограннику ограничений, чем в ЦА, существуют примеры, когда оно не содержит ни одного допустимого решения исходной задачи ЦЛП.

Пример 1.1. Рассмотрим задачу ЦЛП

жо = —13(—Жх) — 18(—х2) —» тах

гг3 = 29 + 13(-ж1) + 9(-ж2), (1-7)

ж4 = 24 + 4(-хх) + 15(—ж2), XI, х2, ж3, х4 е Z+.

Заметим, что множество допустимых решений задачи (1.7)

= {(0,0,29,24), (0,1,20,9), (1,0,16,20), (1,1,7,5), (2,0,3,16)}.

По прямому симплекс-алгоритму после операции замещения получим симплекс-таблицу

2125/53 41/53 39/53

73/53 5/53 -3/53

196/159 -4/159 13/159

0 -1 0

0 0 -1

Вектор х* = (73/53,196/159,0,0) является оптимальным решением «непрерывной» задачи (1.7). На первом шаге ЦА нулевая строка таблицы является

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

ß —> min

fi = 41/53а;з + 39/53£4 — 5/53, ц, Х4 € Z+,

получим, что минимум ¡1* = 3 достигается на решении (жз,^) = (4,0). Таким образом, модифицированное отсечение выглядит следующим образом:

s = -164/53 - 41/53(-ж3) - 39/53(-ж4). (1.8)

Заметим, что ни при каком векторе х 6 Xq не выполнено равенство s = 0. Следовательно, отсечение (1.8) не содержит допустимых решений задачи (1.7).

В [10] показано, что если множество решений задачи (1.1) ограничено, то ЦА (соответственно и МЦА) сходится за конечное число шагов.

Для упрощения записи будем использовать обозначения у3 = x^ , j = 1, Сравнение, задающее ограничение в задаче (1.5), запишем как

п

^ ^ fijУз — fit 3 = 1

где 1 > Д, > 0, j = 1, ...,7г, /г > 0. Пусть г — общий знаменатель рациональных чисел и /г. Положим о, = г/у, с = г/г. Теперь задачу (1.5) в новых переменных можно записать в виде

ß —min

(yu....yn,ß)

" (1.9)

азУз = с + г/г, ^ G Z+, j = 1,..., тг, \i G Z+,

где a3,c,r — положительные целые числа, а г > nmx(c, ai,..., ап). Задачу (1.9) можно перефразировать следующим образом: требуется найти минимальное целое д, при котором уравнение в (1.9) имеет решение в неотрицательных целых числах.

Далее будем считать, что множество допустимых решений у = (ух, задачи (1.9) не пусто. Для этого необходимо и достаточно, чтобы

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

ному решению уравнения из (1.9) (см. [15,42,47]) решение А (г,..., г, ^ а3)

где А — подходящее натуральное число. Без потери общности будем предполагать:

й -1 (иначе обе части уравнения в (1.9) сокращаем на (Г);

2. Ни одно из чисел а3 не делит с (иначе в задаче (1.9) минимум ¡1* = 0).

В частности, а3 > 1;

3. Ни одно из чисел а3 не делит другое число аг (иначе полагаем уг = 0).

Пусть ¿1 — наибольший общий делитель чисел ах,...,щ, I — 1 ,...,п. В частности, д,\ = а\. Отметим, что числа и г взаимно простые, поскольку по предположению их наибольший общий делитель с1 = 1. Далее, из уравнения в (1.9) следует, что число <1п делит с + г/л. Поэтому уравнение с1пг = с + г/1 имеет неотрицательное целочисленное решение (г, д). Среди всех таких решений возьмем решение (г0,Мо) с наименьшей второй компонентой. Тогда ¡л = ¿¿о + где г € Заметим, что ^ с1п — 1 (см. ниже теорему 1.3). Кроме того, ¡1* ^ /¿о-

В следующих двух разделах рассматриваются алгоритмы построения модифицированного отсечения.

п

соответствующего однородного уравнения

п

(1.10)

1.2.1. Алгоритм пометок

Рассмотрим алгоритм пометок (АП) решения задачи (1.9). Аналогичный алгоритм применяется в [38, параграфы 9.2 и 16.2] при поиске кратчайшего пути в ориентированном графе, соединяющего две заданные вершины. В процессе его выполнения изменяется список состоящий из помеченных чисел. После некоторого шага список содержит число с+ 77/, где /л* — компонента оптимального решения у* = (у*, задачи (1.9). Пусть к — текущий

номер элемента списка Р. Алгоритм пометок состоит из начального шага и некоторой последовательности общих шагов.

Шаг 1. Полагаем Р = [0], к = 1, Ь = с + г/ло, ц = ц^. Элемент списка 0 помечаем нулем.

Шаг 2. Элемент списка ^ сравниваем с величиной Ъ. При этом могут возникнуть следующие случаи:

1. ^ = Ъ. Алгоритм останавливает работу. Текущее значение ¡1 является искомым ¡1*.

2. ^ > Ь и Рк не является последним элементом списка Р. Увеличиваем к на 1 и повторяем шаг 2.

3. ^ > 6 и - последний элемент списка Р. Полагаем к = 1, величину Ъ увеличиваем на г<1п, а ¡1 — на с1п. Повторяем шаг 2.

4. / = Рк < Ь. Удаляем элемент Рк из списка Р. В конец списка последовательно добавляем непомеченные числа / + Добавленные числа / + помечаем числом /. Повторяем шаг 2.

После завершения алгоритма компоненты у*-, ] = 1 оптимального

решения задачи (1.9) нетрудно найти по пометкам. Отметим, что в ходе алгоритма все элементы списка Р различны, а удаленное из списка число

помечено и не может быть вновь в него включено. Отсюда нетрудно вывести, что алгоритм пометок совершает порядка 0(п(с + гр*)) операций сложения и сравнения чисел (см. [38]). Поскольку величина р* заранее неизвестна, необходимо ее оценить сверху через входные данные задачи (1.9).

Теорема 1.1. Оптимальное решение у* = (у\, ...,?/*,//) задачи (1.9) удовлетворяет неравенствам

1 п

у] ^ г - 1, j = 1, ...,п, -((г-1)5>,-с) .

Г 3=1

Доказательство. Предположим, что при некотором I выполнено неравенство у\ > г. Тогда

п

г + г/.I* > с + гр* = ^^ а3у* ^ air.

з=1

Тогда 1 + // > а^. Отсюда следует, что р* ^ а;. Возьмем решение однородного уравнения (1.10) вида у® = (0,..., 0, г, 0,..., О, а/), где 1-я компонента равна г, и вычтем его из у*. Тогда решение у* — у^ допустимо в задаче (1.9) и имеет меньшее значение целевой функции р — р* — щ, что противоречит оптимальности решения у*. Итак,

У3 < г - 1, j = 1, ...,п.

Отсюда

П 71

гр* = азУ*з - с ^ (г - 1) ^ а, - с.

J=1 3=1

■

Заметим, что при п = 1 оценка р\ величины р* является точной. Действительно, задача (1.9) с ограничением

ау\ = с + (а + с)р,

где а, с> 0 — взаимно простые целые числа, имеет оптимальное решение

у* = {ylp*) = {a + c-l,a-l) 21

и ¡11 = а — 1. При п > 1 оценка /11 груба и будет улучшена в следующем разделе.

Замечание 1.1. Алгоритм пометок решения задачи (1.9) является псевдополиномиальным (см. [38, §16.2]). Действительно, сведем задачу (1.9) к задаче о рюкзаке (ЗР) (см. [42, §5.2]). Введем переменную а = — ц, где /¿1 определено в теореме 1.1. Тогда следующая ЗР эквивалентна задаче (1.9):

су тах

(уи.:.уп,а)

" (1-11)

а3у3 + га = с + ттл, у3 е Z+, 3 = 1,..., п, а е

Известно, что ЗР является КР-полной (см., например, [38, §16.2]). Метод динамического программирования (он же в данном случае алгоритм пометок) решения ЗР (1.11) псевдополиномиален и имеет временную сложность 0((п + 1)(с + г¡11)). Следовательно, алгоритм пометок решения задачи (1.9) также является псевдополиномиальным. Заметим, что не существует полиномиального алгоритма решения вспомогательной задачи (1.9), поскольку сама задача является ЫР-полной.

1.2.2. Алгоритм подбора параметров

Напомним, что ^ = НОД(аь...,а{), I — 1 ,...,п. Построим у^ — — частные решения уравнений

I

^2азУз = I = 1,-,п. (1-12)

Ясно, что у^ — 1. При каждом I = 2,...,п возьмем ^^г^) — решение в целых числах уравнения с^-!^ + щг^ = с^. Заметим, что из предположения 3 раздела 1.2 вытекает, что г® ф 0. Без потери общности будем считать, что ^ 1. Действительно, в противном случае к решению можно

Список литературы диссертационного исследования кандидат наук Шалбузов Камил Джавид О., 2015 год

ЛИТЕРАТУРА

[1] Амвросенко B.B. Ускорение сходимости метода Брауна решения матричных игр // Экономика и математические методы. — 1965. — Т. 1, В. 4. - С. 571-575.

[2] Арутюнов A.B., Жуковский С.Е., Павлова Н.Г. Равновесные цены как точка совпадения двух отображений // Журн. выч. матем. и матем. физ. - 2013. - № 53. - С. 225-237.

[3] Беленький В.З., Волконский В.А., Иванков С.А., Поманский А.Б., Шапиро А.Д. Итеративные методы в теории игр и программировании. — М.: Наука, 1974.

[4] Беллман Р. Динамическое программирование. — М.: Иностранная литература, 1960.

[5] Берзин Е.А. Оптимальное распределение ресурсов и теория игр. — М.: Радио и связь, 1983.

[6] Берзин Е.А. Оптимальное распределение ресурсов и элементы синтеза систем. — М.: Советское радио, 1974.

[7] Борисова Э.П., Магарик И.В. О двух модификациях метода Брауна решения матричных игр // Экономика и математические методы. — 1966. - Т. 2, В. 5. - С. 733-738.

[8] Васильев Ф.П. Методы оптимизации. — М.: Факториал Пресс, 2002.

[9] Васильев Ф.П., Иваницкий А.Ю. Линейное программирование. — М.: Факториал, 2008.

[10] Васин A.A., Краснощеков П.С., Морозов В.В. Исследование операций. — М.: Издательский центр «Академия», 2008.

[11] Васин A.A., Морозов В.В. Теория игр. - М.: МАКС-Пресс, 2008.

[12] Васин A.A., Морозов В.В. Теория игр и модели математической экономики. - М.: МАКС-Пресс, 2005.

[13] Васин A.A., Шумов В.В., Уразов A.C. Об оптимальных стратегиях применения пограничных средств обнаружения. Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. — 2011. — № 2. — С. 30—36.

[14] Виноградов И.М. Основы теории чисел. — М.: Наука, 1981.

[15] Гельфонд А.О. Решение уравнений в целых числах. — М.: Наука, 1978.

[16] Гермейер Ю.Б. Введение в теорию исследования операций. — М.: Наука,

1971.

[17] Турин Л.С., Дымарский Я.С., Меркулов А.Д. Задачи и методы оптимального распределения ресурсов. — М.: Советское радио, 1968.

[18] Давыдов Э.Г. Исследование операций. — М.: Высшая школа, 1990.

[19] Данскин Д.М. Теория максимина и ее приложение к задачам распределения вооружения. — М.: Советское радио, 1970.

[20] Демьянов В.Ф., Малоземов В.Н. Введение в минимакс. — М.: Наука,

1972.

[21] Дрешер М. Стратегические игры. Теория и приложения. — М.: Советское радио, 1964.

[22] Дюбин Г.Н., Суздаль В.Г. Введению в прикладную теорию игр. — М.: Наука, 1981.

[23] Евтушенко Ю.Г. Численный метод поиска глобального экстремума функций (перебор на неравномерной сетке) // Журн. выч. матем. и матем. физ. - 1971. - Т. 11, № 6. - С. 1390-1403.

[24] Емец O.A. Евклидовы комбинаторные множества и оптимизация на них. Новое в математическом программировании. — К.: 1992.

[25] Емец O.A., Устьян Н.Ю. Игры с комбинаторными ограничениями // Кибернетика и системный анализ. — 2008. — № 4. — С. 134—141.

[26] Емець О.О., Ольховська О.В. Розв'язувания комбшаторних задач irpo-вого типу з обмеженнями-переставленнями у обох гравщв: ггерацшний метод // Системш дослщжения та шформацшш технологи. — № 4. — С. 80-93.

[27] Карлин С. Математические методы в теории игр, программировании и экономике. — М.: Мир, 1964.

[28] Корбут A.A., Финкельштейн Ю.Ю. Дискретное программирование. — М.: Наука, 1969.

[29] Ковалев М.М. Дискретная оптимизация. Целочисленное программирование. — М.: Книжный дом «ЛИБРОКОМ», 2011.

[30] Ларин P.M., Плясунов A.B., Пяткин A.B. Методы оптимизации. Примеры и задачи. — Новосибирск: Изд-во Новосиб. ун-та, 2003.

[31] Морозов В.В., Шалбузов К.Д. Метод решения матричных игр специального вида // Ломоносовские чтения: Научная конференция, Москва, факультет ВМК МГУ имени М.В. Ломоносова, 14-23 апреля 2014 г.: Тезисы докладов. - М.: МАКС Пресс, 2014. - С. 30-31.

[32] Морозов В.В., Шалбузов К.Д. Игровая модель распределения ресурсов при защите объекта // Математическая теория игр и ее приложения. — 2013. - Т. 5, В. 4. - С. 66-83.

[33] Морозов В.В., Шалбузов К.Д. О решении дискретной игры распределения ресурсов // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и ки-берн. - 2014. - № 2. - С. 10-16. (Morozov V.V., Shalbuzov K.D. On a solution of the discrete resource allocation game // Moscow University Computational Mathematics and Cybernetics. — 2014. — V. 38, № 2. — P. 37-44.)

[34] Морозов B.B., Шалбузов К.Д. О численном решении матричных игр специального вида // Журн. выч. матем. и матем. физ. — 2014. — Т. 54, № 10. - С. 1557-1562. (Morozov V.V., Shalbuzov K.D. Numerical solution of special matrix games // Computational Mathematics and Mathematical Physics. - 2014. - V. 54, № 10. - P. 1499-1504.)

[35] Моцкин T.C., Райфа X., Томпсон Дж.Л., Тролл P.M. Метод двойного описания // Матричные игры. Сб. статей (ред. Н.Н. Воробьев). — М.: Физматгиз, 1961. - С. 81-109.

[36] Огарышев В.Ф. Обобщение задачи Гросса // В сб. «Кибернетику на службу коммунизму». — 1971. — № 6. — С. 264—283.

[37] Огарышев В.Ф. Смешанные стратегии в одном обобщении задачи Гросса // Журн. выч. матем. и матем. физ. — 1973. — Сер. 13, № 1. — С. 59-70.

[38] Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. — М.: Мир, 1985.

[39] Петросян Л.А., Зенкевич Н.А., Шевкопляс Е.В. Теория игр. — СПб.: БХВ-Петербург, 2014.

[40] Препарата Ф., Шеймос М. Вычислительная геометрия. — М.: Мир, 1989.

[41] Робинсон Дж. Итеративный метод решения игр // Матричные игры. Сборник статей под. ред. H.H. Воробьева. — М.: Физматгиз. — 1961. — С. 110-118.

[42] Саати Т. Целочисленные методы оптимизации и связанные с ними экстремальные проблемы. — М.: Мир, 1973.

[43] Садовский A.J1. Монотонный итеративный алгоритм решения матричных игр // ДАН СССР. - 1978. - Т. 238, № 3. - С. 538-540.

[44] Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование. Учеб. пособие. — М.: Физматлит, 2007.

[45] Строцев A.A. Модифицированный метод Брауна решения матричной игры "неклассического" типа // Экономика и математические методы. — 2001. - Т. 37, В. 3. - С. 106-110.

[46] Сухарев А.Г., Тимохов A.B., Федоров В.В. Курс методов оптимизации. — М.: Физматлит, 2011.

[47] Схрейвер А. Теория линейного и целочисленного программирования. В двух томах. — М.: Мир, 1991.

[48] Фейн У.У. Роль связи в войне. Применение теории игр к задачам военной связи. В кн. [21] - С. 246-259.

[49] Финкельштейн Ю.Ю. Метод отсечения и ветвления для решения задач целочисленного линейного программирования // Изв. АН СССР. Техн. кибернет. - 1971. - № 4. - С. 34-38.

[50] Хохлюк В.И. Алгоритмы целочисленной оптимизации. — Новосибирск: Изд-во Новосиб. ун-та, 1982.

[51] Хохлюк В.И. Параллельные алгоритмы целочисленной оптимизации. — М.: Радио и связь, 1987.

[52] Хохлюк В.И. Прямой метод целочисленной оптимизации. — Новосибирск: Изд-во Новосиб. ун-та, 2002.

[53] Хохлюк В.И. Задачи целочисленной оптимизации (алгоритмы). — Новосибирск: Изд-во Новосиб. ун-та, 1980.

[54] Ху Т. Целочисленное программирование и потоки в сетях. — М.: Мир, 1974.

[55] Червак Ю.Ю. Метод отсечений для дискретных задач // Украинский математический журнал. — 1971. — Сер. 23, № 6. — С. 839—843.

[56] Чижонков Е.В. Итерационное решение матричных игр методами сеточных вариационных неравенств // Журн. выч. матем. и матем. физ. — 2010. - Т. 50, № 8. - С. 1367-1380.

[57] Шалбузов К.Д., Морозов В.В. Об одной модификации метода Гомори // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и киберн. — 2012. — № 1. — С. 3—9. (Shalbuzov K.D., Morozov V.V. One modification of Gomory's Algorithm // Moscow University Computational Mathematics and Cybernetics. - 2012. - V. 36, № 1. - P. 1-7.)

[58] Шалбузов К.Д. О сравнении некоторых методов отсечения для задач целочисленного линейного программирования // Прикладная математика и информатика: Труды факультета ВМК МГУ имени М.В. Ломоносова / Под ред. Д.П. Костомарова и В.И. Дмитриева. — М.: МАКС Пресс. — 2014. - № 45. - С. 123-130.

[59] Шалбузов К.Д. Модификация метода Гомори для решения задач целочисленного программирования // VI Московская международная конфе-

ренция по исследованию операций (ORM2010): Москва, 19-23 октября 2010 г.: Труды. - М.: МАКС Пресс. - С. 260-261.

[60] Шор Н.З. Методы минимизации недифференцируемых функций и их приложения. — К.: Наукова думка, 1979.

[61] Юдин Д.Б., Гольштейн Е.Г. Линейное программирование (теория, методы и приложения). — М.: Наука, 2012.

[62] Balas Е. Disjunctive programming. Properties of the convex hull of feasible points, MSRR № 348, GSIA, Carnegie-Mellon Univ., Pittsburgh, PA. -1974.

[63] Balas E. Disjunctive programming: Facets of the convex hull of feasible points, MSRR № 348, Carnegie-Mellon Univ. - 1974.

[64] Balas E. Disjunctive programming // Annuals of Discrete Mathematics. — 1979. - V. 5. - P. 3-51.

[65] Balinski M.L. An algorithm for finding all vertices of convex polyhedral sets // Journal of the Society for Industrial and Applied Mathematics. — 1961. - V. 9. - P. 72-88.

[66] Balinski M.L. Integer programming: methods, uses, computation // Management Science. - 1965. - V. 12, № 6. - P. 253-313.

[67] Balinski M.L. On recent developments in integer programming // Proceedings of the Princeton Symposium on Mathematical Programming (Princeton, 1967, Kuhn H.W., Editor). — N.J.: Princeton University Press, 1970. - P. 267-302.

[68] Balinski M.L. Some general methods in integer programming // Nonlinear Programming (Abadie J., Editor). - Amsterdam, 1967. - P. 221-247.

[69] Beale E.M.L., Heselden G.P.M. An approximate method of solving Blotto games 11 Naval Research Logistic Quarterly. — 1962. — V. 9, № 2. — P. 65-79.

[70] Bellman R. On "Colonel Blotto" and analogous games // SIAM Review. — 1969. - V. 11, № 1. - P. 66-68.

[71] Blackett D.W. Some Blotto games // Naval Research Logistic Quarterly. — 1954. - V. 1, № 1. - P. 55-60.

[72] Cooper J.N., Restrepo R.A. Some problems of attack and defense // SIAM Review. - 1967. - V. 9, № 4. - P. 680-691.

[73] Freiberg T. The probability that three positive integers are pairwise coprime, unpublished manuscript (2005).

[74] Golomb S.W. A class of probability distributions on the integers // Journal of Number Theory. - 1970. - V. 2. - P. 189-192.

[75] Gomory R.E. An algorithm for integer solutions to linear programs // Recent Advances in Mathematical Programming. Robert L. Graves and Philip Wolfe, Editors. - N.Y.: McGraw-Hill, 1963. - P. 193-206.

[76] Gomory R.E. An all-integer programming algorithm // IBM Research Center. — 1960 January. — Research Report RC-189.

[77] Green T.M. Linear diophantine equation with non-negative parameters and solutions // The Fibonacci Quarterly. - 1968. - V. 6, № 2. - P. 177-184.

[78] Gross O., Wagner R. A continuous colonel Blotto game // U.S. Air Force Project RAND, Research Memorandum - 408. — 1950.

[79] Gross O. Targets of differing vulnerability with attack stronger than defense. — Santa Monica, California: The RAND Corporation, 1950.

[80] Hu J. Pairwise relative primality of positive integers // New York Number Theory Seminar CANT 2012. Tenth Annual Workshop on Combinatorial and Additive Number Theory. CUNY Graduate Center. — 2012.

[81] Hu J. The probability that random positive integers are k-wise relatively prime // arXiv:1208.1537vl [math.NT], - 2012.

[82] Jeroslow R.G. Cutting-plane theory: Disjunctive methods // Annals of Discrete Mathematics. - 1977. - V. 1. - P. 293-330.

[83] Jeroslow R. Cutting-plane theory: Algebraic methods // Discrete Mathematics. - 1978. - V. 23, № 2. - P. 121-150.

[84] Jeroslow R. Cutting-planes for complementarity constraints. MSRR no. 394, GSIA, Carnegie-Mellon University. 1976. A revised and abbreviated version has appeared in SI AM Journal Control and Optimization 16. — 1978. - P. 56-62.

[85] Jeroslow R. An Introduction to the Theory of Cutting-planes // Annals of Discrete Mathematics. - 1979. - V. 5. - P. 71-95.

[86] Martin G.T. An accelerated Euclidean algorithm for integer linear programming // Recent Advances in Mathematical Programming. Robert L. Graves and Philip Wolfe, Editors. - N.Y.: McGraw-Hill, 1963. -P. 311-317.

[87] Moree P. Counting carefree couples // arXiv:math/0510003vl [math.NT], - 2005. arxiv.org/pdf/math/0510003.pdf

[88] Morozov V.V., Shalbuzov K.D. Zero-sum game of resource allocation // VII Московская международная конференция по исследованию операций (ORM2013): Москва, 15-19 октября 2013 г.: Труды. - Т. 1. - М.: МАКС Пресс. - С. 193-195.

[89] Nikoofal M.E., Zhuang J. Robust Allocation of a Defensive Budget Considering an Attacker's Private Information. Risk Analysis. — 2012. — V. 32, № 5. - P. 930-943.

[90] Nymann J.E. On the probability that k positive integers are relatively prime // Journal of Number Theory. - 1972. - V. 4. - P. 469-473.

[91] Randolph P.H., Swinson G.E. The discrete max-min problem // Naval Research Logistic Quarterly. - 1969. V. 16, № 3. - P. 309-314.

[92] Vicki B. Choosing what to protect: Strategic Defensive Allocation against an Unknown Attacker // Create Interim Report under office of Naval Research. — L.A.: Create Homeland security center, 2005.

[93] Von Neumann J. A numerical method to determine optimum strategy // Naval Research Logistics Quarterly. - 1954. - V. 1, № 2. - P. 109-115.

Приложение 1. Решение вспомогательной задачи в модифицированном циклическом алгоритме при п = 1,2

Укажем явную формулу для ц* при п — 1 в задаче (1.9). Будем писать

[[у (mod ш)]] = ж, если х = у (mod т) иО^ж^т-1.

Таким образом, х является остатком от деления у на т.

В замечании 1.1 было показано, что задача (1.9) эквивалентна следующей задаче о рюкзаке:

а —>• max

(г/i,") (П1.1)

am +га = с + гць уъа е Z+,

где pi = г [((г — 1)а\ — c)/rj, а = — р. Так как НОД(а1,г) = d — 1 (см. предположение 1 раздела 1.2), получаем (см. [77]), что максимум в задаче (П1.1) достигается на

с + гц 1

(7* =

- [[- [[(c + r/ii) (mod г)]]И«!)-1 (modai)]], (П1.2)

г

где (р(х) — функция Эйлера. Напомним, что для любого целого положительного х функция Эйлера (р(х) равна числу взаимно простых с х чисел из ряда О, ...,х — 1. Она может быть найдена по формуле

р\х

где произведение берется по всем простым числам р, делящим х. В силу соотношения а = максимальному а соответствует минимальное значение /.г. Таким образом, находим ¡1* = /¿х — а*.

Пусть п = 2. Укажем алгоритм нахождения р* в задаче (1.9), которая в данном случае переписывается следующим образом:

¡1 —» тт

(У1,У2>1*)

(П1.3)

а\У\ + а2у2 = с + гр, ух, ?/2,М е Лемма П1.1. Пусть минимум в задаче (П1.3) достигается на тройке (у*,у1,р*). Тогда р* — наименьшее р, удовлетворяющее неравенству

аг

+ гр /ахЧ^М)-! / ^ а2 Ао \(3л) V ¿¿о

2)

и

* Ух

£¿2

где (¿2 =Н0Д(а1,а2).

с + гр* /'а^^М)-!^ ^ а2у

* У2

с + гр

С + Г^* - а^

а2

(П1.4)

Доказательство. Положим а^ = аа/с^, а.2 = а2/^2- Так как с^ делит с + гр (иначе в задаче (П1.3) не существует допустимых решений), разделим обе части уравнения а\у\ + а2?/2 = с + гр в задаче (П1.3) на Л2. Получим

а!\У\ + «22/2 = (с + гр)/(12.

(П1.5)

Поскольку а^ и а'2 — взаимно простые, при фиксированном р найдем минимальное у1, для которого выполнено уравнение (П1.5). Получим (см. [77])

г(с + гр)а'[<р{а^'1

¿/.1 ШП

¿2

(тос! а'2)

Условие (П1.4) совпадает с неравенством ашт;п ^ (с + гр)/с12. Однако если последнее неравенство выполнено, тогда найдется неотрицательное у2, удовлетворяющее уравнению (П1.5). Таким образом, минимальное р, для которого выполнено агу1т[п < (с + гр)/с12, у2 ^ 0, будет оптимальным в задаче (П1.3). ■

Замечание П1.1. При поиске

"С + гр* /0,1 \ Ч>{а2/^)-\

*

У\ =

(}2 \й2/

тос! — ^2

можно воспользоваться следующим сравнением [77]: для любых натуральных чисел qn i = 1,...,п, выполнено

г " \ in "

(mod m) — П [[^ (mod m)]] (mod m).

i=i

i=i

Приложение 2. Доказательство теорем 2.3 и 2.4

Нам потребуются вспомогательные факты. Положим рг = Л7/х7, i = 1 , ...,п. Определим на Y х У функцию

п г=1

Поскольку для целых у из множества Y выполнено min G(y, у') = 0, далее

y'eY'

будем рассматривать только у £ Y\Y'. Определим на множестве Y функции

Ti(y) = itM> u1(y) = J2M-

1=1 1=1

Покажем, что для любых у £ Y\Y'

U1(y)>B>T1(y).

(П2.1)

Действительно, так как для любого г выполнено \уг~\ ^ уг ^ [уг\, и хотя бы одна компонента уг нецелая, имеем:

п п п

им = > = Я > ^Ы = ЗД.

г=1 г=1 г=1

Складывая все неравенства +1 ^ Г Уг], получим и\(у)—Т\{у) ^ п. Отсюда и из (П2.1) следует, что п - 1 ^ В - Т^у) ^ 1, у £ У\У. Для каждого д = 1, ...,п — 1 определим множества

и

Rn

п

= {г = (rb...,rn) £ Щ. | = q, гг < 1, г = 1,...,гг|.

г=1

Заметим, что для всякого г € Rq существует у е Yq, такое, что выполнено r? = {y>}i г = 1, ...,п. Поскольку Y\Y' = Y\ U ... U Yn_i, получаем

ш = max min G(y, у') = max min G(y, у') = max max min G(y, у').

yeY y'eY' yeY\Y>y'£Y> vy'yy 9=i ...n-i yeYq y'eY' vy'y;

Замечание П2.1. Поскольку множества Yq не являются замкнутыми, некоторые из этих максимумов могут не достигаться, но обязательно найдется q = 1, ...,п — 1, на котором максимум будет достигаться.

Без потери общности будем считать, что р\ > ... ^ рп > 0. Положим

У {у) = Argmin G(y, у').

y'eY'

Лемма П2.1. Для любых векторов у е Y\Y' и у' 6 У {у) выполнены неравенства у[ ^ г = 1 ,...,п.

Доказательство. Действительно, в противном случае найдется такое к, что

п п

Ук ^ \Ук\ "Ь 1- Поскольку J2y[ = Т,Уг = существует такой номер что

7 = 1 7 = 1

у[ < yi. Отсюда у[ ^ [yi\. Возьмем следующую стратегию у'^ е Y' :

'(1) Уг

у',

у'к- 1, i = k, г = 1,..., п.

У[ + 1, г = 1,

Рассмотрим два случая. Пусть у[ = \_yi\ < у\. Тогда

G(y,y') - G(y,y'V) = Рк(ук - y'k)+ + Pi(yi ~ Ы)--РкЫ ~ (Ук -1))+ - Piiyi ~ {Ы\ + 1))+ = Piivi ~ Ы) > о.

Если у[ < [уг\, то

GW) - G(y>2/W) = Рк(Ук ~ У'к)+ + Pi(yi - У[)-

-Pk(yk - (у'к - 1))+ - Piiyi - (vi +1)) = PI > 0.

118

Таким образом, у' £ Y(y) (противоречие). Теорема 2.3. Пусть рг = р, г = 1, ...,п. Тогда

и - p[n2/4j/n.

Доказательство. По условию

п

и = max max min G(y, у') = p max max min Y(у, — yi)+-9=1, .,u-i yeYg y'eY' 9=1,...,77-1 yeYg y'eY' -f

Возьмем

у* € У; = Аг§тахтшС(г/,?/').

уеУд УеУ

По лемме П2.1 для любого у е У (у*) выполнены неравенства у, ^ \у*], г = 1,...,п. Покажем, что существует такой вектор у' е У (у*), что

Уз = \

[И, 3=4 + 1,...,П.

Предположим противное. Тогда для любого у' Е У(у*) существует такой номер к, что у'к < [уЦ. Поскольку Б > Т\(у), найдется номер I, для которого у\ = \у*л > [у!\ • Определим следующий вектор у€ У' :

У-,

'(1) - = <

Уг, г ф к,1,

у'к + 1, i = к, г = 1,..., п.

У[ - 1, г = i,

Тогда

тг п

ЕМ - - ¿(»Г - г/,'(1))+ =

7 = 1 / = 1

= (у1 ~ у'к) + (г/Г - Гг/П)+ - (у1 - (;й +1)) - (г/Г - (ГуЛ - 1)) = Гг/Л - у! > о.

Следовательно, у' У{у*) (противоречие). Итак, для любого у' е У (у*) выполнены неравенства |_у*\ < у'г ^ \у*~\, ъ = 1,...,п. Из соображений симметрии можно считать, что Г1 = {у^} ^ ... > гп = {у^}. Поскольку у* £ У*,

можно считать, что у\ = |~у*~|, г = 1, Таким образом,

п п

ш = о max max min > (у, — у')+ = р max max гь =

г=1 «=9+1

(г - (п - q)q \п2/А\

= р max max ---= р max -= р--—-.

q=l,.. ,n-ll=q+l, ,п I 9=1. ,п-1 П П

Теорема 2.4. При п = 3

(_L

и) = max

+ 1/Р2 1/Р1 + 1/р2 + 1/р^'

Доказательство. Заметим, что для каждого д = 1,2 множество является объединением следующих четырех подмножеств:

У1 9 = (2/ е П 1 ПР1 < p3,r2p2 < P3, П = {Уг}, г = 1,2,3},

у2 9 = {У е Ув 1 npi < РЗ,Г2Р2 > Рз, Гг = 0/»}, ¿ = 1,2,3},

уЗ 9 = (у е П 1 npl РЗ,Г2р2 <C Рз, Гг = {&}, г = 1,2,3},

у4 9 = {у е П 1 npí > РЗ,Г2Р2 Рз, Гг = {г/г}, i = 1,2,3}.

Определим величины

Ц = max min G(y,y'), г = 1,2,3,4.

у y&Y¡ y'eY'

Тогда

а; = max max w*. (П2.2)

9=1,2 »=1,2.3,4 q

Из леммы П2.1 следует, что Y (у) С {уг, i = 1,2,3,4,5,6} при q = 1 и Y (у) С {у7, ¿ = 7, 8, 9} при q = 2, где

i/1 = (Ы, Ы, 1ж1), у2 = (1ж1> Ы, 1ж1), у3 = (bij, Ы, Ы),

у4 = (Ы -1, Ы, Ы), у5 = (Ы, Ы -1, Ы), у6 = (Гт1, Ы, Ы - i),

у7 = (Ы> Ы, Ы), у8 = (М, Ы, Ы), у9 = (ЫЪ Ы, Ы).

120

Имеем (п = {yi}, ¿ = 1,2,3): G(y, У1) = Р2Г2 + Рз?"з, <3(2/, у2) = pin + p3r3, G(y, у3) = pin + p2r2,

G(y,yA) = pi(l + n), G(y,y5) = P2(l + r2), С(у,Л = р3(1 + г3), G(y,y7) = pin, G(y,y8) = Р2Г2, G{y,y9) = p3rs,

Поскольку pi ^ p2 ^ ps > 0, G(y,y4) ^ G(y,y2) и G(y,y5) ^ G(y,yl). Отсюда У (у) С {í/1, 2/2,3/3,2/6>-

такой, что pir* ^ В самом деле, если pir^ < р2г\, то можно определить вектор у*{е) = (yl + е,у2 — £,у\) £ У*, где £ можно увеличить до тех пор, пока не выполнится равенство pir|(e) = р2г2{£). При этом значения функций G(y, у2), G(y,y3), G(y, у6), G{y,y7) и G(y,y9) не уменьшатся. Итак, можно рассматривать г £ для которых pin ^ Р2^2- Отсюда следует, что множество У2 можно отбросить.

Рассмотрим случай q = 1. Для у* £ У* выполнено Y (у*) П {у1, у3, у6} ф 0.

Найдем значение ш{. Заметим, что в этом случае для у* £ У* выполнено У (у*) Я: {у1, У3}- Случаи А и Б соответствуют минимизирующим векторам у1 и у3. Обозначим сг = 1/(1/рх + 1/р2 + 1/р3).

А) Возьмем такие у £ У^, для которых выполнено pxri ^ Р3Г3. Тогда

Покажем, что существует вектор

у* £ Y* — Arg max min

y'eY'

3

max 111111

yeY^: y'eY'

ÍnY^Pi(yi-y?)+ =

reñí:

max (p2r2+ p3r3).

Получаем максимизирующее

и

{Рз(2 - Рз/Pl - Рз/Р2>, 1/РЗ > 1/pl + 1/P2, 2С", 1/рз < 1/pi + 1/Р2-

Б) Возьмем такие у Е У/, для которых выполнено Р3Г3 > piri. Тогда

з

TO XI - УгУ = т£х (Piri + Р2Г2).

Í/Gíj: j/'Gr' z—' r€i?i'

г=1 Рз^РзГз>

Получаем максимизирующее г* = (r^r^rg) = (cr/pi, (т/р2, <т/рз) и pir^+ = 2сг. Отсюда следует, что если 1/рз ^ 1/pi + I/P2, то w} = тах(р3(2 — рз/р1 - Рз/Р2),2а), иначе = 2<т.

Найдем значение а;3. Поскольку в этом случае для любого у* Е У* выполнено Y (у*) = {у1}, то

з

max min V" р?(у, - у[)+ = max (p2r2 + p3r3). убУ]: ij'eY'¿—' rei? 1:

Р\Г1^РЗ>Р2Г2 ?=1 Р\Г\^РЗ^Р2Г2

Получаем

„ , * „ (Рз/Р1,Рз/Р2, 1 - Рз/Р1 - Р3/Р2), 1/рз ^ 1/pi + 1/P2,

г = (rl5 г2, г3) = i

[(Рз/Р1, 1 - Рз/РьО), 1/рз < 1/pi + 1/р2,

и

{Рз(2 - Рз/Р1 - рз/р2), 1/рз ^ 1/pi + 1/р2, Р2(1 - Рз/pi), 1/рз < 1/pi + 1/р2-

Найдем значение ujf. В этом случае для любого у* Е У*, такого, что [у1\ > 1, справедливо Y (у*) = {у6}. Если же \_yl\ = 0, то Y (у*) = {у1}-Пусть |_Уз] ^ 1- Тогда

з

max min V рДтд - у')+ = max (р3 + p3r3). уеУь у'еУ z—' reRi

Р1П^Р2Г2^РЗ 1=1 Р1Г1^Р2Г2^РЗ

При 1/р3 ^ 1/pi + 1/р2 получаем максимизирующее

г* = (г1,г1,г1) = (рз/рьрз/р2,1 - Рз/Р1 - Рз/Рг),

и

Рз + Рз^з = рз(2 - рз/р1 - Рз/Pi)-

Пусть (_2/зJ = 0. Тогда

з

та Y1 ~ Уг)+ = (Р2^2 + РЗГ3).

2/eVi y'eY'< ieRi

При 1/рз > 1/pi + 1/р2 получаем максимизирующее

Г* = {r{Arl) = (pi(l/pi + 1/р2)' p2(l/pi + I/P2)''

и

Р2Г*2 + РЗ^з = 1

I/P1 + I/P2'

Если 1/рз < I/Pi + I/P2, ТО множество {г £ i^} и {р2Г2 ^ Рз} пусто.

Рассмотрим случай q = 2. Для у* G Y* выполнено Y(y*) П {у8,у9} ф 0. Найдем значение иСлучаи А и Б соответствуют минимизирующим векторам у8 и у9 из множества Y(y*).

А) Возьмем такие у eY^, для которых выполнено p2r2 ^ р3г3. Тогда

з

= тах р3г3.

уеУг у eY 7 ед2

>Р212>РзГз >Р2Г2>РЗГЗ

Получаем если 1/р3 < 1/pi + l/ р2, то г* = 2ст/рг, г = 1,2,3, и р3Гд = 2<т, иначе множество {г е .Я^} U {Рг^2 ^ Рзгз} пусто

Б) Аналогично показывается, что если 1/рз < l/pi + l/p2, то справедливо

з

та У2 Pi (у* ~ = 2iJ-

yeY2 y'eY'

Найдем значение cj^. Получаем

з з

sup min V рг{уг - у'г)+ = sup min Y" рг{уг ~ y[)+ =

уеу2 y'eY' ^ уеу2 y'eY' ^

Piri>P3> Р1П>Рз>

= sup p3r3 = sup p2r2.

7€R2 тев2

Если 1/рз < l/pi + 1/р2, ТО

* / * * *\=(Р± 2 ~ ^з/pi__2-рз/р1 \

Г ^'Г2'Гзj VPl' р2(1/р2 + 1/рз)' рз(1/р2 + 1/рз)J

и

* 2 - Рз/Р1

sup Р3Г3 = Р3Г3 = р2г2 = —-——

гев2 1/Р2 + 1/РЗ

РгП^рз^ ^Р2Г2>РЗ"ГЗ

Иначе lim г[ — 1 — Р3/Р2, lim — Р3/Р2, lim 73 = 1, и

I—>00 Z—>оо I—>оо

sup Р3Г3 = lim Р3Г3 = р3.

Р1П>Рз> >Р2Г2>РЗГЗ

Найдем значение В этом случае для любого у* е У* выполнено W) = {У9}- Тогда

з

sup min У2р,(у, - у'У = sup Р3Г3.

Р1П^Р2Г2^РЗ PlH^P2?2>P3

Если 1/рз < l/pi + 1/р2, то г* = = (рз/рь Р3/Р2, 2 - Рз/pi - Р3/Р2) и

sup Р3Г3 = Р3Г3 = рз(2 - Рз/Р1 - рз/р2). гея2

Р1П^Р2Г2^РЗ

Иначе lim г[ = рз/pi, lim r2 = 1 — Рз/Ръ lim Т3 = 1, и

I—>00 Z—>00 Z-400

sup Р3Г3 = lim Р3Г3 = р3.

Таким образом, получим значения и для g = 1,2. Обозначим

1 2

Xi = Т/-■ 1 / 1 = 7/—~ГТ/—,1/ > Хз = Рз(2 - рз/рг - Р3/Р1),

l/pi + I/P2 l/pi + I/P2 + 1/Рз

= 77—7ТТ~> = Ж1 ~ Рз/Pi)-1/Р2 + 1/Рз

Пусть 1/рз < 1/рх + 1/р2- Тогда получаем

Х2 = = и>2 > Х4 = > Х3 = ^2 > Х5 =

Отсюда

и = тах(х2, Хз, Х4, Хъ) = Х2-

Если 1/рз > 1/р1 + 1/р2, то XI = ш} ^ Хз = = > Х2 = Тогда

и = тах(хь Х2, Хз, Рз) = XI •

Поскольку при 1/рз > 1/р1 + 1/р2 и 1/рз < 1/р! + 1/р2 верны соответственно неравенства XI ^ Х2 и XI < Хг, то, объединяя эти два случая, получаем

ш = тах(х1,Х2)-