Pesquisa Operacional - Tutorial sobre Softwares
1. Resoluo de problemas de Programao Linear utilizando
Excel
O software Excel resolve problemas de Programao Linear atravs da
ferramenta Solver.
Retomando um problema de Programao Linear j citado, tem-se:
Max lucro(x1 , x 2 ) = Z = x1 + 1.5x 2
Sujeito a:
2 x1 + 2 x 2 160
x + 2 x 120
1
2
4 x1 + 2 x 2 280
x1 , x 2 0
(1)
Para resolver este problema utilizando o Excel, deve-se montar a seguinte
planilha:
Notas de Aula - Fernando Nogueira
Pesquisa Operacional - Tutorial sobre Softwares
Os valores nas linhas 2, 3 e 4 com as colunas B e C correspondem aos
coeficientes das restries.
Os valores nas linhas 2, 3 e 4 com a coluna D correspondem ao total para
cada restrio em funo dos valores x1 e x2.
Os valores nas linhas 2, 3 e 4 com a coluna F correspondem aos valores do
lado direito das restries (recursos).
Os valores na linha 5 com as colunas B e C correspondem aos coeficientes
da funo objetivo.
Os valores na linha 6 com as colunas B e C correspondem aos valores de x1
e x2.
O valor da clula D5 o valor da funo objetivo Z.
A coluna E apenas ilustrativa, mostrando o sinal das inequaes.
Na clula D2 digitada a seguinte frmula:
=SOMARPRODUTO(B2:C2;$B$6:$C$6)
ou
=B2*B5 + C2*C5
Nas clulas D3, D4 e D5, pode-se utilizar a opo de auto preenchimento do
Excel clicando sobre a clula D2 e ento arrastando o mouse at a linha 5.
Observao: aps clicar sobre a clula D2 est ficar com a borda realada. Sobre
esta borda, no canto inferior direito aparece um quadrado e ento deve-se
posicionar o mouse sobre este quadrado para o auto preenchimento. A figura
abaixo mostra este quadrado sendo indicado por uma flecha vermelha.
Notas de Aula - Fernando Nogueira
Pesquisa Operacional - Tutorial sobre Softwares
As clulas D3, D4 e D5 devem ento ficar com as seguintes frmulas,
respectivamente:
=SOMARPRODUTO(B3:C3;$B$6:$C$6)
=SOMARPRODUTO(B4:C4;$B$6:$C$6)
=SOMARPRODUTO(B5:C5;$B$6:$C$6)
Uma vez adicionadas estas frmulas planilha pode-se alterar os valores
das clulas B6 e C6, que correspondem aos valores de x1 e x2, e verificar que os
valores
das
clulas
D2,
D3,
D4
D5
(coluna
total)
so
alterados
automaticamente. Neste ponto a planilha est pronta para utilizar a ferramenta
Solver, que ir resolver o problema de Programao Linear.
O comando Solver encontra-se no menu Ferramentas. Caso este comando
no esteja disponvel no menu Ferramentas, deve-se clicar em Ferramentas
Suplementos e selecionar a opo Solver.
Para ativar o comando Solver deve-se clicar sobre a clula D5, que
corresponde ao valor da funo objetivo, e aps em Ferramentas Solver. A
Notas de Aula - Fernando Nogueira
Pesquisa Operacional - Tutorial sobre Softwares
janela Parmetros do Solver ento ir aparecer sobre a planilha. A figura abaixo
mostra a planilha neste estgio.
Nesta janela, o campo Definir clula de destino: aparece o valor $D$5,
que corresponde ao valor da funo objetivo.
O campo Clulas variveis corresponde aos valores de x1 e x2. Assim,
pode-se selecionar com o mouse as clulas correspondentes (B6 e C6) clicando na
posio indicada pela seta vermelha na figura abaixo.
Notas de Aula - Fernando Nogueira
Pesquisa Operacional - Tutorial sobre Softwares
Aps selecionar as clulas B6 e C6, deve-se clicar na caixa Adicionar para
inserir as restries. Estas podem ser selecionadas com o mouse de maneira
anloga a realizada para selecionar as Clulas variveis.
Aps clicar na caixa Adicionar ir aparecer outra janela denominada
Adicionar restrio. Nesta janela o campo Referncia de clula: deve-se
selecionar as clulas D2, D3 e D4 e no campo Restrio deve-se selecionar as
clulas F2, F3 e F4. A figura abaixo mostra como deve ficar est janela.
Notas de Aula - Fernando Nogueira
Pesquisa Operacional - Tutorial sobre Softwares
Aps estas selees deve-se clicar na caixa Opes na janela Parmetros
do Solver e verificar se o campo Presumir modelo linear est selecionado. O
campo Presumir no negativos deve ser selecionado tambm caso os valores das
variveis devam ser no negativos.
De volta a janela Parmetros do Solver clica-se na caixa Resolver, que
ir ento resolver o problema de Programao Linear. A figura abaixo mostra a
planilha com o resultado timo.
Notas de Aula - Fernando Nogueira
Pesquisa Operacional - Tutorial sobre Softwares
Como se pode notar, os valores das clulas B6 e C6 so iguais a 40, ou seja,
os valores de x1 e x2 so iguais a 40 (valores timos). A clula D5, com valor igual
a 100, corresponde ao valor da funo objetivo.
Aps a resoluo, aparece uma janela denominada Resultados do Solver,
sendo que no canto direito aparece um campo denominado Relatrios. Pode-se
ento selecionar as opes de relatrio disponveis para visualizar demais
resultados.
1.1 Programao Linear Inteira
Quando se faz necessrio que uma ou mais variveis de controle sejam
inteiras utiliza-se restries adicionais. Considere a seguinte planilha:
Notas de Aula - Fernando Nogueira
Pesquisa Operacional - Tutorial sobre Softwares
A soluo tima (contnua) :
Para se obter a soluo tima inteira, deve-se acrescentar a seguinte uma
restrio indicando que as clulas B6 e C6 assumam apenas valores inteiros. A
caixa "parmetros do Solver" deve ficar assim:
Notas de Aula - Fernando Nogueira
Pesquisa Operacional - Tutorial sobre Softwares
A primeira restrio ($B$6:$C$6 = nmero) a que "fora" as clulas B6 e
C6 serem inteiras. Est restrio implementada na caixa "Adicionar" como na
figura abaixo.
A soluo tima (inteira) :
Notas de Aula - Fernando Nogueira
Pesquisa Operacional - Tutorial sobre Softwares
2. Resoluo de problemas de Programao Linear utilizando
Lindo
A modelagem do problema de programao linear no software Lindo se d
de maneira bastante semelhante modelagem escrita manualmente.
O modelo de programao linear deve ser digitado no seu prprio editor (ou
outro editor qualquer sendo o arquivo salvo no formato ASCII). O editor
carregado no menu FILE OPEN (se j possui algum arquivo) ou FILE NEW
(para comear um novo arquivo). O texto abaixo mostra o problema de
programao linear dado em 1) para o Lindo (este texto pode ser copiado e colado
no editor do Lindo):
.........................................................................................................................
! A EXCLAMACAO E COMENTARIO
MAX 1 X1 + 1.5 X2 !FUNCAO OBJETIVO, PODE SER MIN PARA MINIMIZAR
SUBJECT TO ! COMECA AS RESTRICOES
REST1) 2 X1 + 2 X2 <= 160 !REST1) E O NOME DA RESTRICAO 1, PODERIA SER OUTRO
REST2) 1 X1 + 2 X2 <= 120
REST3) 4 X1 + 2 X2 <= 280
END !TERMINA AS RESTRICOES
Notas de Aula - Fernando Nogueira
10
Pesquisa Operacional - Tutorial sobre Softwares
!INT E O COMANDO UTILIZADO PARA FORCAR AS VARIAVEIS ASSUMIREM VALORES 0 E 1
!EXEMPLO:
!INT 2 !FORCA AS DUAS VARIAVEIS A ASSUMIREM VALORES 0 E 1
!INT X1 !FORCA APENAS A VARIAVEL X1 ASSUMIR VALOR 0 E 1
!GIN E O COMANDO UTILIZADO PARA FORCAR AS VARIAVEIS ASSUMIREM VALORES !INTEIROS
!EXEMPLO:
!GIN 2 !FORCA AS DUAS VARIAVEIS A ASSUMIREM VALORES INTEIROS
!GIN X1 !FORCA APENAS A VARIAVEL X1 ASSUMIR VALOR INTEIRO
.........................................................................................................................
Aps digitado o modelo, o problema resolvido atravs do menu SOLVE
SOLVE.
3. Resoluo de problemas de Programao Linear utilizando
LINGO
O LINGO um software para otimizao de problemas lineares e nolineares. Este software permite utilizar uma sintaxe especfica de tal modo que
grandes problemas podem ser descritos de concisa. Segue abaixo um exemplo
desta sintaxe para um Problema de Transporte (obs: no caso de programao
linear, a mesma sintaxe utilizada no software Lindo pode ser utilizada tambm).
.........................................................................................................................
MODEL:
!isso um comentrio
!setname / member_list /: attribute_list
Implicit member_list Format Example
Set Members
1..n
1..5
1, 2, 3, 4, 5
stringM..stringN
O1..O3
O1,O2,O3
dayM..dayN
MON..FRI
MON, TUE, WED, THU, FRI
monthM..monthN
OCT..JAN
OCT, NOV, DEC, JAN
monthYearM..monthYearN
OCT2001..JAN2002
OCT2001, NOV2001, DEC2001,
JAN2002
attribute_list (PODE SER MAIS DE UM)
ORIGENS / O1..O3 / : OFERTA, LOCALIZACAO, PATIOS;
Notas de Aula - Fernando Nogueira
11
Pesquisa Operacional - Tutorial sobre Softwares
SETS:
!
ORIGENS / O1 O2 O3 / : OFERTA;
!
ORIGENS / O1 .. O3 / : OFERTA;
ORIGENS /@FILE('[Link]')/ : OFERTA;
!
!
DESTINOS / D1 D2 D3 D4 / : DEMANDA;
DESTINOS / D1 .. D4 / : DEMANDA;
DESTINOS /@FILE('[Link]')/ : DEMANDA;
LINKS(ORIGENS, DESTINOS): CUSTO, FLUXO;
ENDSETS
!FUNO OBJETIVO;
MIN = @SUM(LINKS(I,J): CUSTO(I,J)*FLUXO(I,J));
!RESTRIES PARA ORIGENS;
@FOR(ORIGENS(I):
@SUM(DESTINOS(J):FLUXO(I,J))=OFERTA(I));
!RESTRIES PARA DESTINOS;
@FOR(DESTINOS(J):
@SUM(ORIGENS(I):FLUXO(I,J))=DEMANDA(J));
!DADOS;
DATA:
!
OFERTA = 75 125 100;
!
DEMANDA = 80 65 70 85;
!
CUSTO = 464 513 654 867
352 416 690 791
995 682 388 685;
OFERTA = @FILE( '[Link]');
DEMANDA = @FILE( '[Link]');
CUSTO = @FILE( '[Link]');
ENDDATA
END
.........................................................................................................................
Segue abaixo a estrutura do arquivo [Link] utilizado no exemplo
acima, com os dados do problema (3 origens, 4 destinos, oferta em cada origem,
demanda em cada destino, custos da origem i para o destino j). O caractere "~"
delimita o conjunto de informaes que carregada a cada chamada do arquivo.
o1..o3 ~
d1..d4 ~
166057.15
673249.27
160693.58
~
283146.05
Notas de Aula - Fernando Nogueira
12
Pesquisa Operacional - Tutorial sobre Softwares
267488.36
392904.17
56461.42
~
41.93
90.50
87.74
58.94
98.76
4.36
39.85
87.36
11.06
32.79
87.52
45.90
~
4. Resoluo de problemas de Programao Linear utilizando
MPL
O software MPL, ao contrario do Lindo, permite que se utilizem vrios
"Solvers", inclusive o prprio Lindo, para a resoluo dos problemas de
programao linear. A modelagem se d de maneira bastante parecida com a
modelagem utilizada no Lindo. O texto abaixo mostra o problema de programao
linear dado em 1) para o MPL (este texto pode ser copiado e colado no editor do
MPL):
.........................................................................................................................
! A EXCLAMACAO E COMENTARIO
MAX X1 + 1.5 X2 !FUNCAO OBJETIVO, PODE SER MIN PARA MINIMIZAR
Subject to
2 X1 + 2 X2 <= 160;
X1 + 2 X2 <= 120;
4 X1 + 2 X2 <= 280;
!BINARY FORCAR AS VARIAVEIS ASSUMIREM VALORES 0 E 1
!EXEMPLO:
!BINARY X1 !FORCA APENAS A VARIAVEL X1 ASSUMIR VALOR 0 E 1
Notas de Aula - Fernando Nogueira
13
Pesquisa Operacional - Tutorial sobre Softwares
!INTEGER E O COMANDO UTILIZADO PARA FORCAR AS VARIAVEIS ASSUMIREM VALORES
!INTEIROS
!EXEMPLO:
!INTEGER X1 !FORCA APENAS A VARIAVEL X1 ASSUMIR VALOR INTEIRO
!FREE E O COMANDO UTILIZADO PARA AS VARIAVEIS ASSUMIREM VALORES LIVRES
!EXEMPLO:
! FREE X1 !DEIXA APENAS A VARIAVEL X1 ASSUMIR VALOR 0 E 1
.........................................................................................................................
Depois de digitado o modelo, o problema resolvido atravs do menu
RUNSOLVE CPLEX. Este comando ir executar o CPLEX como Solver. O Comando
SOLVE Conopt ir executar o Conopt como Solver.
O principal problema em escrever o problema de Programao Linear como
acima que para problemas grandes, tal notao se torna invivel.
Porm, possvel escrever o problema utilizando uma notao reduzida,
que ser ento interpretada pelo software.
Segue abaixo um exemplo para o problema de Programao Linear j citado
(este texto pode ser copiado e colado no editor do MPL):
.........................................................................................................................
TITLE
Problema_Classico;
{isto um comentrio}
INDEX
produto:=(x1,x2);
maquina:=(a,b,c);
DATA
coef_lucro[produto]:=(1,1.5);
coef_tec[maquina,produto]:=(2,2,
1,2,
4,2);
Notas de Aula - Fernando Nogueira
14
Pesquisa Operacional - Tutorial sobre Softwares
recurso[maquina]:=(160,120,240);
VARIABLES
producao[produto]->Prod;
MACROS {MACROS NO SO NECESSARIAS, APENAS AJUDAM A DEIXAR MAIS
COMPACTA A NOTAO}
lucro:=SUM(produto:coef_lucro*producao);
MODEL
Max Z = lucro;
SUBJECT TO
Capacidade_prod[maquina]:
SUM(produto:coef_tec*producao)<=recurso;
BOUNDS
producao>=0;
END
5. Previso utilizando o Forecast PRO 3.5
Este item tem por objetivo descrever os principais detalhes de utilizao do
software FORECAST PRO 3.5.
Inicialmente, deve-se criar uma planilha em Excel (arquivo com extenso
.xls) na qual a clula A1 contenha a palavra HORIZONTAL ou VERTICAL, que ser
utilizada para indicar que os dados das sries esto dispostos na planilha
horizontalmente ou verticalmente. As demais clulas da linha 1 e da coluna A
devem estar vazias. Os demais parmetros so: NOME da srie, COMENTRIO,
ANO (MS, SEMANA, DIA,..) INICIAL das sries histricas, MS (SEMANA, DIA,...)
INICIAL das sries histricas, NMERO DE AMOSTRAS QUE ANO (MS, SEMANA,
DIA,...)
CONTM,
PERODO
DO
FENMENO
SAZONAL,
DADO1,
DADO2,
DADO3,....
Para o caso HORIZONTAL a planilha fica:
Notas de Aula - Fernando Nogueira
15
Pesquisa Operacional - Tutorial sobre Softwares
HORIZONTAL
NOME
ANO
MS
NMERO
PERODO
da
COMENTRIO
(MS,
(SEMANA,
DE
DO
srie
SEMANA,
DIA,...)
AMOSTRAS
FENMENO
DIA,..)
INICIAL
QUE ANO
SAZONAL
INICIAL
DADO1
DADO2
...
DADO1
DADO2
...
...
...
...
(MS,
SEMANA,
DIA,...)
CONTM
ANO
MS
NMERO
PERODO
da
(MS,
(SEMANA,
DE
DO
srie
SEMANA,
DIA,...)
AMOSTRAS
FENMENO
DIA,..)
INICIAL
QUE ANO
SAZONAL
NOME
COMENTRIO
(MS,
INICIAL
SEMANA,
DIA,...)
CONTM
...
...
...
...
...
...
Para o caso VERTICAL a planilha fica:
VERTICAL
NOME da srie 1
NOME da srie 2
...
COMENTRIO
COMENTRIO
...
ANO (MS, SEMANA, DIA,..) INICIAL
ANO (MS, SEMANA, DIA,..) INICIAL
...
MS (SEMANA, DIA,...) INICIAL
MS (SEMANA, DIA,...) INICIAL
...
NMERO DE AMOSTRAS QUE ANO (MS,
NMERO DE AMOSTRAS QUE ANO (MS,
...
SEMANA, DIA,...) CONTM
SEMANA, DIA,...) CONTM
PERODO DO FENMENO SAZONAL
PERODO DO FENMENO SAZONAL
...
DADO1
DADO1
...
DADO2
DADO2
...
...
...
...
A figura A1 mostra um exemplo de planilha Excel com as sries histricas
dispostas horizontalmente.
Notas de Aula - Fernando Nogueira
16
Pesquisa Operacional - Tutorial sobre Softwares
Fig. A1 Exemplo de planilha Excel com as sries histricas dispostas horizontalmente.
De posse do arquivo com a planilha Excel abre-se este no FORECAST PRO
3.5 atravs do menu FILE -> OPEN DATABASE. A figura A2 mostra a tela do
FORECAST PRO 3.5 para essa situao.
Fig. A2 Tela do FORECAST PRO 3.5 mostrando menu FILE->OPEN DATABASE.
Notas de Aula - Fernando Nogueira
17
Pesquisa Operacional - Tutorial sobre Softwares
Uma vez aberta a planilha com as sries histricas, deve-se clicar com o
mouse no cone
(script) ou atravs do menu OPERATIONS->SCRIPT a fim de
selecionar quais as sries histricas contidas na planilha que sero utilizadas.
Para selecionar as sries histricas, o FORECAST PRO 3.5 mostra a janela
Forecast Script, como mostra a figura A3. Nesta janela, pode-se selecionar as
sries uma a uma ou selecionar todas clicando no boto Select all.
Fig. A3 Janela Forecast Script.
Para realizar a previso para mais de uma srie (como no exemplo da figura
A3 em que foram selecionadas vrias sries) deve-se utilizar o comando BATCH no
combo box que contm os mtodos de previso. A figura A4 mostra este combo
box em azul.
Notas de Aula - Fernando Nogueira
18
Pesquisa Operacional - Tutorial sobre Softwares
Fig. A4 Combo box com o comando BATCH selecionado.
Aps a seleo do comando BATCH deve-se clicar no cone
ou no menu
Operations->Forecast para realizar os clculos de previso para as sries
selecionadas. Imediatamente aps esta ao, o FORECAST PRO 3.5 apresenta a
janela Select default batch processing mode para o usurio selecionar o mtodo
de previso desejado. A figura A5 mostra esta janela.
A opo Expert Selection ir realizar os clculos para todos os mtodos
apresentados nesta janela e automaticamente selecionar o melhor mtodo para
cada srie segundo critrios prprios.
Notas de Aula - Fernando Nogueira
19
Pesquisa Operacional - Tutorial sobre Softwares
Fig. A5 Janela para selecionar o mtodo de previso a ser utilizado.
O horizonte de previso (quantas amostras aps a ltima amostra de cada
srie) determinado no menu Settings->Options na aba Basic->Forescat Horizon.
Nesta mesma aba pode-se escolher o intervalo de confiana das previses atravs
dos valores Upper confidence Limit e Lower confidence Limit.
No menu Settings->Forecast Output Design pode-se selecionar os
resultados e informaes, alm da disposio destas no arquivo de sada dos
resultados.
Para salvar o arquivo com os resultados, utiliza-se o menu FILE->SAVE
FORECASTS. Por default, o FORECAST PRO 3.5 sugere o nome do arquivo de sada
dos resultados como o mesmo nome do arquivo de entrada dos dados com ! no
comeo do nome. O formato default do arquivo de sada tambm uma planilha
Excel (extenso .xls).
No menu Graph pode-se selecionar vrias opes de grficos das sries.
O menu Operations->Adjust Forecasts exibe uma janela para alterar
manualmente os resultados das previses.
Notas de Aula - Fernando Nogueira
20