1. Геометрический метод решения задач ЛП

Этот метод часто используется при решении задач, в которых только две неизвестных величины. Разберем его на следующих примерах:

Пример 1.1. (Задача о производстве красок).

Небольшая фабрика изготовляет два вида красок: INT - для внутренних работ и EXT - для наружных работ. В производстве красок используются два исходных продукта А и В. Из-за малой площади склада максимально возможные суточные запасы этих продуктов равны 6 т. и 8 т. соответственно. На производство 1 тонны краски INT расходуется 1 тонна продукта А и 2 тонны продукта В, а на изготовление 1 тонны краски EXT идет 2 тонны продукта А и 1 тонна продукта В. Фабрика продает краску по цене 3 тыс. долл. за тонну краски INT и 2 тыс. долл. за тонну краски EXT. Исходные данные удобно свести в таблицу:

Изучение рынка сбыта показало, что суточный спрос на краску EXT никогда не превышает спрос на краску INT, более чем на 1 тонну. Какое количество краски каждого вида должна производить фабрика в сутки, чтобы доход от реализации продукции был максимален?

Построим математическую модель задачи. Для этого надо определить переменные задачи, целевую функцию и ограничения, которым удовлетворяют переменные. Обозначим через x₁ - планируемый суточный объем производства краски INT, а через x₂ - суточный объем производства краски EXT. Целевая функция f(x) будет выражать суточный доход от продажи краски, равный 3x₁ + 2x₂ (тыс. долл.). Этот доход подлежит максимизации

f(x)= 3x₁ + 2x₂ max.

Построим ограничения задачи, связанные с ограниченными запасами продуктов А и В. На производство краски INT в количестве x₁ (т) будет использовано 1x₁ (т) продукта А, а на производство краски EXT в объеме x₂ (т) будет затрачено 2x₂ (т) продукта А. Поскольку суточный запас продукта А равен 6 т., то расход продукта А на изготовление красок двух видов не может превышать в сутки этой величины: 1x₁+ 2x₂ 6. Аналогично получим ограничение, связанное с запасом продукта В: 2x₁+1x₂ 8. Ограничение по соотношению спроса на краски можно описать неравенством: x₂ - x₁ 1. Учитывая естественные условия неотрицательности объемов выпуска продукции, окончательно получим следующую задачу линейного программирования

f(x) = 3 x₁ + 2 x₂ max (1.1)

1 x₁ + 2 x₂ 6, (1.2)

2 x₁ + 1 x₂ 8, (1.3)

- x₁ + x₂ 1, (1.4)

x₁ 0, x₂ 0. (1.5)

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

p₁: 1x₁+2x₂=6

Построим эту прямую на плоскости с координатными осями x₁ и x₂. Для проведения прямой достаточно знать две ее точки. Проще всего найти точки пересечения прямой с осями координат. Полагая x₁ = 0, из уравнения прямой получим x₂ = 3, а при x₂ = 0 найдем x₁ = 6. Таким образом прямая p₁ пройдет через точки (0,3) и (6,0). Чтобы определить, по какую сторону от прямой расположена искомая полуплоскость, достаточно подставить в неравенство (1.2) координаты любой точки плоскости. Если прямая не проходит через начало координат, то удобнее всего взять точку (0, 0). Очевидно, что в этой точке неравенство (1.2) строго выполняется (1* 0 + 2* 0 < 6), значит полуплоскость, определяемая этим неравенством, лежит ниже прямой p₁, включая в себя начало координат. Искомую полуплоскость отметим штриховкой (рис.1.1).

Аналогично построим полуплоскость, задаваемую неравенством (1.3). Для этого нанесем на координатную плоскость граничную прямую

p₂: 2x₁+x₂=8,

найдя ее точки пересечения с осями координат: (0,8) и (4,0).

Подставляя координаты точки (0,0) в неравенство (2.3), видим, что начало координат лежит в искомой полуплоскости (2* 0 + 1* 0 < 8), значит все точки, удовлетворяющие неравенству (2.3), расположены левее прямой p₂. Отметим эту область штриховкой (рис.1.1).

Точки, задаваемые ограничением (4), находятся ниже прямой

p₃: -x₁+x₂=1,

проходящей через точки (0, 1) и (-1, 0).

Наконец, условия неотрицательности: x₁ 0, x₂ 0 задают все точки первой четверти, что также отметим штриховкой.

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

Рис. 1.1

Для графического представления целевой функции введем понятие линии уровня (изолинии функции).

Определение. Линией уровня (изолинией) функции f(x) называется множество точек x = (x_1, x₂), в которых она принимает одно и то же постоянное значение f(x) = h, где h - некоторое число. Для линейной функции двух переменных f(x) = c₁ x₁ + c₂ x₂ линия уровня, соответствующая числу h, будет представлять прямую с уравнением

c₁ x₁ + c₂ x₂ = h (1.6)

При изменении числа h будем получать семейство линий уровня (параллельных прямых) с одним и тем же направляющим вектором c = =(c₁, c₂₎, перпендикулярным всем прямым. Известно, что вектор c = (c₁, c₂) для линейной функции f(x) = c₁ x₁ +c₂ x₂ указывает направление ее возрастания. Геометрически это означает, что при параллельном перемещении прямой (1.6) в направлении целевого вектора c значение целевой функции возрастает.

Построим линии уровня целевой функции f(x) = 3x₁ + 2 x₂ в нашей задаче. Их уравнения будут иметь вид 3x₁ + 2 x₂ = h. Они задают семейство параллельных прямых, зависящих от параметра h. Все прямые перпендикулярны целевому вектору c = (3, 2), составленному из коэффициентов целевой функции, поэтому для построения семейства линий уровня целевой функции достаточно построить ее целевой вектор, и провести несколько прямых, перпендикулярных этому вектору. Линии уровня будем проводить на множестве планов X, помня при этом, что при параллельном перемещении прямых в направлении целевого вектора c = (3, 2₎ значение функции f(x)= 3x₁ + 2x₂ будет возрастать. Поскольку в задаче оптимальный план должен доставлять целевой функции максимально возможное значение, то для решения задачи графически надо среди всех точек x = (x_1, x₂) множества планов X найти такую точку x* = (x₁*_, x₂*), через которую пройдет последняя линия уровня в направлении целевого вектора c = (3,2₎. Из рисунка 1.2 видно, что искомой точкой будет точка, лежащая в вершине множества X, образованной пересечением прямых p₁ и p₂. Решая систему уравнений, описывающих эти прямые найдем оптимальный план x₁* = 3 ¹/₃, x₂* = 1 ¹/₃. При этом максимальное значение целевой функции будет равно f(x*) = 12 ²/₃. Таким образом, ежесуточно фабрика должна производить 3 ¹/₃ тонн краски INT и 1 ¹/₃ тонн краски EXT, получая при этом доход 12 ²/₃ тыс. долларов.

x₁ + 2 x₂ = 6,

2 x₁ + x₂ = 8,

Пример 1.2. Лечебное предприятие закупает два вида мультивитаминных комплексов «Здоровье» и «Долголетие» с содержанием витаминов трех видов. Количество единиц этих витаминов в одном грамме мультикомплексов, необходимая их норма при профилактическом приеме и стоимость одного грамма комплексов «Здоровье» и «Долголетие» отражены в таблице

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

Составим математическую модель задачи. Для этого введем переменные: x₁ - количество комплекса «Здоровье» (гр.), x₂ - количество комплекса «Долголетие» (гр.), необходимое для профилактического приема. Целевая функция выражает суммарную стоимость витаминных комплексов, которая должна быть минимально возможной

f(x)= 5 x₁ + 4 x₂ min (1.7)

Ограничения, описывающие выполнение норм по витаминам, имеют вид:

По витамину V₁: 3x₁ + x₂ 9, (1.8)

По витамину V₂: x₁ + 2x₂ 8, (1.9)

По витамину V₃: x₁ + 6x₂ 12. (1.10)

При этом переменные должны быть неотрицательны: x_j 0, j = 1, 2.

Снова начнем решение с построения множества планов X, для чего проведем граничные прямые, уравнения которых получаются при замене в ограничениях знаков неравенств на равенства

p₁: 3 x₁ + x₂ = 9,

p₂: x₁ + 2 x₂ = 8,

p₃: x₁ + 6 x₂ = 12.

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

Рис. 1.2

Изобразим целевую функцию (1.7) с помощью линий уровня. Для этого достаточно построить целевой вектор c = (5, 4) и перпендикулярно ему провести несколько прямых на множестве Х. Поскольку целевой вектор указывает направление возрастания целевой функции, а в задаче о рационе требуется найти ее минимум, то для нахождения оптимального решения будем перемещать линию уровня параллельно самой себе по множеству Х в направлении, противоположном целевому вектору.

Рис. 1.3

Последней точкой множества планов, через которую еще проходит линия уровня будет точка пересечения прямых p₁ и p₂. Решая систему уранений (рис. 1.3).

3 x₁ + x₂ = 9

x₁ + 2 x₂ = 8

получим оптимальный план x₁* = 2, x₂* = 3. Минимальное значение целевой функции при этом будет равно

f(x*) = 5•2 + 4•3 = 22.

Следовательно, самый дешевый набор для профилактического приема состоит из 2 гр. комплекса А и 3 гр. комплекса В, и его стоимость равна 22 руб.

Теперь несложно сформулировать геометрический способ решения стандартных задач ЛП с двумя переменными:

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

изображается целевой вектор ;

через допустимое множество проводится перпендикуляр к целевому вектору - это линия уровня целевой функции;

путем перемещения линии уровня параллельно самой себе в направлении целевого вектора до тех пор, пока не окажется по одну сторону от перемещаемой прямой, визуально определяется точка (или точки) максимума;

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

Замечание. Для определения точки минимума следует перемещать изолинию против направления целевого вектора.

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

Бесконечное множество оптимальных планов. На рис.1.4 целевая функция принимает одно и то же максимальное значение в любой точке отрезка AB, соединяющего две вершины множества планов Х. Такая ситуация возникает, если линии уровня параллельны граничной прямой.

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

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

Рис. 1.4 Рис. 1.5 Рис. 1.6