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

管理系統(tǒng)決策定量分析模型：線性規(guī)劃第一節(jié)線性規(guī)劃模型、實(shí)例及求解第二節(jié)線性規(guī)劃模型求解的一般方法：?jiǎn)渭冃畏ǖ谌?jié)線性規(guī)劃問題的對(duì)偶問題，對(duì)偶單純形法第四節(jié)線性規(guī)劃問題的靈敏性分析第五節(jié)多目標(biāo)規(guī)劃法中的目的規(guī)劃法簡(jiǎn)介2/3/20231【第六章：線性規(guī)劃*48*】有動(dòng)畫第一節(jié)線性規(guī)劃模型、實(shí)例及求解一、線性規(guī)劃予以解決的實(shí)際問題

1、資源給定，如何對(duì)給定資源予以充分地、合理地運(yùn)用，使之完成的任務(wù)盡可能地多。

2、任務(wù)給定，如何以盡可能少的資源消耗來完成給定的任務(wù)。

可見，上述兩類問題都是尋求利潤(rùn)最大。第一類，是以最大收益扣除定量成本；第二類，是以定量收益扣除最小成本。2/3/20232【第六章：線性規(guī)劃*48*】有動(dòng)畫二、線性規(guī)劃的定義：

當(dāng)收益和消耗均與計(jì)劃指標(biāo)成正比時(shí)，一個(gè)規(guī)劃問題所列出的數(shù)學(xué)表達(dá)式都是關(guān)于計(jì)劃指標(biāo)的線性關(guān)系式，稱此類型規(guī)劃問題為線性規(guī)劃問題。

線性規(guī)劃問題是：在一組線性約束條件下，求一組非負(fù)變量得值，使一個(gè)線性目標(biāo)函數(shù)達(dá)到最大或者是最小。

2/3/20233【第六章：線性規(guī)劃*48*】有動(dòng)畫三、線性規(guī)劃的數(shù)學(xué)模型

例1：

某廠擬定利用三種資源：鑄件、鍛件、加工人時(shí)生產(chǎn)A、B兩種型號(hào)的設(shè)備。已知資料如下表所示：

求總銷售額最大的生產(chǎn)計(jì)劃方案。4萬元/臺(tái)6萬元/臺(tái)設(shè)備售價(jià)120（百人時(shí)）24加工人時(shí)100（噸）32鍛件270（噸）93鑄件資源量BA2/3/20234【第六章：線性規(guī)劃*48*】有動(dòng)畫

例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ì)劃2/3/20235【第六章：線性規(guī)劃*48*】有動(dòng)畫

（LP）模型的形式：

1、矩陣形式

記：C=（c1、c2、c3、……cn）

X=（x1、x2、x3、……xn）TA=（aij）m×n

b=（b1、b2、b3、……bm）T

則（LP）模型的矩陣形式為：價(jià)值系數(shù)行向量決策變量列向量技術(shù)系數(shù)矩陣資源限定列向量2/3/20236【第六章：線性規(guī)劃*48*】有動(dòng)畫2、極大化典型形式（實(shí)際問題一）3、極小化典型形式（實(shí)際問題二）2/3/20237【第六章：線性規(guī)劃*48*】有動(dòng)畫

4、標(biāo)準(zhǔn)型形式（模型求解的基礎(chǔ)）2/3/20238【第六章：線性規(guī)劃*48*】有動(dòng)畫（LP）問題的基本術(shù)語

1、變量決策變量：對(duì)需要優(yōu)化的經(jīng)濟(jì)量所設(shè)置的變量稱之。附加變量：為求解（LP）模型所引入的變量稱之。

（1）松弛變量：為處理約束條件所引入，又分為不足變量和剩余變量（2）人工變量：為人為地制造一個(gè)基而引入的變量2/3/20239【第六章：線性規(guī)劃*48*】有動(dòng)畫2、目標(biāo)函數(shù)；約束條件

3、（LP）模型的解的概念

可行解：稱滿足約束條件的解為可行解。最優(yōu)解：能使目標(biāo)函數(shù)得以滿足的可行解稱之為最優(yōu)解。2/3/202310【第六章：線性規(guī)劃*48*】有動(dòng)畫（LP）模型圖解法x*1=20（臺(tái)）、x*2=20（臺(tái)）Z*=200（萬元）2/3/202311【第六章：線性規(guī)劃*48*】有動(dòng)畫圖形放大2/3/202312【第六章：線性規(guī)劃*48*】有動(dòng)畫（LP）模型圖解法之步驟2/3/202313【第六章：線性規(guī)劃*48*】有動(dòng)畫

圖解法之結(jié)論：（1）（LP）模型的可行解域?yàn)橐粋€(gè)凸多邊形或凸多面體，它們的極點(diǎn)為有限多個(gè)。（2）（LP）模型的最優(yōu)解如果存在，一定可以在凸集合的極點(diǎn)上得到。（3）若（LP）模型的最優(yōu)解在一個(gè)極點(diǎn)上得到，則該模型最優(yōu)解唯一；若在兩個(gè)極點(diǎn)上同時(shí)取得，則該模型有多重最優(yōu)解。（4）若作圖以后；滿足各約束條件的共同部分不存在，則該模型無可行解。（5）若找不到離目標(biāo)函數(shù)線距離最遠(yuǎn)的可行解點(diǎn)，則該模型無有限最優(yōu)解。（開區(qū)域時(shí)發(fā)生）2/3/202314【第六章：線性規(guī)劃*48*】有動(dòng)畫1、線性規(guī)劃模型的一般形式2/3/202315【第六章：線性規(guī)劃*48*】有動(dòng)畫（LP）模型間相互轉(zhuǎn)換的規(guī)則1、2、3、4、5、2/3/202316【第六章：線性規(guī)劃*48*】有動(dòng)畫第二節(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)解2/3/202317【第六章：線性規(guī)劃*48*】有動(dòng)畫三、（LP）模型解的概念的擴(kuò)充

基矩陣、非基矩陣、基向量、非基向量（口述）基變量、非基變量基向量對(duì)應(yīng)的變量稱之為基變量，非基向量對(duì)應(yīng)的變量稱之為非基變量?！罨窘猱?dāng)取定一個(gè)基以后，令全部的非基變量等于零，從方程組中解出基變量得值，由它們構(gòu)成的解：

X=（x1、x2、……xj、……xn)T稱之為一個(gè)基本解。顯然，基本解的個(gè)數(shù)為有限多個(gè)，最多為個(gè)。☆基本可行解滿足非負(fù)要求的基本解稱之為基本可行解。2/3/202318【第六章：線性規(guī)劃*48*】有動(dòng)畫四、單純形法求解步驟及單純形表結(jié)構(gòu)特征求解步驟：

1、將模型變?yōu)闃?biāo)準(zhǔn)型，列初表

2、判斷解是否最優(yōu)（判斷準(zhǔn)則：全部的σj≤0則達(dá)優(yōu)），若不是最優(yōu)則進(jìn)行下一步

3、進(jìn)行解的轉(zhuǎn)換（1）確定基準(zhǔn)列第k列（確定進(jìn)基變量）

σk=max{σj}（σj＞0）（2）確定基準(zhǔn)行第l行（確定退基變量）

θl=min{θi}θi=bi/aik

（aik＞0）（3）確定主元素：基準(zhǔn)行與基準(zhǔn)列交叉處的元素（4）進(jìn)行矩陣的初等行變換，變換的目標(biāo)是：

“基準(zhǔn)列的主元素變?yōu)?；其余的元素變?yōu)?”4、重復(fù)判斷步驟，直至尋求到最優(yōu)解2/3/202319【第六章：線性規(guī)劃*48*】有動(dòng)畫一、利用鑄件、鍛件、加工人時(shí)生產(chǎn)AB設(shè)備之例求解單純形表2/3/202320【第六章：線性規(guī)劃*48*】有動(dòng)畫例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)最大銷售收入為：Z*=200（萬元）

2/3/202321【第六章：線性規(guī)劃*48*】有動(dòng)畫單純形表的結(jié)構(gòu)特征

1、所有單純形表共有特征

（1）基變量的列系數(shù)均為單位向量（2）基變量的檢驗(yàn)數(shù)均為零（3）最右邊的常量均大于等于零

2、最終單純形表的特征（要會(huì)識(shí)別最終表）

（1）基變量的列系數(shù)均為單位向量（2）基變量的檢驗(yàn)數(shù)均為零（3）最右邊的常量均大于等于零

（4）檢驗(yàn)數(shù)行全部小于等于零2/3/202322【第六章：線性規(guī)劃*48*】有動(dòng)畫學(xué)生練習(xí)題1

用單純形法求解2/3/202323【第六章：線性規(guī)劃*48*】有動(dòng)畫2/3/202324【第六章：線性規(guī)劃*48*】有動(dòng)畫學(xué)生練習(xí)題2用單純形法求解2/3/202325【第六章：線性規(guī)劃*48*】有動(dòng)畫2/3/202326【第六章：線性規(guī)劃*48*】有動(dòng)畫五、用矩陣形式表出的單純形表

公式（1）某非基變量檢驗(yàn)數(shù)計(jì)算公式：

σj=Cj-CBB-1Pj

（2）某非基變量列系數(shù)計(jì)算公式：

Pj*=B-1Pj2/3/202327【第六章：線性規(guī)劃*48*】有動(dòng)畫一、利用鑄件、鍛件、加工人時(shí)生產(chǎn)AB設(shè)備之例求解單純形表2/3/202328【第六章：線性規(guī)劃*48*】有動(dòng)畫六、利用ExcelSolver對(duì)線性規(guī)劃模型求解步驟：

1、在電子表格中確定目標(biāo)單元格、活動(dòng)單元格，輸入所有參數(shù)（aij、bi、cj）

2、利用數(shù)據(jù)組相乘公式（常用函數(shù)里SUMPRODUCT）確定好約束條件的左邊對(duì)應(yīng)的單元格

3、打開工具（T）欄里的規(guī)劃求解（1）給定目標(biāo)單元格、活動(dòng)單元格，求最大（2）添加約束條件（3）選項(xiàng)欄里：線性、非負(fù)，確定（4）求解得下表鏈接2/3/202329【第六章：線性規(guī)劃*48*】有動(dòng)畫利用ExcelSolver對(duì)（LP）模型例1求解鏈接2/3/202330【第六章：線性規(guī)劃*48*】有動(dòng)畫物質(zhì)配送問題之例例3：兩個(gè)工廠生產(chǎn)同一種新產(chǎn)品，配送公司將該產(chǎn)品送到兩個(gè)倉庫。運(yùn)送情況如下：

1、工廠1的產(chǎn)品通過鐵路只能送到倉庫1，產(chǎn)品的數(shù)量不限，單位運(yùn)輸成本為700元/單位。

2、工廠2的產(chǎn)品通過鐵路只能送到倉庫2，產(chǎn)品的數(shù)量不限，單位運(yùn)輸成本為900元/單位。

3、卡車可將多達(dá)50個(gè)單位的產(chǎn)品由工廠送到配送中心，再從配送中心以最多50個(gè)單位的載運(yùn)量運(yùn)到各倉庫，其單位運(yùn)費(fèi)如圖所示。

4、各廠的生產(chǎn)量、各倉庫的所需量如圖所示。求最低運(yùn)輸成本對(duì)應(yīng)的運(yùn)輸方案。2/3/202331【第六章：線性規(guī)劃*48*】有動(dòng)畫例3的配送網(wǎng)絡(luò)示意圖配送中心倉庫2工廠2倉庫1工廠1生產(chǎn)70單位需要90單位生產(chǎn)80單位需要60單位700/單位900/單位圖三：配送公司配送網(wǎng)絡(luò)300/單位200/單位400/單位400/單位[最多50單位][最多50單位][最多50單位][最多50單位]2/3/202332【第六章：線性規(guī)劃*48*】有動(dòng)畫例3的變量設(shè)置設(shè)：

x1——工廠1至倉庫1的運(yùn)輸量

x2——工廠2至倉庫2的運(yùn)輸量

x3——工廠1至配送中心的運(yùn)輸量

x4——工廠2至配送中心的運(yùn)輸量

x5——配送中心至倉庫1的運(yùn)輸量

x6——配送中心至倉庫2的運(yùn)輸量根據(jù)條件分析建立模型如下：2/3/202333【第六章：線性規(guī)劃*48*】有動(dòng)畫例3的配送網(wǎng)絡(luò)示意圖配送中心倉庫2工廠2倉庫1工廠1生產(chǎn)70單位需要90單位生產(chǎn)80單位需要60單位700/單位900/單位圖三：配送公司配送網(wǎng)絡(luò)300/單位200/單位400/單位400/單位[最多50單位][最多50單位][最多50單位][最多50單位]x1x3x4x2x5x62/3/202334【第六章：線性規(guī)劃*48*】有動(dòng)畫例3的（LP）模型2/3/202335【第六章：線性規(guī)劃*48*】有動(dòng)畫例3ExcelSolver求解2/3/202336【第六章：線性規(guī)劃*48*】有動(dòng)畫例3求解結(jié)果：運(yùn)輸方案

x1

工廠1——倉庫1：x*1=30x2

工廠2——倉庫2：x*2=40x3

工廠1——配送中心：x*3=50x4

工廠2——配送中心：x*4=30x5

配送中心——倉庫1：x*5=30x6

配送中心——倉庫2：x*6=50Z總運(yùn)費(fèi)最小總運(yùn)費(fèi)為：Zmin=110000（費(fèi)用單位）2/3/202337【第六章：線性規(guī)劃*48*】有動(dòng)畫第三節(jié)線性規(guī)劃問題的對(duì)偶問題，對(duì)偶單純形法

一、線性規(guī)劃問題的對(duì)偶問題的提出

1、原問題（LP）例1中的鑄件、鍛件、加工人時(shí)用于生產(chǎn)A、B兩種設(shè)備，出讓設(shè)備以后獲得銷售收入，將這樣考慮的問題稱之為原問題。

2、對(duì)偶問題（LD）將例1中的鑄件、鍛件、加工人時(shí)制定相應(yīng)的價(jià)格y1、y2、y3，直接出讓資源獲得收入，將這樣考慮的問題稱之為原問題的對(duì)偶問題。2/3/202338【第六章：線性規(guī)劃*48*】有動(dòng)畫二、對(duì)偶模型及對(duì)偶模型的建立

該模型稱之為原模型（LP）的對(duì)偶模型，記為：（LD）（y1

、y2

、y3的設(shè)置及含義解釋一下）2/3/202339【第六章：線性規(guī)劃*48*】有動(dòng)畫三、原模型（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è)模型的變量為自由變量，則另一模型的約束條件為等式2/3/202340【第六章：線性規(guī)劃*48*】有動(dòng)畫兩個(gè)模型對(duì)比原模型對(duì)偶模型2/3/202341【第六章：線性規(guī)劃*48*】有動(dòng)畫四、對(duì)偶問題的性質(zhì)

1、對(duì)稱性：（LP）與（LD）互為對(duì)偶

2、弱對(duì)偶定理：若X(0)，Y(0)分別是原問題和其對(duì)偶問題的任一可行解，則有：CX(0)≤Y(0)b

該性質(zhì)說明：兩個(gè)模型的目標(biāo)函數(shù)值互為界。2/3/202342【第六章：線性規(guī)劃*48*】有動(dòng)畫

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)解。2/3/202343【第六章：線性規(guī)劃*48*】有動(dòng)畫具體的對(duì)應(yīng)規(guī)則：（以最終表為例，其余表規(guī)則相同）（a）原模型松弛變量檢驗(yàn)數(shù)的相反數(shù)對(duì)應(yīng)著其對(duì)偶模型的決策變量的值；（b）原模型決策變量檢驗(yàn)數(shù)的相反數(shù)對(duì)應(yīng)著其對(duì)偶模型的松弛變量的值。由例1的最終表可得：

Y*=（01/25/400）

W*=270×0+100×1/2+120×5/4=200（萬元）最終單純型表64000x1x2x3x4x5bi0x1001-15/49/8304x20101/2-1/4206x3100-1/43/820zj6401/25/4σj000-1/2-5/42/3/202344【第六章：線性規(guī)劃*48*】有動(dòng)畫2/3/202345【第六章：線性規(guī)劃*48*】有動(dòng)畫五、對(duì)偶決策變量y*i

的經(jīng)濟(jì)含義

1、在給定資源最優(yōu)配置時(shí)，y*i為單位第i種資源的增加給目標(biāo)函數(shù)所帶來的貢獻(xiàn)。（邊際貢獻(xiàn)）

2、y*i稱之為在給定資源最優(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的資源稱之為富裕資源；y*i≠0的資源稱之為緊缺資源。

5、需注意的問題（口述）2/3/202346【第六章：線性規(guī)劃*48*】有動(dòng)畫五、對(duì)偶單純形法單純形法：保持原問題的解（B-1b）為可行解，讓其對(duì)偶問題的解（CBB-1A-C）由非可行解逐步變化到可行解

對(duì)偶單純形法：保持對(duì)偶問題的解為可行解（CBB-1A-C≥0），讓原問題的解（B-1b）由非可行解逐步變化到可行解

CBB-1A-C=（0，CBB-1N-CN，CBB-1）為全部的檢驗(yàn)數(shù)，即對(duì)偶問題的解XBXNXLB-1bIB-1NB-1檢驗(yàn)數(shù)0CBB-1N-CNCBB-12/3/202347【第六章：線性規(guī)劃*48*】有動(dòng)畫對(duì)偶單純形法的步驟（參看例14）

第一步：列初始單純形表

第二步：確定基準(zhǔn)行（找出(B-1b)r=min{(B-1b)i|(B-1b)i＜0}，即bi列中負(fù)值中的最小者，則第r行為基準(zhǔn)行，xr為退基變量。若bi列中沒有負(fù)值，則已得最優(yōu)解）

第三步：確定基準(zhǔn)列，先計(jì)算：則第s列為基準(zhǔn)列，xs為進(jìn)基變量

〈若基準(zhǔn)行沒有負(fù)值，則該問題無可行解〉

第四步：以基準(zhǔn)行、基準(zhǔn)列交叉處的元素為主元素，進(jìn)行初等行變換，得新的單純形表后返回第二步。2/3/202348【第六章：線性規(guī)劃*48*】有動(dòng)畫例14用對(duì)偶單純形法求解下述線性規(guī)劃模型解：將模型化為標(biāo)準(zhǔn)型Y*=（0，3/2，1/8，0）Z*=8×3/2+16×1/8=14Z*=－Z‘用對(duì)偶單純形法求解的最優(yōu)解：2/3/202349【第六章：線性規(guī)劃*48*】有動(dòng)畫例14對(duì)偶單純行法求解表2/3/202350【第六章：線性規(guī)劃*48*】有動(dòng)畫第四節(jié)線性規(guī)劃問題靈敏性分析

一、線性規(guī)劃問題靈敏性分析的內(nèi)容

1、參數(shù)bi、cj發(fā)生改變問題的分析

2、新增加一個(gè)約束條件問題的分析

3、新增加一個(gè)決策變量問題的分析二、參數(shù)bi發(fā)生改變問題的分析

1、bi參數(shù)發(fā)生改變的實(shí)際原因

2、求△bi的允許范圍的前提條件（保持原各資源的影子價(jià)格不變）

3、△bi的確定過程（參看例子）

4、對(duì)第i種資源考慮予以增減的步驟（口述）2/3/202351【第六章：線性規(guī)劃*48*】有動(dòng)畫

參數(shù)bi發(fā)生改變問題的分析

△bi的確定過程之例：求△b2最初單純型表64000x1x2x3x4x5bi0x3931002700x4320101000x524001120zj00000σj64000最終單純型表64000x1x2x3x4x5bi0x3001-15/49/8304x20101/2-1/4206x1100-1/43/820zj6401/25/4σj000-1/2-5/42/3/202352【第六章：線性規(guī)劃*48*】有動(dòng)畫處理如下：最初單純型表64000x1x2x3x4x5bi0x393100270+0△b20x432010100+1△b20x524001120+0△b2zj00000σj64000最終單純型表64000x1x2x3x4x5bi0x3001-15/49/830-15/4△b24x20101/2-1/420+1/2△b26x1100-1/43/820-1/4△b2zj6401/25/4σj000-1/2-5/42/3/202353【第六章：線性規(guī)劃*48*】有動(dòng)畫△bi的確定過程之例：求△b2（其他資源量不變）

1、設(shè)法確定出最終表上常量與△b2的關(guān)系：

2、要不改變影子價(jià)格，則要仍然為最終表，故要求：

3、聯(lián)立上述不等式解之得：

2/3/202354【第六章：線性規(guī)劃*48*】有動(dòng)畫

△b2=20時(shí)

0x3001-33/411/8-454x2010

1/2-1/4

306x1100-1/4

3/8

15

zi640

1/211/4

σj000-1/2-11/4

0x400-4/151-3/10

124x201

2/150-1/10

246x110-1/150

3/10

18

zi64

2/15012/5

σj00-2/150-12/5

當(dāng)△b2=20時(shí)，超范圍，右邊出現(xiàn)負(fù)數(shù)，用對(duì)偶單純型法處理一次得：新的最優(yōu)解：x1=18，x2=24，Z*=6×18+4×24=204（8×1/2）

x4=12表明：增加的20單位的鍛件多出12個(gè)單位，只能配置8個(gè)單位。2/3/202355【第六章：線性規(guī)劃*48*】有動(dòng)畫三、參數(shù)cj發(fā)生改變問題的分析

1、cj參數(shù)發(fā)生改變的實(shí)際原因

2、求△cj的允許范圍的前提條件（保持原最優(yōu)解不變）

3、△cj的確定過程（參看例子）最終單純型表64000x1x2x3x4x5bi0x3001-15/49/8304x20101/2-1/4206x1100-1/43/820zj6401/25/4σj000-1/2-5/42/3/202356【第六章：線性規(guī)劃*48*】有動(dòng)畫最終單純型表6+△c14000x1x2x3x4x5bi0x3001-15/49/8304x20101/2-1/4206+△c1x1100-1/43/820zj6+△c1401/2-1/4△c15/4+3/8△c1σj000-1/2+1/4△c1-5/4-3/8△c12/3/202357【第六章：線性規(guī)劃*48*】有動(dòng)畫△cj的確定過程之例：求△c1（余下的cj不變）

1、確定出原終表上-1/2、-5/4與△c1的關(guān)系：

2、要保持原最優(yōu)解不變，則要仍然為最終表，故要求檢驗(yàn)數(shù)行全部小于等于零，即：

3、聯(lián)立上述不等式組解之得：

2/3/202358【第六章：線性規(guī)劃*48*】有動(dòng)畫關(guān)于△bi

、△cj的確定可用靈敏性分析報(bào)告2/3/202359【第六章：線性規(guī)劃*48*】有動(dòng)畫四、新增加一個(gè)約束條件問題的分析

1、新增加一個(gè)約束條件后原最優(yōu)解受到影響否的判斷

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

若為151萬千瓦小時(shí)……

當(dāng)電力總量為180萬千瓦小時(shí)時(shí)，兩種方法判定結(jié)論：原方案不變；當(dāng)電力總量為151萬千瓦小時(shí)時(shí)，兩種方法判定結(jié)論：原方案要變；由方法二判定后，在判定的基礎(chǔ)上，用對(duì)偶單純型法處理可得新的最優(yōu)解為：

x1=17，x2=22，Z*=1902/3/202361【第六章：線性規(guī)劃*48*】有動(dòng)畫

640000

x1x2x3x4x5x6

0x3001-33/411/80304x2010

1/2-1/40206x1100-1/4

3/80200x6530001151

zi640

1/211/4

σj000-1/2-11/4

0x3001-33/411/80304x2010

1/2-1/40206x1100-1/4

3/80200x6000-1/4-11/81-91、變5為0

03011/4-17/8151

zi640

1/211/40

σj000-1/2-11/40

0x3001-401214x2010

5/90-2/9226x1100-1/30

1/3170x5000

2/91-8/98

zi640

2/9011/9

σj000-2/90-11/9

2/3/202362【第六章：線性規(guī)劃*48*】有動(dòng)畫五、新增加一個(gè)決策變量問題的分析

1、新增加一個(gè)決策變量以后原最優(yōu)解改變否的判斷

通過計(jì)算新決策變量（此時(shí)為非基變量）的檢驗(yàn)數(shù)來判定

2、若原最優(yōu)解改變，新的最優(yōu)解的確定用單純型法來確定2/3/202363【第六章：線性規(guī)劃*48*】有動(dòng)畫

P6488

15

6400011

x1x2x3x4x5x6

0x3001-33/411/8

30

4x2010

1/2-1/4

20

6x1100-1/4

3/8B-1P620

zi640

1/211/4

σj000-1/2-11/4σ6=？

-3c6=11的σ6

P6（488）

1c6=15的σ6

當(dāng)c6=11時(shí)，新產(chǎn)品不投產(chǎn)，因?yàn)棣?=-3

；