Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
LINAL.docx
Скачиваний:
4
Добавлен:
01.07.2025
Размер:
757 Кб
Скачать
☆

59 Основные свойства искусственной кзлп

КЗЛП (1) F(X)= 𝛾j xj + 𝛾0

Aj Xj=B

(3) Xj≥0, j=1,2,…n,

Искусственная КЗЛП (4)φ(x)=

(5)

(6)xj≥0, j=1,2,…,n, n+1, n+2, …,n+m,

Где Ej – единичный вектор (j=1,2,…,m), а

Основные свойства:

  1. Вектор β=(0,…,0, b1,b2, …bm)является опорным решение задачи (4)- (6)

Заметим, что по определению КЗЛП все координаты вектора ограничений B=(b1, b2, …,bm)должны быть неотрицательными, т.е. bi≥0, i=1,2,…,m.

Так как единичные вектора E1, E2,…,Em образуют базис системы векторов условий A1, A2, …, An, E1, E2,…,Em задачи (4)- (6), то вектор ограничений В можно представить в виде линейной комбинации векторов E1, E2,…,Em с неотрицательными коэффициентами bi≥0, i=1,2,…,m, т.е. в виде В=b1E1+b2E2+…+bmEm. Следовательно, по свойству базиса опрного решения вектор β=(0,…,0, b1,b2, …bm) является опорным решением задачи (4)-(6).

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

Задача (4)-(6) имеет допустимые решения, одним из которых является, например вектор β=(0,…,0, b1,b2, …bm), так как опорное решение всегда является допустимым. Из (6) следует, что все искусственные переменные неотрицательны, т.е. i=1,2,…,m. Поэтому целевая функция (4) φ(x)= ограничена снизу на множестве допустимых решений, т.е. φ(x)≥0. Следовательно, по теореме о разрешимости КЗЛП задача (4)-(6) имеет оптимальное решение.

Замечание. Так как у задачи (4)-(6) всегда известно начальное опорное решение, то ее можно решить симплекс методом, который через конечное число шагов приведет к оптимальному решению этой задачи.

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

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

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

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

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

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

A1a1+A2a2+…+Anan+E1a n+1+E2an+2+…Eman+m=B,

Так как an+1=an+2=…=an+m=0, то последнее равенство можно записать в виде A1a1+A2a2+…+Anan=B.

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

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

Второе утверждение теоремы будем доказывать от противного, предположив, что существует число аn+i >o, i=1,2,…,m, но при этом исходная задача имеет допустимое решение а=(k1,k2,…kn), которое удовлетворяет системе и kj≥, j=1,2,…,n. Тогда по определению допустимого решения выполняется соотношение: A1k1+A2k2+…+Ankn=B, которое можно переписать в виде A1k1+A2k2+…+Ankn+A n+10+An+20+…An+m0=B.

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

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

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]