§ 6. Некоторые многоэкстремальные задачи

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

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

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

Какой бы то ни было единой теории многоэкстремальных задач пока не существует; равным образом, в зачаточном состоянии находятся и вычислительные методы. Однако многоэкстремальные задачи, вообще говоря, могут быть сведены к частично целочисленным. Для задач экстремизации на невыпуклых областях это фактически уже было продемонстрировано в § 4 настоящей главы. Содержанием настоящего параграфа будет изучение связи задач с невыпуклыми целевыми функциями и целочисленных задач. Подобное сведение представляет немалый теоретический интерес, ибо оно показывает родство и взаимосвязь двух на первый взгляд совершенно различных видов «нерегулярности» в математическом программировании. Кроме того, поскольку численные методы целочисленного программирования уже достаточно освоены, оно открывает один из реальных путей фактического решения многоэкстремальных задач.

Сейчас мы перейдем к изучению указанной взаимосвязи. Отметим, что возможность сведения нелинейной невыпуклой задачи к частично целочисленной была впервые отмечена в 1957 г. (т. е. еще до создания общих методов целочисленного программирования) Марковицем и Манном [115].

6.2. Рассмотрим задачу минимизации функции на некотором выпуклом множестве (конкретный способ задания для нас сейчас безразличен). Будем предполагать, что представима в виде суммы функций от одной переменной, т. е.

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

пусть каждое слагаемое в (6.1) представляет собой выпуклую функцию от и будучи суммой выпуклых функций, также является выпуклой)

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

Рис. 2.6.1.

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

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

Далее, очевидно,

а кусочно-линейную аппроксимацию функции можно записать в виде

Отметим, что в силу выпуклости угловые коэффициенты образуют монотонно неубывающую последовательность

Таким образом, мы можем заменить х согласно (6.4) (учитывая, что переменные ограничены сверху — см. и взять вместо его приближенное представление (6.5). Задача минимизации (6.5) при условиях (6.3) и (6.4) представляет собой уже задачу линейного программирования.

Весьма важно отметить здесь, что оптимальное решение последней задачи будет иметь следующую структуру:

где причем все для равны нулю. Иначе говоря, в этом решении берется максимально возможным; при этом значении берется максимально возможное до тех пор, пока не встретится такое что, взяв максимально возможным, мы уже превысим значение х. Тогда у уменьшается до выполнения равенства (6.4), а все последующие значения полагаются равными нулю. Это обстоятельство сразу следует из выпуклости аппроксимирующей ломаной выражаемой аналитически неравенствами (6.6). Действительно, в силу (6.6) переменная оказывается «более экономичной», чем следующая переменная и пока не достигла своей верхней границы, нет смысла брать отличное от нуля значение

Более формально это можно высказать, наложив следующее требование:

Условие (6.7) говорит о том, что если не достигло своей верхней границы, то а если достигло ее, то допускается и

Подчеркнем, что в рассматриваемом нами пока регулярном случае (6.7) не является дополнительным ограничением в задаче (6.3) — (6.5); для оптимального решения последней оно выполняется автоматически. Таким образом, здесь это альтернативное условие не вносит дополнительных усложнений.

Рис. 2.6.2.

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

Поэтому с точки зрения проведенной выше конструкции теперь было бы оптимальным выбирать «в обратном порядке» (т. е. сначала берется максимальное значение затем максимальное значение ). При этом, если не достигло своей верхней границы, то должно быть Вспоминая определение видим, что в этом случае само представление х в виде (6.4) и в виде (6.5) перестало бы быть справедливым.

В наиболее общем случае (рис. 2.6.3) последовательность угловых коэффициентов в (6.5) вообще не будет монотонной. Нам нужно было бы первой довести до верхней границы переменную отвечающую наименьшему затем переменную, отвечающую следующему по величине . А это привело бы к несвязности системы отрезков, из которых мы должны «набирать» оптимальное х.

Таким образом, в случае невыпуклости требование (6.7) начинает играть ключевую роль, и нам следует

явным образом учесть его в нашей формулировке. Альтернативное условие (6.7) можно, как мы уже знаем (см. § 4), выразить в рамках частично целочисленного программирования.

Рис. 2.6.3.

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

и заменим (6.7) системой неравенств

Мы видим, что если примет значение 0, то неравенства (6.9) сведутся к тому, что (т. е. попросту ). Если же получаем (т. е. ) и тривиальное неравенство Таким образом, выясняется и смысл введенных нами дополнительных переменных: если переменная достигла своей верхней границы, и в противном случае.

Окончательно задача минимизации невыпуклой функции на выпуклом множестве сводится к минимизации (6.5) при условиях (6.3), (6.4), (6.8) и (6.9) (и, разумеется, при условиях, определяющих Замечая, что ограничения сверху на в (6.3) уже фигурируют

в неравенствах (6.9) (кроме ограничения на мы можем заменить (6.3) и (6.9) на

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

Отметим, что фактически мы уже сталкивались с применением этого приема при сведении транспортной задачи с фиксированными доплатами (см. § 5) к частично целочисленной задаче (поясним, что целевая функция транспортной задачи с фиксированными доплатами представляет собой именно сумму вогнутых функций). Другой пример применения этого круга идей мы встретим в § 2 гл. 3 при рассмотрении нелинейной задачи размещения.