Otimização 2011

MSc. Eng Rodrigo Mota Amarante

1o. Semestre de 2011

PNV-2300: Introdução à Engenharia Naval

Otimização

A otimização refere-se ao estudo de

problemas nos quais o objetivo é

maximizar ou minimizar uma função,

sujeita a restrições, através da escolha

sistemática dos valores de variáveis reais

ou inteiras.

Otimizar é o mesmo que melhorar. No

ideal, melhorar necessariamente até o

máximo.

Otimização: Conceitos

Objetivos

• Objetivo Critério de Sucesso

• Atender/satisfazer os requisitos do armador, com o menor custo possível

• Satisfazer requisitos regulatórios

– Desempenho

– Qualidade

– Fatores Humanos

– Custo

– Segurança

– Ambiente de Operação

– Interface com outros Sistemas

– Segurança

– Logística

– Confiabilidade

– Efeito nas Cercanias

– Viabilidade de Manutenção

– Facilidade de Conserto

– Estética

– ...

• Todo projeto possui limitações ou restrições, pois os recursos nunca são infinitos.

• Restrições são aplicadas a todo o projeto de navio, tanto ao processo de desenvolvimento como ao produto.

• Representam limitações e fronteiras para as soluções de projeto.▫ Orçamento

▫ Tempo

▫ Pessoal

▫ Leis

▫ Propriedades de Materiais e disponibilidade

▫ Viabilidade de Fabricação

Restrições

Restrições Restrições

FísicasFísicasEx. calado de portos

Restrições ao Restrições ao

ProcessoProcessoEx. disponibilidade de software

Restrições Restrições

AmbientaisAmbientaisEx. 1990 obrigatoriedade de casco duplo

Espiral de Andrews

Restrições

Projeto convencional x Projeto ótimo

Adquirir informações

para descrever o

sistema

Estimativa do projeto

inicial

Análise

Verificação do

desempenho

É satisfatório?

Modificar o projeto

baseado na

experiência/heurística

Projeto Concluídosim

não

Adquirir informações

para descrever o

sistema

Estimativa do projeto

inicial

Análise

Verificação das

restrições

É satisfatório? Projeto Concluído

Modificar o projeto

usando um modelo de

otimização

Identificar:

1. Variáveis de Projeto

2. Funções de Custo

3. Restrições

sim

não

PR

OJ

ET

O C

ON

VE

NC

ION

AL

PR

OJ

ET

O Ó

TIM

O

Processo de Projeto

OBJETIVOS

De uma longa folha retangular de metal de 30 cm de largura deve-se

fazer uma calha dobrando as bordas perpendicularmente à folha.

Quantos centímetros devem ser dobrados de cada lado de modo que

a calha tenha capacidade máxima?

• Folha tem largura L

• Borda tem comprimento x

• Volume V ocupado por uma calha é

V = L*(30-2x)*x

• A função (30-2x)*x = f(x) tem

máximo em x = 7,5

• Para x = 7,5 , Volume V é máximo

• Para x = 7,5 , o sistema é ótimo

Exemplo de Problema de Otimização

Introdução à Otimização

PROJETO CONVENCIONAL

L

h

b

• Viga Prismática

• Seção Retangular

• Material Madeira

• Engastada

Introdução à Otimização

PROJETO CONVENCIONAL

L

Introdução à Otimização

PROJETO CONVENCIONAL

L

• A viga existe?

• Posso comprá-la?

PROJETO CONCLUIDO

Introdução à Otimização

PROJETO ÓTIMO• Posso sustentar mais massa ?

• A estrutura pode ser mais

leve?

• A estrutura pode ser mais

barata?

L

Introdução à Otimização

PROJETO ÓTIMO• Viga “I”, “H”, caixa...?

• Viga não-prismática?

• Outros materiais?

• Estrutura treliçada?

Quantas barras?

Qual a configuração?

L

Definições: Variáveis de projeto

• São as variáveis que descrevem o sistema;

• Ao modificá-las independentemente, novas

soluções são obtidas;

• As variáveis de projeto devem ser independentes

entre si (o máximo possível / muitas vezes a

capacidade de análise do projetista não permite

identificar inter-relações).

Definições: Funções de custo

• São também chamadas de funções-objetivo;

• São expressões matemáticas que traduzem o

critério de desempenho do sistema;

• A função de custo deve depender das variáveis

de projeto;

• Projetos podem possuir mais de uma função de

custo, e nesse caso, o problema é chamado

problema de otimização multi-objetivo

Definições: Restrições de projeto

• As restrições de projeto definem fronteiras ao

espaço de soluções possíveis;

• Há restrições explícitas e implícitas

– Explícitas estabelecem, por exemplo, os limites

máximos e mínimos das variáveis de projeto;

– Implícitas limitam parâmetros do desempenho do

projeto e por isso são difíceis de serem modeladas

nas etapas iniciais da formulação do problema;

• As restrições podem ser ainda de igualdade ou

de desigualdade.

Definições: Restrições de projeto

x2

x1

x1=x2

x2

x1

x1=x2

x1≤ x2

Região

Viável

igualdade desigualdade

Forma padrão do modelo de otimização

SOLUÇÕES POSSÍVEIS

OBJETIVO

RESTRIÇÕES

Forma Canônica

Exemplo de Problema

Dados do Problema

Linha de Montagem 1 Linha de Montagem 2

Limite de uso: 100h/semana Limite de uso: 42h/semana Lucro Unitário

pára-quedas 10 horas por unidade 3 horas por unidade R$ 60,00

asa-deltas 10 horas por unidade 7 horas por unidade R$ 40,00

OBJETIVO: Programação de produção que maximize o lucro.

• Horizonte de tempo: 1 semana;

• Tempos idênticos na linha de montagem 1;

• Linha de montagem 1: 10 unidades (pára-quedas + asa-deltas);

• Linha de montagem 2: 14 pára-quedas OU 6 asa-deltas;

• Pára-quedas: menos tempo na linha de montagem 2 e maior lucro;

• Opção ótima: confecção de 10 pára-quedas;

• Lucro máximo: R$ 600,00

Solução “óbvia”

Possíveis soluções para o problema (guessing)

X1 X2 Restr. 1 Restr. 2 Restr. 3 Restr. 4 F(X)0 0 ok ok ok ok 0

1 1 ok ok ok ok 100

3 4 ok ok ok ok 340

4 3 ok ok ok ok 360

10 0 ok ok ok ok 600

0 10 ok falha ok ok -

5 2 ok ok ok ok 380

2 5 ok ok ok ok 320

3 6 ok falha ok ok -

6 3 ok ok ok ok 480

4 4 ok ok ok ok 400

5 5 ok falha ok ok -

14 2 falha falha ok ok -

14 0 falha ok ok ok -

0 11 falha falha ok ok -

-1 5 ok ok falha ok -

1 2 ok ok ok ok 140

2 2 ok ok ok ok 200

2 1 ok ok ok ok 160

3 1 ok ok ok ok 220

3 2 ok ok ok ok 260

3 3 ok ok ok ok 300

2 3 ok ok ok ok 240

1 3 ok ok ok ok 180

9 1 ok ok ok ok 580

9 2 falha ok ok ok -

8 1 ok ok ok ok 520

8 2 ok ok ok ok 560

7 3 ok ok ok ok 540

7 4 falha falha ok ok -

Formulação padrão do problema

Variáveis de decisão:

• X1: quantidade de pára-quedas a serem produzidos

• X2: quantidade de asa-deltas a serem produzidos

Função-objetivo:

• Maximizar F(X) = 60. X1 + 40. X2

Restrições:

• 10.X1 + 10.X2 ≤ 100

• 3.X1 + 7.X2 ≤ 42

• X1, X2 ≥ 0

Solução gráfica do problema

2 4 6 8 10 12 14 16

Soluções

Viáveis

X1

X2

8

10

6

4

2

Restrições

Solução gráfica do problema

2 4 6 8 10 12 14 16

Soluções

Viáveis

X1

X2

8

10

6

4

2

Restrições

Função objetivo F(X)

Solução gráfica do problema

2 4 6 8 10 12 14 16

Soluções

Viáveis

X1

X2

8

10

6

4

2

Restrições

Função objetivo F(X)

Solução gráfica do problema

2 4 6 8 10 12 14 16

Soluções

Viáveis

X1

X2

8

10

6

4

2

Restrições

Função objetivo F(X)

Máx F(X)

X1 = 10

X2 = 0

Solução usando o “solver” do Excel®

Função-objetivo:

• Maximizar F(X) = 60. X1 + 40. X2

Restrições:

• 10.X1 + 10.X2 ≤ 100

• 3.X1 + 7.X2 ≤ 42

• X1, X2 ≥ 0

Variáveis de decisão:

• X1: quantidade de pára-quedas a serem produzidos

• X2: quantidade de asa-deltas a serem produzidos

Solução usando o “solver” do Excel®

Função-objetivo:

• Maximizar F(X) = 60. X1 + 40. X2

Restrições:

• 10.X1 + 10.X2 ≤ 100

• 3.X1 + 7.X2 ≤ 42

• X1, X2 ≥ 0

X1 X2 total sinal b

Restrição 1 10 10 0 <= 100

Restrição 2 3 7 0 <= 42

F(X) 60 40 0

Solução

Solução usando o “solver” do Excel®

X1 X2 total sinal b

Restrição 1 10 10 0 <= 100

Restrição 2 3 7 0 <= 42

F(X) 60 40 0

Solução

Solução usando o “solver” do Excel®

X1 X2 total sinal b

Restrição 1 10 10 0 <= 100

Restrição 2 3 7 0 <= 42

F(X) 60 40 0

Solução

• Selecionar a célula F(x) total, que se quer maximizar

Solução usando o “solver” do Excel®

X1 X2 total sinal b

Restrição 1 10 10 0 <= 100

Restrição 2 3 7 0 <= 42

F(X) 60 40 0

Solução

• Selecionar a célula F(x) total, que se quer maximizar

• No Excel 2007, clique em Dados >> (Análise) Solver

• No Excel 2003, Ferramentas >> Solver >> Parâmetros do Solver

Solução usando o “solver” do Excel®

X1 X2 total sinal b

Restrição 1 10 10 0 <= 100

Restrição 2 3 7 0 <= 42

F(X) 60 40 0

Solução

• Em qualquer dos casos...

Solução usando o “solver” do Excel®

X1 X2 total sinal b

Restrição 1 10 10 0 <= 100

Restrição 2 3 7 0 <= 42

F(X) 60 40 0

Solução

• Em qualquer dos casos...

Solução usando o “solver” do Excel®

X1 X2 total sinal b

Restrição 1 10 10 0 <= 100

Restrição 2 3 7 0 <= 42

F(X) 60 40 0

Solução

• Em qualquer dos casos...

Solução usando o “solver” do Excel®

Solução usando o “solver” do Excel®

• A CEARS – Cia. De Estoques Agrícolas do Estado do Rio Grande

do Sul, está avaliando uma série de localidades no estado do Rio

Grande do Sul para construir três novos armazéns agrícolas. A

empresa já possui uma série de armazéns, mas está precisando

expandir sua capacidade devido ao crescimento expressivo das

atividades agrícolas em sua região de atuação. Os armazéns a

serem construidos serão graneleiros e poderão ser utilizados para

estocar uma série de produtos a granel, como soja e milho.

• Podemos classificar este problema como um de “P-medianas”:

envolve a localização de p facilidades e a designação de clientes

a facilidades, minimizando o custo/distância total de designação

Problema 2: Localização de Armazéns da “CEARS”

Localizações e Informações

• As 5 cidades escolhidas como

possiveis armazéns são marcadas

no mapa com a letra C;

• As 5 cidades clientes foram

marcadas com um X;

• Demandas e capacidades

referentes a um ano;

• Os custos logísticos referem-se a

uma tonelada de produto;

• A CEARS está interessada em

construir apenas 3 armazéns, com

custo total de construção e

logístico seja mínimo.

Demais Informações

Função-Objetivo e Restrições

• Levar-se-ão em conta dois custos:

(1) o de construção do armazém escolhido;

(2) o de logística.

• Como o armazém j pode encaminhar seus produtos para qualquer cliente i, chamamos de Yij a quatidade de produtos enviadas de j para i.

(i = 1, 2, 3, 4, 5)

• Consideramos a variável Xj como a presença do armazém na localidade j, ou seja, ela será uma variável binária:

(j = 1, 2, 3, 4, 5)

1

Xj =

0

Função-Objetivo e Restrições

• A função-objetivo é o custo total Z , que deverá ser minimizado

Z = 7000*X1 + 5000*X2 + 9000*X3 + 6000*X4 + 4000*X5

+

2,1*Y11 + 6,3*Y21 + 7,8*Y31 + 6,3*Y41 + 7,5*Y51

+

5,7*Y12 + 2,7*Y22 + 4,5*Y32 + 4,5*Y42 + 3,78*Y52

+

5,4*Y13 + 5,58*Y23 + 4,38*Y33 + 2,88*Y43 + 4,8*Y53

+

10,2*Y14 + 6,54*Y24 + 1,14*Y34 + 2,4*Y44 + 3*Y54

+

5,58*Y15 + 7,86*Y25 + 6*Y35 + 3,48*Y45 + 6,84*Y55

Função-Objetivo e Restrições

• Sabemos que as quantidade enviadas dos armazéns não podem exceder

as capacidades dos armazéns:

Y11 + Y21 + Y31 + Y41 + Y51 <= 600*X1 (Capacidade do armazém 1)

Y12 + Y22 + Y32 + Y42 + Y52 <= 750*X2 (Capacidade do armazém 2)

Y13 + Y23 + Y33 + Y43 + Y53 <= 350*X3 (Capacidade do armazém 3)

Y14 + Y24 + Y34 + Y44 + Y54 <= 450*X4 (Capacidade do armazém 4)

Y15 + Y25 + Y35 + Y45 + Y55 <= 400*X5 (Capacidade do armazém 5)

Função-Objetivo e Restrições

• As demandas também estão restritas, sendo atendidas pelos envios

conforme as inequações:

Y11 + Y12 + Y13 + Y14 + Y15 = 150 (demanda de Uruguaiana )

Y21 + Y22 + Y23 + Y24 + Y25 = 450 (demanda de Pelotas )

Y31 + Y32 + Y33 + Y34 + Y35 = 300 (demanda de Caxias do Sul )

Y41 + Y42 + Y43 + Y44 + Y45 = 250 (demanda de Passo Fundo )

Y51 + Y52 + Y53 + Y54 + Y55 = 500 (demanda de Porto Alegre )

Função-Objetivo e Restrições

• O último grupo de restrições estabelece que apenas 3 armazéns devem ser

abertos, ou seja:

X1 + X2 + X3 + X4 + X5 = 3

• As variáveis Xj são binárias (ou seja, só assumem os valores 0 ou 1)

Solução usando o “solver” do Excel®

Análise da Solução

• As fábricas 1, 2 e 5 devem ser abertas, pois:

X1 = 1 , X2 = 2 , X3 = 0 , X4 = 0 , X5 = 1

• Valores tranferidos dos armazéns 1, 2 e 5 para as cinco cidades

clientes:

Y11 = 150 , Y22 = 450 , Y32 = 200 , Y35 = 100 ,

Y45 = 250 , Y51 = 450 , Y55 = 50

• O função-objetivo minimizada Custo Total também é calculada:

função-objetivo = 22729,00.