《(精品)第1章线性规划与单纯形法.ppt》由会员分享，可在线阅读，更多相关《(精品)第1章线性规划与单纯形法.ppt（244页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、（本科版（本科版）运筹学运筹学运筹学教材编写组 编清华大学出版社第第1 1章章 线性规划与单纯形法线性规划与单纯形法第2章 对偶理论与灵敏度分析第3章 运输问题第4章 目标规划二.线性规划与目标规划第第1章章 线性规划与单纯形法线性规划与单纯形法第1节 线性规划问题及其数学模型第2节 线性规划问题的几何意义第3节 单纯形法第4节 单纯形法的计算步骤第5节 单纯形法的进一步讨论第6节 应用举例第1节 线性规划问题及其数学模型1.1 问题的提出1.2 图解法1.3 线性规划问题的标准形式1.4 线性规划问题的解的概念第1节 线性规划问题及其数学模型 线性规划是运筹学的一个重要分支。线性规划在理论上
2、比较成熟，在实用中的应用日益广泛与深入。特别是在电子计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了。从解决技术问题的最优化设计到工业、农业、商业、交通运输业、军事、经济计划和管理决策等领域都可以发挥作用。它已是现代科学管理的重要手段之一。解线性规划问题的方法有多种，以下仅介绍单纯形法。1.1 问题的提出 从一个简化的生产计划安排问题开始例 1 某工厂在计划期内要安排生产、两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如表1-1所示。资源 产 品拥有量设 备1 2 8台时原材料 A 40 16 kg原材料 B04 12 kg续例1 该
3、工厂每生产一件产品可获利2元，每生产一件产品可获利3元，问应如何安排计划使该工厂获利最多?如何用数学关系式描述这问题，必须考虑数学模型例2.简化的环境保护问题 靠近某河流有两个化工厂(见图1-1)，流经第一化工厂的河流流量为每天500万立方米，在两个工厂之间有一条流量为每天200万立方米的支流。图1-1续例2第一 化工厂每天排放含有某种有害物质的工业污水2万立方米，第二化工厂每天排放这种工业污水1.4万立方米。从第一化工厂排出的工业污水流到第二化工厂以前，有20%可自然净化。根据环保要求，河流中工业污水的含量应不大于0.2%。这两个工厂都需各自处理一部分工业污水。第一化工厂处理工业污水的成本是
4、1000元/万立方米。第二 化工厂处理工业污水的成本是800元/万立方米。现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂总的处理工业污水费用最小。建模型之前的分析和计算设设：第一化工厂每天处理工业污水量为x1万立方米，第二化工厂每天处理工业污水量为x2万立方米 数学模型补充例补充例1.1.生产计划问题生产计划问题 某厂生产甲乙两种产品，各自的零部件分别在A、B车间生产，最后都需在C车间装配，相关数据如表所示：问如何安排甲、乙两产品的产量，使利润为最大。产品产品车间车间工时单耗工时单耗甲甲 乙乙生产能力生产能力ABC 1 0 0 2 3 48 1236单位产品获利单位产品
5、获利 3 5(1)(1)决决策策变变量量。要决策的问题是甲、乙两种产品的产量，因此有两个决策变量：设x1为甲产品产量，x2为乙产品产量。(2)(2)约约束束条条件件。生产这两种产品受到现有生产能力的制约，用量不能突破。生产单位甲产品的零部件需耗用A车间的生产能力1工时，生产单位乙产品不需耗用A车间的生产能力，A车间的能力总量为8工时，则A车间能力约束条件表述为 x1 8同理，B和C车间能力约束条件为 2x2 12 3x1+4 x2 36建立模型建立模型(3)(3)目标函数目标函数。目标是利润最大化，用Z表示利润，则 maxZ=3x1+5 x2(4)(4)非非负负约约束束。甲乙产品的产量不应是负
6、数，否则没有实际意义，这个要求表述为 x1 0，x2 0综上所述，该问题的数学模型表示为综上所述，该问题的数学模型表示为 maxZ=3x1+5 x2 x1 8 2x2 12 3x1+4 x2 36 x1 0,x2 0S.t.共同的特征(1)每一个线性规划问题都用一组决策变量 表示某一方案，这组决策变量的值就代表一个具体方案。一般这些变量取值是非负且连续的；(2)要有各种资源和使用有关资源的技术数据，创造新价值的数据；共同的特征（继续）(3)存在可以量化的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示;(4)要有一个达到目标的要求，它可用决策变量的线性函数(称为目标函数)来表示。按问
7、题的不同，要求目标函数实现最大化或最小化。它们的对应关系可用表格表示：用一组非负决策变量表示一个决策问题，存在一定的等式或不等式的线性约束条件，有一个希望达到的目标，可表示成决策变量的线性函数。可能是最大化，也可能是最小化。线性规划的一般形式线性规划的一般形式 线性规划的一般模型形式1.2 图解法一个二维的线性规划问题，可以在平面图上求解，三维的线性规划则要在立体图上求解，这就比较麻烦，而维数再高以后就不能图示了。例1是二维空间（平面）线性规划问题，可用作图法直观地来表述它的求解。因存在 必须在直角坐标的第1象限内作图，求解。图1-2图1-3 目标值在（4，2）点，达到最大值14目标函数可能出
8、现的几种情况（1）无穷多最优解(多重最优解)，见图1-4（2）无界解，见图1-5-1（3）无可行解，见图1-5-2图1-4 无穷多最优解(多重最优解)目标函数 max z=2x1+4x2 图1-5-1 无界解 无可行解当存在矛盾的约束条件时，为无可行域。如果在例1的数学模型中增加一个约束条件:该问题的可行域为空集空集，即无可行解，图1-5-2 不存在可行域增加的约束条件线性规划的图解法补充1.可行域的确定可行域的确定补充例补充例1的数学模型为的数学模型为 maxZ=3x1+5 x2 x1 8 2x2 12 3x1+4 x2 36 x1 0,x2 0S.t.x1=82x2=123x1+4 x2=
9、36x1x248123690 0A AB BC(4,6C(4,6)D D五边形五边形OABCD内内(含边界含边界)的任意一点的任意一点(x1，x2)都是满足所有都是满足所有约束条件的一个解，称之可行解约束条件的一个解，称之可行解。满足所有约束条件的解的集合，称之为可行域。即所有约束满足所有约束条件的解的集合，称之为可行域。即所有约束条件共同围城的区域。条件共同围城的区域。2.最优解的确定最优解的确定Z=30Z=42Z=15目标函数 Z=3x1+5 x2 代表以Z为参数的一族平行线。x1=82x2=123x1+4 x2=36x1x248123690 0A AB BC(4,6C(4,6)D D等值
10、线：位于同一直线上的点的目标函数值相同。等值线：位于同一直线上的点的目标函数值相同。最优解：可行解中使目标函数最优最优解：可行解中使目标函数最优(极大或极小极大或极小)的解的解三三、解的可能性、解的可能性x1=82x2=123x1+4 x2=36x1x248123690 0A AB BC(4,6C(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唯一最优解：只有一个最优点。多重最优解：无穷多个最优解。若在两个顶点同时得到最优解，则它们连线上的每一点都是最优解。由线性不
11、等式组成的可行域是凸集(凸集的定义是：集合内部任意两点连线上的点都属于这个集合)。可行域有有限个顶点。设规划问题有n个变量，m个约束，则顶点的个数不多于Cnm个。目标函数最优值一定在可行域的边界达到，而不可能在其内部。二、几点说明二、几点说明无界解：线性规划问题的可行域无界，使目标函数无限增大而无界。（缺乏必要的约束条件）三三、解的可能性（续）、解的可能性（续）例如例如 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.无可行解：若约束条件相互矛盾，则可行域为空集三三、解的
12、可能性（续）、解的可能性（续）例如例如 maxZ=3x1+2 x2 -2x1+x2 2 x1-3 x2 3 x1 0,x2 0-2x1+x2=2x1-3 x2=3x2123-1x1123-1S.t.线性规划问题的数学模型有各种不同的形式，如目标函数有极大化和极小化；约束条件有“”、“”和“”三种情况；决策变量一般有非负性要求，有的则没有。为了求解方便，特规定一种线性规划的标准形式，非标准型可以转化为标准型。标准形式为：目标函数极大化，约束条件为等式，右端常数项bi0，决策变量非负。一一、标准型、标准型1.3 线性规划问题的标准型式1.代数式二、标准型的表达方式二、标准型的表达方式 有代数式、矩
13、阵式：有代数式、矩阵式：maxZ=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxnbm x1,x2,xn 0maxZ=cjxj aijxjbi (i=1,2,m)xj0 (j=1,2,n)简记2.矩阵式矩阵式 目标函数极小化问题目标函数极小化问题 minZ=CTX，只需将等式两端乘以-1 即变为极大化问题。因为minZ=-max(-Z)=CTX，令Z=-Z，则maxZ=-CX 右端常数项非正右端常数项非正 两端同乘以-1 约束条件为不等式约束条件为不等式当约束方程为“”时，左端加入一个非负的松弛
14、变量，就把不等式变成了等式；当约束条件为“”时，不等式左端减去一个非负的剩余变量(也可称松弛变量)即可。决策变量决策变量x xk k没有非负性要求没有非负性要求 令xk=xk-x k，xk=xk，x k 0，用xk、x k 取代模型中xk非标准型向标准型转化非标准型向标准型转化 例3 将例1的数学模型化为标准型。例1的数学模型,加松驰变量后(3)若存在取值无约束的变量xk,可令,其中。例4 将下述线性规划问题化为标准型处理的步骤：(1)用x4-x5替换x3，其中x4，x50；(2)在第一个约束不等式号的左端加入松弛变量x6；(3)在第二个约束不等式号的左端减去剩余变量x7；(4)令z=-z，把
15、求min z 改为求max z，即可得到该问题的标准型例4的标准型标准型 补充例补充例 maxZ=3x1+5 x2 x1 8 2x2 12 3x1+4 x2 36 x1 0,x2 0S.t.x1 +x3 =8 2x2 +x4 =12 3x1+4 x2 +x5=36 x1,x2,x3,x4,x5 0 maxZ=3x1+5 x2+0 x3+0 x4+0 x5 minZ=x1+2 x2+3 x3 x1+2 x2+x35 2x1+3 x2+x36 -x1 -x2 -x3-2 x1 0,x30 例例 minZ=x1+2 x2-3 x3 x1+2 x2-x3 5 2x1+3 x2-x3 6 -x1 -x2
16、 +x3 -2 x1 0,x3 0标准化标准化1S.t.标准化标准化2 minZ=x1+2(x2-x 2)+3 x3 x1+2(x2-x 2)+x35 2x1+3(x2-x 2)+x36 -x1 -(x2-x 2)-x3-2 x1,x2,x 2,x3 0 标准化标准化3 minZ=x1+2(x2-x 2)+3 x3 x1+2(x2-x 2)+x35 2x1+3(x2-x 2)+x36 x1+(x2-x 2)+x3 2 x1,x2,x 2,x3 0标准化标准化4 minZ=x1+2(x2-x 2)+3 x3 x1+2(x2-x 2)+x3+x4=5 2x1+3(x2-x 2)+x36 x1+(x
17、2-x 2)+x3 2 x1,x2,x 2,x3,x4 0标准化标准化5 minZ=x1+2(x2-x 2)+3 x3 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,x5 0标准化标准化6 minZ=x1+2(x2-x 2)+3 x3 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标准化标准化7 maxZ=-x1-2(x2-x 2)-3x3+0 x4+0
18、 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 1.4 线性规划问题的解的概念1.可行解2.基3.基可行解4.可行基可行解：满足约束条件AX=b,X0的解。所有可行解的集合称为可行域。最优解：使目标函数最优的可行解，称为最优解。基mn，且m个方程线性无关，即矩阵A的秩为m；根据线性代数定理可知，nm，则方程组有多个解，这也正是线性规划寻求最优解的余地所在。一、线性规划解的概念一、线性规划解的概念 基变量：与基向量Pj相对应的m个变量xj称为基
19、变量，其余的m-n个变量为非基变量。基解：令所有非基变量等于零，对m个基变量所求的解，对应一个特定的基矩阵能求得一组唯一解，这个对应于基的解称为基解。结合图解来看，基解是各约束方程及坐标轴之间交点的坐标。满足约束条件的基解称为基可行解。基可行解对应可行域的顶点。线性方程组的增广矩阵LP标准型标准型 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 x1x2x3x4x5单位矩阵单位矩阵x3x4x5基变量是基变量是x3,x4,x5非基变量是非基变量是x1,x2令非基变量令非基变量x
20、1=x2=0，得到一个基解，得到一个基解 x3=8，x4=12，x5=36基矩阵：系数矩阵A中任意m列所组成的m阶非奇异子矩阵，称为该线性规划问题的一个基矩阵。或称为一个基，用B表示。称基矩阵的列为基向量，用Pj表示(j=1,2,m)。的基矩阵的基矩阵B最多最多C53=10，如下：，如下：x3x4x5x1x4x5x2x4x5x3x1x5x3x2x5x3x4x1x3x4x2x1x2x3x1x2x4x1x2x5线性方程组的增广矩阵求求LP标准型的基解和基可行解标准型的基解和基可行解 maxZ=3x1+5 x2+0 x3+0 x4+0 x5 x1 +x3 =8 2x2 +x4 =12 3x1+4 x
21、2 +x5=36 x1,x2,x3,x4,x5 0 x1x2x3x4x5单位矩阵单位矩阵例例1的数学模型为的数学模型为 maxZ=3x1+5 x2 x1 8 2x2 12 3x1+4 x2 36 x1 0,x2 0S.t.x1=82x2=123x1+4 x2=36x1x248123690 0A AB BC(4,6C(4,6)D D 4.可行基 对应于基可行解的基，称为可行基。约束方程组(1-5)具有基解的数目最多是 个。一般基可行解的数目要小于基解的数目。以上提到的几种解的概念，它们之间的关系可用图1-6表明。另外还要说明一点，基解中的非零分量的个数小于m个时，该基解是退化解。在以下讨论时，假
22、设不出现退化的情况。以上给出了线性规划问题的解的概念和定义，它们将有助于用来分析线性规划问题的求解过程。图1-6 它们之间的关系小结1.线性规划问题的模型特征2.通过图解法了解如何求解线性规划问题3.为求解高维线性规划问题，必须建立的概念第1章 线性规划与单纯形法 第2节线性规划问题的几何意义2.1 基本概念2.2 几个定理线性规划解几何意义 定理定理1 1.若线性规划问题存在可行域，则其可行域一定是凸集。定理定理2.2.线性规划问题的基可行解对应可行域的顶点。定定理理3.3.若可行域有界，线性规划的目标函数一定可以在可行域的顶点上达到最优。线性规划的基本定理线性规划的基本定理 线线性性规规划
23、划问问题题可可以以有有无无数数个个可可行行解解，最最优优解解只只可可能能在在顶顶点点上上达达到到，而而有有限限个个顶顶点点对对应应的的是是基基可可行行解解，故故只只要要在在有有限限个个基基可行解中寻求最优解即可。可行解中寻求最优解即可。从从一一个个顶顶点点出出发发找找到到一一个个可可行行基基，得得到到一一组组基基可可行行解解，拿拿目目标函数做尺度衡量一下看是否最优。标函数做尺度衡量一下看是否最优。如如若若不不是是，则则向向邻邻近近的的顶顶点点转转移移，换换一一个个基基再再行行求求解解、检检验验，如此迭代循环目标值逐步改善，直至求得最优解。如此迭代循环目标值逐步改善，直至求得最优解。线性规划的解
24、题思路线性规划的解题思路 2.1 基本概念1.凸集2.凸组合3.顶点1.凸集设K是n维欧氏空间的一点集，若任意两点X(1)K，X(2)K的连线上的所有点X(1)+(1-)X(2)K，(01)；则称K为凸集。图1-7实心圆，实心球体，实心立方体等都是凸集，圆环不是凸集。从直观上讲，凸集没有凹入部分，其内部没有空洞。图1-7中的(a)(b)是凸集，(c)不是凸集。图1-2中的阴影部分 是凸集。任何两个凸集的交集是凸集，见图1-7(d)2.凸组合 设X(1)，X(2)，X(k)是n维欧氏空间E中的k个点。若存在1，2，k，且0i1,i=1,2,，k;使X=1X(1)+2X(2)+kX(k)则称X为X
25、(1)，X(2)，X(k)的凸组合。（当0i1时，称为严格凸组合）.3.顶点设K是凸集，XK；若X不能用不同的两点X(1)K和X(2)K的线性组合表示为X=X(1)+(1-)X(2)，(01)则称X为K的一个顶点(或极点)。图中0，Q1,2,3,4都是顶点。2.2 几个定理定理1 若线性规划问题存在可行域，则其可行域是凸集 证：为了证明满足线性规划问题的约束条件的所有点(可行解)组成的集合是凸集，只要证明D中任意两点连线上的点必然在D内即可。设是D内的任意两点；X(1)X(2)。引理 1 线性规划问题的可行解X=(x1,x2,，xn)T为基可行解的充要条件是X的正分量所对应的系数列向量是线性独
26、立的。定理定理2 2 线性规划问题的基可行解X对应于可行 D的顶点。证：证：不失一般性，假设基可行解X的前m个分量为正。故现在分两步来讨论，分别用反证法。（1-8）(1)若X不是基可行解，则它一定不是可行域D的顶点根据引理1，若X不是基可行解，则其正分量所对应的系数列向量P1，P2，Pm线性相关，即存在一组不全为零的数i,i=1,2,m使得1P1+2P2+mPm=0 (1-9)用一个0的数乘(1-9)式再分别与(1-8)式相加和相减，。这样得到(x1-1)P1+(x2-2)P2+(xm-m)Pm=b(x1+1)P1+(x2+2)P2+(xm+m)Pm=b 现取X(1)=(x1-1),(x2-2
27、),(xm-m),0,，0X(2)=(x1+1),(x2+2),(xm+m),0,，0由X(1),X(2)可以得到X=（1/2）X(1)+（1/2）X(2)，即X是X(1)，X(2)连线的中点另一方面，当充分小时，可保证 xii0，i=1,2,m即X(1)，X(2)是可行解。这证明了X 不是可行域 D 的顶点。(2)若X不是可行域D的顶点，则它一定不是基可行解因为X不是可行域 D 的顶点，故在可行域D中可找到不同的两点X(1)=(x1(1),x2(1),xn(1)TX(2)=(x1(2),x2(2),xn(2)T使 X=X(1)+(1-)X(2)，01设X是基可行解，对应向量组P1Pm线性独立
28、。当jm时，有xj=xj(1)=xj(2)=0，由于X(1)，X(2)是可行域的两点。应满足将这两式相减，即得因X(1)X(2)，所以上式系数不全为零，故向量组P1,P2,，Pm线性相关，与假设矛盾。即X不是基可行解。引理2 若K是有界凸集，则任何一点XK可表示为K的顶点的凸组合。本引理证明从略，用以下例子说明这引理。例5 设X是三角形中任意一点，X(1),X(2)和X(3)是三角形的三个顶点，试用三个顶点的坐标表示X(见图1-8)解 任选一顶点X(2)，做一条连线XX(2)；并延长交于X(1)、X(3)连接线上一点X。因X是X(1)、X(3)连线上一点，故可用X(1)、X(3)线性组合表示为
29、X=X(1)+(1-)X(3)01又因X是X与X(2)连线上的一个点，故X=X+(1-)X(2)01将X的表达式代入上式得到X=X(1)+(1-)X(3)+(1-)X(2)=X(1)+(1-)X(3)+(1-)X(2)令 1=,2=(1-),3=(1-)这就得到X=1X(1)+2X(2)+3X(3)ii=1,0i1定理 3 若可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。证证 设X(1),X(2)，X(k)是可行域的顶点，若X(0)不是顶点，且目标函数在X(0)处达到最优z*=CX(0)(标准型是z=max z)。因X(0)不是顶点，所以它可以用D的顶点线性表示为定理3
30、的证明：证：证：设X(1),X(2)，X(k)是可行域的顶点，若X(0)不是顶点，且目标函数在X(0)处达到最优z*=CX(0)(标准型是z=max z)。代入目标函数得在所有的顶点中必然能找到某一个顶点X(m)，使CX(m)是所有CX(i)中最大者。并且将X(m)代替(1-10)式中的所有X(i)，这就得到（1-10）由此得到 X(0)CX(m)根 据 假 设 CX(0)是 最 大 值，所 以 只 能 有 CX(0)=CX(m)即目标函数在顶点X(m)处也达到最大值。有时目标函数可能在多个顶点处达到最大;这时在这些顶点的凸组合上也达到最大值。称这种线性规划问题有无限多个最优解。假设是目标函数
31、达到最大值的顶点，若是这些顶点的凸组合，即于是设：于是：另外，若可行域为无界，则可能无最优解，也可能有最优解，若有也必定在某顶点上得到。根据以上讨论，可以得到以下结论：线性规划问题的所有可行解构成的集合是凸集，也可能为无界域，它们有有限个顶点，线性规划问题的每个基可行解对应可行域的一个顶点；若线性规划问题有最优解，必在某顶点上得到。虽然顶点数目是有限的(它不大于个)，若采用“枚举法”找所有基可行解，然后一一比较，最终可能找到最优解。但当n,m的数较大时，这种办法是行不通的，所以要继续讨论，如何有效地找到最优解，有多种方法，这里仅介绍单纯形法。91线性规划的基本定理线性规划的基本定理定理定理1
32、线性规划问题的可线性规划问题的可行解集是凸集。（即连接行解集是凸集。（即连接线性规划问题任意两个可线性规划问题任意两个可行解的线段上的点仍然是行解的线段上的点仍然是可行解。可行解。)92线性规划的基本定理线性规划的基本定理引理引理1 线性规划问题的可线性规划问题的可行解行解x为基础可行解的充分为基础可行解的充分必要条件是：必要条件是：x的非零分量的非零分量所对应的系数矩阵所对应的系数矩阵A的列向的列向量是线性无关量是线性无关。线性规划的基本定理线性规划的基本定理定理定理 2 线性规划问题的可行线性规划问题的可行解集解集D中的点中的点x是顶点的充分是顶点的充分必要条件是：必要条件是：x是基础可行
33、解。是基础可行解。推论：推论：可行解集可行解集D中的顶点个中的顶点个数是有限的数是有限的。线性规划的基本定理线性规划的基本定理定理定理 3 3 若可行解集若可行解集D D有界，则线性有界，则线性规划问题的最优解，必定在规划问题的最优解，必定在D D的顶点的顶点上达到。上达到。说明说明1：若可行解集：若可行解集D无界，则线性规划问无界，则线性规划问题可能有最优解，也可能无最优解。若有题可能有最优解，也可能无最优解。若有最优解，也必在顶点上达到。最优解，也必在顶点上达到。说明说明2：有时目标函数也可能在多个顶点：有时目标函数也可能在多个顶点上达到最优值。这些顶点的凸组合也是最上达到最优值。这些顶点
34、的凸组合也是最优值。（有无穷多最优解）优值。（有无穷多最优解）几何概念代数概念约束直线满足一个等式约束的解约束半平面满足一个不等式约束的解约束半平面的交集：凸多边形满足一组不等式约束的解约束直线的交点基础解可行域的极点基础可行解目标函数等值线：一组平行线 目标函数值等于一个常数的解线线性性规规划划问问题题可可以以有有无无数数个个可可行行解解，最最优优解解只只可可能能在在顶顶点点上上达达到到，而而有有限限个个顶顶点点对对应应的的是是基基可可行行解解，故故只只要要在在有有限限个个基基可可行行解解中中寻寻求求最最优优解解即即可可。虽虽然然基基本本可可行行解解的的数数目目是是有有限限个个（不不超超过过
35、Cnm个个），但但当当m，n较较大大时时，要要用用“穷穷举举法法”求求出出所所有有基基本本可可行行解解也也是是行行不不通通的的。因因此此，必必须须寻寻求求一一种种更更有有效效的的方方法法。从从一一个个顶顶点点出出发发找找到到一一个个可可行行基基，得得到到一一组组基基可可行行解解，拿拿目目标标函函数数做做尺尺度度衡衡量量一一下下看看是是否否最最优优。如如若若不不是是，则则向向邻邻近近的的顶顶点点转转移移，换换一一个个基基再再行行求求解解、检检验验，如如此此迭迭代代循循环目标值逐步改善，直至求得最优解。环目标值逐步改善，直至求得最优解。线性规划的解题思路线性规划的解题思路 第2节 结束第1章 线性
36、规划与单纯形法第第3节节 单纯形法单纯形法3.1 举例3.2 初始基可行解的确定3.3 最优性检验与解的判断3.4 基变换3.5 迭代（旋转运算）单纯形法(Simplex Method)是美国人丹捷格(G.Dantzig)1947年创建的这种方法简捷、规范，是举世公认的解决线性规划问题行之有效的方法。单纯形法的表现形式：代数法表格法矩阵法单纯形法的求解线性规划问题,解决了三个技术问题:给出第一个基可行解;检验一个基可行解是否是最优解;转换到另一个基可行解。单纯形法求解线性规划的思路：一般线性规划问题具有线性方程组的变量数大于方程个数，这时有不定的解。但可以从线性方程组中找出一个个的单纯形，每一
37、个单纯形可以求得一组解，然后再判断该解使目标函数值是增大还是变小，决定下一步选择的单纯形。这就是迭代，直到目标函数实现最大值或最小值为止。这样问题就得到了最优解，先举一例来说明。注：单纯形是指0维中的点，一维中的线段，二维中的三角形，三维中的四面体，n维空间中的有n+1个顶点的多面体。例如在三维空间中的四面体，其顶点分别为(0，0，0)，(1，0，0)，(0，1，0)，(0，0，1)。具有单位截距的单纯形的方程是xi1，并且xi0，i=1,2,m。3.1 举例例6 试以例1来讨论如何用单纯形法求解。例1的标准型为：约束方程(1-12)式的系数矩阵 从(1-12)式中可以看到x3,x4,x5的系
38、数列向量P3,P4,P5是线性独立的，这些向量构成一个基 对应于B的变量x3,x4,x5为 基变量.从(1-12)式中可以得到（1-13）将(1-13)式代入目标函数(1-11)得到当令非基变量x1=x2=0，便得到z=0。这时得到一个基可行解X(0)X(0)=(0,0,8,16,12)T 这个基可行解表示：工厂没有安排生产产品、；资源都没有被利用，所以工厂的利润指标z=0。从分析目标函数的表达式(1-14)可以看到非基变量x1,x2(即没有安排生产产品，)的系数都是正数，因此将非基变量变换为基变量，目标函数的值就可能增大。从经济意义上讲，安排生产产品或，就可以使工厂的利润指标增加。所以只要在
39、目标函数(1-14)的表达式中还存在有正系数的非基变量，这表示目标函数值还有增加的可能，就需要将非基变量与基变量进行对换。如何确定换入，换出变量一般选择正系数最大的那个非基变量x2为换入变量，将它换入到基变量中去，同时还要确定基变量中有一个要换出来成为非基变量，可按以下方法来确定换出变量。现分析(1-13)式，当将x2定为换入变量后，必须从x3,x4,x5中确定一个换出变量，并保证其余的都是非负，即x3,x4,x50。当x1=0,由(1-13)式得到x2取何值时，才能满足非负要求 从(1-15)式中可以看出，只有选择x2=min(8/2,-,12/4)=3时，才能使(1-15)式成立。因当x2
40、=3时，基变量x5=0，这就决定用x2去替换x5。以上数学描述说明了每生产一件产品，需要用掉各种资源数为(2，0，4)。由这些资源中的薄弱环节，就确定了产品的产量。这里就是由原材料B的数量确定了产品的产量x2=12/4=3件。为了求得以x3,x4,x2为基变量的一个基可行解和进一步分析问题，需将(1-13)中x2的位置与x5的位置对换。得到用高斯消去法将(1-16)式中x2的系数列向量变换为单位列向量。其运算步骤是：=/4；=-2;=,并将结果仍按原顺序排列有：再将(1-17)式代入目标函数(1-11)式得到 从目标函数的表达式(1-18)中可以看到，非基变量x1的系数是正的，说明目标函数值还
41、可以增大，X(1)还不是最优解。于是再用上述方法，确定换入、换出变量，继续迭代，再得到另一个基可行解X(2)X(2)=(2,3,0,8,0)T再经过一次迭代，再得到一个基可行解X(3)X(3)=(4,2,0,0,4)T而这时得到目标函数的表达式是：z=14-1.5x3-0.125x4 (1-19)再检查(1-19)式，可见到所有非基变量x3,x4的系数都是负数。这说明若要用剩余资源x3,x4，就必须支付附加费用。所以当x3=x4=0时，即不再利用这些资源时，目标函数达到最大值。所以X(3)是最优解。即当产品生产4件，产品生产2件，工厂才能得到最大利润。通过上例，可以了解利用单纯形法求解线性规划
42、问题的思路。现将每步迭代得到的结果与图解法做一对比，其几何意义就很清楚了。原例1的线性规划问题是二维的，即两个变量x1,x2；当加入松弛变量x3,x4,x5后，变换为高维的。这时可以想象，满足所有约束条件的可行域是高维空间的凸多面体(凸集)。这凸多面体上的顶点，就是基可行解。初始基可行解 X(0)=(0,0,8,16,12)T就相当于图1-2中的原点(0，0)，X(1)=(0,3,2,16,0)T相当于图1-2中的Q4点(0，3)；X(2)=(2，3，0，8，0)T相当于图1-2中的 Q3点(2，3)，最优解X(3)=(4，2，0，0，4)T相当于图1-2中的 Q2点(4，2)。从初始基可行解
43、X(0)开始迭代，依次得到X(1)，X(2)，X(3)。这相当于图1-2中的目标函数平移时，从0点开始，首先碰到Q4，然后碰到Q3，最后达到Q2。下面讨论一般线性规划问题的求解。一般线性规划问题的求解 3.2 初始基可行解的确定为了确定初始基可行解，要首先找出初始可行基，其方法如下。(1)直接观察(2)加非负的人工变量(1)直接观察若线性规划问题从Pj(j=1,2,n)中一般能直接观察到存在一个初始可行基(2)加非负的人工变量对所有约束条件是“”形式的不等式及等式约束情况，若不存在单位矩阵时，就采用人造基方法。即对不等式约束减去一个非负的剩余变量后，再加上一个非负的人工变量；对于等式约束再加上
44、一个非负的人工变量，总能得到一个单位矩阵。关于这个方法将在本章第5节中进一步讨论。3.33.3最优性检验与解的判别最优性检验与解的判别对线性规划问题的求解结果可能出现唯一最优解、无穷多最优解、无界解和无可行解四种情况，为此需要建立对解的判别准则。一般情况下，经过迭代后(1-23)式变成 将 代入目标函数(1-20)式，整理后得令1最优解的判别定理若 为对应于基B的一个基可行解，且对于一切j=m+1,n，有j0，则X(0)为最优解。称j为检验数。当所有非基变量的j0时，由（1-27）式可知已不存在任一可换入的非基变量，使目标函数继续增大。所以以j0，为最优解的判别准则。2.无穷多最优解判别定理若
45、 为一个基可行解，对于一切j=m+1，,n，有j0，又存在某个非基变量的检验数m+k=0，则线性规划问题有无穷多最优解。证:只需将非基变量xm+k换入基变量中，找到一个新基可行解X(1)。因m+k=0，由(1-27)知z=z0，故X(1)也是最优解。由2.2节的定理3可知X(0)，X(1)连线上所有点都是最优解。3无界解判别定理若 为一基可行解，有一个m+k0，并且对i=1,2,，m，有 存在。那么该线性规划问题具有无界解(或称无最优解)。证:构造一个新的解 X(1)，它的分量为 因 ，所以对任意的0都是可行解，把x(1)代入目标函数内得z=z0+m+k因m+k0，故当+，则z+，故该问题目标
46、函数无界。以上讨论都是针对标准型，即求目标函数极大化时的情况。当求目标函数极小化时，一种情况如前所述，将其化为标准型。如果不化为标准型，只需在上述1，2点中把j0改为j0，第3点中将m+k0改写为m+k0即可。3.4 3.4 基变换基变换 若初始基可行解X(0)不是最优解及不能判别无界时，需要找一个新的基可行解。具体做法是从原可行解基中换一个列向量(当然要保证线性独立)，得到一个新的可行基，这称为基变换。为了换基，先要确定换入变量，再确定换出变量，让它们相应的系数列向量进行对换，就得到一个新的基可行解。1.换入变量的确定 由(1-27)式看到，当某些j0时，xj增大，则目标函数值还可以增大。这
47、时要将某个非基变量xj换到基变量中去(称为换入变量)。若有两个以上的j0，那么选哪个非基变量作为换入变量呢?为了使目标函数值增加得快，从直观上一般选j0中的大者，即则对应的xk为换入变量。但也可以任选或按最小足码选。2.换出变量的确定 设P1，P2，Pm是一组线性独立的向量组，它们对应的基可行解是X(0)。将它代入约束方程组(1-21)得到其他的向量Pm+1,Pm+2,Pm+t,Pn都可以用P1，P2，Pm线性表示，若确定非基变量Pm+t为换入变量，必然可以找到一组不全为0的数(i=1,2,m)使得在(1-29)式两边同乘一个正数，然后将它加到(1-28)式上，得到 新的基可行解。由此得到由X
48、(0)转换到X(1)的各分量的转换公式这里 是原基可行解X(0)的各分量；是新基可行解X(1)的各分量；i,m+t是换入向量Pm+t的对应原来一组基向量的坐标。现在的问题是，这个新解X(1)的m个非零分量对应的列向量是否性独立?事实上，因X(0)的第l个分量对应于X(1)的相应分量是零，即 成立。又因 将(1-32)式减(1-31)式得到由于上式中至少有l,m+t0，所以上式表明P1，P2，Pm是线性相关，这与假设相矛盾。由此可见，X(1)的m个非零分量对应的列向量Pj(j=1,2,m,jl)与Pm+t是线性独立的，即经过基变换得到的解是基可行解。实际上，从一个基可行解到另一个基可行解的变换，
49、就是进行一次基变换。从几何意义上讲，就是从可行域的一个顶点转向另一个顶点(见1-2图解法)3.5 迭代(旋转运算)上述讨论的基可行解的转换方法是用向量方程来描述，在实际计算时不太方便，因此采用系数矩阵法。现考虑以下形式的约束方程组 一般线性规划问题的约束方程组中加入松弛变量或人工变量后，很容易得到上述形式设x1,x2,xm为基变量，对应的系数矩阵是mm单位阵I，它是可行基。令非基变量xm+1,xm+2,xn为零，即可得到一个基可行解。若它不是最优解，则要另找一个使目标函数值增大的基可行解。这时从非基变量中确定xk为换入变量。显然这时为在迭代过程中可表示为其中是经过迭代后对应于的元素值。按规则确
50、定xl为换出变量，xk,xl的系数列向量分别为 为了使xk与xl进行对换，须把Pk变为单位向量，这可以通过(1-33)式系数矩阵的增广矩阵进行初等变换来实现。变换的步骤是：(1)将增广矩阵(1-34)式中的第l行除以al k，得到(2)将(1-34)式中xk列的各元素，除al k变换为1以外，其他都应变换为零。其他行的变换是将(1-35)式乘以ai k(il)后，从(1-34)式的第i行减去，得到新的第i行。由此可得到变换后系数矩阵各元素的变换关系式：是变换后的新元素。(3)经过初等变换后的新增广矩阵是(4)由(1-36)式中可以看到x1,x2,xk,，xm的系数列向量构成mm单位矩阵;它是可