Questão 3: Gerando Cortes Lagrangianos
Para cada uma das relaxações propostas na questão 1, derive a forma algébrica do Plano Cortante Lagrangiano que se pode obter a partir da solução do Programa Dual Lagrangeano. Note que se a definição geral da Função Lagrangeana é
Então a expressão do Corte Lagrangeano seria:
Auf Wiedersehen, Senhores!!!
Para cada uma das relaxações propostas na questão 1, derive a forma algébrica do Plano Cortante Lagrangiano que se pode obter a partir da solução do Programa Dual Lagrangeano. Note que se a definição geral da Função Lagrangeana é
Passo 1
O que o enunciado pede:
- Derivar a forma algébrica do Plano Cortante Lagrangiano obtido a partir da solução do Programa Dual Lagrangeano para cada uma das relaxações propostas na questão 1.
Informações fornecidas no enunciado:
- A definição geral da função Lagrangeana:
- A expressão genérica do corte Lagrangeano:
Informação que falta (impedimento para responder apenas com as relaxações específicas da “questão 1”):
- O enunciado refere-se a “cada uma das relaxações propostas na questão 1”, porém essas relaxações específicas não foram enviadas. Sem saber quais restrições foram relaxadas, NÃO é possível escrever os cortes explicitamente para os casos particulares pedidos em Q1.
- Portanto vou: (i) explicar didaticamente como derivar o corte em forma algébrica para o caso geral de relaxação de um subconjunto de restrições; (ii) dar as fórmulas explícitas em termos dos componentes da matriz e dos vetores (ou seja, um “template” que você aplica a cada relaxação específica de Q1 assim que souber quais linhas de
foram relaxadas). Se você quiser depois eu aplico esse template às relaxações concretas de Q1 — é só mandar elas.
Passo 2
Entendendo a estrutura geral (explicação didática, passo a passo, sem pular etapas).
- Suponha que o problema original (por exemplo um MILP) seja
onde:
-
é o vetor de variáveis de decisão; -
é o vetor de custos; -
e representam um conjunto de restrições “complicadas”; -
é o conjunto das demais restrições fáceis (por exemplo integridade, capacidade local, bounds, etc.) sobre as quais o subproblema será resolvido. - Na Lagrangiana usual partimos de uma partição em que relaxamos as restrições complicadoras
com multiplicadores . Os multiplicadores têm sinal conforme o tipo da restrição: - se a restrição for do tipo
então ; - se for
então ; - se for igualdade
então é livre (sem sinal imposto).
- se a restrição for do tipo
- A Lagrangeana associada a um vetor
é obtida movendo para a função objetivo e minimizando sobre . Por isso a fórmula
- O dual Lagrangiano busca
com as restrições de sinal apropriadas em . Seja uma solução dual (ou um candidato de bons multiplicadores) e seja um minimizador do subproblema . Então é o valor obtido avaliando esse mínimo.
Passo 3
Derivação algébrica direta do corte Lagrangeano a partir da fórmula dada.
- A forma genérica do corte é dada no enunciado:
- Expandindo o termo
obtemos:
- Reagrupando os termos que multiplicam
obtemos uma inequação linear padrão em :
- Esta é a forma algébrica do plano cortante: um coeficiente linear para cada variável (o vetor de coeficientes é
) e um lado direito escalar . Em notação mais componente a componente:
Passo 4
Forma alternativa usando o minimizador do subproblema (interpretação útil na prática).
- Seja
um minimizador de . Então, por definição,
- Substituindo
na desigualdade original:
- Cancelando
dos dois lados obtém-se a forma muito simples
ou, escrevendo como diferença,
- Interpretação prática: o corte força que qualquer
viável na master respeite que o valor linear avaliado com o vetor de pesos não caia abaixo do valor atingido pelo minimizador . Se for uma solução relaxada que viola as restrições originais, frequentemente essa desigualdade é violada por e então o corte é efetivo para separar .
Passo 5
Forma expandida por restrição relaxada (template aplicável quando se conhece a lista de restrições relaxadas).
- Se o conjunto de restrições relaxadas for
(índices ), com cada restrição escrita como , então o corte pode ser escrito explicitamente como
- Reagrupando por
:
- Esse é o corte em forma totalmente componente a componente: coeficiente de
é , e o lado direito é .
Passo 6
Exemplos concretos (aplique o template às relaxações de Q1 quando as tiveres)
- Exemplo 1 — relaxando apenas uma restrição
: com . O corte fica
ou equivalentemente
- Exemplo 2 — relaxando várias restrições do tipo capacidade/ligação (índices
): já dado no passo 5 — basta substituir os , e correspondentes.
Passo 7
Notas práticas e observações didáticas rápidas (como usar na prova)
- Sempre verifique o sinal dos
de acordo com o sentido da restrição relaxada antes de montar o corte. - Para calcular
na prática, resolve-se o subproblema . O obtido nesse subproblema permite simplificar o corte (Passo 4). - O corte é válido para o problema original: qualquer
que satisfaça as restrições originais também satisfará o corte; ele serve para cortar soluções do master que violam as restrições relaxadas. - Quando receber as relaxações específicas da questão 1 eu aplico o template e escrevo o corte explicitamente para cada caso pedido.
Resposta
Forma algébrica geral do Plano Cortante Lagrangiano:
Forma componente a componente (relaxando o conjunto
de linhas de
):
Forma usando o minimizador
do subproblema (simplificação prática):
onde
.