Исследование операций на примере ОАО "АвиаМоторс"
Дипломная работа - Менеджмент
Другие дипломы по предмету Менеджмент
шины второго уровня.
.Выделение уровней и нумерация продолжается вплоть до последней вершины.
Упорядочим нумерацию вершин графа, следуя данному алгоритму:
Рисунок 4.6 - Изоморфный граф
В узел 1 графа задания (рис. 4.2) не входит ни одной дуги, а выходят дуги (1,3), (1,4). Присваиваем узлу 1 номер 1, изображаем этот узел на рис. 4.6 вместе с выходящими из него дугами и мысленно удаляем эту вершину из исходного графа.
Среди оставшихся узлов графа в узел 2 теперь не входит ни одной дуги. Присваиваем узлу номера 2 соответственно и изображаем на рис.4.6. Мысленно удаляем эту вершину вместе с инцидентными ей дугами из графа.
Теперь в узел 3 не входит ни одной дуги. Присваиваем этой вершине номера 3 и переносим ее на рис. 4.6 и мысленно удаляем из графа.
Далее мы видим, что в узел 4 не входит ни одной дуги. Присваиваем ему номер 4 и переносим на новый рисунок, мысленно удалив его из исходного графа.
После проделанной операции остался узел 5 без входящих в него дуг. Присваиваем ему номер 5 и переносим на новый рисунок, мысленно удалив его из исходного графа.
Среди оставшихся узлов графа в узел 6 теперь не входит ни одной дуги. Присваиваем узлу номера 6 соответственно и изображаем на рис.4.6. Мысленно удаляем эту вершину вместе с инцидентными ей дугами из графа.
Теперь в узел 7 не входит ни одной дуги. Присваиваем этой вершине номера 7 , переносим ее на рис. 4.6 и мысленно удаляем из графа.
Остался единственный узел 8 без входящих и выходящих из него дуг. Присваиваем этому узлу номер 8 и изображаем на рис. 4.6.
Таким образом, у нас получился новый упорядоченный граф (рис. 4.6), изоморфный исходному графу (рис. 4.2).
. Максимальная мощность потока.
Алгоритм определения максимального потока:
1.Строится начальный поток
.Выявляются подмножества А вершин, достижимых из истока I по ненасыщенным ребрам. Если при этом сток S не попадет в подмножество А, то построенный поток является максимальным, и задача решена. Если же сток S попадает в подмножество А, то следует перейти к следующему пункту алгоритма.
Таблица 4.2 - Матрицы слева - пропускных способностей ребер, справа - начального потока
N12345678N123456781 65 1 14 2 7 3 3 2 0 00 3-6-7 3 5 2 3-10 100 4-5 -3 749 4-4 -1 140 5 -3-5-7 2 5 00-1 1 6 -3-2-4-2 146 00-4-1 147 -9-157 0 -1 18 -4-5 8 -4-1
В соответствии с пунктом 1 алгоритма на сети необходимо сформировать начальный поток. Опираясь на таблицу 4.2, составим маршрут, по которому проходит поток . Для составления маршрута будем двигаться от истока I=1 в направлении вершины с меньшими номерами до тех пор, пока не достигнем стока S=8
линейный транспортный задача граф
: 1 - (6)3- (3)4 - (7)5 - (2)6 - (1)7 - (5)8
Максимальный поток, который может пройти по маршруту , величину общего потока ограничивает поток ребра (6,7), которое становится насыщенным.
: 1 - (5)4 - (4)6 - (4)8
Максимальный поток, который может пройти по маршруту , величину общего потока ограничивают потоки ребер (4,6) и (6,8), которые становятся насыщенными
.
Составляем матрицу , которая определяет пропускную способность сети при условии, что через нее проходит поток . Используя данные таблицы 4.3, составим маршруты дополнительных потоков, проходящие через ненасыщенные ребра.
: 1 - (5)3 - (2)4 - (9)7 - (4)8
Максимальный поток, который может пройти по маршруту , величину общего потока ограничивает поток ребра (3,4), которое становится насыщенным.
Составляем матрицу , которая определяет пропускную способность сети.
: 1 - (1)4 - (7)7 - (2)8
Максимальный поток, который может пройти по маршруту , величину общего потока ограничивает поток ребра (1,4), которое становится насыщенным.
Составляем матрицу , которая определяет пропускную способность сети. Для этого из элементов левой таблицы 4.4 вычитаем элементы правой.
Так как больше маршрутов нет, заканчиваем решение и считаем максимальный поток.
Рис. 4.7 - максимальные потоки и резервы дуг
. Сетевой граф
Сетевой граф - граф, вершины которого отображают состояния некоторого процесса (производство запчастей для автомобиля), а дуги - работы, ведущиеся в этом процессе. Каждой дуге сопоставляется время, за которое осуществляется работа и/или число рабочих, которые осуществляют работу.
В сетевом графе между начальным и конечным событиями может быть несколько путей.
Критический путь - непрерывная последовательность работ и событий от начального до конечного события, требующая наибольшего времени (затрат) для ее выполнения. Термин сетевого планирования, означающий самый длинный по временной протяженности путь в сетевом графе, определяющий продолжительность работ по выполнению проекта.
Особое значение для сетевого графа имеют следующие понятия:
Ранний срок свершения события - минимальное время, к которому необходимо завершить все работы, предшествующие этому событию.
Поздний срок свершения события - момент времени, после которого остается ровно столько времени, сколько необходимо для завершения всех работ, следующих за этим событием.
При оценке резервов времени удобно использовать еще два вспомогательных понятия:
Ранний срок окончания работы - срок, раньше которого нельзя закончить данную работу. Он равен сумме раннего срока свершения работы и продолжительности данной работы.
Поздний срок начала работы - срок, позже которого нельзя начинать данную работу, не увеличив общую продолжительность строительства. Он равен