Линейное программирование, также называемое линейной оптимизацией, — это метод, который используется для решения математических задач, в которых отношения являются линейными по природе. основная природа линейного программирования заключается в максимизации или минимизации целевой функции с учетом некоторых ограничений . Целевая функция — это линейная функция, полученная из математической модели задачи. Ограничения — это условия, которые накладываются на модель и также являются линейными.
- Из заданного вопроса найдите целевую функцию.
- найти ограничения.
- Нарисуйте ограничения на графике.
- найти допустимую область, которая образована пересечением всех ограничений.
- найти вершины допустимой области.
- найти значение целевой функции в этих вершинах.
- Вершина, которая либо максимизирует, либо минимизирует целевую функцию (в зависимости от вопроса) является ответом.
Примеры
Шаг 1 — Максимизируйте $ 5x + 3y $ с учетом
$ x + y \ leq 2 $,
$ 3x + y \ leq 3 $,
$ x \ geq 0 \: and \: y \ geq 0 $
Решение —
Первый шаг — найти допустимую область на графике.
Из графика видно, что вершины допустимой области
$ \ left (0, 0 \ right) \ left (0, 2 \ right) \ left (1, 0 \ right) \ left (\ frac {1} {2}, \ frac {3} {2} \ right ) $
Пусть $ f \ left (x, y \ right) = 5x + 3y $
Поместив эти значения в целевую функцию, мы получим —
$ f \ left (0, 0 \ right) $ = 0
$ f \ left (0, 2 \ right) $ = 6
$ f \ left (1, 0 \ right) $ = 5
$ f \ left (\ frac {1} {2}, \ frac {3} {2} \ right) $ = 7
Следовательно, функция максимизируется в $ \ left (\ frac {1} {2}, \ frac {3} {2} \ right) $
Шаг 2 — Часовая компания производит цифровые и механические часы. Долгосрочные прогнозы указывают на ожидаемый спрос не менее 100 цифровых и 80 механических часов каждый день. Из-за ограничений на производственную мощность в день можно производить не более 200 цифровых и 170 механических часов. Чтобы удовлетворить контракт на перевозку, каждый день отправляется не менее 200 часов.
Если каждая проданная цифровая модель приносит убыток в размере $ \ $ 2 $, но каждая механическая модель приносит прибыль в размере $ \ $ 5 $, сколько единиц каждого типа следует делать ежедневно, чтобы максимизировать чистую прибыль?
Решение —
Пусть $ x $ будет количеством произведенных цифровых часов
$ y $ — количество произведенных механических часов
В соответствии с этим вопросом, по крайней мере, 100 цифровых часов должны изготавливаться ежедневно, и может быть сделано максимум 200 цифровых часов.
$ \ Rightarrow 100 \ leq \: x \ leq 200 $
Точно так же, по крайней мере, 80 механических часов должны изготавливаться ежедневно и максимум 170 механических часов.
$ \ Rightarrow 80 \ leq \: y \ leq 170 $
Поскольку по крайней мере 200 часов должны выпускаться каждый день.
$ \ Rightarrow x + y \ leq 200 $
Поскольку каждая проданная цифровая модель приносит убыток в размере $ \ $ 2 $, но каждая механическая модель приносит прибыль в размере $ \ $ 5 $,
Общая прибыль может быть рассчитана как
$ Прибыль = -2x + 5y $
И мы должны максимизировать прибыль, поэтому вопрос можно сформулировать так:
Увеличить $ -2x + 5y $ при условии
$ 100 \: \ leq x \: \ leq 200 $
$ 80 \: \ leq y \: \ leq 170 $
$ x + y \: \ leq 200 $
Построив вышеприведенные уравнения на графике, получим,
Вершины допустимой области
$ \ left (100, 170 \ right) \ left (200, 170 \ right) \ left (200, 180 \ right) \ left (120, 80 \ right) и \ left (100, 100 \ right) $
Максимальное значение целевой функции получается при $ \ left (100, 170 \ right) $. Таким образом, чтобы максимизировать чистую прибыль, необходимо произвести 100 единиц цифровых часов и 170 единиц механических часов.