Билет №26

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

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

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

Билет №27

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

(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) имеет оптимальное решение.

Билет №28

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

Пусть вектор ß=(а₁, а₂,… , а_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. Получено противоречие. Таким образом, предположение о существовании допустимого решения исходной задачи является неверным. Следовательно, система ограничений исходной задачи является несовместной.