Эвристика (и/или контрольные списки), чтобы решить, действительно ли рассматриваемая проблема является линейной программой.
Вот моя попытка ответить, и я также попытался обрисовать в общих чертах, как я подхожу к этой проблеме.
Вопросы, указывающие на то, что данная проблема подходит для формулировки в виде LP/IP:
- Есть ли решения, которые нужно принимать регулярно, через разные промежутки времени?
- Есть ли ряд ресурсов (рабочие, машины, транспортные средства), которым необходимо назначить задачи? (часы, работа, направления)
- Является ли это проблемой маршрутизации, когда необходимо посетить разные «точки»?
- Это проблема местоположения или "макета"? (В эту группу попадает весь класс задач по раскрою.)
Ответ «да» на эти вопросы означает, что формулировка LP может работать.
Часто встречающиеся LP включают: Распределение ресурсов.: (Назначение, Транспортировка, Перегрузка, Рюкзак), Распределение портфеля, Планирование работы и проблемы с сетевым потоком. Вот хороший список приложений LP для тех, кто плохо знаком с LP или IP. Тем не менее, существует буквально 1000 различных типов задач, которые можно сформулировать как LP/IP. Люди, с которыми я работал (исследователи, коллеги), развивают интуицию. Они хорошо понимают, что проблема представляет собой определенный тип Целочисленной Программы, даже если они не помнят деталей, которые они могут затем найти.
Почему на этот вопрос сложно ответить. Есть много причин, по которым не всегда просто узнать, подойдет ли формула LP.
- В подходе к моделированию/формулированию много «искусства» (субъективности).
- Опыт очень помогает. Люди хорошо понимают, что эту проблему можно «уподобить» другой известной формулировке.
- Даже если проблема не является прямым LP, существует много умных методов master-slave (подзадачи) или методов вложенности, которые заставляют работать формулировку в целом.
- То, что выглядит как несколько целей, может быть объединено в одну целевую функцию с соответствующим набором весов.
- Опытные разработчики моделей используют методы декомпозиции и релаксации ограничений, а затем компенсируют это.
Как действовать, чтобы выполнить базовую формулировку?
Следующее всегда направляло меня в правильном направлении. Обычно я начинаю с перечисления переменных решения, ограничений и целевой функции. Затем я обычно перебираю эти три, чтобы убедиться, что все «подходит».
Итак, если у вас есть проблема, спросите себя:
- Что такое переменные решения (DV)? Я считаю, что это всегда хорошее место для начала процесса формулирования. Сколько существует типов DV? (Какой ресурс получает какую задачу и когда она должна запускаться?)
- Что такое ограничения?
Некоторые ограничения очень хорошо видны. Другие немного поддразнивают. Ограничения должны быть записаны с точки зрения переменных вашего решения и любых наложенных констант/ограничений.
- Что такое целевая функция?
Какие величины необходимо максимизировать или минимизировать? Примечание. Иногда неясно, что такое целевая функция. Это нормально, потому что это вполне может быть проблемой ограничения-удовлетворения.
Несколько быстрых проверок работоспособности, как только вы решите, что ваша формулировка LP готова:
- Я всегда стараюсь увидеть, не является ли тривиальное решение (все 0 или все большие числа) частью набора решений. Если да, то формулировка, скорее всего, неверна. Некоторое ограничение отсутствует.
- Убедитесь, что каждое ограничение «связано» с переменными решения. (Иногда я нахожу ограничения, которые просто «висят там». Это означает, что «ограничение бухгалтерского учета» было пропущено.)
По моему опыту, люди, которые продолжают это делать, почти всегда развивают необходимую интуицию. Надеюсь это поможет.
person
Ram Narasimhan
schedule
31.03.2012
