11. Формы записи злп

Общей задачей линейного программирования (ОЗЛП) называют задачу

(2.10)

при ограничениях:

(2.11) (2.12) (2.13) (2.14)

x_j — произвольные (2.15)

где c_j , A_ij , b_i — заданные действительные числа; (2.10) — целевая функция; (2.11)—(2.15) — ограничения; x = ( x₁ , ..., x_n ) — план задачи.

Задачу линейного программирования можно представить в 3-х различных видах: развернутом, матричном и векторном.

Приведенная выше ОЗЛП записана в развернутой или индексной форме. В этой же форме задачу можно представить и несколько иначе:

(2.16)

при линейных ограничениях:

(2.17) (2.18)

x_j — произвольные

здесь c_j , A_ij , b_i  — заданные действительные числа; (2.16)  целевая функция; (2.17) — ограничения; (2.18) — условие неотрицательности части переменных; x = ( x₁, ... , x_n ) — план задачи.

Рассмотрим теперь матричную форму записи ЗЛП. Введем следующие обозначения:

; , , ,

где C — матрица-строка; A — матрица системы уравнений; X — матрица-столбец переменных; A₀ — матрица-столбец свободных членов.

Тогда наша задача примет вид:

(2.19)

, X  0 ,(2.20)

или

mаx (min) Z = C X , A X {, =,  }A₀ , X  0 .(2.21)

Полезной является также векторная форма ЗЛП. Для столбцов матрицы A введем обозначения:

, , ..., , ..., .

Тогда задача (2.10)—(2.15) в векторной форме записи примет вид:

mаx (min) Z = CX ;(2.22)

A₁x₁ + ... + A_jx_j + A_nx_n = A₀ , X  0 ,(2.23)

где CX  скалярное произведение векторов C = ( c₁; ...;c_n ) и X = (x₁ , ... , x_n).

Каноническая форма представления задачи линейного программирования.

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

Канонической формой записи ЗЛП называют задачу

(2.24) (2.25)

(2.26)

12. Линейное векторное пространство. Линейная зависимость векторов. Ранг.

Опр 1: Совокупность всевозможных упорядоченных систем из n действительных чисел после введения в нее операций сложения и умножения на действительное число называется n-мерным векторным пространством.

Опр 2: Вектор В называется линейной комбинацией векторов A₁, A₂, ... , A_n , если существуют такие числа k₁, k₂, ... , k_n, при которых выполняется соотношение B = k₁ A₁ + k₂ A₂ + ... + k_n A_n.

Опр 3: Система векторов A₁, A₂, ... , A_r (r > 1) называется линейно зависимой, если хотя бы один из векторов системы является линейной комбинацией остальных, и линейно независимой - в противном случае.

Опр 4: Рассматривая линейно зависимую систему векторов A₁, A₂, ... , A_n , возьмем такую линейно независимую подсистему векторов A₁, A₂, ... , A_r  (r n), к которой невозможно присоединить ни одного вектора системы, не нарушив линейной независимости. Такая подсистема называется максимальной линейно независимой подсистемой данной системы векторов. Число векторов, входящих в любую максимальную линейно независимую подсистему векторов, называется рангом системы, а сами вектора составляют базис системы.

13.Понятие базиса системы. Базисное и опорное решение системы.

Базисом  n-мерного векторного пространства называется любая совокупность n линейно независимых векторов этого же пространства.

В двумерном пространстве в качестве базиса могут быть взяты два любых неколлинеарных вектора, в трехмерном пространстве - три некомпланарных вектора, в пространстве измерений n > 3 - система из n линейно независимых векторов.

В полученной системе единичные вектора называются базисными, а вектора — свободными.

Базисными решениями называются решения системы, получаемые при приравнивании свободных неизвестных нулю.

Базисное решение называется невырожденным, если все базисные переменные полученного решения ненулевые, в противном случае базисное решение называется вырожденным.

Опорными решениями системы называются те базисные решения, которые имеют все неотрицательные значения неизвестных.