机械优化设计6线性规划

2019/8/51第六章线性规划一.线性规划的基本概念二.求解线性规划的单纯形法三.初始基本可行解2019/8/52某厂生产甲、乙两种产品，已知：①两种产品分别由两条生产线生产。第一条生产甲，每天最多生产9件，第二条生产乙，每天最多生产7件；②该厂仅有工人24名，生产甲每件用2工日，生产乙每件用3工日；③产品甲、乙的单件利润分别为40元和80元。问工厂如何组织生产才能获得最大利润？一）应用实例§6-1线性规划的基本概念2019/8/53日利润最大生产能力限制劳动力限制变量非负.,21xx解:设甲、乙两种产品的日产件数分别为0,2432798040)(max212121221xxxxxxRDXxxXFs.t.2019/8/54二)线性规划的一般形式0,...,..................)(min21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxaxcxcxcXFs.t.特点:1)为极小化问题;2)约束取等号;3)限定系数非负;4)变量非负.式中，—价值系数；—结构系数—限定系数jcijaib2019/8/55•将数学模型化为标准型的方法1）将极大化问题化为极小化问题iibXg)()1(若iibXg)()2(若kx—松弛变量///jjjxxx（开关变量）（两边乘-1）4）将负的限定系数化为正值3）将任意变量化为非负变量2）将不等式约束变为等式约束：—目标函数变号；ikibxXg)(ikibxXg)(2019/8/560,...,,2432798040)(min5215214231521xxxxxxxxxxRDXxxXFs.t.化为标准型:2019/8/57三）线性规划的基本概念0,2432798040)(max212121221xxxxxxRDXxxXFs.t.1.线性规划的图解x2x10F=0F*=620(1.5,7)2019/8/582.线性规划的基本概念1）可行解—满足约束条件及非负条件的解。（D内及其边界上的解）2）基本解—使n-m个变量等于0，解约束方程组(共有m个约束方程)所得的解。基本解对应于约束边界的交点.3）基本可行解—可行域中的基本解（即D的顶点）。4）基本变量与非基本变量预先取为零值的n-m个变量为非基本变量，其余m个为基本变量。03xx2x10F=0F*=-620(1.5,7)04x05x01x02x0,...,,2432798040)(min5215214231521xxxxxxxxxxRDXxxXFs.t.2019/8/59四）线性规划的基本性质1）可行域D为凸集，每个基本可行解对应于D上的一个顶点；2）只要可行域存在且封闭，则起码有一个基本可行解为最优点；*ⅰ）若最优点所在的边界线与等值线平行，则该边界线上的点均为最优点；ⅱ）若可行域不封闭，则可能有无界解。3)最优点可在D的顶点中寻找。2019/8/510§6-2求解线性规划的单纯形法一.基本思路先取D的一个顶点作为初始点,由此出发朝可使目标函数降低最快的方向依次经过一系列的基本可行解,直至达到最优解.*1)需获得一个初始基本可行解;2)每次只更换一个非基本变量;3)保证下降性和可行性.2019/8/511二.计算实例6,...,2,1,...053244253224)(min6432154321654321jxxxxxxxxxxxxxxxxxXFjs.t.1.初始基本可行解取x5,x6为基本变量,则有:)0(X[000045]T375543)0(F2019/8/5122.第一次变换顶点(1)选取进基变量①原则:考虑下降性,且下降得最快②判别数:假定x2进基,则有5246252xxxx0206252xxxx取12x,15x26x相应的目标函数变化量:1110325326522xxx12a22a即)(22612522acacc6,...,2,1,...053244253224)(min6432154321654321jxxxxxxxxxxxxxxxxxXFj2019/8/513写成一般形式:miijBijjjjacczc11515432203523111251324151344321最小,x3应为进基变量3推论:若线性规划的一个基本可行解的所有进基判别数均为非负,则该解为最优解.6,...,2,1,...053244253224)(min6432154321654321jxxxxxxxxxxxxxxxxxXFj2019/8/514(2)确定离基变量①原则:考虑可行性(该变量离基后,能使余下的基本变量为非负)②判别数:)35(335)2(224336335xxxxxx由于ⅰ)若取(离基),则有05x0263xx0323553xx)/()/(323223313113xabaxabaijiiab,,...,2,1mi进基变量下标j应取为正且其值为最小者对应的基本变量离基.i6,...,2,1,...053244253224)(min6432154321654321jxxxxxxxxxxxxxxxxxXFj(可行)(不可行)06xⅱ)若取(离基),则有2019/8/515ⅱ)推论:若线性规划的的所有离基判别数均为负数时,则问题有无界解.最小,x6应为离基变量2)1(X[005/302/30]T31132335)1(F*ⅰ)因为,故也必须大于0,否则不满足可行性要求;0,21bb2313,aa6,...,2,1,...053244253224)(min6432154321654321jxxxxxxxxxxxxxxxxxXFj)35(335)2(224336335xxxxxx2019/8/516进基4x3.第二次变换顶点去掉了6x5,...,2,1,...05324423224)(min43215432154321jxxxxxxxxxxxxxxxXFj(1)(2)1)确定进基变量03183103311231231332123223133114421:3)2((3)(4)353132314321xxxx:)1()2()3(3231031315421xxxxmiijBijjacc12019/8/5172)确定离基变量2.0310/32531/3521离基5x(1)(2)4321224)(minxxxxXF323103131353132314214321xxxxxxx)2(X[008/51/500]T251258)2(F:310/)2((3)(4)51101101421xxx:)1()31()3(58107103321xxx353132314321xxxx3231031315421xxxx2019/8/5184.第三次变换顶点1)确定进基变量05.110121071205.310121031421故为最优点,为最优值:)2(X)2(F)2(*XX[008/51/500]T251258)2(*FF51101101421xxx58107103321xxx4321224)(minxxxxXF2019/8/519三.用单纯形表求解线性规划例.用初等变换法求解解:增广矩阵:1125452121xxxx1112545,51030111123011112390135321xx2019/8/5206,...,2,1,...053244253224)(min6432154321654321jxxxxxxxxxxxxxxxxxXFjs.t.离基判别数进基判别数单纯形法实际上是解一系列的线性方程组,也可用初等变换方法列表求解.但需加入判别数的计算.421235基变量x1x2x3x4x5x63x5112410425x612310155/3X0000045F037-4-11-20-15jcBicibij例12019/8/52142123基变量x1x2x3x4x5x63x51/3-1/3010/312/30.21x31/32/311/305/35X1005/302/30F111/38/37/3-25/3jcBicibij421235基变量x1x2x3x4x5x63x5112410425x612310155/3X0000045F037-4-11-20-15jcBicibij2019/8/52242123基变量x1x2x3x4x5x63x51/3-1/3010/312/30.21x31/32/311/305/35X1005/302/30F111/38/37/3-25/3jcBicibij4212基变量x1x2x3x4x5x62x41/10-1/10010.21x33/107/10101.6X2001.60.200F223.51.5jcBicibij已获得最优解2019/8/523-2-300基变量x1x2x3x40x3-1110330x41-4014-1X00034F00-2-3jcBicibij-2-30基变量x1x2x3x4-3x2-1103-30x4-30116-16/3X103016F1-9-5jcBicibij4,...,2,1,...044332)(min42132121jxxxxxxxxxXFjs.t.例2问题有无界解2019/8/524§6-3初始基本可行解(1)大M法引入一组人工变量,它们在目标函数中的系数均是非常大的正数M;(2)两相法引入一组人工变量,在人工变量未完全离基前目标函数为各人工变量之和,当人工变量完全离基后恢复原目标函数。当A内不包含单位矩阵时,需引入由人工变量组成的单位矩阵,以方便获得初始可行解.2019/8/525一.采用大M法获得初始基本可行解543214)(minMxMxxxxXF33342253214321xxxxxxxx,0jx5,...,2,1js.t.采用大M法：3214)(minxxxXF333422321321xxxxxx,0jx3,2,1js.t.原问题：因M是比其他价值系数大得多的正数,且人工变量非负,迭代的结果会使人工变量趋于零,而获得原问题的基本可行解.2019/8/526543214)(minMxMxxxxXF33342253214321xxxxxxxx,0jx5,...,2,1js.t.411MM基变量x1x2x3x4x5Mx42121042Mx53310131X000043F07M4-5M1-4M1-3MjcBicibij表一2019/8/527411MM基变量x1x2x3x4x5Mx42121042Mx53310131X000043F07M4-5M1-4M1-3MjcBicibij411M基变量x1x2x3x4x5Mx40-14/3121.54x1111/3013X110020F14+2M-3