料必備___至迎下或

《運(yùn)籌學(xué)》教案

適用專(zhuān)業(yè)：

適用層次：本科

教學(xué)時(shí)間：20XX年上學(xué)期

授課題目：

緒論

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

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

教學(xué)目的與要求:

1.知識(shí)目標(biāo)：掌握運(yùn)籌學(xué)的概念和作用及其學(xué)習(xí)方法；掌握線(xiàn)性規(guī)劃的基

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

2.能力目標(biāo)：掌握線(xiàn)性規(guī)劃建模的標(biāo)準(zhǔn)形式及將普通模型化為標(biāo)準(zhǔn)模型的

方法。要求學(xué)生完成P43習(xí)題1.2兩個(gè)小題。

3.素質(zhì)目標(biāo)：培養(yǎng)學(xué)生良好的職業(yè)道德、樹(shù)立愛(ài)崗精神

教學(xué)重點(diǎn):

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

2、線(xiàn)性規(guī)劃建模的標(biāo)準(zhǔn)形式及將普通模型化為標(biāo)準(zhǔn)模型的方法。

教學(xué)難點(diǎn)：

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

2、將線(xiàn)性規(guī)劃模型的普通形式化為標(biāo)準(zhǔn)形式。

教學(xué)過(guò)程：

1.舉例引入（5分鐘）

2.新課（60分鐘）

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

（2）運(yùn)籌學(xué)與線(xiàn)性規(guī)劃的基本概念（20分鐘）

（3）結(jié)合例題講解線(xiàn)性規(guī)劃標(biāo)準(zhǔn)型的轉(zhuǎn)化方法

3.課堂練習(xí)（20分鐘）

4.課堂小結(jié)（5分鐘）

5.布置作業(yè)

學(xué)習(xí)必備一一一儂下或

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

【教學(xué)流程圖】

舉例引入，緒論

V「運(yùn)籌學(xué)

運(yùn)籌學(xué)與線(xiàn)性規(guī)劃的基本概M線(xiàn)性規(guī)劃

（結(jié)合例題講解）I線(xiàn)性規(guī)劃的標(biāo)準(zhǔn)型

目標(biāo)函數(shù)

結(jié)合例題v講解線(xiàn)性規(guī)劃標(biāo)準(zhǔn)型的轉(zhuǎn)化方法《約束條件的右端常數(shù)

約束條件為不等式

8

課堂練習(xí)

8

課堂小結(jié)

8

布置作業(yè)

【教學(xué)方法】

本課主要采用任務(wù)驅(qū)動(dòng)和程序式思維相結(jié)合的教學(xué)方法，過(guò)程當(dāng)中輔以案例

講解、啟發(fā)提問(wèn)、自主學(xué)習(xí)和協(xié)作學(xué)習(xí)等方式。任務(wù)驅(qū)動(dòng)是實(shí)現(xiàn)本課教學(xué)目標(biāo)和

完成教學(xué)內(nèi)容的主要方法，任務(wù)是師生活動(dòng)內(nèi)容的核心，在教學(xué)過(guò)程中，任務(wù)驅(qū)

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

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

激發(fā)了學(xué)生的團(tuán)隊(duì)意識(shí)，達(dá)到理想的教學(xué)效果。

【教學(xué)內(nèi)容】

一、教學(xué)過(guò)程：

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

（1）齊王賽馬的故事

(2)兩個(gè)囚犯的故事

導(dǎo)入提問(wèn)：什么叫運(yùn)籌學(xué)？

(二)新課：

緒論

一、運(yùn)籌學(xué)的基本概念

(用實(shí)例引入)

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

上馬、中馬、下馬中各選一匹馬來(lái)比賽，并且說(shuō)好每輸一匹馬就得支

付一千兩銀子給予獲勝者。當(dāng)時(shí)齊王的馬比田忌的馬強(qiáng)，結(jié)果每年田

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

試問(wèn)：如果雙方都不對(duì)自己的策略保密，當(dāng)齊王先行動(dòng)時(shí)，哪一方會(huì)

贏？贏多少？反之呢？

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

8年；若兩個(gè)人都抵賴(lài)，則每人判入獄1年；若只有一人坦白，則他

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

乙囚犯

抵賴(lài)坦白

甲囚犯抵賴(lài)-1,-1-10,0

坦白0,-10-8,-8

定義：運(yùn)籌學(xué)(OperationResearch)是運(yùn)用系統(tǒng)化的方法，通過(guò)建

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

經(jīng)濟(jì)活動(dòng)和軍事活動(dòng)中能用數(shù)學(xué)的分析和運(yùn)算來(lái)有效地配置人力、物

力、財(cái)力等籌劃和管理方面的問(wèn)題。

二、學(xué)習(xí)運(yùn)籌學(xué)的方法

1、讀懂教材上的文字；

2、多練習(xí)做題，多動(dòng)腦筋思考；

3、作業(yè)8次；

4、考試；

5、EXCEL操作與手動(dòng)操作結(jié)合。

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

第一節(jié)線(xiàn)性規(guī)劃問(wèn)題及其數(shù)學(xué)模型

（用實(shí)例引入）

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

占用的設(shè)備A、B的臺(tái)時(shí)數(shù)，及測(cè)試工序所需要的時(shí)間。問(wèn)該公司應(yīng)

制造兩種家電各多少件時(shí)才能使獲取的利潤(rùn)最大?

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

（小時(shí)）

設(shè)備A（臺(tái)時(shí)）0515

設(shè)備B（臺(tái)時(shí)）6224

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

利潤(rùn)（元）21

maZ=2%+x2

5x,<15

6國(guó)+2X2<24

x,+x2<5

,%,二220

學(xué)習(xí)必備一一一儂下或

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

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

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

水泥廠、ABC

甲11.52

乙242

地

水泥廠'ABC供應(yīng)量/百袋

甲孫X\2XI323

乙X22X2327

需求量/百袋17181550

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

fMl+X[2+X13=23

x21+x22+x23=27

司+無(wú)21=17

st.<

xi2+x22=18

%+無(wú)23=15

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

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

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

數(shù)、分?jǐn)?shù)或?qū)崝?shù)，目標(biāo)函數(shù)是決策變量的線(xiàn)性函數(shù)，約束條件是含決

學(xué)習(xí)必備一一一儂下或

策變量的線(xiàn)性等式或不等式，則稱(chēng)這種規(guī)劃問(wèn)題為線(xiàn)性規(guī)劃。

二、將線(xiàn)性規(guī)劃的普通型化為標(biāo)準(zhǔn)型

1、對(duì)于minZ=CX,可轉(zhuǎn)化為min(-Z)—CX；

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

個(gè)“松弛變量”職々0,使不等式變?yōu)榈仁剑划?dāng)約束條件

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

變量”升+1之0。

3、當(dāng)某個(gè)決策變量X/N0或符號(hào)不限時(shí)，則增加兩個(gè)決策變量

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

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

例1-5將下列非標(biāo)準(zhǔn)4型線(xiàn)性規(guī)劃問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)型。

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

學(xué)生練習(xí)：P42習(xí)題1.2。

二、學(xué)生練習(xí)(20分鐘)

三、課堂小結(jié)(5分鐘)

授課題目：

第二節(jié)圖解法

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

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

教學(xué)目的與要求：

1.知識(shí)目標(biāo)：用圖解法理解線(xiàn)性規(guī)劃的概念及單純形法中的幾個(gè)概念;

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

3.素質(zhì)目標(biāo)：培養(yǎng)學(xué)生良好的職業(yè)道德、樹(shù)立愛(ài)崗精神。

教學(xué)重點(diǎn)：

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

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

教學(xué)難點(diǎn)：

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

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

教學(xué)過(guò)程：

1.舉例引入（5分鐘）

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

（1）圖解法（20分鐘）

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

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

3.課堂練習(xí)（穿插在例題講解過(guò)程中）

4.課堂小結(jié)（5分鐘）

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

學(xué)習(xí)必備一一一儂下或

《線(xiàn)性規(guī)劃的求解》（2課時(shí)）

【教學(xué)流程圖】

以學(xué)生自學(xué)引入

圖解法

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

EXCEL規(guī)劃求解法

坐標(biāo)系

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

平移目標(biāo)函數(shù)直線(xiàn)

化為標(biāo)準(zhǔn)型

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

I迭代法

課堂小結(jié)

布置作業(yè)

【教學(xué)方法】

本課主要采用任務(wù)驅(qū)動(dòng)和程序式思維相結(jié)合的教學(xué)方法，過(guò)程當(dāng)中輔以案例

講解、啟發(fā)提問(wèn)、自主學(xué)習(xí)和協(xié)作學(xué)習(xí)等方式。任務(wù)驅(qū)動(dòng)是實(shí)現(xiàn)本課教學(xué)目標(biāo)和

完成教學(xué)內(nèi)容的主要方法，任務(wù)是師生活動(dòng)內(nèi)容的核心，在教學(xué)過(guò)程中，任務(wù)驅(qū)

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

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

激發(fā)了學(xué)生的團(tuán)隊(duì)意識(shí)，達(dá)到理想的教學(xué)效果。

【教學(xué)內(nèi)容】

一、教學(xué)過(guò)程：

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

復(fù)習(xí)中學(xué)數(shù)學(xué)中的圖解法。

導(dǎo)人提問(wèn)：線(xiàn)性規(guī)劃圖解法中有哪些基本概念？

（-）新課：

第二節(jié)圖解法

一、圖解法的步驟

（以學(xué)生自學(xué)引入）

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

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

下逐步提出問(wèn)題。

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

標(biāo)準(zhǔn)型。步驟如下；

1、用決策變量建立直角坐標(biāo)系；

2、對(duì)于每一個(gè)約束條件，先取等式畫(huà)出直線(xiàn)，然后取一已知點(diǎn)

（一般取原點(diǎn)）的坐標(biāo)代入該直線(xiàn)方程的左邊，由其值是否

滿(mǎn)足約束條件的不等號(hào)及該已知點(diǎn)的位置來(lái)判斷它所在的

半平面是否為可行域。

3、令Z等于任一常數(shù)，畫(huà)出目標(biāo)函數(shù)的直線(xiàn)，平移該直線(xiàn)，

直至它與凸多邊形可行域最右邊的角點(diǎn)相切，切點(diǎn)坐標(biāo)則為

最優(yōu)解。

例1-5

maxZ=10xj+5x2

s.t.

3芭+4X2<9

<5xi+2X2<8

x,x>0

i*2

解

可行解一一滿(mǎn)足約束條件的解，全部可行解的集合叫可行域。

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

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

陣找出一個(gè)mXm階單位子矩陣，它們對(duì)應(yīng)的變量叫基變量，其余的

叫非基變量。

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

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

二、單純形表迭代法

教師先演示：

1、化為標(biāo)準(zhǔn)型

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

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

應(yīng)的非基變量為進(jìn)基變量

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

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

元行交叉的元素為主元，主元所對(duì)應(yīng)的基變量為出基變量。

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

的列的其余元素化為0。

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

量對(duì)應(yīng)的常數(shù)列為最優(yōu)解，代入目標(biāo)函數(shù)得最優(yōu)目標(biāo)函數(shù)

值。

例1-6

maxZ=2x,+x2

r5X2<15

6%j+2占<24

%1+x2>5

,x2>0

解：先化為標(biāo)準(zhǔn)型:

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)"代入目標(biāo)函數(shù)得：

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

目標(biāo)函數(shù)Cj21000常數(shù)

變量

xJ/J當(dāng)加占

基變量

初X300510015

始f40[6]201024

表X50110015

計(jì)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

次迭陽(yáng)21001/4-1/27/2

代1010-1/43/23/2

Z,2101/41/2

4000-1/4-1/2

4.課堂小結(jié)（5分鐘）

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

授課題目：

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

教學(xué)目的與要求：

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

2.能力目標(biāo)：利用習(xí)題1.15鞏固線(xiàn)性規(guī)劃的建模；

3.素質(zhì)目標(biāo)：培養(yǎng)學(xué)生良好的職業(yè)道德、樹(shù)立愛(ài)崗精神。

教學(xué)重點(diǎn)：

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

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

教學(xué)難點(diǎn)：

1、兩階段法的計(jì)算步驟；

2、習(xí)題1.15中的約束條件分析。

教學(xué)過(guò)程：

1.舉例引入（5分鐘）

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

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

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

3.課堂練習(xí)（穿插在例題講解過(guò)程中）

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

5.布置作業(yè)。

學(xué)習(xí)必備一一一儂下或

《單純形法的進(jìn)一步討論》（2課時(shí)）

【教學(xué)流程圖】

用實(shí)例引入人工變量法

”「初始單純形表中無(wú)單位矩陣

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

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

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

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

第二階段的模型

課堂小結(jié)

布置作業(yè)

【教學(xué)方法】

本課主要采用任務(wù)驅(qū)動(dòng)和程序式思維相結(jié)合的教學(xué)方法，過(guò)程當(dāng)中輔以案例

講解、啟發(fā)提問(wèn)、自主學(xué)習(xí)和協(xié)作學(xué)習(xí)等方式。任務(wù)驅(qū)動(dòng)是實(shí)現(xiàn)本課教學(xué)目標(biāo)和

完成教學(xué)內(nèi)容的主要方法，任務(wù)是師生活動(dòng)內(nèi)容的核心，在教學(xué)過(guò)程中，任務(wù)驅(qū)

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

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

激發(fā)了學(xué)生的團(tuán)隊(duì)意識(shí)，達(dá)到理想的教學(xué)效果。

【教學(xué)內(nèi)容】

一、教學(xué)過(guò)程：

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

復(fù)習(xí)單純形法。

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

（二）新課：

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

學(xué)習(xí)必備一一一儂下或

（用實(shí)例引入人工變量法）

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

maxZ=2%j+3x2-5x3

r2+I2+￡=7

y2xl-5X2+x3>10

I%1,x2,x3>0

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

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

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

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

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

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

rX]++%3+%4=7

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

IX15X2,X3,X4,X5,X6>0

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

變量

玉1x2ix3%x5%

基變量Xj

初-M1111007

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

計(jì)Zj-3M4M-2M-MM-M

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

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

學(xué)習(xí)必備一一一儂下或

一次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對(duì)LP模型：

minw=15>1+24%+5%

S.t.r6y2+>322

-5jj+2y2+y3>1

Iy-NO

用兩階段法求解。

解：先分為標(biāo)準(zhǔn)型：

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

s.t.「6y2+當(dāng)一>4+為=2

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

I必-720

對(duì)

minZ="+%

stJ6y2+%-+為=2

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

KN0

學(xué)習(xí)必備一一一儂下或

使用單純形法求解，化為標(biāo)準(zhǔn)型后，列出單純形表并迭代如下

目標(biāo)函數(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

在上表中的最終表中除去人工變量”，出后，回歸到原來(lái)的標(biāo)準(zhǔn)型:

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

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

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

Li.N0

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

目標(biāo)函數(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、目標(biāo)函數(shù)為運(yùn)費(fèi)總收入：

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ù)量限制:

學(xué)習(xí)必備一一一儂下或

孫+為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.課堂練習(xí)(穿插在例題講解過(guò)程中)

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

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

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

授課題目：

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

第一節(jié)線(xiàn)性規(guī)劃的對(duì)偶問(wèn)題

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

教學(xué)目的與要求:

1.知識(shí)目標(biāo)：理解線(xiàn)性規(guī)劃的對(duì)偶問(wèn)題與原問(wèn)題的基本概念及二者的解之

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

2.能力目標(biāo)：掌握求解線(xiàn)性規(guī)劃的對(duì)偶單純形法的計(jì)算步驟；

3.素質(zhì)目標(biāo)：培養(yǎng)學(xué)生良好的職業(yè)道德、樹(shù)立愛(ài)崗精神。

教學(xué)重點(diǎn):

1、對(duì)偶單純形法的計(jì)算步驟；

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

教學(xué)難點(diǎn):

1、對(duì)偶單純形法的計(jì)算步驟；

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

教學(xué)過(guò)程：

1.舉例引入（5分鐘）

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

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

（2）對(duì)偶單純形法與原問(wèn)題單純形法解之間的關(guān)系；（20分鐘）

（3）對(duì)偶單純形法與原問(wèn)題單純形法的求解原理（20分鐘）

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

3.課堂練習(xí)（穿插在例題講解過(guò)程中）

4.課堂小結(jié)（5分鐘）

學(xué)習(xí)必備一一一儂下或

《線(xiàn)性規(guī)劃的對(duì)偶理論與對(duì)偶單純形法》（2課時(shí)）

【教學(xué)流程圖】

舉例引入

V廠對(duì)偶問(wèn)題與原問(wèn)題的結(jié)構(gòu)特點(diǎn)

線(xiàn)性規(guī)劃的對(duì)偶問(wèn)題的基本概念J對(duì)偶問(wèn)題與原問(wèn)題的解與單純形表

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

vf初始表

對(duì)偶單純形法計(jì)算步驟］進(jìn)基

I出基

8

學(xué)生練習(xí)（結(jié)合例題講解進(jìn)行）

課堂小結(jié)

8

布置作業(yè)

【教學(xué)方法】

本課主要采用任務(wù)驅(qū)動(dòng)和程序式思維相結(jié)合的教學(xué)方法，過(guò)程當(dāng)中輔以案例

講解、啟發(fā)提問(wèn)、自主學(xué)習(xí)和協(xié)作學(xué)習(xí)等方式。任務(wù)驅(qū)動(dòng)是實(shí)現(xiàn)本課教學(xué)目標(biāo)和

完成教學(xué)內(nèi)容的主要方法，任務(wù)是師生活動(dòng)內(nèi)容的核心，在教學(xué)過(guò)程中，任務(wù)驅(qū)

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

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

激發(fā)了學(xué)生的團(tuán)隊(duì)意識(shí)，達(dá)到理想的教學(xué)效果。

【教學(xué)內(nèi)容】

一、教學(xué)過(guò)程：

（一）舉例引入對(duì)偶問(wèn)題的基本概念：（5分鐘）

導(dǎo)人提問(wèn)：線(xiàn)性規(guī)劃的對(duì)偶問(wèn)題與原問(wèn)題的解是什么關(guān)系？

（-）新課：

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

第一節(jié)線(xiàn)性規(guī)劃的對(duì)偶問(wèn)題

回顧例1-3：

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

占用的設(shè)備A、B的臺(tái)時(shí)數(shù)，及測(cè)試工序所需要的時(shí)間。問(wèn)該公司應(yīng)

制造兩種家電各多少件時(shí)才能使獲取的利潤(rùn)最大？

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

（小時(shí)）

設(shè)備A（臺(tái)時(shí)）0515

設(shè)備B（臺(tái)時(shí)）6224

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

利潤(rùn)（元）21

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

maxZ=+x2

z-5x2<15

6x.+2%,<24

X

s工%1+x2<5

i再,42（）

現(xiàn)從另一角度提出問(wèn)題：假定有某個(gè)公司想把美佳公司的資源收買(mǎi)過(guò)來(lái)，

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

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

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

學(xué)習(xí)必備一一一儂下或

原問(wèn)題對(duì)偶問(wèn)題

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

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

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

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

原問(wèn)題對(duì)偶問(wèn)題

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

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

于利潤(rùn)：5y,+2y2+y3>l

r5x<15

2幾，為，必NO

<6%]+2%?24

為：%]+x2<5

xt,x2>0

可見(jiàn):

原問(wèn)題（系數(shù)為mXn矩陣）對(duì)偶問(wèn)題（系數(shù)為nXm矩陣）

maxZminW

目標(biāo)函數(shù)中的系數(shù)成為對(duì)偶問(wèn)題約束約束條件中的右端常數(shù)成為原問(wèn)題中

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

約束條件系數(shù)矩陣為對(duì)偶問(wèn)題約束條約束條件系數(shù)矩陣為原問(wèn)題約束條

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

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

第i個(gè)約束條件為“W”，第i個(gè)變量為“20”

第i個(gè)約束條件為“力”第i個(gè)變量為“W0”

第i個(gè)約束條件為“=”第i個(gè)變量為自由變量

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

第i個(gè)變量為“20”第i個(gè)約束條件為“2”，

第i個(gè)變量為“W0”第i個(gè)約束條件為“W”

第i個(gè)變量為自由變量第i個(gè)約束條件為“=”

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

對(duì)偶問(wèn)題的最終單純形表如下:

目標(biāo)函數(shù)321000

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

基變量七%4%5

最當(dāng)00015/4-15/215/2

不

終21001/4-1/27/2

X2

表1010-1/43/23/2

000-1/4-1/2

變量對(duì)偶問(wèn)題剩余變重對(duì)偶問(wèn)題變量

%M%％%

目標(biāo)函數(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

從上兩表看出兩個(gè)問(wèn)題變量之間的對(duì)應(yīng)關(guān)系，同時(shí)看出只需求解其中

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

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

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

對(duì)偶問(wèn)題的基本性質(zhì)

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

2、LP的檢驗(yàn)數(shù)的相反數(shù)對(duì)應(yīng)于其DP的一組基本解，其中第j個(gè)決策變

量七的檢驗(yàn)數(shù)的相反數(shù)對(duì)應(yīng)于DP第i個(gè)剩余變量與的解；LP第i個(gè)

松弛變量4的檢驗(yàn)數(shù)的相反數(shù)對(duì)應(yīng)于其DP的第i個(gè)對(duì)偶變量y的解。

反之DP的檢驗(yàn)數(shù)對(duì)應(yīng)于其LP的一組基本解。

例1-9

maxZ=6項(xiàng)-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

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

y=（M，%，%，乂，K）=（一=，-4，-4，-4，-4）=（2,2,0,0,11）為對(duì)偶問(wèn)題的基本解。

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

一、對(duì)偶單純形法的原理

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

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

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

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

均20某個(gè)>>0則DP的某個(gè)變量匕.<0,說(shuō)明原問(wèn)題可

行，對(duì)偶問(wèn)題不可行。

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

問(wèn)題不可行，對(duì)偶問(wèn)題可行。

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

二、對(duì)偶單純形法求解過(guò)程

1、用實(shí)例引入：

例1-10

minW=3yl+9%

M+刈之2

M+4y223

M+7y223

力20

解引入非負(fù)松弛變量為一5?0,化為標(biāo)準(zhǔn)型;

maxZ=-3y,-9y2

弘+乂—g=2

H+4y2-乂=3

<y+7%_%=3

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

maxZ=-3y,-9y2

r_y_必+%=-2

-Y-4y2+”=_3

_y-7%+%=-3

iy#0

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

變量常數(shù)

當(dāng)

yjM??>3>4%

基變量

初0[-1]-1100-2

始為0-1-4010-3

表%0-1-7001-3

計(jì)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、總結(jié)對(duì)偶單純形法求解過(guò)程:

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

乙W0,這時(shí)所得最優(yōu)基也是對(duì)偶問(wèn)題的可行基，因此單純形法的求解過(guò)程

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

行（全部乙WO）。

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

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

單純形法的求解思路。

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

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

且檢驗(yàn)數(shù)仍然非正，則轉(zhuǎn)下一步。

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

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

不再是單位矩陣，可適當(dāng)增加人工變量構(gòu)造人造基，再用大M法求解。

第三步：進(jìn)行基變換

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

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

min4K.W0}=區(qū)所在的列為主元列。這里當(dāng)為第j列的檢驗(yàn)數(shù)，因?yàn)槿藢?duì)

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

元素勾，其對(duì)應(yīng)的非基變量為換入基變量。

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

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

二、課堂練習(xí)（穿插在例題講解過(guò)程中）

三、課堂小結(jié)（5分鐘）

授課題目：

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

教學(xué)目的與要求：

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

2.能力目標(biāo)：分析J的變化；分析與的變化；增加一個(gè)變量為的分析。

3.素質(zhì)目標(biāo)：培養(yǎng)學(xué)生良好的職業(yè)道德、樹(shù)立愛(ài)崗精神。

教學(xué)重點(diǎn):

1、分析G的變化；

2、分析鳥(niǎo).的變化；

3、增加一個(gè)變量無(wú),的分析。

教學(xué)難點(diǎn):

1、靈敏度的基本概念；

2、增加一個(gè)變量X）的分析。

教學(xué)過(guò)程：

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

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

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

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

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

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

3.課堂練習(xí)（穿插在例題講解過(guò)程中）

4.課堂小結(jié)（5分鐘）

學(xué)習(xí)必備一一一儂下或

《靈敏度分析》（2課時(shí)）

【教學(xué)流程圖】

舉例引入靈敏度

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

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

d

「分析C,的變化

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

I增加一個(gè)變量Xj的分析

學(xué)生練習(xí)（結(jié)合例題講解進(jìn)行）

課堂小結(jié)

布置作業(yè)

【教學(xué)方法】

本課主要采用任務(wù)驅(qū)動(dòng)和程序式思維相結(jié)合的教學(xué)方法，過(guò)程當(dāng)中輔以案例

講解、啟發(fā)提問(wèn)、自主學(xué)習(xí)和協(xié)作學(xué)習(xí)等方式。任務(wù)驅(qū)動(dòng)是實(shí)現(xiàn)本課教學(xué)目標(biāo)和

完成教學(xué)內(nèi)容的主要方法，任務(wù)是師生活動(dòng)內(nèi)容的核心，在教學(xué)過(guò)程中，任務(wù)驅(qū)

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

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

激發(fā)了學(xué)生的團(tuán)隊(duì)意識(shí)，達(dá)到理想的教學(xué)效果。

【教學(xué)內(nèi)容】

一、教學(xué)過(guò)程：

（二）舉例引入對(duì)偶問(wèn)題的基本概念：（5分鐘）

導(dǎo)入提問(wèn)：線(xiàn)性規(guī)劃的對(duì)偶問(wèn)題與原問(wèn)題的解是什么關(guān)系？

（二）新課：

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

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

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

將LP的標(biāo)準(zhǔn)型寫(xiě)成矩陣形式:

maxZ=CX

s.t.rAX=b

Y

JX20

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

過(guò)程實(shí)際上為:

(All)-*(IA)

<3-10、

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

<2-14

解3-10100、

-211010

2-14001

&+R,,&+R、101110

-211010

005011

學(xué)習(xí)必備一一一儂下或

+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ù)的初始表與最終表:

目標(biāo)函數(shù)C/21000

士策變量常數(shù)

xJ

x2!X3z占

基變量

初七00510015

始一匕0[6]20