《运筹学》复习资料

1运筹学综合复习资料一、判断题1、LP 问题的可行域是凸集。2、LP 问题的基可行解对应可行域的顶点。3、LP 问题的最优解一定是可行域的顶点,可行域的顶点也一定是最优解。4、若 LP 问题有两个最优解,则它一定有无穷多个最优解.5、求解 LP 问题时,对取值无约束的自由变量，通常令 ,其中jjjx,在用单纯形法求得的最优解中,有可能同时出现 .0jjx 0jj6、在 PERT 计算中，将最早节点时刻等于最迟节点时刻、且满足节点连接而成的线路是关键线路)(,()itjitjtEL7、在一个随机服务系统中，当其输入过程是一普阿松流时，即有，则同一时间区间内，相继两名顾客到达的时间间隔是相互独立tnetNP!且服从参数为 的负指数分布，即有 tetXp8、分枝定界求解整数规划时,分枝问题的最优解不会优于原(上一级)问题的最优解.9、对偶问题的对偶问题一定是原问题。10、运输问题是一种特殊的 LP 问题，因而其求解结果也可能会有唯一的最优解或无穷多个最优解。11、动态规划中，定义状态变量时应保证在各个阶段中所做决策的相互独立性。12、用割平面法求解整数规划时，每次增加一个割平面线性约束条件后，在新的线性规划可行域中，除了割去一些不属于整数解的可行解外，还割去了上级问题不属于整数解的最优解。13、在求解目标规划时，遵循的基本原则就是在考虑低级目标时，不能破坏已经满足的高级目标。14、根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解。15、已知 为线性规划的对偶问题的最优解，若 ，说明在最优生产计划中第*iy *iyi 种资源一定有剩余。16、表上作业法中，按最小元素法给出的初始调运方案，从每一空格出发可以找出而且仅能找出唯一的闭回路。217、目标规划中正偏差变量应取正值，负偏差变量应取负值。二、计算题1. 某 LP 模型为0,35.21843.9894321 41xxtszMa单纯形表已解至如下表:9x18x250x319x40s10s2 bx4 2 4/3 0 1 2/3 -10/32x3 -1/2 -1/3 1 0 -1/6 4/3 1ZjCj - Zj填上表中尚缺数据，回答该问题的最优解,最优目标函数值。2. 某运输问题的运价及各产地、销地的数据如下表，试确定总运费最低的运输方案。B1 B2 B3 B4 供应A1 3 11 4 5 7A2 7 7 3 8 4A3 1 2 10 6 9需求 3 6 5 6 203. 某公司计划制造、两种家电产品，已知各制造一件时分别占用的设备 A、B 的台时、调试时间及每天可用的设备能力和单件产品的获利情况如下表：产品 产品 每天可用能力设备 A（小时） 0 5 15设备 B（小时） 6 2 24调试工序（小时） 1 1 5利润（元） 2 1(1) 建立获利最大的线性规划模型并求解（可不考虑整数要求）(2) 对上问中获利最大的线性规划模型建立其对偶规划模型，并回答其最优解和说明该公司的短缺资源是哪些？(3) 如获利最大的线性规划模型要求其变量为整数，试用割平面法解之。(4) 如该公司新研制的产品对三种资源的单位产品消耗是（ 3 4 2 ，预期盈利为 3 元T)3件，试判断且仅判断产品是否值得生产？4. 某公司有某种高效率设备 3 台，拟分配给所属甲、乙、丙工厂，各工厂得到设备后，获利情况如下表，试建立最优分配方案。工厂获利 甲 乙 丙设备台数0 0 0 01 3 5 42 7 10 63 9 11 11(1) 正确设定状态变量、决策变量并写出状态转移方程；(2) 写出规范的（形式）基本方程；(3) 求解。5销地产地 B1 B2 B3 B4 产量A1 4 1 1 5 8A2 1 2 6 1 10A3 3 7 5 1 4销量 8 5 6 3(1) 求其最优解（可取初始调运方案为： ） ；3,1,7, 432211312 xxx(2) 若价值系数 由 1 变为 3,所求最优解是否仍为最优解；(3) 若所有价值系数均增加4,2C1,最优解是否改变？6有一辆卡车最大载重为 10 吨，用以装载 3 种货物，每种货物的单位重量及相应的单位价值如下表所示，问如何装载可使运输货物的总价值最大？货物编号 单位重量（吨） 3 4 5单位价值 4 5 6三、建立模型并计算1. 设有 A，B，C，D 四个工人，可以完成 1，2，3，4 四项工作任务，由于每个工人完成不同的任务成本不同，试建立总成本最低的指派模型并求解。工人 任务 1 2 3 4A 7 9 8 13B 16 16 15 11C 16 19 10 15D 16 17 14 1642. 某采油区已建有 n 个计量站 B1，B 2Bn，各站目前尚未被利用的能力为b1，b 2bn（吨液量/日） 。为适应油田开发的需要，规划在该油区打 m 口调整井A1， A2Am，且这些井的位置已经确定。根据预测，调整井的产量分别为a1， a2am（吨液量/日） 。考虑到原有计量站富余的能力，决定不另建新站，而用原有老站分工管辖调整井。按规划要求，每口井只能属于一个计量站。假定 Ai 到 Bj 的距离dij 已知，试确定各调整井与计量站的关系，使新建集输管线总长度最短。(设定变量，写出模型)。3不允许缺货、补充时间无限短的确定型存储模型的假设条件是：不允许缺货补充时间无限短需求是连续的且需求速率为常数单位物资单位时间的存储费用1 是常数每次定购费3（不考虑货款）是常数试：（）画出存储量变化曲线；（2）分析费用，建立总平均费用最低的订货模型（订货周期、订货量） 。四、绘图并计算某工程的 PERT 数据如下表工序 紧前工序 作业时间 工序 紧前工序 作业时间A _ 3 F C 8B A 4 G C 4C A 5 H D,E 2D B,C 7 I G 3E B,C 7 J H,I 2(1) 画出网络图并予节点以正确的编号；(2) 计算最早.最迟节点时刻；(3) 据所画网络图填写计算下表。i j 作业代号 t es ef ls lf tf 关键工序5运筹学综合复习资料参考答案一、判断题二、计算题1. 参考答案：2. 参考答案：063413224xx3. 参考答案：(1) 217721z(2) ，短缺资源为设备 B 与调试工序。403yy(3) 8321zx(4) ，故产品值得生产。12431053 x4. 参考答案：(1) 设状态变量 sk 表示 k 阶段开始时，可供分配的机器台数；决策变量 xk 表示 k 阶段分配给 k 工厂机器台数，则状态转移方程为： kkxs1题目 1 2 3 4 5 6 7 8 9 10答案 x x 题目 11 12 13 14 15 16 17答案 x x6(2) 1,23,max)(0141 ksfsvsf kkskkk (3) 432131 fx5参考答案：（1 ）最优调运方案：x 12=2 x13=6X21=4 x22=3 x23=3X31=4（2 ）是（3 ）不改变6参考答案：运送第一种货物 2 件，运送第二种货物 1 件，共重 10 砘，可达最大价值为 13。三、建立模型并计算1. 参考答案：11423241 xx2. 参考答案：设 表示 i 井是否连到 j 站ijpositveiablnjxmitsxdzMinmijjiminjijvr1.113参考答案：ST0 t平均存储费用：平均存储量 Rttd2107平均存储费用 tRC12订货费：一个周期内的平均每天的订货费 t3总平均费用：tCRt312模型的建立：令 （其中 ）0213tdt 32tCdt则得:13*RCt13*QRtC31*四、绘图并计算参考答案：1 243675 8 9节点 最早节点时刻 最迟节点时刻 节点 最早节点时刻 最迟节点时刻1 0 0 6 15 152 3 3 7 15 153 8 8 8 17 174 8 8 9 19 195 12 14i j t(i,j) es ef ls lf tf Key.A.1 2 3 0 3 0 3 0 *2 3 5 3 8 3 8 0 *82 4 4 3 7 4 8 13 4 0 8 8 8 8 0 *3 5 4 8 12 10 14 23 9 8 8 16 11 19 34 6 7 8 15 8 15 0 *4 7 7 8 15 8 15 0 *5 8 3 12 15 14 17 26 7 0 15 15 15 15 0 *7 8 2 15 17 15 17 0 *8 9 2 17 19 17 19 0 *