A動(dòng)畫(huà)管理系統(tǒng)工程教學(xué)課件第六章線(xiàn)性規(guī)劃

1、管理系統(tǒng)工程第六章 管理系統(tǒng)決策定量分析模型：線(xiàn)性規(guī)劃 第一節(jié) 線(xiàn)性規(guī)劃模型、實(shí)例及求解 第二節(jié) 線(xiàn)性規(guī)劃模型求解的一般方法：?jiǎn)渭冃畏?第三節(jié) 線(xiàn)性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題，對(duì)偶單純形法 第四節(jié) 線(xiàn)性規(guī)劃問(wèn)題的靈敏性分析 第五節(jié) 多目標(biāo)規(guī)劃法中的目的規(guī)劃法簡(jiǎn)介（六）10/10/20221【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)管理系統(tǒng)工程第六章 管理系統(tǒng)決策定量分析模型：線(xiàn)性規(guī)第一節(jié) 線(xiàn)性規(guī)劃模型、實(shí)例及求解一、線(xiàn)性規(guī)劃予以解決的實(shí)際問(wèn)題 1、資源給定，如何對(duì)給定資源予以充分地、合理地運(yùn)用，使之完成的任務(wù)盡可能地多。 2、任務(wù)給定，如何以盡可能少的資源消耗來(lái)完成給定的任務(wù)。 可見(jiàn)，上述兩類(lèi)問(wèn)題都是尋求利

2、潤(rùn)最大。第一類(lèi)，是以最大收益扣除定 量成本；第二類(lèi)，是以定量收益扣除最小成本。10/10/20222【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)第一節(jié) 線(xiàn)性規(guī)劃模型、實(shí)例及求解10/9/20222【二、線(xiàn)性規(guī)劃的定義： 當(dāng)收益和消耗均與計(jì)劃指標(biāo)成正比時(shí)，一個(gè)規(guī)劃問(wèn)題所列出的數(shù)學(xué)表達(dá) 式都是關(guān)于計(jì)劃指標(biāo)的線(xiàn)性關(guān)系式，稱(chēng)此類(lèi)型規(guī)劃問(wèn)題為線(xiàn)性規(guī)劃問(wèn)題。 線(xiàn)性規(guī)劃問(wèn)題是：在一組線(xiàn)性約束條件下，求一組非負(fù)變量得值，使一 個(gè)線(xiàn)性目標(biāo)函數(shù)達(dá)到最大或者是最小。 10/10/20223【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)二、線(xiàn)性規(guī)劃的定義：10/9/20223【第六章：線(xiàn)性規(guī)劃*三、線(xiàn)性規(guī)劃的數(shù)學(xué)模型 例1： 某廠(chǎng)擬定

3、利用三種資源：鑄件、鍛件、加工人時(shí)生產(chǎn)A、B兩種型號(hào)的設(shè) 備。已知資料如下表所示： 求總銷(xiāo)售額最大的生產(chǎn)計(jì)劃方案。4萬(wàn)元/臺(tái)6萬(wàn)元/臺(tái)設(shè)備售價(jià)120（百人時(shí)）24加工人時(shí)100（噸）32鍛件270（噸）93鑄件資源量BA10/10/20224【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)三、線(xiàn)性規(guī)劃的數(shù)學(xué)模型4萬(wàn)元/臺(tái)6萬(wàn)元/臺(tái)設(shè)備售價(jià)120（百 例1的模型（LP） 根據(jù)以上資料，建立（LP）模型如下： （設(shè)A設(shè)備生產(chǎn)x1臺(tái)；B設(shè)備生產(chǎn)x2臺(tái)）1目標(biāo)函數(shù)2約束條件該模型的解為生產(chǎn)計(jì)劃10/10/20225【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà) 例1的模型（ （LP）模型的形式： 1、矩陣形式 記： C =

4、（c1、c2、c3、cn） X =（x1、x2、x3、xn）T A =（aij）mn b =（b1、b2、b3、bm）T 則（LP）模型的矩陣形式為：價(jià)值系數(shù)行向量決策變量列向量技術(shù)系數(shù)矩陣資源限定列向量10/10/20226【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà) （LP）模型的形2、極大化典型形式（實(shí)際問(wèn)題一）3、極小化典型形式（實(shí)際問(wèn)題二）10/10/20227【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)2、極大化典型形式（實(shí)際問(wèn)題一）10/9/20227【第六章 4、標(biāo)準(zhǔn)型形式（模型求解的基礎(chǔ)）10/10/20228【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)10/9/20228【第六章：線(xiàn)性規(guī)劃*48*

5、】 （LP）問(wèn)題的基本術(shù)語(yǔ) 1、變量 決策變量：對(duì)需要優(yōu)化的經(jīng)濟(jì)量所設(shè)置的變量稱(chēng)之。 附加變量：為求解（LP）模型所引入的變量稱(chēng)之。 （1）松弛變量：為處理約束條件所引入，又分為不 足 變量和剩余變量 （2）人工變量：為人為地制造一個(gè)基而引入的變量10/10/20229【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)（LP）問(wèn)題的基本術(shù)語(yǔ)10/9/20229【第六章：線(xiàn)性規(guī)劃2、目標(biāo)函數(shù)；約束條件 3、（LP）模型的解的概念 可行解：稱(chēng)滿(mǎn)足約束條件的解為可行解。 最優(yōu)解：能使目標(biāo)函數(shù)得以滿(mǎn)足的可行解稱(chēng)之為最優(yōu)解。10/10/202210【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)10/9/202210【第六章：線(xiàn)

6、性規(guī)劃*48*】 （LP）模型圖解法x*1=20（臺(tái)）、x*2=20（臺(tái)）Z*=200（萬(wàn)元）10/10/202211【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)（LP）模型圖解法x*1=20（臺(tái)）、x*2=20（臺(tái)）10圖形放大10/10/202212【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)圖形放大10/9/202212【第六章：線(xiàn)性規(guī)劃*48*】 （LP）模型圖解法之步驟10/10/202213【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)（LP）模型圖解法之步驟10/9/202213【第六章：線(xiàn)性 圖解法之結(jié)論： （1）（LP）模型的可行解域?yàn)橐粋€(gè)凸多邊形或凸多面體，它們的極 點(diǎn)為有限多個(gè)。 （2）（LP）模

7、型的最優(yōu)解如果存在，一定可以在凸集合的極點(diǎn)上得 到。 （ 3）若（LP）模型的最優(yōu)解在一個(gè)極點(diǎn)上得到，則該模型最優(yōu)解唯 一；若在兩個(gè)極點(diǎn)上同時(shí)取得，則該模型有多重最優(yōu)解。 （4）若作圖以后；滿(mǎn)足各約束條件的共同部分不存在，則該模型無(wú)可 行解。 （5）若找不到離目標(biāo)函數(shù)線(xiàn)距離最遠(yuǎn)的可行解點(diǎn)，則該模型無(wú)有限最 優(yōu)解。（開(kāi)區(qū)域時(shí)發(fā)生）10/10/202214【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà) 1、線(xiàn)性規(guī)劃模型的一般形式10/10/202215【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)10/9/202215【第六章：線(xiàn)性規(guī)劃*48*】 （LP）模型間相互轉(zhuǎn)換的規(guī)則1、2、3、4、5、10/10/20221

8、6【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)（LP）模型間相互轉(zhuǎn)換的規(guī)則10/9/202216【第六章：第二節(jié) （LP）模型求解的單純形法一、單純形法的基本思想： 單純形法的基本思想是從有限個(gè)基本可行解中選擇幾個(gè)予以比較，從 而得到最優(yōu)解。二、單純形法的求解步驟： 1、以最簡(jiǎn)單的方法確定第一個(gè)基本可行解 2、判斷該解是否最優(yōu)，若是最優(yōu)則最優(yōu)解得到，若不是最優(yōu)解則進(jìn)行下一步 3、在保證目標(biāo)函數(shù)至少不減（目標(biāo)函數(shù)求最大值模型）的前提下，轉(zhuǎn)換到另 一個(gè)基本可行解上 4、重復(fù)判斷步驟，直至尋找到最優(yōu)解10/10/202217【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)第二節(jié) （LP）模型求解的單純形法10/9/20

9、2217三、 （LP）模型解的概念的擴(kuò)充 基矩陣、非基矩陣、基向量、非基向量 （口述） 基變量、非基變量 基向量對(duì)應(yīng)的變量稱(chēng)之為基變量，非基向量對(duì)應(yīng)的變量稱(chēng)之為非基變量。 基本解 當(dāng)取定一個(gè)基以后，令全部的非基變量等于零，從方程組中解出基變量得值，由它們構(gòu)成的解： X=（x1、x2、xj、xn)T稱(chēng)之為一個(gè)基本解。 顯然，基本解的個(gè)數(shù)為有限多個(gè)，最多為 個(gè)。 基本可行解 滿(mǎn)足非負(fù)要求的基本解稱(chēng)之為基本可行解。10/10/202218【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)三、 （LP）模型解的概念的擴(kuò)充10/9/202218【第六四、單純形法求解步驟及單純形表結(jié)構(gòu)特征 求解步驟： 1、將模型變?yōu)闃?biāo)

10、準(zhǔn)型，列初表 2、判斷解是否最優(yōu)（判斷準(zhǔn)則：全部的j0則達(dá)優(yōu)），若不是最優(yōu)則 進(jìn)行下一步 3、進(jìn)行解的轉(zhuǎn)換 （1）確定基準(zhǔn)列第k列（確定進(jìn)基變量） k=maxj （j0） （2）確定基準(zhǔn)行第l行（確定退基變量） l=mini i=bi/aik （aik0） （3）確定主元素：基準(zhǔn)行與基準(zhǔn)列交叉處的元素 （4）進(jìn)行矩陣的初等行變換，變換的目標(biāo)是： “ 基準(zhǔn)列的主元素變?yōu)?；其余的元素變?yōu)?” 4、重復(fù)判斷步驟，直至尋求到最優(yōu)解10/10/202219【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)四、單純形法求解步驟及單純形表結(jié)構(gòu)特征10/9/202219一、利用鑄件、鍛件、加工人時(shí)生產(chǎn)AB設(shè)備之例求解單純

11、形表10/10/202220【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)一、利用鑄件、鍛件、加工人時(shí)生產(chǎn)AB設(shè)備之例求解單純形表10例1求解的結(jié)論共搜索了三個(gè)基本可行解 X（1）=（0、0、270、100、120） X（2）=（30、0、180 、40、0） X（3）=（20、20、30、0、0）最優(yōu)解為： X*= （20、20、30、0、0） 即：A、B設(shè)備各自生產(chǎn)20臺(tái) 最大銷(xiāo)售收入為： Z*=200（萬(wàn)元） 10/10/202221【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)例1求解的結(jié)論共搜索了三個(gè)基本可行解10/9/202221【單純形表的結(jié)構(gòu)特征 1、所有單純形表共有特征 （1）基變量的列系數(shù)均為

12、單位向量 （2）基變量的檢驗(yàn)數(shù)均為零 （3）最右邊的常量均大于等于零 2、最終單純形表的特征（要會(huì)識(shí)別最終表） （1）基變量的列系數(shù)均為單位向量 （2）基變量的檢驗(yàn)數(shù)均為零 （3）最右邊的常量均大于等于零 （4）檢驗(yàn)數(shù)行全部小于等于零10/10/202222【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)單純形表的結(jié)構(gòu)特征10/9/202222【第六章：線(xiàn)性規(guī)劃*學(xué)生練習(xí)題1 用單純形法求解10/10/202223【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)學(xué)生練習(xí)題1 用單純形法求解10/9/202223【10/10/202224【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)10/9/202224【第六章：線(xiàn)性規(guī)劃*48

13、*】 學(xué)生練習(xí)題2用單純形法求解10/10/202225【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)學(xué)生練習(xí)題2用單純形法求解10/9/202225【第六章：線(xiàn)10/10/202226【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)10/9/202226【第六章：線(xiàn)性規(guī)劃*48*】 五、用矩陣形式表出的單純形表 公式（1）某非基變量檢驗(yàn)數(shù)計(jì)算公式： j=Cj-CBB-1Pj （2）某非基變量列系數(shù)計(jì)算公式： Pj*=B-1Pj10/10/202227【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)五、用矩陣形式表出的單純形表10/9/202227【第六章：一、利用鑄件、鍛件、加工人時(shí)生產(chǎn)AB設(shè)備之例求解單純形表10/10/2

14、02228【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)一、利用鑄件、鍛件、加工人時(shí)生產(chǎn)AB設(shè)備之例求解單純形表10六、利用Excel Solver對(duì)線(xiàn)性規(guī)劃模型求解 步驟： 1、在電子表格中確定目標(biāo)單元格、活動(dòng)單元格，輸入所有參數(shù) （aij、bi、cj） 2、利用數(shù)據(jù)組相乘公式（常用函數(shù)里SUMPRODUCT）確定好約束條件的左邊對(duì)應(yīng)的單元格 3、打開(kāi)工具（T）欄里的規(guī)劃求解 （1）給定目標(biāo)單元格、活動(dòng)單元格，求最大 （2）添加約束條件 （3）選項(xiàng)欄里：線(xiàn)性、非負(fù)，確定 （4）求解得下表鏈接10/10/202229【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)六、利用Excel Solver對(duì)線(xiàn)性規(guī)劃模型求解鏈

15、接10/利用Excel Solver對(duì)（LP）模型例1求解鏈接10/10/202230【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)利用Excel Solver對(duì)（LP）模型例1求解鏈接10/物質(zhì)配送問(wèn)題之例例3： 兩個(gè)工廠(chǎng)生產(chǎn)同一種新產(chǎn)品，配送公司將該產(chǎn)品送到兩個(gè)倉(cāng)庫(kù)。運(yùn)送情況如 下： 1、工廠(chǎng)1的產(chǎn)品通過(guò)鐵路只能送到倉(cāng)庫(kù)1，產(chǎn)品的數(shù)量不限，單位運(yùn)輸成本為700元/單位。 2、工廠(chǎng)2的產(chǎn)品通過(guò)鐵路只能送到倉(cāng)庫(kù)2，產(chǎn)品的數(shù)量不限，單位運(yùn)輸成本為900元/單位。 3、卡車(chē)可將多達(dá)50個(gè)單位的產(chǎn)品由工廠(chǎng)送到配送中心，再?gòu)呐渌椭行囊宰疃?0個(gè)單位的載運(yùn)量運(yùn)到各倉(cāng)庫(kù)，其單位運(yùn)費(fèi)如圖所示。 4、各廠(chǎng)的生產(chǎn)量、各倉(cāng)

16、庫(kù)的所需量如圖所示。 求最低運(yùn)輸成本對(duì)應(yīng)的運(yùn)輸方案。10/10/202231【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)物質(zhì)配送問(wèn)題之例例3：10/9/202231【第六章：線(xiàn)性規(guī)例3的配送網(wǎng)絡(luò)示意圖配送中心倉(cāng)庫(kù)2工廠(chǎng)2倉(cāng)庫(kù)1工廠(chǎng)1生產(chǎn)70單位需要90單位生產(chǎn)80單位需要60單位700/單位900/單位圖三：配送公司配送網(wǎng)絡(luò)300/單位200/單位400/單位400/單位最多50單位最多50單位最多50單位最多50單位10/10/202232【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)例3的配送網(wǎng)絡(luò)示意圖配送中心倉(cāng)庫(kù)2工廠(chǎng)2倉(cāng)庫(kù)1工廠(chǎng)1生產(chǎn)70例3的變量設(shè)置 設(shè)： x1工廠(chǎng)1至倉(cāng)庫(kù)1的運(yùn)輸量 x2工廠(chǎng)2至倉(cāng)庫(kù)

17、2的運(yùn)輸量 x3工廠(chǎng)1至配送中心的運(yùn)輸量 x4工廠(chǎng)2至配送中心的運(yùn)輸量 x5配送中心至倉(cāng)庫(kù)1的運(yùn)輸量 x6配送中心至倉(cāng)庫(kù)2的運(yùn)輸量 根據(jù)條件分析建立模型如下：10/10/202233【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)例3的變量設(shè)置 設(shè)：10/9/20223例3的配送網(wǎng)絡(luò)示意圖配送中心倉(cāng)庫(kù)2工廠(chǎng)2倉(cāng)庫(kù)1工廠(chǎng)1生產(chǎn)70單位需要90單位生產(chǎn)80單位需要60單位700/單位900/單位圖三：配送公司配送網(wǎng)絡(luò)300/單位200/單位400/單位400/單位最多50單位最多50單位最多50單位最多50單位x1x3x4x2x5x610/10/202234【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)例3的配送網(wǎng)絡(luò)示

18、意圖配送中心倉(cāng)庫(kù)2工廠(chǎng)2倉(cāng)庫(kù)1工廠(chǎng)1生產(chǎn)70例3的（LP）模型10/10/202235【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)例3的（LP）模型10/9/202235【第六章：線(xiàn)性規(guī)劃*例3Excel Solver求解10/10/202236【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)例3Excel Solver求解10/9/202236【第六例3求解結(jié)果：運(yùn)輸方案 x1 工廠(chǎng)1倉(cāng)庫(kù)1：x*1=30 x2 工廠(chǎng)2倉(cāng)庫(kù)2：x*2=40 x3 工廠(chǎng)1配送中心：x*3=50 x4 工廠(chǎng)2配送中心：x*4=30 x5 配送中心倉(cāng)庫(kù)1：x*5=30 x6 配送中心倉(cāng)庫(kù)2：x*6=50 Z 總運(yùn)費(fèi) 最小總運(yùn)費(fèi)為： Z

19、min=110000（費(fèi)用單位）10/10/202237【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)例3求解結(jié)果：運(yùn)輸方案 x1 工廠(chǎng)1倉(cāng)庫(kù)1第三節(jié) 線(xiàn)性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題，對(duì)偶單純形法 一、線(xiàn)性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題的提出 1、原問(wèn)題（LP） 例1中的鑄件、鍛件、加工人時(shí)用于生產(chǎn)A、B兩種設(shè)備，出讓 設(shè)備以后獲得銷(xiāo)售收入，將這樣考慮的問(wèn)題稱(chēng)之為原問(wèn)題。 2、對(duì)偶問(wèn)題（LD） 將例1中的鑄件、鍛件、加工人時(shí)制定相應(yīng)的價(jià)格y1、y2、y3， 直接出讓資源獲得收入，將這樣考慮的問(wèn)題稱(chēng)之為原問(wèn)題的對(duì)偶問(wèn) 題。10/10/202238【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)第三節(jié) 線(xiàn)性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題，對(duì)偶單純形法

20、10/9/二、對(duì)偶模型及對(duì)偶模型的建立 該模型稱(chēng)之為原模型（LP）的對(duì)偶模型，記為：（LD） （y1 、y2 、y3的設(shè)置及含義解釋一下）10/10/202239【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)二、對(duì)偶模型及對(duì)偶模型的建立10/9/202239【第六章：三、原模型（LP）與其對(duì)偶模型（LD）模型間的關(guān)系 1、原模型為極大化典型形式，則其對(duì)偶模型為極小化典型形式： 2、（LP）與（LD）的系數(shù)矩陣互為轉(zhuǎn)置 3、（LP）為m個(gè)約束條件， （LD）有m個(gè)決策變量 4、（LP）為n個(gè)決策變量, （LD）有n個(gè)約束條件 5、一個(gè)模型的變量非負(fù)，則另一模型的約束條件為不等式 6、一個(gè)模型的變量為自由變

21、量，則另一模型的約束條件為等式10/10/202240【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)三、原模型（LP）與其對(duì)偶模型（LD）模型間的關(guān)系10/9/兩個(gè)模型對(duì)比原模型對(duì)偶模型10/10/202241【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)兩個(gè)模型對(duì)比原模型對(duì)偶模型10/9/202241【第六章：線(xiàn)四、對(duì)偶問(wèn)題的性質(zhì) 1、對(duì)稱(chēng)性：（LP）與（LD）互為對(duì)偶 2、弱對(duì)偶定理：若X(0)，Y(0)分別是原問(wèn)題和其對(duì)偶問(wèn)題的任一可行解， 則有：CX(0)Y(0)b 該性質(zhì)說(shuō)明：兩個(gè)模型的目標(biāo)函數(shù)值互為界。10/10/202242【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)四、對(duì)偶問(wèn)題的性質(zhì) 10/9/20224

22、2【第六章：線(xiàn)性規(guī)劃 3、設(shè) X* 、Y* 分別為（LP）與（LD）的某一可 行 解， 當(dāng)CX*=Y*b時(shí)，則 X*、Y*分別為（LP）與（LD）的最優(yōu)解。 4、檢驗(yàn)數(shù)與解之間的對(duì)應(yīng)關(guān)系： （1）原模型單純形表上檢驗(yàn)數(shù)的相反數(shù)對(duì)應(yīng)著其對(duì)偶模型的一個(gè)基本 解。 （2）原模型最終單純形表上檢驗(yàn)數(shù)的相反數(shù)對(duì)應(yīng)著其對(duì)偶模型的最優(yōu) 解。10/10/202243【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà) 10/9/202243【第六章：線(xiàn)性規(guī)劃*48具體的對(duì)應(yīng)規(guī)則：（以最終表為例，其余表規(guī)則相同）（a）原模型松弛變量檢驗(yàn)數(shù)的相反數(shù)對(duì)應(yīng)著其對(duì)偶模型的決策變量的值；（b）原模型決策變量檢驗(yàn)數(shù)的相反數(shù)對(duì)應(yīng)著其對(duì)偶模型

23、的松弛變量的值。 由例1的最終表可得： Y*=（0 1/2 5/4 0 0） W*=2700+1001/2+1205/4=200（萬(wàn)元）最終單純型表64000 x1x2x3x4x5bi0 x1001-15/49/8304x20101/2-1/4206x3100-1/43/820zj6401/25/4j000-1/2-5/410/10/202244【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)具體的對(duì)應(yīng)規(guī)則：（以最終表為例，其余表規(guī)則相同）最終單純型表10/10/202245【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)10/9/202245【第六章：線(xiàn)性規(guī)劃*48*】 五、對(duì)偶決策變量y*i 的經(jīng)濟(jì)含義 1、在給

24、定資源最優(yōu)配置時(shí)， y*i為單位第i種資源的增加給目標(biāo)函數(shù)所帶來(lái)的貢獻(xiàn)。（邊際貢獻(xiàn)） 2、 y*i稱(chēng)之為在給定資源最優(yōu)配置時(shí)第i種資源的影子價(jià)格，影子價(jià)格是在給定資源最優(yōu)配置時(shí)對(duì)第i種資源的一種估價(jià)。 3、 y*i可理解為是可以利用的現(xiàn)行市場(chǎng)價(jià)格（邊際成本）的最高限度。 例如：y*2=1/2，則現(xiàn)行市場(chǎng)價(jià)格小于1/2時(shí)，對(duì)鍛件可以適當(dāng)予以增 加；若現(xiàn)行市場(chǎng)價(jià)格大于1/2時(shí)，對(duì)鍛件不能予以增加。 4、 y*i=0的資源稱(chēng)之為富裕資源； y*i0的資源稱(chēng)之為緊缺資源。 5、需注意的問(wèn)題（口述）10/10/202246【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)五、對(duì)偶決策變量y*i 的經(jīng)濟(jì)含義10/9/2

25、02246【第五、對(duì)偶單純形法 單純形法：保持原問(wèn)題的解（B-1b）為可行解，讓其對(duì)偶問(wèn)題的解 （CBB-1A-C）由非可行解逐步變化到可行解 對(duì)偶單純形法：保持對(duì)偶問(wèn)題的解為可行解（CBB-1A-C0） ，讓原問(wèn)題 的解（B-1b）由非可行解逐步變化到可行解 CBB-1A-C=（0，CBB-1N-CN，CBB-1） 為全部的檢驗(yàn)數(shù)，即對(duì)偶問(wèn)題的解XBXNXLB-1bIB-1NB-1檢驗(yàn)數(shù)0CBB-1N-CNCBB-110/10/202247【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)五、對(duì)偶單純形法XBXNXLB-1bIB-1NB-1檢驗(yàn)數(shù)0對(duì)偶單純形法的步驟（參看例14） 第一步：列初始單純形表

26、第二步：確定基準(zhǔn)行（找出(B-1b)r=min(B-1b)i| (B-1b)i0，即bi列中負(fù)值中的 最小者，則第r行為基準(zhǔn)行，xr為退基變量。 若bi列中沒(méi)有負(fù)值， 則已得最優(yōu)解） 第三步：確定基準(zhǔn)列，先計(jì)算： 則第s列為基準(zhǔn)列，xs為進(jìn)基變量 若基準(zhǔn)行沒(méi)有負(fù)值，則該問(wèn)題無(wú)可行解 第四步：以基準(zhǔn)行、基準(zhǔn)列交叉處的元素為主元素，進(jìn)行初等行變換，得新的單 純形表后返回第二步。10/10/202248【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)對(duì)偶單純形法的步驟（參看例14）10/9/202248【第六例14 用對(duì)偶單純形法求解下述線(xiàn)性規(guī)劃模型 解：將模型化為標(biāo)準(zhǔn)型Y*=（0，3/2，1/8，0） Z*=

27、83/2+161/8=14 Z*=Z 用對(duì)偶單純形法求解的最優(yōu)解：10/10/202249【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)例14 用對(duì)偶單純形法求解下述線(xiàn)性規(guī)劃模型Y*=（0，例14對(duì)偶單純行法求解表10/10/202250【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)例14對(duì)偶單純行法求解表10/9/202250【第六章：線(xiàn)性第四節(jié) 線(xiàn)性規(guī)劃問(wèn)題靈敏性分析 一、線(xiàn)性規(guī)劃問(wèn)題靈敏性分析的內(nèi)容 1、參數(shù)bi、cj發(fā)生改變問(wèn)題的分析 2、新增加一個(gè)約束條件問(wèn)題的分析 3、新增加一個(gè)決策變量問(wèn)題的分析 二、參數(shù)bi發(fā)生改變問(wèn)題的分析 1、bi參數(shù)發(fā)生改變的實(shí)際原因 2、求bi的允許范圍的前提條件（保持原各

28、資源的影子價(jià)格不變） 3、bi的確定過(guò)程（參看例子） 4、對(duì)第i種資源考慮予以增減的步驟（口述）10/10/202251【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)第四節(jié) 線(xiàn)性規(guī)劃問(wèn)題靈敏性分析10/9/202251【參數(shù)bi發(fā)生改變問(wèn)題的分析bi的確定過(guò)程之例：求b2最初單純型表64000 x1x2x3x4x5bi0 x3931002700 x4320101000 x524001120zj00000j64000最終單純型表64000 x1x2x3x4x5bi0 x3001-15/49/8304x20101/2-1/4206x1100-1/43/820zj6401/25/4j000-1/2-5/410

29、/10/202252【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)參數(shù)bi發(fā)生改變問(wèn)題的分析bi的確定過(guò)程之例：求b2處理如下：最初單純型表64000 x1x2x3x4x5bi0 x393100270+0b20 x432010100+1b20 x524001120+0b2zj00000j64000最終單純型表64000 x1x2x3x4x5bi0 x3001-15/49/830-15/4b24x20101/2-1/420+1/2b26x1100-1/43/820-1/4b2zj6401/25/4j000-1/2-5/410/10/202253【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)處理如下：最初單純型表64

30、000 x1x2x3x4x5bi0 x bi的確定過(guò)程之例：求b2（其他資源量不變） 1、設(shè)法確定出最終表上常量與b2的關(guān)系： 2、要不改變影子價(jià)格，則要仍然為最終表，故要求： 3、聯(lián)立上述不等式解之得： 10/10/202254【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà) bi的確定過(guò)b2=20時(shí)0 x30 0 1 -3 3/41 1/8-45 4 x20 1 0 1/2- 1/430 6 x11 0 0 - 1/4 3/815 zi6 4 0 1/21 1/4j0 0 0 - 1/2-1 1/40 x40 0 - 4/151 - 3/1012 4 x20 1 2/150 - 1/1024 6 x1

31、1 0 - 1/150 3/1018 zi6 4 2/150 1 2/5 j0 0 - 2/150 -1 2/5 當(dāng)b2=20時(shí)，超范圍，右邊出現(xiàn)負(fù)數(shù)，用對(duì)偶單純型法處理一次得： 新的最優(yōu)解：x1=18 ， x2=24 ， Z*=618+424=204 （81/2） x4=12表明：增加的20單位的鍛件多出12個(gè)單位，只能配置8個(gè)單位。10/10/202255【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)b2=20時(shí)0 x30 0 三、參數(shù)cj發(fā)生改變問(wèn)題的分析 1、cj參數(shù)發(fā)生改變的實(shí)際原因 2、求cj的允許范圍的前提條件（保持原最優(yōu)解不變） 3、cj的確定過(guò)程（參看例子）最終單純型表64000 x1

32、x2x3x4x5bi0 x3001-15/49/8304x20101/2-1/4206x1100-1/43/820zj6401/25/4j000-1/2-5/410/10/202256【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)三、參數(shù)cj發(fā)生改變問(wèn)題的分析最終單純型表64000 x1x2最終單純型表6 +c14000 x1x2x3x4x5bi0 x3001-15/49/8304x20101/2-1/4206+c1x1100-1/43/820zj6 +c1401/2 -1/4c15/4 +3/8c1j000-1/2 +1/4c1-5/4 -3/8c110/10/202257【第六章：線(xiàn)性規(guī)劃*48*】

33、 有動(dòng)畫(huà)最終單純型表6 +c14000 x1x2x3x4x5bi0 x cj的確定過(guò)程之例：求c1（余下的cj不變） 1、確定出原終表上-1/2、-5/4與c1的關(guān)系： 2、要保持原最優(yōu)解不變，則要仍然為最終表，故要求檢驗(yàn)數(shù)行全部小于等于零，即： 3、聯(lián)立上述不等式組解之得： 10/10/202258【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà) cj的確定過(guò)程之例：求c1（余下的cj不變）10/9關(guān)于bi 、cj的確定可用靈敏性分析報(bào)告10/10/202259【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)關(guān)于bi 、cj的確定可用靈敏性分析報(bào)告10/9/202四、新增加一個(gè)約束條件問(wèn)題的分析 1、新增加一個(gè)約束

34、條件后原最優(yōu)解受到影響否的判斷 2、若原最優(yōu)解受到影響，新的最優(yōu)解的確定 判定方法一：將原最優(yōu)解帶入新增約束條件，若滿(mǎn)足，則原解不變；若 不滿(mǎn)足，則原解要變。 判定方法二：在原最終表上加一行、一列后，將基變量的列系數(shù)變?yōu)閱?位向量，若右邊沒(méi)有出現(xiàn)負(fù)數(shù)，則原解不變；若右邊出行 負(fù)數(shù)，則原解要變。 當(dāng)右邊出現(xiàn)負(fù)數(shù)時(shí)，用對(duì)偶單純型法處理之，可得新的最優(yōu)解。10/10/202260【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)四、新增加一個(gè)約束條件問(wèn)題的分析10/9/202260【第六例：電力資源約束：?jiǎn)挝幌模? ，3 電力可用總量： 若為180萬(wàn)千瓦小時(shí) 若為151萬(wàn)千瓦小時(shí) 當(dāng)電力總量為180萬(wàn)千瓦小時(shí)時(shí)

35、，兩種方法判定結(jié)論：原方案不變； 當(dāng)電力總量為151萬(wàn)千瓦小時(shí)時(shí)，兩種方法判定結(jié)論：原方案要變； 由方法二判定后，在判定的基礎(chǔ)上，用對(duì)偶單純型法處理可得新的最優(yōu) 解為： x1=17 ， x2=22 ， Z*=19010/10/202261【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)例：電力資源約束：?jiǎn)挝幌模? ，3 電力可用總量：640000 x1x2x3x4x5x60 x30 0 1 -3 3/41 1/80 30 4 x20 1 0 1/2- 1/40 20 6 x11 0 0 - 1/4 3/80 20 0 x6530001 151zi6 4 0 1/21 1/4j0 0 0 - 1/2-1

36、1/40 x30 0 1 -3 3/41 1/80 30 4 x20 1 0 1/2- 1/40 20 6 x11 0 0 - 1/4 3/80 20 0 x60 0 0 - 1/4-1 1/81 -9 1、變5為00 3 0 1 1/4-1 7/81 51 zi6 4 0 1/21 1/40 j0 0 0 - 1/2-1 1/40 0 x30 0 1 -4 0 1 21 4 x20 1 0 5/90 - 2/922 6 x11 0 0 - 1/30 1/317 0 x50 0 0 2/91 - 8/98 zi6 4 0 2/90 1 1/9j0 0 0 - 2/90 -1 1/910/10/

37、202262【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)640000 x1x2x3x4x5x60 x五、新增加一個(gè)決策變量問(wèn)題的分析 1、新增加一個(gè)決策變量以后原最優(yōu)解改變否的判斷 通過(guò)計(jì)算新決策變量（此時(shí)為非基變量）的檢驗(yàn)數(shù)來(lái)判定 2、若原最優(yōu)解改變，新的最優(yōu)解的確定 用單純型法來(lái)確定10/10/202263【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)五、新增加一個(gè)決策變量問(wèn)題的分析10/9/202263【第六P6488156400011x1x2x3x4x5x60 x30 0 1 -3 3/41 1/830 4 x20 1 0 1/2- 1/420 6 x11 0 0 - 1/4 3/8B-1P620 zi

38、6 4 0 1/21 1/4j0 0 0 - 1/2-1 1/46=？-3 c6=11的6P6（488）1 c6=15的6 當(dāng)c6=11時(shí)，新產(chǎn)品不投產(chǎn)，因?yàn)?= - 3 ； 當(dāng)c6=15時(shí)，新產(chǎn)品要投產(chǎn)，因?yàn)?= 1 新產(chǎn)品 投產(chǎn)多少，用單純型法予以處理可得出10/10/202264【第六章：線(xiàn)性規(guī)劃*48*】 有動(dòng)畫(huà)P6488156400011x1x2x 案例分析（案例一）李P175 某五金廠(chǎng)利用金屬薄板等資源生產(chǎn)四種產(chǎn)品，生產(chǎn)過(guò)程要經(jīng)過(guò)五個(gè)車(chē)間，每個(gè)車(chē)間能提供的月工時(shí)數(shù)量和每種產(chǎn)品所需工時(shí)定額、各種產(chǎn)品的銷(xiāo)售價(jià)格和單位成本、銷(xiāo)售趨勢(shì)等資料如下表所示。 已知下月制造產(chǎn)品B和D用的金屬板供應(yīng)緊張，最大供應(yīng)量為2000平方米，每件B產(chǎn)品需該金屬板2平方米、每件D產(chǎn)品需1