运筹学课后习题三.docx
《运筹学课后习题三.docx》由会员分享，可在线阅读，更多相关《运筹学课后习题三.docx（22页珍藏版）》请在冰点文库上搜索。
运筹学课后习题三
习题三
某公司今后三年内有五项工程可以考虑投资。
每项工程的期望收入和年度费用（万元）如表3-10所示。
表3-10
工程
费用
收入
第一年第二年第三年
1
、
2
3
4
5
518
472
596
752
869
30
·
40
20
15
30
资金拥有量
302530
每项工程都需要三年完成，应选择哪些项目使总收入最大，建立该问题的数学模型。
【解】设
，模型为
【
最优解X＝（1,1,1,0,1），Z=110万元，即选择项目1、2、3、5时总收入最大。
址问题。
以汉江、长江为界将武汉市划分为汉口、汉阳和武昌三镇。
某商业银行计划投资9000万元在武汉市备选的12个点考虑设立支行，如图3-10所示。
每个点的投资额与一年的收益见表3－10。
计划汉口投资2～3个支行，汉阳投资1～2个支行，武昌投资3～4个支行。
如何投资使总收益最大，建立该问题的数学模型，说明是什么模型，可以用什么方法求解。
表3-11
地址i
.
1
2
3
4
5
6
7
8
9
10
[
11
12
投资额（万元）
900
1200
1000
750
680
800
720
；
1150
1200
1250
850
1000
收益（万元）
400
500
450
350
—
300
400
320
460
500
510
380
400
【解】设xj为投资第j个点的状态，xj=1或0，j=1,2,…,12
…
最优解：
x1＝x5=x12=0，其余xj=1,总收益Z=3870万元，实际完成投资额8920万元。
一辆货车的有效载重量是20吨，载货有效空间是8××2m。
现有六件货物可供选择运输，每件货物的重量、体积及收入如表表3-12。
另外，在货物4和5中先运货物5，货物1和2不能混装，怎样安排货物运输使收入最大，建立数学模型。
表3-12
货物号
1
2
3
4
5
（
6
重量（T）
6
5
3
4
7
2
体积（m3）
3
|
7
4
5
6
2
收入（百元）
5
8
4
6
}
7
3
【解】设xj为装载第j件货物的状态，xj=1表示装载第j件货物，xj=0表示不装载第j件货物，有
女子体操团体赛规定：
（1）每个代表队由5名运动员组成，比赛项目是高低杠、平衡木、鞍马及自由体操。
（2）每个运动员最多只能参加3个项目并且每个项目只能参赛一次；
（3）每个项目至少要有人参赛一次，并且总的参赛人次数等于10；
（4）每个项目采用10分制记分，将10次比赛的得分求和，按其得分高低排名，分数越高成绩越好。
已知代表队5名运动员各单项的预赛成绩如表3-13所示。
…
表3-13
怎样安排运动员的参赛项目使团体总分最高，建立该问题的数学模型。
【解】设xij（i=1，2，…，5；j＝1，2，3，4）为第i人参赛j项目的状态，即
记第i人参赛j项目的成绩为Cij,，目标函数
每个运动员最多只能参加3个项目并且每个项目只能参赛一次,约束条件：
{
每个项目至少要有人参赛一次，并且总的参赛人次数等于10，约束条件：
数学模型为
利用0－1变量对下列各题分别表示成一般线性约束条件
\
（1）x1+2x2≤8、4x1+x2≥10及2x1+6x2≤18三个约束中至少两个满足
（2）若x1≥5，则x2≥10，否则x2≤8
（3）x1取值2，4，6，8中的一个
【解】
6．考虑下列数学模型
其中
满足约束条件
（1）x1≥8或x2≥6
&
（2）|x1－x2|=0，4或8
（3）x1+2x2≥20、2x1+x2≥20及x1+x2≥20三个约束中至少一个满足
（4）x1≥0，x2≥0
将此问题归结为混合整数规划的数学模型。
【解】
7．用分枝定界法求解下列IP问题
（1）
（2）
【解】
（1）X=（1,2）,或X＝（0,3）Z=3
（2）X=（5,0）,Z=5
》
8．用割平面法求解下列IP问题
（1）
（2）
【解】
（1）X=（3,3）,Z=15
（2）X=（5,2）,Z=16
9．用隐枚举法求解下列BIP问题
（1）
（2）
【解】
（1）X=（1,1,1）,Z=8
（2）X=（1,1,1,0）,Z=4
10．用分枝定界－隐枚举法求解下列BIP问题
#
（1）
（2）
【解】
（1）X=（1,0,1,1）,Z=8
（2）X=（1,1,0,0,0）,Z=－2
习题四
工厂生产甲、乙两种产品，由Ａ、Ｂ二组人员来生产。
Ａ组人员熟练工人比较多，工作效率高，成本也高；Ｂ组人员新手较多工作效率比较低，成本也较低。
例如，A组只生产甲产品时每小时生产10件，成本是50元有关资料如表所示。
表
产品甲
产品乙
&
效率（件/小时）
成本（元/件）
效率（件/小时）
成本（元/件）
A组
10
50
8
45
B组
-
8
45
5
40
产品售价（元/件）
80
75
二组人员每天正常工作时间都是8小时，每周5天。
一周内每组最多可以加班10小时，加班生产的产品每件增加成本5元。
工厂根据市场需求、利润及生产能力确定了下列目标顺序：
P1：
每周供应市场甲产品400件，乙产品300件
@
P2：
每周利润指标不低于500元
P3：
两组都尽可能少加班，如必须加班由Ａ组优先加班
建立此生产计划的数学模型。
【解】解法一：
设x1,x2分别为A组一周内正常时间生产产品甲、乙的产量，x3,x4分别为A组一周内加班时间生产产品甲、乙的产量；x5,x6分别为B组一周内正常时间生产产品甲、乙的产量，x7,x8分别为B组一周内加班时间生产产品甲、乙的产量。
总利润为
生产时间为
A组：
B组：
）
数学模型为：
解法二：
设x1,x2分别为A组一周内生产产品甲、乙的正常时间，x3,x4分别为A组一周内生产产品甲、乙的加班时间；x5,x6分别为B组一周内生产产品甲、乙的正常时间，x7,x8分别为B组一周内生产产品甲、乙的加班时间。
总利润为
数学模型为
【解】设xij为Ai到Bj的运量，数学模型为
（
双击下图，打开幻灯片。
已知某实际问题的线性规划模型为
假定重新确定这个问题的目标为：
[
Ｐ1：
ｚ的值应不低于1900
Ｐ2：
资源１必须全部利用
将此问题转换为目标规划问题，列出数学模型。
【解】数学模型为
已知目标规划问题
（1）分别用图解法和单纯形法求解；
（2）分析目标函数分别变为①、②两种情况时（②中分析w1、w2的比例变动）解的变化。
~
①
②
【解】
（1）图解法（双击下图，打开幻灯片）
（1）单纯形法
Cj
0
0
P1
】
P4
0
P2
5P3
0
3P3
0
b
CB
基
$
x1
x2
d1－
d1+
d2－
d2+
d3－
d3+
d4－
d4+
P1
d1－
1
2
1
－1
|
6
0
d2－
1
2
！
1
－1
9
5P3
d3－
1
~
－2
1
－1
4
《
3P3
d4－
[1]
}
1
－1
2
表
（1）
Cj－Zj
P1
－1
－2
1
…
P2
$
1
P3
－5
7
5
~
3
P4
1
（
P1
d1－
[1]
>
1
－1
－2
2
2
0
…
d2－
1
1
－1
－2
|
2
5
5P3
d3－
1
《
1
－1
2
－2
8
0
x2－
1
，
1
－1
2
表
（2）
Cj－Zj
P1
－1
1
2
！
－2
P2
1
:
P3
－5
7
<
5
－7
10
P4
*
1
>
0
x1
1
1/2
－1/2
1/2
—
－1/2
0
0
13/2
P4
d1+
－1
1
.
1
－1
3
3P3
d4－
；
－1/4
1/4
1/4
－1/4
1
－1
3/4
|
0
x2
1
1/4
－1/4
－1/4
*
5/4
表（5）
Cj－Zj
P1
1
【
P2
]
1
P3
3/4
－3/4
17/4
3/4
（
3
P4
1
1
】
1
（b）
单纯形法，利用上表（5）的结果，引入参数w1、w2进行灵敏度分析，得到下表。
Cj
^
0
0
P1
P4
0
P2
w1P3
0
w2P3
0
'
b
CB
基
x1
x2
d1－
d1+
d2－
d2+
d3－
]
d3+
d4－
d4+
0
x1
1
<
1/2
－1/2
1/2
－1/2
0
0
13/2
P4
d1+
…
－1
1
1
－1
3
）
w2P3
d4－
－1/4
1/4
[1/4]
－1/4
&
1
－1
3/4
0
x2
1
1/4
》
－1/4
－1/4
5/4
表
（1）
Cj－Zj
P1
|
1
P2
1
#
P3
w2/4
、
－w2/4
w1-w2/4
w2/4
w2
P4
#
1
1
1
0
；
x1
1
1
－1
－2
`
2
5
P4
d1+
－1
1
1
－1
~
3
w1P3
d3－
（
－1
1
1
－1
4
－4
3
0
x2－
1
1
－1
2
表
（2）
Cj－Zj
P1
1
P2
1
P3
w1
－w1
w1
w2－4w1
4w1
P4
1
－1
1
（1）由表
（1）知，当w1－w2/4>0，即
时，满意解为：
X＝（13/2，5/4）
（2）当
时，表
（1）和表
（2）都是满意解。
（3）由表
（2）知，当w2－4w1>0，即
时，满意解为：
X＝（5，2）
、
升级会员 