Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






  • Задача о максимальном потоке

    Элементы теории графов. Оптимизация на графах

    Оптимизация – поиск наилучшего по какому-либо критерию решения из возможных.

    Задача о максимальном потоке

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

    Уже первое рассмотрение сети позволяет сделать вывод, что из узла (1) – источника не может вытекать поток более чем 8 + 2 = 10, а в узел (4) - сток не может втекать поток более чем 6 + 1 = 7, ведь потоку приходится проходить именно по дугам с такими пропуск­ными способностями. Понятно, что поток не будет превышать min (10, 7) = 7.

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

    Задача решается на основе теоремы о максимальном потоке:

    Максимальный поток = минимальному разрезу.

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

    На рисунке примера минимальным разрезом будет {(1, 2), (3, 4)}. Сумма пропускных способ­ностей его 2+1=3 – самая маленькая, значит, и максимальный поток через данную сеть будет иметь значение 3.

    Задача сетевого планирования

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

    1). время начала каждой из работ;

    2). время окончания всего комплекса.

    Рассмотрим пример:

    Работа Время выполнения Работы, которые должны быть выполнены предварительно
    1.    
    2.    
    3.    
    4.   1, 2
    5.   3, 4

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

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

    Вводятся две фиктивные работы: «Начало» и «Конец» работ, и соединяются со всеми источниками и стоками соответственно. Фиктивные работы не требуют времени выполнения, их иногда называют событиями.

    Задачи сформулированные в начале сводятся к одной: оценки времени начала работы. Действительно, время, необходимое для всего комплекса совпадет со временем начала фиктивной работы «Конец» работ.

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

     

    Работа           К
    Начало     0+5 0+5 0+5+3 0+5+3+6
    <== предыдущая лекция | следующая лекция ==>
     | Фонетика мен лексикология




    © 2023 :: MyLektsii.ru :: Мои Лекции
    Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
    Копирование текстов разрешено только с указанием индексируемой ссылки на источник.