СССР Внутренний Предиктор - Мертвая Вода Том 2

r TX K- Z = 0 .

При численно не определённом значении свободного члена Z этого уравнения пространство заполнено “пакетом” параллельных гиперплоскостей, каждая из которых “касается” соседних с нею двух. В трехмерной аналогии это - “слоёный вафельный торт”, в котором исчезающе тонкие вафли и прослойки начинки между ними - плоскости, различимые по значению Z каждой из них.

В задаче линейного программирования координаты точек, т.е. конкретный набор значений X K 1, X K 2,…, X K n , определяющий значение аргумента Z = r TX K критерия оптимальности Min(Z) , могут выбираться только из области, вырезанной всем набором неравенств-ограничений из n- мерного пространства.

То есть в трехмерной аналогии, нам сначала необходимо ориентировать в пространстве “слоеный торт” так, чтобы пакет плоскостей имел ориентацию, определяемую значениями r 1, r 2,…, r n . Ориентация “торта” в пространстве предполагает, что слои его могут быть разположены вовсе не параллельно по отношению к плоской поверхности стола, на которую помещен “торт”. Потом этот “торт” следует обрезать “ножом”, как того требуют неравенства-ограничения. И после этого, если на столе что-то останется [177] , из обрезанного пространственно ориентированного “слоёного торта”, следует вынуть одну из плоскостей (“вафель” или “прослоек”), в которой достигается наименьшее (или наибольшее: Min(Z)=Max(-Z) ) из значений аргумента Z критерия оптимальности: Z = r 1X K 1+ r 2X K 2+… + r nX K n. Поскольку на поверхности стола должна быть известна точка, соответствующая началу координат (например один из углов столешницы), то, чтобы выделить искомое решение, придётся вынуть из “торта” плоскость, самую близкую к ней (или самую удаленную от неё), так как экстремальное значение Min(Z) или Max(Z) однонаправленно обусловлены удаленностью от начала координат. Разстоянием между точкой и плоскостью в трехмерном пространстве является перпендикуляр, опущенный из точки на плоскость.

Так как “торт” прошёл обрезку, то искомая плоскость (вафля или прослойка) может быть представлена либо, как точка-крошка, лежащая в одной из вершин вырезанного из “слоёного торта” многогранника; либо как тонкая полоска-ребро многогранника, по которому пресекаются его грани; либо как одна из граней многогранника, совпадающая по направленности с ориентацией пакета параллельных плоскостей. Вариант решения определяется пространственной ориентацией слоев и характером обрезки “торта” ножами-ограничениями.

Однако задача может и не иметь решений, если ограничения противоречат одно другим; например: X 1‹1 и X 1› 3 . На первом шаге обрезки пространственно ориентированного “слоеного торта” ограничение X 1‹1 сметает со стола за ненадобностью всё, где X 1› 3 ; на втором шаге обрезки X 1› 3 сметает со стола всё, оставшееся после первой обрезки, поскольку оно разположено там, где X 1‹3 . При такой обрезке “торта” на столе просто ничего не останется, но и это не является решением задачи, поскольку в ней необходимо удовлетворить взаимно изключающим требованиям.

Если задача имеет решение, то одна из вершин многогранника принадлежит решению. Даже, если решение выглядит геометрически, как одна из граней или ребро, то все решения, принадлежащие такому множеству оптимальных решений, формально математически неразличимы по критерию оптимальности Min(Z) или Max(Y) , так как значение Z либо Y в пределах таких ребра или грани - неизменны. В таком случае выбор оптимального из множества математически оптимальных решений предполагает разсмотрение каждого из решений во множестве математически оптимальных с учётом информации, которой не нашлось места в формально математической модели.

Соответственно процесс поиска решения задачи линейного программирования, оптимального в смысле достижения Min или Max линейного критерия, сводится к последовательному перебору конечного числа вершин выпуклого многогранника и выбору экстремального из множества значений Z , достигаемого в них.

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

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

( E- A) X K= F Kі F K min,

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

( E- A) X Kі F K min

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

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

Ax Ј b

x 0 (ЛП-1)

Найти Max(c Tx)

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

A Ty і c

y 0 (ЛП-2)

Найти Min(b Ty)

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