运筹学复习整理

1、1.简答题运筹学的工作步骤提出和形成问题：即要弄清问题的目标，可能的约束，问题的可控变量以 及相关的参数，搜集相关资料；建立模型：即把问题中可控变量，参数，目标与约束之间的关系用模型表 示出来；求解：用各种手段将模型求解，解可以是最优解，次优解，满意解。复杂 模型的求解需用计算机，解得精度要求可有决策者提出；解的检验：首先检查求解步骤和程序有无错误，然后检查解是否反映现实 问题；解的控制：通过控制解的变化过程决定对解是否做一定的改变；解的实施：是指将解用到实际中必须考虑的实际问题，如向实际部门讲清 解的用法，在实施中可能产生的问题和修改。退化产生原因及解决办法单纯形法计算中用。规则确定换出变量

2、时，有时存在两个以上相同的最小 比值，这样在下一次迭代中就有一个或几个基变量等于零，这就出现退化 解。勃兰特规则：选取cj-zj0中下标最小的非基变量xk为换入变量，即k=min(j I cj-zj0)当按。规则计算存在两个和两个以上最小比值时，选取下标最小的基 变量为换出变量。对偶问题的经济解释-这说明yi是右端项bi每增加一个单位对目标函数Z的贡献。-对偶变量yi在经济上表示原问题第i种资源的边际价值。-对偶变量的值yi*所表示的第i种资源的边际价值，称为影子价值。若原问题的价值系数Cj表示单位产值，则yi称为影子价格；若原问题的价值系数Cj表示单位利润，则yi称为影子利润。影子价格不是资

3、源的实际价格，而是资源配置结构的反映，是在其它数据相 对稳定的条件下某种资源增加一个单位导致的目标函数值的增量变化。（4）分枝定界法步骤a）先求出整数规划相应的LP（即不考虑整数限制）的最优解，b）若求得的最优解符合整数要求，则是原IP的最优解；c）若不满足整数条件，则任选一个不满足整数条件的变量来构造新 的约束，在原可行域中剔除部分非整数解。d）然后，再在缩小的可行域中求解新构造的线性规划的最优解，这样通过求解一系列线性规划问题，最终得到原整数规划的最优解。（5）树的性质一个无圈的连通图称为树。1树至少有两个悬挂点。一个图为树的充要条件是：不含圈，边数比点数少1.一个图为树的充要条件是：连通

4、，边数比点数少1.一个图为树的充要条件是：任两点之间恰有一条链。2.建模题（1）线性规划建模：目标函数max（min） 约束条件z=cx+ c x + + c x(1.1 )a x +a x +-+ a x )b ia x +a x +-+ a x )b(1.2 )a x +a x +x , x+ a x )bm0(1.3 )（2）目标规划建模：实际量:I f = 口标值I负偏差变量正偏差变量最好等于：min d-d +最好不大于：min d+最好不小于：min d-min Z = EP 芝(w - d-+ w 顼 + ) kkl l kl lk =1 l =1绝对约束目标约束非负性约束乙a

5、xij j j = 1绝对约束目标约束非负性约束乙a xij j j = 1V乙 c x + d - - d + = E *kj j k k kj=1i = 1,2,., mk = 1,2,., Kj = 1,2,., n目标的重要程度不同，用优先等级因子Pk来表示第k等级目标。 优先等级因子Pk是正的常数，Pk Pk+1 o同一优先等级下的目标的相对重要性，赋以不同的加权系数w整数规划模型Max (min) Z = Zcjxjs.t. Zaijxj 0且部分或全部是整数3.证明题证明可行域为凸集为了证明满足线性规划问题的约束条件Y P x = b, x 0, j = 1,2,，n的所有点(可

6、行解)组成的集合是凸集，只要证明D中任意两点连线上的点必然在 D内即可。X(1 - , x nX(2 ) - , x n以 X (X(1 - , x nX(2 ) - , x nX(2 ) = (2 ), x(2 )是D内的任意两点；X(1)乏X(2)。则有Y P xG)= b, xG) 0，j = 1,2,. ,n令 X=(x1j=1Y P x(2令 X=(x1j=1Y P x(2) = b, x(2) 0, j = 1,2, ., nx )t为x(i),x(2)连线上的任意一点，即n(0忍 a 1)将它代入约束条件，j j j=1 x，2X的每一个分量是x =ax(1)+ (1 - 得到Y

7、 P xj = 1X=a X+(1-a冷a) x(2)，=Y P la x (1) (1 aj)x(2)jj = 1na乙px ?)+ Yj=1bY px j)j=1b 一侦b所以乂产0, j=1,2,n。证毕。又因 x(1), x(2) 0, a 0,1 a 所以乂产0, j=1,2,n。证毕。证明无界解的判定构造一个新的解X(1),它的分量为x (1 ) = b ； 人 a ； m + k (人0 )x (1 )= Xm + kx (1 ) = 0 ; j = m + 1 , ., n ,并且 j 丰 m + k因。m+k0,所以对任意的入0都是可行解，把x(1 )代入目标函数内得z=z0

8、+入 a m+k ；因。m+k0,故当入一+8，则z+8，故该问题目标函数无界。证明弱对偶性设原问题是max z = CX; AX 0因X是原问题的可行解，所以满足约束条件，即AX b若r是对偶问题的可行解，将r左乘上式，得到Fax C ; Y 0因Y是对偶问题的可行解，将X右乘上式 ,得到 YAX C所以满足YA C.于是得到CX YAX Yb证毕.4.计算题(1)标准型，单纯行法计算-乙cbc-乙cbcm +1一 Lai i, m +1一&ai inc c.cccj1mm +1n0CXbxxxxiBB1mm +1ncxb10aa01111,m +11n1cxb00aa02222,m +12

9、n2:c:x:b:0:1:a:a:0mmmm , m +1mnm（2）对偶型计算原问题对偶问题目标函数maxmin目标函数约束条件变量变量符号约束条件无约束原问题(LP)max111211mn对偶问题min(y , y1112(c(y , y1112(cm1m2mn当LP与DP均为可行时,LP与DP均得到最优解单-纯形方法：保持LP可行的同时,单-纯形方法：保持LP可行的同时,逐步将DP变可行X寸偶单纯形方法： 保持DP可行的同时, 逐步将LF变可运输问题初始解确定最小元素法：-从单位运价表中逐次挑选最小元素，安排运量mina.,bo-然后，划去该元素所在行或列：-当产大于销，划去该元素所在列

10、；-当产小于销，划去该元素所在行。伏格尔法：第一步：求出每行次小运价与最小运价之差，记为ui，i=1,2,.,m ；同时 求出每列次小运价与最小运价之差，记为vj，j=1，2，n ；第二步：找出所有行、列差额的最大值，即L=maxui，vi，差额L对应行 或列的最小运价处优先调运；第三步：这时必有一列或一行调运完毕，在剩下的运价中再求最大差额， 进行第二次调运，依次进行下去，直到最后全部调运完毕，就得到一个初始调运 方案。判定最优解闭合回路法：从每一空格出发找一条闭回路。它是以某空格为起点，用水平或垂直线向前划， 当碰到一数字格时可以转90后，继续前进，直到回到起始空格为止。当检验数 还存在负

11、数时，说明原方案不是最优解。位势法：变量的检验数bij=cij-ui-vj=0,即cij =ui +vj，且令u1 =0,计算位势量ui和vj 计算非基变量的检验数o产厂虹v.改进方法确定进基变量a）检查非基变量xij的检验数oij，按minoij| oij 0= olk确定xlk进基。确定离基变量b）非基变量xlk进基之后，能让它的运量增加多少呢？ 就要求它所在行和列的运量保持产销平衡。 保持产销平衡的方法是闭回路法。c）闭回路法：以进基变量xlk所在格为始点和终点，其余顶点均为基变 量的封闭回路。d）闭回路的画法:从进基变量xlk所在格开始，用水平或垂直线向前划， 每碰到一个基变量格转90

12、，继续前进，直到返回始点。e）奇偶点：始点是偶点，依次奇偶相间标注；偶点标“+”，表示运量 增加量；奇点标“-”，表示运量减少量。f）调整量：最小可减少的运量，即奇点运量的最小值。 奇点运量的最小值所在格的基变量离基。产销不平衡产大于销：只要增加一个假想的销地j=n+1 （实际上是储存），该销地总需 要量为私a _芫b TOC o 1-5 h z i = 1顶=1 C ；= 0而在单位运价表中从各产地到假想销地的单位运价为i,，+ 1销大于产：可以在产销平衡表中增加一个假想的产地i=m+1，该地产量为元 可_ _一 .；旗bj -旗% 在单位运价表上令从该假想产地到各销地的运价为j = j=1

13、i=1（4）指派问题各行各列出现零元素每行元素减去该行最小元素每列元素减去该行最小元素进行试指派，寻求最优解给只有一个0元素的行（列）的0加圈，然后划去0元素所在行的其他0元 素，记作加圈0元素数目等于矩阵的阶数，则指派问题达到最优解做最少的直线覆盖所有0元素，已确定该系数矩阵中能找到最多的独立元素 数对没有圈的行打”号对已打”的行所有含元素的列打”在对打有”的列中含圈的元素打”对没有打”的行及打”的列画一纵线，这就是覆盖所有0元素的最少直线e,最小支撑树破圈法：任取一圈，去掉权重最大的边，重复进行直到无圈可破。避圈法：选取权重最小的边，重复进行直到形成部分树，并保证不构成圈。最短路径问题Di

14、jkstra 算法：T 3 .) = min T (u .), P 3,) + 七.-S:已确定最短路的(即具有p标号)的节点集合。P：最短路径长度信息；T:目前路径长度信息。入：相关长度的路径信息最大流问题标号过程:(1 )给vs标号(-,+8)，vs成为已标号未检查的点，其余都是未标号点。取一个已标号未检查的点vi，对一切未标号点vj：若有非饱和孤(vi,vj)， 则vj标号(vi,l(vj)，其中l(vj) = minl(vi),cij-fij，vj成为已标号未检查的点；若 有非零孤(vj,vi)，则vj标号(-vi,l(vj)，其中l(vj) = minl(vi),fji，vj成为已标

15、号未 检查的点。vi成为已标号已检查的点。重复步骤(2)，直到vt成为标号点或所有标号点都检查过。若vt成为标号 点，表明得到一条vs到vt的增广链，转入调整过程；若所有标号点都检查 过，表明这时的可行流就是最大流，算法结束。 调整过程：在增广链上，前向孤流量增加l(vt)，后向孤流量减少l(vt)。截集：给定容量网络D = (V,A,C)，若点集V被剖分为两个非空集合V1和V2,使vsV1， vteV2，则把孤集(V1,V2)称为(分离vs和vt的)截集。V1V1显然，若把某一截集的弧从网络中去掉，则从vs到vt便不存在路。所以，直观 上说，截集是从vs到vt的必经之路。截集的容量(简称截量)最小截集。(8)网络计划工序最早开始时间：工序最早可能开始时间。TES(i,j)=TE(i) =maxTE (i) +T(i, j)标号的上界工序最迟结束时间:工序最迟必须结束的时间。TLF(i,j)=TL =min(TL(j)-T(i, j) 标号的下