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):
Balanço de estoque: s_{t-1}^{i}+x_{t}^{i}=d_{t}^{i}+s_{t}^{i} para todo i,t.
Vinculação produção–decisão: x_{t}^{i}\le M y_{t}^{i} para todo i,t.
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
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
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):
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:
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:
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:
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}.