Билет №8

Единственность разложения векторов по базису этой системы

Теорема: Коэффициенты k_1j, …, k_rj в разложении (1) вектора по векторам базиса определены однозначно.

A_j = B₁k_1j + … + B_rk_rj (1)

∆ Предположим, что существует еще одно разложение вектора A_j по векторам базиса, а именно A_j = B₁k_1j + … + B_rk_rj (2). Вычтя соотношение (2) из соотношения (1), получим Ɵ = B₁ (k_1j – k_1j) + … + + B_r (k_rj – k_rj). Т. к. векторы B₁, …, B_r линейно независимы, то из последнего соотношения следует, что k_1j – k_1j = 0, …, k_rj – k_rj = 0. Это равносильно тому, что k_1j = k_1j , …, k_rj = k_rj , т. е. разложение по векторам базиса единственно. ∎

Билет №9

Максимально линейно независимая часть системы векторов и базис этой системы

Линейно независимая часть B₁, …, B_m данной системы векторов A₁, …, A_n называется максимально линейно независимой частью, если после добавления к этой части любого вектора данной системы, не входящего в B₁, …, B_m, получается линейно зависимая часть данной системы векторов.

Теорема: Любая линейно независимая часть C₁, …, C_k данной системы векторов A₁, …, A_n может быть дополнена до базиса этой системы.

∆ Если C₁, …, C_k не является максимально линейно независимой частью системы векторов A₁, …, A_n , то найдется такой вектор C_k+1 ∈ (A₁, …, A_n)/(C₁, …, C_k) , что система векторов C₁, …, C_k, C_k+1 будет линейно независимой частью системы A₁, …, A_n.

Если и система C₁, …, C_k, C_k+1 не является максимально линейно независимой частью системы A₁, …, A_n, то найдется такой вектор C_k+2 ∈ (A₁, …, A_n)/( C₁, …, C_k, C_k+1), что система векторов C₁, …, C_k, C_k+1, C_k+2 будет линейно независимой частью системы A₁, …, A_n и т. д.

Через таких шагов получим максимально линейно независимую часть C₁, …, C_k+l системы векторов A₁, …, A_n. При чем полученная система C₁, …, C_k+l удовлетворяет условиям определения базиса, т. к. она линейно независима. К тому же, если A_j ∉ (C₁, …, C_k+ℓ), то из определения максимальной линейной независимости следует, что система векторов C₁, …, C_k+ℓ, A_j линейно зависима. Тогда по 4-му свойству найдется такой вектор К≠Ө, что будет выполняться соотношение C₁k₁ + … + C_k+ℓk_k+ℓ = A_j, т.е. любой вектор системы A₁, …, A_n линейно выражается через вектора C₁, …, C_k+ℓ. Следовательно, вектора C₁, …, C_k+ℓ образуют базис системы A₁, …, A_n. ∎

Билет №10

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

1. Оптимальное решение задачи линейного программирования не изменится, если целевую функцию помножить на любое положительное число, либо прибавить к целевой функции любое число.

2. Рассмотрим общую задачу линейного программирования:

Умножив целевую функцию (1) на (-1), рассмотрим новую задачу, а именно:

Вектор ⁰ является оптимальным решением задачи (1) – (4) на максимум тогда и только тогда, когда ⁰ является оптимальным решением задачи (1ʼ) – (4ʼ) на минимум.

∆ Необходимость. Пусть W есть множество допустимых решений задачи (1) – (4) и задачи (1ʼ) – (4ʼ), а вектор ⁰ является оптимальным решением задачи (1) – (4) на максимум. Тогда, по определению глобального максимума, выполняется неравенство f( ⁰)≥ f( ) для любого вектора . Умножив последнее неравенство на (-1), получим новое неравенство f( ⁰)≤ f( ) и с учетом обозначения целевой функции задачи (1ʼ) – (4ʼ) имеем f₁( ⁰)≤ f₁( ) для любого вектора . Откуда, по определению глобального минимума функции f₁( ), вектор ⁰ является оптимальным решением задачи (1ʼ) – (4ʼ) на минимум. Таким образом, необходимость доказана. Для доказательства достаточности следует провести рассуждения в обратной последовательности. ∎

Замечание: В дальнейшем будем рассматривать решение задач линейного программирования только на минимум, так как задача на максимум может быть сведена к соответствующей задаче на минимум.