1、管理運籌學管理運籌學第一章第一章 緒論緒論第一章緒論緒論 運籌學（運籌學（Operational Research） 運籌學直譯為“運作研究”，是應用分析、試驗、量化的方法，對經濟管理系統中的人力、物力、財力等資源進行統籌安排，為決策者提供有依據的最優(yōu)方案，以實現最有效的管理。運籌學運籌學 管理運籌學管理運籌學 管理科學管理科學第一章緒論緒論 運籌學的產生和發(fā)展運籌學的產生和發(fā)展 我國古代有很多關于運籌學思想方法的典故。 齊王賽馬 丁渭修皇宮 沈括運軍糧第一章緒論緒論 運籌學的產生和發(fā)展運籌學的產生和發(fā)展 運籌學作為一門新興的學科是在第二次世界大戰(zhàn)期間才出現的。 第一章緒論緒論 運籌學的產生和

2、發(fā)展運籌學的產生和發(fā)展 有效保護從美國到英國的商船補給運輸線； 有效對付德國空軍對英倫三島的大轟炸； 英美成立了“運作研究”（Operation Research）小組，解決了許多復雜的戰(zhàn)略和戰(zhàn)術問題。第一章緒論緒論 運籌學的產生和發(fā)展運籌學的產生和發(fā)展 二戰(zhàn)以后，運籌學的發(fā)展： 1、運籌學方法論快速發(fā)展。其里程碑是: 1947年由丹捷格（George Dantzig）提出的求解線性規(guī)劃問題的單純形法單純形法。第一章緒論緒論 運籌學的產生和發(fā)展運籌學的產生和發(fā)展 2、電子計算機技術迅猛發(fā)展和廣泛應用，使應用運籌學方法解決實際問題可行。 決策、定量分析與管理運籌學決策、定量分析與管理運籌學運籌學

3、的分支運籌學的分支運籌學在工商管理中的應用運籌學在工商管理中的應用學習管理運籌學必須使用相應的計算機學習管理運籌學必須使用相應的計算機軟件，必須注重學以致用的原則軟件，必須注重學以致用的原則本章內容本章內容1234 1決策、定量分析與管理運籌學決策、定量分析與管理運籌學決策過程（解決問題的過程）決策過程（解決問題的過程）（1） 認清問題。（2） 找出一些可供選擇的方案。（3） 確定目標或評估方案的標準。（4） 評估各個方案：解的檢驗、靈敏性分析等。（5） 選出一個最優(yōu)的方案：決策。（6） 執(zhí)行此方案：回到實踐中。（7） 進行后評估：考察問題是否得到圓滿解決。形成問題分析問題：定性分析與定量分析

4、，構成決策決策、定量分析與管理運籌學決策、定量分析與管理運籌學運籌學的分支運籌學的分支運籌學在工商管理中的應用運籌學在工商管理中的應用學習管理運籌學必須使用相應的計算機學習管理運籌學必須使用相應的計算機軟件，必須注重學以致用的原則軟件，必須注重學以致用的原則本章內容本章內容1234 2運籌學的分支運籌學的分支線性規(guī)劃整數線性規(guī)劃動態(tài)規(guī)劃圖與網絡模型存儲論排隊論排序與統籌方法決策分析對策論預測目標規(guī)劃 此外，還有非線性規(guī)劃、多目標規(guī)劃、隨機規(guī)劃、模糊規(guī)劃等。決策、定量分析與管理運籌學決策、定量分析與管理運籌學運籌學的分支運籌學的分支運籌學在工商管理中的應用運籌學在工商管理中的應用學習管理運籌學必

5、須使用相應的計算機學習管理運籌學必須使用相應的計算機軟件，必須注重學以致用的原則軟件，必須注重學以致用的原則本章內容本章內容1234 3運籌學在工商管理中的應用運籌學在工商管理中的應用生產計劃生產計劃庫存管理庫存管理運輸問題運輸問題人事管理人事管理市場營銷市場營銷財務和會計財務和會計 3運籌學在工商管理中的應用運籌學在工商管理中的應用 我國1957年開始成功應用運籌學于工商管理。 運輸部門“圖上作業(yè)法” 管梅谷“中國郵路問題” 華羅庚華羅庚推廣優(yōu)選法和統籌法 3運籌學在工商管理中的應用運籌學在工商管理中的應用 國際運籌與管理科學協會（INFORMS）及其下屬的管理科學實踐學會（College

6、for the Practice of the Management Sciences）頒發(fā)弗蘭茨厄德曼（Franz Edelman）獎。 獎勵運籌學在管理中的應用，該獎每年一次，有六位獲獎。 3運籌學在工商管理中的應用運籌學在工商管理中的應用 自 1972 年至 2014 年，Franz Edelman 獎項入圍項目獲利累計超過 2130 億美元。組織組織應用應用效果效果卡爾森酒店卡爾森酒店集團集團CRHG需求管理和價格優(yōu)化收入2-4%年增長率，增加1600萬美元惠普惠普商業(yè)轉型中的決策分析2002-2012年電子商務業(yè)務翻3番戴爾戴爾Dell價值鏈渠道轉型系統解決方案和服務占收入1/3和利

7、潤的50% 3運籌學在工商管理中的應用運籌學在工商管理中的應用組織組織應用應用效果效果配對捐贈聯盟配對捐贈聯盟優(yōu)化匹配拯救了220個生命美國能源局美國能源局水力發(fā)電量優(yōu)化根據風電和太陽能電源數量調整水力發(fā)電量澳大利亞國家寬澳大利亞國家寬帶網絡帶網絡優(yōu)化光纖網絡設計節(jié)約3.75億美元，模塊設計工期從145天變?yōu)?6天寶鋼集團寶鋼集團優(yōu)化算法和決策支持系統（DSSs）產生7681萬美元效益，提升16.8%的運營能力，CO2排放量每年下降58.5萬噸決策、定量分析與管理運籌學決策、定量分析與管理運籌學運籌學的分支運籌學的分支運籌學在工商管理中的應用運籌學在工商管理中的應用學習管理運籌學必須使用相應的

8、計算機學習管理運籌學必須使用相應的計算機軟件，必須注重學以致用的原則軟件，必須注重學以致用的原則本章內容本章內容1234 4學習管理運籌學必須使用相應的計算機學習管理運籌學必須使用相應的計算機軟件，必須注重學以致用的原則軟件，必須注重學以致用的原則 一位剛剛畢業(yè)的MBA學員，針對公司的設備分銷工作，建立了一個存儲模型，為公司節(jié)省成本35.15萬元。 4學習管理運籌學必須使用相應的計算機學習管理運籌學必須使用相應的計算機軟件，必須注重學以致用的原則軟件，必須注重學以致用的原則第一，對運籌學的理解停留在理論而非應用層面； 第二，認為運籌學方法太復雜繁瑣，不易用，忽視了計算機在運籌學的應用。 他的主

9、管經理也學過運籌學卻不應用，為什么？值得關注的是：責任在誰？在老師，在教學。 4學習管理運籌學必須使用相應的計算機學習管理運籌學必須使用相應的計算機軟件，必須注重學以致用的原則軟件，必須注重學以致用的原則這給我們管理運籌學教學的啟示： 務必把管理運籌學的教學重點放在應用上，學以致用，充分應用計算機的運籌學軟件解決實際問題。 4學習管理運籌學必須使用相應的計算機學習管理運籌學必須使用相應的計算機軟件，必須注重學以致用的原則軟件，必須注重學以致用的原則 例：有人要從北京去烏魯木齊。 在一百多年以前，我們應該告訴他 如何選購馬匹、馬車，挑選馬夫和保鏢 如何配備糧草、銀兩、衣物 如何根據天氣、地理條件

10、和社會諸因素來確定行車路線和行程 教學務必緊密跟蹤現代科技發(fā)展。教學務必緊密跟蹤現代科技發(fā)展。 4學習管理運籌學必須使用相應的計算機學習管理運籌學必須使用相應的計算機軟件，必須注重學以致用的原則軟件，必須注重學以致用的原則 但是現在，我們只需要告訴他如何去北京機場，提前多少時間如何訂機票著陸后如何領取行李出機場后如何到達目的地 沒有必要攻讀空氣動力學、噴氣發(fā)動機設計和制造、飛行器駕駛手冊等。 4學習管理運籌學必須使用相應的計算機學習管理運籌學必須使用相應的計算機軟件，必須注重學以致用的原則軟件，必須注重學以致用的原則與管理運籌學相關的最重要的現代科技:計算機技術信息技術軟件技術 4學習管理運籌

11、學必須使用相應的計算機學習管理運籌學必須使用相應的計算機軟件，必須注重學以致用的原則軟件，必須注重學以致用的原則 管理運籌學教材附有運籌學教學軟件。謝謝 謝！謝！管理運籌學第二章第二章 線性規(guī)劃圖解法線性規(guī)劃圖解法第二章線性規(guī)劃的圖解法線性規(guī)劃的圖解法 線性規(guī)劃是運籌學一個重要分支管理上的典型應用：典型線性規(guī)劃應用典型線性規(guī)劃應用應用場景應用場景合理利用線材問題用料最少配料問題獲利最大投資問題投資回報最大的方案產品生產計劃合理利用人力、物力、財力等使獲利最大勞動力安排用最少的勞動力滿足需要運輸問題總運費最少第二章線性規(guī)劃的圖解法線性規(guī)劃的圖解法線性規(guī)劃的組成：線性規(guī)劃的組成1目標函數：MIN/

12、MAX2約束條件：限制條件3決策變量：可控因素線性規(guī)劃問題的提出線性規(guī)劃的圖解法圖解法的靈敏度分析本章內容本章內容123 1線性規(guī)劃問題的提出線性規(guī)劃問題的提出例1.1.某工廠在計劃期內要安排、兩種產品的生產，生產單位產品所需的設備臺時及 A、B 兩種原材料的消耗以及資源的限制，如下表所示。問：工廠應分別生產多少單位、產品才能使工廠獲利最多？資源資源產品產品產品產品資源限制資源限制設備11300臺時原料A21400kg原料B01250kg單位產品獲利（元）50100 1線性規(guī)劃問題的提出線性規(guī)劃問題的提出問：工廠應分別生產多少單位、產品才能使工廠獲利最多？約束條件：資源資源產品產品 產品產品資

13、源限資源限制制設備11300臺時原料A21400kg原料B01250kg單位產品獲利（元）50100 1線性規(guī)劃問題的提出線性規(guī)劃問題的提出建模過程步驟步驟建立線性規(guī)劃模型建立線性規(guī)劃模型1在什么條件下追求什么目標2定義決策變量表，每組 代表一個方案3用決策變量的線性函數形式寫出目標函數4必須遵循的約束條件 1線性規(guī)劃問題的提出線性規(guī)劃問題的提出問題的提出圖解法圖解法的靈敏度分析本章內容本章內容123 2圖解法圖解法兩個決策變量的線性問題，可以用圖解法求解。 2圖解法圖解法每個約束條件都代表一個半平面。 2圖解法圖解法每個約束條件都代表一個半平面。 2圖解法圖解法把五個限制條件對應的五個半平面

14、合并成一個圖，各約束條件的公共部分即為可行域。 2圖解法圖解法得到最優(yōu)解：B:=50,=250 最優(yōu)目標值 z=27500 2圖解法圖解法重要結論 解的情況解的情況場景場景有最優(yōu)解一定有一個可行域的頂點，對應一個最優(yōu)點無窮多個最優(yōu)解若將例一中的目標函數變?yōu)閦=50 x1+50 x2，則線段BC上的所有點都代表最優(yōu)解無可行解可行域為空域，不存在滿足約束條件的解無界解可行域的范圍延伸到無窮遠，目標函數值可以無窮大或無窮小 2圖解法圖解法重要結論無界解（無最優(yōu)解的情況）目標函數：max z = x1 + x2 ；約束條件：x1 - x2 1 -3 x1 +2 x2 6 x1 0， x2 0該問題可行

15、域無界，目標函數值無窮大，無界解，即無最優(yōu)解。 2圖解法圖解法例2 某公司由于生產需要，共需A,B兩種原料至少350噸（A，B有一定替代性）限制條件具體如下：求目標函數最小化的線性規(guī)劃問題試問在滿足生產需要的前提下，在公司加工能力的范圍內，如何購買 A，B 兩種原料，使得購進成本最低？資源需求資源需求加工時間加工時間（小時（小時/噸）噸）成本成本（萬元（萬元/噸）噸）A125噸22B無限制13總資源需求（A+B）需求350噸時間限制（小時）600 2圖解法圖解法得 B 點坐標（250，100）為最優(yōu)解建立模型：問題的提出圖解法圖解法的靈敏度分析本章內容本章內容123 3圖解法的靈敏度分析圖解法

16、的靈敏度分析 3圖解法的靈敏度分析圖解法的靈敏度分析 3圖解法的靈敏度分析圖解法的靈敏度分析非標準形式的線性規(guī)劃問題，通過變換轉化為標準形式。標準形式的線性規(guī)劃的四大特點線性規(guī)劃標準形式的四個特點線性規(guī)劃標準形式的四個特點1目標最大化2約束為等式3決策變量均非負4右端項非負 3圖解法的靈敏度分析圖解法的靈敏度分析極小化目標函數的標準化問題注意注意：以上兩個問題的最優(yōu)解相同，但最優(yōu)值相差一個負號，即min f = max z 3圖解法的靈敏度分析圖解法的靈敏度分析約束條件不是等式的標準化問題引入一個非負變量s，令其等于等式左右兩邊的差值 3圖解法的靈敏度分析圖解法的靈敏度分析 3圖解法的靈敏度分

17、析圖解法的靈敏度分析 3圖解法的靈敏度分析圖解法的靈敏度分析通過標準化得： 3圖解法的靈敏度分析圖解法的靈敏度分析* 變量無符號限制的標準化問題 3圖解法的靈敏度分析圖解法的靈敏度分析考慮例1 的情況，目標函數 z = 50 x1 + 100 x2 斜線在右圖兩條紅線之間,-1 （-1/2） 0最優(yōu)解不變，仍為B. 3圖解法的靈敏度分析圖解法的靈敏度分析等值線斜率在-1 （-1/2） 0 范圍內則最優(yōu)值不變。 3圖解法的靈敏度分析圖解法的靈敏度分析 3圖解法的靈敏度分析圖解法的靈敏度分析 3圖解法的靈敏度分析圖解法的靈敏度分析在一定范圍內，當約束條件中常數項增加 1 個單位時，（1）對偶價格大

18、于 0，則其最優(yōu)目標函數值得到改善，求Max則函數值增大，求min則函數值變小；（2）對偶價格小于 0，則其最優(yōu)目標函數值受到影響（變壞），求Max則函數值變小，求min則函數值增大；（3）對偶價格等于 0，則其最優(yōu)目標函數值不變。對偶價格謝謝 謝！謝！管理運籌學第三章線性規(guī)劃問題的計算機求解第三章線性規(guī)劃問題的計算機求解第三章線性規(guī)劃問題的計算機求解隨書軟件為“管理運籌學”3.0 版（Windows版），是“管理運籌學”2.5 版（Windows版）的升級版。它包括15 個子模塊。 “管理運籌學”軟件的操作方法“管理運籌學”軟件的輸出分析本章內容本章內容12 1“管理運籌學管理運籌學”軟件的

19、操作方法軟件的操作方法第一步：雙擊“管理運籌學v3.0”在桌面上的快捷方式下面演示如何用“管理運籌學”軟件包來解決第二章例一的線性規(guī)劃問題 1“管理運籌學管理運籌學”軟件的操作方法軟件的操作方法1“管理運籌學管理運籌學”軟件的操作方法軟件的操作方法第二步：在主菜單中選擇線性規(guī)劃模型1“管理運籌學管理運籌學”軟件的操作方法軟件的操作方法第三步：在點擊“新建”按鈕以后，輸入變量個數，約束條件個數，目標函數選擇max(min)，點擊確定1“管理運籌學管理運籌學”軟件的操作方法軟件的操作方法1“管理運籌學管理運籌學”軟件的操作方法軟件的操作方法第五步：點擊解決1“管理運籌學管理運籌學”軟件的操作方法軟

20、件的操作方法第六步：點擊開始1“管理運籌學管理運籌學”軟件的操作方法軟件的操作方法第七步：點擊下一步1“管理運籌學管理運籌學”軟件的操作方法軟件的操作方法第八步：點擊下一步 1“管理運籌學管理運籌學”軟件的操作方法軟件的操作方法第九步：關閉計算過程“管理運籌學”軟件的輸出分析“管理運籌學”軟件的操作方法本章內容本章內容21 2“管理運籌學管理運籌學”軟件的輸出信息分析軟件的輸出信息分析分析軟件輸出的信息解釋解釋變量相差值：為了使決策變量為正值，相應的決策變量的目標系數需要改進的數量約束松弛（剩余變量）：資源剩余量（超過量）。如果為零, 表示與之相對應的資源正好全部用完。對偶價格：對應的資源每增

21、加一個單位，最優(yōu)值將變化多少個單位目標函數系數范圍最優(yōu)解不變的情況下，目標函數的決策變量系數的變化范圍當前值：當前的目標函數的系數取值 2“管理運籌學管理運籌學”軟件的輸出信息分析軟件的輸出信息分析分析軟件輸出的信息靈敏度分析都是在只有一個系數變化的基礎上得出的解釋解釋常數項范圍上限值和下限值：當約束條件的右端常量在此范圍內變化時，與其對應的約束條件的對偶價格不變當前值：約束條件的右端常量現在的取值。 2“管理運籌學管理運籌學”軟件的輸出信息分析軟件的輸出信息分析百分之一百法則：對于所有變化的目標函數決策變量系數（約束條件右端常數值），當其所有允許增加的百分比與允許減少的百分比之和不超過100

22、%時，最優(yōu)解不變（對偶價格不變）當有多個系數變化，怎樣進行靈敏度分析？ 2“管理運籌學管理運籌學”軟件的輸出信息分析軟件的輸出信息分析目標函數系數的百分之一百法則約束條件中常數項的百分之一百法則 2“管理運籌學管理運籌學”軟件的輸出信息分析軟件的輸出信息分析在使用百分之一百法則進行靈敏度分析時，要注意以下幾方面注意事項注意事項1當允許增加量（允許減少量）為無窮大時，則對任意增加量（減少量），其允許增加（減少）百分比均看作零2百分之一百法則是充分條件，但非必要條件；也就是說超過 100%最優(yōu)解或對偶價格并不一定變化。3百分之一百法則不能用于目標函數決策變量系數和約束條件右邊常數值同時變化的情況。

23、這種情況下，只能重新求解 2“管理運籌學管理運籌學”軟件的輸出信息分析軟件的輸出信息分析用“管理運籌學”軟件來分析第二章的例2當購進原料A 250t，原料B 100t時購進成本最低為800萬元。 2“管理運籌學管理運籌學”軟件的輸出信息分析軟件的輸出信息分析解釋解釋松弛/剩余變量約束條件2的值為125，表示對原料A多了125，即對A的剩余變量值為125，原料A用了250。對偶價格約束條件1的對偶價格為-4，表示如果采購量再增加1噸，那么總的成本要增加4萬元。由800萬元增加到804萬元。約束條件3的對偶價格為1萬元，即如果把加工時數從600小時增加到601小時，則總成本將得到改進，由800萬元

24、減少到799萬元常數項范圍約束條件1：常數項在300到475范圍內變化，且其他約束條件不變時，約束條件1的對偶價格不變，仍為-4約束條件2：常數項在負無窮到250范圍內變化，且其他約束條件的常數項不變時，約束條件2的對偶價格不變，仍為0約束條件3：常數項在475到700范圍內變化，且其他約束條件的常數項不變時，約束條件3的對偶價格不變，仍為1。 2“管理運籌學管理運籌學”軟件的輸出信息分析軟件的輸出信息分析影子價格：當約束條件中的常數項增加一個單位時，最優(yōu)目標函數值增加的數量影子價格與對偶價格條件條件影子價格與對偶價格的關系影子價格與對偶價格的關系求目標函數max當約束條件中的常數項增加一個單

25、位時，目標函數值增加的量就為改進的數量，此時影子價格即為對偶價格求目標函數min在求目標函數最小值時，改進的數量即減少的數量，此時影子價格為負的對偶價格 2“管理運籌學管理運籌學”軟件的輸出信息分析軟件的輸出信息分析 管理運籌學”軟件可以解決含有100個變量50個約束方程的線性規(guī)劃問題。 如果想要解決更大的線性規(guī)劃問題，可以使用由芝加哥大學的 L.E.Schrage 開發(fā)的 LINDO計算機軟件包的微型計算機版本 LINDO/PC。注意：謝謝 謝！謝！管理運籌學第四章第四章 線性規(guī)劃在工商線性規(guī)劃在工商 管理中的應用管理中的應用第四章線性規(guī)劃在工商管理中的應用線性規(guī)劃在工商管理中的應用在對線性

26、規(guī)劃的求解及靈敏度分析的基本概念、基本原理有所了解之后，我們來研究線性規(guī)劃在工商管理中的應用，解決工商管理中的實際問題。 人力資源分配的問題生產計劃的問題套裁下料問題配料問題本章內容本章內容1234投資問題5人力資源分配的問題生產計劃的問題套裁下料問題配料問題本章內容本章內容1234投資問題5 例1某晝夜服務的公交線路每天各時間段內所需司機和乘務人員數如下： 1人力資源分配的問題人力資源分配的問題設司機和乘務人員分別在各時間段開始時上班，并連續(xù)工作八小時，問該公交線路應怎樣安排司機和乘務人員，既能滿足工作需要，又使配備司機和乘務人員的人數最少?班次時間所需人數16:00-10:0060210:

27、00-14:0070314:00-18:0060418:00-22:0050522:00-2:002062:00-6:0030 x1 + x6 60（班次1所需人數） 1人力資源分配的問題人力資源分配的問題設 xi 表示第i班次時開始上班的司機和乘務人員人數, 建立如下的數學模型：Min x1 + x2 + x3 + x4 + x5 + x6 x1 + x2 70 x2 + x3 60 x3 + x4 50 x4 + x5 20 x5 + x6 30 x1,x2,x3,x4,x5,x6 0解：目標函數：約束條件：1人力資源分配的問題人力資源分配的問題 例2百貨商場對售貨員的需求如下表。要求售貨

28、員每周工作五天，連續(xù)休息兩天。問：應該如何安排售貨員，滿足工作需要，同時使配備的售貨員人數最少？時間時間所需售貨員人數所需售貨員人數星期一15星期二24星期三25星期四19星期五31星期六28星期日281人力資源分配的問題人力資源分配的問題解：設 xi ( i = 1,2,7)表示星期i開始休息的人數,建立如下的數學模型：目標函數：約束條件：Min x1 + x2 + x3 + x4 + x5 + x6 + x7 x2 + x3 + x4 + x5 + x6 15（星期一所需 售貨員人數）x3 + x4 + x5 + x6 + x7 24x4 + x5 + x6 + x7 + x1 25x5

29、+ x6 + x7 + x1 + x2 19x6 + x7 + x1 + x2 + x3 31x7 + x1 + x2 + x3 + x4 28x1 + x2 + x3 + x4 + x5 28x1,x2,x3,x4,x5,x6,x7 01人力資源分配的問題人力資源分配的問題實際中，服務行業(yè)企業(yè)一周內對人力資源的需求往往像例2所描述的方式變化，而每天各時間段的需求又像例1所描述的那樣變化。我們只要用例1的方法，分別求出周一到周六、周日每天的人員需求，再用例2的方法，即可求出該公司的最小編制。 注意：人力資源分配的問題生產計劃的問題套裁下料問題配料問題本章內容本章內容134投資問題522生產計劃

30、的問題生產計劃的問題 例3公司面臨外包協作、自行生產的問題。甲、乙、丙產品都需要經過鑄造、機加工和裝配三道工序。鑄造工序中甲、乙可外包，亦可自產，丙必須自產，其余工序必須本廠完成。 問：為獲取最大利潤，三種產品各生產多少件？甲、乙的鑄件有多少由本公司鑄造？有多少由外包協作？甲甲乙乙丙丙資源限制資源限制每件鑄造工時每件鑄造工時/小時小時51078000每件機械加工工時每件機械加工工時/小時小時64812000每件裝配工時每件裝配工時/小時小時32210000自行生產鑄件每件成本自行生產鑄件每件成本/元元354外包協作鑄件每件成本外包協作鑄件每件成本/元元56-機械加工每件成本機械加工每件成本/元

31、元213裝配每件成本裝配每件成本/元元322每件產品售價每件產品售價/元元2318162生產計劃的問題生產計劃的問題 設 x1,x2,x3 分別為三道工序都由本公司加工的甲、乙、 丙三種產品的件數，x4 ,x5 分別為由外協鑄造再由本公 司加工和裝配的甲、乙兩種產品的件數。 解：可得到xi，i = 1,2,3,4,5 的利潤分別為 15、10、7、13、9元。求xi 的利潤：利潤 = 售價 - 各成本之和；產品甲全部自制的利潤 =23-(3+2+3)=15；產品甲鑄造外協，其余自制的利潤 =23-(5+2+3)=13；產品乙全部自制的利潤 =18-(5+1+2)=10；產品乙鑄造外協，其余自制

32、的利潤 =18-(6+1+2)=9；產品丙的利潤 =16-(4+3+2)=7；2生產計劃的問題生產計劃的問題通過以上分析,可建立如下的數學模型:目標函數：約束條件：Max 15x1 + 10 x2 + 7x3 + 13x4 + 9x5 5x1 + 10 x2 + 7x3 8000（鑄造工時）6x1 + 4x2 + 8x3 + 6x4 + 4x5 12000 （機械加工工時）3x1 + 2x2 + 2x3 + 3x4 + 2x5 10000 （裝配工時）x1,x2,x3,x4,x5 02生產計劃的問題生產計劃的問題例4機械廠生產、產品，均要經過A、B兩道工序。兩種規(guī)格的設備A1、A2能完成 A

33、工序；三種規(guī)格的設備B1、B2、B3能完成 B 工序?？稍贏、B的任何規(guī)格的設備上加工； 可在任意規(guī)格的A上加工，B工序只能在B1上加工；只能在A2與B2上加工。問：為獲得最大利潤，應如何制定最優(yōu)的產品加工方案？設備設備產品單件工時產品單件工時設備的有效設備的有效臺時臺時滿負荷時的滿負荷時的設備費用設備費用IIIIII2791210000321B1684000250B24117000783B374000200原料（元/件）0.25 0.35 0.50 售價（元/件）1.25 2.00 2.80 2生產計劃的問題生產計劃的問題解：設xijk表示產品 i 在工序 j （工

34、序 A 用 1 表示，工序 B 用 2 表示）的設備 k 上加工的數量，建立如下的數學模型:5x111 + 10 x211 6000 （ 設備 A1 ）7x112 + 9x212 + 12x312 10000 （ 設備 A2 ）6x121 + 8x221 4000 （ 設備 B1 ）4x122 + 11x322 7000 （ 設備 B2 ）7x123 4000 （ 設備 B3 ）x111+ x112- x121- x122- x123 = 0 （產品在A、B工序加工 的數量相等）x211+ x212 - x221 = 0 （產品在A、B工序加工 的數量相等）s.t. x312 - x322 =

35、 0 （產品在A、B工序加工 的數量相等）xijk 0 , i = 1,2,3; j = 1,2; k = 1,2,32生產計劃的問題生產計劃的問題利潤 = （銷售單價-原料單價）* 產品件數之和 -（每臺時的設 備費用*設備實際使用的總臺時數）之和.目標函數為計算利潤最大化，利潤的計算公式為：目標函數：整理得：Max (1.25-0.25)(x111+x112)+(2-0.35) (x211+x212 ) +(2.80-0.5)x312 300/6000(5x111+10 x211)-321/10000(7x112+9x212+12x312)- 250/4000(6x121+8x221)-7

36、83/7000(4x122+11x322)-200/4000(7x123).Max 0.75x111+0.7753x112+1.15x211+1.3611x212+1.9148x312-0.375x121-0.5x221-0.4474x122-1.2304x322-0.35x1232生產計劃的問題生產計劃的問題1. 合并同類項，自行完成；2. 移項問題；3. 變量下標的轉換問題； 把變量設定中兩維和三維下標將為一維； 例： xijk： x111 x1 x112 x2 。 需要注意的問題：人力資源分配的問題生產計劃的問題套裁下料問題配料問題本章內容本章內容1234投資問題53套裁下料問題套裁下料

37、問題 解：列出所有可能下料方案：例5工廠要做100套鋼架，每套用長為2.9 m,2.1 m,1.5 m的圓鋼各一根。已知原料每根長7.4 m，問：應如何下料，可使所用原料最省？方案方案1方案方案2方案方案3方案方案4方案方案5方案方案6方案方案7方案方案82.9m120101002.1m002211301.5m31203104合計/m7.47.37.27.16.66.56.36料頭/m00.10.20.30.80.91.11.43套裁下料問題套裁下料問題設按上述方案下料的原材料根數分別為 x1,x2,x3,x4,x5,x6,x7,x8建立如下的數學模型：目標函數：約束條件：Min x1 + x

38、2 + x3 + x4 + x5 + x6 + x7 + x8 x1 + 2x2 + x4 + x6 100 （2.9m 圓鋼）2x3 + 2x4 + x5 + x6 + 3x7 100 3x1 + x2 + 2x3 + 3x5 + x6 + 4x8 100 x1,x2,x3,x4,x5,x6,x7,x8 03套裁下料問題套裁下料問題用“管理運籌學”軟件計算得出最優(yōu)下料方案：按方案1下料30根；按方案2下料10根；按方案4下料50根。 即 x1=30; x2=10； x3=0； x4=50；x5= x6= x7= x8= 0； 只需90根原材料就可制造出100套鋼架。 注意：建立此類型數學模型

39、時，約束條件用大于等于號優(yōu)于用等于號。3套裁下料問題套裁下料問題 面裁面裁問題如何解決？ 體裁體裁問題又如何解決？3套裁下料問題套裁下料問題零件1 x1：2件 零件2 x2：2件 零件3 x3：3件 零件4 x4：1件 零件5 x5：3件 零件6 x6：2件 零件7 x7：2件 零件8 x8：1件 人力資源分配的問題生產計劃的問題套裁下料問題配料問題本章內容本章內容1234投資問題54配料問題配料問題例6工廠要用三種原料1、2、3混合調配出不同規(guī)格的產品甲、乙、丙。問：該廠應如何安排生產，使利潤最大？產品名稱產品名稱規(guī)格要求規(guī)格要求單價（元單價（元/kg）甲原材料1不少于50%，原材料2不超過

40、25%50乙原材料1不少于25%，原材料2不超過50%35丙不限25原材料名稱原材料名稱每天最多供應量每天最多供應量單價（元單價（元/kg）110065210025360354配料問題配料問題解：設 xij 表示第 i 種（我們分別用1,2,3表示產品甲、乙、丙）產品中原料 j 的含量。建立數學模型時，要考慮：甲產品的數量為： x11 + x12 + x13；乙產品的數量為： x21 + x22 + x23；丙產品的數量為： x31 + x32 + x33；原料1的總需求量為： x11 + x21 + x31；原料2的總需求量為： x12 + x22 + x32； 原料3的總需求量為： x13

41、 + x23 + x33；目標函數： 利潤最大，利潤 = 收入 - 原料支出 約束條件： 規(guī)格要求 4 個； 供應量限制 3 個。4配料問題配料問題 利潤=總收入-總成本=甲乙丙三種產品的銷售單價*產品數量-甲乙丙使用的原料單價*原料數量，故有：目標函數：約束條件：Max 50（x11+x12+x13）+35（x21+x22+x23）+25（x31+x32+x33）-65（x11+x21+x31）-25（x12+x22+x32）-35（x13+x23+x33）= -15x11+25x12+15x13-30 x21+10 x22-40 x31-10 x33 從第1個表中有：x110.5(x11+

42、x12+x13) （甲含原材料1的比例）x120.25(x11+x12+x13)x210.25(x21+x22+x23)x220.5(x21+x22+x23)4配料問題配料問題 從第2個表中， 生產甲乙丙的原材料不能超過原材料的供應限額，故有：(x11+x21+x31)100 （原材料1的供應限額）(x12+x22+x32)100(x13+x23+x33)604配料問題配料問題通過整理，得到以下模型：目標函數：約束條件：Max z = -15x11+25x12+15x13-30 x21+10 x22-40 x31-10 x33 0.5 x11-0.5 x12 -0.5 x13 0 （原材料1不

43、少于50%）-0.25x11+0.75x12 -0.25x13 0 （原材料2不超過25%） 0.75x21-0.25x22 -0.25x23 0 （原材料1不少于25%）-0.5 x21+0.5 x22 -0.5 x23 0 （原材料2不超過50%）x11+ x21 + x31 100 (供應量限制）x12+ x22 + x32 100 (供應量限制）x13+ x23 + x33 60 (供應量限制）xij 0 , i = 1,2,3; j = 1,2,34配料問題配料問題例7.汽油混合問題。汽油的特性用“辛烷數”描述點火特性，用“蒸汽壓力”描述揮發(fā)性。煉油廠有1、2、3、4種標準汽油，性能

44、與庫存信息如表1.將這四種混合，可得到標號為1，2的兩種飛機汽油，性能指標如表2。問：如何根據庫存情況適量混合各種標準汽油，既滿足飛機汽油的性能指標，又使2號汽油滿足需求，并使得1號汽油產量最高？標準汽油標準汽油辛烷數辛烷數蒸汽壓力蒸汽壓力(g/cm2)庫存量庫存量(L)1107.57.1110-2380000293.011.38 10-2265200387.05.6910-24081004108.028.45 10-2130100飛機汽油飛機汽油辛烷數辛烷數蒸汽壓力蒸汽壓力(g/cm(g/cm2 2) )產量需求產量需求1不小于91不大于9.96 10-2越多越好2不小于100不大于9.96

45、 10-2不少于250000表14配料問題配料問題表24配料問題配料問題庫存量和產量約束為：解：設xij為飛機汽油i中所用標準汽油j的數量(L)。 目標函數為飛機汽油1的總產量越多越好 由物理中的分壓定律， 可得有關蒸汽壓力的約束條件： 辛烷數的約束條件為：4配料問題配料問題辛烷數和蒸汽壓力的約束條件為：4配料問題配料問題 綜上所述，得該問題的數學模型為：4配料問題配料問題 由管理運籌學軟件求解得：人力資源分配的問題生產計劃的問題套裁下料問題配料問題本章內容本章內容1234投資問題55投資問題投資問題 例8現有資金200萬元，今后五年內考慮給以下的項目投資。項目A：從第一年到第五年每年年初都可

46、投資，當年末能收回本利110%；項目B：從第一年到第四年每年年初都可投資，次年末能收回本利125%，但規(guī)定每年最大投資額不能超過30萬元；項目C：需在第三年年初投資，第五年末能收回本利140%，但規(guī)定最大投資額不能超過80萬元；項目D：需在第二年年初投資，第五年末能收回本利155%，但規(guī)定最大投資額不能超過100萬元。問：問：a）應如何確定這些項目的每年投資額，使得第五年 年末擁有資金的本利金額為最大？ b）應如何確定這些項目的每年投資額，使得第五年 年末擁有資金的本利在330萬元的基礎上使得其 投資總的風險系數為最??？據測定每萬元每次投資的風險指數如表：5投資問題投資問題項目項目風險指數（次

47、風險指數（次/萬元）萬元）A1B3C4D5.55投資問題投資問題 設 xij 表示第 i 年初投資于A(j=1)、B(j=2)、C(j=3)、D(j=4)項目的金額。這樣我們建立如下的決策變量： A x11 x21 x31 x41 x51 B x12 x22 x32 x42 C x33 D x24解：1）確定決策變量：連續(xù)投資問題2）約束條件：第一年：A項目當年末可收回投資，故第一年年初應把全部資金投出去，于是 x11+ x12 = 200；第二年：B項目次年末才可收回投資，故第二年年初有資金1.1 x11，于是 x21 + x22+ x24 = 1.1x11；B、C、D的投資限制： xi2

48、30 ( i =1、2、3、4 ) x33 80 x24 100 第四年：同上分析，年初有資金 1.1x31+ 1.25x22，于是 x41 + x42 = 1.1x31+ 1.25x22；5投資問題投資問題第五年：同上分析，年初有資金 1.1x41+ 1.25x32，于是 x51 = 1.1x41+ 1.25x32；第三年：第三年年初的資金是從項目A第二年投資和項目B第一年投資所回收的本息總和 1.1x21+ 1.25x12，于是 x31 + x32+ x33 = 1.1x21+ 1.25x12；5投資問題投資問題b)所設變量與問題a相同，目標函數為風險最小，有 Min f =x11+x21

49、+x31+x41+x51+3(x12+x22+x32+x42)+4x33+5.5x24 a) Max z = 1.1x51+ 1.25x42+ 1.4x33 + 1.55x24 s.t. x11+ x12 = 200 x21 + x22+ x24 = 1.1x11； x31 + x32+ x33 = 1.1x21+ 1.25x12； x41 + x42 = 1.1x31+ 1.25x22； x51 = 1.1x41+ 1.25x32； xi2 30 ( i =1、2、3、4 )，x33 80，x24 100 xij 0 ( i = 1、2、3、4、5；j = 1、2、3、4） 3）目標函數及模

50、型：5投資問題投資問題Min f = (x11+x21+x31+x41+x51)+3(x12+x22+x32+x42)+4x33+5.5x24 s.t. x11+ x12 = 200 x21 + x22+ x24 = 1.1x11； x31 + x32+ x33 = 1.1x21+ 1.25x12； x41 + x42 = 1.1x31+ 1.25x22； x51 = 1.1x41+ 1.25x32； xi2 30 ( i =1、2、3、4 )，x33 80，x24 100 1.1x51 + 1.25x42+ 1.4x33+ 1.55x24 330 xij 0 ( i = 1、2、3、4、5；

51、j = 1、2、3、4）即在問題a的約束條件中加上“第五年末擁有資金本利在330萬元”的條件，得模型：謝謝 謝！謝！管理運籌學管理運籌學第五章第五章 單純形法單純形法單純形法的基本思路和原理單純形法的基本思路和原理單純形法的表格形式單純形法的表格形式求目標函數值最小的線性規(guī)劃問題的單求目標函數值最小的線性規(guī)劃問題的單純形表解法純形表解法幾種特殊情況幾種特殊情況本章內容本章內容1234單純形法的基本思路和原理單純形法的基本思路和原理單純形法的表格形式單純形法的表格形式求目標函數值最小的線性規(guī)劃問題的單求目標函數值最小的線性規(guī)劃問題的單純形表解法純形表解法幾種特殊情況幾種特殊情況本章內容本章內容1

52、234 1單純形法的基本思路和原理單純形法的基本思路和原理單純形法的基本思路： 是是否否選取可行域某頂點選取可行域某頂點( (更優(yōu)頂點更優(yōu)頂點) )是否為最優(yōu)解是否為最優(yōu)解輸出輸出最優(yōu)解最優(yōu)解終止終止是否無最優(yōu)解是否無最優(yōu)解是是否否 1單純形法的基本思路和原理單純形法的基本思路和原理一、找出一個初始基本可行解一、找出一個初始基本可行解 下面通過第二章例1的求解來介紹單純形法。 在加上松弛變量之后得到此線性規(guī)劃的標準形式。 目標函數：max 50 x1+100 x2 約束條件：x1+x2+s1=300， 2x1+x2+s2=400， x2+s3=250， xi 0（i=1,2），sj0（j=1,

53、2,3）。 1單純形法的基本思路和原理單純形法的基本思路和原理 該線性規(guī)劃問題約束方程的系數矩陣為： 其中 pj 為系數矩陣 A 第 j 列的向量.A 的秩為3,方程組變量個數大于 A 的秩，從方程組的無數組解中找一找一個初始可行解個初始可行解。 1單純形法的基本思路和原理單純形法的基本思路和原理基 Amn 是約束條件系數矩陣，秩為 m。若 Bmm 是 A 的子陣，且可逆，稱 B 為一個基。如何找初始基本可行解？基本概念 基向量 基 B 中的一列即稱為一個基向量。非基向量在 A 中除了基 B 之外的一列稱之為基 B 的非基向量?；兞?與基向量 pi 相應的變量 xi 叫基變量，基變量有m個。

54、非基變量與非基向量 pj 相應的變量 xj 叫非基變量，非基變量有nm 個。 1單純形法的基本思路和原理單純形法的基本思路和原理 此例題找到 A 的一個基 B3（可逆子陣）：令非基變量 x1=0 ,s2=0 , 約束方程變?yōu)榛兞康姆匠獭?若在約束方程組系數矩陣中找到一個基，令其非基變量為零，再求解該 m 元線性方程組可得到唯一解，該解稱之為線性規(guī)劃的基本解基本解。 1單純形法的基本思路和原理單純形法的基本思路和原理 基變量的約束方程: x2+s1=300， x2 =400，x2+s3=250， 求解得到此線性規(guī)劃的一個基本解： x1=0，x2=400，s1=100，s2=0，s3=150 1

55、單純形法的基本思路和原理單純形法的基本思路和原理 由于該基本解中 s1=100，s3=150 ,不滿足決策變量非負的約束條件，不是可行解可行解。 滿足非負條件的基本解叫做基本可行解基本可行解，并把這樣的基叫做可行基可行基。 1單純形法的基本思路和原理單純形法的基本思路和原理 一般來說判斷一個基是否是可行基，只有在求出其基本解以后。能否在求解之前，找到一個可行基可行基呢？也就是能否找到的一個基保證在求解之后得到的解一定是基本可行解基本可行解呢？ 1單純形法的基本思路和原理單純形法的基本思路和原理 由于線性規(guī)劃的標準型中要求 bj 0，若能找到一個基是單位矩陣（各列向量順序無關重要），例如： 所得

56、基本解一定是基本可行解，解中的各個變量或等于某個 bj 或等于零。 本例中找到了一個基是單位矩陣： 令其非基變量 x1=x2=0，得初始基本可行解初始基本可行解： x1=0，x2=0，s1=300，s2=400，s3=250 1單純形法的基本思路和原理單純形法的基本思路和原理 第一次找到的可行基為單位矩陣（各列可以亂序），稱之為初始可行基初始可行基，相應的基本可行解叫初始初始基本可行解基本可行解。注：若找不到單位矩陣（各列可以亂序）的基作為初始可行基，需要構造初始可行基。 1最優(yōu)性檢驗的依據檢驗數檢驗數 j二、二、最優(yōu)性檢驗最優(yōu)性檢驗 判斷已求得的基本可行解是否是最優(yōu)解。 1單純形法的基本思路

57、和原理單純形法的基本思路和原理基變量&非基變量目標函數非基變量目標函數約束等式中，非基變量移到右邊，用非基變量表示基變量則目標函數中變量系數即為其檢驗數檢驗數，把 xi 的檢驗數記為 i。所有基變量檢驗數為0。 1單純形法的基本思路和原理單純形法的基本思路和原理 例題中找到一個初始可行基： 目標函數為50 x1+100 x2，由于初始可行解中x1，x2 為非基變量，所以此目標函數已經用非基變量表示了，無需代換出基變量。各檢驗數為： 1=50，2=100，3=0，4=0，5=0 1單純形法的基本思路和原理單純形法的基本思路和原理 2最優(yōu)解判別定理 求最大目標函數的問題中，若某個基本可行解

58、所有檢驗數 j 0，則該解是最優(yōu)解最優(yōu)解。 通俗地解釋最優(yōu)解判別定理，設用非基變量表示的目標函數如下所示： 注：對于求目標函數最小值的情況，只需把j 0改為j 0。 1單純形法的基本思路和原理單純形法的基本思路和原理當所有的 x j 0，且j 0，此時 實際上目標函數：基變量均0，只有檢驗數都為0，才有 s x s =0;非基變量的檢驗數均 0，只有非基變量都為0，才有 t x t=0 。此時目標函數才能取最大值z0。 1單純形法的基本思路和原理單純形法的基本思路和原理 三、三、基變換基變換 例題中 1，20，即該基本可行解不是最優(yōu)解，需進行基變換。 具體做法：更換可行基中的一個列向量，得到新

59、的可行基可行基，求出新的基本可行解基本可行解使目標函數值更優(yōu)。 為了換基要確定換入變量-入基變量入基變量與換出變量-出基變量出基變量。 1單純形法的基本思路和原理單純形法的基本思路和原理 1入基變量的確定 當某 j0 ，非基變量 xj 變?yōu)榛兞?，不?值可使目標函數值增大，故選基檢驗數大于0的非基變量換到基變量中。 max j ，其中 j0，對應的非基變量為入基變量基變量 若有兩個以上 j0，為使目標函數更大，一般選 j 較大者的非基變量為入基變量入基變量。例題中 2=100 是最大的非負檢驗數，故選 x2 為入基變量。 1單純形法的基本思路和原理單純形法的基本思路和原理 2出基變量的確定

60、確定入基變量后，需在原來的基變量 s1，s2，s3 中選一個出基變量出基變量。若 s3 作為出基變量，則新的基變量為 x2，s1，s2 ，非基變量 x1=s3=0，方程組變?yōu)椋?x2 + s1 = 300， x2 + s2 = 400， x2 = 250.得基本解：x1=0，x2=250，s1=50，s2=150，s3=0。此解滿足非負條件，是基本可行解基本可行解。 1單純形法的基本思路和原理單純形法的基本思路和原理 如何在求解以前來確定出基變量，使得求出的解是可行解？ 1單純形法的基本思路和原理單純形法的基本思路和原理 確定出基變量的方法如下： 把已確定的入基變量在各約束方程中的正系數除其所在約束方