运筹学考试重点

、二SJ—运筹学考试重点考试题型：1、填空题30分2、判断题10分3、原问题转化为对偶问题10分/15分4、M法单纯线性规划计算20分/15分5、图解法、单纯性法计算30分绪论运筹学的工作步骤一一P3（1）提出和形成问题；（2）建立模型；（3）求解；（4）解的检验；（5）解的控制；（6）解的实施。运筹学模型的三种基本形式一一P3（1）形象模型；（2）模拟模型；（3）符号或数学模型,目前用得最多的是符号或数学模型。线性规划的三个特征一一P9（必考）（1）每一个问题都用一组决策变量（x，x，x，……x）表示某一方案，这组决策变123n量的值就代表一个具体方案。一般这些变量取值是非负且连续的（2）存在有关的数据，同决策变量构成互不矛盾的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。（3）都有一个要求达到的目标，它可用决策变量及其有关的价值系数构成的线性函数称为目标函数）来表示。按问题的不同，要求目标函数实现最大化或最小化。线性规划的数学模型（一般式形式），以及％a,、、含义、一一P10max（min）Z=*xmax（min）Z=*x1+c2x+cx目标函数，七为价值系数;（a11x1+a12x2+a1nx“＜（二,〉）、约束条件ax+ax+ax<（二,〉）b约束条件a21x1+a22x2ax+ax+ax<（二,〉）b约束条件m11m22mnnmIx】，x2……xn〉0——变量的非负约束条件a,技术系数，b/艮额系数勃兰特规则：1）选取Cj-Zj>0中下标最小的非基变量Xk为换入变量。即kminjc.z>02）当按规则计算存在两个和两个以上最小比值时，选择下标最小的基变量为换出变量。线性规划问题的所有可行解构成的集合为凸集集合，也可能为无界域集合，它有有限个顶点，每个顶点对应于线性规划问题的基可行解，若它有最优解，则必在集合的某个顶点上达到。x1+3x2+x3=4如果把约束方程「x1+3x2W4标准化为2x1+5x2N52x1+5x厂气+气=5则：X1为x1+3x2+x3=42x1+5x2N52x1+5x厂气+气=5则：X1为决策变量，x2为决策变量%3为非负松弛变量，%4为非负剩余变量，X5为人P78运输问题的数学模型，它包含mXn个变量，（m+n）个约束方程，（m+n—1）个基变量。对产销平衡的运输问题，其数学模型，最多只有（m+n—1）个独立约束方程，即系数矩阵的秩W（m+n—1）5个产地，5个销地的平衡运输问题，基变量有9个设运输问题，求最大值，当所有的检验数m时，求得最优解。非基变量的系数CN—CB-1N就是第一章中用符合c-z表示的检验数。1B1jj判断题：1、线性规划的基可行解，与可行域D的顶点一一对应（"）2、若X是原问题的可行解，Y是对偶问题的可行解，则存在CXWYb（"）3、对偶的两个数学模型，其中一个有最优解，那么另一个问题也有最优解。"4、凡是基解一定是可行解。X5、基解对应的基是可行基。X6、线性规划的最优解一定是基最优解。X7、互为对偶问题或者同时有最优解或无最优解。"8、对偶问题有可行解，原问题也有可行解。X9、（m+n—1）个变量构成基本变量组的充要条件是它们不包闭回路。"10、原问题有无界解，对偶问题有不可行解或不可行。"P57弱对偶性若X是原问题的可行解，Y是对偶问题的可行解，则存在CXWYb。P58对偶理论原问题有最优解，那么对偶问题也有最优解；且目标函数值相等。例：用图解法和单纯形法求解下题。xW42X3<23x1+2x2W18匚x1,x2^0图解法步骤：画图；求坐标；找交集；交点的坐标代入原函数。解：图解法建立坐标系，横轴为x「纵轴为x2，。分别画出x=4,x=6,3x+2x=18的图形。其交点为A(0,6)、A,(2,6)、A,4,3)、A(4,0)o12121234A2点：由3x1+2x2=18>x2=6解得x1=2A3点：由3x1+2x2=18>x1=4解得x2=3将A(0,6)、A,(2,6)、AJ4,3)、A(4,0)代入maxZ=2x+5x中，123412Z1=2X0+5X6=30；Z「2X2+5X6=34；Z「2X4+5X3=23；Z「2X4+5X0=8。最大值为Z*=34为最优解。・•・由图可知，A2x「2,x2=6,Z*=34o单纯形法：此问题的标准型：

2(0X1+0X0+0X0)=0；。「0-(0X0+0X1+0X0)=0；010=0-3。=0-5(0X0+0X0+0X1)=0；或：x,X,,2(0X1+0X0+0X0)=0；。「0-(0X0+0X1+0X0)=0；010=0-3。=0-5。3二b—换入变量系数二4：0=-(无意义)；。4=12：2=6；。5=18：2=9。选。义最小的数值所对应的行为换出变量，故x4为换出变量。换入变量的列与换出变量的行相交的数值作为主元素。下一步，使主元素变成1,本列中的其他系数变成0。CBXBbxix2x3x4x50x3200ii/3-i/35x260i0i/200xi2i00-i/3i/30j000-ii/6-2/3当OjV0时，终止计算。.*.xi=2,x2=6,x「3，x4=0,气=0。将其带入目标函数中可得:maxZ=2x1+5x2+0x3+0x4+0x5=2X2+5X6+0X3+0X0+0X0=34・.・Z*=34对偶问题：maxZ=4x1+8x2+2x3xi+x2^YYiN0，y2N0，yN0化为标准型:—x1+x2+x3<2x1+2x2—x3<3解：yi对偶问题xi+x2^—x1+x2+x3<2x1+2x2—x3<3x1N0,x2W0,x3N0minW=y1+2y2+3y3y+y+2yW8J1230y+y—yN2123

ry1-y2+y3~y4=40y1+y2~y3-y6=2I七，出，y.,Y4,丛，Sn0用图解法和单纯形法解线性规划问题，并指出单纯形法迭代的每一步，相应于图形上的哪一个顶点。maXZ=2X1+X2r3%1+"^156x1+"W24X],气曰0解：化为标准型maxZ=2X1解：化为标准型maxZ=2X1+X2+0X3+0X4r3x1+5x2+x=156X1+2X+气=24气，气,图解法：1212・.・X*=(15/4,3/4,0,0)T。将其带入目标函数中可得:maxZ=2x1+x2+0x3+0x4=2X15/4+1X3/4+QXQ+QX0=33/4。・.・Z*=33/4。

2(0X1+0X0)=0；。4=0-(0X0+0X1)=0。2(0X1+0X0)=0；。4=0-(0X0+0X1)=0。。=2-1。=0-303二15：3=5；0/24：6=4。・.・X*=（0，0，15，24）t，它对应图解法中的原点。选。j最大的数值所对应的列为换入变量，故％1为换入变量。选。.最小的数值所对应的行为换出变量，故X为换出变量。i4换入变量的列与换出变量的行相交的数值作为主元素。下一步，使主元素变成1,本列2(0X1+2X0)=0；。42(0X1+2X0)=0；。4=0-(0X-1/2+2X1/6)=-1/3。。=2-1。=0-303=3：4=3/4；0广4：1/3=12。・.・X*=（4，0，3，0）t，它对应图解法中的A】（4，0）点。选。j最大的数值所对应的列为换入变量，故气为换入变量。选。/最小的数值所对应的行为换出变量，故X,为换出变量。换入变量的列与换出变量的行相交的数值作为主元素。下一步，使主元素变成1,本列

。=2-。=0-3。=2-。=0-3Cj21000.iCBXBbx1x2X3X41X23/4011/4-1/82X115/410-1/125/24。j00-1/12-7/24(1X0+2X1)=0；。=1-(1X1+2X0)=0；2(1X1/4+2X-1/12)=-1/12；。4=0-(1X-1/8+2X5/24)=-7/24。当。」＜0时，终止计算。・・・X*=(15/4,3/4,0,0)t,它对应图解法中的A2(15/4,3/4)点。maxZ=2x1+x2+0x3+0x4=2X15/4+1X3/4+0X0+0X0=33/4。・・・Z*=33/4。用大M法，求解:minZ=-3X]+4x2x—x=1解：化为标准型minZ=-3x1+4x2+0X3+Mx4+Mx5。.-3-5M4-MM00。1=-3-(MX4+MX1)=-3—5M；o「4-(MX2+MX-1)=4-M；。「0-(MX-1+MX0)=M；o「M-(MX1+MX0)=0；。弘-(MX0+MX1)=0；。5=0-(0X0+0X0+0X1)=0；或：x,x5的系数列组成的是单位矩阵，其气均为0。选气最小的数值所对应的列为换入变量，故％】为换入变量。。广b—换入变量系数二5：4=5/4；。5=1：1=1。选。z最小的数值所对应的行为换出变量，故x5为换出变量。换入变量的列与换出变量的行相交的数值作为主元素。下一步，使主元素变成1,本列中的其他系数变成0。C.-340MM0zcbXBbX]X2X3X4X5MX4106-11-41/6-3X]11-1001—。j01-6MM05M-3"-3-(MX0+-3X1)二0；。「4-(MX6+-3X1)=1—6M；。「0-(MX-1+-3X0)二M；o「M-(MX1+-3X0)=0；05=M-(MX-4+-3X1)=5M—3；或：x『X4的系数列组成的是单位矩阵，其。」均为0。选气最小的数值所对应的列为换入变量，故x2为换入变量。。广b：换入变量系数二1：6=1/6；。广1：-1=-1(无意义)。选。义最小的数值所对应的行为换出变量，故x4为换出变量。换入变量的列与换出变量的行相交的数值作为主元素。下一步，使主元素变成1，本列中的其他系数变成0。Cj-340MMozCBxbbX]X2X3X4X54X21/601-1/61/6-2/3-3X17/610-1/61/61/3。j001/6M-1/6