202183_152110_Programação+Matemática+-+Parte+II+-+Programação+Linear

Prévia do material em texto

Ciência da Computação
Programação Linear
Ciência da Computação
Programação Linear (PL)
• Um aspecto importante de problemas 
envolvendo decisões é o de otimização, quando 
se procura estabelecer quais as maneiras mais 
eficientes de utilizar os recursos disponíveis 
para atingir certos objetivos
• Em geral, trata-se de recursos limitados e a sua 
utilização criteriosa possibilita melhorar o 
rendimento ou produtividade do processo em 
estudo
Programação Matemática - Prof. Malomar Alex Seminotti 2
Ciência da Computação
Programação Linear
• Um problema de Programação Linear (PL) é um 
problema de programação matemática em que 
as funções-objetivo e de restrição são lineares
• É uma das técnicas mais utilizadas na 
abordagem de problemas em PO
• A simplicidade do modelo envolvido e a 
disponibilidade de uma técnica de solução 
programável em computador facilitam sua 
aplicação
Programação Matemática - Prof. Malomar Alex Seminotti 3
Ciência da Computação
Programação Linear (PL)
• A tarefa da PL consiste na maximização ou 
minimização de uma função linear, denominada 
Função Objetivo, respeitando-se um sistema 
linear de igualdades ou desigualdades, que 
recebem o nome de Restrições do Modelo
• As restrições determinam uma região a qual se 
dá o nome de Conjunto Viável
• A melhor das soluções viáveis (soluções que 
pertencem ao Conjunto Viável), ou seja, aquela 
que maximiza ou minimiza a função objetivo, 
denomina-se Solução Ótima
Programação Matemática - Prof. Malomar Alex Seminotti 4
Ciência da Computação
Programação Linear
• O objetivo da PL é determinar a solução ótima
• Para a resolução de um Problema de 
Programação Linear (PPL) dois passos são 
necessários:
– O primeiro é a Modelagem do problema, seguindo-se 
o método de solução do modelo
– No caso de um PPL o método mais utilizado é o 
Método Simplex
Programação Matemática - Prof. Malomar Alex Seminotti 5
Ciência da Computação
Programação Linear
• A Programação Linear (PL) visa 
fundamentalmente encontrar a melhor solução 
para problemas que tenham seus modelos 
representados por expressões lineares
• As aplicações mais conhecidas são feitas em 
sistemas estruturados, como os de produção, 
finanças, controles de estoques etc.
Programação Matemática - Prof. Malomar Alex Seminotti 6
Ciência da Computação
Programação Linear
• Não existem técnicas precisas capazes de 
permitir o estabelecimento do modelo de um 
problema, pois a modelagem envolve aspectos 
de arte, ou seja, pode ser melhorada com a 
prática e observação
• Para modelar uma situação geral é importante 
se ter experiência e capacidade de análise e 
síntese
Programação Matemática - Prof. Malomar Alex Seminotti 7
Ciência da Computação
Hipóteses em PL
• Proporcionalidade: todos os retornos / custos e 
recursos utilizados variam proporcionalmente à 
variável de decisão (não há economia de 
escala)
• Aditividade: o efeito total de quaisquer duas 
variáveis é a soma dos efeitos individuais (não 
há sinergia ou efeito de substituição). 
Exemplo: o custo total é a soma dos custos 
individuais
Programação Matemática - Prof. Malomar Alex Seminotti 8
Ciência da Computação
Hipóteses em PL
• Divisibilidade: as variáveis de decisão podem 
assumir valores fracionados. Se essas variáveis 
só puderem assumir valores inteiros o problema 
é de programação inteira (PI)
• Certeza (determinístico): todos os parâmetros 
do modelo são constantes conhecidas (não são 
variáveis aleatórias)
Programação Matemática - Prof. Malomar Alex Seminotti 9
Ciência da Computação
Programação Matemática
• Um problema de programação matemática é um
problema de otimização no qual o objetivo e as
restrições são expressos como funções 
matemáticas e relações funcionais, como segue:
Programação Matemática - Prof. Malomar Alex Seminotti 10
Ciência da Computação
Programação Matemática
• Um problema de programação matemática é 
linear se a função objetivo f (x1,x2,...,xn) e cada 
uma das funções que representam as restrições 
forem lineares, isto é, na forma abaixo:
Programação Matemática - Prof. Malomar Alex Seminotti 11
Ciência da Computação
Variáveis de Decisão
• x1,x2,...,xn são as chamadas variáveis de decisão
• As variáveis de decisão são aqueles valores que
representam a resposta do problema, e que se 
pode escolher (decidir) livremente
• As variáveis de decisão representam as opções que 
um administrador tem para atingir um objetivo:
– Quanto produzir para maximizar o lucro?
– Quanto comprar de uma ação para minimizar o risco
da carteira?
Programação Matemática - Prof. Malomar Alex Seminotti 12
Ciência da Computação
Solução
• No campo de Programação Linear, a Solução é 
qualquer especificação de valores para as variáveis 
de decisão, não importando se esta especificação 
se trata de uma escolha desejável ou permissível.
• A Solução Ótima é uma solução viável especial
• Dentre todas as soluções viáveis, aquela(s) que 
produzir(em) o valor da função objetivo otimizado é
chamada de ótima
• A grande questão é como determinar a solução 
ótima
Programação Matemática - Prof. Malomar Alex Seminotti 13
Ciência da Computação
Solução
• Solução: qualquer especificação de valores (dentro
do domínio da função-objetivo, f) para as variáveis 
de decisão, independente de se tratar de uma 
escolha desejável ou permissível
• Solução Viável: uma solução em que todas as 
restrições são satisfeitas
• Solução Ótima: uma solução viável que tem o valor
mais favorável da função-objetivo, isto é, maximiza
ou minimiza a função-objetivo em toda a região 
viável, podendo ser única ou não
Programação Matemática - Prof. Malomar Alex Seminotti 14
Ciência da Computação
Modelagem Matemática
• O processo de modelagem deve considerar as 
seguintes condições:
– Variáveis do problema: são fatores controláveis e 
quantificáveis. Representam as variáveis de decisão
– Parâmetros do problema: são os valores fixos do 
problema. Os valores financeiros dos dados os ou 
custos fixos da produção são alguns exemplos
– Restrições: são aspectos que limitam a combinação 
de valores e variáveis de soluções possíveis
– Função objetivo: é uma função que busca 
maximizar ou minimizar , dependendo do objetivo do 
problema. Ela é essencial na definição da qualidade 
da solução em função das incógnitas encontradas
Programação Matemática - Prof. Malomar Alex Seminotti 15
Ciência da Computação
Modelagem Matemática
• O modelo matemático de programação linear é 
composto de uma função objetiva linear e de 
restrições técnicas representadas por um
grupo de inequações também lineares
• Exemplo: função objetivo a ser maximizada
Lucro = 2x1 + 3x2
Programação Matemática - Prof. Malomar Alex Seminotti 16
Ciência da Computação
Modelagem Matemática
• As variáveis controladas ou variáveis de decisão 
são x1 e x2
• A função objetivo ou função e eficiência mede o 
desempenho do sistema, no caso a capacidade 
de gerar lucro, para cada solução apresentada
• O objetivo é maximizar o lucro
• As restrições garantem que essas soluções 
estão de acordo com as limitações técnicas 
impostas pelo sistema
Programação Matemática - Prof. Malomar Alex Seminotti 17
Ciência da Computação
Modelagem Matemática
• As duas últimas restrições exigem a não 
negatividade das variáveis de decisão, o que 
deverá acontecer sempre que a técnica de 
abordagem for a de programação linear
• A construção do modelo matemático, no caso 
um modelo linear, é a parte mais complicada
• Não há regra fixa para esse trabalho, mas a 
seguir há um roteiro que ajuda a ordenar o 
raciocínio:
Programação Matemática - Prof. Malomar Alex Seminotti 18
Ciência da Computação
Roteiro
a) Quais as variáveis de decisão?
• Explicitar as decisões que devem ser tomadas e 
representar as possíveis decisões através de 
variáveis, chamadas variáveis de decisão
• Por exemplo, se o problema é de programação 
de produção, as variáveisde decisão são as 
quantidades a produzir no período
• Nas descrições sumárias de sistemas, isso fica 
claro quando se lê a questão proposta, isto é, a 
pergunta do problema
Programação Matemática - Prof. Malomar Alex Seminotti 19
Ciência da Computação
Roteiro
b) Qual o objetivo?
• Aqui se deve identificar o objetivo da tomada de 
decisão
• Ele aparece geralmente na forma da 
maximização de lucros ou receitas, minimização 
de custos, perdas etc.
• A função objetivo é a expressão que calcula o 
valor do objetivo (lucro, custo, receita, perda 
etc.), em função das variáveis de decisão
Programação Matemática - Prof. Malomar Alex Seminotti 20
Ciência da Computação
Roteiro
c) Quais as restrições?
• Cada restrição imposta na descrição do sistema 
deve ser expressa como uma relação linear 
(igualdade ou desigualdade), montadas com as
variáveis de decisão
• Também não se deve esquecer das restrições 
de não negatividade
Programação Matemática - Prof. Malomar Alex Seminotti 21
Ciência da Computação
Exemplo
• Certa empresa fabrica dois produtos P1 e P2. O 
lucro unitário do produto P1 é de 1.000 unidades 
monetárias e o lucro unitário de P2 é de 1.800 
unidades monetárias. A empresa precisa de 20 
horas para fabricar uma unidade de P1 e de 30 
horas para fabricar uma unidade de P2. O tempo 
anual de produção disponível para isso é de 
1.200 horas. A demanda esperada para cada 
produto é de 40 unidades anuais para P1 e 30 
unidades anuais para P2
Programação Matemática - Prof. Malomar Alex Seminotti 22
Ciência da Computação
Exemplo
• Qual é o plano de produção para que a empresa 
maximize seu lucro nesses itens? Construa o 
modelo de programação linear para esse caso
Programação Matemática - Prof. Malomar Alex Seminotti 23
Ciência da Computação
Exemplo
• Seguindo o roteiro:
a) Quais as variáveis de decisão?
O que deve ser decidido é o plano de produção, isto 
é, quais as quantidades anuais que devem ser 
produzidas de P1 e P2.
Portanto, as variáveis de decisão serão x1 e x2
x1 → quantidade anual a produzir de P1
x2 → quantidade anual a produzir de P2
Programação Matemática - Prof. Malomar Alex Seminotti 24
Ciência da Computação
Exemplo
b) Qual o objetivo?
O objetivo é maximizar o lucro, que pode ser 
calculado da seguinte forma:
Lucro devido a P1: 1.000 . X1
(lucro por unidade de P1 x quant. produzida de P1)
Lucro devido a P2: 1.800 . X2
(lucro por unidade de P2. x quant. produzida de P2)
Lucro total: L = 1.000 . x1 + 1.800 . X2
Objetivo: Maximizar L = 1.000 . x1 + 1.800 . x2
Programação Matemática - Prof. Malomar Alex Seminotti 25
Ciência da Computação
Exemplo
c) Quais as restrições?
As restrições impostas pelo sistema são:
Disponibilidade de horas para a produção: 1.200 h
Horas ocupadas com P1: 20x1
(uso por unidade x quantidade produzida)
Horas ocupadas com P2: 30x2
(uso por unidade x quantidade produzida)
Total em horas ocupadas na produção: 20x1 + 30x2
Disponibilidade: 1.200 horas
Restrição descritiva da situação: 20x1 + 30x2 ≤ 1.200
Programação Matemática - Prof. Malomar Alex Seminotti 26
Ciência da Computação
Exemplo
c) Quais as restrições?
Disponibilidade de mercado para os produtos 
(demanda):
Disponibilidade para P1: 40 unidades
Quantidade a produzir de P1: x1
Restrição descritiva da situação: x1 ≤ 40
Disponibilidade para P2: 30 unidades
Quantidade a produzir de P2: x2
Restrição descritiva da situação: x2 ≤ 30
Programação Matemática - Prof. Malomar Alex Seminotti 27
Ciência da Computação
Exemplo
c) Quais as restrições?
Resumo do modelo: max L = 1.000x1 + 1.800x2
Sujeito a:
Programação Matemática - Prof. Malomar Alex Seminotti 28
Ciência da Computação
Programação Linear – Resumo
• Resumidamente, a construção de um modelo de 
programação linear segue três passos básicos:
– Passo I: identifique as variáveis desconhecidas a 
serem determinadas (elas são denominadas 
variáveis de decisão) e represente-as através de 
símbolos algébricos (por exemplo, x e y ou x1 e x2)
– Passo II: liste todas as restrições do problema e 
expresse-as como equações (=) ou inequações (≤, ≥) 
lineares em termos das variáveis de decisão 
definidas no passo anterior
Programação Matemática - Prof. Malomar Alex Seminotti 29
Ciência da Computação
Programação Linear
– Passo III: identifique o objetivo ou critério de 
otimização do problema, representando-o como uma 
função linear das variáveis de decisão. 
O objetivo pode ser do tipo maximizar ou minimizar
Programação Matemática - Prof. Malomar Alex Seminotti 30