數學建模十大經典算法數學建模必備資料-文庫吧

【正文】 （2） 使之滿足條件 （3）構造n次多項式 使 = （4） 由 (5)即 滿足插值條件，于是問題歸結為具體求出基本插值多項式。根據（4）式以外所有的節點都是的根，因此令 又由=1，得： 所以有 代入（5）得 拉格朗日插值多項式為： 牛頓插值：（拉格朗日插值的缺點）拉格朗日插值公式的形式雖然有一定的規律， 但是當增加一個節點時，不僅要增加項數，而且以前各項也必須重新全部計算，不能利用已有的結果。為克服這一缺點，我們取用另一種形式――牛頓插值公式。牛頓插值公式中用到了差商。一般稱：為在處的n階差商。差商可列表計算：xi yi 一階差商 二階差商 三階差商 四階差商 x0 f (x0)x1 f (x1) f [x0, x1]x2 f (x2) f [x1, x2] f [x0, x1, x2]x3 f (x3) f [x2, x3] f [x1, x2, x3] f [x0, x1, x2, x3]x4 f (x4) f [x3, x4] f [x2, x3, x4] f [x1, x2, x3, x4] f [x0,?, x4]由差商定義可知由差商定義可求得記 則 其中稱為n次牛頓插值多項式，是截斷誤差。最終我們可以證明滿足插值條件 因此有 牛頓插值公式的優點是：當增加一個節點時，只要再增加一項就行了，即有遞推式當然，與拉格朗日插值相比它還有節省運算次數的優點（尤其是節省乘法運算次數）。分段插值與樣條插值為了避免高次插值可能出現的大幅度波動現象，在實際應用中通常采用分段低次插值來提高近似程度埃爾米特插值許多實際插值問題中，為使插值函數能更好地和原來的函數重合，不但要求二者在節點上函數值相等，而且還要求相切，對應的導數值也相等，甚至要求高階導數也相等。這類插值稱作切觸插值，或埃爾米特(Hermite)插值。滿足這種要求的插值多項式就是埃爾米特插值多項式 三角函數插值當被插函數是以2π為周期的函數時，通常用n階三角多項式作為插值函數，并通過高斯三角插值表出。三、線性規劃、整數規劃、多元規劃、二次規劃（1）線性規劃含義的理解線性規劃是運籌學中研究較早、發展較快、應用廣泛、方法較成熟的一個重要分支,，英文縮寫LP。它是運籌學的一個重要分支。在經濟管理、交通運輸、工農業生產等經濟活動中，提高經濟效果是人們不可缺少的要求，而提高經濟效果一般通過兩種途徑：一是技術方面的改進，例如改善生產工藝，：在一定條件下，合理安排人力物力等資源，求線性目標函數在線性約束條件下的最大值或最小值的問題，統稱為線性規劃問題。滿足線性約束條件的解叫做可行解，由所有可行解組成的集合叫做可行域。決策變量、約束條件、目標函數是線性規劃的三要素。線性規劃問題的數學模型的一般形式和模型建立（1）列出約束條件及目標函數 （2）畫出約束條件所表示的可行域 （3）在可行域內求目標函數的最優解及最優值（實際問題中建立數學模型一般有以下三個步驟：根據影響所要達到目的的因素找到決策變量；；。）所建立的數學模型具有以下特點：（1）、每個模型都有若干個決策變量（x1,x2,x3……，xn），其中n為決策變量個數。決策變量的一組值表示一種方案，同時決策變量一般是非負的。（2）、目標函數是決策變量的線性函數，根據具體問題可以是最大化（max）或最小化（min），二者統稱為最優化（opt）。（3）、約束條件也是決策變量的線性函數。當我們得到的數學模型的目標函數為線性函數，約束條件為線性等式或不等式時稱此數學模型為線性規劃模型。實例生產計劃問題問題：某企業要在計劃期內安排生產甲、乙兩種產品，這個企業現有的生產資料是：設備18臺時，原材料A ：4噸，原材料 B： 12噸；已知單位產品所需消耗生產資料及利潤如下表。問應如何確定生產計劃使企業獲利最多？ 產品資源甲乙資源量設備/臺時3218原料A/噸104原料B/噸0212單位贏利/萬元35設x1為甲產品分配的設備臺數，x2為乙產品分配的臺數。則條件限制為：3*x1+2*x2181*x1+0*x240*x1+2*x212x10，x20求max z=3*x1+5*x2用lingo編程，程序如下：max=3*x1+5*x2。3*x1+2*x2=18。x1=4。x2=6。x1=0。x2=0。結果為：Global optimal solution found.Objective value: Total solver iterations: 1 Variable Value Reduced Cost X1 X2 Row Slack or Surplus Dual Price 1 2 3 4 5 6 即在x1=2，x2=6時，企業獲利最多，為36萬元。線性規劃的應用在企業的各項管理活動中,例如計劃、生產、運輸、技術等問題,線性規劃是指從各種限制條件的組合中,選擇出最為合理的計算方法,建立線性規劃模型從而求得最佳結果. 廣泛應用于軍事作戰、經濟分析、經營管理和工程技術等方面。為合理地利用有限的人力、物力、財力等資源作出的最優決策，提供科學的依據。（2）整數規劃一類要求問題的解中的全部或一部分變量為整數的數學規劃。從約束條件的構成又可細分為線性，二次和非線性的整數規劃。 　　在線性規劃問題中，有些最優解可能是分數或小數，但對于某些具體問題，常要求某些變量的解必須是整數。例如，當變量代表的是機器的臺數，工作的人數或裝貨的車數等。為了滿足整數的要求，初看起來似乎只要把已得的非整數解舍入化整就可以了。實際上化整后的數不見得是可行解和最優解，所以應該有特殊的方法來求解整數規劃。在整數規劃中，如果所有變量都限制為整數，則稱為純整數規劃；如果僅一部分變量限制為整數，則稱為混合整數規劃。整數規劃的一種特殊情形是01規劃，它的變數僅限于0或1。不同于線性規劃問題，整數和01規劃問題至今尚未找到一般的多項式解法。組合最優化通常都可表述為整數規劃問題。兩者都是在有限個可供選擇的方案中，尋找滿足一定約束的最好方案。有許多典型的問題反映整數規劃的廣泛背景。例如，背袋（或裝載）問題、固定費用問題、和睦探險隊問題（組合學的對集問題）、有效探險隊問題（組合學的覆蓋問題）、旅行推銷員問題, 車輛路徑問題等。因此整數規劃的應用范圍也是極其廣泛的。它不僅在工業和工程設計和科學研究方面有許多應用，而且在計算機設計、系統可靠性、編碼和經濟分析等方面也有新的應用。 。解整數規劃最典型的做法是逐步生成一個相關的問題，稱它是原問題的衍生問題。對每個衍生問題又伴隨一個比它更易于求解的松弛問題（衍生問題稱為松弛問題的源問題）。通過松弛問題的解來確定它的源問題的歸宿，即源問題應被舍棄，還是再生成一個或多個它本身的衍生問題來替代它。隨即再選擇一個尚未被舍棄的或替代的原問題的衍生問題，重復以上步驟直至不再剩有未解決的衍生問題為止。目前比較成功又流行的方法是分枝定界法和割平面法，它們都是在上述框架下形成的。01規劃在整數規劃中占有重要地位，一方面因為許多實際問題，例如指派問題、選地問題、送貨問題都可歸結為此類規劃，另一方面任何有界變量的整數規劃都與01規劃等價，用01規劃方法還可以把多種非線性規劃問題表示成整數規劃問題，所以不少人致力于這個方向的研究。求解01規劃的常用方法是分枝定界法，對各種特殊問題還有一些特殊方法，例如求解指派問題用匈牙利方法就比較方便。（4）二次規劃二次規劃是非線形規劃中一類特殊的數學規劃問題，它的解是可以通過求解得到的。通常通過解其庫恩—塔克條件（KT條件）,獲取一個KT條件的解稱為KT對，其中與原問題的變量對應的部分稱為KT點。二次規劃分為凸二次規劃與非凸二次規劃，前者的KT點便是其全局極小值點，而后者的KT點可能連局部極小值點都不是。若它的目標函數是二次函數，則約束條件是線性的。由于求解二次規劃的方法很多，所以較為復雜；其較簡便易行的是沃爾夫法，它是依據庫恩－塔克條件，在線性規劃單純形法的基礎上加以修正而成的。此外還有萊姆基法、畢爾法、凱勒法等。四、圖論：（參考資料：建模教程(圖與網絡））（1）含義的理解圖論是專門研究圖的理論的一門數學分支，屬于離散數學范疇，與運籌學有交叉。圖論中常用點和點之間的線所構成的圖，反映實際生產和生活中的某些特定對象之間的特定關系。一般來說，通常用點表示研究對象、用點與點之間的線表示研究對象之間的特定關系。 在一般情況下，圖中的相對位置如何，點與點之間線的長短曲直，對于反映研究對象之間的關系，顯的并不重要。 因此，圖論中的圖與幾何圖，工程圖等本質上是不同的。（2）歷史（包括應用范圍）它有200多年歷史，大體可劃分為三個階段：第一階段是從十八世紀中葉到十九世紀中葉，處于萌芽階段，多數問題圍游戲而產生，最有代表性的工作是所謂的Euler七橋問題，即一筆畫問題。第二階段是從十九世紀中葉到二十世紀中葉，這時，圖論問題大量出現，如Hamilton問題，地圖染色的四色問題以及可平面性問題等，這時，也出現用圖解決實際問題，如Cayley把樹應用于化學領域，Kirchhoff用樹去研究電網絡等.第三階段是二十世紀中葉以后，由生產管理、軍事、交通、運輸、計算機網絡等方面提出實際問題，以及大型計算機使大規模問題的求解成為可能，特別是以Ford和Fulkerson建立的網絡流理論，與線性規劃、動態規劃等優化理論和方法相互滲透，促進了圖論對實際問題的應用。算法重要的算法 求有向圖的強連通分支 (Strongerst Connected Component)（1）Kosaraju算法（2）Gabow算法（3）Tarjan算法求最小生成樹 (Minimal Spanning Trees)（1）Kruskal算法(2)Prim算法最小樹形圖（1）朱永津劉振宏算法最短路徑問題（1）SSSP(Singlesource Shortest Paths)①Dijkstra算法②BellmanFord算法(SPFA算法)（2）APSP(Allpairs Shortest Paths)①FloydWarshall算法②Johnson算法網絡流問題（1）最大網絡流①增廣路算法⒈FordFulkerson算法⒉EdmondsKarp算法⒊最短路徑增殖EK2（MPLA）⒋Dinic②預流推進算法（2）最小費用流圖匹配問題（1）匈牙利算法（2）Hopcroft Karp算法（3）KuhnMunkres算法（4）Edmonds39。 blossomcontraction 算法（有關資料網址：）（1） 基本概念無向圖一個無向圖(undirected graph)是由一個非空有限集合和中某些元素的無序對集合構成的二元組，記為。其中稱為圖的頂點集（vertex set）或節點集（node set）， 中的每一個元素稱為該圖的一個頂點（vertex）或節點（node）；稱為圖的邊集（edge set），中的每一個元素(即中某兩個元素的無序對)記為或 ，被稱為該圖的一條從到的邊（edge）。當邊時，稱為邊的端點，并稱與相鄰（adjacent）；邊稱為與頂點關聯（incident）。如果某兩條邊至少有一個公共端點，則稱這兩條邊在圖中相鄰。邊上賦權的無向圖稱為賦權無向圖或無向網絡（undirected network）。我們對圖和網絡不作嚴格區分，因為任何圖總是可以賦權的有向圖一個有向圖（directed graph或 digraph）是由一個非空有限集合和中某些元素的有序對集合構成的二元組，記為。其中稱為圖的頂點集或節點集， 中的每一個元素稱為該圖的一個頂點或節點；稱為圖的弧集（arc set），中的每一個元素(即中某兩個元素的有序對)記為或，被稱為該圖的一條從到的?。╝rc）。當弧時，稱為的尾（tail），為的頭（head），并稱弧為的出?。╫utgoing arc），為的入弧（ining arc）。對應于每個有向圖，可以在相同頂點集上作一個圖，使得對于的每條弧，有一條有相同端點的邊與之相對應。這個圖稱為的基礎圖。反之，給定任意圖，對于它的每個邊，給其端點指定一個順序，從而確定一條弧，由此得到一個有向圖，這樣的有向圖稱為的一個定向圖。完全圖、二分圖每一對不同的頂點都有一條邊相連的簡單圖稱為完全圖(plete graph)。個頂點的完全圖記為。若，（這里表示集合中的元素個數），中無相鄰頂點對，中亦然，則稱為二分圖(bipartite graph)；特別地，若，則，則稱為完全二分圖，記成。最短路、網絡流、二分圖 最短路問題（SPP－shortest path problem）最短路徑問題是圖論中十分重要的最優化問題之一，它作為一個經常被用到的基本工具，可以解決生產實際中的許多問題，比如城市中的管道鋪設，線路安排，工廠布局，設備更新等等。也可以用于解決其它的最優化問題。若網絡中的每條