Основная задача линейного программирования, ее свойства, подход к решению

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

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

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

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

Если одно уравнение может быть получено путем указанных преобразований из другого уравнения, то одно из них (любое) линейно зависит от другого. Каждое из уравнений:

4х₁+3х₂=30

и

12х₁+9х₂=90

линейно зависимы – второе уравнение получается путем умножения первого на 3.

В системе:

3х₁+4х₂=20

2х₁+х₂=15

5х₁+5х₂=35

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

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

Напомним важные для линейного программирования характеристики возможных результатов решений систем линейных уравнений.

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

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

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

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

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

х₁, х₂,…, х_n.

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

a₁₁x₁+a₁₂x₂+…+a_1nx_n = b₁;

a₂₁x₁+a₂₂x₂+…+a_2nx_n = b₂;

………………………………

a_m1x₁+a_m2x₂+…+a_mnx_n = b_m.

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

Z = c₁x₁+c₂x₂+…+c_nx_n.

Условимся называть допустимым решением основной задачи линейного программирования любую совокупность переменных х₁≥0, х₂≥0,…, х_n≥0, удовлетворяющую системе ограничений.

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

Основная задача линейного программирования необязательно должна иметь решение. Может оказаться, что ограничений противоречат друг другу; может оказаться, что они имеют решение, но не в области неотрицательных значений х₁, х₂,…, х_n. Тогда задача не имеет допустимых решений. Наконец, может оказаться, что допустимые решения основной задачи линейного программирования существуют, но среди них нет оптимального: функция Z в области допустимых решений неограниченна. С примерами таких особенностей основной задачи линейного программирования мы познакомимся в дальнейшем.

Результат решения основной задачи линейного программирования существенно зависит от числа ограничений и переменных. В случае, когда m=n, (т.е. когда число линейно независимых уравнений, входящих в систему ограничений, равно числу переменных n). Задача имеет единственное решение. Если при этом хотя бы одно из значений х₁, х₂,…, х_n отрицательно, то полученное решение недопустимо и, значит, задача не имеет решения.

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

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

Задана система двух уравнений с четырьмя неизвестными:

2х₁- х₂+х₃ – х₄=1

-х₁+х₂ – 2х₃+х₄=2

Очевидно, что здесь m=2 (уравнения линейно независимы), n=4. Выберем в качестве свободных переменных, например, х₃ и х₄, а в качестве базисных – х₁ и х₂. выразим базисные переменные через свободные:

2х₁ – х₂=1 – х₃+х₄,

-х₁+х₂=2+2х₃ – х₄

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

х₁=3+х₃

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

х₂=5+3х₃ – х₄.

Таким образом, базисные переменные х₁, х₂ выражены через свободные х₃, х₄. Свободным переменным х₃, х₄ можно придавать любые значения. При этом всегда можно получать совокупность значений х₁, х₂, х₃, х₄, удовлетворяющую заданной системе уравнений. Например, полагая х₃=х₄=0, получим х₁=3, х₂=5 - эти значения удовлетворяют системе. Полагая х₃=1, х₄=2, получим х₁=4, х₂=6. Эти значения также удовлетворяют исходным уравнениям.

Вообще, если число линейно независимых уравнений, входящих в систему ограничений равно m, то всегда можно выразить какие-то m базисных переменных через n-m остальных (свободных). Затем придавая свободным переменным любые значения можно получить бесчисленное множество решений системы. Итак, если число уравнений m меньше, чем число переменных n, то система имеет бесчисленное множество решений, т.е. совокупностей значений х₁, х₂,…, х_n, удовлетворяющих уравнениям-ограничениям. Если среди этих решений нет ни одного, для которого все х₁, х₂,…, х_n неотрицательны, то это значит, что задача не имеет ни одного допустимого решения.

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

Z = c₁x₁+c₂x₂+…+c_nx_n

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