线性规划.ppt
- 文档编号:18721184
- 上传时间:2023-10-19
- 格式:PPT
- 页数:85
- 大小:1.10MB
线性规划.ppt
《线性规划.ppt》由会员分享,可在线阅读,更多相关《线性规划.ppt(85页珍藏版)》请在冰点文库上搜索。
运筹学的主要内容,线性规划,数学规划,非线性规划,整数规划,动态规划,学科内容,多目标规划,双层规划,组合优化,最优计数问题,网络优化,排序问题,统筹图,随机优化,对策论,排队论,库存论,决策分析,可靠性分析,许多生产计划与管理问题都可以归纳为最优化问题,最优化模型是数学建模中应用最广泛的模型之一,其内容包括线性规划、整数线性规划、非线性规划、动态规划、变分法、最优控制等.,近几年来的全国大学生数学建模竞赛中,几乎每次都有一道题要用到此方法.,目标函数,约束条件,可行解域,线性规划(LinearProgramming,缩写为LP)是运筹学的重要分支之一,在实际中应用得较广泛,其方法也较成熟,借助计算机,使得计算更方便,应用领域更广泛和深入。
线性规划通常研究资源的最优利用、设备最佳运行等问题。
例如,当任务或目标确定后,如何统筹兼顾,合理安排,用最少的资源(如资金、设备、原标材料、人工、时间等)去完成确定的任务或目标;企业在一定的资源条件限制下,如何组织安排生产获得最好的经济效益(如产品量最多、利润最大)。
第一章线性规划,第一节线性规划的基本概念第二节线性规划的标准形式和解的性质第三节单纯形法第四节人工变量法第五节线性规划应用举例,第一节线性规划的基本概念,1.1线性规划数学模型(MathematicalModelofLinearProgramming),【例1.1】最优生产计划问题。
某企业在计划期内计划生产甲、乙、丙三种产品。
这些产品分别需要要在设备A、B上加工,需要消耗材料C、D,按工艺资料规定,单件产品在不同设备上加工及所需要的资源如表1.1所示。
已知在计划期内设备的加工能力各为200台时,可供材料分别为360、300公斤;每生产一件甲、乙、丙三种产品,企业可获得利润分别为40、30、50元,假定市场需求无限制。
企业决策者应如何安排生产计划,使企业在计划期内总的利润收入最大?
1.1.1应用模型举例,表1.1产品资源消耗,【解】设x1、x2、x3分别为甲、乙、丙三种产品的产量数学模型为:
最优解X=(50,30,10);Z=3400,目标函数,资源约束,线性规划的数学模型由决策变量Decisionvariables目标函数Objectivefunction约束条件Constraints构成。
称为三个要素。
其特征是:
1解决问题的目标函数是多个决策变量的线性函数,通常是求最大值或最小值;2解决问题的约束条件是一组多个决策变量的线性不等式或等式。
怎样辨别一个模型是线性规划模型?
【例1.2】某商场决定:
营业员每周连续工作5天后连续休息2天,轮流休息。
根据统计,商场每天至少需要的营业员如表1.2所示。
表1.2营业员需要量统计表,商场人力资源部应如何安排每天的上班人数,使商场总的营业员最少。
【解】设xj(j=1,2,7)为休息2天后星期一到星期日开始上班的营业员,则这个问题的线性规划模型为,目标函数:
总人数最少,约束条件:
上班人数大于每天需要人数,最优解:
Z617(人),【例1.3】合理用料问题。
某汽车需要用甲、乙、丙三种规格的轴各一根,这些轴的规格分别是1.5,1,0.7(m),这些轴需要用同一种圆钢来做,圆钢长度为4m。
现在要制造1000辆汽车,最少要用多少圆钢来生产这些轴?
【解】这是个条材下料问题,设切口宽度为零。
设一根圆钢切割成甲、乙、丙三种轴的根数分别为y1,y2,y3,则切割方式可用不等式1.5y1+y2+0.7y34表示,求这个不等式关于y1,y2,y3的非负整数解。
象这样的非负整数解共有10组,也就是有10种下料方式,如表1.3所示。
表13下料方案,设xj(j=1,2,10)为第j种下料方案所用圆钢的根数。
则用料最少数学模型为:
求下料方案时应注意,余料不能超过最短毛坯的长度;最好将毛坯长度按降的次序排列,即先切割长度最长的毛坯,再切割次长的,最后切割最短的,不能遗漏了方案。
如果方案较多,用计算机编程排方案,去掉余料较长的方案,进行初选。
Z812.5,最优解:
【例1.4】配料问题。
某钢铁公司生产一种合金,要求的成分规格是:
锡不少于28%,锌不多于15%,铅恰好10%,镍要界于35%55%之间,不允许有其他成分。
钢铁公司拟从五种不同级别的矿石中进行冶炼,每种矿物的成分含量和价格如表1.4所示。
矿石杂质在治炼过程中废弃,现要求每吨合金成本最低的矿物数量。
假设矿石在冶炼过程中,合金含量没有发生变化。
表1.4矿石的金属含量,解:
设xj(j=1,2,5)是第j种矿石数量,得到下列线性规划模型,注意,矿石在实际冶炼时金属含量会发生变化,建模时应将这种变化考虑进去,有可能是非线性关系。
配料问题也称配方问题、营养问题或混合问题,在许多行业生产中都能遇到。
最优解:
Z=347.5,第五年:
(x7/2+x9)=x8+2x5,第一年:
x1+x2=200(万元),第二年:
(x1/2+x3)+x4=x2,第三年(x3/2+x5)+x6=x4+2x1,第四年:
(x5/2+x7)+x8=x6+2x3,到第六年实有资金总额为x9+2x7,整理后得到下列线性规划模型,【解】设x1:
第一年的投资;x2:
第一年的保留资金x3:
第二年新的投资;x4:
第二年的保留资金x5:
第三年新的投资;x6:
第三年的保留资金x7:
第四年新的投资x8:
第四年的保留资金x9:
第五年的保留资金,【例1.5】投资问题。
某投资公司在第一年有200万元资金,每年都有如下的投资方案可供考虑采纳:
“假使第一年投入一笔资金,第二年又继续投入此资金的50%,那么到第三年就可回收第一年投入资金的一倍金额”。
投资公司决定最优的投资策略使第六年所掌握的资金最多。
最优解:
Z416.26万元,x1:
第一年的投资;x2:
第一年的保留资金x3:
第二年新的投资;x4:
第二年的保留资金x5:
第三年新的投资;x6:
第三年的保留资金x7:
第四年新的投资x8:
第四年的保留资金x9:
第五年的保留资金,【例1.6】均衡配套生产问题。
某产品由2件甲、3件乙零件组装而成。
两种零件必须经过设备A、B上加工,每件甲零件在A、B上的加工时间分别为5分钟和9分钟,每件乙零件在A、B上的加工时间分别为4分钟和10分钟。
现有2台设备A和3台设备B,每天可供加工时间为8小时。
为了保持两种设备均衡负荷生产,要求一种设备每天的加工总时间不超过另一种设备总时间1小时。
怎样安排设备的加工时间使每天产品的产量最大。
【解】设x1、x2为每天加工甲、乙两种零件的件数,则产品的产量是,设备A、B每天加工工时的约束为,要求一种设备每台每天的加工时间不超过另一种设备1小时的约束为,目标函数线性化。
产品的产量y等价于,整理得到线性规划模型,约束线性化。
将绝对值约束写成两个不等式,【例1.7】(饼干生产问题)某厂生产两类饼干,需搅拌机A1,成形机A2,烘箱A3三种设备,每天的所需机时及机时限制,利润指标如下表,问如何制订生产计划,可使获得最高利润?
【解】设x1、x2为每天生产、两种饼干的产量(单位:
吨),则目标函数是,约束条件有:
搅拌机约束,成形机约束,烘箱约束,非负约束,本问题的数学模型,【例1.8】(运输问题)总公司收到上海B1,青岛B2,西安B3三家商场的电机订单,需求分别为100台,80台,90-120台,现有北京A1,武汉A2二个仓库,库存分别为200台,150台,所需运费如下表,问如何调运电机,可使总运费最少?
【解】设xij为从仓库Ai调到商场Bj的电机数量(i=1,2,j=1,2,3),则目标函数是,库存约束,需求约束,非负约束,问题的数学模型,小结:
建立线性规划数学模型建立数学模型是学习线性规划的第一步也是关键的一步。
建立正确的数学模型要掌握3个要素:
研究的问题是求什么,即设置决策变量;问题要达到的目标是什么,即建立目标函数,目标函数一定是决策变量的线性函数并且求最大值或求最小值;限制达到目标的条件是什么,即建立约束条件。
线性规划的一般形式为:
变量x1,x2,xn称为决策变量,目标函数中变量系数cj,称为价值系数,bi称为右端常数,约束条件(1-3)称为非负约束,(1-2)称为技术约束,系数aij称为技术系数。
满足全部约束条件的变量值(x1,xn)称为可行解,可行解的集合称为可行域,记为R;使目标函数取得最大(最小)值的可行解(x1,xn)称为最优解。
(1-3),(1-2),(1-1),采用求和符号,线性规划的一般形式可以简写为:
用向量形式可表示为:
用矩阵和向量形式表示为:
式中:
X=(x1,x2,xn)TC=(c1,c2,cn)b=(b1,b2,bm)TA=(aij)mnPj=(a1j,a2j,amj)T,二、图解法,当决策变量个数n=2时,LP问题可以通过在平面上作图的方法求解,称为图解法。
图解法求解的目的:
1.判别线性规划问题的求解结局。
2.在存在最优解的条件下,把问题的最优解找出来。
【例1-4】求下列问题的最优解。
(1)确定问题的可行域R。
可行域R是凸多角形OQ1Q2Q3Q4,
(2)分析目标函数Z的等值线平行移动与Z值的关系,确定最优解的位置。
当z取定值时,方程z=2x1+5x2或x2=2/5x1+z/5表示一条斜率为2/5的直线l,称为z的等值线,它在x2轴上的截距为z/5。
当l向右上方平行移动且保持与R有共同部分时,z值不断上升,由于l的斜率为2/5,因此当l向右上方平移的过程中,与R最后的公共点是Q3,z在Q3达到最大值。
(3)计算最优解。
点Q3是直线l1与l3的交点,它的坐标由方程组,决定,从中解得x1=2,x2=3。
这就是问题的最优解,相应的目标函数值z=2253=19。
最优产量计划是P,Q分别生产2个与3个单位,最大产值为19万元。
这时原料A与C用完,B剩余4吨。
线性规划问题求解的几种可能结局:
1.唯一最优解:
如上例。
2.无穷多最优解:
如Z换成maxZ=2X1+4X2,,此时最优解在线段Q2Q3上达到,有无穷多最优解。
已求得Q3的坐标为(2,3);Q2坐标由方程组,决定,从中解得x1=3,x2=5/2。
设,线段Q2Q3上的点可用X1+
(1)X2(01)表示。
因此,X1+
(1)X2(01)是问题的全部最优解。
3.无界解,如约束条件只保留第3个,即4X212,这时可行域无界,Z值可无限上升,无最优解,简称无界解,即有可行解,但目标函数值无解。
产生原因:
是由于在建立实际问题的数学模型中遗漏了某些必要的资源约束条件。
4.无解或无可行解,可行域是空集,问题无可行解,当然更无最优解。
图解法得到的启示,1.求解线性规划问题时,解的情况有:
唯一最优解、无穷多最优解、无界解和无可行解。
2.若线性规划问题的可行域存在,则可行域是一凸集。
3.若线性规划问题的最优解存在,则最优解一定在某个顶点可达到。
4.解题思路是:
先找出凸集的任一顶点,计算Z值,比较相邻顶点Z值,如大,转到相邻顶点,一直到找出使Z值最大的顶点为止。
第二节线性规划的标准形式和解的性质,一、LP的标准形式,称为线性规划问题的标准形式(其中右端常数b1,b2,bm0)。
线性规划标准形式的特点:
1.技术约束条件全部是等式约束2.目标函数限定求最大值,变换一般LP为标准形式的方法:
(1)如果原问题目标函数求极小值:
令z1=z,转化为求。
(2)若某个右端常数bi0,则以1乘该约束两端。
(3)若某约束为“”型的不等式约束,则在左端加上一个非负变量,称为松弛变量,使不等式化为等式;若某约束为“”型,则在左端减去一个非负变量,称为剩余变量,或者仍然称为松弛变量,使不等式转化为等式。
(目标函数不变)(4)若某个xj的符号约束为xj0;那么令xj=xj,则xj0;若某个xj无符号限制,令xj=xjxj,其中xj0,xj0。
(目标函数变),例:
把LP问题,化为标准形式在三个技术约束中,分别加入松弛变量x3,x4,x5,问题化为标准形式:
化为标准形式,【例1-9】把LP问题,二、LP的基可行解的概念对于标准形式的线性规划,利用向量矩阵记号,令X=(x1,x2,xn)T,C=(c1,c2,cn),b=(b1,b2,bm)T,A=(aij)mn。
X,C,b分别称为决策变量向量,价值向量,资源向量(右端常数向量),A称为系数矩阵。
Pj=(a1j,a2j,amj)T是xj的系数列向量,它是A的第j列,A=(P1,P2,Pn)。
利用这些记号,标准形线性规划可表示为:
或者写成:
设系数矩阵A的秩是m,即A的m个行向量是线性无关的。
若B是A的m阶满秩子阵,称B为问题的一个基。
设B=(,),称对应的变量,为基变量,其它的变量称为非基变量。
令非基变量等于0,从方程组可以唯一解出基变量的值,从而得到方程组的一个解,称为基本解;如果它的各个分量非负,即它同时又是可行解,则称之为基可行解,对应的基称为可行基。
可行解是约束方程组的解并且满足非负条件;基本解是约束方程组具有特定性质的解,它至多有m个非0分量,但未必满足非负性。
基可行解同时具有两者的性质。
【例】,它的系数矩阵为:
A的子矩阵(P3,P4,P5)正好是单位矩阵,这种形式的方程组称为典式,或称为对x3,x4,x5的解出形式。
以(P3,P4,P5)为基,令非基变量x1=x2=0,则基变量正好等于右端常数值,得到基可行解X=(0,0,8,20,12)T。
所有基本解见表1-4,三、LP解的性质,定理1线性规划的可行域R是凸集。
定理2X是线性规划基可行解的充分必要条件是X是可行域的极点(顶点)。
定理3线性规划如果有可行解,则一定有基可行解;如果有最优解,则一定有基可行解是最优解。
基可行解至多有个,第三节单纯形法(重点),一、单纯形法的解题思路,【例】,约束方程组已经是对于x3,x4,x5的解出形式,以它们作为第一组(初始)基变量,得基可行解X1=(0,0,8,20,12)T,目标函数值z1=0。
(1),从目标函数z=2x1+5x2来看,如果x1或x2成为基变量(简称入基),变成正值,则z值将会上升。
由于x2系数更大,引入x2更有利于z的上升,故首先选择x2入基,x1仍然保持是非基变量。
此时约束方程组实际成为:
可知x2min8/2,20/2,12/4=3这时x5=0,因此,x5退出基,成为非基变量。
把约束方程组
(1)转化为对新基变量x2,x3,x4的解出形式:
从中可得基可行解X2=(0,3,2,14,0)T,相应z2=53=15,函数值上升了15个单位。
(2),由
(2)第三式得到x2=3x5,代入z的表达式,得到z=2x1+5x2=2x1+5(3x5)=2x1x5+15x1的系数为正,故引入x1,x5保持为0由知x1min2/1,14/5,=2取x1=2,则x3=0,x3退出基。
然后把方程组
(2)变换为对x1,x2,x4的解出形式:
(3),新的基可行解X3=(2,3,0,4,0)T,相应z值z3=22+53=19,由(3)的第一式得到x1=2x3+x5代入
(2)中。
z=2(2x3+x5)x5+15=2x3x5+19此式表明z19,而当X=X3时,z=19,因此X3是问题最优解,z的最优值是19万元。
总结:
单纯形法是一种迭代算法,每步迭代包括下列环节:
首先判定当前基可行解是否最优,若是,则结束;否则,先确定换入变量,再确定换出变量,最后把方程组转化为对新基变量的解出形式,得到新的基可行解。
二、单纯形法要点和单纯形表,1.检验数的意义和计算公式,假定所有b1,bm0。
显然问题有基可行解X1=(b1,b2,bm,0,0)T,相应目标函数值。
i=(1,2,m),基变量的检验数永远为0。
非基变量xj的检验数j是引入xj一个单位时目标函数z的改变量,只有j0时,xj为入基变量。
2.单纯形表,表1-5,总结,从表中可以直接读出基可行解X:
xi=bi(i=1,m),其它xj=0;相应目标函数值,是CB列与b列元素乘积之和;每个变量xj(包括基变量在内)的检验数j,等于cj减去CB列元素与表中xj的系数列向量元素乘积之和。
单纯形法的全部分析和计算过程,可以比较方便地在单纯形表中完成。
3.单纯形法的基本法则,法则1最优性判定法则若对基可行解X1,所有检验数j0(求最大值时),则X1为最优解。
法则2入基变量确定法则(最大价值系数法则)设,则xk为换入变量。
法则3出基变量确定法则(最小比值法则)设xk为换入变量,并设则最小比值所在行的原基变量xl为换出变量。
法则4换基迭代运算法则对方程组的增广矩阵实施行的初等变换,使主元alk化为1,主元列其它元素化为0。
具体地说,第l行乘以1/alk,并将第l行的aik/alk倍加到第i行上去,i=1,2,m,il。
可将这些重要结论的计算设计成如下一个简单的表格,即单纯形表来完成:
例1、试利用单纯形表线性规划的最优解解:
得初始的单纯形表:
初始基本可行解,Z=-1,,12210,8,x4,-1,30400,-1,Z,34101,7,x5,1,x1x2x3x4x5,b,XB,CB,523-11,C,换入变量,换出变量,为主元进行旋转变换,基本可行解,Z=15,,1/2111/20,4,x3,3,1-40-20,15,Z,5/230-1/21,3,x5,1,x1x2x3x4x5,b,XB,CB,523-11,C,12210,8,x4,-1,30400,-1,Z,34101,7,x5,1,x1x2x3x4x5,b,XB,CB,523-11,C,8/2,7/1,最优解最优值,换入变量,换出变量,/为主元进行旋转变换,4/1/2,1/2111/20,4,x3,3,1-40-20,15,Z,3/5/2,5/230-1/21,3,x5,1,x1x2x3x4x5,b,XB,CB,523-11,C,02/513/5-1/5,17/5,x3,3,0-26/50-9/5-2/5,81/5,Z,16/50-1/52/5,6/5,x1,5,x1x2x3x4x5,b,XB,CB,523-11,C,三、关于单纯形法的补充说明,1.无穷多最优解与唯一最优解的判别法则若对某可行解X1,
(1)所有检验数j0,且有一个非基变量xk的检验数等于0,则问题有无穷多最优解;
(2)所有非基变量的检验数j0,则问题有唯一最优解。
2.无最优解(无界解)的判定,若对基可行解X1,存在非基变量xk的检验数k0,但aik0,i=1,2,m即xk的系数列向量无正分量,则问题无最优解。
如上例中,,3.求minz的情况,这时可以有两种处理方式:
一种方式是令z1=z,转化为求maxz1,另一种是直接计算。
最优性检验条件改为:
所有j0;换入变量确定法则改为:
如果则xk为换入变量。
单纯形法的其它要点完全无须改变。
例一求下列LP问题的最优解,例二求下列LP问题的最优解,例三求下列LP问题的最优解,第四节初始可行基的求法人工变量法,大M法首先将线性规划问题化为标准型。
如果约束方程组中包含有一个单位矩阵I,那么已经得到了一个初始可行基。
否则在约束方程组的左边加上若干个非负的人工变量,使人工变量对应的系数列向量与其它变量的系数列向量共同构成一个单位矩阵。
以单位矩阵为初始基,即可求得一个初始的基本可行解。
为了求得原问题的初始基本可行解,必须尽快通过迭代过程把人工变量从基变量中替换出来成为非基变量。
为此可以在目标函数中赋予人工变量一个绝对值很大的负系数-。
这样只要基变量中还存在人工变量,目标函数就不可能实现极大化。
以后的计算与单纯形表解法相同,只需认定是一个很大的正数即可。
假如在单纯形最优表的基变量中还包含人工变量,则说明原问题无可行解。
否则最优解中剔除人工变量的剩余部分即为原问题的初始基本可行解。
例2、用大M法求解下面的线性规划问题:
解:
首先将原问题化为标准型添加人工变量,并在目标函数中分别赋予-,-,01-1/2-1/201/21/2,3/2,X2,2,10-1/21/201/2-1/2,1/2,X1,-1,-,-110-1001,1,X2,2,1/2,20-1101-1,1,X6,-M,1/1,-110-1001,1,X7,-M,2/1,11-10010,2,X6,-M,001/23/20-1/2-M-3/2-M,5/2,Z,001/21/21-1/2-1/2,3/2,X5,0,1+2M0-M2+M00-2-2M,2-M,Z,2/1,100110-1,2,X5,0,-12+2M-M-M000,-3M,Z,3/1,0100100,3,X5,0,X1x2x3x4x5x6x7,b,XB,CB,-12000-M-M,C,0100100,3,X2,2,100110-1,2,X4,0,11-10010,2,X2,2,20-1101-1,1,X4,0,-,01-1/2-1/201/21/2,3/2,X2,2,1/2/1/2,10-1/21/201/2-1/2,1/2,X1,-1,-1000-2-M-M,6,Z,-10101-10,1,X3,0,-30200-2-M-M,4,Z,-10101-10,1,X5,0,001/23/20-1/2-M-3/2-M,5/2,Z,3/2/1/2,001/21/21-1/2-1/2,3/2,X5,0,X1x2x3x4x5x6x7,b,XB,CB,-12000-M-M,C,最优解最优值,M是个很大的正数,因为是对目标函数实现最大化,因此人工变量必须从基变量中迅速换出去,否则目标函数不可能实现最大化,两阶段法,两阶段法引入人工变量的目的和原则与大M法相同,所不同的是处理人工变量的方法。
两阶段法的步骤:
求解一个辅助线性规划。
目标函数取所有人工变量之和,并取极小化;约束条件为原问题中引入人工变量后包含一个单位矩阵的标准型的约束条件。
如果辅助线性规划存在一个基本可行解,使目标函数的最小值等于零,则所有人工变量都已经“离基”。
表明原问题已经得了一个初始的基本可行解,可转入第二阶段继续计算;否则说明原问题没有可行解,可停止计算。
求原问题的最优解。
在第一阶段已求得原问题的一个初始基本可行解的基础上,继续用单纯形法求原问题的最优解,例5、用两阶段法求解下面的线性规划问题。
解:
首先将问题化为标准型添加人工变量x6,x7,并建立辅助线性规划如下:
由于辅助线性规划的目标函数是极小化,因此最优解的判别准则应为:
01-1/2-1/201/21/2,3/2,X2,0,10-1/21/201/2-1/2,1/2,X1,0,-,-110-1001,1,X2,0,1/2,20-1101-1,1,X6,1,1/1,-110-1001,1,X7,1,2/1,11-10010,2,X6,1,0000011,0,W,001/21/21-1/2-1/2,3/2,X5,0,-201-1002,1,W,2/1,100110-1,2,X5,0,0-211000,3,W,3/1,0100100,3,X5,0,x1x2x3x4x5x6x7,b,XB,CB,0000011,C,辅助规划所有检验数:
原问题已得一个初始基本可行解,,由上表可知,通过若干次旋转变换,原问题的约束方程组已变换成包含一个单位矩阵的约束方程组该约束方程组可作为第二阶段初始约束方程组,将目标函数则还原成原问题的目标函数,可继续利用单纯形表求解。
-1000-2,6,Z,1001101001-10101,231,X4X2X3,020,-30200,4,Z,20-11
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 线性规划