机械优化设计6 线性规划

机械优化设计6线性规划2024/3/232第六章线性规划一.线性规划的基本概念二.求解线性规划的单纯形法三.初始基本可行解2024/3/233

某厂生产甲、乙两种产品，已知：①两种产品分别由两条生产线生产。第一条生产甲，每天最多生产9件，第二条生产乙，每天最多生产7件；②该厂仅有工人24名，生产甲每件用2工日，生产乙每件用3工日；③产品甲、乙的单件利润分别为40元和80元。问工厂如何组织生产才能获得最大利润？一）应用实例§6-1线性规划的基本概念2024/3/234二)线性规划的一般形式s.t.特点:1)为极小化问题;2)约束取等号;3)限定系数非负;4)变量非负.式中，—价值系数；—结构系数

—限定系数2024/3/235将数学模型化为标准型的方法1）将极大化问题化为极小化问题

—松弛变量（开关变量）（两边乘-1）4）将负的限定系数化为正值3）将任意变量化为非负变量2）将不等式约束变为等式约束：—目标函数变号；2024/3/236s.t.化为标准型:2024/3/237四）线性规划的基本性质

1）可行域D为凸集，每个基本可行解对应于D上的一个顶点；

2）只要可行域存在且封闭，则起码有一个基本可行解为最优点；*ⅰ）若最优点所在的边界线与等值线平行，则该边界线上的点均为最优点；

ⅱ）若可行域不封闭，则可能有无界解。

3)最优点可在D的顶点中寻找。2024/3/238§6-2求解线性规划的单纯形法一.基本思路

先取D的一个顶点作为初始点,由此出发朝可使目标函数降低最快的方向依次经过一系列的基本可行解,直至达到最优解.*1)需获得一个初始基本可行解;2)每次只更换一个非基本变量;3)保证下降性和可行性.2024/3/239写成一般形式:最小,x3应为进基变量推论:

若线性规划的一个基本可行解的所有进基判别数均为非负,则该解为最优解.2024/3/2310(2)确定离基变量①原则:考虑可行性(该变量离基后,能使余下的基本变量为非负)②判别数:由于ⅰ)若取(离基),则有应取为正且其值为最小者对应的基本变量离基.(可行)(不可行)ⅱ)若取(离基),则有2024/3/2311ⅱ)推论:若线性规划的的所有离基判别数均为负数时,则问题有无界解.最小,x6

应为离基变量[005/302/30]T*ⅰ)因为,故也必须大于0,否则不满足可行性要求;2024/3/2312进基3.第二次变换顶点去掉了(1)(2)1)确定进基变量(3)(4)2024/3/23132)确定离基变量

离基(1)(2)[008/51/500]T(3)(4)2024/3/23144.第三次变换顶点1)确定进基变量

故为最优点,为最优值:[008/51/500]T2024/3/2315三.用单纯形表求解线性规划例.用初等变换法求解解:增广矩阵:2024/3/2316s.t.离基判别数进基判别数

单纯形法实际上是解一系列的线性方程组,也可用初等变换方法列表求解.但需加入判别数的计算.421235基变量x1x2x3x4x5x63x5112410425x612310155/3X0000045F037-4-11-20-15例12024/3/231742123基变量x1x2x3x4x5x63x51/3-1/3010/312/30.21x31/32/311/305/35X1005/302/30F111/38/37/3-25/3421235基变量x1x2x3x4x5x63x5112410425x612310155/3X0000045F037-4-11-20-152024/3/231842123基变量x1x2x3x4x5x63x51/3-1/3010/312/30.21x31/32/311/305/35X1005/302/30F111/38/37/3-25/34212基变量x1x2x3x4x5x62x41/10-1/10010.21x33/107/10101.6X2001.60.200F223.51.5已获得最优解2024/3/2319-2-300基变量x1x2x3x40x3-1110330x41-4014-1X00034F00-2-3-2-30基变量x1x2x3x4-3x2-1103-30x4-30116-16/3X103016F1-9-5s.t.例2问题有无界解2024/3/2320§6-3初始基本可行解大M法引入一组人工变量,它们在目标函数中的系