Алгоритм. Пример
Выше фактически уже описан алгоритм нахождения хотя бы одной вершины многогранника допустимых решений. Сведем вместе все необходимые построения.
Алгоритм.
- Определим направление возрастания целевой функции и выделим грани многогранника допустимых решений, образующие верхнюю (нижнюю) его поверхность. Дополним ее возможными гранями — координатными плоскостями.
- Составим матрицу S косинусов углов между всеми нормалями к действительным и возможным граням сформированной поверхности многогранника допустимых решений.
- Если число r действительных граней верхней (нижней) поверхности не меньше n — размерности задачи, выполняем первый этап алгоритма, исключив из рассмотрения строки и столбцы матрицы S, соответствующие координатным плоскостям.
- Этот пункт является общим для первого и второго этапов. Выбрав произвольно грань или организовав перебор всех граней, или организовав параллельный анализ всех граней, выберем в соответствующей этой грани строке матрицы S n максимальных косинусов. В этой последовательности косинусов, кроме максимального косинуса угла между нормалью выбранной грани и ею же самой, не должно быть косинусов, равных 1 или -1. Таким образом, окажутся выделенными n возможных образующих некоторой вершины многогранника допустимых решений.
- Решаем совместно уравнения выделенных граней.
- Если решение существует и оно неотрицательно, произведем анализ: удовлетворяет ли найденная точка всем ограничениям задачи? Если удовлетворяет, точка действительно является вершиной многогранника. В противном случае необходимо продолжить анализ граней, то есть строк матрицы S.
- Если перебор всех строк матрицы S не привел к успеху на первом этапе выполнения алгоритма, переходим ко второму этапу, введя в рассмотрение координатные плоскости, т.е. начинаем анализ матрицы в полном объеме. Если успех не был достигнут на втором этапе, то, как указано ниже, можно испытать удачу на другой — нижней (верхней) поверхности многогранника допустимых решений. Ведь важно найти хоть какую-то вершину, пусть не столь близкую к вершине-решению.
Если мы и теперь не достигли успеха…
В рассматриваемом примере верхнюю поверхность (где следует искать решение) образуют грани (6.6). Поскольку переименование малого количества граней в соответствии с (6.7) не имеет смысла, составим для этих граней и их нормалей таблицу, включающую матрицу косинусов углов между нормалями. Соответствующие косинусы считаем по (6.9) и (6.10), таблицу строим по образу таблицы 6.1. Матрица S в таблице выделена.
Реализуем первый этап алгоритма поиска вершины, исключив из рассмотрения три последние строки и столбцы.
Выберем грань q1. Максимальные косинусы соответствующей (первой) строки матрицы S указывают на систему граней {q1, q2, q3}. Решаем уравнения граней совместно и проверяем решение на выполнение всех неиспользованных ограничений задачи. Получаем вершину E(13, 8, 4).
| q1 | N1 | l | 0,59 | 0,59 | 0,067 | 0,171 | 0,026 | 0,09 | -0,99 |
| q2 | N2 | 0,59 | 1 | 0,9 | -0,43 | -0,29 | -0,56 | 0,625 | -0,56 |
| q3 | N3 | 0,59 | 0,9 | 1 | -0,25 | -0,125 | -0,28 | 0,46 | -0,84 |
| q4 | N4 | 0,067 | -0,43 | -0,25 | 1 | 0,99 | -0,16 | -0,975 | -0,16 |
| q5 | N5 | 0,171 | -0,29 | -0,125 | 0,99 | 1 | -0,27 | -0,92 | -0,27 |
| q7 | N7 | 0,026 | -0,56 | -0,28 | -0,16 | -0,27 | 1 | 0 | 0 |
| q8 | N8 | 0,09 | 0,625 | 0,46 | -0,975 | -0,92 | 0 | 1 | 0 |
| q9 | N9 | -0,99 | -0,56 | -0,84 | -0,16 | -0,27 | 0 | 0 | 1 |
Для грани q3 получаем ту же систему образующих граней, т.е. ту же вершину E.
По строке табл. 6.4 (матрицы S), соответствующей q4, находим систему {q1, q4, q5}, решением которой является вершина L{6, 10, 4}.
Анализируя строку грани q5, вновь получаем ту же вершину.
Таким образом, мы добились успеха без рассмотрения координатных плоскостей. Однако для полноты анализа исследуем матрицу S полностью.
Анализ строк 1, 3, 4, 5 порождает те же результаты. Максимальные косинусы второй строки, соответствующей грани q2, указывают на систему {q2, q3, q8}. Решаем уравнения совместно и проверяем выполнение всех неиспользованных ограничений.
Получаем вершину D(6, 0, 2).
Со строкой, соответствующей q7, начинаются трудности, обусловленные следующими факторами:
- Координатная плоскость — возможная, но не действительная грань.
- Именно нормали к координатным плоскостям образуют угол . Нулевое значение этого косинуса неоднозначно соответствует углам
и
. Поэтому невозможно правильно упорядочить углы по неубыванию, используя отрицательные и нулевые значения косинусов.
Если, не зная, что делать с нулями, упорядочить только косинусы углов между нормалью к q7 (x = 0) и нормалями к граням-границам, то первые три косинуса невозрастающей последовательности укажут на грани {q1, q4, q7}. Однако точка (0, 11, 4) — решение этой системы — не является вершиной многогранника R, так как не удовлетворяет ограничению q6.
Для возможной грани q8, также не обращая внимание на нули, находим систему {q2, q3, q8}, решением которой является вершина D(6, 0, 2). (По-видимому, углы между нормалями не вышли из диапазона [0,
По последней строке, соответствующей возможной грани q9, находим систему {q4, q5, q9}, решением которой является вершина K(10, 10, 0).
(Неслучайность успеха в последних трех случаях нуждается в обосновании.)
Отметим, что нет гарантии получения всех вершин поверхности. Ведь группируя вместе грани, мы отдаем предпочтение вершинам с "пологими" склонами, выбирая максимальные значения косинусов. В частности, мы ни разу здесь не получили вершину F(17, 8, 0), в которой целевая функция принимает максимальное значение. Так что второй этап решения задачи ЛП неизбежен. Более того, необходимо не качественное, а аналитическое доказательство того, что рассмотренным путем при выполнении определенных условий будет получена хотя бы одна вершина многогранника R допустимых решений задачи. То есть необходимо доказать теорему существования.
