Optimización convexa: programación lineal
Metodología
La Programación Lineal, también llamada Optimización Lineal, es una técnica que se utiliza para resolver problemas matemáticos en los que las relaciones son de naturaleza lineal. La naturaleza básica de la programación lineal es maximizar o minimizar unobjective function con sujeto a algunos constraints. La función objetivo es una función lineal que se obtiene del modelo matemático del problema. Las restricciones son las condiciones que se imponen al modelo y también son lineales.
- A partir de la pregunta dada, encuentre la función objetivo.
- encontrar las limitaciones.
- Dibuja las restricciones en un gráfico.
- encuentre la región factible, que está formada por la intersección de todas las restricciones.
- encuentra los vértices de la región factible.
- encuentra el valor de la función objetivo en estos vértices.
- El vértice que maximiza o minimiza la función objetivo (según la pregunta) es la respuesta.
Ejemplos
Step 1 - Maximizar $ 5x + 3y $ sujeto a
$ x + y \ leq 2 $,
$ 3x + y \ leq 3 $,
$ x \ geq 0 \: y \: y \ geq 0 $
Solution -
El primer paso es encontrar la región factible en un gráfico.
Claramente del gráfico, los vértices de la región factible son
$ \ left (0, 0 \ right) \ left (0, 2 \ right) \ left (1, 0 \ right) \ left (\ frac {1} {2}, \ frac {3} {2} \ right PS
Sea $ f \ left (x, y \ right) = 5x + 3y $
Poniendo estos valores en la función objetivo, obtenemos -
$ 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
Por lo tanto, la función se maximiza en $ \ left (\ frac {1} {2}, \ frac {3} {2} \ right) $
Step 2- Una empresa de relojes produce un reloj mecánico y otro digital. Las proyecciones a largo plazo indican una demanda esperada de al menos 100 relojes digitales y 80 mecánicos cada día. Debido a las limitaciones en la capacidad de producción, no se pueden fabricar más de 200 relojes digitales y 170 mecánicos al día. Para cumplir con un contrato de envío, se envían un total de al menos 200 relojes cada día.
Si cada reloj digital vendido da como resultado una pérdida de $ \ $ 2 $, pero cada reloj mecánico produce una ganancia de $ \ $ 5 $, ¿cuántos de cada tipo deberían hacerse diariamente para maximizar las ganancias netas?
Solution -
Sea $ x $ el número de relojes digitales producidos
$ y $ sea el número de relojes mecánicos producidos
Según la pregunta, se deben fabricar al menos 100 relojes digitales al día y se pueden fabricar como máximo 200 relojes digitales.
$ \ Flecha derecha 100 \ leq \: x \ leq 200 $
Del mismo modo, se deben fabricar al menos 80 relojes mecánicos al día y un máximo de 170 relojes mecánicos.
$ \ Flecha derecha 80 \ leq \: y \ leq 170 $
Dado que se van a producir al menos 200 relojes cada día.
$ \ Flecha derecha x + y \ leq 200 $
Dado que cada reloj digital vendido resulta en una pérdida de $ \ $ 2 $, pero cada reloj mecánico produce una ganancia de $ \ $ 5 $,
El beneficio total se puede calcular como
$ Beneficio = -2x + 5y $
Y tenemos que maximizar la ganancia, por lo tanto, la pregunta se puede formular como:
Maximizar $ -2x + 5y $ sujeto a
$ 100 \: \ leq x \: \ leq 200 $
$ 80 \: \ leq y \: \ leq 170 $
$ x + y \: \ leq 200 $
Al trazar las ecuaciones anteriores en un gráfico, obtenemos,
Los vértices de la región factible son
$ \ left (100, 170 \ right) \ left (200, 170 \ right) \ left (200, 180 \ right) \ left (120, 80 \ right) e \ left (100, 100 \ right) $
El valor máximo de la función objetivo se obtiene en $ \ left (100, 170 \ right) $ Por lo tanto, para maximizar las ganancias netas, se deben producir 100 unidades de relojes digitales y 170 unidades de relojes mecánicos.