Tema: Programação Linear
a) Estratégia para transformar um problema do mundo real em um modelo linear
viável;
Transformar um problema do mundo real em um modelo linear viável é um processo
fundamental na pesquisa operacional e na optimização. Esse processo exige uma
abordagem estruturada, que inclui a formulação adequada do problema, identificação de
variáveis de decisão, definição de restrições e função objectivo.
1. Compreensão do problema
O primeiro passo é entender completamente o problema a ser resolvido. Isso envolve a
colecta de informações relevantes, definição dos objectivos e identificação de todos os
recursos e limitações envolvidos. A clareza nessa etapa é crucial, pois garante que o
modelo represente fielmente a situação real.
Segundo Hillier e Lieberman (2010), a modelagem matemática é eficaz apenas quando
há uma compreensão clara dos elementos do problema e dos objectivos que se deseja
alcançar.
2. Definição das variáveis de decisão
As variáveis de decisão representam os elementos que podem ser controlados ou
ajustados para atingir o objectivo do problema. Elas devem ser quantitativas e passíveis
de mensuração.
"As variáveis de decisão são o cerne do modelo de programação linear, pois definem as
escolhas disponíveis ao tomador de decisão" (Winston, 2004, p. 35).
3. Formulação da função objectivo
A função objectivo expressa o que se deseja maximizar ou minimizar (por exemplo,
lucro, custo, tempo). Deve ser expressa como uma função linear das variáveis de
decisão.
De acordo com Taha (2011), a função objectivo é uma expressão matemática que traduz
o objectivo do problema e orienta a busca pela solução óptima.
4. Identificação das restrições
As restrições representam as limitações do problema, como recursos disponíveis,
capacidades operacionais, exigências legais, entre outros. Assim como a função
objectivo, devem ser formuladas como expressões lineares.
Para Hillier e Lieberman (2010), as restrições delimitam o espaço de soluções viáveis,
garantindo que apenas soluções factíveis sejam consideradas.
5. Verificação da linearidade
É necessário garantir que tanto a função objectivo quanto as restrições sejam lineares,
ou seja, que não envolvam produtos entre variáveis, potências, funções não lineares etc.
"Modelos de programação linear exigem que as relações entre variáveis sejam lineares
para garantir a aplicabilidade dos algoritmos de solução" (Winston, 2004, p. 42).
6. Construção do modelo matemático
Com todos os elementos definidos, elabora-se o modelo formal:
Definir as variáveis;
Especificar a função objectivo;
Listar as restrições;
Incluir as condições de não negatividade.
Exemplo genérico:
Sejam:
quantidade a ser produzida do Produto 1
: quantidade a ser produzida do Produto 2
Função Objectivo
Suponha que o objectivo seja maximizar o lucro total, e que:
O lucro por unidade do Produto 1 é
O lucro por unidade do Produto 2 é
A função objectiva será:
Maximizar
Sujeito a:
b) Limitações da programação linear quando aplicada a sistemas reais;
A programação linear (PL) é uma poderosa ferramenta de optimização, mas quando
aplicada a sistemas reais, ela apresenta algumas limitações importantes, principalmente
devido às simplificações necessárias para transformar problemas complexos em
modelos matemáticos tratáveis.
1. Suposição de Linearidade
A principal limitação da programação linear é a suposição de que todas as relações no
sistema são lineares, tanto na função objectivo quanto nas restrições.
Segundo Taha (2011), "nem todos os problemas do mundo real seguem relações lineares;
muitas vezes, as variáveis se relacionam de forma não linear, o que torna a PL inadequada
ou imprecisa" (p. 183).
2. Dados Precisos e Determinísticos
Modelos de PL assumem que todos os dados de entrada são conhecidos e certos (por
exemplo, custos, lucros, coeficientes técnicos). No entanto, no mundo real, esses dados
costumam ser incertos ou variáveis.
Hillier e Lieberman (2010) destacam que a PL "ignora a incerteza, sendo mais adequada
para ambientes determinísticos, o que pode comprometer a validade do modelo em cenários
voláteis" (p. 67).
3. Restrições de Inteireza
A PL tradicional não considera que algumas variáveis precisam assumir apenas valores
inteiros (como número de pessoas, caminhões, máquinas). Isso pode gerar soluções
inviáveis na prática.
Como aponta Winston (2004), "a ausência de restrições de inteireza pode levar a soluções
matematicamente corretas, mas logicamente inviáveis" (p. 91).
4. Simplicidade Excessiva dos Modelos
Para tornar o problema tratável, é comum fazer simplificações significativas, como ignorar
certos factores ou interacções. Isso pode comprometer a fidelidade do modelo à realidade.
Taha (2011) observa que "há um trade-off entre a complexidade do modelo e sua utilidade
prática; modelos muito simples podem não capturar a essência do problema real" (p. 189).
5. Foco em uma Única Função Objectivo
Modelos de PL normalmente envolvem a maximização ou minimização de uma única
função objectivo, mas muitos problemas reais envolvem múltiplos objectivos
conflituantes (por exemplo, custo vs. qualidade vs. tempo).
Hillier e Lieberman (2010) sugerem que, nesses casos, é necessário recorrer à
programação multiobjetivo, pois a PL padrão não contempla múltiplos critérios de
decisão (p. 215).
6. Incapacidade de Modelar Comportamentos Dinâmicos
A PL é geralmente estática, ou seja, não leva em consideração mudanças ao longo do
tempo, como variações na demanda, produção, ou disponibilidade de recursos.
Winston (2004) afirma que "a programação linear tradicional é ineficiente para problemas
dinâmicos ou que envolvem múltiplos períodos, sendo necessário recorrer a modelos mais
sofisticados" (p. 134).
c) Comparação entre o método simplex e o método gráfico de resolução de
problemas de programação linear, suas vantagens e desvantagens.
A programação linear (PL) pode ser resolvida por diferentes métodos, entre os quais
se destacam o método gráfico e o método simplex. A escolha entre eles depende
principalmente da dimensão do problema, ou seja, da quantidade de variáveis de
decisão envolvidas. Abaixo, apresento uma comparação detalhada entre os dois
métodos, destacando suas vantagens e desvantagens.
1. Método Gráfico
Vantagens:
Visual e didáctico: Permite visualizar o espaço de soluções viáveis e a interação
entre restrições e a função objectivo.
Ideal para iniciantes: Óptimo para o ensino de conceitos básicos de PL, pois
mostra graficamente como a solução óptima é encontrada.
Clareza conceitual: Facilita o entendimento de restrições, regiões factíveis e
pontos óptimos.
Desvantagens:
Limitado a dois (ou no máximo três) variáveis de decisão: Só é aplicável quando
o problema envolve duas variáveis (gráfico 2D) ou, com dificuldade, três
variáveis (gráfico 3D).
Impraticável para problemas reais: A maioria dos problemas reais envolve
múltiplas variáveis e restrições, o que inviabiliza o uso desse método.
Pouco preciso em cálculos complexos: Pode haver imprecisão na determinação
gráfica de soluções exactas.
Segundo Taha (2011), o método gráfico é útil apenas para "problemas simples e
didácticos", sendo inviável para aplicações com mais de duas variáveis (p. 84).
2. Método Simplex
Vantagens:
Capacidade para múltiplas variáveis e restrições: O método simplex pode
lidar com centenas ou milhares de variáveis, sendo adequado para problemas
industriais, logísticos e financeiros.
Algoritmo sistemático e preciso: Garante a localização da solução óptima, se
ela existir, e é amplamente testado e confiável.
Base para softwares e sistemas computacionais: É o método implementado
em diversos programas de optimização (como LINDO, Excel Solver, CPLEX).
Desvantagens:
Mais complexo conceitualmente: Requer conhecimento de álgebra matricial e
técnicas de iteração, o que dificulta seu uso por iniciantes.
Menor apelo visual: Ao contrário do método gráfico, não oferece uma
representação visual direta do problema.
Demanda computacional em casos grandes: Apesar de eficiente, em alguns
casos específicos pode ter tempo de processamento elevado, exigindo
adaptações ou métodos alternativos (como o método interior-point).
Hillier e Lieberman (2010) afirmam que o método simplex "é extremamente eficiente
na prática, mesmo para problemas de grande porte" (p. 251), mas requer um bom
entendimento matemático para sua aplicação manual.
Referencias Bibliográficas
Hillier, F. S., & Lieberman, G. J. (2010). Introdução à pesquisa operacional (9ª ed.).
McGraw-Hill.
Taha, H. A. (2011). Pesquisa operacional: Uma introdução (9ª ed.). Pearson.
Winston, W. L. (2004). Pesquisa operacional: Aplicações e algoritmos (4ª ed.).
Duxbury Press.