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

 Рассмотрим сеть трубопроводов для транспортировки сырой нефти от буровых скважин до нефтеперерабатывающих заводов. Каждый сегмент трубопровода имеет свою пропускную способность.

 Сегменты могут быть как однонаправленные, так и двунаправленные.

 Требуется определить максимальный поток между скважинами и заводами

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

 Разрез с минимальной пропускной способностью определяет максимальный поток в сети.

 

 Перебор всех разрезов – непростая задача.

 Идея алгоритма нахождения максимального потока состоит в нахождении сквозных путей с положительными потоками от источника к стоку.

 Нахождение очередного сквозного пути предполагает задействование части пропусной спосообности ребер. Поэтому следующий сквозной путь ищется на остаточной сети.

 Максимальный поток вычисляется как сумма потоков в сквозных путях.

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

Технология моделирования оптимизационных задач нелинейного программирования (ЗНП). Общая классификация ЗНП. Основные подходы к оптимизации ЗНП.

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

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

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

 Глобальный максимум (минимум) может достигаться как внутри множества допустимых значений, так и на его границах.

 Целевая функция f может быть недифференцируемой, что затрудняет применение классических методов математического анализа.

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

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

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

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

Основные подходы к оптимизации нелинейных задач

Проблемы:

• нет универсальных алгоритмов поиска глобального минимума

 • неясно, как выбрать начальное приближение (зависит от задачи и интуиции)

Основные подходы: • методы локальной оптимизации (результат зависит от выбора начального приближения)

• случайный поиск (без гарантии)

• методы глобальной оптимизации (для особых классов функций).

 

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

⇐ Предыдущая12

Поделиться: