《运筹学》复习参考资料全.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=15∴X*==〔75，15〕T∴max z =Z*= 7075+3015=5700例2：用图解法求解 ⑴max z = 6x1+4x2 ⑵s.t. ⑸、⑹ ⑷ ⑶可行解域为oabcd0，最优解为b点由方程组 解出x1=2，x2=6∴X*==〔2，6〕T∴max z = 62+46=36例3：用图解法求解 ⑴min z =－3x1+x2s.t. ⑵ ⑶ ⑷ ⑸ ⑹、⑺解：可行解域为bcdefb，最优解为b点由方程组解出x1=4，x2=∴X*==〔4，〕T∴min z =－34+=－11二、标准型线性规划问题的单纯形解法：㈠一般思路：1、用简单易行的方法获得初始根本可行解；2、对上述解进展检验，检验其是否为最优解，假设是，停止迭代，否那么转入3；3、根据θL规那么确定改良解的方向；4、根据可能改良的方向进展迭代得到新的解；5、根据检验规那么对新解进展检验，假设是最优解，那么停止迭代，否那么转入3，直至最优解。

㈡具体做法〔可化归标准型的情况〕：设max z = c1x1+ c2x2+…+xns.t.对第i个方程参加松弛变量xn+i，i =1，2，…，m，得到列表计算，格式、算法如下：CBXBbc1c2…cn+mθLx1x2…xn+mcn+1xn+1b1a11a12…a1 n+mc n+2xn+2b2a21a22…a2 n+m.........…………cn+mxn+mbnam1am2…am n+mz1z2…zn+mσ1σ2…σn+m注①： zj =cn+1a1j++2a2j +…++mamj=，〔j=1，2，…，n+m〕σj =cj－zj ,当σj ≤0时，当前解最优注②：由max{σj}确定所对应的行的变量为“入基变量〞；由θ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.列表计算如下：CBXBb7030000θLx1x2x3x4x50x354039100540/3 =1800x445055010450/5 =900x5720〔9〕3001720/9 =800000070↑300000x33000810- 1/3300/8 =37.50x4500〔10/3〕01 - 5/950/10/3 =1570x1801 1/300 1/980/1/3 =2407070/30070/9020/3↑00－70/90x3180001－12/5130x215010 3/10- 1/670x175100- 1/10 1/6570070300220/3000-2－20/3∴X*=〔75，15，180，0，0〕T∴max z =7075+3015=5700例2：用单纯形法求解max z =7x1+12x2s.t.解：参加松弛变量x3，x4，x5，得到等效的标准模型：max z =7x1+12x2+0 x3+0 x4+0 x5s.t.列表计算如下：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/10100 1/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∴max z =720+1224=428三、非标准型线性规划问题的解法：1、一般地，对于约束条件组：假设为“≤〞，那么加松弛变量，使方程成为“＝〞；假设为“≥〞，那么减松弛变量，使方程成为“＝〞。

我们在前面标准型中是规定目标函数求极大值如果在实际问题中遇到的是求极小值，那么为非标准型可作如下处理：由目标函数min z=变成等价的目标函数max〔－z〕=令－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+5x2－Mx5s.t.单纯形表求解过程如下：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∴X*=〔2，6，2，0〕T∴max z =32+56=36类型二：目标函数min z，约束条件组≥与＝。

例2：用单纯形法求解min z =4x1+3x2s.t.解：减去松弛变量x3，x4，并化为等效的标准模型。