运筹学线性规划和单纯形法.ppt
《运筹学线性规划和单纯形法.ppt》由会员分享,可在线阅读,更多相关《运筹学线性规划和单纯形法.ppt(143页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、运筹学运筹学 第一章第一章线性规划及单纯形法线性规划及单纯形法Linear Programming and Simplex Method1 本章内容提要w线性规划问题及其数学模型w线性规划解的概念w单纯形法原理及算法步骤w线性规划应用建模2如何合理地利用如何合理地利用有限的人、财、物有限的人、财、物等资源,得到最等资源,得到最好的经济效果好的经济效果?1.1 1.1 问题的提出问题的提出线性规划是以数学为工具,研究在一定的人、财、物等资源条件下,用最少的资源耗费,取得最大的经济效果。1.线性规划问题及数学模型线性规划问题及数学模型3 例1.1:某工厂拥有A、B、C三种类型的设备,生产甲、乙两种
2、产品。每件产品在生产中需要占用的设备机时数,每件产品可以获得的利润以及三种设备可利用的时数如下表所示:问题:工厂应如何安排生产可获得最大的总利润?产品甲产品乙设备能力(h)设备A3 32 26565设备B2 21 14040设备C0 03 37575利润(元/件)15001500250025004 解:设变量xi为第i种(甲、乙)产品的生产件数(i1,2)。根据题意,我们知道两种产品的生产受到设备能力(机时数)的限制。对设备A,两种产品生产所占用的机时数不能超过65,于是我们可以得到不等式:3 x1+2x265;对设备B,两种产品生产所占用的机时数不能超过40,于是我们可以得到不等式:2x1+
3、x240;5 对设备C,两种产品生产所占用的机时数不能超过75,于是我们可以得到不等式:3x275;另外,产品数不可能为负,即 x1,x20。同时,我们有一个追求目标,即获取最大利润。于是可写出目标函数z为相应的生产计划可以获得的总利润:z=1500 x1+2500 x2。综合上述讨论,在加工时间以及利润与产品产量成线性关系的假设下,把目标函数和约束条件放在一起,可以建立如下的线性规划模型:6目标函数maxz=1500 x1+2500 x2约束条件s.t.3x1+2x2652x1+x2403x275x1,x2 0 这是一个典型的利润最大化的生产计划问 题。其 中,“max”是 英 文 单 词“
4、maximize”的缩写,含义为“最大化”;“s.t.”是“subjectto”的缩写,表示“满足于”。因此,上述模型的含义是:在给定条件限制下,求使目标函数z达到最大的x1,x2的取值。7营养配餐问题假定一个成年人每天需要从食物中获得3000千卡的热量、55克蛋白质和800毫克的钙。如果市场上只有四种食品可供选择,它们每千克所含的热量和营养成分和市场价格见下表。问如何选择才能在满足营养的前提下使购买食品的费用最小?8各种食物的营养成分表9解:设xj为第j种食品每天的购入量,则配餐问题的线性规划模型为:min S=14xmin S=14x1 1+6x+6x2 2+3x+3x3 3+2x+2x4
5、 4 s.t.1000 xs.t.1000 x1 1+800 x+800 x2 2+900 x+900 x3 3+200 x+200 x4 4 3000 3000 50 x 50 x1 1+60 x+60 x2 2+20 x+20 x3 3+10 x+10 x4 4 55 55 400 x 400 x1 1+200 x+200 x2 2+300 x+300 x3 3+500 x+500 x4 4 800 800 x x1 1,x x2 2,x x3 3,x x4 4 0 010线性规划数学模型的构成三要素决策变量决策变量表示某种重要的可变因素,变量的一组数据代表一个解决的方案或措施,用x1,x
6、2,xn表示目标函数目标函数决策变量的函数,目标可以是最大化或最小化约束条件约束条件对决策变量取值的限制条件,由决策变量x1,x2,xn的不等式组或方程组构成11一般形式 max(min)z=c1x1+c2x2+cnxn Subjectto a11 x1+a12 x2+a1n xn (=,)b1a21 x1+a22 x2+a2n xn (=,)b2.am1 x1+am2x2+amn xn(=,)bm x1,x2,xn01213标准形式maxz=c1x1+c2x2+cnxn Subjecttoa11x1+a12x2+a1n xn =b1a21x1+a22x2+a2n xn =b2am1x1+am
7、2x2+amn xn=bm x1,x2,xn0其中bi0,i=1,2,m14标准形式 15标准形式:用向量和矩阵表述 16 可以看出,线性规划的标准形式有如下四个特点:目标最大化、约束为等式、决策变量均非负、右端项非负。对于各种非标准形式的线性规划问题,我们总可以通过以下变换,将其转化为标准形式。171.极小化目标函数的问题:设目标函数为 minf=c1x1+c2x2+cnxn则可以令z-f,该极小化问题与下面的极大化问题有相同的最优解,即 maxz=-c1x1-c2x2-cnxn 但必须注意,尽管以上两个问题的最优解相同,但他们最优解的目标函数值却相差一个符号,即 minf-maxz182、
8、约束条件不是等式的问题:设约束条件为 ai1 x1+ai2 x2+ain xnbi可以引进一个新的变量xn+1,使它等于约束右边与左边之差 xn+1=bi(ai1 x1+ai2x2+ain xn)显然,xn+1也具有非负约束(xn+10),这时新的约束条件成为 ai1 x1+ai2x2+ain xn+xn+1=bi19当约束条件为 ai1 x1+ai2 x2+ain xnbi 时,类似地令 xn+1=(ai1 x1+ai2 x2+ain xn)-bi 显然有 xn+10,这时新的约束条件成为 ai1 x1+ai2 x2+ain xn-xn+1=bi为了使约束由不等式成为等式而引进的变量xn+1
9、称为“松弛变量”,后一种情况也称为“剩余变量”。203.变量无符号限制的问题:在标准形式中,必须每一个变量均有非负约束。当某一个变量xj没有非负约束时,可以令 xj=xj-xj”其中 xj 0,xj”0即用两个非负变量之差来表示一个无符号限制的变量。当然xj的符号取决于xj和xj”的大小。214.右端项有负值的问题:在标准形式中,要求右端项必须每一个分量非负。当某一个右端项系数为负时,如 bi m),秩为m。B=(P1,P2,Pm)是A中m阶非奇异子矩阵,则称B是线性规划问题的一个基矩阵基矩阵,简称基基。B中的列向量Pj 称为基向量基向量,与基向量Pj对应的变量xj称为基变量基变量,其它变量称
10、为非基变量非基变量。令非基变量为0,则由Ax=b可求出一个解,这个解x称为基解基解。满足非负条件的基解称为基可行解基可行解。48maxz=1500 x1+2500 x2s.t.3x1+2x2+x3=652x1+x2+x4=403x2+x5=75x1,x2,x3,x4,x50例1.7:把例1.1化为标准型:49 32100A=P1,P2,P3,P4,P5 =2101003001A矩阵包含以下10个33的子矩阵:B1=P1,P2,P3B2 =P1,P2,P4B3=P1,P2,P5B4 =P1,P3,P4B5=P1,P3,P5B6 =P1,P4,P5B7=P2,P3,P4B8 =P2,P3,P5B9
11、=P2,P4,P5B10=P3,P4,P550 其中B4=0,因而B4不是该线性规划问题的基。其余均为非奇异方阵,因此该问题共有9个基。对于基B3=P1,P2,P5,在等式约束中令非基变量 x3=0,x4=0,解线性方程组:3x1+2x2+0 x5=652x1+x2+0 x5=400 x1+3x2+x5=75 得到x1=15,x2=10,x5=45,对应的基解为基可行解:x3=(x1,x2,x3,x4,x5)T=(15,10,0,0,45)T,对应的目标函数值z3=47500。故基B3是一个可行基。51 类似可得到 x2=(5,25,0,5,0)T (对应B2,z2=70000)x5=(20,
12、0,5,0,75)T (对应B5,z5=30000)x7=(0,25,15,15,0)T(对应B7,z7=62500)x10=(0,0,65,40,75)T(对应B10,z10=0)是基可行解,x2是最优解;而 x1=(7.5,25,-7.5,0,0)T (对应B1)x6=(65/3,0,0,-10/3,75)T(对应B6)x8=(0,40,-15,0,-45)T (对应B8)x9=(0,32.5,0,7.5,-22.5)T(对应B9)是基解但不可行。52可行解基解基可行解可行解,基可行解,基解的关系533.2.3.2.凸集与顶点凸集与顶点凸集:如果在集合C中任意取两个点x1,x2,其连线上的
13、所有点也都在集合C中,则称集合C为凸集。用数学解析式表达为:对n维欧式空间中的一个集合C,任意x1,x2C,和实数a,均有 ax1+(1-a)x2C (0a0,那么相应的非基变量xs,它的值从当前值0开始增加时,目标函数值随之增加。这个选定的非基变量xs称为进基变量,转(3)。如果任何一个非基变量的值增加都不能使目标函数值增加,即所有j非正,则当前的基本可行解就是最优解,计算结束;78(3)基可行解的转换在用非基变量表示的基变量的表达式(1-1)中,观察进基变量增加时各基变量变化情况,确定基变量的值在进基变量增加过程中首先减少到0的变量xr,满足,=min bi/ais ais 0=br/ar
14、s (1-2)这个基变量xr称为出基变量。当进基变量的值增加到 时,出基变量xr的值降为0时,可行解就移动到了相邻的基本可行解(顶点),转(4)。(1-2)即所谓的最小检验比规则。79如果进基变量的值增加时,所有基变量的值都不减少,即所有ais 非正,则表示可行域是无界的,且目标函数值随进基变量的增加可以无限增加,此时,不存在有限最优解,计算结束;(4)将进基变量作为新的基变量,出基变量作为新的非基变量,确定新的基、新的基本可行解和新的目标函数值。在新的基变量、非基变量的基础上重复(2)。80表格单纯形法表格单纯形法 设定设定:bi 0 i=1,2,mmaxz=c1 x1+c2 x2+cn x
15、ns.t.a11 x1+a12 x2+a1n xn b1 a21 x1+a22 x2+a2n xn b2 am1 x1+am2 x2+amn xn bm x1,x2,xn 081加入松弛变量加入松弛变量:max z=c1 x1+c2 x2+cn xn s.t.a11 x1+a12 x2+a1n xn+xn+1=b1 a21 x1+a22 x2+a2n xn+xn+2=b2 am1 x1+am2 x2+amn xn+xn+m=bm x1,x2,xn,xn+1,xn+m 082显然,xj=0,j=1,n;xn+i=bi,i=1,m是基本可行解 对应的基是单位矩阵。以下是初始单纯形表:其中:z=i=
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 线性规划 单纯
限制150内