Aula 10 -Otimização

Prévia do material em texto

>
MODELAGEM MATEMÁTICA
Aula 10: Otimização
Apresentação
Na última aula, nós estudamos os métodos mais tradicionais de resolução de EDO de 1ª ordem. Vimos o método de Euler
e suas variantes, bem como o método de Runge-Kutta. Ao �nal da aula, nós aplicamos os métodos estudados por meio da
implementação computacional de programas em Python. 
Agora, nós veremos outro problema clássico em Engenharia – a resolução de Problema de Programação Linear. Trata-se
de uma ferramenta importante em um sem número de casos em Engenharia de Produção, de modo que o conhecimento
de técnicas computacionais pode ser decisivo em situações-problema da Engenharia. 
Nesta aula de conclusão da disciplina, você fará um estudo dos fundamentos de Otimização e o emprego de métodos
numéricos de apoio. Nosso estudo começará com problemas unidimensionais sem restrições. Em seguida, você estudará
problemas de programação linear com restrições, com apoio da solução grá�ca. Por �m, você resolverá problemas
relacionados ao tema, aplicando o software Solver do Microsoft Excel.
Objetivos
Identi�car os principais métodos de resolução de Problemas de Programação Linear (PPL)
Aplicar o método de resolução de PPL, por meio da implementação computacional com suporte do pacote Solver do
Microsoft Excel.
Problema de programação linear
Conforme descrito em Sucena (2019), o Problema de Programação Linear (PPL) é um método analítico empregado para
resolver problemas em que se procura alocar recursos limitados a atividades ou a identi�cação da solução ótima para tomada
de decisões diversas. No PPL, todas as funções de�nidas no modelo matemático que descreve o problema (função objetivo e
restrições do problema) devem ser lineares. A forma padrão de representação matemática do PPL é descrita a seguir:
Min ou Max Z = c .x + c .x + … + c .x
sujeito às restrições:
a .x + a .x + … + a .x = b
a .x + a .x + … + a .x = b
…
a .x + a .x + … + a .x = b
x >= 0, i = 1, 2, …, n
1 1 2 2 n n
11 1 12 2 1n n 1
21 1 22 2 2n n 2
m1 1 m2 2 mn n m
i
Na representação anterior, considere que:
x : variáveis de decisão para j=1,2,...n;
b : quantidade disponível de um determinado recurso para j=1,2,...m;
n: quantidade de variáveis de decisão do modelo de PPL;
m: quantidade de restrições do modelo de PL;
Z: função-objetivo do modelo de PL
a .x + a .x + … + a .x = b → j-ésima restrição (j = 1, …, m)
 
A forma mais comum de resolução do PPL é a solução grá�ca, empregada para casos simples com duas variáveis de decisão.
Veja como empregar a solução grá�ca a partir da resolução do exemplo a seguir, extraído de Sucena (2019). Vamos lá:
j
j
j1 1 j2 2 jn n j
Atenção! Aqui existe uma videoaula, acesso pelo conteúdo online
Exemplo
Determine a solução ótima do PPL
Max Z = 3X + 4X
Sujeito a:
2,5X + X ≤ 20
3X + 3X ≤ 30
X + 2X ≤ 16
X ≥ 0, X ≥ 0
Resolução:
 
1º passo - Represente as restrições no plano cartesiano x-y. Como as restrições deste problema de PL são dadas em forma de
desigualdades, então a solução grá�ca do conjunto de restrições será um polígono convexo (não necessariamente fechado) que
recebe o nome de Região de Soluções Viáveis (R.S.V.). A solução ótima do problema de programação linear será um dos vértices
desse polígono.
 
2º passo - Encontre o ponto ótimo. Começa-se traçando a reta que anula a função-objetivo, ou seja, a reta que passa pela origem
(X1 = 0, X2 = 0 e Z = 0) e que corresponde a Z = 0, representando a situação mais desfavorável; em seguida procura-se o vértice
do polígono pelo qual passa a reta paralela à reta traçada anteriormente, ponto esse que deve ser o mais afastado possível (visto
que o problema é de maximização). As equações de reta que representa Z = 0 e as paralelas que se destinam ao vértice mais
afastado do polígono convexo são também conhecidas como “equações equipotenciais”.
 
3º passo - Aplicando os dois passos anteriores, veri�ca-se que o ponto B apresenta a solução ótima do PPL. As coordenadas
cartesianas do ponto B são x1 = 4 e x2 = 6. Assim, conforme ilustrado na Figura 1, você pode concluir que a solução ótima, dado
que x1 = 4 e x2 = 6, é Z = 3.4 + 4.6 = 36.
 
1 2
1 2
1 2
1 2
1 2
 Figura 1 – Solução do PPL com emprego do método gráfico. (Fonte: SUCENA, 2018).
O problema dual
Atenção! Aqui existe uma videoaula, acesso pelo conteúdo online
Outro aspecto relevante do PPL é a possibilidade de construção do
dito problema dual. Mais do que um mero exercício matemático, o
conceito de dualidade foi uma das mais importantes descobertas no
início do desenvolvimento da Programação Linear, pois permite a
análise de sensibilidade do resultado do sistema a variações nos
valores dos coe�cientes das restrições. Assim, o modelo dual
apresenta informações sobre questões econômicas relevantes em um
PPL.
Neste momento, é importante que você saiba que há um conjunto de relações simples que permitem transformar um
problema original (dito primal) em dual.
1
https://estacio.webaula.com.br/cursos/go0323/aula10.html
Implementação com o pacote Solver – Microsoft Excel
Vamos ver agora um exemplo de resolução do PPL com suporte computacional? Para isto, nós utilizaremos o Solver,
ferramenta de análise de dados disponível no Microsoft Excel.
 
O manual de ajuda da ferramenta apresenta diversas orientações ao usuário, seja para habilitar a ferramenta, seja para modelar
um problema de programação linear e, com isto, obter a solução, caso exista.
 
Como ilustração, vamos resolver novamente o exemplo 1 desta aula, a saber:
Max Z = 3X + 4X
Sujeito a:
2,5X + X ≤ 20
3X + 3X ≤ 30
X + 2X ≤ 16
X ≥ 0, X ≥ 0
A Figura 2 mostra como �ca o modelo inicial deste problema de programação linear no Excel:
 
1 2
1 2
1 2
1 2
1 2
 Figura 2 – Montagem inicial da planilha em Excel para resolução do problema de programação linear indicado no exemplo 1.
Nesta �gura, é interessante perceber que:
Os valores �nais de X1 e X2 estão indicados, respectivamente, em A1 e B1.
Os valores indicados em A2 e B2 são os coe�cientes da função-objetivo. A célula C2, destacada em amarelo na �gura,
representa o valor de Z. Inicialmente, o valor é 0, visto que A1 e B1 (ou seja, X1 e X2) não têm valores inseridos.
Em seguida, vemos os coe�cientes das restrições, a saber:
A3 e B3 representam os coe�cientes da 1ª restrição, enquanto C3 simboliza o produto com os valores presentes de X1 e
X2
A4 e B4 representam os coe�cientes da 2ª restrição, enquanto C4 simboliza o produto com os valores presentes de X1 e
X2
A5 e B5 representam os coe�cientes da 3ª restrição, enquanto C5 simboliza o produto com os valores presentes de X1 e
X2
E3, E4 e E5 indicam os termos independentes das três restrições.
Os símbolos indicados em D3, D4 e D5 aparecem como referência para ajudar o procedimento de inserção no Solver,
ainda a ser executado.
Repare que a coluna C apresenta os produtos dos coe�cientes pelos valores de X1 e X2. Esta soma de produtos pode ser
representada por meio da função SOMARPRODUTO, da seguinte forma:
C2 =SOMARPRODUTO(A1:B1;A2:B2)
C3 = SOMARPRODUTO($A$1:$B$1;A3:B3)
C4 = SOMARPRODUTO($A$1:$B$1;A4:B4)
C5 = SOMARPRODUTO($A$1:$B$1;A5:B5)
Agora que já modelamos o problema de programação linear, é tempo de inserir as informações no Solver. A Figura 3
mostra como �ca o problema ao �nal da inserção na ferramenta:
 
 Figura 3 – Inserção do PPL do exemplo 1 no Solver.
Veja que:
O objetivo é a célula C2;
As variáveis do problema são as células A1 e B1;
As restrições são C3 <= 20, C4 <= 30 e C5 <= 16.
 
As variáveis vêm intercaladas com o sinal $ para simbolizar que se trata de valores a serem alterados ao longo da execução do
problema. Adicionalmente, vemos que o método de solução escolhido foi o LP Simplex, de acordo com o que vimos na primeira
seção desta aula.
 
Assim, clicando-se em Resolver, vemos uma nova tela, apresentada na Figura 4 exposta a seguir:
 
 Figura 4 – Tela de resultados do Solver.
Assim, basta clicar em Resposta, depois em OK, para se ter a solução do PPL.Na Figura 5, vemos que X1 = 4, X2 = 6 e Z = 36,
exatamente como previsto, dado que já tínhamos calculado a solução com apoio do método grá�co no início desta aula.
 Figura 5 – Tela com a solução do PPL (X1 = 4, X2 = 6 e Z = 36).
Atenção! Aqui existe uma videoaula, acesso pelo conteúdo online
Atividade
1. Assinale a única alternativa que apresenta o valor de Z para o problema apresentado a seguir:
Max Z = 3X + 4X
Sujeito a:
2,5X1 + X ≤ 20
3X + 1X ≤ 30
X + 2X ≤ 16
X ≥ 0, X ≥ 0
1 2
1 2
1 2
1 2
1 2
a) 30
b) 32
c) 34
d) 36
e) 38
2. (Petrobras - 2010) Considere o seguinte problema de Programação Linear: Minimize Z = α. X + β. X
Sujeito a:
X ≤ 3
X ≤ 4
X + 2X ≥ 9
X ≥ 0
X ≥ 0
Para quais valores de α e β o problema apresenta soluções múltiplas?
1 2
1
1
1 2
1
2
a) α=2 e β=4
b) α=2 e β=1
c) α=1 e β=1
d) α=2 e β=3
e) α=3 e β=3
3. (Petrobras - 2012).Considere o seguinte problema de programação linear: Maximize: Z = x + 4x
Sujeito a:
2x + 4x ≤20
−x + 2x2 ≤8
x + x ≤5
x ≥0,x ≥0
Veri�ca-se que o valor ótimo da função objetivo é
1 2
1 2
1 2
1 2
1 2
a)0
b) 9
c) 17
d) 18
e) 20
4. (Petrobras - 2011). Considere o seguinte problema de Programação Linear. Min Z = 2x1 − x2
Sujeito a:
−x1 + x2 ≤ 3
2x1 − x2 ≤ 6
x1 ≥ 0, x2 ≥ 0
Qual é a solução ótima?
a) x1 = 0 e x2 = 1
b) x1 = 0 e x2 = 3
c) x1 = 1 e x2 = 0
d) x1 = 1 e x2 = 4
e) x1 = 3 e x2 = 0
5. Assinale a única alternativa que apresenta o valor de Z para o problema apresentado a seguir: Max Z = 3X + 2X
Sujeito a:
X2,5X + X ≤ 20
3X + 1X ≤ 30
X + 2X ≤ 16
X ≥ 0,X ≥ 0
1 2
1 2
1 2
1 2
1 2
a) 30
b) 32
c) 34
d) 36
e) 28
Notas
Conjunto de relações simples 1
As variáveis duais podem ser interpretadas como sendo os preços associados às restrições do problema primal;
A função objetivo do primal deve ser maximizada, enquanto a do dual deve ser minimizada;
As constantes dos segundos membros das restrições do primal são os coe�cientes da função objetivo do dual;
Os coe�cientes da função objetivo do primal são as constantes dos segundos membros do dual;
As restrições do primal são do tipo <=, enquanto que as do dual são do tipo >=;
O número de variáveis do primal é igual ao número de restrições do dual;
O número de variáveis do dual é igual ao número de restrições do primal;
Os coe�cientes dos primeiros membros das restrições do primal formam uma matriz que é transposta da dos
coe�cientes dos primeiros membros das restrições do dual;
O dual do dual é o primal;
A matriz dos coe�cientes do dual é a transposta da matriz dos coe�cientes do primal; e
As variáveis de ambos os problemas são não-negativas.
Referências
SUCENA, M. P., Apostila de Pesquisa Operacional I – CCE 1012 – 2018/2.
Próxima aula
Explore mais
Conheça mais sobre o assunto nos links:
Hijazi, S. Using Solver in Excel (O�ce 365) to solve Linear Programming Problem; .
PHPSimplex;
Simplex Programação Linear.
javascript:void(0);
javascript:void(0);
javascript:void(0);