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

Теорема 1

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

■ Доказательство:

Рассмотрим задачу линейного программирования в матричной форме:

F = CX ® max (min), (I)

АХ = В, (II)

Х ³ 0, (III)

где С = (с₁,...,с _j ,..., с_n), В = (b₁,...b_i ,...,b_m) ^Т, Х = (х_1, х₂, ..., х _n) ^Т ,

А =

Пусть Х₁ = (х₁⁽¹⁾, х₂⁽¹⁾ , ..., х_n⁽¹⁾) ^Т, Х₂ = (х₁⁽²⁾, х₂⁽²⁾ , ..., х_n ⁽²⁾) ^Т – допустимые базисные решения задачи (I) , (II) , (III).

Тогда выполняются условия:

АХ₁ = В, АХ₂ = В, Х₁ ³ 0, Х₂ ³ 0.

Рассмотрим выпуклую линейную комбинацию решений Х₁ и Х₂:

Х = l₁Х₁ + l₂Х₂, l₁ + l₂ = 1, l₁ ≥ 0, l₂ ≥ 0.

АХ = А(l₁Х₁ + l₂Х₂) = l₁АХ₁ + l₂АХ₂ = l₁В + l₂В = l₁В + (1–l₁) В = В.

Таким образом, произвольное решение Х, которое является ВЛК допустимых базисных решений Х₁ и Х₂ удовлетворяет ограничениям задачи.

Имеем l₁ ≥ 0, l₂ ≥ 0, Х₁ ³ 0, Х₂ ³ 0 Þ Х = l₁Х₁ + l₂Х₂ ³ 0. Условие неотрицательности выполнено. ■

Следующая теорема дает ответ на вопрос, в какой точке области решений возможно оптимальное решение.

Теорема 2

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

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

■ Доказательство первой части теоремы.

Будем предполагать, что область допустимых решений – выпуклый ограниченный многогранник. Обозначим угловые точки области Х₁,… , Х_р , а Х* – оптимум (максимальное значение). Тогда F(X*) ³ F(X) для " Х Î ОДР.

Если Х* – угловая точка, то первая часть теоремы доказана.

Предположим, что Х* – не является угловой, тогда на основании первой теоремы ее можно представить как выпуклую линейную комбинацию угловых точек.

Х* – ВЛК угловых точек Х₁,… , Х_р ОДР:

Х* = l₁Х₁ + l₂Х₂ +… + l_рХ_р l_j ≥ 0, (1 ≤ j ≤ р), l₁ + l₂ + … + l_р = 1.

Так как F (Х) линейная функция, получаем:

F(X*) = F(l₁Х₁ + l₂Х₂ +…+ l_рХ_р) = l₁F(Х₁) + l₂F(Х₂) + …+ l_рF(Х_р).

Обозначим F(Х_к) = М – наибольшее значение среди F(Х _j) (1 ≤ j ≤ р). Заменив остальные слагаемые числом М, перейдем к неравенству:

F(X*) ≤ l₁М + l₂М +… + l_рМ = М.

По предположения Х* – оптимальное (максимальное) решение, поэтому

F(X*) ³ F(X_к) = М, но с другой стороны F(X*) ≤ М Þ F(X*) = F(Х_к) = М.

II. Докажем вторую часть теоремы.

Для доказательства предположим, что целевая функция принимает оптимальное значение более, чем в одной угловой точке. Например, Х₁, Х₂,… , Х_q – угловые точки ОДР, (1 ≤ q ≤ р). F(X₁) = F(X₂) = … = F(X_q) = M.

Точка Х – ВЛК Х₁, Х₂, … , Х_q:

Х = l₁Х₁+ l₂Х₂ +… + l_qХ_q, l_j ≥ 0, (1 ≤ j ≤ q), l₁ + l₂ + … + l_q = 1.

Учитывая, что F (Х) – линейная функция, имеем:

F(X) = F(l₁Х₁ + l₂Х₂ +… + l_qХ_q) = l₁F(Х₁) + l₂F(Х₂) +...+ l_qF(Х_q) = M. ■

Следующая теорема посвящена аналитическому методу нахождения угловых точек.

Теорема 3

Каждому допустимому базисному решению ЗЛП соответствует угловая точка многогранника решений, и наоборот каждой угловой точке многогранника решений соответствует допустимое базисное решение.

Векторная форма записи ЗЛП:

Z = C*X ® max (min), где C = (с₁, с₂, ...,с _n), Х = (х_1, х₂, ...., х _n), целевая функция Z является скалярным произведением векторов С и Х.

А₁х₁ + А₂х₂ +...+ А_nх_n = В

где В = (в₁,..., в_i ,..., в_m)^Т А _j = (а_{1 j}, а_{2 j}, ..., а_{m j})^Т (1 ≤ j ≤ п),

А₁, А₂ , … , А_m – базисные векторы.

На основе векторной записи ЗЛП теорему 3 перефразируем следующим образом:

Теорема (I часть)

Если существует вектор Х = { x₁, x₂, … , x_k,0, … ,0}, x_j > 0, (1 ≤ j ≤ k), k ≤ m,

что А₁х₁ + А₂х₂ + …+ А_kх_k = В, то Х – угловая точка ОДР.

■ Докажем теорему от противного.

Пусть точка Х не является угловой, тогда точку Х, как внутреннюю точку области решений можно представить как выпуклую линейную комбинацию точек Х⁽¹⁾, Х⁽²⁾ .

Пусть Х⁽¹⁾, Х⁽²⁾ – допустимые базисные решения ЗЛП.

Х =l Х⁽¹⁾ + (1 – l ) Х⁽²⁾, 0 < l < 1.

В координатной форме:

x_j = l x_j ⁽¹⁾ + ( 1 – l ) x_j ⁽²⁾, ( 1 ≤ j ≤ n ).

Векторы А₁, А₂, … , А_k являются базисными.

А₁х₁⁽¹⁾ + А₂х₂⁽¹⁾ +…+ А_kх_k⁽¹⁾ = В, А₁х₁⁽²⁾ + А₂х₂⁽²⁾ +…+ А_kх_k⁽²⁾ = В.

Рассмотрим разность разложений:

А₁х₁⁽¹⁾ + А₂х₂⁽¹⁾ +…+ А_kх_k⁽¹⁾ – (А₁х₁⁽²⁾ + А₂х₂⁽²⁾ +…+А_kх_k⁽²⁾) = А₁(х₁⁽¹⁾ – х₁⁽²⁾) +А₂(х₂⁽¹⁾ – – х₂⁽²⁾) +…+ А_k(х_k⁽¹⁾ – х₂⁽²⁾) = 0

Так как А₁, А₂, . .., А_k – линейно независимы, тогда согласно определению линейно независимых векторов х_j ⁽¹⁾ – х_j ⁽²⁾ = 0 , (1 ≤ j ≤ k), Þ Х⁽¹⁾ = Х⁽²⁾ ■

Теорема (I I часть)

Если Х – угловая точка области допустимых решений, то она является допустимым базисным решением ЗЛП.

■ Доказательство:

Х = (х₁, х₂, ..., х_m, 0, ..., 0) – угловая точка ОДР. Х ³ 0.

Если А₁, А₂, .., А_m – линейно независимы, то ранг матрицы А r(А) = m и

переменные х_1, х₂, ..., х_m основные, решение Х = (х_1, х₂, ..., х_m,0, ..., 0) допустимое и базисное.

Предположим, что А₁, А₂,. .., А_m – линейно зависимы, тогда

l₁А₁ + l₂А₂ + … +l_mА_m = 0 при некоторых l_j ≠ 0. (a)

Рассмотрим произвольное положительное число μ = Const, μ > 0.

Умножим выражение (a) на μ: μl₁А₁ + μl₂А₂ + … + μl_mА_m = 0 (в)

Подставив координаты Х в систему ограничений, имеем:

А₁х₁ + А₂х₂ + … + А_mх_m = В (с)

Из (в) и (с):

А₁(х₁ + μl₁) + А₂(х₂ + μl₂) + …+ А_m(х_m + μl_m) = В,

А₁(х₁ – μl₁) + А₂(х₂ – μl₂) + … + А_m(х_m – μl_m) = В.

Тогда полученные решения Х₁ = (х₁ + μl₁, х₂ + μl₂, х_m + μl_m, 0, …,0) и

Х₂ = (х₁ – μl₁, х₂ – μl₂, х_m – μl_m,0,…, 0) при любом μ удовлетворяют системе ограничений.

Так как Х ³ 0 можно подобрать такое малое значение μ, что Х₁ , Х₂ будут различными допустимыми решениями. Причем, 0,5( Х₁ + Х₂ ) = Х . То есть точка Х лежит на середине отрезка, соединяющего точки Х₁ , Х₂ , значит точка Х не является угловой, что противоречит условиям теоремы. ■