Линейное программирование. Графы и их применение. Игровые модели

Размещено на http://www.allbest.ru/

Министерство образования Тульской области

Государственное образовательное учреждение среднего профессионального образования тульской области

"Тульский экономический колледж"

Курсовой проект

по дисциплине "Математические методы"

Студента гр.310П Леднева И.В.

Руководитель: Юрченко В.Н.

Щекино 2013

Задание на курсовую работу по дисциплине "Математические методы"

Задание 1. Линейное програмирование

В пояснительной записке должно быть описано:

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

2. Формы записи задачи линейного программирования.

3. Модель транспортной задачи.

4. Двойственная задача и двойственные оценки

5. Решить задачу линейного программирования

На четыре базы А1, А2, А3, А4 поступил однородный груз в следующем количестве: а 1 - на базу А1; а 2 т - на базу А2; а 3т - на базу А3; а 4т - на базу А4. Полученный груз требуется перевезти в пять пунктов:т - в пункт В 1; т - в пункт В 2; т - в пункт В; т - в пункт ; т - в пункт . Расстояния между пунктами назначения указаны в следующей таблице (матрице расстояний):

	25	19	16	24	20
20	6	11	20	17	8
25	1	25	3	18	17
20	9	39	16	30	31
25	23	15	4	3	28

6. Используя табличный процессор Excel решить задачу линейного программирования

Задание 2. Графы и их применение

В пояснительной записке должно быть описано:

1. Основные понятия и определения теории графов.

2. Основные понятия сетевого графика

3. Правила расчета основных параметров сетевого графика

4. Оптимизация сетевого графика

5. Рассчитать параметры сетевого графика

Дано. Коды работ, их продолжительность (таблица в соответствии с номером варианта).

Требуется:

· Построить сетевой график.

· Выполнить правильную нумерацию событий.

· Рассчитать параметры сетевого графика табличным методом.

· Определить критический путь.

Код работы	1-2	1-3	2-5	3-4	3-6	4-5	5-6	6-7	6-8	7-8
продолжительность	8	3	6	1	2	4	5	3	2	2

Задание 3. Игровые модели

В пояснительной записке раскрыть следующие вопросы: Место для формулы.

1. Основные понятия теории игр.

2. Классификация игр

3. Математическая формализация игровых задач

4. Найти решение игры с помощью критерия Гурвица, Севиджа, Лапласса.

Игра задана платежной матрицей.

	В 1	В 2	В 3	В 4
А 1	1	3	-5	12
А 2	-7	0	8	4
А 3	9	2	0	-11

Содержание

1. Линейное программирование

1.1 Постановка задачи линейного программирования

1.2 Формы записи задачи линейного программирования

1.3 Модель транспортной задачи

1.4 Двойственная задача и двойственная оценки

1.5 Задача линейного программирования

2. Графы и их применение

2.1 Основные понятия и определения теории графов

2.2 Основные понятия сетевого графика

2.3 Правила расчёта основных параметров сетевого графика

2.4 Оптимизация сетевого графика

2.5 Задача на расчёт параметров сетевого графика

3. Теория игр

3.1 Основные понятия теории игр

3.2 Классификация игр

3.3 Математическая формализация игровых задач

3.4 Задача на решение игры

Заключение

Список использованной литературы

Приложение. Листинг программы



1. Линейное программирование

1.1 Постановка задачи линейного программирования

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

F=c1x1+c2x2+…cnxn

при условиях

(1.1)

Сравнивая две сформулированные задачи, видим, что двойственная задача составляется согласно следующим правилам:

1. Целевая функция исходной задачи задается на максимум, а целевая функция двойственной на минимум.

2. Матрица



(1. 2)

составленная из коэффициентов при неизвестных в системе ограничений исходной задачи, и аналогичная матрица

(1.3)

в двойственной задаче получаются друг из друга транспонированием (т.е. заменой строк столбцами, а столбцов - строками).

3. Число переменных в двойственной задаче равно числу ограничений в системе исходной задачи, а число ограничений в системе двойственной задачи - числу переменных в исходной задаче.

4. Коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены в системе исходной задачи, а правыми частями в соотношениях системы двойственной задачи - коэффициенты при неизвестных в целевой функции исходной задачи.

5. Если переменная xj исходной задачи может принимать только лишь положительные значения, то j-е условие в системе двойственной задачи является неравенством вида ">". Если же переменная xj может принимать как положительные, так и отрицательные значения, то 1 - соотношение в системе представляет собой уравнение. Аналогичные связи имеют место между ограничениями исходной задачи и переменными двойственной задачи. Если i- соотношение в системе исходной задачи является неравенством, то i-я переменная двойственной задачи . В противном случае переменная уj может принимать как положительные, так и отрицательные значения.

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

Двойственная задача тесно связана задачей линейного программирования. Задача первоначальная называется исходной. Решение двойственной задачи может быть получено из решения исходной и наоборот. Связующим фактом этих двух задач являются коэффициенты Cj функции исходной задачи. Данные коэффициенты называются свободными членами системы ограничений двойственной задачи. Коэффициенты Bi системы ограничений исходной задачи называются коэффициентами двойственной задачи. Транспонированная матрица коэффициентов системы ограничений исходной задачи является матрицей коэффициентов системы ограничений двойственной задачи.

Рассмотрим задачу использования ресурсов. У предприятия есть tвидов ресурсов в количестве bi(i=1, 2,…, m) единиц, из которых выпускается n видов продукции. На изготовление 1 ед. i-й продукции тратится aijед. t-гo ресурса, ее стоимость составляет Cjед. Необходимо определить план выпуска продукции, обеспечивающий ее максимальный выпуск в стоимостном выражении. Примем за xj(j=1,2,…, n) количество ед. j-й продукций и составляет максимальное значение линейной функции

Z=C1x1+C2x2+ … +Cnxn

Определим ресурсы, которые потребуются для изготовления товара. Обозначим за единицу стоимости ресурсов единицу стоимости выпускаемого товара. А через уi(j=1,2,…, m) стоимость единицы i-го ресурса. Т.е. стоимость всех затраченных ресурсов, которые используются для изобретения единицы j-й продукции, составляет. Цена израсходованных ресурсов не должна превышать цены окончательного товара.

1.2 Формы записи задачи линейного программирования

программирование граф формализация алгоритм

Имеются некоторые стандартные формы задач линейного программирования, к которым и приводят различные конкретные задачи.

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

, , (1.4)

и т.д. Обозначение будет означать, что

Соответственно, запись о значает, что

Первая стандартная форма задачи линейного программирования имеет вид



(1.5)

Введем вектора

; ; ,

a также вектора

,

и матрицу

.

Заметим, что комбинация



есть не что иное, как скалярное произведение векторов и . Поэтому в векторной форме задача (1.2)примет вид

(1.6)

Можно использовать и матричные обозначения. Тогда комбинация

есть произведение и задача (1.7) примет вид

(1.7)

Вторая стандартная форма задачи линейного программирования имеет вид

(1.8)

В векторной форме эта задача имеет вид



(1.9)

и в матричной форме - вид

(1.10)

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

(1.11)

В векторной форме эта задача имеет вид

(1.12)

и в матричной форме - вид

(1.13)



Во всех этих задачах функцию

называют целевой функцией. Вектор

называют вектором коэффициентов линейной формы, вектор

- вектором ограничений.

Матрицу называют матрицей коэффициентов.

Любой набор чисел

,

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

1.3 Модель транспортной задачи

Закрытая модель транспортной задачи

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

Доказательство. Пусть =M>0 .

Тогда величины

xij = aibj /M (i = 1,2,3, ... m; j = 1,2,3, ..., n)

являются планом, так как они удовлетворяют системе ограничений (2)и(3) т. е. линейная функция ограничена на множестве планов транспортной задачи.

Открытая модель транспортной задачи

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

a) суммарные запасы превышают суммарные потребности;

b) суммарные потребности превышают суммарные запасы.

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

Найти минимальное значение линейной функции

при ограничениях

, i=1,2,...,m, (случай а)

, j=1,2,...,n;

, i=1,2,...,m, (случай б)

, j=1,2,...,n,

xij0 (i=1,2,...,m; j=1,2,...,n).

Открытая модель решается приведением к закрытой модели.

В случае (а), когда суммарные запасы превышают суммарные потребности, вводится фиктивный потребитель Bn+1, потребности которого bn+1 = . В случае (б), когда суммарные потребности превышают суммарные запасы, вводится фиктивный поставщик Am+1, запасы которого am+1 = .

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

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

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

1.4 Двойственная задача и двойственная оценки

С экономической точки зрения двойственную задачу можно интерпретировать так: какова должна быть цена единицы каждого из ресурсов, чтобы при заданных количествах ресурсов biи величинах стоимости единицы продукции Cj минимизировать общую стоимость затрат? А исходную задачу определим следующим, образом: сколько и какой продукции xj(j=1,2,…, n) необходимо произвести, чтобы при заданных стоимостях Cj (j=1,2,…, n) единицы продукции и размерах имеющихся ресурсов bi(i=1,2,…, n) максимизировать выпуск продукции в стоимостном выражении. Большинство задач линейного программирования изначально определяются как исходные или двойственные задачи. Сделав вывод можно говорить о паре двойственных задач линейного программирования.

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

F=c1x1+c2x2+…cnxn

при условия

(1.14)

Сравнивая две сформулированные задачи, видим, что двойственная задача составляется согласно следующим правилам:

1. Целевая функция исходной задачи задается на максимум, а целевая функция двойственной на минимум.

2. Матрица

(1.15)

составленная из коэффициентов при неизвестных в системе ограничений исходной задачи, и аналогичная матрица



(1.16)

в двойственной задаче получаются друг из друга транспонированием (т.е. заменой строк столбцами, а столбцов - строками).

3. Число переменных в двойственной задаче равно числу ограничений в системе исходной задачи, а число ограничений в системе двойственной задачи - числу переменных в исходной задаче.

4. Коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены в системе исходной задачи, а правыми частями в соотношениях системы двойственной задачи - коэффициенты при неизвестных в целевой функции исходной задачи.

5. Если переменная xj исходной задачи может принимать только лишь положительные значения, то j-е условие в системе двойственной задачи является неравенством вида ">". Если же переменная xj может принимать как положительные, так и отрицательные значения, то 1 - соотношение в системе представляет собой уравнение. Аналогичные связи имеют место между ограничениями исходной задачи и переменными двойственной задачи. Если i- соотношение в системе исходной задачи является неравенством, то i-я переменная двойственной задачи . В противном случае переменная уj может принимать как положительные, так и отрицательные значения.

Двойственные пары задач обычно подразделяют на симметричные и несимметричные. В симметричной паре двойственных задач ограничения прямой задачи и соотношения двойственной задачи являются неравенствами вида "". Таким образом, переменные обеих задач могут принимать только лишь неотрицательные значения. Двойственная задача тесно связана задачей линейного программирования. Задача первоначальная называется исходной. Решение двойственной задачи может быть получено из решения исходной и наоборот. Связующим фактом этих двух задач являются коэффициенты Cj функции исходной задачи. Данные коэффициенты называются свободными членами системы ограничений двойственной задачи. Коэффициенты Bi системы ограничений исходной задачи называются коэффициентами двойственной задачи. Транспонированная матрица коэффициентов системы ограничений исходной задачи является матрицей коэффициентов системы ограничений двойственной задачи.

Рассмотрим задачу использования ресурсов. У предприятия есть tвидов ресурсов в количестве bi(i=1, 2,…, m) единиц, из которых выпускается n видов продукции. На изготовление 1 ед. i-й продукции тратится aijед. t-гo ресурса, ее стоимость составляет Cjед. Необходимо определить план выпуска продукции, обеспечивающий ее максимальный выпуск в стоимостном выражении. Примем за xj(j=1,2,…, n) количество ед. j-й продукций и составляет максимальное значение линейной функции

Z=C1x1+C2x2+ … +Cnxn

Определим ресурсы, которые потребуются для изготовления товара. Обозначим за единицу стоимости ресурсов единицу стоимости выпускаемого товара. А через уi(j=1,2,…, m) стоимость единицы i-го ресурса. Т.е. стоимость всех затраченных ресурсов, которые используются для изобретения единицы j-й продукции, составляет. Цена израсходованных ресурсов не должна превышать цены окончательного товара.

1.5 Задача линейного программирования

	25	19	16	24	20
20	6	11	20	17	8
25	1	25	3	18	17
20	9	39	16	30	31
25	23	15	4	3	28

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

Определим максимальное значение целевой функции

F(X) = 25x1 + 19x2 + 16x3 + 24x4 + 20x5

при следующих условиях-ограничений.

6x1 + 11x2 + 20x3 + 17x4 + 8x5?20

x1 + 25x2 + 3x3 + 18x4 + 17x5?25

9x1 + 39x2 + 16x3 + 30x4 + 31x5?20

23x1 + 15x2 + 4x3 + 3x4 + 28x5?25

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

6x1 + 11x2 + 20x3 + 17x4 + 8x5 + 1x6 + 0x7 + 0x8 + 0x9 = 20

1x1 + 25x2 + 3x3 + 18x4 + 17x5 + 0x6 + 1x7 + 0x8 + 0x9 = 25

9x1 + 39x2 + 16x3 + 30x4 + 31x5 + 0x6 + 0x7 + 1x8 + 0x9 = 20

23x1 + 15x2 + 4x3 + 3x4 + 28x5 + 0x6 + 0x7 + 0x8 + 1x9 = 25

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

Таблица 1

6	11	20	17	8	1	0	0	0
1	25	3	18	17	0	1	0	0
9	39	16	30	31	0	0	1	0
23	15	4	3	28	0	0	0	1



Решим систему уравнений относительно базисных переменных:

x6, x7, x8, x9,

Полагая, что свободные переменные равны 0, получим первый опорный план: X1 = (0,0,0,0,0,20,25,20,25)

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9
x6	20	6	11	20	17	8	1	0	0	0
x7	25	1	25	3	18	17	0	1	0	0
x8	20	9	39	16	30	31	0	0	1	0
x9	25	23	15	4	3	28	0	0	0	1
F(X0)	0	-25	-19	-16	-24	-20	0	0	0	0

Переходим к основному алгоритму симплекс-метода.

Итерация №0.

Текущий опорный план не оптимален, так как в индексной строке находятся отрицательные коэффициенты.

В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.

Вычислим значения Di по строкам как частное от деления: bi / ai1 и из них выберем наименьшее.

Следовательно, 4-ая строка является ведущей.

Разрешающий элемент равен (23) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9	min
x6	20	6	11	20	17	8	1	0	0	0	31/3
x7	25	1	25	3	18	17	0	1	0	0	25
x8	20	9	39	16	30	31	0	0	1	0	22/9
x9	25	23	15	4	3	28	0	0	0	1	12/23
F(X1)	0	-25	-19	-16	-24	-20	0	0	0	0	0



Получаем новую симплекс-таблицу:

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9
x6	1311/23	0	72/23	1822/23	165/23	16/23	1	0	0	-6/23
x7	2321/23	0	248/23	219/23	1720/23	1518/23	0	1	0	-1/23
x8	105/23	0	333/23	1410/23	2819/23	201/23	0	0	1	-9/23
x1	12/23	1	15/23	4/23	3/23	15/23	0	0	0	1/23
F(X1)	274/23	0	-216/23	-1115/23	-2017/23	1010/23	0	0	0	12/23

Итерация №1.

Текущий опорный план не оптимален, так как в индексной строке находятся отрицательные коэффициенты.

В качестве ведущего выберем столбец, соответствующий переменной x4, так как это наибольший коэффициент по модулю.

Вычислим значения Di по строкам как частное от деления: bi / ai4 и из них выберем наименьшее:

Следовательно, 3-ая строка является ведущей.

Разрешающий элемент равен (2819/23) и находится на пересечении ведущего столбца и ведущей строки.

Базис

B

x1

x2

x3

x4

x5

x6

x7

x8

x9

min

x6

1311/23

0

72/23

1822/23

165/23

16/23

1

0

0

-6/23

310/373

x7

2321/23

0

248/23

219/23

1720/23

1518/23

0

1

0

-1/23

1139/411

x8

105/23

0

333/23

1410/23

2819/23

201/23

0

0

1

-9/23

235/663

x1

12/23

1

15/23

4/23

3/23

15/23

0

0

0

1/23

81/3

F(X2)

274/23

0

-216/23

-1115/23

-2017/23

1010/23

0

0

0

12/23

0

Получаем новую симплекс-таблицу:

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9
x6	7484/663	0	-11122/221	10554/663	0	-10385/663	1	0	-373/663	-9/221
x7	17128/221	0	3179/221	-627/221	0	379/221	0	1	-137/221	44/221
x4	235/663	0	133/221	332/663	1	461/663	0	0	23/663	-3/221
x1	19/221	1	111/221	24/221	0	128/221	0	0	-1/221	10/221
F(X2)	34116/221	0	2131/221	-159/221	0	24189/221	0	0	159/221	178/221

Итерация №2.

Текущий опорный план не оптимален, так как в индексной строке находятся отрицательные коэффициенты.

В качестве ведущего выберем столбец, соответствующий переменной x3, так как это наибольший коэффициент по модулю.

Вычислим значения Di по строкам как частное от деления: bi / ai3 и из них выберем наименьшее:

Следовательно, 3-ая строка является ведущей.

Разрешающий элемент равен (332/663) и находится на пересечении ведущего столбца и ведущей строки.

Базис

B

x1

x2

x3

x4

x5

x6

x7

x8

x9

min

x6

7484/663

0

-11122/221

10554/663

0

-10385/663

1

0

-373/663

-9/221

5125/7184

x7

17128/221

0

3179/221

-627/221

0

379/221

0

1

-137/221

44/221

-

x4

235/663

0

133/221

332/663

1

461/663

0

0

23/663

-3/221

235/332

x1

19/221

1

111/221

24/221

0

128/221

0

0

-1/221

10/221

97/12

F(X3)

34116/221

0

2131/221

-159/221

0

24189/221

0

0

159/221

178/221

0

Получаем новую симплекс-таблицу:

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9
x6	5/83	0	-3635/83	0	-2153/83	-2552/83	1	0	-126/83	21/83
x7	21303/332	0	17143/166	0	1275/332	11285/332	0	1	-65/332	11/332
x3	235/332	0	249/166	1	1331/332	1129/332	0	0	23/332	-9/332
x1	80/83	1	21/83	0	-18/83	81/83	0	0	-1/83	4/83
F(X3)	3535/83	0	244/83	0	244/83	2651/83	0	0	67/83	64/83

Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план

Окончательный вариант симплекс-таблицы:

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9
x6	5/83	0	-3635/83	0	-2153/83	-2552/83	1	0	-126/83	21/83
x7	21303/332	0	17143/166	0	1275/332	11285/332	0	1	-65/332	11/332
x3	235/332	0	249/166	1	1331/332	1129/332	0	0	23/332	-9/332
x1	80/83	1	21/83	0	-18/83	81/83	0	0	-1/83	4/83
F(X4)	3535/83	0	244/83	0	244/83	2651/83	0	0	67/83	64/83

Оптимальный план можно записать так:

x3 = 235/332

x1 = 80/83

F(X) = 16*235/332 + 25*80/83 = 352905/6889



2. Графы и их применение

2.1 Основные понятия и определения теории графов

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

Граф - это совокупность двух множеств: множества точек, которые называются вершинами, и множества ребер А. Каждый элемент есть упорядоченная пара элементов множества , вершины и называются концевыми точками или концами ребра а. Граф называется конечным, если множества R и конечны.

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

,

то говорят, что a есть неориентированное ребро; если же этот порядок существенен, то a называется ориентированным ребром (ориентированное ребро часто называется дугой). В последнем случае называется также начальной вершиной, а - конечной вершиной ребра a. Граф называется неориентированным, если каждое его ребро не ориентировано, и ориентированным, если ориентированы все его ребра. В ряде случаев естественно рассматривать смешанные графы, имеющие как ориентированные, так и неориентированные ребра.

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

Число ребер, инцидентных одной вершине , будем обозначать через . Это число называется локальной степенью или просто степенью графа в вершине . В случае ориентированного графа G обозначим через и число ребер, соответственно выходящих из вершины и входящих в . Эти числа называются локальными степенями G в . Если все числа конечны, то граф называется локально-конечным. Вершина степени 1 называется висячей. Вершина степени 0 называется изолированной.

Рисунок 1.

На рис. 1 и - параллельные ребра, - петля; вершина и ребро инцидентны друг другу; - смежные вершины, - смежные вершины; степень вершины равна трем, - висячая вершина, - изолированная.

Теорема 14.1. В графе G сумма степеней всех его вершин - число четное, равное удвоенному числу ребер графа

,

где n - число вершин графа, m - число его ребер.

Теорема 14.2. Число нечетных вершин любого графа, т. е. вершин, имеющих нечетную степень, четно.

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

Рисунок 2.

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

2.2 Основные понятия сетевого графика

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

Сетевой график (СГ) дает наглядную и понятную картину последовательности выполнения работ по реализации проекта (комплекса работ). Помимо того что такие графики показывают начало и окончание каждой работы (операции), они четко указывают на очередность выполнения работ (операций), а также показывают резервы времени, которыми обладают работы, не лежащие на критическом пути. На нем наглядно видны последствия запаздывания в выполнении любой работы с точки зрения времени реализации всего комплекса работ (проекта). Таким образом, СГ представляет цепи работ (операций) и событий, отражая их технологическую последовательность и связь в процессе достижения промежуточных и конечной цели.

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

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

Основными элементами сетевого графика являются работа (изображается стрелкой - квазивектором), событие (изображается кружком) и путь.

Работа - это любой трудовой процесс, характеризующийся затратами времени и ресурсов (например, сборка узла, изготовление детали, проектирование машины, какого-либо из ее узлов, разработка плана производства и т. п.) или только времени - старение, т. е. процесс или действие, которое нужно совершить, чтобы перейти от одного события к другому. Работа на графике изображается сплошной линией со стрелкой (>). К этому понятию Примыкает понятие "зависимость" или "фиктивная работа". Оно выражает только связь, зависимость отдельных работ и характеризует тот случай, когда для начала данной работы требуется завершение одной или нескольких работ (непосредственно предшествующих данной), причем эту связь работ нельзя выразить ни через временные, ни через какие-либо другие ресурсные затраты, так как этих затрат нет. На графике эта связь изображается пунктирной линией со стрелкой (>). Фиктивная работа представляет собой логическую связь между событиями и показывает зависимость начала выполнения какой-либо работы или совокупности работ от результатов выполнения другой или других и выполняется мгновенно.

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

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

2.3 Правила расчёта основных параметров сетевого графика

1) составление перечня всех работ,

2) определение продолжительности работ,

3) составление сетевого графика,

4) расчёт основных параметров сетевого графика,

5) определение критического пути,

6) анализ сетевого графика и его оптимизация.

Для построения сетевого графика необходимо составить таблицу с

перечнем всех событий и работ. Для оценки продолжительности работ

применяется вероятностный принцип, при этом ответственный представитель по

каждой работе делает две оценки и, на основе этих оценок, определяет

ожидаемое время по формуле:

3tMIN + 2tMАХ (2.1)

Расчёт основных временных параметров сетевого графика.

К основным параметрам описания сетевого графика относятся:

1) резервы времени событий,

2) резервы времени путей и работ.

Зная продолжительность всех работ, можно для любого события сети определить по определённому правилу более ранний из возможных сроков его свершения tpi и наиболее поздний из допустимого срока его свершения tпi. Для событий принадлежащих критическому пути tpi = tпi. Все события в сети, за исключением событий критического пути, имеют резервы времени, которые обозначаются:

Ri = tпi- tpi

Определение критического пути.

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

Критический путь проходит через события:

0-1-2-3-4-5-6-8-9-10-11-12-13-14-15-16-17-18-19-20

ТКР = 95 дней

Работы и события на критическом пути не имеют резервов времени.

Критический путь определяет ранний срок наступления завершающего события.

Поздний срок наступления завершающего события определяет заданный (директивный) срок.

2.4 Оптимизация сетевого графика

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

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

2.5 Задача на расчёт параметров сетевого графика

Код работы	1-2	1-3	2-5	3-4	3-6	4-5	5-6	6-7	6-8	7-8
продолжительность	8	3	6	1	2	4	5	3	2	2



Работа (i,j)	Количество предшествующих работ	Продолжит. tij	Ранние сроки: начало tijР.Н.	Ранние сроки: окончание tijР.О.	Поздние сроки: начало tijП.Н.	Поздние сроки:окончание tijП.О.	Резервы времени: полный tijП	Резервы времени: свободный tijС.В.	Резервы времени: событий Rj
(1,2)	0	8	0	8	0	8	0	0	0
(1,3)	0	3	0	3	6	9	6	0	6
(2,5)	1	6	8	14	8	14	0	0	0
(3,4)	1	1	3	4	9	10	6	0	6
(3,6)	1	2	3	5	17	19	14	14	0
(4,5)	1	4	4	8	10	14	6	6	0
(5,6)	2	5	14	19	14	19	0	0	0
(6,7)	2	3	19	22	19	22	0	0	0
(6,8)	2	2	19	21	22	24	3	3	0
(7,8)	1	2	22	24	22	24	0	0	0

Примечание.

а) графы 1 и 3 заполняются на основе исходных данных.

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

г) в графе 4 раннее начало работ, выходящих из исходного события, а раннее окончание этих работ равно их продолжительности (гр. 5). Раннее начало последующих работ определяется путем выбора максимального из сроков раннего окончания предшествующих работ. Количество сравниваемых сроков равно количеству предшествующих работ графы 2. Раннее начало последующих работ можно определить после того, как найдено раннее окончание предшествующих. В свою очередь раннее окончание каждой работы находится как сумма величин раннего начала и продолжительности данной работы;

г) продолжительность критического пути определяется после заполнения граф 4 и 5 как максимальная величина из сроков раннего окончания работ, которые ведут к завершающему событию 9;

д) найденная величина критического пути ТKP дням заносится в графу 7 для всех работ, ведущих к завершающему событию. Затем заполнение ведется снизу вверх. Находятся все работы, следующие за рассматриваемой, и определяются разности между поздним окончанием этих работ и их продолжительностями. Минимальная из величин заносится в графу 7;

е) в графе 6 позднее начало работы определяется как разность позднего окончания этих работ и их продолжительности (из значений графы 7 вычитаются данные графы 3);

ж) в графе 8 полный резерв времени работы определяется разностью между значениями граф 7 и 5. Если он равен нулю, то работа является критической;

з) в графе 10 резерв времени событий j определяется как разность позднего окончания работы, заканчивающегося событием j графы 7, и ранним началом работы, начинающимся событием j;

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

Критический путь: (1,2)(2,5)(5,6)(6,7)(7,8)

Продолжительность критического пути: 24

Анализ сетевого графика

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

Kc = npab / ncob

где Kc - коэффициент сложности сетевого графика; npab - количество работ, ед.; ncob - количество событий, ед.

Сетевые графики, имеющие коэффициент сложности от 1,0 до 1,5, являются простыми, от 1,51 до 2,0 - средней сложности, более 2,1 - сложными.

Kc = 10 / 8 = 1.25

Поскольку Kc < 1.5, то сетевой график является простым.

Коэффициентом напряженности КH работы Pi,j называется отношение продолжительности несовпадающих (заключенных между одними и теми же событиями) отрезков пути, одним из которых является путь максимальной продолжительности, проходящий через данную работу, а другим - критический путь:

где t(Lmax) - продолжительность максимального пути, проходящего через работу Pi,j, от начала до конца сетевого графика; tkp - продолжительность (длина) критического пути; t1kp - продолжительность отрезка рассматриваемого максимального пути, совпадающего с критическим путем.

Коэффициент напряженности КH работы Pi,j может изменяться в пределах от 0 (для работ, у которых отрезки максимального из путей, не совпадающие с критическим путем, состоят из фиктивных работ нулевой продолжительности) до 1 (для работ критического пути). Чем ближе к 1 коэффициент напряженности КH работы Pi,j, тем сложнее выполнить данную работу в установленные сроки. Чем ближе Кн работы Pi,j к нулю, тем большим относительным резервом обладает максимальный путь, проходящий через данную работу.

Вычисленные коэффициенты напряженности позволяют дополнительно классифицировать работы по зонам. В зависимости от величины Кн выделяют три зоны: критическую (Кн > 0,8); подкритическую (0,6 < Кн < 0,8); резервную (Кн < 0,6).



3. Теория игр

3.1 Основные понятия теории игр

Теория игр занимается изучением т.н. конфликтных ситуаций, где сталкиваются интересы индивидов, партий, государств и т. п.

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

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

Остановимся на классификации игр.

Интересы участников игры (игроков) могут оказаться несовпадающими и даже противоположными. В последнем случае игра называется антагонистической.

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