- •33.Правило умножения матриц
- •34.Свойство системы линейных уравнений, содержащих тривиальное уравнение
- •35.Свойства свободных неизвестных в разрешенной системе уравнений.
- •36. Элементарные преобразования системы линейных уравнений
- •37. Существование ненулевого решения у системы линейных однородных уравнений.
- •38.Примеры линейно зависимых и линейно независимых систем векторов.
- •39. Свойства системы векторов
- •40. Единственность разложения вектора системы векторов по базису этой системы.
- •41. Максимально линейно независимая часть системы векторов и базис этой системы
- •42 Простейшие св-ва задач линейного программирования.
- •43 Примеры задач линейного программирования: выпуск продукции, рацион, транспортная, портфель ценных бумаг.
- •44. Существование опорного решения кзлп
- •45. Существование базиса опорного решения кзлп
- •46. Число ненулевых координат у любого опорного решения кзлп задачи.
- •47. Единственность базиса у невырожденного опорного решения кзлп.
- •48. Базис системы векторов условий кзлп и опорные решения этой задачи.
- •49. Число опорных решений кзлп.
- •50. Условие соответствия базисв системы векторов кзлп базису некоторого опорного решения этой задачи.
- •51.Теорема об оптимальных решениях кзлп
- •52) Свойства симплекс таблицы: структура вектора ограничений, оценки базисных векторов и значение целевой функции.
- •53.Лемма о целевой функции.
- •54.Достаточное условие оптимальности опорного решения канонической задачи линейного программирования на минимум
- •55. Условия неограниченности целевой функции канонической задачи линейного программирования на минимум
- •56. Решение канонической задачи линейного программирования на минимум симплекс методом, критерии выбора вектора вводимого в базис и выводимого из базиса
- •57 Конечность симплекс метода при решении кзлп на минимум
- •58 Условие разрешимости кзлп на минимум
- •59 Основные свойства искусственной кзлп
- •60.Теорема о методе искусственного базиса.
- •61. Свойства взаимно двойственных задач лп
- •63. Экономическая интерпретация взаимно двойственных задач.
- •64. Достаточное условие оптимальности опорного решения транспортной задачи линейного программирования и решение этой задачи методом потенциалов.
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), а
Основные свойства:
Вектор β=(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).
Задача (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) является оптимальным решением искусственной задачи. Тогда:
если an+1=an+2=…=an+m=0,то вектор а=(а1, а2,…,an) является опорным решением исходной канонической задачи линейного программирования;
если среди чисел 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. Получено противоречие. Таким образом, предположение о существовании допустимого решения исходной задачи является неверным. Следовательно, система ограничений исходной задачи является несовместной.
