運籌學教案課程胡運權版

授課題目：

緒論

教學目的與要求：

1.知識目標：掌握運籌學的概念和作用及其學習方法

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

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

教學重點：

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

教學難點：

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

教學過程：

1.舉例引入（5分鐘）

2.新課（60分鐘）

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

（2）運籌學與管理學（30分鐘）

3.課堂練習（20分鐘）

4.課堂小結（5分鐘）

5.布置作業(yè)

《緒論》（2課時）

【教學流程圖】

舉例引入，緒論

廣運籌學

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

課堂練習I

課堂小結

布置作業(yè)

【教學方法】

本課主要采用任務驅動和程序式思維相結合的教學方法，過程當中輔以案例講解、啟發(fā)

提問、自主學習和協(xié)作學習等方式。任務驅動是實現(xiàn)本課教學目標和完成教學內容的主要方

法，任務是師生活動內容的核心，在教學過程中，任務驅動被多次利用。自主學習能提高學

生的自主探究能力，競賽和協(xié)作學習調動學生的積極性，激發(fā)學生參與的熱情。學生之間互

幫互助，共同分享勞動果實，從而激發(fā)了學生的團隊意識，達到理想的教學效果。

【教學內容】

一、教學過程：

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

(1)齊王賽馬的故事

(2)兩個囚犯的故事

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

(二)新課：

緒論

一、運籌學的基本概念

(用實例引入)

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

馬、下馬中各選一匹馬來比賽，并且說好每輸一匹馬就得支付一千兩銀子給予

獲勝者。當時齊王的馬比田忌的馬強，結果每年田忌都要輸?shù)羧摄y子。但

孫臏給田忌出主意，可使田忌反輸為贏。

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

少？反之呢?

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

兩個人都抵賴，則每人判入獄1年；若只有一人坦白，則他初釋放，但另一罪

犯被判刑10年。求雙方的最優(yōu)策略。

乙囚犯

抵賴坦白

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

坦白0,-10-8,-8

定義：運籌學（OperationResearch）是運用系統(tǒng)化的方法，通過建成立數(shù)學

模型及其測試，協(xié)助達成最佳決策的一門科學。它主要研究經(jīng)濟活動和軍事活

動中能用數(shù)學的分析和運算來有效地配置人力、物力、財力等籌劃和管理方面

的問題。

二、學習運籌學的方法

1、讀懂教材上的文字；

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

3、作業(yè)8次；

4、考試；

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

二、學生練習（20分鐘）

三、課堂小結（5分鐘）

授課題目：

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

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

教學目的與要求：

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

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

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

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

教學重點：

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

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

教學難點：

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

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

教學過程：

1.舉例引入（5分鐘）

2.新課（60分鐘）

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

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

3.課堂練習（20分鐘）

4.課堂小結（5分鐘）

5.布置作業(yè)

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

【教學流程圖】

廠運籌學

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

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

r目標函數(shù)

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

約束條件為不等式

課堂練習

課堂小結

布置作業(yè)

【教學方法】

本課主要采用任務驅動和程序式思維相結合的教學方法，過程當中輔以案例講解、啟發(fā)

提問、自主學習和協(xié)作學習等方式。任務驅動是實現(xiàn)本課教學目標和完成教學內容的主要方

法，任務是師生活動內容的核心，在教學過程中，任務驅動被多次利用。自主學習能提高學

生的自主探究能力，競賽和協(xié)作學習調動學生的積極性，激發(fā)學生參與的熱情。學生之間互

幫互助，共同分享勞動果實，從而激發(fā)了學生的團隊意識，達到理想的教學效果。

【教學內容】

一、教學過程：

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

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

（用實例引入）

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

備A、B的臺時數(shù)，及測試工序所需要的時間。問該公司應制造兩種家電各多少

件時才能使獲取的利潤最大？

生產1件I產品生產1件I產品每天可用能力

（小時）

設備A（臺時）0515

設備B（臺時）6224

調試（小時）115

利潤（元）21

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

乙兩個水泥廠每天各生產23百袋和27百袋水泥供應這三個工地。其單位運價

如下表，求最佳調運方案。

水泥廠'\ABC

甲11.52

乙242

地

水泥廠\ABC供應量/百袋

甲23

乙27

需求量/百袋17181550

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

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

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

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

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

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

2、當約束條件中出現(xiàn)即2+%9+…加時一，在左邊加上一個''松弛

變量”亂T0,使不等式變?yōu)榈仁?；當約束條件中出現(xiàn)

勾內+卬2%2+…時，則在左邊減去一個"松弛變量"司+1NO。

3、當某個決策變量X/0或符號不限時，則增加兩個決策變量與和耳，令

Xj-Xj;

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

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

解：

學生練習：P42習題1.2o

二、學生練習（20分鐘）

三、課堂小結（5分鐘）

授課題目：

第二節(jié)圖解法

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

教學目的與要求：

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

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

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

教學重點：

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

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

教學難點：

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

教學過程：

1.舉例引入（5分鐘）

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

（1）圖解法（40分鐘）

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

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

4.課堂小結（5分鐘）

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

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

【教學流程圖】

以學生自學引入

「圖解法

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

匚EXCEL規(guī)劃求解法

［坐標系

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

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

化為標準型

單純形法的原理

迭代法

課.、結

布獸作業(yè)

【教學方法】

本課主要采用任務驅動和程序式思維相結合的教學方法，過程當中輔以案例講解、啟發(fā)

提問、自主學習和協(xié)作學習等方式。任務驅動是實現(xiàn)本課教學目標和完成教學內容的主要方

法，任務是師生活動內容的核心，在教學過程中，任務驅動被多次利用。自主學習能提高學

生的自主探究能力，競賽和協(xié)作學習調動學生的積極性，激發(fā)學生參與的熱情。學生之間互

幫互助，共同分享勞動果實，從而激發(fā)了學生的團隊意識，達到理想的教學效果。

【教學內容】

一、教學過程：

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

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

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

（二）新課：

第二節(jié)圖解法

一、圖解法的步驟

（以學生自學引入）

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

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

出問題。

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

驟如下；

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

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

原點）的坐標代入該直線方程的左邊，由其值是否滿足約束條件的不

等號及該已知點的位置來判斷它所在的半平面是否為可行域。

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

多邊形可行域最右邊的角點相切，切點坐標則為最優(yōu)解。

例1-5

解

G(l,1.5)

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

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

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

mXm階單位子矩陣，它們對應的變量叫基變量，其余的叫非基變量。

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

再加到另外一行上去。

4.課堂小結（5分鐘）

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

授課題目：

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

教學目的與要求：

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

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

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

教學重點：

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

教學難點：

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

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

教學過程：

1.舉例引入（5分鐘）

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

單純形法求解步驟

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

4.課堂小結（5分鐘）

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

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

【教學流程圖】

以學生自學引入

f圖解法

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

1-EXCEL規(guī)劃求解法

化為標準型

單純形時操作步驟求出初始表

迭代法

課蜀、結

布曾作業(yè)

【教學方法】

本課主要采用任務驅動和程序式思維相結合的教學方法，過程當中輔以案例講解、啟發(fā)

提問、自主學習和協(xié)作學習等方式。任務驅動是實現(xiàn)本課教學目標和完成教學內容的主要方

法，任務是師生活動內容的核心，在教學過程中，任務驅動被多次利用。自主學習能提高學

生的自主探究能力，競賽和協(xié)作學習調動學生的積極性，激發(fā)學生參與的熱情。學生之間互

幫互助，共同分享勞動果實，從而激發(fā)了學生的團隊意識，達到理想的教學效果。

【教學內容】

一、教學過程：

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

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

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

（二）新課：

一、三個基本定理

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

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

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

mXm階單位子矩陣，它們對應的變量叫基變量，其余的叫非基變量。

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

再加到另外一行上去。

二、單純形表迭代法

教師先演示：

1、化為標準型

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

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

變量為進基變量

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

小比值，該比值所在的行為主元行；主元列與主元行交叉的元素為主

元，主元所對應的基變量為出基變量。

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

余元素化為Oo

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

常數(shù)列為最優(yōu)解，代入目標函數(shù)得最優(yōu)目標函數(shù)值。

例1-6

解：先化為標準型：

maxZ=2X[+x2+0x3+0x4+0x5

5X2+=15

s.t.J6%]+2X2+x4=24

X1+x2+x5=5

>0

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

6201(24

L110015)

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

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

2=2*7/2+1*3/2+15/2*0+0*0=17/20

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

變量

x{\x2Ix3x4x5

基變量

初f400510015

始0[6]201(24

表0110015

00000

算21000

第一00510015

次迭211/301/604

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

22/301/30

01/30-1/30

第二00015/4-15/：15/2

次迭21001/4-1/27/2

代1010-1/43/23/2

2101/41/2

000-1/4-1/：

4.課堂小結（5分鐘）

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

授課題目：

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

教學目的與要求：

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

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

3.素質目標：培養(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課時）

【教學流程圖】

用實例引入人工變量法

r初始單純形表中無單位矩陣

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

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

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

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

L第二階段的模型

課堂小結

布置作業(yè)

【教學方法】

本課主要采用任務驅動和程序式思維相結合的教學方法，過程當中輔以案例講解、啟發(fā)

提問、自主學習和協(xié)作學習等方式。任務驅動是實現(xiàn)本課教學目標和完成教學內容的主要方

法，任務是師生活動內容的核心，在教學過程中，任務驅動被多次利用。自主學習能提高學

生的自主探究能力，競賽和協(xié)作學習調動學生的積極性，激發(fā)學生參與的熱情。學生之間互

幫互助，共同分享勞動果實，從而激發(fā)了學生的團隊意識，達到理想的教學效果。

【教學內容】

一、教學過程：

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

復習單純形法。

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

（二）新課：

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

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

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

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

的系數(shù)矩陣不存在單位矩陣，這時可在約束條件第一、二等式的左邊分別加上

一個人工變量作為初始基變量，使之出現(xiàn)單位矩陣。為了使目標函數(shù)中的人工

變量為0,令它們的系數(shù)為任意大的負值“7T,然后采用一般單純形表法求解。

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

變量

xxIx2!x4x5x6

基變量

初1111007

始表-M[2]-510-1110

計-3M4M-2M-MM-M

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

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

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

7.M.M.M.

2?！狹-5----hl-M-----1-1-1

2222

n7MnM3M

2222

3011/72/71/7-1/74/7

2106/75/7-1/71/745/7

2315/716/71/7-1/

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

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

例1-8對LP模型：

minw=15必+24乃+5y3

S.￥6y2+>322

《5M+ly2+y3>l

I2。

用兩階段法求解。

解：先分為標準型：

max(-w)=5必_24y2-5y3+0,4+0/

S.￥6%+丁3_%+”=2

65yl+2必+%-K+為=1

I必-720

對

minZ=yf>+y1

stJ6y2+%―%+”=2

15yl+ly2+y3-y5+y1=\

M-7n0

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

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

變量

X1%J%以為為為

基變量

初-10[6]1-10102

始表-15210-1011

582-1-100

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

迭代-1E5]02/31/3-1-1/31/3

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

0011/6-1/601/601/3

0102/151/15-1/5-1/15L1/15

00000-1-1

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

乂

maxQvv)=-45%-24y2-5y3+0+0%

s.t.r6y2+%_乂+乂=2

j5必+2)，2+%―%+必=1

Iy.7z0

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

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

變量

%>2%?>4>5

基變量

初-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,1/4,1/2,0,0）7

1.15題分析:

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

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

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

2、約束條件：

前中后艙載重限制：

前中后艙體積限制：

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

艙體平衡條件：

!(1-0.15)<8x+6121+5%3i2

前艙載重/中艙載重為：n<-(1+0.15)

8XI2+6X22+5X32

8x+6X+5X

后艙載重/中艙載重為：-(1-0.15)<n2333<-(1+0.15)

28X124-6^22+5X322

48X+6X+5X4

前艙載重/后艙載重為：-(1-0.10)<H2J31<-(1+0.10)

38X13+6叫3+5/33

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

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

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

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

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

授課題目：

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

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

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

教學目的與要求:

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

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

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

教學重點：

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

教學難點：

對偶定理

教學過程：

1.舉例引入（5分鐘）

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

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

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

（3）對偶問題的基本性質

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

4.課堂小結（5分鐘）

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

【教學流程圖】

舉例引入

「對偶問題與原問題的結構特點

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

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

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

課堂小結

布置作業(yè)

【教學方法】

本課主要采用任務驅動和程序式思維相結合的教學方法，過程當中輔以案例講解、啟發(fā)

提問、自主學習和協(xié)作學習等方式。任務驅動是實現(xiàn)本課教學目標和完成教學內容的主要方

法，任務是師生活動內容的核心，在教學過程中，任務驅動被多次利用。自主學習能提高學

生的自主探究能力，競賽和協(xié)作學習調動學生的積極性，激發(fā)學生參與的熱情。學生之間

互幫互助，共同分享勞動果實，從而激發(fā)了學生的團隊意識，達到理想的教學效果。

【教學內容】

一、教學過程：

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

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

（二）新課：

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

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

回顧例1-3：

例「3美佳公司計劃制造I、n兩種產品，現(xiàn)已知各制造一件時分別占用的設

備A、B的臺時數(shù)，及測試工序所需要的時間。問該公司應制造兩種家電各多少

件時才能使獲取的利潤最大？

生產1件I產品生產1件I產品每天可用能力

（小時）

設備A（臺時）0515

設備B（臺時）6224

調試（小時）115

利潤（元）21

解：設內和修為兩種產品的產量，得線性規(guī)劃問題：

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

出多大代價，才能使美佳公司愿意放棄生產活動，出讓自己的資源？

設凹，內，為分別為單位時間內設備A,B和調試工序的出讓價格，其線性規(guī)劃

模型如下表:

原問題對偶問題

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

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

司和乙為兩種產品的產量。y,%，X分別為單位時間內設備

A,B和調試工序的出讓價格。

原問題對偶問題

約束條件每生產1件商品在A,B設備每生產1件商品的出讓價不小

和調試工序上的時間約束6y2+為22

于利潤：5%+2%+為21

r5x<15

2幾，為，％一

<6%|+2X2<24

為：X]+x2<5

%）,x2>0

可見:

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

maxZminW

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

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

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

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

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

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

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

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

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

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

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

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

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

最終單純形表如下:

目標函數(shù)21000

^變量常數(shù)

原問題變量原問題松弛變量

基變量

最00015/4-15/215/2

終21001/4-1/27/2

表1010-1/43/23/2

000-1/4-1/2

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

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

變量

M?乂%

基變量

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

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

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

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

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

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

對偶問題的基本性質

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

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

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

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

的一組基本解。

例1-9

解加入松弛變量乙,血后，單純形表迭代為:

再尤3天4/b

%[2]-12102

X5104014

為6-2100

X]1-1/211/201

0[1/2]3-1/213

%01-5-30

104014

工2016-126

為00-11-2-2

設對偶變量為X和內，剩余變量為月，乂，%，由上性質，有

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

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

三、課堂小結（5分鐘）

授課題目：

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

第三節(jié)影子價格

教學目的與要求：

1.知識目標：了解影子價格的實質

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

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

教學重點：

對影子價格的理解。

教學難點：

對影子價格的理解

教學過程：

1.舉例引入（5分鐘）

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

（1）影子價格的概念

（2）影子價格的實質

（3）影子價格的性質與計算

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

4.課堂小結（5分鐘）

《影子價格》（2課時）

【教學流程圖】

舉例引入

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

影子價格的實質

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

課堂小結

布置作業(yè)

【教學方法】

本課主要采用任務驅動和程序式思維相結合的教學方法，過程當中輔以案例講解、啟發(fā)

提問、自主學習和協(xié)作學習等方式。任務驅動是實現(xiàn)本課教學目標和完成教學內容的主要方

法，任務是師生活動內容的核心，在教學過程中，任務驅動被多次利用。自主學習能提高學

生的自主探究能力，競賽和協(xié)作學習調動學生的積極性，激發(fā)學生參與的熱情。學生之間

互幫互助，共同分享勞動果實，從而激發(fā)了學生的團隊意識，達到理想的教學效果。

【教學內容】

一、教學過程：

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

導入提問：什么是影子價格？

（二）新課：

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

第三節(jié)影子價格

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

源的估價，這種估價不是資源的市場價格，而是根據(jù)資源在生產中作出的貢獻

而作的估價，為區(qū)別起見，稱為影子價格(shadowprice)o

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

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

dz**

明(2.27)

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

時，最大產值的改變量。

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

況，是未知數(shù)。由于企業(yè)生產任務、產品結構等情況發(fā)生變化，資源的影子價格也隨之改變。

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

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

場價格高于0.25時，可以賣出這種資源；

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

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

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

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

確定對資源的恰當估價，這種估價直接涉及到資源的最有效利用。

授課題目：

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

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

教學目的與要求：

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

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

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

教學重點：

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

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

教學難點:

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

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

教學過程：

1.舉例引入（5分鐘）

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

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

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

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

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

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

4.課堂小結（5分鐘）

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

【教學流程圖】

舉例引入

「對偶問題與原問題的結構特點

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

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

［初始表

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

L出基

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

課堂小結

布置作業(yè)

【教學方法】

本課主要采用任務驅動和程序式思維相結合的教學方法，過程當中輔以案例講解、啟發(fā)

提問、自主學習和協(xié)作學習等方式。任務驅動是實現(xiàn)本課教學目標和完成教學內容的主要方

法，任務是師生活動內容的核心，在教學過程中，任務驅動被多次利用。自主學習能提高學

生的自主探究能力，競賽和協(xié)作學習調動學生的積極性，激發(fā)學生參與的熱情。學生之間

互幫互助，共同分享勞動果實，從而激發(fā)了學生的團隊意識，達到理想的教學效果。

【教學內容】

一、教學過程：

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

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

（二）新課：

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

一、對偶單純形法的原理

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

LP的b歹ULP的檢驗數(shù)人含義

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

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

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

行，對偶問題不可行。

某個〃<0全部乙W0則DP的檢驗數(shù)4W0且X20,說明原

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

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

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

1、用實例引入:

例1-10

解引入非負松弛變量％5?。，化為標準型;

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

目標函數(shù)-3-9000常數(shù)

變量

M??%?4%

基變量

初0[-1]-1100-2

始0-1-4010-3

表0-1-7001-3

計00000

算-3-9000

e=minG3/—1,—9/—1)=3-3/-1-9/一1

第一-311-1002

次迭00[-3]-11(-1

代00-6-101-1

-3-3300

0-6-300

6=min^6/-3,-3/-l)=2-6/-3-3/-1

第二-310-4/31/3(5/3

次迭-9011/3-1/3(1/3

代0001-211

-3-9120

00-1-20

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

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

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

時所得最優(yōu)基也是對偶問題的可行基，因此單純形法的求解過程是：在保持原始可行

（即常數(shù)列保持》0）的前提下，通過迭代實現(xiàn)對偶可行（全部%W0）。

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

提下，通過迭代實現(xiàn)原始可行（即常數(shù)列保持20）?這就是對偶單純形法的求解思

路。

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

時，如果常數(shù)項與0,即得最優(yōu)解。如常數(shù)項至少有一元素＜0,且檢驗數(shù)仍然非正，

則轉下一步。

第二步：將常數(shù)項＜0所在的約束條件兩邊同乘以-1,將常數(shù)列全變成非負，再

使用原始單純形法求解。如果上述處理過程中出現(xiàn)原始可行基不再是單位矩陣，可適

當增加人工變量構造人造基，再用大M法求解。

第三步：進行基變換

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

為主元行。然后確定入基變量：由最小比值原則，選min{2|旬WO}=區(qū)所在的列為主

元列。這里為.為第j列的檢驗數(shù)，囪為乙.對應的主元行中非基變量的系數(shù)。主元行與

主元列相交叉處的系數(shù)元素為主元素須，其對應的非基變量為換入基變量。

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

元列變成單位向量，得到新的單純形表。

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

三、課堂小結（5分鐘）

授課題目：

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

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

教學目的與要求:

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

2.能力目標：分析弓的變化；分析%的變化；增加一個變量勺的分析。

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

教學重點:

1、分析-的變化；

2、分析3的變化；

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

教學難點:

1、靈敏度的基本概念；

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

教學過程：

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

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

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

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

（3）分析鳥的變化