Различные формы задачи ЛП

Смысл названия «вектор роста» становится ясным, если заметить, что вектор является градиентом функции F, то есть вектором, составленным из частных производных функции F. Действительно, если мы продифференцируем линейную функцию

по переменной , считая остальные переменные постоянными, то конечно получим :

(3)

Как известно из анализа, градиент функции указывает направление максимального роста функции в данной точке. Из (3) видно, что в линейном случае это направление не зависит от точки и совпадает с направлением вектора .

Определение 13. Линией (на плоскости) или поверхностью (в пространстве) уровня функции называется множество точек , удовлетворяющих равенству:

,

где с – некоторая произвольная константа.

Помимо общей задачи ЛП, выделяют однородную, каноническую и симплексную формы задачи ЛП.

Определение 1. Задача ЛП называется однородной, если все ограничения имеют вид неравенства.

Частными случаями однородной задачи являются задача о ресурсах (или производственная):

(1)

и задача об издержках:

(2)

В первом случае требуется найти максимум функции F («прибыли») при ограниченных «ресурсах» , во втором – минимум издержек F при заданных «нормах потребления» , Более подробно, эти типы задачи ЛП будут рассмотрены в следующих параграфах.

Определение 2. Задача ЛП называется канонической, если все нетривиальные ограничения имеют вид равенства и на все переменные наложены тривиальные ограничения.

Поскольку, переменную можно заменить на новую переменную , удовлетворяющую условию то, без ограничения общности, можно считать, что все переменные канонической задачи ЛП неотрицательны.

Таким образом, каноническая задача ЛП может быть записана в виде:

(3)

или в координатной форме:

(4)

Определение 3. Каноническая задача ЛП называется симплексной, если:

1) система линейных ограничений имеет разрешенный вид, то есть матрица системы содержит единичную матрицу ;

2) столбец свободных членов неотрицателен:

3) целевая функция F зависит только от свободных переменных.

Разъясним смысл некоторых терминов, встречающихся в этом определении. Во-первых, напомним, что матрица размера т´т называется единичной (и обозначается Е=Е ), если:

1)

2)

Например, единичными называются матрицы:

Во-вторых, говорят, что система линейных уравнений (4) имеет разрешенный вид, если ее матрица содержит, возможно после перестановки столбцов, единичную подматрицу Е размера т т. Столбцы единичной подматрицы имеют вид:

и называются базисными.

Определение 4. Переменные, соответствующие базисным столбцам, называются также базисными, а остальные переменные – свободными.

Если исходная матрица системы (4) содержит т линейно независимых строк (или столбцов), то есть ее ранг равен т, то, как известно, с помощью метода Гаусса система может быть приведена к равносильной системе, имеющей разрешенный вид. При этом в качестве базисных могут быть выбраны любые т линейно независимых столбцов исходной системы.

Напомним, что метод Гаусса состоит в приведении матрицы системы к ступенчатому виду с помощью элементарных преобразований, к которым относятся:

1) перестановка строк;

2) умножение строки на число ;

3) замена одной из строк ее суммой с другой строкой, умноженой на некоторое произвольное число .

Как правило, базисными будем считать последние т столбцов матрицы системы.

Замечание: Далее слова «матрица системы А содержит единичную подматрицу» будут означать, что матрица системы А после перестановки столбцов содержит единичную подматрицу Е размера т т, где т – число строк матрицы А.

Определение 5. Решение системы (4) называется базисным, если все свободные переменные равны нулю.

Определение 6. Допустимое базисное решение называется опорным решением.

Напомним, что вектор называется допустимым решением, если он удовлетворяет как нетривиальным ограничениям, в данном случае системе уравнений (4), так и тривиальным:

Таким образом решение системы (4) оказывается допустимым, если все его компоненты неотрицательны.

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

Дата добавления: 2014-12-26