运筹习题参考答案

第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*