Upload
internet
View
180
Download
6
Embed Size (px)
Citation preview
Capítulo 6
Pesquisa Operacional na Tomada de Decisões
2ª Edição© Gerson Lachtermacher,2005
Programação Inteira
Capítulo 6
Conteúdos do Capítulo
Programação Inteira Problema Relaxado Solução Gráfica Solução por Enumeração Algoritmo de Branch-And-Bound Solução Excel Solução no Lindo
Caso LCL Tecnologia S.A. Variáveis Binárias e Condições Lógicas Caso LCL Equipamentos S.A.
Capítulo 6
Programação Inteira
São problemas de programação matemática em que a função objetivo, bem como as restrições, são lineares, porém uma ou mais variáveis de decisão podem apenas assumir valores inteiros.
Esse problema pode apresentar dois tipos básicos: Programação Inteira Total - onde todas as variáveis de
decisão são do tipo inteiro. Programação Inteira Mista - onde apenas uma parte das
variáveis são do tipo inteiro, enquanto outras são do tipo real
Capítulo 6
Programação Inteira
A primeira idéia que pode vir à mente é resolver o problema como se fosse um problema de programação linear e arredondar os valores ótimos encontrados para cada uma das variáveis de decisão inteiras.
Para problemas de grande porte, isto geralmente gerará uma solução aceitável (próxima do ótimo real) sem a violação de nenhuma das restrições.
Para problemas menores, esse tipo de procedimento poderá nos levar a soluções inviáveis ou não ótimas.
Capítulo 6
Programação InteiraProblema Relaxado
A todo problema de programação inteira está associado
um problema com a mesma função-objetivo e as
mesmas restrições, com exceção da condição de
variáveis inteiras. A esse problema se dá o nome de
Problema Relaxado
Capítulo 6
Programação InteiraSolução Gráfica
0,
03
1351030
142620
8001008.42
5 ..
618
21
21
21
21
21
21
21
xx
xx
xx
xx
xx
xxts
xxMax
(1)
(2)
(3)
(4)
(5)
(1)
(2) (3)
(4)
(5)
e inteiros
Capítulo 6
Programação InteiraSolução Gráfica
Max x x
s t x x
x x
x x
x x
x x
x x
e inteiros
18 6
5
42 8 100 800
20 6 142
30 10 135
3 0
0
1 2
1 2
1 2
1 2
1 2
1 2
1 2
. .
.
,
x2
x1
(5,28 ; 5,74)
Solução Ótima paraLP Relaxado
Capítulo 6
Programação InteiraSolução Gráfica
Solução Ótima paraLP Relaxado (5,28 ; 5,74)
Solução Ótima para Problema
Inteiro (6 ; 3)
Solução Aproximada doLP Relaxado Ótimo
(5 ; 5)x2
x1
(5,28 ; 5,74)
Capítulo 6
Programação InteiraLP Relaxado
Em um problema de MAXIMIZAÇÃO, o valor ótimo da função-objetivo, do Problema Relaxado, sempre representa um limite superior ao respectivo Problema Inteiro.
Em um problema de MINIMIZAÇÃO, o valor ótimo da função-objetivo, do Problema Relaxado, sempre representa um limite inferior ao respectivo Problema Inteiro.
Capítulo 6
Programação InteiraLP Relaxado
Nenhum ponto inteiro vizinho ao ponto ótimo do problema relaxado é necessariamente viável.
Mesmo que um dos vizinhos seja viável.
Não é necessariamente o ponto ótimo inteiro.
Não é obrigatoriamente uma solução aceitável.
x2
x1
Solução Ótima paraProg.Inteira
Solução Ótima para
LP Relaxado
Capítulo 6
Programação InteiraSolução por Enumeração
Uma idéia que pode resultar em uma solução para um
problema de programação inteira é a de se enumerar
todas as possíveis soluções.
De forma exaustiva, o valor da função-objetivo é
calculado para todas as soluções viáveis e é escolhido
aquele que apresente o maior valor (no caso de
maximização) ou o menor valor (no caso de
minimização).
Capítulo 6
O problema com essa tática de solução está no fato de
que ela só consegue ser aplicada a problemas pequenos.
O número de combinações possíveis de soluções cresce
de forma exponencial, isto é de forma muito rápida. Ex.: Um ILP com 100 variáveis de decisão do tipo binárias
(assumem 0 ou 1) terá até 2100 soluções viáveis, isto é, 1,27 x
1030 soluções possíveis.
Programação InteiraSolução por Enumeração
Capítulo 6
Algoritmo de Branch-And-Bound é mais utilizado atualmente para resolução de problemas do tipo ILP ou MILP.
É uma metodologia geral para solução de ILP e MILP, e existem diversas variantes para tratar diversos tipos de problemas específicos.
A idéia geral é a de se dividir o conjunto de soluções viáveis em subconjuntos sem interseções entre si, calculando-se os limites superior e inferior para cada subconjunto, e então eliminando certos subconjuntos de acordo com regras pré estabelecidas.
Programação InteiraAlgoritmo de Branch-And-Bound
Capítulo 6
Comparativamente ao LP correspondente, o IP levará
muito mais tempo para obter um valor ótimo. Isso está
ligado ao fato que diversos problemas de LP são
resolvidos sucessivamente para se obter a solução de
um IP.
Se o problema for interrompido no meio do processo
uma solução aproximada do problema inteiro pode ser
gerada.
Programação InteiraAlgoritmo de Branch-And-Bound
Capítulo 6
A solução obtida num problema IPL ou MIPL Sem análise de sensibilidade.
Deve ser efetuada alterando-se o problema e obtendo-se nova solução.
Não provê informação similar ao preço de sombra. Muitos softwares que realizam programação inteira são parte
integrante de pacotes de programação linear e produzem análise de sensibilidade, independente desta não ter valor no âmbito de programação inteira.
Programação InteiraAlgoritmo de Branch-And-Bound
Capítulo 6
Usando Solver do Excel Definindo Variáveis Inteiras e Binárias
Capítulo 6
LindoVariáveis Inteiras e Binárias
Os comandos adicionais abaixo são colocados após o comando END ao final das restrições:
FREE <Variável> - Remove os limites de não negatividade imposta a todas as variáveis por default.
GIN <Variável> - Faz a <Variável> uma variável inteira geral.
INT <Variável> - Faz a <Variável> uma variável inteira binária.
Capítulo 6
Problema de Orçamento de CapitalCaso LCL Tecnologia S/A
Capital Requerido em mil R$
Proj.NPV(8%)(mil R$) Ano 1 Ano 2 Ano 3 Ano 4 Ano 5
1 $105.99 70 15 0 20 20
2 $128.90 80 20 25 15 10
3 $136.14 90 20 0 30 20
4 $117.38 50 30 40 0 20
Capital Disponível 200 70 70 70 70
A LCL Tecnologia S/A tem que planejar seus gastos em P&D. A empresa pré-selecionou 4 projetos e deve escolher dentre esses quais deve priorizar em função de restrições orçamentárias. Os dados relevantes encontram-se na tabela abaixo.
Capítulo 6
Caso LCL Tecnologia S/A
Variáveis de Decisão
Função Objetivo = Maximizar o somatório NPV
1,2,3,4i oselecionadfor não i projeto o se , 0
oselecionadfor i projeto o se , 1
iX
4321 38.11714.13690.12899.105 XXXXMax
Capítulo 6
Restrições Orçamentárias
5 Ano - 7020201020
4 Ano - 70301520
3 Ano - 704025
2 Ano - 7030202015
1 Ano - 20050908070
4321
321
42
4321
4321
XXXX
XXX
XX
XXXX
XXXX
Caso LCL Tecnologia S/A
Capítulo 6
Caso LCL Tecnologia S/AO Modelo
0;;;
5 Ano - 7020201020
4 Ano - 70301520
3 Ano - 704025
2 Ano - 7030202015
1 Ano - 20050908070
38.11714.13690.12899.105
4321
4321
321
42
4321
4321
4321
XXXX
XXXX
XXX
XX
XXXX
XXXX
st
XXXXMax
Capítulo 6
Caso LCL Tecnologia S/ASolver do Excel
Capítulo 6
Caso LCL Tecnologia S/ASolver do Excel
Capítulo 6
Caso LCL Tecnologia S/ASolver do Excel
Capítulo 6
Variáveis Binárias eCondições Lógicas
As variáveis binárias também se prestam a selecionar alternativas que sejam condicionais.
No exemplo anterior imagine que não mais de um dos projetos 1, 3 e 4 pudesse ser selecionado. Deveríamos então adicionar:
Se apenas um dos projetos e apenas um dos projetos 1, 2 e 4 tivesse que ser escolhido obrigatoriamente, deveríamos incluir:
1431 XXX
1421 XXX
Capítulo 6
Imagine agora que o projeto 1 dependa de uma tecnologia que deve ser desenvolvida pelo projeto 2, isto é, o projeto 1 só pode ser aprovado se e somente se o projeto 2 for aceito. Deveríamos então incluir:
inviável0,1
aceito foi 2 projeto o apenas1,0
aceitos projetos os ambos1,1
aceitos projetos dos nenhum0,0
0
21
21
21
21
21
XX
XX
XX
XX
XX
Variáveis Binárias eCondições Lógicas
Capítulo 6
Tipo 1 Tipo 2 Tipo 3 Total Disponível
Montagem 2h/unid 3h/unid 2,5h/unid 600h
Pintura 3h/unid 2h/unid 2,5h/unid 500h
Lucro Unitário R$50 R$60 R$65
Preparação R$5.000 R$4.000 R$3.000
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.
Caso LCL Equipamentos S.A.
Capítulo 6
Variáveis de Decisão
Função Objetivo
1,2,3i 0 se 0,
0 se 1,
1,2,3)(i i produto do produzidaser a Quantidade
i
ii
i
X
XY
X
321321 300040005000656050 YYYXXXMax
Caso LCL Equipamentos S.A. Variáveis Binárias
Capítulo 6
Restrições de Produção
Restrições de ligação de Variáveis
5005,223
6005,232
321
321
XXX
XXX
.suficiente o grande é que nº um é 600 :
600
600
600
33
22
11
Obs
YX
YX
YX
Caso LCL Equipamentos S.A. Variáveis Binárias
Capítulo 6
Caso LCL Equipamentos S.A. Variáveis Binárias
=B7*B10
Capítulo 6
Caso LCL Equipamentos S.A. Variáveis Binárias
Capítulo 6
Caso LCL Equipamentos S.A. Variáveis Binárias