Programação Inteira

Prévia do material em texto

Universidade Lúrio 
Faculdade de Engenharia 
Licenciatura em Engenharia Geológica 
III Nível, I Semestre 
 
Investigação Operacional 
 
Programação Inteira 
 
 
 
 
 Estudantes: Docente: 
 Ali Yunussa, no 005 Ernesto Milissão, Lic. 
 Adiame M. Anli, no 002 
 Anlawe Abudo, no 008 
 Narciso A. Sitoe, no 023 
 
 
 
 
 
 
 
 
Pemba, Outubro de 2018 
 
2 
 
Índice 
1. Introdução...................................................................................................................................... 3 
2. Objectivos ...................................................................................................................................... 3 
2.1. Geral:.......................................................................................................................................... 3 
2.2. Específicos: ................................................................................................................................ 3 
3. Programação Inteira..................................................................................................................... 4 
Algoritmo Branch-And-Bound (B&B) ........................................................................................... 5 
4. Conclusão ..................................................................................................................................... 10 
5. Referências bibliográficas .......................................................................................................... 11 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
3 
 
1. Introdução 
O presente trabalho da cadeira de Investigação Operacional é de carácter avaliativo e tem como 
tema Programação Inteira. 
Um Problema de Programação Inteira é um modelo de Programação Linear no qual algumas 
ou todas variáveis do problema são números inteiros. 
2. Objectivos 
2.1. Geral: 
 Determinar se o problema é de minimização ou de maximização 
2.2. Específicos: 
 Reconstruir a árvore de problemas; 
 Saber e explicar se a árvore está completamente explorada ou não e porquê; 
 Indicar os melhores limites, superior e inferior, conhecidos até ao momento (No método de 
Branch-and-Bound). 
 
 
 
 
 
 
 
 
 
 
 
 
4 
 
3. Programação Inteira 
Um Problema de Programação Inteira é um modelo de Programação Linear no qual algumas ou 
todas variáveis do problema são números inteiros. Quando todas variáveis são inteiras, o modelo 
é denominado Programação Inteira Pura; caso contrário é denominado Programação Inteira 
Mista. Embora a Programação Inteira inclua também a Programação Não-Linear Inteira, em 
praticamente todos modelos da vida real se preserva a estrutura linear das funções, pelo que 
quase não existe diferença entre a Programação Inteira e Programação Linear Inteira. 
Os modelos de Programação Linear Inteira serão então do tipo dos modelos de Programação 
Linear, sujeitos a restrições adicionais indicando que algumas ou todas variáveis são 
discretas (inteiras), conforme se pode ver no exemplo seguinte. 
 
Objectivo: Maximizar 
{
 
 
 
 
Os algoritmos de Programação Linear Inteira (PLI) são baseados na exploração do sucesso 
computacional da resolução de problemas de Programação Linear (PL), uma vez que os 
problemas que tratam de soluções inteiras fazem uma busca dentro da região admissível. Os 
algoritmos apresentam três passos para a sua resolução, sendo: 
1o Passo: Relaxar a região de soluções de Programação Linear Inteira (PLI) eliminando a 
restrição inteira imposta a estas variáveis e substituindo qualquer variável binária y pela contínua 
 . Neste passo, transformamos um problema linear inteira em um problema linear (PL). 
2o Passo: Faz-se então a resolução do PL relaxado e identifica-se uma solução óptima contínua 
(de valores não inteiros). A resolução desta etapa pode ser feita através dos métodos já 
conhecidos como o Método Simplex. 
3o Passo: Começando do ponto óptimo contínuo, adicionam-se restrições especiais que 
modifiquem iterativamente a região de soluções de PL de maneira que, a certa altura, resultará 
em um ponto extremo óptimo que deverá satisfazer os requisitos de integralidade. 
5 
 
Os algoritmos existentes desenvolvidos para PLI, executam o terceiro passo acrescentando 
restrições especiais. 
São dois os métodos mais conhecidos: branch-and-bound (B&B) e planos de corte, porém, 
neste trabalho será apresentado o “algoritmo branch-and-bound (B&B)”. 
 
Algoritmo Branch-And-Bound (B&B) 
Este algoritmo será descrito com base num exemplo. 
Exemplo: seja o PLI seguinte: 
Max F(x) = 5x1 + 4x2 
Sujeito à: {
 
 
 
 
 
 
A região de soluções do problema de PLI é definida pelos pontos da grade seguinte: 
 
A solução do problema relaxado, ilustrado pela grade (denominado como PL1), é dada pelos 
vértices das duas restrições, ou seja, x1 = 3:75; x2 = 1:25 e f (x) = 23:75. 
Mas como a solução óptima do problema relaxado não satisfaz a condição de integralidade, o 
algoritmo B&B modifica a região de soluções de modo a identificar a solução óptima do 
problema de PLI. Primeiramente, seleccionamos uma das variáveis inteiras cujo valor óptimo em 
PL1 seja não inteiro. Seleccionamos a variável x1 = 3:75, tomando 3 < x1 < 4 da região de 
soluções de PL1 com nenhum valor inteiro de x1, podendo retirá-la da região total. Esse 
6 
 
passo faz surgir dois problemas de PL que são equivalentes ao PL1. A região criada é 
apresentada na grade seguinte, com: Região PL2 = Região PL1 + (x1 ≤ 3) 
 Região PL3 = Região PL1 + (x1 ≥ 4) 
 
Se usarmos esta lógica para eliminar a condição de integralidade gerando regiões relaxadas 
impondo restrições adequadas (que cercam a condição de valores inteiros para as variáveis), 
teremos PLs cujos pontos extremos óptimos satisfaçam as restrições inteiras. Na verdade, 
resolveremos o PL1 lidando com uma sequência de PLs contínuos. 
As novas restrições, x1 ≤ 3 e x1 ≥ 4 são mutuamente exclusivas, de modo que PL2 e PL3 nos 
“nós" 2 e 3 devem ser tratadas como PLs. 
Essa dicotomização dá origem ao termo ramificação no algoritmo B&B, sendo neste caso, x1 
denominada de variável de ramificação. 
O PLI óptimo se encontra em PL2 ou em PL3. Em consequência, os dois sub-problemas devem 
ser examinados e escolhemos arbitrariamente PL2 para ser o primeiro: 
Max: F(x) = 5x1 + 4x2 
Sujeito à: {
 
 
 
 
 
Resolvendo este problema, chega-se à resposta da ramificação 2, do esquema seguinte: 
 
 
7 
 
 
 
É notório que a solução de PL2 apresenta valores inteiros para as variáveis x1 e x2, deste modo 
diz-se que o problema é incumbente e que não precisa ser mais investigado, pois não pode dar 
nenhuma solução melhor para o PLI com esta ramificação. Entretanto, não se pode ainda afirmar 
que esta solução é a melhor solução para o problema original pois, o PL3 ainda pode fornecer um 
valor melhor para F(x). 
Podemos afirmar apenas que F(x) = 23, encontrada em PL2, é o limite inferior do valor óptimo 
para a função objectivo, isto ´e, qualquer sub-problema não examinado que apresente um valor 
menor que este deve ser descartado como não promissor. Já se ele produzir umasolução melhor, 
actualizamos o valor do limite inferior como sendo o desta nova solução. 
Como F(x) = 23:75 em PL1 e todos os coeficientes da função objectivo são inteiros, é 
impossível, para este caso, que PL3 produza uma solução inteira melhor com F(x) > 23, assim 
descartamos PL3. 
O algoritmo B&B agora está completo porque ambas, PL2 e PL3, foram examinadas e 
descartadas (a primeira por produzir uma solução inteira e a segunda por não ser capaz de 
melhorar tal solução). 
Assim, conclui-se que a solução óptima do PLI está associada com o limite inferior encontrado 
em PL2, ou seja, x1 = 3; x2 = 2 e F(x) = 23. 
 
8 
 
Resoluções alternativas 
E se: 
1. No PL1, em vez de x1 escolhêssemos x2 como variável de ramificação? 
2. Ao seleccionar o próximo sub-problema a ser examinado, resolvêssemos PL3 em vez de PL2? 
Se fizermos a alteração sugerida no item 1 e 2, os cálculos resultantes mudarão, como pode ver a 
seguir: 
A criação dos sub-problemas PL4 e PL5 advêm da solução não inteira de PL3. Temos então: 
- Região PL4 = Região PL3 + (x2 ≤ 0) = Região PL1 + (x1 ≥ 4) + (x2 ≤ 0) 
- Região PL5 = Região PL3 + (x2 ≥ 1) = Região PL1 + (x1 ≥ 4) + (x2 ≥ 1) 
Agora, temos três sub-problemas a serem examinados: PL2, PL4 e PL5. Suponha que optemos 
por examinar PL5 em primeiro lugar. O PL5 não tem nenhuma solução e, em decorrência, está 
descartado. 
Em seguida, examinamos PL4. A solução óptima é x1 = 4:5; x2 = 0 e F(x) = 22:5. O valor não 
inteiro de x1 leva a dois ramos x1 ≤ 4 e x1 ≥ 5, e à criação dos sub-problemas PL6 e PL7 com 
base em PL4: Região PL6 = Região PL1 + (x1 ≥ 4) + (x2 ≤ 0) + (x1 ≤ 4) 
 Região PL7 = Região PL1 + (x1 ≥ 4) + (x2 ≤ 0) + (x1 ≥ 5) 
Assim, pode se construir a seguinte árvore alternativa: 
 
9 
 
Agora, os sub-problemas PL2, PL6 e PL7 precisam ser examinados. Seleccionando PL7, o 
problema não tem nenhuma solução viável e, portanto, está descartado. Em seguida, 
seleccionamos PL6, sendo que este problema dá a primeira solução inteira (x1 = 4; x2 = 0 e F (x) 
= 20) e, assim, fornece o primeiro limite inferior para o valor óptimo da função objectivo para 
PLI. 
Ficamos ainda com PL2, que dá uma solução inteira melhor, como visto no exemplo. Deste 
modo, o limite inferior é actualizado e nesse ponto, com todos os sub-problemas interpretados, a 
melhor solução é a encontrada para PL2. 
A sequência de solução apresentada (PL1 PL3 PL5 PL4 PL7 PL6 PL2) é a pior 
hipótese de passos possíveis para o problema do exemplo, pois foram percorridos todos os ramos 
antes de encontrarmos a solução óptima. 
Dos dois cenários apresentados anteriormente, podemos concluir que a execução do método 
B&B não garante uma solução PLI global, apenas de soluções locais (dependendo do tamanho e 
complexidade do problema). 
Podemos utilizar outros algoritmos matemáticos auxiliares ao B&B, como o algoritmo de Planos 
de Corte, que actuando em conjunto com algoritmo B&B forma o algoritmo chamado de Branch-
and-Cut. Ainda, como visto, o algoritmo pode caminhar em dois sentidos na procura da solução 
óptima, isto é, verticalmente (busca em profundidade) e horizontalmente (busca em largura). 
 
 
 
 
 
 
 
 
10 
 
4. Conclusão 
Problemas de Programação Linear Inteira (PLI) pertencem a optimização discreta ou 
combinatória, pois algumas das variáveis fazem parte de um conjunto discreto, tipicamente, um 
subconjunto dos números inteiros. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
11 
 
5. Referências bibliográficas 
Cantão, L. e Stark, F.; Programação Linear-PL. 
 
	1. Introdução
	2. Objectivos
	2.1. Geral:
	2.2. Específicos:
	3. Programação Inteira
	Algoritmo Branch-And-Bound (B&B)
	4. Conclusão
	5. Referências bibliográficas