Introdução à PLI 2021 2

Prévia do material em texto

Pesquisa Operacional II 
Introdução à Programação Linear Inteira (PLI)
Definição de Programação Linear Inteira: 
São Problemas de Programação Linear em que todas ou algumas variáveissão discretas (tem de assumir valores inteiros) - Programação Linear Inteira - PLI.
Classificação:
- Todas as variáveis de decisões são inteiras: são problemas denominados Problemas de Programação Linear Inteira Pura – PLIP
- Parte das variáveis de decisões é inteira: são problemas denominados Problemas de Programação Linear Inteira Mista – PLIM
- Todas as variáveis de decisões são binárias: são problemas denominados Problemas de Programação Linear Inteira Binária – PLIB
- Parte das varáveis de decisões são binárias: são problemas denominados Problemas de Programação Linear Inteira Binária Mista – PLIBM.
Principais técnicas de resolução dos problemas de PLI:
· Arredondamento ou truncagem dos valores não inteiros: podem produzir soluções distantes da ótima, ou mesmo que não sejam viáveis.
· Técnicas de Enumeração Explicita: faz-se uma enumeração e avaliação de todas as soluções admissíveis, só é viável para problemas com poucas variáveis.
· Técnicas de Enumeração Implícita: obtêm os valores limitantes cada vez mais próximos da solução ótima através de uma enumeração “inteligente” das soluções viáveis do problema, no sentido de que a análise de certas propriedades de cada subproblema evita a enumeração exaustiva (explícita) de todas as soluções inteiras viáveis, o que é impraticável.Ex: Branchandboud, Balas, Planos de Corte
· Partição e avaliação progressiva ou Branch-and-Bound (B&B): é desenvolvido uma arborescência cuja raiz é a solução do PPL obtida pela relaxação do problema de PLI, isto é, retirando-lhe as restrições de integralidade essa classe de algoritmos é utilizada para um problema de PLI qualquer.
· Algoritmo de balas: este algoritmo é utilizado para problemas de PLI em que cada uma das suas n variáveis assumem apenas os valores 0 ou 1.
· Técnicas de Planos de Corte: obtêm os valores limitantes cada vez mais próximos da solução ótima através da redução do tamanho do conjunto de soluções viáveis de relaxações dos subproblemas, acrescentando restrições válidas (cortes) ao conjunto original de restrições.
Em linhas gerais, os métodos para PLI estão fundamentados na obtenção de sucessivas soluções de subproblemas (mais fáceis), fornecendo valores limitantes cada vez mais próximos da solução ótima do problema de PLI original.
Formulações especiais para problemas de PLI: decisão tipo “sim ou não”, “ou – ou”, “há restrições dequek em n tenham que se manter”, “háfunções com n valores possíveis”, “há custo fixo de preparação”. 
1) Exemplo de decisões “sim ou não”:executar o projeto?, fazer o investimento?, instalar a empresa naquela cidade?
Solução usar variável binária 
· Grupos de alternativas mutuamente exclusivas–somente umadecisão no grupo pode ser “sim”. Fazer:
-Se exatamente uma decisão no grupo tiver que ser “sim”.
-Se quando muito uma decisão no grupo tiver que ser “sim”
· Decisões contingentes –dependem de decisões anteriores. Exemplo: decisão k écontingente na decisão j, se a decisão k puder ser “sim” somente se a decisão j for “sim”. Fazer: ou seja, quando YJ= 1 dá escolha livre para YK, mas se YJ= 0 forçaYK= 0
Se Yj=1 então Yk=1 ou Yk=0
 Yj=0 então Yk=0
2) Restrições “ou - ou” (mutuamente excludentes) –escolher entre 2 recursos qual usar para umdado propósito, de modo que seja necessário que uma das duas restrições de disponibilidade de recursos se mantenha válida.Exemplo: seja M = número suficientemente grande.
Generalizando– caso em que “há restrições de que K em N tenham que se manter” –dado um conjunto de N restrições possíveis, apenas é requerido que K destas restrições devam serválidas.
Sejam as restrições:
3) Há funções com N valores possíveis– situação em que é requerido que uma dada função assuma qualquer um de N valores dados:
1
4) Há custo fixo de preparação – custo total é a soma de um custo variável relacionado ao nível da atividade e o custo de preparação requerido para iniciar a atividade. 
Solução:
Alguns problemas clássicos de PLI
1) PROBLEMA DA MOCHILA
Um problema típico de PLI é o Problema da Mochila (KnapsackProblem em inglês). A situação representada por este problema é a seguinte: um alpinista dispõe de uma mochila e de diversos objetos que podem ser “carregados” na mochila; para cada objeto é conhecido o seu peso (pi) e o benefício que dele se tira (vi). Conhecida a capacidade da mochila em termos de peso máximo, quais os objetos, dentre os n existentes, que devem ser escolhidos para colocar na mochila?
Exemplo:Um excursionista planeja fazer uma viagem acampando. Há cinco itens que ele deseja levar consigo, mas estes, juntos, excedem o limite de 60 lb que ele supõe ser capaz de carregar. Para ajudar no processo de deleção, ele atribuiu valores, por ordem crescente de importância, a cada um dos itens segundo a tabela:
	Item
	1
	2
	3
	4
	5
	Peso, libras
	52
	23
	35
	15
	7
	Valor
	100
	60
	70
	15
	15
Que itens devem ser conduzidos de forma a maximizar o valor total sem exceder as restrições de peso?
VAR
Xi= 1, se o item “i” for adicionado na mochila
 0, caso contrário
i=1,2,3,4,5
FO MAX Z = 100X1+60X2+70X3+15X4+15X5
Restrições
Capacidade mochila 
52X1+ 23X2+35X3+15X4+7X5 <= 60 libras
Xi é binário ou
Xi 
2) PROBLEMA DE SELEÇÃO DE PROJETOS
Problema típico de PLI é o problema de seleção de projetos de investimento.Se se admitir que os projetos são perfeitamente divisíveis, o problema pode serrepresentado por um modelo de PL; se pelo contrário, se supuser que os projetos sãoindivisíveis, então as variáveis de decisão são binárias (o projeto ou é escolhido ou érejeitado) e o modelo será de PLI.
A descrição do problema é a seguinte: que projetos escolher, de entre n possíveis,de forma a maximizar o proveito global e não ultrapassando os fundos disponíveis emcada período? Para cada projeto são conhecidos os valores requeridos em cada períodoe o proveito resultante da sua escolha.
Exemplo: A Investe&Futuro possui um capital de R$ 14000 para investir numa carteira de 4 projetos, tendo estudado a rentabilidade dos mesmos. Na tabela apresenta-se, para cada projeto/investimento, o montante de capital a investir e a rentabilidade esperada (Valor Atualizado Líquido):
	Projeto
	Capital (R$)
	Rentabilidade (R$)
	1
	5.000
	16.000
	2
	7.000
	22.000
	3
	4.000
	12.000
	4
	3.000
	8.000
Modele o problema de PLI de forma a maximizar a rentabilidade do investimento.
Var:Xi= 1, se o projeto “i” for escolhido
 0, caso contrário
 i=1,2,3,4 
FO:MAX R = 16000X1+22000X2+12000X3+8000X4
Restrições: Capital 5000X1+ 7000X2+4000X3 + 3000X4<=14000
Xi 
Decisões Contingentes – dependem das decisões tomadas anteriormente.
a) Se a Investe&Futuro selecionar o projeto 2, deverá selecionar também o projeto 1. 
X2=1 então X1=1 Verificar: X2=1 X1=0
X2=0 então X1=0 ou X1=1
X2<=X1 .: X2-X1<=0
Seleção entre variáveis ou alternativas mutuamente exclusivas – apenas uma pode ser sim.
a) 
b) Se a Investe&Futuro selecionar o projeto 2 não poderá selecionar o projeto 4. 
X2=1 então X4=0
 X2=0 então X4=0 ou X4 =1
X2+X4<=1
c) A Investe&Futuro deverá selecionar o projeto 2 ou o projeto 4. (ou excludente)
X2=1 então X4=0
 X2=0 então X4 =1
X2+X4=1
Aulas assíncronas ---
3)PROBLEMA DE O Problema de Designação (em inglês, AssignmentProblem) é conhecido por ser a representação de inúmeras situações em que é necessário designar pessoas a lugares, a tarefas ou a zonas de trabalho, máquinas a tarefas, etc. DESIGNAÇÃO
Aparece muitas vezes como se tratasse de um problema de PL mas, como veremos, as suas variáveis de decisão são binárias. É um caso específico de um problema de transporte.
Exemplo:A fim de privatizar o sistema de telefonia, o governo da SBORNIA decidiu vender o sistema em leilão, dividindo-o em cinco regiões de atuação (Norte, Sul,Centro, Leste e Oeste). Cinco consórcios (C1, C2, C3, C4 e C5) se habilitaram, apresentando uma proposta de compra para cada região, conforme quadro apresentado abaixo (em milhões de Reais). Dado que a legislação vigente não permite que um consórcio compre mais do que uma região, e que o governo deseja arrecadar o máximo possível modele o problema de forma a determinar qual é a estratégia ótima de privatização que deveria ser adotada. 
	
	
	PROPOSTAS DOS CONSÓRCIOS
	
	
	C1
	C2
	C3
	C4
	C5
	REGIÃO
	Norte
	13
	16
	14
	9
	19
	
	Sul
	13
	15
	16
	9
	13
	
	Centro
	14
	18
	14
	14
	22
	
	Leste
	24
	14
	19
	17
	27
	
	Oeste
	15
	13
	23
	20
	26
Altere o exercício imaginando que cada consórcio poderá comprar, no máximo, até duas regiões.
Altere o exercício imaginando que cada região deve ser administrada por pelo menos dois consórcios.
4)PROBLEMAS COM CUSTO FIXO
É um problema que envolve um processo produtivo que tem dois componentes de custo: um custo fixo quando o processo é utilizado e um custo variável proporcional ao número de atividades produzidas.
Exemplo:Uma empresa siderúrgica possui 3 usinas e cada uma delas requer uma quantidade mensal mínima de minério para operar. A empresa adquire minério de 3 minas diferentes. Cada uma das minas tem uma capacidade máxima de produção mensal estabelecida. Por imposições contratuais, o custo do minério para a empresa é composto por um custo fixo mensal para cada mina (este valor é pago em caso de haver produção na mina), mais um custo de transporte ($/t) que varia de acordo com a distância entre as minas e usinas (cada par mina/usina tem um custo diferente). Os dados são mostrados na tabela abaixo:
	
	Mina 1 ($/t)
	Mina 2 ($/t)
	Mina 3 ($/t)
	Requisições de minério (t/mês)
	Usina 1
	10
	8
	13
	12300
	Usina 2
	7
	9
	16
	15400
	Usina 3
	6
	10
	12
	13300
	Cap. máx. das minas (t/mês)
	11500
	16500
	13000
	-
	Custo Fixo ($)
	50000
	40000
	30000
	
Construir um modelo de otimização para determinar a quantidade de minério a ser comprada decada mina e levada a cada usina de forma a minimizar o custo total de compra de minério.
VAR	
Aulas assíncronas ---
5) PROBLEMA DE LOCALIZAÇÃO DE FACILIDADES
É um problema que visa determinar a localização e capacidade das facilidades (restaurantes, depósitos, antenas de rádio etc.) de forma a suprir a demanda da região toda com um custo mínimo e/ou lucro máximo (considerando um determinado período). Cada facilidade possui normalmente um custo fixo de instalação e custos variáveis de operação
Exemplo:O MetroHealth Hospital gostaria de posicionar um serviço de emergência nas comunidades circunvizinhas da grande área metropolitana na qual atua. O objetivo é não ter paciente demorando mais que 10 minutos para chegar até uma sala de emergência. Os tempos estimados para um paciente dirigir em minutos para localizações potenciais são:
	da vizinhança
	Para locais potenciais de sala de emergência
	
	1
	2
	3
	4
	5
	6
	A
	0
	5
	15
	25
	25
	15
	B
	5
	0
	20
	30
	15
	5
	C
	15
	20
	0
	10
	25
	15
	D
	25
	30
	10
	0
	10
	20
	E
	25
	15
	25
	10
	0
	9
	F
	15
	5
	15
	20
	9
	0
Qual o número mínimo de salas de emergência e onde elas devem estar localizadas?
6) PROBLEMA DE DIMENSIONAMENTO DE LOTES DE PRODUÇÃO
Empresas de manufatura fabricam diversos tipos de produtossolicitados por diferentes clientes, muitas vezes em grandesquantidades, os quais devem estar prontos para entrega emdiferentes datas previamente agendadas. Como as fábricas têmcapacidades de produção limitadas (máquinas, mão-de-obra eoutros), é necessário planejar a produção, isto é, decidir o que equanto produzir (em outras palavras, dimensionar os lotes daprodução) em cada período de um horizonte de planejamento.
A necessidade de antecipação da fabricação de produtos(estocados de um período para o outro) acarreta em custos deestocagem e algumas dificuldades operacionais. No planejamentoda produção, deseja-se determinar o tamanho dos lotes deprodução, para atender a demanda na data solicitada e de modoque a soma dos custos de produção e estocagem seja mínima.
Exemplo:Considere a fabricação de dois tipos de vigas com demandas conhecidas paratrês semanas:
	Demanda de vigas
	Período 1
	Período 2
	Período 3
	Item 1
	100
	90
	120
	Item 2
	40
	50
	80
Suponha a disponibilidade de 40 horas de trabalho por período:
· produzir 1 unidade do item 1 consume 15 minutos
· produzir 1 unidade do item 2 consume 20 minutos
Custo de produçãosão conhecidos:
	Custos de produção
	 Período 1 
	Período 2 
	Período 3
	Item 1 
	20
	 20 
	30
	Item 2 
	20
	 20
	30
Admite-se estocar a produção para ser utilizada nos períodosseguinte com os seguintes custos:
	Custo de Estoque
	 Período 1 
	Período 2 
	Item 1 
	2
	3
	Item 2 
	2,5
	3,5
Objetivo: determinar o tamanho dos lotes para produção,atendendo a demanda na data com custos de produção eestocagem mínimos.
VAR
xij = quantidade a ser produzida da viga tipo “i” no período “j”
i = 1 (item 1),2 (item 2)
j = 1(período 1), 2 (período 2), 3 (período 3)
yiw = quantidade da viga tipo “i” estocada no final do período “w”
i = 1 (item 1),2 (item 2)
w= 1(período 1), 2 (período 2)
FO 
Min C = custos de produzir + custos de estocar
Min C = 20 (x11+x12+x21+x22) + 30 (x13 + x23) + 2y11+ 3y12+ 2,5y21+ 3,5y22
Restrições
Período 1 15x11+20x21<=40*60
Período 2 15x12+20x22<=40*60
Período 3 15x13+20x23<=40*60
Conserv fluxo – item 1
Período 1 x11 = 100 + y11
Período 2 x12 + y11 = 90 + y12
Período 3 x13 + y12 = 120
Conserv fluxo – item 2
Período 1 x21 = 40 + y21
Período 2 x22 + y21 = 50 + y22
Período 3 x23 + y22 = 80
Xij é inteiro
Xij >=0
Yiw é inteiro
Yiw >=0
Aulas assíncronas ---
7) PROBLEMA DA ALOCAÇÃO DE PESSOAL
É um problema que visa determinar a quantidade ótima de pessoas de forma a suprira demanda considerando uma escala de trabalho, em dias ou turnos com um custo mínimo, considerando o trabalho em horário normal e/ou em horário extraordinário. 
Exemplo:As praias usualmente são vigiadas no verão por salva-vidas. Umaprogramação numa praia deseja ser considerada, onde sete dias porsemana estarão disponíveis vários nadadores(as)-salvadores. Porregulamento nenhum poderá trabalhar mais do que 5 dias por semana,tendo 2 dias consecutivos de repouso. Ao contrário da maior parte dostrabalhadores estes terão mais sobrecarga ao fim de semana.Atendendo especialmente ao no de frequentadores das praias, a experiência deanos anteriores e a promoção de mais segurança, foi aprovada a tabela com asegurança necessária. Quantos nadadores(as)-salvadores deverão entrar ao serviço em cada dia dasemana, procurando empregar o menor no (N), mas satisfazendo as exigências?
8) PROBLEMA DE CORTE 
Consiste no uso de estratégias para a produção de itens (peças pequenas), a partir do corte de umobjeto (peça grande), garantindo que a perda do material utilizado seja mínima
Exemplo:Vamos considerar um problema em que largura total: L = 170 cm. Os pedidos têm largura menor: l1 = 30 cm, l2 = 50 cm, l3 = 55 cme a demanda para os itens menores é: d1 = 80, d2 =120, d3 =110. Quantos esquemas de corte são possíveis?Não fizemos todos os planos de corte – descartando os que tem muita sobra.
	
	X1
	X2
	X3
	X4
	X5
	X6
	X7
	X8
	.
	.
	.
	.
	
	
	30 cm 
	5
	0
	0
	4
	2
	0
	0
	2
	
	
	
	
	
	
	50 cm
	0
	3
	0
	1
	2
	1
	2
	0
	
	
	
	
	
	
	55 cm
	0
	0
	3
	0
	0
	2
	1
	2
	
	
	
	
	
	
	Perda (cm)
	20
	20
	5
	0
	10
	10
	15
	0
	
	
	
	
	
	
X1= número de bobinas cortadas no padrão “i”
I=1,2,3,4,5,6,7,8
Min Perda= 20x1+20x2+5x3+10x5+10x6+15x7
Dem bob 30 cm 5x1+4X4+2x5+2x8>=80 bobinas
Dem bob 50 cm 3x2+1x4+2x5+1x6+2x7>=120 bobinas
Dem bob 55 cm 3x3+2x6+1x7+2X8>=110 bobinas
Xi é inteiro, xi>=0
Atividade assíncrona- escolha mais 7 problemas – 10 HORAS ASSÍNCRONAS. 
Exercícios - Modelagem em PLI
1) Uma empresa de barcos precisa determinar quantos veleiros devem ser produzidos durante cada um dos 4próximos trimestres. A demanda de cada um dos trimestres é: primeiro trimestre, 40 veleiros; segundo trimestre,60 veleiros; terceiro trimestre, 75 veleiros;quarto trimestre, 25 veleiros. A empresa quer atender a demandaprontamente. No início do primeiro trimestre, a empresa tem 10 veleiros em estoque. No início de cada trimestre, aempresa precisa decidir quantos veleiros devem ser produzidos durante o trimestre. Por simplicidade, assume-se queos veleiros fabricados durante um trimestre podem ser usados para atender a demanda deste trimestre. Durantecada trimestre, a empresa pode produzir até 40 veleiros com sua mão de obra regular a um custo de $ 400 porveleiro. Tendo de trabalhar com horas extras durante o trimestre, a empresa pode produzir veleiros a mais a umcusto total de $ 450 por barco. No final de cada trimestre (após ter ocorrido a produção e a demanda do trimestreter sido atendida), um custo de armazenagem de $ 20 por barco ocorre. Usar a programação linear para determinarum modelo matemático que determine o programa de produção mensal de modo a minimizar a soma dos custos deprodução e estoques durante os 4 próximos trimestres.
2)Restrições Lógicas - Considere 7 variáveis de decisão binárias, xj, j=1,...,7. Estabeleça, em termos de um modelo de Programação Inteira, as seguintes condições:
i) As variáveis 1 e 5 têm de ter o mesmo valor.
ii) Não é possível terem todas o valor 1.
iii) Pelo menos uma tem que ter o valor 1.
iv) A variável 1 não pode ter valor 1 se a variável 3 tiver valor 1.
v) A variável 4 só pode ter valor 1 se a variável 2 também tiver.
3)Uma pessoa foi consultada por três companhias de Telefone para subscrever-se a seu serviço de Longa Distância nos Estados Unidos. MaBell cobrará uma tarifa fixa de 16 dólares por mês, mais 0,25 centavos por minuto. PaBell cobrará 25 dólares por mês, mas reduzirá o custo por minuto a 0,21 centavos. Enquanto a BabyBell, a tarifa mensal fixa e de 18 dólares e o custo por minuto e de 0,22 centavos.
Geralmente a pessoa consultada faz uma média de 200 minutos de chamada a longa distância ao mês. Supondo que não pague a tarifa fixa, a menos de fazer as Chamadas e de que possa dividir mais chamadas entre as três companhias, segundo ele ache conveniente, como a pessoa pode usar os serviços das três companhias para minimizar a conta mensal de telefone?
4). Nos próximos cinco anos, a Petrobras pretende investir, anualmente, até 300 milhões de reais em seu sistema de gasodutos e oleodutos que transportam os diversos derivados entre as suas diferentes unidades produtoras e os seus centros de refino e distribuição, dentro do Programa Tecnológico de Dutos - PROTRAN. Os investimentos podem ser na reabilitação dos dutos já existentes e que estejam perto do final de sua vida útil (entre 20 e 30 anos) ou na implantação de novos dutos.
O processo de reabilitação de dutos consiste da pintura in situ das partes interna e externa de cada duto e depende do desenvolvimento, pelo CENPES (Centro de Pesquisas da PETROBRAS), de uma tinta especial. Sem esse desenvolvimento, o processo de reabilitação fica economicamente inviável e não pode ser executado.
Para todos os projetos foram calculados os Valores Presentes Líquidos (VPL), e os que se apresentaram economicamente viáveis (VPL positivo) estão sob a análise do comitê de investimentos da empresa. Esse comitê tem de decidir que projeto deve ou não ser realizado sujeito às restrições de investimento da empresa, maximizando o retorno para a empresa. Os projetos sob análise são os seguintes, com valores em milhões de reais:
	
	
	Capital Requerido
	Projeto
	VPL 
(8%a.a)
	ANO 1
	ANO 2
	ANO 3
	ANO 4
	ANO 5
	1
	100
	170
	70
	70
	50
	20
	2
	70
	50
	30
	30
	20
	10
	3
	30
	60
	10
	10
	10
	-
	4
	120
	130
	60
	50
	50
	50
	Investimento Disponível
	300
	300
	300
	300
	300
Projeto 1 – Construção de novo gasoduto Campinas-Rio de Janeiro que ligará a Refinaria de Paulínia (Replan) ao terminal de Japeri (RJ).
Projeto 2 – Reabilitação do gasoduto Pilar (AL)/Ipojuca (PE) através de pintura interna in situ.
Projeto 3 – Desenvolvimento da tinta a ser utilizada na recuperação de gasodutos.
Projeto 4 - Construção de novo gasoduto Campinas-Jacutinga que ligará a Refinaria de Paulínia (Replan) ao terminal de Jacutinga (MG).
Modele o problema de PLI.
5). Uma fábrica de artigos de decoração, localizada em Lambari (MG), deve entregar uma grande quantidade de peças na cidade de Baependi (MG). A empresa quer saber qual o caminho que seu caminhão de entregas deve fazer para minimizar a distância total percorrida. A figura a seguir, representa, na forma de rede, as ligações entre as cidades da região. Construa um modelo de programação linear inteira que ajude a minimizar a distância percorrida.
6) Uma fábrica de papel produz bobinas de papel com 70 polegadas de largura. Os clientes, porém, solicitam bobinas (do mesmo comprimento) com largura menor. Os pedidos de hoje são:
100 bobinas de 22 polegadas
125 bobinas de 20 polegadas
80 bobinas de 12 polegadas
Essas bobinas de menor largura são obtidas cortando-se a bobina de 70 polegadas. Por exemplo, uma bobina de 70 polegadas pode ser cortada obtendo-se 2 bobinas de 22 polegadas e 1 bobina de 20 polegadas, gerando uma perda de 6 polegadas. Formule o problema para que a fábrica programe os cortes, atendendo os pedidos do dia, minimizando a perda.
10. Um hospital trabalha com um atendimento variável em demanda durante as 24 horas do dia. As necessidades distribuem-se segundo a tabela abaixo:
	Turno de Trabalho
	Horário
	Número Mínimo de Enfermeiros
	1
	08:00-12:00
	50
	2
	12:00-16:00
	60
	3
	16:00-20:00
	50
	4
	20:00-00:00
	40
	5
	00:00-04:00
	30
	6
	04:00-08:00
	20
O horário de trabalho de um enfermeiro é de oito horas quando ele entra nos turnos 1, 2, 3, 4, e 6. O enfermeiro que entra no turno 4 recebe uma gratificação de 50% sobre o salário e o enfermeiro que entra no turno 5 trabalha apenas quatro horas. Elaborar o modelo de programação linear inteira que minimiza o gasto com mão-de-obra.
7) Uma determinada empresa está interessada em maximizar o lucro mensal proveniente de quatro de seus produtos, designados por I, II, III e IV. Para fabricar esses produtos, ela utiliza dois tipos de máquinas (M1 e M2) e dois tipos de mão-de-obra (MO1 e MO2) que têm as seguintes disponibilidades:
	Máquinas
	Disponibilidades
(maq-hora/mês)
	
	Mão-de-Obra
	Disponibilidades
(homem-hora/mês)
	M1
	80
	
	MO1
	60
	M2
	20
	
	MO2
	40
O setor técnico da empresa fornece os seguintes coeficientes, que especificam o total de horas de máquina e horas de mão-de-obra necessárias para a produção de uma unidade de cada produto.
	Máquinas
	Produtos
	
	Mão-de-obra
	Produtos
	
	I
	II
	III
	IV
	
	
	I
	II
	III
	IV
	M1
	5
	4
	8
	9
	
	MO1
	2
	4
	2
	8
	M2
	2
	6
	-
	8
	
	MO2
	7
	3
	-
	7
O setor comercial da empresa fornece as seguintes informações:
	Produtos
	Potencial de vendas (unid/mês)
	Lucro unitário (R$/unid)
	I
	70
	10,00
	II
	60
	8,00
	III
	40
	9,00
	IV
	20
	7,00
Deseja-se planejar a produção mensal da empresa que maximize o lucro.
8)Uma determinada confecção opera com dois produtos: calças e camisas. Como se tratam de produtos semelhantes, eles possuem uma produtividade comparável e compartilham os mesmos recursos. A programação da produção é realizada por lotes de produto.
O departamento de produção informa que são necessários 10 homens x hora para um lote de calças e 20 homens x hora para um lote de camisas. Sabe-se que não é necessária mão-de-obra especializada para a produção de calças, mas são necessários 10 homens x hora desse tipo de mão-de-obra para produzir um lote de camisas. O departamento de pessoal informa que a força máxima de trabalho disponível é de 30 homens x hora de operários especializados e de 50 homens x hora de não especializados.
Da planta de produção, sabemos que existem apenas duas máquinas com capacidade de produzir os dois tipos de produto, sendo que a máquina 1 pode produzir um lote de calças a cada 20 horas e um lote de camisas a cada 10 horas, não podendo ser utilizada por mais de 80 horas no período considerado. A máquina 2 pode produzir um lote de calças a cada 30 horas e um lote de camisas a cada35 horas, não podendo ser utilizada por mais de 130 horas no período considerado. 
São necessários dois tipos de matéria-prima para produzir calças e camisas. Na produção de um lote de calça são utilizados 12 quilos de da matéria-prima A e 10 da B. Na produção de um lote de camisas são utilizados 8 quilos da matéria-prima A e 15 da B.
O almoxarifado informa que, por imposições do espaço, só pode fornecer 120 quilos de A e 100 quilos de B no período considerado.
Sabendo-se que o lucro pela venda é de 800 reais nos lotes de camisas e de 500 reais nos lotes de calças, formule o problema de maximizar o lucro da operação produtiva em pauta.
9) O diretor de um hospital deve escolher um esquema de designação de leitos e quartos em uma nova ala que será construída, com área total de 1200 m2. Existem três tipos de quartos possíveis: 
· Com um leito para paciente
· Com dois leitos para paciente
· Como três leitos para paciente
O total de quartos a construir não pode ultrapassar 70. Adicionalmente, o número de quartos com um leito não pode ultrapassar 30. Por imposições de demanda, deverão ser oferecidos pelo menos 120 novos leitos. A necessidade de área construída é de: 
· 10 m2 para quarto com um leito
· 15 m2 para quarto com dois leitos
· 18 m2 para quarto com três leitos
A receita mensal estimada por tipo de quarto é: 
· $ 7500 para quarto com um leito
· $ 6000 para quarto com dois leitos
· $ 4500 para quarto com três leitos
a) Determine quantos quartos de cada tipo deverão ser construídos de modo a maximizar a receita mensal.
b) Determine quantos quartos de cada tipo deverão ser construídos de modo a maximizar o número de leitos.
10)O diretor de um hospital deve escolher um esquema de designação de leitos e quartos em uma nova ala que será construída. Existem 3 tipos de quartos possíveis: com um leito; com dois leitos e com três leitos.
O total de quartos a construir não pode ultrapassar 70. Por imposições de demanda, deverão ser oferecidos pelo menos mais 120 leitos. A percentagem de quartos de um leito deve ser restrita entre 15 a 30% do total de quartos. A necessidade em área construída é de 10 m2 por quarto com um leito, 14 m2 por quarto com dois leitos e 17 m2 por quarto com três leitos.
Os pacientes dos quartos com dois e três leitos exigem apenas 80% da mão-de-obra que os do quarto individual. O que o hospital recebe por cada paciente internado é inversamente proporcional à capacidade do número de pessoas do quarto em que ele está internado. Considerando o hospital sempre lotado, formule o problema de forma a:
a) minimizar o esforço da mão-de-obra em apoio médico e administrativo;
b) maximizar a arrecadação global;
c) minimizar o espaço necessário para a nova ala.
11)A LCL Equipamentos S.A. produz três tipos de furadeiras que necessitam de tempos diferentes na linha de montagem. Para que cada tipo de furadeira seja fabricada, um custo de preparação da fabrica é incorrido. Suponha que todas as furadeiras do mesmo tipo serão produzidas de uma só vez (apenas uma preparação por tipo). Abaixo os dados relevantes à análise do problema.
	
	Tipo 1 
	 Tipo 2
	Tipo 3
	Total Disponível
	Montagem
	2 h/unid
	3 h/unid
	2,5 h/unid
	600 h
	Pintura
	3 h/unid
	2 h/unid
	2,5 h/unid
	500 h
	Lucro Unitário
	R$ 50
	R$ 60
	R$ 65
	-
	Preparação
	R$ 5.000
	R$ 4.000
	R$ 3.000
	-
12) Uma fábrica manufatura 5 tipos de prateleiras (P1; P2; P3; P4; P5) utilizando dois processos de produção: processo normal (N) e processo acelerado (A). Cada produto requer um certo número de horas para ser trabalhado dentro de cada processo e alguns produtos só podem ser fabricados através de um dos tipos de processo. O quadro a seguir resume o consumo (em horas) dentro de cada esquema de fabricação e os lucros (em R$) obtidos após a dedução dos custos de produção.
A montagem final de cada prateleira requer 16 h de mão-de-obra por unidade. A fábrica possui3 máquinas para o processo normal e 2 para o processo acelerado. As máquinas trabalham em2 turnos de 8 horas por dia em um regime de 6 dias por semana. Uma equipe de 8 pessoastrabalha em turno único de 8 horas durante 6 dias na montagem das prateleiras. Determine omelhor esquema de produção.
13) A LCL Motores recebeu recentemente uma encomenda para produzir três tipos de motores. Cada tipo de motor necessita de um determinado número de horas de trabalho no setor de montagem e acabamento. A LCL pode terceirizar parte de sua produção. A tabela a seguir resume essas informações:
	Modelo
	1
	2 
	3
	Total (h)
	Demanda (unidades)
	3000
	2500
	500
	-
	Montagem (h/unidade)
	1,1
	1,9
	0,7
	6000
	Acabamento (h/unidade)
	2,5
	0,8
	4,0
	10000
	Custo de produção (R$)
	50
	90
	120
	-
	Terceirizado (R$)
	65
	92
	140
	-
Elabore o modelo de programação matemática que minimiza os custos de produção.
14) Um construtor produz barcos por encomenda, e tem os seguintes pedidos para serem entregues no final dos próximos 6 meses:
	Meses
	Fev
	Mar
	Abr
	Mai
	Jun
	Jul
	Nº de Barcos
	1
	2
	5
	3
	2
	1
Ele pode construir até 4 barcos em qualquer mês, e pode guardar até 3 barcos em estoque. O custo de construção dos barcos é de $ 10.000,00 por unidade. Caso algum barco seja construído em um mês, um custo fixo adicional de $ 4.000,00 deve ser considerado. Para manter um barco em estoque durante o período de um mês, o construtor gasta $ 1.000,00. Qual deve ser o plano ótimo de construção, de modo a minimizar o custo total do construtor? Formule um modelo de programação inteira para obter a solução.
15) Um excursionista planeja fazer uma viagem acampando. Há n itens que o excursionista deseja levar consigo, mas estes, juntos, excedem o limite de T quilos que ele supõe ser capaz de carregar. Para ajudar a si próprio no processo de seleção, ele atribuiu valores, por ordem crescente de importância, a cada um dos itens, onde Vi denota o valor atribuído ao item i e Pi corresponde ao peso do item i. Formule o modelo de Programação Linear associado ao problema.
16) O diretor de uma escola deseja inscrever quatro alunos num concurso de matemática que engloba os seguintes assuntos: álgebra, análise, lógica e geometria. Somente um aluno pode ser inscrito em cada assunto e nenhum aluno pode ser inscrito em mais de um assunto porque as provas dos concursos ocorrerão simultaneamente. Para isso, ele seleciona seus quatro melhores alunos, designados por A, B, C e D e lhes aplica os mesmos exames cobrindo as quatro áreas do concurso. O quadro abaixo indica o número de pontos obtidos por cada aluno em cada uma das áreas. Como o diretor deve tomar sua decisão, visando ao melhor rendimento esperado para a escola? Formule o modelo de programação linear associado.
	
	ÁLGEBRA
	ANÁLISE
	LÓGICA
	GEOMETRIA
	A
	7
	10
	6
	3
	B
	8
	7
	8
	1
	C
	4
	9
	3
	5
	D
	5
	4
	6
	9
17)Um avião de transporte possui três compartimentos para carga, a saber: compartimento frontal, compartimento central e compartimento da cauda. A Tabela 1 resume a capacidade do aparelho:
Tabela 1
	Compartimento
	Peso Máximo (ton)
	Espaço Máximo (m3)
	Frontal
	5
	35
	Central
	7
	55
	Cauda
	6
	30
Objetivando o equilíbrio do voo, é indispensável que a distribuição da carga do avião seja equilibrada nos compartimentos de tal maneira que o peso da carga colocada em cada compartimento seja proporcional a sua capacidade de peso. 
Para carregar o avião, existem dois tipos de containers. Na Tabela 2 temos informações adicionais sobre os containers. 
Tabela 2	
	Carga Tipo
	Peso por Container(ton)
	Volume por Container (m3)
	Lucro ($/ton)
	Container 1
	0,7
	0,5
	200
	Container 2
	0,9
	1
	220
Elaborar o problema de programação linear que otimize a distribuição da carga de forma a maximizar o lucro do voo do cargueiro.
18) Uma companhia de navegação possui um navio com 3 porões de carga (à proa, à ré e ao centro) possuindo os limites de capacidade apresentados na tabela 1:
	Porão
	Tonelagem
(Toneladas)
	Volume
(m3)
	Proa
	2.000
	100.000
	Centro
	3.200
	14.000
	Ré
	1.800
	80.000
À empresa são oferecidas as cargas da tabela 2:
	CargaPeso
(toneladas)
	Volume por tonelada
	Lucro
	ContainerA
	7.000
	60
	20
	ContainerB
	6.500
	50
	24
	ContainerC
	4.000
	25
	16
A fim de preservar o equilíbrio do navio, a proporção entre o peso em cada porão e o volume respectivo deve ser a mesma que entre os correspondentes limites de capacidade. Admita que em cada porão possam ser transportadas partes de cargas diferentes. Pretende-se maximizar o lucro da empresa, relativo à utilização deste navio. Construa um modelo de Programação Linear Inteira para o problema apresentado.
18) Uma companhia produz dois tipos de gasolina de dois tipos de derivados de petróleo. Cada galão da gasolina 1 deve conter no mínimo 50% derivado 1 e cada galão da gasolina 2 deve conter no mínimo 60% do derivado 1. Cada galão da gasolina 1 pode ser vendido a R$ 2.00 reais enquanto que o galão da gasolina 2 pode ser vendido a R$ 2.60 reais. No momento, 500 galões do derivado 1 e 1000 galões do derivado 2 estão disponíveis. Até 1500 galões do derivado 1 pode ser comprado a mais nas seguintes condições: 500 galões a um preço unitário de R$ 0.25 reais, os próximos 500 galões a um preço unitário de R$ 0.20 reais e os próximos 500 galões a um preço de R$ 0.15 reais. Formule como um PLI que maximize o lucro lıquido da empresa.
19)A COMPANHIA DE PRODUÇÃO DAS BEIRAS pretende construir uma nova fábrica em Castelo Banco ou na Guarda ou mesmo duas fábricas, uma em cada cidade. Também está interessada em construir, no máximo, mais um armazém, mas este deverá ser construído numa cidade onde também for construída uma fábrica. O lucro estimado de cada uma das opções é apresentado na terceira coluna da tabela abaixo. Na quarta coluna está o custo de cada uma das opções. Há um limite de 10 milhões de contos para o investimento a efetuar. O objetivo consiste em identificar a alternativa que maximiza o lucro estimado. 
	Decisão
	Pergunta Sim-ou-Não
	Lucro
	Custo
	1
	Fábrica em Castelo Branco?
	9
	6
	2
	Fábrica na Guarda
	5
	3
	3
	Armazém em Castelo Branco?
	6
	5
	4
	Armazém na Guarda
	4
	2
20)Deseja-se investir $14.000. Foram identificadas 4 oportunidades de investimentos: Investimento 1 requer $5.000 e tem um valor presente de $8.000; Investimento 2 requer $7.000 e tem um valor presente de $11.000; Investimento 3 requer $4.000 e tem um valor presente de $6.000, e Investimento 4 requer $3.000 e tem um valor presente de $4.000. Devem-se considerar as seguintes restrições:
Pode-se investir em apenas 2 negócios.
Se investir no negócio 2, deve-se investir no 4 também.
Se investir no negócio 1, não pode-se investir no 3.
Em quais investimentos deve-se aplicar o capital disponível de modo a maximizar o valor presente total?
21) Uma empresa deseja determinar o plano de investimentos para o próximo ano, e dispõe dos seguintes projetos:
	Possibilidade de Investimento
	Valor Presente (US$)
	Capital Requerido (US$)
	I Construir um novo depósito
	7.000.000,00
	5.000.000,00
	II Recuperar o depósito antigo
	4.500.000,00
	3.000.000,00
	III Automatizar o depósito novo
	5.500.000,00
	4.200.000,00
	IV Comprar a fornecedora do produto A
	12.000.000,
	9.300.000,00
	V Construir uma fábrica para produzir A
	9.500.000,00
	7.100.000,00
	VI Reformar o escritório da empresa
	1.500.000,00
	900.000,00
Entre os projetos acima apresentados, as alternativas I e II são mutuamente excludentes, assim como IV e V. O projeto III, por sua vez, depende da realização do projeto I. A empresa dispõe de US$ 20.000.000,00 para investir nestes projetos. Formule um modelo de programação inteira binária para determinação do portfólio ótimo de investimento.
22) Um construtor produz barcos por encomenda, e tem os seguintes pedidos para serem entregues no final dos próximos 6 meses:
	Meses 
	Fev
	Mar
	Abr
	Mai
	Jun
	Jul
	Nº de Barcos 
	1
	2
	5
	3
	2
	1
Ele pode construir até 4 barcos em qualquer mês, e pode guardar até 3 barcos em estoque. O custo de construção dos barcos é de $ 10.000,00 por unidade. Caso algum barco seja construído em um mês, um custo fixo adicional de $ 4.000,00 deve ser considerado. Para manter um barco em estoque durante o período de um mês, o construtor gasta $ 1.000,00. Qual deve ser o plano ótimo de construção, de modo a minimizar o custo total do construtor? Formule um modelo de programação inteira para obter a solução.
23) O aeroporto de Aletrop é a base dos aviões da companhia aérea PAT. Trata-se de um aeroporto moderno, e de uma empresa de aviação em expansão, que pretende manter a sua competitividade num setor de atividade fortemente concorrencial. O aumento de competitividade passa, nomeadamente, pela realização de dois objetivos, a melhoria da qualidade de serviço e a redução dos custos de operação. Por outro lado, a segurança de uma companhia aérea é um aspecto de primordial importância, estando intimamente ligado à manutenção. Para manter um avião em boas condições técnicas, procede-se à manutenção preventiva aos aparelhos da PAT, através de pequenas inspeções entre aterrissagem e posterior descolagem. A direção da empresa está também considerando a hipótese de oferecer estes serviços de manutenção a outras companhias de aviação, mesmo que para tal tenha que aumentar as equipes de manutenção. O elemento crucial nestas equipes é o chefe de manutenção, técnico altamente qualificado, que necessita de fazer formação específica para cada tipo de avião e obter assim uma licença imprescindível para o desempenho dessas funções. A cada licença corresponde uma categoria de aviões, existindo 4 licenças diferentes:
	Tipos de licenças
	Aviões
	1
	Boeing 717 (100 lugares)
	2
	Boeing 777 (300 a 500 lugares)
	3
	Airbus A319 (124 lugares)
	4
	Airbus A340 (350 lugares)
Cada técnico pode ter no máximo 2 licenças. A primeira licença demora vários anos para se obter, sendo, portanto mais cara para a empresa, enquanto a segunda licença demora menos anos para se obter, ficando naturalmente mais barata. O custo da segunda licença depende ainda da licença anterior que o técnico possui. Atualmente existem 9 equipes de manutenção, cada uma chefiada por um técnico licenciado, que funcionam em 3 turnos.
	Turno
	Chefe de equipe
	Tipo de licença
	1
	1
	1,2
	
	2
	1
	
	3
	2
	2
	4
	3,4
	
	5
	2
	
	6
	3
	3
	7
	4
	
	8
	3,4
	
	9
	3
	Custo (M$)
	Licença anterior
	Tipos de Licença 
	
	1
	2
	3
	4
	0
	2
	4
	2
	4
	1
	-
	1
	2
	3
	2
	1
	-
	2
	3
	3
	1
	3
	-
	2
	4
	1
	2
	1
	-
Para poder oferecer serviços a outras companhias de aviação, a empresa pretende que existam 4 licenças de cada tipo, no conjunto dos chefes de manutenção. Isto pode ser conseguido enviando para formação atuais chefes de equipe (portanto técnicos que já possuem 1 licença) ou outros técnicos que ainda não possuem nenhuma licença. No entanto, de cada turno só poderá sair, no máximo, 1 chefe de equipe para formação. Escreva um modelo de programação matemática que permita determinar a política de obtenção de licenças que minimiza os custos para a Aletrop.
24) O diretor de recursos humanos de uma empresa de construção civil pretende planificar os recursos (operários) necessários para construir uma obra que está em curso. Esta obra requer 80000 homens-hora, pretendendo a empresa concluí-la num prazo máximo de três semestres.
Os contratos de pessoal têm a duração de um, dois ou três semestres consecutivos. Cada contrato tem um custo fixo para a empresa de R$ 400,00, independentemente da sua duração (este custo inclui um seguro de acidentes, entre outras parcelas) ao qual acresce o custo de cada homem-hora que varia ao longo do tempo, sendo de R$ 6,00, R$ 6,50 e R$ 7,00 respectivamente para o primeiro, segundo e terceiro semestre de execução da obra.
Foi estabelecido que o número de operários por semestre não deve ser inferior a 25 e que o número de contratos de três semestres não deve ultrapassar 15.
Considerando que cada operário tem um rendimento de 1050 homens-hora por semestre, construa um modelo de programação linear que permita ao diretor de recursos humanos decidir quantos operários deverão ser contratados,por tipo de contrato (sendo necessário especificar o semestre em que os contratos são iniciados, no caso de contratos de um e dois semestres).
Nota: 1 homem-hora é a quantidade de trabalho realizada por 1 homem em 1 hora.
25) Um gestor de produção está a planejar a produção de três produtos, para o que dispõede quatro máquinas. Qualquer produto pode ser fabricado em cada uma das máquinas.O custo de produção (em euros) por unidade de produto, está representado na seguintetabela:
Determine a designação dos produtos às máquinas, de modo a que o custo de produçãoseja mínimo.
26) A figura a seguir representa uma rede de comunicação de dados entre computadores. Osnúmeros representam a capacidade máxima em MBytes por segundo que pode ser transmitidode um computador para outro. Admita que a transmissão só é possível no sentido especificadopela seta. Construa um modelo de programação linear inteira que determine o fluxo máximoque pode passar entre A e G através da rede?
EXERCÍCIO Nº__________.
M O D E L O
DEFINIÇÃO DE VARIÁVEIS
	
FUNÇÃO OBJETIVO
	
RESTRIÇÕES
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
Observações:
Aplicações da PLI:
1) Problema de seleção de projetos.
2) Problema da mochila.
3) Problema de designação
Problemas com custo fixo.
3) Problema de alocação de armazéns.
4) Problemas de sequenciamento de tarefas.
5) Roteamento de veículos, linearização de função objetivo com produto de variáveis, problema do caixeiro viajante, problemas de “matching”, de “covering”, de “partitioning”, e de “packing”).
Atividade 2 – Métodos de Resolução de Problemas de PLI
Exemplo B.
1. Resolva o problema usando o método gráfico e a abordagem por ARREDONDAMENTO: 
1º) Ignore a restrição que faz xi inteiro e resolva como se fosse um PPL.
2º) Se a resposta satisfizer as restrições de inteiros então já temos a solução do PPI.
3º) Caso contrário, obtenha uma solução inteira arredondando a resposta do PPL a números inteiros. 
2. Que críticas podem ser feitas à abordagem por arredondamento?
• É difícil pensar em um procedimento sistemático que seja prático para arredondar uma solução não-inteira em um problema de médio ou grande porte 
• Mesmo que o arredondamento funcione em alguns casos, é difícil esperar que esta abordagem funcione sempre.
3. Resolva o problema usando o método gráfico e a abordagem da ENUMERAÇÃO DE SOLUÇÕES VIÁVEIS:
1º) Enumere todas as soluções viáveis.
2º) Tome a melhor. 
3. Que críticas podem ser feitas à abordagem por enumeração das soluções viáveis?
• Essa alternativa torna-se impraticável já em problemas médios: Exemplo: 100 variáveis de decisão que podem assumir valores 0 ou 1 tem-se 2100soluções viáveis.
4. Qual é a ALTERNATIVA para a resolução dos problemas de programação linear inteira?
• Desenvolvimento de algoritmos que enumeram parcialmente um número tratável de possibilidades e implicitamente todo o resto (métodos parcialmente enumerativos).
• OBS: O método simplex emprega o mesmo princípio para resolver PPLs, pois examina sistematicamente somente um sub-conjunto das soluções básicas possíveis. 
5. Considere o seguinte problema:
Max Z=8x1 + 5x2
sujeito a:
x1 + x2 ≤6
9x1 + 5x2 ≤45
x1, x2 ≥0 e inteiros
Pede-se:
a) Resolva o problema contínuo, isto é, sem considerar que as variáveis sejam inteiras.
b) Resolva o problema original, isto é, considerando que as variáveis sejam inteiras. Observação: Se tiver dúvida de qual ponto é o ótimo, por causa da imprecisão de seu gráfico, teste os pontos na função-objetivo.
6. Uma confeitaria produz dois tipos de bolos: chocolate e creme. Cada lote de bolo de chocolate é vendido com um lucro de 3 u.m. e os lotes de creme com um lucro de 1 u.m. Contratos com várias lojas impõem que sejam produzidos no mínimo 10 lotes de bolos de chocolate por dia e que o total de bolos fabricados nunca seja menor que 20. O mercado só é capaz de consumir até 40 lotes de bolos de creme e 60 de chocolate. As máquinas de preparação dos bolos disponibilizam 180 horas de operação, sendo que cada lote de bolo de chocolate consome 2 horas de trabalho e cada lote de bolos de creme 3 horas. Determinar o esquema de produção que maximize os lucros com a venda dos bolos. Qual o lucro ótimo?
	Alunos
	Tipos de problema 
	Exercício
	Débora
	custo fixo e designação
	3, lPO II
÷
÷
ø
ö
ç
ç
è
æ
tonelada
m
3
÷
ø
ö
ç
è
æ
tonelada
US
$