[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.
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 · x ≤ c
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 ≤ n v[j]x[j] ≤ y[0] c + ∑ 1 ≤ i ≤ n y[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 ≤ n p[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 ≤ n p[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 ≤ n v[m] | |
= | (c − ∑ k < m ≤ n p[m])v[k]/p[k] + ∑ k < m ≤ n v[m] | |
= | c y[0] − (∑ k < m ≤ n p[m]) y[0] + ∑ k < m ≤ n v[m] | |
= | y[0] c + ∑ k < m ≤ n (v[m] − y[0] p[m]) | |
= | y[0] c + ∑ k < m ≤ n y[m] | |
= | y[0] c + ∑ 1 ≤ i ≤ n y[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.