Pesquisa Operacional - PEOP

AULA 18: Solução Gráfica - Problemas com duas variáveis

Profa. Luciane Alcoforado / Profa. Renata

Academia da Força Aérea

Objetivos

Verifique ao final desta aula se você é capaz de:

1- Elaborar gráficos para modelos de programação linear (Ap); 2- Determinar a solução ótima por meio dos gráficos elaborados (Ap);

Roteiro da Aula

  • Revisão de conceitos das aulas anteriores
  • Modelo e sua representação gráfica.
  • Obtendo a solução por meio do gráfico.
  • Exercícios.

Revisão de conceitos

Escolha a alternativa correta

1- Analise cada afirmativa e verifique se é Verdadeira ou Falsa

  1. O vetor gradiente é formado pelos coeficientes da função objetivo do modelo.

  2. O sentido do vetor gradiente aponta sempre para o crescimento da função objetivo.

  3. Um problema de otimização linear pode não ter solução possível.

  4. Uma solução viável é sempre uma solução ótima para o problema.

  5. O método gráfico só pode ser aplicado para obter a solução de um problema com no máximo duas variáveis de decisão.

Confira sua resposta

1- Analise cada afirmativa e verifique se é Verdadeira ou Falsa

  1. O vetor gradiente é formado pelos coeficientes da função objetivo do modelo. (V)

  2. O sentido do vetor gradiente aponta sempre para o crescimento da função objetivo. (V)

  3. Um problema de otimização linear pode não ter solução possível. (V)

  4. Uma solução viável é sempre uma solução ótima para o problema. (F)

  5. O método gráfico só pode ser aplicado para obter a solução de um problema com no máximo duas variáveis de decisão. (V)

Responda

2- Qual a solução ótima com base no gráfico:

Resposta

A região viável é formada pelo polígono ABC, tal que \(A=(0.64,1.73), B=(0.8,2), C=(1,2)\). Considerando o sentido do gradiente e as curvas de nível em amarelo pontilhado, concluímos que a solução ótima é:

\(x1=0.64, x2=1.73\) e o valor ótimo é \(z=3\cdot0.64+4\cdot1.73=\) 8.84

Obtendo a solução com R

No pacote gMOIP as restrições devem ser todas do tipo \(\le\)

#install.packages(gMOIP)
require(gMOIP)
A <- matrix(c(-5,3,3,-4,0,1), ncol = 2, byrow = TRUE)
b <- c(2,-5,2)
obj <- c(3, 4)  # coefficients c

grafico <- plotPolytope(
   A,
   b,
   obj,
   type = rep("c", ncol(A)),
   crit = "min",
   faces = rep("c", ncol(A)),
   plotFaces = TRUE,
   plotFeasible = TRUE,
   plotOptimum = TRUE,
   labels = "coord"
) + ggplot2::xlab("x") + ggplot2::ylab("y") + ggplot2::ggtitle("Solução mínima")+ggplot2::annotate(
    "text", label = "Min z=3x+4y",
    x = 1, y = 1.8, size = 4, colour = "red"
  )
grafico

Obtendo a solução com R

Represente no plano cartesiano as restrições do modelo

Min\(z=x_1 - 8x_2\)

Sujeito a:

\(x_1+x_2\geq5\)

\(-x_1+x_2\leq0\)

\(6x_1+2x_2\leq21\)

\(x_1,x_2\ge0\)

Resposta

As restrições estão delimitadas pelas retas. A região viável atende todas as restrições ao mesmo tempo. Região Viável: \(A=(2.75,2.25), B=(2.5,2.5), C=(2.63,2.63)\)

Obtendo a solução com R

No pacote gMOIP as restrições devem ser todas do tipo \(\le\)

#install.packages(gMOIP)
require(gMOIP)
A <- matrix(c(-1,-1,-1,1,6,2), ncol = 2, byrow = TRUE)
b <- c(-5,0,21)
obj <- c(1, -8)  # coefficients c

grafico <- plotPolytope(
   A,
   b,
   obj,
   type = rep("c", ncol(A)),
   crit = "min",
   faces = rep("c", ncol(A)),
   plotFaces = TRUE,
   plotFeasible = TRUE,
   plotOptimum = TRUE,
   labels = "coord"
) + ggplot2::xlab("x") + ggplot2::ylab("y") + ggplot2::ggtitle("Solução mínima")+ggplot2::annotate(
    "text", label = "Min z=1x-8y",
    x = 1.5, y = 2.8, size = 4, colour = "red"
  )
grafico

Obtendo a solução com R

Resultado Importante para todos os problemas

Se um problema de otimização linear tem uma solução ótima, então existe pelo menos um vértice ótimo.

Observe este exemplo: um vértice é ótimo mas não é único, verifique!

Possibilidades

Um problema pode ter:

  • Uma única solução

  • Infinitas soluções

  • Não ter solução

  • Ter soluções viáveis mas não ter solução ótima (região ilimitada)

Exercício

Um dos problemas abaixo possui uma região ilimitada e não possui solução ótima. Identifique qual deles corresponde a esta situação. Em ambos os casos apresente uma solução viável se houver.

max\(z=2x+3y\)

Sujeito a:

\(x+2y\ge8\)

\(-2x+3y\le12\)

\(x,y\ge0\)

min\(z=2x+3y\)

Sujeito a:

\(x+2y\ge8\)

\(-2x+3y\le12\)

\(x,y\ge0\)

Resposta

O problema 1 de maximização não possui solução ótima pois sua região é ilimitada no sentido de crescimento do gradiente. Portanto qualquer ponto da região viável ilimitada fornece uma solução possível, por exemplo \(x=10, y=5, z=35\) ou \(x=10, y=6, z=38\), etc.

Já o problema 2 de minimização possui solução ótima pois apesar da região ser ilimitada, o sentido de decrescimento é o oposto da região ilimitada. Portanto o ponto ótimo é \(x=0, y=4, z=12\)

Verifique se o problema possui solução

min\(z=2x+3y\)

Sujeito a:

\(x+2y\ge8\)

\(-2x+3y\le12\)

\(x+y\ge2\)

\(x,y\ge0\)

A região viável está pintada de verde.

Resposta

É uma região ilimitada. Neste caso devemos verificar o sentido do vetor gradiente. Como o problema é de minimização e o vetor aponta para (2,3) podemos afirmar que o problema tem uma solução ótima.

Verifique se o problema possui solução

min\(z=2x+3y\)

Sujeito a:

\(x+2y\ge8\)

\(-2x+3y\le12\)

\(x+y\le2\)

\(x,y\ge0\)

Resposta

A região viável é nula, as restrições são incompatíveis. Portanto o problema não tem solução.

Revise

  • Terminou? Revise os conceitos desta aula. Utilize seu caderno para fazer manualmente os gráficos apresentados.

  • Verifique se permanece alguma dúvida sobre a construção do gráfico.

  • Faça os exercícios propostos no moodle.

  • Utilize o pacote gMOIP para visualizar as soluções.

https://rpubs.com/LucianeA/Aula18_PEOP