Los más simples son los llamados modelos deterministas lineales. Se dan en forma de una forma lineal de variables de control ( X):

W = un 0 + a 1 X 1 + … + un k x k

bajo restricciones lineales de la forma

b 1 jx 1 + b 2 jx 2 + … + b kj x k ³ mamada , j = 1,…, q 1 ;

C 1 jx 1 + C 2 jx 2 + … + c kj x k = cj , j = 1,…, q 2 ;

d 1 jx 1 + d 2 jx 2 + … + d kj x k £ DJ , j = 1,…, q 3 .

Número total de restricciones m = q 1 + q 2 + q 3 puede exceder el número de variables (metro> k). Además, la condición de positividad de las variables ( x yo ³ 0).

La superficie de respuesta para el modelo lineal es hiperplano. Por ejemplo, considere un modelo lineal de dos variables de la siguiente forma:

W=–2X 1 –3X 2 (2.2)

bajo las siguientes restricciones

(2.3)

2X 1 + 3X 2 £ 18;

X 1 – 4X 2 £ 4;

–2X 1 + X 2 £ 2;

X 1 ³ 0; X 2 ³ 0.

Rango válido (ámbito de definición) OABCD para el modelo (2.2) está formado por las restricciones (2.3) (Fig. 2.2). La superficie de respuesta es un polígono plano. OA"B"C"D"(Figura 2.2, b).

Para una determinada relación de restricción, el conjunto de soluciones factibles puede estar ausente (vacío). Un ejemplo de un conjunto de este tipo se muestra en la Fig. 2.3. Directo C.A. Y sol limitar el rango de valores permitidos desde arriba. La tercera restricción corta la región de valores admisibles por debajo de la línea recta AB. Por lo tanto, no hay un área común que satisfaga las tres restricciones.

Los modelos lineales son bastante simples y por lo tanto, por un lado, implican una simplificación significativa del problema, y ​​por otro lado, permiten el desarrollo de métodos de solución simples y efectivos.

En el estudio de ADL, los modelos lineales se utilizan rara vez y casi exclusivamente en la descripción aproximada de problemas.

Los modelos lineales se pueden utilizar para la aproximación paso a paso de modelos no lineales (linealización del problema). Esta técnica es especialmente efectiva cuando se estudian áreas pequeñas del espacio estudiado. La representación de secciones individuales de la superficie de respuesta no lineal por un modelo lineal subyace grupo grande métodos de optimización, los llamados métodos con tácticas lineales.

El estudio de modelos lineales no es difícil. En particular, la influencia de cada una de las variables sobre las características del modelo de la forma

W = un 0 + a 1 X 1 + a 2 X 2 + …+ un k x k

viene dada por sus coeficientes:

, i = 1,…, k.

Para encontrar el óptimo del modelo lineal W opt desarrolló un método simplex eficiente.

Los modelos de costos más simples, considerados como un conjunto de costos incurridos, a veces se reducen a modelos lineales.

Un ejemplo de tal modelo es el clásico modelo de costo de transporte (problema de transporte)(Figura 2.4).

Disponible k puntos de producción
(i = 1,…, k) Y metro puntos de consumo
(j = 1,…, metro) de algún producto. La cantidad de producto producido en cada k puntos de producción, un yo; la cantidad de producto necesaria en cada metro puntos de consumo, mamada.

Se supone la igualdad de la producción y el consumo totales:

Cantidad de producto transportado desde i-ésimo punto de producción en j-ésimo punto de consumo, igual a xij; el costo de transportar una unidad de este producto - con ij.

Costo total de transporte CON se da s Modelo lineal:

bajo las siguientes restricciones

Los modelos lineales también incluyen modelos en forma de ecuaciones diferenciales lineales (derivadas ordinarias o parciales).

Ecuación diferencial ordinaria lineal norte el orden tiene la forma

Las condiciones iniciales se escriben como

Una ecuación diferencial parcial lineal tiene la forma

El modelo, dado como una ecuación diferencial parcial, incluye condiciones iniciales y de frontera (condiciones en la frontera del dominio de definición de la función F( t)).

2.3. Estudio del modelo matemático más simple
funcionamiento de un motor de turbina de gas

El motor de turbina de gas (GTE) es la principal planta de energía de los aviones modernos.

El esquema GTE tiene la forma que se muestra en la Fig. 2.5.

Aquí 1 – difusor de entrada; 2 - compresor; 3 - la cámara de combustión; 4 – turbina;
5 - boquilla de salida.

El ciclo de trabajo de GTE incluye las siguientes etapas:

1) Acercándose con velocidad V el flujo de aire a través del difusor entra en el compresor.

2) El compresor, que gira sobre el mismo eje que la turbina, comprime el aire que entra en la cámara de combustión.

3) Se inyecta constantemente combustible (queroseno) en la cámara de combustión, que se mezcla con aire comprimido.

4) El gas generado por la combustión entra en la turbina, que lo acelera a una velocidad W.

5) A esta velocidad, el gas es expulsado a través de la boquilla a la atmósfera.

Debido al hecho de que W > V, se genera fuerza de tracción R, que permite que la aeronave vuele en la atmósfera.

El cambio en la fuerza de tracción se lleva a cabo cambiando la tasa de inyección de combustible en la cámara de combustión moviendo la perilla de control del motor (THROT). El movimiento del acelerador a un cierto ángulo d del acelerador se lleva a cabo manualmente por el piloto o con la ayuda de un actuador de acuerdo con las señales del ACS en vuelo. Un aumento en el valor de d empuje provoca un aumento en la fuerza R, y una disminución es una disminución en esta fuerza.

GTE es complejo sistema técnico, en el que tiene lugar un importante número de procesos físicos y químicos. El motor está equipado con todo tipo de automatismos, sistemas de giro y refrigeración de álabes de turbina, etc. Naturalmente, la descripción matemática del funcionamiento del motor de turbina de gas también será bastante engorrosa, incluyendo sistemas de ecuaciones diferenciales en derivadas parciales, ecuaciones diferenciales ordinarias, funciones trascendentales, algoritmos sistema digital motor de control. Dichos modelos se utilizan en el proceso de diseño de motores de turbina de gas.

Para resolver los problemas de control de vuelo, más de modelo sencillo GTE, que es la dependencia de la fuerza de empuje R desde el ángulo d de la desviación del acelerador del acelerador. El proceso de cambio de la fuerza de empuje se describe mediante una ecuación diferencial ordinaria de la forma:

, (2.11)

donde t > 0 es la constante de tiempo del motor, que depende, además de características de diseño también de la temperatura ambiente, su humedad y otros factores externos; k[kg/grado] – coeficiente de proporcionalidad.

La condición inicial para la ecuación (2.11) se escribe como

R(0) = R 0 . (2.12)

Así, la ecuación (2.11) junto con la condición inicial (2.12) es el modelo matemático más simple del motor de turbina de gas, escrito en forma de ecuación diferencial ordinaria 1-th orden.

Para determinar el factor de proporcionalidad k Se utilizan curvas de calibración de la dependencia del empuje con respecto al ángulo de rotación de los estranguladores, construidas sobre la base de datos experimentales. La tangente de la pendiente de la gráfica es igual al coeficiente deseado.

La integración de la ecuación (2.11) con la condición inicial (2.12) permite averiguar cómo cambia la fuerza de empuje con el tiempo (Fig. 2.6).

Cuando se desvía el acelerador, el empuje R aumenta y luego se estabiliza en un cierto valor límite, es decir GTE es un objeto inercial.

límite de empuje obtenemos de (2.11) cuando la tasa de su cambio es igual a cero:

. (2.13)

Hora de levantarse depende del valor de la constante de tiempo del motor t. Se considera que el proceso es estacionario cuando t = t boca, cuando el empuje entra en el llamado corredor del cinco por ciento del valor límite de la fuerza de empuje (Fig. 2.6). Cuanto mayor sea t, más inercial será el motor y, en consecuencia, más t boca

En la fig. 2.7 muestra el comportamiento de la fuerza de empuje en función del ángulo de deflexión del acelerador en t = 0,5.

La fuerza de empuje durante el despegue, cuando el acelerador se desvía 10°, alcanza un estado estable en el tercer segundo y alcanza un valor de 3390 kg. Diez segundos después del despegue, cuando el acelerador se desvía 20°, la fuerza de empuje se establece en 6780 kg, y otros diez segundos más tarde, cuando el acelerador se desvía 30°, la fuerza de empuje se establece en 10170 kg. El valor límite de la fuerza de tracción es
14270 kg.

Información similar.

3.1. Tarea general programación lineal

Programación lineal- esta es la sección más desarrollada de la programación matemática, con la ayuda de la cual se realizan el análisis y la solución de problemas extremos con conexiones y restricciones lineales.

La programación lineal incluye una serie de métodos de solución heurísticos (aproximados) que permiten, en determinadas condiciones, de todos opciones soluciones a los problemas de producción para elegir el mejor, óptimo. Estos métodos incluyen los siguientes: gráfico, símplex, método potencial (método de distribución modificado - MOD), método de aproximación de Khichkov, Kreko, Vogel y otros.

Algunos de estos métodos están unidos por un nombre común: el método de distribución o transporte.

El lugar de nacimiento de la programación lineal es Rusia. Los primeros trabajos sobre programación lineal del futuro académico L.V. Kantorovich se publicaron en 1939. En 1975, recibió el Premio Nobel de Economía por el desarrollo de métodos de programación lineal. Dado que la mayoría de los trabajos del académico L.V. Kantorovich se dedica a resolver problemas de transporte, se puede considerar que el mencionado Premio Nobel también marca los méritos de la ciencia rusa del transporte.

En el transporte por carretera, los métodos de programación lineal se han utilizado desde la década de 1960 para resolver una gran cantidad de los problemas de producción más importantes, a saber: reducir la distancia de transporte de carga; elaboración de un esquema de transporte óptimo; selección de las rutas de circulación más cortas; tareas de transporte de cargas diferentes, pero intercambiables; planificación de turnos diarios; planificación del transporte de cargas en lotes pequeños; distribución de buses a lo largo de rutas y otros.

Las características del modelo de programación lineal son las siguientes:

La función objetivo y las restricciones se expresan dependencias lineales(igualdades o desigualdades);

El número de dependencias siempre es menor que el número de incógnitas (condición de incertidumbre);

No negatividad de las variables requeridas. La forma general de escribir un modelo de programación lineal en forma abreviada es la siguiente:

Encontrar X ij ≥ 0 (j = 1, 2…n) bajo el siguiente tipo de restricciones:

Estas restricciones minimizan (o maximizan) la función objetivo

La forma estándar de escribir un modelo de programación lineal es un sistema de ecuaciones lineales escrito en canónico forma, es decir, en forma de igualdades lineales, en números no negativos:

a 11 x 1 + a 12 x 2 + ... + a 1 n x n \u003d b 1;

un 21 x 1 + un 22 x 2 + ... + un 2 norte x norte \u003d segundo 2 ; (3.1)

……………………………..

un metro x 1 + un metro 2 x 2 + ...+ un mn x norte = segundo metro ..

Si el modelo está escrito en forma de desigualdades en números no negativos, es decir, tiene la forma

un 11 x 1 + un 12 x 2 + ... + un 1 norte X norte ≤ segundo 1;

un 21 x 1 + un 22 x 2 + ... + un 2 norte X norte ≤ segundo 2 ; (3.2)

……………………………..

un metro x 1 + un metro 2 x 2 + …+ un mn x norte ≤ segundo metro ,..

entonces esta entrada se reduce a canónico forma (3.1) introduciendo variables adicionales x norte +1> 0 (i=1,2…metro) al lado izquierdo de la desigualdad (o reducción del número de variables si el signo de la desigualdad se dirige en sentido contrario). Variables adicionales forman la base.

La forma estándar de resolver un problema de programación lineal es encontrar soluciones a un sistema de ecuaciones lineales en números no negativos que minimicen la función objetivo. La función objetivo tiene entonces la forma

L = do 1 x 1 + do 2 x 2 ... do norte X norte → min, (3.3)

Dónde s 1 , s 2 … s norte son los coeficientes de la función objetivo L con variables X j.

Las variables adicionales ingresan a la función objetivo con coeficientes cero.

En el caso de maximizar la función objetivo L los signos de las variables de la función objetivo deben invertirse, y volveremos nuevamente al problema de minimización, es decir una tarea se reduce a otra sustitución L en - L o máximo L=min(- L).

Una solución básica de un sistema de ecuaciones lineales (3.1) es una solución en la que se dan valores cero a las variables no básicas.

Se denomina solución básica admisible en la que las variables incluidas en la base no son negativas.

Una solución admisible que maximiza (o minimiza) la función objetivo (3.3) se denomina óptima.

Cada problema de programación lineal corresponde a otro, llamado problema de programación lineal dual. El problema original con respecto al dual se llama problema directo. Los problemas primal y dual forman un par, llamado par dual en programación lineal. El par primal y dual forman un par asimétrico cuando el problema primal se escribe en forma canónica, y un par simétrico cuando las condiciones de los problemas se escriben como desigualdades.

Las reglas para compilar un modelo matemático de un problema dual se basan en las reglas del cálculo matricial.

El concepto de dualidad es ampliamente utilizado en el análisis de problemas de programación lineal. La propiedad de dualidad se considera en detalle en cada caso particular.

3.2. Método gráfico-analítico

El método analítico gráfico es uno de los métodos más simples de programación lineal. Revela claramente la esencia de la programación lineal, su interpretación geométrica. Su desventaja es que te permite resolver problemas con 2 o 3 incógnitas, es decir, es aplicable a una gama estrecha de problemas. El método se basa en las reglas de la geometría analítica.

Resolver un problema con dos variables x1 Y x2, que, según el significado del problema, no debe ser negativo, se realiza en el sistema de coordenadas cartesianas. ecuaciones x1=0 y x2= 0 son los ejes del sistema de coordenadas del primer cuadrante

Consideremos el método de solución usando un ejemplo específico.

Ejemplo 3.1. Hay 300 toneladas de productos de hormigón celular y 200 toneladas de productos de acero en stock. La empresa automotriz necesita entregar estos productos a la instalación en construcción. La compañía de automóviles tiene camiones KAMAZ - 5320 y

ZIL-4314. Para un viaje, KamAZ-5320 puede entregar 6 toneladas de hormigón celular y 2 toneladas de acero, y la ganancia del viaje será de 4 mil rublos. ZIL-4314 entrega 2 toneladas de espuma de hormigón y 4 toneladas de acero en un solo viaje, la ganancia del viaje es de 6 mil rublos. Es necesario organizar el transporte de tal manera que proporcione a la empresa automotriz la mayor ganancia.

Construyamos un modelo matemático del problema. Denote por x 1 el número deseado de viajes KamAZ-5320 y a través X 2 número requerido de pasajeros ZIL-4314.

El transporte total en toneladas de productos de hormigón celular es de 6 x 1+ 2x2, y de acero 2 x 1+ 4x2. El límite de envío, en función del número de artículos disponibles, es de 6 x 1+ 2×2 ≤ 300t para hormigón celular y 2 x 1+ 4×2 ≤ 200t para acero.

Beneficio total en miles de rublos. expresado como 4 X 1 + 6X 2 , que necesita ser maximizado y que es el criterio de optimalidad en el problema bajo consideración. El modelo matemático del problema, por lo tanto, se parece a lo siguiente. Es necesario maximizar la función objetivo

L = 4x 1+ 6x2 → max bajo condiciones: 6 x 1+ 2×2 ≤ 300; 2x 1+ 4×2 ≤ 200; X 1 ≥ 0;x2 ≥ 0.

Considere la Ecuación 6 x 1+ 2x2 = 300. Para construir una línea descrita por esta ecuación, encontramos dos puntos que se encuentran en esta línea. En x1= 0 de la ecuación de una línea recta encontramos 2 x2 = 300, de donde x 2 \u003d 150. Por lo tanto, el punto A con coordenadas (0.150) se encuentra en la línea deseada. En x2= 0 tenemos 6 x1\u003d 300, de donde x 1 \u003d 50, y el punto D con coordenadas (50,0) también está en la línea deseada. Dibuja una línea a través de estos dos puntos ANUNCIO(Figura 3.1).

Desigualdad lineal 6 x 1+ 2×2 ≤ 300 es un semiplano situado a un lado de la línea construida 6 x 1+ 2x2 = 300. Para saber de qué lado de esta recta se encuentran los puntos del semiplano buscado, sustituimos en la desigualdad 6 x 1+ 2×2 ≤ 300 coordenadas de algún punto que no se encuentra en la línea límite. Por ejemplo, el origen es 0-(0,0). Satisface la desigualdad 6∙0 + 2∙0 = 0< 300. Это значит, что начало координат лежит в области допустимых значений, которая находится слева от прямой ANUNCIO y en la fig. 3.1 está sombreado.

ecuación 2 x 1+ 4x2= 200 se construirá a partir de dos puntos. En x1 = 0 4x2 = 200 de donde x2 = 50. Luego apunta mi tiene coordenadas (0,50) y pertenece a la línea deseada. En x2= 0, 2x2 = 200 puntos Con está en la línea dada con coordenadas (100,0). Sustituyendo en la desigualdad las coordenadas del punto Con(0,0), obtenemos 2∙0 + 4∙0 = 0< 200. Значит, начало координат находится в области допустимых значений от прямой 2x1+ 4x2= 200.

El sistema de restricción de tareas requiere que los planes ( ×1; x2) satisfacen las cuatro desigualdades, es decir, los diseños admisibles son puntos ( ×1; x2) debe estar simultáneamente en los cuatro semiplanos. Este requisito solo lo cumplen los puntos ubicados dentro y en el borde del polígono. OEKD, que es el polígono de soluciones admisibles.

Los vértices del polígono de soluciones factibles son los puntos O, E, K, D segmentos de linea OE, EK, KD, OD- sus costillas. Cualquier punto del polígono OEKD es el plan de la tarea, satisfaciendo todas sus condiciones. Los vértices del polígono están formados por la intersección de dos rectas y corresponden a los planos básicos del problema, entre los cuales se encuentra el mejor (óptimo) plano. Así, habrá tantos planos de referencia como vértices tenga el polígono de soluciones factibles.

También se puede obtener una representación geométrica visual para la función objetivo L = 4x 1+ 6x2. Fijamos algún valor de la función objetivo, por ejemplo L= 120. ecuación 4 x 1+ 6x2 = 120 define una línea que pasa por un punto EN con coordenadas (x 1 \u003d 0; x 2 \u003d 20) y un punto L con coordenadas (( X 1 = 30; X 2 = 0). Segmento de línea licenciado en Derecho se encuentra dentro del polígono OEKD. Por lo tanto, para todos los planos (puntos) de este segmento, el valor de la función objetivo es el mismo e igual a 120. Dando otros valores de la función objetivo, obtenemos líneas paralelas, que se llaman líneas de nivel función objetivo.

moviendo la linea L paralelo a sí mismo en una dirección, obtenemos un aumento en la función objetivo, y en la dirección opuesta, su disminución. En este ejemplo, el movimiento de una línea recta licenciado en Derecho a la derecha determina el incremento en la función objetivo que estamos maximizando. Hacemos esto hasta la línea licenciado en Derecho tendrá al menos un punto en común con el polígono de soluciones admisibles OEKD. De la fig. 3.1 se sigue que el último punto que corta la recta del nivel de la función objetivo será el punto A. Esto significa que el punto A determina el plan de tareas óptimo.

La dirección de aumento perpendicular a la línea de nivel se llama dirección de mayor incremento función objetivo y determina su ganancia máxima. Esta dirección se puede establecer sin dibujar líneas de nivel. Para esto, es necesario en los ejes. x1 Y x2 apartar segmentos iguales a los coeficientes de la función objetivo, y usándolos, como en coordenadas, construir un vector de mayor incremento en la función objetivo. En matemáticas se llama degradado y denotado por el signo grad. Gradiente para una característica L = 4x1 + 6x2 será vector norte| 4; 6 | . Para la conveniencia de su construcción, aumentamos las coordenadas, por ejemplo, 10 veces, es decir norte | 40; 60 | . Construyamos el gradiente de la función objetivo L, para lo cual conectamos el punto de coordenadas (40; 60) con el origen. Las líneas de nivel de la función objetivo se dibujan perpendiculares a la dirección del gradiente.

Entonces, de una forma u otra, se establece que el punto A determina el plan de tareas óptimo, cuyos valores de las variables corresponden a las coordenadas del punto dado. Para establecer las coordenadas es necesario resolver el sistema de ecuaciones de las rectas que forman este vértice:

6x 1+ 2x2= 300;

2x 1+ 4x2= 200.

Igualamos los coeficientes en x 1 multiplicando la segunda ecuación por 3 y restando el primero de la segunda ecuación. Consigamos 10 x2= 300,x2 = 30. Sustituyendo el valor x 2 \u003d 30 en cualquiera de las ecuaciones, por ejemplo, en la primera, determinamos el valor X 1:

6x1+ 2X · 30 = 300,

de donde 6 x1 = 300 - 60 = 240, por lo tanto, x1 = 40.

Por lo tanto, para obtener el máximo beneficio para una empresa de automóviles, es necesario realizar 40 viajes a KamAZ-5320 y 30 viajes a ZIL-4314. El beneficio máximo en este caso será

L = 4x 1+ 6x2\u003d 4 40 + 6 30 \u003d 340 mil rublos.

Con base en el ejemplo considerado y la interpretación geométrica del problema de optimización con dos variables, podemos sacar las siguientes conclusiones:

1) en el espacio bidimensional, el área de soluciones factibles es un polígono;

2) cada lado del polígono corresponde al valor de una variable igual a cero;

3) cada vértice del polígono de soluciones admisibles corresponde a los valores de dos variables iguales a cero;

4) cada valor de la función objetivo corresponde a una línea recta;

5) la solución óptima del problema corresponde al vértice del polígono, en el que la función objetivo adquiere el valor óptimo, mientras que las variables óptimas son las coordenadas de este vértice.

En el caso general, los problemas de optimización tienen una interpretación geométrica similar. El conjunto de planes de tarea será un poliedro cuyos vértices corresponden a los planes de referencia. Al resolver el problema se realiza el paso de un vértice del poliedro a otro con un valor grande de la función objetivo hasta obtener su valor óptimo. Nótese que la eficiencia de los métodos de optimización radica precisamente en el hecho de que la enumeración de vértices (iteración) se realiza únicamente en la dirección del mayor incremento de la función objetivo. Por lo tanto, no se consideran todos los vértices, de los cuales hay una gran cantidad, sino solo aquellos que están más cerca del extremo.

Al determinar una clase de problemas de optimización y elegir un método para resolverlos, es necesario saber si el conjunto de soluciones factibles es convexo o no convexo, una función objetivo lineal o no lineal.

Por definición, un conjunto se llama convexo si para dos puntos cualquiera todo el segmento que conecta estos puntos pertenece a este conjunto. Ejemplos de conjuntos convexos son, por ejemplo, un segmento (Fig. 3.2, a), un plano en forma de círculo, un cubo, un paralelepípedo, así como polígonos que están completamente ubicados en un lado de cada uno de sus lados , etc.

En la fig. 3.2b muestra conjuntos no convexos. En conjuntos no convexos, se pueden indicar al menos dos puntos del segmento AB que no pertenecen al conjunto considerado.

3.3. Método símplex

Método símplex es un método común para resolver problemas de programación lineal. El método obtuvo su nombre de la palabra "simplex", que denota el polígono convexo más simple, cuyo número de vértices es siempre uno más que la dimensión del espacio. El método simplex fue desarrollado en Estados Unidos por el matemático J. Dantzig a fines de la década de 1940.

El método simplex incluye la obtención de una solución básica no negativa de un sistema de ecuaciones lineales canónicas de tipo (3.1), la posterior minimización (maximización) de la función objetivo (3.3) y, de esta forma, encontrar los valores óptimos de las variables requeridas x 1, x 2… x norte.

La idea del método simplex radica en el hecho de que en el transcurso del cálculo se pasa secuencialmente de la primera solución básica a la segunda, tercera, etc. a través de los llamados símplex transformaciones. Las transformaciones se realizan en forma de tablas simplex, lo que simplifica y acelera enormemente los cálculos.

Para obtener soluciones básicas no negativas de un sistema de ecuaciones lineales, es necesario llevar a cabo el proceso de eliminación de incógnitas de tal manera que los términos libres de las ecuaciones permanezcan no negativos en todas las etapas del proceso. En este caso, uno debe guiarse por la siguiente regla: cualquier variable libre para la cual existe al menos un coeficiente positivo se toma como una nueva variable básica; una variable se deriva de la base, que corresponde a la relación más pequeña de los términos libres de las ecuaciones a los correspondientes coeficientes positivos de las ecuaciones con la variable introducida en la base. Tales transformaciones se llaman convertidores símplex.

Esto es muy importante, porque para encontrar una solución particular no negativa que corresponda al mayor valor posible de una variable libre con valores cero de otras variables libres, en lugar de determinar el rango de la variable especificada y sustituir su mayor valor posible en decisión común basta tomar esta variable como la básica y someter el sistema a una transformación símplex, pasando a una nueva base, lo que simplifica mucho los cálculos.

Los cálculos se realizan convenientemente usando tablas simplex. El paso de una tabla a otra corresponde a una iteración, es decir, el paso de una base a otra, mientras el valor de la función objetivo decrece. Para un cierto número de iteraciones, pasan a la base para la cual se obtiene el valor óptimo (mínimo o máximo) de la función objetivo. Consideremos el método símplex en forma general.

La tarea general de la programación lineal es minimizar (maximizar) la función objetivo, cuyas variables están interconectadas por un sistema de ecuaciones lineales, sujeto a la condición de no negatividad.

Sea necesario minimizar la forma lineal

L = do 1 x 1 + do 2 x 2 + ... do norte x norte.

Bajo las siguientes condiciones (para mayor claridad, los coeficientes cero y unitarios se mantienen en las ecuaciones):

1x1+ 0x2 +... 0x m + a 1m+ 1x m+1 ... + a 1n x n \u003d b 1;

0x 1+ 1x2+… 0x m + a 2m+ 1x m+1 ... + a 2n x n \u003d b 2;

……………………………………………

0x1+ 0x 2 + ... 1x m + a mm + 1x m +1 ... + a mn x n \u003d b m.

Este sistema de ecuaciones ya tiene una base ya hecha, ya que cada ecuación de restricción contiene una incógnita con un coeficiente igual a uno, que no está en otras ecuaciones, es decir, de los coeficientes de las variables X 1 , X 2 …, x metro puede crear una matriz de identidad.

Resolvamos las ecuaciones para las variables básicas:

x 1 \u003d b 1 - (a 1m + 1 x m + 1 ... + a 1n x n);

x 2 \u003d b 2 - (a 2m + 1 x m + 1 ... + a 2n x n);

………………………………

x m \u003d b m - (un mm + 1x m + 1 ... + un mn x n),

y expresaremos la función objetivo en términos de variables libres, sustituyendo en ella, en lugar de las variables básicas, sus expresiones en términos de variables libres:

L=c 1 b 1 +c 2 b 2 +c m b m –(c 1 a 1m +c 2 a 2m+1 +…+c m a mn+1)x m+1 -…-(c 1 a 1n +c 2 a 2n +…+c m a mn)x n …+c n x n..

Variables x 1, x 2 ..., x metro, con cuya ayuda se encuentra el primer plan básico, son básicos, y el resto x m +1 , x m +2 ,…x norte – gratis. Siempre debe haber tantas variables básicas como ecuaciones en el sistema. Según la condición de no negatividad, el valor más pequeño de las variables libres es igual a cero. La solución básica resultante del sistema de ecuaciones es su solución factible inicial, es decir x 1 \u003d segundo 1, x 2 \u003d segundo 2, ... x metro \u003d segundo metro, x metro +1 \u003d 0,…, xn = 0.

Esta solución corresponde al valor de la función objetivo

L = do 1 segundo 1 + do 2 segundo 2 + ... do metro segundo metro.

La solución inicial se comprueba para la optimización. Si no es óptimo, entonces al introducir variables libres en la base, se encuentran las siguientes soluciones factibles con un valor menor de la función objetivo. Para ello se determina una variable libre que se debe ingresar a la base, así como una variable que se debe sacar de la base. Luego pasan del sistema anterior al siguiente sistema equivalente. Esto se hace usando tablas simplex. La solución del problema continúa hasta que se obtiene el valor óptimo de la función objetivo.

Las tablas simplex se compilan de la siguiente manera (ver Tabla 3.1). Coloque todas las variables en la parte superior de la tabla. X 1 , X 2 …, x norte y coeficientes cj, con lo cual se incluyen las correspondientes variables en la función objetivo. Primera columna c yo consiste en el coeficiente de la función objetivo para las variables incluidas en la base. A esto le sigue una columna de variables básicas y términos libres de las ecuaciones. Los elementos de las restantes columnas de la tabla son los coeficientes de las variables con las que estas últimas ingresan al sistema de ecuaciones. Así, cada fila de la tabla corresponde a la ecuación del sistema, resuelta con respecto a la variable básica. La tabla también muestra una variante del plan que corresponde a la función objetivo para una base dada.

La fila inferior de la tabla se llama índice. Cada uno de sus elementos (estimación) ∆ j determinar

∆j = z j – c j ,

Dónde cj son los coeficientes de las variables correspondientes en la función objetivo; zj- la suma de los productos de los coeficientes de la función objetivo con variables básicas y las correspondientes variables - elementos j-ésima columna de la tabla.

Mesa 3.1

Tabla simplex con inicial válida

1.

2. alfombrilla de instrucciones de uso. modelos en la economía.

Los modelos matemáticos le permiten determinar los valores óptimos de parámetros desconocidos sistemas economicos que es importante en el proceso de toma de decisiones. La programación matemática solo proporciona un aparato que le permite optimizar el proceso de selección. las mejores opciones planes en el proceso de gestión en los sistemas económicos.

Utilizado en estadística matemática, métodos de optimización, métodos económicos. cibernética, problemas experimentales.

Cuando se estudian procesos y fenómenos complejos en la economía, a menudo se usa el modelado, una muestra concreta bien definida de las características consideradas del objeto en estudio. Su esencia radica en el hecho de que el fenómeno en estudio se reproduce en condiciones experimentales utilizando un modelo en una escala temporal y espacial diferente. Un modelo es un objeto especialmente creado con la ayuda del cual se reproducen ciertas características del sistema en estudio para estudiarlo. Modelado matemático es el método más perfecto y al mismo tiempo efectivo para obtener información sobre el objeto en estudio. Es una poderosa herramienta para el análisis en economía. Los resultados de las investigaciones que utilizan modelos serán de interés práctico cuando el modelo construido sea suficientemente adecuado al fenómeno en consideración, es decir. lo suficientemente bien como para reflejar la situación real.

2. La programación matemática como ciencia, su estructura. Problemas de optimización. Dificultades en la aplicación de métodos clásicos de optimización en la resolución de problemas económicos.

Programación matemática es una rama de las matemáticas aplicadas que desarrolla bases teóricas y métodos para resolver problemas extremos.

La programación matemática incluye una serie de secciones, las principales de las cuales son las siguientes:

1. Programación lineal. Esta sección incluye problemas en los que se incluyen variables desconocidas en relaciones matemáticas de primer grado.

2. Programación no lineal. Esta sección incluye problemas en los que la función objetivo y (o) las restricciones pueden ser no lineales.

3. Programación dinámica. Esta sección incluye tareas en las que el proceso de solución se puede dividir en etapas separadas.

4. Programación entera. Esta sección incluye tareas en las que las variables desconocidas solo pueden tomar valores enteros.

5. Programación estocástica. Esta sección incluye tareas que contienen variables aleatorias en la función objetivo o restricciones.

6. Programación paramétrica. Esta sección incluye problemas en los que los coeficientes de variables desconocidas en la función objetivo o restricciones dependen de algunos parámetros.

Para resolver problemas de programación matemática es difícil utilizar los métodos clásicos de búsqueda de un extremo, ya que en los problemas de programación matemática la función objetivo alcanza su valor extremo en la frontera de la región de valores aceptables de las variables desconocidas y no existen derivadas. en los puntos limítrofes. Una enumeración completa de los puntos admisibles es imposible debido a su gran número.

3. El concepto de modelo matemático, tipos de mat. modelos

Modelo matemático es una abstracción de un fenómeno o proceso real escrito en símbolos y expresiones matemáticas. Modelos matemáticos procesos económicos y los fenómenos se llaman modelos económicos y matemáticos

Los modelos se dividen en:

1. lineal, en el que todas las dependencias se describen mediante relaciones lineales,

2. no lineal, en el que existen relaciones no lineales;

3. estocástico, que tienen en cuenta la naturaleza aleatoria de los procesos en estudio,

4. determinista, que tienen en cuenta los valores medios de todos los parámetros.

5. dinámica modelos en los que los sistemas en estudio se consideran en desarrollo durante varios períodos,

6. estático, en el que no se tiene en cuenta el factor tiempo.

7. mejoramiento modelos en los que la elección se hace en función de extremización algún criterio,

8. no optimización, en el que no existe un criterio de optimalidad.

9. macromodelos(para toda la casa)

10. micromodelos(eslabones individuales o procesos de la economía).

Tipos de modelos matemáticos: lineal, no lineal, cuadrático, entero, discreto, paramétrico, lineal fraccionario, dinámico, estocástico

4. Enunciado general de problemas de programación matemática.

Considere el enunciado general del problema de la programación matemática.

El problema general de la programación matemática es determinar el valor óptimo de la función objetivo, y los valores de las variables deben pertenecer a un cierto rango de valores admisibles. Matemáticamente, la definición de la solución óptima se expresa en encontrar el extremo (máximo o mínimo) de una función de muchas variables

Z = f(x1, x2, …, xn)

en el rango dado de cambio de estas variables

gi (x1, x2,…, xn)Ribi (i = 1, 2,…, m),

donde Ri es uno de los signos ≥, =, ≤.

5. El problema de optimizar el plan de producción. Formulación económica y construcción de un modelo matemático de problemas.

Entorno económico:

la empresa produce norte tipos de productos que utilizan metro tipos de materias primas. Para la producción de una unidad de producción se utiliza una cantidad estrictamente definida de materias primas de un tipo u otro. Las materias primas de cada tipo en la empresa son limitadas. La empresa recibe una cierta ganancia por la venta de una unidad de producción. Es necesario encontrar un plan de producción de este tipo en el que la empresa reciba la máxima ganancia total.

Configuración matemática:

Sea j el índice del tipo de producto j = 1, n

i - índice del tipo de recurso i = 1, m

e ij son costos de materia prima i-th tipo para la producción de una unidad de producción j-th tipo;

Аi es un límite dado en el volumen disponible de recursos del i-ésimo tipo;

Pj - beneficio recibido por la venta de una unidad de producción del tipo j-ésimo;

xj es el volumen de salida del tipo j-ésimo.

z \u003d P1x 1 + P2x 2 + ... + Pnx n → máximo

a11x 1 + a12x 2 +…+ a1nx n ≤ A1

a21x 1 + a22x 2 +…+ a2nx n ≤ A2

…………………………….

a m1x1 + a m2x2 +…+ a m n x n ≤ Am

xj ≥ 0, j = 1, norte

6. La tarea de la dieta. Formulación económica y construcción de un modelo matemático del problema.

Entorno económico

Algunas granjas alimentan animales. Se utiliza para engorde norte tipos de pienso. Se conoce el contenido de nutrientes (calcio, fósforo, etc.) por unidad de alimento de cada especie. Para una nutrición adecuada de los animales, es necesario consumir nutrientes no menos de las cantidades especificadas. Se conoce el costo unitario de cada alimento. Es necesario determinar la dieta de alimentación animal, en la que el coste total de engorde será mínimo.

Configuración matemática:

j es el índice del tipo de alimentación, j = 1, n

i – índice de tipo de nutriente, i = 1, m

Аi es la ingesta diaria necesaria del i-ésimo tipo de nutriente;

Сj es el costo de una unidad de alimento del tipo j-ésimo.

Introduzcamos variables desconocidas:

хj - volumen diario de alimentación animal j-ésima vista popa.

En términos de la notación introducida tarea dada se escribirá a continuación

a11x1 + a12x2 +…+ a1nxn ≥ A1

a21x1 + a22x2 +…+ a2nxn ≥ A2

…………………………….

am1x1 + am2x2 +…+ y mnxn ≥Am

xj ≥ 0, j = 1, norte

7. Tarea de transporte . Formulación económica y construcción de un modelo matemático del problema.

Entorno económico :

Disponible metro proveedores de productos homogéneos y norte consumidores de este producto. Costos unitarios conocidos para la entrega de una unidad de producción de cada proveedor a cada consumidor. Las existencias de los proveedores son limitadas. También se conocen las necesidades de los productos de cada consumidor.

Es necesario determinar dicho plan para el transporte de productos de proveedores a consumidores, en el que el costo total de transporte será mínimo.

Entorno matemático :

Introduzcamos la notación establecer parámetros:

j – índice de consumo, j = 1, n

i – índice de proveedores, i = 1, m

Аi es el volumen de productos disponibles del i-ésimo proveedor;

Bj - el volumen de demanda de los productos del j-ésimo consumidor;

Cij: costos unitarios para el transporte de una unidad de producción desde el i-ésimo proveedor hasta el j-ésimo consumidor.

Introduzcamos variables desconocidas:

хij es el volumen de transporte de productos desde el i-ésimo proveedor hasta el j-ésimo consumidor.

z = С11x11 + С12x12 +…+С1nx1n + С21x21 +…+ Сm(n -1)xm (n-1) + Сmnxmn → min

Restricciones de tareas.

I. De cada proveedor, podrá retirar productos no más de la cantidad disponible:

x11 + x12 +…+ x1n ≤ A1

x21 + x22 +…+ x2n ≤ A2 (2)

…………………….

xm1 + xm2 +…+ xmn ≤ Am

II. La necesidad de cada consumidor de productos debe ser satisfecha.

x11 + x21 +…+ xm1 ≥B1

x12 + x22 +…+ xm2 ≥B2

……………………. (3)

x1n + x2n +…+ xmn ≥Bn

tercero Condición de no negatividad: xij ≥0, i = 1, m ; j = 1, norte

A menudo es conveniente escribir el enunciado matemático en forma plegada:

, yo = 1, metro , j = 1, norte

8. El problema de elegir asignaciones o asignaciones. Formulación económica y construcción de un modelo matemático del problema.

Entorno económico :

Disponible norte tipos de trabajo y norte artistas intérpretes o ejecutantes Cada uno de los artistas puede realizar cualquier trabajo, pero solo uno. Se fija el coste de realización de cada obra por cada ejecutante. Es necesario asignar a los artistas a trabajar de tal manera que el costo total de completar el trabajo sea mínimo.

Entorno matemático .

Introduzcamos la notación para los parámetros dados.

i – índice de obras, i = 1, m

j es el índice de ejecutantes, j = 1, n

Cij es el costo de realizar el i-ésimo trabajo por parte del j-ésimo ejecutor.

Introduzcamos variables desconocidas. En este problema, las variables desconocidas solo pueden tomar dos valores, 0 o 1. Estas variables se denominan variables nulas.

1 - si el j-ésimo ejecutante está asignado al i-ésimo trabajo;

0 - de lo contrario.

En términos de la notación introducida, este problema se puede escribir de la siguiente manera:

z = С11x11 + С12x12 +…+С1nx1n + С21x21 …+ С(n-1)(n-1)x(n-1)(n-1) + Сnnxnn → min

Grupo de restricciones.

Solo se debe asignar un intérprete a cada obra:

x11 + x12 +…+ x1n = 1

x21 + x22 +…+ x2n = 1

……………………..

xn1 + xn2 +…+ xnn = 1

II. grupo de restricción.

Cada ejecutor puede realizar un solo trabajo:

x11 + x21 +…+ xn1 = 1

x12 + x22 +…+ xn2 = 1

……………………..

x1n + x2n +…+ xnn = 1

xij = (0,1) i = 1, norte; j = 1, norte

9. El problema del corte de materiales. Formulación económica y construcción de un modelo matemático del problema.

Entorno económico .

La materia prima del mismo tamaño se suministra para el corte. Se requiere cortarlo en espacios en blanco de un tamaño dado en una cantidad dada, de modo que el desperdicio total sea mínimo.

Entorno matemático .

Introduzcamos la notación:

i es el índice de espacios en blanco,

Аi - el número requerido de espacios en blanco del i-ésimo tipo;

j - índice de opciones de corte,

Cj es el tamaño de desperdicio al cortar una unidad de material inicial según la opción j;

e ij es el número de piezas en bruto del i-ésimo tipo al cortar una unidad de material inicial según la opción j.

Introduzcamos la notación de variables desconocidas.

xj es la cantidad de materia prima cortada según la opción j.

En términos de la notación introducida, este problema se puede escribir de la siguiente manera:

z \u003d С1x1 + С2x2 + ... + Сnxn → min

a11x1 + a12x2 +…+ a1nxn = A1

a21x1 + a22x2 +…+ a2nxn = A2

…………………………….

am1x1 + am2x2 +…+ amnxn =Am

xj ≥ 0, j = 1, norte

El uso de modelos matemáticos le permite ahorrar hasta un 20% de materias primas.

El modelo matemático de corte se construye en dos etapas.

En la primera etapa, se construyen las opciones de corte, como resultado de lo cual los valores de la cantidad de opciones n, la cantidad de espacios en blanco de cada tipo obtenidos con diferentes opciones de corte (aij), así como los valores de residuos (Cj) se determinan.

La construcción de opciones para cortar una unidad de material de origen se lleva a cabo en la forma de la siguiente tabla:

número de opción

i1 en blanco

i2 en blanco

en blanco estoy

Los espacios en blanco están dispuestos en orden no creciente de sus tamaños. La construcción de variantes se lleva a cabo por el método de enumeración completa.

10. Forma general del modelo de problema PL y sus características

La forma general de la LLP es:

z \u003d С1x1 + ... + Сnxn max (min)

a11 X1 + a12 X2 + … + a1n Xn R1 a1

a21 X1 + a22 X2 + … + a2n Xn R2 a2

………………………………………………….

am1 X1 + am2 X2 +…+ amnxn Rm am

xj ≥ 0, j = 1, k, k ≤ norte

En forma general, cada símbolo R1 , R2 ,…, Rm significa uno de los signos: ≥, = o ≤ .

La forma general del modelo del problema PL tiene las siguientes características.

1. El sistema de restricciones se presenta en forma de ecuaciones (condiciones rígidas) y desigualdades (condiciones no rígidas).

2. No se imponen condiciones de no negatividad a todas las variables

3. La función objetivo tiende al máximo o al mínimo.

11. Forma estándar del modelo de problema PL y sus características

La forma estándar es la siguiente.

Encuentre el máximo o mínimo de la función objetivo z:

z = С1x1 + … + Сnxn → max (min) (1)

Sujeto a las siguientes restricciones:

a11 X1 + a12 X2 + … + a1n Xn ≤ a1

a21 X1 + a22 X2 + ... + a2n Xn ≤ a2

…………………………………………..

am1 X1 + am2 X2 +… + amn Xn ≥ am

xj ≥ 0, j = 1, k, k ≤ norte

Las características de la forma estándar del modelo de problema PL son las siguientes:

1. el sistema de restricciones se presenta en forma de desigualdades (condiciones no rígidas)

2. Se imponen condiciones de no negatividad a todas las variables.

3. la función objetivo tiende a max o min

12. Forma canónica del modelo de problema PL y sus características

La forma canónica es:

Encuentre el mínimo de la función objetivo z:

z = С1x1 + … + Сnxn → min

Sujeto a las siguientes restricciones:

a11 X1 + a12 X2 + ... + a1n Xn = a1

a21 X1 + a22 X2 + ... + a2nxn = a2

…………………………

am1x1 + am2 X2 +… + amn Xn = am

Xj ≥0, j = 1, norte

Las características de la forma canónica son las siguientes:

1. El sistema de restricciones se presenta en forma de ecuaciones (condiciones estrictas).

2. Las condiciones de no negatividad se aplican a todas las variables

3. La función objetivo tiende a

En algunas fuentes, la función objetivo del problema de LP, presentado en forma canónica, tiende a un máximo. Esto se hace por conveniencia de resolver el problema de acuerdo al algoritmo desarrollado para la función objetivo máxima.

13. Plan básico de tareas posible, admisible y óptimo, ODZ de la tarea LP

Definición 1. Los valores de variables desconocidas que satisfacen todas las restricciones de un problema de programación lineal se denominan admisible valores variables o planes .

Definición 2. El conjunto de todos los planes para un problema de programación lineal se denomina dominio de valores admisibles de variables ( ODZ ).

Definición 3. El plan del problema de programación lineal, en el que la función objetivo toma el valor mínimo (o máximo) en la ODZ se llama óptimo .

14. Tipos de registros de tareas de LP: expandido, plegado, matricial, vectorial.

Los modelos de problemas de LP se pueden escribir de varias formas.

1. Vista ampliada del registro del modelo

Z = c1 X1 + c2 X2 + … + cn Xn → min

a11 X1 + a12 X2 + … + a1n Xn = a1,

a21 X1 + a22 X2 + … + a2n Xn = a2,

……………………………………………

a m1 X1 + am2 X2 + … + amn Xn = am,

Xj ≥ 0, j = 1, norte.

2. Vista colapsada:

,

Xj ≥ 0, j = 1, norte.

3. Modelo del problema de PL en forma matricial:

X ≥ 0

Dónde

a11 a12 … a1n X1 a1

A= a21 a22 … a2n , X= X2 , A0 = a2

… … … … … …

am1 am2 … amn X3 am

4. Modelo del problema de PL en forma vectorial:

Dónde

X1 a11 a12 a1n a1

X2, a21, a22, a2n, a2

… … … … …

Хn am1 am2 am2 am

15. Transición de la forma estándar y general de los problemas de PL a la canónica. teorema de conexión

Para pasar de una forma general o estándar a una canónica, se utilizan las siguientes técnicas.

1. Conversión de variables. Si alguna variable Xk es no positiva (Xk ≤ 0), entonces se introduce una nueva variable Xk ", de modo que Xk " = –Xk . Obviamente, Xk " ≥ 0. Después de eso, en cada restricción y función objetivo, la variable Xk se reemplaza por [ – Xk "].

Si alguna variable Xt puede tomar cualquier valor, entonces se reemplaza por la diferencia de dos variables no negativas Xt' y Xt'', es decir, se supone que xt = Xt' – Xt'', donde Xt' 0 ≥ y Xt'' ≥ 0.

2. Transformación de restricciones. Si alguna de las restricciones en el modelo tiene la forma de una desigualdad, entonces se convierte en igualdad sumando (si la desigualdad es de tipo ≤) o restando (si la desigualdad es de tipo ≥) de su lado izquierdo. Estas variables se denominan variables de equilibrio. Las variables de balance se incluyen en la función objetivo con coeficientes cero. La variable saldo toma el valor del índice secuencialmente después de los ya existentes. Si, por ejemplo, el sistema de restricciones tiene 5 variables, entonces la primera variable de saldo será X6, y la segunda, X7, etc.

16. Transición de la forma canónica del modelo ZLP al estándar

Para pasar de la forma canónica a la forma estándar, cada uno de

ecuaciones a ser reemplazadas por un sistema de desigualdades:

Otra forma es llevar el sistema de ecuaciones a una forma especial y eliminar aún más algunas variables.

Usando el método de Jordan-Gauss, seleccionamos la variable básica en cada ecuación. Tal selección se lleva a cabo con la ayuda de transformaciones gaussianas equivalentes (elementales). Éstas incluyen:

a) multiplicación de cualquier ecuación por una constante distinta de cero;

b) suma a cualquier ecuación de cualquier otra ecuación, multiplicada por cualquier constante.

Es conveniente escribir el sistema de ecuaciones lineales inicial antes de la transformación en forma de matriz o tabla:

Escribimos el problema en forma estándar.

17. El concepto de un hiperplano de un semiplano, un hiperplano de apoyo.

18. Geométrica. interpretación del sistema de restricciones y la función objetivo en problemas de PL

19. Conjunto convexo: puntos extremos (esquinas) del conjunto. poliedro convexo

Definición Un conjunto M se llama convexo si, junto con dos puntos cualesquiera pertenecientes a conjunto dado, también contiene un segmento que los conecta.

conjunto convexo

Definición Un punto x de un conjunto M se llama vértice o punto extremo si no es interior a ningún segmento que pertenezca enteramente al conjunto dado.

Teorema 1. Cualquier punto de un segmento se puede representar como una combinación convexa de sus puntos de esquina.

x \u003d λ 1 A + λ 2 B

λ 1 , λ 2 ≥ 0 combinación convexa de puntos de esquina A y B

λ1 + λ2 = 1

Teorema 2. Cualquier punto de un conjunto cerrado convexo se puede representar como una combinación convexa de sus puntos de esquina.

20. Algoritmo del método gráfico para la resolución de problemas de PL

1. Se verifica si el LPP original está en el formulario estándar, si no, entonces la tarea debe convertirse al formulario estándar.

2. Se comprueba el número de variables desconocidas. Si este número es mayor que tres, entonces el problema no se puede resolver mediante un método gráfico (existen otros métodos efectivos para resolver este tipo de problemas).

3. La región de valores admisibles de variables para ZLP está en construcción.

4. Se está construyendo un vector guía. C .

5. El isocel inicial se dibuja a través de la ODZ (perpendicular al vector de dirección).

6. El movimiento mental del isocoel inicial en la dirección del vector se realiza C, si se determina el valor máximo de la función objetivo, o en sentido contrario, si se determina su valor mínimo, hasta que la isometa se convierte en referencia a la ODZ. Los puntos de intersección del isocoel de referencia y la ODZ serán los puntos óptimos del problema.

7. Para determinar las coordenadas del punto óptimo, es necesario resolver el sistema de ecuaciones lineales correspondiente.

8. Para encontrar el valor óptimo de la función objetivo, es necesario sustituir los valores óptimos de las variables en la función objetivo y calcular su valor.

20. algoritmo gráfico. método de resolución de problemas LP

Algoritmo del método gráfico.

1. Por construcción sucesiva de cada una de las condiciones del sistema de restricciones del problema, se lleva a cabo la construcción de la ODZ.

2. El vector director C se construye con los coeficientes de las variables de la función objetivo.

3. El isocoel inicial se dibuja perpendicular al vector de dirección a través del origen.

4. La isometa inicial se mueve mentalmente en la dirección de valores crecientes del vector C, si se determina el valor máximo de la función objetivo, o en la dirección opuesta, si se determina su valor mínimo, hasta que la isometa se convierte en una referencia a la ODZ. Los puntos de intersección del isocoel de referencia y la ODZ serán los puntos óptimos del problema.

5. Para determinar las coordenadas del punto óptimo, es necesario resolver el sistema de ecuaciones lineales correspondientes de aquellas condiciones en la intersección de las cuales se encuentra el punto óptimo.

6. Para encontrar el valor óptimo de la función objetivo, es necesario sustituir las coordenadas del punto óptimo en la función objetivo y calcular su valor.

23. teoremas sobre el rango de valores admisibles del problema PL y sobre la función objetivo

El teorema ODZ. El dominio de soluciones admisibles del problema PL es un conjunto convexo (cerrado y acotado en un espacio n-dimensional)

Teorema 2. Sobre la función objetivo de un problema de programación lineal.

La función objetivo LLP toma su valor óptimo en uno de los puntos de esquina de la región de valores aceptables de las variables. Si la función objetivo toma su valor óptimo en varios puntos de esquina, entonces toma el mismo valor en cualquier punto que sea una combinación convexa de estos puntos de esquina.

24. El teorema del vértice. Suficiente y condición necesaria

25. Corolarios del teorema sobre las propiedades de las soluciones a problemas de LP y conclusiones. El concepto de línea de base.

Consecuencias de los teoremas.

Definición. Plan = (х1,х2,…,хn), cuyas coordenadas positivas corresponden a vectores linealmente independientes, se llama plan basico PLP .

Consecuencia 1. El plano de referencia no tiene más de m coordenadas positivas.

Si tiene exactamente m coordenadas positivas, dicho diseño de soporte se denomina no degenerado; de lo contrario, degenerado.

consecuencia 2. Cada punto de esquina ODZ es el plan básico.

27. Algoritmo del método simplex.

Al resolver problemas de PL por el método símplex, es necesario realizar la siguiente secuencia de acciones.

1. Se comprueba si el problema de LP está en forma canónica. Si no, entonces es necesario convertir el modelo original en una forma canónica.

2. Para este plan de referencia se selecciona el plan de referencia inicial y el valor de la función objetivo.

3. Se construye la tabla símplex inicial.

4. Se verifican los valores de las estimaciones de optimización en la línea de índice. Si no hay estimaciones positivas, se escribe la solución óptima y el algoritmo finaliza su trabajo. En caso contrario, se cumple el punto 5.

5. En la base, se introduce un vector, que corresponde a la estimación positiva más grande. Esta columna se denomina columna de habilitación.

6. De la base se deriva un vector, que corresponde a la relación simplex calculada por la fórmula 0< Ө ≤ . línea dada llamado la cadena de habilitación.

7. Se construye una nueva tabla símplex. Las columnas B y C B se modifican en consecuencia. El resto de la tabla se completa a partir de la anterior mediante transformaciones gaussianas, con la fila de índice considerada como m+1 filas y también transformada mediante transformaciones gaussianas. Procedemos a la implementación del párrafo 4 de este algoritmo.

Después de construir cada tabla, puede verificar la exactitud de los cálculos utilizando las fórmulas para calcular las estimaciones proporcionadas en el párrafo anterior.

28. Elección de una base y construcción de un plan de referencia inicial para la resolución de problemas por el método símplex.

29. Mesas simplex, su relleno. Fórmulas para calcular coeficientes de fila de índice.

30 . El teorema de optimización para el plan de un problema de programación lineal es una consecuencia del teorema de estimación de optimización para la resolución de problemas por el método simplex.

Teorema 1: Si para algún vector Ā j en el sistema

X 1 + a 1 m +1 X m +1 + a 1 m +2 X m +2 + ... + a 1 n X n \u003d a 1

X 2 + a 2 m +1 X m +1 + a 2 m +2 X m +2 + ... + a 2 n X n \u003d a 2

…………………………………………………..

X m + un mn +1 X m +1 + un mn +2 X m +2 + ... + un mn X n = un metro

Se cumple la relación Z j – c j > 0, entonces el plan X B0 no es óptimo y se puede pasar al plan X B1 tal que Z (X B1) ≤ Z (X B0).

Aquí Z j = (С, Ā j) es el producto escalar de vectores.

C es un vector que consta de coeficientes en las variables básicas de la función objetivo Z

 j es un vector que consta de los coeficientes de expansión del vector correspondiente en términos de vectores base.

c j es el coeficiente de la función objetivo Z con variable X j

Consecuencia de teoremas: Si para todos los vectores  1 ,  2 , …,  n de algún plan de referencia Х la relación Z j – c j< 0, то опорный план Х является оптимальным. Величины (Z j – c j) – называются оценками оптимальности соответствующих векторов.

Así, el teorema y el corolario nos permiten establecer si el siguiente plan de soporte es óptimo y, en caso contrario, es necesario cambiar a otro plan de soporte, en el que el valor de la función objetivo será menor.

Comentario. El teorema y el corolario asumen que el problema está en forma canónica con una función objetivo mínima. Sin embargo, el método símplex también se puede utilizar para resolver problemas con una función objetivo máxima. En este caso, al analizar los valores de las estimaciones se utiliza su sentido contrario, es decir, el plan será óptimo si todas las estimaciones de optimalidad son no negativas (positivas o negativas).

31. Elección de un vector que entra en la base y se deriva de la base. Relación símplex.

Para cambiar a un nuevo plan de referencia, se necesita uno de los vectores gratuitos entrar en la base y generar algunos de los vectores base. Para introducir en la base, elegimos un vector que tenga al menos una coordenada positiva. Sea el vector A m+1 un vector de este tipo.

descomposición -

resp. vector, gato. será un plano de referencia si sus coordenadas no son negativas, y el número de coordenadas positivas será igual a m.

Las coordenadas del vector X1 deben ser no negativas, es decir .

Si , entonces esta coordenada será no negativa.

Sea el mínimo en la relación (5) obtenido en i =1, entonces si tomamos

entonces la primera coordenada del vector 1 X se convertirá en cero.

La relación (6) se llama relación símplex. Por lo tanto, nos hemos movido desde la línea de base original 0 X(vectores básicos A1, A2, ... Am) al plano de referencia 1 X(vectores básicos А2, А3,…, Аm, Am+1).

32. elemento permisivo de la mesa, su elección. Regla de eliminación completa de Jordan para el recálculo de tablas símplex.

33. Regla del cuadrilátero para recálculo de tablas símplex

34. Una señal de la unicidad del plan óptimo, el conjunto de planes óptimos y la ausencia de un plan óptimo al resolver el problema de PL por el método simplex.

Al resolver problemas por el método símplex, son posibles los siguientes tipos de soluciones óptimas:

1. Singularidad . Si las estimaciones de todos los vectores libres son estrictamente negativas, entonces el diseño de soporte obtenido es óptimo y único. (ver el ejemplo en el párrafo anterior).

2. Óptimo alternativo (conjunto de soluciones óptimas).

Si entre las estimaciones no positivas de vectores libres existe al menos una estimación cero, entonces el diseño de soporte obtenido será óptimo, pero no el único. En este caso, puede ir a otros planes de soporte (se introducen en la base vectores que corresponden a estimaciones cero) y, luego, escribir la solución óptima general como una combinación convexa de los planes de soporte óptimos obtenidos.

3. LLP no tiene una solución óptima, ya que la función objetivo no está acotada por abajo . Si la tabla símplex tiene una puntuación positiva y todos los elementos columna dada son negativos y cero, entonces vector dado puede incluirse en la base. Sin embargo, ninguno de los vectores base puede deducirse de la base. De esto se deduce que es posible una mayor disminución de la función objetivo cuando se cambia a un plan sin apoyo.

4. LLP no tiene una solución óptima, ya que el sistema de restricciones es inconsistente. Dado que al resolver el LLP, el método simplex habitual debe ser el plan de referencia inicial, el sistema de ecuaciones lineales ciertamente no es inconsistente. Por lo tanto, tal caso no puede ocurrir cuando se resuelve por el método simplex usual.

5. Si la ODZ consta de un punto, entonces la solución de dicho problema es trivial y se puede obtener sin usar el método símplex.

35. ¿Cuándo se utiliza el método de base artificial?

artificial.

36. Construcción del problema M en el método de base artificial

Sin embargo, si el problema de programación lineal está en forma canónica, no todas las ecuaciones contienen variables básicas, es decir, no hay una línea de base original. En este caso, en aquellas ecuaciones en las que no existan variables básicas, es necesario sumar alguna variable no negativa con coeficiente +1. Tal variable se llama artificial.

A la función objetivo hay que añadirle una variable artificial con un número positivo muy grande (ya que la función objetivo es encontrar el mínimo). Este número se denota letra latina M. Se puede considerar igual a +∞. En este sentido, a veces el método de base artificial se denomina método M. Tal transformación del problema original se llama construcción del problema extendido. Si está resolviendo un problema con una función objetivo para encontrar una variable artificial, debe agregar a la función objetivo un número positivo muy grande (ya que la función objetivo es encontrar el mínimo). Este número se denota con la letra latina M. Puede considerarse igual a +∞. En este sentido, a veces el método de base artificial se denomina método M. Tal transformación del problema original se llama construcción del problema extendido. Si se está resolviendo un problema con una función objetivo para encontrar el máximo, entonces las variables artificiales entran a la función objetivo con un coeficiente -M.

Así, en el problema ampliado tenemos una línea base (aunque algunas de las variables base son artificiales).

Se construye la tabla símplex inicial.

37. construcción de una línea de índice en el método de base artificial

Se construye una tabla simplex inicial, en la que la fila del índice se divide en dos filas, ya que las estimaciones constan de dos términos. La línea superior contiene el término de la estimación sin M, la línea inferior muestra los coeficientes en M. El signo de la estimación está determinado por el signo del coeficiente en M, independientemente del valor y el signo del término sin M, ya que M es un número positivo muy grande.

Así, para determinar el vector que se introduce en la base, es necesario analizar la línea de índice inferior. Si se deriva un vector artificial de la base, entonces se puede omitir la columna correspondiente en las tablas simplex subsiguientes si no hay necesidad de obtener una solución al problema dual (ver el siguiente tema).

Después de que todos los vectores artificiales hayan sido eliminados de la base, la fila inferior tendrá todos los elementos cero, excepto las estimaciones correspondientes a los vectores artificiales. Serán iguales a -1. Tal línea puede eliminarse de la consideración y la solución adicional puede llevarse a cabo por el método simplex usual, si no hay necesidad de obtener una solución al problema dual (ver el siguiente tema).

38. Criterio de optimalidad en el método de base artificial. El signo es la construcción del plan básico inicial de la tarea original.

39. Algoritmo del método dual simplex

Algoritmo del método dual simplex:

1. Rellene la primera tabla simplex de la forma habitual, independientemente de los signos de miembros libres. Se cree que tal problema debería tener una base unitaria inicial.

2. Seleccione la línea de guía por el elemento negativo absoluto más grande de la columna de miembros libres A0

3. La columna guía se selecciona de acuerdo con el valor absoluto más pequeño de la relación entre los elementos de la línea de índice y los elementos negativos de la línea guía.

4. Recalcular la tabla simplex de acuerdo con la regla de eliminaciones completas de Jordan

5. comprobar la admisibilidad del plan recibido. Una señal de obtener un plan de referencia aceptable es la ausencia de elementos negativos en la columna A0. Si hay elementos negativos en la columna A0, vaya al segundo párrafo. Si no los hay, entonces se procede a resolver el problema de la forma habitual.

6. Una señal de obtener una solución óptima por el método simplex dual es el criterio de optimalidad para el método simplex ordinario.

41. Modelos de transporte abiertos y cerrados. Transición de un modelo de transporte abierto a uno cerrado.

Tipos de tareas de transporte.

Disponible metro proveedores de productos homogéneos con existencias conocidas de productos y norte consumidores de estos productos con volúmenes dados de necesidades. También se conocen los costos unitarios de transporte.

Si la suma de los volúmenes de los inventarios de productos es igual al volumen de las necesidades de todos los consumidores, ese problema se llama tarea de transporte cerrado

(es decir, si ∑ Ai = ∑ Bj), de lo contrario, el problema de transporte se llama abierto. Para solucionar el problema del transporte, es necesario que se cierre.

Una tarea de transporte abierta se puede convertir en una cerrada de la siguiente manera.

Sea ∑Ai > ∑Bj. En este caso, es necesario introducir un consumidor ficticio n + 1 con un volumen de necesidades ∑Ai – ∑Bj Se supone que los costos unitarios de transporte desde los proveedores hasta un consumidor ficticio son 0, ya que de hecho dicho transporte no será y una parte de los productos se quedará con los proveedores.

Si ∑Bj > ∑Ai . En este caso, es necesario introducir un proveedor ficticio m + 1 con un volumen de inventario ∑Bj – ∑Ai. Los costos unitarios de transporte de un proveedor ficticio a los consumidores se suponen iguales a 0, ya que en realidad dicho transporte no se realizará y los consumidores no recibirán algunos de los productos.

42. Métodos para construir la distribución inicial en el problema de transporte: el método de la esquina noroeste y el método del menor elemento de la matriz.

Técnica del Noroeste para la construcción de un plano de referencia. Según esta técnica, la formación de valores de tráfico comienza con el s.-z. esquina de la mesa, i.e. de la celda x11. De acuerdo con este método, en primer lugar, se distribuyen los bienes del primer proveedor. Además, el primer proveedor primero satisface al primer consumidor tanto como sea posible. Entonces, si el proveedor todavía tiene los bienes,

El método del elemento más pequeño de la matriz.

La esencia del método radica en el hecho de que siempre se pone en la celda la máxima oferta posible, que corresponde a la tarifa más baja de la matriz.

Primero, hacemos marcas (por ejemplo, con el signo ▼) en aquellas celdas de las líneas en las que se observa el precio más bajo para la línea. Luego damos la vuelta a la tabla por columnas y hacemos las mismas notas en las celdas en las que el precio más pequeño está por columnas.

La distribución adicional se realiza primero en la medida de lo posible sobre las celdas con dos marcas, luego, con una, y luego el problema se vuelve a equilibrar a (m + n - 1) rellenos. Organizamos los rellenos al pasar la mesa de izquierda a derecha y de arriba a abajo.

43. Propiedades de las tareas de transporte.

El problema del transporte tiene algunas propiedades que se pueden reflejar en los siguientes teoremas.

Teorema 1. Un problema cerrado de transporte siempre tiene solución.

Teorema 2. Si el volumen de existencias de productos y el volumen de necesidades son números enteros, entonces la solución del problema de transporte también será número entero.

Teorema 3. el sistema de restricciones de un problema de transporte cerrado siempre es linealmente dependiente.

De este teorema se sigue que la distribución de un problema de transporte cerrado siempre tiene m + n – 1 variables básicas y (m – 1) (n – 1) variables de tiempo libre.

44. Distribución degenerada en problemas de transporte, eliminando la degeneración. Combinación tachada.

La distribución se llama degenerada si el número de celdas es menor que m + n - 1.

45. Teoremas de optimalidad para el problema del transporte.

Teorema. Si para alguna distribución de la tarea de transporte Ud.

se cumplen las condiciones:

A). ui+vj = cij para celdas ocupadas

b) ui+vj ≤ сij, para celdas libres,

entonces esta distribución es óptima.

Los valores ui se denominan potenciales de fila y los valores vj se denominan potenciales de columna.

46. ​​Potenciales y métodos de su cálculo.

Para encontrar los potenciales de filas y columnas se utiliza el siguiente razonamiento, basado en la condición a) del teorema de optimalidad.

El número de ecuaciones basadas en esta condición es m + n – 1, y el número de incógnitas ui y vj es m + n. Eso. el número de variables es mayor que el número de ecuaciones y todas las ecuaciones son linealmente independientes. La solución de tal sistema de ecuaciones lineales es indefinida, por lo que a uno de los potenciales se le debe asignar cualquier valor. En la práctica, ui = 0. Se obtiene un sistema de m + n – 1 ecuaciones con m + n – 1 variables desconocidas. Este sistema se puede resolver por cualquier método. En la práctica, para el cálculo de potenciales se consideran celdas ocupadas, para las cuales se conoce uno de sus potenciales, y en base a la condición a) del teorema, se calculan los valores de los restantes potenciales desconocidos.

47. Cálculo de estimaciones de la optimalidad de la distribución de tareas de transporte y el criterio de optimalidad.

Con base en la relación b) del teorema, podemos escribir la siguiente fórmula para calcular las estimaciones: δ yo= ui + vj – сij. Para no confundir las estimaciones con los volúmenes de tráfico, estas (estimaciones) se encierran en círculos.

Las estimaciones de optimización en celdas TK libres son un criterio de optimización que verifica la distribución en busca de optimización. Si las estimaciones de todas las celdas libres son menores o iguales a cero, entonces esta distribución es óptima.

48. redistribución de suministros en el problema del transporte

Si la distribución no es óptima, entonces es necesario redistribuir los suministros.

Para la redistribución, se construye un ciclo de recálculo. La celda con la puntuación positiva más alta se selecciona como celda. Esta celda está marcada con un signo "+", es decir, es necesario registrar una cierta cantidad de entrega en ella. Pero luego se alterará el equilibrio en esta columna, por lo tanto, una de las celdas ocupadas de esta columna debe marcarse con un signo "-", es decir, el volumen de suministro debe reducirse en la misma cantidad. Pero luego el saldo de esta línea cambiará, por lo tanto, alguna celda ocupada de esta línea debe marcarse con un signo "+". Este proceso continúa hasta que se coloca el signo “-” en la línea donde se encontraba la celda original.

Para cualquier celda libre hay un ciclo de recálculo y, además, el único.

49. Cadenas de redistribución, sus tipos.

Deje que el plan de transporte en consideración no sea óptimo, es decir. hay estimaciones relativas positivas. Luego se toma una celda desfavorable (una de las desfavorables) y se construye para ella un ciclo de recálculo, según el cual se redistribuye el transporte planificado. El ciclo se construye en forma de una línea discontinua cerrada, cuyos segmentos corren a lo largo de la columna o a lo largo de la línea. En una de las esquinas de la línea discontinua hay una celda desfavorable reclamando el producto, y en las otras esquinas las celdas están llenas, es decir al construir un ciclo, partimos de la celda candidata y regresamos a ella por una línea discontinua, pero solo podemos hacer giros en celdas llenas (correspondientes a las variables básicas). Deje que una celda desfavorable reclame el producto Q. Para evitar un desequilibrio en la tabla, es necesario

suma y resta Q al tráfico disponible. Como hay un número par de esquinas, se sumará Q en la mitad de las celdas y se restará en la otra mitad. El ciclo se inicia en el sentido de las agujas del reloj o en el sentido contrario a las agujas del reloj desde la celda candidata, colocando una buena Q allí, luego Q se resta de la celda vecina, luego se suma, y ​​así sucesivamente. El valor de Q en sí se elige para que una de las celdas se vacíe, pero ninguno de los suministros se vuelva negativo.

Para hacer esto, se debe elegir Q igual al menor reducible de las celdas en las que se resta Q. En la siguiente fig. 7.1 y 7.2 mostraremos ejemplos de ciclos y la regla de cálculo.

En este caso, se vacían dos celdas. Pero es necesario que solo una celda se vacíe mutuamente. Hacen esto: una de las celdas de vaciado se vacía en la nueva tabla y se pone cero en la otra celda de vaciado. Esta celda se considera básica (llena) en la nueva tabla.

50. La elección del volumen de redistribución.

Determinación del volumen de productos transportados. Al determinar el volumen de productos que se mueven a través del ciclo de conteo, debemos partir de las dos consideraciones siguientes:

a) después de la transformación en las celdas de la tabla, no deben obtenerse números negativos;

b) una de las celdas ocupadas debe quedar libre.

Para que se cumplan estas condiciones, es necesario seleccionar el volumen de productos transportados de la siguiente manera: θ=min (хij) -, donde (хij) es el volumen de transporte de las celdas del ciclo de recálculo marcadas con el “ -" firmar.

θ = min(20;30)=20

θ se suma a los valores de las celdas marcadas con un signo “+”. θ se resta de los valores de las celdas marcadas con un signo "-". El valor de suministro de las celdas restantes se sobrescribe sin cambios. Como resultado, obtenemos la siguiente tabla.

53. Algoritmo del método de los potenciales.

Algoritmo:

1. Comprobar si la ecuación se cumple para la tarea si no, se introduce en la tarea a un proveedor o consumidor ficticio

2. La condición de la tarea se escribe en forma de tabla de transporte.

3. Se está construyendo una línea de base inicial

4. Se determinan los potenciales de suministros y consumidores

5. Se calculan las puntuaciones de celdas libres. Si no todos son negativos, el plan es óptimo y debe escribir la respuesta. La matriz de transporte X y determinar el monto de los costos de transporte. Si el plan no es óptimo, es decir, entre las estimaciones hay algunas negativas, elija una celda prometedora con el mayor valor negativo. estimar y pasar en magnitud a la siguiente.

6. Cargue una celda de perspectiva. Prepare un nuevo plano base en forma de tabla de transporte. Ir al punto 4.

54. Contabilidad del costo de producción y transporte de productos. Tarea de transporte con vedas de suministro.

Al resolver algunos problemas, es necesario tener en cuenta los costos no solo del transporte de mercancías, sino también de la producción de los productos transportados. Para ello, en la matriz transp. tareas

Donde Cij ' es el costo reducido de producir una unidad de producción.

Cij “- el costo de transportar una unidad de producción.

Tareas con vedas de suministro.

En algunas situaciones, no es posible transportar productos en ninguna ruta.

Para ello, en la matriz de la tarea de transporte, el transporte a través del cual está prohibido, se ingresa una tarifa prohibitiva M. Además, la tarea se resuelve de la manera habitual, sin embargo, esta celda siempre corresponderá a una puntuación de celda negativa.

55. teniendo en cuenta las restricciones en el rendimiento de las rutas, teniendo en cuenta la obligatoriedad de ciertas entregas en el problema del transporte.

teniendo en cuenta las restricciones en el rendimiento de las rutas.

En algunas tareas de transporte, en algunas rutas, un menor rendimiento de lo necesario para satisfacer la demanda del punto de consumo.

teniendo en cuenta la obligatoriedad de determinadas entregas en el problema del transporte.

En algunos casos, la tarea requiere que, por ejemplo, a lo largo de la ruta Ak Bs, se debe realizar la entrega en unidades del volumen A. En este caso, del volumen de producción del punto A y del volumen S Bs se descuenta el suministro obligatorio y se resuelve el problema con respecto al suministro facultativo. Después de obtener la solución óptima, el suministro se agrega necesariamente al volumen que se encuentra en la celda Ak Bs.

56. Posibles conclusiones con aspectos económicos. interpretación de la distribución óptima para problemas de transporte abiertos.

Una vez recibida la distribución óptima, es necesario volver al problema original y hacer la económica adecuada. conclusiones. Ellos son los siguientes:

1. Si se introduce un punto de consumo, significa que existen volúmenes de producción excesivos en el sistema analizado, y es posible, sin perjuicio del sistema considerado, reducir las capacidades de esos puntos de producción en la cantidad de vinculante que están atados al punto ficticio de consumo.

2. Si se introduce un punto de producción ficticio, significa que las capacidades de los puntos de producción reales no son suficientes y deben aumentarse. Se aumenta la capacidad de aquellos puntos de producción más cercanos a los puntos de consumo vinculados al punto de producción ficticio. La capacidad del fabricante se incrementa por el valor vinculante. Para ello, considere la columna del punto de consumo, que está ligada al punto de producción ficticio, y encuentre en ella la tarifa más baja. Es más eficiente aumentar la capacidad del punto de producción correspondiente a esta tarifa por el monto de la consolidación.

57. El concepto de dualidad. Formulación económica de problemas duales sobre el ejemplo del problema de optimización del plan de producción.

El problema dual es un problema auxiliar de programación lineal formulado usando ciertas reglas directamente de las condiciones del problema original o directo.

Que haya una tarea de optimizar el plan de producción. Se parece a esto:

Tarea inicial:

a 11 x 1 + a 12 x 2 +…+ a 1p x p ≤v 1 | 1

a 21 x 1 + a 22 x 2 +…+ a 2p x p ≤v 2 | a las 2

……………….. |.. (1)

A T 1 x 1 +a T 2 x 2 + ... + un T norte x norte ≤v 1 | en T

xj ≥0, j = 1,n(2)

z = c 1 x 1 +c 2 x 2 +…+c n x n ->max(3)

X \u003d (x 1, x 2, ..., x n)

a ij - la cantidad de materias primas del tipo i-ésimo, gastadas para la producción del tipo de producto j-ésimo

Doble problema

Deje que la empresa por cualquier motivo no pueda producir productos. Para reducir el costo del tiempo de inactividad, la empresa puede vender las materias primas que tiene. ¿A qué precio se deben vender las materias primas?

i - el precio del i-ésimo tipo de materia prima disponible en la empresa.

a 11 y 1 + a 21 y 2 + ... + a T 1 año T≥s 1

a 12 x 1 + a 22 y 2 + ... + a T 2 x norte ≥s 2

……………….. (1’)

A 1p y 1 +a 2p y 2 +…+ un tp en T≥s PAG

i ≥0, j = 1,m(2’)

F = b 1 y 1 +b 2 y 2 +…+b m y m ->min(3’)

58. Correspondencia entre los elementos estructurales de los problemas directo y dual

Cada problema de programación lineal se puede asociar

doble tarea de acuerdo con las siguientes reglas:

1. En todas las restricciones del problema original, los términos libres deben

estar a la derecha y los términos con incógnitas a la izquierda.

2. Las restricciones-desigualdades del problema original deben tener signos,

dirigida en una dirección.

3. Si se minimiza la función objetivo en el problema original, las restricciones de desigualdad se deben escribir con el signo "≤", entonces en el problema dual se minimizará la función objetivo y los signos de las restricciones de desigualdad serán "≥".

4. Cada restricción del problema original corresponde a una variable en

doble tarea Si una variable corresponde a una desigualdad, es no negativa, si corresponde a la igualdad, entonces la variable es sin restricciones en el signo ("arbitrario").

5. Los coeficientes de las variables en las restricciones del problema dual se obtienen transponiendo la matriz compuesta por

coeficientes para las variables del problema original.

6. Los términos libres del problema original son los coeficientes en

variables en la función objetivo del problema dual, y libre

términos en el problema dual son los coeficientes de las variables en

funciones del problema original También notamos que la relación de dualidad es mutua, es decir la tarea dual con respecto a la dual coincide con la original.Los pares duales de tareas se dividen en simétricos y asimétricos. En un par simétrico, las restricciones de los problemas primal y dual son desigualdades no estrictas y, por tanto, las variables de ambos problemas sólo pueden tomar valores no negativos.

59. Construcción de problemas duales a los problemas originales escritos en la forma estándar, canónica y general del modelo (construcción de problemas duales simétricos y asimétricos)

Formulario estándar (original)

Σ un ij x j ≤ segundo yo , i=1,n(1)

xj ≥0, j=1,n(2)

z = Σ c j x j ->max(3)

Doble estándar

Σ un ij y yo ≤ c j , j=1,n(1)

yi ≥0, j=1,m(2)

F = Σ segundo yo y yo ->min(3)

El problema original en forma canónica:

Σ a ij x j = segundo yo , i=1,m(1)

xj ≥0, j=1,n(2)

z = Σ c j x j ->min(3)

canónica dual

Σ un ij y yo ≤ c j , j=1,n(1)

y yo - cualquiera (2)

F = Σ segundo yo y yo ->max(3)

Démosle una interpretación económica a un par de problemas duales. Considere el problema del uso racional de los recursos. Deje que la empresa tenga recursos b1,b2,...bm que se pueden utilizar para producir n-tipos de productos. Conozcamos también el costo unitario del j-producto cj (j=1,n) y la tasa de consumo del i-ésimo recurso (i=1,m) para la producción j-ésimas unidades productos - aij Se requiere determinar el volumen de producción de cada tipo xj (j=1,n), maximizando el costo total

f= c1x1+…+cnxn (1)

Al mismo tiempo, el consumo de recursos no debe exceder su disponibilidad:

a11x1+…+a1nxn<=b1 }

…………………….. } (2)

am1x1+…+amnxn<=bm }

Todos los conocidos en su sentido económico son no negativos:

Xj>=0 (j=1,n). (3)

Tenga en cuenta que este problema forma un problema dual simétrico.

Problemas duales asimétricos.

Llevemos el ZLP al máximo en la forma canónica:

Máx. Z=(n;j=1)Σcj*xj

(n;j=1)Σaij*xj=bi (i=1,m)

Xj>=0 (j=1,n).

60. Teorema de dualidad principal y segundo (enunciar teoremas y explicar)

El primer teorema de la dualidad.

Teorema: si uno de los problemas duales tiene un plan óptimo, entonces el otro es solucionable, es decir tiene plan opt. En este caso los valores extremos de las funciones objetivo coinciden (j=de 1 a n) Σcjxj*= (i=de 1 a m)Σbiyi* si en el original. problema la función objetivo es ilimitada en el conjunto de planes, entonces en el problema dual el sistema de restricciones es inconsistente.

Segundo teorema de la dualidad y su interpretación económica.

Para que las soluciones factibles de un par de problemas duales sean óptimas, es necesario y suficiente que se cumpla la siguiente condición: xj*(∑aij yi*-cj)=0, j de 1 a n, yi*( ∑aij xj*-bi)=0, I de 1 a m. Estas son condiciones de holgura complementaria. De ellos se sigue: si alguna restricción del problema dual es convertida por el plan óptimo en igualdad estricta, entonces el componente correspondiente del opt. plan del problema dual debe ser igual a cero.Si se opta por algún componente. plan es igual a cero, entonces opt.plan convierte la restricción correspondiente del problema dual en una igualdad estricta xj*>0, por lo tanto (i= de 1 a m)Σaij yi*=cj opt.plan, entonces si costos>precios, volumen de producción=0 Σaij yi* >cj por lo tanto xj*=0

yi*>0 por lo tanto (j=de 1 a n) Σaij xj*=bi (carreras de recursos = stock de recursos).

(j=1 an) Σaij xj*

El significado del teorema es el siguiente:

Si la estimación de costos del consumo de recursos para la producción de una unidad de prod-ii \u003d precio, entonces este tipo de prod-ii se incluye en el plan óptimo;

Si los costos exceden el precio, entonces no se debe producir el prod-yu;

Si el consumo de recursos = existencias, entonces la estimación del costo de este recurso es positiva. Tal recurso se llama escaso. El más deficiente.res-s tiene la puntuación más alta;

Si el recurso no se gasta por completo, su costo estimado = 0.

61. Construcción del plan de soporte óptimo para el problema dual a partir de la tabla símplex del problema original

Información de las columnas de la matriz inversa de transformaciones lineales que llevaron al resultado óptimo. Las columnas de la matriz D-1 proporcionan información muy útil.

Columna A3: el precio "sombra" del recurso S2 es y01=0, la columna permanece

single y desde la primera línea se puede leer que x3=9, es decir al implementar el plan óptimo encontrado, el 1er recurso estará en exceso, y este exceso (subutilización) será de solo 9 unidades convencionales.

Columna A4: el precio "sombra" del recurso S2 es igual a y02=1, el recurso se utilizará en su totalidad y su posible aumento conducirá a un aumento en la función objetivo (es decir, el ingreso). Y porqué y02=1, entonces el aumento en el recurso S2 en 1 u.m. dará una adición en términos de ingresos por.Z = y02 · .w2 = = 1.1 = 1 (mil UAH) (aquí.w2 es el incremento del recurso S2 y .Z es el correspondiente incremento de ingresos). Con tal incremento del recurso S2, el ingreso máximo ya será Zmax=58 mil UAH. + 1 mil UAH = 59 mil UAH. En la fig. 6.2 ilustra esta situación, cuyo comentario se dará a continuación. También se deduce de la columna A4 que con un aumento en el recurso S2 de 1 u.m. para el nuevo punto óptimo, la producción de bienes T1 disminuirá en ½ tonelada (en la intersección de la fila de la variable básica x1 y la columna A4 es "-1/2"), y la producción de bienes T2 aumentará en 3 /2 toneladas (porque en la fila con la variable básica x2 en la columna A4 tenemos "3/2". Lo dicho sobre la columna A4 se comentará a continuación mediante construcciones gráficas (Fig. 6.2). Columna A5: la "sombra " precio del recurso S3 es igual a y03=2. Esto significa que un aumento en el recurso S3 por 1 u.m. traerá una adición en Z a.Z = y03 · .v3 = 2.1 =2(mil hryvnia) y será Zmax=58 mil hryvnia. + 2 mil UAH = 60 mil UAH. Al mismo tiempo, como sigue de la columna A5 de la Tabla. 3, la producción de T1 aumentará en ½ tonelada y la de T2 disminuirá en ½ tonelada. El stock de materias primas S1 (ver línea 1) aumentará en 3/2 u.m.

62. La idea del método de programación dinámica y su interpretación geométrica. Principio de optimalidad de Bellman.

La solución óptima del problema por el método de programación dinámica se encuentra sobre la base de la ecuación funcional

Para definirlo, necesitas:

1. escriba la ecuación funcional para el último estado del proceso (corresponde a l \u003d n-1)

fn-1(Sl-1)=óptimo(Rn(Sn-1,Un)+f0(Sn))

2. encontrar Rn(Sn-1,Un) a partir de un conjunto discreto de sus valores para unos Sn-1 y Un fijos de las áreas admisibles correspondientes (dado que f0(Sn)=0, entonces f1(Sn-1)= óptimo(Rn( Sn-1,Un)

Como resultado, después del primer paso, se conocen la solución Un y el valor correspondiente de la función f1(Sn-1).

3. Disminuye el valor de l en uno y escribe la ecuación funcional correspondiente. Para l=n-k (k= 2,n) parece

fk(Sn-k)=óptimo(Rn-k+1(Sn-k,Un-k+1)+fk-1(Sn-k+1)) (2)

4. encontrar una solución condicionalmente óptima basada en la expresión (2)

5. verificar a qué es igual el valor de l Si l=0, se completa el cálculo de soluciones condicionalmente óptimas y se encuentra la solución óptima del problema para el primer estado del proceso. Si l no es igual a 0, vaya al paso 3.

6. Calcular la solución óptima del problema para cada paso subsiguiente del proceso, moviéndose desde el final de los cálculos hasta el principio.

El método del dinamismo de programas permite reemplazar un problema con muchas variables por varios problemas resueltos sucesivamente con un número menor de variables. La decisión se toma paso a paso. El principio fundamental en el que se basa la optimización de un proceso de varios pasos, así como las características del método computacional, es el principio de optimización de Bellman.

El comportamiento óptimo tiene la propiedad de que cualquiera que sea el estado inicial y la decisión inicial, las decisiones posteriores deben ser óptimas con respecto al estado resultante de la decisión inicial.

Matemáticamente, se escribe como una expresión de la forma:

fn-1(Sl)=óptimo(Rl+1(Sl,Ul+1)+fn-(l+1)(Sl+1)) (1)

(l=0,n-1) Óptimo en la expresión significa el máximo o mínimo dependiendo de la condición del problema.

63. Requisitos para problemas resueltos por el método DP

La programación dinámica es un método matemático para encontrar soluciones óptimas a problemas de varios pasos. Un proceso de varios pasos es un proceso que se desarrolla con el tiempo y se divide en varios pasos o etapas.

Una de las características del método de programación dinámica es que las decisiones tomadas en relación con procesos de múltiples pasos no se consideran como un solo acto, sino como un conjunto completo de decisiones interrelacionadas. Esta secuencia de decisiones interrelacionadas se denomina estrategia. El objetivo de la planificación óptima es elegir una estrategia que proporcione el mejor resultado en términos de un criterio preseleccionado. Tal estrategia se llama óptima.

Otra característica importante del método es la independencia de la decisión óptima tomada en el siguiente paso de la prehistoria, es decir, sobre cómo el proceso que se está optimizando ha llegado a su estado actual. La solución óptima se elige solo teniendo en cuenta los factores que caracterizan el proceso en ese momento.

El método de los programas dinámicos también se caracteriza por el hecho de que la elección de la solución óptima en cada paso debe hacerse teniendo en cuenta sus consecuencias en el futuro. Esto significa que mientras optimiza el proceso en cada paso individual, en ningún caso debe olvidarse de todos los pasos posteriores.

64. Formulación económica y construcción de un modelo matemático del problema resuelto por el método DP (sobre el ejemplo del problema de la distribución de las inversiones de capital). Relación de recurrencia de Bellman.

Expliquemos preliminarmente que el método de programación dinámica se aplica principalmente a aquellos problemas en los que el proceso (o la situación) que se está optimizando se despliega en el espacio o en el tiempo, o en ambos.

Deje que el proceso (situación) en sí mismo sea tan complicado que no haya forma de optimizarlo utilizando métodos conocidos. Luego, de acuerdo con el método de programación dinámica, un proceso COMPLEJO (operación, situación) se divide (particiona) en varias etapas (pasos). Este desglose es en muchos casos natural, pero en el caso general se introduce artificialmente. . Por ejemplo, al considerar cualquier juego de ajedrez, cualquier movimiento de cada uno de los jugadores solo sirve

dividir el lote completo en pasos separados (etapas). Y en una operación militar para perseguir un misil contra otro, todo el proceso continuo tiene que dividirse artificialmente en etapas, por ejemplo, cada segundo de observación. El método de programación dinámica permite sustituir la optimización de todo el complejo proceso por una optimización condicional para cada una de las etapas

(pasos) seguidos de la síntesis del control óptimo de todo el proceso. Al mismo tiempo, el método establece que la optimización condicional en un paso (etapa) separado se realiza en interés, en primer lugar, de toda la operación.

Todos los cálculos que permiten encontrar el valor óptimo del efecto logrado en n pasos, fn(S0), se realizan de acuerdo con la fórmula (1), que se denomina ecuación funcional básica de Bellman o relación de recurrencia. Al calcular el siguiente valor de la función fn-1, se utiliza el valor de la función fn-(l+1) obtenido en el paso anterior, y el valor directo del efecto Rl+1(Sl,Ul+1), se logra como resultado de elegir la solución Ul+1 para un sistema Sl de estado dado. El proceso de calcular el valor de la función fn-1(l=0,n-1)

Se realiza bajo la condición inicial natural f0(Sn)=0, lo que significa que fuera del estado final del sistema, el efecto es cero.

65. El problema de la distribución de las inversiones de capital (ejemplo).

Para resolver el problema de la distribución óptima de las inversiones de capital, utilizaremos la ecuación funcional de Bellman. Primero, usando la situación más simple, ilustraremos la derivación de la ecuación funcional de Bellman, y luego, usando un ejemplo, demostraremos cómo usar esta ecuación para resolver el problema que nos interesa.

Comencemos con la distribución óptima de las inversiones de capital asignadas en la cantidad de K entre dos empresas. Los departamentos de planificación de las empresas, sobre la base de sus cálculos, formaron las funciones de ingreso q(x) para la empresa P1 y h(x) para la empresa P2. Estas funciones significan que si la primera o la segunda empresa recibe una inversión por la cantidad de x, entonces la primera empresa

se recibirá la renta q(x), y la segunda h(x), y el valor de x puede tomar valores continuos o discretos conocidos de 0 a K.

Entonces, deje que la empresa P1 asigne inversiones de capital en la cantidad x, luego a la empresa P2 se le asigna la cantidad K - x. En este caso, la renta q(x) se recibirá de la primera empresa y h(K - x) de la segunda. Si las inversiones K se asignaron para un período de planificación, entonces el ingreso total de las dos empresas será R(K, x) = q(x) + h(K - x). Obviamente, x y, en consecuencia, K - x deben elegirse de manera que R(K, x) tome su valor máximo, que denotaremos por F(K):

Esta entrada es como un esqueleto para entradas más completas.

ecuación funcional de Bellman. COMPLICAR nuestra tarea distribuyendo las inversiones de capital en dos períodos de planificación (dos etapas) . Decida inicialmente asignar la cantidad x a la primera empresa P1 yx a la segunda empresa P1. En general, la renta sería igual a R(K, x) = q(x) +

h(K - x). Si tenemos en cuenta que las inversiones se distribuyen en 2 períodos (2 etapas), entonces en la primera empresa el saldo de inversiones será x, donde , y en la segunda - .(K - x), donde En consecuencia, el ingreso para el segundo período será q( .x) - según la primera facilidad y h[.(K - x)] - según la segunda. La optimización de la programación dinámica, por regla general, comienza desde la etapa final. Por lo tanto, partimos de la segunda etapa, denotando F1 el máximo ingreso posible de dos empresas en la segunda

escenario. Conseguir

Luego, a la última etapa considerada (en nuestro caso, la segunda), añadimos la etapa anterior (en nuestro caso, la primera) y encontramos el ingreso máximo de las dos etapas juntas:

De manera similar, para n etapas, obtenemos

donde Fn-1 es la función objetivo que da el mejor resultado para las últimas (n - 1) etapas. La ecuación de Bellman funcional resultante es recurrente, es decir asocia el valor Fn con el valor Fn-1.

Más generalmente, la ecuación de Bellman tiene la forma

donde , Fn-1 - ingreso máximo para (n - 1) últimas etapas, Fn -

ingresos máximos para todas las n etapas.

66. El concepto de resolución de problemas de programación no lineal

Plantéese el problema de la programación no lineal de la siguiente forma general: encuentre tales valores de las variables x1, x2,..., xn que cumplan las condiciones:

y traer el extremo requerido (máximo o mínimo) de la función objetivo

f = f(x1, x2,…, xn), (13.2)

donde f(х1, …, хn) y qi(х1, …, хn) (m , 1 i =) son reales no lineales,

funciones regulares de n variables reales.

De acuerdo con sus propiedades generales, los problemas de programación no lineal pueden

significativamente diferentes de las lineales. Por ejemplo, el dominio de las soluciones factibles puede que ya no sea convexo, y el extremo de la función objetivo puede observarse en cualquier punto del dominio factible. Los métodos para resolver problemas no lineales también difieren significativamente. Consideremos sólo algunos enfoques para resolver estos problemas.

En primer lugar, el enfoque gráfico también es válido para resolver los problemas más simples de programación no lineal. Entonces, si las variables x1 y x2 son los argumentos del problema, primero se construye el área de soluciones factibles en el plano de estas variables, y luego se determina el punto óptimo en el área utilizando los niveles de la función objetivo. f(x1,x2).

En la programación no lineal, se utiliza un enfoque de gradiente para resolver muchos problemas. Hay una serie de métodos de gradiente, cuya esencia es encontrar el resultado óptimo utilizando el gradiente de la función objetivo, un vector que indica la dirección del aumento máximo en la meta para el punto considerado. En el caso general, el procedimiento de búsqueda se realiza de forma iterativa desde el punto seleccionado inicialmente hasta los puntos con mejor indicador. Sea, por ejemplo, . - dominio de soluciones admisibles

problema considerado, y el proceso iterativo de cálculos comienza desde el punto

Además, primero se hace una transición a lo largo del gradiente de la función objetivo y luego se regresa al área. a lo largo del gradiente hasta el límite perturbado de la región O2 O3. 13.3 se muestra de modo que Ai con índices impares pertenecen al área., y los puntos Ai con índices pares no.A medida que nos acercamos al punto óptimo Q, las direcciones de los gradientes de trabajo convergen. Por lo tanto, el criterio ideal para detener el proceso será la colinealidad del gradiente objetivo y el gradiente límite roto.

67. El concepto de programación paramétrica y entera .

Enunciado y modelo matemático de ZCLP.

En problemas con objetos indivisibles, se imponen condiciones de número entero a las variables. A veces estas condiciones se aplican a todas las variables, a veces a algunas de las variables Considere un problema completamente entero

f=(n,j=1)∑CjXi máx.

(n,j=1)∑AijXj=bi, i=1,m

xi-entero,j=1,n

Ahora, a diferencia del problema general de programación lineal, el plan óptimo no estará necesariamente en el vértice del poliedro del plan.Existen los siguientes métodos para resolver problemas de números enteros:

1. Métodos de recorte

2. Combinatorio

3. Métodos aproximados.

La programación paramétrica es una rama de la programación matemática dedicada al estudio de problemas de optimización en los que las condiciones de admisibilidad y la función objetivo dependen de unos parámetros deterministas.

Definición. Programación lineal (PL) - la ciencia de los métodos de investigación y la búsqueda de valores extremos (máximos y mínimos) de una función lineal, sobre cuyas incógnitas se imponen restricciones lineales.

Esta función lineal se llama objetivo, y las restricciones que se escriben matemáticamente como ecuaciones o desigualdades se denominan sistema de restricciones.

Definición. La expresión matemática de la función objetivo y sus restricciones se llama modelo matemático del problema económico.

En general, el modelo matemático de un problema de programación lineal (LP) se escribe como

con restricciones:

Dónde x j- desconocido; aij, b yo, cj se dan constantes.

Todas o algunas ecuaciones del sistema de restricciones se pueden escribir como desigualdades.

El modelo matemático en una notación más corta tiene la forma

con restricciones:

Definición. Una solución factible (plan) de un problema de programación lineal es un vector = ( X 1 , X 2 ,..., xp), satisfacer el sistema de restricciones.

El conjunto de soluciones admisibles forma la región de soluciones admisibles (ODD).

Definición. Una solución factible, en la que la función objetivo alcanza su valor extremo, se denomina solución óptima del problema de programación lineal y se denota como opt.

Solución básica admisible (X 1 , X 2 ,...,X r , 0, …, 0) es una solución de referencia, donde r- el rango del sistema de restricciones.

El modelo matemático del problema de PL puede ser canónico y no canónico.

7. Resolver problemas de programación lineal por un método gráfico. Gráficas de funciones de restricción. Líneas de nivel.

Método gráfico para resolver problemas de programación lineal

El método más simple y más visual de programación lineal es el método gráfico. Se utiliza para resolver problemas de PL con dos variables dadas en forma no canónica y muchas variables en forma canónica, siempre que no contengan más de dos variables libres.

Desde un punto de vista geométrico, en un problema de programación lineal, se busca tal punto de esquina o un conjunto de puntos de un conjunto admisible de soluciones en el que se alcanza la línea de nivel más alto (inferior), ubicada más lejos (más cerca) que el otros en la dirección de crecimiento más rápido.

Para encontrar el valor extremo de la función objetivo en la solución gráfica de problemas de PL se utiliza el vector L() en la superficie X 1 OH 2 , que denotamos . Este vector muestra la dirección del cambio más rápido en la función objetivo. En otras palabras, el vector es la normal de la línea de nivel L()

Dónde mi 1 y mi 2 - vectores unitarios a lo largo de los ejes BUEY 1 y BUEY 2 respectivamente; por lo tanto = (∂L/∂x 1 , ∂L/∂х 2 ). Las coordenadas vectoriales son los coeficientes de la función objetivo. L(). La construcción de la línea de nivel se considerará en detalle al resolver problemas prácticos.

Algoritmo de resolución de problemas

1. Encontramos el área de soluciones factibles para el sistema de restricciones del problema.

2. Construyendo un vector .

3. Dibujar una línea de nivel L 0 , que es perpendicular .

4. Movemos la línea de nivel en la dirección del vector para tareas al máximo y en la dirección opuesta , para tareas mínimas.

Se desplaza la línea de nivel hasta que tenga un único punto en común con la zona de soluciones factibles. Este punto, que determina la solución única del problema de PL, será el punto extremo.

Si resulta que la línea de nivel es paralela a uno de los lados de la ODT, entonces en este caso se alcanza el extremo en todos los puntos del lado correspondiente, y el problema de PL tendrá infinitas soluciones. Se dice que tal problema de LP tiene óptimo alternativo y su solución viene dada por la fórmula:

donde 0 ≤ t≤ 1, 1 y 2 - soluciones óptimas en los puntos de esquina del ODS.

Un problema de PL puede ser irresoluble cuando las restricciones que lo definen resultan contradictorias.

5. Encontramos las coordenadas del punto extremo y el valor de la función objetivo en él.

Ejemplo 3 Elegir la mejor opción de lanzamiento del producto

La empresa produce 2 tipos de helado: crema y chocolate. Para la fabricación de helados, se utilizan dos productos iniciales: leche y rellenos, cuyos costos por 1 kg de helado y suministros diarios se dan en la tabla.

La investigación de mercado mostró que la demanda diaria de helado de mantequilla supera la demanda de helado de chocolate, pero en no más de 100 kg.

Además, se encontró que la demanda de helado de chocolate no supera los 350 kg por día. El precio de venta al público de 1 kg de helado cremoso es de 16 rublos, chocolate - 14 rublos.

¿Qué cantidad de cada tipo de helado debe producir la empresa para maximizar sus ingresos por ventas?

Solución. Denotar: X 1 - volumen diario de producción de helado cremoso, kg; X 2 - producción diaria de helado de chocolate, kg.

Hagamos un modelo matemático del problema.

Se conocen los precios del helado: 16 rublos y 14 rublos, respectivamente, por lo que la función objetivo se verá así:

Establezca límites en la leche para helados. Su consumo para helado de crema es de 0,8 kg, para helado de chocolate - 0,5 kg. Stock de leche 400kg. Por lo tanto, la primera desigualdad se verá así:

0.8x 1 + 0.5x 2 ≤400 - la primera desigualdad es una restricción. El resto de las desigualdades se construyen de manera similar.

El resultado es un sistema de desigualdades. cual es el area solucion de cada desigualdad. Esto se puede hacer sustituyendo las coordenadas del punto O(0:0) en cada una de las desigualdades. Como resultado, obtenemos:

Cifra OABDEF- dominio de soluciones admisibles. Construimos el vector (16; 14). línea de nivel L 0 viene dado por la ecuación 16x 1 +14x 2 =Const. Elegimos cualquier número, por ejemplo el número 0, luego 16x 1 +14x 2 =0. En la figura, para la recta L 0 se elige algún número positivo, distinto de cero. Todas las líneas de nivel son paralelas entre sí. El vector normal de la línea de nivel.

Mueva la línea de nivel en la dirección del vector. punto de salida L 0 de la región de soluciones factibles es el punto D, sus coordenadas se definen como la intersección de las rectas dadas por las ecuaciones:

Resolviendo el sistema, obtenemos las coordenadas del punto D(312.5; 300), en la que habrá una solución óptima, es decir

Así, la empresa debe producir 312,5 kg de helado de mantequilla y 300 kg de helado de chocolate al día, mientras que los ingresos por ventas serán de 9.200 rublos.

8. Reducción de un problema de programación lineal arbitrario al problema principal. Convertir restricciones dadas por desigualdades en ecuaciones correspondientes.

9. Método símplex. Características y algoritmo del método, su aplicabilidad.

Para resolver el problema por el método símplex, es necesario:

1. Indique un método para encontrar la solución de referencia óptima

2. Especifique el método de transición de una solución de referencia a otra, en la que el valor de la función objetivo estará más cerca del óptimo, es decir. indicar una forma de mejorar la solución de referencia

3. Establezca criterios que le permitan detener oportunamente la enumeración de soluciones de referencia en la solución óptima o pasar una conclusión sobre la ausencia de una solución óptima.

Algoritmo del método simplex para la resolución de problemas de programación lineal

1. Llevar el problema a la forma canónica

2. Encontrar la solución de soporte inicial con "base unitaria" (si no hay solución de soporte, entonces el problema no tiene solución, debido a la incompatibilidad del sistema de restricciones)

3. Calcular estimaciones de expansiones vectoriales en términos de la base de la solución de referencia y completar la tabla del método simplex

4. Si se cumple el criterio de unicidad de la solución óptima, entonces la solución del problema termina

5. Si se cumple la condición para la existencia de un conjunto de soluciones óptimas, entonces por simple enumeración, se encuentran todas las soluciones óptimas

10. Tarea de transporte. Definición, tipos, métodos para encontrar la solución inicial del problema del transporte.

El problema del transporte es uno de los problemas de programación lineal más comunes. Su objetivo es desarrollar las formas y los medios más racionales para el transporte de mercancías, eliminando el transporte repetido, excesivo y de larga distancia.

1. Encontrar la solución de referencia inicial;

2. Comprobación de la optimización de esta solución;

3. Transición de una solución básica a otra.

Conferencia 2

EN forma canónica

solución admisible del PLP(plan aceptable).

solución óptima de la LLP.

Necesidad

Ejemplo.

Escribamos el problema en forma canónica

Situaciones especiales de la solución gráfica del ZLP

Excepto cuando la tarea es la única solución óptima para y , puede ser situaciones especiales:

1. la tarea tiene un número infinito de soluciones óptimas – el extremo de la función se alcanza en el segmento ( óptimo alternativo)- Figura 2;

2. tarea no solucionable debido al carácter ilimitado de la ODR, o - Figura 3;

3. ODR - punto único Ah, entonces;

4. tarea no solucionable si el ODR tiene un área vacía.

A

Figura 2 Figura 3

Si la línea de nivel es paralela al lado del área de soluciones factibles, entonces se alcanza el extremo en todos los puntos del lado. El problema tiene un número infinito de soluciones óptimas - óptimo alternativo . La solución óptima se encuentra por la fórmula

donde esta el parametro. Para cualquier valor de 0 a 1, puede obtener todos los puntos del segmento, para cada uno de los cuales la función toma el mismo valor. De ahí el nombre - óptimo alternativo.

Ejemplo. Resuelva gráficamente el problema de programación lineal ( óptimo alternativo):

Preguntas para el autocontrol.

1. Escriba el problema de programación lineal en forma general.

2. Escriba el problema de programación lineal en forma canónica y estándar.

3. ¿Qué transformaciones se pueden usar para pasar de la forma general o estándar de un problema de programación lineal a uno canónico?

4. Dar una definición de soluciones factibles y óptimas al problema de programación lineal.

5. ¿Cuál de las soluciones es la “mejor” para el problema de minimizar la función si ?

6. ¿Cuál de las soluciones es la “mejor” para el problema de maximizar la función si ?

7. Escriba la forma estándar del modelo matemático de un problema de programación lineal con dos variables.

8. Cómo construir un semiplano dado por una desigualdad lineal con dos variables ?

9. ¿Cómo se llama la solución de un sistema de desigualdades lineales con dos variables? Construya en el plano el dominio de soluciones factibles de tal sistema de desigualdades lineales, que:

1) tiene una solución única;

2) tiene un conjunto infinito de soluciones;

3) no tiene solución.

10. Escribe para una función lineal degradado vectorial, nombre el tipo de líneas de nivel. ¿Cómo se ubican las líneas de gradiente y de nivel entre sí?

11. Formule un algoritmo para un método gráfico para resolver un LLP estándar con dos variables.

12. ¿Cómo encontrar las coordenadas y valores de la solución?

13. Construir el área de soluciones factibles, líneas de gradiente y de nivel, para problemas de programación lineal en los que:

1) se alcanza en un solo punto, y - en el segmento ODR;

2) se alcanza en un solo punto del ODS, y .

14. Proporcione una ilustración geométrica del LLP si:

1) tiene soluciones óptimas únicas para y ;

2) tiene un conjunto de soluciones óptimas para .

Conferencia 2

metodo grafico para encontrar la solucion optima

1. Formas de modelos matemáticos lineales y su transformación.

2. Método gráfico para resolver un problema de programación lineal

3. SITUACIONES ESPECIALES DE LA SOLUCIÓN GRÁFICA DE LLP

4. Solución gráfica de problemas económicos de programación lineal

Formas de modelos matemáticos lineales y su transformación.

Un modelo matemático de un problema de programación lineal (LPP) se puede escribir en una de tres formas.

EN forma general del modelo matemático se requiere encontrar el máximo o mínimo de la función objetivo; el sistema de restricciones contiene desigualdades y ecuaciones; no todas las variables pueden ser no negativas.

EN forma canónica el modelo matemático necesita encontrar el máximo de la función objetivo; el sistema de restricciones consta únicamente de ecuaciones; todas las variables son no negativas.

En la forma estándar de un modelo matemático, se requiere encontrar el máximo o mínimo de una función; todas las restricciones son desigualdades; todas las variables son no negativas.

La solución del sistema de restricciones que satisface las condiciones de no negatividad de las variables se denomina solución admisible del PLP(plan aceptable).

El conjunto de soluciones factibles se llama el área de soluciones factibles de la LLP.

Una solución factible, en la que la función objetivo alcanza un valor extremo, se llama solución óptima de la LLP.

Las tres formas del LLP son equivalentes en el sentido de que cada una de ellas puede reducirse a una forma diferente con la ayuda de transformaciones matemáticas.

Necesidad transición de una forma de modelo matemático a otra asociado con métodos para resolver problemas: por ejemplo, el método simplex, muy utilizado en programación lineal, se aplica a un problema escrito en forma canónica, y el método gráfico se aplica a la forma estándar de un modelo matemático.

Transición a la notación canónica ZLP.

Ejemplo.

Escribamos el problema en forma canónica, introduciendo una variable adicional (equilibrio) con el signo “+” en el lado izquierdo de la primera desigualdad del sistema de restricciones, y una variable adicional con el signo “menos” en el lado izquierdo de la segunda desigualdad.

El significado económico de varias variables adicionales puede no ser el mismo: depende del significado económico de las restricciones en las que se incluyen estas variables.

Entonces, en el problema del uso de materias primas, muestran el resto de las materias primas, y en el problema de elegir tecnologías óptimas, muestran el tiempo no utilizado de la empresa que usa cierta tecnología; en el problema del corte: la liberación de espacios en blanco de una longitud dada por encima del plan, etc.