Programación lineal soluciones óptimas permitidas. La investigación de operaciones

Considere la tarea básica de la programación lineal (OZLP): encontrar valores no negativos de variables X1, X2, ..., XN, satisfactoria M condiciones de M. - Ecualidades

y pagando a la función lineal máxima de estas variables

Para simplificar, asuma que todas las condiciones (1) son linealmente independientes (r \u003d m), y discutiremos en este supuesto.

Llamamos a la solución permisible de OZLP. Cualquier combinación de valores no negativos X1, X2, ..., XN, satisfactoria condiciones (1). Actimal, luego de las soluciones permisibles que pagan una función (2) a un máximo. Se requiere encontrar la solución óptima.

¿Esta tarea siempre tiene una solución? No, no siempre.

ZLP no es resuelto (sin solución óptima):

Debido a la incompletitud del sistema de restricciones. Esos. El sistema no tiene una solución como se muestra en la Figura 1.

Figura 1 - Incompletitud del sistema de restricciones.

Debido a la ilimitación de la función objetivo en una variedad de soluciones. En otras palabras, al resolver el ZLP en MAX, el valor de la función objetivo tiende al infinito, y en el caso de ZLP en minus, a menos del infinito, como se muestra en la Figura 2.

Figura 2 - Función objetivo ilimitada en una variedad de soluciones

ZLP es soluble:

Muchas soluciones consisten en un punto. Es óptimo, como se muestra en la Figura 3.

Figura 3 - Muchas soluciones consisten en un punto.

La única decisión óptima del ZLP. Directo, correspondiente a la función objetivo en la posición de límite se interseca con muchas soluciones en un punto, como se muestra en la Figura 4.

Figura 4 - Solución óptima única

La decisión óptima del ZLP no es la única. Vector N es perpendicular a uno de los lados del conjunto de soluciones. En este caso, el óptimo es cualquier punto en el segmento AB, como se muestra en la Figura 5.

Figura 5 - La solución óptima no es la única.

Solución de tareas de programación lineales Método simplex

SimpleX-Método: un algoritmo para resolver el problema de LP, que implementa la fuerza bruta de los puntos angulares de las soluciones válidas en la dirección de mejorar el valor de la función de destino S. simplex-método es el principal en la programación lineal.

El uso de este método en el proyecto de graduación para resolver el problema de LP se debe a los siguientes factores:

El método es universal, aplicable a cualquier tarea de programación lineal en forma canónica;

La naturaleza algorítmica del método permite programar con éxito e implementarlo utilizando medios técnicos.

El extremo de la función objetivo siempre se logra en los puntos angulares del área de soluciones permisibles. En primer lugar, existe alguna solución inicial (referencia) permisible, es decir, Cualquier punto angular del área de soluciones permisibles. El procedimiento del método le permite responder la pregunta de si esta solución es óptima. Si "SÍ", entonces la tarea se resuelve. Si "NO", luego la transición al punto angular adyacente del área de soluciones permisibles, donde se mejora el valor de la función objetivo. El proceso de extinción de puntos angulares de las soluciones válidas se repite hasta que se encuentra el punto en el que el extremo de la función objetivo.

Dado que el número de vértices del poliedro es limitado, entonces para el número final de pasos está garantizado para encontrar el valor óptimo o establecer el hecho de que la tarea es insoluble.

El sistema de restricciones aquí es un sistema de ecuaciones lineales en las que el número de más desconocido que el número de ecuaciones. Si el rango del sistema es igual, es posible elegir un desconocido, que se expresan a través del resto de lo desconocido. Para la certeza, generalmente se cree que la primera, en fila, se seleccionan las incógnitas. Estos desconocidos (variables) se llaman básicos, el resto son gratuitos. El número de variables básicas es siempre igual al número de restricciones.

Asignación de ciertos valores con variables libres y calculando los valores de la básica (expresada a través de libre), se obtienen diversas soluciones del sistema de límite. De particular interés son las soluciones obtenidas en el caso donde las variables libres son cero. Tales decisiones se denominan básicas. La solución básica se denomina solución de base válida o solución de referencia si los valores de las variables son no negativas. Cumple con todas las restricciones.

Tener un sistema de restricciones, encontrar cualquier solución básica a este sistema. Si la primera solución de base resultó ser permisible, entonces verifíquelo en la optimalidad. Si no es óptimo, entonces se realiza la transición a otra solución de base válida.

El método simplex garantiza que la nueva solución sea una forma lineal si no alcanza el óptimo, se acercará a él. Con una nueva solución de base permisible, hacen lo mismo hasta que encuentran una solución que sea óptima.

Si la primera solución de base no es válida, luego se realiza la transición a otras soluciones básicas, mientras que en algún paso de las soluciones, la solución básica estará permitida, o se puede concluir que las restricciones del sistema de restricciones.

Por lo tanto, el uso del método simplex se desintegra en dos etapas:

Encontrar una solución básica permisible para un sistema de restricciones o establecer el hecho de su incompletitud;

Encontrar la solución óptima en caso de compatibilidad de un sistema de restricciones.

El algoritmo de transición a la siguiente solución permisible es la siguiente:

En la fila de los coeficientes de la función de destino, se selecciona el número negativo más pequeño al encontrar un máximo. El número de secuencia del coeficiente es. Si no hay tal, la solución de base inicial es óptima;

Entre los elementos de la matriz con el número de columna (esta columna se llama el maestro o permisible) se seleccionan elementos positivos. Si no hay tal, la función objetivo es ilimitada en el área de valores permisibles de las variables y la tarea de soluciones no tiene;

Entre los elementos seleccionados de la columna Master, la matriz se selecciona por la para la cual la proporción del miembro gratuito correspondiente a este elemento es mínimo. Este elemento se llama el principal, y la cadena en la que está liderando;

La variable básica correspondiente a la cadena del elemento maestro debe traducirse a la descarga de la libre, y la variable libre correspondiente a la columna del elemento maestro se introduce en el número de BASIC. Se construye una nueva solución, que contiene nuevos números de variables básicas.

Las condiciones para la optimalidad del plan para resolver el problema al máximo: entre los coeficientes de la función objetivo no hay elementos negativos.

Formulación general del problema de la programación lineal (ZLP). Ejemplos de ZLP

La programación lineal es la dirección de las matemáticas, que estudia los métodos para resolver tareas extremas, que se caracterizan por una dependencia lineal entre las variables y el criterio de optimalidad lineal. Algunas palabras sobre el término es la programación lineal. Requiere la comprensión adecuada. En este caso, la programación es, por supuesto, no hacer programas de computadora. La programación aquí debe interpretarse como planificación, formación de planes, desarrollando un programa de acción. Las tareas matemáticas de la programación lineal incluyen estudios de producción específica y situaciones económicas, que se interpretan en uno u otro como problemas de uso óptimo de recursos limitados. La gama de tareas resueltas con métodos de programación lineales es bastante amplia. Esto, por ejemplo:

• - la tarea del uso óptimo de los recursos en la planificación industrial;
• - la tarea de mezclas (planificar la composición de los productos);
• - la tarea de encontrar una combinación óptima de varios tipos de productos para almacenamiento en almacenes (gestión del inventario y "mochila");
• - Tareas de transporte (análisis de la colocación de la empresa, movimiento de mercancías). La programación lineal es la sección más diseñada y ampliamente utilizada de la programación matemática (además, aquí incluye: Programación de enteros, dinámicos, no lineales, paramétricos). Esto se explica de la siguiente manera:
• - Los modelos matemáticos de una gran cantidad de problemas económicos son lineales en relación con las variables deseadas;
• - Este tipo de tarea es actualmente estudiada. Para ello, se han desarrollado métodos especiales, con los que se resuelven estas tareas y los programas correspondientes para las computadoras;
• - Muchas tareas de programación lineales, que se resuelven, se encuentran en todo uso;
• - Algunas tareas que no son lineales en la formulación inicial, después de que una serie de restricciones adicionales y suposiciones pueden volverse lineales o se pueden administrar a esa forma que pueden resolverse mediante métodos de programación lineales. El modelo económico y matemático de cualquier tarea de programación lineal incluye: la función objetivo, se requiere el valor óptimo (máximo o mínimo); limitaciones en forma de un sistema de ecuaciones o desigualdades lineales; Requisito de no negatividad de las variables. En general, el modelo está escrito de la siguiente manera:
• - Característica objetivo:

C1x1 + C2X2 + ... + CNXN\u003e MAX (MIN); - Restricciones:

a11x1 + A12x2 + ... + A1NXN (? \u003d?) B1,

a21x1 + A22X2 + ... + A2NXN (? \u003d?) B2

am1x1 + am2x2 + ... + amnxn (? \u003d?) BM;

Requisito de no negatividad:

En este caso, AIJ, BI, CJ () se le da valores permanentes. La tarea es encontrar el valor óptimo de la función (2.1) bajo la observancia de las restricciones (2.2) y (2.3). El sistema de límite (2.2) se denomina limitaciones funcionales del problema, y \u200b\u200blas limitaciones (2.3) son directas. El vector que satisface las restricciones (2.2) y (2.3) se denomina solución válida (plan) de una tarea de programación lineal. El plan en el que la función (2.1) alcanza su valor máximo (mínimo), se llama óptimo.

A continuación, damos ejemplos de algunas tareas típicas resueltas con métodos de programación lineales. Tales tareas tienen un contenido económico real. Ahora solo los formularemos en términos de ZLP, y consideraremos los métodos para resolver tales tareas a continuación.

1. La tarea del uso óptimo de los recursos durante la planificación de la producción. El significado general de las tareas de esta clase se reduce a lo siguiente. La compañía produce n de varios productos. Porque su producción requiere M de varios tipos de recursos (materias primas, materiales, horas de trabajo, etc.). Los recursos son limitados, sus acciones en el período planificado son, respectivamente, B1, B2, ..., BM de unidades condicionales. También se conocen los coeficientes tecnológicos de AIJ, que muestran cuántas unidades de los recursos I-TA se requieren para la producción de una unidad de producto de tipo JT (). El beneficio obtenido por la empresa al implementar el producto del Espécimen J-TH es CJ. En el período planificado, los valores de los valores de AIJ, BI y CJ permanecen constantes. Se requiere que compile dicho plan de producción, con la implementación de la cual el beneficio del Departamento sería el más grande. A continuación, le damos un ejemplo simple de la tarea de esta clase.

La compañía se especializa en la liberación de clubes de hockey y conjuntos de ajedrez. Cada club trae ganancias de $ 2, y cada conjunto de ajedrez está en la cantidad de $ 4. Se tarda cuatro horas de operación en el sitio A y dos horas de operación en el Sitio B. El conjunto de ajedrez se fabrica con el costo de las seis horas en la sección A, a las seis en punto en la sección B y una hora en la sección C. Capacidad de producción disponible A es de 120 N -Cakes por día, parcela en - 72 n-hora y parcela C - 10 N-HORAS. ¿Cuántas llaves y kits de ajedrez deben producir una empresa diariamente para obtener los máximos beneficios?

Las condiciones de las tareas de clase especificadas a menudo se presentan en forma tabular (consulte la Tabla 2.1).

Para esta condición, formulamos la tarea de la programación lineal. Denote: X1: la cantidad de clubes de hockey producidos diariamente, X2 es el número de conjuntos de ajedrez producidos diariamente. FORMULACIÓN ZLP:

4x1 + 6x2? 120,

Enfatizamos que cada desigualdad en el sistema de restricciones funcionales corresponde en este caso a uno u otro sitio de producción, a saber: la primera sección A, la segunda sección B, la tercera: la P. S. S.

El sistema de variables en la tarea de optimizar la estructura del área de siembra teniendo en cuenta las rotaciones de cultivos.

La tarea general de la programación lineal (OZLP) está formulada de la siguiente manera: encontrar tareas variables x. 1 , x. 2 , ..., x. N, que proporcionan un extremo de la función objetivo.

Una solución permisible (plan) de la tarea de programación lineal (ZLP) se llama cualquier nORTE.- Vector dimensional X.=(x. 1 , x. 2 , ..., x. n), satisfaciendo el sistema de restricciones de igualdades y desigualdades. Muchas soluciones de tareas válidas forman un área de soluciones permisibles. D..

La solución óptima (plan) de la tarea de la programación lineal se denomina una solución permitida en la que la función objetivo Z.(X.) Alcanza extremo.

El problema canónico de la programación lineal (KZLP) tiene la forma.

(1.2)

Se diferencia de OZDP porque su sistema de límite es un sistema de solo ecuaciones y todas las variables no negativas.

Trayendo OZLP al tipo canónico ZLP:

Para reemplazar el problema inicial de minimizar la tarea de maximización (o por el contrario, la tarea de maximización para el problema de la minimización) es una función bastante objetivo para multiplicarse a "-1" y busque una función máxima (mínima) obtenida;

Si hay desigualdades entre las restricciones, introduciendo variables adicionales no negativas x. N +1 ≥ 0 se transforman en la igualdad:

desigualdad uNA. I 1. x. 1 +…+uNA. EN. x. n ≥ b. Soy reemplazado por la igualdad. uNA. I 1. x. 1 +…+uNA. EN. x. N +. x. N +1 \u003d. b. I,

desigualdad uNA. I 1. x. 1 +…+uNA. EN. x. N ≤ b. Soy reemplazado por la igualdad. uNA. I 1. x. 1 +…+uNA. EN. x. N +. x. N +1 \u003d. b. I;

Si alguna variable x. k. no hay restricciones en el signo, se reemplaza (en la función objetivo y en todas las limitaciones) la diferencia entre dos nuevas variables no negativas: x. k. = x." k. – x.” k. , dónde x." k. ≥ 0. x.” k. ≥ 0.

Método gráfico para resolver ZLP con dos desconocidos

ZLP con dos incógnitas tiene la forma:

El método se basa en la posibilidad de una imagen gráfica del área de soluciones permisibles y encontrar una solución óptima entre ellos.

El área de soluciones permisibles (ADR) del problema es un polígono convexo y se construye como una intersección (parte general) de las soluciones de cada una de la desigualdad de las limitaciones del problema.

Región de resolución de desigualdad uNA. I 1. x. 1 +uNA. I 2. x. 2 ≤ b. i es uno de los dos medios aviones a los que directamente uNA. I 1. x. 1 +uNA. I 2. x. 2 = b. Yo corresponde a esta desigualdad divide el plano de coordenadas. Para determinar cuál de los dos semi-posiciones es el área de soluciones, hay suficientes coordenadas de cualquier punto que no se encuentre en la línea recta que se divide para sustituir en la desigualdad:

Si la desigualdad es válida, el área de soluciones es un medio plano que contiene este punto;

Si la desigualdad no es justa, el área de soluciones es un medio plano que no contiene este punto.

Para averiguar entre las soluciones válidas, se utilizan los niveles óptimos.

Línea de nivel llamada recta de 1 x. 1 +de 2 x. 2 = l., dónde l.= const, en el que la función de tarea objetivo toma un valor constante. Todas las líneas de nivel son paralelas entre sí.

Función objetivo de gradiente graduado Z.(X.) Especifica el vector de lo normal. C. = (c. 1 , c. 2) Líneas de nivel. La función objetivo en las líneas de nivel aumenta si las líneas de nivel se mueven en la dirección de su normal, y disminuye en la dirección opuesta.

El Direct de referencia se denomina línea de nivel que tiene al menos un punto común con ADR y con respecto a la cual la ORD está en uno de los medios aviones. La tarea ODR no tiene más de dos líneas rectas de referencia.

La solución óptima del ZLP se encuentra en la referencia directa en el punto angular del polígono ADR. ZLP tiene una solución única si la referencia directa pasa a través de un punto angular del ADR, un conjunto infinito de soluciones, si la referencia directa pasa a través del borde del polígono ADR. El ZLP no tiene una solución si el ADR es un conjunto en blanco (cuando el sistema de restricciones es inconsistente) y si el ADR está ilimitado en la dirección del extremo (la función de destino es ilimitada).

Algoritmo del método gráfico de resolver ZLP con dos incógnitas:

Construir ADR.

Construir vector normal C. = (c. 1 , c. 2) y línea de nivel de 1 x. 1 +de 2 x. 2 \u003d 0, pasando por el origen de las coordenadas y vector perpendicular. DE.

Mueva la línea de nivel a la referencia directamente en la dirección del vector DE En el problema máximo, o en la dirección opuesta, en la tarea mínima.

Si, al mover la línea de nivel en la dirección de Extrema, ORD entra en el infinito, la ZLP no tiene una solución debido a la función objetivo ilimitada.

Si el ZLP tiene una solución óptima, para encontrarlo para resolver juntos la ecuación de ADR directo, limitante y que tiene puntos comunes con una referencia directa. Si el extremo se logra en dos puntos angulares, ZLP tiene soluciones de conjunto infinitas que pertenecen al borde del ODR, limitado por estos puntos angulares. En este caso, se calculan las coordenadas de ambos puntos angulares.

Calcule el valor de la función de destino en el punto extremo.

Simplex-método de decisión del zllp

El método simplex se basa en las siguientes posiciones:

Agregar problema de la programación lineal es un conjunto convexo con un número finito de puntos angulares;

La solución óptima del ZLP es uno de los puntos angulares del ADR. Los puntos angulares del ODR presentes álgebraicamente algunas soluciones básicas (referencia) del sistema de restricción ZLP.

Solución básica (referencia) de la ZLL llamada solución tan permisible X. 0 =( X. 10 , x. 20 , ..., x. m 0, 0, ... 0), para los cuales los vectores de las condiciones (columnas de coeficientes en desconocidos en el sistema de restricciones) son linealmente independientes.

Coordenadas no cero x. 10 , x. 20 , ..., x. M 0 soluciones X. 0 se llaman variables básicas, las coordenadas restantes de la solución X. 0 - Variables libres. El número de coordenadas no cero de la solución de referencia no puede ser más rango r. Sistemas de restricción ZLP (el número de ecuaciones linealmente independientes en el sistema de restricción VLP). A continuación, creemos que el sistema de limitaciones de la ZLP consiste en ecuaciones linealmente independientes, es decir, r. = mETRO..

El significado del método simplex consiste en una transición específica de una solución de referencia de la ZLP a otra (es decir, de un punto angular del ADR a otro) en la dirección del extremo y consiste en la secuencia de etapas:

Encontrar una solución de referencia inicial;

Llevar a cabo la transición de una solución de referencia a otra;

Determine el criterio para lograr la solución óptima o hacer una conclusión sobre la ausencia de una solución.

Ejecución del algoritmoMÉTODO DE SIMBULANCIA ZLP

El algoritmo del método simplex transica de una solución de referencia de la ZLP a otra en la dirección del extremo de la función objetivo.

Deje que la ZLP estén establecidos en forma canónica (1.2) y la condición está satisfecha

b. I ≥ 0, i.=1,2,…,mETRO., (1.3)

la proporción (1.3) siempre se puede realizar, el número de la ecuación correspondiente en "-1" en caso de negatividad b. I. También creemos que el sistema de ecuaciones en las limitaciones del problema (1.2) es linealmente independiente y tiene rango r. = mETRO.. En este caso, el vector de la solución de referencia tiene mETRO. coordenadas distintas de cero.

Deje que el problema inicial (1.2), (1.3), se muestran al formulario donde las variables básicas x. 1 , x. 2 , ..., x. m expresado a través de variables libres x. mETRO. + 1 , x. mETRO. + 2 , ..., x. NORTE.

(1.4)

Basado en estos ratios, construiremos una tabla 1.

Tabla 1.

La tabla 1 se llama una tabla simplex. Todas las transformaciones adicionales están asociadas con cambios en el contenido de esta tabla.

Algoritmo S.método implex:

1. En la última línea. Z. Las tablas simples en la tarea mínima son el elemento positivo más pequeño (en el problema máximo, el elemento negativo más pequeño), sin contar el miembro libre. Una columna enseñada que este elemento se llama permisible.

2. Calcule la proporción de miembros libres a elementos positivos de la columna de resolución (Simplex-Actitud). Encuentre los más pequeños de estos simples: relaciones, corresponde a la cadena de resolución.

3. En la intersección de la cadena que permite y la columna de resolución es el elemento que permite.

4. Si hay un tamaño ligeramente idéntico de la relación simplex, luego elige alguno de ellos. Lo mismo se aplica a los elementos positivos de la última línea de Simleks - Tablas.

5. Después de encontrar el elemento de resolución, vaya a la siguiente tabla. Variables desconocidas correspondientes a la resolución y cambio de columna en los lugares. En este caso, la variable básica se convierte en una variable libre y viceversa. Simplex - La tabla se convierte de la siguiente manera (Tabla 2):

Tabla 2

6. El elemento de la Tabla 2 correspondiente al elemento de resolución de la Tabla 1 es igual al tamaño inverso del elemento de resolución.

7. Los elementos de la cadena de la Tabla 2 correspondientes a los elementos de la línea de resolución de la Tabla 1 se obtienen dividiendo los elementos correspondientes de la Tabla 1 para permitir el artículo.

8. Los elementos de la columna de la Tabla 2 correspondientes a los elementos de la columna de resolución de la Tabla 1, se obtienen dividiendo los elementos correspondientes de la Tabla 1 para permitir el elemento y se toman con el signo opuesto.

9. Los elementos restantes se calculan por regla de rectángulo: dibuja mentalmente un rectángulo en la Tabla 1, un vértice de que coincide con el elemento de resolución (RE), y el otro con el elemento que buscamos; Denote el elemento en la nueva Tabla 2 a (NE), y el elemento que enfrenta el mismo lugar en la antigua Tabla 1: a través de (SE). Los dos vértices restantes A y para complementar la forma al rectángulo. Luego, el elemento NE deseado de la Tabla 2 es NE \u003d SE - A * B / RE.

10. Criterio de optimalidad. Tan pronto como esté la tabla, en la que todos los elementos son negativos en la tarea mínima en la tarea mínima (en el problema máximo, todos los elementos son positivos), se cree que se encuentra el extremo. El valor óptimo de la función objetivo es igual a un miembro libre en la cadena Z, y la solución óptima está determinada por miembros libres en variables básicas. Todas las variables libres se basan igual a cero.

11. Si todos los elementos son negativos en la columna de resolución, la tarea no tiene soluciones (no se logra un mínimo).

Método de soluciones de base artificial ZLP

El algoritmo del método simplex es aplicable si se muestra alguna solución de referencia de la ZLP, que se asigna, se muestra que el ZLP inicial (1.2) se forma (1.4). El método de base artificial ofrece un procedimiento para construir una solución de referencia de este tipo.

El método de base artificial se basa en la introducción de variables de base artificial. y 1 , y 2 ,…, y M, con el cual el sistema de limitaciones de ZLP (2.2)

(1.5)

se puede convertir en la mente

(1.6)

Los sistemas (1.5) y (1.6) serán equivalentes en el caso de que todos y i. será cero. Como antes, creemos que todos b. i. ≥ 0. Con el fin de w. i. eran iguales 0, debemos convertir la tarea para que todas las variables de base artificial y i. cambiado a variables libres. Dicha transición puede ser realizada por el algoritmo del método del método relativo a la función objetivo adicional.

F.(y) = y 1 + y 2 + ... + y M \u003d. d. 0 – (d. 1 x. 1 + D. 2 x. 2 +…+d. NORTE. x. norte). (2.7)

La tabla Simplex Simplex para este método tiene el formulario.

Al principio, la tabla simplex se convierte en relación con la función objetivo. F.(y) Antes de obtener una solución de referencia. La solución de referencia encontró cuando se realizó el siguiente criterio: F.(y) \u003d 0 y todas las variables artificiales w. i. traducido en variables libres. Luego, desde la tabla simplex se elabora la cadena para F.(y) y columnas para w. i. y resolver la tarea de la función objetivo inicial Z.(x.) Antes de obtener la solución óptima.

La tarea de la programación lineal (ZLP) es la tarea de encontrar el valor más grande (o más pequeño) de la función lineal en el conjunto convexo multifacético.

El método simplex es un método para resolver un problema de programación lineal. La esencia del método es encontrar el plan admisible inicial, y en la mejora posterior del plan hasta el valor máximo (o mínimo) de la función objetivo en este conjunto multifacético convexo o defectuoso de la insolutividad del problema.

Considere la siguiente tarea de programación lineal en forma canónica:

(1)

(2)

(3)

Método de base artificial.

Como se agregó anteriormente, para la tarea registrada en forma canónica, si entre los vectores de columnas de matriz UNA. hay mETRO. Individual y lineal independiente, puede especificar directamente el plan de referencia. Sin embargo, para muchas tareas de programación lineales registradas en forma canónica y tener planes de referencia, entre los vectores de columnas de matriz. UNA. No siempre hay mETRO. Soltero y linealmente independiente. Considere tal tarea:

Deja que se necesite para encontrar la máxima función.

bajo condiciones

donde estan los primeros nORTE. Elementos de ceros. Variables Llamado artificial. Vectores Columnas

(28)

formar la llamada base artificial mETRO.- Espacio de vector dimensional.

Dado que la tarea ampliada tiene un plan de referencia, entonces su solución se puede encontrar por el método simplex.

Teorema 4. Si en un plan óptimo. Tarea extendida (24) - (26) Los valores de las variables artificiales. T. Es el plan óptimo del problema (21) - (23).

Por lo tanto, si en el plan óptimo de una tarea extendida, los valores de las variables artificiales son cero, entonces se obtuvo el plan óptimo de la tarea original. Dediquemos con más detalle a encontrar una decisión de una tarea extendida.

El valor de la función objetivo durante el plan de referencia (27):

Nos damos cuenta que F (x) y constar de dos partes independientes, una de las cuales depende de METRO.Y el otro no lo es.

Despues de calcular F (x) Y sus valores, así como los datos de origen de la tarea extendida, se ingresan en la tabla simplex, como se muestra arriba. La diferencia se encuentra solo en que esta tabla contiene una línea más que la tabla Simplex habitual. Al mismo tiempo en ( mETRO.+1) -La cadena colocada coeficientes que no contienen METRO.y en ( mETRO.+2) -t cadena - coeficientes cuando METRO..

Cuando se mueve de un plan de referencia a otro, el vector se introduce en la base, que corresponde al mayor en el valor absoluto del número negativo ( mETRO.+2) líneas. El vector artificial, excluido de la base, tiene sentido volver a ingresar la base. Al pasar a otro plan de referencia, puede suceder que no se excluyerá ninguno de los vectores artificiales de la base. Recálculo de la tabla simplex al cambiar de un plan de referencia a otro, se producen mediante las reglas habituales del simplex del método (ver más arriba).

El proceso iterativo conduce. mETRO.+2 fila hasta los elementos mETRO.+2 líneas correspondientes a las variables no será no negativo. Al mismo tiempo, si las variables artificiales están excluidas de la base, el plan encontrado del problema extendido corresponde a algún plan de referencia de la tarea original.

mETRO.+2 filas, columna x. 0 es negativo, la tarea inicial no tiene solución.

Si no, todas las variables artificiales están excluidas de la base y elemento. mETRO.+2 filas, columna x. 0 es cero, el plan de referencia del problema original es degenerado y la base contiene al menos uno de los vectores de una base artificial.

Si la tarea inicial contiene varios vectores individuales, entonces deben incluirse en la base artificial.

Si durante las iteraciones mETRO.+2 Cadena ya no contiene elementos negativos, entonces el proceso iterativo continúa con mETRO.+1 fila, hasta que el plan óptimo de una tarea extendida se encuentre o la insoluibilidad de la tarea.

Por lo tanto, el proceso de encontrar una solución de un problema de programación lineal (21) - (23) por el método de base artificial incluye las siguientes etapas principales:

• Haga una tarea extendida (24) - (26).
• Encuentre un plan de referencia de una tarea extendida.
• El uso del método simplex excluye los vectores artificiales de la base. Como resultado, encuentran el plan de referencia de la tarea inicial o solucione la intratabilidad.
• Uso del plan de base de la ZLP (21) - (23), o encuentra el plan óptimo de la tarea inicial, o se determina.

Para resolver tareas de programación lineales en línea, use la calculadora.

Componentes del modelo matemático.

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

Modelo matemático Las tareas se denominan una combinación de relaciones matemáticas que describen la esencia del problema.

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

• seleccione tareas variables
• elaboración de un sistema de restricciones.
• selección de función objetivo.

Tareas de variables Se llaman X1, X2, XN, que caracterizan completamente el proceso económico. Por lo general, están escritos en forma de un vector: x \u003d (x1, x2, ..., xn).

Restricciones del sistema Las tareas llaman al conjunto de ecuaciones y desigualdades que describen los recursos limitados en el problema en consideración.

Función de destino Las tareas llaman a la función de las tareas variables, que caracterizan la calidad de la tarea y cuyo extremo se puede encontrar.

En el caso general, la tarea de la programación lineal se puede registrar en este formulario:

Este registro significa lo siguiente: Encuentre el extremo de la función de destino (1) y las variables correspondientes x \u003d (x1, x2, ..., xn) se proporcionan que estas variables satisfacen el sistema de restricciones (2) y la no negatividad Condiciones (3).

Solución permisible (Plan) Las tareas de programación lineal se denominan cualquier vector N-Dimensional X \u003d (X1, X2, ..., XN) que satisfaga el sistema de restricciones y condiciones no negativas.

Muchas soluciones válidas (planes) se forman formularios Área de soluciones permisibles. (Ord).

Decisión óptima (plan) La tarea de la programación lineal se llama una solución (plan) permitida (plan), en la que la función objetivo alcanza extremo.

Un ejemplo de compilar un modelado matemático de uso de recursos (materias primas)

Condición: Para la fabricación de n tipos de productos, se utilizan especies de recursos M. Hacer un modelo matemático.

Conocido:

• bI (I \u003d 1,2,3, ..., M) - Stocks de cada tipo de recurso I-TH;
• aIJ (I \u003d 1,2,3, ..., M; J \u003d 1,2,3, ..., N) - El costo de cada tipo de recurso en la producción de una unidad del volumen. del producto jiff;
• cJ (J \u003d 1,2,3, ..., N) - Beneficio de la implementación de la unidad del volumen del tipo de productos Josh.

Se requiere que haga un plan para la producción de productos, lo que proporciona las máximas ganancias para recibir restricciones a los recursos (materias primas).

Decisión:

Presentamos el vector de variables x \u003d (x1, x2, ..., xn), donde xj (j \u003d 1,2, ..., n) es el volumen de producción del tipo de productos J-TH.

El costo de la vista I-TH del recurso para la fabricación de este volumen de productos XJ es igual a AIJXJ, por lo que la restricción en el uso de los recursos en la producción de todo tipo de productos es:
Las ganancias de la implementación de la vista J-Th de productos son CJXJ, por lo que la función objetivo es igual a:

Respuesta - El modelo matemático tiene la forma:

Forma canónica de problema de programación lineal.

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

En el caso, cuando todas las limitaciones sean ecuaciones y todas las variables satisfacen la condición de definición, se llama la tarea de la programación lineal canónico.

Se puede representar en el registro de coordenadas, vector y matriz.

La tarea canónica de la programación lineal en el registro de coordenadas tiene el formulario:

La tarea de programación lineal canónica en el registro de matriz tiene el formulario:

• A - Matriz de coeficientes del sistema de ecuaciones.
• X - Tareas variables de columna de matriz
• JSC - matriz-columna de las partes correctas del sistema de restricciones

De tareas particularmente utilizadas de la programación lineal, llamadas simétricas, que en el registro de matriz tienen el formulario:

Trayendo una tarea de programación lineal común a la forma canónica

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

Esto puede hacerse de la siguiente manera:

Tome la desigualdad lineal A1x1 + A2x2 + ... + ansn≤b y agregue un poco de xn + 1 a su parte izquierda, de modo que la desigualdad se convirtió en una igualdad A1x1 + A2x2 + ... + ansn + xn + 1 \u003d b. En este caso, este valor de XN + 1 no es aditivo.

Considera todo en el ejemplo.

Ejemplo 26.1.

Conduce al tipo canónico de la tarea de programación lineal:

Decisión:
Veamos a la tarea de buscar un máximo de la función objetivo.
Para hacer esto, cambie los signos de los coeficientes de la función de destino.
Para convertir la segunda y tercera desigualdad del sistema de restricciones en la ecuación, introducimos variables adicionales no negativas X4 X5 (en el modelo matemático, esta operación está marcada con la letra D).
La variable X4 se introduce en la parte izquierda de la segunda desigualdad con el signo "+", ya que la desigualdad es "≤".
La variable X5 se introduce en el lado izquierdo de la tercera desigualdad con el signo "-", ya que la desigualdad es "≥".
En la función objetivo, las variables X4 X5 se ingresan con el coeficiente. igual a cero.
Registre la tarea en la forma canónica: