Студопедия

КАТЕГОРИИ:

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



Потоки на сетях. Постановка задачи о максимальном потоке




Читайте также:
  1. I. Задачи настоящей работы
  2. I. Цели и задачи проекта
  3. II. Основные цели и задачи Программы, срок и этапы ее реализации, целевые индикаторы и показатели
  4. II. Упражнения и задачи
  5. II. Упражнения и задачи
  6. II. Упражнения и задачи
  7. II. Цели и задачи проекта
  8. III. Для обеспечения проверки исходного уровня Ваших знаний-умений необходимому, предлагаем решить 2 задачи.
  9. III. Для обеспечения проверки исходного уровня Ваших знаний-умений необходимому, предлагаем решить 2 задачи.
  10. IV. Задачи для самостоятельной работы.

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

Для наглядности будем представлять, что по дугам из истока I в сток S направляется некоторое вещество (груз, ресурс, информация и т.п.)

Определение 12.8. Максимальное количество rij вещества, которое может пропустить за единицу времени дуга, идущая из вершины xi в xj называется его пропускной способностью. В общем случае rij ≠ rji .

Определение 12.9. Количество xij вещества, проходящего через дугу из вершины xi в xj в единицу времени, называется потоком по дуге.

Предполагается, что если из вершины xi в xj направляется поток величиной xij , то величина потока из xj в xi равна –xij , то есть xji = –xij. (12.1)

Принимается также, что xii=0. (12.2)

Определение 12.10. Совокупность X={xij} потоков по всем дугам сети называется потоком по сети или просто потоком.

Поток по любой дуге не превышает его пропускную способность:

xij ≤ rij . (12.3)

Если xij<rij , то дугу между вершинами xi и xj называют ненасыщенной.

Общее количество вещества, вытекающего из истока I, совпадает с общим количеством вещества, поступающего в сток S, то есть мощность потока (12.4),

где j – конечные вершины дуг, исходящих из I; i – начальные вершины дуг, входящих в S.

Задача о максимальном потоке формулируется следующим образом: найти совокупность X*={x*ij} потоков x*ij по всем дугам сети, которая удовлетворяет условиям (12.1) – (12.3) и максимизирует линейную функцию (12.4).

К задаче о максимальном потоке сводятся задачи: доставка груза; отыскание минимальной по стоимости плана выполнения комплекса работ при заданной его продолжительности; задачи, связанные с наиболее экономным строительством энергетических сетей и т.д.


Дата добавления: 2014-12-03; просмотров: 43; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2020 год. (0.006 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты