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

Р е ш е н и е. Прежде всего построим экономико-математическую модель этой задачи. Предположим, что предприятие изготовит x₁ изделий вида P₁ и x₂ изделий вида P₂. Суммарная прибыль p(x) от реализации x₁ изделий P₁ и x₂ изделий P₂ составит p(x) = 30 x₁ + 80 x₂ . При этом сырья S₁ будет израсходовано 2 x₁ + 4 x₂ , а так как запас этого сырья равен 240 кг, то получаем следующее ресурсное ограничение: 2 x₁ + 4 x₂  240. Аналогично, для сырья S₂ и S₃ имеем: 4 x₁ + 5 x₂  400, 2,5 x₁ + 2 x₂  200.

Поскольку изделий вида P₂ может быть произведено не больше, чем изделий вида P₁, то x₂  x₁ . При этом выпуск продукции не может быть отрицательным, т.е. x₁  0, x₂  0. Таким образом, получили математическую модель поставленной задачи, которая представлена в стандартной форме записи:

p(x) = 30 x₁ + 80 x₂  max

x₁  0 , x₂  0.

Таблица 1.1.

Исходные данные для примера 1.5.

Вид сырья	Нормы расхода сырья на одно изделие, кг		Наличие (запасы) сырья, кг
	P1	P2
S1 S2 S3	2 4 2,5	4 5 2	240 400 200
Прибыль от реализации одного изделия, руб.	30	80

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

Теперь в четырехугольнике OABC необходимо найти точку, в которой целевая функция p(x) принимает максимальное значение. Чтобы определить такую точку, построим градиент функции p(x), а именно p(x) = (30; 80) и начальную линию уровня, проходящую через точку (0; 0) и перпендикулярную градиенту, p(x) = 30 x₁ + 80 x₂ = 0. На рис. 1.9 линия уровня p(x) = 0 обозначена а, а линия уровня, проходящая через точку максимума, обозначена а^.

Перемещая построенную прямую в направлении вектора p(x), нетрудно заметить, что последней общей точкой ее и многоугольника решений задачи будет точка A. Координаты этой точки и определяют оптимальный план выпуска изделий P₁ и P₂. Вычислим координаты точки A как точки пересечения прямых линий (1) и (4):

.

Решив данную систему уравнений, получим Таким образом, если предприятие изготовит и реализует 40 изделий P₁ и 40 изделий P₂, то оно получит максимальную прибыль p(x^*) = 3040 + 8040 = 4400 руб.

Заметим, что любая другая точка многоугольника OABC, отличная от точки A, представляет допустимый план производства изделий, который дает меньшее значение целевой функции. В частности, план, соответствующий точке B, обеспечит прибыль в размере 4266,7 руб., а план, соответствующий точке C, обеспечит прибыль и того меньше – всего 2400 руб.

x₂ (5)

100 --

80 -- p(Х) (4)

60 --

40 -- A

B

20 -- а^

С (6)

-       x₁

0 20 40 60 80 100 120

p(x)=0

а (3) (2) (1)

Рис. 1.9. Графический метод решения ЗЛП (пример 1.5)

Однако, если снять ограничение x₂  x₁, то оптимальный план выпуска изделий существенно изменится, а именно изделие P₁ производить станет не выгодно , а изделие P₂ необходимо производить в количестве 60 единиц . При этом прибыль предприятия составит 4800 руб., что на 400 руб. больше, чем в исходной постановке задачи.

Замечание. Графический метод решения ЗЛП может быть применен и к каноническим задачам, в которых n – m = 2, где n – количество переменных, а m – количество уравнений. Для этого нужно выбрать две произвольные переменные x_k и x_l , через которые можно определить другие переменные. Затем, используя систему уравнений, выразить через них остальные переменные , где – линейные функции.

Исходя из геометрической интерпретации ЗЛП, можно сделать выводы:

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

2. Если оптимальный план существует, то он может быть единственным. При этом он обязательно находится в одной из вершин допустимого множества.

3. Оптимальный план либо единственный, либо оптимальных планов бесчисленное множество (отрезок, луч).

Геометрическая интерпретация стандартной ЗЛП для n = 2 может быть распространена на произвольное n  3. Тогда ограничение стандартной задачи имеет вид и определяет гиперплоскость, если знак “  ” заменить на “ = ”. В двумерном пространстве – это прямая, в трехмерном пространстве – плоскость, при n  3 – гиперплоскость. Точки, которые удовлетворяют ограничениям-неравенствам, находятся в одном из полупространств. Следовательно, множество допустимых планов в стандартной задаче является пересечением полупространств, соответствующих ограничениям-неравенствам.

Оптимальный план x^*, если он существует, находится в одной из вершин многогранника. Поэтому, чтобы его найти, необходимо перебрать все вершины многогранника и выбрать из них такую вершину, координаты которой доставляют максимум целевой функции. Однако уже при относительно небольших n и m количество вариантов очень велико. Так, при n = m = 30 количество возможных вариантов превышает 10³¹. Последовательный перебор всех вариантов не возможен даже при использовании быстродействующего компьютера. Поэтому разработаны методы решения ЗЛП, позволяющие находить оптимальный план, не перебирая все вершины допустимого множества.