Задача о кратчайшем пути между двумя вершинами графа

Пусть для каждой дуги (х, у) графа G задана её длина l(x, у), если вершины х и у не соединены дугой, то l(х, y) = ∞. Длина пути определяется как сумма длин отдельных дуг, составляющих этот путь. Тре­буется найти кратчайший путь между двумя заданными вершинами s и t графа G.

 

Алгоритм поиска кратчайшего пути (алгоритм окрашивания)

В ходе выполнения алгоритма окрашивают вершины и дуги графа и вычисляют величины d(x), равные крат­чайшему пути из вершины s в вершину х, включающему только окрашенные вершины.

1. Полагают d (s) = 0, d (х) = ∞ для любого х ≠s. Окрашивают вершину s и полагают y = s.

2. Для каждой неокрашенной вершины х пересчиты­вают величину d(x) по формуле d(x) = min { d(x), d(y) + l(y,x)}.

Если d (x) = ∞для всех вершин, то вычисления заканчи­вают. В графе G отсутствуют дуги из вершины s в не­окрашенные вершины.

В противном случае окрасить вершину х, для которой величина d(x) минимальна, и дугу, ведущую в вершину х. Полагают у = х.

3. Если y = t, то кратчайший путь найден. В противном случае переходят к шагу 2.

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

 

5.2 Задания

 

Задание 5.2.1

 

1. Охарактеризовать граф.

2. Выписать матрицу смежности графа.

3. Вычислить степени вершин.

 

Варианты:

 

Задание 5.2.2

 

1. По матрице инцидентности нарисовать граф.

2. Охарактеризовать граф.

3. Назвать специальные вершины графа.

4. Вычислить полустепени вершин.

5. Выписать цикл, цепь, простой цикл, простую цепь.

 

Варианты:

1)   X1 X2 X3 X4 X5 X6 V1 -1     -1 -1   V2   -1         V3     -1       V4             V5             V6	2)   X1 X2 X3 X4 X5 X6 V1 -1     -1     V2   -1     -1   V3     -1       V4             V5             V6
3)   X1 X2 X3 X4 X5 X6 V1 -1   -1       V2             V3   -1         V4         -1   V5           -1 V6	4)   X1 X2 X3 X4 X5 X6 V1 -1 -1         V2       -1 -1   V3             V4           -1 V5             V6

 

 

	X1	X2	X3	X4	X5	X6
V1
V2	-1
V3		-1		-1
V4			-1
V5					-1
V6

5)

 

 

 

Задание 5.2.3

 

1. Нагрузить граф задания 1.1 согласно матрицы длин дуг и нарисовать.

2. По алгоритму окрашивания найти кратчайший путь между вершинами V₁ и V₆.

3. Построить покрывающее дерево с корнем в вершине V₁.

 

Варианты:

 

1)   V1 V2 V3 V4 V5 V6 V1 ¥       ¥ ¥ V2   ¥     ¥ ¥ V3     ¥ ¥ ¥   V4     ¥ ¥   ¥ V5 ¥ ¥ ¥   ¥   V6 ¥ ¥   ¥   ¥	2)   V1 V2 V3 V4 V5 V6 V1 ¥   ¥     ¥ V2   ¥   ¥   ¥ V3 ¥   ¥ ¥ ¥   V4   ¥ ¥ ¥   ¥ V5     ¥   ¥   V6 ¥ ¥   ¥   ¥
3)   V1 V2 V3 V4 V5 V6 V1 ¥       ¥ ¥ V2   ¥   ¥   ¥ V3     ¥ ¥ ¥   V4   ¥ ¥ ¥   ¥ V5 ¥   ¥   ¥   V6 ¥ ¥   ¥   ¥	4)   V1 V2 V3 V4 V5 V6 V1 ¥   ¥     ¥ V2   ¥     ¥ ¥ V3 ¥   ¥ ¥ ¥   V4     ¥ ¥   ¥ V5   ¥ ¥   ¥   V6 ¥ ¥   ¥   ¥

 

5)

	V1	V2	V3	V4	V5	V6
V1	¥		¥		¥	¥
V2		¥		¥	¥	¥
V3	¥		¥
V4		¥		¥		¥
V5	¥	¥			¥
V6	¥	¥		¥		¥

6. Сетевое планирование

 

6.1 Основные определения и понятия

 

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

Сеть – конечный граф без циклов и петель, ориентированный в одном направлении.

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

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

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

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

- всем стрелкам сетевого графика задают общее направление слева направо;

- между одной парой событий можно изобразить только одну работу;

- не должно быть стрелок, которые ниоткуда не выходят и никуда не входят;

- сеть может содержать несколько начальных вершин (в которые не входит ни одна дуга). В этом случае можно добавить еще одну вершину и провести из нее дуги c нулевыми длительностями работ во все начальные вершины. Тогда сеть будет иметь одну начальную вершину. Аналогично вводят ко­нечную вершину;

- для упрощения анализа сети, устраняют пересечения работ преобразованием взаимного расположения работ и событий;

- нумерацию событий проводят последовательно слева направо и сверху вниз.

Правильная нумерация – номер начала любой дуги меньше номера ее конца.

Временные параметры сетевых моделей:

- Ранний срок свершения j-го события t_j ^p – наиболее ранний из возможных моментов наступления данного собы­тия при заданной продолжительности работ.

- Поздний срок свершения j-го события t_j ⁿ – наиболее поздний из допустимых моментов наступления данного события, при котором еще возможно выполнение всех последую­щих работ в установленный срок.

- Резерв времени на свершение j-го события Rj – это промежуток времени, на который может быть отсрочено наступление собы­тия j без нарушения сроков завершения всего комплекса, опреде­ляется как разность между поздним t_j ⁿ и ранним t_j ^p сроками на­ступления события

Rj = t_j ⁿ - t_j ^p.

- Ранний срок начала работы t_ij ^P.H – наиболее ранний из возможных моментов начала данной работы при за­данной продолжительности работ. Он совпадает с ранним сроком наступления ее начального события:

t_ij ^P.H = t_j ^p.

- Ранний срок окончания работы t_ij ^P.O – наиболее ранний из возможных моментов окончания данной работы при заданной продолжительности работ. Он превышает ранний срок наступления ее события i на величину продолжительности работы:

t_ij ^P.O = t_j ^p + t_ij.

- Поздний срок начала работы t_ij ^П.Н – наиболее поздний из допустимых моментов начала данной работы, при котором еще возможно выполнение всех последующих работ в установленный срок:

t_ij ^П.Н = t_j ^П - t_ij.

- Поздний срок окончаний работы t_ij ^П.О – наиболее поздний из допустимых моментов окончания данной ра­боты, при котором еще возможно выполнение последующих ра­бот в установленный срок:

t_ij ^П.О = t_j ^П.

- Полный резерв времени работы (i,j) r_ij ^П – максимальное время, на которое можно отсрочить начало или увеличить продолжи­тельность работы t_ij без изменения общего срока выполнения комплекса:

r_ij ^П = t_j ^П - t_j ^P - t_ij.

- Свободный резерв времени работы (i, j) r_ij ^С.В – максимальное время, на которое можно отсрочить начало или увеличить про­должительность работы при условии, что все события сети насту­пают в свои ранние сроки: r_ij ^С.В = t_j ^P - t_i ^P - t_ij.

6.2 Задания

 

Задание 6.2.1

 

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

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

Таблица заданий

 

Содержание работ	Работа	Длительность, t i
Коэффи-циент, c i	Обозна-чение, a i	Опор-ная, a j	Варианты заданий
Отбор товара	0,1	a 1	-
Подготовка к отправке	0,2	а 2	a 1
Выписка накладных	0,3	a 3	а 2
Определение объема отгрузки	0,4	а 4	a 3
Проверка цен	0,5	a 5	a 3
Оформления счета	0,6	a 6	a 5
Заказ автомашин для перевозки товара	0,7	a 7	а 4 a 6
Отправка счета покупателю	0,8	a 8	а 4 a 6
Проверка товара по счету	0,9	а 9	a 7
Оплата счета	1,0	a 10	a 8
Погрузка товара и проверка количества	1,1	a 11	a 9 a 10
Перевозка товара	1,2	a 12	a 11
Выгрузка и сверка с документами	1,3	a 13	a 12

 

 

2. Построить критический путь, вычислить критическое время, нанести критический путь на сетевой график.

7. Системы массового обслуживания (СМО)

 

7.1 Основные определения и понятия

 

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

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

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

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

Ординарный поток – вероятность попадания на малый отрезок времени двух или более событий пренебрежимо мала по сравнению с вероятностью попадания только одного события.

Простейший (пуассоновский) поток – поток одновременно обладающий свойствами стационарности, ординарности и отсутствием последействия.

Показатели эффективности СМО:

1) Вероятность того, что поступающее в систему требование откажется присоединяться к очереди и теряется (Р_отк ).Этот показатель для системы массового обслужи­вания с отказами равен вероятности того, что в системе находится столько требований, сколько она содержит приборов (каналов) обслуживания:

 

Р_отк = Р_m,

где m – число каналов обслуживания.

Для системы с ограниченной длиной очереди Р_отк равно вероятности того, что в системе находится m+l требований:

 

Р_отк = Р _{m + l},

где l – допустимая длина очереди.

Противоположным показателем является вероятность обслуживания требования

 

P_обсл = 1 – P_отк.

 

Вероятности состояний Pi определяются по формулам:

cистема с отказами

 

Р_i = Р₀ *ρⁱ / i!,

 

где i = l, 2,..., m, ρ = λ/µ, λ – интенсивность входящего потока требований, µ - производительность одного канала (прибора) обслуживания, S₀, S₁,..., S_m – состояния системы (индекс указывает число требований в системе), m – общее число каналов, а вероятность Р₀ находится из выражения

 

система с ограниченной длиной очереди и ожиданием

имеющей m каналов с ограниченной очередью, число мест в которой ограничено величиной l вероятности состояний S₁, S₂,..., S_m находят по формуле

 

Pi = P₀*ρⁱ / i!, (i = l, 2,.... m).

 

Вероятности состояний S_m+1, S_m+2,..., S _m+l определяют по формулам

(i = m+1, …,m+l)

 

 

В большинстве практических задач при (ρ/m) < 1

 

2) Среднее количество требований, ожидающих начала обслуживания,

где P _п –вероятность того, что в системе находятся n требований.

При условии простейшего потока требовании и экспо­ненциального закона распределения времени обслужива­ния формулы для М _ож принимают следующий вид:

 

система с ограниченной длиной очереди

где ρ = λ/µ, λ – интенсивность входящего потока требований (среднее число требований, поступающих в единицу времени), µ – интенсивность обслуживания (среднее число обслуженных требований в единицу времени);

система с ожиданием

3) Относительная (q) и абсолютная (А) пропускные способности системы. Эти величины находят соответственно по формулам

 

q = 1- Р_отк, А = λq.

 

4) Среднее число занятых обслуживанием приборов в случае экспоненциального характера потока требований и времени обслуживания

 

m₃ = ρq.

 

Для системы массового обслуживания с отказами m₃ можно найти по формуле

 

 

5) Общее количество требований, находящихся в си­стеме (М). Эту величину определяют следующим образом:

 

система массового обслуживания с отказами

 

M = m₃ ,

 

система массового обслуживания с ограниченной длиной очереди и ожиданием

 

М = m₃ + М_ож.

 

6) Среднее время ожидания требованиям начала обслуживания (Т_ож ). Если известна функция распределения вероятности времени ожидания требованием начала обслуживания

 

F(t) = Р (Т_ож < t),
то среднее время ожидания находится как математическое ожидание случайной величины Т_ож:

Т_ож при показательном законе распределения требований во входящем потоке можно определить по формуле

 

Т_ож = .

7.2 Задания

 

Задание 7.2.1

 

1. Решить задачу для СМО с отказами:

В вычислительный центр с m ЭВМ поступают заказы на вычислительные работы. Если работают все m ЭВМ, то вновь поступающий заказ не принимается. Пусть среднее время работы с одним за­казом составляет Т_обс^ср часов. Интенсивность потока заявок равна λ (1/ч). Найти вероятность отказа Р_отк и m_з – среднее число занятых ЭВМ.

 

Варианты:

 

	В1	В2	В3	В4	В5
m
λ	0,25	0,2	0,2	0,15	0,1
Тобсс р

 

 

Задание 7.2.2

 

1. Решить задачу для СМО с ограниченной длиной очереди:

На автозаправочной станции установлены m колонок для выдачи бензина. Около станции находится площадка на L машин для их ожидания в очереди. На станцию прибывает в среднем λ машин в минуту. Среднее время заправки одной машины Т_обс^ср мин. Требуется определить вероятность отказа Р_отк и среднюю длину очереди М _ож.

 

Варианты:

 

	В1	В2	В3	В4	В5
m
L
λ
Тобсс р		0,5	0,6	0,8	0,9

 

 

 

8. Игры

 

8.1 Основные определения и понятия

 

• Теория игр – математическая теория конфликтных ситуаций.

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

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

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

• Матричная – парная игра с нулевой суммой, задаваемая матрицей - ||aij||_mxn, элементы которой определяют выигрыш первого игрока (и соответственно проигрыш второго), если первый игрок выберет i-ю строку (i-ю стратегию), а второй игрок – j-й столбец (j-ю стратегию). Матрица ||aij||_mxn называется платежной матрицей или матрицей игры.

• Каждая фиксированная стратегия, которую может выбрать игрок, называется его чистой стратегией.

• Матричная игра имеет решение в чистых стратегиях, если игра имеет равновесную ситуацию – когда v = V = v*, где

 

- нижняя цена игры;

- верхняя цена игры.

Всегда v ≤ V. v* называется ценой игры в чистых стратегиях.

• Если v = V = v*, то решение игры в чистых стратегиях достигается в седловых точках. Любая пара (i₀, j₀) назы­вается седловой точкой, когда существует элемент матрицы a_i0j0 , обладающий свойством a_ij0 ≤ a_i0j0 ≤ a_i0j, т. е. когда элемент матрицы a_i0j0 - минимальный в своей строке и в то же время максимальный в столбце.

 

• Если обозначить через p₁, p₂,..., p_m вероятности (частоты), с которыми первый игрок выбирает соответ­ственно первую, вторую,..., m-ю чистую стратегию, так что

pi ≥ 0, i = l, 2,..., m, ;

через q₁, q₂,,..., q_n — вероятности, с которыми второй игрок выбирает первую, вторую,..., n-ю свою чистую стратегию, причем

qj ≥ 0, j = 1, 2,..., n, ,

то наборы чисел P = (p₁, p₂,...,..., p_m) и Q = (q₁, q₂,..., q_n) называются смешанными стратегиями первого и второго игроков соответственно.

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

• налитическое решение игры 2х2

Если матрица размером 2х2 не имеет седловой точки, то каждый из игроков обладает единственной оптимальной смешанной стратегией Р⁰ и Q⁰ с компонентами

, p ₂ = 1 – p ₁

, q ₂ = 1 – q ₁

цена игры v * определяется формулой

• Правило (принцип) доминирования

Строка k называется доминируемой строкой l, если все элементы строки k не превышают соответствующих элементов строки l, т.е.
a _ki ≤ a _li для всех i.

Столбец k называется доминируемым столбцом l, если все элементы столбца l не превышают соответствующих элементов столбца k, т.е. a _kj ≥ a _lj для всех j. Оптимальные смешанные стратегии в игре с усеченной матрицей, полученной отбрасыванием доминируемых строк и столбцов, являются оптимальным решением исходной игры, если вероятности доминируемых чистых стратегий положить равными нулю.

 

 

8.2 Задания

 

Задание 8.2.1

 

1. Решить игру в чистых стратегиях.

2. Выписать седловые точки.

3. Вычислить цену игры.

 

Варианты:

			2)   В1 В2 В3 В4 А1   -3 -2 -1 А2         А3

 

 

5)   В1 В2 В3 В4 А1         А2         А3

 

Задание 8.2.2

 

1. Решить игру.

 

Указание: использовать принцип доминирования.

 

Варианты:

	5)   В1 В2 В3 В4 В5 А1           А2           А3           А4

 

Задание 8.2.3

 

1. Решить игру 2хn графическим методом.

		5)   В1 В2 В3 В4 А1         А2     -2

 

 

Вопросы по курсу «Методы принятия управленческих решений»

1. Предмет «Исследование операций», этапы операционных исследований.

2. Экономико-математическое моделирование, его сущность.

3. Экономическая и математическая постановка задачи производственного планирования.

4. Классификация задач математического программирования.

5. Задачи линейного программирования (ЗЛП, общая и каноническая формы).

6. Приведение ЗЛП к каноническому виду.

7. Геометрический метод решения общей ЗЛП с двумя неизвестными.

8. Допустимый и оптимальный базисные планы.

9. Суть симплекс-метода, базисные и свободные переменные.

10. Построение симплекс-таблицы канонической ЗЛП.

11. Алгоритм симплекс-метода.

12. Метод искусственного базиса.

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

14. Правила построения двойственной пары.

15. Основные теоремы двойственности.

16. Построение общей симплекс-таблицы пары двойственных ЗЛП.

17. Признаки оптимальности двойственной пары ЗЛП.

18. Экономический смысл пары двойственных ЗЛП.

19. Постановка и математическая модель транспортной задачи (ТЗ).

20. Метод северо-западного угла построения опорного плана перевозок.

21. Метод потенциалов решения транспортной задачи.

22. Математическая формулировка задач дискретного программирования.

23. Основные идеи и принципы метода отсекающих плоскостей.

24. Обобщенная схема алгоритма Гомори.

25. Постановка задачи нелинейного программирования. Локальный и глобальный экстремум.

26. Решение задач условной оптимизации методом Лагранжа.

27. Градиентные методы решения задач безусловной оптимизации.

28. Выпуклое программирование.

29. Двойственность в нелинейном программировании. Теорема Куна-Такера.

30. Понятие задачи динамического программирования. Пример.

31. Принцип оптимальности Беллмана, уравнения Беллмана.

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

33. Предмет и основные понятия «Теории игр».

34. Классификация игр. Матричные игры.

35. Чистые стратегии. Максиминные и минимаксные стратегии.

36. Равновесная ситуация. Игры с седловыми точками.

37. Смешанные стратегии. Функция выигрыша. Верхняя и нижняя цена игры.

38. Теорема фон Неймана. Свойства оптимальных стратегий.

39. Принцип доминирования.

40. Решение игр 2хn, mх2.

41. Связь с задачей линейного программирования.

42. Игры с природой. Критерии Гурвица, Лапласа, Вальда, Сэвиджа,

43. Основные понятия теории графов. Путь, цикл, дерево.

44. Операции над графами.

45. Эйлеровы и гамильтоновы графы.

46. Ориентированные графы. Сети. Максимальный поток в сети.

47. Кратчайший путь между двумя вершинами графа.

48. Задачи сетевого планирования. Сетевой график.

49. Критический путь. Алгоритм построения критического пути.

50. Временные параметры сетевого графика. Ранние и поздние сроки, резервы времени.

51. Марковские процессы, основные понятия и классификация.

52. Цепи Маркова. Уравнения Колмогорова. Процесс «гибели и размножения».

53. Характеристики и классификация систем массового обслуживания (СМО).

54. СМО с отказами.

55. СМО с ожиданиями.

56. Замкнутые СМО.

 

 

Библиографический список

 

1. Афанасьев, М. Ю. Прикладные задачи исследования операций [текст]: учебное пособие / М. Ю. Афанасьев, К. А. Багриковский, В. М. Матюшок. – М: Инфра-М, 2009. – 352 с.

2. Бухалков, М. И. Планирование на предприятии [Текст]: учебник / М. И. Бухалков. - 3-е изд., испр. - М.: Инфра-М, 2008. - 416 с. - (Высшее образование).

3. Высшая математика для экономистов [Текст]: учебник. - 3-е изд. – М: Юнити-Дана, 2009. – 479с.

4. Гмурман, В. Е. Теория вероятностей и математическая статистика [Текст]: учеб. пособие для бакалавров; рекомендовано Мин. образования / В. Е. Гмурман. - 12-е изд. - М.: Юрайт, 2013. - 479 с.: ил. - (Бакалавр. Базовый курс).

5. Математические методы и модели исследования операций [Текст]: Учебник. +СД: учебное пособие / Под науч. ред. проф. Б. А. Суслакова. – М.:"Дашков и К", 2011. – 400с.

6. Сборник задач по курсу "Математика в экономике" [Текст]: в 3-х ч. учеб. пособие для вузов; рекомендовано методсоветом по направлению / ред.: В. А. Бабайцев, В. Б. Гисин. - М.: Финансы и статистика: Инфра-М, 2010 - Ч.4: Исследовагние операций. - 128 с.

7. Шикин, Е. В. Исследование операций [Текст]: учебник / Е. В. Шикин, Г. Е. Шикина. - М.: Велби: Проспект, 2008. - 280 с.

 

 

Приложение 1.

Образец оформления титульного листа

Негосударственное образовательное учреждение

Высшего профессионального образования

«Сибирский институт бизнеса, управления и психологии»

Экономический факультет

Кафедра прикладной математики и информатики

 

 

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

 

Контрольная работа

Вариант 2

 

 

Выполнил: И.И. Иванова, студент гр. 228 м зачетная книжка № 08-2247   Проверил: А.А. Ступина, д.т.н., профессор «____»______________2013 г. _________________________ (оценка и подпись преподавателя

 

 

Красноярск 2013
ДЛЯ ЗАМЕТОК

 

 

Технический редактор: Е. С. Разгулина

 

 

Подписано в печать Формат 14,85×21,0 1/16 Печать трафаретная. Изд. № Тираж 30 экз.

Сдано в производство Бумага потребительская Усл. печатных листов 4,0   Заказ №

 

 

Редакционно-издательский отдел НОУ ВПО СИБУП.

660037, Красноярск, ул. Московская, 7а.