运筹学考试重点

运筹学考试重点考试题型：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）表示某一方案，这组决策变1 2 3 n量的值就代表一个具体方案。一般这些变量取值是非负且连续的（2） 存在有关的数据，同决策变量构成互不矛盾的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。（3） 都有一个要求达到的目标，它可用决策变量及其有关的价值系数构成的线性函数称为目标函数）来表示。按问题的不同，要求目标函数实现最大化或最小化。线性规划的数学模型（一般式形式），以及匕、a^、机含义、一一P10max（min）z=c1x】+%x：……^x「 ——目标函数，Cj为价值系数;（ax+ax+ ax忍（=，N）b 约束条件TOC\o"1-5"\h\z111 12 2 1nn 1ax+ax+ ax忍（=，N）b 约束条件211 22 2 2nn 2ax+ax+ ax忍（=，N）b 约束条件m11m22 mnn mIx『x2……xnN0 ——变量的非负约束条件aid技术系数，机限额系数勃兰特规则：［.）选取Cj）Zj>0中下标最小的非基变量Xk为换入变量。即k=min\c—z>0,2）当按0规则计算存在两个和两个以上最小比值时，选择下标最小的基变量为换出变量。线性规划问题的所有可行解构成的集合为主集集合，也可能为无界域集合，它有有限个顶点，每个顶点对应于线性规划问题的直可行解，若它有最优解，则必在集合的某个顶点上达到。如果把约束方程「x1+3x2^4标准化为「x1+3x2+x3 =42x1+5x2^5 I2x1+5x2—x4+x5=5贝U：x1为决策变量，x2为决策变量，x3为非负松弛变量，x4为非负剩余变量，x5为人工变量线性规划问题的基可行解与基解的区别：基解是基可行解的分量N0已知原线性规划数学模型maxZ二CX，AX=b，XN0，则其对偶问题数学模型为min_二Yb，YANC，Y为无约束在单纯形法中，初始基可能由决策变量、松弛变量、人工变量三种类型组成。P78运输问题的数学模型，它包含mXn个变量，（m+n）个约束方程，（m+n—1）个基变量。对产销平衡的运输问题，其数学模型，最多只有（m+n—1）个独立约束方程，即系数矩阵的秩忍（m+n—1）5个产地，5个销地的平衡运输问题，基变量有9个设运输问题，求最大值，当所有的检验数M0时，求得最优解。非基变量的系数CN1—CBB-1N1就是第一章中用符合c「Zj表示的检验数。判断题：1、 线性规划的基可行解,与可行域D的顶点一一对应（”）2、 若X是原问题的可行解，Y是对偶问题的可行解，则存在CX忍Yb（"）3、 对偶的两个数学模型，其中一个有最优解，那么另一个问题也有最优解。V4、 凡是基解一定是可行解。X5、 基解对应的基是可行基。X6、 线性规划的最优解一定是基最优解。X7、 互为对偶问题或者同时有最优解或无最优解。V8、 对偶问题有可行解，原问题也有可行解X9、 （m+n—1）个变量构成基本变量组的充要条件是它们不包闭回路。V10、 原问题有无界解，对偶问题有不可行解或不可行。VP57弱对偶性若X是原问题的可行解，Y是对偶问题的可行解，则存在CX忍Yb。P58对偶理论原问题有最优解，那么对偶问题也有最优解；且目标函数值相等。例：用图解法和单纯形法求解下题。厂x1 ^42x2 ^123x1+2x2^18[x],x2^0图解法步骤：画图；求坐标；找交集；交点的坐标代入原函数。解：图解法建立坐标系，横轴为xy纵轴为x2,。分别画出x=4，x=6，3x+2x=18的图形。其交点为A(0,6)、A,(2,6)、A(4,3).A(4,0)o12 12 12 3 4A2点：由3x1+2x2=18.x2=6解得x1=2A3点：由3x1+2x2=18.x1=4解得x2=3将A(0,6)、A,(2,6)、A(4,3).A(4,0)代入maxZ=2x+5x中，1 2 3 4 1 2Z=2X0+5X6=30；Z=2X2+5X6=34；Z=2X4+5X3=23；Z=2X4+5X0=8。最大值12 3 4为Z*=34为最优解。「.由图可知，A2x1=2,x2=6,Z*=34。单纯形法：此问题的标准型：maxZ=2x1+5x2+0x3+0x4+0x5

2(0X1+0X0+0X0)=0；a4=0-(0X0+0X1+0X0)=0；1=0-3=0-5(0X0+0X0+0X1)=0；或：X3,X2(0X1+0X0+0X0)=0；a4=0-(0X0+0X1+0X0)=0；1=0-3=0-5为0。选。」最大的数值所对应的列为换入变量，故x2为换入变量。03=b+换入变量系数二4+0=-(无意义)；04=12+2=6；05=18+2=9。选。±最小的数值所对应的行为换出变量，故X4为换出变量。换入变量的列与换出变量的行相交的数值作为主元素。下一步，使主元素变成1,本列中的其他系数变成0。

CBXBb区1区2区3区4x.0CBXBb区1区2区3区4x.0区320011/3-1/35x?60101/200x】2100-1/31/30j000-11/6-2/3当。V0时，终止计算。j.\x1=2,x2=6,x3=3,x4=0,x5=0。将其带入目标函数中可得:maxZ=2X1+5x2+0x3+0x.+°x一二2X2+5X6+°X3+°X°+°X°=34・.・Z*=34对偶问题:maxZ=4x1+8x2+2x3x1+x2 W—x1+x2+x3^x1+2x2—x3^x1>0,x2W0，X3部解：对偶问题yix1+x2 Wryi_y2+y3_y4=4Iyi+y2+2y3+y5=8°yi+y2-y3-y6=2<Y『y2,y3,Y4,y"y3N°用图解法和单纯形法解线性规划问题，并指出单纯形法迭代的每一步，相应于图形上的哪一个顶点。maxZ=2x1+x2{3x1+5x弟156x1+2x2^24xi，x2>°解：化为标准型maxZ=2x1+x2+°x3+°x4{3x1+5x2+x3 =156x1+2x2 +x4=24xi，x2,x3,x4>°图解法：i2・.・X*=(i5/4,3/4,°,°)T。将其带入目标函数中可得：maxZ=2xi+x2+°x3+°x4=2Xi5/4+1X3/4+°X°+°X°=33/4。・Z*=33/4。单纯形法:CjCj2CBXBbX]0X31530X42460j21000iX2X3X451052014100O=2-(0X3+0X6)=2；O=1-(0X5+0X2)=1；O=0-(0X1+0X0)=0；。=0-(0X0+0X1)=0。03=15^3=5；04=24+6=4。・.・X*=(0,0,15,24)t,它对应图解法中的原点。选。」最大的数值所对应的列为换入变量，故x1为换入变量。选0［最小的数值所对应的行为换出变量，故x4为换出变量。换入变量的列与换出变量的行相交的数值作为主元素。下一步，使主元素变成1,本列中的其他系数变成0。CjCj2cbXBbX10X3302X1410j01000iX2X3X441-1/23/41/301/6121/30-1/312O=2-(0X0+2X1)=0；。=1-(0X4+2X1/3)=1/3；1234O=0-(0X1+2X0)=0；。=0-(0X-1/2+2X1/6)=-1/3。3403=3+4=3/4；01=4+1/3=12。・.・X*=(4,0,3,0)t,它对应图解法中的A1(4,0)点。选。.最大的数值所对应的列为换入变量，故x为换入变量。J 2选0［最小的数值所对应的行为换出变量，故X3为换出变量。换入变量的列与换出变量的行相交的数值作为主元素。下一步，使主元素变成1,本列

。1=2-a3。1=2-a3=0-CJ2100eiCBXBbx1x2x3x41X23/4011/4-1/82X115/410-1/125/24aj00-1/12-7/24(1X0+2X1)=0；。2=1-(1X1+2X0)=0；(1X1/4+2X-1/12)=-1/12；a4=0-(1X-1/8+2X5/24)=-7/24。当。V0时，终止计算。j・・・X*=(15/4,3/4,0,0)t,它对应图解法中的A2(15/4,3/4)点。maxZ=2x]+x2+0x3+0x4=2X15/4+1X3/4+0X0+0X0=33/4。・・・Z*=33/4。用大M法，求解：minZ=-3x+4x1 2{4x1+2x2^5X1—x2=1X1，、2部解：化为标准型 minZ=-3x1+4x2+0x3+Mx4+Mx5{4x1+2x2—x3+x4 =5x1—x +x5=1x1，x2,x3,x4,x5>0、-M为任意大正数CJ-340MMeiCBXBb区1x?x3x4x5MX4542-1105/4MX511-10011a.-3-5M4—MM00a1=-3-(MX4+MX1)=-3-5M；a2=4-(MX2+MX-1)=4—M；a3=0-(MX-1+MX0)=M；a4=M-(MX1+MX0)=0；a5=M-(MX0+MX1)=0；a5=0-(0X0+0X0+0X1)=0；或：x4,x5的系数列组成的是单位矩阵，其。J均为0。选。J最小的数值所对应的列为换入变量，故x1为换入变量。04=b+换入变量系数二5：4=5/4；05=1+1=1。选。.最小的数值所对应的行为换出变量，故x5为换出变量。换入变量的列与换出变量的行相交的数值作为主元素。下一步，使主元素变成1,本列中的其他系数变成0。C.-340MM0.cbXBbx】x?x3区4x5MX4106-11-41/6-3X111-1001—aj01—6MM05M—3a1=-3-(MX0+ -3X1)=0；a 2=4- (MX6+ -3X1) =1—6M；a3=0-(MX-1+ -3X0)=M；a 4=M- (MX1+ -3X0) =0；a5=M-(MX-4+-3X1)=5M—3；或：x1，x4的系数列组成的是单位矩阵，其a」均为0。选a」最小的数值所对应的列为换入变量，故x2为换入变量。04=b+换入变量系数二1+6=1/6；01=1+-1=-1(无意义)。选0.最小的数值所对应的行为换出变量，故x4为换出变量。换入变量的列与换出变量的行相交的数值作为主元素。下一步，使主元素变成1，本列中的其他系数变成0。Cj-340MM0.CBxbb区1x?x3x4x54X21/601-1/61/6-2/3-3X17/610-1/61/61/3aj001/6M—1/6M+11/3O=_3-(4X0+-3X1)=0；o=4-(4X1+-3X0)=0；a3=0-(4X-1/6+-3X-1/6)=1/6；o4=M-(4X1/6+-3X1/6)