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, forall x in S,

Passo 1

Beleza, bora resumir o que tá rolando. A gente tem um problema tipo “knapsack” (mochila):
  • Variáveis binárias S=lxin0,1^N : sumjin Naj,xj <= br para todo xi <= xjforall,xin S;? .
  • Cada item tem peso (ou “valor”) positivo .
  • A capacidade da mochila é .
    Então o conjunto de soluções viáveis é
O que a questão pede é: “quais condições necessárias e suficientes sobre para garantir
Ou seja, sempre que a gente também devia ter .
Para resolver isso a gente vai usar:
  • Definição de viabilidade no knapsack.
  • Observação de que a única forma de violar é ter .

Passo 2

Vamos entender quando xi = 1 e xj = 0 falha.
Ela falha exatamente se existe algum sumkin Nak,xk = aicdot1 + ajcdot0 + sumkin Nsetminusi,jak,xk ;>=; ai, com
Para esse , a soma de pesos seria
pois os outros são 0 ou 1. O menor peso total que dá pra arrumar com é justamente escolhendo todos os outros , daí o total fica .

Passo 3

Agora, quando esse ai > b não pode estar em xi=1,;xj=0,; xk=0;forall kneq i,j ?
Se . No caso mínimo que acabamos de falar, isso dá
Em outras palavras, se , qualquer tentativa de colocar já estoura a capacidade mesmo que você deixe todo mundo – incluindo – zerado. Logo não existe vetor em com , e então sempre que você já é obrigado a tomar (ou senão não tá em ).
Por outro lado, se , basta escolher o vetor com
para ter , isto é viável e quebra .

Resposta

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

Exercícios relacionados