INVESTIGAÇÃO OPERACIONAL
TEMA : PROGRAMAÇÃO LINEAR
MÉTODO SIMPLEX PARA RESOLVER PROBLEMAS DE PROGRAMÇÃO LINEAR
FORMA CANÓNICA E FORMA STANDAR DE UM PROBLEMA DE PROGRAMAÇÃO
LINEAR
VARIÁVEIS DE FOLGA
REVISÃO
BASE DE UM ESPAÇO VECTORIAL
TRANSFORMAÇÃO DE DESIGUALDADES EM IGUALDADES
SOLUÇÕES DE UM PROBLEMA DE PROGRAMCAO LINEAR
Um problema de P.L. pode ter:
Uma única solução óptima
Múltiplas soluções óptimas (uma infinidade)
Não ter óptimo finito
Não ter nenhuma solução (neste caso o problema é impossível)
ALGORITMO SIMPLEX PARA RESOLVER PROBELMAS DE PROGRAMÇÃO LINEAR
O que é um algoritmo.
Um algoritmo é um processo que repete (itera) sucessivas vezes um procedimento
sistemático até obter um resultado. Além disso, também inclui um procedimento para iniciar
e um critério para terminar.
EXEMPLO.
Max Z = 3x1 + 5x2
SA x1 <= 4
2x2 <= 12 FORMA CANONICA (V. DE FOLGA)
3x1 + 2x2 <= 18
x1, x2 >= 0
ALGORITMO PRIMAL SIMPLEX. QUADRO #1
CIJ 3 5 0 0 0
BASE VALOR(BI) X1 X2 X3 X4 X5
X3 4 1 0 1 0 0
X4 12 0 2* 0 1 0 SIMETRICOS COEF. F.O
X5 18 3 2 0 0 1
-Z 0 -3 -5 0 0 0
SOLUCAO BASICA INICIAL ( SBI ) X1=
0, X2 = 0, X3 = 4, X4 = 12, X5 = 18
SBI: (0, 0, 4, 12, 18) X1,X2 V. NÃO BÁSICAS, X3,X4,X5 V. BÁSICAS, Z = 0
NÃO CONSTIUI A SOLUÇÃO ÓPTIMA EXISTEM CUSTOS REDUZIDOS NEGATIVOS (X1 = -3
X2 = -5).
TEMOS QUE CONTINUAR O ALGORITMO ATÉ ENCONTRAR A SOLUÇÃO ÓPTIMA
PROXIMA SOLUÇÃO BÁSICA
1. V. Entra a base : X2 a de menor custo reduzido X2 = -5
2. V. Sai da Base : MIN ( 12/2 ; 18/2); 6 ----- X4
3. PIVOTE : INTERSECÇÃO ENTRE COLUNA QUE ENTRA E LINHA QUE SAI: 2
TRANSFORMAÇÕES :
A VARIAVEL QUE ENTRA A BASE DEVE TOMAR OS COMPONENTES DA VARIAVEL QIE
SAI, PARA O CASO X2 DEVE PASSAR DE (0, 2, 2) PARA (0,1, 0), QUE SÃO OS
COMPONENTES DE X4, QUE SAI DA BASE
1) L2 = ½ L2 2) L1 = L1 3) L3 = -2L2 + L3 4) L4 = 5L3 + L4
QUADRO #2
CIJ 3 5 0 0 0
BASE VALOR(BI) X1 X2 X3 X4 X5
X3 4 1 0 1 0 0
X2 6 0 1 0 1/2 0
X5 6 3* 0 0 -1 1 SB: ( 0, 6, 4, 0, 6), Z = 30
-Z 30 -3 0 0 5/2 0 NÃO OPTIMA EXISTE UM CUSTO
REDUZIDO NEGATIVO X1 = -3
DETERMINAÇÃO DE UMA NOVA SOLUÇÃO BÁSICA
1.- VARIÁVEL QUE ENTRA A BASE: A DE MENOR CUSTO REDUZIDO ( A MAIS NEGATIVA,
X1 = -3)
2.- VARIAVEL QUE SAI DA BASE MIN ( 4:1 = 4, 6:3 = 2), X5 : 6/3 = 2
3.- PIVOTE : 3 (INTERSEÇÃO DA LINHA QUE SAI E COLUNA QUE ENTRA)
TRANSFORMAÇÕES
1) L3 = 1/3 L3
2) L1 = -L3 + L1
3) L4 = 3L3 + L4
QUADRO 3
CIJ 3 5 0 0 0
BASE VALOR(BI) X1 X2 X3 X4 X5
X3 2 0 0 1 1/3 -1/3
X2 6 0 1 0 1/2 0
X1 2 1 0 0 - 1/3 NOVA SOLUÇÃO BÁSICA
1/3 (,X1,X2,X3,X4,X5) = (2,6,2,0,0)
-Z 36 0 0 0 3/2 1 NÃO EXISTEM CUSTOS REDUZIDOS
NEGATIVOS, A SOLUÇÃO É ÓPTIMA
MAX Z = 36
INTERPRETAÇÃO ECONÓMICA E COMPARAÇÃO COM RESULTADO DA SOLUCAO GRÁFICA
OBTIDA
CONCLUSÃO:
1. O ALGORITMO SIMPLEX PERMITE PASASSAR DE UMA SOLUÇÃO BÁSICA
ADMISIVEL PARA OUTRA COM MELHOR VALOR DA F.O ATÉ DETERMINAR A
SOLUÇÃO ÓPTIMA
TPC
1. Resolver aplicando o algoritmo Simplex o problema formulado abaixo
Max Z = 40x1 + 60x2
S.A ; 2x1 + x2 <= 70
x1 + x2 <= 40
x1 + 3x2 <= 90, x1 >= 0, x2>= 0
2. Pesquisar solução através de software online de PPL. Entrar a [Link] ou lindo e
resolver analitica e graficamente o exercicio resolvidos e /ou de tpc.
3. Pesquisar a utilização de solver de Microsoft Excel para resolver PPL