Teoria de Decisão I

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

Profa. Luciane Alcoforado

PPGEC/UFF

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- O que é uma variável de decisão do modelo de programação linear?

São os elementos do sistema cujo controle você tem e seus valores são números reais positivo.
São as incógnitas do modelo e seus valores são números reais, em geral positivos.
São os elementos do sistema cujo controle você não tem e seus valores são números reais negativos.
São os parâmetros do modelo, cujos valores são fixos e conhecidos.
São os elementos do sistema cujo controle você tem e seus valores são números imaginários.

Escolha a alternativa correta

2- Como deve ser definida uma variável de decisão?

Variáveis de decisão são definidas como sendo os dados do problema.
Variáveis de decisão são definidas como sendo os limites de recursos em cada restrição do modelo.
Variáveis de decisão são designadas por letras gregas como $\mu$ e $\sigma$ que representam a média e o desvio-padrão dos dados do problema.
Variáveis de decisão são definidas de forma abstrata, seus valores podem variar de 1 a n.
As variáveis de decisão compõem tanto a função objetivo como as restrições e são em geral designadas por letras como x, y, z, etc., ou por uma letra indexada como x1, x2, etc.

Verifique seus acertos

1- O que é uma variável de decisão do modelo de programação linear?

São as incógnitas do modelo e seus valores são números reais, em geral positivos.

2- Como deve ser definida uma variável de decisão?

As variáveis de decisão compõem tanto a função objetivo como as restrições e são em geral designadas por letras como x, y, z, etc., ou por uma letra indexada como x1, x2, etc.

Responda

3- O que é uma solução factível/viável de um problema de programação linear?

4- O que é uma solução ótima de um problema de programação linear?

5- Qual a diferença entre solução viável e solução factível? E entre solução factível e solução ótima?

Resposta esperada

3- O que é uma solução factível/viável de um problema de programação linear?

Solução possível para o sistema de restrições do modelo, é aquela que atende a todas as restrições ao mesmo tempo.

4- O que é uma solução ótima de um problema de programação linear?

É a melhor solução dentre as soluções factíveis para o modelo.

5- Qual a diferença entre solução viável e solução factível? E entre solução factível e solução ótima?

Solução viável e factível são sinônimos. Uma solução ótima é uma solução factível que fornece o melhor valor possível para a função objetivo do problema. A diferença entre solução factível e ótima é que a ótima é a melhor solução dentre todas as soluções factíveis.

O que é uma representação gráfica de um problema de programação linear?

É uma maneira de visualizar a solução ótima de um problema de programação linear em um gráfico cartesiano em duas dimensões (plano xy).

Para problemas que apresentam duas variáveis de decisão, a solução ótima pode ser encontrada graficamente. Isso permite que se encontre a solução ótima do problema de forma mais intuitiva e visual.

Como encontrar a solução ótima utilizando o método gráfico?

É possível para problemas com duas variáveis de decisão.

Isso envolve representar as restrições do problema como retas em um gráfico cartesiano e identificar a região viável, que é o conjunto de pontos que satisfazem todas as restrições.

A solução ótima é então encontrada como um ponto na região viável que fornece o melhor valor para a função objetivo.

Representando restrições

Os problemas possuem 3 tipos possíveis de restrições:

1- $2x-4y \leq 10$

2- $2x-4y \geq 10$

3- $2x-4y = 10$

Em todos os casos a igualdade está presente, por isso graficamente cada restrição é decomposta em uma reta que divide a região do plano em Região Viável (TRUE) e Região Não Viável (FALSE).

Representando duas restrições

R1- $2x-4y \leq 10$

R2- $3x+y \leq 30$

Obtendo uma solução viável

Qualquer ponto da região viável é uma solução para o problema. Por exemplo o ponto x=5 e y=10 é uma solução possível pois atende as duas restrições ao mesmo tempo:

R1- $2\cdot5-4\cdot10 = -30 \leq 10$

R2- $3\cdot5+1\cdot10 = 25\leq 30$

Conceitos para obter a solução ótima

Suponha que a função objetivo do problema seja:

$max \space z=5x+3y$

Graficamente percebemos infinitos pontos possíveis como solução das restrições (Área azul). Mas agora precisamos obter o ponto que fornece o melhor valor para a função objetivo.

Por exemplo, considere os pontos viáveis P1=(5,10) e P2=(9,3). Qual deles apresenta a melhor solução?

Resposta

$max \space z=5x+3y$

sujeito a:

$2x-4y \leq 10$

$3x+y \leq 30$

$x,y\geq0$

Considerando P1=(5,10) e P2=(9,3), obtemos

$z(P1)=5\cdot5+3\cdot10=55$

$z(P2)=5\cdot9+3\cdot3=54$

Portanto podemos concluir que o ponto P1 é melhor que o ponto P2 para a função objetivo do problema. Ainda não podemos garantir que é a solução ótima.

Como representar a função objetivo graficamente?

A função objetivo fornece o vetor gradiente que é formado pelos coeficientes desta função. No exemplo anterior o vetor gradiente = $(5,3)$ uma vez que a função objetivo é dada por $max \space z=5x+3y$

O vetor gradiente fornece a direção de crescimento/decrescimento da função objetivo. No sentido do gradiente a função objetivo aumenta de valor; no sentido contrário diminui.

Curvas de nível x solução ótima

As curvas de nível estão representadas em linhas pontilhadas, são perpendiculares ao vetor gradiente, todos os pontos sobre cada curva de nível corresponde ao mesmo valor da função objetivo $z = 5x+3y$. Por exemplo, os pontos (5,5) e (2,10) fornecem o mesmo valor $z=5\cdot5+3\cdot5 = 5\cdot2+3\cdot10=40$, portanto estão sobre a curva de nível $z=40$. Os pontos (9,3) e (5,10) estão sobre a curva $z=53$ e $z=54$ respectivamente.

Ampliando a visão do gráfico

Solução Ótima

Considerando o sentido de crescimento da função objetivo, considerando as curvas de nível e a região viável do problema, concluímos que o ponto ótimo encontra-se em (0,30) pois é o ponto que intercepta a curva de nível de maior valor na região viável. Neste ponto a curva de nível tem valor de $z=90$ pois $5\cdot0+3\cdot30=90$

Procedimento para solução gráfica

1- Verificar se o problema tem apenas duas variáveis de decisão. Se tiver mais do que duas, o método gráfico não pode ser aplicado.

2- Desenhar um sistema de coordenadas cartesianas com os eixos representando as variáveis de decisão.

3- Representar graficamente cada restrição como uma reta no plano cartesiano, usando as inequações para identificar a região do plano que satisfaz cada restrição.

4- Identificar a região viável do problema que é a região delimitada pelas retas e pontos que satisfazem todas as restrições ao mesmo tempo.

5- Representar graficamente a função objetivo como um vetor gradiente que aponta a direção de crescimento/decrescimento da função. A solução ótima do problema é o ponto da região viável que maximiza ou minimiza a função objetivo. Para encontrar esse ponto, deve-se mover as curvas de nível paralelamente a si mesma até atingir o último ponto da região viável na direção do critério de otimalidade.

Exercício

Observe o gráfico e as restrições. Identifique a região viável.

Resposta

Região Viável é formada pelo polígono ABCD tal que

$A=(10,0), B=(10,12), C=(15,15), D=(25,15)$

Para certificar-se que marcou corretamente a região viável, escolha qualquer ponto desta região e verifique se satisfaz todas as restrições ao mesmo tempo.

Exercício

Observe o gráfico e as restrições. Identifique a região viável.

Resposta

A região viável é um conjunto vazio. Este é um exemplo em que o problema não apresenta nenhuma solução possível.

Exercício

Observe o gráfico e as restrições. Identifique a região viável.

Resposta

Região viável é formada pelo polígono ABC, tal que

$A=(10,5), B=(9.5,7), C=(10, 6.67)$

Exercício

Considere a variável de decisão $x_i$ = número de aeronaves do tipo $i$ a serem adquiridas, $i=1,2$. A função objetivo é $min \space z=10x_1+8x_2$ que representa a minimização do custo total de aquisição em R$

Identifique no gráfico a solução ótima e apresente-a no contexto.

Resposta

Para minimizar o custo total de aquisição devem ser adquiridas somente aeronaves do tipo 2 num quantitativo de 50 unidades e o custo mínimo de aquisição será de R$400,00.

O que acontece se for acrescentado uma restrição de que a aquisição das aeronaves do tipo 1 devem ser adquiridas em pelo menos 25 unidades?

Gráfico considerando nova restrição

$z=10\cdot25+8\cdot25=$ 450

Escolha a alternativa correta

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

O vetor gradiente é formado pelos coeficientes da função objetivo do modelo.
O sentido do vetor gradiente aponta sempre para o crescimento da função objetivo.
Um problema de otimização linear pode não ter solução possível.
Uma solução viável é sempre uma solução ótima para o problema.
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

O vetor gradiente é formado pelos coeficientes da função objetivo do modelo. (V)
O sentido do vetor gradiente aponta sempre para o crescimento da função objetivo. (V)
Um problema de otimização linear pode não ter solução possível. (V)
Uma solução viável é sempre uma solução ótima para o problema. (F)
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.