Понятие транспортной сети. Поток и разрез сети. Условия существования потока в сети. Пропускная способность сети.

Понятие транспортной сети. Поток и разрез сети. Условия существования потока в сети. Пропускная способность сети.

Транспортная сеть (flow network) — ориентированный граф в котором:

 каждому ребру приписана неотрицательная пропускная способность;

 выделены две вершины: источник (source) и сток (sink), такие, что любая другая вершина сети лежит на пути из источника в сток.

Потоком в транспортной сети называется неотрицательная вещественная функция, определенная на множестве дуг, удовлетворяющая условиям: 1.ограниченности: поток по любой дуге сети не превосходит пропускной способности этой дуги; 2.сохранения: суммарный поток , заходящий в любую вершину сети ( кроме истока и стока ) равен суммарному потоку , выходящему из этой вершины. Величиной потока называется сумма значений этой функции по всем выходным дугам сети ( выходные дуги сети - это дуги, инцидентные стоку). В общем случае потоки в сети ограничены пропускной способностью ее ребер Cij (пропускная способность участка дороги, пропускная способность телекоммуникационных каналов и т.д.).

Разрезом сети называется множество , которому принадлежит исток, и не принадлежит сток. Т.е. разрез - это минимальное (в смысле отношения включения) множество дуг, удаление которых “ разрывает” все пути, соединяющие исток и сток.

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

Теорема Форда-Фалкерсона.

В любой транспортной сети величина любого максимального потока равна пропускной способности любого минимального разреза.

 

 

Постановка задачи о максимальном потоке. Примеры практического приложения задачи. Представление задачи в форме модели линейного программирования.

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

Общая классификация задач нелинейного программирования

В экономических приложениях рассматриваются следующие классы задач нелинейного программирования:

 нелинейные задачи безусловной оптимизации;

 нелинейные задачи условной оптимизации.

Технология прямой условной оптимизации задач нелинейного программирования. Численные методы решения ЗНП. Эволюционные методы решения ЗНП.

Численные методы решения задач нелинейного программирования

 

Метод множителей Лагранжа

Приведем ниже алгоритм метода множителей Лагранжа решения задач нелинейного программирования.

Этап 1. Составляют функцию Лагранжа

Этап 2. Находят частные производные функции Лагранжа и приравнивают их к нулю

Этап З. Решают систему и определяют точки, в которых функция может иметь экстремум.

Этап 4. Проверяют полученные на этапе 3 точки на экстремум и определяют экстремальное значение функции найденной точки.

Понятие транспортной сети. Поток и разрез сети. Условия существования потока в сети. Пропускная способность сети.

Транспортная сеть (flow network) — ориентированный граф в котором:

 каждому ребру приписана неотрицательная пропускная способность;

 выделены две вершины: источник (source) и сток (sink), такие, что любая другая вершина сети лежит на пути из источника в сток.

Потоком в транспортной сети называется неотрицательная вещественная функция, определенная на множестве дуг, удовлетворяющая условиям: 1.ограниченности: поток по любой дуге сети не превосходит пропускной способности этой дуги; 2.сохранения: суммарный поток , заходящий в любую вершину сети ( кроме истока и стока ) равен суммарному потоку , выходящему из этой вершины. Величиной потока называется сумма значений этой функции по всем выходным дугам сети ( выходные дуги сети - это дуги, инцидентные стоку). В общем случае потоки в сети ограничены пропускной способностью ее ребер Cij (пропускная способность участка дороги, пропускная способность телекоммуникационных каналов и т.д.).

Разрезом сети называется множество , которому принадлежит исток, и не принадлежит сток. Т.е. разрез - это минимальное (в смысле отношения включения) множество дуг, удаление которых “ разрывает” все пути, соединяющие исток и сток.

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

Теорема Форда-Фалкерсона.

В любой транспортной сети величина любого максимального потока равна пропускной способности любого минимального разреза.

 

 

Постановка задачи о максимальном потоке. Примеры практического приложения задачи. Представление задачи в форме модели линейного программирования.

12Следующая ⇒

Поделиться: