Campus - Mossoró Profª Adricia Fonseca Mendes

Dualidade

Todo problema de PL está associado a outro problema de PL chamado dual. O problema original é chamado primal;

Apesar de possuírem características distintas, ambos os problemas levam a mesma solução ótima;

Tanto do ponto de vista teórico como prático, a Teoria da Dualidade é um dos mais importantes tópicos da (PL).

Todas variáveis devem ser não-negativas;

Todas restrições devem ser desigualdades com oModelo de maximização => restrições do tipo “≤” oModelo de minimização => restrições do tipo “≥”

Um problema de maximização de PL pode ser representado matematicamente como:

⋮ ⋮ ⋮

Forma matricial do problema anterior é: em que:

O problema dual pode ser escrito como:

sujeito a:

⋮ ⋮ ⋮

Forma matricial do problema anterior é: em que:

Definir uma variável Dual (y≥ 0) para cada restrição do Primal;

Fazer o vetor C de coeficientes de variáveis primais na função objetivo ser o vetor de constantes das restrições do Dual;

Fazer o vetor B de constantes nas restrições do Primal ser o vetor de coeficientes de variáveis duais na função objetivo do Dual;

A transposta da matriz a de coeficientes de variáveis primais nas restrições do Primal, At, será a matriz dos coeficientes das variáveis duais nas restrições do Dual;

O sentido das desigualdades das restrições do Dual será o inverso do sentido das desigualdades das restrições do Primal;

O critério de otimização da função objetivo do Dual será maximização se o Primal for de minimização, e será de minimização caso contrário.

A empresa Venix de brinquedos está revendo seu planejamento de produção de carrinhos e triciclos. O lucro líquido por unidade de carrinho e triciclo produzido é de R$12,0 e R$60,0, respectivamente. As matérias-primas e os insumos necessários para a fabricação de cada um dos produtos são terceirizados cabendo à empresa os processos de usinagem, pintura e montagem. O processo de usinagem requer 15 minutos de mão de obra especializada por unidade de carrinho e 30 minutos por unidade de triciclo produzida. O processo de pintura requer 6 minutos de mão de obra especializada por unidade de carrinho e 45 minutos por unidade de triciclo produzida. Já o processo de montagem necessita de 6 minutos e 24 minutos para uma unidade de carrinho e triciclo produzida, respectivamente. O tempo disponível por semana é de 36, 2 e 15 horas para os processos de usinagem, pintura e montagem, respectivamente. A empresa quer determinar quanto produzir de cada produto por semana, respeitando as limitações de recursos, de forma a maximizar o lucro líquido semanal. Formular o problema de programação linear que maximiza o lucro líquido da empresa Venix.

Determine o dual e forma matricial do exemplo 1. 13

No problema primal, os recursos da empresa Venix Brinquedos são utilizados para a fabricação de dois tipos de produtos: carrinho e triciclo;

interna, serão vendidos para uma empresa compradora

Imaginemos outro caso, para o problema dual, em que os recursos da empresa, em vez serem utilizados para a produção oPara que compense para a empresa Venix vender os seus recursos, o preço pago pela empresa compradora deve ser, no mínimo, igual ao lucro total gerado pelo seus produtos.

𝑥𝑗≥0,𝑗=1,2
𝑦𝑖≥0,𝑖=1,2,3

Propriedade 1: o dual do problema dual é o próprio primal e vice-versa;

Propriedade 2 (dualidade fraca): considerando o primal como um problema de maximização (max z) e o dual com um problema de minimização (min w), se ambos os problemas possuem soluções factíveis, o valor da função objetivo do problema primal é menor ou igual ao valor da função objetivo do problema dual, ou seja, z ≤ w.

Se o primal for um problema de minimização (min z), e o dual, de maximização (max w), ambos com soluções factíveis, tem-se que z ≥ w.

Propriedade 3: se a solução de um dos problemas (primal ou dual) for viável e com função objetivo limitada, tendo assim uma solução ótima finita, os valores da função objetivo de ambos os problemas são iguais, isto é, max z=min w ou min z=max w.

Propriedade 4: suponha um problema primal na forma padrão com uma solução ótima factível. Utilizando as condições de folga complementares, pode-se determinar a solução ótima do problema dual.

Sejam x* e y* um par de soluções ótimas para os problemas primal e dual, respectivamente. Podemos definir o teorema da folga complementar como:

O teorema da dualidade engloba as seguintes relações entre os problemas primal e dual:

1.Se a solução de um dos problemas (primal ou dual) for factível com função objetivo limitada, isto é, existe uma solução ótima finita, então o outro problema também será solução ótima. Nesse caso, as propriedades da dualidade fraca e forte podem ser aplicadas.

2.Se a solução de um dos problemas (primal ou dual) for factível, porém, com função objetivo ilimitada (não existe uma solução ótima), então a solução do outro problema é infactível.

O teorema da dualidade engloba as seguintes relações entre os problemas primal e dual:

3.Se a solução de um dos problemas (primal ou dual) for infactível, então a solução do outro problema também será solução infactível ou a função objetivo será ilimitada (não existe solução ótima).

O quadro abaixo resume as possíveis relações entre os problemas primal e dual.

Um fabricante deseja transportar uma mercadoria de dois armazéns A1 e A2 até três lojas L1 , L2 , e L3 com menor custo de transporte. As quantidades de mercadoria disponíveis nos armazéns são 300 e 600 respectivamente para A1 e A2. As demandas pelo produto em cada loja são dadas por 200, 300,

400, respectivamente para as lojas L1 , L2 , e L3 . Os custos unitários para transportar o produto de cada armazém para cada loja (em dólar) são os seguintes:

a)Encontrar o problema primal e dual. b)Fazer as interpretações econômicas de dualidade.

Referência

• BELFIORE, P. FÁVERO, L. P. Pesquisa Operacional: para cursos de engenharia. São Paulo: Campus, 2013.

Comentários