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

Московский государственный университет имени М.В. Ломоносова Факультет вычислительной математики и кибернетики Кафедра исследования операций

Шалбузов Камил Джавид О.

РЕШЕНИЕ ДВУХ КЛАССОВ ДИСКРЕТНЫХ ЗАДАЧ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ

01.01.09 — Дискретная математика и математическая кибернетика

На правах рукописи

АВТОРЕФЕРАТ

диссертации на соискание учёной степени кандидата физико-математических наук

1 3 ПАИ 2015

Москва - 2015

005568505

005568505

Работа выполнена на кафедре исследования операций факультета вычислительной математики и кибернетики Федерального государственного бюджетного образовательного учреждения высшего образования «Московсковский государственный университет имени М.В.Ломоносова»

Научный руководитель: Морозов Владимир Викторович,

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

Официальные оппоненты: Косоруков Олег Анатольевич,

доктор технических наук, профессор, главный научный сотрудник Всероссийского научно-исследовательского института по проблемам гражданской обороны и чрезвычайных ситуаций (Федеральный центр науки и высоких технологий) МЧС России Сигал Израиль Хаимович,

доктор технических наук, профессор, главный научный сотрудник Федерального государственного бюджетного учреждения науки «Вычислительный центр имени A.A. Дородницына Российской академии наук» Ведущая организация: Федеральное государственное бюджетное образовательное

учреждение высшего образования «Российский университет дружбы народов»

Защита диссертации состоится 29 мая 2015 г. в 11:00 на заседании диссертационного совета Д 501.001.44 в Московском государственном университете имени М.В.Ломоносова по адресу: 119991, ГСП-1, Москва, Ленинские горы, 2-й учебный корпус, факультет ВМК, аудитория 685. Желающие присутствовать на заседании диссертационного совета должны сообщить об этом за два дня по тел. (495)939-30-10 (для оформления заявки на пропуск).

С диссертацией можно ознакомиться в Научной библиотеке МГУ. С текстом автореферата можно ознакомиться на официальном сайте факультета ВМК МГУ http://cs.msu.ru в разделе «Диссертации».

Автореферат разослан « 2fr » ¿t^p^ilfj 2015 г.

Ученый секретарь диссертационного совета, д.ф.-м.н., доцент

Шестаков О.В.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

В качестве оптимизационных задач рассмотрены задачи целочисленного линейного программирования (ЦЛП). Для решения задач ЦЛП Гомори сформулировал циклический алгоритм (ЦА)1, который, используя отсечения, за конечное число шагов находит оптимальное решение. Позже им же был предложен полностью целочисленный алгоритм (ПЦА)2, в котором симплекс-таблица на каждом шаге остается целочисленной. Метод отсечений для задачи ЦЛП состоит в добавлении ограничений, не изменяющих множество допустимых целых точек, и последующем решении соответствующих непрерывных задач. Методы отсечения являются одним из классических подходов к решению ЦЛП3. Мартином был предложен алгоритм (AM)4, в котором используется специальный метод построения отсечения. Будем называть его отсечением Мартина. При построении отсечения Мартина в данной работе предлагается поиск производящей строки, минимизирующий число преобразований в AM. В перечисленных алгоритмах возникают ситуации, когда добавленное отсечение задается гиперплоскостью, не содержащей неотрица-

'Gomory R.E. An algorithm [or Integer solutions to linear programs // Princeton - IBM Mathematics Research

Project, Technical Report № 1. November 17, 1958.

2Gomory R.E. An all-integer programming algorithm // IBM Research Center. 1960 January. Research Report

RC-189.

3Xy Т. Целочисленное программирование и потоки в сетях. М.: Мир, 1974.

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

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

В качестве дискретных игровых задач рассмотрены матричные игры специального вида. Алгоритмам решения матричных игр посвящена обширная литература. Отметим метод двойного описания и метод фон Неймана, основанный на решении системы дифференциальных уравнений. В настоящей работе предлагается алгоритм, основанный на решении подыгр (АРП). АРП применяется к дискретному варианту игры «нападение-защита» и к играм комбинаторного типа. В первой игре нападение распределяет средства для прорыва через пункты, обороняемые защитой. Непрерывные игры распределения бесконечно-делимых ресурсов изучались многими авторами5. Особо отметим следующие основополагающие работы. Блэккет6 дал общее определение игры и исследовал игровую модель выбора маршрута поставки ресурса. В диссертации построены явные формулы решений в смешанных стратегиях для моделей Гросса7, Гермейера8 и их обобщения9. Однако дискретная матричная игра распределения штучных ресурсов в общем случае имеет матрицу больших размеров. Способ построения приближенного решения дискретной игры указаны Билом и Хеселденом10. Предложенный в диссертации алгоритм позволяет обобщение на игры с бюджетными ограничениями.

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

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

6BIackett D.W. Some Blotto games // Naval Research Logistic Quarterly. 1954. V. 1. № 1. P. 55-60.

7Gross O., Wagner R. A continuous colonel Blotto game // U.S. air force Project RAND, research memorandum - 408. 1950.

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

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

|0Веа!е E.M.L., Heselden G.P.M. An approximate method of solving Blotto games // Naval Research Logistic Quarterly. 1962. V. 9. № 2. P. 65-79.

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

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

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

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

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

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

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

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

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

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

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

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

В разделе 1.1 рассматривается задача ЦЛП

и соответствующая «непрерывная» задача (обозначим её (1)), в которой отброшено условие целочисленности переменных. Множество допустимых решений х = (х1,...,хп+т) задачи (1) обозначим через Хо. Решая задачу (1) симплекс-методом и используя заключительную столбцовую таблицу, выразим все переменные через небазисные переменные хщ, з — 1 ,—,п,

ц = о-0 4- яяД г = 0,1, ...,п + тп. Выберем в таблице производящую

строку с номером к, где а'кй — первый нецелый элемент нулевого столбца, и

п

¿=1

хп+1 = аго — йцх1 — ... — щпхп, 2 = 1, ..., тп, X] е з = 1 ,...,п + тп,

п

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

п

(2)

3=1

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

п

^ , min ,

^ (3)

Минимальное значение целевой функции в задаче (3) равно {а'ы} + /Л где /х* - некоторое целое число. Так как для любого решения х £ х0, выполнено сравнение в (3), то .верно неравенство

п

> Ы + /Л (4)

з=1

которое будем называть модифицированным отсечением. Отсечение Гомори (2) в ЦА соответствует неравенству (4) при // = 0. Задачу (3) в новых переменных yj = j = 1,..., п, можно записать в виде

ц —> min

(г/ь-.Уп

" (5)

ajyj = с + r/t, yj G Z+, j = 1,..., n, ß e 2,+,

3=1

где a,j,c,r — положительные целые числа, а г > max(c, сц,..., ап).

В разделе 1.2.1 задача (5) решается алгоритмом пометок. Аналогичный алгоритм применяется при поиске кратчайшего пути в ориентированном графе, соединяющего две заданные вершины. Алгоритм совершает порядка . 0(п(с + rß*)) операций сложения и сравнения чисел.

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

1 п

у* < г - 1, з = 1,.., п, /1* < /и = [- ((г - 1) ^ а,- - с)].

Показано, что алгоритм пометок решения задачи (5) является псевдополиномиальным.

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

Пусть ¿1 = НОД(аь...,аг), I = 1 ,...,п. Построим у® = (у1/\ ...,у[1}) - част-

I

ные решения уравнений азУз = I = 1, ...,п. Общее решение диофантова

з=1

уравнения

п

У^ а.]Уз = (6)

3=1

будем задавать формулами Бонда

п

ЕЩ+1 (г). , «г.

'=2 , (7)

Еаг+1 (г). аз-1± • о

где ¿п - произвольные целые числа, а <¿„+1 = ап+1 = 1 по.определению. При з = 1, ...,п - 1 определим функции

......«-^¿^"А

¿=,74-1

где ра = ¿ свд][.г), / = , ...,п. Введем отрезки целых чисел к=1

Л^^+ь ...,«„) = {Гф(^+1,-.*пУ1.-. 3 = 1,...,п- 1-

Теорема 2. Для того чтобы целые числа гь ...,*„ задавали по формулам (7) неотрицательное решение уравнения (6), необходимо и достаточно, чтобы € #¿(¿¿+1, 3 = —— 1> ^ ^ 0.

Теорема 3. Алгоритм подбора параметров сходится за конечное число шагов. При этом справедлива оценка ц* < р,2 + с1п — 1, где

¿¿2 =

— шах „ г з=1,...,п-1

Явная формула для ¿и* прн гг = 1 и алгоритм нахождения ц* при п = 2 в задаче (5) указаны в приложении 1.

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

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

Результаты главы 1 опубликованы в работах [5,6].

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

Чтобы выделить специальный класс матриц А = (ау) тхп в разделе 2.1 рассмотрены вспомогательные задачи (ВЗ) игроков, в которых каждый игрок

находит наилучшую чистую стратегию в ответ на произвольную смешанную

т п

стратегию партнера. Введем обозначения A(p,j) = £2Piaij> A(h<l) = YlaijQj-

i=1 J=1

Рассмотрим ВЗ для каждого игрока. Первый игрок для любой смешанной стратегии q — (qi,--,qn) второго игрока находит чистую стратегию из множества I(q) = {г I ü(g)= шах A(k,q) = А(г,д)}. Второй игрок для любой смешанной стратегии р = (ри—,Рт) первого игрока находит чистую стратегию из множества J(p) = {j I w(p) = min A(p, к) = A(p,j)}.

Предлагаемый алгоритм, основанный на решении последовательности подыгр (АРП), состоит в следующем. Пусть к к-му шагу сформированы подмножества 1к и Jk чистых стратегий игроков (на первом шаге их можно выбрать произвольно, но разумных размеров). Шаг 1. Решается подыгра с матрицей Ак =

Шаг 2. Для оптимальной стратегия рк первого игрока выбирается любая чистая стратегия jk S J(ph)',

Шаг 3. Решается подыгра с матрицей вк = (ay)i6/ti j&jk+i, где jk+1 = jk U {jkh

Шаг 4. Пусть в этой подыгре qk — оптимальная смешанная стратегия второго игрока. В общем случае последовательности оценок v(pk), к = 1,2,..., и v(qk), к = 1,2,..., не являются монотонными. Определим наилучшие верхнюю и нижнюю оценки vk = min ö(gf) = v(qh), vk = max u(p') = v{pt2); Шаг 5. Проверяется неравенство vk - vk ^ е. Если оно выполнено, то величина (vk + vh)/2 является е-приближением для значения игры v, а р*2 и qli -соответствующими ¿-оптимальными стратегиями;

Шаг 6. Если vk - ук > е, то выбирается любая чистая стратегия ik е I{qk), формируется подматрица Ak+l = (а^)шк+itjsJtn, гДе 1>c+l = lk и 0*}> и осуществляется переход к (к + 1)-му шагу.

Алгоритм сходится за конечное число шагов, поскольку на каждом шаге множества 1к и jk увеличиваются, а величины vk и ук соответственно не возрастают и не убывают.

В разделе 2.2 исследуется модель Дрешера дискретной игры «нападение-защита».

В разделе 2.2.1 определяется игра. Пусть А и В - положительные целые числа, задающие количества средств нападения и защиты, распределяемые по п пунктам в соответствии со стратегиями х = (хг,..., хп) и У = (уи—,уп)- Определим сначала непрерывную антагонистическую игру Г = (X, Y, F(x,y)), в которой множества стратегий X и Y нападения и защиты (первого и второго игроков) имеют вид

п п

X = {х е RJ I ]>> - л} и Y = [у € к; | = в},

¿=1 i=l

71

а функция выигрыша нападения F(x,y) = J2MxuVi) задает суммарный эф-

i=l

фект ее взаимодействия с защитой на всех пунктах. Предположим, что каждая функция fi: неотрицательна и непрерывна на [О, А] х [О, В], не убывает и выпукла по хобращается в нуль при Xi = 0, не возрастает и выпукла по yi. Например, функции /»(£¿,2/0 = где а+ = тах(а,0) для действи-

тельного числа а, перечисленным требованиям удовлетворяют. В этом случае будем говорить о модели Дрешера, предложившего следующую интерпретацию функций /¿. Коэффициент Hi > 0 определяет количество средств нападения, которое может уничтожить одна единица средств защиты на г-м пункте, а множитель А, > 0 задает величину ущерба, наносимого единицей средств нападения, прорвавшегося на этом пункте. При щ = 1, г = 1,...,п, получаем модель Гросса, а при Л{ = 1, г = 1 ,...,п, - модель Гермейера. Далее без потери общности будем предполагать, что в модели Дрешера Xj ^ ... > А„, а в модели Гермейера ^ ... ^ цп.

Дискретная игра Г' = (X',Y',F(x,y)} получается из игры Г при дополнительном предположении, что компоненты стратегий игроков являются целыми числами. Множества X' и Y' могут содержать большое число стратегий.

Поэтому в общем случае стандартный прием сведения решения матричной игры к ЗЛП неприменим.

В разделе 2.2.2 сформулировано условие совпадения значения дискретной и непрерывной игр, указана ВЗ для второго игрока, которая сводится к нахождению точки минимума выпуклой сепарабельной функции с использованием критерия Гросса. Обозначим через v, v' значения игр Г и Г'. Для каждого i = 1,...,п определим стратегию нападения для которой = А, х= 0, к ф i. Поскольку функция F(x,y) выпукла по х, при решении игры Г' в смешанных стратегиях первый игрок может использовать только вероятностные распределения р = (р!,...,рп) на множестве г = 1,...,п}. Множество всех смешанных стратегий такого вида обозначим через Р. Отсюда вытекает, что значение игры Г' можно

п

записать как v' = maxminF(p,?/), где F(p,y) = 22piF(xW,y). Посколь-реР уеУ ¿=1

ку в игре Г функция выигрыша F{x,y) выпукла по у, ее значение равно у = min max F(x{-i\y) = max F(x^\y°), а минимаксная стратегия у0 вто-

убУ t=l,...,n i=l,...,n

poro игрока оптимальна. Стратегию у° можно найти с помощью принципа уравнивания Гермейера.

В сделанных предположениях относительно функций /¿(£¿,2/j)> i = 1> — >"> решение игры Г' в смешанных стратегиях может быть найдено с использованием АРП. Далее в этом разделе указаны частные случаи, не требующие применения АРП. Определим множества

vi = {у е y | vi < 1а/tu], г = 1,..,п} , y{ = {у £ Yi | y¿ е Z+,г = 1, ...,п},

y2 = {yey I Vi < \A/ml i = i, ...,n}, Y¿ = {y e y2 | y¡ = i, ...,n}.

Обозначим через y*xi, y2ext множества крайних точек множеств Yi, У2. Нетрудно показать, что y¿ext С У/, i = 1,2. Заметим, что в модели Дреше-ра в сделанных предположениях относительно функций /¿(:c¿,y¿), i = l,...,n, всегда выполнено неравенство v' ^ v. Укажем условие, при котором v' = v.

Представим вектор у0 как выпуклую комбинацию векторов у® € Yfxt с коэффициентами q£ ^ 0, j = 1,..., s, <7i + ... + q° — 1.

Теорема 4. Пусть в непрерывной игре Г модели Дрешера р° — оптимальная смешанная стратегия первого игрокап, а минимаксная стратегия второго игрока у0 е Y\. Тогда (p°,q°,v) — решение дискретной игры Г', где оптимальная смешанная стратегия второго игрока q° состоит в выборе чистой стратегии у® с вероятностью j = 1, ...,s.

Следствие 1. Пусть в модели Гермейера /z¿ = ¡x, i = 1,...,п, а В ^ n[A/pj и п не делит В. Тогда справедливо утверждение теоремы 4.

В разделе 2.2.3 в модели Дрешера указаны алгоритмы поиска нижнего и верхнего значений v' = max min Fix, у) nv'~ min mexF(x.y) игры Г'. В

xeX'yeY' v ' yeY1 xeX' v r

отличие от функции W{x) = min F(x,y), которая является выпуклой, функция W'(x) = mm F(x, у) в общем случае многоэкстремальна на множестве X. Для поиска максиминной чистой стратегии в игре Г' используется алгоритм глобального поиска, основанный на покрытии симплексов правильными симплексами меньших размеров.

Лемма 1. Для любого х',х" s X верно неравенство

W\x') - W'{x") < ¿ \ъ(х[ - x'l)+. (8)

í=i

Правильный симплекс S(A,z) в X с вершинами x¿ = z + Де^', j — 1,...,п, где ej — единичный вектор вдоль оси Xj, зададим целым числом Д е (О, Л] и вектором г = (zi,...,zn), удовлетворяющим следующим условиям: zi + ... + zn — А — Д, zí е Z+, г = 1, ...,п. Из неравенства (8) следует, что функция g(x) = min (W'ixi) + £ Ai(a:í - x{)) является мажорантой функции W на симплексе S(A, z), причем в вершинах симплекса значения функций W и д

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

совпадают. Положим = max([A/nJ, 1). Определим симплексы

Sf = S(A - x(A),z + х(Д)ег), i = 1, п.

Назовем S = {5i,...,5„} стандартным покрытием симплекса S(A,z).

Рассмотрим алгоритм глобальной оптимизации поиска величины г/. Пусть N — наибольшее текущее значение функции W', найденное по некоторому набору точек из X'. В начале алгоритма положим N = max(W'(a;W),..., W'(x^)). Будем просматривать симплексы стандартного покрытия множества X, вычисляя в их вершинах значения функции W', изменяя N и отбрасывая те симплексы, для которых максимум мажоранты меньше N + е, где константа е > 0 задает точность поиска величины г/. Среди оставшихся симплексов возьмем симплекс с максимальным значением мажоранты и произведем для него стандартное покрытие и т.д. Вычисления продолжаются до тех пор, пока все симплексы не будут отброшены.

Теорема 5. Если в модели Дрешера при стандартном покрытии S симплекса S(A,z) при некоторых i и j (г < j) выполнены равенства zi — Zj, Л; = Аj, ßi = ßj, то в алгоритме глобального поиска симплекс Sj можно отбросить.

п

Обозначим и> = max min У) - j/,')+. В качестве мажоранты для сим-

yeY j/eY' ¡=i

плекса S(A,z) с вершинами xj, j = 1 ,...,п, вместо g(x) можно использовать minij(i), max W(xj)+cj).

Теорема 6. Пусть Х\р\ = ... = Апрп. Тогда ш = [n2/4j/п. Теорема 7. При п — 3

W = maX (l/(AlMl) + 1/(АгкУ 1/(А,т) + + !/(«)"

Теоремы 6 и 7 доказаны в приложении 2. Обозначим через Т'п(р) игру Г' в модели Гермейера, в которой /и,- = р, г = 1,...,п.

Теорема 8. Пусть в игре Г' модели Гермейера наименьший коэффициент цп целый. Если в соответствующей игре Т'п(р„) выполнено у'(р,п) = (.А - рпВ)+, то v' = v'(//„), а ж(п) = (О,...,О, А) - максиминная стратегия нападения.

Рассмотрим поиск минимаксной стратегии в игре Г' модели Дрешера. Так как для верхнего значения игры выполнено

v' = mmmaxF(x,y) =max.F(x,y*) = max F(x®,y*) = шах fi{A,y*), yeY' xeX' xeX' i=i,...,n ¿=i,...,n

при поиске минимаксной стратегии у' можно воспользоваться дискретным аналогом принципа уравнивания.

В разделе 2.2.4 АРП применяется для поиска решения игры Г с бюджетными ограничениями, в которой

п п

X = {х e R'; | ^üiXi < A}, Y = {у е Щ I < Bj,

¿=1 ¡=1

где А и В — капиталы первого и второго игроков, используемые для приобретения средств нападения и защиты на г-м пункте по ценам о, и b¡. Здесь А, В, ai, bi € Z, г = 1,гг. Как и выше, игра Г' получается из игры Г в предположении, что компоненты стратегий игроков являются целыми числами. Чтобы применить АРП поиска решения в смешанных стратегиях игры Г', необходимо существенно сократить множество стратегий X' первого игрока. Из монотонности и выпуклости функций f¡ по переменным следует, что первый игрок может ограничиться стратегиями из множества Xext крайних точек выпуклой оболочки множества всех недоминируемых (при покомпонентном сравнении) стратегий из X'. В этом разделе предложен алгоритм построения множества Xext.

В разделе 2.3 АРП применяется к матричным играм комбинаторного типа, где стратегиями игроков являются всевозможные перестановки последовательности 1, В разделах 2.3.1, 2.3.2 и 2.3.3 рассматриваются следующие игровые модели:

1. игра фермера против природы;

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

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

ВЗ для каждого игрока во второй модели сводятся к упорядочиванию чисел, а в первой и третьей моделях - к решению задачи о назначениях. Во всех игровых моделях в разделах 2.2 и 2.3 АРП численно сравнивается с методом Брауна-Робинсон.

Результаты главы 2 опубликованы в работах [3,4]. Третья глава посвящена антагонистической игре нападения против защиты, осуществляющей охрану объекта. Изучаются свойства Z-образных функций, указаны достаточные условия существования решения в чистых стратегиях, обсуждаются условия доминирования, с помощью метода возможных направлений оценивается нижнее значение игры.

В разделе 3.1 определяется игра. Пусть имеется m типов средств нападения и п типов средств защиты. Введем обозначения: А и В — общее количество средств нападения и защиты; а— количество средств нападения и защиты соответственно г'-го и j'-ro типа; рц — вероятность преодоления одним средством нападения г-го типа одного средства защиты j-го типа, pij е [0,1]. Стратегии нападения х = (хь ...,хт) и защиты у — (уи.. .,уп) принадлежат множествам

m п

х - [х е | Y,xi = и Y = {у € ж+ I = в}-i=1 1

Пусть Pij(xi,yj) - вероятность преодоления г-м типом нападения в количестве х{ j-то типа защиты в количестве yj. Положим

Рфг,к) = (1 - (1 -рцГУ1,

если Xi,yj > 0. Будем говорить, что стратегия нападения х преодолела стратегию защиты у, если каждое средство защиты преодолевается некоторым

средством нападения. Вероятность этого события обозначим через F(x,y) и примем за функцию выигрыша нападения. Таким образом, определена антагонистическая игра

Г = (Х, Y, F(x,y) = П П (l-^ite.Vj)))}, jeJ(y) iei(z)

где I(x) = {xi > 0,i = 1, ...,m}, J(y) = {y} > 0, j = 1, ...,n}.

Дискретная игра Г' = (X',Y',F(x,y)) получается из игры Г при дополнительном предположении, что компоненты стратегий игроков являются целыми числами. Функция выигрыша в игре Г в общем случае не является ни выпуклой, ни вогнутой.

В разделе 3.2 изучаются свойства ^-образных функций.

Определение 1. Убывающую функцию f(z), определенную на полупрямой R+, будем называть Z-образной, если /(0) = 1, /'(0) = 0 и lim f(z) = 0.

г-юо

Определим на R+ семейство ¿Г-образных функций

faß(z) = 1 - (1 - cr)(l - ß*) = az + ßz - {aß)\ зависящих от параметров a,ß е (0,1).

Теорема 9. При (a,ß) ф (7,6) уравнение faß(z) = f~;5(z) имеет не более одного положительного корня. Если, к тому же, 7 ^ а., 6 ^ ß (или 7 < а, 5 ^ ß), то уравнение не имеет положительных корней.

Определим на интервале (0, оо) более общие функции

т

fai...am(z) = 1 ~ Iii1 " <*?)>

г—1

зависящие от параметров а,- € [0,1], г = 1,...,т, т > 2. Теорема 10. Яри любых 0 < zj < справедливо неравенство

flUJzi) > /£...<*»• 18

Теорема 11. Пусть ai,ßi € [0,1], г = 1 ,...,т. Тогда при любых z\, z2 > 0 справедливо неравенство

fai...am(zl)fßi-ßm(z2) > min[fai...am(zi + Z2), fß^.ß^Zl + Z2)].

Следствие 2. Пусть € [0,1], i = 1, ...,m, j = 1, ...,n. Тогда для любых Zj > 0, j — l,...,n, справедливо неравенство

n

J[fQlj...cmj(Zj) ^ 1 + + Z„).

j=l

В разделе 3.3 указаны достаточные условия существования решения в чистых стратегиях игры Г'.

Лемма 2. Пусть при некоторых г и j вероятность ру е (0,1). При любом фиксированном yj > 0 функция ln(l — Pij(xi,yj)) переменной х,- строго вогнута, если yj > 1, и линейна, если у,- = 1.

Для каждого i = 1, ...,т определим стратегию нападения х(г\ для которой х-!) = А, х^ = 0, к ф i. Аналогично для каждого j = 1, ...,тг определим стратегию защиты уй\ для которой = В, у^ = 0, к ф j. С использованием следствия 2 доказывается

Теорема 12. Для любой стратегии нападения х € X minF(x, у) = .min

ysY j=l,...,n

Кроме того,

maxF(x,yu)) = max F(x(i),yU)), j = xeX i=l,...,m

Следствие 3. Для любой стратегии нападения х € X' min F(x,y) = min F(x,yü)), maxF(x,j/w) = max F(x(i),yü)), j = 1, ...,n.

J/Si" j=l,...,n ISX' i=l,...,m

Теорема 13. £сли игра с матрицей (F(xw,yü)))mxn шиеет решение в чистых стратегиях, то оно является решением и исходной игры Г'.

В разделе 3.4 строятся оптимальные смешанные стратегии игроков, ран-домизирующие выбор крайних точек множеств стратегий X и Y в игре Г. На их основе построены оценки для значения игры. В разделе 3.5 обсуждаются условия доминирования.

Теорема 14. Пусть 1-я строка матрицы (ру) доминирует k-ю, т.е. pij ^ Pkj, j = 1, ...,п, 1фк = 1, ...,771. Тогда

1. Найдется максиминная стратегия нападения, не использующая к-е средство.

2. Если стратегия у е Y удовлетворяет неравенствам yj ^ 1, j = 1, ...,п, то при нахождении maxF(x,y) нападение к-е средство может не

х€Х

использовать.

Теорема 15. Пусть 1-й столбец матрицы (ру) доминируется ее к-м столбцом, т.е. р^ > ри, г = 1, ...,m, к ф I = 1, ...,п. Тогда

1. Найдется минимаксная стратегия защиты, не использующая к-е средство.

2. Для любой стратегия нападения х е X выполнено неравенство

В разделе 3.6 с помощью метода возможных направлений оценивается нижнее значение и' игры Г'.

Результаты главы 3 опубликованы в работе [2]. Основные результаты работы приведены в заключении.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ, ВЫНОСИМЫЕ НА ЗАЩИТУ

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

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

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

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

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

ПУБЛИКАЦИИ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

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

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

[3] Морозов В.В., Шалбузов К.Д. О решении дискретной игры распределения ресурсов // Вестник Моск. ун-та. Сер. 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.)

[4] Морозов В.В., Шалбузов К.Д. О численном решении матричных игр специального вида // Журн. выч. матем. и матем. физ. — 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.

[5] Шалбузов К.Д., Морозов В.В. Об одной модификации метода Гомори // Вестн. Моск. ун-та. Сер. 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.

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

[7] Шалбузов К.Д. Модификация метода Гомори для решения задач целочисленного программирования // VI Московская международная конференция по исследованию операций (ORM2010): Москва, 19-23 октября 2010 г.: Труды. - М.: МАКС Пресс. - С. 260-261.

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

Напечатано с готового оригинал-макета

Подписано в печать 27.03.2015 г. Формат 60x90 1/16. Усл.печл. 1,0. Тираж 100 экз. Заказ 053.

Издательство ООО "МАКС Пресс" Лицензия ИД N00510 от01.12.99 г. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 527 к. Тел. 8(495)939-3890/91. Тел./факс 8(495)939-3891.