Programación lineal 101

Programación lineal

En Investigación Operativa (OR) como la programación lineal, modelar un problema consiste en identificar:

• variables intrínsecas (incógnitas)
• las diversas restricciones a las que están sujetas estas variables
• el objetivo objetivo (mejoramiento) llamada función Meta.

En un problema de programación lineal (LP), las restricciones y el objetivo son funciones lineales de las variables. También conocido como programa lineal. Se denotan de la siguiente manera (forma canónica escarpado):

Maximizar	vsT X
Sujeto a	Hacha ≤ b
	x ≥ 0

donde x es el vector de variables (X₁, …, X_no), vs y B son vectores de coeficientes, PARA una matriz de coeficientes de tamaño m * n, y ^T la transposición (vector de columna en lugar de vector de fila, por ejemplo). Las desigualdades Hacha ≤ b y x ≥ 0 (positividad de las variables) son restricciones. la campo de definición formado es un politopo convexo. Se dice que el programa lineal está en forma estándar si implica restricciones de igualdad.

Positividad de variables. Si en el contexto, tenemos un límite inferior distinto de cero x ≥ k, solo pregunta y = xk y y ≥ 0. Si no hay un límite inferior, siempre podemos establecer x = yz con y ≥ 0 y z ≥ 0.

Cualquier problema estándar se puede escribir canónicamente y viceversa. La restricción de igualdad se descompone en dos restricciones de desigualdad. Una restricción de desigualdad se escribe en forma de igualdad agregando un variable de holgura.

Se dice que una solución x' es factible si satisface todas las restricciones.

En resumen, la programación lineal se compone de cuatro elementos:

1. variables de decisión;
2. una función objetiva;
3. limitaciones de recursos;
4. restricciones de "tipo".

Para formular un problema a partir de una especificación, se deben seguir en orden los cuatro puntos anteriores.

Ejemplo. Considere una fábrica que produce dos tipos de teclados que generan £ 50 y £ 70 cada uno. Para fabricar una unidad tipo 1 se necesitan 40 min de mano de obra y 20 min de mecanizado. Para fabricar una unidad tipo 2 se necesitan 30 min de mano de obra y 30 min de mecanizado. La mano de obra trabaja 6 horas al día mientras que la máquina está disponible 8 horas al día. ¿Cuántas unidades de cada tipo se deben producir para maximizar las utilidades?

Programa lineal. Este problema se modela de acuerdo con el siguiente PL:

máximo 50x + 70y
SC 40x + 30y ≤ 360
20x + 30y ≤ 480
x, y≥ 0

Soluciones posibles

Solo pueden surgir cuatro casos:

1. Si el dominio de definición es nulo, el problema no es realizable;
2. de lo contrario: el óptimo no existe, el problema es ilimitado;
3. o: el problema tiene una solución óptima única que coincide con un punto extremo (un vértice) del dominio de definición;
4. o: el problema tiene infinidad de soluciones que forman una cara o un borde del dominio de definición.