Решение двух классов дискретных задач исследования операций

• Автор: Шалбузов Камил Джавид О.
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2015
• Место защиты: Москва
• Количество страниц: 125 с. : ил.

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ

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

ГЛАВА 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. Свойства Д-образных функций
3.3. Решение игры в чистых стратегиях
3.4. Использование смешанных стратегий
3.5. Доминирование при поиске максиминных и минимаксных стратегий
3.6. Поиск максиминных и минимаксных стратегий
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА
Приложение 1. Решение вспомогательной задачи в модифицированном циклическом алгоритме при п— 1,2
Приложение 2. Доказательство теорем 2.3 и 2.

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

Шаг 3.3. Пусть [-а'к]3 = а = -а'к^.
Шаг 3.4. Положим
Л = шах А.,-. ї-*'н< о
Пример 1.3. Рассмотрим задачу ЦЛП
жо = —79(—.г'і) — 14(—жо) —ї шах
ж3 = 39 + 2(-ж1) + 7(-х2), (1.26)
ж4 = 35 + 14(-Жі) + 5(—ж2), Х, ж2, ж3) ж4 Є 2+.
Решим ее МЦА и АМ. Начальная симплекс-таблица прямо допустима. По прямому симплекс-алгоритму определим ведущий элемент а4і = 14 и сделаем операцию замещения. В результате получим прямо и двойственно допустимую симплекс-таблицу
/*„ пп,лл шп н л

395/2 79/14 199/
5/2 1/14 5/
0
34 -1/7 44/

(1.27)
Поэтому вектор х* = (5/2,0,34,0) — оптимальное решение непрерывной задачи и N = 4, N2 = 2. Отсюда |Z?| = а44 = 14. Ha первом шаге МЦА (как и в ЦА) нулевая строка таблицы является производящей. Решив вспомогательную задачу
/и min
fi — 9/14ж4 + 3/14х2 — 1/2, ß, х4, ж2 Е Z+,
получим, что минимум ß* = 1 достигается на решении (х4, х2) = (2,1). Таким образом, добавляется отсечение
s = -3/2 - 9/14(—ж4) - 3/14(—ж2).