como usar o solver- planilha de otimização em programação linear

Prévia do material em texto

Universidade do Minho Escola de Engenharia Departamento
Campus de Gualtar de Produção
4710-057 Braga e Sistemas
Microsoft Excel na resolução de problemas de
optimização
Manual da disciplina de Métodos Numéricos II
A. Ismael F. Vaz
M. Teresa T. Monteiro
Universidade do Minho - Escola de Engenharia - Departamento de Produção e Sistemas - Campus de Gualtar - 4710-057 Braga
Tel.: +351 253 604740 Fax: +351 253 604741 Email: {aivaz,mtm}@dps.uminho.pt
Conteúdo
Lista de Figuras ii
Resumo iii
1 Introdução 1
1.1 Conceitos básicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Instalação do solver . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 Problema exemplo de optimização não linear 3
2.1 O problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 Formulação do problema em Excel . . . . . . . . . . . . . . . . . . . . . . 3
3 Resolução do problema exemplo 6
4 Opções para o Solver 14
i
Lista de Figuras
1.1 Entrada de referência a células. . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Navegação para entrada de referência a células. . . . . . . . . . . . . . . . 1
1.3 Janela de instalação do Solver. . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.1 Problema exemplo inserido no Excel. . . . . . . . . . . . . . . . . . . . . . 5
3.1 Janela inicial do solver. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.2 Janela do solver parcialmente preenchida. . . . . . . . . . . . . . . . . . . 7
3.3 Janela de adição de restrições. . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.4 Janela de adição de restrições preenchida. . . . . . . . . . . . . . . . . . . 8
3.5 Janela do solver preenchida. . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.6 Janela com a solução. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.7 Janela com o relatório da solução. . . . . . . . . . . . . . . . . . . . . . . . 11
3.8 Janela com o relatório de sensibilidade da solução. . . . . . . . . . . . . . . 12
3.9 Janela com o relatório de limites da solução. . . . . . . . . . . . . . . . . . 13
4.1 Janela de opções. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.2 Gravação do modelo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4.3 Leitura do modelo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
ii
Resumo
Este relatório tem como objectivo servir de manual de apoio às aulas práticas de utiliza-
ção do solver do Excel, da disciplina de Métodos Numéricos II, leccionada ao curso de
Engenharia Biológica da Universidade do Minho.
O manual não se destina a descrever o funcionamento completo, nem todo o potencial
do Excel, mas sim como se pode usar o solver para resolver problemas de optimização.
A versão usada neste manual corresponde ao Microsoft c©Excel 2000.
iii
Capítulo 1
Introdução
Serão apresentados de seguida alguns conceitos básicos necessários ao uso do Excel. Apresenta-
se de seguida o procedimento de instalação do solver.
1.1 Conceitos básicos
O Excel é uma aplicação que implementa o conceito de Folha de Cálculo. Um documento
Excel é constituído por uma conjunto de folhas (sheets) de cálculo, que por sua vez são
constituídas por células (cells). Uma célula é identificada pela intersecção de uma coluna
com uma linha. Por exemplo a célula A2 corresponde à célula de intersecção da coluna A
com a linha 2. A2 corresponde a uma referência relativa enquanto que $A$2 corresponde
a uma referência absoluta. Quando a aplicação necessita de uma referência, a uma ou
várias células, aparece o gráfico da Figura 1.1. O utilizador pode simplesmente escrever
Figura 1.1: Entrada de referência a células.
a referência da célula ou clicar no botão da direita para navegar pelo documento. Na
navegação pelo documento aparece o gráfico apresentado na Figura 1.2. Neste caso o
Figura 1.2: Navegação para entrada de referência a células.
utilizador deve seleccionar as células em questão e clicar no botão da direita, voltando ao
ponto de partida, antes da navegação.
1
CAPÍTULO 1. INTRODUÇÃO 2
1.2 Instalação do solver
O solver é utilizado através da selecção, no menu das ferramentas (Tools), do sub-menu
Solver.
Se o sub-menu Solver não existir significa que não tem este Add-In instalado. Para a
sua instalação seleccione o sub-menu Add-Ins... dentro do menu Tools. Aparece no monitor
a janela apresentada na Figura 1.3.
Figura 1.3: Janela de instalação do Solver.
Certifique-se que a opção Solver Add-In está seleccionada e prima OK. O sub-menu
Solver passará a constar no menu Tools.
Nota 1 Poderá ser necessário a instalação de ficheiros no seu computador.
UM - EE - DPS - Subgrupo de Métodos Numéricos e Estatísticos Fevereiro 2003
Capítulo 2
Problema exemplo de optimização não
linear
2.1 O problema
Para ilustrar o uso do Excel na resolução de problemas de optimização usar-se-á o seguinte
problema
min
x1,x2,x3∈D
f(x) ≡ 0.2x3 − 0.8x1
s.a h1(x) ≡ x2 − ex1 ≥ 0
h2(x) ≡ x3 − ex2 ≥ 0
D = [0, 100]× [0, 100]× [0, 10].
(1)
Usando a aproximação inicial x0 = (x01, x02, x03)T = (0, 1.05, 2.9)T .
2.2 Formulação do problema em Excel
O primeiro passo consiste na identificação das variáveis do problema, neste caso x1, x2 e
x3. As variáveis correspondem a células na folha de cálculo. A aproximação inicial deve
ser colocada nas respectivas células. Por exemplo considere-se a correspondência indicada
na seguinte tabela.
Variável Célula Conteúdo
x1 A3 0
x2 B3 1.05
x3 C3 2.9
O segundo passo consiste na descrição da função objectivo e das funções das restrições.
A fórmula correspondente à função objectivo é
3
CAPÍTULO 2. PROBLEMA EXEMPLO DE OPTIMIZAÇÃO NÃO LINEAR 4
0.2*C3-0.8*A3
e as restrições
B3-exp(A3)
C3-exp(B3).
Estas fórmulas devem também ser inseridas em células.
Nota 2 Pode-se usar qualquer procedimento permitido pelo Excel para inserir as referidas
fórmulas. Neste caso, uma vez que as fórmulas são simples, o procedimento mais rápido é
o de escrever directamente o texto na respectiva célula, não esquecendo que uma fórmula
em Excel inicia-se sempre pelo sinal =.
As fórmulas neste caso foram inseridas nas células D3 (função objectivo), A6 (função
h1(x)) e B6 (função h2(x)).
As restrições x ∈ D não necessitam, neste momento, de atenção especial, uma vez que
são restrições do tipo limite simples.
Introduzindo alguns comentários, juntamente com os dados do problema resulta numa
folha de cálculo como se mostra na Figura 2.1.
UM - EE - DPS - Subgrupo de Métodos Numéricos e Estatísticos Fevereiro 2003
CAPÍTULO 2. PROBLEMA EXEMPLO DE OPTIMIZAÇÃO NÃO LINEAR 5
Figura 2.1: Problema exemplo inserido no Excel.
UM - EE - DPS - Subgrupo de Métodos Numéricos e Estatísticos Fevereiro 2003
Capítulo 3
Resolução do problema exemplo
A janela apresentada na Figura 3.1 aparece quando se selecciona o sub-menu Solver do
menu Tools.
Figura 3.1: Janela inicial do solver.
Os botões apresentados, na Figura 3.1, à direita são Solve, Close, Options, Reset all e
Help e servem, respectivamente, para resolver o problema com os dados fornecidos, fechar a
janela, modificar as opções do algoritmo usado, limpar todos os campos da janela e chamar
o sistema de ajuda do Excel. A janela apresentada após seleccionar o botão Options será
descrita no próximo capítulo. O botão Solve resolve o problema com os dados indicados. O
preenchimento desses dados será descrito de seguida, para já não se farão mais comentários
6
CAPÍTULO 3. RESOLUÇÃO DO PROBLEMA EXEMPLO 7
acerca dos restantes botões.
Começa-se por indicar qual a função objectivo do problema através do preenchimento
do campo Set Target Cell:. Este pode ser feito através de um simples click na célula D3.
O problema em questão é um problema de minimização da função objectivo, pelo quedeve ser seleccionado, no campo Equal to: a opção Min. A opção Max refere-se a um
problema em que a função objectivo é maximizada e a opção Value of: quando se pretende
que a função objectivo, na solução, seja igual ao valor indicado.
O campo By Changing Cells: indica as células que são variáveis do problema. O botão
Guess tenta adivinhar quais são as variáveis do problema, através da análise das células
cuja referência é feita na fórmula da função objectivo. Neste caso o botão Guess não
produz um resultado satisfatório, uma vez que a variável x2 (célula B3 ) não é usada na
função objectivo. Neste caso o preenchimento pode ser feito através da selecção das células
A3, B3 e C3 (clicar na célula A3 e arrastar até à célula C3 ).
Nesta altura, e antes de se proceder à descrição das restrições, a janela encontra-se
preenchida como se mostra na Figura 3.2.
Figura 3.2: Janela do solver parcialmente preenchida.
O campo Subject to the Constraints: possui à esquerda uma lista de restrições do
problema (neste momento vazia) e à direita três botões. Os botões Change e Delete têm
de ser precedidos da selecção de uma restrição na lista de restrições. O botão Delete remove
essa restrição da lista, enquanto que o botão Change abre uma nova janela que permite
modificar a restrição seleccionada. A janela para modificar uma restrição é semelhante à
janela que adiciona uma restrição, pelo que não será descrita em detalhe.
UM - EE - DPS - Subgrupo de Métodos Numéricos e Estatísticos Fevereiro 2003
CAPÍTULO 3. RESOLUÇÃO DO PROBLEMA EXEMPLO 8
Premindo o botão Add aparece a janela da Figura 3.3.
Figura 3.3: Janela de adição de restrições.
A introdução das restrições é feita da seguinte forma. No campo Cell Reference deve-se
introduzir uma referência à célula que contém o valor a ser restrito. No caso da primeira
restrição, será a célula A6. O tipo de restrição é seleccionado na lista de relações. Neste
caso é uma restrição de ≥, pelo que este sinal deve ser seleccionado. O campo Constraint:
deve conter um valor ou uma referência a outra célula. Neste caso será indicado o valor 0.
Após o preenchimento, a janela fica como indicada na Figura 3.4.
Figura 3.4: Janela de adição de restrições preenchida.
Se usar o botão Add é adicionada a restrição à lista de restrições e continua-se na
mesma janela, para permitir adicionar mais restrições. Se usar o botão OK a restrição é
adicionada e retorna-se à janela anterior. Após adicionar todas as restrições (duas restrições
de desigualdade mais as restrições x ∈ D) a janela do Solver fica como se mostra na Figura
3.5.
Finalmente para resolver o problema prima-se o botão Solve. Após resolvido o problema
aparece a janela indicada na Figura 3.6. As células referentes às variáveis encontram-se
alteradas para reflectir a solução encontrada pelo solver.
O utilizador tem a opção de aceitar os valores encontrados para o problema (Keep
Solver Solution) ou de anular a alteração (Restore Original Values). O utilizador pode
UM - EE - DPS - Subgrupo de Métodos Numéricos e Estatísticos Fevereiro 2003
CAPÍTULO 3. RESOLUÇÃO DO PROBLEMA EXEMPLO 9
Figura 3.5: Janela do solver preenchida.
ainda pedir a inclusão no documento de trabalho de folha(s) com relatório(s) acerca do
processo de optimização.
A folha de cálculo com o relatório da solução encontrada (Answer) é apresentado na
Figura 3.7.
Este relatório merece alguns comentários. A tabela Target Cell refere-se à função
objectivo. São apresentados os valores anteriores e posteriores à optimização. A tabela
Adjustable Cells refere-se às variáveis do problema, mais uma vez com os valores antes e
depois da optimização. A tabela Constraints refere-se às restrições. As duas primeiras res-
trições encontram-se activas na solução encontrada, enquanto as restantes estão inactivas.
Slack representa a diferença para o respectivo limite.
A folha de cálculo com a análise de sensibilidade (Sensitivity) é apresentada na Figura
3.8. Este relatório apresenta as variáveis na solução e o respectivo gradiente reduzido.
Apresenta ainda os multiplicadores de Lagrange na solução encontrada.
A folha de cálculo com a análise dos limites das variáveis (Limits) é apresentada na
Figura limits.
Este relatório apresenta valores para os limites das variáveis. O limite inferior é o valor
mais pequeno que a variável pode tomar, mantendo as restantes fixas e satisfazendo as
restrições. O limite superior diz respeito ao maior valor.
O botão Save Scenario permite guardar vários cenários que corresponde a diferentes
conteúdos das células em instantes diferentes. Esta é uma facilidade fornecida pelo Excel
que não é particular do Solver e como tal não será descrita com mais detalhe.
UM - EE - DPS - Subgrupo de Métodos Numéricos e Estatísticos Fevereiro 2003
CAPÍTULO 3. RESOLUÇÃO DO PROBLEMA EXEMPLO 10
Figura 3.6: Janela com a solução.
UM - EE - DPS - Subgrupo de Métodos Numéricos e Estatísticos Fevereiro 2003
CAPÍTULO 3. RESOLUÇÃO DO PROBLEMA EXEMPLO 11
Figura 3.7: Janela com o relatório da solução.
UM - EE - DPS - Subgrupo de Métodos Numéricos e Estatísticos Fevereiro 2003
CAPÍTULO 3. RESOLUÇÃO DO PROBLEMA EXEMPLO 12
Figura 3.8: Janela com o relatório de sensibilidade da solução.
UM - EE - DPS - Subgrupo de Métodos Numéricos e Estatísticos Fevereiro 2003
CAPÍTULO 3. RESOLUÇÃO DO PROBLEMA EXEMPLO 13
Figura 3.9: Janela com o relatório de limites da solução.
UM - EE - DPS - Subgrupo de Métodos Numéricos e Estatísticos Fevereiro 2003
Capítulo 4
Opções para o Solver
Usando o botão Options na janela do Solver aparece uma nova janela de opções para o
Solver. A Figura 4.1 apresenta a referida janela.
Figura 4.1: Janela de opções.
Os botões da direita são: OK para terminar aceitando as modificações das opções en-
tretanto efectuadas, Cancel para terminar sem alterar as opções anteriores e Help para
obter ajuda do Excel. Os botões Load Model e Save Model merecem uma descrição mais
14
CAPÍTULO 4. OPÇÕES PARA O SOLVER 15
pormenorizada. O modelo do problema descrito na janela do Solver não é guardado auto-
maticamente com o documento. Assim se se pretende guardar o modelo (função objectivo,
restrições e opções) deve-se usar o botão Save Model. Esta opção espera por uma selecção
de um conjunto de células onde guarda a informação acerca do modelo. Na Figura 4.2
apresenta-se a selecção da área para guardar o modelo.
Quando se pretender ler o modelo deve-se usar o botão Load Model e seleccionar a área
onde o modelo foi previamente guardado, como se indica na Figura 4.3.
A opção Assume Linear Model deve ser seleccionada quando o problema é de progra-
mação linear (função objectivo e restrições do tipo linear).
A opção Assume Non-Negative deve ser seleccionada quando as variáveis não podem
ser negativas (é equivalente à restrição A3:C3>=0 ).
A opção Use Automatic Scaling faz um escalonamento automático, quando as variáveis
envolvidas são muito diferentes em magnitude.
A opção Show Iteration Results faz com que o procedimento apresente, iteração a
iteração, a evolução nas respectivas células. Esta opção permite que se gravem vários
cenários, correspondendo a iterações do algoritmo.
O tempo máximo e o número de iterações pode ser controlado através das opções Max
Time: e Iterations:, respectivamente.
A precisão da solução pode ser controlada através das opções Precision: e Convergence:
que se referem à violação máxima permitida das restrições e ao erro relativo entre sucessivas
aproximações da função objectivo. O Solver pára quando o erro relativo é inferior ao valor
da convergência nas últimas cinco iterações.
A opção Tolerance: refere-se à percentagem entre a função objectivo na solução, que
satisfaz as restrições inteiras, e o verdadeiro valor. Apenas é usada para nas restrições
inteiras.
A opção Estimates refere-se ao uso de uma extrapolação linear de um vectortangente
(Tangent) ou ao uso da extrapolação quadrática (Quadratic) na procura uni-dimensional.
A opção Derivatives especifica se se deve usar diferenças ascendentes (Forward) ou
centrais (Center) no cálculo de estimativas para as primeiras derivadas.
A opção Search refere-se ao uso do algoritmo quasi-Newton (Newton) ou dos Gradientes
conjugados (Conjugate).
UM - EE - DPS - Subgrupo de Métodos Numéricos e Estatísticos Fevereiro 2003
CAPÍTULO 4. OPÇÕES PARA O SOLVER 16
Figura 4.2: Gravação do modelo.
UM - EE - DPS - Subgrupo de Métodos Numéricos e Estatísticos Fevereiro 2003
CAPÍTULO 4. OPÇÕES PARA O SOLVER 17
Figura 4.3: Leitura do modelo.
UM - EE - DPS - Subgrupo de Métodos Numéricos e Estatísticos Fevereiro 2003