運籌學(xué)教案(胡運權(quán)版)

授課題目：

緒論

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

1.知識目標(biāo)：掌握運籌學(xué)的概念和作用及其學(xué)習(xí)方法

2.能力目標(biāo)：掌握運籌學(xué)的數(shù)學(xué)模型

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

教學(xué)重點：

運籌學(xué)的數(shù)學(xué)模型

教學(xué)難點：

運籌學(xué)的數(shù)學(xué)模型

教學(xué)過程：

1.舉例引入（5分鐘）

2.新課（60分鐘）

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

（2）運籌學(xué)與管理學(xué)（30分鐘）

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

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

5.布置作業(yè)

《緒論》(2課時)

【教學(xué)流程圖】

舉例引入，緒論

v「運籌學(xué)

運籌學(xué)與數(shù)學(xué)模型的基本概"管理學(xué)

課堂練習(xí)

課堂小結(jié)

布置作業(yè)

【教學(xué)方法】

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

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

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

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

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

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

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

一、教學(xué)過程：

(-)舉例引入：(5分鐘)

(1)齊王賽馬的故事

(2)兩個囚犯的故事

導(dǎo)人提問：什么叫運籌學(xué)？

(二)新課：

緒論

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

(用實例引入)

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

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

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

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

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

贏？贏多少？反之呢？

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

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

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

乙囚犯

抵賴坦白

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

坦白0,-10-8，-8

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

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

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

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

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

1、讀懂教材上的文字；

2、多練習(xí)做題，多動腦筋思考;

3、作業(yè)8次；

4、考試；

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

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

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

授課題目：

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

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

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

1.知識目標(biāo)：掌握線性規(guī)劃的基本概念和兩種基本建模方法。

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

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

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

教學(xué)重點：

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

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

教學(xué)難點：

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

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

教學(xué)過程：

1.舉例引入（5分鐘）

2.新課（60分鐘）

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

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

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

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

5.布置作業(yè)

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

【教學(xué)流程圖】

■?運籌學(xué)

運籌學(xué)與線性規(guī)劃的基本概念線性協(xié)劃

以性規(guī)劃的標(biāo)準(zhǔn)型

（結(jié)合例題講解）

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

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

約束條件為不等式

0

課堂練習(xí)

8

課堂小結(jié)

8

布置作業(yè)

【教學(xué)方法】

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

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

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

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

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

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

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

-、教學(xué)過程：

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

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

（用實例引入）

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

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

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

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

（小時）

設(shè)備A（臺時）0515

設(shè)備B（臺H寸）6224

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

利潤（元）21

maxZ=2玉+x2

z-5^2<15

+2X7<24

X-

x1+x2<5

l220

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

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

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

地

水泥廠'ABC

甲11.52

乙242

地

ABC供應(yīng)量/百袋

水泥廠

甲孫X\2X\323

乙X2\X22X2327

需求量/百袋17181550

maxZ=xH+1.5X12+2x13+2x21+4x22+2x23

rX“+X|2+%3=23

%2I+X22+X23=27

+x21=17

x[2+x22=18

$3+々3=15

l馬？0(i=l,2;/=123)

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

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

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

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

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

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

2、當(dāng)約束條件中出現(xiàn)由西+ai2x2+…+用時,在左邊加上一

個“松弛變量”職R0,使不等式變?yōu)榈仁?；?dāng)約束條件

中出現(xiàn)％內(nèi)+的々+???+%/“汕.時,則在左邊減去一個“松弛

變量xi+l>0o

3、當(dāng)某個決策變量x/0或符號不限時，則增加兩個決策變量

Xj和Xj9令X/=Xj_Xj;

4、當(dāng)約束條件中有常數(shù)項〃/O時、則在方程兩邊同乘以（-1）。

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

minZ=3xl-2x2+4x3

s.t.

r2X]+3X2+4X3>300

+5X2+6X3<400

Xj+x2+x3<200

l%，了220,與不限

解：

min（-Z）=-3Xj+2x2-4（x3-%;+0x4+0x5+0x6

s.t.

r2%14-3X2+4（尤3-X3）-x4>300

Xj+5X2+6（x3-x；）+尤5<400

x,+x2+x3-x3+x6<200

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

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

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

授課題目：

第二節(jié)圖解法

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

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

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

2.能力目標(biāo)：掌握用圖解法和單純形法求解線性規(guī)劃的原理；

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

教學(xué)重點：

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

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

教學(xué)難點：

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

教學(xué)過程：

1.舉例引入（5分鐘）

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

（1）圖解法（40分鐘）

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

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

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

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

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

【教學(xué)流程圖】

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

V「圖解法

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

匚EXCEL規(guī)劃求解法

V坐標(biāo)系

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

、平移目標(biāo)函數(shù)直線

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

單純形法的原理-

1I迭代法

課堂小結(jié)

布置作業(yè)

【教學(xué)方法】

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

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

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

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

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

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

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

?、教學(xué)過程：

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

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

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

（二）新課：

第二節(jié)圖解法

一、圖解法的步驟

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

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

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

下逐步提出問題。

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

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

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

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

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

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

半平面是否為可行域。

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

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

優(yōu)解。

例1-5

maxZ=10%1+5x2

s.t.

+4X2<9

y5尤］+2X2<8

X|x>0

X.,2

解

￡

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

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

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

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

叫非基變量。

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

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

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

5.布置作業(yè)：要求學(xué)生完成P43習(xí)題1.3兩個小題。

授課題目：

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

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

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

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

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

教學(xué)重點：

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

教學(xué)難點：

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

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

教學(xué)過程：

1.舉例引入（5分鐘）

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

單純形法求解步驟

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

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

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

第四節(jié)《單純法的計算步驟》（2課時）

【教學(xué)流程圖】

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

V「圖解法

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

LEXCEL規(guī)劃求解法

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

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

JI迭代法

課堂小結(jié)

布置作業(yè)

【教學(xué)方法】

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

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

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

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

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

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

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

-、教學(xué)過程：

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

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

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

（二）新課：

一、三個基本定理

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

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

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

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

叫非基變量。

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

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

二、單純形表迭代法

教師先演示：

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

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

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

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

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

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

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

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

的列的其余元素化為0。

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

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

值。

例1-6

maxZ=2玉+x2

<5X2<15

6x}+2X2<24

x1+x2>5

l芭,々20

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

maxZ=2x]+x2+0x3+0x4+0x5

5X2+x3=15

s.t.6x)+2X2+%4=24

%1+x2+x5=5

IxI9x2,x3,x4,x5>0

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

r05100151

6201024

^110015」

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

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

Z=2*7/2+1*^2+15/2*0+0*0=17/2O

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

變量

xxx

X]12Ix345

基變量

初X300510015

始?40[6]201024

表X50110015

計Zj00000

算221000

。=min(-,24/6,5/1)=24/6：=4

第一00510015

次迭21卑01/604

代000-1^11

Z,2羽00

030-卑0

^=min(—,—,-^)=-^=3/2

51/32/32/3

第二七0001小-15/215/2

次迭當(dāng)21001A-1727R

代X21010-1/4切切

ZJ2101/4V2

為000-1A-V2

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

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

授課題目：

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

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

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

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

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

教學(xué)重點：

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

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

教學(xué)難點：

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

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

教學(xué)過程：

1.舉例引入（5分鐘）

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

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

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

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

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

5.布置作業(yè)。

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

【教學(xué)流程圖】

用實例引入人工變量法

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

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

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

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

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

L第二階段的模型

8

課堂小結(jié)

V

布置作業(yè)

【教學(xué)方法】

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

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

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

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

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

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

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

一、教學(xué)過程：

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

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

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

（二）新課：

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

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

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

maxZ=2工1+3x2-5x3

rXj+X2+X3=7

<2x]-5X2+x3>10

-xJ,x2,>0

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

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

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

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

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

minZ=22+3x2-5x3-Mx4+0x5-Mxb

rXj+X2++X4=7

<2x1-5X2+尢3-/+%6=10

目標(biāo)函數(shù)C,23-5-M0-M常婁

變量

尤11X2IX3尤4龍5X6

基變量XJ

初%-M1111007

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

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

算”,3M+23-4M2M-50-M0

e=min(7/l,10/2)=5

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

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

C1-uM1RAM1M1

Z,2—M-5-----F1-M------1----F1

2222

(0-M+8----60---FI------1

2222

x23011/72/73/7-1/74/7

玉2106/75/7-1/71/74y7

Zj2315/71^71/7-1/7

00-50/7-M-1^7-1/7-M+1/7

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

例1-8對LP模型:

minw=15y)+24y2+5%

s.t,「6%+為22

?+2y2+y3>\

I

用兩階段法求解。

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

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

S.t.r6y2+%-%+兒=2

5%+2%+>3一>5+>7=1

「必.720

對

minZ=兒+乃

6%+%-”+%=2

s.t.

5y+2%+%-K+乃=1

%-720

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

目標(biāo)函數(shù)300000-1-1常數(shù)

變量

必1%I為％K%y?

基變量

初兒-10[6]1-10102

始表->7-15210-1011

為582-1-100

一次001%-%0壞0本

迭代f-1[5]0羽火-1-1/31

(502/31/3-1-4/30

%001%-1/60lyB0電

y010羽51/15-1/5-1/15V51/15

(00000-1-1

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

max(-vv)=-15^-24y2-5y3+0y4-f-Ox5

s.t.16乃+%-%+”=2

]5yl+2y2+y3-y5+y7=1

13?o

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

目標(biāo)函數(shù)5-15-24-500常數(shù)

變量

%>2>3?>4%

基變量

初-2401必-1/60本

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

%0-96-3-3

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

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

-1^200-7/2-3/2

故y=(0,1/4,1/2,0,0)'

1.15題分析：

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

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

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

maxZ=1000(卬+x}2+x13)+700(x21+x22+x23)+600(x3|+x32+x33)

2、約束條件：

前中后艙載重限制：

8孫+6%2i+5/12000

8X12+6X22+5l32<3000

8X13+6叫3+5X33<1500

前中后艙體積限制：

1+7X

10xH+5當(dāng)31<4000

5X+7X

10x12+2232<5400

10元]3+5尤23+7^33<1500

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

X1]+尤]2+X13-600

x21+x22+工2341000

x3}+x32+x33<800

艙體平衡條件：

前艙載重/中艙載重為：-(1-0.15)<8V[1+6-"21+5^31<-(1+0.15)

38%12+6]22+5九323

后艙載重/中艙載重為：-(1-0.15)<8仆+6心+5丘<_L(i+o.i5)

28玉2+6X22+5X322

6

前艙載重/后艙載重為：-(1-0.10)<+匕1+5%<1(1+0.10)

38為3+6123+5X333

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

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

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

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

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

授課題目：

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

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

第二節(jié)對偶問題的基本性質(zhì)

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

1.知識目標(biāo)：掌握一般形式對偶問題的對應(yīng)規(guī)律、理解并應(yīng)用對偶定理

2.能力目標(biāo)：掌握線性規(guī)劃的對偶問題的基本性質(zhì)；

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

教學(xué)重點：

一般形式對偶問題的對應(yīng)規(guī)律、對偶定理

教學(xué)難點：

對偶定理

教學(xué)過程：

1.舉例引入（5分鐘）

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

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

（2）一般形式的對偶問題

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

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

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

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

【教學(xué)流程圖】

舉例引入

”「對偶問題與原問題的結(jié)構(gòu)特點

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

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

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

8

課堂小結(jié)

V

布置作業(yè)

【教學(xué)方法】

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

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

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

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

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

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

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

一、教學(xué)過程：

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

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

（二）新課：

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

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

回顧例1-3：

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

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

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

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

（小時）

設(shè)備A（臺時）0515

設(shè)備B（臺時）6224

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

利潤（元）21

解：設(shè)當(dāng)和當(dāng)為兩種產(chǎn)品的產(chǎn)量，得線性規(guī)劃問題:

maxZ=2玉+x2

5%2<15

6%1+2X2<24

s'+x2<5

i玉>0

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

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

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

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

原問題對偶問題

目標(biāo)函數(shù)最大利潤為maxZ=2再+%，某公司最小出讓價為：

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

王和乙為兩種產(chǎn)品的產(chǎn)量。M，為，為分別為單位時間內(nèi)設(shè)備

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

原問題對偶問題

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

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

于利潤:5%+2%+%21

<5%2<15

幾，為，>320

<6x]+2x2<24

為：%1+x2<5

%,馬>0

可見:

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

maxZminW

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

基變量X]x2x3x4x5

最X3000104-15/215/2

占

終21001/4-1/27/2.

表10101AM切

000-1A-1/2

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

)3%y%%

目標(biāo)函數(shù)Cj-15-24-500

變量常數(shù)

月必必I%y5

基變量

一次丁2-24-5/410-1/41A1A

迭代%-51^2011/2-3/23

-1E/200-7/2-3/2

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

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

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

/=(0,1/4,1/2,0,0)ro

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

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

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

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

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

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

例1-9

maxZ=6七一2x2+x3

/2xl-々+2九3-2

<%+4X3<3

-玉.320

解加入松弛變量尤4,%后，單純形表迭代為：

X}x2%3匕尤5b

[2]-12102

104014

46-2100

1-V2.101

X50[1/2]3-1/213

(01-5-30

再104014

x2016-126

%00-11-2-2

%y4)5>2

設(shè)對偶變量為y和力，剩余變量為%，以，%，由上性質(zhì)，有

丫=（%，為，內(nèi)，＞4，卜5）=（-%4，-4，-4，-九2，-4）=（2,2,0,0,11）為對偶問題的基本解O

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

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

授課題目：

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

第三節(jié)影子價格

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

1.知識目標(biāo)：了解影子價格的實質(zhì)

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

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

教學(xué)重點：

對影子價格的理解。

教學(xué)難點：

對影子價格的理解

教學(xué)過程：

1.舉例引入（5分鐘）

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

（1）影子價格的概念

（2）影子價格的實質(zhì)

（3）影子價格的性質(zhì)與計算

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

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

《影子價格》（2課時）

【教學(xué)流程圖】

舉例引入

V

線性規(guī)劃影子價格基本概念

影子價格的實質(zhì)

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

V

課堂小結(jié)

V

布置作業(yè)

【教學(xué)方法】

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

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

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

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

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

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

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

■、教學(xué)過程：

（二）舉例引入影子價格的基本概念：（5分鐘）

導(dǎo)入提問：什么是影子價格？

(二)新課：

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

第三節(jié)影子價格

對偶變量的意義——代表在資源最優(yōu)利用條件下對單位第

種資源的估價，這種估價不是資源的市場價格，而是根據(jù)資源在生產(chǎn)

中作出的貢獻(xiàn)而作的估價，為區(qū)別起見，稱為影子價格(shadow

price)o

z*=w*=Y*b=?='(2.26)

對bi求偏導(dǎo)數(shù)，得到：

*

^7-=Z

如，(2.27)

即第i種資源影子價格yi*是z*對資源數(shù)量bi的變化率，是第i種資源增

加一個單位時，最大產(chǎn)值的改變量。

1.資源的市場價格是已知數(shù)，相對比較穩(wěn)定，而它的影子價格則有賴于資

源的利用情況，是未知數(shù)。由于企業(yè)生產(chǎn)任務(wù)、產(chǎn)品結(jié)構(gòu)等情況發(fā)生變化，資源

的影子價格也隨之改變。

資源的影子價格實際上又是--種機會成本.

在純市場經(jīng)濟條件下，當(dāng)?shù)?種資源(設(shè)備B)的影子價格是

0.25,當(dāng)市場價格高于0.25時，可以賣出這種資源；

相反當(dāng)市場價格低于影子價格時，就會買入這種資源。

隨著資源的買進(jìn)賣出，它的影子價格也將隨之發(fā)生變化，一直

到影子價格與市場價格保持同等水平時，才處于平衡狀態(tài)。

一般說對線性規(guī)劃問題的求解是確定資源的最優(yōu)分配方案，而對于對偶問題

的求解則是確定對資源的恰當(dāng)估價，這種估價直接涉及到資源的最有效利用。

授課題目：

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

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

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

1.知識目標(biāo)：理解線性規(guī)劃單純形法求解的實質(zhì)；

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

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

教學(xué)重點:

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

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

教學(xué)難點:

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

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

教學(xué)過程：

1.舉例引入（5分鐘）

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

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

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

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

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

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

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

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

【教學(xué)流程圖】

舉例引入

”「對偶問題與原問題的結(jié)構(gòu)特點

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

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

vf初始表

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

L出基

8

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

V

課堂小結(jié)

V

布置作業(yè)

【教學(xué)方法】

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

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

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

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

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

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

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

■、教學(xué)過程：

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

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

（二）新課：

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

一、對偶單純形法的原理

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

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

均20均W0則DP的檢驗數(shù)4W0且X?0,這時

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

均20某個乙〉0則DP的某個變量為＜0,說明原問題可

行，對偶問題不可行。

某個。＜0全部為W0貝UDP的檢驗數(shù)且其？0,說明原

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

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

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

1、用實例引入：

例1-10

minIV=3%+9%

1y+%22

M+4y2之3

“y,+7y2＞3

、必，＞2NO