《运筹学考试重点(精简后的)》由会员分享，可在线阅读，更多相关《运筹学考试重点(精简后的)（10页珍藏版）》请在金锄头文库上搜索。
1、运筹学考试重点考试题型：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）每一个问题都用一组决策变量（x1，x2，x3，xn）表示某一方案，这组决策变量的值就代表一个具体方案。一般这些变量取值是非负且连续的。（2）存在有关的数据，同
2、决策变量构成互不矛盾的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。（3）都有一个要求达到的目标，它可用决策变量及其有关的价值系数构成的线性函数（称为目标函数）来表示。按问题的不同，要求目标函数实现最大化或最小化。线性规划的数学模型（一般式形式），以及cj、aij、bi含义、P10max(min)Z=c1x 1c2x n+cnx n 目标函数，cj为价值系数；a11x1a12x 2a1nx n（=,）b1 约束条件a21x1a22x 2a2nx n（=,）b2 约束条件am1x1am2x 2amnx n（=,）bm 约束条件x1 , x 2 x n0 变量的非负约束条件aij技术
3、系数，bi限额系数勃兰特规则：1）选取Cj-Zj0中下标最小的非基变量Xk为换入变量。即 。 2）当按规则计算存在两个和两个以上最小比值时，选择下标最小的基变量为换出变量。线性规划问题的所有可行解构成的集合为 凸集 集合，也可能为 无界域 集合，它有有限个顶点，每个顶点对应于线性规划问题的 基可行解 ，若它有最优解，则必在集合的 某个顶点上 达到。如果把约束方程 x 13x 24 标准化为 x 13x 2x 3 = 4 2x1 5x 25 2x1 5x 2x4x5 =5则：x1为决策变量，x2为决策变量，x3为非负松弛变量，x4为非负剩余变量，x5为人工变量。线性规划问题的基可行解与基解的区别
4、：基解是基可行解的分量0。已知原线性规划数学模型maxZ=CX，AX=b，X0，则其对偶问题数学模型为min=Yb，YAC，Y为无约束。在单纯形法中，初始基可能由决策变量、松弛变量、人工变量 三种类型组成。P78 运输问题的数学模型，它包含mn个变量，（mn）个约束方程，（mn1）个基变量。对产销平衡的运输问题，其数学模型，最多只有（mn1）个独立约束方程，即系数矩阵的秩（mn1）。5个产地，5个销地的平衡运输问题，基变量有9个。设运输问题，求最大值，当所有的检验数0 时，求得最优解。非基变量的系数 CN1CBB-1N1就是第一章中用符合cj-zj表示的检验数。判断题：1、线性规划的基可行解,
5、与可行域D的顶点一一对应()2、若是原问题的可行解，是对偶问题的可行解，则存在Cb ()3、对偶的两个数学模型，其中一个有最优解，那么另一个问题也有最优解。4、凡是基解一定是可行解。5、基解对应的基是可行基。6、线性规划的最优解一定是基最优解。7、互为对偶问题或者同时有最优解或无最优解。8、对偶问题有可行解，原问题也有可行解。9、（mn1）个变量构成基本变量组的充要条件是它们不包闭回路。10、原问题有无界解，对偶问题有不可行解或不可行。P57 弱对偶性 若是原问题的可行解，是对偶问题的可行解，则存在Cb。P58 对偶理论 原问题有最优解，那么对偶问题也有最优解；且目标函数值相等。例：用图解法和
6、单纯形法求解下题。maxZ=2x15x2 x1 4 2x2 12 3x12x218x1，x20图解法步骤：画图；求坐标；找交集；交点的坐标代入原函数。解：图解法建立坐标系，横轴为x1，纵轴为x2,。分别画出x1=4，x2=6，3x12x2=18的图形。其交点为A1(0,6)、A2(2,6)、A3(4,3)、A4(4,0)。A2点：由3x12x2=18、x2=6解得x1=2A3点：由3x12x2=18、x1=4解得x2=3 x29 3x12x2=18 A1(0,6) A2(2,6) 2x2=12 A3(4,3) O A4(4,0) 6 x1 x1=4将A1(0,6)、A2(2,6)、A3(4,3
7、)、A4(4,0)代入maxZ=2x15x2中，Z1=2056=30；Z2=2256=34；Z3=2453=23；Z4=2450=8。最大值为Z=34为最优解。由图可知，A2 x1=2，x2=6， Z=34。单纯形法：此问题的标准型：maxZ =2x15x20x30x40x5 x1 x3 = 4 2x2 x4 =12 3x12x2 x5 =18x1，x2，x3，x4，x50Cj25000iCBXBbx1x2x3x4x5 0x3410100- 0x412020106 0x518320019j250001=2-（01+00+03）=2；2=5-（00+02+02）=5；3=0-（01+00+00）
8、=0；4=0-（00+01+00）=0；5=0-（00+00+01）=0；或：x3，x4，x5的系数列组成的是单位矩阵，其j均为0。选j最大的数值所对应的列为换入变量，故x2为换入变量。3= b换入变量系数=40=-（无意义）；4= 122=6；5= 182=9。选i最小的数值所对应的行为换出变量，故x4为换出变量。换入变量的列与换出变量的行相交的数值作为主元素。下一步，使主元素变成1，本列中的其他系数变成0。Cj25000iCBXBbx1x2x3x4x5 0x34101004 5x260101/20- 0x56300-112j200-5/20Cj25000iCBXBbx1x2x3x4x5 0
9、x320011/3-1/3 5x260101/20 0x12100-1/31/3j000-11/6-2/3当j0时，终止计算。x1=2，x2=6，x3=3，x4=0，x5=0。将其带入目标函数中可得：maxZ =2x15x20x30x40x5=2256030000=34Z=34对偶问题：maxZ =4x18x22x3 x1x2 1 x1x2x3 2 x12x2x3 3 x10，x20，x30解：对偶问题y1 x1x2 1y2 x1x2x3 2y3 x12x2x3 3 x10，x20，x30min W = y12y23y3 y1y2y3 4 y1y22y3 8 0y1y2y3 2 Y10，y20
10、，y30化为标准型： y1y2y3y4=4 y1y22y3 y5=8 0y1y2y3 y6=2 Y1，y2，y3，Y4，y5，y30用图解法和单纯形法解线性规划问题，并指出单纯形法迭代的每一步，相应于图形上的哪一个顶点。maxZ =2x1x2 3x15x215 6x12x224 x1，x20解：化为标准型maxZ =2x1x20x30x4 3x15x2x3 =15 6x12x2 x4=24 x1，x2，x3，x40图解法： x2 6x12x224 12 A3（0，3） A2（15/4，3/4）0 (4，0）A1 5 3x15x215X=（15/4，3/4，0，0）T。将其带入目标函数中可得：m
11、axZ =2x1x20x30x4=215/413/40000=33/4。Z=33/4。单纯形法：Cj2100iCBXBbx1x2x3x4 0x31535105 0x42462014j21001=2-（03+06）=2；2=1-（05+02）=1；3=0-（01+00）=0；4=0-（00+01）=0。3=153=5；4= 246=4。X=（0，0，15，24）T，它对应图解法中的原点。选j最大的数值所对应的列为换入变量，故x1为换入变量。选i最小的数值所对应的行为换出变量，故x4为换出变量。换入变量的列与换出变量的行相交的数值作为主元素。下一步，使主元素变成1，本列中的其他系数变成0。Cj2100iCBXBbx1x2x3x4 0x33041-1/23/4 2X1411/301/612j01/30-1/31=2-（00+21）=0；2=1-（04+21/3）=1/3；3=0-（01+20）=0；4=0-（0-1/2+21/6）=-1/3。3=34=3/4；1= 41/3=12。X=（4，0，3，0）T，它对应图解法中的A
