Основные свойства решения задач ЛП

Рассмотрим различные формы представления задачи линейного программирования:

1) Векторная форма записи:

Z=CX®max

A₁X₁+…+A_nX_n B

X 0

где C=(C₁…C_n) – вектор коэффициента целевой функции (строка коэффициента);

X=(Х₁…….Х_n) – вектор-строка переменных задач;

CX – скалярное произведение векторов, равное сумме произведений их соответствующих компонентов,т.е. СХ = С₁Х₁ +….+ С_nХ_n;

A₁…A_n – векторы условий, но векторы-столбцы при соответствующих переменных;

B – вектор - столбец ограничения или вектор правых частей.

2) Матричная форма

Z=CX max

AX B

X 0

A – матрица условий, составленная из столбцов-векторов A₁…A_n,

X2

3)Геометрическая интерпретация

Z=C₁X₁+…..+C_nX_n max

a₁x₁+….+a_n x_n b_i

……………..

X1

A_m x₁+……+a_mnx_n b_m

x_1….. x_n 0

Геометрическую интерпретацию даем только в случае двух переменных. Тогда выражение Z=C₁X₁+C₂X₂ в зависимости от значения Z представляет собой семейство параллельных прямых, которые в точке (0,0) Z=0, и с увеличением Z прямые «приближаются» к границам области допустимых решений, которые определяются заданными неравенствами. Максимальное значение целевой функции достигается в одной (или нескольких) граничных точках области допустимых решений.

Необходимые сведения берутся из линейной алгебры.

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

Векторы равны, когда они имеют одинаковую размерность и соответствующие координаты совпадают.

Вектор B , равный α₁A₁+…+α_nA_n, является линейной комбинацией векторов A₁…A_n, если существуют такие числа a₁…a_n, одновременно не равные нулю, при которых это равенство выполняется.

Система векторов A₁…A_n называется линейно зависимой, если существуют такие числа a_1,…,a_m 0(одновременно не равные нулю) и такие что выполняется равенство: (*) 0=a₁A₁+…a_mA_m , где 0 – нуль-вектор (все его компоненты равны нулю).

Через Rⁿ обозначим множество всех векторов размерности n c операциями сложения векторов и умножения их на число. В дальнейшем рассмотрим только векторы одинаковой размерности.

Если равенство (*) выполняется только в случае, когда все a_1,…a_n равны нулю, то система векторов A₁…A_n линейно независима.

Содержательно: система векторов линейно независима, если никакой ее вектор нельзя представить в виде линейной комбинации остальных векторов системы.

Базис – максимально линейно-независимая система векторов в пространстве. Любой базис содержит в пространстве Rⁿ n-векторов. Единичный базис – система, состоящая из n различных единичных векторов E₁……E_n (i-й единичный вектор, у которого на i месте 1, а остальные компоненты равны 0).

Элементы выпуклого анализа.

Линейная комбинация векторов (*) R=a₁A₁+…+a_nA_n называется выпуклой, если выполняется условие:

a_i=1 и все a_i неотрицательны.

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

Определение: множество называется выпуклым, если вместе с каждой парой своих элементов, оно содержит все их выпуклые комбинации.

выпуклое невыпуклое

множество множество

Система линейных неравенств в ограничениях задачи ЛП стандартной формы определяет некоторое выпуклое возможно неограниченное множество, которое называют многогранником решений.

Ограниченный и Неограниченный

многогранники решения.

Определение: угловая точка многогранника решений – это такая точка многогранника, которая не является выпуклой линейной комбинацией никаких других точек многогранника (не лежит на отрезке, соединяющим две другие точки многогранника).

Если система ограничений содержит конечное число неравенств, то число угловых точек будет конечно и не превосходит С -числа сочетаний.

Теорема № 1.