Искусственная задача линейного программирования и ее основные свойства

(1) (X)=x_n+1+x_n+2+…+x_n+m(min)

(2) ₁x_n+1+E₂x_n+2+…+E_mx_n+m=B

(3) x_j≥0, j=1,2,…,n+1,n+2,…,n+m.

 

1. Вектор β=(0,…,0,b₁,b₂,…,b_m) является опорным решением задачи (1)-(3)

Заметим что по определению канонической задачи линейного программирования все координаты вектора ограничений B=(b₁,b₂,…,b_m) должны быть неотрицательными.

Так как единичные векторы E₁,E₂,…,E_m образуют базис системы векторов условий A₁,A₂,…,A_n, E₁,E₂,…,E_m задачи (1)-(3), то вектор ограничений В можно представить в виде линейной комбинации векторов E₁,E₂,…,E_m с неотрицательными коэффициентами b_i≥0, i=1,2,…,m, т.е. в виде B= b₁ E₁+b₂ E₂ +… + b_m E_m. Следовательно, по свойству базиса опорного решения вектор β=(0,…,0,b₁,b₂,…,b_m) является опорным решением задачи (1)-(3).

2. Задача (1)-(3) всегда имеет оптимальное решение.

Задача (1)-(3) имеет допустимые решения, одним из которых является например вектор β=(0,…,0,b₁,b₂,…,b_m), так как опорное решение всегда является допустимым. Из (3) следует. Что все искусственные переменные неотрицательны, т.е. x_n+i≥0, i=1,2,…,m. поэтому целевая функция (1) ограничена снизу на множестве допустимых решений. Следовательно по теореме о разрешимости канонической задачи линейного программирования задача (1)-(3) имеет оптимальное решение.

 

 

Билет №27

Теорема (о методе искусственного базиса)

Пусть вектор ß=(а₁, а₂,…, а_n, a_n+1, a_n+2,…, a_n+m) является оптимальным решением искусственной задачи. Тогда:

1. если a_n+1=a_n+2=…=a_n+m=0,то вектор а=(а₁, а₂,…,a_n) является опорным решением исходной канонической задачи линейного программирования;

2. если среди чисел a_n+1, a_n+2,…, a_n+m, хотя бы одно отличается от нуля, т.е. найдётся a_n+1>0, i=1,2,…,m, то задача не имеет ни одного допустимого решения, т.е. система ограничений канонической задачи линейного программирования является несовместной.

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

Докажем первое утверждение. По условию вектор ß =(а₁, а₂,…, а_n, a_n+1, a_n+2,…, a_n+m) является оптимальным решением искусственной задачи. Тогда вектор ß является опорным решением этой задачи, а, следовательно, допустимым решением и, по определению, является решением системы линейных уравнений, т.е. выполняется соотношение:

A₁a₁+A₂a₂+…+A_na_n+E₁a _n+1+E₂a_n+2+…E_ma_n+m=B,

Так как a_n+1=a_n+2=…=a_n+m=0, то последнее равенство можно записать в виде A₁a₁+A₂a₂+…+A_na_n=B.

Откуда по определению следует, что вектор а=(а₁, а₂,…,a_n) является допустимым решением исходной задачи.

Так как вектор ß=(а₁, а₂,…, а_n,0, 0,…, 0) является опорным решением искусственной задачи, то ненулевым координатам этого вектора соответствуют линейно независимые векторов условий этой задачи. Тогда некоторые из указанных линейно независимых векторов соответствуют ненулевым координатам вектора а=(а₁, а₂,…,a_n). Следовательно, вектор а является опорным решением исходной задачи.

Второе утверждение теоремы будем доказывать от противного, предположив, что существует число а_n+i >o, i=1,2,…,m, но при этом исходная задача имеет допустимое решение а=(k₁,k₂,…k_n), которое удовлетворяет системе и k_j≥, j=1,2,…,n. Тогда по определению допустимого решения выполняется соотношение: A₁k₁+A₂k₂+…+A_nk_n=B, которое можно переписать в виде A₁k₁+A₂k₂+…+A_nk_n+A _n+10+A_n+20+…A_n+m0=B.

Откуда следует, что вектор ß’=(k₁, k₂,…, k_n,0, 0,…, 0) является допустимым решением искусственной задачи.

Так как по условию вектор ß=(а₁, а₂,…, а_n, a_n+1, a_n+2,…, a_n+m) является оптимальным решением искусственной задачи, то φ(а=(k₁,k₂,…k_n),) ≤ φ(ß’), что равносильно неравенству: a _n+1+a_n+2+…a_n+m≤0+0+…0. Однако, по предположению, существует a _n+1>0, i=1,2,…,m, а следовательно, a _n+1+a_n+2+…a_n+m>0. Получено противоречие. Таким образом, предположение о существовании допустимого решения исходной задачи является неверным. Следовательно, система ограничений исходной задачи является несовместной.

 

Билет №28

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

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) не имеет ни одного допустимого решения, т.е. система условий этой задачи несовместна.

 

 

Билет №29

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

Теорема 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’) соответственно.

 

Билет №30