《運籌學》完整教案(本科)

料必備___至迎下或

《運籌學》教案

適用專業(yè)：

適用層次：本科

教學時間：20XX年上學期

授課題目：

緒論

第一章線性規(guī)劃及單純形法

第一節(jié)：線性規(guī)劃問題及數(shù)學模型。

教學目的與要求:

1.知識目標：掌握運籌學的概念和作用及其學習方法；掌握線性規(guī)劃的基

本概念和兩種基本建模方法。

2.能力目標：掌握線性規(guī)劃建模的標準形式及將普通模型化為標準模型的

方法。要求學生完成P43習題1.2兩個小題。

3.素質(zhì)目標：培養(yǎng)學生良好的職業(yè)道德、樹立愛崗精神

教學重點:

1、線性規(guī)劃的基本概念和兩種基本建模方法；

2、線性規(guī)劃建模的標準形式及將普通模型化為標準模型的方法。

教學難點：

1、線性規(guī)劃的兩種基本建模方法；

2、將線性規(guī)劃模型的普通形式化為標準形式。

教學過程：

1.舉例引入（5分鐘）

2.新課（60分鐘）

（1）舉例引入，緒論（20分鐘）

（2）運籌學與線性規(guī)劃的基本概念（20分鐘）

（3）結合例題講解線性規(guī)劃標準型的轉化方法

3.課堂練習（20分鐘）

4.課堂小結（5分鐘）

5.布置作業(yè)

學習必備一一一儂下或

《線性規(guī)劃及單純形法》（2課時）

【教學流程圖】

舉例引入，緒論

V「運籌學

運籌學與線性規(guī)劃的基本概M線性規(guī)劃

（結合例題講解）I線性規(guī)劃的標準型

目標函數(shù)

結合例題v講解線性規(guī)劃標準型的轉化方法《約束條件的右端常數(shù)

約束條件為不等式

8

課堂練習

8

課堂小結

8

布置作業(yè)

【教學方法】

本課主要采用任務驅動和程序式思維相結合的教學方法，過程當中輔以案例

講解、啟發(fā)提問、自主學習和協(xié)作學習等方式。任務驅動是實現(xiàn)本課教學目標和

完成教學內(nèi)容的主要方法，任務是師生活動內(nèi)容的核心，在教學過程中，任務驅

動被多次利用。自主學習能提高學生的自主探究能力，競賽和協(xié)作學習調(diào)動學生

的積極性，激發(fā)學生參與的熱情。學生之間互幫互助，共同分享勞動果實，從而

激發(fā)了學生的團隊意識，達到理想的教學效果。

【教學內(nèi)容】

一、教學過程：

（一）舉例引入：（5分鐘）

（1）齊王賽馬的故事

(2)兩個囚犯的故事

導入提問：什么叫運籌學？

(二)新課：

緒論

一、運籌學的基本概念

(用實例引入)

例1-1戰(zhàn)國初期，齊國的國王要求田忌和他賽馬，規(guī)定各人從自己的

上馬、中馬、下馬中各選一匹馬來比賽，并且說好每輸一匹馬就得支

付一千兩銀子給予獲勝者。當時齊王的馬比田忌的馬強，結果每年田

忌都要輸?shù)羧摄y子。但孫臏給田忌出主意，可使田忌反輸為贏。

試問：如果雙方都不對自己的策略保密，當齊王先行動時，哪一方會

贏？贏多少？反之呢？

例1-2有甲乙兩個囚犯正被隔離審訊，若兩人都坦白，則每人判入獄

8年；若兩個人都抵賴，則每人判入獄1年；若只有一人坦白，則他

初釋放，但另一罪犯被判刑10年。求雙方的最優(yōu)策略。

乙囚犯

抵賴坦白

甲囚犯抵賴-1,-1-10,0

坦白0,-10-8,-8

定義：運籌學(OperationResearch)是運用系統(tǒng)化的方法，通過建

成立數(shù)學模型及其測試，協(xié)助達成最佳決策的一門科學。它主要研究

經(jīng)濟活動和軍事活動中能用數(shù)學的分析和運算來有效地配置人力、物

力、財力等籌劃和管理方面的問題。

二、學習運籌學的方法

1、讀懂教材上的文字；

2、多練習做題，多動腦筋思考；

3、作業(yè)8次；

4、考試；

5、EXCEL操作與手動操作結合。

第一章線性規(guī)劃及單純形法

第一節(jié)線性規(guī)劃問題及其數(shù)學模型

（用實例引入）

例1-3美佳公司計劃制造I、II兩種產(chǎn)品，現(xiàn)已知各制造一件時分別

占用的設備A、B的臺時數(shù)，及測試工序所需要的時間。問該公司應

制造兩種家電各多少件時才能使獲取的利潤最大?

生產(chǎn)1件I產(chǎn)品生產(chǎn)1件I產(chǎn)品每天可用能力

（小時）

設備A（臺時）0515

設備B（臺時）6224

調(diào)試（小時）115

利潤（元）21

maZ=2%+x2

5x,<15

6國+2X2<24

x,+x2<5

,%,二220

學習必備一一一儂下或

例1?4有A、B、C三個工地，每天需要水泥各為17、18、15百袋。

為此甲、乙兩個水泥廠每天各生產(chǎn)23百袋和27百袋水泥供應這三個

工地。其單位運價如下表，求最佳調(diào)運方案。

水泥廠、ABC

甲11.52

乙242

地

水泥廠'ABC供應量/百袋

甲孫X\2XI323

乙X22X2327

需求量/百袋17181550

maxZ=+1.5X12+2xl3+2x2l+4x22+2x23

fMl+X[2+X13=23

x21+x22+x23=27

司+無21=17

st.<

xi2+x22=18

%+無23=15

Ix().>0(z=l,2;j=l,2,3)

線性規(guī)劃的基本概念

如果規(guī)劃問題的數(shù)學模型中，決策變量的取值是連續(xù)的整數(shù)、小

數(shù)、分數(shù)或實數(shù)，目標函數(shù)是決策變量的線性函數(shù)，約束條件是含決

學習必備一一一儂下或

策變量的線性等式或不等式，則稱這種規(guī)劃問題為線性規(guī)劃。

二、將線性規(guī)劃的普通型化為標準型

1、對于minZ=CX,可轉化為min(-Z)—CX；

2、當約束條件中出現(xiàn)出玉+%%2+…+%再工瓦時,在左邊加上一

個“松弛變量”職々0,使不等式變?yōu)榈仁?；當約束條件

中出現(xiàn)%X]+%工2+…+4〃%〃-bi時，則在左邊減去一個“松弛

變量”升+1之0。

3、當某個決策變量X/N0或符號不限時，則增加兩個決策變量

Xj和X；,令Xj=Xj-Xj;

4、當約束條件中有常數(shù)項々4)時、則在方程兩邊同乘以(-1)。

例1-5將下列非標準4型線性規(guī)劃問題轉化為標準型。

minZ=3玉-2x2+4x3

s,t.

r2x]+3X2+4X3>300

x+5X+6/<400

<]2

Xj+x2+x3<200

XpX2>0,%3不限

解：

min^Z)=-3x)+2x2—4(x3-x3+0x4+0x5+0x6

st.

j2X]+3X2+4(X3-X3)-X4>300

X]+5X+6(x3-/)+%<400

<2.

x1+x2+x3-￡+44200

學生練習：P42習題1.2。

二、學生練習(20分鐘)

三、課堂小結(5分鐘)

授課題目：

第二節(jié)圖解法

第三節(jié)單純形法原理

第四節(jié)單純法的計算步驟

教學目的與要求：

1.知識目標：用圖解法理解線性規(guī)劃的概念及單純形法中的幾個概念;

2.能力目標：掌握用圖解法和單純形法求解線性規(guī)劃的計算步驟；

3.素質(zhì)目標：培養(yǎng)學生良好的職業(yè)道德、樹立愛崗精神。

教學重點：

1、用圖解法求解線性規(guī)劃的計算步驟；

2、用單純形法求解線性規(guī)劃的計算步驟。

教學難點：

1、用單純形法求解線性規(guī)劃的計算原理;

2、用單純形法求解線性規(guī)劃的計算步驟。

教學過程：

1.舉例引入（5分鐘）

2.舉例講解新課（80分鐘）

（1）圖解法（20分鐘）

（2）單純形法原理（20分鐘）

（3）單純形法求解步驟（40分鐘）

3.課堂練習（穿插在例題講解過程中）

4.課堂小結（5分鐘）

5.布置作業(yè):要求學生完成P43習題1.4兩個小題。其中第1小題為作業(yè)一。

學習必備一一一儂下或

《線性規(guī)劃的求解》（2課時）

【教學流程圖】

以學生自學引入

圖解法

線性規(guī)劃求解方法介紹單純形法

EXCEL規(guī)劃求解法

坐標系

圖解法的操作步驟求出可行域

平移目標函數(shù)直線

化為標準型

單純形法的操作步驟J求出初始表

I迭代法

課堂小結

布置作業(yè)

【教學方法】

本課主要采用任務驅動和程序式思維相結合的教學方法，過程當中輔以案例

講解、啟發(fā)提問、自主學習和協(xié)作學習等方式。任務驅動是實現(xiàn)本課教學目標和

完成教學內(nèi)容的主要方法，任務是師生活動內(nèi)容的核心，在教學過程中，任務驅

動被多次利用。自主學習能提高學生的自主探究能力，競賽和協(xié)作學習調(diào)動學生

的積極性，激發(fā)學生參與的熱情。學生之間互幫互助，共同分享勞動果實，從而

激發(fā)了學生的團隊意識，達到理想的教學效果。

【教學內(nèi)容】

一、教學過程：

（一）舉例引入：（5分鐘）

復習中學數(shù)學中的圖解法。

導人提問：線性規(guī)劃圖解法中有哪些基本概念？

（-）新課：

第二節(jié)圖解法

一、圖解法的步驟

（以學生自學引入）

學生自學P16-17,教師檢查看不懂文字的學生，并做好記錄。

提問：以P44的1.4題第1小題為例，圖解法第一步是什么？以

下逐步提出問題。

教師演示并總結如下：圖解法適用于兩個決策變量的線性規(guī)劃非

標準型。步驟如下；

1、用決策變量建立直角坐標系；

2、對于每一個約束條件，先取等式畫出直線，然后取一已知點

（一般取原點）的坐標代入該直線方程的左邊，由其值是否

滿足約束條件的不等號及該已知點的位置來判斷它所在的

半平面是否為可行域。

3、令Z等于任一常數(shù)，畫出目標函數(shù)的直線，平移該直線，

直至它與凸多邊形可行域最右邊的角點相切，切點坐標則為

最優(yōu)解。

例1-5

maxZ=10xj+5x2

s.t.

3芭+4X2<9

<5xi+2X2<8

x,x>0

i*2

解

可行解一一滿足約束條件的解，全部可行解的集合叫可行域。

最優(yōu)解一一使目標函數(shù)達到最大值的可行解。

基變量一一利用矩陣的初等變換從約束條件的mXn（n〉m）階系數(shù)矩

陣找出一個mXm階單位子矩陣，它們對應的變量叫基變量，其余的

叫非基變量。

矩陣的初等變換一一將矩陣的一行同乘以一個數(shù)；將矩陣的一行同乘

以一個數(shù)，再加到另外一行上去。

二、單純形表迭代法

教師先演示：

1、化為標準型

2、做出初始單純形表，求出檢驗數(shù)；

3、確定檢驗數(shù)中最大正數(shù)所在的列為主元列，選擇主元列所對

應的非基變量為進基變量

4、按最小比值原則，用常數(shù)列各數(shù)除以主元列相對應的正商

數(shù)，取其最小比值，該比值所在的行為主元行；主元列與主

元行交叉的元素為主元，主元所對應的基變量為出基變量。

5、對含常數(shù)列的增廣矩陣用初等變換把主元變?yōu)?,主元所在

的列的其余元素化為0。

6、計算檢驗數(shù)，直到全部檢驗數(shù)小于等于0,迭代終止?；?/p>

量對應的常數(shù)列為最優(yōu)解，代入目標函數(shù)得最優(yōu)目標函數(shù)

值。

例1-6

maxZ=2x,+x2

r5X2<15

6%j+2占<24

%1+x2>5

,x2>0

解：先化為標準型:

maxZ=2X]+々+0x3+0x4+0x5

’5X2+x3=15

S.t.y6%[+2X2+x4=24

Xj+x2+x5=5

其約束條件的系數(shù)增廣矩陣為「05100151

6201024

^1100151

初始始基可行解為：X=(0,0,15,24,5)"以此列出單純形表如下。

得：X=(7/2,3/2,15/2,0,0,0)"代入目標函數(shù)得：

Z=2*7/2+1*3/2+15/2*0+0*0=17/2。

目標函數(shù)Cj21000常數(shù)

變量

xJ/J當加占

基變量

初X300510015

始f40[6]201024

表X50110015

計ZJ00000

算乙21000

0=minj,24/6,5/1)=24/6=4

第一00510015

次迭211/301/604

代00[2/3]0-1/611

Zj22/301/30

01/30-1/30

.1541、1

0=二min(z—,----,-----)------=3/2

51/32/32/3

第二00015/4-15/215/2

次迭陽21001/4-1/27/2

代1010-1/43/23/2

Z,2101/41/2

4000-1/4-1/2

4.課堂小結（5分鐘）

5.布置作業(yè)：要求學生完成P43習題1.4兩個小題。其中第1小題為作業(yè)一

授課題目：

第五節(jié)單純形法的進一步討論

教學目的與要求：

1.知識目標：理解求解線性規(guī)劃的人工變量法中大M法和兩階段法;

2.能力目標：利用習題1.15鞏固線性規(guī)劃的建模；

3.素質(zhì)目標：培養(yǎng)學生良好的職業(yè)道德、樹立愛崗精神。

教學重點：

1、求解線性規(guī)劃的人工變量法中兩階段法的計算步驟。

2、人工變量法與普通單純形法的區(qū)別。

教學難點：

1、兩階段法的計算步驟；

2、習題1.15中的約束條件分析。

教學過程：

1.舉例引入（5分鐘）

2.舉例講解新課（80分鐘）

（1）人工變量法（40分鐘）

（2）兩階段法（40分鐘）

3.課堂練習（穿插在例題講解過程中）

4.課堂小結與單純形法小結（5分鐘）

5.布置作業(yè)。

學習必備一一一儂下或

《單純形法的進一步討論》（2課時）

【教學流程圖】

用實例引入人工變量法

”「初始單純形表中無單位矩陣

人工變量法的例題講解工引入人工變量

L在目標函數(shù)中引入大M

lf兩階段法用EXCEL求解中的困難

兩階段法的例題講解《第一階段的模型

第二階段的模型

課堂小結

布置作業(yè)

【教學方法】

本課主要采用任務驅動和程序式思維相結合的教學方法，過程當中輔以案例

講解、啟發(fā)提問、自主學習和協(xié)作學習等方式。任務驅動是實現(xiàn)本課教學目標和

完成教學內(nèi)容的主要方法，任務是師生活動內(nèi)容的核心，在教學過程中，任務驅

動被多次利用。自主學習能提高學生的自主探究能力，競賽和協(xié)作學習調(diào)動學生

的積極性，激發(fā)學生參與的熱情。學生之間互幫互助，共同分享勞動果實，從而

激發(fā)了學生的團隊意識，達到理想的教學效果。

【教學內(nèi)容】

一、教學過程：

（二）舉例引入：（5分鐘）

復習單純形法。

導入提問：當初始單純形表中不出現(xiàn)單位矩陣怎么辦？

（二）新課：

第五節(jié)單純形法的進一步討論

學習必備一一一儂下或

（用實例引入人工變量法）

例1-7用單純形法求解下列線性規(guī)劃問題：

maxZ=2%j+3x2-5x3

r2+I2+￡=7

y2xl-5X2+x3>10

I%1,x2,x3>0

解：將第二個約束條件化為等式（左邊減去一個松弛變量）后，

約束條件的系數(shù)矩陣不存在單位矩陣，這時可在約束條件第一、二等

式的左邊分別加上一個人工變量作為初始基變量，使之出現(xiàn)單位矩

陣。為了使目標函數(shù)中的人工變量為0,令它們的系數(shù)為任意大的負

值“-M”，然后采用一般單純形表法求解。

minZ=2X]+3x2-5x3-Mx4+0x5-Mx6

rX]++%3+%4=7

<22-5X2+X3-4-X6=10

IX15X2,X3,X4,X5,X6>0

目標函數(shù)Cj23-5-M0-M常多

變量

玉1x2ix3%x5%

基變量Xj

初-M1111007

始表f6-M[2]-510-1110

計Zj-3M4M-2M-MM-M

算43M+23-4M2M-50-M0

6=min(7/U0/2)=5

學習必備一一一儂下或

一次f4-M0[7/2]1/211/2-1/22

迭代勺21-5/21/20-1/21/25

C7、，LM,..M,M,

Zj2——M-5-----+1-M-------1——+1

2222

c：A/0MAM3M

20—M+8-----60n——+1--------1

2222

x23011/72/71/7-1/74/7

xl2106/75/7-1/71/745/7

Z,2315/716/71/7-1/7

乙00-50/7-M-16/7-1/7-M+l/7

所以最優(yōu)解為：X=(45/7,4/7,0,0,0,0)

例1-8對LP模型：

minw=15>1+24%+5%

S.t.r6y2+>322

-5jj+2y2+y3>1

Iy-NO

用兩階段法求解。

解：先分為標準型：

max(-w)=-15y1-24y2-5y3+0y4+0x5

s.t.「6y2+當一>4+為=2

-5M+2y2+%—K+)'7=1

I必-720

對

minZ="+%

stJ6y2+%-+為=2

l5必+2y2+%-%+為=1

KN0

學習必備一一一儂下或

使用單純形法求解，化為標準型后，列出單純形表并迭代如下

目標函數(shù)Cj00000-1-1常數(shù)

逆策變量

yjM1WJ%%%為為

基變量

初-i0[6]1-10102

始表-i5210-1011

582-1-100

一次必0011/6-1/601/601/3

迭代f-1[5]02/31/3-1-1/311/3

502/31/3-1-4/30

必0011/6-1/601/601/3

>,10102/151/15-1/5-1/151/51/15

00000-1-1

在上表中的最終表中除去人工變量”，出后，回歸到原來的標準型:

max(-w)=-15%-24y2-5y3+0y4+Ox5

s.t.+%—%+%=2

15%+2y2+y3-y5+y7=1

Li.N0

然后對該最終表繼續(xù)使用單純形法計算：

目標函數(shù)-15-24-500常數(shù)

變量

M必為?>4%

基變量

初%-24011/6-1/601/3

始表-1510[2/15]1/15-1/51/15

0-96-3-3

一次%-24-5/410-1/41/41/4

迭代%-515/2011/2-3/21/2

-15/200-7/2-3/2

故y=(0,l/4,l/2,0,0)T

1.15題分析：

令i=l,2,3代表A,B,C三種商品，j=l,2,3代表前，中，后艙,

與20代表裝載于第j艙位的第i中商品的數(shù)量(件)。

1、目標函數(shù)為運費總收入：

maxZ=lOOQxn+x12+0)+70ax21+々2+尤23)+600(%31+x32+x33)

2、約束條件：

前中后艙載重限制：

8XH+6叫]+5X3I<2000

8X12+6X22+5工3243000

8X13+6式3+5X33<1500

前中后艙體積限制：

10xu+5X21+7X31<4000

10xl2+5122+7%3245400

10x[3+5X23+lx33<1500

三商品的數(shù)量限制:

學習必備一一一儂下或

孫+為2+113-600

x21+X22+尤23-1000

%31+*32+%33—8?！?/p>

艙體平衡條件：

前艙載重/中艙載重為：-(1-0.15)<8%||+6%2|+5^<^(1+0.15)

38元12+6122+5X323

后艙載重/中艙載重為：-(1-0.15)<8%13+6^23+5v-33<-(1+0.15)

28X12+6X22+5X322

前艙載重/后艙載重為：^(1-0.10)<^"+6^+5^'<^(1+0.10)

3網(wǎng)3+6々3+5%333

上三式中，2000/3000=2/3,1500/3000=1/2,2000/1500=4/30

3.課堂練習(穿插在例題講解過程中)

4.課堂小結與單純形法小結(5分鐘)

圖1-9：強調(diào)當非基變量的檢驗數(shù)為零時，線性規(guī)劃存在多重解。

5、布置作業(yè)二：1.15題

授課題目：

第二章：線性規(guī)劃的對偶理論與靈敏度分析

第一節(jié)線性規(guī)劃的對偶問題

第四節(jié)對偶單純形法

教學目的與要求:

1.知識目標：理解線性規(guī)劃的對偶問題與原問題的基本概念及二者的解之

間的關系；理解線性規(guī)劃單純形法求解的實質(zhì)；

2.能力目標：掌握求解線性規(guī)劃的對偶單純形法的計算步驟；

3.素質(zhì)目標：培養(yǎng)學生良好的職業(yè)道德、樹立愛崗精神。

教學重點:

1、對偶單純形法的計算步驟；

2、對偶單純形法與原問題單純形法求解思路上的區(qū)別。

教學難點:

1、對偶單純形法的計算步驟；

2、用單純形法求解線性規(guī)劃的實質(zhì)。

教學過程：

1.舉例引入（5分鐘）

2.舉例講解新課（80分鐘）

（1）對偶問題的基本概念與解的性質(zhì)；（20分鐘）

（2）對偶單純形法與原問題單純形法解之間的關系；（20分鐘）

（3）對偶單純形法與原問題單純形法的求解原理（20分鐘）

（4）對偶單純形法原理（20分鐘）求解步驟（20分鐘）

3.課堂練習（穿插在例題講解過程中）

4.課堂小結（5分鐘）

學習必備一一一儂下或

《線性規(guī)劃的對偶理論與對偶單純形法》（2課時）

【教學流程圖】

舉例引入

V廠對偶問題與原問題的結構特點

線性規(guī)劃的對偶問題的基本概念J對偶問題與原問題的解與單純形表

逐性規(guī)劃的單純形法求解實質(zhì)

vf初始表

對偶單純形法計算步驟］進基

I出基

8

學生練習（結合例題講解進行）

課堂小結

8

布置作業(yè)

【教學方法】

本課主要采用任務驅動和程序式思維相結合的教學方法，過程當中輔以案例

講解、啟發(fā)提問、自主學習和協(xié)作學習等方式。任務驅動是實現(xiàn)本課教學目標和

完成教學內(nèi)容的主要方法，任務是師生活動內(nèi)容的核心，在教學過程中，任務驅

動被多次利用。自主學習能提高學生的自主探究能力，競賽和協(xié)作學習調(diào)動學生

的積極性，激發(fā)學生參與的熱情。學生之間互幫互助，共同分享勞動果實，從而

激發(fā)了學生的團隊意識，達到理想的教學效果。

【教學內(nèi)容】

一、教學過程：

（一）舉例引入對偶問題的基本概念：（5分鐘）

導人提問：線性規(guī)劃的對偶問題與原問題的解是什么關系？

（-）新課：

第二章線性規(guī)劃的對偶理論與靈敏度分析

第一節(jié)線性規(guī)劃的對偶問題

回顧例1-3：

例1-3美佳公司計劃制造I、n兩種產(chǎn)品，現(xiàn)已知各制造一件時分別

占用的設備A、B的臺時數(shù)，及測試工序所需要的時間。問該公司應

制造兩種家電各多少件時才能使獲取的利潤最大？

生產(chǎn)1件I產(chǎn)品生產(chǎn)1件I產(chǎn)品每天可用能力

（小時）

設備A（臺時）0515

設備B（臺時）6224

調(diào)試（小時）115

利潤（元）21

解：設項和占為兩種產(chǎn)品的產(chǎn)量，得線性規(guī)劃問題:

maxZ=+x2

z-5x2<15

6x.+2%,<24

X

s工%1+x2<5

i再,42（）

現(xiàn)從另一角度提出問題：假定有某個公司想把美佳公司的資源收買過來，

它至少應付出多大代價，才能使美佳公司愿意放棄生產(chǎn)活動，出讓自己的資源？

設y，為，已分別為單位時間內(nèi)設備A,B和調(diào)試工序的出讓價格,

其線性規(guī)劃模型如下表：

學習必備一一一儂下或

原問題對偶問題

目標函數(shù)最大利潤為maxZ=2X|+x2,某公司最小出讓價為：

其中：minW=15y+24y2+5%，其中：

內(nèi)和超為兩種產(chǎn)品的產(chǎn)量。必，為。3分別為單位時間內(nèi)設備

A,B和調(diào)試工序的出讓價格。

原問題對偶問題

約束條件每生產(chǎn)1件商品在A,B設每生產(chǎn)1件商品的出讓價不小

備和調(diào)試工序上的時間約束6y2+%z2

于利潤：5y,+2y2+y3>l

r5x<15

2幾，為，必NO

<6%]+2%?24

為：%]+x2<5

xt,x2>0

可見:

原問題（系數(shù)為mXn矩陣）對偶問題（系數(shù)為nXm矩陣）

maxZminW

目標函數(shù)中的系數(shù)成為對偶問題約束約束條件中的右端常數(shù)成為原問題中

條件中的右端常數(shù)目標函數(shù)中的系數(shù)

約束條件系數(shù)矩陣為對偶問題約束條約束條件系數(shù)矩陣為原問題約束條

件系數(shù)矩陣的轉置。件系數(shù)矩陣的轉置。

約束條件數(shù)有m個，變量數(shù)m個，

第i個約束條件為“W”，第i個變量為“20”

第i個約束條件為“力”第i個變量為“W0”

第i個約束條件為“=”第i個變量為自由變量

變量數(shù)n個，約束條件數(shù)有n個，

第i個變量為“20”第i個約束條件為“2”，

第i個變量為“W0”第i個約束條件為“W”

第i個變量為自由變量第i個約束條件為“=”

例1-6和例1-8分別用單純形法和兩階段法可求得上述例題的原問題和其

對偶問題的最終單純形表如下:

目標函數(shù)321000

^變量原問題變量原問題松弛變量常數(shù)

基變量七%4%5

最當00015/4-15/215/2

不

終21001/4-1/27/2

X2

表1010-1/43/23/2

000-1/4-1/2

變量對偶問題剩余變重對偶問題變量

%M%％%

目標函數(shù)G-15-24-500常數(shù)

變量

力M為為?%%

基變量

一次%-24-5/410-1/41/41/4

迭代%-515/2011/2-3/21/2

乙-15/200-7/2-3/2

從上兩表看出兩個問題變量之間的對應關系，同時看出只需求解其中

一個問題，從最優(yōu)解的單純形表中同時得到另一個問題的最優(yōu)解。即原問

題的最優(yōu)解為：X=(7/2,3/2,0,0,0)，；其對偶問題的最優(yōu)解為：

r=(0,l/4,l/2,0,0)ro

對偶問題的基本性質(zhì)

1、若線性規(guī)劃原問題(LP)有最優(yōu)解，其對偶問題(DP)也有最優(yōu)解;

2、LP的檢驗數(shù)的相反數(shù)對應于其DP的一組基本解，其中第j個決策變

量七的檢驗數(shù)的相反數(shù)對應于DP第i個剩余變量與的解；LP第i個

松弛變量4的檢驗數(shù)的相反數(shù)對應于其DP的第i個對偶變量y的解。

反之DP的檢驗數(shù)對應于其LP的一組基本解。

例1-9

maxZ=6項-2x2+x3

.2xl-x2+2X3<2

<$+4%3<3

、％2o

解加入松弛變量8,七后，單純形表迭代為：

x

x2*3%5b

[2]-12102

X5104014

(6-2100

x\1-1/211/201

X50口⑵3-1/213

為01-5-30

104014

*2016-126

00-11-2-2

%>4%>2

設對偶變量為必和％，剩余變量為%，%，>5，由上性質(zhì)，有

y=（M，%，%，乂，K）=（一=，-4，-4，-4，-4）=（2,2,0,0,11）為對偶問題的基本解。

第四節(jié)對偶單純形法

一、對偶單純形法的原理

LP與DP在求解迭代過程中有三種情形:

LP的b列LP的檢驗數(shù)乙含義

均20均W0則DP的檢驗數(shù)4〈。且M20，這時

LP與DP均達到最優(yōu)解。

均20某個>>0則DP的某個變量匕.<0,說明原問題可

行，對偶問題不可行。

某個4Vo全部"WO則DP的檢驗數(shù)4WO且y’NO,說明原

問題不可行，對偶問題可行。

對于第二種情形用單純形法求解，第三種情形用對偶單純形法求解。

二、對偶單純形法求解過程

1、用實例引入：

例1-10

minW=3yl+9%

M+刈之2

M+4y223

M+7y223

力20

解引入非負松弛變量為一5?0,化為標準型;

maxZ=-3y,-9y2

弘+乂—g=2

H+4y2-乂=3

<y+7%_%=3

將三個約束式兩邊分別乘以-1,得

maxZ=-3y,-9y2

r_y_必+%=-2

-Y-4y2+”=_3

_y-7%+%=-3

iy#0

目標函數(shù)C,-3-9000

變量常數(shù)

當

yjM??>3>4%

基變量

初0[-1]-1100-2

始為0-1-4010-3

表%0-1-7001-3

計Zj00000

算為-3-9000

e=minJ3/—1,—9/-1)==3-3/-1-9/-1

第一必-311-1002

次迭一以00[-3]-110-1

代%00-6-101-1

Zj-3-3300

%0-6-300

0=min(-6/—3,-3/—1)=2-6/-3-3/-1

第二-310-4/31/305/3

次迭為-9011/3-1/301/3

代%0001-211

4-3-9120

00-1-20

最優(yōu)解為:Y=(5/3,1/3,0,0,1)

3、總結對偶單純形法求解過程:

由于用單純形法求解極大化線性規(guī)劃問題時一，通過迭代直至所有檢驗數(shù)

乙W0,這時所得最優(yōu)基也是對偶問題的可行基，因此單純形法的求解過程

是：在保持原始可行(即常數(shù)列保持10)的前提下，通過迭代實現(xiàn)對偶可

行（全部乙WO）。

換一個角度考慮線性規(guī)劃的求解過程：能否在保持對偶可行（全部

0）的前提下，通過迭代實現(xiàn)原始可行（即常數(shù)列保持10）?這就是對偶

單純形法的求解思路。

第一步：建立初始單純形表，計算檢驗數(shù)行，當全部人W0（非基變量

的4V0）時，如果常數(shù)項N0,即得最優(yōu)解。如常數(shù)項至少有一元素＜0,

且檢驗數(shù)仍然非正，則轉下一步。

第二步：將常數(shù)項＜0所在的約束條件兩邊同乘以T,將常數(shù)列全變

成非負，再使用原始單純形法求解。如果上述處理過程中出現(xiàn)原始可行基

不再是單位矩陣，可適當增加人工變量構造人造基，再用大M法求解。

第三步：進行基變換

先確定出基變量：選取常數(shù)列中絕對值最小的負元素對應的基變量出

基，相應行為主元行。然后確定入基變量：由最小比值原則，選

min4K.W0}=區(qū)所在的列為主元列。這里當為第j列的檢驗數(shù)，因為人對

應的主元行中非基變量的系數(shù)。主元行與主元列相交叉處的系數(shù)元素為主

元素勾，其對應的非基變量為換入基變量。

第四步：對主元素進行換基迭代后，用矩陣的初等變換將主元素變成

1,并把主元列變成單位向量，得到新的單純形表。

二、課堂練習（穿插在例題講解過程中）

三、課堂小結（5分鐘）

授課題目：

第二章第五節(jié)：靈敏度分析

教學目的與要求：

1.知識目標：理解求解線性規(guī)劃的單純形法中靈敏度分析的基本原理；

2.能力目標：分析J的變化；分析與的變化；增加一個變量為的分析。

3.素質(zhì)目標：培養(yǎng)學生良好的職業(yè)道德、樹立愛崗精神。

教學重點:

1、分析G的變化；

2、分析鳥.的變化；

3、增加一個變量無,的分析。

教學難點:

1、靈敏度的基本概念；

2、增加一個變量X）的分析。

教學過程：

1.舉例引入靈敏度（5分鐘）

2.舉例講解新課（80分鐘）

（1）靈敏度的基本概念；（20分鐘）

（2）分析弓的變化；（20分鐘）

（3）分析3的變化；（20分鐘）

（4）增加一個變量馬的分析。（20分鐘）

3.課堂練習（穿插在例題講解過程中）

4.課堂小結（5分鐘）

學習必備一一一儂下或

《靈敏度分析》（2課時）

【教學流程圖】

舉例引入靈敏度

線性規(guī)劃靈敏度的基本概念S分析黃敏度的方法

I線性規(guī)劃模型參數(shù)

d

「分析C,的變化

分析線性規(guī)劃模型中參數(shù)的變化，分析與的變化

I增加一個變量Xj的分析

學生練習（結合例題講解進行）

課堂小結

布置作業(yè)

【教學方法】

本課主要采用任務驅動和程序式思維相結合的教學方法，過程當中輔以案例

講解、啟發(fā)提問、自主學習和協(xié)作學習等方式。任務驅動是實現(xiàn)本課教學目標和

完成教學內(nèi)容的主要方法，任務是師生活動內(nèi)容的核心，在教學過程中，任務驅

動被多次利用。自主學習能提高學生的自主探究能力，競賽和協(xié)作學習調(diào)動學生

的積極性，激發(fā)學生參與的熱情。學生之間互幫互助，共同分享勞動果實，從而

激發(fā)了學生的團隊意識，達到理想的教學效果。

【教學內(nèi)容】

一、教學過程：

（二）舉例引入對偶問題的基本概念：（5分鐘）

導入提問：線性規(guī)劃的對偶問題與原問題的解是什么關系？

（二）新課：

第五節(jié)靈敏度分析

一、靈敏度分析的基本概念與原理

由LP單純形迭代法的基本原理:

將LP的標準型寫成矩陣形式:

maxZ=CX

s.t.rAX=b

Y

JX20

其約束條件的系數(shù)矩陣為A,加上人工基I（I為單位矩陣）以后，迭代

過程實際上為:

(All)-*(IA)

<3-10、

例1-11求矩陣A=-211的逆矩陣。

<2-14

解3-10100、

-211010

2-14001

&+R,,&+R、101110

-211010

005011

學習必備一一一儂下或

+2R]101110

=013230

0101/51/5

R1十(-1)夫3，R?+(―3)/?3「10014/5-1/51

010212/5-5/3

101/3)

0101/5

再看美佳公司的LP約束條件系數(shù)的初始表與最終表:

目標函數(shù)C/21000

士策變量常數(shù)

xJ

x2!X3z占

基變量

初七00510015

始一匕0[6]20