《第一章线性规划及单纯形法》由会员分享，可在线阅读，更多相关《第一章线性规划及单纯形法（140页珍藏版）》请在金锄头文库上搜索。
1、第一章第一章 线性规划及单纯形法线性规划及单纯形法1线性规划介绍2线性规划数学模型3线性规划标准形式4线性规划的图解法5线性规划基本概念6单纯形法7应用举例掖苑汀下鞍蛾釜柑乱盲秤棱帅纱熊劳坝缺饥雌克板摸撂者妄靳铱系胚矩排第一章线性规划及单纯形法第一章线性规划及单纯形法第一章1线性规划介绍线性规划介绍历史悠久，理论成熟，应用广泛运筹学的最基本的方法之一，网络规划、整数规划、目标规划和多目标规划都是以线性规划为基础的。解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大。歪吾盲凳扩瘦尼糕缺化邮揣驶开绿彪攒阻硅瞩慕枪欢歇榜背寂媒柒暗丧柱第一章线性规划及单纯形法第一章线性规划及单纯形法第一
2、章线性规划理论的发展线性规划理论的发展：1939年前苏联康托洛维奇（年前苏联康托洛维奇（KOHTOPOBUZ） 生产组织与计划中的生产组织与计划中的 数学方法提出数学方法提出 “解乘数法解乘数法”。1线性规划介绍线性规划介绍列奥尼德列奥尼德康托罗维奇，前苏联人，由于在康托罗维奇，前苏联人，由于在1939年创年创立了享誉全球的线形规划要点，对资源最优分配理论立了享誉全球的线形规划要点，对资源最优分配理论做出了贡献，而获得诺贝尔经济学奖。做出了贡献，而获得诺贝尔经济学奖。丘譬乍超拟椽坛曳萧彤帜烛脊裳螺拘笼悯郸秃赚架敷浊招崭沛返鱼吾林黍第一章线性规划及单纯形法第一章线性规划及单纯形法第一章美国科学院
3、院士美国科学院院士DANTZIG（丹齐克），（丹齐克），1948年在年在研究美国空军资源的优化配置时提出线性规划及其通用研究美国空军资源的优化配置时提出线性规划及其通用解法解法 “单纯形法单纯形法”。被称为线性规划之父。被称为线性规划之父。1线性规划介绍线性规划介绍 线性规划之父的Dantzig (丹齐克)。据说，一次上课，Dantzig迟到 了，仰头看去，黑板上留了几个几个题目，他就抄了一下，回家后埋头苦做。几个星期之后，疲惫的去找老师说，这件事情真的对不起，作业好像太难了，我所以现在才交，言下很是 惭愧。几天之后，他的老师就把他召了过去，兴奋的告诉他说他太兴奋了。Dantzig很不解 ,
4、后来才知道原来黑板上的题目根本就不是什么家庭作业，而是老师说的本领域的未解决的问题，他给出的那个解法也就是单纯形法。这个方法是上个世纪前十位的算法。 厩扮业胶椒芥获曝概酣腊车雏乃贿掷挥钡筒磋挖往弄颖峙金侩巢检述唆总第一章线性规划及单纯形法第一章线性规划及单纯形法第一章1线性规划介绍线性规划介绍 1960 1960年，年，“最佳资源利用的经济计算最佳资源利用的经济计算” ” 康托洛维奇康托洛维奇和库伯曼斯和库伯曼斯(Koopmans) (Koopmans) 。两人因对资源最优分配理论的。两人因对资源最优分配理论的贡献而获贡献而获19751975年诺贝尔经济学奖年诺贝尔经济学奖 佳林佳林库普曼斯，
5、美国人，他将数理统计学成功运用库普曼斯，美国人，他将数理统计学成功运用于经济计量学，对资源最优分配理论做出了贡献。于经济计量学，对资源最优分配理论做出了贡献。撤榨跌扶词稽邦甩病徽谁咯锦蹲狱岔舜昼墟翔返脑样刷曼够霸鳃绎谭乌碑第一章线性规划及单纯形法第一章线性规划及单纯形法第一章1961年，查恩斯与库伯提出了目标规划，艾吉利提出了用优先因子来处理多目标问题。20世纪70年代，斯姆李与杰斯开莱尼应用计算机处理目标规划问题。计算机 50约束 100变量 30000约束 3000000变量1线性规划介绍线性规划介绍有楔至胎糯嘱需整蜂商苏铺察络生亥厅枪啤帮亏蚀刀毯氨伦涂强樟氨欲镭第一章线性规划及单纯形法第
6、一章线性规划及单纯形法第一章从1964年诺贝尔奖设经济学奖后，到1992年28年间的32名获奖者中有13人(40%)从事过与线性规划有关的研究工作，其中著名的有Simon，Samullson，Leontief，Arrow，Miller等。1线性规划介绍线性规划介绍保罗-萨缪尔逊（PAUL A SAMUELSON ）, 他发展了数理和动态经济理论，将经济科学提高到新的水平。他的研究涉及经济学的全部领域。于1970年获得诺贝尔经济学奖。华西里列昂惕夫（WASSILY LEONTIEF） ，美国人，他发展了投入产出方法，该方法在许多重要的经济问题中得到运用。曾获1973年诺贝尔经济科学奖。肯尼斯-J
7、-阿罗（KENNETH J. ARROW）,美国人，因与约翰-希克斯（JOHN R. HICKS）共同深入研究了经济均衡理论和福利理论获得1972年诺贝尔经济学奖。牟顿-米勒（MERTON M. MILLER）,1923-2000, 美国人,由于他在金融经济学方面做出了开创性工作，于1990年获得诺贝尔经济奖。弧妈锌眩晃眷怜塔沉悯浆障琉赠某拆骚室涩拒啪砌良伟脆蚜扩蒋阐键栗末第一章线性规划及单纯形法第一章线性规划及单纯形法第一章1线性规划介绍线性规划介绍线性规划研究的主要问题：有一定的人力、财力、资源条件下，如何合理安排使用，效益最高? 某项任务确定后，如何安排人、财、物，使之最省?劫输厅冲锻讹
8、怖耸翰迄酞轴泄吧互讶率蛔负厅来厂抢对袄栏揍斗升运者莲第一章线性规划及单纯形法第一章线性规划及单纯形法第一章 例例1 美佳公司计划制造美佳公司计划制造I，II两种家电产品。已知各两种家电产品。已知各制造一件时分别占用的设备制造一件时分别占用的设备A、B的台时、调试时间及的台时、调试时间及A、B设备和调试工序每天可用于这两种家电的能力、各售出设备和调试工序每天可用于这两种家电的能力、各售出一件时的获利情况如表一件时的获利情况如表Il所示。问该公司应制造所示。问该公司应制造A、B两两种家电各多少件，使获取的利润为最大？种家电各多少件，使获取的利润为最大？项目项目I IIIII每天可用能力每天可用能力
9、设备设备A A（h h）设备设备B B（h h）调试工序调试工序（h h）0 06 61 15 52 21 1151524245 5利润（元）利润（元）2 21 12线性规划数学模型线性规划数学模型豺汪似埋概韶因仙没弛鲤靡滇褂顽雇杰盖闽磊坎昨析菱迂吐致糯砍微而刺第一章线性规划及单纯形法第一章线性规划及单纯形法第一章例例2 捷运公司拟在下一年度的捷运公司拟在下一年度的1-4月的月的4个月内需租用仓库堆个月内需租用仓库堆放物资。已知各月份所需仓库面积数列见下表。仓库租借费用随放物资。已知各月份所需仓库面积数列见下表。仓库租借费用随合同期定，期限越长折扣越大，具体数字见下表。租借仓库的合合同期定，期
10、限越长折扣越大，具体数字见下表。租借仓库的合同每月初都可办理，每份台同具体现定租用面积数和期限。因此同每月初都可办理，每份台同具体现定租用面积数和期限。因此该厂可根据需要，在任何一个月初办理租借台同。每次办理时可该厂可根据需要，在任何一个月初办理租借台同。每次办理时可签一份，也可签若干份租用面积和租借期限不同的合同，试确定签一份，也可签若干份租用面积和租借期限不同的合同，试确定该公司签订租借合同的最优决策，目的是使所付租借费用最小。该公司签订租借合同的最优决策，目的是使所付租借费用最小。月份月份1 12 23 34 4所需仓库面积所需仓库面积1515101020201212合同租借期限合同租借
11、期限1 1个月个月2 2个月个月3 3个月个月4 4个月个月合同期内的租费合同期内的租费280028004500450060006000730073002线性规划数学模型线性规划数学模型睁佛愤啦屉茶用金吵吞绵黄扛降钻稚抹憾彬沉魏寅鬼磷隘翅跟彻入六讲肤第一章线性规划及单纯形法第一章线性规划及单纯形法第一章目标函数目标函数约束条件约束条件解：用变量解：用变量x1x1和和x2x2分别表示美佳公司制造家电分别表示美佳公司制造家电I I和和IIII的数量。的数量。项目项目I IIIII每天可用能力每天可用能力设备设备A A（h h）设备设备B B（h h）调试工序调试工序（h h）0 06 61 15
12、52 21 1151524245 5利润（元）利润（元）2 21 1例例1 1用数学语言描述用数学语言描述2线性规划数学模型线性规划数学模型开雕褂氨换民棠画屏日扒儒杏夫衙领池涟特豹寅尖医谣泪飘辗铸萌贬井仅第一章线性规划及单纯形法第一章线性规划及单纯形法第一章解：设变量xij表示捷运公司在第i(i1，4)个月初签订的租借期为jj1，4)个月的仓库面积的合同(单位为100m2)。约束条件目标函数例例2 2月份月份1 12 23 34 4所需仓库面积所需仓库面积1515101020201212合同租借期限合同租借期限1 1个月个月2 2个月个月3 3个月个月4 4个月个月合同期内的租费合同期内的租费
13、280028004500450060006000730073002线性规划数学模型线性规划数学模型裔潍宅利夹帅橱倚虱庐屑茵伤思帕豌惹驯盆醇贺焉鹏又庞岸顺痴痒孪连历第一章线性规划及单纯形法第一章线性规划及单纯形法第一章 A B 备用资源备用资源 煤煤 1 2 30 劳动日劳动日 3 2 60 仓库仓库 0 2 24 利润利润 40 50求：最大利润的生产计划。练习练习1 生产计划问题生产计划问题2线性规划数学模型线性规划数学模型演红椽械磁硕辛底戌革秃冈座雀喇渍雏蹿栖瞒倔骑厚梁沈地卓吨菱歇谜宵第一章线性规划及单纯形法第一章线性规划及单纯形法第一章max Z= 40x1 +50x2解:设产品A, B
14、产量分别为变量x1 ， x2x1 + 2x2 30 3x1 + 2x2 602x2 24x1，x2 0s.t.2线性规划数学模型线性规划数学模型涉扣鲍哈仑判磅惩赐历茸厘护斩竟辩锡琉忠闽慈锨份规由就何莽嫁健丁纱第一章线性规划及单纯形法第一章线性规划及单纯形法第一章求：最低成本的原料混合方案？求：最低成本的原料混合方案？ 原料原料 A B 每单位成本每单位成本 1 4 1 0 2 2 6 1 2 5 3 1 7 1 6 4 2 5 3 8 每单位添每单位添 加剂中维生加剂中维生 12 14 8 素最低含量素最低含量练习练习2 混合配料问题混合配料问题2线性规划数学模型线性规划数学模型脐廷赂淖淄殉息
15、泡铣进哉眉寐沤废瞳现亚远狠蚤描杉航粹更抒肌凰墨痰课第一章线性规划及单纯形法第一章线性规划及单纯形法第一章解：设每单位添加剂中原料解：设每单位添加剂中原料i的用量为的用量为xi(i =1,2,3,4)minZ= 2x1 + 5x2 +6x3+8x4 4x1 + 6x2 + x3+2x4 12 x1 + x2 +7x3+5x4 14 2x2 + x3+3x4 8 xi 0 (i =1,4)s.t.2线性规划数学模型线性规划数学模型玩蓝董椭遭碍插蚀车废婚璃猴此贪这竣磅鹰迭周阐贪终薪跋濒俘焕掷凹诣第一章线性规划及单纯形法第一章线性规划及单纯形法第一章决策变量：向量(x1 xn)T 决策人要考虑和控制的
16、因素。非负约束条件：线性等式或不等式目标函数：Z=(x1 xn) 线性式，求Z极大或极小线性规划模型特点2线性规划数学模型线性规划数学模型尉亭惕饯车呸涛惊诱汕瞪市肖扔踌诌霞放丽靴铸理接红竹滤伤壤啥羔鹅占第一章线性规划及单纯形法第一章线性规划及单纯形法第一章如果规划问题的数学模型中，决策变量的取值可以是连续的，目标函数是决策变量的线性函数，约束条件是含决策变量的线性等式或不等式，则该类规划问题的数学模型称为线性规划的数学模型线性规划的数学模型。实际问题中线性的含义：一是严格的比例性二是可叠加性关于线性的界定关于线性的界定2线性规划数学模型线性规划数学模型牺箩翅遵隘佣氯肩偏巍叫扒蓟节慧耶扼试链民偏
17、冈简城蠕绽救晒爪侩矫惹第一章线性规划及单纯形法第一章线性规划及单纯形法第一章max(min)Z=c1x1+ c2x2+cnxnn个变量个变量价值系价值系数数第第i 种资种资源的拥有源的拥有量量技术系数或技术系数或工艺系数工艺系数a11x1+ a12x2+ a1nxn (=, )b1a21x1+ a22x2+ a2nxn (=, )b2 am1x1+ am2x2+ amnxn (=, )bmxj 0(j=1,n)s.t.线性规划的一般式线性规划的一般式2线性规划数学模型线性规划数学模型后尤积他藤怜瘪痘戊品叫笨署尾水颖爆铺曙凝废亭疤缄铲粤逛甄以问刮蛔第一章线性规划及单纯形法第一章线性规划及单纯形法
18、19第一章线性规划的简写式线性规划的简写式2线性规划数学模型线性规划数学模型毯傣汇萨蛔拆锡即劈电乖湛俄痊肠吾腐芥酒寐烬厕湿醉乖怨居景诫臀诚讯第一章线性规划及单纯形法第一章线性规划及单纯形法第一章线性规划的向量表示式线性规划的向量表示式2线性规划数学模型线性规划数学模型绘沧舞剂弱恋惶呈幅子艘湘蛊泼砚牟渺棺醒蜀镭掏着忠柱绕骏涕挚铰跟镊第一章线性规划及单纯形法第一章线性规划及单纯形法第一章线性规划的矩阵表示式线性规划的矩阵表示式2线性规划数学模型线性规划数学模型道蓉埂咀缺鸭廊舱捞纬汤锰拐诸硫庇冷剩掳翌厕毒拐你洒藐藉碾爷洁庇靛第一章线性规划及单纯形法第一章线性规划及单纯形法第一章比例性：决策变量变化引
19、起目标的改变量与决策变量改变量成正比；可加性：每个决策变量对目标和约束的影响独立于其它变量；连续性：每个决策变量取连续值；确定性：线性规划中的参数aij , bi , ci为确定值。隐含的假设隐含的假设2线性规划数学模型线性规划数学模型忻邵手耶瞄婪眉失宴釉缎洁媳勒省猴殿鸦侣皋碎呜传胜催衫冉部柄形都梦第一章线性规划及单纯形法第一章线性规划及单纯形法第一章仓库工厂 1 2 3 库存 1 2 1 3 50 2 2 2 4 30 3 3 4 2 10 需求 40 15 35练习练习3 运输问题运输问题工厂需要的原棉存放在三个仓库中，现将原棉运往工厂以满足工厂生产的需求。已知原棉运到各个工厂的单位运费如
20、表所示。问使总运费最小的运输方案？2线性规划数学模型线性规划数学模型弥催履任哦遗玩漆媚窿绝诡涡寡佩门患吃阿擎舶夏箩墙凯祖椅凑交扎旦侦第一章线性规划及单纯形法第一章线性规划及单纯形法第一章解：设解：设xij为为i 仓库运到仓库运到 j工厂的原棉数量工厂的原棉数量(i =1,2,3 j =1,2,3)minZ= 2x11 + x12+3x13+2x21 +2x22 +4x23 +3x31 +4x32 +2x33x11 +x12+x13 50x21+x22+x23 30x31+x32+x33 10x11 +x21+x31 = 40x12 +x22+x32 = 15x13 +x23+x33 = 35
21、xij 0st.2线性规划数学模型线性规划数学模型吞呈散宋厢粘雕晶赠辞毋澎兑镐篡赛羹绳钳逝孪庄气廖燥辈仔玻占韩宣堪第一章线性规划及单纯形法第一章线性规划及单纯形法第一章练习练习4 4 连续投资连续投资1010万元万元A A：从第：从第1 1年到第年到第4 4年每年初投资，次年末回收本利年每年初投资，次年末回收本利1.151.15；B B：第：第3 3年初投资，到第年初投资，到第5 5年末回收本利年末回收本利1.251.25，最大投资，最大投资4 4万元；万元；C C：第：第2 2年初投资，到第年初投资，到第5 5年末回收本利年末回收本利1.401.40，最大投资，最大投资3 3万元；万元；D
22、D：每年初投资，每年末回收本利：每年初投资，每年末回收本利1.111.11。求：使求：使5 5年末总资本最大的投资方案。年末总资本最大的投资方案。分析：分析： 1 2 3 4 5A x1A x2A x3A x4A B x3BC x2CD x1D x2D x3D x4D x5D 2线性规划数学模型线性规划数学模型锄之概描诲止堂狗翠泻侨纵遮布佑俏搭迟只阂胶愿请恢菠皑东沁旨纲汲隅第一章线性规划及单纯形法第一章线性规划及单纯形法第一章解解：xik( i =1,2,5; k =A,B,C,D)为第为第i年初投资到第年初投资到第k个项个项目的资金数。目的资金数。MaxZ= 1.15x4A +1.40 x2
23、C+1.25x3B+1.11x5Dx1A+x1D=10x2A+x2C+x2D= 1.11 x1Dx2C 3x3A +x3B+x3D =1.15 x1A+ 1.11 x2Dx3B 4x4A +x4D =1.15 x2A+ 1.11 x3Dx5D =1.15 x3A+ 1.11 x4D xik 0s.t.2线性规划数学模型线性规划数学模型短吊惠豁禄跃溺串枷桂畔健股蛇尺腐刊倡势磺统沈饭荡伐活芝皋淡署棕碗第一章线性规划及单纯形法第一章线性规划及单纯形法第一章线性规划问题应用线性规划问题应用市场营销(广告预算和媒介选择，竞争性定价，新产品开发，制定销售计划)生产计划制定(合理下料，配料，“生产计划、库存
24、、劳力综合”)库存管理(合理物资库存量，停车场大小，设备容量)运输问题财政、会计(预算，贷款，成本分析，投资，证券管理)人事(人员分配，人才评价，工资和奖金的确定)设备管理(维修计划，设备更新)城市管理(供水，污水管理，服务系统设计、运用)2线性规划数学模型线性规划数学模型抽章数明割蠢姨旋皇拢磕妨帐孜褪阔嘛先疥拼泼拳蒸相监普躲楞曝来褒烽第一章线性规划及单纯形法第一章线性规划及单纯形法第一章线性规划的适用情况线性规划的适用情况要解决的问题的目标可以用数值指标反映对于要实现的目标有多种方案可选择有影响决策的若干约束条件2线性规划数学模型线性规划数学模型扛涛感舌划丢薪物沥眶倡兴惩任督仕察冲涛纪践炊盂
25、洲菩园栖押凉梨赢谬第一章线性规划及单纯形法第一章线性规划及单纯形法第一章线性规划模型的结构目标函数 ：max，min约束条件：,=,变量符号：0, 0线性规划的标准形式目标函数：max约束条件：=变量符号：03线性规划标准形式线性规划标准形式拌独胁钎默灭愧鸯傻役娠丢逞樟材丹吸履盯锥帚幢觅衍驴爱侮也钎杭苟赚第一章线性规划及单纯形法第一章线性规划及单纯形法第一章标准型的一般型标准型的一般型maxZ=c1x1+ c2x2+cnxn其中 bi 0 (i=1,2,m)a11x1+ a12x2+ a1nxn =b1a21x1+ a22x2+ a2nxn =b2 am1x1+ am2x2+ amnxn =b
26、mxj 0(j=1,2,n)s.t.3线性规划标准形式线性规划标准形式例窑势市雍垄桅昆式乏因骤括焰韭纷娥铁版镑哀唆蛊昭纺陪檄釉鲍韶器狄第一章线性规划及单纯形法第一章线性规划及单纯形法第一章 P1 P2 Pn a11 a12 a1n其中 A= a21 a22 a2n am1 am2 amn x1 x= x2 xn b1 b= b2 bmC=(C1 C2 Cn )标准型的矩阵型标准型的矩阵型maxZ=Cx Ax=b x 0 b0 b 0 0 3线性规划标准形式线性规划标准形式蝉仰绞摈换膘阀泞道琵邢悉毡挣慈惊辕锌皮剁桔佬畅菌勤碌刊套挫职沫畜第一章线性规划及单纯形法第一章线性规划及单纯形法第一章 x1
27、Ax=(P1 P2 Pn ) x2 = b xn P1 x1+ P2 x2 + +Pn xn=b标准型的向量型标准型的向量型3线性规划标准形式线性规划标准形式曾婴撼漏鹅刹臣振腰夹汁涕炼歌场勾幸前妇伺堵沧囊庙要接薪躁斧龋邹隘第一章线性规划及单纯形法第一章线性规划及单纯形法第一章线性规划问题化标准型：线性规划问题化标准型：(1)、约束条件(2)、变量(3)、目标函数(4)、右端常数3线性规划标准形式线性规划标准形式粕菊剃裳圾节钞忽颓渣梳垦呻知踢捞仅皑儿敞骂后旨抬意恢悉皿瘪征言雄第一章线性规划及单纯形法第一章线性规划及单纯形法第一章(1)、约束条件、约束条件x3为松弛变量x4为剩余变量 松弛变量或剩
28、余变量在实际问题中分别表示未被充分利用的资源和超出的资源数，均未转化为价值和利润，所以引进模型后它们在目标函数中的系数均为零。当约束条件为“ ”时：当约束条件为“ ”时：3线性规划标准形式线性规划标准形式娩薄袱碟网飘自铺狞者肯邮诸皇仓潜镰桶屈烈军鳞测获所滚割取胸迸歪影第一章线性规划及单纯形法第一章线性规划及单纯形法第一章3线性规划标准形式线性规划标准形式 X1 +2X2 +X3 =30 s.t. 3X1 +2X2 +X4 =60 2X2 +X5 =24 X1 , , X5 0 0 转化为：转化为：maxZ=40X1+ 50X2+0X3 +0X4+0X5 x1 + 2x2 30 3x1 + 2x
29、2 60s.t. 2x2 24 x1，x2 0 例：例：max Z= 40x1 +50x2松弛变量松弛变量姥堵帽菌嘴劲皮伯崇佯句劣绦锣心皋刑明雌束俭菊屠洽员余策豌耻升提钝第一章线性规划及单纯形法第一章线性规划及单纯形法第一章3线性规划标准形式线性规划标准形式例：例： 4x1 + 6x2 + x3+2x4 12 x1 + x2 +7x3+5x4 14 2x2 + x3+3x4 8 xi 0 (i =1,4)4X1+6X2+ X3 +2X4 - X5 =12 X1+ X2+7X3+5X4 - X6 =14 2X2+ X3+3X4 - X7=8 X1 , , X7 0 0 剩余变量剩余变量赦釜飘扳出
30、盼爵信允污迷钱完盐吾管玩预葱麻冻钳蹈匠迅彻砸旦揣捐加掌第一章线性规划及单纯形法第一章线性规划及单纯形法第一章(2)、变量、变量3 x1 -3 x1 +2x2 8 x1 - x1 - 4x2 14x1 , x1 ,x2 01、x 0的情况，3x1+2x2 8 x1 -4x2 14 x20令x1= x1- x1 2、x取值无约束的情况。令x- x。令x= x- x3 x1 -3 x1 +2x2 +x3 = 8 x1 - x1 - 4x2 +x 4= 14x1 , x1 ,x2 ,x3 ,x4 03线性规划标准形式线性规划标准形式朋喊挡挽碱鸟烈爬丑耿撅式镰苯氨滚败僵坝者窒蝴袍裂假漾茧衡更威凳檄第一章
31、线性规划及单纯形法第一章线性规划及单纯形法第一章x1 +x2 11x1 16x1 , x2 0（3 3）、）、x两边有约束的情况。两边有约束的情况。x1+x2 5-6 x1 10x20-6+6 x1+6 10+6 令x1 = x1 +6 0 x1 163线性规划标准形式线性规划标准形式瀑鸯诽荚兆搀沏戊艘着浇榷巨鹰嚣难谁盔宪今患板湍迪根稼僚虾鬃烈乒巍第一章线性规划及单纯形法第一章线性规划及单纯形法第一章(3)、目标函数、目标函数xoZ-Z令Z = - Z 3线性规划标准形式线性规划标准形式灿飞硷唉樊触霍摸呐疡肾辰浆詹疙唬拧食糕访崭澜烘砖词氨栗井麦吵宇遗第一章线性规划及单纯形法第一章线性规划及单纯
32、形法第一章(4)、右端常数、右端常数右端项b0时，只需将等式或不等式两端同乘(一1)，则等式右端项必大于零。3线性规划标准形式线性规划标准形式狡笋亚矣牌磺不亢派苇洁舟沛健榨厢彻晦叭盎斥宽懦沼哥芽甄堰璃将豺峭第一章线性规划及单纯形法第一章线性规划及单纯形法第一章例3：将 min Z = -x1+2x2 -3x3x1+x2 +x3 7x1 -x2 +x3 2x1，x20，x3无限制化为标准型3线性规划标准形式线性规划标准形式药募讣巷竿阅瞄壁雕茶歇溶梢涂叁毛浚帘羔宇拾柱座舍淹菠惟氰皿梳铺沟第一章线性规划及单纯形法第一章线性规划及单纯形法第一章解： 令x3 =x4 - x5 加松弛变量x6加剩余变量x
33、7 令Z= -ZmaxZ= x1 -2x2 +3x4 -3x5 x1 +x2 +x4 -x5 +x6=7x1 -x2 +x4 -x5 -x7 =2x1 , x2 , x4 , , x7 0min Z = -x1+2x2 -3x3x1+x2 +x3 7x1 -x2 +x3 2x1，x20，x3无限制3线性规划标准形式线性规划标准形式阻资今克址摧缔受鹰铆账浇箩死贝撼砧直安烬弛惨佐娠梗闲知灰箩稗鼎黎第一章线性规划及单纯形法第一章线性规划及单纯形法第一章(1) min Z= 2x1 -x2+2x3练习练习5 将下列线性规划问题化成标准型：将下列线性规划问题化成标准型：- x1 +x2 +x3 = 4
34、- x1 +x2 - x3 6x1 0 ，x2 0, x3 无约束 s.t.(2) max Z= 2x1 +x2+3x3 +x4x1 +x2 +x3 +x3 7 2x1 - 3x2 + x3 = - 8x1 - 2x3 + 2x4 1x1 , x3 0, x2 0 ， x4 无约束 s.t.3线性规划标准形式线性规划标准形式融检板含劳曹化晨享喜杆土邻根出傅出拂赢磐娩酝顺炕住挤睬喊尹九睦毙第一章线性规划及单纯形法第一章线性规划及单纯形法第一章(3) min Z= 2x1 +3x2+5x3x1 +x2 -x3 - 5 - 6x1 + 7x2 -9 x3 = 15|19x1 - 7x2+ 5x3|
35、13x1 , x2 0, x3 无约束 s.t.(4) max Z= x1 -3x2- x1 +2x2 - 5 x1 + 3x2 = 10x1 , x2 无约束 s.t.3线性规划标准形式线性规划标准形式癸排直赁豢宋藕识锅蜘驱滇散摈萎织似柜漱检妻昼屉荣籍敦菌怨损旺匆赢第一章线性规划及单纯形法第一章线性规划及单纯形法第一章作业作业: 课本课本P44 123线性规划标准形式线性规划标准形式猛洞办痒缨宝恐家腕樟小聪是窥形语枣旺肖花曹像躬浅铜界修劳具刨吏辞第一章线性规划及单纯形法第一章线性规划及单纯形法第一章Ax=b (1)x 0 (2)maxZ=Cx (3)定义1：满足约束(1)、(2)的x=(x1
36、 xn)T称为LP问题的可行解，全部可行解的集合称为可行域。定义2：满足(3)的可行解称为LP问题的最优解线性规划的标准型线性规划的标准型4线性规划的图解法线性规划的图解法弹憾逝罩油付易隙涸僧棒柠逮敖杜绿惨呜沙毙时孪到眷酪乌稽粮杉颠拒老第一章线性规划及单纯形法第一章线性规划及单纯形法第一章图解法求解的目的：一是判别线性规划问题的求解结局；二是在存在最优解的条件下，把问题的最优解找出来。 4线性规划的图解法线性规划的图解法嘱嗣送肉绦崩款佳拆逮篱葛蒙炭垛校方屁构电廓型柄递拘瓤杖境笋雍渭拧第一章线性规划及单纯形法第一章线性规划及单纯形法第一章图解法的步骤：1、在平面上建立直角坐标系；2、图示约束条件
37、，找出可行域；3、图示目标函数和寻找最优解。4线性规划的图解法线性规划的图解法帝歧坠椎架双踌存雇刊脾夫步岩渐胎殃胡则梯逝骡址霞辨势亢循玲肃撂怨第一章线性规划及单纯形法第一章线性规划及单纯形法第一章例4 maxZ=40x1+ 50x2 x1+2x2 303x1+2x2 60 2x2 24 x1 , x2 04线性规划的图解法线性规划的图解法驹袭彪品券涅捌逐克芹茁湘名俄姑衰雾堪巴埔趋壮咙辜吁凄院洱违狮社锥第一章线性规划及单纯形法第一章线性规划及单纯形法第一章解：(1)、确定可行域 x1 0 x1 =0 (纵) x2 0 x2=0 (横) x1+2x2 30 x1+2x2 =30 (0,15) (3
38、0,0)x20102030DABC3x1+2x2 =60(0,30) (20,0) 2x2 =24203010x14线性规划的图解法线性规划的图解法耍胆憾弘搪蔷昼嫌户诌澄抽置颗掘转齐希笑慨鬼蓉啸郭猜邹今源漳掉阳鲤第一章线性规划及单纯形法第一章线性规划及单纯形法第一章(2)、求最优解最优解：x* = (15,7.5) Zmax =975Z=40x1+50x20=40x1+50x2 (0,0)， (10,-8)x20102030203010x1DABCC点： x1+2x2 =30 3x1+2x2 =604线性规划的图解法线性规划的图解法疚捅珠投遂梁酉睁邓舰蛹毋抑成障祭胯咐鸡只社坝垒剿恋推破吱停磺私
39、徊第一章线性规划及单纯形法第一章线性规划及单纯形法第一章Z= 40 x1 + 80x2 =0 x1 + 2x2 =30DABCx20x1解: 最优解：BC线段B点 C点x(1)=(6,12) x(2)=(15,7.5)x= x(1)+(1-) x(2) (0 1)例5、 maxZ=40x1+ 80x2 x1+2x2 303x1+2x2 60 2x2 24 x1 , x2 04线性规划的图解法线性规划的图解法莫耀悔权氓凯坏欢管奏亡稀协群握强骂本蔚额冗匝绊行艇鼎甲临襟籍拙槛第一章线性规划及单纯形法第一章线性规划及单纯形法第一章4线性规划的图解法线性规划的图解法X1 =6 + (1- )15X2=1
40、2 + (1- )7.5X1 =15-9 X2 =7.5+4.5 (0 1)X= = +(1- )maxZ=1200 X1 6 15 X2 12 7.5唆污骤浩筑媒稚拔赁恃塞檀蕊榨点纶撼梅娩恭纵圾鳖掂掺嫁由箱吩碍训汉第一章线性规划及单纯形法第一章线性规划及单纯形法第一章无界解无有限最优解例6、 maxZ=2x1+ 4x2 2x1+x2 8-2x1+x2 2x1 , x2 0Z=02x1+ x2=8-2x1+ x2=28246x240x14线性规划的图解法线性规划的图解法搂颂俘垄掳敞赘座姜裴恳膀渴遵裕鸦浸铲盗艰券拳寐圈咏絮熊霹表茬滓瓷第一章线性规划及单纯形法第一章线性规划及单纯形法第一章例7、
41、maxZ=3x1+2x2 -x1 -x2 1x1 , x2 0无解无可行解-1x1-1x204线性规划的图解法线性规划的图解法巾威甫隐详卜贼浚养摆给娩卢涌鹤桅脖线融翼另矗萍鞍隶鸳畔盖舰农队统第一章线性规划及单纯形法第一章线性规划及单纯形法第一章唯一解无穷多解 无有限最优解 无可行解有解无解当目标函数的直线族与某约束条件平行，且该问题有解时。约束条件无公共区域。有解但可行域可伸展到无穷时总总 结结4线性规划的图解法线性规划的图解法阿风充赖泊肚兴侗村缘殊耪峙节抽肾橱霸春层赦捉诫囚衣兹尚啪蜜香侩到第一章线性规划及单纯形法第一章线性规划及单纯形法第一章由图解法得到的启示由图解法得到的启示(1)、线性规
42、划问题的解的情况有四种：唯一最优解；无穷多最优解；无界解；无可行解。(2)、若线性规划可行域存在，则可行域是一个凸集。(3)、若有最优解，定可在可行域的顶点得到。(4)、解题思路是找出凸集的各顶点的最大目标函数值。4线性规划的图解法线性规划的图解法聘剪鳞诧什泣檀贡鲜五洗蛔库参妹捡柒唯裸炼化鲜照群抠扎鼻穆宙逆谱交第一章线性规划及单纯形法第一章线性规划及单纯形法第一章作业：作业：用图解法解以下问题： max Z= 5x1 +6x2x1 - 2x2 2 -2x1 + 3x2 2x1 , x2 无约束 s.t.4线性规划的图解法线性规划的图解法烦颠衙提邱徊负赫谐光诞惫脊黔绵时拍摔主韭肋耳慷憨俐洗是氦扼
43、阶献拂第一章线性规划及单纯形法第一章线性规划及单纯形法第一章maxZ=Cx Ax =b x0A mn 满秩 x = (x1 xn)T 一、线性规划问题的解的概念一、线性规划问题的解的概念5线性规划基本概念线性规划基本概念兹成潘邵管树烃韧示隅尽积醇汐吴颁妄伐那尝伺袁代沦陵洒蕉吸丢礁擞乙第一章线性规划及单纯形法第一章线性规划及单纯形法第一章定义定义1：基基(基阵基阵) 设A为约束方程组的mn阶系数矩阵设(nm)，其秩为m，B是矩阵A中的一个mm阶的满秩子矩阵，称B是线性规划问题的一个基。 P1 P2 Pm Pn a11 a12 a1m a1n A= a21 a22 a2m a2n am1 am2
44、amm amnB5线性规划基本概念线性规划基本概念焰絮荷讼竹鬃澜痘曼裳馋该狮简雾拂诌史长舆爱休露迟凑脓矫郭纳贡挫铜第一章线性规划及单纯形法第一章线性规划及单纯形法第一章A= (P1 Pm Pm+1 Pn )=(BN) 基向量 非基向量x= (x1 xm xm+1 xn )T=(xB xN)T 基变量 非基变量 xB xNB中的每一个列向量Pj称为基向量，与基向量对应的变量称为基变量，其他变量称为非基变量。5线性规划基本概念线性规划基本概念导裔违撤区郸矾羔补感竟糕格毒谐涎纳幅祟种压菲撬肉者汝捷倔嘲悯议疗第一章线性规划及单纯形法第一章线性规划及单纯形法第一章Ax=b的求解的求解xB xN(BN)
45、= bBxB +NxN=bBxB =b-NxNxB = B-1 b - B-1N xNA=(BN)x=(xB xN )T若B为单位矩阵 xB = b - N xN若xN0 xB = B-1 b5线性规划基本概念线性规划基本概念失淑声飞滁啮持陨颁未涵秦铃剔秀懦泪酌强职精置依寅撵镀庇乙忙减挂膳第一章线性规划及单纯形法第一章线性规划及单纯形法第一章定义2：可行解满足方程约束条件的解x（x1，x2，xn)T,称为线性规划问题的可行解。全部可行解的集合称为可行域。定义3：最优解使目标函数达到最大值的可行解，称为最优解。5线性规划基本概念线性规划基本概念辆闷且裔挖询洞酮诣怠女扼兴右哀诊米赵阉峻瘴嗜啼炯级碧
46、寇鸦帝钱衫肃第一章线性规划及单纯形法第一章线性规划及单纯形法第一章定义4：基本解对应于基B，x=为Ax=b的一个解，则x为线性规划问题的基本解，也称基解。B-1 b 0定义5：基本可行解基B，基本解x=若B-1 b0，称基解为基本可行解，也称基可行解。 B-1 b 0 基本解中最多有m个非零分量。 基本解的数目不超过Cnm = 个。n!m!(n-m)!定义6：可行基对应于基可行解的基称为可行基。5线性规划基本概念线性规划基本概念验荚仁舟壶钒赐技法锈渴岛伦易烫垢泄劫稚糕浑焊诧慈弘突景似嗓菠颇造第一章线性规划及单纯形法第一章线性规划及单纯形法第一章例8 x1+2x2 +x3 =30 3x1+2x2
47、 +x4 =60 2x2 +x5=24 x1 x5 01 2 1 0 03 2 0 1 00 2 0 0 1P1 P2 P3 P4 P5A=5线性规划基本概念线性规划基本概念塔手撼喝拉拨苗订池搁蓖琉瓦来业沮淆豌察爆仲补请掀滦播傣沙祁沿膝撇第一章线性规划及单纯形法第一章线性规划及单纯形法第一章x1x2x3x4x5x=b=306024B=(P3 P4 P5)=I 是满秩子矩阵 非基 N=(P1 P2)x3=30-( x1+2 x2)x4=60-(3x1+2 x2)x5 =24 -2 x25线性规划基本概念线性规划基本概念鲜盒资焙屁猩辣胡摇温督敏皆抖质仅彬卯偶魁玛盲吵厦朋完淮蔽彰端检极第一章线性规划
48、及单纯形法第一章线性规划及单纯形法第一章令x1 = x2 =0, x3=30, x4=60, x5=24x= = = xN 0 xB B-1 b003060245线性规划基本概念线性规划基本概念熙空汰乐乳幽兴袭侮拴淘蕊瑶钒爹宿门怀卸是掳堆嫁氏洽艘创来徽蹄展吝第一章线性规划及单纯形法第一章线性规划及单纯形法第一章例9：给定约束条件 -x3+x4 =0 x2 +x3 +x4 =3 -x1 +x2 +x3+x4 =2 xj 0 ( j=1,2,3,4 )求出基变量是x1 , x3 , x4的基本解，是不是可行解？5线性规划基本概念线性规划基本概念撤尤敦接春稍开谋尖乾函藕专苑柠鲁托困胃烬税礼邱驯痹扛司
49、历疼璃施碑第一章线性规划及单纯形法第一章线性规划及单纯形法第一章 0 -1 1解：B=(P1 P3 P4)= 0 1 1 -1 1 1 0 1 -1 0B-1= -1/2 1/2 0 3 1/2 1/2 0 2b=5线性规划基本概念线性规划基本概念猩畜耸困矩俩袜谁虹符堑那惩井泻钾岛帛柄觅稻莹涌福站绪缨谱郧系澈憨第一章线性规划及单纯形法第一章线性规划及单纯形法第一章 x1 x3 = B-1 b x4 xB = 0 1 -1 0 1 = -1/2 1/2 0 3 = 3/2 1/2 1/2 0 2 3/2x=(1, 0, 3/2, 3/2)T 是 5线性规划基本概念线性规划基本概念厚滞捎辰嘿押绞盆
50、豪感虑帅掏观逗鸟察校炬榔赶式够雇窑宙茬闰遏委纪谍第一章线性规划及单纯形法第一章线性规划及单纯形法第一章凸集D是n维空间的一个集合，x(1), x(2)D,若对任何x(1), x(2)，有x= x(1)+(1-) x(2) D(0 1)，则D为凸集。定义定义1：凸集如果集合D中任意两个点，其连线上的所有点也都是集合D中的点，则称D为凸集。二、凸集及其顶点二、凸集及其顶点5线性规划基本概念线性规划基本概念忆馈怜台紫鳞里深畴臭聊挟啡村枫算行堑地逊语盅瞩窄翅砷盟严院眩秉蛹第一章线性规划及单纯形法第一章线性规划及单纯形法第一章x(1)x(2)凸多边形凸多边形凹多边形凹多边形x(1)x(2)5线性规划基本
51、概念线性规划基本概念第一章锁今典借噎抠肤杠盟仅帖虞曲主颈戴铀飘酶灰慢赖唯告咽偏薄冲扁翰吻棱第一章线性规划及单纯形法第一章线性规划及单纯形法第一章 x(1) , x(2) , ,x(k) 是n维欧氏空间中的k个点，若有一组数 1 , 2 , , k 满足 0 i 1 (i=1, ,k)定义定义2 i =1ki=1有点 x= 1 x(1) + + k x(k)则称点x为 x(1) , x(2) , ,x(k) 的凸组合。凸组合5线性规划基本概念线性规划基本概念阐敢裳恳侦畸团讶歌苇缄霞幅椅指虫距购蹭蚜缮泄罗撮擦沼獭始恩结术漆第一章线性规划及单纯形法第一章线性规划及单纯形法第一章 凸集D, 点 xD，
52、若找不到两个不同的点x(1) , x(2) D 使得 x= x(1) +(1- ) x(2) (0 1) 则称x为 D的顶点。定义定义3顶点顶点5线性规划基本概念线性规划基本概念淘权墩拘郧悯忠岩楔鳞颊绷傍抄景髓噎碰堡认灼冉拈捷愁易馒警殴捕碌佃第一章线性规划及单纯形法第一章线性规划及单纯形法第一章证明：设LP问题的可行解域为集合CC= x| Ax=b x 0 任取x(1) , x(2) C, 则 x= x(1) +(1- ) x(2) 0 (0 1)又因为 A x(1) =b， A x(2) =b所以 Ax=A x(1) +(1- ) x(2) = b +(1- ) b=b 则 xC，C为凸集定
53、理定理1：LP问题的可行解域一定是凸集。问题的可行解域一定是凸集。三、几个基本定理的证明三、几个基本定理的证明5线性规划基本概念线性规划基本概念体帮昨藐蛮婶珍蟹翘闭极基纹侩帜遍获请拖拾建囱煌胳溜伞蹲沦璃沧裴些第一章线性规划及单纯形法第一章线性规划及单纯形法第一章只须证明： D的k个顶点x(1) , ,x(k) ，有 预理预理1 D为有界凸多面集，为有界凸多面集， x D，x必可表必可表 为为D的顶的顶点的凸组合点的凸组合 。0 i 1，使 x= 1 x(1) + + k x(k) i =1ki=15线性规划基本概念线性规划基本概念则签担锚象傅瓣驶纷井停卿魁距括赊孩巧荧是揭讣痉容离窥竭紧后睡薯虽
54、第一章线性规划及单纯形法第一章线性规划及单纯形法第一章证明可用归纳法（略）x(1)x(2)x(3)x xx在边界上x在内部 x(1) (1- ) x(2) (1- )x(3) x=+x x +(1- ) x(2) (0 1)x x(1) +(1- ) x(3) (0 1)5线性规划基本概念线性规划基本概念拐筑范括赠写薪景夸很酸假输丁酪鸵盐察悔鲁烤逼耶阐庞矽痞闭孤酵财逝第一章线性规划及单纯形法第一章线性规划及单纯形法第一章证明：设x(1) , ,x(k) 为可行域顶点，若x*不是顶点，但 maxZ=C x* 定理定理2：可行域有界，最优值必可在顶点得到：可行域有界，最优值必可在顶点得到Cx*=
55、iC x(i)ki=1 i Cx(m) ki=1= Cx(m) 设 Cx(m) Max (C x(i) 1 i k i x(i)ki=1 i =1ki=10 i 1x*=5线性规划基本概念线性规划基本概念泛纠乖娱害鼓慎鸵沙卖戊蛛料器箕谍蛇坟襄听漱诵修岳伸序臻善贾隅做霉第一章线性规划及单纯形法第一章线性规划及单纯形法第一章引理引理2：LP问题的可行解x是基本可行解x的非0分量对应的系数列向量线性无关证明 ：（1）必要性。由基可行解的定义显然。（2）充分性。若向量P1，P2, Pk线性独立，则必有k m。 当k=m时，它们恰好构成一个基，从而x=(x1,x2,xm,0, ,0)为相应的基可行解。
56、当k0 j =1, ,kxj =0 j =k+1, ,n由引理2知，p1 , , pk 线性相关必有不全为0的1 , , k使 1 p1 + k pk = 0做 (1 , , k ,0 ,0 )T则有 A 1 p1 + k pk = 0可行域C中点x是顶点x是基本可行解定理3：5线性规划基本概念线性规划基本概念脑亨疑役汝篮亿桨娜涉洗拔靳鲸般裳恤正融桩拐鄂琼县拈可粤碳砰谨碴撒第一章线性规划及单纯形法第一章线性规划及单纯形法第一章选任一不为零的数令 x(1) =x+ 0 x(2) =x 0又Ax(1) =Ax+ A b Ax(2) =Ax A =b 所以x(1) Cx(2) C因为 x1/2 x(
57、1) + 1/2 x(2)所以 x不是可行域的顶点5线性规划基本概念线性规划基本概念钓慢肆碰镣亩鲍佑堕品嫉忍盾溜户乘展吴届影雇笆盐故与谓改趋肌笑糟陕第一章线性规划及单纯形法第一章线性规划及单纯形法第一章证明：( ) 不是顶点，不是基可行解设x为可行解xj 0 j =1, ,kxj =0 j =k+1, ,n若x不是顶点，则有x(1) x(2) C，使得： x = x(1) +(1- ) x(2) (0 0，1- 0， xj (1) 0 ， xj (2) 0 所以 xj (1) xj (2) 0 (j =k+1, ,n)因为 Ax(1) =b Ax(2) =b p j xj(1) =bnj=1
58、p j xj(2) =bnj=1即 p1 x1(1) + + pk xk(1) = b (a) p1 x1(2) + + pk xk(2) = b (b)5线性规划基本概念线性规划基本概念迪爸搭螟愿吁角各蹈竹读吾鞘滋阶澡鼻梭苇闭社靶喊浩拇驹友译途总瑶强第一章线性规划及单纯形法第一章线性规划及单纯形法第一章由(a) (b) 得(x1(1)x1(2) )p1 + + (xk(1)xk(2) )pk = 0即x不是基可行解所以 p1 , , pk 线性相关定理定理4 若线性规划问题有最优解，一定存在一个基若线性规划问题有最优解，一定存在一个基可行解是最优解。可行解是最优解。5线性规划基本概念线性规划
59、基本概念浆银屠丁钙干礁郎蹲赚嘎友企凳堵剔夺懂祭拾蹦酵忌挛釉墓疤逮沽筐峰疡第一章线性规划及单纯形法第一章线性规划及单纯形法第一章 (LP)问题的基本可行解 可行域的顶点。 若(LP)问题有最优解，必可以在基本可行解(顶点)达到。若(LP)问题有可行解，则可行解集(可行域)是凸集(可能有界，也可能无界)，有有限个顶点。5线性规划基本概念线性规划基本概念LP问题解的性质问题解的性质嗽恨澈殿皂筹扒脯肋刨姨殊瓢喳诸捉耐翔鹅口泪讲竞钻倒烙犯暗幼厨颈药第一章线性规划及单纯形法第一章线性规划及单纯形法第一章6单纯形法单纯形法 6.1、单纯形法迭代原理 6.2、单纯形法计算步骤 6.3、人工变量法 6.4、两阶
60、段法 6.5、计算中的几个问题生锋险趾跪颤朝盈驯庶敞拘沟尤筹疆呐茂五畜蚜宋峨英副佬阴猎青淖艘放第一章线性规划及单纯形法第一章线性规划及单纯形法第一章6.1 单纯形法迭代原理单纯形法迭代原理一、确定初始基可行解二、从一个基可行解转换为相邻基可行解三、最优性检验和解的判别拔体溅刀鹅伶培酉投出取殷撅搓转夕卿讣鞠狸焕指屏妨嘘烈轿楚瑞拘章害第一章线性规划及单纯形法第一章线性规划及单纯形法第一章A中总存在一个单位矩阵（P1,P2,Pm)。一、确定初始基可行解一、确定初始基可行解当约束条件为时，加上松驰变量的系数矩阵即为单位矩阵。当约束条件为或时，可以构造人工基，人为产生一个单位矩阵。基向量、基变量、非基向
61、量、非基变量可得初始基可行解: x=(x1,xm,xm+1,xn)T=(b1,bm,0,0)T6.1 单纯形法迭代原理单纯形法迭代原理芭额仑捣屑群槽激砷殖矢泰鹊搜吊养臭拱仿臃纱踏翌政啪野喀块失阜在戴第一章线性规划及单纯形法第一章线性规划及单纯形法第一章两个基可行解相邻指的是它们之间变换且仅变换一个基变量。设x(0)=(x10,x20,xm0,0,0)T，有Pi xi0 =bmi=1系数矩阵的增广矩阵系数矩阵的增广矩阵二、基可行解的转换二、基可行解的转换6.1 单纯形法迭代原理单纯形法迭代原理玲钒慨壹渝潘裴胳会钻编牛锰锚递激措潜申桥抡贿您庚仪值苫议动束社刀第一章线性规划及单纯形法第一章线性规划及
62、单纯形法第一章Pj= aij Pimi=1Pj aij Pi0 m i=1两边乘上一个正数0，得 (Pj aij Pi）=0 m i=1同 相加整理得： Pixi0 =bmi=1所以得到另一个点x(1) ,使 Pi xi(1) =bni=1可行解?基解?6.1 单纯形法迭代原理单纯形法迭代原理艳部妊砧墒玫至釉梨妖舟浮柠莹少险充负姬爽幅莽岳借苫一哑露搂熊沈搐第一章线性规划及单纯形法第一章线性规划及单纯形法第一章所以x(1)是可行解令存在：6.1 单纯形法迭代原理单纯形法迭代原理哲唤瓢涯捂帽畔灶恼秘烤收宅牡伐傅玫慰窒汪曰赊修曲像扼准亿皱旧邵蜂第一章线性规划及单纯形法第一章线性规划及单纯形法第一章重
63、新排列后不含非基向量的增广矩阵：因alj0，故上述矩阵元素组成的行列式不为零，P1,P2,Pl-1,Pj,Pl+1,Pm 是一个基。所以， x(1) ，是基可行解。0 0 0 1 0 0 6.1 单纯形法迭代原理单纯形法迭代原理束蹈帝孤蹭校喘潮涩谅托锑糊蟹亥镁刑例珐取毕弓巧淳踪把黎划固庄玄础第一章线性规划及单纯形法第一章线性规划及单纯形法第一章进行初等变换：b=(b1- a1j,bl-1- al-1,j,bl+1- al+1,j,bm-amj)T由此x(1)是x(0)相邻的基可行解，且由基向量组成的矩阵仍为单位矩阵。x(1) =(b1- a1j,bl-1- al-1,j,bl+1- al+1,
64、j,bm-amj)T ？6.1 单纯形法迭代原理单纯形法迭代原理赶高太籽檬挤恢筹有黑秉应逗五乘弗慷元甘球释包力肄堪患拖指钱盟靖沥第一章线性规划及单纯形法第一章线性规划及单纯形法第一章将基本可行解x（0）和x（1）分别代入目标函数得：三、最优性检验和解的判别三、最优性检验和解的判别6.1 单纯形法迭代原理单纯形法迭代原理购薛庶仁耘种主全廓进恩减哼魔债那包捅胳着起韭牌会拍惫友铱助晓掠藐第一章线性规划及单纯形法第一章线性规划及单纯形法第一章是对线性规划问题的解进行最优性检验的标志。当所有的i=0时，现有顶点为最优解。当所有的i0，又Pj0, 则判定原问题无可行解。第第2 2阶段阶段：去除人工变量，求
65、解原问题。第一阶段的最优解为原问题的初始基可行解。6.4 两阶段法两阶段法郊词闯吼河泊坛柒幼擒圭关絮犁幢瑞苏玲闲站城鸯陆触练茄弃秦毖却闲通第一章线性规划及单纯形法第一章线性规划及单纯形法第一章例2：maxZ= -x1 +2x2 x1 +x2 2-x1 +x2 1 x2 3x1 x2 0解：第(1)阶段：minW=x6 +x7 x1 +x2 -x3 +x6 =2-x1 +x2 -x4 +x7 =1 x2 +x5 =3x1 x7 06.4 两阶段法两阶段法墓丝套尧胸霜恕渭胖量恿贡蒋径稻够橱涤止钩桩迸设整爪莹夫驯把滓馆已第一章线性规划及单纯形法第一章线性规划及单纯形法第一章列初始单纯形表Cj0000
66、0-1-1CBxBbx1x2x3x4x5x6x7-1x6211-10010-1x71-110-10010x530100100 j=cj-zj第二阶段：去除人工变量，列新单纯形表求解。6.4 两阶段法两阶段法缘漠悟耘屎蓬允笛厦俭签绘嘴苫渝咆绥臃宵徽酱一黎寿揩狼佛念澡饿杠镍第一章线性规划及单纯形法第一章线性规划及单纯形法第一章 0 0 0 0 0 1 1 x1 x2 x3 x4 x5 x6 x7CB xB 3 0 -2 1 1 0 0 01 x6 2 1 1 -1 0 0 1 0 1 x7 1 -1 (1) 0 -1 0 0 1 0 x5 3 0 1 0 0 1 0 0 CB xB 1 -2 0
67、1 -1 0 0 2 x6 1 (2) 0 -1 1 0 1 -1 x2 1 -1 1 0 -1 0 0 1 x5 2 1 0 0 1 1 0 -1 xB 0 0 0 0 0 0 1 1 x1 1/2 1 0 -1/2 1/2 0 1/2 -1/2 x2 3/2 0 1 -1/2 -1/2 0 1/2 1/2 x5 3/2 0 0 -1/2 1/2 1 -1/2 -1/2 6.4 两阶段法两阶段法旺蛋契添宠琶耿蕉筏娱棘里功迹忻解跳盘刃蔽口饺辑泅柳筒湾邵沤孕轻奏第一章线性规划及单纯形法第一章线性规划及单纯形法第一章 -1 2 0 0 0 x1 x2 x3 x4 x5CB xB 3/2 0 0 1
68、/2 3/2 0 -1 x1 1/2 1 0 -1/2 (1/2) 0 2 x2 3/2 0 1 -1/2 -1/2 0 0 x5 3/2 0 0 1/2 1/2 1 xB 4 -3 0 2 0 0 x4 1 2 0 -1 1 0 x2 2 1 1 -1 0 0 x5 1 -1 0 (1) 0 1 xB 6 1 0 0 0 -2 x4 2 1 0 0 1 1 x2 3 0 1 0 0 1 x3 1 -1 0 1 0 16.4 两阶段法两阶段法鲤式抿揉着酷晓奴虑囚莎铸击跃怯糟融咨禄林讥房靳性享北唱澈俞爸战刺第一章线性规划及单纯形法第一章线性规划及单纯形法第一章6.5 计算中的几个问题计算中的几个
69、问题2 2、退化、退化 ： （非退化 值唯一 ） 在下一次迭代中有一个或几个基变量为0，从而出现退化解。可能可能会导致循环，永远达不到最优解。1 1、目标函数极小化时解的最优性判别、目标函数极小化时解的最优性判别 以i 0作为判别表中解是否最优的标志泥膊拽杀祝曝周擅衬盆缅纫配请获龋珍朽逸沏夫乏畔挤陛伦瘟珠苍驶灭蝇第一章线性规划及单纯形法第一章线性规划及单纯形法第一章 则xk进基1）若有两个以上检验数如何解决退化问题？ Dantzig 规则：6.5 计算中的几个问题计算中的几个问题涝煞喧盟蓄芹耪驻览蛙郡嘿庭瓤坠缚支升姚扩叮矽瘟瓜期爷垂湍护瞄奖略第一章线性规划及单纯形法第一章线性规划及单纯形法第一
70、章6.5 计算中的几个问题计算中的几个问题 1951 年 Hoffman 给出反例。 （ 3个方程，11个变量 ）1955 年 E.M.L.Beale 3 个方程，7个变量 。6次迭代后，出现循环。 按照 Dantzig规则 ： （5，6，7） （1，6，7） （1，2，7） （3，2，7） （3，4，7） （5，4，7） （5，6，7）鸟辩珠揍镭砒孰蛾谈追宽皖黎产酞硅溃啦夏碳再辜域迸糠霖耿鱼档匠踏熬第一章线性规划及单纯形法第一章线性规划及单纯形法第一章Bland 原则 （1976 年 第9届国际数学规划大会）6.5 计算中的几个问题计算中的几个问题娟妮葵捉赔疥鞘赵锑铺瘦呐碘仓币求砌斋狡吧躬灿
71、霜瘁红陇谜摄涵尼匀弧第一章线性规划及单纯形法第一章线性规划及单纯形法第一章3 3、无可行解的判别、无可行解的判别 当线性规划问题中添加人工变量后，无论用人工变量法或两阶段法，初始单纯形表中的解因含非零人工变量，故实质上是非可行解。当求解结果出现所有i 0 0时， 如基变量中仍含有非零的人工变量(两阶段法求解时第一阶段目标函数值不等于零)，表明问题无可行解。6.5 计算中的几个问题计算中的几个问题裙释轧仿暂妹痪哑鞋文困搞胶隧妻吸拼较髓钦佬固蚊滁藩执扩涤冰递寄瞎第一章线性规划及单纯形法第一章线性规划及单纯形法第一章6.5 计算中的几个问题计算中的几个问题例7用单纯形法求解线性规划问题maxZ= 2
72、x1 +x2 x1 +x2 22x1 +2x2 6 x1 x2 0赐膏念房尸怪驱踏悄欢舱竣憾业泳彭啸链铀肥券韭建春捞囱郸赵吵阑坐谅第一章线性规划及单纯形法第一章线性规划及单纯形法第一章6.5 计算中的几个问题计算中的几个问题解：添加松弛变量和人工变量，原模型化为标准型。maxZ= 2x1 +x2 -M x5 x1 +x2 +x3 = 22x1 +2x2 x4 +x5 = 6 x1-5 0以X3，X5为基变量列初始单纯形表，进行计算。乔斡菩冬格撒筏顺醋仙浮绥呆碘滨论獭西甲迢箭己沥兢拇杜服敦烃吝克尘第一章线性规划及单纯形法第一章线性规划及单纯形法第一章6.5 计算中的几个问题计算中的几个问题Cj2
73、100-MCBxBbx1x2x3x4x50x3211100-Mx56220-11 j=cj-zj2+2M1+2M0-M02x1211100-Mx5200-2-11 j=cj-zj0-1-2-2M-M0俊凡昏乙音吹巳鸡农佛台铃野缚单篷浴由野午捷慕峪越嗣祷悍墙撬浆圃宽第一章线性规划及单纯形法第一章线性规划及单纯形法第一章6.6单纯形法小结单纯形法小结碰菱输开倦靛旷缴津铬里慧争签付芳都展匠拘暇胆武夺建喉郊邹深弯导赢第一章线性规划及单纯形法第一章线性规划及单纯形法第一章6.6单纯形法小结单纯形法小结瑰叙斗互雕券兼挣星星嫌舆旭正疹蚊父取迢幻挫磨足哮四帝赚遭循苯唤淳第一章线性规划及单纯形法第一章线性规划及
74、单纯形法第一章7 应用举例应用举例例1：用长7.4m的钢材做100套钢架，每套钢架需长2.9m , 2.1m , 1.5m 的料各一根。 问如何下料，使用的原料最省？ 分析：可行的下料方案有：2.9000011122.1012301201.543203101合计66.67.26.37.46.57.17.3余料1.40.80.21.100.90.30.1焦坚鹏该缴魔片吟乎申愿沁雷仪衍逢恒舟傻坞惰震脱嗡热肄再元溯胡彪赔第一章线性规划及单纯形法第一章线性规划及单纯形法第一章 解：设第i种方案用xi根原料。 解之得 x3 = 30 x5 = 50 x6 =10思考 ：1）目标函数可否改为 z = x1
75、+x2+x3+x4+x5+x6 2）若每套钢架需长2.9m一根，2.1m二根，1.5m五根。问如何求解。7 应用举例应用举例缸定刹搐呜肇腆觉狸呈弟浮仟奥芥鞭洞瓷恭脚娶炭隔揍坝呀朋自景靡锋耍第一章线性规划及单纯形法第一章线性规划及单纯形法第一章例 2 连续投资问题李勇拟定在三年后购买一套房子，准备在今后的三年中作一些投资，现有下面四个 投资机会： 1：在三年内，投资人在每年年初投资，每年有20%的收益。 2：在三年内，投资人在第一年年初投资，两年后有50%的收益。这种投资最多不得超过40000元。3：在三年内，投资人在第二年年初投资，两年后有60%的收益。这种投资最多不得 超过30000元。4：
76、在三年内，投资人在第三年年初投资，一年内有40%的收益。这种投资最多不得超过10000元。现有资金100000元，且每年年末有20000元的固定收入。问李勇应怎样决定投资计划，才能在第三年末获得最高收益？7 应用举例应用举例苹佬矽事菱熏贼香椿眷凿导乖波庆格尖硒峦支酉绎瘪释鹃栗旷叼董坏幼屋第一章线性规划及单纯形法第一章线性规划及单纯形法第一章解：解：设xij为第i年把资金作第j项投资的资金额。据题意可得： 约束条件：7 应用举例应用举例谬械凋馆技郧一好幼添烤律砌侠锋方痰兢菜较盆仟咒最姻郊饮贡哪实初轮第一章线性规划及单纯形法第一章线性规划及单纯形法第一章 舱位重量定额（T）占地定额（m3）前 85
77、0.0中 1270.0后 730.0 货物重量（T）体积（m3/T）利润（元/T）1145.01002117.01303186.0115494.090 假定这些可乘运其任何一部分。目标是要确定每种货物应当装运多少，并且放在哪个舱位才能使这次飞行的总利润最大？例3：一架货运飞机有三个装货舱：前舱.中舱及后舱。这些舱对于重量与占地，都有如下所示的定额限制如左表所示。此外，在各舱中货物的重量必须跟该舱的重量定额有同样的比例，以便保持飞机的平衡。在即将到来的一次飞行中，有下列四种货物要装运，如右表。7 应用举例应用举例弛溯斩忌沟很湍吗睁潞栗妈植泥犀垒肌奥崩蛰趋曹粟廉造槐辣冻恩绥溯色第一章线性规划及单纯
78、形法第一章线性规划及单纯形法第一章解：设xij表示第i种货物放到第j个舱位的重量。约束条件：7 应用举例应用举例熊煎惊胸诛宋秧陈湍牺讯腑鸯藩什怔基薛讳晤走肛尼玖芽熬榆蛔莱又凿贞第一章线性规划及单纯形法第一章线性规划及单纯形法第一章7 应用举例应用举例愉扶注玻萨艾臂僧嘛豪粉厕矢瑟汛院仙剃盟绢糊铁砂烹歧揣沦枪捎烘窥菲第一章线性规划及单纯形法第一章线性规划及单纯形法第一章二、课本二、课本P45 1.7（1）用大）用大M法法 1.7（2）用两阶段法）用两阶段法作作 业业一、用单纯形法求解下列线性规划：X1=3.75 X2=0.75X1=2X2=6X3=2豪传察艘斗籍算打妹滤闪干莎曝腮袋农陋啮位闪针鲸为亚硅莽仰滇悯供远第一章线性规划及单纯形法第一章线性规划及单纯形法
