Проблема целочисленности

Несмотря на линейность модели допустимое множество целочисленной задачи не является выпуклым. Так, в полностью целочисленной задаче оно представляет собой множество отдельных точек, имеющих целочисленные координаты. Методы ЛП базируются на выпуклости допустимого множества и поэтому непосредственно не могут быть применимы к целочисленным задачам. Можно пренебречь требованием целочисленности и использовать один из методов ЛП, но тогда, результат не будет целочисленным. Округление дробных значений переменных проблематично - может привести к недопустимости. При двух дробных переменных имеется 4, а при n переменных – 2 ⁿ вариантов округления. Какие из них дают допустимые решения, можно определить только после проверки всех ограничений. При этом следует иметь в виду, что, во-первых, целочисленная задача может оказаться неразрешимой несмотря на разрешимость непрерывной задачи; во-вторых, допустимость округленного решения еще не означает его оптимальность. Пример: задача о садовнике. По расчетам садовника требуется внести в почву удобрения в количестве 107 кг. Удобрения продаются только в расфасованном виде: 1) мешок 35 кг 140 руб.; 2) мешок 24 кг 120 руб. Необходимо определить вариант закупки удобрений с минимальными затратами.

Модель задачи: L= 140 x₁+ 120 x₂® min; 35 x₁+ 24 x₂ ³ 107; x₁, x₂ ³ 0, int (целые).

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

x₁= 3 , x₂= 0. Если округлить его по правилам арифметики, то получим недопустимое решение. Округление в большую сторону (x₁= 4, x₂= 0)приводит к допустимости, но является ли такое решение оптимальным? Чтобы ответить на этот вопрос, рассмотрим все возможные целочисленные решения. Прочерк в графе критерия означает недопустимость. Как видно из таблицы, оптимальным является решение x₁^*= 1, x₂^*= 3, которое принципиально отличается от непрерывного. Округленное допустимое решение оказалось далеким от оптимального: затраты в нем выше минимальных на 12%. Пример 2: Другая особенность свойств ЦЗ:

L= 21 x₁+ 11 x₂® max; 7 x₁+ 4 x₂ £ 13; x₁, x₂ ³ 0, int.

Рассмотрим все возможные целочисленные решения. При этом сначала возьмем решение x₁= 1, x₂= 1 и решения, окружающие его. Целочисленные точки и ограничение показаны на рис.Из таблицы следует, что в точке (1, 1) имеет место локальный экстремум, а глобальный максимум достигается в точке (0, 3). В непрерывной линейной задаче любой локальный экстремум является глобальным. То что ЦЗ может иметь локальные экстремумы, необходимо учитывать при использовании методов частичного перебора.

В ряде случаев решение целочисленной задачи находят, решая ее как непрерывную. Так, если в оптимальном решении непрерывной задачи нецелочисленные значения переменных велики (их порядок >10²), округление до целых оправдано: возможные нарушения условий и отклонение от оптимальности пренебрежимо малы.

При особых свойствах ЦЗ (все вершины допустимого множества целочисленные) решение ее как непрерывной всегда дает целочисленный результат. Многогранное множество, обладающее этим свойством, - целочисленное. У словия, при которых множество оказывается целочисленным. Возьмем многогранное множество M (B):

;(1) где a_ij – фиксированные int числа, B = (b ₁ ,b ₂,…, b_m)^Т и m<n (ранг матрицы [ a_ij ] равен m.) Для него справедлива следующая теорема.

Теорема. Для того чтобы все вершины многогранного множества M (B) при любом целочисленном векторе B были целочисленными, необходимо и достаточно, чтобы каждый минор порядка m матрицы условий [ a_ij ] был равен либо 0, либо +1 или –1.

Если вместо равенств (1) множество задается неравенствами, указанные в теореме значения относятся ко всем минорам матрицы [ a_ij ]. Класс задач, удовлетворяющих теореме, очень узок (транспортные задачи, о назначениях и др.) – легкоразрешимые задачи (по Дж. Эдмондсу), для них существуют полиномиальные алгоритмы (время или число итераций растет полиномиально с увеличением размерности задачи). Остальные целочисленные задачи входят в класс трудноразрешимых задач (класс NP по Карпу и Куку). Для решения таких задач применяются различные подходы. Из точных методов можно назвать следующие: методы отсечений; метод ветвей и границ; метод построения последовательности планов; модификации динамического программирования; методы последовательного анализа вариантов. Последние 4 метода входят в группу комбинаторных методов. Кроме точных методов имеется также большое число приближенных методов.