Постановка задачи дискретного программирования логические переменные целевая функция логических переменных

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

.  .  .  .  .  .  .  .  .  .                             (4.1.2)

                             (4.1.3)
где D — некоторое множество.
Если множество D конечным или счетным, то условие (4.1.3) — это условие дискретности и задача (4.1.1) — (4.1.3) является задачей дискретного программирования.
Чаще всего условие дискретности разделено по отдельным переменным следующим образом:
 .
Если вводится ограничение  — целое число, , то приходят к задаче целочисленного программирования (ЦП), а если вводится ограничение , то к задаче булевого программирования.
В задачах дискретного программирования область допустимых решений является невыпуклой и несвязной. Поэтому отыскание решения таких задач сопряжено со значительными трудностями. В частности, невозможно применение стандартного подхода, состоящего в замене дискретной задачи ее непрерывным аналогом, и дальнейшем округлении найденного решения до ближайшего целочисленного.
Методы решения задач дискретного программирования делятся на такие группы:
1) точные методы, которые включают метод отсекающих плоскостей (Гомори), метод ветвей и границ, метод последовательного анализа и отсева вариантов, аддитивний метод и др.;
2) приближенные методы: метод локальной оптимизации, модификации точных методов, методы случайного поиска и эвристические методы, максимально учитывающие специфику решаемых задач.
По структуре математической модели задачи дискретного программирования разделяют на следующие основные классы: 1) задачи с неделимостями; 2) экстремальные комбинаторные задачи; 3) задачи на невыпуклых и несвязных областях; 4) задачи с разрывными целевыми функциями.
Рассмотрим некоторые из них….