Prova da correção do algoritmo da mochila fracionária

[Enunciado]   Considere uma instância ( p, v, n, c) do problema da mochila fracionária. Suponha que os objetos estão em ordem crescente de valor específico. Queremos provar que a mochila fracionária produzida pelo algoritmo Mochila-Fracionária tem valor máximo.

Prova

A prova é inspirada em dualidade de programação linear. Diremos que um vetor primal é qualquer vetor racional x[1 .. n]. Diremos que um vetor primal x[1 .. n] é viável se p · xc e 0 ≤ x[j] ≤ 1 para todo j em 1 .. n.

Diremos que um vetor dual é qualquer vetor racional y[0 .. n] e diremos que um vetor dual y[0 .. n] é viável se y[i] ≥ 0 para todo i e y[0] p[i] + y[i] ≥ v[i] para todo i em 1 .. n.

Lema da Dualidade: Para qualquer vetor primal viável x e qualquer vetor dual viável y, vale a desigualdade ∑ 1 ≤ j ≤ nv[j]x[j] ≤ y[0] c + ∑ 1 ≤ i ≤ ny[i].

Para provar o lema basta verificar a sequinte sequência de igualdades e desigualdades:

∑ v[i]x[i] ∑ (y[0] p[i] + y[i]) x[i]
  = y[0] ∑ x[i]p[i] + ∑ x[i] y[i]
  y[0] c + ∑ x[i] y[i]
  y[0] c + ∑ y[i].

O lema tem a seguinte consequência: se x é primal viável e existe um vetor dual viável y tal que ∑ v[i] x[i] = y[0] c + ∑ y[i] então x maximiza v · x. Essa observação será explorada a seguir para mostrar que o vetor x calculado pelo algoritmo Mochila-Fracionária maximiza x · v. Vamos tratar em separado de dois casos, conforme o valor da soma dos pesos:

CASO 1:  ∑ p[i] ≤ c.  Nesse caso, o algoritmo devolve um vetor x tal que x[i] = 1 para todo i. É claro que x é viável. Agora considere o vetor dual y definido assim: y[0] = 0 e y[i] = v[i] para todo i ≥ 1. É claro que y é viável. Como x · v = ∑ v[i] = y[0] c + ∑ y[i], o Lema acima garante que x maximiza x · v.

CASO 2:  ∑ p[i] > c.  Seja k o menor índice tal ∑ k < m ≤ np[m] ≤ c. O algoritmo devolve um vetor primal x tal que x[i] = 0 para todo i em 1 .. k−1, x[k] = (c − ∑ k < m ≤ np[m]) / p[k], e x[m] = 1 para todo m em k+1 .. n. É fácil constatar que x é viável. Resta mostrar que x maximiza x · v.

Seja y o vetor dual definido assim:

Para mostrar que y é viável, basta verificar que y[m] ≥ 0 para todo m em k .. n. Faremos isso a seguir. Por hipótese, v[k] / p[k] ≤ v[m] / p[m] para todo m em k .. n. Logo, para todo m em k .. n temos p[m] y[0] = p[m]v[k]/p[k] ≤ p[m]v[m]/p[m] = v[m]. Logo, v[m] − p[m]y[0] ≥ 0 e portanto y[m] ≥ 0 para todo m em k .. n. Assim, y é viável.

Finalmente, observe que

x · v = ∑ x[i]v[i]
  = x[k]v[k] + ∑ k < m ≤ nv[m]
  = (c − ∑ k < m ≤ np[m])v[k]/p[k] + ∑ k < m ≤ nv[m]
  = c y[0] − (∑ k < m ≤ np[m]) y[0] + ∑ k < m ≤ nv[m]
  = y[0] c + ∑ k < m ≤ n (v[m] − y[0] p[m])
  = y[0] c + ∑ k < m ≤ ny[m]
  = y[0] c + ∑ 1 ≤ i ≤ ny[i].

A última linha segue da observação de que y[i] = 0 para todo i em 1 .. k−1 e y[k] = 0. Portanto, de acordo com o Lema acima, x maximiza x · v.