Прямая задача. max L (1) = ∑ c( j)* x (j) , при ограничениях

n

max L (1) = ∑ c(j)* x (j), при ограничениях

j= 1

x (j) ≥ 0 (мир решений – реален).

n

∑ a(i,j) * x (i) ≤ b (i) (i= 1,2, …, m)

j= 1

2) двойственная задача имеет целевую функцию

n

min L (2) = ∑ b(j)* y(j) при условиях:

j= 1

m

∑ a(i,j) * y (i) ≥ c (i) (i= 1,2, …, m), при ограничениях

j= 1

y (j) ≥ 0 - цена единицы ресурса (мир цен – реален);

для выпуска единицы j – го вида продукции необходимо по нормам a (i, j) единиц i- го ресурса

Теоремы линейного программирования:

Линейная система, в которой число неизвестных равно числу уравнений, имеет одно решение

Если число неизвестных меньше числа уравнений, то решения нет и система несовместна

1)Если целевая функция принимает максимальное значение в некоторой точке допустимого множества R -1, то она принимает это значение в крайней точке реального пространства R -1.

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

2)Если задача линейного планирования содержит n переменных и m ограничений

(n ≥ m) в форме неравенств, не считая ограничений неотрицательности

x (j) ≥ 0, то в оптимальное решение входит не более чем m ненулевых компонент вектора x.

При векторной форме записи ограничения задачи ЛП записывают:

А (1) * Х (1) +... + А(n) Х(n) ≤ b.

Поскольку А(1),..., А(n) - m – мерные вектора (n ≥ m), то среди них всегда найдётся m линейно независимых векторов, образующих базис m – мерного пространства и содержащих конус, образованный векторами А(1),..., А(n).