Artículos

4.7: Problemas de optimización


Objetivos de aprendizaje

  • Configurar y resolver problemas de optimización en varios campos aplicados.

Una aplicación común del cálculo es calcular el valor mínimo o máximo de una función. Por ejemplo, las empresas a menudo quieren minimizar los costos de producción o maximizar los ingresos. En la fabricación, a menudo es deseable minimizar la cantidad de material utilizado para envasar un producto con un cierto volumen. En esta sección, mostramos cómo configurar estos tipos de problemas de minimización y maximización y resolverlos utilizando las herramientas desarrolladas en este capítulo.

Resolución de problemas de optimización en un intervalo cerrado y acotado

La idea básica de los problemas de optimización que siguen es la misma. Tenemos una cantidad particular que nos interesa maximizar o minimizar. Sin embargo, también tenemos alguna condición auxiliar que debe cumplirse. Por ejemplo, en el Ejemplo ( PageIndex {1} ), estamos interesados ​​en maximizar el área de un jardín rectangular. Ciertamente, si seguimos agrandando los lados del jardín, el área continuará haciéndose más grande. Sin embargo, ¿qué pasa si tenemos alguna restricción sobre la cantidad de cercas que podemos usar para el perímetro? En este caso, no podemos hacer que el jardín sea tan grande como queramos. Veamos cómo podemos maximizar el área de un rectángulo sujeto a alguna restricción en el perímetro.

Ejemplo ( PageIndex {1} ): maximizar el área de un jardín

Se construirá un jardín rectangular utilizando una pared de roca como un lado del jardín y una cerca de alambre para los otros tres lados (Figura ( PageIndex {1} )). Dado (100 , text {ft} ) de cercas de alambre, determine las dimensiones que crearían un jardín de área máxima. cual es el area maxima?

Solución

Sea (x ) la longitud del lado del jardín perpendicular a la pared de roca y (y ) la longitud del lado paralelo a la pared de roca. Entonces el área del jardín es

(A = x⋅y. )

Queremos encontrar el área máxima posible sujeta a la restricción de que el cercado total sea (100 , text {ft} ). De la Figura ( PageIndex {1} ), la cantidad total de vallado usado será (2x + y. ) Por lo tanto, la ecuación de restricción es

(2x + y = 100. )

Resolviendo esta ecuación para (y ), tenemos (y = 100−2x. ) Por lo tanto, podemos escribir el área como

(A (x) = x⋅ (100−2x) = 100x − 2x ^ 2. )

Antes de intentar maximizar la función de área (A (x) = 100x − 2x ^ 2, ) necesitamos determinar el dominio en consideración. Para construir un jardín rectangular, ciertamente necesitamos que las longitudes de ambos lados sean positivas. Por lo tanto, necesitamos (x> 0 ) y (y> 0 ). Dado que (y = 100−2x ), si (y> 0 ), entonces (x <50 ). Por lo tanto, estamos tratando de determinar el valor máximo de (A (x) ) para (x ) sobre el intervalo abierto ((0,50) ). No sabemos que una función tiene necesariamente un valor máximo en un intervalo abierto. Sin embargo, sabemos que una función continua tiene un máximo absoluto (y un mínimo absoluto) en un intervalo cerrado. Por lo tanto, consideremos la función (A (x) = 100x − 2x ^ 2 ) sobre el intervalo cerrado ([0,50] ). Si el valor máximo ocurre en un punto interior, entonces hemos encontrado el valor (x ) en el intervalo abierto ((0,50) ) que maximiza el área del jardín.

Por tanto, consideramos el siguiente problema:

Maximizar (A (x) = 100x − 2x ^ 2 ) en el intervalo ([0,50]. )

Como se mencionó anteriormente, dado que (A ) es una función continua en un intervalo cerrado y acotado, según el teorema del valor extremo, tiene un máximo y un mínimo. Estos valores extremos ocurren en puntos finales o puntos críticos. En los extremos, (A (x) = 0 ). Dado que el área es positiva para todo (x ) en el intervalo abierto ((0,50) ), el máximo debe ocurrir en un punto crítico. Diferenciando la función (A (x) ), obtenemos

(A ′ (x) = 100−4x. )

Por lo tanto, el único punto crítico es (x = 25 ) (Figura ( PageIndex {2} )). Concluimos que el área máxima debe ocurrir cuando (x = 25 ).

Entonces tenemos (y = 100−2x = 100−2 (25) = 50. ) Para maximizar el área del jardín, sea (x = 25 , text {ft} ) y (y = 50 , text {ft} ). El área de este jardín es (1250 , text {ft} ^ 2 ).

Ejercicio ( PageIndex {1} )

Determine el área máxima si queremos hacer el mismo jardín rectangular que en la Figura ( PageIndex {2} ), pero tenemos (200 , text {ft} ) de cerca.

Insinuación

Necesitamos maximizar la función (A (x) = 200x − 2x ^ 2 ) en el intervalo ([0,100]. )

Respuesta

El área máxima es (5000 , text {ft} ^ 2 ).

Ahora veamos una estrategia general para resolver problemas de optimización similar al Ejemplo.

Estrategia de resolución de problemas: resolución de problemas de optimización

  1. Introduce todas las variables. Si corresponde, dibuje una figura y etiquete todas las variables.
  2. Determine qué cantidad se va a maximizar o minimizar, y para qué rango de valores de las otras variables (si esto se puede determinar en este momento).
  3. Escribe una fórmula para maximizar o minimizar la cantidad en términos de las variables. Esta fórmula puede involucrar más de una variable.
  4. Escribe cualquier ecuación que relacione las variables independientes en la fórmula del paso (3 ). Utilice estas ecuaciones para escribir la cantidad a maximizar o minimizar en función de una variable.
  5. Identifique el dominio de consideración para la función en el paso (4 ) basándose en el problema físico que se va a resolver.
  6. Localice el valor máximo o mínimo de la función del paso (4. ) Este paso normalmente implica buscar puntos críticos y evaluar una función en los puntos finales.

Ahora apliquemos esta estrategia para maximizar el volumen de una caja abierta dada una restricción en la cantidad de material que se utilizará.

Ejemplo ( PageIndex {2} ): maximizar el volumen de una caja

Se debe hacer una caja abierta con una (24 , text {pulg.} ) Por (36 , text {pulg.} ) Quitando un cuadrado de cada esquina del caja y doblando las solapas a cada lado. ¿Qué tamaño de cuadrado se debe cortar de cada esquina para obtener una caja con el volumen máximo?

Solución

Paso 1: Sea (x ) la longitud del lado del cuadrado que se eliminará de cada esquina (Figura ( PageIndex {3} )). Luego, las cuatro solapas restantes se pueden plegar para formar una caja abierta. Sea (V ) el volumen de la caja resultante.

Paso 2: Estamos intentando maximizar el volumen de una caja. Por tanto, el problema es maximizar (V ).

Paso 3: Como se mencionó en el paso 2, estamos tratando de maximizar el volumen de una caja. El volumen de una caja es

[V = L⋅W⋅H nonumber, ]

donde (L, , W, ) y (H ) son el largo, ancho y alto, respectivamente.

Paso 4: De la Figura ( PageIndex {3} ), vemos que la altura de la caja es (x ) pulgadas, la longitud es (36−2x ) pulgadas y el ancho es (24 −2x ) pulgadas. Por tanto, el volumen de la caja es

[ begin {align *} V (x) & = (36−2x) (24−2x) x [4pt] & = 4x ^ 3−120x ^ 2 + 864x end {align *}. ]

Paso 5: Para determinar el dominio de consideración, examinemos la Figura ( PageIndex {3} ). Ciertamente, necesitamos (x> 0. ) Además, la longitud del lado del cuadrado no puede ser mayor o igual a la mitad de la longitud del lado más corto, (24 , text {in.} ); de lo contrario, una de las solapas quedaría completamente cortada. Por lo tanto, estamos tratando de determinar si hay un volumen máximo de la caja para (x ) sobre el intervalo abierto ((0,12). ) Dado que (V ) es una función continua sobre el intervalo cerrado ([0,12] ), sabemos que (V ) tendrá un máximo absoluto sobre el intervalo cerrado. Por lo tanto, consideramos (V ) sobre el intervalo cerrado ([0,12] ) y verificamos si el máximo absoluto ocurre en un punto interior.

Paso 6: Dado que (V (x) ) es una función continua sobre el intervalo cerrado y acotado ([0,12] ), (V ) debe tener un máximo absoluto (y un mínimo absoluto). Dado que (V (x) = 0 ) en los puntos finales y (V (x)> 0 ) para (0

(V ′ (x) = 12x ^ 2−240x + 864. )

Para encontrar los puntos críticos, necesitamos resolver la ecuación

(12x ^ 2−240x + 864 = 0. )

Dividiendo ambos lados de esta ecuación por (12 ), el problema se simplifica para resolver la ecuación

(x ^ 2−20x + 72 = 0. )

Usando la fórmula cuadrática, encontramos que los puntos críticos son

[ begin {align *} x & = dfrac {20 ± sqrt {(- 20) ^ 2−4 (1) (72)}} {2} [4pt] & = dfrac {20 ± sqrt {112}} {2} [4pt] & = dfrac {20 ± 4 sqrt {7}} {2} [4pt] & = 10 ± 2 sqrt {7} end {align *}. ]

Dado que (10 ​​+ 2 sqrt {7} ) no está en el dominio de consideración, el único punto crítico que debemos considerar es (10−2 sqrt {7} ). Por lo tanto, el volumen se maximiza si dejamos que (x = 10−2 sqrt {7} , text {in.} ) El volumen máximo es

[V (10−2 sqrt {7}) = 640 + 448 sqrt {7} ≈1825 , text {in} ^ 3. sin número ]

como se muestra en el siguiente gráfico.

Ejercicio ( PageIndex {2} )

Suponga que las dimensiones del cartón en el Ejemplo ( PageIndex {2} ) son (20 , text {in.} ) Por (30 , text {in.} ) Sea (x ) sea la longitud del lado de cada cuadrado y escriba el volumen de la caja abierta en función de (x ). Determine el dominio de consideración para (x ).

Insinuación

El volumen de la caja es (L⋅W⋅H. )

Respuesta

(V (x) = x (20−2x) (30−2x). ) El dominio es ([0,10] ).

Ejemplo ( PageIndex {3} ): Minimizar el tiempo de viaje

Una isla está a (2 ) mi al norte de su punto más cercano a lo largo de una línea costera recta. Un visitante se aloja en una cabaña en la costa que está a (6 ) mi al oeste de ese punto. El visitante tiene previsto ir de la cabaña a la isla. Suponga que el visitante corre a una velocidad de (8 ) mph y nada a una velocidad de (3 ) mph. ¿Qué distancia debe correr el visitante antes de nadar para minimizar el tiempo que tarda en llegar a la isla?

Solución

Paso 1: Sea (x ) la distancia recorrida y (y ) la distancia nadando (Figura ( PageIndex {5} )). Sea (T ) el tiempo que se tarda en llegar de la cabaña a la isla.

Paso 2: El problema es minimizar (T ).

Paso 3: Para encontrar el tiempo dedicado a viajar desde la cabaña a la isla, agregue el tiempo dedicado a correr y el tiempo dedicado a nadar. Dado que Distancia = Velocidad × Tiempo ((D = R × T), ) el tiempo dedicado a correr es

(T_ {corriendo} = dfrac {D_ {corriendo}} {R_ {corriendo}} = dfrac {x} {8} ),

y el tiempo que pasas nadando es

(T_ {natación} = dfrac {D_ {natación}} {R_ {natación}} = dfrac {y} {3} ).

Por lo tanto, el tiempo total dedicado a viajar es

(T = dfrac {x} {8} + dfrac {y} {3} ).

Paso 4: De la Figura ( PageIndex {5} ), el segmento de línea de (y ) millas forma la hipotenusa de un triángulo rectángulo con catetos de longitud (2 ) mi y (6 − x ) mi. Por lo tanto, por el teorema de Pitágoras, (2 ^ 2 + (6 − x) ^ 2 = y ^ 2 ), y obtenemos (y = sqrt {(6 − x) ^ 2 + 4} ). Por lo tanto, el tiempo total dedicado a viajar viene dado por la función

(T (x) = dfrac {x} {8} + dfrac { sqrt {(6 − x) ^ 2 + 4}} {3} ).

Paso 5: De la Figura ( PageIndex {5} ), vemos que (0≤x≤6 ). Por lo tanto, ([0,6] ) es el dominio de consideración.

Paso 6: Dado que (T (x) ) es una función continua sobre un intervalo cerrado y acotado, tiene un máximo y un mínimo. Comencemos por buscar cualquier punto crítico de (T ) en el intervalo ([0,6]. ) La derivada es

[ begin {align *} T ′ (x) & = dfrac {1} {8} - dfrac {1} {2} dfrac {[(6 − x) ^ 2 + 4] ^ {- 1 / 2}} {3} ⋅2 (6 − x) [4pt] & = dfrac {1} {8} - dfrac {(6 − x)} {3 sqrt {(6 − x) ^ 2 + 4}} end {align *} ]

Si (T ′ (x) = 0, ), entonces

[ dfrac {1} {8} = dfrac {6 − x} {3 sqrt {(6 − x) ^ 2 + 4}} label {ex3eq1} ]

Por lo tanto,

[3 sqrt {(6 − x) ^ 2 + 4} = 8 (6 − x). label {ex3eq2} ]

Al elevar al cuadrado ambos lados de esta ecuación, vemos que si (x ) satisface esta ecuación, entonces (x ) debe satisfacer

[9 [(6 − x) ^ 2 + 4] = 64 (6 − x) ^ 2, nonumber ]

lo que implica

[55 (6 − x) ^ 2 = 36. sin número]

Concluimos que si (x ) es un punto crítico, entonces (x ) satisface

[(x − 6) ^ 2 = dfrac {36} {55}. sin número]

Por lo tanto, las posibilidades de puntos críticos son

[x = 6 ± dfrac {6} { sqrt {55}}. nonumber ]

Dado que (x = 6 + 6 / sqrt {55} ) no está en el dominio, no es posible que exista un punto crítico. Por otro lado, (x = 6−6 / sqrt {55} ) está en el dominio. Como elevamos al cuadrado ambos lados de la Ecuación ref {ex3eq2} para llegar a los posibles puntos críticos, queda verificar que (x = 6−6 / sqrt {55} ) satisface la Ecuación ref {ex3eq1}. Dado que (x = 6−6 / sqrt {55} ) satisface esa ecuación, concluimos que (x = 6−6 / sqrt {55} ) es un punto crítico, y es el único . Para justificar que el tiempo se minimiza para este valor de (x ), solo necesitamos verificar los valores de (T (x) ) en los puntos finales (x = 0 ) y (x = 6 ) y compárelos con el valor de (T (x) ) en el punto crítico (x = 6−6 / sqrt {55} ). Encontramos que (T (0) ≈2.108 , text {h} ) y (T (6) ≈1.417 , text {h} ), mientras que

[T (6−6 / sqrt {55}) ≈1.368 , text {h}. sin número]

Por lo tanto, concluimos que (T ) tiene un mínimo local en (x≈5.19 ) mi.

Ejercicio ( PageIndex {3} )

Suponga que la isla está a (1 ) mi de la costa y que la distancia desde la cabaña al punto de la costa más cercano a la isla es de (15 ) mi. Suponga que un visitante nada a una velocidad de (2.5 ) mph y corre a una velocidad de (6 ) mph. Sea (x ) la distancia que el visitante correrá antes de nadar, y encuentre una función para el tiempo que le toma al visitante llegar desde la cabaña a la isla.

Insinuación

El tiempo (T = T_ {correr} + T_ {nadar}. )

Respuesta

(T (x) = dfrac {x} {6} + dfrac { sqrt {(15 − x) ^ 2 + 1}} {2.5} )

En los negocios, las empresas están interesadas en maximizando los ingresos. En el siguiente ejemplo, consideramos un escenario en el que una empresa ha recopilado datos sobre cuántos coches puede arrendar, según el precio que cobra a sus clientes por alquilar un coche. Usemos estos datos para determinar el precio que la empresa debe cobrar para maximizar la cantidad de dinero que genera.

Ejemplo ( PageIndex {4} ): maximizar los ingresos

Los propietarios de una empresa de alquiler de automóviles han determinado que si cobran a los clientes (p ) dólares por día por alquilar un automóvil, donde (50≤p≤200 ), la cantidad de automóviles (n ) que alquilan por día se puede modelar mediante la función lineal (n (p) = 1000−5p ). Si cobran ($ 50 ) por día o menos, alquilarán todos sus autos. Si cobran ($ 200 ) por día o más, no alquilarán ningún automóvil. Suponiendo que los propietarios planean cobrar a los clientes entre ($ 50 ) por día y ($ 200 ) por día por alquilar un automóvil, ¿cuánto deberían cobrar para maximizar sus ingresos?

Solución

Paso 1: Sea (p ) el precio cobrado por automóvil por día y sea n el número de automóviles alquilados por día. Sea (R ) los ingresos por día.

Paso 2: El problema es maximizar (R. )

Paso 3: El ingreso (por día) es igual a la cantidad de autos alquilados por día multiplicado por el precio cobrado por auto por día, es decir, (R = n × p. )

Paso 4: Dado que el número de automóviles alquilados por día se modela mediante la función lineal (n (p) = 1000−5p, ) los ingresos (R ) se pueden representar mediante la función

[ begin {align *} R (p) & = n × p [4pt] & = (1000−5p) p [4pt] & = - 5p ^ 2 + 1000p. end {align *} ]

Paso 5: Dado que los propietarios planean cobrar entre ($ 50 ) por automóvil por día y ($ 200 ) por automóvil por día, el problema es encontrar los ingresos máximos (R (p) ) para (p ) en el intervalo cerrado ([50,200] ).

Paso 6: Dado que (R ) es una función continua sobre el intervalo cerrado y acotado ([50,200] ), tiene un máximo absoluto (y un mínimo absoluto) en ese intervalo. Para encontrar el valor máximo, busque puntos críticos. La derivada es (R ′ (p) = - 10p + 1000. ) Por lo tanto, el punto crítico es (p = 100 ) Cuando (p = 100, R (100) = $ 50 000. ) Cuando ( p = 50, R (p) = $ 37,500 ). Cuando (p = 200, R (p) = $ 0 ).

Por lo tanto, el máximo absoluto ocurre en (p = $ 100 ). La empresa de alquiler de automóviles debe cobrar ($ 100 ) por día por automóvil para maximizar los ingresos, como se muestra en la siguiente figura.

Ejercicio ( PageIndex {4} )

Una empresa de alquiler de coches cobra a sus clientes (p ) dólares por día, donde (60≤p≤150 ). Se ha descubierto que el número de coches alquilados por día puede modelarse mediante la función lineal (n (p) = 750−5p. ) ¿Cuánto debería cobrar la empresa a cada cliente para maximizar los ingresos?

Insinuación

(R (p) = n × p, ) donde (n ) es el número de automóviles alquilados y (p ) es el precio que se cobra por automóvil.

Respuesta

La empresa debería cobrar ($ 75 ) por automóvil por día.

Ejemplo ( PageIndex {5} ): maximizar el área de un rectángulo inscrito

Se inscribe un rectángulo en la elipse

[ dfrac {x ^ 2} {4} + y ^ 2 = 1. sin número ]

¿Cuáles deberían ser las dimensiones del rectángulo para maximizar su área? cual es el area maxima?

Solución

Paso 1: Para que un rectángulo se inscriba en la elipse, los lados del rectángulo deben ser paralelos a los ejes. Sea (L ) la longitud del rectángulo y (W ) su ancho. Sea (A ) el área del rectángulo.

Paso 2: El problema es maximizar (A ).

Paso 3: El área del rectángulo es (A = LW. )

Paso 4: Sea ((x, y) ) la esquina del rectángulo que se encuentra en el primer cuadrante, como se muestra en la Figura ( PageIndex {7} ). Podemos escribir longitud (L = 2x ) y ancho (W = 2y ). Dado que ( dfrac {x ^ 2} {4 + y ^ 2 = 1} ) y (y> 0 ), tenemos (y = sqrt { dfrac {1 − x ^ 2} {4 }} ). Por lo tanto, el área es

(A = LW = (2x) (2y) = 4x sqrt { dfrac {1 − x ^ 2} {4}} = 2x sqrt {4 − x ^ 2} )

Paso 5: De la Figura ( PageIndex {7} ), vemos que para inscribir un rectángulo en la elipse, la coordenada (x ) - de la esquina en el primer cuadrante debe satisfacer (0

Paso 6: Como se mencionó anteriormente, (A (x) ) es una función continua sobre el intervalo cerrado y acotado ([0,2] ). Por tanto, tiene un máximo absoluto (y un mínimo absoluto). En los extremos (x = 0 ) y (x = 2 ), (A (x) = 0. ) Para (0 0 ).

Por lo tanto, el máximo debe ocurrir en un punto crítico. Tomando la derivada de (A (x) ), obtenemos

[ begin {align *} A '(x) & = 2 sqrt {4 − x ^ 2} + 2x⋅ dfrac {1} {2 sqrt {4 − x ^ 2}} (- 2x) [4pt] & = 2 sqrt {4 − x ^ 2} - dfrac {2x ^ 2} { sqrt {4 − x ^ 2}} [4pt] & = dfrac {8−4x ^ 2 } { sqrt {4 − x ^ 2}}. end {alinear *} ]

Para encontrar puntos críticos, necesitamos encontrar donde (A '(x) = 0. ) Podemos ver que si (x ) es una solución de

[ dfrac {8−4x ^ 2} { sqrt {4 − x ^ 2}} = 0, label {ex5eq1} ]

entonces (x ) debe satisfacer

[8−4x ^ 2 = 0. sin número]

Por lo tanto, (x ^ 2 = 2. ) Por lo tanto, (x = ± sqrt {2} ) son las posibles soluciones de la Ecuación ref {ex5eq1}. Como estamos considerando (x ) en el intervalo ([0,2] ), (x = sqrt {2} ) es una posibilidad para un punto crítico, pero (x = - sqrt { 2} ) no lo es. Por lo tanto, verificamos si ( sqrt {2} ) es una solución de la Ecuación ref {ex5eq1}. Dado que (x = sqrt {2} ) es una solución de la ecuación ref {ex5eq1}, concluimos que ( sqrt {2} ) es el único punto crítico de (A (x) ) en el intervalo ([0,2] ).

Por lo tanto, (A (x) ) debe tener un máximo absoluto en el punto crítico (x = sqrt {2} ). Para determinar las dimensiones del rectángulo, necesitamos encontrar la longitud (L ) y el ancho (W ). Si (x = sqrt {2} ) entonces

[y = sqrt {1− dfrac {( sqrt {2}) ^ 2} {4}} = sqrt {1− dfrac {1} {2}} = dfrac {1} { sqrt {2}}. Nonumber ]

Por lo tanto, las dimensiones del rectángulo son (L = 2x = 2 sqrt {2} ) y (W = 2y = dfrac {2} { sqrt {2}} = sqrt {2} ). El área de este rectángulo es (A = LW = (2 sqrt {2}) ( sqrt {2}) = 4. )

Ejercicio ( PageIndex {5} )

Modifique la función de área (A ) si el rectángulo se va a inscribir en el círculo unitario (x ^ 2 + y2 ^ = 1 ). ¿Cuál es el dominio de consideración?

Insinuación

Si ((x, y) ) es el vértice del cuadrado que se encuentra en el primer cuadrante, entonces el área del cuadrado es (A = (2x) (2y) = 4xy. )

Respuesta

(A (x) = 4x sqrt {1 − x ^ 2}. ) El dominio de consideración es ([0,1] ).

Solución de problemas de optimización cuando el intervalo no está cerrado o no está acotado

En los ejemplos anteriores, consideramos funciones en dominios cerrados y delimitados. En consecuencia, por el teorema del valor extremo, se nos garantizó que las funciones tenían extremos absolutos. Consideremos ahora funciones para las que el dominio no es cerrado ni acotado.

Muchas funciones todavía tienen al menos un extremo absoluto, incluso si el dominio no está cerrado o el dominio no está acotado. Por ejemplo, la función (f (x) = x ^ 2 + 4 ) sobre ((- ∞, ∞) ) tiene un mínimo absoluto de (4 ) en (x = 0 ). Por lo tanto, todavía podemos considerar funciones sobre dominios ilimitados o intervalos abiertos y determinar si tienen extremos absolutos. En el siguiente ejemplo, intentamos minimizar una función en un dominio ilimitado. Veremos que, aunque el dominio de consideración es ((0, ∞), ) la función tiene un mínimo absoluto.

En el siguiente ejemplo, buscamos construir una caja de menor área de superficie con un volumen prescrito. No es difícil mostrar que para una caja con tapa cerrada, por simetría, entre todas las cajas con un volumen específico, un cubo tendrá el área de superficie más pequeña. En consecuencia, consideramos el problema modificado de determinar qué caja abierta con un volumen específico tiene el área de superficie más pequeña.

Ejemplo ( PageIndex {6} ): Minimizar el área de superficie

Se construirá una caja rectangular con una base cuadrada, una parte superior abierta y un volumen de (216 , text {in} ^ 3 ). ¿Cuáles deben ser las dimensiones de la caja para minimizar el área de superficie de la caja? ¿Cuál es la superficie mínima?

Solución

Paso 1: Dibuja una caja rectangular e introduce la variable (x ) para representar la longitud de cada lado de la base cuadrada; deje que (y ) represente la altura de la caja. Sea (S ) el área de la superficie de la caja abierta.

Paso 2: Necesitamos minimizar el área de superficie. Por lo tanto, necesitamos minimizar (S ).

Paso 3: Dado que la caja tiene la parte superior abierta, solo necesitamos determinar el área de los cuatro lados verticales y la base. El área de cada uno de los cuatro lados verticales es (x⋅y. ) El área de la base es (x ^ 2 ). Por lo tanto, el área de la superficie de la caja es

(S = 4xy + x ^ 2 ).

Paso 4: Dado que el volumen de esta caja es (x ^ 2y ) y el volumen se da como (216 , text {in} ^ 3 ), la ecuación de restricción es

(x ^ 2y = 216 ).

Resolviendo la ecuación de restricción para (y ), tenemos (y = dfrac {216} {x ^ 2} ). Por lo tanto, podemos escribir el área de la superficie como una función de (x ) solamente:

[S (x) = 4x left ( dfrac {216} {x ^ 2} right) + x ^ 2. Nonumber ]

Por lo tanto, (S (x) = dfrac {864} {x} + x ^ 2 ).

Paso 5: Dado que estamos requiriendo que (x ^ 2y = 216 ), no podemos tener (x = 0 ). Por lo tanto, necesitamos (x> 0 ). Por otro lado, se permite que (x ) tenga cualquier valor positivo. Tenga en cuenta que a medida que (x ) se vuelve grande, la altura de la caja (y ) se vuelve correspondientemente pequeña de modo que (x ^ 2y = 216 ). De manera similar, a medida que (x ) se vuelve pequeño, la altura de la caja se vuelve correspondientemente grande. Concluimos que el dominio es el intervalo abierto e ilimitado ((0, ∞) ). Tenga en cuenta que, a diferencia de los ejemplos anteriores, no podemos reducir nuestro problema a buscar un máximo absoluto o un mínimo absoluto en un intervalo cerrado y acotado. Sin embargo, en el siguiente paso, descubrimos por qué esta función debe tener un mínimo absoluto en el intervalo ((0, ∞). )

Paso 6: Note que como (x → 0 ^ +, , S (x) → ∞. ) También, como (x → ∞, , S (x) → ∞ ). Dado que (S ) es una función continua que se acerca al infinito en los extremos, debe tener un mínimo absoluto en algún (x∈ (0, ∞) ). Este mínimo debe ocurrir en un punto crítico de (S ). La derivada es

[S ′ ​​(x) = - dfrac {864} {x ^ 2} + 2x. Nonumber ]

Por lo tanto, (S ′ (x) = 0 ) cuando (2x = dfrac {864} {x ^ 2} ). Resolviendo esta ecuación para (x ), obtenemos (x ^ 3 = 432 ), entonces (x = sqrt [3] {432} = 6 sqrt [3] {2}. ) Dado que esto es el único punto crítico de (S ), el mínimo absoluto debe ocurrir en (x = 6 sqrt [3] {2} ) (ver Figura ( PageIndex {9} )).

Cuando (x = 6 sqrt [3] {2} ), (y = dfrac {216} {(6 sqrt [3] {2}) ^ 2} = 3 sqrt [3] {2 } , text {in.} ) Por lo tanto, las dimensiones de la caja deben ser (x = 6 sqrt [3] {2} , text {in.} ) y (y = 3 sqrt [3] {2} , text {in.} ) Con estas dimensiones, el área de la superficie es

[S (6 sqrt [3] {2}) = dfrac {864} {6 sqrt [3] {2}} + (6 sqrt [3] {2}) ^ 2 = 108 sqrt [ 3] {4} , text {in} ^ 2 nonumber ]

Ejercicio ( PageIndex {6} )

Considere la misma caja abierta, que debe tener un volumen (216 , text {in} ^ 3 ). Suponga que el costo del material para la base es (20 ¢ / text {in} ^ 2 ) y el costo del material para los lados es (30 ¢ / text {in} ^ 2 ) y nosotros están tratando de minimizar el costo de esta caja. Escribe el costo en función de las longitudes de los lados de la base. (Sea (x ) la longitud del lado de la base y (y ) la altura de la caja).

Insinuación

Si el costo de uno de los lados es (30 ¢ / text {in} ^ 2, ) el costo de ese lado es (0.30xy ) dólares.

Respuesta

(c (x) = dfrac {259.2} {x} + 0.2x ^ 2 ) dólares

Conceptos clave

  • Para resolver un problema de optimización, comience dibujando una imagen e introduciendo variables.
  • Encuentre una ecuación que relacione las variables.
  • Encuentre una función de una variable para describir la cantidad que se minimizará o maximizará.
  • Busque puntos críticos para ubicar los extremos locales.

Glosario

problemas de optimización
problemas que se resuelven al encontrar el valor máximo o mínimo de una función

Contribuyentes y atribuciones

  • Gilbert Strang (MIT) y Edwin “Jed” Herman (Harvey Mudd) con muchos autores contribuyentes. Este contenido de OpenStax tiene una licencia CC-BY-SA-NC 4.0. Descárguelo gratis en http://cnx.org.


Optimización de métodos lineales (desarrollador)

L-BFGS es un algoritmo de optimización de la familia de métodos cuasi-Newton para resolver los problemas de optimización de la forma $ min_ < wv in R ^ d> f ( wv) $. El método L-BFGS aproxima la función objetivo localmente como una cuadrática sin evaluar las segundas derivadas parciales de la función objetivo para construir la matriz de Hesse. La matriz hessiana se aproxima a las evaluaciones de gradiente anteriores, por lo que no hay ningún problema de escalabilidad vertical (el número de características de entrenamiento) a diferencia de calcular la matriz hessiana explícitamente en el método Newton & # 8217s. Como resultado, L-BFGS a menudo logra una convergencia más rápida en comparación con otras optimizaciones de primer orden.

Orthant-Wise Limited-memory Quasi-Newton (OWL-QN) es una extensión de L-BFGS que puede manejar eficazmente la regularización de la red elástica y L1.

El solucionador MLlib L-BFGS llama a la implementación correspondiente en un abrir y cerrar de ojos.


Transcripción de la presentación

Aplicaciones de la diferenciación Sección 4.7 Problemas de optimización

Aplicaciones de la diferenciación • Los métodos que hemos aprendido en este capítulo para encontrar valores extremos tienen aplicaciones prácticas en muchas áreas de la vida. • Una persona de negocios quiere minimizar los costos y maximizar las ganancias. • Un viajero quiere minimizar el tiempo de transporte. • El Principio de Fermat en óptica establece que la luz sigue el camino que toma menos tiempo.

Problemas de optimización • En esta sección resolvemos problemas tales como: • Maximizar áreas, volúmenes y ganancias • Minimizar distancias, tiempos y costos

Problemas de optimización • Al resolver estos problemas prácticos, el mayor desafío suele ser convertir el problema verbal en un problema de optimización matemática, configurando la función que se va a maximizar o minimizar. • Por lo tanto, hay seis pasos involucrados en la resolución de problemas de optimización. • Estos son los siguientes.

1. Comprender el problema • Lea el problema con atención hasta que se entienda claramente. • Pregúntese: • ¿Qué es lo desconocido? • ¿Cuáles son las cantidades dadas? • ¿Cuáles son las condiciones dadas?

3. Introduce la notación • Asignar un símbolo a la cantidad a maximizar o minimizar. • Llamémoslo Q por ahora. 2. Dibujar un diagrama • En la mayoría de los problemas, es útil dibujar un diagrama e identificar las cantidades dadas y requeridas en el diagrama.

4. Exprese Q en términos de las variables • Exprese Q en términos de algunos de los otros símbolos del Paso 3. 3. Introduzca la notación • Además, seleccione símbolos (a, b, c,..., X, y) para otras cantidades desconocidas y etiquete el diagrama con estos símbolos . • Puede ser útil utilizar las iniciales como símbolos sugerentes. • Algunos ejemplos son: A para área, h para altura yt para tiempo.

5. Exprese Q en términos de una variable • Si Q se ha expresado en función de más de una variable en el Paso 4, use la información proporcionada para encontrar relaciones, en forma de ecuaciones, entre estas variables. • Luego, use las ecuaciones para eliminar todas las variables menos una en la expresión de Q. • Por lo tanto, Q se expresará como una función de una variable x, digamos, Q = f (x). • Escriba el dominio de esta función.

6. Encuentra los abdominales. Max./Min de f • Utilice los métodos de las Secciones 4.1 y 4.3 para encontrar el valor absoluto máximo o mínimo de f. • En particular, si el dominio de f es un intervalo cerrado, entonces se puede usar el Método de intervalo cerrado de la Sección 4.1.

Problemas de optimización - Ej. 1 • Un agricultor tiene 2400 pies de cerca y quiere cercar un campo rectangular que bordea un río recto. No necesita vallas a lo largo del río. • ¿Cuáles son las dimensiones del campo que tiene el área más grande? • Para tener una idea de lo que está sucediendo en el problema, experimentemos con algunos casos especiales.

Problemas de optimización - Ej. 1 • Aquí hay tres formas posibles de colocar los 2400 pies de cerca.

Problemas de optimización - Ej. 1 • Vemos que cuando probamos campos anchos y poco profundos o campos estrechos y profundos, obtenemos áreas relativamente pequeñas. • Parece plausible que haya alguna configuración intermedia que produzca el área más grande.

Problemas de optimización - Ej. 1 • La figura ilustra el caso general. • Deseamos maximizar el área A del rectángulo. • Sean xey la profundidad y el ancho del rectángulo (en pies). • Entonces, expresamos A en términos de xey: A = xy

Problemas de optimización - Ej. 1 • Queremos expresar A en función de una sola variable. • Entonces, eliminamos y expresándolo en términos de x. • Para hacer esto, usamos la información dada de que la longitud total de la cerca es 2400 pies. • Por lo tanto, 2x + y = 2400

Problemas de optimización - Ej. 1 • De esa ecuación, tenemos: y = 2400 - 2x • Esto da: A = x (2400 - 2x) = 2400x - 2x2 • Note que x ≥ 0 yx ≤ 1200 (de lo contrario A & lt 0).

Problemas de optimización - Ej. 1 • Entonces, la función que deseamos maximizar es: A (x) = 2400x - 2x2 0 ≤x ≤ 1200 • La derivada es: A '(x) = 2400 - 4x • Entonces, para encontrar los números críticos, resolvemos : 2400 - 4x = 0 • Esto da: x = 600 • No hay puntos singulares.

Problemas de optimización - Ej. 1 • El valor máximo de A debe ocurrir en ese número crítico o en un punto final del intervalo. • A (0) = 0 A (600) = 720,000 y A (1200) = 0 • Entonces, el método de intervalo cerrado da el valor máximo como: A (600) = 720,000

Problemas de optimización - Ej. 1 • Alternativamente, podríamos haber observado que A ’’ (x) = - 4 & lt 0 para todo x • Entonces, A es siempre cóncava hacia abajo y el máximo local en x = 600 debe ser un máximo absoluto.

Problemas de optimización - Ej. 1 • Por lo tanto, el campo rectangular debe tener: • 600 pies de profundidad • 1200 pies de ancho

Problemas de optimización - Ej. 2 • Se debe hacer una lata cilíndrica para contener 1 L de aceite. • Encuentre las dimensiones que minimizarán el costo del metal para fabricar la lata.

Problemas de optimización - Ej. 2 • Dibuje el diagrama como en esta figura, donde r es el radio y h la altura (ambos en centímetros).

Problemas de optimización - Ej. 2 • Para minimizar el costo del metal, minimizamos el área de superficie total del cilindro (superior, inferior y laterales).

Problemas de optimización - Ej. 2 • Vemos que los lados están formados por una hoja rectangular de dimensiones 2πr y h.

Problemas de optimización - Ej. 2 • Entonces, el área de la superficie es: A = 2πr2 + 2πrh

Problemas de optimización - Ej. 2 • Para eliminar h, usamos el hecho de que el volumen se da como 1 L, que tomamos como 1000 cm3. • Por lo tanto, πr2h = 1000 • Esto da h = 1000 / (πr2)

Problemas de optimización - Ej. 2 • Sustituyendo esto en la expresión por A da: • Entonces, la función que queremos minimizar es:

Problemas de optimización - Ej. 2 • Para encontrar los números críticos, diferenciamos: • Entonces, A ’(r) = 0 cuando πr3 = 500 • Entonces, el único número crítico es:

Problemas de optimización - Ej. 2 • Como el dominio de A es (0, ), no podemos usar el argumento del Ejemplo 1 con respecto a los puntos finales. • Sin embargo, podemos observar que A ’(r) & lt 0 para y A’ (r) & gt 0 para • Entonces, A es decreciente para todo r a la izquierda del número crítico y aumenta para todo r a la derecha. • Por tanto, debe dar lugar a un mínimo absoluto.

Problemas de optimización - Ej. 2 • Alternativamente, podríamos argumentar que A (r) → ∞ cuando r → 0+ y A (r) → ∞ como r → ∞. • Entonces, debe haber un valor mínimo de A (r), que debe ocurrir en el número crítico.

Problemas de optimización - Ej. 2 • El valor de h correspondiente a es:

Problemas de optimización - Ej. 2 • Por lo tanto, para minimizar el costo de la lata, • El radio debe ser cm. • La altura debe ser igual al doble del radio, es decir, el diámetro.

Observación 1 • El argumento utilizado en el ejemplo para justificar el mínimo absoluto es una variante de la Prueba de la primera derivada, que se aplica solo a los valores máximos o mínimos locales. • Se indica a continuación para referencia futura.

First Deriv. Prueba de Abs. Extrema • Suponga que c es un número crítico de una función continua f definida en un intervalo. • Si f ’(x) & gt 0 para todo x & ltc y f’ (x) & lt 0 para todo x & gt c, entonces f (c) es el valor máximo absoluto de f. • Si f ’(x) & lt 0 para todo x & ltc y si f’ (x) & gt 0 para todo x & gt c, entonces f (c) es el valor mínimo absoluto de f.

Observación 2 • Un método alternativo para resolver problemas de optimización es utilizar la diferenciación implícita. • Veamos el ejemplo nuevamente para ilustrar el método.

Diferenciación implícita • Trabajamos con las mismas ecuaciones A = 2πr2 + 2πrh πr2h = 100 • Sin embargo, en lugar de eliminar h, diferenciamos implícitamente ambas ecuaciones con respecto a r: A ’= 4πr + 2πh + 2πrh’ 2πrh + πr2h ’= 0

Diferenciación implícita • El mínimo ocurre en un número crítico. • Entonces, establecemos A ’= 0, simplificamos y llegamos a las ecuaciones 2r + h + rh’ = 0 2h + rh ’= 0 • La resta da: 2r - h = 0 o h = 2r

Problemas de optimización - Ej. 3 • Encuentra el punto de la parábola y2 = 2x que está más cerca del punto (1, 4).

Problemas de optimización - Ej. 3 • La distancia entre el punto (1, 4) y el punto (x, y) es: • Sin embargo, si (x, y) se encuentra en la parábola, entonces x = ½ y2. • Entonces, la expresión para d se convierte en:

Problemas de optimización - Ej. 3 • Alternativamente, podríamos haber sustituido para obtener d en términos de x solo.

Problemas de optimización - Ej. 3 • En lugar de minimizar d, minimizamos su cuadrado: • Debe convencerse de que el mínimo de d ocurre en el mismo punto que el mínimo de d 2. • Sin embargo, es más fácil trabajar con d 2.

Problemas de optimización - Ej. 3 • Al diferenciar, obtenemos: • Entonces, f ’(y) = 0 cuando y = 2.

Problemas de optimización - Ej. 3 • Observe que f '(y) & lt 0 cuando y & lt 2 y f' (y) & gt 0 cuando y & gt 2. • Entonces, por la prueba de la primera derivada para valores extremos absolutos, el mínimo absoluto ocurre cuando y = 2. • Alternativamente, podríamos decir simplemente que, debido a la naturaleza geométrica del problema, es obvio que hay un punto más cercano pero no un punto más lejano.

Problemas de optimización - Ej. 3 • El valor correspondiente de x es: x = ½ y2 = 2 • Por lo tanto, el punto en y2 = 2x más cercano a (1, 4) es (2, 2).

Problemas de optimización - Ej. 4 • Un hombre lanza su bote desde el punto A en la orilla de un río recto, de 3 km de ancho, y quiere llegar al punto B (8 km río abajo en la orilla opuesta) lo más rápido posible.

Problemas de optimización - Ej. 4 • Podría proceder de tres maneras: • Remar con su bote directamente a través del río hasta el punto C y luego correr a B • Remar directamente a B • Remar a algún punto D entre C y B y luego correr a B

Problemas de optimización - Ej. 4 • Si puede remar 6 km / hy correr 8 km / h, ¿dónde debería aterrizar para llegar a B lo antes posible? • Suponemos que la velocidad del agua es insignificante en comparación con la velocidad a la que rema.

Problemas de optimización - Ej. 4 • Si hacemos que x sea la distancia de C a D, entonces: • La distancia de carrera es: | DB | = 8 - x • El Teorema de Pitágoras da la distancia de remo como: | AD | =

Problemas de optimización - Ej. 4 • Usamos la ecuación • Entonces, el tiempo de remo es: • El tiempo de ejecución es: (8 - x) / 8 • Entonces, el tiempo total T en función de x es:

Problemas de optimización - Ej. 4 • El dominio de esta función T es [0, 8]. • Observe que si x = 0, rema a C, y si x = 8, rema directamente a B. • La derivada de T es:


Nuevos idiomas y mejoras específicas de idiomas

  • La opción de línea de comandos -feliminate-unused-debug-types se ha vuelto a habilitar de forma predeterminada, al igual que para los otros idiomas, lo que lleva a una reducción en el tamaño de la información de depuración del 12,5% y más para los casos relevantes, así como a una pequeña compilación acelerada.

Familia C

  • Se ha agregado un nuevo incorporado, __builtin_assume_aligned, a través del cual el compilador puede recibir sugerencias sobre la alineación del puntero y puede usarlo para mejorar el código generado.
  • Se agregó una nueva opción de advertencia -Wunused-local-typedefs para C, C ++, Objective-C y Objective-C ++. Esta advertencia diagnostica las definiciones de tipo definidas localmente en una función y, por lo demás, no se utilizan.
  • Se agregó una nueva opción de línea de comandos experimental -ftrack-macro-expansion para C, C ++, Objective-C, Objective-C ++ y Fortran. Permite al compilador emitir un diagnóstico sobre la pila de expansión de macro actual cuando se produce un error de compilación en una expansión de macro.

Se ha agregado soporte experimental para memoria transaccional. Incluye soporte en el compilador, así como una biblioteca en tiempo de ejecución de soporte llamada libitm. Para compilar código con construcciones de memoria transaccional, use la opción -fgnu-tm.

Actualmente, el soporte está disponible para las plataformas Alpha, ARM, PowerPC, SH, SPARC y x86 de 32 bits / 64 bits.

Para obtener más detalles sobre la memoria transaccional, consulte GCC WiKi.

Se ha agregado soporte para operaciones atómicas que especifican el modelo de memoria C ++ 11 / C11. Estas nuevas rutinas __atómicas reemplazan las rutinas integradas de __sync existentes.

El soporte atómico también está disponible para bloques de memoria. Se utilizarán instrucciones sin bloqueo si un bloque de memoria tiene el mismo tamaño y alineación que un tipo de entero admitido. Las operaciones atómicas que no tienen soporte sin bloqueo se dejan como llamadas a funciones. Un conjunto de funciones de biblioteca está disponible en la wiki atómica de GCC en la sección "Biblioteca Atómica Externa".

Para obtener más detalles sobre los modelos y las características de la memoria, consulte la wiki atómica.

  • Hay soporte para algunas características más de la revisión C11 del estándar ISO C. GCC ahora acepta las opciones -std = c11 y -std = gnu11, además de las anteriores -std = c1x y -std = gnu1x.
    • Cadenas Unicode (anteriormente admitidas solo con opciones como -std = gnu11, ahora compatibles con -std = c11) y las macros predefinidas __STDC_UTF_16__ y __STDC_UTF_32__
    • Funciones de no retorno (_Noreturn y & ltstdnoreturn.h & gt).
    • Soporte de alineación (_Alignas, _Alignof, max_align_t, & ltstdalign.h & gt).
    • Se proporciona una función incorporada __builtin_complex para admitir la implementación de la biblioteca C de la familia de macros CMPLX.
    • G ++ ahora acepta las opciones -std = c ++ 11, -std = gnu ++ 11 y -Wc ++ 11-compat, que son equivalentes a -std = c ++ 0x, -std = gnu ++ 0x, y -Wc ++ 0x-compat, respectivamente.
    • G ++ ahora implementa la sintaxis de amigos extendida de C ++ 11:

    Tenga en cuenta que esto no debería causar ningún cambio de comportamiento para los temporales de tipos con destructores no triviales, ya que ya están destruidos al final de la expresión completa, el cambio es que ahora también se libera el almacenamiento.

    Biblioteca en tiempo de ejecución (libstdc ++)

    • Soporte experimental mejorado para el nuevo estándar ISO C ++, C ++ 11, que incluye:
      • usando no, excepto en la mayor parte de la biblioteca
      • implementaciones de pointer_traits, allocator_traits y scoped_allocator_adaptor
      • construcción de asignador de usos para tupla
      • el vector cumple con los requisitos de contenedor consciente del asignador
      • reemplazando monotonic_clock con Steady_clock
      • habilitar la biblioteca de soporte de subprocesos en la mayoría de los destinos POSIX
      • muchas pequeñas mejoras para ajustarse al FDIS.

      Fortran

      • Se ha agregado el indicador de compilación -fstack-arrays, lo que hace que todas las matrices locales se coloquen en la memoria de la pila. Para algunos programas, esto mejorará significativamente el rendimiento. Si su programa utiliza matrices locales muy grandes, es posible que tenga que ampliar sus límites de tiempo de ejecución para la memoria de pila.
      • El indicador -Ofast ahora también implica -fno-protect-parens y -fstack-arrays.
      • Las optimizaciones de front-end ahora se pueden seleccionar con la opción -ffrontend-optimizar y deseleccionarlas con la opción -fno-frontend-optimizar.
      • Cuando la optimización de front-end elimina una llamada de función, -Wfunction-elimination advierte sobre eso.
      • Al realizar la optimización de front-end, la opción -faggressive-function-elimination permite la eliminación de llamadas de función duplicadas incluso para funciones impuras.
      • Se ha agregado el indicador -Wreal-q-constante, que advierte si se han especificado literales de punto flotante usando q (como 1.0q0), el marcador q ahora se admite como una extensión del proveedor para denotar precisión cuádruple (REAL (16) o , si no está disponible, REAL (10)). Considere usar un parámetro de tipo (como en 1.0_qp) en su lugar, que se puede obtener a través de SELECTED_REAL_KIND.
      • Se ha eliminado la variable de entorno GFORTRAN_USE_STDERR. GNU Fortran ahora siempre imprime mensajes de error en error estándar. Si desea redirigir el error estándar, consulte el manual de su sistema operativo, shell, entorno por lotes, etc., según corresponda.
      • Se han eliminado la opción -fdump-core y la variable de entorno GFORTRAN_ERROR_DUMPCORE. Cuando se encuentra con un error grave, gfortran ahora siempre abortará el programa. Si se genera un volcado de núcleo depende de la configuración del entorno del usuario, consulte la configuración ulimit -c para shells POSIX, limite el tamaño de coredumpsize para shells C y la configuración de volcados de modo de usuario WER en Windows.
      • La opción -fbacktrace ahora está habilitada de forma predeterminada. Cuando se encuentra con un error fatal, gfortran intentará imprimir un retroceso al error estándar antes de abortar. Se puede desactivar con -fno-backtrace. Nota: En los destinos POSIX con la utilidad addr2line de GNU binutils, GNU Fortran puede imprimir un seguimiento con el nombre de la función, el nombre del archivo, la información del número de línea además de las direcciones; de lo contrario, solo se imprimen las direcciones. :
        • Ahora se admiten nombres de interfaz genéricos que tienen el mismo nombre que los tipos derivados, lo que permite escribir funciones de constructor. Tenga en cuenta que Fortran no admite funciones de constructor estáticas, solo están disponibles la inicialización predeterminada o una inicialización explícita de constructor de estructura. Las matrices (de clase) ahora son compatibles.
        • Se ha agregado soporte para la construcción DO CONCURRENT, que permite al usuario especificar que las iteraciones de bucle individuales no tienen interdependencias. : Soporte completo de una sola imagen excepto para coarrays polimórficos. Además, se ha agregado soporte preliminar para múltiples imágenes a través de una biblioteca de comunicación coarray basada en MPI. Nota: La versión de la biblioteca aún no se puede utilizar ya que aún no es posible el acceso a coarray remoto.
        • El nuevo indicador -std = f2008ts permite programas que se espera que cumplan con el estándar Fortran 2008 y el borrador de la Especificación Técnica (TS) 29113 sobre Interoperabilidad adicional de Fortran con C.
        • El atributo OPCIONAL ahora está permitido para argumentos ficticios de procedimientos BIND (C).
        • Se ha agregado el RANK intrínseco.
        • La implementación del atributo ASYNCHRONOUS en GCC es compatible con el borrador candidato de TS 29113 (desde GCC 4.6).
        • GCC 4.7 implementa el estándar de lenguaje Go 1. El soporte de la biblioteca en 4.7.0 no está del todo completo, debido al tiempo de lanzamiento. La versión 4.7.1 incluye soporte completo para Go 1. La biblioteca Go es de la versión Go 1.0.1.
        • Go ha sido probado en plataformas GNU / Linux y Solaris. También puede funcionar en otras plataformas.

        Hay 3 hojas de ejemplos, cada una con 11 preguntas, en este único archivo: exsheetoc.pdf. Debería recibir una supervisión en cada hoja de ejemplos.

        Puede comentar o hacer preguntas en la página de discusión y también al final de cada una de las publicaciones del blog. Me esforzaré por responder preguntas. Cuando comente, puede hacerlo de forma anónima si lo desea. Simplemente dé cualquier nombre y deje el cuadro de dirección de correo electrónico en blanco. También puede enviarme un correo electrónico con preguntas, sugerencias o si cree que ha descubierto un error en las notas.


        1 respuesta 1

        problemas al migrar el proyecto c ++ / cli de .net 4.7 a .netcore 3.1

        He probado en mi lado: migre un proyecto net framework clr al proyecto net core clr mediante el documento de orientación sin ningún error.

        Por lo tanto, pruebe las siguientes sugerencias:

        En su lugar, asegúrese de utilizar estas propiedades en el archivo xxx.vcxproj.

        1) cierre VS Instance, elimine la carpeta oculta .vs, carpetas de salida como Debug o x64 (tanto en la carpeta de la solución como en la carpeta del proyecto)

        2) Haga clic con el botón derecho en el proyecto c ++ - & gtPropiedades- & gtC / C ++- & gtMejoramiento- Optimización de & gtset a deshabilitado (/ Od)

        Cambio de generación de código de tiempo de enlace a / LTCG por proyecto Propiedades - & gt Enlazador - & gt Mejoramiento.

        además, intente crear un nuevo proyecto C ++ Clr Net Core predeterminado y luego pruebe si se puede construir correctamente.

        Y si es así, puede intentar migrar su antiguo proyecto al nuevo proyecto.

        Además, puede compartir una muestra mínima y reproducible con nosotros para que podamos solucionar su problema más rápidamente.

        La razón es que usó el nodo xml CompileAsManaged en su archivo xxx.vcxproj, y para su proyecto net core clr no necesita ese nodo. Con él, pierde la referencia de ensamblaje.

        Realmente, ese nodo entra en conflicto con su proyecto debido a algunas razones, ya sea que su valor sea verdadero o falso.


        Contenido

        Optimización matemática Editar

        En términos de optimización matemática, la programación dinámica generalmente se refiere a simplificar una decisión dividiéndola en una secuencia de pasos de decisión a lo largo del tiempo. Esto se hace definiendo una secuencia de funciones de valor V1, V2, . Vnorte tomando y como un argumento que representa el Expresar del sistema a veces I de 1 a norte. La definición de Vnorte(y) es el valor obtenido en el estado y a ultimo momento norte. Los valores VI en épocas anteriores I = norte −1, norte - 2,. 2, 1 se puede encontrar trabajando hacia atrás, usando una relación recursiva llamada ecuación de Bellman. Para I = 2, . norte, VI−1 en cualquier estado y se calcula a partir de VI maximizando una función simple (generalmente la suma) de la ganancia de una decisión en el momento I - 1 y la función VI en el nuevo estado del sistema si se toma esta decisión. Desde VI ya se ha calculado para los estados necesarios, la operación anterior produce VI−1 para esos estados. Finalmente, V1 en el estado inicial del sistema es el valor de la solución óptima. Los valores óptimos de las variables de decisión se pueden recuperar, uno por uno, rastreando los cálculos ya realizados.

        Teoría de control Editar

        Alternativamente, el proceso continuo puede aproximarse mediante un sistema discreto, lo que conduce a una siguiente relación de recurrencia análoga a la ecuación de Hamilton-Jacobi-Bellman:

        Ejemplo de economía: el problema de ahorro óptimo de Ramsey Editar

        En economía, el objetivo es generalmente maximizar (en lugar de minimizar) alguna función dinámica de bienestar social. En el problema de Ramsey, esta función relaciona las cantidades de consumo con los niveles de utilidad. Hablando libremente, el planificador se enfrenta a la compensación entre el consumo contemporáneo y el consumo futuro (a través de la inversión en el capital social que se utiliza en la producción), lo que se conoce como elección intertemporal. El consumo futuro se descuenta a una tasa constante β ∈ (0, 1) < displaystyle beta in (0,1)>. Una aproximación discreta a la ecuación de transición del capital viene dada por

        El valor de cualquier cantidad de capital en cualquier momento anterior se puede calcular mediante inducción hacia atrás utilizando la ecuación de Bellman. En este problema, para cada t = 0, 1, 2,…, T < displaystyle t = 0,1,2, ldots, T>, la ecuación de Bellman es

        Trabajando hacia atrás, se puede mostrar que la función de valor en el tiempo t = T - j < displaystyle t = T-j> es

        que se puede simplificar a

        Vemos que es óptimo consumir una fracción mayor de la riqueza actual a medida que uno envejece, consumiendo finalmente toda la riqueza restante en el período T, el último período de la vida.

        Programación informática Editar

        Hay dos atributos clave que debe tener un problema para que la programación dinámica sea aplicable: subestructura óptima y subproblemas superpuestos. Si un problema puede resolverse combinando soluciones óptimas para no superpuesto subproblemas, la estrategia se llama "divide y vencerás" en su lugar. [1] Esta es la razón por la que la clasificación por combinación y la clasificación rápida no se clasifican como problemas de programación dinámica.

        Subestructura óptima significa que la solución a un problema de optimización dado se puede obtener mediante la combinación de soluciones óptimas a sus subproblemas. Estas subestructuras óptimas suelen describirse mediante recursividad. Por ejemplo, dado un gráfico G = (V, E), el camino mas corto pag desde un vértice tu a un vértice v exhibe una subestructura óptima: tome cualquier vértice intermedio w en este camino más corto pag. Si pag es realmente el camino más corto, entonces se puede dividir en subrutas pag1 de tu a w y pag2 de w a v de tal manera que estos, a su vez, son de hecho los caminos más cortos entre los vértices correspondientes (por el simple argumento de cortar y pegar descrito en Introducción a los algoritmos). Por lo tanto, se puede formular fácilmente la solución para encontrar los caminos más cortos de manera recursiva, que es lo que hace el algoritmo Bellman-Ford o el algoritmo Floyd-Warshall.

        Superposición subproblemas significa que el espacio de subproblemas debe ser pequeño, es decir, cualquier algoritmo recursivo que resuelva el problema debería resolver los mismos subproblemas una y otra vez, en lugar de generar nuevos subproblemas. Por ejemplo, considere la formulación recursiva para generar la serie de Fibonacci: FI = FI−1 + FI−2, con estuche base F1 = F2 = 1. Entonces F43 = F42 + F41, y F42 = F41 + F40. Ahora F41 se está resolviendo en los subárboles recursivos de ambos F43 así como F42. Aunque el número total de subproblemas es realmente pequeño (solo 43 de ellos), terminamos resolviendo los mismos problemas una y otra vez si adoptamos una solución recursiva ingenua como esta. La programación dinámica tiene en cuenta este hecho y resuelve cada subproblema solo una vez.

        Esto se puede lograr de dos maneras: [ cita necesaria ]

        • Enfoque de arriba hacia abajo: Ésta es la consecuencia directa de la formulación recursiva de cualquier problema. Si la solución a cualquier problema puede formularse de forma recursiva utilizando la solución a sus subproblemas, y si sus subproblemas se superponen, entonces se pueden memorizar o almacenar fácilmente las soluciones a los subproblemas en una tabla. Siempre que intentamos resolver un nuevo subproblema, primero revisamos la tabla para ver si ya está resuelto. Si se ha registrado una solución, podemos usarla directamente, de lo contrario resolvemos el subproblema y agregamos su solución a la tabla.
        • Enfoque de abajo hacia arriba: Una vez que formulamos la solución a un problema de forma recursiva como en términos de sus subproblemas, podemos intentar reformular el problema de abajo hacia arriba: intente resolver los subproblemas primero y use sus soluciones para construir sobre ellos y llegar a soluciones a subproblemas mayores. Esto también se hace generalmente en forma de tabla generando iterativamente soluciones para subproblemas cada vez más grandes utilizando las soluciones para pequeños subproblemas. Por ejemplo, si ya conocemos los valores de F41 y F40, podemos calcular directamente el valor de F42.

        Algunos lenguajes de programación pueden memorizar automáticamente el resultado de una llamada a una función con un conjunto particular de argumentos, con el fin de acelerar la evaluación de la llamada por nombre (este mecanismo se conoce como llamada por necesidad). Algunos lenguajes lo hacen posible de forma portátil (por ejemplo, Scheme, Common Lisp, Perl o D). Algunos idiomas tienen incorporada la memorización automática, como Prolog y J en tabla, que admite la memorización con el METRO. adverbio. [4] En cualquier caso, esto solo es posible para una función referencialmente transparente. La memorización también se encuentra como un patrón de diseño de fácil acceso en lenguajes basados ​​en reescritura de términos como Wolfram Language.

        Bioinformática Editar

        La programación dinámica se utiliza ampliamente en bioinformática para tareas como la alineación de secuencias, el plegamiento de proteínas, la predicción de la estructura del ARN y la unión proteína-ADN. Los primeros algoritmos de programación dinámica para la unión proteína-ADN fueron desarrollados en la década de 1970 de forma independiente por Charles DeLisi en EE. UU. [5] y Georgii Gurskii y Alexander Zasedatelev en la URSS. [6] Recientemente, estos algoritmos se han vuelto muy populares en bioinformática y biología computacional, particularmente en los estudios de posicionamiento de nucleosomas y unión de factores de transcripción.

        Algoritmo de Dijkstra para el problema de la ruta más corta Editar

        Desde el punto de vista de la programación dinámica, el algoritmo de Dijkstra para el problema de la ruta más corta es un esquema de aproximación sucesiva que resuelve la ecuación funcional de programación dinámica para el problema de la ruta más corta mediante el Alcanzando método. [7] [8] [9]

        De hecho, la explicación de Dijkstra de la lógica detrás del algoritmo, [10] a saber

        es una paráfrasis del famoso Principio de Optimidad de Bellman en el contexto del problema del camino más corto.

        Secuencia de Fibonacci Editar

        Utilizando la programación dinámica en el cálculo de la norteEl miembro de la secuencia de Fibonacci mejora enormemente su rendimiento. Aquí hay una implementación ingenua, basada directamente en la definición matemática:

        Observe que si llamamos, digamos, fib (5), producimos un árbol de llamadas que llama a la función en el mismo valor muchas veces diferentes:

        1. fib (5)
        2. fib (4) + fib (3)
        3. (fib (3) + fib (2)) + (fib (2) + fib (1))
        4. ((fib (2) + fib (1)) + (fib (1) + fib (0))) + ((fib (1) + fib (0)) + fib (1))
        5. (((fib (1) + fib (0)) + fib (1)) + (fib (1) + fib (0))) + ((fib (1) + fib (0)) + fib (1) )

        En particular, fib (2) se calculó tres veces desde cero. En ejemplos más grandes, muchos más valores de fib, o subproblemas, se recalculan, lo que lleva a un algoritmo de tiempo exponencial.

        Ahora, supongamos que tenemos un objeto de mapa simple, metro, que asigna cada valor de fib que ya se ha calculado a su resultado, y modificamos nuestra función para usarlo y actualizarlo. La función resultante requiere solo O (norte) tiempo en lugar de tiempo exponencial (pero requiere O (norte) espacio):

        Esta técnica de guardar valores que ya han sido calculados se llama memorización este es el enfoque de arriba hacia abajo, ya que primero dividimos el problema en subproblemas y luego calculamos y almacenamos los valores.

        En el de abajo hacia arriba enfoque, calculamos los valores más pequeños de fib primero, luego construimos valores más grandes a partir de ellos. Este método también usa O (norte) tiempo, ya que contiene un bucle que se repite n - 1 veces, pero solo ocupa un espacio constante (O (1)), en contraste con el enfoque de arriba hacia abajo que requiere O (norte) espacio para almacenar el mapa.

        En ambos ejemplos, solo calculamos fib (2) una vez, y luego lo usamos para calcular tanto fib (4) como fib (3), en lugar de calcularlo cada vez que se evalúa cualquiera de ellos.

        Un tipo de edición de matriz equilibrada 0-1

        Considere el problema de asignar valores, ya sea cero o uno, a las posiciones de una matriz n × n, con n par, de modo que cada fila y cada columna contenga exactamente n / 2 ceros y n / 2 unos. Preguntamos cuántas asignaciones diferentes hay para un n < displaystyle n> dado. Por ejemplo, cuando n = 4, cuatro posibles soluciones son

        Hay al menos tres enfoques posibles: fuerza bruta, retroceso y programación dinámica.

        La fuerza bruta consiste en comprobar todas las asignaciones de ceros y unos y contar las que tienen filas y columnas equilibradas (n / 2 ceros y n / 2 unos). Como hay (n n / 2) n < displaystyle < tbinom >^> posibles asignaciones, esta estrategia no es práctica excepto tal vez hasta n = 6 < displaystyle n = 6>.

        El retroceso para este problema consiste en elegir algún orden de los elementos de la matriz y colocar recursivamente unos o ceros, comprobando que en cada fila y columna el número de elementos que no han sido asignados más el número de unos o ceros son ambos al menos n / 2. Si bien es más sofisticado que la fuerza bruta, este enfoque visitará todas las soluciones una vez, por lo que no será práctico para n mayor que seis, dado que el número de soluciones ya es 116,963,796,250 para n = 8, como veremos.

        Por ejemplo, en las dos primeras tablas que se muestran arriba, las secuencias de vectores serían

        El número de soluciones (secuencia A058527 en la OEIS) es

        1 , 2 , 90 , 297200 , 116963796250 , 6736218287430460752 , …

        Los enlaces a la implementación de MAPLE del enfoque de programación dinámica se pueden encontrar entre los enlaces externos.

        Tablero de ajedrez Editar

        Considere un tablero de ajedrez con norte × norte cuadrados y una función de costo c (i, j) que devuelve un costo asociado con cuadrado (i, j) ( I siendo la fila, j siendo la columna). Por ejemplo (en un tablero de ajedrez de 5 × 5),

        5 6 7 4 7 8
        4 7 6 1 1 4
        3 3 5 7 8 2
        2 6 7 0
        1 *5*
        1 2 3 4 5

        Supongamos que hay un verificador que puede comenzar en cualquier casilla del primer rango (es decir, una fila) y desea conocer el camino más corto (la suma de los costos mínimos en cada rango visitado) para llegar al último rango asumiendo el El inspector solo podía moverse diagonalmente hacia la izquierda hacia adelante, hacia la derecha en diagonal hacia adelante o hacia adelante. Es decir, un corrector en (1,3) puede moverse a (2,2), (2,3) o (2,4).

        5
        4
        3
        2 X X X
        1 o
        1 2 3 4 5

        Este problema exhibe subestructura óptima. Es decir, la solución a todo el problema se basa en soluciones a subproblemas. Definamos una función q (i, j) como

        q(I, j) = el costo mínimo para alcanzar el cuadrado (I, j).

        Comenzando en el rango ny descendiendo al rango 1, calculamos el valor de esta función para todos los cuadrados en cada rango sucesivo. Elegir el cuadrado que tiene el valor mínimo en cada rango nos da el camino más corto entre el rango n y el rango 1.

        La función q (i, j) es igual al costo mínimo para llegar a cualquiera de los tres cuadrados debajo de ella (ya que esos son los únicos cuadrados que pueden alcanzarlo) más c (i, j). Por ejemplo:

        5
        4 A
        3 B C D
        2
        1
        1 2 3 4 5
        q (A) = mínimo (q (B), q (C), q (D)) + c (A)

        Ahora, definamos q (i, j) en términos algo más generales:

        La primera línea de esta ecuación trata con un tablero modelado como cuadrados indexados en 1 en el límite más bajo yn en el límite más alto. La segunda línea especifica lo que sucede en el primer rango proporcionando un caso base. La tercera línea, la recursividad, es la parte importante. Representa los términos A, B, C, D del ejemplo. De esta definición podemos derivar un código recursivo sencillo para q (i, j). En el siguiente pseudocódigo, n es el tamaño de la placa, c (i, j) es la función de costo y min () devuelve el mínimo de varios valores:

        Esta función solo calcula el costo de la ruta, no la ruta real. Discutimos el camino real a continuación. Esto, como el ejemplo de los números de Fibonacci, es horriblemente lento porque también exhibe la subproblemas superpuestos atributo. Es decir, vuelve a calcular los mismos costos de ruta una y otra vez. Sin embargo, podemos calcularlo mucho más rápido de forma ascendente si almacenamos los costos de ruta en una matriz bidimensional q [i, j] en lugar de usar una función. Esto evita volver a calcular todos los valores necesarios para la matriz q [i, j] se calculan antes de tiempo sólo una vez. Los valores precalculados para (i, j) simplemente se buscan siempre que sea necesario.

        También necesitamos saber cuál es el camino más corto real. Para hacer esto, usamos otra matriz p [i, j] a matriz predecesora. Esta matriz registra la ruta a cualquier cuadrado s. El predecesor de s se modela como un desplazamiento relativo al índice (en q [i, j]) del costo de ruta precalculado de s. Para reconstruir la ruta completa, buscamos el predecesor de s, luego el predecesor de ese cuadrado, luego el predecesor de ese cuadrado, y así sucesivamente de forma recursiva, hasta llegar al cuadrado inicial. Considere el siguiente código:

        Ahora el resto es simple cuestión de encontrar el mínimo e imprimirlo.

        Alineación de secuencia Editar

        En genética, la alineación de secuencias es una aplicación importante donde la programación dinámica es esencial. [11] Normalmente, el problema consiste en transformar una secuencia en otra mediante operaciones de edición que reemplazan, insertan o eliminan un elemento. Cada operación tiene un costo asociado y el objetivo es encontrar la secuencia de ediciones con el costo total más bajo.

        El problema se puede plantear naturalmente como una recursividad, una secuencia A se edita de manera óptima en una secuencia B por:

        1. insertando el primer carácter de B y realizando una alineación óptima de A y la cola de B
        2. eliminar el primer carácter de A y realizar la alineación óptima de la cola de A y B
        3. reemplazando el primer carácter de A con el primer carácter de B, y realizando alineaciones óptimas de las colas de A y B.

        Las alineaciones parciales se pueden tabular en una matriz, donde la celda (i, j) contiene el costo de la alineación óptima de A [1..i] a B [1..j]. El costo en la celda (i, j) se puede calcular sumando el costo de las operaciones relevantes al costo de sus celdas vecinas y seleccionando el óptimo.

        Rompecabezas de la Torre de Hanoi Editar

        La Torre de Hanoi o Torres de Hanoi es un juego o rompecabezas matemático. Consta de tres varillas y varios discos de diferentes tamaños que pueden deslizarse sobre cualquier varilla. El rompecabezas comienza con los discos en una pila ordenada en orden ascendente de tamaño en una varilla, la más pequeña en la parte superior, creando así una forma cónica.

        El objetivo del rompecabezas es mover todo el montón a otra barra, obedeciendo las siguientes reglas:

        • Solo se puede mover un disco a la vez.
        • Cada movimiento consiste en tomar el disco superior de una de las varillas y deslizarlo sobre otra varilla, encima de los otros discos que ya pueden estar presentes en esa varilla.
        • No se puede colocar ningún disco encima de un disco más pequeño.

        La solución de programación dinámica consiste en resolver la ecuación funcional

        S (n, h, t) = S (n-1, h, no (h, t)) S (1, h, t) S (n-1, no (h, t), t)

        donde n denota el número de discos que se moverán, h denota la barra de inicio, t denota la barra de destino, no (h, t) denota la tercera barra (ni h ni t), "" denota concatenación y

        S (n, h, t): = solución a un problema que consta de n discos que se van a mover de la barra h a la barra t.

        Para n = 1, el problema es trivial, a saber, S (1, h, t) = "mover un disco de la barra h a la barra t" (solo queda un disco).

        El número de movimientos requeridos por esta solución es 2 norte - 1. Si el objetivo es maximizar el número de movimientos (sin ciclismo) entonces la ecuación funcional de programación dinámica es un poco más complicada y 3 norte - Se requieren 1 movimientos. [12]

        Rompecabezas de caída de huevos Editar

        La siguiente es una descripción de la instancia de este famoso rompecabezas que involucra N = 2 huevos y un edificio con H = 36 pisos: [13]

        • Un huevo que sobrevive a una caída se puede volver a utilizar.
        • Un huevo roto debe desecharse.
        • El efecto de una caída es el mismo para todos los huevos.
        • Si un huevo se rompe al caer, se rompería si se dejara caer desde una ventana más alta.
        • Si un huevo sobrevive a una caída, sobreviviría a una caída más corta.
        • No se descarta que las ventanas del primer piso rompan huevos, ni se descarta que los huevos sobrevivan a las ventanas del piso 36.

        Para derivar una ecuación funcional de programación dinámica para este rompecabezas, deje que el Expresar del modelo de programación dinámica sea un par s = (n, k), donde

        norte = número de huevos de prueba disponibles, norte = 0, 1, 2, 3, . norte − 1. k = número de pisos (consecutivos) aún por probar, k = 0, 1, 2, . H − 1.

        Por ejemplo, s = (2,6) indica que hay dos huevos de prueba disponibles y que aún no se han probado 6 pisos (consecutivos). El estado inicial del proceso es s = (norte,H) dónde norte indica el número de huevos de prueba disponibles al comienzo del experimento. El proceso termina cuando no hay más huevos de prueba (norte = 0) o cuando k = 0, lo que ocurra primero. Si la terminación ocurre en el estado s = (0,k) y k & gt 0, la prueba falló.

        W(norte,k) = número mínimo de pruebas requeridas para identificar el valor del piso crítico en el peor de los casos dado que el proceso está en estado s = (norte,k).

        Entonces se puede demostrar que [14]

        con W(norte, 0) = 0 para todos norte & gt 0 y W(1,k) = k para todos k. Es fácil resolver esta ecuación iterativamente aumentando sistemáticamente los valores de norte y k.

        Solución DP más rápida usando una parametrización diferente Editar

        Por lo tanto, f (t, n) = f (t - 1, n - 1) + f (t - 1, n) < displaystyle f (t, n) = f (t-1, n-1) + f (t-1, n)>.

        Multiplicación de cadenas de matrices Editar

        La multiplicación de cadenas de matrices es un ejemplo bien conocido que demuestra la utilidad de la programación dinámica. Por ejemplo, las aplicaciones de ingeniería a menudo tienen que multiplicar una cadena de matrices. No es de extrañar encontrar matrices de grandes dimensiones, por ejemplo 100 × 100. Por tanto, nuestra tarea es multiplicar las matrices A 1, A 2,. . . . A n < Displaystyle A_ <1>, A_ <2>. A_>. La multiplicación de matrices no es conmutativa, sino asociativa y solo podemos multiplicar dos matrices a la vez. Entonces, podemos multiplicar esta cadena de matrices de muchas formas diferentes, por ejemplo:

        y así. Existen numerosas formas de multiplicar esta cadena de matrices. Todos producirán el mismo resultado final, sin embargo, tomarán más o menos tiempo para calcular, en función de qué matrices particulares se multiplican. Si la matriz A tiene dimensiones m × n y la matriz B tiene dimensiones n × q, entonces la matriz C = A × B tendrá dimensiones m × q, y requerirá m * n * q multiplicaciones escalares (usando un algoritmo simplista de multiplicación de matrices para propósitos de ilustración).

        Por ejemplo, multipliquemos las matrices A, B y C. Supongamos que sus dimensiones son m × n, n × p y p × s, respectivamente. La matriz A × B × C tendrá un tamaño de m × sy se puede calcular de las dos formas que se muestran a continuación:

        1. Ax (B × C) Este orden de multiplicación de matrices requerirá multiplicaciones escalares nps + mns.
        2. (A × B) × C Este orden de multiplicación de matrices requerirá cálculos escalares mnp + mps.

        Supongamos que m = 10, n = 100, p = 10 ys = 1000. Entonces, la primera forma de multiplicar la cadena requerirá 1,000,000 + 1,000,000 cálculos. La segunda forma requerirá solo 10,000 + 100,000 cálculos. Obviamente, la segunda forma es más rápida y debemos multiplicar las matrices usando esa disposición de paréntesis.

        Por lo tanto, nuestra conclusión es que el orden de los paréntesis es importante y que nuestra tarea es encontrar el orden óptimo de los paréntesis.

        En este punto, tenemos varias opciones, una de las cuales es diseñar un algoritmo de programación dinámica que dividirá el problema en problemas superpuestos y calculará la disposición óptima de paréntesis. La solución de programación dinámica se presenta a continuación.

        Llamemos m [i, j] el número mínimo de multiplicaciones escalares necesarias para multiplicar una cadena de matrices desde la matriz i a la matriz j (es decir, AI ×. × Aj, es decir, i & lt = j). Dividimos la cadena en alguna matriz k, tal que i & lt = k & lt j, y tratamos de averiguar qué combinación produce el mínimo m [i, j].

        dónde k rangos desde I a j − 1.

        Esta fórmula se puede codificar como se muestra a continuación, donde el parámetro de entrada "cadena" es la cadena de matrices, es decir, A 1, A 2,. . . A n < Displaystyle A_ <1>, A_ <2>. A_> :

        Hasta ahora, hemos calculado valores para todos los posibles metro[I, j], el número mínimo de cálculos para multiplicar una cadena a partir de una matriz. I a la matriz j, y hemos registrado el "punto de división" correspondiente s[I, j]. Por ejemplo, si multiplicamos la cadena A1× A2× A3× A4 , y resulta que metro[1, 3] = 100 y s[1, 3] = 2, eso significa que la ubicación óptima de los paréntesis para las matrices 1 a 3 es (A 1 × A 2) × A 3 < displaystyle (A_ <1> times A_ <2>) times A_ <3>> y multiplicar esas matrices requerirá un cálculo escalar de 100.

        Este algoritmo producirá "tablas" metro[, ] y s[,] que tendrá entradas para todos los valores posibles de i y j. La solución final para toda la cadena es m [1, n], con la división correspondiente en s [1, n]. Desentrañar la solución será recursivo, comenzando desde la parte superior y continuando hasta llegar al caso base, es decir, la multiplicación de matrices simples.

        Por lo tanto, el siguiente paso es dividir la cadena, es decir, colocar el paréntesis donde (óptimamente) pertenecen. Para ello podríamos utilizar el siguiente algoritmo:

        Por supuesto, este algoritmo no es útil para la multiplicación real. Este algoritmo es solo una forma fácil de usar de ver cómo se ve el resultado.

        Para realmente multiplicar las matrices usando las divisiones adecuadas, necesitamos el siguiente algoritmo:

        El termino programación dinámica Richard Bellman lo utilizó originalmente en la década de 1940 para describir el proceso de resolución de problemas en el que es necesario encontrar las mejores decisiones una tras otra.Para 1953, refinó esto al significado moderno, refiriéndose específicamente a anidar problemas de decisión más pequeños dentro de decisiones más grandes, [16] y, a partir de entonces, el campo fue reconocido por el IEEE como un tema de análisis e ingeniería de sistemas. La contribución de Bellman se recuerda en el nombre de la ecuación de Bellman, un resultado central de la programación dinámica que reafirma un problema de optimización en forma recursiva.

        Bellman explica el razonamiento detrás del término programación dinámica en su autobiografía, Ojo del huracán: una autobiografía:

        Pasé el trimestre de otoño (de 1950) en RAND. Mi primera tarea fue encontrar un nombre para los procesos de decisión de varias etapas. Una pregunta interesante es: "¿De dónde viene el nombre, programación dinámica?" La década de 1950 no fue una buena época para la investigación matemática. Tuvimos un caballero muy interesante en Washington llamado Wilson. Era secretario de Defensa y, de hecho, tenía un miedo y un odio patológicos a la palabra "investigación". No estoy usando el término a la ligera, lo estoy usando con precisión. Su rostro se ensuciaría, se enrojecería y se volvería violento si la gente usara el término investigación en su presencia. Puede imaginarse cómo se sintió, entonces, sobre el término matemático. La Corporación RAND fue empleada por la Fuerza Aérea, y la Fuerza Aérea tenía a Wilson como su jefe, esencialmente. Por lo tanto, sentí que tenía que hacer algo para proteger a Wilson y la Fuerza Aérea del hecho de que realmente estaba haciendo matemáticas dentro de la Corporación RAND. ¿Qué título, qué nombre, podría elegir? En primer lugar me interesaba planificar, tomar decisiones, pensar. Pero planificación no es una buena palabra por varias razones. Por tanto, decidí utilizar la palabra "programación". Quería transmitir la idea de que esto era dinámico, esto era de varias etapas, esto variaba en el tiempo. Pensé, matemos dos pájaros de un tiro. Tomemos una palabra que tiene un significado absolutamente preciso, a saber, dinámico, en el sentido físico clásico. También tiene una propiedad muy interesante como adjetivo, y es que es imposible usar la palabra dinámica en un sentido peyorativo. Intente pensar en alguna combinación que posiblemente le dé un significado peyorativo. Es imposible. Por lo tanto, pensé que la programación dinámica era un buen nombre. Era algo a lo que ni siquiera un congresista podría objetar. Así que lo usé como paraguas para mis actividades.

        La palabra dinámica Bellman lo eligió para capturar el aspecto de los problemas que varían con el tiempo y porque sonaba impresionante. [11] La palabra programación referido al uso del método para encontrar un óptimo programa, en el sentido de un programa militar para entrenamiento o logística. Este uso es el mismo que en las frases programación lineal y programación matemática, sinónimo de optimización matemática. [17]

        Falta la explicación anterior del origen del término. Como han escrito Russell y Norvig en su libro, refiriéndose a la historia anterior: "Esto no puede ser estrictamente cierto, porque su primer artículo usando el término (Bellman, 1952) apareció antes de que Wilson se convirtiera en Secretario de Defensa en 1953". [18] Además, hay un comentario en un discurso de Harold J. Kushner, donde recuerda a Bellman. Citando a Kushner mientras habla de Bellman: "Por otro lado, cuando le hice la misma pregunta, respondió que estaba tratando de eclipsar la programación lineal de Dantzig agregando dinámica. Quizás ambas motivaciones eran ciertas".


        Asuntos

        Los procesadores convencionales tienen una gran flexibilidad en el manejo de problemas de optimización combinatoria porque procesan estos problemas usando software, pero por otro lado, no pueden resolverlos rápidamente. Por el contrario, las computadoras cuánticas actuales pueden resolver problemas de optimización combinatoria rápidamente, pero debido a que resuelven problemas basados ​​en un fenómeno físico, existe la limitación de que solo los elementos adyacentes pueden entrar en contacto, por lo que actualmente no pueden manejar una amplia gama de problemas. Como resultado, el desarrollo de una nueva arquitectura informática que pueda resolver rápidamente los problemas de optimización combinatoria del mundo real ha sido un problema (Figura 2).


        Ejercicios Encuentre un paréntesis óptimo de un producto matriz-cadena cuya secuencia de dimensiones sea 5, 10, 3, 12, 5, 50, 6. Sea R (i, j) el número de veces que MATRIZ - CADENA - ORDEN hace referencia a la entrada de la tabla m [i, j] al calcular otras entradas de la tabla. Muestre que el número total de referencias para toda la tabla es (Sugerencia: puede encontrar la identidad Demuestre que un paréntesis completo de una expresión de n elementos tiene exactamente n - 1 pares de paréntesis. 4.7: Problemas de optimización

        Comenzando con la prueba BYTE Dhyrystone 2, esta prueba computacional que se ejecuta en el sistema Ivy Bridge se benefició enormemente del soporte de Optimización de tiempo de enlace de GCC: el binario optimizado para LTO fue aproximadamente un 34% más rápido.

        Con el renderizador TTSIOD, sorprendentemente hubo una pequeña caída en el rendimiento con el binario LTO.

        El binario de Himeno no pudo beneficiarse de la característica actual de Optimización del tiempo de enlace de GCC.

        Con el perfil de prueba build-php, echamos un vistazo a la diferencia de tiempo de compilación con y sin GCC 4.7.1 LTO. Con las optimizaciones adicionales en todo el programa PHP, el tiempo de compilación aumentó en 2.8x. Si bien este aumento del tiempo de compilación puede ser un problema si se aplica LTO a las compilaciones de depuración, el aumento del uso de memoria y los tiempos de compilación no deberían ser una gran restricción para el software ampliamente distribuido listo para su lanzamiento, dadas las mejoras de rendimiento que LTO proporciona a algunas cargas de trabajo.

        C-Ray y Smallpt, programas livianos de trazado de rayos de un solo archivo, no vieron ninguna mejora en el rendimiento de los binarios optimizados para LTO para no ser una gran sorpresa.


        Ver el vídeo: Section: Optimization Problems (Septiembre 2021).