- •Билет № 1
- •1. Теоремы о взаимосвязи опорных решений задачи линейного программирования и угловых точек области допустимых решений.
- •Билет № 3
- •1. Необходимые и достаточные условия разрешимости транспортной задачи.
- •Билет № 4
- •1. Свойство системы ограничений транспортной задачи. Взаимосвязь линейной зависимости векторов-условий и циклов.
- •Билет № 5
- •1. Методы построения опорного решения транспортной задачи. Метод вычёркивания.
- •Билет № 6
- •Билет № 8
- •2. Теорема об единичном базисе.
- •Билет № 9
- •2. Теорема о двух линейно независимых системах векторов.
- •Билет № 10
- •2. Теорема о двух системах векторов, которым соответствуют равносильные системы уравнений.
- •Билет № 12
- •2. Общая теория систем уравнений. Теорема Кронекера-Капелли.
- •Билет № 13
- •2. Фундаментальная система решений однородной системы уравнений, теорема о её существовании.
- •Билет № 14
- •2. Необходимые и достаточные условия существования обратной матрицы.
- •Билет № 15
- •1. Построение начального опорного решения и переход от одного опорного решения к другому в симплексном методе (вывод формул).
- •Билет № 16
- •Теорема об улучшении опорного решения, её следствия.
- •Билет № 17
- •1. Теоремы о взаимосвязи опорных решений и угловых точек области допустимых решений.
- •Билет № 18
- •1. Метод искусственного базиса решения задач линейного программирования, его обоснование. Леммы и теорема об оптимальности опорного решения.
- •Билет № 20
- •Обоснование метод искусственного базиса решения задач линейного программирования. Теорема об отсутствии оптимального решения ввиду неограниченности целевой функции.
- •Билет № 21
- •1. Первая теорема двойственности, её доказательство.
- •Билет № 22
- •Вторая теорема двойственности, её доказательство.
- •Билет № 29
- •1. Теорема о виде области допустимых решений задачи линейного программирования.
- •Билет № 30
- •1. Теорема об улучшении опорного решения, её следствия.
Билет № 9
2. Теорема о двух линейно независимых системах векторов.
Теорема 3.3. Если система линейно независимых векторов, содержащая n векторов, разлагается по другой линейно независимой системе векторов, содержащей m векторов, то n m.
Д о к а з а т е л ь с т в о. Пусть имеется две линейно независимые системы векторов и , и векторы первой системы разлагаются по векторам второй системы. Предположим, что и придем к противоречию. Пусть коэффициентами разложения каждого из векторов по векторам являются коэффициенты (j=1,2,…, m). Запишем разложения векторов по векторам , затем умножим эти векторы и их разложения на некоторые коэффициенты соответственно и сложим, получим линейную комбинацию
. Имеем
………………..…………………
.
Покажем, что существует ненулевой набор чисел , при котором линейная комбинация равняется нулевому вектору . Для этого все выражения в скобках перед векторами должны одновременно равняться нулю, т. е. система
должна иметь ненулевое решение. По теореме 2.6 о решении однородной системы уравнений эта система имеет ненулевое решение , так как по предположению число неизвестных n (число векторов первой системы) больше числа уравнений m (числа векторов второй системы). Это противоречит тому, что система векторов является линейно независимой. Предположение неверно. Следовательно, n m.
Теорема 3.4. О числе векторов, входящих в базис. Любой базис системы векторов содержит одно и то же число векторов.
Число векторов, входящих в базис системы векторов, называется рангом системы векторов и обозначается буквой r.
Д о к а з а т е л ь с т в о. Пусть система векторов имеет два базиса. Базис содержит m векторов, а базис содержит k векторов. Каждый из базисов представляет линейно независимую систему векторов и векторы каждого базиса разлагаются по векторам другого базиса. Поэтому по предыдущей теореме 3.3
m ≤ k и k ≤ m.
Следовательно, m = k.
Билет № 10
2. Теорема о двух системах векторов, которым соответствуют равносильные системы уравнений.
Теорема 3.5. О двух системах векторов, которым соответствуют равносильные системы уравнений.
Если двум системам векторов
, (1)
(2)
соответствуют равносильные системы уравнений
, (3)
, (4)
и векторы образуют базис системы (2), то соответствующие векторы образуют базис системы (1) и при этом разложения соответствующих векторов систем по своим базисам совпадают, т. е. если
( j = r + 1, 2, …, n), то
( j = r + 1, 2, …, n).
Д о к а з а т е л ь с т в о. Пусть ( ) базис системы векторов (2). Покажем, что соответствующие этим векторам векторы системы (1) также образуют базис. Докажем от противного.
Предположим, что линейно зависимы, т. е. существует ненулевой набор чисел , такой, что . Дополним левую часть этого равенства слагаемыми , которые равны нулю. Равенство не нарушится.
.
Это равенство можно рассматривать как условие, подтверждающее то, что система уравнений (3) имеет ненулевое решение ( , 0, …, 0).
По условию теоремы системы уравнений (3) и (4) равносильные, т. е. это решение является также решением системы (4). Тогда
или при ненулевом наборе чисел , что возможно только при линейной зависимости векторов . Это противоречит условию теоремы. Следовательно, векторы линейно независимые.
Пусть далее известно разложение
(j = 1, 2, …, n).
Покажем, что с такими же коэффициентами разлагается соответствующий вектор по векторам . Ввиду равносильности систем уравнений (3) и (4) из последнего равенства имеем
.
Отсюда получаем (j = 1, 2, …, n). Следовательно, векторы образуют базис первой системы векторов (1); причем коэффициенты разложений соответствующих векторов в системах (1) и (2) по своим базисам совпадают.