机械优化设计课件 第5章 线性规划

开放 包容 求实 创新机械优化设计第五章 线性规划第五章 线性规划一.线性规划的基本概念二.求解线性规划的单纯形法三三. .初始基本可行解初始基本可行解第五章 线性规划 某厂生产甲、乙两种产品，已知：两种产品分别由两条生产线生产。第一条生产甲，每天最多生产9件，第二条生产乙，每天最多生产7件；该厂仅有工人24名，生产甲每件用2工日，生产乙每件用3工日；产品甲、乙的单件利润分别为40元和80元。问工厂如何组织生产才能获得最大利润？一）应用实例§5-1 线性规划的基本概念日利润最大生产能力限制劳动力限制变量非负解: 设甲、乙两种产品的日产件数分别为s.t.第五章 线性规划§5-1 线性规划的基本概念二)线性规划的一般形式s.t.特点: 1)为极小化问题; 2)约束取等号;3)限定系数非负; 4)变量非负.式中， 价值系数； 结构系数 限定系数第五章 线性规划§5-1 线性规划的基本概念将数学模型化为标准型的方法1）将极大化问题化为极小化问题松弛变量（开关变量）（两边乘-1）4）将负的限定系数化为正值3）将任意变量化为非负变量2）将不等式约束变为等式约束：目标函数变号；第五章 线性规划§5-1 线性规划的基本概念s.t.化为标准型:第五章 线性规划§5-1 线性规划的基本概念三）线性规划的基本概念s.t.1.线性规划的图解x2x10F=0F*=620(1.5,7)第五章 线性规划§5-1 线性规划的基本概念2. 线性规划的基本概念1）可行解满足约束条件及非负条件的解。 （D内及其边界上的解） 2）基本解 使n-m个变量等于0，解约束方程 组(共有m个约束方程)所得的解。 基本解对应于约束边界的交点.x2x10F=0F*=-620(1.5,7)第五章 线性规划§5-1 线性规划的基本概念3）基本可行解可行域中的基本解（即D的顶点）。 4）基本变量与非基本变量基本可行解中取零值的n-m个变量为非基本变量，取正 值为基本变量。s.t.第五章 线性规划§5-1 线性规划的基本概念四）线性规划的基本性质1）可行域D为凸集，每个基本可行解对应于D上的一个顶点 ；2）只要可行域存在且封闭，则起码有一个基本可行解为最 优点；*）若最优点所在的边界线与等值线平行，则该边界线上 的点均为最优点；）若可行域不封闭，则可能有无界解。3)最优点可在D的顶点中寻找。第五章 线性规划§5-1 线性规划的基本概念§5-2 求解线性规划的单纯形法一.基本思路先取D的一个顶点作为初始点,由此出发朝 可使目标函数降低最快的方向依次经过一系 列的基本可行解,直至达到最优解.*1)需获得一个初始基本可行解;2)每次只更换一个非基本变量;3)保证下降性和可行性.第五章 线性规划二.计算实例s.t.1.初始基本可行解取x5,x6 为基本变量, 则有:0 0 0 0 4 5T§5-2 求解线性规划的单纯形法第五章 线性规划2.第一次变换顶点(1)选取进基变量原则: 考虑下降性,且下降得最快判别数:假定x2进基, 则有 取相应的目标函数变化量:即§5-2 求解线性规划的单纯形法第五章 线性规划写成一般形式 :最小,x3 应为进基变量 推论: 若线性规划的一个基本可行解的所有进基判别数均为非负,则该解为最优解.§5-2 求解线性规划的单纯形法第五章 线性规划(2)确定离基变量原则:考虑可行性(该变量离基后,能使余下的基本变量为非负)判别数:由于)若取 (离基),则有 应取 为正且其值为最小者对应的基本变量离基.(可行)(不可行)若取 (离基),则有 §5-2 求解线性规划的单纯形法第五章 线性规划)推论:若线性规划的所有离基判别数均为负数时,则问题有无界解.最小,x6 应为离基变量 0 0 5/3 0 2/3 0T)因为 ,故 也必须大于0, 否则不满足可行性要求;§5-2 求解线性规划的单纯形法第五章 线性规划进基3.第二次变换顶点去掉了(1)(2)1)确定进基变量(3 )(4 )§5-2 求解线性规划的单纯形法第五章 线性规划2)确定离基变量离基(1 ) (2 )0 0 8/5 1/5 0 0T(3)(4)§5-2 求解线性规划的单纯形法第五章 线性规划4. 第三次变换顶点1) 确定进基变量故 为最优点, 为最优值:0 0 8/5 1/5 0 0T§5-2 求解线性规划的单纯形法第五章 线性规划三.用单纯形表求解线性规划例.用初等变换法求解解:增广矩阵:§5-2 求解线性规划的单纯形法第五章 线性规划s.t.离基判别数进基判别数单纯形法实际上是解 一系列的线性方程组,也 可用初等变换方法列表求 解.但需加入判别数的计 算.4 42 21 12 23 35 5基变量基变量x x1 1x x2 2x x3 3x x4 4x x5 5x x6 63 3x x5 51 11 12 24 41 10 04 42 25 5x x6 61 12 23 31 10 01 15 55/35/3X X0 00 00 00 00 04 45 5F F0 03737-4-4-11-11-20-20-15-15例1§5-2 求解线性规划的单纯形法第五章 线性规划4 42 21 12 23 3基变量基变量x x1 1x x2 2x x3 3x x4 4x x5 5x x6 63 3x x5 51/31/3- -1/31/30 010/10/3 31 12/32/30.20.21 1x x3 31/31/32/32/31 11/31/30 05/35/35 5X X1 10 00 05/35/30 02/32/30 0F F1 111/11/3 38/38/37/37/3- -25/25/3 34 42 21 12 23 35 5基变量基变量x x1 1x x2 2x x3 3x x4 4x x5 5x x6 63 3x x5 51 11 12 24 41 10 04 42 25 5x x6 61 12 23 31 10 01 15 55/35/3X X0 00 00 00 00 04 45 5F F0 03737-4-4-11-11-20-20-15-154 42 21 12 23 3基变量基变量x x1 1x x2 2x x3 3x x4 4x x5 5x x6 63 3x x5 51/31/3- -1/31/30 010/10/3 31 12/32/30.20.21 1x x3 31/31/32/32/31 11/31/30 05/35/35 5X X1 10 00 05/35/30 02/32/30 0F F1 111/11/3 38/38/37/37/3- -25/25/3 34 42 21 12 2基变量基变量x x1 1x x2 2x x3 3x x4 4x x5 5x x6 62 2x x4 41/11/10 0- -1/1/ 10100 01 10.20.21 1x x3 33/13/10 07/7/ 10101 10 01.61.6X X2 20 00 01.61.60.20.20 00 0F F2 22 23.53.51.51.5已获得最优解-2-2-3-30 00 0基变量基变量x x1 1x x2 2x x3 3x x4 40 0x x3 3-1-11 11 10 03 33 30 0x x4 41 1-4-40 01 14 4-1-1X X0 00 00 03 34 4F F0 00 0-2-2-3-3-2-2-3-30 0基变量基变量x x1 1x x2 2x x3 3x x4 4-3-3x x2 2-1-11 10 03 3-3-30 0x x4 4-3-30 01 11616- -16/16/3 3X X1 10 03 30 01616F F1 1-9-9-5-5s.t.例2问题有无界解§5-3 初始基本可行解(1) 大M法引入一组人工变量,它们在目标函数中的系数均是 非常大的正数M; (2) 两相法引入一组人工变量,在人工变量未完全离基前目标 函数为各人工变量之和,当人工变量完全离基后恢复 原目标函数。当A内不包含单位矩阵时,需引入由人工变量组 成的单位矩阵,以方便获得初始可行解.第五章 线性规划一.采用大M法获得初始基本可行解s.t.采用大M法：s.t.原问题：因M是比其他价值系数大得多的正数,且人工变量非负,迭代 的结果会使人工变量趋于零,而获得原问题的基本可行解.§5-3 初始基本可行解第五章 线性规划s.t.4 41 11 1MMMM基变量基变量x x1 1x x2 2x x3 3x x4 4x x5 5MMx x4 42 21 12 21 10 04 42 2MMx x5 53 33 31 10 01 13 31 1X X0 00 00 00 04 43 3F F0 07M7M4-5M4-5M1-4M1-4M1-3M1-3M表一§5-3 初始基本可行解第五章 线性规划4 41 11 1MMMM基变量基变量x x1 1x x2 2x x3 3x x4 4x x5 5MMx x4 42 21 12 21 10 04 42 2MMx x5 53 33 31 10 01 13 31 1X X0 00 00 00 04 43 3F F0 07M7M4-5M4-5M1-4M1-4M1-3M1-3M4 41 11 1MM基变量基变量x x1 1x x2 2x x3 3x x4 4x x5 5MMx x4 40 0-1-14/34/31 12 21.51.54 4x x1 11 11 11/31/30 01 13 3X X1 11 10 00 02 20 0F F1 14+2M4+2M-3+M-3+M-4/3-4/3- 4M/34M/3表一表二4 41 11 1基变量基变量x x1 1x x2 2x x3 3x x4 4x x5 51 1x x3 30 0- -3/43/41 11.51.5-2-24 4x x1 11 15/45/40 00.50.50.40.4X X2 20.50.50 01.51.5F F2 23.53.50 0- -13/413/40 0表三初始基本 可行解4 41 11 1MM基变量基变量x x1 1x x2 2x x3 3x x4 4x x5 5MMx x4 40 0-1-14/34/31 12 21.51.54 4x x1 11 11 11/31/30 01 13 3X X1 11 10 00 02 20 0F F1 14+2M4+2M-3+M-3+M-4/3-4/3- 4M/34M/3表二4 41 11 1基变量基变量x x1 1x x2 2x x3 3x x4 4x x5 51 1x x3 30 0- -3/43/41 11.51.5-2-24 4x x1 11 15/45/40 00.50.50.40.4X X2 20.50.50 01.51.5F F2 23.53.50 0- -13/413/40 04 41 11 1基变量基变量x x1 1x x2 2x x3 3x x4 4x x5 51 1x x3 30 01 11.81.81 1x x2 21 10 00.40.4X X3 30 00.40.41.81.8F F3 32.22.2表三表四初始基本 可行解最优解二.采用两相法获得初始基本可行解大M法的M是一个充分大的正数, 有时在计算机上不便处理.s.t.原问题：s.t.相1问题：§5-3 初始基本可行解第五章 线性规划0 00 00 01 11 1基变量基变量x x1 1x x2 2x x3 3x x4 4x x5 51 1x x4 42 21 12 21 10 04 42 21 1x x5 53 33 31 10 01 13 31 1X X 0 00 00 00 04 43 3F F