运筹学考试重点(精简后的)

运筹学考试重点考试题型：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）存在有关的数据，同决策变量构成互不矛盾的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。（3）都有一个要求达到的目标，它可用决策变量及其有关的价值系数构成的线性函数（称为目标函数）来表示。按问题的不同，要求目标函数实现最大化或最小化。线性规划的数学模型（一般式形式），以及cj、aij、bi含义、——P10max(min)Z=c1x1＋c2xn+……cnxn——目标函数，cj为价值系数；a11x1＋a12x2＋……a1nxn≤（=,≥）b1——约束条件a21x1＋a22x2＋……a2nxn≤（=,≥）b2——约束条件………………………am1x1＋am2x2＋……amnxn≤（=,≥）bm——约束条件x1,x2……xn≥0——变量的非负约束条件aij技术系数，bi限额系数勃兰特规则：1）选取Cj-Zj＞0中下标最小的非基变量Xk为换入变量。即0min＞jjzcjk。2）当按规则计算存在两个和两个以上最小比值时，选择下标最小的基变量为换出变量。线性规划问题的所有可行解构成的集合为凸集集合，也可能为无界域集合，它有有限个顶点，每个顶点对应于线性规划问题的基可行解，若它有最优解，则必在集合的某个顶点上达到。如果把约束方程x1＋3x2≤4标准化为x1＋3x2＋x3=42x1＋5x2≥52x1＋5x2－x4＋x5=5则：x1为决策变量，x2为决策变量，x3为非负松弛变量，x4为非负剩余变量，x5为人工变量。线性规划问题的基可行解与基解的区别：基解是基可行解的分量≥0。已知原线性规划数学模型maxZ=CX，AX=b，X≥0，则其对偶问题数学模型为min=Yb，YA≥C，Y为无约束。在单纯形法中，初始基可能由决策变量、松弛变量、人工变量三种类型组成。P78运输问题的数学模型，它包含m×n个变量，（m＋n）个约束方程，（m＋n－1）个基变量。对产销平衡的运输问题，其数学模型，最多只有（m＋n－1）个独立约束方程，即系数矩阵的秩≤（m＋n－1）。5个产地，5个销地的平衡运输问题，基变量有9个。设运输问题，求最大值，当所有的检验数≤0时，求得最优解。非基变量的系数CN1－CBB-1N1就是第一章中用符合cj-zj表示的检验数。判断题：1、线性规划的基可行解,与可行域D的顶点一一对应(√)2、若X_是原问题的可行解，Y_是对偶问题的可行解，则存在CX_≤Y_b(√)3、对偶的两个数学模型，其中一个有最优解，那么另一个问题也有最优解。√4、凡是基解一定是可行解。×5、基解对应的基是可行基。×6、线性规划的最优解一定是基最优解。×7、互为对偶问题或者同时有最优解或无最优解。√8、对偶问题有可行解，原问题也有可行解。×9、（m＋n－1）个变量构成基本变量组的充要条件是它们不包闭回路。√10、原问题有无界解，对偶问题有不可行解或不可行。√P57弱对偶性若X_是原问题的可行解，Y_是对偶问题的可行解，则存在CX_≤Y_b。P58对偶理论原问题有最优解，那么对偶问题也有最优解；且目标函数值相等。例：用图解法和单纯形法求解下题。maxZ=2x1＋5x2x1≤42x2≤123x1＋2x2≤18x1，x2≥0图解法步骤：画图；求坐标；找交集；交点的坐标代入原函数。解：图解法建立坐标系，横轴为x1，纵轴为x2,。分别画出x1=4，x2=6，3x1＋2x2=18的图形。其交点为A1(0,6)、A2(2,6)、A3(4,3)、A4(4,0)。A2点：由3x1＋2x2=18、x2=6解得x1=2A3点：由3x1＋2x2=18、x1=4解得x2=3x293x1＋2x2=18A1(0,6)A2(2,6)2x2=12A3(4,3)OA4(4,0)6x1x1=4将A1(0,6)、A2(2,6)、A3(4,3)、A4(4,0)代入maxZ=2x1＋5x2中，Z1=2×0＋5×6=30；Z2=2×2＋5×6=34；Z3=2×4＋5×3=23；Z4=2×4＋5×0=8。最大值为Z﹡=34为最优解。∴由图可知，A2x1=2，x2=6，Z﹡=34。单纯形法：此问题的标准型：maxZ=2x1＋5x2＋0x3＋0x4＋0x5x1＋x3=42x2＋x4=123x1＋2x2＋x5=18x1，x2，x3，x4，x5≥0Cj25000θiCBXBbx1x2x3x4x50x3410100-0x4120201060x518320019σj25000σ1=2-（0×1+0×0+0×3）=2；σ2=5-（0×0+0×2+0×2）=5；σ3=0-（0×1+0×0+0×0）=0；σ4=0-（0×0+0×1+0×0）=0；σ5=0-（0×0+0×0+0×1）=0；或：x3，x4，x5的系数列组成的是单位矩阵，其σj均为0。选σj最大的数值所对应的列为换入变量，故x2为换入变量。θ3=b÷换入变量系数=4÷0=-（无意义）；θ4=12÷2=6；θ5=18÷2=9。选θi最小的数值所对应的行为换出变量，故x4为换出变量。换入变量的列与换出变量的行相交的数值作为主元素。下一步，使主元素变成1，本列中的其他系数变成0。Cj25000θiCBXBbx1x2x3x4x50x341010045x260101/20-0x56300-112σj200-5/20Cj25000θiCBXBbx1x2x3x4x50x320011/3-1/35x260101/200x12100-1/31/3σj000-11/6-2/3当σj＜0时，终止计算。∴x1=2，x2=6，x3=3，x4=0，x5=0。将其带入目标函数中可得：maxZ=2x1＋5x2＋0x3＋0x4＋0x5=2×2＋5×6＋0×3＋0×0＋0×0=34∴Z﹡=34对偶问题：maxZ=4x1＋8x2＋2x3x1＋x2≤1－x1＋x2＋x3≤2x1＋2x2－x3≤3x1≥0，x2≤0，x3≥0解：对偶问题y1x1＋x2≤1y2－x1＋x2＋x3≤2y3x1＋2x2－x3≤3x1≥0，x2≤0，x3≥0minW=y1＋2y2＋3y3y1－y2＋y3≥4y1＋y2＋2y3≤80y1＋y2－y3≥2Y1≥0，y2≥0，y3≥0化为标准型：y1－y2＋y3－y4=4y1＋y2＋2y3＋y5=80y1＋y2－y3－y6=2Y1，y2，y3，Y4，y5，y3≥0用图解法和单纯形法解线性规划问题，并指出单纯形法迭代的每一步，相应于图形上的哪一个顶点。maxZ=2x1＋x23x1＋5x2≤156x1＋2x2≤24x1，x2≥0解：化为标准型maxZ=2x1＋x2＋0x3＋0x43x1＋5x2＋x3=156x1＋2x2＋x4=24x1，x2，x3，x4≥0图解法：x26x1＋2x2≤2412A3（0，3）A2（15/4，3/4）0(4，0）A153x1＋5x2≤15∴X﹡=（15/4，3/4，0，0）T。将其带入目标函数中可得：maxZ=2x1＋x2＋0x3＋0x4=2×15/4＋1×3/4＋0×0＋0×0=33/4。∴Z﹡=33/4。单纯形法：Cj2100θiCBXBbx1x2x3x40x315351050x42462014σj2100σ1=2-（0×3+0×6）=2；σ2=1-（0×5+0×2）=1；σ3=0-（0×1+0×0）=0；σ4=0-（0×0+0×1）=0。θ3=15÷3=5；θ4=24÷6=4。∴X﹡=（0，0，15，24）T，它对应图解法中的原点。选σj最大的数值所对应的列为换入变量，故x1为换入变量。选θi最小的数值所对应的行为换出变量，故x4为换出变量。换入变量的列与换出变量的行相交的数值作为主元素。下一步，使主元素变成1，本列中的其他系数变成0。Cj2100θiCBXBbx1x2x3x40x33041-1/23/42X1411/301/612σj01/30-1/3σ1=2-（0×0+2×1）=0；σ2=1-（0×4+2×1/3）=1/3；σ3=0-（0×1+2×0）=0；σ4=0-（0×-1/2+2×1/6）=-1/3。θ3=3÷4=3/4；θ1=4÷1/3=12。∴X﹡=（4，0，3，0）T，它对应图解法中的A1（4，0）点。选σj最大的数值所对应的列为换入变量，故x2为换入变量。选θi最小的数值所对应的行为换出变量，故x3为换出变量。换入变量的列与换出变量的行相交的数值作为主元素。下一步，使主元素变成1，本列中的其他系数变成0。Cj2100θiCBXBbx1x2x3x41X23/4011/4-1/82X115/410-1/125/24σj00-1/12-7/24σ1=2-（1×0+2×1）=0；σ2=1-（1×1+2×0）=0；σ3=0-（1×1/4+2×-1/12）=-1/12；σ4=0-（1×-1/8+2×5/24）=-7/24。当σj＜0时，终止计算。∴X﹡=（15/4，3/4，0，0）T，它对应图解法中的A2（15/4，3/4）点。maxZ=2x1＋x2＋0x3＋0x4=2×15/4＋1×3/4＋0×0＋0×0=33/4。∴Z﹡=33/4。用大M法，求解：minZ=-3x1＋4x24x1＋2x2≥5x1－x2=1x1，x2≥0解：化为标准型minZ=-3x1＋4x2＋0x3＋Mx4＋Mx54x1＋2x2－x3＋x4=5x1－x2＋x5=1x1，x2，x3，x4，x5≥0M为任意大正数Cj-340MMθiCBXBbx1x2x3x4x5MX4542-1105/4MX511-10011σj-3－5M4－MM00σ1=-3-（M×4+M×1）=-3－5M；σ2=4-（M×2+M×-1）=4－M；σ3=0-（M×-1+M×0）=M；σ4=M-（M×1+M×0）=0；σ5=M-（M×0+M×1）=0；σ5=0-（0×0+0×0+0×1）=0；或：x4，x5的系数列组成的是单位矩阵，其σj均为0。选σj最小的数值所对应的列为换入变量，故x1为换入变量。θ4=b÷换入变量系数=5÷4=5/4；θ5=1÷1=1。选θi最小的数值所对应的行为换出变量，故x5为换出变量。换入变量的列与换出变量的行相交的数值作为主元素。下一步，使主元素变成1，本列中的其他系数变成0。Cj-340MMθiCBXBbx1x2x3x4x5MX4106-11-41/6-3X111-1001-σj01－6MM05M－3σ1=-3-（M×0+-3×1）=0；σ2=4-（M×6+-3×1）=1－6M；σ3=0-（M×-1+-3×0）=M；σ4=M-（M×1+-3×0）=0；σ5=M-（M×-4+-3×1）=5M－3；或：x1，x4的系数列组成的是单位矩阵，其σj均为0。选σj最小的数值所对应的列为换入变量，故x2为换入变量。θ4=b÷换入变量系数=1÷6=1/6；θ1=1÷-1=-1（无意义）。选θi最小的数值所对应的行为换出变量，故x4为换出变量。换入变量的列与换出变量的行相交的数值作为主元素。下一步，使主元素变成1，本列中的其他系数变成0。Cj-340MMθiCBXBbx1x2x3x4x54X21/601-1/61/6-2/3-3X17/610-1/61/61/3σj001/6M－1/6M＋11/3σ1=-3-（4×0+-3×1）=0；σ2=4-（4×1+-3×0）=0；σ3=0-（4×-1/6+-3×-1/6）=1/6；σ4=M-（4×1/6+-3×1/6）=M－1/6；σ5=M-（4×-2/3+-3×