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

Рассмотрим задачу линейного программирования с ограничениями – равенствами – так называемую - основную задачу линейного программирования(ОЗЛП), в дальнейшем покажем, как от задачи с ограничениями- неравенствами можно перейти к ОЗЛП, и обратно.

Основная задача линейного программирования ставится следующим образом:

имеется ряд переменных

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

(2.1)

и, кроме того, обращали бы в максимум линейную функцию

. (2.2)

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

. (2.3)

Условимся называть допустимым решением ОЗЛП любую совокупность переменных

х₁≥0, х₂≥0, х₃ 0, …, х_n≥0,

удовлетворяющую уравнениям (2.1)

Оптимальным решением будем называть то из допустимых решений, при котором линейная функция (2.2) обращается в максимум.

Основная задача линейного программирования необязательно должна иметь решение. Может оказаться, что уравнения (2.1) несовместны, т.е. решений нет.

Может быть случай, когда решения ОЗЛП существуют, но среди них нет оптимального: функция L в области допустимых решений неограничена сверху. Рассмотрим, прежде всего, вопрос о существовании допустимых решений ОЗЛП. При решении этого вопроса мы можем исключить из рассмотрения линейную функцию L, которую требуется максимизировать - наличие допустимых решений определяется только уравнениями ограничений.

Итак, пусть имеется система уравнений – ограничений. Существуют ли неотрицательные значения удовлетворяющие этой системе? Этот вопрос рассматривается в специальном разделе математики – линейной алгебре.

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

Матрицей системы линейных уравнений

Называется таблица, составленная из коэффициентов при

Расширенной матрицей системы линейных уравнений называется та же матрица, дополненная столбцом свободных членов:

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

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

Итак, если система уравнений – ограничений ОЗЛП совместна, то матрица системы и ее расширенная матрица имеют один и тот же ранг. Этот общий ранг r называется рангом системы; он представляет собой не что иное, как число линейно независимых уравнений среди наложенных ограничений.

Ранг системы r не может быть больше общего числа уравнений m:

.

Ранг системы r не может быть больше общего числа переменных n:

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

Рассмотрим, прежде всего, случай когда r=n, т.е. когда число линейно независимых уравнений, входящих в систему, равно числу переменных n.Система уравнений-ограничений принимает вид:

(2.4)

Так как r=n, то определитель, составленный из коэффициентов,

не равен нулю. Из алгебры известно, что в этом случае система (2.4) имеет единственное решение. Чтобы найти величину , достаточно в определителе заменить i-ый столбец - столбцом свободных членов и разделить на .

Итак, при r=n система уравнений-ограничений ОЗЛП имеет единственное решение:

Если в этом решении хотя бы одна из величин отрицательна, это значит, что полученное решение недопустимо и, значит, ОЗЛП не имеет решения.

Если все величины неотрицательны, то найденное решение является допустимым. Оно же, очевидно, является и оптимальным (потому что других нет).

В дальнейшем мы будем рассматривать случай, когда r<n, т.е., когда число независимых уравнений, которым должны удовлетворять переменные , меньше числа самих переменных. Тогда, если система совместна, у нее существует бесчисленное множество решений. При этом n-r переменным мы можем придавать произвольные значения (так называемые свободные переменные), а остальные r переменных выразятся через них (эти r переменных мы будем называть, базисными).

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

В дальнейшем, для простоты, записывая уравнения ОЗЛП, мы будем считать их линейно независимыми; при этом ранг системы r будет равен числу уравнений m.

Итак, если число уравнений ОЗЛП r=m меньше, чем число переменных n, то система линейных уравнений имеет бесчисленное множество решений. Если среди этих решений нет ни одного, для которого все неотрицательны, то это значит, что ОЗЛП не имеет допустимого решения.

Если же существуют какие-то решения системы (2.1), для которых все неотрицательны (короче, «неотрицательные решения»), то каждое из них допустимо. Возникает задача – найти среди допустимых решений – оптимальное, то есть такое решение

,

для которого линейная функция

обращается в максимум.

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