Полная версия

Главная arrow Психология arrow Искусство решать сложные задачи. Системный подход

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Целочисленное программирование

  • 1. Область применения. Используется для решения однокритериальных задач с детерминированной целевой функцией при ограничениях на значения переменных. Основной особенностью является то, что все или некоторые переменные должны принимать только целочисленные значения. Обычно это бывает при описании неделимых объектов (людей, машин и тому подобного) или при наложении жёстких ограничений типа равенств. В этом случае округление непрерывной величины несостоятельно, так как нет гарантии, что округлённое решение будет удовлетворять ограничениям. Если переменные являются булевыми, то есть принимают значения только ноль или единица, то округление вообще теряет смысл.
  • 2. Сущность. Задача целочисленного программирования формулируется как обычная задача математического программирования (смотри, например, формулировку задачи линейного программирования), но в алгоритме решения предусмотрен поиск специальных дополнительных ограничений на переменные, которые должны выделить множество решений, удовлетворяющих требованию целочисленности.
  • 3. Особенности применения. Алгоритмы решения задач целочисленного программирования неоднократно используют процедуры линейного программирования, время работы которого зависит от числа переменных и количества ограничений. Кроме того, возникают сложности с выбором специальных дополнительных ограничений (для отсечения области решений с нецелочисленными переменными), их часто приходится выбирать по эвристическим правилам, разработанным в ходе вычислительного эксперимента.
  • 4. Наиболее употребительные методы. Классифицируют методы решения задач целочисленного программирования исходя из линейности задачи и вида переменных. Различают два класса методов: методы отсечения и комбинаторные методы.

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

Комбинаторные методы /44,58/ обычно используются для решения линейных задач с булевыми переменными. Для таких задач используется так называемый аддитивный алгоритм, вычислительные операции в котором ограничиваются лишь сложением и вычитанием. Идея аддитивного алгоритма заключается в переборе 2N возможных решений, где N— число булевых переменных, и выборе лучшего из них.

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>