Проблема целочисленности
Несмотря на линейность модели допустимое множество целочисленной задачи не является выпуклым. Так, в полностью целочисленной задаче оно представляет собой множество отдельных точек, имеющих целочисленные координаты. Методы ЛП базируются на выпуклости допустимого множества и поэтому непосредственно не могут быть применимы к целочисленным задачам. Можно пренебречь требованием целочисленности и использовать один из методов ЛП, но тогда, результат не будет целочисленным. Округление дробных значений переменных проблематично - может привести к недопустимости. При двух дробных переменных имеется 4, а при n переменных – 2 n вариантов округления. Какие из них дают допустимые решения, можно определить только после проверки всех ограничений. При этом следует иметь в виду, что, во-первых, целочисленная задача может оказаться неразрешимой несмотря на разрешимость непрерывной задачи; во-вторых, допустимость округленного решения еще не означает его оптимальность. Пример: задача о садовнике. По расчетам садовника требуется внести в почву удобрения в количестве 107 кг. Удобрения продаются только в расфасованном виде: 1) мешок 35 кг 140 руб.; 2) мешок 24 кг 120 руб. Необходимо определить вариант закупки удобрений с минимальными затратами. Модель задачи: L= 140 x1+ 120 x2® min; 35 x1+ 24 x2 ³ 107; x1, x2 ³ 0, int (целые). Если пренебречь целочисленностью, то легко увидеть, что оптимальным будет решение
x1= 3
L= 21 x1+ 11 x2® max; 7 x1+ 4 x2 £ 13; x1, x2 ³ 0, int.
В ряде случаев решение целочисленной задачи находят, решая ее как непрерывную. Так, если в оптимальном решении непрерывной задачи нецелочисленные значения переменных велики (их порядок >102), округление до целых оправдано: возможные нарушения условий и отклонение от оптимальности пренебрежимо малы. При особых свойствах ЦЗ (все вершины допустимого множества целочисленные) решение ее как непрерывной всегда дает целочисленный результат. Многогранное множество, обладающее этим свойством, - целочисленное. У словия, при которых множество оказывается целочисленным. Возьмем многогранное множество M (B):
Теорема. Для того чтобы все вершины многогранного множества M (B) при любом целочисленном векторе B были целочисленными, необходимо и достаточно, чтобы каждый минор порядка m матрицы условий [ aij ] был равен либо 0, либо +1 или –1. Если вместо равенств (1) множество задается неравенствами, указанные в теореме значения относятся ко всем минорам матрицы [ aij ]. Класс задач, удовлетворяющих теореме, очень узок (транспортные задачи, о назначениях и др.) – легкоразрешимые задачи (по Дж. Эдмондсу), для них существуют полиномиальные алгоритмы (время или число итераций растет полиномиально с увеличением размерности задачи). Остальные целочисленные задачи входят в класс трудноразрешимых задач (класс NP по Карпу и Куку). Для решения таких задач применяются различные подходы. Из точных методов можно назвать следующие: методы отсечений; метод ветвей и границ; метод построения последовательности планов; модификации динамического программирования; методы последовательного анализа вариантов. Последние 4 метода входят в группу комбинаторных методов. Кроме точных методов имеется также большое число приближенных методов.
|