Свойство системы линейных уравнений, содержащей тривиальное уравнение.

Билет №1

Правило умножения матриц

Пусть даны 2 матрицы A(m×n) и B(n×l), причем число столбцов матрицы A равно числу строк матрицы B. Тогда матрица C(m×l) с элементами , (т.е. i-тая строка матрицы A, умноженная скалярно на j-й столбец матрицы B, дает c_ij-й элемент матрицы C, стоящий в i-й строке и j-м столбце).

, .

Билет №2

Свойство системы линейных уравнений, содержащей тривиальное уравнение.

Тривиальное уравнение – уравнение, в котором коэффициенты при всех неизвестных и свободных членах равны нулю.

Теорема: Система линейных уравнений, содержащая тривиальное уравнение, равносильна той же системе без тривиального уравнения.

Доказательство: Рассмотрим СЛУ (1) и ту же СЛУ (2), но без тривиального уравнения.

(1) ……………………………………………………………… (2)

Пусть вектор является решением системы (1), тогда этот вектор является и решением системы (2).

Обратно, пусть вектор является решением системы (2). Т.к. n-мерный вектор L является и решением тривиального уравнения, то он является решением системы (1).

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

 

 

Билет №3

Свойство свободных неизвестных в разрешенной СЛУ

СЛУ называется разрешенной, если каждое уравнение системы содержит хотя бы одно разрешенное неизвестное.

Теорема: Если в разрешенной СЛУ (4) придать свободным неизвестным произвольные значения , т. е. , то найдется единственное решение этой системы в виде n-мерного вектора К, у которого значения координат, соответствующих свободным неизвестным, равны соответственно .

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

(4)

Подставим в систему (4). Тогда разрешенные неизвестные примут значения такие, что:

(5)

Т. к. вектор обращает каждое уравнение системы (4) в точное числовое равенство, то он является решением этой системы. Таким образом, доказано существование решения системы (4).

Докажем единственность такого решения. Пусть вектор с теми же значениями свободных неизвестных является также решением системы (4). Тогда подставим его в систему (4), получим:

(6)

Сопоставляя (5) и (6), видим, что . Таким образом, доказано, что существует единственное решение системы (4) с заданными значениями свободных неизвестных.

Замечания:

1) Т. к. значения свободных неизвестных можно задать бесконечно большим числом способов, то система (4) является неопределенной.

2) Разрешенная СЛУ всегда совместна. При этом она определена, если m=n, т. е. число уравнений равно числу неизвестных, и не определена, если число уравнений меньше числа неизвестных, т. е. m<n

 

Билет №4

Решение системы однородных уравнений

Линейное уравнение называется однородным, если его свободный член равен нулю, и неоднородным в противном случае. Система, состоящая из однородных уравнений, называется однородной и имеет общий вид:

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

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

Следствие 1: Однородная система уравнений, в которой число уравнений меньше числа неизвестных, всегда имеет ненулевое решение.

Доказательство: Если у системы уравнений , то ранг системы не превышает числа уравнений , т.е. . Таким образом, выполняется условие и, значит, система имеет ненулевое решение.

Следствие 2: Однородная система уравнений с неизвестными имеет ненулевое решение тогда и только тогда, когда ее определитель равен нулю.

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

 

Билет №5

Примеры линейно зависимых и линейно независимых систем векторов

1) Система m -мерных векторов называется линейно зависимой, если система линейных уравнений (1) имеет ненулевые решения. Если же система (1) не имеет ненулевых решений, то данная система векторов является линейно независимой.

2) Система m -мерных векторов называется линейно зависимой, если существует такой ненулевой вектор , что выполняется линейное соотношение (2) . Если же из всякого соотношения вида (2) следует, что , то система векторов называется линейно независимой.

Пример:

Билет №6

Билет №7

Билет №8

Билет №9

Билет №10

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

 

 

 

Билет №11

Билет №12

Билет №13

Билет №14

Билет №15

Билет №16

Билет №17

Билет №18

Билет №19

Билет №20

Лемма о целевой функции

Пусть δ₁,…,δј,…,δn оценки векторов условий задачи (1)-(3), приведенных к базису опорного решения α. Если вектор β=(l₁,…,lј,…,ln) является допустимым решением данной задачи, то f(β)=f(α)-∑ δј lј.

Пусть векторы А₁, А₂, …, Аr являются базисом опорного решения α=(α₁,α₂,…,αr,0,0,…,0). Тогда симплекс таблица системы векторов условий задачи(1)-(3), приведенных к данному базису будет иметь вид:

Где по правилу построения строки (δ₁,…,δј,…,δn), оценки примут следующие значения: δ₁=δ₂=…=δr=0 и

Так как для базисных векторов А₁, А₂, …, Аr оценки равны нулю, то есть δ₁=δ₂=…=δr=0, то значение целевой функции на векторе β можно записать в виде:

f(β)= γ₀+γ₁α₁+…+γr αr-δ r+₁ l r+₁- δ r+₂ l r+₂-…-δn ln=f(α)-∑ δј lј.

Билет №21

Билет №22

Билет №23

Билет №24

Билет №25

Билет №26

Билет №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)-(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

Билет №31

Билет №1

Правило умножения матриц

Пусть даны 2 матрицы A(m×n) и B(n×l), причем число столбцов матрицы A равно числу строк матрицы B. Тогда матрица C(m×l) с элементами , (т.е. i-тая строка матрицы A, умноженная скалярно на j-й столбец матрицы B, дает c_ij-й элемент матрицы C, стоящий в i-й строке и j-м столбце).

, .

Билет №2

Свойство системы линейных уравнений, содержащей тривиальное уравнение.

Тривиальное уравнение – уравнение, в котором коэффициенты при всех неизвестных и свободных членах равны нулю.

Теорема: Система линейных уравнений, содержащая тривиальное уравнение, равносильна той же системе без тривиального уравнения.

Доказательство: Рассмотрим СЛУ (1) и ту же СЛУ (2), но без тривиального уравнения.

(1) ……………………………………………………………… (2)

Пусть вектор является решением системы (1), тогда этот вектор является и решением системы (2).

Обратно, пусть вектор является решением системы (2). Т.к. n-мерный вектор L является и решением тривиального уравнения, то он является решением системы (1).

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

 

 

Билет №3