Manejo Florestal - Método Simplex (PL, PI, Dualidade)

Prévia do material em texto

ENF 343 – MANEJO FLORESTAL 
PESQUISA OPERACIONAL (PO) 
PO - conjunto de técnicas direcionadas a 
problemas complexos voltados para a 
tomada de decisões em empresas. 
Ponto chave: construção de modelos 
matemáticos a partir dos quais, escolhe-se 
uma técnica adequada para resolução. 
Exemplo (área florestal): alocação de 
recursos, substituição de equipamentos, 
estoque, localização e distribuição da 
produção, roteamento de veículos, etc. 
 
PO 
 
 
HISTÓRICO 
Primeira citação: 1938 (estudo matemático 
em operações militares). 
Pós-guerra: 1937 (Método Simplex – para 
resolução de problemas de PL) 
Brasil: Década 1960 (1º Simpósio Brasileiro 
de Pesquisa Operacional (SBPO) foi 
realizado em 1968 no ITA; criação 
Sociedade Brasileira de Pesquisa 
Operacional (SOBRAPO)). 
 
CONCEITOS BÁSICOS 
• A determinação do método de solução é 
em função do tipo e complexidade do 
modelo matemático de PO. 
• Exemplos de técnicas: programação 
linear, programação inteira, programação 
dinâmica, etc. 
• A maioria das técnicas obtêm soluções 
através de algoritmos. 
• Em alguns casos há, inclusive, a 
necessidade de adotar heurísticas a fim de 
obter soluções em tempo viável. 
 
• Qualidade da solução: depende de quanto 
o modelo representa o sistema real. 
 
 
• Solução viável: satisfaz todas as restrições 
do modelo. 
• Solução é ótima: além de viável, resulta o 
melhor valor (máximo ou mínimo) para o 
modelo especificado. 
• Em geral trata-se de recursos limitados e 
a sua utilização criteriosa possibilita 
melhorar o rendimento ou produtividade 
do processo em estudo. 
 
FASES PARA IMPLEMENTAÇÃO DA PO 
1. Definição do problema: 
Identificar 3 elementos primordiais - 
descrição das alternativas de decisão 
determinação do objetivo do estudo 
especificação das limitações do sistema. 
2. Construção do modelo: 
a. Adoção de notação apropriada (x1, 
x2, xn) para as variáveis de decisão 
(quantidades presentes) do 
problema 
b. Redefinição matemática do 
problema através de fórmulas, 
relações matemáticas ou 
proposições. Uma fórmula 
denominada de função-objetivo é 
utilizada para descrever como o 
objetivo do problema é 
influenciado pelos valores das 
variáveis de decisão. 
• Relações matemáticas envolvendo os 
símbolos "=", “<", “>" e proposições gerais 
são empregadas para descrever restrições 
para a escolha de valores para as variáveis 
de decisão. 
• Os modelos matemáticos adotados para 
problemas de planejamento são 
normalmente prescritivos. 
• A prescrição quase sempre é otimizar a 
função-objetivo sujeito às restrições, sendo 
que otimizar pode significar minimizar ou 
maximizar a função. 
Programação matemática 
(te dá o valor ótimo) 
Modelos 
• Vetores x = (x1, x2, ..., xn) de variáveis 
de decisão representam possíveis 
soluções para o problema de 
otimização. 
• Um método é exato quando é capaz de 
gerar uma solução ótima x* = (x*1, x*2, ..., 
x*n) para o problema. 
3. Implementação da solução 
Transformar a solução em um conjunto de 
instruções na linguagem operacional usada 
pelos administradores do sistema. 
 
EXEMPLO 
Uma agroindústria, deve produzir um tipo 
de ração para determinado animal. 
– A ração é produzida pela mistura de 
farinhas de 3 ingredientes básicos: osso, 
soja e resto de peixe. 
– Cada ingrediente possui diferentes 
quantidades de 2 nutrientes: proteína e 
cálcio. 
– O nutricionista especifica as necessidades 
mínimas desses nutrientes em 1kg de 
ração: 30% de proteína e 50% de cálcio 
(pelo menos). 
– Objetivo: determinar em que quantidades 
os ingredientes devem ser misturados de 
modo a produzir uma ração que satisfaça às 
restrições nutricionais com o mínimo custo. 
Nutrientes 
Ingredientes 
Osso Soja Peixe Ração 
Proteína 0,2 0,5 0,4 0,3 
Cálcio 0,6 0,4 0,4 0,5 
Custos 
(R$/kg) 
0,56 0,81 0,46 
 
– Variável de decisão: xj (quantidade (em 
kg) do ingrediente j que deve ser usada em 
uma unidade (1kg) de ração) j=1 (osso), 2 
(soja), 3 (peixe). Assim, o custo da mistura 
será dado por: 
f(x1, x2, x3)=0,56x1+0,81x2+0,46x3 
– Restrições: 
0,2x1+0,5x2+0,4x3>=0,3 (mín. de cálcio) 
0,6x1+0,4x2+0,4x3>=0,5 (mín. de proteína) 
x1+x2+x3=1 (quantidade para 1kg) 
x1>=0, x2>=0, x3>=0 (valores positivos) 
– Modelo Resultante: 
MIN (z) = 0,56x1+0,81x2+0,46x3 
Sujeito a: 
0,2x1+0,5x2+0,4x3>=0,3 
0,6x1+0,4x2+0,4x3>=0,5 
x1+x2+x3=1 
x1>=0, x2>=0, x3>=0 
 
PROGRAMAÇÃO LINEAR 
Objetivo: determinar o quanto de cada 
recurso será consumido em cada atividade, 
ou seja, determinar a solução ótima. 
• Programação  Planejamento 
• É preciso construir um modelo 
matemático que represente a essência do 
problema. 
• Para facilitar a construção do modelo é útil 
construir tabelas com os valores fornecidos. 
• A PL visa fundamentalmente encontrar a 
melhor solução para problemas que 
tenham seus modelos representados por 
expressões lineares. 
• A sua grande aplicabilidade e simplicidade 
devem-se a linearidade do modelo. 
• A tarefa da PL consiste na maximização ou 
minimização de uma função linear (função 
objetivo), respeitando-se um sistema linear 
de igualdades ou desigualdades (Restrições 
do Modelo). 
• Conjunto viável: região determinada 
pelas restrições. A melhor das soluções 
viáveis, ou seja, aquela que maximiza ou 
minimiza a função objetivo, denomina-se 
Solução Ótima. 
• 2 passos: Modelagem e método de 
solução do problema. 
• Pressuposições da PL: 
1. Modelo linear 
2. Proporcionalidade (O custo de cada 
atividade é proporcional ao nível de 
operação da atividade; a 
quantidade de recursos 
consumidos por uma atividade é 
proporcional ao nível dessa 
atividade) 
3. Aditividade (O custo total é a soma 
das parcelas associadas a cada 
atividade) 
4. Certeza (Assume-se que todos os 
parâmetros do modelo são 
constantes conhecidas) 
5. Divisibilidade (As atividades podem 
ser divididas em qualquer nível 
fracionário) 
• Matematicamente, na PL, não pode 
ter valores negativos. 
 
SOLUÇÃO GRÁFICA PL 
• Para modelos com apenas duas variáveis 
de decisão. 
1ª Etapa – Encontrar a Região Viável, ou 
seja, o conjunto dos pares (x1, x2) que 
satisfazem todas as restrições. As restrições 
de não negatividade correspondem ao 1º. 
Quadrante do espaço de pontos (x1, x2), 
conforme Figura 1, onde as setas indicam a 
área onde estão os pontos que satisfazem 
essas restrições. 
Figura 1. 
2a Etapa – Encontrar a solução ótima. Deve-
se perceber que a função objetivo, para 
cada um de seus valores possíveis gera uma 
família de retas paralelas, e o que se está 
buscando é qual delas está associado ao 
maior valor e ainda corta (tangenciando) a 
Região Viável. 
RESUMINDO... 
1º Define o modelo (de acordo com os 
dados) 
2º Definir as restrições 
3º Definir áreas de soluções viáveis 
4º Construir curvas de nível até encontrar o 
valor ótimo. 
• Se existe exatamente uma solução ótima, 
então deve ser uma solução factível em um 
vértice. 
EXEMPLO 
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. 
• 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 
 
 
 
 
 
 
 
 
MÉTODO SIMPLEX 
 
• Procedimento matricial para resolver o 
modelo de programação linear na forma 
normal. 
• Começando com X0, o método localiza 
sucessivamente outras soluções básicasviáveis acarretando melhores valores para a 
função objetivo até ser obtida a solução 
ótima. 
• Método de baixo custo computacional. 
• Extremamente eficiente quando são 
fornecidos os parâmetros corretos. 
• Só resolve problemas com valores 
positivos. 
• Procedimento iterativo que fornece a 
solução de qualquer modelo de PL em um 
número finito de iterações. 
• Indica se o modelo tem solução ilimitada, 
se não tem solução, ou se possui infinitas 
soluções. 
 
ETAPAS SIMPLEX (PASSO A PASSO NO 
EXEMPLO) 
1º Transformar as desigualdades (das 
restrições) em igualdades, utilizando 
variáveis folga. 
 
Ex.: x1 ≥ 40 
 x1 = 40 + Xf1 
 
 x1 ≤ 40 
 x1 = 40 - Xf1 
 
 x1 = 40 
 x1 = 40 + Xf1 
 x1 = 40 - Xf1 
 
EXEMPLO: 
Maximizar Z= 3x1 + 5x2 
Sujeito a: 
2x1 + 4x2 ≤ 10 
6x1 + x2 ≤ 20 
x1 – x2 ≤ 30 
x1 ≥ 0 
x2 ≥ 0 
 
1º passo: Jogar todas as variáveis no 
primeiro membro  Z – 3x1 – 5x2 = 0 
2º passo: Colocar as variáveis folga, 
transformando as desigualdades em 
igualdades 
2x1 + 4x2 + xF1 = 10 (para ficar igual a 10, 
precisa acrescentar mais um pouco) 
6x1 + x2 + xF2 = 20 
x1 – x2 +xF3 = 30 
• OBS: As folgas são colocadas apenas nas 
restrições técnicas. 
3º passo: Construção da tabela 
 
Z x1 x2 xF1 xF2 xF3 b 
1 -3 -5 0 0 0 0 
0 2 4 1 0 0 10 
0 6 1 0 1 0 20 
0 1 -1 0 0 1 30 
0,
1823
122
4:.
53
21
21
2
1
21





xx
xx
x
xas
xxZMax
Pelo menos 40, mas 
pode ser 40 e mais 
um pouco (por isso 
soma) 
No máximo 40, mas 
pode ser menos (por 
isso subtrai) 
Pode ser maior ou 
menor que 40 no 
resultado final. 
Restrições 
técnicas 
Restrições de não negatividade 
Contém 
todas as 
 variáveis 
Termos 
independentes 
 
4º passo: Resolução 
i. Identificar a variável que entra 
Olhar na primeira linha (linha da função 
objetivo) e identificar o número de menor 
valor, que no nosso caso é o -5. Logo, a 
variável que entra é x2.  Destacar a 
COLUNA da variável x2. 
Z x1 x2 xF1 xF2 xF3 b 
1 -3 -5 0 0 0 0 
0 2 4 1 0 0 10 
0 6 1 0 1 0 20 
0 1 -1 0 0 1 30 
 
ii. Identificar a linha que sai (linha 
pivô) 
Será uma das restrições técnicas (nunca 
será a linha da função objetivo). 
- Pegar os valores independentes (b) das 
restrições e dividir pelos coeficientes das 
restrições na coluna da variável que entra 
(x2). 
10/4 = 2,5 
20/1 = 20 
30/-1 = -30 Não convém (número 
negativo – só olhamos os números 
positivos) 
 
O objetivo é: escolher a linha em que o 
resultado foi o MENOR POSITIVO (2,5). E 
nesse caso é a linha do valor independente 
10. 
 
Z x1 x2 xF1 xF2 xF3 b 
1 -3 -5 0 0 0 0 
0 2 4 1 0 0 10 
0 6 1 0 1 0 20 
0 1 -1 0 0 1 30 
 
 
 
iii. Identificar o elemento pivô 
É o elemento que está no cruzamento da 
coluna que entra com a linha que sai. Que 
nesse caso, o elemento pivô é o 4. 
 
Z x1 x2 xF1 xF2 xF3 b 
1 -3 -5 0 0 0 0 
0 2 4 1 0 0 10 
0 6 1 0 1 0 20 
0 1 -1 0 0 1 30 
 
iv. Calcular a nova linha pivô 
- Pegar a linha pivô atual e dividir TODOS os 
elementos dessa linha pelo elemento pivô. 
0 2 4 1 0 0 10 
÷ 
4 (elemento pivô) 
= 
0 0,5 1 0,25 0 0 2,5 
 
v. Calcular as novas linhas (sem 
ser a pivô que já está calculada) 
- Cálculo da nova primeira linha (da 
tabela): 
Multiplicar a NLP pelo oposto do 
coeficiente da variável que entra (x2) 
que está na primeira linha (Nesse caso o 
coeficiente é o -5 e seu oposto é 5). 
0 0,5 1 0,25 0 0 2,5 
X 
5 (oposto do coeficiente da variável 
que entra - x2) 
= 
0 2,5 5 1,25 0 0 12,5 
 
 
Nova linha 
pivô (NLP) 
Depois somar os valores encontrados 
com os valores da primeira linha atual. 
0 2,5 5 1,25 0 0 12,5 
+ 
1 -3 -5 0 0 0 0 
= 
1 -0,5 0 1,25 0 0 12,5 
 
- Cálculo da nova terceira linha: 
NLP x OPOSTO do coeficiente da 
variável que entra (O coeficiente é 1 e o 
oposto é -1). 
0 0,5 1 0,25 0 0 2,5 
X 
-1 
= 
0 -0,5 -1 -0,25 0 0 -2,5 
 
Soma do resultado com a terceira linha 
atual: 
0 -0,5 -1 -0,25 0 0 -2,5 
+ 
0 6 1 0 1 0 20 
= 
0 5,5 0 -0,25 0 17,5 
 
- Calcular a nova quarta linha: 
NLP x OPOSTO do coeficiente da 
variável que entra (O coeficiente é 1 e o 
oposto é -1). 
0 0,5 1 0,25 0 0 2,5 
X 
1 
= 
0 0,5 1 0,25 0 0 2,5 
Soma do resultado com a terceira linha 
atual: 
0 0,5 1 0,25 0 0 2,5 
+ 
0 1 -1 0 0 1 30 
= 
0 1,5 0 0,25 0 1 32,5 
 
vi. Construção da nova tabela 
Z x1 x2 xF1 xF
2 
xF3 b 
1 -0,5 0 1,25 0 0 12,5 
0 0,5 1 0,25 0 0 2,5 
0 5,5 0 -0,25 1 0 17,5 
0 1,5 0 0,25 0 1 32,5 
 
SOLUÇÃO 
Variáveis 
básicas (VB) 
Variáveis 
não-básicas 
(VNB) 
Valor de Z 
 
- VB: Procurar colunas (no meio da 
tabela) em que aparece apenas os 
números 0 e 1 e com o número 1 
aparecendo uma vez só na coluna. As 
variáveis associadas a essas colunas são 
chamadas variáveis básicas. 
Z x1 x2 xF1 xF
2 
xF3 b 
1 -0,5 0 1,25 0 0 12,5 
0 0,5 1 0,25 0 0 2,5 
0 5,5 0 -0,25 1 0 17,5 
0 1,5 0 0,25 0 1 32,5 
 
Para achar o valor das variáveis básicas é 
preciso ver até onde o número 1 da coluna 
vai e associar com o valor de b da linha. 
Dessa forma: 
Nova primeira 
l inha 
Nova terceira 
l inha 
Nova quarta 
l inha 
Z x1 x2 xF1 xF
2 
xF3 b 
1 -0,5 0 1,25 0 0 12,5 
0 0,5 1 0,25 0 0 2,5 
0 5,5 0 -0,25 1 0 17,5 
0 1,5 0 0,25 0 1 32,5 
 
 
Z x1 x2 xF1 xF
2 
xF3 b 
1 -0,5 0 1,25 0 0 12,5 
0 0,5 1 0,25 0 0 2,5 
0 5,5 0 -0,25 1 0 17,5 
0 1,5 0 0,25 0 1 32,5 
 
Z x1 x2 xF1 xF
2 
xF3 b 
1 -0,5 0 1,25 0 0 12,5 
0 0,5 1 0,25 0 0 2,5 
0 5,5 0 -0,25 1 0 17,5 
0 1,5 0 0,25 0 1 32,5 
 
Logo, 
x2 = 2,5 
xF2 = 17,2 
xF3 = 32,5 
 
- VNB: Agora para dizer que 1Z = 12,5 é 
preciso zerar todas as variáveis da função 
objetivo (x1, x2, xF1, xF2, xF3), sendo que 
x2, xF2, xF3 já estão zeradas. Logo, nesse 
caso, é preciso zerar x1 e xF1. Logo, essas 
variáveis são consideradas não-básicas. 
Para que dê zero x1 = 0 e xF1 = 0, pois ao 
multiplicar pelos respectivos valores na 
função objetivo (no caso -0,5 e 1,25 
respectivamente) o resultado dará zero. 
 
 
 
ENTÃO: 
Variáveis 
básicas (VB) 
Variáveis 
não-básicas 
(VNB) 
Valor de Z 
x2, xF2, xF3 x1, xF1 Z 
2,5; 
17,5;32,5 
0;0 12,5 
 
ESSA SOLUÇÃO NÃO É ÓTIMA!!! 
Por que? 
Pois na função objetivo ainda permanece 
um valor negativo (-0,5). Para ser ótima 
todos os valores têm que ser positivos ou 
zero. 
vii. Recalcular 
Z x1 x2 xF1 xF
2 
xF3 b 
1 -0,5 0 1,25 0 0 12,5 
0 0,5 1 0,25 0 0 2,5 
0 5,5 0 -0,25 1 0 17,5 
0 1,5 0 0,25 0 1 32,5 
 
I. Olhar na primeira linha (linha 
da função objetivo) e identificar 
o número de menor valor, que 
no nosso caso é o -0,5. Logo, a 
variável que entra é x1.  
Destacar a COLUNA da variável 
x1. 
II. Identificar a linha que sai (linha 
pivô) 
2,5/0,5 = 5 
17,5/5,5 = 3,18 
32,5/1,5 = 21,67 
III. Identificar o elemento pivô 
IV. Calcular NLP 
0 5,5 0 -0,25 1 0 17,5 
÷ 
5,5 (elemento pivô) 
= 
0 1 0 -0,045 0,182 0 3,18 
Menor valor positivo 
Corres-
ponde 
à 3ª 
l inha 
NLP 
V. Cálculo das novas primeiras 
linhas 
Nova 1ª linha: 
0 1 0 -0,045 0,182 0 3,18 
x 
0,5 
= 
0 0,5 0 -0,023 0,091 0 1,59 
+ 
1 -0,5 0 1,25 0 0 12,5 
= 
1 0 0 1,227 0,091 0 14,09 
 
Nova 2ª linha: 
0 1 0 -0,045 0,182 0 3,18 
x 
-0,5 
= 
0 -0,5 0 0,023 -0,091 0 -1,59 
+ 
0 0,5 1 0,25 0 0 2,5 
= 
0 0 1 0,273 -0,091 0 0,91 
 
Nova 4ª linha: 
0 1 0 -0,045 0,182 0 3,18 
x 
-1,5 
= 
0 -1,5 0 0,068 -0,273 0 -4,77 
+ 
0 1,50 0,25 0 1 32,5 
= 
0 0 0 0,318 -0,273 1 27,73 
 
 
VI. Nova tabela 
Z x1 x2 xF1 xF2 xF3 b 
1 0 0 1,227 0,091 0 14,09 
0 0 1 0,273 -0,091 0 0,91 
0 1 0 -0,045 0,182 0 3,18 
0 0 0 0,318 -0,273 1 27,73 
 
SOLUÇÃO: 
 
VB: x1, x2, xF3 
x1= 3,18 
x2= 0,91 
xF3= 27,73 
 
VNB: xF1, xF2 
xF1 = 0 
xF2= 0 
 
Valor de Z =14,09 
 
SOLUÇÃO ÓTIMA!!!! 
No campo da função objetivo só 
há valores positivos. 
 
EXEMPLO DE RESOLUÇÃO 
GRÁFICA 
 
Ex.: Minimizar Z = 2x1 + 3x2 
Sujeito a: 
x1 + x2 ≥ 5 
5x1 + x2 ≥ 10 
x1 ≤ 8 
x1 ≥ 0 
x2 ≥ 0 
 
i. Transformar as 
desigualdades das 
restrições técnicas em 
igualdades. 
x1 + x2 = 5 (1ª) 
5x1 + x2 = 10 (2ª) 
x1 = 8 (3ª) 
 
ii. Determinar os pontos 
(para traçar uma reta e 
jogar no gráfico) 
 
NLP x oposto 
do coeficiente 
da variável que 
entra (x1) 
Soma do 
resultado com 
a linha atual 
Restrições 
técnicas 
Restrições de não-negatividade 
1ª restrição: 
 
A (0,5) 
B (5, 0) 
 
 
2ª restrição: 
C (0, 10) 
D (2,0) 
3ª restrição: 
F (8, 0) 
G (8, 2) 
 
 
 
 
iii. Marcar os pontos no 
plano cartesiano 
- Lembrando que: x1 = X e x2= Y 
 
 
 
 
 
 
iv. Reescrever as 
inequações e encontrar 
as soluções das 
mesmas. 
 
IMPORTANTE: PONTO E (1,1) - ponto para 
verificar onde estão as soluções das 
inequações 
x1 + x2 ≥ 5 5x1 + x2 ≥ 10 x1 ≤ 8 
 
 
- Se x1=1 e x2=1, 2 ≥ 5 (ESSA AFIRMAÇÃO É 
FALSA) – Isso quer dizer que o ponto E (1,1) 
não pertence ao conjunto de soluções dessa 
inequação. 
- Se x1=1 e x2=1, 6 ≥ 10 (ESSA AFIRMAÇÃO 
É FALSA) – Isso quer dizer que o ponto E 
(1,1) não pertence ao conjunto de soluções 
dessa inequação. 
- Se x1=1 e x2=1, 1 ≤ 8 (ESSA AFIRMAÇÃO É 
VERDADEIRA) – Isso quer dizer que esse 
ponto E (1,1) pertence ao conjunto de 
soluções dessa inequação. 
 
- No gráfico: 
Devemos marcar o ponto E (1,1). E rebater 
de acordo com as inequações. 
 
 
x1 = 0 
x2 = 0 
Se x1 = 0, 
x2 = 5 
Se x2 = 0, 
x1 = 5 
 
Como essa restrição só tem x1, então x1 
será sempre 8, o que vai variar é x2. Pra x2 
qualquer valor pode ser atribuído, nesse 
caso atribuiu-se 0 e 2. 
E 1 
1 
Como a afirmação é 
falsa para as duas 
inequações, então o 
conjunto de soluções 
dessas inequações 
está do lado oposto 
ao ponto. 
(Considerando a reta 
das inequações) 
Como a 
afirmação é 
verdadeira 
para a 
inequação, 
então o 
conjunto de 
soluções 
está do 
mesmo lado 
do ponto. 
(Consideran
do a reta da 
inequação) 
As soluções viáveis 
são apenas valores 
positivos (não – 
negatividade) 
SOLUÇÕES VIÁVEIS 
O QUE QUEREMOS? 
MINIMIZAR! Então agora a função de 
minimizar será trabalhada. 
Z = 2x1 + 3x2 
- Se existe exatamente uma solução ótima, 
então deve ser uma solução factível em um 
vértice. 
- No caso nos pontos (5,0), (8,0), (0,10) e 
(1,6;3,8) agora devemos calcular qual dará 
o menor resultado. 
Z = 2(5) + 3(0) = 10 
Z = 2(8) + 3(0) = 16 
Z = 2(0) + 3(10) = 30 
Z 2(1,6) + 3(3,8) = 14,6 
 
PROGRAMAÇÃO BINÁRIA E INTEIRA (PI) 
PI: Segue os princípios da PL, contudo todas 
as variáveis decisórias são inteiras (0, 1, 
2...). 
Ex. 1: Uma pessoa como um todo deve ser 
designada para um determinado trabalho 
(item que não pode ser dividido). 
Ex. 2: Problema de escalonamento de 
pessoal, talhões a serem cortados, número 
de tratores a serem comprados. 
PB: Todas as variáveis de decisão são 
binárias (podem assumir valores 1 – quando 
a característica de interesse está presente 
ou 0, caso contrário) 
Ex.: Problema de designação de tarefas, 
Problema do caixeiro viajante, Programação 
de produção, Problema do caminho mais 
curto. 
PIM (Programação Inteira Mista): Variáveis 
inteiras e contínuas usadas em um modelo. 
 
MÉTODO SIMPLEX X VARIÁVEIS INTEIRAS 
• Às vezes tendemos a resolver os 
problemas de PI pelo método Simplex e 
depois arredondar a solução para um valor 
inteiro próximo. 
• Porém essa solução arredondada pode 
não ser viável ou se for viável pode não ser 
o valor ótimo (ideal). 
• O algoritmo mais usado para encontrar a 
solução de PI é o Branch and Bound. 
Branch and Bound 
• Ideia do algoritmo: Subdividir o conjunto 
de todas as soluções viáveis em diversos 
subconjuntos e, para cada um, obter um 
limite inferior ou superior para o valor da 
função-objetivo das soluções dentro do 
respectivo subconjunto. 
Aqueles subconjuntos cujos limites 
inferiores excedam o limite superior 
corrente no valor da função-objetivo serão, 
então, excluídos de futuras considerações. 
Um subconjunto que seja excluído por esta 
ou outras razões legítimas é dito ser 
sondado. 
• EXEMPLO: 
Maximizar (Z) = 5x1+8x2 
Sujeito a: 
x1 + x2 ≤ 6 
5x1+ 9x2 ≤ 45 
x1, x2 € Z⁺ (valores inteiros) 
No gráfico: 
i. Traçar no gráfico as retas 
referentes às restrições. Para 
isso, definir pontos para cada 
restrição. 
1ª restrição: 
x1 + x2 ≤ 6 
A (0,6) 
B (6,0) 
2ª restrição: 
5x1+ 9x2 ≤ 45 
A (0, 5) 
B (9, 0) 
 
• Utilizando o ponto E (1,1), encontramos a 
região de soluções viáveis e a solução ótima 
6 
6 
x1 + x2 ≤ 6 
 
5 
9 
5x1+ 9x2 ≤ 45 
 
Solução ótima PL 
de PL (nos vértices) – que deseja a 
MAXIMIZAÇÃO. 
x1= 2,25 
 x2=3,75 
Valor de Z = 41,25 Não é inteiro. 
Branch 
Divisão em dois conjuntos “inteiros” 
x2 ≤ 3 ; x2 ≥ 4 (não pode ser 3,75) 
- Obter o valor ótimo para cada conjunto: 
x2 ≤ 3 ; x2 ≥ 4  são duas novas restrições 
(são dois subproblemas) 
1º subproblema: 
(Z) = 5x1+8x2 
Sujeito a: 
x1 + x2 ≤ 6 
5x1+ 9x2 ≤ 45 
x2 ≥ 4 
x1, x2 € Z⁺ (valores inteiros) 
 SOLUÇÃO ÓTIMA: x1=1,8 e x2=4 (no 
gráfico, quando x2=3, x1=3 – 
soluções no vértice) 
Se x1=3 e x2=3  Z = 41 
2º subproblema: 
(Z) = 5x1+8x2 
Sujeito a: 
x1 + x2 ≤ 6 
5x1+ 9x2 ≤ 45 
x2 ≤ 3 
x1, x2 € Z⁺ (valores inteiros) 
 
 SOLUÇÃO ÓTIMA: x1=3 e x2=3 (no 
gráfico, quando x2=3, x1=3 – 
soluções no vértice) 
Se x1=3 e x2=3  Z = 39 – Esta solução é 
uma solução inteira, que satisfez todas as 
restrições do problema. (É ARMAZENADA – 
melhor solução encontrada ATÉ O 
MOMENTO, logo todo valor que for 
encontrado abaixo de 39 não interessa). 
Porém, o primeiro subproblema apresentou 
um valor maior de Z (41), mesmo não 
atendendo todas as restrições. Então ele 
será mais uma vez RAMIFICADO, gerando 
outros dois subproblemas, para isso serão 
geradas outras duas restrições em X1 
(x1=1,8), visto que essa variável não é 
inteira (é a que precisa ser trabalhada). 
Novas restrições: x1 ≥ 2; x1 ≤ 1 
3º subproblema: 
(Z) = 5x1+8x2 
Sujeito a: 
x1 + x2 ≤ 6 
5x1+ 9x2 ≤ 45 
x2 ≥ 4 
x1 ≥ 2 
x1, x2 € Z⁺ (valores inteiros) 
 INVIÁVEL (com x1=2 os pontos 
saem do espaço de soluções 
viáveis) 
4º subproblema: 
(Z) = 5x1+8x2 
Sujeito a: 
x1 + x2 ≤ 6 
5x1+ 9x2 ≤ 45 
x2 ≥ 4 
x1 ≤ 1 
x1, x2 € Z⁺ (valores inteiros) 
 SOLUÇÃO ÓTIMA: x1=1 e x2= 4,44 
Z= 40,52 – viável. 
 
 
x2 ≤ 3 
x2 ≥ 4 
 
A RESTRIÇÃO ORIUNDA DO 
SUBPROBLEMA 1 
PERMANECE, POIS ESSES 
NOVOS SUBPROBLEMAS 
SÃO UMA RAMIFICAÇÃO 
DO SUBPROBLEMA 1. !!!!!! 
O 4º subproblema é viável, porém não 
atende todas as restrições (x2 não é inteiro), 
logo ela será RAMIFICADA e a partir dela 
serão gerados outros 2 subproblemas. E a 
variável que gerará as restrições é a variável 
x2. 
Novas restrições: x2 ≥ 5 e x2 ≤ 4 
5º subproblema: 
(Z) = 5x1+8x2 
Sujeito a: 
x1 + x2 ≤ 6 
5x1+ 9x2 ≤ 45 
x2 ≥ 4 (restrição redundante, pode retirar) 
x1 ≤ 1 
x2 ≥ 5 
x1, x2 € Z⁺ (valores inteiros) 
 SOLUÇÃO ÓTIMA: x2=5, x1 = 0 
Z = 40 É MELHOR SOLUÇÃO DE PI. 
6º subproblema: 
(Z) = 5x1+8x2 
Sujeito a: 
x1 + x2 ≤ 6 
5x1+ 9x2 ≤ 45 
x2 ≥ 4 
x1 ≤ 1 
x2 ≤ 4 
 SOLUÇÃO ÓTIMA: x2=4, x1= 1 
Z = 37 
 
CONSIDERAÇÕES: 
• O branch and bound pode originar em 
casos que temos que testar todas as 
combinações possíveis. Sendo impossível a 
resolução em computadores tradicionais, 
tornando o método ineficiente. Pra isso 
existem as METAHEURÍSTICAS. 
• O branch and bound é o simplex rodado 
repetidamente até encontrar uma soluçãoótima e inteira para o problema de PI.  
Programa LINGO (funções @gin para PPI e 
@bin para PPB). 
DUALIDADE 
• Todo problema de PL tem uma 
formulação simétrica, o que é muito útil 
para determinar como a função objetivo 
altera-se, se uma das restrições mudar 
ligeiramente, mantendo todo o resto igual. 
• Esta formulação simétrica é chamada de 
problema dual. 
• Contém exatamente os mesmos dados 
do problema original (primal), mas é 
reorganizado de forma simétrica. 
CARACTERÍSTICAS: 
• Quando o problema é maximização a 
função objetivo do dual é minimizada 
(seria maximizado se no problema primal 
fosse a minimização). 
• O número de variáveis (variáveis duais) é 
igual ao número de restrições do primal, e 
todas as variáveis duais são positivas ou 
nulas. 
• O número de restrições é igual ao 
número de variáveis no primal. 
• Os coeficientes em cada coluna do 
problema primal, tornam-se os coeficientes 
das linhas correspondentes do dual 
(primeira coluna torna-se a primeira linha, 
a segunda coluna torna-se a segunda linha, 
etc.). 
• Os coeficientes da função objetivo no 
primal tornam-se os coeficientes do lado 
direito das restrições do dual, e vice-versa. 
• A direção das desigualdades é invertida. 
• O dual do dual é o primal (simetria). 
• O teorema da dualidade afirma que o 
melhor valor da função objetivo do dual 
deve ser igual ao melhor valor da função 
objetivo do primal. 
• Na terminologia da programação linear, 
as variáveis decisórias do dual são os 
preços-sombra. 
Ou seja, 
igual a 4 
• O termo “sombra” é um lembrete de que 
estes preços não são necessariamente 
iguais aos preços de mercado dos recursos. 
• Os preços-sombra medem o quanto o 
melhor valor da função objetivo seria 
alterado se o lado direito de uma restrição 
mudasse em uma unidade, com as outras 
coisas permanecendo iguais (o quanto irá 
aumentar no valor final da função objetiva, 
caso aumente ou diminua 1 unidade do 
produto disponível) 
EXEMPLO: 
MAXIMIZAR (Z) = 2x1 + 3x2 
Sujeito a: 
x1 + x2 ≤ 10 1x1 + 1x2 ≤ 10 
x1 ≤ 6  1x1 + 0x2 ≤ 6 
2x1 + x2 ≤ K 2x1 + 1x2 ≤ K 
 
Primal: 2 variáveis decisórias e 3 
restrições 
 
 
 
Dual: 3 variáveis decisórias e 2 restrições 
MINIMIZAR (Z’) = 10y1 + 6y2 +Ky3 
Sujeito a: 
1y1 + 1y2 + 2y3 ≥ 2 
1y1 + 0y2 + 1y3 ≥ 3 
 
*Sendo a função objetiva igual a Z e y2=5 (y2 
está relacionada com a 2ª restrição primal), 
caso seja acrescentado uma unidade na 
restrição, a função objetiva será Z + 5 
(PREÇO SOMBRA). 
 
PROGRAMAÇÃO DINÂMICA (PD) 
FUNDAMENTOS E APLICAÇÕES EM 
MANEJO FLORESTAL 
PRELIMINARES A PD é uma técnica de 
programação matemática, desenvolvida 
por Belman, para solução de problemas de 
decisão que possam ser subdivididos em 
subproblemas inter-relacionados. Portanto 
o PD envolve: estágios, estados e decisões. 
Ao contrário da PL, na PD não existe uma 
formulação padrão e nem um algoritmo 
único, como simplex, para resolver 
qualquer PPD. Porém existem duas 
características comuns em todo modelo de 
PD: uma relação de recorrência construída 
com base no princípio de OTIMALIDADE de 
Belman. 
 Uma vez que estabelecido a política 
ótima (caminho/alternativa ótima), 
qualquer subpolítica (ou parte 
desse caminho) é ótima sem 
necessidade de fazer nenhuma 
análise. 
 A relação de recorrência pode ser 
uma ou mais fórmulas lineares ou 
não-lineares (ou ambas), que 
relacionam estágios, estados e 
decisões. Podem, também, incluir 
componentes estocásticos. 
 A relação de recorrência é a função 
objetivo de PD. 
Na PD saímos de um estado atual (com 
diferentes alternativas de decisão), cada 
alternativa gera uma transformação 
levando à uma mudança de estado e de 
cada transformação têm-se um retorno. 
Aplicações da PD em Manejo: 
- Conversão de árvores em multiprodutos; 
- Otimização de corte em serraria 
(desdobro) 
- Determinação do ótimo regime de 
desbastes; 
- Substituição de equipamentos; 
- Análise de projetos de investimento; 
- Problemas de transporte da madeira; 
EXEMPLO: 
Seja uma prancha de madeira a ser 
subdividida em peças conforme a tabela a 
seguir, estabeleça uma relação de 
recorrência e determine o desdobro ótimo. 
Vamos assumir que qualquer quantidade 
Variáveis decisórias 
Restrições 
P
R
I
M
A
L 
Restrições 
D
U
A
L 
produzida pode ser vendida, para qualquer 
tipo de sortimento. 
Produto Comprimento Valor($) 
1 1 10 
2 2 20,5 
3 3 31 
4 4 41,5 
5 5 52 
 
1º Calcular o MDC dos comprimentos 
possíveis (1,2,3,4,5 metros) MDC = 1. O 
MDC será o intervalo de estágio, resultando 
em: N (número de estágios) = L 
(comprimento da peça) / K (intervalo de 
estágio) N=L/K = 6/1 = 6 ESTÁGIOS. 
0 1 2 3 4 5 6 
 
2º Relação de recorrência dos problemas: 
Obs: A intenção é maximizar o lucro 
MAX fn = Rnj + fn-j 
Sendo j = 0,1,2,3,4,5,6 e n = 0,1,2,3,4,5,6 
Rnj = valor de um sortimento j, obtido no 
estágio n 
fn-j = valor da relação de recorrência (ou 
função no estágio relacionado) 
fn = valor da função no estágio n 
SOLUÇÃO: 
No estágio n=0 
Fn=f0=0 
0 1 2 3 4 5 6 
 
Fn=f0=0 
No estágio n=1 
F1= f1= R1,1 + f 1-1 = R1,1 + f0 = 10 + 0 = 10 
0 1 2 3 4 5 6 
 
 
 
No estágio n=2 
F2 = R1,2 + f2-1 = 10 + 10 = 20 
 R2,2 + f2-2 = 20,5 + 0 = 20,5  maior 
0 1 2 3 4 5 6 
 
No estágio n=3 
F3= R1,3 + f3-1 = R1,3 + f2 = 10 + 20,5 = 30,5 
 R2,3 + f3-2 = 20,5 + 10 = 30,5 
 R3,3 + f3-3 = 31 + 0 = 31  maior 
0 1 2 3 4 5 6 
 
No estágio n =4 
F4=R1,4 + f4-1 = 10 + 31 = 41 
 R2,4 + f4-2 = 20,5 + 20,5 = 41 
 R3,4 + f4-3 = 31 + 10 = 41 
 R4,4 + f4-4 = 41,5 + 0 = 41,5  maior 
0 1 2 3 4 5 6 
 
No estágio n=5 
F5=R1,5 + f5-1= 10 + 41,5 = 51,5 
 R2,5 + f5-2 = 20,5 + 31 = 51,5 
 R3,5 + f5-3 = 31 + 20,5 = 51,5 
 R4,5 + f5-4 = 41,5 + 10 = 51,5 
 R5,5 + f5-5 = 52  maior 
0 1 2 3 4 5 6 
 
No estágio n=6 
F6= R1,6 + f6-1= 10 + 52 = 62 
 R2,6 +f6-2= 20,5 + 41,5 = 62  
 R3,6 +f6-3 = 31 + 31 = 62 
 R4,6 +f6-4 = 41,5 + 20,5 = 62 
 R5,6 +f6-5 = 52 + 10 = 62 
0 1 2 3 4 5 6 
 
 
Qualquer uma 
das soluções é 
ótima