版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
第二章线性规划的图解法第一页,共六十四页,2022年,8月28日第二章:线性规划的图解法第一节:线性规划问题的提出第二节:线性规划的图解法第三节:图解法的灵敏度分析本章的重点和难点:2:图解法的灵敏度分析1:线性规划的图解法第二页,共六十四页,2022年,8月28日线性规划的定义求线性目标函数在线性约束条件下的最大值或最小值的问题,统称为线性规划问题。满足线性约束条件的解叫做可行解,由所有可行解组成的集合叫做可行域。决策变量、约束条件、目标函数是线性规划的三要素.第二章线性规划的图解法第三页,共六十四页,2022年,8月28日4
在管理中一些典型的线性规划应用合理利用线材问题:如何在保证生产的条件下,下料最少配料问题:在原料供应量的限制下如何获取最大利润投资问题:从投资项目中选取方案,使投资回报最大第二章线性规划的图解法第四页,共六十四页,2022年,8月28日
产品生产计划:合理利用人力、物力、财力等,使获利最大劳动力安排:用最少的劳动力来满足工作的需要运输问题:如何制定调运方案,使总运费最小第二章线性规划的图解法第五页,共六十四页,2022年,8月28日问题1:某工厂计划生产甲、乙两种产品,生产1kg的甲需耗煤9t、电力4kw.h、油3t;生产1kg的乙需耗煤4t、电力5kw.h、油10t;该厂现有煤360t、电力200kw.h、油300t。已知甲产品每千克的售价为7万元、乙产品每千克的售价为12万元。在上述条件下决定生产方案,使得总收入最大。第二章线性规划的图解法第六页,共六十四页,2022年,8月28日问题1具体数据如表所示:资源产品单耗资源甲乙资源限量煤(t)电(kw.h)油(t)9445310360200300单位产品价格712提出和形成问题建立模型求解结果的分析和应用第二章线性规划的图解法第七页,共六十四页,2022年,8月28日总收入记为f,则f=7x1+12x2
,为体现对其求极大化,在f的前面冠以极大号Max,也就是:甲、乙产品的计划产量,记为x1
,x2;在本例中资源煤、电、油的数量是有限的,对产品甲和乙的生产量构成了约束,表示为:决策变量:目标函数:约束条件:Max(maximize最大化)Min(minimum)s.t.(subjectto受制于)第二章线性规划的图解法第八页,共六十四页,2022年,8月28日解:设安排甲、乙产量分别为x1
,x2,总收入为f
,则该问题的数学模型为:第二章线性规划的图解法第九页,共六十四页,2022年,8月28日(1)决策变量:甲、乙产品的产量x1
,x2★线性规划模型的三个基本要素:
(也是所有规划问题的三个基本要素):决策变量:需要决策的量,即等待求解的未知数。目标函数:想要达到的目标,用决策变量的表达式表示。约束条件:由于资源有限,为了实现目标有哪些资源限制,用决策变量的等式或不等式表示。(3)约束条件:(2)目标函数:总收入最大,Maxf=7x1+12x2
第二章线性规划的图解法第十页,共六十四页,2022年,8月28日什么是线性规划模型:决策变量为可控的连续变量。目标函数和约束条件都是线性的。x1
≥0,x2≥0
x1
=0,1,2,3…n第二章线性规划的图解法第十一页,共六十四页,2022年,8月28日
例2.某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产,已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制,如下表:问题:工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利最多?第二章线性规划的图解法第十二页,共六十四页,2022年,8月28日
目标函数:Maxz=50x1+100x2
约束条件:s.t.x1+x2≤3002x1+x2≤400x2≤250x1,x2≥0第二章线性规划的图解法第十三页,共六十四页,2022年,8月28日
一般形式目标函数:Max(Min)z=c1x1+c2x2+…+cnxn
约束条件:
s.t.a11x1+a12x2+…+a1nxn
≤(=,≥)b1
a21x1+a22x2+…+a2nxn
≤(=,≥)b2…………
am1x1+am2x2+…+amnxn
≤(=,≥)bm
x1,x2,…,xn≥0
第二章线性规划的图解法第十四页,共六十四页,2022年,8月28日
对于只有两个变量的简单的线性规划问题,一般采用图解法求解。这种方法仅适用于只有两个变量的线性规划问题。它的特点是直观而易于理解,但实用价值不大。第二章线性规划的图解法第十五页,共六十四页,2022年,8月28日
1.基本概念(1)可行解:满足约束条件的决策变量的取值(2)可行域:可行解的全体(3)最优解:使目标函数取得最优值的可行解(4)最优值:最优解代入目标函数所得到的值第二章线性规划的图解法第十六页,共六十四页,2022年,8月28日例3.用图解法对下列线性规划模型进行求解。MaxZ=2x1+3x2
x1+2x2≤84x1≤16x2≤12x1,x2≥0s.t.第二章线性规划的图解法第十七页,共六十四页,2022年,8月28日18
图解法求解的步骤:分别取决策变量X1,X2
为坐标向量建立直角坐标系。在直角坐标系里,图上任意一点的坐标代表了决策变量的一组值。第二章线性规划的图解法第十八页,共六十四页,2022年,8月28日9—8—7—6—5—4—3—2—1—0x2| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2
84x1
164x2
12x1+2x2
84x1
164x2
12x1、x2
0第二章线性规划的图解法第十九页,共六十四页,2022年,8月28日9—8—7—6—5—4—3—2—1—0| | | | | | | | |1 2 3 4 5 6 7 8 9x1
x1+2x2
84x1
164x2
12可行域ABCDO可行解:满足约束条件的解。红色区域中的每一个点(包括边界点)都是可行解。此区域是就是可行域。第二十页,共六十四页,2022年,8月28日9—8—7—6—5—4—3—2—1—0x2| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2
84x1
164x2
12ABCDO
目标函数Z=2x1+3x2在这个坐标平面上,它可以表示以Z为参数、-2/3为斜率的一族平行线:位于同一直线上的点,具有相同的目标函数,称为“等值线”。第二十一页,共六十四页,2022年,8月28日9—8—7—6—5—4—3—2—1—0x2
当Z值由小变大时,直线沿其法线方向向右上方移动。当移动到C时,Z值在可行域的边界上实现最大化。最优解(4,2),Z=14。| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2
84x1
164x2
12ABCDO最优解(4,2)最优生产方案:产品1生产4kg,产品2生产2kg,最大利润14元(最优值)。第二十二页,共六十四页,2022年,8月28日
结论:线性规划问题如果有最优解,则最优解一定在可行域的边界上取得.第二章线性规划的图解法第二十三页,共六十四页,2022年,8月28日
无穷多最优解
9—8—7—6—5—4—3—2—1—0x2| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2
84x1
164x2
12O可行域
第二章线性规划的图解法第二十四页,共六十四页,2022年,8月28日当移动到AB线段时,Z值在线段CD上实现最大化。线段CD上的任意一点都使Z取得相同的最大值,这个线性规划问题有无穷多最优解。9—8—7—6—5—4—3—2—1—0x2| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2
84x1
164x2
12ABCDO可行域第二章线性规划的图解法第二十五页,共六十四页,2022年,8月28日无可行解可行域为空集,无可行解,当然也无最优解。9—8—7—6—5—4—3—2—1—0x2| | | | | | | | |1 2 3 4 5 6 7 8 9x1Ol2l1第二章线性规划的图解法Maxz=x1+2x2
s.t.x1+2x2≤84x1≤164x2≤12x1≥3x2≥3
第二十六页,共六十四页,2022年,8月28日
无界解x1x20123456789654321线性规划问题可行域无界,目标函数可以增大到无穷大第二章线性规划的图解法第二十七页,共六十四页,2022年,8月28日该问题如果求目标函数的最小值,由下图可以看出在顶点B取得最优解:x1x20123456789654321B(1,0)第二章线性规划的图解法第二十八页,共六十四页,2022年,8月28日
唯一解无穷多解无有限最优解无可行解有最优解无最优解
求解一个线性规划问题就是要判断该问题属于那种情况,当问题有最优解时,还需要在可行区域中求出使目标函数达到最优值的点,也就是最优解,以及目标函数的最优值。第二章线性规划的图解法第二十九页,共六十四页,2022年,8月28日
练习题:1.考虑下面线性规划问题:
Maxz=2x1+3x2s.t.x1+2x2≤65x1+3x2≤15x1,x2≥0(1)画出其可行域(2)当Z=6时,画出等值线2x1+3x2=6(3)用图解法求出其最优解以及最优目标函数值第二章线性规划的图解法第三十页,共六十四页,2022年,8月28日31
例2:.某公司由于生产需要,共需要A,B两种原料至少350吨(A,B两种材料有一定替代性),其中A原料至少购进125吨。但由于A,B两种原料的规格不同,各自所需的加工时间也是不同的,加工每吨A原料需要2个小时,加工每吨B原料需要1小时,而公司总共有600个加工小时。又知道每吨A原料的价格为2万元,每吨B原料的价格为3万元,试问在满足生产需要的前提下,在公司加工能力的范围内,如何购买A,B两种原料,使得购进成本最低?第二章线性规划的图解法第三十一页,共六十四页,2022年,8月28日32
解:目标函数:Minf=2x1+3x2
约束条件:s.t.x1+x2≥350x1≥
1252x1+x2≤
600x1,x2≥0
采用图解法。如下图:得Q点坐标(250,100)为最优解。第二章线性规划的图解法第三十二页,共六十四页,2022年,8月28日
得Q点坐标(250,100)为最优解X1=250,x2=100时minf=800100200300400500600100200300400600500x1=125x1+x2=3502x1+x2=600x1x2Q第二章线性规划的图解法第三十三页,共六十四页,2022年,8月28日
例1.某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产,已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制,如下表:问题:工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利最多?第二章线性规划的图解法第三十四页,共六十四页,2022年,8月28日
数学模型为:求解得:x1=50,x2=250maxz=27500第二章线性规划的图解法第三十五页,共六十四页,2022年,8月28日36
引入松驰变量(含义是资源的剩余量)例1中引入s1,s2,s3模型化为Maxz=50x1+100x2+0s1+0s2+0s3s.t.x1+x2+s1=3002x1+x2+s2=400x2+s3=
250x1,x2,s1,s2,s3≥0对于最优解x1=50x2=250,s1=0s2=50s3=0说明:生产50单位Ⅰ产品和250单位Ⅱ产品将消耗完所有可能的设备台时数及原料B,但对原料A则还剩余50千克。第二章线性规划的图解法第三十六页,共六十四页,2022年,8月28日
松弛变量和剩余变量松弛变量:在线性规划中,对于“≤”约束条件中没有使用的资源或能力称之为松弛变量。剩余变量:在线性规划中,对于“≥”约束条件,可以增加一些代表最低限约束的超过量,称之为剩余变量。第二章线性规划的图解法第三十七页,共六十四页,2022年,8月28日38
线性规划的标准化一般形式目标函数:Max(Min)z=c1x1+c2x2+…+cnxn
约束条件:
s.t.a11x1+a12x2+…+a1nxn
≤(=,≥)b1
a21x1+a22x2+…+a2nxn
≤(=,≥)b2…………
am1x1+am2x2+…+amnxn
≤(=,≥)bm
x1,x2,…,xn≥0第二章线性规划的图解法第三十八页,共六十四页,2022年,8月28日
标准形式目标函数:Maxz=c1x1+c2x2+…+cnxn
约束条件:
s.t.a11x1+a12x2+…+a1nxn
=b1
a21x1+a22x2+…+a2nxn
=b2…………
am1x1+am2x2+…+amnxn
=bm
x1,x2,…,xn≥0,bi≥0第二章线性规划的图解法第三十九页,共六十四页,2022年,8月28日40
可以看出,线性规划的标准形式有如下四个特点:目标最大化;约束为等式;决策变量均非负;右端项非负。第二章线性规划的图解法第四十页,共六十四页,2022年,8月28日41
1.极小化目标函数的问题:设目标函数为:Minf=c1x1+c2x2+…+cnxn
(可以)令z=-f
,则该极小化问题与下面的极大化问题有相同的最优解即Maxz=-c1x1-c2x2-…-cnxn
但必须注意,尽管以上两个问题的最优解相同,但它们最优解的目标函数值却相差一个符号,即
Minf=-Maxz第二章线性规划的图解法第四十一页,共六十四页,2022年,8月28日42
2、约束条件不是等式的问题:设约束条件为
ai1x1+ai2x2+…+ainxn≤bi可以引进一个新的变量s
,使它等于约束右边与左边之差
s=bi–(ai1x1+ai2x2+…+ainxn)显然,s
也具有非负约束,即s≥0,这时新的约束条件成为
ai1x1+ai2x2+…+ainxn+s=bi第二章线性规划的图解法第四十二页,共六十四页,2022年,8月28日43
当约束条件为
ai1x1+ai2x2+…+ainxn≥bi
时,类似地令
s=(ai1x1+ai2x2+…+ainxn)-bi
显然,s
也具有非负约束,即s≥0,这时新的约束条件成为
ai1x1+ai2x2+…+ainxn-s=bi第二章线性规划的图解法第四十三页,共六十四页,2022年,8月28日
3.右端项有负值的问题:在标准形式中,要求右端项必须每一个分量非负。当某一个右端项系数为负时,如bi<0,则把该等式约束两端同时乘以-1,得到:
-ai1x1-ai2x2-…-ainxn=-bi。第二章线性规划的图解法第四十四页,共六十四页,2022年,8月28日
4.变量无符号限制的问题***
在标准形式中,必须每一个变量均有非负约束。当某一个变量xj没有非负约束时,可以令
xj=xj’-xj”
其中
xj’≥0,xj”≥0
即用两个非负变量之差来表示一个无符号限制的变量,当然xj的符号取决于xj’和xj”的大小。第二章线性规划的图解法第四十五页,共六十四页,2022年,8月28日46
例1:将以下线性规划问题转化为标准形式
Minf=2x1-3x2+4x3s.t.3x1
+4x2-5x3≤62x1+x3≥8
x1+x2+x3=-9
x1,x2,x3
≥0
第二章线性规划的图解法第四十六页,共六十四页,2022年,8月28日47
通过以上变换,可以得到以下标准形式的线性规划问题:
Maxz=-2x1
+3x2-4x3+0s1+0s2s.t.3x1+4x2-5x3+S1
=62x1+x3-S2=8-x1-x2-x3=9
x1,x2,x3,s1,s2
≥0第二章线性规划的图解法第四十七页,共六十四页,2022年,8月28日
练习题:1.将以下线性规划问题转化为标准形式
Minf=-x1-2x2s.t.3x1
+5x2≤70-2x1-5x2=50-3x1+2x2≥30
x1≤0,-≤x2≤+第二章线性规划的图解法第四十八页,共六十四页,2022年,8月28日
2.考虑下面线性规划问题:Maxz=10x1+5x2s.t.3x1
+4x2≤95x1+x2≤8
x1,x2≥0
(1)用图解法求解。(2)写出此线性规划问题的标准形式。(3)求出此线性规划问题的两个松弛变量的值。第二章线性规划的图解法第四十九页,共六十四页,2022年,8月28日50
图解法的灵敏度分析灵敏度分析:建立数学模型和求得最优解后,研究线性规划的一个或多个参数(系数)ci,aij,bj
变化时,对最优解产生的影响。第二章线性规划的图解法第五十页,共六十四页,2022年,8月28日
3.1目标函数中的系数ci
的灵敏度分析考虑例1的情况,ci的变化只影响目标函数等值线的斜率目标函数z=50x1+100x2
在z=x2(x2=z斜率为0
)
到
z=x1+x2(x2=-x1+z斜率为-1
)之间时,原最优解x1=50,x2=100仍是最优解。第二章线性规划的图解法第五十一页,共六十四页,2022年,8月28日
一般情况:
z=c1x1+c2x2
写成斜截式x2=-(c1/c2)x1+z/c2
目标函数等值线的斜率为
-(c1/c2),当-1-(c1/c2)0(*)时,原最优解仍是最优解。第二章线性规划的图解法第五十二页,共六十四页,2022年,8月28日53
假设产品Ⅱ的利润100元不变,即c2=100,代到式(*)并整理得
0c1
100假设产品Ⅰ的利润50元不变,即c1=50,代到式(*)并整理得
50c2
+第二章线性规划的图解法第五十三页,共六十四页,2022年,8月28日
假若产品Ⅰ、Ⅱ的利润均改变,则可直接用式(*)来判断假设产品Ⅰ、Ⅱ的利润分别为60元、55元,则
-2-(60/55)
-1已经不满足条件了。B点已经不是最优解了。
第二章线性规划的图解法第五十四页,共六十四页,2022年,8月28日55
3.2约束条件中右边系数bj
的灵敏度分析当约束条件中右边系数bj变化时,线性规划的可行域发生变化,可能引起最优解的变化。第二章线性规划的图解法第五十五页,共六十四页,2022年,8月28日
考虑例1的情况:假设设备台时增加1个台时,即b1变化为301,这时可行域扩大,最优解为
x2=250
和
x1+x2=301
的交点
x1=51,x2=250。变化后的总利润-变化前的总利润=增加的利润
(50×51+100×250)-(50×50+100×250)=50
第二章线性规划的图解法第五十六页,共六十四页,2022年,8月28日
x2CBADE目标函数:Maxz=50x1+100x2约束条件:s.t.x1+x2≤3102x1+x2≤400x2≤250x1,x2≥0最优解x1=60x2=250第二章线性规划的图解法第五十七页,共六十四页,2022年,8月28日
约束条件的对偶
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- GB/T 43891-2024非金属化工设备不透性石墨换热器传热系数和流阻性能测试方法
- 运营管理规划方案设计(2篇)
- 会“上瘾”的创意设计-知到答案、智慧树答案
- 2023年电工胶带投资申请报告
- 2023年双金属温度计资金筹措计划书
- 2024年防结皮剂项目资金申请报告代可行性研究报告
- 2023年医用超声治疗设备投资申请报告
- 2024年特种粉末及粉末冶金制品项目投资申请报告代可行性研究报告
- 2023年警车玻璃系列资金筹措计划书
- 2023年五面加工中心资金筹措计划书
- 国家开放大学《人文英语4》边学边练参考答案
- 四川省雅安市《教育基础知识和教师综合素养》公务员(国考)真题及答案
- GB/T 5240-2015氧化钕
- 海洋仪器环境试验方法 第13部分:倾斜和摇摆试验 编制说明
- GB 17957-2021凿岩机械与气动工具安全要求
- 加强人文关怀,做有温度的护理人n
- 资料管理方案5篇
- 外科-休克-课件
- 信息系统用户账号申请单
- 2022年动物防疫大赛理论考试题库(含答案)
- 阿司匹林的由来与发展课件
评论
0/150
提交评论