PO2_Aula 01

Prévia do material em texto

AULA 1
PESQUISA OPERACIONAL II
Programação Inteira
Prof. José Roberto Dale Luche
SUMÁRIO
Tipos de Problemas de Programação Inteira
O problema do arredondamento
Relaxação Linear
Introdução
Os problemas de Programação Linear onde todas ou algumas variáveis devem assumir valores inteiros são chamados de Problemas de Programação Inteira (PLI), sendo classificados como:
PLI puro: Apenas variáveis inteiras
PLI misto: Variáveis inteiras e outras contínuas
Com ou sem variáveis binárias
Aplicações de PLI
 Quadro de horários de Professores, escala de ônibus, enfermeiros;
 Planejamento de produção: sequenciamento de máquinas, controle de estoques;
 Problemas de localização de antenas de celulares, postos de saúde;
Existem várias outras aplicações!
Forma geral de um PLI Misto
Max / Min Z = cx + hy
Sujeito a: Ax + Dy ≤ b
 x  Rn+, y  Zp+ 
Dimensões
A : m x n	 D : m x p
x : n x 1 y : p x 1
c : 1 x n		h : 1 x p 
b : m x 1 
No PLI puro só existirão 
 as variáveis y.
No PLI binário, todas as variáveis y assumem 0 ou 1.
Questão
Resolver um problema de PLI será mais fácil por ter menos soluções viáveis para procurar o ótimo?
R. Não, é muito mais demorado, será fácil perceber isso ao estudarmos o algoritmo Branch and Bound.
Uma montadora produzirá dois modelos de carros, a Tabela a seguir traz detalhes quantitativos do problema. Formule o modelo de PLI que seja capaz de encontrar a solução que proporcionará o lucro máximo à empresa. 
Dado o seguinte problema
	Veículo	Lucro unitário
 (mil R$)	Tempo para
Montagem (hs)	Tempo para
Pintura (hs)
	SUV	10	20	28
	Passeio	7	15	6
	Disp. mensal	 	320	250
Modelo algébrico
Variáveis de decisão:
x1: produção mensal do SUV
x2: produção mensal do veículo de passeio
Função Objetivo: Maximizar o Lucro
Max z = 10x1 + 7x2
Sujeito a:
 20x1 + 15x2 ≤ 320 (Tempo disponível para montagem)
 28x1 + 6x2 ≤ 250 (Tempo disponível para pintura)
 x1, x2 ≥ 0 (Não negatividade) Z+ 
Solução com variáveis contínuas
z = 153,4
x1 = 6,1
x2 = 13,2
Mas, interessa para a empresa produzir apenas 10% de um modelo e 20% do outro?
Solução Inteira
Arredondar ou Truncar o valor das variáveis:
x1 = 6,1		x1 = 6
x2 = 13,2		x2 = 13
z = 153,4		z = 151
Quais os perigos?
Solução não Factível!
Solução distante da ótima.
Solução Ótima Inteira x1 , x2  z+
Utilizando o LINDO: z = 152
MAX 10X1 + 7X2	 x1 = 4
St 				 x2 = 16
20X1 + 15X2 <= 320
28X1 + 6X2 <= 250
End
gin 2
Uma solução inteira nunca retornará um valor de z melhor do que o encontrado com as variáveis relaxadas.
Há várias soluções inteiras, qual a melhor?
PLI Misto
Agora suponha que existam variáveis inteiras e variáveis contínuas.
Max z = 10x1 + 7x2
Sujeito a:
 20x1 + 15x2 ≤ 320
 28x1 + 6x2 ≤ 250
 x1 ≥ 0 (Não negatividade)
 x2  Z+ 	 (Inteiro positivo)
PLI Misto
Utilizando o LINDO: z = 153
MAX 10X1 + 7X2	 x1 = 5,5
St 				 x2 = 14
20X1 + 15X2 <= 320
28X1 + 6X2 <= 250
End
gin x2
Lembrando:
Variáveis contínuas:
z = 153,4
x1 = 6,1 x2 = 13,2
Variáveis inteiras:
z = 152
x1 = 4 x2 = 16
Problema 1 da Aula 18 de PO I
O coordenador de curso selecionou aleatoriamente quatro alunos da turma do último semestre. Ele têm a média final de cada aluno em quatro disciplinas. Para cada disciplina, uma prova será aplicada e cada aluno será submetido a apenas uma delas. Sendo assim, o coordenador pretende distribuir as provas de forma que alcance maior chance possível dos alunos obterem o melhor desempenho geral.
Supondo que o Alu 4 teve um problema de saúde e não pôde comparecer, um dos demais alunos deverá acumular uma segunda atividade, mas não poderá acumular PO e PCP.
	NOTAS	PO	SI	PCP	ECO
	ALU 1	5,0	6,0	7,5	8,0
	ALU 2	7,0	6,0	6,5	9,0
	ALU 3	5,0	8,0	9,5	7,5
	ALU 1_2	-	6,0	-	8,0
	ALU 2_2	-	6,0	-	9,0
	ALU 3_2	-	8,0	-	7,5
PLI Binário - LINDO
Max 5X11 + 6X12 + 7.5X13 + 8X14 + 7X21 + 6X22 + 6.5X23 + 9X24 + 5X31 + 8X32 + 9.5X33 + 7.5X34 + 6X42 + 8X44 + 6X52 + 9X54 + 8X62 + 7.5X64
st
X11 + X12 + X13 + X14 = 1 X21 + X22 + X23 + X24 = 1
X31 + X32 + X33 + X34 = 1 
X42 + X44 + X52 + X54 + X62 + X64 = 1
X11 + X21 + X31 = 1 X12 + X22 + X32 + X42 + X52 + X62 = 1
X13 + X23 + X33 = 1 X14 + X24 + X34 + X44 + X54 + X64 = 1
END
int 18
Portanto, todas são restrições de exclusividade!
REFERÊNCIAS
BELFIORE, P.; FÁVERO, L. P. Pesquisa Operacional Para Cursos de Engenharia. Rio de Janeiro: Campus Elsevier, 2012
LACHTERMACHER, G. Pesquisa Operacional na Tomada de Decisões. São Paulo: LTC, 2016.
MARINS, FERNANDO AUGUSTO SILVA. Introdução à Pesquisa Operacional. Cultura acadêmica, 2011.