Контрольня работа. контрольная работа. 1. Теоретическая часть

Название	1. Теоретическая часть
Анкор	Контрольня работа
Дата	15.04.2022
Размер	1.02 Mb.
Формат файла
Имя файла	контрольная работа.docx
Тип	Документы #476624

Содержание
1. Теоретическая часть ………………………………………………………….. 3

1.1 Природа потоков в сетях и принцип их сохранения …………………… 3

2. Практическая часть …………………………………………………………... 8

2.1 Общая постановка задач линейного программирования ………………. 8

2.2 Элементы теории игр …………………………………………………...... 9

2.3 Планирование производства с помощью сетевых моделей ………….... 9

Список литературы …………………….………………………………………. 16

Теоретическая часть

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

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

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

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

Рис. 1 – Пример транспортной сети.
Сходство сетевых представлений наблюдается в природе, технике и различных сферах деятельности человека. Так, например, с высоты птичьего полёта или самолёта можно наблюдать сетевую модель формирования реки, например, Волги, от её истоков маленькие ручейки и реки, соединяясь во взаимосвязанные артерии, объединяются в одно большое русло, по которому потоки воды устремляются в Каспийское море. Такие же аналогии представляют собой сети железных дорог, по которым транспортные потоки направляются из пунктов отправления в пункты назначения, осуществляя перевозку потоков грузов и пассажиров. Совокупность линий электропередач также представляют собой энергетическую сеть, по которой потоки электроэнергии от электростанций по проводам поступают к потребителям. Автомобильные дороги как в масштабе города, района, области, так и в более крупных масштабах страны или, например, континента, представляют собой сети, по которым движутся потоки автомобилей. Нефте- и газопроводы в совокупности представляют собой сети трубопроводов, по которым потоки нефти или газа поступают от источников к потребителям. Водопроводные сети обеспечивают движение потоков воды по трубопроводам от источников к потребителям. Аналогичные сети представляют собой маршруты движения кораблей и самолётов, обеспечивающие перемещение потоков пассажиров и грузов по планете. Такие же аналогии представляют собой телефонные, радио- и телекоммуникационные сети, по которым циркулируют информационные потоки, например, компьютерные сети связи различного назначения. Особый интерес представляют сети, образованные движением товарных и финансовых потоков, изучение которых может пояснить очень многие явления нашей жизни.

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

Потоком f в сети G является действительная функция f: V x V → R, удовлетворяющая условиям:

1)

(антисимметричность);

2)

(ограничение пропускной способности), если ребра нет, то

;

3)

для всех вершин u, кроме s и t (закон сохранения потока).

Величина потока f определяется как:

Также существует альтернативное определение (по Асанову), не вводящее антисимметричность.

Поток f в сети G = (V, E, c) называется функция f: E→R, удовлетворяющая условиям:

1) Величина потока по каждой дуге не должна превосходить её пропускной способности:

2) Величина потока, входящего в каждую вершину сети, за исключением входа и выхода, равна величине потока, выходящего из этой вершины:

Здесь s – источник, а t – сток сети G (s имеет нулевую степень захода, а t имеет нулевую степень исхода); через v+ обозначено множество вершин, к которым идут дуги из вершины v; через v– обозначено множество вершин, из которых идут дуги в вершину v; c(e) называется пропускной способностью дуги е и неотрицательно.

Число f(v,w) можно интерпретировать, например, как количество жидкости, поступающей из v в w по дуге (v,w). С этой точки зрения значение f(v−) может быть интерпретировано как поток, втекающий в вершину v, а f(v+) — вытекающий из v. Условие 1) называется условием ограничения по пропускной способности, а условие 2) — условием сохранения потока в вершинах; иными словами, поток, втекающий в вершину v, отличную от s или t, равен вытекающему из неё потоку.

Пример сети с источником s и стоком t.

Рис. 2 – Сеть с источником s и стоком t
Первое число означает величину потока, второе — пропускную способность ребра. Отрицательные величины потока не указаны (так как они мгновенно получаются из антисимметричности:

). Сумма входящих рёбер везде (кроме источника и стока) равна сумме исходящих и на то, что в общем

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

Величина потока в этом примере равна 3+2=5 (считаем от вершины s).

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

Из определения потока следует, что величина потока не исчезает и не накапливается в вершинах сети, и, следовательно, количество потока, выходящего из входа s, равно количеству потока, заходящему в выход t. Это значение называется величиной потока V. Таким образом, поток в сети сохраняется, а величина потока равняется сумме значений потоков, выходящих из вершины s или входящих в вершину t.
2. Практическая часть

2.1 Общая постановка задач линейного программирования
№ 6.

В задаче составить экономико-математическую модель. На двух автоматических линиях выпускают аппараты трёх типов. Другие условия задачи приведены в таблице.

Тип аппарата	Производительность работы линий, шт. в сутки			Затраты на работу линий, ден. ед. в сутки			План, шт.
	1	2	1		2
А	4	3	400		300	50
В	6	5	100		200	40
С	8	2	300		400	50

Составить такой план загрузки станков, чтобы затраты были минимальными, а задание выполнено не более чем за 10 суток.
Решение:

Составим экономико-математическую модель задачи. Через х₁^А, х₁^В, х₁^С обозначим время, в течение которого первая линия будет занята выпуском аппаратов А, В и С. Аналогично обозначим через х₂^А, х₂^В, х₂^С – время, в течение которого вторая линия будет занята выпуском аппаратов А, В и С.

Так как время работы каждой линии ограничено десятью сутками, то:

По плану:

Также:

.

Целевая функция:

2.2 Элементы теории игр
№ 9.

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

0,3	0,6	0,8
0,9	0,4	0,2
0,7	0,5	0,4

B_i
Решение:

A_j	В₁	В₂	В₃	a_i
А₁	0,3	0,6	0,8	0,3
А₂	0,9	0,4	0,2	0,2
А₃	0,7	0,5	0,4	а=0,4 0,4
b_j	0,9	0,6	0,8	b=0,6

Анализируя строки матрицы (стратеги игрока А) заполняем столбец a_i: а₁=0,3; а₂=0,2; а₃=0,4 – минимальные числа в строках 1, 2 и 3. Аналогично b₁=0,9; b₂=0,6; b₃=0,8 – максимальные числа в столбцах 1, 2 и 3 соответственно. Нижняя цена игры a = max a_i = max (0,3; 0,2; 0,4) = 0,4 (наибольшее число в столбце a_i) и верхняя цена игры b = min b_j = min (0,9; 0,6; 0,8) = 0,6 (наименьшее число в строке b_j). Эти значение не равны, то есть a ≠ b, следовательно, седловая точка отсутствует.

2.3 Планирование производства с помощью сетевых моделей
№ 1.

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

Вариант	1
Работа	Длительность выполнения работы, час
0—1	4
1—2	9
1—3	4
1—4	5
2—6	22
2—5	8
3—5	1
4—5	10
4—7	6
5—6	7
5—12	6
6—9	9
6—10	9
7—8	6
8—12	15
9—11	4
10—11	12
11—12	1
12—13	13

Решение:

Полагаем, что i₀ =0, i₁=4, узлам 2, 3 и 4 непосредственно предшествует только узел 1: i₂ = d₁₂ = 13, i₃ = d₁₃ = 8, i₄ = d₁₄ = 9. Далее находим:

i₅ = max (i₂+ d₂₅; i₃+ d₃₅; i₄ + d₄₅) = (21; 9; 19) = 21

i₆ = max (i₂+ d₂₆; i₅+ d₅₆) = (35; 28) = 35

i₇ = max (i₄ + d₄₇) = 15

i₈ = max (i₇ + d₇₈) = 21

i₉ = max (i₆ + d₆₉) =44

i₁₀ = max (i₆ + d₆₁₀) = 44

i₁₁ = max (i₉ + d₉₁₁; i₁₀ + d₁₀₁₁) = (48; 56) = 56

i₁₂ = max (i₈ + d₈₁₂; i₅ + d₅₁₂; i₁₁ + d₁₁₁₂) = (36; 26; 57) = 57

i₁₃ = max (i₁₂ + d₁₂₁₃) = 70

Поздний срок:

u₁₃ = 70

u₁₂ = min (u₁₃ – d₁₃₁₂) = 57

u₁₁ = min (u₁₂ – d₁₂₁₁) = 56

u₁₀ = min (u₁₁ – d₁₁₁₀) = 44

u₉ = min (u₁₁ – d₁₁₉) = 52

u₈ = min (u₁₂ – d₁₂₈) = 42

u₇ = min (u₈ – d₈₇) = 36

u₆ = min (u₉ – d₉₆; u₁₀ – d₁₀₆) = (43; 35) = 35

u₅ = min (u₆ – d₆₅; u₁₂ – d₁₂₅) = (28; 51) = 28

u₄ = min (u₅ – d₅₄; u₇ – d₇₄) = (18; 30) = 18

u₃ = min (u₅ – d₅₃) = 27

u₂ = min (u₅ – d₅₂; u₆ – d₆₂) = (20; 13) = 13

u₁ = min (u₂ – d₂₁; u₃ – d₃₁; u₄ – d₄₁) = (4; 23; 13) = 4

u₀ = min (u₁ – d₁₀) = 0

Событие	Ранний срок	Поздний срок	Резерв времени
0	0	0	0
1	4	4	0
2	13	13	0
3	8	27	19
4	9	18	9
5	21	28	7
6	35	35	0
7	15	36	1
8	21	42	21
9	44	52	8
10	44	44	0
11	56	56	0
12	57	57	0
13	70	70	0

Критический путь: 0 – 1 – 2 – 6 – 10 – 11 – 12 – 13 = 70

№ 11.

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

Вариант	11
Работа	Длительность выполнения работы, час
0—1	5
1—2	7
1—3	4
1—4	4
2—6	24
2—5	10
3—5	7
4—5	9
4—7	12
5—6	10
5—12	5
6—9	4
6—10	11
7—8	3
8—12	14
9—11	18
10—11	7
11—12	10
12—13	12

Решение:

Полагаем, что i₀ =0, i₁=5, узлам 2, 3 и 4 непосредственно предшествует только узел 1: i₂ = d₁₂ = 12, i₃ = d₁₃ = 9, i₄ = d₁₄ = 9. Далее находим:

i₅ = max (i₂+ d₂₅; i₃+ d₃₅; i₄ + d₄₅) = (22; 16; 18) = 22

i₆ = max (i₂+ d₂₆; i₅+ d₅₆) = (36; 32) = 36

i₇ = max (i₄ + d₄₇) = 21

i₈ = max (i₇ + d₇₈) = 24

i₉ = max (i₆ + d₆₉) =40

i₁₀ = max (i₆ + d₆₁₀) = 47

i₁₁ = max (i₉ + d₉₁₁; i₁₀ + d₁₀₁₁) = (58; 54) = 58

i₁₂ = max (i₈ + d₈₁₂; i₅ + d₅₁₂; i₁₁ + d₁₁₁₂) = (38; 27; 68) = 68

i₁₃ = max (i₁₂ + d₁₂₁₃) = 80

Поздний срок:

u₁₃ = 80

u₁₂ = min (u₁₃ – d₁₃₁₂) = 68

u₁₁ = min (u₁₂ – d₁₂₁₁) = 58

u₁₀ = min (u₁₁ – d₁₁₁₀) = 51

u₉ = min (u₁₁ – d₁₁₉) = 40

u₈ = min (u₁₂ – d₁₂₈) = 54

u₇ = min (u₈ – d₈₇) = 33

u₆ = min (u₉ – d₉₆; u₁₀ – d₁₀₆) = (36; 40) = 36

u₅ = min (u₆ – d₆₅; u₁₂ – d₁₂₅) = (26; 63) = 26

u₄ = min (u₅ – d₅₄; u₇ – d₇₄) = (17; 21) = 17

u₃ = min (u₅ – d₅₃) = 19

u₂ = min (u₅ – d₅₂; u₆ – d₆₂) = (16; 12) = 12

u₁ = min (u₂ – d₂₁; u₃ – d₃₁; u₄ – d₄₁) = (5; 15; 13) = 5

u₀ = min (u₁ – d₁₀) = 0

Событие	Ранний срок	Поздний срок	Резерв времени
0	0	0	0
1	5	5	0
2	12	12	0
3	9	19	10
4	9	17	8
5	22	26	4
6	36	36	0
7	21	33	12
8	24	54	30
9	40	40	0
10	47	51	4
11	58	58	0
12	68	68	0
13	80	80	0

Критический путь: 0 – 1 – 2 – 6 – 9 – 11 – 12 – 13 = 80

Список литературы

Алпатов, Ю.Н. Математическое моделирование производственных процессов: Учебное пособие / Ю.Н. Алпатов. - СПб.: Лань, 2018. - 136 c.
Асанов М. О., Баранский В. А., Расин В. В. — Дискретная математика: Графы, матроиды, алгоритмы: Учебное пособие. 2-е изд., испр. и доп. — СПб.: Издательство "Лань", 2010. — 368 с.
Белотелов, Н.В. Сложность. Математическое моделирование. Гуманитарный анализ: Исследование исторических, военных, социально-экономических и политических процессов / Н.В. Белотелов, Ю.И. Бродский, Ю.Н. Павловский. - М.: КД Либроком, 2019. - 320 c.
Волгина, О.А. Математическое моделирование экономических процессов и систем: Учебное пособие / О.А. Волгина, Н.Ю. Голодная, Н.Н. Одияко. - М.: КноРус, 2016. - 395 c.
Жирков, А.М. Математическое моделирование систем и процессов: Учебное пособие / А.М. Жирков, Г.М. Подопригора, М.Р. Цуцунава. - СПб.: Лань КПТ, 2016. - 192 c.
Катаргин, Н.В. Экономико-математическое моделирование: Учебное пособие / Н.В. Катаргин. - СПб.: Лань, 2018. - 256 c.
Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд Алгоритмы: построение и анализ, 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.
Михалева, М.Ю. Математическое моделирование и количественные методы исследований в менеджменте: Учебное пособие / М.Ю. Михалева, И.В. Орлова. - М.: Вузовский учебник, 2019. - 320 c.
Степанов, В.И. Экономико-математическое моделирование / В.И. Степанов. - М.: Academia, 2018. - 336 c.
Яглом, И.М. Математические структуры и математическое моделирование / И.М. Яглом. - М.: Ленанд, 2018. - 144 c.