Gol do Brasail

Aula 2 – Pesquisa Operacional
Método do Branch and bound – passa pelo problema de programação linear relaxado

Problema de Programação Linear (P.I.)
As variáveis são inteiras – X ԑ ƶ+

Max cTx
s.a.
Ax=b
X ԑ ƶ+
Dentro da região viável, se tenho que um dos pontos viáveis tem variáveis não inteiras, não se pode utilizá-las. AO arredondar para cima ou para baixo não adianta porque tem diversas variáveis e provavelmente um ou ambos os casos ficaria fora da região viável e o arredondamento não garante que o ponto seja o ótimo inteiro.
Quando a solução do problema relaxado (PR) for inteira, esta solução pode ser deste problema de variáveis somente inteiras. No caso presente, o método gráfico não é mais eficiente e na tem o método simplex.
Se a envoltória convexa for composta por pontos extremos, vértices, sendo todos pontos inteiros, a solução do PR coincide com a do Problema original, com isso pode-se resolver pelo método simplex normal.
Solução do problema relaxado é sempre maior ou igual ao problema inteiro.
Por exemplo: Problema abaixo

Uma das bolinhas, dentre muitas as que podem aparecer, sendo a combinação de todos os pontos inteiros, será uma das soluções.
Solução do problema relaxado é sempre maior ou igual ao problema inteiro. No caso acima, se supormos que a solução ótima do PR for o (9/2,3), e sua solução será 7,5. No caso do P, como só será de números inteiros, ele terá um valor de no máximo 7.

Resolvendo:
Resolve-se o problema relaxado e chega-se a uma solução ótima (x*PR) para ele que nem sempre será formada por números inteiros (xj não inteiro).

X1 ≥ 5 ou X1 ≤ 4
Piso – maior inteiro menor do que o número.
Teto – maior inteiro maior do que o número.

(Pode-se dividir o problema P em dois novos problemas P1 e P2 em que a envoltória convexa C de P1 U P2 é estritamente contida na envoltória de P). No fundo não é o valor da função objetivo que eu quero como número inteiro e sim as variáveis, logo o Z será inteiro devido as