Общий алгоритм перебора

На основе ограничений задачи q1
b1, ... qm
bm строим систему граней (гиперплоскостей) q1 = b1, ... qm = bm. Дополним эту систему граней всеми потенциальными гранями на основе условий: x1

= 0, ... , xn = 0. Получим систему m+n линейных уравнений, в общем случае избыточную и, возможно, противоречивую.
Выбираем из этой системы очередную подсистему n линейных уравнений (всего таких подсистем Cnm + n) и решаем ее.

Как известно, система n линейных уравнений имеет единственное решение в том и только в том случае, если ранг r матрицы системы равен рангу расширенной матрицы системы и равен n.

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

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

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

Однако традиционно при решении систем линейных уравнений в подобных задачах используют метод Гаусса как обобщение метода последовательного исключения. Метод Гаусса позволяет получать значения переменных последовательно. Значит, их контроль на отрицательность производится немедленно и останавливает дальнейший счет. Кроме того, попутные преобразования системы уравнений позволяют динамически выявить тот случай, когда матрица — алгебраическое дополнение диагонального элемента содержит нулевую строку, т.е. определитель системы равен нулю. Это также останавливает дальнейший анализ системы уравнений.

Если же получено единственное решение и все его компоненты x1, ... , xn не отрицательны, то они могут определять вершину многогранника R.
Могут, ибо если среди уравнений подсистемы есть уравнения вида xj = 0, введенные в состав граней на основе условий неотрицательности решений, и не вошли все уравнения граней, обусловленные ограничениями задачи, то полученное решение может противоречить некоторым "законным" ограничениям задачи. А именно — не представленным в составе решенной подсистемы.

Поэтому в таком случае необходимо дополнительно проверить, принадлежит ли действительно точка (x1, ... , xn) многограннику R, т.е. выполняются ли для нее все не отображенные в подсистеме ограничения вида qj
bj, первоначально указанные при постановке задачи ЛП.
Если найденная точка (x1, ... , xn) действительно является вершиной многогранника R, определяемого ограничениями и условиями при постановке задачи, отыскивается значение z(x1, ... , xn) = c1x1+c2x2+ ... +cnxn. Если это значение превосходит ранее полученные при уже проведенном анализе других вершин, оно запоминается вместе со значениями x1, ... , xn — для продолжения поиска и анализа других вершин R или окончания решения задачи.
Перебор всех подсистем n линейных уравнений на основе m+n ограничений (исходных и дополнительных), их число Cnm+n, полученные при их решении координаты вершин многогранника R, обусловленного числом m основных ограничений, позволяет выбрать ту вершину, которая порождает максимальное (минимальное) значение целевой функции — линейной формы z.

Данная вычислительная процедура хорошо реализуется на многопроцессорных ВС. Различные варианты подсистем линейных уравнений следует динамически распределять между процессорами. А это, в свою очередь, полностью соответствует SPMD-технологии "одна программа — много потоков данных".

О единственности решения. Мы видели по рисункам, что z = zmax может выполняться на ребрах и гранях многогранника R. Если на ребре, то в двух сопряженных вершинах z принимает одинаковое значение zmax. Если на гранях, то более чем в двух вершинах z = zmax . Это легко переносится в n-мерное пространство.

Итак, указанная вычислительная процедура может привести к получению единственной вершины X = (x1, ... , xn) многогранника R, в которой z(X) = zmax.

Пусть в r вершинах X1, ... , Xr многогранника R выполняются равенства z(Xj) = zmax, j = 1, ... ,r. Построим выпуклую комбинацию векторов:

X = k1 X1 + k2 X2 + ... + kr Xr , k1 + k2 + ... + kr = 1, kj

0. (4.3)

Множество значений X, удовлетворяющих этому условию, определяет бесконечное множество решений данной задачи ЛП.

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

m.

Содержание раздела