2015昆明理工大學數學建模B題論文

1、2015昆明理工大學數學建模B題論文 昆明理工大學第十屆大學生數學建模競賽 承 諾 書 我們仔細閱讀了昆明理工大學大學生數學建模競賽的競賽規(guī)則。 我們完全明白，在競賽開始后參賽隊員不能以任何方式（包括 、電子郵件、網上咨詢等）與隊外的任何人研究、討論與賽題有關的問題。 我們知道，抄襲別人的成果是違反競賽規(guī)則的。如果引用別人的成果或其他公開的資料（包括網上查到的資料），必須按照規(guī)定的參考文獻的表述方式在正文引用處和參考文獻中明確列出。 我們鄭重承諾，嚴格遵守競賽規(guī)則，以保證競賽的公正、公平性。如有違反競賽規(guī)則的行為，我們將受到嚴肅處理。 我們的參賽報名序號為： 我們選擇的題號是（A題/B題）：

2、B 我們的參賽性質是（學院代表隊/個人參賽隊）： 個人參賽隊 參賽隊員 (打印并簽名) ： 1. 學院姓名 簽名 2. 學院姓名 簽名 3. 學院姓名 簽名 數學建模聯絡員 (打印并簽名)： 簽名 日期： 2015 年 05 月 10 日 評閱編號（由組委會評閱前進行編號）： 昆明理工大學第十屆大學生數學建模競賽 評 閱 專 用 頁 評閱編號（由組委會評閱前進行編號）： 全國評閱編號（由全國組委會評閱前進行編號）： 紙質老照片電子化過程中的優(yōu)化模型 摘要 本文主要討論的是針對不同尺寸大小的紙質老照片通過掃描儀掃描生成圖像文件，然后通過圖像處理軟件對圖像文件中的照片進行處理獲得電子版的照片，對此

3、過程中的處理流程進行優(yōu)化設計，在滿足相關約束條件下以獲得最優(yōu)的處理流程，基于對此的研究，建立數學模型設計出最佳的處理流程，使得總用時最少。 問題1、是對照片長度完全一致的情況下，對給定的不同寬度照片按照在分辨率給定的情況下，首先通過附件1給出的照片數據確定選用掃描的幅面，多次掃描n張照片的具體過程進行分析，分別以照片張數、總的掃描次數、在600dpi分辨率下每種幅面掃描次數，設出未知量，在給定的約束條件下，建立了一個關于時間總長的數學模型，給出表達式，通過MATLAB軟件數值求解，找到10張照片在采用600dpi分辨率進行電子化過程的最優(yōu)解。最后通過01動態(tài)規(guī)劃模型編寫程序求解符合最短時間內每

4、次掃描的照片分配。 問題2、是對照片長度完全一致的情況下，對給定三種不同寬度照片按照在分辨率給定的情況下，多張照片情況下對一定數量規(guī)格的照片進行優(yōu)化。通過建立線性規(guī)劃模型，利用LINGO軟件解出最少掃描次數及每次掃描平面中所放的照片尺寸。通過MATLAB軟件數值求解，找到50張照片在采用300dpi分辨率進行電子化過程的最優(yōu)解。 在算法上主要對模型分析得到數學表達式，運用MATLAB、LINGO等編程軟件求解得出最優(yōu)結果，對數據的分析和模型的建立能夠直觀和清晰的得出照片電子化過程的最優(yōu)方法，而且對其做出了評價和方法改進，能夠更好的看出結果。 關鍵詞：優(yōu)化設計 多次掃描 數值求解 0-1動態(tài)規(guī)劃

5、模型 線性規(guī)劃模型 1 一、 問題重述 今有一批紙質矩形珍貴老照片擬采用如下流程進行電子化：首先通過掃描儀進行掃描以生成圖像文件，然后通過圖像處理軟件將掃描得到的圖像文件中的照片處理成符合要求的圖像。現有一臺平面掃描儀，該掃描儀的掃描幅面大小見表一。 使用掃描儀進行一次掃描的標準流程如下：選擇掃描幅面和分辨率，打開掃描儀的蓋板，把準備掃描的照片（通常是若干張，也可以是一張）放在掃描儀玻璃板的相應區(qū)域，蓋上蓋板；按掃描儀的開始掃描按鈕，等待掃描完成；完成后打開蓋板，取出玻璃板上的照片，蓋上蓋板。掃描儀進行一次掃描流程所用時間見表二。 在圖像處理軟件中設定復制尺寸通常需要2秒，選擇復制區(qū)域通常需要

6、1秒，將選中的區(qū)域復制到新文件中需要1秒，順時針旋轉任意圖像文件90度、180度、270度均需要2秒，存儲選定的區(qū)域需要1秒。如果下一次要設定的復制區(qū)域的尺寸與上一次設定的復制區(qū)域的尺寸一致，則可以省略設定復制區(qū)域尺寸的時間。 現有平面掃描儀和電腦(裝有圖像處理軟件)各一臺，操作人員一名（可熟練使用該 2 掃描儀和電腦中的圖像處理軟件），已知該掃描儀的最大掃描幅面為A4（長厘米，寬21厘米），也可以掃描LTR幅面（長厘米，寬厘米）和B5幅面（長厘米，寬厘米）；該掃描儀掃描時可選的圖像分辨率為150dpi、300dpi和600dpi三種,表三給出掃描幅面和分辨率的關系，現要求為其安排流程使其盡早

7、完成電子化。 1、現有10張長度完全一致的照片（相關數據見附件1）按照給定流程進行電子化成分辨率均為600dpi的圖像，如何安排整個流程以使得這10張照片盡早完成電子化？ 2、現有50張長度完全一致的照片（相關數據見附件2）按照給定上述流程進行電子化成分辨率均為300dpi的圖像，如何安排整個流程以使得這50張照片盡早完成電子化？ 二、問題分析 根據給定的附件1、2來看，照片的長度都是一樣的，因此我們只需要考慮的是不同寬度照片尺寸需要滿足的條件，我們根據題目給出的流程分析，在滿足不同幅面尺寸要求下。 針對問題1，附件1中照片長度均為28cm，只能采用A4幅面，才能將附件1中照片掃描完整。因此在

8、A4幅面下，掃描的總時長只和掃描次數有關，掃描次數由所給的照片寬度及掃描幅面的寬度決定。容易知道在數量較少的問題中用枚舉法可以找出用時最短的方案，但在數量多的時候計算量太太，不易找出，因此我們采用動態(tài)規(guī)劃法解決這個問題，分析了10張照片的擺放只有4種情況，即最大照片數P=1，2，3，4，并且從照片擺放的最多張數分別討論了P=1，2，3，4種情況下照片電子化過程用時情況，得出在最大張數為3和4的情況下用時最少，從時間變化上建立數學模型，通過此模型計算出了在不同情況下電子化過程用時最少的方法，并得出最少時間和所對應的組合。 對于問題2，附件2給出50張長度一樣，但寬度不一樣的照片，并且給出寬度為5

9、cm、8cm、11cm的照片各20、20、10張，考慮到照片長度都是26cm，因此可以 3 選擇A4幅面和LTR幅面對照片進行掃描，并且針對兩種掃描方法建立其關于時間的函數，通過比較選擇使總用時最少的幅面掃描，因此只需考慮不同照片組合情況下的模型求解，采用LINGO編程求解，通過此模型計算出了在不同情況下電子化過程用時最少的方法。 對于哪些照片組合在一起以及組合次數最少是該題的問題，因此如何正確有效的建立在不同寬度下求出組合問題的理論表達式以及總時間的表達式并設計算法求解成為模型建立的關鍵。 三、模型假設 1假設掃描儀較大的邊長是豎著的，對圖片處理時的旋轉沒有影響； 2假設照片擺放時各邊均與掃

10、描儀的矩形邊緣相平行或垂直； 3假設每張照片都是規(guī)整的矩形； 4. 假設照片質量好壞不影響掃描和圖像處理過程的時間. 四、符號說明 4 五、 模型建立和求解 5.1 問題一的模型建立及求解 5.1.1 問題分析 該問題是一個對于長度一定，寬度不同以及掃描用時最短問題的不同組合做出一個合理的設計方案，根據照片組合問題我們分為了5種情況進行討論： I. 每次掃描一張照片，需要10次掃描； II 每次掃描兩張照片，需要5次掃描； III每次掃描三張照片，需要4次掃描； IV 每次掃描四張照片，需要4次掃描； V 每次掃描五張照片，需要2次掃描。 但是進一步分析知道，掃描三張照片的組合情況只可以是（3

11、,3,2,2），四張照片的組合情況只有（4,2,2,2），而五張以上不存在組合情況，因此在下面的討論中，只討論4種情況。 5 5.1.2 理論分析 根據第一問的要求，可知要求的目標函數為時間的最小值，則有 T=T1+T2 (1-1) a. 掃描過程分析： 由題目已知，分辨率（dpi）已經確定為600dpi，即 DPI=600dpi (1-2) 則有約束條件： (l r?1n1r?0.5)?(dr?0.5)? Lk (1-3) r?1m1 (l r?1n2r?0.5)?(dr?0.5)?Dk (1-4) r?1m2 用圖表示即為： 圖一 即 ?l1?0.5?d2?0.5?Lk?d3?l4?0.5

12、?0.5?d2?0.5?Lk ?l2?0.5?Dk?d1?l3?1?Dk?d?d?1?D4k?1 根據表一掃描儀的掃描幅面大小可知： 6 由于附件給出的照片長度lr都是28cm ,最短的照片寬度為： mindr?3 (1-5) lr?mindr?1?maxLk (k?1) (1-6) 即 由（1-6）式可知，這種組合方式，如圖二 圖二 不滿足約束條件（1-3）、（ 1-4），所以不存在組合lr? dr。 又已知LTR掃描幅面為L2、D2，B5掃描幅面為L3、D3，因為 lr?28?L2?L3 (1-7) 因此由（1-2）和（1-7）可知，只能選用A4幅面掃描法，并且由（1-6）知，只存在一種擺

13、放照片的方法，且采用的分辨率為600dpi，則有 ?lr?0.5?Lk (1-8) r?1n 如圖三： 圖三 b.掃描時間 一次掃描一張照片的時間為: 7 t11 t1n?12?Sij （1-9） (1-10) 一次掃描n張照片的時間為： ?10?2n?Sij假設m次掃描中，每次都是n張，則： m次掃描n張照片的時間為： tmn?6?2mn?4m?mSij 如果每次掃描不一定相同的照片張數，則有： m 6?2m?nk?4m?mSij (1-11) k?1 c.掃描次數 假如采用一次一張的方法，則有 ?10(dr?0.5) r?180 D? 121?3 ?P?4 m Sum1?6?2m?nk?4

14、m?mSij k?1 m Sum2?(12?Sij)m?nk k?1 -得: mm(2?nk?4?Sij)m?6?(12?Sij)m?nkk?1k?1 m ?m?10?nn? k?1(1?k)Sij?4 k?1?6 k?1 m ?(?10?Sij)?nk?Sij?10 k?1 mm ?(?10?n? k?10)?Sij(1?nk) k?1k?1? 8 ?n k?1mk?1 ?0 ?采用m次nk 張照片的掃描方法更好 由（1-11）可以直觀的看出，掃描操作時間為m的一元一次函數，且隨m的增加，時間也增加 150 100 t 50 00246810 m1214161820 ?T1?m?minT1?

15、min(m) （1-12） 綜上可得，要取得最短時間，必須控制掃描的次數最少，由于已確定使用A4幅面掃描，其寬度為D1，每張照片寬度為di（i=1,2,3,10）,照片所占寬度為（） ?(d r?110r?0.5) D1 ?P?480?3 21 ?少于4次不可能把所有照片掃面完，即m?4 9 5.1.3 建立模型及求解 運用動態(tài)規(guī)劃方法建立模型，把照片掃描過程劃分為多階段處理，分別建立了在掃描照片最大張數下的數學表達式，然后運用LINGO軟件求解。 a.通過枚舉思想建立模型 通過對照片掃描過程的分析，我們將掃描情況劃分為5種情況求出電子化過程的總時間T，并且圖像處理時間都是50s, S13 =

16、120s: (1) P=1： 第一次：4+1+(2+1+S13+1+2) 第二次： (2+1+S13+1+2) 第十次： (2+1+S13+1+2)+1 Ta=5+10（6+S13）+1+50=1316s (2) P=2: 第一次:4+1+(4+1+S13+1+2) 第二次： (4+1+S13+1+2) 第五次： (4+1+S13+1+2)+1 Tb=5+5(8+S13)+1+50=696s (3)P=3: 第一次：4+1+（6+1+S13+1+2） 第二次： (6+1+S13+1+2) 第三次： (4+1+S13+1+2) 第四次： (4+1+S13+1+2)+1 Tc=5+2(10+S13

17、)+2(8+S13)+1+50=572s (4)P=4: 第一次：4+1+(8+1+S13+1+2) 10 第二次： (4+1+S13+1+2) 第三次： (4+1+S13+1+2) 第四次： (4+1+S13+1+2)+1 Td=5+(12+S13)+3(8+S13)+1+50=572s 得到用時最少的數學表達式為 n?T?4n?nS16?6?2?nXmax?(Xmax?Xi)?T1 i?1? 此題最優(yōu)化的方法為： 當P?5時不存在組合情況，因此只能在P?4情況下考慮，通過結果可知，Tc=Td=572s,因此采用組合(3,3,2,2 )和(4,2,2,2)兩種情況下的照片組合能夠使用時最少，

18、最快完成電子化過程。 在組合（4,2,2,2）下4張照片一起的只有（3,4,5,6）和（3,4,5,7），剩下的6 2張照片排列組合有C6=15種，因此共有30種情況。 b.動態(tài)規(guī)劃（0-1規(guī)劃）模型 (1)模型的建立 對于 張照片，長度相同，且已知第張照片的寬度為正數 片的寬度和價值相等），最大容納下的掃描幅面寬度為正數 的一個子集，使得子集中照片的總寬度不超過掃描幅面寬度，價值為正數（照，現要求找出這 張照片 且總價值盡量大。（由上述模型中可知，照片只能正放，故不考慮照片長度的影響）。 根據問題描述，可以將其轉化為如下的約束條件和目標函數： 于是，問題就歸結為尋找一個滿足約束條件（1），并

19、使目標函數式（2）達到最大的解向量。 0-1寬度問題可以看作是尋找一個序列，對任一個變量的判斷是決定等于1還是等 11 于0，在判斷時，會有兩種情況： a) 掃描幅面寬度容量不足以放入照片，則等于0，價值不增加； b) 掃描幅面寬度容量可以放入照片，則等于1，價值增加； 這兩種情況下總價值的最大者應該是對判斷后的價值。令表示在前張照片中能夠放入到寬度為 的掃描幅面寬度的總價值，則可以得到如下的動態(tài)規(guī)劃函數： 式（3）說明：把前面張照片放入掃描幅面寬度為0的掃描幅面和把0張照片放入掃描幅面寬度為 的掃描幅面中，得到的價值均為0. 式（4）第一個式子說明：如果第 張照片的寬度大于掃面幅面的寬度，則

20、放入第 張照片得到的最大價值和放入第 不能放入掃描幅面中； 式（4 ）第二個式子說明：如果第張照片的寬度小于掃描幅面的寬度，則會有兩種情況： 1. 如果把第 張照片能放入掃面幅面寬度為 的掃描幅面中，則掃面幅面的價值等于前張照片放入寬度為 的掃描幅面中價值與第張照片價值之和。 張照片得到的最大價值是相同的，即第 張照片 2. 如果第 張照片不能放入掃描幅面寬度為 的掃描幅面中，則掃面幅面價值就等于把前張照片放入掃面幅面寬度為 的掃描幅面中的價值。顯然，取二者中價值較大者作為把張照片放入掃面幅面為 的掃描幅面中的最優(yōu)解。 (2)模型的求解 第一步，只放入一張照片，確定在各種情況下掃描幅面能得到的

21、最大價值；第二步，只兩張照片，確定在各種情況下掃描幅面能夠得到的最大價值；依次類推，到了第就得到所需要的最優(yōu)解。 最后，便是在掃描幅面寬度為中，放入 張照片取得的最大價值。為了確定裝入背包的具體物品，從價值向前尋找。依此類推，直到確定第一個物品是否被裝入背包為 12 步 止。由此，得到如下的函數： 根據動態(tài)規(guī)劃函數，用一個二維數組 存放中間變量，表示把前張照片能放入掃面幅面寬度為 的掃描幅面中取得的最大價值(程序見附錄1)。 5.2 問題二模型建立及求解 5.2.1 問題分析 該問題是在第一問的基礎上增加照片的數量以及將照片劃分為3種長度各20、20、10張相同尺寸的照片，并且要求使用分辨率為

22、300dpi,對于該問的解答我們通過0-1規(guī)劃問題并且進一步分析知道， 5.2.1.1 理論模型 由問題一中的(1-1)式知： T=T1+T2 由題目知道，設分辨率為DPI，已確定為DPI=300dpi，并且照片長度lr均為26cm, 最短的照片寬度為mindr?5cm，因此滿足 lr?min?dr?1?max?Lk?k?1,2,3? （2-1） 即： 由（1-2）、（1-3）的約束條件可知： 不存在組合lr? dr，即 13 已知三種掃描幅面的長寬為Lk(k=1,2,3)，Dk(k=1,2,3) 因為 lr?26?L3, (2-2) 所以只能選用A4幅面掃描法和LTR幅面掃描法, 且由（2-

23、1）可知，只存在一種擺放照片的方法，即 圖五 5.2.1.2 掃描時間 已知掃描時間為Sij( i 為幅面，j為分辨率)，則A4幅面掃描法與LTR幅面掃描法的掃描時間分別為 A4: S12 LTR: S12 由第一問中對（1-11）式的證明可知，采用m次掃描nk張的方法為最優(yōu)解， 且掃描次數越少，所用時間越短。 由（1-8）和兩種掃描方法的寬度D1、D2 D1=21cm， 可知：A4每次所放張數nk1與LTR每次所放張數nk2的關系為： nk1?nk2 所以A4幅面掃描方法的掃描次數m1與LTR的掃描次數m2的關系為： m1?m2 且A4的掃描時間S12與LTR的掃描時間S22的關系為： 14

24、 S12?S22 A4的掃描過程總時間為： Sum1?6?2m1?nk1?4m1?m1S12 （2-3） k1?1m1 LTR的掃描過程總時間為： Sum2?6?2m2?nk2?4m2?m2S22 （2-4） k2?1m2 兩式相減為： Sum1?Sum2?(6?2m1?nk1?4m1?m1S12)?(6?2m2?nk2?4m2?m2S22) k1?1 k2?1 m1 m2 ?2(m1?nk1?2m2?nk2)?4(m1?m2)?(m1S12?m2S22) k1?1 k2?1 m1m2 （2-5） 所以 Sum1?Sum2?0 即針對第二問來說，所有照片掃描均使用LTR掃描方法為最優(yōu)解。 5.

25、2.2 模型建立及求解 接下來討論用LTR掃描方法掃描50張照片的最少次數： 設掃描次數為M，則目標函數為min (M)，已知共有3種尺寸的照片，擺放方法已定，在寬度的限制條件下，掃描方法如下表所示： 表四 掃描方法 決策變量：用xi表示按照第i種模式（i=1,2,10）分配的照片數量，顯然它們 15 應當是非負整數. 決策目標：所建立模型的目標為掃描的次數最少，即： min (M)= x1?x2?x3?x4?x5?x6?x7?x8?x9?x10 （2-6） 約束條件：d=5cm照片數不少于20張，d=8cm照片數不少于20張，d=11cm照片數不少于10張, ?x1+x2+x3+2x4+2x

26、5+3x6>20?x+x+x7+x8+2x9>20 ?15 （2-7) ?x+x+x>10?3410 模型求解：將（2-6）、（2-7)構成的整數線性規(guī)劃模型（加上整數約束），輸入LINGO求解，可以得到最優(yōu)解如下：(附錄2) ，即按照方法5和方法8來掃描照片是掃描次數最少x5?10，x8?10（其余變量為0） 的方法. 即： 方法5：掃描2張d=5cm的照片+掃描1張d=8cm的照片共10次 方法8：掃描1張d=8cm的照片+掃描1張d=11cm的照片共10次 總共是20次，在圖像處理過程中，采用方法5和方法8的方式設定的復制區(qū)域的尺寸只作了一次更改

27、，即設置了兩次，假如最少設置一次，則只有每次均掃描三種尺寸的照片，即：， 此種方法是不可行的，所以上述得出的方法即為掃描過程minT1和圖像處理過程minT2的最優(yōu)解. 并且有 n?T?4n?nS23?6?2?nXmax?(Xmax?Xi)?T2 i?1? 經過計算得出 minT1=30 s T?1756s 所以將整個流程安排完成需要1756秒。 此題最優(yōu)化的方法為： 同時掃描2張寬為5cm的照片和1張寬為8cm的照片共10次，同時掃描1張寬為8cm和1張寬為11cm的照片共10次，即得到最短的時間1756s. 16 六、 模型的結果分析 本文針對照片擺放的問題，采用0-1動態(tài)規(guī)劃方法和理論證

28、明建立數學模型，列出目標函數，對電子化過程用時最少建立理論數學模型，并且通過編程得出理論結果，和實際推導結果一致，并且得出10張照片掃描用時為572s以及50張照片用時為1756s，符合實際情況。 七、 模型優(yōu)缺點分析 （1）優(yōu)點： 1、 本文采用理論模型證明與0-1動態(tài)規(guī)劃方法這兩種思想來建立模型，這兩種模型在一定條件下可以相互轉化； 2、 在照片電子化過程用時最少的計算時，忽略復雜計算，不考慮旋轉問題； 3、 基于0-1規(guī)劃和理論思考，用MATLAB和LINGO編程，通過求解該模型，更能準確得出結果，在一定程度上由于理論討論。 （2）不足 所采用的理論思想和模型有一定的局限性，并且假設了照

29、片擺放位置以及處理照片時候的旋轉，在現實中并不是理想的，在計算總時間的時候有一定的主觀性，不能夠解決實際中所遇到的問題。 八、 參考文獻 1 姜啟源，謝金星，邢文訓，張立平編著.大學數學實驗（第二版）M.北京：清華大學出版社， 2 姜啟源，謝金星,葉俊編著.數學模型（第四版）M.北京：宮燈教育出版社， 3 許兆美.價值與重量相等的0/1背包問題的一種解法，成組技術與現代化，期 4 林鑫，基于0/1背包問題的討論，研究與設計，2007年第23卷第4期： 5 霍紅衛(wèi)，許進，保靜.基于遺傳算法的0/1背包問題求解，西安電子科技大學學報，1999年04期： 6 劉明波,陳學軍,程勁暉.三種無功優(yōu)化線性

30、規(guī)劃建模方法的比較J.電力系統(tǒng)及其自動化學報.1999(02) 7 余雪雷.線性規(guī)劃問題的一種改進算法D.吉林大學,2006 8 張魯輝,陳愛社.動態(tài)規(guī)劃在鋼材采購中的研究與應用J.河南建材. 2008(03) 9 HM Government .Planning and Compulsory Purchase Act 2004. 17 九、附錄 附錄1 #include<stdio.h> double c; /掃描幅面的寬度 int n; /照片的張數 int x100; /是否選取照片，為0或1 double weight100; double price100;

31、 double bp; /最大價值 double bA100; /最優(yōu)解 int times=0; /節(jié)點訪問次數 double currentWeight=0; /當前總寬度 double currentPrice=0; /當前總價值 void print(); /輸出每條有效路徑及最大價值 void Backtrack(int i) times+=1; if(i>n) print(); if(currentPrice>bp) bp=currentPrice; for(int j=1;j<=n;j+) bAj=xj; return; if(curre

32、ntWeight+weighti<=c) /將照片i放入掃描幅面，搜索左子樹 xi=1; currentWeight+=weighti; currentPrice+=pricei; Backtrack(i+1); /完成上面的遞歸，返回上一節(jié)點，搜索右子樹，及不選照片i currentWeight-=weighti; 18 currentPrice-=pricei; xi=0; Backtrack(i+1); void print() int i; printf("路徑為："); for(i=1;i<n;i+) printf("%d,",xi); printf("%d 價值為 %lfn",xi,currentPrice); int main() int i; printf("請輸入照片數量："); scanf("%d",&n); printf("請輸入掃描幅面寬度："); scanf("%lf",&c); printf("請輸入照片的寬度："