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