Решение. 1. Построение математической модели

1. Построение математической модели

В данной задаче следует определить

х ₁ — число изделий, заказанное первой фирме;

х ₂ — число изделий, заказанное второй фирме.

Эти величины являются переменными модели. Ясно, что они должны принимать неотрицательные значения, т.е. х ₁ ≥ 0 и х ₂ ≥ 0; причем их сумма должна равняться общему числу заказанных изделий, т.е. х ₁ + х ₂ = 100.

Цель предпринимателя — минимизировать суммарные затраты на выполнение заказа. Так как стоимость х ₁ изделий, заказанных первой фирме составляет

f ₁(x ₁) = 25+ 2 x ₁+ 0.2 ,

а стоимость х ₂ изделий, заказанных второй фирме, составляет

f ₂(x ₂) = 15+ 6 x ₂+ 0.3 ,

то суммарные затраты Z на выполнение всего заказа равны

Z = f (x ₁, x ₂) = f ₁(x ₁) + f ₂(x ₂) = 25+ 2 x ₁+ 0.2 + 15+ 6 x ₂+ 0.3 (руб.).

Таким образом, целевая функция (ЦФ) имеет вид:

f (x ₁, x ₂) = 40+ 2 x ₁+ 0.2 + 6 x ₂+ 0.3 .

Математическая модель задачи может быть записана в таком виде: найти неизвестные значения переменных х ₁ и х ₂, доставляющие минимальное значение ЦФ

Z = 40+ 2 x ₁ + 0.2 + 6 x ₂ + 0.3 → min (1)

и удовлетворяющие ограничениям

х ₁ + х ₂ = 100, (2)

х ₁ ≥ 0, х ₂ ≥ 0. (3)

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

а) Построение ОДР

ОДР состоит из точек плоскости с неотрицательными координатами, которые лежат на прямой, задаваемой уравнением (2). Следовательно, ОДР представляет собой отрезок прямой АВ (см. рис. 1).

Рис. 1. Графическое решение задачи 1

б) Построение и анализ линий уровня ЦФ

Приведем ЦФ к более удобному для анализа виду, выделив полные квадраты по каждой ее переменной:

f (х ₁, х ₂) =40+ 2 x ₁ + 0.2 + 6 x ₂ + 0.3 =

0.2( + 10 x ₁ + 25) + 0.3( + 20 x ₂ + 100) + 5 =
0.2(х ₁ + 5)² + 0.3(x ₂ + 10)² + 5.

Пусть С — некоторое фиксированное число. Тогда линия уровня функции

f (х ₁, х ₂) = С

состоит из всех точек х = (х ₁, х ₂) плоскости, координаты которых удовлетворяют уравнению

0.2(х ₁ + 5)² + 0.3(x ₂ + 10)² + 5 = С

или 0.2(х ₁ + 5)² + 0.3(x ₂ + 10)² = С – 5. (4)

Так как левая часть этого уравнения неотрицательна при любых значениях х ₁ и х ₂, то ясно, что должно выполняться неравенство С ≥ 5, поскольку при С < 5 это уравнение не имеет решений.

Если С = 5, то линия уровня целевой функции содержит единственную точку О = (-5, -10), так как левая часть уравнения (4) равна нулю лишь при х ₁ = -5 и х ₂ = ‑10.

При С > 5 линии уровня являются эллипсами[1] с общим центром в точке О, размеры которых увеличиваются с ростом параметра С (см. рис. 1).

в) Нахождение точки минимума ЦФ

С ростом параметра С линии уровня ЦФ становятся все ближе к ОДР задачи — отрезку АВ. Сначала они не имеют с ним общих точек, но при определенном значении С = С_min линия уровня коснется этого отрезка в некоторой точке х ^* = (). Эта точка соответствует наименьшему значению С, при котором линия уровня имеет общие точки с АВ. Значит, точка х ^* является решением задачи, так как в ней ЦФ достигает минимума на этом отрезке.

Для определения ее координат воспользуемся следующим фактом. Если прямая

х ₁ + х ₂ = 100,

касается в некоторой точке линии уровня ЦФ, задаваемой уравнением

f (х ₁, х ₂) = С,

то градиент Ñ f = , вычисленный в точке касания, перпендикулярен этой прямой. Это означает, что координаты ее вектора нормали прямой, т.е. вектора а = (1, 1), пропорциональны координатам вектора Ñ f. Таким образом, выполняется соотношение

или .

Поскольку = 0.4 х ₁ + 2, а = 0.6 х ₂ + 6, то из равенства частных производных получаем, что координаты точки касания удовлетворяют уравнению

.

Значит, точку минимума ЦФ можно найти, решив систему уравнений

или (5)

Ее решение: = 64, = 36. Вычислим значение ЦФ в этой точке:

Z ^* = f () = 0.2(64 + 5)² + 0.3(36 + 10)² + 5 = 1592 (руб.).

Итак, получено решение задачи (1) – (3): предприниматель должен заказать первой фирме 62 изделия, а второй фирме — 36 изделий. В этом случае его затраты будут минимальными и составят 1592 руб.

г) Нахождение точки максимума ЦФ

При дальнейшем увеличении параметра С линии уровня будут пересекать ОДР в точках, которым соответствуют все возрастающие значения ЦФ. Поэтому последняя точка пересечения является точкой максимума ЦФ на отрезке АВ. Из рис. 1 видно, что в нашей задаче ЦФ достигает максимума в точке А = (0, 100). В этой точке значение ЦФ равно

Z_max = f (0, 100) = 0.2(0 + 5)² + 0.3(100 + 10)² + 5 = 3635 (руб.).

Таким образом, самым неудачным решением предпринимателя будет выбор второй фирмы в качестве единственного исполнителя заказа. В этом случае его затраты будут максимальными и составят 3635 руб.

Замечание. Графический анализ показывает, что ЦФ достигает своего максимума в одной из крайних точек отрезка АВ. Поэтому для определения точки максимума проще всего сравнить значения ЦФ в точках А и В. Та точка, в которой это значение больше, будет искомой. Если же значения ЦФ в этих точках равны, то это означает, что обе они являются точками максимума.

3. Нахождение оптимального решения методом множителей Лагранжа

Сначала убедимся в том, что задача (1) – (3) является задачей выпуклого программирования (ВП). Действительно, все ограничения задачи линейны, а ЦФ — выпуклая функция, как сумма выпуклых функций f ₁(x ₁) и f ₂(x ₂).

Чтобы применить метод множителей Лагранжа для решения задачи, следует отбросить условие неотрицательности переменных (3). Тогда исходная задача может быть переформулирована следующим образом: найти неизвестные значения переменных х ₁ и х ₂, доставляющие минимальное значение функции

Z = 40+ 2 x ₁+ 0.2 + 6 x ₂+ 0.3 → min(6)

и удовлетворяющие условию

х ₁ + х ₂ = 100. (7)

Ясно, что эта задача также является задачей ВП. Отказ от условия (3) приводит к расширению ОДР, так что оптимальное решение задачи (6) – (7) может оказаться недопустимым в исходной задаче (1) – (3). Однако очевидно, что если оптимальное решение задачи (6) – (7) удовлетворяет условию неотрицательности, то это решение будет оптимально и в исходной задаче.

Построим функцию Лагранжа задачи (6) – (7) по формуле (8). Она имеет вид

L (x ₁, x ₂, λ) = 40+ 2 x ₁+ 0.2 + 6 x ₂+ 0.3 + λ (100 – х ₁ – х ₂). (8)

Найдем частные производные функции L по x ₁, x ₂и λ, а затем приравняем их к нулю. Получим следующую систему уравнений:

(9)

Исключим переменную λ, вычтя из первого уравнения второе. Тогда получим систему уравнений:

(10)

Она фактически совпадает с системой (5) и, значит, имеет такое же решение: = 64 и = 36. Поскольку задача (6) – (7) является задачей ВП, то вектор х ^* = (, ) = (64, 36) является ее оптимальным решением. Так как найденное решение удовлетворяет условию неотрицательности, то оно будет оптимальным в исходной задаче (1) – (3).

Итак, методом множителей Лагранжа получено оптимальное решение, совпадающее с решением, полученным ранее графическим методом: предприниматель должен распределить заказ между фирмами следующим образом: заказать первой фирме 62 изделия, а второй фирме — 36 изделий. В этом случае его затраты будут минимальными и составят 1592 руб.

Из первого уравнения в системе (9) легко найти оптимальное значение множителя Лагранжа: λ^* = 0.4×64 + 2 = 27.6 (руб./ед.).

Множитель Лагранжа λ^* имеет такую экономическую интерпретацию: его величина приближенно показывает насколько возрастут минимальные общие затраты Z ^*(d), если величина заказа d увеличится на единицу, т.е.

λ ^* ≈ Δ Z ^*(d) = Z ^*(d + 1) – Z ^*(d).

Таким образом, при увеличении заказа от 100 ед. до 101 ед. затраты возрастут примерно на 27.6 руб.

Замечание 1. Точное значение прироста затрат несколько выше: оно равно 27.72 руб. Его можно получить, решив задачу 1 для d = 101. Для этого достаточно найти решение системы, аналогичной (10), в которой второе уравнение имеет следующий вид: 101 – х ₁ – х ₂ = 0.

Замечание 2. Решение задачи 1 можно свести к отысканию минимума функции одной переменной на заданном отрезке. Для этого достаточно выразить одну из переменных через другую, используя уравнение (2), а затем подставить полученное выражение в формулу (1), определяющую ЦФ. Однако этот упрощающий прием возможен лишь потому, что ограничение в задаче имеет очень простой вид, и не применим в общем случае. Универсальным способом решения оптимизационных задач с ограничениями типа равенства является метод множителей Лагранжа.