Modelos de otimização

Prévia do material em texto

Escola Superior de Negócios e Empreendedorismo de Chibuto (ESNEC)
Departamento de Gestão
Licenciatura em Gestão de Empresas
Nível II - Laboral
MQG (Métodos quantitativos aplicados a gestão)
Modelos de optimização 
Discente: Caiamy Constantino Pinto Alberto Docente: dr.Stella Ocuane		 	
Chibuto, Março de 2021
2
Índice	
1.	Introdução	2
1.1.	Objectivos	2
2.	Metodologia	3
3.	Revisão da bibliografia	4
3.1.	Modelos de optimização	4
3.1.1.	Representação matemática de um método de optimização	5
3.1.2.	Métodos determinísticos	5
3.1.3.	Métodos Probabilísticos	6
3.2.	Analise marginal	6
3.3.	Programação linear	7
3.3.1.	Método simplex	8
3.4.	Programação não linear	12
4.	Referencias bibliográficas	13
1. Introdução
A optimização é uma área da ciência que busca responder à pergunta “O que é melhor?” para problemas em que a qualidade de uma resposta pode ser medida por um número. Estes problemas aparecem em praticamente todas as áreas do conhecimento: negócios, ciências físicas, químicas e biológicas, engenharia, arquitectura, economia e administração. A quantidade de ferramentas disponíveis para auxiliar nesta tarefa é quase tão grande quanto o número de aplicações.
No presente trabalho, serão apresentados alguns conceitos gerais sobre optimização e a maneira formal de se apresentar um problema de optimização.
1.1. Objectivos
1.1.1. Geral
· Conhecer os modelos de optimização 
1.1.2. Específicos
· Definir modelo de optimização 
· Representar matematicamente um modelo de optimização 
· Conhecer os métodos determinísticos
· Conhecer os métodos probabilísticos
· Explicar a analise marginal
· Simplificar a programação linear
· Explicar a analise não linear
2. Metodologia
Segundo Gil (2006), define-se pesquisa como um processo formal e sistematizado de desenvolvimento do método científico, que tem como objectivo fundamental, descobrir respostas para problemas mediante o emprego de procedimentos científicos.
2.1. Quanto a natureza
No que se refere a natureza da pesquisa, optou-se pela aplicada, que objectiva gerar conhecimentos para aplicações praticas com objectivo de solucionar problemas específicos.
2.2. Quanto aos objectivos
Aplicou-se pesquisa descritiva de forma a proporcionar maior familiaridade com o problema.
2.3. Quanto aos procedimentos
Em relação aos procedimentos, usou-se uma pesquisa bibliográfica que é desenvolvida a partir de material já publicado, constituído principalmente de livros e artigos científicos (Gil, 2006).
3. Revisão da bibliografia
3.1. Modelos de optimização
A optimização pode ser definida como um conjunto de procedimentos por meio dos quais se busca minimizar e maximizar um determinada função, denominada função objectivo, sujeita ou não a uma série de restrições, obtendo assim um melhor aproveitamento dos recursos disponíveis (Oliveri, 2004).
Os problemas de optimização são problemas de maximização ou minimização de função de uma ou mais variáveis num determinado domínio, sendo que, geralmente, existe um conjunto de restrições nas variáveis.
Os algoritmos usados para a solução de um problema de optimização podem ser, basicamente, determinísticos ou probabilísticos.
Para melhor entendimento dos algoritmos de optimização, faz-se necessário o conhecimento de alguns conceitos e definições utilizados na literatura (BASTOS, 2004). 
A seguir são listados alguns termos usualmente relacionados a um problema de optimização qualquer:
· Variáveis de projecto: São aquelas que se alteram durante o processo de optimização, podendo ser contínuas (reais), inteiras ou discretas.
· Restrições: São funções de igualdade ou desigualdade sobre as variáveis de projecto que descrevem situações de projecto consideradas não desejáveis.
· Espaço de busca: É o conjunto, espaço ou região que compreende as soluções possíveis ou viáveis sobre as variáveis do projecto do problema a ser optimizado, sendo delimitado pelas funções de restrição.
· Função Objectivo: é uma função que associa cada ponto no espaço de soluções a um número real. Este número permite medir a qualidade de uma resposta: no problema de minimização, quanto menor este valor, melhor a resposta. No problema de maximização, o inverso ocorre. 
· O Ponto Óptimo: É o ponto formado pelas variáveis de projecto que extremizam a função objectivo e satisfazem as restrições.
· Valor Óptimo: É o valor da função objectivo no ponto óptimo.
3.1.1. Representação matemática de um método de optimização
Geralmente um problema de optimização pode ser representado, matematicamente, por um sistema de equações ou desigualdades composta por uma série de funções objectivo (f1,f2,…fp) e uma série de restrições (g1, g2, …gp) entre suas variáveis (x1, x2, … xn), conforme mostrado a seguir:
f1 = f1 (x1, x2, …xn) cf1	g1=g1 (x1,x2,…xn)cg1
f2 =f2(x1,x2,…xn) cf2	g2=g2(x1,x2,…xn)cg2
…	…
Fp=fp(x1,x2,…xn)cfp	gq=gq(x1,x2,…xn)Cgq
Onde:
· f2, f2, f3 … fp : Representa as funções objectivo a serem optimizadas.
· cf1, cf2, cf3 … cfp : Limites desejados para função objectivo.
· g1, g2, g3 … gq :Funções de restrição para o problema.
· Cg1, cg2,cg3 … cgq : Limites desejados para as restrições.
· x1, x2, x3 … xn : Variáveis do problema.
3.1.2. Métodos determinísticos
Métodos determinísticos, também conhecidos como métodos clássicos, conseguem se aproximar ao ponto óptimo por meio de uma sequencia determinística, que gera possíveis soluções, empregando um ponto de referencia como ponto de partida e um vector de direcção para avançar no espaço de busca.
Um método de optimização é chamado de Determinístico se for possível prever todos os seus passos conhecendo seu ponto de partida. Em outras palavras, um método determinístico sempre leva à mesma resposta se partir do mesmo ponto inicial.
Para utilizar este tipo de método, a função objectivo e as restrições precisam ser representadas por funções matemáticas e/ou relações funcionais, sendo que a função objectivo precisa ser continua e diferenciável num espaço de busca convexo (Polak, 1971; Tavares e Correia, 1999).
Quando se trata de um problema de variáveis discretas, considera-se um espaço de busca com variáveis contínuas que, após a optimização, fornecerão uma aproximação das variáveis de projecto para as disponíveis no espaço discreto. Entretanto, isso gera um trabalho adicional na escolha das variáveis discretas mais próximas das contínuas encontradas. Sempre existirão duas
opções de variáveis discretas para cada variável contínua, ou seja, uma imediatamente superior e outra imediatamente inferior. Os métodos determinísticos apresentam teoremas que lhes garantem a convergência para uma solução óptima que não é necessariamente a solução óptima global. Como nesses métodos a solução encontrada é extremamente dependente do ponto de partida fornecido, pode-se convergir para um óptimo local, por isso não possuem bom desempenho em optimizar funções multimodais, isto é, funções que possuem vários óptimos locais.
· De acordo com OLIVIERI (2004), BASTOS (2004) e HAFTKA(1993), os problemas de optimização abordados pelos métodos clássicos podem ser classificados em duas classes, conforme as características da função objectivo e das restrições:
· Programação Linear: quando a função objectivo e as restrições são funções lineares das variáveis de projecto. O Método Simplex (HADLEY, 1982) é o método mais tradicional para solucionar este tipo de problema de optimização;
· Programação Não-Linear: quando a função objectivo, ou pelo menos uma das restrições, é uma função não-linear das variáveis de projecto. 
3.1.3. Métodos Probabilísticos
Os métodos de optimização baseados nos algoritmos probabilísticos usam somente a avaliação da função objectivo e introduzem no processo de optimização dados e parâmetros estocásticos. Por não utilizarem a derivada da função objectivo, são considerados métodos de ordem zero.
3.2. Analise marginal
Analise marginal é a relação que se faz entre os custos para desempenhar uma certa actividade em uma empresa e os benefícios obtidos através desses custos.
O objectivo da analise marginaé comparar custos com resultados na perspectiva de aumentar a lucratividade de uma empresa a partir dessa estratégia.
Esse tipo de analise é muito importante para guiar a tomada de decisão dentro de uma empresa. Isso porque com ela o gestor pode, por exemplo, decidir se alocar recursos em uma actividade X trará os resultados esperados. No caso de haver uma relação de ganhos relativos a custos, ele pode decidir manter ou aumentar o investimento na mesma.
Caso ocorra o contrário ele pode optar por deixar de investir nessa actividade e buscar algo que traga maiores benefícios. 
Para fazer os cálculos, é preciso ter informações de todas as variáveis de produção, pois ele é baseado na media dos custos.
O custo marginal (Cmg) é igual a variação do custo total () dividido pela variacao da quantidade total produzida ().
Ou seja a formula do custo total é:
 
No entanto para saber esse custo, precisa-se, antes, mensurar os custos fixos e os custos variáveis de produção e, também, os custos totais.
3.3. Programação linear
Programação linear é um problema de optimização em que a função que se pretende optimizar (função objectivo) é linear e esta sujeita a restrições (geralmente inequações lineares) que redefinem o seu domínio, ou seja, num problema de Programação linear pretende-se determinar o óptimo de uma função linear num conjunto convexo que resulta na intersecção de inequações lineares. A formulação do problema a ser resolvido por programação linear segue alguns passos básicos:
· Deve ser definido o objectivo básico do problema, ou seja, a optimização a ser alcançada. Por exemplo, maximização de lucro, ou de desempenhos, ou de bem-estar social; minimização de custos, de perdas, de tempo. Tal objectivo será representado por uma função objectivo, a ser maximizada ou minimizada;
· Para que esta função objectivo seja matematicamente especifica devem ser definidas as variáveis de decisão envolvidas. Por exemplo número de maquinas, a área a ser explorada, as classes de investimento a disposição, etc. Normalmente, assume-se que todas essas variáveis possam assumir somente valores positivos;
· Essas variáveis normalmente estão sujeitas a uma série de restrições, normalmente representadas por inequações. Por exemplo, quantidade de equipamento disponível, tamanho da área a ser explorada, capacidade de um reservatório, etc.
Todas essas expressões, entretanto, devem estar de acordo com a hipótese principal da programação linear, ou seja, todas as relações entre as variáveis devem ser lineares. Isso implica proporcionalidade das quantidades envolvidas. 
3.3.1. Método simplex
O método simplex é um procedimento matricial para resolver o modelo de programação linear na forma normal.
Começando com X0, o método localiza sucessivamente outras soluções básicas viáveis acarretando melhores valores para a função objectivo até ser obtida a solução óptima.
Para os problema de minimização, o método simplex utiliza o quadro abaixo:
	
	XT
CT
	
	X0 C0
	A
	B
	
	CT – C0T A
	- CT0 B
Para os problemas de maximização o quadros acima e aplicado desde que os elementos da linha inferior sejam colocados com sinal invertido.
Uma vez obtida esta ultima linha do Quadro, a segunda linha e a segunda colina do Quadro, correspondentes a CT e C0, respectivamente, tornam-se supérfluas e podem ser eliminadas.
CT: vector linha dos custos correspondentes.
X: vector coluna de incógnitas (incluindo variáveis de folga, excesso e artificiais).
A: matriz de coeficientes das equações de restrições.
B: vector coluna de valores á direita das equações representando as restrições.
X0: vector coluna de variáveis de folga e artificiais.
C0: vector coluna de custo associado com as variáveis em X0.
Como resolver um problema de optimização usando o modelo simplex:
1. Localize o número mais negativo da última linha do quadro simplex, excluída a última coluna, e chame a coluna em que este número aparece de coluna de trabalho. Se existir mais de um candidato a número mais negativo, escolha um.
2. Forme quocientes da divisão de cada número positivo da coluna de trabalho pelo elemento da última coluna da linha correspondente (excluindo-se a última linha do quadro). Designe por pivô o elemento da coluna de trabalho que conduz ao menor quociente. Se mais de um elemento conduzir ao mesmo menor quociente, escolha um. Se nenhum elemento da coluna de trabalho for positivo, o problema não terá solução.
3. Use operações elementares sobre as linhas a fim de converter o elemento pivô em 1 e, em seguida, reduzir a zero todos os outros elementos da coluna de trabalho.
4. Substitua a variável x existente na linha pivô e primeira coluna pela variável x da primeira linha e coluna pivô. Esta nova primeira coluna é o novo conjunto de variáveis básicas.
5. Repita os passos de 1 a 4 até a inexistência de números negativos na última linha, excluindo-se desta apreciação a última coluna.
6. A solução óptima é obtida atribuindo-se a cada variável da primeira coluna o valor da linha correspondente, na última coluna. Às demais variáveis é atribuído o valor zero. O valor óptimo da função objectivo, associado a Z, é o número resultante na última linha, última coluna, nos problemas de maximização ou o negativo deste número, nos problemas de minimização. 
Exemplo: 
Maximizar: Z = x1+9x2+x3
Sujeito a: x1+2x2+3x3 9 e 3x1+2x2+2x3 15
 
Passo 5: Não é necessário aplicar, pois não existe números negativos na última
linha.
Passo 6
X2 = 9/2
X5 = 6
X1 = X3 = X4 = 0
Z = 81/2
3.4. Programação não linear
Para que um problema de programação matemática seja caracterizado como de programação
não-linear, ele deve apresentar uma função objectivo não linear, ou pelo menos uma das
restrições caracterizada por uma função não linear. Os problemas de programação linear
podem ser classificados, de acordo com o número de variáveis e restrições em:
a) Problemas mono-variados sem restrição
Min f (x) = 2x6 + 3x4 - 12x 
b) Problemas multi-variados sem restrição 
Min f (x1, x2 ) = x12 + 2 x22 − 2 x2 − 2 x1 x2
c) Problemas mono-variados com restrição 
Min 
s.a: 
d) Problemas multi-variados sem restrição
Min 
s.a: 
	 
 		
4. Referencias bibliográficas 
· https://www.maxwell.vrac.puc-rio.br/7603/7603_4.PDF
· https://www.maxwell.vrac.puc-rio.br/7603/7603_4.PDF
· http://www2.peq.coppe.ufrj.br/Pessoal/Professores/Arge/COQ897/Naturais/aulas_piloto/aula1.pdf
· http://www.celiomoliterno.eng.br/Arquivos/Pesop/Metodo%20Simplex.pdf
· http://mayerle.deps.prof.ufsc.br/private/eps5115/PNL%2001.pdf