内容发布更新时间 : 2024/5/19 8:20:55星期一 下面是文章的全部内容请认真阅读。

《运筹学》综合复习资料

一、判断题

1、LP问题的可行域是凸集。

2、LP问题的基可行解对应可行域的顶点。

3、LP问题的最优解一定是可行域的顶点,可行域的顶点也一定是最优解。 4、若LP 问题有两个最优解,则它一定有无穷多个最优解.

???5、求解LP问题时,对取值无约束的自由变量，通常令xj?xj?xj,其中∶xj?xj?0,

在用单纯形法求得的最优解中,有可能同时出现xj??xj?0.

6、在PERT计算中，将最早节点时刻等于最迟节点时刻、且满足tL(j)?t(i,j)?tE(i)?0节点连接而成的线路是关键线路

7、在一个随机服务系统中，当其输入过程是一普阿松流时，即有

??t?n??tP?N?t??n??en!，

则同一时间区间内，相继两名顾客到达的时间间隔是相互独立且服从参数为λ的负指数

??t??pX?t??e分布，即有

8、分枝定界求解整数规划时,分枝问题的最优解不会优于原(上一级)问题的最优解. 9、对偶问题的对偶问题一定是原问题。

10、运输问题是一种特殊的LP问题，因而其求解结果也可能会有唯一的最优解或无穷多个最优解。

11、动态规划中，定义状态变量时应保证在各个阶段中所做决策的相互独立性。 12、用割平面法求解整数规划时，每次增加一个割平面／线性约束条件后，在新的线性规划可行域中，除了割去一些不属于整数解的可行解外，还割去了上级问题不属于整数解的最优解。

13、在求解目标规划时，遵循的基本原则就是在考虑低级目标时，不能破坏已经满足的高级目标。

14、根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解。

15、已知yi* 为线性规划的对偶问题的最优解，若yi* ＝０，说明在最优生产计划中第i种资源一定有剩余。

16、表上作业法中，按最小元素法给出的初始调运方案，从每一空格出发可以找出而且

1

仅能找出唯一的闭回路。

17、目标规划中正偏差变量应取正值，负偏差变量应取负值。 二、计算题 1. 某LP模型为∶

Maxz?9x1?8x2?50x3?19x4

s.t.3x1?2x2?10x3?4x4?182x3?0.5x4?3x1,x2,x3,x4?0

单纯形表已解至如下表: 9 x1 8 x2 50 x3 19 x4 0 s1 0 s2 b x4 2 4/3 0 1 2/3 -10/3 2 x3 -1/2 -1/3 1 0 -1/6 4/3 1 Zj Cj - Zj 填上表中尚缺数据，回答该问题的最优解,最优目标函数值。

2. 某运输问题的运价及各产地、销地的数据如下表，试确定总运费最低的运输方案。

A1 A2 A3 B1 3 7 1 3 B2 11 7 2 6 B3 4 3 10 5 B4 5 8 6 6 供应 7 4 9 20 需求 3. 某公司计划制造Ⅰ、Ⅱ两种家电产品，已知各制造一件时分别占用的设备A、B的台时、调试时间及每天可用的设备能力和单件产品的获利情况如下表：

设备A（小时） 设备B（小时） 调试工序（小时） 利润（元） 产品Ⅰ 0 6 1 2 产品Ⅱ 5 2 1 1 每天可用能力 15 24 5 (1) 建立获利最大的线性规划模型并求解（可不考虑整数要求）

(2) 对上问中获利最大的线性规划模型建立其对偶规划模型，并回答其最优解和说明该公司的短缺资源是哪些？

(3) 如获利最大的线性规划模型要求其变量为整数，试用割平面法解之。

T)(4) 如该公司新研制的产品Ⅲ对三种资源的单位产品消耗是（3 4 2，预期盈利为3元∕

2

件，试判断且仅判断产品Ⅲ是否值得生产？

4. 某公司有某种高效率设备3 台，拟分配给所属甲、乙、丙工厂，各工厂得到设备后，获利情况如下表，试建立最优分配方案。

工厂 获利 设备台数 甲 0 3 7 9 乙 0 5 10 11 丙 0 4 6 11 0 1 2 3 (1) 正确设定状态变量、决策变量并写出状态转移方程；(2) 写出规范的（形式）基本方程；(3) 求解。 5．

销地 产地 A1 A2 A3 销量 B1 4 1 3 8 B2 1 2 7 5 B3 1 6 5 6 B4 5 1 1 3 产量 8 10 4 (1) 求其最优解（可取初始调运方案为：x12?2,x13?6,x21?7,x22?3,x31?1,x34?3）；(2) 若价值系数C2,4由1变为3,所求最优解是否仍为最优解；(3) 若所有价值系数均增加

1,最优解是否改变？

6．有一辆卡车最大载重为10吨，用以装载3种货物，每种货物的单位重量及相应的单位价值如下表所示，问如何装载可使运输货物的总价值最大？

货物编号 单位重量（吨） 单位价值 Ⅰ 3 4 Ⅱ 4 5 Ⅲ 5 6 三、建立模型并计算

1. 设有A，B，C，D四个工人，可以完成1，2，3，4四项工作任务，由于每个工人完成不同的任务成本不同，试建立总成本最低的指派模型并求解。

工人\\ 任务 A B C D 1 7 16 16 16 3

2 9 16 19 17 3 8 15 10 14 4 13 11 15 16 2. 某采油区已建有n个计量站B1，B2…Bn，各站目前尚未被利用的能力为b1，b2…bn（吨液量/日）。为适应油田开发的需要，规划在该油区打m口调整井A1，A2…Am，且这些井的位置已经确定。根据预测，调整井的产量分别为a1，a2…am（吨液量/日）。考虑到原有计量站富余的能力，决定不另建新站，而用原有老站分工管辖调整井。按规划要求，每口井只能属于一个计量站。假定Ai到Bj的距离dij已知，试确定各调整井与计量站的关系，使新建集输管线总长度最短。(设定变量，写出模型)。 3．不允许缺货、补充时间无限短的确定型存储模型的假设条件是： 不允许缺货 补充时间无限短

需求是连续的且需求速率Ｒ为常数 单位物资单位时间的存储费用Ｃ1是常数 每次定购费Ｃ3（不考虑货款）是常数

试：（１）画出存储量变化曲线；（2）分析费用，建立总平均费用最低的订货模型（订货周期、订货量）。 四、绘图并计算

某工程的PERT数据如下表∶

工序 A B C D E 紧前工序 _ A A B,C B,C 作业时间 3 4 5 7 7 工序 F G H I J 紧前工序 C C D,E G H,I 作业时间 8 4 2 3 2 (1) 画出网络图并予节点以正确的编号；(2) 计算最早.最迟节点时刻；(3) 据所画网络图填写计算下表。

i j 作业代号 t es ef ls lf tf 关键工序

4

《运筹学》综合复习资料参考答案

一、判断题

题目 答案 题目 答案 1 √ 11 √ 2 √ 12 √ 3 x 13 √ 4 √ 14 x 5 x 15 √ 6 √ 16 √ 7 √ 17 x 8 √ 9 √ 10 √ 二、计算题 1. 参考答案：

2. 参考答案：

x13?1x14?6x23?4x31?3x32?6x34?0

3. 参考答案：

(1) x1?7(2) y1?0(3) x1?32x2?3y2?142z?17

2y3?1，短缺资源为设备B与调试工序。

2x2?2z?8

(4) ?x3?154?152??3??????3??021??014?12??4??1，故产品Ⅲ值得生产。

?0?1432??2?????4. 参考答案：

(1) 设状态变量sk表示k阶段开始时，可供分配的机器台数；决策变量xk表示k阶段分配给k工厂机器台数，则状态转移方程为：sk?1?sk?xk5