EPS7005 – Pesquisa Operacional
Prof. Sérgio Mayerle
Ementa: Introdução: histórico, objetivos, restrições e modelos.
Condições de otimalidade. Programação linear: modelos de
programação linear, método simplex, dualidade, análise de
sensibilidade e pós-otimalidade. Problemas lineares especiais.
Programação não linear; otimização multivariada; otimização sem
restrições. Programação Inteira, binária e mista: algoritmos e
modelos. Programação dinâmica determinística e estocástica.
Pesquisa Operacional
Sumário

Parte I – Introdução à Pesquisa Operacional

Parte II – Programação Linear

Parte III – Problemas Lineares com estruturas especiais

Parte IV – Programação Inteira

Parte V – Programação Dinâmica

Parte VI – Programação Não Linear
Parte I
Introdução à Pesquisa Operacional
Histórico
Definição
Abordagem da PO
Princípios de modelagem
Validação de modelos
Introdução à Pesquisa Operacional
Histórico



II Guerra Mundial
• Problemas complexos
• Envolvimento multidisciplinar de cientistas (UK)
• Desenvolvimento de técnicas matemáticas (USA)
• Eficiência e sucesso na área militar
Transferência dos conhecimentos adquiridos para a área civil
• Retorno dos cientistas para as universidades
• Adaptação e aplicação das técnicas em atividades econômicas
(empresas petrolíferas e grandes coorporações)
• PO Vantagem Competitiva
• Padronização dos problemas generalização do uso da PO
Década de 50
• 1952 - Operations Research Society of America (ORSA)
• 1953 - Institute of Management Sciences (TIMS)
• Operations Research e Management Sciences
Introdução à Pesquisa Operacional
Histórico


Década de 60
• computadores resolução de problemas grandes e complexos
• introdução da PO como disciplina nas universidades
• cursos de pós-graduação (M.Sc. e Ph.D.)
Atualmente
• IFORS - International Federation of Operations Research Society
• ALAIO - Associación Latino Americana de Investigación Operativa
• SOBRAPO - Sociedade Brasileira de Pesquisa Operacional
• Existem congressos, simpósios: "Production planning", "OR in
community health planning", "OR models of the criminal justice system",
"Transportation and mass transit studies", "Travel and tourism",
"Energy", "Education models", "OR applications in sports".
• Aplicações na indústrias, bancos, hospitais, instituições governamentais,
universidades, comércio, agricultura, informática
Introdução à Pesquisa Operacional
Definição

Definição histórica
• "É um conjunto de problemas, técnicas de resolução e soluções, com
características bem definidas, acumuladas sob o termo PO desde a
década de 40 do século passado".

Definição filosófica
• "Pesquisa Operacional é o conjunto de conhecimentos relacionados
com o processo científico de tomada de decisão, aplicados no projeto e
operação de sistemas homem-máquina, em um ambiente com recursos
restritos".
Introdução à Pesquisa Operacional
Abordagem da PO
Modelo é uma representação
simplificada / idealizada, que
visa obter informações sobre o
sistema real com economia de
tempo e recursos
Formulação: liberdade,
arbitrariedade e coerência
Sistema
Real
Formulação
Abordagem Direta
Solução
Real
Modelo
Dedução
Interpretação
Interpretação: julgamento humano,
reavaliação do modelo
Solução do
Modelo
Dedução: uso de
técnicas dependentes
do modelo formulado,
rigor matemático e
precisão, uso de
computadores
Introdução à Pesquisa Operacional
Princípios de Modelagem
1.
2.
Não construir modelos complicados quando um modelo simples é suficiente.
Evitar a construção de modelos de modo que estes se ajustem a uma
técnica de solução previamente definida.
3.
Conduzir a fase de dedução com o máximo rigor possível.
4.
Os modelos devem ser validados a priori em relação a implementação.
5.
Não confiar cegamente no resultado do modelo, de modo a perder de vista
a realidade do problema.
6.
Modelos não devem ser utilizados, nem tão pouco criticados por não
resolver situações para as quais não foram desenvolvidos.
7.
Não sobrevalorizar o modelo diante do usuário.
8.
Sempre envolver o usuário no processo de desenvolvimento e validação do
modelo.
9.
Os resultados de um modelo nunca podem ser melhores que os dados nele
introduzidos.
10. Modelos não podem substituir tomadores de decisão.
Introdução à Pesquisa Operacional
Validação de Modelos

Aspectos a considerar
• não existe modelo perfeito
• não existe um critério absoluto de verificação de modelos
• não se pode "provar" ou "verificar" o modelo

Validar o modelo
• adquirir a convicção de que o modelo é útil para aquilo a que foi
proposto
• convencer o usuário de que os resultados são úteis dentro de um
determinado contexto
Parte II
Programação Linear
Formulação de modelos
Solução gráfica
Forma padrão e relações de equivalência
Propriedades dos PPL’s
Solução inicial viável
Método Simplex – Forma tableau
Método Simplex – Algoritmo
Método Simplex – Forma matricial
Dualidade em Programação Linear
Análise de pós-otimalidade
Programação Linear
Formulação de Modelos
A WINDOR GLASS Inc. dispõe de capacidade extra para produzir dois novos
produtos. A demanda é muito maior que a capacidade disponível (toda
produção poderá ser vendida).
Pergunta-se: (a) o que produzir? (b) quanto produzir? (c) qual será o lucro?
(d) qual o valor, em $/hora, da capacidade disponível em cada setor
produtivo? Os dados estão na tabela abaixo.
Produto
Janelas
Portas
Capacidade
Disponível
Montagem
1 hora/unid.
-
4.000 horas/mês
Laminação
-
2 hora/unid.
12.000 horas/mês
Corte
3 hora/unid.
2 hora/unid.
18.000 horas/mês
Lucro Unitário
$ 3,00
$ 5,00
Setor Produtivo
Programação Linear
Formulação de Modelos
Produto
Janelas
Portas
Capacidade
Disponível
Montagem
1 hora/unid.
-
4.000 horas/mês
Laminação
-
2 hora/unid.
12.000 horas/mês
Corte
3 hora/unid.
2 hora/unid.
18.000 horas/mês
Lucro Unitário
$ 3,00
$ 5,00
Setor Produtivo
 Variáveis
X1 = qtde. de janelas, em milhares de unidades;
X2 = qtde. de portas, em milhares de unidades;
Z = lucro total obtido com novos produtos.
 Restrições
a) disponibilidade do setor de montagem;
b) disponibilidade do setor de laminação;
c) disponibilidade do setor de corte;
d) quantidades não negativas.
 Objetivo
Maximizar o lucro total da empresa
Max Z  3 x1  5 x2
s.a :
x1  4
2 x2  12
3 x1  2 x2  18
x1 , x2  0
Programação Linear
Formulação de Modelos













Produção
Logística
Mistura
Finanças e investimentos
Carregamento de navios
Corte de chapas e barras
Aquisição de máquinas
Problemas dinâmicos
Câmbio

Alguns do problemas acima apresentam variáveis discretas que somente
podem assumir valores do conjunto de inteiros, e em casos mais particulares
o conjunto de inteiros se limita a {0,1}.



Estratégia militar
Engenharia estrutural
Operação de dutos
Dimensionamento de linhas de
produção
Alocação de mão-de-obra
Programação de operações
Controle de emissão de poluentes
Programação Linear
Solução Gráfica
Max Z  3 x1  5 x2
s.a :
x2
x1  4
9
x1  4
8
2 x2  12
7
3 x1  2 x2  18
2 x2  12
6
x1 , x2  0
5
4
x1  0
3
2
3 x1  2 x2  18
1
0
0
1
2
x2  0
3
4
5
6
7
8
9
x1
Programação Linear
Solução Gráfica

O que fazer se além de portas e janelas a WINDOR puder fabricar, também,
mesas e armários?
Resolver graficamente o problema torna-se inviável ... É necessário usar
métodos numéricos mais eficazes e eficientes.

Quantos produtos diferentes uma fábrica pode produzir?
5, 10, 100, 1000, ...

Quantos setores de produção uma fábrica possui?
5, 10, 100, 1000, ...

E se existem restrições adicionais em relação ao uso de matéria-prima,
energia, estoques, mão-de-obra, cadeia de suprimento e distribuição?
Outros modelos, mais complexos, poderão ser formulados ...
A solução gráfica não se aplica a estas outras situações !!!
Programação Linear
Forma padrão e relações de equivalência
Max
z  c1 x1  c2 x2    cn xn
s.a :
a11x1  a12 x2    a1n xn  b1
a21x1  a22 x2    a2 n xn  b2

am1 x1  am 2 x2    am nxn  bm
x1 , x2 ,, xn  0
Programação Linear
Forma padrão e relações de equivalência
n
Max
z  cj xj
j 1
n
s.a :
a
j 1
ij
x j  bi
xj  0
i  1,, m
j  1,, n
Programação Linear
Forma padrão e relações de equivalência
Max
z  c1
 a11
a
s.a :  21
 
a
 m1
c2
a12
a22

am 2
 x1 
x 
 cn   2 

x 
 n
 a1n   x1   b1 
 a2 n   x2   b2 
   e
    
 am n   xn  bm 
 x1  0
 x  0 
 2   
   
x   
 n  0 
Programação Linear
Forma padrão e relações de equivalência
Max
s.a :
z  cT x
Ax  b
x0
 c1 
c 
2


c

c 
 n
 x1 
 b1 
x 
b 
2
2




x
b


x 
b 
 n
 m
 a11
a
21

A
 
a
 m1
a12
a22

am 2
 a1n 
 a2 n 

  
 am n 
Programação Linear
Forma padrão e relações de equivalência

Qualquer que seja a estrutura do PPL, sempre é possível transformá-lo no
formato padrão apresentado.

Relação entre maximização e minimização
n
Max
z  cj xj
 Min
j 1
n
Min z   c j x j
j 1
 z     c j  x j
n
j 1
 Max
 z     c j  x j
n
j 1
Programação Linear
Forma padrão e relações de equivalência

Relação entre inequações e equações
n
aij x j  bi

j 1
n
aij x j  bi

j 1
n
 aij x j  Si  bi
  j 1
0  S  

i
n
 aij x j  Si  bi
  j 1
0  S  

i
Programação Linear
Forma padrão e relações de equivalência

Tratamento de limites de variáveis
 x j  LB  xj  x j  xj  LB
x j  LB  0  
 xj  0
UB  x j  xj  x j  UB  xj
x j  UB  
 xj  0
 x j  xj  xj
   x j    
 xj  0 e xj  0
Programação Linear
Propriedades dos PPL’s
Suposições da modelagem
 Proporcionalidade
Custos e quantidades de recursos consumidos na produção são
proporcionais às quantidades produzidas
 Aditividade
Custos totais e quantidades totais de recursos são determinados pela soma
de custos e recursos consumidos na produção de todos items
 Divisibilidade
É possível produzir quantidades fracionárias de cada um dos produtos
 Certeza
Todos os parâmetros do modelo são determinados e conhecidos
Perspectiva das suposições da modelagem
Existe a possibilidade de todas estas suposições não serem verdadeiras.
Programação Linear
Propriedades dos PPL’s


Se existe exatamente uma solução
ótima, então deve ser uma solução
factível em um vértice
Se existem soluções ótimas múltiplas,
então ao menos duas delas devem ser
soluções factíveis em vértices
adjacentes
x2
9
8
7
6


Existe um número finito de soluções
factíveis em vértices, não maior que...
Se muma solução
n!factível em um vértice
éCigual
n ou melhor (segundo o valor de
Z) que todas
m!(nassoluções
m)! factíveis nos
vértices adjacentes a ela, então é igual
ou melhor que todas as demais
soluções factíveis existentes nos
vértices, isto é, é uma solução ótima
5
4
3
2
1
0
0
1
2
3
4
5
6
7
8
9
x1
Programação Linear
Propriedades dos PPL’s
Estrutura do Método Simplex
x2



Passo inicial: iniciar com
uma solução em um vértice
(solução básica viável).
Teste de otimalidade: se
não existe um vértice
adjacente, melhor que o
vértice atual, então PARE.
O vértice atual corresponde
à solução ótima. Em caso
contrário, vá ao passo 3.
Passo iterativo: movimente
em direção de uma solução
factível melhor, em um
vértice adjacente; volte ao
passo 2.
Solução
Ótima
9
8
7
6
5
4
3
2
1
0
0
1
2
3
4
5
6
7
8
9
x1
Programação Linear
Solução Inicial Viável - Caso trivial
Max
z  3 x1  5 x2
Max
z  3 x1  5 x2
s.a :
x1  4
s.a :
x1  S1  4
2 x2  12
2 x2  S 2  12
3 x1  2 x2  18
3 x1  2 x2  S3  18
x1 , x2  0
x1 , x2 , S1 , S 2 , S3  0
Caso trivial
a) variáveis não negativas
b) restrições com limite superior
Solução
 variáveis nulas
 folgas iguais ao RHS
S1  4 x1  0
S 2  12 x2  0
S3  18 z  0
Programação Linear
Solução Inicial Viável - Caso não trivial
n
Max
z  cj xj
Não tem solução trivial
j 1
n
s.a :
a
j 1
ij
x j  bi
xj  0
i  1,...,mn
Max z   c j x j
j 1
j  1,...,n
n
s.a :
a
j 1
Sempre tem solução trivial
ij
x j  d i  bi
i  1,...,m
xj  0
j  1,...,n
di  0
i  1,...,m
Ambas formulações são equivalentes quando
di  0, i  1,..., m
Programação Linear
Solução Inicial Viável - Método do M-grande
Max
n
m
j 1
i 1
z   c j x j   M di
n
s.a :
a
j 1
ij
x j  d i  bi
i  1,...,m
xj  0
j  1,...,n
di  0
i  1,...,m
Se di  0, i  1,..., m  encontrou a solução ótima
não existe solução viável, ou
Se di  0  
M não é suficientemente grande
Programação Linear
Solução Inicial Viável - Método das 2 fases
Max w  
di

i 1
Fase 1
n
s.a :
Resolver o problema da
fase 1 usando as variáveis
artificiais para formar uma
base inicial viável.
Se w = 0, então uma
solução inicial viável foi
obtida para o problema.
m
aij x j  di  bi

j 1
xj  0
j  1,..., n
di  0
i  1,..., m
i  1,..., m
Max
z
n
c
j
xj
j 1
Se w = 0, usar solução ótima
da fase 1 como solução inicial
viável para a fase 2.
n
s.a :
a
ij
x j  bi
Fase 2
i  1,..., m
j 1
xj  0
j  1,..., n
Programação Linear
Método Simplex - Forma Tableau
Base
Z
X1
X2
S1
S2
S3
RHS
S1
0
1
0
1
0
0
4
+inf
S2
0
0
2
0
1
0
12
+6
S3
0
3
2
0
0
1
18
+9
Z
1
-3
-5
0
0
0
0
O que fazer para melhorar a solução?
Quanto aumentar X2 ?
Max
z  3 x1  5 x2
sS2
.a :
RHS
xS3
1  S1  4
Base
Z
X1
X2
S1
S1
0
1
0
1
0
X2
0
0
1
0
1/2
S3
0
3
0
0
-1
31 x1  26x2  S+2
3  18
Z
1
-3
0
0
5/2
x01 , x2 , S30
1 , S 2 , S3  0
0
4
+4
0
6
+inf
2 x2  S 2  12
Programação Linear
Método Simplex - Forma Tableau
Base
Z
X1
X2
S1
S2
S3
RHS
S1
0
0
0
1
1/3
-1/3
2
X2
0
0
1
0
1/2
0
6
X1
0
1
0
0
-1/3
1/3
2
Z
1
0
0
0
3/2
1
36
Var.
Decisões
Valor
Marg.
X1
Janelas
2
0
X2
Portas
6
0
S1
Montagem
2
0
S2
Laminação
0
1,5
S3
Corte
0
1
Z
Lucro
36
1
Pergunta-se:
(a) o que produzir?
(b) quanto produzir?
(c) qual será o lucro?
(d) qual o valor da capacidade
disponível em cada setor?
Programação Linear
Custo marginal
mais negativo
Método Simplex – Algoritmo
Início
Escolher variável
para entrar na base
Montar tableau com
solução básica
inicial viável
Menor razão
não negativa
Calcular razão
RHS / coluna (entra)
Escolher variável
para sair da base
1
Existe custo
marginal < 0 ?
Sim
Existe
razão  0
finita ?
Não
Não
Solução
ótima
Solução
ilimitada
Sim
Fazer troca de
base e recalcular
o tableau
1
Fim
Programação Linear
Método Simplex – Algoritmo
Supondo que a troca de base será realizada com o pivo localizado na r-ésima
linha e k-ésima coluna, o novo tableau poderá ser obtido pré-multiplicando o
tableu da iteração corrente pela inversa da matriz elementar formada pela k-ésima
coluna do tableau corrente, posicionada na r-ésima coluna desta matriz
elementar, isto é:
T
(t 1)
1
r ,k
 E T
(t )
Programação Linear
Método Simplex – Algoritmo
T (0)
0 1 0

0 0 2


0 3 2

 1 2 5
T (1)
1
1 0
 0 1 0

 0 0 2
2
 


2 1  0 3 2

 

5
1

  1 2 5
T
(2)
1
0
0
0
0
1
0
0
0 4

0 12 
1 18 

0 0 
1
1
1
 0 1

 0 0
1
0
 


 0 3
3

 

3
1

  1 3
4  0 1
 
0 1 0 12   0 0

0 0 1 18   0 3
 
0 0 0 0   1 3
1 0 0
4  0
 
1 0 1/ 2 0 6   0

0 0 1 1 6   0
 
0 0 5 / 2 0 30   1
0 1
0
0
4

1 0 1/ 2 0 6 
0 0 1 1 6 

0 0 5 / 2 0 30 
0 1
0
0
0 0 1
1/ 3
1/ 3
0 1 0
1/ 2
0
1 0 0 1/ 3
0 0 0
3/ 2
1/ 3
1
2

6
2

36 
Programação Linear
Método Simplex - Forma Matricial
Max z  c x
s.a : Ax  b
x0
 xB 
Max z  c c  
 xR 
 xB 
s.a : B R     b
 xR 

T
Particionando...
T
B
T
R
 x B  0 
 x   0 
 R  

Programação Linear
Método Simplex - Forma Matricial

Como resolver o sistema de equações lineares ?
 xB 
B R    b
 xR 
B xB  R xR  b
B xB  b  R xR
xB  B 1 b  R xR 

No caso particular em que as variáveis não básicas são nulas ...
xˆ R  0
Solução Particular
xˆB  B 1b
Programação Linear
Método Simplex - Forma Matricial

E o valor da função objetivo ?

z c

T
B
c
T
R

z  cBT xB  cRT xR
z  cBT B 1 b  R xR   cRT xR
 xB 
x 
 R
z  cBT B 1b  cRT  cBT B 1 R  xR
z  cBT xˆ B  cRT  cBT B 1 R  xR
No caso particular em que as variáveis não básicas são nulas ...
xˆ R  0
1
xˆ B  B b
Solução Particular
zˆ  cBT xˆB
Programação Linear
Método Simplex - Forma Matricial

Resumindo, até aqui tem-se ...
xB  B
1
b  R xR  
 xˆ R  0

1
x

B
b
ˆ
 B
z  cBT xˆB  cRT  cBT B1R xR


É possível melhorar o valor da função objetivo ? ...
z  zˆ  cRT  cBT B 1R xR  0
zˆ  cBT xˆB
Programação Linear
Método Simplex - Forma Matricial

Como melhorar ...
z  zˆ  cRT  cBT B 1R xR  0
z  zˆ  

Escolher para aumentar (entrar
na base) uma variável não
básica associada a uma
componente positiva do vetor
 xR ,1 
 x

R ,k

0

0 
  
x

 R ,nm 
cRT  cBT B 1R
Programação Linear
Método Simplex - Forma Matricial

Aumentar a k-ésima variável não básica (escolhida) ... até quanto ?
xB ,i  xˆ B ,i  Rk ,i xR ,k  0
xB  B 1 b  R xR 
Rk ,i xR ,k  xˆ B ,i
xB  xˆ B  B 1 Rk xR ,k
xˆ B ,i

Rk ,i
xB  xˆ B  Rk xR ,k
x R ,k
 xB ,1   xˆ B ,1   Rk ,1 
0 
 x   xˆ   R 
0 
 B , 2    B , 2    k , 2  xR ,k   
        


 x   xˆ  
0 
R
 
 B ,m   B ,m   k ,m 
i  1,...,m
i  1,...,m
somente para
Rk ,i  0
Escolher para sair da base
uma variável básica
associada ao menor valor
calculado.
Programação Linear
Método Simplex - Forma Matricial

Resumo...
x
ˆ B  B 1b
zˆ  cBT xˆB
z  zˆ  cRT  cBT B 1R xR  0
Solução
Teste de entrada
Rk  B1Rk
xR ,k
 xˆ B ,i

 min 
| Rk ,i  0
 Rk ,i

Teste de saída
Programação Linear
Exemplo (1)
cRT
cBT
 x1 
x 
 2
Max z  3 5 0 0 0  S1 
S 
 2
 S3 
R
B
s.a :
 x1 
 
1 0 1 0 0   x 2   4 
0 2 0 1 0  S   12

  1  
3 2 0 0 1  S 2  18
 S3 
xR
xB
b
 x1  0
 x  0 
 2  
 S1   0
S   
 2  0 
 S3  0
Programação Linear
Exemplo (1.a)
1a. Iteração
 S1 
xB   S 2 
 
 S3 
 x1 
xR   
 x2 
4
b  12
 
18
1 0 0
B  0 1 0 


0 0 1
1 0
R  0 2 


3 2
cTB  0 0 0
cTR  3 5
Programação Linear
Exemplo (1.b)
1
 x1  0
xˆ R      
 x2  0
 S1 
1 0 0  4   4 
xˆ B   S2   B 1b  0 1 0 12  12
 

    
 S3 
0 0 1 18 18
4
zˆ  cBT xˆ B  [0 0 0] 12  0
 
18
cRT  cBT B 1 R  3 5  0
cRT  cBT B 1 R  3 5
1
 1 0 0  1
0 0 0 1 0  0
x2 Entra
 na base  
0 0 1 3
0
2

2
Programação Linear
Exemplo (1.c)
1
1 0 0 0 0
Rk  B 1 Rk  0 1 0 2  2

    
0 0 1 2 2
 4  0 
0 
xB  xˆ B  Rk xR ,k  12  2 xR ,k  0
   
 
18 2
0
 4 12 18 
xR ,k  min  , ,   6
0 2 2 
S2
Sai da base
 S1   4 
xˆ B   S2   12
   
 S3  18
Coluna de
x2
Programação Linear
Exemplo (2.a)
2a. Iteração
 S1 
xB   Sx2 
 
 S3 
 x1 
xR   
 Sx2 
4
b  12
 
18
1 0 0
B  0 12 0


2 1
0 0
1 0
2
R  0 1


0
3 2
cTB  0 50 0
5
cTR  3 0
Programação Linear
Exemplo (2.b)
 x1  0
xˆR      
S2  0
zˆ  cTB xˆ B  [0
 S1 
1
xˆ B   x2   B 1b  0
 

 S3 
0
5
0
2
2
 4
0] 6  30
 
6
1
c RT  cBT B 1 R  3 0  0 5 0 0

x1 Entra na base
0
5

T
T
1
c R  cB B R  3  
2

0
2
2
0
0

1
1
0
0

1 
 4   4
12  6
   
18 6
1
1
0

3
0
1

0
Programação Linear
Exemplo (2.c)
1
1 0 0 1 1
Rk  B 1 Rk  0 2 0 0  0

    
0 2 1 3 3
 s1  4
xˆ B   x2   6
   
 s3  6
4 1
0 
xB  xˆ B  Rk xR ,k  6  0 xR ,k  0
   
 
6 3
0
 4 6 6
xR ,k  min  , ,   2
1 0 3
S3
Coluna de
Sai da base
x1
Programação Linear
Exemplo (3.a)
3a. Iteração
 S1 
xB   x2 
 
 Sx13 
 Sx13 
xR   
S 2 
4
b  12 
 
18
0
1 0 1
B  0 2 0 


0 2 13
0
0 1
R  0 1
0


3
1 0
cTB  0 5 3
0
cTR  0 03
Programação Linear
Exemplo (3.b)
1
1 0 1  4  2
xˆ B  B 1b  0 2 0 12  6

    
0 2 3 18 2
 2
zˆ  cBT xˆ B  [0 5 3] 6  36
 
2
Solução ótima
1
1 0 1   0 0 
cRT  cBT B 1 R  0 0  0 5 3 0 2 0 0 1

 

0 2 3 1 0
3

cRT  cBT B 1 R   1  
2

Programação Linear
Exemplo (4)
Var.
Decisões
Valor
Marg.
X1
Janelas
2
0
X2
Portas
6
0
S1
Montagem
2
0
S2
Laminação
0
-1,5
S3
Corte
0
-1
Z
Lucro
36
1
Parte III
Problemas Lineares Especiais
Problema de Atribuição
Problema de Transportes
Problemas de Fluxo em Redes
Parte IV
Programação Inteira
Modelagem
Algoritmo de branch and bound
Algoritmo de Balas
Parte V
Programação Dinâmica
Formulação de modelos
Programação Dinâmica Determinística
Programação Dinâmica Estocástica
Programação Dinâmica com horizonte ilimitado
Parte VI
Programação Não Linear
Formulação de modelos
Condições de Karush-Kuhn-Tucker (KKT)
Problemas não lineares monovariados
Problemas mutivariados não lineares
Problemas multivariados não lineares com restrições