8. Выпуклый n-мерный многогранник является выпуклой линейной комбинацией своих угловых точек.

Доказательство. Возьмем для простоты n=2, а в качестве многоугольника – треугольник X1X2X3. Через произвольную точку Х треугольника проведем отрезок Х1Х4. Поскольку точка Х лежит на этом отрезке, то Х=α1Х1 + α4Х4, где α1≥0, α2≥0, α1+α4=1.

Точка Х4 лежит на отрезке Х2Х3, следовательно, Х4= α2Х2+ α3Х3, где α2≥0, α3≥0, α2+α3=1. Подставив значение Х4 в выражение для Х, получим Х= α1Х1 + α4(α2Х2+ α3Х3)= α1Х1 + α2 α4Х2 + α3α4Х3.

Обозначив t1= α1, t2= α2α4, t3= α3α4, получим окончательно X=t1X1+t2X2+t3X3, где t1≥0, t2≥0, t3≥0 и t1+t2+t3=1.

Таким образом, точка Х есть выпуклая линейная комбинация угловых точек треугольника Х1Х2Х3.

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

Доказательство. Пусть Х1=(х1(1), х2(1),…,xn(1)) и X2=(x1(2), x2(2),…,xn(2) – два допустимых решения задачи, заданной в матричной форме. Тогда АХ1=В и АХ2=В. Рассмотрим выпуклую линейную комбинацию решений Х1 и Х2, т.е. Х=α1Х1 + α2Х2 при α1≥0, α2≥0 и α1 + α2 =1, и покажем, что она также является решением системы. В самом деле, АХ = А(α1Х1 + α2Х2) = α1АХ1 + (1- α1)АХ2 = α1В + (1- α1)В=В, т.е. решение Х удовлетворяет системе. Но так как Х1≥0, Х1≥0, α1≥0, α2≥0, то и Х ≥0, т.е решение Х удовлетворяет и условию.

10. Теорема об экстремальном значении целевой функции.

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

Доказательство. Будем полагать, что многогранник решений является ограниченным. Обозначим его угловые точки через Х1, Х2, …, Хр, а оптимальное решение – через Х*. Тогда F(X*)≥F(X) для всех точек Х многогранника решений. Если Х* - угловая точка, то первая часть теоремы доказана. Предположим, что Х* не является угловой точкой , тогда на основании теоремы о выпуклом многоугольнике, являющемся выпуклой линейной комбинацией своих угловых точек, Х* можно представить как выпуклую линейную комбинацию угловых точек многогранника решений, т.е. Х*= α1Х1 + α2Х2 +…+ αрХр, αj≥0, j=1,p; j=1Σn αj=1.

Так как F(X) линейная функция, получаем F(X*)=F(α1Х1 + α2Х2 +…+ αрХр)= α1F(X1) + α2F(X2) + … + αpF(Xp). (1)

В этом разложении среди значений F(xj) (j=1,p) выберем максимальное. Пусть оно соответствует угловой точке Xk (1≤k≤p); обозначим его черех М, т.е. F(Xk)=M. Заменим в выражении (1) каждое значение этим максимальным значением М. Тогда, учитывая, что αj≥0, j=1Σp αj=1, найдем F(X*)≤α1M + α2M + … + αpM= M j=1 Σp αj=M. По предположению Х* - оптимальное решение, поэтому, с одной стороны, F(X*)≥F(Xk)=М, но, с другой стороны, доказано, что F(X*)≤М, следовательно, F(X*)=М=F(Xk), где Xk – угловая точка. Итак, существует угловая точка Xk, в которой линейная функция принимает максимальное значение.

Для доказательства второй части теоремы допустим, что F(X) принимает максимальное значение более чем в одной угловой точке, например, в точках X1, X2, … Xq, где 1≤q≤p; тогда F(X1)=F(X2)=…=F(Xq)=M.

Пусть Х – выпуклая комбинация этих угловых точек, т.е Х= α1Х1 + α2Х2 +…+ αqХq, aj≥0 (j=1,q), j=1Σq aj=1. В этом случае, учитывая, что функция F(X) – линейная, получим F(X)=А(α1Х1 + α2Х2 +…+ αqХq)= α1F(X1) + α2F(X2) + … + αqF(Xq) = α1M + α2M +…+ αqM = M j=1Σq aj=M, т.е. линейная функция F принимает максимальное значение в произвольной точке Х, являющейся выпуклой линейной комбинацией угловых точек X1, X2,…., Xq.