Целочисленное программирование

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

В Древней Греции Диофант (II-III в.) формулирует уравнения, в которых искомые переменные – целые. Например, для уравнения первой степени, a ₀ + a ₁ x ₁ = 0, где a ₀, a ₁ – целые, решение x ₁ = – a ₀/ a ₁ – целое, если a ₀ делится на a ₁ без остатка, то есть такое уравнение не всегда разрешимо в целых числах. Из двух уравнений 3 x ₁–27 = 0 и 5 x ₂ + 21 = 0 только первое имеет целое решение: x ₁ = 27/3 = 9, а второе – нет, так как x ₂ = –21/5.

Для уравнения с двумя неизвестными: a ₁ x ₁ + a ₂ x ₂ = 0, где a ₁, a ₂ – целые, решение будет x ₁ = –(a ₂/ a ₁) x ₂. Например,

10 x ₁– 5 x ₂ = 0 или x ₁ = 0,5 x ₂. (1)

Из этого примера можно сделать следующие выводы: уравнение имеет бесчисленное множество решений, так как n > m; решение – целое, если x ₂ – четное.

Для того, чтобы из множества допустимых решений выбрать одно – оптимальное, необходимо, как нам уже известно, добавить к условию (1) целевую функцию. Задачи оптимизации, в которых решение должно быть в целых числах, называют задачами целочисленного программирования. Если в этой задаче целевая функция и ограничения – линейные зависимости, то ее называют целочисленной задачей линейного программирования; если же хотя бы одна зависимость будет нелинейной, то такая задача формулируется как целочисленная нелинейного программирования.

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

Если к условию (1) добавить такие, например, граничные условия:

2 £ x ₁ £ 8; 1 £ x ₂ £ 3,

то можно видеть, что такая система решения не имеет. Отсюда следует, что задача целочисленного программирования не всегда имеет решение, то есть она не совместна.

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

Аналитическая задача целочисленного программирования формулируется:

Если n ₁ = n, то задачу называют полностью целочисленной; если n ₁< n, то – частично-целочисленной.

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

Рис. 3.1. Многогранник решений

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

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

- Так как целевая функция достигает оптимума в угловой точке, то построением многогранника обеспечивается целочисленность оптимального решения.

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

В ряде случаев задачу целочисленного программирования решают следующим образом:

1. Как непрерывную задачу линейного программирования.

2. Округляют переменные.

3. Проверяют допустимость округленного решения.

4. Если решение допустимое, то оно принимается как целочисленное.

При необходимости точного решения применяют специальные методы, где учитывается, что множество решений любой целочисленной задачи – конечно. Например, в задаче с переменными x ₁, x ₂: 0 < x ₁ £ 4; 0 < x_j £ 5. Число возможных решений 4^.5 = 20. Следовательно, возможен полный перебор всех возможных сочетаний целочисленных x ₁, x ₂ и выбор из них наилучших в смысле целевой функции. Трудоемкость этого метода возрастает с ростом числа переменных и области граничных условий, и для реальных задач неприменим.

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