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

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


Так, в рассмотренном примере анализа верхней поверхности многогранника R достаточно было исследовать первые пять строк матрицы S ( табл. 6.1), опираясь на предположение о наличии "срединных" граней. Ведь в результате этого анализа вершины были найдены.

Напомним, что, выделяя верхнюю и нижнюю поверхности, мы некоторые вершины делаем недоступными для предлагаемого метода. Это — вершины "на стыке" поверхностей. В данном случае это, например, вершины, образуемые комбинациями {q1, q6, q8}, {q4, q6, q9} и др.

Рассмотренный пример анализа нижней поверхности многогранника R приводит к уточнению алгоритма нахождения опорного плана.

Нули — косинусы углов между осями координат — не всегда удается игнорировать. Это характерно для того случая, когда действительных граней, образующих рассматриваемую поверхность, недостаточно (r < n) или анализ соответствующих им строк матрицы S не приводит к успеху. Тогда приходится анализировать строки, соответствующие координатным плоскостям, "добирая" нулевые значения косинусов до общего количества n таких косинусов. При этом неизбежен перебор всех возможных комбинаций таких нулей.

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




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



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