1、一、引言 二、線性規劃模型三、整數線性規劃模型第一講 規劃理論及模型 四、0-1整數規劃模型 五、非線性規劃模型 六、多目標規劃模型 七、動態規劃模型一、引言 我們從2005年“高教社杯”全國大學生數模競談起. 其中第二個問題是一個如何來分配有限資源，從而達到人們期望目標的優化分配數學模型. 它在運籌學中處于中心的地位. 這類問題一般可以歸結為數學規劃模型.賽的B題“DVD在線租賃”問題的第二問和第三問 最優化問題概述最優化問題的定義最優化問題的分類及處理方法最優化模型的基本要素最優化問題的定義最優化問題就是在給定條件下尋找最佳方案的問題，即在資源給定時尋找最好的目標，或在目標確定時使用最少的

2、資源。最優化問題的分類及處理方法無條件最優化問題：求導法等約束條件為等式的有約束條件的最優化問題：拉格朗日乘數法等約束條件為不等式的有約束條件的最優化問題：數學規劃數學規劃模型：目標規劃（一個、多個）、動（靜）態規劃（與時間是否有關）、線性規劃（整數規劃、0-1規劃）、非線性規劃最優化（規劃）模型的基本要素決策變量、目標函數和約束條件：決策變量是問題中有待確定的未知因素。目標函數是指對問題所追求的目標的數學描述。約束條件是指實現問題目標的限制因素。引例 某工廠在計劃期內要安排生產I、II兩種產品，該工廠每生產一件產品I可獲利2元，每生產一件產品II可獲利3元。問應如何安排計劃使該工廠獲利最多？

3、已知生產單位產品所需的設備臺時及A、B兩種原材料的消耗，如下表所示 12kg40原材料B16kg04原材料A8臺時21設備III運用規劃模型解決最優化問題的一般方法步驟如下：前期分析：分析問題，找出要解決的目標，約束條件，并確立最優化的目標。定義變量，建立最優化問題的數學模型，列出目標函數和約束條件。針對建立的模型，選擇合適的求解方法或數學軟件。編寫程序，利用計算機求解。對結果進行分析，討論諸如：結果的合理性、正確性，算法的收斂性，模型的適用性和通用性，算法效率與誤差等。 規劃模型的應用極其廣泛，其作用已為越來來越急速地滲透于工農業生產、商業活動、軍事行為核科學研究的各個方面，為社會節省的財富

4、、創造的價值無法估量. 特別是在數模競賽過程中，規劃模型是最常見的一類數學模型. 從92-06年全國大學生數模競越多的人所重視. 隨著計算機的逐漸普及，它越賽試題的解題方法統計結果來看，規劃模型共出現了15次，占到了50%，也就是說每兩道競賽題中就有一道涉及到利用規劃理論來分析、求解. 二、線性規劃模型 線性規劃模型是所有規劃模型中最基本、最例1.（食譜問題）設有 n 種食物，各含 m 種營養素，第 j 種食物中第 i 中營養素的含量為 aij , n 種食物價格分別為c1, c2, , cn，請確定食譜中n 種食物的數量x1, x2, , xn，要求在食譜中 m 種營養素簡單的一種. 2.1

5、 線性規劃模型的標準形式 的含量分別不低于b1, b2, , bm 的情況下，使得總總的費用最低. 首先根據食物數量及價格可寫出食譜費用為 其次食譜中第 i 種營養素的含量為 因此上述問題可表述為： 解 上述食譜問題就是一個典型的線性規劃問題，尋求以線性函數的最大（小）值為目標的數學模型.它是指在一組線性的等式或不等式的約束條件下，例： 某豆腐店用黃豆制作兩種不同口感的豆腐出售。制作口感較鮮嫩的豆腐每千克需要0.3千克一級黃豆及0.5千克二級黃豆，售價10元；制作口感較厚實的豆腐每千克需要0.4千克一級黃豆及0.2千克二級黃豆，售價5元。現小店購入9千克一級黃豆和8千克二級黃豆。 問：應如何安

6、排制作計劃才能獲得最大收益。一、問題前期分析該問題是在不超出制作兩種不同口感豆腐所需黃豆總量條件下合理安排制作計劃，使得售出各種豆腐能獲得最大收益。二、模型假設1假設制作的豆腐能全部售出。2假設豆腐售價無波動。變量假設： 設計劃制作口感鮮嫩和厚實的豆腐各x1千克和 x2千克，可獲得收益R元。 目標函數：獲得的總收益最大。 總收益可表示為：。 受一級黃豆數量限制：。 受二級黃豆數量限制：。 綜上分析，得到該問題的線性規劃模型：運輸問題（常見典型的線性規劃問題）例2. 設要從甲地調出物資2000噸，從乙地調出物 資1100噸，分別供給A地1700噸、B地1100噸、C假定運費與運量成正比. 在這種

7、情況下，采用不地200噸、D地100噸. 已知每噸運費如表1.1所示. 同的調撥計劃，運費就可能不一樣. 現在問：怎樣才能找出一個運費最省的調撥計劃？1572521甲15375151乙DCBA表 1.1銷地運費產地假設：假設題目中所給運費已考慮各地間公里數；只考慮運量和運費，不考慮車輛調撥等其它相關因素不考慮車輛返空的費用（或：所給運費已包含車輛返空的費用）變量說明：xij:從第i城運往第j地的蔬菜數量（i=1,2,3;j=1,2,3,4）乙甲DCBA解一般的運輸問題可以表述如下：數學模型： 若其中各產地的總產量等于各銷地的總銷量，即 類似與將一般的線性規劃問題轉化為其標準否則，稱為不平衡的運

8、輸問題，包括：，則稱該問題為平衡的運輸問題.總產量總銷量和總產量總銷量.形式，我們總可以通過引入假想的銷地或產地，將不平衡的運輸問題轉化為平衡的運輸問題. 從而，我們的重點就是解決平衡運輸問題的求解. 顯然，運輸問題是一個標準的線性規劃問題，因而當然可以運用單純形方法求解. 但由于平衡的運輸問題的特殊性質，它還可以用其它的一些特殊方法求解，其中最常用的就是表上作業法，該方法將單純形法與平衡的運輸問題的特殊性質結合起來，很方便地實行了運輸問題的求解. 關于運輸問題及其解法的進一步介紹參加文獻2. 對于線性規劃問題，如果要求其決策變量取整數值，則稱該問題為整數線性規劃問題.平面法和分支定界法是兩種

9、常用的求解整數線性 對于整數線性規劃問題的求解，其難度和運三、整數線性規劃模型算量遠大于同規模的線性規劃問題. Gomory割規劃問題的方法（見文獻1）. 此外，同線性規劃模型一樣，我們也可以運用LINGO和LINDO軟件包來求解整數線性規劃模型. 以1988年美國大學生數學建模競賽B題為例，說明整數線性規劃模型的建立例3. 有七種規格的包裝箱要裝到兩節鐵路平板車上去。包裝箱的寬和高是一樣的，但厚度（t，以cm 計）及重量（w，以kg計）是不同的. 表1給出了每種包裝箱的厚度、重量以及數量。每節平板車有10.2m 長的地方可用來裝包裝箱（像面包片那樣），載重為40t. 由于當地貨運的限制，對于

10、C5, C6, C7 類包裝箱的總數有一個特別的限制：這類箱子所占的空間（厚度）不能超過302.7cm. 試把包裝箱裝到平板車上，使得浪費的空間最小.種類C1C2C3C4C5C6 C7t/cm48.753.061.372.048.752.064.0w/kg200030001000500400020001000n/件8796648 為在第 節車上裝載第 件包裝箱的解 令 下面我們建立該問題的整數線性規劃模型。1) 約束條件兩節車的裝箱數不能超過需要裝的件數，即：每節車可裝的長度不能超過車能提供的長度：每節車可裝的重量不超過車能夠承受的重量：對于C5, C6, C7類包裝箱的總數的特別限制： 2)

11、 目標函數浪費的空間最小，即包裝箱的總厚度最大：3) 整數線性規劃模型由上一步中的求解結果可以看出，4) 模型求解運用LINGO軟件求解得到：5) 最優解的分析說明的裝車方案，此時裝箱的總長度為1019.7cm，兩節車共裝箱的總長度為2039.4cm.即為最優 但是，上述求解結果只是其中一種最優的裝車方案，即此答案并不唯一. 0-1整數規劃是整數規劃的特殊情形，它要求線性規劃模型中的決策變量xij只能取值為0或1.單隱枚舉法，該方法是一種基于判斷條件（過濾 0-1整數規劃模型的求解目前并沒有非常好的四、0-1整數規劃模型 算法，對于變量比較少的情形，我們可以采取簡條件）的窮舉法. 我們也可以利

12、用LINGO和LINDO軟件包來求解0-1整數規劃模型.背包問題例4. 有 n 個物品，編號為1, 2, , n，第 i 件物品重 ai 千克，價值為 ci 元，現有一個載重量不超過大，應如何裝載這些物品？ a 千克的背包，為了使裝入背包的物品總價值最用變量 xi 表示物品 i 是否裝包，i =1, 2, , n，并令：解可得到背包問題的規劃模型為：指派問題例5. 有n 項任務，由 n 個人來完成，每個人只能做一件， 第 i 個人完成第 j 項任務要 cij 小時，如何合理安排時間才能使總用時最小？ 引入狀態變量 xij ，并令：解則總用時表達式為：可得到指派問題的規劃模型為： 上面介紹的指派

13、問題稱為指派問題的標準形式，還有許多其它的諸如人數與任務數不等、及但一般可以通過一些轉化，將其變為標準形式.某人可以完成多個任務，某人不可以完成任務，某任務必須由某人完成等特殊要求的指派問題. 對于標準形式的指派問題，我們可以利用匈牙利算法實現求解. 它將指派問題中的系數構成一個矩陣，利用矩陣上簡單的行和列變換，結合解的判定條件，實現求解（見文獻2）.DVD在線租賃第二個問題的求解問題二的分析 經營成本和會員的滿意度是被考慮的兩個相互制約的重要因素. 在忽略郵寄成本的前提下，經營成本主要體現為DVD的數量. 我們主要考慮在會員向網站提供需求信息，且滿足一定要求的前提下，對給定數量DVD進行分配

14、決策，使得DVD的數量盡量小，會員滿意度最大. 假設按照公歷月份進行的租賃業務，即會員無論兩次租賃還是一次租賃，必須在當月內完成DVD的租與還. 同時假設網站對其會員進行一次租賃業務時，只能向其提供3張該會員已經預定的DVD，否則不進行租賃. 經觀察，可以認為在線訂單中每個會員的預定DVD的表示偏好程度的數字反映了會員對所預定不同DVD的滿意程度，且當會員租到其預定排序為1，2，3的三張DVD時，滿意度達到100% .會員沒有預定的DVD對其滿意度的貢獻為0 . 利用層次分析法，對此滿意指數的合理性進行了簡單分析. 該問題要求根據現有的100種DVD的數量和當前需要處理的1000位會員的在線訂單，制定分配策略，使得會員達到最大的滿意度. 因而我們認為只需對這些DVD進行一次性分配，使得會員的總體滿意度達到最大. 為此考慮建立優化模型，進行求解. 問題二的模型及求解 經營成本和會員的滿意度是被考慮的兩個相互制約的重要因素. 在忽略郵寄成本的前提下，經營成本主要體現為DVD的數量. 我