Развитие стратегии решения задачи ЛП
- Выделяя на многограннике R допустимых решений верхнюю и нижнюю поверхности, мы на деле не столько стремимся "подобраться" поближе к вершине-решению, сколько стремимся расчленить задачу, локализовать поиск опорного плана. Если мы с помощью указанных косинусов начнем исследовать совместно всю совокупность граней многогранника, то окажемся во власти неразрешимых коллизий. Ни о каком упорядочении углов в этом случае не может быть речи, так как во всем диапазоне [0, 2] изменения углов между нормалями к граням косинус никогда не даст однозначного ответа об отношении между этими углами.
- Многогранник R может иметь столь причудливую форму, что знание значения целевой функции в некоторой его вершине нисколько не определяет того, за сколько шагов будет найдена вершина-решение. Например, двигаясь из вершины, в которой значение целевой функции меньше, можно за один шаг второго этапа алгоритма достичь, как смежную, вершину-решение. В то же время, стремясь найти вершину с большим значением целевой функции, можно оказаться в ситуации, когда для достижения вершины-решения потребуется несколько шагов. Это говорит о том, что анализ суммы коэффициентов целевой функции для выбора верхней или нижней поверхности многогранника R не столь важен.
-
Более того, выбранная таким образом поверхность не всегда может привести к успеху.
Например, на рис. 6.6 верхнюю поверхность образуют грань (ребро), противоположная вершине A, и, возможно, координатные плоскости (оси).
Поскольку при анализе этой поверхности другие грани исключены из рассмотрения, то нет системы двух уравнений, результатом решения которой стали бы вершины, образуемые этой гранью. Мы зашли бы в тупик, если бы не позволили себе рассмотреть и другую, нижнюю, поверхность.
Кстати, в нашем примере нижняя поверхность определяется следующим образом:
Qнижн = {q6, q7, q8, q9}.
Составим для нее матрицу S косинусов в составе табл. 6.5.
Таблица 6.5.
ГраньНормаль N6 N7 N8 N9 q6 N6 1 0,83 0,23 0,56 q7 N7 0,83 1 0 0 q8 N8 0,23 0 1 0 q9 N9 0,56 0 0 1
В результате анализа первой строки, соответствующей грани q6, находим грани {q6, q7, q9}, возможно, образующие некоторую вершину. В результате решения выделенной системы уравнений получаем точку (0, 55, 0). Эта точка не удовлетворяет ограничениям q40 и q5
0. Мы видим по рисунку 6.3, что ошибки бы не произошло, если бы из рассмотрения не была исключена грань q4. Мы делаем вывод о том, что "на стыке" поверхностей, где частично отсутствует информация об образующих некоторых вершин многогранника R, возможны ошибки. Нормаль к q4 составила бы с нормалью к q6 меньший угол, который был бы включен в формируемую комбинацию трех углов.
В результате анализа строки, соответствующей грани q7
(игнорируя нули), находим только грани q6 и q7. Однако для нахождения третьей грани придется все же организовать перебор (именно перебор) нулей. Проверим комбинацию граней {q6, q7, q8}. Их совместное решение определяет точку (0, 75, 0), не удовлетворяющую тем же ограничениям. Комбинация {q6, q7, q9} уже рассматривалась.
Анализ следующей строки приводит к необходимости проверки комбинаций {q6, q7, q8} и {q6, q8, q9}. Первая комбинация уже исследовалась, а вторая приводит к получению точки (5, 0, 0), удовлетворяющей всем ограничениям (точка B на рис. 6.3).
Анализ последней строки приводит к необходимости проверки комбинаций {q6, q7, q9} и {q6, q8, q9}. Обе комбинации уже рассматривались: первая — как неудачная, вторая — повторно образующая вершину.
Легко видеть, что если бы мы не выполняли перебор комбинаций нулей, то так и не получили бы вершину, так как при первой возможной комбинации, обусловленной алгоритмом, она ни разу не обнаружилась.
Отсюда вывод: в общем случае необходимо избегать анализа строк матрицы S, соответствующих координатным плоскостям. Помимо того, что это — лишь возможные, но не действительные грани, углы, образуемые нормалями к ним и нормалями к другим граням, могут превышать
Так, в рассмотренном примере анализа верхней поверхности многогранника R достаточно было исследовать первые пять строк матрицы S ( табл. 6.1), опираясь на предположение о наличии "срединных" граней. Ведь в результате этого анализа вершины были найдены.
Напомним, что, выделяя верхнюю и нижнюю поверхности, мы некоторые вершины делаем недоступными для предлагаемого метода. Это — вершины "на стыке" поверхностей. В данном случае это, например, вершины, образуемые комбинациями {q1, q6, q8}, {q4, q6, q9} и др.
Рассмотренный пример анализа нижней поверхности многогранника R приводит к уточнению алгоритма нахождения опорного плана.
Нули — косинусы углов между осями координат — не всегда удается игнорировать. Это характерно для того случая, когда действительных граней, образующих рассматриваемую поверхность, недостаточно (r < n) или анализ соответствующих им строк матрицы S не приводит к успеху. Тогда приходится анализировать строки, соответствующие координатным плоскостям, "добирая" нулевые значения косинусов до общего количества n таких косинусов. При этом неизбежен перебор всех возможных комбинаций таких нулей.
Можно было бы сделать здесь вывод о том, что при подозрении о таких трудностях немедленно следует приступить к поиску опорного плана на другой поверхности. Однако мы не доказали, что хотя бы одна вершина обязательно будет найдена. Это приводит к необходимой готовности воспользоваться, в случае неудачи, одним из проверенных, традиционных методов нахождения опорного плана решения задачи ЛП, — более сложного и практически не распараллеливаемого.
