Modelos matemáticos de problemas de programación lineal

Los componentes del modelo matemático

La base para resolver problemas económicos son los modelos matemáticos.

El modelo matemático del problema es el conjunto de relaciones matemáticas que describen la esencia del problema.

La compilación de un modelo matemático incluye:

• elección de variables de tareas
• compilación de un sistema de limitaciones
• elección de la función objetivo

Los problemas variables son las cantidades X1, X2, Xn, que caracterizan por completo el proceso económico. Por lo general, están escritos en forma de un vector: X = (X ₁ , X ₂ , ..., X _n ).

Un sistema de restricciones es un conjunto de ecuaciones y desigualdades que describen los recursos limitados en el problema bajo consideración.

La función objetiva del problema se denomina función de las variables de la tarea, que caracteriza la calidad de la tarea y la parte más importante de la cual se debe encontrar.

En el caso general, el problema de programación lineal se puede escribir de esta forma:

Esta entrada significa lo siguiente: encuentre el extremo de la función objetivo (1) y las variables correspondientes X = (X ₁ , X ₂ , ..., X _n ) bajo la condición de que estas variables satisfagan el sistema de restricciones (2) y las condiciones de no negatividad (3) .

Una solución (plan) admisible de un problema de programación lineal es cualquier vector n-dimensional X = (X ₁ , X ₂ , ..., X _n ) que satisfaga el sistema de restricciones y las condiciones de no negatividad.

El conjunto de soluciones admisibles (planes) del problema forma el dominio de soluciones admisibles (ODR).

La solución (plan) óptima de un problema de programación lineal es una solución (plan) admisible del problema, en la cual la función objetivo alcanza un extremo.

Ejemplo de compilación de un modelo matemático

La tarea de usar recursos (materias primas)

Condición: Para la producción de n tipos de productos, se usan m tipos de recursos. Escribe un modelo matemático.

Conocido:

• b _i (i = 1,2,3, ..., m) - las reservas de cada tipo de recurso i-ésimo;
• a _ij (i = 1,2,3, ..., m; j = 1,2,3, ..., n) es el costo de cada tipo de recurso i-ésimo por unidad de volumen del j-ésimo producto;
• c _j (j = 1,2,3, ..., n) - ganancia de la venta de una unidad de volumen del tipo j-ésimo de productos.

Se requiere elaborar un plan para la producción de productos, que proporcione el máximo beneficio para las limitaciones dadas en los recursos (materias primas).

Solución:

Introducimos el vector de las variables X = (X ₁ , X ₂ , ..., X _n ), donde x _j (j = 1,2, ..., n) es el volumen de salida del producto j-ésimo.

Los costos del i-ésimo tipo de recurso para la producción de este volumen x _j son iguales a _ij x _j , por lo que la restricción en el uso de recursos para la producción de todo tipo de productos tiene la forma:
El beneficio de la realización del tipo de salida j-ésimo es c _j x _j , por lo tanto, la función objetivo es igual a:

Respuesta : el modelo matemático se ve así:

La forma canónica del problema de programación lineal

En general, el problema de programación lineal está escrito de tal manera que las restricciones son tanto ecuaciones como desigualdades, y las variables pueden ser no negativas o arbitrariamente variables.

En el caso en que todas las restricciones sean ecuaciones y todas las variables satisfagan la condición de no negatividad, el problema de programación lineal se llama canónico.

Puede representarse en registros de coordenadas, vectores y matrices.

El problema de programación lineal canónica en la grabación de coordenadas es:

El problema de programación lineal canónica en la notación de matriz es:

Aquí:

• A es la matriz de los coeficientes del sistema de ecuaciones
• X es la matriz-columna de las variables del problema
• Ao es la columna de la matriz de los lados derechos del sistema de restricciones

A menudo se usan problemas de programación lineal, llamados simétricos, que en las entradas de la matriz tienen la forma:

Reducción del problema de programación lineal general a la forma canónica

En la mayoría de los métodos para resolver problemas de programación lineal, se supone que el sistema de restricción consiste en ecuaciones y las condiciones naturales para la no negatividad de las variables. Sin embargo, cuando se elaboran modelos de problemas económicos, las restricciones se forman principalmente en forma de un sistema de desigualdades, por lo que es necesario poder pasar de un sistema de desigualdades a un sistema de ecuaciones.

Esto se puede hacer de la siguiente manera:

Tomamos la desigualdad lineal a ₁ x ₁ + a ₂ x ₂ + ... + a _n x _n ≤b y agregamos a su lado izquierdo un cierto valor x _{n + 1} , de modo que la desigualdad se convierte en la igualdad a ₁ x ₁ + a ₂ x ₂ + ... + a _n x _n + x _{n + 1} = b. En este caso, el valor dado de x _{n + 1} no es negativo.

Consideremos todo en un ejemplo.

Ejemplo 26.1

Para reducir el problema de la programación lineal a la forma canónica:

Solución:
Pasamos ahora al problema de encontrar el máximo de la función objetivo.
Para hacer esto, cambiamos los signos de los coeficientes de la función objetivo.
Para transformar las desigualdades segunda y tercera del sistema de restricciones en ecuaciones, introducimos variables adicionales no negativas x ₄ x ₅ (en el modelo matemático, esta operación está marcada con la letra D).
La variable x ₄ se introduce en el lado izquierdo de la segunda desigualdad con el signo más, ya que la desigualdad tiene la forma "≤".
La variable x ₅ se ingresa en el lado izquierdo de la tercera desigualdad con un signo "-", ya que la desigualdad tiene la forma "≥".
En la función objetivo, las variables x ₄ x ₅ se ingresan con un coeficiente. igual a cero.
Anotamos el problema en la forma canónica: