Линейное программирование

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

Рассмотрим задачу линейного программирования с ограничениями-равенствами — так называемую основную задачу линейного программирования (ОЗ) [7].

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

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

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

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

(2.12)

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

где

(2.13)

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

(2.14)

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

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

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

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

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

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

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

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

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

Матрицей системы линейных уравнений (2.12) является таблица (2.13).

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

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

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

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

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

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

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

ее столбцов равно n, то

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

Рассмотрим, прежде всего, случай, когда r = n, т. е. когда число линейно независимых уравнений, входящих в систему (2.12), равно числу переменных n. Если отбросить избыточные уравнения, являющиеся линейными комбинациями других, то система уравнений-ограничений ОЗ принимает вид (т.е. здесь m = n):

(2.15)

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

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

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

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

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

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

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

(2.16)

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

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

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

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

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

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

Итак, если число уравнений 03 r = m меньше, чем число переменных n, то система линейных уравнений имеет бесчисленное множество решений, т. е. совокупностей значений удовлетворяющих уравнениям-ограничениям (2.12). Если среди этих решений нет ни одного, для которого все неотрицательны, то это значит, что 03 не имеет допустимого решения.

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

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

Что еще почитать

Комментарии к новости