運(yùn)籌學(xué)0 北郵

1、Operational Research ( OR ) |主講人：趙秀娟 |單位：北京郵電大學(xué)經(jīng)濟(jì)管理 學(xué)院信息系統(tǒng)中心 |電子郵箱： |電話|研究方向：優(yōu)化決策、經(jīng)濟(jì)評(píng) 價(jià)方法、金融分析與決策 201 1 年年 12 月月 出出 版版 目目 錄錄 緒緒 論論 第一章第一章 線性規(guī)劃線性規(guī)劃 第二章第二章 對(duì)偶理論與靈敏度分析對(duì)偶理論與靈敏度分析 第三章第三章 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 第四章第四章 整數(shù)規(guī)劃整數(shù)規(guī)劃 第五章第五章 動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃 第六章第六章 圖與網(wǎng)路分析圖與網(wǎng)路分析 第七章第七章 隨機(jī)服務(wù)理論概述隨機(jī)服務(wù)理論概述 第八章第八章 生滅服務(wù)系統(tǒng)生滅服務(wù)系統(tǒng)

2、第九章第九章 一般服務(wù)系統(tǒng)一般服務(wù)系統(tǒng) 第十章第十章 存儲(chǔ)理論存儲(chǔ)理論 第十一章第十一章 網(wǎng)絡(luò)計(jì)劃方法網(wǎng)絡(luò)計(jì)劃方法 緒緒 論論 一、運(yùn)籌學(xué)的起源與發(fā)展一、運(yùn)籌學(xué)的起源與發(fā)展 二、運(yùn)籌學(xué)的定義和主要研究分支二、運(yùn)籌學(xué)的定義和主要研究分支 三、運(yùn)籌學(xué)的特點(diǎn)及研究對(duì)象三、運(yùn)籌學(xué)的特點(diǎn)及研究對(duì)象 四、運(yùn)籌學(xué)解決問(wèn)題的方法步驟四、運(yùn)籌學(xué)解決問(wèn)題的方法步驟 五、運(yùn)籌學(xué)與其他學(xué)科的關(guān)系五、運(yùn)籌學(xué)與其他學(xué)科的關(guān)系 夫運(yùn)籌帷幄之中， 決勝千里之外。 |中國(guó)古代的運(yùn)籌學(xué)思想 z田忌賽馬 z丁渭修皇宮 z候叔獻(xiàn)治水 一、運(yùn)籌學(xué)的起源與發(fā)展一、運(yùn)籌學(xué)的起源與發(fā)展 起源于二次大戰(zhàn)的一門(mén)新興交叉學(xué)科起源于二次大戰(zhàn)的一門(mén)新

3、興交叉學(xué)科 與作戰(zhàn)問(wèn)題相關(guān)與作戰(zhàn)問(wèn)題相關(guān) 如雷達(dá)的設(shè)置、運(yùn)輸船隊(duì)的護(hù)航、反潛作戰(zhàn)中深水炸彈如雷達(dá)的設(shè)置、運(yùn)輸船隊(duì)的護(hù)航、反潛作戰(zhàn)中深水炸彈 的深度、飛行員的編組、軍事物資的存儲(chǔ)等的深度、飛行員的編組、軍事物資的存儲(chǔ)等 英國(guó)稱為英國(guó)稱為 Operational Research 美國(guó)稱為美國(guó)稱為 Operations Research 戰(zhàn)后在經(jīng)濟(jì)、管理和機(jī)關(guān)學(xué)校及科研單戰(zhàn)后在經(jīng)濟(jì)、管理和機(jī)關(guān)學(xué)校及科研單 位繼續(xù)研究位繼續(xù)研究 1952年，年，Morse 和和 Kimball出版出版運(yùn)籌學(xué)方法運(yùn)籌學(xué)方法 1948年英國(guó)首先成立運(yùn)籌學(xué)會(huì)年英國(guó)首先成立運(yùn)籌學(xué)會(huì) 1952年美國(guó)成立運(yùn)籌學(xué)會(huì)年美國(guó)成立運(yùn)籌

4、學(xué)會(huì) 1959年成立國(guó)際運(yùn)籌學(xué)聯(lián)合會(huì)年成立國(guó)際運(yùn)籌學(xué)聯(lián)合會(huì)(IFORS) 我國(guó)于我國(guó)于1982年加入年加入IFORS，并于，并于1999年年8月組織了第月組織了第15 屆大會(huì)屆大會(huì) 一、運(yùn)籌學(xué)的起源與發(fā)展一、運(yùn)籌學(xué)的起源與發(fā)展 1、中國(guó)運(yùn)籌學(xué)會(huì)簡(jiǎn)介、中國(guó)運(yùn)籌學(xué)會(huì)簡(jiǎn)介 50年代中期，我國(guó)著名科學(xué)家錢(qián)學(xué)森、許國(guó)志等教授將運(yùn)籌學(xué)從西方引年代中期，我國(guó)著名科學(xué)家錢(qián)學(xué)森、許國(guó)志等教授將運(yùn)籌學(xué)從西方引 入國(guó)內(nèi)。入國(guó)內(nèi)。1980年年4月，中國(guó)數(shù)學(xué)會(huì)運(yùn)籌學(xué)分會(huì)成立。月，中國(guó)數(shù)學(xué)會(huì)運(yùn)籌學(xué)分會(huì)成立。1991年，中國(guó)運(yùn)籌年，中國(guó)運(yùn)籌 學(xué)會(huì)成立。歷屆學(xué)會(huì)理事長(zhǎng)有，華羅庚、越民義，徐光輝，章祥蓀，袁學(xué)會(huì)成立。歷屆學(xué)會(huì)理

5、事長(zhǎng)有，華羅庚、越民義，徐光輝，章祥蓀，袁 亞湘（現(xiàn)任）亞湘（現(xiàn)任） 2、中國(guó)系統(tǒng)工程學(xué)會(huì)簡(jiǎn)介、中國(guó)系統(tǒng)工程學(xué)會(huì)簡(jiǎn)介 1、1979年由錢(qián)學(xué)森、宋健、關(guān)肇直、許國(guó)志等年由錢(qián)學(xué)森、宋健、關(guān)肇直、許國(guó)志等21名專家、學(xué)者共同倡名專家、學(xué)者共同倡 議并籌備。議并籌備。1980年年11月月18日在北京正式成立。日在北京正式成立。 第一屆理事會(huì)理事長(zhǎng)關(guān)第一屆理事會(huì)理事長(zhǎng)關(guān) 肇直，第二、三屆理事長(zhǎng)許國(guó)志。第四、五屆理事長(zhǎng)顧基發(fā)、第六屆理肇直，第二、三屆理事長(zhǎng)許國(guó)志。第四、五屆理事長(zhǎng)顧基發(fā)、第六屆理 事長(zhǎng)陳光亞、第七屆理事長(zhǎng)汪壽陽(yáng)（現(xiàn)任）。事長(zhǎng)陳光亞、第七屆理事長(zhǎng)汪壽陽(yáng)（現(xiàn)任）。 3、運(yùn)籌學(xué)、系、運(yùn)籌學(xué)、系

6、統(tǒng)工程統(tǒng)工程 主要研究人員構(gòu)成主要研究人員構(gòu)成 1）數(shù)學(xué)：如華羅庚、越民義，徐光輝，章祥蓀，袁亞湘，許國(guó)志，顧）數(shù)學(xué)：如華羅庚、越民義，徐光輝，章祥蓀，袁亞湘，許國(guó)志，顧 基發(fā)等；基發(fā)等； 2）控制論：張仲俊，劉豹，陳珽，鄭維敏，趙純均，陳劍等）控制論：張仲俊，劉豹，陳珽，鄭維敏，趙純均，陳劍等 3）管理等專業(yè)相關(guān)教學(xué)、科研技術(shù)人員）管理等專業(yè)相關(guān)教學(xué)、科研技術(shù)人員 一、運(yùn)籌學(xué)的起源與發(fā)展一、運(yùn)籌學(xué)的起源與發(fā)展 4、相關(guān)研究機(jī)構(gòu)和高校、相關(guān)研究機(jī)構(gòu)和高校 1）中國(guó)科學(xué)院數(shù)學(xué)與系統(tǒng)科學(xué)研究院應(yīng)用數(shù)學(xué)研究所）中國(guó)科學(xué)院數(shù)學(xué)與系統(tǒng)科學(xué)研究院應(yīng)用數(shù)學(xué)研究所 2）中國(guó)科學(xué)院數(shù)學(xué)與系統(tǒng)科學(xué)研究院應(yīng)用數(shù)學(xué)研

7、究所）中國(guó)科學(xué)院數(shù)學(xué)與系統(tǒng)科學(xué)研究院應(yīng)用數(shù)學(xué)研究所 3）哈工大：胡運(yùn)權(quán)，黃梯云，錢(qián)國(guó)明等）哈工大：胡運(yùn)權(quán)，黃梯云，錢(qián)國(guó)明等 4）天津大學(xué)：劉豹，顧培亮，張維，杜）天津大學(xué)：劉豹，顧培亮，張維，杜 綱等綱等 5）西安交大：汪應(yīng)洛，席酉民等）西安交大：汪應(yīng)洛，席酉民等 6）上海交大：張仲俊，王浣塵等）上海交大：張仲俊，王浣塵等 7）清華大學(xué)：鄭維敏，趙純均，陳劍等；）清華大學(xué)：鄭維敏，趙純均，陳劍等； 8）大連理工：王眾托，胡祥培等）大連理工：王眾托，胡祥培等 9）北航：顧昌耀，黃海軍等）北航：顧昌耀，黃海軍等 10）北理工）北理工 ：吳滄浦，吳祈宗，張強(qiáng)等：吳滄浦，吳祈宗，張強(qiáng)等 12 二、運(yùn)籌

8、學(xué)的定義和主要研究分支二、運(yùn)籌學(xué)的定義和主要研究分支 運(yùn)籌學(xué)的定義運(yùn)籌學(xué)的定義 為決策機(jī)構(gòu)對(duì)所控制的業(yè)務(wù)活動(dòng)作決策時(shí)，提供以數(shù)量為決策機(jī)構(gòu)對(duì)所控制的業(yè)務(wù)活動(dòng)作決策時(shí)，提供以數(shù)量 為基礎(chǔ)的科學(xué)方法為基礎(chǔ)的科學(xué)方法Morse 和和 Kimball 運(yùn)籌學(xué)是把科學(xué)方法應(yīng)用在指導(dǎo)人員、工商企業(yè)、政府運(yùn)籌學(xué)是把科學(xué)方法應(yīng)用在指導(dǎo)人員、工商企業(yè)、政府 和國(guó)防等方面解決發(fā)生的各種問(wèn)題，其方法是發(fā)展一個(gè)和國(guó)防等方面解決發(fā)生的各種問(wèn)題，其方法是發(fā)展一個(gè) 科學(xué)的系統(tǒng)模式，并運(yùn)用這種模式預(yù)測(cè)，比較各種決策科學(xué)的系統(tǒng)模式，并運(yùn)用這種模式預(yù)測(cè)，比較各種決策 及其產(chǎn)生的后果，以幫助主管人員科學(xué)地決定工作方針及其產(chǎn)生的后果

9、，以幫助主管人員科學(xué)地決定工作方針 和政策和政策英國(guó)運(yùn)籌學(xué)會(huì)英國(guó)運(yùn)籌學(xué)會(huì) 運(yùn)籌學(xué)是應(yīng)用分析、試驗(yàn)、量化的方法對(duì)經(jīng)濟(jì)管理系統(tǒng)運(yùn)籌學(xué)是應(yīng)用分析、試驗(yàn)、量化的方法對(duì)經(jīng)濟(jì)管理系統(tǒng) 中人力、物力、財(cái)力等資源進(jìn)行統(tǒng)籌安排，為決策者提中人力、物力、財(cái)力等資源進(jìn)行統(tǒng)籌安排，為決策者提 供有根據(jù)的最優(yōu)方案，以實(shí)現(xiàn)最有效的管理供有根據(jù)的最優(yōu)方案，以實(shí)現(xiàn)最有效的管理中國(guó)百中國(guó)百 科全書(shū)科全書(shū) 現(xiàn)代運(yùn)籌學(xué)涵蓋了一切領(lǐng)域的管理與優(yōu)化問(wèn)題，稱為現(xiàn)代運(yùn)籌學(xué)涵蓋了一切領(lǐng)域的管理與優(yōu)化問(wèn)題，稱為 Management Science 13 二、運(yùn)籌學(xué)的定義和主要研究分支二、運(yùn)籌學(xué)的定義和主要研究分支 運(yùn)籌學(xué)的分支運(yùn)籌學(xué)的分支

10、數(shù)學(xué)規(guī)劃：線性規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃、動(dòng)態(tài)規(guī)數(shù)學(xué)規(guī)劃：線性規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃、動(dòng)態(tài)規(guī) 劃、目標(biāo)規(guī)劃等劃、目標(biāo)規(guī)劃等 圖論與網(wǎng)路理論圖論與網(wǎng)路理論 隨機(jī)服務(wù)理論：排隊(duì)論隨機(jī)服務(wù)理論：排隊(duì)論 存儲(chǔ)理論存儲(chǔ)理論 網(wǎng)絡(luò)計(jì)劃方法網(wǎng)絡(luò)計(jì)劃方法 決策理論決策理論 對(duì)策論對(duì)策論 系統(tǒng)仿真：隨機(jī)模擬技術(shù)、系統(tǒng)動(dòng)力學(xué)系統(tǒng)仿真：隨機(jī)模擬技術(shù)、系統(tǒng)動(dòng)力學(xué) 可靠性理論可靠性理論 金融工程金融工程 例1： 某工廠在生產(chǎn)過(guò)程中需要使用 濃度為80%的硫酸100噸，而市面上 只有濃度為30%，45%，73%，85% ，92%的硫酸出售，每噸的價(jià)格分 別為400、700、1400、1900和2500 元。問(wèn)：采用怎

11、樣的購(gòu)買(mǎi)方案，才 能使所需費(fèi)用最?。?王經(jīng)理花費(fèi)12000元購(gòu)買(mǎi)了一臺(tái)微型車(chē)，年 度維護(hù)費(fèi)用取決于年初時(shí)汽車(chē)的役齡，如表示。 為避免使用舊車(chē)會(huì)帶來(lái)較高的維護(hù)費(fèi)用，王經(jīng)理 可選擇賣(mài)掉舊車(chē)而購(gòu)買(mǎi)新車(chē)使用的策略，舊車(chē)的 售價(jià)如表示。為簡(jiǎn)化計(jì)算，假定任何時(shí)刻購(gòu)買(mǎi)新 車(chē)都需花費(fèi)12000元，王經(jīng)理的目標(biāo)是使凈費(fèi)用 最小。（凈費(fèi)用=購(gòu)置費(fèi)+維護(hù)費(fèi)-賣(mài)舊車(chē)收入） 役齡(年) 0 1 2 3 4 5 年維護(hù)費(fèi)2000 4000 5000 9000 12000 - 交易價(jià)格 - 7000 6000 2000 1000 0 費(fèi)用單位：元 若你在俱樂(lè)部玩擲骰子的游戲，兩枚骰子 同時(shí)擲，勝負(fù)取決于出現(xiàn)的點(diǎn)數(shù)之和。兩枚

12、骰 子之和可能212。若點(diǎn)數(shù)為2，你就損失10元 ，若點(diǎn)數(shù)為7或11，你就贏W元；若出現(xiàn)其它點(diǎn) 數(shù)，你就損失1元。問(wèn)：W為多大時(shí)，這個(gè)游戲 才能對(duì)你有吸引力？ 17 三、運(yùn)籌學(xué)的特點(diǎn)及研究對(duì)象三、運(yùn)籌學(xué)的特點(diǎn)及研究對(duì)象 運(yùn)籌學(xué)的特點(diǎn)：運(yùn)籌學(xué)的特點(diǎn)： 1)優(yōu)化優(yōu)化 以整體最優(yōu)為目標(biāo)，從系統(tǒng)的觀點(diǎn)出發(fā)，力圖以整個(gè)系以整體最優(yōu)為目標(biāo)，從系統(tǒng)的觀點(diǎn)出發(fā)，力圖以整個(gè)系 統(tǒng)最佳的方式來(lái)協(xié)調(diào)各部門(mén)之間的利害沖突，從而求出統(tǒng)最佳的方式來(lái)協(xié)調(diào)各部門(mén)之間的利害沖突，從而求出 問(wèn)題的最優(yōu)解。所以運(yùn)籌學(xué)可看成是一門(mén)優(yōu)化技術(shù)，為問(wèn)題的最優(yōu)解。所以運(yùn)籌學(xué)可看成是一門(mén)優(yōu)化技術(shù)，為 解決各類問(wèn)題提供優(yōu)化方法解決各類問(wèn)題提供優(yōu)

13、化方法 2定量定量 為所研究的問(wèn)題提供定量的解決方案。如采用運(yùn)籌學(xué)研為所研究的問(wèn)題提供定量的解決方案。如采用運(yùn)籌學(xué)研 究資源分配問(wèn)題時(shí)，其求解結(jié)果是一個(gè)定量的最優(yōu)資源究資源分配問(wèn)題時(shí)，其求解結(jié)果是一個(gè)定量的最優(yōu)資源 分配方案。分配方案。 運(yùn)籌學(xué)的研究對(duì)象：運(yùn)籌學(xué)的研究對(duì)象： 來(lái)自生產(chǎn)管理過(guò)程中的具體問(wèn)題，如資源分配、物資調(diào)來(lái)自生產(chǎn)管理過(guò)程中的具體問(wèn)題，如資源分配、物資調(diào) 度，生產(chǎn)計(jì)劃與控制等。度，生產(chǎn)計(jì)劃與控制等。 |特點(diǎn)： z系統(tǒng)的整體觀念 z多學(xué)科的綜合 z以及模型方法的應(yīng)用。 |優(yōu)點(diǎn)： 1 事前分析、減少失誤 2 符號(hào)語(yǔ)言、便于交流 3 抽象反映實(shí)際、突出共性 2a x 用一塊邊長(zhǎng)為2a

14、的正方形鐵皮，四角剪 去相等小正方形后將四邊折起做一個(gè)鐵盒， 問(wèn)：如何剪能使做成的盒子體積最大？ 底 模型的概念：按一定規(guī)則完成的對(duì)現(xiàn) 實(shí)的抽象。 模型的形式： （1）實(shí)物模型：以實(shí)體描述對(duì)象。 （2）圖像模型：以圖示描述對(duì)象。 （3）數(shù)學(xué)模型：以數(shù)學(xué)符號(hào)和表達(dá)式完 成的對(duì)現(xiàn)實(shí)的抽象。 模型的建立：實(shí)際問(wèn)題抽象為數(shù)學(xué)表 達(dá)式的過(guò)程稱為建模。 設(shè) 剪掉的小正方形的邊長(zhǎng)為x， 則該問(wèn)題等同于 求max V=(2a-2x)2 x 在滿足2x2a x0 V所做成的盒子的體積。 （1）按表達(dá)事物的數(shù)學(xué)特點(diǎn)：線性規(guī) 劃、整數(shù)規(guī)劃、非線性規(guī)劃等； （2）按特定專題用途：運(yùn)輸模型、 分配模型、存儲(chǔ)模型、投入產(chǎn)

15、出模型 、排隊(duì)模型等； （3）按研究對(duì)象：能源模型、教育模 型、人口模型、投資模型、宏觀經(jīng)濟(jì) 模型。 管理內(nèi)容核心問(wèn)題：正確決策 管理方法核心問(wèn)題：科學(xué)性；藝術(shù)性 定性決策：方向性、戰(zhàn)略性 定量決策：數(shù)量上、戰(zhàn)術(shù)上 24 四、運(yùn)籌學(xué)解決問(wèn)題的方法步驟四、運(yùn)籌學(xué)解決問(wèn)題的方法步驟 1、理清問(wèn)題、明確目標(biāo)、理清問(wèn)題、明確目標(biāo) 2、建立模型、建立模型 討論：什么叫模型討論：什么叫模型 3、求解模型。建立模型之后，需要設(shè)計(jì)相應(yīng)算法進(jìn)、求解模型。建立模型之后，需要設(shè)計(jì)相應(yīng)算法進(jìn) 行求解，實(shí)際問(wèn)題運(yùn)算量一般都很大，通常需要用計(jì)行求解，實(shí)際問(wèn)題運(yùn)算量一般都很大，通常需要用計(jì) 算機(jī)求解。算機(jī)求解。 4、結(jié)果分

16、析、結(jié)果分析 討論：模型計(jì)算結(jié)果與已有的經(jīng)驗(yàn)或知識(shí)進(jìn)行比較討論：模型計(jì)算結(jié)果與已有的經(jīng)驗(yàn)或知識(shí)進(jìn)行比較 1）模型計(jì)算結(jié)果和已有的經(jīng)驗(yàn)或知識(shí)比較一致）模型計(jì)算結(jié)果和已有的經(jīng)驗(yàn)或知識(shí)比較一致 2）模型計(jì)算結(jié)果和已有的經(jīng)驗(yàn)或知識(shí)差異較大）模型計(jì)算結(jié)果和已有的經(jīng)驗(yàn)或知識(shí)差異較大 你喜歡那一種情況？你喜歡那一種情況？ 確定目標(biāo)，明確約束 抓主要矛盾、舍次要矛盾 選擇模型、設(shè)定變量 描述約束和目標(biāo)、確定參數(shù) 選擇求解方法、求解問(wèn)題 靈敏度分析、評(píng)價(jià) 匯總、解釋結(jié)果、報(bào)告 提出問(wèn)題 建立模型 優(yōu)化求解 評(píng)價(jià)分析 決策支持 26 五、運(yùn)籌學(xué)與其他學(xué)科的關(guān)系五、運(yùn)籌學(xué)與其他學(xué)科的關(guān)系 運(yùn)籌學(xué)目標(biāo)分析、建模、求解

17、和結(jié)果分析需要用到運(yùn)籌學(xué)目標(biāo)分析、建模、求解和結(jié)果分析需要用到 很多相關(guān)學(xué)科的知識(shí)，它與如下學(xué)科的知識(shí)關(guān)系比較很多相關(guān)學(xué)科的知識(shí)，它與如下學(xué)科的知識(shí)關(guān)系比較 密切。密切。 1、數(shù)學(xué)：學(xué)習(xí)、應(yīng)用運(yùn)籌學(xué)應(yīng)該具備較廣的數(shù)學(xué)知識(shí)，、數(shù)學(xué)：學(xué)習(xí)、應(yīng)用運(yùn)籌學(xué)應(yīng)該具備較廣的數(shù)學(xué)知識(shí)， 許多運(yùn)籌學(xué)者來(lái)自數(shù)學(xué)專業(yè)就是這個(gè)原因，有人甚至許多運(yùn)籌學(xué)者來(lái)自數(shù)學(xué)專業(yè)就是這個(gè)原因，有人甚至 認(rèn)為運(yùn)籌學(xué)是一門(mén)應(yīng)用數(shù)學(xué)；認(rèn)為運(yùn)籌學(xué)是一門(mén)應(yīng)用數(shù)學(xué)； 2、管理學(xué)：運(yùn)籌學(xué)研究對(duì)象是生產(chǎn)管理過(guò)程的具體問(wèn)、管理學(xué)：運(yùn)籌學(xué)研究對(duì)象是生產(chǎn)管理過(guò)程的具體問(wèn) 題，在利用運(yùn)籌學(xué)理論和方法解決具體問(wèn)題時(shí)，需要題，在利用運(yùn)籌學(xué)理論和方法解決具體問(wèn)題

18、時(shí)，需要 的涉及管理科學(xué)的有關(guān)理論；的涉及管理科學(xué)的有關(guān)理論； 3、計(jì)算機(jī)：運(yùn)籌學(xué)所研究的實(shí)際問(wèn)題通常都是比較復(fù)、計(jì)算機(jī)：運(yùn)籌學(xué)所研究的實(shí)際問(wèn)題通常都是比較復(fù) 雜，而且規(guī)模比較大，在求解這些問(wèn)題時(shí)，必須借助雜，而且規(guī)模比較大，在求解這些問(wèn)題時(shí)，必須借助 計(jì)算機(jī)來(lái)完成。計(jì)算機(jī)來(lái)完成。 認(rèn)真聽(tīng)課，出勤，預(yù)習(xí)與復(fù)習(xí)； 及時(shí)完成作業(yè)：課堂作業(yè)； (3)考核辦法： 平時(shí)成績(jī) 分 期中考試 分 期末考試 分 28 第一章第一章 線性規(guī)劃線性規(guī)劃 1.1 線性規(guī)劃模型線性規(guī)劃模型 1.1.11.1.1問(wèn)題的提出問(wèn)題的提出 一、例一、例1 1、多產(chǎn)品生產(chǎn)問(wèn)題、多產(chǎn)品生產(chǎn)問(wèn)題（Max, ） 甲電纜甲電纜乙電纜乙

19、電纜資源量資源量 銅（噸）銅（噸）2110 鉛（噸）鉛（噸）118 價(jià)格（萬(wàn)元）價(jià)格（萬(wàn)元）64 需求需求無(wú)限制無(wú)限制7 另 問(wèn)該工廠應(yīng)如何安排生產(chǎn)才能使工廠的總收入最大？問(wèn)該工廠應(yīng)如何安排生產(chǎn)才能使工廠的總收入最大？ 一、例一、例1 1、多產(chǎn)品生產(chǎn)問(wèn)題、多產(chǎn)品生產(chǎn)問(wèn)題（Max, ） 設(shè)設(shè)x1, x2 分別代表甲、乙兩種電纜的生產(chǎn)量，分別代表甲、乙兩種電纜的生產(chǎn)量，f(x)為工廠為工廠 的總收入，則上述問(wèn)題可用如下數(shù)學(xué)模型來(lái)表示的總收入，則上述問(wèn)題可用如下數(shù)學(xué)模型來(lái)表示 其中，其中，OBJ（Objective）表示目標(biāo)，）表示目標(biāo)，S.t.（Subject to）表示滿足）表示滿足 于。表示在

20、滿足銅、鉛資源和需求等約束條件下，使工廠的總收于。表示在滿足銅、鉛資源和需求等約束條件下，使工廠的總收 入這一目標(biāo)達(dá)到最大。最優(yōu)解為入這一目標(biāo)達(dá)到最大。最優(yōu)解為 產(chǎn)量不允許為負(fù)值 產(chǎn)量約束 鉛資源約束 銅資源約束 0, 7 8 102 . . 46)(max: 21 2 21 21 21 xx x xx xx ts xxxfOBJ .36)(max, 6, 2 21 xfxx 二、例二、例2、配料問(wèn)題（、配料問(wèn)題（min, ) ) 某混合飼料加工廠計(jì)劃從市場(chǎng)上購(gòu)買(mǎi)甲、乙兩種原料生產(chǎn)一種某混合飼料加工廠計(jì)劃從市場(chǎng)上購(gòu)買(mǎi)甲、乙兩種原料生產(chǎn)一種 混合飼料?；旌巷暳蠈?duì)混合飼料?；旌巷暳蠈?duì)VA、VB1、

21、VB2和和VD的最低含量有一定的最低含量有一定 的要求。已知單位甲、乙兩種原料的要求。已知單位甲、乙兩種原料VA、VB1、VB2和和VD的含量，的含量， 單位混合飼料對(duì)單位混合飼料對(duì)VA、VB1、VB2和和VD的最低含量以及甲、乙兩的最低含量以及甲、乙兩 種原料的單位價(jià)格如下表所示。種原料的單位價(jià)格如下表所示。 問(wèn)該該加工廠應(yīng)如何搭配使用甲乙兩種原料，才能使混合問(wèn)該該加工廠應(yīng)如何搭配使用甲乙兩種原料，才能使混合 飼料在滿足飼料在滿足VA、VB1、VB2和和VD的最低含量要求條件下，的最低含量要求條件下， 總成本最小？總成本最小？ 二、例二、例2、配料問(wèn)題（、配料問(wèn)題（MIN, ) ) 設(shè)設(shè) x

22、1, x2分別代表混合單位飼料對(duì)甲、乙兩種原料的用量，分別代表混合單位飼料對(duì)甲、乙兩種原料的用量，f(x) 表示單位混合飼料所需要的成本，則上述問(wèn)題的線性規(guī)劃數(shù)學(xué)表示單位混合飼料所需要的成本，則上述問(wèn)題的線性規(guī)劃數(shù)學(xué) 模型如下：模型如下： 該數(shù)學(xué)模型的最優(yōu)解為該問(wèn)題的最優(yōu)解為該數(shù)學(xué)模型的最優(yōu)解為該問(wèn)題的最優(yōu)解為 x1=3.69，x2=0.77，minf(x)=1.49 0, 22 . 05 . 0 2 . 16 . 02 . 0 33 . 00 . 1 25 . 05 . 0 . . 5 . 03 . 0)(min 21 21 21 21 21 21 xx xx xx xx xx ts xxx

23、f 三、線性規(guī)劃數(shù)學(xué)模型的特征和定義三、線性規(guī)劃數(shù)學(xué)模型的特征和定義 1、線性規(guī)劃數(shù)學(xué)模型的特征：、線性規(guī)劃數(shù)學(xué)模型的特征： 1）有一組決策變量（）有一組決策變量（x1，x2，xn）表示某一方案。這一組）表示某一方案。這一組 決策變量的具體值就代表一個(gè)具體方案；決策變量的具體值就代表一個(gè)具體方案； 2）有一個(gè)目標(biāo)函數(shù)，該目標(biāo)函數(shù)根據(jù)其的具體性質(zhì)取最大值）有一個(gè)目標(biāo)函數(shù)，該目標(biāo)函數(shù)根據(jù)其的具體性質(zhì)取最大值 或最小值。當(dāng)目標(biāo)為成本型時(shí)取最小，而當(dāng)目標(biāo)為效益型時(shí)取或最小值。當(dāng)目標(biāo)為成本型時(shí)取最小，而當(dāng)目標(biāo)為效益型時(shí)取 最大。最大。 3）有一組約束方程，包括決策變量的非負(fù)約束；）有一組約束方程，包括決

24、策變量的非負(fù)約束； 4）目標(biāo)函數(shù)和約束方程都是線性的。）目標(biāo)函數(shù)和約束方程都是線性的。 2、線性規(guī)劃數(shù)學(xué)模型的定義、線性規(guī)劃數(shù)學(xué)模型的定義 定義定義1.1 有一個(gè)目標(biāo)函數(shù)和一組約束方程，且目標(biāo)函數(shù)和約束有一個(gè)目標(biāo)函數(shù)和一組約束方程，且目標(biāo)函數(shù)和約束 方程都是線性的數(shù)學(xué)模型稱為線性規(guī)劃數(shù)學(xué)模型。方程都是線性的數(shù)學(xué)模型稱為線性規(guī)劃數(shù)學(xué)模型。 四、線性規(guī)劃數(shù)學(xué)模型的背景模型和思考四、線性規(guī)劃數(shù)學(xué)模型的背景模型和思考 1、線性規(guī)劃數(shù)學(xué)模型的背景模型：、線性規(guī)劃數(shù)學(xué)模型的背景模型： 例例1.1的多產(chǎn)品生產(chǎn)計(jì)劃問(wèn)題的數(shù)學(xué)模型稱為線性規(guī)劃的背景模的多產(chǎn)品生產(chǎn)計(jì)劃問(wèn)題的數(shù)學(xué)模型稱為線性規(guī)劃的背景模 型。把該背

25、景模型的條件一般化后可敘述如下：用有限量的幾型。把該背景模型的條件一般化后可敘述如下：用有限量的幾 種資源生產(chǎn)若干種產(chǎn)品，如何安排生產(chǎn)，才能使工廠的總收入種資源生產(chǎn)若干種產(chǎn)品，如何安排生產(chǎn)，才能使工廠的總收入 或利潤(rùn)達(dá)到最大?；蚶麧?rùn)達(dá)到最大。 2、背景模型的思考、背景模型的思考 1）討論：什么叫背景模型）討論：什么叫背景模型 能夠幫助我們理解和記住一些相對(duì)抽象和復(fù)雜問(wèn)題的簡(jiǎn)單問(wèn)題能夠幫助我們理解和記住一些相對(duì)抽象和復(fù)雜問(wèn)題的簡(jiǎn)單問(wèn)題 模型。模型。 2）背景模型的思考）背景模型的思考 利用一些相對(duì)比較簡(jiǎn)單的問(wèn)題來(lái)闡述一些相對(duì)復(fù)雜和抽象的運(yùn)利用一些相對(duì)比較簡(jiǎn)單的問(wèn)題來(lái)闡述一些相對(duì)復(fù)雜和抽象的運(yùn) 籌

26、學(xué)中的一些基礎(chǔ)概念和原理是本課程力求在教學(xué)中體現(xiàn)的第籌學(xué)中的一些基礎(chǔ)概念和原理是本課程力求在教學(xué)中體現(xiàn)的第 一個(gè)特點(diǎn)，希望大家用心體會(huì)。一個(gè)特點(diǎn)，希望大家用心體會(huì)。 1.1.2 1.1.2 線性規(guī)劃數(shù)學(xué)模型的一般表示方式線性規(guī)劃數(shù)學(xué)模型的一般表示方式 技術(shù)系數(shù)右端項(xiàng)價(jià)值系數(shù) 線性規(guī)劃問(wèn)題的規(guī)模 約束行數(shù)變量個(gè)數(shù) : ;: ;: : ;: ;: 0, ),( ),( ),( . )(max(min) 21 2211 22222121 11212111 2211 ijij n mnmnmm nn nn nn abc mn mn xxx bxaxaxa bxaxaxa bxaxaxa ts xcxc

27、xcxf 35 1、和式和式 njx mibxa ts xcxf j i n j jij n j jj , 2 , 1 , 0 , 2 , 1 , . )(max 1 1 36 2、向量式向量式 0 0 0 0 ),( );,( . )(max 2 1 0 2 1 2121 0 1 0 b b b b a a a P xxxXcccC 0X bxP ts CXxf mmj j j j T nn n j jj 37 3、矩陣式矩陣式 00 ,00 ),( ),( );,( . . )(max 21 21 21 21 22221 11211 矩陣表示， T T m T n n mnmm n n b

28、bb xxx ccc aaa aaa aaa ts xf 0 b X C A 0X bAX CX 38 1.1.3 線性規(guī)劃的圖解法線性規(guī)劃的圖解法 1 1 8 7 6 5 4 3 2 2x1876543 O 10 9 x2 A B C E D F G H 1 2 3 f(x)=0 f(x)=1 2 .36)(max , 6, 2: 0, 7 8 102 . 46)(max 21 21 2 21 21 21 xf xx xx x xx xx ts xxxf 最優(yōu)解最優(yōu)解 1 1 8 7 6 5 4 3 2 2x1876543 O 10 9 x2 A B C E D F G H 1 2 3 f(

29、x)=36 線性規(guī)劃問(wèn)題的幾個(gè)特點(diǎn)：線性規(guī)劃問(wèn)題的幾個(gè)特點(diǎn)： 1、線性規(guī)劃的可行域?yàn)橥辜?、線性規(guī)劃的可行域?yàn)橥辜?討論：什么叫凸集？討論：什么叫凸集？ 集合中任意兩點(diǎn)連線上的一切點(diǎn)仍然在該集合中，在平面上集合中任意兩點(diǎn)連線上的一切點(diǎn)仍然在該集合中，在平面上 為凸多邊形，在空間上為凸幾何體；為凸多邊形，在空間上為凸幾何體； 討論：最優(yōu)解在那里取得？討論：最優(yōu)解在那里取得？ 2、線性規(guī)劃的最優(yōu)解一定可在其凸集的某一頂點(diǎn)上達(dá)到；、線性規(guī)劃的最優(yōu)解一定可在其凸集的某一頂點(diǎn)上達(dá)到； 討論：什么情況有最優(yōu)解？最優(yōu)解的存在性條件？討論：什么情況有最優(yōu)解？最優(yōu)解的存在性條件？ 3、線性規(guī)劃若有可行域且其可

30、行域有界，則一定有最優(yōu)解。、線性規(guī)劃若有可行域且其可行域有界，則一定有最優(yōu)解。 上述上述3個(gè)結(jié)論是線性規(guī)劃的個(gè)結(jié)論是線性規(guī)劃的3個(gè)基礎(chǔ)定理，可以用嚴(yán)格的數(shù)學(xué)個(gè)基礎(chǔ)定理，可以用嚴(yán)格的數(shù)學(xué) 方法進(jìn)行證明。我們以簡(jiǎn)單、直觀的圖解法方式給出，相信方法進(jìn)行證明。我們以簡(jiǎn)單、直觀的圖解法方式給出，相信 大家是可以接受的。大家是可以接受的。 1.3 線性規(guī)劃求解的基礎(chǔ)原理和單純形法線性規(guī)劃求解的基礎(chǔ)原理和單純形法 1.3.1 1.3.1 線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形 一、線性規(guī)劃模型一般形式一、線性規(guī)劃模型一般形式 二、求解思路二、求解思路 1 1、規(guī)定一標(biāo)準(zhǔn)型線性的規(guī)劃問(wèn)題數(shù)學(xué)模型；、規(guī)定一標(biāo)

31、準(zhǔn)型線性的規(guī)劃問(wèn)題數(shù)學(xué)模型； 2 2、如何把非標(biāo)準(zhǔn)形的線性規(guī)劃問(wèn)題數(shù)學(xué)模型轉(zhuǎn)化為標(biāo)準(zhǔn)形、如何把非標(biāo)準(zhǔn)形的線性規(guī)劃問(wèn)題數(shù)學(xué)模型轉(zhuǎn)化為標(biāo)準(zhǔn)形 線性規(guī)劃問(wèn)題數(shù)學(xué)模型？線性規(guī)劃問(wèn)題數(shù)學(xué)模型？ 3 3、如何求解標(biāo)準(zhǔn)形線性規(guī)劃問(wèn)題數(shù)學(xué)模型。、如何求解標(biāo)準(zhǔn)形線性規(guī)劃問(wèn)題數(shù)學(xué)模型。 njx mibxa ts xcxf j i n j jij n j jj ,2 , 1 ),0(0 ,2 , 1 ,),( . )(max(min) 1 1 不不限限 三、線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形三、線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形 在上述線性規(guī)劃標(biāo)準(zhǔn)形中，決策變量的個(gè)數(shù)取在上述線性規(guī)劃標(biāo)準(zhǔn)形中，決策變量的個(gè)數(shù)取n+mn+m個(gè)是習(xí)慣表個(gè)是習(xí)慣表

32、示法。我們知道，對(duì)于線性規(guī)劃背景模型，有示法。我們知道，對(duì)于線性規(guī)劃背景模型，有m m個(gè)約束方程，個(gè)約束方程， 且每個(gè)約束方程的不等式均為且每個(gè)約束方程的不等式均為“ ”號(hào)。如果我們?cè)诿總€(gè)約束號(hào)。如果我們?cè)诿總€(gè)約束 方程的左邊加上一個(gè)大于等于方程的左邊加上一個(gè)大于等于0 0的變量，則可將各個(gè)約束方程的變量，則可將各個(gè)約束方程 的的“ ”號(hào)轉(zhuǎn)變?yōu)樘?hào)轉(zhuǎn)變?yōu)椤? =”。此時(shí)，決策變量就有。此時(shí)，決策變量就有n+mn+m個(gè)。個(gè)。 njmixb mibxa ts xcxf ji i mn j jij mn j jj , 2 , 1 , 2 , 1 , 0, , 2 , 1 , . )(max 1 1 4

33、2 四、變換的方法變換的方法 1 1、目標(biāo)函數(shù)為、目標(biāo)函數(shù)為minmin型，價(jià)值系數(shù)一律反號(hào)。令型，價(jià)值系數(shù)一律反號(hào)。令 g(g(x x) = ) = - -f f( (x x) = -) = -CXCX, , 有有 min min f f( (x x) = - max - ) = - max - f f( (x) = - x) = - max gmax g( (x)x) 2 2、第、第i i 個(gè)約束的個(gè)約束的b bi i 為負(fù)值，則該行左右兩端系數(shù)同時(shí)為負(fù)值，則該行左右兩端系數(shù)同時(shí) 反號(hào)，同時(shí)不等號(hào)也要反向反號(hào)，同時(shí)不等號(hào)也要反向 3 3、第、第i i 個(gè)約束為個(gè)約束為 型，在不等式左邊增加

34、一個(gè)非負(fù)的型，在不等式左邊增加一個(gè)非負(fù)的 變量變量x xn+i n+i ， ，稱為松弛變量；同時(shí)令稱為松弛變量；同時(shí)令 c cn+i n+i = 0 = 0 4 4、第、第i i 個(gè)約束為個(gè)約束為 型，在不等式左邊減去一個(gè)非負(fù)的型，在不等式左邊減去一個(gè)非負(fù)的 變量變量x xn+i n+i ， ，稱為剩余變量；同時(shí)令稱為剩余變量；同時(shí)令 c cn+i n+i = 0 = 0 5 5、若、若x xj j 0 0，令 ，令 x xj j= -= -x xj j ，代入非標(biāo)準(zhǔn)型，則有，代入非標(biāo)準(zhǔn)型，則有x xj j 0 0 6 6、若、若x xj j 不限，令 不限，令 x xj j= = x xj

35、j - - x xj j ， x xj j 0 0，x xj j 0 0， 代入非標(biāo)準(zhǔn)型代入非標(biāo)準(zhǔn)型 43 五、五、 變換舉例：變換舉例： 0, , 200 40065 300432 . . 423)(min: 213 321 321 321 321 xxx xxx xxx xxx ts xxxxf 不限 原非標(biāo)準(zhǔn)型 0, 200 400665 3004432 . 0004423)(max: 6543321 63321 53321 43321 6543321 xxxxxxx xxxxx xxxxx xxxxx ts xxxxxxxxf標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型 1.3.2 線性規(guī)劃問(wèn)題的解和基礎(chǔ)定理線性規(guī)劃

36、問(wèn)題的解和基礎(chǔ)定理 本章開(kāi)始到現(xiàn)在已討論的內(nèi)容，相信大部分讀者都會(huì)感到本章開(kāi)始到現(xiàn)在已討論的內(nèi)容，相信大部分讀者都會(huì)感到 比較容易理解和掌握。這一節(jié)我們將要討論關(guān)于線性規(guī)劃比較容易理解和掌握。這一節(jié)我們將要討論關(guān)于線性規(guī)劃 問(wèn)題解的一些基礎(chǔ)概念和定理，與前面討論的內(nèi)容相比，問(wèn)題解的一些基礎(chǔ)概念和定理，與前面討論的內(nèi)容相比， 線性規(guī)劃問(wèn)題解的一些基礎(chǔ)概念略顯難一些，其中比較難線性規(guī)劃問(wèn)題解的一些基礎(chǔ)概念略顯難一些，其中比較難 的概念有線性規(guī)劃問(wèn)題的基和基礎(chǔ)解等相關(guān)概念。為了幫的概念有線性規(guī)劃問(wèn)題的基和基礎(chǔ)解等相關(guān)概念。為了幫 助大家比較容易理解這些概念，我們先從大家熟悉的兩個(gè)助大家比較容易理解這

37、些概念，我們先從大家熟悉的兩個(gè) 變量?jī)蓚€(gè)線性方程組這一簡(jiǎn)單問(wèn)題入手，然后逐步過(guò)渡到變量?jī)蓚€(gè)線性方程組這一簡(jiǎn)單問(wèn)題入手，然后逐步過(guò)渡到 我們所要討論的線性規(guī)劃問(wèn)題的基和基礎(chǔ)解等相關(guān)概念。我們所要討論的線性規(guī)劃問(wèn)題的基和基礎(chǔ)解等相關(guān)概念。 著名數(shù)學(xué)家笛卡爾曾說(shuō)過(guò)，他最擅長(zhǎng)做的兩件事是：著名數(shù)學(xué)家笛卡爾曾說(shuō)過(guò)，他最擅長(zhǎng)做的兩件事是： 1)第一做簡(jiǎn)單事；第一做簡(jiǎn)單事； 2)第二是將復(fù)雜事變?yōu)楹?jiǎn)單事。第二是將復(fù)雜事變?yōu)楹?jiǎn)單事。 本課程將從大家熟悉的一些簡(jiǎn)單問(wèn)題入手，然后逐步過(guò)渡本課程將從大家熟悉的一些簡(jiǎn)單問(wèn)題入手，然后逐步過(guò)渡 到運(yùn)籌學(xué)一些相對(duì)比較抽象和難的概念和原理。這是本課到運(yùn)籌學(xué)一些相對(duì)比較抽象和

38、難的概念和原理。這是本課 程教學(xué)力求的另一特點(diǎn)。程教學(xué)力求的另一特點(diǎn)。 一、線性方程組的解一、線性方程組的解 考慮如下線性方程組的解：考慮如下線性方程組的解： (1) 852 53 21 21 xx xx (2) 2 1 2 1 x x 再考慮如下線性方程組的解：再考慮如下線性方程組的解： (3) 852 53 321 321 xxx xxx (4)2 21 33 32 31 xx xx xx (5) 0 2 1 3 2 1 x x x 一、線性方程組的解一、線性方程組的解 類似地，如果將方程組（類似地，如果將方程組（3 3）中的變量）中的變量x x2 2或或x x1 1當(dāng)成常數(shù)，分別當(dāng)成常數(shù)

39、，分別 移到其方程的右邊后采用消元法進(jìn)行求解，則也可得到如下移到其方程的右邊后采用消元法進(jìn)行求解，則也可得到如下 兩組通解及其特解：兩組通解及其特解： (6) 2 23 22 23 21 xx xx xx (8) 2 1 2 1 2 1 2 3 11 13 12 xx xx xx (7) 0 2 3 2 3 1 x x x (9) 0 2 1 2 3 1 3 2 x x x 一、線性方程組的解一、線性方程組的解 仔細(xì)觀察和思考方程組（仔細(xì)觀察和思考方程組（3 3）的三組通解（）的三組通解（4 4）、（）、（6 6）和）和 （8 8）或三組特解（）或三組特解（5 5）、（）、（7 7）和（）和（

40、9 9）是如何得到的，以）是如何得到的，以 及能夠得到這些通解或特解的條件是什么？根據(jù)求解線性及能夠得到這些通解或特解的條件是什么？根據(jù)求解線性 方程組克萊姆條件可知，能夠得到方程組（方程組克萊姆條件可知，能夠得到方程組（3 3）的通解（）的通解（4 4） 或特解（或特解（5 5）的條件是方程組（）的條件是方程組（3 3）中的變量）中的變量x x1 1和和x x2 2的系數(shù)的系數(shù) 矩陣行列式不等于矩陣行列式不等于0 0，即，即 0-1 52 31 B 1 或變量或變量x x1 1和和x x2 2的系數(shù)矩陣的系數(shù)矩陣B B1 1是非奇異矩陣或變量是非奇異矩陣或變量x x1 1和和x x2 2的的

41、 系數(shù)列向量是線性無(wú)關(guān)。顯然，這三個(gè)條件是等價(jià)的。系數(shù)列向量是線性無(wú)關(guān)。顯然，這三個(gè)條件是等價(jià)的。 一、線性方程組的解一、線性方程組的解 同樣，由于方程組組（同樣，由于方程組組（3 3）中的變量）中的變量x x1 1和和x x3 3的系數(shù)矩陣行列式的系數(shù)矩陣行列式 |B|B2 2| |不等于不等于0 0與變量與變量x x2 2和和x x3 3的系數(shù)矩陣行列式的系數(shù)矩陣行列式|B|B3 3| |不等于不等于0 0，即，即 0-1 12 11 B2 0-1 15 13 B3 才能得到方程組（才能得到方程組（3 3）的通解或特解（）的通解或特解（6 6）或（）或（7 7）與通解或）與通解或 特解（特

42、解（8 8）或（）或（9 9）。）。 將上面討論的方程組（將上面討論的方程組（3 3）加上一目標(biāo)函數(shù)和變量非負(fù)約）加上一目標(biāo)函數(shù)和變量非負(fù)約 束條件后就變成一標(biāo)準(zhǔn)型線性規(guī)劃。如：束條件后就變成一標(biāo)準(zhǔn)型線性規(guī)劃。如： (10) 0,0,0 852 53 . 32)( 321 321 321 321 xxx xxx xxx ts xxxxMaxf 一、線性方程組的解一、線性方程組的解 對(duì)于上述標(biāo)準(zhǔn)型線性規(guī)劃（對(duì)于上述標(biāo)準(zhǔn)型線性規(guī)劃（1010）, ,稱稱 B B1 1 、B B2 2和和B B3 3為線性規(guī)劃為線性規(guī)劃 （1010）的基。因利用其中任何一個(gè)基）的基。因利用其中任何一個(gè)基B B1 1

43、或或B B2 2或或B B3 3，都能得到，都能得到 線性規(guī)劃（線性規(guī)劃（1010）的一組通解和特解（見(jiàn)式（）的一組通解和特解（見(jiàn)式（4 4）-（9 9）。）。 52 31 21 1 xx B 變量變量x x1 1和和x x2 2為基變量，變量為基變量，變量x x3 3為非基變量，令為非基變量，令x x3 3=0=0，得解（，得解（5 5） 為線性規(guī)劃（為線性規(guī)劃（1010）的基礎(chǔ)解，但因該基礎(chǔ)解中）的基礎(chǔ)解，但因該基礎(chǔ)解中x x1 1= -10= -10，不，不 滿足線性規(guī)劃（滿足線性規(guī)劃（1010）的變量非負(fù)約束條件，因此，該基礎(chǔ)）的變量非負(fù)約束條件，因此，該基礎(chǔ) 解（解（5 5）是線性規(guī)

44、劃（）是線性規(guī)劃（1010）的基礎(chǔ)非可行解。）的基礎(chǔ)非可行解。 12 11 31 2 xx B 變量變量x x1 1和和x x3 3為基變量，變量為基變量，變量x x2 2為非基變量，令為非基變量，令x x2 2=0=0，得解（，得解（7 7） 為線性規(guī)劃（為線性規(guī)劃（1010）的基礎(chǔ)解。該基礎(chǔ)解中）的基礎(chǔ)解。該基礎(chǔ)解中x x1 1和和x x3 3均大于均大于0 0，滿，滿 足線性規(guī)劃（足線性規(guī)劃（1010）的變量非負(fù)約束條件，因此，該基礎(chǔ)解（）的變量非負(fù)約束條件，因此，該基礎(chǔ)解（7 7） 是線性規(guī)劃（是線性規(guī)劃（1010）的基礎(chǔ)可行解。）的基礎(chǔ)可行解。 15 13 32 3 xx B 變量變

45、量x x2 2和和x x3 3為基變量，變量為基變量，變量x x1 1為非基變量，令為非基變量，令x x1 1=0=0，得解（，得解（9 9） 為線性規(guī)劃（為線性規(guī)劃（1010）的基礎(chǔ)解）的基礎(chǔ)解. .該基礎(chǔ)解中該基礎(chǔ)解中x x2 2和和x x3 3均大于均大于0 0，滿足，滿足 線性規(guī)劃（線性規(guī)劃（1010）的變量非負(fù)約束條件，因此，該基礎(chǔ)解（）的變量非負(fù)約束條件，因此，該基礎(chǔ)解（9 9） 是線性規(guī)劃（是線性規(guī)劃（1010）的基礎(chǔ)可行解。）的基礎(chǔ)可行解。 二、標(biāo)準(zhǔn)型線性規(guī)劃解的若干基礎(chǔ)概念標(biāo)準(zhǔn)型線性規(guī)劃解的若干基礎(chǔ)概念 標(biāo)準(zhǔn)型有標(biāo)準(zhǔn)型有 n+m 個(gè)變量，個(gè)變量， m 個(gè)約束行個(gè)約束行 “基基

46、”的概念的概念 在標(biāo)準(zhǔn)型中，技術(shù)系數(shù)矩陣有在標(biāo)準(zhǔn)型中，技術(shù)系數(shù)矩陣有 n+m 列，即列，即 A = ( P1, P2 , , Pn+m ) A中線性獨(dú)立的中線性獨(dú)立的 m 列，構(gòu)成該標(biāo)準(zhǔn)型的一個(gè)列，構(gòu)成該標(biāo)準(zhǔn)型的一個(gè)基基，即，即 B = ( P1 , P2 , , Pm )， | B | 0 P1 , P2 , , Pm 稱為稱為基向量基向量 與與基向量基向量對(duì)應(yīng)的變量稱為對(duì)應(yīng)的變量稱為基變量基變量，記為，記為 XB = ( x1 , x2 , , xm )T，其余的變量稱為，其余的變量稱為非基變量非基變量， 記為記為 XN = ( xm+1 , xm+2 , , xm+n ) T ， 故有故

47、有 X = （XB ， ， XN ) 最多有最多有 個(gè)基個(gè)基 m nm C 二、標(biāo)準(zhǔn)型線性規(guī)劃解的若干基礎(chǔ)概念二、標(biāo)準(zhǔn)型線性規(guī)劃解的若干基礎(chǔ)概念 可行解可行解與與非可行解非可行解 滿足約束條件和非負(fù)條件的解滿足約束條件和非負(fù)條件的解 X 稱為稱為可行解可行解，不滿足約束，不滿足約束 條件或非負(fù)條件的解條件或非負(fù)條件的解 X 稱為稱為非可行解非可行解 基礎(chǔ)解基礎(chǔ)解 對(duì)應(yīng)某一基對(duì)應(yīng)某一基B且令其且令其非基變量非基變量 XN = 0，求得，求得基變量基變量 XB的值。的值。 稱稱X = (XB , XN)T為為基礎(chǔ)解。基礎(chǔ)解。 其中其中，XB = B 1 b， XN = 0 XB 是是基礎(chǔ)解基礎(chǔ)解必

48、須滿足如下條件：必須滿足如下條件： 1）非）非0分量的個(gè)數(shù)分量的個(gè)數(shù) m； 2、m個(gè)基變量所對(duì)應(yīng)的系數(shù)矩陣為非奇異的；個(gè)基變量所對(duì)應(yīng)的系數(shù)矩陣為非奇異的； 3、滿足、滿足m個(gè)約束條件。個(gè)約束條件。 二、標(biāo)準(zhǔn)型線性規(guī)劃解的若干基礎(chǔ)概念二、標(biāo)準(zhǔn)型線性規(guī)劃解的若干基礎(chǔ)概念 基礎(chǔ)可行解基礎(chǔ)可行解與與基礎(chǔ)非可行解基礎(chǔ)非可行解 基礎(chǔ)解基礎(chǔ)解 X XB B 的非零分量都 的非零分量都 0 0 時(shí)，稱為時(shí)，稱為基礎(chǔ)可行解基礎(chǔ)可行解，否，否 則為則為基礎(chǔ)非可行解。基礎(chǔ)非可行解。 退化退化解解 基礎(chǔ)可行解的非零分量個(gè)數(shù)基礎(chǔ)可行解的非零分量個(gè)數(shù) f (X(0) )=0 （五）最優(yōu)檢驗(yàn)（五）最優(yōu)檢驗(yàn) 將（將（5）式代

49、入）式代入(1)的目標(biāo)函數(shù)后可得的目標(biāo)函數(shù)后可得 f (X)=30+x2-3x3 （6） 從目標(biāo)函數(shù)（從目標(biāo)函數(shù)（6）可知，非基變量）可知，非基變量x2的系數(shù)是正數(shù)，所以的系數(shù)是正數(shù)，所以X(1) 不是最優(yōu)解。不是最優(yōu)解。 （六）求另一個(gè)更好的基礎(chǔ)可行解（六）求另一個(gè)更好的基礎(chǔ)可行解 64 1、確定換入變量及其值、確定換入變量及其值 從從目標(biāo)函數(shù)（從從目標(biāo)函數(shù)（6）可知，只有非基變量）可知，只有非基變量x2的系數(shù)為正，所以，的系數(shù)為正，所以， 可確定可確定x2為換入變量。為換入變量。 由 于 (7) 07 0 2 1 2 1 3 0 2 1 2 1 5 25 324 321 xx xxx xx

50、x 所以，當(dāng)另一個(gè)非基變量所以，當(dāng)另一個(gè)非基變量x3仍仍 然為然為0時(shí)，由（時(shí)，由（7）式可得到換）式可得到換 入變量入變量x1的值為的值為 x2=Min5/0.5，3/0.5，7/1=6 2、確定換出變量、確定換出變量 從（從（7）式可知，當(dāng)）式可知，當(dāng)x2=6時(shí)，時(shí)，x4=0，所以，所以x4為換出變量。由此得為換出變量。由此得 到線性規(guī)劃（到線性規(guī)劃（1）的一個(gè)新的基）的一個(gè)新的基B2和一組新的基變量與非基變和一組新的基變量與非基變 量。量。 B2=(P1 ,P2 ,P5 ), XB2=（x1，x2，x5)T，XN2=（x3，x4)T 65 3、求另一個(gè)更好的基礎(chǔ)可行解、求另一個(gè)更好的基礎(chǔ)

51、可行解 將（將（1)約束方程中對(duì)應(yīng)于基約束方程中對(duì)應(yīng)于基B2的非基變量的非基變量x3和和x4移到方程的右移到方程的右 邊后可得邊后可得 7 8 102 52 421 321 xx xxx xxx (8) 21 26 2 435 432 431 xxx xxx xxx 令非基變量令非基變量x3=x4=0，可得另一基礎(chǔ)可行解，可得另一基礎(chǔ)可行解 X(2) = (2，6，0，0，1)T 此時(shí)，對(duì)應(yīng)于此時(shí)，對(duì)應(yīng)于X(2)的目標(biāo)函數(shù)的目標(biāo)函數(shù)f (X(2) )=6x1+4x2=36 f (X(1) )=30 （七）最優(yōu)檢驗(yàn)（七）最優(yōu)檢驗(yàn) 將（將（8）式代入）式代入(1)的目標(biāo)函數(shù)后可得的目標(biāo)函數(shù)后可得

52、f (X)=36-2x3-2x4 （9） 從目標(biāo)函數(shù)（從目標(biāo)函數(shù)（9）可知，非基變量）可知，非基變量x3和和x4的系數(shù)都是負(fù)數(shù)，所以的系數(shù)都是負(fù)數(shù)，所以 X(2)是最優(yōu)解。即是最優(yōu)解。即X*= X(2) = (2，6，0，0，1)T ,f (X*)=36 三、求初始基礎(chǔ)可行解（背景模型，三、求初始基礎(chǔ)可行解（背景模型，MAX, ) 66 設(shè)線性規(guī)劃問(wèn)題為設(shè)線性規(guī)劃問(wèn)題為 , 2 , 1 , 0 , 2 , 1 , . . )(max 1 1 njx mibxa ts xcxf j i n j jij n j jj ,2, 1 ,0 ,2, 1 , )(max 1 1 mnjx mibxax x

53、cxf j i mn mj jiji mn j jj 另設(shè)另設(shè)bi 0 (i=1,2,m)。標(biāo)。標(biāo) 準(zhǔn)化后，若對(duì)準(zhǔn)化后，若對(duì)xj和和aij重新編重新編 號(hào)，則約束方程可化為號(hào)，則約束方程可化為 變量變量x1，x2，xm作為初始基變量，其余變量作為初始非作為初始基變量，其余變量作為初始非 基變量，并令基變量，并令xm+1=xm+1=xn+m=0，則得初始本可行解，則得初始本可行解 ),0,0,.,0b., ,b ,(b T m21 (0) X 四、最優(yōu)檢驗(yàn)四、最優(yōu)檢驗(yàn) 67 對(duì)于標(biāo)準(zhǔn)化線性規(guī)劃問(wèn)題對(duì)于標(biāo)準(zhǔn)化線性規(guī)劃問(wèn)題(2)，經(jīng)過(guò)若干次迭代后，如果對(duì)，經(jīng)過(guò)若干次迭代后，如果對(duì)xj及及 aij重新

54、編號(hào)，則約束方程可化為重新編號(hào)，則約束方程可化為 , 2 , 1 1 mixabx mn mj j iji i 其中，其中，bi和和aij表示經(jīng)過(guò)若干次迭代后，當(dāng)前的右端系數(shù)和技表示經(jīng)過(guò)若干次迭代后，當(dāng)前的右端系數(shù)和技 術(shù)系數(shù)，以便區(qū)別于原始的右端系數(shù)術(shù)系數(shù)，以便區(qū)別于原始的右端系數(shù)bi和技術(shù)系數(shù)和技術(shù)系數(shù)aij。將上式。將上式 代入（代入（2）的目標(biāo)函數(shù)后可得）的目標(biāo)函數(shù)后可得 mn mj jjj j m i ij i m i mn mj j i i mn mj jj m i mn mj j iji i xzcz xaccbc xcxabcxf 1 0 1 11 111 )( )( ) ()

55、( 1 0 m i iib cz 1 m i ijij acz 機(jī)會(huì)成本機(jī)會(huì)成本 68 在一般情況下，目標(biāo)函數(shù)值在一般情況下，目標(biāo)函數(shù)值OBJ計(jì)算公式和機(jī)會(huì)成本計(jì)算計(jì)算公式和機(jī)會(huì)成本計(jì)算 公式可寫(xiě)成公式可寫(xiě)成 四、最優(yōu)檢驗(yàn)四、最優(yōu)檢驗(yàn) , 1 0 Ii mk kib czOBJ , 1 0 Ii mk kib czOBJ , 1 Ii mk kjij acz Jj 0 , 1 Ii mk kjijjjj acczc 其中，其中，I為基變量的下標(biāo)集。最優(yōu)檢驗(yàn)條件為為基變量的下標(biāo)集。最優(yōu)檢驗(yàn)條件為 其中，其中，J表示非基變量的下標(biāo)集。對(duì)于基變量的檢驗(yàn)數(shù)為表示非基變量的下標(biāo)集。對(duì)于基變量的檢驗(yàn)數(shù)為

56、0 , 1 ii Ij mk kijiiii ccacczc 因?yàn)榛兞康募夹g(shù)系數(shù)因?yàn)榛兞康募夹g(shù)系數(shù) 滿足：滿足： aij=1, 當(dāng)當(dāng)i=j aij=0, 當(dāng)當(dāng)i j 五、五、 求另一個(gè)更好的基礎(chǔ)可行解求另一個(gè)更好的基礎(chǔ)可行解 69 若某一基礎(chǔ)可行解經(jīng)過(guò)最優(yōu)檢驗(yàn)表明不是最優(yōu)解，若某一基礎(chǔ)可行解經(jīng)過(guò)最優(yōu)檢驗(yàn)表明不是最優(yōu)解， 則需要設(shè)法求得另一個(gè)更好的基礎(chǔ)可行解。求另一則需要設(shè)法求得另一個(gè)更好的基礎(chǔ)可行解。求另一 個(gè)更好的基礎(chǔ)可行解的主要步驟如下：個(gè)更好的基礎(chǔ)可行解的主要步驟如下： 1、確定換入變量；、確定換入變量； 2、確定換出變量；、確定換出變量； 3、通過(guò)基變換或初等變換求得另一個(gè)更好的基

57、礎(chǔ)、通過(guò)基變換或初等變換求得另一個(gè)更好的基礎(chǔ) 可行解。可行解。 我們已在前面例子中說(shuō)明了這種初等變換方法的基我們已在前面例子中說(shuō)明了這種初等變換方法的基 礎(chǔ)思路。下一小節(jié)我們將用單純形表進(jìn)一步說(shuō)明這礎(chǔ)思路。下一小節(jié)我們將用單純形表進(jìn)一步說(shuō)明這 種初等變換方法。種初等變換方法。 70 1.3.4 單純形法表及單純形法單純形法表及單純形法 IV III III x1x2 xnxn+1xn+2xn+m C B X B bc1c2 cncn+1cn+2cn+m c1 = cn+1xn+1b1a11a12 a1n100 c2 = cn+2xn+2b2a21a22 a2n010 cm = cn+mxn+m

58、bmam1am2 amn001 OBJ z1z2 znzn+1zn+2zn+m c1-z1c2-z2 cn-zncn+1-zn+1cn+2-zn+2 cn+m-zn+m 71 例例 試列出下面線性規(guī)劃問(wèn)題的初始單純型表試列出下面線性規(guī)劃問(wèn)題的初始單純型表 0, 120233 10032 . 244540)(max 321 321 321 321 xxx xxx xxx ts xxxxf x1x2x3x4x5 CBXBb 40452400 0 x4 10023110 0 x5 12033201 OBJ = 0 zj00000 cj- -zj40452400 單純形法步驟單純形法步驟 72 1、求

59、初始基礎(chǔ)可行解、求初始基礎(chǔ)可行解 將線性規(guī)劃模型標(biāo)準(zhǔn)化，建立初始單純將線性規(guī)劃模型標(biāo)準(zhǔn)化，建立初始單純 形表，求初始基礎(chǔ)可行解。形表，求初始基礎(chǔ)可行解。 2、最優(yōu)檢驗(yàn)：對(duì)任一基礎(chǔ)可行解、最優(yōu)檢驗(yàn)：對(duì)任一基礎(chǔ)可行解X，若其所有檢驗(yàn)數(shù)，若其所有檢驗(yàn)數(shù) j =cj zj 0，j J 則則X為最優(yōu)解，即為最優(yōu)解，即X*=X，計(jì)算最優(yōu)解所對(duì)應(yīng)的最優(yōu)目標(biāo)函數(shù)值，計(jì)算最優(yōu)解所對(duì)應(yīng)的最優(yōu)目標(biāo)函數(shù)值 f(X*)，算法停止。否則轉(zhuǎn)，算法停止。否則轉(zhuǎn)3。 3、求另一個(gè)更好的基礎(chǔ)可行解、求另一個(gè)更好的基礎(chǔ)可行解 1）確定入變量）確定入變量xk 若若 0 j Jj k Max則則xk為換入變量；為換入變量； 2）確定換

60、出變量）確定換出變量xl* 計(jì)算計(jì)算 ,1 0| lk l ik ik i mi l a b a a b Min 若若 l為空集，則為無(wú)界解，算法停止。否則與右端系數(shù)為空集，則為無(wú)界解，算法停止。否則與右端系數(shù)bl 同一行的同一行的 基變量基變量xl*為換出變量。轉(zhuǎn)為換出變量。轉(zhuǎn)3） 3）初等變換，得到另一個(gè)更好的基礎(chǔ)可行解）初等變換，得到另一個(gè)更好的基礎(chǔ)可行解 將入變量將入變量xk所在列所在列k，出變量，出變量xl*所在行所在行l(wèi)的主元技術(shù)系數(shù)的主元技術(shù)系數(shù)al k變換為變換為1， 主元主元al k 所在列的其余元變換為所在列的其余元變換為0。更換基變量（用入變量。更換基變量（用入變量xk替