运筹学规划复习.doc

《运筹学》线性计划问题复习补充

一、 简答题
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两种金属, 每种矿石金属含量、 所需金属总量以及矿石价格以下表所表示, 欲决定每种矿石各用多少吨能够使总费用最省, 试建立对应线性计划模型。

每吨矿石金属含量 (克/吨)
所需金属总量

甲
乙
丙
A
300
200
60
48 千克
B
200
240
320
56 千克
每吨矿石价格(元／吨)
60
48
50

3．

三、 证实题
1. 证实线性计划问题可行域是凸集。
全部线性计划约束都能够化成: AX<=b
假设可行域为S,从中任意取两个点X1,X2,
则AX1<=b,AX2<=b
则A(a*X1+(1-a)*X2)=a*AX1+(1-a)*AX2<=a*b+(1-a)*b=b 其中0<=a<=1
所以A(a*X1+(1-a)*X2)<=b
所以a*X1+(1-a)*X2属于S
据凸集定义可知: S凸集。
即线性计划问题可靠域一定是凸集。

2. 线性计划问题 设, 为问题两个最优解, 证实也是其最优解, 即该问题有没有穷多最优解。
线性计划有解, 解集必为凸集, x1, x2是两顶点, 两点连线上任何一点都能够表成两点凸组合, 既然x1和x2都是最优解, 哪么她们凸组合也必是最优解

3．线性计划问题 设为问题最优解, 若目标函数中C用C* 替换后, 问题最优解变为X*, 求证: .
将不等式化开为C*(X*-X)-C(X*-X),因为当等于C*时, 最优解为X*,所以X*-X定大于0, 而当等于C时, 最优解为X, 所以X*-X定小于0, 所以整个式子大于0 , 什么时候能取到0, 应该是当X=0时吧!

四、 计算题

1． 考虑线性计划问题

试讨论在什么取值范围时, 该问题:
(1) 有唯一最优解;
(2) 有没有穷多最优解
(3) 为无界解。

2． 求线性计划问题全部基解, 并指出哪些是基可行解。

3． 请分别给出下列线性计划问题标准型和对偶问题。
．
4． 应用对偶理论证实下述线性计划问题无最优解。

5． 已知线性计划

最优单纯形表如表下, 求原线性计划矩阵C、 A、 及b, 最优基B及．

Cj
c1
c2
c3
c4
c5
b
CB
XB
x1
x2
x3
x4
x5
C1
x1
1
0
4
1/6
1/15
6
C2
x2
0
1
－3
0
1/5
2
λj
0
0
－1
－2
－3

总体要求:
(1) 牢靠掌握书本和作业基础知识点
(2) 了解所学习模型所针对问题类型
(3) 能够对比较简单问题建立模型
(4) 在了解模型求解思想基础上掌握求解具体过程
(5) 基础理论和方法简单应用
(6) 基础理论简单证实
(7) 基础模型计算机求解: Lingo或Excel