Programas lineales
Los programas lineales (LP) son una forma de usar ecuaciones para representar problemas que enfrentamos comúnmente, ya sea un problema cotidiano como, por ejemplo, cómo minimizar los costos de comestibles mientras nos aseguramos de tener todos los ingredientes para nuestras recetas o un problema de ingeniería complicado donde un La fábrica está tratando de maximizar las ganancias sin exceder la capacidad de las máquinas que tiene para fabricar sus productos. Luego, las ecuaciones se resuelven mediante varios métodos para encontrar una solución óptima (la decisión que maximizará / minimizará nuestro objetivo, sujeto a todas las restricciones).
Todos los LP comparten algunas características comunes:
- hay un objetivo (minimizar costos, maximizar ganancias)
- hay limitaciones (necesitamos hacer todas nuestras recetas, no se puede exceder la capacidad de cada máquina)
- las ecuaciones utilizadas para representar el objetivo y las restricciones son todas lineales
- hay un conjunto de decisiones a tomar (cuánto de cada ingrediente comprar, cuántos de cada tipo de widget fabricar)
Declaración general de un LP
Digamos que tenemos m variables de decisión y n restricciones. La declaración general de un LP se ve así:
 |
- x i son las variables de decisión
- c i y a i son coeficientes
- b j representa los valores máximos de las restricciones.
La última ecuación dice que es imposible tener valores negativos para las variables de decisión. (Desafortunadamente, no podemos comprar una cantidad negativa de azúcar para ahorrar dinero). Esto debería quedar un poco más claro con algunos ejemplos.
Tipos y ejemplos
Ya sea que estemos considerando decisiones en ingeniería, informática o fabricación, existen algunos tipos comunes de LP que se repiten con frecuencia. Todos se pueden representar mediante variaciones de la declaración general de un LP. Aquí dos de los tipos más comunes.
El problema del transporte
El problema de transporte se refiere al tipo de problema de decisión en el que intentamos suministrar artículos de un número determinado de fuentes a un número determinado de ubicaciones al costo mínimo.
 |
¿Qué universidades ofrecen programas en inglés en España?
A modo de ejemplo, imagina que hay w bodegas productoras de neumáticos y S tiendas que lo deseen. Cada almacén i puede hacer un máximo de unos i neumáticos. Y cada tienda j exige al menos d j neumáticos. El costo de envío del almacén i al almacén j es c ij . Y nuestra variable de decisión, x ij , es la cantidad de neumáticos enviados desde el almacén i al almacén j . El LP es:
 |
Probemos con un problema de transporte simple (dos almacenes y una tienda) que se puede resolver gráficamente para ver cómo funciona:
- El almacén n. ° 1 puede producir 20 neumáticos.
- El almacén n. ° 2 puede producir 10 neumáticos.
- tienda demanda 20 neumáticos
- el costo de envío desde el almacén n. ° 1 es de $ 4 / llanta
- el costo de envío desde el almacén n. ° 2 es de $ 2 / llanta
El LP es:
¿Qué es la Educación en Marketing? Definición, programas y ejemplos
 |
Esto se puede resolver gráficamente:
 |
La línea roja es la primera restricción (satisfacer la demanda), la línea verde es la segunda restricción (límite del almacén 1), la línea azul es la tercera restricción (límite del almacén 2) y el área sombreada son todas las soluciones factibles. El costo total se minimiza en el vértice A: $ 60, lo que significa que cada almacén envía 10 neumáticos.
El problema del flujo máximo
El problema de flujo máximo se refiere a la decisión en la que estamos tratando de maximizar la cantidad de objetos que movemos entre dos puntos y donde hay muchas formas diferentes de llegar de un punto al otro. Los ejemplos típicos son elegir la mejor ruta para mover el mayor número de camiones entre dos ubicaciones físicas o mover paquetes de datos entre computadoras.
Los objetos deben moverse de un nodo a otro entre los puntos y los bordes entre los nodos. Los bordes son las únicas formas permitidas de moverse entre los nodos y tienen diferentes capacidades. También tenemos que mantener el equilibrio del flujo , lo que significa que nos aseguramos de que nada se atasque en ninguno de los nodos. Hacemos esto estableciendo una restricción para decir que el número de objetos que fluyen hacia un nodo es igual al número que fluye hacia afuera. Para ver cómo se ve todo esto, hagamos un mapa simple de puntos y nodos y luego creemos el LP para maximizar el flujo entre los puntos. Primero, el mapa.
 |
El punto de partida (A) está en verde, el punto de destino (F) está en rojo y los nodos intermedios (BE) están en azul. Los bordes , que representan movimientos permitidos dentro y fuera de los nodos, son las delgadas líneas negras.
 |
El primer conjunto de restricciones dice que el número de objetos que se mueven sobre un borde no puede exceder la capacidad del borde. El segundo conjunto de restricciones son las restricciones de equilibrio de flujo . Las últimas ecuaciones dicen que es imposible tener valores negativos para las variables de decisión, lo que, en el problema de flujo máximo, significa que los objetos solo pueden moverse hacia adelante y no hacia atrás.
Resumen de la lección
Los programas lineales (LP) se pueden utilizar para representar y resolver problemas de decisión para encontrar la decisión óptima que maximizará (o minimizará) nuestro objetivo, sujeto a todas las restricciones. El problema del transporte es una forma común de LP en la que intentamos suministrar artículos de un número determinado de fuentes a un número determinado de ubicaciones al costo mínimo. El problema de flujo máximo es otra forma común de LP en la que intentamos maximizar la cantidad de objetos que movemos entre dos puntos, donde hay muchas formas diferentes de ir de un punto al otro.
Explora más sobre este tema
Selecciona un tema y sigue aprendiendo...
