Математические методы теории принятия решений

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

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

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

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

Л. С. Костевич «Математическое программирование» стр. 222-234

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

Л. С. Костевич «Математическое программирование» стр. 234-250

6. Оптимизация сетевых графиков по ресурсам.

Л. С. Костевич «Математическое программирование» стр. 250-263

7. Основные понятия теории массового обслуживания.

8. Основные классификации систем массового обслуживания.

9. Одноканальная система массового обслуживания с отказами.

10. Простейший пуассоновский поток.

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

Большое количество практических задач можно сформулировать и решать как сетевые модели. Например:

1) Проектирование нефте- и газопроводов;

2) Поиск кратчайшего пути между 2-мя городами по существующей сети дорог;

3) Определение максимальной пропускной способности трубопровода для транспортировки угля;

4) Составление временного графика строительных работ;

5) Определение схемы транспортировки нефти от пунктов нефтедобычи к нефтепереработки.

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

Математически графом G(V, E) называют совокупность двух множеств: непустого множества V – множества вершин и множества Е – пар элементов из V. Например, G(V, E)

V = {a, b, c, d},

E = {(a, b), (a, c),(a, d), (d, c)}.

Если элементы множества Е не упорядочены, то они называются ребрами, а граф – неориентированным. Если же элементы множества Е упорядочены, то они называются дугами, а граф – ориентированным или орграфом.

Путь в графе – это последовательность вершин, в которой 2 любые соседние вершины соединены, по крайней мере, одним ребром (дугой).

Путь формирует цикл, если начальная и конечная вершина пути совпадают.

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

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

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

Различают 3 вида событий:

· Исходное – это такое событие, с которого начинается выполнение комплекса работ (в него не входит ни одна дуга)

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

· Промежуточные – все остальные события.

По количеству входящих в него работ события делятся на простые и сложные.

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

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

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

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

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

Выделяют следующие виды работ:

· Действительная работа (–––>) – это процесс, требующий затрат времени и ресурсов (разработка проекта, подвоз материалов, выполнение монтажных работ и т. д.)

· Работа-ожидание (–∙–∙–∙–>) – процесс, требующий только затрат времени (затвердение бетона, естественная сушка штукатурки перед началом отделочных работ, рост растений и т. д.)

· Фиктивная работа (– – –>) – процесс, не требующий ни времени, ни ресурсов, а лишь указывающий на то, что возможность выполнения одной работы непосредственно зависит от результатов другой.