线性规划与单纯形法

Chapter1线性规划与单纯形法LinearProgrammingandSimplexAlgorithm运筹学OperationsResearch1.线性规划问题及其数学模型2.线性规划问题的几何意义3.单纯形法4.单纯形法的计算步骤5.单纯形法的进一步讨论6.应用举例

线性规划是运筹学的一个重要分支。自1947年丹捷格〔〕提出了线性规划问题求解的方法——单纯形法之后，线性规划在理论上趋向成熟，在实用中日益广泛与深入。特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛。从解决技术问题的最优化设计到工业、农业、商业、交通运输业、军事、经济方案和管理决策等领域都可以发挥作用。引言线性规划研究的问题：如何合理地利用有限的人力、物力、财力等资源，以便得到最好的经济效果。1.1问题的提出1.1问题的提出例1某工厂在方案期内要安排生产I、II两种产品，生产单位产品所需的设备台时及A、B两种原材料的损耗，如表1.1所示。III设备原材料A原材料B1402048台时16kg12kg表1-1该工厂每生产一件产品Ⅰ可获利2元，每生产一件产品Ⅱ可获利3元，问应如何安排方案使该工厂获利最多？用数学关系式描述这个问题1.1问题的提出1.1问题的提出得到本问题的数学模型为:这就是一个最简单的线性规划模型。

例2

靠近某河流有两个化工厂(见图1-1)，流经第一化工厂的河流流量为每天500万立方米，在两个工厂之间有一条流量为每天200万立方米的支流。

化工厂1每天排放含有某种有害物质的工业污水2万立方米，化工厂2每天排放的工业污水为1.4万立方米。从化工厂1排出的污水流到化工厂2前，有20%可自然净化。根据环保要求，河流中工业污水的含量应不大于0.2%。因此两个工厂都需处理一局部工业污水。化工厂1处理污水的本钱是1000元/万立方米,化工厂2处理污水的本钱是800元/万立方米。问:在满足环保要求的条件下，每厂各应处理多少工业污水，使两个工厂处理工业污水的总费用最小。1.1问题的提出设第一化工厂每天处理工业污水x1万立方米，第二化工厂每天处理工污水x2万立方米。从第一化工厂到第二化工厂之间，河流中工业污水含量不大于0.2%，由此可得近似关系式流经第二化工厂后，河流中的工业污水含量仍要不大于0.2%，这时有近似关系式1.1问题的提出建模型之前的分析和计算1.1问题的提出得到本问题的数学模型为：1.1问题的提出上述两个问题具有的共同特征：每一个线性规划问题都用一组决策变量(x1,x2,…,xn)表示某一方案，这组决策变量的值代表一个具体方案。一般这些变量的取值是非负且连续的；都有关于各种资源和资源使用情况的技术数据，创造新价值的数据；存在可以量化的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示;都有一个到达某一目标的要求，可用决策变量的线性函数(称为目标函数)来表示。按问题的要求不同，要求目标函数实现最大化或最小化。线性规划模型的一般形式1.1问题的提出决策变量及各类系数之间的对应关系1.1问题的提出1.2图解法例1是一个二维线性规划问题，因而可用作图法直观地进行求解。1.2图解法目标值在〔4，2〕点，到达最大值141.2图解法〔1〕无穷多最优解(多重最优解)，见图1-4。〔2〕无界解，见图1-5-1。〔3〕无可行解，见图1-5-2。通过图解法，可观察到线性规划的解可能出现的几种情况：1.2图解法目标函数maxz=2x1+4x2

图1-4无穷多最优解〔多重最优解〕1.2图解法图1-5-1无界解1.2图解法当存在相互矛盾的约束条件时，线性规划问题的可行域为空集。例如，如果在例1的数学模型中增加一个约束条件:那么该问题的可行域即为空集，即无可行解.无可行解的情形1.2图解法增加的约束条件图1-5-2不存在可行域1.2图解法——在边界，而且是在某个顶点上获得思考：1〕线性规划的可行域是一个什么形状？2〕最优解在什么位置获得？——多边形，而且是“凸”的多边形结论：1.2图解法问题：性质2有何重要意义？1.3线性规划问题的标准形式

1.3线性规划问题的标准形式用向量形式表示的标准形式线性规划1.3线性规划问题的标准形式

用矩阵形式表示的标准形式线性规划1.3线性规划问题的标准形式

这时只需将目标函数最小化变换为求目标函数最大化，。（1）若要求目标函数实现极小化，即必须注意，尽管以上两个问题的最优解相同，但它们最优解的目标函数值却相差一个符号。于是得到即令如何将一般线性规划转化为标准形式的线性规划1.3线性规划问题的标准形式

引进一个松弛变量，把原不等式约束用两个约束来等价地替换设约束条件为〔2〕约束方程为不等式有两种情况：一种是约束方程为“≤〞不等式，那么可在“≤〞不等式的左端参加非负松弛变量，把原“≤〞不等式变为等式。1.3线性规划问题的标准形式

另一种是约束方程为“≥〞不等式，那么可在“≥〞不等式的左端减去一个非负剩余变量〔也可称松弛变量〕，把原“≥〞不等式变为等式。引进一个剩余变量，把原不等式约束用两个约束来等价地替换设约束条件为1.3线性规划问题的标准形式

〔4〕在标准形式中，要求约束条件的右端项bi>0，否那么等式两端乘以-1。下面举例说明。可以令，其中。即用两个非负变量之差来表示一个无符号限制的变量，当然的符号取决于和的相对大小。（3）若存在取值无约束的变量1.3线性规划问题的标准形式

1.3线性规划问题的标准形式

例3将例1的数学模型化为标准形式的线性规划。例1的数学模型在参加了松驰变量后变为例4将下述线性规划问题化为标准形式线性规划(1)用x4−x5替换x3，其中x4，x5≥0；(2)在第一个约束不等式左端参加松弛变量x6；(3)在第二个约束不等式左端减去剩余变量x7；(4)令z′=−z，将求minz改为求maxz′即可得到该问题的标准型。1.3线性规划问题的标准形式

例4例4的标准型1.3线性规划问题的标准形式

1.4线性规划问题解的概念可行解满足约束条件（1-5）、（1-6）式的解称为线性规划问题的可行解，其中使目标函数达到最大值的可行解称为最优解。考虑LP的标准型称为基向量，与基向量相对应的变量称为基变量，否则称为非基变量。设A是约束方程组的维系数矩阵，其秩为m。B是A中m阶非奇异子矩阵(|B|≠0)，那么称B是线性规划问题的一个基，这就是说，矩阵B是由A中m个线性无关的列向量组成。为不失一般性,可设B是A中的前m列，即2基1.4线性规划问题解的概念注：〔1〕对应于给定的基B，基解是唯一的。〔2〕基解中非基变量取零值，非零分量的数目不超过m。〔3〕基解一定满足等式约束，但不一定满足非负约束。称为对应于基B的基解。令所有非基变量，得到因B可逆，该方程有唯一解。把约束方程〔1-5〕式写成1.4线性规划问题解的概念例在下述线性规划问题中列出全部的基并确定相应的基解。解：将该线性规划问题化为标准形：只要从A的列向量中找出3个线性无关的列向量就组成该线性规划问题的一个基。1.4线性规划问题解的概念取A的第一、二、三列组成子矩阵易见，故B1是该线性规划问题的一个基。令非基变量，则约束方程变为基变量为，非基变量。令非基变量为零，求解线性方程组，就可找出全部基解。解得这里X〔1〕不满足非负约束，故不是可行解。1.4线性规划问题解的概念取A的第一、四、五列得到基，相应地基解取A的第一、三、五列得到基，相应地基解类似地取A的第一、二、四列得到基，相应地基解取A的第一、二、五列得到基，相应地基解1.4线性规划问题解的概念对于A的第一、三、四列组成的矩阵易见，故不能作成一组基。取A的第二、三、四列得到基相应地基解取A的第二、四、五列得到基相应地基解取A的第三、四、五列得到基，相应地基解同理，也不能作成一组基。1.4线性规划问题解的概念〔1〕基解的数目最多是个。〔2〕基解中非零分量的个数小于m个时，该基解是退化解。3基可行解满足非负约束条件的基解称为基可行解。以下讨论时，假设不出现退化的情况，即基解中非零分量恰为m个。说明：4可行基对应于基可行解的基称为可行基。1.4线性规划问题解的概念几何上，图中A、B、C、D、E、F、G、H对应X〔i〕〔i=1，2，…,8〕1.4线性规划问题解的概念4x1=16x1x2x1+2x2=84x2=12HEGBADFC直观上，可行解即可行域中的点，基解是约束直线的交点，基可行解即可行域的顶点。它们之间的关系可以用图1-6表示。基解非可行解可行解基可行解图1-61.4线性规划问题解的概念第2节线性规划问题的几何意义

2.1根本概念设K是n维欧氏空间的一个点集，若任意两点的连线上的所有点；则称K为凸集。注：（1）就是以X（1）、X（2）为端点的线段方程，当时，；当时，（2）直观上，凸集没有凹入部分，其内部没有空洞。1凸集试判断以下图形是否凸集：2.1根本概念设K是凸集，，若X不能用K中两个不同的点的凸组合表示为则称X是K的一个顶点或极点。设

是n维欧氏空间En中的k个点。若存在且使则称X为的凸组合。2凸组合3顶点注：X是凸集K的顶点即X不可能是K中某一线段的内点，而只能是K中某一线段的端点。2.2几个定理定理1若线性规划问题存在可行域，则其可行域是凸集。设，则有

令X为X1，X2连线上的任意一点，即把它代入约束条件，得到显然。由此可见，X是凸集。证明：只要证明D中任意两点连线上的点必然在D内即可。引理1线性规划问题的可行解为基可行解的充要条件是X的正分量所对应的系数列向量是线性独立的。证明：不失一般性，假设可行解X的前k个分量为正，即。（1）必要性由基可行解的定义可知。（2）充分性若向量线性独立，则必有；当时，它们恰好构成一个基，从而为相应的基可行解。当k<m时，则一定可以从其余的列向量中取出m-k个与构成最大的线性独立向量组，其对应的解恰为X，根据定义它是基可行解。2.2几个定理2.2几个定理证明：不失一般性，假设可行解X的前m个分量为正，即故(1)若X不是基可行解，则它一定不是可行域的顶点。根据引理1，若X不是基可行解，则其正分量所对应的系数列向量线性相关，即存在一组不全为零的数使得定理2线性规划问题的基可行解X对应于可行域D的顶点。2.2几个定理用一个的数乘（1-9）式再分别和（1-8）式相加和相减，这样得到现取由X（1）、X（2）可以得到

即X是X（1）、X（2）连线的中点。另一方面，当充分小时，可保证。即X（1）、X（2）是可行解。这证明了X不是可行域D的顶点。2.2几个定理（2）若X不是可行域D的顶点，则它一定不是基可行解。因为X不是可行域D的顶点，故在可行域D中可找到不同的点使当j>m时，有，由于X（1）、X（2）是可行域的两点，应满足和将两式相减，即得因，所以上式系数不全为零，故向量组线性相关，即X不是基可行解。2.2几个定理例5设X是三角形中任意一点，X〔1〕，X〔2〕和X〔3〕是三角形的三个顶点，试用三个顶点的坐标表示X〔见以下图〕。引理2若K是有界凸集，则任何一点可表示为K的顶点的凸组合。图1-82.2几个定理解：任选一顶点X（2），做一条连线XX(2)；并延长交于X(1)、X（3）连线上一点X′。因X′是X(1)、X（3）连线上一点，故可用X(1)、X（3）的线性组合表示为又因X是X′与X（2）连线上的一个点，故将X′的表达式代入上式得到令即可。2.2几个定理定理3假设可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点上到达最优。证明：设是可行域的顶点，若X(0)不是顶点，且目标函数在X(0)处达到最优。因X(0)不是顶点，所以它可以用D的顶点线性表示为

设X(m)是所有顶点中目标函数值最大的，则X(m)一定也是最优解。事实上，有故，X(m)也是最优解。2.2几个定理定理2刻划了可行域的顶点与基可行解的对应关系，顶点是基可行解，反之，根本可行解一定是顶点，但它们并非一一对应，有可能两个或几个基可行解对应于同一顶点〔退化基可行解时〕。定理3描述了最优解在域中的位置，假设最优解唯一，那么最优解只能在某一顶点上到达，假设具有多重最优解，那么最优解是某些顶点的凸组合，从而最优解是可行域的顶点或界点，不可能是可行域的内点。假设线性规划的可行解集非空且有界，那么一定有最优解；假设可行解集无界，那么线性规划可能有最优解，也可能没有最优解。丹捷格教授在一次演说中，形象而风趣地说明了单纯形解法的奇效：设给70个人分配70项任务，每人一项。如果每人完成各项任务所需要付出的代价（时间、工资）都知道，要寻求代价最小的方案。所有的可行方案共有70！种。70！比还要大。如果用穷举法，逐个来比较的话，即使用个地球或个太阳的容量来装计算机，这些计算机从150亿年前开始，全部投入计算，大约要算到太阳熄灭才有答案。而用单纯形法软件，几秒钟就可以给出答案。单纯形法是求解线性规划的主要算法，1947年由美国斯坦福大学教授丹捷格〔G.B.Dantzig〕提出。第3节单纯形法第3节单纯形法单纯形法(SimplexAlgorithm)先求出一个初始基可行解并判断它是否最优，假设不是最优，再换一个基可行解并判断，直到得出最优解或无最优解。它是一种逐步逼近最优解的迭代方法。oABCDEz=omaxz优跨越式寻找最优解3.1举例例6试以例1来讨论如何用单纯形法求解。解：本例的标准型为：约束条件(1-12)式的系数矩阵为可看到x3,x4,x5的系数构成的列向量3.1举例P3

,P4,P5是线性独立的，这些向量构成一个基B。对应于B的变量x3,x4,x5为基变量.从(1-12)式中可以得到〔1-13〕3.1举例将(1-13)式代入目标函数(1-11)：得到当令非基变量x1=x2=0，便得到z=0。这时得到一个基可行解X(0)

X(0)=(0,0,8,16,12)T

本基可行解的经济含义是：工厂没有安排生产产品Ⅰ、Ⅱ，资源都没有被利用，所以工厂的利润为z=0。3.1举例从分析目标函数的表达式(1-14)可以看到：

非基变量x1,x2(即没有安排生产产品Ⅰ，Ⅱ)的系数都是正数，因此将非基变量变换为基变量，目标函数的值就可能增大。从经济意义上讲，安排生产产品Ⅰ或Ⅱ，就可以使工厂的利润指标增加。所以只要在目标函数(1-14)的表达式中还存在有正系数的非基变量，这表示目标函数值还有增加的可能，就需要将非基变量与基变量进行对换。3.1举例一般选择正系数最大的那个非基变量x2为换入变量，将它换到基变量中，同时还要确定基变量中哪一个换出来成为非基变量。分析(1-13)式，当将x2定为换入变量后，必须从x3,x4,x5中确定一个换出变量，并保证其余的变量仍然非负，即x3,x4,x5≥0。3.1举例当x1=0时，由(1-13)式得到从(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件。3.1举例为了求得以x3,x4,x2为基变量的一个基可行解和进一步分析问题，需将(1-13)中x2的位置与x5的位置对换，得到3.1举例将(1-16)式中x2的系数列向量变换为单位列向量。其运算步骤是：③′=③/4；①′=①－2×③′;②′=②,并将结果仍按原顺序排列有：高斯消去法3.1举例3.1举例再将(1-17)式代入目标函数(1-11)式得到令非基变量x1=x5=0，得到目标值z=9和另一基可行解X(1)=(0,3,2,16,0)T从目标函数的表达式(1-18)可看到，非基变量x1的系数是正的，说明目标函数值还可以增大，即X(1)还不是最优解。确定x1进基，此时非基变量x5=0。3.1举例当x1=2时，基变量x3=0，确定x3退基。新的基变量x1,x4,x2，非基变量x3,x5，对（1-17）式作初等变换得由和x3，x4，x2非负可知，x1至多增加2个单位。3.1举例令非基变量x3=x5=0，得到新的基可行解X(2)=(2,3,0,8,0)T把目标函数用非基变量x3，x5表示确定x5进基，x3=0。由及x1，x4，x2非负，知x5至多增加4个单位，此时x4=0。x4退基，新的基变量x1，x5，x2。3.1举例约束对应的增广矩阵将基变量前的系数矩阵(P1,P5,P2)经初等行变换化为单位阵，只需将化为单位向量。为了求出新的基可行解，也可考虑对约束对应的增广矩阵作初等行变换。从上面的增广阵可以看到基可行解X(3)=(4,2,0,0,4)T，目标函数用非基变量表示得到

所有非基变量的系数都是负数，所以目标函数达到最大，X(3)是最优解。即当产品Ⅰ生产4件，产品Ⅱ生产2件时，工厂可以得到最大利润。新的增广阵3.1举例小结与图解法比较：单纯形法从初始基可行解X〔0〕开始迭代，依次得到X〔1〕，X〔2〕，X〔3〕。这相当于图中的目标函数平移时，从O点开始，首先碰到Q4，然后碰到Q3，最后达到Q2。x1x2Q2(4,2)Q3(2,3)O(0,0)Q4(0,3)X(0)=(0,0,8,16,12)TX(1)=(0,3,2,16,0)TX(2)=(2,3,0,8,0)TX(3)=(4,2,0,0,4)T3.2初始基可行解确实定由于基可行解是由一个可行基决定的。因此，确定一个初始基可行解X〔0〕相当于确定一个初始可行基B0。方法：假设A中含I，那么B0=I；假设A中不含I，那么可用人工变量法构造一个I.问题：假设B0=I，那么X〔0〕=？3.3最优性检验与解的判别设是LP的一个基，为相应的基可行解。将约束写成非基变量表示基变量的形式，不妨设思路：对一个给定的基可行解，把目标函数用非基变量表示，非基变量前的系数称为检验数。当所有非基变量的检验数均小于等于零时，当前解即最优解。3.3最优性检验与解的判别将（1-24）式代入目标函数令则3.3最优性检验与解的判别1最优解的判别定理若所有非基变量的检验数，，则X（0）是最优解。2无穷多最优解判别定理若所有非基变量的检验数，，又存在某个非基变量的检验数，则线性规划问题有无穷多最优解。证将非基变量xm+k换入基变量中得到新的基可行解X〔1〕。X〔1〕也是最优解。从而X〔0〕，X〔1〕连线上的所有点都是最优解。3.3最优性检验与解的判别3无界解判别定理若，并且，，那么该线性规划问题具有无界解。证明思路：由及xm+k每增加一个单位,目标函数值增加选择xm+k进基，因，所以对任意的，

都是可行解。令，则。其它情形以上讨论都是针对标准型的，即求目标函数极大化时的情况。当要求目标函数极小化时，一种情况是将其化为标准型。如果不化为标准型，只需在上述1，2点中把σj≤0改为σj≥0，第3点中将σm+k＞0改写为σm+k＜0即可。3.3最优性检验与解的判别假设初始基可行解X(0)不是最优解及不能判别无界时，需要找一个新的基可行解。具体做法是从原可行基中换一个列向量(当然要保证线性独立)，得到一个新的可行基，称为基变换。为了换基，先要确定换入变量，再确定换出变量，让它们相应的系数列向量进行对换，就得到一个新的基可行解。3.4基变换3.4基变换为了使目标函数增加得快，从直观上一般选σj>0中的最大者，即对应的将xk进基。也可任选或按最小号码选。由可知，若存在σj>0，xj增加则目标函数还可能增大，这时要将某个检验数大于零的非基变量换到基变量中去，即令该变量的取值大于零。1换入变量确实定不妨设xk进基，则其余的非基变量仍然为零。由对，当xk取值超过时,将破坏xi的非负性,故在新的基可行解中xk的值不超过3.4基变换2换出变量确实定3.4基变换另一方面，xk取值越大，目标函数的增加量就越多。故取。这时原基变量，将从基变量中换出。处在变量转换的交叉点上，称之为主元，它所在的列称为主元列，它所在的行称为主元行。新的可行解问题：X〔1〕是不是基可行解？判别方法：由引理1，只需要考虑X〔1〕中的正分量所对应的系数列向量是否线性无关。3.4基变换X（1）中正分量所对应的系数列向量设注意到将Pk的表达式代入（*）得到

因线性无关，故，

这表明，从而线性无关。即X（1）是基可行解。3.5迭代〔旋转运算〕不妨假定xk进基，xl退基。xk,xl的系数列向量分别为：原基可行解对应的增广矩阵：x1

…xl…xmxm+1

…xk…xnb为了求出新的基可行解，需要把当前基变量的系数矩阵经初等行变换化为单位阵，即把Pk化为单位向量。作以下变换：(1)第l行除以主元alk;(2)第i（i≠l）行的元素减去主元行的倍。3.5迭代〔旋转运算〕原基可行解对应的增广矩阵：x1

…xl…xmxm+1

…xk…xnb3.5迭代〔旋转运算〕经过初等变换后的增广矩阵：x1

…xl…xmxm+1

…xk…xnb从而得到新的基可行解3.5迭代〔旋转运算〕以为基变量，可得基可行解。用x2替换x5，将的系数矩阵变换为单位阵，经变换为：例7试用上述方法计算例6的两个基变换。解：将例6的约束方程组的系数矩阵写成增广矩阵新的基可行解：第4节单纯形法的计算步骤单纯形法的表格形式是把用单纯形法求基可行解、检验其最优性、迭代等步骤都用表格的方式给出，其表格的形式很像增广矩阵，而计算方法较多使用矩阵的初等行变换。将约束与目标组成n+1个变量，m+1个方程的方程组。为了便于迭代运算，可将上述方程组写成增广矩阵形式：第4节单纯形法的计算步骤4.1单纯形表假设将z看作不参与基变换的基变量，它与x1,x2,…,xm的系数构成一个基，这时可采用行初等变换将c1,c2,…,cm变换为零，使其对应的系数矩阵为单位矩阵。得到4.1单纯形表cj→c1…cmcm+1…cnθiCBXBbx1…xmxm+1…xn

c1c2…cmx1x2…xmb1b2…bm1…0a1,m+1…a1n0…0a2,m+1…a2n………………0…1am,m+1…amnθ1θ2…θm

σj0…0σm+1

…σn根据上述增广矩阵设计计算表，见表1-2.4.1单纯形表表1-2称为初始单纯形表，每迭代一步构造一个新单纯形表。表1-2的说明XB列中填入基变量，这里是x1，x2,…，xm；CB列中填入基变量的价值系数，这里是c1,c2,…,cm；它们是与基变量相对应的；b列中填入约束方程组右端的常数；cj行中填入变量的价值系数c1,c2,…,cn；θi列的数字是在确定换入变量后，按θ规则计算后填入；最后一行称为检验数行，对应各非基变量xj的检验数是4.2计算步骤(1)找出初始可行基，确定初始基可行解，建立初始单纯形表。(2)检验各非基变量xj的检验数，假设所有σj≤0，j=m+1,…,n,那么已得到最优解，停止计算。否那么转入下一步。(3)在σj>0，j=m+1,…,n中，假设有某个σk对应xk的系数列向量Pk≤0，那么最优解无界，停止计算。否那么，转入下一步。(4)根据max{σj>0}=σk，确定xk为换入变量，按θ规那么计算θ=min{bi/aik|aik>0}=bl/alk可确定xl为换出变量，转入下一步。4.2计算步骤现用例1的标准型来说明上述计算步骤。(5)以alk

为主元素进行迭代，把xk所对应的列向量Pk变为单位向量。将XB列中的xl换为xk，得到新的单纯形表。重复（2）～（5）,直到终止。4.2计算步骤例1的标准型：(1)取松弛变量x3,x4,x5为基变量，它对应的单位矩阵为基。这就得到初始基可行解X(0)=(0,0,8,16,12)T。将有关数字填入表中，得到初始单纯形表，见表1-3。表中左上角的cj是表示目标函数中各变量的价值系数。在CB列填入初始基变量的价值系数，它们都为零。cj→23000θCBXBbx1x2x3x4x50x38121008/2=40x41640010-0x5120[4]00112/4=3cj-zj

23000表1-3计算非基变量的检验数各非基变量的检验数为σ1=c1−z1=2−(0×1+0×4+0×0)=2σ2=c2−z2=3−(0×2+0×0+0×4)=34.2计算步骤4.2计算步骤它所在行对应的x5为换出变量，x2所在列和x5所在行的交叉处[4]称为主元素或枢元素(pivotelement)。(2)因检验数都大于零，且P1，P2有正分量存在，转入下一步；(3)max(σ1,σ2)=max(2,3)=3，对应的变量x2为换入变量，计算θ(4)以[4]为主元素进行旋转运算或迭代运算，即初等行变换，使P2变换为(0,0,1)T,在XB列中将x2替换x5,于是得到新表1-4。换人变量换出变量主元素cj→23000θCBXBbx1x2x3x4x50x32[1]010-1/220x4164001043x2301001/4-

cj-zj2000-3/44.2计算步骤表1-4(5)检查表1-4的所有cj−zj,这时有c1−z1=2；说明x1应为换入变量。重复(2)～(4)的计算步骤，得表1-5。换人变量换出变量因为还存在检验数>0，继续进行迭代。cj→23000CBXBbx1x2x3x4x5θ2x121010-1/2-0x4800-41[2]43x2301001/412cj-zj

00-201/4主元素4.2计算步骤表1-5

(6)表1-6最后一行的所有检验数都已为负或零.这表示目标函数值已不可能再增大，于是得到最优解.cj→23000θCBXBbx1x2x3X4x52x141011/400x5400-21/213x22011/2-1/80cj-zj00-3/2-1/804.2计算步骤表1-6X*=X(3)=(4,2,0,0,4)T

目标函数的最大值z*=14设线性规划问题的约束条件.其中没有可作为初始基的单位矩阵，则分别给每个约束方程加入人工变量xn+1,…,xn+m，得到第5节单纯形法的进一步讨论第5节单纯形法的进一步讨论以xn+1,…,xn+m为基变量，便可得到一个m×m单位矩阵。令非基变x1,…,xn为零，便可得到一初始基可行解X(0)=(0,0,…,0,b1,b2,…,bm)T注：人工变量与松弛变量和剩余变量不同。松弛变量、剩余变量可以取零值，也可以取正值，而人工变量只能取零值。一旦人工变量取正值，那么有人工变量的约束方程和原始的约束方程就不等价了，这样所求得的解就不是原线性规划的解。第5节单纯形法的进一步讨论这就要求经过基变换将人工变量从基变量中逐个替换出来。基变量中不再含有非零的人工变量，这表示原问题有解。假设在最终表中当所有cj−zj≤0，而在其中还有某个非零人工变量，这表示原问题无可行解。如何求解含有人工变量的线性规划问题?第5节单纯形法的进一步讨论5.1人工变量法1大M法思路：为了要求人工变量为零，规定人工变量在目标函数中的系数为－M.这样只要人工变量不等于零，目标函数就不可能实现极大化。为了使目标函数实现极大就必须把人工变量从基变量中换出。如果直到最后人工变量仍不能从基变量中换出，也就是说人工变量仍不为零，那么该线性规划问题无可行解。5.1人工变量法例8用大M法求解线性规划问题解在上述问题的约束条件中参加松弛变量x4，剩余变量x5，人工变量x6，x7，得到cj→-31100MMθiCBXBbx1x2x3x4x5x6x70MMx4x6x711311-4-2-21012[1]1000-10010001113/21cj-zj-3+6M1-M1-3M0M005.1人工变量法因本例的目标是要求min，所以用所有cj−zj≥0来判别目标函数是否实现了最小化。用单纯形法进行计算时，见表1-6。5.1人工变量法cj→-31100MMθiCBXBbx1x2x3x4x5x6x70M1x4x6x3101130-2-2[1]00011000-10010-1-211

cj-zj-11-M00M03M-1011x4x2x31211[3]0-2010001100-2-10210-5-214cj-zj-10001M-1M+1-311x1x2x34191000100011/302/3-2/3-1-4/32/314/3-5/3-2-7/3cj-zj0001/31/3M-1/3M-2/35.1人工变量法两阶段法两阶段法是处理人工变量的另一种方法，这种方法是将参加人工变量后的线性规划分两阶段求解。第一阶段：不考虑原问题是否存在基可行解；给原线性规划问题参加人工变量，并构造仅含人工变量的目标函数和要求实现最小化。如5.1人工变量法5.1人工变量法然后用单纯形法求解上述模型，若，这说明原问题存在基可行解，可以进行第二阶段计算。否则原问题无可行解，应停止计算。第二阶段：将第一阶段计算得到的最终表，除去人工变量。将目标函数行的系数，换成原问题的目标函数系数，作为第二阶段计算的初始表。注：第一阶段构造的线性规划问题约束条件与原线性规划一样，而目标函数是求人工变量之和的最小值。如果此值为零，即说明存在一个可行解，使得所有的人工变量都为零。如果此值不为零，那么不存在使所有人工变量都为零的可行解，原问题无可行解。5.1人工变量法5.1人工变量法例9

试用两阶段法求解如下线性规划问题：解:先在上述线性规划问题的约束方程中参加人工变量，给出第一阶段的数学模型为：5.1人工变量法5.1人工变量法第一阶段用单纯形法求解，见表1-7。求得的结果是，最优解是x1=0,x2=1,x3=1,x4=12,x5=x6=x7=0因为人工变量x6=x7=0，所以(0，1，1，12，0)T是原线性规划问题的基可行解。于是可以进行第二阶段运算。将第一阶段的最终表中的人工变量取消填入原问题的目标函数系数，进行第二阶段计算，见表1-8。cj→0000011θiCBXBbx1x2x3x4x5x6x7011x4x6x711311-4-2-21012[1]1000-10010001113/21cj-zj6-1-30100010x4x6x3101130-2-2[1]00011000-10010-1-21-1-cj-zj0-100103000x4x2x3121130-2010001100-2-10210-5-21cj-zj00000115.1人工变量法表1-8Cj-31100θi

CBXBbx1x2x3x4x5011x4x2x31211[3]0-2010001100-2-104--cj-zj-10001-311x1x2x34191000100011/302/3-2/3-1-4/3-cj-zj0001/31/35.2退化在单纯形法计算中用θ规那么确定换出变量时，有时存在两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于零，这就出现了退化解。这时换出变量xl=0，迭代后目标函数值不变。这时不同基表示为同一顶点。有人构造了一个特例，当出现退化时，进行屡次迭代，而基从B1,B2，…又返回到B1，即出现计算过程的循环，便永远达不到最优解。5.2退化尽管实际计算过程中循环现象极少出现，但还是有可能发生的。如何解决这问题?先后有人提出了“摄动法〞，“字典序法〞。1974年Bland提出一种防止循环的Bland规那么：(1)选取cj−zj＞0中下标最小的非基变量xk为换入变量，即k=min(j｜cj−zj＞0)(2)当按θ规那么计算存在两个和两个以上最小比值时，选取下标最小的基变量为换出变量。5.2退化第6节应用举例一般讲，一个经济、管理问题凡满足以下条件时，才能建立线性规划的模型。〔1〕要求解问题的目标函数能用数值指标来反映，且为线性函数；〔2〕存在着多种方案，及有关数据；〔3〕要求到达的目标是在一定约束条件下实现的，这些约束条件可用线性等式或不等式来描述。例10合理利用线材问题。现要做100套钢架，每套用长2.9m，2.1m和1.5m的原钢各一根。原料长7.4m,问应如何下料，使用的原材料最省。第6节应用举例第6节应用举例解最简单的做法，在每根原材料上截取2.9m,2.1m和1.5m的原钢各一根组成一套，每根原材料剩下料头0.9m。为了做100套钢架，需用原材料100根，有90m料头。假设改用套裁，这可以节约原材料。下面有几种套裁方案，都可以采用。 下料根数长度(m)方案ⅠⅡⅢⅣⅤ2.92.51.510321221213合计料头7.407.30.17.20.27.10.36.60.8第6节应用举例第6节应用举例为了得到100套钢架，需要混合使用各种下料方案。设x1，x2，x3，x4，x5分别为上面5种方案下料的原材料根数。可列出以下数学模型：minz=0x1+0.1x2+0.2x3+0.3x4+0.8x5

s.t.x1+2x2+x4≥1002x3+2x4+x5≥1003x1+x2+2x3+3x5≥100

x1，x2，x3，x4，x5≥0解：如以AC表示产品A中C的成分，AP表示产品A中P的成分，依次类推。某工厂要用三种原材料C、P、H混合调配出三种不同规格的产品A、B、D。产品的规格要求，产品单价，每天供给的原料数量及原料单价，分别见表1-13和表1-14。问该厂如何安排生产，使利润收入最大？产品名称规格要求单价（元/kg）A原材料C不少于50%原材料P不超过25%50B原材料C不少于25%原材料P不超过50%35D不限25表1-13例11配料问题根据表1-13有：这里AC+AP+AH=A；BC+BP+BH=B(1-40)将(1-40)逐个代入(1-39)并整理得到例11配料问题表1-14说明这些原材料供给数量的限额。参加到产品A、B、D的原材料C总量每天不超过100kg，P的总量不超过100kg，H总量不超过60kg。表1-14原材料名称每天最多供应量（kg）单价(元/kg)C10065P10025H6035例11配料问题由此得约束条件AC+BC+DC≤100AP+BP+DP≤100AH+BH+DH≤60在约束条件中共有9个变量，为计算和表达方便，分别用x1,…,x9表示。令x1=Ac,x2=Ap,x3=AH,x4=BC,x5=BP,x6=BH,x7=DC,x8=DP,x9=DH.例11配料问题约束条件可表示为：例11配料问题目标函数目的是使利润最大，即产品价格减去原材料的价格为最大。产品价格为：50(x1+x2+x3)——产品A35(x4+x5+x6)——产品B25(x7+x8+x9)——