线性规划及单纯形法

《线性规划及单纯形法》由会员分享，可在线阅读，更多相关《线性规划及单纯形法（81页珍藏版）》请在装配图网上搜索。

1、1运筹学Operational Research运筹帷幄，决胜千里运筹帷幄，决胜千里 2绪 论一、运筹学发展简介一、运筹学发展简介二、运筹学的特点及研究对象二、运筹学的特点及研究对象三、运筹学的工作步骤三、运筹学的工作步骤四、运筹学内容介绍四、运筹学内容介绍3一、运筹学（一、运筹学（OROR）发展简介）发展简介 运筹学在国外运筹学在国外 英国称为英国称为 Operational Research 美国称为美国称为 Operations Research 起源于二战期间的军事问题，如雷达的设置、运输起源于二战期间的军事问题，如雷达的设置、运输船队的护航舰队的规模、反潜作战中深水炸弹的深船队的护航

2、舰队的规模、反潜作战中深水炸弹的深度、飞机出击队型、军事物资的存储等。度、飞机出击队型、军事物资的存储等。 二战以后运筹学应用于经济管理领域（二战以后运筹学应用于经济管理领域（LP、计算机）、计算机） 1948年英国首先成立运筹学会；年英国首先成立运筹学会；1952年美国成立运年美国成立运筹学会。筹学会。 1952年，年，Morse 和和 Kimball出版出版运筹学方法运筹学方法 1959年成立国际运筹学联合会年成立国际运筹学联合会4 运筹学在国内运筹学在国内 中国古代朴素的运筹学思想（田忌赛马、都江中国古代朴素的运筹学思想（田忌赛马、都江堰工程、丁渭修复皇宫）堰工程、丁渭修复皇宫） 195

3、6年中科院成立运筹学小组年中科院成立运筹学小组 1957年正式将年正式将Operations Research命名为命名为“运筹学运筹学” 1958年提出运输问题的图上作业法年提出运输问题的图上作业法（解决粮食合（解决粮食合理运输问题）理运输问题） 1962年提出中国邮路问题年提出中国邮路问题（管梅谷）（管梅谷） 1964年华罗庚推广统筹方法年华罗庚推广统筹方法 1980年中国运筹学学会正式成立年中国运筹学学会正式成立 1982年中国加入国际运筹学联合会年中国加入国际运筹学联合会 1999年年8月我国组织了第月我国组织了第15届大会届大会5齐王赛马（齐王和田忌）齐王赛马（齐王和田忌） 战国时期

4、，齐威王与田忌赛马，规定双战国时期，齐威王与田忌赛马，规定双方各出上中下三个等级的马各一匹。如方各出上中下三个等级的马各一匹。如果按同等级的马比赛，齐王可获全胜。果按同等级的马比赛，齐王可获全胜。田忌的谋士孙膑提出的以下、上、中对田忌的谋士孙膑提出的以下、上、中对齐王的上、中、下对策，使处于劣势的齐王的上、中、下对策，使处于劣势的田忌战胜齐王，这是从总体出发制定对田忌战胜齐王，这是从总体出发制定对抗策略的一个著名事例。抗策略的一个著名事例。6l丁渭主持皇宫的修复（北宋，皇宫因火焚毁） 北宋真宗年间，皇城失火，宫殿烧毁，大臣丁谓主持了皇宫修复工程。他采用了一套综合施工方案: 先在需要重建的大道上

5、就近取土烧砖； 在取土后的深沟中引水，形成人工河，再由此水路运入建筑材料，从而加快了工程进度； 皇宫修复后，又将碎砖废土填入沟中，重修大道。 使烧砖、运输建筑材料和处理废墟三项繁重工程任务协调起来，从而在总体上得到了最佳解决，一举三得，节省了大量劳力、费用和时间。7运筹学为决策机构对所控制的业务活动作决策时，提供以运筹学为决策机构对所控制的业务活动作决策时，提供以数量为基础的科学方法数量为基础的科学方法Morse Morse 和和 KimballKimball运筹学是把科学方法应用在指导人员、工商企业、政府和运筹学是把科学方法应用在指导人员、工商企业、政府和国防等方面解决发生的各种问题，其方法

6、是发展一个科学的国防等方面解决发生的各种问题，其方法是发展一个科学的系统模式，并运用这种模式预测、比较各种决策及其产生的系统模式，并运用这种模式预测、比较各种决策及其产生的后果，以帮助主管人员科学地决定工作方针和政策后果，以帮助主管人员科学地决定工作方针和政策英国英国运筹学会运筹学会运筹学是应用分析、试验、量化的方法对经济管理系统中运筹学是应用分析、试验、量化的方法对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有根人力、物力、财力等资源进行统筹安排，为决策者提供有根据的最优方案，以实现最有效的管理据的最优方案，以实现最有效的管理中国百科全书中国百科全书现代运筹学涵盖了一切领域

7、的管理与优化问题，称为现代运筹学涵盖了一切领域的管理与优化问题，称为 Management ScienceManagement Science运筹学的定义运筹学的定义二、运筹学的特点及研究对象二、运筹学的特点及研究对象8运筹学的特点：运筹学的特点：优化：从全局观点看问题，追求总体效果最优优化：从全局观点看问题，追求总体效果最优量化：通过建立和求解模型使问题在量化的基础量化：通过建立和求解模型使问题在量化的基础 上得到合理决策上得到合理决策综合：多学科交叉综合：多学科交叉运筹学的研究对象：运筹学的研究对象：生产与经济等各种实践活动中提出来的实际问题生产与经济等各种实践活动中提出来的实际问题二、运

8、筹学的特点及研究对象二、运筹学的特点及研究对象9三、运筹学的工作步骤三、运筹学的工作步骤明确问题明确问题建立模型建立模型设计算法设计算法整理数据整理数据求解模型求解模型评价结果评价结果简化？简化？ 满意？满意？YesNoNo 明确问题明确问题 建立模型建立模型 设计算法设计算法 整理数据整理数据 求解模型求解模型 评价结果评价结果10四、运筹学内容介绍四、运筹学内容介绍 线性规划及单纯形法线性规划及单纯形法 对偶理论及灵敏度分析对偶理论及灵敏度分析 运输问题运输问题 整数规划整数规划 动态规划动态规划 图与网络分析图与网络分析 11第一章第一章 线性规划及单纯形法线性规划及单纯形法 1939年

9、年 苏苏 康托洛维奇发表康托洛维奇发表 “生产组织与计划生产组织与计划中的数学方法中的数学方法”，1960年出版年出版“最佳资源利用最佳资源利用的经济计算的经济计算”获诺贝尔经济学奖获诺贝尔经济学奖 1941年年 美美 Hichcock提出运输问题提出运输问题 1947年年 美美 丹捷格（丹捷格（G.B.Dantzig）提出单纯形）提出单纯形法，法，1963年出版年出版“线性规划及其扩展线性规划及其扩展” 在生产管理中如何有效地利用现有人力、物力完管理中如何有效地利用现有人力、物力完成更多的任务，或在预定的任务目标下，如何耗用成更多的任务，或在预定的任务目标下，如何耗用最少的人力、物力去实现目

10、标。最少的人力、物力去实现目标。12 0,12416482. .32max:21212121xxxxxxtsxxZOBJ第一节第一节 线性规划问题及数学模型线性规划问题及数学模型例例1 生产计划问题生产计划问题 (P4) I II 资源限量资源限量设设 备备 1 2 8台时台时 原材料原材料A 4 0 16公斤公斤原材料原材料B 0 4 12公斤公斤单位利润单位利润 2 3 设设I I、IIII两种产品的产量分别为两种产品的产量分别为x1, x2 。建立该问题的数学模型为：建立该问题的数学模型为：目标函数目标函数约束条件约束条件决策变量决策变量一、实例一、实例13例例2 合理下料问题合理下料问

11、题现要做现要做100套钢架，每套需套钢架，每套需2.9米、米、2.1米和米和1.5米的圆钢米的圆钢各一根。已知原料长各一根。已知原料长7.4米，问如何下料，使用的原料米，问如何下料，使用的原料最少（余料最少或根数最少）？最少（余料最少或根数最少）？解解：设：设 x1, x2 , x3, x4 , x5分别代表五种不同的原料用分别代表五种不同的原料用量方案（余料最少）量方案（余料最少）14方案方案2.9米米2.1米米1.5米米合计合计余料余料x11037.40 x22017.30.1x30227.20.2x41207.10.3x50136.60.816; 050010300,1003231002

12、21002.8 . 03 . 02 . 01 . 00:5432154321532154342154321 OBJxxxxxxxxxxxxxxxxxxxxtsxxxxxMinZOBJ，解解得得：决策变量？决策变量？目标函数？特点？目标函数？特点？约束条件？约束条件？决策方案？决策方案？最优方案？最优方案？最优值？最优值？15二、总结二、总结 目标函数用决策变量的线性函数来表示。按问题目标函数用决策变量的线性函数来表示。按问题的不同，要求目标函数实现最大化和最小化。的不同，要求目标函数实现最大化和最小化。线性规划问题（线性规划问题（LP问题）的共同特征：问题）的共同特征： 每一个问题变量都用一组

13、决策变量（每一个问题变量都用一组决策变量（x1, x2, , xn）表示某一方案，这组决策变量的值代表一个具体方表示某一方案，这组决策变量的值代表一个具体方案，这些变量是非负的。案，这些变量是非负的。 存在一定的约束条件，这些约束条件可以用一组存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。线性等式或线性不等式来表示。线性规划模型的一般形式与标准形式（线性规划模型的一般形式与标准形式（P7稍后讲）稍后讲）16三、两变量线性规划问题的图解法三、两变量线性规划问题的图解法1. 线性不等式的几何意义线性不等式的几何意义 半平面半平面2132xx 212xx 2作出作出LP问题的

14、可行域问题的可行域作出目标函数的等值线作出目标函数的等值线移动等值线到可行域边界得到最优点移动等值线到可行域边界得到最优点2. 图解法步骤图解法步骤172132xx 212xx 0,12416482. .32max:21212121xxxxxxtsxxZOBJ4x1=164x2=12x1+2x2=8x1x248430例例1 （书（书P4）：）：Q(4,2)Z=2x1+3x2 做目标函数做目标函数2x1+3x2的等值线，与的等值线，与阴影部分的边界相交于阴影部分的边界相交于Q(4,2)点，点，表明最优生产计划为：表明最优生产计划为：生产生产I产品产品4件，生产件，生产II产品产品2件。件。最大利

15、润：最大利润：14.基本概念：基本概念：可行解、可行域、最优解？可行解、可行域、最优解？18例例21187654322x1876543O109x2A BCEDFGH123f(x)=0f(x)=12 0,78102.46max212212121xxxxxxxtsxxZ1187654322x1876543O109x2A BCEDFGH123Z=363662:21 Zxx最优解最优解193. 图解法的作用图解法的作用 能解决少量问题能解决少量问题LPLP问题问题有可行解有可行解有最优解有最优解唯一解唯一解无穷多解无穷多解无最优解（可行域为无界）无最优解（可行域为无界）无可行解（无解）无可行解（无解）

16、规律规律1： 揭示了线性规划问题的若干规律揭示了线性规划问题的若干规律见见P9-10 例题例题20结论：结论：若若LP问题有最优解，则要么最问题有最优解，则要么最优解唯一，要么有无穷多最优解。优解唯一，要么有无穷多最优解。scknmaksakscasdjknklajskdghgklkldsjln是是最最优优解解。则则）（）（，且且又又）（）（则则，）（作作，则则有有问问题题的的解解是是不不妨妨设设证证明明：）（）（）（）（）（）（）（）（）（）（）（）（XZ1ZX1XCXC0Xbb1bX1XAXA10X1XXXCZ0XbAXXCZ0XbAXLPXX0XbAX. t . sXCMaxZ*21TT

17、21212T*21T*121T 21 规律规律2： 线性规划问题的可行域为一凸集线性规划问题的可行域为一凸集 线性规划问题凸集的顶点个数是有限的线性规划问题凸集的顶点个数是有限的 最优解肯定可在凸集的某顶点处达到最优解肯定可在凸集的某顶点处达到 的的一一个个顶顶点点。为为，则则，）（使使得得，若若不不存存在在两两点点为为凸凸集集，）顶顶点点：设设（）（）（）（）（）（）（）（SXXXXSXXSXS02102101012 基本概念基本概念为为一一凸凸集集。，则则，）（若若，点点维维空空间间一一点点集集，任任取取两两为为）凸凸集集：设设（）（）（）（）（KKXXKXXnK10112121 22四、

18、四、 线性规划问题的标准线性规划问题的标准型型112211112211211222221122max( )( ). .( )0,1,2,0,1,2,:; :; :; :; :nnnnnnmmmnnmjijiijZc xc xc xa xa xa xba xaxaxbs taxaxaxbxjnbimnmcba 变量个数约束行数价值系数右端项技术系数1. 一般形式一般形式23112211112211211222221122max. .0,1,2,0,1,2,maxCX. . 0nnnnnnmmmnnmjiZc xc xc xa xa xa xba xaxaxbs taxaxaxbxjnbimZs

19、t AXbX矩阵形式：2. 标准型标准型LP模型的各种表模型的各种表示法见示法见P7243. 所有所有LP问题均可化为标准型问题均可化为标准型)0.(,)0,0( ;0)3(3 jnjjjjjjjjjjjjjjxabxxabxaxxbxaxxxxxxxxx令令若若无无限限制制，令令若若，令令若若CXZMaxCXMinZZZ ，令令)1( 为为剩剩余余变变量量为为松松弛弛变变量量等等式式约约束束条条件件将将不不等等式式约约束束条条件件化化为为0,0,)2(2211ninjijijijninjijijijxbxxabxaxbxxabxa 0, 0, 0)4(ijijijijibxabxab则则若若

20、1.目标函数最大化目标函数最大化2.约束条件为等式约束条件为等式3.变量约束为非负变量约束为非负4.约束右端项非负约束右端项非负25例例1 0,12416482.3221212121xxxxxxtsxxMaxZ )5 , 1( 01241648200032524132154321jxxxxxxxxxxxxxMaxZj可化为可化为26例例2 化标准型化标准型型型即即可可得得到到该该问问题题的的标标准准改改为为求求，把把求求令令以以满满足足非非负负约约束束条条件件；号号两两端端同同乘乘以以在在第第三三个个约约束束条条件件号号的的左左端端减减去去剩剩余余变变量量在在第第二二个个约约束束不不等等式式号

21、号的的左左端端加加入入松松弛弛变变量量在在第第一一个个约约束束不不等等式式；，令令其其中中令令;, 1;0;0, 0,7622254543ZMaxMinZZZxxxxxxxxxx 无无约约束束例例：321321321321321, 0, 053327.32xxxxxxxxxxxxtsxxxMinZ27 0;4 ,2,1,0417431432.42;8424040,2343321321321321434333xjxxxxxxxxxtsxxxZMaxxxxMaxZxxxxxxj即即所所以以，满满足足；且且则则有有解解：令令课堂作业课堂作业 62 , 0,25432032.4232132132132

22、1xxxxxxxxxtsxxxMaxZ28五、标准型五、标准型LPLP问题的解问题的解问问题题的的一一个个基基。为为），则则称称非非奇奇异异矩矩阵阵（的的为为问问题题的的系系数数矩矩阵阵，为为设设基基问问题题的的最最优优解解；）的的可可行行解解，为为满满足足（最最优优解解）的的解解；）、（满满足足（可可行行解解其其中中，LPB0BAB,m)A(rLPALP132)m)A(r,nm( ,aaaaaaaaaA,xxxX,cccC)3(0X )2(bAX. t . s)1(XCMaxZmmnmmn2m1mn22221n11211n21n21T LP模型向量模型向量表示法见表示法见P729121231

23、241234561624359. .0,1, 2,3, 412101211,3501353010212010,31505101jM axZxxxxxxxxs txjABBBBBBBBLP引 例 ：均 为问 题 的 基 。30令令B = =( P1 , P2 , , Pm ) 且且| B | 0 ，称，称A中基中基B对应的列向量对应的列向量Pj (j=1,2,m) 为基向量。为基向量。与基向量与基向量Pj对应的变量对应的变量xj称为称为基变量基变量，记为记为XB = ( x1 , x2 , , xm )T，其余的变量称为其余的变量称为非基变量非基变量，记为，记为 XN = ( xm+1 , xm

24、+2 , , xm+n ) T 。 mmm12m1m1211aaaaaa为为非非基基变变量量。、为为一一组组基基变变量量，、则则对对应应的的，如如在在上上例例中中，41324xxxx0512B 基变量：基变量：31基本解基本解令非基变量令非基变量 XN = 0，求得的一组基变量求得的一组基变量 XB的值称为基本解。的值称为基本解。 基可行解（顶点）基可行解（顶点）既是基本解，又是可行解。既是基本解，又是可行解。基最优点基最优点既是基本解，又是使目标函数值达到最优的解既是基本解，又是使目标函数值达到最优的解32如引例中：如引例中： 基基 基变量基变量 非基变量非基变量 基本解基本解 是否可行是否

25、可行 目标函数值目标函数值ZB1 x1,x2 x3,x4 （-2，3，0，0） 否否B2 x1,x3 x2,x4 （3，0，1，0） 是是 Z=3 B3 x1,x4 x2,x3 （4，0，0，-3） 否否 B4 x2,x3 x1,x4 （0，9/5，2/5，0） 是是 Z=9/5B5 x1,x4 x2,x3 （ 2，0，0，-1） 否否B3 x3,x4 x1,x2 （0，0，4，9） 是是 Z=01212312424359. .0,1,2,3,4jMaxZxxxxxxxxstxj33 线性规划标准型问题解的关系线性规划标准型问题解的关系约束方程的约束方程的解空间解空间基解基解可行解可行解非可行

26、解非可行解基可基可行解行解LP解的基本解的基本定理见定理见P1234第二节第二节 单纯型法单纯型法 一、基本思想一、基本思想化化LP问题为标准型，问题为标准型，确定一个初始基本可行解确定一个初始基本可行解检验解的检验解的最优性最优性结束结束Y枢轴运算（旋转运算）枢轴运算（旋转运算）确定另一个基本可行解确定另一个基本可行解N35二、枢轴运算二、枢轴运算1231213122210(1)336(2)zxxxxxxxxx例 ： max 以为 枢 轴 元 素为为枢枢轴轴元元素素以以233223221112/ )1( ,)1()2(x)2()1(95x2xxxx0 x32 6xxx08xx0 x33421

27、33521)2( , 3)2()1(32 基本解（8，-6，0） （不可行）36又如：又如：1231213122210(1)336(2)zxxxxxxxxx例 ： max 以为 枢 轴 元 素2312(2) (1),(1)/23123323125(1)209(2)xxxxxxx以 为枢轴元素1231235104239042xxxxxx 基本解（1/2，0，9/2） （可行,是否最优？）2xz=5-2 （当前解是最优？）37三、检验数的意义三、检验数的意义1111111111(1)(2)0331TBNBNBNBNBTTTTTTTBNBBNNBNNNNTTTTBNBNBjMaxZC XAXbBNX

28、XXBXNXbB BXB NXB bXB bB NXXZC XCCC XC XCB bB NXC XXC B bCC B NXC B bC令为基，为非基；为基变量，为非基变量，有（ ）把（ ）代入（）得（，）（）（）（11000,0jTBjjxTjBjjC B PXCC B PZZZ为非基变量）若则，即为最优解。（基变量检验数一定为 ）分分非非必必要要性性）问问题题已已得得最最优优解解。（充充则则该该，到到某某步步时时，所所有有检检验验数数问问题题通通过过单单纯纯型型法法迭迭代代结结论论：如如果果LPLP0 P1738四、单纯形表四、单纯形表11111111( ) 0TTTBBTTTNBBBA

29、B bT Bcc BAc B bIB NB bcc B Nc B b基变量非基变量常数项约束方程增广矩阵检验数+目标函数值P1739第三节第三节 单纯型法的步单纯型法的步 骤骤一、步骤一、步骤化化LP问题为标准型问题为标准型,建立初始单纯型表建立初始单纯型表; 为为进进基基变变量量；所所对对应应变变量量，选选取取计计算算则则，则则最最优优解解已已达达到到，否否若若所所有有检检验验数数kkjjkxMax 0|,0. 2 ;,0|.3为为出出基基变变量量所所对对应应变变量量选选取取计计算算lllklikikilxabaabMin .2,. 4步步转转第第算算为为枢枢轴轴元元素素进进行行枢枢轴轴运运

30、以以lka1TjjBjCC B P直接求最小化问题，P23说明40二、用单纯形表求解二、用单纯形表求解LP问题实例问题实例 0,121684243221221121xxxxxxxxMaxZ化为标准型化为标准型 5 , 4 , 3 , 2 , 1, 01241648232524132121jxxxxxxxxxxMaxZj例例1.1.41单纯型表单纯型表算法步骤：算法步骤： Cj 2 3 0 0 0 CB XB b X1 X2 X3 X4 X5 0 X3 0 X4 0 X5 8 1612 1 2 1 0 0 4 4 0 0 1 0 - 0 4 0 0 1 3 0 2 3 0 0 0 j 以以4为枢

31、轴元素进行旋转运为枢轴元素进行旋转运算，算，x2为换入变量，为换入变量，x5为换出为换出变量变量Cj 2 3 0 0 0 CB XB b X1 X2 X3 X4 X5 0 X3 0 X4 3 X2 2 16 3 1 0 1 0 -1/2 2 4 0 0 1 0 4 0 1 0 0 1/4 - -9 2 0 0 0 -3/4以以11为枢轴元素进行运算，为枢轴元素进行运算，x1为换入变量，为换入变量， x3为换出为换出变量变量（1）建立初始单纯形表；（）建立初始单纯形表；（2）求检验数并判断）求检验数并判断最优性，若最优，终止，否则转下一步；（最优性，若最优，终止，否则转下一步；（3）确）确定出基

32、与进基变量；（定出基与进基变量；（4）换基迭代，转入（）换基迭代，转入（2）。）。j 42Cj 2 3 0 0 0 CB XB b X1 X2 X3 X4 X5 2 X1 0 X4 3 X2 2 8 3 1 0 1 0 -1/2 - 0 0 -4 1 2 4 0 1 0 0 1/4 12 -13 0 0 -2 0 1/4 j 以以22为枢轴元素进行运为枢轴元素进行运算，算，x5为换入变量，为换入变量， x4为换出变量为换出变量Cj 2 3 0 0 0 CB XB b X1 X2 X3 X4 X5 2 X1 0 X5 3 X2 4 4 2 1 0 0 1/4 0 0 0 -2 1/2 1 0 1

33、 1/2 -1/8 0 -14 0 0 -3/2 -1/8 0此时达到最优解。此时达到最优解。X*=(4,2), MaxZ=14。430,524261552max212121221xxxxxxxxxz例例2 2440,524261550002max515214213254321xxxxxxxxxxxxxxxz45 2 1 0 0 0 0 15 0 5 1 0 0 0 24 6 2 0 1 0 0 5 1 1 0 0 1 2 1 0 0 0 jcBCbBX1x3x2x4x5x3x4x5x 24/65/1min主元化为主元化为1 1主列单位向量主列单位向量 换出换出 换入换入1x4x表表1：列初始

34、单纯形表：列初始单纯形表 （单位矩阵对应的变量为基变量）（单位矩阵对应的变量为基变量）正检验数中最大者对正检验数中最大者对应的列为主列应的列为主列j 46 2 1 0 0 0 0 15 0 5 1 0 0 2 4 1 2/6 0 1 /6 0 0 1 0 4/6 0 -1/6 1 0 1/3 0 -1/3 0 jcBCbBX1x3x2x4x5x3x1x5x 15/524/26/4min 0*5 2*2/6 +0*4/61- 2/3=表表2：换基：换基 （初等行变换，主列化为单位向量，主元为（初等行变换，主列化为单位向量，主元为1）检验数检验数0确定主列确定主列 最小最小确定主列确定主列主元主元

35、j 47 2 1 0 0 0 0 15/2 0 0 1 5/4 -15/2 2 7/2 1 0 0 1/4 -1/2 1 3/2 0 1 0 -1/4 3/2 0 0 0 -1/4 -1/2 jcBCbBX1x3x2x4x5x3x1x2x min检验数检验数=0=0最优解为最优解为X=(7/2,3/2,15/2,0,0)X=(7/2,3/2,15/2,0,0)目标函数值目标函数值Z=8.5Z=8.5 2*7/2 1*3/2+0*15/28.5表表3：换基：换基 （初等行变换，主列化为单位向量，主元为（初等行变换，主列化为单位向量，主元为1）j 48 2 1 0 0 0 0 15 0 5 1 0

36、 0 0 24 6 2 0 1 0 0 5 1 1 0 0 1 2 1 0 0 0 jcBCbBX1x3x2x4x5x3x4x5x练习练习:一般主列选择正检验数中最大者对应的一般主列选择正检验数中最大者对应的列列,也可选择其它正检验数的列也可选择其它正检验数的列.以第以第2列列为主列为主列,用单纯形法求解。用单纯形法求解。正检验数对应正检验数对应的列为主列的列为主列注：注：1. 几种特殊情形几种特殊情形P20-23； 2. 对于极小化的对于极小化的LP问题，只须改成检验数问题，只须改成检验数0为最优。为最优。j 49第四节第四节 LP问题的进一步讨论问题的进一步讨论一、人工变量法一、人工变量法

37、 0.XbAXtsXCMaxZT 0,. .SSTXXbIXAXtsXCMaxZ501. 大大M法法(M为任意大的正数为任意大的正数) 0,12324112.332131321321321xxxxxxxxxxxtsxxxMinZ例例： 7, 2 , 1; 012324112.0037316532143217654321jxxxxxxxxxxxxxtsxMxMxxxxxMinZj加入松弛变量加入松弛变量x4;剩余变量剩余变量x5;人工人工变量变量x6,x7511) 人工变量的识别人工变量的识别2) 目标函数的处理目标函数的处理 iTiiTVMXCMinZVMVMXCMaxZ)(为为人人工工变变量

38、量，为为3) 计算计算(单纯型法单纯型法)52Cj-31100MMCBXBbx1x2x3x4x5x6x70 x4111-21100011Mx63-4120-1103/2Mx71-20100011-3+6M1-M1-3M0M000 x4103-20100-1-Mx610100-11-211x31-2010001-11-M00M03M-1i j 注意：本例是求最小值，所以用所有注意：本例是求最小值，所以用所有 来判别目标函数是否实现了最小化。因而换来判别目标函数是否实现了最小化。因而换入变量入变量xk的选取标准为的选取标准为0 j0| jjkMinj 53结果得结果得: X*=(4,1,9,0,0

39、,0,0) Z*=2Cj-31100MMCBXBbx1x2x3x4x5x6x70 x4123001-22-541x210100-11-2-1x31-2010001-10001M-1M+1-3x141001/3-2/32/3-5/31x210100-11-21x390012/3-4/34/3-7/30001/31/3M-1/3 M-2/3j i j 即即认认为为达达到到了了最最优优解解。所所有有检检验验数数此此时时,0, j（接上表）（接上表）54 两阶段法两阶段法(将将LP问题分成两个阶段来考问题分成两个阶段来考虑虑) 第第I 阶段阶段: 求解模型（求解模型（1）得到原问题的一个基本可行解。）

40、得到原问题的一个基本可行解。做法是：先不考虑原问题是否存在可行解，给原做法是：先不考虑原问题是否存在可行解，给原LP问题加入问题加入人工变量，并构造仅含人工变量之和的目标函数人工变量，并构造仅含人工变量之和的目标函数w并要求最小并要求最小化；然后用单纯型法求解，若得化；然后用单纯型法求解，若得w=0，则求得原问题的一个基，则求得原问题的一个基本可行解，进行第二阶段计算，否则无可行解。本可行解，进行第二阶段计算，否则无可行解。. (1),0rrMinWyAXIYbstX Y55 第第II 阶段：求解模型（阶段：求解模型（2）得到原）得到原LP问题的最优解。问题的最优解。做法是：将第一阶段得到的最

41、终表除去人工变量，将目标做法是：将第一阶段得到的最终表除去人工变量，将目标函数行的系数换为原问题的系数，作为第二阶段的初始表。函数行的系数换为原问题的系数，作为第二阶段的初始表。. (2)0TMaxZC XAXbstX解的理论见：解的理论见：P24命题命题1.5.1，1.5.256 0,12324112.332131321321321xxxxxxxxxxxtsxxxMinZ例例：加入松弛变量加入松弛变量x4;剩余变量剩余变量x5;人工人工变量变量x6,x7 7, 2 , 1; 012324112.)(73165321432176jxxxxxxxxxxxxxtsIxxMinWj用单纯形法求解第一

42、阶段的结果得：用单纯形法求解第一阶段的结果得：57Cj0000011CBXBbx1x2x3x4x5x6x70 x4111-211000111x63-4120-1103/21x71-201000116-1-301000 x4103-20100-1-1x610100-11-210 x31-2010001-0-1001030 x4123001-22-540 x210100-11-2-0 x31-2010000-0000011i j j j 此时，达到第一阶段的最优解，此时，达到第一阶段的最优解，W=058Cj-31100CBXBbx1x2x3x4x50 x4123001-241x210100-1-1

43、x31-20100-10001-3x141001/3-2/31x210100-11x390012/3-4/30001/31/3i j j 由于人工变量由于人工变量x6 =x7=0,所以（所以（0,1,1,12,0）T是该线性规划问题的基可行解。于是转入第二阶段运算：是该线性规划问题的基可行解。于是转入第二阶段运算：此时达到该此时达到该LP问题的最优解：问题的最优解：x1=4,x2=1,x3=9; 目标函数值目标函数值Z=-2。59二、单纯型法中存在的问题二、单纯型法中存在的问题1. 存在两个以上的最大正检验数。选择存在两个以上的最大正检验数。选择任何变量（对应最大正检验数）作为进任何变量（对应

44、最大正检验数）作为进基变量。基变量。2. 最小比值相同。最小比值相同。LP问题出现退化现象，即基变量取值为问题出现退化现象，即基变量取值为0 0,10321122109841.621204343213432143214321xxxxxxxxxxxxxtsxxxxMaxZ例例：60 7 , 2 , 1;010321122109841.00062120437364321543217654321jxxxxxxxxxxxxxtsxxxxxxxMaxZjCj 3/4 -20 1/2 -6 0 0 0 CBXBbX1X2X3X4X5X6X70X501/4-8-191000X601/2-12-1/23010

45、0X71001000103/4-201/2-6000j 61Cj 3/4 -20 1/2 -6 0 0 0 CBXBbX1X2X3X4X5X6X73/4X101-32-4364000X60043/2-150100X7100100010047/221-300j 选取选取x1为换入变量；按为换入变量；按Bland算法，算法，选取下标最小的选取下标最小的x5为换出变量，得下表：为换出变量，得下表：此时换出变量为此时换出变量为x1，换入变量为，换入变量为x4，迭代后目，迭代后目标函数值不变，继而出现了循环现象，达不标函数值不变，继而出现了循环现象，达不到最优解。到最优解。j Cj 3/4 -20 1/

46、2 -6 0 0 0 CBXBbX1X2X3X4X5X6X73/4X101-32-4364000X60043/2-150100X7100100010047/221-300j 62解决退化的方法有：解决退化的方法有：“摄动法摄动法”、“辞典序法辞典序法”、 Bland规规则等则等1974年年Bland提出提出Bland算法规则：算法规则：为为换换出出变变量量。选选取取下下标标最最小小的的基基变变量量个个以以上上的的最最小小比比值值时时，规规则则计计算算存存在在两两个个和和两两当当按按）（量量。所所对对应应的的变变量量为为进进基基变变则则选选取取 2,0|min)1(kjjk633. 最小比值原则

47、失效最小比值原则失效问问题题有有无无界界解解则则此此对对应应列列向向量量，而而存存在在某某问问题题迭迭代代到到某某步步时时，当当用用单单纯纯型型法法求求解解LPaLPkkk, 00 4 , 3 , 2 , 1; 0432.3242132121jxxxxxxxtsxxMaxZj例例：Cj2300CBXBbX1X2X3X40X36-20113X24-3101Cj-Zj-121100-3经过一次迭代后可得右表经过一次迭代后可得右表64 kkBjjkNBNBkTBkkjjTBjZZaBbBXXXXNXBbBXbNXBXaBCCXaBCCZZ011111100)(0, 00)(为为非非基基变变量量其其余

48、余令令若若存存在在说说明明：4. 在最优表中出现某在最优表中出现某非基变量检验数为非基变量检验数为0 0,36431228.4321212121xxxxxxtsxxMaxZ例：例：65CBXBbX1X2X3X4X50X340012/3-1/34X260101/203X14100-2/31/3Cj-Zj-360000-10X46003/21-1/24X2301-3/401/43X1810100Cj-Zj-360000-1Cj-Zj0340001 ,0;)1(*)2()1(* xxx)6 , 4(*)1( x)3 ,8(*)2( x结论：若线性规划问题存在某非基变量检验数为结论：若线性规划问题存在

49、某非基变量检验数为0,而其对应列向量而其对应列向量ak0,仍可判断线性规划问题有无穷多最优解。任一个仍可判断线性规划问题有无穷多最优解。任一个LP问题最优问题最优解都可表示成其基本最优解的凸组合加上其凸方向的线性组合解都可表示成其基本最优解的凸组合加上其凸方向的线性组合.66第五节第五节 应用举例应用举例例例1 某工厂要用三种原材料某工厂要用三种原材料C、P、H混合调配出三种不同规格混合调配出三种不同规格的产品的产品A、B、D。已知产品的规格要求、单价和原材料的供应量、。已知产品的规格要求、单价和原材料的供应量、单价。该厂应如何安排生产使利润最大？单价。该厂应如何安排生产使利润最大？产品名称产

50、品名称规格要求规格要求单价单价(元元/kg）A原材料原材料C不少于不少于50%原材料原材料P不超过不超过25%50B原材料原材料C不少于不少于25%原材料原材料P不超过不超过50%35D不限不限25原材料名原材料名称称每天最多每天最多供应量供应量(kg)单价单价(元元/kg)C10065P10025H6035333231232221131211xxxHPCDxxxHPCBxxxHPCA、的的含含量量为为、中中、的的含含量量为为、中中、的的含含量量为为、中中解解：设设67333231232221131211332313322212312111333231232221131211100400103

51、0152515)(35)(25)(65)(25)(35)(50 xxxxxxxxxxxxxxxxxxxxxxxxxxxMaxZ 12112131111213211222322122232213233321222311111213. .10025%10025%6050%50%0; ,1,2,3ijxstxxxxxxxxxxxxxxxxxxxxxxi jxxx用单纯型法计算得结果用单纯型法计算得结果:每天生产每天生产A产品产品200kg,分别需要原分别需要原料料:C为为100kg;P为为50kg;H为为50kg. 总利润收入总利润收入Z=500元元/天天.68成成全全年年计计划划。号号产产品品要要

52、求求二二月月底底前前完完第第两两种种产产品品下下半半年年投投产产，、，如如第第再再根根据据前前面面的的假假设设条条件件种种产产品品的的数数量量月月内内计计划划生生产产表表示示；台台时时类类设设备备的的生生产产能能力力月月内内第第表表示示类类设设备备的的台台时时数数类类产产品品需需要要的的第第表表示示加加工工单单位位类类产产品品全全年年的的计计划划量量表表示示第第种种产产品品表表示示工工厂厂生生产产的的第第类类设设备备表表示示工工厂厂的的第第设设：48512, 2 , 1)(), 2 , 1(), 2 , 1(jkxkikbijajdnjjjmiiijkikijj 先考虑一月份的线性规划模型先考

53、虑一月份的线性规划模型:例例2 （书（书P41 例例12）69种种产产品品全全年年的的产产量量为为第第一一月月份份：jdxnjdxmibxaxxtsbxaMaxZjjjjinjjijmiiminjjij;0);, 2 , 1();, 2 , 1(;0.11111815111111 以一月份内各种设备的生产能力总和为分以一月份内各种设备的生产能力总和为分母母,生产产品所需要的各类设备的总台时数生产产品所需要的各类设备的总台时数为分子为分子,可计算出一月份的平均设备利用系可计算出一月份的平均设备利用系数数Z,将将Z作为目标函数作为目标函数,可得下面的模型可得下面的模型:700),2 , 1(),2

54、 , 1(0.21221241442825212112 jjjjinjjijmiiminjjijxnjxdxmibxaxdxxxtsbxaMaxZ；二二月月份份： 考虑二月份线性规划模型时考虑二月份线性规划模型时:(1)从全从全年计划中减去一月份已生产的数量年计划中减去一月份已生产的数量;(2)对对批量小的产品批量小的产品,如一月份已经安排较大产如一月份已经安排较大产量的量的,二月份将剩余部分安排生产二月份将剩余部分安排生产;(3)保保证第证第4号产品在月底前交货号产品在月底前交货.这样这样,我们可以依次对我们可以依次对12个月列出线性规划模型个月列出线性规划模型并求解并求解,再根据具体情况再

55、根据具体情况对计算结果进行必要调对计算结果进行必要调整整.71例例3 某部门在今后某部门在今后5年内连续给以下项目投资：年内连续给以下项目投资： 项目项目A，第一年至第四年每年年初投资，次年，第一年至第四年每年年初投资，次年末回收本利末回收本利 115%； 项目项目B，第三年初投资，第五年末回收本利，第三年初投资，第五年末回收本利 125%，最大投资额不，最大投资额不超过超过4万元；万元； 项目项目C，第二年初投资，第五年末回收本利，第二年初投资，第五年末回收本利 140%，最大投资额，最大投资额不超过不超过3万元；万元； 项目项目D，五年内每年初可购买公债，当年末归还，并加利息，五年内每年初

56、可购买公债，当年末归还，并加利息6% 。 该部门现有资金该部门现有资金 10万元，问该如何确定投资方案，使第五年末万元，问该如何确定投资方案，使第五年末拥有的资金本利和最大？拥有的资金本利和最大？12345Ax1Ax2Ax3Ax4ABx3BCx2CDx1Dx2Dx3Dx4Dx5D72.)5 ,2 , 1(,的的投投资资额额、年年年年初初给给项项目目第第分分别别表表示示解解：设设DCBAiixxxxiDiCiBiA DBCAxxxxMaxZ532406. 125. 14 . 115. 1 )5 , 1(0,30000;4000006. 115. 106. 115. 106. 115. 106.

57、1100000.23435324421333122211 ixxxxxxxxxxxxxxxxxxxxxxxxtsiDiCiBiACBDADDADADADBADDCADA元元。额额为为到到第第五五年年末末拥拥有有资资金金总总第第五五年年：第第四四年年：第第三三年年：第第二二年年：第第一一年年：用用单单纯纯型型法法计计算算结结果果得得14375000,450000,40000, 00,30000,3913065217,3478354433322211 DDADBADCADAxxxxxxxxxxx73班次班次时间时间所需人数所需人数16:0010:0060210:0014:0070314:0018:

58、0060418:0022:0050522:002:002062:006:0030例例4 4 某公交线路每天各时段内所需司乘某公交线路每天各时段内所需司乘 人员数如下：人员数如下： 设所有的司乘人员分别在各时段的开始上班，并连续工设所有的司乘人员分别在各时段的开始上班，并连续工作作8小时，问该公交线路至少需配备多少司乘人员。列出该小时，问该公交线路至少需配备多少司乘人员。列出该问题的线性规划模型。问题的线性规划模型。74 )6 , 5 , 4 , 3 , 2 , 1(0603020506070.)5 , 4 , 3 , 2 , 1(166554433221654321ixxxxxxxxxxxxx

59、tsxxxxxxMinWixii则则有有人人数数为为时时间间上上班班的的解解：设设在在各各个个班班次次开开始始75第六节第六节 LPLP问题的基本理论问题的基本理论一、基本概念一、基本概念为为一一凸凸集集。则则称称有有，对对于于、维维空空间间一一点点集集为为凸凸集集：设设SSXXXSXXnS,)1(,10,. 1)2()1()2()1( 的的一一顶顶点点。为为则则称称成成立立使使，对对于于若若不不存存在在为为一一凸凸集集凸凸集集顶顶点点：设设）（）（SXXXXSXXSXS)0()2()1(0)2()1(0,)1(),10(,. 2 的的一一个个凸凸组组合合。为为则则称称使使得得若若存存在在个个

60、点点，维维空空间间中中的的为为凸凸组组合合：设设）（）（）（）（）（）（）（)(211221121)(21,)1, 10( ,. 3kkiiikkkkXXXXXXXXknXXX 76二、基本定理二、基本定理定理定理1 LP问题的可行域为一凸集。问题的可行域为一凸集。 )(, 0)1()1()1(,1000,0|)2()1()2()1(221121是是凸凸集集，而而凸凸集集的的并并集集不不一一定定凸凸集集的的交交集集一一定定是是凸凸集集为为一一凸凸集集。则则则则显显然然则则作作，对对于于，；，则则任任取取，记记证证明明：）（）（）（）（）（）（SSXXbbbXXAAXXXXXbAXXbAXSXX

61、XbAXXS 77引理：线性规划问题的可行解引理：线性规划问题的可行解X=(x1,x2,xn)T是基可行解的充是基可行解的充要条件是要条件是X的正分量所对应的系的正分量所对应的系数列向量是线性独立的。数列向量是线性独立的。为为基基可可行行解解。所所以以由由定定义义。解解恰恰为为构构成成极极大大无无关关组组，对对应应个个与与向向量量中中取取出出时时，一一定定可可以以从从其其余余列列为为相相应应基基可可行行解解时时，它它们们恰恰为为一一个个基基，线线性性独独立立，必必有有由由于于向向量量。所所对对应应的的系系数数列列向向量量为为其其中中不不妨妨设设先先证证充充分分性性：XXPPPkmmkxxxXm

62、kmkPPPPPPxxxkixxxxXkkkkkik,)()0 , 0 ,(,), 2 , 1(0),0 , 0 ,(212121212121 。由由基基可可行行解解的的定定义义可可知知再再证证必必要要性性：78定理定理2 线性规划问题的基可行解对应线性规划问题的基可行解对应于可行域的顶点。（即：若于可行域的顶点。（即：若X是是LP问题问题的可行解，则的可行解，则“X是是LP问题的基可行解问题的基可行解”等价于等价于“X是是LP问题可行域顶点问题可行域顶点”）不不是是基基可可行行解解。线线性性相相关关，则则所所以以又又得得，则则所所对对应应的的系系数数列列向向量量为为令令）（）（）（）（）（）

63、（）（）（）（）（）（）（XaaaXXxxaxxabaxaxaxbaxaxaxkixakkkkkkkkii,;0)()(:),2()1()2()1(),2,1(2121212111122221211212111 .,不不是是基基可可行行解解”则则不不是是可可行行域域顶顶点点逆逆反反命命题题为为“若若问问题题的的可可行行域域顶顶点点”。是是则则是是基基可可行行解解“若若步步先先证证证证明明：第第XXLPXXI0 , 0 ,;0 , 0 ,)1 , 0(,1,0 , 0 ,222212112111212121）（）（）（）（）（）（）（）（）（）（）（）（）（则则成成立立。）（使使问问题题的的可可

64、行行解解为为、则则存存在在不不同同的的两两个个点点）（不不是是顶顶点点，设设kkkxxxXxxxXXXXLPXXxxxXX 79)5(;00,40)0()3(2211211212211baxaxaxbxxxaaaaabAXLPxaaakkknkkkk ）即即（问问题题的的可可行行解解，则则是是由由于于）（得得：是是基基可可行行解解”是是可可行行域域顶顶点点，则则“若若步步：用用反反证证法法证证第第XXII)3(0,., 2 , 1, 0,)0 , 0 ,(221121 kkiiiikaaaaxkixxxxX使使数数即即存存在在一一组组不不全全为为零零的的线线性性相相关关。所所对对应应的的系系数

65、数列列向向量量则则但但不不是是基基可可行行解解。其其中中是是可可行行解解设设80）（）（令令0 , 0 ,0 , 0 ,2211)2(2211)1(kkkkxxxXxxxX 连连线线的的中中点点。、是是即即可可得得：、由由）（）（）（）（21)2()1(21,2121XXXXXXXX 不不是是可可行行域域的的顶顶点点。是是可可行行解解。这这证证明明、即即充充分分小小时时，可可保保证证另另外外，当当）（）（XXXmixii21),2, 1(0 baxaxaxbaxaxaxkkkkkk )()()(),4() 5()()()(),4() 5(222111222111得得：得得：81）（处处达达到到

66、最最优优数数在在也也是是可可行行解解，且且目目标标函函若若问问题题可可行行域域的的顶顶点点为为证证明明：设设0*)0()0()()2()1(,CXZXXLPXXXk 达达到到最最大大值值。，即即目目标标函函数数在在顶顶点点为为最最优优值值，所所以以只只能能又又。所所以以则则中中最最大大者者。，使使之之为为所所有有的的到到某某一一个个顶顶点点在在所所有有的的顶顶点点中中必必能能找找。因因此此其其中中表表示示成成：不不是是顶顶点点，所所以以它它可可以以因因）（）（）（)()()0()0()()0()(1)(1)()(1)(011)(0)0(1,0,mmmmkimikiiiimkiiikiiikiiiXCXCXCXCXCXCXCXaCXaCXXCXaCXaaXaXX 定理定理3 若可行域有界，则若可行域有界，则LP问题的问题的目标函数一定可以在其可行域的顶点目标函数一定可以在其可行域的顶点上达到最优。上达到最优。