otimizacao de projetos

Prévia do material em texto

OTIMIZAÇÃO DE PROJETOS
MARCO ANTÔNIO RAHAL SACOMAN[1] 
1. RESUMO 
OTIMIZAÇÃO DE PROJETOS
Este trabalho apresenta as informações mínimas necessárias para que se possa perceber as vantagens da utilização da otimização na solução de projetos. São apresentados os conceitos de modelagem e um exemplo de otimização de projeto estrutural. O exemplo mostra que a solução obtida é a melhor possível, entre as infinitas soluções existentes. 
Palavras-Chave: Projeto ótimo, programação não-linear, pesquisa operacional 
2. SUMMARY 
OPTIMUM DESIGN
This work introduces the minimum informations in order to perceive the advantages when utilizing optimization for projects solution. Modeling concepts are presented and also an example of optimum structural design. The example shows the solution obtained is the best one possible among infinity existing solutions. 
Keywords: Optimum design, nonlinear programming, operations research 
3. INTRODUÇÃO 
A elaboração e execução de um projeto ótimo deve utilizar procedimentos de engenharia e de pesquisa operacional. A engenharia procura soluções técnicas para os problemas, que são formalizadas como projetos. A pesquisa operacional trata, através da estatística e da otimização, da seleção do projeto mais adequado. 
Os projetos podem envolver aspectos técnicos, econômicos, e até de cunho social. São, portanto, projetos de dimensionamento, alocação de recursos, localização de empreendimentos, determinação de rotas e tantos outros que possam se beneficiar de técnicas de engenharia e de pesquisa operacional, para a busca de uma solução ótima. 
A solução teórica de um projeto pode ter infinitas soluções e, na prática, várias delas podem ser consideradas aceitáveis. 
Contudo, devido à grande competitividade de mercado, não é adequado desenvolver um projeto que seja apenas aceitável. Portanto, há uma real necessidade de respostas para perguntas como:
o uso de recursos escassos está sendo o mais eficiente ?
pode-se obter um projeto mais econômico ?
há riscos dentro dos limites aceitáveis ? 
Para responder adequadamente tais questões, foram desenvolvidos, nas últimas quatro décadas, modelos e técnicas de otimização. O crescimento, paralelo, das facilidades computacionais, permitiram a utilização das técnicas desenvolvidas. Outro aspecto que estimulou o uso de uma abordagem sistemática na solução de problemas, foi o rápido aumento, no tamanho e na complexidade, dos problemas, como resultado do avanço tecnológico desde a segunda guerra mundial. 
Após a guerra, a aceitação da pesquisa operacional, nas atividades industriais, empresariais, militares e governamentais, pode ser creditada, no mínimo, pela extensão com a qual a abordagem e a metodologia da pesquisa operacional ajudaram nas tomadas de decisão. As aplicações eram, principalmente, aquelas que utilizavam a programação linear e a análise estatística. Na década de 60 já eram disponíveis procedimentos e códigos computacionais eficientes para estas aplicações. 
Contudo, os modelos matemáticos que representam o comportamento de um projeto, só serão adequados se suas equações forem, tanto quanto possível, fiéis ao que acontece na realidade. E é evidente que os modelos não-lineares representam melhor a realidade. Nas últimas duas décadas, houve um grande avanço nas técnicas de otimização não-linear. 
A técnica de pesquisa operacional para a solução de problemas de otimização, utilizada neste trabalho, é a Programação Matemática, mostrando-se como a Programação Não-Linear permite uma modelagem eficiente para os problemas de otimização de projetos. 
De forma geral, o que se defende é a idéia de que a abordagem sistemática, com a utilização da pesquisa operacional, produz um resultado melhor e mais confiável do que a abordagem tradicional. Esquematicamente, a Figura 1 mostra uma comparação entre estas abordagens. No caso da abordagem tradicional, se faz necessária uma avaliação posterior, para verificar se os valores obtidos são aceitáveis. No caso da otimização, o próprio procedimento utilizado, seleciona valores para as variáveis, dentro dos limites permitidos. 
FIGURA 1 - 
Comparação entre formas de abordagem de um projeto: (a) Cálculo clássico; (b) Cálculo por otimização.
A necessidade de reduzir o peso das estruturas sem comprometer a integridade estrutural, particularmente em aplicações aeroespaciais, foi historicamente a grande força motriz por detrás do desenvolvimento dos métodos de projeto ótimo. Este impulso ocorreu nos anos 60 e SCHMIT (1981) escreve, com muita propriedade, seu desenvolvimento. 
Porém, a literatura sobre otimização de projetos estruturais remonta desde o século passado. Inicialmente, com o trabalho de Maxwell[2] e, em seguida, seu desenvolvimento feito por Michell[3], ambos citados por SCHMIT (1981), supriram a teoria básica para a solução de problemas de otimização de peso de estruturas treliçadas simples (sujeitas apenas às restrições de tensão). Desta época até o final da década de 50, os trabalhos escritos foram quase todos relacionados com o mesmo tipo de problema. 
A partir daí, com as facilidades criadas pelo uso do computador, após o surgimento da linguagem FORTRAN, o avanço foi grande. Empresas como a NASA (1960), Bell Aerosystems (1964) e Boeing (1968), envolveram-se em pesquisas relacionadas com a otimização estrutural. Em seguida, GALLAGHER e ZIENKIEWICZ (1973) apresentaram a primeira coletânea de artigos importantes em otimização estrutural. 
Após esta fase, na década de 70, as pesquisas se caracterizaram pelo desenvolvimento e escolha de métodos matemáticos de otimização para uso em problemas de otimização estrutural. 
A partir da década de 70, até a atualidade, as pesquisas têm-se concentrado em métodos matemáticos de resolução de problemas de combinatória, para solução de problemas com variáveis discretas e, em termos de programação matemática, têm-se concentrado na melhoria dos códigos computacionais baseados em métodos de gradiente de passos largos, para que esses códigos possam resolver problemas de grande porte, de forma tão eficiente quanto vêm resolvendo os problemas de pequeno e médio portes que lhes tem sido submetidos atualmente. 
Dentro desta última linha de trabalho, há que se ressaltar que o Método do Gradiente Reduzido Generalizado foi o método eleito para as pesquisas desenvolvidas pelo Laboratório de Otimização de Projetos da Universidade de Arizona (WANG e RAGSDELL, 1984a; WANG e RAGSDELL, 1984b), além de ser o método eleito por Lasdon e Smith para resolver problemas não-lineares de grande porte (JOHNSON e NEMHAUSER, 1992). Uma breve descrição deste método é apresentada na próxima seção. 
É importante salientar que as pesquisas em desenvolvimento de métodos e códigos computacionais para solução de problemas de programação não-linear têm sido efetuadas por pesquisadores associados a institutos de pesquisas governamentais e universidades. As empresas que comercializam sistemas computacionais na área de otimização insistem em vender a imagem de que seus códigos de programação linear são eficientes e resolvem todos os problemas que lhes são submetidos. Vão além, ao afirmar que "as empresas de petróleo e química têm conhecimento e entendem que seus problemas são não-lineares há muito tempo, mas, apesar disto, a metodologia predominante parece ser a solução seqüencial de problemas lineares" (JOHNSON e NEMHAUSER, 1992). 
Nesta mesma linha de raciocínio, WILSON e RUDIN (1992) apresentaram a última versão da Biblioteca de Rotinas de Otimização da IBM, que contém rotinas para resolver problemas de programação linear, programação quadrática, programação inteira mista e fluxo em redes. Esta é mais uma nova versão da biblioteca de rotinas que, desde a década de 60, resolve os mesmos tipos de problema, sem contemplar a programação não-linear. 
As áreas que têm sido alvo de pesquisas envolvendo programação não-linear são, principalmente, otimização de projetos estruturais, energéticos, agropecuários, petroquímicose econômico-financeiros. 
4. MÉTODO 
A otimização de projetos requer a modelagem de problemas em diferentes áreas de aplicação e a solução desses modelos através de recursos computacionais adequados. Portanto, requer, também, o estudo de métodos e algoritmos que resolvem problemas de otimização não-linear e a implementação computacional desses algoritmos. 
4.1. Modelagem do Problema de Projeto Ótimo 
A otimização procura os valores das variáveis de projeto para obter, dentro das restrições, seu fim de otimalidade definido pela função objetivo. 
Para melhor compreensão do significado dessas entidades, as seguintes definições são úteis: 
Variáveis de Projeto
Um sistema a ser otimizado pode ser descrito por um conjunto de quantidades, onde algumas das quais são fixadas e outras variam durante um processo de otimização. Estas quantidades que são fixas, são pré-determinadas por preceitos de normas técnicas, disposições construtivas, pré-fabricação, ou ainda, pelo fato do projetista saber por experiência que um valor particular produz bons resultados. As quantidades que não são pré-determinadas são as variáveis de projeto. 
Restrições
Em qualquer classe de problema, as restrições são as condições que devem ser satisfeitas para que o projeto seja aceitável. Um projeto que satisfaz todas as suas restrições é chamado de projeto viável. As restrições podem ser dos seguintes tipos: 
restrições em variáveis de projeto, que são escritas na forma de limitações impostas diretamente nas variáveis ou grupos de variáveis;
restrições de comportamento, que são obtidas a partir das equações de análise do sistema a ser otimizado. 
Função Objetivo
Em geral, existe um número infinito de projetos viáveis para um determinado problema. Para que se possa fazer uma escolha, é necessário que se tenha uma função que sirva como base de comparação entre os vários projetos aceitáveis. Esta é a função objetivo, também chamada custo, econômica, critério ou mérito. É uma função das variáveis de projeto e deve ser minimizada ou maximizada. Pode representar a propriedade mais importante do projeto, ou a soma ponderada de um número de propriedades. Em geral, a função objetivo é uma função não-linear das variáveis de projeto. 
4.2. Algoritmo 
Considera-se o problema geral de programação não-linear escrito sob a seguinte forma: 
Esta formulação é geral e pode representar todos os problemas de programação não-linear. Isto é possível, porque as restrições de desigualdade sempre podem ser transformadas em restrições de igualdade pela introdução de variáveis de folga. Além disto, em problemas de minimização, basta que se utilize a relação mín{f(x)} = -máx{-f(x)}. 
O algoritmo, descrito a seguir, é baseado no Método do Gradiente Reduzido Generalizado e a notação utilizada ao longo do algoritmo é apresentada no Quadro 1. 
Quadro 1 - Notação utilizada. 
Nome
Notação
Relacionado à base
Não-relacionado à base
Variáveis
x
xB
xN
Gradiente da função objetivo 
Jacobiano das restrições ���INCLUDEPICTURE \d "oti01_08.gif"� 
Direção
d
dB
dN
B é o conjunto dos índices das variáveis básicas; |B|=m
N é o conjunto dos índices das variáveis não-básicas; |N|=n-m
xk, dk são os valores de x e d na k-ésima iteração do algoritmo
Passo 1
Encontrar uma primeira solução viável x0. Considerar xk a k-ésima solução encontrada pelo algoritmo. 
Passo 2
Calcular o jacobiano �no ponto xk e separar as variáveis em �(variáveis básicas) e �(variáveis não-básicas), de forma a satisfazer as hipóteses de não-degenerescência:
H1) �
H2) �é não-singular. 
Passo 3
Calcular a direção de deslocamento das variáveis não-básicas, como segue:
a) calcular os multiplicadores de Lagrange
�
b) calcular o gradiente reduzido
�
c) calcular o gradiente reduzido projetado
�
Se pN = 0, PARAR; senão, fazer dN = pN. 
Passo 4
Calcular a direção de deslocamento das variáveis básicas, como segue:
�, então, �
e a partir da relação, calcular dB
�
Passo 5
Melhorar a solução, como segue:
a) encontrar um valor positivo �que maximize �
b) deslocar as variáveis, tanto não-básicas como básicas, segundo as direções calculadas
�
o ponto obtido �, em geral, não é viável; então, 
c) resolver um sistema de m equações não-lineares a m incógnitas, para modificação de suas variáveis básicas
�
para tanto, aplicar um método pseudo-Newton:
- calcular, iterativamente, a partir de �
�
- considerar �a solução encontrada, e o ponto obtido �pode ser tal que:
. se �, tentar encontrar um novo ponto, reduzindo �;
. se �, tentar encontrar uma solução melhor, aumentando �;
. se �, efetuar uma troca de base. 
Retornar ao Passo 2. 
5. EXEMPLO DE APLICAÇÃO 
Nesta seção é apresentada a modelagem e a solução de um problema de otimização de projeto, pela programação não-linear. O exemplo (SACOMAN, 1994) tem apenas duas variáveis, para que se possa representar graficamente as variáveis de projeto, as restrições, a função objetivo e o espaço de solução do problema de otimização, por programação não-linear. 
Deseja-se projetar, para construção em série, estruturas tipo viga-caixão, bi-apoiadas em consolos, tal como mostrado na Figura 2. O objetivo da otimização é minimizar a quantidade de material a ser consumido no projeto. O material utilizado será o alumínio, cujo peso específico �. 
FIGURA 2 - 
(a) Estrutura viga-caixão bi-apoiada; (b) Carregamento; (c) Seção Transversal.
São dadas, para o projeto, as seguintes constantes:
vão da viga L0 = 600 cm
tensão admissível de cisalhamento 
largura da viga b = 60 cm
tensão normal admissível de flexão 
largura da aba ts = 0,5 cm
módulo de elasticidade do alumínio E = 700 tf/cm2
deflexão máxima 
carregamento na viga p = 10-4 tf/cm2 = 6.10-3 tf/cm
Deseja-se projetar a viga, de tal forma que:
 (a)
o peso da estrutura seja mínimo;
(b)
as dimensões das variáveis x1 e x2 sejam positivas;
(c)
a máxima tensão de cisalhamento não exceda a admissível;
(d)
a máxima tensão normal de flexão não exceda a admissível;
(e)
não ocorra flambagem nas abas;
(f )
a máxima deflexão não exceda a admissível.
De acordo com os itens (a) até (f) listados, o problema pode ser formulado como segue:
�
Inicialmente, é necessário conhecer as expressões de 
FIGURA 3 - 
Esquema estático, equações de reação de apoio, diagramas e equações de momento fletor e força cortante.
As expressões da sobrecarga, da área da seção transversal, da carga permanente e da carga total da viga são: 
p = 6.10-3 tf/cm; cm2
tf/cm 				q = p+g = 6.10-3+2,7.10-6.(118.x1+x2) tf/cm
Seguem as expressões necessárias para a modelagem do problema: 
Na expressão de 
Na expressão de 
A função a ser minimizada fornece o peso da estrutura, ou seja, �. Como �são constantes, basta otimizar a função �. 
O problema, então, se reduz a:
 
Ou seja:
 
A Figura 4 mostra o espaço de solução do problema e o projeto ótimo 
FIGURA 4 - 
Espaço de projeto, função objetivo e solução ótima do problema da viga-caixão.
O ótimo é o ponto x* que é formado pela tangência de f com g3. 
Então, isolando x2 nas expressões de f e g3, derivando x2 com relação a x1, para as duas expressões, e igualando-as, tem-se: 
f(x):
�
x2 = f(x)-118.x1
�
g3(x):
 
x1 = 0,6423; x2 = 25,262; f(x) = 101,048
Então, a solução ótima do problema é dada por 
6. CONCLUSÕES 
O exemplo, com apenas duas variáveis, serve para demonstrar que a utilização da otimização produz um resultado melhor e mais confiável do que aquele que poderia ser obtido com a abordagem tradicional. Melhor, por ter selecionado o ponto ótimo, dentre os infinitos pontos da região viável, de acordo com o objetivo pré-definido.Mais confiável, porque a modelagem por otimização requer que as restrições sejam explicitadas, evitando os erros que poderiam ocorrer na avaliação do resultado, necessária no cálculo clássico. 
Da mesma forma como o problema-exemplo foi modelado, diferentes problemas de diversas áreas de aplicação podem ser modelados e resolvidos através de técnicas de otimização não-linear. 
Problemas não tão simples, como o apresentado na seção anterior, e que tenham várias variáveis deverão ser resolvidos computacionalmente com um programa que resolva problemas de programação não-linear e que pode ser implementado a partir de algoritmos como o descrito na seção 4.2. 
Detalhes sobre uma implementação computacional do Método do Gradiente Reduzido Generalizado para microcomputadores e alguns modelos e soluções aplicados a diferentes áreas são encontrados em SACOMAN (1994). 
7. REFERÊNCIAS BIBLIOGRÁFICAS 
PRIVATE�GA
LLAGHER, R. H.; ZIENKIEWICZ, C.O. Optimum Structural Design. London: John Willey & Sons, 1973. 372p.
JO
HNSON, E. L.; NEMHAUSER, G. L. Recent Developments and Future Directions in Mathematical Programming. IBM Systems Journal, v.31, n.1, p.79-93, 1992.
SA
COMAN, M. A. R. Aplicação da Programação Não-Linear na Solução de Problemas de Energia na Agricultura. Botucatu, 1994. Tese (Doutorado) - FCA-UNESP.
SC
HMIT, L. A. Structural Synthesis: Its Genesis and Development. American Institute of Aeronautics and Astronautics Journal, v.19, n.10, p.1249-1263, 1981.
WA
NG, S. H.; RAGSDELL, K. M. OPT2 User's Guide: A Nonlinear Programming Code in FORTRAN IV Implementing an Advanced Version of the Generalized Reduced Gradient Method. Tucson: University of Arizona at Tucson, 1984. 64p.
WA
NG, S. H.; RAGSDELL. K. M. TRUOPT User's Manual: A Structural Synthesis Software Package Employing Multilevel Approximation Techniques and the Generalized Reduced Gradient Method. Tucson: University of Arizona at Tucson, 1984. 52p.
WI
LSON, D. G.; RUDIN, B. D. Introduction to the IBM Optimization Subroutine Library. IBM Systems Journal, v.31, n.1, p.4-10, 1992.
[1]Docente do Departamento de Computação - DCo-FC-UNESP - Bauru-SP-Brasil. 
[2]Maxwell, C. - Scientific Papers, 1869, vol.2, 175-177. 
[3]Michell, A. G. M. - The Limits of Economy of Material in Frame Structures, Philosophical Magazine, Nov. 1904, no.47, vol.8, series 6, 589-595. 
© Marco Antônio Rahal Sacoman - mail - http 
DCo-FC-UNESP - maio de 1998