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 (X1,…, Xno), 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 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, siga los cuatro puntos anteriores en orden.

Ejemplo. Considere una fábrica que produce dos tipos de teclados que ganan £ 50 y £ 70 cada uno. Para fabricar una unidad de tipo 1, se necesitan 40 minutos de mano de obra y 20 minutos de mecanizado. Para fabricar una unidad de tipo 2, se necesitan 30 minutos de mano de obra y 30 minutos 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 deben producirse para maximizar las ganancias?

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 factible;
  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.

programación lineal

Compartir, repartir