线性规划ppt课件.pptx

《线性规划ppt课件.pptx》由会员分享，可在线阅读，更多相关《线性规划ppt课件.pptx（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1线性规划线性规划ppt课件课件2 某某某某厂厂厂厂生生生生产产产产甲甲甲甲、乙乙乙乙两两两两种种种种产产产产品品品品，已已已已知知知知：两两两两种种种种产产产产品品品品分分分分别别别别由由由由两两两两条条条条生生生生产产产产线线线线生生生生产产产产。第第第第一一一一条条条条生生生生产产产产甲甲甲甲，每每每每天天天天最最最最多多多多生生生生产产产产9 9 9 9件件件件，第第第第二二二二条条条条生生生生产产产产乙乙乙乙，每每每每天天天天最最最最多多多多生生生生产产产产7 7 7 7件件件件；该该该该厂厂厂厂仅仅仅仅有有有有工工工工人人人人24242424名名名名，生生生生产产产产甲甲甲甲

2、每每每每件件件件用用用用2 2 2 2工工工工日日日日，生生生生产产产产乙乙乙乙每每每每件件件件用用用用3 3 3 3工工工工日日日日；产产产产品品品品甲甲甲甲、乙乙乙乙的的的的单单单单件件件件利利利利润润润润分分分分别别别别为为为为40404040元元元元和和和和80808080元元元元。问问问问工工工工厂厂厂厂如如如如何何何何组组组组织织织织生生生生产产产产才才才才能能能能获获获获得得得得最大利润？最大利润？最大利润？最大利润？一）应用实例一）应用实例一一一一.线性规划的基本概念线性规划的基本概念线性规划的基本概念线性规划的基本概念第1页/共33页3日利润最日利润最大大生产能力限生产能力限

3、制制劳动力限劳动力限制制变量非变量非负负解解:设甲、乙两种产品的日产件数分别为设甲、乙两种产品的日产件数分别为s.t.第2页/共33页4二二二二)线性规划的一般形式线性规划的一般形式线性规划的一般形式线性规划的一般形式s.s.t.t.特点特点:1)1)为极小化问题为极小化问题;2);2)约束取等号约束取等号;3)3)限定系数非负限定系数非负;4);4)变量非负变量非负.式中，式中，价值系数；价值系数；结构系数结构系数 限定系数限定系数第3页/共33页5n n将数学模型化为标准将数学模型化为标准型的方法型的方法1 1 1 1）将极大化问题化为极小化问题）将极大化问题化为极小化问题）将极大化问题化

4、为极小化问题）将极大化问题化为极小化问题 松弛变量松弛变量（开关变量）（开关变量）（两边乘（两边乘-1-1）4 4）将负的限定系数化为正值）将负的限定系数化为正值3 3）将任意变量化为非负变量）将任意变量化为非负变量2 2）将不等式约束变为等式约束：）将不等式约束变为等式约束：目标函数变号；目标函数变号；第4页/共33页6s.t.化为标准型化为标准型:第5页/共33页7三）线性规划的基本概念三）线性规划的基本概念s.t.1.1.线性规划的图解线性规划的图解x2x10F=0F*=620(1.5,7)第6页/共33页82.2.线性规划的基本概念线性规划的基本概念1 1）可行解）可行解满足约束条件及

5、非负条件的解。满足约束条件及非负条件的解。（D D内及其边界上的解）内及其边界上的解）2 2）基本解）基本解使使n-mn-m个变量等于个变量等于0 0，解约束方程，解约束方程组组(共有共有m m个约束方程个约束方程)所得的解。所得的解。基本解对应于约束边界的交点基本解对应于约束边界的交点.3 3）基本可行解）基本可行解可行域中的基本解（即可行域中的基本解（即D D的顶点）。的顶点）。4 4）基本变量与非基本变量）基本变量与非基本变量 预先取为零值的预先取为零值的n-mn-m个变量为非个变量为非基本变量，其余基本变量，其余m m个为基本变量。个为基本变量。x2x10F=0F*=-620(1.5,

6、7)s.t.第7页/共33页9四）线性规划的基本性质四）线性规划的基本性质 1 1 1 1）可行域）可行域）可行域）可行域D D D D为凸集，每个基本可行解对应于为凸集，每个基本可行解对应于为凸集，每个基本可行解对应于为凸集，每个基本可行解对应于D D D D上的上的上的上的一个顶点；一个顶点；一个顶点；一个顶点；2 2 2 2）只要可行域存在且封闭，则起码有一个基本可）只要可行域存在且封闭，则起码有一个基本可）只要可行域存在且封闭，则起码有一个基本可）只要可行域存在且封闭，则起码有一个基本可行解为最优点；行解为最优点；行解为最优点；行解为最优点；*）若最优点所在的边界线与等值线平行，则该）

7、若最优点所在的边界线与等值线平行，则该）若最优点所在的边界线与等值线平行，则该）若最优点所在的边界线与等值线平行，则该边界线上的点均为最优点；边界线上的点均为最优点；边界线上的点均为最优点；边界线上的点均为最优点；）若可行域不封闭，则可能有无界解。）若可行域不封闭，则可能有无界解。）若可行域不封闭，则可能有无界解。）若可行域不封闭，则可能有无界解。3)3)3)3)最优点可在最优点可在最优点可在最优点可在D D D D的顶点中寻找。的顶点中寻找。的顶点中寻找。的顶点中寻找。第8页/共33页10二二二二.求解线性规划的单纯形法求解线性规划的单纯形法求解线性规划的单纯形法求解线性规划的单纯形法一一)

8、基本思路基本思路 先先取取D D的的一一个个顶顶点点作作为为初初始始点点,由由此此出出发发朝朝可可使使目目标标函函数数降降低低最最快快的的方方向向依依次次经经过过一一系系列的基本可行解列的基本可行解,直至达到最优解直至达到最优解.*1)*1)需获得一个初始基本可行解需获得一个初始基本可行解;2)2)每次只更换一个非基本变量每次只更换一个非基本变量;3)3)保证下降性和可行性保证下降性和可行性.第9页/共33页11二二)计算实例计算实例s.t.s.t.1.1.初始基本可行解初始基本可行解取取x x5 5,x,x6 6 为基本变量为基本变量,则有则有:0 0 0 0 4 5T第10页/共33页12

9、2.2.第一次变换顶点第一次变换顶点(1)(1)选取进基变量选取进基变量原则原则:考虑下降性考虑下降性,且下降得最快且下降得最快判别数判别数:假定假定x x2 2进基进基,则有则有取取相应的目标函数变化量相应的目标函数变化量:即即第11页/共33页13写成一般形写成一般形式式:最小最小,x,x3 3 应为进基变应为进基变量量推论推论:若若线线性性规规划划的的一一个个基基本本可可行行解解的的所所有有进进基基判判别别数数均均为非负为非负,则该解为最优解则该解为最优解.第12页/共33页14(2)(2)确定离基变量确定离基变量原则原则:考虑可行性考虑可行性(该变量离基后该变量离基后,能使余下的基本变

10、量为非负能使余下的基本变量为非负)判别数判别数:由于由于)若取若取 (离基离基),),则有则有 应取应取 为正且其值为最小者对应的基本变量离基为正且其值为最小者对应的基本变量离基.(可行可行)(不可行不可行)若取若取 (离基离基),),则有则有 第13页/共33页15)推推论论:若若线线性性规规划划的的的的所所有有离离基基判别数均为负数时判别数均为负数时,则问题有无界解则问题有无界解.最小最小,x,x6 6 应为离基变量应为离基变量0 0 5/3 0 2/3 0T*)因因为为 ,故故 也也必必须须大大于于0,0,否否则则不不满满足足可行性要求可行性要求;第14页/共33页16进基进基3.3.第

11、二次变换顶点第二次变换顶点去掉了去掉了(1)(2)1)1)确定进基变量确定进基变量(3)(4)第15页/共33页172)2)确定离基变量确定离基变量 离基离基(1(1)(2(2)0 0 8/5 1/5 0 0T(3)(3)(4)(4)第16页/共33页184.4.第三次变换顶点第三次变换顶点1)1)确定进基变量确定进基变量 故故 为最优点为最优点,为最优值为最优值:0 0 8/5 1/5 0 0T第17页/共33页19三三)用单纯形表求解线性用单纯形表求解线性规划规划例例.用初等变换法求解用初等变换法求解解解:增广矩阵增广矩阵:第18页/共33页20s.t.离离基基判判别别数数进基判别数进基判

12、别数 单单纯纯形形法法实实际际上上是是解解一一系系列列的的线线性性方方程程组组,也也可可用用初初等等变换方法列表求解变换方法列表求解.但需加入判别数的计算但需加入判别数的计算.421235基变量基变量x1x2x3x4x5x63x5112410425x612310155/3X0000045F037-4-11-20-15例例1 1第19页/共33页2142123基变量基变量x1x2x3x4x5x63x51/3-1/3010/312/30.21x31/32/311/305/35X1005/302/30F111/38/37/3-25/3421235基变量基变量x1x2x3x4x5x63x5112410

13、425x612310155/3X0000045F037-4-11-20-15第20页/共33页2242123基变量基变量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已获得最优解已获得最优解第21页/共33页23-2-300基变量基变量x1x2x3x40 x3-1110330 x41-4014-1X00034F00-2-3-2-3

14、0基变量基变量x1x2x3x4-3x2-1103-30 x4-30116-16/3X103016F1-9-5s.t.例例2 2问题有无界解问题有无界解第22页/共33页24三三.初始基本可初始基本可行解行解(1)(1)(1)(1)大大M M法法 引入一组人工变量引入一组人工变量引入一组人工变量引入一组人工变量,它们在目标函数中的它们在目标函数中的它们在目标函数中的它们在目标函数中的系数均是非常大的正数系数均是非常大的正数系数均是非常大的正数系数均是非常大的正数M;M;M;M;(2)(2)两相法两相法 引入一组人工变量引入一组人工变量引入一组人工变量引入一组人工变量,在人工变量未完在人工变量未完

15、在人工变量未完在人工变量未完全离基前目标函数为各人工变量之和全离基前目标函数为各人工变量之和全离基前目标函数为各人工变量之和全离基前目标函数为各人工变量之和,当人当人当人当人工变量完全离基后恢复原目标函数。工变量完全离基后恢复原目标函数。工变量完全离基后恢复原目标函数。工变量完全离基后恢复原目标函数。当当A A内不包含单位矩阵时内不包含单位矩阵时,需引入由人工变量组需引入由人工变量组成的单位矩阵成的单位矩阵,以方便获得初始可行解以方便获得初始可行解.第23页/共33页25一一一一)采用大采用大采用大采用大M M M M法获得初始基本可行解法获得初始基本可行解法获得初始基本可行解法获得初始基本可

16、行解s.t.采用大采用大M M法法：s.t.原问题原问题：因因M M是比其他价值系数大得多的正数是比其他价值系数大得多的正数,且人工变量非负且人工变量非负,迭代迭代的结果会使人工变量趋于零的结果会使人工变量趋于零,而获得原问题的基本可行解而获得原问题的基本可行解.第24页/共33页26s.t.411MM基变量基变量x1x2x3x4x5Mx42121042Mx53310131X000043F07M4-5M1-4M1-3M表表一一第25页/共33页27411MM基变量基变量x1x2x3x4x5Mx42121042Mx53310131X000043F07M4-5M1-4M1-3M411M基变量基变量

17、x1x2x3x4x5Mx40-14/3121.54x1111/3013X110020F14+2M-3+M-4/3-4M/3表表一一表表二二第26页/共33页28411基变量基变量x1x2x3x4x51x30-3/411.5-24x115/400.50.4X20.501.5F23.50-13/40表表三三初始基本初始基本可行解可行解411M基变量基变量x1x2x3x4x5Mx40-14/3121.54x1111/3013X110020F14+2M-3+M-4/3-4M/3表表二二第27页/共33页29411基变量基变量x1x2x3x4x51x30-3/411.5-24x115/400.50.4X

18、20.501.5F23.50-13/40411基变量基变量x1x2x3x4x51x3011.81x2100.4X300.41.8F32.2表表三三表表四四初始基本初始基本可行解可行解最优解最优解第28页/共33页30二二)采用两相法获得初始基本可行解采用两相法获得初始基本可行解大大M M法的法的M M是一个充分大的正数是一个充分大的正数,有时在计算机上不便处理有时在计算机上不便处理.s.t.原问题：原问题：s.t.相相1 1问题：问题：第29页/共33页3100011基变量基变量x1x2x3x4x51x421210421x53310131X0 00043F07-5-4-30001基变量基变量x

19、1x2x3x4x51x40-14/3121.50 x1111/3013X1 10020F121-4/3表表一一表表二二第30页/共33页32000基变量基变量x1x2x3x4x50 x30-3/411.5-20 x115/400.50.4X2 0.501.5F2 00表表三三初始基本初始基本可行解可行解411基变量基变量x1x2x3x4x51x30-3/411.5-24x115/400.50.4X00.501.5F03.5-13/4表表四四初始基本初始基本可行解可行解换换 相相第31页/共33页33411基变量基变量x1x2x3x4x51x3011.81x2100.4X100.41.8F12.213/5表表五五最优解最优解第32页/共33页