ANEXO 3E(página 135)
Optimización convexa
Otra forma de resolver un problema de optimización es usar una técnica que resuelva
las variables de Lagrange directamente y luego resuelve las variables del problema en sí.
Esta formulación se conoce como una "solución dual", y en ella los multiplicadores de
Lagrange son llamadas "variables duales". Usaremos el ejemplo resuelto previamente
para demostrar esta técnica.
La presentación hasta ahora ha estado relacionada con la solución de lo que es formalmente
llamado el "problema primario", que se estableció en la Ecuación 3A.2 como:
y su función lagrangiana es:
Si definimos una doble función, q( λ), es:
entonces el "doble problema" es encontrar:
La solución en el caso del problema dual implica dos optimizaciones separadas Problemas, El
primero requiere que tomemos un conjunto inicial de valores para x1 y x2 y luego encuentre el
valor de λ que maximiza q (λ). Luego tomamos este valor de λ y, sosteniéndolo constante,
encontramos valores de x1 y x2 que minimizan L (X1, X2, λ). Este proceso es repetido o iterado
hasta que se encuentre la solución.
En el caso de funciones objetivas convexas, como el ejemplo utilizado en este apéndice, este
procedimiento está garantizado para resolver al mismo óptimo que el primario Solución del
problema presentado anteriormente. El lector notará que en el caso de las funciones presentadas
en la Ecuación 3A.2, nosotros puede simplificar el procedimiento discutido anteriormente al
eliminar x1 y x2 del problema en total, en cuyo caso podemos encontrar el máximo de q (λ )
directamente. Si expresamos las variables problemáticas en términos del multiplicador de
Lagrange (o variable dual), obtenemos.
Ahora eliminamos las variables del problema original de la función lagrangiana:
Podemos usar la variable dual para resolver nuestro problema de la siguiente manera:
Por lo tanto, el valor de la variable dual es q * (λ ) = 5. Los valores de las variables
primarias son x1 = 4 y x2 = 1.
En el problema de despacho económico tratado en este capítulo, uno no puede eliminar
las variables problemáticas ya que las funciones de generación de costo unitario pueden
ser por partes funciones lineales u otras funciones complejas. En este caso, debemos
usar la optimización dual algoritmo descrito anteriormente: primero optimizamos en λ y
luego en las variables problemáticas, luego regrese y actualice λ , etc. Dado que el doble
problema requiere que encontremos
y no tenemos una función explícita en λ (como lo hicimos en el texto anterior), debemos
adopta una estrategia ligeramente diferente. En caso de despacho económico u otros
problemas. donde no podemos eliminar las variables problemáticas, encontramos una
manera de ajustar λ para mueva q (λ ) de su valor inicial a uno que sea más grande. La
forma más sencilla de hacer esto es usar un ajuste de gradiente para que
donde a simplemente hace que el gradiente se comporte bien. Una forma más útil de aplicar el
La técnica de gradiente es dejar que se ajuste hacia arriba a una velocidad y hacia abajo a una
velocidad tasa mucho más lenta; por ejemplo,
La cercanía a la solución final en el método de optimización dual se mide por observando el
tamaño relativo de la "brecha" entre la función primaria y la dual función. El problema de
optimización principal se puede resolver directamente en el caso de El problema se indica en la
Ecuación 3A.2, y el valor óptimo se llamará J * y Se define como
Este valor se comparará con el valor óptimo de la función dual, q *. Los la diferencia
entre ellos se llama "brecha de dualidad". Una buena medida de la cercanía para la
solución óptima es la "brecha de dualidad relativa", definida como
Para un problema convexo con variables continuas, la brecha de dualidad se convertirá
en 0 en el solución final. Cuando retomamos el método de optimización dual en el
Capítulo 4, trataremos problemas no convexos con variables no continuas y el la brecha
de dualidad en realidad nunca irá a 0.
Usando el enfoque de optimización dual en el problema dado en la Ecuación 3A.2
y comenzando en λ = 0, obtenemos los resultados que se muestran en la Tabla 3.5.
Como se puede ver, esto procedimiento converge a la respuesta correcta.
Una nota especial sobre la búsqueda lambda. El lector debe tener en cuenta que la técnica
dual, cuando se aplica al despacho económico, es lo mismo que la técnica de búsqueda
lambda que introducido anteriormente en este capítulo para resolver el problema del
despacho económico.
Apendice 4A
Introdujimos el concepto de optimización dual en el Apéndice 3E y señalamos
que cuando la función a optimizar es convexa, y las variables son continuas,
entonces la maximización de la función dual da el mismo resultado que minimizar
La función primaria. La optimización dual también se utiliza para resolver el
compromiso de la unidad
problema. Sin embargo, en el problema de compromiso de la unidad, hay variables que
debe restringirse a dos valores: 1 o 0. Estas variables 1–0 causan una gran cantidad de
problemas y son la razón de la dificultad para resolver el compromiso de la unidad
problema. La aplicación de la técnica de optimización dual al compromiso de la unidad.
Al problema se le ha dado el nombre de "relajación de Lagrange" y la formulación del
El problema de compromiso de la unidad con este método se muestra en el capítulo de
la Sección 4.2.2 En este apéndice, ilustramos esta técnica con un problema geométrico
simple. El problema está estructurado con 1–0 variables, lo que lo hace claramente no
convexo. Sus la forma es generalmente similar a la forma de los problemas de
compromiso de la unidad, pero eso es incidental por ahora.
El problema de muestra a resolver se da a continuación. Ilustra la habilidad del dual
técnica de optimización para resolver el problema de compromiso de la unidad. Dado:
donde x1 y x2 son números reales continuos, y
Tenga en cuenta que en este problema tenemos dos funciones, una en x1 y la otra en x2.
Los Se eligieron funciones para demostrar ciertos fenómenos en una optimización dual.
Tenga en cuenta que las funciones son numéricamente cercanas y solo difieren en una
pequeña y constante cantidad. Cada una de estas funciones se multiplica por una variable
1–0 y se combina en La función objetivo general. También hay una restricción que
combina x1 y x2 variables de nuevo con las variables 1–0. Hay cuatro posibles soluciones.
1. Si u1 y u2 son ambos 0, el problema no puede tener una solución ya que la igualdad
restricción no puede ser satisfecha.
2. Si u1 = 1 y u2 = 0, tenemos la solución trivial que x1 = 5 y x2 no entrar en el problema
más. La función objetivo es 21.25.
3. Si u1 = 0 y u2 = 1, entonces tenemos el resultado trivial de que x2 = 5 y x1 no entran en el
problema La función objetivo es 21.375.
4. Si u1 = 1 y u2 = 1, tenemos una función de Lagrange simple de
El óptimo resultante está en x1 = 2.5248, x2 = 2.4752 y λ = 1.2624, con un objetivo
valor de la función de 33.1559. Por lo tanto, sabemos el valor óptimo para este
problema; a saber, u1 = 1, u2 = 0 y x1 = 5.
Lo que hemos hecho, por supuesto, es enumerar todas las combinaciones posibles de
1–0 variables y luego optimizar sobre las variables continuas. Cuando hay mas
que algunas variables 1–0, esto no se puede hacer debido a la gran cantidad de posibles
combinaciones. Sin embargo, hay una forma sistemática de resolver este problema
utilizando el doble formulación
El método de relajación de Lagrange resuelve problemas como el anterior como
sigue. Defina la función de Lagrange como
Como se muestra en el Apéndice 3E, definimos q (λ ) como:
donde x1, x2, u1, u2 obedecen los límites y las condiciones 1–0 como antes. El doble
problema es entonces encontrar
Esto es diferente del enfoque de optimización dual utilizado en el Apéndice 3E porque de
la presencia de las variables 1–0. Debido a la presencia de las variables 1–0, nosotros no
puede eliminar variables; por lo tanto, mantenemos todas las variables en el problema y
proceder en pasos alternos como se muestra en el Apéndice 3E.
Paso 1. Elija un valor para λk y considérelo fijo. Ahora la función lagrangiana puede
ser minimizado Esto es mucho más simple que la situación que teníamos antes desde
que están tratando de minimizar
donde el valor de λk es fijo. Entonces podemos reorganizar la ecuación anterior como
El último término en la ecuación anterior es fijo y podemos ignorarlo. Los otros términos
ahora se dan de tal manera que la minimización de esta función es relativamente fácil.
Tenga en cuenta que la minimización ahora está en dos términos, cada uno multiplicado
por un 1-0 variable. Dado que estos dos términos se resumen en el lagrangiano,
podemos minimizar la función completa minimizando cada término por separado. Como
cada término es producto de una función en x y λ (que es fija) y todas ellas se multiplican
por la variable 1–0 u, entonces el mínimo será 0 (es decir, con u = 0) o será negativo,
con u = 1 y el valor de x establecido para que el término dentro de los paréntesis sea
negativo. Mirando al primer término, el valor óptimo de x1 se encuentra por (ignore u1
por un momento):
Si el valor de x1 que satisface el valor establecido anteriormente cae fuera de los límites
de 0 y 10 para x1, forzamos a x1 al límite infringido. Si el término entre paréntesis
es positivo, entonces podemos minimizar el lagrangiano simplemente configurando u1
= 0; de otra manera, u1 = 1.
Mirando el segundo término, el valor óptimo de x2 se encuentra por (nuevamente,
ignore u2)
y si el valor de x2 que satisface el valor indicado anteriormente queda fuera del 0-10
límites en x2, lo establecemos en el límite violado. Del mismo modo, el término en el
segundo paréntesis
es evaluado Si es positivo, minimizamos el lagrangiano haciendo u2 = 0;
de otra manera,
u2 = 1. Ahora hemos encontrado el valor mínimo de L con un valor fijo especificado
valor de λk.
Paso 2 Suponga que las variables x1, x2, u1, u2 encontradas en el paso 1 son fijas y
encuentra un valor para l que maximiza la doble función. En este caso, no podemos
resolver el máximo ya que q (λ) no tiene límites con respecto a λ. En cambio,
formamos el gradiente de q (λ) con respecto a λ, y ajustamos l para movernos en la
dirección de aproximadamente q (λ). Es decir, dado
que para nuestro problema es
ajustamos λ de acuerdo a
donde a es un multiplicador elegido para moverse λ solo una corta distancia. Tenga en
cuenta también que si ambos u1 y u2 son 0, el gradiente será 5, lo que indica un valor
positivo que nos indica que aumentemos λ . Eventualmente, aumentar λ resultará en un
valor negativo para
O por:
o para ambos, y esto hará que u1 o u2, o ambos, se establezcan en 1 . Una vez que el
valor de λ es aumentado, volvemos al paso λ y encontramos los nuevos valores para
x1, x2, u1, u2 nuevamente.
La verdadera dificultad aquí es no aumentarlo demasiado. En el ejemplo presentado
anteriormente, se impuso el siguiente esquema al ajuste de λ :
Esto me permite acercarme a la solución lentamente, y si se sobrepasa, retrocede muy
lentamente. Esta es una técnica común para hacer que un gradiente se "comporte".
También debemos tener en cuenta que, dadas las pocas variables que tenemos, y dado el
hecho de que dos de ellas son variables 1–0, el valor de λ no convergerá al valor
necesario para minimizar el lagrangiano. De hecho, rara vez es posible encontrar un dak
que haga que problema factible con respecto a la restricción de igualdad. Sin embargo,
cuando tenemos encontramos los valores para u1 y u2 en cualquier iteración, entonces
podemos calcular el mínimo de J (x1, x2, u1, u2) resolviendo para el mínimo de
utilizando las técnicas en el Apéndice 3E (ya que ahora se conocen las variables u1 y
u2).
La solución a este mínimo estará en X1= X1 , X2= X2 y λ = λ. Para el caso
donde u1 y u2 son ambos 0, estableceremos arbitrariamente este valor en un valor
grande (aquí configúrelo en 50). Llamaremos a este valor mínimo J*(1 2 1 2 J (x1, x2,
u1, u2), y observaremos que comienza con un valor grande y disminuye, mientras que el
valor dual q * (λ ) comienza fuera con un valor de 0, y aumenta. Como hay 1–0
variables en este problema, el los valores primarios y los valores duales nunca se
vuelven iguales. El valor J * - q * se llama brecha de dualidad y llamaremos al valor
la brecha de dualidad relativa.
La presencia de las variables 1–0 hace que el algoritmo oscile alrededor de una solución
con una o más de las variables 1–0 saltando de 1 a 0 a 1, etc. En tales
casos, el usuario del algoritmo de relajación de Lagrange debe detener el algoritmo,
basado
sobre el valor de la brecha de dualidad relativa.
Las iteraciones a partir de λ = 0 se muestran en la Tabla 4.4. La tabla muestra ocho
itera e ilustra el enfoque lento de λ hacia el umbral cuando ambos las variables 1–0
cambian de 0 a 1. También tenga en cuenta que w se volvió negativo y el valor de
Ahora debo ser disminuido. Finalmente, se alcanza la solución óptima y la relativa
la brecha de dualidad se vuelve pequeña. Sin embargo, como es típico con la
optimización dual en un en un problema con 1–0 variables, la solución no es estable y si
se repite más adelante exhibe cambios adicionales en las variables 1–0 a medida que se
ajusta l. Tanto los valores q * como J * y La brecha relativa de dualidad se muestra en la
Tabla 4.4.
Teoria:
4.2.2 Lagrange Relaxation Solution
El método DP de solución del problema de compromiso de la unidad tiene muchas
desventajas. para grandes sistemas de energía con muchas unidades generadoras. Esto
se debe a la necesidad de forzar a la solución DP a buscar en un pequeño número de
estados de compromiso para
reduzca el número de combinaciones que deben probarse en cada período de tiempo.
En la técnica de relajación de Lagrange, estas desventajas desaparecen (aunque
surgen otros problemas técnicos y deben abordarse, como veremos). Este método
se basa en un enfoque de optimización dual como se presenta en el Apéndice 3E y más
expandido en el Apéndice 4A de este capítulo. (El lector debe estar familiarizado con
ambos estos apéndices antes de continuar).
Comenzamos definiendo la variable es
si la unidad está fuera de línea durante el período t
si la unidad está en línea durante el período t (4.1)
Ahora definiremos varias restricciones y la función objetivo de la unidad
Compromiso problema:
1. Restricciones de carga:
2. Límites de la unidad:
3. Restricciones mínimas de tiempo de actividad y de inactividad de la unidad
Tenga en cuenta que otras restricciones pueden se puede formular y agregar
fácilmente al problema de compromiso de la unidad. Éstos incluyen
restricciones de seguridad de transmisión (ver Capítulo 7), restricciones de
límite de combustible del generador, y restricciones de la calidad del aire del
sistema en forma de límites de emisiones de plantas alimentadas con fósiles,
restricciones de reservas giratorias, etc.
4. The objective function is
Entonces podemos formar la función de Lagrange de manera similar a como lo hicimos
en la economía problema de despacho:
El problema de compromiso de la unidad requiere que minimicemos esta función de
Lagrange, sujeto a las restricciones de unidad local 2 y 3, que se pueden aplicar a cada
unidad por separado. Nota:
1. La función de costo, junto con las restricciones 2 y 3 son cada una
Separable sobre unidades. Es decir, lo que se hace con una unidad no afecta el costo de
ejecutar otra unidad, en cuanto a la función de costo y los límites de la unidad
(restricción 2) y el tiempo de inactividad y de inactividad de la unidad (restricción 3)
están relacionados.
2. Las restricciones 1 son restricciones de acoplamiento entre las unidades, de modo que
lo que hacemos para una unidad afecta lo que sucederá en otras unidades si las
restricciones de acoplamiento deben cumplirse
El procedimiento de relajación de Lagrange resuelve el problema de compromiso de la
unidad al "relajarse" o ignorar temporalmente las restricciones de acoplamiento y
resolver el problema como si No existían. Esto se realiza mediante el procedimiento de
optimización dual como se explicó en el Apéndice 4A de este capítulo. El
procedimiento dual intenta alcanzar el límite óptimo maximizando el lagrangiano con
respecto a los multiplicadores de Lagrange mientras se minimiza con respecto a las
otras variables en el problema; es decir,
Esto se realiza en dos pasos básicos:
Paso 1. Encuentra un valor para cada ʎt que mueve q (ʎ) hacia un valor mayor.
Paso 2. Suponiendo que los ʎt encontrados en el paso 1 ahora están fijos, encuentre el
mínimo de L ajustando los valores de Pt y Ut.
El ajuste de los valores de ʎt se tratará más adelante en esta sección; supongamos entonces
que se ha elegido un valor para todo el ʎt y que ahora deben ser tratado como números fijos.
Minimizaremos el lagrangiano de la siguiente manera.
Primero, reescribimos el lagrangiano como
Esto ahora se reescribe como
El segundo término en la ecuación anterior es constante y puede descartarse (ya que
Son fijos). Finalmente, escribimos la función de Lagrange como
Aquí, hemos logrado nuestro objetivo de separar las unidades entre sí. El termino
dentro de los corchetes exteriores, es decir,
se puede resolver por separado para cada unidad generadora, sin tener en cuenta lo que
es sucediendo en las otras unidades generadoras. El mínimo del lagrangiano se ncuentra
resolviendo el mínimo para cada unidad generadora en todos los períodos de tiempo; es
decir,
y las restricciones de tiempo de actividad y de inactividad. Esto se resuelve fácilmente
como un problema DP en uno variable. Esto se puede visualizar en la Figura 4.5, que
muestra los dos únicos posibles estados para la unidad i
donde Si es el costo inicial para la unidad i.
estado, el valor de la función a minimizar es trivial (es decir,
es igual a 0); en el estado donde la función a minimizar es (el costo inicial
se cae aquí ya que la minimización es con respecto a )
El mínimo de esta función se encuentra tomando la primera derivada
La solución a esta ecuación es
Hay tres casos que deben preocuparse dependiendo de la relación de
y el límites de la unidad:
entonces
La solución del programa dinámico de dos estados para cada unidad procede de manera
normal. manera como se hizo para la solución DP avanzada del problema de
compromiso de la unidad sí mismo. Tenga en cuenta que ya que buscamos minimizar
en cada etapa y que cuando este valor va a 0,
entonces la única forma de obtener un valor más bajo es tener
El programa dinámico debe tener en cuenta todos los costos iniciales, Si, para cada
unidad, así como el tiempo de inactividad y inactividad mínimos para el generador. Ya
que estamos resolviendo para cada generador de forma independiente, sin embargo,
hemos evitado los problemas de dimensionalidad que afectan la solución DP.
[Link] Adjusting Lambda
Hasta ahora, hemos mostrado cómo programar la generación
unidades con valores fijos de ʎt para cada período de tiempo. Como se muestra en el
Apéndice 4A de este capítulo, el ajuste de lt debe hacerse con cuidado para maximizar q
(ʎ). Más Las referencias que trabajan en el procedimiento de relajación de Lagrange
utilizan una combinación de gradiente búsqueda y diversas heurísticas para lograr una
solución rápida. Tenga en cuenta que a diferencia del Apéndice 4A, el ʎ aquí es un
vector de valores, cada uno de los cuales debe ser ajustado. Mucha investigación en
Los últimos años se han dirigido a formas de acelerar la búsqueda de los valores
correctos de ʎ para
cada hora. En el ejemplo 4E, usaremos la misma técnica de ajustar ʎ por cada hora
eso se usa en el apéndice. Para el problema de compromiso de la unidad resuelto en el
Ejemplo 4E, sin embargo, los factores de ʎ ajuste son diferentes:
Cada ʎt se trata por separado. El compromiso general de la unidad de relajación de
Lagrange El algoritmo se muestra en la Figura 4.6. Una medida de la cercanía a la
solución, llamada "brecha relativa de dualidad", es definido como (J * - q *) / q *. La
brecha de dualidad relativa se usa en el ejemplo 4E como medida.
Para cálculos de compromiso de unidades de sistema de potencia grandes y de tamaño
real, la dualidad
la brecha se vuelve bastante pequeña a medida que avanza la optimización dual, y su
tamaño puede
ser utilizado como criterio de detención. Cuanto mayor es el problema (mayor número
de
generando
unidades), cuanto menor es la brecha.
2. La convergencia es inestable al final, lo que significa que algunas unidades están
siendo
encendido y apagado, y el proceso nunca llega a un final definitivo.
3. No hay garantía de que cuando se detenga la solución dual, se encuentre en un
factible
solución.
Todos estos se demuestran en el Ejemplo 4E. La brecha de dualidad es grande al
principio
y se vuelve progresivamente más pequeño a medida que avanzan las iteraciones. La
solución alcanza
un cronograma de compromiso cuando se compromete al menos suficiente generación
para que un
el despacho económico puede ejecutarse, y otras iteraciones solo resultan en un cambio
marginal
unidades de encendido y apagado. Finalmente, las restricciones de carga no se cumplen
con la solución dual
cuando se detienen las iteraciones.
Muchos de los programas de compromiso de la unidad de relajación de Lagrange usan
algunas iteraciones
de un algoritmo DP para obtener un buen punto de partida, luego ejecute la
optimización dual
iteraciones,
y finalmente, al final, use lógica heurística o DP restringido para llegar a un final
solución. El resultado es una solución que no se limita a las ventanas de búsqueda,
como qué
tuvo que hacerse en estricta aplicación de DP.
EJEMPLO 4E En este ejemplo, un compromiso de unidad de tres generadores y cuatro
horas El problema será resuelto. Los datos para este problema son los siguientes. Dados
los tres unidades generadoras en lo siguiente,
sin costos iniciales, sin restricciones mínimas de tiempo de actividad o inactividad.
Este ejemplo se resuelve utilizando la técnica de relajación de Lagrange. Mostrado en el
El siguiente texto es el resultado de varias iteraciones, comenzando desde una condición
inicial donde todos los valores de ʎ se establecen en 0. Se ejecuta un despacho
económico por cada hora, siempre que hay suficiente generación comprometida esa
hora. Si no hay suficiente generación comprometido, el costo total para esa hora se
establece arbitrariamente en 10,000. Una vez cada hora tiene suficiente generación
comprometida, el valor primario J * simplemente representa el total costo de generación
sumado a lo largo de todas las horas según lo calculado por el despacho económico.
El programa dinámico para cada unidad con un ʎ = 0 para cada hora siempre resultará
en todas las unidades generadoras fuera de línea.
En la próxima iteración, los valores de ʎ se han incrementado. Para ilustrar el uso de DP
para programar cada generador, detallaremos los pasos DP para la unidad 3 en la Figura
4.7.
El resultado es programar la unidad 3 apagado durante las horas 1, 2 y 4 y encendido
durante la hora 3. Además, la unidad 3 está programada para alcanzar su máximo de
200 MW durante la hora 3. El Los resultados, después de que todas las unidades hayan
sido programadas por DP, son los siguientes.
El cronograma de compromiso no cambia significativamente con más iteraciones,
aunque de ninguna manera es estable. Otras iteraciones reducen la brecha de dualidad
algo, pero estas iteraciones son inestables en que la unidad 2 está en el límite entre
estar comprometido y no estar comprometido y se activa y desactiva sin final
convergencia. Después de 10 iteraciones, q (ʎ) = 19, 485, J * = 20, 017 y (J * - q *) / q *
= 0.027. Este último valor no irá a 0, ni la solución se establecerá en un valor final;
por lo tanto, el algoritmo debe detenerse cuando (J * - q *) / q * es suficientemente
pequeño (por ejemplo, menos de 0.05 en este caso).
Lagrange Relaxation Solution
El método DP de solución del problema de compromiso de la unidad tiene muchas
desventajas. para grandes sistemas de energía con muchas unidades generadoras.
Esto se debe a la necesidad de obligar a la solución DP a buscar en un pequeño número
de estados de compromiso para reduzca el número de combinaciones que deben
probarse en cada período de tiempo. En la técnica de relajación de Lagrange, estas
desventajas desaparecen (aunque surgen otros problemas técnicos y deben abordarse,
como veremos). Este método se basa en un enfoque de optimización dual como se
presenta en el Apéndice 3E y más expandido en el Apéndice 4A de este capítulo. (El
lector debe estar familiarizado con ambos estos apéndices antes de continuar).
