Содержание к диссертации
Введение
ГЛАВА 1. Модификация метода Гомори решения задачи целочисленного линейного программирования 13
1.1. Постановка задачи и циклический алгоритм Гомори 14
1.2. Модифицированный циклический алгоритм 16
1.2.1. Алгоритм пометок 20
1.2.2. Алгоритм подбора параметров 22
1.2.3. Сравнение алгоритма пометок с алгоритмом подбора параметров 30
1.3. Сравнение модифицированного циклического алгоритма с другими алгоритмами 31
ГЛАВА 2. Решение матричных игр специального вида 41
2.1. Алгоритм решения матричных игр 42
2.2. Дискретная игра «нападение-защита» 45
2.2.1. Постановка задачи 45
2.2.2. Решение дискретной игры в смешанных стратегиях 47
2.2.3. Поиск нижнего и верхнего значений игры 55
2.2.4. Игра с бюджетными ограничениями 67
2.3. Игры комбинаторного типа 73
2.3.1. Игра фермера против природы 73
2.3.2. Соревнование двух фермерских хозяйств 75
2.3.3. Взаимодействие двух сторон на нескольких пунктах 77
ГЛАВА 3. Игровая модель распределения ресурсов при защите объекта 79
3.1. Постановка задачи 79
3.2. Свойства Z-образных функций 81
3.3. Решение игры в чистых стратегиях 88
3.4. Использование смешанных стратегий 94
3.5. Доминирование при поиске максиминных и минимаксных стратегий 96
3.6. Поиск максиминных и минимаксных стратегий 99
Заключение 103
Литература 105
- Алгоритм пометок
- Дискретная игра «нападение-защита»
- Игра фермера против природы
- Использование смешанных стратегий
Алгоритм пометок
При решении непрерывных игр часто используется метод дискретизации. В результате возникают матричные игры. В общем случае матрицы в этих играх могут содержать большое количество строк или столбцов. Для решения матричных игр чаще всего используется прием сведения решения матричной игры к паре двойственных задач линейного программирования (ЗЛП). При этом для ЗЛП больших размеров вместо симплекс-метода целесообразно использовать метод внутренней точки (см., например, [9, с. 298-311]). Но в случае, если матрица содержит более 1010 строк или столбцов, то указанный метод неприменим. В этой главе предлагается метод решения матричных игр (АРП) больших размеров специального вида, основанный на решении последовательности подыгр. Чтобы выделить специальный класс матриц в разделе 2.1 рассмотрены вспомогательные задачи (ВЗ) игроков, в которых каждый игрок находит наилучшую чистую стратегию в ответ на произвольную смешанную стратегию партнера.
В разделе 2.2 исследуется модель Дрешера дискретной игры «нападение-защита». В разделе 2.2.2 сформулировано условие совпадения значения дискретной и непрерывной игр. В этом же разделе указана ВЗ для второго игрока, которая сводится к нахождению точки минимума выпуклой сепара-бельной функции с использованием критерия Гросса.
Помимо решения игры в смешанных стратегиях в модели Дрешера представляет интерес нахождение нижнего и верхнего значений игры, а также максиминной и минимаксной чистой стратегий. В разделе 2.2.3 для поиска максиминной чистой стратегии используется алгоритм глобального поиска. Минимаксная чистая стратегия ищется с использованием дискретного ана лога принципа уравнивания. В разделе 2.2.4 АРП применяется для поиска решения игры с бюджетными ограничениями.
В разделе 2.3 АРП применяется к матричным играм комбинаторного типа, где стратегиями игроков являются всевозможные перестановки последовательности 1, ..., n. В разделах 2.3.1, 2.3.2 и 2.3.3 рассматриваются следующие игровые модели: 1. игра фермера против природы; 2. соревнование двух фермерских хозяйств; 3. взаимодействие двух сторон на нескольких пунктах.
ВЗ для каждого игрока во второй модели сводятся к упорядочиванию чисел, а в первой и третьей моделях - к решению задачи о назначениях. Во всех игровых моделях в разделах 2.2 и 2.3 АРП численно сравнивается с методом Брауна-Робинсон. Вторая модель в [26] решалась МБР. Отметим, что модификации МБР [1,7,45], направленные на ускорение его сходимости, для рассматриваемых матриц больших размеров использовать нельзя, поскольку они требуют дополнительных громоздких вычислений.
Если тройка (p,q,v) является решением матричной игры в смешанных стратегиях, то для приближенного решения игры ищутся значение игры с точностью є 0 и е-оптимальные стратегии игроков р и q} определяемые соответственно из условий v{p) v - є и v{(f) v + є. Отметим, что всегда выполнены неравенства v(p) v v(q).
Предлагаемый алгоритм состоит в следующем. Пусть к к-му шагу сформированы подмножества 1к и Jk чистых стратегий игроков (на первом шаге их можно выбрать произвольно, но разумных размеров). Шаг 1. Решается подыгра с матрицей Ак = (aij)ilkjjk; Шаг 2. Для оптимальной стратегия рк первого игрока выбирается любая чистая стратегия jk є J(pk); Шаг 3. Решается подыгра с матрицей Вк = (atJ)ieI jeJk+1 где Jk+l = Jk U
Шаг 4. Пусть в этой подыгре qk — оптимальная смешанная стратегия второго игрока. В общем случае последовательности оценок v(pk), к = 1,2,..., и v(qk), к = 1,2,..., не являются монотонными. Определим наилучшие верхнюю и нижнюю оценки Шаг 5. Проверяется неравенство vk - vk е. Если оно выполнено, то величина (vk + vk)/2 является є-приближением для значения игры v, а ph и q -соответствующими е-оптимальными стратегиями;
Шаг 6. Если vk -vk є, то выбирается любая чистая стратегия гк є I(qk), формируется подматрица Ak+l = (агз)шк+1 J(.Jk+1, где Ік+1 = Ік U {ік}, и осуществляется переход к (к + 1)-му шагу. Если число строк т невелико, то на любом к-м шаге алгоритма следует взять 1к = {1,...,т}, а матрицу Ак+1 положить равной Вк. При этом верхняя оценка vk = v(qk) не возрастает по к, поскольку число строк матрицы подыгры не меняется, а число столбцов увеличивается. Если число столбцов п невелико, то следует взять Jk = {1,...,п}, а матрицу Вк положить равной Ак. При этом нижняя оценка vk = v(pk) не убывает по к.
Алгоритм сходится за конечное число шагов, поскольку на каждом шаге множества 1к и Jk увеличиваются, а величины vk и vk соответственно не возрастают и не убывают. Напомним МБР [41]. На первом шаге сначала первый игрок выбирает произвольную чистую стратегию гъ Затем второй игрок выбирает любую чистую стратегию
Дискретная игра «нападение-защита»
Доказательство. Если В В1 то для любой стратегии х є X защита в состоянии уничтожить все средства нападения, поскольку В В1 U(x). Следовательно, у = 0. Пусть В : Б2. Для любой стратегии ж є X выполнено неравенство В : Г(ж). Поэтому найдется такая стратегия у є У , что
Теорема 2.6. Пусть в игре Г модели Гермейера наименьший коэффициент fin целый. Если в соответствующей игре Т п{цп) выполнено v (fin) = (А - finB)+, то v = v (fin), а а ) - максиминная стратегия нападения.
Доказательство. Так как в игре Т п(рп) нижнее значение г/(/іп) = (А /inB)+, этот результат достижим и в исходной игре Г . Он не улучшаем, поскольку ЦІ /ІП, г = 1,...,п - 1, и эффективность защиты в игре Г не меньшая, чем в игре Г п(рп). Ш Следствие 2.2. Пусть в игре Г 3 модели Гермейера стратегия х = (О,...,О,ж ,...,ж ) является максиминной. Тогда для нижнего значения v в исходной игре Г модели Гермейера верно xGX XGX Так как первые s — 1 компонента максиминной стратегии х нулевые, то выигрыш W s(x ) достижим для первого игрока и в исходной игре Замечание 2.5. Поскольку в игре Г3 Хг = 1, і = 1,...,п, щ = ... = /is, для сокращения перебора при поиске максимина при покрытии симплекса S(A, z) симплексами Si следует воспользоваться соображениями симметрии (см. теорему 2.2).
Замечание 2.6. Максиминная стратегия х также может быть найдена методом динамического программирования [4,91], позволяющем получать верхние и нижние оценки для г/.
Рассмотрим поиск минимаксной стратегии в игре Г модели Дрешера. Так как для верхнего значения игры выполнено при поиске минимаксной стратегии у можно воспользоваться дискретным аналогом принципа уравнивания ( [10, теорема 9.2]), т.е. использовать следующее достаточное условие: Если для некоторого вектора у1 условие (2.12) не выполнено, то следует перебросить единицу с j-го пункта на 1-й, затем для полученного вектора у2 вновь проверить условие (2.12) и т.д. вплоть до его выполнения на некотором шаге к для стратегии ук = у .
Пример 2.2. Пусть п = 3, А = 75, В = 15, щ = /І3 = 6, /І2 = 5, ЛІ = З, \2 = Аз = 2. Тогда (p }q }v ) - решение в смешанных стратегиях игры Г , где v1 = 4500/43 « 104.65, р = (10/43,18/43,15/43) - распределение на множестве {жШжФжФ}, а q = (4/43,19/86,59/86) - распределение на множестве {(6,5,4), (6,6,3), (7,4,4)}. Заметим, что v = v, поскольку минимаксная стратегия в непрерывной игре у0 = (6.69, 4.53, 3.78) є Yi (см. теорему 2.1). Нижнее и верхнее значения игры Г равны v = 7 и v = ПО, максиминная и минимаксная чистые стратегии х = (1,72,2) и у = (7,4,4). где Aи В - капиталы первого и второго игроков, используемые для приобретения средств нападения и защиты на г-м пункте по ценам щ и Ь{. Без потери общности будем считать числа ДБ,аг,6г, і = 1,...,п, целыми. Действительно, если они рациональные, то неравенства в определении множеств X и У домножим на общие знаменатели чисел а{, і = 1,...,п, А и Ь{, і = 1,...,п, В соответственно. Как и выше, игра Г получается из игры Г в предположении, что компоненты стратегий игроков являются целыми числами. Чтобы применить АРП поиска решения в смешанных стратегиях игры Г , необходимо существенно сократить множество стратегий X первого игрока.
Определение 2.1. Будем говорить, что стратегия х є X доминирует стратегию х" є X , если ж- ж /, г = 1, ...,п. Пусть Хтах - множество всех недоминируемых стратегий из X , а Xext -множество крайних точек выпуклой оболочки conv Xmax. Из монотонности и выпуклости функций fi по переменным ХІ следует, что первый игрок может ограничиться стратегиями из множества Xext.
Без потери общности будем считать, что d = 1. Действительно, если d не делит А} то А можно уменьшить до ближайшего целого А } кратного d, с сохранением множества стратегий X . После этого обе части неравенства а\Х\ + ... + апхп А можно сократить на d.
Предположим, что каждый коэффициент аг ф 1 и не делит другой коэффициент а3. В самом деле, пусть, например, сц = ка2, к є Z. Обозначим Хтах = Хтах П{хєХ хі = 0}, а Xext - множество крайних точек выпуклой оболочки conv Xmax. Тогда Xext = ext у {(ж / о, xl..., ) (х 2,..., ) Є Xext и к делит ж }. Итак, множество Xext строится по множеству Xext. Дальше будем считать, что 1 а\ ... ап. Теперь займемся вопросом разрешимости в Z+ (т.е. в целых неотрицательных числах) уравнения
Рассмотрим алгоритм построения множества Xext. Пусть Xxt — множество крайних точек выпуклой оболочки convX , а Л - наибольшее из чисел a{dj — щ — a,j, і j. При A А на всех ребрах симплекса ХА существуют точки из множества Х А. Для каждого ребра [(А/аг)е\ (A/a eJ] симплекса ХА строим на нем крайние точки жу и х г из ХА\ имеющие соответственно максимальные г-ю и j-ю компоненты. При этом компонента х- равна наименьшему числу Xj є Z__, удовлетворяющему сравнению близкие к вершинам (А/аг)ег симплекса ХА. Если Аг А , то по аналогии с предыдущим строим на ребрах симплекса ХАІ точки из ХАx t С XAxt и симплексы, близкие к вершинам симплекса XAV В противном случае перебором строим все множество ХАt. Процесс продолжается до полного просмотра всех возникающих симплексов и завершается построением множества Xext (см. рис. 2.3). (А/аи ,0,0)
Таким способом находятся множества Xfjl5 ...,Xfja1+1. Отметим, что симплекс ХА-Я1 рассматривать не нужно, поскольку каждая точка х є ХА-Я1 доминируется точкой (жі + 1,ж2,...,Жп) Є ХА. В каждом из множеств Xft отбрасываются точки, доминируемые выпуклыми комбинациями точек из мно l,...,ai - 1. Оставшиеся недоминируемые точки образуют множество Xext.
Следующая постановка является обощением игры из [26]. Фермер (первый игрок) имеет т участков земли разных площадей и плодородностей. Обозначим через st долю площади /-го участка в общей площади S. Тогда и без потери общности si s2 ... sm 0. Фермер намеревается засеять участки т видами сельскохозяйственных культур по одному виду на каждом участке. Природа (второй игрок) реализует одно из п погодных условий. Если фермер засеет г-й культурой 1-й участок, то при j-м погодном условии его прибыль с 1-го участка составит величину sib S. Стратегия фермера состоит в выборе тг = (тг(1), ...,тг(ш)) - перестановки последовательности 1, ...,т, означающей, что г-й культурой засевается тт(г)-й участок. Тогда прибыль (выигрыш) фермера с единицы общей площади равна
Игра фермера против природы
Об использовании смешанных стратегий в непрерывной модели рассматриваемой игры см. [32]. Данный раздел показывает, что в дискретном случае нахождение оптимальной смешанной стратегии встречает довольно серьезные затруднения. Ограничимся для нападения и защиты смешанными стратегиями специального вида. Пусть (р = (ірі} і = l,...,m) — смешанная стратегия нападения, где ( — вероятность выбора чистой стратегии х \ Аналогично определяется смешанная стратегия защиты ф = (ifjj} j = 1,...,п) — вероятностное распределение на точках у \ j = 1,...,п. Множества всех смешанных стратегий нападения и защиты указанных видов обозначим соответственно ФиФ. Множества всех смешанных стратегий первого и второго игроков обозначаются, как и раньше, через Р и Q соответственно. Положим h = C +A_v линейна по у. Поэтому функция F(x ,y) выпукла по у. Следовательно, нахождение минимума во вспомогательной задаче АРП для второго игрока сводится к нахождению минимума выпуклой функции на множестве У. Его можно найти с помощью критерия Гросса ( [10, теорема 9.3]) (частный случай применения критерия указан в конце предыдущего раздела). В качестве начального у1 є У можно взять вектор, полученный округлением компонент стратегии
Для поиска минимума у є Y выпуклой функции f (p,F(x \y) целесообразно использовать МВН [8,30,60].
Для нахождения верхней оценки w необходимо в явном виде решить матричную игру, содержащую т строк и d столбцов. Пример 3.1 показывает, что величину нельзя брать в качестве альтернативной верхней оценки значения v игры Г. Рассмотрим нахождение w и w в игре Td с диагональной матрицей (Pij)mxm, которая была определена в конце предыдущего раздела. Возьмем произвольную стратегию у є У с двумя положительными компонентами. Для нее выполнено F(x \y) = 0, і = l,...,m. Тогда для любого (р є Ф вы полнено F( p,y) = 0. Отсюда
Для произвольной фиксированной стратегии єФ максимум по х последней суммы во вспомогательной задаче первого игрока в АРП ищется методом динамического программирования. Доминирование при поиске максиминных и минимаксных стратегий При поиске максиминных и минимаксных стратегий следует использовать соображения доминирования. Теорема 3.6. Пусть 1-я строка матрицы {рг]) доминирует k-ю, т.е. щ pkj, j = l,...,n, \фк = l,...,m. Тогда 1. Найдется максиминная стратегия нападения, не использующая к-е средство. 2. Если стратегия у є У удовлетворяет неравенствам у3 1, j = 1,...,п, то при нахождении maxF(x}y) нападение к-е средство может не
Из условия доминирования вытекает, что Лу Xkj, j = 1, ...,п. Пусть ж0 є X - максиминная стратегия нападения, удовлетворяющая условию х0к 0. Определим стратегию х со следующими компонентами: 1. Найдется минимаксная стратегия защиты, не использующая к-е средство. 2. Для любой стратегия нападения х є X выполнено неравенство F(x,yW) F(x,yW). Доказательство. Докажем первое утверждение. Возьмем произвольную стратегию нападения х є X и положим щ = 1 - Щ, і = 1, ...,m, j = 1, ...,n. Тогда aijfe = 1 - \ 1 - Af/ = c , і = 1, ...,m.
Обсудим применение метода возможных направлений (МВН). По лемме 3.2 функции gj(x), j = 1,...,п, строго вогнуты на множестве X и МВН найдет лишь точку локального минимума функции max а Ах). Поэтому ми j=1,...,n нимизацию следует повторять, начиная из нескольких начальных точек. Укажем эти начальные точки. Пусть х? — точка максимума функции gj(x) на множестве X, j = 1, ...,п. По лемме Гиббса она удовлетворяет системе уравнений
При этом вектор & имеет положительные компоненты. Произведем симпли-циальное разбиение множества X, т.е. разобьем его на симплексы размерности т — 1, имеющие попарно непересекающиеся внутренности и вершинами которых служат точки из множества
Для этого возьмем точку х1 и разобьем множество X на т симплексов, имеющих общую вершину в точке х1. Если какой-нибудь из построенных симплексов содержит внутри точку хА то разобъем его на т симплексов, имеющих общую вершину в точке xj и т.д. (см. рис. 3.2b). В качестве начальных точек для МВН следует взять центры построенных симплексов. Выбор величины шага вдоль направления убывания и условия остановки можно взять те же, что и в МВН [8,20]. которую, в свою очередь, можно решить МВН, поскольку функции f(x,u) и gj(x)-u, j = l,...,n, являются гладкими (см. [8, C. 269]).
Отметим, что минимаксную стратегию в игре Г следует искать, используя минимизацию по сетке, заданной на Y , сгущая сетку в окрестностях точек минимума [20]. Нижнее и верхнее значения, максиминная и минимаксная стратегии игры Г, найденные по сетке, соответственно равны г/ = 0.0448, г/ = 0.169, ж = (3,5,0) и у = (2,3,3). Поскольку выполнено mm( F(x{1\y) + ( №(2),v)) = 0.0917 г/, где = 0.57, ( = 0.43, нападению в данной игре целесообразно использовать смешанную стратегию (р = ((/ (/ О), в которой с вероятностями ц \ и Lp\ выбираются чистые стратегии (8,0,0) и (0,8,0).
Основные результаты диссертационной работы состоят в следующем.
Предложена модификация циклического алгоритма Гомори, имеющая при небольшом числе переменных более высокую скорость сходимости, чем ряд известных алгоритмов отсечений.
Разработан алгоритм подбора параметров для решения вспомогательной задачи, возникающей при поиске отсечения в модифицированном циклическом алгоритме.
При построении отсечения Мартина предложен поиск производящей строки, который минимизирует число преобразований в алгоритме Мартина.
Приведены результаты численного сравнения циклического алгоритма Гомори, полностью целочисленного алгоритма Гомори, модифицированного циклического алгоритма и алгоритма Мартина.
Предложен метод решения матричных игр больших размеров специального вида, в которых существует быстрый алгоритм нахождения наилучшей чистой стратегии для каждого игрока в ответ на произвольную смешанную стратегию партнера. Алгоритм был применен к модели Дрешера игры «нападение-защита» и к играм комбинаторного типа, в которых стратегиями игроков являются всевозможные перестановки последовательности 1, ..., m. Приведены результаты численного сравнения предложенного алгоритма с методом Брауна-Робинсон.
Исследована модель Дрешера дискретной игры «нападение-защита». Сформулировано условие совпадения значения дискретной и непрерывной игр. Найдены максиминные и минимаксные стратегии.
Сформулированы условия существования решения антагонистической игры нападения против защиты, осуществляющей охрану объекта, в чистых и смешанных стратегиях. Исследованы свойства Z-образных функций, на основе которых разработаны методы поиска максиминных и минимаксных стратегий.
Использование смешанных стратегий
Например, функции /г(хг}у = Хг(хг - ціУ + перечисленным требованиям удовлетворяют. В этом случае будем говорить о модели Дрешера, предложившего в [21] следующую интерпретацию функций ft. Коэффициент цг О определяет количество средств нападения, которое может уничтожить одна единица средств защиты на г-м пункте, а множитель А; 0 задает величину ущерба, наносимого единицей средств нападения, прорвавшегося на этом пункте. При fa = 1, і = 1,...,п, получаем модель Гросса [78], а при Хг = 1, і = 1,...,п, - модель Гермейера [11,12]. Далее без потери общности будем предполагать, что в модели Дрешера Аі ... ) Ап, а в модели Гермейера /ii ... цп.
Дискретная игра Г = (X ,Y ,F(x,y)) получается из игры Г при дополнительном предположении, что компоненты стратегий игроков являются целыми числами. Множества X и Y могут содержать большое число стратегий. Поэтому в общем случае стандартный прием сведения решения матричной игры к ЗЛП неприменим. 2.2.2. Решение дискретной игры в смешанных стратегиях А 3 = h О, j ф г, состоящую в концентрированном ударе по г-му пункту. Покажем, что в игре Г любая стратегия х = (жі,...,жп) є X первого игрока доминируется смешанной стратегией р = (хл/А, ...,жп/Л), выбирающей х с вероятностью рг = ХІ/А, і = 1,...,п. Действительно, из выпуклости функции F(x,y) по х следует, что для любой стратегии у є Y справедливо неравенство F(p,y) F(x,y). Поэтому при решении игры Г в смешанных стратегиях первый игрок может использовать только вероятностные распределения р = (ри...,рп) на множестве {х \ і = 1,...,п}. Множество всех смешанных стратегий такого вида обозначим через Р. Отсюда вытекает, что значение игры Г можно записать как а минимаксная стратегия у0 второго игрока оптимальна (см., например, [11, с. 54]). Стратегию у0 можно найти с помощью принципа уравнивания Гермейе-ра [10]. Сформулируем его для данного случая. Пусть без потери общности /і(ДО) ... /„(ДО). Тогда для того чтобы стратегия у0 была минимаксной в игре Г, достаточно выполнения следующего условия: найдутся такие число Си номер к є {1,...,п}, что Если к = п, то последние соотношения отсутствуют. Перебирая последовательно к = 1,...,п, найдем систему (2.2), имеющую решение относительно уг, г = 1,...,п, и С. При этом С = v.
Решим игру Г в смешанных стратегиях в сделанных предположениях относительно функции выигрыша нападения F{x,y). Рассмотрим ВЗ для второго игрока. Как было указано выше, нападение может ограничиться использованием вероятностных распределений на множестве стратегий {xSl\ і = 1,...,п}. Таким образом, матрица игры содержит п строк и С в_х столбцов.
Замечание 2.1. В сделанных предположениях относительно функций /І(%І,УІ), і = l,-",w, решение игры Г в смешанных стратегиях может быть найдено с использованием АРП. В самом деле, при решении игры Г в смешанных стратегиях первый игрок может ограничиться смешанными страте гиями из множества Р. Поэтому в матрице игры Г можно оставить только п строк, соответствующих стратегиям х 1\ і = 1,...,п. Тогда поскольку каждая функция fi удовлетворяет указанным на с. 46 предположениям, то для любой смешанной стратегии р первого игрока нижняя оценка может быть найдена с использованием критерия Гросса для точки минимума выпуклой сепарабельной функции. При этом в алгоритме в качестве начального приближения целесообразно взять вектор, полученный округлением компонент минимаксной стратегии у0 игры Г. также находится по критерию Гросса, а для вектора частот q (стратегия уг применялась вторым игроком с частотой qr, г = 1,...,«;) первый игрок выбирает чистую стратегию xSl\ где і берется из множества
Обозначим через 7xt, У2ext множества крайних точек множеств Yu Y2. Для модели Дрешера укажем условие, при котором v = v.
Теорема 2.1. Пусть в непрерывной игре Г модели Дрешера р - оптимальная смешанная стратегия первого игрока, а минимаксная стратегия второго игрока у0 є Yh Тогда (p}q}v) - решение дискретной игры Г , где оптимальная смешанная стратегия второго игрока q состоит в выборе чистой стратегии у с вероятностью , j = l,...,s.
Доказательство. Отметим, что оптимальная стратегия первого игрока р была построена Огарышевым в [37]. Нетрудно показать, что Yfxt с Y . Используя теорему Каратеодори [46], представим вектор у0 как выпуклую комбинацию векторов у є Yxext с коэффициентами q? 0, j
Замечание 2.2. Для нахождения стратегии q необходимо построить все вершины многогранника Y\. Это можно сделать, используя симплекс-метод для ЗЛП с двусторонними ограничениями на переменные [10, с. 75]. Другие алгоритмы построения Yfxt можно найти, например, в [40,65].
Рассмотрим алгоритм глобальной оптимизации поиска величины г/. Аналогичный алгоритм, названный методом покрытий, применяется в [46, глава 2, 2] при поиске глобального экстремума функций одной переменной, удовлетворяющих условию Липшица. Пусть N - наибольшее текущее значение функции W, найденное по некоторому набору точек из X . В начале алгоритма положим N = max 1)), ...,W (x )). Будем просматривать симплексы стандартного покрытия множества X, вычисляя в их вершинах значения функции W , изменяя N и отбрасывая те симплексы, для которых максимум мажоранты меньше N + е, где константа є 0 задает точность поиска величины г/. Среди оставшихся симплексов возьмем симплекс с максимальным значением мажоранты и произведем для него стандартное покрытие и т.д. Вычисления продолжаются до тех пор, пока все симплексы не будут отброшены. Если коэффициенты А», рц, і = 1, ...,п, целые, то при є = 1 после завершения работы алгоритма получаем точное значение v = N. Действительно, в этом случае значение W (x) является целым, и N достигается на некотором векторе х. Тогда для любого симплекса S(A,z), с максимальным значением мажоранты, выполнено