С войства решений задач линейного программирования

Пусть на плоскости  Ох₂ (рис. 1) заданы две точки: А₁ (х , х ) и А₂ (х , х ), определяющие вектор . Найдем координаты произвольной точки А(х₁, х₂) данного вектора:

рассмотрим вектора ,

Так как ,  коллинеарны и одинаково направлены, то  где 0 £ t £ 1

Þ

Þ

Пусть 1 - t = l₁, t = l₂ Þ  и l₁ ³ 0, l₂ ³ 0, l₁ + l₂ =1.

Рис. 1

Итак: если A = (х₁; х₂), A₁ = (; ), A₂ = (; ), то

A = l₁A₁ + l₂ A₂, l₁ ³ 0, l₂ ³ 0, l₁ + l₂ = 1.               (4)

Точка А, для которой выполняются условия (4), называется выпук­лой линейной комбинацией точек А₁ и А₂. При х₁ = 1, х₂ = 0 точка А совпа­дает с точкой А₁; при х₁ = 0, х₂ = 1 – с концом A₂. Таким образом для любой внутренней точки А отрезка [А₁А₂] выполняются условия (4).

Точки А₁ и А₂ называются угловыми или крайними точками отрезка [А₁А₂]. Очевидно, что угловая точка не может быть представлена как вы­пуклая линейная комбинация двух других точек отрезка.

Соотношения верны и для n-мерного пространства:

Ā = λ₁Ā₁, + λ₂Ā₂ +... + λ_nĀ_n, при λ₁ ³ 0, .

Множество точек называется выпуклым, если оно вместе с любыми двумя точками содержит и их произвольную выпуклую линейную комбинацию. Геометрический смысл этого определения состоит в том, что множеству вместе с его двумя любыми точками полностью принадлежит и весь отрезок, их соединяющий. Примерами выпуклых множеств явля­ется: отрезок, прямая, полуплоскость, круг, шар, куб, пирамида, полупространство и т. д. Пример не выпуклого множества показан на рис. 2., т. к. [А₁ А₂] полностью этому множеству не принадлежит.

Рис. 2

Точка множества называется граничной, если любой шар с центром в этой точке содержит как точки принадлежащие множеству, так и не принадлежащие множеству. Граничные точки множества образуют его границу.

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

Угловой точкой выпуклого множества называется точка, которая принадлежит этому множеству, но не является внутренней ни для какого отрезка, целиком лежащего в заданном множестве. Например, у много­угольника угловыми точками являются его вершины, у круга – точки ок­ружности, которая его ограничивает. Таким образом, выпуклое множе­ство может иметь конечное и бесконечное число угловых точек.

Опорной прямой выпуклого многоугольника (многогранника) назы­вается прямая, имеющая с многоугольником (многогранником), распо­ложенным по одну сторону от нее, хотя бы одну общую точку.

Теорема 1

Замкнутый, ограниченный, выпуклый многоугольник является вы­пуклой линейной комбинацией своих угловых точек.

Пример 3. Даны точки А₁(3; – 2; 5) и A₂(– 1; 6; 1). Найти точку А (х₁; х₂; x₃), являющуюся линейной комбинацией точек А₁ и A₂. Так как точка А является линейной комбинацией точек А₁ и A₂, то Ā =     = l₁Ā₁ + l₂Ā₂, l₁ ³ 0, l₁ + l₂ = 1.

Пусть, например, l₁ = , тогда l₂ =  Þ (х₁; х₂; x₃) = (3; –2; 5) + + (-1; 6; 1) = (; ; ), отсюда х₁ = ; х₂ = ; х₃ = .

Теорема 2

Если система векторов , , …, содержит m линейно незави­симых векторов , , , то допустимый план

= (х₁, х₂, …, x_m, 0, 0…0), n – является угловой точкой мно-              

                                           ()

гоугольника планов.    

Теорема 3

Если задача линейного программирования имеет решение, то целе­вая функция достигает экстремального значения, хотя бы в одной из уг­ловых (крайних) точек многогранника решений. Если же целевая функ­ция достигает экстремального значения больше, чем в одной угловой точке, то она достигает того же значения в любой точке, являющейся их выпуклой линейной комбинацией.