《运筹学》课程综合复习资料

《运筹学》课程综合复习资料

一、判断下述说法是否正确（正确划*，错误划）“X”、线性规划模型中增加约束条件，可行域的范围一般将缩小，减少约束条件，可行域的范围一般1将扩大、线性规划问题的每一个基解对应可行域的一个顶点

2、线性规划问题的任一可行解都可以用全部基可行解的线性组合表示

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

5、已知y为线性规划的对偶问题的最优解，若y=0,说明在最优生产计划中第i种资源一定有剩余、表上作业法中，按最小元素法给出的初始调运方案，从每一空格出发可以找出而且仅能找出唯6一的闭回路、目标规划中正偏差变量应取正值，负偏差变量应取负值

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

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

10、问题的可行域是凸集11LP、问题的基本可行解对应可行域的顶点12LP、问题的最优解一定是可行域的顶点，可行域的顶点也一定是最优解13LP、若问题有两个最优解，则它一定有无穷多个最优解.14LPf f!f ff、求解问题时，对取值无约束的自由变量，通常令£.=/•-.，其中在15LP x.%.20,J J J JJ用单纯形法求得的最优解中，有可能同时出现勺Xj

0.、分枝定界求解整数规划时，分枝问题的最优解不会优于原（上一级）问题的最优解.

16、对偶问题的对偶问题一定是原问题

17、运输问题是一种特殊的问题，总有可行解存在18LP、运输问题是一种特殊的问题，因而其求解结果也可能会有唯一的最优解或多个最优解19LP、在网络图中，连接最早、最迟节点时刻相等的节点所成的线路是关键线路20PERT整数规划中，割平面的构造应满足能割掉松弛问题的最优解，但不割掉原问题的可行解

21.动态规划实质是阶段上枚举，但过程上不枚举

22.图中，节点时刻相等的节点连接而成的线路是为关键线路

23.PERT

二、建立模型

1、某采油区已建有n个计量站Bi，B...B,各站目前尚未被利用的能力为b，b2…bn（吨液量/日）2n为适应油田开发的需要，规划在该油区打m口调整井A”A2…Am，且这些井的位置已经确定根据预测，调整井的产量分别为由，a

2.・.am（吨液量/日）考虑到原有计量站富余的能力，决定不另建新站，而用原有老站分工管辖调整井按规划耍求，每口井只能属于一个计量站假定到的距离已知，A Bjdij试确定各调整井与计量站的关系，使新建集输管线总长度最短（设定变量，写出模型）.篮球队要选择名队员组成上场阵容，名队员的身高及擅长位置见下表:258队员12345678身高

1.

921.

901.

881.

861.

851.

831.

801.78擅长位置中锋中锋前锋前锋前锋后卫后卫后卫上场阵容应满足以下条件只能有一名中锋上场；至少有一名后卫；如一号和号均上场，则号46不出场；号和号至少有一个不出场问应如何选择名上场队员，才能使出场队员平均身高最高，285试建立其模型

三、计算及回答.某公司计划制造、两种家电产品，已知各制造一件时分别占用的设备的台时、调试时间1I nA、B及每天可用的设备能力和单件产品的获利情况如下表产品产品每天可用能力I11设备A（小时）0515设备B（小时）6224调试工序（小时）115利润（元）21

①建立获利最大的线性规划模型并求解

②对获利最大的线性规划模型

①，建立其对偶规划模型，并回答其最优解和说明该公司的短缺资源是哪些？

③如该公司新研制的产品HI对三种资源的单位产品消耗是

（342）、预期盈利为3元/件，试判断且仅判断产品是否值得生产？HI.某公司计划制造、两种家电产品，根据已知数据建立的获利最大的线性规划模型为2I nMax z=2X]+x2s.t.5X1526x+2X2412+x52x x0n2上述模型的单纯形表已解至如下表21000C XbB BXix S1s s223SI0510015X111/301/604S302/30-1/611机会成本检验数

（1）完成模型求解，并回答最优解及最优目标函数值（）建立该问题的对偶规划，并回答其最优解和说明该公司的短缺资源是哪些？2

（3）当获利最大的线性规划模型

①要求其变量为整数，试用割平面法解之.某商业公司计划开办家新商店，决定由家建筑公司承建，已知各建筑公司对各家商店的建344造费用报价如下表（单位万元），试问商业公司应怎样决定，才能使总建造费用最省？商店商店商店商店1234建筑公司148715建筑公司2791714建筑公司369128建筑公司

467146.下图是一个交通网络，每条边（弧）的容量及一个可行流如下表所示，试求这个网络的最大流4边容量f..边容量九s--1552-622s-2423-622s—3324-t421-4525—t331-5336—t542-

530.某人每天从住处

①开车至工作地

⑦上班，每天早上他总得超速开车；下图是其可能行车路线,5各段线路可能遇到警察的概率如下表，试为此公选择一条碰到警察概率最小的行车路线边概率边概率边概率1—

20.22—

40.84—

50.41—

30.93—

40.14—

60.352—

30.63—

50.35—

70.256—

70.5,某企业有某种高效率设备台，拟分配给所属甲、乙、丙车间，各车间得到设备后，获利情63况如下表，试建立最优分配方案、甲乙丙设备台数0000135427106391111综合复习资料参考答案

一、判断题号12345678910答案q q q q q q qX X X题号11121314151617181920答案qqqqq qXXX题号212223答案qqX

二、建立模型.答设％.表示井是否连到站1i j=通网Min z/=1;=1s.t.Z/=1i=T・・・m j=iZ叩-bj j=i…几z=lvar tablepositive答:

2.设表队员上场与否Xj=O,1j8Maxz=V cx.;JJ./=!S.t.+X=I2x+x+x16783X]+%4+尤6x+x128x+x++x+x+x+x+x=5}245678=0,1j=l…8

三、计算及问答

1.答1玉=%X2=%Z=I/2y=0%=%，短缺资源为设备B与调试工序丫、15/4-15/23⑶/3=3-021故产品值得生产01/4-1/24=1,m\-1/43/2b答⑴

2.21000C XbB BX1x Sis S32200510015S1211/301/604X1002/30-1/611S3机会成本22/301/308检验数01/30-1/3000015/4-15/215/2S121001/4-1/27/2X11x010-1/43/23/22机会成本2101/41/217/2检验数000-1/4-1/2为=%%=%，短缺资源为设备与调试工序2%=0B⑶玉=3%=2z=8答增广路一一调整后，最大流为

4.S—2—5-14t,

11.答行车线路一一一一

5.

12357.答玉6=0x=2x=1/13=1423。