2、i=1,2,…,m)。m种零件的需求量分别为n1,n2,…,nm。下料时，零件的边必须分别和原材料的边平行。这类问题在工程上通常简称为二维下料问题。特别当所有零件的宽度均与原材料相等，即，则问题称为一维下料问题。特别当所有零件的宽度均与原材料相等，即wi=W.(i=1,2,…,m)，则问题称为一维下料问题。一个好的下料方案首先应该使原材料的利用率最大，从而减少损失，降低成本，提高经济效益。其次要求所采用的不同的下料方式尽可能少，即希望用最少的下料方式来完成任务。因为在生产中转换下料方式需要费用和时间，既提高成本，又降低效率。此外，每种零件有
3、各自的交货时间，每天下料的数量受到企业生产能力的限制。因此实用下料问题的目标是在生产能力容许的条件下，以最少数量的原材料，尽可能按时完成需求任务,同时下料方式数也尽量地小.请你们为某企业考虑下面两个问题。问题：1.建立一维单一原材料实用下料问题的数学模型,并用此模型求解下列问题，制定出在生产能力容许的条件下满足需求的下料方案,同时求出等额完成任务所需的原材料数，所采用的下料方式数和废料总长度.单一原材料的长度为3000mm,需要完成一项有53种不同长度零件的下料任务.具体数据见表一，其中li为需求零件的长度，ni为需求零件的数量.此外，在每
4、个切割点处由于锯缝所产生的损耗为5mm.据估计，该企业每天最大下料能力是100块，要求在4天内完成的零件标号(i)为:5,7,9,12,15,18,20,25,28,36,48;要求不迟于6天完成的零件标号(i)为:4,11,24,29,32,38,40,46,50.(提示：可分层建模。(1).先考虑用材料既少,下料方式又少的模型,或先仅考虑所用材料最少的模型及增加一种下料方式大致相当于使原材料总损耗增加0.08%情况下的最佳方案。(2).在解决具体问题时,先制定4天的下料方案,再制定6天的下料方案,最后制定53种零件的下料方案.这一提示对
5、第2题也部分适用.)2.建立二维单一原材料实用下料问题的数学模型,并用此模型求解下列问题.制定出在企业生产能力容许的条件下满足需求的下料方案,同时求出等额完成任务所需的原材料块数和所需下料方式数.这个问题的单一原材料的长度为3000mm,宽度为100mm,需要完成一项有43种不同长度和宽度零件的下料任务.具体数据见表二，其中li,wi,ni分别为需求零件的长度、宽度和数量.切割时的锯缝可以是直的也可以是弯的，切割所引起的锯缝损耗忽略不计.据估计，该企业每天最大下料能力是20块要求在4天内完成的零件标号(i)为:3,7,9,12,15,18,
6、20,25,28,36.1、下料问题(cuttingstockproblem)”是把相同形状的一些原材料分割加工成若干个不同规格大小的零件的问题；2、二维下料问题----下料时，零件的边必须分别和原材料的边平行;3、一维下料问题----所有零件的宽度均与原材料相等。词汇:本题是有交货时间限制的大规模单一原材料下料问题。1、目标是既要所用材料最少，也要下料方式少。2、有交货时间限制分析:假设（1）每天下料的数量受到企业生产能力的限制，在未完成需求任务前，每天下料的数量等于最大下料能力。（2）每个切割点处由于锯缝所产生的损耗不可忽略。（3）增加
7、一种下料方式大致相当于使原材料总损耗增加0.08%。（4）每种零件有各自的交货时间，若某零件无交货时间，则记该零件交货时间为无穷大。一维下料问题变量定义（符号）零件种类总数第i种下料方式下料的根数下料方式的种类数第i种下料方式每根的余料模型的建立然后代入，推得该线光源的范围为[－0.03,0.03]m。模型的求解对于该问题，因为可能的下料方式将随需要的零件种类数量成指数级增长，所以它是一个NP－Hard问题。这样对于大多数问题，一般方法无法得到最优结果或无法及时得到最优结果。因此对于大规模的一维下料问题，我们给出了结合动态规划和贪婪算法的新
8、算法，称之为DP贪婪算法。基本思想是：对模型计算时，不用先得到一定数量的下料方案，而是在选取下料方案时就以数学模型中的目标和约束条件为基础来进行寻找。为了保证尽量节省材料，应该尽
