2. ОСНОВНАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Выше мы рассмотрели различные практические задачи, сводящиеся к схеме линейного программирования. В одних из этих задач линейные ограничения имели вид неравенства, в других — равенств, в третьих — тех и других.

Здесь мы рассмотрим задачу линейного программирования с ограничениями-равенствами — так называемую основную задачу линейного программирования (0ЗЛП).

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

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

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

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

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

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

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

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

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

Основная задача линейного программирования необязательно должна иметь решение.

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

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

Рассмотрим, прежде всего, вопрос о существовании допустимых решений ОЗЛП.

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

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

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

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

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

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

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

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

Пример 1. Дана система трех уравнений с четырьмя неизвестными:

Определить, является ли эта система совместной?

Решение. Матрица системы:

Расширенная матрица:

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

Вычисляя этот определитель по известному правилу, получим:

Этот определитель не равен нулю, значит, ранг матрицы системы равен 3. Очевидно, ранг расширенной матрицы тоже равен 3, так как из элементов расширенной матрицы можно составить тот же определитель. Из равенства рангов матриц следует, что система уравнений совместна.

Пример 2. Исследовать на совместность систему двух уравнений с тремя неизвестными :

Решение. Расширенная матрица системы:

(левая ее часть — матрица системы).

Найдем ранг матрицы системы, составляя все возможные определители второго порядка:

Итак, все возможные определители второго порядка, составленные из элементов матрицы системы равны нулю; значит, ранг этой матрицы системы

Найдем ранг расширенной матрицы. Определитель

Отсюда ранг расширенной матрицы он не равен рангу матрицы системы: Грфг, следовательно, система уравнений несовместна.

Пример 3. Исследовать на совместность систему трех уравнений с четырьмя неизвестными:

Решение Расширенная матрица системы (вместе с матрицей системы):

Найдем ранг матрицы системы. Возьмем определитель третьего порядка, составленный из ее элементов, например:

Известно, что если какая-либо строка определителя является линейной комбинацией двух других его строк, то определитель равен нулю. В нашем случае третья строка является линейной Комбинацией двух первых: чтобы ее получить, достаточно сложить первую строку с удвоенной второй Поэтому .

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

Так как имеется неравный нулю определитель второго порядка, например,

то ранг матрицы системы равен

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

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

Итак, если система уравнений-ограничений ОЗЛП совместна, то матрица системы и ее расширенная матрица имеют один и тот же ранг.

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

Очевидно, ранг системы не может быть больше числа уравнений :

Очевидно, также, что ранг системы не может быть больше общего числа переменных :

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

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

Рассмотрим, прежде всего, случай, когда , т. е. когда число линейно независимых уравнений, входящих в систему (2.1), равно числу переменных п. Отбросим «лишние» уравнения, являющиеся линейными комбинациями других. Система уравнений-ограничений ОЗЛП принимает вид:

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

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

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

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

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

Очевидно, этот тривиальный случай не может нас интересовать.

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

Пример 4. Рассматривается система двух уравнений с четырьмя неизвестными:

Ранг этой системы равен (уравнения линейно независимы). Выберем в качестве свободных переменных, например, 3 и 4, а в качестве базисных — и 2. Выразим базисные переменные через свободные. Имеем из уравнений (2.5):

Складывая эти уравнения, получим

Умножая второе уравнение на 2 и складывая с первым, получим

Таким образом, базисные переменные выражены через свободные 3, 4 Свободным переменным 3, 4 можно придавать любые значения; при этом мы будем всегда получать совокупность значений , удовлетворяющую системе уравнений (2.5) Например, полагая получим эти значения удовлетворяют системе (2.5). Полагая получим эти значения также удовлетворяют уравнениям (2.5).

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

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

Итак, если число уравнений ОЗЛП меньше, чем число переменных , то система линейных уравнений имеет бесчисленное множество решений, т. е. совокупностей значений удовлетворяющих уравнениям-ограничениям (2/1). Если среди этих решений нет ни одного, для которого все неотрицательны, то это значит, что ОЗЛП не имеет допустимого решения.

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

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

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

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