Роль целочисленного программирования в стратегическом инженерном планировании

Целое программирование (IP) является краеугольным камнем исследований и оптимизации операций, позволяя инженерам и менеджерам проектов принимать оптимальные решения, когда выбор по своей сути дискретен. В контексте стратегического планирования для крупномасштабных инженерных проектов модели IP используются для распределения ресурсов, планирования задач, выбора оборудования и систем проектирования при соблюдении множества ограничений. Когда неопределенность вводится - как это почти всегда бывает в реальных проектах - эти модели должны быть расширены, чтобы включать стохастические или надежные элементы. В этой статье рассматривается, как целое программирование может быть адаптировано для обработки неопределенности, обеспечивая основу для устойчивого и экономически эффективного планирования инженерных проектов.

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

Основы целочисленного программирования

Целая задача программирования — это математическая задача оптимизации, в которой некоторые или все переменные решения ограничены целыми значениями. Это ограничение интегральности имеет решающее значение для моделирования реальных ситуаций, когда решения включают целые блоки — например, количество генераторов для установки на электростанции, количество строительных бригад для назначения или бинарный выбор того, инвестировать ли в конкретную технологию. Общая форма целочисленной линейной программы:

cTx, подчиняющийся Ax ≤ b, x ∈ Zn (или подмножество целочисленных переменных).

Комбинаторный характер целочисленного программирования делает эти задачи вычислительно сложными. Однако достижения в алгоритмах (например, ветвящиеся и связанные, плоскости разреза, разложение) и коммерческих решателях (например, Gurobi, CPLEX, Xpress) позволили эффективно решать крупномасштабные модели IP. В инженерном стратегическом планировании модели IP часто включают тысячи целочисленных переменных и ограничений, представляющих сложные взаимозависимости между решениями.

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

Источники неопределенности в инженерных проектах

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

  • Неопределенность спроса — Будущий спрос на продукты, энергию или услуги редко известен с уверенностью. Например, требуемая мощность новой магистрали или энергосети зависит от роста населения, экономической активности и технологических сдвигов.
  • Неопределенность в стоимости — Цены на материалы, ставки труда и затраты на оборудование колеблются из-за рыночных условий, инфляции и сбоев в цепочке поставок. Бюджет строительного проекта может серьезно пострадать от неожиданного роста цен на сталь.
  • Неопределенность в отношении продолжительности выполнения задач проекта — Продолжительность выполнения задач проекта зависит от погоды, производительности труда, поломок оборудования и непредвиденных условий на объекте.
  • Регуляторная и политическая неопределенность — Изменения в природоохранных нормах, законах о зонировании или налоговых льготах могут изменить осуществимость или рентабельность проекта.
  • Технологическая неопределенность — Производительность и надежность новых технологий, таких как системы возобновляемых источников энергии или передовые производственные процессы, могут быть неопределенными.

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

Методы включения неопределенности

Стохастическое интегральное программирование

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

Математически двухступенчатая стохастическая целочисленная программа может быть написана как:

cTx + Eξ[[Q(x, ξ)], подчиняющийся Ax ≤ b, x ∈ Zn,

где Q(x, ξ) = min {qTy : Wy ≤ h — Tx, y ∈ Zm] для заданной реализации случайных величин ξ.

Эта формулировка, естественно, подходит для задач планирования инженерных мощностей. Например, при проектировании энергосистемы первым этапом может быть количество установленных ветровых турбин и солнечных панелей, в то время как решения второго этапа регулируют распределение мощности на основе фактической погоды и спроса. Ожидание обычно аппроксимируется конечным набором сценариев, что приводит к крупномасштабному детерминистическому эквиваленту IP, который может быть решен с использованием методов разложения, таких как разложение Бендеров или метод L-образной формы.

Надежная оптимизация

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

Надежная формула программирования целых чисел обычно включает полубесконечное ограничение: Ax(ξ) ≤ b для всех ξ ∈ U, где U — множество неопределенности. Для линейных ограничений со специальными структурами (например, интервальная неопределенность) проблема часто может быть переформулирована как детерминированный IP с использованием методов, таких как надежный аналог, как впервые предложенный Бен-Талом и Немировски. Современная надежная оптимизация распространяется на целые переменные с использованием таких методов, как структурированные наборы неопределенности и заложенная неопределенность (Bertsimas и Sim), которые контролируют степень консерватизма.

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

Сдержанное на случай программирование

Сдержанное на случай программирование (ССП) является еще одним стохастическим подходом, при котором ограничения должны сохраняться с заданной вероятностью. Например, ограничение может указывать на то, что бюджет проекта не должен превышаться с вероятностью не менее 95%. КПК может быть интегрирован с целыми переменными, хотя это часто приводит к сложным вероятностным ограничениям, которые требуют переформулирования с использованием распадов сценария или смешанных целых программных релаксации. КПК полезна, когда лица, принимающие решения, могут терпеть некоторый риск, но хотят связать вероятность нежелательных результатов.

Средняя приближенность выборки

Примерное среднее приближение (SAA) является практическим методом решения стохастических целочисленных программ, когда базовое распределение сложно. Он заменяет истинное ожидание средним значением выборки из набора случайно сгенерированных сценариев, затем решает результирующий детерминированный IP. SAA является асимптотически последовательным и может быть объединен со статистической валидизацией для оценки качества решения. Он особенно эффективен в инженерных приложениях, где имитационные модели могут генерировать сценарии, такие как интеграция возобновляемых источников энергии или проектирование логистической сети.

Приложения в инженерном стратегическом планировании

Планирование строительного проекта

Строительные проекты, как известно, подвержены неопределенности в продолжительности задач, доступности ресурсов и погоде. Целые модели программирования для планирования строительства часто включают бинарные переменные для последовательности задач (например, отношения приоритета) и целочисленные переменные для распределения ресурсов. В условиях неопределенности двухступенчатые стохастические формулы IP могут включать решения о сверхурочных или субподрядные действия в качестве регрессных действий. Надежная оптимизация может использоваться для создания графиков, которые поддерживают выполнимость даже тогда, когда продолжительность задач изменяется в пределах установленной в бюджете неопределенности.

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

Проектирование и планирование энергетических систем

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

Надежная оптимизация также применяется, особенно для обеспечения надежности системы в экстремальных условиях, таких как волны тепла или перебои с подачей топлива. Исследователи из Массачусетского технологического института разработали надежные модели планирования энергосистемы, которые защищают от самых суровых погодных условий. (см. Пример надежной бумаги оптимизации )

Оптимизация производственных процессов

В производстве стратегическое планирование включает в себя решения о местах расположения заводов, производственных линиях и политике инвентаризации. Неопределенность спроса, время выполнения заказа и отказы машин делают целочисленное программирование с неопределенностью естественным соответствием. Многоступенчатые стохастические модели IP могут захватывать динамические решения в течение периодов времени, такие как расширение мощностей или внедрение технологий. Например, производитель автомобилей может решить построить новый завод в регионе с неопределенными затратами на рабочую силу и спросом. Решение инвестировать сейчас или ждать является классической проблемой реальных опционов, которая может быть смоделирована с использованием стохастического целочисленного программирования.

Цепочка поставок и логистический дизайн

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

Рассмотрение осуществления

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

  • Методы разложения — Декомпозиция Бендеров (также называемая L-образным методом стохастического программирования) разделяет проблему на главную задачу (первая стадия) и подзадачи (вторая стадия по сценарию).
  • Снижение сценариев — Используя кластеризацию или выборку важности, большой набор сценариев может быть сведен к репрезентативному подмножеству при сохранении статистических свойств.
  • Прогрессивное хеджирование — эвристический алгоритм, который итеративно настраивает сценарные решения в сторону консенсуса, пригодного для крупномасштабных стохастических IP-адресов.
  • Коммерческие решатели — Современные решатели, такие как Gurobi и CPLEX, включают в себя специализированные возможности для стохастического программирования, такие как автоматическое разложение сценариев и параллельные Бендеры.См.

Для надежной оптимизации основной проблемой является размер набора неопределенности. Формулировки с бюджетной неопределенностью часто приводят к вычислительно тягостным программам с смешанным целым числом, в то время как более сложные наборы (например, эллипсоидные) могут потребовать конического целочисленного программирования или внешнего приближения. Программные инструменты и решатели теперь поддерживают надежные формулировки изначально; например, оптимизатор IBM CPLEX обеспечивает API для неопределенных параметров.

Также важно проверить модель с помощью тестирования вне выборки. Обычная практика заключается в решении IP с помощью обучающего набора сценариев, затем оценить производительность решения на отдельном тестовом наборе (или с помощью моделирования). Это помогает гарантировать, что модель не перестраивается на конкретный набор сценариев и что представление неопределенности является адекватным.

Последние достижения и будущие направления

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

  • Нежелательное к риску стохастическое программирование — Включение таких мер риска, как Условная стоимость в риске (CVaR) в цель или ограничения, позволяющие лицам, принимающим решения, контролировать хвостовые риски.
  • Дистрибутивно надежная оптимизация — Комбинирование элементов стохастической и надежной оптимизации, предполагая, что истинное распределение лежит в пределах набора двусмысленности, определяемого информацией о моменте или расстоянием Вассерштейна.
  • Интеграция машинного обучения — Использование машинного обучения для создания более совершенных деревьев сценариев, прогнозирования параметров неопределенности или даже изучения политик, которые приближают оптимальные решения стохастических IP.
  • Смешанное целое нелинейное программирование — Многие инженерные проблемы связаны с нелинейностью (например, квадратичные функции затрат, нелинейные уравнения потока мощности). Расширение обработки неопределенности до смешанных целых нелинейных программ остается активной областью исследований.

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

Заключение

Целое программирование является незаменимым инструментом стратегического планирования в инженерных проектах, обеспечивая строгую основу для принятия дискретных решений в условиях ограничений. Когда среда проекта неопределенна - как это почти всегда бывает - расширение моделей IP со стохастическими, надежными или случайными методами дает планы, которые являются оптимальными и устойчивыми. От планирования строительства до проектирования энергетической системы, эти модели помогают инженерам ориентироваться в рисках, контролировать затраты и обеспечивать успех проекта.

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

Для дальнейшего чтения по стохастическому целочисленному программированию и его приложениям страница ресурсов INFORMS предлагает отличные учебные пособия и тематические исследования.Кроме того, учебник «Введение в стохастическое программирование» Бирге и Луво обеспечивает комплексную обработку теории и алгоритмов.