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

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

,

………………………….

,                                                                      (1)

,

,

…………………………..,

где .

и линейная функция

,                                               (2)

где .

необходимо найти такое решение системы  где

                                            (3)

при котором линейная функция f (1) принимает оптимальное значение.

Система (1) называется системой ограничений, а функция f – линейной функцией.

Оптимальным решением задачи линейного программирования называется решение  системы ограничений (1), удовлетворяющее условию (3), при котором линейная функция (2) принимает оптимальное значение.

Основные определения

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

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

Базисным решением системы m линейных уравнений с n переменными называется решение, в котором все  неосновных переменных равны нулю.

Угловая точка – точка множества, которая не является внутренней ни для какого отрезка, целиком принадлежащего данному множеству.

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

Оптимум линейной функции задачи линейного программирования следует искать среди конечного числа ее допустимых базисных решений.