Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Постановка задачи о максимальном потоке ⇐ ПредыдущаяСтр 2 из 2
Рассмотрим сеть трубопроводов для транспортировки сырой нефти от буровых скважин до нефтеперерабатывающих заводов. Каждый сегмент трубопровода имеет свою пропускную способность. Сегменты могут быть как однонаправленные, так и двунаправленные. Требуется определить максимальный поток между скважинами и заводами Разрез определяет множество ребер, при удалении которых из сети полностью прекращается поток от источника к стоку. Разрез с минимальной пропускной способностью определяет максимальный поток в сети.
Перебор всех разрезов – непростая задача. Идея алгоритма нахождения максимального потока состоит в нахождении сквозных путей с положительными потоками от источника к стоку. Нахождение очередного сквозного пути предполагает задействование части пропусной спосообности ребер. Поэтому следующий сквозной путь ищется на остаточной сети. Максимальный поток вычисляется как сумма потоков в сквозных путях. Задача о максимальном потоке в виде модели линейного программирования Технология моделирования оптимизационных задач нелинейного программирования (ЗНП). Общая классификация ЗНП. Основные подходы к оптимизации ЗНП. Нелинейное программирование – это класс моделей и методов оптимального программирования, в которых хотя бы одно из математических выражений представляет собой нелинейную функцию. Основные свойства задач нелинейного программирования Множество допустимых планов может иметь очень сложную структуру (например, быть невыпуклым или несвязным). Глобальный максимум (минимум) может достигаться как внутри множества допустимых значений, так и на его границах. Целевая функция f может быть недифференцируемой, что затрудняет применение классических методов математического анализа. Общая классификация задач нелинейного программирования
В экономических приложениях рассматриваются следующие классы задач нелинейного программирования: нелинейные задачи безусловной оптимизации; нелинейные задачи условной оптимизации. Основные подходы к оптимизации нелинейных задач
Проблемы: • нет универсальных алгоритмов поиска глобального минимума • неясно, как выбрать начальное приближение (зависит от задачи и интуиции) Основные подходы: • методы локальной оптимизации (результат зависит от выбора начального приближения) • случайный поиск (без гарантии) • методы глобальной оптимизации (для особых классов функций).
Технология прямой условной оптимизации задач нелинейного программирования. Численные методы решения ЗНП. Эволюционные методы решения ЗНП. |
Последнее изменение этой страницы: 2019-04-10; Просмотров: 245; Нарушение авторского права страницы