文档库 最新最全的文档下载
当前位置:文档库 › 多目标线性规划在小流域综合治理规划中的应用研究——以四川省石柱县密麻沟小流域为例

多目标线性规划在小流域综合治理规划中的应用研究——以四川省石柱县密麻沟小流域为例

多目标线性规划在小流域综合治理规划中的应用研究——以四川省石柱县密麻沟小流域为例
多目标线性规划在小流域综合治理规划中的应用研究——以四川省石柱县密麻沟小流域为例

第14卷第3期中国生态农业学报Vol.14 No.3 2006年7月Chinese Journal of Eco2Agriculture J uly, 2006多目标线性规划在小流域综合治理规划中的应用研究3

———以四川省石柱县密麻沟小流域为例

缪驰远 何丙辉33陈晓燕 林尤莲

(西南大学资源环境学院 重庆 400716)(重庆市石柱县水利局 石柱 409100)

摘 要 本研究以四川省石柱县密麻沟小流域为研究对象,通过分别建立4个子目标函数,利用专家权重法与方向性系数将多个子目标函数整合为1个目标函数,并应用EXCEL软件对多目标函数的规划模型进行线性求解。

小流域经治理规划后土地利用趋于合理,生态平衡趋于协调,农、林、牧3业用地比例由原23132∶74120∶2148调整为24123∶67167∶811,流域年土壤侵蚀模数由原1823t/km2降为162814t/km2。

关键词 线性规划 综合治理 水土保持

Study on the multiple objective linear planning applied in comprehensive control of sm all w atershed—a case study from Mim agou sm all w atershed in Shizhu County,Sichu an Province.MIAO Chi2Yuan,HE Bing2Hui,CHEN Xiao2Y an(Col2 lege of Resources and Environment,S outhwest University,Chongqing400716,China),L IN Y ou2Lian(Shizhu Water Resources Bureau,Chongqing City,Shizhu409100,China),CJ EA,2006,14(3):223~227

Abstract Based on the Mimagou small watershed in Shizhu County,Sichuan Province,through building the four objec2 tive sub2functions,the multiple objective functions were integrated as an objective function using the expertπs weight and directional coefficient and applying EXCEL software,the optimal solution of the multiple objective function planning mod2 el was determined.From the result,the land use of watershed becomes more reasonable,the ecology balance tends to har2 monious,the proportion of agriculture2forestry2stock is adjusted from23132∶74120∶2148to24123∶67167∶811,the soil erosion modulus in a year falls from the original1823t/km2to162814t/km2.

K ey w ords Linear planning,Comprehensive control,Water and soil conservation

(Received Nov.26,2004;revised Feb.5,2005)

小流域线性规划就是将规划对象作为1个系统,并认为系统中所有输入、输出关系为线性关系。根据规划对象的自然和社会经济特点,建立数学模型,求得最优解[1]。多目标线性规划由单目标线性规划发展而来,它同时考虑数个目标函数,在确定出各目标重要程度的权重以后,可求得同时兼顾各目标利益时的合理解。与单目标规划相比,多目标规划方法能充分体现小流域生态经济系统功能目标的多重性[2]。本研究以四川省石柱县密麻沟小流域为例,将经济效益、生态效益等分别列为不同目标函数,建立系统数学模型的优化治理模式,对多目标线性规划进行探讨。

1 治理区概况与治理方法

密麻沟小流域位于四川省石柱县黄水镇,面积34139km2,海拔高度1135~1621m,地层出露为侏罗系沙溪庙组紫色岩、泥岩。年均气温1117℃,年均降雨量137216mm,森林覆盖率47172%。据2003年底统计,流域内总人口1349人,其中农业人口1320人。农林牧3大产业年收入依次为166万元、7万元和26万元,分别占流域总收入的78168%、3131%和12132%,粮食总产55万kg,平均单产90415kg/hm2,农业人均产粮416167kg。土地利用分为农耕地、林地、荒山荒坡、水域面积和非生产用地5大类,分别占流域总面积的18118%、57187%、13166%、1186%和8143%,流域土壤年均侵蚀模数为1823t/km2,年侵蚀总量5124万t。

规划目标。流域生态经济系统结构设计分生态效益、经济效益和社会效益3个目标。因社会效益无法直接计算[3],本流域治理规划目标以生态效益和经济效益为主。生态效益目标为各项措施减沙量最大,水

3国家“十五”科技攻关重大专项“区域生态环境安全和生态经济系统重建关键技术研究与示范”(2001BA04A)资助

33通讯作者

收稿日期:2004211226 改回日期:2005202205

土流失最少;实现土地肥力的平衡,保持土地较高生产力[4]。经济效益目标为纯收入最大,投资最省。系统线性规划模型的建立。确定总体规划后,依据各项措施的单项规划和总体规划的原则、构想及流域自然资源现状,调整了40个约束条件,分别建立小流域5年农、林、牧、渔各业发展线性规划的单目标数学模型,把这些单目标函数作为子目标函数与相应的权重结合,建立1个新目标函数,即为所求的多目标函数。求一组变量X j (j =1,2,3,…,n )的值,满足约束条件[5]:

∑40j =1

a

ij X j

≤b j (≥b i )

X j ≥0

f m (X )=

∑40

j =1

c

mj X

j

使综合目标函数F (X )=

∑p m λm f

m

(X )达到最优。式中,X j 为决策变量,a ij 为决策变量系数,b i 为资源

限制量,c mj 为价值系数,F (X )为综合目标函数,f m (X )为单目标函数,λm 为决策目标相应的权系数,p m 为单目标函数方向系数。多目标模型线性规划求解比单目标更复杂,如徐新华[3]先是分别求出所有单目标函

数变量的最优解,再根据各单目标函数的权重与各单变量的乘积之和作为变量最终解,即X 1终=

∑n

i =1

λi

X i

1

(λi 为第i 个单目标函数权重,X i 1为第i 单目标函数第一个变量的解)。

笔者认为该方法欠说服性,因为规表1 模型决策变量说明

Tab.1 The model decision variable declaration

变量名

Name

变量说明

Variable declaration 变量名

Name

变量说明

Variable declaration X 11级地种黄连公顷数

X 22级地种黄连公顷数X 33级地修梯田种黄连公顷数X 44级地修梯田种黄连公顷数X 51级地种玉米公顷数X 62级地加修地埂生物带种玉米公顷数X 73级地修坡式梯田种玉米公顷数X 84级地修梯田种玉米公顷数X 91级地种洋芋公顷数

X 102级地加修地埂生物带种洋芋公顷数X 113级地加修坡式梯田种洋芋公顷数X 124级地加修坡式过渡梯田种洋芋公顷数

X 133级地种小杂粮公顷数X 144级地种小杂粮公顷数X 151级地种蔬菜公顷数X 162级地种油料作物公顷数

X 173级地修坡式梯田种油料作物公顷数X 184级地修坡式梯田种油料作物公顷数

X 192级地种天麻公顷数

X 20

3级地加修地埂生物带种天麻公顷数

X 213级地人工牧草公顷数X 224级地人工牧草公顷数X 235级地人工牧草公顷数X 242级地薪炭林公顷数X 255级地薪炭林公顷数X 266级地薪炭林公顷数X 273级地混交林公顷数X 284级地混交林公顷数X 295级地混交林公顷数X 303级地用材林公顷数X 314级地用材林公顷数X 325级地防护林公顷数X 336级地防护林公顷数X 342级地粮草作公顷数X 353级地粮草作公顷数

X 36大牲畜头数X 37奶牛发展头数X 38猪发展头数X 39鸡发展头数X 40

鸭鹅发展头数

划求解只能是针对单目标的,考虑多个因素时应以1种合理的方程转化为1个目标值,然后按约束条件对目标求极值。笔者构造了1个多目标模型,通过将多个单目标函数与各自的权重整合成1个函数F (X )求解,由于单目标函数所求的方向性不同(有的为求最大值,有的为求最小值),故又加入了1个单目标函数的方向系数p ,当求最大值时,p 为“1”,当求最小值时,p 为“-1”。在小流域土地质量分类及适应性评价研究基础上,按照选择影响大的因素设置变量的原则设置变量(见表1)。根据小流域社会经济状况及规划后的生态和经济效益目标,并参考当地近期规划,确定4类约束方程。

第一类:土地约束

一级地公顷数:

X 1+X 5+X 9+X 15=19912

(1) 二级地公顷数:

X 2+X 6+X 10+X 19+X 24+X 34=117

(2) 三级地公顷数:

X 3+X 7+X 11+X 13+X 20+X 21+X 27+X 30+X 35=21516

(3) 四级地公顷数:

X 4+X 8+X 12+X 14+X 18+X 22+X 28+X 31=45618

(4) 五级地公顷数:

X 23+X 25+X 29+X 32=136117

(5)

224 中国生态农业学报第14卷

六级地公顷数:

X 26+X 33=126123

(6)

第二类:生产发展约束

保持蔬菜自给,人均66167m 2(人口按015%增长,到2009年为1865人):

X 15=66167×1865/10000(7) 为满足粮食需求,人匀粮田不低于3333135m 2:

X 1+X 2+X 3+X 4+X 5+X 6+X 7+X 8+X 9+X 10+X 11+X 12+X 13+X 14≥621167

(8) 草场不少于133133hm 2:

X 21+X 22+X 23≥133133

(9) 为满足农村能源需要,薪炭林应不少于66167hm 2:

X 24+X 25+X 26≥66167

(10) 人均产粮不少于750kg :

9000X 5+8250X 6+7500X 7+7500X 8+4500X 9+3750X 10+3750X 11+

(11)

3000X 12+3000X 13+1500X 14+9000X 34+7500X 35≥2797500

洋芋总产量不低于186500kg :

4500X 9+3750X 10+3750X 11+3000X 12≥186500

(12) 流域每年可投基建工118800个:

15X 2+30X 3+450X 4+15X 6+30X 7+450X 8+15X 10+30X 11+30X 12+30X 13+

(13)

30X 14+30X 16+30X 17+30X 18+30X 19+30X 20+30X 21+30X 22+30X 23+15X 24+15X 25+15X 26+15X 27+15X 28+15X 29+15X 30+15X 31+15X 32+15X 33≤118800

流域劳力每年可投生产用工158400个:

180X 1+180X 2+180X 3+180X 4+120X 5+120X 6+120X 7+120X 8+60X 9+

(14)

60X 10+60X 11+60X 12+90X 13+90X 14+225X 15+90X 16+90X 17+90X 18+135X 19+135X 20+30X 21+30X 22+30X 23+105X 24+105X 25+105X 26+135X 27+135X 28+135X 29+135X 30+135X 31+135X 32+135X 33+120X 34+120X 35+18X 36+

20X 37+12X 38+5X 39+5X 40≤158400

第三类:平衡约束

饲草平衡约束:

2400X 1+2100X 2+1800X 3+1800X 4+3000X 5+2700X 6+2400X 7+2400X 8+2400X 9+

(15)

1800X 10+1800X 11+1500X 12+4500X 13+3000X 14+7500X 21+15000X 22+15000X 23+9750X 27+8670X 28+8670X 29+2250X 34+1500X 35-4400X 36-5110X 37-1825X 38≥0

到2009年群众需薪炭99311215kg :

4950X 1+4290X 2+3630X 3+1650X 4+7500X 5+6000X 6+4500X 7+4500X 8+

(16)

4800X 9+4320X 10+4080X 11+3360X 12+4080X 13+2400X 14+9000X 24+8100X 25+

8100X 26+2360X 30+2250X 31+2138X 32+2040X 33≥9931115

饲料平衡:

7500X 1+6750X 2+6000X 3+6000X 4+9000X 5+8250X 6+7500X 7+7500X 8+

(17)

4500X 9+3750X 10+3750X 11+3000X 12+3000X 13+2250X 14+9000X 34+7500X 35-800X 36-1095X 37-500X 38-108X 39-110X 40≥0

第四类:畜牧业约束

大牲畜上限250头:

X 36≤250

(18) 奶牛不超过350头:

X 37≤350

(19)

第3期缪驰远等:多目标线性规划在小流域综合治理规划中的应用研究225

 

猪不超过300头:

X 38≤300

(20) 鸡不多于1500只:

X 39≤1500

(21) 鸭鹅不多于5000只:

X 40≤5000

(22) 分别确定纯收入、水土流失、基建投资和粮食产量为子目标函数,其纯收入方程为:

f 1(X )=12600X 1+9600X 2+9600X 3+8100X 4+1125X 5+114715X 6+2250X 7+

(23)

975X 9+723175X 10+723175X 11+723175X 12+1200X 13+1125X 14+1800X 15+

975X 16+723175X 17+723175X 18+1425X 19+1350X 20+60X 24+150X 25+150X 26+150X 27+150X 28+150X 29+855X 30+750X 31+750X 32+69715X 33+1200X 34+1200X 35+140X 36+660X 37+22312X 38+15X 39+21X 40

水土流失量为:

f 2(X )=5X 1+20X 2+60X 3+100X 4+3X 5+1212X 6+3616X 7+61X 8+415X 9+18X 10+53X 11+90X 12+(24)

50X 13+80125X 14+5X 15+18X 16+53X 17+90X 18+11X 19+33X 20+217X 21+5X 22+5X 23+121225X 24+15X 25+30X 26+50X 27+80X 28+15X 29+217X 30+415X 31+15X 32+30X 33+11X 34+20X 35

基建投资为:

f 3(X )=6715X 2+120X 3+1185X 4+6715X 6+120X 7+1185X 8+6715X 10+105X 11+

(25)

105X 12+105X 13+105X 14+105X 16+105X 17+105X 18+135X 19+135X 20+150X 21+150X 22+18715X 23+13714X 24+13714X 25+13714X 26+41215X 27+41215X 28+41215X 29+375X 30+375X 31+405X 32+30X 34+30X 35

粮食产量为:

f 4(X )=9000X 5+8250X 6+7500X 7+7500X 8+4500X 9+3750X 10+3750X 11+3000X 12+

(26)

3000X 13+1500X 14+1500X 34+7500X 35

2 结果与分析

211 模型求解

先采用“专家法”,按f 1(X )、f 2(X )、f 3(X )、f 4(X )4个子目标函数的重要程度确定其权重系数λ1、λ2、λ3、λ4,且要求λ1+λ2+λ3+λ4=1,最终确定权重系数结果分别为014、

012、012、012,根据子目标函数极值的方向性,最终确定F (X )=λ1f 1(X )-λ2f 2(X )-λ3f 3(X )+λ4f 4(X ),先将方程(23)、

(24)、(25)、(26)进行整合,得方程:F (X )=5039X 1+382215X 2+3804X 3+2983X 4+224914X 5+2093106X 6+2368168X 7+

(27)125018X 8+128911X 9+102214X 10+1007191X 11+756X 12+1049X 13+712195X 14+719X 15+365X 16+257X 17+25015X 18+54018X 19+50614X 20-30154X 21-31X 22-3815X 23-5193X 24+29152X 25+26152X 26-3215X 27-3815X 28-2515X 29+266146X 30+22411X 31+216X 32+273X 33+77118X 34+1970X 35+56X 36+264X 37+89128X 38+6X 39+814X 40

运用EXCEL 的规划求解功能,分别设定相应目标单元和约束单元,最终求得综合方程F (X )的最优解

即最大值为2193558194,4个子目标函数f 1(X )、f 2(X )、f 3(X )、f 4(X )的值为3214925109、56001124、388258196、4093684129,其中决策变量值见表2。212 规划成果

通过计算获得5年后小流域农、林、牧、渔发展布局(种植业及林草布局产值见表3)农地、林草、牧草和其他面积依次为747187hm 2、208819hm 2、250133hm 2和35119hm 2,分别占流域面积的21175%、60174%、7128%和10123%;畜牧业中牛、猪、鸡、鸭(鹅)和大牧畜数量分别达350头、300只、1321只、152只和250

226 中国生态农业学报第14卷

只,相应净收入为2311万

元、61696万元、119815万

元、3192元和216万元。从

规划结果看,密麻沟小流域

经治理规划后土地利用趋于

合理,农、林、牧3业用地比

例由原23132∶74120∶2148

调整为24123∶67167∶811,养殖业有较大发展,林草覆

盖度调整为68102%。规划

实现后小流域群众人均纯收入1723182元,比规划前提

高923182元;粮食总产达

表2 决策变量取值Tab 12 The value of decision variable 决策变量Decision variable 取值Value 决策变量Decision variable 取值Value 决策变量Decision variable 取值Value 决策变量Decision variable

取值Value X 1149120X 20X 30X 40X 522165X 60X 721516X 8225107X 910192X 100X 110X 12107193X 130X 140X 1512143X 160X 170X 180X 190X 200X 210X 22123173X 23916X 240X 25166167X 26333133X 27200X 28266167X 29133133X 3066167X 31133133X 32126157

X 33595167

X 34117

X 350X 36250

X 37350

X 38300

X 391321X 40152

4093168429t ,人均2195kg ,比规划前提高1465kg ;小流域水土流失得到有效控制,年土壤侵蚀模数由原1823t/km 2降为162814t/km 2。

表3 种植业及林草布局、产值表

Tab 13 The plantation and wood layout and output value

项目

Items

面积/hm 2Area

净收入/元

Net incoming

一级

First class

二级

Second class 三级

Third class 四级

Fourth class 五级

Fifth class 六级

Sixth class 合计

Sum 黄 连1491200000149121879920100玉 米2616502151622510700467132224017105洋 芋10192001071930011818263274141杂 粮01170000117140400100蔬 菜

12143000001214322380100

油 料作 物00000000天 麻00000000

小 计1991211721516333008641772329991146

牧 草00012317391601331330薪炭林000016616733313350075000混交林00200266167133133060090000用材林006616713313300200157000防护林0000126157595167722124510402150小 计

266167

523173

436117

929

2155157

751402150

随着计算机发展和小流域治理的深入,运用多目标规划模型理论解决小流域综合治理规划问题将变得更简便,运用多目标规划模型,不仅可从多目标多层次解决规划方案的优选问题,解决了单目标模型单一性的局限,且该模型能提供多种可行方案,对规划阶段进行多方案评价,最终提高规划成果的精度和可靠性。

参 考 文 献

1 李永贵,田玉柱.混合整数线性规划方法在小流域综合治理规划中的应用.北京水利,1996(4):20~222 翁文斌等.宏观经济水资源规划多目标决策分析方法研究及应用.水利学报,1999(2):1~113 许志云.浅谈小流域水土保持综合治理优化规划问题.水土保持通报,1996,16(1):97~101

4 王印传,张凤荣,孙丹峰.小流域土地利用规划的理论与方法探讨.水土保持学报,2002,16(2):118~1215 齐元栋,曹步山.水土保持规划中新技术的应用.水土保持通报,1996,16(1):119~123

第3期缪驰远等:多目标线性规划在小流域综合治理规划中的应用研究227

 

线性规划模型及其举例

线性规划模型及其举例 摘要:在日常生活中,我们常常对一个问题有诸多解决办法,如何寻找最优方案,成为关键,本文提出了线性规划数学模型及其举例,在一定约束条件下寻求最优解的过程,目的是想说明线性规划模型在生产中的巨大应用。 关键词:资源规划;约束条件;优化模型;最优解 在工农业生产与经营过程中,人们总想用有限的资源投入,获得尽可能多的使用价值或经济利益。如:当任务或目标确定后,如何统筹兼顾,合理安排,用最少的资源(如资金、设备、原材料、人工、时间等)去完成确定的任务或目标;企业在一定的资源条件限制下,如何组织安排生产获得最好的经济效益(如产品量最多,利润最大)。 一.背景介绍 如果产出量与投入量存在(或近似存在)比例关系,则可以写出投入产品的线性函数式: 1()n i ij j j f x a x ==∑,1,2,,,1i m m =+ (1) 若将(1)式中第(1m +)个线性方程作为待求的目标函数,其余m 个线性方程作为资源投入的限制条件(或约束条件),则(1)式变为: OPT. 1()n j j j f x c x ==∑ ST. 1 n ij j j a x =∑> ( =, < )i b , 1,2,,i m = (2) 0,j x ≥ 1,2,,j n =… (2)式特点是有n 个待求的变量j x (1,2,,j n =…);有1个待求的线性目标函数()f x ,有m 个线性约束等式或不等式,其中i b (1,2,,i m =…)为有限的资源投入常量。将客观实际问题经过系统分析后,构建线性规划模型,有决策变量,目标函数和约束条件等构成。 1.决策变量(Decision Variable,DV )在约束条件范围内变化且能影响(或限定)目标函数大小的变量。决策变量表示一种活动,变量的一组数据代表一个解决方案,通常这些变量取非负值。 2.约束条件(Subject To,ST )在资源有限与竞争激烈的环境中进行有目的性的一切活动,都

一个基于妥协解的多目标线性规划分类模型

? 1 2 1 100049 2 100190 (MCLP) MCLP MCLP A compromise-based MCLP classi?cation model Bo Wang1Yong Shi2 (1Graduate University of Chinese Academy of Sciences,Beijing100049) (2CAS Research Center On Ficitious Economy and Data Science,Beijing100190) Abstract Although multiple criteria linear programming can deal with classi?cation problem successfully,an original MCLP model has some dif?culties in choosing parameters.To overcome the problems,compromise-based MCLP model is proposed to offer a good promotion of the original one.In the latter model,there are also two deviations for every single point;that is, interior deviation and exterior deviation.Similar to the original MCLP model,for each point,we want at least one of the deviations to be zero.In addition to modeling work,this paper also gives a proof of the existence of the parameter selection condition. Keywords MCLP Interior deviation Exterior deviation Compromise solution ? ( 70921061( ),90718042( )) BHP Billiton Co.,Australia

考虑如下线性规划问题

考虑如下线性规划问题: Min z=60 x+402x+803x 1 . 3 x+22x+3x≥2 1 4 x+2x+33x≥4 1 2 x+22x+23x≥3 1 x,2x,3x≥0 1 要求:(1)写出其对偶问题; (2)用对偶单纯形法求解原问题; (3)用单纯形法求解其对偶问题; (4)对比(2)与(3)中每步计算得到的结果。 解:(1)设对应于上述约束条件的对偶变量分别为 y,2y,3y;则 1 由原问题和对偶问题,可以直接写出对偶问题为: Max Z’=2 y+42y+33y 1 3 y+42y+23y≤60 1 2 y+2y+23y≤40 1 y+32y+23y≤80 1 y,2y,3y≥0 1 (2)用对偶单纯形法求解原问题(添加松弛变量 x,5x,6x) 4 MaxZ= -60 x-402x-803x+04x+05x+06x 1 -3 x-22x-3x+4x=-2 1 -4 x-2x-33x+5x=-4 1 -2 x-22x-23x+6x=-3 1

1x ,2x ,3x ≥0 建立此问题的初始单纯形表,可见: 从表中可以看到,检验数行对应的对偶问题的解是可行解。因b 列数字为负,故需进行迭代运算。 换出变量的确定,计算min (-2,-4,-3)=-4,故5x 为换出变量。 换入变量的确定,计算得15,40,80/3,故1x 为换入变量。

由表可知,6x 为换出变量。2x 为换入变量。然后继续画单纯形表: 可得4x 为换出变量,3x 为换入变量。继续做单纯形表:

所以此问题的最优解为X=(11/10,19/30,1/10),此对偶问题的最优解为Y=(16,12,30),原问题的最小值为118/3. (3)MaxZ ’=21y +42y +33y +04y +05y +06y 31y +42y +23y +4y =60 21y +2 y +23y +5y =40 1y +32y +23y +6y =80 1y ,2y ,3y ,4y ,5y ,6y ≥0 然后建立单纯形表,可得 i

线性规划的实际应用题解题步骤

线性规划的实际应用题解题步骤 广东 王远征 在近几年的高考试卷中出现了求线性目标函数在线性约束条件下的最大(小)值应用题,本文以高考试题为例,介绍解题的模式和一般步骤. 一、线性规划问题的数学模型如下: 已知???????≤++++≤++++≤++++n m nm n n n m m m m b x a x a x a x a b x a x a x a x a b x a x a x a x a ΛΛΛΛΛ3322112232322212111313212111 (I ) 其中ij a ,i b 都是常数,i x 是非负变量. (n i ,,3,2,1Λ= m j ,,3,2,1Λ=). 求m m x c x c x c x c z ++++=Λ332211 的最大(小)值,其中i c 是常数. 我们将(I )称为线性约束条件,把m m x c x c x c x c z ++++=Λ332211称为目标函数. 二、解题的一般步骤: 1. 建模:在读懂题意的前提下,写出反映实际问题的线性约束条件和目标函数表达式; 2. 作出可行解、可行域:将线性约束条件中的每个不等式当作等式,在平面直角坐标 系中作出相应的直线,并确定原不等式所表示的半平面,然后作出所有半平面的交 集; 3. 作出目标函数的等值线; 4. 求出最优解:在可行域内,平移目标函数的等值线,从图中能判断实际问题的解的 情况,有唯一最优解,或无最优解,或有无穷最优解. 三、典型试题解析 例(07年高考山东)本公司计划2008年在甲、乙两个电视台做总时间不超过300分钟的广告,广告总费用不超过9万元,甲、乙电视台的广告收费标准分别为500元/分钟和200元/分钟,规定甲、乙两个电视台为该公司所做的每分钟广告,能给公司事来的收益分

数学建模线性规划

线性规划 1.简介: 线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法.在经济管理、交通运输、工农业生产等经济活动中,提高经济效果是人们不可缺少的要求,而提高经济效果一般通过两种途径:一是技术方面的改进,例如改善生产工艺,使用新设备和新型原材料.二是生产组织与计划的改进,即合理安排人力物力资源. 线性规划所研究的是:在一定条件下,合理安排人力物力等资源,使经济效果达到最好.规划问题。一般地,求线性目标函数在线性约束条件下的最大值或最小值的问题,统称为线性线性约束条件的解叫做可行解,由所有可行解组成的集合叫做可行域。 (x)都是线性函数,则该模型称为在优化模型中,如果目标函数f(x)和约束条件中的g i 线性规划。 2.线性规划的3个基本要素 (1)决策变量 (2)目标函数f(x) (x)≤0称为约束条件) (3)约束条件(g i 3.建立线性规划的模型 (1)找出待定的未知变量(决策变量),并用袋鼠符号表示他们。 (2)找出问题中所有的限制或者约束,写出未知变量的线性方程或线性不等式。

(3)找到模型的目标或判据,写成决策变量的线性函数,以便求出其最大值或最小值。以下题为例,来了解一下如何将线性规划用与实际的解题与生活中。 生产计划问题 某工厂生产甲乙两种产品,每单位产品消耗和获得的利润如表 试拟订生产计划,使该厂获得利润最大 解答:根据解题的三个基本步骤 (1)找出未知变量,用符号表示: 设甲乙两种产品的生产量分别为x 1与x 2 吨,利润为z万元。 (2)确定约束条件: 在这道题目当中约束条件都分别为:钢材,电力,工作日以及生产量不能为负的限制 钢材:9x 1+5 x 2 ≤360, 电力:4x 1+5 x 2 ≤200, 工作日:3x 1+10 x 2 ≤300, x 1≥0 ,x 2 ≥0, (3)确定目标函数: Z=7x 1+12 x 2

多目标线性规划的若干解法及MATLAB实现

多目标线性规划的若干解法及MATLAB 实现 一.多目标线性规划模型 多目标线性规划有着两个和两个以上的目标函数,且目标函数和约束条件全是线性函 数,其数学模型表示为: 11111221221122221122max n n n n r r r rn n z c x c x c x z c x c x c x z c x c x c x =+++??=+++?? ??=+++? (1) 约束条件为: 1111221121122222112212,,,0 n n n n m m mn n m n a x a x a x b a x a x a x b a x a x a x b x x x +++≤??+++≤?? ??+++≤?≥?? (2) 若(1)式中只有一个1122i i i in n z c x c x c x =+++ ,则该问题为典型的单目标线性规划。我们记:()ij m n A a ?=,()ij r n C c ?=,12(,,,)T m b b b b = ,12(,,,)T n x x x x = , 12(,,,)T r Z Z Z Z = . 则上述多目标线性规划可用矩阵形式表示为: max Z Cx = 约束条件:0 Ax b x ≤?? ≥? (3) 二.MATLAB 优化工具箱常用函数[3] 在MA TLAB 软件中,有几个专门求解最优化问题的函数,如求线性规划问题的linprog 、求有约束非线性函数的fmincon 、求最大最小化问题的fminimax 、求多目标达到问题的fgoalattain 等,它们的调用形式分别为: ①.[x,fval]=linprog(f,A,b,Aeq,beq,lb,ub) f 为目标函数系数,A,b 为不等式约束的系数, Aeq,beq 为等式约束系数, lb,ub 为x 的下 限和上限, fval 求解的x 所对应的值。 算法原理:单纯形法的改进方法投影法 ②.[x,fval ]=fmincon(fun,x0,A,b,Aeq,beq,lb,ub ) fun 为目标函数的M 函数, x0为初值,A,b 为不等式约束的系数, Aeq,beq 为等式约束

考虑如下线性规划问题

考虑如下线性规划问题

考虑如下线性规划问题: Min z=60 x+402x+803x 1 s.t. 3 x+22x+3x≥2 1 4 x+2x+33x≥4 1 2 x+22x+23x≥3 1 x,2x,3x≥0 1 要求:(1)写出其对偶问题; (2)用对偶单纯形法求解原问题; (3)用单纯形法求解其对偶问题; (4)对比(2)与(3)中每步计算得到的结果。 解:(1)设对应于上述约束条件的对偶变量分别为 y,2y,3y;则由原问 1 题和对偶问题,可以直接写出对偶问题为: Max Z’=2 y+42y+33y 1 s.t 3 y+42y+23y≤60 1 2 y+2y+23y≤40 1 y+32y+23y≤80 1 y,2y,3y≥0 1 (2)用对偶单纯形法求解原问题(添加松弛变量 x,5x,6x) 4 MaxZ= -60 x-402x-803x+04x+05x+06x 1 s.t -3 x-22x-3x+4x=-2 1 -4 x-2x-33x+5x=-4 1 -2 x-22x-23x+6x=-3 1

x,2x,3x≥0 1 建立此问题的初始单纯形表,可见: 从表中可以看到,检验数行对应的对偶问题的解是可行解。因b列数字为负,故需进行迭代运算。 换出变量的确定,计算min(-2,-4,-3)=-4,故 x为换出变量。 5 换入变量的确定,计算得15,40,80/3,故 x为换入变量。 1 由表可知, x为换出变量。2x为换入变量。然后继续画单纯形表: 6

可得 x为换出变量,3x为换入变量。继续做单纯形表: 4 所以此问题的最优解为X=(11/10,19/30,1/10),此对偶问题的最优解为Y=(16,12,30),原问题的最小值为118/3. (3)MaxZ’=2 y+42y+33y+04y+05y+06y 1 s.t 3 y+42y+23y+4y=60 1 2 y+2y+23y+5y=40 1 y+32y+23y+6y=80 1 y,2y,3y,4y,5y,6y≥0 1 然后建立单纯形表,可得

(完整版)简单的线性规划问题(附答案)

简单的线性规划问题 [ 学习目标 ] 1.了解线性规划的意义以及约束条件、目标函数、可行解、可行域、最优解等基本概念 .2. 了解线性规划问题的图解法,并能应用它解决一些简单的实际问题. 知识点一线性规划中的基本概念 知识点二线性规划问题 1.目标函数的最值 线性目标函数 z=ax+by (b≠0)对应的斜截式直线方程是 y=-a x+z,在 y 轴上的 截距是z, b b b 当 z 变化时,方程表示一组互相平行的直线. 当 b>0,截距最大时, z 取得最大值,截距最小时, z 取得最小值; 当 b<0,截距最大时, z 取得最小值,截距最小时, z 取得最大值. 2.解决简单线性规划问题的一般步骤在确定线性约束条件和线性目标函数的前提下,解决简单线性规划问题的步骤可以概括为:“画、移、求、答”四步,即, (1)画:根据线性约束条件,在平面直角坐标系中,把可行域表示的平面图形准确地画出来,可行域可以是封闭的多边形,也可以是一侧开放的无限大的平面区域.(2)移:运用数形结合的思想,把目标函数表示的直线平行移动,最先通过或最后通过的顶点 (或边界 )便是最优解. (3)求:解方程组求最优解,进而求出目标函数的最大值或最小值. (4)答:写出答案.

知识点三简单线性规划问题的实际应用 1.线性规划的实际问题的类型 (1)给定一定数量的人力、物力资源,问怎样运用这些资源,使完成的任务量最大,收到的效益最大; (2)给定一项任务,问怎样统筹安排,使完成这项任务耗费的人力、物力资源量最小.常见问题有: ①物资调动问题例如,已知两煤矿每年的产量,煤需经两个车站运往外地,两个车站的运输能力是有限的,且已知两煤矿运往两个车站的运输价格,煤矿应怎样编制调动方案,才能使总运费最小? ②产品安排问题例如,某工厂生产甲、乙两种产品,每生产一个单位的甲种或乙种产品需要的A、B、C 三种 材料的数量,此厂每月所能提供的三种材料的限额都是已知的,这个工厂在每个月中应如何安排这两种产品的生产,才能使每月获得的总利润最大? ③下料问题例如,要把一批长钢管截成两种规格的钢管,应怎样下料能使损耗最小?2.解答线性规划实际应用题的步骤 (1)模型建立:正确理解题意,将一般文字语言转化为数学语言,进而建立数学模型,这需要在学习有关例题解答时,仔细体会范例给出的模型建立方法. (2)模型求解:画出可行域,并结合所建立的目标函数的特点,选定可行域中的特殊点作为最优解. (3)模型应用:将求解出来的结论反馈到具体的实例中,设计出最佳的方案. 题型一求线性目标函数的最值 y≤2, 例 1 已知变量 x,y 满足约束条件 x+y≥1,则 z=3x+y 的最大值为 ( ) x-y≤1, A . 12 B .11 C .3 D .- 1 答案 B 解析首先画出可行域,建立在可行域的基础上,分析最值点,然后通过解方程组得最值点 的坐标,代入即可.如图中的阴影部分,即为约束条件对应的可行域,当直线y=-3x+z 经 y=2,x= 3,

R语言求解线性规划和非线性规划

第七章线性规划与非线性规划 例1m a x z=10x 1+5x2 s.t.5x1+2x2<=8 3x1+4x2=9 x1+x2>=1 x1,x2>=0 首先可化为标准形式:min - z = -10x1 -5x2 s.t. 5x1+2x1<=8 -x1-x2<=-1 3x1+4x2=9 x1,x2>=0 library(Rglpk) obj<-c(-10,-5) mat<-matrix(c(5,2,-1,-1,3,4),3,2,T) dir<-c("<=","<=","==") rhs<-c(8,-1,9) Rglpk_solve_LP(obj,mat,dir,rhs) #直接求解 library(Rglpk) obj<-c(10,5) mat<-matrix(c(5,2,1,1,3,4),3,2,T) dir<-c("<=",">=","==") rhs<-c(8,1,9) Rglpk_solve_LP(obj,mat,dir,rhs,max=T) 非线性规划求解(Rdonlp2) 例2 有如下的条件约束最优化问题:

22min(sin cos ) 1001001001002133 2sin cos 3z x y y x x y x y x y xy x y =+-<

简单的线性规划应用题解析

简单的线性规划应用题解析 1.某人有楼房一幢,室内面积共180㎡,拟分隔两类房间作为旅游客房.大每间面积为18㎡,可住游客5名,每名游客每天住宿费为40元;小房间每间面积为15㎡,可住游客3名,每名游客每天住宿费为50元;装修大房间每间需1000元,装修小房间每间需600元.如果他只能筹款8000元用于装修,且游客能住满客房,他应隔出大房间和小房间各多少间,能获得最大收益? 设应隔出大、小房间分别为x ,y 间,此时收益为z 元,则 1815180 1000600800000 x y x y x y +≤??+≤? ? ≥??≥? 200150z x y =+ 将上述不等式组化为 6560 534000 x y x y x y +≤??+≤? ? ≥??≥? 作出可行域,如图⑴,作直线l:200x+150y=0,即l:4x+3y=0. 将直线l 向右平移,得到经过可行域的点B ,且距原点最远的直线l 1. 解方程组 6560 5340 x y x y +=?? +=? 图⑴

得最优解 20 7 60 7 2.9 8.6 x y =≈ ? ? =≈ ? 但是房间的间数为整数,所以,应找到是整数的最优解. ①当x=3时,代入5x+3y=40中,得401525 338 y- ==>,得整点(3,8),此时z=200×3+150×8=1800(元); ②当x=2时,代入6x+5y=60中,得601248 559 y- ==>,得整点(2,9),此时z=200×2+150×9=1750(元); ③当x=1时,代入6x+5y=60中,得60654 5510 y- ==>,得整点(1,10),此时z=200×1+150×10=1700(元); ④当x=0时,代入6x+5y=60中,得60 512 y==,得整点(0,12),此时 z=150×12=1800(元). 由上①~④知,最优整数解为(0,12)和(3,8). 答:有两套分隔房间的方案:其一是将楼房室内全部隔出小房间12间;其二是隔出大房间3间,小房间8间,两套方案都能获得最大收益为1800元. 2.某家具厂有方木料90m3,五合板60㎡,准备加工成书桌和书橱出售.已知生产每张书桌需要方木料0.1 m3、五合板2㎡,生产每个书橱需要方木料0.2 m3、五合板1㎡,出售一张书桌可获得利润80元,出售一个书橱可获得利润120元.如果只安排生产书桌,可获利润多少?如果只安排生产书橱,可获利润多少?怎样安排生产可使所得利润最大? 【解析】将已知数据列成下表: 用完五合板,此时获利润为80×300=24000(元); ⑵只生产书橱因为90÷0.2=450,600÷1=600,所以,可产生450个书橱,用完方木料.此时获利润为120×450=54000(元);

数学建模-线性规划

-1- 第一章线性规划 §1 线性规划 在人们的生产实践中,经常会遇到如何利用现有资源来安排生产,以取得最大经济 效益的问题。此类问题构成了运筹学的一个重要分支—数学规划,而线性规划(Linear Programming 简记LP)则是数学规划的一个重要分支。自从1947 年G. B. Dantzig 提出 求解线性规划的单纯形方法以来,线性规划在理论上趋向成熟,在实用中日益广泛与深入。特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后,线性 规划的适用领域更为广泛了,已成为现代管理中经常采用的基本方法之一。 1.1 线性规划的实例与定义 例1 某机床厂生产甲、乙两种机床,每台销售后的利润分别为4000 元与3000 元。 生产甲机床需用A、B机器加工,加工时间分别为每台2 小时和1 小时;生产乙机床 需用A、B、C三种机器加工,加工时间为每台各一小时。若每天可用于加工的机器时 数分别为A 机器10 小时、B 机器8 小时和C 机器7 小时,问该厂应生产甲、乙机床各几台,才能使总利润最大? 上述问题的数学模型:设该厂生产1 x 台甲机床和2 x 乙机床时总利润最大,则1 2 x , x 应满足 (目标函数)1 2 max z = 4x + 3x (1) s.t.(约束条件) ?? ? ?? ? ? ≥ ≤ + ≤ + ≤ , 0 7 8 2 10 1 2 2 1 2 1 2 x x x x x x x (2) 这里变量1 2 x , x 称之为决策变量,(1)式被称为问题的目标函数,(2)中的几个不等式是问题的约束条件,记为s.t.(即subject to)。由于上面的目标函数及约束条件均为线性

数学建模线性规划与非线性规划

实验7:线性规划与非线性规划 班级:2015级电科班,学号:222015333210187,姓名:吴京宣,第1组 ====================================================================== 一、实验目的: 1. 了解线性规划的基本内容。 2. 直观了解非线性规划的基本内容。 3. 掌握用数学软件求解优化问题。 二、实验内容 1. 两个引例. 2. 用数学软件包MATLAB求解线性规划与非线性规划问题. 3. 用数学软件包LINDO、LINGO求解线性规划问题. 4. 建模案例:投资的收益与风险. 5. 非线性规划的基本理论 6. 钢管订购及运输优化模型. 三、实验步骤 对以下问题,编写M文件: 1.某厂生产甲乙两种口味的饮料,每百箱甲饮料需用原料6千克,工人10名,可获利10万元;每百箱乙饮料需用原料5千克,工人20名,可获利9万元.今工厂共有原料60千克,工人150名,又由于其他条件所限甲饮料产量不超过800箱.问如何安排生产计划,即两种饮料各生产多少使获利最大.进一步讨论: 1)若投资0.8万元可增加原料1千克,问应否作这项投资. 2)若每100箱甲饮料获利可增加1万元,问应否改变生产计划. 2.某厂向用户提供发动机,合同规定,第一、二、三季度末分别交货40台、60 台、80台.每季度的生产费用为(单位:元), 其中x 是该季度生产的台数.若交货后有剩余,可用于下季度交货,但需支付存储费,每台每季度c元.已知工厂每季度最大生产能力为100台,第一季度开始时无存货,设a=50、b=0.2、c=4,问:工厂应如何安排生产计划,才能既满足合同又使总费用最低.讨论a、b、c变化对计划的影响,并作出合理的解释.

应用题,线性规划

应用题最后一卷 三题 一、类型 基本不等式 1、某种商品第一天销售价为42元,以后每天提价2元,且在开始销售的前30天内每天的销售量与上市天数的关系是5100()x g x x +=(其中x 为天数). (1)写出上市30天内商品销售价格与天数x 的关系式. (2)求销售30天内,哪一天的销售额最小,并求出最小值. 二、类型 换元成二次函数 2、销售甲、乙两种商品所得利润分别是12,y y 万元,它们与投入资金x 万元的关系分别为 12,y a y bx ==(其中,,m a b 都为常数) ,函数12,y y 对应的曲线12,C C 如图所示. (1)求函数12,y y 的解析式; (2)若该商场一共投资8万元经销甲、乙两种商品,求该商场所获利润的最大值. 解:(1)由题意0835m a m a +=???+=?? ,解得5 4,54-==a m , 14,(0)5 y x =≥………………………………………………4分 又由题意588=b 得5 1=b 215 y x =(0)x ≥……………………………………………7分 (2)设销售甲商品投入资金x 万元,则乙投入(8x -)万元 由(1 )得41(8)55 y x =+-,(08)x ≤≤………………………10分 ,(13)t t =≤≤,则有 2149555y t t =-++=2113(2)55 t --+,(13)t ≤≤, 当2=t 即3=x 时,y 取最大值135 . 答:该商场所获利润的最大值为135 万元.………………………………16分

线性规划的应用题三题 1、 某企业生产甲、乙两种产品,已知生产每吨甲产品要用A 原料3吨、B 原料2吨;生产每吨乙产品要用A 原料1吨、B 原料3吨.销售每吨甲产品可获得利润5万元、每吨乙产品可获得利润3万元,该企业在一个生产周期内消耗A 原料不超过13吨、B 原料不超过18吨,那么该企业可获得的最大利润是万元. 【解析】设生产甲产品x 吨、乙产品y 吨, 则获得的利润为z =5x +3y . 由题意得????? x ≥0,y ≥0,3x +y ≤13,2x +3y ≤18, 可行域如图阴影所示. 由图可知当x 、y 在A 点取值时,z 取得最大值,此时x =3,y =4,z =5×3+3×4=27(万元).

《运筹学》习题线性规划部分练习题及答案

《运筹学》线性规划部分练习题 一、思考题 1.什么是线性规划模型,在模型中各系数的经济意义是什么? 2.线性规划问题的一般形式有何特征? 3.建立一个实际问题的数学模型一般要几步? 4.两个变量的线性规划问题的图解法的一般步骤是什么? 5.求解线性规划问题时可能出现几种结果,那种结果反映建模时有错误? 6.什么是线性规划的标准型,如何把一个非标准形式的线性规划问题转化成标准形式。 7.试述线性规划问题的可行解、基础解、基础可行解、最优解、最优基础解的概念及它们之间的相互关系。 8.试述单纯形法的计算步骤,如何在单纯形表上判别问题具有唯一最优解、有无穷多个最优解、无界解或无可行解。 9.在什么样的情况下采用人工变量法,人工变量法包括哪两种解法? 10.大M 法中,M 的作用是什么?对最小化问题,在目标函数中人工变量的系数取什么?最大化问题呢? 11.什么是单纯形法的两阶段法?两阶段法的第一段是为了解决什么问题?在怎样的情况下,继续第二阶段? 二、判断下列说法是否正确。 1.线性规划问题的最优解一定在可行域的顶点达到。 2.线性规划的可行解集是凸集。 3.如果一个线性规划问题有两个不同的最优解,则它有无穷多个最优解。 4.线性规划模型中增加一个约束条件,可行域的范围一般将缩小,减少一个约束条件,可行域的范围一般将扩大。 5.线性规划问题的每一个基本解对应可行域的一个顶点。 6.如果一个线性规划问题有可行解,那么它必有最优解。 7.用单纯形法求解标准形式(求最小值)的线性规划问题时,与 > j σ 对应的变量都 可以被选作换入变量。 8.单纯形法计算中,如不按最小非负比值原则选出换出变量,则在下一个解中至少有一个基变量的值是负的。 9.单纯形法计算中,选取最大正检验数k σ对应的变量k x作为换入变量,可使目标函数值得到最快的减少。 10.一旦一个人工变量在迭代中变为非基变量后,该变量及相应列的数字可以从单纯形表中删除,而不影响计算结果。 三、建立下面问题的数学模型 1.某公司计划在三年的计划期内,有四个建设项目可以投资:项目Ⅰ从第一年到 第三年年初都可以投资。预计每年年初投资,年末可收回本利120% ,每年又可以重新将所获本利纳入投资计划;项目Ⅱ需要在第一年初投资,经过两年可收回本利150% ,又可以重新将所获本利纳入投资计划,但用于该项目的最大投资额不得超过20万元;项目Ⅲ需要在第二年年初投资,经过两年可收回本利160% ,但用于该项目的最大投资额不得超过15万元;项目Ⅳ需要在第三年年初投资,年末可收回本利140% ,但用于该项目的最大投资额不得超过10万元。在这个计划期内,该公司第一年可供投资的资金有30万元。问怎样的投资方案,才能使该公司在这个计划期获得最大利润? 2.某饲养场饲养动物,设每头动物每天至少需要700克蛋白质、30克矿物质、100克维生素。现有五种饲料可供选用,各种饲料每公斤营养成分含量及单 价如下表2—1所示:

简单的线性规划问题附答案

简单的线性规划问题 [学习目标] 1.了解线性规划的意义以及约束条件、目标函数、可行解、可行域、最优解等基本概念.2.了解线性规划问题的图解法,并能应用它解决一些简单的实际问题. 知识点一 线性规划中的基本概念 1.目标函数的最值 线性目标函数z =ax +by (b ≠0)对应的斜截式直线方程是y =-a b x +z b ,在y 轴上的截距是z b , 当z 变化时,方程表示一组互相平行的直线. 当b >0,截距最大时,z 取得最大值,截距最小时,z 取得最小值; 当b <0,截距最大时,z 取得最小值,截距最小时,z 取得最大值. 2.解决简单线性规划问题的一般步骤 在确定线性约束条件和线性目标函数的前提下,解决简单线性规划问题的步骤可以概括为:“画、移、求、答”四步,即, (1)画:根据线性约束条件,在平面直角坐标系中,把可行域表示的平面图形准确地画出来,

可行域可以是封闭的多边形,也可以是一侧开放的无限大的平面区域. (2)移:运用数形结合的思想,把目标函数表示的直线平行移动,最先通过或最后通过的顶点(或边界)便是最优解. (3)求:解方程组求最优解,进而求出目标函数的最大值或最小值. (4)答:写出答案. 知识点三简单线性规划问题的实际应用 1.线性规划的实际问题的类型 (1)给定一定数量的人力、物力资源,问怎样运用这些资源,使完成的任务量最大,收到的效益最大; (2)给定一项任务,问怎样统筹安排,使完成这项任务耗费的人力、物力资源量最小. 常见问题有: ①物资调动问题 例如,已知两煤矿每年的产量,煤需经两个车站运往外地,两个车站的运输能力是有限的,且已知两煤矿运往两个车站的运输价格,煤矿应怎样编制调动方案,才能使总运费最小? ②产品安排问题 例如,某工厂生产甲、乙两种产品,每生产一个单位的甲种或乙种产品需要的A、B、C三种材料的数量,此厂每月所能提供的三种材料的限额都是已知的,这个工厂在每个月中应如何安排这两种产品的生产,才能使每月获得的总利润最大? ③下料问题 例如,要把一批长钢管截成两种规格的钢管,应怎样下料能使损耗最小? 2.解答线性规划实际应用题的步骤 (1)模型建立:正确理解题意,将一般文字语言转化为数学语言,进而建立数学模型,这需要在学习有关例题解答时,仔细体会范例给出的模型建立方法. (2)模型求解:画出可行域,并结合所建立的目标函数的特点,选定可行域中的特殊点作为最优解.

线性与非线性规划问题求解

线性与非线性规划问题求解 实验目的:学会用lindo 和lingo 软件求解线性和非线性规划,并作简单分析。 实验内容: 问题1:最佳连续投资方案 某部门在今后五年内考虑下列项目投资,已知 项目1 从第一年到第四年每年年初需要投资,并于次年末回收本利115%; 项目 2 第三年年初需要投资,到第五年末能回收本利125%,但规定最大投资额不超过4 万元; 项目 3 第二年年初需要投资,到第五年末能回收本利140%,但规定最大投资额不超过3 万元; 项目4 五年内每年年初可购买公债,于每年末归还,并加利息6%. 该部门现有资金10万元,问它应如何确定给这些项目每年的投资额,使到第五年末拥有的资金的本利总额为最大? 提示:设ij y 表示第i 年年初投资给项目j 的资金额度(单位:万元),则各年的投资限制为 第一年:;101411≤+y y 第二年:年初拥有的资金额为,06.110141114y y y --+因此有 ;06.0101411242321y y y y y +-≤++ 第三年:年初拥有的资金额为 ;06.115.106.01024232124111411y y y y y y y ---+++- 因此有 ;06.006.015.0102423211411343231y y y y y y y y +--++≤++ 依次类推有: 第四年: ;06.006.015.006.015.01034323124232114114441y y y y y y y y y y +--+-+++≤+ 第五年: ; 06.006.015.006.015.006.015.0104441343231242321141154y y y y y y y y y y y +-+-++-+++≤本问题是要制定投资方案使第五年末该部门拥有的资金额最大,即 5441322306.115.125.140.1max y y y y f +++=. 问题2:运输问题 某公司有3个仓库A1、A2、A3,库存原料量分别为:A1为21吨,A2为12吨,A3为27

《运筹学》习题线性规划部分练习题及答案.doc

《运筹学》线性规划部分练习题 一、思考题 1. 什么是线性规划模型,在模型中各系数的经济意义是什么? 2. 线性规划问题的一般形式有何特征? 3. 建立一个实际问题的数学模型一般要几步? 4. 两个变量的线性规划问题的图解法的一般步骤是什么? 5. 求解线性规划问题时可能出现几种结果,那种结果反映建模时有错误? 6. 什么是线性规划的标准型,如何把一个非标准形式的线性规划问题转化成标准形式。 7. 试述线性规划问题的可行解、基础解、基础可行解、最优解、最优基础解的概念及它们之间的相互关系。 8. 试述单纯形法的计算步骤,如何在单纯形表上判别问题具有唯一最优解、有无穷多个最优解、无界解或无可行解。 9. 在什么样的情况下采用人工变量法,人工变量法包括哪两种解法? 10.大M 法中,M 的作用是什么?对最小化问题,在目标函数中人工变量的系数取什么?最大化问题呢? 11.什么是单纯形法的两阶段法?两阶段法的第一段是为了解决什么问题?在怎样的情况下,继续第二阶段? 二、判断下列说法是否正确。 1. 线性规划问题的最优解一定在可行域的顶点达到。 2. 线性规划的可行解集是凸集。 3. 如果一个线性规划问题有两个不同的最优解,则它有无穷多个最优解。 4. 线性规划模型中增加一个约束条件,可行域的范围一般将缩小,减少一个约束条件,可行域的范围一般将扩大。 5. 线性规划问题的每一个基本解对应可行域的一个顶点。 6. 如果一个线性规划问题有可行解,那么它必有最优解。 7. 用单纯形法求解标准形式(求最小值)的线性规划问题时,与0 >j σ对应的变量都可以被选作换入变量。 8. 单纯形法计算中,如不按最小非负比值原则选出换出变量,则在下一个解中至少有一个基变量的值是负的。 9. 单纯形法计算中,选取最大正检验数k σ对应的变量k x 作为换入变量,可使目 标函数值得到最快的减少。 10. 一旦一个人工变量在迭代中变为非基变量后,该变量及相应列的数字可以从单纯形表中删除,而不影响计算结果。 三、建立下面问题的数学模型 1. 某公司计划在三年的计划期内,有四个建设项目可以投资:项目Ⅰ从第一年到 第三年年初都可以投资。预计每年年初投资,年末可收回本利120% ,每年又可以重新将所获本利纳入投资计划;项目Ⅱ需要在第一年初投资,经过两年可收回本利150% ,又可以重新将所获本利纳入投资计划,但用于该项目的最大投资额不得超过20万元;项目Ⅲ需要在第二年年初投资,经过两年可收回本利160% ,但用于该项目的最大投资额不得超过15万元;项目Ⅳ需要在第三年年初投资,年末可收回本利140% ,但用于该项目的最大投资额不得超过10万元。在这个计划期内,该公司第一年可供投资的资金有30万元。问怎样的投资方案,才能使该公司在这个计划期获得最大利润? 2.某饲养场饲养动物,设每头动物每天至少需要700克蛋白质、30克矿物质、 100克维生素。现有五种饲料可供选用,各种饲料每公斤营养成分含量及单 价如下表2—1所示:

八种经典线性规划例题最全总结(经典)

线性规划常见题型及解法 由已知条件写出约束条件,并作出可行域,进而通过平移直线在可行域内求线性目标函数的最优解是最常见的题型,除此之外,还有以下六类常见题型。 一、求线性目标函数的取值范围 例1、若x、y满足约束条件 ,则z=x+2y的取值范围是() A、[2,6] B、[2,5] C、[3,6] D、(3,5] 解:如图,作出可行域,作直线l:x+2y=0,将 l向右上方平移,过点A(2,0)时,有最小值 2,过点B(2,2)时,有最大值6,故选A 二、求可行域的面积

例2、不等式组 表示的平面区域的面积为() A、4 B、1 C、5 D、无穷大 解:如图,作出可行域,△ABC的面积即为所求,由梯形OMBC的面积减去梯形OMAC的面积即可,选B 三、求可行域中整点个数 例3、满足|x|+|y|≤2的点(x,y)中整点(横纵坐标都是整数)有() A、9个 B、10个 C、13个 D、14个

解:|x|+|y|≤2等价于 作出可行域如右图,是正方形内部(包括边界),容易得到整点个数为13个,选D 四、求线性目标函数中参数的取值范围 例4、已知x、y满足以下约束条件 ,使z=x+ay(a>0)取得最小值的最优解有无数个,则a的值为() A、-3 B、3 C、-1 D、1

解:如图,作出可行域,作直线l:x+ay=0,要使目标函数z=x+ay(a>0)取得最小值的最优解有无数个,则将l向右上方平移后与直线x+y=5重合,故 a=1,选D 五、求非线性目标函数的最值 例5、已知x、y满足以下约束条件 ,则z=x2+y2的最大值和最小值分别是() A、13,1 B、13,2 C、13, D、 , 解:如图,作出可行域,x2+y2是点(x,y)到原点的距离的平方,故最大值为点A(2,3)到原点的距离的平方,即|AO|2=13,最小值为原点到直线2x+y-2=0的距离的平方,即为

多目标非线性规划程序Matlab完整版

多目标非线性规划程序 M a t l a b Document serial number【NL89WT-NY98YT-NC8CB-NNUUT-NUT108】

f u n c t i o n[e r r m s g,Z,X,t,c,f a i l]= BNB18(fun,x0,xstat,xl,xu,A,B,Aeq,Beq,nonlcon,setts,options1,options2,maxSQPit,varargin ); %·Dêy1£Díóa·§¨μü′ú·¨£úDê1ó£DèOptimization toolbox §3 % Minimize F(x) %subject to: xlb <= x <=xub % A*x <= B % Aeq*x=Beq % C(x)<=0 % Ceq(x)=0 % % x(i)éaáD±á£êy£ò1ì¨μ % ê1óê %[errmsg,Z,X]=BNB18('fun',x0,xstat,xl,xu,A,B,Aeq,Beq,'nonlcon',setts) %fun£o Mt£±íê×Dˉ±êoˉêyf=fun(x) %x0: áDòᣱíê±á3μ %xstat£o áDòá£xstat(i)=0±íêx(i)aáD±á£1±íêêy£2±íê1ì¨μ %xl£o áDòᣱíê±á %xu: áDòᣱíê±áé %A: ó, ±íêD2μèêêμêy %B: áDòá, ±íêD2μèêêé %Aeq: ó, ±íêDμèêêμêy %Beg: áDòá, ±íêD2μèêêóòμ %nonlcon: Mt£±íê·Dêoˉêy[C,Ceq]=nonlin(x),DC(x)a2μèêê, % Ceq(x)aμèêê %setts: ·¨éè %errmsq: ·μ′íóìáê %Z: ·μ±êoˉêy×Dμ %X: ·μ×óa % %àyìa % max x1*x2*x3 % -x1+2*x2+2*x3>=0 % x1+2*x2+2*x3<=72 % 10<=x2<=20 % x1-x2=10 % èD′ Moˉêy % function f=discfun(x) % f=-x(1)*x(2)*x(3); %óa % clear;x0=[25,15,10]';xstat=[1 1 1]'; % xl=[20 10 -10]';xu=[30 20 20]'; % A=[1 -2 -2;1 2 2];B=[0 72]';Aeq=[1 -1 0];Beq=10; % [err,Z,X]=BNB18('discfun',x0,xstat,xl,xu,A,B,Aeq,Beq); % XMAX=X',ZMAX=-Z %

相关文档
相关文档 最新文档