Учебники

Выпуклая оптимизация – линейное программирование

Линейное программирование, также называемое линейной оптимизацией, – это метод, который используется для решения математических задач, в которых отношения являются линейными по природе. основная природа линейного программирования заключается в максимизации или минимизации целевой функции с учетом некоторых ограничений . Целевая функция – это линейная функция, полученная из математической модели задачи. Ограничения – это условия, которые накладываются на модель и также являются линейными.

  • Из заданного вопроса найдите целевую функцию.
  • найти ограничения.
  • Нарисуйте ограничения на графике.
  • найти допустимую область, которая образована пересечением всех ограничений.
  • найти вершины допустимой области.
  • найти значение целевой функции в этих вершинах.
  • Вершина, которая либо максимизирует, либо минимизирует целевую функцию (в зависимости от вопроса) является ответом.

Примеры

Шаг 1 – Максимизируйте $ 5x + 3y $ с учетом

$ x + y \ leq 2 $,

$ 3x + y \ leq 3 $,

$ x \ geq 0 \: and \: y \ geq 0 $

Решение

Первый шаг – найти допустимую область на графике.

Пример 1

Из графика видно, что вершины допустимой области

$ \ 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 $

Построив вышеприведенные уравнения на графике, получим,

Пример 2

Вершины допустимой области

$ \ 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 единиц механических часов.