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

Итак, будем называть основной задачей линейного программирования (ОЗЛП) следующую задачу: определить такие значения переменных , которые удовлетворяют системе соотношений

(1)

ограничениям неотрицательности

(2)

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

(3)

здесь ¾ заданные вещественные числа.

В дальнейшем будем считать, что m < n. Действительно, если m > n, то система ограничений (1) либо несовместна, либо содержит уравнения, которые можно из нее исключить, так как они являются следствиями других уравнений системы. Если же m=n, то либо имеет место один из случаев, возможных и для m > n, либо система (1) имеет единственное решение и задача линейного программирования становится тривиальной.

ОЗЛП удобно записывать в матрично-векторной форме. Пусть Тогда ОЗЛП запишется так: найти n –мерный вектор x, который удовлетворяет условиям и при этом доставляет минимум функции .

Ограничения (1) можно также записать в векторной форме где ¾ j –ый столбец матрицы A,

Дата добавления: 2015-07-14