Ao final desta aula, você deverá ser capaz de:
Ideia central: transformar uma situação de decisão em matemática para comparar alternativas e escolher a melhor delas.
A programação linear é uma técnica para tomar decisões quando:
Linear significa que as variáveis aparecem apenas multiplicadas por constantes e somadas. Por exemplo:
\[ 40x + 30y \]
é linear; já \(xy\), \(x^2\) e \(\sqrt{x}\) não são expressões lineares.
Todo modelo introdutório de programação linear costuma ter quatro partes:
| Parte | Pergunta-guia |
|---|---|
| Variáveis de decisão | O que precisamos decidir? |
| Função objetivo | O que queremos maximizar ou minimizar? |
| Restrições | O que limita nossas decisões? |
| Não negatividade | Faz sentido produzir ou escolher quantidades negativas? |
Dica: antes de escrever qualquer equação, descreva em palavras o que está sendo decidido.
Uma fábrica produz dois itens:
Cada unidade consome recursos:
| Recurso disponível | Produto A | Produto B |
|---|---|---|
| Horas de acabamento | 2 | 1 |
| Quilos de matéria-prima | 1 | 2 |
| Disponibilidade | 40 | 50 |
Pergunta: quantas unidades de A e B devemos produzir para obter o maior lucro possível?
Definimos:
\[ \begin{aligned} x &= \text{quantidade produzida do Produto A} \\ y &= \text{quantidade produzida do Produto B} \end{aligned} \]
Observe que:
Regra prática: normalmente, cada variável de decisão responde a “quanto de quê?” ou “quantas unidades de qual atividade?”.
O lucro total é:
Logo, queremos maximizar:
\[ \boxed{\text{Maximizar } Z = 40x + 30y} \]
onde \(Z\) representa o lucro total, em reais.
A função objetivo não é uma restrição. Ela indica o que queremos melhorar: lucro, receita, produção, custo, tempo etc.
Cada unidade de A usa 2 horas e cada unidade de B usa 1 hora.
Como há somente 40 horas disponíveis:
\[ \boxed{2x + y \leq 40} \]
Leitura em palavras:
horas usadas por A + horas usadas por B não podem ultrapassar 40.
O símbolo \(\leq\) aparece porque se trata de um recurso com limite máximo: podemos usar até 40 horas, mas não mais do que isso.
Cada unidade de A usa 1 kg e cada unidade de B usa 2 kg.
Como há 50 kg disponíveis:
\[ \boxed{x + 2y \leq 50} \]
Leitura em palavras:
matéria-prima usada por A + matéria-prima usada por B não pode ultrapassar 50 kg.
Para montar uma restrição, multiplique o consumo por unidade pela quantidade produzida e compare com a disponibilidade.
Não faz sentido produzir uma quantidade negativa de um produto:
\[ \boxed{x \geq 0, \qquad y \geq 0} \]
Essas condições são chamadas de restrições de não negatividade.
O modelo completo fica:
\[ \begin{aligned} \text{Maximizar } & Z = 40x + 30y \\ \text{sujeito a } & 2x + y \leq 40 \\ & x + 2y \leq 50 \\ & x \geq 0,\; y \geq 0 \end{aligned} \]
Uma solução possível é um par \((x,y)\).
Por exemplo, \((10,20)\) significa:
Verificação:
\[ 2(10)+20 = 40 \quad \text{horas} \]
\[ 10+2(20) = 50 \quad \text{kg} \]
Logo, essa solução usa exatamente os dois recursos e é factível (ou viável).
A região factível reúne todos os pontos que satisfazem simultaneamente:
\[ 2x+y\leq40,\quad x+2y\leq50,\quad x\geq0,\quad y\geq0. \]
O gráfico abaixo ajuda a visualizar as combinações possíveis.
Em um problema de programação linear, quando existe uma solução ótima, ela pode ser encontrada em um vértice da região factível.
Vértices do exemplo:
| Vértice | Interpretação | Lucro |
|---|---|---|
| \((0,0)\) | Nada produzido | R$ 0 |
| \((20,0)\) | Somente A | R$ 800 |
| \((10,20)\) | A e B | R$ 1.000 |
| \((0,25)\) | Somente B | R$ 750 |
Comparando os lucros, a melhor decisão é:
\[ \boxed{x=10,\qquad y=20,\qquad Z=\text{R\$ 1.000}} \]
No ponto de interseção, as duas restrições de recursos ficam ativas:
\[ \begin{cases} 2x+y=40\\ x+2y=50 \end{cases} \]
Da primeira equação:
\[ y=40-2x. \]
Substituindo na segunda:
\[ x+2(40-2x)=50 \Rightarrow -3x=-30 \Rightarrow x=10. \]
Então:
\[ y=40-2(10)=20. \]
“Restrição ativa” significa que o recurso foi totalmente utilizado: aparece uma igualdade no ponto considerado.
A solução ótima \((10,20)\) diz que a fábrica deve:
Uma boa solução matemática precisa ser traduzida de volta para a linguagem do problema.
Sempre faça três perguntas: a solução é possível? O valor do objetivo está correto? A resposta faz sentido para a operação?
Uma escola prepara uma mistura com dois alimentos:
A mistura deve fornecer pelo menos 24 unidades de energia e 24 de proteína, com custo mínimo. Os custos são R$ 2 e R$ 3 por porção.
Defina:
\[ x=\text{porções do alimento A},\qquad y=\text{porções do alimento B}. \]
Modelo:
\[ \begin{aligned} \text{Minimizar } & C=2x+3y\\ \text{sujeito a } & 3x+2y\geq24\\ & 2x+4y\geq24\\ & x,y\geq0. \end{aligned} \]
Atenção: “pelo menos” gera \(\geq\), enquanto “no máximo” gera \(\leq\).
Uma organização pode comprar dois tipos de anúncio:
Ela precisa alcançar pelo menos 12.000 pessoas e pode gastar no máximo R$ 2.000.
Variáveis:
\[ x=\text{número de anúncios digitais},\qquad y=\text{número de anúncios locais}. \]
Se o objetivo for minimizar o custo:
\[ \begin{aligned} \text{Minimizar } & C=200x+100y\\ \text{sujeito a } & 1000x+600y\geq12000\\ & 200x+100y\leq2000\\ & x,y\geq0. \end{aligned} \]
O mesmo raciocínio aparece em produção, alimentação, publicidade, transporte e alocação de pessoas.
Considere novamente a fábrica. Dependendo da pergunta, o modelo pode mudar:
Maximizar lucro:
\[ \text{Max } Z=40x+30y \]
Maximizar receita, se os preços forem R$ 70 e R$ 50:
\[ \text{Max } R=70x+50y \]
Minimizar horas ociosas:
\[ \text{Min } O=40-(2x+y) \]
As restrições descrevem o que é possível. A função objetivo define o que é desejável.
Uma padaria produz bolos e tortas.
Defina as variáveis e escreva o modelo de maximização do lucro.
Pense: quais são as duas decisões? Qual recurso gera a primeira restrição? O que significa “no máximo 10 bolos”?
Defina:
\[ x=\text{número de bolos},\qquad y=\text{número de tortas}. \]
Modelo:
\[ \begin{aligned} \text{Maximizar } & Z=20x+30y\\ \text{sujeito a } & 2x+3y\leq24\\ & x\leq10\\ & x\geq0,\;y\geq0. \end{aligned} \]
Observe que não há limite explícito para o número de tortas além das horas disponíveis e da não negatividade.
Antes de considerar o modelo pronto, confira:
A estrutura básica é:
\[ \boxed{\text{Decisões} \longrightarrow \text{Objetivo} + \text{Limitações} + \text{Não negatividade}} \]
No exemplo da fábrica:
\[ \begin{aligned} \text{Max } & 40x+30y\\ \text{s.a. } & 2x+y\leq40\\ &x+2y\leq50\\ &x,y\geq0. \end{aligned} \]
Na próxima etapa, podemos usar métodos gráficos e ferramentas computacionais para resolver modelos maiores.
Mensagem principal: uma boa modelagem começa com uma boa leitura do problema.