(Prob.01) Uma indústria dispõe de três recursos, Aço, Cobre e Chumbo, em quantidades limitadas. Com esses recursos, a indústria pretende produzir dois produtos que chamaremos de Peça 1 e Peça 2. A tabela abaixo dá a utilização unitária de cada recurso em cada um dos produtos e a disponibilidade de cada recurso.

Utilização unitária e disponibilidade dos recursos

Recurso Disponib. Recurso gasto p/ fazer 1un dePeça 1 Peça 2

Aço 14 1 2Cobre 9 1 1

Chumbo 56 7 4

A indústria sabe que cada unidade produzida do Peça 1 dá uma margem de lucro unitária de R$ 5 e cada unidade do Peça 2 dá R$ 6. O problema de programação da produção é determinar a quantidade a ser produzida de ambos os produtos de modo a maximizar a margem de lucro total.

Por outro lado, vamos supor que a indústria tenha a alternativa de vender os recursos Aço, Cobre e Chumbo, em vez de emprega-los na produção dos dois produtos.

O problema que se coloca agora é encontrar o valor da unidade de cada recurso. É evidente que a venda dos recursos deve fornecer um ganho pelo menos igual ao obtido com a utilização deles na produção.

Peça 1= x1 e Peça 2 = x2

Modelo completo:

Maximizar Z = 5x1 + 6x2 (primal)Sujeito a:

1x1 + 2x2 ≤ 14 (aço)1x1 + 1x2 ≤ 9 (cobre)7x1 + 4x2 ≤ 56 (chumbo)

Com x1 e x2 ≥ 0

Y1 = valor unitário do AçoY2 = valor unitário do CobreY3 = valor unitário do Chumbo

Minimizar z = 14y1 + 9y2 + 56y3 (dual)Sujeito a:

1y1 + 1y2 + 7y3 ≥ 52y1 + 1y2 + 4 y3 ≥ 6

Com y1, y2 e y3 ≥ 0BAS

E X1 X2 X3 X4 X5 bX3 1 2 1 0 0 14 /2 = 7X4 1 1 0 1 0 9 /1 = 9 X5 7 4 0 0 1 56 /4 =14Z -5 -6 0 0 0 0

BASE X1 X2 X3 X4 X5 b

X2 1 2 1 0 0 14 /lin (2)X4 1 1 0 1 0 9 X5 7 4 0 0 1 56Z -5 -6 0 0 0 0

BASE X1 X2 X3 X4 X5 b

X2 1/2 1 1/2 0 0 7 Mult lin x2 (-1) + lin x4X4 1 1 0 1 0 9 X5 7 4 0 0 1 56Z -5 -6 0 0 0 0

BASE X1 X2 X3 X4 X5 b

X2 1/2 1 1/2 0 0 7 Mult lin x2 (-4) + lin x5X4 1/2 0 -1/2 1 0 2 X5 7 4 0 0 1 56Z -5 -6 0 0 0 0

BASE X1 X2 X3 X4 X5 b

X2 1/2 1 1/2 0 0 7 Mult lin x2 (6) + lin ZX4 1/2 0 -1/2 1 0 2 X5 5 0 -2 0 1 28Z -5 -6 0 0 0 0

BASE X1 X2 X3 X4 X5 b

X2 1/2 1 1/2 0 0 7 / ½ = 14X4 1/2 0 -1/2 1 0 2 / ½ = 4

X5 5 0 -2 0 1 28 / 5 > 5Z -2 0 3 0 0 42

BASE X1 X2 X3 X4 X5 b

X2 1/2 1 1/2 0 0 7X1 1/2 0 -1/2 1 0 2 / 1/2 X5 5 0 -2 0 1 28Z -2 0 3 0 0 42

BASE X1 X2 X3 X4 X5 b

X2 1/2 1 1/2 0 0 7X1 1 0 -1 2 0 4 Mult lin x1 (-1/2) + lin x2 X5 5 0 -2 0 1 28Z -2 0 3 0 0 42

BASE X1 X2 X3 X4 X5 b

X2 0 1 1 -1 0 5X1 1 0 -1 2 0 4 Mult lin x1 (-5) + lin x5 X5 5 0 -2 0 1 28Z -2 0 3 0 0 42

BASE X1 X2 X3 X4 X5 b

X2 0 1 1 -1 0 5X1 1 0 -1 2 0 4 Mult lin x1 (2) + lin Z X5 0 0 3 -10 1 8Z -2 0 3 0 0 42

BASE X1 X2 X3 X4 X5 b

X2 0 1 1 -1 0 5 Como não existe nenhumX1 1 0 -1 2 0 4 número negativo na linha Z X5 0 0 3 -10 1 8 então a solução é ótimaZ 0 0 1 4 0 50

Minimizar z = 14y1 + 9y2 + 56y3 (dual)Sujeito a:

1y1 + 1y2 + 7y3 ≥ 52y1 + 1y2 + 4 y3 ≥ 6

Com y1, y2 e y3 ≥ 0

Passo1 – Variáveis de folga/excesso

z = 14y1 + 9y2 + 56y3 - 0y4 - 0y5 1y1 + 1y2 + 7y3 - 1y4 = 52y1 + 1y2 + 4 y3 - 1y5 = 6

Passo2 – Variáveis artificiais

1y1 + 1y2 + 7y3 - 1y4 + 1ya1 = 52y1 + 1y2 + 4 y3 - 1y5 + 1ya2 = 6

Passo3 – Função Objetivo Artificial

1y1 + 1y2 + 7y3 - 1y4 + 1ya1 = 52y1 + 1y2 + 4 y3 - 1y5 + 1ya2 = 63y1 + 2y2 + 11y3 -1y4 – 1y5 + 0ya1 + 0ya2 = 11

Passo3 – Criação da Matriz

BASE y1 y2 y3 y4 y5 ya1 ya2 b

ya1 1 1 7 -1 0 1 0 5 /7ya2 2 1 4 0 -1 0 1 6 /4

z -14 -9 -56 0 0 0 0 0 Entra y3 (mais negativo) eza -3 -2 -11 1 1 0 0 -11 sai ya1 por ser o menor

BASE y1 y2 y3 y4 y5 ya1 ya2 b

y3 1 1 7 -1 0 1 0 5 /lin (7)ya2 2 1 4 0 -1 0 1 6

z -14 -9 -56 0 0 0 0 0za -3 -2 -11 1 1 0 0 -11

BASE y1 y2 y3 y4 y5 ya1 ya2 b

y3 1/7 1/7 1 -1/7 0 1/7 0 5/7 Mult (-4) + lin ya2ya2 2 1 4 0 -1 0 1 6

z -14 -9 -56 0 0 0 0 0za -3 -2 -11 1 1 0 0 -11

BASE y1 y2 y3 y4 y5 ya1 ya2 b

y3 1/7 1/7 1 -1/7 0 1/7 0 5/7 Mult (56) + lin zya2 10/7 3/7 0 4/7 -1 -4/7 1 22/7

z -14 -9 -56 0 0 0 0 0za -3 -2 -11 1 1 0 0 -11

BASE y1 y2 y3 y4 y5 ya1 ya2 b

y3 1/7 1/7 1 -1/7 0 1/7 0 5/7 Mult (11) + lin zaya2 10/7 3/7 0 4/7 -1 -4/7 1 22/7

z -6 -1 0 -8 0 8 0 40za -3 -2 -11 1 1 0 0 -11

BASE y1 y2 y3 y4 y5 ya1 ya2 b

y3 1/7 1/7 1 -1/7 0 1/7 0 5/7 / 1/7 = 5ya2 10/7 3/7 0 4/7 -1 -4/7 1 22/7 / 10/7 = 2,2

z -6 -1 0 -8 0 8 0 40 Sai ya2 e entra y1za -10/7 -3/7 0 -4/7 1 11/7 0 -22/7

BASE y1 y2 y3 y4 y5 ya1 ya2 b

y3 1/7 1/7 1 -1/7 0 1/7 0 5/7y1 10/7 3/7 0 4/7 -1 -4/7 1 22/7 /lin 10/7z -6 -1 0 -8 0 8 0 40

za -10/7 -3/7 0 -4/7 1 11/7 0 -22/7

BASE y1 y2 y3 y4 y5 ya1 ya2 by3 1/7 1/7 1 -1/7 0 1/7 0 5/7y1 1 3/10 0 4/10 -7/10 -4/10 7/10 22/10 Mult (-1/7) + lin y3z -6 -1 0 -8 0 8 0 40

za -10/7 -3/7 0 -4/7 1 11/7 0 -22/7

BASE y1 y2 y3 y4 y5 ya1 ya2 by3 0 1/10 1 -1/5 1/10 1/5 -1/10 2/5y1 1 3/10 0 4/10 -7/10 -4/10 7/10 22/10 Mult (6) + lin zz -6 -1 0 -8 0 8 0 40

za -10/7 -3/7 0 -4/7 1 11/7 0 -22/7

BASE y1 y2 y3 y4 y5 ya1 ya2 b

y3 0 1/10 1 -1/5 1/10 1/5 -1/10 2/5y1 1 3/10 0 4/10 -7/10 -4/10 7/10 22/10 Mult (10/7) + lin zaz 0 4/5 0 -28/5 -21/5 28/5 21/5 266/5

za -10/7 -3/7 0 -4/7 1 11/7 0 -22/7

BASE y1 y2 y3 y4 y5 ya1 ya2 b

y3 0 1/10 1 -1/5 1/10 1/5 -1/10 2/5y1 1 3/10 0 4/10 -7/10 -4/10 7/10 22/10

z 0 4/5 0-

28/5 -21/5 28/5 21/5 266/5

za 078/3

5 0 0 0 1 1 0

BASE y1 y2 y3 y4 y5 b

y3 0 1/10 1 -1/5 1/10 2/5 / 1/10 = 4y1 1 3/10 0 4/10 -7/10 22/10 / 3/10 = 7,33z 0 4/5 0 -28/5 -21/5 266/5 Sai y3 e entra y2

BASE y1 y2 y3 y4 y5 b

y2 0 1/10 1 -1/5 1/10 2/5 / (1/10)y1 1 3/10 0 4/10 -7/10 22/10z 0 4/5 0 -28/5 -21/5 266/5

BASE y1 y2 y3 y4 y5 b

y2 0 1 10 -2 1 4 Mult (-3/10) + lin y1y1 1 3/10 0 4/10 -7/10 22/10z 0 4/5 0 -28/5 -21/5 266/5

BASE y1 y2 y3 y4 y5 b

y2 0 1 10 -2 1 4 Mult (-4/5) + lin zy1 1 0 -3 1 -1 1z 0 4/5 0 -28/5 -21/5 266/5

BASE y1 y2 y3

y4y5

b

y2 0 1 10 -2 1 4y1 1 0 -3 1 -1 1z 0 0 -8 -4 -5 50

y1, y2 e y3, também podem ser encontrados através da matriz Primal nesta mesma posição.

Var. de Excesso

Sol. X1 e X2 Primal c/ sinal trocado