RESUMO Modelos Lineares e o Método Simplex

Prévia do material em texto

RESUMO Modelos Lineares e o Método Simplex
Modelos lineares são uma classe de modelos matemáticos amplamente utilizados na otimização de problemas nos quais as relações entre as variáveis são lineares. Eles são caracterizados por terem uma função objetivo linear e restrições lineares. Um exemplo simples de modelo linear é o problema de maximização de lucros ou minimização de custos sujeito a restrições de recursos.
O Método Simplex é um algoritmo utilizado para resolver problemas de programação linear. Ele foi desenvolvido por George Dantzig na década de 1940 e é um dos algoritmos mais importantes e eficientes para resolver esse tipo de problema. O Método Simplex funciona explorando vértices do poliedro definido pelas restrições do problema até encontrar a solução ótima.
Aqui está uma explicação mais detalhada sobre modelos lineares e o Método Simplex:
1. Modelos Lineares
Características:
· Função Objetivo Linear: A função que se deseja maximizar ou minimizar é uma combinação linear das variáveis de decisão.
· Restrições Lineares: As restrições que limitam as decisões são expressas como equações ou inequações lineares.
· Variáveis de Decisão: São as incógnitas do problema, cujos valores devem ser determinados para otimizar a função objetivo.
Exemplo de Formulação:
Um exemplo clássico de modelo linear é o problema de maximização de lucros em uma empresa que produz dois produtos, A e B. Suponha que o lucro por unidade de A seja $5 e por unidade de B seja $4. A empresa tem disponíveis 40 horas de mão de obra e 60 horas de máquina para produzir esses produtos. Cada unidade de A consome 2 horas de mão de obra e 3 horas de máquina, enquanto cada unidade de B consome 1 hora de mão de obra e 2 horas de máquina. O objetivo é maximizar o lucro total.
Formalmente, podemos definir:
· 𝑥1x1​: número de unidades do produto A a serem produzidas
· 𝑥2x2​: número de unidades do produto B a serem produzidas
A função objetivo é maximizar o lucro total, dada por: Maximizar 𝑧=5𝑥1+4𝑥2Maximizar z=5x1​+4x2​
Sujeito às seguintes restrições: 2𝑥1+𝑥2≤402x1​+x2​≤40 3𝑥1+2𝑥2≤603x1​+2x2​≤60 𝑥1,𝑥2≥0x1​,x2​≥0
2. Método Simplex
O Método Simplex é um algoritmo iterativo que resolve problemas de programação linear. Ele começa com uma solução viável básica e, em cada iteração, move-se de uma solução básica viável para outra, melhorando o valor da função objetivo. O algoritmo termina quando não há mais melhorias possíveis na solução atual, indicando que foi encontrada a solução ótima.
Passos do Método Simplex:
1. Formular o Problema: Converter o problema em uma forma padrão, com todas as desigualdades como igualdades e introduzir variáveis de folga ou artificiais, se necessário.
2. Encontrar a Solução Inicial: Encontrar uma solução básica viável para começar o algoritmo.
3. Iteração do Método Simplex:
· Cálculo dos Custos Reduzidos: Calcular os custos reduzidos das variáveis não básicas.
· Selecionar a Variável de Entrada: Escolher uma variável não básica com custo reduzido negativo.
· Determinar a Direção: Determinar a direção na qual a solução básica atual pode ser melhorada.
· Calcular o Passo: Calcular o tamanho do passo na direção selecionada.
· Atualizar a Base: Atualizar a solução básica, introduzindo a variável selecionada na base e removendo outra variável.
4. Critérios de Parada: O algoritmo termina quando não há mais variáveis não básicas com custo reduzido negativo, indicando que a solução atual é ótima.
5. Solução Ótima: Após o término do algoritmo, as variáveis básicas terão valores que maximizam ou minimizam a função objetivo, dependendo