Консалтология Общая теория консалтинга (стр. 44 )

9.12. Методы и алгоритмы оптимизации структур

Из множества формализуемых задач структурного син­теза значительная их часть может быть сведена к определению экстремального значения це­левой функции

(9.117)

при ограничениях

(9.118)

(9.119)

xj — целые числа, j= 1, 2,…, р (р≤т). (9.120)

Если в сформулированной задаче ограничения (9.120) отсутствуют, то имеет место классическая задача линейно­го программирования, если ограничения (9.120) имеются и р=т, то данная задача является полностью целочислен­ной, при р<т задача является частично целочисленной.

Задача линейного программирования. В настоящее вре­мя теория линейного программирования хорошо разрабо­тана и имеется целый арсенал методов решения задач линейного программирования — это, например симплекс-метод, реализующий последовательную процедуру направ­ленного поиска оптимального значения целевой функции (9.117) при существующих ограничениях вида (9.118) и (9.119).

Симплекс-метод. Первоначально система нера­венств (9.118) путем введения дополнительных переменных xm+i≥Q преобразуется в систему уравнений таким обра­зом, чтобы имело место одно из двух выражений

Такое изменение приводит просто к увеличению числа переменных, что не меняет существа задачи. Введем ряд понятий, широко применяемых в задачах линейного про­граммирования.

Базисом называют любой набор из п таких перемен­ных, что определитель, составленный из коэффициентов при этих переменных, не равен нулю. Отметим, что осталь­ные т—п переменных называют свободными.

Не уменьшая общности, рассмотрим сущность сим­плекс-метода на примере задачи максимизации целевой функции (9.117) при наличии ограничений (9.118) и (9.119). Для определения первоначального базисного решения ка­кие-либо т—п переменные принимают за свободные, т. е. приравнивают нулю, при этом все базисные переменные выражают через свободные, после чего решают систему полученных уравнений. Если некоторые из базисных переменных окажутся отрицательными, то полученное базис­ное решение является недопустимым и производится пере­ход к новому базису путем выбора новой совокупности свободных переменных. Базисное решение, в котором от­сутствуют отрицательные переменные, называют допу­стимым.

После того как найдено допустимое базисное решение, проверяют, не достигнут ли максимум целевой функции F(Х). Если нет, то ищут новое допустимое базисное реше­ние, но не любое, а такое, которое увеличивает значение целевой функции F(Х). Затем процедуру повторяют. Дан­ный метод довольно быстро приводит к цели, так как поз­воляет исключить из рассмотрения большое число базис­ных решений, заведомо не обращающих в максимум целе­вую функцию F(Х).

Проверку того, не достигнут ли при найденном решении максимум целевой функции, можно сделать путем поиска нового базисного решения, при котором значение целевой функции F(X) будет больше предыдущего. Для прихода к новому допустимому базисному решению одну из свобод­ных переменных следует сделать базисной, при этом она будет отличной от нуля, т. е. возрастет. Следовательно, ес­ли какая-либо из свободных переменных входит в выра­жение для целевой функции со знаком « + », а значит, при ее увеличении целевая функция увеличивается, то макси­мум целевой функции не достигнут и данную свободную переменную следует перевести в базисную.

Однако при возрастании свободной переменной неко­торые из базисных переменных начнут уменьшаться. Так как отрицательные значения переменных недопустимы, в качестве новой свободной переменной следует взять ту из базисных, которая раньше других обратится в нуль.

Задачи целочисленного программирования. В общем случае условие целочисленности накладывает дополнитель­ные ограничения, вследствие которых максимальное зна­чение целевой функции (в задачах максимизации) оказы­вается, как правило, меньше максимального значения це­левой функции соответствующей задачи линейного программирования; в последней отсутствуют условия це-лочисленности переменных.

Комбинаторные методы. Методы решения задач целочислен­ного линейного программирования в классе комбинаторных мето­дов базируются на максимальном учете характера задач и конеч­ности множества вариантов их решения. В их вычислительных схемах используется идея частичного перебора вариантов реше­ния задач. Это достигается путем отбрасывания некоторых под­множеств вариантов, которые согласно известным свойствам оптимального решения заведомо могут считаться неперспектив­ными.

Отличительной особенностью комбинаторных алгоритмов яв­ляется и то, что во многих из них вообще не используется решение задач линейного программирования, соответствующей исходной целочисленной задаче линейного программирования.

Таким образом, для большинства комбинаторных методов не требуется специальных доказательств их конечности, что и спо­собствовало широкому применению методов этого типа на прак­тике. Большая группа комбинаторных методов базируется на достаточно общей схеме методов, которые объединены под назва­нием — методы «ветвей и границ». В настоящее время схема метода «ветвей и границ» широко используется на практике.

Приближенные методы. Одной из основных причин бурного развития этой группы методом следует назвать сравнительную сложность реализации точных методов, а зачастую и просто не­возможность применения последних для задач большой размер­ности и для задач, время решения которых ограничено. Другим фактором, способствующим на практике развитию приближенных методов, является то, что для многих практических задач в зна­чительной мере точные решения не обеспечиваются из-за малой достоверности исходных данных.

Среди приближенных методов решения целочисленных задач линейного программирования следует выделить применение раз­личного рода эвристических алгоритмов, основанных на:

а) мето­дах, построенных на использовании случайного поиска;

б) мето­дах, сочетающих случайный поиск с идеей локальной оптимиза­ции;

в) методах, вычислительные схемы которых строятся на максимальном учете специфики конкретных типов задач и др.

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

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

Сущность алгоритмов, основанных на методе отсечения, легко уяснить, обратившись к геометрическим представле­ниям в пространстве решений (см. п. 9.1). Определим вы­пуклую оболочку множества допустимых целочисленных точек (решений) как минимальное выпуклое множество, содержащее все эти точки. Допустимыми решениями будет не вся область допустимых решений, находящаяся внутри и на границе выпуклой оболочки, а лишь отдельные дис­кретные точки этой области, имеющие все целочисленные координаты. Целевая функция достигает оптимального значения в одной из вершин этой выпуклой оболочки, кото­рая представляет собой одно из допустимых целочислен­ных решений.

Выпуклую оболочку можно представить конечным мно­жеством линейных ограничений (9.118), как изображено на рис. 9.12.

Рис. 9.12. Геометрическая иллю­страция принципа отсечения

Можно, не считаясь с условиями целочисленности, найти решение, определяемое точкой 1, а затем, округлив это решение до ближайших целых чисел, получить целочисленное решение в точке 2. Однако при этом может по­лучиться решение, далекое от оптимального. Оптимальным целочисленным решением будет точка 3.

Для определения оптимального решения в алгоритмах отсечения вначале рассмотрим выпуклую оболочку, опре­деленную линейными ограничениями (9.118) и условиями неотрицательности перемен­ных исходной задачи, и отыщем экстремальную точку этой оболочки (точка 1 на рис. 9.12). Если такое решение оказывается нецелочислеппым, то добавляют ограничение, отсекающее текущую экстремальную точку и уменьшающее «объ­ем» выпуклой оболочки (прямая А—А). Однако но­вое ограничение не отсека­ет ни одной экстремальной точки выпуклой оболочки, принадлежащей допусти­мым целочисленным решениям. В конечном итоге вводится такое число дополни­тельных ограничений, что экстремальная точка усеченной ныпуклой оболочки представляет собой целочисленное ре­шение исходной задачи.

Покажем, как формально построить дополнительные линейные ограничения, которым должно удовлетворить любое решение задачи (9.117) — (9.120). Рассмотрим ограни­чение

(9.121)

Возможно, одна или несколько величин аij и bi явля­ются дробными. Обозначим символом [аij] целую часть аij, т. е. наибольшее целое число, меньшее действительного чи­сла аij или равное ему. Поскольку на величины хj нало­жено ограничение (9.119), любые значения хj, соответству­ющие условию (9.121), должны удовлетворять более сла­бому ограничению

(9.122)

Поскольку сумма в левой части неравенства (9.122) должна быть целочисленной, (9.122) можно усилить следующим образом: