运筹习题参考答案

第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