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

纸质老照片电子化过程中的优化模型摘要本文主要讨论的是针对不同尺寸大小的纸质老照片通过扫描仪扫描生成图像文件，然后通过图像处理软件对图像文件中的照片进行处理获得电子版的照片，对此过程中的处理流程进行优化设计，在满足相关约束条件下以获得最优的处理流程，基于对此的研究，建立数学模型设计出最佳的处理流程，使得总用时最少。问题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张照片尽早完成电子化？二、 问题分析根据给定的附件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)模型的建立对于 张照片，长度相同，且已知第张照片的宽度为正数 ，价值为正数（照片的宽度和价值相等），最大容纳下的扫描幅面宽度为正数，现要求找出这 张照片的一个子集，使得子集中照片的总宽度不超过扫描幅面宽度且总价值尽量大。（由上述模型中可知，照片只能正放，故不考虑照片长度的影响）。根据问题描述，可以将其转化为如下的约束条件和目标函数： 于是，问题就归结为寻找一个满足约束条件（1），并使目标函数式（2）达到最大的解向量。0-1宽度问题可以看作是寻找一个序列，对任一个变量的判断是决定等于1还是等于0，在判断时，会有两种情况：a) 扫描幅面宽度容量不足以放入照片，则等于0，价值不增加；b) 扫描幅面宽度容量可以放入照片，则等于1，价值增加；这两种情况下总价值的最大者应该是对判断后的价值。令表示在前张照片中能够放入到宽度为的扫描幅面宽度的总价值，则可以得到如下的动态规划函数：式（3）说明：把前面张照片放入扫描幅面宽度为0的扫描幅面和把0张照片放入扫描幅面宽度为 的扫描幅面中，得到的价值均为0.式（4）第一个式子说明：如果第 张照片的宽度大于扫面幅面的宽度，则放入第 张照片得到的最大价值和放入第张照片得到的最大价值是相同的，即第 张照片不能放入扫描幅面中；式（4）第二个式子说明：如果第张照片的宽度小于扫描幅面的宽度，则会有两种情况：1. 如果把第张照片能放入扫面幅面宽度为 的扫描幅面中，则扫面幅面的价值等于前张照片放入宽度为 的扫描幅面中价值与第张照片价值之和。2. 如果第张照片不能放入扫描幅面宽度为 的扫描幅面中，则扫面幅面价值就等于把前张照片放入扫面幅面宽度为 的扫描幅面中的价值。显然，取二者中价值较大者作为把张照片放入扫面幅面为 的扫描幅面中的最优解。(2)模型的求解第一步，只放入一张照片，确定在各种情况下扫描幅面能得到的最大价值；第二步，只两张照片，确定在各种情况下扫描幅面能够得到的最大价值；依次类推，到了第步 就得到所需要的最优解。最后，便是在扫描幅面宽度为中，放入 张照片取得的最大价值。为了确定装入背包的具体物品，从价值向前寻找。依此类推，直到确定第一个物品是否被装入背包为止。由此，得到如下的函数：根据动态规划函数，用一个二维数组存放中间变量，表示把前张照片能放入扫面幅面宽度为 的扫描幅面中取得的最大价值(程序见附录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;currentWeight+=weighti;currentPrice+=pricei;Backtrack(i+1);/完成上面的递归，返回上一节点，搜索右子树，及不选照片icurrentWeight-=weighti;currentPrice-=pricei;xi=0;Backtrack(i+1);void print()int i;printf(路径为：);for(i=1;in;i+)printf(%d,xi);printf(%d 价值为 %lfn,xi,currentPrice);int main()int i;printf(请输入照片数量：);scanf(%d,&n);printf(请输入扫描幅面宽度：);scanf(%lf,&c);printf(请输入照片的宽度：);for(i=1;i=n;i+)scanf(%lf,&weighti);printf(请输入照片的价值：);for(i=1;i=n;i+)scanf(%lf,&pricei);Backtrack(1);printf(最优解是：);for(i=1;i20;x1+x5+x7+x8+2*x920;x3+x8+x1010;结果：Global optimal solution found. Objective value: 20.00000 Infeasibilities: 0.000000 Total solver iterations: 3 Variable Value Reduced Cost X1 0.000000 0.2500000 X2 0.000000 0.7500000 X3 0.000000 0.2500000 X4 0.000000 0.5000000 X5 10.00000 0.000000 X6 0.000000 0.2500000 X7 0.000000 0.5000000 X8 10.00000 0.000000 X9 0.000000 0.000000 X10 0.000000 0.5000000 Row Slack or Surplus Dual Price 1 20.00000 -1.000000 2 0.000000 -0.2500000 3 0.000000 -0.5000000 4 0.000000 -0.5000000毕业设计（论文）原创性声明和使用授权说明原创性声明本人郑重承诺：所呈交的毕业设计（论文），是我个人在指导教师的指导下进行的研究工作及取得的成果。尽我所知，除文中特别加以标注和致谢的地方外，不包含其他人或组织已经发表或公布过的研究成果，也不包含我为获得 及其它教育机构的学位或学历而使用过的材料。对本研究提供过帮助和做出过贡献的个人或集体，均已在文中作了明确的说明并表示了谢意。作 者 签 名： 日 期： 指导教师签名： 日期： 使用授权说明本人完全了解 大学关于收集、保存、使用毕业设计（论文）的规定，即：按照学校要求提交毕业设计（论文）的印刷本和电子版本；学校有权保存毕业设计（论文）的印刷本和电子版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它复制手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部分或全部内容。作者签名： 日 期： 学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名： 日期： 年 月 日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权 大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。涉密论文按学校规定处理。作者签名：日期： 年 月 日导师签名： 日期： 年 月 日注 意 事 项1.设计（论文）的内容包括：1）封面（按教务处制定的标准封面格式制作）2）原创性声明3）中文摘要（300字左右）、关键词4）外文摘要、关键词 5）目次页（附件不统一编入）6）论文主体部分：引言（或绪论）、正文、结论7）参考文献8）致谢9）附录（对论文支持必要时）2.论文字数要求：理工类设计（论文）正文字数不少于1万字（不包括图纸、程序清单等），文科类论文正文字数不少于1.2万字。3.附件包括：任务书、开题报告、外文译文、译文原文（复印件）。4.文字、图表要求：1）文字通顺，语言流畅，书写字迹工整，打印字体及大小符合要求，无错别字，不准请他人代写2）工程设计类题目的图纸，要求部分用尺规绘制，部分用计算机绘制，所有图纸应符合国家技术标准规范。图表整洁，布局合理，文字注释必须使用工程字书写，不准用徒手画3）毕业论文须用A4单面打印，论文50页以上的双面打印4）图表应绘制于无格子的页面上5）软件工程类课题应有程序清单，并提供电子文档5.装订顺序1）设计（论文）2）附件：按照任务书、开题报告、外文译文、译文原文（复印件）次序装订25