运筹学教案(胡运权版)

11138138页脚内容授课题目：绪论教学目的与要求：知识目标：掌握运筹学的概念和作用及其学习方法能力目标：掌握运筹学的数学模型素质目标：培养学生良好的职业道德、树立爱岗精神教学重点：运筹学的数学模型教学难点：运筹学的数学模型教学过程：举例引入（5）新课 （60分钟）举例引入，绪论（30）运筹学与管理学（303.课堂练习（20）课堂小结（5）布置作业（2）【教学流程图】举例引入，绪论运筹学运筹学与数学模型的基本概念管理学课堂练习课堂小结布置作业【教学方法】激发了学生的团队意识，达到理想的教学效果。【教学内容】（一）（5）（1）齐王赛马的故事（2）两个囚犯的故事（二）新课：绪论一、运筹学的基本概念（用实例引入）例1-1战国初期，齐国的国王要求田忌和他赛马，规定各人从自己试问：如果双方都不对自己的策略保密，当齐王先行动时，哪一方会赢？赢多少？反之呢？例1-2有甲乙两个囚犯正被隔离审讯，若两人都坦白，则每人判入8110乙囚犯抵赖 坦白甲囚犯 抵赖-1，-1 坦白0，-10 定义：运筹学Research）二、学习运筹学的方法1、读懂教材上的文字；2、多练习做题，多动脑筋思考；3、作业8次；4、考试；5、EXCEL操作与手动操作结合。（20三、课堂小结（5）授课题目：

第一章线性规划及单纯形法第一节：线性规划问题及数学模型。教学目的与要求：知识目标：掌握线性规划的基本概念和两种基本建模方法。P431.2素质目标：培养学生良好的职业道德、树立爱岗精神教学重点：1、线性规划的基本概念和两种基本建模方法；2、线性规划建模的标准形式及将普通模型化为标准模型的方法。教学难点：1、线性规划的两种基本建模方法；2、将线性规划模型的普通形式化为标准形式。教学过程：举例引入（5）新课 （60分钟）运筹学与线性规划的基本概念（20）结合例题讲解线性规划标准型的转化方法（203.课堂练习（20）课堂小结（5）布置作业《线性规划及单纯形法》（2课时）【教学流程图】运筹学运筹学与线性规划的基本概念线性规划（结合例题讲解） 线性规划的标准型目标函数结合例题讲解线性规划标准型的转化方法 约束条件的右端常数约束条件为不等式课堂练习课堂小结布置作业【教学方法】激发了学生的团队意识，达到理想的教学效果。【教学内容】第一章 线性规划及单纯形法第一节 线性规划问题及其数学模型（用实例引入）例1-3美佳公司计划制造Ⅰ、Ⅱ两种产品，现已知各制造一件时分AB应制造两种家电各多少件时才能使获取的利润最大？11每天可用能力（小时）设备A（台时）0515设备B（台时）6224调试（小时）115利润（元）21maxZ2xx15x1521

224xx51 2x,x01 21-4ABC1718、152327工地ABC水泥厂甲11．52乙242工地工地ABC供应量/百袋水泥厂甲xx12x231113乙xxx2721 22 23需求量/百袋17181550maxZx11

1.5x12

2x13

2x21

4x22

2x23s.t.

x x11 12x x21 x x11 21x x12 x x13 23

x13x23171815

2327x 0(ijij一、线性规划的基本概念如果规划问题的数学模型中，决策变量的取值是连续的整数、小策变量的线性等式或不等式，则称这种规划问题为线性规划。二、将线性规划的普通型化为标准型1、对于minZ=CX,可转化为min(-Z)=-CX；2、当约束条件中出现axi11

a xi2

a xin n

bi个“松弛变量”x 0 ，使不等式变为等式；当约束条件i1中出现axi11

a xi2

a xin n

bi变量”xi10。3、当某个决策变量xj0或符号不限时，则增加两个决策变量x' x''，令xj j

x'j

x''；j4、当约束条件中有常数项b0（-。i1-54minZ3x1

2x2

4x3s.t.2x1

3x2

4x3

300x5x1 2

6x3

400xx x1 2 3

200x,x1 2解：

0,x不限3min(Z)3x1

2x2

4(x'3

x3

0x4

0x5

0x6s.t.2x1

3xxx2xx

4('3

x'')x3

300x5x1 2

6('3

x'')x3

400xx1 2

x3

x''x3

200x,x,x',x'',x,x,x 01 2 3 3 4 5 6学生练习：P421.2。（20三、课堂小结（5）授课题目：第二节图解法第三节 单纯形法原理教学目的与要求：知识目标：用图解法理解线性规划的概念及单纯形法中的几个概念；能力目标：掌握用图解法和单纯形法求解线性规划的原理；素质目标：培养学生良好的职业道德、树立爱岗精神。教学重点：1、用图解法求解线性规划的计算步骤；2、用单纯形法求解线性规划的计算步骤。教学难点：用单纯形法求解线性规划的计算原理；教学过程：举例引入（5）举例讲解新课 （80分钟）图解法（40）单纯形法原理（403.课堂练习（穿插在例题讲解过程中）课堂小结（5）P431.41一。《线性规划的求解》（2课时）【教学流程图】以学生自学引入图解法线性规划求解方法介绍 单纯形EXCEL规划求解法坐标系图解法的操作步骤 求出可行域平移目标函数直线单纯形法的原理课堂小结布置作业

化为标准型迭代法激发了学生的团队意识，达到理想的教学效果。【教学内容】（一）（5）复习中学数学中的图解法。导入提问：线性规划图解法中有哪些基本概念？（二）新课：第二节图解法一、图解法的步骤（以学生自学引入）学生自学P16-17，教师检查看不懂文字的学生，并做好记录。P441.41下逐步提出问题。教师演示并总结如下：图解法适用于两个决策变量的线性规划非标准型。步骤如下；1、用决策变量建立直角坐标系；2、对于每一个约束条件，先取等式画出直线，然后取一已知点（一般取原点满足约束条件的不等号及该已知点的位置来判断它所在的半平面是否为可行域。3、令Z优解。1-5maxZ10x1

5x2s.t.3x15x1

4x 922x 82xx 02解xx25x2x 8123x4x 912x110x5x 1012可行解——满足约束条件的解，全部可行解的集合叫可行域。最优解——使目标函数达到最大值的可行解。基变量——利用矩阵的初等变换从约束条件的m×n(n>m)阶系数矩阵m×m非基变量。以一个数，再加到另外一行上去。课堂小结（5）布置作业：要求学生完成P431.3授课题目：授课题目：第四节单纯法的计算步骤教学目的与要求：知识目标：用图解法理解线性规划的概念及单纯形法中的几个概念；能力目标：掌握用单纯形法求解线性规划的计算步骤；素质目标：培养学生良好的职业道德、树立爱岗精神。教学重点：用单纯形法求解线性规划的计算步骤。教学难点：1、用单纯形法求解线性规划的计算原理；、用单纯形法求解线性规划的计算步骤。教学过程：教学过程：1.举例引入（5）2.举例讲解新课（80）单纯形法求解步骤课堂练习（穿插在例题讲解过程中）课堂小结（5）P431.41一。第四节《单纯法的计算步骤》（2课时）【教学流程图】以学生自学引入图解法线性规划求解方法介绍 单纯形EXCEL规划求解法化为标准型单纯形法的操作步骤求出初始表迭代法课堂小结布置作业【教学方法】激发了学生的团队意识，达到理想的教学效果。【教学内容】（二）（5）复习中学数学中的图解法。导入提问：线性规划图解法中有哪些基本概念？（二）新课：一、三个基本定理可行解——满足约束条件的解，全部可行解的集合叫可行域。最优解——使目标函数达到最大值的可行解。基变量——利用矩阵的初等变换从约束条件的m×n(n>m)阶系数矩阵m×m非基变量。以一个数，再加到另外一行上去。二、单纯形表迭代法教师先演示：1、化为标准型2、做出初始单纯形表，求出检验数；3、确定检验数中最大正数所在的列为主元列，选择主元列所对应的非基变量为进基变量4、按最小比值原则，用常数列各数除以主元列相对应的正商数5、对含常数列的增广矩阵用初等变换把主元变为1，主元所在的列的其余元素化为0。6、计算检验数，直到全部检验数小于等于0，迭代终止。基变量对应的常数列为最优解，代入目标函数得最优目标函数值。1-6maxZ2xx1 2s.t.5x26x1

152x2

24xx 51 2x,x 01 2解：先化为标准型：maxZ2xx1 2

0x3

0x4

0x55x x2 3

15s.t. 6x1

2x x2

24xx x 51 2 5x,x1 2

,x,x,x 03 4 5其约束条件的系数增广矩阵为05100156201024110015X(0,0,15,24,5)T，以此列出单纯形表如下。X(7///2,0,0,0)T，代入目标函数得：Z=2*7/2+1*3/2+15/2*0+0*0=17/2。目标函数 Cj决策变量基变量

2 1 0 0 0 常数x↓x↓x x x1 2 3 4 5初 x 03

0 5 1 0 0 15始 ←x40 1 1 0 0 1 50000 1 1 0 0 1 50000021000min(,24//1)24/6400510015211/301/604

0 [6] 2 0 1 0245计 Zj算 j第一 x3次迭 x1代 ←x5Zjj

0 0 [2/3] 0 -1/6 1 12 2/3 0 1/3 00 1/3 0 -1/3 01/32/3 21/32/3 2/300015/4-15/215/221001/4-1/27/2第二 x3次迭 x

min( 5

, ) 3/2110101010-1/43/23/22101/41/2000-1/4-1/22Zjj课堂小结（5）布置作业：要求学生完成P431.41授课题目：授课题目：第五节单纯形法的进一步讨论教学目的与要求：M1.15素质目标：培养学生良好的职业道德、树立爱岗精神。教学重点：1、求解线性规划的人工变量法中两阶段法的计算步骤。2、人工变量法与普通单纯形法的区别。教学难点：1、两阶段法的计算步骤；2、1.15教学过程：教学过程：1.举例引入（5）2.举例讲解新课（80）人工变量法（40）两阶段法（40）3.课堂练习（穿插在例题讲解过程中课堂小结与单纯形法小结（5）布置作业。《单纯形法的进一步讨论》（2课时）【教学流程图】用实例引入人工变量法初始单纯形表中无单位矩人工变量法的例题讲解 引入人工变量在目标函数中引入大M两阶段法用EXCEL求解中的困两阶段法的例题讲解 第一阶段的模型第二阶段的模型课堂小结布置作业【教学方法】激发了学生的团队意识，达到理想的教学效果。【教学内容】（三）（5复习单纯形法。导入提问：当初始单纯形表中不出现单位矩阵怎么办？（二）新课：第五节 单纯形法的进一步讨论（用实例引入人工变量法）1-7用单纯形法求解下列线性规划问题：maxZ2x1

3x2

5x3xx x 71 2 32x5x x1 2

10x,x,x 01 2 3解：将第二个约束条件化为等式（左边减去一个松弛变量）0，令它们的系数为任意大的负minZ2x1

3x2

5x3

Mx4

0x5

Mx6xx1 2

xx 73 42x5x1 2

x x x3 5

10x,x1 2

,x,x3

,x,x 05 6目标函数决策变量基变量

C 2 3 -5 -M 0 -M 常数jx↓x↓x x x x1234x5 61234xj初 x -M4

1 1 1 1 0 0 7始表x6

-M [2] -5 1 0 -1 1 10计 Z -3M 4M -2M-M M -Mj算 3M+23-4M2M-50 -M 0jmin(7/1,10/2)5一次x4迭代 x1

-M 0 [7/2] 1/2 1 1/2 -1/222 1 -5/2 1/2 0 -1/2 1/25Z 27M5 M1 -MM1 M1j 2 2 2 2 07M8 M6 0M1 3M1j 2 2 2 2x 3 0 1 1/7 2/7 1/7 -1/74/72x 2 1 0 6/7 5/7 -1/7 1/745/71232315/716/71/7-1/700-50/7-M-16/7-1/7-M+1/7jj1-8对LPminw15y1

24y2

5y323s.t.6y y 2235y1y13

2y y 12 30用两阶段法求解。max(w)15y1

24y2

5y3

0y4

0x5s.t.6y2

y y y 23 4 65y1y17对

2y20

y y y 13 5 7minZy y6 7s.t.

6y y y y 22 3 4 65y1y17

2y20

y y y 13 5 7目标函数C0目标函数C0j决策变量y基变量jy↓1初y-10[6]6始表←y7j一次y2迭代y7jy2y1j1-101020000-1-1常数y↓2y3y4y5y6y7-15210-1011582-1-1000011/6-1/601/6 01/3-1[5]02/31/3-1-1/3 11/3502/31/3-1-4/3 00011/6-1/601/601/30102/151/15-1/5-1/151/1/1500000-1-1在上表中的最终表中除去人工变量y,y6 7

后，回归到原来的标准型：max(w)15y1

24y2

5y3

0y4

0x5s.t.6y2

y y y 23 4 65y1y17

2y20

y y y 13 5 7然后对该最终表继续使用单纯形法计算：目标函数目标函数C-15-24-500常数j决策变量y基变量jy1y2y↓3yy45初y-24011/6-1/601/32始表←y1-1510[2/15]1/15-1/51/150-96-3-3j一次y-24-5/410-1/41/41/42迭代y-515/2011/2-3/21/23j-15/200-7/2-3/2故Y(0,1/2,0,0)T1.15题分析：令i=1,2,3x 0代表装载于第ji（件。ij1、目标函数为运费总收入：Z1000(x x11 12

x )700(x x13 21

x )600(x x23 31

x )332、约束条件：前中后舱载重限制：8x 6x11

5x31

20008x 6x12 8x 6x

5x325x

3000150013 23 33前中后舱体积限制：10x11

5x21

7x31

400010x1210x

5x225x

7x327x

5400150013 23 33三商品的数量限制：x x11 12x x21 x x31 32

x 60013x 100023x 80033舱体平衡条件：/23/12/4

0.15)0.15)

8x 6x11 8x 6x12 8x 6x13 8x 6x12 8x 6x

5x315x325x335x325x

231240.10)3

11 8x 6x

315x

0.10)313 23 33上三式中，2000/3000=2/3，1500/3000=1/2，2000/1500=4/3。课堂练习（穿插在例题讲解过程中）课堂小结与单纯形法小结（5）图1—9：强调当非基变量的检验数为零时，线性规划存在多重解。5、布置作业二：1.15授课题目：授课题目：第二节对偶问题的基本性质教学目的与要求：知识目标：掌握一般形式对偶问题的对应规律、理解并应用对偶定理能力目标：掌握线性规划的对偶问题的基本性质；素质目标：培养学生良好的职业道德、树立爱岗精神。教学重点：一般形式对偶问题的对应规律、对偶定理教学难点：对偶定理教学过程：教学过程：1.举例引入（5）2.举例讲解新课（80）对偶问题的基本概念与解的性质；一般形式的对偶问题对偶问题的基本性质课堂练习（穿插在例题讲解过程中）课堂小结（5）《线性规划的对偶理论》（2课时）【教学流程图】举例引入对偶问题与原问题的结构特点线性规划的对偶问题的基本概念 对偶问题与原问题的解与单纯形表线性规划的单纯形法求解实质学生练习（结合例题讲解进行）课堂小结布置作业【教学方法】激发了学生的团队意识，达到理想的教学效果。【教学内容】（一）（5）导入提问：线性规划的对偶问题与原问题的解是什么关系？（二）新课：第二章线性规划的对偶理论与灵敏度分析第一节线性规划的对偶问题回顾1-3：例1-3美佳公司计划制造Ⅰ、Ⅱ两种产品，现已知各制造一件时分AB应制造两种家电各多少件时才能使获取的利润最大？11每天可用能力（小时）设备A（台时）0515设备B（台时）6224调试（小时）115利润（元）21解：设x和x1 2

为两种产品的产量，得线性规划问题：Z2x x1 25x1521

24xx51 2x,x01 2现从另一角度提出问题：假定有某个公司想把美佳公司的资源收买过来，yyy分别为单位时间内设备A，B1 2 3其线性规划模型如下表：原问题原问题对偶问题目标函数最大利润为Z2xx，某公司最小出让价为：1 2其中：W15y 24y1 25y，其中：3x和x为两种产品的产量。1 2yyy分别为单位时间内设备1 2 3A，B原问题原问题对偶问题约束条件每生产1件商品在B设备每生产1件商品的出让价不小和调试工序上的时间约束6y y5x156x2x24xx5x,x01 2于利润：5y 2y232y 11 2 32y,y,y 02 31212可见：原问题（系数为m×n矩阵）原问题（系数为m×n矩阵）对偶问题（系数为n×m矩阵）maxZminW目标函数中的系数成为对偶问题约束约束条件中的右端常数成为原问题条件中的右端常数 目标函数中的系数约束条件系数矩阵为对偶问题约束条约束条件系数矩阵为原问题约束条件系数矩阵的转置。约束条件数有m个，第i第i第i变量数n个，第i第i第i

件系数矩阵的转置。变量数m个，iii约束条件数有n个，第iii目标函数C21000j目标函数C21000j决策变量原问题变量原问题松弛变量常数基变量最x3终x1x表2000-1/4-1/2jx1x2x3x4x500015/4-15/215/221001/4-1/27/21010-1/43/23/22-24-5/410-1/41/41/43-515/2011/2-3/21/2变量对偶问题剩余变量对偶问题变量y y3 4y1yy23目标函数C变量对偶问题剩余变量对偶问题变量y y3 4y1yy23目标函数C-15-24-500j决策变量常数y基变量jy1yy↓3yy245一次y迭代yj-15/200-7/2-3/2Y(0,1/4,1/2,0,0)T。对偶问题的基本性质1、若线性规划原问题（LP）有最优解，其对偶问题（DP）也有最优解；2、LP的检验数的相反数对应于其DP的一组基本解，其中第j个决策变x的检验数的相反数对应于DP第ixj

i松弛变量xsi

的检验数的相反数对应于其DPiyi

的解。反之DPLP1-9maxZ6x1

2x x2 32x x1

2x 23x4x 31 3x 013解加入松弛变量x4

x后，单纯形表迭代为：51040146-2100j01-5-30x1040141x016-126j00-11-2-2y3y4y5y1y2xxxxxbxxxxxb1 2 3 4 5x[2]-121024x5jx11-1/211/201x0[1/2]3-1/213521 2

yy3 4

y，由上性质，有5Y(y,y1 2

,y,y,y3 4

)(4

,5

,1

,2

,3

)为对偶问题的基本解。二、课堂练习（穿插在例题讲解过程中）三、课堂小结（5分钟）授课题目：授课题目：第二章：线性规划的对偶理论与灵敏度分析第三节影子价格教学目的与要求：知识目标：了解影子价格的实质能力目标：掌握求解线性规划的对偶单纯形法的计算步骤；素质目标：培养学生良好的职业道德、树立爱岗精神。教学重点：对影子价格的理解。教学难点：对影子价格的理解教学过程：教学过程：1.举例引入（5）2.举例讲解新课（80）影子价格的概念影子价格的实质影子价格的性质与计算3.课堂练习（穿插在例题讲解过程中4.课堂小结（5分钟）《影子价格》（2课时）【教学流程图】举例引入线性规划影子价格基本概念影子价格的实质学生练习（结合例题讲解进行）课堂小结布置作业【教学方法】激发了学生的团队意识，达到理想的教学效果。【教学内容】（二）（5）导入提问：什么是影子价格？（二）新课：第二章线性规划的对偶理论与灵敏度分析第三节影子价格对偶变量 的意义——代表在资源最优利用条件下对单位第种资源的估价这种估价不是资源的市场价格而是根据资源在生中作出的贡献而作的估价，为区别起见，称为影子价格price)。mby*z*=w*=Y*b=

i1

i i （2.26）对bi求偏导数，得到：z*y*b ii

（2.27）iyi*z*bii加一个单位时，最大产值的改变量。资源的市场价格是已知数，相对比较稳定，而它的影子价格则有赖于资的影子价格也随之改变。资源的影子价格实际上又是一种机会成本.2（B）0.250.25相反当市场价格低于影子价格时，就会买入这种资源。随着资源的买进卖出，它的影子价格也将随之发生变化，一直到影子价格与市场价格保持同等水平时，才处于平衡状态。的求解则是确定对资源的恰当估价，这种估价直接涉及到资源的最有效利用。授课题目：授课题目：第二章：线性规划的对偶理论与灵敏度分析第四节对偶单纯形法教学目的与要求：知识目标：理解线性规划单纯形法求解的实质；能力目标：掌握求解线性规划的对偶单纯形法的计算步骤；素质目标：培养学生良好的职业道德、树立爱岗精神。教学重点：1、对偶单纯形法的计算步骤；2、对偶单纯形法与原问题单纯形法求解思路上的区别。教学难点：教学难点：1、对偶单纯形法的计算步骤；2、用单纯形法求解线性规划的实质。教学过程：1.举例引入（5）2.举例讲解新课（80））（20）对偶单纯形法与原问题单纯形法的求解原理（20）对偶单纯形法原理（20）求解步骤（203.课堂练习（穿插在例题讲解过程中）4.课堂小结（5分钟）《线性规划的对偶理论与对偶单纯形法》（2课时）【教学流程图】举例引入对偶问题与原问题的结构特点线性规划的对偶问题的基本概念 对偶问题与原问题的解与单纯形表线性规划的单纯形法求解实质初始对偶单纯形法计算步骤 进基出基学生练习（结合例题讲解进行）课堂小结布置作业【教学方法】激发了学生的团队意识，达到理想的教学效果。【教学内容】（三）（5）导入提问：线性规划的对偶问题与原问题的解是什么关系？（二）新课：第四节 对偶单纯形一、对偶单纯形法的原理LP与DP在求解迭代过程中有三种情形：LPLPbLP含义j均≥0均≤0则DP≤0y0，这时iiLP与DP均≥0某个＞0j则DPy＜0，说明原问题可j行，对偶问题不可行。某个某个b＜0i全部≤0j则DP的检验数≤0且y 0，说明原ii问题不可行，对偶问题可行。对于第二种情形用单纯形法求解，第三种情形用对偶单纯形法求解。二、对偶单纯形法求解过程1、用实例引入：1-10minW3y1

9y2y y 21 2y 4y 31 2y 7y 31 2y,y 01 2解引入非负松弛变量y 0，化为标准型；35maxZ3y1

9y2y y y 21 2 3y 4y y 31 2 4y 7y y 31 2 5y 015将三个约束式两边分别乘以-1，得maxZ3y1

9y2yy1 2

y 23y1y1y目标函数C-3-9目标函数C-3-9000j决策变量常数y基变量jy↓1y ↓2yyy345

4y27y20

y 34y 35初 ←y3始 y40-1-40-1-4010-30-1-7001-300000

0 [-1] -1 1 0 0 -25计 Zj算 -3 -9 0 0 0jmin(3//3-3/-1-9/-1第一y-311-10021次迭←y00[-3]-110-1400-600-6-101-1-3-33000-6-3005Zjjmin(6//2 -6/-3 -3/-1第二 y1

-3 1 0 -4/3 1/3 05/3次迭y2-9011/3-1/301/3代y0001-2115Z -3 -9 1 2 0j 0 0 -1 -2 0j最优解为：Y=(5/3,1/3,0,0,1)3、总结对偶单纯形法求解过程：j是：在保持原始可行（即常数列保持≥0）的前提下，通过迭代实现对偶可行（全部j

≤。换一个角度考虑线性规划的求解过程：能否在保持对偶可行（全部≤j0）的前提下，通过迭代实现原始可行（即常数列保持≥0）？这就是对偶单纯形法的求解思路。第一步：建立初始单纯形表，计算检验数行，当全部j

≤0（非基变量的＜0）j且检验数仍然非正，则转下一步。第二步：将常数项＜0所在的约束条件两边同乘以-1，将常数列全变成非负，再使用原始单纯形法求解。如果上述处理过程中出现原始可行基不再是单位矩阵，可适当增加人工变量构造人造基，再用大M法求解。第三步：进行基变换先确定出基变量：选取常数列中绝对值最小的负元素对应的基变量出基，相应行为主元行。然后确定入基变量：由最小比值原则，选jaja'min{iij

a' kij a'kik

所在的列为主元列。这里j

为第j'ij

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

，其对应的非基变量为换入基变量。第四步：对主元素进行换基迭代后，用矩阵的初等变换将主元素变成1，并把主元列变成单位向量，得到新的单纯形表。二、课堂练习（穿插在例题讲解过程中）三、课堂小结（5分钟）授课题目：授课题目：第二章线性规划的对偶理论与灵敏度分析第五节：灵敏度分析教学目的与要求：1.知识目标：理解求解线性规划的单纯形法中灵敏度分析的基本原理；能力目标：分析C的变化；分析bx的分析。j j j素质目标：培养学生良好的职业道德、树立爱岗精神。教学重点：1、分析C的变化；j2、分析b的变化；j3、增加一个变量x的分析。j教学难点：1、灵敏度的基本概念；2、增加一个变量x的分析。j教学过程：教学过程：1.举例引入灵敏度（5）2.举例讲解新课（80））分析C）j分析b）jx（20）j课堂练习（穿插在例题讲解过程中）课堂小结（5）《灵敏度分析》（2课时）【教学流程图】举例引入灵敏度灵敏度线性规划灵敏度的基本概念 分析灵敏度的方法线性规划模型参数分析Cj

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

的变化学生练习（结合例题讲解进行）课堂小结

增加一个变量xj

的分析11布置作业【教学方法】激发了学生的团队意识，达到理想的教学效果。【教学内容】（四）（5）导入提问：线性规划的对偶问题与原问题的解是什么关系？（二）新课：第五节 灵敏度分析由LP将LPmaxZ=CXs.t. 其约束条件的系数矩阵为A，加上人工基I（I为单位矩阵）以后，迭代过程实际上为：（A∣I）→（I∣A）3 -1 0页脚内脚内容例1-11求矩阵A=-2 1 1的逆矩阵。2-14解32-14解3-10100-2110102-14001RR,RR101110-23 2 1 2-2=

1 1 0 1 01R,R

2R

0 0 5 0 1 11 0 1 1 1 05 3 2 1= 0 1 3 2 3 00 0 1 0 1/51/5R(1)R,R1 3

(3)R3

1 0 0 1 4/5 -1/5= 0 1 0 2 12/5 -5/30 0 1 0 1/5 1/3再看美佳公司的LP约束条件系数的初始表与最终表：目标函数目标函数Cj21000决策变量常数x↓1x↓2xxx基变量345初x005100153始←x0[6]2010244表x01100155计 Z 0j0000算 21000jmin(,24//1)24/64第二 x00015/4-15/215/23次迭 x21001/4-1/27/21代x1010-1/43/23/22Z2Z2101/41/2j000-1/4-1/2j目标函数的系数 C CB N决策变量 X XB N初始表中约束条件的系数 B N b最优表约束条件的系数 B1B B1N B最优表的检验数 CB

C B1B CB

C B1NB由上表看出，目标函数中的决策变量的系数（又叫参数）变动时，只影响最优表中的检验数，因此只要对最优表继续使用单纯形表法，直至得到最优解为止。二、分析Cj

的变化5-25。将c c1

2代入原最优表中并继续迭代，得：目标函数目标函数C1.52000常数j0001[5/4]-15/215/231.51001/4-1/27/22010-1/43/23/20001/8-9/40004/51-661．510-1/50122011/5003决策变量基变量x决策变量基变量x↓1x↓2xx↓4x35第二←x次迭x1代x2j第三x4次迭x1代x200-1/100-3/2j目标函数C目标函数C200j10决策变量常数基变量x↓1x↓2xxx345第二x03次迭x1代x1.512000j11 134 4 2 2

1，代入原最优表，得001[5/4]-15/2 15/21001/4-1/27/2010-1/43/23/2解 110 和130，得：11，故212。4 4 2 2 3 3三、分析bi

的变化设初始表中的常数列为b,那么最优表中的常数列为B1bb，那么最优表中的常数列为是当初始表中的常数列有增量b时，那么最优表中的常数列有增量B1b。例5-3设美佳公司这一例中的单纯形表中的初始表中的常数列中有增量：0 8 ，设最优表中的常数列为b'，那么其增量为：15/4-15/201001/415/4-15/201001/4-1/28=20-1/43/20-2b'=用对偶单纯形法继续计算得：基变量x↓1x↓2x3x↓4x5第二x300015/4-15/235/2次迭x121001/4-1/211/2代x21010[-1/4]3/2-1/2j000-1/4-1/2第三x300510015次迭x12110015代x400-401-62j0-100-2目标函数C2目标函数C21000j决策变量常数j7。

（P66P67二、课堂练习（穿插在例题讲解过程中）三、课堂小结（5分钟）授课题目：授课题目：第三章：运输问题第一节运输问题及其数学模型教学目的与要求：知识目标：掌握运输问题的基本概念；能力目标：。素质目标：培养学生良好的职业道德、树立爱岗精神。教学重点：初始调运方案的确定。教学难点：教学难点：初始调运方案的确定。教学过程：1.举例引入运输问题（5）2.举例讲解新课（70）运输问题的基本概念；课堂练习（穿插在例题讲解过程中）课堂小结（5））《运输问题：表上作业法与规划求解法》（2课时）【教学流程图】举例引入运输问题产地运输问题的基本概念 销运价与运量学生练习（结合例题讲解进行）课堂小结布置作业：要求学生完成习题中例7的表上作业计算。【教学方法】激发了学生的团队意识，达到理想的教学效果。【教学内容】（一）（5）导入提问：线性规划在管理实践中有哪些应用？（二）新课：第三章运输问题第一节 运输问题及其数学模一、引入P82的例1二、运输问题的数学模型及其特点101；2在前mn3、对于产销平衡运输问题，所有约束条件都有是等式约束，各产地产量之和等于各销地销量之和。运输问题的解初始基可行解的确定应本着下列原则皆应满足模型中的所有约束；基变量对应的约束方程组的系数列向量线性无关基变量的个数（非零变量的个数。中一直保持为（m+n-1）个。二、学生练习（穿插在例题讲解中）三、布置作业：对本章例题7进行具体推导授课题目：授课题目：第三章：运输问题第二节用表上作业法求解运输问题教学目的与要求：知识目标：掌握运输问题的表上作业法；验法中的闭回路法和位势法的计算步骤。素质目标：培养学生良好的职业道德、树立爱岗精神。教学重点：1、运输问题的建模和表上作业求解法；2、求检验数的两种方法；3EXCEL教学难点：教学难点：1和位势法（求检验数的两种方法；2、求解运输问题的EXCEL规划求解法。教学过程：1.举例引入运输问题的求解（5）2.举例讲解新课（70）求解运输问题的表上作业法；课堂小结（5））《运输问题：表上作业法与规划求解法》（2课时）【教学流程图】举例引入运输问题的解用最小元素法求初始方求解运输问题的表上作业法 闭回路法位势法学生练习（结合例题讲解进行）课堂小结布置作业：要求学生完成习题中例7的表上作业计算。【教学方法】激发了学生的团队意识，达到理想的教学效果。【教学内容】（二）（5）导入提问：线性规划在管理实践中有哪些应用？（二）新课：第三章运输问题第二节 用表上作业法求解运输问一、一般单纯形法销地产地B1BBB23销地产地B1BBB234产量412411A1x11x12x13x141621039A2x21xxx1022 23 24885116A3xxxx2231 32 33 34销量8141214解：先写出LP数学模型如下：minZ4x11

12x12

4x13

11x14

2x21

10x22

3x23

9x24

8x31

5x32

11x33

6x34x x11 12x x21 22x x31 32

x x13 14x x23 x x33 34

161022s.t. x11

x x 821 31x x12 x x13

x 1432x 1233x x14 24

x 1434x 0(ijij(目标函数和约束条件模型见教材P83)11x x1112

x x13

x x x x21 22 23

x x x x31 32 33 341 1 1

1 1 1

1 1 1 11 1 11 1 11 1 11 1 1m+n=3+4=7m*n=3*4=12m+n-1=3+4-1=6二、表上作业法1、求初始可行解——最小元素法先在表中找出一个运价最小的数（最小元素，给予尽可能满足，然后在余下的格子中，继续按此法安排调运。注意每次安排时，如果销地BjAi

已分配完产量，就划去该行（划去是打“×”之意；（一列（0，再按最小元素法填写其他m+n-12、调运方案的检验方法（怎样求空格检验数？）①空格闭回路法xlk

处为空格以外，xlk

所在的空格开始，沿直线前进，碰到实格可拐弯也可不拐，但碰到空格应不改变方向，如此曲折前进，一直返回到起始空格。xlk

所在空格的单位运费加上正号，沿它的空格闭回路按顺时针方向再在第二个、第三个等有数格的单位运费前依次加上负号，正号，…，如此正负交错，xlk

所在空格的检验数 。lk②位势法uiv称为位势m+n-1j

v（u和j ic uvij i j

（1）由于u和vi j

共有m+n个，因此上式组成的m+n-1个方程中多一个未知数，可任设一个未知量为一任意常（一般设u 0求出全部u和v的值再把这些u和1 i j iv的值代入空格检验数的表达式：j3、换基

cij

(ui

v) （2）j对各空格检验数按max(ij ij

0)lk

xlk

xlk

的空格闭回xlk

为0号，按顺时针或反时针方向把其他角点依次标为1号，2号，…，如此min（各奇数转角点的调运量运量，奇点处减调运量”的方法，重新安排空格闭回路上转角点的调运量。4、再求新调运方案的检验数，再换基求更新的调运方案…，如此迭代，直至空格检验数不出现负值为止。5、当某空格检验数ij

0时，同样可以选取它所在的空格进基，运用调整量调节器整后的方案仍为最优，不过目标函数值不会有所改善，称之为多解。例3-2对例3-1用表上作业法求解。解先用最小元素法求初始调运方案如下表1，用空格闭回路法或位势法求得各空格检验数为：11

1，12

2，22

1，24

1，31

10，33

12，由于存在负检验数，2。由于所有非基变量（空格）这个调运方案为最优解。和检验数为： 11 12

2，22

2，23

1，31

9，33

123.83-32，332006表1 初始调运方案销地销地产地B1BBB234产量412411A1616××1021039A28×2×108 5 11 6A3×2214×8销量81412142最优调运方案销地销地产地B1BBB234产量412411A1616××1221039A28×210×85116A3×2214×8销量销量8141214二、学生练习（穿插在例题讲解中）三、布置作业：用表上作业法进行计算求解。授课题目：授课题目：第三章运输问题第三节：运输问题进一步讨论。教学目的与要求：知识目标：掌握运输问题的基本概念；验法中的闭回路法和位势法的计算步骤。素质目标：培养学生良好的职业道德、树立爱岗精神。教学重点：教学重点：1、运输问题的建模和表上作业求解法；2、求检验数的两种方法；3EXCEL教学难点：1和位势法（求检验数的两种方法；2、求解运输问题的EXCEL规划求解法。教学过程：1.举例引入产销不平衡的运输问题（5）2.举例讲解新课（80））））（203.课堂练习（穿插在例题讲解过程中）4.课堂小结（5分钟）《运输问题进一步讨论》（2课时）【教学流程图】举例引入产销不平衡的运输问题产大于产销运输问题的基本概念 销大于产基变量的个数增加一个产求解不平衡的运输问题的表上作业法 增加一个销最后几个单元格的数据填充学生练习（结合例题讲解进行）课堂小结布置作业：要求学生完成习题中例7的表上作业计算。【教学方法】激发了学生的团队意识，达到理想的教学效果。【教学内容】（一）（5）导入提问：在运输问题中当产大于销或者销大于产怎么办？（二）新课：一、产销不平衡的运输问题1、总产量大于总销量，需增加一个虚拟的销地（收点0，用表上作业法求解。销地产地产量销地产地产量A17A25A37BBBB123421134103597812销量销量23461915解增加一个销地B0

，令它的单位运费为0。在用最小元素法寻找初始调运方案时，每次不要考虑新增这一列的运价，否则会使初始方案距离最优方案更远，增加以后调整的工作量。销地销地产地B1BBBB2340产量A12113402××327A2103590×3××25A378120××43×719销量2346419由于所有的检验数大于等于0，此方案最优，但其中130的最优调拨方案，但总运费不会下降。2、总产量小于总销量，需增加一个虚拟的产地（发点0，再用表上作业法求解。二、产量有上下限的产销不平衡运输问题71解 方法：这是一个产地A和A1 3

A的37（20-6-7=725，大于总需求20，故增加一个虚销地B4

。当某地产量有最高产量和最低产量时，可以把它的产量分为基本产量和多余产量两部分，前者应发往实在的需用地，而不能发B4

，从而将这部分产量运往虚销点的单位运价取为充分大的M，另一部分多余产量可以运往虚销点，但实际上没有运输，故取相应的单位运价为0。现将初始方案表列于下表2：销地产地产量A销地产地产量A16a111A2a 72BBB123243156AA3324a 43销量104620表2 初始调运方案表销地销地产地B1BBB23产量41243M3×3×6A12430××325A2156M7×××7A3324M×4×04A33240×××33销量102546525用位势法求得各空格检验数为： 2M，12

M,21

0,22

2M,32

4M,33

4,34

1M, 1M，41

1M,51

52

M, 153再迭代得： 12

M,21

0,22

3,32

5,33

4,34

1M, 41

M1,51

52

153表2 最优调运方案表销地销地产地B1BBB产量2341243M3×3×6A12430××325A2156M7×××7A3324M×40×4A33240×××332525销量1046525经计算，全部检验数为大于等于0。故为最优调运方案。教材上例8再加上调度所需要的船只数。（数）内共需多少条船？只数与该港口为终点时到达的船只数之差的相反数。第三步：设多余船只数为产量，缺少的船只数为销量（需求量口为产地，调入港口为销地，作运输问题求解的作业表如下：表1 初始方案表至（销地）至（销地）从（产地）ABE产量（多余船只）C2351 102D141317××22F283××11销量（缺少船只）11355 7。以 2所在格为进基变量换基，得一21 22 31 32 22最优解：x x x x x 1CA CE DB DE FE表2 最优表Ⅰ至（销地）至（销地）从（产地）ABE产量（多余船只）C2351 ×12D141317×112F283××11销量（缺少船只）11355以210所在格为进基变量换基，得另一最优解：x 2,x x x x 1CE DA DB DB FE表3 最优表Ⅱ至（销地）至（销地）从（产地）ABE产量（多余船只）C2350 ×22D14131711×2F283××11销量（缺少船只）11355二、学生练习（结合例题进行）三、布置作业授课题目：授课题目：第四章目标规划第一节目标规划问题及其数学模型第二节目标规划的图解法教学目的与要求：掌握目标规划的规划求解法。重点要求是目标规划的三种求解方法的比较。能力目标：能够运用目标规划的求解原理进行表上操作与计算机操作。1.掌握目标规划的图解法与规划求解法。掌握目标规划的三种求解方法的区别。目标偏差变量的概念、教学难点：目标规划的图解法。教学过程：（分钟）新课 （60分钟）目标规划的定义与分类（30）目标规划的图解法与规划求解法（303.课堂练习（20）课堂小结（5）布置作业《目标规划》（2课时）【教学流程图】复习旧课定义目标规划概述 特点分类回顾目标规划的图解法例题讲解学生操作回顾目标规划的规划求解法 例题操作学生操作具体实例课堂练习课堂小结布置作业【教学方法】【教学内容】（5）（1）线性规划的求解方法有哪些？各有什么区别？（学生边回答，老师边板书）区别：适用环境不同目的不同老师归纳。导入提问：什么叫目标规划？（二）新课：一、举例引入：11300020000360002213157衫售价20元，成本14元。求使利润最大时男女衬衫的生产量x和x。1 2解：LP模型为：maxZ8x1

6x22x x1 2

20000s.t. 2x1

3x2

36000x x1 2

13000x,x 01 2用单纯形求解，得x1

7000件，x2

6000件。总销售额=15x1

20x2

225000元。2250000预定目标的正负偏差量之和为最小。求该目标规划的数学模型。解：数学模型为：minfdd2xx1 2

20000s.t.

2x3x1

36000xx1 2

1300015x1

20x2

dd250000x,x1 2

,d,d0二、目标规划的基本概念目标规划是对每个优化目标预先给定一个理想的期望值，再把实（d和d分别叫正负偏差变量，将对目标函数求极值问题转化为对目标偏差变量求极值的三、目标规划的数学模型（以上例为依据）1、引入偏差变量与目标约束设d0d0为超过①当销售额小于250000元时，有d ＞0且d0，则15x1

20x2

d250000 成立；②当销售额大于250000元时，有d ＞0且d0，则15x1

20x2

d250000成立；250000dd0，则15x1

20x2

250000成立。这三种情况可全并为一个等式：15x1

20x2

dd250000，把为目标约束，其中d和d至少有一个为0。2、引入达成函数g(xddEE为目标的预定值，那么达成函数有五种形式：①infd，不关心超过量大小（越大越好d0，这时目标约束为g(xdEg(xE，希望g(x)最好超过E；②infd，不关心不足量大小（越大越好这时最优值为d0，目标约束为g(xdEE，希望g(x)不超过E；minfdd，希望不足量与超过量之和越小越好，最优值为dd0，即g(x)E，意味着g(x)尽量接近E；minfddd0d，f超过最优值（为，意味着要求g(x与E无关，超过值越大越好，相当于求maxg(x)。minfdddd0fdd趋于最优值（为，意味着要求g(x与E相当于求ming(x)。3、下面以上述例题为例，说明达成函数与目标约束怎样配合？①infd即d015x1

20x2

dd250000，叫作销售额不少250000（250000②infd即d015x1

20x2

dd250000，叫作销售额不超250000（250000③infdd15x1

20x2

dd250000，叫作销售额尽可能接250000三、目标规划的图解法（适用于两个决策变量）例3某工厂生产两种产品，受到原材料和设备工时的限制。在单件利润等有关数据已知的条件下，要求制订一个获利最大的生产计划。具体数据见下表：产品ⅠⅡ限量原材料（kg/件）2111设备工时（h）1210利润（万/件）910解：该例用单纯形法求解，为：maxz8x1

10x22xx1 2

11x2x1

10x 012解之得

4,x1

3,Z62(万元）4现对上例考虑：（即xx1 2

0，也就是x1

x的值不超过；2（10，也不小于1，也就是尽量接近于10；③总利润不小于56万元；④引入优先因子Pk1

P 。k1解：由上原则，上述三种目标对应的目标函数和目标约束分别为：①xx dd0,Zd1 2 1 1 1②x2x dd10,Zdd1 2 2 2 2 2③8x10x dd56,minZd1 2 3 3 3总结以上分析，由例4的要求，该线性规划的数学模型为：minZPdP(dd)pd1 1 2 2 2 3 32xx1 2

11xx dd01 2 1 1x2x dd101 2 2 28x10x dd561x,x

2 3 3,d,d01 2 i i1、以x和x1 2

为轴作出直角坐标系。2、对于绝对约束的作直线方法与一般线性规划的图解法相同；3、对于目标约束条件，先令dd0侧标上d和d的方向，表明目标约束可以沿d和d所示的方向平移。例如，对于直线xx1 2

0，它右下半平面为xx1 2

0（即d>0（因为当x不变而x2

增加时有xx1 2

0，所以该直线的右下方为d增加的方向，那么它的左上方为d增加的方向。4、最后根据目标函数中的优先因子求解。本例子先考虑d，可满足d0这时x

在⊿OBC边界和其中取值;再实现目标函数中1 1 1 2的dddd0时，线段可在ED2 2 2 2现mind，从图中判断可以使d0此时x

的取值范围缩小在线段GD上。3 3 1 2这就是该目标规划的解，可求得G和D（2，4）和10/，GD的凸线性集合就是该目标规划的解。xx2xx 0dB112d2xx11211FEd3CGx2x1210d2Ox10x1356x1三、课堂小结（5四、布置作业：授课题目：授课题目：第四章目标规划第三节目标规划的单纯形法教学目的与要求：知识目标：了解目标规划的单纯形法的定义与操作步骤。纯形求解步骤中检验数的计算。素质目标：培养学生良好的职业道德、树立爱岗精神教学重点：1.掌握目标规划的单纯形法。2.掌握目标规划的目标规划的单纯形法与普通单纯形求解方法的区别。教学难点：目标规划的单纯形法的定义与操作步骤。掌握目标规划法单纯法求解步骤与一般线性规划单纯形法求解步骤的区别。教学过程：（分钟）新课 （60分钟）目标规划单纯形法的定义与分类（30(4)目标规划单纯形法操作步骤（30）课堂练习（20）课堂小结（5）布置作业《目标规划：单纯形法求解》（2课时）【教学流程图】复习旧课目标规划单纯形法概述目标函数的系目标规划单纯形法求解步骤 检验数为多项检验数为负值的判定具体实例课堂练习课堂小结布置作业【教学方法】【教学内容】（一）（5）（1）目标规划单纯形法的定义（学生边回答，老师边板书）导入提问：目标规划单纯形法与一般单纯形法的操作区别是什么？（二）引入5对4解：列出单纯表如下：C 0 0 0 0j

P P P P 0b1 2 2 3bx C x↓B B 1

x↓x2 3

d d d d1 1 2 2

d d↓3 3x 23d 11d P 1

1 1-1[2]

111 -1 01 -1 102 2d P 8 10 1 -1 563 3 P 1j 1P -1 -2 22P 3

-10 1x 3/23d 3/21x2 1/2 1

11

-1/21/21/2

1/2 6-1/2 55-1/26d P3 3 [3]

-5 5 1 -1 6 P 1j 1P 1 12P -3 5 -5 1312-2-1/21/231-13-3-1/2[1/2]232-26-621-1/31/31/3-1/3jPP11P1x3x3d1x14/3-4/3-1/61/642x11-5/35/31/3-1/321jP1P211P31x1-11-113d-11xx112/3-2/31/3-1/31231、因目标函数为最小化，故以检验数j

0作为最优准则；2、因非基变量检验数含有不同等级的优先级因子，需逐级考虑。 C Zj j

a Pkj k

,j1,2,…，n为列序号，k1,2,,K为行序号，因PP1

PK

，从每个检验数的整体看，检验数的正负首先取决于P1的系数a1j

的正负，若a1j

=0，检验数的正负取决于a2j

的正负，下面依三、目标规划单纯形求解的步骤：1、化为标准型，建立初始单纯形表，表中将检验行按优先级因子个数分别列成K行，置k1；2、检查该行中是否存在负数，且对应的前k10。若有，取其中最小（最负）35就选具有较高的优先级别的变量为换出变量；4、按单纯形法进行迭代运算，建立新的运算表，再返回第2步；5、当kK时表中的解为满意解否则置kk125下面以上例题为例，分析单纯形求解的步骤。1、化为标准型：取第一个约束中加上松弛变量x

x、d、dd为初始基变量，列出初始单纯形表；

3 3 1 2 32Pk

取k=1，P1

行，因该行无负检验数，执行步骤3；5，因为（K（），取kk122；42P2

行有-1，-2，取-2x2

进基，执行步骤3，计算最小比值/2,56/10)10/2其对应的变量d24；542，止。二.课堂练习（20三.课堂小结（5）四.布置作业授课题目：授课题目：第四章目标规划第四节目标规划的灵敏度分析教学目的与要求：教学目的与要求：知识目标：了解目标规划的灵敏度分析。能力目标：掌握目标规划的灵敏度分析。素质目标：培养学生良好的职业道德、树立爱岗精神教学重点：目标规划的灵敏度分析教学难点：目标规划的灵敏度分析教学过程：（5分钟）2.新课（60分钟）目标规划的灵敏度分析课堂练习（20）课堂小结（5）布置作业《目标规划：目标规划的灵敏度分析》（2课时）【教学流程图】复习旧课目标规划灵敏度分析概述目标规划灵敏度分析步骤具体实例课堂练习课堂小结布置作业【教学方法】【教学内容】（一）（5）（1）目标规划灵敏度分析的定义（学生边回答，老师边板书）导入提问：目标规划灵敏度分析与对偶问题灵敏度分析的操作区别是什么？（二）新课：目标规划的灵敏度分析例5已知目标规划问 minPd,Pd,P(5d3d),Pd1 1 2 2 3 3 4 4 1x2x dd 61 2 1 1x2x

d

d 91 2 2 2x2x

dd 41 2 3 3 x d

d2x,x

2 4 4,d,,d0 i1 2 i i目标函数分别变为： minPd,Pd,Pd,P(5d3d)1 1 2 2 3 1 4 3 4 minPd,Pd,PdWd),Pd

0)1 1 2 2 3 1 3 2 4 4 1 1 2解目标函数的变化仅影响原解的最优性，即各变量的检验数。因此，应当先考察检验数的变化，然后再作适当的处理。cjcj00p1p40p5p2303p30CXbxxB B 1 2d1d1d2d2d3d3d4d40p4x1d13p d3 40 x213/233/45/4P110000000100-1001010001/21-1/41/40-1/2-11/4-1/401/201/4-1/40-1/20-1/41/400010000-100c zj jP00000100002P00003/4-317/43/4033P40010-110000当目标函数变4—7表4—7ccj00p1p30p25p403p40CXbxxB B 1 2d1d1d2d2d3d3d4d400x113/210001/2-1/21/2-1/2p3d13p04d4x23/45/400010000-1/41/41/4-1/41/4-1/4-1/41/4c zj jP1P2P3P4cjCcjC XB B00x1d23p04d4x2c zj jP1P2P3P4003 00-111-100001-100001000000000000100000010-11000004—80003/4-3/417/43/4030b x0xp1dp3d0dp2d5p4d0d3p4d0d12112233445101/2-1/2001/2-1/200300-111-100003/200-1/41/4001/4-1/41-11/2011/4-1/400-1/41/400001000000000000100000001000000003/4-3/40017/43/403cj00p1p30cj00p1p30p2WP130WP230CXbxBB1x2d1d1d2d2d3d3d4d40x1P4d1WP23d04x213/233/45/4100000010-10001001/21-1/41/4-1/2-11/4-1/41/201/4-1/4-1/20-1/41/4001000-10c zj jP1P2P3P4001000000000000100000000W/42-W/42W-W/41 2W/420W20010-110000二.课堂练习（20三.课堂小结（5）四.布置作业授课题目：授课题目：第五章整数规划第一节：整数规划的数学模型及解的特点第三节：分支定界法教学目的与要求：教学目的与要求：能力目标：掌握分支定界法的求解步骤；素质目标：培养学生良好的职业道德、树立爱岗精神教学重点：1、分支定界法的基本概念；2、分支定界法的操作原理与步骤。教学难点：1、分支与定界的方法；2、图解法在分支定界法中的应用。教学过程：1.举例引入（5）2.新课讲解（80分钟）分支与定界原则与方法（20）分支定界法操作步骤（40）学生操作（20）3.课堂小结（5）5.布置作业《整数规划：定义、类型、求解综述和分支定界法》（2课时）【教学流程图】举例引入整数规划整数规划的定义与分整数规划的定义、分类与求解综述 整数规划的松驰问题整数规划的几种求解方法分支方法定界方法分支定界法的求解过程 解的搜索法最优解的确定课堂练习（结合例题讲解进行）课堂小结布置作业【教学方法】激发了学生的团队意识，达到理想的教学效果。【教学内容】（二）（5）整数规划的定义整数规划的分类整数规划的求解综述导入提问：怎样运用分支定界法？（二）新课：第五章 整数规划第一节整数规划的数学模型及解的特点一、整数规划的定义与分类二、整数规划的求解方法综述第三节分支定界法一、主要思路1、要求一部分或全部决策变量必须取整数值的规划问题称为整数规划。不考虑整数条件，其相对应的线性规划问题叫该整数规划的松弛问题。求解整数规划时，首先求解与它相对应的松弛问题，如果它的松弛问题的最优解满足整数要求，则得该整数规划的最优解，否则通过增加新的函数约束来缩小其松弛问题的可行域，将原整数规划模型分为两个子规划模型，并除去可行域中的无整数解的部分，达到分枝的目的。然后对每一个子规划模型的松弛问题再求解，以此类推，并不断定界，最后求得原问题的最优解。2、分枝的方法：选择与整数值相差最大的非整数变量先分枝；人为地按变量的相对重要性进行选择。3、定界与剪枝1）定界方法：①求解整数规划时，如果解它的松弛问题得到的不是一个整数解，则最优整数解一定不会优于所得松弛问题的目标函数值，即松弛问题的的解必是整数规划问题的目标函数值的一个界，它对于最大值问题是上界，对于最小值问题是下界。②如果在求解整数规划的松弛问题的过程中已经得到了一个整数解，则最优整数解一定不会劣于该整数解，因此该整数解可构成最优整数解的另一个界，对于最大化问题它为下界，对于最小化问题它为上界。③以上讨论可用不等式表示如下：Z---松弛问题的解；Z0

---目前已找到的整数解，Z* 最优整数解；Z---下界。则最优整数解满足：对于最大化问题：ZZi

Z*Z0

ZZ 0

Z*Zi

。显然如能找到一种方法，或降低上界或提出高下界，最后使得上界等于下界，就可以搜索得到最优整数解。2）子问题无可行解，此时无须继续向下分枝，将其剪枝；得到一个非整数解，继续向下分枝；如得到一组整数解，则不必继续向下分枝，因该点有整数解而被关闭。二、例题分析例1求解下列整数规划：maxZ40x1

90x29x7x1 2

567x20x1

70x jjx,x1

是整数2xx29x7x 5612G(4.81.8）7x20x 7012x1第一步：用图解法求出原整数规划问题的松驰问题的解。对x=4.81按1x4和x51 1划问题的松驰问题进行定界（上界与下界。两个子问题由原问题的松驰问题分别加上分支的两个约束条件组成，再用图解法求出它们的解。maxZ40x1

90x2

maxZ40x1

90x29x7x1 2

9x7x1 2

567x20x1 2

和 7x1

20x2

70x41x jj

x51x jj11xx29x7x 5612G(4.81.8）7x20x 701245x1第二步：根据对节点分支的三种情况：剪支、停止分支和继续分支，对上述两个子问题进行继续分支。又分别得到两个子问题。如此下去，是否无穷次分支？需由定界来确定。第三步：最后如果得到一个整数解，即为最优整数解；如得到几个整数解，取目标函数值最大者为最优整数解。问题B1

2

x4.819x7x1 27x20x

5670

1x 2

Z0,Z3561 2

356xj0j138页脚内容问题B1 问题B2x4.00 x 5.0011138138页脚内容maxZ40x1

90x2

x4 x51 1

maxZ40x1

90x29x7x1

56

9x7x1

567x20x1

70

7x20x1

70x41x jj

x51x jjx 2 x 32 2

Z0,Z349maxZ40x1

90x2

maxZ40x1

90x29x7x1

56

9x7x1

567x20x1

70

7x20x1

70x4,x21 1

x4,x31 1x jj

x jjmaxZ40x1

90x2

Z340,Z341x 1 x 22