La optimización lo ayuda a encontrar el mejor resultado que genere ganancias, reduzca costos o establezca un parámetro que provoque fallas en los procesos comerciales.
Este proceso también se llama programación matemática. Resuelve el problema de determinar la distribución de los recursos limitados necesarios para alcanzar el objetivo planteado por el jefe del problema de optimización. De todas las opciones posibles, es deseable encontrar aquella que maximice (o reduzca) el parámetro de control, por ejemplo, la ganancia o el costo. Los modelos de optimización también se denominan prescriptivos o normativos porque buscan encontrar una estrategia factible para el negocio.
Historial de desarrollo
La programación lineal (PL) funciona con una clase de problemas de optimización donde todas las restricciones son lineales.
Presentamos una breve historia del desarrollo de LP:
- En 1762, Lagrange resolvió problemas simples de optimización con restricciones de igualdad.
- En 1820, Gauss decidiósistema lineal de ecuaciones usando eliminación.
- En 1866, Wilhelm Jordan perfeccionó el método de encontrar errores de mínimos cuadrados como criterio de ajuste. Esto ahora se llama el método de Gauss-Jordan.
- La computadora digital apareció en 1945.
- Danzig inventó los métodos símplex en 1947.
- En 1968, Fiacco y McCormick introdujeron el método Inside Point.
- En 1984, Karmarkar aplicó el método interior para resolver programas lineales, añadiendo su innovador análisis.
LP ha demostrado ser una herramienta extremadamente poderosa tanto para modelar problemas del mundo real como una teoría matemática ampliamente aplicada. Sin embargo, muchos problemas de optimización interesantes no son lineales.
¿Qué hacer en este caso? El estudio de tales problemas involucra una mezcla variada de álgebra lineal, cálculo multivariado, análisis numérico y métodos computacionales. Los científicos están desarrollando algoritmos computacionales, incluidos métodos de puntos interiores para programación lineal, geometría, análisis de funciones y conjuntos convexos, y el estudio de problemas especialmente estructurados, como la programación cuadrática.
La optimización no lineal proporciona una comprensión fundamental del análisis matemático y se usa ampliamente en diversos campos, como la ingeniería, el análisis de regresión, la gestión de recursos, la exploración geofísica y la economía.
Clasificación de problemas de optimización
Un paso importante enEl proceso de optimización es la clasificación de modelos, ya que sus algoritmos de solución se adaptan a un tipo particular.
1. Problemas de optimización discreta y continua. Algunos modelos tienen sentido solo si las variables toman valores de un subconjunto discreto de enteros. Otros contienen datos que pueden tomar cualquier valor real. Suelen ser más fáciles de resolver. Las mejoras en los algoritmos, combinadas con los avances en la tecnología informática, han aumentado drásticamente el tamaño y la complejidad de un problema de optimización de programación lineal.
2. Optimización ilimitada y limitada. Otra diferencia importante son las tareas en las que no hay restricciones en las variables. Puede variar ampliamente desde simples estimadores hasta sistemas de igualdades y desigualdades que modelan relaciones complejas entre datos. Estos problemas de optimización se pueden clasificar según la naturaleza de las funciones (lineales y no lineales, convexas y uniformes, diferenciables y no diferenciables).
3. Tareas de viabilidad. Su objetivo es encontrar valores de variables que satisfagan las restricciones del modelo sin ningún objetivo de optimización específico.
4. Tareas de complementariedad. Son ampliamente utilizados en tecnología y economía. El objetivo es encontrar una solución que satisfaga las condiciones de complementariedad. En la práctica, las tareas con varias metas a menudo se reformulan en tareas de un solo objetivo.
5. Optimización determinista versus estocástica. La optimización determinista asume que los datos paralas asignaciones son completamente precisas. Sin embargo, en muchos temas de actualidad no se pueden conocer por varias razones.
La primera tiene que ver con un simple error de medición. La segunda razón es más fundamental. Se encuentra en el hecho de que algunos datos representan información sobre el futuro, por ejemplo, la demanda de un producto o el precio para un período de tiempo futuro. Al optimizar en condiciones de optimización estocástica, la incertidumbre se incluye en el modelo.
Componentes principales
La función objetivo es la que se quiere minimizar o maximizar. La mayoría de los tipos de problemas de optimización tienen una función objetivo. Si no, a menudo se pueden reformular para que funcionen.
Dos excepciones a esta regla:
1. Tarea de búsqueda de objetivos. En la mayoría de las aplicaciones de negocios, el gerente quiere lograr una meta específica mientras satisface las restricciones del modelo. El usuario no quiere optimizar algo en particular, por lo que no tiene sentido definir una función objetivo. Este tipo se conoce comúnmente como un problema de satisfacibilidad.
2. Muchas características objetivas. A menudo, a un usuario le gustaría optimizar varios objetivos diferentes a la vez. Suelen ser incompatibles. Las variables que optimizan para un objetivo pueden no ser las mejores para otros.
Tipos de componentes:
- Una entrada controlada es un conjunto de variables de decisión que afectan el valor de una función objetivo. En una tarea de producción, las variables pueden incluir la distribución de los diversos recursos disponibles o el trabajo requerido paracada acción.
- Las restricciones son relaciones entre variables de decisión y parámetros. Para un problema de producción, no tiene sentido dedicar mucho tiempo a ninguna actividad, así que limite todas las variables "temporales".
- Soluciones posibles y óptimas. El valor de la decisión para las variables, bajo el cual se satisfacen todas las restricciones, se llama satisfacible. La mayoría de los algoritmos primero lo encuentran y luego intentan mejorarlo. Finalmente, cambian las variables para pasar de una solución factible a otra. Este proceso se repite hasta que la función objetivo alcanza su máximo o mínimo. Este resultado se llama solución óptima.
Los algoritmos de problemas de optimización desarrollados para los siguientes programas matemáticos son ampliamente utilizados:
- Convexo.
- Separables.
- Cuadrático.
- Geométrica.
Solvers lineales de Google
Optimización lineal o programación es el nombre que se le da al proceso computacional de resolución óptima de un problema. Se modela como un conjunto de relaciones lineales que surgen en muchas disciplinas científicas y de ingeniería.
Google ofrece tres formas de resolver problemas de optimización lineal:
- Biblioteca de código abierto Glop.
- Complemento de optimización lineal para Hojas de cálculo de Google.
- Servicio de optimización lineal en Google Apps Script.
Glop está integrado en Googlesolucionador lineal Está disponible en código abierto. Puede acceder a Glop a través del contenedor de solución lineal OR-Tools, que es un contenedor para Glop.
El módulo de optimización lineal para Hojas de cálculo de Google le permite realizar una declaración lineal del problema de optimización ingresando datos en una hoja de cálculo.
Programación cuadrática
La plataforma Premium Solver utiliza una versión extendida LP/cuadrática del método Simplex con límites de procesamiento de problemas LP y QP de hasta 2000 variables de decisión.
SQP Solver para problemas a gran escala utiliza una implementación moderna del método de conjunto activo con escasez para resolver problemas de programación cuadrática (QP). El motor XPRESS Solver utiliza una extensión natural del método "Punto interior" o Barrera de Newton para resolver problemas QP.
MOSEK Solver aplica métodos incrustados de "Punto interno" y auto-dual. Esto es especialmente efectivo para problemas QP débilmente acoplados. También puede resolver los problemas de Restricción cuadrática de escala (QCP) y Programación de cono de segundo orden (SOCP).
Cálculos multioperación
Se utilizan con bastante éxito con el uso de funciones de Microsoft Office, por ejemplo, para resolver problemas de optimización en Excel.
En la tabla anterior, los símbolos son:
- K1 - K6 - clientes que necesitan proporcionar bienes.
- S1 - S6 son posibles sitios de producción que podrían construirse para esto. se puede crear1, 2, 3, 4, 5 o las 6 ubicaciones.
Hay costos fijos para cada instalación enumerada en la columna I (Fijo).
Si la ubicación no cambia nada, no contará. Entonces no habrá costes fijos.
Identifique ubicaciones potenciales para obtener el costo más bajo.
En estas condiciones, la ubicación se establece o no. Estos dos estados son: "VERDADERO - FALSO" o "1 - 0". Hay seis estados para seis ubicaciones, por ejemplo, 000001 se establece solo en el sexto, 111111 se establece en todos.
En el sistema numérico binario, hay exactamente 63 opciones diferentes desde 000001 (1) hasta 111111 (63).
L2-L64 debería leer ahora {=OPERACIÓN MÚLTIPLE (K1)}, estos son los resultados de todas las soluciones alternativas. Entonces el valor mínimo es=Min (L) y la alternativa correspondiente es INDICE (K).
Programación de enteros CPLEX
A veces, una relación lineal no es suficiente para llegar al corazón de un problema empresarial. Esto es especialmente cierto cuando las decisiones implican opciones discretas, como abrir o no un almacén en una ubicación determinada. En estas situaciones, se debe utilizar la programación entera.
Si el problema involucra tanto opciones discretas como continuas, es un programa entero mixto. Puede tener problemas cuadráticos convexos lineales y las mismas restricciones de segundo orden.
Los programas enteros son mucho más complejos que los programas lineales, pero tienen importantes aplicaciones comerciales. SoftwareEl software CPLEX utiliza métodos matemáticos complejos para resolver problemas de números enteros. Sus métodos implican la búsqueda sistemática de posibles combinaciones de variables discretas utilizando relajaciones de software lineales o cuadráticas para calcular los límites del valor de la solución óptima.
También utilizan LP y otros métodos de resolución de problemas de optimización para calcular las restricciones.
Solver estándar de Microsoft Excel
Esta tecnología utiliza la implementación básica del método Simplex principal para resolver problemas de LP. Está limitado a 200 variables. "Premium Solver" utiliza un método símplex primario mejorado con límites de dos caras para las variables. La plataforma Premium Solver utiliza una versión extendida de LP/Quadratic Simplex Solver para resolver un problema de optimización con hasta 2000 variables de decisión.
El LP a gran escala para la plataforma Premium Solver aplica una implementación de vanguardia del método símplex simple y doble, que utiliza la escasez en el modelo LP para ahorrar tiempo y memoria, estrategias avanzadas para actualizar y matrices de refactorización, fijación de precios y rotaciones múltiples y parciales, y para superar la degeneración. Este motor está disponible en tres versiones (capaz de manejar hasta 8.000, 32.000 o variables y límites ilimitados).
MOSEK Solver incluye simplex primario y dual, un método que también explota la escasez y utiliza estrategias avanzadas para la actualización y "refactorización" de matrices. Resuelve problemas de tamaño ilimitado, fueprobado en problemas de programación lineal con millones de variables de decisión.
Ejemplo paso a paso en EXCEL
Para definir el modelo del problema de optimización en Excel, realice los siguientes pasos:
- Organizar los datos del problema en una hoja de cálculo de forma lógica.
- Seleccione una celda para almacenar cada variable.
- Cree en la celda una fórmula para calcular el modelo matemático objetivo del problema de optimización.
- Cree fórmulas para calcular el lado izquierdo de cada restricción.
- Utilice cuadros de diálogo en Excel para informar a Solver sobre variables de decisión, objetivos, restricciones y límites deseados en esos parámetros.
- Ejecute "Solver" para encontrar la solución óptima.
- Crea una hoja de Excel.
- Organizar los datos para el problema en Excel donde se calcula la fórmula para la función objetivo y la restricción.
En la tabla anterior, las celdas B4, C4, D4 y E4 se han reservado para representar las variables de decisión X 1, X 2, X 3 y X 4. Ejemplos de decisión:
- El modelo de combinación de productos ($450, $1150, $800 y $400 de ganancia por producto) se ingresó en las celdas B5, C5, D5 y E5, respectivamente. Esto permite calcular el objetivo en F5=B5B4 + C5C4 + D5D4 + E5E4 o F5:=SUMPRODUCT (B5: E5, B4: E4).
- En B8 ingrese la cantidad de recursos necesarios para fabricar cada tipo de producto.
- Fórmula para F8:=SUMAPRODUCTO(B8:E8, $B$4:$E$4).
- Copiar estofórmula en F9. Los signos de dólar en $B$4:$E$4 indican que este rango de celdas permanece constante.
- En G8 ingrese la cantidad disponible de recursos de cada tipo, correspondiente a los valores de las restricciones a la derecha. Esto le permite expresarlos así: F11<=G8: G11.
- Esto es equivalente a cuatro límites F8<=G8, F9 <=G9, F10 <=G10 y F11=0
Campos de aplicación práctica del método
La optimización lineal tiene muchas aplicaciones prácticas como ejemplo de un problema de optimización:
Una empresa puede fabricar varios productos con un margen de contribución conocido. La producción de una unidad de cada artículo requiere una cantidad conocida de recursos limitados. La tarea es crear un programa de producción para determinar la cantidad de cada producto que se debe producir para maximizar las ganancias de la empresa sin violar las restricciones de recursos.
Los problemas de mezcla son la solución a los problemas de optimización relacionados con la combinación de ingredientes en el producto final. Un ejemplo de esto es el problema de la dieta estudiado por George Danzig en 1947. Se dan una serie de materias primas, como la avena, la carne de cerdo y el aceite de girasol, así como su contenido nutricional, como proteínas, grasas, vitamina A, y su precio por kilogramo. El desafío es mezclar uno o más productos finales a partir de materias primas al menor costo posible, respetando los límites mínimos y máximos de su valor nutricional.
Una aplicación clásica de un problema de optimización lineal es determinar el enrutamiento para las necesidadestráfico en redes de telecomunicaciones o transporte. Al mismo tiempo, los flujos deben enrutarse a través de la red de tal manera que se cumplan todos los requisitos de tráfico sin violar las condiciones de ancho de banda.
En teoría matemática, la optimización lineal se puede utilizar para calcular estrategias óptimas en juegos de suma cero para dos personas. En este caso se calcula la distribución de probabilidad de cada participante, que es el coeficiente de mezcla aleatoria de sus estrategias.
Ningún proceso comercial exitoso en el mundo es posible sin optimización. Hay muchos algoritmos de optimización disponibles. Algunos métodos solo son adecuados para ciertos tipos de problemas. Es importante poder reconocer sus características y seleccionar el método de solución adecuado.
