《运筹学》复习参考资料.doc

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

1、《运筹学》复习参考资料资料加工、整理人——杨峰（函授总站高级讲师）要求掌握的各部分知识点第一部分线性规划问题的求解（相当于教材的第一章）——重要算法：单纯形迭代、大M法单纯形迭代、表上作业法、匈牙利法第二部分动态规划问题的求解（相当于教材的第三章）——重要算法：图上标号法第三部分网络分析问题的求解（相当于教材的第四章）——重要算法：破圈法、TP标号法、寻求网络最大流的标号法第四部分存储论简介（相当于教材的第七章）※杨老师关于学习方法的提示：《运筹学》属于应用数学的范畴，本门课程在管理类本科生层次开设时，

2、又称“管理运筹学”，是现代数学理论和计算机技术应用于管理科学的新兴学科。非应用数学系（专业）学生学习本门课程之前务必先具备“高数Ⅱ”（线性代数、概率论与数理统计）的知识基础。学员同志们通过学习，必须领会数学建模的思想、系统工程的思想。非全日制学生学习时，只要求知道若干典型数学模型及其算法的操作，即只须明白“怎样做”，而不必去过问“为什么”要这样做。第29页共29页第一部分线性规划问题的求解一、两个变量的线性规划问题的图解法：㈠概念准备：定义：满足所有约束条件的解为可行解；可行解的全体称为可行（解）域。定

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

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

5、5=5700第29页共29页例2：用图解法求解⑴maxz=6x1+4x2⑵s.t.⑸、⑹⑷⑶解：可行解域为oabcd0，最优解为b点。由方程组解出x1=2，x2=6∴X*==（2，6）T∴maxz=6×2+4×6=36第29页共29页例3：用图解法求解⑴minz=－3x1+x2s.t.⑵⑶⑷⑸⑹、⑺解：可行解域为bcdefb，最优解为b点。由方程组解出x1=4，x2=∴X*==（4，）T∴minz=－3×4+=－11第29页共29页二、标准型线性规划问题的单纯形解法：㈠一般思路：1、用简单易行的方法获得

6、初始基本可行解；2、对上述解进行检验，检验其是否为最优解，若是，停止迭代，否则转入3；3、根据θL规则确定改进解的方向；4、根据可能改进的方向进行迭代得到新的解；5、根据检验规则对新解进行检验，若是最优解，则停止迭代，否则转入3，直至最优解。㈡具体做法（可化归标准型的情况）：设已知maxz=c1x1+c2x2+…+cnxns.t.对第i个方程加入松弛变量xn+i，i=1，2，…，m，得到列表计算，格式、算法如下：第29页共29页CBXBbc1c2…cn+mθLx1x2…xn+mcn+1xn+1b1a11

7、a12…a1n+mcn+2xn+2b2a21a22…a2n+m.........…………cn+mxn+mbnam1am2…amn+mz1z2…zn+mσ1σ2…σn+m注①：zj=cn+1a1j+cn+2a2j+…+cn+mamj=，（j=1，2，…，n+m）σj=cj－zj,当σj≤0时，当前解最优。注②：由max{σj}确定所对应的行的变量为“入基变量”；由θL=确定所对应的行的变量为“出基变量”，行、列交叉处为主元素，迭代时要求将主元素变为1，此列其余元素变为0。例1：用单纯形法求解（本题即是本资

8、料P2“图解法”例1的单纯形解法；也可化“对偶问题”求解）maxz=70x1+30x2s.t.解：加入松弛变量x3，x4，x5，得到等效的标准模型：maxz=70x1+30x2+0x3+0x4+0x5第29页共29页s.t.列表计算如下：CBXBb7030000θLx1x2x3x4x50x354039100540/3=1800x445055010450/5=900x5720（9）3001720/9=800000070↑300000x3300