RESUMO Programção Linear

Prévia do material em texto

RESUMO Programação Linear
Programação Linear (PL) é uma técnica de otimização matemática utilizada para maximizar ou minimizar uma função objetivo, sujeita a um conjunto de restrições lineares. É amplamente utilizada em diversas áreas, como economia, engenharia, logística e administração, para resolver problemas que envolvem a alocação eficiente de recursos limitados.
1. Elementos da Programação Linear
1.1. Função Objetivo
· Representa o objetivo a ser otimizado (maximizado ou minimizado).
· Exemplo: Maximizar o lucro ou minimizar os custos.
· Forma geral: 𝑧=𝑐1𝑥1+𝑐2𝑥2+…+𝑐𝑛𝑥𝑛z=c1​x1​+c2​x2​+…+cn​xn​
1.2. Variáveis de Decisão
· Representam as decisões a serem tomadas.
· Exemplo: Quantidades de produtos a serem fabricados.
· Representadas como 𝑥1,𝑥2,…,𝑥𝑛x1​,x2​,…,xn​.
1.3. Restrições
· Limitações ou condições que devem ser respeitadas.
· Exemplo: Limitações de recursos como tempo, dinheiro, materiais.
· Forma geral: 𝑎11𝑥1+𝑎12𝑥2+…+𝑎1𝑛𝑥𝑛≤𝑏1a11​x1​+a12​x2​+…+a1n​xn​≤b1​
1.4. Condições de Não-Negatividade
· As variáveis de decisão devem ser não-negativas.
· Forma geral: 𝑥𝑖≥0xi​≥0 para todos 𝑖i.
2. Formulação de um Problema de Programação Linear
Vamos considerar um exemplo clássico para ilustrar a formulação de um problema de programação linear.
Exemplo: Problema de Alocação de Recursos
Uma empresa fabrica dois produtos, A e B. O lucro por unidade de A é $40 e o lucro por unidade de B é $30. A empresa possui 100 horas de trabalho e 180 unidades de matéria-prima disponíveis. Cada unidade de A requer 2 horas de trabalho e 3 unidades de matéria-prima, enquanto cada unidade de B requer 1 hora de trabalho e 2 unidades de matéria-prima. O objetivo é maximizar o lucro.
Passos para Formular o Problema:
1. Definir as Variáveis de Decisão:
· 𝑥1x1​: Número de unidades do produto A a serem produzidas.
· 𝑥2x2​: Número de unidades do produto B a serem produzidas.
2. Formular a Função Objetivo:
· Maximizar o lucro 𝑧z.
· Função objetivo: 𝑧=40𝑥1+30𝑥2z=40x1​+30x2​.
3. Estabelecer as Restrições:
· Restrição de horas de trabalho: 2𝑥1+𝑥2≤1002x1​+x2​≤100.
· Restrição de matéria-prima: 3𝑥1+2𝑥2≤1803x1​+2x2​≤180.
4. Incluir Condições de Não-Negatividade:
· 𝑥1≥0x1​≥0.
· 𝑥2≥0x2​≥0.
Modelo Matemático:
Maximizar 𝑧=40𝑥1+30𝑥2Maximizar z=40x1​+30x2​
sujeito a:sujeito a:
2𝑥1+𝑥2≤1002x1​+x2​≤100
3𝑥1+2𝑥2≤1803x1​+2x2​≤180
𝑥1,𝑥2≥0x1​,x2​≥0
3. Método Simplex
O Método Simplex é um algoritmo amplamente utilizado para resolver problemas de programação linear. Ele iterativamente melhora a solução até encontrar a solução ótima. Aqui está um resumo dos principais passos do Método Simplex:
Passos do Método Simplex:
1. Inicialização:
· Encontrar uma solução básica viável (geralmente, o ponto onde todas as variáveis de decisão são zero, exceto as variáveis de folga).
2. Cálculo das Taxas de Substituição (Custos Reduzidos):
· Determinar quanto a função objetivo mudará ao introduzir uma unidade de cada variável não-básica na solução.
3. Seleção da Variável de Entrada:
· Escolher a variável não-básica com o maior custo reduzido positivo para maximizar (ou mais negativo para minimizar).
4. Determinação da Variável de Saída:
· Determinar qual variável básica deve sair da base para manter a viabilidade da solução.
5. Atualização da Solução:
· Atualizar a solução básica viável, substituindo a variável de saída pela variável de entrada.
6. Iteração:
· Repetir os passos 2 a 5 até que não seja possível melhorar a função objetivo, indicando que a solução ótima foi encontrada.
Exemplo Simplificado:
Consideremos um problema de programação linear simplificado com as seguintes restrições e função objetivo:
Maximizar 𝑧=3𝑥1+2𝑥2Maximizar z=3x1​+2x2​
sujeito a:sujeito a:
𝑥1+𝑥2≤4x1​+x2​≤4
2𝑥1+𝑥2≤52x1​+x2​≤5
𝑥1,𝑥2≥0x1​,x2​≥0
Passos do Método Simplex:
1. Inicialização:
· Adicionar variáveis de folga 𝑠1s1​ e 𝑠2s2​ para transformar as desigualdades em igualdades:
𝑥1+𝑥2+𝑠1=4x1​+x2​+s1​=4
2𝑥1+𝑥2+𝑠2=52x1​+x2​+s2​=5
· A solução inicial é 𝑥1=0x1​=0, 𝑥2=0x2​=0, 𝑠1=4s1​=4, 𝑠2=5s2​=5.
2. Tabela Simplex Inicial:
𝑥1𝑥2𝑠1𝑠2Lado DireitoFunc¸a˜o Objetivo−3−2000𝑠111104𝑠221015Func¸​a˜o Objetivos1​s2​​x1​−312​x2​−211​s1​010​s2​001​Lado Direito045​​
3. Iteração:
· Escolher 𝑥1x1​ para entrar na base (maior coeficiente negativo na linha da função objetivo).
· Calcular a razão Lado DireitoCoeficiente de EntradaCoeficiente de EntradaLado Direito​ para determinar qual variável sairá da base:
Para 𝑠1:41=4(menor raza˜o)Para s1​:14​=4(menor raza˜o)
Para 𝑠2:52=2.5Para s2​:25​=2.5
· 𝑠2s2​ sai da base.
4. Atualização:
· Realizar as operações de linha para atualizar a tabela Simplex.
· Continuar iterando até não haver mais coeficientes negativos na linha da função objetivo.
4. Aplicações da Programação Linear
A programação linear é utilizada em diversas áreas para resolver problemas como:
· Planejamento de Produção: Determinar a quantidade de diferentes produtos a serem fabricados para maximizar o lucro ou minimizar os custos, considerando limitações de recursos.
· Transporte e Logística: Otimizar rotas de transporte para minimizar custos ou tempos de entrega.
· Alocação de Recursos: Distribuir recursos limitados entre várias atividades ou projetos de maneira a maximizar o retorno ou minimizar o risco.
· Mix de Marketing: Alocar um orçamento de marketing entre diferentes canais para maximizar o retorno sobre o investimento.
Conclusão
A programação linear é uma poderosa ferramenta de otimização que permite resolver problemas complexos de alocação de recursos de forma eficiente. O Método Simplex é um algoritmo robusto para encontrar soluções ótimas para esses problemas. Juntos, eles fornecem uma base sólida para a tomada de decisões informadas em uma ampla variedade de contextos empresariais e industriais.