Параллельное программирование

Развитие стратегии решения задачи ЛП


  1. Выделяя на многограннике R допустимых решений верхнюю и нижнюю поверхности, мы на деле не столько стремимся "подобраться" поближе к вершине-решению, сколько стремимся расчленить задачу, локализовать поиск опорного плана. Если мы с помощью указанных косинусов начнем исследовать совместно всю совокупность граней многогранника, то окажемся во власти неразрешимых коллизий. Ни о каком упорядочении углов в этом случае не может быть речи, так как во всем диапазоне [0, 2
    ] изменения углов между нормалями к граням косинус никогда не даст однозначного ответа об отношении между этими углами.
  2. Многогранник R может иметь столь причудливую форму, что знание значения целевой функции в некоторой его вершине нисколько не определяет того, за сколько шагов будет найдена вершина-решение. Например, двигаясь из вершины, в которой значение целевой функции меньше, можно за один шаг второго этапа алгоритма достичь, как смежную, вершину-решение. В то же время, стремясь найти вершину с большим значением целевой функции, можно оказаться в ситуации, когда для достижения вершины-решения потребуется несколько шагов. Это говорит о том, что анализ суммы коэффициентов целевой функции для выбора верхней или нижней поверхности многогранника R не столь важен.
  3. Более того, выбранная таким образом поверхность не всегда может привести к успеху.

    Например, на рис. 6.6 верхнюю поверхность образуют грань (ребро), противоположная вершине A, и, возможно, координатные плоскости (оси).

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

    Кстати, в нашем примере нижняя поверхность определяется следующим образом:

    Qнижн = {q6, q7, q8, q9}.

    Составим для нее матрицу S косинусов в составе табл. 6.5.

    Таблица 6.5.

    ГраньНормаль N6 N7 N8 N9
    q6N610,830,230,56
    q7N70,83100
    q8N80,23010
    q9N90,56001




    Начало  Назад  Вперед



    Книжный магазин