La definición correcta del concepto de investigación de operaciones es: Tema y tareas de la investigación operativa.

1. Conceptos básicos de IA

Y SOBRE – disidencia científica, comprometida con el desarrollo y la aplicación práctica de métodos para la gestión más eficaz de diversos sistemas organizativos.

El IO incluye las siguientes secciones:

1) programa matemático. (justificación de planes, programas de actividad económica); Incluye secciones: programa lineal, programa no lineal, programa dinámico.

2) teoría de colas, basada en la teoría de procesos aleatorios;

3) teoría de juegos, que permite justificar decisiones tomadas en condiciones de información incompleta.

Al resolver un problema de control específico, el uso de métodos de IA implica:

Construcción de modelos económicos y matemáticos para problemas de toma de decisiones en situaciones complejas o en condiciones de incertidumbre;

Estudiar las relaciones que posteriormente determinan la toma de decisiones y establecer criterios de actuación que permitan evaluar la ventaja de una determinada conducta.

Conceptos básicos y definiciones de OI.

Operación – Cualquier actividad controlada encaminada a lograr un objetivo. El resultado de la operación depende del método de implementación y organización; de lo contrario, de la elección de ciertos parámetros. Una operación es siempre un evento controlado, es decir, de nosotros depende cómo elegir algunos parámetros que caractericen su organización. Se entiende aquí por “organización” en el sentido amplio de la palabra, incluyendo el conjunto de medios técnicos utilizados en la operación.

Cualquier elección específica de parámetros se llama decisión . Las decisiones pueden ser exitosas o no, razonables o irrazonables. Óptimo considerar aquellas soluciones que, por una razón u otra, son preferibles a otras. La principal tarea de la investigación operativa es la justificación cuantitativa preliminar de soluciones óptimas.

Modelo de operación – Esta es una descripción bastante precisa de la operación utilizando aparatos matemáticos (diversos tipos de funciones, ecuaciones, sistemas de ecuaciones y desigualdades, etc.). Elaborar un modelo de operación requiere comprender la esencia del fenómeno que se describe y el conocimiento del aparato matemático.

Eficiencia operativa – el grado de adaptabilidad a la tarea se expresa cuantitativamente en forma de criterio de eficiencia: la función objetivo. La elección del criterio de eficacia determina el valor práctico del estudio. (Un criterio elegido incorrectamente puede ser perjudicial, ya que las operaciones organizadas en función de dicho criterio de eficiencia a veces generan costos injustificados).

Tareas de planificación y gestión de redes. considerar la relación entre las fechas de finalización de un gran complejo de operaciones (obras) y las horas de inicio de todas las operaciones del complejo. Estas tareas consisten en encontrar la duración mínima de un conjunto de operaciones, la relación óptima de los valores de costos y el momento de su implementación.

Problemas de cola se dedican al estudio y análisis de sistemas de servicio con colas de aplicaciones o requerimientos y consisten en determinar los indicadores de desempeño de los sistemas, sus características óptimas, por ejemplo, determinar el número de canales de servicio, tiempo de servicio, etc.

Tareas de gestión de inventario. Consisten en encontrar los valores óptimos de nivel de inventario (punto de pedido) y tamaño del pedido. La peculiaridad de tales tareas es que con un aumento en el nivel de inventarios, por un lado, aumentan los costos de almacenamiento, pero por otro lado, disminuyen las pérdidas por una posible escasez del producto almacenado.

Problemas de asignación de recursos surgen durante un determinado conjunto de operaciones (obras) que deben realizarse con recursos disponibles limitados, y es necesario encontrar la distribución óptima de los recursos entre operaciones o la composición de las operaciones.

Tareas de reparación y sustitución de equipos. son relevantes debido al desgaste de los equipos y la necesidad de reemplazarlos con el tiempo. Las tareas se reducen a determinar el momento óptimo, el número de reparaciones e inspecciones preventivas, así como cuándo reemplazar los equipos por equipos modernizados.

Programar (programar) tareas consisten en determinar la secuencia óptima de operaciones (por ejemplo, procesamiento de piezas) en varios tipos de equipos.

Tareas de planificación y colocación. nia consisten en determinar el número y la ubicación óptimos de nuevos objetos, teniendo en cuenta su interacción con los objetos existentes y entre sí.

Problemas de selección de ruta o red Los problemas que se encuentran con mayor frecuencia en el estudio de diversos problemas en los sistemas de transporte y comunicaciones y consisten en determinar las rutas más económicas.

2. Problema general de programa lineal. Optimizando la solución

Modelo económico-matemático

LP es una rama de las matemáticas que desarrolla la teoría y los métodos numéricos para resolver problemas de encontrar el extremo (máximo o mínimo) de una función lineal de muchas variables en presencia de restricciones lineales, es decir, igualdades o desigualdades que conectan estas variables.

Los métodos LP se aplican a problemas prácticos en los que: 1) es necesario seleccionar la mejor solución (plan óptimo) entre una variedad de posibles; 2) la solución se puede expresar como un conjunto de valores de algunas variables; a) las restricciones impuestas a las soluciones factibles por condiciones específicas del problema se formulan en forma de ecuaciones lineales o desigualdades; 4) el objetivo se expresa en forma de función lineal de las variables principales. Los valores de la función objetivo, que permiten comparar diferentes soluciones, sirven como criterio para la calidad de la solución.

Para resolver prácticamente un problema económico utilizando métodos matemáticos, en primer lugar se debe escribir utilizando un modelo económico-matemático. Un modelo económico-matemático es una descripción matemática del proceso económico u objeto en estudio. Este modelo expresa las leyes del proceso económico de forma abstracta utilizando relaciones matemáticas.

Esquema general de formación de modelos: I

1) selección de un cierto número de cantidades variables, cuya asignación de valores numéricos determina de forma única uno de los posibles estados del fenómeno en estudio;

2) expresión de las relaciones inherentes al fenómeno en estudio en forma de relaciones matemáticas (ecuaciones, desigualdades). Estas relaciones forman un sistema de restricciones para el problema;

3) expresión cuantitativa del criterio de optimización seleccionado en forma de función objetivo; I

4) formulación matemática del problema como problema de encontrar el extremo de la función objetivo, sujeto al cumplimiento de las restricciones impuestas a las variables.

Problema general de programación lineal tiene la forma:

Dado un sistema de m ecuaciones lineales y desigualdades con n variables

y función lineal

Es necesario encontrar una solución al sistema X=(x1,x2,…,xj,…,xn), donde la función lineal F toma el valor óptimo (es decir, máximo o mínimo).

El sistema (1) se denomina sistema de restricciones y la función F se denomina función lineal, forma lineal, función objetivo o función meta.

Más brevemente, el problema general de programación lineal se puede representar como:

con restricciones:

Solución óptima (o plan óptimo) de un problema PL es una solución X=(x1,x2,…,xj,…,xn), un sistema de restricciones (1), que satisface la condición (3), bajo la cual la función lineal (2) toma el valor óptimo (máximo o mínimo) valor.

Siempre que todas las variables no sean negativas, el sistema de restricciones (1) consta únicamente de desigualdades; este problema de programación lineal se llama estándar (simétrico); si el sistema de restricciones consta únicamente de ecuaciones, entonces el problema se llama canónico.

Un caso especial de un problema canónico es un problema en forma básica, caracterizado porque todos los coeficientes del vector de restricción b son no negativos y en cada ecuación hay una variable con un coeficiente de 1 que no está incluida en ninguna de las otras ecuaciones. Una variable con esta propiedad se llama básica.

Los problemas estándar y canónicos son casos especiales del general. Cada uno de ellos se utiliza en su área específica. Además, las tres formulaciones son equivalentes entre sí: cualquier problema de programación lineal se puede reducir a un problema canónico, estándar o general mediante transformaciones matemáticas simples.

4 . Elementos de álgebra lineal

Un sistema de m ecuaciones lineales con n variables tiene la forma

o en forma corta

Cualesquiera m variables de un sistema de m ecuaciones lineales con n variables (m< n) называются основными (или базисными), если определитель матрицы коэффициентов при них отличен от нуля. Такой определитель часто называют базисным минором матрицы А. Тогда остальные m–n переменных называются неосновными (или свободными).

Resolver el sistema (2.1) bajo la condición m< n сформулируем утверждение.

Declaración 2.1. Si por el sistemametroecuaciones lineales connortevariables (metro < norte) el rango de la matriz de coeficientes de las variables es igual a m, es decir Si hay al menos un grupo de variables básicas, entonces este sistema es indeterminado y cada conjunto arbitrario de valores de variables no básicas corresponde a una solución del sistema.

Solución X=(x1,x2,…,xn) del sistema (2.1) se considera admisible si contiene solo componentes no negativos, es decir xj>=0 para cualquier j=1,n. De lo contrario, la solución se considera inválida.

Entre la infinidad de soluciones del sistema se distinguen las llamadas soluciones básicas.

Solución básica de un sistema de m ecuaciones lineales con n variables es una solución en la que todas las n–m variables menores son iguales a cero.

En los problemas de programación lineal, son de particular interés las soluciones básicas admisibles o, como también se les llama, planes de referencia. Una solución básica en la que al menos una de las variables principales es igual a cero se llama degenerada.

Conjuntos de puntos convexos.

La propiedad definitoria común que distingue un polígono convexo de uno no convexo es que si tomas dos de sus puntos y los conectas con un segmento, entonces todo el segmento pertenecerá a ese polígono. Esta propiedad se puede tomar para definir un conjunto convexo de puntos.

Un conjunto de puntos se llama convexo., si, junto con dos de sus puntos cualesquiera, contiene el segmento completo que conecta estos puntos.

Los conjuntos convexos tienen una importante propiedad: La intersección (parte común) de cualquier número de conjuntos convexos es un conjunto convexo.

Entre los puntos de un conjunto convexo, se pueden distinguir los puntos internos, los límites y los vértices.

Un punto de un conjunto se llama interno., si parte de su vecindad contiene puntos únicamente de este conjunto.

Un punto de un conjunto se llama punto límite., si cualquiera de sus vecindades contiene tanto puntos que pertenecen al conjunto dado como puntos que no le pertenecen.

De particular interés en los problemas de programación lineal son los puntos de esquina. El punto del conjunto se llama angular(o extremo), si no es interno a ningún segmento que pertenezca enteramente al conjunto dado.

En la Fig. 2.4 muestra ejemplos de varios puntos de un polígono: interior (punto M), límite (punto N) y esquina (puntos A, B, C, D, E). El punto A es un punto de esquina, ya que para cualquier segmento que pertenezca enteramente a un polígono, por ejemplo, el segmento AP, no es interno; El punto A es interno al segmento KL, pero este segmento no pertenece enteramente al polígono.

Para un conjunto convexo, los puntos de las esquinas siempre coinciden con los vértices del polígono (poliedro), mientras que para un conjunto no convexo esto no es necesario. Un conjunto de puntos se llama cerrado si incluye todos sus puntos límite. El conjunto de puntos se llama limitado, si hay una bola (círculo) de radio de longitud finita con centro en cualquier punto del conjunto, que contiene completamente el conjunto dado; en caso contrario se dice que el conjunto es ilimitado.

Un conjunto cerrado convexo de puntos en un plano que tiene un número finito de puntos de esquina se denomina polígono convexo si está acotado y región poligonal convexa si no está acotado.

Significado geométrico de las soluciones a desigualdades, ecuaciones y sus sistemas.

Consideremos soluciones a las desigualdades.

Enunciado 1. El conjunto de soluciones a la desigualdad con dos variables a11x1+a12x2<=b1 является одной из двух полуплоскостей, на которые вся плоскость делится прямой a11x1+a12x2=b1 , включая и эту прямую, а другая полуплоскость с той же прямой есть множество решений неравен­ства a11x1+a12x2>=b1.

Para determinar el semiplano deseado (superior o inferior), se recomienda establecer un punto de control arbitrario que no se encuentre en su límite: la línea recta construida. Si una desigualdad se cumple en un punto de control, entonces se cumple en todos los puntos del semiplano que contiene el punto de control, y no se cumple en todos los puntos del otro semiplano. Por el contrario, si una desigualdad no se satisface en un punto de control, no se satisface en todos los puntos del semiplano que contiene el punto de control y se satisface en todos los puntos del otro semiplano. Es conveniente tomar como punto de control el origen de coordenadas O (0;0), que no se encuentra en la línea construida.

Consideremos un conjunto de soluciones a sistemas de desigualdades.

Enunciado 2. El conjunto de soluciones de un sistema conjunto de desigualdades lineales en dos variables es un polígono convexo (o una región poligonal convexa).

Cada una de las desigualdades, de acuerdo con el Enunciado 1, define uno de los semiplanos, que es un conjunto convexo de puntos. El conjunto de soluciones de un sistema conjunto de desigualdades lineales son puntos que pertenecen a los semiplanos de soluciones de todas las desigualdades, es decir pertenecen a su intersección. Según la afirmación sobre la intersección de conjuntos convexos, este conjunto es convexo y contiene un número finito de puntos de esquina, es decir es un polígono convexo (un área poligonal convexa).

Las coordenadas de los puntos de las esquinas (los vértices del polígono) se encuentran como las coordenadas de los puntos de intersección de las líneas correspondientes.

Al construir áreas de solución para sistemas de desigualdades, pueden ocurrir otros casos: el conjunto de soluciones es un área poligonal convexa (figura 2.9, a); un punto (Fig. 2.9, b); un conjunto vacío cuando el sistema de desigualdades es inconsistente (figura 2.9, c).

5 . Método geométrico para resolver problemas de LP.

solución óptima al problema de LP

Teorema 1. Si el problema LP tiene una solución óptima, entonces la función lineal toma su valor máximo en uno de los puntos de las esquinas del poliedro solución. Si una función lineal toma un valor máximo en más de un punto de esquina, entonces lo toma en cualquier punto que sea una combinación lineal convexa de estos puntos.

El teorema indica la forma fundamental de resolver problemas de PL. De hecho, según este teorema, en lugar de estudiar un conjunto infinito de soluciones factibles para encontrar la solución óptima deseada entre ellas, es necesario estudiar sólo un número finito de puntos vértices del poliedro solución.

El siguiente teorema está dedicado al método analítico para encontrar puntos de esquina.

Teorema 2. Cada solución básica admisible del problema LP corresponde a un punto vértice del poliedro solución, y viceversa, a cada punto vértice del poliedro solución corresponde una solución básica admisible.

Un corolario importante se desprende directamente de los teoremas 1 y 2: Si un problema de PL tiene una solución óptima, entonces coincide con al menos una de sus soluciones básicas admisibles.

Entonces, el óptimo de la función lineal del problema PL debe buscarse entre el número finito de sus soluciones básicas admisibles.

Entonces, el conjunto de soluciones factibles (poliedro de solución) del problema LP es un poliedro convexo (o región poliédrica convexa), y la solución óptima del problema se ubica al menos en uno de los puntos de las esquinas del poliedro de solución.

Considere el problema en forma estándar con dos variables. (PAG = 2).

Sea la imagen geométrica del sistema de restricciones un polígono. A B C D E(Figura 4.1). Es necesario encontrar un punto entre los puntos de este polígono en el que la función lineal F=c1x1+c2x2 tome el valor máximo (o mínimo).

Consideremos el llamado línea de nivel función lineal F, es decir. Línea a lo largo de la cual esta función toma el mismo valor fijo. A, es decir. F = A, o c1x1+c2x2=a.

En el polígono solución, encuentre el punto por el que pasa la línea de nivel de función. F con el nivel más alto (si se maximiza la función lineal) o más bajo (si se minimiza).

La ecuación de línea de nivel de la función c1x1+c2x2=a es la ecuación de línea recta. En diferentes niveles A las líneas de nivel son paralelas, ya que sus coeficientes angulares están determinados únicamente por la relación entre los coeficientes c1 y c2 y, por tanto, son iguales. Por lo tanto, las líneas de nivel de función F – Se trata de una especie de “paralelos”, normalmente situados en ángulo con respecto a los ejes de coordenadas.

Una propiedad importante de la línea de nivel de una función lineal es que cuando la línea se desplaza paralelamente en una dirección, el nivel solo aumenta, y cuando se desplaza en la otra dirección, solo disminuye. El vector c=(c1,c2), que emerge del origen, indica la dirección del aumento más rápido de la función F. La línea de nivel de la función lineal es perpendicular al vector c=(c1,c2).

El procedimiento para resolver gráficamente el problema de LP:

1. Construya un polígono de soluciones.

2. Construya un vector c = (c1, c2) y primero dibuje una línea de nivel de función lineal para él. F, por ejemplo, F=0.

3. Mediante el movimiento paralelo de la recta F=0 en la dirección del vector c(-c), encuentre el punto Amax(Bmin), en el cual F alcanza su máximo (mínimo).

1. Resolviendo conjuntamente las ecuaciones de rectas que se cruzan en el punto óptimo, encuentre sus coordenadas.

2.Calcule Fmax(Fmin).

Comentario. El punto mínimo es el punto de "entrada" al polígono de solución y el punto máximo es el punto de "salida" del polígono.

6. Idea general del método simplex. Interpretación geométrica

El método gráfico es aplicable a una clase muy limitada de problemas de programación lineal: puede resolver eficazmente problemas que contengan no más de dos variables. Se consideraron los teoremas básicos de la programación lineal, de los cuales se deduce que si un problema de programación lineal tiene una solución óptima, entonces corresponde al menos a un punto angular del poliedro de soluciones y coincide con al menos una de las soluciones básicas admisibles del sistema de restricciones. Se indicó una forma de resolver cualquier problema de programación lineal: enumerar un número finito de soluciones básicas factibles del sistema de restricciones y seleccionar entre ellas aquella en la que la función objetivo constituye la solución óptima. Geométricamente, esto corresponde a enumerar todos los puntos de las esquinas del poliedro solución. Una búsqueda tan exhaustiva conducirá en última instancia a una solución óptima (si existe), pero su implementación práctica está asociada con enormes dificultades, ya que para problemas reales el número de soluciones básicas factibles, aunque finitas, puede ser extremadamente grande.

El número de soluciones básicas permitidas a buscar se puede reducir si la búsqueda no se realiza de forma aleatoria, sino teniendo en cuenta los cambios en la función lineal, es decir asegurar que cada solución posterior sea “mejor” (o al menos “no peor”) que la anterior, según los valores de la función lineal (aumentándola al encontrar un máximo, disminuyéndola al encontrar un mínimo) . Esta búsqueda le permite reducir el número de pasos para encontrar el óptimo. Expliquemos esto con un ejemplo gráfico.

Sea la región de soluciones factibles representada por un polígono. A B C D E. Supongamos que su punto de esquina A Corresponde a la solución original en base factible. Una búsqueda aleatoria requeriría probar cinco soluciones básicas factibles correspondientes a los cinco puntos de las esquinas del polígono. Sin embargo, del dibujo se desprende claramente que después de la cima A es ventajoso moverse a un vértice vecino EN, y luego al punto óptimo CON. En lugar de cinco, pasamos por sólo tres vértices, mejorando constantemente la función lineal.

La idea de mejorar sucesivamente la solución formó la base de un método universal para resolver problemas de programación lineal: Método simplex o método de mejora secuencial del plan.

El significado geométrico del método simplex consiste en una transición secuencial de un vértice del poliedro de restricción (llamado inicial) al vecino, en el que la función lineal toma el mejor (al menos no el peor) valor en relación con el objetivo del problema; hasta que se encuentre la solución óptima: el vértice donde se logra el valor óptimo de la función objetivo (si el problema tiene un óptimo final).

El método simplex fue propuesto por primera vez por el científico estadounidense J. Danzig en 1949, pero ya en 1939 las ideas del método fueron desarrolladas por el científico ruso L.V. Kantorovich.

El método simplex, que permite resolver cualquier problema de programación lineal, es universal. Actualmente, se utiliza para cálculos por computadora, pero los ejemplos simples que utilizan el método simplex se pueden resolver manualmente.

Para implementar el método simplex (mejora secuencial de la solución) es necesario dominar tres elementos principales:

un método para determinar cualquier solución básica inicial viable a un problema;

la regla de transición hacia la mejor solución (más precisamente, no peor);

Criterio para comprobar la optimización de la solución encontrada.

Para utilizar el método simplex, el problema de programación lineal debe reducirse a su forma canónica, es decir el sistema de restricciones debe presentarse en forma de ecuaciones.

La literatura describe con suficiente detalle: encontrar el plan de soporte inicial (solución básica inicial admisible), también usar el método de base artificial, encontrar el plan de soporte óptimo y resolver problemas usando tablas simplex.

7 . Algoritmo del método simplex.

Consideremos la solución del ZLP usando el método simplex y presentémosla en relación con el problema de maximización.

1. A partir de las condiciones del problema se elabora su modelo matemático.

2. El modelo completo se convierte a la forma canónica. En este caso se puede identificar una base con un plan de referencia inicial.

3. El modelo canónico del problema se escribe en forma de tabla simplex para que todos los términos libres sean no negativos. Si se selecciona el plan de referencia inicial, continúe con el paso 5.

Tabla simplex: un sistema de ecuaciones de restricción y una función objetivo se ingresan en forma de expresiones resueltas con respecto a la base inicial. La línea en la que se escriben los coeficientes de la función objetivo F se llama línea F o línea de función objetivo.

4. El plan de referencia inicial se encuentra realizando transformaciones simplex con elementos de resolución positivos correspondientes a las relaciones simplex mínimas, y sin tener en cuenta los signos de los elementos de la fila F. Si durante las transformaciones se encuentra una fila 0 cuyos elementos, excepto el término libre, son ceros, entonces el sistema de ecuaciones de restricción del problema es inconsistente. Si encontramos una fila 0 en la que, aparte del término libre, no hay otros elementos positivos, entonces el sistema de ecuaciones restrictivas no tiene soluciones no negativas.

Llamaremos a la reducción del sistema (2.55), (2.56) a una nueva base. transformación simplex . Si consideramos la transformación simplex como una operación algebraica formal, entonces podemos observar que como resultado de esta operación, los roles se redistribuyen entre dos variables incluidas en un determinado sistema de funciones lineales: una variable pasa de dependiente a independiente y la otra. , por el contrario, de independiente a dependiente. Esta operación se conoce en álgebra como Paso de eliminación de Jordania.

5. Se examina la optimización del plan de soporte inicial encontrado:

a) si no hay elementos negativos en la fila F (sin contar el término libre), entonces el plan es óptimo. Si no hay ceros, entonces sólo hay un plan óptimo; si hay al menos un cero, entonces hay un número infinito de planes óptimos;

b) si en la fila F hay al menos un elemento negativo, que corresponde a una columna de elementos no positivos, entonces;

c) si hay al menos un elemento negativo en la fila F y hay al menos un elemento positivo en su columna, entonces puede pasar a un nuevo plan de referencia que esté más cerca del óptimo. Para hacer esto, la columna especificada debe designarse como columna de resolución, utilizando la relación simplex mínima, encontrar la fila de resolución y realizar una transformación simplex. El plan de referencia resultante se examina nuevamente para determinar su optimización. El proceso descrito se repite hasta obtener un plan óptimo o hasta establecer la insolubilidad del problema.

La columna de coeficientes de una variable incluida en la base se llama resolución. Por lo tanto, al elegir una variable introducida en la base (o elegir una columna de resolución) en función del elemento negativo de la fila F, nos aseguramos de que la función F aumente .

Es un poco más difícil determinar la variable que se excluirá de la base. Para hacer esto, componen las proporciones de los términos libres a los elementos positivos de la columna resolutiva (tales relaciones se llaman simplex) y encuentran el más pequeño entre ellos, lo que determina la fila (resolutiva) que contiene la variable excluida. La elección de una variable excluida de la base (o la elección de una línea de resolución) según la relación simplex mínima garantiza, como ya se ha establecido, la positividad de los componentes de la base en el nuevo plan de referencia.

En el punto 3 del algoritmo, se supone que todos los elementos de la columna de términos libres no son negativos. Este requisito no es necesario, pero si se cumple, todas las transformaciones simples posteriores se realizan solo con elementos de resolución positivos, lo cual es conveniente para los cálculos. Si hay números negativos en la columna de términos libres, entonces el elemento de resolución se elige de la siguiente manera:

1) mirar la fila correspondiente a algún término libre negativo, por ejemplo, una fila t, y seleccionar algún elemento negativo en ella, y la columna correspondiente se considera resolutiva (asumimos que las restricciones del problema son consistentes);

2) componer las relaciones de los elementos de la columna de términos libres con los elementos correspondientes de la columna resolutiva que tienen los mismos signos (relaciones simples);

3) elija la más pequeña de las relaciones simplex. Esto determinará la cadena de habilitación. Sea, por ejemplo, R-línea;

4) en la intersección de la columna y la fila de resolución, se encuentra un elemento de resolución. Si el elemento de la fila y resulta resolutivo, luego de la transformación simplex el término libre de esta fila se volverá positivo. De lo contrario, en el siguiente paso se accede nuevamente a la fila t. Si el problema se puede resolver, después de un cierto número de pasos no quedarán elementos negativos en la columna de términos libres.

8. Método de matriz inversa

Consideremos un LP de la forma:

A – matriz de restricciones;

C=(c1,c2,…,cn)–vector de fila;

X=(x1,x2,…,xn) – variables;

es el vector del lado derecho.

Suponemos que todas las ecuaciones son linealmente independientes, es decir rango(a)=m. En este caso, la base es menor del orden de la matriz A. Es decir, existe al menos una submatriz B de orden m tal que |B|<>0. Todas las incógnitas correspondientes a B se denominan básicas. Todos los demás son gratuitos.

Sea B alguna base. Luego, al reorganizar las columnas de la matriz A, siempre podemos reducir A a la forma A=(B|N),

donde N es una submatriz que consta de columnas de la matriz A que no pertenecen a la base. De la misma forma, es posible dividir el vector x en un vector de variables básicas y.

Cualquier solución al problema (1) satisface la condición A*x=b y, por tanto, el sistema adopta la siguiente forma:

Porque |B|<>0, entonces hay una matriz inversa. Multiplicando por la izquierda por la inversa obtenemos:

- decisión común.

La solución básica (relativa a la base B) es una solución particular al problema (2) obtenida bajo la condición. Entonces se determina de forma única.

La solución básica se llama realizable, Si.

La base correspondiente a la solución básica implementada. Llamado base implementable. La solución básica se llama degenerada si el vector tiene componentes cero.

La solución general contiene todas las soluciones que existen. Volvamos a la función objetivo. Introducimos Cb – coeficientes delante de las variables básicas, Cn – el resto.

Así conseguimos. Sustituimos de la solución general:

Declaración. Criterio de optimización de la solución básica.

Digamos. Entonces la solución básica es óptima. Si, entonces la solución básica no es óptima.

Documento: Permitir. Consideremos la solución básica.

Por tanto, es el valor de la función objetivo para la solución básica.

Sea otra solución: (Xb,Xn).

Entonces miremos

Por tanto, la solución básica es la más mínima. Por el contrario, no se cumpla, es decir. existe.

Entonces hay una solución para la cual el valor de la función objetivo será menor que el valor de la función objetivo de la solución básica.

Hagamos que corresponda a una variable libre Xi:Xj, le asignamos un valor y lo ingresamos en la base, derivamos otra variable y la llamamos libre.

¿Cómo determinarlo? Todas las variables libres excepto siguen siendo iguales a 0 también.

Luego en la solución general, donde.

Saquemos: – una condición necesaria.

Una solución básica se llama regular si. Derivamos la variable de la base. Con una nueva solución, la función objetivo disminuye, porque

Algoritmo:

1.Problema LP en forma estándar.

2. Dejamos ecuaciones linealmente independientes.

3. Encuentre una matriz B tal que |B|<>0 y la solución básica.

Calculamos:

si, entonces hay una solución óptima: ésta es la solución básica;

si, entonces encontramos el componente, lo agregamos y así encontramos otra solución; – en el que una de las variables básicas =0. Eliminamos esta variable de la base e introducimos xi. Hemos obtenido una nueva base B2, conjugada a la base B1. Luego volvemos a calcular.

1. Si existe una solución óptima, luego de un número finito de pasos la obtendremos.

Geométricamente, el procedimiento se interpreta como una transición desde un punto de esquina a un punto de esquina conjugado a lo largo del límite del conjunto X, el conjunto de soluciones del problema. Porque hay un número finito de puntos de esquina y la estricta disminución de la función F(x) prohíbe pasar dos veces por el mismo punto extremo, entonces si hay una solución óptima, entonces después de un número finito de pasos la obtendremos.

9. Interpretación económica del problema dual al problema del uso de recursos.

Tarea. Para producir dos tipos de productos P1 y P2, se utilizan cuatro tipos de recursos S1, S2, S3, S4. Se dan las reservas de recursos, el número de unidades de recursos gastadas en la producción de una unidad de producción. Se conoce el beneficio recibido de una unidad de producción P1 y P2. Es necesario elaborar un plan de producción en el que el beneficio de su venta sea máximo.

TareaI(original):

F=c1x1+c2x2+…+CnXn->max con restricciones:

y la condición de no negatividad x1>=0, x2>=0,…,Xn>=0

Elaborar un plan de producción X=(x1,x2,…,Xn) en el que el beneficio (ingreso) por la venta del producto será máximo, siempre que el consumo de recursos para cada tipo de producto no supere las reservas disponibles.

TareaII(doble)

Z=b1y1+b2y2+…+BmYm->mín.

con restricciones:

y la condición de no negatividad

y1>=0, y2>=0,…,yn>=0.

Encuentre un conjunto de precios (estimaciones) de recursos Y=(y1,y2,…,yn), en el que los costos totales de los recursos serán mínimos, siempre que los costos de los recursos en la producción de cada tipo de producto sean no menos que el beneficio (ingreso) de la venta de estos productos

En el modelo anterior, bi(i=1,2,…,m) denota la reserva de recursos Si; aij – el número de unidades de recurso Si consumidas en la producción de una unidad de producción Pj(j=1,2,…,n); cj– beneficio (ingreso) por la venta de una unidad de producción Pj (o precio del producto Pj) .

Supongamos que alguna organización ha decidido comprar los recursos S1, S2,..., Sm de la empresa y es necesario fijar precios óptimos para estos recursos y1, y2,..., ym. Obviamente, la organización de compras está interesada en gastar en todos los recursos Z en las cantidades b1,b2,…,bm. a los precios y1,y2,…,ym, respectivamente, eran mínimos, es decir Z=b1,y1+b2y2+…+bmym->mín.

Por otro lado, una empresa que vende recursos está interesada en asegurarse de que los ingresos recibidos no sean menores que la cantidad que la empresa puede recibir al procesar recursos en productos terminados.

Para producir una unidad del producto P1, se consumen a11 unidades del recurso S1, a21 unidades del recurso S2,...., aj1 unidades del recurso Si1,......, am1 unidades del recurso Sm a un precio de y1. ,y1,...,yi,...,ym, respectivamente. Por lo tanto, para satisfacer los requisitos del vendedor, los costos de los recursos consumidos en la producción de una unidad del producto P1 no deben ser menores que su precio c1, es decir a11y1+a21y2+…+am1ym>=c1.

De manera similar, puedes crear restricciones en forma de desigualdades para cada tipo de producto P1, P2,…Pn. El modelo económico-matemático y la interpretación significativa del problema dual II así obtenido se dan en el lado derecho de la tabla.

Los precios de los recursos y1,y1,…,yi,…,ym han recibido varios nombres en la literatura económica: contabilidad, implícito, sombra . El significado de estos nombres es que es condicional , Precios "falsos". A diferencia de los precios “externos” c1,c2,…,cn de los productos, conocidos, por regla general, antes del inicio de la producción, los precios de los recursos y1,y2,…,ym son interno , porque no vienen dados desde el exterior, sino que se determinan directamente como resultado de la resolución del problema, por eso se les llama más a menudo estimados recursos.

10. Problemas de LP mutuamente duales y sus propiedades.

Consideremos formalmente dos problemas I y II de programación lineal, presentados en la tabla, abstrayéndonos de la interpretación significativa de los parámetros incluidos en sus modelos económicos y matemáticos.

Ambas tareas tienen las siguientes propiedades:

1. En un problema se busca el máximo de una función lineal, en el otro, el mínimo.

2. Los coeficientes de variables en una función lineal de un problema son miembros libres del sistema de restricciones en otro.

3.Cada uno de los problemas se da en forma estándar, y en el problema de maximización todas las desigualdades de la forma "<=", а в задаче минимизации – все неравенства вида ">=".

4. Las matrices de coeficientes para variables en los sistemas de restricciones de ambos problemas se transponen entre sí.

5. El número de desigualdades en el sistema de restricciones de un problema coincide con el número de variables en otro problema.

6. En ambos problemas se conservan las condiciones para la no negatividad de las variables.

Comentario. Si se impone una condición de no negatividad a la j-ésima variable del problema original, entonces la j-ésima restricción del problema dual será una desigualdad, pero si la j-ésima variable puede tomar valores tanto positivos como negativos, entonces la j-ésima restricción del problema dual será una ecuación; las restricciones del problema original y las variables del dual están igualmente relacionadas.

Dos problemas de programación lineal I y II que tienen las propiedades indicadas se denominan problemas duales simétricos. En lo que sigue, por simplicidad, los llamaremos simplemente tareas duales.

Cada problema de LP puede asociarse con su doble tarea.

11. Algoritmo para componer un problema dual:

1. Reducir todas las desigualdades del sistema de restricciones del problema original a un significado: si en el problema original se busca el máximo de una función lineal, entonces reducir todas las desigualdades del sistema de restricciones a la forma "<=", а если минимум – к виду ">=". Para estas desigualdades en las que no se cumple este requisito, se multiplica por –1.

2. Componga una matriz extendida del sistema A, que incluya una matriz de coeficientes para variables, una columna de términos libres del sistema de restricciones y una fila de coeficientes para variables en una función lineal.

3. Encuentre la matriz transpuesta a la matriz A .

4. Formule un problema dual basado en la matriz resultante. y condiciones para la no negatividad de las variables: forman la función objetivo del problema dual, tomando como coeficientes de las variables los miembros libres del sistema de restricciones del problema original; componer un sistema de restricciones para el problema dual, tomando elementos de la matriz como coeficientes de las variables y coeficientes de las variables en la función objetivo del problema original como términos libres, y escribir desigualdades de significado opuesto; Escriba la condición para la no negatividad de las variables del problema dual.

12. Primer teorema de la dualidad

La conexión entre soluciones óptimas de problemas duales se establece mediante teoremas de dualidad.

Un signo suficiente de optimización.

Si X*=(x1*,x2*,…,xn*) Y Y*=(y1*,y2*,…,ym*) – soluciones admisibles de problemas mutuamente duales para los cuales se cumple la igualdad,

entonces es la solución óptima al problema original I y al problema dual II.

Además del signo suficiente de optimización de los problemas mutuamente duales, existen otras relaciones importantes entre sus soluciones. En primer lugar, surgen las preguntas: ¿existen siempre simultáneamente soluciones óptimas para cada par de problemas duales? ¿Es posible que uno de los problemas duales tenga solución y el otro no? La respuesta a estas preguntas viene dada por el siguiente teorema.

El primer (principal) teorema de la dualidad. Si uno de los problemas mutuamente duales tiene una solución óptima, entonces el otro también la tiene y los valores óptimos de sus funciones lineales son iguales:

Fmáx = Zmín o F(X*)=Z(Y*) .

Si la función lineal de uno de los problemas no es limitada, entonces las condiciones del otro problema son contradictorias (el problema no tiene solución).

Comentario. La afirmación inversa a la segunda parte del teorema principal de la dualidad no es cierta en el caso general, es decir Del hecho de que las condiciones del problema original sean contradictorias, no se sigue que la función lineal del problema dual sea ilimitada.

Significado económico del primer teorema de la dualidad.

Plan de producción X*=(x1*,x2*,…,xn*) y conjunto de precios (estimaciones) de los recursos Y*=(y1*,y2*,…,ym*) resultan óptimos si y sólo si el beneficio (ingreso) de los productos, encontrado a precios “externos” (conocidos de antemano) c1, c2,…, cn, es igual a los costos de los recursos a precios “internos” (determinados sólo de resolver el problema) precios y1 ,y2,…,ym. Para todos los demás planes X Y Y En ambos problemas, la ganancia (ingreso) de los productos es siempre menor (o igual) que los costos de los recursos.

El significado económico del primer teorema de la dualidad se puede interpretar de la siguiente manera: a la empresa le es indiferente producir productos de acuerdo con el plan óptimo X*=(x1*,x2*,…,xn*) y recibir el máximo beneficio (ingreso) Fmax o vender recursos a precios óptimos Y* =(y1*,y2*,…,ym*) y reembolsar de la venta el costo mínimo de los recursos Zmin.

13. Segundo teorema de la dualidad

Se dan dos problemas mutuamente duales. Si cada uno de estos problemas se resuelve utilizando el método simplex, entonces es necesario llevarlos a la forma canónica, para lo cual se deben introducir en el sistema de restricciones del Problema I (en notación corta) t variables no negativas, y en el sistema de restricciones del Problema II () – norte variables no negativas, donde i(j) es el número de la desigualdad en la que se introduce la variable adicional.

Los sistemas de restricciones para cada uno de los problemas mutuamente duales tomarán la forma:

Establezcamos una correspondencia entre las variables iniciales de uno de los problemas duales y las variables adicionales del otro problema (tabla).

Teorema. Los componentes positivos (distintos de cero) de la solución óptima de uno de los problemas mutuamente duales corresponden a componentes cero de la solución óptima del otro problema, es decir para cualquier i=1,2,…,m u j=1,2,…,n: si X*j>0, entonces; Si , entonces, y de manera similar,

si entonces ; si entonces.

De este teorema se desprende una conclusión importante de que la correspondencia introducida entre las variables de problemas mutuamente duales cuando se logra el óptimo (es decir, en el último paso de resolver cada problema usando el método simplex) representa la correspondencia entre principal(por regla general, no igual a cero) variables de uno de los problemas duales y no básico(igual a cero) variables de otro problema cuando forman soluciones básicas factibles.

Segundo teorema de la dualidad. Los componentes de la solución óptima del problema dual son iguales a los valores absolutos de los coeficientes de las variables correspondientes de la función lineal del problema original, expresados ​​a través de las variables no básicas de su solución óptima.

Comentario. Si en uno de los problemas mutuamente duales se viola la unicidad de la solución óptima, entonces la solución óptima al problema dual es degenerada. Esto se debe al hecho de que si se viola la unicidad de la solución óptima del problema original, al menos una de las variables principales falta en la expresión de la función lineal de su solución óptima en términos de variables no básicas.

14. Evaluaciones objetivamente determinadas y su significado.

Los componentes de la solución óptima del problema dual se denominan estimaciones óptimas (duales) del problema original. El académico L.V. Kantorovich los llamó objetivamente determinado" estimados ( en la literatura también se les llama ingresos ocultos) .

Variables adicionales del problema original I, que representan la diferencia entre las reservas bi de los recursos S1, S2, S3, S4 y su consumo, expresa recursos restantes , y variables adicionales del problema dual II, que representan la diferencia entre los costos de los recursos para producir una unidad de producción a partir de ellos y los precios cj de los productos P1, P2. , expresar exceso de costos sobre el precio.

Por lo tanto, las evaluaciones de recursos determinadas objetivamente determinan el grado de escasez de recursos: de acuerdo con el plan de producción óptimo, los recursos escasos (es decir, totalmente utilizados) reciben evaluaciones distintas de cero, y los recursos no escasos reciben evaluaciones de cero. El valor y*i es una evaluación del i-ésimo recurso. Cuanto mayor sea el valor de la estimación y*i, mayor será la escasez del recurso. Para un recurso no escaso y*i=0.

Por lo tanto, solo los tipos de productos rentables y no rentables pueden incluirse en el plan de producción óptimo (sin embargo, el criterio de rentabilidad aquí es único: el precio del producto no excede los costos de los recursos consumidos en su producción, pero es exactamente iguales a ellos).

Tercer teorema de la dualidad . Los componentes de la solución óptima del problema dual son iguales a los valores de las derivadas parciales de la función lineal. Fmáx(b1, b2,…, bm)según los argumentos correspondientes, es decir

Las estimaciones de recursos determinadas objetivamente muestran cuántas unidades monetarias cambiará el beneficio (ingreso) máximo de las ventas de productos cuando el stock del recurso correspondiente cambie en una unidad.

Las evaluaciones duales pueden servir como herramienta para el análisis y la toma de decisiones correctas en condiciones de producción en constante cambio. Por ejemplo, con la ayuda de estimaciones de recursos determinadas objetivamente, es posible comparar los costos condicionales óptimos y los resultados de producción.

Las estimaciones de recursos determinadas objetivamente nos permiten juzgar el efecto no de ninguno, sino sólo de cambios relativamente pequeños en los recursos. Con cambios repentinos, las estimaciones mismas pueden volverse diferentes, lo que hará imposible su uso para analizar la eficiencia de la producción. Con base en los ratios de evaluaciones determinadas objetivamente, se pueden determinar las normas calculadas de sustituibilidad de recursos, siempre que los reemplazos realizados dentro de los límites de la estabilidad de las evaluaciones duales no afecten la efectividad del plan óptimo. Conclusión. Las estimaciones duales son:

1. Un indicador de escasez de recursos y productos.

2. Un indicador de la influencia de las restricciones sobre el valor de la función objetivo.

3. Un indicador de la eficiencia de producción de determinados tipos de productos desde el punto de vista del criterio de optimización.

4. Una herramienta para comparar costos y resultados condicionales totales.

15. Planteamiento del problema del transporte en función del criterio de coste.

TK - el problema del plan más económico para transportar un producto homogéneo o intercambiable desde el punto de producción (estaciones de salida) hasta los puntos de consumo (estaciones de destino) - es el problema particular más importante del LP, que tiene amplias aplicaciones prácticas. no sólo a los problemas de transporte.

La especificación técnica se distingue en LP por la certeza de sus características económicas, las características del modelo matemático y la presencia de métodos de solución específicos.

La formulación más sencilla de las especificaciones técnicas según el criterio de coste es la siguiente: en t en los puntos de salida A1,…,Am hay respectivamente a1,…,am unidades de carga homogénea (recursos) que deben entregarse norte consumidores B1,…,Bn en cantidades b1,…,bn unidades (necesidades). Se conocen los costes de transporte Cij de transportar una unidad de carga desde el i-ésimo punto de salida hasta el j-ésimo punto de consumo.

Se requiere elaborar un plan de transporte, es decir, encontrar cuántas unidades de carga se deben enviar desde el i-ésimo punto de salida hasta el j-ésimo punto de consumo para satisfacer plenamente las necesidades y para que el transporte total Los costos son mínimos.

Para mayor claridad, presentamos las condiciones de la especificación técnica en forma de una tabla llamada distribución .

Proveedor	Consumidor			Stock de carga
Necesidad

Aquí, la cantidad de carga transportada desde el i-ésimo punto de salida hasta el j-ésimo destino es igual a xij, el stock de carga en el i-ésimo punto de salida está determinado por el valor ai>=0, y el La necesidad de carga en el j-ésimo destino es bj>=0. Se supone que todo xij>=0.

La matriz se llama matriz tarifaria (costos o costos de transporte).

Plan de tareas de transporte se llama matriz, donde cada número xij denota el número de unidades de carga que deben entregarse desde el i-ésimo punto de salida hasta el j-ésimo destino. La matriz xij se llama matriz de transporte.

Los costos totales totales asociados con la implementación del plan de transporte se pueden representar mediante la función objetivo.

Las variables xij deben satisfacer las restricciones de inventarios, consumidores y condiciones de no negatividad:

– restricciones a las reservas (2);

– restricciones a los consumidores (2);

– condiciones de no negatividad (3).

Así, matemáticamente, el problema del transporte se formula de la siguiente manera. Se dan el sistema de restricciones (2) bajo la condición (3) y la función objetivo (1). Entre el conjunto de soluciones del sistema (2), se requiere encontrar una solución no negativa que minimice la función (1).

El sistema de restricciones del problema (1) – (3) contiene m+n ecuaciones con tnorte variables. Se supone que las reservas totales son iguales a las necesidades totales, es decir

16. Signo de solucionabilidad del problema del transporte.

Para que un problema de transporte tenga planes admisibles es necesario y suficiente que se cumpla la igualdad

Hay dos tipos de problemas de transporte: cerrado , en el que el volumen total de carga de los proveedores es igual a la demanda total de los consumidores, y abierto , en el que la capacidad de producción total de los proveedores excede la demanda de los consumidores o la demanda de los consumidores es mayor que la capacidad total real de los proveedores, es decir,

Un modelo abierto se puede convertir en uno cerrado. Entonces, si, entonces se introduce un destino ficticio (n+1) en el modelo matemático del problema de transporte. Para ello, se proporciona una columna adicional en la matriz de tareas, para la cual la demanda es igual a la diferencia entre la capacidad total de los proveedores y la demanda real de los consumidores:

Todas las tarifas de entrega de carga hasta este punto se considerarán iguales a cero. Esto transforma el modelo abierto del problema en uno cerrado. Para un problema nuevo, la función objetivo es siempre la misma, ya que los precios del transporte adicional son iguales a cero. En otras palabras, el consumidor ficticio no viola la compatibilidad del sistema de obligaciones.

Si, entonces se introduce un punto de partida ficticio (m+1)ésimo, al que se le asigna un stock de carga igual a.

Las tarifas por la entrega de mercancías de este proveedor ficticio vuelven a ser cero. Se agregará una fila a la matriz, esto no afectará la función objetivo y el sistema de restricciones del problema se volverá conjunto, es decir, será posible encontrar el plan óptimo.

Para el problema del transporte, el siguiente teorema es importante.

Teorema. El rango de la matriz del problema de transporte es uno menos que el número de ecuaciones, es decir r ( a )= metro + norte -1.

Del teorema se desprende que cada diseño de referencia debe tener (m-1)(n-1) variables libres iguales a cero y m+n-1 variables de base.

Buscaremos el plan de transporte de la tarea de transporte directamente en la tabla de distribución. Supongamos que si la variable xij toma un valor, entonces escribiremos este valor en la celda correspondiente (I,j), pero si xij=0, entonces dejaremos libre la celda (I,j). Teniendo en cuenta el teorema sobre el rango de la matriz en la tabla de distribución. el plan de referencia debe contener m+n-1 celdas ocupadas, y el resto será gratis.

Los requisitos especificados para el plan de referencia no son los únicos. Los planes de referencia deben satisfacer otro requisito relacionado con los ciclos.

Un conjunto de celdas de una matriz de transporte en el que dos y solo dos celdas adyacentes están ubicadas en una fila o en una columna y la última celda del conjunto se encuentra en la misma fila o columna que la primera se llama cerrado ciclo .

Gráficamente, un ciclo es una línea discontinua cerrada, cuyos vértices están ubicados en las celdas ocupadas de la tabla y los enlaces están ubicados solo en filas o columnas. Además, en cada vértice del ciclo hay exactamente dos eslabones, uno de los cuales está en una fila y el otro en una columna. Si una línea discontinua que forma un ciclo se cruza a sí misma, entonces los puntos de autointersección no son vértices.

Las siguientes propiedades importantes de los planes de problemas de transporte están asociadas con un conjunto de celdas de ciclo:

1) un plan admisible para un problema de transporte es de referencia si y sólo si no se puede formar ningún ciclo a partir de las celdas ocupadas por este plan;

2) si tenemos un plan de referencia, entonces para cada celda libre solo se puede formar un ciclo que contenga esta celda y una parte de las celdas ocupadas.

17. Construcción del plan de referencia inicial

La regla de la "esquina noroeste".

Para elaborar el plan de transporte inicial es conveniente utilizar la regla de la “esquina noroeste”, que es la siguiente.

Completaremos comenzando desde la parte superior izquierda, convencionalmente llamada "esquina noroeste", avanzando a lo largo de la línea hacia la derecha o hacia abajo en la columna. Pongamos en la celda (1; 1) el menor de los números a1 y b1, es decir . Si, entonces la primera columna está "cerrada", es decir, la demanda del primer consumidor está completamente satisfecha. Esto significa que para todas las demás celdas de la primera columna la cantidad de carga para .

Si, entonces, la primera línea es igualmente "cerrada", es decir, para . Procedemos a llenar la celda adyacente (2; 1), en la que ingresamos.

Habiendo completado la segunda celda (1; 2) o (2; 1), procedemos a completar la siguiente tercera celda a lo largo de la segunda línea o en la segunda columna. Continuaremos este proceso hasta que en algún momento se agoten los recursos y las necesidades. La última celda llena estará en la última enésima columna y en la última enésima fila.

La regla del "elemento mínimo".

El plano de referencia inicial, construido según la regla de la “esquina noroeste”, suele resultar muy lejos de ser óptimo, ya que su determinación no tiene en cuenta los valores de costes cij. Por lo tanto, más cálculos requerirán muchas iteraciones para lograr el plan óptimo. El número de iteraciones se puede reducir si el plan inicial se construye de acuerdo con la regla del "elemento mínimo". Su esencia radica en el hecho de que en cada paso se realiza el máximo "movimiento" posible de carga hacia la jaula con una tarifa mínima cij. Comenzamos a llenar la tabla desde la celda que corresponde al elemento más pequeño cij de la matriz tarifaria. El menor de los números ai o bj se coloca en la celda con la tarifa más baja. . Luego se excluye de consideración la fila correspondiente a un proveedor cuyo inventario está completamente agotado, o la columna correspondiente a un cliente cuya demanda está completamente satisfecha. Puede ser necesario eliminar una fila y una columna al mismo tiempo si el inventario del proveedor está completamente agotado y la demanda del cliente está totalmente satisfecha. A continuación, del resto de celdas de la tabla se vuelve a seleccionar la celda con la tarifa más baja y se continúa el proceso de distribución de stocks hasta distribuirlos todos y satisfacer la demanda.

18. Método de potenciales.

El principio general de determinar el plan óptimo para un problema de transporte utilizando el método potencial es similar al principio de resolver un problema de PL utilizando el método simplex, a saber: primero se encuentra un plan de referencia para un problema de transporte y luego se calcula sucesivamente. mejorar hasta obtener un plan óptimo.

La esencia del método potencial es la siguiente. Una vez que se ha encontrado el plan de transporte de referencia inicial, a cada proveedor (cada fila) se le asigna un número determinado llamado potencial de proveedor Ai, y a cada consumidor (cada columna) se le asigna un número determinado llamado potencial de consumidor.

El costo de una tonelada de carga en un punto es igual al costo de una tonelada de carga antes del transporte + el costo de su transporte: .

Para resolver un problema de transporte utilizando el método potencial, es necesario:

1. Construya un plan de transporte básico de acuerdo con una de las reglas establecidas. El número de celdas llenas debe ser m+n-1.

2. Calcular los potenciales y, en consecuencia, los proveedores y consumidores (para celdas ocupadas): . El número de celdas llenas es m+n-1 y el número de ecuaciones es m+n. Porque el número de ecuaciones es uno menos que el número de incógnitas, entonces una de las incógnitas resulta libre y puede tomar cualquier valor numérico. Por ejemplo, . Los potenciales restantes para una solución de referencia determinada se determinarán de forma única.

3. Verifique la optimización, es decir para celdas libres, calcule estimaciones. Si, entonces el transporte es conveniente y el plan X es óptimo, un signo de optimización. Si hay al menos una diferencia, pase a un nuevo plan de referencia. En su significado económico, el valor caracteriza el cambio en los costos totales de transporte que se producirá debido a una sola entrega por parte del i-ésimo proveedor al j-ésimo consumidor. Si es así, una única entrega supondrá un ahorro en los costes de transporte, pero si, un aumento de los mismos. En consecuencia, si entre las direcciones de suministro gratuito no hay direcciones que ahorren costos de transporte, entonces el plan resultante es óptimo.

4. Entre los números positivos se selecciona el máximo y se construye un ciclo de recálculo para la celda libre a la que corresponde. Después de que se haya construido el ciclo para la celda libre seleccionada, debe pasar a un nuevo plan de referencia. Para hacer esto, es necesario mover las cargas dentro de las celdas conectadas a una celda libre determinada mediante un ciclo de recálculo.

a) A cada una de las celdas conectadas por un ciclo con una celda libre determinada se le asigna un signo determinado, y esta celda libre es "+", y a todas las demás celdas (vértices del ciclo) se les asignan alternativamente los signos "-" y " +”. Llamaremos a estas celdas menos y más.

b) En las celdas negativas del ciclo encontramos la oferta mínima, que denotamos por. El menor de los números xij ubicados en las celdas negativas se transfiere a esta celda libre. Al mismo tiempo, este número se suma a los números correspondientes en las celdas con el signo "+" y se resta de los números en las celdas menos. Una celda que antes estaba libre pasa a ocuparse y entra en el plano de soporte; y la celda menos, que contenía el mínimo de los números xij, se considera libre y sale del plan de soporte.

Así, se determinó un nuevo plan de referencia. La transición descrita anteriormente de un plan de referencia a otro se denomina cambio en el ciclo de recálculo. Cuando se desplaza a lo largo del ciclo de recálculo, el número de celdas ocupadas permanece sin cambios, es decir, permanece igual a m+n-1. Además, si hay dos o más números idénticos xij en las celdas negativas, entonces sólo una de estas celdas se libera y el resto queda ocupada sin suministros.

5. Se comprueba que el plan de referencia resultante sea óptimo, es decir repita todos los pasos desde el paso 2.

19. El concepto de programación dinámica.

DP (planificación) es un método matemático para encontrar soluciones óptimas a problemas de varios pasos (varias etapas). Algunos de estos problemas se dividen naturalmente en pasos separados (etapas), pero hay problemas en los que la partición debe introducirse artificialmente para poder resolverlos mediante el método DP.

Normalmente, los métodos DP optimizan el funcionamiento de algunos sistemas controlados, cuyo efecto se evalúa aditivo, o multiplicativo, la función objetivo. Aditivo Se llama una función de varias variables f(x1,x2,…,xn), cuyo valor se calcula como la suma de algunas funciones fj que dependen solo de una variable xj: . Los términos de la función objetivo aditiva corresponden al efecto de las decisiones tomadas en etapas individuales del proceso controlado.

Principio de optimización de R. Bellman.

El significado del enfoque implementado en la programación dinámica es reemplazar la solución del problema multidimensional original con una secuencia de problemas de menor dimensión. Requisitos básicos para las tareas:

1. el objeto de la investigación debe ser sistema controlado (objeto) con validez dada estados y aceptable departamentos;

2. la tarea debe permitir la interpretación como un proceso de varios pasos, cada uno de los cuales consiste en la aceptación soluciones oh elegir uno de los controles admisibles que conduzcan a cambio de estado sistemas;

3. la tarea no debe depender del número de pasos y estar definida en cada uno de ellos;

4. el estado del sistema en cada paso debe describirse mediante el mismo conjunto (en composición) de parámetros;

5. el estado posterior en el que se encuentra el sistema después de elegir una solución en km paso, depende sólo de la decisión dada y del estado inicial al principio k- º paso. Esta propiedad es fundamental desde el punto de vista de la ideología de la programación dinámica y se llama sin consecuencias .

Consideremos las cuestiones de la aplicación del modelo de programación dinámica de forma generalizada. Dejemos que la tarea sea controlar algún objeto abstracto que pueda estar en diferentes estados. El estado actual del objeto se identificará con un cierto conjunto de parámetros, que se indicarán además con S y se denominarán vector de estado. Se supone que se da un conjunto S de todos los estados posibles. También hay un conjunto definido para el objeto. controles admisibles(acciones de control) X, el cual, sin pérdida de generalidad, puede considerarse un conjunto numérico. Las acciones de control se pueden llevar a cabo en momentos discretos en el tiempo, y la gestión solución Consiste en elegir uno de los controles. Plan tareas o estrategia administrativa se llama vector x=(x1,x2,…,xn-1), cuyos componentes son los controles seleccionados en cada paso del proceso. En vista de lo esperado sin efectos secundarios entre cada dos estados consecutivos del objeto Sk y Sk+1, existe una relación funcional conocida, que también incluye el control seleccionado: . Así, establecer el estado inicial del objeto y elegir un plan. X definir claramente trayectoria de comportamiento objeto.

Controle la eficiencia en cada paso k depende del estado actual Sk, del control seleccionado xk y se cuantifica mediante las funciones fk(xk,Sk), que son términos función objetivo aditiva , que caracteriza la eficiencia general de la gestión de instalaciones. ( Nota , que la definición de la función fk(xk,Sk) incluye el rango de valores permitidos xk , y esta área, por regla general, depende del estado actual de Sk). Control óptimo , para un estado inicial dado S1, todo se reduce a elegir dicho plan óptimo x* , en el que se logra cantidad máxima valores de fk en la trayectoria correspondiente.

El principio básico de la programación dinámica es que en cada paso no se debe esforzarse por lograr una optimización aislada de la función fk(xk,Sk), sino elegir el control óptimo x*k bajo el supuesto de que todos los pasos posteriores son óptimos. Formalmente, este principio se implementa encontrando en cada paso k controles óptimos condicionales , proporcionando la mayor eficiencia total a partir de este paso, suponiendo que el estado actual es S.

Sea Zk(s) el valor máximo de la suma de funciones fk a lo largo de los pasos desde k antes PAG(obtenido con control óptimo en un segmento dado del proceso), siempre que el objeto al comienzo del paso k está en el estado S. Entonces las funciones Zk(s) deben satisfacer la relación de recurrencia:

Esta relación se llama relación de recurrencia básica (ecuación funcional básica) programación dinámica. Implementa el principio básico de la programación dinámica, también conocida como Principio de optimización de Bellman :

La estrategia de control óptima debe satisfacer la siguiente condición: cualquiera que sea el estado inicial sk en el k-ésimo paso y el control seleccionado en este paso xk, La gestión posterior (decisiones gerenciales) debe ser óptima en relación con cocomo Ianiya ,resultante de la decisión tomada en el paso k .

La relación principal nos permite encontrar las funciones Zk(s) solo V combinado con condición inicial, que en nuestro caso es la igualdad.

El principio de optimización formulado anteriormente es aplicable sólo al control de objetos para los cuales la elección del control óptimo no depende de los antecedentes del proceso controlado, es decir, de cómo llegó el sistema a su estado actual. Es esta circunstancia la que nos permite descomponer el problema y hacer posible su solución práctica.

Para cada tarea específica, la ecuación funcional tiene su propia forma específica, pero ciertamente debe preservar el carácter recurrente inherente a la expresión (*) y que encarna la idea básica del principio de optimidad.

20. El concepto de modelos de juego.

El modelo matemático de una situación de conflicto se llama juego , partes involucradas en el conflicto - jugadores, y el resultado del conflicto es ganar.

Para cada juego formalizado, normas , aquellos. un sistema de condiciones que determina: 1) opciones para las acciones de los jugadores; 2) la cantidad de información que cada jugador tiene sobre el comportamiento de sus compañeros; 3) la ganancia a la que conduce cada conjunto de acciones. Normalmente, ganar (o perder) puede cuantificarse; por ejemplo, puedes valorar una pérdida como cero, una victoria como uno y un empate como 1/2. Cuantificar los resultados de un juego se llama pago .

el juego se llama cuarto de vapor , si se trata de dos jugadores, y múltiple , si el número de jugadores es superior a dos. Sólo consideraremos juegos de dobles. Involucran a dos jugadores. A Y EN, cuyos intereses son opuestos, y por juego entendemos una serie de acciones por parte de A Y EN.

el juego se llama Juego de suma cero o antagonista cielo , si la ganancia de uno de los jugadores es igual a la pérdida del otro, es decir la suma de las ganancias de ambos lados es cero. Para completar la tarea del juego, basta con indicar el valor de uno de ellos. . Si designamos A– ganancias de uno de los jugadores, b – las ganancias del otro, luego para un juego de suma cero segundo = –A, por lo que basta considerar, por ejemplo A.

La elección y ejecución de una de las acciones previstas por las normas se denomina progreso jugador. Los movimientos pueden ser personal Y aleatorio . mudanza personal – se trata de una elección consciente por parte del jugador de una de las posibles acciones (por ejemplo, un movimiento en una partida de ajedrez). El conjunto de opciones posibles para cada jugada personal está regulado por las reglas del juego y depende de la totalidad de jugadas anteriores de ambos bandos.

movimiento aleatorio – es una acción elegida al azar (por ejemplo, elegir una carta de un mazo barajado). Para que un juego esté definido matemáticamente, las reglas del juego deben indicar para cada movimiento aleatorio Distribución de probabilidad posibles resultados.

Algunos juegos pueden consistir únicamente en movimientos aleatorios (el llamado juego puro) o únicamente en movimientos personales (ajedrez, damas). La mayoría de los juegos de cartas pertenecen a juegos de tipo mixto, es decir, contienen movimientos tanto aleatorios como personales. En el futuro, consideraremos sólo los movimientos personales de los jugadores.

Los juegos se clasifican no sólo por la naturaleza de los movimientos (personales, aleatorios), sino también por la naturaleza y cantidad de información disponible para cada jugador sobre las acciones del otro. Una clase especial de juegos son los llamados "juegos con información completa". Un juego con información completa es un juego en el que cada jugador, con cada movimiento personal, conoce el resultado de todos los movimientos anteriores, tanto personales como aleatorios. Ejemplos de juegos con información completa incluyen el ajedrez, las damas y el conocido juego “tic-tac-toe”. La mayoría de los juegos de importancia práctica no pertenecen a la clase de juegos con información completa, ya que la incertidumbre sobre las acciones del enemigo suele ser un elemento esencial en las situaciones de conflicto.

Uno de los conceptos principales de la teoría de juegos es el concepto estrategias .

Estrategia Un jugador es un conjunto de reglas que determinan la elección de su acción en cada movimiento personal, dependiendo de la situación actual. Por lo general, durante el juego, con cada movimiento personal, el jugador toma una decisión dependiendo de la situación específica. Sin embargo, en principio es posible que todas las decisiones las tome el jugador de antemano (en respuesta a cualquier situación dada). Esto significa que el jugador ha elegido una estrategia específica, que puede especificarse como una lista de reglas o un programa. (De esta manera puedes jugar usando una computadora). el juego se llama último , si cada jugador tiene un número finito de estrategias, y sin fin .– de lo contrario.

Con el fin de decidir juego , o encontrar solución de juego , Para cada jugador debemos elegir una estrategia que satisfaga la condición. optimidad , aquellos. uno de los jugadores debe recibir ganancia máxima, cuando el segundo se apega a su estrategia, al mismo tiempo el segundo jugador debe tener pérdida mínima , si el primero se apega a su estrategia. Este tipo de estrategias se denominan óptimo . Las estrategias óptimas también deben satisfacer la condición. sostenibilidad , aquellos. Debe ser desventajoso para cualquiera de los jugadores abandonar su estrategia en este juego.

Si el juego se repite varias veces, es posible que los jugadores no estén interesados ​​en ganar o perder en cada juego específico, sino en A ganancia (pérdida) promedio en todos los lotes.

El objetivo de la teoría de juegos es determinar la estrategia óptima para cada jugador.

21. Matriz de pago. Precio inferior y superior del juego.

El juego definitivo en el que el jugador A Tiene t estrategias y el jugador V-p estrategias se llama juego m×n.

Considere un juego m×n de dos jugadores. A Y EN(“nosotros” y “enemigo”).

deja que el jugador A tiene t estrategias personales, que denotamos como A1,A2,…,Am. deja que el jugador EN disponible norte estrategias personales, denotémoslas B1,B2,…,Bn.

Dejemos que cada lado elija una estrategia específica; para nosotros será Ai, para el enemigo Bj. Como resultado de la elección por parte de los jugadores de cualquier par de estrategias Ai y Bj (), el resultado del juego se determina de forma única, es decir, ganancias del jugador aij A(positivo o negativo) y pérdida (-aij) del jugador EN.

Supongamos que los valores de aij son conocidos para cualquier par de estrategias (Ai,Bj) . Matriz P=aij , cuyos elementos son los pagos correspondientes a las estrategias Ai y Bj, llamado matriz de pago o matriz del juego. Las filas de esta matriz corresponden a las estrategias del jugador. A, y las columnas – las estrategias del jugador B. Estas estrategias se llaman puras.

La matriz del juego m×n tiene la forma:

Considere un juego m×n con una matriz y determine la mejor entre las estrategias A1,A2,…,Am . Elegir estrategia Ai jugador A hay que esperar que el jugador EN lo responderá con una de las estrategias Bj por la cual el jugador gana A mínimo (jugador EN busca "perjudicar" al jugador A).

Denotemos por las ganancias más pequeñas del jugador. A cuando elige la estrategia Ai para todas las estrategias posibles del jugador EN(número más pequeño en iª fila de la matriz de pagos), es decir

Entre todos los números () elegimos el mayor: .

Llamemos el precio más bajo del juego, o ganancias máximas (maxmin). Esta es una victoria garantizada para el jugador A para cualquier estrategia del jugador B. Por eso,

La estrategia correspondiente a maximin se llama estrategia maximina . Jugador EN interesado en reducir las ganancias del jugador A, Al elegir la estrategia Bj, tiene en cuenta el máximo beneficio posible para A. denotemos

Entre todos los números, elige el más pequeño.

y llamemos precio superior del juego o victoria minimax(minimáx). El ego garantiza la pérdida del jugador B. Por lo tanto,

La estrategia correspondiente a minimax se llama estrategia minimax.

El principio que dicta a los jugadores elegir las estrategias minimax y maximin más “cautelosas” se llama principio minimax . Este principio se deriva del supuesto razonable de que cada jugador se esfuerza por lograr un objetivo opuesto al de su oponente.

Teorema. El precio inferior del juego no siempre supera el precio superior del juego. .

Si los precios superior e inferior del juego son iguales, entonces el valor total de los precios superior e inferior del juego se llama el precio puro del juego, o a costa del juego. Las estrategias Minimax correspondientes al precio del juego son estrategias optimas , y su totalidad - solucion optima o solución del juego. En este caso el jugador A recibe el máximo garantizado (independiente del comportamiento del jugador) EN) ganancias v y el jugador EN alcanza el mínimo garantizado (independientemente del comportamiento del jugador) A) perdiendo v. Dicen que la solución al juego tiene sostenibilidad , aquellos. Si un jugador se apega a su estrategia óptima, entonces no puede ser rentable para el otro desviarse de su estrategia óptima.

Si uno de los jugadores (por ejemplo A) se apega a su estrategia óptima, y ​​el otro jugador (EN) se desviará de su estrategia óptima de alguna manera, entonces para el jugador que hizo la desviación, ésta nunca podrá ser rentable; tal desviación del jugador EN En el mejor de los casos, puede dejar las ganancias sin cambios. y en el peor de los casos, aumentarlo.

Por el contrario, si EN se adhiere a su estrategia óptima, y A se desvía del suyo, entonces esto de ninguna manera puede ser beneficioso para A.

Un par de estrategias puras y da una solución óptima al juego si y sólo si el elemento correspondiente es tanto el más grande en su columna como el más pequeño en su fila. Esta situación, si existe, se llama PowerPoint. En geometría se llama un punto de una superficie que tiene la propiedad de tener un mínimo simultáneo en una coordenada y un máximo en otra. fuerza Por analogía, este término se utiliza en la teoría de juegos.

El juego para el cual , llamado jugando con un power point. Un elemento que tiene esta propiedad es el punto de fuerza de la matriz.

Entonces, para cada juego con power point, existe una solución que determina un par de estrategias óptimas para ambos bandos, diferenciándose en las siguientes propiedades.

1) Si ambas partes siguen sus estrategias óptimas, entonces el pago promedio es igual al costo neto del juego. v, que es simultáneamente su precio inferior y superior.

2) Si una de las partes se adhiere a su estrategia óptima y la otra se desvía de la suya, entonces la parte que se desvía solo puede perder y en ningún caso puede aumentar sus ganancias.

En la teoría de juegos, está demostrado que, en particular, cada juego con información completa tiene un punto de poder y, por lo tanto, cada juego tiene una solución, es decir, hay un par de estrategias óptimas de ambos lados, lo que da un pago promedio. igual al coste del juego. Si un juego con información completa consiste únicamente en movimientos personales, entonces cuando cada lado aplica su estrategia óptima, siempre debería terminar con un resultado bien definido, es decir, una ganancia exactamente igual al costo del juego.

22. Solución del juego en estrategias mixtas.

Entre los juegos finitos de importancia práctica, los juegos con un punto de fuerza son relativamente raros; un caso más típico es cuando el precio superior e inferior del juego son diferentes. Al analizar las matrices de tales juegos, llegamos a la conclusión de que si a cada jugador se le da la opción de una sola estrategia, entonces, contando con un oponente que actúe razonablemente, esta elección debe estar determinada por el principio minimax. Al seguir nuestra estrategia maximin, ante cualquier comportamiento del enemigo nos garantizamos obviamente una ganancia igual al precio más bajo del juego α. Estas estrategias combinadas, que consisten en el uso de varias estrategias puras, alternadas según una ley aleatoria con una cierta relación de frecuencia, se llaman en la teoría de juegos estrategias mixtas

Estrategia mixta sa El jugador A es la aplicación de las estrategias puras A1,A1,…,Ai,…,Am con probabilidades p1,p2,…pi,…pm, y la suma de las probabilidades es igual a 1: . Las estrategias mixtas del jugador A están escritas como una matriz.

o como una cadena Sa=(p1,p2,…,pi,…,pm).

De manera similar, las estrategias mixtas del jugador B se denotan por:

O Sb=(q1,q2,…,qi,…,qn),

donde la suma de las probabilidades de aparición de estrategias es igual a 1: .

Obviamente, cada estrategia pura es un caso especial de una mixta, en la que todas las estrategias excepto una se aplican con frecuencias (probabilidades) cero, y ésta se utiliza con una frecuencia (probabilidad) de 1.

Resulta que utilizando no sólo estrategias puras, sino también mixtas, es posible para cada juego finito obtener una solución, es decir, un par de estrategias (en el caso general mixtas) tales que cuando ambos jugadores las usan, el El pago será igual al precio del juego, y cuando cualquier desviación unilateral de la estrategia óptima sólo puede cambiar el pago en una dirección desfavorable para el desviado. Entonces, basándose en el principio minimax, se determina solucion optima (o solución) Juegos: estas son un par de estrategias óptimas. en el caso general, mixto, que tiene la siguiente propiedad: si uno de los jugadores se adhiere a su estrategia óptima, entonces para el otro no puede ser rentable desviarse de la suya. El pago correspondiente a la solución óptima se llama a costa del juego v . El precio del juego satisface la desigualdad:

Donde α y β son los precios superior e inferior del juego.

La declaración expresada constituye el contenido de la llamada Teorema fundamental de la teoría de juegos. Este teorema fue demostrado por primera vez por John von Neumann en 1928. Las demostraciones conocidas del teorema son relativamente complejas; Por tanto, daremos únicamente su formulación.

Todo juego finito tiene al menos una solución óptima, posiblemente entre estrategias mixtas.

Del teorema principal se deduce que todo juego finito tiene un precio.

Déjalo ser – un par de estrategias óptimas. Si una estrategia pura se incluye en una estrategia mixta óptima con una probabilidad distinta de cero, entonces se llama activo (útil) .

Justo teorema de estrategias activas: Si uno de los jugadores se apega a su estrategia mixta óptima, entonces el pago permanece sin cambios e igual al coste del juego v, si el segundo jugador no va más allá de los límites de sus estrategias activas.

El jugador puede utilizar cualquiera de sus estrategias activas en su forma pura y también puede mezclarlas en cualquier proporción.

Este teorema es de gran importancia práctica: proporciona modelos específicos para encontrar estrategias óptimas en ausencia de un punto de silla.

Consideremos juego de tamaño 2x2, que es el caso más simple de un juego finito. Si tal juego tiene un punto silla, entonces la solución óptima es un par de estrategias puras correspondientes a este punto.

Un juego en el que no existe punto de silla, de acuerdo con el teorema fundamental de la teoría de juegos. La solución óptima existe y está determinada por un par de estrategias mixtas. Y.

Para encontrarlos utilizamos el teorema de las estrategias activas. si el jugador A se apega a su estrategia óptima , entonces sus ganancias promedio serán iguales al precio del juego v, no importa qué estrategia activa utilice el jugador EN. Para un juego 2x2, cualquier estrategia pura del oponente está activa si no hay un punto medio. ganancias del jugador A(pérdida de jugador EN)– una variable aleatoria cuya expectativa matemática (valor medio) es el precio del juego. Por lo tanto, el pago del jugador promedio A(estrategia óptima) será igual a v tanto para la primera como para la segunda estrategia enemiga.

Dejemos que el juego esté dado por una matriz de pagos.

Ganancias promedio de los jugadores A, si utiliza una estrategia mixta óptima y el jugador EN - estrategia pura B1 (esto corresponde a la primera columna de la matriz de pagos R), igual al precio del juego v: .

El jugador recibe las mismas ganancias promedio. A, si el segundo jugador usa la estrategia B2, es decir . Considerando eso, obtenemos un sistema de ecuaciones para determinar la estrategia óptima. y precios de juegos v:

Resolviendo este sistema obtenemos la estrategia óptima.

y el precio del juego.

Aplicar el teorema sobre estrategias activas en la búsqueda. – La estrategia óptima del jugador. EN, encontramos que para cualquier estrategia de jugador puro A (A1 o A2) pérdida promedio de jugadores EN igual al precio del juego v, es decir.

Entonces la estrategia óptima está determinada por las fórmulas: .

El problema de resolver un juego, si su matriz no contiene un punto silla, es más difícil cuanto mayores sean los valores metro Y norte. Por tanto, en la teoría de los juegos matriciales se consideran métodos mediante los cuales la solución de unos juegos se reduce a la solución de otros más simples, en particular, reduciendo la dimensión de la matriz. La dimensión de la matriz se puede reducir excluyendo duplicando y obviamente improductivo estrategias.

Duplicar Se denominan estrategias que corresponden a los mismos valores de elementos de la matriz de pagos, es decir. la matriz contiene filas (columnas) idénticas.

Si todos los elementos de la i-ésima fila de la matriz son menores que los elementos correspondientes de la k-ésima fila, entonces la i-ésima estrategia para el jugador A no rentable (menos ganancia).

Si todos los elementos de la r-ésima columna de la matriz son mayores que los elementos correspondientes de la j-ésima columna, entonces para el jugador EN La estrategia r-ésima no es rentable (la pérdida es mayor).

El procedimiento para eliminar estrategias duplicadas y obviamente no rentables siempre debe preceder a la solución del juego.

23. Interpretación geométrica del juego 2x2.

solución de juego 2x2 permite una clara interpretación geométrica.

Sea el juego especificado por la matriz de pagos P=(aij), i, j=1,2.

En el eje de abscisas (Fig.) trazaremos unidad segmento A1A2; punto A1 ( X=0) representa la estrategia A1, punto A2 ( X=1) representa la estrategia A2, y todos los puntos intermedios de este segmento son estrategias mixtas Sa del primer jugador, y la distancia desde Sa al extremo derecho del segmento es la probabilidad p1 de la estrategia A1 , distancia al extremo izquierdo – probabilidad p2 de la estrategia A2 .

Dibujemos dos perpendiculares al eje de abscisas que pasan por los puntos A1 y A2: eje I-I y eje II-II. En el eje I-I trazaremos las ganancias de la estrategia A1; en el eje II-II – beneficios de la estrategia A2.

Si el jugador A usa la estrategia A1, entonces su pago con la estrategia B1 del jugador B es a11, y con la estrategia B2 es igual a a12. Los números a11 y a12 del eje I corresponden a los puntos B1 y B2.

Si el jugador A usa la estrategia A2, entonces su pago con la estrategia B1 del jugador B es a21, y con la estrategia B2 es igual a a22. Los números a21 y a22 corresponden a los puntos B1 y B2 del eje II.

Conectamos los puntos B1 (I) y B1 (II); B2 (I) y B2 (II). Tenemos dos líneas rectas. Directo B1B1– si el jugador A aplica una estrategia mixta (cualquier combinación de estrategias A1 y A2 con probabilidades p1 y p2) y el jugador B usa la estrategia B1. El jugador gana A corresponde a algún punto que se encuentra en esta línea. El pago promedio correspondiente a la estrategia mixta está determinado por la fórmula a11p1+a21p2 y está representado por el punto M1 en la recta B1B1.

De manera similar, construimos el segmento B2B2, correspondiente al uso de la estrategia B2 por parte del segundo jugador. En este caso, la ganancia promedio está determinada por la fórmula a12p1+a22p2 y está representada por el punto M2 en B2B2 directo.

Necesitamos encontrar la estrategia óptima S*a, es decir, aquella para la cual el pago mínimo (para cualquier comportamiento) EN) giraría al máximo. Para ello construiremos límite inferior de ganancias para estrategias B1B2 , es decir, la línea discontinua B1NB2 marcada en la Fig. línea gruesa. Este el límite inferior expresará las ganancias mínimas del jugador A con cualquiera de sus estrategias mixtas; puntonorte , en el que esta ganancia mínima alcanza un máximo, y determina la solución (estrategia óptima) y el precio del juego. punto de ordenadas norte hay un precio por el juego v. Coordenadas de puntos norte encontramos como las coordenadas de los puntos de intersección de las líneas B1B1 y B2B2. En nuestro caso, la solución del juego estuvo determinada por el punto de intersección de las estrategias. Sin embargo, este no será siempre el caso.

Geométricamente, uno puede determinar la estrategia óptima como jugador. A, el jugador también EN; en ambos casos se utiliza el principio minimax, pero en el segundo caso no se construye el límite inferior, sino el límite superior de ganancias, y no el máximo, sino el mínimo.

Si la matriz de pagos contiene números negativos, entonces para resolver el problema gráficamente es mejor pasar a una nueva matriz con elementos no negativos; Para ello, basta con sumar el número positivo correspondiente a los elementos de la matriz original. La solución del juego no cambiará, pero el precio del juego aumentará en este número. El método gráfico se puede utilizar para resolver el juego de 2×n, m×2.

24. Reducir un juego matricial a un problema de programación lineal

En el caso general, el juego m×n no tiene una interpretación geométrica clara. Su solución requiere bastante mano de obra para grandes t Y norte, sin embargo, no tiene dificultades fundamentales, ya que puede reducirse a resolver un problema de programación lineal. Mostrémoslo.

Sea el juego m×n dado por la matriz de pagos . Jugador A tiene estrategias A1,A2,..Ai,..Am , jugador EN - estrategias B 1,B 2,..B i,.. B norte. Es necesario determinar las estrategias óptimas y dónde son las probabilidades de utilizar las correspondientes estrategias puras Ai,Bj,

La estrategia óptima satisface el siguiente requisito. Proporciona al jugador A ganancias promedio, no menos que el precio del juego v, para cualquier estrategia de jugador. EN y ganancias iguales al precio del juego. v, con la estrategia óptima del jugador EN. Sin pérdida de generalidad suponemos v> 0; esto se puede lograr haciendo todos los elementos . si el jugador A aplica una estrategia mixta contra cualquier estrategia pura del jugador Bj EN, entonces el consigue ganancias promedio , o expectativa matemática de ganar (es decir, elementos j-GRAMOoh columnas de la matriz de pagos se multiplican término a término por las probabilidades correspondientes de las estrategias A1, A2,..Ai,..Am y se suman los resultados).

Para una estrategia óptima, todos los pagos promedio no son menores que el precio del juego. v, por tanto obtenemos un sistema de desigualdades:

Cada una de las desigualdades se puede dividir por un número. Introduzcamos nuevas variables: . Entonces el sistema toma la forma

Objetivo del jugador A - maximice sus ganancias garantizadas, es decir, precio del juego v.

Dividiendo por igualdad, encontramos que las variables satisfacen la condición: . Maximizando el precio del juego. v equivale a minimizar la cantidad , Por tanto, el problema se puede formular de la siguiente manera: determinar los valores de las variables , mamápara que satisfagan las restricciones lineales(*) Y mientras que la función lineal (2*) aplicado al mínimo.

Este es un problema de programación lineal. Resolviendo el problema (1*)–(2*), obtenemos la solución óptima y estrategia óptima .

Para determinar la estrategia óptima, se debe tener en cuenta que el jugador EN busca minimizar la ganancia garantizada, es decir encontrar máx. Las variables satisfacen las desigualdades.

que se derivan del hecho de que la pérdida media de un jugador EN no excede el precio del juego, sin importar qué estrategia pura use el jugador A.

Si denotamos (4*), obtenemos un sistema de desigualdades:

Las variables satisfacen la condición.

El juego se redujo al siguiente problema.

Determinar valores de variables , que satisfacen el sistema de desigualdades (5*)Y maximizar la función lineal

La solución al problema de programación lineal (5*), (6*) determina la estrategia óptima. Al mismo tiempo, el precio del juego. (7*)

Habiendo compilado matrices extendidas para los problemas (1*), (2*) y (5*), (6*), nos aseguramos de que una matriz se haya obtenido de otra mediante transposición:

Por tanto, los problemas de programación lineal (1*), (2*) y (5*), (6*) son mutuamente duales. Obviamente, al determinar estrategias óptimas en problemas específicos, se debe elegir uno de los problemas mutuamente duales cuya solución sea menos laboriosa y encontrar una solución al otro problema utilizando teoremas de dualidad.

Al resolver un juego finito arbitrario de tamaño m×n, se recomienda seguir el siguiente esquema:

1. Excluir de la matriz de pagos aquellas estrategias que obviamente no sean rentables en comparación con otras estrategias. Tales estrategias para el jugador. A

1. Materia y objetivos de la investigación operativa en economía. Conceptos básicos de la teoría de la investigación operativa.

El tema de la investigación de operaciones son los sistemas u organizaciones de gestión organizacional, que constan de una gran cantidad de unidades que interactúan y que no siempre son consistentes entre sí y pueden ser opuestas.

El propósito de la investigación de operaciones es fundamentar cuantitativamente las decisiones tomadas para gestionar las organizaciones.

La solución que resulta más beneficiosa para toda la organización se llama óptima, y ​​la solución que resulta más beneficiosa para una o más divisiones será subóptima.

La investigación de operaciones es una ciencia que se ocupa del desarrollo y la aplicación práctica de métodos para la gestión más óptima de los sistemas organizacionales.

Una operación es cualquier evento (sistema de acciones) unido por un solo plan y encaminado a lograr algún objetivo.

El propósito de la investigación operativa es la justificación cuantitativa preliminar de soluciones óptimas.

Cualquier elección específica de parámetros que dependen de nosotros se llama solución. Las soluciones óptimas son aquellas que son preferibles a otras en función de determinadas características.

Los parámetros cuya combinación forma una solución se denominan elementos de solución.

Al conjunto de soluciones factibles se les dan condiciones que son fijas y no pueden violarse.

Un indicador de eficiencia es una medida cuantitativa que permite comparar diferentes soluciones en términos de eficiencia.

2. El concepto de planificación y gestión de redes. Modelo de red del proceso y sus elementos.

El método para trabajar con gráficos de redes (planificación de redes) se basa en la teoría de grafos. Traducido del griego, un gráfico (grafpho - escribo) representa un sistema de puntos, algunos de ellos están conectados por líneas: arcos (o aristas). Este es un modelo topológico (matemático) de sistemas que interactúan. Con la ayuda de gráficos, puede resolver no solo problemas de planificación de redes, sino también otros problemas. El método de planificación de redes se utiliza cuando se planifica un conjunto de obras interrelacionadas. Le permite visualizar la secuencia organizativa y tecnológica del trabajo y establecer la relación entre ellos. Además, permite coordinar operaciones de diversos grados de complejidad e identificar operaciones de las que depende la duración de todo el trabajo (es decir, un evento organizacional), así como centrarse en la finalización oportuna de cada operación.

La base de la planificación y gestión de la red es el modelo de red (NM), que modela un conjunto de obras y eventos interconectados que reflejan el proceso de lograr un objetivo determinado. Puede presentarse en forma de gráfico o tabla.

Conceptos básicos del modelo de red:

Evento, trabajo, camino.

Los eventos son el resultado de uno o más trabajos. No tienen extensión en el tiempo.

Un camino es una cadena de trabajos que se suceden entre sí, conectando los vértices inicial y final.

La duración del viaje está determinada por la suma de las duraciones de las obras que lo componen.

3. Construcción y organización de un diagrama de red.

Un modelo de red se utiliza como modelo que refleja las relaciones tecnológicas y organizativas del proceso de trabajo de construcción e instalación en los sistemas de planificación y gestión de redes (NPS).

Un modelo de red es una representación gráfica de procesos, cuya implementación conduce al logro de uno o más objetivos establecidos, indicando las relaciones establecidas entre estos procesos. El diagrama de red es un modelo de red con parámetros de tiempo calculados.

La estructura del diagrama de red, que determina la dependencia mutua de actividades y eventos, se denomina topología.

El trabajo es un proceso de producción que requiere tiempo, mano de obra y recursos materiales, que, una vez finalizado, conduce al logro de determinados resultados.

Una dependencia (trabajo ficticio) que no requiere tiempo se representa con una flecha punteada. El trabajo ficticio se utiliza en un diagrama de red para mostrar relaciones entre eventos y actividades.

El diagrama de red utiliza tiempo, costo y otras características del trabajo.

Trabajo continuo: el tiempo que lleva completar este trabajo en días hábiles u otras unidades de tiempo que son iguales para todos los trabajos en el cronograma de la red. La duración del trabajo puede ser una variable determinada (determinista) o aleatoria especificada por la ley de su distribución.

El costo de la obra son los costos directos necesarios para completarla, dependiendo de la duración y condiciones de esta obra.

Los recursos se caracterizan por la necesidad de unidades físicas necesarias para completar un trabajo determinado.

La calidad, la confiabilidad y otros indicadores del trabajo sirven como características adicionales del trabajo.

Un evento es el hecho de la finalización de uno o más trabajos, que es necesario y suficiente para el inicio de uno o más trabajos posteriores. A cada evento se le asigna un número llamado código. Cada trabajo está definido por dos eventos: un código de evento inicial, indicado por i, y un código de evento final, indicado por j.

Los eventos que no tienen trabajo previo se denominan iniciales; Los eventos que no tienen otros posteriores son finitos.

1 La dirección de la construcción de la red puede ser de diferente naturaleza. El diagrama de red se puede construir desde el evento inicial al final y desde el final al inicial, así como desde cualquiera de los eventos al inicial o final.

2 Al construir una red, se resuelven los siguientes problemas:

Qué trabajo(s) se debe(n) completar para comenzar este trabajo;

Qué trabajo es recomendable realizar en paralelo con este trabajo;

3 El cronograma inicial de la red se construye sin tener en cuenta la duración de las obras que componen la red.

4 La forma del gráfico debe ser simple y visualmente fácil de percibir.

5 Sólo puede ocurrir un trabajo entre dos eventos. Durante la construcción de edificios y estructuras, el trabajo se puede realizar de forma secuencial, en paralelo o simultáneamente, algunos de forma secuencial y otros en paralelo, como resultado de lo cual se desarrollan diversas dependencias entre los trabajos individuales.

La numeración (codificación) de eventos se realiza una vez finalizada la construcción de la red, desde el evento inicial hasta el final.

4. Ruta crítica del diagrama de red. Reservas de tiempo. Fechas tempranas y tardías de eventos y trabajo en el cronograma de la red.

En un diagrama de red, puede haber varias rutas entre los eventos de inicio y fin. El camino con mayor duración se llama crítico. La ruta crítica determina la duración total de la actividad. Todos los demás caminos tienen una duración menor, por lo que el trabajo realizado en ellos tiene reservas de tiempo.

La ruta crítica se indica en el diagrama de red mediante líneas gruesas o dobles (flechas).

Dos conceptos son de particular importancia al elaborar un diagrama de red:

El inicio anticipado del trabajo es un período antes del cual este trabajo no se puede iniciar sin violar la secuencia tecnológica aceptada. Está determinado por el camino más largo desde el evento inicial hasta el inicio de este trabajo.

La finalización tardía del trabajo es el último plazo para completar el trabajo, en el que la duración total del trabajo no aumenta. Está determinado por el camino más corto desde un evento determinado hasta la finalización de todo el trabajo.

La finalización anticipada es una fecha límite antes de la cual no se puede completar el trabajo. Es igual al inicio anticipado más la duración de este trabajo.

Inicio tardío: período después del cual no se puede iniciar el trabajo sin aumentar la duración total de la construcción. Es igual a la finalización tardía menos la duración de este trabajo.

Si un evento es el final de un solo trabajo (es decir, solo una flecha está dirigida hacia él), entonces el final temprano de este trabajo coincide con el comienzo temprano del siguiente.

La reserva general (completa) es el tiempo máximo durante el cual se puede retrasar la finalización de un trabajo determinado sin aumentar la duración total del trabajo. Está determinada por la diferencia entre empezar tarde y temprano (o terminar tarde y temprano, que es lo mismo).

La reserva privada (gratuita) es el tiempo máximo durante el cual se puede retrasar la ejecución de un trabajo determinado sin cambiar el inicio anticipado del siguiente. Esta reserva sólo es posible cuando el evento incluye dos o más trabajos (dependencias), es decir. dos o más flechas (sólidas o punteadas) se dirigen hacia él. Entonces sólo uno de estos trabajos tendrá un final anticipado que coincide con el inicio anticipado del siguiente trabajo, pero para el resto serán valores diferentes. Esta diferencia para cada puesto de trabajo será su reserva privada.

5. Programación dinámica. Principio de optimización y control de Bellman.

La programación dinámica es uno de los métodos de optimización más poderosos. Especialistas de diversos perfiles se ocupan de los problemas de la toma de decisiones racionales, la elección de las mejores opciones y una gestión óptima. Entre los métodos de optimización, la programación dinámica ocupa una posición especial. Este método es extremadamente atractivo debido a la simplicidad y claridad de su principio básico: el principio de optimización. El ámbito de aplicación del principio de optimización es extremadamente amplio; la gama de problemas a los que se puede aplicar aún no se ha delineado completamente. Desde el principio, la programación dinámica ha sido un medio para resolver prácticamente problemas de optimización.

Además del principio de optimización, el principal método de investigación, la idea de sumergir un problema de optimización específico en una familia de problemas similares juega un papel importante en el aparato de programación dinámica. Su tercera característica, que lo distingue de otros métodos de optimización, es la forma del resultado final. La aplicación del principio de optimización y el principio de inmersión en procesos discretos de varios pasos conduce a ecuaciones funcionales recurrentes sobre el valor óptimo del criterio de calidad. Las ecuaciones resultantes permiten escribir consistentemente controles óptimos para el problema original. El beneficio aquí es que el problema de calcular el control para todo el proceso se divide en una serie de problemas más simples de calcular el control para etapas individuales del proceso.

El principal inconveniente del método es, en palabras de Bellman, la "maldición de la dimensionalidad": su complejidad aumenta catastróficamente a medida que aumenta la dimensión del problema.

6. El problema de la distribución de fondos entre empresas.

Podemos decir que el procedimiento para construir el control óptimo mediante el método de programación dinámica se divide en dos etapas: preliminar y final. En la etapa preliminar, para cada paso, el SOE se determina dependiendo del estado del sistema (logrado como resultado de los pasos anteriores), y la ganancia condicionalmente óptima en todos los pasos restantes, a partir de este, también dependiendo del estado. . En la etapa final se determina el control óptimo (incondicional) para cada paso. La optimización preliminar (condicional) se realiza paso a paso en orden inverso: del último paso al primero; optimización final (incondicional), también en pasos, pero en un orden natural: desde el primer paso hasta el último. De las dos etapas de optimización, la primera es incomparablemente más importante y requiere más tiempo. Una vez completada la primera etapa, completar la segunda no presenta ninguna dificultad: solo queda “leer” las recomendaciones ya elaboradas en la primera etapa.

7. Planteamiento del problema de programación lineal.

La programación lineal es una herramienta popular para resolver problemas económicos que se caracterizan por la presencia de un criterio (por ejemplo, maximizar los ingresos de la producción mediante la elección óptima de un programa de producción o, por ejemplo, minimizar los costos de transporte, etc.). Los problemas económicos se caracterizan por limitaciones de recursos (materiales y/o financieros). Están escritos en forma de sistema de desigualdades, a veces en forma de igualdades.

Desde el punto de vista de la previsión de intervalos de precios aceptables (o volúmenes de ventas) en el marco del método no paramétrico generalizado, el uso de programación lineal significa:

El criterio es el precio MÁXIMO del siguiente producto del grupo de interés f.

Las variables controladas son los precios de todos los productos del grupo f.

Las limitaciones en nuestro problema de pronóstico utilizando el método no paramétrico generalizado son:

a) un sistema de desigualdades (limitaciones a la racionalidad del comportamiento del consumidor) (ver 4.2. Previsión en el marco del método no paramétrico generalizado);

b) el requisito de no negatividad de las variables controladas (en nuestro problema de pronóstico exigiremos que los precios de los productos del grupo f no caigan por debajo del 80% de los valores de los precios en el último momento);

c) restricción presupuestaria en forma de igualdad: el requisito de que el monto de los costos para la compra de productos del grupo f sea constante (teniendo en cuenta una inflación del 15%, por ejemplo).

8. Método gráfico para la resolución de problemas de programación lineal.

El método gráfico se basa en la interpretación geométrica del problema de programación lineal y se utiliza principalmente para resolver problemas en un espacio bidimensional y solo algunos problemas en un espacio tridimensional, ya que es bastante difícil construir un poliedro solución que esté formado como resultado de la intersección de semiespacios. Generalmente es imposible representar gráficamente un problema en un espacio de dimensiones mayores a tres.

Sea el problema de programación lineal especificado en un espacio bidimensional, es decir, las restricciones contienen dos variables.

Encuentra el valor mínimo de una función.

(2.1) Z = С1х1+С2х2

a11x1 + a22x2 b1

(2.2)a21x1 + a22x2 b2

aM1x1 + aM2x2 bM

(2.3) x1 0, x2 0

Supongamos que el sistema (2.2) bajo la condición (2.3) es consistente y su polígono solución está acotado. Cada una de las desigualdades (2.2) y (2.3), como se señaló anteriormente, define un semiplano con líneas límite: ai1x1 + ai2x2 + ai3x3 = bi,(i = 1, 2, ..., n), x1=0 , x2=0 . La función lineal (2.1) para valores fijos de Z es la ecuación de una recta: C1x1 + C2x2 = const. Construyamos un polígono de soluciones al sistema de restricciones (2.2) y una gráfica de la función lineal (2.1) en Z = 0 (figura 2.1). Entonces al problema de programación lineal planteado se le puede dar la siguiente interpretación. Encuentre el punto del polígono solución en el cual la línea de soporte C1x1 + C2x2 = const y la función Z alcanza un mínimo.

Los valores de Z = C1x1 + C2x2 aumentan en la dirección del vector N = (C1, C2), por lo que movemos la recta Z = 0 paralela a sí misma en la dirección del vector X. De la Fig. 2.1 se deduce que la línea recta se convierte dos veces en una línea de referencia en relación con el polígono solución (en los puntos A y C), y toma el valor mínimo en el punto A. Las coordenadas del punto A (x1, x2) se encuentran resolviendo la sistema de ecuaciones de rectas AB y AE.

Si el polígono solución es un área poligonal ilimitada, entonces son posibles dos casos.

Caso 1. La recta C1x1 + C2x2 = constante, que se mueve en la dirección del vector N o en dirección opuesta a él, interseca constantemente el polígono solución y no es soporte del mismo en ningún punto. En este caso, la función lineal no está acotada en el polígono solución ni arriba ni abajo (figura 2.2).

Caso 2. La línea recta, en movimiento, se convierte, sin embargo, en un soporte con respecto al polígono de soluciones (Fig. 2.2, a - 2.2, c). Luego, dependiendo del tipo de área, la función lineal puede estar acotada desde arriba e ilimitada desde abajo (Fig. 2.2, a), acotada desde abajo e ilimitada desde arriba (Fig. 2.2, b), o acotada tanto desde abajo como desde arriba (Fig. 2.2, c).

9. Método símplex.

El método simplex es el principal en programación lineal. La solución del problema comienza considerando uno de los vértices del poliedro de condiciones. Si el vértice en estudio no corresponde al máximo (mínimo), entonces se mueven al vecino, aumentando el valor de la función objetivo al resolver el problema para el máximo y disminuyéndolo al resolver el problema para el mínimo. Por tanto, pasar de un vértice a otro mejora el valor de la función objetivo. Dado que el número de vértices del poliedro es limitado, en un número finito de pasos se garantiza encontrar el valor óptimo o establecer el hecho de que el problema no tiene solución.

Este método es universal, aplicable a cualquier problema de programación lineal en forma canónica. El sistema de restricciones aquí es un sistema de ecuaciones lineales en el que el número de incógnitas es mayor que el número de ecuaciones. Si el rango del sistema es r, entonces podemos elegir r incógnitas, que expresamos en términos de las incógnitas restantes. Para mayor precisión, suponemos que se seleccionan las primeras incógnitas consecutivas X1, X2, ..., Xr. Entonces nuestro sistema de ecuaciones se puede escribir como

El método simplex se basa en un teorema llamado teorema fundamental del método simplex. Entre los planes óptimos de un problema de programación lineal en forma canónica existe necesariamente una solución de referencia a su sistema de restricciones. Si el plan óptimo del problema es único, entonces coincide con alguna solución de referencia. Hay un número finito de diferentes soluciones de apoyo al sistema de restricciones. Por lo tanto, se podría buscar una solución al problema en forma canónica buscando entre las soluciones de referencia y eligiendo entre ellas aquella para la cual el valor F sea mayor. Pero, en primer lugar, todas las soluciones de referencia son desconocidas y es necesario encontrarlas y, en segundo lugar, en los problemas reales hay muchas de estas soluciones y la búsqueda directa es casi imposible. El método simplex es un procedimiento determinado para la enumeración dirigida de soluciones de soporte. A partir de una determinada solución de referencia encontrada de antemano utilizando un determinado algoritmo del método simplex, calculamos una nueva solución de referencia en la que el valor de la función objetivo F no es menor que el de la anterior. Luego de una serie de pasos llegamos a una solución de referencia, que es el plan óptimo.

10. Planteamiento del problema del transporte. Métodos para determinar los planes de referencia.

Hay m puntos de partida (“proveedores”) y n puntos de consumo (“consumidores”) de algún producto idéntico. Para cada elemento se define lo siguiente:

ai - volúmenes de producción del i-ésimo proveedor, i = 1,…, m;

âj - demanda del j-ésimo consumidor, j= 1,…,n;

сij es el costo de transportar una unidad de producto desde el punto Ai, el i-ésimo proveedor, hasta el punto Bj, el j-ésimo consumidor.

Para mayor claridad, es conveniente presentar los datos en forma de tabla, lo que se denomina tabla de costos de transporte.

Es necesario encontrar un plan de transporte que satisfaga plenamente la demanda de todos los consumidores, al mismo tiempo que haya suficiente oferta de proveedores y los costos totales de transporte sean mínimos.

El plan de transporte se refiere al volumen de transporte, es decir. la cantidad de bienes que deben transportarse desde el i-ésimo proveedor hasta el j-ésimo consumidor. Para construir un modelo matemático del problema, es necesario ingresar m·n variables xij, i= 1,..., n, j= 1,..., m, cada variable xij denota el volumen de transporte desde el punto Ai para señalar Bj. El conjunto de variables X = (xij) será el plan que se deberá encontrar a partir de la formulación del problema.

Esta es una condición para resolver problemas de transporte cerrados y abiertos (CTZ).

Obviamente, para que el Problema 1 tenga solución, es necesario que la demanda total no exceda el volumen de producción de los proveedores:

Si esta desigualdad se satisface estrictamente, entonces el problema se llama "abierto" o "desequilibrado", pero si , entonces el problema se llama problema de transporte "cerrado" y tendrá la forma (2):

Condición de equilibrio.

Esta es una condición para resolver problemas de transporte cerrado (CTP).

11. Algoritmo de resolución del problema del transporte.

La aplicación del algoritmo requiere el cumplimiento de una serie de requisitos previos:

1. Debe conocerse el coste de transportar una unidad de producto desde cada punto de producción hasta cada destino.

2. Deberá conocerse el stock de productos en cada punto de producción.

3. Se deben conocer los requisitos del producto en cada punto de consumo.

4. La oferta total debe ser igual a la demanda total.

El algoritmo para resolver el problema del transporte consta de cuatro etapas:

Etapa I: Presentar los datos en forma de tabla estándar y encontrar cualquier asignación de recursos factible. Es aceptable una distribución de recursos que permita satisfacer toda la demanda en los destinos y retirar todo el stock de productos de los puntos de producción.

Etapa 2. Comprobación de la optimización de la asignación de recursos resultante

Etapa 3. Si la asignación de recursos resultante no es óptima, entonces los recursos se redistribuyen, reduciendo el costo del transporte.

Etapa 4. Volver a comprobar la optimización de la asignación de recursos resultante.

Este proceso iterativo se repite hasta obtener la solución óptima.

12. Modelos de gestión de inventarios.

A pesar de que cualquier modelo de gestión de inventarios está diseñado para responder dos preguntas principales (cuándo y cuánto), existe una cantidad significativa de modelos en cuya construcción se utilizan una variedad de herramientas matemáticas.

Esta situación se explica por la diferencia en las condiciones iniciales. La base principal para clasificar los modelos de gestión de inventarios es la naturaleza de la demanda de productos almacenados (recordemos que desde el punto de vista de una gradación más general, ahora consideramos solo casos con demanda independiente).

Entonces, dependiendo de la naturaleza de la demanda, los modelos de gestión de inventarios pueden ser

determinista;

probabilístico.

A su vez, la demanda determinista puede ser estática, cuando la intensidad del consumo no cambia con el tiempo, o dinámica, cuando la demanda confiable puede cambiar con el tiempo.

La demanda probabilística puede ser estacionaria, cuando la función de densidad de probabilidad de la demanda no cambia con el tiempo, y no estacionaria, donde la función de densidad de probabilidad cambia según el tiempo. La clasificación anterior se ilustra en la figura.

El caso más simple es el de la demanda estática determinista de productos. Sin embargo, este tipo de consumo es bastante raro en la práctica. Los modelos más complejos son los modelos de tipo no estacionario.

Además de la naturaleza de la demanda de productos, al crear modelos de gestión de inventarios, se deben tener en cuenta muchos otros factores, por ejemplo:

Plazos para el cumplimiento del pedido. La duración del período de contratación puede ser constante o una variable aleatoria;

proceso de reposición de inventario. Puede ser instantáneo o distribuido en el tiempo;

existencia de restricciones sobre capital de trabajo, espacio de almacén, etc.

13. Sistemas de colas (QS) e indicadores de su eficacia.

Los sistemas de colas (QS) son sistemas de un tipo especial que implementan la ejecución repetida de tareas similares. Estos sistemas desempeñan un papel importante en muchas áreas de la economía, las finanzas, la producción y la vida cotidiana. Como ejemplos de QS en el ámbito financiero y económico; en este ámbito podemos citar bancos de diversos tipos (comerciales, de inversión, hipotecarios, innovadores, de ahorro), organizaciones de seguros, sociedades anónimas estatales, compañías, firmas, asociaciones, cooperativas, inspecciones fiscales, servicios de auditoría, diversos sistemas de comunicación (incluidos centrales telefónicas), complejos de carga y descarga (puertos, estaciones de carga), gasolineras, empresas diversas y organizaciones de servicios (tiendas, mostradores de información, peluquerías, taquillas, casas de cambio, talleres de reparación, hospitales). Como una especie de QS también se pueden considerar sistemas como redes informáticas, sistemas de recopilación, almacenamiento y procesamiento de información, sistemas de transporte, áreas de producción automatizadas, líneas de producción, diversos sistemas militares, en particular sistemas de defensa aérea o antimisiles.

Cada QS incluye en su estructura una cierta cantidad de dispositivos de servicio, que se denominan canales de servicio (dispositivos, líneas). El papel de los canales puede ser desempeñado por varios dispositivos, personas que realizan determinadas operaciones (cajeros, operadores, peluqueros, vendedores), líneas de comunicación, automóviles, grúas, equipos de reparación, vías de tren, gasolineras, etc.

Los sistemas de colas pueden ser monocanal o multicanal.

Cada QS está diseñado para atender (cumplir) un determinado flujo de aplicaciones (requisitos) que llegan a la entrada del sistema, en su mayoría no de forma regular, sino en momentos aleatorios. El servicio de las aplicaciones, en este caso, tampoco dura un tiempo constante y conocido, sino un tiempo aleatorio, que depende de muchas razones aleatorias, a veces desconocidas para nosotros. Después de atender la solicitud, el canal queda libre y listo para recibir la siguiente solicitud. La naturaleza aleatoria del flujo de solicitudes y el tiempo de su servicio conduce a una carga desigual del QS: en otras ocasiones, las aplicaciones no atendidas pueden acumularse en la entrada del QS, lo que conduce a una sobrecarga del QS y, a veces, cuando hay canales libres en la entrada del QS, no habrá aplicaciones, lo que conduce a una subcarga del QS, es decir, e. a la inactividad de sus canales. Las solicitudes que se acumulan en la entrada del QS se "unen" a la cola o, debido a la imposibilidad de permanecer más tiempo en la cola, dejan el QS sin servicio.

Indicadores de la efectividad del funcionamiento del par “CMO - consumidor”, donde se entiende por consumidor el conjunto completo de aplicaciones o algunas de sus fuentes (por ejemplo, el ingreso promedio generado por la CMO por unidad de tiempo, etc. ). Este grupo de indicadores resulta útil en los casos en que algunos ingresos recibidos por el servicio de aplicaciones y los costos del servicio se miden en las mismas unidades. Estos indicadores suelen ser de naturaleza muy específica y están determinados por las características específicas del QS, las solicitudes atendidas y la disciplina del servicio.

14. Ecuaciones dinámicas para estados probabilísticos (ecuaciones de Kolmogorov). Limitar las probabilidades de los estados.

Derivando formalmente la ecuación de Kolmogorov-Chapman con respecto a s en s = 0, obtenemos la ecuación directa de Kolmogorov:

Derivando formalmente la ecuación de Kolmogorov-Chapman con respecto a t en t = 0, obtenemos la ecuación inversa de Kolmogorov

Se debe enfatizar que para espacios de dimensiones infinitas el operador ya no es necesariamente continuo y no puede definirse en todas partes, por ejemplo, como un operador diferencial en el espacio de distribuciones.

Si el número de estados del sistema S es finito y parece posible pasar de cada estado (en un cierto número de pasos) a otros estados, entonces las probabilidades límite de los estados existen y tampoco dependen del estado inicial. del sistema.

En la Fig. Se muestra un gráfico de estados y transiciones que satisfacen la condición establecida: desde cualquier estado, el sistema tarde o temprano puede pasar a cualquier otro estado. La condición no se cumplirá cuando cambie la dirección de la flecha 4-3 en el gráfico de la Fig., sino al contrario.

Supongamos que se cumple la condición establecida y, por tanto, existen las probabilidades límite:

Las probabilidades límite se indicarán con las mismas letras que las probabilidades de estados, mientras que significan números, no variables (funciones del tiempo).

Está claro que las probabilidades límite de los estados deben sumar uno: en consecuencia, en el sistema se establece un cierto régimen estacionario límite: incluso si el sistema cambia sus propios estados aleatoriamente, la probabilidad de cada uno de estos estados no dependen del tiempo y cada uno de ellos ocurre con alguna probabilidad constante, que es el tiempo relativo promedio que el sistema permanece en este estado.

15. El proceso de muerte y reproducción.

Llamemos a un proceso de Markov de muerte y reproducción con tiempo continuo un proceso que sólo puede tomar valores enteros no negativos; Los cambios en este proceso pueden ocurrir en cualquier momento t, mientras que en cualquier momento puede aumentar en uno o permanecer sin cambios.

Los flujos de reproducción λi(t) se denominarán flujos de Poisson y conducirán a un aumento de la función X(t). Por tanto, μi(t) son los flujos de muerte que conducen a una disminución de la función X(t).

Compongamos la ecuación de Kolmogorov a partir del gráfico:

Si el flujo es de estado finito:

El sistema de ecuaciones de Kolmogorov para el proceso de muerte y reproducción con un número limitado de estados tiene la forma:

El proceso de reproducción pura es un proceso de muerte y reproducción en el que las intensidades de todos los flujos de muerte son iguales a cero.

El proceso de muerte pura es un proceso de muerte y reproducción en el que las intensidades de todos los flujos de reproducción son iguales a cero.

16. Sistemas de colas con fallas..

El más simple de los problemas considerados en el marco de la teoría de colas es el modelo de un QS de un solo canal con fallas o pérdidas.

Cabe señalar que en este caso el número de canales es 1 (). Este canal recibe un flujo de solicitudes de Poisson cuya intensidad es igual a . El tiempo afecta la intensidad:

Si una solicitud llega a un canal que actualmente no es gratuito, es rechazada y deja de figurar en el sistema. El servicio de aplicaciones se realiza durante un tiempo aleatorio, cuya distribución se implementa de acuerdo con la ley exponencial con el parámetro:

17. Sistemas de colas con espera..

Una solicitud recibida cuando el canal está ocupado se pone en cola y espera servicio.

Sistema con longitud de cola limitada. Supongamos primero que el número de lugares en la cola está limitado por m, es decir, si una aplicación llega en un momento en el que ya hay m aplicaciones en la cola, deja el sistema sin servicio. En el futuro, dirigiendo m al infinito, obtendremos las características de un QS de un solo canal sin restricciones en la longitud de la cola.

Numeraremos los estados del QS según la cantidad de aplicaciones en el sistema (tanto en servicio como en espera de servicio):

— el canal es gratuito;

— el canal está ocupado, no hay cola;

— el canal está ocupado, hay una solicitud en cola;

—el canal está ocupado, k - 1 solicitudes están en cola;

— el canal está ocupado, hay toneladas de aplicaciones en cola.

18. Métodos de toma de decisiones en condiciones de conflicto. Juegos de matrices. Juegos de estrategia pura y mixta.

Un juego matricial es un juego finito de suma cero entre dos jugadores, en el que el pago del jugador 1 se especifica en forma de matriz (la fila de la matriz corresponde al número de la estrategia aplicada del jugador 2, la columna corresponde al número de la estrategia aplicada del jugador 2; en la intersección de la fila y columna de la matriz está el pago del jugador 1, apropiado a las estrategias aplicadas).

Para los juegos matriciales se ha demostrado que cualquiera de ellos tiene solución y se puede encontrar fácilmente reduciendo el juego a un problema de programación lineal.

Un juego matricial de suma cero para dos jugadores puede considerarse como el siguiente juego abstracto para dos jugadores.

El primer jugador tiene m estrategias i = 1,2,...,m, el segundo jugador tiene n estrategias j = 1,2,...,n. Cada par de estrategias (i,j) está asociado con un número aij, que expresa la ganancia del jugador 1 a expensas del jugador 2 si el primer jugador acepta su i-ésima estrategia, y 2 - su j-ésima estrategia.

Cada jugador hace un movimiento: el jugador 1 elige su i-ésima estrategia (i=), 2 - su j-ésima estrategia (j=), después de lo cual el jugador 1 recibe el pago aij a expensas del jugador 2 (si aij

Cada estrategia del jugador i=; j = a menudo se denomina estrategia pura.

Definición. La estrategia mixta de un jugador es el conjunto completo de probabilidades de utilizar sus estrategias puras.

Así, si el jugador 1 tiene m estrategias puras 1,2,...,m, entonces su estrategia mixta x es un conjunto de números x = (x1,..., xm) que satisfacen las relaciones

xi³ 0 (i= 1,m), =1.

De manera similar, para el jugador 2, que tiene n estrategias puras, la estrategia mixta y es el conjunto de números

y = (y1, ..., yn), yj ³ 0, (j = 1,n), = 1.

Dado que cada vez que un jugador usa una estrategia pura excluye el uso de otra, las estrategias puras son eventos incompatibles. Además, son los únicos acontecimientos posibles.

La estrategia pura es un caso especial de estrategia mixta. De hecho, si en una estrategia mixta se aplica cualquier i-ésima estrategia pura con probabilidad 1, entonces no se aplican todas las demás estrategias puras. Y esta i-ésima estrategia pura es un caso especial de estrategia mixta. Para mantener el secreto, cada jugador aplica sus propias estrategias independientemente de las elecciones del otro jugador.

19. Método geométrico para resolver un juego matricial.

La solución de juegos de tamaño 2xn o nx2 permite una interpretación geométrica clara. Estos juegos se pueden resolver gráficamente.

En el plano XY a lo largo del eje de abscisas trazamos un único segmento A1A2 (Figura 5.1). Asignemos a cada punto del segmento alguna estrategia mixta U = (u1, u2). Además, la distancia desde algún punto intermedio U hasta el extremo derecho de este segmento es la probabilidad u1 de elegir la estrategia A1, la distancia hasta el extremo izquierdo es la probabilidad u2 de elegir la estrategia A2. El punto A1 corresponde a la estrategia pura A1, el punto A2 corresponde a la estrategia pura A2.

En los puntos A1 y A2 restauraremos las perpendiculares y depositaremos en ellas las ganancias de los jugadores. En la primera perpendicular (que coincide con el eje OY) mostramos el pago del jugador A cuando usa la estrategia A1, en la segunda, cuando usa la estrategia A2. Si el jugador A usa la estrategia A1, entonces su pago con la estrategia B1 del jugador B es igual a 2, y con la estrategia B2 es igual a 5. Los números 2 y 5 en el eje OY corresponden a los puntos B1 y B2. De manera similar, en la segunda perpendicular encontramos los puntos B"1 y B"2 (ganancias 6 y 4).

Al conectar los puntos B1 y B"1, B2 y B"2, obtenemos dos líneas rectas, cuya distancia al eje OX determina el pago promedio para cualquier combinación de estrategias correspondientes.

Por ejemplo, la distancia desde cualquier punto del segmento B1B"1 al eje OX determina el pago promedio del jugador A para cualquier combinación de las estrategias A1 y A2 (con probabilidades u1 y u2) y la estrategia B1 del jugador B.

Las ordenadas de los puntos pertenecientes a la línea discontinua B1MB"2 determinan el pago mínimo del jugador A cuando utiliza estrategias mixtas. Este valor mínimo es mayor en el punto M, por lo tanto, este punto corresponde a la estrategia óptima U* = ( ,), y su ordenada es igual al coste del juego v .

Encontramos las coordenadas del punto M como las coordenadas del punto de intersección de las líneas B1B"1 y B2B"2.

Para hacer esto, necesitas conocer las ecuaciones de líneas. Puedes crear tales ecuaciones usando la fórmula para la ecuación de una línea que pasa por dos puntos:

Creemos ecuaciones en línea recta para nuestro problema.

Línea B1B"1: = o y = 4x + 2.

Directo B2B"2: = o y = -x + 5.

Obtenemos el sistema: y = 4x + 2,

Resolvámoslo: 4x + 2 = -x + 5,

x = 3/5, y = -3/5 + 5 = 22/5.

Por tanto, U = (2/5, 3/5), v = 22/5.

20. Juegos bimatriz.

Un juego bimatriz es un juego finito de dos jugadores con una suma distinta de cero, en el que los pagos de cada jugador se especifican mediante matrices por separado para el jugador correspondiente (en cada matriz, una fila corresponde a la estrategia del jugador 1, una columna corresponde a la estrategia del jugador 2, en la intersección de la fila y la columna en la primera matriz está el pago del jugador 1, en la segunda matriz, el pago del jugador 2.)

También se ha desarrollado una teoría del comportamiento óptimo del jugador para los juegos bimatriciales, pero resolver estos juegos es más difícil que los juegos matriciales ordinarios.

21. Juegos de estadística. Principios y criterios para la toma de decisiones en condiciones de incertidumbre total y parcial.

En la investigación de operaciones es común distinguir tres tipos de incertidumbres:

incertidumbre de metas;

la incertidumbre de nuestro conocimiento sobre el medio ambiente y los factores que actúan en este fenómeno (incertidumbre de la naturaleza);

incertidumbre de las acciones de un socio o adversario activo o pasivo.

En la clasificación anterior, el tipo de incertidumbre se considera desde la perspectiva de uno u otro elemento del modelo matemático. Por ejemplo, la incertidumbre de los objetivos se refleja al plantear una tarea en la elección de criterios individuales o de todo el vector de efecto beneficioso.

Por otro lado, los otros dos tipos de incertidumbres afectan principalmente a la formulación de la función objetivo de las ecuaciones de restricción y al método de decisión. Por supuesto, la afirmación anterior es bastante condicional, como lo es cualquier clasificación. Lo presentamos sólo con el objetivo de resaltar algunas características más de las incertidumbres que deben tenerse en cuenta en el proceso de toma de decisiones.

La cuestión es que, además de la clasificación de las incertidumbres discutidas anteriormente, es necesario tener en cuenta su tipo (o “género”) desde el punto de vista de su relación con la aleatoriedad.

Sobre esta base, se puede distinguir la incertidumbre estocástica (probabilística), cuando los factores desconocidos son estadísticamente estables y, por lo tanto, representan objetos ordinarios de la teoría de la probabilidad: variables aleatorias (o funciones aleatorias, eventos, etc.). En este caso, se deben conocer o determinar todas las características estadísticas necesarias (leyes de distribución y sus parámetros) al plantear el problema.

Un ejemplo de este tipo de tareas puede ser, en particular, un sistema de mantenimiento y reparación de cualquier tipo de equipo, un sistema de organización de aclareos, etc.

Otro caso extremo puede ser la incertidumbre de tipo no estocástico (en palabras de E.S. Ventzel - "mala incertidumbre"), en la que no existen supuestos sobre la estabilidad estocástica. Finalmente, podemos hablar de un tipo intermedio de incertidumbre, cuando se toma una decisión sobre la base de algunas hipótesis sobre las leyes de distribución de variables aleatorias. Al mismo tiempo, quien toma las decisiones debe tener presente el peligro de una discrepancia entre sus resultados y las condiciones reales. Este riesgo de descalce se formaliza mediante coeficientes de riesgo.

La toma de decisiones en condiciones de riesgo puede basarse en uno de los siguientes criterios:

criterio de valor esperado;

combinaciones de valor esperado y varianza;

nivel límite conocido;

el evento más probable en el futuro.

Operación Se llama cualquier evento (sistema de acciones) unido por un solo plan y encaminado a lograr un objetivo específico. Siempre hay una operación revisado evento, es decir Es posible decidir cómo seleccionar ciertos parámetros que caracterizan su organización. Estos parámetros se llaman variables de control.

Cualquier elección específica de tales variables se llama decisión. Las decisiones pueden ser exitosas o no, razonables o irrazonables. Óptimo nombrar aquellas soluciones que, según algunos criterios, sean preferibles a otros.

El propósito de la investigación operativa es una justificación cuantitativa preliminar de las soluciones óptimas, de las cuales puede haber más de una. La elección final de la decisión va más allá del ámbito de la investigación operativa y se realiza mediante la llamada teoría de la decisión.

Cualquier tarea de investigación operativa tiene condiciones iniciales "disciplinarias", es decir. tales datos iniciales que están fijos desde el principio y no pueden ser violados. En conjunto, forman el llamado conjunto de posibles soluciones.

Para comparar diferentes soluciones en términos de efectividad, es necesario tener un criterio cuantitativo llamado indicador de rendimiento(o función objetivo). Este indicador se elige para reflejar la orientación objetivo de la operación.

A menudo, la operación va acompañada de la acción de factores aleatorios. Luego, como indicador de eficiencia, no se toma el valor en sí que se quisiera optimizar, sino su valor medio (o expectativa matemática).

A veces, una operación acompañada de factores aleatorios persigue ese objetivo. A, que puede lograrse por completo o no lograrse en absoluto (como “sí o no”). Luego se elige la probabilidad de lograr este objetivo como indicador de eficiencia. pag(A). (Si pag(A) = 0 o 1, entonces llegamos al problema de la “caja negra” conocido en cibernética.)

Elegir el indicador de desempeño incorrecto es muy peligroso. Las operaciones organizadas según un criterio elegido sin éxito pueden generar costes y pérdidas injustificadas. (Por ejemplo, el "eje" como criterio principal para evaluar la actividad económica de una empresa).

1.3. Planteamiento general del problema de investigación de operaciones.

Los problemas de investigación de operaciones se dividen en dos categorías: a) hacia adelante yb) hacia atrás.

Tareas directas Responda la pregunta: ¿a qué será igual el indicador de eficiencia? z, si en determinadas condiciones y  Y se tomará alguna decisión X  X. Para resolver tal problema, se construye un modelo matemático que permite expresar el indicador de eficiencia a través de condiciones dadas y una solución, a saber:

Dónde
factores especificados (datos iniciales),

variables de control (decisión),

z– indicador de eficiencia (función objetivo),

F– dependencia funcional entre variables.

Esta dependencia se expresa de manera diferente en diferentes modelos. Dependencia entre Y generalmente expresado en términos de restricciones sobre

Si el tipo de dependencia F se conoce, entonces el indicador z se encuentra por sustitución directa Y en esta funcionalidad.

Problemas inversos responder a la pregunta: ¿cómo en estas condiciones? elige una solución
para que el indicador de desempeño z girado al máximo (mínimo). Este problema se llama problema de optimización de soluciones.

Dejemos que se resuelva el problema directo, es decir se especifica el modelo de operación y se especifica el tipo de dependencia F famoso. Entonces el problema inverso (es decir, el problema de optimización) se puede formular de la siguiente manera.

Necesito encontrar tal decisión
en el que el indicador de eficiencia z = optar:

Esta fórmula dice así: z hay un valor optimo
asumido todas las soluciones incluidas en el conjunto de posibles soluciones X.

Método para encontrar el extremo del indicador de eficiencia. z y la solución óptima asociada Siempre debe elegirse en función de las características de la función. F y el tipo de restricciones impuestas a la solución. (Por ejemplo, un problema clásico de programación lineal).

Problema de investigación de operaciones

Introducción………………………………………………………………………………...3

1. Conceptos básicos y definiciones de investigación de operaciones……..……..5

2. Planteamiento general del problema de investigación operativa…………..…………6

Conclusión……………………………………………………………………....13

Literatura………………………………………………………………………………...14

Introducción

La investigación de operaciones - Disciplina científica que se ocupa del desarrollo y la aplicación práctica de métodos para la gestión más eficaz de diversos sistemas organizativos.

La gestión de cualquier sistema se implementa como un proceso que obedece a ciertas leyes. Su conocimiento ayuda a determinar las condiciones necesarias y suficientes para la implementación de este proceso. Para ello, se deben cuantificar y medir todos los parámetros que caracterizan el proceso y las condiciones externas. Por lo tanto, el propósito de la investigación de operaciones es justificación cuantitativa de las decisiones tomadas sobre la organización de la gestión.

Al resolver un problema de gestión específico, el uso de métodos de investigación operativa implica:

Construcción de modelos económicos y matemáticos para problemas de toma de decisiones en situaciones complejas o en condiciones de incertidumbre;

Estudiar las relaciones que posteriormente determinan la toma de decisiones y establecer criterios de actuación que permitan evaluar la ventaja de una determinada conducta.

Ejemplos de tareas de investigación de operaciones que reflejan su especificidad incluyen las siguientes tareas.

Tarea 1. Para garantizar la alta calidad de los productos fabricados, se organiza un sistema de control de muestreo en la planta. Es necesario elegir tales formas de organización (por ejemplo, asignar los tamaños de los lotes de control, indicar la secuencia de las operaciones de control, determinar las reglas de rechazo) para garantizar la calidad requerida a costos mínimos.

Tarea 2. Para vender un determinado lote de productos de temporada, se crea una red de puntos de venta temporales. Es necesario seleccionar los parámetros de la red (el número de puntos, su ubicación, el número de personal) para garantizar la máxima eficiencia económica de la venta.

Tarea 3. En una fecha determinada, es necesario realizar un examen médico masivo de un grupo de la población para identificar determinadas enfermedades. Se han asignado materiales, equipos y personal para el examen. Es necesario desarrollar un plan de exámenes de este tipo: establecer el número de puestos médicos, su ubicación, tipo y número de pruebas para identificar el mayor porcentaje posible de enfermos.

También es necesario señalar problemas sobre el uso de recursos, sobre mezclas, sobre el uso de capacidades, sobre materiales de corte, un problema de transporte, etc., en los que es necesario encontrar una solución cuando algunos criterio de desempeño(por ejemplo, ganancias, ingresos, costos de recursos, etc.) toma un valor máximo o mínimo.

Las tareas asignadas se relacionan con diferentes áreas de práctica, pero tienen características comunes: en cada caso estamos hablando de algunos evento controlado (operación), persiguiendo un cierto objetivo. En la tarea 1, se trata de organizar el control de muestreo para garantizar la calidad de los productos; en la tarea 2: organizar puntos de venta temporales con el fin de realizar ventas de temporada; en la tarea 3: un examen médico masivo para determinar el porcentaje de casos.

Cada tarea contiene algunos condiciones celebración de este evento, en cuyo marco es necesario tomar solución - tal que el evento traiga algún beneficio. Las condiciones para realizar la operación en cada tarea son los medios a nuestra disposición, tiempo, equipo, tecnología y la solución en la tarea 1 es elegir la forma de control: el tamaño de los lotes de control, las reglas de rechazo; en la tarea 2: al elegir el número de puntos de colocación y el número de personal; en la tarea 3: elegir el número de puestos médicos, el tipo y el número de pruebas.

1. Conceptos básicos y definiciones de investigación de operaciones.

Operación- cualquier evento controlado destinado a lograr un objetivo. El resultado de la operación depende del método de implementación y organización; de lo contrario, de la elección de ciertos parámetros.

Cualquier elección específica de parámetros se llama decisión.

Óptimo considerar aquellas soluciones que, por una razón u otra, son preferibles a otras. Es por eso tarea principal La investigación de operaciones es cuantitativa preliminar. Justificación de soluciones óptimas.

Nota 1. Se debe prestar atención al planteamiento del problema: el tomando decisiones va más allá del alcance de la investigación operativa y es responsabilidad de la persona o grupo de personas responsables que podrán tener en cuenta consideraciones distintas a las que estén matemáticamente justificadas.

Nota 2. Si en algunos problemas de investigación operativa la solución óptima es aquella en la que se adopta algún criterio de eficiencia.

valor máximo o mínimo, entonces en otras tareas esto no es en absoluto necesario. Así, en la tarea 2, se puede considerar el número óptimo de puntos de venta y personal en ellos de modo que el tiempo promedio de atención al cliente no exceda, por ejemplo, 5 minutos, y la longitud promedio de la cola en cualquier momento no sea mayor. de 3 personas.

Para aplicar métodos de investigación cuantitativa, es necesario construir modelo matemático de la operación. Al construir un modelo, la operación, por regla general, se simplifica, se esquematiza y el esquema de operación se describe utilizando uno u otro aparato matemático.

Modelo operaciones - Esta es una descripción bastante precisa de la operación utilizando aparatos matemáticos (diversos tipos de funciones, ecuaciones, sistemas de ecuaciones y desigualdades, etc.). Elaborar un modelo de operación requiere comprender la esencia del fenómeno que se describe y el conocimiento del aparato matemático.

Eficiencia operativa - el grado de adaptabilidad a la tarea se expresa cuantitativamente en forma de criterio de eficiencia: la función objetivo. Por ejemplo, en el problema del uso de recursos, el criterio de eficiencia es el beneficio de la venta de productos manufacturados, que debe maximizarse; en el problema del transporte, los costos totales de transporte de mercancías desde los proveedores hasta los consumidores, que deben minimizarse. . La elección del criterio de eficacia determina el valor práctico del estudio. (Un criterio elegido incorrectamente puede ser perjudicial, ya que las operaciones organizadas en función de dicho criterio de eficiencia a veces generan costos injustificados).

2. Planteamiento general del problema de investigación operativa.

Es importante comprender la metodología para la construcción de modelos de problemas de investigación operativa. Todos los factores incluidos en la descripción de la operación se pueden dividir en dos grupos:

factores constantes(condiciones de funcionamiento), sobre las que no podemos influir. Denotémoslos por α1, α2, ... ;

factores dependientes(elementos de la solución) X 1, x2,...; que, dentro de ciertos límites, podemos elegir a nuestro criterio.

Por ejemplo, en el problema del uso de recursos, los factores constantes deben incluir las reservas de recursos de cada tipo, la matriz de producción, cuyos elementos determinan el consumo de materias primas de cada tipo por unidad de producción de cada tipo. Elementos de la solución: un plan de producción para cada tipo de producto.

Un criterio de desempeño expresado por alguna función llamada objetivo, depende de los factores de ambos grupos, por lo que la función objetivo z se puede escribir en la forma

z= F (x1, x2, ..., α1, α2, ...)

Todos los modelos de investigación operativa se pueden clasificar según la naturaleza y propiedades de la operación, la naturaleza de los problemas que se resuelven y las características de los métodos matemáticos utilizados.

Cabe señalar, en primer lugar, la gran Clase de modelos de optimización. Estos problemas surgen cuando se intenta optimizar la planificación y gestión de sistemas complejos, principalmente sistemas económicos. El problema de optimización se puede formular en forma general: encontrar variables x1, x2, ..., x norte , satisfacer el sistema de desigualdades (ecuaciones)

gramo i (x1, x2, x3,..., X norte )<= b i , yo = 1, 2,..., norte (0.1)

Y convertir la función objetivo a un máximo (o mínimo), es decir,

z= F (x1, x2, ..., X norte ) - metro ah (m en ) (0.2)

(Las condiciones para que las variables no sean negativas, si las hay, se incluyen en las restricciones (0.1))

Consideremos otro problema típico de la investigación de operaciones: el clásico problema del consumo, de gran importancia en el análisis económico.

Dejalo ser PAG tipos de bienes y servicios, cuyas cantidades (en unidades naturales) x1, x2, ..., X norte,a precios acordes pag 1, pag 2, ..., pag norte para una unidad. El costo total de estos bienes y servicios es ∑ pag i X i .

Nivel de consumo z puede expresarse mediante alguna función z= F (x1, x2, ..., X norte ) ,llamado función de utilidad. Es necesario encontrar tal conjunto de bienes y servicios. x1, x2, ..., X norte dado cantidad de ingresos yo, a garantizar el máximo nivel de consumo, aquellos.

z= F (x1, x2, ..., X norte ) - metro Oh (0.3)

dado que

∑ pag i X i <= I (0.4)

X i >= 0 ( i = 1, 2,..., norte ) (0.5)

Soluciones a este problema que dependen de los precios pag 1, pag 2, ..., pag norte y la cantidad de ingresos I, son llamados funciones de demanda.

Es obvio que el problema de consumo considerado (0.3)-(0.5), así como muchos otros, es un caso especial del problema general (0.1)-(0.2) formulado anteriormente para determinar el extremo de la función. PAG variables bajo ciertas restricciones, es decir tarea para condicional extremo.

En los casos en que las funciones F Y gramo i, en el problema (0.1)-(0.2) son al menos dos veces diferenciables, podemos usar clásico métodos de optimización. Sin embargo, el uso de estos métodos en la investigación operativa es muy limitado, ya que la tarea de determinar el extremo condicional de una función de i variables es técnicamente muy difícil: el método permite determinar el extremo local y, debido a la multidimensionalidad de la función, determinar su valor máximo (o mínimo) (extremo global) puede resultar muy laborioso, especialmente porque este extremo es posible en el límite de la región de solución. Los métodos clásicos no funcionan en absoluto si el conjunto de valores de argumentos válidos es discreto o la función z se da en una tabla. En estos casos, para resolver el problema (0.1)-(0.2) se utilizan los métodos programación matemática.

Si el criterio de desempeño z= F (x1, x2, ..., X norte ) (0.2) representa una función lineal, y las funciones gramo i (x1, x2, x3,..., X norte ) en el sistema de restricciones (0.1) también son lineales, entonces tal problema es un problema programación lineal. Si, según el contenido, sus soluciones deben ser números enteros, entonces este problema programación lineal entera. Si el criterio de eficiencia y (o) el sistema de restricciones están especificados por funciones no lineales, entonces tenemos el problema programación no lineal. En particular, si las funciones indicadas tienen propiedades de convexidad, entonces el problema resultante es un problema programación convexa.

Si en un problema de programación matemática hay una variable de tiempo y el criterio de eficiencia (0,2) no se expresa explícitamente en función de las variables, sino indirectamente, a través de ecuaciones que describen el flujo de operaciones en el tiempo, entonces ese problema es un problema. programación dinámica.

Si el criterio de eficiencia (0.2) y el sistema de restricciones (0.1) se especifican mediante funciones de la forma Con*( X 1^α 1 )*( X 2^α 2 )...( X norte ^α norte ) , entonces tenemos el problema programación geométrica. Si las funciones F y/o gramo i en las expresiones (0.2) y (0.1) dependen de los parámetros, entonces obtenemos el problema programación paramétrica, Si estas funciones son de naturaleza aleatoria, la tarea programación estocástica. Si es imposible encontrar algorítmicamente el óptimo exacto debido a una cantidad excesivamente grande de opciones de solución, entonces recurra a métodos heurístico programación, permitiéndole reducir significativamente la cantidad de opciones que está considerando y encontrar, si no óptima, sí una solución bastante buena que sea satisfactoria desde un punto de vista práctico.

De los métodos enumerados de programación matemática, el más común y desarrollado es la programación lineal. Cubre una amplia gama de tareas de investigación de operaciones.

Tareas de planificación y gestión de redes. considerar la relación entre las fechas de finalización de un gran complejo de operaciones (obras) y las horas de inicio de todas las operaciones del complejo. Estas tareas consisten en encontrar la duración mínima de un conjunto de operaciones, la relación óptima de los valores de costos y el momento de su implementación.

Problemas de cola se dedican al estudio y análisis de sistemas de servicio con colas de aplicaciones o requerimientos y consisten en determinar los indicadores de desempeño de los sistemas, sus características óptimas, por ejemplo, determinar el número de canales de servicio, tiempo de servicio, etc.

Tareas de gestión de inventario. Consisten en encontrar los valores óptimos de nivel de inventario (punto de pedido) y tamaño del pedido. La peculiaridad de tales tareas es que con un aumento en el nivel de inventarios, por un lado, aumentan los costos de almacenamiento, pero por otro lado, disminuyen las pérdidas por una posible escasez del producto almacenado.

Problemas de asignación de recursos surgen durante un determinado conjunto de operaciones (obras) que deben realizarse con recursos disponibles limitados, y es necesario encontrar la distribución óptima de los recursos entre operaciones o la composición de las operaciones.

Tareas de reparación y sustitución de equipos. son relevantes debido al desgaste de los equipos y la necesidad de reemplazarlos con el tiempo. Las tareas se reducen a determinar el momento óptimo, el número de reparaciones e inspecciones preventivas, así como cuándo reemplazar los equipos por equipos modernizados.

Programar (programar) tareas consisten en determinar la secuencia óptima de operaciones (por ejemplo, procesamiento de piezas) en varios tipos de equipos.

Tareas de planificación y colocación. consisten en determinar el número y la ubicación óptimos de nuevos objetos, teniendo en cuenta su interacción con los objetos existentes y entre sí.

Problemas de selección de ruta o red Los problemas que se encuentran con mayor frecuencia en el estudio de diversos problemas en los sistemas de transporte y comunicaciones y consisten en determinar las rutas más económicas.

Entre los modelos de investigación operativa destacan los modelos de toma de decisiones óptimas en situaciones de conflicto, estudiados por teoría de juego. Las situaciones de conflicto en las que chocan los intereses de dos (o más) partes, que persiguen objetivos diferentes, incluyen una serie de situaciones en el campo de la economía, el derecho, los asuntos militares, etc. En los problemas de teoría de juegos, es necesario desarrollar recomendaciones para la Comportamiento razonable de los participantes en el conflicto, para determinar sus estrategias óptimas.

En la práctica, en la mayoría de los casos, el éxito de una operación se evalúa no por uno, sino por varios criterios a la vez, uno de los cuales debe maximizarse y el resto, minimizarse. El aparato matemático también puede ser útil en casos problemas de investigación de operaciones multicriterio, al menos ayudar a descartar soluciones obviamente fallidas.

Para seleccionar una función objetivo a partir de una variedad de criterios, incluidos aquellos que se contradicen entre sí (por ejemplo, ganancias y gastos), es necesario establecer una prioridad criterios. denotemos F 1 (x), f 2 (X), ..., F norte (X)(Aquí X - argumento condicional). Que se organicen en orden de prioridad descendente. Dependiendo de determinadas condiciones, existen básicamente dos opciones:

El criterio se elige como función objetivo. F 1 (X), tener la máxima prioridad;

Se está considerando una combinación

F ( X ) = ω 1 * F 1 ( X ) + ω 2 * F 2 ( X ) + …+ ω norte * F norte ( X ) , (0.6)

Dónde ω 1 , ω 2 , … ω norte- algunos coeficientes (pesos).

Magnitud F (X) Como función objetivo se elige , que tiene en cuenta todos los criterios hasta cierto punto.

En condiciones de certeza ω i- números, F i (X)- funciones. En condiciones de incertidumbre F i (X) puede resultar ser aleatorio y en su lugar F i (X) la expectativa matemática de la suma (0,6) debe considerarse como la función objetivo.

Un intento de reducir un problema multicriterio a un problema con un criterio de eficiencia (función objetivo) en la mayoría de los casos no da resultados satisfactorios. Otro enfoque consiste en descartar ("seleccionar") del conjunto de soluciones admisibles las soluciones claramente infructuosas que son inferiores a otras en términos de todos los criterios. Como resultado de este procedimiento, el llamado eficaz(o " Pareto") soluciones, cuyo conjunto suele ser significativamente más pequeño que el original. Y la elección final de una solución de “compromiso” (no óptima según todos los criterios, que, por regla general, no existe, pero aceptable según estos criterios) queda en manos de la persona que toma las decisiones.

Conclusión

Los científicos rusos L.V. hicieron una gran contribución a la creación de un aparato matemático moderno y al desarrollo de muchas áreas de la investigación operativa. Kantorovich, N.P. Buslenko, E.S. Ventzel, N.N. Vorobyov, N.N. Moiseev, D.B. Yudin y muchos otros. Particularmente digno de mención es el papel del académico L.V. Kantorovich, quien en 1939, habiendo comenzado a planificar el funcionamiento de las unidades de la fábrica de madera contrachapada, resolvió varios problemas: sobre la mejor carga de equipos, sobre el corte de materiales con pérdidas mínimas, sobre la distribución de la carga entre varios tipos de transporte, etc. Kantorovich formuló una nueva clase de problemas condicionalmente extremos y propuso un método universal para resolverlos, sentando las bases para una nueva dirección en las matemáticas aplicadas: la programación lineal.

Los científicos extranjeros R. Akof, R. Bellman, G. Danzig, G. Kuhn, J. Neumann, T. Saaty, R. Churchman, A. Kofman y otros hicieron importantes contribuciones a la formación y el desarrollo de la investigación operativa.

Los métodos de investigación operativa, como cualquier método matemático, siempre simplifican y tonifican el problema en un grado u otro, reflejando a veces procesos no lineales con modelos lineales, sistemas estocásticos con modelos deterministas, procesos dinámicos con modelos estáticos, etc. La vida es más rica que cualquier plan. Por lo tanto, no se debe exagerar la importancia de los métodos cuantitativos en la investigación de operaciones ni minimizarla citando ejemplos de soluciones fallidas. Es apropiado citar a este respecto la definición humorísticamente paradójica de investigación operativa hecha por uno de sus creadores, T. Saaty, como “el arte de dar malas respuestas a aquellas preguntas prácticas que pueden responderse aún peor con otros métodos”.

Literatura

1. Kremer N. Sh., Putko B. A., Trishin I. M., Fridman M. N. Investigación de operaciones en economía: Libro de texto para universidades - M.: UNITI, 2002.

2. Ventzel E.S. La investigación de operaciones. Objetivos, principios, metodología - M.: Nauka, 1980.

3. Gorelik V.A., Ushakov I.A. La investigación de operaciones. - M.: Ingeniería Mecánica, 1986.

EN. Slinkin

Libro de texto para estudiantes de universidades pedagógicas.

con especialización en informática

Shadrinsk, 2003

Slinkina I.N.

La investigación de operaciones. Manual educativo y metodológico. – Shadrinsk: editorial del Instituto Pedagógico Estatal de Shadrinsk, 2002. - 106 p.

Slinkina I.N. – Candidato de Ciencias Pedagógicas

El libro de texto presenta la parte teórica del curso de Investigación de Operaciones. Está destinado a estudiantes de tiempo completo y parcial de facultades que cursan la especialidad "Informática".

© Instituto Pedagógico Estatal de Shadrinsk

© Slinkina I.N., 2002

Preguntas para unidades del curso “Investigación Operativa” 5

1.1. Asunto y tareas de la investigación operativa 7.

1.2. Conceptos y principios básicos de la investigación de operaciones 8.

1.3. Modelos matemáticos de operaciones 10

1.4. Concepto de programación lineal 12

1.5. Ejemplos de problemas de programación lineal económica. Mejor uso de los recursos Problema 13

1.6. Ejemplos de problemas de programación lineal económica. Problema de elegir tecnologías óptimas 15.

1.7. Ejemplos de problemas de programación lineal económica. Problema de mezcla 16

1.8. Ejemplos de problemas de programación lineal económica. Problema de transporte 17

1.9. Tipos básicos de grabación de problemas de programación lineal 19.

1.10. 21 métodos de conversión

1.11. Transición a la forma canónica 22

1.12. Transición a una forma simétrica de grabación 25

2.1. Interpretación geométrica del problema de programación lineal 28.

2.2. Resolver problemas de programación lineal por método gráfico 29

2.3. Propiedades de las soluciones a problemas de programación lineal 34

2.4. Idea general del método simplex 35

2.5. Construcción del plan de referencia inicial al resolver problemas de programación lineal utilizando el método simplex 36

2.6. Signo de optimización del plan de referencia. Mesas simplex 40

2.7. Transición al plan de referencia del peor de los casos. 44

2.8. Transformaciones simplex 46

2.9. Óptimo alternativo (signo de infinito del conjunto de planes de referencia) 51

2.10. Signo de ilimitación de la función objetivo 52

2.11. El concepto de degeneración. Monotonicidad y finitud del método simplex. Bucle 53

2.12. El concepto de dualidad para problemas de programación lineal simétrica 54

3.1. Problemas duales asimétricos 57

3.2. Modelos abiertos y cerrados del problema del transporte 61.

3.3. Construcción del plano de referencia inicial. Regla 63 de la esquina noroeste

3.4. Construcción del plano de referencia inicial. Regla del elemento mínimo 64

3.5. Construcción del plano de referencia inicial. Método Vogel 64

3.6. Método potencial 65

3.7. Resolver problemas de transporte con restricciones de capacidad 69

3.8. Ejemplos de problemas de programación discreta. Problema de transporte de contenedores. Problema de tarea 71

3.9. La esencia de los métodos de optimización discretos 72.

3.10. Problema de programación convexa 74

3.11. Método del multiplicador de Lagrange 75

3.12. Métodos de gradiente 77

4.1. Métodos de penalización y funciones de barrera 78.

4.2. Programación dinámica. Conceptos básicos. La esencia de los métodos de solución 79.

4.3. Programación estocástica. Conceptos básicos 81

4.4. Juegos de matrices de suma cero 83

4.5. Estrategias puras y mixtas y sus propiedades 85

4.6. Propiedades de las estrategias puras y mixtas 88

4.7. Reducir un juego de matrices a ZLP 92

4.8. Problemas de la teoría de colas. Clasificación de sistemas de colas 94.

4.9. Flujos de eventos 96

4.10. Esquema de muerte y reproducción 97.

4.11. Fórmula 99 de Little

4.12. Sistemas de colas más simples 101

Preguntas para bloques del curso “Investigación Operativa”

Bloque 1

1. Materia y objetivos de la investigación operativa.

2. Conceptos y principios básicos de la investigación operativa.

3. Modelos matemáticos de operaciones.

4. El concepto de programación lineal.

5. Ejemplos de problemas de programación lineal económica. Tarea

6. Ejemplos de problemas de programación lineal económica. El problema de elegir tecnologías óptimas.

7. Ejemplos de problemas de programación lineal económica. Problema sobre las mezclas.

8. Ejemplos de problemas de programación lineal económica. Problema de transporte.

9. Tipos básicos de redacción de problemas de programación lineal.

10. Métodos de conversión.

11. Transición a la forma canónica.

12. Transición a una forma de grabación simétrica.

Bloque 2

1. Interpretación geométrica del problema de programación lineal.

2. Resolución de problemas de programación lineal mediante el método gráfico.

3. Propiedades de las soluciones del problema de programación lineal.

4. Idea general del método simplex.

5. Construcción del plan de referencia inicial a la hora de resolver problemas de programación lineal mediante el método simplex.

6. Signo de optimización del plan de referencia. Tablas simplex.

7. Transición al plan de referencia no peor.

8. Transformaciones simplex.

9. Óptimo alternativo (un signo del infinito del conjunto de planes de referencia).

10. Signo de ilimitación de la función objetivo.

11. El concepto de degeneración. Monotonicidad y finitud del método simplex. Bucle.

12. El concepto de dualidad para problemas de programación lineal simétrica.

Bloque 3

1. Problemas duales asimétricos.

2. Modelos abiertos y cerrados del problema del transporte.

3. Construcción del plano de referencia inicial. Regla de la "esquina noroeste".

4. Construcción del plano de referencia inicial. Regla del elemento mínimo.

5. Construcción del plano de referencia inicial. Método Vogel.

6. Método de potenciales.

7. Resolver problemas de transporte con limitaciones de capacidad.

8. Ejemplos de problemas de programación discreta. Problema de transporte de contenedores. Problema de asignación.

9. La esencia de los métodos de optimización discretos.

10. Problema de programación convexa.

11. Método del multiplicador de Lagrange.

12. Métodos de gradiente.

Bloque 4

1. Método de penalización y funciones de barrera.

2. Programación dinámica. Conceptos básicos. La esencia de los métodos de solución.

3. Programación estocástica. Conceptos básicos.

4. Juegos matriciales de suma cero.

5. Estrategias puras y mixtas.

6. Propiedades de las estrategias puras y mixtas.

7. Reducir un juego matricial a un PLP

8. Problemas de la teoría de colas. Clasificación de sistemas de colas.

9. Secuencias de eventos.

10. Esquema de muerte y reproducción.

11. La fórmula de Little.

12. Los sistemas de colas más sencillos.

Bloque 1.

Tema y tareas de la investigación operativa.

El estado actual de la ciencia y la tecnología, en particular el desarrollo de herramientas de cálculo informático y la fundamentación matemática de teorías, ha permitido simplificar significativamente la solución de muchos problemas planteados a diversas ramas de la ciencia. Muchos de los problemas se reducen a resolver la cuestión de la optimización de la producción y el control óptimo del proceso.

Las necesidades de la práctica han dado lugar a métodos científicos especiales, que se combinan convenientemente bajo el nombre de "investigación operativa".

Definición: Por investigación operativa entendemos la aplicación de métodos matemáticos y cuantitativos para justificar decisiones en todas las áreas de la actividad humana con propósito.

Que se tomen algunas medidas para lograr un objetivo determinado. La persona (o grupo de personas) que organiza el evento siempre tiene cierta libertad de elección: puede organizarse de una forma u otra. Una decisión es una elección entre una serie de posibilidades disponibles para el organizador.

La necesidad de tomar decisiones y probar la hipótesis de solución propuesta se confirma matemáticamente con los siguientes ejemplos:

Tarea 1. Sobre el mejor uso de los recursos.

La empresa produce varios tipos de productos. Para fabricarlos se utilizan algunos recursos (incluidos los humanos, la energía, etc.). Es necesario calcular cómo planificar el trabajo de la empresa para que los costos de recursos sean mínimos y se maximicen las ganancias.

Tarea 2. Sobre mezclas.

Es necesario preparar una mezcla que tenga determinadas propiedades. Para hacer esto, puede utilizar algunos "productos" (para calcular dietas - productos alimenticios, para mezclas de piensos - productos alimenticios para animales, para mezclas técnicas - aleaciones, líquidos para fines técnicos). la tarea es seleccionar la cantidad óptima de productos (por precio) para obtener la cantidad óptima de la mezcla.

Tarea 3. Problema de transporte.

Existe una red de empresas que producen productos similares de la misma calidad y una red de consumidores de estos productos. Los consumidores y proveedores están conectados por vías de comunicación (carreteras, líneas ferroviarias, líneas aéreas). Se han determinado las tarifas de transporte. Es necesario calcular el plan óptimo para el transporte de productos para que los costos de transporte sean mínimos, se satisfagan las necesidades de todos los consumidores y todos los bienes se retiren de los proveedores.

En cada uno de los ejemplos dados, estamos hablando de algún tipo de evento que persigue un objetivo específico. Se especifican algunas condiciones que caracterizan la situación (en particular, los medios de los que se puede disponer). En estas condiciones, es necesario tomar una decisión para que el evento planificado sea en cierto sentido más rentable.

De acuerdo con estas características generales, se desarrollan métodos generales para resolver problemas similares, que en conjunto constituyen el esquema metodológico y el aparato de la investigación operativa.

Actualmente, se están generalizando los sistemas de control automatizado (ACS) basados ​​​​en el uso de tecnología informática. La creación de un sistema de control automatizado es imposible sin un examen preliminar del proceso controlado utilizando métodos de modelado matemático. Con la creciente escala y complejidad de los acontecimientos, los métodos matemáticos para fundamentar decisiones se vuelven cada vez más importantes.

Conceptos y principios básicos de la investigación de operaciones.

Definición: Una operación es cualquier evento (sistema de acciones) unido por un solo plan y encaminado a lograr algún objetivo.

Una operación es siempre un evento controlado, es decir. Depende de los cálculos cómo elegir los parámetros que caracterizan su organización. Se entiende aquí por “organización” en el sentido amplio de la palabra, incluyendo el conjunto de medios técnicos utilizados en la operación.

Definición: Cualquier elección específica que dependa de parámetros decisivos se denomina decisión.

Definición: Las soluciones óptimas son aquellas que, por una razón u otra, son preferibles a otras.

Propósito de la investigación de operaciones– justificación cuantitativa preliminar de las soluciones óptimas.

A veces, como resultado del estudio, es posible indicar una solución única y estrictamente definida, mucho más a menudo es posible identificar un área de soluciones óptimas casi equivalentes dentro de las cuales se puede hacer la elección final.

La toma de decisiones en sí va más allá del ámbito de la investigación operativa y cae dentro de la competencia de la persona responsable, más a menudo: un grupo de personas a las que se les otorga el derecho de tomar la decisión final y a quienes se les atribuye la responsabilidad de esta elección.

Definición: Los parámetros cuya combinación forma una solución se denominan elementos de solución.

Los elementos de la solución pueden incluir varios números, vectores, funciones, características físicas, etc. Por simplicidad, denotaremos todo el conjunto de elementos de la solución por x.

Además de los elementos de solución en cualquier problema de investigación operativa, también existen condiciones dadas que están fijadas en la condición del problema y no pueden violarse. En particular, tales condiciones incluyen medios (materiales, técnicos, humanos) de los que se puede disponer y otras restricciones impuestas a la decisión. En conjunto, forman el llamado “conjunto de posibles soluciones”. Designemos este conjunto X, y el hecho de que la solución x pertenece a este conjunto se escribirá: xОХ.

Para comparar diferentes soluciones en términos de eficiencia, es necesario tener algún tipo de criterio cuantitativo, el llamado indicador de eficiencia (función objetivo). Este indicador se selecciona de modo que refleje la orientación objetivo de la operación. Se considerará mejor solución aquella que contribuya en la máxima medida a la consecución del objetivo. Para elegir un indicador de desempeño Z, primero debe determinar a qué debería conducir la solución al problema. Al elegir una solución, se da preferencia a aquella que lleva el indicador de eficiencia Z al máximo o al mínimo. Por ejemplo, me gustaría maximizar los ingresos de una operación; si el indicador de eficiencia son los costes, es recomendable reducirlos al mínimo.

Muy a menudo, el funcionamiento va acompañado de factores aleatorios: “caprichos” de la naturaleza, fluctuaciones en la oferta y la demanda, fallos de los dispositivos técnicos, etc. En tales casos, normalmente no es el valor en sí lo que se desea maximizar (minimizar), sino el valor medio (expectativa matemática) que se toma como indicador de eficiencia.

La tarea de elegir un indicador de desempeño se resuelve para cada problema individualmente.

Tarea 1. Sobre el mejor uso de los recursos.

El objetivo de la operación es producir el máximo número de bienes. Indicador de eficiencia Z: beneficio de la venta de bienes con costos mínimos de recursos (max Z).

Tarea 2. Sobre mezclas.

Un indicador natural de eficiencia, sugerido por la formulación del problema, es el precio de los productos necesarios para la mezcla, sujeto a la necesidad de mantener las propiedades especificadas de la mezcla (min Z).

Tarea 3. Problema de transporte.

El objetivo de la operación es asegurar el suministro de bienes a los consumidores con costos mínimos de transporte. El indicador de eficiencia Z es el costo total de transporte de mercancías por unidad de tiempo (min Z).