Universidade Federal de Itajubá – UNIFEI
Instituto de Recursos Naturais - IRN
Programação Linear
Benedito C. Silva
Programação Linear
É técnica de otimização mais empregada na área de
Recursos Hídricos, devido às seguintes razões:
1. Flexibilidade para adaptação a uma grande variedade de
problemas
2. Maior Facilidade de entendimento, comparada com outras
técnicas
3. Capacidade de tratar problemas de grande porte, comuns
em recursos hídricos
4. Disponibilidade de pacotes computacionais, em nível
comercial, para pronta utilização
Linear: refere-se à necessidade de haver relações
lineares entre as variáveis. Ou seja, o problema é
descrito por equações lineares
Programação: refere-se ao planejamento de
atividades
Vamos imaginar o seguinte problema:
Deseja-se cultivar milho e feijão em uma propriedade de área igual a 100 ha, onde a
água para irrigação é fornecida por um reservatório através de um sistema de
bombeamento
Reservatório
bombeamento
Área 1: X1 ha
(milho)
Área 2: X2 ha
(feijão)
A receita líquida por unidade de área cultivada é de,
Milho: 100 R$/ha
Feijão: 80 R$/ha
Pergunta: Considerando que não há restrição hídrica, qual a
área a ser cultivada de cada cultura para que o agricultor
maximize sua receita?
As variáveis de decisão são:
X1 = área da cultura de milho
X2 = área da cultura de feijão
R = receita obtida com as duas culturas
O problema pode ser escrito como:
MáximizarR  100 X1  80 X2
Função Objetivo
sujeito a
X1  X2  100
onde
X1, X2  0
Principais restrições
Restrições de não negatividade
este é o formato da
Programação Linear
MáximizarR  100 X1  80 X2
sujeito a
X1  X2  100
onde
X1, X2  0
Métodos de Solução
Métodos Geométricos
Vamos supor que desejamos determinar os
pontos que satisfazem a:
X2
(0,100)
Máx R  100 X1  80 X2
s. a
X1+X2 ≤ 100
X1  X2  100
onde
X1, X2  0
X1 ≥ 0
região factível
X1
X2 ≥ 0
(100,0)
Os pontos da área hachurada obedecem às
restrições....mas o máximo ou mínimo da Função
Objetivo (FO) está nos vértices do plano definido pelas
diversas restrições do problema:
X2
(0,100)
região factível
X1
(100,0)
Teorema muito importante:
O Máximo ou um Mínimo de uma PL, se existir, irá
ocorrer necessariamente num vértice (corner point) da
região de soluções viáveis ou factíveis, dado pelo conjunto
de restrições
Qual o ponto de máximo rendimento para o problema?
Para o ponto A temos
X1 = 20 e X2 = 50
R=100.20 + 80.50 = 6000
Para o ponto B (X1=0 e X2=100), R=8000
Para o ponto C (X1=100 e X2=0), R=10000 (máximo)
X2
B (0,100)
Direção de crescimento da FO
A (20,50)
Ponto de máxima
receita
X1
C (100,0)
Problema 2: Introdução da limitação do volume d’água
O consumo de água por unidade de área para as culturas é,
Milho: 3,0 dam3/ha
Feijão: 1,5 dam3/ha
A disponibilidade de água no reservatório para o período de estiagem é 240 dam3
A formulação do problema fica:
Máx R  100 X1  80 X2
s. a
X1  X2  100 (limite de área total)
3,0 X1  1,5 X2  240 (limite de volume disponível)
onde
X1, X2  0
Solução gráfica
X2
D (0,160)
Reta da FO, coef.
inalterados
B (0,100)
Novo ponto de
máxima receita
F (60,40)
X1
E (80,0)
C (100,0)
Problema 3: Introdução da cobrança pelo uso da água
A aquisição de água no reservatório terá um custo unitário igual a R$ 20/dam3
A receita passa ser calculada por:
R = 100 X1 – 20 (3 X1) + 80 X2 – 20 (1,5 X2)
R = 40 X1 + 50 X2
A formulação do problema fica:
Máx R  40 X1  50 X2
s. a
X1  X2  100
3,0 X1  1,5 X2  240
onde
X1, X2  0
Solução gráfica
X2
D (0,160)
B (0,100)
Novo ponto de
máxima receita
Reta da FO, coef.
alterados
X1
E (80,0)
C (100,0)
Comparação das Soluções
Tabela.2 - Consumo Hídrico e Receita Líquida para cada Cultura
Cultura
Milho (X1)
Feijão (X2)
Consumo
Hídrico
(dam3/ha)
3,0
1,5
Receita
Líquida
(R$/ha )
100
80
Solução Ótima(ha)
PL1
100
0
PL2
60
40
PL3
0
100
Área total utilizada(ha)
100
100
100
Água total utilizada (dam3)
300
240
150
Enquanto a água não tinha limite (PL1) ou custo zero (PL2):
X1> X2 na solução ótima, embora o milho exija mais água
Quando houve custo para a água (PL3): X2>X1 na sol.ótima
O método gráfico é de fácil aplicação,
mas só é viável de ser utilizado
quando:
• se existirem duas ou no máximo três variáveis de decisão;
• se existirem poucas equações de restrição (um problema
com muitas restrições possui muitos vértices para serem
testados!)