线性规划数学建模与数学实验后勤工程学院数学教研室实验目的实验内容
2、掌握用数学软件包求解线性规划问题。
1、了解线性规划的基本内容。
*2、线性规划的基本算法。
5、实验作业。
3、用数学软件包求解线性规划问题。
1、两个引例。
4、建模案例：投资的收益与风险问题一,任务分配问题：某车间有甲、乙两台机床，可用于加工三种工件。假定这两台车床的可用台时数分别为 800和
900，三种工件的数量分别为 400,600和 500，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表。问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？
单位工件所需加工台时数 单位工件的加工费用 车床类 型 工件 1 工件 2 工件 3 工件 1 工件 2 工件 3
可用台时数甲 0,4 1,1 1,0 13 9 10 800
乙 0,5 1,2 1,3 11 12 8 900
两个引例解 设在甲车床上加工工件 1,2,3的数量分别为 x1,x2,x3，
在乙车床上加工工件 1,2,3的数量分别为 x4,x5,x6。可建立以下线性规划模型：
654321
8121110913m i n xxxxxxz
6,,2,1,0
9 0 03.12.15.0
8 0 01.14.0
5 0 0
6 0 0
4 0 0x
,.
654
321
63
52
41
ix
xxx
xxx
xx
xx
x
ts
i
解答问题二,某厂每日 8小时的产量不低于 1800件。为了进行质量控制，计划聘请两种不同水平的检验员。一级检验员的标准为：速度 25件 /小时，正确率 98%，计时工资 4元 /小时；二级检验员的标准为：速度 15小时 /件，正确率 95%，计时工资 3元 /小时。检验员每错检一次，工厂要损失 2元。为使总检验费用最省，该工厂应聘一级、二级检验员各几名？
解 设需要一级和二级检验员的人数分别为 x1,x2人,
则应付检验员的工资为：
2121 24323848 xxxx因检验员错检而造成的损失为：
2121 1282)%5158%2258( xxxx
故目标函数为：
212121 3640)128()2432(m i n xxxxxxz
约束条件为：
0,0
1 8 0 0158
1 8 0 0258
1 8 0 0158258
21
2
1
21
xx
x
x
xx
线性规划模型：
21 3640m i n xxz
0,0
15
9
4535
,.
21
2
1
21
xx
x
x
xx
ts
解答返 回
1.线性规划的标准形式：
x
m i n z = )( xf
.,ts )( xg i? 0 （ ),,2,1 mi
其中目标函数 )( xf 和约束条件中 )( xg i 都是线性函数
m i n f = cx
s,t,A x = b （ 1 ）
x
0
这里
A
= ( ija )
m,n
,x =
T
21 n
xxx?
b =
T
21 n
bbb?,
c
=nccc?21
用单纯法求解时，常将标准形式化为：
2,线性规划的基本算法 —— 单纯形法线性规划的基本算法 —— 单纯形法例 m i n z = 1 0 x 1 + 9 x 2
s,t,6x 1 + 5 x 2 ≤ 6 0
1 0 x 1 + 2 0 x 2 ≥ 1 5 0
x 1 ≤ 8
x 1,x 2 ≥ 0
引入松弛变量 x3,x4,x5,将不等式化为等式,即单纯形标准形,
m i n z = 1 0 x 1 + 9 x 2
s,t,6x 1 + 5 x 2 + x 3 = 6 0
1 0 x 1 + 2 0 x 2 - x 4 = 1 5 0
x 1 + x 5 = 8
x i≥ 0 ( i = 1,2,3,4,5 )
系数矩阵为,6 5 1 0 0
A = 1 0 2 0 0 - 1 0 = ( P 1 P 2 P 3 P 4 P 5 )
1 0 0 0 1
b = ( 6 0,1 5 0,8 ) T
显然 A的秩 ran(A)=3,任取 3个线性无关的列向量,如 P3 P4 P5称为一组 基,记为 B,其余列向量称为 非基,记为 N,
于是 f = cBxB + cNxN,Ax = BxB + NxN = b,
则 xB = B-1b-B-1NxN,f = cBB-1b + (cN – cBB-1N)xN
令非基变量 x N = 0,解得基变量 x B = B1? b,称 ( x B,x N ) 为 基解,
基解的所有变量的值都非负，则称为 基可行解,此时的基称为 可行基,
若可行基进一步满足,cN – cBB-1N≥0,即,cBB-1N - cN≤0
则对一切可行解 x,必有 f(x) ≥ cBB-1b,此时称基可行解 x = (B-1b,0) T
为 最优解,
3,最优解的存在性定理将 A的列向量重排次序成 A = (B,N),相应 x = (xB,xN) T,c = (cB,cN)
基对应的变量 xB称为 基变量,非基对应的变量 xN称为 非基变量,
定理 1 如果线性规划 (1)有可行解，那么一定有基可行解,
定理 2 如果线性规划 (1)有最优解，那么一定存在一个基可行解是最优解,
4,基可行解是最优解的判定准则因为 f = cBB-1b + (cN – cBB-1N)xN，
即 f - 0?xB + (cBB-1N- cN )xN = cBB-1b
若基 B = (
1
P,
2
P,
,
m
P ),非基 N = (
1?m
P,
2?m
P,?,
n
P ),
令 j
=
B
c
1?
B
j
P
- j
c
,j=m+1,m+2,
,n,则 ( 1 ) 可写成
min f
s.t,
B
x +
1?
B N N
x
=
1?
B b
f + 0 ·
B
x +
n
mj
jj
x
1
=
B
c
1?
B b
x
0
称为 （ 1 ）式的 典式,
定理 3 设 （ 1x,2x,?,mx ）是规划 ( 1 ) 的一个可行基,B 是对应的基阵,如果典式中的 1?,2?,?,m? 都不大于零,即对应的 1?m 0,2?m 0,
,n 0,则基 （ 1x,2x,
,mx ）对应的基可行解
0X
=
0
1 bB
是最优解,
令
1?B b
=
m?
2
1
，
1?B N
=
nmmmmm
nmm
nmm
,2,1,
,22,21,2
,12,11,1
5.基可行解的改进线性规划 （ 1 ）的典式变为：
min f
s.t,ix +?
n
mj
jij
x
1
= i? i = 1,2,?,m
f + 0 ·
B
x +?
n
mj
jj
x
1
= Bc
1?
B b
x
0
定理 4 设 （
1
x,
2
x,?,mx ）是规划 ( 1 ) 的一个可行基，
B 是对应的基阵,如果存在
km?
> 0,使
1)
km?,1
,
km?,2
,?,
kmm?,
中至少有一个大于零；
2) 所有的 i
> 0,i =1,2,?,m
则一定存在另一个可行基，它对应的基可行解使目标函数值更小,
令 0? =
kmi
i
kmi
,
0,
m i n
=
kml
l
,?
,则把 lx 从原有的基中取出来，
把 kmx? 加进后得到的 （ 1x,2x,
,lx,kmx?,1?lx,
,mx ）仍是基，
即是所要找的新基,
改进方法：
返 回用 MATLAB优化工具箱解线性规划
min z=cX
bAXts?..
1、模型：
命令,x=linprog（ c,A,b）
2,模型,min z=cX
bAXts?..
b e qXA e q
命令,x=linprog（ c,A,b,Aeq,beq）
注意：若没有不等式,存在，则令 A=[ ],b=[ ].bAX?
3,模型,min z=cX
bAXts?..
b e qXA e q
VLB≤X≤VUB
命令,[1] x=linprog（ c,A,b,Aeq,beq,VLB,VUB）
[2] x=linprog（ c,A,b,Aeq,beq,VLB,VUB,X0）
注意,[1] 若没有等式约束,,则令 Aeq=[ ],
beq=[ ].
[2]其中 X0表示初始点
b e qXA e q
4、命令,[x,fval]=linprog(…)
返回最优解ｘ及ｘ处的目标函数值 fval.
解 编写 M文件 xxgh1.m如下：
c=[-0.4 -0.28 -0.32 -0.72 -0.64 -0.6];
A=[0.01 0.01 0.01 0.03 0.03 0.03;0.02 0 0 0.05 0 0;0 0.02 0 0 0.05 0;0 0
0.03 0 0 0.08];
b=[850;700;100;900];
Aeq=[]; beq=[];
vlb=[0;0;0;0;0;0]; vub=[];
[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)
例 1 m a x 654321 6.064.072.032.028.04.0 xxxxxxz
85 003.003.003.001.001.001.0.,654321 xxxxxxts
70005.002.0
41
xx
10 005.002.0 52 xx
90 008.003.0
63
xx
6,2,10 jx
j
To Matlab (xxgh1)
例 2 321 436m i n xxxz
120.,321 xxxts
301?x
500 2 x
203?x
解,编写 M文件 xxgh2.m如下：
c=[6 3 4];
A=[0 1 0];
b=[50];
Aeq=[1 1 1];
beq=[120];
vlb=[30,0,20];
vub=[];
[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)
To Matlab (xxgh2)
3
2
1)436(m i n
x
x
x
z
3
2
1
200
30
x
x
x
50
1 2 0
010
111,.
3
2
1
x
x
x
ts
S.t.
Xz 8121110913m i n?
9 0 0
8 0 0
3.12.15.0000
00011.14.0 X
500
600
400
100100
010010
001001
X,0
6
5
4
3
2
1
x
x
x
x
x
x
X
改写为：
例 3 问题一的解答 问题编写 M文件 xxgh3.m如下,
f = [13 9 10 11 12 8];
A = [0.4 1.1 1 0 0 0
0 0 0 0.5 1.2 1.3];
b = [800; 900];
Aeq=[1 0 0 1 0 0
0 1 0 0 1 0
0 0 1 0 0 1];
beq=[400 600 500];
vlb = zeros(6,1);
vub=[];
[x,fval] = linprog(f,A,b,Aeq,beq,vlb,vub)
To Matlab (xxgh3)
结果,
x =
0.0000
600.0000
0.0000
400.0000
0.0000
500.0000
fval =1.3800e+004
即在甲机床上加工 600个工件 2,在乙机床上加工 400个工件 1、
500个工件 3，可在满足条件的情况下使总加工费最小为 13800。
例 2 问题二的解答 问题
2
1
3640m i n
x
x
z
s,t, )45(35
2
1
x
x
改写为：
编写 M文件 xxgh4.m如下：
c = [40;36];
A=[-5 -3];
b=[-45];
Aeq=[];
beq=[];
vlb = zeros(2,1);
vub=[9;15];
%调用 linprog函数：
[x,fval] = linprog(c,A,b,Aeq,beq,vlb,vub)
To Matlab (xxgh4)
结果为：
x =
9.0000
0.0000
fval =360
即只需聘用 9个一级检验员。
注,本问题应还有一个约束条件,x1,x2取整数。故它是一个 整数线性规划 问题。这里把它当成一个线性规划来解，求得其最优解刚好是整数,x1=9,x2=0，故它就是该整数规划的最优解。若用线性规划解法求得的最优解不是整数，将其取整后不一定是相应整数规划的最优解，这样的整数规划应用专门的方法求解。
返 回投资的收益和风险一、问题提出市场上有 n 种资产
i
s
（ i =1,2 …… n ）可以选择，现用数额为 M 的相当大的资金作一个时期的投资。这 n 种资产在这一时期内购买 i
s
的平均收益率为 i
r
，风险损失率为 i
q
，投资越分散，总的风险越小，总体风险可用投资的 i
s
中最大的一个风险来度量。
购买 i
s
时要付交易费,( 费率 i
p
),当购买额不超过给定值 i
u
时，交易费按购买 i
u
计算。另外，假定同期银行存款利率是
0
r
，既无交易费又无风险。 （
0
r
=5% ）
已知 n=4 时相关数据如下：
i
s
i
r
（ % ） i
q
（ % ） i
p
（ % ） i
u
（元）
S
1
28 2,5 1 1 0 3
S
2
21 1,5 2 1 9 8
S
3
23 5,5 4,5 52
S
4
25 2,6 6,5 40
试给该公司设计一种投资组合方案，即用给定达到资金 M,有选择地购买若干种资产或存银行生息，使净收益尽可能大，使总体风险尽可能小。
基本假设：
1,投资数额 M 相当大,为了便于计算，假设 M=1 ；
2,投资越分散，总的风险越小；
3,总体风险用投资项目
i
s 中最大的一个风险来度量；
4,n 种资产 S i 之间是相互独立的；
5,在投资的这一时期内,r i,p i,q i,r 0 为定值，不受意外因素影响；
6,净收益和总体风险只受 r i,p i,q i 影响，不受其他因素干扰。
二、基本假设和符号规定符号规定：
S i ——第 i 种投资项目，如股票，债券
r i,p i,q i - - - - 分别为 S i 的平均收益率,风险损失率，交易费率
u i ---- S i 的交易定额
0
r - - - - - - - 同期银行利率
x i ----- -- 投资项目 S i 的资金 a - - - - - 投资风险度
Q ---- 总体收益 Δ Q ---- 总体收益的增量三、模型的建立与分析
1.总体风险用所投资的 Si中最大的一个风险来衡量,即 max{ qixi|i=1,2,…n}2,购买 S
i 所付交易费是一个分段函数,即
p ix i x i> u i
交易费 =
p iu i x i≤ u i
而题目所给定的定值 u i( 单位,元 ) 相对总投资 M 很小,p iu i 更小,
可以忽略不计,这样购买 S i 的净收益为 ( r i-p i) x i
3,要使净收益尽可能大，总体风险尽可能小,这是一个多目标规划模型,
目标函数 M A X?
n
i
iii
xpr
0
)(
M I Nm a x { q
i
x
i
}
约束条件?
n
i
ii
xp
0
)1( =M
x
i
≥ 0 i = 0,1,… n
4,模型简化：
c,投资者在权衡资产风险和预期收益两方面时，希望选择一个令自己满意的投资组合。
因此对风险、收益赋予权重 s （ 0 ＜ s ≤ 1),s 称为投资偏好系数,
模型 3 目标函数,m i n s { m a x { q ix i } } - （ 1 - s ）?
n
i
iii
xpr
0
)(
约束条件?
n
i
ii
xp
0
)1( =M,x
i≥ 0 i = 0,1,2,… n
b,若投资者希望总盈利至少达到水平 k 以上，在风险最小的情况下寻找相应的投资组合。
模型 2 固定盈利水平，极小化风险目标函数,R = m i n { m a x { q
i
x
i
}}
约束条件,?
n
i
iii
xpr
0
)( ≥ k,
Mxp ii )1(,x
i
≥ 0 i =0,1,… n
a,在实际投资中，投资者承受风险的程度不一样，若给定风险一个界限 a,使最大的一个风险 q
i
x
i
/M ≤ a,可找到相应的投资方案。这样把多目标规划变成一个目标的线性规划。
模型 1 固定风险水平，优化收益目标函数,Q = M A X?
1
1
)(
n
i
iii
xpr
约束条件,
M
xq
ii
≤ a
Mxp ii )1(,x
i
≥ 0 i =0,1,… n
四、模型 1的求解模型 1 为,
m i n f = ( - 0,05,- 0,27,- 0,19,- 0,185,- 0,185 ) ( x
0
x
1
x
2
x
3
x
4
)
T
x
0
+ 1,01x
1
+ 1,02x
2
+ 1,045 x
3
+ 1,065 x
4
= 1
s,t,0,025 x
1
≤ a
0,0 1 5 x
2
≤ a
0,0 5 5 x
3
≤ a
0,0 2 6 x
4
≤ a
x
i
≥ 0 ( i = 0,1,…..4)
由于 a是任意给定的风险度，到底怎样给定没有一个准则，不同的投资者有不同的风险度。我们从 a=0开始，以步长 △ a=0.001进行循环搜索，编制程序如下：
a=0;
while(1.1-a)>1
c=[-0.05 -0.27 -0.19 -0.185 -0.185];
Aeq=[1 1.01 1.02 1.045 1.065]; beq=[1];
A=[0 0.025 0 0 0;0 0 0.015 0 0;0 0 0 0.055 0;0 0 0 0 0.026];
b=[a;a;a;a];
vlb=[0,0,0,0,0];vub=[];
[x,val]=linprog(c,A,b,Aeq,beq,vlb,vub);
a
x=x'
Q=-val
plot(a,Q,'.'),axis([0 0.1 0 0.5]),hold on
a=a+0.001;
end
xlabel('a'),ylabel('Q')
To Matlab（ xxgh5）
a = 0,0 0 3 0 x = 0,4 9 4 9 0,1 2 0 0 0,2 0 0 0 0,0 5 4 5 0,1 1 5 4 Q = 0,1 2 6 6
a = 0,0 0 6 0 x = 0 0,2 4 0 0 0,4 0 0 0 0,1 0 9 1 0,2 2 1 2 Q = 0,2 0 1 9
a = 0,0 0 8 0 x = 0,0 0 0 0 0,3 2 0 0 0,5 3 3 3 0,1 2 7 1 0,0 0 0 0 Q = 0,2 1 1 2
a = 0,0 1 0 0 x = 0 0,4 0 0 0 0,5 8 4 3 0 0 Q =0,2 1 9 0
a = 0,0 2 0 0 x = 0 0,8 0 0 0 0,1 8 8 2 0 0 Q =0,2 5 1 8
a = 0,0 4 0 0 x = 0,0 0 0 0 0,9 9 0 1 0,0 0 0 0 0 0 Q =0,2 6 7 3
计算结果：
五,结果分析返 回
4.在 a=0.006附近有一个转折点，在这一点左边，风险增加很少时，利润增长很快。在这一点右边，风险增加很大时，利润增长很缓慢，所以对于风险和收益没有特殊偏好的投资者来说，应该选择曲线的拐点作为最优投资组合，
大约是 a*=0.6%,Q*=20%,所对应投资方案为,
风险度 收益 x0 x1 x2 x3 x4
0.0060 0.2019 0 0.2400 0.4000 0.1091 0.2212
3.曲线上的任一点都表示该风险水平的最大可能收益和该收益要求的最小风险。对于不同风险的承受能力，选择该风险水平下的最优投资组合。
2.当投资越分散时，投资者承担的风险越小，这与题意一致。即,
冒险的投资者会出现集中投资的情况，保守的投资者则尽量分散投资。
1.风险大，收益也大。
实验作业某厂生产甲乙两种口味的饮料,每百箱甲饮料需用原料 6千克,
工人 10名,可获利 10万元 ;每百箱乙饮料需用原料 5千克,工人 20
名,可获利 9万元,今工厂共有原料 60千克,工人 150名,又由于其他条件所限甲饮料产量不超过 8百箱,问如何安排生产计划,即两种饮料各生产多少使获利最大,进一步讨论,
1)若投资 0.8万元可增加原料 1千克,问应否作这项投资,
2)若每百箱甲饮料获利可增加 1万元,问应否改变生产计划,
返 回
2、掌握用数学软件包求解线性规划问题。
1、了解线性规划的基本内容。
*2、线性规划的基本算法。
5、实验作业。
3、用数学软件包求解线性规划问题。
1、两个引例。
4、建模案例：投资的收益与风险问题一,任务分配问题：某车间有甲、乙两台机床，可用于加工三种工件。假定这两台车床的可用台时数分别为 800和
900，三种工件的数量分别为 400,600和 500，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表。问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？
单位工件所需加工台时数 单位工件的加工费用 车床类 型 工件 1 工件 2 工件 3 工件 1 工件 2 工件 3
可用台时数甲 0,4 1,1 1,0 13 9 10 800
乙 0,5 1,2 1,3 11 12 8 900
两个引例解 设在甲车床上加工工件 1,2,3的数量分别为 x1,x2,x3，
在乙车床上加工工件 1,2,3的数量分别为 x4,x5,x6。可建立以下线性规划模型：
654321
8121110913m i n xxxxxxz
6,,2,1,0
9 0 03.12.15.0
8 0 01.14.0
5 0 0
6 0 0
4 0 0x
,.
654
321
63
52
41
ix
xxx
xxx
xx
xx
x
ts
i
解答问题二,某厂每日 8小时的产量不低于 1800件。为了进行质量控制，计划聘请两种不同水平的检验员。一级检验员的标准为：速度 25件 /小时，正确率 98%，计时工资 4元 /小时；二级检验员的标准为：速度 15小时 /件，正确率 95%，计时工资 3元 /小时。检验员每错检一次，工厂要损失 2元。为使总检验费用最省，该工厂应聘一级、二级检验员各几名？
解 设需要一级和二级检验员的人数分别为 x1,x2人,
则应付检验员的工资为：
2121 24323848 xxxx因检验员错检而造成的损失为：
2121 1282)%5158%2258( xxxx
故目标函数为：
212121 3640)128()2432(m i n xxxxxxz
约束条件为：
0,0
1 8 0 0158
1 8 0 0258
1 8 0 0158258
21
2
1
21
xx
x
x
xx
线性规划模型：
21 3640m i n xxz
0,0
15
9
4535
,.
21
2
1
21
xx
x
x
xx
ts
解答返 回
1.线性规划的标准形式：
x
m i n z = )( xf
.,ts )( xg i? 0 （ ),,2,1 mi
其中目标函数 )( xf 和约束条件中 )( xg i 都是线性函数
m i n f = cx
s,t,A x = b （ 1 ）
x
0
这里
A
= ( ija )
m,n
,x =
T
21 n
xxx?
b =
T
21 n
bbb?,
c
=nccc?21
用单纯法求解时，常将标准形式化为：
2,线性规划的基本算法 —— 单纯形法线性规划的基本算法 —— 单纯形法例 m i n z = 1 0 x 1 + 9 x 2
s,t,6x 1 + 5 x 2 ≤ 6 0
1 0 x 1 + 2 0 x 2 ≥ 1 5 0
x 1 ≤ 8
x 1,x 2 ≥ 0
引入松弛变量 x3,x4,x5,将不等式化为等式,即单纯形标准形,
m i n z = 1 0 x 1 + 9 x 2
s,t,6x 1 + 5 x 2 + x 3 = 6 0
1 0 x 1 + 2 0 x 2 - x 4 = 1 5 0
x 1 + x 5 = 8
x i≥ 0 ( i = 1,2,3,4,5 )
系数矩阵为,6 5 1 0 0
A = 1 0 2 0 0 - 1 0 = ( P 1 P 2 P 3 P 4 P 5 )
1 0 0 0 1
b = ( 6 0,1 5 0,8 ) T
显然 A的秩 ran(A)=3,任取 3个线性无关的列向量,如 P3 P4 P5称为一组 基,记为 B,其余列向量称为 非基,记为 N,
于是 f = cBxB + cNxN,Ax = BxB + NxN = b,
则 xB = B-1b-B-1NxN,f = cBB-1b + (cN – cBB-1N)xN
令非基变量 x N = 0,解得基变量 x B = B1? b,称 ( x B,x N ) 为 基解,
基解的所有变量的值都非负，则称为 基可行解,此时的基称为 可行基,
若可行基进一步满足,cN – cBB-1N≥0,即,cBB-1N - cN≤0
则对一切可行解 x,必有 f(x) ≥ cBB-1b,此时称基可行解 x = (B-1b,0) T
为 最优解,
3,最优解的存在性定理将 A的列向量重排次序成 A = (B,N),相应 x = (xB,xN) T,c = (cB,cN)
基对应的变量 xB称为 基变量,非基对应的变量 xN称为 非基变量,
定理 1 如果线性规划 (1)有可行解，那么一定有基可行解,
定理 2 如果线性规划 (1)有最优解，那么一定存在一个基可行解是最优解,
4,基可行解是最优解的判定准则因为 f = cBB-1b + (cN – cBB-1N)xN，
即 f - 0?xB + (cBB-1N- cN )xN = cBB-1b
若基 B = (
1
P,
2
P,
,
m
P ),非基 N = (
1?m
P,
2?m
P,?,
n
P ),
令 j
=
B
c
1?
B
j
P
- j
c
,j=m+1,m+2,
,n,则 ( 1 ) 可写成
min f
s.t,
B
x +
1?
B N N
x
=
1?
B b
f + 0 ·
B
x +
n
mj
jj
x
1
=
B
c
1?
B b
x
0
称为 （ 1 ）式的 典式,
定理 3 设 （ 1x,2x,?,mx ）是规划 ( 1 ) 的一个可行基,B 是对应的基阵,如果典式中的 1?,2?,?,m? 都不大于零,即对应的 1?m 0,2?m 0,
,n 0,则基 （ 1x,2x,
,mx ）对应的基可行解
0X
=
0
1 bB
是最优解,
令
1?B b
=
m?
2
1
，
1?B N
=
nmmmmm
nmm
nmm
,2,1,
,22,21,2
,12,11,1
5.基可行解的改进线性规划 （ 1 ）的典式变为：
min f
s.t,ix +?
n
mj
jij
x
1
= i? i = 1,2,?,m
f + 0 ·
B
x +?
n
mj
jj
x
1
= Bc
1?
B b
x
0
定理 4 设 （
1
x,
2
x,?,mx ）是规划 ( 1 ) 的一个可行基，
B 是对应的基阵,如果存在
km?
> 0,使
1)
km?,1
,
km?,2
,?,
kmm?,
中至少有一个大于零；
2) 所有的 i
> 0,i =1,2,?,m
则一定存在另一个可行基，它对应的基可行解使目标函数值更小,
令 0? =
kmi
i
kmi
,
0,
m i n
=
kml
l
,?
,则把 lx 从原有的基中取出来，
把 kmx? 加进后得到的 （ 1x,2x,
,lx,kmx?,1?lx,
,mx ）仍是基，
即是所要找的新基,
改进方法：
返 回用 MATLAB优化工具箱解线性规划
min z=cX
bAXts?..
1、模型：
命令,x=linprog（ c,A,b）
2,模型,min z=cX
bAXts?..
b e qXA e q
命令,x=linprog（ c,A,b,Aeq,beq）
注意：若没有不等式,存在，则令 A=[ ],b=[ ].bAX?
3,模型,min z=cX
bAXts?..
b e qXA e q
VLB≤X≤VUB
命令,[1] x=linprog（ c,A,b,Aeq,beq,VLB,VUB）
[2] x=linprog（ c,A,b,Aeq,beq,VLB,VUB,X0）
注意,[1] 若没有等式约束,,则令 Aeq=[ ],
beq=[ ].
[2]其中 X0表示初始点
b e qXA e q
4、命令,[x,fval]=linprog(…)
返回最优解ｘ及ｘ处的目标函数值 fval.
解 编写 M文件 xxgh1.m如下：
c=[-0.4 -0.28 -0.32 -0.72 -0.64 -0.6];
A=[0.01 0.01 0.01 0.03 0.03 0.03;0.02 0 0 0.05 0 0;0 0.02 0 0 0.05 0;0 0
0.03 0 0 0.08];
b=[850;700;100;900];
Aeq=[]; beq=[];
vlb=[0;0;0;0;0;0]; vub=[];
[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)
例 1 m a x 654321 6.064.072.032.028.04.0 xxxxxxz
85 003.003.003.001.001.001.0.,654321 xxxxxxts
70005.002.0
41
xx
10 005.002.0 52 xx
90 008.003.0
63
xx
6,2,10 jx
j
To Matlab (xxgh1)
例 2 321 436m i n xxxz
120.,321 xxxts
301?x
500 2 x
203?x
解,编写 M文件 xxgh2.m如下：
c=[6 3 4];
A=[0 1 0];
b=[50];
Aeq=[1 1 1];
beq=[120];
vlb=[30,0,20];
vub=[];
[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)
To Matlab (xxgh2)
3
2
1)436(m i n
x
x
x
z
3
2
1
200
30
x
x
x
50
1 2 0
010
111,.
3
2
1
x
x
x
ts
S.t.
Xz 8121110913m i n?
9 0 0
8 0 0
3.12.15.0000
00011.14.0 X
500
600
400
100100
010010
001001
X,0
6
5
4
3
2
1
x
x
x
x
x
x
X
改写为：
例 3 问题一的解答 问题编写 M文件 xxgh3.m如下,
f = [13 9 10 11 12 8];
A = [0.4 1.1 1 0 0 0
0 0 0 0.5 1.2 1.3];
b = [800; 900];
Aeq=[1 0 0 1 0 0
0 1 0 0 1 0
0 0 1 0 0 1];
beq=[400 600 500];
vlb = zeros(6,1);
vub=[];
[x,fval] = linprog(f,A,b,Aeq,beq,vlb,vub)
To Matlab (xxgh3)
结果,
x =
0.0000
600.0000
0.0000
400.0000
0.0000
500.0000
fval =1.3800e+004
即在甲机床上加工 600个工件 2,在乙机床上加工 400个工件 1、
500个工件 3，可在满足条件的情况下使总加工费最小为 13800。
例 2 问题二的解答 问题
2
1
3640m i n
x
x
z
s,t, )45(35
2
1
x
x
改写为：
编写 M文件 xxgh4.m如下：
c = [40;36];
A=[-5 -3];
b=[-45];
Aeq=[];
beq=[];
vlb = zeros(2,1);
vub=[9;15];
%调用 linprog函数：
[x,fval] = linprog(c,A,b,Aeq,beq,vlb,vub)
To Matlab (xxgh4)
结果为：
x =
9.0000
0.0000
fval =360
即只需聘用 9个一级检验员。
注,本问题应还有一个约束条件,x1,x2取整数。故它是一个 整数线性规划 问题。这里把它当成一个线性规划来解，求得其最优解刚好是整数,x1=9,x2=0，故它就是该整数规划的最优解。若用线性规划解法求得的最优解不是整数，将其取整后不一定是相应整数规划的最优解，这样的整数规划应用专门的方法求解。
返 回投资的收益和风险一、问题提出市场上有 n 种资产
i
s
（ i =1,2 …… n ）可以选择，现用数额为 M 的相当大的资金作一个时期的投资。这 n 种资产在这一时期内购买 i
s
的平均收益率为 i
r
，风险损失率为 i
q
，投资越分散，总的风险越小，总体风险可用投资的 i
s
中最大的一个风险来度量。
购买 i
s
时要付交易费,( 费率 i
p
),当购买额不超过给定值 i
u
时，交易费按购买 i
u
计算。另外，假定同期银行存款利率是
0
r
，既无交易费又无风险。 （
0
r
=5% ）
已知 n=4 时相关数据如下：
i
s
i
r
（ % ） i
q
（ % ） i
p
（ % ） i
u
（元）
S
1
28 2,5 1 1 0 3
S
2
21 1,5 2 1 9 8
S
3
23 5,5 4,5 52
S
4
25 2,6 6,5 40
试给该公司设计一种投资组合方案，即用给定达到资金 M,有选择地购买若干种资产或存银行生息，使净收益尽可能大，使总体风险尽可能小。
基本假设：
1,投资数额 M 相当大,为了便于计算，假设 M=1 ；
2,投资越分散，总的风险越小；
3,总体风险用投资项目
i
s 中最大的一个风险来度量；
4,n 种资产 S i 之间是相互独立的；
5,在投资的这一时期内,r i,p i,q i,r 0 为定值，不受意外因素影响；
6,净收益和总体风险只受 r i,p i,q i 影响，不受其他因素干扰。
二、基本假设和符号规定符号规定：
S i ——第 i 种投资项目，如股票，债券
r i,p i,q i - - - - 分别为 S i 的平均收益率,风险损失率，交易费率
u i ---- S i 的交易定额
0
r - - - - - - - 同期银行利率
x i ----- -- 投资项目 S i 的资金 a - - - - - 投资风险度
Q ---- 总体收益 Δ Q ---- 总体收益的增量三、模型的建立与分析
1.总体风险用所投资的 Si中最大的一个风险来衡量,即 max{ qixi|i=1,2,…n}2,购买 S
i 所付交易费是一个分段函数,即
p ix i x i> u i
交易费 =
p iu i x i≤ u i
而题目所给定的定值 u i( 单位,元 ) 相对总投资 M 很小,p iu i 更小,
可以忽略不计,这样购买 S i 的净收益为 ( r i-p i) x i
3,要使净收益尽可能大，总体风险尽可能小,这是一个多目标规划模型,
目标函数 M A X?
n
i
iii
xpr
0
)(
M I Nm a x { q
i
x
i
}
约束条件?
n
i
ii
xp
0
)1( =M
x
i
≥ 0 i = 0,1,… n
4,模型简化：
c,投资者在权衡资产风险和预期收益两方面时，希望选择一个令自己满意的投资组合。
因此对风险、收益赋予权重 s （ 0 ＜ s ≤ 1),s 称为投资偏好系数,
模型 3 目标函数,m i n s { m a x { q ix i } } - （ 1 - s ）?
n
i
iii
xpr
0
)(
约束条件?
n
i
ii
xp
0
)1( =M,x
i≥ 0 i = 0,1,2,… n
b,若投资者希望总盈利至少达到水平 k 以上，在风险最小的情况下寻找相应的投资组合。
模型 2 固定盈利水平，极小化风险目标函数,R = m i n { m a x { q
i
x
i
}}
约束条件,?
n
i
iii
xpr
0
)( ≥ k,
Mxp ii )1(,x
i
≥ 0 i =0,1,… n
a,在实际投资中，投资者承受风险的程度不一样，若给定风险一个界限 a,使最大的一个风险 q
i
x
i
/M ≤ a,可找到相应的投资方案。这样把多目标规划变成一个目标的线性规划。
模型 1 固定风险水平，优化收益目标函数,Q = M A X?
1
1
)(
n
i
iii
xpr
约束条件,
M
xq
ii
≤ a
Mxp ii )1(,x
i
≥ 0 i =0,1,… n
四、模型 1的求解模型 1 为,
m i n f = ( - 0,05,- 0,27,- 0,19,- 0,185,- 0,185 ) ( x
0
x
1
x
2
x
3
x
4
)
T
x
0
+ 1,01x
1
+ 1,02x
2
+ 1,045 x
3
+ 1,065 x
4
= 1
s,t,0,025 x
1
≤ a
0,0 1 5 x
2
≤ a
0,0 5 5 x
3
≤ a
0,0 2 6 x
4
≤ a
x
i
≥ 0 ( i = 0,1,…..4)
由于 a是任意给定的风险度，到底怎样给定没有一个准则，不同的投资者有不同的风险度。我们从 a=0开始，以步长 △ a=0.001进行循环搜索，编制程序如下：
a=0;
while(1.1-a)>1
c=[-0.05 -0.27 -0.19 -0.185 -0.185];
Aeq=[1 1.01 1.02 1.045 1.065]; beq=[1];
A=[0 0.025 0 0 0;0 0 0.015 0 0;0 0 0 0.055 0;0 0 0 0 0.026];
b=[a;a;a;a];
vlb=[0,0,0,0,0];vub=[];
[x,val]=linprog(c,A,b,Aeq,beq,vlb,vub);
a
x=x'
Q=-val
plot(a,Q,'.'),axis([0 0.1 0 0.5]),hold on
a=a+0.001;
end
xlabel('a'),ylabel('Q')
To Matlab（ xxgh5）
a = 0,0 0 3 0 x = 0,4 9 4 9 0,1 2 0 0 0,2 0 0 0 0,0 5 4 5 0,1 1 5 4 Q = 0,1 2 6 6
a = 0,0 0 6 0 x = 0 0,2 4 0 0 0,4 0 0 0 0,1 0 9 1 0,2 2 1 2 Q = 0,2 0 1 9
a = 0,0 0 8 0 x = 0,0 0 0 0 0,3 2 0 0 0,5 3 3 3 0,1 2 7 1 0,0 0 0 0 Q = 0,2 1 1 2
a = 0,0 1 0 0 x = 0 0,4 0 0 0 0,5 8 4 3 0 0 Q =0,2 1 9 0
a = 0,0 2 0 0 x = 0 0,8 0 0 0 0,1 8 8 2 0 0 Q =0,2 5 1 8
a = 0,0 4 0 0 x = 0,0 0 0 0 0,9 9 0 1 0,0 0 0 0 0 0 Q =0,2 6 7 3
计算结果：
五,结果分析返 回
4.在 a=0.006附近有一个转折点，在这一点左边，风险增加很少时，利润增长很快。在这一点右边，风险增加很大时，利润增长很缓慢，所以对于风险和收益没有特殊偏好的投资者来说，应该选择曲线的拐点作为最优投资组合，
大约是 a*=0.6%,Q*=20%,所对应投资方案为,
风险度 收益 x0 x1 x2 x3 x4
0.0060 0.2019 0 0.2400 0.4000 0.1091 0.2212
3.曲线上的任一点都表示该风险水平的最大可能收益和该收益要求的最小风险。对于不同风险的承受能力，选择该风险水平下的最优投资组合。
2.当投资越分散时，投资者承担的风险越小，这与题意一致。即,
冒险的投资者会出现集中投资的情况，保守的投资者则尽量分散投资。
1.风险大，收益也大。
实验作业某厂生产甲乙两种口味的饮料,每百箱甲饮料需用原料 6千克,
工人 10名,可获利 10万元 ;每百箱乙饮料需用原料 5千克,工人 20
名,可获利 9万元,今工厂共有原料 60千克,工人 150名,又由于其他条件所限甲饮料产量不超过 8百箱,问如何安排生产计划,即两种饮料各生产多少使获利最大,进一步讨论,
1)若投资 0.8万元可增加原料 1千克,问应否作这项投资,
2)若每百箱甲饮料获利可增加 1万元,问应否改变生产计划,
返 回
