文档库

最新最全的文档下载
当前位置:文档库 > 《运筹学》习题集

《运筹学》习题集

第一章线性规划

1.1将下述线性规划问题化成标准形式

1)min z=-3x1+4x2-2x3+5 x4

-x2+2x3-x4=-2

4x

《运筹学》习题集

st. x1+x2-x3+2 x4 ≤14

-2x1+3x2+x3-x4 ≥ 2

x1,x2,x3≥0,x4无约束

2)min z =2x1-2x2+3x3

+x2+x3=4

-x

《运筹学》习题集

st. -2x1+x2-x3≤6

x1≤0 ,x2≥0,x3无约束

1.2用图解法求解LP问题,并指出问题具有唯一最优解、无穷多最优解、无界解还是无可行解。

1)min z=2x1+3x2

4x1+6x2≥6

st2x1+2x2≥4

x1,x2≥0

2)max z=3x1+2x2

2x1+x2≤2

st3x1+4x2≥12

x1,x2≥0

3)max z=3x1+5x2

6x1+10x2≤120

st5≤x1≤10

3≤x2≤8

4)max z=5x1+6x2

2x1-x2≥2

st-2x1+3x2≤2

x1,x2≥0

1.3找出下述LP问题所有基解,指出哪些是基可行解,并确定最优解

(1)min z=5x1-2x2+3x3+2x4

x1+2x2+3x3+4x4=7

st2x1+2x2+x3 +2x4=3

x1,x2,x3,x4≥0

1.4 分别用图解法与单纯形法求解下列LP 问题,并对照指出最优解所对应的顶点。 1) maxz =10x 1+5x 2

3x 1+4x 2≤9 st 5x 1+2x 2≤8 x 1,x 2≥0

2) maxz =2x 1+x 2 3x 1+5x 2≤15 st 6x 1+2x 2≤24

x 1,x 2≥0

1.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≥0

2) max z =4x 1+5x 2+ x 3

. 3x 1+2x 2+ x 3≥18

St. 2x 1+ x 2 ≤4

x 1+ x 2- x 3=5

3) 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≥0

123123

123123123

4)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人,周日去植树。根据经验,一天男生平均每人挖坑20个,或栽树30棵,或给25棵树浇水;女生平均每人挖坑10个,或栽树20棵,或给15棵树浇水。问应怎样安排,才能使植树(包括挖坑、栽树、浇水)最多?请建立此问题的线性规划模型,不必求解。

1.8某糖果厂用原料A、B、C加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中A、B、C含量,原料成本,各种原料的每月限制用量,三种牌号糖果的单位加工费及售价如下表所示。

问该厂每月应生产这三种牌号糖果各多少千克,使该厂获利最大?试建立此问题的线性规划的数学模型。

甲乙丙原料成本(元/千克) 每月限量(千克)A≥60%≥15% 2.00 2000

B 1.50 2500

C ≤20%≤60%≤50% 1.00 1200

加工费(元/千克)0.50 0.40 0.30

售价 3.40 2.85 2.25

1.9某商店制定7-12月进货售货计划,已知商店仓库容量不得超过500件,6月底已存货200件,以后每月初进货一次,假设各月份此商品买进售出单价如下表所示,问各月进货售货各多少,才能使总收入最多?请建立此问题的线性规划模型。

月份7 8 9 10 11 12

买进单价28 24 25 27 23 23

售出单价29 24 26 28 22 25

1.10某厂接到生产A、B两种产品的合同,产品A需200件,产品B需300件。这两种产品的生产都经过毛坯制造与机械加工两个工艺阶段。在毛坯制造阶段,产品A每件需要2小时,产品B每件需要4小时。机械加工阶段又分粗加工和精加工两道工序,每件产品A 需粗加工4小时,精加工10小时;每件产品B需粗加工7小时,精加工12小时。若毛坯生产阶段能力为1700小时,粗加工设备拥有能力为1000小时,精加工设备拥有能力为3000小时。又加工费用在毛坯、粗加工、精加工时分别为每小时3元、3元、2元。此外在粗加工阶段允许设备可进行500小时的加班生产,但加班生产时间内每小时增加额外成本4.,5元。试根据以上资料,为该厂制订一个成本最低的生产计划。

1.11某公司有三项工作需分别招收技工和力工来完成。第一项工作可由一个技工单独完成,或由一个技工和两个力工组成的小组来完成。第二项工作可由一个技工或一个力工单独去完成。第三项工作可由五个力工组成的小组完成,或由一个技工领着三个力工来完成。已知技工和力工每周工资分别为100元和80元,他们每周都工作48小时,但他们每人实际的有效工作小时数分别为42和36。为完成这三项工作任务,该公司需要每周总有效工作小时数为:第一项工作10000小时。第二项工作20000小时,第三项工作30000小时。又能招收到的工人数为技工不超过400人,力工不超过800人。试建立数学模型,确定招收技工和力工各多少人。使总的工资支出为最少(

第二章对偶与灵敏度分析

2.1写出以下线性规划问题的DLP

1)minz=2x1+2x2+4x3

x1+3x2+4x3≥2

st 2x1+x2+3x3≤3

x1+4x2+3x3=5

x1,x2≥0,x3无约束

2)max z=5x1+6x2+3x3

x1+2x2+2x3=5

st-x1+5x2-x3≥3

4x1+7x2+3x3≤8

x1无约束,x2≥0,x3≤0

3)max z=c1x1+c2x2+c3x3

a11x1+a12x2+a13x3≤b1

st a21x1+a22x2+a23x3=b2

a31x1+a32x2+a33x3≥b3

x1≥0,x2≤0,x3无约束

2.2对于给出的LP:

minz=2x1+3x2+5x3+6x4

x1+2x2+3x3+x4≥2

st-2x1+x2-x3+3x4≤-3

x j≥0 (j=1,2,3,4)

1)写出DLP;

2)用图解法求解DLP;

3)利用2)的结果及根据对偶性质写出原问题的最优解。

2.3对于给出LP:

maxz=x1+2x2+x3

x1+x2-x3≤2

st x1-x2+x3=1

2x1+x2+x3≥2

x1≥0,x2≤0,x3无约束

1)写出DLP;

2)利用对偶问题性质证明原问题目标函数值Z≤1

2.4已知LP:

max z=x1+x2

-x1+x2+x3≤2

st-2x1+x2-x3≤1

x j≥0

试根据对偶问题性质证明上述线性问题目标函数值无界。

2.5 给出LP : maxz =2x 1+4x 2+x 3+x 4 x 1+ 3x 2 +x 4 ≤8 2x 1+ x 2 ≤6

st. x 2 + x 3+ x 4≤6

x 1+ x 2 + x 3 ≤9

x j ≥0

1) 写出DLP ;

2) 已知原问题最优解X =(2,2,4,0),试根据对偶理论,直接求出对偶问题的最优解。

2.6 用对偶单纯形法求解下列线性规划问题 1) minz =4x 1+12x 2+18x 3 x 1 +3x 3 ≥3

st 2 x 2+2x 3 ≥5

x j ≥0 (j=1,2,3)

123123123123

2)min 524324.63510,,0z x x x x x x st x x x x x x =++++≥??

++≥??≥?

2.7 考虑如下线性规划问题

minz =60x 1+40x 2+80x 3 3x 1+2x 2+ x 3 ≥2 st 4x 1+ x 2+3x 3 ≥4

2x 1+2x 2+2x 3 ≥3

x j ≥0

1) 写出DLP ;

2) 用对偶单纯形法求解原问题; 3) 用单纯形法求解其对偶问题; 4) 对比以上两题计算结果。

2.8 已知LP :maxz =2x 1-x 2+x 3 x 1+ x 2+ x 3≤6 st -x 1+2x 2 ≤4

x 1,x 2,x 3≥0

1) 用单纯形法求最优解

2) 分析当目标函数变为maxz =2x 1+3x 2+x 3时最优解的变化; 3) 分析第一个约束条件右端系数变为3时最优解的变化。

2.9给出线性规划问题

maxz=2x1+3x2+x3

1/3x1+1/3x2+1/3x3≤1

st 1/3x1+4/3x2+7/3x3≤3

x j≥0

《运筹学》习题集

1)目标函数中变量x3的系数变为6;

2)分别确定目标函数中变量x1和x2的系数C1、C2在什么范围内变动时最优解不变;

3)约束条件的右端由 1 变为 2 ;

《运筹学》习题集

《运筹学》习题集

《运筹学》习题集

3 3

2.10 某厂生产甲、乙两种产品,需要A、B两种原料,生产消耗等参数如下表(表中的消耗系数为千克/件)。

《运筹学》习题集

(2)原料A、B的影子价格各为多少。

(3)现有新产品丙,每件消耗3千克原料A和4千克原料B,问该产品的销售价格至少为多少时才值得投产。

(4)工厂可在市场上买到原料A。工厂是否应该购买该原料以扩大生产?在保持原问题最优基的不变的情况下,最多应购入多少?可增加多少利润?

3.5 某玩具公司分别生产三种新型玩具,每月可供量分别为1000、2000、2000件,它们分别被送到甲、乙、丙三个百货商店销售。已知每月百货商店各类玩具预期销售量均为1500件,由于经营方面原因,各商店销售不同玩具的盈利额不同,见下表。又知丙百货商店要求至少供应C玩具1000件,而拒绝进A玩具。求满足上述条件下使总盈利额最大的供销分配方案。

甲乙丙可供量

A 5 4 -1000

B 16 8 9 2000

C 12 10 11 2000

第三章 运输问题

3.1

《运筹学》习题集

3.

《运筹学》习题集

23.

3

《运筹学》习题集

3.4 某市有三个面粉厂,他们供给三个面食加工厂所需的面粉,各面粉厂的产量、各面食加工厂加工面粉的能力、各面食加工厂和各面粉厂之间的单位运价,均式于下表。假定在第1,2和3面食加工厂制作单位面粉食品的利润分别为12元、16元和11元,试确定使总效益最大的面粉分配计划(假定面粉厂和面食加工厂都属于同一个主管单位)。

《运筹学》习题集

3.5 光明仪器厂生产电脑绣花机是以产定销的。已知1至6月份各月的生产能力、合同销量和单台电脑绣花机平均生产费用见下表:

《运筹学》习题集

已知上年末库存103台绣花机,

如果当月生产出来的机器当月不交货,则需要运到分厂库房,

每台增加运输成本0.1万元,每台机器每月的平均仓储费、维护费为0.2万元。在7--8月份销售淡季,全厂停产1个月,因此在6月份完成销售合同后还要留出库存80台。加班生产机器每台增加成本1万元。问应如何安排1--6月份的生产,可使总的生产费用(包括运输、仓储、维护)最少?

3.6 设有A 、B 、C 三个化肥厂供应1、2、3、4四个地区的农用化肥。假设效果相同,有关数据如下表:

《运筹学》习题集

试求总费用为最低的化肥调拨方案

第四章 动态规划

4.1

现有天然气站A ,需铺设管理到用气单位E ,可以选择的设计路线如下图,B 、C 、D

《运筹学》习题集

各点是中间加压站,各线路的费用如图所标注(单位:万元),试设计费用最低的线路。 4.2

一艘货轮在A 港装货后驶往F 港,中途需靠港加油、加淡水三次,从A 港到F 港全部可能的航运路线及两港之间距离如图,F 港有3个码头F 1,F 2,F 3,试求最合理停靠的码头及航线,使总路程最短。

《运筹学》习题集

F

4.3某公司有资金4万元,可向A、B、C三个项目投资,已知各项目的投资回报如下,求最大回报。

《运筹学》习题集

4.4 某厂有1000台机器,高负荷生产,产品年产量S1与投入机器数Y1的关系为S1=8Y1,机器完好率为0.7;低负荷生产,产品年产量S2与投入机器数Y2的关系为S2=5Y2,机器完好率为0.9;请制定一个五年计划,使总产量最大。

4.5某厂准备连续3个月生产A种产品,每月初开始生产。A的生产成本费用为x2,其中x 是A产品当月的生产数量。仓库存货成本费是每月每单位为1元。估计3个月的需求量分别为d1=100,d2=110,d3=120。现设开始时第一个月月初存货s0=0,第三个月的月末存货s3=0。试问:每月的生产数量应是多少才使总的生产和存货费用为最小。

4.6 某公司为主要电力公司生产大型变压器,由于电力采取预订方式购买,所以该公司可以预测未来几个月的需求量。为确保需求,该公司为新的一年前四个月制定一项生产计划,这四个月的需求如表1所示。生产成本随着生产数量而变化。调试费为4,除了调度费用外,每月生产的头两台各花费为2,后两台花费为1。最大生产能力每月为4台,生产成本如2所示。

表1

《运筹学》习题集

表2

《运筹学》习题集

4.7某工厂生产三种产品,各种产品重量与利润关系如下表,现将此三种产品运往市场出售,运输能力总重量不超过6t,问应运输每种产品各多少件可使总利润最大。

《运筹学》习题集

4.8 用动态规划方法求解

2

123

123123max 49224310,,0

z x x x x x x x x x =++++≤??

≥?

第五章 存储论

5.1 某建筑工地每月需用水泥800t ,每t 定价2000元,不可缺货。设每t 每月保管费率为0.2%,每次订购费为300元,求最佳订购批量、经济周期与最小费用。

5.2 一汽车公司每年使用某种零件150,000件,每件每年保管费0.2元,不允许缺货,试比较每次订购费为1,000元或100元两种情况下的经济订购批量、经济周期与最小费用。

5.3 某拖拉机厂生产一种小型拖拉机,每月可生产1000台,但对该拖拉机的市场需要量为每年4,000台。已知每次生产的准备费用为15,000元,每台拖拉机每月的存贮费为10元,允许缺货(缺货费为20元/台月),求经济生产批量、经济周期与最小费用。

5.4 某产品每月需求量为8件,生产准备费用为100元,存贮费为5元/月件。在不允许缺货条件下,比较生产速度分别为每月20件和40件两种情况下的经济生产批量、经济周期与最小费用。

5.5 对某种电子元件每月需求量为4,000件,每件成本为150元,每年的存贮费为成本的10%,每次订购费为500元。求:

(1) 不允许缺货条件下的最优存贮策略;

(2) 允许缺货(缺货费为100元/件年)条件下的最优存贮策略。

5.6 某农机维修站需要购一种农机配件,其每月需要量为150件,订购费为每次400元,存贮费为0.96元/件月,并不允许缺货。

(1) 求经济订购批量、经济周期与最小费用;

(2) 该厂为少占用流动资金,希望进一步降低存贮量。因此,决定使订购和存贮总

费用可以超过原最低费用的10%,求这时的最优存贮策略。

5.7 某公司每年需电容器15,000个,每次订购费80元,保管费1元/个年,不允许缺货。若采购量少于1000个时,每个单价为5元,当一次采购1000个以上时每个单价降为4.9元。求该公司的最优采购策略。

5.8 某工厂对某种物料的年需要量为10,000单位,每次订货费为2,000元,存贮费率为20%。该物料采购单价和采购数量有关,当采购数量在2,000单位以下时,单价为100元;当采购数量在2,000及以上单位时,单价为80元。求最优采购策略。

5.9某制造厂在装配作业中需用一种外购件,全年需求量为300万件,不允许缺货;一次订购费为100元;存贮费为0.1元/件月。该外购件进货单价和订购批量Q有关,

《运筹学》习题集

5.10试证明:一个允许缺货的EOQ模型的费用,决不会超过一个具有相同存贮费、订购费、但又不允许缺货的EOQ模型的费用。

5.11某时装屋在某年春季欲销售某种流行时装。据估计,该时装可能的销售量见下表:

《运筹学》习题集

有把握的抛售价为每套120元。问该时装屋在季度初时一次性进货多少为宜?

第六章排队论

6.1某店仅有一个修理工人,顾客到达过程为Poisson流,平均3人/h,修理时间服从负指数分布,平均需10min。求:

(1)店内空闲的概率;

(2)有4个顾客的概率;

(3)至少有1个顾客的概率;

(4)店内顾客的平均数;

(5)等待服务的顾客的平均数;

(6)平均等待修理时间;

(7)一个顾客在店内逗留时间超过15 min的概率。

6.2设有一单人打字室,顾客的到达为为Poisson流,平均到达时间间隔为20 min ,打字时间服从负指数分布,平均为15min。求:

(1)顾客来打字不必等待的概率;

(2)打字室内顾客的平均数;

(3)顾客在打字室内的平均逗留时间;

(4)若顾客在打字室内的平均逗留时间超过1.25h,则主人将考虑增加设备及打字员。问顾客的平均到达率为多少时,主人才会考虑这样做。

6.3汽车按平均90辆/h的Poisson流到达高速公路上的一个收费关卡,通过关卡的平均时间为38s。由于驾驶人员反映等待时间太长,主管部门打算采用新装置,使汽车

通过关卡的平均时间减少到平均30s。但增加新装置只有在原系统中等待的汽车平

均数超过5辆和新系统中关卡的空闲时间不超过10%时才是合算的。根据这一要求,分析采用新装置是否合算。

6.4 有一个M/M/1/5系统,平均服务率μ=10。就两种到达率λ=6,λ=15已得到相应的概率p n,如下表所示,试就两种到达率分析:

(1)有效到达率和系统的服务强度;

(2)系统中顾客的平均数;

(3)系统的满员率;

(4)服务台应从哪些方面改进工作,理由是什么?

《运筹学》习题集

1