《运筹学》复习参考资料

《《运筹学》复习参考资料》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、.第一部分线性规划问题的求解——重要算法：图解法、单纯形迭代、大M法单纯形迭代、对偶问题、表上作业法（找初始可行解：西北角法，最小元素法；最优性检验：闭回路法，位势法；）、目标规划：图解法、整数规划：分支定界法（次重点），匈牙利法（重点）、第二部分动态规划问题的求解——重要算法：图上标号法第三部分网络分析问题的求解——重要算法：破圈法、TP标号法、寻求网络最大流的标号法第一部分线性规划问题的求解一、两个变量的线性规划问题的图解法：㈠概念准备：定义：满足所有约束条件的解为可行解；可行解的全体称为可行（解）域。定义：达到目标的可行解为最优解

2、。㈡图解法：图解法采用直角坐标求解：x1——横轴；x2——竖轴。1、将约束条件（取等号）用直线绘出；2、确定可行解域；3、绘出目标函数的图形（等值线），确定它向最优解的移动方向；注：求极大值沿价值系数向量的正向移动；求极小值沿价值系数向量的反向移动。4、确定最优解及目标函数值。㈢参考例题：（只要求下面这些有唯一最优解的类型）例1：某厂生产甲、乙两种产品，这两种产品均需在A、B、C三种不同的设备上加工，每种产品在不同设备上加工所需的工时不同，这些产品销售后所能获得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示：品产

3、耗消备设ABC利润（万元）甲乙3599537030有效总工时540450720——问：该厂应如何组织生产，即生产多少甲、乙产品使得该厂的总利润为最大？（此题也可用“单纯形法”或化“对偶问题”用大M法求解）解：设x1、x2为生产甲、乙产品的数量。⑴maxz=70x1+30x2⑵s.t.⑸、⑹⑷⑶..可行解域为oabcd0，最优解为b点。由方程组解出x1=75，x2=15∴X*==（75，15）T∴maxz=Z*=70×75+30×15=5700例2：用图解法求解⑴maxz=6x1+4x2⑵s.t.⑸、⑹⑷⑶..可行解域为oabcd0，最优

4、解为b点。由方程组解出x1=2，x2=6∴X*==（2，6）T∴maxz=6×2+4×6=36例3：用图解法求解⑴minz=－3x1+x2s.t.⑵⑶⑷⑸⑹、⑺解：可行解域为bcdefb，最优解为b点。由方程组解出x1=4，x2=∴X*==（4，）T..∴minz=－3×4+=－11..二、标准型线性规划问题的单纯形解法：㈠一般思路：1、用简单易行的方法获得初始基本可行解；2、对上述解进行检验，检验其是否为最优解，若是，停止迭代，否则转入3；3、根据θL规则确定改进解的方向；4、根据可能改进的方向进行迭代得到新的解；5、根据检验规则对新

5、解进行检验，若是最优解，则停止迭代，否则转入3，直至最优解。㈡具体做法（可化归标准型的情况）：设已知maxz=c1x1+c2x2+…+cnxns.t.对第i个方程加入松弛变量xn+i，i=1，2，…，m，得到列表计算，格式、算法如下：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=

6、，（j=1，2，…，n+m）σj=cj－zj,当σj≤0时，当前解最优。..注②：由max{σj}确定所对应的行的变量为“入基变量”；由θL=确定所对应的行的变量为“出基变量”，行、列交叉处为主元素，迭代时要求将主元素变为1，此列其余元素变为0。例1：用单纯形法求解（本题即是本资料P2“图解法”例1的单纯形解法；也可化“对偶问题”求解）maxz=70x1+30x2s.t.解：加入松弛变量x3，x4，x5，得到等效的标准模型：maxz=70x1+30x2+0x3+0x4+0x5s.t.列表计算如下：CBXBb7030000θLx1x2x3

7、x4x50x354039100540/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）

8、T..∴maxz=70×75+30×15=5700..例2：用单纯形法求解maxz=7x1+12x2s.t.解：加入松弛变量x3，x4，x5，得到等效的标准模型：maxz=7x1+12x2+0x3+0x4+