□ Для записи в форме канонической задачи нужно перейти от ограниченийнеравенств к ограничениям-равенствам. Этот переход может быть осуществлен введением четырех дополнительных неотрицательных переменных. При этом к левым частям каждого неравенства вида " ≤" соответствующая переменная прибавляется, а из левых частей каждого из неравенства вида " ≥" вычитается. В результате, получается следующая каноническая задача: максимизировать функцию F = 3x1 − 2x2 +5x3 + x5 при условиях

2x1 + x3 − x4 + x5 + x6 = 2,x1 − x3 + 2x4 + x5 + x7 = 3,

2x1 + x3 − x4 + 2x5 + x8 = 6, ■x1 + x4 +5x5 − x9 = 8, x1 ,…x9 ≥ 0.

8.3. Геометрическое истолкование задач линейного программирования

Определение. Непустое множество планов общей (основной) задачи линейного программирования называется многогранником решений.

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

Вершину многогранника решений, в которой целевая функция принимает максимальное значение, найти не сложно, если задача содержит не более двух переменных (в общем случае задача, записанная в основной форме, содержит не более двух свободных переменных, то есть n −r ≤ 2 , где n − число переменных, r − ранг матрицы, составленной из коэффициентов в системе ограничений задачи).

Найдем решение задачи, состоящей в определении максимального значения

Каждое из неравенств (8.11), (8.12) геометрически определяет полуплоскость соответственно с граничными прямыми ai1 x1 + ai2 x2 = bi , i =1, ..., k , x1 = 0, x2 = 0.

156

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

Исходная задача линейного программирования состоит в нахождении вершины многоугольника решений, в которой целевая функция (8.10) принимает максимальное значение. Такая вершина существует тогда, когда многоугольник решений не пуст и на нем целевая функция ограничена сверху. Для определения этой вершины построим линию уровня c1 x1 + c2 x2 = h , проходящую через многоугольник решений, и будем перемещать ее в направлении вектора C = (c1 , c2 ) ,

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

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

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

Нормы затрат и общее количество сырья в задаче 1 Таблица 8.2.

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

□ Предположим, что предприятие изготовит x1 единиц изделий вида A , x2

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

157

12x1 + 4x2 ≤ 300,4x1 + 4x2 ≤120,

3x1 +12x2 ≤ 252, x1 , x2 ≥ 0.

Общая прибыль от реализации всей продукции составит F = 30x1 + 40x2 .

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

Эти прямые изображены на рис.8.1. Каждая из прямых делит плоскость (x1 , x2 )

на две полуплоскости. Координаты точек одной полуплоскости удовлетворяют исходному неравенству, а координаты другой − нет. Пересечение полученных полуплоскостей определяет многоугольник решений данной задачи.

Рис. 8.1. Графическое решение примера 8.4

Из рис. 8.1 следует, что многоугольником решений является пятиугольник OABCD . Задача будет решена, если найдется точка, принадлежащая пятиугольнику OABCD , в которой функция F = 30x1 + 40x2 принимает максимальное значение. Для определения этой точки построим вектор C = (30;40) и прямую 30x1 + 40x2 = h , где

158

h − некоторое число, при котором прямая имеет общие точки с многоугольником решений. Положим например, h = 480 и построим прямую 30x1 + 40x2 = 480 (см.

рис.8.1).

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

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

4x1 + 4x2 =120,3x1 +12x2 = 252.

Решив эту систему, получим x1 =12, x2 =18 . Следовательно, если предприятие изготовит 12 изделий вида A и 18 вида B , то оно получит максимальную прибыль

F = 30 12 + 40 18 =1080 . ■

Пример 8.5. Найти минимум и максимум функции F = x1 + x2 при условиях

2x1 + 4x2 ≤16,

− 4x1 + 2x2 ≤ 8,x1 +3x2 ≥ 9,

x1 , x2 ≥ 0.

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

159