运筹习题参考答案

《实用管理运筹学》

习题参考答案

沈阳航空航天大学 2010年6月

目 录

第2章 线性规划及其对偶问题 ..................................................................................... 1 第3章整数规划与运输问题 ......................................................................................... 20 第4章 目标规划 ........................................................................................................... 40 第5章 动态规划方法的基本思想及应用 ................................................................... 50 第7章 对策论模型 ....................................................................................................... 58 第10章 决策分析 ......................................................................................................... 67

第2章 线性规划及其对偶问题

2.1 用图解法求解下列线性规划问题，并指出问题是具有唯一最优解、无穷多最优解、无界解还是无可行解？

maxZ?4x1?3x2maxZ?x1?2x2?x1?2x2?6? 2x1 ? x2?10?3x?2x?12 ??3x?2x?6 （2） （1）

??212s..t?1s..t?? x2?2? x1 ? x2?6???x1?0,x2?0?x1,x2?0 minZ?3x1?2xmaxZ?x1?x2（3）

?x1?2x2?2 （4）

?s..ts..t?x1?x2??1?x,x?0 ?12? x1? x2? 1 ??2x1?3x2?6?x,x?0 ?12解：各线性规划模型的图解如下。

有惟一最优解 有无穷多最优解

有无界解 无可行解

1

第2章 线性规划及其对偶问题

2.2 将下列线性规划模型化为标准形式并列出初始单纯形表。

minz?x1?2x2?4x3maxs?zk/pk??3x1?2x2?2x3?19?zk??n?maikxiki?1k?1??4x?3x?4x?14 （2） ?（1） m?1?23s..t?s..t??k?1?xik??1,?i5x?2x?4x??2623??1xik?0,?i,k??x1?0,x2?0,x3无约束??解：（1）令x1'??x1,x3?x3'?x3\,z'??z，则得到标准型为（其中M为一个任

意大的正数）

maxz'??2x1'?2x2?4x3'?4x3''?0x4?0x5?Mx6?Mx7?3x1'?2x2?2x3'?2x3''?x4?19?4x'?3x?4x'?4x''?x?x?14?123356s..t??5x1'?2x2?4x3'?4x3''?x7?26??x1',x2,x3',x3'',x4,x5,x6,x7?0初始单纯形表如表2-1所示：

表2-1 cj CB 0 -M -M XB x4 x6 x7 -z b 19 14 26 -2 2 x2 2 3 2 2+5M 4 x3'

-4 0 x4 1 0 0 0 0 x5 0 -1 0 -M -M x6 0 1 0 0 -M x7 0 0 1 0 x1' 3 [ 4 ] 5 -2+9M x3'' -2 -4 -4 -4-8M ? 19/3 14/4 26/5 2 4 4 4+8M

（2）在上述问题的约束条件中加入人工变量x1,x2,?,xn，得到标准型

maxs?m1pk?i?1?k?1xik?M?i?1xi

nmn?x?xi?1(i?1,2,?,n)?s..t??k?1ik??xik?0,xi?0(i?1,2,?,n;k?1,2,?,m)其中，M是一个任意大的正数。初始单纯形表如表2-2所示：

2

第2章 线性规划及其对偶问题

表2-2 cj CB -M -M XB x1 x2 b 1 1 -M x1 1 0 ? ? -M xn 0 0 a11pk … a1mpk an1pk ? ? anmpk ? x11 1 0 ? x1m 1 0 ? xn1 0 0 xnm 0 0 pk? -M ? xn -s ? 1 ? 0 0 ? ? ? ? ? ? 1 0 ? 0 a11pk? ? ? ? ? ? 0 a1mpk? ? ? ? ? ? 1 an1pk? ? ? ? ? ? 1 anm +M +M +M +M

2.3 用单纯形法求解下列线性规划问题。

maxz?2x1?x2?x3minz?5x1?2x2?3x3?2x43x?x?x?60?123?x1?2x2?3x3?4x4?7 ?x?x?2x?10 （2） （1）

??123s..t?2x1?2x2?x3?2x4?3s..t??x,x,x,x?0?x1?x2?2x3?20?1234?x,x,x?0?123解：（1）最优解为x*?(15,5,0)T,z*?25。

（2）最优解为x*?(0,1.5,0,0)T,z*??3。

2.4 分别用大M法和两阶段法求解下列线性规划问题。

minz?4x1?x2maxz?2x1?3x2?5x3?3x1?x2?3x?x?x?7?123?4x?3x?x?6 （1） （2） ??123s..t?2x1?5x2?x3?10s..t??x,x,x?0?x1?2x2?x4?4?123??x1,x2,x3,x4?0解：（1）最优解为x*?(6.429,0.571,0)T,z*?14.571。 （2）最优解为x*?(0.4,1.8,1,0)T,z*?3.4。

2.5 写出下列线性规划的对偶问题，并用单纯形法或对偶单纯形法求出对偶问题的最优解。

minz?2x1?2x2?4x3maxz?x1?2x2?3x3?4x4??x1?x2?x3?3x4?5?6x?7x?3x?5x?8 ?1234??12x1?9x2?9x3?9x4?20?x1,x2?0,x3?0,x4无约束??2x1?3x2?5x3?2?3x?x?7x?3 （2） （1）

?123s..t?s..tx?4x?6x?523?1??x1,x2,x3?03

第2章 线性规划及其对偶问题

解：（1）将原问题化为：

max(?z)??2x1?2x2?4x3??2x1?3x2?5x3??2?3x?x?7x?3 ?123s..t??x1?4x2?6x3?5??x1,x2,x3?0设y1,y2,y3分别为三个约束条件对应的对偶变量，则原问题的对偶问题为 min(?w)??2y1?3y2?5y3??2y1?3y2?y3??2??3y?y?4y??2 ?123s..t???5y1?7y2?6y3??4??y1,y2,y3?0整理后得

maxw?2y1?3y2?5y3?2y1?3y2?y3?2?3y?y?4y?2 ?123s..t??5y1?7y2?6y3?4??y1,y2,y3?0求解此问题的初始单纯形表及最终单纯形表分别为表2-3和表2-4。

表2-3 初始单纯形表 cj CB 0 0 0 XB y4 y5 y6 -z b 2 2 4 2 y1 2 [ 3 ] 5 2? -3 y2 -3 -1 -7 -3 -5 y3 -1 -4 -6 -5 0 y4 1 0 0 0 0 y5 0 1 0 0 0 y6 0 0 1 0 ? 1 2/3 4/5

表2-4 最终单纯形表 cj CB 0 2 0 XB y4 y1 y6 -z b 2/3 2/3 2/3 2 y1 0 1 0 0 -3 y2 -7/3 -1/3 -16/3 -7/3 4 -5 y3 5/3 -4/3 -4/3 -7/3 0 y4 1 0 0 0 0 y5 -2/3 1/3 -5/3 -2/3 0 y6 0 0 1 0 ? 第2章 线性规划及其对偶问题

所以，原问题的对偶问题最优解为(2/3,0,0)T,w*=4/3。

（2）令三个约束条件的对偶变量分别为y1,y2,y3，则根据对偶问题的转换法则可直接得到原问题的对偶问题

minw?5y1?8y2?20y3??y1?6y2?12y3?1?y?7y?9y?2 123??s..t??y1?3y2?9y3?3??3y?5y?9y?4123???y1无约束,y2?0,y3?0令y1?y1'?y1'',y2??y2'，则对偶问题转化为

minw?5y1'?5y1''?8y2'?20y3??y1'?y1''?6y2'?12y3?1?y'?y''?7y'?9y?2 1123??s..t??y1'?y1''?3y2?9y3?3??3y'?3y''?5y?9y?41123???y1',y1'',y2',y3?0利用单纯形方法求解此模型（求解过程略），可得此对偶问题无最优解。 2.6 已知线性规划问题

minZ?2x1?3x2?5x3?2x4?3x5?x1?x2?2x3?x4?3x5?4?s..t?2x1?x2?3x3?x4?x5?3?x?0,j?1,2,?,5?j 解：先写出它的对偶问题

**其对偶问题最优解为y1?4/5,y2?3/5;Z*?5。试用对偶理论找出原问题最优解。

maxw?4y1?3y2?y1?2y2?2?y?y?3?12

??2y1?3y2?5s..t??y1?y2?2?3y1?y2?3???y1,y2?0**将y1?4/5,y2?3/5代入约束条件可知，第2、3、4个约束为严格不等式，因

此，由互补松弛性得x2?x3?x4?0。又因为y1,y2?0，所以原问题的两个约束

5

*****第2章 线性规划及其对偶问题

条件应取等式，因此有

**??x1?3x5?4 ? ?**??2x1?x5?3故原问题最优解为X*?(1,0,0,0,1)T,z*?5。

*??x1?1 ?*??x5?12.7 某单位加工制作100套工架，每套工架需用长为2.9m、2.1m和1.5m的圆钢各一根。已知原材料长7.4m。问如何下料使得所用的原材料最省？

解：简单分析可知，在每一根原材料上各截取一根2.9m,2.lm和1.5m的圆钢做成一套工架，每根原材料剩下料头0.9m，要完成100套工架，就需要用100根原材料，共剩余90m料头。若采用套截方案，则可以节省原材料，下面给出了几种可能的套截方案，如表2-5所示。

表2-5 可能的下料方案 方案 A 长度/m 2.9 2.1 1.5 合计/m 料头/m

1 0 3 7.4 0 B 2 0 1 7.3 0.1 C 0 2 2 7.2 0.2 D 1 2 0 7.1 0.3 E 0 1 3 6.6 0.8 实际中，为了保证完成这100套工架，使所用原材料最省，可以混合使用各种下料方案。

设按方案A,B,C,D,E下料的原材料数分别为x1,x2,x3,x4,x5，根据表2-5可以得到下面的线性规划模型

minz?0x1?0.1x2?0.2x3?0.3x4?0.8x5?x1?2x2?x4?100?2x?2x?x?100?345s..t??3x1?x2?2x3?3x5?100??xi?0,i?1,2,3,4,5优值为z*=16。

6

用大M法求解此模型的过程如表2-6所示，最优解为：x*=(0,40,30,20,0)T，最

第2章 线性规划及其对偶问题

表2-6 cj CB -M -M -M XB x6 x7 x8 cj - zj -M -M 0 x6 x7 x1 cj - zj -M -0.3 0 x6 x4 x1 cj - zj -0.1 -0.3 0 x2 x4 x1 cj - zj 10 50 30 50/3 50 100/3 200/3 100 100/3 0 b 100 100 100 x1 1 0 [ 3 ] 4M 0 0 1 0 0 0 1 0 0 0 1 0 -0.1 x2 2 0 1 -0.1 +3M 5/3 0 -0.2 x3 0 2 2 -0.2 +4M -2/3 2 -0.3 x4 1 2 0 -0.3 +3M 1 [ 2 ] 0 -0.3 +3M 0 1 0 0 0 1 0 0 -0.8 x5 0 1 3 -0.8 +4M -1 1 1 -0.8 -3/2 1/2 1 -0.65 -3M/2 -9/10 1/2 13/10 -0.74 -M x6 1 0 0 0 1 0 0 0 1 0 0 0 3/5 0 -M x7 0 1 0 0 0 1 0 0 -1/2 1/2 0 0.15 3M/2 -3/10 1/2 -M x8 0 0 1 0 -1/3 0 1/3 -4M/3 -1/3 0 1/3 -4M/3 -1/5 0 2/5 -M -0.02 θi 100 — 100/3 200/3 100/2 — 150/15 — 100/1 1/3 2/3 -0.1 -0.2 +5M/3 +4M/3 [ 5/3 ] 0 1/3 -0.1 +5M/3 1 0 0 0 -5/3 1 2/3 0.1 -5M/3 -1 1 1 0 -1/5 1/10 -M -M +0.06 +0.12

求解该问题的LINGO程序如下：

model:

sets: row/1..3/:b; arrange/1..5/:x,c; link(row,arrange):a; endsets data:

b=100,100,100; c=1,0.1,0.2,0.3,0.8;

a=1,2,0,1,0,0,0,2,2,1,3,1,2,0,3; enddata

7

第2章 线性规划及其对偶问题

min=@sum(arrange(j):c(j)*x(j));

@for(row(i):@sum(arrange(j):a(i,j)*x(j))=b(i);); end

运行该程序后，也立即可以得到最优解为：x*=(0,40,30,20,0)T，最优值为z*=16。即按方案B下料40根，方案C下料30根，方案D下料20根，共需原材料90根就可以制作完成100套工架，剩余料头最少为16m。

2.8 某工厂要用三种原材料C、P、H混合调配出三种不同规格的产品A、B、D。已知原材料单价及每天能供应的数量、产品的规格要求及产品的单价分别见表2-7和表2-8。该厂应如何安排生产，使利润收入为最大？（本科生仅需建立问题的数学模型）

表2-7 原材料名称 C P H 表2-8 产品名称 A 规格要求 原材料C不少于50% 原材料P不超过25% 原材料C不少于25% B D 原材料P不超过50% 不限 35 25 50 单价（元/kg） 每天最多供应量（kg） 100 100 60 单价（元/kg） 65 25 35

解：如以AC表示产品A中C的成分，AP表示产品A中P的成分，以此类推。 根据表2-8有：

AC?0.5A,AP?0.25A,BC?0.25B,BP?0.5B (1) 此处，

AC?AP?AH?ABC?BP?BH?B (2)

将(2)逐个代入(1)中并整理得到

8

第2章 线性规划及其对偶问题

?0.5AC?0.5AP?0.5AH?0 ?0.25AC?0.75AP?0.25AH?0 ?0.75BC?0.25BP?0.25BH?0 ?0.5BC?0.5BP?0.5BH?0

表2-7表明这些原材料供应的限额。加入到产品A,B,D的原材料C总量每天不超过100kg，P的总量不超过100kg，H的总量不超过60kg。因此有下列的约束

AC?BC?DC?100A?B?C?100

PPPAH?BH?CH?60在约束条件中共有9个变量，为计算和叙述方便，分别用x1,x2,…,x9表示。令

x1?AC,x2?AP,x3?AHx?B,x?B,x?B

4C5P6Hx7?DC,x8?DP,x9?DH则约束条件可表示为

??0.5x1?0.5x2?0.5x3?0??0.25x?0.75x?0.25x?0123???0.75x4?0.25x5?0.25x6?0? ??0.5x4?0.5x5?0.5x6?0??x1?x4?x7?100?x2?x5?x8?100??x3?x6?x9?60?x,?,x?09?1该问题的目标函数可表示为

maxz?50(x1?x2?x3)?35(x4?x5?x6)?25(x7?x8?x9)?65(x1?x4?x7)?25(x2?x5?x7)?35(x3?x6?x9) ??15x1?25x2?15x3?30x4?10x5?40x7?10x9采用LINGO软件求解以上模型，结果为：每天只生产产品A为200kg，需要原材料C,P,H分别为100kg,50kg,50kg。

2.9 某昼夜服务公交公司的公交线路每天各时段内所需要司机和乘务人员如表2-9所示。

9

第2章 线性规划及其对偶问题

表2-9 班次 1 2 3 时间 6:00-10:00 10:00-14:00 14:00-18:00 所需人数 60 70 60 班次 4 5 6 时间 18:00-22:00 22:00-2:00 2:00-6：00 所需人数 50 20 30

设司机和乘务人员分别在各时段开始时上班并连续工作8小时。问该公司公交线路应如何安排司机和乘务人员，使得既能满足工作需要，又使配备的总人数最少？（本科生仅需建立问题的数学模型）

解：设xi为安排从第i班次开始时上班的人数，则该问题的数学模型为

minz??i?1xi?x6?x1?60??x1?x2?70 ?x2?x3?60?s..t?x3?x4?50?x?x?20?45?x5?x6?30??xi?0,i?1,2,...,66求解此模型得到最优解：x?(40,30,30,20,0,30),z?150。

2.10 某投资公司拟制定今后5年的投资计划，初步考虑下面的4个投资项目：

项目A：从第1年到第4年每年年初需要投资，于次年年末收回成本并可获利15%；

项目B：第3年年初需要投资，到第5年年末可以回收成本并获利25%，但为了保证足够的资金流动，规定该项目的投资金额上限为不超过总金额的40%；

项目C：第2年年初需要投资，到第5年年末可以回收成本并获利40%，但公司规定该项目的最大投资金额不超过总金额的30%；

项目D：5年内每年年初可以购买公债，于当年年末可以归还本金并获利息6%。 该公司现有投资金额100万元，请你帮助该公司制定这些项目每年的投资计划，使公司到第5年年末能够获得最大的利润。（本科生仅需建立问题的数学模型）

解：用决策变量xi1,xi2,xi3,xi4 (i=1,2,…,5)分别表示第i年年初为项目A,B,C,D的投资额。根据问题的要求，各变量的对应关系如表2-10所示。表中空白处表示当年不能为该项目投资，也可认为投资额为0。

10

*T*第2章 线性规划及其对偶问题

表2-10 各变量的对应关系 年份 1 项目 A B C D

x11 x14 2 x21 x23 x24 3 x31 x32 x34 4 x41 x44 5 x54 首先注意到，项目D每年都可以投资，并且当年末就能收回本息，所以公司每年应把全部资金都投出去，因此，投资方案应满足下面的条件。 第1年：将100万元资金全部用于项目A和项目D的投资，即

x11＋x14＝1000000

第2年：因为第1年用于项目A的投资到第2年年末才能收回，所以能用于第2年年初的投资金额只有项目D的第1年收回的本息总额为 (1+0.06) x14。于是第2年的投资分配为

x21＋x23＋x24＝1.06x14

第3年：第3年投资金额应是项目A第1年及项目D第2年收回的本利总和，即 (1+0.15) x11+(1+0.06) x24。于是第3年的投资分配为

x31＋x32＋x34＝1.15x11+1.06x24

第4年：类似地，有

x41＋x44＝1.15x21＋1.06x34

第5年：只能将第4年收回的资金全部用于项目D投资，即

x54 = 1.15x31＋1.06x44

另外，对项目B和项目C的投资金额有上额限制，即

x32≤400000，x23≤300000

问题的目标是要求到第5年年末公司收回四个项目的全部资金总和最大，即

max z＝1.15x41+1.25x32+1.40x23+1.06x54

于是可以得到问题的线性规划模型为

11

第2章 线性规划及其对偶问题

maxz?1.15x41?1.25x32?1.40x23?1.06x54?x11?x14?1000000??1.06x?x?x?x?014212324???1.15x11?1.06x24?x31?x32?x34?0 ??1.15x?1.06x?x?x?0?21344144s..t???1.15x31?1.06x44?x54?0?x32?400000??x23?300000?x,x,x,x?0(i?1,2,3,4,5)?i1i2i3i4 利用LINGO软件求解该模型，得到最优解为x11=716981.1,x14=283018.9, x23=300000, x31=424528.3,x32 =400000,x51=488207.5，其他的均为0。最优值为z=1437500。即连续投资方案为：第1年用于投资项目A的金额为716981.1元，项目D的金额为283018.9元；第2年用于项目C的投资金额为300000元；第3年用于项目A的投资金额为424528.3元，项目B的金额为400000元；第5年用于投资项目D的金额为488207.5。到第5年年末该公司拥有总资金为1437500元，收益率为43.75%。

2.11 某工厂生产n种产品(i?1,2,?,n)，上半年各月对每种产品的最大市场需求量为dij(i?1,2,?,n;j?1,2,?,6)。已知每件产品的单价为Si元，生产每件产品所需工时为ai，单件成本为Ci元；该工厂上半年各月正常生产工时为

''rj(j?1,2,?,6)，各月内允许的最大加班工时为rj；Ci为加班单件成本。又每月

生产的各种产品如当月销售不完，可以库存。库存费用为Hi（元/件?月）。假设1月初所有产品的库存为零，要求6月底各产品的库存量分别为ki件。现要求为该厂制定一个生产库存计划，在尽可能利用生产能力的条件下，获取最大利润。试建立该问题的数学模型。

'解：设xij,xij分别为该厂第i种产品的第j个月在正常时间和加班时间内的生产量；yij为i种产品在第j月的销售量，wij为第i种产品第j月末的库存量。依题意有： 目标函数

maxz???(Siyij?Cixij?Cx)???Hiwij

''iiji?1j?1i?1j?15655 约束条件

（1）各种产品每月的生产量不能超过允许的生产能力，即

5?i?1aixij?rj(j?1,2,...,6)

12

第2章 线性规划及其对偶问题

?5''ax?r(j?1,2,...,6) iijji?1（2）各种产品每月销售量不超过市场最大需求量，即 yij?dij?i,j

（3）每月末库存量登月上月末库存量加上该月产量减去当月销售量

'wij?wi,j?1?xij?xij?yij?i,j 其中，wi0?0,wi6?ki。

非负条件

'xij,xij,yij,wij?0?i,j

2.12 现有线性规划问题

maxz??5x1?5x2?13x3??x1?x2?3x3?20 ?s..t?12x1?4x2?10x3?90?x,x,x?0?123 （1）约束条件①的右端项系数由20变为30；

（2）约束条件②的右端项系数由90变为70；

（3）目标函数中x3的系数由13变为8； （4）x1的系数列向量由(?1,12)变为(0,5)； （5）将原约束条件②改变为10x1?5x2?10x3?100； （6）增加一个约束条件2x1?3x2?5x3?50。

解：在上述LP问题的第①、②个约束条件中分别加入松弛变量x4,x5得

maxz??5x1?5x2?13x3?0x4?0x5TT① ②

先用单纯形法求出最优解，然后分析在下列各种条件下，最优解分别有什么变化？

?20??x1?x2?3x3?x4?s..t?12x1?4x2?10x3?x5?90?x,x,x,x,x?0?12345

列出此问题的初始单纯形表并进行迭代运算，过程如表2-11所示。

由表2-11中的计算结果可知，LP问题的最优解X*=(0,20,0,0,10)T，z*=5*20=100。

（1）约束条件①的右端项系数由20变为30，则有

?10??30??30?B?1b????90????30? ?41??????列出单纯形表，并利用对偶单纯形法求解，过程如表2-12所示。

13

第2章 线性规划及其对偶问题

表2-11 cj CB 0 0 XB x4 x5 cj-zj 13 0 x3 x5 cj-zj 5 0 x2 x5 cj-zj

表2-12 cj CB 5 0 XB x2 X5 cj-zj 5 13 x2 x3 cj-zj 0 13 x4 x3 cj-zj

3 9 -15 15 b 30 -30 -5 x1 -1 16 0 23 -8 -16 -23/5 6/5 -103/5 5 x2 1 0 0 1 0 0 -1/5 2/5 -1/5 13 x3 3 [ -2 ] -2 0 1 0 0 1 0 0 x4 1 -4 -5 [ -5 ] 2 -1 1 0 0 0 x5 0 1 0 3/2 -1/2 -1 -3/10 1/10 -13/10 20 10 20/3 70/3 b 20 90 -5 x1 -1 12 -5 -1/3 46/3 -2/3 -1 16 0 5 x2 1 4 5 [ 1/3 ] 2/3 2/3 1 0 0 13 x3 [ 3 ] 10 13 1 0 0 3 -2 -2 0 x4 1 0 0 1/3 -10/3 -13/3 1 -4 -5 0 x5 0 1 0 0 1 0 0 1 0 θi 20/3 9 20 35 由表2-12中计算结果可知，LP问题的最优解变为

X*?(0,0,9,3,0)T,z*?13?9?117。

（2）约束条件②的右端常数由90变为70，则有

?10??20??20?B?1b????????

?4170?10??????列出单纯形表，并利用对偶单纯形法求解，结果如表2-13所示。

14

第2章 线性规划及其对偶问题

表2-13 cj CB 5 0 XB x2 X5 cj-zj 5 13 x2 x3 cj-zj

5 5 b 20 -10 -5 x1 -1 16 0 23 -8 -16 5 x2 1 0 0 1 0 0 13 x3 3 [ -2 ] -2 0 1 0 0 x4 1 -4 -5 -5 2 -1 0 x5 0 1 0 3/2 -1/2 -1 由表2-13结果知，LP问题的最优解变为

X*?(0,5,5,0,0)T,z*?5?5?13?5?90。

（3）目标函数中x3的系数由13变为8，由于x3是非基变量，其检验数变为

?3?8?5?3?0?(?2)??7?0 所以LP问题的最优解不变。

（4）x1的系数列向量由(-1,12)T变为(0,5) T，则x1在最终单纯形表中的系数列向量变为

?10??0??0? 'B?1P?1??41??5???5???????从而x1在最终单纯形表中的检验数变为

' ?1'?c1?CBB?1P1??5?(5,0)????5?05?0???所以LP问题的最优解保持不变。

（5）将原约束条件②改变为10x1+5x2+10x3≤100，则x1在最终单纯形表中系数

'?1列向量变为P,14)T，检验数?1'?c1?CBB?1P,14)T?0 1?BP1?(?11??5?(5,0)(?1'?1x2在最终单纯形表中系数列向量变为P,1)T，检验数2?BP2?(1'?2?c2?CBB?1P,1)T?0。 2?5?(5,0)(110??20??20?又因B?1b??的各分量均大于0，故LP问题的最优解不变。

??41??100???20??????? （6）增加一个约束条件2x1+3x2+5x3≤50，则在此约束条件中加入松弛变量x6，并将此约束加入到最终单纯形表中，继续迭代，过程如表2-14所示。

由表2-14中计算结果可知，LP问题的最优解变为X*?(0,25/2,5/2,0,15,0)T，

15

第2章 线性规划及其对偶问题

z*?5?25/2?13?5/2?95。

表2-14 cj CB 5 0 0 5 0 0 XB x2 x5 x6 x2 x5 x6 cj - zj 5 0 13 x2 x5 x3 cj - zj 25/2 15 5/2 b 20 10 50 20 10 -10 -5 x1 -1 16 2 -1 16 5 0 11/4 27/2 -5/4 -5/2 5 x2 1 0 3 1 0 0 0 1 0 0 0 13 x3 3 -2 5 3 -2 [ -4 ] -2 0 0 1 0 0 x4 1 -4 0 1 -4 -3 -5 -5/4 -5/2 3/4 -7/2 0 x5 0 1 0 0 1 0 0 0 1 0 0 0 x6 0 0 1 0 0 1 0 3/4 -1/2 -1/4 -1/2

2.13 已知某工厂生产I、II、III三种产品，各产品需要在A、B、C设备上加工，有关数据如表2-15所示。

表2-15 设备代号 A B C 单位产品利润（千元） I 8 10 2 3 II 2 5 13 2 III 10 8 10 2.9 设备有效台时/月 300 400 420 试回答：

（1）如何充分发挥设备能力使生产盈利最大？

（2）若为了增加产量，可借用其他工厂的设备B，每月可借用60台时，租金为1.8万元，问借用B设备是否合算？

（3）若另有两种产品IV和V，其中IV需用设备A—12台时、B—5台时、C—10

16

第2章 线性规划及其对偶问题

台时，单位产品盈利2.1千元；新产品V需用设备A—4台时、B—2台时、C—12台时，单位产品盈利1.87千元。如A、B、C设备台时不增加，分别回答这两种新产品投产在经济上是否合算？

（4）对产品工艺进行设计，改进结构。改进后生产每件产品I需用设备A—9台时、B—12台时、C—4台时，单位产品盈利4.5千元。问这对原计划有何影响？

解：（1）设I,II,III三种产品的生产量分别为x1,x2,x3，依题意可列出问题的LP模型：

maxz?3x1?2x2?2.9x3?8x1?2x2?10x3?300?10x?5x?8x?400 ?123s..t??2x1?13x2?10x3?420??x1,x2,x3?0在上述模型的各约束条件中分别加入松弛变量x4,x5,x6得：

maxz?3x1?2x2?2.9x3?0x5?0x6?300?8x1?2x2?10x3?x4?10x?5x?8x?x5?400 ?123s..t??x6?420?2x1?13x2?10x3??x1~6?0列出初始单纯形表，并进行迭代运算，最终单纯形表如表2-16所示：

表2-16 cj CB 3 2 2.9 XB x1 x2 x3 cj - zj

b 338/15 116/5 22/3 -5 x1 1 0 0 0 5 x2 0 1 0 0 13 x3 0 0 1 0 0 x4 -9/100 -7/50 1/5 -3/100 0 x5 11/60 1/10 -1/6 -4/15 0 x6 -17/300 3/50 1/30 -7/150 θi T33811822 从表2-16可得，LP问题的最优解为X??,,,0,?1553?2029z*??135.27。

15*?，0?,0?（2）由最终单纯形表知，设备B的影子价格为4/15(千元/台时)，而借用设备B的租金为18/60=0.3>4/15，所以借用设备B不合算。

17

第2章 线性规划及其对偶问题

（3）设产品IV和V的产量分别为x7、x8，则x7在最终单纯形表中的系数列向量为

?9??100?7'?1P7?BP7????50?1???5故生产产品IV在经济上不合算；

11601101?6?17??73??300??12??100????3????29?

5????50?50?????10??1????19????30??10?''从而x7在最终单纯形表中的检验数?7，?c7?CBB?1P7?2.1?(3,2,2.9)P7??0.06?0 x8在最终单纯形表中的系数列向量为

1117??9?23?????10060300??4??75?????71314???4??? P8'?B?1P8??????501050????25????12???1118?????????630??5?15?''检验数为?8，所以生产产品V在经济上?c8?CBB?1P8?1.87?(3,2,2.9)P8?0.12?0是合算的。把x8的系数列向量加入到最终单纯形表中，并进行迭代计算，过程如表2-17所示。

表2-17 cj CB 3 2 2.9 XB x1 x2 x3 cj - zj 3 2 1.87 x1 x2 x8 cj - zj

107/4 31/2 55/4 b 338/15 116/5 22/3 -5 x1 1 0 0 0 1 0 0 0 5 x2 0 1 0 0 0 1 0 0 13 x3 0 0 1 0 23/40 -21/20 15/8 -41/40 0 x4 -9/100 -7/50 1/5 -3/100 1/40 -7/20 3/8 -3/40 0 x5 11/60 1/10 -1/6 -4/15 21/240 11/40 -5/16 0 x6 -17/300 3/50 1/30 -7/150 -3/80 1/40 1/16 0 x8 -23/75 14/25 [ 8/15 ] 3/25 0 0 1 0 θi — 290/7 77/12 T-73/320 -827/1600 1073155?由表2-17可知，线性规划问题的最优解为X??,,0,0,0,0,0,?，?4??42*18

第4章 目标规划

基，用最小比值原理确定d3?出基。换基后，计算的新的基本可行解如表4-6所示。

表4-6 cj CB P1 0 0 2.5P3 XB b 20 10 50 44 P1 σj P2 P3 P4

0 x1 0 0 1 0 0 0 0 0 0 x2 [ 1 ] 0 0 1 -1 0 -2.5 0 P1 P4 0 P2 4P3 2.5P3 d1 1 0 0 0 0 0 0 0 ?d1 -1 1 0 0 1 0 0 1 ?d2 0 1 0 0 0 0 0 0 ?d2 0 -1 0 0 0 1 0 0 ?d3 -1 0 1 0 1 0 4 0 ?d4 0 0 0 1 0 0 0 0 ?? 20 — — 44 d1 d2 x1 ??d4 ?可见只有x2的检验数小于零，因此x2进基，用最小比值法确定d1?出基。换基后，求得新的基本可行解如表4-7所示。

表4-7 cj CB 0 0 0 2.5P3 XB x2 ?0 b 20 10 50 24 P1 x1 0 0 1 0 0 0 0 0 0 x2 1 0 0 0 0 0 0 0 P1 P4 0 P2 4P3 2.5P3 d1 1 0 0 -1 1 0 2.5 0 ?d1 -1 [ 1 ] 0 1 0 0 -2.5 1 ?d2 0 1 0 0 0 0 0 0 ?d2 0 -1 0 0 0 1 0 0 ?d3 -1 0 1 1 0 0 1.5 0 ?d4 0 0 0 1 0 0 0 0 ?? — 10 — 24 d2 x1 d4 ?σj P2 P3 P4

?同样的方法确定d1?进基，d2出基，换基后，计算得到新的基本可行解如表4-8

所示。

44

第4章 目标规划

表4-8 cj CB 0 P4 0 2.5P3 XB x2 ?0 b 30 10 50 14 P1 x1 0 0 1 0 0 0 0 0 0 x2 1 0 0 0 0 0 0 0 P1 P4 0 P2 4P3 2.5P3 d1 1 0 0 -1 1 0 2.5 0 ?d1 0 1 0 0 0 0 0 0 ?d2 1 1 0 -1 0 0 2.5 -1 ?d2 -1 -1 0 1 0 1 -2.5 1 ?d3 -1 0 1 1 0 0 1.5 0 ?d4 0 0 0 1 0 0 0 0 ?? d1 x1 d4 ?σj P2 P3 P4

所有变量的检验数的最高优先级系数都已大于等于零，因此获得了满意解，结

?果是：x1=50,x2=30, d1?=10, d2=14，其他偏差变量等于零。

4.3 某厂生产A、B、C三种产品，装配工作在同一生产线上完成，三种产品时的工时消耗分别为6、8、10小时，生产线每月正常工作时间为200小时；三种产品销售后，每台可获利分别为500、650和800元；每月销售量预计为12、10和6台。

该厂经营目标如下：（1）利润指标为每月16000元，争取超额完成；（2）充分利用现有生产能力；（3）可以适当加班，但加班时间不得超过24小时；（4）产量以预计销售量为准。试建立目标规划模型。

解：该问题的数学模型如下：

minZ?p1d1??p2d2??p3d3?? p4(d4??d4??d5??d5??d6??d6?)?500x1?650x2?800x3?d1??d1??16000????6x1?8x2?10x3?d2?d2?200?d??d??d??2433?2? s.t. ?x1?d4??d4??12????x2?d5?d5?10?x?d??d??666 ?3????x1,x2,x3?0,di,di?0(i?1,2,?,6)4.4 已知条件如表4-9所示。如果工厂经营目标的期望值和优先等级如下： P1: 每周总利润不得低于10000元；

45

第4章 目标规划

P2: 因合同要求，A型机每周至少生产10台，B型机每周至少生产15台； P3: 希望工序Ⅰ的每周生产时间正好为150小时，工序Ⅱ的生产时间最好用足，甚至可适当加班。

试建立这个问题的目标规划模型。

表4-9 型号 工序 A I(小时/台) II(小时/台) 利润(元/台)

4 3 300 B 6 2 450 加工能力 150 70 每周最大 如果工序Ⅱ在加班时间内生产出来的产品，每台A型机减少利润20元，每台B型机减少利润25元，并且工序Ⅱ的加班时间每周最多不超过30小时，这是P4级目标，试重新建立这个问题的目标规划模型。

解：目标规划模型：

?min f?p1d1??p2(300d2?450d3?)?p3(d4??d4??d5?)?300x1?450x2?d1??d1??10000???? x1 ?d2?d2?10? x ?d??d??15?233s.t. ???? 4x1 ?6x2?d4?d4?150? 3x ?2x?d??d??70255?1????x1,x2,di,di?0 i?1,2,3,4,5

设x1,x2分别为在正常时间和加班时间生产A型机台数，x3,x4 分别为在正常时间和加班时间生产B型机台数，目标规划数学模型为：

min f?p1d1??p2(300d2??450d3?)?p3(d4??d4??d5?)?p4d6??300x1?280x2?450x3?425x4?d1??d1??10000???? x1 ?x2 ?d2?d2?10? x ?x ?d??d??153433????s..t? 4x1 ?4x2 ?6x3 ?6x4 ?d4?d4?150???? 3x1 ?3x2 ?2x3 ?2x4?d5?d5?70? d??d??d??30566?????x1,x2,x3,x4,di,di?0 i?1,2,3,4,5,646

4.5某计算机公司生产三种型号的笔记本电脑A,B,C。这三种笔记本电脑需要

第4章 目标规划

在复杂的装配线上生产，生产1台A,B,C型号的笔记本电脑分别需要5，8,12(小时)。公司装配线正常的生产时间是每月1700小时。公司营业部门估计A,B,C三种笔记本电脑的利润分别是每台1000,1440,2520(元），而公司预测这个月生产的笔记本电脑能够全部售出。公司经理考虑以下目标：

第一目标：充分利用正常的生产能力，避免开工不足；

第二目标：优先满足老客户的需求，A,B,C三种型号的电脑50,50,80（台），同时根据三种电脑的纯利润分配不同的权因子；

第三目标：限制装配线加班时间，不允许超过200小时；

第四目标：满足各种型号电脑的销售目标，A,B,C型号分别为100,120,100(台），再根据三种电脑的纯利润分配不同的权因子； 第五目标：装配线的加班时间尽可能少。 请列出相应的目标规划模型。 解：建立目标约束

（1)装配线正常生产

设生产A,B,C型号的电脑为x1,x2,x3(台)，d1?为装配线正常生产时间未利用数，

d1?为装配线加班时间，希望装配线正常生产，避免开工不足，因此装配线目标约

束为

mind1?s..t5x1?8x2?12x3?d?d?1700 (2)销售目标

?1?1

优先满足老客户的需求．并根据三种电脑的纯利润分配不同的权因子，A,B,C三种型号的电脑每小时的利润是1000/5,1440/8,2520/12，因此，老客户的销售目标约束为

??min20d2?18d3??21d4???x1?d2?d2?50?s..t?x2?d3??d3??50????x3?d4?d4?80

再考虑一般销售。类似上面的讨论，得到

min20d5??18d6??21d7??x1?d5??d5??100 ???s..t?x2?d6?d6?120????x3?d7?d7?100(3)加班限制首先是限制装配线加班时间，不允许超过200小时，因此得到

47

第4章 目标规划

mind8?s..t5x1?8x2?12x3?d?d?1900其次装配线的加班时间尽可能少，即 mind1??8?8

s..t5x1?8x2?12x3?d?d?1700?1?1

写出目标规划的数学模型：

?????minz?Pd11?P2(20d2?18d3?21d4)?P3d8?P4(20d5??18d6??21d7?)?P5d1??5x1?8x2?12x3?d1??d1??1700????x1?d2?d2?50?x?d??d??5033?2???x3?d4?d4?80??s..t?x1?d5??d5??100???x?d?d?120266??x?d??d??10077?3?5x1?8x2?12x3?d8??d8??1900???x,x,d,d?0,i?1,2,?,8?12ii?写出相应的LINGO程序，清单如下：（研究生选用）

MODEL: 1]sets:

2] Level/1..5/:P,z,Goal; 3] Variable/1..3/:x;

4] S_Con_Num/1..8/:g,dplus,dminus; 5] S_Cons(S_Con_Num,Variable):C; 6] obj(Level,S_Con_Num):Wpluse,Wminus; 7]endsets 8]data:

9] P=? ? ? ? ?; 10] Goal=? ? ? ? 0;

11] g=1700 50 50 80 100 120 100 190;

12] C=5 8 12 1 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 1 5 8 12; 13] Wpluse=0 0 0 0 0 0 0 0 14] 0 0 0 0 0 0 0 0

48

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库运筹习题参考答案在线全文阅读。