La versión más aceptable de la decisión que se toma a nivel gerencial con respecto a cualquier tema se considera óptima y el proceso de búsqueda en sí mismo se considera optimización.

La interdependencia y complejidad de los aspectos organizativos, socioeconómicos, técnicos y de otro tipo de la gestión de la producción se reduce actualmente a la toma de una decisión de gestión, que afecta a un gran número de diferentes tipos de factores estrechamente entrelazados entre sí, lo que hace imposible analizarlos cada uno. por separado utilizando métodos analíticos tradicionales.

La mayoría de los factores son decisivos en el proceso de toma de decisiones y (en esencia) no se prestan a ninguna caracterización cuantitativa. También están los que prácticamente no han cambiado. En este sentido, se hizo necesario desarrollar métodos especiales que puedan asegurar la selección de decisiones de gestión importantes en el marco de problemas organizativos, económicos y técnicos complejos (evaluaciones de expertos, investigación de operaciones y métodos de optimización, etc.).

Los métodos destinados a investigar las operaciones se utilizan para encontrar soluciones óptimas en áreas de gestión como la organización de los procesos de producción y transporte, la planificación de la producción a gran escala, el suministro de materiales y técnicos.

Los métodos de optimización de decisiones consisten en el estudio mediante la comparación de las estimaciones numéricas de una serie de factores, cuyo análisis no puede realizarse por métodos tradicionales. La solución óptima es la mejor entre las opciones posibles para el sistema económico, y la solución más aceptable para los elementos individuales del sistema es subóptima.

La esencia de los métodos de investigación de operaciones

Como se mencionó anteriormente, forman métodos para optimizar las decisiones de gestión. Se basan en modelos matemáticos (deterministas) probabilísticos que representan el proceso, tipo de actividad o sistema investigado. Los modelos de este tipo proporcionan una caracterización cuantitativa del problema correspondiente. Sirven como base para tomar una importante decisión de gestión en el proceso de búsqueda de la opción óptima aceptable.

La lista de problemas que juegan un papel importante para los gerentes de producción directos y que se resuelven en el curso del uso de los métodos en consideración:

  • el grado de validez de las opciones seleccionadas para las decisiones;
  • cuánto mejor que los alternativos;
  • el grado en que se tienen en cuenta los determinantes;
  • cuál es el criterio para la optimalidad de las soluciones seleccionadas.

Estos métodos de optimización de decisiones (gerenciales) tienen como objetivo encontrar soluciones óptimas para tantas firmas, empresas o sus divisiones como sea posible. Se basan en los logros existentes de las disciplinas estadísticas, matemáticas y económicas (teoría de juegos, colas, gráficos, programación óptima, estadística matemática).

Métodos de evaluación expertos

Estos métodos de optimización de decisiones gerenciales se utilizan cuando la tarea no está parcial o totalmente sujeta a formalización, y además su solución no puede encontrarse por medio de métodos matemáticos.

La pericia es un estudio de cuestiones especiales complejas en la etapa de desarrollo de una determinada decisión de gestión por personas adecuadas que tienen una reserva especial de conocimiento y una experiencia impresionante para obtener conclusiones, recomendaciones, opiniones, evaluaciones. En el proceso de investigación de expertos, los últimos logros de la ciencia y la tecnología se aplican dentro de la especialización del experto.

Los métodos considerados de optimización de una serie de decisiones de gestión (evaluaciones de expertos) son eficaces para resolver las siguientes tareas de gestión en el campo de la producción:

  1. Estudio de procesos complejos, fenómenos, situaciones, sistemas que se caracterizan por características cualitativas no formalizadas.
  2. Clasificar y determinar, según un criterio dado, los factores esenciales que son determinantes para el funcionamiento y desarrollo del sistema productivo.
  3. Los métodos de optimización considerados son especialmente efectivos para predecir las tendencias de desarrollo del sistema de producción, así como su interacción con el entorno externo.
  4. Aumentar la confiabilidad de la evaluación de expertos de las funciones predominantemente objetivo, que son cuantitativas y cualitativas, promediando las opiniones de especialistas calificados.

Y estos son solo algunos de los métodos para optimizar una serie de decisiones de gestión (evaluación de expertos).

Clasificación de los métodos considerados

Los métodos para resolver problemas de optimización, basados ​​en el número de parámetros, se pueden dividir en:

  • Métodos de optimización unidimensionales.
  • Técnicas de optimización multidimensional.

También se denominan "métodos de optimización numérica". Para ser precisos, estos son los algoritmos para encontrarlo.

En el marco de la aplicación de derivados, los métodos son:

  • métodos de optimización directa (orden cero);
  • métodos de gradiente (primer orden);
  • Métodos de segundo orden, etc.

La mayoría de los métodos de optimización multidimensional están cerca del problema del segundo grupo de métodos (optimización unidimensional).

Métodos de optimización unidimensionales

Cualquier método de optimización numérica se basa en un cálculo aproximado o exacto de características tales como los valores de la función objetivo y las funciones que definen el conjunto admisible y sus derivadas. Entonces, para cada problema individual, la cuestión de la elección de las características para el cálculo puede resolverse dependiendo de las propiedades existentes de la función en consideración, las capacidades disponibles y las limitaciones en el almacenamiento y procesamiento de la información.

Existen los siguientes métodos para resolver problemas de optimización (unidimensionales):

  • Método de Fibonacci;
  • dicotomías;
  • proporción áurea;
  • doblando el paso.

Método de Fibonacci

Primero, debe establecer las coordenadas m. X en el intervalo como un número igual a la relación entre la diferencia (x - a) y la diferencia (b - a). Por lo tanto, a tiene la coordenada 0 con respecto al intervalo, y b - 1, el punto medio - ½.

Si asumimos que F0 y F1 son iguales entre sí y tomamos el valor 1, F2 será igual a 2, F3 - 3, ..., entonces Fn = Fn-1 + Fn-2. Entonces, Fn son números de Fibonacci, y la búsqueda de Fibonacci es la estrategia óptima de la llamada búsqueda máxima secuencial debido al hecho de que está muy relacionada con ellos.

En el marco de la estrategia óptima, se acostumbra elegir xn - 1 = Fn-2: Fn, xn = Fn-1: Fn. Para cualquiera de los dos intervalos (o), cada uno de los cuales puede actuar como un intervalo de incertidumbre reducido, el punto (heredado) relativo al nuevo intervalo tendrá coordenadas o. Además, como xn - 2, se toma un punto que tiene una de las coordenadas presentadas en relación con el nuevo intervalo. Si usa F (xn - 2), el valor de la función, que se hereda del intervalo anterior, es posible reducir el intervalo de incertidumbre y heredar un valor de la función.

En el paso final, resultará ir a un intervalo de incertidumbre como, mientras que el punto medio se hereda del paso anterior. Como x1, se establece un punto que tiene una coordenada relativa ½ + ε, y el intervalo de incertidumbre final será o [½, 1] con respecto a.

En el primer paso, la longitud de este intervalo se redujo a Fn-1: Fn (de uno). En los pasos finales, el acortamiento de las longitudes de los intervalos correspondientes está representado por los números Fn-2: Fn-1, Fn-3: Fn-2,…, F2: F3, F1: F2 (1 + 2ε). Entonces, la longitud de un intervalo como la versión final tomará el valor (1 + 2ε): Fn.

Si despreciamos ε, entonces asintóticamente 1: Fn será igual a rn, con n → ∞, y r = (√5 - 1): 2, que es aproximadamente igual a 0,6180.

Cabe señalar que, asintóticamente para n significativo, cada paso posterior de la búsqueda de Fibonacci reduce significativamente el intervalo considerado con el coeficiente anterior. Este resultado debe compararse con 0.5 (el coeficiente de reducir el intervalo de incertidumbre dentro del método de bisección para encontrar el cero de la función).

Método de dicotomía

Si imagina alguna función objetivo, primero debe encontrar su extremo en el intervalo (a; b). Para hacer esto, el eje de abscisas se divide en cuatro partes equivalentes, luego es necesario determinar el valor de la función en consideración en 5 puntos. Entonces se selecciona el mínimo entre ellos. El extremo de la función debe estar dentro del intervalo (a "; b"), que es adyacente al punto mínimo. Los límites de búsqueda se reducen 2 veces. Y si el mínimo se encuentra en el punto aob, entonces se reduce cuatro veces. El nuevo intervalo también se divide en cuatro segmentos iguales. Debido al hecho de que los valores de esta función en tres puntos se determinaron en la etapa anterior, se requiere calcular la función objetivo en dos puntos.

Método de la sección dorada

Para valores significativos de n, las coordenadas de puntos como xn y xn-1 están cerca de 1 - r, igual a 0,3820 y r ≈ 0,6180. El impulso de estos valores está muy cerca de la estrategia óptima deseada.

Si asumimos que F (0.3820)> F (0.6180), entonces se describe un intervalo. Sin embargo, dado que 0,6180 * 0,6180 ≈ 0,3820 ≈ xn-1, en este punto F ya se conoce. En consecuencia, en cada etapa, a partir de la 2, solo se necesita un cálculo de la función objetivo, y cada paso reduce la longitud del intervalo considerado en un factor de 0,6180.

A diferencia de la búsqueda de Fibonacci, este método no requiere fijar el número n antes de comenzar la búsqueda.

La "sección áurea" de una sección (a; b) es una sección en la que la razón de su longitud r a la parte más grande (a; c) es idéntica a la razón de la parte más grande r a la más pequeña, es decir , (a; c) a (c; b). Es fácil adivinar que r está determinado por la fórmula anterior. En consecuencia, para n significativo, el método de Fibonacci pasa al dado.

Método de duplicación de pasos

La esencia es la búsqueda de la dirección de disminución de la función objetivo, movimiento en esta dirección en el caso de una búsqueda exitosa con un paso que aumenta gradualmente.

Primero, determinamos la coordenada inicial M0 de la función F (M), el valor de paso mínimo h0 y la dirección de búsqueda. Luego definimos la función en el punto M0. A continuación, damos un paso y encontramos el valor de esta función en este punto.

Si la función es menor que el valor que estaba en el paso anterior, debes dar el siguiente paso en la misma dirección, habiéndolo aumentado previamente 2 veces. Si su valor es mayor que el anterior, deberá cambiar la dirección de la búsqueda y luego comenzar a moverse en la dirección elegida con un paso h0. El algoritmo presentado se puede modificar.

Técnicas de optimización multivariante

El método de orden cero mencionado anteriormente no tiene en cuenta las derivadas de la función minimizada, por lo tanto, su uso puede ser efectivo en caso de dificultades con el cálculo de las derivadas.

El grupo de métodos de primer orden también se llama gradiente, porque para establecer la dirección de la búsqueda, se usa el gradiente de la función dada, un vector, cuyos componentes son las derivadas parciales de la función minimizada con respecto a la correspondientes parámetros optimizados.

En el grupo de métodos de segundo orden se utilizan 2 derivadas (su uso es bastante limitado debido a la presencia de dificultades en su cálculo).

Lista de métodos de optimización sin restricciones

Cuando se utiliza la búsqueda multidimensional sin utilizar derivadas, los métodos de optimización sin restricciones son los siguientes:

  • Hook and Jeeves (implementación de 2 tipos de búsqueda: patrón e investigación);
  • minimización con respecto al simplex correcto (busque el punto mínimo de la función correspondiente comparando en cada iteración separada de sus valores en los vértices del simplex);
  • descenso cíclico de coordenadas (utilizando vectores de coordenadas como puntos de referencia);
  • Rosenbrock (basado en el uso de minimización unidimensional);
  • minimización con respecto a un símplex deformado (modificación del método de minimización con respecto a un símplex regular: adición de un procedimiento de compresión, estiramiento).

En la situación de utilizar derivadas en el proceso de búsqueda multidimensional, se distingue el método de descenso más pronunciado (el procedimiento más fundamental para minimizar una función diferenciable con varias variables).

Además, también existen métodos que utilizan direcciones conjugadas (método de Davidon-Fletcher-Powell). Su esencia es la representación de las direcciones de búsqueda como Dj * grad (f (y)).

Clasificación de métodos matemáticos de optimización

Convencionalmente, en función de la dimensión de las funciones (objetivo), son:

  • con 1 variable;
  • multidimensional.

Dependiendo de la función (lineal o no lineal), existe una gran cantidad de métodos matemáticos destinados a encontrar un extremo para resolver un problema dado.

Según el criterio para la aplicación de derivadas, los métodos matemáticos de optimización se subdividen en:

  • métodos para calcular 1 derivada de la función objetivo;
  • multidimensional (1er gradiente de cantidad de vector derivado).

Según la eficiencia del cálculo, existen:

  • métodos para el cálculo rápido del extremo;
  • cálculo simplificado.

Esta es una clasificación condicional de los métodos considerados.

Optimización de procesos comerciales

Aquí se pueden utilizar diferentes métodos, dependiendo de los problemas que se resuelvan. Es habitual destacar los siguientes métodos para optimizar los procesos comerciales:

  • excepciones (reducción de los niveles del proceso existente, eliminación de las causas de interferencia y control de entrada, reducción de rutas de transporte);
  • simplificación (paso facilitado del pedido, complejidad reducida de la estructura del producto, distribución del trabajo);
  • estandarización (uso de programas, métodos, tecnologías especiales, etc.);
  • aceleración (ingeniería paralela, estimulación, diseño de prototipos operativos, automatización);
  • cambio (cambios en el campo de las materias primas, tecnologías, métodos de trabajo, disposición del personal, sistemas de trabajo, volumen de pedidos, orden de procesamiento);
  • asegurar la interacción (en relación con las unidades organizativas, el personal, el sistema de trabajo);
  • selección e inclusión (en relación con los procesos, componentes necesarios).

Optimización fiscal: métodos

La legislación rusa brinda al contribuyente oportunidades muy ricas para recortes de impuestos, por lo que es habitual señalar los métodos destinados a minimizarlos como generales (clásicos) y especiales.

Los métodos generales de optimización fiscal son los siguientes:

  • elaboración de la política contable de la empresa con el máximo uso posible de las oportunidades proporcionadas por la legislación rusa (el procedimiento para cancelar la IBE, la elección del método para calcular el producto de la venta de bienes, etc.);
  • optimización mediante contrato (celebración de transacciones preferenciales, uso claro y competente de la redacción, etc.);
  • aplicación de diversos tipos de beneficios, exenciones fiscales.

El segundo grupo de métodos también puede ser utilizado por todas las empresas, pero aún tienen un alcance bastante limitado. Los métodos especiales de optimización fiscal son los siguientes:

  • sustitución de relaciones (una operación que prevé una tributación onerosa se sustituye por otra que le permite alcanzar un objetivo similar, pero que al mismo tiempo utiliza un procedimiento de tributación preferencial).
  • separación de relaciones (reemplazo de solo una parte de una transacción comercial);
  • aplazamiento del pago de impuestos (aplazamiento del momento en que el objeto del impuesto aparece a otro período calendario);
  • reducción directa del objeto de tributación (deshacerse de muchas transacciones o bienes gravables sin afectar negativamente el negocio principal de la empresa).

5. Optimización multidimensional

Programación lineal

Mejoramiento - es una actividad con propósito, que consiste en obtener los mejores resultados en las condiciones adecuadas.

La evaluación cuantitativa de la calidad optimizada se denomina criterio de optimalidad o función de destino Puede escribirse como:

(5.1)

donde x 1, x 2, ..., x n- algunos parámetros de la optimización del objeto.

Hay dos tipos de problemas de optimización: incondicional y condicional.

Tarea incondicional La optimización consiste en encontrar el máximo o mínimo de la función real (5.1) denortevariables válidas y definir los valores de argumento correspondientes.

Problemas de optimización condicional , o problemas con restricciones, son aquellos en cuya formulación se imponen restricciones sobre los valores de los argumentos en forma de igualdades o desigualdades.

La solución de problemas de optimización en los que el criterio de optimización es una función lineal de variables independientes (es decir, contiene estas variables en el primer grado) con restricciones lineales sobre ellas es el tema de programación lineal.

La palabra "programación" aquí refleja el objetivo final del estudio: la determinación del plan óptimo o del programa óptimo, según el cual se selecciona la mejor variante óptima del conjunto de posibles variantes del proceso en estudio.

Un ejemplo tal tarea es distribución óptima de materias primas entre diferentes industrias al máximo costo de producción.

Dejemos que dos tipos de productos se fabriquen a partir de dos tipos de materias primas.

Denotemos: x 1, x 2 - el número de unidades de productos del primer y segundo tipo, respectivamente; c 1, c 2 –Unidades de productos del primer y segundo tipo, respectivamente. Entonces el costo total de todos los productos será:

(5.2)

Como resultado de la producción, es deseable que se maximice el costo total de producción.R (x 1, x 2 ) Es la función objetivo en este problema.

b 1, b 2 - la cantidad de materias primas del primer y segundo tipo disponibles;a ij- número de unidades I -ésimo tipo de materia prima necesaria para la producción de una unidadj-ésimo tipo de producto.

Considerando que el consumo de un recurso dado no puede exceder su monto total, anotamos las condiciones restrictivas para los recursos:

(5.3)

Variables x 1, x 2 también podemos decir que no son negativos y no son infinitos.:

(5.4)

Entre el conjunto de soluciones del sistema de desigualdades (5.3) y (5.4), se requiere encontrar dicha solución ( x 1, x 2 ) para la cual la funciónRalcanza el valor más alto.

Las llamadas tareas de transporte (tareas de la organización óptima de la entrega de mercancías, materias primas o productos desde varios almacenes a varios destinos con un mínimo de costes de transporte) y una serie de otras se formulan de forma similar.

Un método gráfico para resolver problemas de programación lineal.

Que se requiera encontrar x 1 y x 2 , satisfactorio sistema de desigualdades:

(5.5)

Y condiciones no negatividad:

(5.6)

por cual función

(5. 7 )

alcanza un máximo.

Solución.

Trazar en un sistema de coordenadas rectangular x 1 Buey 2 el área de soluciones factibles al problema (Fig. 11). Para ello, reemplazando cada una de las desigualdades (5.5) por igualdad, construimos el correspondiente para él una línea fronteriza:

(I = 1, 2, … , r)

Arroz. once

Esta línea divide todo el plano en dos semiplanos. Para coordenadas x 1, x 2 Cualquier punto A un semiplano, se cumple la siguiente desigualdad:

y para las coordenadas de cualquier punto V el otro semiplano es la desigualdad opuesta:

Las coordenadas de cualquier punto de la línea de límite satisfacen la ecuación:

Para determinar en qué lado de la línea de límite se encuentra el semiplano correspondiente a una desigualdad dada, basta con "probar" un punto (el punto más simple es O(0; 0)). Si, al sustituir sus coordenadas en el lado izquierdo de la desigualdad, se satisface, entonces el semiplano se gira hacia el punto de prueba, si no se satisface la desigualdad, entonces el semiplano correspondiente se gira en la dirección opuesta. La dirección del semiplano se muestra en el dibujo mediante un sombreado. Desigualdades:

corresponden a los semiplanos ubicados a la derecha de la ordenada y por encima de la abscisa.

En la figura, construimos líneas de contorno y semiplanos correspondientes a todas las desigualdades.

La parte común (intersección) de todos estos semiplanos representará la región de soluciones factibles de este problema.

Al construir la región de soluciones factibles, dependiendo del tipo específico de sistema de restricciones (desigualdades) en las variables, puede ocurrir uno de los siguientes cuatro casos:

Arroz. 12. La región de soluciones factibles está vacía, lo que corresponde a la inconsistencia del sistema de desigualdades; sin solución

Arroz. 13. La región de soluciones factibles está representada por un punto A, que corresponde a la única solución del sistema.

Arroz. 14. La región de soluciones factibles está acotada, representada como un polígono convexo. Hay un conjunto infinito de soluciones factibles.

Arroz. 15. La región de soluciones factibles es ilimitada, en forma de región poligonal convexa. Hay un conjunto infinito de soluciones factibles.

Representación gráfica de la función objetiva

con un valor fijoRdefine una línea recta, y al cambiarR- una familia de líneas paralelas con el parámetroR. Para todos los puntos que se encuentran en una de las líneas, la función R toma un valor definido, por lo tanto, estas líneas se llaman líneas de nivel para la función R.

Vector de degradado:

perpendiculara las líneas de nivel, muestra la dirección de aumentoR.

El problema de encontrar la solución óptima al sistema de desigualdades (5.5) para el cual la función objetivoR(5.7) alcanza un máximo, geométricamente se reduce a determinar en la región de soluciones admisibles el punto a través del cual la línea de nivel correspondiente al mayor valor del parámetroR

Arroz. dieciséis

Si la región de soluciones factibles es un polígono convexo, entonces el extremo de la funciónR se alcanza al menos en uno de los vértices de este polígono.

Si valor extremoRse alcanza en dos vértices, entonces se alcanza el mismo valor extremo en cualquier punto del segmento que conecta estos dos vértices. En este caso, se dice que el problema tiene óptimo alternativo .

En el caso de una región ilimitada, el extremo de la funciónRo no existe, o se alcanza en uno de los vértices de la región, o tiene un óptimo alternativo.

Ejemplo.

Deje que se requiera encontrar los valores x 1 y x 2 satisfaciendo el sistema de desigualdades:

Y condiciones no negatividad:

por que función:

alcanza un máximo.

Solución.

Reemplazamos cada una de las desigualdades con igualdad y construimos las líneas de límite:

Arroz. 17

Definamos los semiplanos correspondientes a estas desigualdades "probando" el punto (0; 0). Teniendo en cuenta no negatividad x 1 y x 2 obtenemos la región de soluciones factibles de este problema en forma de polígono convexo OAVDE.

En la región de soluciones factibles, encontramos la solución óptima construyendo el vector de gradiente

demostracióndirección ascendenteR.

La solución óptima corresponde al punto V, cuyas coordenadas se pueden determinar gráficamente o resolviendo un sistema de dos ecuaciones correspondientes a las líneas de contorno AB y VD:

Respuesta: x 1 = 2; x 2 = 6; R max = 22.

Tareas. Encuentre la posición del punto extremo y el valor extremo de la función objetivo

bajo las restricciones dadas.

Cuadro 9

Opción No.

Extremum
Restricciones

METRO hacha

; ;

; ;

Max

; ; ;

;

; ;

; ;

; ;

; ; ;

;

; ;


Métodos clásicos de optimización ilimitada

Introducción

Como sabe, el problema clásico de la optimización sin restricciones tiene la forma:

Existen métodos analíticos y numéricos para resolver estos problemas.

En primer lugar, recordemos los métodos analíticos para resolver el problema de la optimización ilimitada.

Los métodos de optimización sin restricciones ocupan un lugar importante en el curso de AA. Esto se debe a su aplicación directa en la resolución de una serie de problemas de optimización, así como en la implementación de métodos para resolver una parte importante de los problemas de optimización condicional (problemas MT).

1. Condiciones necesarias para el punto de mínimo local (máximo)

Sea m entregar los valores mínimos de la función. Se sabe que en este punto el incremento de la función no es negativo, es decir

Hallemos usando la expansión de la función en la vecindad de m en la serie de Taylor.

donde, es la suma de los miembros de la serie cuyo orden es relativo a los incrementos (dos) y superiores.

De (4) se deduce claramente que

Supongamos que, entonces

Teniendo en cuenta (6) tenemos :. (7)

Supongamos que es positivo, es decir. ... Elijamos, entonces, un producto que contradice (1).

Por tanto, es realmente obvio.

Argumentando de manera similar con respecto a otras variables, obtenemos una condición necesaria para los puntos de mínimo local de una función de varias variables

Es fácil demostrar que las condiciones necesarias para el punto máximo local serán exactamente las mismas que para el punto mínimo local, es decir condiciones (8).

Está claro que el resultado de la demostración será una desigualdad de la forma: - la condición para un incremento no positivo de una función en una vecindad de un máximo local.

Las condiciones necesarias obtenidas no responden a la pregunta: ¿el punto estacionario es un punto mínimo o un punto máximo?

La respuesta a esta pregunta se puede obtener examinando las condiciones suficientes. Estas condiciones implican el estudio de la matriz de las segundas derivadas de la función objetivo.

2. Condiciones suficientes para el punto de mínimo local (máximo)

Representamos la expansión de una función en una vecindad de un punto en una serie de Taylor hasta cuadrática en términos.

La expansión (1) se puede presentar de forma más concisa utilizando el concepto: "producto escalar de vectores" y "producto vector-matriz".

Matriz de dos derivadas de la función objetivo con respecto a las variables correspondientes.

El incremento de función basado en (1 ") se puede escribir como:

Dadas las condiciones necesarias:

Sustituya (3) en la forma:

La forma cuadrática se llama forma cuadrática diferencial (DKF).

Si el DKF es positivo definido, entonces el punto estacionario también es un punto mínimo local.

Si el DKF y la matriz que lo representa están definidos negativamente, entonces el punto estacionario también es un punto máximo local.

Entonces, las condiciones necesarias y suficientes para un punto de mínimo local tienen la forma

(las mismas condiciones necesarias se pueden escribir de la siguiente manera:

Condición suficiente.

En consecuencia, la condición necesaria y suficiente para el máximo local tiene la forma:

Recordemos el criterio para determinar si la forma cuadrática y la matriz que la representa son definidas positivas o definidas negativas.

3. Criterio de Sylvester

Le permite responder a la pregunta: ¿es la forma cuadrática y la matriz que la representa positivamente definida, o negativa definida?

Se llama matriz de Hesse.

El principal determinante de la matriz de Hesse.

y el DKF que representa será positivo definido si todos los determinantes principales de la matriz hessiana () son positivos (es decir, se lleva a cabo el siguiente esquema de signos:

Si hay un esquema de signo diferente para los principales determinantes de la matriz de Hesse, por ejemplo, entonces la matriz y el DKF se definen negativamente.

4. El método de Euler es un método clásico para resolver problemas de optimización sin restricciones.

Este método se basa en las condiciones necesarias y suficientes estudiadas en 1.1 a 1.3; aplicamos para encontrar extremos locales de funciones diferenciables continuas solamente.

El algoritmo de este método es bastante simple:

1) utilizando las condiciones necesarias, formamos un sistema de ecuaciones no lineales en el caso general. Tenga en cuenta que generalmente es imposible resolver este sistema analíticamente; es necesario aplicar métodos numéricos para resolver sistemas de ecuaciones no lineales (NE) (ver "FM"). Por ello, el método de Euler será un método analítico-numérico. Resolviendo el sistema de ecuaciones especificado, encontramos las coordenadas del punto estacionario.

2) investigamos el DKF y la matriz de Hesse que lo representa. Utilizando el criterio de Sylvester, determinamos si el punto estacionario es un punto mínimo o un punto máximo;

3) calcular el valor de la función objetivo en el punto extremo

Usando el método de Euler, resuelva el siguiente problema de optimización sin restricciones: encuentre 4 puntos estacionarios de una función de la forma:

Descubra la naturaleza de estos puntos, ya sean puntos mínimos o puntos de silla (ver). Construya una representación gráfica de esta función en el espacio y en un plano (usando líneas de nivel).

5. El problema clásico de optimización condicional y métodos para su solución: Método de eliminación y Método de multiplicadores de Lagrange (MLM)

Como sabe, el problema clásico de la optimización condicional tiene la forma:

Gráfica que explica el enunciado del problema (1), (2) en el espacio.

Ecuaciones de línea de nivel

Entonces, el ODR en el problema bajo consideración es una cierta curva representada por la ecuación (2 ").

Como puede ver en la figura, el punto es el punto del máximo global incondicional; punto - el punto del mínimo local condicional (relativo); punto - el punto del máximo local condicional (relativo).

El problema (1 "), (2") se puede resolver mediante el método de eliminación (sustitución), resolviendo la ecuación (2 ") con respecto a la variable y sustituyendo la solución encontrada (1").

El problema original (1 "), (2") se transforma así en un problema de optimización ilimitada de la función, que puede resolverse fácilmente mediante el método de Euler.

Método de exclusión (sustitución).

Deje que la función objetivo dependa de las variables:

se denominan variables dependientes (o variables de estado); en consecuencia, podemos introducir el vector

Las variables restantes se denominan variables de decisión independientes.

En consecuencia, podemos hablar de un vector de columna:

y vectores.

En el clásico problema de optimización condicional:

El sistema (2), de acuerdo con el método de exclusión (sustitución), debe resolverse con respecto a las variables dependientes (variables de estado), es decir, Deben obtenerse las siguientes expresiones para las variables dependientes:

¿Es el sistema de ecuaciones (2) siempre solucionable con respecto a las variables dependientes? No siempre, esto es posible solo en el caso en que el determinante, llamado jacobiano, cuyos elementos tienen la forma:

no es igual a cero (ver el teorema correspondiente en el curso de maestría)

Como puede ver, las funciones deben ser funciones diferenciables continuas y, en segundo lugar, los elementos del determinante deben calcularse en el punto estacionario de la función objetivo.

Sustituyendo de (3) en la función objetivo (1), tenemos:

La función investigada para el extremo se puede producir mediante el método de Euler, el método de optimización sin restricciones de una función continuamente diferenciable.

Entonces, el método de eliminación (sustitución) permite utilizar el problema de la optimización condicional clásica para transformarlo en un problema de optimización incondicional de una función - una función de variables bajo la condición (4), lo que permite obtener un sistema de expresiones ( 3).

La desventaja del método de eliminación: dificultades y, a veces, la imposibilidad de obtener un sistema de expresiones (3). Libre de este inconveniente, pero requiriendo el cumplimiento de la condición (4), está MLM.

5.2. Método del multiplicador de Lagrange. Condiciones necesarias en el problema clásico de optimización condicional. Función de Lagrange

MLM permite el problema original de la optimización condicional clásica:

Transforme una función especialmente diseñada: la función de Lagrange en un problema de optimización ilimitada:

donde, - multiplicadores de Lagrange;

Como puede ver, es una suma que consta de la función objetivo original y la suma "ponderada" de funciones, funciones que representan sus restricciones (2) del problema original.

Sea el punto el punto del extremo incondicional de la función, entonces, como se sabe, o (el diferencial total de la función en el punto).

Utilizando el concepto de variables dependientes e independientes - variables dependientes; son variables independientes, entonces representamos (5) en forma expandida:

De (2) es obvio que se sigue un sistema de ecuaciones de la forma:

El resultado de calcular el diferencial total para cada una de las funciones.

Representamos (6) en forma "expandida", utilizando el concepto de variables dependientes e independientes:

Tenga en cuenta que (6 "), a diferencia de (5"), es un sistema que consta de ecuaciones.

Multipliquemos cada -ésima ecuación del sistema (6 ") por el correspondiente -ésimo multiplicador de Lagrange. Súmelos y con la ecuación (5") y obtenga la expresión:

Organicemos los multiplicadores de Lagrange de tal manera que la expresión entre corchetes bajo el signo de la primera suma (es decir, los coeficientes en las diferenciales de las variables independientes) sea igual a cero.

El término "eliminar" los multiplicadores de Lagrange de la manera anterior significa que es necesario resolver un determinado sistema de ecuaciones con respecto a.

La estructura de tal sistema de ecuaciones se puede obtener fácilmente igualando la expresión entre corchetes bajo el signo de la primera suma a cero:

Reescribimos (8) como

El sistema (8 ") es un sistema de ecuaciones lineales con respecto a las conocidas:. El sistema es solucionable si (por eso, como en el método de eliminación en el caso considerado, se debe cumplir la condición). (9 )

Dado que en la expresión clave (7) la primera suma es igual a cero, es fácil entender que la segunda suma también será igual a cero, es decir el siguiente sistema de ecuaciones es válido:

El sistema de ecuaciones (8) consta de ecuaciones y el sistema de ecuaciones (10) consta de ecuaciones; de todas las ecuaciones en dos sistemas, y las incógnitas

Las ecuaciones faltantes vienen dadas por el sistema de ecuaciones de restricciones (2):

Entonces, existe un sistema de ecuaciones para encontrar incógnitas:

El resultado obtenido es que el sistema de ecuaciones (11) constituye el contenido principal del MLM.

Es fácil comprender que el sistema de ecuaciones (11) puede obtenerse de manera muy simple introduciendo en consideración una función de Lagrange especialmente construida (3).

En realidad

Entonces, el sistema de ecuaciones (11) se puede representar de la forma (usando (12), (13)):

El sistema de ecuaciones (14) representa una condición necesaria en el problema clásico de optimización condicional.

La solución resultante de este sistema, el valor del vector se llama punto condicionalmente estacionario.

Para descubrir la naturaleza del punto condicionalmente estacionario, es necesario utilizar condiciones suficientes.

5.3 Condiciones suficientes en el problema clásico de optimización condicional. Algoritmo MML

Estas condiciones permiten averiguar si un punto condicionalmente estacionario es un punto de un mínimo condicional local o un punto de un máximo condicional local.

Relativamente simple, así como se obtuvieron condiciones suficientes en el problema para un extremo incondicional. También se pueden obtener condiciones suficientes en el problema clásico de optimización condicional.

El resultado de este estudio:

donde es el punto del mínimo condicional local.

donde es el punto del máximo condicional local, es la matriz hessiana con elementos

La matriz de Hesse tiene dimensiones.

La dimensión de la matriz de Hesse se puede reducir utilizando la condición de desigualdad a cero del jacobiano :. Bajo esta condición, las variables dependientes se pueden expresar en términos de variables independientes, entonces la matriz de Hesse tendrá dimensiones, es decir es necesario hablar de una matriz con elementos

entonces las condiciones suficientes serán las siguientes:

El punto del mínimo condicional local.

El punto del máximo condicional local.

Prueba: Algoritmo MML:

1) componga la función de Lagrange :;

2) usando las condiciones necesarias, formamos un sistema de ecuaciones:

3) encontrar un punto de la solución de este sistema;

4) usando condiciones suficientes, determinamos si el punto es un punto de un mínimo o máximo condicional local, luego encontramos

1.5.4. Un método grafoanalítico para resolver el problema clásico de optimización condicional en el espacio y sus modificaciones al resolver los problemas más simples de IP y AP

Este método utiliza una interpretación geométrica del problema clásico de optimización restringida y se basa en una serie de hechos importantes inherentes a este problema.

B es la tangente común para la función y la función que representa el ODR.

Como puede ver en la figura, un punto es un punto de un mínimo incondicional, un punto es un punto de un mínimo local condicional, un punto es un punto de un máximo local condicional.

Demostremos que en los puntos de los extremos locales condicionales la curva y las líneas de nivel correspondientes

Se sabe por el curso de MA que en el punto de tangencia la condición

donde es la pendiente de la tangente trazada por la línea de nivel correspondiente; es la pendiente de la tangente a la función

Se conoce la expresión (MA) para estos coeficientes:

Demostremos que estos coeficientes son iguales.

porque las condiciones necesarias "hablan" de ello

Lo anterior nos permite formular el algoritmo HFA para el método para resolver el problema clásico de optimización restringida:

1) construimos una familia de líneas del nivel de función objetivo:

2) construimos un ODR usando la ecuación de restricción

3) para corregir el aumento de la función, encontramos y aclaramos la naturaleza de los puntos extremos;

4) investigamos la interacción de las líneas de nivel y la función, mientras encontramos a partir del sistema de ecuaciones las coordenadas de puntos condicionalmente estacionarios: mínimos condicional locales y máximos condicional locales.

5) calcular

Cabe señalar especialmente que las etapas principales del método HFA para resolver el problema clásico de optimización restringida coinciden con las etapas principales del método HFA para resolver problemas NP y LP, la única diferencia está en el ODR, así como en encontrar el ubicación de puntos extremos en el ODR (por ejemplo, en problemas LP, estos puntos se encuentran necesariamente en los vértices del polígono convexo que representa el ODR).

5.5. Sobre el significado práctico de MML

Representemos el problema clásico de optimización condicional en la forma:

donde son cantidades variables que representan recursos variables en problemas técnicos y económicos aplicados.

En el espacio, el problema (1), (2) toma la forma:

donde es una variable. (2 ")

Sea el punto del extremo condicional:

Cuando cambia, cambia

El valor de la función objetivo cambiará en consecuencia:

Calculemos la derivada:

De (3), (4), (5). (6)

Sustituya (5 ") en (3) y obtenga:

De (6) que el multiplicador de Lagrange caracteriza el valor de "reacción" (ortogonal al valor de la función objetivo) a los cambios en el parámetro.

En general, (6) toma la forma:

De (6), (7), que el factor caracteriza el cambio cuando el -ésimo recurso correspondiente cambia en 1.

Si es la ganancia máxima o el costo mínimo, entonces, caracteriza los cambios en este valor al cambiar, por 1.

5.6. El problema clásico de optimización restringida como el problema de encontrar el punto de silla de la función de Lagrange:

Un par se llama punto silla si la desigualdad se mantiene.

Obviamente, de (1). (2)

De (2) eso. (3)

Como puede ver, el sistema (3) contiene ecuaciones similares a aquellas ecuaciones que representan la condición necesaria en el problema clásico de optimización condicional:

donde está la función de Lagrange.

En relación con la analogía de los sistemas de ecuaciones (3) y (4), el problema clásico de la optimización condicional puede considerarse como el problema de encontrar el punto silla de la función de Lagrange.

Documentos similares

    Problemas de optimización multidimensional en el estudio de procesos tecnológicos en la industria textil, análisis de dificultades emergentes. Encontrar un extremo, como un extremo, el valor de la función objetivo de la optimización multidimensional sin restricciones.

    prueba, agregado 26/11/2011

    Caracterización de métodos clásicos de optimización ilimitada. Determinación de una condición necesaria y suficiente para la existencia de un extremo de funciones de una y varias variables. Regla del multiplicador de Lagrange. Condiciones necesarias y suficientes para la optimalidad.

    trabajo de término agregado el 13/10/2013

    Métodos y características para resolver problemas de optimización, en particular, en la distribución de inversiones y la elección de una ruta en la red de transporte. Los detalles del modelado utilizando los métodos de Hamming y Brown. Identificación, estimulación y motivación como funciones de gestión.

    prueba, agregado 12/12/2009

    Enunciado, análisis, solución gráfica de problemas de optimización lineal, método simplex, dualidad en optimización lineal. Formulación del problema del transporte, propiedades y búsqueda de una solución de referencia. Optimización condicional bajo restricciones de igualdad.

    manual, agregado el 07/11/2010

    Ruta crítica en el gráfico. Distribución óptima del flujo en la red de transporte. Problema de programación lineal resuelto gráficamente. Desafío de transporte desequilibrado. Métodos numéricos para la resolución de problemas unidimensionales de optimización estática.

    trabajo de término agregado 21/06/2014

    Un método gráfico para resolver el problema de la optimización de los procesos productivos. Aplicación de un algoritmo simplex para resolver un problema de control de producción económicamente optimizado. Método de programación dinámica para elegir el perfil de vía óptimo.

    prueba, agregada 15/10/2010

    Métodos de optimización para la resolución de problemas económicos. La formulación clásica del problema de optimización. Optimización de funciones. Optimización de funcionales. Optimización multicriterio. Métodos para reducir un problema de varios criterios a un problema de un solo criterio. Método de concesiones.

    resumen, agregado 20/06/2005

    Aplicación de métodos de programación no lineal para la resolución de problemas con funciones no lineales de variables. Condiciones de optimalidad (teorema de Kuhn-Tucker). Métodos de optimización condicional (método de Wolfe); diseño degradado; funciones de penalización y barrera.

    resumen, agregado 25/10/2009

    Concepto, definición, resaltado de funcionalidades, posibilidades y características de problemas existentes de optimización multicriterio y formas de solucionarlos. Cálculo del método de igual y mínima desviación de optimización multicriterio y su aplicación en la práctica.

    trabajo de término agregado 21/01/2012

    Conceptos básicos de modelado. Conceptos generales y definición del modelo. Declaración de problemas de optimización. Métodos de programación lineal. Tarea general y típica en programación lineal. Método simplex para la resolución de problemas de programación lineal.

Objetivo 1. Encontrar

El problema 1 se reduce a resolver el sistema de ecuaciones:

y el estudio del valor del segundo diferencial:

en los puntos de solución de las ecuaciones (8.3).

Si la forma cuadrática (8.4) se define negativamente en un punto, entonces alcanza su valor máximo, y si se define positivamente, entonces el valor mínimo.

Ejemplo:

El sistema de ecuaciones tiene soluciones:

El punto (-1 / 3,0) es el punto máximo y el punto (1 / 3,2) es el punto mínimo.

Objetivo 2. Encontrar

bajo condiciones:

El problema 2 se resuelve mediante el método del multiplicador de Lagrange. Para ello, se encuentra una solución de sistema (m + n) ecuaciones:

Ejemplo. Encuentre los lados de un rectángulo de área máxima inscritos en un círculo :. El área A de un rectángulo se puede escribir como: A = 4hu, luego

Objetivo 3. Encontrar:

bajo condiciones:

Esta tarea cubre una amplia gama de tareas definidas por funciones F y .

Si son lineales, entonces el problema es un problema de programación lineal.

Tarea3 una.

bajo condiciones

Se resuelve mediante el método simplex, que, utilizando el aparato de álgebra lineal, realiza una enumeración intencionada de los vértices del poliedro definido por (8.13).

Método simplex (consta de dos etapas):

Etapa 1. Encontrar la solución de soporte x (0).

La solución de soporte es uno de los puntos del politopo (8.13).

Etapa 2. Encontrar la solución óptima.

La solución óptima se encuentra mediante la enumeración secuencial de los vértices del politopo (8.13), en la que el valor de la función objetivo z no disminuye en cada paso, es decir:

Un caso especial de un problema de programación lineal es el llamado problema de transporte.

Problema de transporte. Que haya almacenes en puntos, en los que las mercancías se almacenan en cantidades, respectivamente. En puntos están los consumidores que necesitan suministrar estos bienes en cantidades, respectivamente. Nosotros denotamos C ij el costo de transportar una unidad de carga entre puntos

Investiguemos el funcionamiento del transporte por parte de los consumidores de bienes en cantidades suficientes para satisfacer las necesidades de los consumidores. Denotemos por la cantidad de mercancías transportadas desde el punto a I apuntar B j .

Para satisfacer las necesidades del consumidor, es necesario que los valores NS ij satisfacer las condiciones:

Al mismo tiempo desde un almacén; no se pueden sacar productos en cantidades mayores que las existentes. Esto significa que los valores buscados deben satisfacer el sistema de desigualdades:

Existen innumerables formas de satisfacer las condiciones (8.14), (8.15), es decir, elaborar un plan de transporte que satisfaga las necesidades de los consumidores. Para que el investigador de operaciones pueda elegir una solución específica, es decir, asignar ciertas NS ij, se debe formular una cierta regla de selección, determinada mediante un criterio que refleje nuestra idea subjetiva del objetivo.

El problema del criterio se resuelve independientemente del estudio de la operación: el criterio debe ser especificado por el lado operativo. En este problema, uno de los posibles criterios será el costo del transporte. Se define de la siguiente manera:

Luego, el problema de transporte se formula como un problema de programación lineal: determine las cantidades que satisfagan las restricciones (8.14), (8.15) y proporcionen a la función (8.16) un valor mínimo. La restricción (8.15) es una condición de equilibrio; La condición (8.14) se puede llamar el propósito de la operación, porque el significado de la operación es asegurar las necesidades de los consumidores.

Estas dos condiciones constituyen esencialmente el modelo de la operación. La implementación de la operación dependerá del criterio por el cual se logre el objetivo de la operación. El criterio puede aparecer en varios roles. Puede actuar tanto como una forma de formalizar el objetivo como un principio para elegir acciones entre las permisibles, es decir, satisfacer las restricciones.

Uno de los métodos conocidos para resolver el problema del transporte es el método potencial.

En la primera etapa de resolución del problema, se elabora un plan de transporte inicial que satisface

restricciones (8.14), (8.15). Si (es decir, los requisitos totales no coinciden con las existencias totales de productos en los almacenes), se introduce un punto de consumo ficticio o un almacén ficticio con costos de transporte iguales a cero. Para una nueva tarea, el número total de mercancías en los almacenes coincide con su demanda total. Entonces, algún método (por ejemplo, el elemento más pequeño o la esquina noroeste) es el plan original. En el siguiente paso del procedimiento del plan resultante, se construye un sistema de características especiales (potenciales). Una condición necesaria y suficiente para un plan óptimo es su potencialidad. El procedimiento para refinar el plan se lleva a cabo hasta que se vuelve potencial (óptimo).

Problema 3b. En el caso general, el problema (8.10 - 8.11) se denomina problema de programación no lineal. Considérelo en una forma más aceptada:

bajo condiciones

Para solucionar este problema se utilizan los denominados métodos de relajación. El proceso de construir una secuencia de puntos se llama relajación si:

Métodos de descenso (esquema general)... Todos los métodos de descenso para resolver el problema de optimización sin restricciones (8.17) difieren en la elección de la dirección de descenso o en la forma de movimiento a lo largo de la dirección de descenso. Los métodos de descenso consisten en el siguiente procedimiento de construcción de secuencia { X k }.

Se elige un punto arbitrario como aproximación inicial X 0 . Las aproximaciones sucesivas se construyen de acuerdo con el siguiente esquema:

Punto X k se selecciona la dirección de descenso - s k ;

Encuentre (k + 1) - ésima aproximación mediante la fórmula:

donde como valor se elige cualquier número que satisfaga la desigualdad

donde número es cualquier número cuando

En la mayoría de los métodos de descenso, el valor de  k se elige para que sea igual a uno. Por lo tanto, para determinar k, uno tiene que resolver el problema de minimización unidimensional.

Método de descenso por gradiente. Desde el antigradiente: indica la dirección de la disminución más pronunciada de la función. F(X), entonces es natural moverse desde el punto NS k en esta dirección. Método de descenso, que se denomina método de descenso de gradiente. Si, entonces el proceso de relajación se denomina método de descenso más empinado.

El método de direcciones conjugadas. En álgebra lineal, este método se conoce como el método de gradiente conjugado para resolver sistemas de ecuaciones algebraicas lineales. AX =B, y por lo tanto, como método para minimizar la función cuadrática

Diagrama de método:

Si = 0, entonces este esquema se convierte en un esquema de descenso más empinado. Elección adecuada de valor t k garantiza la convergencia del método de dirección conjugada a una velocidad del mismo orden de magnitud que en los métodos de descenso en gradiente y asegura que el número de iteraciones en el descenso cuadrático sea finito (por ejemplo).

Descenso coordinado. En cada iteración, como la dirección de descenso: s k se selecciona una dirección a lo largo de uno de los ejes de coordenadas. El método tiene una tasa de convergencia del proceso de minimización del orden de 0 (1 / m). Además, depende esencialmente de la dimensión del espacio.

Diagrama de método:

donde el vector de coordenadas

Si en el punto X k hay información sobre el comportamiento del gradiente de la función F(X), por ejemplo:

luego como la dirección de descenso s k podemos tomar el vector de coordenadas mi j . En este caso, la tasa de convergencia del método es n veces menor que con el descenso de gradiente.

En la etapa inicial del proceso de minimización, se puede utilizar el método de descenso cíclico por coordenadas, cuando primero se realiza el descenso en la dirección mi 1 , luego en e 2, etc.hasta mi NS , después de lo cual se repite todo el ciclo. Más prometedor en comparación con el anterior es el descenso por coordenadas, en el que las direcciones de descenso se eligen al azar. Con este enfoque de la elección de la dirección, existen estimaciones a priori que garantizan la función F(X) con la probabilidad tiende a la unidad en, la convergencia del proceso con una tasa del orden de 0 (1 / m).

Diagrama de método:

En cada paso del proceso, de n números (1, 2, ..., n), se selecciona un número al azar j(k) y como s k, el vector de coordenadas unitarias mi j ( k ) , después de lo cual se realiza el descenso:

Método de descenso aleatorio.s k sujeto a una distribución uniforme en esta esfera, y luego de acuerdo con el elemento calculado en el k-ésimo paso del proceso NS Para Esta determinado por:

La tasa de convergencia del método de descenso aleatorio es n veces menor que la del método de descenso de gradiente, pero n veces mayor que la del método de descenso de coordenadas aleatorio. Los métodos de descenso considerados son aplicables a funciones convexas opcionales y garantizan su convergencia bajo restricciones muy pequeñas sobre ellas (como la ausencia de mínimos locales).

Métodos de relajación de la programación matemática. Volvamos al problema 36 ((8.17) - (8.18)):

bajo condiciones

En problemas de optimización con restricciones, la elección de la dirección de descenso está asociada con la necesidad de verificar constantemente que el nuevo valor NS k +1 debería así como el anterior X k satisfacer un sistema de restricciones X.

Método de gradiente condicional. En este método, la idea de elegir la dirección de descenso es la siguiente: en el punto NS Para linealizar la función F(X), construir una función lineal y luego, minimizar F(X) En el set NS, encontrar un punto y k . Posteriormente se asume, y más adelante en esta dirección, se realiza el descenso, de modo que

Por lo tanto, para encontrar la dirección - s k, se debe resolver el problema de minimizar una función lineal en el conjunto X. Si X a su vez viene dada por restricciones lineales, entonces se convierte en un problema de programación lineal.

Método de direcciones posibles. La idea del método: entre todas las direcciones posibles en un punto NS Para elija aquel a lo largo del cual la función F(X) disminuye más rápido y luego desciende en esta dirección.

Dirección - s en el punto NSX Se llama posible si existe tal número que para todos. Para encontrar una posible dirección, es necesario resolver un problema de programación lineal, o el problema de programación cuadrática más simple:

Bajo condiciones:

Sea la solución a este problema. La condición (8.25) garantiza que la dirección es posible. La condición (8.26) asegura el valor máximo de (, es decir, entre todas las direcciones posibles - s, dirección: proporciona la caída más rápida de la función F(X). La condición (8.27) elimina lo ilimitado de la solución al problema. El método de posibles direcciones es resistente a posibles errores de cálculo. Sin embargo, es difícil estimar la tasa de su convergencia en el caso general, y este problema sigue sin resolverse.

Método de búsqueda aleatoria. En el caso general, la implementación de los métodos de minimización anteriores es muy laboriosa, excepto en los casos más simples cuando el conjunto de restricciones tiene una estructura geométrica simple (por ejemplo, es un paralelepípedo multidimensional). En el caso general, el método de búsqueda aleatoria, cuando la dirección de descenso se elige al azar, puede ser muy prometedor. En este caso, perderemos significativamente en la tasa de convergencia, sin embargo, la simplicidad de la elección de la dirección puede compensar estas pérdidas en términos de los costos laborales totales para resolver el problema de minimización.

Diagrama de método:

Se selecciona un punto aleatorio en la esfera unitaria de n dimensiones centrada en el origen r k, sujeto a una distribución uniforme en esta esfera, y luego la dirección de descenso es s k de las condiciones

Se elige como aproximación inicial. Para el punto calculado en cada iteración X k en construcción ( k+ 1) punto X k +1 :

Como calidad, se selecciona cualquier número de = que satisfaga la desigualdad:

La convergencia de este método se demuestra bajo restricciones muy laxas en la función F (convexidad) y muchas restricciones X (convexidad y cierre).