Основные теоремы линейного программирования

Теорема 1. Множество всех допустимых решений, системы ограничений задачи линейного программирования, является выпуклым.

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

Пример. Найти максимум функции

F=X₁-X₂

при ограничениях:

3X₁+2X₂<=14

X₁-4X₂<=0

3X₁-X₂>=0

-X₁+X₂<=2

X₁,X₂>=0

Найдём оптимальное решение поставленной задачи геометрическим способом. Для этого в системе координат Х₁,Х₂ построим множество допустимых решений, используя систему неравенств. Убедимся в справедливости теоремы 1. На рисунке 1 множество допустимых решений пред­ставляет собой замкнутый выпуклый четырехугольник с вершинами О D, В,С. Функция "F" может принимать различные значения из области допустимых значений, т.е. Х₁-Х₂=а

Меняя величину "а", получим семейство параллельных прямых. Теорема 2. утверждает, что максимум или минимум функции F достигается в одной из вершин области допустимых решений. Убедимся в этом, последовательно подставляя координаты вершин в выражение целевой функции F. Максимум будет в точке С с координатами X₁=4, Х₂=1 и значение его равно 3 (4-1=3).

Рис. 2.1.

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

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

ЗХ₁+2Х₂+Х₃=14

X₁-4X₂+X₄=0

-3X₁+X₂+X₅=0

-X₁+X₂+X₆=2

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

1. Положим Х₁=Х₂=0. Подставляя эти значения в систему уравнений, получим базисное решение (0,0,14,0,0,2).Оно допустимо, т.к. Х₁, Х₂, Х₃, Х₄, Х₅, Х₆ больше нуля и вырождено, т.к. Х₄=Х₅=0.

2. Найдем теперь второе базисное решение, полагая X₁=X₆=0. Подставим эти значения в систему уравнений и, решая эту систему относительно оставшихся неизвестных переменных, получим второе базисное решение (0,2,10,8,-2,0).Оно не допустимо, т.к. Х₅=-2 отрицательно.

3. Третье базисное решение получим аналогичным способом, полагая Х₃=Х₄=0. Базисное решение (4,1,0,0,11,5) допустимо и соответствует решению, полученному геометрическим способом (вершина С).

Таким же образом можно найти все базисные решения, выбрать среди них допустимые, подставляя значения X₁ и Х₂ в целевую функцию, получить значения функции и среди этих значений выбрать максимальное. Очевидно, что для данной задачи число базисных решений будет равно числу сочетаний из шести по четыре, а именно: С⁴₆=15. В общем случае количество базисных решений равно

C^mn=n!/m!(n-m)! (2.3)

Замечание. Если в угловой точке соответствуют два, три и более базисных решений, то все они будут вырожденными.

Следствие из теоремы 1 и теоремы 2 оптимальное решение задачи линейного программирования, заданной ограничениями - уравнениями совпадает с допустимым базисным решением системы ограничений.

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

Что Вы должны знать:

(вопросы для самоконтроля)

1. Из чего состоит задача линейного программирования?

2. Какие параметры являются заданными в задаче линейного программирования, и какие надо найти?

3. Какова формулировка первой теоремы линейного программирования?

4. Какое решение является допустимым решением задачи линейного программирования?

5. Что позволяет определить вторая теорема линейного программирования?

6. Какие задачи линейного программирования решаются геометрическим способом?

7. В каком случае оптимальное решение не является единственным?

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

Решение задачи ЛП графическим методом:

Пример 1, (случаи единственного оптимального решения). Используя графический метод, найти решение следующей задачи ЛП:

max f(x) = x₁- x₂

при ограничениях

(1) 3х₁+2х₂ ≤14,

(2) x₁ – 4x₂ ≤ 0,

(3) 3x₁ – x₂ ≥ 0,

(4) –x₁ + x₂ ≤ 2

(5) x₁ ≥ 0,

(6) x₂ ≥ 0.

Решение. На плоскости R² построим допустимое множество, описываемое шестью неравенствами. Это будет пересечение шести полуплоскостей (каждое неравенство-ограничение задает на R² полуплоскость). Например, первую полуплоскость 3x₁+2х₂≤14 строим так. Проводим прямую 3x₁+2х₂=14, которая является границей этой полуплоскости. Чтобы определить, какую из полуплоскостей, лежащих по обе стороны от прямой 3x₁+2х₂=14, описывает неравенство 3x₁+2х₂≤14, достаточно поставить в это неравенство координаты начала координат, т.е. (0,0). Если неравенство выполняется, то берем ту полуплоскость, которая содержит начало координат, если не выполняется, то берем полуплоскость, не содержащую начала координат. В нашем случае 3*0 + 2*0≤14. На рис. 1 в кружочках написаны номера линий (границ полуплоскостей), а полуплоскости обозначены стрелками. В результате пересечения построенных шести полуплоскостей получаем многогранник ОАВС. который и является допус­тимым множеством нашей задачи. Можно проверить, что любая точка этого многогранника удовлетворяет всем шести неравенствам, а для любой точки вне этого многогранника хотя бы одно неравенствоиз шести будет нарушено.

Таким образом, геометрически наша задача свелась к тому, чтобы в пределах многогранника ОАВС найти точку х* = (x₁*,x₂*). в которой целевая функций f(x) = x₁-x₂ получит максимальное значение.

Благодаря свойству 3 (см. выше) мы заранее знаем, что точкой максимума нашей целевой функции является одна или некоторые из вершин О,А,В или С.

Для того, чтобы определить эту вершину, проведем какую-либо линию уровня целевой функции, т.е. проведем прямую f(x)=с₁, где с-const. Для простоты возьмем с=0, тогда линия уровня есть x₁-x₂=0. Увеличивая правую часть этого уравнения (например, x₁-x₂=1, x₁-x₂=3 и т.д.), мы обнаружим параллельное смещение линии уровня вниз, причем, чем больше правая часть, тем дальше. Если же уменьшим правую часть (например, x₁-x₂=-1, x₁-x₂=-2 и т.д.), то наблюдаем смещение вверх.

Отсюда понятно, что, смещая линию уровня в сторону возрастания целевой функции, мы найдем ту вершину многогранника ОАВС, которая соответствует точке максимума. Как видно из рисунка 1, это есть точка С.

Чтобы сразу определить направление возрастания функции t, вычисляют ее градиент Ñf. Для линейной функции градиент всегда равен вектору, составленному из коэффициентов этой функции.

Для нашей целевой функции f(x)= x₁-x₂ градиент Ñf = (1,-1) (см. рис, 1). Известно, что градиент перпендикулярен линии уровня и показывает направление возрастания функции, а антиградиент, т.е. вектор -Ñf показывает направление убывания функции.

Итак, "двигая" линию уровня x₁-x₂=0 в сторону вектора Ñf, находим точку максимума С.

Координаты точки С найдем решая совместно уравнения линий 1 и 2, пересекающихся в точке С:

3x1+2x2=14

x1-4x2=0

Ответ: х*=(4,1) - точка максимума,

f(x*) = 3 - максимальное значение целевой функции.

Отсюда получаем алгоритм графического метода:

1) построить на плоскости допустимое множество,

2) построить линию уровня целевой функции,

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

4) найти и вычислить координаты точки максимума или минимум,

5) вычислить значение целевой функции в найденной точке.

Пример 2. (Случай бесконечного множества оптимальных решений):

min f(x)=--x1-2x2

при ограничениях

x₁+2x₂≤7

2x₁+x₂≤8

x₂≤3

x₁,x₂≥0

Как видно из рис. 2, наиболее удаленным в сторону антиградиента -Ñf=(1,2) местом касания линии уровня f(x)=с с допустимым множеством OABCD является грань ВС (т.е. выпуклая оболочка вершин B=(l, 3) и С=(3,2)). Поэтому любая точка грани ВС является точкой минимума целевой функции.

Ответ: х*=a(1,3)+(1-a)(3,2)=(3-2a,2+a) для любого aÎ[0, 1] - точка минимума,

f(x*)=-7 - минимальное значение целевой функции.

Пример 3. (Случай отсутствия оптимального решения ввиду неограниченности целевой функции на допустимом множестве):

min f(x) == -x₁-2x₂

при ограничениях.

x₁+x₂³1

2x₁-x₂³-1

x₁-2x₂≤0

x₁,x₂≥0

Допустимое множество этой задачи представляет собой неограниченный многогранник (рис. 3).

При параллельном переносе линии уровня f(x)=с вдоль антиградиента -Ñf=(1,2) она всегда пересекает допустимое множество, т.е. нет "наиболее удаленной точки касания", а целевая функция неограниченно убывает.

Ответ: Точки минимума нет; целевая функция неограниченна снизу.

Пример 4. (Случай отсутствия оптимального решения ввиду пустоты допустимого множества):

max f(x)=x₁+x₂

при ограничениях

-x₁+x₂≤-1

-x₁-x₂≤-1

x₁,x₂≥0

Как показано на рис, 4, полуплоскости, образованные первыми двумя неравенствами, не пересекаются (система не совместна); Поэтому нет ни одной допустимой точки.

Графический метод применяется и в том случае, когда в задаче ЛП число линейно независимых ограничений-неравенств (каноническая форма) ровно на два меньше числа переменных. Об этом подробно можно почитать, например, в [8, стр. 49].