Линейное математическое программирование, страница 4

Для выполнения плана выпуска по номенклатуре необходимо чтобы выполнялись следующие равенства

(1.14)

Кроме этого быть x_ij ≥ 0 (1.15)

Затраты на производство всей продукции выразятся функцией

(1.16)

Нужно найти такое решение х (х₁₁, x₁₂ , …, x_mk), удовлетворяющее системам (1.13), (1.14) и условию (1.15), при котором функция цели (1.16) принимает минимальное значение.

2. Cистемаm линейных уравнений с n переменными

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

(2.1)

n > m

Если все уравнения независимы, то ранг матрицы, составленной из коэффициентов при неизвестных, равен числу уравнений r = m. Тогда при условии совместности системы (когда ранг матрицы системы равен рангу расширенной матрицы) поскольку n > m = r, система имеет бесконечное множество решений.

При поиске этих решений определяют группы m переменных, которые называют основными или базисными. Число групп базисных переменных определяется из условия неравенства нулю определителя, составленного из коэффициентов при этих неизвестных. Число групп базисных переменных не превышает числа сочетаний из n элементов по m, т.е. .

Остальные m-n переменных называются неосновными или свободными.

Решение, полученное при условии, что все свободные переменные равны нулю, называются базисным решением. Базисное решение может быть допустимым или недопустимым. Допустимым базисным решением (его ещё называют опорным планом) есть решение, в котором значения всех переменных неотрицательны. Недопустимым является базисное решение, в котором значение хотя бы одной переменной отрицательное.