智能制造系統設計 課件2.4 運籌學

運籌學--智能制造系統的器官1運籌學概念2運籌學內容——十大分支3運籌學應用——與智能制造的關系智能制造框架

運籌學與智能制造關系

動態規劃智能制造生態圈智能排產PLMERPAPSLIMSSRM企業供應方工廠實驗數據研發工藝工藝仿真物料采購單與物料供應計劃排產發布MES運籌學非線性規劃網絡分析排隊論決策分析對策論WMS物料配送存儲論一一對應運輸問題線性規劃動態規劃和整數規劃運籌學釋義與發展簡史運籌學釋義

運籌學(operationalresearch)一詞起源于第二次世界大戰時期的英國。運籌學在不同的領域有不同的釋義,從其性質與特點可定義為:

運籌學是一門以數學為主要工具,用系統的觀念,多學科的綜合,應用模型技術,為經濟、軍事、管理等部門提供最優的決策方案。“夫運籌帷幄之中，決勝前里之外”，樸素的運籌學思想在我國古代文獻中有不少記載。如齊王賽馬和北宋丁渭修復皇宮等事例。

現代運籌學名詞源于1938年英國，為解決空襲的

早期預警中的協調配合問題。英軍成立了由P.M.S.Blackett領導的“operationalresearch”小組。由于綜合應用了科學方法和技術，糾正了人們一些直觀想象的錯誤，有效解決了當時戰爭中的一些新問題。運籌學的發展趨勢：(1)運籌學理論研究將會進一步系統深入發展．(2)運籌學將向一些新的研究領域發展．(3)運籌學分散融化于其他學科，并結合于其他學科一起發展．(4)運籌學沿原有的各學科分支向前發展．(5)運籌學中建立模型的問題將日益受到重視．(6)運籌學的發展將進一步依賴計算機的應用和發展．工業生產優化1940二戰期間的軍事應用交通運輸的應用融合大數據人工智能結合計算機技術19702000195019802020深度運籌時間線

運籌學將不同的實際問題歸結為不同的數學模型，不同的模型構成了運籌學的各個分支，主要的分支有：1.線性規劃（linearprogramming)——PLM

2.非線性規劃（nonlinearprogramming)——PLM3.動態規劃（dynamicprogramming)——MES4.整數規劃（Integerprogramming——SCM5.網絡分析（networkanalysis)——ERP6.運輸問題（Transportationproblem）7.存儲論（inventorytheory)——WMS8.排隊論（queueingtheory)——APS9.對策論（gametheory)——CRM10.決策分析（decisiontheory)——CRM運籌分析基本步驟運籌學的核心方法為智能制造系統提供了強有力的決策支持與優化方案。這些方法不僅在理論上精致而全面，也在實際應用中證明了其高效與可行性。問題的分析和確立深入分析，并準確表述問題的本質和目標模型的建立以形式化的方式描述問題結構和關系模型的求解和優化數學方法和算法對建立的模型進行求解模型的驗證和修正確保解在實際應用中的有效性和可行性解的有效控制將優化的方案轉化為實際行動，實施并監控方案的執行過程方案的實施

確保模型的準確性和可靠性在多元化的經濟活動中，巧妙地利用手中有限的資源，以精心的統籌安排實現總體效益的最大化，或是在既定的任務目標下，如何以最小的資源消耗達成目標，這些都是我們面臨的關鍵問題。這類問題，我們通常稱之為規劃問題。而當這類問題被轉化為數學語言進行表述時，如果目標（函數）以及資源的約束條件均呈現為線性函數的形式，那么我們便稱之為線性規劃問題。第一章線性規劃

在考慮資源的合理分配時，還要兼顧效益的最大化線性規劃問題的數學模型，其一般形式是：

線性規劃問題及其數學模型min(或max)z=CTX

≤(≥,=)bX≥0其中:

向量形式:線性規劃問題及其數學模型min(或max)Z=CTXAX≤(≥,=)bX≥0其中:矩陣和向量形式:線性規劃問題及其數學模型例如對三個資源的約束，構建二維坐標系。考慮目標函數，在可行域上找到使得目標函數達到最大值的方案。資源1資源2資源3等值線12340123456789圖2-75

三個資源的二維坐標系圖解法對模型中只含2個變量的LP，可通過在平面坐標系中作圖求解。其步驟概括為：1.在平面建立直角坐標系；2.圖示約束條件，找出可行域；3.圖示目標函數和尋求最優解。

圖解法一、圖解法的步驟：二、線性規劃問題求解的幾種可能的結局

無窮多最優解：目標函數與某約束條件對應成比例。無界解：可行域無界無解或無可行解：無可行域1.解的情況有：唯一最優解；無窮多最優解；無界解；無可行解。2.若LP的可行域存在，則可行域是一凸集。3.若線性規劃問題的最優解存在,則最優解或最優解之一(如有無窮多)一定是可行域的某個頂點。4.解題思路,先找出可行域的某個頂點，計算其目標函數值。比較相鄰頂點的目標函數值，直至找出使目標函數值最大的頂點。圖解法三、從圖解法得到的啟示：

通過建立一個目標函數和一系列線性約束來尋找最優解。在智能制造的大背景下，線性規劃與PLM的結合，不僅強化了對生產流程的智能化管理，還促進了制造系統中資源配置的精準化和科學化，為企業的可持續發展提供了有力的決策支持。通過對生產計劃的優化，企業可以更靈活地應對市場變化，實現生產效率和產品質量的雙重提升，從而在激烈的市場競爭中占據有利地位。產品外觀圖產品加工路線生產物料清單產品設計產品工藝設計產品生產制造產品服務產品設計圖設計物料清單產品庫存信息客戶需求信息客戶需求產品的形成過程產品資料與信息

運輸是WMS和SCM中的一類重要問題。供應鏈是一個由物流系統和該供應鏈中的所有單個組織或企業相關活動組成的網絡。為滿足供應鏈中各方的需求，需要對物品、服務及相關信息，從產地到消費地高效率、低成本地流動及儲存進行規劃、執行和控制。運籌學中對運輸模型的研究為達到上述目的提供了相應的理論和方法論基礎。第二章運輸問題圖2-77

運輸網

運輸問題即研究物資運輸的調度問題。其典型的情況是：設某種物品有m個產地A1,A2,……,Am，各產地的產量分別為a1,a2,……am;有n個銷地B1,B2,…,Bn，各銷地的銷量分別為b1,b2,……,bn，假定從產地Ai（i=1,2……m)向銷地Bj（j=1,2,……,n）運輸單位物品的運價是cij，如圖所示，問怎樣調運這些物品才能使總運費最少？運輸問題及數學模型產銷平衡問題的數學模型為：或用表格表示：運輸問題及數學模型運輸問題一定有有限最優解運輸問題的約束系數矩陣⑴的元素等于０或１。⑵運輸問題的約束系數矩陣的每一列有兩個非零元素。對產銷平衡問題有：⑶所有約束都是等式約束。⑷產量等于總銷量。運輸問題及數學模型運輸問題數學模型的特點運輸問題的解運輸問題的解X＝（xij）代表一種運輸方案。xij的值表示從Ai調運數量為xij的物品到Bj。解X必須滿足模型中所有約束條件。基變量對應的約束方程組的系數列向量線性無關。運輸問題模型中的約束條件個數為m+n個，但因為總產量=總銷量，故只有m+n-1個是線性獨立的，所以解X中非零變量的個數不能大于m+n-1個。為使迭帶過程能順利進行，基變量在迭代過程中應保持為m+n-1個。運輸問題及數學模型最小元素法：產大于銷，劃掉列；產小于銷，劃掉行銷產B1B2B3B4產量A141241116A22103910A38511622銷量8141214②⑤⑥81410268681026①③④⑦運輸問題的最小元素法前面討論的線性規劃問題，有些最優解可能是分數或小數，這是因為線性規劃是連續變量的優化問題。在實際問題中，常有要求問題的解必須是整數的情形（整數解），如人員、設備配置等。線性規劃中如果所有的變量都限制為（非負）整數，就稱之為純整數線性規劃或稱為全整數線性規劃。第三章整數規劃整數規劃的數學模型及解的特點整數線性規劃的分類：純整數線性規劃：指全部決策變量都必須取值的整數線性規劃。也稱全整數規劃。混合整數線性規劃：指決策變量中有一部分必須取整數值，另一部分可以不取整數值的線性規劃。0-1型整數線性規劃：指決策變量只能取值0或1的整數線性規劃。整數規劃的數學模型及解的特點整數規劃數學模型為：去掉整數約束后的數學模型稱為整數規劃的松弛問題整數規劃及其松弛問題，從解的特點看，二者間既有密切的聯系，又有本質的區別。松弛問題的可行域是一凸集，整數規劃的可行域（非凸集）是它的松弛問題的可行解集的一個子集。由于整數規劃的可行解一定是它的松弛問題的可行解(反之則不一定)。所以整數規劃的最優解的目標函數值≤其松弛問題的目標函數值。在一般情況下，松弛問題的最優解不會剛好滿足整數約束條件，自然就不是整數規劃的最優解。解的特點：整數規劃的數學模型及解的特點整數規劃并不是線性規劃取整。求解整數規劃可用分支定界法和割平面解法。分支定界解法，就是只檢查可行的整數部分，就能定出最優的整數解，可用于解純整數或混合的整數規劃問題。整數規劃的求解例圖2-76

三個約束的二維坐標系1234056781234678959x1+8x2=567x1+22x2=70z=x1+x2①

分支定界解法分支定界解法整數規劃的求解迭代過程圖整數規劃的求解②

割平面解法先利用單純形法解其松弛問題，若最優解中X*的所有分量均為整數，則原問題得到最優解，否則，從X*的非整數分量中選一個，用于構造一個線性約束條件，將其加入最終單純形表中在繼續求解．重復上述步驟，直到獲得整數最優解為止。現實生活中經常遇到這樣的問題，如某單位需要完成n項任務，有n個人可承擔這些任務。由于每個人專長不同，各人完成任務不同（或所耗費時間），效率也不同。于是產生應指派哪個人去完成哪項任務，使完成n項任務的總效率最高（或所需總時間最小）的問題。這類問題被稱為指派（分配）問題（assignment

problem）。整數規劃的求解問題要求極小化時的數學模型是：整數規劃的求解約束條件②說明第j項任務只能一人完成：約束條件③說明第i人只能完成一項任務。約束條件②~④的可行解可寫成表格或矩陣形式，稱為解矩陣。整數規劃的求解第一步：使指派問題的系數矩陣經變換，在各行各列都出現0元素。整數規劃的求解反復進行前兩步直到0元素都被圈出和劃掉為止這表明，甲加工D，乙加工B，丙加工A，丁加工C，所需總時間最少。

第一步：變換系數矩陣。第二步：用最少的直線覆蓋系數矩陣中的零元素，若直線數等于矩陣階數n，則已得到最優解，可用畫圈的方法確定獨立零元素。否則轉第三步。第三步：對于系數矩陣中未被直線覆蓋的元素選取最小者θ

，所有未被直線覆蓋的元素都減去θ，而被一條直線覆蓋的元素不變，被兩條直線覆蓋的元素加上θ

，轉第二步。

整數規劃的求解匈牙利解法的一般步驟:→-1-7-6-6-6-4-3因為可以覆蓋所有０元素的最少直線為４條，小于矩陣階數，故獨立０元素個數小于階數，非最優。轉下一步調整。

整數規劃的求解→

整數規劃的求解→-1-1+1

C’’已有５個獨立的０元素，故可以確定最優的指派方案X。在很多管理情境中，企業面臨著多階段（可以體現為空間、時間等維度）的決策問題，每一階段的最優決策不僅受制于當時的實際情況（比如當時具備的資源)，而且要考慮到該決策對未來的影響。因此，不同階段的決策是彼此關聯的。動態規劃提供了一種解決多階段決策過程最優化的數學方法。第四章動態規劃多階段決策過程的最優化所謂多階段決策問題是指這樣一類活動過程:它可以分為若干個互相聯系的階段(稱為時段)，在每一階段都需要作出決策。這個決策不僅決定這一階段的效益,而且決定下一階段的初始狀態。每個階段的決策確定以后,就得到一個決策序列,稱為策略。多階段決策問題求一個策略,使得整個活動過程的整體效果最優。243254354735358235724332圖2-78

簡單的線路網圖動態規劃的基本概念：

⑴

階段：將所給問題的過程，按時間或空間特征分解為若干相互聯系的階段，以便按次序去求每一階段的解。用k表示階段變量。⑵狀態：各階段開始時的客觀條件叫做狀態。描述各階段的客觀條件的變量稱為狀態變量sk

，狀態變量sk的取值集合稱為狀態集合,用Sk表示。

狀態應具有如下性質：當某階段狀態給定后，在這階段以后過程的發展不

受以前各段狀態的影響。這種特性稱為狀態的無后效性。多階段決策過程的最優化⑶決策和策略：當個階段的狀態取定后，就可以做出不同的決策（或選擇），從而確定下一階段的狀態，這種決定稱為決策，表示決策的變量稱為決策變量，用uk（sk)表示。而當各階段的決策確定后，從初始階段開始一直到最后一個階段結束就構成一個決策序列，每一可能的決策序列稱為一個策略。用p1,n{u1(s1),u2(s2)…un(sn)}表示。⑷狀態轉移方程：動態規劃中本階段的狀態往往是上一階段狀態和上一階段的決策結果.它們的關系可用sk+1=T(sk,uk)表示由于它表示了由k階段到k+1階段的狀態轉移規律,所以稱為狀態轉移方程。多階段決策過程的最優化動態規劃中用于衡量所選定策略的優劣的數量指標稱為指標函數。指標函數的最優解（最大值或最小值）稱為最優值函數，它表示從第k階段狀態采用最優策略到過程終止時的最佳效益值，即例1生產與存儲問題

某工廠每月需供應市場一定數量的產品,并將所余的產品存入倉庫。一般某月適當增加產量可降低生產成本，但超產部分存入倉庫會增加庫存費用。要求制定一個逐月的生產計劃，在滿足需求的條件下，使得一年的生產與存儲費用之和最小。

該問題可以看成每月一個決策階段，全年12個階段逐次進行決策。

多階段決策過程的最優化例2投資決策問題某公司現有現金Q萬元，在今后5年內考慮給A、B、C、D4個項目投資，這些項目的投資的回收期限、回報率均不同，問該公司應如何確定這些項目的每一年的投資額，使得到第五年末擁有資金的本利總額最大。

該問題可以看成每年一個決策階段,共5個階段逐次進行決策。例3設備更新問題企業在使用設備時都要考慮設備的更新問題。因為設備越存舊所需的維護維修費用越多，但購買新設備則要一次性支付較大的費用。現某企業要決定一臺設備未來8年的更新計劃，已預測了第j年購買設備的價格為Kj，設Gj為經過j年后的殘值，Cj為設備連續使用j-1年后在第j年的維修費用（j=1,2,……,8)。問應在那些年更新設備可使得總費用最小。

這是一個8階段決策問題，每年年初要做出決策，是繼續使用舊設備，還是購買新設備。

多階段決策過程的最優化例4最短路問題逆序解法狀態轉移方程確定了由一個狀態到另一個狀態的演變過程，記為圖2-78

簡單的線路網圖243254354735358235724332

多階段決策過程的最優化第一步:

k=5第二步:

k=4

路徑：D1→E1→F路徑：D2→E2→F路徑：D3→E1→F圖2-78

簡單的線路網圖243254354735358235724332

多階段決策過程的最優化

多階段決策過程的最優化第三步：k=3第四步：k=2第五步：k=1決策序列圖2-78

簡單的線路網圖243254354735358235724332將多階段決策過程劃分階段，恰當地選取狀態變量、決策變量及定義最優指標函數，把問題化成一簇同類型的子問題，然后逐個求解。求解時從邊界開始，逆（順）過程行進方向，逐段遞推尋優。在每一個子問題求解時，都利用前段已求出的子問題的最優結果，最后一個子問題的最優解，就是整個問題的最優解。動態規劃方法就是把當前一段與未來各段分開，又把當前效益與未來效益結合起來考慮的一種最優算法，因此每段的最優決策是從全局考慮的。動態規劃的基本思想：

多階段決策過程的最優化從需要管理的任務的總進度著眼，以任務中各工作所需要的工時為時間因素，按照工作的先后順序和相互間的關系作出網絡圖，以反映任務全貌，實現管理過程的模型化。然后進行時間參數計算，找出計劃中的關鍵工作和關鍵路線，對任務的各項工作所需的人、財、物通過改善網絡計劃作出合理的安排，得到最優方案并付諸實施。第五章網絡分析

網絡圖網絡就是與點或邊有關的帶有某種數量指標的圖（賦權圖）。網絡圖又稱箭頭圖，由帶箭頭的線和節點組成。箭線表示工作（或工序、活動），節點表示事項。工作是組成整個任務的各個局部任務，需要一定的時間與資源，而事項則是表示一個或若干個工作的開始或結束，與工作相比，事項不需要時間或所用時間可以忽略不計。圖2-79

簡單網絡

當ERP系統在網絡環境中運行時，會產生大量的數據。這些數據不僅包含了企業的運營狀況，還記錄了用戶的行為、網絡流量等關鍵信息。通過網絡分析，企業可以深入了解這些數據背后的含義，發現潛在的問題和機會。網絡圖中的時間參數，主要目的是找出關鍵路線，為網絡計劃的優化、調整和執行提供明確的時間概念。網絡圖的時間參數包括工作所需時間、事項最早、最遲時間、工作最早、最遲時間及時差等。212683574453242314

網絡圖可見第4條路線所需時間最長。通常把網絡圖中所需時最長的路稱為關鍵路，關鍵路上的工作稱為關鍵工作。212683574453242314上圖有４條路線：１２３５８４６７１２８１２６７８１２３４６７８4+5+1+3=134+3+4+2+4=174+2+2+4=124+5+2+4+2+4=21

網絡圖存儲論研究的基本問題是：對于特定的需求類型，以怎樣的方式進行補充，才能最好地實現存儲管理的目標。儲存物品的現象是為了解決供應（生產）與需求（消費）之間的不協調問題，這種不協調性一般表現為供應量與需求量和供應時期與需求時期的不一致性（供不應求或供過于求）。在供應與需求之間加入儲存這一環節，能夠起到緩解供應與需求之同不協調的作用。第六章存儲論根據需求和補充過程中是否包含隨機性因素，存儲問題分為確定型和隨機型兩種。存儲管理中常常以經濟性作為管理目標，所以費用分析是存儲論研究的基本方法。確定型庫存模型可分為經濟訂貨批量模型、帶有提前期的經濟訂貨批量模型、存在數量折扣的庫存模型。隨機型庫存模型分為隨機離散需求報童模型和隨機連續需求報童模型。存儲問題經濟訂貨批量模型不允許缺貨，補充時間極短因為Q=Rt，所以訂貨費為C3+KRt，t時間內的平均訂貨費為：

t時間內的平均存儲量為：因此t時間內的平均存儲費為：t時間內平均費用為：經濟批量公式（EOQ）：圖2-81

模型一的存儲狀態圖提前期的經濟訂貨批量模型允許缺貨的情況，且補充時間較長圖2-82

模型二的存儲狀態圖

補充周期內的生產速度P大于需求速度R，這意味著在補貨期間，庫存水平會逐漸上升，直至達到設定的再訂貨點。

由于生產速度恒定，且P>R，可以預測庫存將在一個補貨周期內先減少到零（如果需求量足夠大），然后進入缺貨狀態，直至新的補貨到達。需要考慮缺貨成本（C2）、存儲成本（C1）、訂貨成本（C3）。開始生產時間：結束生產時間：隨機儲存模型當每天準備Q份報紙時，報童每天的損失期望值為：

由于C(Q)是離散的，故采用邊際分析法：排隊論也稱隨機服務系統理論，就是為解決排隊時，如機械故障、存儲調節、增添服務等問題而發展起來的一門學科。排隊系統的優化問題分為兩類：系統的最優設計和最優控制，即靜態最優問題和動態最優問題。在一般情況下，提高服務水平可以減少顧客的等待費用，但卻常常增加了服務機構的成本。因此優化的目標之一就是使得這兩者的費用之和為最小。第七章排隊論圖2-84

排隊系統排隊論是研究由于隨機因素的影響而產生擁擠現象的科學，也稱隨機服務系統理論。排隊系統的優化問題分為兩類:系統的最優設計和最優控制,即靜態最優問題和動態最優問題。在具體實踐中，可以通過建立數學模型來描述排隊系統的運作過程，并利用數學工具進行求解。常見的排隊系統模型有M/M/1、M/M/c、M/G/1等，它們分別描述了不同的服務過程和顧客到達過程。M/M/1/k模型服務水平服務費用總費用等待費用費用

構建M/M/1/k模型：在平穩狀態下，單位時間內到達并進入系統的平均顧客數為

，它即是單位時間內實際服務完的平均顧客數，設每服務一顧客服務機構的收入為G元，于是單位時間內輸入的期望值是

元，故利潤為：

排隊論可以幫助APS系統建立精確的生產模型，包括工作站的排隊情況和資源利用率。通過排隊論的模型，APS可以預測工作站的瓶頸和可能的等待時間，從而調整生產計劃和資源分配，以最大化生產效率。排隊論提供了對物流系統的詳細分析，例如等待時間、服務率、AGV小車利用率等。今日最后期限今日最后期限CEADBCEADB對策論（GameTheory），又名博弈論，乃是一門專注于研究具有對抗性或競爭性特征的數學理論和方法。它不僅作為現代數學的一個嶄新分支熠熠生輝，更是運籌學領域的重要一環。第八章對策論齊王策略α|齊王的贏得|田忌策略ββ1（上中下）α2（上下中）α3（中上下）α4（中下上）α5（下中上）α6（下上中）α1（上中下）31111-1α2（上下中）1311-11α3（中上下）1