Programación lineal

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 de destino (optimización) llamado función de objetivo.

En un problema de programación lineal (PL), las restricciones y el objetivo son funciones lineales de las variables. También hablamos de un programa lineal. Se indican de la siguiente manera (forma canónica pura):

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 limitaciones. El dominio de definición definido es un politopo convexo. Se dice que el programa lineal está en forma estándar si se trata de 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 de forma canónica y viceversa. La restricción de igualdad se divide en dos restricciones de desigualdad. Una restricción de desigualdad se escribe en forma de igualdad agregando una variable de diferencia.

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
es_ESES
A los bloggers de %d les gusta esto: