运筹复参考资料.doc

第一部分线性规划问题的求解重要算法：图解法、单纯形迭代、大M法单纯形迭代、对偶问题、表上作业法找初始可行解：西北角法,最小元素法；最优性检验：闭回路法,位势法；、目标规划：图解法、整数规划：分支定界法次重点,匈牙利法重点、第二部分动态规划问题的求解重要算法：图上标号法第三部分网络分析问题的求解重要算法：破圈法、TP标号法、寻求网络最大流的标号法第一部分线性规划问题的求解一、两个变量的线性规划问题的图解法：概念准备：定义：满足所有约束条件的解为可行解；可行解的全体称为可行解域.定义：达到目标的可行解为最优解.图解法：图解法采用直角坐标求解：x1横轴；x2竖轴.1、将约束条件取等号用直线绘出；2、确定可行解域；3、绘出目标函数的图形等值线,确定它向最优解的移动方向；注：求极大值沿价值系数向量的正向移动；求极小值沿价值系数向量的反向移动.4、确定最优解与目标函数值.参考例题：只要求下面这些有唯一最优解的类型例1：某厂生产甲、乙两种产品,这两种产品均需在A、B、C三种不同的设备上加工,每种产品在不同设备上加工所需的工时不同,这些产品销售后所能获得利润以与这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示：品产耗消备设 A B C利润万元甲乙3 5 99 5 37030有效总工时540 450 720问：该厂应如何组织生产,即生产多少甲、乙产品使得该厂的总利润为最大？此题也可用"单纯形法"或化"对偶问题"用大M法求解解：设x1、x2为生产甲、乙产品的数量. max z = 70x1+30x2 s.t. 、 可行解域为oabcd0,最优解为b点.由方程组 解出x1=75,x2=15X*=75,15Tmax z =Z*= 70×75+30×15=5700例2：用图解法求解 max z = 6x1+4x2 s.t. 、 可行解域为oabcd0,最优解为b点.由方程组 解出x1=2,x2=6X*=2,6Tmax z = 6×2+4×6=36例3：用图解法求解 min z =3x1+x2s.t. 、解：可行解域为bcdefb,最优解为b点.由方程组解出x1=4,x2=X*=4,Tmin z =3×4+=11二、标准型线性规划问题的单纯形解法：一般思路：1、用简单易行的方法获得初始基本可行解；2、对上述解进行检验,检验其是否为最优解,若是,停止迭代,否则转入3；3、根据L规则确定改进解的方向；4、根据可能改进的方向进行迭代得到新的解；5、根据检验规则对新解进行检验,若是最优解,则停止迭代,否则转入3,直至最优解.具体做法可化归标准型的情况：设已知max z = c1x1+ c2x2+ xns.t.对第i个方程加入松弛变量xn+i,i =1,2,m,得到列表计算,格式、算法如下：CBXBbc1c2+mLx1x2xn+m+1xn+1b1a11a12a1 n+mc n+2xn+2b2a21a22a2 n+m.+mxn+mbnam1am2am n+mz1z2zn+m12n+m注： zj =+1a1j+ +2a2j + +mamj=,j=1,2,n+mj =cjzj ,当j 0时,当前解最优.注：由maxj确定所对应的行的变量为"入基变量"；由L=确定所对应的行的变量为"出基变量",行、列交叉处为主元素,迭代时要求将主元素变为1,此列其余元素变为0.例1：用单纯形法求解本题即是本资料P2"图解法"例1的单纯形解法；也可化"对偶问题"求解max z =70x1+30x2s.t.解：加入松弛变量x3,x4,x5,得到等效的标准模型：max z =70x1+30x2+0 x3+0 x4+0 x5s.t.列表计算如下：CBXBb7030000Lx1x2x3x4x50x354039100540/3 =1800x445055010450/5 =900x572093001720/9 =800000070300000x33000810- 1/3300/8 =37.50x450010/301 - 5/950/10/3 =1570x1801 1/300 1/980/1/3 =2407070/30070/9020/30070/90x318000112/5130x215010 3/10- 1/670x175100- 1/10 1/6570070300220/3000-220/3X*=75,15,180,0,0Tmax z =70×75+30×15=5700例2：用单纯形法求解max z =7x1+12x2s.t.解：加入松弛变量x3,x4,x5,得到等效的标准模型：max z =7x1+12x2+0 x3+0 x4+0 x5s.t.列表计算如下：CBXBb712000Lx1x2x3x4x50x336094100360/4 =900x420045010200/5 =400x5300310001300/10 =30000007120000x324078/10010- 2/5240/78/10 =2400/780x4505/2001- 1/250/5/2 =2012x2303/10100 1/1030/3/10 =10018/512006/517/50006/50x38400178/2529/257x1201002/5- 1/512x2240103/254/28428712034/2511/3500034/2511/35X*=20,24,84,0,0Tmax z =7×20+12×24=428三、非标准型线性规划问题的解法：1、一般地,对于约束条件组：若为"",则加松弛变量,使方程成为""；若为"",则减松弛变量,使方程成为"".我们在前面标准型中是规定目标函数求极大值.如果在实际问题中遇到的是求极小值,则为非标准型.可作如下处理：由目标函数min z=变成等价的目标函数maxz=令z=z/,min z=max z/2、等式约束大M法：通过加人工变量的方法,构造人造基,从而产生初始可行基.人工变量的价值系数为M,M是很大的正数,从原理上理解又称为"惩罚系数".课本P29类型一：目标函数仍为max z,约束条件组与.例1：max z =3x1+5x2s.t.解：加入松弛变量x3,x4,得到等效的标准模型：max z =3x1+5x2s.t.其中第三个约束条件虽然是等式,但因无初始解,所以增加一个人工变量x5,得到： max z =3x1+5x2Mx5s.t.单纯形表求解过程如下：CBXBb3500MLx1x2x3x4x50x34101004/1 =40x41202010Mx5183200118/3 =63M2M00M3M352M0003x14101000x4120201012/2 =6Mx56023016/2 =332M33M0M0533M003x14101004/1 =40x46003116/3 =25x23013/201/23/<2/3> =9/2359/205/2009/20M5/2305x121001/31/3x320011/31/3x260101/20363503/210003/2M1X*=2,6,2,0Tmax z =3×2+5×6=36类型二：目标函数min z,约束条件组与.例2：用单纯形法求解min z =4x1+3x2s.t.解：减去松弛变量x3,x4,并化为等效的标准模型：max z/ =4x13x2s.t.增加人工变量x5、x6,得到：max z/ =4x13x2Mx5Mx6s.t单纯形表求解过程如下：CBXBb400MMLx1x2x3x4x5x6Mx51624101016/4=4Mx61232010112/2=65M6MMMMM5M46M3MM003x241/211/401/404/1/2=8Mx64201/211/214/2=22M3/233/4M/2MM/23/4M2M5/20M/23/4M3/43M/203x23013/81/43/81/44x12101/41/21/41/217431/85/41/85/4001/85/4M1/8M5/4X*=2,3,0,0Tmin z =max z/ =17=17四、对偶问题的解法：什么是对偶问题？1、在资源一定的条件下,作出最大的贡献；2、完成给定的工作,所消耗的资源最少.引例与本资料P2例1 "图解法"、P7例1 "单纯形法"同：某工厂生产甲、乙两种产品,这些产品均需在A、B、C三种不同的设备上加工,每种产品在不同设备上加工时需要不同的工时,这些产品售后所能获得的利润值以与这三种加工设备因各种条件下所能使用的有效总工时数如下表：品产耗消备设 A B C利润万元甲乙3 5 99 5 37030有效总工时540 450 720问：该厂应如何组织生产,即生产多少甲、乙产品使得该厂的总利润为最大？解：原问题设x1、x2为生产甲、乙产品的数量.max z = 70x1+30x2s.t.将这个原问题化为它的对偶问题设y1、y2、y2分别为设备A、B、C单位工时数的加工费.min w = 540y1+450y2+720y3s.t.用大M法,先化为等效的标准模型：max w/ =540y1450y2720y3s.t.增加人工变量y6、y7,得到：max z/ =540y1450y2720y3My6My7s.t大M法单纯形表求解过程如下：CBXBb54045072000MMLy1y2y3y4y5y6y7My670359101070/3My730953010130/9=10/312M10M12MMMMM12M54010M45012M720MM00My660010/3811/311/360/8=2.5540y110/315/91/301/901/910/3/1/3=10-300+10/3M-8M180MM/3+60MM/3600-150+10/3M8M-540MM/3600M/3+60720y315/205/1211/81/241/81/2415/2/5/12=18540y15/615/1201/241/81/241/85/6/5/12=2540572720135/2475/12135/275/201250135/2475/12135/2M75/2M720450y320/31011/61/61/61/6y2212/5101/103/101/103/1057003604507207515751518000751575M15M该对偶问题的最优解是y*=0,2,0,0T最优目标函数值min w =5700=5700五、运输规划问题：运输规划问题的特殊解法"表上作业法"解题步骤：1、找出初始调运方案.即在<m×n>产销平衡表上给出m+n-1个数字格.最小元素法2、对空格求检验数.判别是否达到最优解.如已是最优解,则停止计算,否则转到下一步.闭回路法3、对方案进行改善,找出新的调运方案.根据检验结果选择入基变量,用表上闭回路法调整即迭代计算,得新的基本可行解4、重复2、3,再检验、再迭代,直到求得最优调运方案.类型一：供求平衡的运输规划问题又称"供需平衡"、"产销平衡"引例：某钢铁公司有三个铁矿和四个炼铁厂,铁矿的年产矿石量分别为100万吨、80万吨和50万吨,炼铁厂年需矿石量分别为50万吨、70万吨、80万吨和30万吨,这三个铁矿与四个炼铁厂的距离如下：矿铁厂铁离距炼 B1 B2 B3 B4A1A2A315 20 3 3070 8 14 2012 3 20 15问：该公司应如何组织运输,既满足各炼铁厂需要,又使总的运输费用为最小按吨.公里计？解：用"表上作业法"求解.1 用最低费用法最小元素法求此问题的初始基础可行解：地产用费地销B1B2B3B4产量SiA11520673306510020×80×A2708144420803020×30A3125332033251050×50××销量dj50708030 230230初始方案：B2203030B1B3A22080B1B3A1B250A3Z=15×20+3×80+70×30+8×20+20×30+3×50=3550吨.公里2 的初始可行解进行迭代表上闭回路法,求最优解：地产用费地销B1B2B3B4产量SiA11520143301210020×80×A2705381492080×50×30A312320202510503020××销量dj50708030 230230用表上闭回路法调整后,从上表可看出,所有检验数>=0,已得最优解.最优方案：3020B1B2A35030B2B4A22080B1B3A1Z=15×20+3×80+8×50+20×30+12×30+3×20=1960吨.公里解法分析：如何求检验数并由此确定入基变量？有数字的空格称为"基格"、打×的空格称为"空格",标号为偶数的顶点称为偶点、标号为奇数的顶点称为奇点,出发点算0故为偶点.找出所有空格的闭回路后计算它们的检验数,必须0,才得到最优解.否则,应选所有中正的最大者对应的变量xj为入基变量进行迭代调整.检验后调整运输方案的办法是：在空格的闭回路中所有的偶点均加上奇点中的最小运量,所有的奇点均减去奇点中的最小运量.重复以上两步,再检验、再调整,直到求得最优运输方案.求下面运输问题的最小值解：12341311310721923437410593656解：由最小元素法得到初始解：v1=2v2=9v3=3v4=101934u1=01311310743u2=-121923431u3=-53741059633656则：,最小值为-6,非基变量为,闭回路,最大调整量为1,得新解：,重新计算位势与影响系数,得下表：v1=8v2=9v3=3v4=101234u1=01311310752u2=-721923431u3=-53741059633656,最小值为-5,非基变量为,闭回路,最大调整为2,得新解：重新计算位势与影响系数,得下表：v1=3v2=4v3=3v4=51234u1=01311310725u2=-221923413u3=03741059633656,此时,故当前解为最优解.最优解值为：.六、目标规划问题已知目标规划问题min z= p1 d1- + p2d2- + p35d3- + 3d4- + p4 d1+x1 +2x2 + d1- - d1+ =6x1 +2x2 + d2- - d2+ =9x1 -2x2 + d3- - d3+ =4x2 + d4- - d4+ =2x1 ,x20,di- , di+0 <i=1,2,3,4>分别用图解法和单纯形法求解x2d2+54d2-d4+d3-d1+3Ad4-d1-2d3+B10 2 4 6 8 x1七1、整数规划问题分枝定界法：用分枝定界法求解整数规划七2、工作指派问题：工作指派问题的数学模型假定有n项工作需要完成,恰好有n个人每人可去完成其中一项工作,效果要好.工作指派问题的特殊解法"匈牙利法"考！解题步骤：1、使系数矩阵效率矩阵各行、各列出现零元素.作法：行约简系数矩阵各行元素减去所在行的最小元素,列约简再从所得矩阵的各列减去所在列最小元素.2、试求最优解.如能找出n个位于不同行不同列的零元素,令对应的xij= 1,其余xij= 0,得最优解,结束；否则下一步.作法：由独立0元素的行列开始,独立0元素处画 标记,在有 的行列中划去也可打*其它0元素；再在剩余的0元素中重复此做法,直至不能标记 为止.3、作能覆盖所有0元素的最少数直线集合.作法：对没有的行打号；对已打号的行中所有0元素的所在列打号；再对打有号的列中0元素的所在行打号；重复、直到得不出新的打号的行<列>为止；对没有打号的行画一横线,对打号的列画一纵线,这就得到覆盖所有0元素的最少直线数.未被直线覆盖的最小元素为cij,在未被直线覆盖处减去cij,在直线交叉处加上cij.4、重复2、3,直到求得最优解.类型一：求极小值的匈牙利法：重点掌握这种基本问题例1：有甲、乙、丙、丁四个人,要派去完成A、B、C、D四项工作,他们完成的工时如下表：人务时工任 A B C D甲乙丙丁6 12 13 410 3 12 147 14 13 168 8 12 10试问：应如何分配任务可使总工时为最少？解：用"匈牙利法"求解.已知条件可用系数矩阵效率矩阵表示为：行约简列约简cij=ABCD标号甲乙丙丁使总工时为最少的分配任务方案为：甲D,乙B,丙A,丁C此时总工时数W=4+3+7+12=26例2：求效率矩阵的最优解.列约简行约简解：标号所画0元素少于n,未得到最优解,需要继续变换矩阵求能覆盖所有0元素的最少数直线集合：未被直线覆盖的最小元素为cij=1,在未被直线覆盖处减去1,在直线交叉处加上1.标号得最优解：类型二：求极大值的匈牙利法：min z=maxzcijMcij=bij,cij中最大的元素为Mmaxz=第二部分 动态规划只要求掌握动态规划的最短路问题用"图上标号法"解决：具体解题步骤请参看教材这是本套资料少见的与教材完全相同的算法类型之一,务必看书掌握只有完全理解了这种作法思路：逆向追踪才有可能做题,考试时数字无论如何变化都能作出正确求解！第二部分到此结束第三部分网络分析一、求最小生成树最小支撑树、最小树问题：破圈法任取一个圈,从圈中去掉一条权最大的边如果有两条或两条以上的边都是权最大的边,则任意去掉其中一条.在余下的图中,重复这个步骤,直到得到一个不含圈的图为止,这时的图便是最小树.参考例题：例：求下图的最小生成树：67941510v2v1v3v5v4v6328解：用"破圈法"求得最小生成树为：9415v2v1v3v5v4v62已得最小树,此时权w=1+2+4+5+9=21为最小.二、最短路问题：有向图TP标号法狄克斯托算法具体解题步骤请参看教材P125这是本套资料少见的与教材完全相同的算法类型之一,务必看书掌握只有完全理解了这种作法思路：顺向追踪才有可能做题,考试时数字无论如何变化都能作出正确求解！参考例题：例：教材P124图48的例子略三、网络最大流问题：寻求网络最大流的标号法福特富克尔逊算法具体解题步骤请参看教材P130.教材用有序数对fij,cij表示流量,容量,但我们解题算法格式按南邮要求,用大多数运筹学书籍中的标准格式,即用有序数对cij,fij表示容量,流量.解法本质是相同的.只有完全理解了这种作法思路：标号检查、迭代调整才有可能做题,考试时数字无论如何变化都能作出正确求解！第三部分到第四部分存储论简介随机存储模型参考例题：例：一食品店要决定每天牛奶的进货量,该店根据过去的销售经验,知道需求量的概率分布如下：需求x箱25262728px0.10.30.50.1若进货每箱80元,售价100元,又若当天不能售出因牛奶变质而全部损失,试确定每天进货量.解法一：已知C=80,p=100,g=0,需求x箱25262728概率px0.10.30.50.1累计概率0.10.40.91根据单周期随机型存储模型 "报童模型"之离散型随机存储模型公式,可得0.2即可以确定进货26箱,获利的期望值最大.解法二：k=10080=20,h=80.=0.2Px=25=0.10.2Px=25+Px=26=0.4可以确定进货26箱,获利的期望值最大.注：该问题即"报童问题"关于报童进报纸问题的数学模型,即是相当于将上题的进"牛奶"改为进"报纸"等等,解法思路是完全一致的,请注意！15 / 15