文档介绍：该【数学建模教材(第四章) 】是由【guoxiachuanyue014】上传分享，文档一共【58】页，该文档可以免费在线阅读，需要了解更多关于【数学建模教材(第四章) 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。12
1
第4章数学规划模型
本章研究数学规划模型,其中包括:线性规划、整数规划、非线性规划、多目标规划与动态规划等内容.
线性规划模型
线性规划是运筹学的一个重要分支,随着计算机技术的发展,线性规划不仅在理论上已趋向成熟,。数学软件对线性规划模型进行求解.
在生产管理和经营活动中经常提出一类问题,即如何合理地利用有限的人力、物力、财力等资源,以便得到最好的经济效果.
引例1普通生产计划安排问题
某工厂在计划期内要安排生产I、II两种产品,已知生产单位产品所需的设备台时及A、B两种原材料的消耗,如表4-,每生产一件产品II可获利3兀,问应该如何安排计划使该工厂获利最多
表普通生产计划安排问题
I
II
设备
1
2
8台时
原材料A
4
0
16kg
原材料B
0
4
12kg
利润
2
3
引例2奶制品的生产计划问题
一奶品加工厂用牛奶生产A、B两种奶制品,1桶牛奶可以在甲类设备上用12小时加工成3公斤A,或者在乙类设备上用8小时加工成4公斤B,根据市场需求,生产的A、B全部能售出,且每公斤A获利24元,,每天正式工人总的劳动时间为480小时,并且甲类设备每天最多能加工100公斤A,,使每天获利最大,并进一步讨论以下3个附加问题:
⑴若用35元可以买到1桶牛奶,应否做这项投资若投资,每天最多购买多少桶牛奶
⑵若可以聘用临时工人以增加劳动时间,付给临时工人的工资最多是每小时几元
⑶由于市场需求变化,每公斤A的获利增加到30元,应否改变生产计划
对于引例1,可以设x、y分别表示在计划期内产品I、
2
13
利润,这时,z=2x+3y・因为设备的有效台时为8,因此应有限制条件:x+2y<8;同理考虑原材料的不同限制,可得如下限制条件:4x<16,4y<12•综上所述,该计划问题可用数学模型表示为:
目标函数:maxz=2x+3y
”x+2y<8
约束条件:J4x<16
y<12
x>0,y>0
对于引例2,可以设每天用x桶牛奶生产A,用x桶牛奶生产B•类似引例1可
12
得奶制品生产计划问题的数学模型:
目标函数:maxz=72x+64x
12
x+x<50
约束条件:
12
v12x+8x<480
12
x<100
1
x>0,x>0
12
从以上两例可以看出,他们都属于同一类优化问题,他们的共同特征:
⑴每一个问题都用一组决策变量(x,x,,x)表示某一方案;这组决策变量的值
12n就代表一个具体方案,一般这些变量取值都是非负的;一⑵存在一定的约束条件,这些约束条件可以用一组线性等式或线性不等式来表示;...
⑶都有一个要求达到的目标,它可用决策变量的线性函数来表示,这个函数称为目标函数・
满足以上三个条件的数学模型称为线性规划数学模型・其一般形式为:
目标函数:max(min)z=cx+cx++cx
1122nn
ax<(=,>)b
1nn1
ax<•(=,>)b
2nn2
ax+ax+
111122约束条件:Ja21x1+a22x2+
ax+ax+
m11m22
ax<(=,>)b
mnnm
12
13
x>0,x.>.0,….x..>0..
12n
12
13
使用Lingo数学软件对引例1进行求解,编写程序如下:
max=2*x+3*y;
x+2*y<8;
4*x<16;
4*y<12;
end
求解结果为:目标函数的最大值z=14,即可获得最大利润14元;最优生产计划方案是:生产产品14件,生产产品112件.
使用Lingo数学软件对引例2进行求解,编写程序如下:
max=72*x1+64*x2;
x1+x2<50;
12*x1+8*x2<480;
3*x1<100;
end
求解结果为:每天用20桶牛奶生产A,用30桶牛奶生产B,:
⑴针对附加问题1,可假设应投资购买x桶牛奶,目标函数应修改为:
maxz=72x+64x一35*x
12
关于牛奶的约束条件也应作相应的修改:
x+x<50+x
12
通过编程求解得:最大利润增加到3490元,因此,应作该项投资,每天最多购买10桶牛奶.
⑵针对附加问题2,首先将劳动时间480小时增加1个小时,对原问题进行求解,可得最大利润由3360元增加到3362元,,若可以聘用临时工人以增加劳动时间,,若还想知道以低于每小时2元的价格增加劳动时间,最多可购买多少劳动时间可以对目标函数以及关于劳动时间的约束条件作类似的修改,,若以每小时元的价格聘用临时工人,最多可购买小时.
⑶针对附加问题3,:
maxz=90x+64x,约束条件不变•通过求解可得:最大利润有所增加,由原来的12
3360元增加到3720元,但生产计划没有改变,仍然是每天用20桶牛奶生产A,用30桶牛奶生产B•
例1一个家庭有625英亩的土地可以用来种植农作物,这个家庭考虑种植的农作物有玉米、小麦和燕麦,预计可以有1000英亩-英尺的灌溉用水,农场工人每周可以投入的工作时间为300小时,其他的数据在表4-2中给出,为能够获得最大收益,每种作物应该种植多少
6
5
表农场问题的有关数据
玉米
小麦
燕麦
现有量
灌溉用水(英亩-英尺)
1000
劳力(人-小时/周)
300
收益(美元)
400
200
250
解设应种植玉米x英亩,:
123
目标函数:maxz=400x+200x+250x
123
3x+x+<1000
约束条件:++<300
123
x+x+x<625
123
x>0,x>0,x>0
123
使用Lingo数学软件进行求解,编写程序如下:
max=400*x1+200*x2+250*x3;x1+x2+x3<625;
*x1+*x2+*x3<300;3*x1+x2+*x3<1000;
end
程序运行结果为:,,获最大收益162500美元.
例2某市有甲、乙、丙、丁四个居民区,自来水由A、B、,70,10,10千吨,但由于水源紧张,三个水库每天最多只能供应50,60,,自来水公式从各水库向各地区送水所需付出的引水管理费不同(见表4-3,其中C水库与丁地区之间没有输水管道),其它管理费用都是450元/,各区用户按照统一标准900元/,四个区都向公司申请了额外用水量,分别为每天50,70,20,,才能获利最多
为了增加供水量,自来水公司正在考虑进行水库改造,使三个水库每天的最大供水量都提高一倍,问那时供水方案应如何改变公司利润可增加多少
表引水管理费
引水管理费(元/千吨)
甲
乙
丙
丁
A
160
130
220
170
B
140
130
190
150
C
190
200
230
/
解决策变量应为A、B、C三个水库(i=1,2,3)分别向甲、乙、丙、丁四个区
(j=1,2,3,4),由于C水库与丁区之间ij
没有输水管道,即x二0,:
34
目标函数:maxz二(450-160)x+(450-130)x+(450-220)x+(450-170)x
11121314
6
13
+(450-140)x+(450-130)x+(450-190)x+(450-150)x
21222324
+(450-190)x+(450-200)x+(450-230)x
313233
约束条件:水库供应量限制可以表示为:
x+x+x+x<50
11121314
x+x+x+x<60
21222324
x+x+x<50
313233
各区基本用水量与额外用水量限制为:
30<x+x+x<80
112131
70<x+x+x<140
112131
10<x+x+x<30
112131
10<x+x+x<50
112131
x..>0,i二1,2,3;j二1,2,3,4
ij
使用Lingo数学软件进行求解,编写程序如下:max=(450-160)*x11+(450-130)*x12+(450-220)*x13+(450-170)*x14+(450-140)*x21+(450-130)*x22+(450-190)*x23+(450-150)*x24+(450-190)*x31+(450-200)*x32+(450-230)*x33;
x11+x12+x13+x14<50;
x21+x22+x23+x24<60;
x31+x32+x33<50;
x11+x21+x31<80;
x11+x21+x31>30;x12+x22+x32<140;
x12+x22+x32>70;
x13+x23+x33<30;
x13+x23+x33>10;
x14+x24<50;
x14+x24>10;
end
程序运行结果为:A水库向乙区供水50千吨;B水库向乙、丁区分别供水50,10千吨;C水库向甲、丙分别供水40,.
对于本例来说,无论是目标函数还是约束条件都显得比较麻烦,,.
为此,需假定C水库向丁地区的引入管理费用为无穷大,本例可用1000元/千吨来代替.
使用Lingo数学软件中的高级编程技巧进行求解,编写程序如下:
model:sets:
sk/1..3/:g;
dq/1..4/:sl1,sl2;
link(sk,dq):c,x;
endsets
data:
8
7
c=160130220170
140130190150
1902002301000;
g=506050;
sl1=30701010;
sl2=801403050;
enddata
[obj]max=***@sum(link(i,j):x(i,j)*(450-c(i,j)));
***@for(sk(i):***@sum(dq(j):x(i,j))<g(i));
***@for(dq(j):***@sum(sk(i):x(i,j))>sl1(j));
***@for(dq(j):***@sum(sk(i):x(i,j))<sl2(j));
end
,只需将数据段中的供水量修改成:g=100120100;或者对第一个约束条件作简单修改,在小于号后面将供水量扩大2倍,:A水库向乙区供水100千吨;B水库向甲、乙、丁区分别供水30,40,50千吨;C水库向甲、丙分别供水50,.
评注:本例考虑的是将某种物资从若干供应点运往一些需求点,在供需量约束条件下使总费用最少,.
注意:本例目标函数采用的是最大利润,,成本最小,,最小成本与最大利润是等价的;若总收入随决策变量的改变而变化时,,而非最小成本.
非线性规划
在工程技术、经济管理、交通运输和日常生活等诸多领域中,很多实际问题可以归结为线性规划问题,其目标函数和约束条件都是自变量(决策变量)的一次函数(线性函数).但是,还有另外一些问题,其目标函数和(或),,。数学软件的开发与应用,对非线性规划模型的求解提供了很大的帮助.
某公司将4种不同含硫量的液体原料(分别记为甲、乙、丙、丁)混合生产两种产品(分别记为A、B).按照生产工艺的要求,原料甲、乙、丁必须首先倒入混合池中混合,、乙、丙、丁的含硫量分别是3,1,2,1(%),进货价格分别为6,16,10,15(千元/吨);产品A、B的含硫量分别不能超过,(%),售价分别为9,15(千元/吨).根据市场信息,原料甲、乙、丙的供应没有限制,原料丁的供应量最多为50吨;产品A、B的市场需求量分别为
8
9
100、200(吨),问应如何安排生产
某乡镇由12个主要的自然村组成,每个自然村的位置(用平面坐标x,y表示,距离单位:km)和自然村的人口数(R)如表4-4所示.
试根据需要解决如下问题:
⑴目前准备在该乡镇建一个服务网点为各村提供各种服务,那么服务网点应该建在何处
⑵假设各村人口增长了一倍,需要建两个服务网点,确定其位置.
表最佳选址问题
0
1
2
3
4
5
6
7
8
9
10
11
12
X
0
y
0
R
600
1000
800
1400
1200
700
600
800
1000
1200
1000
1100
引例1液体原料混合问题的模型建立
设y,z分别是产品A中来自混合池和原料丙的吨数;y,z分别是产品B中来自
1122混合池和原料丙的吨数;混合池中原料甲、乙、丁所占的比例分别为x,x,x,优化
124目标是总利润(z)最大.
目标函数为:
maxz=9(y+z)+15(y+z)一10(z+z)一(6x+16x+15x)(y+y)
**********
=(9一6x一16x一15x)y+(15一6x一16x一15x)y+(9一10)z+(15一10)z
1241124212
约束条件为:
⑴原料最大供应限制:x(y+y)<50
412
⑵产品最大需求限制:y+z<100,y+z<200
1122
⑶产品最大含硫量限制:(3x1+x2+叮y1+2“<,(3x1+x2+x4)y2+2z2<
y+zy+z
1122
⑷其它限制:x+x+x=1,x,x,x,y,z,y,z>0
1241241122
12
9
引例2最佳选址问题的模型建立
(1)模型一的建立
设服务网点的坐标为:(a,b);自然村的位置坐标:(x,y),i=1,2,,12;自然村
ii
的人口数:r,i=1,2,,12,服务网点到各自然村的距离为:d,i=1,2,,
ii
村的人口数作为距离的权重,优化的目标为总距离最小.…
目标函数为:minz=芳rd
iii=1
约束条件为:d=x-a)2+(y-b)2,i=1,2,,12
i、ii
(2)模型二的建立
设两个服务网点的坐标分别为:(a,b.),i=1,2;自然村的位置坐标:(x,y),iijj
j=1,2,,12;自然村的人口数:r,i=1,2,,12;服务网点i到自然村j的距离为:
j
d,i=1,2;j=1,2,,12;服务网点i对自然村j服务的人口数为:c,i=1,2;
ijij
•••
•••
j=1,2,,12;k(i),i=1,2表示第i个服务网点服务的人口数占人口总数的比例•以服
务网点对自然村服务的人口数作为距离的权重,优化的目标为总距离最小.
目标函数为:minz=歧2c(i,j)-d(i,j)
j=1i=1
d(i,j)=J(x-a)2+(y-b)2
/iji
国c(i,j)=e(i)
约束条件:
j=1
e(i)=k(i)艺2r(j)
10
13
j=1
工c(i,j)>2r(j)
i=1
从以上两个引例可以总结出非线性规划的一般模型:
目标函数:max(min)z=f(x,x,,x)
12n
约束条件:
h(x,x,i12
12
,x)=0,i=1,2,,m
n
,x)>0,…丿'=1,2,,l
n
目标函数为一般非线性函数,约束条件为一般非线性等式或非线性不等式•一般来说,目标函数与约束条件中只要有非线性项存在,即为非线性规划•特别地,若某非线性规划的目标函数为决策变量的二次函数,•约束条件又全是线性的,就称这种规划为二次规划.
12
13
使用Lingo数学软件进行求解,编写程序如下:max=(9-6*x1-16*x2-15*x4)*y1+(15-6*x1-16*x2-15*x4)*y2+(1-10)*z1+(15-10)*z2;x4*(y1+y2)<50;
y1+z1<100;y2+z2<200;
((3*x1+x2+x4)*y1+2*z1)/(y1+z1)<;((3*x1+x2+x4)*y2+2*z2)/(y2+z2)<;
x1+x2+x4=1;
end
用Lingo求解时,如果怀疑不是全局最优解,用"LING0|0PTI0NS"菜单命令启动"GlobalSolver"选项卡上的"UseGlobalSolver"选项,然后求解,可以得到全局最优解如下:,y二z二100,其余为0;
2422产品最大含硫量限制的约束条件作简单修改后,也可直接进行求解,:max=(9-6*x1-16*x2-15*x4)*y1+(15-6*x1-16*x2-15*x4)*y2+(1-10)*z1+(15-10)*z2;x4*(y1+y2)<50;
y1+z1<100;y2+z2<200;!((3*x1+x2+x4)*y1+2*z1)/(y1+z1)<;
(3*x1+x2+**z1<0;
!((3*x1+x2+x4)*y2+2*z2)/(y2+z2)<;
(3*x1+x2+*y2+*z2<0;
x1+x2+x4=1;
end
针对模型一,使用Lingo数学软件进行求解,编写程序如下:model:
title:最佳选址(一);
sets:
point/1..12/:x,y,r,dis;
endsets
data:
X=0;
Y=0;
r=6001000800140012007006008001000120010001100;
enddata
***@for(point(i):dis(i)=((x(i)-a厂2+(y(i)-b厂2厂(1/2));min=***@sum(point:dis*r);
end
用Lingo求解得到结果为:a=,b=.
针对模型二,若取k(1)=k(2)=,使用Lingo数学软件进行求解,编写程序如
下:
model:
title:最佳选址(一);
sets:
point/1..12/:x,y,r;
weizhi/1..2/:a,b,e;
link(weizhi,point):c;
endsets
12
13
data:
X=0;
Y=0;
r=6001000800140012007006008001000120010001100;enddata
submodelxuanzhi:
min=***@sum(link(i,j):c(i,j)*((a(i)—x(j)厂2+(b(i)—y(j)厂2厂(1/2));***@for(weizhi(i):***@sum(point(j):c(i,j))=e(i));***@for(point(j):***@sum(weizhi(i):c(i,j)))>2*r(j));
endsubmodel
calc:
e(1)=***@sum(point:r);
e(2)=***@sum(point:r);***@solve(xuanzhi);
***@ole('','最佳位置a')=a;
***@ole('','最佳位置b')=b;
***@ole('','最优方案')二c;
Endcalc
End
用Lingo求解得到结果为:两个服务网点的位置坐标为:(,);(,)
各服务网点服务人数对照表见表4-5.
表服务人数对照表(限制服务网点的服务人数相同)
1234
56789101112人口总数(千人)
网点1
00
02
0
20
网点2
20
0000
0
针对模型二,若不考虑服务网点服务人数的限制,使用Lingo数学软件进行求解,编写程序如下:
model:
title:最佳选址(一);
sets:
point/1..12/:x,y,r;weizhi/1..2/:a,b,e;link(weizhi,point):c;
endsets
data:
X=0;
Y=0;
r=6001000800140012007006008001000120010001100;enddata
submodelxuanzhi:
min=***@sum(link(i,j):c(i,j)*((a(i)—x(j)厂2+(b(i)—y(j)厂2厂(1/2));!***@for(weizhi(i):***@sum(point(j):c(i,j))=e(i));
***@for(point(j):***@sum(weizhi(i):c(i,j))>2*r(j));endsubmodel
calc:
!e(1)=***@sum(point:r);
!e(2)=***@sum(point:r);***@solve(xuanzhi);
***@ole('','最佳位置a')=a;
***@ole('','最佳位置b')=b;
12
13