Utilizando o EXCEL Solver
Outubro de 2000
2
A opção Solver no Excel pode ser utilizada para resolver problemas de otimização lineares e nãolineares. As restrições de inteiros podem ser colocadas nas variáveis de decisão. O Solver pode ser utilizado para
resolver problemas com até 200 variáveis de decisão, 100 restrições implícitas e 400 restrições simples (limites
inferior e superior e/ou restrições de inteiros nas variáveis de decisão). Para ativar o Solver, selecione
Ferramentas no menu principal e, a seguir, Solver. A caixa de diálogo Parâmetros do Solver será exibida
como mostrado a seguir.
3
Caixa de Diálogo Parâmetros do Solver
A Caixa de Diálogo Parâmetros do Solver é utilizada para descrever o problema de otimização para o
Excel. A caixa Definir célula de destino deve conter a localização da célula da função de objetivo para o
problema em consideração. Máx ou Mín podem ser selecionados para encontrar o máximo ou mínimo da célula alvo. Se Valor de for selecionado, o Solver tentará encontrar um valor para a Célula -Alvo igual a qualquer valor
colocado na caixa, logo à direita dessa seleção. A caixa Células variáveis deve conter a localização das variáveis
de decisão para o problema. Finalmente, as restrições devem ser especificadas na caixa Submeter às restrições,
clicando-se em Adicionar. Alterar permite a modificação de uma restrição já inserida e Excluir permite a
exclusão de uma restrição previamente inserida. Redefinir tudo limpa o problema atual e reinicializa todos os
parâmetros aos seus valores padrão. Opções ativa a caixa de diálogo de opções do Solver (a ser discutido mais
adiante). A caixa de seleção Estimar não é particularmente útil para nossos objetivos e não será discutida aqui.
As partes relevantes da caixa de diálogo Parâmetros do Solver estão identificadas abaixo para uma referência
mais fácil.
Localização da Célula da Função de Objetivo
Resolver Problema
Máx. ou Mín.?
Ativar Opções do Solver
Adicionar uma restrição
Alterar uma restrição
Excluir uma restrição
Localização da Célula da
Variável de Decisão
Limpar Modelo Atual
Conjunto de Restrições
Quando o botão Adicionar é clicado, a caixa de diálogo Adicionar restrição é exibida:
4
Referência à Célula de
Restrição ou conjunto de
Células de Referência
Fórmula, Célula de
Referência ou Valor
Tipo de Restrição
Ao clicar na Caixa Referência de célula, você pode especificar uma localização de célula (normalmente uma
célula com uma fórmula). O tipo de restrição pode ser definido por meio da seleção com a seta para baixo
(<=, >=, =, int, onde int significa inteiro ou bin significa binário). A caixa Re strição pode conter uma fórmula de
células, uma referência de célula simples ou um valor numérico. O botão Adicionar adiciona a restrição
atualmente especificada ao modelo existente e retorna à caixa de diálogo Adicionar Restrição. O botão OK
adiciona a restrição atual ao modelo e retorna à caixa de diálogo do Solver. Nota: O Solver não supõe nãonegatividade das variáveis de decisão. A caixa de diálogo de opções discutida abaixo permite a especificação
das variáveis como não-negativas.
Se o botão Opções for selecionado na caixa de diálogo Parâmetros do Solver, a caixa de diálogo a seguir será
exibida:
Solução de LP dentro
desse % de Idealização
Utilizar Algoritmo Simplex
Supor Não-Negatividade
Opções Não-Lineares
5
Tempo máximo permite a definição do número de segundos antes do Solver parar. Iterações, de forma similar
ao Tempo Máximo, permitem a especificação do número máximo de iterações (passos do algoritmo do Solver)
antes de parar. Precisão é o grau de precisão do algoritmo do Solver (por exemplo, quão próximo do valor o lado
esquerdo de uma restrição ele deve estar antes de ser considerado igual ao lado direito). Tolerância é usada para
programas de inteiros. Ela especifica uma porcentagem dentro da qual a solução é garantida como sendo a ótima.
Se você busca a solução ideal, esse valor deve ser definido como zero. Se o tempo de execução for muito longo,
você pode definir um valor mais alto (caso queira aceitar uma solução dentro desse percentual de idealização).
Caso o seu modelo seja um programa linear ou um programa linear de inteiros, você deve marcar a
caixa Presumir modelo linear. Ela informa o Solver para utilizar o algoritmo simplex em vez de um algoritmo
não-linear que consumirá um tempo maior (Método do Gradiente Reduzido Generalizado). A caixa Presumir
não negativos deve ser marcada se você deseja que todas as mudanças nos seus valores de células sejam ≥ 0.
Marque Mostrar resultado de iteração se deseja ver as informações iteração a iteração (isso pode realmente
deixar as coisas mais lentas!). A caixa Usar escala automática é útil se o seu modelo apresentar uma escala
deficiente (caso as entradas tenham ordens de magnitude drasticamente diferentes). Finalmente, a seção inferior
da caixa de diálogo diz respeito às opções do algoritmo não-linear, a saber, como ele calcula as não-linearidades,
como as taxas de mudança são estimadas e o tipo de técnica de pesquisa empregada.
Falando de forma geral, os valores padrão da maioria desses parâmetros funcionam bem. A coisa
importante a ser lembrada é a marcação da caixa Presumir modelo linear se você tiver um programa linear
ou um programa linear de inteiros. Marque Presumir não negativos se quiser que as mudanças nas células
produzam somente valores não-negativos. Além disso, se estiver resolvendo um programa de inteiros e em
busca da solução ideal, certifique-se de que a Tolerância seja definida como 0%.
6
Um Exemplo: A Colorado Cattle Company1
A Colorado Cattle Company (CCC) pode comprar três tipos de ingredientes de ração animal de um
atacadista. O gado da empresa tem certas necessidades nutricionais em relação à gordura, proteínas, cálcio e
ferro. Cada vaca exige, no mínimo, 10 unidades de cálcio, não mais que 7,5 unidades de gordura, no mínimo 12
unidades de ferro e 15 unidades de proteínas por dia. A tabela abaixo mostra a quantidade de gordura, proteínas,
cálcio e ferro em cada libra dos três ingredientes de ração animal. A ração de classe 1 custa $ 0,25/libra, a de
classe 2, $ 0,10/libra e a de classe 3, $0,08/libra. O gado pode ser alimentado com uma mistura dos três tipos de
ração. A CCC gostaria de alimentar seu rebanho da forma mais econômica possível.
Dados da Colorado Cattle Company
Ingredientes da Ração (Unidades por Libra)
Classe 1
Classe 2
Classe 3
Cálcio
0,7
0,8
0
Ferro
0,9
0,8
0,8
Proteínas
0,8
1,5
0,9
Gordura
0,5
0,6
0,4
Um modelo de programação linear desse problema segue abaixo:
Considere classe1 = quantidade (em lb) da ração classe 1 a ser usada diariamente na alimentação de uma vaca
classe2 = quantidade (em lb) da ração classe 2 a ser usada diariamente na alimentação de uma vaca
classe3 = quantidade (em lb) da ração classe 3 a ser usada diariamente na alimentação de uma vaca
1
Esse problema está em Management Science, Modeling, Analysis and Interpretation, de J.D. Camm e J.R. Evans, South-Western Publishing Co.,
Cincinnati, Ohio, 1996.
7
Minimize
0,25 classe1 + 0,1 classe2 + 0,08 classe3
sujeita a
0,7 classe1 + 0,8 classe2 + 0 classe3 ≥ 10
(Cálcio)
0,9 classe1 + 0,8 classe2 + 0,8 classe3 ≥ 12
(Ferro)
0,8 classe1 + 1,5 classe2 + 0,9 classe3 ≥ 15
(Proteínas)
0,5 classe1 + 0,6 classe2 + 0,4 classe3 ≤ 7,5
(Gordura)
classe1, classe2, classe3 ≥ 0
Um modelo de planilha Excel desse cenário é mostrada a seguir
8
As fórmulas das células nessa planilha ocorrerão todas na seção Saídas do Modelo (isto é, Restrições):
A funç ão SUMPRODUCT efetua o produto escalar. Por exemplo, a quantidade de cálcio usada é
SUMPRODUCT(B7:D7,B15:D15) = (B7*B15 + C7*C15 + D7*D15).
Os passos a seguir são utilizados para criar o modelo de LP mostrado abaixo:
1. Selecione Ferramentas e Solver.
2. Clique na caixa Definir célula de destino e insira B26.
3. Clique em Mín.
4. Clique na caixa Células variáveis e clique e arraste o mouse na planilha de b15 para D15 (ou digite
B15:D15).
5. Clique no botão Adicionar para ativar a caixa Adicionar restrição.
6. Para inserir as restrições mínimas de necessidade: Na caixa Referência de célula, clique e insira
B20:B22, selecione o tipo >= e, a seguir, clique na caixa Restrição e digite F7:F9. Clique em
Adicionar.
7. Para inserir a restrição máxima permitida: Na caixa Referência de célula, clique e insira B24,
selecione o tipo <= e, a seguir, clique na caixa Restrição e digite G10. Clique no botão OK.
8. Finalmente, selecione Opções, Presumir não negativos e Presumir modelo linear.
9
O modelo completo na caixa de diálogo Parâmetros do Solver é o seguinte:
Para resolver o modelo, clique no botão Resolver. Após a resolução do problema, a caixa Resultados do Solver
será exibida:
Você tem a opção de manter a solução encontrada pelo Solver na planilha ou restaurar os valores originais. Além
disso, como mostrado na caixa Relatórios, três relatórios diferentes podem ser automaticamente gerados. Você
pode selecionar qualquer um deles, clicando sobre os mesmo nessa caixa. Na próxima seção descreveremos cada
um dos relatórios.
10
Relatórios do Solver
O Solver gera três relatórios para programas lineares: Relatório de Resposta, Relatório de Sensibilidade
e Relatório de Limites. Se a opção Manter solução do Solver tiver sido selecionada na caixa de resultados do
Solver, a solução ideal será mantida na própria planilha. Para o problema a Colorado Cattle Company, isso é
mostrado a seguir.
O Relatório de Resposta fornece os valores original e final da Célula de Destino e de todas as Células
Ajustáveis, bem como uma lista de cada restrição e seu status (nota: o termo Transigência descreve as variáveis
de sobra e falta). O modelo do Relatório de Resposta para a Colorado Cattle Company é mostrado na próxima
página. Observe que o EXCEL rotula a Célula de Destino, as Células Ajustáveis e as Restrições utilizando o
primeiro texto encontrado à esquerda e acima de cada uma das células.
Microsoft Excel 8.0 Relatório de resposta
Planilha: [CCC.XLS] CCC
Relatório criado: 12/11/97 08:33:07
Célula de destino (Mín)
Célula
Nome
$B$26
Custo Total
Células ajustáveis
Célula
Nome
$B$15
Qtd Classe 1
$C$15
Qtd Classe 2
$D$15
Qtd Classe 3
Restrições
Célula
$B$20
$B$21
$B$22
$B$24
Nome
Qtd. Cálcio
Qtd. Ferro
Qtd. Proteína
Qtd. Gordura
Valor original
Valor final
0
Valor original
2,59
Valor final
0
0
0
Valor da célula
Fórmula
10 $B$20>=$F$7
12 $B$21>=$F$8
15,1 $B$22>=$F$9
7,5 $B$24<=$G$10
8
5,5
0,5
Status
Agrupar
Agrupar
Sem agrupar
Agrupar
Transigência
0
0
0,1
0
11
O Relatório de Sensibilidade fornece o valor final de cada célula ajustável, seu custo reduzido, o
coeficiente da função objetivo, o acréscimo e o decréscimo do coeficiente da função objetivo para o qual a
solução atual permanecerá ótima (todo o resto é mantido fixo). Por exemplo, no Relatório de Sensibilidade da
Colorado Cattle Company mostrado abaixo, o custo da classe 1 pode diminuir em até 0,1425 e a solução atual
permanecerá como ideal. O preço-sombra para cada restrição (a variação na função objetivo por unidade de
acréscimo no lado direito) é fornecido juntamente com o acréscimo e decréscimo do valor no lado direito para o
qual o preço é válido. Por exemplo, no Relatório de Sensibilidade da Colorado Cattle Company mostrado
abaixo, um acréscimo de 0,5 unidades na quantidade de gordura (o qual está dentro do acréscimo permitido de 1
na restrição) resultará em uma variação na função de objetivo de (0,5)x(-1,14) = -0,57.
Microsoft Excel 8.0 Relatório de sensibi lidade
Planilha: [CCC.XLS] CCC
Relatório criado: 12/11/97 08:33:07
Células ajustáveis
Célula
$B$15
$C$15
$D$15
Nome
Classe 1 Qtd
Classe 2 Qtd
Classe 3 Qtd
Valor
Final
Reduzido
Custo
Objetivo
Coeficiente
8
5,5
0,5
0
0
0
10
12
15,1
Sombra
Preço
0,31
0,67
0
7,5
-1,14
0,25
0,1
0,08
Permissível
Acréscimo
1E+30
0,162857143
0,177142857
Permissível
Decréscimo
0,1425
1E+30
2,68
Permissível
Decréscimo
10
12
15
Permissível
Acréscimo
0,137931034
0,054794521
0,1
7,5
1
Restrições
Célula
$B$20
$B$21
$B$22
$B$24
Nome
Cálcio Qtd
Ferro Qtd
Proteínas
Qtd
Gordura Qtd
Valor
Final
Restrição
Lateral R.H.
4
2
1E+30
0,016949153
12
O Relatório de Limites (mostrado abaixo para o Exemplo da Colorado Cattle Company) fornece os limites
inferior e superior de cada célula ajustável, mantendo todas as outras células em seus valores atuais e
satisfazendo as restrições. O relatório abaixo mostra que a solução para o Exemplo da Colorado Cattle Company
é muito apertada (com duas das três células ajustáveis fixadas em seus valores de destino, a terceira tem limites
inferior e superior iguais ao seu valor de destino).
Microsoft Excel 8.0 Relatório de limites
Planilha: [CCC.XLS] CCC
Relatório criado: 12/11/97 08:33:07
Nome
Célula Destino
$B$26 Custo
Total
Nome
Célula Ajustável
$B$15 Classe 1
Qtd
$C$15 Classe 2
Qtd
$D$15 Classe 3
Qtd
Valor
2,59
Limite
Inferior
Valor
8
Resultado
Destino
8
2,59
Limite
Superior
Resultado
Destino
8
2,59
5,5
5,5
2,59
5,5
2,59
0,5
0,5
2,59
0,5
2,59
Resolvendo Problemas de Inteiros e Não-Lineares
A resolução de modelos lineares de inteiros, modelos não-lineares e mesmo modelos de inteiros nãolineares é obtida por meio das mesmas técnicas previamente descritas. Para especificar uma restrição como
inteiro, ative a caixa de diálogo Adicionar Restrição, selecione a célula ajustável em Referência de célula e
selecione o tipo int (inteiro) (para variáveis binárias, selecione bin). Para modelos não-lineares, simplesmente
não especifique Presumir modelo linear na caixa de diálogo Opções.