运筹学（第三版）（本科版）：线性规划.ppt

清华大学出版社1二、线性规划与目标规划n第1章 线性规划与单纯形法n第2章 对偶理论与灵敏度分析n第3章 运输问题n第4章 目标规划清华大学出版社2第1章 线性规划与单纯形法线性规划与单纯形法n第1节 线性规划问题及其数学模型n第2节 线性规划问题的几何意义n第3节 单纯形法n第4节 单纯形法的计算步骤n第5节 单纯形法的进一步讨论n第6节 应用举例清华大学出版社3第1节 线性规划问题及其数学模型v1.1 问题的提出v1.2 图解法v1.3 线性规划问题的标准形式v1.4 线性规划问题的解的概念清华大学出版社4第1节 线性规划问题及其数学模型 线性规划是运筹学的一个重要分支线性规划在理论线性规划是运筹学的一个重要分支线性规划在理论上比较成熟，在实用中的应用日益广泛与深入特别是在上比较成熟，在实用中的应用日益广泛与深入特别是在电子计算机能处理成千上万个约束条件和决策变量的线性电子计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了从解决规划问题之后，线性规划的适用领域更为广泛了。

从解决技术问题的最优化设计到工业、农业、商业、交通运输业、技术问题的最优化设计到工业、农业、商业、交通运输业、军事、经济计划和管理决策等领域都可以发挥作用它已军事、经济计划和管理决策等领域都可以发挥作用它已是现代科学管理的重要手段之一解线性规划问题的方法是现代科学管理的重要手段之一解线性规划问题的方法有多种，以下仅介绍有多种，以下仅介绍单纯形法单纯形法 清华大学出版社51.1 问题的提出1.1 1.1 问题的提出问题的提出 例例 1 某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如表1-1所示资源 产 品ⅠⅡ 拥有量设 备1 2 8台时原材料 A 40 16 kg原材料 B04 12 kg每生产一件产品每生产一件产品ⅠⅠ可获利可获利2 2元，每生产一件产品元，每生产一件产品ⅡⅡ可获利可获利3 3元，问应如何安排计划使该工厂获利最多元，问应如何安排计划使该工厂获利最多? ? 清华大学出版社61.1 问题的提出用数学关系式描述这个问题用数学关系式描述这个问题清华大学出版社71.1 问题的提出得到本问题的数学模型为:这就是一个最简单的线性规划模型。

这就是一个最简单的线性规划模型清华大学出版社81.1 问题的提出 例例 2 靠近某河流有两个化工厂(见图1-1)，流经第一化工厂的河流流量为每天500万立方米，在两个工厂之间有一条流量为每天200万立方米的支流 •图1-1化工厂1每天排放含有某种有害物质的工业污水2万立方米，化工厂2每天排放的工业污水为1.4万立方米从化工厂1排出的污水流到化工厂2前，有20%可自然净化根据环保要求，河流中工业污水的含量应不大于0.2%因此两个工厂都需处理一部分工业污水化工厂1处理污水的成本是1000元/万立方米,化工厂2处理污水的成本是800元/万立方米问:在满足环保要求的条件下，每厂各应处理多少工业污水，在满足环保要求的条件下，每厂各应处理多少工业污水，使两个工厂处理工业污水的总费用最小使两个工厂处理工业污水的总费用最小清华大学出版社91.1 问题的提出设：化工厂1每天处理的污水量为x1万立方米；化工厂2每天处理的污水量为x2万立方米建模型之前的分析和计算清华大学出版社101.1 问题的提出得到本问题的数学模型为：清华大学出版社111.1 问题的提出l每一个线性规划问题都用一组决策变量 表示某一方案，这组决策变量的值代表一个具体方案。

一般这些变量的取值是非负且连续的；l都有关于各种资源和资源使用情况的技术数据，创造新价值的数据；l存在可以量化的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示;l都有一个达到某一目标的要求，可用决策变量的线性函数(称为目标函数)来表示按问题的要求不同，要求目标函数实现最大化或最小化上述两个问题具有的共同特征：上述两个问题具有的共同特征：清华大学出版社121.1 问题的提出决策变量及各类系数之间的对应关系清华大学出版社131.1 问题的提出线性规划模型的一般形式清华大学出版社141.2 图解法1.2 1.2 图解法图解法例1是一个二维线性规划问题，因而可用作图法直观地进行求解清华大学出版社151.2 图解法•目标值在（4，2）点，达到最大值14清华大学出版社161.2 图解法（1）无穷多最优解(多重最优解)，见图1-42）无界解，见图1-5-13）无可行解，见图1-5-2通过图解法，可观察到线性规划的解可能出现的几种情况：清华大学出版社171.2 图解法目标函数 max z=2x1+4x2 •图1-4 无穷多最优解（多重最优解）清华大学出版社181.2 图解法图1-5-1 无界解清华大学出版社19 当存在相互矛盾的约束条件时，线性规划问题的可行域为空集。

例如，如果在例1的数学模型中增加一个约束条件: 则该问题的可行域即为空集空集，即无可行解，无可行解的情形1.2 图解法清华大学出版社20增加的约束条件图1-5-2 不存在可行域1.2 图解法清华大学出版社211.3 线性规划问题的标准型式1.3 线性规划问题的标准型式线性规划问题的标准型式清华大学出版社221.3 线性规划问题的标准型式用向量形式表示的标准形式线性规划•线性规划问题的几种表示形式清华大学出版社231.3 线性规划问题的标准型式用矩阵形式表示的标准形式线性规划用矩阵形式表示的标准形式线性规划清华大学出版社241.3 线性规划问题的标准型式(1) 若要求目标函数实现最小化，即min z =CX，则只需将目标函数最小化变换求目标函数最大化，即令z′= −z，于是得到max z′= −CX2) 约束条件为不等式分两种情况讨论：l若约束条件为“≤”型不等式，则可在不等式左端加入非负松弛变量，把原“≤”型不等式变为等式约束；l若约束条件为“≥”型不等式，则可在不等式左端减去一个非负剩余变量(也称松弛变量)，把不等式约束条件变为等式约束3) 若存在取值无约束的变量xk,可令 如何将一般线性规划转化为标准形式的线性规划如何将一般线性规划转化为标准形式的线性规划清华大学出版社251.3 线性规划问题的标准型式例例3 将例1的数学模型化为标准形式的线性规划。

例1的数学模型在加入了松驰变量后变为清华大学出版社261.3 线性规划问题的标准型式例例4 将下述线性规划问题化为标准形式线性规划(1) 用x4−x5替换x3，其中x4，x5≥0；(2) 在第一个约束不等式左端加入松弛变量x6；(3) 在第二个约束不等式左端减去剩余变量x7；(4) 令z′= −z，将求min z 改为求max z′即可得到该问题的标准型清华大学出版社271.3 线性规划问题的标准型式例例4 例4的标准型清华大学出版社281.4 线性规划问题的解概念v1.可行解(Feasible Solution)v2.基(Basic)v3.基可行解(Basic Feasible Solution, BF)v4.可行基(Feasible Basis)清华大学出版社291.4 线性规划问题的解的概念v定义¢满足约束条件(1-5)、(1-6)式的解X=(x1,x2，…，xn)T，称为线性规划问题的可行解，其中使目标函数达到最大值的可行解可行解称为最最优解解1. 可行解可行解清华大学出版社301.4 线性规划问题的解的概念2. 基，基向量，基变量基，基向量，基变量清华大学出版社311.4 线性规划问题的解的概念满足非负条件（1-6）的基解，称为基可行解. 基可行解的非零分量的数目不大于m，并且都是非负的。

3 基可行解基可行解清华大学出版社321.4 线性规划问题的解的概念l对应于基可行解的基，称为可行基l约束方程组(1-5)具有的基解的数目最多是 个，一般基可行解的数目要小于基解的数目l以上提到了几种解的概念，它们之间的关系可用图1-6表明l说明：当基解中的非零分量的个数小于m时，该基解是退化解在以下讨论时，假设不出现退化的情况 4 可行基可行基清华大学出版社331.4 线性规划问题的解的概念•不同解之间的关系不同解之间的关系清华大学出版社34第2节 线性规划问题的几何意义v2.1 基本概念v2.2 几个定理清华大学出版社35 2.1 基本概念1.凸集2.凸组合3.顶点清华大学出版社362.1 基本概念v定义¢设K是n维欧氏空间的一点集，若任意两点X(1)∈K，X(2)∈K的连线上的所有点αX(1)+(1−α)X(2)∈K，(0≤α≤1)，则称K为凸集图1-71.凸集凸集清华大学出版社372.1 基本概念v实心圆，实心球体，实心立方体等都是凸集，圆环不是凸集从直观上讲，凸集没有凹入部分，其内部没有空洞图1-7中的(a)(b)是凸集，(c)不是凸集v图1-2中的阴影部分是凸集。

v任何两个凸集的交集是凸集，见图1-7(d)清华大学出版社382.1 基本概念v设X(1)，X(2)，…，X(k)是n维欧氏空间En中的k个点若存在μ1，μ2，…，μk，且0≤μi≤1, i=1,2,…，k 使 X=μ1X(1)+μ2X(2)+…+μkX(k) 则称X为X(1)，X(2)，…，X(k)的一个凸组合（当0＜μi＜1时，称为严格凸组合）2. 凸组合凸组合清华大学出版社392.1 基本概念v设K是凸集，X∈K；若X不能用不同的两点X(1)∈K和X(2)∈K的线性组合表示为 X=αX(1)+(1−α)X(2)，(0＜α＜1) 则称X为K的一个顶点(或极点) 图中的0，Q1,2,3,4都是顶点3. 顶点顶点清华大学出版社402.2 几个定理v定理定理1 : 若线性规划问题存在可行域，则其可行域 是凸集清华大学出版社412.2 几个定理v定理1的证明：只需证明D中任意两点连线上的点必然在D内即可设 是D内的任意两点；且X(1)≠X(2)清华大学出版社422.2 几个定理清华大学出版社432.2 几个定理v引理引理 1 线性规划问题的可行解X=(x1,x2,…，xn)T为基可行解的充要条件是：X的正分量所对应的系数列向量是线性独立的。

清华大学出版社442.2 几个定理定理定理2 线性规划问题的基可行解X对应于可行域D的顶点 证：：不失一般性，假设基可行解X的前m个分量为正 故 现分两步来讨论，分别用反证法清华大学出版社452.2 几个定理 (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 清华大学出版社462.2 几个定理 因X 不是可行域D的顶点，故在可行域D中可找到不同的两点 X(1)=(x1(1),x2(1),…,xn(1))T X(2)=(x1(2),x2(2),…,xn(2))T 使得 X=αX(1)+(1−α) X(2) ， 0＜α＜1 设X是基可行解，对应的向量组P1…Pm线性独立，故当j＞m时，有xj=xj(1)=xj(2)=0。

由于X(1)，X(2)是可行域的两点，因而满足 （2）若X不是可行域D的顶点，则它一定不是基可行解将两式相减，得 因X(1)≠X(2)，所以上式中的系数不全为零，故向量组P1,P2,…，Pm线性相关，与假设矛盾，即X不是基可行解清华大学出版社472.2 几个定理v引理引理2 若K是有界凸集，则任何一点X∈K可表示为K的顶点的凸组合 本引理的证明从略，用以下例子说明本引理的结论v例例5 设X是三角形中任意一点，X(1)，X(2)和X(3)是三角形的三个顶点，试用三个顶点的坐标表示X(见图1-8)图1-8清华大学出版社482.2 几个定理 解：解：任选一顶点X(2)，做一条连线XX(2)，并延长交于X(1)、X(3)连接线上一点X′因为X′是X(1)、X(3)连线上一点，故可用X(1)、X(3)线性组合表示为X′=αX(1)+(1−α)X(3) 0＜α＜1 又因X是X′与X(2)连线上的一个点，故X=λX′+(1 − λ)X(2) 0＜λ＜1 将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)∑iμi=1, 0＜μi＜1清华大学出版社492.2 几个定理v定理定理 3 若可行域有界，则线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。

证：： 设X(1),X(2)，…，X(k)是可行域的顶点，若X(0)不是顶点，且目标函数在X(0)处达到最优z*=CX(0)(标准型是z=max z) 因X(0)不是顶点，所以它可以用D的顶点线性表示为 代入目标函数得清华大学出版社502.2 几个定理在所有的顶点中必然能找到某一个顶点X(m)，使CX(m)是所有CX(i)中最大者并且将X(m)代替(1-10)式中的所有X(i)，得到由此得到 X(0)≤CX(m)根据假设CX(0)是最大值，所以只能有 CX(0)=CX(m)即目标函数在顶点X(m)处也达到最大值 清华大学出版社512.2 几个定理有时，目标函数可能在多个顶点处达到最大，这时在这些顶点的凸组合上也达到最大值，这时线性规划问题有无限多个最优解假设是目标函数达到最大值的顶点，则对这些顶点的凸组合，有清华大学出版社522.2 几个定理设：于是：另外，若可行域为无界，则可能无最优解，也可能有最优解，若有最优解，也必定在某顶点上得到清华大学出版社53基本结论l线性规划问题的所有可行解构成的集合是凸集，也可能为无界域，它们有有限个顶点，线性规划问题的每个基可行解对应可行域的一个顶点。

l若线性规划问题有最优解，必在某顶点上得到虽然顶点数目是有限的，若采用“枚举法”找所有基可行解，然后一一比较，最终必然能找到最优解但当n,m较大时，这种办法是行不通的，所以要继续讨论如何有效寻找最优解的方法本课程将主要介绍单纯形法单纯形法(simplex method)l备注：单纯形备注：单纯形(单纯形是指单纯形是指0维中的点，一维中的线段，二维中的三角形，三维中的点，一维中的线段，二维中的三角形，三维中的四面体，维中的四面体，n维空间中的有维空间中的有n+1个顶点的多面体例如在三维空间中的四面体，个顶点的多面体例如在三维空间中的四面体，其顶点分别为其顶点分别为(0,0,0)，，(1,0,0)，，(0,1,0)，，(0,0,1)清华大学出版社54第第3节节 单纯形法单纯形法v3.1 举例v3.2 初始基可行解的确定v3.3 最优性检验与解的判断v3.4 基变换v3.5 迭代（旋转运算）清华大学出版社55单纯形法求解线性规划的思路： 一般线性规划问题具有线性方程组的变量数大于一般线性规划问题具有线性方程组的变量数大于方程个数，这时有不定的解但可以从线性方程组中方程个数，这时有不定的解。

但可以从线性方程组中找出一个个的单纯形，找出一个个的单纯形，每一个单纯形可以求得一组解每一个单纯形可以求得一组解，，然后再判断该解使目标函数值是增大还是变小，决定然后再判断该解使目标函数值是增大还是变小，决定下一步选择的单纯形下一步选择的单纯形这就是这就是迭代迭代，直到目标函数实，直到目标函数实现最大值或最小值为止这样，问题就得到了最优解，现最大值或最小值为止这样，问题就得到了最优解，先举一例来说明先举一例来说明清华大学出版社563.1 举例例例6 试以例1来讨论如何用单纯形法求解解：已知本例的标准型为：清华大学出版社573.1 举例约束条件(1-12)式的系数矩阵为从(1-12)式可看到x3,x4,x5的系数构成的列向量清华大学出版社583.1 举例P3 ,P4,P5是线性独立的，这些向量构成一个基B 对应于B的变量x3,x4,x5为基变量. 从(1-12)式中可以得到（1-13）清华大学出版社593.1 举例将(1-13)式代入目标函数(1-11)：得到当令非基变量x1=x2=0，便得到z=0这时得到一个基可行解X(0) X(0)=(0,0,8,16,12)T 本基可行解的经济含义是：工厂没有安排生产产品Ⅰ、Ⅱ，资源都没有被利用，所以工厂的利润为z=0。

清华大学出版社603.1 举例 从分析目标函数的表达式从分析目标函数的表达式(1-14)可以看到：可以看到： 非基变量非基变量x1,x2(即没有安排生产产品即没有安排生产产品Ⅰ，，Ⅱ)的系数的系数都是正数，因此将非基变量变换为基变量，目标函都是正数，因此将非基变量变换为基变量，目标函数的值就可能增大从经济意义上讲，安排生产产数的值就可能增大从经济意义上讲，安排生产产品品Ⅰ或或Ⅱ，就可以使工厂的利润指标增加所以只要，就可以使工厂的利润指标增加所以只要在目标函数在目标函数(1-14)的表达式中还存在有正系数的非基的表达式中还存在有正系数的非基变量，这表示目标函数值还有增加的可能，就需要变量，这表示目标函数值还有增加的可能，就需要将非基变量与基变量进行对换将非基变量与基变量进行对换清华大学出版社613.1 举例v如何确定换入、换出变量¢一般选择正系数最大的那个非基变量x2为换入变量，将它换到基变量中，同时还要确定基变量中哪一个换出来成为非基变量¢可按以下方法来确定换出变量：o分析(1-13)式，当将x2定为换入变量后，必须从x3,x4,x5中确定一个换出变量，并保证其余的变量仍然非负，即x3,x4,x5≥0。

清华大学出版社623.1 举例v如何确定换入、换出变量¢当x1=0时，由(1-13)式得到清华大学出版社633.1 举例v如何确定换入、换出变量¢当x2取何值时，才能满足非负要求呢？ 从(1-15)式可看出，只有选择 x2=min(8/2,-,12/4)=3时，才能使(1-15)式成立 因当x2=3时，基变量x5=0，这就决定用x2去替换x5 以上数学描述说明，每生产一件产品Ⅱ，需要用掉的各种资源数为(2，0，4)由这些资源中的薄弱环节，就确定了产品Ⅱ的产量 这里就是由原材料B的数量确定了产品Ⅱ的产量x2=12/4=3件清华大学出版社643.1 举例v如何确定换入、换出变量¢为了求得以x3,x4,x2为基变量的一个基可行解和进一步分析问题，需将(1-13)中x2的位置与x5的位置对换，得到清华大学出版社653.1 举例v将(1-16)式中x2的系数列向量变换为单位列向量其运算步骤是：v③′=③/4；①′=①-2×③′;②′=②,v并将结果仍按原顺序排列有：高斯消去法高斯消去法清华大学出版社663.1 举例v再将(1-17)式代入目标函数(1-11)式得到清华大学出版社673.1 举例 从目标函数的表达式(1-18)可看到，非基变量x1的系数是正的，说明目标函数值还可以增大，即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件时，工厂可以得到最大利润清华大学出版社68小结v通过上例，可将每步迭代得到的结果与图解法做一对比v例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对应于图中的Q4点(0，3)； X(2)=(2，3，0，8，0)T对应于Q3点(2，3)；最优解X(3)=(4，2，0，0，4)T相当于图中的 Q2点(4，2)。

从初始基可行解X(0)开始迭代，依次得到X(1)，X(2)，X(3)，相当于图中的目标函数平移时，从0点开始，首先碰到Q4，然后碰到Q3，最后达到Q2清华大学出版社693.2 初始基可行解的确定v为了确定初始基可行解，要首先找出初始可行基，其方法如下¢(1)直接观察¢(2)加松弛变量¢(3)加非负的人工变量清华大学出版社703.2 初始基可行解的确定从线性规划问题的系数构成的列向量Pj(j=1,2,…,n)中，通过直接观察，找出一个初始可行基(1)直接观察直接观察清华大学出版社713.2 初始基可行解的确定 对所有约束条件为“≤”形式的不等式，利用化标准型的方法，在每个约束条件的左端加上一个松弛变量经过整理，重新对xj及aij (i=1,2,…,m; j=1,2,…,n)进行编号，则可得下列方程组（x1,x2,…,xm 为松弛变量）：(2)加松弛变量加松弛变量清华大学出版社723.2 初始基可行解的确定于是，(1-22)中含有一个m×m阶单位矩阵，初始可行基B即可取该单位矩阵将(1-22)式每个等式移项得清华大学出版社733.2 初始基可行解的确定令xm+1=xm+2=…=xn=0，由(1-23)式可得xi=bi (i=1,2,…,m)得到一个初始基可行解。

又因bi≥0(在1-3节中已做过规定)，所以得到一个初始基可行解 X=(x1,x2,…,xm,0，…，0)T n−m个 =(b1,b2,…,bm,0，…，0)T n−m个清华大学出版社743.2 初始基可行解的确定v对所有约束条件为“≥”形式的不等式及等式约束情况，若不存在单位矩阵时，可采用人造基方法¢即对不等式约束，减去一个非负的剩余变量，再加上一个非负的人工变量；¢对于等式约束，再加上一个非负的人工变量v这样，总能在新的约束条件系数构成的矩阵中得到一个单位矩阵3)加非负的人工变量加非负的人工变量清华大学出版社753.3 最优性检验与解的判别v由于线性规划问题的求解可能出现唯一最优解、无穷多最优解、无界解和无可行解等四种情况，因此，需要建立解的判别准则。

一般情况下，经过迭代后(1-23)式变成 清华大学出版社763.3 最优性检验与解的判别将 代入目标函数(1-20)式，整理后得清华大学出版社773.3 最优性检验与解的判别•令清华大学出版社783.3 最优性检验与解的判别 若 为对应于基B的一个基可行解，且对于一切j=m+1,…,n，有σj≤0，则X(0)为最优解称σj为检验数1.最优解的判别定理最优解的判别定理清华大学出版社793.3 最优性检验与解的判别 若 为一个基可行解，对于一切j=m+1，…,n，有σj≤0，又存在某个非基变量的检验数σm+k=0，则线性规划问题有无穷多最优解 证: 只需将非基变量xm+k换入基变量中，找到一个新基可行解X(1)因σm+k=0，由(1-27)知z=z0，故X(1)也是最优解由2.2节的定理3可知，X(0)和X(1)连线上所有点都是最优解2.无穷多最优解判别定理无穷多最优解判别定理清华大学出版社803.3 最优性检验与解的判别 若 为一基可行解， 有一个σm+k＞0，并且对i=1,2,…，m，有a‘i,m+k≤0，那么该线性规划问题具有无界解(或称无最优解)。

证: 构造一个新的解 X(1)，它的分量为3．无界解判别定理．无界解判别定理清华大学出版社813.3 最优性检验与解的判别 因 ，所以对任意的λ＞0都是可行解，把x(1)代入目标函数内，得到z=z0+λσm+k 因σm+k＞0，故当λ→+∞，则z→+∞，故该问题目标函数无界清华大学出版社823.3 最优性检验与解的判别v其它情形¢以上讨论都是针对标准型的，即求目标函数极大化时的情况当要求目标函数极小化时，一种情况是将其化为标准型¢如果不化为标准型，只需在上述1，2点中把σj≤0改为σj≥0，第3点中将σm+k＞0改写为σm+k＜0即可清华大学出版社833.4 基变换v若初始基可行解X(0)不是最优解及不能判别无界时，需要找一个新的基可行解v具体做法是¢从原可行解基中换一个列向量(当然要保证线性独立)，得到一个新的可行基，称为基变换为了换基，先要确定换入变量，再确定换出变量，让它们相应的系数列向量进行对换，就得到一个新的基可行解清华大学出版社841.换入变量的确定v由(1-27)式可知，当某些σj＞0时，若xj增大，则目标函数值还可以增大。

这时需要将某个非基变量xj换到基变量中去(称为换入变量)v若有两个以上的σj＞0，那么选哪个非基变量作为换入变量呢?为了使目标函数值增加得快，从直观上看应选σj＞0中的较大者，即由 应选择xk为换入变量清华大学出版社852.换出变量的确定v设P1，P2，…，Pm是一组线性独立的向量组，它们对应的基可行解是X(0)，将它代入约束方程组(1-21)得到其他的向量Pm+1,Pm+2,…,Pm+t,…,Pn都可以用P1，P2，…，Pm线性表示若确定非基变量Pm+t为换入变量，必然可以找到一组不全为0的数(i=1,2,…,m)使得清华大学出版社862.换出变量的确定在(1-29)式两边同乘一个正数θ，然后将它加到(1-28)式上，得到 清华大学出版社872.换出变量的确定清华大学出版社882.换出变量的确定清华大学出版社892.换出变量的确定v新的基可行解为清华大学出版社902.换出变量的确定v由此得到由X(0)转换到X(1)的各分量的转换公式清华大学出版社912.换出变量的确定这里 是原基可行解X(0)的分量； 是新基可行解X(1)的各分量；vβi,m+t是换入向量Pm+t对应原来一组基向量的坐标。

v现在的问题是，这个新解X(1)的m个非零分量对应的列向量是否独立?事实上，因为X(0)的第一个分量对应于X(1)的相应分量是零，即 清华大学出版社922.换出变量的确定成立又因将(1-32)式减(1-31)式得到清华大学出版社932.换出变量的确定由于上式中至少有βl,m+t≠0，所以上式表明P1，P2，…，Pm是线性相关，这与假设相矛盾由此可见，X(1)的m个非零分量对应的列向量Pj(j=1,2,…,m,j≠l)与Pm+t是线性独立的，即经过基变换得到的解是基可行解实际上，从一个基可行解到另一个基可行解的变换，就是进行一次基变换从几何意义上讲，就是从可行域的一个顶点转向另一个顶点 清华大学出版社943.5 迭代(旋转运算)上述讨论的基可行解的转换方法是用向量方程描述的，在实际计算时不太方便，因此下面介绍系数矩阵法系数矩阵法考虑以下形式的约束方程组一般线性规划问题的约束方程组中加入松弛变量或人工变量后，很容易得到上述形式清华大学出版社953.5 迭代(旋转运算)设x1,x2,…,xm为基变量，对应的系数矩阵是m×m单位阵I，它是可行基令非基变量xm+1,xm+2,…,xn为零，即可得到一个基可行解。

若它不是最优解，则要另找一个使目标函数值增大的基可行解这时从非基变量中确定xk为换入变量显然这时θ为在迭代过程中θ可表示为•其中 是经过迭代后对应于 的元素值清华大学出版社963.5 迭代(旋转运算)按θ规则确定xl为换出变量，xk, xl的系数列向量分别为清华大学出版社973.5 迭代(旋转运算)为了使xk与xl进行对换，须把Pk变为单位向量，这可以通过(1-33)式系数矩阵的增广矩阵进行初等变换来实现清华大学出版社983.5 迭代(旋转运算)变换的步骤是：(1) 将增广矩阵(1-34)式中的第l行除以al k，得到(2) 将(1-34)式中xk列的各元素，除al k变换为1以外，其他都应变换为零其他行的变换是将(1-35)式乘以aik(i≠l)后，从(1-34)式的第i行减去，得到新的第i行清华大学出版社993.5 迭代(旋转运算)由此可得到变换后系数矩阵各元素的变换关系式 是变换后的新元素 清华大学出版社1003.5 迭代(旋转运算)(3) 经过初等变换后的新增广矩阵是清华大学出版社1013.5 迭代(旋转运算)(4) 由(1-36)式中可以看到x1,x2,…,xk,…，xm的系数列向量构成m×m单位矩阵;它是可行基。

当非基变量xm+1,…，xl,…,xn为零时，就得到一个基可行解X(1)在上述系数矩阵的变换中，元素al k称为主元素主元素，它所在列称为主元列，它所在行称为主元行，元素al k位置变换后为1 清华大学出版社1023.5 迭代(旋转运算)例例7 7 试用上述方法计算例6的两个基变换 解：例6的约束方程组的系数矩阵写成增广矩阵当以x3,x4,x5为基变量，x1,x2为非基变量，令x1,x2=0，可得到一个基可行解X(0)=(0,0,8,16,12)T清华大学出版社1033.5 迭代(旋转运算)现用x2去替换x5，于是将x3,,x4, x2的系数矩阵变换为单位矩阵，经变换后为 令非基变量x1,x5=0，得到新的基可行解X(1)=(0,3,2,16,0)T清华大学出版社104第4节 单纯型法的计算步骤v4.1 单纯型表v4.2 计算步骤清华大学出版社1054.1 单纯型表v为了便于理解计算关系，现设计一种计算表，称为单纯形表，其功能与增广矩阵相似v将(1-22)式与目标函数组成n+1个变量，m+1个方程的方程组清华大学出版社106线性规划的方程组清华大学出版社107线性规划的方程组v为了便于迭代运算，可将上述方程组写成增广矩阵形式清华大学出版社108线性规划的方程组v若将z看作不参与基变换的基变量，它与x1,x2,…,xm的系数构成一个基，这时可采用行初等变换将c1,c2,…,cm变换为零，使其对应的系数矩阵为单位矩阵。

得到表1-2清华大学出版社109清华大学出版社110线性规划的方程组v表1-2的说明¢XB列中填入基变量，这里是x1，x2,…，xm；¢CB列中填入基变量的价值系数，这里是c1,c2,…,cm；它们是与基变量相对应的；¢b列中填入约束方程组右端的常数；¢cj行中填入变量的价值系数c1,c2,…,cn；¢θi列的数字是在确定换入变量后，按θ规则计算后填入；¢最后一行称为检验数行，对应各非基变量xj的检验数是清华大学出版社1114.2 计算步骤v表1-2称为初始单纯形表，每迭代一步构造一个新单纯形表v计算步骤：¢(1) 按数学模型确定初始可行基和初始基可行解，建立初始单纯形表¢(2) 计算各非基变量xj的检验数， 检查检验数，若所有检验数 则已得到最优解，可停止计算否则转入下一步清华大学出版社1124.2 计算步骤¢(3)在σj＞0,j=m+1,…,n中，若有某个σk对应xk的系数列向量Pk≤0，则此问题是无界，停止计算 否则，转入下一步¢(4) 根据max(σj＞0)=σk，确定xk为换入变量，按θ规则计算清华大学出版社1134.2 计算步骤¢(5) 以alk为主元素进行迭代(即用高斯消去法或称为旋转运算)，把xk所对应的列向量 将XB列中的xl换为xk，得到新的单纯形表。

重复(2)～(5)，直到终止清华大学出版社1144.2 计算步骤v现用例1的标准型来说明上述计算步骤v(1) 取松弛变量x3,x4,x5为基变量，它对应的单位矩阵为基这就得到初始基可行解X(0)=(0,0,8,16,12)Tv将有关数字填入表中，得到初始单纯形表，见表1-3表中左上角的cj是表示目标函数中各变量的价值系数在CB列填入初始基变量的价值系数，它们都为零清华大学出版社1154.2 计算步骤表 1-3清华大学出版社1164.2 计算步骤v计算非基变量的检验数 各非基变量的检验数为σ1=c1−z1=2−(0×1+0×4+0×0)=2σ2=c2−z2=3−(0×2+0×0+0×4)=3 填入表1-3的底行对应非基变量处清华大学出版社1174.2 计算步骤 它所在行对应的x5为换出变量，x2所在列和x5所在行的交叉处 [4]称为主元素或枢元素(pivot element)清华大学出版社1184.2 计算步骤 (4) 以[4]为主元素进行旋转运算或迭代运算，即初等行变换，使P2变换为(0,0,1)T,在XB 列中将x2 替换x5 ,于是得到新表1-4. 换入变量换入变量换出变量换出变量主元素主元素清华大学出版社1194.2 计算步骤 (5) 检查表1-4的所有cj−zj,这时有c1−z1=2；说明x1应为换入变量。

重复(2)～(4)的计算步骤，得表1-5 换入变量换入变量换出变量换出变量主元素主元素因为还存在检验数>0，继续进行迭代清华大学出版社1204.2 计算步骤 (6) 表1-6最后一行的所有检验数都已为负或零这表示目标函数值已不可能再增大，于是得到最优解 X*=X(3)=(4,2,0,0,4)T 目标函数的最大值 z*=14清华大学出版社121第5节 单纯形法的进一步讨论v5.1 人工变量法v5.2 退化v5.3 检验数的几种表示形式清华大学出版社1225.1 人工变量法设线性规划问题的约束条件其中没有可作为初始基的单位矩阵，则分别给每一个约束方程加入人工变量xn+1,…,xn+m，得到清华大学出版社1235.1 人工变量法v以xn+1,…，xn+m为基变量，并可得到一个m×m单位矩阵令非基变量x1,…,xn为零，便可得到一个初始基可行解X(0)=(0,0,…,0,b1,b2,…,bm)Tv因为人工变量是后加入到原约束条件中的虚拟变量，要求经过基的变换将它们从基变量中逐个替换出来。

v基变量中不再含有非零的人工变量，这表示原问题有解v若在最终表中当所有cj−zj≤0，而在其中还有某个非零人工变量，这表示原问题无可行解v以下讨论如何解含有人工变量的线性规划问题清华大学出版社1245.1 人工变量法 例例8 现有线性规划问题，试用大M法求解1.大M法清华大学出版社1255.1 人工变量法解解 在上述问题的约束条件中加入松弛变量x4，剩余变量x5，人工变量x6，x7，得到 这里M是一个任意大的正数 清华大学出版社1265.1 人工变量法 因本例的目标函数是要求min，所以用所有cj−zj≥0来判别目标函数是否实现了最小化.用单纯形法进行计算时，见表1-6清华大学出版社1275.1 人工变量法在表1-6的最终计算结果可看出，已得到最优解：x1=4,x2=1,x3=9，x4=x5=x6=x7=0；目标函数z = −2清华大学出版社1285.1 人工变量法v以下介绍求解含有人工变量线性规划问题的两阶段法v第一阶段：不考虑原问题是否存在基可行解；给原线性规划问题加入人工变量，并构造仅含人工变量的目标函数和要求实现最小化2.两阶段法两阶段法清华大学出版社1295.1 人工变量法v第一阶段：不考虑原问题是否存在基可行解；给原线性规划问题加入人工变量，并构造仅含人工变量的目标函数和要求实现最小化。

如清华大学出版社1305.1 人工变量法v第一阶段求解¢用单纯形法求解上述模型若得到的最优值w=0，说明原问题存在基可行解，可以进行第二段计算否则原问题无可行解，应停止计算v第二阶段求解¢从第一阶段计算得到的最终表中除去人工变量，将目标函数行的系数，换为原问题的目标函数系数，作为第二阶段计算的初始表各阶段的计算方法及步骤与第3节介绍的单纯形法相同 清华大学出版社1315.1 人工变量法v例例9 试用两阶段法求解如下线性规划问题：清华大学出版社1325.1 人工变量法v解解: : 先在上述线性规划问题的约束方程中加入人工变量，给出第一阶段的数学模型为：清华大学出版社1335.1 人工变量法v第一阶段用单纯形法求解，见表1-7求得的结果是w=0，最优解是x1=0,x2=1,x3=1,x4=12,x5=x6=x7=0v因为人工变量x6=x7=0，所以(0，1，1，12，0)T是原线性规划问题的基可行解v于是可以进行第二阶段运算将第一阶段的最终表中的人工变量取消，填入原问题的目标函数系数，进行第二阶段计算，见表1-8清华大学出版社1345.1 人工变量法•表 1-7清华大学出版社1355.1 人工变量法表 1-8从表1-8得到最优解：x1=4,x2=1,x3=9,目标函数值 z=−2清华大学出版社1365.2 退化v在单纯形法计算中用θ规则确定换出变量时，有时存在两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于零，这就出现了退化解。

v这时换出变量xl=0，迭代后目标函数值不变这时不同基表示为同一顶点有人构造了一个特例，当出现退化时，进行多次迭代，而基从B1,B2，…又返回到B1，即出现计算过程的循环，便永远达不到最优解 清华大学出版社1375.2 退化v尽管实际计算过程中循环现象极少出现，但还是有可能发生的如何解决这问题? 先后有人提出了“摄动法”，“字典序法”1974年由勃兰特(Bland)提出一种简便的规则，简称勃兰特规则：¢(1) 选取cj−zj＞0中下标最小的非基变量xk为换入变量，即k=min(j｜ cj−zj＞0 )¢(2) 当按θ规则计算存在两个和两个以上最小比值时，选取下标最小的基变量为换出变量¢按勃兰特规则计算时，一定能避免出现循环清华大学出版社1385.3 检验数的几种表示形式v本书以max z=CX；AX=b，X≥0为标准型，以cj−zj≤0，（j=1,2,…,n）作为最优解的判别准则v由于还有其他形式的问题，为了避免混淆，将有关情况归纳如下：¢设x1,x2,…,xm为约束方程的基变量，于是可得清华大学出版社1395.3 检验数的几种表示形式¢将它们代入目标函数后，可有两种表达形式清华大学出版社140判别准则的选择¢当要求目标函数实现最大化时，若用(1-37)式来分析，就需要用cj−zj≤0,（j=1,2，…,n）作为判别准则；若用(1-38)式来分析，就需要用zj−cj≥0,（j=1,2,…,n）作为判别准则。

¢当要求目标函数实现最小化时，可用(1-37)式或(1-38)式来分析，这时可分别用cj−zj≥0或zj−cj≤0，（j=1,2,…,n）来判别目标函数是否已达到最小清华大学出版社141几种判别准则的汇总清华大学出版社1425.4 单纯形法小结v(1) 根据实际问题给出数学模型，列出初始单纯形表进行标准化，见表1-10分别以每个约束条件中的松弛变量或人工变量为基变量，列出初始单纯形表表1-10清华大学出版社143清华大学出版社144第6节 应用举例v一般讲，一个经济、管理问题凡满足以下条件时，才能建立线性规划模型¢ (1) 要求解问题的目标函数能用数值指标来表示，且为线性函数；¢ (2) 存在着多种方案及有关数据； ¢ (3) 要求达到的目标是在一定约束条件下实现的，这些约束条件可用线性等式或不等式来描述清华大学出版社145第6节 应用举例v例例10 合理利用线材问题合理利用线材问题现要做100套钢架，每套需用长为2.9m，2.1m和1.5m的元钢各一根已知原料长7.4m，问应如何下料，使用的原材料最省v解：解：最简单做法是，在每一根原材料上截取2.9m，2.1m和1.5m的元钢各一根组成一套，每根原材料剩下料头0.9m（7.4-2.9-2.1-1.5=0.9)。

为了做100套钢架，需用原材料100根，共有90m料头若改为用套裁，这可以节约原材料下面有几种套裁方案，都可以考虑采用见表1-11表1-11清华大学出版社146第6节 应用举例v为了得到100套钢架，需要混合使用各种下料方案设按Ⅰ方案下料的原材料根数为x1,Ⅱ方案为x2，Ⅲ方案为x3，Ⅳ方案为x4,Ⅴ方案为x5根据表1-11的方案，可列出以下数学模型：清华大学出版社147第6节 应用举例v在以上约束条件中加入人工变量x6,x7,x8；然后用表1-12进行计算表1-12清华大学出版社148第6节 应用举例v第1次计算清华大学出版社149第6节 应用举例v第2次计算清华大学出版社150第6节 应用举例v最终计算表（第3次计算）由计算得到最优下料方案是：•按Ⅰ方案下料30根；•Ⅱ方案下料10根；•Ⅳ方案下料50根•即需90根原材料可以制造100套钢架有非基变量的检验数为零，所以存在多重最优解 清华大学出版社151第6节 应用举例v例例11 （配料问题）某工厂要用三种原材料C、P、H混合调配出三种不同规格的产品A、B、D已知产品的规格要求，产品单价，每天能供应的原材料数量及原材料单价，分别见表1-13和表1-14。

该厂应如何安排生产，使利润收入为最大? 解：解： 如以AC表示产品A中C的成分，AP表示产品A中P的成分，依次类推表1-13清华大学出版社152第6节 应用举例v根据表1-13有：这里 AC+AP+AH=A； BC+BP+BH=B (1-40)将(1-40)逐个代入(1-39)并整理得到清华大学出版社153第6节 应用举例v表1-14表明这些原材料供应数量的限额加入到产品A、B、D的原材料C总量每天不超过100kg，P的总量不超过100kg，H总量不超过60kg表1-14清华大学出版社154第6节 应用举例v由此得约束条件AC+BC+DC≤100AP+BP+DP≤100AH+BH+DH≤60v在约束条件中共有9个变量，为计算和叙述方便，分别用x1,…,x9表示令x1=Ac, x2=Ap, x3=AH,x4=BC, x5=BP, x6=BH,x7=DC, x8=DP, x9=DH.清华大学出版社155第6节 应用举例v约束条件可表示为：清华大学出版社156第6节 应用举例v目标函数¢目的是使利润最大，即产品价格减去原材料的价格为最大¢产品价格为：50(x1+x2+x3)——产品A 35(x4+x5+x6) —— 产品B 25(x7+x8+x9) —— 产品D¢原材料价格为：65(x1+x4+x7)——原材料C 25(x2+x5+x8) —— 原材料P 35(x3+x6+x9) —— 原材料Hv为了得到初始解，在约束条件中加入松弛变量x10～x16，得到数学模型：清华大学出版社157第6节 应用举例v例11的线性规划模型清华大学出版社158第6节 应用举例v最优解¢用单纯形法计算，经过四次迭代，得最优解为： x1=100,x2=50,x3=50¢这表示：需要用原料C为100kg，P为50kg，H为50kg，构成产品A。

¢即每天只生产产品A为200kg，分别需要用原料C为100kg，P为50kg，H为50kg¢从最终计算表中得到，总利润是z=500元/天清华大学出版社159第6节 应用举例v例例12 生生产与与库存的存的优化安排化安排问题 某工厂生产五种产品(i=1,…,5)，上半年各月对每种产品的最大市场需求量为dij(i=1,…,5;j=1,…,6)已知每件产品的单件售价为Si元，生产每件产品所需要工时为ai，单件成本为Ci元；该工厂上半年各月正常生产工时为rj(j=1,…,6)，各月内允许的最大加班工时为rj′;Ci′为加班单件成本又每月生产的各种产品如当月销售不完，可以库存库存费用为Hi(元/件·月)假设1月初所有产品的库存为零，要求6月底各产品库存量分别为ki件现要求为该工厂制定一个生产计划，在尽可能利用生产能力的条件下，获取最大利润清华大学出版社160第6节 应用举例 解：解：设xij和xij′分别为该工厂第i种产品的第j个月在正常时间和加班时间内的生产量；yij为i种产品在第j月的销售量，wij为第i种产品第j月末的库存量根据题意，可用以下模型描述： (1) 各种产品每月的生产量不能超过允许的生产能力，表示为：清华大学出版社161第6节 应用举例(2) 各种产品每月销售量不超过市场最大需求量 yi j≤dij (i=1,…,5; j=1,…,6)(3) 每月末库存量等于上月末库存量加上该月产量减掉当月的销售量(4) 满足各变量的非负约束 xij ≥0, xij′ ≥0, yij≥0, (i=1,…,5；j=1,…,6)wij≥0 (i=1,…,5；j=1,…,6)清华大学出版社162第6节 应用举例(5) 该工厂上半年总盈利最大可表示为： 清华大学出版社163第6节 应用举例例例1313 连续投资问题连续投资问题 某部门在今后五年内考虑给下列项目投资，已知：v项目A，从第一年到第四年每年年初需要投资，并于次年末回收本利115%；v项目B，第三年初需要投资，到第五年末能回收本利125%，但规定最大投资额不超过4万元；v项目C，第二年初需要投资，到第五年末能回收本利140%，但规定最大投资额不超过3万元；v项目D，五年内每年初可购买公债，于当年末归还，并加利息6%。

v该部门现有资金10万元，问它应如何确定给这些项目每年的投资额，使到第五年末拥有的资金的本利总额为最大?清华大学出版社164第6节 应用举例 解：解： (1) 确定决策变量 这是一个连续投资问题，与时间有关但这里设法用线性规划方法，静态地处理以xiA,xiB,xiC,xiD(i=1,2,…，5)分别表示第i年年初给项目A，B，C，D的投资额，它们都是待定的未知变量根据给定的条件，将变量列于表1-15中表1-15清华大学出版社165第6节 应用举例(2) 投资额应等于手中拥有的资金额 由于项目D每年都可以投资，并且当年末即能回收本息所以该部门每年应把资金全部投出去，手中不应当有剩余的呆滞资金因此¢第一年：该部门年初拥有100000元，所以有x1A+x1D=100000¢第二年：因第一年给项目A的投资要到第二年末才能回收所以该部门在第二年初拥有资金额仅为项目D在第一年回收的本息x1D(1+6%)于是第二年的投资分配是x2A+x2C+x2D=1.06x1D¢第三年初的资金额是从项目A第一年投资及项目D第二年投资中回收的本利总和：x1A(1+15%)及x2D(1+6%)。

于是第三年的资金分配为 x3A+x3B+x3D=1.15x1A+1.06x2D¢第四年：与以上分析相同，可得x4A+x4D=1.15x2A+1.06x3D¢第五年：x5D=1.15x3A+1.06x4D清华大学出版社166第6节 应用举例此外，由于对项目B、C的投资有限额的规定，即：x3B≤40000x2C≤30000(3) 目标函数 问题是要求在第五年末该部门手中拥有的资金额达到最大，与五年末资金有关的变量是：x4A,x3B,x2C,x5D;因此这个目标函数可表示为： max z=1.15x4A+1.40x2C+1.25x3B+1.06x5D清华大学出版社167第6节 应用举例(4) 数学模型 经过以上分析，这个与时间有关的投资问题可以用以下线性规划模型来描述：清华大学出版社168第6节 应用举例(5) 用两阶段单纯形法计算结果得到第一年： x1A=34783元，x1D=65217元第二年： x2A=39130元，x2C=30000元，x2D=0第三年： x3A=0，x3B=40000元，x3D=0第四年： x4A=45000元，x4D=0第五年： x5D=0到第五年末该部门拥有资金总额为143,750元，即盈利43.75%。

清华大学出版社169第6节 应用举例v另一个的投资方案：¢第一年： x1A=71698元，x1D=28300元¢第二年： x2A=0元，x2C=30000元，x2D=0¢第三年： x3A=42453元，x3B=40000元，x3D=0¢第四年： x4A=0元，x4D=0¢第五年： x5D=48820元v还可以有其他的方案 清华大学出版社170有兴趣的读者可以进入以下网站http://www.ifors.ms.unimelb.edu.au/tutorial/提供了网上学习线性规划单纯形法、表上求解和匈牙利法等方法。