27Out

• P27/10 Questionário

  ---

• Agenda

  • Introdução à Programação Linear: inicialmente, após uma breve síntese do tipo de problemas que a programação linear pode resolver, faremos referência novamente ao roteiro sugerido para que problemas reais possam ser expressos como modelos de programação linear. Esse roteiro será usado para transformar o enunciado de um problema em um problema de programação linear.  Por resultar num problema envolvendo apenas duas variáveis (incógnitas), esse problema pode ser resolvido graficamente. Usaremos, então, uma planilha Excel para explorar essa solução gráfica.
    
  • Dinâmica:  Vamos assistir a dois vídeos que demonstram a aplicação do roteiro e, agrupados em salas virtuais, iremos trabalhar nos problemas da lista de exercícios do ED09 propostos na aula passada.

  ---

• Solução gráfica de problemas de programação linear (PL) com duas variáveis

  Esta aula mostra como problemas de programação linear envolvendo apenas duas variáveis podem ser resolvidos graficamente. Para isso, utilizaremos uma planilha MS Excel (clique AQUI para fazer o download da planilha).

  Desenhando retas em gráficos do Excel

  Primeiramente, precisamos descobrir como o Excel pode nos ajudar a representar expressões lineares em planos cartesianos. Um plano cartesiano permite expressar funções matemáticas envolvendo duas variáveis. Usaremos recursos simples para expressar funções matemáticas simples. As funções que queremos expressar são simples relações lineares entre duas variáveis. Uma relação entre duas variáveis pode ser expressa matematicamente da seguinte forma:

  \( a Y + b X = c\)

  Talvez você conheça melhor essa expressão se representada de outra forma:

  \( Y = (c/a) - (b/a) X \)

  Repare que essa é a expressão matemática da reta, e revela melhor o caráter linear da relação entre Y e X. Nesse caso, (c/a) é o intercepto da equação de reta, e -(b/a) é o coeficiente angular da equação de reta.

  Para representarmos uma reta em um plano cartesiano, precisamos apenas de dois pontos. Em outras palavras, se dois pontos fazem parte de uma reta basta conhecê-los para determinar os demais pontos que constituem essa reta. Vamos, então, a partir dessa premissa usar o Excel para construir qualquer reta que desejemos. Um ponto no plano cartesiano é identificado por um par de valores denominado par ordenado do tipo (x, y), onde x e y são valores pertencentes aos eixos X e Y, respectivamente. Já que quaisquer dois pontos de uma reta são suficientes para representá-la em um plano cartesiano, vamos considerar dois pares ordenados especiais:

  • Ponto 1: (0, ___)
  • Ponto 2: (___ ,0)

  Exemplo

  Vamos considerar a expressão linear $ 7 Y + 3 X = 210 $, que é equivalente à expressão de reta $ Y = 30 - 0,4 X $. Nesse caso, os dois pares ordenados especiais $(x_i, y_i)$ são $y_i = \frac{c}{a}$ quando $x_i = 0$; e $x_i = \frac{c}{b}$ quando $y_i = 0$, ou seja, $(0, 30)$ para o ponto 1 e $(70, 0)$ para o ponto 2. O Excel pode ser usado para facilmente representar a reta que conecta esses dois pontos:

  
  

  Desenhando a região de viabilidade do problema de PL com duas variáveis

  A região de viabilidade de um problema de programação linear (PL) com apenas duas incógnitas (variáveis) é definida em um plano cartesiano como a área que satisfaz simultaneamente todas as restrições do problema. Por exemplo, digamos que o problema apresente duas restrições, uma expressando um teto ($ 7 Y + 3 X \le 210 $) e outra expressando um piso ($ 10 Y + 20 X \ge 500 $). As retas expressando as restrições podem ser representada no gráfico a partir dos pares ordenados $y_i = \frac{c}{a}$ quando $x_i = 0$; e $x_i = \frac{c}{b}$ quando $y_i = 0$. No caso da restrição "piso" o ponto 1 seria $(0, 50)$ e o ponto 2 seria $(25, 0)$.  O resultado de considerar simultaneamente as duas restrições, uma impondo um teto e outra impondo um piso, limita o conjunto de valores viáveis para X e Y (região cinza no gráfico abaixo).

  
  

  Vamos supor que a região de viabilidade tenha agora que considerar também um piso para a variável Y, por exemplo ($ Y \ge 10 $). A reta expressando o novo piso pode ser graficamente representada pelos pares ordenados $(0, 10)$ e por um segundo ponto $(70, 10)$ que, nesse caso, define um fim para a reta quando $X = 70$.

  
  

  Encontrando uma solução para o problema de PL com duas variáveis

  A solução do problema de PL precisa agora considerar a função objetivo. Digamos que a função objetivo seja Maximizar $Y + 4 X = Z$. Isto é, queremos determinar os valores de Y e X que maximizam o valor de Z. Para encontrarmos a solução no gráfico, vamos primeiramente tentar expressar a reta que representa a função objetivo. Acontece que, enquanto $Z$ puder assumir qualquer valor, são infinitas as retas que poderíamos considerar. Vamos, então escolher um valor qualquer, por exemplo $Z = 40$. Nesse caso, poderíamos usar os pontos $(0,40)$ e $(10, 0)$ para expressar a reta $Y + 4 X = 40$.
  

  

  Reparem que, conforme aumentamos o valor de Z, a reta representando a função objetivo se desloca para a direita. Se considerarmos o deslocamento dessa reta para a direita (maximização de Z) que respeita a região de soluções viáveis (definidas pelas restrições), veremos que apenas um ponto satisfaz simultaneamente o objetivo de deslocar ao máximo a reta para a direita (maximizar Z) e atender as restrições. Esse ponto aparece identificado no gráfico abaixo.
  

  

  ---

• Aplicando o roteiro de apoio à formulação de problemas de programação linear

  Passo-a-passo para expressar o problema de refeição de custo mínimo como um problema de PL
  Resolvendo no Excel o problema da refeição de custo mínimo

  Reúna-se com os seus colegas numa das salas virtuais de estudo listadas abaixo, e aplique o roteiro ao problema da lista designado à sua sala.

  Sala 1 Problema 3	Sala 2 Problema 4	Sala 3 Problema 5

  ---