GAMS - SISTEMA GERAL DE MODELAGEM ALGÉBRICA

Prévia do material em texto

ANTHONY BROOKE . DAVID KENDRIK
ALEXANDER MEERAUS
oTtMtzAçÃo
MODETO DEctsÃo
PROG
rónuuH
srMunçÃo
vArrolçÃo
ESCoP0 OBJETIVO
SISTEMA
GAMS
SISTEMA
GERAL DE
MODELAGEM
ALGÉeRIcA
JMStern Pesquisa operacionat EDIroRA t""gf er-ücsER''or"
ANTHONY BROOKE
DAVID KENDRICK
ALEXANDER MEERAUS
GAMS
SIsTEnaa GEnNL DE MOOENGEM AI-CÉENICN
Traducão
JACOB Nr,gANõ SOBRINHO
Ph.D. pela Univesidade de São Paulo
Professor adiunto do Instituto de Matemática da USP
Supervisão técnica
JULIO MICHAEL STERN
Ph.D. pela Univesidade de Cornell. EUA
Dirètor do Centro de Matemática e
ComputaçãoAplicadas do IME - USP
JMStern Pesquisa Operacional
/
F\t
EDITORA EDGAFID EIIJCHER TToI
O 1997 AnthonY Brooke
David Kendrick
Alexander Meeraus
ls edição - 1997
É proíbida a reproilução total ou parcíal
Por quaisquer meios
sem aú0rtgção escríta da editora
EDITORA EDGARD BLÜ CHER LTDA'
Fax: (0/1) 852-2707
Caixa Postal5450
01061-970 - S. Paulo - SP - Brasil
Impresso no Brasil Printed in Brazil
^u !vÃ.<, r
êr .z:Z:\.'f
Fs ,A?.
P- ZZZÀ\T E,
- 
---^allal
âF-.-R.R
+"ffi neë
-tè 
q or"o1o È"
EDITORA AFILIADA
Conteúdo
coxrpúoo
pnpr'ÁcIo À notçÃo eneSILEIRA
pRpr'Ácto
PARTE I - Introdução
t rNTRoouçÃo
1.1 t v to t ruaçÃo. . .
\.2 cARAcTERÍsrlcns eÁstCAS DE gÁME
(a) Princípios Gerais
(b) Documenüação
(c) Portabilidade
(d) A interface com o usuário
(e) A Biblioteca de Modelos
1.3 oRGANIzAçÃo oo LIVRo
L.4 PREPARANDO-SE PARA COMEçAR
2 UM TUTORIAL gAME
INTRODUçAO
A ESTRUTURA DE UM MoDELo 9"41ì48
C O N J U N T O S . . . .
I
vii
viii
2.L
2.2
2 .3
2.4
D
c
8
I
DADOS 1 1
1 1
13
13
t4
(a) Enürada de dados
(b) Entrada de dados
(c) Entrada de dados
por meio de listas
por meio de üabelas
por meio de atribuição direta
2.5
2.6
VARIAVEIS . .
EQUAçõES . . . . . _ . .
(a) Declaração de equações
(b) A notação de soma e produto em 9"4M8
OS ENUNCIADOS DO TIPO MODEL e SOLVE
OS ENUNCIADOS DO TIPO DISPLAY
A BASE DE DADOS u.LO, .L, .UP, .M"
(a) Atribuição do limite de variáveis e/ou valores iniciais
15
15
(c) Definição de equações
FUNçAO OBJETIVO
15
16
18
18
19
19
19
2.7
2.8
2.9
2.L0
t l Conteúdo
(b) Tlansformação e display dos valores ótimos
2.1L SAÍDA DO PROGRAMA 9"4Ìvt8
(a) Impressão de echo
(b) Mensagens de erro
(c) Mapas de referência
(d) Listagens de equações
(e) Estatísticas do modelo
(f) Relatórios de status
(g) Relatórios de solução
2.].2 CONCLUSÕES
PARTE II - A Linguasem $AÌVLS
3 PROGRAMAS g"4I4E
3.1 A ESTRUTURA DOS PROGRAMAS 9-4}48
3.2 oRcANrzAçÃo Dos pRocRAMAS 9.4'vt8
3.3 DEFTNTçÕES E TIPOS DE DADOS
3.4 Ítnus DE LINGUAGEM
(a) Caracteres
(b) Palavras Reservadas e Tokens.
(c) Identificadores
(d) Rótulos
(e) Texto
(f) Números
(g) Delimitadores
(h) Comentários
3.6 SUMÁRIO
20
2 I
2 t
23
25
26
27
27
28
30
34
34
35
37
37
37
38
38
3 9 r
40
40
47
4t
42
4 DEFINIçOES DE CONJUNTOS
CONJUNTOS SIMPLES
O ENUNCIADO ALIAS: NOMES MULTIPLOS PARA CONJUNTOS
SUBCONJUNTOS E VERIFICAçÃO DE DOMÍNrO . .
CONJUNTOS MULTIDIMENSIONAIS E FUNçÕES . .
SUMÁRIO
ENTRADA DE DADOS: PARÂMETROS, ESCALARES
& TABELAS
5.1 PARÂMETROS .
5 . 2 E S C A L A R E S . . .
5.3 TABELAS SIMPLES
5.4 TÂBELAS CONTINUADAS .
5.5 TABELAS COM MAIS DE DUAS DIMENSÕES. . .
6.6 RELAToS DE ERRoS DURANTE A CoMPILAçÃo
5-7 ENTTNCIADOS DO TIPO PARAMETER E TABLE QUE NÃO POSSUEM
vERrFrcAçÃo oo DoMÍNro
5.8 CONCLUSÕES
4.1
4.2
4.3
4.4
4.5
43
43
46
47
47
50
52
52
54
54
c c
co
58
59
60
Conteúdo i l l
6 MANTPULAçÃO DE DADOS COM PARÃMETROS
6 . 1 O E N U N C T A D O D E A T R I B U I ç Ã O . . . 6 2
6 . 2 O E N U N C I A D O D I S P L A Y . . . . . . . 6 5
6 . 3 E X P R E S S Õ E S S I M P L E S . . . . . . . . . 6 7
(a) Operações aritméticas padrão 67
(b) Operações Indexadas 68
(c) Funções 69
(d) Aritmética Estendida e Tlatamento de Erros 71
6.4 TRATAMENTO DE EXCEçOES 72
(a)OperadoresRelac iona is - . . - 72
( b ) O O p e r a d o r D ó l a r ' . . - . . 7 2
6.5 INTEGRIDADE DE DADOS E ENUNCIADO ABORT 76
6.6 UM EXEMPLO FINAL 77
6 . 7 C O N C L U S Ã O . . . 8 0
VARIÁVEIS 81
7.t DECLARAçÃo np vARIÁvEIS 81
7.2 LIMITES EM VARIÁVEIS . 84
7.3 vARrÁvEIS EM DIsPLAY E ENUNCIADos DE ATRIBUIçÃo . . . . . . 84
7.3 SUMÁRIO 86
EQUAçOES 87
8 . 1 D E C L A R A ç Ã O D E E Q U A ç Õ E S . . . . . . . . . 8 7
8.2 DEFiNIÇÕES SIMPLES DE EQUAçÕES 88
8.3 DEFTNIçÕES DE EQUAçOBS INDEXADAS . . . s1
8.4 FUNçÕES E OPEEADORES ARITMÉTICOS UTILIZADOS EM DEFINI-
ÇÕES DE EeuAçÓES e2
8.5 
-opBn,q.ÇÕES 
DOLAR EM DEFINIçÕES DE EQUAçÕES . e3
(a) Controle das operações de índice pelo Dólar 93
(b) Operadores Dólar internos à Algebra " " 93
(c) O Controle do Domínio de Definição de uma Equação pelo 
-operador Dólar 95
8.6 ASPECTOS DO TRATAMENTO DE DADOS NAS EQUAçÕES . . . . ' . 96
8.7 SUMÁRIO 96
ENUNCIADOS TIPO MODEL & SOLVE 98
62
9.1 O ENUNCIADO TIPO MODEL
9.2 CLASSTFICAçÃO DE MODELOS
9.3 O ENUNCIADO SOLVE
9.4 PROGRAMAS COM VÁNTOS ENUNCIADOS DO TIPO SOLVE . . . . . .
(a) Vários Modelos
(b) Análise de Casos e Sensibilidade, e Relatórios
(c) Implementação Iterativa de Algoritmos Não-standard
9.5 OPçOES USADAS COM ENUNCIADOS SOLVE
(a) Detalhe de Controle de Saída
(b) Controle dos Recursos do Computador Usado pelo Solver
(c) Controle de Ações tomadas pelo Solver
(d) O Controle pelo qual o Solver é Usado
98
99
100
101
101
101
103
104
104
105
106
r07
IV Conteúdo
9.6 TORNANDO NOVOS SOLVERS COMPATÍVEIS COM 9"4MS . . IO7
10 sAÍDA gc]lr's 1oe
10.1 SAÍDA DE COMPTLAçÃO . . loe
(a) Impressão de Echo do Arquivo de Entrada . . . 109
( b ) M a p a s p r o d u z i d o s . . . . . . 1 1 3
(c) Diretivas Usuais de Controle tipo Dólar . . . . 115
10.2 SAÍDANAEXECUçÃO . . . . 116
10.3 SAÍDA PRODUZIDA POR UM ENUNCIADO DO TIPO SOLVE . . . . . . 117
( a ) A l i s t a g e m d a E q u a ç ã o . . . L 1 7
( b ) A l i s t a g e m d a s C o l u n a s . . . 1 1 9
( c ) E s t a t í s t i c a s d o M o d e l o . . . . 1 1 9
( d ) O s u m á r i o d o S o l v e . . . . . L 2 0
( e ) A l i s t a g e m d a S o l u ç ã o . . . . 1 2 3
10.4 RELATÓNTO DE ERROS . . . T25
(a) Erros de Compilação . . . L26
( b ) E r r o s d e E x e c u ç ã o . . . . . . L 2 7
(c) Erros de Solve
l o .scoNcLUSÃO . . . . . r2s
].1 CONJUNTOS DINÂMICOS
1 1 . 1 C O N J U N T O S E S T Á T I C O S E D I N Â M I C O S . . . 1 3 0
1.1.2 ATRTBUIçÕES DE CONJUNTOS . . . 130
11.3 oPERAçÕES DE CONJUNTOS: UNrÕES, TNTERSECçÕES E COMPLF-
M E N T O S . . . 1 3 3
11.4 vERrFrcAÇÃO DE DOMÍNIOS COM CONJUNTOS DrNÂMICOS . . . . 134
12 CONJUNTOS COMO SEQUENCIAS:
MODELOS DINÂMICOS
12.1 CONJUNTOS ORDENADOS ENAOORDENADOS . . . . . . . . T37
L 2 . 2 C P " D E C A R D . . . . . 1 3 8
1 2 . 3 o P E R A ç Õ E S D E A V A N ç O E R E T R O C E S S O . . . . . . 1 3 e
(a) Atribuições de Avanços e Retrocessos . 139
( b ) A v a n ç o e R e t r o c e s s o e m E q u a ç õ e s . . . . L 4 1 .
L 2 . 4 O E N U N C I A D O L O O P . . . . . 1 4 3
L 2 . 5 C O N C L U S Ã O . . . . . L 4 4
PARTE III - Tópicos especrars
13 O ENUNCIADO DISPLAY
130
L37
146
13.1 A ORDEM DOS RóTULOS EM DISPLAYS . . . T47
13.2 ENIJNCTADOS DE OPçÕES QUE CONTROLAM DTSPLAYS . . . . . . . r4s
13.3 EXPORTÂçÃO DE DADOS PARA OUTROS PROGRAMAS . . . . . . . . 151
Conteúdo
L4 SALVANDO E RECOMEÇANDO: O ARQUIVO DE TRABALHO 153
1 4 . 1 o C o N C E I T o D E A R Q U I V O D E T R A B A L H O . . . . . . 1 5 3
I 4 . 2 S A L V A N D O O S A R Q U I V O S D E T R A B A L H O . . . . . . . 1 5 4
I 4 . 3 R E I N I C I A N D O . . . . 1 5 5
14.4 MANETRAS DE APROVEITAR OS ARQUIVOS DE TRABALHO . . . . . 156
(a) Programa de Desenvolvimento Incremental . . 156
(b) Lidando com Seqüências de Solves Difíceis . . . 156
( c ) C e n ár i o s m ú l t i p l o s . . . . . . 1 5 7
l 4 .5suMÁRro . . . . . . .1 .57
L5 PROGRAMAçAO NAO-LINEAR
15.1 ASPECTOS GERATS DE PROGRAMAçÃO NÃO-lWeeR . . .
(a) Valores Iniciais
(b) Limites
(c) Escalonamento
(d) Reformulação da F\rnção Objetivo
(e) Derivadas Descontínuas e Ótimos Múltiplos
15.2 ASPECTOS PARTICULARES A RESPEITO DE GAMS/MINOS
(a) O Sumário do Solve GAMS/MINOS
(b) Confronto com a não Viabilidade não-linear
(c) O Sumário da Tela
(d) Desconsiderando a Base
(e) O Uso dos Arquivos de Op,ções GAMS/MINOS ' .
].6 PROGRAMAçÃO INTEIRA MISTA
16.1 ASPECTOSGERAIS A RESPEITO DE PROGRAMAçAO INTEIRA E
MiSTA
159
159
160
160
161
r62
L62
t62
163
t64
r b b
165
165
L67
t67
(a) As'folerâncias de Término em 9,4M8 . . . . . 167
( b ) R e i n i c i a n d o a s e x e c u ç õ e s M I P . . . . . 1 6 8
16.2 ASPECTOS PARTICULARES A RESPEITO DE GAMSIZOOM . . . . . . 168
17 MODELOS DE GRANDE PORTE
17.1 PORQUE MODELOS DE GRANDE PORTE DEVEM SER EVITADOS . . 170
17.2 COMO LIDAR COM MODELOS DE GRANDE PORTE . . . . . . 171
17.3 LIMITAçÕNS DE TAMANHO EM 9'4MS E SEUS SOLVERS . . . I7T
17.4 coNsrDERAçõESARESPEIToDEEFIcIÊNCIA . . . . . . . . t74
L8 PONTUAçÃO ENFRAQUECIDA L76
1 8 . 1 P O N T O E V Í R G U L A . . . . . , T 7 6
l 8 . 2 V Í R G U L A . . 1 7 7
18.3 FINAL DE LINHA . . T77
1 8 . 4 A S P A S . . . . . . . . . r 7 7
170
Conteúdo
19 A BIBLIOTECA DE MODELOS L79
19 .1 TNTRODUçÃO . . . . 17s
19 .2 OSMoDELOS . . . . . 180
lg .3REFERÊNCIAS . . . . 184
APÊNDICES
A A CHAMADA 9"4ì48 leo
4.1 A CHAMADA GENERICA Sil]YfS "SEM XABU,, . . .
A.2 A cHAMADA GENÉRIcA DE "oPçÃo"
4.3 EXEMPLoS DE SEQüENCIAS DE CHAMADA PARA MICROS MS-DOS
A.4 EXEMpLos oe snqtlÊNCHS DE cHAMADA PARA SISTEMAS IBM
CMS .
4.5 EXEMPLOS DE SEQTJENCIAS DE CHAMADA PARA SISTEMAS VAX
v M S . . . . . . 1 9 3
B oPÇoES DE coNTRoLE PELo DoLAR L94
8.1 coNTRoLES DE FoRMATAçÃo oa ENTRADA
8.2 coNTRoLES DE FoRMATAçÃo oa seba
8.3 coNTRoLES DAS A^ET.SRÊTqCIAS DE MAPAS
8.4 EXEMPLO
C O ENUNCIADO OPTION
D sÃ\/tglurNos
D.l UMA DEScntçÃo cERAL DE9AMEIMINoS
D.2 o FoRMATo DE uM ARQUrvo DE oPçoES g/Ms/MINos .
D.3 oeçÕes g"4Ms/MINos . .
D.4 REFEnÊlucns
E gAiltE/zooM
8.1 uue vtsÃo cERAL DE zooM
8.2 oeçons gAmslzooM ESPECIFICADAS EM sEU PRoGRAMA . . . . .
E.3 FORMATO DO ARQUIVO DE OeçOnS S"LMS/ZOOM . . .
8.4 oeçoes sAms/zooM . .
E.5 DrcAS eARA coNTRoLAR A RAMIFIcaçÃo E PoDA
F GRAMÁTICA
G GLOSSÁRIO
REFERÊNCIAS BIBLIOGRÁFICAS
INDICE
190
191
192
t94
195
L97
198
20L
204
204
210
21.2
230
23L
23r
240
24L
242
245
247
254
263
280
PREFÁCIOEDrçAO BRASTLETRAA
Tem sido um grande prazer para a J.M.Stern Pesquisa Operacional representar no Brasil
o Software 9"4MS (Sistema Genérico de Modelagem Algébrica). 9r4ME é hoje o sistema
de Programação Matemática mais utilizado em todo o mundo para modelagem em Pesquisa
Operacional. Varios fatores contribuem, a nosso ver, para tal sucesso:
1. A Linguagem $ÁMS possui uma sintaxe simples, intuitiva e poderosa, que permite
descrever com facilidade modelos complexos de Otirnização.
2. O Sistema 9,ÁME tem uma filosofia aberta, sendo compatível com uma grande va-
riedade de soluers, i.e., programas resolventes paÍa os problemas de Programação
Matemática gerados pelo modelo de Pesquisa Operacional.
3. A existência de uma ampla bibüoteca de modelos, já desenvolvidos e testados, facilita
o desenvolvimenüo de novos progriìm.ìs.
A tradução deste guia para o Português é parte do esforço da J.M.Stern-P.O. de dar
suporte para a crescente comunidade de usuários 9"4MS no Brasil. Esperamos também
que a tradução do guia contribua p.ua o ensino de Pesquisa Operacional e todas as suas
áreas de aplicação. Os interessados poderão obter uma versão estudantil de 9"4ME e alguns
solvers, juntamente com uma pequena biblioteca de exemplos. Para tanto, contacte-nos no
mdereço eletrônico abaixo. Somos gratos a vários alunos e professores da USP, UNICAMP
e PUC-CAMP, por suas sugestões no trabalho de revisão desta tradução.
A biblioteca que acompanha a versão estudantil inclui exemplos nas áreas de Admi-
nistração, Agro-Indústria, Comunicações, Desenvolvimento, Ecologia, Economia, Energia,
Engenharia, Estatística, Finanças, Matemática, Nutrição, Planejamento, e Política de Co-
mercio, Militar, de Tlansporte, Tlibutária, Urbana, etc.
J.M.Stern Pesquisa Operacional e
Equipamentos de Informática Ltda.
Rua Marcelino Ritter L, Pacaembu,
01246-090, São Paulo, Brasil.
Tel/Fax: (+55-1 1)-259-1217 3159-227 I
Bmail: stent@uso.net
I
It vll
PREFACIO
Este guia de estudos descreve os principais aspectos de 9"4ME (a sigla abrevia Gene-
ral Algebraic Modelling System) e ensina como usá-lo. gÁMS foi projetado para fazer a
construção e resolução de modelos matemáticos amplos e complexos de forma mais direta
para programadores, e mais inteligível para usuários de modelos em outras disciplinas, e.g.,
economisüas. Pelo fato de poder efetuar enunciados concisos de modelos em uma linguagem
que pode ser facilmente lida tanto por especialistas como por computadores, $ÁME pode
aumentar substancialmente a produtividade dos modelistas e expandir bastante a extensão
e o uso das aplicações de programação matemática em análise de políticas e tomadas de
decisão.
O ímpeto para o desenvolvimento de $ÁMS adveio das experiências frustrantes de um
grupo de modelagem ecouômica do Banco Mundial. Mesmo as técnicas disponíveis mais
evoluídas para desenvolver e resolver, e.g., modelos econômicos multi-setoriais em larga
escala ou ainda modelos amplos de simulação e otimização em setores tais como agricultura,
siderurgia e fertilizantes, possuiam sérios defeitos. Os programadores do grupo escreviam
programas em FORTRAN para preparar a solução de cada modelo; o trabalho era entediante,
exigindo muitos esforços, e os erros eram fáceis de fazer e difíceis de achar. Além disso,
os economistas envolvidos freqüentemente achavam as representações computadorizadas de
seus modelos complicadas, consumindo muito tempo para a compreensão e o trabalho; o
programador do modelo, às vezes, era a única pessoa que conhecia exatamente como o modelo
funcionava. Assim, a demissão de um programador fazia com que demorassem meses até que
seu sucessor dominasse o programa. Os modelos também eram difíceis e caros demais para
serem mudados, especialmente se a mudança contemplada não houvesse sido planejada ou
prevista. Nas apresentações em seminários, os modeladores tinham que defender as versões
existentes dos modelos, algumas vezes irracionalmente, porque o tempo e dinheiro envolvidos
em mudanças tornavam as modificações própostas proibitivas. Esses modelos não podiam ser
adaptados a novos ambientes, não apenas pelo conhecimento especializado de programação
necessário, mas também porque os formatos de dados e os métodos de solução não eram
portáveis. gÁMS foi projetado para mudar essa situação, fornecendo uma estrutura de
sistemas e uma linguagem de programação na qual concisão de expressões, generalidade e
portabilidade são passíveis de facil manutenção, além de usar o computador para rastrear
tantos detalhes de programação quantos possíveis.
Tendo em vista as origens do sistema, não se consititui em surpresa que as pessoas que
desenvolveram 9,4MS devam considerável gratidão ao Banco Mundial. A pesquisa e desen-
volvimento de 9ÁMS foram custeados pela Comissão de Pesquisa do Banco (RPO671-58 e
623-06), e foram executados sob a direção de Alexander Meeraus no Centro de Pesquisa e De-
senvolvimento (mais tarde Departamento) em Washigton D.C. Muitas pessoas participaram
do projeto e da implementação do sistema em tempos diversos; uma vez que a atribuição
exata de cada um dos mesmos é impossível, nós simplesmente os listamos em órdem al-
façtica: Masood Ahmad, John Ayler, Jan Bisschop, Pete Bleyendaal, Tony Brooke, Henrik
vlll
Prefácio tx
Dú1, Arne Drud,Paul van der Eijk, Richard Inman, David Kendrick, Mohammed Ketabchi,
yonatan Levi, Alex Meeraus, Soren Nielsen, Sethu Palaniappan, Helen Patton, Skip Paules,
peter Pellemans, Mohammed Pourghadiri, e Ardy Stoutjesdijk. Os auüores principais do
sofiuaresão: Tony Brooke, Paul van der Eijk e Alexander Meerhaus'
Sem o apoio, compreensão, e compromisso da administração senior, o projeto seria
impossível. Em órdem cronológica, J. Duloy, A. Stoutjesdijk, e G. Ingram, foram os dire-
torls responsáveis pelo departamento, e Hollis B. Chennery e Anne O' Kreuger, os vice-
presidentes. B. Balassa, B. King e D. Lal foram administradores de pesquisa' Nós todos
muito lhes devemos.
Também muito devemos a Allan Manne e Michael Saunders. Eles revisaram incansavel-
mente sucessivas versões deste liwo e contribuirÍrm para torná-lo mais claro, menos prolixo
e mais didático. Peter Bocock fez um excepcional trabalho de edição e de arte final, e
também recebemos comentários e sugestões de J. Coüas, P. Manouchehri-Adib, B' McCul-
lough, B. Paulin, S. Rogers, e R. Rosenthal-
Somos também gratos a Roy Marsten e Micüael Saunders por cederem seu tempo gra-
tuitamente enquanto ZOOM e MINOS estavam sendo modificados para rodar com 9ÁMS.
Também somos gratos àqueles que escreyeram partes deste livro: Rick Rosenthal, pelo
Capítulo 2, o tutorial; Philip Gill, Walter Murray, Bruce Murtagh, Michael Saunders e Mar-
g"r"tl Wright, pelo Apêndice D sobre 9/$I{S/MINOS; Roy Marsten e Jaya Singhal, pelo
Ápêndice Eìobre }AMSIZOOM. Um muito obrigado a todos os usuários de 9"4M8, que são
em demasiado número para serem mencionados individualmente, que fizeram comentários
sobre o softwore, nos mostrareÍn seus modelos, e relataram alguns erros.
Anthony Brooke
The Worlil Bank
David Kendrick
The Uniuersity of Teras
Alexander Meeraus
The World Bonk