Билет №29

Основные свойства взаимно двойственных задач ЛП

1⁰. если векторы а=(k₁,…k_n) и ß=(l₁,…,l_m) являются допустимыми решениями взаимно двойственных задач ЛП (1)-(4) и (1’)-(4’) соответственно, то f(a)≤φ(ß).

Доказательство.

Значение целевой функции ЗЛП (1)-(4) на допустимом векторе а=( k₁,…k_n) с учетом доказанной леммы можно записать в виде f(a)=y₁k₁+…+y_Tk_n+y₀≤(∑_i=1^ma_i11_j)k₁+…+(∑^m_i=1a_in1_j)k_n+y₀=(a₁₁1₁+…+a_m11_m)k1+…+(a_1n1₁+…+a_mn1_m)k_n+y₀= (a₁₁k₁+…+a_1nk_n)1₁+…+(a_m1k₁+…+a_m1k_n)1_m+y₀=(∑_j=1ⁿa_1jk_j)1₁+…+(∑_j=1ⁿa_mjk_j)1_m+y₀=b₁1₁+…+b_m1_m+y₀≤φ(ß).

Следовательно, f(a)≤φ(ß).

2⁰. Если векторы а⁰ и ß⁰ являются допустимыми решениями взаимно двойственных задач ЛП (1)-(4) и (1’)-(4’) соответственно, и f(a⁰)=φ(ß⁰), то векторы а⁰ и ß⁰ – оптимальные решения этих задач соответственно.

Доказательство.

Для произвольного допустимого решения а задачи ЛП (1)-(4) по свойству 1⁰ выполняется неравенство f(a)≤φ(ß⁰).так как по условию f(a⁰)= φ(ß⁰), то f(a)≤f(а⁰) и по определению вектор а⁰ является оптимальным решением ЗЛП (1)-(4).

Оптимальность вектора ß⁰ доказывается аналогично.

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

Доказательство.

Доказательство проведем от противного. Пусть целевая функция - φ(ß) задачи ЛП (1’)-(4’) неограниченна снизу на множестве допустимых решений, а задача ЛП (1)-(4) имеет допустимое решение –а. тогда по свойству 1⁰ для любого допустимого решения-ß задачи ЛП (1’)-(4’) должно выполняться неравенство f(a)≤φ(ß). Это неравенство противоречит неограниченности снизу целевой функции φ(ß) на множестве допустимых решений этой задачи. Следовательно, задача ЛП (1)-(4) не имеет ни одного допустимого решения, т.е. система условий этой задачи несовместна.

Билет №30

Теоремы двойственности

Теорема 1.

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

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

Доказательство теоремы следует из сформулированных выше свойств.

Теорема 2.

Пусть векторы a⁰=(x₁⁰,…,x_n⁰) и ß⁰=(y₁⁰,…,y_m⁰) являются допустимыми решениями взаимно двойственных задач ЛП (1)-(4) и (1’)-(4’) соответственно. Для того, чтобы векторы a⁰ и ß⁰ были оптимальными решениями этих задач необходимо и достаточно выполнение следующих равенств:

{ x_j⁰(∑^m_i=1a_ijy_j⁰-y_j)=0, j=1,2,…,n;

{y_i⁰(∑ⁿ_j=1a_ijx⁰_j-b_i)=0, i=1,2,…,m.

Доказательство.

Необходимость. Пусть векторы a⁰ и ß⁰ оптимальные решения взаимно двойственных задач ЛП (1)-(4) и (1’)-(4’) соответственно. Тогда по свойству 2⁰ выполняется равенство f(a⁰)=φ(ß⁰), которое можно записать в виде: y₁x₁⁰+…+y_nx_n⁰+y₀=b₁y₁⁰+…+b_my_m⁰+y_0.

Это равенство с учётом соотношения (∑a_ijy_i⁰)x_j⁰≥y_jx_j⁰,j=1,2,…,n,равносильно неравенству:

(∑a_i1y_i⁰)x₁⁰+…+(∑a_iTy_i⁰)x_T⁰≥b₁y₁⁰+…+b_my_m⁰ (a₁₁x₁⁰+…+a_1nx_n⁰-b₁)y₁⁰+…+(a_m1x_n⁰+…+a_mnx_n⁰-b_m)y_m≥0 (∑a_1jx_j⁰-b₁)y₁⁰+…+(∑a_mjx_j⁰-b_m)y_m⁰≥0.

В то же время, из условий задач (1)-(4) и (1’)-(4’) следует, что каждое слагаемое в последнем неравенстве неположительное. Поэтому и все выражение в левой части этого неравенства должны быть не положительны. Следовательно в последнем отношении должно быть равенство, т.е. (∑a_1jx_j⁰-b₁)y₁⁰+…+(∑a_mjx_j⁰-b_m)y_m⁰=0.

Однако сумма положительных слагаемых может равняться нулю только тогда, когда каждое слагаемое равно нулю.

Таким образом, необходимость для выполнения второго соотношения в утверждении теоремы доказана.

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

Достаточность. Пусть выполняются равенства:

{ x_j⁰(∑^m_i=1a_ijy_j⁰-y_j)=0, j=1,2,…,n;

{y_i⁰(∑ⁿ_j=1a_ijx⁰_j-b_i)=0, i=1,2,…,m.

Тогда f(a⁰)=y₁x₁⁰+…+y_nx_n⁰+y₀=x_j⁰(∑a_ijy_i⁰)+…+x_j⁰(∑a_ijy_i⁰)+y⁰=(a₁₁y₁⁰+…+a_m1y_m⁰)x₁⁰+…+(a_1ny₁⁰+…+a_mny_m⁰)x_n⁰+y₀=

=b₁y₁⁰+…+b_my_m⁰+y₀=φ(ß⁰)

Т.е. f(a⁰)= φ(ß⁰). Откуда с учётом свойства 2⁰ следует, что векторы a⁰ и ß⁰ оптимальные решения взаимно двойственных задач ЛП (1)-(4) и (1’)-(4’) соответственно.