运筹学考研试题

运筹学考研试汇编运筹学OperationalResearch一、线性规划（每题20分）设线性规划问题为：北京工商大学2004年攻读硕士学位研究生入学考试试题考试科目：物流管理与运筹学第一部分运筹学（60分）（1）利用两阶段法求解上述线性规划问题；（2）写出相应的对偶线性规划问题数学模型。*二、动态规划（10分）某商店在未来4个月里，准备利用它的一个仓库来专门经销某种商品。仓库最大容量能储存这种商品1000单位。假定该仓库每月只能出卖仓库现有的货。当商店在某月购货时，下月初才能到货。预测该商品未来四个月的买卖价格如下表所示，假定商品在1月开始经销时，仓库储有该商品500单位。试问若不计库存费用，该商店应如何制定1月至4月的订购与销售计划，使预期获利最大。试用动态规划建立相应的数学模型。 月份k 购买单价（ck） 销售单价（pk） 1 10 12 2 9 8 3 11 13 4 15 17三、对策论（每题15分）用图解法求解矩阵对策G={S1,S2,A},其中四、存储论（15分）某厂按合同每年需提供D个产品，不允许缺货。假设每一周期工厂需装配费b元，存储费每年每单位产品为a元，问全年应分几批订货才能使装配费、存储费两者之和为最少。一、（40分）已知线性规划问题北京交通大学2005年硕士研究生入学考试试卷考试科目：管理运筹学（1）求线性规划问题的最优解（20分）（2）求对偶问题的最优解（5分）（3）当△b3=－150时最优基是否发生变化？为什么？（5分）（4）求c2的灵敏度范围（5分）(5)如果x3的系数由[1,3,5]变为[1,3,2]，最优基是否改变？若改变求最优解。（5分）二、已知某运输问题其供销关系及单位运价表如下表所示：要求：用表上作业法求出最优调运。 销地产地 B1 B2 B3 产量 A1 4 2 5 8 A2 3 5 3 7 A3 1 3 2 4 销量 4 8 5三、（20分）某市共有6个区，每个区都可以设消防站，市政府希望设置消防站最少以便节省费用，但必须保证在城区任何地方发生火灾时消防车能在15分钟内赶到现场。据实地测定，各区之间消防车行驶时间如下表所示。建立该问题的规划模型。各区之间的行驶时间 一区二区三区四区五区六区 一区二区三区四区五区六区 010016240283212027172715020102125140四、（30分）某公司有资金10万元，若投资于各项目（i=1，2，3）的投资额为xi时，收益分别为问如何分配投资数额才能使总投资最大？五、（20分）求下图所示的网络的最小费用最大流。（每条弧旁边的数字(bij,cij)）六、（20分）某厂拟用1名修理工人，已知平均送修的设备数台/h,现有两种级别的工人可聘：A级工，其工作能力为台/小时，工资每小时20元。因设备送修，平均每台每小时造成停工损失为40元。问应聘用哪一种工人，可使工厂的经济效益较高。杭州商学院2003年硕士研究生入学考试试卷（A卷）招生专业：管理科学与工程考试科目：运筹学考试时间：3小时一、填空题（每小题4分，共28分）1、线性规划行问题的可行域为，特殊情况下为或。2、用单纯形法解线性规划问题时，目标函数中人工变量的系数为，附加变量的系数数为­。3、单纯形法与对偶单纯形法的主要区别在于：迭代过程中，前者始终保持的可行性，后者始终保持的可行性。4、分支定界法和割平面法的基本思路都是通过在原线性规划问题中不断来缩小，最终得到原问题的整数最优解。7、动态规划的两种递推方法是和。对于给定的问题，如果有固定的，则这两种方法会得到相同的最优结果。6、序贯式算法的核心是序贯地，即根据优先级别，将线性目标规划依次求解。5、目标规划中，和对于第i个目标约束，如果希望，则目标函数为。分别表示变量；二、计算题（共60分）1、已知线性规划的数学模型为：（30分）（1）用两阶段法求该模型的最优解；（2）用对偶单纯形法求该模型的最优解；（3）写出对偶问题的数学模型，并求其最优解；（4）价值系数C3在什么范围内变化可保持最优解不变？2、求解0—1规划问题：（15分）3、用动态规划方法求解整数规划问题：（15分）三、应用题（共50分）1、某公司计划新开4家连锁店B1、B2、B3、B4，并通知了4家建筑公司A1、A2、A3、A4，以便每家商店都分别由一个建筑公司来承建；设建筑公司Ai对商店Bj投标的建造费用为Cij万元（见表）。试求解：对这4家建筑公司如何分配建造任务，才能使总建造费用最少？所需的建造费用是多少？（15分） B1 B2 B3 B4 A1 15 18 21 24 A2 19 23 22 18 A3 26 17 16 19 A4 19 21 23 172、某公司有三个服装加工厂甲、乙、丙，每天的服装产量分别为1000件、1200件、1100件，供应A、B、C三个销售点，各销售点的需求量分别为900件、1300件、1000件。从服装厂到各个销售点的运费和销售利润见下表（单位：元/件）：该公司按以下目标调运产品：第一目标：满足各销售点的需求；第二目标：因路况原因，C销售点的服装最好由乙厂供应；第三目标：甲厂因仓库限制，其产品应尽量全部调出；第四目标：利润不少于60000元；第五目标：调运总费用最省；试建立该目标规划问题的数学模型（不要求求解）。（15分） 销售点工厂 A销售点 B销售点 C销售点 运费 利润 运费 利润 运费 利润 甲厂 3 20 4 25 5 27 乙厂 4 25 6 22 3 24 丙厂 5 27 3 24 4 223、某公司出售中央空调，空调每年的热销季节是6—9月，销售部门对这段时间的需求时预测分别为30、20、30、40台。每月的订货量只能是10、20、30、40台这四种情况之一，所需费用相适应为48、86、118、138万元。每月末的存货不应超过40台，储存费按月末存货量计算，每月每台为100元。由于空调是季节性产品，因而希望热销前后存货为零。问如何合理安排各个月的订货，才能使热销季节的总费用最小？（20分）四、证明题（12分）证明：如果线性规划问题有限最优解，则其目标函数最优值一定可以在可行域的顶点上达到杭州商学院2004年硕士研究生入学考试试卷（A卷）招生专业：管理科学与工程考试科目：运筹学考试时间：3小时2．单纯形法中，要把数学模型化为型，须引入；若约束条件中附加变量的系数是或原约束为，则必须引入，以构成初始可行基。3．0-1规划的隐枚举法的基本思想是从所有变量等于出发，依次指定一些变量为，直到得到一个可行解。一、填空题（每空格2分，共28分）1．线性规划问题的可行解X=（x1,x2,…,xn)T为基本可行解的充要条件是X的正分量对应的系数列向量是。4.目标规划中，和对于第i个目标约束，如果希望，则目标函数为。分别表示变量；5．建立目标规划的数学模型时，需要排定各目标的，确定各目标值bi,各权系数wj。6．动态规划模型中，状态变量的选择要能满足两个条件：和。7．动态规划中，对于一个给定的问题，如果有固定的和，则顺序递推和逆序递推会得到相同的最优结果。 已知线性规划的数学模型如下，请用图解法求该模型的最优解。（10分） 采用隐枚举法求解0-1规划问题（15分）3．已知线性规划的数学模型如下，请写出对偶问题的数学模型，并求其对偶问题的最优解。（15分）三、应用题（共70分）1．某农场有3万亩农田，欲种植玉米、大豆和小麦三种农作物。各种作物每亩需施肥料分别为0.12吨、0.2吨、0.15吨。预计秋后玉米每亩可收获500千克，售价为0.24元/千克，大豆每亩可收获200千克，售价为1.20元/千克，小麦每亩可收获300千克，售价为0.70元/千克。农场年初规划时依次考虑以下的几个方面：P1：年终收益不低于350万元；P2：总产量不低于1.25万吨；P3：小麦产量以0.5万吨为宜；P4：大豆产量不少于0.2万吨；P5；玉米产量不超过0.6万吨；P6：农场现能提供5000吨化肥，若不够，可在市场高价购买，但希望高价采购量愈少愈好。试建立该目标规划问题的数学模型（不需要求解）。（16分）2．现指派五位员工去完成五项不同的工作，每人做各项工作所需费用（元）如下表所示。问应该如何指派，才能使总的费用最小？相应的总费用为多少？（16分） 任务人员 A1 A2 A3 A4 A5 B1 12 7 9 7 9 B2 8 9 6 6 6 B3 7 17 12 14 12 B4 15 14 6 6 10 B5 4 10 7 10 63．某农场生产四种农作物，每种农作物的成本和利润如下：目前农场有400公斤肥料和500公斤杀虫剂，问每种农作物种植多少亩才使利润最大？（20分） 农作物 肥料（公斤/亩） 杀虫剂（公斤/亩） 利润（元） 萝卜 4 2 50 包心菜 2 9 40 洋葱 5 2 10 土豆 0 3 204．已知四个城市间的距离如下表所示，求从A城市出发，经其余城市一次且仅一次，最后返回到A城市的最短路径与距离。（18分） A B C D A -- 11 20 28 B 12 -- 18 25 C 23 9 -- 10 D 34 32 6 --四、证明题（12分）证明：若线性规划问题存在可行域，则问题的可行域是凸集。华南理工大学2005年攻读硕士学位研究生入学考试试卷一、设某种动物每天至少需700克蛋白质、30克矿物质、100毫克维生素。现有5种饲料可供选用，各种饲料每公斤营养成分的含量及单价如下表所示：科目：运筹学适用专业：数量经济学试建立既满足动物生长的营养需要，又使费用最省的选用饲料方案的线性规划模型。（25分） 饲料 蛋白质（克） 矿物质（克） 维生素（毫克） 价格（元/公斤） 1 3 1 0.5 0.2 2 2 0.5 1 0.7 3 1 0.2 0.2 0.4 4 6 2 2 0.3 5 6 0.5 0.8 0.8二、给定线性规划：已知试确定该基本解是否为最优解？如果是，给出相应结果；否则确定进入变量和退出变量。三、给定整数线性规划：已知其对应线性规划问题的最优单纯形表为：试以x2为源行，写出其分量切割方程和约束条件的表示形式。（20分） 基变量 x1 x2 x3 x4 x5 x6 解 z 0 0 0 0.2 0.4 1 19.4 x1 1 0 0 2/5 -1/5 0 1.8 x2 0 1 0 -1/10 1/3 0 2.3 x3 0 0 1 -9/10 -1/3 1 0.7四、某地区有三个化肥厂，设为A、B、C，其年产量分别为7万吨，8万吨和3万吨。有四个产粮区需要该种化肥，设为甲、乙、丙、丁，其化肥需求量分别为6万吨，6万吨，3万吨，3万吨。已知从各化肥厂到各产粮区的每吨化肥的运价如下标所示（表中单位：元/吨）试制定一个使总的运费为最少的化肥调拨方案。（25分） 产粮区化肥厂 甲 乙 丙 丁 A 5 8 7 3 B 4 9 10 7 C 8 4 2 9五．求解下面网络中的最大流，并在图上用切割线标记出网络的最小截集。(20分)六.指出下面网络图中的错误并予以改进：(15分)七.已知某项工程的网络图如下，试确定图中的关键路线并计算工程的预计完工时间与时间方差。(20分)北京交通大学2006年硕士研究生入学考试试卷考试科目：管理运筹学一、（25分）设有如下线性规划问题：二、（25分）标准型线性规划问题（maxz=CX,AX=b,X≥0）的最优单纯形表为：其中：x4,x5是对应于初始单位矩阵的松弛变量。试求：⑴求该标准型线性规划目标函数的系数c1-c5;⑵设该标准型线性规划的右端常数项为b,△b1和△b2分别为b的两个分量的增量，试分别对这两个增量进行灵敏度分析，即求出△b1和△b2分别变化时的取值范围。⑷要使现行的最优基不变，求目标函数系数c1的变化范围。⑸求两个约束的影子价格。 cj c1 c2 c3 c4 c5 B-1b CB XB x1 x2 x3 x4 x5 c1c2 x1x2 10 01 -12 3-1 -11 12 cj-zj 0 0 3 3 1 8三、某工厂安排某种生活必需品在以后四个月的生产计划。该产品可以在以后四个月的任一个月生产，不过受用工和原料价格的影响，不同的月份其生产成本不同，该产品在以后四个月的生产成本分别是12，10，15，18元/件。该产品在以后四个月需要量分别是400，700，900和800件。考虑到生活必需品的需要，产品需要量必须加以满足。该厂平常每月最多能生产700件，但在第二个月农闲时期工厂可以聘用临时工加班，加班后可增产300件，但生产成本每件增加3元。过剩产品每件储存费用是每月3元。试完成：（1）仿照运输问题建立使总成本最小的生产计划线性规划数学模型；（10分）（2）用运输问题表上作业法求解。（10分）（3）理论上将该问题有几个最优基本可行解？（5分）四、（25分）某城市公共交通公司共有公交客车1000辆，可投入超负荷和正常负荷两种状态运营，如果当年投入高负荷状态运营，年运量为20万人/台，且第一年投入高负荷运营时汽车年完好率为0.8，以后每年投入高负荷运营时每年完好率随车龄每年以0.1递减，如果投入正常负荷状态运营，年运量为15万人/台，第一年汽车年完好率为0.95，以后各年投入正常负荷状态运营时每年年完好率以0.05递减，试安排5年运量最大的运营方案。五、（15分）用割平面法求解下列IP问题：六、（15分）试证明定理：可行流f*是最大流的充分必要条件是不存在关于f*的增广链。七、（20分）某理发店只有一个理发师，来理发的顾客到达过程为possion流，平均到达间隔为20分钟。理发时间服从负指数分布，平均需要15分钟。试求：（1）理发店空闲的概率；（2）店内恰有3个顾客的概率；（3）店内至少有一个顾客的概率；（4）在店内的平均顾客数；（5）每位顾客在店内的平均逗留时间；（6）等待服务的平均顾客数；（7）每位顾客的平均等待时间；（8）顾客在店内逗留超过10分钟的概率。北京交通大学2004年硕士研究生入学考试试卷考试科目：管理运筹学一、（30分）回答下列问题：1.什么是线性规划问题的基可行解？2.什么是可行流？3.什么是关于可行流f的增广链？4.线性规划问题最优解共有几种可能？并写出各自相应的判别准则。5.非标准指派问题：某大型工程有5个工程项目，决定向社会公开招标。建设公司A1，A2，A3参加招标承建，根据实际情况，可允许每家公司承建一或两项工程。报价表如右，单位万元。如何将其化成标准的指派问题（只转化成标准的指派问题即可，不要求求解）二、（30分）某工厂生产甲、乙两种产品，需要A，B两种资源，有关资料如下： 工程公司 B1 B2 B3 B4 B5 A1 4 8 7 15 12 A2 7 9 17 14 10 A3 6 9 12 8 7 资源产品 A B 单位产品利润 甲 1 1 7 乙 1 2 17 资源最大供应量 6 8（1）求使工厂获利最大的生产计划（列出模型并求解）（2）确定原最优基不变条件下，产品甲的单位利润的允许可变范围。（3）若该厂准备出让资源给另一个工厂，构成原问题的对偶问题，列出对偶问题的数学模型。（4）资源A，B的影子价格。（5）试用此例的计算结果，验证和解释对偶理论中的互补松弛性定理的正确性。三、（20分）设有产量分别为30，50，60的三个原料产地A1，A2，A3，欲将原料运往需求量分别为15，10，40，45的四个销地，运价表如下。试求运费最省的调运方案。 销地产地 B1 B2 B3 B4 产量 A1 3 5 8 4 30 A2 7 4 8 6 50 A3 10 3 5 2 60 销量 15 10 40 45四、（25分）某工厂现有100台机器，拟分四期使用，在每一期都有两种生产任务。根据经验，若把x1台投入第一种任务，则在本期结束时将有1/3x1台机器损坏报废，剩下的机器全部投入第二种任务，则有1/10的机器在期末损坏报废。如果干第一种任务时每台机器可获利润10，干第二种任务时每台机器可获利润7，问应如何分配使用机器以使四期的总利润最大（期末剩下的完好机器数量不限）五、求下图所示网络的最大流（弧旁的数字是容量，流量），并指出截集。(25分)七、（20分）某修理店只有一个修理工人，来修理的顾客到达次数服从普阿松分布，平均每小时4人。修理时间服从负指数分布，平均需6分钟。求：（1）修理店空闲的概率；（2）店内有3个顾客的概率；（3）店内至少有一个顾客的概率；（4）在店内顾客的平均数；（5）在店内的平均逗留时间；（6）等待服务的顾客平均数；（7）平均等待修理时间；（8）如果店内已有3个顾客，那么后来的顾客即不再排队，其他条件相同，求店内空闲的概率和店内顾客平均数。物流工程与管理方向考试运筹学的学习与方向1西南交大物流工程专业课管理运筹学2北京交大交通运输规划与管理运输与物流专业课管理运筹学3大连海事交通运输规划与管理专业课运筹学4哈工大土地资源管理专业课运筹学 7.西安建筑科技大学管理学院工程管理专业①101统考政治②201统考英语③303数学三④416技术经济学或417运筹学 4.东南大学土木学院建设与房地产系120100管理科学与工程 南开120100管理科学与工程①101政治②201英语③303数学三④885管理信息系统或886（商学院）运筹学_01信息系统与电子商务_02物流与供应链管理_03管理科学侧重数学建模和计算机应用，这两科难度较大。复试笔试科目：项目管理与工程造价或施工技术与组织设计或运筹学 上海交大：120100管理科学与工程研究方向：_01系统科学与系统工程_02管理科学与决策科学_03管理信息系统_04技术创新与管理_05工程管理与项目管理_06交通运输管理考试科目：①101政治②201英语③301数学一④816自动控制理论或840运筹学与概率统计或842信息系统分析与设计或845管理学 840运筹学与概率统计（线性规划、图论与网络、排队论、库存论、决策论）《运筹学》清华大学编写组编清华大学出版社1990《概率论与数理统计》（第二版）浙大编高等教育出版社1989 120100管理科学与工程①101政治理论②201英语③301数学一④863运筹学或893管理经济学意思就是说你可以从这两门中任选一门参加考试你可以选择考运筹学也可以选择管理经济学一般都会选择一门难度较低的或是自己学的比较好的参加初试东南大学120100管理科学与工程01国际工程管理02工程项目管理03房地产投资与管理04建筑业与建筑企业管理05建设项目环境管理与可持续发展①101政治理论②201英语③301数学一④926工程经济或972运筹学复试科目:539工程项目管理北大028)光华管理学院(120100)管理科学与工程(101)政治(201)英语(301)数学一(487)运筹学与管理信息系统北京交通大学2001年硕士研究生入学考试试卷考试科目：管理运筹学一、（30分）某厂下一个计划期准备利用设备甲、乙、丙生产A，B，C三种产品，生产单位产品所需的设备台时有关数据如下：（1）如何安排生产，使该厂生产利润最大？最大利润是多少？（2）如果可利用其它厂的设备来扩大生产，每月可租用300台设备甲，租金为8.4万，问是否要租借？（3）如果A产品对各种设备的生产消耗变为（8，2，5）T，是否要生产A产品？ 产品设备 A B C 设备可利用台时（小时） 甲 8 2 10 300 乙 10 5 5 400 丙 2 13 5 390 利润 2.5 2 4二、（13分）由A、B两煤矿供应甲、乙、丙三个城市煤炭，各煤炭可供应量、各城市需要量及各煤矿到各城市间运价（元/吨）如下表：由于供不应求，经研究平衡决定，甲城市供应量可减少0~30万吨，乙城市需求量需全部满足，试求将甲乙两矿煤炭全部分配出去，满足上述条件又使总费用为最低的调运方案。 城市煤矿 甲 乙 丙 供应量（万吨） A 15 18 22 400 B 21 25 16 450 需要量（万吨） 320 250 350 8三、（15分）（1）对整数规划问题去掉变量为整数的约束，引入松弛变量x3,x4，并用单纯形法求解，可得最终单纯形表如下：则下面哪个式子是这个问题的割平面方程。 cj 1 1 0 0 CB XB b x1 x2 x3 x4 1 x1 3/4 1 0 -1/4 1/4 1 x2 7/4 0 1 3/4 1/4（2）某公司有可利用资金M万元，拟在S1，S2，…，S10处增建5个分店。经市场调研和预测，增建分店时要考虑以下几点：①第i处建分店的投资为Ci万元；②S1，S2，S3三处至多建两个分店；③S4，S5两处至少建一个分店；④S6，S7，S8三处中应建一个分店；试建立满足上述条件且总投资额为最小的整数规划模型。四、（12分）某工厂为职工设立了昼夜24小时都能看病的医疗室（按单服务台处理）。医疗室有两个供病人等候看病的椅子，病人到达医疗室如没有座位就依次站立等候。病人按泊松流到达，平均每小时到达3人，医生给病人看病时间服从负指数分布，平均给每个病人看病时间为12分钟。因病人看病给工厂造成的损失为20元。（1）求病人到达医疗室需要站立等候的概率。（2）平均每个病人在医疗室要等待多长时间。（3）工厂每天损失的期望值。五、（15分）从两口油井v1，v2经管道将原油输至脱水处理厂v5，中间经过v3,v4两个泵站。下图中弧旁的数字为各管道的最大通过能力（吨/小时）。求从油井每小时能输送到处理厂的最大流量。（写出求解的过程和结果）201010304020六、（15分）某公司总部有一部货车沿着公路给4个零售店卸下5箱货物，如果各零售店出售该货物所得利润如下表所示。（1）求使总利润最大的动态规划递推方程。 零售店箱数 1 2 3 4 0 0 0 0 0 1 4 3 3 4 2 5 4 5 5 3 6 6 7 6 4 7 8 8 6 5 7 9 8 6（2）如果用逆推法，阶段k表示第k个零售店，pk(xk)表示给零售店k得到xk箱货物的利润，fk(sk)表示第k店到第n(n=4)店的总利润,则k=4，k=3时动态规划求解过程如下表给出，试完成后面各阶段的动态规划求解过程。 x4s4 p4(x4) x4* 0 1 2 3 4 5 f4(s4) 0 0 0 0 1 4 4 1 2 5 5 2 3 6 6 3 4 6 6 4 5 6 6 5 x3s3 p3(x3)+f4(s4) x3* 0 1 2 3 4 5 f3(s3) 0 0 0 0 1 0+4 3+0 4 0 2 0+5 3+4 5+0 7 1 3 0+6 3+5 5+4 7+0 9 2 4 0+6 3+6 5+5 7+4 8+0 11 3 5 0+6 3+6 5+6 7+5 8+4 8+0 12 3,4北京交通大学2000年硕士研究生入学考试试卷考试科目：管理运筹学一、是非选择题（回答是与否，每题1.5分，共15分）1.线性规划问题的基本类型是“max”类型。2.线性规划问题的每一个基可行解对应可行域的一个顶点。3.已知y1*为线性规划对偶最优解的一个分量，说明在原最优生产计划中第一种资源已完全耗尽。4.因为资源的影子价格不是市场价格，所以它们两者不可能相等。5.当一个运输问题的调运方案存在负检验数时，它不可能是最优方案。6.整数规划解的目标值一般不优于其相应线性规划问题的最优值。7.存储论研究的中心问题是供应和需求问题。8.经济订货批量是数量最低的订货批量。9.任何图中，次为奇数的顶点必为2的倍数。10.图G=（V，E），其边数等于顶点数减1，则G是树。二、已知某生产计划问题的线性规划模型及求解的最终单纯形表：1.用图解法求原问题的最优解。2.写出其对偶问题，并用对偶单纯形法求对偶问题的最优解。3.对目标函数c1=3进行灵敏度分析。4.若约束常数b2=8减少1个单位，求新的最优解。（25分） x1 x2 x3 x4 x5 -20 0 0 -2 -1 0 x5 1 0 0 1 -1 1 x1 4 1 0 2 -1 0 x2 2 0 1 -1 1 0三、某公司计划从bi(i=1,2,…,8)等8个可供选择的城市中决策筹建4个分公司，相应的建设费为Ci(i=1,2,…,8)并规定：①b1，b2，b8最多选一个；②b3，b4，b5最少选一个；③b6，b7，b8最多只能选择两个。试建立该问题的数学模型。（10分）四、现有四个水泥产地发运15（万吨）水泥供三个工地使用，需要量是19（万吨），各产地及工地供销量以及运送1吨水泥运价（元）如表所示：设1.B1工地需要供给3万吨优质水泥；2.B2工地可取得当地2万吨水泥补充使用；3.B3工地可使用低标号水泥；4.A3水泥厂可生产3万吨优质水泥，剩余生产的是一般水泥，A4生产低标号水泥，其他产地生产一般水泥。试求在满足以上条件下，使运费达到最少的运输方案。（20分） 销地产地 B1 B2 B3 供 A1 2 10 7 2 A2 11 3 8 3 A3 3 2 1 4 A4 4 9 2 6 需 7 5 7五、用Dijkstra算法求v1到各点的最短路。（15分）六、某厂可同时采购I，II，III三种元件，年需要量分别为DI=2000，DII=4000，DIII=5000，每个年存储费分别为C1I=0.1，C1II=0.08，C1III=0.15，每次采购订货费C2=150元，求共同的订购周期和各自的经济订购批量，并计算三种元件联合采购比分别单独采购全年节省的费用。（15分）北京交通大学2003年硕士研究生入学考试试卷考试科目：管理运筹学一、已知线性规划问题（35分） 试用单纯形法求最优解。 写出原问题的对偶问题，并根据对偶理论，直接求出对偶问题的最优解。 如果增加一个新的变量x6(x6>0)，，c6=7，原问题的最优解有何变化。 如果添加一个新的约束x1+2x2+x3≤4，原问题的最优解有何变化。二、有三家企业A1，A2，A3生产同一种产品供应三个用户B1，B2，B3，A1企业至少要发出60个单位的产品，它最多能生产110个单位产品；A2企业必须发出70个单位产品；A3企业至少发出40个单位产品。各用户的需求量分别为100，40和60个单位，生产企业到用户的单位运价见下表。用表上作业法求该运输问题的最优解。（20分） 用户生产企业 B1 B2 B3 生产量（万吨） A1 2 4 3 不小于60单位，同时不大于110单位 A2 1 5 6 70单位 A3 3 2 4 不小于40单位 需要量（万吨） 100 40 60三、甲、乙、丙、丁和戊五条生产线去生产A、B、C、D和E五种产品。已知每条生产线生产各种产品所产生的效益如下表所示。试确定总效益为最大的指派方案。（20分） A B C D E 甲 3 8 2 10 3 乙 8 7 2 9 7 丙 6 4 2 7 5 丁 8 4 2 3 5 戊 9 10 6 9 10四、求下图从vs到vt的最小费用最大流。图中弧旁的数字为（费用，容量）（20分）○○○○○（5，6）（3，4）（1，1）（2，3）（9，2）（4，1）（3，2）（4，10）vsvtv1v2v3五、某市为方便居民就医，拟在新建的居民小区建设若干所医院。已知备选地址代码及其所能覆盖的居民小区编号如下标，试问，为覆盖所有小区，至少应建多少所学校。列出模型，不用求解。（15分） 备选建设地址代码 覆盖的居民小区编号 ① 1，2，3，4，6，7，8 ② 1，2，8，9 ③ 5，6，11 ④ 6，7，8，9，10，11六、某汽车检测站有一条检测线，要求做检测的车辆按普阿松流到达，平均每小时6辆。每辆车的检测时间服从负指数分布，平均每辆10分钟。用于等待检测的停车泊位有5个，当无停车泊位时，来检测的车辆自动离去，到其他检测站检测。试计算：1.某车辆一到达就可以进行检测的概率；2.等待检测的平均车数；3.每辆车在检测线上逗留的期望时间；4.在可能到来的车辆中，有百分之几不等待离开；5.如果车辆因停车泊位被占用而离去，每辆车损失a元，求每小时因车辆离去而造成的损失。（20分）七、设某台新设备的年效益及年均维修费、更新净费用如下表。试确定今后4年内的更新策略，使总收益最大。（要求写出状态转移方程和递推）。设折扣因子为1，单位万元。（20分） 役龄项目 0 1 2 3 4 5 效益rk(t) 5 4.5 4 3.75 3 2.5 维修费uk(t) 0.5 1 1.5 2 2.5 3 更新费ck(t) 0.5 1.5 2.2 2.5 3 3.5 x3s3 p3(x3)+f4(s4) x3* 0 1 2 3 4 5 f3(s3) 0 0 0 0 1 0+4 3+0 4 0 2 0+5 3+4 5+0 7 1 3 0+6 3+5 5+4 7+0 9 2 4 0+6 3+6 5+5 7+4 8+0 11 3 5 0+6 3+6 5+6 7+5 8+4 8+0 12 3,4北京交通大学2000年硕士研究生入学考试试卷考试科目：管理运筹学一、是非选择题（回答是与否，每题1.5分，共15分）1.线性规划问题的基本类型是“max”类型。2.线性规划问题的每一个基可行解对应可行域的一个顶点。3.已知y1*为线性规划对偶最优解的一个分量，说明在原最优生产计划中第一种资源已完全耗尽。4.因为资源的影子价格不是市场价格，所以它们两者不可能相等。5.当一个运输问题的调运方案存在负检验数时，它不可能是最优方案。6.整数规划解的目标值一般不优于其相应线性规划问题的最优值。7.存储论研究的中心问题是供应和需求问题。8.经济订货批量是数量最低的订货批量。9.任何图中，次为奇数的顶点必为2的倍数。10.图G=（V，E），其边数等于顶点数减1，则G是树。二、已知某生产计划问题的线性规划模型及求解的最终单纯形表：1.用图解法求原问题的最优解。2.写出其对偶问题，并用对偶单纯形法求对偶问题的最优解。3.对目标函数c1=3进行灵敏度分析。4.若约束常数b2=8减少1个单位，求新的最优解。（25分） x1 x2 x3 x4 x5 -20 0 0 -2 -1 0 x5 1 0 0 1 -1 1 x1 4 1 0 2 -1 0 x2 2 0 1 -1 1 0三、某公司计划从bi(i=1,2,…,8)等8个可供选择的城市中决策筹建4个分公司，相应的建设费为Ci(i=1,2,…,8)并规定：①b1，b2，b8最多选一个；②b3，b4，b5最少选一个；③b6，b7，b8最多只能选择两个。试建立该问题的数学模型。（10分）四、现有四个水泥产地发运15（万吨）水泥供三个工地使用，需要量是19（万吨），各产地及工地供销量以及运送1吨水泥运价（元）如表所示：设1.B1工地需要供给3万吨优质水泥；2.B2工地可取得当地2万吨水泥补充使用；3.B3工地可使用低标号水泥；4.A3水泥厂可生产3万吨优质水泥，剩余生产的是一般水泥，A4生产低标号水泥，其他产地生产一般水泥。试求在满足以上条件下，使运费达到最少的运输方案。（20分） 销地产地 B1 B2 B3 供 A1 2 10 7 2 A2 11 3 8 3 A3 3 2 1 4 A4 4 9 2 6 需 7 5 7五、用Dijkstra算法求v1到各点的最短路。（15分）六、某厂可同时采购I，II，III三种元件，年需要量分别为DI=2000，DII=4000，DIII=5000，每个年存储费分别为C1I=0.1，C1II=0.08，C1III=0.15，每次采购订货费C2=150元，求共同的订购周期和各自的经济订购批量，并计算三种元件联合采购比分别单独采购全年节省的费用。（15分）华中科技大学2007年考研运筹学试题适用专业:管理科学与工程、工商管理等一、（20分）已知一个线性规划问题的灵敏度分析如下：变动单元格 单元格 变量名 最终值 减少成本 目标系数 允许增加值 允许减少值 $B$ x1 0 -5 3 5 1E+30 $C$ x2 18.7 0 2 7 14 $D$ x3 5.14 0 6 1E+30 3.5约束条件（1）当x1的目标系数增加2单位，同时x2的目标系数减少5单位时最优解是否改变？（2）当第一约束的右端项减少2单位，同时第二约束的右端增加3单位，第三约束的右端项增加2单位时目标值改变多少？（3）第三约束是起作用约束？第二约束的影子价格为-2表示什么意义？ 单元格 名称 最终值 影子价格 右端值 允许增加值 允许减少值 $E$ 第一约束 66 2 66 1E+30 13.33333 $E$ 第二约束 32 -2 32 12 65 $E$ 第三约束 47.42 0 36 11.42 1E+30二、（20分）已知线性规划（1）填空完成上面单纯形表，并求其对偶问题的最优解。（2）求出C2和C3的值，并确定C3增加多少时，线性规划有无穷多个最优解。的最优单纯形表 CB XB b x1 x2 x3 x4 x5 x6 x2 1 1/3 0 x5 0 -2/3 0 x6 0 -2 -CBB-1b -40/3 0 -1/2 0 0三、求解线性规划四、（10分）某人求解某平衡运输问题，得到该问题的最优运输方案和最优运费，然后将某一产地的产量增加20单位，同时将另一销地的销量增加20单位，其他数据不变，结果最优运费在运量增加后反而下降，请解释为什么会发生这种现象？西北工业大学复试大纲 《运筹学》考试大纲 　　一、考试内容 　　1.线性规划与单纯形方法：线性规划的基本概念；线性规划的基本理论；单纯形方法；线性规划应用举例。 　　2.线性规划的对偶理论及其应用：线性规划的对偶问题；线性规划的对偶理论；对偶解的经济解释；对偶单纯形方法；灵敏度分析。 　　3.运输问题：运输问题的数学模型；表上作业法；产销不平衡的运输问题。 　　4.目标规划：多目标线性规划问题；目标规划模型及其求解方法；目标规划的灵敏度分析；应用举例。 　　5.整数规划：整数规划问题的提出；求解整数规划的方法；整数规划应用举例；0-1型整数规划；指派问题。 　　6.动态规划：动态规划的基本概念和方法；动态规划的基本原理；动态规划应用举例。 　　7.图与网络分析：图的基本概念；最小生成树；最短路问题；中国邮递员问题。 　　8.网络计划方法：计划网络图；网络分析方法。 　　二、参考书目 　　1.钱迪颂，《运筹学》，清华大学出版社，1990年。 　　2.牛映武，《运筹学》，西安交通大学出版社，1994年。 x3s3 p3(x3)+f4(s4) x3* 0 1 2 3 4 5 f3(s3) 0 0 0 0 1 0+4 3+0 4 0 2 0+5 3+4 5+0 7 1 3 0+6 3+5 5+4 7+0 9 2 4 0+6 3+6 5+5 7+4 8+0 11 3 5 0+6 3+6 5+6 7+5 8+4 8+0 12 3,4天津大学 　　课程名称：运筹学基础 　 　　二、考试的内容及比例（150分） 　　1.线性规划 　　模型、图解法、单纯形法原理、单纯形表计算、对偶理论、灵敏度分析、运输问题、线性目标规划和线性整数规划模型。 　　2.动态规划 　　基本概念与基本方程、离散型与连续型问题的基本解法、主要应用类型。 　　3.图与网络分析 　　最小部分（支撑）树、最短路、最大流、网络方法在计划中的应用（包括CPM、PERT、资源与费用优化等）。 　　4.排队论 　　基本概念、M/M/1系统、M/M/c系统 　　5.存储论 　　基本概念、确定型与随机型存储模型。 　　6.决策论 　　基本概念、风险型决策问题：先验分析（期望值准则、效用期望值准则、完全信息期望值、决策树）、后验分析、预后分析。 　　7.随机模拟 　　基本概念、系统的模拟。 　　8.对策论 　　基本概念、矩阵对策的最优纯策略、混合策略。 　　其中第1-3部分约占60%，第4-8部分约占40%.此外，考生还应对运筹学在管理中的应用方法等有一定的了解。 　　三、试卷题型及比例 　　1.基本概念、基本理论：填空、简答、选择。 　　2.基本理论和方法的应用：计算题、证明题、综合应用题。西南交通大学2002年硕士研究生招生入学考试试卷运筹学试题一、给定线性规划，讨论a取何值时，线性规划有可行解并求最优解和最优值。二、设一线性规划问题为其最优单纯形表为在下述每一种情况下进行灵敏度分析并求出最优解。（1）目标函数变为maxz=2x1+3x2+x3(2)约束条件右端项由变为（3）增加一个约束条件 cj 2 -7 1 0 0 b CB XB x1 x2 x3 x4 x5 2 x1 1 1 1 1 0 6 0 x5 0 3 1 1 1 10 cj-zj 0 -9 -1 -2 0三、在下面的运输问题中，假定对销地1，2和3未满足需求量的单位惩罚为成本是5，3和2，求最优解。 销产 1 2 3 ai 1 5 1 7 10 2 6 4 6 80 3 3 2 5 15 bj 75 20 50四、现有3辆卡车需要调到3个不同的目的地，各辆卡车的运行成本如下表，试求使总成本最低的调运方案。 目的地车辆 v1 v2 v3 A 46 62 39 B 24 31 49 C 29 38 56五、某住宅建筑公司拟建甲、乙、丙三类住宅出售。已知甲类住宅楼每栋耗资100万元，售价200万元；乙类住宅楼每栋耗资60万元，售价110万元；丙类住宅楼每栋耗资30万元，售价70万元。由于市政当局的限制，建设每栋住宅楼不得多于三栋。该公司可利用资金为350万元。问应如何拟定建造计划，方能使该公司的售房收入最大？六、下图是一个石油输送管道网络图，x1,x2为油井，y1,y2为油库，弧旁的数字为管道的输送能力及初始流，试确定管道系统的最大输送能力。x1x2y2y1v3v2v1x4(10,5)(8,3)(20,8)(20,5)(25,12)(12,12)(15,15)(30,14)(10,4)(15,6)(10,10)(15,10)(10,4)(10,8)