Programação Linear Aplicada · Capítulo 4

Cap. 4
Dualidade em Programação Linear

Relação entre problemas primal e dual, interpretação econômica das variáveis duais, propriedades primal-dual, Método Dual-Simplex e fundamentos da análise de pós-otimização.

Objetivos do capítulo

Ao final deste capítulo, espera-se que o estudante seja capaz de:

1. Introdução à dualidade

Todo problema de Programação Linear, denominado primal, possui um segundo problema associado, chamado dual. Os dois modelos são construídos a partir dos mesmos dados e estão fortemente relacionados: a estrutura de um contém informações sobre o outro.

Ideia central. Quando o primal representa, por exemplo, a melhor forma de utilizar recursos para maximizar um resultado, o dual pode ser interpretado como um problema de avaliação econômica desses recursos.

2. Montagem do problema dual

Problema primal

\[ \max Z=\sum_{j=1}^{n} c_jx_j \] sujeito a \[ \sum_{j=1}^{n} a_{ij}x_j \le b_i,\quad i=1,\ldots,m \] \[ x_j\ge 0,\quad j=1,\ldots,n \]

Problema dual

\[ \min z=\sum_{i=1}^{m} b_iy_i \] sujeito a \[ \sum_{i=1}^{m} a_{ij}y_i \ge c_j,\quad j=1,\ldots,n \] \[ y_i\ge 0,\quad i=1,\ldots,m \]

Regras básicas de correspondência

No primalNo dual
Cada restriçãocorresponde a uma variável dual
Cada variável de decisãocorresponde a uma restrição
Coeficientes do lado direito \(b_i\)tornam-se coeficientes da função objetivo
Coeficientes da função objetivo \(c_j\)tornam-se os lados direitos das restrições
Matriz \(A\)é transposta: \(A^T\)
Maximização com restrições \(\le\)Minimização com restrições \(\ge\)

3. Exemplo de construção do dual

Considere o problema primal:

\[ \max Z=x_1+2x_2 \] sujeito a \[ \begin{aligned} x_1+5x_2 &\le 18\\ 2x_1+x_2 &\le 15\\ 5x_1-2x_2 &\le 20\\ x_2 &\le 8\\ x_1,x_2&\ge 0 \end{aligned} \]

Como há quatro restrições estruturais no primal, o dual terá quatro variáveis: \(y_1,y_2,y_3,y_4\).

\[ \min z=18y_1+15y_2+20y_3+8y_4 \] sujeito a \[ \begin{aligned} y_1+2y_2+5y_3 &\ge 1\\ 5y_1+y_2-2y_3+y_4 &\ge 2\\ y_1,y_2,y_3,y_4&\ge 0 \end{aligned} \]
Observe a troca de dimensões: o primal possui 4 restrições e 2 variáveis; o dual possui 2 restrições e 4 variáveis.

4. Variáveis irrestritas em sinal

Um caso especial ocorre quando uma restrição do primal é uma igualdade. Uma igualdade pode ser representada por duas desigualdades de sentidos contrários. No dual, isso leva a duas variáveis não negativas cuja diferença pode assumir valor positivo, zero ou negativo.

\[ a_{11}x_1+a_{12}x_2=b_1 \] é equivalente a \[ \begin{cases} a_{11}x_1+a_{12}x_2\le b_1\\ -a_{11}x_1-a_{12}x_2\le -b_1 \end{cases} \]

Se as variáveis duais correspondentes forem \(y'_1\) e \(y''_1\), pode-se definir:

\[ y_1=y'_1-y''_1 \]
Consequência: uma restrição de igualdade no primal corresponde a uma variável dual irrestrita em sinal. O raciocínio inverso também é válido.

5. Interpretação econômica das variáveis duais

As variáveis duais admitem uma interpretação econômica especialmente útil: podem representar a avaliação unitária ou o valor marginal dos recursos disponíveis.

Exemplo: dois produtos e três recursos

Recurso Disponibilidade Consumo por unidade — Produto 1 Consumo por unidade — Produto 2
A1412
B911
C5674

Se os lucros unitários forem 5 e 6, o primal é:

\[ \max Z=5x_1+6x_2 \] sujeito a \[ \begin{aligned} x_1+2x_2&\le14\\ x_1+x_2&\le9\\ 7x_1+4x_2&\le56\\ x_1,x_2&\ge0 \end{aligned} \]

Associando \(y_1,y_2,y_3\) aos recursos A, B e C, o dual procura o menor valor total atribuído ao estoque de recursos, sem atribuir a cada produto um valor inferior ao seu lucro unitário:

\[ \min z=14y_1+9y_2+56y_3 \] sujeito a \[ \begin{aligned} y_1+y_2+7y_3&\ge5\\ 2y_1+y_2+4y_3&\ge6\\ y_1,y_2,y_3&\ge0 \end{aligned} \]
Na solução ótima, as variáveis duais podem ser interpretadas como preços-sombra: indicam a variação marginal esperada no valor ótimo do primal quando a disponibilidade de um recurso sofre pequena alteração, respeitadas as condições de validade da solução básica.

6. Relações entre os valores ótimos do primal e do dual

Há duas relações fundamentais entre os problemas:

Dualidade fraca

Para quaisquer soluções viáveis do primal e do dual, no caso padrão de maximização/minimização:

\[ Z\le z \]

Dualidade forte

Quando ambos atingem uma solução ótima finita:

\[ \max Z=\min z \]

No exemplo anterior, a solução ótima apresentada é:

\[ x_1=4,\qquad x_2=5,\qquad Z^*=50 \] e, no dual, \[ y_1=1,\qquad y_2=4,\qquad y_3=0,\qquad z^*=50 \]

7. Importantes propriedades primal-dual

7.1 Multiplicadores do Simplex

Em qualquer iteração, a matriz associada às variáveis básicas pode ser utilizada para obter os coeficientes da linha transformada da função objetivo. Na solução ótima, esses multiplicadores coincidem com os valores ótimos das variáveis duais.

Esses valores também aparecem na literatura como custos implícitos, custos de oportunidade ou preços-sombra.

7.2 Valores das variáveis básicas

Os valores das variáveis na base podem ser obtidos aplicando a matriz associada à base ao vetor dos termos independentes do modelo original.

7.3 Coeficientes transformados

Os coeficientes de uma variável nas restrições transformadas podem ser obtidos multiplicando-se a mesma matriz básica pelo vetor de coeficientes originais dessa variável.

7.4 Relação com a equação \(Z\) transformada

A substituição das variáveis duais pelos multiplicadores do Simplex permite interpretar os coeficientes da equação \(Z\) transformada como diferenças entre os lados das restrições correspondentes do dual. Um coeficiente que viola a condição de otimalidade indica que a solução primal ainda pode ser melhorada e que a solução dual associada ainda não é viável.

8. Situações especiais na preparação do modelo para o Simplex

Até aqui, a formulação dos problemas primal e dual permitiu compreender a estrutura matemática e a interpretação econômica dos modelos. Entretanto, alguns problemas não apresentam imediatamente uma solução básica inicial viável. Isso ocorre, em especial, quando aparecem restrições do tipo \(\ge\) ou de igualdade.

Ponto-chave. As variáveis de folga, excesso e artificiais têm papéis diferentes. A variável de folga costuma permitir a construção direta de uma base inicial. A variável de excesso, por sua vez, não garante essa base. Quando isso acontece, recorre-se temporariamente às variáveis artificiais.

8.1 Transformação de desigualdades

Uma desigualdade pode ser multiplicada por \(-1\), desde que o seu sentido seja invertido. Assim:

\[ a_1x_1+a_2x_2\ge b \] é equivalente a \[ -a_1x_1-a_2x_2\le -b. \]

8.2 Variáveis de excesso

Em uma restrição do tipo \(\ge\), a transformação em igualdade exige a retirada de uma variável de excesso:

\[ a_1x_1+a_2x_2\ge b \] transforma-se em \[ a_1x_1+a_2x_2-e_1=b,\qquad e_1\ge0. \]

A variável de excesso mede quanto o lado esquerdo ultrapassa o limite imposto pela restrição. Entretanto, como aparece com coeficiente \(-1\), ela não constitui, em geral, uma variável básica inicial viável.

8.3 Por que a variável de excesso não gera uma base inicial

Considere:

\[ 8x_1+4x_2+4x_3\ge16. \]

Com a variável de excesso:

\[ 8x_1+4x_2+4x_3-e_1=16. \]

Se \(x_1=x_2=x_3=0\), então:

\[ -e_1=16 \quad\Rightarrow\quad e_1=-16. \]
Como \(e_1\ge0\), essa solução inicial é inviável. Portanto, a simples introdução da variável de excesso não resolve o problema da base inicial.

8.4 Variáveis artificiais

Para criar temporariamente uma base inicial, introduz-se uma variável artificial. No exemplo:

\[ 8x_1+4x_2+4x_3-e_1+a_1=16, \qquad a_1\ge0. \]

Agora, tomando inicialmente \(x_1=x_2=x_3=e_1=0\), temos \(a_1=16\), o que permite iniciar o processo iterativo.

Variável Papel no modelo Significado
Folga É adicionada a uma restrição \(\le\) Representa recurso não utilizado e frequentemente forma a base inicial.
Excesso É subtraída de uma restrição \(\ge\) Representa quanto o valor supera o limite mínimo.
Artificial É introduzida temporariamente quando não existe base inicial evidente Não possui significado físico; serve apenas para iniciar o algoritmo.

8.5 Aspectos matemáticos complementares

Alguns artifícios matemáticos também ajudam a colocar o modelo em uma forma adequada ao algoritmo. Entre eles:

\[ x_j=x'_j-x''_j,\qquad x'_j\ge0,\quad x''_j\ge0. \]

Além disso, os modelos lineares pressupõem, em sua forma clássica, divisibilidade e aditividade. A divisibilidade admite valores fracionários para as variáveis; a aditividade pressupõe que o consumo total de recursos e o resultado total sejam obtidos pela soma das contribuições individuais de cada atividade.

9. Método Simplex em Duas Fases

O Método Simplex em Duas Fases é utilizado quando a formulação não fornece diretamente uma solução básica inicial viável. As variáveis artificiais são empregadas apenas para iniciar o processo e devem ser eliminadas antes da otimização da função objetivo original.

9.1 Exemplo de formulação

Considere o problema:

\[ \min z=16x_1+12x_2+5x_3 \] sujeito a \[ \begin{aligned} 8x_1+4x_2+4x_3&\ge16\\ 4x_1+6x_2&\ge12\\ x_1,x_2,x_3&\ge0. \end{aligned} \]

Introduzindo variáveis de excesso:

\[ \begin{aligned} 8x_1+4x_2+4x_3-e_1&=16\\ 4x_1+6x_2-e_2&=12. \end{aligned} \]

Essa transformação ainda não fornece uma base inicial viável. Por isso, são introduzidas duas variáveis artificiais:

\[ \begin{aligned} 8x_1+4x_2+4x_3-e_1+a_1&=16\\ 4x_1+6x_2-e_2+a_2&=12. \end{aligned} \]

9.2 Fase 1 — obtenção de uma solução básica viável

Na primeira fase, substitui-se temporariamente a função objetivo original por uma função auxiliar que procura reduzir a zero a soma das variáveis artificiais:

\[ \min W=a_1+a_2+\cdots+a_k. \]

Se \(W^*=0\)

Todas as variáveis artificiais podem ser retiradas da solução. Foi encontrada uma solução básica viável para o problema original.

Se \(W^*>0\)

Pelo menos uma variável artificial permanece positiva. Isso indica que o problema original não possui solução viável.

9.3 Fase 2 — otimização da função objetivo original

Concluída a Fase 1 com \(W^*=0\), eliminam-se as colunas correspondentes às variáveis artificiais e restabelece-se a função objetivo original. A solução básica viável encontrada passa a ser o ponto de partida para a otimização.

1
Preparar o modelo. Converter as restrições em igualdades e introduzir folgas, excessos e, quando necessário, variáveis artificiais.
2
Executar a Fase 1. Minimizar a soma das variáveis artificiais.
3
Testar a viabilidade. Se \(W^*=0\), existe uma base viável para o problema original.
4
Executar a Fase 2. Retomar a função objetivo original e prosseguir com o Simplex até a solução ótima.
Leitura conceitual. O método de duas fases resolve primeiro o problema da viabilidade e somente depois o problema da otimização.

Fluxograma — Método Simplex em Duas Fases

Acompanhe as decisões e as iterações. As notas à direita explicam cada etapa; as setas de retorno indicam a repetição do processo.

Fluxograma do método Simplex em duas fases Doze etapas com notas explicativas. Na Fase 1, testar otimalidade antes de iterar e verificar artificiais após o ótimo. Na Fase 2, testar otimalidade, pivotar ou registrar ilimitação. Encerrar com interpretação e Solver. Início 1. Modelar o problema original NOTA 1 Definir variáveis de decisão, função objetivo deminimização, restrições e domínios. 2. Remodelar o problemaIncluir excesso e artificiais NOTA 2 Normalizar lados direitos negativos, invertendodesigualdades quando necessário. Adicionar folga em≤ e subtrair excesso em ≥. Incluir artificiais ondenecessário para formar a base inicial. 3. Fase 1: montar o quadroinicialBase inicial NOTA 3 Nos exemplos da planilha, as artificiais formam abase inicial e recebem os valores de b. As nãobásicas iniciam em zero. Minimizar W = soma dasartificiais e ajustar a linha objetivo à base. 4. A fase 1 alcançou o pontoótimo? NOTA 4 Na função auxiliar transformada da planilha, acondição de parada é C − Z ≤ 0 em todas as colunas.O ótimo auxiliar ainda exige verificar se asartificiais zeraram. 5. Gerar a iteração iBase i · Quadro i NOTA 5 Escolher uma coluna que melhore o objetivo. Calcularb/coefficientes positivos da coluna. A menor razãonão negativa define quem sai. Normalizar a linhapivô, zerar o restante da coluna e atualizar base eobjetivo. 6. Todas as artificiais sãoiguais a zero? NOTA 6 No ótimo auxiliar, W = 0 significa que todas asartificiais são zero: o original é viável. Se W > 0,o original é inviável. Artificiais positivas antesdo ótimo não permitem essa conclusão. 7. Fase 2: montar o quadroinicial NOTA 7 Partir da base viável da Fase 1. Retirar artificiaisbásicas de valor zero por pivô ou remover a linharedundante. Excluir apenas colunas artificiais;manter originais, folgas, excessos e restriçõestransformadas. Restaurar custos reais e recalcular Z− C. 8. A fase 2 alcançou o pontoótimo? NOTA 8 Para minimização, com a convenção Z − C, todos oscustos reduzidos devem ser ≤ 0. A base inicial daFase 2 pode já ser ótima, dispensando novasiterações. 9. Existe pivô admissível? NOTA 9 Escolher coluna com Z − C positivo. Havendocoeficiente positivo nas restrições, aplicar a menorrazão não negativa. Sem coeficiente positivo, hádireção viável de redução ilimitada do objetivo. 10. Gerar a iteração iBase i · Quadro i NOTA 10 Pivotar e atualizar base, quadro e Z − C. Aviabilidade é preservada e o objetivo não aumenta.Normalmente passa-se a um PEF adjacente. Nadegenerescência, o ponto pode não mudar. Usar regraanticiclagem, como Bland. 11. Interpretar a solução NOTA 11 Ler as básicas no lado direito; as não básicas sãozero. Calcular o objetivo original. Folgas indicamcapacidade não utilizada e excessos indicamatendimento acima do mínimo. 12. Conferir com o Solver NOTA 12 Resolver o original com Simplex LP, sem artificiaise respeitando os domínios. Conferir viabilidade,objetivo, folgas e excessos. Ótimos alternativospodem ter variáveis diferentes e o mesmo objetivo. Não Sim Não Sim Sim Retornar Sim Retornar Não → Original inviável → Fim Não → Original ilimitado → Fim Fim

Observação de leitura. Na Fase 1, a linha C − Z corresponde à função auxiliar transformada utilizada na planilha; seu valor “Z” não deve ser confundido com W = soma das artificiais. Nas verificações numéricas de zero, utilize uma tolerância, por exemplo, 10−6.

10. Método Dual-Simplex

O Método Dual-Simplex oferece uma estratégia diferente da utilizada no método de duas fases. Enquanto o método de duas fases procura primeiro construir uma solução primal viável, o Dual-Simplex pode partir de um quadro que já satisfaz o critério de otimalidade, mas apresenta uma ou mais variáveis básicas com valor negativo — isto é, uma solução ainda inviável no primal.

Variável que sai

Escolhe-se a variável básica com o valor mais negativo do lado direito.

Variável que entra

É escolhida entre as variáveis não básicas com coeficiente negativo na linha da variável que sai, segundo o teste de razão apropriado.

Exemplo

\[ \min z=2x_1+x_2 \] sujeito a \[ \begin{aligned} 4x_1+3x_2&\ge6\\ x_1+2x_2&\le3\\ x_1,x_2&\ge0 \end{aligned} \]

Após a transformação indicada no método, obtém-se uma solução inicial inviável. As iterações do Dual-Simplex restauram a viabilidade mantendo a condição de otimalidade.

A solução ótima apresentada no exemplo é \[ x_1=\frac35,\qquad x_2=\frac65,\qquad z=\frac{12}{5}. \]
Se, na linha escolhida para sair da base, não existir coeficiente com sinal adequado para realizar o teste de entrada, o problema não possui solução viável nas condições consideradas.

11. Análise de pós-otimização e sensibilidade

Depois de encontrada uma solução ótima, é natural perguntar se ela continuará válida quando os dados do modelo sofrerem alterações. Essa etapa é conhecida como análise de pós-otimização ou análise de sensibilidade.

Ela é importante porque, em aplicações reais:

O objetivo não é apenas encontrar uma solução ótima, mas também avaliar até que ponto essa solução é robusta diante de pequenas mudanças nos parâmetros do problema.

Resumo do capítulo

A dualidade oferece uma segunda leitura do mesmo problema de Programação Linear. Enquanto o primal normalmente descreve decisões operacionais, o dual evidencia a avaliação econômica das restrições e dos recursos. A igualdade entre os valores ótimos dos dois modelos, os multiplicadores do Simplex e a interpretação dos preços-sombra formam a base para análises gerenciais e para estudos de sensibilidade.

As situações envolvendo restrições do tipo \(\ge\) ou de igualdade mostram por que variáveis de excesso e artificiais são necessárias em alguns modelos. O Método Simplex em Duas Fases separa a busca por viabilidade da etapa de otimização, enquanto o Método Dual-Simplex segue a lógica complementar de restaurar a viabilidade a partir de um quadro que já satisfaz o critério de otimalidade.

Conteúdo organizado e reescrito a partir das páginas de referência fornecidas pelo usuário. As formulações e exemplos numéricos foram preservados para fins didáticos.

← Capítulo 3