当前位置:首页 >> 其它课程 >> 数学建模与数学实验线性规划

数学建模与数学实验线性规划


数学建模与数学实验
线性规划
后勤工程学院数学教研室

实验目的
1、了解线性规划的基本内容。

2、掌握用数学软件包求解线性规划问题。

实验内容
1、两个引例。 *2、线性规划的基本算法。 3、用数学软件包求解线性规划问题。 4、建模案例:投资的收益与风险 5、实验作业。

r />
两个引例 问题一 : 任务分配问题:某车间有甲、乙两台机床,可用
于加工三种工件。假定这两台车床的可用台时数分别为800和 900,三种工件的数量分别为400、600和500,且已知用三种 不同车床加工单位数量不同工件所需的台时数和加工费用如 下表。问怎样分配车床的加工任务,才能既满足加工工件的 要求,又使加工费用最低?
车床 类 型 甲 乙 单位工件所需加工台时数 工件 1 0.4 0.5 工件 2 1.1 1.2 工件 3 1.0 1.3 单位工件的加工费用 工件 1 13 11 工件 2 9 12 工件 3 10 8 可用台 时数 800 900



设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3, 在乙车床上加工工件1、2、3的数量分别为x4、x5、x6。可建立 以下线性规划模型:
min z ? 13 x1 ? 9 x 2 ? 10 x 3 ? 11 x 4 ? 12 x 5 ? 8 x 6

?x 1 ? x 4 ? 400 ? x ? x ? 600 5 ? 2 ? x3 ? x6 ? 500 ? s.t. ? ?0.4 x1 ? 1.1x 2 ? x3 ? 800 ?0.5 x 4 ? 1.2 x5 ? 1.3x6 ? 900 ? ? xi ? 0, i ? 1,2,?,6 ?

解答

问题二: 某厂每日8小时的产量不低于1800件。为了进行质
量控制,计划聘请两种不同水平的检验员。一级检验员的标准 为:速度25件/小时,正确率98%,计时工资4元/小时;二级检 验员的标准为:速度15件/小时,正确率95%,计时工资3元/小 时。检验员每错检一次,工厂要损失2元。为使总检验费用最 省,该工厂应聘一级、二级检验员各几名? 解 设需要一级和二级检验员的人数分别为x1、x2人, 则应付检验员的工资为:

8 ? 4 ? x1 ? 8 ? 3 ? x2 ? 32 x1 ? 24 x2
因检验员错检而造成的损失为:

(8 ? 25 ? 2% ? x1 ? 8 ?15 ? 5% ? x2 ) ? 2 ? 8x1 ? 12 x2

故目标函数为:

min z ? (32 x1 ? 24 x2 ) ? (8x1 ? 12 x2 ) ? 40 x1 ? 36 x2
约束条件为:

?8 ? 25 ? x1 ? 8 ? 15 ? x2 ? 1800 ?8 ? 25 ? x ? 1800 ? 1 ? ?8 ? 15 ? x2 ? 1800 ? x1 ? 0, x2 ? 0 ?

线性规划模型:

min z ? 40 x1 ? 36 x2

?5 x1 ? 3 x2 ? 45 ?x ? 9 ? 1 s.t. ? ? x2 ? 15 ? x1 ? 0, x2 ? 0 ?
返 回

解答

线性规划的基本算法——单纯形法
1.线性规划的标准形式:
min z = f (x)
x

s.t . g i (x )? 0 ( i ? 1,2,?, m)

其中目标函数 f (x) 和约束条件中gi (x) 都是线性函数

2. 线性规划的基本算法——单纯形法

用单纯法求解时,常将标准形式化为:
c min f = x b s.t. Ax = x ?
这里 A = (aij )m,n , x

(1) 0

= ?x1 x2 ? xn ? T

b = ?b1

b2 ? bn ? T ,

c

= ?c1 c 2 ? c n ?



min z = 10x1 + 9x2 s.t.6x1 + 5x2 ≤ 60 10x1 + 20x2 ≥ 150 x1 ≤ 8 x1, x2 ≥ 0

引入松弛变量x3, x4, x5, 将不等式化为等式, 即单纯形标准形: min z = 10x1 + 9x2 s.t.6x1 + 5x2 + x3 = 60 10x1 + 20x2 - x4 = 150 x1 + x5 = 8 xi≥ 0 (i = 1,2,3,4,5) 系数矩阵为: 6 5 1 0 0 A = 10 20 0 -1 0 = (P1 P2 P3 P4 P5) 1 0 0 0 1 b = (60, 150, 8 ) T 显然A的秩ran(A)=3, 任取3个线性无关的列向量,如P3 P4 P5称为 一组基, 记为B. 其余列向量称为非基, 记为N .

将A的列向量重排次序成A = (B, N), 相应x = (xB, xN) T, c = (cB, cN) 基对应的变量xB称为基变量, 非基对应的变量xN称为非基变量. 于是 f = cBxB + cNxN , Ax = BxB + NxN = b, 则 xB = B-1b-B-1NxN , f = cBB-1b + (cN – cBB-1N)xN
? 令非基变量 xN = 0, 解得基变量 xB = 1B b, 称(xB, xN)为基解. 基解的所有变量的值都非负,则称为基可行解,此时的基称为可行基.

若可行基进一步满足: cN – cBB-1N≥0, 即: cBB-1N - cN≤0 则对一切可行解x, 必有f(x) ≥ cBB-1b, 此时称基可行解x = (B-1b, 0) T 为最优解. 3. 最优解的存在性定理 定理1
定理2

如果线性规划(1)有可行解,那么一定有基可行解.
如果线性规划(1)有最优解,那么一定存在一个基可行解 是最优解.

4. 基可行解是最优解的判定准则 因为 f = cBB-1b + (cN – cBB-1N)xN, 即 f - 0?xB + (cBB-1N- cN )xN = cBB-1b
?1

若基 B =(P ,P2 ,? ,Pm ), 非基N =(Pm ?1 , Pm ? 2 ? Pn, , 1 令 ? j = cB B min s.t.

),

Pj - j ,j=m+1,m+2, ? ,n ,则 (1) 可写成 c

f

xB + B
f

?1

1 N x N =B ?b

+ 0·xB +

0 称为(1)式的典式. B 定理 3 设( 1 , 2 , ,xm )是规划 (1) 的一个可行基, x x ? ? ? ? 的基阵,如果典式中的 ,? , , ? 都不大于零,即对应的 ?
1 2
m m ?1

x ?

j ? m ?1

?? x
j

n

j

= cBB b

?1

是对应

? 0,?m ? 2

0,

?

x x , ?n ? 0,则基( 1 , 2 ,

?

X ,xm )对应的基可行解

0

? B ?1b ? ? =? ? 0 ? ? ?

是最优解.

5.基可行解的改进
? ? 1,m?1 ? ?1 ? ? ? ? ? ? 2,m ?1 ??2 ? ?1 ?1 B N = ? 令B b = ? ?, ? ? ? ? ? ?? ? ?? ? m? ? m,m ?1
线性规划(1)的典式变为: min f s.t. xi +

? 1,m? 2 ? 2,m ? 2
?

? 1,n ? ? ? ? 2,n ?
? ? ? ? ? ? ? m,n ? ?

? m,m? 2

j ? m ?1

??

n

ij

x j = ? ii
n

=1,2,? ,m
?1

f
x ?

+ 0·xB + 0

j ? m ?1

? ? j x j =cBB b

定理 4 1) 2)

B 是对应的基阵,如果存在 ? m? k >0,使 i 所有的? i >0, =1,2, ? ,m

x x ? 设( 1 , 2 , ,xm )是规划 (1) 的一个可行基,

?1,m?k , ? 2,m?k , , ? m,m? k 中至少有一个大于零; ?

则一定存在另一个可行基,它对应的基可行解使目标函数值更小.

改进方法:
? ?i ? ? ? 令? 0 = min ? ? = ? i , m ? k ?0 ? ? ? i ,m? k ? ? x x 把 x m ? k 加进后得到的( 1 , 2
即是所要找的新基.

?l xl ,则把 从原有的基中取出来, ? l ,m? k
,
?

xl ,

, x m ? kx,?1 l

?

,

xm )仍是基, ,

返 回

用MATLAB优化工具箱解线性规划
1、模型: min z=cX s.t. AX ? b 命令:x=linprog(c,A,b)

2、模型:min z=cX s.t. AX ? b Aeq ? X ? beq 命令:x=linprog(c,A,b,Aeq,beq)
AX 注意:若没有不等式: ? b 存在,则令A=[ ],b=[ ].

3、模型:min z=cX s.t. AX ? b Aeq ? X ? beq 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 ? X ? beq , 则令Aeq=[ ], beq=[ ]. [2]其中X0表示初始点 4、命令:[x,fval]=linprog(…) 返回最优解x及x处的目标函数值fval.

例 1 max

s.t.

z ? 0.4 x1 ? 0.28 x 2 ? 0.32 x 3 ? 0.72 x 4 ? 0.64 x 5 ? 0.6 x 6 0.01 x1 ? 0.01 x 2 ? 0.01 x 3 ? 0.03 x 4 ? 0.03 x 5 ? 0.03 x 6 ? 850

0.02x1 ? 0.05x 4 ? 700
0.02 x 2 ? 0.05 x 5 ? 100 0.03 x 3 ? 0.08 x 6 ? 900 xj ? 0 j ? 1,2, ? 6

解 编写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)

To Matlab (xxgh1)

例2

min z ? 6 x1 ? 3 x 2 ? 4 x 3

m in z ? (6

3

s.t.

x1 ? x 2 ? x 3 ? 120

? x1 4)? x 2 ? ? x3

? ? ? ?

x1 ? 30 0 ? x2 ? 50
x 3 ? 20

s.t .

?1 ? ?0 ?

解: 编写M文件xxgh2.m如下: c=[6 3 4]; A=[0 1 0]; b=[50]; Aeq=[1 1 1]; beq=[120]; To Matlab (xxgh2) vlb=[30,0,20]; vub=[]; [x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)

? x1 1 ?? ?? x2 1 0 ?? ? x ? 3 ? x1 ? ? 3 0? ? 0 ? ? ?x ? ? 2? ? 2 0? ? ? ? x3 ? 1

? ? ?1 2 0? ??? ? 50 ? ? ? ? ? ?

例3 问题一的解答
改写为: S.t.

问题

min z ? ?13 9 10 11 12 8?X
0 0? ? 0.4 1.1 1 0 ? 800 ? ? ?X ? ? ? 0 ? ? 900 ? ? 0 0 0.5 1.2 1.3 ? ? ? ?
? x1 ? ? ? ? x2 ? ?x ? 3 ,X ?? ??0 ? x4 ? ?x ? ? 5? ?x ? ? 6?

?1 0 0 1 0 0? ? 400 ? ? ? ? ? ? 0 1 0 0 1 0 ? X ? ? 600 ? ?0 0 1 0 0 1? ? 500 ? ? ? ? ?

编写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 010010 0 0 1 0 0 1]; To Matlab (xxgh3) beq=[400 600 500]; vlb = zeros(6,1); vub=[]; [x,fval] = linprog(f,A,b,Aeq,beq,vlb,vub)

结果:
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 问题二的解答
改写为:

问题

? x1 ? min z ? ?40 36 ?? ? ?x ? ? 2? ? x1 ? s.t. ?? 5 ? 3?? ? ? (?45) ?x ? ? 2?

编写M文件xxgh4.m如下:
c = [40;36]; A=[-5 -3]; b=[-45]; Aeq=[]; To Matlab (xxgh4) beq=[]; vlb = zeros(2,1); vub=[9;15]; %调用linprog函数: [x,fval] = linprog(c,A,b,Aeq,beq,vlb,vub)

结果为: x= 9.0000 0.0000 fval =360 即只需聘用9个一级检验员。

注:本问题应还有一个约束条件:x1、x2取整数。故它
是一个整数线性规划问题。这里把它当成一个线性规划来 解,求得其最优解刚好是整数:x1=9,x2=0,故它就是该 整数规划的最优解。若用线性规划解法求得的最优解不是 整数,将其取整后不一定是相应整数规划的最优解,这样 的整数规划应用专门的方法求解。
返 回

投资的收益和风险
一、问题提出
市场上有 n 种资产 s i (i=1,2……n)可以选择,现用数额为 M 的相当大的资金作一个时期 的投资。这 n 种资产在这一时期内购买 s i 的平均收益率为 购买 s i 时要付交易费,(费率

ri ,风险损失率为 qi ,投资越

分散,总的风险越小,总体风险可用投资的 s i 中最大的一个风险来度量。

pi ),当购买额不超过给定值 ui 时,交易费按购买 ui 计 算。另外,假定同期银行存款利率是 r0 ,既无交易费又无风险。 r0 =5%) (
已知 n=4 时相关数据如下:

si
S1 S2 S3 S4

ri (%)
28 21 23 25

qi (%)
2.5 1.5 5.5 2.6

pi (%)
1 2 4.5 6.5

ui (元)
103 198 52 40

试给该公司设计一种投资组合方案,即用给定达到资金 M,有选择地购买若干种资产或存银行 生息,使净收益尽可能大,使总体风险尽可能小。

二、基本假设和符号规定
基本假设: 1. 投资数额 M 相当大,为了便于计算,假设 M=1; 2.投资越分散,总的风险越小; 3.总体风险用投资项目s i 中最大的一个风险来度量; 4.n 种资产 Si 之间是相互独立的; 5.在投资的这一时期内, ri,pi,qi,r0 为定值,不受意外因素影响; 6.净收益和总体风险只受 ri,pi,qi 影响,不受其他因素干扰。

符号规定: Si ——第 i 种投资项目,如股票,债券 ri,pi,qi ----分别为 Si 的平均收益率, 交易费率,风险损失率 ui xi Q ----Si 的交易定额
-------

r0

-------

同期银行利率

投资项目 Si 的资金 ----总体收益

a -----投资风险度 Δ Q ----总体收益的增量

三、模型的建立与分析

1.总体风险用所投资的Si中最大的一个风险来衡量,即max{ qixi|i=1,2,…n}

2.购买 Si 所付交易费是一个分段函数,即 pixi xi>ui 交易费 = piui xi≤ui 而题目所给定的定值 ui(单位:元)相对总投资 M 很小, piui 更小, 可以忽略不计,这样购买 Si 的净收益为(r i-pi)xi
3.要使净收益尽可能大,总体风险尽可能小,这是一个多目标规划模型: 目标函数 MAX
n

? (r ? p ) x
i i i ?0
i i

n

i

MINmax{ q ix i} 约束条件

( ?1? p)x =M
i?0

xi≥0
4. 模型简化:

i=0,1,…n

a. 在实际投资中,投资者承受风险的程度不一样,若给定风险一个界限 a,使最大的一个 风险 q ix i/M≤a,可找到相应的投资方案。这样把多目标规划变成一个目标的线性规划。 模型 1 固定风险水平,优化收益 目标函数: 约束条件: Q=MAX

? (r ? p ) x
i ?1 i i

n ?1

i

qi xi M

≤a
i i

?(1 ? p )x

? M , xi≥ 0

i=0,1,…n

b.若投资者希望总盈利至少达到水平 k 以上,在风险最小的情况下寻找相应的投资组合。 模型 2 固定盈利水平,极小化风险 目标函数: R= min{max{ q ix i}} 约束条件:

? (r
i ? 0

n

i

? p i ) x i ≥k,
i i

?(1? p )x

? M , xi≥ 0

i=0,1,…n

c.投资者在权衡资产风险和预期收益两方面时,希望选择一个令自己满意的投资组合。 因此对风险、收益赋予权重 s(0<s≤1),s 称为投资偏好系数. 模型 3 目标函数:min s{max{q ix i}} -(1-s)
n

? (r ? p ) x
n i i i ?0

i

约束条件

?(1?p )x =M, x ≥0
i i i?0
i

i=0,1,2,…n

四、模型1的求解

模型 1 为: minf = (-0.05, -0.27, -0.19, -0.185, -0.185) (x0 x1 x2 x3 x 4 ) T x0 + 1.01x1 + 1.02x2 +1.045x3 +1.065x4 =1 s.t. 0.025x1 ≤a 0.015x2 ≤a 0.055x3 ≤a 0.026x4≤a xi ≥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; To Matlab(xxgh5) end xlabel('a'),ylabel('Q')

计算结果:
a = 0.0030 a = 0.0060 a = 0.0080 a = 0.0100 a = 0.0200 a = 0.0400 x = 0.4949 x=0 x = 0.0000 x=0 x=0 x = 0.0000 0.1200 0.2400 0.3200 0.4000 0.8000 0.9901 0.2000 0.4000 0.5333 0.5843 0.1882 0.0000 0.0545 0.1091 0.1271 0 0 0 0.1154 0.2212 0.0000 0 0 0 Q = 0.1266 Q = 0.2019 Q = 0.2112 Q =0.2190 Q =0.2518 Q =0.2673

五、 结果分析 1.风险大,收益也大。

2.当投资越分散时,投资者承担的风险越小,这与题意一致。即: 冒险的投资者会出现集中投资的情况,保守的投资者则尽量分散投资。
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

返 回

实验作业
某厂生产甲乙两种口味的饮料,每百箱甲饮料需用原料6千克, 工人10名,可获利10万元;每百箱乙饮料需用原料5千克,工人20 名,可获利9万元.今工厂共有原料60千克,工人150名,又由于其 他条件所限甲饮料产量不超过8百箱.问如何安排生产计划,即 两种饮料各生产多少使获利最大.进一步讨论: 1)若投资0.8万元可增加原料1千克,问应否作这项投资. 2)若每百箱甲饮料获利可增加1万元,问应否改变生产计划.

返 回


更多相关文档:

数学建模线性规划和整数规划实验

数学建模线性规划和整数规划实验 1、加工奶制品的生产计划 2、下料问题 3、投资问题 4、工程进度问题 5、生产计划与库存问题 6、志愿者排班问题 7、最小覆盖问题...

数学建模作业实验3线性规划实验

数学建模作业 (实验 3 线性规划实验) 基本实验 1.生产计划安排某公司使用三种操作装配三种玩具——玩具火车、 玩具卡车和玩具汽车。 对于三种操作 可用时间限制分别...

数学建模实验线性规划模型实验实验报告

数学建模实验线性规划模型实验实验报告 隐藏>> 线性规划模型实验一、实验目的:掌握线性规划模型的建立与 Lingo 求解方法。 二、实验题目:某工厂计划生产甲、乙两种产...

数学建模实验报告3 线性规划与整数规划、

数学建模与实验课程实验名称 三、线性规划与整数规划 姓名 班级 实验地点 学号 实验报告日期 2014-10-28 成绩 【实验目的及意义】 [1] 学习最优化技术和基本原理...

《数学建模与数学实验》实验报告实验五:线性规划模型实验

数学建模与数学实验》实验报告 实验五:线性规划模型实验专业、 班级 课程编号 实验(上机)地点 任课教师 李锋 数学 09B 学号 实验类型 同析楼 4 栋 404 094080...

数学建模线性规划

数学建模线性规划_工学_高等教育_教育专区。线性规划 1.简介: 线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是 辅助人们进行...

线性规划在数学建模中的应用

研究背景以及意义 1.1.1 研究背景 1.1.2 研究意义 研究线性规划数学建模中的应用其理论意义主要在于利用数学建模的手 段, 为线性规划更好的应用于显示生活中...

重庆大学_数学实验_4线性规划(数学建模)

重庆大学_数学实验_4线性规划(数学建模)_职业规划_求职/职场_实用文档。重庆大学学生实验报告 实验课程名称 开课实验室 学姓院名 2012 至 材料学院 聂志宇 2013...

线性规划问题求解----数学建模实验报告

报告 1、 实验目的:(1)学会用 matlab 软件解决线性规划问题的最优值求解问题。 (2) 学会将实际问题归结为线性规划问题用 MATLAB 软件建立恰 当的数学模型来...

对数学建模线性规划的认识

线性规划和概率论的应用论文 线性规划和概率论的应用论文 郑州师范学院 10 级数学数学与应用数学二班 李玲玲 15036131624 1 线性规划及概率统计的应用体会 ...
更多相关标签:
数学建模线性规划例题 | 数学建模非线性规划 | 数学建模线性规划问题 | 数学建模线性规划 | 数学建模线性规划论文 | 数学建模线性规划模型 | 数学建模线性规划ppt | 线性规划建模 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com