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

管理系統(tǒng)決策定量分析模型：線性規(guī)劃第一節(jié)線性規(guī)劃模型、實例及求解第二節(jié)線性規(guī)劃模型求解的一般方法：單純形法第三節(jié)線性規(guī)劃問題的對偶問題，對偶單純形法第四節(jié)線性規(guī)劃問題的靈敏性分析第五節(jié)多目標規(guī)劃法中的目的規(guī)劃法簡介2/3/20231【第六章：線性規(guī)劃*48*】有動畫第一節(jié)線性規(guī)劃模型、實例及求解一、線性規(guī)劃予以解決的實際問題

1、資源給定，如何對給定資源予以充分地、合理地運用，使之完成的任務盡可能地多。

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

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

當收益和消耗均與計劃指標成正比時，一個規(guī)劃問題所列出的數(shù)學表達式都是關于計劃指標的線性關系式，稱此類型規(guī)劃問題為線性規(guī)劃問題。

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

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

例1：

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

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

例1的模型（LP）

根據(jù)以上資料，建立（LP）模型如下：

（設A設備生產(chǎn)x1臺；B設備生產(chǎn)x2臺）〈1〉目標函數(shù)〈2〉約束條件該模型的解為生產(chǎn)計劃2/3/20235【第六章：線性規(guī)劃*48*】有動畫

（LP）模型的形式：

1、矩陣形式

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

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

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

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

4、標準型形式（模型求解的基礎）2/3/20238【第六章：線性規(guī)劃*48*】有動畫（LP）問題的基本術語

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

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

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

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

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

（LP）模型求解的單純形法一、單純形法的基本思想：

單純形法的基本思想是從有限個基本可行解中選擇幾個予以比較，從而得到最優(yōu)解。二、單純形法的求解步驟：

1、以最簡單的方法確定第一個基本可行解

2、判斷該解是否最優(yōu)，若是最優(yōu)則最優(yōu)解得到，若不是最優(yōu)解則進行下一步

3、在保證目標函數(shù)至少不減（目標函數(shù)求最大值模型）的前提下，轉(zhuǎn)換到另一個基本可行解上

4、重復判斷步驟，直至尋找到最優(yōu)解2/3/202317【第六章：線性規(guī)劃*48*】有動畫三、（LP）模型解的概念的擴充

基矩陣、非基矩陣、基向量、非基向量（口述）基變量、非基變量基向量對應的變量稱之為基變量，非基向量對應的變量稱之為非基變量。☆基本解當取定一個基以后，令全部的非基變量等于零，從方程組中解出基變量得值，由它們構成的解：

X=（x1、x2、……xj、……xn)T稱之為一個基本解。顯然，基本解的個數(shù)為有限多個，最多為個?！罨究尚薪鉂M足非負要求的基本解稱之為基本可行解。2/3/202318【第六章：線性規(guī)劃*48*】有動畫四、單純形法求解步驟及單純形表結構特征求解步驟：

1、將模型變?yōu)闃藴市?，列初?/p>

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

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

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

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

（aik＞0）（3）確定主元素：基準行與基準列交叉處的元素（4）進行矩陣的初等行變換，變換的目標是：

“基準列的主元素變?yōu)?；其余的元素變?yōu)?”4、重復判斷步驟，直至尋求到最優(yōu)解2/3/202319【第六章：線性規(guī)劃*48*】有動畫一、利用鑄件、鍛件、加工人時生產(chǎn)AB設備之例求解單純形表2/3/202320【第六章：線性規(guī)劃*48*】有動畫例1求解的結論共搜索了三個基本可行解

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設備各自生產(chǎn)20臺最大銷售收入為：Z*=200（萬元）

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

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

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

2、最終單純形表的特征（要會識別最終表）

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

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

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

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

σj=Cj-CBB-1Pj

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

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

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

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

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

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

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

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

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

x1——工廠1至倉庫1的運輸量

x2——工廠2至倉庫2的運輸量

x3——工廠1至配送中心的運輸量

x4——工廠2至配送中心的運輸量

x5——配送中心至倉庫1的運輸量

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

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總運費最小總運費為：Zmin=110000（費用單位）2/3/202337【第六章：線性規(guī)劃*48*】有動畫第三節(jié)線性規(guī)劃問題的對偶問題，對偶單純形法

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

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

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

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

、y2

、y3的設置及含義解釋一下）2/3/202339【第六章：線性規(guī)劃*48*】有動畫三、原模型（LP）與其對偶模型（LD）模型間的關系

1、原模型為極大化典型形式，則其對偶模型為極小化典型形式：

2、（LP）與（LD）的系數(shù)矩陣互為轉(zhuǎn)置

3、（LP）為m個約束條件，（LD）有m個決策變量

4、（LP）為n個決策變量,（LD）有n個約束條件

5、一個模型的變量非負，則另一模型的約束條件為不等式

6、一個模型的變量為自由變量，則另一模型的約束條件為等式2/3/202340【第六章：線性規(guī)劃*48*】有動畫兩個模型對比原模型對偶模型2/3/202341【第六章：線性規(guī)劃*48*】有動畫四、對偶問題的性質(zhì)

1、對稱性：（LP）與（LD）互為對偶

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

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

3、設X*、Y*分別為（LP）與（LD）的某一可行解，當CX*=Y*b時，則X*、Y*分別為（LP）與（LD）的最優(yōu)解。

4、檢驗數(shù)與解之間的對應關系：（1）原模型單純形表上檢驗數(shù)的相反數(shù)對應著其對偶模型的一個基本解。（2）原模型最終單純形表上檢驗數(shù)的相反數(shù)對應著其對偶模型的最優(yōu)解。2/3/202343【第六章：線性規(guī)劃*48*】有動畫具體的對應規(guī)則：（以最終表為例，其余表規(guī)則相同）（a）原模型松弛變量檢驗數(shù)的相反數(shù)對應著其對偶模型的決策變量的值；（b）原模型決策變量檢驗數(shù)的相反數(shù)對應著其對偶模型的松弛變量的值。由例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*】有動畫2/3/202345【第六章：線性規(guī)劃*48*】有動畫五、對偶決策變量y*i

的經(jīng)濟含義

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

2、y*i稱之為在給定資源最優(yōu)配置時第i種資源的影子價格，影子價格是在給定資源最優(yōu)配置時對第i種資源的一種估價。

3、y*i可理解為是可以利用的現(xiàn)行市場價格（邊際成本）的最高限度。例如：y*2=1/2，則現(xiàn)行市場價格小于1/2時，對鍛件可以適當予以增加；若現(xiàn)行市場價格大于1/2時，對鍛件不能予以增加。

4、y*i=0的資源稱之為富裕資源；y*i≠0的資源稱之為緊缺資源。

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

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

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

第一步：列初始單純形表

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

第三步：確定基準列，先計算：則第s列為基準列，xs為進基變量

〈若基準行沒有負值，則該問題無可行解〉

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

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

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

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

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

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

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

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

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

參數(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*】有動畫處理如下：最初單純型表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*】有動畫△bi的確定過程之例：求△b2（其他資源量不變）

1、設法確定出最終表上常量與△b2的關系：

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

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

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

△b2=20時

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

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

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

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

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*】有動畫最終單純型表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*】有動畫△cj的確定過程之例：求△c1（余下的cj不變）

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

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

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

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

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

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

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

若為151萬千瓦小時……

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

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

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*】有動畫五、新增加一個決策變量問題的分析

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

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

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

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

當c6=11時，新產(chǎn)品不投產(chǎn)，因為σ6=-3

；