《运筹学复习参考资料》由会员分享，可在线阅读，更多相关《运筹学复习参考资料（21页珍藏版）》请在金锄头文库上搜索。
1、第一局部线性规划问题的求解重要算法：图解法、单纯形迭代、大M法单纯形迭代、对偶问题、表上作业法找初始可行解：西北角法, 最小元素法；最优性检验：闭回路法，位势法；、目标规划：图解法、整数规划：分支定界法次重点，匈牙利法重 点、 第二局部动态规划问题的求解重要算法：图上标号法第三局部网络分析问题的求解重要算法：破圈法、TP标号法、寻求网络最大流的标号法第一局部线性规划问题的求解一、两个变量的线性规划问题的图解法：概念准备：定义：满足所有约束条件的解为可行解；可行解的全体称为可行解域。 定义：到达目标的可行解为最优解。图解法：图解法采用直角坐标求解：x横轴；x竖轴。1、将约束条件取等号用直线绘出;
2、122、确定可行解域；3、绘出目标函数的图形等值线，确定它向最优解的移动方向；注：求极大值沿价值系数向量的正向移动；求极小值沿价值系数向量的反向移动。4、确定最优解及目标函数值。参考例题：只要求下面这些有唯一最优解的类型例1:某厂生产甲、乙两种产品，这两种产品均需在A、B、C三种不同的设备上加工，每种产品在不同设备上加工 所需的工时不同，这些产品销售后所能获得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下 表所示：消备 产、：ABC利润 万元甲35970乙95330有效总工时540450720问：该厂应如何组织生产，即生产多少甲、乙产品使得该厂的总利润为最大？此题也可用“单纯
3、形法或化“对偶问题用大M法求解解：设x2为生产甲、乙产品的数量。 max z = 70x +30x1 2、s.t.3x + 9x 540125x + 5x 450v 129 x + 3 x 012可行解域为。abcdO，最优解为b点。 由方程组解出 x =75, x =151 25 x + 5 x = 450129 x + 3x = 72012X*= x =75, 15t丿.max z =Z*= 70X 75+30X15=5700例2:用图解法求解max z = 6x +4x1 2s.t.、2 x + x 101 2x + x 8v 12x 0J 12 可行解域为oabcdO,最优解为b点。由
4、方程组2x x 10解出 xx=2, x2=61 2x x 81 2XAX *= x =2,6tx2Amax z = 6x2+4x6=36例3：用图解法求解 min z =-3x+x1 2s.t.、x4ix 322x 5x 121 2x 2x 81 2x, x 01 2解：可行解域为bcdefb最优解为b点。x 44由方程组2； 5x 12解出x1=4, x2= 5 1 2x4AX*= x1=4, 5t2Amin z=-3x4+5 = -115二、标准型线性规划问题的单纯形解法：一般思路：1、用简单易行的方法获得初始根本可行解；2、对上述解进展检验，检验其是否为最优解，假设是，停顿迭代，否那么
5、转入3；3、根据t规那么确定改良解的方向；4、根据可能改良的方向进展迭代得到新的解；5、根据检验规那么对新解进展检验，假设是最优解，那么停顿迭代，否那么转入3，直至最优解 具体做法可化归标准型的情况：设max z = cx + ex x1 1 2 2 ns.t.a x + a x +. + a x b1111221n n 1a x + a x +. + a x b21 122 22n n 2 a x + a x +. + a x 0, j = 1, 2 , . , njm,得到对第i个方程参加松弛变量x , i =1, 2,n+ia x + a x +. + a x + x = b11 112
6、 21n nn+11a x + a x +. + a x + x = b21 122 22n nn+22+ x = bn+mma x + a x +. + a xm11 m22mn nx 0,j= 1, 2 , ., nj列表计算,格式、算法如下：CBXBbclx1c2x2+mxn+mOL+1xn+1blallai2ai n+mc n+2xn+2b2a21a22a2 n+m+mxn+mbnamiam2am n+mz1z2zn+moio2on+mymca注： zj=+1a1j+2a2j+ +mamj=n+i i/ ,尸1, 2,，n+mi=1可二cj zj,当可VO时，当前解最优。注：由m宓讥确
7、定所对应的行的变量为“入基变量由 = min 0确定所对应的行的变量为 出基变量，行、列穿插处为主元素，迭代时要求将主元 a ikik素变为 1，此列其余元素变为0。例1:用单纯形法求解此题即是本资料P2 “图解法例1的单纯形解法也可化“对偶问题求解max z =70x +30x12 s.t.3x+ 9 x 540125x+ 5 x 450129x+ 3 x 0, j = 1,2,. j.,5列表计算如下：7030000CBXBbx1x2x3x4x5OL0x354039100540/3=1800x445055010450/5=900x57203001720/9=800000070 f30000
8、0x33000810-1/3300/8=37.50x450010/301-5/950/10/3=1570x18011/3001/980/1/3=2407070/30070/9020/3 f00-70/90x3180001-12/5130x2150103/10-1/670x175100-1/101/670300220/35700000-2-20/3 X*二75, 15, 180, 0, 0T/.max z =70X75+30X15=5700例2：用单纯形法求解max z =7x +12x12s.t.9x + 4x 360124x + 5 x 200V123x +10x 012解：参加松弛变量x3
9、，X4, X5,得到等效的标准模型max z =7x +12x +0 x+0 x+0 x12345s.t.9 x + 4 x + x=3601234 x + 5 x+ x = 200V1243 x +10 x+ x = 300125列表计算如下：CBXBb7xl12x20x30x40x5OL0x336094100360/4 =900x420045010200/5 =400x5300310001300/10 =3000000712 f0000x324078/10010-2/5240/78/10 =2400/780x4505/2001-1/250/5/2 =2012x2303/101001/103
10、0/3/10 =10018/512006/517/5 f000-6/50x384001-78/2529/257xl201002/5-1/512x224010-3/254/28428712034/2511/35000-34/25-11/35/X*=20，24，84，0，0T/max z =7X20+12X24=428三、非标准型线性规划问题的解法：1、一般地，对于约束条件组：假设为“W,那么加松弛变量，使方程成为“ = 假设为“，那么减松弛变量，使方程成为“=。我们在前面标准型中是规定目标函数求极大值。如果在实际问题中遇到的是求极小值，那么为非标准型。可作如下处工(-C X )jjj=1理：cx由目标函数min z= j j变成等价的目标函数max一z j=1令z=z/,.
