2-formulacao-de-problemas

Prévia do material em texto

Formulações de PPL que exigem transformações. 
Função de Custo Linear por Partes 
!  Anteriormente, assumimos que a contribuição de uma variável (por 
exemplo, x1) para a função-objetivo pode ser escrita como: 
f(x1) = c1x1 
 ou seja, como c1 é uma constante, a contribuição de x1 na função-
objetivo varia linearmente com x1. 
!  Vamos imaginar uma situação em que a contribuição de x1 para a 
FO varia de forma linear por partes. Por exemplo: 
Intervalo de x1 Inclinação 
0 – 10 3 (c11) 
10 – 25 5 (c12) 
25 – ∞ 7 (c13) 
x1 c1
1 
f(x1) 
c12 
c13 
10 25 
x1 
inclinação c1 
f(x1) 
17 
!  Se c11 < c12 < c13 < ... , ou seja, se as inclinações são 
monotonicamente crescentes, então a função é convexa. No caso 
das inclinações serem monotonicamente decrescentes, então a 
função é côncava. 
!  No exemplo anterior, a variável x1 pode ser particionada como: 
 y1 + y2 + y3, onde: 
 0 ≤ y1 ≤ 10 
 0 ≤ y2 ≤ 15 e se y2 > 0 então y1 = 10 
 0 ≤ y3 se y3 > 0 então y1 = 10 e y2 = 15 
x1 c1
1 
f(x1) 
c12 
c13 
10 25 
função convexa 
10 
x1 
c11 
f(x1) c12 
c13 
25 
função côncava 
restrições não-lineares 
Notar que, se o problema é de minimização e a função de custo for convexa, 
as restrições não-lineares estarão automaticamente satisfeitas. Por que? 18 
!  Imaginando que o problema seja de minimização, como no exemplo 
a função é convexa, não será preciso incluir as restrições não- 
lineares e, portanto, com a substituição da variável x1 por y1+y2+y3 
ainda teremos um modelo de PL (observar que o mesmo raciocínio 
vale para um problema de maximização com função de custo 
côncava). 
!  Temos então: 
 ou seja, f(x1) pode ser escrita como: 
 3y1 + 5y2 + 7y3 
 e as restrições: 
 y1 ≤ 10 
 y2 ≤ 15 
 devem ser acrescentadas ao conjunto de restrições do modelo 
(notar que estamos assumindo que todas as variáveis do modelo 
são não-negativas). 
Intervalo de x1 Inclinação 
0 – 10 3 (c11) 
10 – 25 5 (c12) 
25 – ∞ 7 (c13) 
19 
Minimização do Máximo de Várias Funções Lineares 
!  Seja o problema: 
 Problemas como este são muito comuns. Imagine, por exemplo, que 
as funções f1(x,y) e f2(x,y) correspondem aos tempos gastos por 
duas máquinas independentes para realizar partes de uma peça. 
Como as máquinas são independentes, a peça estará terminada 
quando a máquina mais lenta terminar seu trabalho. Mas deseja-se 
que este tempo máximo seja o menor possível. 
!  Um problema assim não é um PPL, mas pode ser transformado em 
um PPL introduzindo-se uma nova variável: 
min { z(x,y) = max [ f1(x,y) = 2x – 3y, f2(x,y) = -7x + 8y] } 
s.a x – 3y ≥ 8 
 9x + 15 y ≥ 100 
 x, y ≥ 0 
min w 
s.a w – f1(x,y) ≥ 0 
 w – f2(x,y) ≥ 0 
 x – 3y ≥ 8 
 9x + 15 y ≥ 100 
 x, y ≥ 0 
20 
Minimização de Valores Absolutos 
!  Seja um problema da forma: 
 onde cj ≥ 0 (j = 1, ..., n) e as variáveis xj (j = 1, ..., n) são irrestritas 
em sinal no problema. 
!  Todo número real x pode ser expresso como a diferença de dois 
números não-negativos x+ e x–, ou seja: 
x = x+ – x– com x+ ≥ 0 e x– ≥ 0 
 x+ é denominada parte positiva de x e x–, parte negativa de x. 
!  Dado um x, existem várias escolhas para x+ e x–, por exemplo: 
x = 5 x+ = 7 x– = 2 
 x+ = 6 x– = 1 
 x+ = 5 x– = 0 
x = –5 x+ = 2 x– = 7 
 x+ = 1 x– = 6 
 x+ = 0 x– = 5 
21 
!  Vamos escolher as partes positiva e negativa de x como: 
!  Assim escolhidos, tem-se que x+x– = 0, ou seja, pelo menos uma 
das partes será nula e, portanto: 
| x | = x+ + x– 
 Logo, substituindo | xj | por xj+ + xj– pode-se transformar o 
problema em: 
Com esta restrição, o modelo torna-se não-linear. 
Pode-se mostrar que, se 
cj ≥ 0, a restrição não-
linear pode ser 
eliminada do modelo, 
pois a solução viável 
ótima (caso exista) irá, 
necessariamente, 
satisfazer esta restrição. 
Por que? 
22 
Modelagem com Excessos e Faltas 
!  Em alguns problemas, a função-objetivo depende da comparação de 
uma função linear Σajxj com uma constante conhecida b. Considere, 
por exemplo, que em um modelo de estoque, Σajxj é a quantidade 
produzida e b é a demanda por um determinado item. 
!  se Σajxj > b, existe uma situação de excesso, o que implica em 
um custo (por exemplo, de armazenamento) de c1(Σajxj – b) 
!  se Σajxj < b, existe uma situação de falta, o que precisa ser 
penalizada em c2(b – Σajxj) 
!  Vamos imaginar que o problema é minimizar o custo total. Neste 
caso, o número (Σajxj – b) pode ser expresso como a diferença de 
dois números não-negativos y1 e y2 (como vimos anteriormente). 
Então, podemos escrever: 
 Σajxj – b = y1 – y2 ⇒ Σajxj – y1 + y2 = b 
 y1 ≥ 0, y2 ≥ 0 
 y1y2 = 0 
 Neste caso, podemos imaginar que y1 representa o excesso e y2, a 
falta. Assim, o custo total pode ser expresso como c1y1 + c2y2. 
23 
!  Como o problema é de minimização, deve-se ter c1 ≥ 0 e c2 ≥ 0, 
para garantir que a restrição y1y2 = 0 seja satisfeita, 
automaticamente, pela solução ótima do problema. 
!  Exemplo: Ajuste de curva 
!  Neste caso, basta expressar os valores de f(a,xi) – y(xi) como a 
diferença de dois números não-negativos yi+ e yi–. Assim, o 
problema pode ser formulado como: 
x y(x) 
-5 80 
-3 92 
-1 96 
0 98 
1 100 
3 105 
5 115 
Representar y(x) como uma função da forma: 
f(a,x) = a0 + a1x + a2x2 + a3x3 
Determinar os valores dos coeficientes ai (i = 0, ..., 3) 
de modo a minimizar a soma dos valores absolutos 
dos desvios f(a,x) – y(x), ou seja: 
min Σ | f(a,xi) – y(xi) | (i = 1, ..., 7) 
Notar que, neste 
caso, como os custos 
são todos iguais a 1, 
a restrição yi+yi– = 0 
estará satisfeita. 
24 
25 
Exercício 
!  Uma serralheria dispõe de pranchas de madeira de 70 cm de 
comprimento. Esta serralheria tem uma encomenda de 30 peças de 
20 cm e 51 peças de 22 cm (todas as peças têm a mesma largura 
da prancha). Pretende-se satisfazer a encomenda de modo a 
minimizar o desperdício de madeira, que é constituído pelos restos 
de cada corte e pelas peças produzidas a mais. Formular este 
problema como um PPL, identificando claramente as variáveis de 
decisão, a função-objetivo e as restrições do modelo. 
70 
20 
20 
20 
10 
22 
4 
22 
22 
20 
20 
22 
8 
26 
Neste problema temos: 
!  elementos conhecidos: padrões de corte, demanda de cada peça; 
!  elementos desconhecidos: quantas vezes um determinado padrão 
de corte será usado; 
!  objetivo a ser alcançado: minimizar o número de peças produzidas e 
as sobras; 
!  restrições: 
!  o número de peças obtidas com os padrões de corte usados 
deve ser maior ou igual à demanda das peças. 
!  sobras referentes a cada padrão usado. 
Padrões de corte 
peça p1 p2 p3 p4 p5 p6 p7 p8 p9 demanda 
20 1 0 2 1 0 3 2 1 0 30 
22 0 1 0 1 2 0 1 2 3 51 
sobra 50 48 30 28 26 10 8 6 4 
27 
Solução: 
Variáveis de decisão: 
xj = número de vezes que o padrão de corte pj foi usado; 
nk = número de peças de tamanho k produzidas; 
s = sobra total. 
Função-objetivo: 
 Min n20 + n22 + s 
Restrições: 
 x1 + 2x3 + x4 + 3x6 + 2x7 + x8 – n20 = 0 
 x2 + x4 + 2x5 + x7 + 2x8 + 3x9 – n22 = 0 
 n20 >= 30 
 n22 >= 51 
 50x1 + 48x2 + 30x3 + 28x4 + 26x5 + 10x6 + 8x7 + 6x8 + 4x9 – s = 0 
Solução do modelo: 
x6 = 10, x9 = 17, n20 = 30, n22 = 51, s = 168 
28 
!  Observe que, neste caso, na solução ótima do problema, as 
variáveis têm valores inteiros. Mera coincidência! 
!  Se as demandas fossem: 
#peças 20 cm = 31 
#peças 22 cm = 50, a solução ótima seria: 
x6 = 10.333, x9 = 16.667, n20 = 31, n22 = 50, s = 170 
!  Existem PPLs em que a solução ótima leva sempre a valores inteiros 
para as variáveis de decisão. 
Definições: 
!  Uma matriz quadrada inteira A é unimodular se |det(A)|=1. 
!  Uma matriz inteira A é totalmente unimodular se toda submatriz 
quadrada não-singular de A é unimodular. 
Teorema: 
!  Seja P um PPL na forma padrão: z = min { cx | Ax = b, x ≥ 0 }. 
Se A é totalmente unimodular e b é um vetor inteiro, então o 
conjunto das soluções viáveis de P é um conjunto de inteiros. 
Portanto, a solução ótima de P é inteira.29 
Exercício 
!  Uma empresa produz apenas cômodas e armários. Cada cômoda é 
composta por uma base, 3 gavetas grandes e 2 gavetas pequenas. 
Cada armário é composto por uma base, 2 portas e 2 gavetas 
grandes (iguais às gavetas grandes das cômodas). Cada 
componente dos móveis pode ser processado nas duas seções da 
empresa, cujos tempos de processamento (em horas) são: 
Produto Seção 1 Seção 2 
Base de cômoda 6 4 
Base de armário 6 8 
Gaveta grande 2 2 
Gaveta pequena 1 2 
Porta de armário 3 3 
Tempo disponível 200 150 
30 
!  É possível adquirir mais horas de trabalho para a seção 2, com um 
custo adicional de $10/hora, e num máximo de 80 horas. As gavetas 
podem ser compradas (em parte ou na totalidade) de uma outra 
empresa, implicando um custo adicional de $4/gaveta grande e de 
$3/gaveta pequena. Caso não existam custos adicionais, o lucro 
obtido com cada cômoda é de $35 e o lucro obtido com cada 
armário é de $45. O objetivo da empresa é maximizar o lucro total. 
!  Formular o problema como um PPL, indicando o significado de cada 
variável e de cada restrição. 
Variáveis: 
!  nc = número de cômodas produzidas 
!  na = número de armários produzidos 
!  bcj = qtd de bases de cômodas a produzir na seção j 
!  baj = qtd de bases de armários a produzir na seção j 
!  ggpj = qtd de gavetas grandes a produzir na seção j 
!  gppj = qtd de gavetas pequenas a produzir na seção j 
!  paj = qtd de portas de armário a produzir na seção j 
31 
!  ggc = qtd de gavetas grandes compradas 
!  gpc = qtd de gavetas pequenas compradas 
!  he = horas extras adquiridas para a seção 2 
Função-objetivo: 
Max 35 nc + 45 na – 4 ggc – 3 gpc – 10 he 
Restrições: 
ngg = ggp1 + ggp2 + ggc 
ngp = gpp1 + gpp2 + gpc 
bc = bc1 + bc2 
ba = ba1 + ba2 
pa = pa1 + pa2 
bc >= nc 
ngg >= 3 nc + 2 na 
ngp >= 2 nc 
32 
Restrições (cont.) 
ba >= na 
pa >= 2 na 
6 bc1 + 6 ba1 + 2 ggp1 + gpp1 + 3 pa1 <= 200 
4 bc2 + 8 ba2 + 2 ggp2 + 2 gpp2 + 3 pa2 <= 150 + he 
he <= 80 
Solução do modelo: FO = 1254.166667 
nc = 37.500000 
na = 16.666667 
ngg = 145.833333 ggc = 145.833333 
ngp = 75.000000 gpc = 75.000000 
bc = 37.500000 bc2 = 37.500000 
ba = 16.666667 ba1 = 16.666667 
pa = 33.333333 pa1 = 33.333333