Main menu

Задача календарного планирования с ограниченными ресурсами (RCPSP)

Классические сетевые методы управления проектами, такие как PERT и CPM, строят идеалистические временные графики, опираясь исключительно на технологические зависимости между работами. Они предполагают, что у компании есть бесконечный запас рабочих, бульдозеров и финансов, чтобы выполнять любые параллельные задачи одновременно. В реальной жизни ресурсы всегда жестко ограничены. Как только мы вводим в математическую модель лимиты на доступный персонал или оборудование, простая задача вычисления критического пути мгновенно превращается в Задачу календарного планирования с ограниченными ресурсами (Resource-Constrained Project Scheduling Problem, RCPSP) — одну из самых трудных проблем дискретной оптимизации.

Подробнее

Искусственные пчелиные колонии (ABC): метаэвристики и глобальная оптимизация

Среди алгоритмов роевого интеллекта, применяемых в исследовании операций для решения NP-трудных задач нелинейной оптимизации, особое место занимает алгоритм искусственной пчелиной колонии (Artificial Bee Colony, ABC). Предложенный Дервишем Карабогой в 2005 году, этот метод был вдохновлен поразительно эффективным поведением медоносных пчел при поиске нектара. В отличие от строгих математических градиентных методов, которые беспомощно застревают в локальных оптимумах мультимодальных функций, алгоритм ABC использует элегантный баланс между случайным поиском и коллективным обменом информацией, позволяя находить глобальные экстремумы в многомерных пространствах с фантастической скоростью.

Подробнее

Анализ Парето-фронта: методы ε-ограничений (Epsilon-Constraint) и взвешенной суммы

Многокритериальная оптимизация редко способна выдать руководителю одно единственное идеальное решение. Главная задача аналитика — предоставить лицу, принимающему решение (ЛПР), исчерпывающую математическую картину всех возможных компромиссов. Геометрическим отражением этих компромиссов является фронт Парето — множество всех эффективных решений, где улучшение одного критерия неминуемо влечет ухудшение другого. Построение точного фронта Парето требует перевода векторной задачи в серию скалярных. Двумя фундаментальными алгебраическими подходами к аппроксимации этой границы являются метод взвешенной суммы и метод эпсилон-ограничений (Epsilon-Constraint), каждый из которых имеет свои скрытые математические особенности.

Подробнее

Соц. сети