Общая задача линейного программирования

В общем случае задача линейного программирования сводится к отысканию такого решения х = (x₁; х₂; ...; х_n) системы m линейных уравнений с n переменными

при котором целевая функция F = + с₂х₂ + ... + с_nх_n принимает оптимальное (максимальное или минимальное) значение.

Решение х = (х₁; х₂; ...; х_n) при котором функция F обращается в оптимум, называется оптимальным решением.

В задачах линейного программирования коэффициенты - заданные постоянные величины, а число уравнений меньше числа переменных, т.е. m<n.

Все правые части системы неотрицательны, т.е. b_j (i = 1, 2, ..., m). Если в некоторых уравнениях системы это условие нарушено, то можно умножить обе части таких уравнений на -1.

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

Задачу можно записать в более короткой форме; найти решение

х = (х₁, х₂, ..., х_n) системы ограничений

(i = 1, 2, ..., m) приводящее к оптимуму линейную функцию , при

условии, что хj ≥ 0 (j = 1, 2, . . ., n) .

Для записи системы часто употребляется векторно-матричная форма:

AX = В матрица А - матрица условий задачи.

В = (b₁, b₂, ..., b_m) - вектор ограничений.

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

(i = 1, m) или

или смешанные ограничения (≥; ≤).

Но любую системуограничений можно привести к системе уравнений. Для этого достаточно к левой части каждого неравенства прибавить (отнять) какое-либо неотрицательное число - добавочную переменную, с тем, чтобы каждое неравенство обратилось в уравнение.

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

Система m-линейных уравнений с n-переменными может быть совместной и несовместной; уравнения системы - зависимы и независимы,

Несовместность системы означает, что ее уравнения противоречивы. Система не имеет решения => не имеет решения задача линейного программирования.

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

Допустимым базисным решением является решение, содержащее m неотрицательных основных (базисных) переменных и (n-m) неосновных (свободных) переменных. Неосновные переменные в базисном решении равны нулю.

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

Т.к. компоненты оптимального решения задачи линейного программированияне могут быть отрицательными, то поиски этого решения нужно ограничить только допустимыми решениями системы ограничений.