Manual Solver, Lindo e Lingo

Manual Solver, Lindo e Lingo

Pesquisa Operacional - Tutorial sobre Softwares

Notas de Aula - Fernando Nogueira 1

1. Resolução de problemas de Programação Linear utilizando Excel

O software Excel resolve problemas de Programação Linear através da ferramenta “Solver”. Retomando um problema de Programação Linear já citado, tem-se:

Para resolver este problema utilizando o Excel, deve-se montar a seguinte planilha:

Pesquisa Operacional - Tutorial sobre Softwares

Notas de Aula - Fernando Nogueira 2

Os valores nas linhas 2, 3 e 4 com as colunas B e C correspondem aos coeficientes das restrições. Os valores nas linhas 2, 3 e 4 com a coluna D correspondem ao total para cada restrição em função dos valores x1 e x2. Os valores nas linhas 2, 3 e 4 com a coluna F correspondem aos valores do lado direito das restrições (recursos).

Os valores na linha 5 com as colunas B e C correspondem aos coeficientes da função objetivo.

Os valores na linha 6 com as colunas B e C correspondem aos valores de x1 e x2. O valor da célula D5 é o valor da função objetivo Z.

A coluna E é apenas ilustrativa, mostrando o sinal das inequações. Na célula D2 é digitada a seguinte fórmula: =SOMARPRODUTO(B2:C2;$B$6:$C$6) ou =B2*B5 + C2*C5

Nas células D3, D4 e D5, pode-se utilizar a opção de auto preenchimento do

Excel clicando sobre a célula D2 e então arrastando o mouse até a linha 5. Observação: após clicar sobre a célula D2 está ficará com a borda realçada. Sobre esta borda, no canto inferior direito aparece um quadrado e então deve-se posicionar o mouse sobre este quadrado para o auto preenchimento. A figura abaixo mostra este quadrado sendo indicado por uma flecha vermelha.

Pesquisa Operacional - Tutorial sobre Softwares

Notas de Aula - Fernando Nogueira 3

As células D3, D4 e D5 devem então ficar com as seguintes fórmulas, 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 fórmulas à planilha pode-se alterar os valores das células B6 e C6, que correspondem aos valores de x1 e x2, e verificar que os valores das células D2, D3, D4 e D5 (coluna “total”) são alterados automaticamente. Neste ponto a planilha está pronta para utilizar a ferramenta “Solver”, que irá resolver o problema de Programação Linear. O comando Solver encontra-se no menu “Ferramentas”. Caso este comando não esteja disponível no menu Ferramentas, deve-se clicar em Ferramentas →

Suplementos e selecionar a opção Solver.

Para ativar o comando Solver deve-se clicar sobre a célula D5, que corresponde ao valor da função objetivo, e após em Ferramentas → Solver. A

Pesquisa Operacional - Tutorial sobre Softwares

Notas de Aula - Fernando Nogueira 4 janela “Parâmetros do Solver” então irá aparecer sobre a planilha. A figura abaixo mostra a planilha neste estágio.

Nesta janela, o campo “Definir célula de destino:” aparece o valor $D$5, que corresponde ao valor da função objetivo.

O campo “Células variáveis” corresponde aos valores de x1 e x2. Assim, pode-se selecionar com o mouse as células correspondentes (B6 e C6) clicando na posição indicada pela seta vermelha na figura abaixo.

Pesquisa Operacional - Tutorial sobre Softwares

Notas de Aula - Fernando Nogueira 5

Após selecionar as células B6 e C6, deve-se clicar na caixa “Adicionar” para inserir as restrições. Estas podem ser selecionadas com o mouse de maneira análoga a realizada para selecionar as “Células variáveis”.

Após clicar na caixa “Adicionar” irá aparecer outra janela denominada

“Adicionar restrição”. Nesta janela o campo “Referência de célula:” deve-se selecionar as células D2, D3 e D4 e no campo “Restrição” deve-se selecionar as células F2, F3 e F4. A figura abaixo mostra como deve ficar está janela.

Pesquisa Operacional - Tutorial sobre Softwares

Notas de Aula - Fernando Nogueira 6

Após estas seleções deve-se clicar na caixa “Opções” na janela “Parâmetros do Solver” e verificar se o campo “Presumir modelo linear” está selecionado. O campo “Presumir não negativos” deve ser selecionado também caso os valores das variáveis devam ser não negativos.

De volta a janela “Parâmetros do Solver” clica-se na caixa “Resolver”, que irá então resolver o problema de Programação Linear. A figura abaixo mostra a planilha com o resultado ótimo.

Pesquisa Operacional - Tutorial sobre Softwares

Notas de Aula - Fernando Nogueira 7

Como se pode notar, os valores das células B6 e C6 são iguais a 40, ou seja, os valores de x1 e x2 são iguais a 40 (valores ótimos). A célula D5, com valor igual a 100, corresponde ao valor da função objetivo.

Após a resolução, aparece uma janela denominada “Resultados do Solver”, sendo que no canto direito aparece um campo denominado “Relatórios”. Pode-se então selecionar as opções de relatório disponíveis para visualizar demais resultados.

1.1 Programação Linear Inteira

Quando se faz necessário que uma ou mais variáveis de controle sejam inteiras utiliza-se restrições adicionais. Considere a seguinte planilha:

Pesquisa Operacional - Tutorial sobre Softwares

Notas de Aula - Fernando Nogueira 8

A solução ótima (contínua) é:

Para se obter a solução ótima inteira, deve-se acrescentar a seguinte uma restrição indicando que as células B6 e C6 assumam apenas valores inteiros. A caixa "parâmetros do Solver" deve ficar assim:

Pesquisa Operacional - Tutorial sobre Softwares

Notas de Aula - Fernando Nogueira 9

A primeira restrição ($B$6:$C$6 = número) é a que "força" as células B6 e

C6 serem inteiras. Está restrição é implementada na caixa "Adicionar" como na figura abaixo.

A solução ótima (inteira) é:

Pesquisa Operacional - Tutorial sobre Softwares

Notas de Aula - Fernando Nogueira 10

2. Resolução de problemas de Programação Linear utilizando

Lindo

A modelagem do problema de programação linear no software Lindo se dá de maneira bastante semelhante à modelagem escrita manualmente.

O modelo de programação linear deve ser digitado no seu próprio 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 começar um novo arquivo). O texto abaixo mostra o problema de programação 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

Pesquisa Operacional - Tutorial sobre Softwares

Notas de Aula - Fernando Nogueira 1

!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 2 !FORCA AS DUAS VARIAVEIS A ASSUMIREM VALORES INTEIROS

!GIN X1 !FORCA APENAS A VARIAVEL X1 ASSUMIR VALOR INTEIRO

Após digitado o modelo, o problema é resolvido através do menu SOLVE →SOLVE.

3. Resolução de problemas de Programação Linear utilizando

O LINGO é um software para otimização de problemas lineares e nãolineares. Este software permite utilizar uma sintaxe específica 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 programação linear, a mesma sintaxe utilizada no software Lindo pode ser utilizada também).

MODEL: !isso é um comentário

!setname / member_list /: attribute_list

Implicit member_list Format ExampleSet Members
1..n1..5 1, 2, 3, 4, 5
stringM..stringNO1..O3 O1,O2,O3
dayM..dayNMON..FRI MON, TUE, WED, THU, FRI
monthM..monthNOCT..JAN OCT, NOV, DEC, JAN
monthYearM..monthYearN OCT2001..JAN2002OCT2001, NOV2001, DEC2001,

attribute_list (PODE SER MAIS DE UM) ORIGENS / O1..O3 / : OFERTA, LOCALIZACAO, PATIOS;

Pesquisa Operacional - Tutorial sobre Softwares

Notas de Aula - Fernando Nogueira 12

SETS: ! ORIGENS / O1 O2 O3 / : OFERTA;

! ORIGENS / O1O3 / : OFERTA;

ORIGENS /@FILE : OFERTA;

! DESTINOS / D1D4 / : DEMANDA;

! DESTINOS / D1 D2 D3 D4 / : DEMANDA; DESTINOS /@FILE : DEMANDA;

@SUM(ORIGENS(I):FLUXO(I,J))=DEMANDA(J)); !DADOS; DATA: ! OFERTA = 75 125 100;

OFERTA = @FILE( 'transporte.ldt'); DEMANDA = @FILE( 'transporte.ldt'); CUSTO = @FILE( 'transporte.ldt');

Segue abaixo a estrutura do arquivo transporte.ldt 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 informações que é carregada a cada chamada do arquivo. o1..o3 ~

Pesquisa Operacional - Tutorial sobre Softwares

Notas de Aula - Fernando Nogueira 13

4. Resolução de problemas de Programação Linear utilizando

O software MPL, ao contrario do Lindo, permite que se utilizem vários

"Solvers", inclusive o próprio Lindo, para a resolução dos problemas de programação linear. A modelagem se dá de maneira bastante parecida com a modelagem utilizada no Lindo. O texto abaixo mostra o problema de programação 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

Pesquisa Operacional - Tutorial sobre Softwares

Notas de Aula - Fernando Nogueira 14

!INTEGER X1 !FORCA APENAS A VARIAVEL X1 ASSUMIR VALOR INTEIRO

! FREE X1 !DEIXA APENAS A VARIAVEL X1 ASSUMIR VALOR 0 E 1

Depois de digitado o modelo, o problema é resolvido através do menu

RUN→SOLVE 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 Programação Linear como acima é que para problemas grandes, tal notação se torna inviável.

Porém, é possível escrever o problema utilizando uma notação reduzida, que será então interpretada pelo software.

1,2,

Segue abaixo um exemplo para o problema de Programação Linear já citado (este texto pode ser copiado e colado no editor do MPL): TITLE Problema_Classico; {isto é um comentário} INDEX produto:=(x1,x2); maquina:=(a,b,c); DATA coef_lucro[produto]:=(1,1.5); coef_tec[maquina,produto]:=(2,2, 4,2);

Pesquisa Operacional - Tutorial sobre Softwares

Notas de Aula - Fernando Nogueira 15 recurso[maquina]:=(160,120,240); VARIABLES producao[produto]->Prod;

MACROS {MACROS NÃO SÃO NECESSARIAS, APENAS AJUDAM A DEIXAR MAIS COMPACTA A NOTAÇÃO} 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. Previsão utilizando o Forecast PRO 3.5

Este item tem por objetivo descrever os principais detalhes de utilização do software FORECAST PRO 3.5.

DADO3,

Inicialmente, deve-se criar uma planilha em Excel (arquivo com extensão .xls) na qual a célula A1 contenha a palavra HORIZONTAL ou VERTICAL, que será utilizada para indicar que os dados das séries estão dispostos na planilha horizontalmente ou verticalmente. As demais células da linha 1 e da coluna A devem estar vazias. Os demais parâmetros são: NOME da série, COMENTÁRIO, ANO (MÊS, SEMANA, DIA,..) INICIAL das séries históricas, MÊS (SEMANA, DIA,...) INICIAL das séries históricas, NÚMERO DE AMOSTRAS QUE ANO (MÊS, SEMANA, DIA,...) CONTÉM, PERÍODO DO FENÔMENO SAZONAL, DADO1, DADO2, Para o caso HORIZONTAL a planilha fica:

Pesquisa Operacional - Tutorial sobre Softwares

HORIZONTAL

Notas de Aula - Fernando Nogueira 16

NOME da série 1

DADO1 DADO2

NOME da série 2

DADO1 DADO2
VERTICAL
NOME da série 1 NOME da série 2
COMENTÁRIO COMENTÁRIO
ANO (MÊS, SEMANA, DIA,..) INICIAL ANO (MÊS, SEMANA, DIA,..) INICIAL
MÊS (SEMANA, DIA,...) INICIAL MÊS (SEMANA, DIA,...) INICIAL

Para o caso VERTICAL a planilha fica:

PERÍODO DO FENÔMENO SAZONAL PERÍODO DO FENÔMENO SAZONAL
DADO1 DADO1
DADO2 DADO2

A figura A1 mostra um exemplo de planilha Excel com as séries históricas dispostas horizontalmente.

Pesquisa Operacional - Tutorial sobre Softwares

Notas de Aula - Fernando Nogueira 17

Fig. A1 – Exemplo de planilha Excel com as séries históricas dispostas horizontalmente.

De posse do arquivo com a planilha Excel abre-se este no FORECAST PRO 3.5 através do menu FILE -> OPEN DATABASE. A figura A2 mostra a tela do FORECAST PRO 3.5 para essa situação.

Fig. A2 – Tela do FORECAST PRO 3.5 mostrando menu FILE->OPEN DATABASE.

Pesquisa Operacional - Tutorial sobre Softwares

Notas de Aula - Fernando Nogueira 18

Uma vez aberta a planilha com as séries históricas, deve-se clicar com o mouse no ícone (script) ou através do menu OPERATIONS->SCRIPT a fim de selecionar quais as séries históricas contidas na planilha que serão utilizadas.

Para selecionar as séries históricas, o FORECAST PRO 3.5 mostra a janela

“Forecast Script”, como mostra a figura A3. Nesta janela, pode-se selecionar as séries uma a uma ou selecionar todas clicando no botão “Select all”.

Fig. A3 – Janela Forecast Script.

Para realizar a previsão para mais de uma série (como no exemplo da figura

A3 em que foram selecionadas várias séries) deve-se utilizar o comando BATCH no combo box que contém os métodos de previsão. A figura A4 mostra este combo box em azul.

Pesquisa Operacional - Tutorial sobre Softwares

Notas de Aula - Fernando Nogueira 19

Fig. A4 – Combo box com o comando BATCH selecionado.

Após a seleção do comando BATCH deve-se clicar no ícone ou no menu

Operations->Forecast para realizar os cálculos de previsão para as séries selecionadas. Imediatamente após esta ação, o FORECAST PRO 3.5 apresenta a janela “Select default batch processing mode” para o usuário selecionar o método de previsão desejado. A figura A5 mostra esta janela.

A opção “Expert Selection” irá realizar os cálculos para todos os métodos apresentados nesta janela e automaticamente selecionar o melhor método para cada série segundo critérios próprios.

Pesquisa Operacional - Tutorial sobre Softwares

Notas de Aula - Fernando Nogueira 20

Fig. A5 – Janela para selecionar o método de previsão a ser utilizado.

O horizonte de previsão (quantas amostras após a última amostra de cada série) é determinado no menu Settings->Options na aba Basic->Forescat Horizon. Nesta mesma aba pode-se escolher o intervalo de confiança das previsões através dos valores “Upper confidence Limit” e “Lower confidence Limit”.

No menu Settings->Forecast Output Design pode-se selecionar os resultados e informações, além da disposição destas no arquivo de saída 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 saída dos resultados como o mesmo nome do arquivo de entrada dos dados com “!” no começo do nome. O formato default do arquivo de saída é também uma planilha Excel (extensão .xls).

No menu Graph pode-se selecionar várias opções de gráficos das séries. O menu Operations->Adjust Forecasts exibe uma janela para alterar manualmente os resultados das previsões.

Comentários