运筹试题

一、回答下面问题(每小题3分)

1.在单纯形法计算中,如果不按最小比值规则确定换基变量,则在下一个解中一定会出现。 2. 原问题无界时，其对偶问题，反之，当对偶问题无可行解时，原问题。

3．已知y0为线性规划的对偶问题的最优解，若y0>0，说明在最优生产计划中对应的资源 。

4．已知y0为线性规划的对偶问题的最优解，若y0=0，说明在最优生产计划中对应的资源 。

5．已知线形规划问题的原问题有无穷多最优解，则其对偶问题的最优解一定是 。

6．m个产地n个销地的产销平衡运输问题的模型其决策变量的个数是个；基变量的个数是个；决策变量的系数列向量的特点是。

7．用位势法求解运输问题，位势的含义是；行位势与列位势中有一个的取值是任意的，这是因为。

8.用割平面法求解整数规划，割平面割去了；但未割去 。

9．按教材中的符号写出最大流问题的数学模型。 10．什么是截集，何谓最小截集？ 二、（10分）

下表是用单纯形法计算到某一步的表格，已知该线性规划的目标函数值为z=14 表1

cj x3 x1 σj 2 a x1 c d b x2 0 e -1 x3 1 0 f x4 1/5 1 g

（1） 求a—g的值；（8分）

（2） 表中给出的解是否为最优解。（2分） 三、（每小题6分共12分）

车间为全厂生产一种零件，其生产准备费是100元，存贮费是0.05元／天·个，需求量

为每天30个，而且要保证供应。

（1） 设车间生产所需零件的时间很短（即看成瞬时供应）； （2） 设车间生产零件的生产率是50个／天。

要求在（1）（2）条件下的最优生产批量Q*，生产间隔期t*和每天的总费用C*。 四、（18分）

某公司下属甲、乙两个厂，有A原料360斤，B原料640斤。甲厂用A、B两种原料生产x1,x2两种产品，乙厂也用A、B两种原料生产x3,x4两种产品。每种单位产品所消耗各种原料的数量及产值、分配等如下

工厂 产品 原料 A B 甲 x1 x2 8 4 6 10 4 3 分配原料 160 330 乙 x3 x4 5 8 10 4 3 4 分配原料 200 310 产值（百元）

1． 求各厂最优生产计划；（12分）

2． 问公司能否制定新的资源分配方案使产值更高？（6分） 五、（10分）

已知有六个村庄，相互间道路的距离如图所示，已知各村庄的小学生数为：A村50人，B村40人，C村40人，D村60人，E村50人，F村90人。现六村决定合建一所小学，问小学应建在哪村，才能使学生上学所走的总路最短？程

六、（8分）

A、B、C、D、E、F分别代表陆地和岛屿，1、2、3??14表示桥梁及其编号。若河两岸分别敌对的双方部队占领，问至少应切几座桥梁（具体指出编号）才能达到阻止对方部队过河的目的，试用图论方法进行分析。（提示：以陆地为点，桥梁为弧，两点之间的桥梁

数为弧的容量。） 七、（12分）

设有三个化肥厂供应四个地区的农用化肥。各化肥的年产量，各地区的需求量，化肥的运价如下表所示，请写出产销平衡运输表。

A1 A2 A3 最低要求 最高要求

B1 16 12 19 30 45 B2 13 14 21 70 70 B3 22 18 23 0 30 B4 16 15 ? 10 不限 产量 50 60 50 运筹学试卷（2）

一、填空（15×2分）

1、在线性规划问题的约束方程AX=b,X≥0中，对于选定的基B，令非基变量XN=0，得到的解X=；若，则称此基本解为基本可行解；若，则称此基本可行解为退化的解；若，则此基可行解为最优解。

2、用对偶单纯形法求解线性规划问题时，根据b r确定xr为出基变量；根据最小比值法则θ=，确定x k为进基变量。

3、在单纯形法的相邻两次迭代中，迭代前的可行基B和迭代后的可行基系：

-1

的逆矩阵存在关

= ErkB-1其中Erk=。

4、已知y*为某线形规划问题的对偶问题的最优解，若y*>0，说明在最优化生产计划中对应的资源。

5、平衡运输问题（m个产地，n个销地）的基可行解中基变量共有个；其中决策变量xij所对应的列向量pij=.。

6、对于Max 型整数规划问题，若其松弛问题的最优单纯形表中有一行数据为：

XB b x1 x2 x3 x4 x2 3/4 0 1 7/4 -11/4

则对应的割平面方程为。

7、用匈牙利法解分配问题时，当 则找到了分配问题的最优解；称此时独立零元素对应的效益矩阵为。

8、将网络D=（V，A，C）的顶点集合V分割成两个非空集合V1和V1，使VS∈V1，Vt∈V1，则弧集成为分割VS和Vt的截集；称为截集的容量。 二、问答题（2×5分）

1．材写出目标规划的一般模型； 2．试叙动态规划的最优性原理。

三、已知某线性规划问题的目标函数为max=5x1+3x2,约束形式为“≤”。设x3,x4为松弛变

量，用单纯形法计算是某一步的表格如下所示： （15分）

Cj CB 0 5 -Z （1） 求a~g的值；

（2） 表中给出的解是否为最优解，并求出最优解。

四、已知某线性规划问题，其初始及最优单纯形表如下：（15分）

Cj CB 0 0 0 XB x3 x4 x5 σj 最优解表

Cj CB XB B 1 2 0 0 0 x1 x2 x3 x4 x5 b 12 9 8 1 2 0 0 0 X1 x2 x3 x4 x5 2 2 1 0 0 3 0 0 1 1 0 2 0 0 1 1 2 0 0 0 XB x3 x1 b 5 3 0 0 x1 x2 x3 x4 c 0 1 1/5 d e 0 1 b -1 f g -10 1 0 2 x1 x4 x2 σj 2 3 4 1 0 1/2 0 -1/2 0 0 -3/2 1 3/2 0 1 0 0 1/2 0 0 -1/2 0 -1/2 (1)求出对偶问题的最优解; (2)求C1的变化范围,使最优基不变; (3)如果b1由12变为16,求最优解.

五、种机器可以在高低两种不同的负荷下生产,高负荷生产时,产品的年产量g与投资的机器数量x的关系为:g(x)=8x,这时机器的年完好率a=0.7;在低负荷下生产时产品的年产量h和投入的机器数量y的关系为:h(x)=5y,这时机器的年完好率b=0.7。假定开始生产时的完好机器数量s1=1000台，试制定一个5年计划，确定每年投入高、低两种负荷下生产的完好机器数量，使5年内产品的总产品量最大，并且5年末完好的机器数量是500台。 （1） 写出阶段变量、状态变量、决策变量；（6分） （2） 写出第k阶段的决策集合与状态转移方程；（9分） （3） 写出递推方程，并规范化求解。（选作10分）

五、 如图所示是某地区交通运输示意图，s是起点t终点，弧旁数字为cij(fij)。（15分）

（1）写出此交通运输规划的线性规划数学模型； （2）用标号法求出从s到t最大流及其流量； （3）写出该网络的最小割集。

运筹学试卷(3)

一、填空(11×3分)

1、在线性规划问题的约束方程AX=b,X≥0中，对于选定的基B，令非基变量XN=0，得到的解X=；若，则称此基本解为基本可行解；若，则称此基本可行解为退化的解。

2、用单纯形法求解线性规划问题的迭代步骤中，根据σK=确定xk为进基变量；根据最小比值法则=，确定xr为出基变量。

3、平衡运输问题（m个产地，n个销地）的基可行解中基变量共有个。 4、对于Max型整数规划问题，若其松弛问题的最优单纯形表中有一行数据为：

XB x2 b 3/4 x1 0 x 1 x 7/4 x -11/4 则对应的割平面方程为 。

5、用匈牙利法解分配问题时，当 则找到了分配问题的最优解；称此时独立零元素对应的效益矩阵为 。 6、将网络D=(V,A,C)的顶点集合V分割成两个非空集合V1和集成为分割VS和Vt的截集；称为截集的容量。 二、单项选择题（3×5分）

1、含有两个变量的线性规划问题若有可行解，则可行域是（） （A）全平面（B）多平面（C）凸多平面（D）凹多平面 2、在目标线性规划问题中，叙述正确的选项为（）

（A） 正偏差变量取正值，负偏差变量取负值； （B） 目标规划模型中，若模型有解，则一定有最优解；

（C） 目标函数中的优先级P1，P2，P3，??之间表明数量上的重要型差别，如：P1

比P2级重要10倍或20倍等；

（D） 描写可以含系统约束（刚性约束），也可以不含。 3、下列叙述中，有关树G（V，E）性质不正确的选项为（）

（A） 无圈且不连通；

（B） n个顶点的树必有n-1条边； （C） 树中任意两点，恰有一条初等链；

（D） 树无回路，但不相邻顶点连一条边，恰得一回路。

三、已知某线性规划问题的目标函数为maxZ=5x1+3x2,约束形式为“≤”。设x3,x4为松弛变量，用单纯形法计算是某一步的表如下所示：（15分）

Cj CB XB B x1 x2 x3 x4 5 3 0 0 ，使VS∈V1,Vt∈

，则弧

0 5 Z x3 x1 2 a -10 c 0 1 1/5 d e 0 1 b -1 f g （1）求a~g的值；

（2）表中给出的解是否为最优解，并求出最优解。

四、已知某线性规划问题，其初始及最优单纯形表如下：（15分）

Cj CB 0 0 0 XB x3 x4 x5 σj 最优解表 Cj CB 1 0 2 σj XB x1 x4 x2 b 2 3 4 1 2 0 0 0 x1 x2 x3 x4 x5 1 0 1/2 0 -1/2 0 0 -3/2 1 3/2 0 1 0 0 1/2 0 0 -1/2 0 -1/2 b 12 9 8 1 2 3 4 5 x1 x2 x3 x4 x5 2 2 1 0 0 3 0 0 1 0 0 2 0 0 1 1 2 0 0 0 （1）求对偶问题的最优解；

（2）求C1的变化范围，使最优基不变； （3）如果b1由12变为16，求最优解。

五、如图所示是某地区交通运输示意图。VS是起点，Vt是终点。（12分）

（1）求出从VS到Vt的最短距径； （2）用双箭头在图上标明。

六、某物资每月需供应50箱，每次订货费为60元，每月每箱的存贮费为40元。（10分） （1）若不允许缺货，且一订货就可以提货，试问每隔多少时间订购一次，每次应订购多少箱？

（2）若一个周期中缺一箱的缺货损失费为40元，缺货不补，问每隔多少时间订购一次，每次应订购多少箱？

运筹学习题(4)

一、知线性规划问题（本题14分） min z=-5x1-6x2-7x3

要求：（1）化为标准形式（7分）

（2）列出用两阶段法求解时第一阶段的初始单纯形表（7分）。

二、已知下表是某极大化线性规划问题的初始单纯形表和迭代计算中某一步的单纯形表，试求出表中未知数a~l的值（每个 1.5分，共18分）。

X5 20 X6 8 cj-zj x1 x2 x3 x4 x5 x6 5 -4 13 (b ) 1 0 (j) -1 (k) (c) 0 1 1 6 -7 (a) 0 0 ┇ ┇

x3 (d) X2 (e) cj-zj -1/7 0 1 -3/7 (5) 4/7 (l) 1 0 -3/7 -5/7 (g) 7 2/7 0 0 11/7 (k) (i) 三、已知某一运输问题的产销平衡表、单位运价表如下表所示，且表中给出一个最优调运方案（16分）。

问：（1）从A2→B2的单位运价c22在什么范围内变化时，上述最优调运方案不变（8分）。

（2）A2→B4的单位运价c24变为何值时，该运输问题有无穷多最优调运方案。（4分）除表中给出

的方案外，至少再给出另两个不同的最优的方案。（4分）

四、有十名研究生参加六门课程考试，由于每人研究方向不同，所选课程也不一样，已知每名研究生要参加考试的课程如下表所示（表中打√的为参加考试的课程）（16分）。

考试安排在1月18~20日连

续三天，上、下午各考一门。

每名研究生都要提出希望自己每天最多只参加一门课程考试。已知要求C课程安排在19日上午，D课程必须安排在下午考，F课的考试必须安排在B、E考试之后。要求排出一张满足上述所有要求的考试日程表。

1月18日 1月19日 1月20日 上午 下午 五、见以下有向图，图中数字为两点间距离（16分）。

要求：（1）用动态规划的方法求出A→D的最短路（8分）

（2）若f2(B1)为从B1出发至D点的最短距离，写出f2(B1)的动态规划递推方程的一般表达

式，并具体说明递推方程中每个符号的意义（8分）。

六、选择填充题（每题4分，共20分） （1） 线性规划问题min z=3x1+5x2

已知其最优解为x1=2,x2=6,z*=36,则其对偶问题的最优解为 .。.（①y1=3,y2=2,y3=0;②y1=0,y2=3/2,y3=1;③y1=0,y2=1,y3=4/3;④y1=3,y2=1,y3=2/3）

（2）已知某个含10个节点的树图，其中9个节点的次（线度）为，1，1，3，1，1，1，3，1，3，则另一节点的次为。（①1；②4；③3；④2）

（3）用标号法寻找网络最大流时，发生标号中断。这时若用V表示已标号的节点集合，

解：增广矩阵为

x11x12x13x21x22x23x31x32x33

6??1?8??7? 5??3???1000000?11?0111000?00?000000111?0100100?10?010010010?1001001?00??2?3?11?3?2?8?5?8?15?x11x12x13x21x22x23x31x32x33

0?11100000?0?00011100?000000111?0?0?1?110010?010010010?1?00100100?0?1?9?3?2?8?5?8?15?6??1?8??1? 5??3???x11x12x13x21x22x23x31x32x33

?1??0?0??0?0??0?0?00001001??01110001?00001118???11101106? 00100105??10010013???9?3?1?8?5?7?15?10?100?10

x11x12x13x21x22x23x31x32?1??0?0??0?0??0?0?000010010?100?1x33

01??01110001?00001118???11101106? 00100105??10010013???9?3?1?8?5?7?15?x11x12x13x21x22x23x31x32x33

?1??0?0??0?0??0?0?00001001??01110001?00001118???11101106? 00100105??10010013???9?3?1?8?5?7?15?10?100?10x11x12x13x21x22?1??0?0??0?0??0?0?000010010?1x23x31x32x33

00?101??01110001??100?11105???11101106? 00100105??10000012??6?3?17?5?70?五、由800万元，分别用于3个项目的投资，按规定每个项目至少投资200万元，最多投资400万元，各项目得到不同投资时的预期效益如下表所示，要求确定使投资效益最大的各项目投资数（20分）。

要

求：（a）建立动态规划模型，列出递推关系式（基本方程），并说明方程中各符号的意义（10分）；

（b）建立网络模型，画出网络图，简要说明图中点、线和权术的意义（10分）。

运筹学习题（7）

一、将下列线性规划问题化为标准型（8分）min z=x1+2x2

二、生产一项产品，其加工的某道工序可有两种方案：采用设备A，平均加工时间为4分钟，指数分布，设备费用为每小时2元；采用设备B，加工时间恰好为5分钟，设备费用为每小时1.8元。产品以每小时8件的速度达到这一工序。产品在加工过程中每延误一小时，对工厂将有3元的损失，问应选哪一种设备？（8分）

三、某高架工程的作业明细表及有关资料如下表，试计算最低成本日程。

正常进度 工序代号 紧前工序 工序时间（天） 直接费用（元） 10 赶工进度 每赶工一天需要工序时间（天） 1 直接费用（元） 18 4 的费用（元/天） a b c d a a c 3 7 4 5 15 12 18 3 2 24 19 20 24 1 4 2 间接费用为每天4.5元。（10分）

四、某产品的需要量为每周650单位，且均匀领出。订购费为25元。每件产品的单位成本为3元，存货保存成本为每单位每周0.05元。

1） 假定不允许缺货，求多久订购一次与每次应订购数量。

2） 设缺货成本每单位每周2元，求多久订购一次与每次应订购数量。

3） 可允许缺货且设送货延迟为一周，求多久订购一次与每次应订购数量。（共12分） 五、见下图，现准备在v1,v2,?,v7七个居民点中设置一工商银行，各点之间的距离由附图给出。问工商银行设在哪个点，可使最大的服务距离为最小？若要设置两个银行，问设在哪两个点。

七、用三种固定要素（土地、劳动、机器）生产一产品M。已知该产品M价格每吨10美元，采用三种方法进行生产，每种方法的单位水平收入为1000美元。其投入系数与资源利用情况如下：

问：1）求解此线性规划问题。（5分）2）对所求解进行解释。（5分）3）对其对偶解进行经济解释。（5分）4） 证明劳动和土地之间的替代率（产量固定）等于要素价格比率。（7分）

运筹学试卷（8）

一、已知某线性规划问题，其初始及最优单纯形表如下。（15分） 初始表

CB xB 0 x3 0 x4 0 x5 σj 最优表

1 x1 0 x4 2 x2 σj 1 0 1/2 0 -1/2 0 0 -3/2 1 3/2 0 1 0 0 1/2 0 0 -1/2 0 -1/2 2 3 4 1 2 0 0 0 x1 x2 x3 x4 x5 2 2 1 0 0 3 0 0 1 0 0 2 0 0 1 1 2 0 0 0 b 12 9 8 1. 在求出对偶问题的最优解。

2. 求出c1的变化范围，使最优基不变。 3. 如b1由12变为16，求最优解。

二.、产品今后四周的需求量分别为300、700、900、600件，必须得到满足。已知每件产品的成本在起初两周是10元，以后两周是15元，工厂每周能生产这种产品700件，且在第二、三周能加班生产。加班后，每周可增产200件产品，但成本每件增加5元。产品如不能在本周交货，则每件每周存贮费是3元。问如何安排生产计划，使总成本最小》（要求建立运输问题数学模型，但不需求解）。（15分）

三、一块用堤埂粉肠很多小块的水稻田，如附图所示。为了即灌溉方便，需要挖开一些堤埂。问怎样挖堤埂，才能使挖开处最少，又能使水流入每一小块水稻田中？（15分）

四、汽车按普拉阿松分布到达某高速公路收费口，平均每

小时90辆。每辆车通过收费口平均需时35秒，服从负指数分布。为缩短收费等待时间，管理部门考虑采用自动收款装置，这样可使收费时间缩短到30秒。但采用的条件是原收费口平均等待车辆超过6辆，且新装置的利用率不会低于75%。问新装置能否被采用？（15分）

五、已知标准的M/M/3随机服务系统，平均每分钟到达顾客约数为0.9人，每位顾客的平均服务时间约为2.5分钟。求系统的服务强度ρ，并简述其意义。（15分）

六、假使某商品市场由A、B二家公司垄断，竞争中一方所得为另一方的所失。二家公司分别制订了五种未来经营策略。A公司的策略αi(i=1,2,?,5)、B公司的策略βj(j=1,2,?,5)以及A公司的预期的盈利矩阵A=（aij）,如下表所示。（15分）

βj aij αi α1 α2 α3 α4 α5 1 4 -3 5 4 3 4 3 0 1 1 5 2 3 4 0 3 0 2 4 -2 0 -2 1 3 β1 β2 β3 β4 β5 求双方的最优经营策略及竞争结果。 七、用图解法解目标规划(10分)

运筹学试卷（9）

一、参数线性规划问题（20分）

max z（θ1, θ2）=（5+2θ1）x1+(2-θ1)x2+(3+θ1)x3+0x4-Mx5-Mx6

当θ1=θ2=0时，用单纯形法求解，得最终单纯形表如下

x2 10 x4 5 cj-zj -1 0 2 1 -1 1 x1 x2 x3 x4 x5 x6 3 1 2 0 0 1 -1 0 -1 0 -M -M-2 要求：1.分析当θ2=0时，θ1在[0，∞]范围内变化时最优解的变化（8分）；

2.分析当θ1=0时，θ2在[0，1]范围内变化时最优解的变化（8分）；

3.将上述1、2的分析结果画两张图，第一张以θ1为横坐标，z(θ1)为纵坐标，第二张以θ

2

为横坐标，z(θ2)为纵坐标，用以表示目标函数值随参数θ1、θ2分别变化的规律（4分）。

二、已知4种化工品A、B、C、D拟存放于7个库房内，已知各化工品需存放量（吨），各库存最大允许存放量（吨）及存放费用（元/吨·年）如下表所示。

存放费用 ↘ A 化 工 品 B C D 仓库 1 2 3 4 5 6 7 1 2 2 3 4 5 5 2 3 3 1 1 5 5 4 4 3 2 1 5 5 1 1 2 2 3 6 4 需存放量 75 50 25 80 最大允许缺货量 25 25 40 60 80 100 100 考虑到安全因素，每个仓库内最多只能存放一种化工品。

要求：1.上述条件下，为使存放费用最小，建立相应数学模型（10分）；

2.若各仓库对应一个固定启用费用Fj(j=1,?,7)，当仓库不存放任何化工品时，Fj=0；否则不管存放

多少，Fj固定不变。要求重新建立使启用费用加上存放费总和为最小的 数学模型（10分）。

（以上两个模型均不需求解）

三、司了解到竞争对手将推出一种具有很大市场潜力的新产品，该公司正在研制性能类似产品，并接近完成。为此公司决定加速研制开发进度。已知产品投入市场前尚有4个阶段工作：下表1列出各阶段工作正常情况下，采取应急措施和采取特别措施时，完成各阶段工作所需时间（周）。表2列出4个阶段采取相应措施时的费用（万元），已知用于该产品研制的剩余费用为30万元，要求；

1.将此问题归结为最短路问题，画出相应网络图（10分）；

2.应用Dijkstra算法为该公司找出在费用允许条件下完成研制开发的最佳方案（10分）。 表1 单位：周

措施 正常 应急 特殊 表2 单位：万元

措施 正常 应急 特殊 阶段 1 2 3 4 3 6 6 9 3 9 9 12 6 2 2 3 1 阶段 1 2 3 4 5 4 3 5 2 四、某项重点攻关任务由三个单位按各自的方案独立研制，只要任何一个单位完成，该项任务即完成。该攻关任务指挥部有2名经验丰富人员可用于支援上述研制单位。已知各单位在无人员支持及分别有1名或2名人员支援时，其完成研制任务的概率如下表所示。问该指挥部应如何分配这两名支援人员，使完成攻关任务的概率为最大。

支援各单位人数 完成研制任务概率 单位1 单位2 单位3 0 1 2 要求用动态规划方法求解：

1.建立动态规划模型，列出和说明各模型要素（10分） 2.求数值解（10分）。

五、简要回答下列问题（20分） 1. 运输问题的数学模型通常表为（6分）

0.60 0.40 0.20 0.80 0.60 0.50 0.85 0.80 0.70 说明该模型对实际的运输问题作出哪几

点简化假定。

2.希望工程主管部门想在西部地区某个市的升初中一年级学生中（该市由小学升初中进行了一次全市统一考试）奖励一名优希望小学升入初中的统一考试成绩总分最高的女学生。考虑到在全市考生中普查工作量太大，请你应用分枝定界法的思想步骤为解决此问题设计一个方案。简述思路步骤（8分）。

2. 简要对比线性规划同目标规划在模型结构上的相同点和异同点（6分）。

本文来源：https://www.bwwdw.com/article/x8ew.html