《运筹学》题集

1．1 将下述线性规划问题化成标准形式 1) min z ＝ －3x1 ＋ 4x2 － 2x3 ＋ 5 x4 4x1 － x2 ＋ 2x3 － x4 ＝ －2 st. x1 ＋ x2 － x3 ＋ 2 x4 ≤ 14 －2x1 ＋ 3x2 ＋ x3 － x4 ≥ 2 x1 ，x2 ，x3 ≥ 0，x4 无约束

2) min z ＝ 2x1 －2x2 ＋3x3 － x1 ＋ x2 ＋ x3 ＝ 4 st. －2x1 ＋ x2 － x3 ≤ 6 x1≤0 ，x2 ≥ 0，x3无约束

1．2 用图解法求解LP问题，并指出问题具有唯一最优解、无穷多最优解、无界解还是

无可行解。

1) minz＝2x1＋3x2 4x1＋6x2≥6 st 2x1＋2x2≥4 x1，x2≥0

2) maxz＝3x1＋2x2 2x1＋x2≤2 st 3x1＋4x2≥12 x1，x2≥0

3) maxz＝3x1＋5x2 6x1＋10x2≤120 st 5≤x1≤10 3≤x2≤8

4) maxz＝5x1＋6x2 2x1－x2≥2 st －2x1＋3x2≤2 x1，x2≥0

1．3 找出下述LP问题所有基解，指出哪些是基可行解，并确定最优解 （1）minz＝5x1－2x2＋3x3＋2x4 x1＋2x2＋3x3＋4x4＝7 st 2x1＋2x2＋x3 ＋2x4＝3 x1，x2，x3，x4≥0

1．4 分别用图解法与单纯形法求解下列LP问题，并对照指出最优解所对应的顶点。 1) maxz＝10x1＋5x2 3x1＋4x2≤9 st 5x1＋2x2≤8 x1，x2≥0

2) maxz＝2x1＋x2 3x1＋5x2≤15 st 6x1＋2x2≤24 x1，x2≥0

1．5 分别用大M法与两阶段法求解下列LP问题。 1) minz＝2x1＋3x2＋x3 x1＋4x2＋2x3≥8 st 3x1＋2x2 ≥6 x1，x2 ，x3≥0

2) max z ＝4x1＋5x2＋ x3

. 3x1＋2x2＋ x3≥18 St. 2x1＋ x2 ≤4

x1＋ x2－ x3＝5

3) maxz＝ 5x1＋3x2 +6x3 x1＋2x2 －x3 ≤ 18 st 2x1＋x2 －3 x3 ≤ 16 x1＋x2 －x3＝10 x1，x2 ，x3≥0

4)maxz10x115x212x395x13x2x35x6x15x15123st.x352x1x2x,x,x01231．6

cj XB x4 x5

求下表中a～l的值。 （a） b 6 1 x1 （b） -1 （a） （f） ［（g）］ 4 （h） 0 －1 x2 （c） 3 -1 2 （I） -7 2 x3 （d） （e） 2 -1 1 （j） 0 x4 1 0 0 1/2 1/2 （k） 0 x5 0 1 0 0 1 （l） CB 0 0 （a） 0 j x1 x5 j 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) maxz＝5x1＋6x2＋3x3 x1＋2x2＋2x3 ＝5 st －x1＋5x2－ x3 ≥3 4x1＋7x2＋3x3 ≤8 x1无约束，x2≥0，x3≤0

3) maxz＝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 xj≥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： maxz＝x1＋x2 －x1＋ x2＋ x3 ≤2 st －2x1＋ x2－ x3 ≤1 xj≥0

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

2．5 给出LP： maxz＝2x1＋4x2＋x3＋x4 x1＋ 3x2 ＋x4 ≤8 2x1＋ x2 ≤6 st. x2 ＋ x3＋ x4≤6

x1＋ x2 ＋ x3 ≤9 xj≥0

1) 写出DLP；

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

2．6 用对偶单纯形法求解下列线性规划问题

1) minz＝4x1＋12x2＋18x3 x1 ＋3x3 ≥3

st 2 x2＋2x3 ≥5 xj≥0 (j=1,2,3)

2)minz5x12x24x33x1x22x34st.6x13x25x310x,x,x0123

2．7

st

1) 2) 3) 4)

2．8

1) 2) 3)

考虑如下线性规划问题 minz＝60x1＋40x2＋80x3 3x1＋2x2＋ x3 ≥2 4x1＋ x2＋3x3 ≥4 2x1＋2x2＋2x3 ≥3 xj≥0 写出DLP；

用对偶单纯形法求解原问题； 用单纯形法求解其对偶问题； 对比以上两题计算结果。

已知LP：maxz＝2x1－x2＋x3 x1＋ x2＋ x3≤6 st －x1＋2x2 ≤4 x1，x2，x3≥0 用单纯形法求最优解

分析当目标函数变为maxz＝2x1＋3x2＋x3时最优解的变化； 分析第一个约束条件右端系数变为3时最优解的变化。

2．9 给出线性规划问题 maxz＝2x1＋3x2＋x3 1/3x1＋1/3x2＋1/3x3≤1 st 1/3x1＋4/3x2＋7/3x3≤3 xj≥0 用单纯形法求解得最终单纯形表如下 CB 2 3 cj XB x1 x2 2 B 1 2 x1 1 0 0 3 x2 0 1 0 1 x3 －1 2 －3 0 x4 4 －1 －5 0 X5 －1 1 －1 j 试分析下列各种条件下，最优解（基）的变化： 1) 目标函数中变量x3的系数变为6；

2) 分别确定目标函数中变量x1和x2的系数C1、C2在什么范围内变动时最优解不变； 3) 约束条件的右端由 1 变为 2 ； 3 3

2.10 某厂生产甲、乙两种产品，需要A、B两种原料，生产消耗等参数如下表（表中的消耗系数为千克/件）。 产品原料 A B 销售价（元） 甲 2 3 13 乙 4 2 16 可用量（千克） 原料成本（元/千克） 160 180 1.0 2.0 （1）请构造数学模型使该厂利润最大，并求解。

（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 根据下表，用表上作业法求最优解。 A1 A2 A3 销量 B1 4 1 3 6 B2 1 2 7 5 B3 4 5 5 6 B4 6 0 1 3 产量 8 8 4 20

3．2 根据下表，用表上作业法求最优解。 A1 A2 A3 销量 B1 9 4 5 1 B2 3 9 7 3 B3 8 4 6 2 B4 7 5 2 5 产量 3 3 5 11

3．3 求给出的产销不平衡问题的最优解 A1 A2 A3 销量 B1 5 11 9 4 B2 12 8 7 3 B3 3 5 1 5 B4 4 9 5 6 产量 8 5 9

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

3.5 光明仪器厂生产电脑绣花机是以产定销的。已知1至6月份各月的生产能力、合同销量和单台电脑绣花机平均生产费用见下表： 正常生产能力（台） 加班生产能力（台） 销量（台） 单台费用（万元） 10 60 104 15 1月份 50 10 75 14 2月份 90 115 13.5 3月份 20 100 40 160 13 4月份 100 40 103 13 5月份 80 40 70 13.5 6月份 已知上年末库存103台绣花机，如果当月生产出来的机器当月不交货，则需要运到分厂库房，每台增加运输成本0.1万元,每台机器每月的平均仓储费、维护费为0.2万元。在7--8月份销售淡季，全厂停产1个月，因此在6月份完成销售合同后还要留出库存80台。加班生产机器每台增加成本1万元。问应如何安排1--6月份的生产，可使总的生产费用（包括运输、仓储、维护）最少？

3.6 设有A、B、C三个化肥厂供应1、2、3、4四个地区的农用化肥。假设效果相同，有关数据如下表： A B C 最低需要量 最高需要量 1 16 14 19 30 50 2 13 13 20 70 70 3 22 19 23 0 30 4 17 15 --- 10 不限 产量 50 60 50 试求总费用为最低的化肥调拨方案

第四章 排队论

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

（1） 店内空闲的概率； （2） 有4个顾客的概率； （3） 至少有1个顾客的概率； （4） 店内顾客的平均数；

（5） 等待服务的顾客的平均数； （6） 平均等待修理时间；

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

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

（1） 顾客来打字不必等待的概率； （2） 打字室内顾客的平均数；

（3） 顾客在打字室内的平均逗留时间；

（4） 若顾客在打字室内的平均逗留时间超过1.25h，则主人将考虑增加设备及打

字员。问顾客的平均到达率为多少时，主人才会考虑这样做。

4.3汽车按平均90辆/h的Poisson流到达高速公路上的一个收费关卡，通过关卡的平均时间为38s。由于驾驶人员反映等待时间太长，主管部门打算采用新装置，使汽车通过关卡的平均时间减少到平均30s。但增加新装置只有在原系统中等待的汽车平均数超过5辆和新系统中关卡的空闲时间不超过10%时才是合算的。根据这一要求，分析采用新装置是否合算。

4.4 有一个M/M/1/5 系统，平均服务率µ ＝10。就两种到达率 λ＝6，λ＝15已得到相应的概率pn,如下表所示，试就两种到达率分析：

（1） 有效到达率和系统的服务强度； （2） 系统中顾客的平均数； （3） 系统的满员率；

（4） 服务台应从哪些方面改进工作，理由是什么？ 系统中顾客数n 0 1 2 3 4 5

（λ＝6）pn, 0.42 0.25 0.15 0.09 0.05 0.04 （λ＝15）pn, 0.05 0.07 0.11 0.16 0.24 0.37

第五章 动态规划

5．1 现有天然气站A，需铺设管理到用气单位E，可以选择的设计路线如下图，B、C、D各点是中间加压站，各线路的费用如图所标注（单位：万元），试设计费用最低的线路。

15 B1C17 13 5 2 D1 7 7 5 1 A E B2 10 C2 4 5 1 1

D2 3 10 4 6 B3 C3

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

C150

F1 20 30 60

D1 20 B130 40 60 C2 30 50 F F2 40

50 A D2 30

40 45

C3 25 F3 B2 30

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

项目 A B C 投资额及收益 0 0 0 0 1 41 42 2 48 50 68 3 60 60 78 4 66 66 76

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

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

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

表1

表2

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

产品 1 2 3

5.8 用动态规划方法求解

2maxz4x19x22x3重量（t/件） 2 3 4 利润（千元/件） 80 130 180 2x14x23x310x1,x2,x30

第六章 存储论

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

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

6.3 某拖拉机厂生产一种小型拖拉机，每月可生产1000台，但对该拖拉机的市场需要量

为每年4,000台。已知每次生产的准备费用为15,000元，每台拖拉机每月的存贮费为10元，允许缺货（缺货费为20元/台月），求经济生产批量、经济周期与最小费用。

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

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

（1） 不允许缺货条件下的最优存贮策略；

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

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

（2） 求经济订购批量、经济周期与最小费用；

（3） 该厂为少占用流动资金，希望进一步降低存贮量。因此，决定使订购和存贮总

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

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

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

6.9某制造厂在装配作业中需用一种外购件，全年需求量为300万件，不允许缺货；一次订购费为100元；存贮费为0.1元/件月。该外购件进货单价和订购批量Q有关，具体如下表，求最佳订购策略。 批量（件） 0≤Q＜10000 10000≤Q＜30000 单价（元） 1.00 0.98 30000≤Q＜50000 0.96 Q≥50000 0.94

6.10试证明：一个允许缺货的EOQ模型的费用，决不会超过一个具有相同存贮费、订购

费、但又不允许缺货的EOQ模型的费用。

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

销售量r（套） 概率P（r） 150 0.05 160 0.1 170 0.5 180 0.3 190 0.05 该款式时装每套进价180元，售价200元。因隔季会过时，故在季末需低价抛售完，较有把握的抛售价为每套120元。问该时装屋在季度初时一次性进货多少为宜？