运筹学考试重点 考试题型：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 1，x 2，x 3，……x n ）表示某一方案，这组决策变量的值就代表一个具体方案。
一般这些变量取值是非负且连续的。
（2）存在有关的数据，同决策变量构成互不矛盾的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。
（3）都有一个要求达到的目标，它可用决策变量及其有关的价值系数构成的线性函数（称为目标函数）来表示。
按问题的不同，要求目标函数实现最大化或最小化。
线性规划的数学模型（一般式形式），以及c j 、a ij 、b i 含义、——P10 m ax (min)Z=c 1x 1＋c 2x n +……c n x n ——目标函数，c j 为价值系数； a11x 1＋a 12x 2＋……a 1n x n ≤（=,≥）b 1 ——约束条件 a 21x 1＋a 22x 2＋……a 2n x n ≤（=,≥）b 2 ——约束条件 ………………………a m1x 1＋a m2x 2＋……a mn x n ≤（=,≥）b m ——约束条件x 1 , x 2 …… x n ≥0 ——变量的非负约束条件a ij 技术系数，b i 限额系数勃兰特规则：1）选取Cj-Zj ＞0中下标最小的非基变量X k 为换入变量。
即()0min ＞j j z c j k -=。
2）当按θ规则计算存在两个和两个以上最小比值时，选择下标最小的基变量为换出变量。
线性规划问题的所有可行解构成的集合为 凸集 集合，也可能为 无界域 集合，它有有限个顶点，每个顶点对应于线性规划问题的 基可行解 ，若它有最优解，则必在集合的某个顶点上达到。
如果把约束方程x1＋3x2≤4 标准化为x1＋3x2＋x3= 42x1 ＋5x2≥5 2x1＋5x2－x4＋x5=5则：x1为决策变量，x2为决策变量，x3为非负松弛变量，x4为非负剩余变量，x5为人工变量。
线性规划问题的基可行解与基解的区别：基解是基可行解的分量≥0。
已知原线性规划数学模型m ax Z=CX，AX= b，X≥0，则其对偶问题数学模型为m in =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 对偶理论原问题有最优解，那么对偶问题也有最优解；且目标函数值相等。
例：用图解法和单纯形法求解下题。
m ax Z=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=3x1x1=4将A1(0,6)、A2(2,6)、A3(4,3)、A4(4,0)代入m ax Z=2x1＋5x2中，Z 1=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。
单纯形法：此问题的标准型：m ax Z =2x1＋5x2＋0x3＋0x4＋0x5x1＋x3 = 42x2＋x4 =12 3x1＋2x2＋x5 =18 x1，x2，x3，x4，x5≥0σ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。
当σj＜0时，终止计算。
∴x1=2，x2=6，x3=3，x4=0，x5=0。
将其带入目标函数中可得：m ax Z =2x1＋5x2＋0x3＋0x4＋0x5=2×2＋5×6＋0×3＋0×0＋0×0=34 ∴Z﹡=34对偶问题：m ax Z =4x1＋8x2＋2x3x1＋x2≤ 1－x1＋x2＋x3≤ 2x1＋2x2－x3≤ 3x1≥0，x2≤0，x3≥0解：对偶问题y1x1＋x2≤ 1y 2－x1＋x2＋x3≤ 2y 3x1＋2x2－x3≤ 3x1≥0，x2≤0，x3≥0min W = 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用图解法和单纯形法解线性规划问题，并指出单纯形法迭代的每一步，相应于图形上的哪一个顶点。
m ax Z =2x1＋x23x1＋5x2≤156x1＋2x≤242x1，x2≥0解：化为标准型m ax Z =2x1＋x2＋0x3＋0x43x1＋5x2＋x3 =156x1＋2x＋x4=242x1，x2，x3，x4≥0图解法：x263/4）3x1＋5x2≤15∴X﹡=（15/4，3/4，0，0）T。
将其带入目标函数中可得：m ax Z =2x1＋x2＋0x3＋0x4=2×15/4＋1×3/4＋0×0＋0×0=33/4。
∴Z﹡=33/4。
单纯形法：σ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。
σ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。
σ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）点。
m ax Z =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解：化为标准型 m in Z =-3x1＋4x2＋0x3＋M x4＋M x54x1＋2x2－x3＋x4 =5x1－x2＋x5=1x1，x2，x3，x4，x5≥0Mσ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。