《运筹学》完整教案(本科)

料必备___至迎下或

《运筹学》教案

适用专业：

适用层次：本科

教学时间：20XX年上学期

授课题目：

绪论

第一章线性规划及单纯形法

第一节：线性规划问题及数学模型。

教学目的与要求:

1.知识目标：掌握运筹学的概念和作用及其学习方法；掌握线性规划的基

本概念和两种基本建模方法。

2.能力目标：掌握线性规划建模的标准形式及将普通模型化为标准模型的

方法。要求学生完成P43习题1.2两个小题。

3.素质目标：培养学生良好的职业道德、树立爱岗精神

教学重点:

1、线性规划的基本概念和两种基本建模方法；

2、线性规划建模的标准形式及将普通模型化为标准模型的方法。

教学难点：

1、线性规划的两种基本建模方法；

2、将线性规划模型的普通形式化为标准形式。

教学过程：

1.举例引入（5分钟）

2.新课（60分钟）

（1）举例引入，绪论（20分钟）

（2）运筹学与线性规划的基本概念（20分钟）

（3）结合例题讲解线性规划标准型的转化方法

3.课堂练习（20分钟）

4.课堂小结（5分钟）

5.布置作业

学习必备一一一侬下或

《线性规划及单纯形法》（2课时）

【教学流程图】

举例引入，绪论

V「运筹学

运筹学与线性规划的基本概M线性规划

（结合例题讲解）I线性规划的标准型

目标函数

结合例题v讲解线性规划标准型的转化方法《约束条件的右端常数

约束条件为不等式

8

课堂练习

8

课堂小结

8

布置作业

【教学方法】

本课主要采用任务驱动和程序式思维相结合的教学方法，过程当中辅以案例

讲解、启发提问、自主学习和协作学习等方式。任务驱动是实现本课教学目标和

完成教学内容的主要方法，任务是师生活动内容的核心，在教学过程中，任务驱

动被多次利用。自主学习能提高学生的自主探究能力，竞赛和协作学习调动学生

的积极性，激发学生参与的热情。学生之间互帮互助，共同分享劳动果实，从而

激发了学生的团队意识，达到理想的教学效果。

【教学内容】

一、教学过程：

（一）举例引入：（5分钟）

（1）齐王赛马的故事

(2)两个囚犯的故事

导入提问：什么叫运筹学？

(二)新课：

绪论

一、运筹学的基本概念

(用实例引入)

例1-1战国初期，齐国的国王要求田忌和他赛马，规定各人从自己的

上马、中马、下马中各选一匹马来比赛，并且说好每输一匹马就得支

付一千两银子给予获胜者。当时齐王的马比田忌的马强，结果每年田

忌都要输掉三千两银子。但孙膑给田忌出主意，可使田忌反输为赢。

试问：如果双方都不对自己的策略保密，当齐王先行动时，哪一方会

赢？赢多少？反之呢？

例1-2有甲乙两个囚犯正被隔离审讯，若两人都坦白，则每人判入狱

8年；若两个人都抵赖，则每人判入狱1年；若只有一人坦白，则他

初释放，但另一罪犯被判刑10年。求双方的最优策略。

乙囚犯

抵赖坦白

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

坦白0,-10-8,-8

定义：运筹学(OperationResearch)是运用系统化的方法，通过建

成立数学模型及其测试，协助达成最佳决策的一门科学。它主要研究

经济活动和军事活动中能用数学的分析和运算来有效地配置人力、物

力、财力等筹划和管理方面的问题。

二、学习运筹学的方法

1、读懂教材上的文字；

2、多练习做题，多动脑筋思考；

3、作业8次；

4、考试；

5、EXCEL操作与手动操作结合。

第一章线性规划及单纯形法

第一节线性规划问题及其数学模型

（用实例引入）

例1-3美佳公司计划制造I、II两种产品，现已知各制造一件时分别

占用的设备A、B的台时数，及测试工序所需要的时间。问该公司应

制造两种家电各多少件时才能使获取的利润最大?

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

（小时）

设备A（台时）0515

设备B（台时）6224

调试（小时）115

利润（元）21

maZ=2%+x2

5x,<15

6国+2X2<24

x,+x2<5

,%,二220

学习必备一一一侬下或

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

为此甲、乙两个水泥厂每天各生产23百袋和27百袋水泥供应这三个

工地。其单位运价如下表，求最佳调运方案。

水泥厂、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)

线性规划的基本概念

如果规划问题的数学模型中，决策变量的取值是连续的整数、小

数、分数或实数，目标函数是决策变量的线性函数，约束条件是含决

学习必备一一一侬下或

策变量的线性等式或不等式，则称这种规划问题为线性规划。

二、将线性规划的普通型化为标准型

1、对于minZ=CX,可转化为min(-Z)—CX；

2、当约束条件中出现出玉+%%2+…+%再工瓦时,在左边加上一

个“松弛变量”职々0,使不等式变为等式；当约束条件

中出现%X]+%工2+…+4〃%〃-bi时，则在左边减去一个“松弛

变量”升+1之0。

3、当某个决策变量X/N0或符号不限时，则增加两个决策变量

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

4、当约束条件中有常数项々4)时、则在方程两边同乘以(-1)。

例1-5将下列非标准4型线性规划问题转化为标准型。

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分钟)

授课题目：

第二节图解法

第三节单纯形法原理

第四节单纯法的计算步骤

教学目的与要求：

1.知识目标：用图解法理解线性规划的概念及单纯形法中的几个概念;

2.能力目标：掌握用图解法和单纯形法求解线性规划的计算步骤；

3.素质目标：培养学生良好的职业道德、树立爱岗精神。

教学重点：

1、用图解法求解线性规划的计算步骤；

2、用单纯形法求解线性规划的计算步骤。

教学难点：

1、用单纯形法求解线性规划的计算原理;

2、用单纯形法求解线性规划的计算步骤。

教学过程：

1.举例引入（5分钟）

2.举例讲解新课（80分钟）

（1）图解法（20分钟）

（2）单纯形法原理（20分钟）

（3）单纯形法求解步骤（40分钟）

3.课堂练习（穿插在例题讲解过程中）

4.课堂小结（5分钟）

5.布置作业:要求学生完成P43习题1.4两个小题。其中第1小题为作业一。

学习必备一一一侬下或

《线性规划的求解》（2课时）

【教学流程图】

以学生自学引入

图解法

线性规划求解方法介绍单纯形法

EXCEL规划求解法

坐标系

图解法的操作步骤求出可行域

平移目标函数直线

化为标准型

单纯形法的操作步骤J求出初始表

I迭代法

课堂小结

布置作业

【教学方法】

本课主要采用任务驱动和程序式思维相结合的教学方法，过程当中辅以案例

讲解、启发提问、自主学习和协作学习等方式。任务驱动是实现本课教学目标和

完成教学内容的主要方法，任务是师生活动内容的核心，在教学过程中，任务驱

动被多次利用。自主学习能提高学生的自主探究能力，竞赛和协作学习调动学生

的积极性，激发学生参与的热情。学生之间互帮互助，共同分享劳动果实，从而

激发了学生的团队意识，达到理想的教学效果。

【教学内容】

一、教学过程：

（一）举例引入：（5分钟）

复习中学数学中的图解法。

导人提问：线性规划图解法中有哪些基本概念？

（-）新课：

第二节图解法

一、图解法的步骤

（以学生自学引入）

学生自学P16-17,教师检查看不懂文字的学生，并做好记录。

提问：以P44的1.4题第1小题为例，图解法第一步是什么？以

下逐步提出问题。

教师演示并总结如下：图解法适用于两个决策变量的线性规划非

标准型。步骤如下；

1、用决策变量建立直角坐标系；

2、对于每一个约束条件，先取等式画出直线，然后取一已知点

（一般取原点）的坐标代入该直线方程的左边，由其值是否

满足约束条件的不等号及该已知点的位置来判断它所在的

半平面是否为可行域。

3、令Z等于任一常数，画出目标函数的直线，平移该直线，

直至它与凸多边形可行域最右边的角点相切，切点坐标则为

最优解。

例1-5

maxZ=10xj+5x2

s.t.

3芭+4X2<9

<5xi+2X2<8

x,x>0

i*2

解

可行解一一满足约束条件的解，全部可行解的集合叫可行域。

最优解一一使目标函数达到最大值的可行解。

基变量一一利用矩阵的初等变换从约束条件的mXn（n〉m）阶系数矩

阵找出一个mXm阶单位子矩阵，它们对应的变量叫基变量，其余的

叫非基变量。

矩阵的初等变换一一将矩阵的一行同乘以一个数；将矩阵的一行同乘

以一个数，再加到另外一行上去。

二、单纯形表迭代法

教师先演示：

1、化为标准型

2、做出初始单纯形表，求出检验数；

3、确定检验数中最大正数所在的列为主元列，选择主元列所对

应的非基变量为进基变量

4、按最小比值原则，用常数列各数除以主元列相对应的正商

数，取其最小比值，该比值所在的行为主元行；主元列与主

元行交叉的元素为主元，主元所对应的基变量为出基变量。

5、对含常数列的增广矩阵用初等变换把主元变为1,主元所在

的列的其余元素化为0。

6、计算检验数，直到全部检验数小于等于0,迭代终止。基变

量对应的常数列为最优解，代入目标函数得最优目标函数

值。

例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

其约束条件的系数增广矩阵为「05100151

6201024

^1100151

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

得：X=(7/2,3/2,15/2,0,0,0)"代入目标函数得：

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

目标函数Cj21000常数

变量

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.布置作业：要求学生完成P43习题1.4两个小题。其中第1小题为作业一

授课题目：

第五节单纯形法的进一步讨论

教学目的与要求：

1.知识目标：理解求解线性规划的人工变量法中大M法和两阶段法;

2.能力目标：利用习题1.15巩固线性规划的建模；

3.素质目标：培养学生良好的职业道德、树立爱岗精神。

教学重点：

1、求解线性规划的人工变量法中两阶段法的计算步骤。

2、人工变量法与普通单纯形法的区别。

教学难点：

1、两阶段法的计算步骤；

2、习题1.15中的约束条件分析。

教学过程：

1.举例引入（5分钟）

2.举例讲解新课（80分钟）

（1）人工变量法（40分钟）

（2）两阶段法（40分钟）

3.课堂练习（穿插在例题讲解过程中）

4.课堂小结与单纯形法小结（5分钟）

5.布置作业。

学习必备一一一侬下或

《单纯形法的进一步讨论》（2课时）

【教学流程图】

用实例引入人工变量法

”「初始单纯形表中无单位矩阵

人工变量法的例题讲解工引入人工变量

L在目标函数中引入大M

lf两阶段法用EXCEL求解中的困难

两阶段法的例题讲解《第一阶段的模型

第二阶段的模型

课堂小结

布置作业

【教学方法】

本课主要采用任务驱动和程序式思维相结合的教学方法，过程当中辅以案例

讲解、启发提问、自主学习和协作学习等方式。任务驱动是实现本课教学目标和

完成教学内容的主要方法，任务是师生活动内容的核心，在教学过程中，任务驱

动被多次利用。自主学习能提高学生的自主探究能力，竞赛和协作学习调动学生

的积极性，激发学生参与的热情。学生之间互帮互助，共同分享劳动果实，从而

激发了学生的团队意识，达到理想的教学效果。

【教学内容】

一、教学过程：

（二）举例引入：（5分钟）

复习单纯形法。

导入提问：当初始单纯形表中不出现单位矩阵怎么办？

（二）新课：

第五节单纯形法的进一步讨论

学习必备一一一侬下或

（用实例引入人工变量法）

例1-7用单纯形法求解下列线性规划问题：

maxZ=2%j+3x2-5x3

r2+I2+£=7

y2xl-5X2+x3>10

I%1,x2,x3>0

解：将第二个约束条件化为等式（左边减去一个松弛变量）后，

约束条件的系数矩阵不存在单位矩阵，这时可在约束条件第一、二等

式的左边分别加上一个人工变量作为初始基变量，使之出现单位矩

阵。为了使目标函数中的人工变量为0,令它们的系数为任意大的负

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

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

rX]++%3+%4=7

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

IX15X2,X3,X4,X5,X6>0

目标函数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

所以最优解为：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

学习必备一一一侬下或

使用单纯形法求解，化为标准型后，列出单纯形表并迭代如下

目标函数Cj00000-1-1常数

逆策变量

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

然后对该最终表继续使用单纯形法计算：

目标函数-15-24-500常数

变量

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中商品的数量(件)。

1、目标函数为运费总收入：

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

三商品的数量限制:

学习必备一一一侬下或

孙+为2+113-600

x21+X22+尤23-1000

%31+*32+%33—8。°

舱体平衡条件：

前舱载重/中舱载重为：-(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网3+6々3+5%333

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

3.课堂练习(穿插在例题讲解过程中)

4.课堂小结与单纯形法小结(5分钟)

图1-9：强调当非基变量的检验数为零时，线性规划存在多重解。

5、布置作业二：1.15题

授课题目：

第二章：线性规划的对偶理论与灵敏度分析

第一节线性规划的对偶问题

第四节对偶单纯形法

教学目的与要求:

1.知识目标：理解线性规划的对偶问题与原问题的基本概念及二者的解之

间的关系；理解线性规划单纯形法求解的实质；

2.能力目标：掌握求解线性规划的对偶单纯形法的计算步骤；

3.素质目标：培养学生良好的职业道德、树立爱岗精神。

教学重点:

1、对偶单纯形法的计算步骤；

2、对偶单纯形法与原问题单纯形法求解思路上的区别。

教学难点:

1、对偶单纯形法的计算步骤；

2、用单纯形法求解线性规划的实质。

教学过程：

1.举例引入（5分钟）

2.举例讲解新课（80分钟）

（1）对偶问题的基本概念与解的性质；（20分钟）

（2）对偶单纯形法与原问题单纯形法解之间的关系；（20分钟）

（3）对偶单纯形法与原问题单纯形法的求解原理（20分钟）

（4）对偶单纯形法原理（20分钟）求解步骤（20分钟）

3.课堂练习（穿插在例题讲解过程中）

4.课堂小结（5分钟）

学习必备一一一侬下或

《线性规划的对偶理论与对偶单纯形法》（2课时）

【教学流程图】

举例引入

V厂对偶问题与原问题的结构特点

线性规划的对偶问题的基本概念J对偶问题与原问题的解与单纯形表

逐性规划的单纯形法求解实质

vf初始表

对偶单纯形法计算步骤］进基

I出基

8

学生练习（结合例题讲解进行）

课堂小结

8

布置作业

【教学方法】

本课主要采用任务驱动和程序式思维相结合的教学方法，过程当中辅以案例

讲解、启发提问、自主学习和协作学习等方式。任务驱动是实现本课教学目标和

完成教学内容的主要方法，任务是师生活动内容的核心，在教学过程中，任务驱

动被多次利用。自主学习能提高学生的自主探究能力，竞赛和协作学习调动学生

的积极性，激发学生参与的热情。学生之间互帮互助，共同分享劳动果实，从而

激发了学生的团队意识，达到理想的教学效果。

【教学内容】

一、教学过程：

（一）举例引入对偶问题的基本概念：（5分钟）

导人提问：线性规划的对偶问题与原问题的解是什么关系？

（-）新课：

第二章线性规划的对偶理论与灵敏度分析

第一节线性规划的对偶问题

回顾例1-3：

例1-3美佳公司计划制造I、n两种产品，现已知各制造一件时分别

占用的设备A、B的台时数，及测试工序所需要的时间。问该公司应

制造两种家电各多少件时才能使获取的利润最大？

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

（小时）

设备A（台时）0515

设备B（台时）6224

调试（小时）115

利润（元）21

解：设项和占为两种产品的产量，得线性规划问题:

maxZ=+x2

z-5x2<15

6x.+2%,<24

X

s工%1+x2<5

i再,42（）

现从另一角度提出问题：假定有某个公司想把美佳公司的资源收买过来，

它至少应付出多大代价，才能使美佳公司愿意放弃生产活动，出让自己的资源？

设y，为，已分别为单位时间内设备A,B和调试工序的出让价格,

其线性规划模型如下表：

学习必备一一一侬下或

原问题对偶问题

目标函数最大利润为maxZ=2X|+x2,某公司最小出让价为：

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

内和超为两种产品的产量。必，为。3分别为单位时间内设备

A,B和调试工序的出让价格。

原问题对偶问题

约束条件每生产1件商品在A,B设每生产1件商品的出让价不小

备和调试工序上的时间约束6y2+%z2

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

r5x<15

2几，为，必NO

<6%]+2%«24

为：%]+x2<5

xt,x2>0

可见:

原问题（系数为mXn矩阵）对偶问题（系数为nXm矩阵）

maxZminW

目标函数中的系数成为对偶问题约束约束条件中的右端常数成为原问题中

条件中的右端常数目标函数中的系数

约束条件系数矩阵为对偶问题约束条约束条件系数矩阵为原问题约束条

件系数矩阵的转置。件系数矩阵的转置。

约束条件数有m个，变量数m个，

第i个约束条件为“W”，第i个变量为“20”

第i个约束条件为“力”第i个变量为“W0”

第i个约束条件为“=”第i个变量为自由变量

变量数n个，约束条件数有n个，

第i个变量为“20”第i个约束条件为“2”，

第i个变量为“W0”第i个约束条件为“W”

第i个变量为自由变量第i个约束条件为“=”

例1-6和例1-8分别用单纯形法和两阶段法可求得上述例题的原问题和其

对偶问题的最终单纯形表如下:

目标函数321000

^变量原问题变量原问题松弛变量常数

基变量七%4%5

最当00015/4-15/215/2

不

终21001/4-1/27/2

X2

表1010-1/43/23/2

000-1/4-1/2

变量对偶问题剩余变重对偶问题变量

%M%％%

目标函数G-15-24-500常数

变量

力M为为।%%

基变量

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

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

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

从上两表看出两个问题变量之间的对应关系，同时看出只需求解其中

一个问题，从最优解的单纯形表中同时得到另一个问题的最优解。即原问

题的最优解为：X=(7/2,3/2,0,0,0)，；其对偶问题的最优解为：

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

对偶问题的基本性质

1、若线性规划原问题(LP)有最优解，其对偶问题(DP)也有最优解;

2、LP的检验数的相反数对应于其DP的一组基本解，其中第j个决策变

量七的检验数的相反数对应于DP第i个剩余变量与的解；LP第i个

松弛变量4的检验数的相反数对应于其DP的第i个对偶变量y的解。

反之DP的检验数对应于其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，由上性质，有

y=（M，%，%，乂，K）=（一=，-4，-4，-4，-4）=（2,2,0,0,11）为对偶问题的基本解。

第四节对偶单纯形法

一、对偶单纯形法的原理

LP与DP在求解迭代过程中有三种情形:

LP的b列LP的检验数乙含义

均20均W0则DP的检验数4〈。且M20，这时

LP与DP均达到最优解。

均20某个>>0则DP的某个变量匕.<0,说明原问题可

行，对偶问题不可行。

某个4Vo全部"WO则DP的检验数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

目标函数C,-3-9000

变量常数

当

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=(5/3,1/3,0,0,1)

3、总结对偶单纯形法求解过程:

由于用单纯形法求解极大化线性规划问题时一，通过迭代直至所有检验数

乙W0,这时所得最优基也是对偶问题的可行基，因此单纯形法的求解过程

是：在保持原始可行(即常数列保持10)的前提下，通过迭代实现对偶可

行（全部乙WO）。

换一个角度考虑线性规划的求解过程：能否在保持对偶可行（全部

0）的前提下，通过迭代实现原始可行（即常数列保持10）?这就是对偶

单纯形法的求解思路。

第一步：建立初始单纯形表，计算检验数行，当全部人W0（非基变量

的4V0）时，如果常数项N0,即得最优解。如常数项至少有一元素＜0,

且检验数仍然非正，则转下一步。

第二步：将常数项＜0所在的约束条件两边同乘以T,将常数列全变

成非负，再使用原始单纯形法求解。如果上述处理过程中出现原始可行基

不再是单位矩阵，可适当增加人工变量构造人造基，再用大M法求解。

第三步：进行基变换

先确定出基变量：选取常数列中绝对值最小的负元素对应的基变量出

基，相应行为主元行。然后确定入基变量：由最小比值原则，选

min4K.W0}=区所在的列为主元列。这里当为第j列的检验数，因为人对

应的主元行中非基变量的系数。主元行与主元列相交叉处的系数元素为主

元素勾，其对应的非基变量为换入基变量。

第四步：对主元素进行换基迭代后，用矩阵的初等变换将主元素变成

1,并把主元列变成单位向量，得到新的单纯形表。

二、课堂练习（穿插在例题讲解过程中）

三、课堂小结（5分钟）

授课题目：

第二章第五节：灵敏度分析

教学目的与要求：

1.知识目标：理解求解线性规划的单纯形法中灵敏度分析的基本原理；

2.能力目标：分析J的变化；分析与的变化；增加一个变量为的分析。

3.素质目标：培养学生良好的职业道德、树立爱岗精神。

教学重点:

1、分析G的变化；

2、分析鸟.的变化；

3、增加一个变量无,的分析。

教学难点:

1、灵敏度的基本概念；

2、增加一个变量X）的分析。

教学过程：

1.举例引入灵敏度（5分钟）

2.举例讲解新课（80分钟）

（1）灵敏度的基本概念；（20分钟）

（2）分析弓的变化；（20分钟）

（3）分析3的变化；（20分钟）

（4）增加一个变量马的分析。（20分钟）

3.课堂练习（穿插在例题讲解过程中）

4.课堂小结（5分钟）

学习必备一一一侬下或

《灵敏度分析》（2课时）

【教学流程图】

举例引入灵敏度

线性规划灵敏度的基本概念S分析黄敏度的方法

I线性规划模型参数

d

「分析C,的变化

分析线性规划模型中参数的变化，分析与的变化

I增加一个变量Xj的分析

学生练习（结合例题讲解进行）

课堂小结

布置作业

【教学方法】

本课主要采用任务驱动和程序式思维相结合的教学方法，过程当中辅以案例

讲解、启发提问、自主学习和协作学习等方式。任务驱动是实现本课教学目标和

完成教学内容的主要方法，任务是师生活动内容的核心，在教学过程中，任务驱

动被多次利用。自主学习能提高学生的自主探究能力，竞赛和协作学习调动学生

的积极性，激发学生参与的热情。学生之间互帮互助，共同分享劳动果实，从而

激发了学生的团队意识，达到理想的教学效果。

【教学内容】

一、教学过程：

（二）举例引入对偶问题的基本概念：（5分钟）

导入提问：线性规划的对偶问题与原问题的解是什么关系？

（二）新课：

第五节灵敏度分析

一、灵敏度分析的基本概念与原理

由LP单纯形迭代法的基本原理:

将LP的标准型写成矩阵形式:

maxZ=CX

s.t.rAX=b

Y

JX20

其约束条件的系数矩阵为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约束条件系数的初始表与最终表:

目标函数C/21000

士策变量常数

xJ

x2!X3z占

基变量

初七00510015

始一匕0[6]20