22. Транспортная задача (открытая модель).

Открытая модель транспортной задачи сводится к закрытой модели транспортной задачи, а именно, если a и b – векторы поставщиков и потребителей, и если

a=(a1, …, an)

b=(b1, …, bn) , то вводится фиктивный потребитель Вn+1, потребности которого и стоимость перевозок cin+1=0, i любое.

А если , то вводится фиктивный поставщик Аm+1, запасы которого и стоимость перевозок от которого Сm+1j=0, j любое.

23. Математическая модель об оптимальном назначении.

24. Алгоритм решения задачи об оптимальном назначении.

Теория игр

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

Имеется 2 игрока, 1 из которых может выбирать одну из m своих стратегий, а 2ой не зная выбора 1ого – одну из n стратегий.

А1, А2…, Аm В1, В2…, Вn – такие стратегии – числа

При выборе стратегии (Ai, Bj) 1ый игрок выигрывает аij единиц, а 2ой проигрывает aij единиц. При этом матрица С=(аij) i=1…m, j=1…n – платежная матрица игры.

Определение 1: Пусть А= (аij) – платежная матрица игры. Нижняя цена игры (максимино) – число α=max(min aij).

Верхняя цена игры (минимаксимо) – β=min(max aij).

Теорема 1: α<β

Доказательство: Пусть α=max(min aij)=ai0j

β=min(max aij)=aij0

α= ai0j ≤ ai0j0 ≤aij0 =β

Определение 2: Пусть нижняя и верхняя цены игры совпадают. Тогда найдется элемент ai0j0=α=β – седловая точка игры.

Теорема 2 : Рассмотрим игру с седловой точкой ai0j0=α=β. Тогда стратегии Аi0 и Bj0 являются наиболее благоприятными для 1ого и 2ого игрока.

Доказательство: Если 1ый игрок выберет стратегию, отличную от Ai0, он выиграет меньше при правильной игре 2ого. Если 2ой игрок выберет стратегию, отличную от Bj0, то проиграет больше при правильной игре 1ого.

Определение 3: Пусть А – платежная матрица игры. Рассмотрим стратегии Ар и Aq для 1ого игрока такие, что apj aqj. Тогда стратегия Ар – доминирующая, а Aq – доминируемая.

Пусть Bl и Bk – стратегии 2ого игрока, такие, что ail≤aik, i любое. Тогда стратегия Bl – доминирующая, а Bk – доминируемая.

Замечание: Доминируемые стратегии можно отбросить, т. к. они заведомо не будут выбраны одним из игроков.

Определение 4: Стратегии p*=(p*1, p*2, …, p*m) q*=(q*1, q*2, …, q*n) отрицательные, если средний выигрыш по этим стратегиям M(p, q*)≤M(p*, q*)≤M(p*, q) (1)

При этом M(p*, q*) – цена игры.

Замечание: Выигрыш первого игрока при выборе им оптимальной стратегии больше, чем выигрыш по любой другой стратегии при правильной игре второго.

Средний проигрыш 2ого игрока при выборе стратегии q* будет меньше, чем проигрыш при выборе им другой стратегии при правильной игре 1ого игрока.

Рассмотрим правую часть неравенства (1).

M(p*, q*)≤M(p*, q) q=(0,…,1,…,0)

Пусть q=(0,…,1,…,0), тогда (p*1,…,p*m)A =(p*1, …, p*m) ≥δ, j любое.

Разделим обе части на δ, δ>0.

При этом p*1/δ=x1,…, p*m/δ=xm. Тогда (x1,…, xm)*A≥(1,…,1) (2)

f=x1+…+xm=1/ →min (3) – задачи линейного программирования

Рассмотрим левую часть неравенства (1)δ

M(p,q*)≤M(p*,q*)

Пусть p=(0,…,1,….,0)A

(ai1,…,ain) . Будем считать, что δ>0, поделим обе части на δ.

q*1/δ=y1,…, q*n/δ=yn.

В результате получаем систему неравенств:

(4)

yi≥0, i любое

(5)

(4)-(5) – задачи линейного программирования

(2)-(3), (4)-(5) – пара взаимодвойственных задач линейного программирования. Если их решить то цена игры δ:

Δ=1/zmax=1/fmin (6)

q*j= δy*j j любое, и p*i=δx*I i любое. (7)

25. Граф — это совокупность непустого множества вершин и множества пар вершин (связей между вершинами).

Объекты представляются как вершины, или узлы графа, а связи — как дуги, или рёбра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах.

Если пара упорядоченная, то она дуга, в противном случае – ребро. Если все пары в графе упорядочены , то граф – ориентированный(орграф)

Путем в графе(орграфе) называется последовательность ребер(дуг), такая, что конец каждой предыдущей дуги совпадает с началом последующей. Если конец пути совпадает с началом – контур. Контур, в котором всего одна вершина- петля. Граф связный, если любые две его вершины можно соединить каким-то путем.

26. Алгоритм Фалкерсона. Упорядочивания вершин связного орграфа без петель и контуров.

1 i=1, i- счетчик цифр

2) рассмотрим вершины графа, в который не входят ни одна дуга и номеруем их в произвольном порядке i=i+1

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

27. Сетевой график показывает последовательность выполнения работ друг за другом.

Ранним сроком начала работы ij - называется наименьшее время, после которого можно начинать выполнение работы ij.

Если из вершины I выходит несколько работ, то ранние сроки начала этих работ совпадают и они называются – ранним сроком свершения события I и обозначаются (

Более того , (k,i) € , где раннее окончание работы (k,i), а множество всех дуг, входящих в i -ую вершину

Ранний срок свершения последнего события называется критическим временем. Путь на сетевом графике от 1-ого события к последнему, длина которого равна - называется критическим путем.

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

28.Поздним сроком свершения события j ( будем называть наибольшее возможное время свершения этого события которое не повлияет на .

Если в вершину j входят несколько дуг ij, то поздние сроки окончания этих работ совпадают и равны

Максимально возможное время окончания работы, не нарущающее )

, (j,k)€

Все дуги, выходящие из j-ой вершины

Крайний срок начала работы без изменения

29 Сетевое планирование (резервы времени событий и работ)

Резерв времени события : R_j=T_i^п-T_j^p –на столько можно отложить свершение события, чтобы не изменилось Т критическое.

Пример: R₂=6-3=3 дня-свершение события 2 можно задержать на 3 дня и при этом Т критическое не изменится.

Резерв времени работ: R_ij=T_j^п-T_i^p-t_ij- полный резерв времени работы ij (на такой срок работа ij может быть задержана без изменения Т критического. Но все последующие работы должны выполняться без задержек).

Резерв времени для событий, лежащих на критическом пути =0.

r_ij= T_j^р-T_i^p-t_ij – свободный резерв времени (резерв для выполнения работы ij, не влияющий на ранние сроки совершения последующих событий).

Свободным резервом времени можно распоряжаться произвольно.

30. Математическая модель задачи о максимальном потоке

Задача о максимальном потоке в сети: Рассмотрим орграф, каждой ориентированной дуге (I,j) которого поставлено в соответствие некоторое число d_ij (пропускная способность дуги). Выделены две вершины S-источник, t-сток. Построить максимальный поток (какого-то груза или ресурса) из S в t, чтобы величина x_ij потока была меньше, чем d_ij, и чтобы в промежуточных вершинах не оставалось ни одной единицы потока.

Математическая модель: Пусть x_ij- кол-во ресурса, перевозимого по дуге ij и V-общее кол-во ресурса. Тогда целевая функция V->max. Ограничение 0<= x_ij<= d_ij

для любых k≠S; k≠t

31. Потоки в сетях (теорема Форда-Фалкерсона)

Максимальный поток из S в t равен минимальной из пропускных способностей разреза.

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

По теореме 1 максимальный поток V=c(R₁,R₂) для любого разреза R₁,R₂.

Найдем разрез, когда V=c(R₁,R₂) и построим разрез, когда V=c(R₁,R₂)

Пусть множество R₁ включает в себя: 1. Источник S и если i-тая вершина из R₁ и на дуге (i,j) выполняется неравенство x_ij<=d_ij, то вершину j включаем в множество R₁

А если рассматриваем дугу с обратным направлением (j,i), то если x_ji>0, то вершину j также включаем в R₁. Проводя такие манипуляции в окончательном варианте получится, что вершина t не включается в R₁. Тогда разбиение c(R_1, ) будет разрезом. Предположим противное, что t включится в R₁, тогда на сети будет существовать путь S=i₀,i₁,i₂…i_n=t из S в t, все вершины которого принадлежат множеству R₁. Обозначим через P⁺ множество дуг на этом пути, направленных из S в t и через P^- множество дуг этого пути, имеющих противоположное направление.

Для любой дуги (i,j) из P⁺ выполняется неравенство x_ij<d_ij, а для любой (j,i) из P^—неравенство x_ji>0.

Пусть ε₁=min(d_ij-x_ij)-дуги, направленные из S в t. ε₂=min(x_ij)-дуги из P^-. ε=min(ε_1,ε₂)

Тогда поток вдоль данного пути можно увеличивать на ε единиц. Прибавим ε по всем дугам из P⁺ и величину ε во всех дугах из P^-.

В результате получим увеличивающий путь. Поток V не будет максимальным.

Противоречие, поэтому t не принадлежит R₁, а если посчитать пропускную способность разреза (R₁, ), то она равна:

с(R₁, )= ч.т.д.

32. Потоки в сетях (алгоритм решения задачи)

1) Находим на сети первоначально допустимый поток x_ij для любых i,j и каждую дугу помечаем метками (d_ij,x_ij)

2) Вершину S помечаем меткой S⁺. Просматриваем все вершины j соседние с вершиной S и если x_sj<d_sj, то вершину j помечаем меткой S⁺.

Если же x_js>0, то вершину j помечаем меткой S^-.

3) Просматриваем все вершины, помеченные на предыдущем этапе, и если i-одна из таких вершин, рассматриваем соседние с ней вершины j, и тогда при выполнении неравенства x_ij<d_ij вершину j помечаем метку i⁺, если x_js>0, то помечаем i^- и т.д., пока есть что помечать

Если вершина окажется помеченной, строят увеличивающий путь, поток по которому увеличивают с помощью неравенств 4-5 и далее переходят на шаг 2. Если вершина t не помечена, то строят разрез (R_помеч.,R_{не помеч.}) и V=c(R_помеч.,R_{не помеч.})