Линейное программирование. Геометрическая интерпретация и графический метод решения задачи линейного программирования, страница 5

З а м е ч а н и е 2.9. Некоторые авторы обозначают столбец свободных членов символом A₀ .

В более подробной (покомпонентной) записи векторы – столбцы матрицы A и вектор B  будут иметь  следующий вид :

A₁ =,    A₂  =  , …,   A_n=   ,  B =

Тогда постановка задачи в канонической форме примет вид

max z = c₁x₁+c₂x₂+…+c_nx_n                                   (2.8)

A₁x₁+A₂x₂+…+A_nx_n = B                                       (2.9)

                          x₁ ³0, x₂ ³0, …, x_n ³0.                                    (2.10)

Поставим вопрос: каковы должны быть значения компонент вектора X=(x₁, x₂, …, x_n), чтобы такой вектор представлял собой допустимый план задачи (2.8) – (2.10) ?

Из (2.9) видно, что вектор X=(x₁, x₂, …, x_n), x_j³0 ( j=1, …, n) является допустимым  решением (планом) задачи в том и только том случае, когда вектор B выражается как неотрицательная линейная комбинация столбцов матрицы A, где в качестве коэффициентов разложения берутся координаты вектора X. 

Для обозначения таких  планов в ЛП введен специальный термин - “опорный план”.

О п р е д е л е н и е 2.1. План X = (x₁, x₂, …, x_n) задачи (2.8) – (2.10) называется опорным, если система векторов A_j  матрицы A (j=1, …, n), входящих в разложение (2.9), обладает следующими свойствами:

-  векторы  A_j  линейно независимы;

       -  коэффициенты x_j,  в разложении (2.9) положительны.

Из определения опорного плана следует, что число его положительных координат не может превышать m, где m – число ограничений задачи (остальные n-m компонент плана равны 0). Действительно, векторы A_j являются m-мерными, а в m-мерном пространстве максимальное число линейно независимых векторов равно m (см. приложение A).

О п р е д е л е н и е 2.2. Опорный план называется невырожденным, если он содержит m положительных компонент, в противном случае план называется вырожденным.(В вырожденном плане количество положительных компонент меньше m).

Приведем далее ряд теорем, описывающих свойства допустимых планов. С доказательства этих теорем можно ознакомиться в [4].

Теорема 2.1. Множество планов задачи линейного программирования  выпукло (если оно не пусто).

В соответствии с введенной ранее символикой будем обозначать такое выпуклое (ограниченное или неограниченное) множество планов задачи ЛП символом  X.

Теорема 2.2.  Целевая функция задачи линейного программирования достигает своего экстремального значения в вершине многогранника допустимых решений.

Теорема 2.3.  Если целевая функция имеет экстремум более, чем в одной вершине многогранника X, то этот экстремум достигается в любой точке, являющейся выпуклой комбинацией этих точек. (Данная теорема отражает случай, когда экстремум ЦФ достигается во всех точках ребра многогранника решений).

Из теорем 2.2 и 2.3 следует чрезвычайно важный вывод о том, что для отыскания оптимального решения канонической задачи ЛП достаточно исследовать лишь вершины выпуклого многогранника X.

Приведем теорему, устанавливающую связь между введенными геометрическими  и  алгебраическими представлениями в задаче ЛП.

Теорема 2.4. Вектор X является опорным планом задачи (2.8) – (2.10) тогда и только тогда, когда X – вершина многогранника допустимых планов X.

Из рассматриваемой теоремы вытекает, что множество опорных планов задачи линейного программирования совпадает с множеством крайних точек или вершин многогранника X, определяемого условиями задачи.

З а м е ч а н и е 2.10. В [26] признак “опорность” плана объясняется тем, что вершины многогранника условий, соответствующие опорным планам, полностью определяют этот многогранник. (т.е. являются  “опорными точками”  многогранника, по которым этот многогранник можно построить).

Связь рассмотренных терминов может быть проиллюстрирована таблицей 2.1

Таблица 2.1.

Алгебраическое представление	Геометрическое представление
Опорный план	Крайняя точка, вершина многогранника X