Проверка и корректировка модели.

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

Чрезвычайно ответственный этап операционного исследования. Первоначально задачу формулируют с точки зрения заказчика. Такая постановка никогда не бывает окончательной. Во время анализа исследуемой системы постановка всегда уточняется. На этом этапе роль операций состоит в тщательном исследование объекта, изучении множества факторов, влияющих на результаты исследования процесса.

Формализация задачи.

В самом общем случае математическая модель задачи имеет вид:

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

x – вектор управляемых переменных;

y – вектор неуправляемых переменных;

g_i – функция потребления i-го ресурса

b_i – величина i-го ресурса

Нахождение метода решения.

Для нахождения оптимального решения `х _опт в зависимости от структуры целевой функции и ограничений применяют те или иные методы теории оптимальных решений:

· Линейное программирование, если f и g – линейные функции.

· Нелинейное программирование, если f и g – нелинейные функции.

· Динамическое программирование, если f имеет специфическую структуру, т.е. является аддитивной или мультипликативной функцией от переменных `х и `у:

· Геометрическое программирование, если целевая функция , а

· Стохастическое программирование, когда `у – случайная величина, а вместо функции f (`х, `y) рассматривается ее математическое ожидание Е<sub>у</sub>[f(`х, `y)]

· Дискретное программирование, если на `х и `у наложено требование дискретности (например цело численности).

· Эвристическое программирование применяют при решение тех задач, в которых точный оптимизм найти алгоритмическим путем невозможно из-за огромного числа вариантов.

Проверка и корректировка модели.

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

5. Реализация найденного решения на практике – важнейший этап, завершающий операционное исследование.

Типичные классы задач исследования операций

По содержательной постановке наиболее часто возникают следующие типичные классы задач:

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

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

Часто задачи оказываются комбинированными.

Развернутая форма игры

Теория игр есть теория моделей принятия решений, она не занимается этими решениями как психологическими, волевыми актами. Не занимается она и вопросами их практической реализации. В рамках теории игр принимаемые решения выступают как достаточно упрощенные и идеализированные схемы реальных явлений.

Наши представления об играх связаны с карточными или “салонными ” играми, шахматами, шашками.

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

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

В конце игры игроки получают какой-либо выигрыш, который зависит от протекания игры и окончательной позиции. Это примеры позиционных игр.

Т.о. наше представление об игре определяется наличием 3-х элементов:

1. Чередованием ходов, которые могут быть как личными, так и случайными.

2. Возможной недостаточностью информации.

3. Наличием функция выигрыша.

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

Где А - начальная вершина (позиция), В, С - промежуточные вершины (позиции), Х - окончательная.

Определение. Под позиционной игрой n лиц понимают следующее:

1. Топологическое дерево Г с выделенной вершиной А, называемой начальной позицией игры.

2. Функция выигрыша, которая ставит в соответствие каждый окончательной позиции дерева некоторый n -мерный вектор (для n игроков)

3. Разбиение множества всех неокончательных позиций (т.е. неокончательных вершин) дерева Г на n+1 множество , , …, , которые называют множествами очередности. Множество соответствует началу (может быть связано со случайностью), – множество очередности для 1-го игрока (1-ый уровень от А - см. рис. *), и т.д.

4. Вероятное распределение для каждой позиции из на множестве непосредственно следующих за ней позиций (т.е. из каждой позиции следуют варианты позиций с некоторой вероятностью).

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

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

В этом определении перечислены все элементы игры: условие (1) устанавливает, что имеется начальная позиция; (2) задает функцию выигрыша; (3) разделяет множество неокончательных позиций на позиции с ходом случая () и личные позиции, соответствующие каждому из игроков: (, …, ) (из позиции очередь хода принадлежит игроку ); (4) задает схему рандомизации в каждой позиции случая; (5) разбивает позиции каждого игрока на информационные множества: игрок знает лишь, в каком информационном множестве он находится, но не знает, в какой именно позиции этого множества.

Такая форма задания игры называется развернутой формой.

Нормальная форма игры

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

Определение. Стратегия i -го игрока есть некоторая функция, которая ставит в соответствие каждому информационному множеству этого игрока некоторый индекс из .

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

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

Нас, как и игроков, интересует, какие из стратегий являются наилучшими с точки зрения максимизации доли каждого игрока в выигрыше: i -ый игрок стремится максимизировать i -ю компоненту функции выигрыша.

Т.к., однако, результаты случайных ходов известны только в вероятностном смысле, то естественно рассматривать математическое ожидание функции выигрыша, определенное в случае, когда игроки используют данный n -набор стратегий, т.е данную ситуацию. Поэтому для описания математического ожидания функции выигрыша при условии, что i -ый игрок применяет стратегию , можно использовать следующее обозначение:

Функцию на множестве всех взаимных значений , …, можно выразить либо в форме соотношения, либо в виде n - мерной таблицы n -мерных векторов. В случае n =2 эта запись сводится к матрице, элементами которой являются пары вещественных чисел. Такая n -мерная таблица называется нормальной формой игры.

Пример⁰. Для игры в “Орлянку” нормальной формой игры является матрица

	“Р”	“О”
Р”	(−1, 1)	(1, −1)
О”	(1, −1)	(−1, 1)

Здесь каждая строка представляет стратегию игрока 1, а столбец − стратегию игрока 2.

Пример⁰. Рассмотрим следующую игру. Случайно выбирается целое число z с возможными значениями 1, 2, 3, 4, каждое с вероятностью . Игрок I не зная результата этого хода, выбирает целое число x. Игрок II, не зная ни z, ни х, выбирает целое число у.

Выигрыш определяется следующим образом: , т.е. целью является выбор числа, по возможности близкого к z.

В этой игре каждый игрок имеет 4 стратегии: 1, 2, 3, 4, так как от других чисел мало проку. Если игрок I выбирает 1, а, игрок II − 3, то выигрыш будет равен (2, -2) с вероятностью , (0,0) - с вероятностью и (-2, 2) с вероятностью . Ожидаемый выигрыш тогда равен:

.

Подсчитав все значения, получим таблицу:

	(0, 0)	(−1/2, 1/2)	(−1/2, 1/2)	(0, 0)
	(1/2, −1/2)	(0, 0)	(0, 0)	(1/2, −1/2)
	(1/2, −1/2)	(0, 0)	(0, 0)	(1/2, −1/2)
	(0, 0)	(−1/2, 1/2)	(−1/2, 1/2)	(0, 0)

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

Ситуации равновесия

Определение. Пусть дана игра Г. Говорят, что ситуация (т.е. какой-нибудь n -набор стратегий) равновесна, или, что она является ситуацией равновесия, если для любого и для любого имеет место неравенство

.

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

 

Пример ⁰. Для игры в нормальной форме

 

как , так и являются ситуациями равновесия.

 

К сожалению, не каждая игра обладает ситуациями равновесия. Например, игра в “Орлянку” такой ситуации не имеет.

 

	“Р”	“О”
“Р”	(−1, 1)	(1, −1)
“О”	(1, −1)	(−1, 1)

 

 

Вообще, если игра не имеет ситуаций равновесия, то обычно некоторые игроки пытаются отгадать стратегии остальных игроков, сохраняя собственные стратегии в тайне. Это наводит на мысль, что в играх с полной информацией ситуации равновесия существуют (в конечных играх).

Действительно, справедлива следующая теорема:

Теорема: Любая конечная игра n лиц с полной информацией имеет ситуацию равновесия.

Доказательство.

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

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

.

Но, аналогично получится, если отправляться от ситуации :

.

Из этих двух систем неравенств следует справедливость (2).

Далее, для любого

и для любого

.

Следовательно, является ситуацией равновесия. Аналогично, равновесна и ситуация .

Эта теорема не имеет места для других игр (т.е., только для антагонистических игр с нулевой суммой).

Нормальная форма

Нормальная форма конечной антагонистической игры сводится к некоторой матрице А с числом строк, равным числу стратегий игрока 1 и с числом столбцов, равным числу стратегий игрока 2.

,

где а_ij – величина выигрыша, если 1 -ый игрок выбирает стратегию i, а 2 -ой – стратегию j, – число стратегий первого игрока, – второго игрока.

Ситуация (пара стратегий) будет равновесной тогда и только тогда, когда соответствующий ей элемент а_ij является одновременно наибольшим в своем столбце и наименьшим в своей строке. Такая ситуация, если она существует, называется седловой точкой.

 

Пример ⁰. Матрица игры с седловой точкой: . (*)

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

Величина а_ij представляет собой выигрыш 1 -го игрока при его i -ой стратегии, если 2 -й игрок придерживается своей j -ой стратегии.

1 -й игрок стремится максимизировать а_ij, а 2 -й – минимизировать. Ни один из игроков не знает заранее стратегии противника. А это имеет большее значение для выбора собственной стратегии.

Если матрица игры имеет седловую точку, то очевидно, что 1 -ый игрок будет использовать эту стратегию, даже, если 2 -й игрок её узнает. Иллюстрацией может служить пример *.

Т.е., если игра с седловой точкой, то её нахождение уже есть решение игры, т.к., если игрок 1 -й выберет эту стратегию, то неважно, знает ли это 2 -й игрок.

Доказательство.

Пусть – такая точка из , расстояние которой от минимально. (такая точка существует, т.к. замкнуто.) Положим

, ,

.

Очевидно, что равенство (2) выполняется, поскольку .

Необходимо показать, что имеет место (3). Мы имеем

 

и, следовательно,

Поэтому

Допустим, что существует , для которого

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

Квадрат расстояния от до имеет вид

 

 

Поэтому

При (т.е. при ) имеем

.

Здесь первое слагаемое по предположению не превосходит , а второе больше . Поэтому .

Отсюда следует, что для , достаточно близких к нулю

.

Но это противоречит выбору . Следовательно, для любых условие (3) должно выполняться.

Метод отсечения.

В дальнейшем будут необходимы следующие понятия.

Лексикография.

1°. Говорят, что вектор = (x₁, …, x_n) лексикографически положителен , если

и x_k > 0, где k = min{ j | x_j ¹ 0}

1°°. Говорят, что вектор лексикографически неотрицателен, если , или

1°°°. Говорят, что вектор = (x₁, …, x_n) лексикографически больше вектора , , если

.

Лексикографически не меньше, , если .

Лексикографически отрицателен, , если .

Пусть имеем задачу линейного программирования

, i = 1, 2, …, m (1)

x_j ³ 0, j = 1, 2, …, n.

Под расширенным планом задачи линейного программирования понимают план

Определение План (расширенный план ) ЗЛП называется лексикографически оптимальным (или лексикографическим оптимумом), если для всех расширенных планов имеет место соотношение .

/ l — оптимальный план/

Теорема 1. Если множество оптимальных планов задачи ЛП (1) не пусто и ограничено, то существует лексикографическим оптимумом задачи (1).

(6, 3, 4, 5) ³ (6, 2, 5, 5)

Теорема 2. Если лексикографический оптимальный план задачи (1), то — опорный план.

Пусть вектора условий

— базис опорного плана X.

B = { j ₁, …, j_k } — индексы базисных переменных.

N = {1, …, n } – B — индексы небазисных переменных.

Qⁿ = {0, 1, 2, …, n }

N ° = {0}È N — множество индексов всех небазисных переменных + 0.

Опр. Симплексная таблица

|| x_ij ||, i Î Qⁿ, j Î N °

называется лексикографически нормальной, если

, " j Î N.

/ l — нормальная симплексная таблица/

Теорема 3. Для того, чтобы опорный план задачи (1) был l‑оптимальным, необходимо и достаточно, чтобы нашёлся такой базис B, что симплексная таблица

|| x_ij ||, i Î Qⁿ, j Î N °

является l‑нормальной.

Определение Псевдоплан (расширенный псевдоплан ) задачи (1) называется лексикографически положительным, если соответствующая симплексная таблица является l‑нормальной. /l‑псевдоплан/

Лексикографическая модификация метода последовательного уточнения оценок

Здесь вместо исходной задачи (1) , i =1,2… m, x_j ³ 0, j =1,2… n.

решается её лексикографический вариант. Требуется найти лексикографический максимум расширенного плана при , i = 1, 2, …, m, x_j ³ 0, j = 1, 2, …, n.

Система ограничений определяет допустимый многогранник L. Задачу (1) будем обозначать, как (L, C), где C — вектор целевой функции. (не скал. умн.). А задачу лексикографической максимизации или l ‑задачу . Соответствующая модификация метода последовательного уточнения оценок — l‑метод.

Общая итерация l‑метода описывается следующим образом. Пусть имеется l‑псевдоплан . Ему соответствуют:

B_r — множество индексов базисных переменных;

N_r — множество индексов небазисных переменных;

T_r — симплексная таблица.

			…	– xl	…	–
x0	x00		…	x0 l	…
x1	x10	…	…	…	…	…
X2	x20	…	…	…	…	…
…	…	…	…	…	…	…
xk	xk0	…	…	xkl	…	Xk
…	…	…	…	…	…	…
xn	xn0	…	…	Xnl	…

{ j ₁, …, l, …, j_k } = N_r. Все , j_k Î N_r.

Столбцы таблицы T_r обозначим через , .

Проверяем, является ли таблица T_r допустимой, т.е. выполнено ли условие , i = 1, 2, …, n.

Если является, то — l ‑оптимальный план. Если нет, то ищем переменную x_k, выводимую из базиса, по правилу

Затем отыскивается переменная x_l, вводимая в базис, по правилу

Если среди чисел нет отрицательных, то задача неразрешима. Если такие числа есть, то переходим к новому l‑псевдоплану , которому соответствует B_r+1 = (B_r È{l}) ‑ {k},

N_r+1 = (N_r È{k}) ‑ {l}.

Элементы новой таблицы T_r+1 получаются по следующим формулам:

, i = 0, 1, 2, …, n, (столбец делится)

, " j Î(N_r – { l }) È {0}; i = 0, 1, 2, …, n.

Другими словами, столбец, в котором находится поправляющий элемент , делится на этот элемент и умножается на (‑1). Чтобы получить любой другой столбец новой таблицы, надо к соответствующему старому столбцу прибавить вновь полученный, умноженный на элемент стоящий на пересечении направляющей строки и искомого столбца. Затем повторяется общая итерация. Способ получения l‑нормальной таблицы.

Ищется такое число

вводят x_{n +1}³ 0; , добавляют к таблице. Из базиса выводят x_k, k = n +1,

выводят x_l, R_l = lex min{ R_j | j ÎN}

производят пересчёт и получают l‑нормальную таблицу.

Теорема доказана.

Используя теорему, можно построить целочисленное правильное отсечение, удовлетворяющее условиям 1-4.

Пусть задана целочисленная, недопустимая и L-нормальная таблица.

и пусть для некоторого k (1£k£n) x_k0<0.

Положим M=N,

, так что и получим целочисленное правильное отсечение: , z ³ 0, z-целое.

Построение начальной l -нормальной целочисленной симплексной таблицы

Мы говорили уже, что исходная таблица должна быть целочисленной и L-нормальной. Допустим, что построили таблицу T₀^¢ для задачи целочисленного ЛП:

Если T₀^¢ L-нормальна, то можно переходить к итерациям алгоритма гомори. Если нет, то можно воспользоваться следующим приёмом для получения L-нормальной целочисленной симплексной таблицы.

При условии (**) ищут и находят .

Очевидно, что для всех шагов задачи (1) выполняется .

Следовательно, можно ввести новую переменную , x_n+1³0, x_n+1 – целое.

Строку x_n+1 приписываем снизу к таблице T₀^¢ и берём в качестве направляющей. Направляющим столбцом выбираем . - столбец таблицы T₀^¢, соответствующий небазисной переменной.

Проделывается одна итерация L-метода, вычёркиваем строку x_n+1 и получаем полностью целочисленную и L-нормальную таблицу T₀^¢. В дальнейшем, если переменная x_n+1 вводится в базис, то соответствующая строка не восстанавливается.

Алгоритм.

0-ая итерация. Строится исходная таблица T₀: целочисленная и l-нормальная. Если T₀ является допустимой, то расширенный l-псевдоплан является расширенным оптимальным планом задачи (L^j,C). Если T₀ не является допустимой, то переходим к 1-ой итерации.

p-я итерация. (p³1). Задана целочисленная и L-нормальная, но недопустимая таблица . Столбцы обозначаем . Находим первую по номеру компоненту , нарушающую допустимость таблицы ,

(1)

Если числа , то задача (L^j,C) неразрешима.

Построение целочисленного отсечения в третьем алгоритме Гомори

Если же среди чисел есть отрицательные, то выбираем ведущий столбец :

(2)

и строим целочисленное правильное отсечение:

; x_n+p ³0, x_n+p – целое. (3)

Строка x_n+p приписывается снизу к таблице, принимается за направляющую и проделывается одна итерация L-метода.

Переменная x_n+p – выводится из базиса, а x_l – вводится. Стока x_n+p вычёркивается. Если l³n+1, то строку x_l не восстанавливаем. Получаем новую таблицу:

целочисленную и l-нормальную.

. Если таблица T_p окажется допустимой, то вектор является расширенным оптимальным планом задачи (L^j,C). Если T_p – недопустима, то переходим к (p+1) итерации.

Замечание.

Т. к. направляющий элемент равен (-1) и , то . Из 1 следует положительностьl, т. к. .

Как найти l из условий (4-6). Условие 4 можно переписать следующим образом , или (4’)

Условие (5) также можно упростить. Если , и условие (5) выполняется при любом (положительном) l.

Т.о. достаточно рассматривать те , для которых . Теперь, пусть

Из (2) (т.е. из того, что - l мин-й столбец) следует:

Если h(j)<h(l), то, очевидно, что при любом l

.

Следовательно, достаточно рассмотреть лишь те , для которых и h(j)=h(l).

Обозначим множество таких j через :

Теперь условие (5) можно переписать следующим образом:

(5^')

Если множество - пусто, то условие (5^') не накладывает никаких ограничений на (положительное) l. Допустим, что множество не пусто. Тогда для каждого можно найти такое натуральное число z_j, что

Заметим, что ни при каком z.

Действительно, если , то

Но это невозможно, поскольку направляющие элементы у нее все время равны (-1). Поэтому получим