Notas de aula de Pesquisa Operacional Aplicada ` Minerao. a ca c Universidade Federal de Ouro Preto.

PESQUISA OPERACIONAL` APLICADA A

MINERACAO

Marcone Jamilson Freitas Souza Alexandre Xavier Martins Tatiana Alves Costa Frederico Augusto C. Guimares a Jos Maria do Carmo Bento Alves e

Departamento de Computao ca Instituto de Cincias Exatas e Biolgicas e o Universidade Federal de Ouro Preto

2

Pesquisa Operacional Aplicada ` Minerao a ca

Sumrio aI OTIMIZADOR LINGO 55 5 6 6 7 7 7 7 8 8 8 8 9 9 9 10 10 10 11 11 11 12 12 13 15 15 17 17 18 19 19 20 20 20 22

1 Introduo ca 2 Restries Lineares co 3 Introduo ` Linguagem de Modelagem do LINGO ca a 3.1 Funao Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . c 3.2 Restries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . co 4 Adicionando Caracter sticas 4.1 Rotulando as Restries . co 4.2 Intitulando o Modelo . . . 4.3 Inserindo comentrios . . . a ` Linguagem de Modelagem a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5 Operadores e Funes do LINGO co 5.1 Operadores Aritmticos . . . . . . e 5.2 Operadores Lgicos . . . . . . . . . o 5.3 Operadores Relacionais . . . . . . . 5.4 N de prioridade dos operadores vel 5.5 Funoes matemticas . . . . . . . . c a 5.6 Funoes de probabilidade . . . . . . c 5.7 Funoes de dom c nio . . . . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

6 O modelo LINGO do Problema de Transporte 7 SETS (Conjuntos) 7.1 Porque SETS? . . . . . . . . . . . . . 7.2 O que so SETS? . . . . . . . . . . . a 7.3 Seo SETS . . . . . . . . . . . . . . ca 7.4 Denindo Conjuntos Primitivos . . . 7.5 Denindo conjuntos derivados . . . . 7.6 Funoes sobre conjuntos . . . . . . . c 7.7 Funoes de manipulao de conjuntos c ca 8 Seo DATA ca 8.1 Introduo ` seo DATA . . . . ca a ca 8.2 Parmetros . . . . . . . . . . . . a 8.3 Anlise E se. . . . . . . . . . . . a 8.4 Inicializando um atributo com um 8.5 Omitindo valores na seo DATA ca

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . simples valor . . . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

9 Utilizando Arquivos-texto 9.1 Importando dados de um arquivo texto com @FILE . . . . . . . . . . . . . . . . . 9.2 Exportando dados para um arquivo com @TEXT . . . . . . . . . . . . . . . . . .

Modelagem de PPLs 10 Utilizando planilhas do EXCEL 10.1 Funao @OLE . . . . . . . . . . . . . . . . . c 10.2 Importando dados do EXCEL com @OLE . 10.3 Denindo nomes no EXCEL . . . . . . . . . 10.4 Excluindo um nome denido no EXCEL . . 10.5 Exportando dados para EXCEL com @OLE 10.6 Algumas consideraes sobre @OLE . . . . . co 11 Embutindo planilhas do EXCEL no LINGO 12 Embutindo Modelos LINGO no EXCEL 13 Utilizando links OLE automatizados no EXCEL 13.1 Comando SET . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 23 23 23 25 27 27 29 30 32 34 38

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

II

Modelagem de Problemas de Programao Linear ca

3939 39 41 41 45 47 47 51 51 54 54 57 60 60 62 64 64 65 65 67 69 72 72

Carteira de Investimentos Problema 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Mistura de Minrios com Custos e Problema 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Problema 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Mistura de Minrios com Metas e Problema 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Problema das Usinas Problema 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Planejamento da Produo ca Problema 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Problema 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Alocao de Pessoal ca Problema 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Problema 9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Formao de Ligas ca Problema 10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Corte de Estoque Unidimensional (Cutting Stock Problem) Problema 11 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Problema 12 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Problema 13 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Corte de Estoque Bidimensional Problema 14 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

Pesquisa Operacional Aplicada ` Minerao a ca 73 73 75 75 77 77 79 79 81 81 82 82 84 84

Mochila 0-1 Problema 15 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Mochila 0-1 M ltipla u Problema 16 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Mochila Inteira Problema 17 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Mochila Inteira M ltipla u Problema 18 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Localizao ca Problema 19 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Caixeiro Viajante Problema 20 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Roteamento de Ve culos Problema 21 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

Parte I

OTIMIZADOR LINGO1 Introduo caO LINGO uma ferramenta computacional para modelagem e resoluo de problemas lineares e ca e no-lineares de otimizao. O processo de otimizao consiste em tentar encontrar a melhor a ca ca soluo poss para um dado problema, usando tcnicas de programao matemtica, de forma ca vel e ca a a atingir o maior benef cio/lucro ou gerar o menor custo/desperd cio. Problemas de otimizao so ca a classicados como lineares ou no-lineares, dependendo se os relacionamentos entre as variveis a a do problema so lineares ou no, respectivamente. a a

2

Restries Lineares co

Se todos os termos das variveis so de primeira ordem, a restrio dita linear. Isto signica a a ca e que a restrio no contm uma varivel quadrtica, cbica, ou elevada a qualquer potncia, um ca a e a a u e termo dividido por uma varivel, ou uma varivel multiplicada por outra. Alm disso, deve existir a a e proporcionalidade, ou seja, para cada unidade adicionada ou retirada de uma varivel, o valor da a restrio aumentar ou reduzir em uma quantidade xada. ca a a Frmulas lineares so relaes que podem ser gracamente representadas por uma linha reta. o a co Sua forma bsica pode ser escrita como: a y = mx + b onde m e b so constantes. a Suponha, por exemplo, que um quilo de tomate custe R$ 1,50. A expresso ou funo usada a ca para calcular o custo (c) em termos da quantidade de tomate comprada (t) : e c = 1.5 t Como esperado, o grco da funo de custo uma linha reta: a ca e

Expresses lineares podem ter mltiplos valores, como por exemplo, se forem acrescentados ` o u a funo acima o custo de batatas (b) a R$ 0,75 e mas (m) a R$ 1,25, ter ca ca amos: c = 1.5 t + 0.75 b + 1.25 m

6 Esta nova expresso de custo formada continua sendo linear. Pode-se dizer que ela e a soma a de trs expresses lineares simples. e o Como os modelos lineares podem ser resolvidos de forma mais rpida em ordens de magnitude a e com maior preciso do que os modelos no-lineares, prefer que os modelos sejam formulados a a e vel usando expresses lineares sempre que poss o vel. Para problemas representados por modelos lineares, quando completamente resolvidos pelo LINGO (sem serem interrompidos), tem-se a garantia que o valor da funo objetivo encontrado ca timo, ou seja, o melhor valor poss para o problema em questo. Tal garantia no ocorre eo e vel a a no caso de modelos no-lineares, j que os mesmos podem car presos em timos locais, como a a o mostra a gura abaixo, que ilustra o caso de uma funo objetivo no-linear. ca a

Algumas expresses no-lineares podem ser facilmente convertidas em lineares. Considere a o a restrio abaixo: ca x/y = 10; Da forma como est escrita, essa restrio no-linear porque x est sendo dividido por y. a ca e a a Simplesmente multiplicando ambos os lados por y, temos a restrio linear equivalente: ca x = 10 y;

33.1

Introduo ` Linguagem de Modelagem do LINGO ca aFuno Objetivo ca

A linguagem de modelagem do LINGO permite representar a funo objetivo de forma bastante ca simples e intuitiva. Para exemplicar, considere dois conjuntos, fabricas e armazens, e uma matriz rotas de elementos (i, j), com i fabricas e j armazens. As funes objetivo a seguir: co minimizarifabricas jarmazens

custoij qtdEnviadaij lucroij qtdEnviadaij

maximizarif abricas jarmazens

so assim representadas no LINGO: a MIN = @SUM(fabricas(i): @SUM(armazens(j): custo(i,j)*qtdEnviada(i,j))); MAX = @SUM(fabricas(i): @SUM(armazens(j): lucro(i,j)*qtdEnviada(i,j))); ou, equivalentemente: MIN = @SUM(rotas(i,j): custo(i,j)*qtdEnviada (i,j)); MAX = @SUM(rotas(i,j): lucro(i,j)*qtdEnviada(i,j));

7

3.2

Restries co

Assim como na funo objetivo, podemos usar a linguagem de modelagem do LINGO para repreca sentar as restries do problema de forma simples e direta. co Para as seguintes restries em notao matemtica: co ca a (qtdEnviadaij ) capacidadeijarmazens

i fabricas j armazens

(qtdEnviadaij ) = demandajifabricas

temos a seguinte representao no LINGO: ca @FOR(fabricas(i): @SUM(armazens(j): qtdEnviada(i,j))