Лекция: Исторические сведения о дисциплине.

Глава 1. Общие сведения о задачах дискретной и комбинаторной оптимизации и методах их решения.

Исторические сведения о дисциплине.

В 1947 г. Джордж Данциг (Dantzig) разработал симплексный алгоритм для решения задач линейного программирования (ЛП), опубликованный в 1951 г. Уже в то время было признано, что задачи линейного программирования появляются при моделировании многих реальных ситуаций, причем симплекс-метод оказался очень эффективным на практике.

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

В то время не было известно общего метода решения задач этого вида, называемых задачами смешанного целочисленного линейного программирования (ЦЛП).

В 1958 г. Ральф Гомори (Gomory) опубликовал небольшую статью об использовании симплексного алгоритма с относительно небольшими модификациями для построения конечного алгоритма для нахождения оптимального целочисленного решения задачи ЦЛП. Гомори показал, как симплексная таблица может быть использована для получения новых неравенств, которые выполняются для всех решений, удовлетворяющих ограничениям целочисленности, но которым не удовлетворяет оптимальное (нецелочисленное) решение задачи ЛП. Изучение этих неравенств, именуемых отсечениями, быстро стало главной областью дальнейших исследований как по теоретическим причинам, так и из-за перспективности их использования в виде вычислительного инструмента[1].

В 1955 г. в статье Гарольда Куна (Kuhn) описан комбинаторный алгоритм для задачи целочисленного программирования со специальной структурой – задачи о назначениях. В этой работе впервые применен специализированный метод для решения задачи со специальной структурой и впервые использован прямо-двойственный алгоритм линейного программирования.

Хофманн и Крускал (Hoffman, Kruskal) в статье 1956 г. показали важность понятия полной унимодулярности для нахождения целочисленных решений задач линейного программирования.

В статье Лэнд и Дойг (Land, Doig) в 1960 г. был предложен перспективный и наиболее популярный в настоящее время метод решения задач целочисленного программирования ‑ метод ветвей и границ. Современные решатели используют гибридные методы отсечений и ветвей и границ.

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

Важность полиномиальных алгоритмов для комбинаторных алгоритмов стала ясна в начале 1970-х годов в связи с введением в области теоретических основ информатики классов P (полиномиальных) и NP (недетерминистских полиномиальных). Фундаментальный результат Кука (Steven Cook) показал, что имеется множество так называемых NP-полных задач, обладающих таким свойством, что если любая из них была бы разрешима за полиномиальное время, тогда все задачи также были бы в классе NP. Статья Карпа (Richard Karp), опубликованная в 1972 году, подчеркнула важность этих результатов для математического программирования и показала, что большое число задач целочисленного программирования (ЦП), для которых не было известно полиномиальных алгоритмов, принадлежат к классу NP-полных задач.

Джеффрион (Geoffrion) в работе 1974 г. показал, как функция Лагранжа может быть использована для получения релаксации задачи ЦЛП, что позволило ввести «трудные» ограничения в целевую функцию задачи.

Следует особо выделить весьма общие и эффективные при решении ряда конкретных прикладных задач дискретной оптимизации схемы, предложенные отечественными учеными, такие как метод последовательного конструирования, анализа и отсева вариантов В.С. Михалевича-Н.З. Шора (Институт кибернетики НАНУ), общая схема глобального равновесного поиска (И. В. Сергиенко, В. П. Шило (Институт кибернетики НАНУ) [15]), последовательностные схемы В. А. Емеличева (Белорусский государственный университет), локальные алгоритмы Ю. И. Журавлева (Вычислительный центр РАН) [7].

Основные понятия: задачи комбинаторной и дискретной оптимизации, Модели дискретного программирования. Постановка задачи, примеры.

Под задачей дискретной оптимизации (или дискретного программирования – см. [16]) понимается задача математического программирования

, (1.1)

где ‑ конечное множество допустимых решений.

Задача комбинаторной оптимизации имеет вид:, где для конечного множества ( ‑ булеан, т.е. множество всех подмножеств множества ).

Введем дальнейшие определения.

Задачей линейного программирования (ЛП) называется следующая задача либо задача .

Задача целочисленного программирования (ЦП) определяется так: .

Задача частично целочисленного линейного программирования (ЧЦЛП) (или смешанного целочисленного линейного программирования (СЦЛП)) выглядит следующим образом:

.

Среди задач дискретной оптимизации выделяются задачи с бинарными или булевыми переменными

Возможно выделить следующие основные классы задач дискретной оптимизации [10]:

1. Задачи с неделимостями.

2. Экстремальные комбинаторные задачи.

3. Задачи с неоднородной разрывной целевой функцией.

4. Задачи на неклассических областях.

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

6. Дискретные задачи в узком смысле слова (нахождение экстремумов на конечных множествах).

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

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

(1.2)

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

(1.3)

, (1.4)

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

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

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

Формализуем выполнение условий

, (1.5)

если для функций известны конечные нижние границы .

Введем дополнительную бинарную переменную и заменим (1.5) двумя условиями (1.6), (1.7):

(1.6)

(1.7)

В самом деле, если примет в решении значение 1, то (1.6) сведется к а (1.7) – к; при из (1.6) получим а из (1.7) ‑

Пример 1.3. Рассмотрим задачу оптимизации с ограничениями

(1.8)

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

(1.9)

где

и (1.10)

Условия (1.9) и (1.10) обеспечивают требуемое.

Пример 1.4. Рассмотрим формализацию условных, или логических ограничений. Именно, пусть необходимо формализовать условие вида

если то (1.11)

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

либо (1.12)

либо (1.13)

Введя бинарную переменную, заменим условия (1.12), (1.13) следующим и условиями

Пример 1.5. Рассмотрим задачу оптимизации с неоднородной разрывной целевой функцией

(1.14)

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

(1.15)

(1.16)

где

‑ разрывная функция.

Предположим, что заданы еще верхние границы для переменных:

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

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