《运筹学》复习资料

1、运筹学综合复习资料一、判断题1、LP问题的可行域是凸集。2、LP问题的基可行解对应可行域的顶点。3、LP问题的最优解一定是可行域的顶点，可行域的顶点也一定是最优解。4、若LP问题有两个最优解，则它一定有无穷多个最优解.5、 求解LP问题时,对取值无约束的自由变量，通常令Xj =Xj -Xj ,其中：Xj Xj _0, 在用单纯形法求得的最优解中，有可能同时出现x/ x/ 0.6、在PERT计算中，将最早节点时刻等于最迟节点时刻、且满足如（j） - t（i, j） - tE（i） = 0节 点连接而成的线路是关键线路pN（t ）= n=匕丄，7、在一个随机服务系统中，当其输入过程是一普阿松流时，

2、即有n! ,则同一时间区间内，相继两名顾客到达的时间间隔是相互独立且服从参数为 入的负指数 分布，即有P X =t = e&分枝定界求解整数规划时，分枝问题的最优解不会优于原（上一级）问题的最优解9、对偶问题的对偶问题一定是原问题。10、运输问题是一种特殊的LP问题，因而其求解结果也可能会有唯一的最优解或无穷 多个最优解。11、动态规划中，定义状态变量时应保证在各个阶段中所做决策的相互独立性。12、用割平面法求解整数规划时，每次增加一个割平面/线性约束条件后，在新的线性 规划可行域中，除了割去一些不属于整数解的可行解外，还割去了上级问题不属于整数 解的最优解。13、在求解目标规划时，遵循的基本

3、原则就是在考虑低级目标时，不能破坏已经满足的 咼级目标。14、根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶 问题无可行解时，其原问题具有无界解。15、 已知y*为线性规划的对偶问题的最优解，若 y* =0,说明在最优生产计划中第i 种资源一定有剩余。16、表上作业法中，按最小元素法给出的初始调运方案，从每一空格出发可以找出而且仅能找出唯一的闭回路。17、目标规划中正偏差变量应取正值，负偏差变量应取负值二、计算题1. 某LP模型为：Max z = 9为 8x250x319x4s.t. 3x1 2x2 10x3 4x4 -182x30.5x4 _ 3洛，X2, X3,

4、X4 一 0单纯形表已解至如下表：9X18X250X319X40S10S2bX424/301213-10/32X3-1/2-1/310-1/64/31ZjC - Z填上表中尚缺数据，回答该问题的最优解，最优目标函数值。2.某运输问题的运价及各产地、销地的数据如下表，试确定总运费最低的运输方案。B1B2B3B4供应A1311457A277384A3121069需求3656203. 某公司计划制造I、U两种家电产品，已知各制造一件时分别占用的设备A、B的台时、调试时间及每天可用的设备能力和单件产品的获利情况如下表：产品I产品U每天可用能力设备A （小时）0515设备B （小时）6224调试工序（小

5、时）115利润（元）21（1）建立获利最大的线性规划模型并求解（可不考虑整数要求）（2）对上问中获利最大的线性规划模型建立其对偶规划模型，并回答其最优解和说明该 公司的短缺资源是哪些？（3）如获利最大的线性规划模型要求其变量为整数，试用割平面法解之。T 如该公司新研制的产品川对三种资源的单位产品消耗是（3 4 2），预期盈利为3元/件，试判断且仅判断产品川是否值得生产？4. 某公司有某种高效率设备3台，拟分配给所属甲、乙、丙工厂，各工厂得到设备后, 获利情况如下表，试建立最优分配方案。获利设备台数甲乙丙0000135427106391111（1）正确设定状态变量、决策变量并写出状态转移方程；（

6、2）写出规范的（形式）基本方程；（3）求解。5.销地 产地B1B2B3B4产量A141158A2126110A337514销量8563（1）求其最优解（可取初始调运方案为：X!2= 2 , X!3= 6, X21= 7, X22= 3, X31= 1, X34= 3）；若价值系数C2,4由1变为3,所求最优解是否仍为最优解；若所有价值系数均增加 1,最优解是否改变？6.有一辆卡车最大载重为10吨，用以装载3种货物，每种货物的单位重量及相应的单 位价值如下表所示，问如何装载可使运输货物的总价值最大？货物编号In出单位重量（吨）345单位价值456三、建立模型并计算1.设有A，B，C, D四个工人

7、，可以完成1, 2, 3, 4四项工作任务，由于每个工人完 成不同的任务成本不同，试建立总成本最低的指派模型并求解。工人任务1234A79813B16161511C16191015D161714162. 某采油区已建有n个计量站Bi, B2-Bn,各站目前尚未被利用的能力为bi, b?b （吨 液量/日）。为适应油田开发的需要，规划在该油区打 m 口调整井Ai, Az-Am，且这些井 的位置已经确定。根据预测，调整井的产量分别为ai, az-am （吨液量/日）。考虑到原有计量站富余的能力，决定不另建新站，而用原有老站分工管辖调整井。按规划要求， 每口井只能属于一个计量站。假定 Ai到Bj的距

8、离dj已知，试确定各调整井与计量站的 关系，使新建集输管线总长度最短。（设定变量，写出模型）。3 不允许缺货、补充时间无限短的确定型存储模型的假设条件是：不允许缺货补充时间无限短需求是连续的且需求速率R为常数单位物资单位时间的存储费用C 1是常数每次定购费C 3 （不考虑货款）是常数试：（1）画出存储量变化曲线；（2）分析费用，建立总平均费用最低的订货模型（订 货周期、订货量）。四、绘图并计算某工程的PERT数据如下表：工序紧前工序作业时间工序紧前工序作业时间A3FC8BA4GC4CA5HD,E2DB,C7IG3EB,C7JH,l2（1）画出网络图并予节点以正确的编号；（2）计算最早.最迟节点

9、时刻；（3）据所画网 络图填写计算下表。ij作业代号tesefIslftf关键工序运筹学综合复习资料参考答案、判断题题目12345678910答案VVXVXVVVVV题目11121314151617答案VVVXVVX、计算题1. 参考答案:9X850心190力0S2b19X424/3012/3-10/3250xj-1/2-U30-1/64/31Zj1326/30013/310/388Cj坷-2 300133-10 32. 参考答案:X13 = 1X-14 = 6X23 = 4X32 =63. 参考答案：Xk表示k阶段分配给k工(1) Xi二7? X2= 32z =17 2(2) %=0y 14

10、y 12，短缺资源为设备B与调试工序。(3)X1 =3X2 =2z =815/4-15/23(4)3=3_(0 21)0 1/4-1/24=1，故产品川值得生产。2 -1/4 324.参考答案：(1)设状态变量sk表示k阶段开始时，可供分配的机器台数；决策变量厂机器台数，则状态转移方程为:f4(S4)=0fk(Sk)=0max Vk Sk,Xkfk 1 Sk 1 k =3,2,10刍仝kSk 1 仝k -xkXr=0 x?=2 X3=1 3=145 参考答案：(1 )最优调运方案：x12=2 x13=6X21=4 X22= 3 x23 =3X31=4(2 )是(3)不改变6 参考答案：运送第一

11、种货物2件，运送第二种货物1件，共重10砘，可达最大价值为13三、建立模型并计算1.参考答案：2.参考答案：设Xj表示i井是否连到j站m nMin z _ dij xiji壬j生ns.t. Xjj = 1 i = T mj 1m，二 aixij 乞 bj j = 1 ni =1variable positive3 参考答案：平均存储费用:平均存储量平均存储费用订货费：1 tRtdt t 01RC12一个周期内的平均每天的订货费Rt2C3t总平均费用:1 C3C tRGt 2 t模型的建立：心Jrgdt 2（其中djdt2二 2C3 t)则得:t* 二Q*Ci2RC3C t* = 2C1C3R四、绘图并计算参考答案：节点最早节点时刻最迟节点时刻节点最早节点时刻最迟节点时刻100615152337151