Seja S=x in B^|N1|+|N2|: sumj in N aj xj <= b, onde aj>0 para todo j in N. Dados i, j in N, i neq j, encontre condições necessárias e suficientes para que:
xi+xj <= 1, forall x in S.

Passo 1

Beleza, o enunciado diz o seguinte: temos um conjunto
S = lxin0,1^|N1|+|N2| : sumkin N ak,xk <= br,
com todos os xi + xj <= 1, forall,xin S . Queremos achar quando, para duas variáveis diferentes e , vale sempre
Conteúdo: é basicamente teoria de “knapsack” (mochila) e cobertura (“cover”). A gente vai usar a ideia de que, se colocar 1 em e viola a capacidade , então nunca dá para ter os dois iguais a 1. E vice-versa.

Passo 2

Primeiro, mostramos que
ai + aj > b ;Longrightarrow; xi + xj <= 1;forall xin S
Teoria: se , qualquer vetor que tenha e faria
,
violando a restrição da mochila. Logo, não há com os dois 1 juntos, e sempre dá .

Passo 3

Agora a recíproca: suponha que para todo ai + aj <= b, valha xi=1,;xj=1,;xk=0;forall kneq i,j . Se por acaso tivéssemos
ai + aj > b
então o vetor que define
satisfazeria

ou seja, estaria em , mas tem , contradição. Logo é impossível . A única opção é

Resposta

Condição necessária e suficiente:
boxedai + aj > b

Exercícios relacionados