Читать онлайн «Мёртвая вода. Часть 2». Страница 53

Картофелина после её обрезки ножом — трехмерный эквивалент такого n-мерного многогранника. Свойство выпуклости проявляется в том, что, если из любой точки на её поверхности картофелину проткнуть прямолинейной спицей в произвольном направлении, то спица войдет в картофелину и выйдет из неё только по одному разу: т.е. одно пронзание спицей картофелины на её поверхности оставляет только две дырки.

Аргумент Z функции Min(Z) критерия оптимальности — также линейная функция n переменных:

Z = rTXK = (r1 , r2 , ... , rn)(XK 1 , XK 2 , ... , XK n)T =

= r1XK 1 + r2XK 2 + ... + rnXK n .

То есть скалярное произведение векторов 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 . Ориентация “торта” в пространстве предполагает, что слои его могут быть расположены вовсе не параллельно по отношению к плоской поверхности стола, на которую помещен “торт”. Потом этот “торт” следует обрезать “ножом”, как того требуют неравенства-ограничения. И после этого, если на столе что-то останется[141], из обрезанного  пространственно ориентированного “слоеного торта”, следует вынуть одну из плоскостей (“вафель” или “прослоек”), в которой достигается наименьшее (или наибольшее: 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, достигаемого в них.

Аналогичное утверждение доказано в линейной алгебре математически строго для n-мерного пространства. Алгоритм перебора вершин n-мерного выпуклого многогранника и выбора в них экстремального значения критерия оптимальности называется симплекс-метод. В разных модификациях он известен с 1940 г. Этот алгоритм также позволяет ответить и на вопросы о совместимости системы ограничений и о существовании решений либо же об отсутствии таковых. То есть работоспособность аппарата линейного программирования абстрактно-математически подтверждена уже более, чем 50 лет. А “слоеный пространственно ориентированный торт” нам потребовался только для наглядности, предметной образности изложения, а те, кому необходимы формально-математические доказательства изложенного и практические алгоритмы решения, могут найти их в специальной литературе.

Мы записали ограничения задачи линейного программирования (ЛП) в виде:

 (E - A) XK = FK =>FK min ,

а не как это принято при математически канонической записи задачи линейного программирования:

(E - A) XK  =>FK min

Дело в том, что при канонической записи задачи ограничения налагаются явно на левую часть абстрактного математического уравнения, которое по умолчанию в рассматриваемом нами случае приложения математического аппарата является уравнением межотраслевого баланса реального продуктообмена. В реальном же продуктообмене непосредственный интерес представляет выполнение FK ³ FK min , а не обусловленность вектора конечной продукции FK  вектором валовых мощностей XK и матрицей A . Поскольку вектор FK является в нашем контексте идентификатором, уже несущим определенный экономический смысл, который может выпасть из восприятия читателя при записи ограничений в обычном для математического канона их виде (E - A) XK  ³ FK min , то нами избрана такая форма напоминания, хотя чисто формально математически правая и левая части уравнения равноправны, а решать задачу ЛП‑П придется в канонической записи: т.е. по отношению к левой части уравнения продуктообмена.

Практически в каждой книге, в которой рассматривается линейное программирование (ЛП), излагается теория двойственности. Её смысл сводится к следующему: задаче ЛП 

A x =<b

 x =>0                    (ЛП-1)

Найти Max(cTx)

математически объективно соответствует задача ЛП:

AT y =>c

 y =>0                   (ЛП-2)

Найти Min(bTy)

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