《运筹学》线性规划问题复习补充
一、 简答题
1. 试述运筹学模型应用的基本流程。
2. 简述运筹学学科的性质和特点。 1. 运筹学已被广泛应用于工商企业、军事部门、民政事业等研究组织内的统筹协调问题，
2. 运筹学既对各种经营进行创造性的科学研究，它具有很强的实践性，最终应能向决策者提供建设性意见，并应收到实效；3. 它以整体最优为目标，从系统的观点出发，力图以整个系统最佳的方式来解决该系统各部门之间的利害冲突。
3. 试述线性规划问题以及单纯形法求解的几何意义。
4. 如果max 型线性规划问题有无界解，则其对偶问题无可行解， 为什么？ 弱对偶性
5. 试述影子价格和一般市场价格的区别。 6. 简述单纯形法出现退化的现象, 原因和措施。
7. 目标规划模型有什么特点?
相同点：都有决策变量、目标函数和约束条件
线性规划模型存在的局限性：（不同点）
1）要求问题的解必须满足全部约束条件，实际问题中并非所有约束都需要严格满足。
2）只能处理单目标的优化问题。实际问题中，目标和约束可以相互转化。
3）线性规划中各个约束条件都处于同等重要地位，但现实问题中，各目标的重要性即有层次上的差别，同一层次中又可以有权重上的区分。
4）线性规划寻求最优解，但很多实际问题中只需找出满意解就可以。
8. 整数规划问题分支定界法的直观解释和基本过程是什么? 分支终止条件是什么?
二、 建模题
1． 运输工具的配载问题。有一辆运输卡车，载重2.5吨，容积18米3，用来装载如下两种货物：箱装件0.4米3，125公斤；包装件1.5米3，125公斤。请问：如何装，卡车所装物件个数最多？
2． 从甲、乙、丙三种矿石中提炼A 、B 两种金属，每种矿石的金属含量、所需金属总量以及矿石价格如下表所示，欲决定每种矿石各用多少吨可以使总费用最省，试建立相应的线性规划模型。
3．
三、 证明题
D ={x |∑a ij x j =b i , x j ≥0, i =1,..., m }
j =1n 1. 证明线性规划问题的可行域是凸集。 所有的线性规划约束都可以化成：AX
假设可行域为S, 从中任意取两个点X1,X2,
则AX1
则A(a*X1+(1-a)*X2)=a*AX1+(1-a)*AX2
所以A(a*X1+(1-a)*X2)
所以a*X1+(1-a)*X2属于S
据凸集的定义可知：S 凸集。
即线性规划问题的可靠域一定是凸集。
2. 线性规划问题 max z =CX , AX =b , X ≥0, 设X 1, X 2为问题的两个最优解，证明αX 1+(1-α) X 2也是其最优解， 即该问题有无穷多最优解。
线性规划有解，解集必为凸集，x1，x2是两顶点，两点连线上任何一点都可以表成两点的凸组合，既然x1和x2都是最优解，哪么他们的凸组合也必是最优解
3．线性规划问题 max z =CX , AX =b , X ≥0, 设X 0为问题的最优解， 若目标函数中C 用C* 代替后， 问题的最优解变为X*， 求证：(C *-C )(X *-X 0) ≥0.
将不等式化开为C*(X*-X)-C(X*-X),因为当等于C*时，最优解为X*,所以X*-X定大于0，而当等于C 时，最优解为X ，所以X*-X定小于0，所以整个式子大于0 ，什么时候能取到0，应该是当X=0时吧！
四、 计算题
1． 考虑线性规划问题
m i n z =x 1+βx 2
⎧-2x 1+x 2≤4 ⎪x -x ≤2⎨12⎪x , x ≥0⎩12
试讨论β在什么取值范围时, 该问题:
(1) 有唯一最优解;
(2) 有无穷多最优解
(3) 为无界解。
2． 求线性规划问题的所有基解， 并指出哪些是基可行解。
max z =x 1+4x 2
⎧x 1+x 2+x 3=4 ⎨-x +x +x =2⎩124
x i ≥0, i =1,..., 4
3． 请分别给出下列线性规划问题的标准型和对偶问题。
m i n Z =x 3+x 1+x 22-x 635
+x +x ≥57⎧2x 1+x 2-4x 343⎪x +2x -x ≤4． ⎪134s .. t ⎨ +x =5-2⎪-x 1+3x 2-x 4
⎪x , x , x ≥0, x ≤0, x 无约束12345⎩
4． 应用对偶理论证明下述线性规划问题无最优解。
max z =x 1+x 2
⎧-x 1+x 2+x 3≤2 ⎪s .. t ⎨-2x 1+x 2-x 3≤1
⎪x , x , x ≥0⎩123
5． 已知线性规划
max Z =c 1x 1+c 2x 2+c 3x 3
⎧a 11x 1+a 12x 2+a 13x 3≤b 1⎪⎨a 21x 1+a 22x 2+a 23x 3≤b 2⎪x , x , x ≥0⎩123 -1的最优单纯形表如表下，求原线性规划矩阵C 、A 、及b ，最优基B 及B ．
总体要求:
(1) 牢固掌握课本和作业的基本知识点
(2) 理解所学习模型所针对的问题类型
(3) 能够对比较简单的问题建立模型
(4) 在理解模型的求解思想的基础上掌握求解的具体过程
(5) 基本理论和方法的简单应用
(6) 基础理论的简单证明
(7) 基本模型的计算机求解：Lingo 或Excel
《运筹学》线性规划问题复习补充
一、 简答题
1. 试述运筹学模型应用的基本流程。
2. 简述运筹学学科的性质和特点。 1. 运筹学已被广泛应用于工商企业、军事部门、民政事业等研究组织内的统筹协调问题，
2. 运筹学既对各种经营进行创造性的科学研究，它具有很强的实践性，最终应能向决策者提供建设性意见，并应收到实效；3. 它以整体最优为目标，从系统的观点出发，力图以整个系统最佳的方式来解决该系统各部门之间的利害冲突。
3. 试述线性规划问题以及单纯形法求解的几何意义。
4. 如果max 型线性规划问题有无界解，则其对偶问题无可行解， 为什么？ 弱对偶性
5. 试述影子价格和一般市场价格的区别。 6. 简述单纯形法出现退化的现象, 原因和措施。
7. 目标规划模型有什么特点?
相同点：都有决策变量、目标函数和约束条件
线性规划模型存在的局限性：（不同点）
1）要求问题的解必须满足全部约束条件，实际问题中并非所有约束都需要严格满足。
2）只能处理单目标的优化问题。实际问题中，目标和约束可以相互转化。
3）线性规划中各个约束条件都处于同等重要地位，但现实问题中，各目标的重要性即有层次上的差别，同一层次中又可以有权重上的区分。
4）线性规划寻求最优解，但很多实际问题中只需找出满意解就可以。
8. 整数规划问题分支定界法的直观解释和基本过程是什么? 分支终止条件是什么?
二、 建模题
1． 运输工具的配载问题。有一辆运输卡车，载重2.5吨，容积18米3，用来装载如下两种货物：箱装件0.4米3，125公斤；包装件1.5米3，125公斤。请问：如何装，卡车所装物件个数最多？
2． 从甲、乙、丙三种矿石中提炼A 、B 两种金属，每种矿石的金属含量、所需金属总量以及矿石价格如下表所示，欲决定每种矿石各用多少吨可以使总费用最省，试建立相应的线性规划模型。
3．
三、 证明题
D ={x |∑a ij x j =b i , x j ≥0, i =1,..., m }
j =1n 1. 证明线性规划问题的可行域是凸集。 所有的线性规划约束都可以化成：AX
假设可行域为S, 从中任意取两个点X1,X2,
则AX1
则A(a*X1+(1-a)*X2)=a*AX1+(1-a)*AX2
所以A(a*X1+(1-a)*X2)
所以a*X1+(1-a)*X2属于S
据凸集的定义可知：S 凸集。
即线性规划问题的可靠域一定是凸集。
2. 线性规划问题 max z =CX , AX =b , X ≥0, 设X 1, X 2为问题的两个最优解，证明αX 1+(1-α) X 2也是其最优解， 即该问题有无穷多最优解。
线性规划有解，解集必为凸集，x1，x2是两顶点，两点连线上任何一点都可以表成两点的凸组合，既然x1和x2都是最优解，哪么他们的凸组合也必是最优解
3．线性规划问题 max z =CX , AX =b , X ≥0, 设X 0为问题的最优解， 若目标函数中C 用C* 代替后， 问题的最优解变为X*， 求证：(C *-C )(X *-X 0) ≥0.
将不等式化开为C*(X*-X)-C(X*-X),因为当等于C*时，最优解为X*,所以X*-X定大于0，而当等于C 时，最优解为X ，所以X*-X定小于0，所以整个式子大于0 ，什么时候能取到0，应该是当X=0时吧！
四、 计算题
1． 考虑线性规划问题
m i n z =x 1+βx 2
⎧-2x 1+x 2≤4 ⎪x -x ≤2⎨12⎪x , x ≥0⎩12
试讨论β在什么取值范围时, 该问题:
(1) 有唯一最优解;
(2) 有无穷多最优解
(3) 为无界解。
2． 求线性规划问题的所有基解， 并指出哪些是基可行解。
max z =x 1+4x 2
⎧x 1+x 2+x 3=4 ⎨-x +x +x =2⎩124
x i ≥0, i =1,..., 4
3． 请分别给出下列线性规划问题的标准型和对偶问题。
m i n Z =x 3+x 1+x 22-x 635
+x +x ≥57⎧2x 1+x 2-4x 343⎪x +2x -x ≤4． ⎪134s .. t ⎨ +x =5-2⎪-x 1+3x 2-x 4
⎪x , x , x ≥0, x ≤0, x 无约束12345⎩
4． 应用对偶理论证明下述线性规划问题无最优解。
max z =x 1+x 2
⎧-x 1+x 2+x 3≤2 ⎪s .. t ⎨-2x 1+x 2-x 3≤1
⎪x , x , x ≥0⎩123
5． 已知线性规划
max Z =c 1x 1+c 2x 2+c 3x 3
⎧a 11x 1+a 12x 2+a 13x 3≤b 1⎪⎨a 21x 1+a 22x 2+a 23x 3≤b 2⎪x , x , x ≥0⎩123 -1的最优单纯形表如表下，求原线性规划矩阵C 、A 、及b ，最优基B 及B ．
总体要求:
(1) 牢固掌握课本和作业的基本知识点
(2) 理解所学习模型所针对的问题类型
(3) 能够对比较简单的问题建立模型
(4) 在理解模型的求解思想的基础上掌握求解的具体过程
(5) 基本理论和方法的简单应用
(6) 基础理论的简单证明
(7) 基本模型的计算机求解：Lingo 或Excel