Постановка задачи о назначениях

14Решение игры в смешанных стратегиях путем сведения к задаче линейного программированияПусть платежная матрица игры не содержит седловой точки, следовательно, игра решается в смешанных стратегиях.Будем считать, что все элементы платежной матрицы неотрицательны. Если это не так, то можно ко всем элементам матрицы добавить некоторое достаточно большое число L, переводящее платежи в область неотрицательных значений. При этом цена игры увеличится на L, а смешанные стратегии игроков не изменятся. Если все выигрыши игрока А неотрицательны, то можно принять, что средний выигрыш g > 0.Применение игроком А оптимальной смешанной стратегии =
= (p₁, p₂, …, p_m) гарантирует ему, независимо от поведения игрока В, средний выигрыш, не меньший цены игры (g).Допустим, что игрок А применяет свою оптимальную стратегию , а игрок В – свою чистую стратегию В_j. Тогда средний выигрыш (математическое ожидание выигрыша) игрока А можно рассчитать по формуле

.Учитывая, что g_j не может быть меньше цены игры g, можем записать нижеприведенные условия: .Разделив левую и правую части этого неравенства на g > 0, получим следующее:

.

(3.5)

Введем новые обозначения:

.

(3.6)

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

,

(3.7)

где все x_i ³ 0 ( ), так как p_i ³ 0, g > 0.Компоненты вектора p являются вероятностями событий, образующих полную группу. Поэтому они удовлетворяют следующему условию: .Учитывая соотношение (3.6), получим следующее равенство:

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

.

(3.8)

Таким образом, задача решения матричной игры сводится к задаче линейного программирования, в которой требуется найти неотрицательные значения переменных x_i ( ), минимизирующие линейную функцию (3.8) и удовлетворяющие ограничениям (3.7):

;

Решив данную задачу, найдем цену игры по формуле

.

(3.9)

Вероятности применения игроком А его чистых стратегий рассчитаем по следующей формуле:

( .

(3.10)

Для определения смешанной стратегии игрока В нужно решить двойственную задачу:

;

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

.Вероятности применения игроком В его чистых стратегий рассматриваются по формуле

.

(3.11)

15Игры с природой. Критерии выбора оптимальных стратегий Игра с природой – это такая игровая модель, в которой один из участников безразличен к результату игры. Под термином «природа» понимают всю совокупность внешних обстоятельств, в которых сознательному игроку приходится принимать решение (погодные условия, спрос на рынке, состояние валютной биржи и т. Д).В играх с природой степень неопределенности при принятии решения сознательным игроком возрастает. «Природа», будучи безразличной в отношении выигрыша, может реализовать такие стратегии, которые выгодны сознательному игроку. Поэтому в таких играх решение принять сложнее, а выиграть можно больше.Игра с природой задается платежной матрицей, в которой строки соответствуют стратегиям сознательного игрока, а столбцы – состояниям природы.Критерий БайесаИногда на основе данных статистических наблюдений можно определить вероятности состояний природы, например: .Причем и , так как все состояния природы составляют полную группу событий.Среднее значение (математическое ожидание) выигрыша , которое получит игрок А при применении им стратегии A_i, можно рассчитать по формуле Согласно критерию Байеса, в качестве оптимальной выбирается та из стратегий A_i, которая соответствует максимальному математическому ожиданию выигрыша.

.

(3.12)

Критерий Байеса-ЛапласаЕсли можно считать, что все состояния природы равновероятны,
т. е. удовлетворяют следующему условию: ,

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

.

(3.13)

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

.

Критерий Вальда выражает позицию «крайнего пессимизма», и принимаемое решение носит перестраховочный характер.Критерий Сэвиджа (минимаксного риска)На основе платежной матрицы можно рассчитать соответствующую матрицу рисков игры. Риском называется разность между максимально возможным при данном состоянии природы выигрышем и тем выигрышем, который будет получен при применении стратегии А_i. Максимальный выигрыш при состоянии природы П_j (максимум в j-м столбце) обозначим b_j:

.

Риск игрока А при применении им стратегии A_i в условиях П_j определяется по следующей формуле:

.

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

.

Этот критерий также соответствует позиции крайнего пессимизма, но здесь пессимизм понимается в ином свете: рекомендуется всячески избегать большого риска при принятии решений.Критерий ГурвицаОптимальной считается чистая стратегия А_i, найденная из следующего условия:

где l – коэффициент пессимизма, принимающий значения 0 £ l £ 1.При l = 1 критерий Гурвица превращается в критерий Вальда (критерий «крайнего пессимизма»), а при l = 0 – в критерий «крайнего оптимизма», когда рекомендуется выбирать стратегию, обеспечивающую самый большой выигрыш. При 0 < l < 1 получается нечто среднее между тем и другим. В связи с этим критерий Гурвица называют также критерием «пессимизма–оптимизма».Величина l выбирается исходя из опыта и здравого смысла. Чем ответственнее ситуация, тем ближе к 1 выбирается l.

16Общие понятия и построение сетевого графика Метод сетевого планирования и управления (СПУ) используется при планировании сложных комплексов взаимосвязанных работ. Анализ сетевой модели позволяет решить следующие задачи:четко выявить взаимосвязь различных этапов проекта, условия начала тех или иных работ;определить срок выполнения проекта;выявить возможности задержки начала каждой работы или удлинения срока ее выполнения;оптимизировать время выполнения проекта или ресурсы, требуемые для его выполнения.сетевой график – графическая модель некоторого комплекса взаимосвязанных работ (проекта или производственного процесса). Сетевой график отражает логическую взаимосвязь и взаимообусловленность входящих в него работ. С математической точки зрения сетевой график представляет собой ориентированный граф без контуров, дугам которого приписаны некоторые числовые значения.Дугам графа соответствуют отдельные работы проекта. Различают три вида работ:действительная работа (¾¾®) – любой трудовой процесс, требующий ресурсов и имеющий некоторую продолжительность (разработка проекта, подвоз материалов, монтаж оборудования и т. д.);ожидание (– × – × ®)– процесс, не требующий ресурсов, но имеющий некоторую продолжительность (затвердение бетона, сушка штукатурки, рост растений и т. д.);фиктивная работа (– – ®) отражает логическую зависимость между действительными работами. Не требует ресурсов и имеет нулевую продолжительность.Над дугой графа может быть указана числовая характеристика работы (например, время ее выполнения).Вершинам графа соответствуют события. Событие означает факт окончания всех работ, в него входящих, и начала всех работ, из него исходящих. Событие не имеет продолжительности и не потребляет ресурсов.Событие в сетевом графике имеет номер. Работа может обозначаться двумя способами:парой номеров (i, j), где i – номер начального события работы, а j – номер конечного события работы;буквенно-числовым обозначением с номером работы (a₁, b₂
и т. д.).Продолжительность работы обозначается t (i, j).Событие, с которого начинается выполнение проекта, называется исходным (I). Исходное событие не имеет предшествующих работ. Событие, которое констатирует факт завершения проекта, называется завершающим (S). Завершающее событие не имеет последующих работ.При построении сетевого графика необходимо соблюдать следующие правила:В сетевом графике не должно быть событий (кроме исходного), в которые не входит ни одна дуга и событий (кроме завершающего), из которых не выходит ни одна дуга.Сетевой график не должен содержать контуров.Любая пара событий сетевого графика может быть соединена не более чем одной дугой. Если нужно изобразить параллельно выполняемые работы с общими начальными и конечными событиями, то рекомендуется ввести дополнительные события и соединить их с последующим событием фиктивными работами. Пусть, например, имеются три различные работы a₁, a₂ и a₃, которые начинаются одним событием 2 и заканчиваются одним событием 5 (рис. 5.2).

Рис. 5.2. Фрагмент неверного сетевого графика

В этой ситуации может возникнуть путаница из-за того, что различные работы имеют одно и то же обозначение (2, 5). Чтобы избежать этого, введем фиктивные работы, как показано на рис. 5.3.

Рис. 5.3. Правильное изображение параллельных работ

События должны быть пронумерованы так, чтобы для любой работы (i, j) номер конечного события был больше-начального (j > i).Желательно, чтобы дуги сетевого графика не пересекались.Построение сетевого графика начинается с составления списка работ, подлежащих выполнению. Для каждой работы определяется ее продолжительность и предшествующие ей работы.Построение начинается с изображения исходного события 1, из которого выходят работы, не имеющие предшествующих.Работа изображается дугой, выходящей из начального события этой работы. Изображение конечного события работы будем откладывать, насколько это возможно.Далее последовательно изображаем каждую работуЕсли ей предшествует другая работа, то вводим событие, означающее конец этой предшествующей работы, и из него начинаем новую дугу.Если же работе предшествуют несколько работ, то нужно дуги, изображающие эти предшествующие работы, свести к одному событию, т. е. ввести вершину графа, в которую входят все предшествующие работы, и из этой вершины начать новую работу (при этом возможно, придется перерисовать график).Таким образом, новое событие вводится только тогда, когда нужно начать какую-либо работу.Номера событиям (вершинам графа) даются последовательно по мере их появления в модели. Такой подход обеспечивает правильную нумерацию событий.Когда изображены все работы, нужно проанализировать, какие работы не имеют последующих (не имеют пока конечных событий на графике). Все эти работы следует свести к одной вершине, которая и будет являться завершающим событием проекта. Поскольку проект будет закончен только тогда, когда закончатся все его работы, факт окончания всех не законченных ранее работ и будет являться фактом окончания проекта.

17Временные параметры сетевого графика Полный путь (m) в сетевом графике – это цепочка следующих друг за другом работ, соединяющих исходное и завершающее события. Критическим называется полный путь, имеющий наибольшую продолжительность во времени. Критических путей на сетевом графике может быть несколько (при этом все они имеют одинаковую продолжительность). Критический путь принято выделять на графике жирной линией.Продолжительность критического пути определяет критический срок проекта (t_кр). Все остальные (некритические) полные пути выполняются параллельно с критическим путем (цепочкой работ) и завершаются раньше. Критический срок, таким образом, показывает, за какое минимальное время может быть завершен весь проект. Очевидно, что увеличение сроков выполнения проекта больше t_кр невыгодно.Работы, принадлежащие критическому пути, называются критическими. Они не имеют резервов времени. Их несвоевременное выполнение ведет к срыву сроков всего проекта.Самый очевидный способ определения критического срока проекта – это перебрать все полные пути, рассчитать продолжительность каждого из них T (m) и выбрать полный путь наибольшей продолжительности:Однако, если сетевой график достаточно сложный, перебрать все возможные пути затруднительно. Поэтому используют более формальный подход: 1) Для каждого события рассчитывают ранний и поздний сроки свершения. 2) На их основе определяют резервы времени всех событий и работ. 3) Проводят критический путь по тем работам и событиям, которые не имеют резерва времени.Ранний срок свершения события – это самый ранний момент, к которому завершаются все работы, предшествующие этому событию.Ранний срок свершения события рассчитывается последовательно для каждого события от исходного к завершающему по следующим формулам:

(5.1)

где i ® j – множество работ, заканчивающихся j-м событием (дуги, входящие в вершину j);t_р (i) – ранний срок свершения начального события работы (i, j);t (i, j) – продолжительность работы (i, j).

Ранний срок свершения завершающего события совпадает с критическим сроком: t_кр = t_р(S).Поздний срок свершения события – это такой предельный момент, после которого остается ровно столько времени, сколько необходимо для выполнения к критическому сроку всех работ, следующих за этим событием.Поздние сроки свершения событий рассчитываются в обратном порядке от завершающего события к исходному по следующим формулам:

(5.2)

где i ® j – множество работ, начинающихся i-м событием (дуги, исходящие из вершины i)t_п (j) – поздний срок свершения конечного события работы (i, j);

t (i, j) – продолжительность работы (i, j).Резерв времени события показывает, на какой предельно допустимый срок может задержаться свершение события i без нарушения критического срока проекта. Резерв времени события равен разности между его поздним и ранним сроками свершения:

.

(5.3)

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

.

(5.4)

Ранний срок окончания работы равен сумме раннего срока свершения начального события работы и ее продолжительности:

.

(5.5)

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

.

(5.6)

Полный резерв времени работы – это максимальный запас времени, на которое можно задержать начало работы или увеличить ее продолжительность при условии, что весь комплекс работ будет завершен в критический срок:

.

(5.7)

В верхнем секторе запишем номер события, в левом по мере вычислений будем записывать ранний срок t_р (i) свершения события i, в правом – поздний срок t_п (i) этого события, а в нижнем – резерв времени R (i) события.1 шаг. Определение ранних сроков свершения событий от исходного к завершающему. t_p (1) = 0 (расчет времени начинается с 0).2 шаг. Определение поздних сроков свершения событий выполняется в обратном порядке – от завершающего события к исходному.

3 шаг. Определение резервов времени событий производится по формуле (5.3):

; и т.д.4 шаг. Определение параметров работ. Оптимизация сетевого графика1. Минимизация времени выполнения проекта при заданных ресурсах, которая может быть сформулирована в виде следующей задачи математического программирования:F = t_кр ® min;r £ r^выд,где r – требуемые ресурсы;r^выд – выделенные ресурсы.2. Минимизация требуемых ресурсов, обеспечивающих выполнение проекта в заданный период времени, математическая модель которой имеет следующий вид:F = r ® min; t_кр £ t^зад,где t^зад – заданное время выполнения проекта.Сокращение времени выполнения работ может быть достигнуто за счет вложения в них некоторых ресурсов. Такими ресурсами являются, например, трудовые ресурсы или машины, а также универсальный ресурс – финансы. При вложении дополнительного количества финансов в работу сокращение ее длительности достигается за счет следующих факторов:найма дополнительного количества рабочих;улучшения организации работ;автоматизации производственных процессов;применения передовых технологий и т. д.в качестве ресурса будут рассматриваться только финансы. При этом будем считать, что каждая работа (a_i, ) характеризуется некоторой трудоемкостью (Q_i, ), а время выполнения работы (t_i) обратно пропорционально величине вложенных в нее финансов (r_i). Это можно выразить следующей формулой: ,где n – количество работ проекта.В общем случае зависимость времени выполнения работы от величины вложенных в работу финансов может выражаться и другой убывающей функцией (например, линейной). Для определения конкретного вида этой функции следует построить уравнение регрессии на основе фактических данных о длительности работ и соответствующих вложенных в работу финансах.Однако насыщение любой работы финансами небеспредельно. Для каждой работы существует минимально возможное время ее выполнения, которое определяется технологическими особенностями этой работы. Это утверждение можно выразить следующим неравенством: ,где d_i – минимально возможное время выполнения работы.Критический срок проекта зависит как от длительности работ этого проекта (t_i), так и от логической последовательности и взаимозависимости работ. Пусть L – это логическая зависимость работ, которая задается в виде сетевого графика. Тогда критический срок проекта (t_кр) можно представить в виде следующей функции:t_кр = f (L, t₁, t₂, …, t_n).Сокращение времени выполнения проекта возможно как за счет внутренних резервов, так и внешних дополнительных средств. В первом случае у работ, имеющих резервы времени, забирают ресурсы и передают их работам, лежащим на критическом пути. Это позволяет сократить длительность критических работ. В случае использования внешних дополнительных средств, их также стараются вложить сначала в критические работы.

18Принципиальная схема межотраслевого баланса Под балансовой моделью понимается система уравнений, каждое из которых выражает требование баланса между производимым количеством продукции и общей потребностью в этой продукцииВажнейшим видом балансовых моделей являются модели межотраслевого баланса (МОБ). Они используются для анализа и планирования обмена продукцией между отраслями народного хозяйства [11].В модели МОБ все народное хозяйство представляется в виде совокупности n отраслей (промышленность, сельское хозяйство и т. д.). При этом используется понятие чистой (или технологической) отрасли, т. е. условной отрасли, объединяющей все производство данного продукта, независимо от ведомственной подчиненности и форм собственности предприятий и фирм. Валовой продукцией отрасли X_i ( ) называется вся производимая данной отраслью продукция. Распределение этой продукции можно условно разделить на две части: промежуточную и конечную продукцию.Промежуточной называется продукция, потребленная внутри системы отраслей для нужд производства. Таким образом, промежуточная продукция, которую произвела одна из отраслей, для другой отрасли выступает в качестве ресурса. Обозначим через x_ij объем продукции, произведенной в i-й отрасли и потребленной в j-й отрасли ( ).Конечной продукцией отрасли Y_i ( ) называется та часть произведенной в этой отрасли продукции, которая выходит за пределы системы (на внешнее потребление, на рынок, в другие системы).Принципиальная схема МОБ представлена в виде табл. 6.1.

Таблица 6.1. Принципиальная схема межотраслевого баланса

Раздел конечной продукции в этой схеме дан укрупненно в виде одного столбца величин Y_i. В развернутой схеме баланса конечный продукт каждой отрасли может быть показан дифференцированно по следующим направлениям использования: на личное потребление населения, общественное потребление, на накопление, экспорт и др. Этот столбец характеризует отраслевую материальную структуру национального дохода, а в развернутом виде – и распределение национального дохода.Если рассмотреть схему МОБ по строкам для каждой производящей отрасли, то очевидно, что валовая продукция (вся продукция, произведенная отраслью) равна сумме промежуточной и конечной продукции данной отрасли (которые в сумме дают все потребление этой продукции). Таким образом, можно записать следующее равенство:

,

(6.1)