fundamentos de planificación

CT-7611

PLANIFICACIÓN DE SISTEMAS DE POTENCIA

CT-7611

QUE ES PLANIFICAR ?

“Predecir a mínimo costo, requerimientos futuros del sistema ante las exigencias que se estiman colocarle al mismo, de tal manera que:”.

a) Se mantengan estándares adecuados para el intercambio energético en la red.

b) Se garantice la seguridad e integridad del sistema y del personal.

c) El costo de producción sea mínimo (Generación).

d) Se puedan efectuar extensiones (refuerzos, economía de escala) al sistema sin poner en riesgo sus estándares.

CT-7611

QUE ES PLANIFICAR ?

•DONDE

•CUANDO

•QUE Y

•COMO

REFORZAR EL SISTEMA ELÉCTRICO, IDENTIFICANDO

Reforzar el sistema.

CT-7611

T DG D MW

SISTEMA DE POTENCIA A PLANIFICAR

PLANIFICACIÓN INTEGRAL

ΔT ΔT ΔT

PLANIFICACIÓN POR BLOQUES, JUSTIFICADO SOBREMANERA POR DIFERENCIAS EN TIEMPO DE CONTRUCCIÓN Y COSTOS

CT-7611

PLANIFICACIÓN POR BLOQUE

G D MW

CONFIABILIDAD

MÍNIMOS COSTOS DE OPERACIÓN

A. GENERACIÓN-DEMANDA : FORMA CONVENCIONAL DE PLANIFICAR GENERACIÓN.

CT-7611

TG

PLANIFICACIÓN POR BLOQUE

B. GENERACIÓN-TRANSMISIÓN-DEMANDA

MW

DEMANDA AGREGADA

CONFIABILIDAD

COSTOS

CT-7611

GG

G

S/E S/E

S/ES/E

S/E

B. GENERACIÓN-TRANSMISIÓN-DEMANDA

CT-7611

T D

C. TRANSMISIÓN-DISTRIBUCIÓN-DEMANDA

CONFIABILIDAD

SEGURIDAD

COSTOS

S/E

S/E

S/E

CT-7611

1

2

3

4

5

10

20 año horizonte ?Cor

to p

lazo

Mediano plazo

Largo plazo

Definición de las alternativas a largo plazo en la evolución año tras año.

Estudios técnicos, económicos, financieros y ambientales

Costo final a un año horizonte, relativamente alto.

CT-7611

1

2

3

4

5

10

20 año horizonte ?Cor

to p

lazo

Mediano plazo

Largo plazo

Definición de las alternativas en el año horizonte

Definición de los planes intermedios

Estudios técnicos, económicos, financieros y ambientales

Costo final a un año horizonte,

moderada y relativamente bajo.

Flujo de carga, cortocircuito, estabilidad, ajuste nivel de V, estructuras.. ……….

CT-7611TÉCNICAS COMUNES PARA ELTRATAMIENTO DEL PROBLEMA

DE PLANIFICACIÓN DE SISTEMAS DE POTENCIA ELÉCTRICA

Pérdida de carga esperada ( Generación)

Energía no servida (Generación)

Programación Lineal

Programación Mixta

Programación Dinámica

Programación Cuadrática

Programación no-lineal

Métodos heurísticos (métodos de búsqueda)

Métodos Meta-heurísticos

CT-7611PROPIEDADES BÁSICAS DE ALGUNOS MÉTODOS DE OPTIMIZACIÓN

MËTODO Modelación del comportamiento del sistema

Características de las restricciones

Características de la función objetivo

Restricción en las variables .

LP: Programación Lineal

Mediante ecuaciones y/o inecuaciones

Deben ser lineales Debe ser lineal Deben ser continuas y no-negativas

PM: Programación entera


Deben ser lineales Debe ser lineal Deben ser no-negativas Continuas y/o enteras

Programación dinámica

Proceso físico debe ser Markoviano. Sistema representado en etapas, estados y estrategias, descrito por cualquier conjunto de ecuaciones disponibles.

Ninguna Puede utilizarse cualquier formulación para definir costos en los estados del sistema

Ninguna

Programación cuadrática


Deben ser lineales Debe ser función convexa para minimización o cóncava para maximización

Deben ser no-negativas

Programación no-lineal. Métodos del gradiente.

Mediante ecuaciones y/o inecuaciones incluidas como términos de penalización en la función objetivo.

En la mayoría de los métodos deben ser diferenciables en el rango considerado

En la mayoría de los métodos debe ser diferenciable en el rango considerado

Dependiendo del punto de arranque puede encontrar solo valores extremos locales.

Métodos Heurísticos y Meta-heuristicos

Logística del proceso puede utilizarse para definir la solución

Ninguna

CT-7611UBICACIÓN DE LA PLANIFICACIÓN EN ELTIEMPO

Tiempo Acción o proceso Función

Segundos Control automático de generación. Protecciones

Minimizar errores en las áreas o lazos de control sujetos a restricciones dinámicas

de las máquinas y del sistema.Resguardar el sistema de los efectos de

las fallas.

MinutosFlujo de carga óptimo. Despacho económico

Minimizar costos instantáneos de operación y otros índices, polución por

ejemplo

Horas Asignación de unidades. Despacho Hidrotérmico Minimizar costos esperados en la operación y otros índices, bote de carga

por ejemplo.

Días y/o semanas Despacho Hidrotérmico ( Unit Commitment). Coordinación de intercambio energético entre áreas.

Estimar cuales plantas deben estar en línea y su nivel promedio de operación

para cada intervalo de tiempo.

Meses Programación de mantenimiento. Coordinación de intercambio. Políticas gerenciales sobre combustibles y embalses basados

en cargas futuras, agua disponible y costo de combustible.

Minimizar costos de operación con restricciones mínimas de seguridad y

confiabilidad.

Años Programación del mantenimiento. Planificación del sistema a largo plazo.

Minimizar futuras posibles inversiones y los costos operativos asociados a niveles

de seguridad y confiabilidad.

CT-7611UBICACIÓN DE LA PLANIFICACIÓN EN ELTIEMPO

Un ejemplo de programación lineal.

Método Simplex

CT-7611Programación Lineal

Suponga que usted tiene una fábrica de vasos y sólo tiene dos moldes.

Con el molde 1 puede producir 1 caja de vasos1 en 6 horas.

Con el molde 2 puede producir 1 caja de vasos2 en 5 horas.

Usted tiene un almacén donde coloca su producción semanal.

La caja de vasos1 requiere 10 pie3 de almacenamiento.

La caja de vasos2 requiere 20 pie3 de almacenamiento.

Usted dispone de 60 horas por semana para la producción.

El depósito para su producción tiene una capacidad de 150 pie3.

Precio de venta de caja de vasos1 = 500 U., y la de vasos2 = 450 U.

El mercado no le permite colocar mas de 8 cajas de vasos1 por semana.

¿COMO PUEDE USTED ORDENAR LA PRODUCCION PARA QUE EL BENEFICIO DE LA VENTA DE VASOS, SEMANAL, SEA MÁXIMO?

CT-7611Formulación como problema de


Variables de decisión :

X1= # de cajas de vasos1 producidas por semana.

X2= # de cajas de vasos2 producidas por semana.

Objetivo: Maximizar la venta de cajas de vasos = Maximizar sus ingresos

Función Objetivo: Maximizar : 500X1 + 450X2

Restricciones:

# horas de producción/semana ≤ 60 6X1 + 5X2 ≤ 60

Capacidad del almacén: ≤ 150 10X1 + 20X2 ≤ 150

Demanda de X1 ≤ 8 X1 ≤ 8

Variables de decisión deben ser no-negativas: X1 ≥ 0

X2 ≥ 0



RESÚMEN DEL MODELO

Maximizar Z = 500X1 + 450X2

6X1 + 5X2 ≤ 60

10X1 + 20X2 ≤ 150

X1 ≤ 8

X1 ≥ 0

X1 ≥ 0

Note que las variables X1 y X2 en la

función Z, están acompañadas de sus

respectivos coeficientes de costo.

En las restricciones, estas variables

están acompañadas de coeficientes

técnicos.

Cada restricción está acotada por las

denominadas constantes de limitación

de recursos o (RHS)



REPRESENTACIÓN GRÁFICA


6X1 + 5X2 ≤ 60

10X1 + 20X2 ≤ 150

X1 ≤ 8

X1 ≥ 0

X2 ≥ 02

6

4

8

10

12

2 4 6 8 10 12 14 16

o

oo

o o

Zona factible

6X1 + 5X2 = 60

10X1 + 20X2 = 150

X1 = 8

Vértices

X1

X2

●●

●

●





6X1 + 5X2 ≤ 60

10X1 + 20X2 ≤ 150

X1 ≤ 8

X1 ≥ 0

X2 ≥ 0

Nótese que la solución óptima ocurre en

uno de los vértices de la región factible;

esta es una propiedad de la programación

lineal.

Solución óptima

2

6

4

8

10

12

2 4 6 8 10 12 14 16

o

oo

o o

Zona factible

X1=6.43, x2=4.28, Z = 5142

X1

X2

X1=8, x2=2.4, Z = 5080

X1=8, x2=0, Z = 4000

X1=0, x2=7.5, Z = 3375

Función Objetivo

●

●

●

●●



METODO SIMPLEX

El método Simplex, utilizado para resolver

problemas de programación lineal, explota

la propiedad de que la solución se

encuentra en un vértice.

El método inicia la búsqueda de la solución en

un vértice y se desplaza de vértice a

vértice, mejorando en cada movimiento, el

valor de la función objetivo, hasta alcanzar el

mejor valor ( el óptimo).

2

6

4

8

10

12

2 4 6 8 10 12 14 16

o

o

o o

Zona factible

X1=6.43, x2=4.28, Z = 5142

X1

X2

X1=8, x2=2.4, Z = 5080

X1=8, x2=0, Z = 4000

X1=0, x2=7.5, Z = 3375

Función Objetivo

●●

●

●

●



2

6

4

8

10

12

2 4 6 8 10 12 14 16

o

oo

o o

Zona factible

X1=6.43, x2=4.28, Z = 5142

X1

X2

X1=8, x2=2.4, Z = 5080

X1=8, x2=0, Z = 4000

X1=0, x2=7.5, Z = 3375

Función Objetivo

METODO SIMPLEX

En este particular problema, el punto óptimo

se encuentra en el vértice donde se

interceptan las rectas:

6X1+ 5X2 = 60 (Capacidad de producción)

y

10X1+ 20X2 = 150 (Capacidad de almacén)

●

●●

●●



2

6

4

8

10

12

2 4 6 8 10 12 14 16

o

oo

o o

Zona factible

X1=6.43, x2=4.28, Z = 5142

X1

X2

X1=8, x2=2.4, Z = 5080

X1=8, x2=0, Z = 4000

X1=0, x2=7.5, Z = 3375

Función Objetivo

METODO SIMPLEX

Se dice en ese caso que las restricciones

6X1+ 5X2 = 60 (Capacidad de producción)

10X1+ 20X2 = 150 (Capacidad de almacén)

están activas. En cambio la restricción X1 ≤ 8

no lo está, de hecho, en el punto óptimo, X1

vale 6.43. Por tanto la ecuación X1 ≤ 8 tiene

una holgura de 1.57= ( 8 - 6.43), es decir

si se redujera la producción de X2, se pudiera

entonces incrementar la producción de X1

hasta 1.57 unidades, pero por supuesto eso

alteraría el óptimo.

●

●

●●

●



METODO SIMPLEX

Para cada inecuación no activa existirá

una holgura en la solución, cuyo valor se

le asigna a una variable denominada

variable de holgura.

2

6

4

8

10

12

2 4 6 8 10 12 14 16

o

oo

o o

Zona factible

X1=6.43, x2=4.28, Z = 5142

X1

X2

X1=8, x2=2.4, Z = 5080

X1=8, x2=0, Z = 4000

X1=0, x2=7.5, Z = 3375

Función Objetivo

●

●●

●●



VALORES MARGINALES,

VARIABLES DUALES O

PRECIOS DE SOMBRA.

Estas son valores asociados a cada

ecuación activa del problema, en el

punto de solución óptima.

Representan el cambio que

experimentaría la función

objetivo debido a incrementos unitarios

en los valores de las constantes de

limitación de recursos (RHS), asociados

a las restricciones activas.

2

6

4

8

10

12

2 4 6 8 10 12 14 16

o

oo

o o

Zona factible

X1=6.43, x2=4.28, Z = 5142

X1

X2

X1=8, x2=2.4, Z = 5080

X1=8, x2=0, Z = 4000

X1=0, x2=7.5, Z = 3375

Función Objetivo

●

●●

●●

CT-7611


6X1 + 5X2 ≤ 60

10X1 + 20X2 ≤ 150

X1 ≤ 8

X1 ≥ 0

X2 ≥ 0

Formulación como problema de Programación Lineal

En el ejemplo que se sigue, suponga que el número de horas de trabajo semanal se incrementa de 60 a 61,¿Cuál es el cambio en la función objetivo?

2

6

4

8

10

12

2 4 6 8 10 12 14 16

o

oo

o o

Zona factible

6X1 + 5X2 = 60

10X1 + 20X2 = 150

X1 = 8

Vértices

X1

X2

●●

●

●●

CT-7611


6X1 + 5X2 ≤ 61

10X1 + 20X2 ≤ 150

X1 ≤ 8

X1 ≥ 0

X2 ≥ 0


Con este nuevo elemento, el problema quedaría formulado de la siguiente manera:

CT-7611


6X1 + 5X2 ≤ 61

10X1 + 20X2 ≤ 150

X1 ≤ 8

X1 ≥ 0

X2 ≥ 0


Su solución está en el siguiente vértice:

X1 = 6.71; X2 = 4.14

y el valor de la función objetivo es: Z = 5221

Luego el valor marginal o la variable dual de

la restricción 6X1 + 5X2 ≤ 60 es :

5221 – 5142 = 79

Esto indica que si se decidiese aumentar el

tiempo de producción en una hora

semanal, el ingreso se incrementaría en

79 unidades monetarias. Dicho de otra

manera, no es rentable invertir mas de 79

unidades monetarias para incrementar el

tiempo de producción en una hora.



Si el incremento fuera en la capacidad de almacenamiento:

Maximizar Z = 500X1 + 450X2 6X1 + 5X2 ≤ 60 10X1 + 20X2 ≤ 151 X1 ≤ 8 X1 ≥ 0 X2 ≥ 0

El valor marginal de la respectiva variable dual resulta en 2.86; locual indica que la adición de un pié cúbico más al almacén produciría un ingreso adicional de 2.86 unidades de costo o, si usted va a rentar más espacio por que desea incrementar su producción, no debe pagar por el alquiler más de 2.86 unidades de costo por pié cúbico, de lo contrario estaría perdiendo.



Maximizar Z = 500X1 + 450X2 6X1 + 5X2 ≤ 60 10X1 + 20X2 ≤ 151 X1 ≤ 8 X1 ≥ 0 X2 ≥ 0

La variable dual asociada a la demanda de cajas de vasos1 X1 ≤ 8

debe ser cero. No se están produciendo las cajas de vasos que demanda el mercado, de tal forma que incrementar el límite de 8 a 9 da igual para la solución; el valor de la función objetivo no se altera.

2

6

4

8

10

12

2 4 6 8 10 12 14 16

o

oo

o o

Zona factible

6X1 + 5X2 = 60

10X1 + 20X2 = 150

X1 = 8

Vértices

X1

X2

●●

●

●●



Maximizar Z = 500X1 + 450X2 6X1 + 5X2 ≤ 60

10X1 + 20X2 ≤ 151 X1 ≤ 8 X1 ≥ 0 X2 ≥ 0

Finalmente, consideremos las variables duales asociadas a las restricciones de no-negatividad: X1 ≥ 0 y X2 ≥ 0.

Estas son comúnmente denominados costos reducidos.

Usualmente se reportan separadas de las variables duales de las otras restricciones. Sin embargo, su interpretación es idéntica a la que se da a aquellas. El costo reducido de una variable = cero, si esa variable está en la solución del problema (X ≠ 0), -se dice que la variable está en la base-, de lo contrario, el costo reducido es ≠ cero.




s.a.Variable dual y1 = 79 ; 6X1 + 5X2 ≤ 60Variable dual y2 = 2.86; 10X1 + 20X2 ≤ 151Variable dual y3 = 0 ; X1 ≤ 8 X1 ≥ 0 Costo reducido R1 = 0 X2 ≥ 0 Costo reducido R2 = 0

En Programación Lineal todo problema principal tiene asociado un problema dual.

Este planteamiento se revisará más adelante.

CT-7611Programación Lineal: Método Simplex

En términos matemáticos el problema de programación lineal se puede expresar como la maximización o minimización de una función objetivo sujeta a un conjunto de restricciones lineales.

Maximizar Z = C1X1 + C2X2+……….CnXn Sujeto a : a11X1 + a12X2 + …….a1nXn ≤ b1 a21X1 + a22X2 + …….a2nXn ≤ b2 . . . . . . an1X1 + an2X2 + …….annXn ≤ bn X1 ≥0; X2 ≥0;………….Xn ≥0Donde C´s, a´s y b´s son constantes.

El objetivo puede ser minimizar.

Las restricciones pueden ser tipo ≤, ≥, o = .

Algunas variables pueden asumir valores positivos o negativos.

CT-7611Programación Lineal: Método Simplex.

Cualquier problema de programación lineal se puede expresar en la llamada forma estándar añadiendo variables de holgura o variables artificiales:

Minimizar Z = C1X1 + C2X2+……….CnXn Sujeto a : a11X1 + a12X2 + …….a1nXn + Xh1 = b1 a21X1 + a22X2 + …….a2nXn + Xh2 = b2 . . . . . . an1X1 + an2X2 + …….annXn + Xhn = bn X1 ≥0; X2 ≥0;………….Xn, Xh1..Xhn, ≥0

Las constantes b´s deben ser no-negativas.

Si alguna de ellas es negativa, la respectiva restricción se multiplica por -1.

CT-7611Programación Lineal: Método Simplex.

Para la solución de un problema de programación lineal mediante el método simplex, ese debe estar expresado en la llamada “formulación canónica”.

FORMULACIÓN CANÓNICA: Si un sistema tiene n variables y m ecuaciones, éste se encuentra en “forma canónica” cuando tiene m variables básicas ( variables que constituyen la solución); una por cada restricción.

En cada ecuación hay una sola variable básica, su coeficiente “a” es 1 y su coeficiente de costo en la función objetivo es cero.

Minimizar Z = C1X1 + C2X2+……….CnXn Sujeto a : a11X1 + a12X2 + …….a1nXn + Xh1 = b1 a21X1 + a22X2 + …….a2nXn + …….+ Xh2 = b2 . . . . . . am1X1 + am2X2 + …….amnXn + …………+Xhn = bn X1 ≥0; X2 ≥0;………….Xn, Xh1..Xhn, ≥0

CT-7611

Maximizar Z = 500X1 + 450X2 6X1 + 5X2 ≤ 60

10X1 + 20X2 ≤ 150 X1 ≤ 8 X1 ≥ 0 X2 ≥ 0

Programación Lineal: Método Simplex

Retornemos al ejemplo:

Maximizar Z = 500X1 + 450X2 6X1 + 5X2 + X3 = 60 10X1 + 20X2 + X4 = 150 X1 - X5 = 8 X1 ≥ 0 X2 ≥ 0

X3, X4 y X5 son variables de holgura: En este momento X3 y X4 están en la base de la solución (vértice), no así X5, debido a su signo.

CT-7611

Maximizar Z = 500X1 + 450X2 6X1 + 5X2 + X3 = 60 10X1 + 20X2 + X4 = 150 X1 - X5 = 8 X1 ≥ 0 X2 ≥ 0

Programación Lineal: Método Simplex

Maximizar Z = 500X1 + 450X2 6X1 + 5X2 + X3 = 60 10X1 + 20X2 + X4 = 150 X1 - X5 + Xa1 = 8 X1 ≥ 0 X2 ≥ 0

Para colocar el problema en “forma canónica”, se añade otra variable en aquellas restricciones (ahora de igualdad) no básicas, que en este caso se denominan “variables artificiales”.

CT-7611Programación Lineal : Método Simplex.


Expresado en esta forma, las variables básicas en este momento son X3, X4 y Xa1. Aquí empieza a trabajar el Método Simplex.

Si el problema tiene solución, las variables artificiales deben salir de la base por lo tanto, en la solución, su valor debe ser cero, de lo contrario el problema se declara infactible; en cambio, las variables de holgura, pueden o no salir de la base, es decir, pueden aparecer en la solución final.

El conjunto de variables básicas constituye un vértice del “polyhedron” .

CT-7611Programación Lineal : Método Simplex.


El método simplex procede estratégicamente modificando la base del sistema de ecuaciones, es decir, moviéndose de la mejor manera entre vértice y vértice hasta encontrar el vértice donde se obtiene la mejor solución.

La mayoría de los programas concebidos para resolver este tipo de problemas emiten un reporte donde describen:

1.- Variables del problema que están en la base (solución), y su valor.

2.- Variables de holgura que están en la solución y su valor.

3.- Variables duales del problema.

4.- Costos reducidos.

5.- Otro caudal de información que pudiera ser de interés en la solución.

CT-7611Como procede el Método Simplex ?. Ejemplo.

Maximizar Z = 3X1 + X2 + 3X3 s.a. : 2X1 + X2 + X3 ≤ 2 X1 + 2X2 + 3X3 ≤ 5 2X1 + 2X2 + X3 ≤ 6 X1 ≥ 0 , X2 ≥ 0, X2 ≥ 0

Z 1 -3 ‘1 -3 0 0 0 0

X4 0 2 1 1 1 0 0 2

X5 0 1 2 3 0 1 0 5

X6 0 2 2 1 0 0 1 6

Z 1 0 ½ -3/2 3/2 0 0 3

X1 0 1 ½ ½ ½ 0 0 1

X5 0 0 3/2 5/2 -1/2 1 0 4

X6 0 0 1 0 -1 0 1 4

Z 1 0 7/5 0 6/5 3/5 0 27/5

X1 0 1 1/5 0 3/5 -1/5 0 1/5

X3 0 0 3/5 1 -1/5 2/5 0 8/5

X6 0 0 1 0 -1 0 1 4

Z X1 X2 X3 X4 X5 X6 RHS

CT-7611Programación Lineal : Aplicación del

programa LINGO.

MAX Z = 16.95 * M + 24.95 * E;S. a.: 30 * M + 40 * E <= 19900; 40 * M + 85 * E <= 29700; M ≥ 0 E ≥ 0 solution:

Optimal solution found at step: 0

Objective value: 11478.50

Variable Value Reduced Cost M 530.0000 0.0000000 E 100.0000 0.0000000

Row Slack or Surplus Value Dual Price1 11478.50 1.0000002 0.0000000 0.46605263 0.0000000 0.7421052E-01

CT-7611Programación Lineal: formulación de un

problema de planificación de redes.

1

2

4

33

Asuma que en este sistema se prevé que la carga se duplique en los próximos 5 años por lo que habrá que reforzar la generación (4). Las posibilidades que se disponen para sacar la producción de (4) son corredores 4 -1 y 4 – 3.

Líneas X Cap. max.(MW)

1 - 2 0.2 100

1 - 3 0.4 80

2 - 3 0.4 100

Datos de líneas

corredor X Cap.max # max. de líneas

CostoU/MW

4 - 1 0.2 100 MW 100 MW 250

4 - 3 0.2 100 100 350

Datos de corredores

Barra Despacho (MW) Carga (MW)

1 60 120

2 120 140

3 0 220

4 320 0

Datos de barras

CT-7611Programación Lineal: formulación de un problema de planificación de redes (DC).

1

2

4

33

Se aplica modelo DC (lineal)

Para la red existente

Pij = bij (δi – δj); bij = 1/Xij

Los nuevos nexos se modelan como canales de potencia direccionales, simulando las posibilidades de flujo de potencia en cualquier dirección.

Min Z = 250 PD14 + 250 PD41 + 350 PD34 + 350 PD43

-7.5 δ1 + 5 δ2 + 2.5 δ3 + PG1 + PD14 - PD41 = 1.2

5 δ1 – 7.5 δ2 + 2.5 δ3 + PG2 = 1.4

2.5 δ1 + 2.55 δ2 - 5 δ3 + PG1 + PD43 – PD34 = 2.2

PG4 + PD14 - PD41 + PD34 - PD43 = 0.0

b12 (δ1 – δ2) ≤ 1.0b12 (δ2 – δ1) ≤ 1.0b13 (δ1 – δ3) ≤ 0.8b13 (δ3 – δ1) ≤ 0.8b23 (δ2 – δ3) ≤ 1.0b23 (δ3 – δ2) ≤ 1.0

δ1≥0; δ2≥0; δ1≥0

PD14≥0; PD41≥0

PD34≥0; PD43≥0

CT-7611Programación Lineal: Dualidad

Cada problema de Programación lineal está íntimamente relacionado con otro denominado “problema dual”.

Ambos problemas se construyen con la misma información pero si uno es de minimización, el otro es de maximización.

El valor óptimo de la función objetivo, si existe, es el mismo en ambos problemas.

En muchos casos la consideración simultánea de la solución para el problema “primal” y para el problema “dual”, aporta información relevante sobre el caso, en particular, en el sentido económico.

Primal Dual

Min Ct x Max y t b

Sujeto a: A x ≥ b Sujeto a: A t y ≤ c

x ≥ 0 y ≥ 0

CT-7611

Primal Dual

Minimizar z = 60 y1 + 150 y2 Maximizar Z = 500X1 + 450X2 s. a : 6y1 + 10y2 + y3 ≥ 500 s. a : 6X1 + 5X2 ≤ 60 5y1 + 20y2 ≥ 450 10X1 + 20X2 ≤ 150 y1 ≥ 0 X1 ≤ 8 y2 ≥ 0 X1 ≥ 0 X2 ≥ 0

Primal Dual

Min Ct x Max y t b

Sujeto a: A x ≥ b Sujeto a: A t y ≤ c

x ≥ 0 y ≥ 0

Programación Lineal: Dualidad

CT-7611Programación Lineal: Dualidad

Primal Dual

Minimizar z = 60 y1 + 150 y2 + 8y3 Maximizar Z = 500X1 + 450X2 s. a : 6y1 + 10y2 + y3 ≥ 500 s. a : 6X1 + 5X2 ≤ 60 5y1 + 20y2 ≥ 450 10X1 + 20X2 ≤ 150 y1 ≥ 0 X1 ≤ 8 y2 ≥ 0 X1 ≥ 0 y3 ≥ 0 X2 ≥ 0

t t t

t

C = [60 150 8] ; y = [y1 y2 y3] x = [x1 x2]

6 56 10 1 500

A = ; A = 10 20 ; b = 5 20 0 450

1 0

CT-7611Programación Mixta ( unas variables reales y

otras enteras).

En Programación Lineal (LP) el espacio de decisión es continuo en el sentido de que las variables pueden tomar valores fraccionales. Hay otros problemas en los cuales algunas variables requieren tomar valores enteros. En esos casos se requiere usar métodos de programación entera.

Los problemas de programación entera no son fáciles de resolver puesto que caen en el dominio del análisis combinatorio, lo que los diferencia de los LP.

Se han diseñado algoritmos especiales para resolver este tipo de problemas pero aún persisten dificultades para resolver problemas de gran tamaño.

El algoritmo que presenta, hasta ahora, el mejor comportamiento en la búsqueda de solución de este tipo de problemas, es el denominado “Branch and Bound” . A él nos dedicaremos en estas notas.


otras enteras).

Decisiones como las que se indican a continuación deben modelarse mediante variables enteras binarias (0 – 1):

a) Construir o no construir una planta o línea de transmisión.

b) Emprender un viaje o no.

c) Asignar una cuadrilla para trabajar en una ruta o no.

d) Etc.

Decisiones como las siguientes deben modelarse mediante variables enteras no-binarias:

1) Número máximo de líneas que se pueden construir en un corredor.2) Número de cajas de vasos de 200 cc.3) Número de trabajadores que deben ir en una cuadrilla.Etc.


otras enteras).



6X1 + 5X2 ≤ 60

10X1 + 20X2 ≤ 150

X1 ≤ 8

X1 ≥ 0

X2 ≥ 0

Regresemos al problema de producción de cajas de vasos.

2

6

4

8

10

12

2 4 6 8 10 12 14 16

o

oo

o o

Zona factible

X1=6.43, x2=4.28, Z = 5142

X1

X2

X1=8, x2=2.4, Z = 5080

X1=8, x2=0, Z = 4000

X1=0, x2=7.5, Z = 3375

Función Objetivo

●

●●

●

La solución óptima con LP resultó en

X1 = # cajas de vasos1 = 6.43

X2 = # cajas de vasos2 = 4.28

No luce razonable que se produzcan fracciones de cajas de vasos.

Este es un problema de Programación entera.


otras enteras).

2

6

4

8

10

12

2 4 6 8 10 12 14 16

o

oo

o o

Zona factible

X1=6.43, x2=4.28, Z = 5142

X1

X2

X1=8, x2=2.4, Z = 5080

X1=8, x2=0, Z = 4000

X1=0, x2=7.5, Z = 3375

Función Objetivo

●

●●

●

Pudiera pensarse intuitivamente que la solución entera de este problema sería la que resulte de aproximar el valor de las variables al entero más cercano. X1 = 6X2 = 4.La función objetivo es z = 4800U . Es esta la solución óptima?

Pudiéramos redondear por arriba X1 = 7X2 = 5, lo cual no es posible debido a que es un punto fuera de la región factible.

Resulta que la solución óptima para este problema es X1 = 8, X2 = 2 para un valor de la función objetivo de 4900U.

CT-7611Programación Mixta: Branch and Bound

2

6

4

8

10

12

2 4 6 8 10 12 14 16

o

oo

o o

Zona factible

X1=6.43, x2=4.28, Z = 5142

X1

X2

X1=8, x2=2.4, Z = 5080

X1=8, x2=0, Z = 4000

X1=0, x2=7.5, Z = 3375

Función Objetivo

●

●●

●

Branch and Bound : Es un procedimiento básicamente de “división y conquista”. La idea es partir la región factible en subregiones mas manejables y continuar la partición hasta encontrar la mejor solución bajo la condición de variables enteras.

Un problema mixto es un problema lineal que además está restringido por la condición de integralidad en algunas de sus variables.

Un problema entero es un problema lineal que además está restringido por la condición de integralidad en todas sus variables.


Branch and Bound :

Considérese el siguiente problema:Maximizar Z = 5X1 + 8X2 s. a. X1 + X2 ≤ 6 5X1 + 9X2 ≤ 45 X1 ≥ 0 entera X2 ≥ 0 enteraEn la gráfica se muestra la solución del LP. Se dice del LP asociado al PE.

1

3

2

4

5

6

1 2 3 4 5 6 7 8

X1

X2

●

●9

Zona factible

●

Solución LP óptima

x1=2.25, x2=3.75, Z =41.25

Dado que un problema de programación mixta (PM) o entera (PE) es mas restringido que el correspondiente en LP, en el caso de maximización, la solución del LP es el máximo valor(“upper bound”)que puede tomar el PM o PE. De la misma manera un punto se solución en PM o PE es un “lower bound” del LP.


Branch and Bound :

Considérese el siguiente problema:Maximizar Z = 5X1 + 8X2 s. a. X1 + X2 ≤ 6 5X1 + 9X2 ≤ 45 X1 ≥ 0 entera X2 ≥ 0 entera

1

3

2

4

5

6

1 2 3 4 5 6 7 8

X1

X2

●

●9

Zona factible

●


x1=2.25, x2=3.75, Z =41.25

Solución del LP = 41.25 implica que

Solución del PE planteado es z* ≤ 41

x1 = 2.25 x2 = 3.73 pero ellas deben ser enteros en la solución óptima, por tanto se puede dividir la región factible para tratar de hacerlos enteros.

En la solución entera x2 ≤ 3 ó x2 ≥ 4. Así que la región factible la dividiremos considerando esas dos condiciones.


Branch and Bound :


Si hubiésemos escogido la variable x1, la subdivisión habría sido x1 ≤ 2 y x1 ≥ 3.

1

3

2

4

5

6

1 2 3 4 5 6 7 8

X1

X2

●

●9

Zona factible

L2

●


x1=2.25, x2=3.75, Z =41.25

Zona factible L1

●

● ●

●

●


Branch and Bound :


Si hubiésemos escogido la variable x1, la subdivisión habría sido x1 ≤ 2 y x1 ≥ 3.

Así plantearíamos dos sub-problemas: uno para cada región factible resultante de la división. Se genera así, un árbol de búsqueda como se muestra a continuación.

1

3

2

4

5

6

1 2 3 4 5 6 7 8

X1

X2

●

●9

Zona factible

L2

●


x1=2.25, x2=3.75, Z =41.25

Zona factible L1

●

● ●

●

●


L0

X1 = 2.25X2 =3.75Z = 41.25

z* ≤ 41

L1 L2

x2 ≥ 4 x2 ≤ 3

Maximizar Z = 5X1 + 8X2 s. a. X1 + X2 ≤ 6 5X1 + 9X2 ≤ 45 X1 ≥ 0 X2 ≥ 0

Maximizar Z = 5X1 + 8X2 s. a. X1 + X2 ≤ 6 5X1 + 9X2 ≤ 45 X1 ≥ 0 entera 0≤ X2 ≤ 3 entera

Maximizar Z = 5X1 + 8X2 s. a. X1 + X2 ≤ 6 5X1 + 9X2 ≤ 45 X1 ≥ 0 entera X2 ≥ 4 entera


L0

X1 = 2.25X2 =3.75Z = 41.25

z* ≤ 41

L1

X1 = 1.8X2 =4Z = 41

L2

X1 = 3X2 = 3Z = 39

x2 ≥ 4 x2 ≤ 3

(*)


(*) indica que el árbol no se subdividirá más allá de este punto por esta rama, es decir la región no necesita ser subdividida.

CT-7611Programación Mixta

: Branch and BoundL0

X1 = 2.25X2 =3.75Z = 41.25

z* ≤ 41

L1

X1 = 1.8X2 =4Z = 41

L2

X1 = 3X2 = 3Z = 39

L3

Infactible.Incumple restr. 2

L4

X1 = 1X2 =4.44z = 40.56

x2 ≥ 4 x2 ≤ 3

(*)

x1 ≥ 2x1 ≤ 1

Maximizar Z = 5X1 + 8X2 s. a. X1 + X2 ≤ 6 5X1 + 9X2 ≤ 45 X1 ≥ 0 X2 ≥ 0

(*)Maximizar Z = 5X1 + 8X2 s. a. X1 + X2 ≤ 6 5X1 + 9X2 ≤ 45 X1 ≥ 2 entera X2 ≥ 4 entera

Maximizar Z = 5X1 + 8X2 s. a. X1 + X2 ≤ 6 5X1 + 9X2 ≤ 45 0≤ X1 ≤ 1 entera X2 ≥ 4 entera

CT-7611Programación Mixta

: Branch and Bound L0

X1 = 2.25X2 =3.75Z = 41.25

z* ≤ 41

L1

X1 = 1.8X2 =4Z = 41

L2

X1 = 3X2 = 3Z = 39

L3

Infactible.Incumple restr. 2

L6

X1 = 0X2 = 5Z = 40

z* ≥ 40

L5

X1 = 1X2 =4Z = 37

L4

X1 = 1X2 =4.44z = 40.56

x2 ≥ 4 x2 ≤ 3

(*)

x1 ≥ 2x1 ≤ 1

x2 ≥ 5x2 ≤ 4

(*)(*)


(*)

Solución óptima : X1 = 0, X2 = 5, Z = 40

CT-7611

Formulación de un problema sencillo.

Asumamos “I” centros de carga y “J” sitios posibles donde localizar las fuentes de energía (S/E); Cij representa el costo de alimentar el centro de carga i desde la fuente j. Se desea determinar cual es la mejor (menos costosa), ubicación de las fuentes y la conexión de los centros de cargas a estas.

Definimos Variables lógicas de decisión

Yj = 1 si el sitio j es seleccionado para ubicar una fuente

= 0 si no lo es..

Xij = 1 si el centro de carga i se asigna a la fuente j

= 0 si no se asigna a esa fuente.

Programación Mixta

: Branch and Bound

CT-7611Programación Mixta:

Branch and Bound.


Asumamos que cada centro de carga debe estar conectado a una sola fuente.

J

∑Xij = 1 ; i = 1 , 2 , 3, ………….,I.

J=1

Por supuesto no se debe asignar ningún centro de carga a una fuente que no existe.

I

∑Xij ≤ Yj I; j = 1 , 2 , 3, ………….,J.

i=1Esta restricción dice que debido a que las variables Xij son binarias, su suma nunca excederá el valor de I, esto se cumple en esta restricción, cuando Yj = 1; si Yj = 0, implica que Xij = 0. En otras palabras, no puede haber más de I centros de carga conectados a una sola fuente j.

CT-7611Formulación de un problema sencillo.

El costo de asignar un centro de carga i a su correspondiente fuente se puede modelar como:

J

Ci = ∑Cij xij , dado que sólo un Xij será dsitinto de cero

J=1

Por supuesto no se debe asignar ningún centro de carga a una fuente que no existe.

I

∑xij ≤ Yj I; j = 1 , 2 , 3, ………….,J.

i=1

CT-7611


Supongamos que hay un centro de carga en particular que requiere de alta disponibilidad en el servicio, por lo que se exige que sea alimentado desde dos fuentes , bien desde las fuentes 1 y 2 o desde las fuentes 3 y 4.

Se define la variable “ Y “ para modelar la conexión de ese centro.

Y1 + Y2 ≥ 2 Y

Y3 + Y4 ≥ 2 (1-Y)

CT-7611Formulación de un problema sencillo.

Resumen del modelo.

Min ∑ Ci = ∑Cij Xij

S. a.

J

∑Xij = 1 ; i = 1 , 2 , 3, ………….,I.

J=1

I

∑Xij ≤ Yj I; j = 1 , 2 , 3, ………….,J.

i=1

Y1 + Y2 ≥ 2 YY3 + Y4 ≥ 2 (1-Y)

Xij, Yj, Y, son variables binarias. i = 1 , 2 , 3, ………….,I, j = 1 , 2 , 3, ………….,J.

CT-7611Formulación de un problema de planificación

de transmisión.

Generación (MW) Carga Costo por generación

Nodo Nominal Despacho (MW) Bs

1 150.0 50.0 80.0 0.01

2 0.0 0.0 240.0 0.00

3 360.0 165.0 40.0 0.01

4 0.0 0.0 160.0 0.00

5 0.0 0.0 240.0 0.00

6 600.0 545.0 0.0 0.01


de transmisión.

Datos de los corredores para el sistema de 6 barras (Existentes y candidatos)

Corredor Nodo Nodo No. de circuitosReactanci

a Capacidad Costo

No. Terminal 1 Terminal 2 existentes p.u. (MW) Bs

1 1 2 1 0.40 100 0

2 1 4 1 0.60 80 0

3 1 5 1 0.20 100 0

4 2 3 1 0.20 100 0

5 2 4 1 0.40 100 0

6 3 5 1 0.20 100 100

7 6 2 0 0.20 100 150

8 6 4 0 0.20 100 150

9 6 5 0 0.20 100 305


de transmisión.


de transmisión. Modelo

Minimizar:

p q qq

qvq

qfP

Pv

psn k sn k wn k wn p

pf

kwnk

knwnwk

knwsnk

knsnsk

kns

PGGCXGGCPGGC

GXGCXCXCXCXCOFr r t t

t

t

t

t

r

r

r

r

, , , ,

..

Restricciones. a.- Balance de Potencia en los Nodos:

La ecuación tiene dos formas dependiendo si el nodo estaba ya en la red o si el nodo es nuevo. : Para nodos existentes en la red la ecuación es la siguiente:

s s k s knsksnkssnn

ssn

r r

rrPPABAB

n k n

npk

nwkwnk

t t

ttPLPGPP

Para nodos nuevos la ecuación es la siguiente:

n k n

wqk

wnknwk

t t

ttPLPGPP



b.- Restricción de Acople:

Para los nodos existentes en la red:

0 Ppp XGGPGPara los nodos nuevos:

0 qqq XGGPG



Para los nodos existentes en la red:

0rr snksnsnk ABP

0rr nsksnnsk ABP

0rr snksnk PmáxXP

0rr nsknsk PmáxXP

Para los nodos nuevos:

0tt wnkwnwnk ABP

0tt nwkwnnwk ABP

0tt wnkwnk PmáxXP

0tt nwknwk PmáxXP

c.- Control de la transmisión por corredor



d.- Restricción de capacidad de transmisión en los elementos del sistema:

Las líneas existentes tienen limitaciones con respecto a la cantidad de potencia que pueden transmitir.

Para dirección ns: Para dirección sn:

PmáxAAB snsn )( PmáxAAB nsns )(



Para los nodos existentes en la red:a

MXMXMAAAAtttt nwkwnknwkwnknw **

b MXMXMAAAAtttt nwkwnknwkwnkwn **

Para los nodos nuevos:

MXMXMAAAArrrr nsksnknsksnkns **

MXMXMAAAArrrr nsksnknsksnksn **

e.- Control del Límite Angular por Corredor:

CT-7611

• ESTIMACIÓN DE DEMANDA

Dicta en gran medida la capacidad y tiempo de establecimiento de nuevas plantas y nuevos refuerzos de transmisión en el sistema.

Un plan de expansión de la generación por ejemplo, será el resultado de la combinación de:

1.- Estudios de demanda

2.- Capacidad previa instalada

3.- Costos de producción

4.- Estándares requeridos en la producción.

5.- Factores de seguridad: Mínimos técnicos, capacidad de reserva, etc.

CT-7611

• ESTIMACIÓN DE LA DEMANDA

En la estimación de la demanda se utilizan diferentes esquemas:

a) Energía (MWh) y Factor de carga (MW promedio/MW Max.), que luego se convierte a MW.

b) Extrapolación. Valores pasados de la demanda se ajustan, usualmente mediante mínimos cuadrados, a una función de tiempo y luego se extrapola hasta el tiempo que se desee a futuro.

CT-7611


c) Métodos estocásticos (ME). Cualquier método probabilístico que use un modelo estocástico. Se especifica la forma del ME; se determinan entradas aleatorias no conocidas a partir de los datos históricos y se calcula la respuesta (demanda) del modelo ME a futuro.

d) Modelos de serie de tiempo. Incluye varios modelos en el tiempo, considerando siempre que consisten de dos componentes: Una verdadera (determinística) y otra falsa (ruido): esta última sigue una función probabilística con media =0.

CT-7611CRONOGRAMA DE ACTIVIDADES


La precisión en la estimación de la demanda es determinante en la definición de los refuerzos del sistema. Si la precisión es baja seguramente se tendrá suministro deficiente, pérdidas en venta, etc., Si la precisión es alta puede conducir a problemas financieros debido a una alta inversión y baja utilización.

Una expresión bastante utilizada para estimar el crecimiento de la demanda es la exponencial.

Ly = L0 (1+β) y

Esto se corresponde con una tendencia de que la demanda se duplica cada 10 años.

CT-7611

BIBLIOGRAFIA

1. BILLINTON, ROY-POWER SYSTEM RELIABILITY EVALUATION.

2. ENDRENYI, J –RELIABILITY MODELING IN ELECTRIC POWER SYSTEMS.

3. WOLLENBERG, BRUCE F. – POWER GENERATION, OPERATION AND CONTROL

4. SULLIVAN, ROBERT LEE – POWER SYSTEM PLANNING.

5. GöNEN, TURAN - ELECTRIC POWER TRANSMISSION SYSTEM ENGINEENING: ANALISIS AND DESIGN.

CT-7611

FIN PARTE I

fundamentos de planificación

Documents