Faculdade de Ciências - Câmpus de Bauru - Minicursoadriana/curiosidades/Introducao.pdf · 2012. 8. 16. · Os problemas de empacotamento podem ser encarados como o inverso dos problemas

Minicurso Introdução a Problemas de Otimização

Adriana Cristina Cherri

Departamento de Matemática - Faculdade de Ciências

Universidade Estadual Paulista - Campus de Bauru

[email protected]

Andréa Carla Gonçalves Vianna Departamento de Computação - Faculdade de Ciências

Universidade Estadual Paulista - Campus de Bauru

[email protected]

Bauru - SP

27 a 31 de agosto de 2012

mailto:[email protected]

XXIV Semana da Licenciatura em Matemática Bauru – SP, 27-31 de agosto de 2012

2

1. Introdução

A área que estuda problemas de otimização é chamada de Programação Matemática . Esta

denominação identifica uma ampla classe de problemas.

Otimizar significa encontrar a melhor maneira de fazer algo, dada uma medida do que é ser

“melhor”. Sempre que encurtamos um caminho para ganhar tempo, economizamos para comprar

algo, tomamos decisão com base em investimentos, estamos interessados na melhor forma de

aplicarmos nossos recursos. Resolver um problema de otimização, significa procurar a solução de

um problema de forma a se maximizar algo ou a minimizar algo.

Uma infinidade de problemas do cotidiano podem ser classificados como problemas de

Otimização Combinatória. Alguns deles são:

Corte de Materiais

Uma fábrica de peças de mármore vende peças, sob encomenda, que são produzidas

cortando-se placas grandes em pedaços menores. Uma placa grande pode ser cortada de

diversas maneiras e sempre haverá um desperdício de mármore oriundo dos pedaços que

sobram após o corte das peças desejadas. Esses pedaços não podem ser aproveitados para

produzir peças úteis. O objetivo aqui é descobrir a melhor maneira de cortar as placas de

modo que o desperdício seja minimizado. Este é um problema de corte em duas dimensões

(corte bidimensional) que também se aplica a vidro, metal, madeira etc. Há problemas de

corte em uma dimensão (por exemplo, rolos de papel) e em três dimensões (por exemplo,

corte de blocos de espuma para produção de colchões).

Empacotamento

Os problemas de empacotamento podem ser encarados como o inverso dos problemas de

corte. Aqui a ideia é arrumar a melhor maneira de agrupar um conjunto de itens de modo

que o espaço total necessário para guardá-los seja minimizado. Em certos casos, o espaço

disponível para o armazenamento é predeterminado e o objetivo é guardar o maior número

de itens possível. Por exemplo, uma companhia de mudanças deseja encontrar a melhor

maneira arrumar os móveis dentro dos seus caminhões de modo a realizar a mudança com

um número mínimo de viagens.

Designação de mão-de-obra

Dado um conjunto de tarefas a realizar e um conjunto de funcionários, um empresário deseja

encontrar a melhor maneira de alocar seus funcionários às tarefas de forma que todas as

tarefas sejam cumpridas e os gastos com mão-de-obra sejam minimizados. Além disso, há

restrições trabalhistas e restrições operacionais da empresa que afetam a forma com que a

alocação pode ser feita. Os custos podem estar relacionados com a quantidade de operários

envolvidos e/ou com o número de horas-extra que o empresário terá de pagar. Por exemplo,

numa companhia aérea, é preciso decidir quais viagens serão destinadas a quais pilotos e

ainda obedecer a regras do tipo: um piloto não pode trabalhar mais de 8 horas seguidas sem

descansar; a cada três dias seguidos de trabalho todo piloto deve ter um dia de descanso etc.

Escalonamento de tarefas

Em certas fábricas, um produto final é criado a partir da execução de pequenas tarefas. Essas

tarefas possuem regras de precedência entre si e particularidades que exigem um ou outro

tipo de máquina para sua execução. Com isso, dado um conjunto de itens a produzir, deseja-

se descobrir, para cada máquina da fábrica, a ordem em que as tarefas devem ser

processadas de forma a minimizar o tempo de produção.

Localização de Facilidades

Dado um conjunto de clientes que precisam ser atendidos e um conjunto de possíveis locais

para instalação de facilidades, deseja-se determinar quais os melhores locais para instalação

das facilidades de forma que todos os clientes sejam atendidos a um custo mínimo. Por

exemplo, os clientes podem ser um conjunto de casas e as facilidades a instalar podem ser


3

postos de pronto-socorro. O custo pode estar relacionado com a distância das casas ao

pronto-socorro mais próximo.

Distribuição de Bens de Consumo

Dado um conjunto de fregueses que precisam receber mercadorias, a fábrica tem que decidir

a quantidade de carga a ser colocada em cada caminhão e quais caminhões irão atender

quais clientes. Além disso, é preciso otimizar as rotas dos veículos e, em alguns casos, levar

em consideração a eventual necessidade de reabastecimento da carga por parte de alguns

caminhões. Por exemplo, os clientes podem ser bares e a fábrica pode ser uma fábrica de

bebidas.

Projeto de Circuitos Integrados

Antes que um circuito integrado seja impresso na placa, é preciso decidir em que lugares

serão colocados os chips e por onde passarão as ligações entre os componentes. O objetivo é

minimizar os gastos com as ligações entre componentes e também minimizar as distâncias

entre componentes que se comunicam com maior frequência.

Planejamento de Produção

Dado um horizonte de demanda por produtos, um fabricante de determinado item de

consumo precisa decidir quanto deve produzir por mês de forma a atender toda a demanda e

ainda minimizar os custos. Existe um limite no poder de estocagem e um preço a ser pago

por quantidade de produto estocada. Além disso, os produtos podem ter data de validade e

atrasos na entrega de mercadoria podem ser tolerados (gerando custo adicional) ou não.

Para encontrar a solução para estes e outros problemas modelos matemáticos devem ser

elaborados para que possam ser resolvidos com o auxílio de computadores.

O objetivo principal deste texto consiste em apresentar uma visão geral de problemas de

otimização linear. São apresentados alguns problemas clássicos com seus respectivos modelos

matemáticos e métodos solução.

2. Modelagem de problemas

As seguintes etapas são utilizadas para a elaboração de um modelo matemático:


4

Não há um algoritmo para se escrever um modelo matemático. Entretanto, algumas etapas

podem auxiliar na sua construção:

Passo fundamental: ouvir aquele que lida com o problema “real” e entender como obtém

suas soluções;

Passo 1: descobrir o que deve ser determinado: variáveis do problema;

Passo 2: descobrir o que é disponível: dados do problema;

Passo 3: reproduzir os caminhos que levam a uma solução: equações/inequações.

Um modelo matemático apresenta a seguinte estrutura:

nnxcxcxcxfMinimizar

2211)( função objetivo

Sujeito a:

mnmnmm

nn

nn

bxaxaxa

bxaxaxa

bxaxaxa

2211

22222121

11212111

restrições ( ou )

x1 0, x2 0, xn 0. condição das variáveis

),...,,(21 n

xxx que satisfaz todas as restrições é chamado de solução factível.

A função objetivo indica se uma decisão é preferível a outras. As restrições limitam as

decisões que devem ser tomadas e a condição das variáveis definem o tipo de variável do problema.

3. Problemas de otimização linear

Nesta seção, apresentamos alguns problemas clássicos de otimização linear com seus

respectivos modelo matemáticos.

Problema da Mistura Uma mistura é produzida a partir de ingredientes que possuem os componentes desejados no

novo produto, satisfazendo determinadas especificações. Os componentes e os custos de cada

ingrediente são conhecidos.

OBJETIVO: determinar as quantidades de cada ingrediente que será utilizada para obter uma

mistura com a composição especificada e com o menor custo possível.

Dados do problema:

n: número de ingredientes;

m: número de componentes;

aij: fração do componente i no ingrediente j;

bi: fração do componente i na mistura;

cj: custo unitário do ingrediente j.

Variáveis de decisão: xj: quantidade do ingrediente j a ser usada em uma unidade da mistura.


5

Formulação matemática:

minimizar f (x1, x2, . . . , xn) = c1x1 + c2x2 + . . . + cnxn

Sujeito a:

a11x1 + a12x2 + . . . + a1nxn b1

a21x1 + a22x2 + . . . + a2nxn b2

...

am1x1 + am2x2 + . . . + amnxn bm

x1 + x2 + . . . + xn = 1

x1 0, x2 0,..., xn 0

Exemplo: Mistura de ração Uma agroindústria deve produzir um tipo de ração para um determinado animal. A ração é

produzida pela mistura de farinhas de 3 ingredientes básicos: farinhas de osso, de soja e de peixe.

Cada um dos ingredientes contém diferentes quantidades de dois nutrientes necessários para uma

dieta nutricional balanceada: proteína e cálcio. O nutricionista especifica as necessidades mínimas

desses nutrientes em 1 kg de ração. Cada ingrediente é adquirido no mercado com custo unitário. Os

dados são apresentados na tabela:

Ingredientes

Nutrientes Osso Soja Peixe Ração

Proteína 0.2 0.5 0.4 0.3

Cálcio 0.6 0.4 0.4 0.5

Custos ($/kg) 0.56 0.81 0.46

Objetivo: Determinar em que quantidades os ingredientes devem ser misturados de modo a

produzir 1 kg de ração que satisfaça às restrições nutricionais com o mínimo custo.

Variáveis de decisão (1 kg de mistura)

xosso : quantidade de farinha de osso

xsoja : quantidade de farinha de soja

xpeixe : quantidade de farinha de peixe

Custo da mistura: f(xosso, xsoja, xpeixe) = 0.56 xosso + 0.81 xsoja + 0.46 xpeixe

Quantidade de proteína (1 kg de mistura): 0.2xosso + 0.5 xsoja + 0.4 xpeixe 0.3

Quantidade de cálcio (1 kg de mistura): 0.6xosso + 0.4 xsoja + 0.4 xpeixe 0.5

Soma dos ingredientes: 1 kg de mistura: xosso + xsoja + xpeixe = 1

Formulação matemática:

minimizar f(xosso, xsoja, xpeixe) = 0.56 xosso + 0.81 xsoja + 0.46 xpeixe

Sujeito a:

0.2 xosso + 0.5 xsoja + 0.4 xpeixe 0.3

0.6 xosso + 0.4 xsoja + 0.4 xpeixe 0.5

xosso + xsoja + xpeixe = 1

xosso 0; xsoja 0; xpeixe 0


6

Problemas de Transporte O problema consiste em transportar produtos dos centros de produção (origens) aos

mercados consumidores (destinos);

As quantidades disponíveis em cada centro de produção e as quantidades demandadas em

cada mercado consumidor são conhecidas. O transporte deve ser efetuado respeitando-se as

limitações de oferta em cada origem e atendendo à demanda de cada destino.

OBJETIVO: transportar o produto dos centros de produção aos mercados consumidores de modo

que o custo total de transporte seja o menor possível.

Dados: m: número de origens;

n: número de destinos;

ai: oferta do produto na origem i;

bj: demanda do produto no destino j;

cij: custo de transportar uma unidade do

item da origem i ao destino j.

Variáveis de decisão: xij quantidade de itens transportada da origem i para o destino j.

As quantidades transportadas não podem ser negativas!

Logo, restrições xij 0, para i = 1, ..., m e j = 1, ..., n, fazem parte do modelo.

cij xij é o custo para se realizar o transporte da origem i para o destino j.

O custo total de transporte, que deve ser minimizado, é dado por:

Solução ótima: xosso

= 0.5; xsoja

= 0; xpeixe

= 0.5

Função objetivo: f(0.5, 0, 0.5) = 0.51

.,...,1 ;,...,1 ,inteiro ,0

,...,1 ,

,...,1 ,

:a Sujeito

),...,,(min

1

1

1 1

1211

njmix

njbx

miax

xcxxxf

ij

m

i

jij

n

j

iij

m

i

n

j

ijijmn


7

Exemplo: Transporte de bebidas Considere uma companhia distribuidora de bebidas que possui:

• Dois centros de produção (m = 2): Araraquara e São José dos Campos;

• Três mercados consumidores (n = 3): São Paulo, Belo Horizonte e Rio de Janeiro.

cij custo unitário do transporte de uma unidade de produto de cada centro de produção i a cada

mercado consumidor j.

Variáveis de decisão:

xij quantidade do produto a ser enviada do centro i ao mercado j

(uma unidade pode ser um engradado contendo dezenas de garrafas, ou um palete com

centenas de garrafas)

Os custos de custos de transporte, demandas e capacidades de produção são dados abaixo:

Formulação matemática

minimizar f(x11, ..., x23) = 4x11 + 8x12 + 8x13 + 2x21 + 8x22 + 5x23

Sujeito a:

x11 + x12 + x13 800

x21 + x22 + x23 1000

x11 + x21 = 500

x12 + x22 = 400

x13 + x23 = 900

x11 0; x12 0; x13 0; x21 0; x22 0; x23 0

Problema de Designação (Caso particular do problema de transporte) Suponha que n tarefas precisam ser atribuídas a n pessoas. Cada pessoa deve executar uma

única tarefa e todas as tarefas devem ser executadas. Cada pessoa i tem um interesse em efetuar

cada tarefa j, dado por pij. Queremos fazer a alocação de modo que a soma dos interesses seja

maximizada.

O Problema de Designação envolve a determinação de n! possíveis soluções.

Solução ótima: x11 = 500; x12 = 300; x13 = 0;

x21 = 0; x22 = 100; x23 = 900.

Função objetivo: f(500, 300, 0, 0, 100, 900) = 6900


8

Exemplo:

para um problema com 5 trabalhadores e 5 tarefas o número de soluções possíveis é igual a

5! = 120.

para um problema com 10 trabalhadores e 10 tarefas o número de soluções possíveis é igual

a 10! = 3.628.800.

Variáveis de decisão

xij = 1, se o individuo i for designado para a realização da tarefa j.

xij = 0, caso contrário.

Problemas de Corte O problema consiste em produzir itens (peças pequenas), a partir do corte de um objeto

(peça grande).

OBJETIVOS: minimizar a perda de material dos objetos cortados, minimizar a quantidade de

objetos cortados, minimizar o custo de cortar os objetos, maximizar o lucro, entre outros.

11 12

1 1

1

1

max ( , ,..., )

Sujeito a:

1, 1,...,

1, 1,...,

{0, 1}, 1,..., ; 1,..., .

n n

nn ij ij

i j

n

ij

j

n

ij

i

ij

f x x x p x

x i n

x j n

x i n j n

cada trabalhador é designado a uma só tarefa

cada tarefa é executada apenas por um trabalhador

Dados: L : tamanho do objeto;

m : número de tipos de itens;

li : comprimento de um tipo de item i;

bi : quantidade de um determinado tipo de item i;

aj : vetor associado a um padrão de corte.

aj = (a1j, a2j, ..., amj)

quantidade de peças do tipo 1 no padrão de corte j

Variáveis de decisão: xj : número de barras cortadas conforme o padrão de corte j

Padrão de corte:

Problema!!! Como gerar um padrão de corte?

Quantas vezes devemos cortar cada padrão?

Um vetor = (1, 2, ..., m)T representa um padrão de corte se e somente se o seguinte

sistema é satisfeito:

l11 + l22 + ... + lmm L

1 0, 2 0, ..., m 0 e inteiros

Como escrever a formulação que minimiza o número de barras utilizadas, dado que sabemos

todos os padrões de corte possíveis ?

O problema de corte pode ser formulado como:

Exemplo: Problema de corte Uma indústria de papel produz bobinas jumbo de L = 400 cm de largura. Os jumbos devem

ser cortados em bobinas menores (itens) nas larguras e quantidades apresentadas na tabela conforme

a solicitação dos diversos clientes:

.,...,1 ,0

...),...,,(min

2

1

2

1

2

2

22

12

1

1

21

11

2121

njx

b

b

b

x

a

a

a

x

a

a

a

x

a

a

a

xxxxxxf

j

m

n

mn

n

n

mm

nn


10

Possíveis padrões de corte:

Padrão de corte 1: a1 = (10 0 0 0)

Padrão de corte 2: a2 = ( 1 8 0 0)





Problemas de Planejamento da Produção O problema de planejamento e programação da produção de produtos pode ser o mais

variado possível

Mix de Produção (fabricação de diversos produtos)

Seleção de processos (vários produtos com vários processos alternativos)

Dimensionamento de lotes (diversos produtos para variados clientes com diferentes datas

de entrega)

OBJETIVO: Minimizar os custos de produção dos diferentes produtos em diversas situações

Mix de produção (planejamento estocástico) O problema consiste em decidir quais produtos e quanto fabricar de cada produto em um

período. A capacidade limitada de produção (maquinas, recursos humanos, capital, armazenagem,

etc) e os diversos produtos que a empresa pode fabricar são conhecidos. O objetivo consiste em

determinar quais produtos e quanto deve ser fabricado de cada produto de modo a maximizar o

lucro da empresa.

Dados: Ci : capacidade do recurso i disponível no período;

aij : quantidade do recurso i utilizado para a produção de uma unidade do produto j;

lj : lucro da empresa para produzir o item j;

dj : produção mínima do produto j que deve ser realizada no período;

vj : produção máxima do produto j que deve ser realizada no período;

.,...,1 ,0

18

42

20

12

3

4

0

0

0

4

4

0

6

0

0

1

0

7

0

0

0

0

8

1

0

0

0

10

...),...,,(min

654321

2121

njx

xxxxxx

xxxxxxf

j

nn

Solução factível: (x1, x2, x3, x4, x5, x6) = (1 1 2 1 3 4)

Função objetivo: 1 + 1 + 2 + 1 + 3 + 4 = 12


11

Variáveis de decisão: xj : quantidade de cada produto j a ser produzida em um período do planejamento

Objetivo – Maximizar o lucro da empresa

F(x) = maximizar f(x1, ..., xn) = l1x1 + l2x2 + ... + lnxn

Modelo Matemático

Maximizar z = l1x1 + l2x2 + ... + lnxn

Sujeito a:

ai1x1 + ai2x2 + ... + ainxn ≤ Ci i = 1,..., m

dj ≤ xj ≤ vj j = 1,..., n

Exemplo Um fabricante de geladeiras precisa decidir quais modelos deve produzir em uma nova

fábrica recentemente instalada. O departamento de marketing verificou que no próximo mês podem

ser vendidas no máximo1.500 unidades do modelo luxo e 6.000 unidades no modelo básico.

A empresa dispõe de uma força de trabalho de 25.000 homens-hora por mês. Cada modelo de

luxo requer 10 homens-hora e cada modelo básico requer 8 homens-hora para ser montado. Além

disso, uma mesma linha de montagem é compartilhada pelos dois modelos. Considere que a

capacidade de produção desta linha seja de 4.500 geladeiras por mês.

O lucro unitário do modelo de luxo é de R$ 100,00 e do modelo básico é de R$ 50,00. Deseja-se

determinar quanto produzir de cada modelo de modo a maximizar o lucro da empresa.

Variável de decisão xj : quantidade de geladeiras do tipo j, j = luxo, básico

Maximizar f(xluxo, xbásico) = 100xluxo + 50xbásico

Sujeito a:

10xluxo + 8xbásico ≤ 25.000

xluxo + xbásico ≤ 4.500

0 ≤ xluxo ≤ 1.500 e 0 ≤ xbásico ≤ 6.000

A visualização de soluções de um problema matemático, quando possível e mesmo que

limitada a um desenho no R2, pode ser bastante útil para melhorar nossa intuição sobre o problema

em estudo. Na Seção 4 apresentamos a resolução gráfica de um problema.

4. Resolução Gráfica

Como vimos, resolver um problema de otimização linear consiste em encontrar uma solução

ótima para o problema. Por conveniência, consideramos o problema de otimização linear com duas

variáveis e na forma de desigualdade.


12

Exemplo 4.1:

maximizar f(x1, x2) = x1 + 2x2

Sujeito a:

1 2

1

2

1 2

4

2

3

0, 0

x x

x

x

x x

Região factível S

Desenhando uma região factível

As soluções factíveis de um problema sempre devem satisfazer todas as restrições do

problema. Considerando o Exemplo 4.1, representamos inicialmente os pontos no plano (x1, x2) que

satisfazem as condições de não-negatividade, isto é, primeiro quadrante do plano.

Para representar os pontos no plano (x1, x2) que também satisfazem a restrição x1 + x2 ≤ 4,

identificamos os pontos que satisfazem a igualdade x1 + x2 = 4. Esta equação é uma reta no plano,

sendo seus coeficientes, o vetor (1, 1)T, perpendicular à reta. Em seguida, identificamos os pontos

que satisfazem x1 + x2 < 4. Para identificar este conjunto, observe que este vetor (1, 1)T aponta no

sentido em que x1 + x2 cresce. Portanto, os pontos no plano a partir da reta opostos àqueles para o

qual o vetor (1, 1)T aponta são tais que x1 + x2 < 4. A reunião dos pontos tais que x1 + x2 = 4 e x1 +

x2 < 4 juntamente com as restrições de não-negatividade é o que queremos considerar. A Figura 4.1

ilustra esta representação.

Figura 4.1: Região definida por x1 + x2 ≤ 4, x1 ≥ 0, x2 ≥ 0.

De modo semelhante, desenhamos as regiões dos pontos que satisfazem x1 ≤ 2 e x2 ≤ 3. A

intersecção de todas as regiões define a região factível representada na Figura 4.2.

Figura 4.2: Região factível S.


13

Determinando a solução ótima x*

A função objetivo f(x1, x2) = x1 + 2x2, definida no conjunto S, pode assumir infinitos valores.

Por exemplo, na solução factível ' '

1 2' ( ) (0,0)T Tx x x a função objetivo vale f ’ = f(x’) = 0 e todos

os pontos do plano (x1, x2) que atribuem este mesmo valor à função objetivo estão na reta

x1 + 2x2 = 0. Esse conjunto de pontos é chamado de curva de nível e esta representado na Figura 4.3

pela reta tracejada f ’ = 0.

Ao definir a região factível, o vetor dos coeficientes (1, 2)T (vetor gradiente) é perpendicular

à reta x1 + 2x2 = 0 (uma curva de nível) e aponta no sentido em que a função cresce. Com isso,

podemos visualizar na Figura 4.3 que qualquer ponto de S atribui valor maior que zero à função f.

Como queremos maximizar f, podemos concluir, graficamente, que a solução factível ' (0,0)Tx

não é uma solução ótima.

Figura 4.3: Determinando a solução ótima x* (Problema de maximização).

Quando analisamos a solução factível '' (2,0)Tx , a função objetivo f ’’ = 2. Como o vetor

gradiente não se altera, essa reta é paralela à f ’ = 0. Continuando o procedimento de identificar

pontos que atribuem valores maiores à função objetivo, chegamos a um extremo * *

1 2* ( ) (1,3)T Tx x x , para o qual f(x*) = 7. A curva de nível x1 + 2x2 = 7 nos permite observar

que todos os pontos de S atribuem valores menores que 7 à função objetivo. Portanto, a solução x*

que satisfaz todas as restrições simultaneamente e maximiza f(x) existe e é única:

1

2

1*

3

xx

x

No Exemplo 4.1 desejamos maximizar f(x), desta forma, procuramos pontos factíveis que

estivessem do lado apontado pelo vetor gradiente, partindo da curva de nível f(x)=f '. Entretanto, se

o objetivo fosse minimizar f(x), aplicamos o mesmo procedimento, porém, buscando pontos no

sentido contrário ao do vetor gradiente.

A solução ótima da Figura 4.3 é uma solução factível muito especial, chamada vértice ou

ponto extremo. Na região factível ilustrada, é possível notar que os vértices são determinados pela

intersecção de pelo menos duas retas que definem a fronteira da região factível (observe que xi = 0 é

uma equação de reta). Assim, temos que os vértices são soluções de sistemas de equações lineares.

Observe que se o vetor gradiente da função objetivo for modificado, outro vértice pode ser

uma solução ótima.

Propriedade 4.1: Se um problema de otimização linear tem uma solução ótima, então existe um

vértice ótimo.


14

No Exemplo 4.2, a região factível do problema é limitada e apresenta uma única solução

ótima. Entretanto, várias outras possibilidades podem ocorrer: não existência de solução ótima,

solução ótima degenerada, infinitas soluções ótimas, entre outras. A resolução gráfica de problema

de otimização linear com dimensões maiores que dois é igualmente possível.

Nesta seção, observamos que uma solução ótima, se houver, pode ser pesquisada entre os

vértices. Assim, se formos capazes de sair de um vértice para outro melhor, podemos repetir isso

um número finito de vezes até encontrar um vértice ótimo. É assim que trabalha o método simplex,

um dos mais utilizados métodos para a resolução de problemas de otimização linear. Uma breve

revisão deste método é apresentada na próxima seção.

5. Técnicas Utilizadas Problemas de Otimização Combinatória precisam ser transformados em modelos concretos

para que possam ser resolvidos com o auxílio de computadores. Como já vimos, é preciso aplicar

métodos mais inteligentes do que a simples enumeração de todas as possíveis soluções. Atualmente,

temos utilizado as seguintes técnicas na resolução de diversos problemas de otimização:

Programação Linear e Programação Inteira

Essas técnicas já são bastante conhecidas no campo da Otimização, tendo suas origens na

década de 40. A Programação Linear consiste em expressar um problema em termos de

variáveis contínuas e um conjunto de restrições lineares sobre essas variáveis otimizando

uma função linear. Dada uma função objetivo que descreve basicamente como é calculado o

"custo" a ser minimizado, aplica-se um algoritmo (normalmente o Simplex) que resolve o

problema de forma eficiente. Na vida real, entretanto, é muito comum que as variáveis

precisem assumir valores inteiros e não contínuos. Por exemplo, para resolver um problema

em que se precisa decidir quantos empregados serão atribuídos a uma determinada tarefa,

gostaríamos de obter como resposta um número inteiro e não 5.78. O que são 5.78

empregados? 5 ou 6? Por incrível que pareça, quando se impõe a restrição de que as

variáveis assumam valores inteiros o problema pode ficar muito mais difícil. E a ideia

natural de simplesmente arredondar os valores nem sempre traz bons resultados. É aí que

entra a Programação Inteira. Ela se baseia fundamentalmente em relaxar, de alguma forma,

o problema original e resolvê-lo aos poucos até que se consiga encontrar a melhor solução

possível, com o requerimento adicional de que a resposta seja dada em função de números

inteiros.

Programação por Restrições

Técnica mais recente que começou a ganhar força na década de 80. Teve suas origens no

campo da Inteligência Artificial, mais especificamente no ramo da Programação Lógica. Em

termos simplificados, consiste em um mecanismo de inferência lógica auxiliado por um

resolvedor de restrições que são impostas sobre as variáveis do problema em questão. A

modelagem dos problemas é facilitada por se tratar de uma linguagem declarativa baseada

em implicações lógicas. Restrições complexas podem ser escritas de forma clara e concisa.

Tem obtido bastante sucesso em problemas de porte industrial.

Algoritmos Híbridos

Há problemas em que nem Programação (Linear) Inteira nem Programação por Restrições

conseguem obter êxito. Em certos casos, as fraquezas inerentes a cada uma dessas duas

técnicas colaboram para que seja muito difícil encontrar uma solução. Desse modo, torna-se

necessário que se combinem os pontos fortes de cada uma, criando o que se chamam

Algoritmos Híbridos. Tratam-se de algoritmos cooperativos onde Programação Inteira e

Programação por Restrições ajudam-se mutuamente. Vários tipos de integrações são

possíveis, dando origem a algoritmos bastante interessantes e eficientes.


15

Métodos Heurísticos

Nem sempre é possível encontrar a melhor solução de um problema de otimização em

tempo razoável. Nesses casos, uma solução relativamente boa pode já ser suficiente para a

aplicação que se tem em mãos. Os Métodos Heurísticos são algoritmos que não garantem

encontrar a solução ótima de um problema, mas são capazes de retornar uma solução de

qualidade em um tempo adequado para as necessidades da aplicação.

Referência Bibliográfica

[1] Arenales, M., Armentano, V., Morabito, R., Yanasse, H., (2007). Pesquisa Operacional. Rio de

Janeiro: Elsevier. Editora Campus, 523p.

[2] http://www.ic.unicamp.br/~cid/intro-comb-opt.html

http://www.ic.unicamp.br/~cid/intro-comb-opt.html

Documents

Faculdade de Ciências - Câmpus de Bauru - Minicursoadriana/curiosidades/Introducao.pdf · 2012. 8. 16. · Os problemas de empacotamento podem ser encarados como o inverso dos problemas