Pular para o conteúdo

Estrutura e escalonamento do PL

Este capítulo descreve a estrutura de colunas e linhas do PL do estágio e seu condicionamento numérico: a ordem de suas regiões de colunas e famílias de linhas, o escalonamento (scaling) de custos, o pré-escalonamento de colunas e linhas pela média geométrica e o desescalonamento das variáveis duais das linhas e dos custos reduzidos que fornecem os coeficientes dos cortes.

Ordem de leitura: Gerenciamento de cortes → este capítulo → Aproveitamento de base do PL

A figura lista, à esquerda, as regiões de colunas do PL do estágio em sua ordem e, à direita, suas famílias de linhas em sua ordem. As colunas começam com o armazenamento de saída, as parcelas de água em trânsito (in-transit buckets) de saída e as posições do anel de despacho antecipado (commitment ring slots) de saída; seguem-se o armazenamento de entrada fixado, as parcelas de água em trânsito e as posições do anel de despacho antecipado de entrada fixadas e θ\theta, e as colunas de equipamentos e de folga encerram a estrutura. As defasagens de afluência e a afluência realizada não têm coluna: a afluência realizada é calculada antes da resolução e entra nas linhas que a leem pelos seus lados direitos (Formulação do PL §5, Folding do PAR(p)). As linhas começam com o balanço hídrico e terminam com os cortes de Benders, acrescentados após as linhas próprias do estágio. A aresta indica a origem dos coeficientes de corte de armazenamento, das parcelas de água em trânsito e das posições do anel: o custo reduzido de uma coluna de entrada fixada. Os coeficientes das defasagens de afluência vêm dos duais pela regra da cadeia (Folding do PAR(p) §4).

Colunas, em ordemFamílias de linhas, em ordemArmazenamento de saídaParcelas de águaem trânsito de saídaPosições do anel de despachoantecipado de saídaArmazenamento, parcelas de água em trânsitoe posições do anel de entrada fixadosθEquipamentos e folgasBalanço hídricoDefinição das parcelas de água em trânsitoAtendimento à demandaPlanos da FPHAEvaporaçãoPisos e teto operativosEnchimento e pisos de volume mortoCompromisso: retirada · depósito · transporteRestrições genéricasCortes de Benders custo reduzido →coeficiente do corte

O PL do estágio usa uma estrutura fixa de colunas e linhas que posiciona as variáveis de estado primeiro, seguidas das colunas auxiliares e de equipamentos. O armazenamento, as parcelas de água em trânsito e as posições do anel de despacho antecipado são fixados por limites das colunas de estado de entrada (Aumento do espaço de estados §2, §5, §6), e os seus coeficientes de corte são lidos como os custos reduzidos dessas colunas — portanto, é a ordem fixa das colunas, e não uma ordem fixa das linhas, que permite a extração contígua dos coeficientes. Com N=∣H∣N = |\mathcal{H}| usinas hidrelétricas e BB = o número total de parcelas de água em trânsito (a soma, sobre as usinas receptoras, da profundidade de defasagens de chegada de cada usina — Aumento do espaço de estados §6):

Estrutura das colunas:

RegiãoQuantidadeDescrição
storageNNVolumes armazenados de saída (estado) — primeiro
transit_buckets_outBBVolumes das parcelas de água em trânsito de saída (estado, usina como índice externo, defasagem como índice interno) — após o armazenamento
commit_outuma por posição do anel de despacho antecipado (Aumento do espaço de estados §1)Posições do anel de despacho antecipado de saída (estado, posição como índice externo, usina como índice interno) — após as parcelas de água em trânsito de saída
storage_inNNVolumes armazenados de entrada (fixados, Aumento do espaço de estados §2) — após as posições do anel de saída
transit_buckets_inBBVolumes das parcelas de água em trânsito de entrada (fixados, Aumento do espaço de estados §6) — após storage_in
commit_inuma por posição do anel de despacho antecipado (Aumento do espaço de estados §1)Posições do anel de despacho antecipado de entrada (fixadas, Aumento do espaço de estados §5) — após as parcelas de água em trânsito de entrada
theta11Variável de custo futuro — a última do prefixo de estado

As colunas de equipamentos e de folga seguem imediatamente após θ\theta, nesta ordem: em um estágio cronológico, o armazenamento ao final de cada patamar, exceto o último; vazão turbinada, vertimento e desvio; geração térmica; as decisões de antecipação de despacho térmico; fluxos nas linhas em cada sentido; déficit e excesso; as folgas de não negatividade da vazão afluente, em todos os métodos de tratamento da vazão exceto none; geração da FPHA; evaporação e suas folgas; as folgas de retirada; as folgas de violação operativa; geração não despachável; vazão bombeada; contratos de importação e exportação; as folgas das restrições genéricas; e as folgas do piso de enchimento e do piso flexível de volume morto. A família de colunas de vazão turbinada e a família de colunas de geração da FPHA são indexadas por célula (usina hidrelétrica, barramento), e não por usina — uma coluna por célula (Formulação do PL §3, §6) —, enquanto as demais colunas de equipamentos hidráulicos (vertimento, desvio) permanecem indexadas por usina. Assim como o armazenamento de saída e as posições do anel de despacho antecipado, o bloco de parcelas de água em trânsito de saída ocupa as colunas de seus próprios índices de estado: ele contém o volume ainda em trânsito em cada trecho da cascata, definido por linhas de definição das parcelas de água em trânsito no próprio PL (Aumento do espaço de estados §6), e não fixado, e o bloco de parcelas de água em trânsito de entrada é a cópia de entrada fixada correspondente, lida para o termo de chegada defasada do balanço hídrico e para o coeficiente do corte (Aumento do espaço de estados §6). Um bloco de equipamentos atende às térmicas com antecipação de despacho: uma coluna de decisão por térmica com antecipação, que representa o compromisso decidido neste estágio para o seu estágio de entrega (Aumento do espaço de estados §5).

O estado de defasagens de afluência não tem coluna: as defasagens de entrada e o ruído da abertura dão a afluência realizada z^h\hat{z}_h antes da resolução, e ela entra nas linhas que a leem como constante do lado direito (Formulação do PL §5).

Estrutura das linhas:

Como o estado é fixado por limites das colunas (Aumento do espaço de estados §2, §5, §6), e não por linhas de igualdade, o PL não tem linhas de fixação de estado, e o modelo de afluências não tem linhas de definição (Folding do PAR(p) §1). As famílias de linhas vêm nesta ordem: balanço hídrico, definição das parcelas de água em trânsito (Aumento do espaço de estados §6), atendimento à demanda, planos da FPHA, evaporação, as linhas operativas (vazão defluente mínima, vazão defluente máxima, vazão turbinada mínima, geração mínima e, em seguida, as linhas de vazão turbinada e geração mínimas da usina e as linhas de vazão turbinada e geração máximas da usina, para uma usina hidrelétrica com várias células, Formulação do PL — Mínimo e máximo da usina), o piso de enchimento e o piso flexível de volume morto, as linhas de retirada, de depósito e de transporte do compromisso (Aumento do espaço de estados §5) e as restrições genéricas; Visão geral do PL do estágio contabiliza cada família. As linhas dos cortes de Benders são acrescentadas após elas (Formulação do PL §11).

Cada coordenada de armazenamento, de parcela de água em trânsito e de posição do anel de despacho antecipado do estado de entrada é fixada em sua própria coluna do PL — a coluna de armazenamento de entrada, a coluna de entrada da parcela de água em trânsito, a coluna de entrada da posição do anel —, e seu coeficiente de corte é o custo reduzido dessa coluna (Aumento do espaço de estados §2, Gerenciamento de cortes). O mapeamento de uma coordenada de estado para sua coluna fixada é fixo, e cada uma dessas regiões de colunas de estado de entrada é contígua, de modo que os coeficientes de armazenamento, das parcelas de água em trânsito e das posições do anel de despacho antecipado são obtidos pela leitura de algumas fatias contíguas do vetor de custos reduzidos. As defasagens de afluência de entrada não são colunas do PL: seus valores visitados entram na afluência realizada e nos lados direitos dos cortes, e seus coeficientes de corte vêm dos duais das linhas e dos cortes pela regra da cadeia (Folding do PAR(p) §4).

Exemplo resolvido (N=3N = 3, uma profundidade de defasagens de afluência Pmax⁡=2P^{\max} = 2, sem térmica com antecipação de despacho e sem trecho com tempo de viagem): a região de armazenamento contém 3 colunas e a região de armazenamento de entrada contém 3, de modo que θ\theta é a 7ª coluna. O número de variáveis de estado (armazenamento + defasagens de afluência) é N(1+Pmax⁡)=9N(1 + P^{\max}) = 9, das quais apenas as 3 coordenadas de armazenamento têm colunas no PL.

O PL do estágio é condicionado numericamente por um procedimento de escalonamento em três etapas, aplicado uma única vez na construção do modelo-base (template). O escalonamento estreita a dispersão das magnitudes dos coeficientes da matriz de restrições, o que costuma melhorar o comportamento numérico do método simplex, sem alterar o argmin da otimização; ele não dá nenhuma garantia sobre o número de condição da matriz.

Todos os coeficientes da função objetivo (exceto a variável de custo futuro θ\theta) são divididos por uma constante positiva fixa KK, escolhida uma vez por estudo. KK escala uniformemente o domínio dos custos e não altera a matriz de restrições nem a região viável, de modo que o argmin do PL é invariante em relação a ele e quaisquer duas escolhas de KK concordam em aritmética exata:

c~j=cjKfor all j≠θ\tilde{c}_j = \frac{c_j}{K} \quad \text{for all } j \neq \theta

A variável θ\theta mantém um coeficiente não escalonado, o fator de desconto de um passo dt→t+1d_{t \to t+1}: cada linha de corte é θ≥Rscaled+∑jβjscaledxj\theta \geq R^{scaled} + \sum_j \beta_j^{scaled} x_j sobre as colunas jj de estado de saída, sendo seu lado direito (Formulação do PL §11) e cada coeficiente o valor na unidade original dividido por KK, de modo que θ\theta já está no espaço de custos escalonado. A função objetivo do PL é ∑jc~jxj+dt→t+1 θ\sum_j \tilde{c}_j x_j + d_{t \to t+1} \, \theta, e a função objetivo escalonada total é igual a (Cstage+dt→t+1 Cfuture)/K(C_{stage} + d_{t \to t+1} \, C_{future}) / K. O fator de cada estágio leva o custo de cada estágio posterior ao estágio 1 exatamente uma vez (Formulação da taxa de desconto). Todas as saídas no domínio de custos (valores da função objetivo, variáveis duais, decomposições de custo) são multiplicadas por KK no momento do relatório para recuperar as unidades originais.

Após o escalonamento de custos, cada coluna jj recebe um fator de escala por uma passagem de escalonamento pela média geométrica (Tomlin, 1975; Elble & Sahinidis, 2012), que torna a maior e a menor magnitude não nula da coluna recíprocas uma da outra:

djcol=1max⁡i∣Aij∣⋅min⁡i∣Aij∣d_j^{col} = \frac{1}{\sqrt{\max_i |A_{ij}| \cdot \min_i |A_{ij}|}}

em que o máximo e o mínimo são tomados sobre os elementos não nulos da coluna jj. As colunas sem elementos não nulos e as colunas das posições do anel de despacho antecipado recebem djcol=1d_j^{col} = 1. A transformação substitui:

  • Elementos da matriz: A~ij=Aij⋅djcol\tilde{A}_{ij} = A_{ij} \cdot d_j^{col}
  • Coeficientes da função objetivo: c~j=cj⋅djcol\tilde{c}_j = c_j \cdot d_j^{col}
  • Limites das colunas: l~j=lj/djcol\tilde{l}_j = l_j / d_j^{col}, u~j=uj/djcol\tilde{u}_j = u_j / d_j^{col}

Após o escalonamento de colunas, cada linha ii recebe um fator de escala pela mesma fórmula da média geométrica, aplicada à matriz já escalonada por colunas:

dirow=1max⁡j∣A~ij∣⋅min⁡j∣A~ij∣d_i^{row} = \frac{1}{\sqrt{\max_j |\tilde{A}_{ij}| \cdot \min_j |\tilde{A}_{ij}|}}

A transformação substitui:

  • Elementos da matriz: Aˇij=A~ij⋅dirow\check{A}_{ij} = \tilde{A}_{ij} \cdot d_i^{row}
  • Limites das linhas: lˇirow=lirow⋅dirow\check{l}_i^{row} = l_i^{row} \cdot d_i^{row}, uˇirow=uirow⋅dirow\check{u}_i^{row} = u_i^{row} \cdot d_i^{row}

Os limites das colunas e os coeficientes da função objetivo não são modificados pelo escalonamento de linhas.

O escalonamento combinado produz a forma padrão Dr⋅A⋅DcD_r \cdot A \cdot D_c, em que DrD_r e DcD_c são matrizes diagonais de escala.