MÉTODO DA SOLUÇÃO GRÁFICA em PDF

Prévia do material em texto

PROBLEMA DE PROGRAMAÇÃO LINEAR - PPL 
A tarefa da Programação Linear consiste na maximização ou minimização de uma função 
linear, denominada Função Objetivo, respeitando-se um sistema linear de igualdades ou 
desigualdades que recebem o nome de RESTRIÇÕES do modelo. 
As restrições representam normalmente limitações de recursos disponíveis (capital, mão de 
obra, recursos minerais ou fatores de produção) ou então, exigências e condições que 
devem ser cumpridas no problema. Essas restrições do modelo determinam uma região a 
qual recebe o nome de Conjunto de Soluções Viáveis. 
A melhor das soluções viáveis, isto é, aquela que maximiza ou minimiza a função objetivo 
denomina-se SOLUÇÃO ÓTIMA. O objetivo da programação linear consiste na determinação 
da solução ótima. 
O Problema de Programação Linear será chamado de PPL. 
Dois passos são fundamentalmente necessários para a resolução de um PPL: 
 MODELAGEM do problema 
 MÉTODO de solução do modelo 
Não existem técnicas precisas, capazes de permitir o estabelecimento do modelo de um 
problema. Para consegui-lo, é muito importante fazer uma análise e síntese. 
O seguinte procedimento é normalmente utilizado na formulação de modelos para a solução 
de problemas envolvendo programação linear: 
1. Defina as variáveis de controle ou de decisão 
2. Estabeleça a função objetivo 
3. Estabeleça as restrições do sistema 
A seguir é apresentado um exemplo simples de PPL com a finalidade de deixar claro como 
um problema pode ser formulado e resolvido. 
A Companhia de Produção de Sensores XYZ fabrica dois tipos de sensores: (a) sensor de 
velocidade do vento e (b) sensor de pluviosidade. Existem duas linhas de produção, um para 
cada tipo de sensor. A capacidade de produção da linha de sensor de velocidade do vento é 
de 60 unidades por dia enquanto que a capacidade de produção de sensores de pluviosidade 
é de 50 unidades por dia. O sensor de velocidade do vento requer 1 (um) homem-hora de 
mão-de-obra e o sensor de pluviosidade requer 2 (dois) homens-hora de mão-de-obra. 
Atualmente, existem 120 homens-hora de mão-de-obra disponíveis por dia para ser usado 
na produção desses dois tipos de sensores. Se o lucro é de R$ 20,00 e R$ 30,00 para o sensor 
de velocidade do vento e para o sensor de pluviosidade, respectivamente, qual deve ser a 
produção diária de cada sensor? 
 
 
Resposta: 
Representando o número de sensores de velocidade do vento produzidos diariamente por x₁ 
e o número de sensores de pluviosidade produzidos por x₂, pode-se definir a seguinte 
função objetivo: 
Maximize 20x₁ + 30x₂ 
 
O próximo passo é definir as restrições. Nesse caso, existem dois tipos de restrição: mão-de-
obra e capacidade das linhas de produção. 
 
x₁ ≤ 60 (capacidade de produção da linha de sensores de velocidade do vento) 
x₂ ≤ 50 (capacidade de produção da linha de sensores de pluviosidade) 
x₁ + 2x₂ ≤ 120 (mão-de-obra) 
 
x₁, x₂ ≥ 0 (restrição de não negatividade) 
 
Vamos outro exemplo, apresentado um quadro resumo do problema: 
 
Um pizzaiolo trabalha 8 horas por dia e faz 16 pizzas por hora, caso faça somente pizzas, e 9 
calzones por dia se fizer somente calzones. Ele gasta 40 g de queijo para preparar uma pizza 
e 60 g de queijo para fazer um calzone. Sabendo que o total disponível de queijo é de 5 kg 
por dia, e que a pizza é vendida a R$ 18,00 e o calzone a R$ 22,00, pergunta-se: quantas 
unidades de pizzas e calzones uma pizzaria deve vender diariamente para maximizar a sua 
receita, considerando que ela tem um pizzaiolo? 
 
Variáveis de decisão: 
- x1 = Qtd. de horas que serão utilizadas no preparo das pizzas 
- x2 = Qtd. de horas que serão utilizadas no preparo dos calzones 
 
Parâmetros: 
- Pizza, calzone e queijo. 
 
Restrições: 
- capacidade diária de produção de pizzas e calzones e a quantidade de queijo disponível. 
 
Função Objetivo: 
- Função objetivo a ser maximizada: 
 Zmáx. = 18 x1 + 22 x2 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
MÉTODO DA SOLUÇÃO GRÁFICA 
Os problemas de Pesquisa Operacional, quando esboçam uma relação linear entre as 
variáveis de decisão, são chamados de Problemas de Programação Linear (PPL). 
Dentre as diversas possibilidades de PPL, aqueles que são baseados em apenas 2 (duas) 
variáveis de decisão (x₁ e x₂) podem ser solucionados pelo Método Gráfico. 
Este método caracteriza-se pela busca da Solução Ótima do PPL, dentro de uma Região 
Factível formada pela interseção das retas geradas pelas Inequações das Restrições. 
Como obter a solução gráfica? 
1º Passo: Formulação do problema de Pesquisa Operacional 
Dicas: 
 Quando o problema citar que há um estoque para se utilizar, as restrições são do tipo 
(≤) pois não se pode consumir matéria-prima além do que se tem disponível no 
estoque. São as Restrições de Matéria-Prima; 
 
 Quando o problema citar que há um número existente de máquinas para produção, 
homens para trabalhar, veículos para transportar, dinheiro para investir e similares, as 
restrições são do tipo (≤) pois não se pode utilizar mais máquinas para se produzir, além 
do que se tem. Não pode contar com mais operadores, além do que se tem. Não se pode 
transportar além da capacidade do veículo. Enfim, todas são Restrições de Capacidade 
de Produção; 
 
 Quando o problema citar quantidades necessárias para a produção ser aceitável, as 
restrições são do tipo (≥) pois não se pode utilizar menos do que o exigido. 
2º Passo: Estabelecer os eixos do plano cartesiano xy. 
Para trabalharmos com um padrão, o eixo vertical será a variável x₂ (abscissas) e o eixo 
horizontal será a variável x₁ (ordenadas). 
 
 
 
 
 
 
 
 
3º Passo: Traçar as retas para cada restrição (vamos utilizar um exemplo de restrições já 
obtidas em um processo de formulação de PPL). 
Zmáx. = 3x1 + 3x2 
s.a. 2x₁ + 4x₂ ≤ 12 
 6x₁ + 4x₂ ≤ 24 
 x₁, x₂ ≥ 0 
 
 
 
 
 
 
 
 
 
Calculando x₁ 
2x₁ = 12 
x₁ = 12 / 2 
x₁ = 6 
Calculando x₂ 
4x₂ = 12 
x₂ = 12 / 4 
x₂ = 3 
4º Passo: Esboçar o sentido da solução da inequação. Se for do tipo ≤ , a solução está para 
baixo ou para a esquerda. Se for do tipo ≥ , a solução está para cima ou para a direita. 
 
 
5º Passo: Repetir para todas as inequações. 
 
 
6º Passo: Delimitar a região factível. 
 
 
 
 
 
 
 
Calculando x₁ 
6x₁ = 24 
x₁ = 24 / 6 
x₁ = 4 
Calculando x₂ 
4x₂ = 24 
x₂ = 24 / 4 
x₂ = 6 
7º Passo: Traçar as retas da Função Objetivo. 
 
 
 
 
 
 
8º Passo: Encontrar os pontos ótimos. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
9º Passo: Encontrar a solução do problema (se for maximizar lucro, encontrar o lucro 
máximo, por exemplo).