《运筹学》复习参考资料

第1页共28页《运筹学》复习参考资料资料加工、整理人——杨峰（函授总站高级讲师）要求掌握的各部分知识点第一部分线性规划问题的求解（相当于教材的第一章）——重要算法：单纯形迭代、大M法单纯形迭代、表上作业法、匈牙利法第二部分动态规划问题的求解（相当于教材的第三章）——重要算法：图上标号法第三部分网络分析问题的求解（相当于教材的第四章）——重要算法：破圈法、TP标号法、寻求网络最大流的标号法第四部分存储论简介（相当于教材的第七章）※杨老师关于学习方法的提示：《运筹学》属于应用数学的范畴，本门课程在管理类本科生层次开设时，又称“管理运筹学”，是现代数学理论和计算机技术应用于管理科学的新兴学科。非应用数学系（专业）学生学习本门课程之前务必先具备“高数Ⅱ”（线性代数、概率论与数理统计）的知识基础。学员同志们通过学习，必须领会数学建模的思想、系统工程的思想。非全日制学生学习时，只要求知道若干典型数学模型及其算法的操作，即只须明白“怎样做”，而不必去过问“为什么”要这样做。第2页共28页第一部分线性规划问题的求解一、两个变量的线性规划问题的图解法：㈠概念准备：定义：满足所有约束条件的解为可行解；可行解的全体称为可行（解）域。定义：达到目标的可行解为最优解。㈡图解法：图解法采用直角坐标求解：x1——横轴；x2——竖轴。1、将约束条件（取等号）用直线绘出；2、确定可行解域；3、绘出目标函数的图形（等值线），确定它向最优解的移动方向；注：求极大值沿价值系数向量的正向移动；求极小值沿价值系数向量的反向移动。4、确定最优解及目标函数值。㈢参考例题：（只要求下面这些有唯一最优解的类型）例1：某厂生产甲、乙两种产品，这两种产品均需在A、B、C三种不同的设备上加工，每种产品在不同设备上加工所需的工时不同，这些产品销售后所能获得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示：ABC利润（万元）甲乙3599537030有效总工时540450720——问：该厂应如何组织生产，即生产多少甲、乙产品使得该厂的总利润为最大？（此题也可用“单纯形法”或化“对偶问题”用大M法求解）设备消耗产品第3页共28页解：设x1、x2为生产甲、乙产品的数量。maxz=70x1+30x2s.t.072039450555409321212121xxxxxxxx，可行解域为oabcd0，最优解为b点。由方程组72039450552121xxxx解出x1=75，x2=15∴X*=21xx=（75，15）T∴maxz=Z*=70×75+30×15=5700⑴⑵⑶⑷⑸、⑹第4页共28页例2：用图解法求解maxz=6x1+4x2s.t.0781022122121xxxxxxx，解：可行解域为oabcd0，最优解为b点。由方程组81022121xxxx解出x1=2，x2=6∴X*=21xx=（2，6）T∴maxz=6×2+4×6=36⑴⑵⑶⑷⑸、⑹第5页共28页例3：用图解法求解minz=－3x1+x2s.t.08212523421212121xxxxxxxx，解：可行解域为bcdefb，最优解为b点。由方程组12524211xxx解出x1=4，x2=54∴X*=21xx=（4，54）T∴minz=－3×4+54=－1151⑴⑵⑶⑷⑸⑹、⑺第6页共28页二、标准型线性规划问题的单纯形解法：㈠一般思路：1、用简单易行的方法获得初始基本可行解；2、对上述解进行检验，检验其是否为最优解，若是，停止迭代，否则转入3；3、根据θL规则确定改进解的方向；4、根据可能改进的方向进行迭代得到新的解；5、根据检验规则对新解进行检验，若是最优解，则停止迭代，否则转入3，直至最优解。㈡具体做法（可化归标准型的情况）：设已知maxz=c1x1+c2x2+…+cnxns.t.njxbxaxaxabxaxaxabxaxaxajmnmnmmnnnn，，，，...210.....................22112222212111212111对第i个方程加入松弛变量xn+i，i=1，2，…，m，得到njxbxxaxaxabxxaxaxabxxaxaxajmmnnmnmmnnnnnn，，，，...210.....................2211222222121111212111列表计算，格式、算法如下：第7页共28页CBXBbc1c2…cn+mθLx1x2…xn+mcn+1xn+1b1a11a12…a1n+mcn+2xn+2b2a21a22…a2n+m.........…………cn+mxn+mbnam1am2…amn+mz1z2…zn+mσ1σ2…σn+m注①：zj=cn+1a1j+cn+2a2j+…+cn+mamj=miijinac1，（j=1，2，…，n+m）σj=cj－zj,当σj≤0时，当前解最优。注②：由max{σj}确定所对应的行的变量为“入基变量”；由θL=0minikikiiaab确定所对应的行的变量为“出基变量”，行、列交叉处为主元素，迭代时要求将主元素变为1，此列其余元素变为0。例1：用单纯形法求解（本题即是本资料P2“图解法”例1的单纯形解法；也可化“对偶问题”求解）maxz=70x1+30x2s.t.072039450555409321212121xxxxxxxx，解：加入松弛变量x3，x4，x5，得到等效的标准模型：maxz=70x1+30x2+0x3+0x4+0x5第8页共28页s.t.5,...,2,1,0720394505554093521421321jxxxxxxxxxxj列表计算如下：CBXBb7030000θLx1x2x3x4x50x354039100540/3=1800x445055010450/5=900x5720（9）3001720/9=800000070↑300000x33000810-1/3300/8=37.50x4500（10/3）01-5/950/10/3=1570x18011/3001/980/1/3=2407070/30070/9020/3↑00－70/90x3180001－12/5130x2150103/10-1/670x175100-1/101/6570070300220/3000-2－20/3∴X*=（75，15，180，0，0）T∴maxz=70×75+30×15=5700第9页共28页例2：用单纯形法求解maxz=7x1+12x2s.t.0300103200543604921212121xxxxxxxx，解：加入松弛变量x3，x4，x5，得到等效的标准模型：maxz=7x1+12x2+0x3+0x4+0x5s.t.5,...,2,1,03001032005436049521421321jxxxxxxxxxxj列表计算如下：第10页共28页CBXBb712000θLx1x2x3x4x50x336094100360/4=900x420045010200/5=400x53003（10）001300/10=3000000712↑0000x324078/10010-2/5240/78/10=2400/780x450（5/2）001-1/250/5/2=2012x2303/101001/1030/3/10=10018/512006/517/5↑000－6/50x384001－78/2529/257x1201002/5-1/512x224010－3/254/28428712034/2511/35000－34/25－11/35∴X*=（20，24，84，0，0）T∴maxz=7×20+12×24=428三、非标准型线性规划问题的解法：1、一般地，对于约束条件组：若为“≤”，则加松弛变量，使方程成为“＝”；若为“≥”，则减松弛变量，使方程成为“＝”。我们在前面标准型中是规定目标函数求极大值。如果在实际问题中遇到的是求极小值，则为非标准型。可作如下处理：第11页共28页由目标函数minz=njjjxc1变成等价的目标函数max（－z）=njjjxc1)(令－z=z/，∴minz=－maxz/2、等式约束——大M法：通过加人工变量的方法，构造人造基，从而产生初始可行基。人工变量的价值系数为－M，M是很大的正数，从原理上理解又称为“惩罚系数”。（课本P29）类型一：目标函数仍为maxz，约束条件组≤与＝。例1：maxz=3x1+5x2s.t.018231224212121xxxxxx，解：加入松弛变量x3，x4，得到等效的标准模型：maxz=3x1+5x2s.t.4,3,2,1,018231224214231jxxxxxxxj其中第三个约束条件虽然是等式，但因无初始解，所以增加一个人工变量x5，得到：maxz=3x1+5x2－Mx5s.t.5,...,2,1,0182312245214231jxxxxxxxxj第12页共28页单纯形表求解过程如下：CBXBb3500－MθLx1x2x3x4x50x34（1）01004/1=40x41202010——－Mx5183200118/3=6－3M－2M00－M3M＋3↑5＋2M0003x1410100——0x4120201012/2=6－Mx560（2）－3016/2=33－2M3＋3M0－M05↑－3－3M003x14101004/1=40x4600（3）1－16/3=25x2301－3/201/23/(－2/3)=－9/235－9/205/2009/2↑0－M－5/2305x12100－1/31/3x320011/3－1/3x260101/20363503/21000－3/2－M－1第13页共28页∴X*=（2，6，2，0）T∴maxz=3×2+5×6=36类型二：目标函数minz，约束条件组≥与＝。例2：用单纯形法求解minz=4x1+3x2s.t.012231642212121xxxxxx，解：减去松弛变量x3，x4，并化为等效的标准模型：maxz/=－4x1－3x2s.t.4,3,2,1,012231642421321jxxxxxxxj增加人工变量x5、x6，得到：maxz/=－4x1－3x2－Mx5－Mx6s.t6,...,2,1,01223164264215321jxxxxxxxxxj单纯形表求解过程如下：第14页共28页CBXBb－400－M－MθLx1x2x3x4x5x6－Mx5162（4）－101016/4=4－Mx612320－10112/2=6－5M－6MMM－M－M5M－46M－3↑－M－M00－3x241/21－1/401/404/1/2=8－Mx64（2）01/2－1－1/214/2=2－2M－3/2－33/4－M/2MM/2－3/4－M2M－5/2↑0M/2－3/4－M3/4－3M/20－3x2301－3/81/43/8－1/4－4x12101/4－1/2－1/41/2－17－4－31/85/4－1/8－5/400－1/8－5/4－M＋1/8－M＋5/4∴X*=（2，3，0，0）T∴minz=－maxz/=－（－17）=17第15页共28页四、对偶问题的解法：什么是对偶问题？1、在资源一定的条件下，作出最大的贡献；2、完成给定的工作，所消耗的资源最少。引例（与本资料P2例1“图解法”、P7例1“单纯形法”同）：某工厂生产甲、乙两种产品，这些产品均需在A、B、C三种不同的设备