То есть скалярное произведение векторов rTXK в ортогональном базисе - также уравнение гиперплоскости. Её направленность в пространстве определяется набором коэффициентов r1, r2,…, rn . При этом вектор r=(r1, r2,…, rn)T ортогонален (т.е. перпендикулярен) к гиперплоскости, задаваемой уравнением Z = rT XK. Удаленность гиперплоскости от начала системы координат обусловлена значением Z, являющемся свободным членом уравнения:
rT XK - Z = 0.
При численно не определённом значении свободного члена Z этого уравнения пространство заполнено “пакетом” параллельных гиперплоскостей, каждая из которых “касается” соседних с нею двух. В трехмерной аналогии это - “слоёный вафельный торт”, в котором исчезающе тонкие вафли и прослойки начинки между ними - плоскости, различимые по значению Z каждой из них.
В задаче линейного программирования координаты точек, т.е. конкретный набор значений XK 1, XK 2,…, XK n , определяющий значение аргумента Z = rT XK критерия оптимальности Min(Z), могут выбираться только из области, вырезанной всем набором неравенств-ограничений из n-мерного пространства.
То есть в трехмерной аналогии, нам сначала необходимо ориентировать в пространстве “слоеный торт” так, чтобы пакет плоскостей имел ориентацию, определяемую значениями r1, r2,…, rn. Ориентация “торта” в пространстве предполагает, что слои его могут быть разположены вовсе не параллельно по отношению к плоской поверхности стола, на которую помещен “торт”. Потом этот “торт” следует обрезать “ножом”, как того требуют неравенства-ограничения. И после этого, если на столе что-то останется
[177], из обрезанного пространственно ориентированного “слоёного торта”, следует вынуть одну из плоскостей (“вафель” или “прослоек”), в которой достигается наименьшее (или наибольшее: Min(Z)=Max(-Z)) из значений аргумента Z критерия оптимальности: Z = r1XK 1 + r2XK 2 +… + rnXK n . Поскольку на поверхности стола должна быть известна точка, соответствующая началу координат (например один из углов столешницы), то, чтобы выделить искомое решение, придётся вынуть из “торта” плоскость, самую близкую к ней (или самую удаленную от неё), так как экстремальное значение Min(Z) или Max(Z) однонаправленно обусловлены удаленностью от начала координат. Разстоянием между точкой и плоскостью в трехмерном пространстве является перпендикуляр, опущенный из точки на плоскость.
Так как “торт” прошёл обрезку, то искомая плоскость (вафля или прослойка) может быть представлена либо, как точка-крошка, лежащая в одной из вершин вырезанного из “слоёного торта” многогранника; либо как тонкая полоска-ребро многогранника, по которому пресекаются его грани; либо как одна из граней многогранника, совпадающая по направленности с ориентацией пакета параллельных плоскостей. Вариант решения определяется пространственной ориентацией слоев и характером обрезки “торта” ножами-ограничениями.
Однако задача может и не иметь решений, если ограничения противоречат одно другим; например: X1 ‹1 и X1› 3. На первом шаге обрезки пространственно ориентированного “слоеного торта” ограничение X1 ‹1 сметает со стола за ненадобностью всё, где X1› 3; на втором шаге обрезки X1› 3 сметает со стола всё, оставшееся после первой обрезки, поскольку оно разположено там, где X1 ‹3 . При такой обрезке “торта” на столе просто ничего не останется, но и это не является решением задачи, поскольку в ней необходимо удовлетворить взаимно изключающим требованиям.
Если задача имеет решение, то одна из вершин многогранника принадлежит решению. Даже, если решение выглядит геометрически, как одна из граней или ребро, то все решения, принадлежащие такому множеству оптимальных решений, формально математически неразличимы по критерию оптимальности Min(Z) или Max(Y), так как значение Z либо Y в пределах таких ребра или грани - неизменны. В таком случае выбор оптимального из множества математически оптимальных решений предполагает разсмотрение каждого из решений во множестве математически оптимальных с учётом информации, которой не нашлось места в формально математической модели.
Соответственно процесс поиска решения задачи линейного программирования, оптимального в смысле достижения Min или Max линейного критерия, сводится к последовательному перебору конечного числа вершин выпуклого многогранника и выбору экстремального из множества значений Z, достигаемого в них.
