如果x不都是1,那么设j是第一个≠1的x的下标,即X = (1,1,1,…,1,x
j
_j
j,0,0,0,…,0)。如果X不是最优解,那么一定有一个最优解Y = (y
1
_1
1,y
2
_2
2,……,y
n
_n
n),使Σp
i
_i
iy
i
_i
i>Σp
i
_i
ix
i
_i
i,设k是x≠y的最小下标,那么有三种情况,证明这三种情况都不正确就可以:
若k<j,这个时候x
k
_k
k=1,假设有y
k
_k
k≠x
k
_k
k,那么y
k
_k
k<x
k
_k
k 若k=j,已经假设y
k
_k
k≠x
k
_k
k,所以只有两种情况。y
k
_k
k>x
k
_k
k时,在X里,Σ
i
=
1
k
^{k}_{i=1}
i=1kp
i
_i
ix
i
_i
i = M(质量上限),那Σ
i
=
1
k
^{k}_{i=1}
i=1kp
i
_i
iy
i
_i
i肯定 > M,肯定不可能。那就只可能是y
k
_k
k<x
k
_k
k。 若k>j,也有 Σ
i
=
1
k
^{k}_{i=1}
i=1kp
i
_i
iy
i
_i
i > M,矛盾。
发现了吗,上面3中的三种情况,除了Σ
i
=
1
k
^{k}_{i=1}
i=1kp
i
_i
iy
i
_i
i > M这种矛盾情况就是y
k
_k
k<x
k
_k
k,所以我们只要证y
k
_k
k<x
k
_k
k矛盾即可得证。 那么我就将Y中的y
k
_k
k增加到x
k
_k
k那么多,那么一定要将k后面的若干个y——(y
k
+
1
_{k+1}
k+1,y
k
+
2
_{k+2}
k+2,……,y
n
_n
n)中减少相同的质量,假设这个解是Z=(z
1
_1
1,z
2
_2
2,……,z
n
_n
n)。众所周知,前面的贵后面的便宜,贵的质量增加了,便宜的质量减少了(用数学写法表示见图),那Z就一定肯定是更优解。
δ是递增序列(元素是i),δ’是J中使用的序列(元素是r),找到第一个不同的作业r
a
_a
a≠i
a
_a
a,找到递增序列δ这个位置的作业i
a
_a
a在J序列δ’中的位置r
b
_b
b,r
b
_b
b=i
a
_a
a,交换J序列中的r
a
_a
a和r
b
_b
b(因为d
r
a
_{ra}
ra=d
r
b
_{rb}
rb所以可交换),不停如此交换可以从δ’转化为δ,得证。