ибо если среди уравнений подсистемы

Могут, ибо если среди уравнений подсистемы есть уравнения вида 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.

Содержание Назад Вперед

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