Restrições disjuntas

Como se sabe, as restrições de um PL devem ser satisfeitas simultaneamente pelas variáveis. Do ponto de vista lógico, isso representa um AND. Porém, existe um modo de modelar um OR, ou seja, permitir que as variáveis satisfaçam uma ou outra restrição? A resposta é sim, e essa modelagem é obtida através das restrições disjuntas.

Vamos começar por um exemplo de uma dimensão. Suponha que queiramos que x satisfaça x <= 1 ou x >= 3. Para isso, introduzimos uma novo variável y binária (ou seja y=0 ou y=1). Se x satisfizer x <= 1, então y=0, se x satisfizer x >= 3, então y=1. Seja M um número positivo muito grande. Modificamos as desigualdades na seguinte forma:


Para entender o funcionamento desse modelo, suponha que y=0. Então o modelo fica:


Como M é suficientemente grande, x >= 3 – M será satisfeito para qualquer x. Ou seja, a desigualdade torna-se redundante e podemos desconsiderá-la. Agora supomos que y=1. Temos então:


A interpretação é análoga. A ideia básica dessa técnica consiste em tornar uma das desigualdades redundantes.

Podemos generalizar essa ideia para que, dado um conjunto de desigualdades, apenas uma delas seja satisfeita. Se tivermos três restrições para duas variáveis, por exemplo:



Introduzimos as variáveis . Se a primeira desigualdade for satisfeita, queremos que (análogo para as outras desigualdades). Consideramos o seguinte modelo:

Observe que exatamente um dos ‘s tem 1 e o resto tem 0. Ele age como um Multiplexador. Quando , dá pra ver que a segunda e terceira desigualdades ficam redundantes, já que os outros termos são sempre positivos e só tendem a aumentar o lado direito da desigualdade. Entretanto, todos os termos envolvendo da primeira equação zeram, fazendo com que ela fique na forma original. Os outros casos são análogos.

Referências

[1] http://www.dcc.unicamp.br/~cid/cursos/MO420/Material-didatico/

Os comentários estão fechados.

%d bloggers like this: