王家荣运筹学习题Word文档下载推荐.docx

王家荣运筹学习题Word文档下载推荐.docx

《王家荣运筹学习题Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《王家荣运筹学习题Word文档下载推荐.docx（20页珍藏版）》请在冰点文库上搜索。

min

-3x2

2x1

-x2

≥3

（3）

≤3

（4）

≥4

四、在以下问题中，列出所有的基，指出其中的可行基，基础可行解以及最优解。

-x3

+x2

+4x2

五、对于以下的约束

≤2

x1,x2

（1）.画出该可行域，并求出各极点的座标。

（2）.从原点开始，从一个基础可行解移到下一个“相邻的”基础可行解，指出每一次叠代，哪个变量进基，哪个变量离基。

六、用单纯形原理求解以下线性规划问题

3x1

七、已知（x1，x2，x3）＝（4，0，4）是以下线性规划的一个基础可行解，以这个基为初始可行基，求解这个线性规划问题

-2x2

＝12

八、用单纯形表求解以下线性规划问题

≤6

≤9

≥0

+3x3

-5x4

s.t

+4x3

-x4

+x4

≤4

x3,

x4

≥-3

≥-6

≤8

4x1

≤16

九、用两阶段法求解以下线性规划问题

≤13

≤17

=13

-2x3

≤8

≥2

+5x2

第二章对偶线性规划和灵敏度分析

一.写出以下问题的对偶问题

≥2

+5x3

+6x4

+3x4

≤-3

-5x3

≥5

=6

x1≤0,x2≥0,x3≥0,x4无符号限制

二、设原始问题为

s.写出对偶问题

（2）用图解法分别求出原始问题和对偶问题的各基础可行解，并求出各基础可行解的目标函数值，并比较他们的大小。

（3）验证原始问题和对偶问题的最优解满足Kuhn-Tucker最优性条件。

三、已知如下最优单纯形表，其中x4，x5是松弛变量，两个约束都是≤型的。

z

x5

RHS

1

-4

-4

-2

-40

1/2

0

5/2

-1/2

-1/6

1/3

（1）写出原始问题及对偶问题。

（2）从上表中直接求出对偶问题的最优解。

四、对于以下线性规划问题

+6x3

（1）.写出对偶问题

（2）.写出原始问题所有的基，判断这些是否原始可行基，是否对偶可行基。

（3）.求出原始问题和对偶问题的最优解。

五、对于以下问题

+6x2

（1）写出对偶问题

（2）用单纯形表求解原始问题，求出每一次叠代的当前基B对应的对偶变量WT＝CTBB-1，并判断每次得到的对偶变量是否满足对偶可行条件。

六、用对偶单纯形法求解以下问题

+18x3

x3≥0

10x1

≥6

七、对以下问题

（1）用图解法画出可行域和各个极点。

（2）用对偶单纯形表求解以上问题，并在图上画出叠代路线。

八、已知以下线性规划问题

及其最优单纯形表如下：

3

2

16

8

x6

-1

12

（1）求使最优基保持不变的c2=1的变化范围。

如果c2从1变成5，最优基是否变化，如果变化，求出新的最优基和最优解。

（2）对c1=2进行灵敏度分析，求出c1由2变为4时的最优基和最优解。

（3）对变量x3在第二个约束中的系数a23=-2进行灵敏度分析，求出a23从-2变为1时新的最优基和最优解。

（4）增加一个新的变量x6，它在目标函数中的系数c6=4，在约束条件中的系数向量为

，求新的最优基和最优解。

（5）增加一个新的约束x2+x3≥2，求新的最优基和最优解。

（6）设变量x1在约束条件中的系数向量由

变为

，求出新的最优基和最优解。

九、某工厂用甲、乙、丙三种原料生产A、B、C、D四种产品，每种产品消耗原料定额以及三种原料的数量如下表所示:

产品

A

B

C

D

原料数量（吨）

对原料甲的单耗（吨/万件）

4

2400

对原料乙的消耗（吨/万件）

－

3200

对原料丙的消耗（吨/万件）

1800

单位产品的利润（万元/万件）

25

14

15

（1）求使总利润最大的生产计划和按最优生产计划生产时三种原料的耗用量和剩余量。

（2）求四种产品的利润在什么范围内变化，最优生产计划不会变化。

（3）求三种原料的影子价格和四种产品的机会成本，并解释最优生产计划中有的产品不安排生产的原因。

（4）在最优生产计划下，哪一种原料更为紧缺?

如果甲原料增加120吨，这时紧缺程度是否有变化?

第三章整数规划

1、分别用割平面法和分枝定界法求以下整数规划问题

14x1

+42x2

≤196

≤5

2、用分枝定界法求解以下混合整数规划问题

+7x2

≤2

x1为整数

3、求解以下整数规划问题

65x1

+80x2

+30x3

x1，x2，x3为整数

第四章运输问题

1、求解如下图所示的运输问题，并将最优解在网络中表示。

2、将下表所示的一组解作为初始解，分别用闭回路法和对偶变量法求出非基变量的zij-cij，并求出运输问题的最优解。

9

13

18

10

24

11

6

7

5

35

3、对下表所示的运输问题（表内部的数字表示cij，表右面和下面的数字分别表示供应量和需求量）。

B1

B2

B3

B4

A1

A2

A3

20

（1）分别用西北角法和最小元素法得到初始基础可行解；

（2）选择其中一个基础可行解，从这个基础可行解出发，求出这个问题的最优解；

（3）如果c11=6变为-4，最优解是否改变？

如改变，求出新的最优解；

（4）在原来的问题中，如果从A2到B1的道路被阻，最优解是否会改变？

如改变，求出新的最优解。

4、求解下表所示的供求不平衡的运输问题，其中Ai—Bj格子中的数字表示cij。

供求地

供应量

需求量

5、有n项任务，分配给n个人去完成，每项任务只需要一个人去做，每个人只做一项任务。

第i项任务分配给第j个人去做所需要的费用为cij。

应如何分配各项任务，使完成n项任务的总费用最小。

这个问题称为指派问题（AssignmentProblem）。

矩阵C=[cij]n⨯n称为指派问题的费用矩阵。

指派问题是一类特殊的运输问题。

用运输问题算法求解以下指派问题，费用矩阵如下表所示：

人员1

人员2

人员3

任务1

任务2

任务3

第五章网络优化

1、

对以下网络，用试凑的方法得到一个初始可行的生成树，求这个网络的最小费用流。

2、求解下图所示的最小费用流问题（注意：

）

3、求解下图所示的具有中转站的运输问题，其中节点1、2、3是发地，6、7是收地，4、5是中转站。

边上的数字是cij。

4、用两阶段法求解下图所示的网络最小费用流问题。

5、求解以下的生产—运输—存储问题。

一个公司在A1、A2两地生产同一种产品，考虑一、二两个季度的生产。

不同的产地，不同的季节，生产费用和生产能力都不相同。

产地A1、A2两个季度的生产费用和生产能力如下表。

产地

第一季度

第二季度

生产费用

生产能力

25元/吨

6吨

35元/吨

2吨

30元/吨

10吨

43元/吨

9吨

A1、A2生产的产品可以运输到两个销地B1、B2（运输时间可以不计），以满足两地的需求，B1、B2两地的需求量如下表所示。

销地

3吨

5吨

4吨

运输费用也随运输路线和季节不同而变化。

如下表所示。

销地B1

销地B2

50元/吨

60元/吨

80元/吨

40元/吨

70元/吨

90元/吨

另外，每个产地和销地都可以库存第一季度的产品，以供第二季度之用，库存费用如下表所示。

产/销地

库存费用

2元/吨

3元/吨

4元/吨

求两个季度的最优生产、库存计划，使两个季度的总费用最小。

6、求下图所示网络的最大流

4、求以下网络从节点1到其余各节点的最短路径

第六章动态规划

一、用动态规划求解以下网络从A到F的最短路径，路径上的数字表示距离。

二、某公司有5台设备，分配给所属A,B,C三个工厂。

各工厂获得不同的设备台数所能产生效益（万元）的情况如下表。

求最优分配方案，使总效益最大。

台数

工厂

23

17

22

三、用动态规划求解以下非线性整数规划问题：

minz=3x12-5x1+3x22-3x2+2x32-7x3

s.t.2x1+3x2+2x3≥16

x1,x2,x3≥0,x1,x2,x3为整数

四、用动态规划求解以下背包问题

（1）maxz=12x1+22x2+15x3

s.t.2x1+4x2+3x3≤10

x1,x2,x3≥0,x1,x2,x3为整数

（2）maxz=17x1+72x2+35x3

s.t.10x1+41x2+20x3≤50

五、某工厂要安排某种产品一年中四个季度的生产计划。

生产费用的经验公式是：

0.005元×

（本季度产量）2

产品的存储费用为每件每季度1元。

设初始存储量为0，最大存储量为1500件。

四个季度的市场销售量预测如下：

季度

销售量（件）

累计销售量（件）

一

600

二

700

1300

三

500

四

1200

3000

用动态规划确定四个季度的生产量和储存量，在满足各季度销售额的条件下使总生产、存储费用为最小。

六、有三种新产品A，B，C有待研制。

每种新产品在一年内研制不成功的概率与投入该产品的研制费用有关，有关数据如下表。

设总的研制经费为3万元。

试求三个项目研制费用的分配方案，使这三个产品研制全不成功的概率为最小。

1万元

0.40

0.60

0.80

2万元

0.20

0.50

3万元

0.15

0.30

七、求解以下设备更新问题：

当设备年龄为k年时，设备运行每年所得的净收入可用下式表示：

Ik=26-2k-0.5k2,k=0,1,2,3,4

设备用过4年后就被废弃，更新设备的费用为22。

现有一台设备，已用过一年，要作这种设备更新的五年计划，决定每一年初设备更新或留用，使总收入最大。

八、求以下货郎担问题的最小旅行费用周游线路，以下是5个城市中从城市i到城市j的费用。

注意其中两个城市之间往返的费用是不相等的。

ij

—

第七章排队论

一、某修理店只有一个修理工，来修理的顾客到达的次数服从Poisson分布，平均每小时4人；

修理时间服从负指数分布，每次服务平均需要6分钟。

求：

（1）修理店空闲的概率；

（2）店内有三个顾客的概率；

（3）店内至少有一个顾客的概率；

（4）在店内平均顾客数；

（5）顾客在店内的平均逗留时间；

（6）等待服务的平均顾客数；

（7）平均等待修理的时间；

二、一个单人理发点，顾客到达服从Poisson分布，平均到达时间间隔为20分钟；

理发时间服从负指数分布，平均理发时间为15分钟。

（1）顾客来店理发不必等待的概率；

（2）理发店内顾客平均数；

（3）顾客在理发店内的平均逗留时间；

（4）当顾客到达速率是多少时，顾客在店内的平均逗留时间将超过1.25小时。

三、在第一题中，如果修理店内已有三个顾客时，店主就拒绝顾客排队。

（1）店内空闲的概率；

（2）各运行指标L，Lq，W，Wq。

四、在[M/M/1]:

[N/∞/FCFS]系统中，设顾客到达速率为λ，服务速率为μ，求单位时间内被拒绝的顾客数的期望值。

五、在第一题中，设顾客到达速率增加到12人/小时，这时又增加一个同样熟练的修理工，平均修理时间也是6分钟。

（2）店内有两个或更多顾客的概率；

（3）计算运行指标L，Lq，W，Wq。

六、如果将第五题中的两个修理工分别安排在两家修理店里，成为两个单人修理店，每个店顾客到达速率都是6人/小时，服务速率都是6分钟。

（1）求这两个修理店的运行指标L，Lq，W，Wq；

（2）将以上运行指标与第五题两个修理工的系统比较。

[文档可能无法思考全面，请浏览后下载，另外祝您生活愉快，工作顺利，万事如意!

]