新運籌學課件

1、運運 籌籌 學學( Operations Research )Page 2 運籌學（Operations Research）是用數(shù)學方法研究各種系統(tǒng)的最優(yōu)化問題，運籌學強調發(fā)揮現(xiàn)有系統(tǒng)的效能，應用數(shù)學模型求得合理利用各種資源的最佳方案，為決策者提供科學決策的依據(jù)。Page 3 選用教材選用教材 運籌學教程胡運權主編 （第2版）清華出版社參考教材運籌學牛英武主編 西安交通大學出版社運籌學(修訂版) 錢頌迪主編 清華出版社 先修課程先修課程 高等數(shù)學 線性代數(shù) 概率論（1）運籌學的產生發(fā)展及發(fā)展趨勢）運籌學的產生發(fā)展及發(fā)展趨勢（2）運籌學的性質特點及解題思路）運籌學的性質特點及解題思路（3）運籌學

2、的分支簡介）運籌學的分支簡介（4）運籌學在管理中的應用）運籌學在管理中的應用本章主要內容：本章主要內容：Page 5一、一、運籌學（運籌學（Operations Research）的產生、發(fā)展及）的產生、發(fā)展及發(fā)展趨勢發(fā)展趨勢 運籌學運籌學 的發(fā)展：三個來源（軍事、經濟及管理）的發(fā)展：三個來源（軍事、經濟及管理） 1.軍事：運籌學的主要發(fā)源地軍事：運籌學的主要發(fā)源地 國外歷史上的阿基米德、伽利略研究過作戰(zhàn)問題；第一次世界大戰(zhàn)時，英國的蘭徹斯特（Lanchester）提出了戰(zhàn)斗方程，指出了數(shù)量優(yōu)勢、火力和勝負的動態(tài)關系；美國的愛迪生為美國海軍咨詢委員會研究了潛艇攻擊和潛艇回避攻擊的問題。Page

3、 6運籌學的歷史運籌學的歷史“運作研究運作研究(Operational Research)小組小組”:解決復解決復雜的戰(zhàn)略和戰(zhàn)術問題。例如：雜的戰(zhàn)略和戰(zhàn)術問題。例如：1. 如何合理運用雷達有效地對付德軍德空襲如何合理運用雷達有效地對付德軍德空襲2. 對商船如何進行編隊護航，使船隊遭受德國潛對商船如何進行編隊護航，使船隊遭受德國潛艇攻擊時損失最少；艇攻擊時損失最少；3. 在各種情況下如何調整反潛深水炸彈的爆炸深在各種情況下如何調整反潛深水炸彈的爆炸深度，才能增加對德國潛艇的殺傷力等。度，才能增加對德國潛艇的殺傷力等。Page 7運籌學的正式產生：第二次世界大戰(zhàn)運籌學的正式產生：第二次世界大戰(zhàn) 據(jù)

4、不完全統(tǒng)計，二戰(zhàn)期間，僅在英、美和加拿大，參加據(jù)不完全統(tǒng)計，二戰(zhàn)期間，僅在英、美和加拿大，參加運籌學工作的科學家超過運籌學工作的科學家超過700名。名。2.管理管理 (1)泰勒的時間動作研究、甘特的用于生產計劃與控制的泰勒的時間動作研究、甘特的用于生產計劃與控制的“甘特圖甘特圖”、吉爾布雷思夫婦的動作研究等、吉爾布雷思夫婦的動作研究等 (2)愛爾朗（愛爾朗（Erlong）的排隊論公式）的排隊論公式 19091920年間，丹麥哥本哈根電話公司工程師愛爾朗年間，丹麥哥本哈根電話公司工程師愛爾朗陸續(xù)發(fā)表了關于電話通路數(shù)量等方面的分析與計算公式。陸續(xù)發(fā)表了關于電話通路數(shù)量等方面的分析與計算公式。尤其是

5、尤其是1909年的論文年的論文“概率與電話通話理論概率與電話通話理論”，開創(chuàng)了，開創(chuàng)了運籌學的重要分支排隊論。運籌學的重要分支排隊論。Page 83.經濟（數(shù)理經濟學）經濟（數(shù)理經濟學） (1)Von Neumann 與對策論與對策論 1932年，年，Von Neumann提出一個廣義經濟平衡模型；提出一個廣義經濟平衡模型；1939年，提出年，提出了一個屬于宏觀經濟優(yōu)化的控制論模型；了一個屬于宏觀經濟優(yōu)化的控制論模型；1944年，與年，與Morgenstern共著共著的對策論與經濟行為開創(chuàng)了對策論分支。的對策論與經濟行為開創(chuàng)了對策論分支。 (2)康托洛維奇與康托洛維奇與“生產組織與計劃中的數(shù)學

6、方法生產組織與計劃中的數(shù)學方法” 30年代，蘇聯(lián)數(shù)理經濟學家康托洛維奇從事生產組織與管理中的定年代，蘇聯(lián)數(shù)理經濟學家康托洛維奇從事生產組織與管理中的定量化方法研究，取得了很多重要成果。量化方法研究，取得了很多重要成果。1939年，出版了堪稱運籌學的先年，出版了堪稱運籌學的先驅著作生產組織與計劃中的數(shù)學方法，其思想和模型被歸入線驅著作生產組織與計劃中的數(shù)學方法，其思想和模型被歸入線性規(guī)劃范疇。性規(guī)劃范疇。Page 9Page 1011二、運籌學的研究對象、研究特征及解題思路二、運籌學的研究對象、研究特征及解題思路中國企業(yè)管理百科全書中國企業(yè)管理百科全書：運籌學是運用分析，試：運籌學是運用分析，試

7、驗，量化的方法，對經濟管理系統(tǒng)中人、財、物驗，量化的方法，對經濟管理系統(tǒng)中人、財、物( (時間時間) )等有限資源，進行統(tǒng)籌安排，為決策者提供有依據(jù)的等有限資源，進行統(tǒng)籌安排，為決策者提供有依據(jù)的最優(yōu)方案最優(yōu)方案（滿意方案）（滿意方案），以實現(xiàn)最有效地管理。，以實現(xiàn)最有效地管理。辭海辭海對運籌學解釋為：對運籌學解釋為：“二十世紀四十年代開始二十世紀四十年代開始形成的一門科學，主要研究經濟活動與軍事活動中能形成的一門科學，主要研究經濟活動與軍事活動中能用數(shù)量來表達的有關運用，籌劃與管理方面的問題，用數(shù)量來表達的有關運用，籌劃與管理方面的問題，它根據(jù)問題的要求，通過數(shù)學的分析與運算，作出綜它根據(jù)問

8、題的要求，通過數(shù)學的分析與運算，作出綜合性的合理的安排，以達到較經濟、較有效地使用人合性的合理的安排，以達到較經濟、較有效地使用人力、物力。近年來，它在理論與應用方面都有較大發(fā)力、物力。近年來，它在理論與應用方面都有較大發(fā)展。其主要分支有規(guī)劃論、對策論、排隊論及質量控展。其主要分支有規(guī)劃論、對策論、排隊論及質量控制等。制等?！边\籌學的研究對象、研究特征及解題思路運籌學的研究對象、研究特征及解題思路Page 12 1）機器、工具、設備、人員等資源如何最佳利用問題）機器、工具、設備、人員等資源如何最佳利用問題 研究方法有：線性規(guī)劃、整數(shù)規(guī)劃、網(wǎng)絡圖、動態(tài)規(guī)劃、研究方法有：線性規(guī)劃、整數(shù)規(guī)劃、網(wǎng)絡圖

9、、動態(tài)規(guī)劃、 目標規(guī)劃等目標規(guī)劃等2）競爭現(xiàn)象：如戰(zhàn)爭、投資、商品競爭）競爭現(xiàn)象：如戰(zhàn)爭、投資、商品競爭 方法是對策論方法是對策論3）擁擠現(xiàn)象：如公共汽車排隊、打電話、買東西、飛機著）擁擠現(xiàn)象：如公共汽車排隊、打電話、買東西、飛機著陸、船舶進港等陸、船舶進港等 方法是排隊論方法是排隊論Page 13所以可對運籌學的研究對象做如下概括： .運籌學的研究對象是各種系統(tǒng)。 .運籌學的研究目的是實現(xiàn)系統(tǒng)的最優(yōu)化，求得合理利用各種資源的最優(yōu)方案。 .運籌學的研究方法是運用數(shù)學語言來描述實際系統(tǒng)，通過建立數(shù)學模型和優(yōu)化技術求得系統(tǒng)運營的最優(yōu)解。 . .運籌學的研究動機是為決策者提供科學決策的依據(jù)。運籌學的

10、研究動機是為決策者提供科學決策的依據(jù)。 運籌學在工業(yè)、農業(yè)、商業(yè)、物流、經濟計劃、人力資源、軍事等運籌學在工業(yè)、農業(yè)、商業(yè)、物流、經濟計劃、人力資源、軍事等行業(yè)都有著非常廣泛的應用。有人曾對世界上行業(yè)都有著非常廣泛的應用。有人曾對世界上500500家著名的企業(yè)集團或家著名的企業(yè)集團或跨國公司進行過調查，發(fā)現(xiàn)其中跨國公司進行過調查，發(fā)現(xiàn)其中95%95%曾使用過線性規(guī)劃，曾使用過線性規(guī)劃，75%75%使用過運輸使用過運輸模型，模型，90%90%使用過網(wǎng)絡計劃技術，使用過網(wǎng)絡計劃技術，90%90%使用過存儲模型，使用過存儲模型，43%43%使用過動態(tài)使用過動態(tài)規(guī)劃。規(guī)劃。 由此可見運籌學是一門應用性

11、很強的學科。特別是隨著計算機技術由此可見運籌學是一門應用性很強的學科。特別是隨著計算機技術的不斷發(fā)展，計算機成為運籌學最強有力的運算工具，運籌學越來越顯的不斷發(fā)展，計算機成為運籌學最強有力的運算工具，運籌學越來越顯示出其廣泛的使用價值。示出其廣泛的使用價值。Page 143.3.運籌學的性質特點運籌學的性質特點1 1）運籌學的性質）運籌學的性質 應用科學“應用現(xiàn)有的科學技術知識和數(shù)學方法，解決實際中提出的專門問題，為決策者選擇最優(yōu)決策提供定量依據(jù)”。2)2)運籌學的特點運籌學的特點定量化分析多學科交叉，如綜合利用了心理學、經濟學、物理、化學等方法實現(xiàn)最優(yōu)決策15(1) (1) 科學性：運籌學是

12、以研究事物內科學性：運籌學是以研究事物內在規(guī)律，并從定量分析的角度探求更在規(guī)律，并從定量分析的角度探求更好地解決問題的一門科學。好地解決問題的一門科學。運籌學的研究對象、研究特征及解題思路運籌學的研究對象、研究特征及解題思路16(2) (2) 應用性：運籌學既對各種經營進應用性：運籌學既對各種經營進行創(chuàng)造性的科學研究，又涉及到組織行創(chuàng)造性的科學研究，又涉及到組織的實際管理問題，它具有很強的實踐的實際管理問題，它具有很強的實踐性，最終應能向決策者提供建設性意性，最終應能向決策者提供建設性意見，并應收到實效；見，并應收到實效；運籌學的研究對象、研究特征及解題思路運籌學的研究對象、研究特征及解題思路

13、17(3)(3)多學科的交叉性、綜合性：運籌學研究多學科的交叉性、綜合性：運籌學研究中吸收了來自不同領域的經驗，并被廣泛中吸收了來自不同領域的經驗，并被廣泛應用于工商企業(yè)、軍事部門、民政事業(yè)等應用于工商企業(yè)、軍事部門、民政事業(yè)等研究組織內的統(tǒng)籌協(xié)調問題，故其應用不研究組織內的統(tǒng)籌協(xié)調問題，故其應用不受行業(yè)、部門之限制；受行業(yè)、部門之限制；運籌學的研究對象、研究特征及解題思路運籌學的研究對象、研究特征及解題思路18(4)(4)系統(tǒng)性和最優(yōu)性系統(tǒng)性和最優(yōu)性: :它以整體最優(yōu)為目它以整體最優(yōu)為目標標, ,從系統(tǒng)的觀點出發(fā)從系統(tǒng)的觀點出發(fā), ,力圖以整個系統(tǒng)力圖以整個系統(tǒng)最佳的方式來解決該系統(tǒng)各部門之

14、間的最佳的方式來解決該系統(tǒng)各部門之間的利害沖突。對所研究的問題求出最優(yōu)解利害沖突。對所研究的問題求出最優(yōu)解, ,尋求最佳的行動方案尋求最佳的行動方案, ,所以它也可看成是所以它也可看成是一門優(yōu)化技術一門優(yōu)化技術, ,提供的是解決各類問題的提供的是解決各類問題的優(yōu)化方法。優(yōu)化方法。運籌學的研究對象、研究特征及解題思路運籌學的研究對象、研究特征及解題思路Page 19運籌學的研究對象、研究特征及解題思路運籌學的研究對象、研究特征及解題思路4.4.運籌學的工作步驟運籌學的工作步驟v提出和形成問題，v建立模型，v求解，v解的檢驗，v解的控制，v解的實施Page 20運籌學的研究的主要步驟：運籌學的研究

15、的主要步驟：真實系統(tǒng)真實系統(tǒng)系統(tǒng)分析系統(tǒng)分析問題描述問題描述模型建立模型建立與修改與修改模型求解模型求解與檢驗與檢驗結果分析與結果分析與實施實施數(shù)據(jù)準備數(shù)據(jù)準備Page 21數(shù)學規(guī)劃（數(shù)學規(guī)劃（線性規(guī)劃、整數(shù)規(guī)劃、目標規(guī)劃線性規(guī)劃、整數(shù)規(guī)劃、目標規(guī)劃、動態(tài)、動態(tài)規(guī)劃等）規(guī)劃等）圖論圖論存儲論存儲論排隊論排隊論對策論對策論排序與統(tǒng)籌方法排序與統(tǒng)籌方法決策分析決策分析Page 22運籌學在管理中的應用涉及幾個方面：運籌學在管理中的應用涉及幾個方面：1. 生產計劃2. 運輸問題3. 人事管理4. 庫存管理5. 市場營銷6. 財務和會計另外，還應用于設備維修、更新和可靠性分析，項目的選擇另外，還應用于

16、設備維修、更新和可靠性分析，項目的選擇與評價，工程優(yōu)化設計等。與評價，工程優(yōu)化設計等。231.3 1.3 運籌學在管理中的應用運籌學在管理中的應用 生產計劃生產計劃: : 生產作業(yè)的計劃、日程表的編生產作業(yè)的計劃、日程表的編排、合理下料、配料問題、物料管理等排、合理下料、配料問題、物料管理等; ; 庫存管理庫存管理: : 多種物資庫存量的管理多種物資庫存量的管理, , 庫存庫存方式、庫存量等方式、庫存量等; ; 運輸問題運輸問題: : 確定最小成本的運輸線路、物確定最小成本的運輸線路、物資的調撥、運輸工具的調度以及建廠地址資的調撥、運輸工具的調度以及建廠地址的選擇等的選擇等; ; 人事管理人事

17、管理: : 對人員的需求和使用的預測，對人員的需求和使用的預測，確定人員編制、人員合理分配，建立人才確定人員編制、人員合理分配，建立人才評價體系等評價體系等; ;241.3 1.3 運籌學在工商管理中的應用運籌學在工商管理中的應用 市場營銷市場營銷: : 廣告預算、媒介選擇、廣告預算、媒介選擇、定價、產品開發(fā)與銷售計劃制定等定價、產品開發(fā)與銷售計劃制定等; ; 財務和會計財務和會計: : 預測、貸款、成本分預測、貸款、成本分析、定價、證券管理、現(xiàn)金管理等析、定價、證券管理、現(xiàn)金管理等; ; * * * * 設備維修、更新，項目選擇、設備維修、更新，項目選擇、評價，工程優(yōu)化設計與管理等評價，工程

18、優(yōu)化設計與管理等; ;Page 25學科總成績學科總成績平時成績平時成績（2020）課堂考勤課堂考勤（5050）平時作業(yè)平時作業(yè)（5050）期末成績期末成績（8080）講授為主，結合習題作業(yè)講授為主，結合習題作業(yè)26“田忌田忌賽馬賽馬”是家喻戶曉的歷史故事。戰(zhàn)國時齊威王與齊是家喻戶曉的歷史故事。戰(zhàn)國時齊威王與齊相田忌賽馬，雙方各出三匹馬比賽，每勝一場贏得一千金。由相田忌賽馬，雙方各出三匹馬比賽，每勝一場贏得一千金。由于王府的馬比相府的馬好，所以田忌每次比賽都要輸?shù)羧Ы稹Ｓ谕醺鸟R比相府的馬好，所以田忌每次比賽都要輸?shù)羧Ы稹?后來田忌的謀士孫臏獻了一計：在每次開賽前要求對方先后來田忌的謀士孫

19、臏獻了一計：在每次開賽前要求對方先報馬名，由此區(qū)分對方參賽的是上馬、中馬還是下馬；然后以報馬名，由此區(qū)分對方參賽的是上馬、中馬還是下馬；然后以自己的上馬對對方的中馬、自己的中馬對對方和下馬、自己的自己的上馬對對方的中馬、自己的中馬對對方和下馬、自己的下馬對對方的上馬。這樣，兩勝一負反而贏得一千金。下馬對對方的上馬。這樣，兩勝一負反而贏得一千金。 幾個典故幾個典故 我國古代我國古代運籌運籌思想運用的典故思想運用的典故1 1“田忌田忌賽馬賽馬”27第一章第一章 緒緒 論論 我國古代我國古代運籌運籌思想運用的典故思想運用的典故2 2晉國公重建皇城晉國公重建皇城晉國公重建皇城的施工方案，晉國公重建皇城

20、的施工方案，體現(xiàn)了運籌學的樸素思想。要體現(xiàn)了運籌學的樸素思想。要使重建工程的各個工序使重建工程的各個工序, ,在時間、空間上彼此協(xié)調在時間、空間上彼此協(xié)調, ,環(huán)環(huán)環(huán)相扣環(huán)相扣, ,就需要運用行列式的相關知識就需要運用行列式的相關知識, ,進行精確計算進行精確計算. .283.3.沈括運糧沈括運糧 沈括沈括(1031-1095年年),北宋時期大科學家、軍事北宋時期大科學家、軍事家家.在率兵在率兵抗擊西夏侵擾抗擊西夏侵擾的征途中的征途中,曾經從行軍中各曾經從行軍中各類人員可以背負糧食的基本數(shù)據(jù)出發(fā)類人員可以背負糧食的基本數(shù)據(jù)出發(fā),分析計算分析計算了后了后勤人員與作戰(zhàn)士兵在不同行軍天數(shù)中的不同比例

21、關勤人員與作戰(zhàn)士兵在不同行軍天數(shù)中的不同比例關系系,同時也分析計算了用各種牲畜運糧與人力運糧之同時也分析計算了用各種牲畜運糧與人力運糧之間的間的利弊利弊,最后做出了最后做出了從敵國就地征糧從敵國就地征糧,保障前方供保障前方供應的重要決策應的重要決策.從而減少了后勤人員的比例從而減少了后勤人員的比例,增強了增強了 前方作戰(zhàn)的兵力前方作戰(zhàn)的兵力. Page 29“管理運籌學管理運籌學”2.02.0版包括：線性規(guī)劃、運輸問題、整數(shù)規(guī)劃（版包括：線性規(guī)劃、運輸問題、整數(shù)規(guī)劃（0-10-1整數(shù)整數(shù)規(guī)劃、純整數(shù)規(guī)劃和混合整數(shù)規(guī)劃）、目標規(guī)劃、對策論、最短路徑、規(guī)劃、純整數(shù)規(guī)劃和混合整數(shù)規(guī)劃）、目標規(guī)劃、對

22、策論、最短路徑、最小生成樹、最大流量、最小費用最大流、關鍵路徑、存儲論、排隊論、最小生成樹、最大流量、最小費用最大流、關鍵路徑、存儲論、排隊論、決策分析、預測問題和層次分析法，共決策分析、預測問題和層次分析法，共1515個子模塊。個子模塊。Chapter1 線性規(guī)劃線性規(guī)劃 (Linear Programming) LP的數(shù)學模型的數(shù)學模型 圖解法圖解法 單純形法單純形法 單純形法的進一步討論人工變量法單純形法的進一步討論人工變量法 LP模型的應用模型的應用Page 311. 規(guī)劃問題規(guī)劃問題 生產和經營管理中經常提出如何合理安排，使生產和經營管理中經常提出如何合理安排，使人力、物力等各種資源

23、得到充分利用，獲得最大的人力、物力等各種資源得到充分利用，獲得最大的效益，這就是規(guī)劃問題。效益，這就是規(guī)劃問題。（1 1）當任務或目標確定后，如何統(tǒng)籌兼顧，合理安排，用）當任務或目標確定后，如何統(tǒng)籌兼顧，合理安排，用最少的資源最少的資源 （如資金、設備、原標材料、人工、時間等）（如資金、設備、原標材料、人工、時間等）去完成確定的任務或目標去完成確定的任務或目標（2 2）在一定的資源條件限制下，如何組織安排生產獲得最）在一定的資源條件限制下，如何組織安排生產獲得最好的經濟效益（如產品量最多好的經濟效益（如產品量最多 、利潤最大、利潤最大. .）Page 32例例1.1 如圖所示，如何截取如圖所示

24、，如何截取x使鐵皮所圍成的容積最使鐵皮所圍成的容積最大？大？ x xa a xxav 220 dxdv0)2()2()2(22 xaxxa6ax Page 33例例1、(生產計劃問題）生產計劃問題） 某企業(yè)計劃生產甲、乙兩種產某企業(yè)計劃生產甲、乙兩種產品。這些產品分別要在品。這些產品分別要在A、B、C、D、四種不同的設、四種不同的設備上加工。按工藝資料規(guī)定，單件產品在不同設備上備上加工。按工藝資料規(guī)定，單件產品在不同設備上加工所需要的臺時如下表所示，企業(yè)決策者應如何安加工所需要的臺時如下表所示，企業(yè)決策者應如何安排生產計劃，使企業(yè)總的利潤最大？排生產計劃，使企業(yè)總的利潤最大？ 設設 備備產產

25、品品 A B C D利潤（元）利潤（元） 甲甲 2 1 4 0 2 乙乙 2 2 0 4 3 有有 效效 臺臺 時時 12 8 16 12Page 34解：設解：設x1、x2分別為甲、乙兩種產品的產量，則數(shù)學模型為：分別為甲、乙兩種產品的產量，則數(shù)學模型為：Page 35例例2（下料問題）長度為（下料問題）長度為1米的圓鋼多根，欲截成米的圓鋼多根，欲截成40、30、20cm長的用料分別長的用料分別為為20、45、50根，問如何下料才能使用料最??？根，問如何下料才能使用料最??？分析：在長度確定的原料上截取三種不同規(guī)格的圓鋼，可以歸納出分析：在長度確定的原料上截取三種不同規(guī)格的圓鋼，可以歸納出8

26、8種不種不同的下料方案：同的下料方案：圓鋼（米）圓鋼（米）40402 21 11 11 10 00 00 00 030300 02 21 10 03 32 21 10 020201 10 01 13 30 02 23 35 5料頭（米）料頭（米）0 00 010100 010100 010100 0Page 36 上述問題歸納為如何混合使用這上述問題歸納為如何混合使用這8 8種不同的下料方案，種不同的下料方案，來制造來制造20,45,5020,45,50根不同的鋼料，且要使用料最??？根不同的鋼料，且要使用料最?。?用料最省反映在兩個方面：用料最省反映在兩個方面： 1. 1.所用圓鋼數(shù)最少所用圓

27、鋼數(shù)最少 2. 2.使剩余的料頭總長為最短使剩余的料頭總長為最短 設設x xj j表示用第表示用第j j種下料方案下料的原料根種下料方案下料的原料根j=1,2,j=1,2,8,8,目標：料頭總長度目標：料頭總長度= = 圓鋼數(shù)圓鋼數(shù)= =Page 37例例3（運輸問題）兩個倉庫（運輸問題）兩個倉庫A1、A2，每月可分別調出鋼材，每月可分別調出鋼材28、29噸，噸，工地工地B1、B2、B3每月需鋼材分別每月需鋼材分別12、15、30噸均由倉庫噸均由倉庫A1、A2供應，供應，各倉庫運往各工地每噸鋼材的運費（元各倉庫運往各工地每噸鋼材的運費（元/噸）如下表，問如何安排運輸噸）如下表，問如何安排運輸計

28、劃可是總費用最小？計劃可是總費用最??？B1B2B3供應量A118252028A221222429需求量121530Page 38例例4、（合理配料問題）要求所分配飼料每單位的營養(yǎng)標準為：含蛋白、（合理配料問題）要求所分配飼料每單位的營養(yǎng)標準為：含蛋白質不少于質不少于21%，纖維不少于，纖維不少于5%，脂肪不少于，脂肪不少于3.4%，鐵不少于，鐵不少于1%但不大但不大于于1.05%，鈣不少于，鈣不少于0.45%但不大于但不大于0.6%。要求得出成本最小的配比方案要求得出成本最小的配比方案Page 39例例5、（廣告方式的選擇）某公司推銷一種新產品，有關數(shù)據(jù)如下表，銷、（廣告方式的選擇）某公司推銷

29、一種新產品，有關數(shù)據(jù)如下表，銷售部第一個月的廣告預算費為售部第一個月的廣告預算費為2萬元，要求至少有萬元，要求至少有8次電視廣告，次電視廣告，15次報次報紙廣告，電視廣告費不得超過紙廣告，電視廣告費不得超過1.2萬元，電臺廣播至少隔日一次，問公司萬元，電臺廣播至少隔日一次，問公司銷售部應采用怎樣的廣告宣傳計劃，才能取得最好的宣傳效果？銷售部應采用怎樣的廣告宣傳計劃，才能取得最好的宣傳效果？廣告方式廣告費用（元/次）可用最高次數(shù)（每月）期望宣傳效果電視（白天）5001650電視（晚上）10001080每日晨報1002430星期日報廣播電臺300804254015Page 40Page 4100

30、)( )( (min) max12211112121112211 nmnmnmmnnnnxxbxaxaxabxaxaxaxcxcxcz)21(j 0 )21(i )( Z (min)max 11nxmbxaxcjnjijijnjjj 簡寫為：簡寫為：Page 42通常稱 為決策變量， 為價值系數(shù)， 為消耗系數(shù), 。 為資源限制系數(shù)。) (21ncccC 12nx, x, x1 11 2m na,a, a12mb, b, bPage 43) (21ncccC nxxX1 mjjjaaP1 mbbB1 0 )( (min) maxXBxpCXzjj其中：其中：Page 44 mnmnaaaaA11

31、11 0 )( (min) maxXBAXCXZ其中：其中：) (21ncccC nxxX1 mbbB1Page 454. 線性規(guī)劃問題的標準形式線性規(guī)劃問題的標準形式minjxbxatsxcZjnjijijnjjj, 2 , 1, 2 , 1, 0.max11 特點：特點：(1) 目標函數(shù)求最大值（有時求最小值）目標函數(shù)求最大值（有時求最小值）(2) 約束條件都為等式方程，且右端常數(shù)項約束條件都為等式方程，且右端常數(shù)項bi都大于或等于零都大于或等于零(3) 決策變量決策變量xj為非負。為非負。Page 46（1 1）如何化標準形式）如何化標準形式 目標函數(shù)的轉換目標函數(shù)的轉換如果是求極小值即

32、如果是求極小值即 則可將目標函數(shù)乘以則可將目標函數(shù)乘以(-1)(-1)可化為求極可化為求極大值問題。大值問題。 jjxczmin也就是：令也就是：令 可得到上式?？傻玫缴鲜?。zz jjxczzmax即即若存在取值無約束的變量若存在取值無約束的變量 可令可令 其中：其中：jxjjjxxx 0, jjxx 變量的轉換變量的轉換Page 47 約束方程的轉換：由不等式轉換為等式。約束方程的轉換：由不等式轉換為等式。 ijijbxa0 iniinjijxbxxa稱為松弛變量稱為松弛變量 ijijbxa0 iniinjijxbxxa稱為剩余變量稱為剩余變量 變量的變換當變量的變換當 可令可令 ，顯然，顯

33、然0 jxjjxx 0 jxPage 48例例1.3 將下列線性規(guī)劃問題化為標準形式將下列線性規(guī)劃問題化為標準形式 ,0,52324 7 532min321321321321321無無約約束束xxxxxxxxxxxxxxxZ用用 替換替換 ，且，且 解解:（）因為（）因為x3無符號要求無符號要求 ，即，即x3取正值也可取負值，標準取正值也可取負值，標準型中要求變量非負，所以型中要求變量非負，所以33xx 3x0,33 xxPage 49(2) 第一個約束條件是第一個約束條件是“”號，在號，在“”左端加入松馳變量左端加入松馳變量x4，x40,化為等式；化為等式；(3) 第二個約束條件是第二個約束

34、條件是“”號，在號，在“”左端減去剩余變量左端減去剩余變量x5，x50；(4) 第第3個約束方程右端常數(shù)項為個約束方程右端常數(shù)項為-5，方程兩邊同乘以，方程兩邊同乘以(-1),將右將右端常數(shù)項化為正數(shù)；端常數(shù)項化為正數(shù)； (5) 目標函數(shù)是最小值，為了化為求最大值，令目標函數(shù)是最小值，為了化為求最大值，令z=-z,得到得到max z=-z，即當，即當z達到最小值時達到最小值時z達到最大值，反之亦然達到最大值，反之亦然;Page 50 0,5 )(252 )( 7 )(500)(32max54332133215332143321543321xxxxxxxxxxxxxxxxxxxxxxxxxxZ標

35、準形式如下：標準形式如下：Page 515. 5. 線性規(guī)劃問題的解線性規(guī)劃問題的解 )3(, 2 , 1, 0)2(), 2 , 1(.) 1 (max11njxmibxatsxcZjnjijijnjjj線性規(guī)劃問題線性規(guī)劃問題求解線性規(guī)劃問題，就是從滿足約束條件求解線性規(guī)劃問題，就是從滿足約束條件(2)、(3)的方程組的方程組中找出一個解，使目標函數(shù)中找出一個解，使目標函數(shù)(1)達到最大值。達到最大值。Page 52線性規(guī)劃問題的求解方法線性規(guī)劃問題的求解方法一一 般般 有有兩種方法兩種方法圖圖 解解 法法單純形法單純形法兩個變量、直角坐標兩個變量、直角坐標三個變量、立體坐標三個變量、立體

36、坐標適用于任意變量、但必需將適用于任意變量、但必需將一般形式變成標準形式一般形式變成標準形式下面我們分析一下簡單的情況下面我們分析一下簡單的情況 只有兩個決策只有兩個決策變量的線性規(guī)劃問題，這時可以通過圖解的方法變量的線性規(guī)劃問題，這時可以通過圖解的方法來求解。圖解法具有簡單、直觀、便于初學者窺來求解。圖解法具有簡單、直觀、便于初學者窺探線性規(guī)劃基本原理和幾何意義等優(yōu)點。探線性規(guī)劃基本原理和幾何意義等優(yōu)點。Page 53max Z = 2X1 + X2 X1 + 1.9X2 3.8 X1 - 1.9X2 3.8s.t. X1 + 1.9X2 10.2 X1 - 1.9X2 -3.8 X1 ，X

37、2 0例例1.5 用圖解法求解線性規(guī)劃問題用圖解法求解線性規(guī)劃問題Page 54x1x2oX1 - 1.9X2 = 3.8()X1 + 1.9X2 = 3.8()X1 - 1.9X2 = -3.8 ()X1 + 1.9X2 = 10.2()4 = 2X1 + X2 20 = 2X1 + X2 17.2 = 2X1 + X2 11 = 2X1 + X2 Lo： 0 = 2X1 + X2 （7.6，2）Dmax Zmin Z此點是唯一最優(yōu)解，此點是唯一最優(yōu)解，且最優(yōu)目標函數(shù)值且最優(yōu)目標函數(shù)值 max Z=17.2可行域可行域max Z = 2X1 + X2Page 55max Z=3X1+5.7X

38、2x1x2oX1 - 1.9X2 = 3.8 ()X1 + 1.9X2 = 3.8()X1 - 1.9X2 = -3.8()X1 + 1.9X2 = 10.2 ()（7.6，2）DL0： 0=3X1+5.7X2 max Z（3.8，4）34.2 = 3X1+5.7X2 藍色線段上的所有點都是最藍色線段上的所有點都是最優(yōu)解這種情形為有無窮多最優(yōu)解這種情形為有無窮多最優(yōu)解，但是最優(yōu)目標函數(shù)值優(yōu)解，但是最優(yōu)目標函數(shù)值max Z=34.2是唯一的。是唯一的。可行域可行域Page 56min Z=5X1+4X2x1x2oX1 - 1.9X2 = 3.8 ()X1 + 1.9X2 = 3.8()X1 +

39、1.9X2 = 10.2 ()DL0： 0=5X1+4X2 max Z min Z 8=5X1+4X2 43=5X1+4X2 （0，2）可行域可行域此點是唯一最優(yōu)解此點是唯一最優(yōu)解Page 57 006346321212121xxxxxxxx、246x1x2246無界解無界解( (無最優(yōu)解無最優(yōu)解) )max Z=x1+2x2例例1.6x1+x2=4()x1+3x2=6()3x1+x2=6() max Z min Zx1x2O10203040102030405050無可行解無可行解(即無最優(yōu)解即無最優(yōu)解)0,050305 .140221212121 xxxxxxxxmax Z=3x1+4x2例

40、例1.7Page 59學習要點：學習要點：1. 通過圖解法了解線性規(guī)劃有幾種解的形式通過圖解法了解線性規(guī)劃有幾種解的形式（唯一最優(yōu)解；無窮多最優(yōu)解；無界解；無可行解）（唯一最優(yōu)解；無窮多最優(yōu)解；無界解；無可行解）2. 作圖的關鍵有三點：作圖的關鍵有三點： (1) 可行解區(qū)域要畫正確可行解區(qū)域要畫正確 (2) 目標函數(shù)增加的方向不能畫錯目標函數(shù)增加的方向不能畫錯 (3) 目標函數(shù)的直線怎樣平行移動目標函數(shù)的直線怎樣平行移動Page 60 可行解可行解：滿足約束條件、的解為可行解。所有可行解：滿足約束條件、的解為可行解。所有可行解的集合為可行域。的集合為可行域。 最優(yōu)解最優(yōu)解：使目標函數(shù)達到最大值

41、的可行解。：使目標函數(shù)達到最大值的可行解。 基：基：設設A為約束條件的為約束條件的mn階系數(shù)矩陣階系數(shù)矩陣(m04010換換出出行行將將3化為化為15/311801/301/31011/3303005/304/3乘乘以以1/3后后得得到到103/51/518011/52/540011Page 83例例1.9 用單純形法求解用單純形法求解 02053115232.2max321321321321xxxxxxxxxtsxxxZ、解：將數(shù)學模型化為標準形式：解：將數(shù)學模型化為標準形式： 5 , 2 , 1, 02053115232.2max53214321321jxxxxxxxxxtsxxxZj不難

42、看出不難看出x4、x5可作為初始基變量，列單純形表計算?？勺鳛槌跏蓟兞浚袉渭冃伪碛嬎恪age 84cj12100icB基變量基變量bx1x2x3x4x50 x4152-32100 x5201/31501121000 x42x2j 201/3150120753017131/30902j 256011017/31/31250128/9-1/92/335/300-98/9 -1/9 -7/3j Page 85學習要點：學習要點：1. 線性規(guī)劃解的概念以及線性規(guī)劃解的概念以及3個基本定理個基本定理2. 熟練掌握單純形法的解題思路及求解步驟熟練掌握單純形法的解題思路及求解步驟Page 86人工變量

43、法：人工變量法：前面討論了在標準型中系數(shù)矩陣有單位矩陣，很容易前面討論了在標準型中系數(shù)矩陣有單位矩陣，很容易確定一組基可行解。在實際問題中有些模型并不含有單位確定一組基可行解。在實際問題中有些模型并不含有單位矩陣，為了得到一組基向量和初基可行解，在約束條件的矩陣，為了得到一組基向量和初基可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變量。這種人為加等式左端加一組虛擬變量，得到一組基變量。這種人為加的變量稱為人工變量，構成的可行基稱為人工基，用大的變量稱為人工變量，構成的可行基稱為人工基，用大MM法或兩階段法求解，這種用人工變量作橋梁的求解方法稱法或兩階段法求解，這種用人工變量作橋梁的求

44、解方法稱為人工變量法。為人工變量法。Page 87例例1.10 用大用大M法解下列線性規(guī)劃法解下列線性規(guī)劃 012210243423max321321321321321xxxxxxxxxxxxxxxZ、解：首先將數(shù)學模型化為標準形式解：首先將數(shù)學模型化為標準形式 5 , 2 , 1, 012210243423max32153214321321jxxxxxxxxxxxxxxxZj系數(shù)矩陣中不存在系數(shù)矩陣中不存在單位矩陣，無法建單位矩陣，無法建立初始單純形表。立初始單純形表。Page 88故人為添加兩個單位向量，得到人工變量單純形法數(shù)學模型：故人為添加兩個單位向量，得到人工變量單純形法數(shù)學模型：

45、7 , 2 , 1, 012210243423max732153216432176321jxxxxxxxxxxxxxxMxMxxxxZj其中：其中：M是一個很大的抽象的數(shù)，不需要給出具體的數(shù)值，是一個很大的抽象的數(shù)，不需要給出具體的數(shù)值，可以理解為它能大于給定的任何一個確定數(shù)值；再用前面介可以理解為它能大于給定的任何一個確定數(shù)值；再用前面介紹的單純形法求解該模型，計算結果見下表。紹的單純形法求解該模型，計算結果見下表。 Page 89cj32-100-M-MCBXBbx1x2x3x4x5x6x7i0 x64-431-10104-Mx5101-1201005-Mx712-21000113-2M2

46、+M-1+2M-M0 x63-650-1013/5-Mx58-3300108/3-1x312-210005-6M5M0-M002x23/56/5101/50-Mx531/53/5003/5131/3-1x311/52/5012/505 00002x213010123x131/310015/3-1x319/300102/3000-5-25/3j j j j Page 90解的判別：解的判別：1）唯一最優(yōu)解判別：最優(yōu)表中所有非基變量的檢驗數(shù)非零）唯一最優(yōu)解判別：最優(yōu)表中所有非基變量的檢驗數(shù)非零,則線則線 規(guī)劃具有唯一最優(yōu)解。規(guī)劃具有唯一最優(yōu)解。2）多重最優(yōu)解判別：最優(yōu)表中存在非基變量的檢驗數(shù)為零）

47、多重最優(yōu)解判別：最優(yōu)表中存在非基變量的檢驗數(shù)為零,則線則性規(guī)劃具有多重最優(yōu)解（或無窮多最優(yōu)解）。則線則性規(guī)劃具有多重最優(yōu)解（或無窮多最優(yōu)解）。3）無界解判別：某個）無界解判別：某個k0且且aik（i=1，2,m）則線性）則線性規(guī)劃具有無界解。規(guī)劃具有無界解。4）無可行解的判斷：當用大）無可行解的判斷：當用大M單純形法計算得到最優(yōu)解并單純形法計算得到最優(yōu)解并且存在且存在Ri0時，則表明原線性規(guī)劃無可行解。時，則表明原線性規(guī)劃無可行解。5）退化解的判別：）退化解的判別：存在某個基變量為零的基本可行解。存在某個基變量為零的基本可行解。Page 91單純性法小結單純性法小結:建建立立模模型型個個 數(shù)數(shù)

48、取取 值值右右 端端 項項等式或等式或不等式不等式極大或極小極大或極小新加變量新加變量系數(shù)系數(shù)兩兩個個三個三個以上以上xj0 xj無無約束約束xj 0 bi 0bi mi 時，企業(yè)愿意時，企業(yè)愿意購進這種資源，單位純利為購進這種資源，單位純利為yi*mi ，則有利可圖；如果，則有利可圖；如果yi* mi 則購進資源則購進資源i，可獲單位純利，可獲單位純利yi*mi 若若yi* mi則轉讓資源則轉讓資源i ，可獲單位純利，可獲單位純利miyiPage 1473）影子價格在資源利用中的應用）影子價格在資源利用中的應用根據(jù)對偶理論的互補松弛性定理根據(jù)對偶理論的互補松弛性定理:Y*Xs=0 , YsX

49、*=0表明生產過程中如果某種資源表明生產過程中如果某種資源bi未得到充分利用時，該種資未得到充分利用時，該種資源的影子價格為源的影子價格為0；若當資源資源的影子價格不為；若當資源資源的影子價格不為0時，表明時，表明該種資源在生產中已耗費完。該種資源在生產中已耗費完。Page 1484）影子價格對單純形表計算的解釋）影子價格對單純形表計算的解釋單純形表中的檢驗數(shù)單純形表中的檢驗數(shù) miiijjjBjjyacPBCc11其中其中c cj j表示第表示第j j種產品的價格種產品的價格; ; 表示生產該種產品所表示生產該種產品所消耗的各項資源的影子價格的總和消耗的各項資源的影子價格的總和, ,即產品的

50、隱含成本。即產品的隱含成本。 miiijya1當產值大于隱含成本時，即當產值大于隱含成本時，即 ，表明生產該項產品有，表明生產該項產品有利，可在計劃中安排；否則利，可在計劃中安排；否則 ，用這些資源生產別的，用這些資源生產別的產品更有利，不在生產中安排該產品。產品更有利，不在生產中安排該產品。0 j 0 j Page 149 對偶單純形法是求解線性規(guī)劃的另一個基本方法。它對偶單純形法是求解線性規(guī)劃的另一個基本方法。它是根據(jù)對偶原理和單純形法原理而設計出來的，因此稱為是根據(jù)對偶原理和單純形法原理而設計出來的，因此稱為對偶單純形法。不要簡單理解為是求解對偶問題的單純形對偶單純形法。不要簡單理解為是

51、求解對偶問題的單純形法。法。 找出一個對偶問題的可行基，保持對偶問題為可行解的找出一個對偶問題的可行基，保持對偶問題為可行解的條件下，判斷條件下，判斷XB是否可行（是否可行（XB為非負），若否，通過變換基為非負），若否，通過變換基解，直到找到原問題基可行解（即解，直到找到原問題基可行解（即XB為非負），這時原問題為非負），這時原問題與對偶問題同時達到可行解，由定理與對偶問題同時達到可行解，由定理4可得最優(yōu)解?？傻米顑?yōu)解。Page 150找出一個找出一個DP的可行基的可行基LP是否可行是否可行（XB 0）保持保持DP為可行解情況下轉移到為可行解情況下轉移到LP的另一個基本解的另一個基本解最優(yōu)解最

52、優(yōu)解是是否否循循環(huán)環(huán)結束結束Page 151例例2.9 用對偶單純形法求解：用對偶單純形法求解： )3.2.1(0145 1232102215129min321321321321jxxxxxxxxxxxxxZj解解:（1）將模型轉化為求最大化問題，約束方程化為等式求將模型轉化為求最大化問題，約束方程化為等式求出一組基本解，因為對偶問題可行，即全部檢驗數(shù)出一組基本解，因為對偶問題可行，即全部檢驗數(shù)0（求（求max問題）。問題）。Page 152 014 5 12 3210 2215129max61632153214321321xxxxxxxxxxxxxxxxZcj-9-12-15000bcBxB

53、x1x2x3x4x5x60 x4-2-2-1100-100 x5-2-3-1010-120 x6-1-1-5001-14(-9/-1.-12/-1. -15/-5)j-9-12-150000iPage 153cj-9-12-15000bcBxBx1x2x3x4x5x60 x4-9/5-9/5010-1/5-36/50 x5-9/5-14/5001-1/5-46/5-15x31/51/5100-1/514/5(-30/-9,-45/-14,-15/-1)-6-9000-342icj-9-12-15000bcBxBx1x2x3x4x5x60 x4-9/14001-9/14-1/14-9/7-12x

54、29/14100-5/141/1423/7(-3/-9,-45/-9,-33/-1)-15x31/140101/14-3/1415/7-3/14000-45/14-33/14ij j Page 154cj-9-12-15000cBxBx1x2x3x4x5x6b-9x1100-14/911/92-12x20101-102-15x30011/90-2/92000-1/3-3-7/3j 原問題的最優(yōu)解為：原問題的最優(yōu)解為：X*=（2 , 2 , 2 , 0 , 0 , 0），），Z* =72 其對偶問題的最優(yōu)解為：其對偶問題的最優(yōu)解為：Y*= （1/3 , 3 , 7/3），），W*= 72Page

55、 155 對偶單純形法應注意的問題：對偶單純形法應注意的問題： 用對偶單純形法求解線性規(guī)劃是一種求解方法，而不是去求對用對偶單純形法求解線性規(guī)劃是一種求解方法，而不是去求對偶問題的最優(yōu)解偶問題的最優(yōu)解 初始表中一定要滿足對偶問題可行，也就是說檢驗數(shù)滿足最優(yōu)初始表中一定要滿足對偶問題可行，也就是說檢驗數(shù)滿足最優(yōu)判別準則判別準則 最小比值中最小比值中 的絕對值是使得比值非負，在極小化問題的絕對值是使得比值非負，在極小化問題 j j00，分母分母a aij ij0 0 這時必須取絕對值。在極大化問題中，這時必須取絕對值。在極大化問題中， j j00，分母，分母a aij ij00， 總滿足非負，這時

56、絕對值符號不起作用，可以去掉。如總滿足非負，這時絕對值符號不起作用，可以去掉。如在本例中將目標函數(shù)寫成在本例中將目標函數(shù)寫成ijja 這里這里 j j 0 0在求在求 k k時就可以不帶絕對值符號。時就可以不帶絕對值符號。32134maxxxxz ijja Page 156 對偶單純形法與普通單純形法的換基順序不一樣，普通單純形法對偶單純形法與普通單純形法的換基順序不一樣，普通單純形法是先確定進基變量后確定出基變量，對偶單純形法是先確定出基變是先確定進基變量后確定出基變量，對偶單純形法是先確定出基變量后確定進基變量；量后確定進基變量； 普通單純形法的最小比值是普通單純形法的最小比值是 其目的是

57、保證下一其目的是保證下一個原問題的基本解可行，對偶單純形法的最小比值是個原問題的基本解可行，對偶單純形法的最小比值是 0minikikiiaab其目的是保證下一個對偶問題的基本解可行其目的是保證下一個對偶問題的基本解可行 0|minljljjjaa 對偶單純形法在確定出基變量時，若不遵循對偶單純形法在確定出基變量時，若不遵循 規(guī)則，任選一個小于零的規(guī)則，任選一個小于零的b bii對應的基變量出基，不影響計算結果，對應的基變量出基，不影響計算結果，只是迭代次數(shù)可能不一樣。只是迭代次數(shù)可能不一樣。 0|min iilbbbPage 157學習要點：學習要點：1. 線性規(guī)劃解的概念以及線性規(guī)劃解的概

58、念以及3個基本定理個基本定理2. 熟練掌握單純形法的解題思路及求解步驟熟練掌握單純形法的解題思路及求解步驟運輸規(guī)劃問題的數(shù)學模型運輸規(guī)劃問題的數(shù)學模型表上作業(yè)法表上作業(yè)法運輸問題的應用運輸問題的應用 Page 159例例3.1 某公司從兩個產地某公司從兩個產地A1、A2將物品運往三個銷地將物品運往三個銷地B1, B2, B3，各產地的產量、各銷地的銷量和各產地運往各銷地每件，各產地的產量、各銷地的銷量和各產地運往各銷地每件物品的運費如下表所示，問：應如何調運可使總運輸費用最物品的運費如下表所示，問：應如何調運可使總運輸費用最?。啃。緽1B2B3產量產量A1646200A2655300銷量銷量1

59、50150200Page 160解：產銷平衡問題：總產量解：產銷平衡問題：總產量 = 總銷量總銷量500 設設 xij 為從產地為從產地Ai運往銷地運往銷地Bj的運輸量，得到下列運輸量的運輸量，得到下列運輸量表：表：B1B2B3產量產量A1x11x12x13200A2x21x22x23300銷量銷量150150200Min C = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23 s.t. x11+ x12 + x13 = 200 x21 + x22+ x23 = 300 x11 + x21 = 150 x12 + x22 = 150 x13 + x23 = 200 xij

60、 0 ( i = 1、2；j = 1、2、3）Page 161運輸問題的一般形式：產銷平衡運輸問題的一般形式：產銷平衡A1、 A2、 Am 表示某物資的表示某物資的m個產地；個產地； B1、B2、Bn 表示表示某物質的某物質的n個銷地；個銷地；ai 表示產地表示產地Ai的產量；的產量； bj 表示銷地表示銷地Bj 的銷量；的銷量； cij 表示把物資從產地表示把物資從產地Ai運往銷地運往銷地Bj的單位運價。設的單位運價。設 xij 為從產地為從產地Ai運往銷地運往銷地Bj的運輸量，得到下列一般運輸量問題的模型：的運輸量，得到下列一般運輸量問題的模型： minjijijxcz11min njmi