运筹习题参考答案

《实用管理运筹学》

习题参考答案

沈阳航空航天大学 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

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

z*?10957?136.96。 80（4）改进后c1=4.5，P1=(9,12,4)T，x1在最终单纯形表中的系数列向量为

1117??9?349????10060300??9??100?????7139'?1???12???? P1?BP1?????50?501050??????4???1?111??????????630??5?15?'x1在最终单纯形表中的检验数为?1'?c1?CBB?1P，所1?4.5?(3,2,2.9)P1?0.843?0以改进后能带来更多的经济效益。

19

第3章整数规划与运输问题

3.1 分别用分支定界法和割平面法求解下列整数规划模型。 （1）minz??4x1?3x2 （2）maxz?x1?x2

?4x1?x2?10? s..s..t?2x1?3x2?8t?x,x?0,且为整数?12?2x1?x2?6? ?4x1?5x2?20?x,x?0,且为整数?12**解：（1）求解得到最优解x1（计算步骤略） ?2,x2?1,z*??11。

割平面法：在原IP问题约束条件中加入松弛变量x3,x4，化为标准型，可得

maxz?4x1?3x2?0x3?0x4?10?4x1?x2?x3

?s..t?2x1?3x2??x4?8?x,x,x,x?0且为整数?1234不考虑整数条件，用单纯形法求解原问题的松弛问题，计算结果如下表所示。

cj CB 0 0 XB x3 x4 cj-zj 4 0 x1 x4 cj-zj 4 3 x1 x2 cj-zj 2.2 6/5 2.5 3 b 10 8 4 x1 [ 4 ] 2 4 1 0 0 1 0 0 3 x2 1 3 3 0.25 [ 2.5 ] 2 0 1 0 0 x3 1 0 0 0.25 -0.5 -1 0.3 -1/5 -0.6 0 x4 0 1 0 0 1 0 -0.1 2/5 -0.8 ?i 5/2 4 10 3/2.5

因此，松弛问题的最优解为x1=2.2, x2=1.2, x3=0, x4=0; z=-12.4。 由于x2不为整数，因此在最终单纯形表中根据x2所在的行作割平面

1/5?1/5*(4x3?2x4)?0 即

20

第3章 整数规划与运输问题

?4x3?2x4??1

将它作为约束条件，引入松弛变量后加到最终单纯形表中，并采用对偶单纯形法继续迭代，计算过程如下表所示。

表3-2 cj CB 4 3 0 XB x1 x2 x5 cj-zj 4 3 0 x1 x2 x3 cj-zj 4 3 0 x1 x2 x4 cj-zj

1.575 1.65 0.5 1.45 1.7 0.25 b 2.2 6/5 -1 4 x1 1 0 0 0 1 0 0 0 1 0 0 0 3 x2 0 1 0 0 0 1 0 0 0 1 0 0 0 x3 0.3 -1/5 [ -4 ] -0.6 0 0 1 0 0.5 -0.6 2 0 x4 -0.1 2/5 -2 -0.8 -0.25 0.3 [ 0.5 ] 0.1 0 0 1 0 x5 0 0 1 0 0.75 -0.05 -0.25 -2.85 0.625 -0.2 -0.5 由于x1,x2的值均为整数，所以得到原问题的最优解为x*?(2,2)T,z*?4

（2）仅写出利用割平面法求解的过程。

在原IP问题约束条件中加入松弛变量x3,x4，化为标准型，可得

maxz?x1?x2?0x3?0x4?6?2x1?x2?x3

?s..t?4x1?5x2??x4?20?x,x,x,x?0且为整数?1234不考虑整数条件，用单纯形法求解原问题的松弛问题，计算结果如表3-1所示。

21

第3章 整数规划与运输问题

表3-1 cj CB 0 0 XB x3 x4 cj-zj 0 1 x3 x2 cj-zj 1 1 x1 x2 cj-zj 5/3 8/3 2 4 b 6 20 1 x1 2 4 1 [ 6/5 ] 4/5 1/5 1 0 0 1 x2 1 [ 5 ] 1 0 1 0 0 1 0 0 x3 1 0 0 1 0 0 5/6 -2/3 -1/6 0 x4 0 1 0 -1/5 1/5 -1/5 -1/6 1/3 -1/30 ?i 6 4 5/3 5

因此，松弛问题的最优解为x1=5/3,x2=8/3,x3=0,x4=0;z=13/3。 由于x2不为整数，因此在最终单纯形表中根据x2所在的行作割平面

2/3?1/3(x3?x4)?0 即

?x3?x4??2

将它作为约束条件，引入松弛变量后加到最终单纯形表中，并采用对偶单纯形法继续迭代，计算过程如表3-2所示。

表3-2 cj CB 1 1 0 XB x1 x2 x5 cj-zj 1 1 0 x1 x2 x4 2 2 2 b 5/3 8/3 -2 1 x1 1 0 0 0 1 0 0 1 x2 0 1 0 0 0 1 0 22

0 x3 5/6 -2/3 -1 -1/6 1 -1 1 0 x4 -1/6 1/3 [ -1 ] -1/30 0 0 1 0 x5 0 0 1 0 -1/6 1/3 -1 第3章 整数规划与运输问题

cj-zj

0 0 0 0 -1/6 由于x1,x2的值均为整数，所以得到原问题的最优解为x*?(2,2)T,z*?4 3.2 解0-1整数规划

maxz?2x1?5x2?3x3?4x4??4x1?x2?x3?x4?0??2x?4x?2x?4x?4 ?1234s..t??x1?x2?x3?x4?1??x1,x2,x3,x4?0或1解：重排决策变量的顺序，得如下的模型： maxz?2x1?3x3?4x4?5x2??4x1?x3?x4?x2?0??2x?2x?4x?4x?4 ?1342s..t??x1?x3?x4?x2?1??x1,x2,x3,x4?0或1目标函数可能取得的值从大到小的排列顺序为14、12、11、10、9、8、7、6、5、

4、3、2、0，对应的变量取值（按x1,x3,x4,x2得顺序排列）依次为(1,1,1,1)、(0,1,1,1)、(1,0,1,1)、(1,1,0,1)、??，将变量的可能取值依次带入约束条件可得，(0,1,1,1)第一次满足所有的约束条件，即(x1,x3,x4,x2)?(0,1,1,1)为问题的最优解，因此原问题的最优解为x*?(0,1,1,1)T,z*?12。

3.3某汽车工厂的一条生产线上生产两种轿车A和B。生产A型车需要钢材2吨、工时3小时；B型车需钢材4吨、工时2小时。已知该厂每周可提供钢材80吨、工时55小时。根据目前市场情况，A型车每周最大销售量为16辆，每辆可获利60千元，B型车每周最大销售量为18辆，每辆可获利50千元。试制定该厂的周生产计划以使利润最大。

解：设每周生产A型车x辆，B型车y辆，则整数规划模型为：

maxz?60x?50y?2x?4y?80?3x?2y?55? ?(D)s.t.?x?16?y?18???x,y?0且为整数(1)用线性规划求解其松弛问题

23

第3章 整数规划与运输问题

利用图解法或单纯形法可以很快得到松弛问题的最优解为（7.5,16.25),利润值为Z=1262.5（千元）。

在上面的原问题中分别增加x≤7和x≥8两个约束条件完成分支过程，它们是

maxz?60x?50ymaxz?6x0?y50?2x?4y?80?3x?2y?55??x?16

(D1)s.t.??y?18?x?7??x,y?0且为整数1数，故zu?1245。

?2x?4y?80?3x?2y?55??x?16

(D2)s.t.??y?18?x?8??x,y?0且为整数子问题D1的松弛问题D1的最优解为x=7,y=16.5。因其中一个变量仍然为非整子问题D2的松弛问题D2的最优解为x=8,y=15.5。因其中一个变量仍然为非整

2数，故zu?1255。

（2）第2次分支：取zu值较大的D2进行分支。分别增加约束y≤15和y≥16将D2分支为D3和D4。

maxz?60x?50ymaxz?6x0?y50?2x?4y?80?2x?4y?80?3x?2y?55?3x?2y?55???x?16?x?16 ??(D3)s.t.?y?18(D4)s.t.?y?18?x?8?x?8???y?15?y?16?x,y?0且为整数?x,y?0且为整数??用图解法或单纯形法求出它们的松弛问题的解

3?1250,zL?0 D3:x=8.33,y=15; zuD4:无可行解，D4分支停止

13（3）在现有的分支D1,D3中选择zu和zu两者中大的子问题D3继续进行分支。

分别增加约束x≤8和x≥9产生子问题D5和D6。

24

第3章 整数规划与运输问题

maxz?60x?50ymaxz?6x0?y50?2x?4y?80?2x?4y?80?3x?2y?55?3x?2y?55???x?16?x?16?? ?y?18?y?18(D5)s.t.?(D6)s.t.??x?8?x?8?y?15?y?15??x?8??x?9?x,y?0且为整数?x,y?0且为整数??用图解法或单纯形法求出它们的松弛问题的解

5?1230,zL?1230 D5:x=8,y=15; zu6?1240,zL?1240。 D6: x=9,y=14; zu5 （4）在现有的分支D1,D5和D6中，因zu?zL，故D5子问题停止分支，而1zu?zL，故仍继续对子问题D1进行分支。增加约束y≤16和y≥17，将D1分支为

D7和D8：

maxz?60x?50ymaxz?6x0?y50?2x?4y?80?2x?4y?80?3x?2y?55?3x?2y?55???x?16?x?16 ??(D5)s.t.?y?18(D5)s.t.?y?18?x?7?x?7???y?16?y?17?x,y?0且为整数?x,y?0且为整数??用图解法或单纯形法求出它们的松弛问题的解

7?1220,zL?1240 D7:x=7,y=16; zu8?1210,zL?1240 D8: x=6,y=17; zu（5）检查现有的各分支中，已不存在zu大于zL的分支，因此整个分支过程停止。该整数规划问题(D)的最优解在D6分支中得到，其最优解为x=9, y=14,

zL=1240。

3.4 某厂新购4台不同类型机器，可以把它们安装在4个不同的地点。由于对特定的机器而言，某些地方可能安装起来特别方便且合适，所以不同的机器安装在不同的地点费用是不同的。估计的费用见表3-3，试制定使得总安装费用最小的安

25

第3章 整数规划与运输问题

装方案。

表3-3 （费用单位：元） 地点 1 2 3 4 机器总数 机器 1 2 3 4 需要量 10 3 2 4 1 9 4 1 3 1 8 5 1 5 1 7 6 2 6 1 1 1 1 1

?1,如果机器i安装在地点j解：设 xij??

?0,否则cij—机器i安装在地点j所需的费用。建立该问题的数学模型如下：

目标函数：

minz???i?144j?1ijijcx

x?1i?1,2,3,4 ?1j?1,2,3,4

约束条件：

? (2)每一个地点只能有一台机器，即 ?x(1)每一部机器只分配在一个地点，即

44j?1iji?1ij (3) xij?0或1

工作指派问题可以看成是一类特殊的运输问题，每个供应点的供应量为1，每个需求点的需求量也为1。因此，本题可以采用表上作业法进行计算，也可以利用匈牙利法进行计算。计算得到的最佳安装方案为：机器1安装在地点4、机器2安装在地点1、机器3安装在地点3、机器4安装在地点2，最小总安装费为14元。

3.5某港务局装卸队在安排所属五个班组进行五条作业线的配工时，先把以往各班组完成某项作业的实际效率的具体数据列出如表3-4。

表3-4 单位：吨 项目 “风益”4舱 “铜川”1舱 “风益”2舱 “汉川”5舱 “汉川”3舱 组别 卸钢材 卸化肥 卸卷纸 装 砂 装 杂 1组 2组 3组 400 435 505 315 295 370 26

220 240 320 120 220 200 145 160 165 第3章 整数规划与运输问题

4组 5组

495 450 310 320 250 310 180 190 135 100 试安排一个效率最高的配工方案。

解：(1)因为我们要求得到装卸的最大吨位（是求极大值问题），所以用表中最大的数505减去每一个元素后得到下列5阶矩阵表格（见表3-5）。

表3-5

105 70 0 10 55 190 210 135 195 185 285 265 185 255 195 385 285 305 325 315 360 345 340 370 405

(2)进行行约简和列约简后得到表3-6。

表3-6

0 0 0 0 0

0 55 50 100 45

40 55 45 105 0

65 0 90 100 45

0 20 85 105 95

(3)试求最优解，如表3-7所示。

表3-7

27

第3章 整数规划与运输问题

因为圈出的0元素数目为4个，小于5，故画最小覆盖线，如表中虚线所示，共4条。因覆盖线数少于矩阵的阶数，所以变换矩阵，增加0元素。

(4)变换矩阵，增加0元素。从未被覆盖的元素中选出最小元素45，然后从未被覆盖的每个元素中减去45，两条覆盖线相交的元素加上45，得到表3-8。再试找最优解，只能圈出4个0元素。因为少于5个，故再用前法画最少覆盖线(见表3-8)。

因覆盖线的数目仍少于矩阵的阶数，继续变换矩阵增加0元素。从未被覆盖的每个元素中减去5，两条覆盖线相交的4个元素加5后得到表3-9。

(5)试求最优解。如表3-9，取的顺序是x24,x41,x53,x32,x15，共5个0元素，因此找到了最优解，算法结束。

表3-8

表3-9

28

第3章 整数规划与运输问题

即最优配工方案是：1组在“汉川”3舱装杂货145吨；2组在“汉川”5舱装砂220吨；3组在“铜川”1舱卸化肥370吨；4组在“风益\舱卸钢材495吨；5组在“风益\舱卸卷纸310吨。5个组完成的总吨位是145+220+370+495+310=1540吨。

3.6 有4名同学到一家公司参加三个阶段的面试。公司要求每个同学都必须首先找公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，并且不允许插队（即在任何一个阶段4名同学的顺序是一样的）。由于4名同学的专业背景不同，所以每人在三个阶段的面试时间也不相同，如表3-10所示。这4名同学约定他们全部面试完以后一起离开公司。假定现在时间是早晨8:00，请问他们最早何时能离开公司？（本科生仅需建立问题的数学模型）

表3-10 单位：min 同学甲 同学乙 同学丙 同学丁 秘书初试 13 10 20 8 主管复试 15 20 16 10 经理面试 20 18 10 15

解：建立模型

实际上，这个问题就是要安排4名同学的面试顺序，使完成全部面试所花费的时间最少。

记tij为第i名同学参加第j阶段面试需要的时间(已知)，令xi表示第i名同学参加第j阶段面试的开始时刻(不妨记早上8:00面试开始为0时刻)(i=1,2,3,4；j=1,2,3)，T为完成全部面试所花费的最少时间。

优化目标为

minT?max?xi3?ti3?

i?? 约束条件：

29

第3章 整数规划与运输问题

(1)时间先后次序约束(每人只有参加完前一个阶段的面试后才能进入下一个阶段)：

xij?tij?xi,j?1,i?1,2,3,4;j?1,2

(2)每个阶段j同一时间只能面试1名同学：用0-1变量yik表示第k名同学是否排在第i名同学前面(1表示“是”、0表示“否”），则

xij?tij?xkj?Tyik

xkj?tkj?xij?T(1?yik)其中，i,k?1,2,3,4;j?1,2,3;i?k。

可以将非线性的优化目标函数改写为如下线性优化目标：

minT?T?T?s..t??T??Tyik还有0 - 1约束)。

求解模型（研究生选用） 这个模型可以如下输入LINGO:

Model： min=T; T>=x13+t13; T>=x23+t23; T>=x33+t33; T>=x43+t43; x11+tll<=x12;

x12+t12<=x13; x21+t21<=x22; x22+t22<=x23; x31+t31<=x32; x32+t32<=x33; x41+t41<=x42; x42+t42<=x43; x11+tll-x21<=T*y12; x21+t21-x11<=T*(1-y12);

?x13?t13?x23?t23 ?x33?t33?x43?t43 以上就是这个问题的0-1非线性规划模型(当然所有变量还有非负约束，变量

30

第3章 整数规划与运输问题

x12+t12-x22<=T*y12; x22+t22-x12<=T*(1-y12); x13+t13-x23<=T* y12; x23+t23-x13<=T*(1-y12); x11+tll-x31<=T*y13; x31+t31-x11<=T*(1-y13); x12+t12-x32<=T* y12; x32+t32-x12<=T*(1-y13); x13+t13-x33<=T * y13; x33+t33-x13<=T*(1-y13); x11+tll-x41<=T*y14; x41+t41-x11<=T*(1-y14); x12+t12-x42<=T*y14; x42+t42-x12<=T*(1-y14); x13+t13-x43<=T*y14; x43+t43-x13<=T*(1-y14); x21+t21-x31<=T*y23; x31+t31-x21<=T*(1-y23); x22+t22-x32<=T*y23; x32+t32-x32<=T*(1-y23); x23+t23-x33<=T*y23; x33+t33-x23<=T*(1-y23); x21+t21-x41<=T*y24; x41+t41-x21<=T*(1-y24); x22+t22-x42<=T*y24; x42+t42-x22<=T*(1-y24); x23+t23-x43<=T*y24; x43+t43-x23<=T*(1-y24); x31+t31-x41<=T*y34; x41+t41-x31<=T*(1-y34); x32+t32-x42<=T*y34; x42+t42-x32<=T*(1-y34); x33+t33-x43<=T*y34; x43+t43-x33<=T*(1-y34);

tll=13; t12=15; t13=20;

31

第3章 整数规划与运输问题

t21=10; t22=20; t23=18; t31=20; t32=16; t33=10; t41=8; t42=10; t43=15;

@bin(y12); @bin(y13); @bin(y14); @bin(y23); @bin(y24); @bin(y34); End

用LINGO求解得到：

Global optimal solution found.

Objective value: Extended solver steps: Total solver iterations: Variable T X13 T13 X23 T23 X33 T33 X43 T43 X11 TLL X12 T12 X21 T21 X22 T22 X31 T31 X32 T32 X41 T41 32

84.00000 1 3809

Value 84.00000 36.00000 20.00000 56.00000 18.00000 74.00000 10.00000 18.00000 15.00000 8.000000 13.00000 21.00000 15.00000 21.00000 10.00000 36.00000 20.00000 31.00000 20.00000 56.40000 16.00000 0.000000 8.000000

第3章 整数规划与运输问题

X42 8.000000 T42 10.00000 Y12 0.000000 Y13 0.000000 Y14 1.000000 Y23 0.000000 Y24 1.000000 Y34 1.000000

即所有面试完成至少需要84min，面试顺序为4-1-2-3(丁→甲→乙→丙)。早上8:00面试开始，最早9:24面试可以全部结束。

3.7 某公司值班室准备聘请4名兼职值班员(代号为1,2,3,4)和2名兼职带班员(代号为5,6)值班。已知每人从周一到周日每天最多可以安排的值班时间及每人每小时值班的报酬如表3-11所示。

表3-11 值班员代号 1 2 3 4 5 6 报酬/(元/h) 10 10 9 9 15 16 周一 6 0 4 5 3 0 每天最多可安排的值班时间/h 周二 周三 周四 周五 周六 0 6 8 5 0 6 6 0 3 6 4 0 0 6 0 0 8 6 7 0 5 4 0 3 12 0 12 0 12 0 周日 0 12 12 12 0 12 该值班室每天需要值班的时间为早上8:00至晚上22:00，值班时间内须有且仅有一名值班员值班。要求兼职值班员每周值班不少于l0小时，兼职带班员每周值班不少于8小时。每名值班员每周值班不超过4次，每次值班不少于2小时，每天安排值班的值班员不超过3人，且其中必须有一名兼职带班员值班。试为该值班室安排一张人员的值班表，使总支付的报酬为最少。（本科生仅需建立问题的数学模型）

解：根据题意，用xij为值班员i在周j的值班时间，记

?1,当安排值班员i在周j值班时 yij???0,否则(i?1,2,...,6;j?1,2,...,7)用aij代表值班员i在周j最多可值班的值班时间，用ci为值班员i的每小时的报酬，其中i=1,2,…,6；j=1,2,…,7。根据问题的要求，则问题可归结为如下的0-1整数规

33

第3章 整数规划与运输问题

划模型：

minz???cixiji?1j?167?2yij?xij?aijyij(i?1,?,6;j?1,?,7)?7??j?1xij?10(i?1,2,3,4)?7??xij?8(i?5,6) ?j?16???i?1xij?14(j?1,?,7)s..t???7yij?5(i?1,?,6)?j?1?6y?3(j?1,?,7)??i?1ij?y5j?y6j?1(j?1,?,7)???xij?0,yij?0or1(i?1,?,6;j?1,?,7)用LINGO软件求解，给出程序如下：（研究生选用）

MODEL: sets:

num_i/1..6/;c; num_j/1..7/;

link(num_i,num_j):a,x,y; num_k/1..4/; endsets data:

c=10,10,9,9,15,16;

a=6,0,6,0,7,12,0,0,6,0,6,0,0,12,4,8,3,0,5,12,12,5,5,6,0,4,0,12, 3,0,4,8,0,12,0,0,6,0,6,3,0,12; enddata

min=@sum(link(i,j):c(i)*x(i,j));

@for(link(i,j):2*y(i,j)<=x(i,j)<=a(i,j)*y(i,j)); @for(num_k(k):@sum(num_j(j):x(k,j))>=10); @sum(num_j(j):x(5,j))>=8; @sum(num_j(j):x(6,j))>=8;

@for(num_j(j):@sum(num_i(i):x(i,j))+14); @for(num_i(i):@sum(num_j(j):y(i,j))<=5); @for(num_j(j):@@sum(num_i(i):y(i,j))<=3); @for(num_j(j):y(5,j)+y(6,j)>=1); @for(link(i,j):@gin(x(i,j));x(i,j)>=0);

34

第3章 整数规划与运输问题

@for(link(i,j):@bin(y(i,j));y(i,j)>=0); end

运行该程序可得结果如下：

x11?6,x13?6,x15?7;x22?4,x24?6;x32?8,x35?5,x36?12;x41?5,x43?6,x47?12;x51?3,x53?2,x54?6,x56?2;x62?2,x64?2,x65?2,x67?2;其他的xij?0

y11?y13?y15?1;y22?y24?1;y32?y35?y36?1;y41?y43?y47?1;y51?y53?y54?y56?1;y62?y64?y65?y67?1;其他的yij?0班表如表3-12所示。

表3-12 每天最多可安排的值班时间/h 值班员代号 1 2 3 4 5 6

值班时间/h 周一 19 10 25 23 13 8 6 5 3 周二 4 8 2 周三 6 6 2 周四 6 6 2 周五 7 5 2

最优值z=1045。对求解结果进行分析，可以得到该部队聘用兼职值班员的值

周六 12 2 周日 12 2 由此可以看出，求解结果完全符合实际要求，每周所需要的总费用为1045元，是最低的安排方案。

3.8某公司有3个生产同类产品的工厂，生产的产品由4个销售点销售。各工厂的生产量、各销售点的销售量以及各工厂到各销售点的单位产品运价如表3-13所示。问该公司应如何调运产品，在满足各销售点的需要量前提下，使总的运费为最小。

表3-13 销地 产地 A1 A2 A3 B1 5 1 20 B2 3 6 10 35 B3 10 9 5 B4 4 6 7 产量 9 4 7 第3章 整数规划与运输问题

销量 3 5 8 4

解：（1）求初始调运方案

①方法一：利用最小元素法求得得出事调运方案如表3-14所示。

表3-14 销地 产地 A1 A2 A3 销量 B1 3 3 B2 5 5 B3 0 1 7 8 B4 4 4 产量 9 4 7

②方法二：利用伏格尔法求得得出事调运方案如表3-15所示。

表3-15 销地 产地 A1 A2 A3 销量

B1 3 3 B2 5 5 B3 0 1 7 8 B4 4 4 产量 9 4 7 （2）最优解的判别

得到运输问题的初始基可行解后就要判别这个解是否为最优解，判别的方法是计算非基变量即空格的检验数。因运输问题的目标函数是要求实现最小化，所以当所有的非基变量检验数全都大于等于0时为最优解。下面分别使用两种求空格检验数的方法。

①方法一：闭回路法

对于表3-15所示的初始调运方案，利用闭回路法计算所有空格的检验数，如表3-16所示。

表3-16

36

第3章 整数规划与运输问题

空格 (A1,B1) (A2,B2) (A2,B4) (A3,B1) (A3,B2) (A3,B4) 闭回路 (1,1)→(1,3)→(2,3)→(2,1) (2,2)→(2,3)→(1,3)→(1,2) (2,4) →(2,3) →(1,3) →(1,4) (3,1) →(3,3) →(2,3)→(2,1) (3,2) →(3,3) →(1,3) →(1,2) (3,4) →(1,4) →(1,3) →(3,3) 5 4 3 23 12 8 检验数

这时检验数均为正数，所以表3-15给出的方案即为最有调运方案。 ②方法二：位势法

联立方程：

u1+v3=3, u1+v4=10, u2+v1=1, u2+v4=8, u3+v2=4, u3+v4=5

?v1??7?u1?10??v2?1。 令v4=0得??u2?8，??u?5?v3??7?3??v4?0对于表3-15所示的初始调运方案，利用位势法计算所有空格的检验数，结果与用闭回路发得到的结果相同。

最优调运方案：A1→B2 5t,A1→B4 4t,A2→B1 3t,A2→B3 1t,A3→B3 7t，最小运费78元。

3.9 设有三个化肥厂供应四个地区的农用化肥。假定等量的化肥在这些地区使用的效果相同。各化肥厂年产量、各地区年需求量及从各化肥厂到各地区运送单位化肥的运价如表3-17所示。试确定使总运费最少的化肥调拨方案。

表3-17 需求 产地 A B C 最低需求(万吨) 最高需求(万吨) I 16 14 19 30 50 II 13 13 20 70 70 III 22 19 23 0 30 IV 17 15 -- 10 不限 产量(万吨) 50 60 50

解：这是一个产销不平衡的运输问题，总产量为160万t，四个地区的最低需

37

第3章 整数规划与运输问题

求为110万t，最高需求为无限。根据现有产量，第IV个地区每年最多能分配到60万t，这样最高需求就为210万t，大于产量。为了求得平衡，在产销平衡表中增加一个假想的化肥厂D，其年产量为50万t。由于各地区的需求量包含两部分，如地区I，其中30万t是最低需求，故不能由假想化肥厂D供给，令相应的单位运价为M（任意大的正数）；而另一部分20万t满足或不满足均可以，因此可以由假想化肥厂D供给，按前述，可令相应的单位运价为0。对凡是需求分两种情况的地区，实际上可按照两个地区看待。这样可以写出这个问题的产销平衡表（表3-18）和单位运价表（表3-19）。并根据表上作业法，可以求得这个问题的最优解，如表3-20所示。

表3-18 销地 产地 A B C D 销量

表3-19 销地 产地 A B C D

表3-20 销地 产地 A I 30 I’ 20 II 70 III 30 IV 10 IV’ 50 产量 50 60 50 50 I 16 14 19 M I’ 16 14 19 0 II 13 13 20 M III 22 19 23 0 IV 17 15 M M IV’ 17 15 M 0 I I’ II 50 38

III IV IV’ 产量 50

第3章 整数规划与运输问题

B C D 销量

30 30 20 20 20 0 70 30 30 10 10 30 20 50 60 50 50 39

第4章 目标规划

4.1 利用图解法求解下列目标规划模型。

????minz?P1(d1?d1)?P2(2d2?d3)????minz?P1(d1?d1)?P2d2?P3d3?x1?10x2?d1??d1??50?（1）???3x1?5x2?d2?d2?20s..t????8x1?6x2?d3?d3?100?x,x,d?,d??0,i?1,2,3?12ii解：（1）由约束条件作图4-1。

?x1?x2?d1??d1??10?（2） ???3x1?4x2?d2?d2?50s..t????8x1?10x2?d3?d3?300?x,x,d?,d??0,i?1,2,3?12ii

图4-1

首先考虑P1优先因子的目标的实现，在目标函数中要求实现

min(d1??d1?)

从图中可以看出：当x1,x2在射线x1-10x2=50且x2≥0上取值可以满足d1??0和d1??0。 再考虑P2优先因子的目标的实现，在目标函数中要求实现

??min(2d2?d3)

?因d2的权系数大于d3?的权系数，由图可知，D点为满意解，D点坐标为(50,0)。

（2）由约束条件作图4-2。

首先考虑P1优先因子的目标的实现，在目标函数中要求实现 min(d1??d1?)，从图中可以看出：可以满足d1??0和d1??0，此时x1,x2在线段AF上取值。

? 再考虑P2优先因子的目标的实现，在目标函数中要求实现 mind2。从图中

40

第4章 目标规划

?可以看出，F点满足d2最小。故F为满意解，F点坐标为(10,0)。

图4-2

4.2 利用单纯形法求解下列目标规划模型。

???（1）minz?P 1(d1?d1)?P2d3?x1?2x2?d1??d1??50????2x1?x2?d2?d2?40 s..t????2x1?2x2?d3?d3?80?x,x,d?,d??0,i?1,2,3?12ii?????（2）minz?Pd 11?P2d2?P3(4d3?2.5d4)?P4d1?x1?x2?d1??d1??70?????d1?d2?d2?10? s..t?x1?d3??50???x2?d4?44?x,x,d?,d??0,i?1,2,3,4?12ii解：（1）本题的三个约束条件都是目标约束，有三个负偏差变量，因此选择负偏差变量为初始基变量。并计算出各非基变量的检验数，得到初始的单纯形表如表4-1所示。

非基变量x1,x2的检验数分别为σ1= -P1-2P2和σ2= -2P1 -2P2，它们的最高优先级的系数都小于零，但σ2中P1的系数等于-2，其绝对值等于2，大于σ1中P1的系数的绝对值1，因此x2应当进基。用最小比值法确定d1?应当出基。换基后，通过计算求得新的基本可行解，如表4-2所示。

41

第4章 目标规划

表4-1 cj CB P1 0 P2 σj XB b 50 40 80 P1 P2 0 x1 1 2 2 -1 -2 0 x2 [ 2 ] 1 2 -2 -2 P1 0 0 P1 P2 0 ?d1 1 0 0 0 0 ?d1 -1 0 0 1 0 ?d2 0 1 0 0 0 ?d2 0 -1 0 1 0 ?d3 0 0 1 0 0 d3 0 0 -1 0 1 ?? 25 40 40 d1 d2 d3 ???

表4-2 cj CB 0 0 P2 σj

XB x2 ?0 b 25 15 30 P1 P2 x1 1/2 [ 3/2 ] 1 0 -1 0 x2 1 0 0 0 0 P1 0 0 P1 P2 0 d1 1/2 -1/2 -1 1 1 ?d1 -1/2 1/2 1 0 -1 ?d2 0 1 0 0 0 ?d2 0 -1 0 1 0 ?d3 0 0 1 0 0 ?d3 0 0 -1 0 1 ?? 50 10 30 d2 d3 ?尽管x1与d1?具有相同的负检验数，但根据前面讨论的原则，由于x1是决策变

?量，选择x1进基，用最小比值法确定d2出基，换基后，计算所得新的基本可行解

如表4-3所示。

表4-3 cj CB 0 0 P2 σj

42

XB x2 x1 b 20 10 20 P1 P2 0 x1 0 1 0 0 0 0 x2 1 0 0 0 0 P1 0 0 P1 P2 0 d1 2/3 -1/3 -2/3 1 2/3 ?d1 -2/3 [ 1/3 ] 2/3 0 -2/3 ?d2 -1/3 2/3 -2/3 0 2/3 ?d2 1/3 -2/3 2/3 1 -2/3 ?d3 0 0 1 0 0 ?d3 0 0 -1 0 1 ?? — 30 30 d3 ?第4章 目标规划

首项系数小于零的检验数只有d1?的为?2/3P，因此d1?应当进基，由于存在两2个最小比值，取下标最小的变量出基，因此x1出基，换基后，再计算新的基本可行解，如表4-4所示。

表4-4 cj CB 0 0 P2 σj

XB x2 ?0 b 40 30 0 P1 P2 x1 2 3 -2 0 2 0 x2 1 0 0 0 0 P1 0 0 P1 P2 0 d1 0 -1 0 1 0 ?d1 0 1 0 0 0 ?d2 1 2 -2 0 2 ?d2 -1 -2 2 1 -2 ?d3 0 0 1 0 0 ?d3 0 0 -1 0 1 ?? d1 d3 ? 此时所有变量的检验数的首项系数都已经大于等于零，因此获得了满意解如下：x1=0,x2 =40,d1?=30，其他偏差变量都等于零。

（2）选择四个负偏差变量为初始基变量，构成初始单纯形表如表4-5所示。

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

0 x1 1 0 [ 1 ] 0 -1 0 -4 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 0 0 1 0 0 0 0 0 ?d4 0 0 0 1 0 0 0 0 ?? 70 — 50 — d1 d2 d3 d4 ???? 现在决定进基变量。检验数首项具有负系数的变量有x1,x2，应当由它们中的一个进基。它们的检验数分别是?1??P和?2??P。首项优先级相同且1?4P31?2.5P3系数相等，比较它们的第二项，其优先级也相同，但系数不等，比较后确定x1进

43

第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

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