线性规划建模课件

线性规划方法线性规划（LinearProgramming,缩写为LP）是运筹学的重要分支之一，在实际中应用得较广泛，其方法也较成熟，借助计算机，使得计算更方便，应用领域更广泛和深入。线性规划通常研究资源的最优利用、设备最佳运行等问题。例如，当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标；企业在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多、利润最大）等等。一、应用模型举例生产计划问题

2x1

+x2

8s.t.x1

3x2

4

x1，x2

0

maxf=5x1+2x2

求最大利润三种材料量的限制生产量非负运输问题解：设A1,A2调运到三个粮站的大米分别为x1，x2，

x3，

x4，

x5，

x6吨。题设量可总到下表：结合存量限制和需量限制得数学模型：m个产地A1,…,Am联合供应n个销地B1,…,Bn,各产地至各销地单位运价(单位:元/吨)为cij，问如何调运使总运费最少?一般运输问题总运价产量限制需量限制运量非负

二、线性规划的数学模型

以上例子表明，线性规划问题具有以下特征：①每一个问题都用一组未知变量（x1，x2，…，xn）表示某一规划方案，其一组定值代表一个具体的方案，而且通常要求这些未知变量的取值是非负的。②每一个问题的组成部分：一是目标函数，按照研究问题的不同，常常要求目标函数取最大或最小值；二是约束条件，它定义了一种求解范围，使问题的解必须在这一范围之内。③每一个问题的目标函数和约束条件都是线性的。即线性规划的数学模型由决策变量

Decisionvariables

目标函数Objectivefunction约束条件Constraints构成。称为三个要素。其特征是：1．解决问题的目标函数是多个决策变量的线性函数，

通常是求最大值或最小值；2．解决问题的约束条件是一组多个决策变量的线性不

等式或等式。

由此可以抽象出线性规划问题的数学模型。

一般地，假设线性规划数学模型中，有m个约束，有n个决策变量xj,j=1,2…,n，目标函数的变量系数用cj表示,cj称为价值系数。约束条件的变量系数用aij表示，aij称为工艺系数。约束条件右端的常数用bi表示，bi称为资源限量。则线性规划数学模型的一般表达式可写成为了书写方便，上式也可写成：

采用矩阵形式可描述为：在约束条件

AX≤(≥，＝)bX≥0下，求未知向量，使得Z=CX→max(min)

其中应用市场营销(广告预算和媒介选择，竞争性定价，新产品开发，制定销售计划)生产计划制定(合理下料，配料，“生产计划、库存、劳力综合”)库存管理(合理物资库存量，停车场大小，设备容量)运输问题财政、会计(预算，贷款，成本分析，投资，证券管理)人事(人员分配，人才评价，工资和奖金的确定)设备管理(维修计划，设备更新)城市管理(供水，污水管理，服务系统设计、运用)小结：建立线性规划数学模型

建立数学模型是学习线性规划的第一步也是关键的一步。建立正确的数学模型要掌握3个要素：研究的问题是求什么，即设置决策变量；问题要达到的目标是什么，即建立目标函数，目标函数一定是决策变量的线性函数并且求最大值或求最小值；限制达到目标的条件是什么，即建立约束条件。三、线性规划问题的基本理论

（一）线性规划的标准形式

在讨论与计算时，需要将线性规划问题的数学模型转化为标准形式，即1．目标函数求最大值（或求最小值）2．约束条件都为等式方程3．变量xj非负4．常数bi非负max(或min)Z=c1x1+c2x2+…+cnxn或写成下列形式：

或用矩阵形式通常x记为：

称Ａ为约束方程的系数矩阵，m是约束方程的个数，n是决策变量的个数，一般情况m≤n，且r(Ａ)＝m。其中:

任何一个线性规划问题都可以化为标准形式，我们的求解方法都是针对标准形式的。如果给定的LP问题是极小化问题,即可化为极大化问题约束条件不变,其最优解是一致的,但目标函数值的符号相反.则:结论:如果问题是求目标函数的最小值,则化为求–f的最大值;1.关于目标函数2.关于约束条件(1)如果给定的LP有约束不等式注意:新引入的变量在目标函数中的系数为0.(2)如果给定的LP有约束不等式3.关于变量

在标准形式中,所有的变量都有非负限制,如果某些变量没有非负限制,则称这些变量为自由的.两种处理办法:【例1】将下列线性规划化为标准形【解】（１）因为x3无符号要求，即x3取正值也可取负值，标准型中要求变量非负，所以令(2)第一个约束条件是≤号，在≤左端加入松驰变量(slackvariable)x4，x4≥0,化为等式；(4)第三个约束条件是≤号且常数项为负数，因此在≤左边加入松驰变量x6，x6≥0，同时两边乘以－1。（5）目标函数是最小值，为了化为求最大值，令Z′=－Z,得到maxZ′=－Z，即当Z达到最小值时Z′达到最大值，反之亦然。(3)第二个约束条件是≥号，在≥左端减去剩余变量(Surplusvariable)x5，x5≥0。也称松驰变量综合起来得到下列标准型

当某个变量xj≤0时,令x/j=－xj

。当某个约束是绝对值不等式时，将绝对值不等式化为两个不等式，再化为等式，例如约束将其化为两个不等式再加入松驰变量化为等式。

(二)线性规划的解

若x*满足约束条件，则称之为LP问题的可行解。所有可行解的集合称为可行域。使目标函数达到最优值的可行解称为最优解。对给定的LP问题，若存在最优解，则称该LP问题有解，否则称LP问题无解。线性规划的标准形几个概念（Ⅰ）用图解法求解线性规划问题图解法的步骤：1.求可行解集合。分别求出满足每个约束包括变量非负要求的区域，其交集就是可行解集合，或称为可行域；2.绘制目标函数图形。先过原点作一条矢量指向点（c1,c2)，矢量的方向就是目标函数增加的方向，称为梯度方向，再作一条与矢量垂直的直线，这条直线就是目标函数图形；3.求最优解。依据目标函数求最大或最小移动目标函数直线，直线与可行域相交的点对应的坐标就是最优解。一般地，将目标函数直线放在可行域中求最大值时直线沿着矢量方向移动求最小值时沿着矢量的反方向移动x1x2O1020304010203040(3,4)(15,10)最优解X=(15,10)最优值Z=85例3246x1x2246最优解X=(3,1)最优值Z=5(3,1)minZ=x1+2x2例4(1,2)246x1x2246X（2）＝（3,1）X（1）＝（1,3）(5,5)minZ=5x1+5x2例5有无穷多个最优解即具有多重解,通解为0≤α≤1

当α=0.5时Ｘ=(x1,x2)=0.5(1,3)+0.5(3,1)=(2,2)246x1x2246(1,2)无界解(无最优解)maxZ=x1+2x2例6x1x2O10203040102030405050无可行解即无最优解maxZ=10x1+4x2例7由以上例题可知，线性规划的解有4种形式：1.有唯一最优解(例3、例4)2.有多重解(例5)3.有无界解(例6)4.无可行解(例7)1、2情形为有最优解3、4情形为无最优解从上述几何直观还可看出：⑴线性规划问题的任意两个可行解联线上的点都是可行解；⑵线性规划问题的任意两个最优解联线上的点都是最优解；⑶线性规划问题的最优值若存在，则一定在某个顶点达到。（Ⅱ）线性规划的有关概念及基本定理1.线性规划常用的概念：凸集、凸组合、极点（凸点）、可行解、基本解、基本可行解、最优解、基本最优解、基、可行基、最优基。2.线性规划的三个基本定理。凸集(Convexset)设K是n维空间的一个点集，对任意两点

时，则称K为凸集。

就是以X（1）、X（2）为端点的线段方程，点X的位置由α的值确定，当α=0时，X=X（2），当α=1时X=X（1）凸组合(Convexcombination)

设是Rn中的点若存在

使得成立，则称X为的凸组合。极点(Extremepoint)

设K是凸集，，若X不能用K中两个不同的点的凸组合表示为<)10()1()2()1(<-+=aaaXXX则称X是K的一个极点或顶点。X是凸集K的极点是指X不可能是K中某一线段的内点，只能是K中某一线段的端点。O

设线性规划的标准型

maxZ=CX

（1.1）

AX=b

（1.2）

X≥0（1.3）式中A是m×n矩阵，m≤n并且r（A）=m，显然A中至少有一个m×m子矩阵B，使得r（B）=m。基

(basis)A中m×m子矩阵B并且有r（B）=m，则称B是线性规划的一个基（或基矩阵basismatrix）。当m=n时，基矩阵唯一，当m<n时，基矩阵就可能有多个，但数目不超过【例8】线性规划

求所有基矩阵。【解】约束方程的系数矩阵为2×5矩阵容易看出r(A)=2，2阶子矩阵有C52=10个，其中第1列与第3列构成的2阶矩阵不是一个基，基矩阵只有9个，即由线性代数知，基矩阵B必为非奇异矩阵并且|B|≠0。当矩阵B的行列式等于零（即|B|=0）时就不是基当确定某一矩阵为基矩阵时，则基矩阵对应的列向量称为基向量(basisvector)，其余列向量称为非基向量（或自由向量）基向量对应的变量称为基变量(basisvariable)，非基向量对应的变量称为非基变量

在上例中B2的基向量是A中的第一列和第四列，其余列向量是非基向量，x1、x4是基变量，x2、x3、x5是非基变量。基变量、非基变量是针对某一确定基而言的，不同的基对应的基变量和非基变量也不同。可行解(feasiblesolution)

满足式（1.2）及（1.3）的解x=（x1,x2…，xn)T称为可行解。基本可行解(basis

feasiblesolution)

若基本解是可行解则称为是基本可行解（也称基可行解）。

基本解(basissolution)对某一确定的基B，令非基变量等于零，利用式（1.２）解出基变量，则这组解称为基Ｂ的基本解。最优解(optimalsolution)满足式（1.1）的可行解称为最优解，即是使得目标函数达到最大值的可行解就是最优解。非可行解(Infeasiblesolution)

无界解

(unboundsolution)显然，只要基本解中的基变量的解满足式（1.３）的非负要求，那么这个基本解就是基本可行解。在例5中，对Ｂ１来说，x1，x2是基变量，x3，x4，x5是非基变量，令x3=x4=x5=0，则式（1.２）为对B2来说，x1,x4,为基变量，令非基变量x2,x3,x5为零，由式（1.2）得到

，x4=4，因|B1|≠０，由克莱姆法则知，x1、x2有唯一解x1＝2/5,x2=1则基本解为由于是基本解，从而它是基本可行解，在中x1<0,因此不是可行解，也就不是基本可行解。反之，可行解不一定是基本可行解例如满足式（1.2）～（1.3），但不是任何基矩阵的基本解。基本解为可行基基可行解对应的基称为可行基；最优基基本最优解对应的基称为最优基；如上述B3就是最优基，最优基也是可行基。当最优解唯一时，最优解亦是基本最优解，当最优解不唯一时，则最优解不一定是基本最优解。例如右图中线段的点为最优解时，Q1点及Q2点是基本最优解,线段的内点是最优解而不是基本最优解。基本最优解

最优解是基本解称为基本最优解。例如，满足式（1.1）~(1.3)是最优解,又是B3的基本解,因此它是基本最优解。基本最优解、最优解、基本可行解、基本解、可行解的关系如下所示：基本最优解基本可行解可行解最优解基本解例如,B点和D点是可行解,不是基本解;C点是基本可行解;A点是基本最优解,同时也是最优解、基本可行解、基本解和可行解。【定理1】若线性规划可行解K非空,则K是凸集。【定理2】线性规划的可行解集合K的点X是极点的充要条件为X是基本可行解。【定理3】若线性规划有最优解,则最优值一定可以在可行解集合的某个极点上到达,最优解就是极点的坐标向量。定理2刻划了可行解集的极点与基本可行解的对应关系，极点是基本可行解，反之，基本可行解一定是极点，但它们并非一一对应，有可能两个或几个基本可行解对应于同一极点（退化基本可行解时）。线性规划的基本定理

定理3描述了最优解在可行解集中的位置，若最优解唯一，则最优解只能在某一极点上达到，若具有多重最优解，则最优解是某些极点的凸组合，从而最优解是可行解集的极点或界点，不可能是可行解集的内点。

若线性规划的可行解集非空且有界，则一定有最优解；若可行解集无界，则线性规划可能有最优解，也可能没有最优解。

定理2及3还给了我们一个启示，寻求最优解不是在无限个可行解中去找，而是在有限个基本可行解中去寻求。下面将介绍一种有效地寻找最优解的方法。（Ⅲ）单纯形法求解线性规划问题

单纯形计算方法(SimplexMethod)是先求出一个初始基可行解并判断它是否最优，若不是最优，再换一个基可行解并判断，直到得出最优解或无最优解。它是一种逐步逼近最优解的迭代方法。

当系数矩阵A中可以观察得到一个可行基时（通常是一个单位矩阵或m个线性无关的单位向量组成的矩阵），可以通过解线性方程组求得基本可行解。【例9】用单纯形法求下列线性规划的最优解【解】化为标准型，加入松驰变量x3、x4则标准型为系数矩阵A及可行基B1r(B1)=2，B1是一个初始基,x3、x4为基变量，x1、x2为非基变量，令x1=0、x2=0由约束方程知x3=40、x4=30得到初始基本可行解X(1)=(0,0,40,30)T

以上得到的一组基可行解是不是最优解，可以从目标函数中的系数看出。目标函数Z=3x1+4x2中x1的系数大于零，如果x1为一正数，则Z的值就会增大，同样若x2不为零为一正数，也能使Z的值增大；因此只要目标函数中非基变量的系数大于零，那么目标函数就没有达到最大值，即没有找到最优解，判别线性规划问题是否达到最优解的数称为检验数，记作λj,j=1,2…,n。

本例中λ1=3,λ2=4,λ3=0,λ4=0。参看表1.4（a）。最优解判断标准当所有检验数λj≤0（j=1，…，n）时，基本可行解为最优解。当目标函数中有基变量xi时，利用约束条件将目标函数中的xi消去即可求出检验数。检验数目标函数用非基变量表达时的变量系数进基列出基行bi/ai2，ai2>0θi表1(1)XBx1x2x3x4bx3211040x4130130λj3400

(2)x3x2λj

(3)x1

x2

λj

基变量110001/301/3105/31-1/3405/30-4/330103/5-1/51801-1/52/5400-1-1将3化为1乘以1/3后得到3018最优解X=(18，4，0，0)T，最优值Z=70O20301040(3,4)X(3)=(18,4)最优解X=(18,4)最优值Z=70X(1)=(0,0)2010x2x130X(2)=(0,10)单纯形法全过程的计算，可以用列表的方法计算更为简洁，这种表格称为单纯形表（表1）。计算步骤：1.求初始基可行解，列出初始单纯形表，求出检验数。其中基变量的检验数必为零；2.判断：（a）若λj≤０（j＝１，２，…，n）得到最优解；（b）某个λk>0且aik≤０（i=1，2,…,m）则线性规划具有无界解(见例1.18)。（c）若存在λk>0且aik(i=1,…,m)不全非正，则进行换基；第Ｌ个比值最小，选最小比值对应行的基变量为出基变量，若有相同最小比值，则任选一个。aLk为主元素；

(c）求新的基可行解：用初等行变换方法将aLk

化为１,k列其它元素化为零（包括检验数行）得到新的可行基及基本可行解，再判断是否得到最优解。（b）选出基变量，求最小比值：3.换基：（a）选进基变量设λk=max｛λj|λj>0｝,xk为进基变量【例10】用单纯形法求解【解】将数学模型化为标准形式：不难看出x4、x5可作为初始基变量，单纯法计算结果如表2所示。Cj12100bθCBXBx1x2x3x4x50x42－3210150x51/3150120λj12100

0x42x2λj

1x1

2x2

λj

表21/3150120301713751/30－90－2M2025601017/31/31250128/9－1/92/335/300－98/9－1/9－7/3最优解X=(25，35/3，0，0，0)T，最优值Z=145/3【例11】用单纯形法求解

【解】

这是一个极小化的线性规划问题,可以将其化为极大化问题求解,也可以直接求解,这时判断标准是：λj≥0(j=1，…，n)时得到最优解。容易观察到,系数矩阵中有一个3阶单位矩阵,x3、x4、x5为基变量。目标函数中含有基变量x4,由第二个约束得到x4=6+x1－x2，并代入目标函数消去x4得XBx1x2x3x4x5bθx3x4x51-16[1]121000100015→6215621/2λj1-1↑000

x2x4x51-241001-1-20100015111

λj20100

表中λj≥0,j=1,2,…,5所以最优解为X=(0,5,0,1,11,)最优值

Z=2x1－2x2－x4=－2×5－1=－11极小值问题,注意判断标准,选进基变量时,应选λj<0的变量xj进基。表3【例12】求解线性规划【解】化为标准型初始单纯形表为XBx1x2x3x4bx3x432－2－1100114λj－1100

λ2=1>0,x2进基，而a12<0，a22<0，没有比值，从而线性规划的最优解无界。由模型可以看出，当固定x1使x2→+∞且满足约束条件，还可以用图解法看出具有无界解。【例13】求解线性规划【解】:化为标准型后用单纯形法计算如下表所示XBx1x2x3x4x5bθ(1)x3x4x5－111[2]2－11000100014→10225—λj24↑000(2)x2x4x5－1/2[2]1/21001/2－11/201000126→4—38λj4↑0－200(3)x2x1x50101001/4－1/2[3/4]1/41/2－1/40017/235/2→14—10/3λj000↑－20(4)x2x1x30101000011/31/3－1/3－1/32/34/38/314/310/3λj000－20

表(3)中λj全部非正,则最优解为:

表(3)表明,非基变量x3的检验数λ3=0,x3若增加,目标函数值不变,即当x3进基时Z仍等于20。使x3进基

x5出基继续迭代,得到表(4)的另一基本最优解X(1),X(2)是线性规划的两个最优解，它的凸组合

仍是最优解，从而原线性规划有多重最优解。唯一最优解的判断：最优表中所有非基变量的检验数非零,则线规划具有唯一最优解

。多重最优解的判断:最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解。无界解的判断:

某个λk>0且aik≤０（i=1，2,…,m）则线性规划具有无界解退化基本可行解的判断:存在某个基变量为零的基本可行解。（三）对偶问题

对偶理论是线性规划的重要内容之一。随着线性规划问题研究的深入，人们发现对应于每个线性规划问题都伴生一个相应的线性规划问题。前者是由矩阵Ａ，右端向量ｂ和价值向量Ｃ定义的，称之为原问题；后者也是由相同的数据集合Ａ，ｂ和Ｃ构成的，称之为原问题的对偶问题。一对原问题和对偶问题是紧密关联的，它们不但有相同的数据集合，相同的最优目标函数值，而且在求得一个线性规划的最优解的同时，也同步得到对偶线性规划的最优解。对偶理论深刻地指示了原问题和对偶问题的内在联系，由对偶问题引伸出来的对偶解还有着重要的经济意义，是研究经济学的重要概念和工具之一。（1）对偶问题的提出例1、某工厂生产甲,乙两种产品，这两种产品需要在A,B,C三种不同设备上加工。每种甲、乙产品在不同设备上加工所需的台时，它们销售后所能获得的利润，以及这三种设备在计划期内能提供的有限台时数均列于表。试问如何安排生产计划，即甲,乙两种产品各生产多少吨，可使该厂所获得利润达到最大。

设备每吨产品的加工台时可供台时数甲乙ABC359448364076利润（元/吨）3230用图解法或单纯形法可求得最优解

(元)

即在计划期内甲产品生产4/3吨，乙产品生产8吨，可以使总利润达到最大，为元。

假设计划期内甲乙两种产品各生产x1x2

吨，设备每吨产品的加工台时可供台时数甲乙ABC359448364076利润（元/吨）3230

例1'

现在从另一个角度来考虑该工厂的生产问题:

假设该厂的决策者打算不再自己生产甲,乙产品，而是把各种设备的有限台时数租让给其他工厂使用，这时工厂的决策者应该如何确定各种设备的租价。

设y1y2y3

分别为设备A，B，C每台时的租价，约束条件：把设备租出去所获得的租金不应低于利用这些设备自行生产所获得的利润目标函数：所获租金总额最小．为什么要最小化？由此可得两个对称的线性规划：矩阵形式：（2）对偶定义1、对称形式（典则形式）的对偶定义

一对对称形式的对偶规划之间具有下面的对应关系。

(1)若一个模型为目标求“极大”，约束为“小于等于”的不等式，则它的对偶模型为目标求“极小”，约束是“大于等于”的不等式。即“max，≤”和“min，≥”相对应。

(2)从约束系数矩阵看：一个模型中为Ａ，则另一个模型中为AT。一个模型是m个约束，n个变量，则它的对偶模型为n个约束，m个变量。

(3)从数据b、c的位置看：在两个规划模型中，b和c的位置对换。

(4)两个规划模型中的变量皆非负。

标准形式的对偶定义推导过程：

若原问题是极小化问题，则对偶问题是极大化问题；若原问题是极大化问题，则对偶问题是极小化问题在原问题和对偶问题中，约束右端向量与目标函数的系数向量恰好互换对于极小化问题的“≥”型约束(极大化问题的“≤”型约束)，相应的对偶变量有非负限制；对于极小化问题的“≤”型约束(极大化问题的“≥”型约束)，相应的对偶变量有非正限制；对于原问题的“=”型约束，相应的对偶变量无正负限制对于极小化问题具有非负限制的变量(极大化问题具有非正限制的变量),在其对偶问题中，相应的约束为“≤”型约束；对于极小化问题具有非正限制的变量(极大化问题具有非负限制的变量),在其对偶问题中，相应的约束为“≥”型约束；对于原问题中无正负限制的变量，在其对偶问题中，相应的约束为“=”型约束对偶规则【例15】写出下面线性规划的对偶规划模型练习：写出对偶规划。（2）对偶理论对称性：对偶问题的对偶是原问题弱对偶性：若x和y分别是(LP)和(DP)的可行解，则c’x≥b’y.可行解为最优的充分条件：设x和y分别是(LP)和(DP)的可行解，若c’x=b’y，则x和y分别是(LP)和(DP)的最优解.无界性：若(LP)和(DP)之一为无界解，则其对偶问题无可行解.对偶定理：若(LP)和(DP)均有可行解，则它们都有最优解，且最优值相同.最优基本可行解之间的关系：若(LP)存在一个对应基B的最优基本可行解，则单纯形乘子是(DP)的一个最优解.互补松弛性：设x和y分别是(LP)和(DP)的可行解，则x和y分别是(LP)和(DP)的最优解的充要条件为y’(Ax-b)=0，且

(c’-y’A)x=0.（3）对偶单纯形法

由对偶理论可以知道，对于一个线性规划问题，我们能够通过求解它的对偶问题来找到它的最优解。

对偶单纯形法是求解线性规划的另一的基本方法。由于它是根据对偶原理和单纯形法的原理而设计出来的，因此称为对偶单纯形法。不能简单理解为是求解对偶问题的单纯形法。原始单纯形法从一个基本可行解迭代到下一个基本可行解时，总是保持解的可行性不变，变化的只是检验数例如对于极大化问题而言，检验向量从部分分量不满足逐步过渡到，一旦达到，也就达到了最优解。由于，是对偶问题的可行解。可以这样理解原始单纯形法的迭代过程：从基本可行解向最优解的迭代过程，是在始终保持原问题可行性的条件下，其对偶解由不可行向可行转化。一旦对偶解也成为可行解时，原问题的可行解即成为最优解。也就是说，当原问题解保持可行性条件下，其最优性条件与对偶解可行这个条件是一致的。这为我们提供了另一条求解思路：在迭代过程中，始终保持对偶问题解的可行性，而原问题的解由不可行向可行性转化，一旦原问题的解也满足可行性条件，也就达到了最优值。这就是对偶单纯形方法的思路。对偶单纯形法并不需要把原问题转化为对偶问题，而是利用原问题与对偶问题的数据相同，只是所处的位置不同这一特点，直接在反映原问题的单纯形表上进行运算。对偶单纯形法不要求向量,处理带剩余变量的一些问题很方便。（2）确定换出变量根据，确定基变量xl

作为换出变量。检验xl

所在行各元素若所有alj≥0,则无可行解，停止计算。否则转入(３)，（3）确定换入变量按最小比值原则，若确定非基变量xk

为换入变量。（4）以alk

为主元进行旋转变换，得新的单纯形表，重复（2）-（4），直到求得最优解。对偶单纯形法的计算步骤如下（对于极大化目标函数问题）：（1）根据原始线性规划，列出初始单纯形表，检查b列数字和检验行元素，若b列数字全部非负，检验数全部非负，则已经求得最优解，停止计算。若b列中至少有一个负分量，检验数全部非正，则转入（2）,【例16】用对偶单纯形法求解解：先化为标准型

对偶单纯形允许约束方程右端为负，因此可将方程2，3两端同乘-1，可得含单位矩阵的标准型：据此列出初始单纯形表，并施行对偶单纯形法迭代步骤如下：-5/4-7/4000-16-W-1/41/40102x2

-2-1/4-3/40014x1

-35/43/41004x3

0-2/3000-7/3-20/3-W-1/30011/310/3x2

-21/3100-4/3-16/3x4

0101018x3

0000-2-30-W100-3-1-10x5

00101-1-2x4

00013218x3

0x5

x4

x3

x2

x1

bXB

CB

000-2-3C可得最优解是是是是否否否否所有所有得到最优解计算计算典式对应原规划的基本解是可行的典式对应原规划的基本解的检验数所有所有计算计算以为中心元素进行迭代以为中心元素进行迭代停没有最优解没有最优解单纯形法

对偶单纯形法对偶单纯形法的优点和应用的前提条件对偶单纯形法的优点是原问题的初始解不要求是可行解，可以从非可行解开始迭代，从而省去了引入人工变量的麻烦。当然对偶单纯形法的应用也是有前提条件的，这一前提条件就是对偶问题的解是基可行解。五、线性规划的灵敏度分析1.灵敏度分析的内涵

一个标准形式的线性规划问题可由约束矩阵Ａ，右端项向量b，和价值向量Ｃ完全确定，假如一个线性规划问题对于给定的数据集合Ａ，b，Ｃ有最优解，则最优解。最优目标函数值，其中Ｂ为最优基。但是线性规划问题所对应的数据集合Ａ，b，Ｃ常常是通过预测或估计所得到的统计数据，在实际使用中，不免会有一定的误差。而且随着市场环境，工艺条件和资源数量的改变，这些数据完全可能发生变化。因此有必要来分析一下当这些数据发生波动时，对目前的最优解，最优值或者最优基会产生什么影响，这就是所谓的灵敏度分析。

灵敏度分析主要讨论如下二类问题：线性规划的数据集合在什么范围内波动将不影响最优解或最优基？

若最优解发生变化，应如何用最简单的方法找到新的最优解。为讨论方便，以下列出标准型线性规划问题最优单纯形表的一般形式，其中B为线性规划问题的最优基：CC1

C2

…Cn

CB

XB

bx1

x2

…xn

CB1

XB1

B-1bB-1A=B-1(P1，P2，…，Pn)CB2

XB2

::CBm

XBm

ZCBB-1bC-CBB-1A1.价值向量C的改变当价值向量由时，最优单纯形表发生变化的只是检验行的有关数据，其中基变量检验数保持为零。非基变量检验数应修改为：目标函数值应为。只要变化以后的非基变量检验数那么原最优解仍然为最优。至于目标函数值是否改变，取决于基变量价值系数的改变量以下分别就价值系数对应非基变量或基变量两种情况加以讨论：若是非基变量的价值系数，为该价值系数的改变量。那么在最优表中只有

的检验数发生变化。由只要即就可以保持现行最优解仍为最优，由此可以确定价值系数的可变化范围。若超出稳定范围，那么的检验数，当前解已不是最优解。此时必须以修改后的单纯形表出发，重新进行单纯形迭代，直至求出新的最优解。非基变量价值系数的变化，可能使最优基Ｂ改变，从而导致最优解和最优值的改变。

若是某基变量的价值系数，为价值系数的改变量。由于为基变量，所以在最优表中所有的非基变量检验数均发生了变化，由只要非基变量检验数：

或即可最优解仍然保持为最优，其中为原最优表中非基变量检验数，为最优表系数矩阵中基变量所在行中所有非基变量对应的系数。由上式可得到一个联列不等式组，求解该不等式组就可得到价值系数的可变动范围。基变量价值系数的变化，可能使最优基Ｂ改变，从而导致最优解的改变。而最优值则一定改变。【例17】

、某工厂用甲乙两种原料生产A，B，C，D四种产品，每种产品的利润，现有原料数及每种产品消耗原料定额如表所示：

原料（公斤）产品（万件）供应量ABCD甲乙321040021/2183利润（万元/万件）985019问应该怎样组织生产，才能使总利润最大，若产品Ａ或Ｃ的利润产生波动，波动范围多大时，原最优解保持不变？解：设生产Ａ，Ｂ，Ｃ，Ｄ四种产品各万件，则此问题的线性规划模型为：标准化，引入松弛变量x5,x6，，

利用单纯形表求解：-4-2/300-13/3-10/388Z24/3012/3-10/3-1/2-1/310-1/64/321x4x319500202-3-1084Z2612/301/21/3-5/30011/401/213/2x1x395098013/20-2575Z1-3203/21-50011/401/233/2x5x3050985019000Z9/53/232104100021/201183x5x600

x1

x2x3

x4x5x6bXBCBθ98501900C即最优生产方案是生产Ｃ产品1万件，Ｄ产品2万件，不生产Ａ,Ｂ两种产品。可得最大利润为88万元。C

98501900θCBXBb

x1

x2x3

x4x5x61950x4x32124/3012/3-10/3-1/2-1/310-1/64/3Z88-4-2/300-13/3-10/3最优表：(1)若Ａ产品的利润，有改变量。因为为非基变量，由推得或（万元）时原最优解不变，最优利润值（万元）也不变。(２)若Ｃ产品的利润，有改变量。因为为基变量，由推得即当或时原最优解不变，最优利润值（万元）2.右端项向量b的改变

当右端项向量b由时，改变的只是表中右端常数列。此时基变量，目标函数值。而检验行的检验向量保持不变。右端项向量b的波动会使最优解和最优目标函数值发生变化，但原最优解的检验向量仍能保持非正。为了使B可行，只要或若，因为检验向量仍保持非正，因此可用对偶单纯形法再次进行迭代，直到求得新最优解。右端列向量b变化时，最优解和最优值一定改变。因此我们主要讨论右端列向量b变化时，最优基Ｂ是否改变【例8】、在例17中，若想增加甲种原料，问增加多少时原最优基不变？

解：设甲种原料的改变量为,则由即

由此可以推得，即当时，原最优基不变。此时最优解或最优目标函数值

(万元)3.约束矩阵A的改变

约束矩阵A的改变可能导致不同的最优解和最优基.以下只涉及两种较简单的情形：增加或减少一个变量，增加或减少一个约束条件。

以下讨论假设原线性规划问题有一个最优解其中Ｂ为最优基，且约束矩阵被划分为

增加或减少一个变量（1）增加一个新变量假设在获得原线性规划的最优解之后，又发现了一个新变量，其对应的价值系数为，在新的约束矩阵中对应的系数列向量为，于是可得如下新的线性规划问题：设，则

为新线性规划问题的一个可行解。因此可在此基础上开始单纯形法，求新的最优解。如果，则含的当前解是新问题的最优解。否则以为换入变量进行基变换，继续使用单纯形算法为新的线性规划寻求一个最优解。（2）减少一个变量如果必须把某个变量从决策变量中去掉，那么原最优解在新的线性规划中一定发生改变。我们讨论的目标是如何用最小的工作量去寻求新的最优解。如果原最优解中的，则只需将从原最优解中剔除即可保持最优。如果原最优解中的（此时必为基变量），则必须重新计算新的解。为此可建立一个辅助线性规划：由于约束方程组没有改变，因此原最优解在辅助线性规划中可以作为初始基本可行解用于单纯形算法。如果辅助线性规划最优解的目标函数值为零，则用此最优解剔除以后，可得新的线性规划问题的一个初始基本可行解，经有限次迭代，即可求出新问题的最优解。否则从原来问题中去除而得到的新的线性规划必定是不可行的。增加或减少一个约束（1）