数学建模论文-纸质老照片电子化过程中的优化模型.doc

昆明理工大学第十届大学生数学建模竞赛承 诺 书我们仔细阅读了昆明理工大学大学生数学建模竞赛的竞赛规则。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的。如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们的参赛报名序号为： 学院第 队 我们选择的题号是（A题/B题）： B 我们的参赛性质是（学院代表队/个人参赛队）： 个人参赛队 参赛队员 (打印并签名) ：1. 学院 理学院 专业年级 2013级信计专业 姓名 何 力 签名 2. 学院 理学院 专业年级 2013级信计专业 姓名 赵小丽 签名 3. 学院 理学院 专业年级 2013级信计专业 姓名 万 文 签名 数学建模联络员 (打印并签名)： 签名 日期： 2015 年 05 月 10 日评阅编号（由组委会评阅前进行编号）：昆明理工大学第十届大学生数学建模竞赛评 阅 专 用 页评阅编号（由组委会评阅前进行编号）：评阅记录（供评阅时使用）：评阅人评分备注总分全国评阅编号（由全国组委会评阅前进行编号）：纸质老照片电子化过程中的优化模型摘要本文主要讨论的是针对不同尺寸大小的纸质老照片通过扫描仪扫描生成图像文件，然后通过图像处理软件对图像文件中的照片进行处理获得电子版的照片，对此过程中的处理流程进行优化设计，在满足相关约束条件下以获得最优的处理流程，基于对此的研究，建立数学模型设计出最佳的处理流程，使得总用时最少。问题1、是对照片长度完全一致的情况下，对给定的不同宽度照片按照在分辨率给定的情况下，首先通过附件1给出的照片数据确定选用扫描的幅面，多次扫描n张照片的具体过程进行分析，分别以照片张数、总的扫描次数、在600dpi分辨率下每种幅面扫描次数，设出未知量，在给定的约束条件下，建立了一个关于时间总长的数学模型，给出表达式，通过MATLAB软件数值求解，找到10张照片在采用600dpi分辨率进行电子化过程的最优解。最后通过01动态规划模型编写程序求解符合最短时间内每次扫描的照片分配。问题2、是对照片长度完全一致的情况下，对给定三种不同宽度照片按照在分辨率给定的情况下，多张照片情况下对一定数量规格的照片进行优化。通过建立线性规划模型，利用LINGO软件解出最少扫描次数及每次扫描平面中所放的照片尺寸。通过MATLAB软件数值求解，找到50张照片在采用300dpi分辨率进行电子化过程的最优解。在算法上主要对模型分析得到数学表达式，运用MATLAB、LINGO等编程软件求解得出最优结果，对数据的分析和模型的建立能够直观和清晰的得出照片电子化过程的最优方法，而且对其做出了评价和方法改进，能够更好的看出结果。关键词：优化设计 多次扫描 数值求解 0-1动态规划模型 线性规划模型一、 问题重述今有一批纸质矩形珍贵老照片拟采用如下流程进行电子化：首先通过扫描仪进行扫描以生成图像文件，然后通过图像处理软件将扫描得到的图像文件中的照片处理成符合要求的图像。现有一台平面扫描仪，该扫描仪的扫描幅面大小见表一。表一 扫描仪的扫描幅面大小幅面类型长（单位：cm）宽 (单位：cm)A429.721LTR27.9421.59B525.718.2使用扫描仪进行一次扫描的标准流程如下：选择扫描幅面和分辨率，打开扫描仪的盖板，把准备扫描的照片（通常是若干张，也可以是一张）放在扫描仪玻璃板的相应区域，盖上盖板；按扫描仪的开始扫描按钮，等待扫描完成；完成后打开盖板，取出玻璃板上的照片，盖上盖板。扫描仪进行一次扫描流程所用时间见表二。表二 扫描仪进行一次扫描流程时间操作时间（单位：s）选择扫描幅面2选择分辨率2打开扫描仪盖板1盖上扫描仪盖板1放照片（一张）2取出照片2在图像处理软件中设定复制尺寸通常需要2秒，选择复制区域通常需要1秒，将选中的区域复制到新文件中需要1秒，顺时针旋转任意图像文件90度、180度、270度均需要2秒，存储选定的区域需要1秒。如果下一次要设定的复制区域的尺寸与上一次设定的复制区域的尺寸一致，则可以省略设定复制区域尺寸的时间。现有平面扫描仪和电脑(装有图像处理软件)各一台，操作人员一名（可熟练使用该扫描仪和电脑中的图像处理软件），已知该扫描仪的最大扫描幅面为A4（长29.7厘米，宽21厘米），也可以扫描LTR幅面（长27.94厘米，宽21.59厘米）和B5幅面（长25.7厘米，宽18.2厘米）；该扫描仪扫描时可选的图像分辨率为150dpi、300dpi和600dpi三种,表三给出扫描幅面和分辨率的关系，现要求为其安排流程使其尽早完成电子化。表三 扫描幅面和分辨率的关系分时 辨幅 长 率面150dpi300dpi600dpiA44578120LTR406798B53446661、现有10张长度完全一致的照片（相关数据见附件1）按照给定流程进行电子化成分辨率均为600dpi的图像，如何安排整个流程以使得这10张照片尽早完成电子化？ 2、现有50张长度完全一致的照片（相关数据见附件2）按照给定上述流程进行电子化成分辨率均为300dpi的图像，如何安排整个流程以使得这50张照片尽早完成电子化？2、 问题分析根据给定的附件1、2来看，照片的长度都是一样的，因此我们只需要考虑的是不同宽度照片尺寸需要满足的条件，我们根据题目给出的流程分析，在满足不同幅面尺寸要求下。针对问题1，附件1中照片长度均为28cm，只能采用A4幅面，才能将附件1中照片扫描完整。因此在A4幅面下，扫描的总时长只和扫描次数有关，扫描次数由所给的照片宽度及扫描幅面的宽度决定。容易知道在数量较少的问题中用枚举法可以找出用时最短的方案，但在数量多的时候计算量太太，不易找出，因此我们采用动态规划法解决这个问题，分析了10张照片的摆放只有4种情况，即最大照片数P=1，2，3，4，并且从照片摆放的最多张数分别讨论了P=1，2，3，4种情况下照片电子化过程用时情况，得出在最大张数为3和4的情况下用时最少，从时间变化上建立数学模型，通过此模型计算出了在不同情况下电子化过程用时最少的方法，并得出最少时间和所对应的组合。对于问题2，附件2给出50张长度一样，但宽度不一样的照片，并且给出宽度为5cm、8cm、11cm的照片各20、20、10张，考虑到照片长度都是26cm，因此可以选择A4幅面和LTR幅面对照片进行扫描，并且针对两种扫描方法建立其关于时间的函数，通过比较选择使总用时最少的幅面扫描，因此只需考虑不同照片组合情况下的模型求解，采用LINGO编程求解，通过此模型计算出了在不同情况下电子化过程用时最少的方法。对于哪些照片组合在一起以及组合次数最少是该题的问题，因此如何正确有效的建立在不同宽度下求出组合问题的理论表达式以及总时间的表达式并设计算法求解成为模型建立的关键。三、模型假设1假设扫描仪较大的边长是竖着的，对图片处理时的旋转没有影响；2假设照片摆放时各边均与扫描仪的矩形边缘相平行或垂直；3假设每张照片都是规整的矩形；4. 假设照片质量好坏不影响扫描和图像处理过程的时间.四、符号说明符号说明单位T电子化过程的总时间s扫描过程的总时间s图像处理过程的总时间s第k种扫描幅面的长度cm第k种扫描幅面的宽度cmk采用哪种幅面，k=1,2,3_第r张照片的长度cm 第r张照片的宽度cmrr表示照片的序号,r=110_n1扫描仪长边摆放竖着的照片个数_n2扫描仪长边摆放横着的照片个数_m1扫描仪短边摆放竖着的照片个数_m2扫描仪短边摆放横着的照片个数_每次扫描的照片张数张n照片张数张i表示选用的幅面_j表示选用的分辨率dpi相应的幅面和分辨率的扫描时间sSum扫描的总张数张P扫描组合中扫描照片的最大张数（P=1，2，3，4）_A4幅面对应600dpi下的用时s五、 模型建立和求解5.1 问题一的模型建立及求解5.1.1 问题分析该问题是一个对于长度一定，宽度不同以及扫描用时最短问题的不同组合做出一个合理的设计方案，根据照片组合问题我们分为了5种情况进行讨论：I. 每次扫描一张照片，需要10次扫描；II 每次扫描两张照片，需要5次扫描；III每次扫描三张照片，需要4次扫描；IV 每次扫描四张照片，需要4次扫描；V 每次扫描五张照片，需要2次扫描。但是进一步分析知道，扫描三张照片的组合情况只可以是（3,3,2,2），四张照片的组合情况只有（4,2,2,2），而五张以上不存在组合情况，因此在下面的讨论中，只讨论4种情况。5.1.2 理论分析根据第一问的要求，可知要求的目标函数为时间的最小值，则有=+ (1-1)a. 扫描过程分析：由题目已知，分辨率（dpi）已经确定为600dpi，即DPI=600dpi (1-2)则有约束条件： (1-3) (1-4)用图表示即为：图一即根据表一扫描仪的扫描幅面大小可知：由于附件给出的照片长度都是28cm ,最短的照片宽度为： (1-5) (1-6)即 28+3+1=3229.7由（1-6）式可知，这种组合方式，如图二 图二不满足约束条件（1-3）、（1-4），所以不存在组合。又已知LTR扫描幅面为、，B5扫描幅面为、，因为 (1-7)因此由（1-2）和（1-7）可知，只能选用A4幅面扫描法，并且由（1-6）知，只存在一种摆放照片的方法，且采用的分辨率为600dpi，则有 (1-8)如图三：图三b.扫描时间一次扫描一张照片的时间为: （1-9）一次扫描n张照片的时间为： (1-10)假设m次扫描中，每次都是n张，则：m次扫描n张照片的时间为：如果每次扫描不一定相同的照片张数，则有： (1-11)c.扫描次数假如采用一次一张的方法，则有 -得: 0采用m次 张照片的扫描方法更好由（1-11）可以直观的看出，扫描操作时间为m的一元一次函数，且随m的增加，时间也增加 （1-12）综上可得，要取得最短时间，必须控制扫描的次数最少，由于已确定使用A4幅面扫描，其宽度为，每张照片宽度为（i=1,2,3,10）,照片所占宽度为（+0.5）少于4次不可能把所有照片扫面完，即5.1.3 建立模型及求解运用动态规划方法建立模型，把照片扫描过程划分为多阶段处理，分别建立了在扫描照片最大张数下的数学表达式，然后运用LINGO软件求解。a.通过枚举思想建立模型通过对照片扫描过程的分析，我们将扫描情况划分为5种情况求出电子化过程的总时间T，并且图像处理时间都是50s, =120s:(1) P=1：第一次：4+1+(2+1+1+2)第二次： (2+1+1+2)第十次： (2+1+1+2)+1=5+10（6+）+1+50=1316s(2) P=2:第一次:4+1+(4+1+1+2)第二次： (4+1+1+2)第五次： (4+1+1+2)+1=5+5(8+)+1+50=696s(3)P=3:第一次：4+1+（6+1+1+2）第二次： (6+1+1+2)第三次： (4+1+1+2)第四次： (4+1+1+2)+1=5+2(10+)+2(8+)+1+50=572s(4)P=4:第一次：4+1+(8+1+1+2)第二次： (4+1+1+2)第三次： (4+1+1+2)第四次： (4+1+1+2)+1=5+(12+)+3(8+)+1+50=572s得到用时最少的数学表达式为此题最优化的方法为：当时不存在组合情况，因此只能在情况下考虑，通过结果可知，=572s,因此采用组合(3,3,2,2 )和(4,2,2,2)两种情况下的照片组合能够使用时最少，最快完成电子化过程。在组合（4,2,2,2）下4张照片一起的只有（3,4,5,6）和（3,4,5,7），剩下的6张照片排列组合有=15种，因此共有30种情况。b.动态规划（0-1规划）模型(1)模型的建立对于 n 张照片，长度相同，且已知第 i 张照片的宽度为正数 Wi，价值为正数 Vi（照片的宽度和价值相等），最大容纳下的扫描幅面宽度为正数 W，现要求找出这 n 张照片的一个子集，使得子集中照片的总宽度不超过扫描幅面宽度 W且总价值尽量大。（由上述模型中可知，照片只能正放，故不考虑照片长度的影响）。根据问题描述，可以将其转化为如下的约束条件和目标函数：i=1nWiXi WXi0,1 1in 1Maxi=1nViXi 2 于是，问题就归结为寻找一个满足约束条件（1），并使目标函数式（2）达到最大的解向量。0-1宽度问题可以看作是寻找一个序列，对任一个变量的判断是决定等于1还是等于0，在判断时，会有两种情况：a) 扫描幅面宽度容量不足以放入照片 i，则等于0，价值不增加；b) 扫描幅面宽度容量可以放入照片 i，则等于1，价值增加；这两种情况下总价值的最大者应该是对判断后的价值。令表示在前 i 张照片中能够放入到宽度为 j 的扫描幅面宽度的总价值，则可以得到如下的动态规划函数：C i,0=C 0,j=0 (3)C i,j= C i=1,j , j Wi (4) 式（3）说明：把前面 i 张照片放入扫描幅面宽度为0的扫描幅面和把0张照片放入扫描幅面宽度为 j 的扫描幅面中，得到的价值均为0.式（4）第一个式子说明：如果第 i 张照片的宽度大于扫面幅面的宽度，则放入第 i 张照片得到的最大价值和放入第 i-1张照片得到的最大价值是相同的，即第 i 张照片不能放入扫描幅面中；式（4）第二个式子说明：如果第 i 张照片的宽度小于扫描幅面的宽度，则会有两种情况：1. 如果把第 i 张照片能放入扫面幅面宽度为 j 的扫描幅面中，则扫面幅面的价值等于前i-1张照片放入宽度为 j 的扫描幅面中价值与第i 张照片价值之和。2. 如果第 i 张照片不能放入扫描幅面宽度为 j 的扫描幅面中，则扫面幅面价值就等于把前i-1张照片放入扫面幅面宽度为 j 的扫描幅面中的价值。显然，取二者中价值较大者作为把 i 张照片放入扫面幅面为 j 的扫描幅面中的最优解。(2)模型的求解第一步，只放入一张照片，确定在各种情况下扫描幅面能得到的最大价值；第二步，只两张照片，确定在各种情况下扫描幅面能够得到的最大价值；依次类推，到了第 n 步 就得到所需要的最优解。最后，便是在扫描幅面宽度为W中，放入n 张照片取得的最大价值。为了确定装入背包的具体物品，从价值向前寻找。依此类推，直到确定第一个物品是否被装入背包为止。由此，得到如下的函数：Xi= 0 ， Ci,j=C(i-1,j)1，j=j- Wi Ci,jC(i-1,j)根据动态规划函数，用一个二维数组C存放中间变量，表示把前 i 张照片能放入扫面幅面宽度为 j 的扫描幅面中取得的最大价值(程序见附录1)。 5.2 问题二模型建立及求解5.2.1 问题分析该问题是在第一问的基础上增加照片的数量以及将照片划分为3种长度各20、20、10张相同尺寸的照片，并且要求使用分辨率为300dpi,对于该问的解答我们通过0-1规划问题并且进一步分析知道， 5.2.1.1 理论模型由问题一中的(1-1)式知：=+由题目知道，设分辨率为DPI，已确定为DPI=300dpi，并且照片长度均为26cm,最短的照片宽度为，因此满足 （2-1）即：26+5+1=3229.727.9425.7由（1-2）、（1-3）的约束条件可知：不存在组合，即 图四已知三种扫描幅面的长宽为(k=1,2,3)，(k=1,2,3)因为 , (2-2)所以只能选用A4幅面扫描法和LTR幅面扫描法, 且由（2-1）可知，只存在一种摆放照片的方法，即图五5.2.1.2 扫描时间已知扫描时间为( i 为幅面，j为分辨率)，则A4幅面扫描法与LTR幅面扫描法的扫描时间分别为A4: LTR: 由第一问中对（1-11）式的证明可知，采用m次扫描张的方法为最优解，且扫描次数越少，所用时间越短。由（1-8）和两种扫描方法的宽度、=21cm，=21.59cm可知：A4每次所放张数与LTR每次所放张数的关系为：所以A4幅面扫描方法的扫描次数与LTR的扫描次数的关系为：且A4的扫描时间与LTR的扫描时间的关系为：A4的扫描过程总时间为： （2-3）LTR的扫描过程总时间为： （2-4）两式相减为：（2-5）所以即针对第二问来说，所有照片扫描均使用LTR扫描方法为最优解。5.2.2 模型建立及求解接下来讨论用LTR扫描方法扫描50张照片的最少次数：设扫描次数为M，则目标函数为min (M)，已知共有3种尺寸的照片，摆放方法已定，在宽度=21.59cm的限制条件下，扫描方法如下表所示：表四 扫描方法d=5cm照片数d=8cm照片数d=11cm照片数方法1100方法2110方法3101方法4200方法5210方法6300方法7010方法8011方法9020方法10001决策变量：用表示按照第i种模式（i=1,2,10）分配的照片数量，显然它们应当是非负整数.决策目标：所建立模型的目标为扫描的次数最少，即： min (M)= （2-6）约束条件：d=5cm照片数不少于20张，d=8cm照片数不少于20张，d=11cm照片数不少于10张, （2-7)模型求解：将（2-6）、（2-7)构成的整数线性规划模型（加上整数约束），输入LINGO求解，可以得到最优解如下：(附录2)，（其余变量为0），即按照方法5和方法8来扫描照片是扫描次数最少的方法.即：方法5：扫描2张d=5cm的照片+扫描1张d=8cm的照片共10次方法8：扫描1张d=8cm的照片+扫描1张d=11cm的照片共10次总共是20次，在图像处理过程中，采用方法5和方法8的方式设定的复制区域的尺寸只作了一次更改，即设置了两次，假如最少设置一次，则只有每次均扫描三种尺寸的照片，即：(5+0.5+8+0.5+11+0.5)=25.5cm21.59cm，此种方法是不可行的，所以上述得出的方法即为扫描过程min和图像处理过程min的最优解.并且有 经过计算得出 所以将整个流程安排完成需要1756秒。此题最优化的方法为：同时扫描2张宽为5cm的照片和1张宽为8cm的照片共10次，同时扫描1张宽为8cm和1张宽为11cm的照片共10次，即得到最短的时间1756s.六、 模型的结果分析本文针对照片摆放的问题，采用0-1动态规划方法和理论证明建立数学模型，列出目标函数，对电子化过程用时最少建立理论数学模型，并且通过编程得出理论结果，和实际推导结果一致，并且得出10张照片扫描用时为572s以及50张照片用时为1756s，符合实际情况。七、 模型优缺点分析（1）优点：1、 本文采用理论模型证明与0-1动态规划方法这两种思想来建立模型，这两种模型在一定条件下可以相互转化；2、 在照片电子化过程用时最少的计算时，忽略复杂计算，不考虑旋转问题；3、 基于0-1规划和理论思考，用MATLAB和LINGO编程，通过求解该模型，更能准确得出结果，在一定程度上由于理论讨论。（2）不足所采用的理论思想和模型有一定的局限性，并且假设了照片摆放位置以及处理照片时候的旋转，在现实中并不是理想的，在计算总时间的时候有一定的主观性，不能够解决实际中所遇到的问题。八、 参考文献1 姜启源，谢金星，邢文训，张立平编著.大学数学实验（第二版）M.北京：清华大学出版社，2012.022 姜启源，谢金星,叶俊编著.数学模型（第四版）M.北京：宫灯教育出版社，2015.013 许兆美.价值与重量相等的0/1背包问题的一种解法，成组技术与现代化，2009.03期4 林鑫，基于0/1背包问题的讨论，研究与设计，2007年第23卷第4期：5 霍红卫，许进，保静.基于遗传算法的0/1背包问题求解，西安电子科技大学学报，1999年04期：6 刘明波,陈学军,程劲晖.三种无功优化线性规划建模方法的比较J.电力系统及其自动化学报.1999(02)7 余雪雷.线性规划问题的一种改进算法D.吉林大学,20068 张鲁辉,陈爱社.动态规划在钢材采购中的研究与应用J.河南建材.2008(03)9 HMGovernment .PlanningandCompulsoryPurchaseAct2004.九、附录附录1#includedouble c;/扫描幅面的宽度int n;/照片的张数int x100; /是否选取照片，为0或1double weight100;double price100;double bp;/最大价值double bA100;/最优解int times=0;/节点访问次数double currentWeight=0; /当前总宽度double currentPrice=0;/当前总价值void print();/输出每条有效路径及最大价值void Backtrack(int i)times+=1;if(in)print();if(currentPricebp)bp=currentPrice;for(int j=1;j=n;j+)bAj=xj;return;if(currentWeight+weighti=c)/将照片i放入扫描幅面，搜索左子树xi=1;current