Курс лекций по линейному программированию

Стратегия оптимальна, если при многократном повторе игры она обеспечивает игроку максимально  возможный выигрыш (минимально возможный  проигрыш), один из которых может выиграть i-ую стратегию из m возможных стратегий, а второй не зная выбора первого, выбирает j-ую стратегию из n возможных. В результате полагают, что первый игрок выигрывает величину А_ij а второй проигрывает эту же величину.

Сопоставим матрицу, которая называется матрицей игры

Строки –  стратегии первого игрока, столбцы  – второго.

Эта матрица  – матрица резервов игры. В зависимости от выбора игроками своих стратегий 

Игра размерностью mxn

Число α=max(min a_ij) называется нижней ценой игры. Это максимум из минимума по строкам.

Число β=mn(max a_ji) – минимум из всех максимумов, взятых по столбцам. Верхняя цена игры.

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

Если α=β=V, то игра называется определенной или игрой с седловой точкой:

Нахождение решения состоит в выборе максимальной (для первого игрока) и минимальной (для второго игрока) стратегии.

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

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

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

Чистая стратегия  – это стратегия, обусловленная  заранее выбранной игроками. Чистая стратегия у каждого игрока конечна (у первого игрока n, у второго m).

Обычно, в случае решения игры в свешанных стратегиях х*=(х₁^*, … , х_n^*) у*=(у₁^*, … , у_m^*), где х*, у* - оптимальные смешенные стратегии, 1-ого и 2-ого игроков соответственно. Под выигрышным понимается величина

^-

максимальный выигрыш математического ожидания. 

Теорема Неймана:

Всякая конечная матричная игра имеет решение  в смешенных стратегиях.

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

Критерий оптимальности – для того чтобы V^* было ценой игры, а х* и у* были оптимальными стратегиями первого и второго игрока соответственно, необходимо и достаточно выполнение следующих условий:

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

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

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

Математически это выражается: 
первый игрок выбирает стратегию х_i, дающую max{min ∑a_ijу_j ∑a_mjy_j}, а второй игрок выбирает стратегию у_j, дающую min{max ∑a_ijx_i ∑a_inx_i}.

Согласно критерию оптимальности, для оптимальной стратегии первого игрока U* выполняется неравенство:

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

В этом случае поделим все неравенство на V, получим:

 Обозначая получаем задачу  линейного программирования.

, используя введенные обозначения переменных условий переходим к

(*)

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

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

            

Лекция № 6: «  сетевое планирование».

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

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

Каждый проект – некоторый ориентированный  график (сетевой график). Для этого  задают:

- перечень всех  операций проекта

- время, необходимое для выполнения каждой операции

- совокупность  операций, которые предшествуют каждой операции. 

Каждая операция представленная в виде дуги ориентированного графа, который построен по правилу:

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

Правило построения сетевой модели:

1. если (i,j) – операция, то в вершину i входят только дуги, которое представляют операции, непосредственно предшествующие данной.
2. Каждой операции соответствует только одна дуга (на одна операция не может появиться в модели два раза).
3. ни одна пара операций не должна определяться одинаково конечными ни начальными событиями (нет кратных дуг). Для того чтобы избежать кратных дуг вводят фиктивные операции с нулевыми затратами.
4. при включении в сетевую модель операции необходимо определить:
1. какие операции необходимо завершить непосредственно перед началом выполнения данной операции.
2. Какие операции непосредственно следуют после завершения данной операции.
3. Какие операции могут выполняться одновременно с данной операцией.

 

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

Свойства ориентированного графика:

1. нет контуров. Контур – это ориентированный цикл.
2. есть одно начальное событие (вершина в которую не входит ни одна дуга) и финальное событие (вершина из которой не исходит ни одной дуги)

 

построение сетевой  модели – первая часть оптимального проекта.

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

Определение: операция называется критической, если задержка начала её выполнения приведет к задержке срока выполнения всего проекта на такое же количество единиц времени.

Определение: операция называется некритической, если время  между ее ранним началом и поздним  завершением больше фактически ее продолжительности (есть резерв т.е. запас для выполнения).

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

Нумерация вершин происходит по алгоритму:

1. начальному событию присваивается № 1
2. присвоить № N любому пронумерованному событию для которого все непосредств. предшествующие события пронумерованы от 1 до N-1.

Определение: непосредственно предшествующее событие  – это событие начальная операция соответствует дугам, входящим в данное событие.

3. нумерация продолжается до тех пор, пока не будет пронумеровано финальное событие.

 

Пример:

  
 
 

Введем понятие  резервов времени. Для этого определим  наиболее ранний из сроков наступления  события и наиболее поздний из сроком завершения события.

Пусть Е(х) –  наиболее ранний из сроков наступления  события х.

L(n) – наиболее поздний из сроков наступления события х, так то допускается своевременное завершение проекта.

Из вычисления наиболее поздних сроков следует, что увеличение наиболее позднего срока завершения проекта L(n) на t единиц времени приведет к увеличению наиболее поздних сроков так же на t единиц. Е(х) – величина пути наибольшей длины оси начального события х.

L(n) – E(x) – длинна пути наибольшей длины от события х к конечному событию.

Рассмотрим операции (х,у). Какое максимальное время можно  выделить для выполнения операции (х,у) без задержки своевременного завершения проекта)?

Операция (х,у) не может начаться раньше, чем Е(х) и закончиться познее, чем L(n), следовательно, для её выполнения может быть выделено время L(y) – E(x), следовательно, максимальная задержка к  выполнения, еще допускающая своевременное завершение проекта =

L(n) – E(x) – t (x,y) ≥ 0. Эта величина называется полным резервом времени операции (х,у). Задержка выполнения операции, полный резерв времени которого = 0 приведет к такой же задержке всего проекта. 

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

Для выполнения этого условия операция (х,у) должна быть выполнена к моменту Е(у), поскольку операция (х,у) начинается не раньше чем Е(х), то на её выполнение без введения дополнительного времени  ограничения на последующие операции проекта можно выделить Е(у) – У(х) единиц времени и тогда величина Е(у) – Е(х) – t(x,y) называется свободным резервом времени операции (х,у). 

Какое максимальное время можно выделить для выполнения операции (х,у) без введения дополнительного времени на операция проекта?

Операция (х,у) должна начаться в момент L(x) как можно позднее для выполнения этого условия, а завершиться как можно раньше в момент Е(у), следовательно, для её выполнения можно выделить Е(у) – L(x) единия времени. Величина Е(у) – L(x) = t(x,y) это независимый резерв времени. Он может быть отрицательным и если эта величина отрицательно, то для своевременного завершения преокта необходимо введение дополнительных временных ограничений на некоторые операции этого проекта.

Полный резерв ≥ свободный резерв ≥ независимый резерв.

Определение: операция называется критической, если все три её резерва равны 0.

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

Свойства критических путей:

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

 

Признак события, принадлежащего критическому пути: если через событие х проходят критические  пути, то наиболее ранние и поздние  сроки этого события равны.