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

Важный подкласс таких задач образуют задачи целочисленного программирования (к ним, в первую очередь, относятся задачи с неделимостями). В свою очередь, среди задач целочисленного программирования наиболее разработанной является задача линейного целочисленного программирования (ЛЦП). Она формулируется как задача ЛП,  дополненная требованием целочисленности.

Постановка такой задачи в матричной форме имеет вид:

.                   (3.11)

Здесь - множество индексов переменных, на которые распространяется требование целочисленности. Если множество  включает все , то задача ЛЦП называется полностью целочисленной, в противном случае - частично целочисленной.

3. 3.   Задачи дискретного программирования в САПР

Как указывалось ранее, в отличие от “классического” ЛП (с непрерывными переменными) дискретное программирование находит широкое применение в САПР. С его помощью решаются задачи структурного и параметрического синтеза [21,22]  .

При решении задач параметрического синтеза систем (в первую очередь технических) приходится учитывать, что переменные оптимизации могут принимать только стандартизированные или нормализованные (нормализированные) значения (например, значения электрических сопротивлений и емкостей элементов радиоэлектронных устройств, значения размеров стандартных и нормализованных деталей и узлов в машиностроении и т.д.).

При решении задач параметрической оптимизации ищутся оптимальные значения таких величин, определенных на некоторых конечных множествах. В этом случае задача математического программирования будет задачей дискретного программирования. Для решения таких задач используется искусственный прием, иллюстрируемый соотношениями вида (3.4) и (3.5).

Задачи структурного синтеза могут быть сведены к задачам дискретного программирования несколькими способами.

Один из вариантов такого сведения состоит во введении переменных задачи, обозначающих количество вхождений элементов определенного (-го) вида в состав некоторого объекта или системы. Такие переменные могут принимать значения из ряда чисел  . При этом значение 0 соответствует не вхождению элемента в систему, значение 1- однократному вхождению, значение 2 - двухкратному вхождению и т.д. (формально это условие записывается в виде: ).

З а м е ч а н и е 3.8. Очевидно, что в рассмотренном варианте не учитывается вопрос о связях  между элементами системы.

Другая группа вариантов сведения использует рассмотренные ранее в п.3.1 булевы переменные. С помощью таких переменных могут решаться задачи выбора оптимальной структуры системы при задании ее элементов. Задание структуры осуществляется путем указания наличия или отсутствия связи между двумя элементами системы. Например, если между -м и -м элементами системы имеется связь, , если связь отсутствует - то . Соответственно, оптимальная структура системы будет задаваться набором переменных задачи, состоящим из оптимального сочетания нулей и единиц. С помощью таких переменных решаются задачи компоновки, размещения и трассировки [22].

Двоичные переменные используются также при проектировании систем, состоящих из взаимосвязанных объектов, имеющих сложные логические взаимообуславливающие связи (например, в случае, если одни проектные решения исключают другие) [4].

Отметим, что в задачах дискретного программирования, использующих булевы переменные, большую роль играют ограничения ОГР_ф, построенные на базе этих переменных и отражающие логические требования проектирования (примерами таких ограничений являются ограничения-равенства (3.4) и (3.5)).

Ряд постановок задач  ДП, названные авторами задачами логического проектирования,  рассмотрены также в [9]

 3.4.   Методы решения задач дискретного программирования

 3.4.1.  Классификации методов решения задач дискретного

                        программирования

В соответствии с [9] могут быть выделены три группы методов решения задач  ДП.