O que é um modelo Dual?

O que é um modelo Dual?

De acordo com Andrade, E.L (2009): “ Todo problema de programação linear, que chamaremos de primal, traz com sigo uma segundo problema, chamado dual, sendo ambos completamente inter-relacionados, de tal maneira que a solução ótima de um fornece informações completas sobre o outro.”

Para que precisamos estudar o modelo Dual? Devido às interpretações econômicas que o modelo Dual nos proporciona O modelo Dual pode ter uma solução mais fácil do que o original (primal), pois o número de restrições e variáveis pode ser diferente

Capitulo 8: Dualidade

Vamos supor o seguinte modelo matemático:

1) Variáveis de decisão

X1: Quantidade de produção do produto 1



2) Função Objetivo (maximizar o lucro)

Max Z= 2X1+4X2+3X3

3) Restrições

Mão de Obra X1 + X2+ 2X3≤10

Matéria Prima 3X1+ + X3≤5

Horas de Máquinas 2X2+ X3≤6

Com X1, X2 e X3≥0

Esse é o modelo original, chamado de Primal


Vamos agora, transformar o modelo Primal em um modelo Dual. Apenas para uma questão didática, vamos organizar o modelo da seguinte maneira (forma matricial), e vamos seguir os passos abaixo


Max Z= 2X1+ 4X2+ 3X3

X1 + X2+ 2X3≤10

3X1+ + X3≤5

2X2+ X3≤6

10Y1Min Z=

1) Transformamos a função objetivo de “Maximizar” para “Minimizar”

2) Para cada restrição (são 3 no exemplo), criamos uma variável Y

Y1

Y2

Y3

+5Y2 +6Y3

3) Colocar cada Y na função objetivo do Dual e dar ao seu coeficiente o valor máximo da restrição a que se refere

PRIMAL DUAL

4) Cada variável de decisão do Primal, corresponde a uma restrição no Dual, cujo limite (bi) será o coeficiente da variável Primal na função objetivo. Os coeficientes das restrições do Primal para a mesma variável (X1, por exemplo) se transformarão nos coeficientes das variáveis Y do Dual. O sinal da inequação deverá ser trocado: onde tiver “≤” deverá ser colocado “≥”


Max Z= 2X1+ 4X2+ 3X3

Restrições

1X1 + X2+ 2X3≤10

3X1+ + X3≤5

2X2+ X3≤6

Analogamente, para os coeficientes de X2 e X3, teremos:

1Y1+ 3Y2+ 0Y3Y1

Y2

Y3

≥2

MinW= 10Y1+5Y2+6Y3

Restrições

≥4

≥3

1Y1+ 0Y2+ 2Y3

2Y1+ 1Y2+ 1Y3

Agora que já temos a Função Objetivo do Dual, vamos definir as restrições:

PRIMAL DUAL

Capitulo 8: DualidadeAssim, teremos os dois modelos da seguinte forma:

PRIMALMax Z= 2X1+ 4X2+ 3X3

Sujeito a:

X1+ X2+2X3 ≤10

3X1+ X3 ≤5

2X2+ X3 ≤6

X1, X2 e X3 ≥0

DUALMin W= 10Y1+5Y2+6Y3

Sujeito a

Y1+3Y2 ≥2

Y1+2Y3 ≥4

2Y1+Y2+Y3 ≥3

Y1, Y2 e Y3 ≥0

Assim, os conceitos básicos para a criação de um problema Dual através de um Primal se resumem da seguinte maneira:

• Para cada restrição de um Primal, teremos uma variável no Dual;

• Os limites das restrições do Primal (constantes que chamamos de bi) serão os coeficientes na Função Objetivo do Dual;

• A maximização no Primal se transforma em minimização no Dual e a minimização, em maximização;

• Quando as restrições do Primal forem “≤”, no Dual serão “≥” e vice-versa;

• A solução ótima obtida é a mesma para ambos os problemas

• Nota 1*: Tanto no Primal quanto no Dual, as variáveis (X ou Y) serão sempre positivas (ou seja: “≥0”)

• Nota 2: O Dual do Primal é o Primal do Dual.

*Exceto quando uma das restrições tiver sinal de igualdade. Nesse caso a variável correspondente é irrestrita em sinal.


Interpretação Econômica do DualNum modelo de maximização dos lucros, o Dual se refere à capacidade dos recursos de gerar lucros.

Dado o exemplo abaixo (Andrade E. L., 2009), vamos fazer a interpretação do modelo Dual:

Problema Primal: Problema Dual:


Max. Z= 5X1+6X2

Sujeito a:

X1+2X2≤14 (Recurso A)

X1+ X2≤9 (Recurso B)

7X1+4X2≤58 (Recurso C)

X1 e X2 ≥ 0

Onde: X1 é a quantidade do Produto 1 e X2 a do Produto 2

Min. W= 14Y1+9Y2+58Y3

Sujeito a:

Y1+Y2+7Y3 ≥5

2Y1+Y2+4Y3 ≥6

Y1, Y2 e Y3 ≥ 0


1) Qual o valor de Z do Primal?

2) Quais as variáveis básicas?

3) Quais as variáveis não básicas?

4) Qual o valor de Y1 e o que significa?


1) Max Z = min. W = 50

O Simplex do problema Dual seria:

Y1 Y2 Y3 Y4 Y5 b

0 1 10 -2 1 4

1 0 -3 1 -1 1

0 0 10 4 5 50

2) Y1 e Y2

3) Y3, Y4 e Y5

4) Y1 é igual a 1 (coluna b) e é chamado de utilidade marginal. Ele representa a primeira restrição, que é o recurso A. O valor 1 atribuído a ele, significa que a cada 1 unidade a mais desse recurso, o lucro é acrescido de 1 unidade. Inversamente, para cada 1 unidade perdida nesse recurso, o lucro é subtraído de 1 unidade também.5) Y2 é igual a 4 (utilidade marginal). Ele representa a segunda restrição, que é o recurso B. O valor 4 atribuído a ele, significa que a cada 1 unidade a mais desse recurso, o lucro é acrescido de 4 unidades. Inversamente, para cada 1 unidade perdida nesse recurso, o lucro é subtraído de 4 unidades também.



7) O recurso C é escasso?


6) Y3 é uma variável não básica, por isso seu valor é 0. Ele representa o recurso C. Significa que uma variação unitária na sua disponibilidade não causará nenhum efeito no lucro final.


Y1 Y2 Y3 Y4 Y5 b

0 1 10 -2 1 4

1 0 -3 1 -1 1

0 0 10 4 5 50

7) Não. A folga desse recurso é de 10 unidades e pode ser vista na linha que representa W (última linha).

8) Y4 é uma variável não básica, por isso seu valor é 0. Na linha que representa W, o coeficiente 4 indica que serão produzidos 4 Produto1.

Se ele fosse diferente de 0 (variável não básica) o seu valor (na coluna b) significaria um lucro marginal negativo (que seria o quanto o lucro seria menor se fossemos obrigado a produzir o Produto1)



10) Quanto você pagaria para comprar 1 unidade do recurso B?

11) Quanto você pagaria para comprar 1 unidade do recurso C?


Y1 Y2 Y3 Y4 Y5 b

0 1 10 -2 1 4

1 0 -3 1 -1 1

0 0 10 4 5 50


Se ele fosse diferente de 0 (variável não básica) o seu valor (na coluna b) significaria um lucro marginal negativo (que seria o quanto o lucro seria menor se fossemos obrigado a produzir o Produto2)10) O recurso B é escasso e cada unidade dele aumentará o lucro em $4, por isso, poderíamos pagar qualquer valor abaixo de $4 (somando-se seus custos)

11) O recurso C está sobrando. Não deve ser comprado

Exercicio 8.1Fazer o Dual e a interpretação do modelo Dual:

Problema Primal: Problema Dual:


Max. Z= 13X1+4X2

Sujeito a:

2X1+1X2≤80 (Recurso A)

X1+ X2≤60 (Recurso B)

X1≤50 (Recurso C)

X1 e X2 ≥ 0

Onde: X1 é a quantidade do Produto 1 e X2 a do Produto 2

Min. W= 80Y1+60Y2+50Y3

Sujeito a:

2Y1+Y2+Y3 ≥13

Y1+Y2 ≥4

Y1, Y2 e Y3 ≥ 0


1) Qual o valor de Z do Primal?

2) Quais as variáveis básicas?

3) Quais as variáveis não básicas?



6) O recurso B é escasso?

1) Max Z = min. W = 520


Y1 Y2 Y3 Y4 Y5 b

0 1 2,5

1 0 6,5

0 20 10 40 0 520

2) Y1 e Y5

3) Y2, Y3 e Y4

4) Y1 é igual a 6,5 (coluna b) e é chamado de utilidade marginal. Ele representa a primeira restrição, que é o recurso A. O valor 6,5 atribuído a ele, significa que a cada 1 unidade a mais desse recurso, o lucro é acrescido de 6,5 unidade. Inversamente, para cada 1 unidade perdida nesse recurso, o lucro é subtraído de 6,5 unidade também.5) Y2 é uma variável não básica, por isso seu valor é 0. Ele representa o recurso B. Significa que uma variação unitária na sua disponibilidade não causará nenhum efeito no lucro final.

6) Não. A folga desse recurso é de 20 unidades e pode ser vista na linha que representa W (última linha).






Y1 Y2 Y3 Y4 Y5 b

0 1 2,5

1 0 6,5

0 20 10 40 0 520

8) Y5 é igual a 2,5 (coluna b) e significa um lucro marginal negativo. Não será produzido nenhum produto 2, mas, se fossemos obrigado a produzir lo, cada unidade produzida traria um prejuízo de $2,5

Documents

O que é um modelo Dual?