§ 4. Задачи на невыпуклых и несвязных областях

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

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

Рис. 2.4.1.

Приведем простейший пример. Присоединяя к условиям неотрицательности переменных условия

получаем несвязную область, изображенную на рис. 2.4.1 жирными линиями. Если в условия входит равенство

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

Задачи математического программирования с дополнительными условиями типа «либо — либо» (альтернативными условиями) будем называть дихотомическими. Оказывается, что подобные задачи могут быть сведены к частично целочисленным. Проиллюстрируем несколько наиболее типичных приемов, используемых при подобном сведении.

Пусть некоторая переменная X] задачи математического программирования ограничена сверху:

и, кроме того, на нее наложено ограничение

где Введем дополнительную целочисленную переменную принимающую два значения: и 1. Заменим ограничения (4.1), (4.2) следующими:

Отметим, что дополнительная переменная в целевую функцию не включается. Легко видеть, что система неравенств (4.3) относительно х и дополнительной целочисленной переменной эквивалентна (4.1) и альтернативному условию (4.2). В самом деле, если примет в решении значение 1, то (4.3) сведется к при будем иметь

В случае нескольких ограничений типа (4.2) неравенства (4.3) выписываются для каждого из них.

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

где функции.

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

Введем теперь вспомогательную целочисленную переменную у, принимающую значения и 1, и рассмотрим систему неравенств

Дополнительная переменная у в целевую функцию не входит. Система неравенств (4.5) эквивалентна альтернативному условию (4.4); действительно, если у примет значение 1, то (4.5) сведется к автоматически выполняющемуся соотношению и желаемому неравенству при мы получим соответственно

В дальнейшем мы еще встретимся с применением описанного приема (см. § 4 гл. 3).

4.2. Рассмотрим задачу математического программирования с системой ограничений

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

переменные принимающие значения и 1, и рассмотрим систему ограничений

где переменные подчинены условию

Условия (4.7), (4.8) обеспечивают требуемое; это устанавливается рассуждением, которое уже можно считать стандартным.

Если в решении требуется выполнение ровно из условий (4.6), то неравенство в (4.8) следует заменить равенством.

Одна конкретизация такой модели, представляющая самостоятельный интерес, указана Динкельбахом и Стеффенсом [70]. Пусть в обычной задаче линейного программирования наложено дополнительное требование следующего типа: в окончательном решении отличными от нуля должны быть не более компонент (разумеется, Предположим, что для всех переменных известны (или могут быть найдены) верхние границы (4.1). Введем целочисленные переменные принимающие значения и 1. Тогда сформулированное выше требование реализуется следующей системой дополнительных условий:

Другой вариант подобных задач с ограничением на число применяемых способов заключается в следующем. Пусть множество индексов переменных разбито на два непересекающихся подмножества: причем в окончательном решении отличными от нуля могут быть либо переменные из либо

переменные из Снова предполагается наличие верхних границ (4.1). Здесь нужно ввести две целочисленные переменные Нужные нам условия принимают вид

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

Рис. 2.4.2.

Рассмотрим в качестве примера задачу линейного программирования с дополнительными условиями на пару переменных

где В плоскости условия (4.13) описывают -образную область, изображенную на рис. 2.4.2.

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

где или 1. При неравенства (4.14) сводятся к а при мы имеем

Ограничения (4.13) можно интерпретировать также несколько иным образом. Именно, они равносильны тому, что искомая точка должна принадлежать одному из двух прямоугольников: либо прямоугольнику

либо прямоугольнику В более общем случае мы можем встретиться с системой пар областей причем решение должно принадлежать либо либо Пусть для каждой пары область описывается системой неравенств

а область системой

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

Если теперь то первая серия неравенств из (4.17) превращается в неравенства а вторая серия выполняется автоматически; при ситуация будет обратной.

Рекомендуем читателю в качестве упражнения описать область, представляющую собой объединение двух треугольников (рис. 2.4.3).

Рис. 2.4.3.

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

где заданные функции. Здесь предполагается также, что для функции известна ее верхняя граница А, а для функций их нижние границы Условное ограничение (4.18) можно, очевидно, переписать в виде альтернативного условия

Теперь используем уже известный нам прием: после введения дополнительной переменной у, принимающей значения или 1, (4.19) перепишется в виде системы неравенств

Отметим попутно, что первое из неравенств (4.20) записано со знаком вместо знака ибо при условие будет выполняться автоматически при

Этот прием несложно перенести, например, на случай, когда логическое ограничение имеет более сложный вид:

Вводя три дополнительные переменные принимающие значения или 1, мы можем переписать (4.21) в виде системы (обозначения не требуют пояснений)

Проверку эквивалентности (4.21) и (4.22) предоставим читателю.