Дискретное программирование. Задачи дискретного программирования в САПР. Методы решения задач дискретного программирования, страница 2

 .                                         (3.4)

Очевидно, что такое ограничение выполняется при выборе только одного варианта из n возможных (при этом соответствующее выбранному варианту значение b_j  равно 1, а остальные значения равны 0).

С помощью двоичных  переменных можно также осуществить выбор одного из возможных значений некоторой величины. Пусть, например, величина a может принимать одно из нескольких возможных значений a₁, a _{2 ,} …, a _{n .} Тогда требование выполнения  условия

                                         (3.5)

совместно с условием (3.4) обеспечит выбор одного из возможных значений a.

Часто двоичные переменные, отражая логические ограничения,  играют роль вспомогательных переменных в задаче оптимизации. (Основной переменной оптимизации может быть, например, рассмотренная выше  дискретная переменная a ).

Рассмотренный прием формального выбора одной из возможностей иллюстрирует идею сведения задачи дискретного нецелочисленного программирования к задаче целочисленного программирования ( при принятии целыми числами значений 0 и 1) [9].

З а м е ч а н и е 3.6.По-видимому, возможность такого сведения задачи ДП (с конечным множеством значений переменных) к задаче ЦП объясняет позицию авторов, называющих весь рассматриваемый в данном разделе класс задач целочисленным программированием.

Отметим, что задача ДП является разновидностью класса так называемых нерегулярных задач, заданных на несвязных множествах [9].

Для более подробного уяснения специфики задач ДП рекомендуется ознакомиться с классификациями прикладных задач ДП, приводимыми  в [5,7,9].

3.2.   Постановка задачи дискретного программирования

Наличие большого количества разновидностей задач ДП затрудняет формулировку общей постановки задач такого вида. Так, в [5] приведены четыре вида структур математической модели задачи ДП: 1) задачи с неделимостями; 2) экстремальные комбинаторные задачи; 3) задачи на несвязных и на невыпуклых областях; 4) задачи с разрыв-ными целевыми функциями.  Аналогичные виды структур рассмотрены также в [5,6].

Различные постановки задач ДП, приводимые различными авторами, можно также условно разделить по степени их подробности на две группы: «свернутые»  постановки  и  «развернутые» постановки.

В постановках первой группы дается лишь теоретико-мно-жественное описание множества допустимых планов (или ОДР) без явного выделения ограничений. Во второй группе постановок ограничения указываются.

В качестве примера «свернутой» постановки укажем постановку, приводимую в  [4]:

найти максимум целевой функции , определенной на некотором дискретном множестве . Для решения задачи необходимо определить элемент , такой, что

.                             (3.6)

З а м е ч а н и е 3.7. Строго говоря, постановка (3.6) произведена для частного случая дискретного множества D , а именно, для конечного  множества.

Приведем «развернутую» постановку задачи, сформированную на основе постановок,  приводимых  в [5,9,21]:

максимизировать функцию

                                            (3.7)

при условиях

 ;               (3.8)

;                                (3.9)

;                               (3.10)

где  - множество индексов переменных, для которых  - конечные или счетные множества ().

В такой постановке (3.7) - целевая функция, (3.8) - система ограничений в форме неравенств, (3.9) - условие неотрицательности, (3.10) - условия дискретности.

Постановка задачи ДП (3.7) - (3.10) является достаточно общей. Условия (3.10) позволяет задавать как частично дискретные, так и полностью дискретные задачи. Можно специально оговорить конечность или “двоичность” отдельных множеств . При целочисленности переменных   вместо ограничений (3.10) обычно используется ограничение (3.3).

Варианты с минимизацией целевой функции, ограничениями-не-равенствами противоположного смысла и ограничениями-равенствами сводятся к приведенной постановке путем преобразований, приведенных в разделе 1.

Выделим некоторые подклассы задачи ДП.