Programação Linear Inteira
●
Introduzimos o tema da Programação Linear Inteira. Até o momento, estávamos
considerando que as variáveis de decisão podiam assumir valores reais. Contudo, em
algumas situações é necessário determinar a solução para um problema de
otimização assumindo que as variáveis de decisão devem ser necessariamente
valores inteiros.
●
A Programação Inteira é um tema bastante estudado atualmente e podemos dizer
que não foi desenvolvido ainda um algoritmo eficiente para resolver um Problema de
Programação Linear Inteira (PLI) de tamanho razoável. Na verdade, resolver um PLI é
um problema da classe NP-Completo e é comum na literatura encontrarmos autores
dizendo que não existe solução eficiente para um problema dessa classe e, mais
ainda, qualquer solução correta do problema necessita de tempo exponencial no pior
caso. 1
Programação Linear Inteira
●
Contudo, existem duas classes de algoritmos "aceitáveis", em termos
computacionais, que resolvem problemas grandes: os algoritmos de Planos de Corte
e os algoritmos Enumerativos.
●
O método Branch-and-bound (algoritmo enumerativo), proposto por Land and Doig,
para a resolução de problemas de programação inteira, utiliza uma estratégia de
divisão e conquista.
●
O seu princípio básico é o uso de estimativas no valor da solução ótima de um
problema, para evitar a inspeção de partes de seu conjunto de soluções.
2
Programação Linear Inteira
Considere um exemplo...
Contexto: para a fabricação de bicicletas e triciclos, a linha de soldagem gasta 2
horas para cada bicicleta e 1 hora para cada triciclo, para uma capacidade máxima
disponível de 10 horas da linha de soldagem por dia. Para a montagem, é
necessária 1 hora para cada bicicleta e 2,5 horas para cada triciclo, para uma
capacidade máxima disponível de 12 horas da linha de montagem por dia.
Problema: 0 lucro obtido para cada bicicleta é de R$ 300,00 e para cada triciclo é
de R$ 160,00. Quanto se deve produzir de bicicletas e triciclos para se obter o
máximo lucro diário?
3
Programação Linear Inteira
Modelagem linear:
x1: quantidade de bicicletas
x2: quantidade de triciclos
Função objetivo: f(x1,x2) = 300x1 + 160x2
Restrições:
2x1 + x2 ≤ 10
x1 + 2,5x2 ≤ 12
x1, x2 ≥ 0 e inteiros!
Problema: maximizar z = f(x1,x2)
4
Programação Linear Inteira
Como temos duas variáveis, uma análise
gráfica é bem-vinda!
5
Programação Linear Inteira
●
Como exercício, vamos imaginar que não fosse possível uma visualização gráfica
para obter o resultado.
●
Vamos então tentar fazer vários (alguns!) arredondamentos por tentativa e erro
para encontrar a solução ótima, ou seja, o máximo lucro com valores inteiros das
variáveis de decisão.
6
Programação Linear Inteira
Vemos, que o simples arredondamento
para um ponto vizinho não encontra
uma solução viável, por exemplo, os pontos
com coordenadas (3,4) e (4,4) e quando a
encontra, a solução viável não é ótima.
Por exemplo, o ponto de coordenadas (3,3).
Nesse caso, a solução ótima, o ponto H(4,2),
não é um ponto vizinho ao ponto P.
7
Programação Linear Inteira
●
O simples arredondamento pode levar a valores que não são ótimos, ou pior,
longe da solução ótima, o que invalida o resultado. Neste caso, devemos
empregar modelos de programação linear inteira, empregando algoritmos
especializados para encontrar valores inteiros para as variáveis de decisão que
fornecem o valor máximo da função objetivo.
●
Um algoritmo muito empregado em softwares comerciais de PO para a solução
de problemas que podem ser aplicados modelos de programação linear inteira é
o algoritmo branch and bound.
8
O algoritmo Branch and Bound
Relembrando...
x1: quantidade de bicicletas
x2: quantidade de triciclos
maximizar z = 300x1 + 160x2
Restrições:
2x1 + x2 ≤ 10
x1 + 2,5x2 ≤ 12
x1, x2 ≥ 0 e inteiros!
Observamos que o ponto P(3,3;3,5) é o ponto de intersecção das equações
oriundas das duas restrições impostas ao problema.
9
O algoritmo Branch and Bound
10
O algoritmo Branch and Bound
●
Inicialmente, vamos determinar o valor máximo da função objetivo como um
problema de programação linear com variáveis reais contínuas.
●
Vamos agora calcular os pontos extremos do conjunto das soluções viáveis:
●
Substituindo em z = f(x1,x2) os pontos C(5,0), D(0;4,8) e P(3,3;3,5)
Para C => z = 300.(5) + 160.(0) = 1500
Para D => z = 300.(0) + 160.(4,8) = 768
Para P => z = 300.(3,3) + 160.(3,5) = 1550
11
O algoritmo Branch and Bound
●
Temos então que o ponto P fornece o valor máximo para a função
objetivo, como mostrado na figura.
●
Note que as coordenadas do ponto P não são valores inteiros, o que
contraria as restrições.
●
Entretanto, este é o ponto inicial do algoritmo branch and baund.
12
O algoritmo Branch and Bound
Determinação do ponto P no
processo Inicial do algoritmo.
13
O algoritmo Branch and Bound
●
Como os valores x1 e x2 do ponto P não são inteiros, o algoritmo do branch
and bound vai escolher uma das variáveis de decisão da solução ótima
cujo valor não é inteiro.
●
Vamos escolher a variável x1, ou seja, a região 3<x1<4 da região de soluções
viáveis não contém nenhum valor inteiro de x1.
●
A região nesse intervalo de x1 será descartada.
●
Dividimos o problema inicial P em dois problemas (ou duas regiões de
soluções viáveis) P1 e P2.
●
Cada problema será resolvido separadamente.
14
O algoritmo Branch and Bound
G
Descarte da região 3 < x1 < 4,
originando P1 e P2.
15
O algoritmo Branch and Bound
●
O ponto G foi obtido substituindo x1 = 3 na equação x1 + 2,5x2 = 12,
resultando em x2 = 3,6.
●
O ponto G é onde obtemos o valor máximo da função objetivo
z = 300x1 +160x2,
na região de soluções viáveis de P1, com z = 300.(3) + 160.(3,6) = 1476.
●
Para o problema P1, a variável de decisão x2 não apresenta um valor
inteiro, logo o algoritmo continuará a ser aplicado.
16
O algoritmo Branch and Bound
17
O algoritmo Branch and Bound
●
Aplicando o mesmo procedimento usado para o problema original P,
vamos resolver o problema P1, escolhendo a variável x2, o que resulta na
divisão do problema P1 em problemas P11 e P12.
●
Para o valor x2 = 3,6, vamos eliminar a região de 3 < x2 < 4, obtendo as
regiões P11 e P12.
18
O algoritmo Branch and Bound
19
O algoritmo Branch and Bound
●
Após a ramificação, vamos resolver primeiro P11.
●
O ponto I(2,4) é obtido substituindo x2 = 4 na equação x1 + 2,5x2 = 12,
resultando em x1 = 2.
●
Para o problema P11, as variáveis de decisão apresentam valores inteiros,
logo o algoritmo nesse ramo para de ser executado.
20
O algoritmo Branch and Bound
●
Podemos voltar para o problema P12. O ponto J(3,3) é obtido no encontro
das retas x1 = 3 e x2 = 3. É no ponto J que obtemos o valor máximo de
z = 300x1 +160x2, ou seja, z = 300.(3) + 160(3) = 1380.
●
Para o problema P12, as variáveis de decisão apresentam valores inteiros
e o algoritmo nesse ramo também para de ser executado.
21
O algoritmo Branch and Bound
●
Ainda resta resolver o problema P2...
●
Para a região de soluções viáveis de P2, o ponto H é onde obtemos o valor
máximo da função objetivo
z = 300x1 +160x2, com z = 300.(4)+ 160.(2) = 1520.
●
Neste caso, as duas variáveis de decisão apresentam valores inteiros e o
algoritmo não avança nesse ramo.
22
O algoritmo Branch and Bound
●
Verificando a construção da árvore de solução do algoritmo branch and
bound vemos que todos os ramos apresentam soluções inteiras.
●
Sendo assim, o processo da aplicação do algoritmo está encerrado.
●
A solução ótima é encontrada no ramo onde os valores inteiros das
variáveis de decisão fornecem o maior valor da função objetivo.
●
No caso, o ramo do problema P2, com z = 1520, o maior valor com
variáveis de decisão com valores inteiros.
23
O algoritmo Branch and Bound
24
O algoritmo Branch and Bound
●
Exercício:
Compare os valores das variáveis de decisão considerando o problema
contínuo (ponto P) com os valores obtidos com o algoritmo branch and
bound para variáveis inteiras (Ponto H). O que podemos concluir?
25
O algoritmo Branch and Bound
●
Exercício:
Na resolução de um problema de programação inteira, em que o objetivo
é minimizar uma função z = f(x1, x2, … , x25) definida em R25, obteve-se no
nó inicial uma solução não inteira com z = 100. Escolheu-se a variável x10
para começar a construir a árvore do algoritmo branch-and-bound. No
lado esquerdo, obteve-se uma solução inteira com z = 120. No lado direito,
obteve-se uma solução em que todas as variáveis são inteiras exceto x9
que tem o valor 4,7 e a que corresponde z = 130. O que se deve fazer a
seguir? Por quê?
26