МАТЕМАТИЧЕСКИЕ МЕТОДЫ ТЕОРИИ ПРИНЯТИЯ РЕШЕНИЙ
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 вида событий:
· Исходное – это такое событие, с которого начинается выполнение комплекса работ (в него не входит ни одна дуга)
· Завершающее – это событие, соответствующее достижению конечной цели и завершению комплекса работ (из него не исходит ни одна дуга). Если сетевой график имеет несколько завершающих событий, то его называют многоцелевым.
· Промежуточные – все остальные события.
По количеству входящих в него работ события делятся на простые и сложные.
Моментом свершения события считается момент окончания всех входящих в это событие работ. Пока не выполнены все входящие в это событие работы, не может свершиться само событие, а следовательно, не может бы начата ни одна из непосредственно следующих за ним работ.
Работа – это производственный процесс, требующий затрат времени, труда и материальных ресурсов, который при его выполнении приводит к достижению определенных результатов.
Стоимость работы – это прямые денежные затраты, необходимые для ее выполнения, зависящие от продолжительности и условий выполнения этой работы.
Продолжительность работы – это время выполнения данной работы в единицах измерения, одинаковых для всех работ сетевого графика. Может быть как детерминированной, так и случайной величиной, задаваемой законом распределения.
Материальные и трудовые ресурсы характеризуются потребностью в физических единицах и количестве исполнителей, необходимых для выполнения данной работы.
Выделяют следующие виды работ:
· Действительная работа (–––>) – это процесс, требующий затрат времени и ресурсов (разработка проекта, подвоз материалов, выполнение монтажных работ и т. д.)
· Работа-ожидание (–∙–∙–∙–>) – процесс, требующий только затрат времени (затвердение бетона, естественная сушка штукатурки перед началом отделочных работ, рост растений и т. д.)
· Фиктивная работа (– – –>) – процесс, не требующий ни времени, ни ресурсов, а лишь указывающий на то, что возможность выполнения одной работы непосредственно зависит от результатов другой.