习题3.1 证明②小问如下: 问题的解用解向量表示(见题目说明) 设按照该贪心策略选择的解为X={x,x2,…,xn},选中的文件集合即为Q,这些文 件按照长度从小到大存放到磁带上,记其排列为8=i1i2…is,k为Q选中的文件数 设该问题的一个最优解为Y={y1,y2,…,yn},选中的文件集合即为W。现证明Q的 文件个数不少于W(注意,对选中的文件个数进行证明是本题证明的关键,不是证选中了 具体哪个文件) 由于∑a≤L,所以Y集合里被选中的文件可以全部放进磁带,而且与其放的先后次 序无关(这也是问题的关键,只要顺序存放,长度总和都是一样的)。故将W中文件按照长 度从小到大排个序,得到一个按照文件长度从小到大的一个排列 r1r2…rn,m为W选 中的文件数,该排列可以放到磁带上。 1)如果8=8’,则X=Y,即X和Y选中同样的文件,Q是问题选中的最大子集。得 2)如果8≠δ’,则记j是i≠r的最小下标。根据i的选择方式(按文件长度从小 到大选择),a<=a-,否则在Q中一定是先选r;这个作业,而不是选i ●如果i∈W,则其长度a;=a-,此时,设ra=ij,则在δ中调换ra与r;,可以消去 位置的不同点 ●否则,i不在W中,由于其长度有a<=an,所以在δ中去掉r,而选择i,得到 个新文件集合W’,这个集合同样满足长度的限制,而且文件个数不会少于W。总之也可以 消去j位置的不同点。 经过以上调整,最终将W变得和Q一样,其文件个数不少于问题的最优解W,问题得 ,Q是问题选中的最大子集。 当今,“优化”无疑是一个热门词。做宏观经济规划要优化资源配置,搞企业经 营管理要优化生产计划,作新产品设计要优化性能成本比。就是在人们的日常生 活中,优化的要求也比比皆是,消费时,如何花尽可能少的钱办尽可能多的事, 出行时,如何走最短的路程到达目的地,等等。总而言之,在经济如此发展,竞 争如此剧烈,资源日渐紧张的今天,人们做任何事,无不望求事半功倍之术 求或提效、或增收、或节约等等之目标。所有类似的这种课题统称为最优化问题, 研究解决这些问题的科学一般就总称之为最优化理论和方法,另外也可用学术味 更浓的名称:“运筹学”。由于最优化问题背景十分广泛,涉及的知识不尽相同, 学科分枝很多,因此这个学科名下到底包含哪些分枝,其说法也不一致。比较公 认的是:“规划论”(包括线性和非线性规划、整数规划、动态规划、多目标规 划和随机规划等),“组合最优化”,“对策论”及“最优控制”等等。 从数学上比较一般的观点来看,所谓最优化问题可以概括为这样一种数学模 型:给定一个“函数”,F(X),以及“自变量”X应满足的一定条件,求X为怎
习题 3.1 证明②小问如下： 问题的解用解向量表示（见题目说明） 设按照该贪心策略选择的解为 X＝{x1，x2，…，xn}，选中的文件集合即为 Q，这些文 件按照长度从小到大存放到磁带上，记其排列为 δ＝i1i2…ik，k 为 Q 选中的文件数 设该问题的一个最优解为 Y＝{y1，y2，…，yn}，选中的文件集合即为 W。现证明 Q 的 文件个数不少于 W（注意，对选中的文件个数进行证明是本题证明的关键，不是证选中了 具体哪个文件）。 由于 Pi W ai L ，所以 Y 集合里被选中的文件可以全部放进磁带，而且与其放的先后次 序无关（这也是问题的关键，只要顺序存放，长度总和都是一样的）。故将 W 中文件按照长 度从小到大排个序，得到一个按照文件长度从小到大的一个排列 δ’ ＝r1r2…rm，m 为 W 选 中的文件数，该排列可以放到磁带上。 1）如果 δ＝δ’，则 X＝Y，即 X 和 Y 选中同样的文件，Q 是问题选中的最大子集。得 证。 2）如果 δ≠δ’，则记 j 是 ij≠rj 的最小下标。根据 ij 的选择方式（按文件长度从小 到大选择），aij<=arj，否则在 Q 中一定是先选 rj 这个作业，而不是选 ij。 ● 如果 ij∈W，则其长度 aij=arj，此时，设 rd=ij，则在 δ’中调换 rd 与 rj，可以消去 j 位置的不同点 ● 否则，ij 不在 W 中，由于其长度有 aij<=arj，所以在 δ’中去掉 rj，而选择 ij，得到一 个新文件集合 W’，这个集合同样满足长度的限制，而且文件个数不会少于 W。总之也可以 消去 j 位置的不同点。 经过以上调整，最终将 W 变得和 Q 一样，其文件个数不少于问题的最优解 W，问题得 证。 ，Q 是问题选中的最大子集。 当今，“优化”无疑是一个热门词。做宏观经济规划要优化资源配置，搞企业经 营管理要优化生产计划，作新产品设计要优化性能成本比。就是在人们的日常生 活中，优化的要求也比比皆是，消费时，如何花尽可能少的钱办尽可能多的事， 出行时，如何走最短的路程到达目的地，等等。总而言之，在经济如此发展，竞 争如此剧烈，资源日渐紧张的今天，人们做任何事，无不望求事半功倍之术，以 求或提效、或增收、或节约等等之目标。所有类似的这种课题统称为最优化问题， 研究解决这些问题的科学一般就总称之为最优化理论和方法，另外也可用学术味 更浓的名称：“运筹学”。由于最优化问题背景十分广泛，涉及的知识不尽相同， 学科分枝很多，因此这个学科名下到底包含哪些分枝，其说法也不一致。比较公 认的是：“规划论”（包括线性和非线性规划、整数规划、动态规划、多目标规 划和随机规划等），“组合最优化”，“对策论”及“最优控制”等等。 从数学上比较一般的观点来看，所谓最优化问题可以概括为这样一种数学模 型：给定一个“函数”，F(X)，以及“自变量”X 应满足的一定条件，求 X 为怎
样的值时,F(X)取得其最大值或最小值。这里在函数和自变量两个词上之所以打 上引号,是想强调它们的含意比中学数学和大学微积分中函数的定义要广泛得 多。通常,称F(X)为“目标函数”,X应满足的条件为“约束条件”。约束条件 般用一个集合D表示为:X∈D。求目标函数F(X)在约束条件X∈D下的最小值 或最大值问题,就是一般最优问题的数学模型,它还可以利用数学符号更简洁地 表示成:MinF(X)或MaxF(X)。 解决最优化问题的关键步骤是,如何把实际问题抽象成上述数学模型,也就 是构造出目标函数与约束条件。一但这一步完成,对于简单问题,可借图形或微 积分来求解。遇到比较复杂的课题,可先搞清它属于运筹学哪一分枝,并在此基 础上尽量利用现有的数学软件或最优化软件,比如 Matlab, Mathematica, Lindo, Lingo等,来计算。下面举一个简单例子来具体说明这个关键步骤
样的值时，F(X)取得其最大值或最小值。这里在函数和自变量两个词上之所以打 上引号，是想强调它们的含意比中学数学和大学微积分中函数的定义要广泛得 多。通常，称 F(X)为“目标函数”，X 应满足的条件为“约束条件”。约束条件 一般用一个集合 D 表示为：X∈D。求目标函数 F(X)在约束条件 X∈D 下的最小值 或最大值问题，就是一般最优问题的数学模型，它还可以利用数学符号更简洁地 表示成：Min F(X)或 Max F(X)。 解决最优化问题的关键步骤是，如何把实际问题抽象成上述数学模型，也就 是构造出目标函数与约束条件。一但这一步完成，对于简单问题，可借图形或微 积分来求解。遇到比较复杂的课题，可先搞清它属于运筹学哪一分枝，并在此基 础上尽量利用现有的数学软件或最优化软件，比如 Matlab，Mathematica， Lindo， Lingo 等，来计算。下面举一个简单例子来具体说明这个关键步骤