Билет №17 Число опорных решений канонической задачи линейного программирования

КЗЛП имеет конечное число различных опорных решений.

Любому опорному решению задачи соответствует не менее одного базиса системы векторов условий задачи. Один и тот же базис системы векторов условий рассматриваемой задачи не может быть базисом двух различных опорных решений этой задачи. Следовательно, число опорных решений не превосходит числа базисов системы векторов условий задачи. В то же время, число базисов любой системы из n m-мерных векторов конечно и не превосходит числа сочетаний из n по m, то есть c=n!/(n-m)!m!.

Следовательно, число опорных решений КЗЛП тоже конечно.

Билет №18

Связь базиса системы векторов условий КЗЛП с базисом некоторого опорного решения этой задачи

Базис системы векторов условий КЗЛП (1)-(3) является базисом некоторого опорного решения этой задачи тогда и только тогда, когда вектор ограничений В СЛУ (2) линейно выражается через базисные векторы с неотрицательными коэффициентами.

Необходимость. Пусть Аі₁, Аі₂, …, Аіr базис системы векторов условий задачи (1)-(3) является базисом опорного решения α=(α₁,…,αј,…,αn) этой задачи. Из определения базиса опорного решения следует, что αі=0 для любых і≠і₁,і₂,…,іr.

По определению, опорное решение является допустимым решением задачи(1)-(3), то есть оно удовлетворяет ограничениям (3) αі₁≥0, αі₂≥0,…, αіr≥0 и является решением СЛУ (2),то есть обращает ее в точное числовое равенство вида Аі₁ αі₁+ Аі₂ αі₂+…+Аіr αіr=В. Следовательно, вектор ограничений В линейно выражается через базисные векторы Аі₁, Аі₂,…,Аіr с неотрицательными коэффициентами.

Достаточность. Пусть Аі₁, Аі₂,…,Аіr базис системы векторов условий задачи (1)-(3) и вектор ограничений В представим в виде Аі₁ αі₁+ Аі₂ αі₂+…+Аіr αіr=В,где αі₁≥0, αі₂≥0,…, αіr≥0. Рассмотрим вектор α=(0,…,0,αі₁,0,…,0,αі₂,0,…,0,αіr,0,…,0). Очевидно, что этот вектор удовлетворяет условию (3) и является решением СЛУ (2). Следовательно, вектор α является допустимым решением задачи(1)-(3), причем его ненулевым координатам соответствуют векторы из набора базисных векторов Аі₁, Аі₂,…,Аіr. Может случиться, что среди координат αі₁,αі₂,…,αіr окажутся такие, которые равны нулю(например, если вектор α является вырожденным). в этом случае остальным ненулевым координатам вектора будут соответствовать некоторая часть базисных векторов, которая будет линейно независимой. Таким образом, вектор α по определению является опорным решением задачи(1)-(3). Кроме того, векторы условий данной задачи, не попавшие в набор базисных векторов Аі₁, Аі₂,…,Аіr, будут соответствовать нулевым координатам рассматриваемого вектора α.

Следовательно, набор базисных векторов Аі₁, Аі₂,…,Аіr системы векторов условий задачи (1)-(3) является базисом опорного решения α.

Билет №19

Теорема об оптимальном решении КЗЛП

Рассмотрим КЗЛП

(4) f(X)=∑ γј*хј+γ₀,

(5) ∑ Ај*хј=В,

(6) хј≥0, ј=1,2,…,n.

Если КЗЛП имеет оптимальные решения, то одно из них является опорным решением этой задачи.

Рассмотрим оптимальное решение задачи с наименьшим числом нулевых координат. Пусть таким решением будет вектор α°=(α₁,…,α₁,0,…,0),где координаты α₁>0, ,α₁<0(координаты всегда можно перенумеровать так, чтобы первыми из них стали ненулевые) и докажем, что выбранный вектор является опорным решением задачи.

Предположим противное, а именно, что вектор α° не является опорным решением. Тогда по определению опорного решения, векторы А₁,А₂,…,А₁, соответствующие ненулевым координатам выбранного вектора α°, образуют линейно зависимую систему, то есть можно указать ненулевой набор чисел k₁, k₂,…,k₁ такой, что будет выполняться соотношение:

А₁k₁+А₂k₂+…+А₁k₁=Ѳ.

Так как вектор α° является оптимальным решением, то он является и допустимым решением задачи, то есть, этот вектор является решением системы линейных уравнений(2). Тогда по определению решения системы уравнений должно выполняться соотношение:

А₁α₁+А₂α₂+…+А₁α₁=В.

Прибавив к соотношению (5) соотношение (4),умноженное на ±δ, получим

А₁(α₁±δ*k₁)+А₂(α₂±δ*k₂)+…+ А₁(α₁±δ*k₁)=В.

Из последнего соотношения по определению решения системы уравнений следует, что векторы α΄=(α₁+δ*k₁, α₂+δ*k₂,…, α₁+δ*k₁) и α΄΄=(α₁-δ*k₁, α₂-δ*k₂,…, α₁-δ*k₁) являются решениями СЛУ(2). Если же число δ выбрать так, что оно удовлетворяет арифметической лемме, то координаты векторов α΄и α΄΄ будут удовлетворять условию (3), а сами векторы будут являться допустимыми решениями задачи(1)-(3) и при этом, хотя бы у одного из этих векторов число ненулевых координат будет меньше, чем 1. Пусть это будет вектор α΄. Тогда этот вектор не будет являться оптимальным решением, так как ранее был выбран оптимальный вектор α° с наименьшим числом 1 ненулевых координат. Поэтому для векторов α΄ и α΄΄ должна выполняться система неравенств:

{f(α°)<f(α΄),

{f(α°)≤f(α΄΄),

Которая равносильна системе:

{∑ γј*αј+γ₀<∑ γј(αј+δ*kј)+γ₀,

{∑ γј*αј+γ₀≤∑ γј(αј-δ*kј)+γ₀.

Откуда получаем противоречивую систему:

{0<δ∑γј*kј,

{0≤-δ∑γј*kј.

Таким образом, предположение о том, что вектор α° не является опорным решением неверно. Следовательно, вектор α° является опорным решением задачи.