常見運籌學概念和操作

1、管理科學（運籌學）是對于定量因素有關的管理問題通過應用科學的方法進行輔助管理決策 制定的一門學科。起初用于第二次世界大戰(zhàn)，而推動其發(fā)展的重大因素之一是計算機革命的爆發(fā)。解決問題的一般步驟：1，定義問題和收集數(shù)據(jù)（考慮的問題和達成的目標）構(gòu)建模型（數(shù)學模型）從模型中形成一個對問題進行求解的基于計算機的程序測試模型并在必要時進行修正應用模型分析問題以及提出管理意見幫助實施被管理者采納的小組意見建立模型的重要因素：1，約束條件：數(shù)學模型中對決策變量可能取值進行限制的不等式或等式。2，參數(shù)：數(shù)學模型中的變量。3，目標函數(shù)：是數(shù)學模型中根據(jù)決策變量作出的績效度量的數(shù)學表達式。關于敏感性分析：數(shù)學模型只是

2、問題的一個近似求解，因而敏感性分析是由于估計值發(fā)生偏差時，帶來的 模型變化。數(shù)學模型編入電子表格，這種數(shù)學模型通常成為電子表格模型。線性規(guī)劃【用線性數(shù)學模型表示的活動計劃】的基本概念1，顯示數(shù)據(jù)的單元格稱為數(shù)據(jù)單元格。2，可變單元格包含要做的決策。3，輸出單元格顯示依賴于可變單元格的輸出結(jié)果。4，目標單元格是一種特殊的可變單元格，其包含了對所有可變單元格所作出決策的評估 用電子表格為問題建立數(shù)學模型（線性規(guī)劃模型）過程中要解決的三個問題：1，要做出的決策是什么？（表現(xiàn)的是什么）2，在作出這些決策上有哪些約束條件？（約束是什么）3，這些決策的全部績效測度是什么？（達到的目的是什么）電子表格上的線

3、性規(guī)劃模型的特征：1，需要作出許多活動水平的決策，因此可變單元格被用來顯示這些水平。2，這些活動的水平能夠取滿足許多約束條件的任何值（包括小數(shù)值）3，每個約束條件對活動水平的決策可行值進行了限制，約束條件的左邊往往是一個輸出 單元格，中間是一個數(shù)學符號（=,=等），右邊是數(shù)據(jù)單元格。4，活動水平的決策是以進入目標單元格的一個完全績效測度為基礎的，目標是最大化目 標單元格或是最小化目標單元格，這由績效測度的性質(zhì)決定。5，每個輸出單元格（包括目標單元格）的excel等式可以表達一個SUMPRODUCT函數(shù)， 這里加和的每一項是一個數(shù)據(jù)單元格與一個可變單元格的乘積。特征2與5是區(qū)分線性規(guī)劃模型和其他

4、可變電子表格上建模的數(shù)學模型的關鍵。約束邊界線：即形成一個約束條件所允許的邊界的直線，它通常是由它的方程式確定的，切 對于一含有不等號的約束條件，它的約束邊界方程將不等號換成等號即可。約束邊界線的位 置由它與兩軸相交的交點確定。如3*x+4*y=10。只改變約束條件的右邊會得到平行的約束 邊界線，檢驗（0，0）是否滿足約束條件可以表明位于約束邊界線的哪一邊滿足約束條件。斜截式，斜率?？尚杏颍嚎尚杏騼?nèi)的點是那些符合所有約束條件的解。目標函數(shù)線：是它上面點的都有相同目標函數(shù)值的一條直線。如何有效的建立一個電子表格模型：首先輸入數(shù)據(jù)，先輸入和仔細編排所有數(shù)據(jù)，然后盡量使模型的結(jié)構(gòu)符合數(shù)據(jù)的編排。 可

5、以先建立一個小型表格。組織和清楚的標識數(shù)據(jù)，行列都有表示。每個數(shù)據(jù)輸入唯一的一個單元格，為了方便更改數(shù)據(jù)。公式與數(shù)據(jù)分離。避免在公式中直接使用數(shù)字，這樣可以是表格易于說明，切模型易 于修改。保持簡單化。使用區(qū)域名稱。但也不能濫用。（命名方法，注意事項：不允許使用空格，但可以用 下劃線）使用相對與絕對坐標（它的使用方法$）使用邊框，陰影和顏色來區(qū)分單元格類型在電子表格中顯示整個模型。即要包含整個內(nèi)容，而不要依賴so lver對話框去包含某 些要素。關于四類線性規(guī)劃問題：資源分配問題：資源分配問題是將有限的資源分配到各種活動中去的線性規(guī)劃問題。 這一類問題的共性是在線性規(guī)劃模型中每一個函數(shù)限制為資

6、源限制，并且，每一種資 源都可以表現(xiàn)為如下形式，使用的資源數(shù)量=可用的資源數(shù)量。廣義上的資源角度來說：使用的數(shù)量=可獲得的數(shù)量解決資源分配問題的第一步是明確活動和資源，對每一個活動，需要作出活動數(shù)量的 決策，也就是要確定活動水平。一下三類數(shù)據(jù)是必須的：每種資源的可供量；每一種 活動所需要的各種資源的數(shù)量，對于每一種資源與活動的組合，單位活動所消耗的資 源量必須首先估計出來；每一種活動對總的績效測度的單位貢獻。它包含了生產(chǎn)分配和財務問題。它的一般建模步驟：首先確認問題的活動類型，問題的決策也就是決定各種活動的水平明確合適的績效測度以求解問題估計每一種活動對于總績效測度的單位貢獻明確分配給各種活動

7、的有限資源對于每一種資源，明確可獲得的數(shù)量以及各種活動的單位使用量將數(shù)據(jù)輸入電子表格，可以在活動欄與可獲得的資源欄之間要保留兩個空欄的參數(shù)表 指定可變單元格來顯示活動水平的決策量在第六步中產(chǎn)生的兩個空欄，左邊一欄做為輸出單元格的總數(shù)欄，右邊一欄為所有的 資源輸入=符號，使用SUMPRODUCT函數(shù)指派目標單元格以顯示總的績效測度，也使用SUMPRODUCT函數(shù)成本收益平衡問題：成本收益平衡問題是一類線性規(guī)劃問題，在這類問題中，通過選 擇各種活動水平的組合，從而以最小的成本來實現(xiàn)最低可接受的各種收益水平。這類 問題的共性是，所有的函數(shù)約束條件均為收益約束，并具有如下的形式，完成的水平= 可接受的

8、最低水平它也需要三種數(shù)據(jù)：每種收益的最低可接受水平；每一種活動對一種收益的貢獻；每 種活動的單位成本。解決任何成本收益平衡問題的第一步是明確活動和收益。線性規(guī)劃建模的類型并不是由應用決定，而是由作出決策的各種限制條件決定的。其他的建模步驟跟資源問題大致相同。網(wǎng)絡配送問題：它出現(xiàn)了一種新的限制條件一一確定需求的約束，確定的需求限制在 網(wǎng)絡配送中占有重要的地位，且必須確定需求以及相應的確定需求的約束條件。首先必須明確這一網(wǎng)絡配送問題的活動與需求，線性規(guī)劃中確定需求的限制是以“=” 表示的等式，每種這樣的限制都可以解釋為一定數(shù)量的確定的需求：提供的數(shù)量=需 求的數(shù)量，純網(wǎng)絡配送問題的特點之一就是其建

9、模的主要函數(shù)約束是確定需求的約 束。但是，其他類型的線性規(guī)劃問題也可能包含這一類的約束條件。4.混合型問題類型形式解釋主要用于資源問題LHS=RHS對于特定的資源使用的數(shù)量 =RHS對于特定的收獲達到的水平 =最低可接受水平成本收益平衡問題混合問題確定要求約束LHS=RHS對于一些數(shù)量提供的數(shù)量=需求的數(shù)量網(wǎng)絡配送問題混合問題LHS=左式（一個 SUMPRODUCT 函數(shù)）RHS=右式（常數(shù)）混合線性規(guī)劃問題建模過程的總結(jié)：【首先明確問題的各種活動，活動的水平即為要做出的決策】從管理的角度，為問題的解確定一個總績效測度；對于每一種活動，估計活動對總技校測度的單位貢獻；確定分配給各種活動的有限資

10、源，明確每一種資源可獲得的數(shù)量以及活動的單位使用量； 確定各種活動的可獲得的收益，并明確各種收益管理層所制定的最低可接受水平以及每種活 動的單位收益貢獻；判別確定的需要，對于一些類型的數(shù)量，提供的數(shù)量必須等于需求的數(shù)量，明確每一種要求 的數(shù)量，以及每一活動對該要丟的數(shù)量的單位貢獻；將36步所收集的數(shù)據(jù)輸入到電子表格的數(shù)據(jù)單元格中；指明可變單元格一顯示活動水平的各項決策；使用輸出單元格來說明資源，收益以及確定需求的約束；指定目標單元格來顯示總的績效測度。檢驗模型的錯誤與遺漏的過程就是模型的確認。模型的擴展就叫模型的變異。如何會出現(xiàn)WHAT-IF問題：如果模型的參數(shù)的估計有誤怎么辦；如果作出不同的

11、似是而非的假設，問題的結(jié)果將會如何變化；如果管理方面所要求的某一選項沒有被考慮在內(nèi)，會產(chǎn)生怎么樣的結(jié)果。線性規(guī)劃的目的：對未來進行各種各樣的假想，在這些假設下，測試各種管理方法可能產(chǎn)生 的結(jié)果，而通過對各種各樣結(jié)果的深入分析來知道管理者作出最終的決定。WHAT-IF的基本作用：線性規(guī)劃模型的許多參數(shù)在建模時是難精確的，只能是對一些數(shù)據(jù)的估計，通過 WHAT-IF分析可以表明，系數(shù)估計值必須精確到怎么樣的程度，才能避免得出 錯誤的最優(yōu)解，而且，可以找出哪些系數(shù)是需要重新精確定義的靈敏度參數(shù)。如果在研究結(jié)果之后，問題的條件發(fā)生了變化，通過WHAT-IF分析，即使不求 解，也可以表明模型參數(shù)的變化是

12、否會改變最優(yōu)解。（通常稱靈敏度分析；如果 模型的主要參數(shù)是管理層的政策決策而不是管理層所無法控制的外部數(shù)據(jù)，就可 以用這種前攝性分析方法）當模型特定的參數(shù)反映管理政策決策時，WHAT-IF分析可以表明改變這些決策 對結(jié)果的影響，從而有效指導管理者作出最終的決定。SOLVER TABLE可以解決一系列數(shù)據(jù)單元格的數(shù)值改變的問題；當在SOLVER TABLE的 第一欄里填入相關數(shù)據(jù)單元格的試驗值時，請將第一行置空，以便在其他欄第一行的單元格 內(nèi)填入可變單元格和（或）相應輸出單元格的公式。【具體練習】能使最優(yōu)解保持在相同的范圍稱為保持最優(yōu)解的允許變化范圍，簡稱最優(yōu)域。目標函數(shù)中系數(shù)的允許變化范圍是指

13、系數(shù)在次范圍內(nèi)變化最優(yōu)解保持不變。EXCELSOLVER得出的靈敏度報告顯示了目標函數(shù)允許的變化范圍。如果參數(shù)的微小變動能引起最優(yōu)解的變化，就認為它是敏感參數(shù)。二維SOLVER TABLE的使用，雖然他只能顯示一組試算值的變化給單元格帶來的影響， 但是使用符號“&”可以在表格中的一個單元格內(nèi)可以顯示多個單元格。任何需要在公式中顯示的文本必須在兩側(cè)加以引號（比如“（” &A22& ，” &B12& “）”） &符號這此表示連接。多系數(shù)變化可以用一下三種方法來做，在電子表格上作相應的變動；使用二維SOLVER表 格；應用百分百法則。目標函數(shù)系數(shù)同時變化的百分之百法則：如果目標函數(shù)的系數(shù)同時變動，計

14、算出每一系數(shù) 變動量占該系數(shù)允許變化范圍允許變動量的百分比，而后，將各個系數(shù)的變動百分比相加， 如果所得的和不超過100%，最優(yōu)解不會改變，如果超過100%，則不能確定最優(yōu)解是否改 變。注：1.百分百法則可以用于確定在保持最優(yōu)解不變的條件下，目標函數(shù)系數(shù)的變動范圍當模型中有大量的決策變量時，用電子表格系統(tǒng)的測試目標函數(shù)一部分或全部系數(shù)的 同步變動是相當不實際的，因為即使有代表性的變動組合數(shù)也是大量的。SOLVER表格只能 用來檢驗一次最多兩個系數(shù)的變化。但是，百分百法則通過將允許的增加或減少值在各個系 數(shù)之間分攤，從而可以直接顯示出每個系數(shù)的允許變動量。在線性規(guī)劃的研究結(jié)束后，也可以節(jié)省修正模

15、型的時間。影子價格：在給定線性規(guī)劃模型的最優(yōu)解和目標函數(shù)相應值的條件下，影子價格就是約束常 數(shù)增加微小的量1，使得目標函數(shù)值增加的量，一般約束條件的影子價格顯示了約束條件右 端值的改變給目標單元格帶來的增長率。它在右端值在允許變化范圍內(nèi)保持正確。函數(shù)約束的右端值允許變化范圍就是保持約束條件的影子價格有效時右端值變化的范圍。考慮約束條件變化帶來的影響時，常用三種方法：運用靈敏度報告只能用來分析左端值的 變化，而用電子表格和SOLVER表格分析左端系數(shù)和右端值的變化時過程是一樣的。而著 重分析右端值。通過在一個單元格內(nèi)輸入有關另一個單元格的公式，一維SOLVER表格可以解決相關的 單元格的試算值。

16、雖然一維SOLVER表格只能用來研究一個數(shù)據(jù)格的試算值變化的情況， 但是可以通過上述方法來解決二維問題。約束右端值同時變化的百分百法則：同時改變幾個或所有函數(shù)約束的約束右端值，如果這 些變化的幅度不大，那么可以用影子價格預測變動產(chǎn)生的影響。為了判別這些變動的幅度是 否允許，計算每一變動占可行域所允許的增加值或減少值的百分比，如果所有的百分比之和 不超過100%，那么，影子價格還是有效的，如果所有的百分比之和超過100%，那就無法 確定影子價格是否有效了。運輸問題和指派問題都屬于網(wǎng)絡配送問題。運輸問題的基本概念：運輸問題最關心的是以最低的總配送成本把出發(fā)地的任何產(chǎn)品運送到每一個目的地；需求假設：

17、每一個出發(fā)地都有一個固定的供應量，所有的供應量都必須配送到目的地， 與之類似，每一個目的地都有一個固定的需求量，整個需求量都必須有出發(fā)地滿足?？尚刑卣鹘猓寒斍覂H當供應量的總和等于需求量的總和時，運輸問題才有可行解。成本假設：從任何一個出發(fā)地到任何一個目的地的貨物配送成本和所配送的數(shù)量成線性 比例關系，因此這個成本就等于配送的單位乘以所配送的數(shù)量。模型：如果問題可以完全描述成以參數(shù)形式，明確出發(fā)地，目的地，供應量，需求量和 單位成本，符合需求假設和成本假設，那么這個問題（不管涉不涉及運輸）都適用于運輸問 題模型，最終目的都是要使配送的總成本最小。注：供應量，需求量和單位成本提供了運輸問題所需要的

18、一切數(shù)據(jù)。運輸問題的電子表格模型用兩張分開的表格顯示單位成本數(shù)據(jù)和可變單元格，在兩張表中使 用相同的行號和列號。在可變單元格旁邊表明了的約束條件。整數(shù)解的性質(zhì)：只要它的供應量和需求量都是整數(shù)，任何有可行解的運輸問題必然有所有 決策變量都是整數(shù)的最優(yōu)解。因此，沒有必要加上所有變量都是整數(shù)的約束條件。我們在execl中用到的SOLVER來解決運輸問題的另一種方法是單純形法，其中有運輸單純 形法和網(wǎng)絡單純形法，它們的運行速度很快，而網(wǎng)絡的越來越有競爭力。運輸問題變體類型：供應總量超過了需求總量。于是每一個供應量代表了從這個出發(fā)地中配送出去的 最大數(shù)量（而不是一個固定的值）需求總量超過了供應總量。于是

19、每一個需求量代表了在這個目的地中接收到的最 大數(shù)量（而不是一個固定的值）一個目的地同時存在著最小需求和最大需求，于是所有在這兩個數(shù)值之間的數(shù)量 都是可以接受的在配送中不能使用特定的出發(fā)地一一目的地組合目標是使與配送數(shù)量有關的總利潤最大而不是最小此上問題均有一般的解法，以后討論。指派問題一般模型的假設：被指派者的數(shù)量和任務的數(shù)量是相同的每一個被指派者只完成一項任務每一項任務只能由一個被指派者完成每一個被指派者和每一項任務的組合都會有一個相關的成本問題的目標是要確定怎樣進行指派才能使得總成本達到最小 網(wǎng)絡表示法提供了另一種表示指派問題的方法 指派問題的變形：有一些被指派者并不能進行某一項任務雖然每

20、一個被指派者完成一項任務，但是任務比被指派者多。所以其中某些任務并 沒有得到執(zhí)行雖然每一項任務只由一個被指派者完成，但是這里被指派者比要完成的任務數(shù)量多。 所以，其中有一些被指派者沒有指派到任務每一個被指派者可以同時被指派給多個任務每一項任務都可以由多個被指派者完成解決指派問題時有時會用到一種更為快捷的方法：匈牙利方法。網(wǎng)絡最優(yōu)化問題的求解，許多網(wǎng)絡最優(yōu)化問題實質(zhì)上是線性規(guī)劃問題的特殊類型，主要是構(gòu) 建出一個模型，即有弧的模型。（最重要的即為畫出網(wǎng)絡模型）最小費用流問題是線性規(guī)劃問題的特殊類型，也叫做網(wǎng)絡配送問題。它的目標是通過配送網(wǎng) 絡的運輸成本最小?？梢杂镁W(wǎng)絡圖完整的表示最小成本問題。基本

21、術(shù)語：所有最小費用流問題都是用帶有通過其中的流的網(wǎng)絡表示的網(wǎng)絡中的圓圈被稱為節(jié)點如果節(jié)點產(chǎn)生的凈流量（流出減去流入）是一個確定的正數(shù)的話，這個節(jié)點就是供 應點如果節(jié)點產(chǎn)生的凈流量是一個確定的負數(shù)的話，那么這個節(jié)點就是需求點如果節(jié)點產(chǎn)生的凈流量恒為零，那么這個節(jié)點就稱為轉(zhuǎn)運點，我們把流出節(jié)點的量 等于流入節(jié)點的量稱為流量守恒網(wǎng)絡中的箭頭稱為弧允許通過某一條弧的最大流量稱為該弧的容量最小費用流問題的假設：至少一個節(jié)點是供應點至少一個節(jié)點是需求點所有剩下的節(jié)點都是轉(zhuǎn)運點通過弧的流只允許沿著箭頭的方向流動，通過弧的最大流量取決于該弧的容量（如 果流是雙向的話，則需要用一對箭頭指向相反方向的弧來表示）網(wǎng)

22、絡中有足夠的弧提供足夠的容量，使得所有在供應點中產(chǎn)生的流都能夠到達需求 點在流的單位成本已知的前提下，通過每一條弧的流的成本和流量成正比最小費用流問題的目標是在滿足給定需求的條件下，使得通過網(wǎng)絡供應的總成本最 下這類問題的解需要確定通過每一條弧的流有多大。具有可行解的特征：在以上的假設下，當且僅當供應點所提供的流量總和等于需求點所需要 的流量總和時，最小費用流問題有可行解。具有整數(shù)解的特征：只要其所有的供應，需求和弧的容量都是整數(shù)值，那么任何最小費用流 問題的可行解就一定有所有流量都是整數(shù)的最優(yōu)解。容量限制在任何有流量限制的弧的最小費用流問題中都存在。最小費用流問題的任一個節(jié)點都需要凈流量限制

23、Sumif的使用方法這里不加介紹。在這里也有網(wǎng)絡單純形法，它可以用來解決那些對于單純形法來說太大而無法解決的大型問 題。最小費用流問題最重要的應用可能是在配送網(wǎng)絡的運營上。幾類典型的最小費用流問題的應用：應用的類型供應點轉(zhuǎn)運點需求點配送網(wǎng)絡的運作貨源中間存儲設備客戶固體廢棄物管理固體廢棄物源處理設備固體廢棄物掩埋地供應網(wǎng)絡的運作供應商中間倉庫加工設備工廠協(xié)調(diào)產(chǎn)品組合工廠某一特定產(chǎn)品的生產(chǎn)某一特定產(chǎn)品的市場現(xiàn)金流管理某一特定時間的現(xiàn)金 來源短期投資期權(quán)在特定時間對現(xiàn)金的 需求最小費用流問題的特殊類型：運輸問題，沒有轉(zhuǎn)運點和弧的容量限制指派問題，供應量為一的供應點，每項任務都是需求量為一的需求點轉(zhuǎn)

24、運問題，在出發(fā)點與目的地之間會有轉(zhuǎn)運點，除此斗魚運輸問題一樣最大流問題最短路問題對于此些做法，可以用網(wǎng)絡單純形法，它可以跟快捷的進行計算求解。對于最大流問題，它的目標是使目標單元格最大流量最大化。最大流問題的假設：網(wǎng)絡中所有流起源于一個節(jié)點，這個節(jié)點叫做源，所有的流終止于另一個節(jié)點，這個 節(jié)點叫做收點其余所有的節(jié)點叫做轉(zhuǎn)運點通過每一個弧的流只允許沿著弧的箭頭所指方向流動。由源出發(fā)的所有的弧背向源， 而所有終于收點的弧都指向收點。最大流問題的目標是使得從源到收點的總流量最大。這個流量的大小可以用兩種等價 的方法來衡量，分別叫做從源點出發(fā)的流量和進入收點的流量最大流問題與最小費用流問題的區(qū)別：供應點的供應量和需求點的需求量都是固定的，而源和收點則不同最小費用流問題中，不管是供應點的數(shù)量還是需求點的數(shù)量都可能多于一個，而在最 大流問題中只能有一個源和收點（若有多個，可用其變形）注：當網(wǎng)絡中實際行進在多個節(jié)點結(jié)束時，我們在每一個這樣的節(jié)點和虛擬目標地之間插入 一個長度為0的弧，從而使得網(wǎng)絡中仍然只有一個目標地 最大流的一些實際應用：通過配送網(wǎng)絡的流量最大通