第1页:第五章习题封面
第五章2, 3, 8, 9
第2页:习题P121-2题目
P121-2
- 求以下情况背包问题的最优解,n=7,m=15,(p1,…, p7)=(10,5,15,7,6,18,3)和(w1,…,w7)=(2,3,5,7,1,4,1)。
- 将以上数据情况的背包问题记为I。设FG(I)是物品按pi的非增次序输入时由GREEDY-KNAPSACK所生成的解,FO(I)是一个最优解。问FO(I)/ FG(I)是多少?
- 当物品按wi的非降次序输入时,重复②的讨论。
第3页:P121-2:按效益质量比输入
P121-2
- ①按照pi/wi的非增序可得(p5/w5,p1/w1,p6/w6,p3/w3,p7/w7,p2/w2,p4/w4)=(6,5,9/2,3,3,5/3,1)所以最优解为:(1,2/3,1,0,1,1,1),并且FO(I)=166/3
- ②按照pi的非增次序输入时,得到(p6,p3,p1,p4,p5,p2,p7)=(18,15,10,7,6,5,3),对应的(w6,w3,w1,w4,w5,w2,w7)=(4,5,2,7,1,3,1),则FG(I)的解为(0,1,0,1,1,0,4/7),并且FG(I)=47,所以,FO(I)/FG(I)=166/141.
第4页:P121-2:按质量非增序输入
P121-2
- ③按照wi的非增次序输入时,得到(w5,w7,w1,w2,w6,w3,w4)=(1,1,2,3,4,5,7),(p5,p7,p1,p2,p6,p3,p4)=(6,3,10,5,18,15,7),FW(I)的解为(1,1,4/5,0,1,1,1),FW(I)=54,所以FO(I)/FW(I)=83/81.
第5页:习题P122-3题目
P122-3
第6页:P122-3的反例
否定一个命题,直接举反例即可设n=3,M=6,(p1,p2,p3)=(3,4,8),(w1,w2,w3)=(1,2,5)按照pi/wi的非增序得到(p1/w1,p2/w2,p3/w3)=(3,2,1.6),则其解为(1,1,0),而事实上最优解是(1,0,1)。
第7页:习题P123-8题目
P123-8
- ①当n=7,(p1,…, p7)=(3,5,20,18,1,6,30)和(d1,…,d7)=(1,3,4,3,2,1,2)时,算法5.4所生成的解是什么?(P123)
- ②证明即使作业有不同的处理时间定理5.3亦真。这里,假定作业i的效益pi>0,要用的处理时间ti>0,限期di≥ti.
第8页:P123-8的解
P123-8
- 解:①按照pi的非增排序对作业重新排序,得到
- (p7, p3, p4, p6, p2, p1, p5)=(30,20,18,6,5,3,1),对应的期限为( 2, 4, 3, 1,3,1,2),
- 按照算法5.4生成的解为:1.J(1)=7,2.J(1)=7, J(2)=3;3.J(1)=7, J(2)=4, J(3)=3;4.J(1)=6, J(2)=7, J(3)=4, J(4)=3;
第9页:定理5.3在作业处理时间不同时仍成立
P123-8
- ②证明即使作业有不同的处理时间定理5.3亦真。这里,假定作业i的效益pi>0,要用的处理时间ti>0,限期di≥ti.
- 定理5.3:设J是k个作业的集合,σ=i1i2…ik是J中作业的一种排序,它使得di1≤di2≤…≤dik. J是一个可行解,当且仅当J中的作业可以按照σ的次序又不违反任何一个期限的情况下来处理.
第10页:可行性排列的证明
P123-8
- 证明:显然即使作业的处理时间各不相同(ti>0,di≥ti),如果J中的作业可以按照σ的次序排列而又不超出任何一个期限的限定,即对σ次序中的任一个作业k,满足dk≥,则J就是一个可行解。
- 下面证明如果J是可行解,σ=i1i2…ik使得J中的作业可以按照di1≤di2≤…≤din排列而又不超出任何一个作业的期限。
第11页:按期限排序的交换论证
- 若J是可行解,则必存在一种排列σ’=r1r2…rn,使得对任意的rk,都有.
- 设σ是按照di1≤di2≤…≤din排列的作业序列。若σ’=σ,则σ中每个作业都不会超出其期限。命题得证.
- 假设σ’≠σ,那么令a是使ra≠ia的最小下标,设rb=ia,显然b>a.在σ’中将ra与rb相交换,因为drb≤dra,显然交换后ra和rb可以在各自的期限前完成作业。
第12页:交换后中间作业的可行性
- 下面证明ra和rb之间的作业也能按期完成。因为drb≤dra,而显然二者之间的所有作业rt,都有drb≤drt,又由于σ’是可行解,所以,ra和rb交换后ra和rb之间的作业也能按期完成。
- 作业ra和rb交换后,所有作业可依新产生的排列σ’’=s1s2…sn的次序处理而不违反任何一个期限,连续使用这种方法,σ’就可转换成σ且不违反任何一个期限,定理得证。
第13页:习题P123-9题目
P123-9
- ①对于5.3节的作业排序问题证明:当且仅当子集合J中的作业可以按下述规则处理时它表示一个可行解;如果J中的作业i还没分配处理时间,则将它分配在时间片[α-1,α]处理,其中α是使得1≤r≤di的最大整数r,且时间片[α-1,α]是空的。
- ②仿照例5.4的格式,在习题8①所提供的数据集上执行算法5.5。
第14页:可行解规则的充分性
- 如果J中的作业能按上述规则处理,则每一个作业都可在它的期限之前获得一个空的时间片,所以J是可行解。
- 如果J是可行解,存在一种排列σ’=i1i2…ik,作业都可在其期限前完成。
- J中作业按效益值非递增的顺序排列为s1s2…sk,采用数学归纳法
- 考虑作业s1,根据命题中的规则,它放在期限允许的最大位置ds1,若其在σ’中也处于该位置,则考虑下一个作业s2;否则,s1在σ’中的位置必然小于ds1,可将σ’中处于ds1位置的作业与s1交换,不影响其可行性。
- 假设s1s2…sa都已经按照命题中规则安排好,并且与σ’中相应的作业处于相同的位置。现在考虑sa+1,按照规则它应该放在dsa+1或其前面的一个最大的空位置上,设其位置为α,若其在σ’中的位置不是α,设其为β(β<α),在σ’中将iα和iβ互换,且交换后仍可行,iα一定不是s1s2…sa中的任何一个。这样一直进行下去一直到sk,则σ’中的作业按照命题中
第15页:可行解规则的必要性
- n=7(p1,…,p7)=(3,5,20,18,1,6,30)(d1,…,d7)=(1,3, 4, 3, 2,1, 2)
- (p7, p3, p4, p6, p2, p1, p5)=(30,20,18,6,5,3,1),对应的期限为(2, 4, 3,1,3,1,2)
- b = min{ n,max{d(i)} }= min{7,4 }=4
第16页:P123-9的实例数据
F(4)F(3)F(2)F(1)F(0)43210-10-11-12-13-14F(4)F(3)F(2)F(1)F(0)43110-10-2112-13-14空{7}F(4)F(3)F(2)F(1)F(0)33110{7,3}-10-2112-2334(p7, p3, p4, p6, p2, p1, p5)=(30,20,18,6,5,3,1)对应的期限为(2,4,3,1,3,1,2)J考虑作业无73
第17页:时间片分配过程之一
(p7, p3, p4, p6, p2, p1, p5)=(30,20,18,6,5,3,1)对应的期限为(2,4,3,1,3,1,2)F(4)F(3)F(2)F(1)F(0)31110{7,3,4}-10-41121334F(4)F(3)F(2)F(1)F(0)31100{7,3,4,6}10-51121334J考虑作业64
第18页:时间片分配过程之二
(p7, p3, p4, p6, p2, p1, p5)=(30,20,18,6,5,3,1)对应的期限为(2,4,3,1,3,1,2)F(4)F(3)F(2)F(1)F(0)31100F(4)F(3)F(2)F(1)F(0)31100{7,3,4,6}J考虑作业2(舍弃)10-511213341(舍弃){7,3,4,6}同上F(4)F(3)F(2)F(1)F(0)31100{7,3,4,6}5(舍弃)同上作业的处理顺序为(6,7,4, 3),效益值为74.