基础运筹学教程配光盘课件教学ppt作者 马良 主编运筹学教学.ppt

《基础运筹学教程配光盘课件教学ppt作者 马良 主编运筹学教学.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、运筹学教学课件上海理工大学管理学院系统科学研究所目录第一章线性规划第二章整数规划第三章动态规划第四章图与网络第五章决策论第六章矩阵对策第一章线性规划数学模型图解法可行域的性质单纯形法单纯形表单纯形法的矩阵描述对偶规划运输问题数学模型线性规划模型的结构目标函数：max，minmaxz(minf)=∑cjxj约束条件：≥,=,≤∑aijxj≤(=,≥)bi(i=1,2,…n)变量符号：≥0,unr,≤0xj≥0(j=1,2,…n)线性规划的标准形式目标函数：maxmaxz=∑cjxj约束条件：=∑aijxj=bi(i=1,2,…n)变量符号：≥

2、0xj≥0(j=1,2,…n)典型问题：合理下料问题典型问题：合理下料问题运输问题典型问题：合理下料问题运输问题生产的组织与计划问题典型问题：合理下料问题运输问题生产的组织与计划问题投资证券组合问题典型问题：合理下料问题运输问题生产的组织与计划问题投资证券组合问题分派问题典型问题：合理下料问题运输问题生产的组织与计划问题投资证券组合问题分派问题生产工艺优化问题线性规划的图解x1x2目标函数等值线可行域最优解66-84maxz=x1+3x2s.t.x1+x2≤6-x1+2x2≤8x1≥0,x2≥0可行域的性质线性规划的最优解在极点上线性规划的

3、可行域是凸集极点凸集不是凸集凸集二个重要结论：满足约束条件的可行域一般都构成凸多边形。这一事实可以推广到更多变量的场合。二个重要结论：满足约束条件的可行域一般都构成凸多边形。这一事实可以推广到更多变量的场合。最优解必定能在凸多边形的某一个顶点上取得，这一事实也可以推广到更多变量的场合。解的讨论：最优解是唯一解；解的讨论：最优解是唯一解；无穷多组最优解：例：maxz=40x1+30x2s.t.4x1+3x21202x1+x250x1,x20x2504030201010203040x1可行域目标函数是同约束条件：4x1+3x2120平行

4、的直线x2504030201010203040x1可行域当z的值增加时，目标函数与约束条件：4x1+3x2120重合，Q1与Q2之间都是最优解。Q1（25，0）Q2（15，20）解的讨论：无界解：例：maxz=x1+x2s.t.-2x1+x240x1-x220x1,x20x2504030201010203040x1该可行域无界，目标函数值可增加到无穷大，称这种情况为无界解或无最优解。解的讨论：无可行解：例：maxS=2x1+3x2s.t.x1+2x28x14x23-2x1+x24x1,x20该问题可行域为空集，即无可行解，

5、也不存在最优解。解的情况：有可行解⊙有唯一最优解⊙有无穷最优解⊙无最优解无可行解单纯形法的引例例：maxz=31x1+22x2s.t.6x1+2x2≤1804x1+10x2≤4003x1+5x2≤210x1,x2≥0写成标准型为：maxz=31x1+22x26x1+2xx+x3=1804x1+10x2+x4=4003x1+5x2+x5=210xj≥0(j=1,2,…,5)maxz=31x1+22x26x1+2x2+x3=1804x1+10x2+x4=4003x1+5x2+x5=210xj≥0(j=1,2,…,5)基变量XB=(x3,x4,x

6、5)T,非基变量XN=(x1,x2)T,令所有非基变量为0，则得初始可行解为X(0)=(0,0,180,400,210)T,对应z(0)=0取目标函数最大正系数对应的非基变量为入基变量；取最小比值所对应方程的基变量为出基变量。本例中，取x1为入基变量，x3为出基变量。x1+1/3x2+1/6x3=3026/3x2-2/3x3+x4=2804x2-1/2x3+x5=120令非基变量x2=x3=0,z(1)=930,相应的基可行解为x(1)=(30,0,0,280,120)T为使目标函数中不出现基变量，消去x1，得z=31(30-1/3x2-1

7、/6x3)+22x2=930+35/3x2-31/6x3由于非基变量x2的系数为正，故将x2作为入基变量，z值仍可变大，即X(1)还不是最优解。再次迭代得，x1+5/24x3－1/12x5=205/12x3+x4－13/6x5=20x2－1/8x3+1/4x5=30同理，为使目标函数中不出现基变量，消去x2，得z=930＋35/3(30＋1/8x3－1/4x5)－31/6x3=1280－89/24x3－35/12x5（*）令非基变量x3=x5=0,得z(2)=1280,相应的基可行解为X(2)=(20,30,0,20,0)T.由于（*）式中

8、，非基变量x3,x5的系数皆为负，故若将其作为入基变量，均只能使z值减小而非增大。由此，X（2）已是最优解X*,z(2)为对应的最优值z*.单纯形表写出单纯形表maxz=31x1