A continuación se presentan cinco ejercicios clásicos de programación lineal y sus resultados:
Maximización de la ganancia en una empresa:
Un fabricante quiere maximizar su ganancia produciendo dos tipos de productos, A y B. Para producir una unidad del producto A, se necesitan 2 horas de trabajo y se obtiene una ganancia de $3. Para producir una unidad del producto B, se necesitan 3 horas de trabajo y se obtiene una ganancia de $2. La empresa solo tiene 400 horas disponibles para producir. ¿Cuántas unidades de cada producto deben producirse para maximizar la ganancia?
Solución:
La función a maximizar es: 3x + 2y, donde x es el número de unidades del producto A y y el número de unidades del producto B.
Los límites son: 2x + 3y ≤ 400 (por las horas disponibles) y x, y ≥ 0 (porque no se pueden producir unidades negativas).
El problema se puede resolver mediante el método gráfico, obteniendo los siguientes resultados:
x = 100 unidades
y = 133.3 unidades
La ganancia máxima es de $533.
Problema de asignación: dado un conjunto de tareas y un conjunto de trabajadores, asignar cada tarea a un trabajador de tal manera que se minimice el costo total.
Ejemplo:
Tareas: T1, T2, T3, T4
Trabajadores: W1, W2, W3
Costos:
| T1 | T2 | T3 | T4 |
W1| 2 | 6 | 7 | 5 |
W2| 3 | 4 | 8 | 6 |
W3| 5 | 7 | 3 | 2 |
Solución: asignar T1 a W1, T2 a W2, T3 a W3 y T4 a W1. El costo total sería 17
Problema del viajero de comercio: dado un conjunto de ciudades y las distancias entre ellas, encontrar el camino más corto para visitar todas las ciudades y regresar a la ciudad de origen.
Ejemplo:
Ciudades: C1, C2, C3, C4
Distancias (en millas):
| C1 | C2 | C3 | C4 |
C1| 0 | 2 | 5 | 7 |
C2| 2 | 0 | 4 | 1 |
C3| 5 | 4 | 0 | 6 |
C4| 7 | 1 | 6 | 0 |
Solución: visitar las ciudades en el siguiente orden: C1, C2, C4, C3, C1. La distancia total sería 14 millas.
Problema de transporte: dado un conjunto de fábricas y un conjunto de tiendas, determinar la cantidad de productos que deben ser enviados de cada fábrica a cada tienda para satisfacer la demanda de productos de cada tienda y minimizar el costo total.
Ejemplo:
Fábricas: F1, F2
Tiendas: T1, T2, T3
Demanda de productos:
| T1 | T2 | T3 |
F1| 2 | 3 | 1 |
F2| 1 | 2 | 3 |
Costos (por unidad):
| T1 | T2 | T3 |
F1| 3 | 4 | 5 |
F2| 4 | 3 | 6 |
Solución: enviar 2 unidades de F1 a T1, 3 unidades de F1 a T2, 1 unidad de F1 a T3, 1 unidad de F2 a T1 y 2 unidades de F2 a T2. El costo total sería 27.
Asignación de trabajos a trabajadores:
Una empresa quiere asignar trabajos a sus trabajadores de manera que maximice su productividad. Cada trabajador tiene una habilidad diferente para realizar cada tipo de trabajo, y se sabe cuánto tiempo se tarda en realizar cada trabajo. ¿Cuántos trabajos de cada tipo deben asignarse a cada trabajador para maximizar la productividad?
Solución:
La función a maximizar es: 2x + 3y + 4z, donde x, y y z representan el número de trabajos de cada tipo que se asignan a cada trabajador.
Los límites son: x + y + z ≤ 10 (por el número total de trabajos disponibles) y x, y, z ≥ 0 (porque no se pueden asignar trabajos negativos).
El problema se puede resolver mediante el método gráfico, obteniendo los siguientes resultados:
x = 2 trabajos
y = 4 trabajos
z = 4 trabajos
La productividad máxima es de 26
