线性规划及单纯形PPT学习教案

1、会计学11.1 线性规划的数学模型 第1页/共110页合理安排，以最少的资源来完成它。第2页/共110页设备设备ABCD边际利润利润产品甲产品甲21402元元产品乙产品乙22043元元有效有效台时数台时数1281612第3页/共110页n同理，对设备B、C、D也可以得到以下不等式：8 16 12考虑到实际意义，不可能为负值，即021,xx2122xx 212xx 14x24x21,xx21,xx第4页/共110页max3221xxZ2132maxxxZ21,xx212xx 14x24x21,xx2122xx 第5页/共110页2132maxxxZ21,xx212xx 14x24x21,xx21

2、22xx 设备设备ABCD边际利利润润产品甲产品甲21402元元产品乙产品乙22043元元有效有效台时数台时数1281612其中 必须满足以下条件 12 8s.t. 16 12 0第6页/共110页第7页/共110页2134maxxxz16002221 xx25005 . 2521xx1x02xs.t.,4001x第8页/共110页成年人每天需要从食物中摄取的营养以及四种食品所含营养和价格见下表。问如何选择食品才能在满足营养的前提下使购买食品的费用最小？食品名称 热量(kcal) 蛋白质(g) 钙（mg） 价格（元） 猪肉 1000 50 400 14 鸡蛋 800 60 200 6 大米 9

3、00 20 300 3 白菜 200 10 500 2 营养需求量 3000 55 800 第9页/共110页0,800500300200400551020605030002009008001000. .23614min43214321432143214321xxxxxxxxxxxxxxxxt sxxxxz第10页/共110页第11页/共110页 方案长度一x1二x2三x3四x4五x52.92.11.513210221213合计（米）料头（米）7.407.30.17.20.27.10.36.60.8第12页/共110页5 , 4 , 3 , 2 , 1, ixi0,10032310022100

4、2. .8 . 03 . 02 . 01 . 00 . 0min54321532154342154321xxxxxxxxxxxxxxxtsxxxxxz第13页/共110页nxxx,21第14页/共110页 12 8 s.t. 16 12 02132maxxxZ212xx 14x24x21,xx2122xx 目标函数约束条件第15页/共110页nnxcxcxcZ2211max(min)0,2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxas.t.约束条件目标函数决策变量价值系数技术系数限定系数第16页/共110页第17页/共110页

5、0;, 2 , 1, 0max221122222121112121112211iimnmnmmnnnnnnbnixbxaxaxabxaxaxabxaxaxaxcxcxczs.t极大化型约束方程为等式所有的决策变量为非负值约束方程的右端项系数为非负值第18页/共110页1、极大化型2、约束方程为等式3、所有的决策变量为非负值4、约束方程的右端项系数为非负值n形式线性规划标准数学模型的特征第19页/共110页njxbxptsxczjnjjjnjjj, 2 , 1, 0. .max11第20页/共110页0.maxXbAXtsCXz第21页/共110页nmnmmnnpppaaaaaaaaaA2121

6、2222111211mnbbbbxxxX2121,ncccC21第22页/共110页非标准形式如何转换成标准形式1、目标函数是极小化的转化321723z minxxx321723, xxxzzz则目标函数转换为等价变换：令maxminzz )0(1647616476 ) 1 (2444321321cxxxxxxxx为松弛变量如：约束方程为转换、约束方程为不等式的xz-z第23页/共110页)0(1232712327 )2(444321321cxxxxxxxx为剩余变量如：约束方程为无非负约束如：jx无非负限制的转换决策变量jx. 3jjjjjxxxxx 令引入, 0, 0第24页/共110页4

7、.决策变量有上下界的转换4, 0 , 1 5 , 1, 51 3333333xxxxxxx则令如：无非负约束例：21332121321, 0 6 1 5 7 s.t 23min xxxxxxxxxxxz7)( .4221 xxxxts) 1()(23max3221 xxxxz4)(53221 xxxxx563xx0,6543221 xxxxxxx1, -23 33222321 xxxxxxxxz令：第25页/共110页0,124164821222000032max616251421321654321xxxxxxxxxxxxxxxxxxzs.t第26页/共110页0,40025005 . 251

8、6002200034max515142132154321xxxxxxxxxxxxxxxzs.t第27页/共110页第28页/共110页 12 8 s.t. 16 12 02132maxxxZ212xx 14x24x21,xx2122xx 第29页/共110页O123456132456782x1x0,21xx第30页/共110页412345613256O782x1x122221 xx第31页/共110页54R1234561326O782x1x122221 xx8221 xx第32页/共110页4QR12345613256O782x1x122221 xx8221 xx1641x1242xPS第33

9、页/共110页PQRS123456132456O782x1x122221 xx8221 xx1641x1242x第34页/共110页PQRS123456132456O782x1x122221 xx8221 xx1641x1242x2132xxZ第35页/共110页PQRS123456132456O782x1x122221 xx8221 xx1641x1242x(4,2)第36页/共110页第37页/共110页O123456132456782x1x第38页/共110页PQRS123456132456O782x1x122221 xx8221 xx1641x1242x可行域第39页/共110页PQR

10、S123456132456O782x1x122221 xx8221 xx1641x1242x(4,2)可行域n思考：当目标函数改为时，最优解是什么？2142maxxxZ第40页/共110页第41页/共110页第42页/共110页第43页/共110页第44页/共110页第45页/共110页是否为可行解？）（，）（，）（判断TTTXXXxxxxxxtsxxz1 23 11 5 0, 42 63 .23 max21212121第46页/共110页的约束方程系数矩阵为该例：LP 1 0 2- 10 1- 3 1 4 2 6 3 421321Axxxxxx第47页/共110页 1 0 2- 10 1-

11、3 1 4 2 6 3 421321Axxxxxx系数矩阵例： 2- 13 11B0 11- 12B1 0 0 1 1 2-0 3 0 2-1- 3 654BBB1 10 13B需要扣除奇异矩阵为：基矩阵的个数（最多）,)!( ! mnmnCmn第48页/共110页4 2- 16 3 1462- 13 1 21增广矩阵如上例：xxbBXB2- 5- 06 3 1初等变换52 1 06 3 152 1 0524 0 152 52421xxTX0 0 52 524)1(TX0) 2- 0 4()2(TX2)- 0 0 6()3(TTTXXX4) 6- 0 0( 8) 0 2 0( 0) 12- 2

12、- 0()6(5)4(第49页/共110页可行解基本解基本可行解结论：若LP问题存在最优解，则一定可以在 基本可行解中找到。第50页/共110页）最优解）基本可行解；）所有的基本解；求：问题如下：练习：有3 2 14 , 3 , 2 , 1 0 30332 50542 . 423max 432143214321jxxxxxxxxxtsxxxxzLPj第51页/共110页3- 31 5 3- 21 4 3 25 4 3- 11 2 3 15 2) 154321BBBBB基矩阵：解：TTTXXXXX710- 0 790 0710- 0 0 71800 10 0 0)2)4(2)5()3(1（退化解

13、）基本解：）（)5()3(1,)3XXX）（基本可行解：10z 0 10 0 0)4*T*）（最优解：X2 14 20*B第52页/共110页* LP问题存在可行解，则问题的可行域是凸集* LP问题的基本可行解X对应LP问题可行域的顶点* LP问题有最优解，一定存在一个基可行解是最优解第53页/共110页单纯形法思路初始基可行解新的基可行解最优性条件最优解换基迭代YN第54页/共110页第55页/共110页0,40025005 . 2516002200034max515142132154321xxxxxxxxxxxxxxxz第56页/共110页4001000125000105 . 251600

14、0012254321bxxxxx1000100011B第57页/共110页n目标函数与最优性检验543,xxx152142134005 . 252500221600 xxxxxxxxTX400,2500,1600,0 ,0154321100034xxxxxZ第58页/共110页1x400140050052500800216004001000125000105 . 2516000012254321bxxxxx5x对目标函数贡献大（价值系数高）受资源的约束，400所对应的资源最紧张第59页/共110页1005102012B143,xxx400100015005105 . 2080020120543

15、21bxxxxx第60页/共110页TX0,500,800,0,4002522524316003)400(4xxxxZ第61页/共110页2x4x2005 . 25004002800400100015005105 . 208002012054321bxxxxx不考虑零与负值第62页/共110页v新基v新的基变量：v新的基本可行解10055.202213B123,xxx4001000120024 . 001040028 . 010054321bxxxxx第63页/共110页v基本可行解v目标函数TX0,0,400,200,400354545322 . 12200)24 . 0200(3)400(

16、4xxxxxZ第64页/共110页v确定入基变量：v确定出基变量：5x3x400140020024004001000120024 . 001040028 . 010054321bxxxxx不考虑零与负值第65页/共110页10155.202204B125,xxx20004 . 05 . 00160004 . 00 . 11020014 . 05 . 00054321bxxxxx第66页/共110页。TX200,0,0,600,200443434344 . 02600)4 . 0600(3)4 . 05 . 0200(4xxxxxxZ第67页/共110页nixbAxxptscxxcziniiin

17、iii, 3 , 2 , 1, 0)(. .)(max11第68页/共110页NBNxbBxNBNxBbBx11NNBBxCxCzminmjjmiijijiiNBNBNNNBxaccbcxNBCCbBCxCNxBbBCz1111111)()()(NBxxxNBA,第69页/共110页miiiBbcbBCz110miijijBjBjacPBCNBCz111)(jjjzc nmjjjxzz10第70页/共110页第71页/共110页430000001600250040025122.5010001000180050040043000jcBcBx1x2xjjjzc 3x4x5x3x4x5xbBCB1b

18、B1第72页/共110页430000001600250040025122.50100010001800500400043000jcBCBx1x2x3x4x5x3x4x5xjjjzc bBCB1bB1第73页/共110页4300000480050040000122.50100010-2-514002000不算不算16000300-4jcBCBx1x2x3x4x5x3x4x1xjjjzc bB1330202.54016000800+0500+4400第74页/共110页43000034400200400001010100-0.80.402-21200负值负值 不算不算4002200000-1.22

19、jcBCBx1x2x3x4x5x3x2x1xjjjzc bB1第75页/共110页430000342006002000010100.51-0.5-0.4-0.40.4100260000-1-0.40jcBCBx1x2x3x4x5x5x2x1xjjjzc bB1第76页/共110页第77页/共110页单纯形法的进一步讨论单纯形法的进一步讨论1、无界解、无界解4 , 3 , 2 , 1 0 4 3- 2 s.t 32max j2421132121jxlxxxlxxxxxz例：O1x2x2l1lz第78页/共110页cj2300bcBxBx1x2x3x400 x3x41-110-310124j230

20、020 x1x41-1100-231210j05-20结论：结论：若若j0,对应的系数列向量对应的系数列向量0，则该，则该LP存在无存在无界解。界解。第79页/共110页2、多个解22112121 2127 2172 144max lxxlxx s.txxz例：x1x2l2l1OABC第80页/共110页 cj4 14 0 0b cB xBx1 x2 x3 x300 x3X42 7 1 07 2 0 121213j4 14 0 014 0 x2x42/7 1 1/7 045/7 0 -2/7 1315j 0 0 -2 0z=4221/27/314 4x2x1 0 1 7/45 -2/45 1

21、0 2/45 7/457/37/3j 0 0 -2 0z=4221/2第81页/共110页42)01 ()1 (0 0 37 37,15 0 3 0*)2()1(*)2()1(zXXXXXTT结论：若某个非基变量的检验系数为零，则该 LP存在多个最优解。当所有的检验数全部小于等于零时,若有某个非基变量的检验数也是零,则该线性规划有无穷多组解,否则有唯一解.第82页/共110页3、退化解0, 3 4 2 2 . 5 . 12max 321321312131xxxxxxxxxxtsxxz例：第83页/共110页cj2 0 1.5 0 0 0bcBxBx1 x2 x3 x4 x5 x6000 x4x

22、5x61 -1 0 1 0 02 0 1 0 1 01 1 1 0 0 1243223j2 0 1.5 0 0 0200 x1x5x61 -1 0 1 0 00 2 1 -2 1 00 2 1 -1 0 1201j0 2 1.5 -2 0 0基本可行解中基变量等于零第84页/共110页*在单纯形法的计算过程中，确定换出基变量时存在在单纯形法的计算过程中，确定换出基变量时存在两两个或两个以上的最小比值，这时会出现退化解个或两个以上的最小比值，这时会出现退化解。特征：基本可行解中，基变量等于零特征：基本可行解中，基变量等于零*有时，退化会造成计算过程的循环，永远达不到有时，退化会造成计算过程的循环

23、，永远达不到最优解最优解。4,.,2 , 1 0 1 03211221 09841s.t 6212043min6.j3432143214321jxxxxxxxxxxxxxxzBealeE次后又回到初始解）代给出的循环例子：（迭由*用勃兰特法则一定可以避免出现循环用勃兰特法则一定可以避免出现循环第85页/共110页为避免循环,常采用1976年R.G.Bland提出Bland法则:单纯形表中有若干个检验数大于零大于零 时,取下取下标号小标号小的非基变量为换入基变量入基变量; 用 法则选取换出基出基变量时,若比值相同,则选取下标号小下标号小的基变量为换出基变量. 勃兰特（Bland）法则第86页/共

24、110页4、无可行解（大M法）0, 40 30 150103 . 3020max212112121xxxxxxxtsxxz例：第87页/共110页 cj20 30 0 0 0 -MbcBxBx1 x2 x3 x4 x5 x6 00-Mx3x4x63 10 1 0 0 01 0 0 1 0 01 1 0 0 -1 11503040j20+M 30+M 0 0 -M 0 3020-Mx2x1x60 1 1/10 -3/10 0 01 0 0 1 0 00 0 -1/10 -7/10 -1 1 6 30 4 j0 0 3-M/10 -11-7M/10 M 0第88页/共110页xBx1x2x3x4x

25、5bx2x3x5110-40-201-30300a153dj-3000讨论题讨论题在求解极大化在求解极大化LP问题中，得到如下单纯形表：问题中，得到如下单纯形表：1、当前解为最优解时，各参数应满足的条件；、当前解为最优解时，各参数应满足的条件；2、原问题存在无界解时，各参数应满足的条件；、原问题存在无界解时，各参数应满足的条件；3、原问题存在多个解时，各参数应满足的条件；、原问题存在多个解时，各参数应满足的条件；4、当、当x4作为进基变量取代作为进基变量取代x5时，目标值的增量为多少？时，目标值的增量为多少？结论：结论：若基变量中有非零的人工变量，则该若基变量中有非零的人工变量，则该LP无可行

26、解。无可行解。第89页/共110页第90页/共110页 标准型j0,maxXbAXCXz0,minXbAXCXzjjzc 00第91页/共110页0,18231224. .53max21212121xxxxxxtsxxz第92页/共110页0,18231224. .)(053max43212142314321xxxxxxxxxxtsxxxxz第93页/共110页0,18231224. .)(053max521521423154321xxxxxxxxxxtsMxxxxxz第94页/共110页3500-Mb00-M41218103022100010001 4 6-18M3+3M5+2M000jcBcBx1x2xjjjzc 3x4x5x5x4x3x第95页/共110页3500-Mb30-M412610002210-30100016312-6M05+2M-3-M00jcBcBx1x2xjjjzc 3x4x5x5x4x1x第96页/共110页3500-Mb30546310000113-1.50100-10.54227