管理運(yùn)籌學(xué) 課件 田世海 第1-3章 緒論、線性規(guī)劃及單純形法、線性規(guī)劃的對(duì)偶理論

運(yùn)籌學(xué)——緒論夫運(yùn)籌策帷幄之中，決勝于千里之外——《史記·高祖本紀(jì)》

緒論一、運(yùn)籌思想及運(yùn)籌學(xué)的出現(xiàn)和發(fā)展樸素的運(yùn)籌思想

緒論一、運(yùn)籌思想及運(yùn)籌學(xué)的產(chǎn)生和發(fā)展樸素的運(yùn)籌思想5

緒論一、運(yùn)籌思想及運(yùn)籌學(xué)的出現(xiàn)和發(fā)展二戰(zhàn)期間：“運(yùn)作研究(OperationalResearch)小組”

解決復(fù)雜的戰(zhàn)略和戰(zhàn)術(shù)問(wèn)題——如何合理運(yùn)用雷達(dá)有效地對(duì)付德軍空襲對(duì)商船如何進(jìn)行編隊(duì)護(hù)航，使船隊(duì)遭受德國(guó)潛艇攻擊時(shí)損失最少；在各種情況下如何調(diào)整反潛深水炸彈的爆炸深度，才能增加對(duì)德國(guó)潛艇的殺傷力等。運(yùn)籌學(xué)的產(chǎn)生

緒論一、運(yùn)籌思想及運(yùn)籌學(xué)的出現(xiàn)和發(fā)展二戰(zhàn)后運(yùn)籌學(xué)的發(fā)展階段7

緒論二、運(yùn)籌學(xué)是什么——定義

應(yīng)用分析、試驗(yàn)、量化的方法，對(duì)經(jīng)濟(jì)管理系統(tǒng)中人、財(cái)、物等資源進(jìn)行統(tǒng)籌安排，通過(guò)建立模型求解，為決策者提供有依據(jù)的最優(yōu)方案，以實(shí)現(xiàn)最有效的管理。

緒論二、運(yùn)籌學(xué)是什么——定義

應(yīng)用分析、試驗(yàn)、量化的方法，對(duì)經(jīng)濟(jì)管理系統(tǒng)中人、財(cái)、物等資源進(jìn)行統(tǒng)籌安排，通過(guò)建立模型求解，為決策者提供有依據(jù)的最優(yōu)方案，以實(shí)現(xiàn)最有效的管理。系統(tǒng)的整體觀念三、運(yùn)籌學(xué)的基本特征

緒論靠近某河流有兩個(gè)化工廠，流經(jīng)第一化工廠的河流流量為每天500萬(wàn)m3，兩工廠之間有一條流量為每天200萬(wàn)m3的支流（見(jiàn)圖）。

第一化工廠每天排放污水2萬(wàn)m3，第二化工廠每天排放污水1.4萬(wàn)m3。污水從工廠1流到工廠2前會(huì)有20%自然凈化。根據(jù)環(huán)保要求，河水中污水的含量應(yīng)不大于0.2%。而工廠1和工廠2處理污水的成本分別為1000元/萬(wàn)m3和800元/萬(wàn)m3。問(wèn)兩工廠各應(yīng)處理多少污水才能使處理污水的總費(fèi)用最低？例10

緒論二、運(yùn)籌學(xué)是什么——定義

應(yīng)用分析、試驗(yàn)、量化的方法，對(duì)經(jīng)濟(jì)管理系統(tǒng)中人、財(cái)、物等資源進(jìn)行統(tǒng)籌安排，通過(guò)建立模型求解，為決策者提供有依據(jù)的最優(yōu)方案，以實(shí)現(xiàn)最有效的管理。系統(tǒng)的整體觀念多學(xué)科的綜合模型方法的應(yīng)用三、運(yùn)籌學(xué)的基本特征11

緒論四、運(yùn)籌學(xué)研究?jī)?nèi)容12博弈論（對(duì)策論）之囚徒困境——招供不招招供不招

緒論四、運(yùn)籌學(xué)研究?jī)?nèi)容軟件應(yīng)用基本教學(xué)內(nèi)容1線性規(guī)劃及單純形法2線性規(guī)劃的對(duì)偶理論3運(yùn)輸問(wèn)題4整數(shù)規(guī)劃與分配問(wèn)題5圖與網(wǎng)絡(luò)分析6動(dòng)態(tài)規(guī)劃

緒論五、運(yùn)籌學(xué)的研究步驟ax提出問(wèn)題建立模型求解解的檢驗(yàn)及控制決策實(shí)施例15

緒論六、學(xué)科地位及應(yīng)用領(lǐng)域

緒論六、學(xué)科地位及應(yīng)用領(lǐng)域運(yùn)籌學(xué)在管理中的應(yīng)用生產(chǎn)運(yùn)作庫(kù)存管理運(yùn)輸問(wèn)題人力資源財(cái)務(wù)管理…………運(yùn)籌學(xué)

緒論六、學(xué)科地位及應(yīng)用領(lǐng)域運(yùn)籌學(xué)在信管專業(yè)中的應(yīng)用管理：面向企業(yè)的戰(zhàn)術(shù)執(zhí)行層。如生產(chǎn)調(diào)度、供應(yīng)與銷售、財(cái)務(wù)管理、人力資源管理等。信息：以信息為運(yùn)作對(duì)象。包括信息的收集、存儲(chǔ)、加工、傳輸和使用。系統(tǒng)：是企業(yè)功能系統(tǒng)的一個(gè)映射。是由計(jì)算機(jī)硬件、軟件、數(shù)據(jù)庫(kù)及其管理系統(tǒng)、工作規(guī)程和操作人員組成的一個(gè)系統(tǒng)。

緒論教材《管理運(yùn)籌學(xué)》田世海、蘭小春、黃永濤主編

機(jī)械工業(yè)出版社參考書《運(yùn)籌學(xué)》編寫組清華大學(xué)出版社《管理運(yùn)籌學(xué)》韓伯棠主編高等教育出版社《運(yùn)籌學(xué)及其工程應(yīng)用》韓中庚清華大學(xué)出版社《運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用》胡運(yùn)權(quán)主編哈工大出版社要求聯(lián)系實(shí)際問(wèn)題理解原理及定義盡可能理解原理，對(duì)數(shù)理推導(dǎo)不強(qiáng)求，但方法要會(huì)用七、學(xué)習(xí)方法及要求第1章線性規(guī)劃及單純形法1.1一般線性規(guī)劃問(wèn)題的數(shù)學(xué)模型

第一化工廠每天排放污水2萬(wàn)m3，第二化工廠每天排放污水1.4萬(wàn)m3。污水從工廠1流到工廠2前會(huì)有20%自然凈化。根據(jù)環(huán)保要求，河水中污水的含量應(yīng)不大于0.2%。而工廠1和工廠2處理污水的成本分別為1000元/萬(wàn)m3和800元/萬(wàn)m3。問(wèn)兩工廠各應(yīng)處理多少污水才能使處理污水的總費(fèi)用最低？例1

靠近某河流有兩個(gè)化工廠，流經(jīng)一廠的河流流量為每天500萬(wàn)m3，工廠之間有一條流量為每天200萬(wàn)m3的支流。1.1.1問(wèn)題提出

設(shè)工廠1和工廠2每天分別處理污水x1和x2萬(wàn)m3，則有：Minz=1000x1+800x2(2-x1)/500≤0.002[0.8(2-x1)+1.4-x2]/700≤0.002x1≤2,x2≤1.4x1,x2≥0

設(shè)備產(chǎn)品ABCD利潤(rùn)(元)

Ⅰ21402

Ⅱ22043

有效臺(tái)時(shí)1281612

例2已知資料如表所示，問(wèn)如何安排生產(chǎn)才能使利潤(rùn)最大？maxZ=2x1+3x2

x1≥0,x2≥0s.t.2x1+2x2≤12x1+2x2≤84x1≤164x2≤12設(shè)：X1——產(chǎn)品Ⅰ產(chǎn)量X2——產(chǎn)品Ⅱ產(chǎn)量建模1.1.1問(wèn)題提出1.用未知自變量(決策變量)表示可變因素，變量的一組數(shù)據(jù)代

表一種解決方案，通常情況下決策變量取非負(fù)值。2．都有一個(gè)要達(dá)到的目標(biāo)，它也是自變量的線性函數(shù)，稱為

目標(biāo)函數(shù)。根據(jù)需要，要求目標(biāo)函數(shù)極大化或極小化。3．存在限制條件，它們可用自變量的線性方程(等式)或線性不

等式來(lái)表示。這些條件稱為約束條件。

以上例子的共同特征：1.1.1問(wèn)題提出maxZ=2x1+3x2

x1≥0,x2≥0s.t.2x1+2x2≤12x1+2x2≤84x1≤164x2≤12設(shè)：X1——產(chǎn)品Ⅰ產(chǎn)量，X2——產(chǎn)品Ⅱ產(chǎn)量線性規(guī)劃數(shù)學(xué)模型三要素1.1.1問(wèn)題提出24其他典型問(wèn)題：合理下料問(wèn)題運(yùn)輸問(wèn)題投資組合問(wèn)題1.1.1問(wèn)題提出1.1.2線性規(guī)劃問(wèn)題的數(shù)學(xué)模型的表示一般表示方式:

目標(biāo)函數(shù)：約束條件：1.1一般線性規(guī)劃問(wèn)題的數(shù)學(xué)模型簡(jiǎn)寫形式1.1一般線性規(guī)劃問(wèn)題的數(shù)學(xué)模型1.1.2線性規(guī)劃問(wèn)題的數(shù)學(xué)模型的表示向量形式1.1一般線性規(guī)劃問(wèn)題的數(shù)學(xué)模型1.1.2線性規(guī)劃問(wèn)題的數(shù)學(xué)模型的表示矩陣形式1.1一般線性規(guī)劃問(wèn)題的數(shù)學(xué)模型1.1.2線性規(guī)劃問(wèn)題的數(shù)學(xué)模型的表示練習(xí)1：某工廠用三種原料生產(chǎn)三種產(chǎn)品，已知的條件如表所示，試制訂總利潤(rùn)最大的生產(chǎn)計(jì)劃。1.1一般線性規(guī)劃問(wèn)題的數(shù)學(xué)模型1.1.3線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式maxz=c1x1+c2x2++cnxna11x1+a12x2++a1nxn=b1a21x1+a22x2++a2nxn=b2

am1x1+am2x2++amnxn=bmx1,x2,,xn≥0其中，bi≥0(i=1,2,,m)（一）定義及形式一般形式1.1一般線性規(guī)劃問(wèn)題的數(shù)學(xué)模型簡(jiǎn)寫形式矩陣形式（一）定義及形式1.1.3線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式1.1一般線性規(guī)劃問(wèn)題的數(shù)學(xué)模型（二）如何將一般問(wèn)題化為標(biāo)準(zhǔn)型1、目標(biāo)函數(shù)為minz=c1x1+c2x2++cnxn令z=-z,變?yōu)閙axz

=-c1x1-c2x2--cnxn2、約束條件為a11x1+a12x2++a1nxn≤b1加入非負(fù)變量xn+1，稱為松弛變量，有

a11x1+a12x2++a1nxn+xn+1=b11.1一般線性規(guī)劃問(wèn)題的數(shù)學(xué)模型1.1.3線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式（二）如何將一般問(wèn)題化為標(biāo)準(zhǔn)型令xj=xj-xj

，對(duì)模型中的進(jìn)行變量代換。3、約束條件為a11x1+a12x2++a1nxn≥b1減去非負(fù)變量xn+1，稱為剩余變量，有

a11x1+a12x2++a1nxn-xn+1=b14、變量xj無(wú)約束。1.1一般線性規(guī)劃問(wèn)題的數(shù)學(xué)模型1.1.3線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式（二）如何將一般問(wèn)題化為標(biāo)準(zhǔn)型令xj=xj-xj

，對(duì)模型中的進(jìn)行變量代換。3、約束條件為a11x1+a12x2++a1nxn≥b1減去非負(fù)變量xn+1，稱為剩余變量，有

a11x1+a12x2++a1nxn-xn+1=b14、變量xj無(wú)約束。令xj

=-xj5、變量xj≤01.1一般線性規(guī)劃問(wèn)題的數(shù)學(xué)模型1.1.3線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式minz=x1+2x2

+3x3

s.t.-2x1+x2+x3≤9-3x1+x2+2x3≥43x1-2x2-3x3=-6x1≤0,x2≥0,x3取值無(wú)約束例3（二）如何將一般問(wèn)題化為標(biāo)準(zhǔn)型1.1一般線性規(guī)劃問(wèn)題的數(shù)學(xué)模型1.1.3線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式解：令得標(biāo)準(zhǔn)形式為：1.1.3線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式1.1.4線性規(guī)劃問(wèn)題的解37一、線性規(guī)劃問(wèn)題的解求解線性規(guī)劃問(wèn)題：就是從滿足約束方程組和約束不等式的決策變量取值中，找出使得目標(biāo)函數(shù)達(dá)到最大的值。Maxz=CX（1）

s.t.AX=b（2）

X

0（3）（一）解、可行解、最優(yōu)解1.滿足約束條件（2）

的X，稱為線性規(guī)劃

問(wèn)題的解。2.滿足約束條件（2）與（3）的X，稱為線性規(guī)劃的問(wèn)題可行解。3.滿足目標(biāo)函數(shù)（1）的可行解X，稱為線性規(guī)劃的問(wèn)題最優(yōu)解。1.1.4線性規(guī)劃問(wèn)題的解（二）基、基向量、基變量1.設(shè)r(A)=m,并且B是A的m

階非奇異的子矩陣（det(B)

0),則稱矩陣B為線性規(guī)劃問(wèn)題的一個(gè)基。1.1.4線性規(guī)劃問(wèn)題的解（二）基、基向量、基變量1.設(shè)r(A)=m,并且B是A的m

階非奇異的子矩陣（det(B)

0),則稱矩陣B為線性規(guī)劃問(wèn)題的一個(gè)基。1.1.4線性規(guī)劃問(wèn)題的解

maxZ=2x1+3x22x1

+2x2+x3

=12x1

+2x2+x4

=84x1

+

+x5

=164x2

+x6

=12x1

，x2，x3

，x4，x5，x6

02.矩陣B=（P1，P2….Pm)，其列向量Pj稱為對(duì)應(yīng)基B的基向量。3.與基向量Pj相對(duì)應(yīng)的變量xj就稱為基變量，其余的就稱為非基變量。1.1.4線性規(guī)劃問(wèn)題的解

maxZ=2x1+3x2

2x1

+2x2+x3

=12

x1

+2x2+x4

=8

4x1

+

+x5

=16

4x2

+x6

=12x1

，x2，x3

，x4，x5，x6

0(1)可行解：滿足約束條件的解稱為可行解，可行解的集合稱為可行域。(2)最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最大值的可行解。(3)基：約束方程組的一個(gè)滿秩子矩陣稱為規(guī)劃問(wèn)題的一個(gè)基，基中的每一個(gè)列向量稱為基向量，與基向量對(duì)應(yīng)的變量稱為基變量，其他變量稱為非基變量?；靖拍钚〗Y(jié)：1.1.4線性規(guī)劃問(wèn)題的解(4)基解：在約束方程組中，令所有非基變量為0，可以解出基變量的唯一解，這組解與非基變量的0共同構(gòu)成基解。(5)基可行解：滿足變量非負(fù)的基解稱為基可行解(6)可行基：對(duì)應(yīng)于基可行解的基稱為可行基1.1.4線性規(guī)劃問(wèn)題的解1.1.5有關(guān)線性和線性規(guī)劃模型的假設(shè)1比例性目標(biāo)函數(shù)的值同決策變量的取值成嚴(yán)格的比例。2可疊加性決策變量間相互獨(dú)立，決策變量的各自取值對(duì)目標(biāo)函數(shù)

總的取值互不影響。3可分性決策變量允許取小數(shù)、分?jǐn)?shù)或任一實(shí)數(shù)。4確定性線性規(guī)劃模型中的參數(shù)必須是確定的常數(shù)1.2圖解法1、建立直角坐標(biāo)系，將約束條件

表示在圖中。2、確定滿足約束條件的解的范圍。3、繪制目標(biāo)函數(shù)的圖形。4、確定最優(yōu)解。一、圖解法步驟1.2圖解法二、舉例⑴⑵⑶⑷一、圖解法步驟012345678123456⑴⑵⑶⑷作圖∴最優(yōu)解：x1=4，x2=2有唯一最優(yōu)解，Z=14x2

x1(42)⑴⑵⑶⑷

例二、

例三、⑴⑵⑶無(wú)窮多最優(yōu)解⑴⑵無(wú)界解x1x1x2

x2

⑴⑵x1x2

無(wú)可行解例四、1.2圖解法三、LP問(wèn)題可行域和解的情況1、可行域封閉唯一最優(yōu)解2、可行域封閉多個(gè)最優(yōu)解3、可行域開放唯一最優(yōu)解4、可行域開放多個(gè)最優(yōu)解5、可行域開放目標(biāo)函數(shù)無(wú)界6、無(wú)可行解1.2圖解法四、啟示：

圖解法的解題思路和幾何上的直觀結(jié)論對(duì)求解一般的線性規(guī)劃有什么啟示?1、求解LP問(wèn)題時(shí)，解的四種情況2、若LP問(wèn)題的可行域存在，則可行域是凸集。3、若存在最優(yōu)解，則最優(yōu)解一定在可行域的頂點(diǎn)

（邊界）找到4、解題思路：逐個(gè)比較凸集頂點(diǎn)的目標(biāo)函數(shù)值。1.3單純形法原理52凸集：如果集合C中任意兩個(gè)點(diǎn)，其連線上的所有點(diǎn)也都是集合C中的點(diǎn)。集合C為凸集。頂點(diǎn)：如果對(duì)于凸集C中的點(diǎn)X，不存在C中的任意其它兩個(gè)不同的點(diǎn)，使得X在它們的連線上，這時(shí)稱X為凸集的頂點(diǎn)。1.3.1預(yù)備知識(shí)1.3單純形法原理53定理2:

線性規(guī)劃問(wèn)題的基可行解X對(duì)應(yīng)線性規(guī)劃問(wèn)題可行域（凸集）的頂點(diǎn)。定理3:

若線性規(guī)劃問(wèn)題有最優(yōu)解，一定存在一個(gè)基可行解是最優(yōu)解。定理1:若線性規(guī)劃問(wèn)題存在可行解，則問(wèn)題的可行域是凸集。1.3.2基本定理maxz=2x1+3x2

（1）s.t.-2x1+3x2

6（2-1）

3x1-2x2

6（2-2）

x1+x2

4（2-3）

x1,x2

0

（3）（1）用圖解法求解（2）化為標(biāo)準(zhǔn)形式。（3）找出問(wèn)題的所有基解，

指出哪些是基可行解。已知下列線性規(guī)劃問(wèn)題：練習(xí)（1）：x243211234x1O-1-1-2-2-3-3-2x1+3x2

63x1-2

x2

6x1+x2

4AQ1Q2Q3Q4B可行域本問(wèn)題解的情況：基解：點(diǎn)（O，A，B，Q1，Q2，Q3，Q4）可行解：由點(diǎn)（O，Q1，Q2，Q3，Q4）圍成的區(qū)域?；尚薪猓狐c(diǎn)（O，Q1，Q2，Q3，Q4）最優(yōu)解：Q3練習(xí)（2）：minz=2x1+3x2s.t.2x1+2x2≤84x1≥12x2≥-16x1≤0,x2

取值無(wú)約束。

將下列線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形式：1.3單純形法原理1.3.3單純形法求解思路尋求最優(yōu)解的思路：

設(shè)給定線性規(guī)劃問(wèn)題：（一）確定初始基可行解1.3單純形法原理添加松弛變量得其標(biāo)準(zhǔn)形為：因此約束方程組的系數(shù)矩陣為：（一）確定初始基可行解1.3.3單純形法求解思路1.3單純形法原理由于該矩陣含有一個(gè)單位子矩陣，因此，這個(gè)單位陣就是一組基，就可以求出一個(gè)基可行解：稱其為初始基可行解。（一）確定初始基可行解1.3.3單純形法求解思路1.3單純形法原理⑴⑵⑶⑷例：（一）確定初始基可行解1.3.3單純形法求解思路1.3單純形法原理（二）從初始基可行解轉(zhuǎn)換到另一個(gè)基可行解

思路：對(duì)初始基可行解的系數(shù)矩陣進(jìn)行初等行變換，構(gòu)造出一個(gè)新的單位矩陣，其各列所對(duì)應(yīng)的變量即為一組新的基變量，求出其數(shù)值，就是一個(gè)新的基可行解。1.3.3單純形法求解思路1.3單純形法原理（三）最優(yōu)性檢驗(yàn)和解的判別設(shè)有基可行解比較兩者對(duì)應(yīng)的目標(biāo)函數(shù)值，哪一個(gè)更優(yōu)？1.3.3單純形法求解思路1.3單純形法原理（三）最優(yōu)性檢驗(yàn)和解的判別1.3.3單純形法求解思路1.3單純形法原理64小結(jié)：1、確定初始基可行解2、最優(yōu)性檢驗(yàn)和解的判別3、從初始基可行解轉(zhuǎn)換為另一個(gè)基可行解4、重復(fù)步驟2-3直至得到最優(yōu)解設(shè)給定線性規(guī)劃問(wèn)題：解:標(biāo)準(zhǔn)化：

maxZ=2x1+3x2+0x3+0x4+0x5+0x6

2x1

+2x2+x3

=12

x1

+2x2+x4

=8

4x1

+

+x5

=16

4x2

+x6

=12x1

，x2，x3

，x4，x5，x6

01.4單純形法計(jì)算步驟例

maxZ=2x1+3x22x1+2x2

12

x1+2x2

8

4x1

164x2

12x1

，x2

066(1)找到初始可行基，建立初始單純形表.(2)進(jìn)行最優(yōu)性檢驗(yàn)2024/6/1367入基變量由最大增加原則確定入基變量：(3)從一個(gè)基可行解轉(zhuǎn)換到另一個(gè)目標(biāo)函數(shù)值更大的基可行解

當(dāng)某些非基變量的檢驗(yàn)數(shù)時(shí)，為使目標(biāo)函數(shù)值增加地更快，一般選擇正檢驗(yàn)數(shù)中最大者對(duì)應(yīng)的非基變量入基

，成為新的基變量。

68由最小比值原則選擇出基變量；為確保新的基可行解的非零分量非負(fù)，按下述規(guī)則求得最小比值，其所對(duì)應(yīng)的原基變量中的出基。(3)從一個(gè)基可行解轉(zhuǎn)換到另一個(gè)目標(biāo)函數(shù)值更大的基可行解由最大增加原則確定入基變量：(3)從一個(gè)基可行解轉(zhuǎn)換到另一個(gè)目標(biāo)函數(shù)值更大的基可行解由最小比值原則選擇出基變量；入基變量由最大增加原則確定入基變量：出基變量70(3)從一個(gè)基可行解轉(zhuǎn)換到另一個(gè)目標(biāo)函數(shù)值更大的基可行解由最小比值原則選擇出基變量；入基變量由最大增加原則確定入基變量：于是，新的一組基是：出基變量以為主元素進(jìn)行換基迭代：即利用初等行變換將入基變量

所在的系數(shù)列變?yōu)閱挝涣邢蛄?，而變?yōu)?。這樣原來(lái)基矩陣中的就不再是單位向量，取而代之的是，這樣就找到了一組新的基。71(3)從一個(gè)基可行解轉(zhuǎn)換到另一個(gè)目標(biāo)函數(shù)值更大的基可行解由最小比值原則選擇出基變量；入基變量由最大增加原則確定入基變量：于是，新的一組基是：出基變量以為主元素進(jìn)行換基迭代：(4)重復(fù)二、三兩步，直至找到最優(yōu)解。72(1)找到初始可行基，建立初始單純形表.741.4單純形法計(jì)算步驟特殊情況：（1）出現(xiàn)兩個(gè)或兩個(gè)以上相同的最大，此時(shí)可任選一個(gè)所對(duì)應(yīng)的變量作為進(jìn)基變量。

（2）利用規(guī)則決定出基變量時(shí)，出現(xiàn)兩個(gè)或兩個(gè)以上的最小比值，則迭代后，會(huì)出現(xiàn)一個(gè)或幾個(gè)基變量等于零的情況，稱此為退化現(xiàn)象。1.4單純形法計(jì)算步驟找出一個(gè)初始可行解是否最優(yōu)轉(zhuǎn)移到另一個(gè)基本可行解最優(yōu)解是否循環(huán)核心是：變量迭代結(jié)束求解步驟1.4單純形法計(jì)算步驟小結(jié)——單純形法的要點(diǎn)（1）化線性規(guī)劃模型為標(biāo)準(zhǔn)型，建立初始單純形表。（2）根據(jù)單純形表按照最大增加原則選擇換入變量；（3）按照最小比值原則選擇換出變量；（4）實(shí)施矩陣的初等變換進(jìn)行換基迭代；（5）建立新的單純形表；（6）重復(fù)上述過(guò)程直到求得最優(yōu)表格為止。2024/6/1377當(dāng)所有時(shí)，現(xiàn)有頂點(diǎn)對(duì)應(yīng)的基可行解即為最優(yōu)解。小結(jié)——解的情況2024/6/13781.當(dāng)所有時(shí)，現(xiàn)有頂點(diǎn)對(duì)應(yīng)的基可行解即為最優(yōu)解。小結(jié)——解的情況2.當(dāng)所有時(shí)，又對(duì)某個(gè)非基變量有則該線性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解。791.當(dāng)所有時(shí)，現(xiàn)有頂點(diǎn)對(duì)應(yīng)的基可行解即為最優(yōu)解。小結(jié)——解的情況2.當(dāng)所有時(shí)，又對(duì)某個(gè)非基變量有則該線性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解。3.如果存在某個(gè)，又向量的所有分量，對(duì)任

意，恒有，則存在無(wú)界解。單純形法與圖解法比較例

maxZ=50x1+30x2

4x1+3x2+x3=120(1)2x1+x2+x4=20(2)x1

，x2

040502530(0，0)(15，20)(1)(2)81用單純形法解題時(shí)，需要有一個(gè)單位陣作為初始基。當(dāng)約束條件都是“≤”時(shí)，加入松弛變量就形成了初始基?！?.5單純形法的進(jìn)一步討論82

maxZ=2x1+3x2+0x3+0x4+0x5+0x6

2x1

+2x2+x3

=12

x1

+2x2+x4

=8

4x1

+

+x5

=16

4x2

+x6

=12x1

，x2，x3

，x4，x5，x6

0解:將模型標(biāo)準(zhǔn)化例3

maxZ=2x1+3x2

2x1+2x2

12x1+2x2

8

4x1

16

4x2

12x1

，x2

083但實(shí)際存在“≥”或“＝”型的約束，沒(méi)有現(xiàn)成的單位矩陣。例maxZ=-3x1+x3

x1+x2+x3

4-2x1+x2

-x3

≥

13x2+x3

=9x1

，x2，x3

0采用人造基的辦法：添加人工變量，構(gòu)造單位矩陣§1.5單純形法的進(jìn)一步討論84

人工單位矩陣的構(gòu)造方法在“

”的不等式約束中減去一個(gè)剩余變量后可變?yōu)榈仁郊s束，但此剩余變量的系數(shù)是（-1），所以再加入一個(gè)人工變量，其系數(shù)是（+1），因而在系數(shù)矩陣中可得到一個(gè)相應(yīng)的單位向量，以便構(gòu)成初始單位陣，即初始基矩陣。在原本就是“

=”的約束中可直接添加一個(gè)人工變量，以便得到初始基矩陣。注意：人工變量是在等式中人為加入的，只有它等于0時(shí)，約束條件才是它本來(lái)的意義。求解帶人工變量的線性規(guī)劃有兩種方法：☆大M法☆兩階段法例解線性規(guī)劃1.5.1

大M法

86添加人工變量，構(gòu)造初始基：87-30100-M-Mx1x2x3x4x5x6x71111000-21-10-1100310001初始單純形表：CCBXBb0x44-Mx61-Mx79-3-2M4M10-M0041330211-10-21-10-11060403-311-10x430x21-Mx76-3+6M01+4M03M-4M088-30100-M-M初始單純形表：C30211-10-21-10-11060403-311-10x430x21-Mx76-3+6M01+4M03M-4M0-30100-M-Mx1x2x3x4x5x6x7CCBXBb00303/2-M-3/2-M+1/2-33/20001-1/21/2-1/2011/30001/3102/301/2-1/21/60x400x23-3x1189-30100-M-Mx1x2x3x4x5x6x7CCBXBb00303/2-M-3/2-M+1/2-33/20001-1/21/2-1/2011/30001/3102/301/2-1/21/60x400x23-3x11-9/2000-3/4-M+3/4-M-1/40x400x25/21x33/20001-1/21/2-1/2-1/2100-1/41/41/43/20103/4-3/41/490此時(shí)人工變量全部出基，并已達(dá)最優(yōu)條件。最優(yōu)解為最優(yōu)值為-9/2000-3/4-M+3/4-M-1/40x400x25/21x33/20001-1/21/2-1/2-1/2100-1/41/41/43/20103/4-3/41/4911.5.2兩階段法

第一階段：構(gòu)造目標(biāo)函數(shù)只含人工變量的線性規(guī)劃問(wèn)題，求解后判斷原線性規(guī)劃問(wèn)題是否有基本可行解，若有，則進(jìn)行第二階段；第二階段：將第一階段的最終單純形表所對(duì)應(yīng)的解，去掉人工變量，作為第二階段的初始單純形表的初始基可行解，進(jìn)行單純形法的迭代。1.5.2兩階段法

(2)第二階段先在第一階段的最終單純形表去掉人工變量，再還原原目標(biāo)函數(shù)，即maxz′=-2x1-3x2+0x3，繼續(xù)迭代：

961.5.3關(guān)于解的判別

一、唯一最優(yōu)解當(dāng)所有時(shí)，該基可行解即為最優(yōu)解。971.5.3關(guān)于解的判別

二、無(wú)窮多最優(yōu)解98二、無(wú)窮多最優(yōu)解1.5.3關(guān)于解的判別

99三、無(wú)界解1.5.3關(guān)于解的判別

100四、無(wú)可行解1.5.3關(guān)于解的判別

1.5.4單純形法小結(jié)：三要素決策變量約束條件目標(biāo)函數(shù)兩個(gè)三個(gè)以上xj≥0xj無(wú)約束xj≤0

bi

≥0bi<0≤=≥maxZminZxs

xa標(biāo)準(zhǔn)化圖解法、單純形法單純形法不處理令xj=

xj′

-xj″

xj′

≥0xj″

≥0令

xj′=-xj不處理約束條件兩端同乘以-1加松弛變量xs加人工變量xa減去xs加入xa不處理令z′=-Z

0-M個(gè)數(shù)取值限制右端常數(shù)約束方向要求系數(shù)A,b,C停止1,3/2§1.6

改進(jìn)單純形法——矩陣描述一、矩陣形式的單純形法若記：線性規(guī)劃模型為：

maxz=CXAX=bX≥0基變量：XB非基變量：XN

基矩陣：B

非基矩陣：N基變量的價(jià)值系數(shù)：CB非基變量的價(jià)值系數(shù)：CN則有：maxz=CBXB+CNXNBXB+NXN=b①XB,XN

≥0為求XB，用B-1左乘①式兩端，有：B-1BXB+B-1NXN=B-1b從而有：XB=B-1b?

B-1NXN令非基變量XN=0，則有：1）基變量：XB=B-1b3）目標(biāo)函數(shù)值：z=CBXB=CBB-1b2）檢驗(yàn)數(shù)：σN=CN?CBB-1N=CB(B-1b?B-1NXN)+CNXN

z=CBXB+CNXN=CBB-1b+(CN?CBB-1N)XN4）非基矩陣:B-1N將XB=B-1b?

B-1NXN代入目標(biāo)函數(shù)：

運(yùn)籌學(xué)的研究步驟ax提出問(wèn)題建模求解解的檢驗(yàn)及控制決策實(shí)施例1.7應(yīng)用舉例

設(shè)備產(chǎn)品ABCD利潤(rùn)(元)

Ⅰ21402

Ⅱ22043

有效臺(tái)時(shí)1281612已知資料如表所示，問(wèn)如何安排生產(chǎn)才能使利潤(rùn)最大？1.7應(yīng)用舉例問(wèn)題可以歸結(jié)為線性規(guī)劃模型的條件（1）問(wèn)題目標(biāo)能用效益指標(biāo)度量（2）為達(dá)到目標(biāo)有多種方案（3）目標(biāo)要在一定約束條件下實(shí)現(xiàn)，條件可用線性

等式或不等式描述

設(shè)備產(chǎn)品ABCD利潤(rùn)(元)

Ⅰ21402

Ⅱ22043

有效臺(tái)時(shí)1281612已知資料如表所示，問(wèn)如何安排生產(chǎn)才能使利潤(rùn)最大？maxZ=2x1+3x2

x1≥0,x2≥0s.t.2x1+2x2≤12x1+2x2≤84x1≤164x2≤12設(shè)：X1——產(chǎn)品Ⅰ產(chǎn)量X2——產(chǎn)品Ⅱ產(chǎn)量建模1.7應(yīng)用舉例1.7應(yīng)用舉例

例11工業(yè)原材料的合理利用解：先看有多少種裁料方案，再進(jìn)行組合和選擇。ⅠⅡⅢⅣⅤⅥ3m4m5m201120210002011300總長(zhǎng)/m1111101099料頭/m001122某大樓改造工程用11m長(zhǎng)角鋼切割成鋼窗用料。每扇窗含3m長(zhǎng)2根、4m長(zhǎng)3根，5m長(zhǎng)2根，若需鋼窗100扇，至少需要多少根角鋼原材料？1.7應(yīng)用舉例解：先看有多少種裁料方案，再進(jìn)行組合和選擇。ⅠⅡⅢⅣⅤⅥ3m4m5m201120210002011300總長(zhǎng)/m1111101099料頭/m001122設(shè)按方案Ⅰ到Ⅵ下料的原材料根數(shù)分別為xj(j=1,2,3,4,5,6,)，則：1.7應(yīng)用舉例設(shè)按方案Ⅰ到Ⅵ下料的原材料根數(shù)分別為xj(j=1,2,3,4,5,6,)，則：用單純形法求解得最終表為：

例2投資項(xiàng)目組合問(wèn)題：某公司有一筆30萬(wàn)的資金，今后三

年內(nèi)用于下列項(xiàng)目投資：（1）三年內(nèi)每年年初均可投資，當(dāng)年收回，獲利為每年投資額的20%；（2）只允許第一年初投入，于第二年末收回，本利合計(jì)為投資額的

150%，但此類投資的限額不超過(guò)15萬(wàn)；（3）允許于第二年初投入，于第三年末回收，本利合計(jì)為投資額的

160%，限額投資20萬(wàn)元。（4）允許第三年初投入，年末回收，可獲利40%，限額為10萬(wàn)元。為該公司制定一個(gè)到第三年末本利和為最大的投資組合方案。解：用xij表示第i年初投放到第j個(gè)項(xiàng)目的資金數(shù)1234一x11（1.2）x12（1.5）二x21（1.2）x23（1.6）三x31（1.2）x34（1.4）第i年初項(xiàng)目j解：用xij表示第i年初投放到第j個(gè)項(xiàng)目的資金數(shù)線性規(guī)劃模型：線性規(guī)劃模型：1234一166666.7133333.3二0200000三100000100000第三年末本利和=580000用單純形法求解得：例13某醫(yī)院晝夜24h各時(shí)段內(nèi)需要的護(hù)士數(shù)量如下：2:00-6:0010人，6:00-10:0015人，10:00-14:0025人，14:00-18:0020人，18:00-22:0018人，22:00-2:0012人。護(hù)

士分別于2:00,6:00,10:00,14:00,18:00,22:00分6批上

班，并連續(xù)工作8h。試確定：a、該醫(yī)院至少應(yīng)設(shè)多少名護(hù)士，才能滿足值班需要？b、若醫(yī)院可聘用合同工護(hù)士，上班時(shí)間同正式工護(hù)士。

若正式工護(hù)士報(bào)酬為10元/h，合同工護(hù)士報(bào)酬為15元/h，

問(wèn)醫(yī)院是否應(yīng)聘合同工護(hù)士及聘多少名？醫(yī)院晝夜24小時(shí)各時(shí)段內(nèi)需要的護(hù)士數(shù)量如下：護(hù)士分別于2、6、10、14、18、22點(diǎn)分6批上班，并連續(xù)工作8小時(shí)。時(shí)段2-66-1010-1414-1818-2222-2上班人數(shù)101525201812若醫(yī)院可聘用合同工護(hù)士，上班時(shí)間同正式工護(hù)士。若正式工護(hù)士報(bào)酬為10元/h，合同工護(hù)士報(bào)酬為15元/h，問(wèn)醫(yī)院是否應(yīng)聘合同工護(hù)士及聘多少名？例14.混合配料問(wèn)題某糖果廠用原料A、B、C加工成三種不同牌號(hào)的糖果甲、乙、丙。已知各種牌號(hào)糖果中A、B、C含量，原料成本，各種原料的每月限制用量，三種牌號(hào)糖果的單位加工費(fèi)及售價(jià)如下表，問(wèn)該廠每月生產(chǎn)這三種牌號(hào)糖果各多少千克，使該廠獲利最大，試建立該問(wèn)題的線性規(guī)劃數(shù)學(xué)模型。例4.混合配料問(wèn)題解：設(shè)xij

為生產(chǎn)第j

種糖果使用的第i

種原料的數(shù)量，則數(shù)學(xué)模型的目標(biāo)函數(shù)為：例4.混合配料問(wèn)題約束條件為：118運(yùn)籌學(xué)

OPERATIONSRESEARCH

第二章線性規(guī)劃的對(duì)偶理論119第二章線性規(guī)劃的對(duì)偶理論

(DualLinearProgramming,DLP)對(duì)偶問(wèn)題的提出原問(wèn)題與對(duì)偶問(wèn)題對(duì)偶問(wèn)題的基本性質(zhì)影子價(jià)格對(duì)偶單純形法靈敏度分析參數(shù)線性規(guī)劃120例甲方生產(chǎn)計(jì)劃問(wèn)題：

ⅠⅡ能力設(shè)備A2212設(shè)備B4016設(shè)備C0515利潤(rùn)23Ⅰ，Ⅱ各生產(chǎn)多少,可獲最大利潤(rùn)?§2.1對(duì)偶問(wèn)題的提出設(shè)有原問(wèn)題乙方租借設(shè)備：甲方以何種價(jià)格將設(shè)備A、B、C租借給乙方比較合理？請(qǐng)為其定價(jià)。假設(shè)A、B、C的單位租金分別為。思路：就甲方而言，租金收入應(yīng)不低于將設(shè)備用于自己生產(chǎn)時(shí)的利潤(rùn)。121所以：生產(chǎn)產(chǎn)品Ⅰ的資源用于出租時(shí)，租金收入應(yīng)滿足：類似的，生產(chǎn)產(chǎn)品Ⅱ的資源用于出租時(shí)，租金收入應(yīng)滿足：總的租金收入：122原問(wèn)題對(duì)偶問(wèn)題用矩陣將上述原問(wèn)題對(duì)偶問(wèn)題寫出123原問(wèn)題對(duì)偶問(wèn)題矩陣形式的原問(wèn)題與對(duì)偶問(wèn)題124原問(wèn)題對(duì)偶問(wèn)題目標(biāo)函數(shù)：MAX約束條件：m個(gè)約束變量：n個(gè)變量目標(biāo)函數(shù)：MIN約束條件：n個(gè)約束變量：m個(gè)變量§2.2

原問(wèn)題與對(duì)偶問(wèn)題125例寫出下述規(guī)劃的對(duì)偶問(wèn)題互為對(duì)偶如何寫出非規(guī)范的原問(wèn)題相應(yīng)的對(duì)偶問(wèn)題：目標(biāo)函數(shù)MINMAX約束條件約束條件=?4.變量?

對(duì)偶問(wèn)題與原問(wèn)題的關(guān)系：原問(wèn)題對(duì)偶問(wèn)題目標(biāo)函數(shù)：MAX約束條件：m個(gè)約束變量：n個(gè)變量目標(biāo)函數(shù)：MIN約束條件：n個(gè)約束變量：m個(gè)變量約束條件右端項(xiàng)價(jià)值系數(shù)價(jià)值系數(shù)約束條件右端項(xiàng)例寫出下述規(guī)劃的對(duì)偶問(wèn)題目標(biāo)函數(shù)MAXMIN約束條件變量3.變量約束例寫出下述規(guī)劃的對(duì)偶問(wèn)題目標(biāo)函數(shù)MINMAX約束條件變量3.變量約束129原問(wèn)題對(duì)偶問(wèn)題§2.3

對(duì)偶問(wèn)題的基本性質(zhì)假定線性規(guī)劃的原問(wèn)題與對(duì)偶問(wèn)題分別為：130例甲方生產(chǎn)計(jì)劃問(wèn)題：

ⅠⅡ能力設(shè)備A2212設(shè)備B4016設(shè)備C0515利潤(rùn)23Ⅰ，Ⅱ各生產(chǎn)多少,可獲最大利潤(rùn)?乙方租借設(shè)備，租金如何確定？原問(wèn)題對(duì)偶問(wèn)題131§2.3

對(duì)偶問(wèn)題的基本性質(zhì)1、弱對(duì)偶性 如果分別是原問(wèn)題和對(duì)偶問(wèn)題的可行解，則恒有132§2.3

對(duì)偶問(wèn)題的基本性質(zhì)2、最優(yōu)性 如果分別是原問(wèn)題和對(duì)偶問(wèn)題的可行解，且有則分別是原問(wèn)題和對(duì)偶問(wèn)題的最優(yōu)解。1334、強(qiáng)對(duì)偶性 如果原問(wèn)題有最優(yōu)解，則其對(duì)偶問(wèn)題也必有最優(yōu)解，且兩者最優(yōu)目標(biāo)函數(shù)值相等，即。3、無(wú)界性:如果原問(wèn)題（對(duì)偶問(wèn)題）有無(wú)界解，則其對(duì)偶問(wèn)題（原問(wèn)題）無(wú)可行解。5、互補(bǔ)松弛性：在線性規(guī)劃的最優(yōu)解中，如果對(duì)應(yīng)某一約束條件的對(duì)偶變量值非零，則該約束條件取嚴(yán)格等式；反之，如果約束條件取嚴(yán)格不等式，則其對(duì)偶變量一定為零。即若若§2.4

對(duì)偶問(wèn)題的基本性質(zhì)例：1、寫出其對(duì)偶問(wèn)題。2、已知原問(wèn)題的最優(yōu)解為用對(duì)偶理論直接求對(duì)偶問(wèn)題的最優(yōu)解。練習(xí)：1、寫出其對(duì)偶問(wèn)題。2、已知原問(wèn)題的最優(yōu)解為用對(duì)偶理論直接求對(duì)偶問(wèn)題的最優(yōu)解。1366、單純形法的雙層含義（1）用單純形法求解LP問(wèn)題時(shí)，迭代的每一步在得到該問(wèn)題的一個(gè)基可行解的同時(shí)，其檢驗(yàn)數(shù)的相反數(shù)就構(gòu)成對(duì)偶問(wèn)題的一個(gè)基本解。1376、單純形法的雙層含義（2）在單純形表中，原問(wèn)題的松

馳變量對(duì)應(yīng)對(duì)偶問(wèn)題的變量，

對(duì)偶問(wèn)題的剩余變量對(duì)應(yīng)原問(wèn)

題的變量。1386、單純形法的雙層含義（3）這些互相對(duì)應(yīng)的變量，如果在一個(gè)問(wèn)題的解中是基變量，則在另一個(gè)問(wèn)題的解中是非基變量。6、單純形法的雙層含義（4）將這兩個(gè)解代入各自的

目標(biāo)函數(shù)，有Z=W1406、單純形法的雙層含義（4）將這兩個(gè)解代入各自的

目標(biāo)函數(shù)，有Z=W141對(duì)偶變量可理解為對(duì)一個(gè)單位第種資源的估價(jià)，稱為影子價(jià)格。§2.4

影子價(jià)格1、定義：假設(shè)有原問(wèn)題和對(duì)偶問(wèn)題如下142例甲方生產(chǎn)計(jì)劃問(wèn)題：

ⅠⅡ能力設(shè)備A2212設(shè)備B4016設(shè)備C0515利潤(rùn)23Ⅰ，Ⅱ各生產(chǎn)多少,可獲最大利潤(rùn)?乙方租借設(shè)備，租金如何確定？原問(wèn)題對(duì)偶問(wèn)題原問(wèn)題是利潤(rùn)最大化的生產(chǎn)計(jì)劃問(wèn)題產(chǎn)品的利潤(rùn)（元/件）產(chǎn)品產(chǎn)量（件）總利潤(rùn)（元）資源限量（噸）剩余的資源（噸）消耗的資源單位產(chǎn)品消耗的資源（噸/件）§2.4影子價(jià)格比較對(duì)偶問(wèn)題資源限量（噸）資源價(jià)格（元/噸）總租金（元）對(duì)偶問(wèn)題是資源定價(jià)問(wèn)題，對(duì)偶問(wèn)題的最優(yōu)解w1、w2、...、wm稱為m種資源的影子價(jià)格?！?.4影子價(jià)格（1）資源市場(chǎng)價(jià)格受供求變化影響，影子價(jià)格則依賴于資源

利用情況?！?.4影子價(jià)格2、對(duì)影子價(jià)格的理解§2.4影子價(jià)格2、對(duì)影子價(jià)格的理解（2）影子價(jià)格是一種邊際價(jià)格：表示資源增加一個(gè)單位時(shí)，

最優(yōu)解及目標(biāo)函數(shù)值的變化。Z=17/2Z=35/4Z=9§2.4影子價(jià)格2、對(duì)影子價(jià)格的理解（3）影子價(jià)格是一種機(jī)會(huì)成本。

當(dāng)某種資源的市場(chǎng)價(jià)低于影子價(jià)格時(shí)，應(yīng)買進(jìn)這種資源；否則，應(yīng)賣出這種資源。Z=17/2Z=35/4Z=9§2.4影子價(jià)格2、對(duì)影子價(jià)格的理解(4)由互補(bǔ)松馳性理解影子價(jià)格：如果最優(yōu)生產(chǎn)計(jì)劃下某種資源有剩余，這種資源的影子價(jià)格一定等于0。影子價(jià)格不為零時(shí)，表明資源已用完。§2.4影子價(jià)格2、對(duì)影子價(jià)格的理解(5)從影子價(jià)格的含義考察單純形法的計(jì)算生產(chǎn)該種產(chǎn)品所消耗各項(xiàng)資源的影子價(jià)格總和——隱含成本第j種產(chǎn)品的產(chǎn)值§2.4影子價(jià)格2、對(duì)影子價(jià)格的理解（6）求解線性規(guī)劃問(wèn)題及對(duì)偶問(wèn)題的目的151§2.5

對(duì)偶單純形法單純形法：找一個(gè)初始基可行解，保持b列為正，通過(guò)迭代找到下一個(gè)基可行解，使目標(biāo)函數(shù)值不斷增大，當(dāng)檢驗(yàn)數(shù)行全部小于等于零時(shí)，達(dá)到最優(yōu)解。152§2.5

對(duì)偶單純形法在單純形表中，列對(duì)應(yīng)原問(wèn)題的基可行解，行對(duì)應(yīng)對(duì)偶問(wèn)題的一個(gè)基解；當(dāng)時(shí)，在檢驗(yàn)數(shù)行就得到對(duì)偶問(wèn)題的基可行解，

此時(shí)兩個(gè)問(wèn)題的目標(biāo)函數(shù)值相等；由最優(yōu)性條件知，兩個(gè)問(wèn)題都達(dá)到了最優(yōu)解。153一、對(duì)偶單純形法思想§2.5

對(duì)偶單純形法換個(gè)角度考慮LP求解過(guò)程：保持對(duì)偶問(wèn)題可行的前提下，通過(guò)逐步迭代實(shí)現(xiàn)原問(wèn)題可行。1544、檢查是否達(dá)最優(yōu)：b列非負(fù)時(shí)達(dá)最優(yōu)，否則繼續(xù)2、3。1、建立初始單純形表，使表中的檢驗(yàn)數(shù)都小于等于0。2、確定出基變量：選擇b列中負(fù)值最小者對(duì)應(yīng)變量出基，即對(duì)應(yīng)的為出基變量。3、確定入基變量：最小比值規(guī)則，即以對(duì)應(yīng)的為進(jìn)基變量，為主元素進(jìn)行迭代。二、對(duì)偶單純形法計(jì)算步驟：§2.5

對(duì)偶單純形法155例：用對(duì)偶單純形法求解下述問(wèn)題§2.5

對(duì)偶單純形法對(duì)偶單純形法的使用條件：

①檢驗(yàn)數(shù)全部≤0；②b列至少一個(gè)元素<0；156§2.5

對(duì)偶單純形法157原問(wèn)題無(wú)可行解的判別準(zhǔn)則：當(dāng)對(duì)偶問(wèn)題存在可行解時(shí)，若有某個(gè)，而所有，則原問(wèn)題無(wú)可行解，對(duì)偶問(wèn)題目標(biāo)值無(wú)界?！?.5

對(duì)偶單純形法158§2.6

靈敏度分析、含義：對(duì)系統(tǒng)因周圍條件變化顯示出來(lái)的敏

感程度的分析?？赡茏兓臈l件：利潤(rùn)

設(shè)備產(chǎn)品ABCD利潤(rùn)(元)

Ⅰ21402

Ⅱ22043

有效臺(tái)時(shí)1281612已知資料如表所示，問(wèn)如何安排生產(chǎn)才能使利潤(rùn)最大？maxZ=2x1+3x2

x1≥0,x2≥0s.t.2x1+2x2≤12x1+2x2≤84x1≤164x2≤12設(shè)：X1——產(chǎn)品Ⅰ產(chǎn)量X2——產(chǎn)品Ⅱ產(chǎn)量建?！?.6

靈敏度分析160§2.6

靈敏度分析二、分析方法及步驟：能把參數(shù)變化直接反映在

最終單純形表，無(wú)需從頭計(jì)算。已知線性規(guī)劃問(wèn)題：將參數(shù)的改變計(jì)算反映到最終表162§2.6

靈敏度分析二、分析方法及步驟：能把參數(shù)變化直接反映在

最終單純形表，無(wú)需從頭計(jì)算。已知線性規(guī)劃問(wèn)題：將參數(shù)的改變計(jì)算反映到最終表163§2.6

靈敏度分析已知線性規(guī)劃問(wèn)題：將參數(shù)的改變計(jì)算反映到最終表2.檢查原問(wèn)題是否仍為可行解3.檢查對(duì)偶問(wèn)題是否仍為可行解4.得到最優(yōu)解或繼續(xù)計(jì)算二、分析方法及步驟：能把參數(shù)變化直接反映在

最終單純形表，無(wú)需從頭計(jì)算。164§2.6

靈敏度分析原問(wèn)題對(duì)偶問(wèn)題結(jié)論或計(jì)算步驟可行解可行解仍是最優(yōu)解可行解非可行解用單純形法繼續(xù)迭代得到新的最優(yōu)解非可行解可行解用對(duì)偶單純形法繼續(xù)迭代得到新的最優(yōu)解非可行解非可行解引入人工變量，重新編單純形表，重新計(jì)算三、判斷得出結(jié)論或決定繼續(xù)計(jì)算的依據(jù)：（一）Cj

的變化分析——只影響檢驗(yàn)數(shù)。四、各個(gè)參數(shù)變化后的討論167（一）Cj

的變化分析——只影響檢驗(yàn)數(shù)。四、各個(gè)參數(shù)變化后的討論例：設(shè)有如下的線性規(guī)劃模型168用單純形法求得最終單純形表如下所示：（a）當(dāng)目標(biāo)函數(shù)變?yōu)闀r(shí)，最優(yōu)解會(huì)出現(xiàn)什么變化;169解：將目標(biāo)函數(shù)的變化直接反映到最終單純形表中：170Cj

的變化對(duì)最優(yōu)解的影響：171（b）目標(biāo)函數(shù)變?yōu)闀r(shí)在什么范圍內(nèi)變化，最優(yōu)解不變？將目標(biāo)函數(shù)系數(shù)的變化直接反映到最終單純形表中：解：由已知求得最終單純形表：172（b）目標(biāo)函數(shù)變?yōu)闀r(shí)在什么范圍內(nèi)變化，最優(yōu)解不變？解：將目標(biāo)函數(shù)系數(shù)的變化直接反映到最終單純形表中：173（二）分析bi變化影響：反映在最終單純形表上只引起

基變量列數(shù)字變化例、設(shè)有如下的線性規(guī)劃模型174用單純形法求得最終單純形表如表所示：（a）第2個(gè)約束條件的右端項(xiàng)增大到32，分析最優(yōu)解變化。175變換后的結(jié)果及迭代如下：bi

的變化對(duì)最優(yōu)解的影響：177（b）第2個(gè)約束條件變?yōu)闀r(shí)在什么范圍內(nèi)變化，表中基為最優(yōu)基？已求得最終單純形表如下：解：將b的變化反映到基變量b這一列數(shù)字上，得表179（三）增加一個(gè)變量的分析：即增加一種新產(chǎn)品，A增加一列，C增加一個(gè)相應(yīng)的分量。180（三）增加一個(gè)變量的分析：

設(shè)備產(chǎn)品ABCD利潤(rùn)(元)

Ⅰ21402

Ⅱ22043

有效臺(tái)時(shí)1281612已知資料如表所示，問(wèn)如何安排生產(chǎn)才能使利潤(rùn)最大？maxZ=2x1+3x2

x1≥0,x2≥0s.t.2x1+2x2≤12x1+2x2≤84x1≤164x2≤12設(shè)：X1——產(chǎn)品Ⅰ產(chǎn)量X2——產(chǎn)品Ⅱ產(chǎn)量建模181（三）增加一個(gè)變量的分析：182例:設(shè)有如下的線性規(guī)劃模型以上模型中，若增加一個(gè)變量，有,分析最優(yōu)解變化。（三）增加一個(gè)變量的分析：183用單純形法求得最終單純形表如表所示：184將變化反映到最終單純形表中:185增加一個(gè)變量對(duì)最優(yōu)解的影響：186§2.6

靈敏度分析、含義二、方法及步驟

三、判斷或計(jì)算依據(jù)（一）Cj

的變化分析——只影響檢驗(yàn)數(shù)四、各個(gè)參數(shù)變化后的討論（二）分析bi變化影響——只引起基變量列數(shù)字變化（三）增加一個(gè)變量的分析人工變量法187（四）分析變化的影響1、變化的兩種情況189例：設(shè)有如下的線性規(guī)劃模型四、各個(gè)參數(shù)變化后的討論（四）分析變化的影響上述問(wèn)題中，的系數(shù)向量變?yōu)榉治鲎顑?yōu)解變化。已用單純形法求得最終單純形表：上述問(wèn)題中，的系數(shù)向量變?yōu)榉治鲎顑?yōu)解變化。191迭代，此時(shí)換出變量必為將變化反映到最終單純形表，得：引入人工變量，將原問(wèn)題轉(zhuǎn)化為可行解。變化對(duì)最優(yōu)解的影響：上述問(wèn)題中，的系數(shù)向量變?yōu)?94四、各個(gè)參數(shù)變化后的討論（四）分析變化的影響195例:設(shè)有如下的線性規(guī)劃模型,求得最終單純形表如下：上述問(wèn)題中，的系數(shù)向量變?yōu)榉治鲎顑?yōu)解變化。196（五）增加一個(gè)約束條件的分析四、各個(gè)參數(shù)變化后的討論1、含義：相當(dāng)于增加一道工序，可能使可行域變小2、方法：將原最優(yōu)解取值代入新增的約束條件，如滿足說(shuō)明新增約束未起限制作用，原最優(yōu)解不變，否則將新增約束直接反映到最終表再進(jìn)行分析。197（五）增加一個(gè)約束條件的分析四、各個(gè)參數(shù)變化后的討論例：設(shè)有如下的線性規(guī)劃模型上述問(wèn)題中，增加一個(gè)約束條件分析最優(yōu)解變化。198用單純形法求得最終單純形表如表2.8所示：增加一個(gè)約束條件199將約束條件寫成取為基變量，直接反映到最終表：200將約束條件寫成取為基變量，直接反映到