《线性规划及单纯形法精选PPT.ppt》由会员分享，可在线阅读，更多相关《线性规划及单纯形法精选PPT.ppt（116页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、关于线性规划及单纯形法第1页，讲稿共116张，创作于星期三线性规划线性规划线性规划线性规划是运筹学的一个重要分支。是运筹学的一个重要分支。自自1947年年美美国国数数学学家家丹丹捷捷格格（G.B.Dantzig）提提出出了了求求解解线线性性规规划划问问题题的的方方法法单单纯纯形形法法之之后后，线线性性规规划划在在理理论论上上趋趋于于成成熟熟，在在实实际际中中的的应应用用日日益益广广泛泛与与深深入入。特特别别是是在在能能用用计计算算机机来来处处理理成成千千上上万万个个约约束束条条件件和和变变量量的的大大规规模模线线性性规规划划问问题之后，它的适用领域更广泛了。题之后，它的适用领域更广泛了。第一章
2、第一章 线性规划及单纯形法线性规划及单纯形法线线线线性性性性规规规规划划划划是是一一种种合合理理利利用用资资源源、合合理理调调配配资资源源的的应应用用数数学学方方法法。其其中中：规规规规划划划划就就是是利利用用某某种种数数学学方方法法使使得得有有效效资资源源的的运运用用最最优优化化；线线线线性性性性就是用来描述变量之间关系的函数是线性函数。就是用来描述变量之间关系的函数是线性函数。第2页，讲稿共116张，创作于星期三线性规划研究的主要内容：线性规划研究的主要内容：（1）计划任务的确定，如何统筹安排，精心筹划，用最少的资源来实现。）计划任务的确定，如何统筹安排，精心筹划，用最少的资源来实现。这方
3、面的问题涉及到系统的这方面的问题涉及到系统的投入投入投入投入和和求极小值问题求极小值问题求极小值问题求极小值问题（2）资源的确定，如何合理利用，合理规划，使得完成的任务最大。）资源的确定，如何合理利用，合理规划，使得完成的任务最大。这方面的问题涉及到系统的这方面的问题涉及到系统的产出产出产出产出和和求最大值问题求最大值问题求最大值问题求最大值问题 线性规划研究和应用的内容是实现系统的投入产出的问题，就是用最少的劳力线性规划研究和应用的内容是实现系统的投入产出的问题，就是用最少的劳力和物力消耗，获利更多更好的社会需求产品。和物力消耗，获利更多更好的社会需求产品。第3页，讲稿共116张，创作于星期
4、三1.1 线性规划问题及其数学模型线性规划问题及其数学模型 1.1.1 问题的提出问题的提出(一一)例例 某工厂在计划期内要安排生产某工厂在计划期内要安排生产、两种产品，已知两种产品，已知生产单位产品所需的设备台时和原料生产单位产品所需的设备台时和原料A、B的消耗量如下的消耗量如下表。表。该工厂每生产一件该工厂每生产一件产品产品可获利可获利2元，每生产一件产元，每生产一件产品品可获利可获利3元，问应如何安排生元，问应如何安排生产计划能使该厂获利最多？产计划能使该厂获利最多？这个问题可以用下面的数学模这个问题可以用下面的数学模型来描述，设计划期内产品型来描述，设计划期内产品、的产量分别为的产量分
5、别为x1，x2，可获利润用，可获利润用z表示，则有：表示，则有：Max Z=2x1+3x2x1+2x284x1 16 4x212x1,x20第4页，讲稿共116张，创作于星期三 1.1.1 问题的提出问题的提出(二二)例例 靠近某河流有两个化工厂，流经靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天第一化工厂的河流流量为每天500万万m3，两工厂之间有一条流量为每天，两工厂之间有一条流量为每天200万万m3的支流（见图）。的支流（见图）。第一化工厂每天排放污水第一化工厂每天排放污水2万万m3，第二化工厂每天排放污水第二化工厂每天排放污水 1.4万万m3。污。污水从工厂水从工厂1流到工厂流
6、到工厂2前会有前会有20%自然自然净化。根据环保要求，河水中污水的净化。根据环保要求，河水中污水的含量应不大于含量应不大于0.2%。而工厂。而工厂1和工厂和工厂2处理污水的成本分别为处理污水的成本分别为1000元元/m3和和800元元/m3。问两工厂各应处理多少污。问两工厂各应处理多少污水才能使处理污水的总费用最低？水才能使处理污水的总费用最低？设工厂设工厂1和工厂和工厂2每每天分别处理污水天分别处理污水x1和和x2万万m3，则有，则有：Min z=1000 x1+800 x2(2-x1)/5000.0020.8(2-x1)+1.4-x2/700 0.002x12,x21.4 x1,x20第5
7、页，讲稿共116张，创作于星期三1.1.1 问题的提出问题的提出(三三)例例 某养鸡场所用的混合饲料是由某养鸡场所用的混合饲料是由 n 种配料组成。要求这种混合饲料必须含种配料组成。要求这种混合饲料必须含有有 m 种不同的营养成份，而且要求每单位混合饲料中第种不同的营养成份，而且要求每单位混合饲料中第 i 种营养成份的含量种营养成份的含量不能低于不能低于 bi(i=1,2,m）。已知第）。已知第 i 种营养成份在每单位的第种营养成份在每单位的第 j 种配料种配料中的含量为中的含量为 aij,j=1,2,n，每单位的第，每单位的第 j 种配料的价格为种配料的价格为 cj。现在要求在。现在要求在保
8、证营养条件的前提下，应采用何种配方，使混合饲料的成本最小保证营养条件的前提下，应采用何种配方，使混合饲料的成本最小.配料营养成份B1 B2 Bn含量A1A2Am a11 a12 a1n a21 a22 a2n am1 am2 amnb1b2 bm单价 c1 c2 cn第6页，讲稿共116张，创作于星期三建立模型：建立模型：MinZ=MinZ=c c1x1+c c2x2+c cnxn 设设xj 表示在单位混合饲料中，第表示在单位混合饲料中，第j 种配料的含量（种配料的含量（j=1,2,n）则有）则有如下的数学模型：如下的数学模型：配料营养成份B1 B2 Bn含量A1A2Am a11 a12 a1
9、n a21 a22 a2n am1 am2 amnb1b2bm价格 c1 c2 cna a11x1+a a12x2+a a1nxn b1 a a21x1+a a22x2+a a2nxn b2a am1x1+a am2x2+a amnxn bmx1 0,x2 0,xn0 第7页，讲稿共116张，创作于星期三 1.1.2 线性规划问题的数学模型线性规划问题的数学模型 线性规划问题的共同特征线性规划问题的共同特征（1 1）每个问题都用一组每个问题都用一组决策变量决策变量决策变量决策变量(x(x1 1,x,x2 2,x,xn n，Decision Decision variablevariable)表
10、示某一表示某一方案方案 ,这组未知数的值就代表一个具体的方案这组未知数的值就代表一个具体的方案,通常要通常要求这些未知数取值是非负的。求这些未知数取值是非负的。（2）存在一定的限制条件）存在一定的限制条件(称为称为约束条件，约束条件，约束条件，约束条件，ConstraintConstraint),),这些条件都可这些条件都可以用关于决策变量的一组线性等式或不等式来表示。以用关于决策变量的一组线性等式或不等式来表示。（3）都有一个目标要求）都有一个目标要求,并且这个目标可表示为这组决策变量的线并且这个目标可表示为这组决策变量的线性函数性函数(称为称为目标函数，目标函数，目标函数，目标函数，Obj
11、ective functionObjective function),),按研究问题的不同按研究问题的不同,要要求求目标函数实现最大化或最小化。目标函数实现最大化或最小化。满足以上三个条件的数学模型称为线性规划数学模型。其满足以上三个条件的数学模型称为线性规划数学模型。其满足以上三个条件的数学模型称为线性规划数学模型。其满足以上三个条件的数学模型称为线性规划数学模型。其一般形式为一般形式为一般形式为一般形式为第8页，讲稿共116张，创作于星期三线性规划一般模型的代数式为：线性规划一般模型的代数式为：max(min)Z=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn (或或,)
12、b1 a21x1+a22x2+a2nxn (或或,)b2 am1x1+am2x2+amnxn(或或,)bm x1,x2,xn ()0第9页，讲稿共116张，创作于星期三1.1.3 线性规划问题的标准形式线性规划问题的标准形式 线性规划问题的数学模型有各种不同的形式，如 目标函数有极大化极大化极大化极大化和极小化极小化极小化极小化；约束条件有“”、“”和“”三种情况；决策变量一般有非负性非负性非负性非负性要求，有的则没有。为了求解方便，特规定一种线性规划的标准形式，非标准型可以转化为标准型计算 第10页，讲稿共116张，创作于星期三标准形式为：标准形式为：标准形式为：标准形式为：（一）标准形式（
13、一）标准形式 目标函数目标函数最大化最大化最大化最大化 约束条件为约束条件为等式等式等式等式 右端常数项右端常数项b bi i0 0 决策变量决策变量非负非负非负非负 maxZ=c1x1+c2x2+cnxna11x1+a12x2+a1nxn b1a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxnbmx1,x2,xn 0第11页，讲稿共116张，创作于星期三标准型的表达方式有代数式、矩阵式：标准型的表达方式有代数式、矩阵式：（二）标准型的表达方式（二）标准型的表达方式 1.1.1.1.代数式代数式代数式代数式 maxZ=c1x1+c2x2+cnxn a11x1+a12x
14、2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxnbm x1,x2,xn 0简记maxZ=cjxj aijxjbi (i=1,2,m)xj0 (j=1,2,n)第12页，讲稿共116张，创作于星期三 2.2.2.2.矩阵式矩阵式矩阵式矩阵式 化为maxZ=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxnbm x1,x2,xn 0第13页，讲稿共116张，创作于星期三（三）（三）非非标标准型向准型向标标准型准型转转化化 目标函数极小化问题目标函数极小
15、化问题目标函数极小化问题目标函数极小化问题只只需需将将等等式式两两端端乘乘以以-1即即变变变变为为为为极极极极大大大大化化化化问问题题。因因为为minZ=max(Z)=CTX，令令Z=-Z，则，则maxZ=maxZ=C CT TX XminZ=CminZ=CT TX X约束条件中约束条件中约束条件中约束条件中右端常数项非正右端常数项非正右端常数项非正右端常数项非正 两端同乘以两端同乘以-1 约束条件为不等式约束条件为不等式约束条件为不等式约束条件为不等式 当当约约束束方方程程为为“”时时，左左端端加加入入一一个个非非负负的的松松松松弛弛弛弛变变变变量量量量，就就把把不不等等式式变变成了等式；如
16、成了等式；如4X4X1 12X2X2 2 6060 4X4X1 12X2X2 2 X X3 3 =6060 当当约约束束条条件件为为“”“”时时，不不等等式式左左端端减减去去一一个个非非负负的的剩剩剩剩余余余余变变变变量量量量(也也可可称松弛变量称松弛变量)，就把不等式变成了等式就把不等式变成了等式。决策变量决策变量决策变量决策变量x xk k为无约束变量为无约束变量为无约束变量为无约束变量 令令xk=xk-xk，其中令其中令xk，xk 0，用，用xk、xk 取代模型中取代模型中xk第14页，讲稿共116张，创作于星期三例例1：试将如下线性规划问题化成标准型：试将如下线性规划问题化成标准型例例
17、例例1 1 的标准型的标准型的标准型的标准型 maxZ=3x1+5 x2 x1 8 2x2 12 3x1+4 x2 36 x1 0,x2 0S.t.maxZ=3x1+5 x2+0 x3 x1 +x3 =8 2x2 12 3x1+4 x2 36 x1,x2,x3 0 maxZ=3x1+5 x2+0 x3+0 x4 x1 +x3 =8 2x2 +x4 =12 3x1+4 x2 36 x1,x2,x3,x4 0 maxZ=3x1+5 x2+0 x3+0 x4+0 x5 x1 +x3 =8 2x2 +x4 =12 3x1+4 x2 +x5=36 x1,x2,x3,x4,x5 0 maxZ=3x1+5
18、x2+0 x3+0 x4+0 x5 x1 +x3 =8 2x2 +x4 =12 3x1+4 x2 +x5=36 x1,x2,x3,x4,x5 0需要化为标准型需要化为标准型需要化为标准型需要化为标准型引进一引进一 x3引进一引进一 x4引进一引进一 x5第15页，讲稿共116张，创作于星期三例例2：试将如下线性规划问题化成标准型：试将如下线性规划问题化成标准型minZ=x1+2 x2-3 x3 x1+2 x2-x3 5 2x1+3 x2-x3 6 -x1 -x2 -x3 -2 x1 0,x3 0S.t.例例例例2 2的标准化的标准化的标准化的标准化 minZ=x1+2 x2+3 x3 x1+2
19、 x2+x3 5 2x1+3 x2+x3 6 -x1 -x2 +x3 -2 x1 0,x3 0 minZ=x1+2(x2-x 2)+3 x3 x1+2(x2-x 2)+x3 5 2x1+3(x2-x 2)+x3 6 -x1 -(x2-x 2)+x3 -2 x1,x2,x 2,x3 0 minZ=x1+2(x2-x 2)+3 x3 x1+2(x2-x 2)+x3 5 2x1+3(x2-x 2)+x3 6 x1+(x2-x 2)-x3 2 x1,x2,x 2,x3 0 maxZ=-x1-2(x2-x 2)-3 x3+0 x4 x1+2(x2-x 2)+x3+x4=5 2x1+3(x2-x 2)+x
20、3 6 x1+(x2-x 2)-x3 2 x1,x2,x 2,x3,x4 0 maxZ=-x1-2(x2-x 2)-3 x3+0 x4+0 x5 x1+2(x2-x 2)+x3+x4 =5 2x1+3(x2-x 2)+x3 -x5=6 x1+(x2-x 2)-x3 2 x1,x2,x 2,x3,x4,x50 maxZ=-x1-2(x2-x 2)-3 x3+0 x4+0 x5+0 x6 x1+2(x2-x 2)+x3+x4 =5 2x1+3(x2-x 2)+x3 -x5 =6 x1+(x2-x 2)-x3 +x6=2 x1,x2,x 2,x3,x4,x5,x6 0 maxZ=-x1-2(x2-x
21、 2)-3 x3 x1+2(x2-x 2)+x3 5 2x1+3(x2-x 2)+x3 6 x1+(x2-x 2)-x3 2 x1,x2,x 2,x3 0 maxZ=-x1-2(x2-x 2)-3 x3+0 x4+0 x5+0 x6 x1+2(x2-x 2)+x3+x4 =5 2x1+3(x2-x 2)+x3 -x5 =6 x1+(x2-x 2)-x3 +x6=2 x1,x2,x 2,x3,x4,x5,x6 0 需要化为标准型需要化为标准型需要化为标准型需要化为标准型令令 x3 x3令令 x2 x2x2令令-Z Z引进一引进一 x4引进一引进一 x5引进一引进一 x6第16页，讲稿共116张，
22、创作于星期三例例3:试将如下线性规划问题化成标准型试将如下线性规划问题化成标准型例例例例3 3 的标准型为：的标准型为：的标准型为：的标准型为：需要化为标准型需要化为标准型需要化为标准型需要化为标准型第17页，讲稿共116张，创作于星期三练习：试将如下线性规划问题化成标准型练习：试将如下线性规划问题化成标准型（1）maxZ=-x1+3 x3+4 x4 2 x1+4 x2+x3-2 x4 13 6 x1 +x3+8 x4 50 -x1+4 x2-5 x3-3 x4=-10 xi 0,i=1,2,3,4S.t.（2）minZ=6 x1+7 x2-x3 3 x1+2 x2-x3 10 x2+x3 1
23、5 x1 3 x2 2 x1,x2 0，x3 无限制无限制S.t.第18页，讲稿共116张，创作于星期三答案：答案：（1）maxZ=-x1+3 x3+4 x4+0 x5+0 x6 2 x1+4 x2+x3-2 x4+x5 =13 6 x1 +x3+8 x4 -x6=50 x1-4 x2+5 x3+3 x4=10 xi 0,i=1,2,3,4,5,6S.t.（2）maxZ=-6 x1-7 x2+x3x4+0 x5+0 x6+0 x7+0 x8 3 x1+2 x2-x3+x4+x5 =10 x2+x3x4+x6 =15 x1 -x7 =3 x2 -x8=2 x1,x2,x3,x4,x5,x6,x7
24、,x80S.t.第19页，讲稿共116张，创作于星期三1.1.4 线性规划解的概念线性规划解的概念在讨论线性规划问题的求解之前在讨论线性规划问题的求解之前,先要了解线性规划问题的解的概念。由先要了解线性规划问题的解的概念。由前面讨论可知线性规划问题的标准型为：前面讨论可知线性规划问题的标准型为：求求解解线线性性规规划划问问题题就就是是从从满满足足约约束束条条件件(2)、(3)的的方方程程组组中中找找出出一一个个解解，使使目目标标函数（函数（1）达到最大值。）达到最大值。若若设设矩矩阵阵A的的秩秩R(A)=m；根根据据线线性性代代数数定定理理可可知知，当当R(A)=mn，则则方方程程组组有有无无
25、穷多个解，这也正是线性规划寻求最优解的穷多个解，这也正是线性规划寻求最优解的余地所在余地所在余地所在余地所在。第20页，讲稿共116张，创作于星期三关于标准型解的若干基本概念关于标准型解的若干基本概念可行解（可行解（可行解（可行解（feasible solutionfeasible solutionfeasible solutionfeasible solution）与非可行解（非可行解（非可行解（非可行解（infeasible solutioninfeasible solutioninfeasible solutioninfeasible solution）y满足约束条件（满足约束条件（2
26、2）和非负条件（）和非负条件（3 3）的解）的解 X 称为称为可行解可行解可行解可行解，满足约束条件（，满足约束条件（2 2）但不满足非负条件（但不满足非负条件（3 3）的解）的解 X 称为称为非可行解非可行解非可行解非可行解y y可行域（可行域（可行域（可行域（feasible regionfeasible regionfeasible regionfeasible region）:可行解可行解可行解可行解组成的集合叫做组成的集合叫做最优解（最优解（最优解（最优解（optimal solutionoptimal solutionoptimal solutionoptimal solution
27、）：使目标函数使目标函数(1)(1)达到最大的解称为最优解达到最大的解称为最优解第21页，讲稿共116张，创作于星期三 基基基基y在标准型中，约束方程组的系数矩阵有在标准型中，约束方程组的系数矩阵有 n n 列，即列，即 A=(P1,P2 ,Pn )y设设A A的秩为的秩为m m ，当当R(A)=mn ，A A中必有线性独立的中必有线性独立的m m列，构成该标准型的列，构成该标准型的一个一个基基基基，即即 B=(P1,P2,Pm)，|B|0 yP1 ,P2 ,Pm 称为称为基向量基向量基向量基向量y与与基向量基向量基向量基向量对应的变量称为对应的变量称为基变量基变量基变量基变量，记为，记为XB
28、=(x1,x2 ,xm)T其余的变量称为其余的变量称为非基变量非基变量非基变量非基变量，记为，记为XN=(xm+1,xm+2,xn)T，y故有故有 X=XB+XN，最多有最多有 个基个基第22页，讲稿共116张，创作于星期三基本解基本解基本解基本解令令非基变量非基变量 XN=0，求得求得基变量基变量XB的值称为的值称为基解，基解，即即XB=B 1 b基解是有限的基本可行解基本可行解基本可行解基本可行解y基本解基本解XB 的非零分量都的非零分量都 0 时，称为时，称为基本可行解基本可行解，否则为，否则为基非基非可行解可行解y基本可行解基本可行解的非零分量个数的非零分量个数 m m 时，称为退化时
29、，称为退化解解可行基可行基可行基可行基y对应于基本可行解对应于基本可行解的基的基，称为，称为可行基可行基第23页，讲稿共116张，创作于星期三线性规划标准型问题解的关系线性规划标准型问题解的关系约束方程的约束方程的解空间解空间基本解基本解可行解可行解非可行解非可行解基本基本可行解可行解退化解退化解第24页，讲稿共116张，创作于星期三例例1 的标准型为的标准型为 maxZ=3x1+5 x2+0 x3+0 x4+0 x5 x1 +x3 =8 2x2 +x4 =12 3x1+4 x2 +x5=36 x1,x2,x3,x4,x5 0 约束方程的增广矩阵约束方程的增广矩阵约束方程的增广矩阵约束方程的增
30、广矩阵x1x2x3x4x53 3阶非奇异子矩阵为基矩阵阶非奇异子矩阵为基矩阵还原为maxZ=3x1+5 x2+0 x3+0 x4+0 x5x3 =-x1 +8 x4 =-2x2+12 x5=-3x1-4 x2+36 基变量是x3,x4,x5，令非基变量x1=x2=0，得到x3=8，x4=12，x5=36基解。此解为基可行解：此解为基可行解：此解为基可行解：此解为基可行解：X X0 0=(0,0,8,12,36)=(0,0,8,12,36)T TR(A)=3R(A)=3非基变量是x1,x2，第25页，讲稿共116张，创作于星期三1.21.2线性规划问题的求解线性规划问题的求解 1.2.1 1.2
31、.1 1.2.1 1.2.1 图图图图解法解法解法解法对于简单的线性规划问题对于简单的线性规划问题(只有两个决策变量的线性规划问题只有两个决策变量的线性规划问题)，可可以通过图解法对它进行求解。以通过图解法对它进行求解。图解法图解法图解法图解法即是用图示的方法来求解线性规划问题。即是用图示的方法来求解线性规划问题。图解法简单直观，图解法简单直观，有助于了解线性规划问题求解的基本原理有助于了解线性规划问题求解的基本原理。一个二维的线性规划问题，可以在平面图上求解，三维的线性一个二维的线性规划问题，可以在平面图上求解，三维的线性规划则要在立体图上求解，这就比较麻烦，而维数再高以后就不能规划则要在立
32、体图上求解，这就比较麻烦，而维数再高以后就不能用图示了。用图示了。第26页，讲稿共116张，创作于星期三（一）（一）图解法的基本步骤图解法的基本步骤满足所有约束条件的解叫可行解，解的集合称之为满足所有约束条件的解叫可行解，解的集合称之为可行域可行域可行域可行域。即所有约束条。即所有约束条件共同围成的区域。件共同围成的区域。1.1.可行域可行域可行域可行域 的确定的确定的确定的确定例例例例1 1求解线性规划求解线性规划求解线性规划求解线性规划x1=82x2=123x1+4 x2=36x1x248123690 0A AB BC(4,6)C(4,6)D D五边形五边形OABCD内内(含边界含边界)的
33、任意一点的任意一点(x1，x2)都是满足所有约束条件的一都是满足所有约束条件的一个解，称之个解，称之可行解可行解可行解可行解。maxZ=3x1+5 x2 x1 8 2x2 12 3x1+4 x2 36 x1 0,x2 0第27页，讲稿共116张，创作于星期三2.最优解的确定最优解的确定确定确定x1、x2希望希望目标函数目标函数 Z=3x1+5 x2达到最大，图形中达到最大，图形中Z=3x1+5 x2 代表以代表以Z为参数的一族平行线，即等值线。为参数的一族平行线，即等值线。等值线：位于同一直线上的点的目标函数值相同。等值线：位于同一直线上的点的目标函数值相同。Z=3x1+5x20 x1=82x
34、2=123x1+4 x2=36x1x248123690 0A AB(8,3)B(8,3)C(4,6)C(4,6)D D最优解：可行解中使目标函数最优最优解：可行解中使目标函数最优(极大或极小极大或极小)的解的解本题中：满足目标函数最大的极点是离原点距离最远的点（本题中：满足目标函数最大的极点是离原点距离最远的点（4,6）Z=3x1+5x224Z=3x1+5x230Z=39Z=42即即x1=4，x2=6时时Z的值最大为的值最大为42。C(4,6)C(4,6)C(4,6)C(4,6)为最优解为最优解为最优解为最优解第28页，讲稿共116张，创作于星期三（二）解的几种可能性（二）解的几种可能性唯一最
35、优解：唯一最优解：唯一最优解：唯一最优解：只有一个最优点。如上题的最优解（只有一个最优点。如上题的最优解（4,64,6）多重最优解：多重最优解：多重最优解：多重最优解：无穷多个最优解。若在两个顶点同时得到最优解，则它们连无穷多个最优解。若在两个顶点同时得到最优解，则它们连线上的每一点都是最优解。线上的每一点都是最优解。x1=82x2=123x1+4 x2=36x1x248123690 0A AB BC(4,6)C(4,6)D D如例如例1的数学模型变为的数学模型变为 maxZ=3x1+4 x2 x1 8 2x2 12 3x1+4 x2 36 x1 0,x2 0S.t.Z=24Z=36Z=12第
36、29页，讲稿共116张，创作于星期三线线性性规规划划问问题题的的可可行行域域无无界界，使使目目标标函函数数无无限限增增大大而而无无界界。（缺缺乏乏必必要要的的约束条件）约束条件）例如例如 maxZ=3x1+2 x2 -2x1+x2 2 x1-3 x2 3 x1 0,x2 0-2x1+x2=2x1-3 x2=3x2123-1x1123-1Z=6Z=12S.t.例如例如 maxZ=3x1+2 x2 -2x1+x2 2 x1-3 x2 3 x1 0,x2 0-2x1+x2=2x1-3 x2=3x2123-1x1123-1S.t.无界解：无界解：无界解：无界解：无可行解：无可行解：无可行解：无可行解：
37、若约束条件相互矛盾，则可行域为空集。若约束条件相互矛盾，则可行域为空集。第30页，讲稿共116张，创作于星期三例：求最大值问题例：求最大值问题数学模型为数学模型为数学模型为数学模型为：四边形四边形OBQC内内(含边界含边界)的任意一点的任意一点(x1，x2)都是满足所有约束条件的都是满足所有约束条件的一个解，称之可行解一个解，称之可行解。maxZ=8x1+6x24x1+2 x2 60 2x1+4 x2 48 2x1+3 x2 36 x1 0,x2 02x1+3 x2=36x1x2510510150 0C(0,12C(0,12)4x1+2 x2=602x1+4x2=48B(15,0B(15,0)
38、Z=0Z=72Z=120Z=126Q(13.5,3)Q(13.5,3)结论：在结论：在结论：在结论：在Q(13.5,3)Q(13.5,3)Q(13.5,3)Q(13.5,3)处利润最大为处利润最大为处利润最大为处利润最大为126126126126，Q(13.5,3)Q(13.5,3)Q(13.5,3)Q(13.5,3)为最优解为最优解为最优解为最优解第31页，讲稿共116张，创作于星期三例：求最小值问题例：求最小值问题设有某林场需配制某种灭虫药水设有某林场需配制某种灭虫药水500500公斤，该药水系由甲与乙两种公斤，该药水系由甲与乙两种药水混合而成。甲种药水每公斤药水混合而成。甲种药水每公斤5
39、 5元，乙种药水每公斤元，乙种药水每公斤8 8元。按照两种元。按照两种药水的化学性质，在混合时，药水的化学性质，在混合时，500500公斤混合药水中含甲种药水最多不能公斤混合药水中含甲种药水最多不能超过超过400400公斤，含乙种药水最少不能少于公斤，含乙种药水最少不能少于200200公斤。问如何配制可使该药公斤。问如何配制可使该药水配制成本最低？水配制成本最低？.minZ=5x1+8x2 x1 400 x2 200 x1+x2=500 x1 0,x2 0则数学模型为则数学模型为则数学模型为则数学模型为：设：设：500500公斤混合药水中，甲种药水公斤混合药水中，甲种药水x1公斤公斤，乙种药水
40、乙种药水x2公斤公斤第32页，讲稿共116张，创作于星期三例：求最小值问题例：求最小值问题数学模型为数学模型为数学模型为数学模型为：线段线段BC上的任意一点上的任意一点(x1，x2)都是满足所有约束条件的一个解，称之都是满足所有约束条件的一个解，称之可行解可行解。minZ=5x1+8x2 x1 400 x2 200 x1+x2=500 x1 0,x2 0结论：等成本线往右下移，成本越来越小，结论：等成本线往右下移，成本越来越小，结论：等成本线往右下移，成本越来越小，结论：等成本线往右下移，成本越来越小，A(300,200)A(300,200)A(300,200)A(300,200)成本为最小成
41、本为最小成本为最小成本为最小Z=5x1+8x2=4000Z=3100 x2=200 x1+x2=500 x1x2502004000 0B(0,500)B(0,500)100300500 x1=400100200300 400C CA A最优解为最优解为（300,200300,200）第33页，讲稿共116张，创作于星期三练习题：用图解法求解下列问题练习题：用图解法求解下列问题x2y2 x2y 6x y 3x3y 3x0,y 01.1.1.1.约束条件为约束条件为约束条件为约束条件为：（1）max Z=4x+y画出可行域图形，求下面几种情况下的最优解画出可行域图形，求下面几种情况下的最优解（2）
42、minZ=2x-3y（3）max Z=x+2y（4）maxZ=2x-3y第34页，讲稿共116张，创作于星期三练习题：求解练习题：求解x2y2 x2y 6x y 3x3y 3x0,y 0（1）max Z=4x+y求下面几种情况下的最优解求下面几种情况下的最优解（2）minZ=2x-3y（4）max Z=x+2y（3）maxZ=2x-3yx+3y=3x+2y=2xy=3x1x2161234523x+2y=6(2,2)(4,1)(3,0)(0,1)Z=4x+y=1Z=10Z=12 Z=17Z=-3Z=-2Z=5Z=6最优解最优解 x=4,y=1 max Z=17最优解最优解 x=0,y=1 min
43、 Z=-3Z=2x+y=1Z=3Z=6有无穷多最优解有无穷多最优解 max Z=6最优解最优解 x=3,y=0 max Z=6第35页，讲稿共116张，创作于星期三1.2.21.2.2单纯形法（单纯形法（Simple MethodSimple Method）（一）线性规划解的基本概念和基本定理（一）线性规划解的基本概念和基本定理（一）线性规划解的基本概念和基本定理（一）线性规划解的基本概念和基本定理基本概念基本概念1、凸集、凸集:假设假设 K 是是 n 维欧氏空间的一个点集维欧氏空间的一个点集,若对于若对于K 中的任意两点中的任意两点 X1、X2,其连线上的所有点其连线上的所有点 X1+(1-
44、)X2(0 1)都在集合都在集合 K 中中,即即:X1+(1-)X2 K (0 1),则称则称 K 为凸集。为凸集。2.顶点顶点:假设假设 K 是凸集是凸集,X K;若不能用不同的两个点若不能用不同的两个点X1、X2 K 的线性组合表示为的线性组合表示为:X=X1+(1-)X2，(0 0=b0=bl l/a/alklk,对应的第对应的第l行的基变量为换出行的基变量为换出变量变量.第三第三,旋转运算旋转运算.换入变量所在的行与换出变量所在换入变量所在的行与换出变量所在的列交叉点的元素称为中心元素的列交叉点的元素称为中心元素,用高斯消去法把中心元用高斯消去法把中心元素化成素化成1,同列的其他元素化
45、成同列的其他元素化成0,得到一个新的单纯形表得到一个新的单纯形表,也也就得到一个新的基本可行解就得到一个新的基本可行解.第42页，讲稿共116张，创作于星期三（六）（六）表格单纯形法的计算步骤表格单纯形法的计算步骤 maxZ=3x1+5 x2 x1 8 2x2 12 3x1+4 x2 36Cj比值CBXBb检验数jx1x2x3x4x53500081010012020103634001x3x4x5000035000 maxZ=3x1+5 x2+0 x3+0 x4+0 x5 x1 +x3 =8 2x2 +x4 =12 3x1+4 x2 +x5=36 标准型基变量基变量基变量基变量x x3 3,x,
46、x4 4,x,x5 5，1 1、建立初始单纯形表、建立初始单纯形表、建立初始单纯形表、建立初始单纯形表非基变量非基变量非基变量非基变量x x1 1,x,x2 2第43页，讲稿共116张，创作于星期三2、求初始基本可行解并进行最优性检验、求初始基本可行解并进行最优性检验Cj比值CBXBb检验数jx1x2x3x4x53500081010012020103634001x3x4x5000035000令非基变量x1=0，x2=0，找到一个初始基可行解：x x1 1=0 0，x x2 2=0=0，x x3 3=8=8，x x4 4=12=12，x x5 5=36=36，j j0 0，此解不是最优（因为，此
47、解不是最优（因为，此解不是最优（因为，此解不是最优（因为 z=3xz=3x1 1+5x+5x2 2+0+0 x x3 3+0+0 x x4 4+0+0 x x5 5)可求基可行解的状态可求基可行解的状态即即即即X X0 0=(0,0,8,12,36)=(0,0,8,12,36)T T，此时利润，此时利润，此时利润，此时利润Z=0 Z=0 第44页，讲稿共116张，创作于星期三初始基本可行解图示初始基本可行解图示Z=3x1+5x20 x1=82x2=123x1+4 x2=36x1x248123690 0A AB(8,3)B(8,3)C(4,6)C(4,6)D DX0=(0,0,8,12,36)T
48、说明：说明：说明：说明：一个可行解就是一个生产方案，上述方案表明两种产品一个可行解就是一个生产方案，上述方案表明两种产品都不生产都不生产x1=0，x2=0，利润，利润Z=0。第45页，讲稿共116张，创作于星期三3、寻找另一基本可行解、寻找另一基本可行解Cj比值CBXBb检验数jx1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=9 中心元素首先确定换入变量首先确定换入变量首先确定换入变量首先确定换入变量再确定换出变量再确定换出变量再确定换出变量再确定换出变量第46页，讲稿共116张，创作于星期三检验数j810100601
49、01/2012300-21x3x2x5050-30300-5/20Cj比值CBXBb检验数jx1x2x3x4x5350008101001202 20103634001x3x4x5000035000-12/2=636/4=9令令令令 x x1 1=0 0，x x4 4=0=0，得，得，得，得 x x2 2=6=6，x x3 3=8=8，x x5 5=12=12，即得基可行解即得基可行解即得基可行解即得基可行解X X1 1=(0,6,8,0,12)=(0,6,8,0,12)T T 此时此时此时此时Z Z3030 1 1=3=30 0，此解不是最优，此解不是最优，此解不是最优，此解不是最优迭代迭代可
50、求基可行解的状态可求基可行解的状态第47页，讲稿共116张，创作于星期三第一次基迭代可行解图示第一次基迭代可行解图示Z=3x1+5x230 x1=82x2=123x1+4 x2=36x1x248123690 0A AB(8,3)B(8,3)C(4,6)C(4,6)D DX1=(0,6,8,0,12)T第48页，讲稿共116张，创作于星期三4、寻找下一基本可行解、寻找下一基本可行解Cj比值CBXBb检验数jx1x2x3x4x53500081010060101/20123 300-21x3x2x5050-30300-5/208-4检验数j40012/3-1/360101/204100-2/31/3