问题一 汽车厂月度生产计划一汽车厂生产小、中,大三种类型的汽车,各种类型的汽车对钢材以及劳动时间的需求如下表,试制订月生产计划,使该工厂的利润最大,
小型车 中型车 大型车 现有量钢材 1.5 3 5 600
劳动时间 280 250 400 60000
利润 2 3 4
分析小型车 中型车 大型车 现有量钢材 1.5 3 5 600
劳动时间 280 250 400 60000
利润 2 3 4
从收益率来看,比较中型车和大型车得出结论,
生产大型车不经济,因此,若允许车辆数量为实数,则不生产大型车,但是现在车辆为整数,因此模型为
1 模型的建立记月生产的小、中、大型车的数量分别为 x1,
x2,x3,模型为
( *),
,6 00 004 002 502 80
,6 00535.1
..
432m a x
321
321
321
为非负整数ix
xxx
xxx
ts
xxxR
这是个整数线性规划问题,有三个决策变量,要用软件来求 ILP.但是本题比较特殊,我们可以发现
2 LP图解法我们先得到实数型的最优解为（ 64.5,167.7),利润的最大值为 632.3.
1x
2x
（ 64.5,167.7)?
但是,遗憾的是,这个解不是整数解,因此不合要求,解决方法,
(1) 由于解的数字都比较大,我们可以简单地舍去小数,即取 (64,167),此时利润为 629,可以接受,同时定界,
(2) 在最优解附近试探,(64,168);(65,167); (66,167),
(65,166,1)等等,利润分别为 632,631,后两个不满足约束,由于最大利润为 632,故最优解为 (64,168).
,6 0 0 0 02 5 02 8 0
,6 0 035.1
..
32m a x
21
21
21
xx
xx
ts
xxR
3 进一步讨论由于各种原因 (比如,工艺 ),若生产某种汽车,则至少生产 80辆,问生产计划有何改变?
分析,要么 xi=0,要么 xi≥80,组合起来,共有八种情形,;80,80,80 )8( ;0,80,80 )7(;0,80,80 )6( ;0,80,80 )5(;0,80 )4( ;0,80 )3(;0,80 )2( ;0 )1(
321132
231321
213312
321321
xxxxxx
xxxxxx
xxxxxx
xxxxxx
方法一,让它们分别与模型 (*)一起来求解新的 LP,
逐一得到它们的最优解,其中 (1)不用解 ;(7),(8)无解 ;(2)的解为 (214.3,0,0),z=428.5;(3)的解为
(0,200,0),z=600; ;(4)的解为 (0,0,120),z=480;
(5)的最优解为 (80,150.4,0),
z=611.2;工时为紧约束 ;
(6)的最优解为 (80,0,94),
z=536;工时为紧约束 ;
,6 0 00 0400250280
,600535.1..
321
321
xxx
xxxts
结论,此时最优解为
(80,150.4,0),利润为 611.2
1x
2x
（ 64.5,167.7)?
(75,97.5)? 可行域
1x
3x
方法二 引入 0-1变量
.1 0 0 0,
},1,0{,80,
800
本例可以取为充分大正数这里等价于要么要么
M
yyxMyx
xx
iiiii
ii
,6 0 00 0400250280
,600535.1
..
432m ax
321
321
321
xxx
xxx
ts
xxxR
ii Myx?
的作用是当 yi=0时,必有 xi=0.
本例中,
)100 0(80
1,80,
自然满足
ii
iiiii
xx
yyxMyx
方法三 从数学上讲,
.)(
:
080
800
iii
ii
xxx
xx
满足对非负变量等价于要么要么不过,这个式子对变量而言,出现了非线性函数,因此就变成了非线性规划问题,其求解往往比较困难,
即使用软件求解 (如,LINGO,Matlab),也往往依赖于初值的选择,
评注,若能用线性规划处理,则尽量不要用非线性规划,
例 2 原油的采购与加工问题 某公司用两种原油 (A和 B)混合加工成两种汽油 (甲和乙 ).甲乙两种汽油含原油 A的最低比例分别是 50%和 60%,每吨售价分别为 4800
元和 5600元,该公司现有原油 A和 B的库存量分别为 500吨和 1000吨,还可以从市场上买到不超过 1500吨的原油 A.原油 A的市场价为,购买量不超过 500吨时的单价为 10000元 /吨 ;购买量超过
500吨但不超过 1000吨时,超过 500吨的部分
8000元 /吨 ;购买量超过 1000吨时,超过 1000吨的部分 6000元 /吨,该公司应如何安排原油的采购和加工?
模型的建立设购买原油 A x吨,生产汽油甲所用的原油 A和 B
分别为 x11和 x21吨 ;乙的分别为 x12和 x22吨,公司销售生产的汽油收入为 P千元,纯收入为 R千元,则
)(6.5)(8.4 22122111 xxxxP;500,1500,1000 12112221 xxxxxx
).(6.0);(5.0 221212211111 xxxxxx
购买原油 A的成本为
15001000 ),1000(640005000
1000500 ),500(85000
5000,10
)(
xx
xx
xx
xc
于是模型为
)()(6.5)(8.4)(m a x 22122111 xcxxxxxcPR
.0,,,,
);(6.0
( * ) );(5.0
,1 5 0 0;1 0 0 0;5 0 0,.
22211211
221212
211111
2221
1211
xxxxx
xxx
xxx
x
xx
xxxts
其中
1 5 0 01 0 0 0,63 0 0 0
1 0 0 05 0 0,81 0 0 0
5 0 00,10
)(
xx
xx
xx
xc
模型求解方法一 由于 c(x) 为分段函数,且在每一段内都是线性函数,因此我们可以通过求解三个线性规划问题,
最后比较即可得到模型的最优解,
.500
( *)
10)(6.5)(8.4)(m ax 2212211111
x
st
xxxxxxcPR
.100 0500
( *)
)8100 0()(6.5)(8.4m ax 221221112
x
st
xxxxxR
.150 0100 0
( *)
)6300 0()(6.5)(8.4m ax 221221113
x
st
xxxxxR
方法二 处理分段函数 c(x)
1 5 0 01 0 0 0,63 0 0 0
1 0 0 05 0 0,81 0 0 0
5 0 00,10
)(
xx
xx
xx
xc
)6810()(6.5)(8.4
),(A
,
32122122111
321
xxxxxxxR
xxxx
则吨的数量原油购买它们分别是三种价格的设
00 0)5(,05 00 )(
( * )
3221 x-xx-x
st
方法三 引入 0-1变量 yi
以 yi=1分别表示以三种价格购买原油,
00 0)5(,05 00 )(
( * )
3221 x-xx-x
st
等价于
33
223
112
050
500050
500050
( * )
yx
,yxy
,yxy
st
模型为混合线性规划,
方法四 处理分段线性函数的一般方法
15001000 ),1000(640005000
1000500 ),500(85000
5000,10
)(
xx
xx
xx
xc
500 1000 1500
12000
9000
5000
这个分段函数在三个区间内分别是线性函数,区间的分段点为 0,500,1000,1500.
当 x落在某个区间时我们可以取做区间两个端点的线性组合来解决,
500 1000 1500
12000
9000
5000
取分点 b1=0,b2=500,b3=1000,b4=
1500.取分点的比例 z1,z2,z3,z4,当 x
落在区间 [b1,b2]时,取 x=b1z1+b2z2,
z1+z2=1;当 x落在区间 [b2,b3]时,取
x=b2z2+b3z3,z2+z3=1;当 x落在区间
[b3,b4]时,取 x=b3z3+b4z4,z3+z4 =1;
由于 c(x)是 x的线性函数,自然也是
zi的线性函数,
为了表示 x落在某个区间,我们还要引入表示这个属性的变量,0-1变量 yi.关系式
.1,1
,,,,
3214321
3432321211
yyyzzzz
yzyyzyyzyz
yi中有只有一个为 1.
投资的收益与风险问题 (98年 A题 )
市场上有 n种资产（如股票、债券,…… ）
Si（ i=1,2,…,n ）供投资者选择，某公司有数额为 M的一笔相当大的资金可用于作一个时期的投资。公司财务分析人员对这 n种资产进行了评估，估算出在这一时期内购买 Si的平均收益率为 ri，并预测出购买 Si的的风险损失率为
qi。考虑到投资越分散，总的风险越小，公司确定，当用这笔资金购买若干种资产时，总体风险可用所投资的 Si中最大的一个风险来度量。
购买 Si要付交易费，费率为 pi，并且当购买额不超过给定值 ui时，交易费按购买 ui计算（不买当然无须付费）。另外，假定同期银行存款利率是 r0，且既无交易费又无风险。（ r0=5%）
1)已知 n=4时的相关数据如下：
Si ri (%) qi(%) pi(%) ui(元 )
S1 28 2.5 1 103
S2 21 1.5 2 198
S3 23 5.5 4.5 52
S4 25 2.6 6.5 40
试给该公司设计一种投资组合方案，即用给定的资金 M，有选择地购买若干种资产或存银行生息，使净收益尽可能大，而总风险尽可能小。
2)试就一般情况对以上问题进行讨论，并利用以下数据进行计算。
Si ri(%) qi(%) pi(%) ui(元 )
S1 9.6 42 2.1 181
S2 18.5 54 3.2 407
S3 49.4 60 6.0 428
S4 23.9 42 1.5 549
S5 8.1 1.2 7.6 270
Si ri(%) qi(%) pi(%) ui(元 )
S6 14 39 3.4 397
S7 40.7 68 5.6 178
S8 31.2 33.4 3.1 220
S9 33.6 53.3 2.7 475
S10 36.8 40 2.9 248
S11 11.8 31 5.1 195
S12 9 5.5 5.7 320
S13 35 46 2.7 267
S14 9.4 5.3 4.5 328
S15 15 23 7.6 131
小型车 中型车 大型车 现有量钢材 1.5 3 5 600
劳动时间 280 250 400 60000
利润 2 3 4
分析小型车 中型车 大型车 现有量钢材 1.5 3 5 600
劳动时间 280 250 400 60000
利润 2 3 4
从收益率来看,比较中型车和大型车得出结论,
生产大型车不经济,因此,若允许车辆数量为实数,则不生产大型车,但是现在车辆为整数,因此模型为
1 模型的建立记月生产的小、中、大型车的数量分别为 x1,
x2,x3,模型为
( *),
,6 00 004 002 502 80
,6 00535.1
..
432m a x
321
321
321
为非负整数ix
xxx
xxx
ts
xxxR
这是个整数线性规划问题,有三个决策变量,要用软件来求 ILP.但是本题比较特殊,我们可以发现
2 LP图解法我们先得到实数型的最优解为（ 64.5,167.7),利润的最大值为 632.3.
1x
2x
（ 64.5,167.7)?
但是,遗憾的是,这个解不是整数解,因此不合要求,解决方法,
(1) 由于解的数字都比较大,我们可以简单地舍去小数,即取 (64,167),此时利润为 629,可以接受,同时定界,
(2) 在最优解附近试探,(64,168);(65,167); (66,167),
(65,166,1)等等,利润分别为 632,631,后两个不满足约束,由于最大利润为 632,故最优解为 (64,168).
,6 0 0 0 02 5 02 8 0
,6 0 035.1
..
32m a x
21
21
21
xx
xx
ts
xxR
3 进一步讨论由于各种原因 (比如,工艺 ),若生产某种汽车,则至少生产 80辆,问生产计划有何改变?
分析,要么 xi=0,要么 xi≥80,组合起来,共有八种情形,;80,80,80 )8( ;0,80,80 )7(;0,80,80 )6( ;0,80,80 )5(;0,80 )4( ;0,80 )3(;0,80 )2( ;0 )1(
321132
231321
213312
321321
xxxxxx
xxxxxx
xxxxxx
xxxxxx
方法一,让它们分别与模型 (*)一起来求解新的 LP,
逐一得到它们的最优解,其中 (1)不用解 ;(7),(8)无解 ;(2)的解为 (214.3,0,0),z=428.5;(3)的解为
(0,200,0),z=600; ;(4)的解为 (0,0,120),z=480;
(5)的最优解为 (80,150.4,0),
z=611.2;工时为紧约束 ;
(6)的最优解为 (80,0,94),
z=536;工时为紧约束 ;
,6 0 00 0400250280
,600535.1..
321
321
xxx
xxxts
结论,此时最优解为
(80,150.4,0),利润为 611.2
1x
2x
（ 64.5,167.7)?
(75,97.5)? 可行域
1x
3x
方法二 引入 0-1变量
.1 0 0 0,
},1,0{,80,
800
本例可以取为充分大正数这里等价于要么要么
M
yyxMyx
xx
iiiii
ii
,6 0 00 0400250280
,600535.1
..
432m ax
321
321
321
xxx
xxx
ts
xxxR
ii Myx?
的作用是当 yi=0时,必有 xi=0.
本例中,
)100 0(80
1,80,
自然满足
ii
iiiii
xx
yyxMyx
方法三 从数学上讲,
.)(
:
080
800
iii
ii
xxx
xx
满足对非负变量等价于要么要么不过,这个式子对变量而言,出现了非线性函数,因此就变成了非线性规划问题,其求解往往比较困难,
即使用软件求解 (如,LINGO,Matlab),也往往依赖于初值的选择,
评注,若能用线性规划处理,则尽量不要用非线性规划,
例 2 原油的采购与加工问题 某公司用两种原油 (A和 B)混合加工成两种汽油 (甲和乙 ).甲乙两种汽油含原油 A的最低比例分别是 50%和 60%,每吨售价分别为 4800
元和 5600元,该公司现有原油 A和 B的库存量分别为 500吨和 1000吨,还可以从市场上买到不超过 1500吨的原油 A.原油 A的市场价为,购买量不超过 500吨时的单价为 10000元 /吨 ;购买量超过
500吨但不超过 1000吨时,超过 500吨的部分
8000元 /吨 ;购买量超过 1000吨时,超过 1000吨的部分 6000元 /吨,该公司应如何安排原油的采购和加工?
模型的建立设购买原油 A x吨,生产汽油甲所用的原油 A和 B
分别为 x11和 x21吨 ;乙的分别为 x12和 x22吨,公司销售生产的汽油收入为 P千元,纯收入为 R千元,则
)(6.5)(8.4 22122111 xxxxP;500,1500,1000 12112221 xxxxxx
).(6.0);(5.0 221212211111 xxxxxx
购买原油 A的成本为
15001000 ),1000(640005000
1000500 ),500(85000
5000,10
)(
xx
xx
xx
xc
于是模型为
)()(6.5)(8.4)(m a x 22122111 xcxxxxxcPR
.0,,,,
);(6.0
( * ) );(5.0
,1 5 0 0;1 0 0 0;5 0 0,.
22211211
221212
211111
2221
1211
xxxxx
xxx
xxx
x
xx
xxxts
其中
1 5 0 01 0 0 0,63 0 0 0
1 0 0 05 0 0,81 0 0 0
5 0 00,10
)(
xx
xx
xx
xc
模型求解方法一 由于 c(x) 为分段函数,且在每一段内都是线性函数,因此我们可以通过求解三个线性规划问题,
最后比较即可得到模型的最优解,
.500
( *)
10)(6.5)(8.4)(m ax 2212211111
x
st
xxxxxxcPR
.100 0500
( *)
)8100 0()(6.5)(8.4m ax 221221112
x
st
xxxxxR
.150 0100 0
( *)
)6300 0()(6.5)(8.4m ax 221221113
x
st
xxxxxR
方法二 处理分段函数 c(x)
1 5 0 01 0 0 0,63 0 0 0
1 0 0 05 0 0,81 0 0 0
5 0 00,10
)(
xx
xx
xx
xc
)6810()(6.5)(8.4
),(A
,
32122122111
321
xxxxxxxR
xxxx
则吨的数量原油购买它们分别是三种价格的设
00 0)5(,05 00 )(
( * )
3221 x-xx-x
st
方法三 引入 0-1变量 yi
以 yi=1分别表示以三种价格购买原油,
00 0)5(,05 00 )(
( * )
3221 x-xx-x
st
等价于
33
223
112
050
500050
500050
( * )
yx
,yxy
,yxy
st
模型为混合线性规划,
方法四 处理分段线性函数的一般方法
15001000 ),1000(640005000
1000500 ),500(85000
5000,10
)(
xx
xx
xx
xc
500 1000 1500
12000
9000
5000
这个分段函数在三个区间内分别是线性函数,区间的分段点为 0,500,1000,1500.
当 x落在某个区间时我们可以取做区间两个端点的线性组合来解决,
500 1000 1500
12000
9000
5000
取分点 b1=0,b2=500,b3=1000,b4=
1500.取分点的比例 z1,z2,z3,z4,当 x
落在区间 [b1,b2]时,取 x=b1z1+b2z2,
z1+z2=1;当 x落在区间 [b2,b3]时,取
x=b2z2+b3z3,z2+z3=1;当 x落在区间
[b3,b4]时,取 x=b3z3+b4z4,z3+z4 =1;
由于 c(x)是 x的线性函数,自然也是
zi的线性函数,
为了表示 x落在某个区间,我们还要引入表示这个属性的变量,0-1变量 yi.关系式
.1,1
,,,,
3214321
3432321211
yyyzzzz
yzyyzyyzyz
yi中有只有一个为 1.
投资的收益与风险问题 (98年 A题 )
市场上有 n种资产（如股票、债券,…… ）
Si（ i=1,2,…,n ）供投资者选择，某公司有数额为 M的一笔相当大的资金可用于作一个时期的投资。公司财务分析人员对这 n种资产进行了评估，估算出在这一时期内购买 Si的平均收益率为 ri，并预测出购买 Si的的风险损失率为
qi。考虑到投资越分散，总的风险越小，公司确定，当用这笔资金购买若干种资产时，总体风险可用所投资的 Si中最大的一个风险来度量。
购买 Si要付交易费，费率为 pi，并且当购买额不超过给定值 ui时，交易费按购买 ui计算（不买当然无须付费）。另外，假定同期银行存款利率是 r0，且既无交易费又无风险。（ r0=5%）
1)已知 n=4时的相关数据如下：
Si ri (%) qi(%) pi(%) ui(元 )
S1 28 2.5 1 103
S2 21 1.5 2 198
S3 23 5.5 4.5 52
S4 25 2.6 6.5 40
试给该公司设计一种投资组合方案，即用给定的资金 M，有选择地购买若干种资产或存银行生息，使净收益尽可能大，而总风险尽可能小。
2)试就一般情况对以上问题进行讨论，并利用以下数据进行计算。
Si ri(%) qi(%) pi(%) ui(元 )
S1 9.6 42 2.1 181
S2 18.5 54 3.2 407
S3 49.4 60 6.0 428
S4 23.9 42 1.5 549
S5 8.1 1.2 7.6 270
Si ri(%) qi(%) pi(%) ui(元 )
S6 14 39 3.4 397
S7 40.7 68 5.6 178
S8 31.2 33.4 3.1 220
S9 33.6 53.3 2.7 475
S10 36.8 40 2.9 248
S11 11.8 31 5.1 195
S12 9 5.5 5.7 320
S13 35 46 2.7 267
S14 9.4 5.3 4.5 328
S15 15 23 7.6 131
