Questão 1: Produzindo expressões para o operador Lagrangiano
Seja o problema de “Lot-sizing” Capacitado Multiproduto:
\begin{aligned} \min \sum_{i} \sum_{t}\left\{p_{t}^{i} x_{t}^{i}+f_{t}^{i} y_{t}^{i}+h_{t}^{i} s_{t}^{i}\right\} & \\\ s_{t-1}^{i}+x_{t}^{i}=d_{t}^{i}+s_{t}^{i} & \text { for all } i, t \\\ x_{t}^{i} \leq M y_{t}^{i} & \text { for all } i, t \\\ \sum_{i} \alpha^{i k} x_{t}^{i}+\sum_{i} \beta^{i k} y_{t}^{i} \leq L_{t}^{k} & \text { for all } t, k \\\ x_{t}^{i}, s_{t}^{i} \geq 0, y_{t}^{i} \in\{0,1\} & \text { for all } i, t \end{aligned}
Produza a Relaxação Lagrangeana do problema obtida pela dualização das restrições (2.9)

Passo 1

O enunciado nos dá o problema de lot-sizing capacitado multiproduto com as variáveis e restrições abaixo (pego exatamente do enunciado):
  • Variáveis: x_{t}^{i} (produção do item i no período t), y_{t}^{i}\in\{0,1\} (indicadora de abertura de produção), s_{t}^{i} (estoque do item i no período t).
  • Parâmetros: custos p_{t}^{i} (custo variável por unidade), f_{t}^{i} (custo fixo de abrir produção), h_{t}^{i} (custo de estocagem), demanda d_{t}^{i}, grande M, coeficientes \alpha^{ik},\beta^{ik} e capacidades L_{t}^{k}.
  • Restrições (lista conforme enunciado):
    1. Balanço de estoque: s_{t-1}^{i}+x_{t}^{i}=d_{t}^{i}+s_{t}^{i} para todo i,t.
    2. Vinculação produção–decisão: x_{t}^{i}\le M y_{t}^{i} para todo i,t.
    3. Capacidades de recurso/linha: \sum_{i} \alpha^{i k} x_{t}^{i}+\sum_{i} \beta^{i k} y_{t}^{i} \leq L_{t}^{k} para todo t,k.
      O enunciado pede: produzir a Relaxação Lagrangeana obtida pela dualização das restrições (2.9). Vou interpretar que a etiqueta (2.9) corresponde às restrições de capacidade por recursos/linhas (a terceira restrição acima), porque é a típica restrição dualizada em lot-sizing para decompor por produto. Assim as restrições dualizadas são
\sum_{i} \alpha^{i k} x_{t}^{i}+\sum_{i} \beta^{i k} y_{t}^{i} \le L_{t}^{k}\qquad\text{para todo }t,k.
Não começo a resolver ainda; apenas enumerei o que o problema dá e o que é pedido.

Passo 2

O que é fazer uma relaxação Lagrangeana (rapidamente, sem formalismo excessivo): dado um conjunto de restrições que atrapalham a separação do problema, introduz-se multiplicadores (variáveis duais) não-negativos associados a essas restrições, multiplica-se cada restrição pelo seu multiplicador e adiciona-se esse produto ao objetivo (com sinal positivo), passando essas restrições para o objetivo. Assim o problema relaxado deixa de ter essas restrições explicitamente, e o termo adicionado ao objetivo penaliza violações delas. Depois define-se a função objetivo Lagrangiana que depende dos multiplicadores; o problema dual Lagrangiano consiste em escolher os multiplicadores para maximizar o menor valor dessa função (isto fornece um limite inferior para o problema original).
Aplicando isso ao nosso caso: para cada restrição de capacidade no período t e recurso k introduzimos um multiplicador \lambda_{t}^{k}\ge 0. A penalização que acrescentamos ao objetivo é \lambda_{t}^{k} vezes o lado esquerdo menos o lado direito da restrição (normalmente escreve-se \lambda(\text{esquerda}-\text{direita})). Então a Lagrangiana é o objetivo original mais a soma dessas penalizações.

Passo 3

Escrevendo explicitamente a função Lagrangiana (primeiro nível, sem rearranjar ainda). O problema original tem objetivo
\sum_{i}\sum_{t}\bigl\{p_{t}^{i} x_{t}^{i}+f_{t}^{i} y_{t}^{i}+h_{t}^{i} s_{t}^{i}\bigr\}.
Ao dualizar as restrições de capacidade adicionamos
\sum_{t}\sum_{k}\lambda_{t}^{k}\Bigl(\sum_{i}\alpha^{i k} x_{t}^{i}+\sum_{i}\beta^{i k} y_{t}^{i}-L_{t}^{k}\Bigr), \qquad\text{com }\lambda_{t}^{k}\ge 0.
Portanto a função Lagrangiana (para um vetor de multiplicadores \lambda=(\lambda_{t}^{k})) é, ao minimizar sobre as variáveis originais sujeitas às demais restrições (balanço, vínculo x\le M y, integrais em y e não-negatividades):
\mathcal{L}(\lambda)=\min_{\substack{x,s,y\\\ s_{t-1}^{i}+x_{t}^{i}=d_{t}^{i}+s_{t}^{i}\\\ x_{t}^{i}\le M y_{t}^{i},\;y_{t}^{i}\in\{0,1\},\;x_{t}^{i},s_{t}^{i}\ge0}} \Biggl\{\sum_{i}\sum_{t}\bigl(p_{t}^{i} x_{t}^{i}+f_{t}^{i} y_{t}^{i}+h_{t}^{i} s_{t}^{i}\bigr) +\sum_{t}\sum_{k}\lambda_{t}^{k}\Bigl(\sum_{i}\alpha^{i k} x_{t}^{i}+\sum_{i}\beta^{i k} y_{t}^{i}-L_{t}^{k}\Bigr)\Biggr\}.

Passo 4

Agora reorganizamos a expressão agrupando termos por i e por t, e isolando o termo constante que depende só de \lambda. Desenvolvendo a soma de penalizações e recolhendo:
\begin{aligned} \mathcal{L}(\lambda) &= \min_{x,s,y\in X}\Biggl\{\sum_{i}\sum_{t}\Bigl(p_{t}^{i} x_{t}^{i}+f_{t}^{i} y_{t}^{i}+h_{t}^{i} s_{t}^{i} +\sum_{k}\lambda_{t}^{k}\alpha^{i k} x_{t}^{i}+\sum_{k}\lambda_{t}^{k}\beta^{i k} y_{t}^{i}\Bigr)\\\ &\qquad\qquad\qquad\qquad\qquad\qquad -\sum_{t}\sum_{k}\lambda_{t}^{k} L_{t}^{k}\Biggr\}, \end{aligned}
onde X denota o conjunto definido pelas outras restrições: balanço de estoque, vínculo x\le M y, integridade de y e não-negatividade de x,s.
Note que o termo -\sum_{t}\sum_{k}\lambda_{t}^{k} L_{t}^{k} é constante durante a minimização sobre x,s,y, pois depende apenas de \lambda. Os demais termos podem ser agrupados por par (i,t). Definimos custos modificados (custos reduzidos) por:
\tilde p_{t}^{i} \coloneqq p_{t}^{i} + \sum_{k}\alpha^{i k}\lambda_{t}^{k}, \qquad \tilde f_{t}^{i} \coloneqq f_{t}^{i} + \sum_{k}\beta^{i k}\lambda_{t}^{k}.
Com isso a Lagrangiana fica
\mathcal{L}(\lambda)= -\sum_{t}\sum_{k}\lambda_{t}^{k} L_{t}^{k} \;+\; \sum_{i}\min_{\substack{x^{i},s^{i},y^{i}\\\ s_{t-1}^{i}+x_{t}^{i}=d_{t}^{i}+s_{t}^{i}\\\ x_{t}^{i}\le M y_{t}^{i},\;y_{t}^{i}\in\{0,1\}}} \sum_{t}\bigl(\tilde p_{t}^{i} x_{t}^{i}+\tilde f_{t}^{i} y_{t}^{i}+h_{t}^{i} s_{t}^{i}\bigr).
Isto mostra a decomposição: para um dado vetor \lambda a minimização separa-se em subproblemas independentes por produto i (cada subproblema envolve só as variáveis \{x_{t}^{i},s_{t}^{i},y_{t}^{i}\}_{t} sujeitas ao balanço e ao vínculo local).

Passo 5

Expressão do problema dual Lagrangiano. A função objetivo Lagrangiana \mathcal{L}(\lambda) dá, para cada \lambda\ge 0, um valor que é um limite inferior do problema primal. O dual Lagrangiano consiste em escolher \lambda para maximizar esse valor:
\text{(Dual Lagrangiano)}\qquad \max_{\lambda\ge 0}\; \mathcal{L}(\lambda),
ou seja
\boxed{\displaystyle \max_{\lambda_{t}^{k}\ge0}\; \left\{ -\sum_{t}\sum_{k}\lambda_{t}^{k} L_{t}^{k} +\sum_{i}\; \min_{\substack{x^{i},s^{i},y^{i}\\\ s_{t-1}^{i}+x_{t}^{i}=d_{t}^{i}+s_{t}^{i}\\\ x_{t}^{i}\le M y_{t}^{i},\;y_{t}^{i}\in\{0,1\}}} \sum_{t}\bigl(\tilde p_{t}^{i} x_{t}^{i}+\tilde f_{t}^{i} y_{t}^{i}+h_{t}^{i} s_{t}^{i}\bigr)\right\}.}
Aqui cada subproblema de item i é um problema de lot-sizing unicapacitado (com custos modificados \tilde p,\tilde f e mesmos h) e pode ser resolvido separadamente para avaliar \mathcal{L}(\lambda). O termo -\sum_{t,k}\lambda_{t}^{k}L_{t}^{k} é apenas uma constante subtraída que penaliza \lambda.

Passo 6

Resumo prático / interpretação que ajuda na prova:
  • Introduzir \lambda_{t}^{k}\ge0 para cada restrição de capacidade e adicionar \lambda_{t}^{k}(\sum_{i}\alpha^{ik}x_{t}^{i}+\sum_{i}\beta^{ik}y_{t}^{i}-L_{t}^{k}) ao objetivo.
  • Reagrupar termos para obter custos reduzidos \tilde p_{t}^{i}=p_{t}^{i}+\sum_{k}\alpha^{ik}\lambda_{t}^{k} e \tilde f_{t}^{i}=f_{t}^{i}+\sum_{k}\beta^{ik}\lambda_{t}^{k}.
  • O problema relaxado separa-se por item i: cada subproblema minimiza \sum_{t}(\tilde p_{t}^{i}x_{t}^{i}+\tilde f_{t}^{i}y_{t}^{i}+h_{t}^{i}s_{t}^{i}) sujeito apenas ao balanço e vínculo local.
  • O dual Lagrangiano maximiza sobre \lambda\ge0 o somatório dos valores ótimos dos subproblemas menos o termo \sum_{t,k}\lambda_{t}^{k}L_{t}^{k}.

Resposta

\displaystyle \mathcal{L}(\lambda)=\min_{\substack{x,s,y\\\ s_{t-1}^{i}+x_{t}^{i}=d_{t}^{i}+s_{t}^{i}\\\ x_{t}^{i}\le M y_{t}^{i},\;y_{t}^{i}\in\{0,1\},\;x_{t}^{i},s_{t}^{i}\ge0}} \Biggl\{\sum_{i}\sum_{t}\bigl(p_{t}^{i} x_{t}^{i}+f_{t}^{i} y_{t}^{i}+h_{t}^{i} s_{t}^{i}\bigr) +\sum_{t}\sum_{k}\lambda_{t}^{k}\Bigl(\sum_{i}\alpha^{i k} x_{t}^{i}+\sum_{i}\beta^{i k} y_{t}^{i}-L_{t}^{k}\Bigr)\Biggr\},\\ \lambda_{t}^{k}\ge0
\displaystyle
\displaystyle \text{Equivalente a}\quad \mathcal{L}(\lambda)=-\sum_{t}\sum_{k}\lambda_{t}^{k}L_{t}^{k}+\sum_{i}\min_{\substack{x^{i},s^{i},y^{i}\\\ s_{t-1}^{i}+x_{t}^{i}=d_{t}^{i}+s_{t}^{i}\\\ x_{t}^{i}\le M y_{t}^{i},\;y_{t}^{i}\in\{0,1\}}} \sum_{t}\bigl(\tilde p_{t}^{i} x_{t}^{i}+\tilde f_{t}^{i} y_{t}^{i}+h_{t}^{i} s_{t}^{i}\bigr),
\displaystyle
\displaystyle\text{onde }\tilde p_{t}^{i}=p_{t}^{i}+\sum_{k}\alpha^{i k}\lambda_{t}^{k},\quad \tilde f_{t}^{i}=f_{t}^{i}+\sum_{k}\beta^{i k}\lambda_{t}^{k}.
\displaystyle
\displaystyle\text{O dual Lagrangiano é } \max_{\lambda_{t}^{k}\ge0}\mathcal{L}(\lambda).é

Exercícios relacionados