当前位置：文档之家 › 运筹学》综合练习题

运筹学》综合练习题

  • 格式：docx
  • 大小：28.27 KB
  • 文档页数：9

《运筹学》综合练习题 第一章 线性规划及单纯形法 1、教材43页——44页1.1题 2、教材44页1.4题 3、教材45页1.8题 4、教材46页1.13题 5、教材46页1.14题 6、补充：判断下述说法是否正确  LP问题的可行域是凸集。  LP问题的基本可行解对应可行域的顶点。  LP问题的最优解一定是可行域的顶点,可行域的顶点也一定是最优解。  若LP 问题有两个最优解,则它一定有无穷多个最优解.  求解LP问题时,对取值无约束的自由变量，通常令jjjxxx,其中∶

0jjxx,在用单纯形法求得的最优解中,不可能同时出现0jjxx.

 当用两阶段法求解带有大M的LP模型时，若第一阶段的最优目标函数值

为零，则可断言原LP模型一定有最优解。 7、补充：建立模型 （1）某采油区已建有n个计量站B1，B2…Bn，各站目前尚未被利用的能力为b1，b2…bn（吨液量/日）。为适应油田开发的需要，规划在该油区打m口调整井A1，A2…Am，且这些井的位置已经确定。根据预测，调整井的产量分别为a1，a2…am（吨液量/日）。考虑到原有计量站富余的能力，决定不另建新站，而用原有老站分工管辖调整井。按规划要求，每口井只能属于一个计量站。假定Ai到Bj的距离dij已知，试确定各调整井与计量站的关系，使新建集输管线总长度最短。 （2）靠近某河流有两个化工厂(见附图)，流经第一个工厂的河流流量是每天500万立方米；在两个工厂之间有一条流量为每天200万立方米的支流。第一个工厂每天排放工业污水2万立方米；第二个工厂每天排放工业污水1.4万立方米 。从第一个工厂排出的污水流到第二个工厂之前，有20%可自然净化。根据环保要求，河流中工业污水的含量不应大于0.2%，若这两个工厂都各自处理一部分污水，第一个工厂的处理成本是1000元/万立方米，第二个工厂的处理成本是800元/万立方米。试问在满足环保要求的条件下，每厂各应处理多少污水，才能使总的污水处理费用为最小?建立线性规划模型。

第二章 线性规划的对偶理论与灵敏度分析 1、教材77—78页2.1，2.2，2.3题 2、教材79—80页2.10题： ①写出其对偶问题 ②用单纯形法求解原问题及对偶问题 ③比较②中原问题及对偶问题最优解的关系，掌握当求解原问题/对偶问题后，如何辨识对偶问题/原问题的最优解 3、教材80页2.12、2.14题 4、设有LP模型如下：

试用矩阵语言，描述其最优性检验条件为：0011BCABCCBB 5、写出二题线性规划的对偶规划（10分） 6、某公司计划制造Ⅰ、Ⅱ两种家电产品，已知各制造一件时分别占用的设备A、B

工厂1 工厂2 的台时、调试时间及每天可用的设备能力和单件产品的获利情况如下表： Ⅰ Ⅱ 每天可用能力

设备A（小时） 0 5 15 设备B（小时） 6 2 24 调试工序（小时） 1 1 5

利润（元） 2 1 ①.建立获利最大的线性规划模型并求解（可不考虑整数要求，10分） ②.该公司计划推出新型号的家电产品Ⅲ，生产一件所需设备A、B及调试工序的时间分别为3、4、2小时，该产品单件获利3元，试判断且仅判断该产品是否值得生产？（10分） ③.对第一问中获利最大的线性规划模型建立其对偶规划模型，并回答其最优解和说明该公司的短缺资源是哪些？（10分） 第三章 运输问题 1、教材107页3.1、3.5题 2、教材103页例题6 3、教材109页3.10，3.11题 4、补充：一个有退化基可行解的运输问题 某运输问题的运价及各产地、销地的数据如下表: B1 B2 B3 B4 供应

A1 3 11 4 5 7 A2 7 7 3 8 4 A3 1 2 10 6 9 需求 3 6 5 6 20

试确定总运费最低的运输方案。（注意：本题存在退化的基本可行解） 第四章 目标规划 1、“目标规划不会出现无解”的结论对否？ 2、用图解法及单纯形法求解教材125页4.2题 3、教材114页例3及116页例5. 第五章 整数规划 1、判断说法是否正确： ①分枝定界求解整数规划时,分枝问题的最优解不会优于原(上一级)问题的最优解. ②整数规划中，割平面的构造应满足能割掉松弛问题的最优解，但不割掉原问题的可行解。 2、教材154—155页5.4，5.5题 3、教材155页5.6，5.7题 4、教材156—157页5.13，5.14题 5、对教材11页例1建立其整数规划模型，并用分支定界法与割平面求解。 第七章 动态规划 1、判断结论正误 ①动态规划的最优性原理保证了从某一状态开始的未来决策独立于先前已作出的决策 ②对于同一个动态规划问题，逆序法与顺序法的解不一样 2、教材237页7.1，7.2题 3、某企业有某种高效率设备3 台，拟分配给所属甲、乙、丙车间，各车间得到设备后，获利情况如下表，试建立最优分配方案（20分）

工厂 获利 甲 乙 丙 设备台数

0 0 0 0 1 3 5 4 2 7 10 6 3 9 11 11 4、教材238页7.6题 5、某企业今有3个可供选择的投资项目，其收益所得及所需投资额如下表，由于可支配资金只有10万元，试进行项目选择。 项目编号 1 2 3 收益（万元） 4 5 6 投资额（万元） 3 4 5 6、石油公司所属某仪器厂按合同向勘探单位提供地震勘探仪器，在计划年度内各季度的合同交货量、该厂的生产能力、生产成本及成品库中的维护与保管成本数据如下表，试建立总成本最低的生产计划模型并用表上作业法求解一步。 季度 合同交货（台） 生产能力（台） 生产成本（千元/台） 保管成本（千元/台季） 1 10 25 103 1.5 2 15 35 111 1.5 3 25 30 110 1.5 4 20 10 113 1.5 第八章 图与网络分析 本章只考察——最短路问题与最大流问题 1、教材264页例12 2、下图是一个交通网络，每条边（弧）的容量及一个可行流如下表所示，试求这个网络的最大流。 边 容量 边 容量 s--1 5 5 2--6 2 2 s--2 4 2 3--6 2 2 s--3 3 2 4--t 4 2 1--4 5 2 5--t 3 3 1--5 3 3 6--t 5 4 2--5 3 0

3、下图为一运输网络，试安排其流量为7的最小费用流。

图中各边的容量及费用如下表： 边 容量 单位流费用 边 容量 单位流费用 1——2 10 4 3——2 5 2 1——3 8 1 3——4 10 3 2——4 2 6 4——5 4 2

1 2 3 4 5 s 1 2 3 4 5 6 t 2——5 7 1 第九章 网络计划 1、判断说法正误 ①PERT计算中，总时差是线路上的时差，可以串用，但单时差是工序的时差，不能串用 ②在PERT计算中，将最早节点时刻等于最迟节点时刻、且满足0)(),()(itjitjtEL节点连接而成的线路是关键线路

2、教材313页9.2题 3、某工程的PERT数据如下表： ①画出网络图并予节点以正确的编号 ②计算最早、最迟节点时刻 工序 工序时间 先行工序 A 3 - B 4 A C 5 A D 7 B C E 8 B C F 9 C G 4 C H 2 D E I 3 G J 2 H I ③据所画网络图填写计算下表 i j 作业代号 t es ef ls lf tf 关键工序

4、考虑由A、B、……H等八道工序组成的产品加工任务，这些工序的先后顺序和加工的时间如下表所示： 工序 紧前工序 工作时间/天 A \ 10 B \ 5 C B 3 D A、C 3 E A、C 5 F D 6 G E 5 H F、G 5 要求： 1、绘制所给工序的网络图； 2、计算各节点的最早与最迟节点时刻； 第十章 排队论 本章不做重点要求 1、在一个随机服务系统中，当其输入过程是一普阿松流时，即有

tnentntNP

!，则同一时间区间内，相继两名顾客到达的时间间隔是相互独立且服从参数为λ的负指数分布，即有tetXp说法正确否？ 第十一章 存贮论 本章公式记忆太多，不做重点要求 1、分析建立模型 不允许缺货、补充时间无限短的确定型存储模型的假设条件是： 不允许缺货 补充时间无限短 需求是连续的且需求速率Ｒ为常数 单位物资单位时间的存储费用Ｃ1是常数 每次定购费Ｃ3（不考虑货款）是常数 试：（１）画出存储量变化曲线 （2）分析费用，建立总平均费用最低的订货模型（订货周期、订货量） 2、参看弄懂教材362页：“模型二，允许缺货，补充时间较长”；能够根据其他模型条件，从而由模型二得到其他模型

合集下载

运筹学上机练习题集

运筹学上机练习题集

练习题1、各矿与各市之间的运输价格如下表示：问应如何调运，才能既满足城市用煤需要，又使运输的总费用为最少？2、某农场要新买一批拖拉机以完成每年三季的工作量：春种330公顷，夏管130公顷，秋收470公顷，可供选择的拖拉机型号、单台投资额及工作能力如下表所示。

Min 5000x1+4500x2+4400x3+5200x430x1+29x2+32x3+31x4>=330……3、某航空公司的一架波音737—300客机的航线为：广州——上海——大连，飞机早上从广州飞往大连，中途停在上海，可容纳112个座位。

错误！未找到引用源。

说明了该客机的航线状况。

该航空公司为此客机制定了两种级别的机票：B级别和A级别机票。

错误！未找到引用源。

详细说明了该客机各旅程的两种级别机票的票价和需求预测情况。

应如何安排该客机各旅程的两种级别机票的数量以使总收益最大化。

MaxX1+X3+X4+X6<=122;4、有A1，A2，A3三个水泥厂，每天要把生产的水泥运往B1，B2两地。

各厂的产量、各地的需求量（销量）以及各厂地间的运价见下表。

问如何设计调运方案才能使总运费最少？56、设有三个化肥厂（A、B、C）供应四个地区（Ⅰ、Ⅱ、Ⅲ、Ⅳ）的农用化肥。

假定等量的花费在这些地区的使用效果相同。

各化肥厂年产量，各地区需要量及从各化肥厂到各地区运送单位化肥的运价表如下表所示。

试求出总的运费最节省的化肥调拨方案。

若规定每人专门负责一个语种的翻译工作，那么，试回答下列问题：（1）应如何指派，使总的翻译效率最高？（2）若甲不懂德文，乙不懂日文，其他数字不变，则应如何指派？8、某市六个新建单位之间的交通线路的长度（公里）如下表所示。

其中单位A距市煤气供应网最近，为1.5公里。

应如何铺设煤气管道使其总长最短。

9、在下面的网络中，试求：①各点到点t的最短路；②点s到各点的最短路。

-2410、求出下图所示的网络的最大流。

11、试确定关键路径和总工期。

运筹学练习题

运筹学练习题

一、填空题（每题1分,共5分；许圣兰得分:4分）1、已知线性规划maxZ=3x1+4x2+x3,x1+2x2+x3≤10,2x1+2x2+x3≤16,x1,x2,x3≥0的最优基为约束条件系数矩阵的第一、第二两列，则最优解(x1,x2)= (6,2) 。

√ +1分2、非基变量x j的系数为c j,对应的最终表的检验数为-2,则最优解不变时,c j的允许增量应满足(用不等式表示):Δc j <=2/cj 。

×!参考答案:<=23、已知非整数最优解中基变量x1=3.25，x1要求取整数，则添加分枝约束x1<=3和 x1>=4 。

√ +1分4、一个可行流为最大流的充要条件是存在一个截集使其截量等于网络流的流量。

√ +1分5、每隔相同时间t0进货一次且每次进货量都相等的存贮策略称为t0循环策略。

√ +1分-------------------------------------------------------------------------------------------------------------------------二、判断题（每题1分,共10分；许圣兰得分:9分）1、当你自己建立的 LP 模型无最优解时，一定是模型中存在矛盾的约束条件 (错误)√ +1分2、设X*是m in z = CX,AX≥b, X≥0的最优解，Y*是max w =Yb, YA≤C, Y≥0的最优解，则CX*=Y*b (正确)√ +1分3、整数规划的可行解集合是离散型集合 (正确)√ +1分4、若运输问题中的产量和销量为整数则其最优解也一定为整数。

(错误)√ +1分5、μ是一条增广链，则后向弧上满足流量f ≥0。

(错误)√ +1分6、指派问题一定有最优解 (正确)√ +1分7、 (s,S)策略是连续盘存，当存储量降到s时立即提出订货，订货量等于S (错误)√ +1分8、 LP 问题的基本可行解对应可行域的顶点。

《运筹学》习题集

《运筹学》习题集

第一章线性规划1．1将下述线性规划问题化成标准形式1)min z＝－3x1＋4x2－2x3＋5 x4－x2＋2x3－x4＝－24xst. x1＋x2－x3＋2 x4 ≤14－2x1＋3x2＋x3－x4 ≥ 2x1，x2，x3≥0，x4无约束2)min z ＝2x1－2x2＋3x3＋x2＋x3＝4－xst. －2x1＋x2－x3≤6x1≤0 ，x2≥0，x3无约束1．2用图解法求解LP问题，并指出问题具有唯一最优解、无穷多最优解、无界解还是无可行解。

1)min z＝2x1＋3x24x1＋6x2≥6st2x1＋2x2≥4x1，x2≥02)max z＝3x1＋2x22x1＋x2≤2st3x1＋4x2≥12x1，x2≥03)max z＝3x1＋5x26x1＋10x2≤120st5≤x1≤103≤x2≤84)max z＝5x1＋6x22x1－x2≥2st－2x1＋3x2≤2x1，x2≥01．3找出下述LP问题所有基解，指出哪些是基可行解，并确定最优解（1）min z＝5x1－2x2＋3x3＋2x4x1＋2x2＋3x3＋4x4＝7st2x1＋2x2＋x3 ＋2x4＝3x1，x2，x3，x4≥01．4 分别用图解法与单纯形法求解下列LP 问题，并对照指出最优解所对应的顶点。

1) maxz ＝10x 1＋5x 23x 1＋4x 2≤9 st 5x 1＋2x 2≤8 x 1，x 2≥02) maxz ＝2x 1＋x 2 3x 1＋5x 2≤15 st 6x 1＋2x 2≤24 x 1，x 2≥01．5 分别用大M 法与两阶段法求解下列LP 问题。

1) minz ＝2x 1＋3x 2＋x 3 x 1＋4x 2＋2x 3≥8 st 3x 1＋2x 2 ≥6 x 1，x 2 ，x 3≥02) max z ＝4x 1＋5x 2＋ x 3. 3x 1＋2x 2＋ x 3≥18 St. 2x 1＋ x 2 ≤4x 1＋ x 2－ x 3＝53) maxz ＝ 5x 1＋3x 2 +6x 3 x 1＋2x 2 －x 3 ≤ 18 st 2x 1＋x 2 －3 x 3 ≤ 16 x 1＋x 2 －x 3＝10 x 1，x 2 ，x 3≥01231231231231234)max 101512539561515.25,,0z x x x x x x x x x st x x x x x x =++++≤⎧⎪-++≤⎪⎨++≥⎪⎪≥⎩1．6《运筹学》习题集1.7某班有男生30人，女生20人，周日去植树。

运筹学练习题

运筹学练习题

运筹学练习题《运筹学》---数据、模型与决策练习题2010年9⽉⼀、线性规划：基本概念1、下⾯的表格总结了两种产品A和B的关键信息以及⽣产所需的资源Q, R, S：满⾜所有线性规划假设。

（1）在电⼦表格上为这⼀问题建⽴线性规划模型；（2）⽤代数⽅法建⽴⼀个相同的模型；（3）⽤图解法求解这个模型。

2、今天是幸运的⼀天，你得到了10000美元的奖⾦。

除了将4000美元⽤于交税和请客之外，你决定将剩余的6000美元⽤于投资。

两个朋友听到这个消息后邀请你成为两家不同公司的合伙⼈，每⼀个朋友介绍了⼀家。

这两个选择的每⼀个都将会花去你明年夏天的⼀些时间并且要花费⼀些资⾦。

在第⼀个朋友的公司中成为⼀个独资⼈要求投资5000美元并花费400⼩时，估计利润（不考虑时间价值）是4500美元。

第⼆个朋友的公司的相应数据为4000美元和500⼩时，估计利润为4500美元。

然⽽每⼀个朋友都允许你根据所好以任意⽐例投资。

如果你选择投资⼀定⽐例，上⾯所有给出的独资⼈的数据（资⾦投资、时间投资和利润）都将乘以⼀个相同的⽐例。

因为你正在寻找⼀个有意义的夏季⼯作（最多600⼩时），你决定以能够带来最⼤总估计利润的组合参与到⼀个或全部朋友的公司中。

你需要解决这个问题，找到最佳组合。

（1）为这⼀问题建⽴电⼦表格模型。

找出数据单元格、可变单元格、⽬标单元格，并且⽤SUMPRODUCT函数表⽰每⼀个输出单元格中的Excel等式。

（2）⽤代数⽅法建⽴⼀个同样的模型。

（3）分别⽤模型的代数形式和电⼦表格形式确定决策变量、⽬标函数、⾮负约束、函数约束和参数。

（4）使⽤图解法求解这个模型。

你的总期望利润是多少3、伟特制窗（Whitt Window）公司是⼀个只有三个雇员的公司，⽣产两种⼿⼯窗户：⽊框窗户和铝框窗户。

公司每⽣产⼀个⽊框窗户可以获利60美元，⼀个铝框窗户可以获利30美元。

Doug制作⽊框窗户，每天可以制作6扇。

Linda制作铝框窗户，每天可以制作4扇。