运筹学课程讲义

运筹学课程讲义第一部分线性规划第一章线性规划的基本性质1.1线性规划的数学模型一、 线性规划问题的特点胜利家具厂生产桌子和椅子两种家具。桌子售价50元/个，椅子售价30元/个。生产桌子和椅子需木工和油漆工两种工种。生产一个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？maxz=50x+30x124x+3x<12012<2x+x<5012x,x>012例：某工厂生产某一种型号的机床。每台机床上需要2.9m、2.1m、1.5m的轴，分别为1根、2根和1根。这些轴需用同一种圆钢制作，圆钢的长度为74m。如果要生产100台机床，问应如何安排下料，才能用料最省？二、 数学模型的标准型1.繁写形式2.缩写形式向量形式矩阵形式

三、 任一模型如何化为标准型？1.若原模型要求目标函数实现最大化，如何将其化为最小化问1.题？2.若原模型中约束条件为不等式，如何化为等式？2.若原模型中约束条件为不等式，如何化为等式？3.若原模型中变量xk是自由变量，如何化为非负变量?k4.若原模型中变量X.有上下界，如何化为非负变量?j3.若原模型中变量xk是自由变量，如何化为非负变量?k4.若原模型中变量X.有上下界，如何化为非负变量?jmaxz=一5x一6x一7x123一x+5x一3xn15

123一5x一6x+10x<20< 1 2 3x一x一x=一5

123x<0,x>0,x无约束123令x'=-x,x=x'-x”，x',x”>0,-Z=Z'1 1 3 3 3 3 3minz'=-5x'+6x+7x'一7x''+0x一Mx一Mx1 2 3 3 5 6 7x'+5x—3x'+3x''—x+x=151 2 3 3 4 65x'一6x+10x'一10x''+x=20< 1 2 3 3 5x'+x+x'—x''+x=—5

12337x',x,x',x'',x,x,x,x>0

123345671.2图解法该法简单直观，平面作图适于求解二维问题。使用该法求解线性规划问题时，不必把原模型化为标准型。、图解法步骤由全部约束条件作图求出可行域作出一条目标函数的等值线平移目标函数等值线，作图求解最优点，再算出最优值、从图解法看线性规划问题解的几种情况有唯一最优解有无穷多组最优解3.有唯一最优解有无穷多组最优解3.无可行解无有限最优解（无界解）minz=6x+4x122x+x>1123<3x+4x>-122x,x>012最优解（丄,0），最优值32直观结论：1）线性规划问题的可行域为凸集，特殊情况下为无界域但有有限个顶点）或空集；2）线性规划问题若有最优解，一定可以在其可行域的顶点上得到。1.3线性规划的基本概念和基本定理一、 线性规划问题的基与解可行解最优解基基向量非基向量基变量非基变量基本解基本可行解最优基本可行解退化的基本解二、 几何意义上的几个基本概念凸集凸组合顶点三、 线性规划问题的基本定理定理1：若线性规划问题存在可行域，则其可行域是凸集。引理1：线性规划问题的可行解X=(x,x,,X)T为基本可行解的充要12n条件是X的正分量对应的系数列向量是线性无关的。定理2：线性规划问题的基本可行解对应于可行域的顶点。引理2：K是有界凸集，则任何一点XeK可表示为K的顶点的凸组合。定理3：如果线性规划问题有有限最优解，则其目标函数最优值一定可以在可行域的顶点上达到。四、 求解线性规划问题的基本思路在有限个基本可行解中寻找最优基本可行解。找一个基本可行解(m个线性无关的系数列向量)，由其换到另一个基本可行解。实质即为换基。前提是保证新的基本可行解的目标函数值比原来的更优而不是更劣。第二章单纯形法它是求解线性规划最为成熟的算法。胜利家具厂生产桌子和椅子两种家具。桌子售价50元/个，椅子售价30元/个，生产桌子和椅子需要木工和油漆工两种工种。生产一个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？maxz=50x+30x124x+3x<12012<2x+x<5012x,x>012将其变形，得4x+3x+x=1201232x+x+x=50124x,x,x,x>011234将xx对应的单位矩阵作为初始可行基。令xx为基变量，xx为非TOC\o"1-5"\h\zxx xx xx3 4 3 4 1 2基变量。原模型变形为maxz=50x+30x12x=120一4x一3x3 1 2ix=50一2x一x41 2x,x,x,x>01234如果令非基变量「x等于零，得一个基本可行解（0,0，120,50）,12对应的目标函数值z=0最优性检验：该解是否最优？显然不是。经济意义分析：,x等于零12意味着家具厂不开工生产,销售收入为零,资源未得到充分利用。数学角度分析：非基变量x,x前的系数都为正，表明目标函数值有增12

加的可能。只要将系数为正的非基变量与某一基变量对换，当换入变量的值增加时，目标函数值就可能增加。换基迭代：寻找下一个可行解需要进行换基迭代。换基后需满足：（1）新的解仍是基本可行解；（2）目标函数得到改善。选择入基变量：x,x系数均为正。对求目标函数极大化的问题，我们12希望目标值增加得越快越好，因此应选系数最大的,入基。1选择出基变量：x入基后，其值从零增加并引起其他变量取值的变化。1由问题的典则表达式和变量必须取正值的条件，得下列不等式关系：x=120-4x-3x>03 1 2x=50-2x-x>04 1 2因迭代后x仍为取零值的非基变量，上式可简化为2120-4x>0150-2x>01很明显，只有选x=min（120/4,50/2）=25时，才能使上述不等式成立，1并使基变量x变为零，正好满足非基变量必须为零的条件，所以可令4x出基，新的典则方程变为44x+x=120一3xTOC\o"1-5"\h\z1 3 22x=50一x一x1 2 4化简后得x=25一0.5x一0.5x化简后得1 2 4x=20一x+2x3 2 4代入目标函数可得z代入目标函数可得z=1250+5x一25x2 2 4得到下一个基本可行解（25，0，20，0），并完成了第一次迭代。新解是最优解吗？需进行最优检验。由于目标函数中x的系数仍为2正，说明多生产椅子仍有利可图，该解仍不是最优解。再次迭代。

入基，X入基，X3出基’换基后典则形式变为z=1350—5x一15xTOC\o"1-5"\h\z3 3 4x=15+0.5x一1.5x1 3 4x=20一x+2x2 3 4第三个基本可行解为（15，20，0，0），松弛变量都已为零，表明资源已得到充分利用；非基变量在目标函数中的系数全为负值，说明目标函数已无法进一步改善，因此该解已是最优解。2.1单纯形法原理、构造初始可行基引入附加变量，把数学模型化为标准型若约束条件中附加变量的系数是-1或原约束即为等式，则必须引入人工变量，以构成初始可行基目标函数中，附加变量的系数为0,而人工变量的系数为M（很大的正数）、求出一个基本可行解用非基变量表示基变量和目标函数式+x）54x+3x+8x+M（2—x一x+x）+M（5一2x+x）51 2 3 1 3 4 2 5=（4-M）x+（3-M）x+（8-3M）x+Mx+Mx+7M1 2 3 4 5求出一个基本可行解及相应的z值三、最优性检验最优性检验的依据一检验数。j最优解判别定理：若在极小化问题中，对于某个基本可行解，所有检验数。＞0,且人工变量为0,则这个基本可行解是最优j解。对于极大化问题，只要把上述定理中饨＞0改成。＜0即可。jj这里的检验数。即为（c-z）。jjj无穷多最优解判别定理：若在极小化问题中,对于某个基本可行解，所有检验数，＞0,又存在某个非基变量的检验数为0，j且人工变量为0,则线性规划问题有无穷多最优解。无可行解情况若在极小化问题中，对于某个基本可行解，所有检验数＞0，j但人工变量工0,则该线性规划问题无可行解。四、基变换基本可行解的改进定理换入变量的确定换出变量的确定最小非负比值规则Q=b/a=min{b/ala＞0}rrkiiikik在单纯形法迭代中,基变换带来可行域顶点的变换,且相邻两次迭代所对应的顶点也是相邻的。无有限最优解（无界解）判定定理：若在极小化问题中,对于

某个基本可行解，有一个非基变量的检验数＜0,但P列中kk没有正元素，且人工变量为0，则线性规划问题无有限最优解（具有无界解）。2.2单纯形法的表格形式一、构造初始可行基，并计算检验蜕j。=C-zjjj12mjBjz=(c,c,„,c)•P=(C)•P'12mjBjj二、从表中找到基本可行解和相应目标函数值三、最优性检验四、基变换1.换入变量的确定负检验数中最小2.换出变量的确定最小非负比值规则3.主元素的确定换入元素所在列和换出元素所在行交点处二、从表中找到基本可行解和相应目标函数值三、最优性检验四、基变换1.换入变量的确定负检验数中最小2.换出变量的确定最小非负比值规则3.主元素的确定换入元素所在列和换出元素所在行交点处的元素4.取主变换4.取主变换通过矩阵行的初等变换，把换入向量变换为单位列向量。即基变换，亦即单纯形法的一次迭代。2.3大M法和两阶段法根据处理人工变量的方法不同，单纯形法的两种常见形式。大M法也叫罚函数法，前已介绍。两阶段法将线性规划问题的求解分为两个阶段。第一阶段：判断原线性规划问题是否有可行解。该阶段所要求解的线性规划问题的约束条件即原问题的约束条件，而目标函数取全部人工变量之和，求其最小值。若求解结果是上述目标函数的最小值为0，则说明所有人工变量都能退出基，原问题有可行解，且第一阶段的最终单纯型表上的基本可行解就是原问题的一个基本可行解。若求解的结果是上述目标函数的最小值大于0，则说明最终人工变量不能完全退出基，原问题无可行解，应停止计算。第二阶段：求解原线性规划问题的最优解。以第一阶段的最终单纯型表为基础，去掉其中的人工变量列，把目标函数换成原问题的目标函数，并修正因c改变而改变的(C)T、o和jBj-Z。以此作为第二阶段的初始表，继续迭代，得原问题的最优解。438000迭代次数(c)TB基变量x1x2xx34xb51■8_x3-2102-113x20023-1922.4退化问题、什么是退化当基本解、基本可行解、最优基本可行解中有基变量为0时，即出现了退化。退化情况下，即使存在最优解，也可能出现循环现象，即迭代过程总是重复解的某一部分序列，目标函数值总是不变，永远达不到最优解。二、 摄动法1.摄动法简介对线性规划原问题，为了避免退化情况下发生循环，而使向量b摄动。确定换出变量的步骤举例三、 勃兰特方法法则1：在极小化问题中，如果有几个检验数c-z）都是负的，那jj么选其中下标最小的非基变量作为换入变量。法则2：在极小化问题中，根据最小非负比值规则确定换出变量时，如果有几个比值同时达到最小比值，那么选其中下标最小的基变量作为换出变量。定理：只要在迭代时，遵循上述法则，就不会出现循环。3.5改进单纯形法每次迭代只计算换入列、常数列及检验数行以提高计算效率。一、单纯形法的矩阵形式用矩阵（分块）形式表示线性规划标准型

把矩阵A、C、X分别按“基”与“非基”分成两块A=(B,N)C=(C,C)BNXBXN其中B=N=P，PB=N=P，P，1P，Pm+1m+P)m，P)nC=(c,c,„,c)C=(c,c,„,c)B12C=(c,cN,„,c2x1x2xm+1xm+2将分块结果代入标准型，BX+NX=bBNX>0,XBNminzminz=CXBXNN用矩阵（分块）形式表示基本解、目标函数值及检验数X=B一ib-B一1NXBNz=CB」+(C-CB一iN)XBNBNb=C-CB_1NNNB令X=0,可得NX=B_]bBz=CB_1bB3.单纯型乘子Y。Y=CBB、改进单纯形法的求解步骤1.完成第0次迭代表。构造初始可行基，计算B-1。再利用公式0b=C-CB-1N=C-CN，计算第0次迭代表中的检验N0N0 B0 00N0B00ork数。确定换入向量为P，换出向量为P，主元素是orkkBr计算B_1i+1构造基矩阵Bi+1计算B_1i+1第一种方法：已知B，用初等变换法求其逆矩阵B_1。i+1 i+1第二种方法：已知B_1和第i次迭代表的换入列P'，主元素为a，,i k rk通过取主变换求出B_1。i+1计算第i+1次迭代表的常数列和检验数。常数列=B_1・bY=C・B_ii+1Bi+1 i+1=CN=CNi+1 Ni+1-YNi+1 i+1进行最优性检验如果。＞0,且人工变量为0则已经得到最优解。否则，转下步。N5.计算第i+1次迭代表中的换入列P'kP'=B-・Pk i+1 k6.确定第i+1次迭代表中换出向量的下标B。r最小非负比值规则令i=i+1,返回步骤2。三、 逆的乘积形式B_1=EE・„EEi+1ii_1 10改进单纯形法的基本思想就是给定初始基本可行解后,通过修改旧基的逆来获得现行基的逆,进而完成单纯形法的其他运算。四、 计算举例01212000121200「-1o—T11_211_22常数列105」L_2Y=C•B-i=(8,3J 03 B3 3 _2 1b =C-YN=(ccccc)_Y(PPPPP)N3 N33314567 314567=(400MM)-(2 3)1_1010、I00_101丿(400MM)_(2_2 _3 23)=(223M-2M-3)第三章线性规划的对偶原理3.1线性规划的对偶问题一、 对偶问题的提出换位思考家具厂的线性规划问题，该问题站在家具厂管理者的角度追求销售收入最大maxz=50x+30x124x+3x<12012<2x+x<5012x,x>012某企业家有一批待加工的订单，有意利用该家具厂的木工和油漆工资源来加工他的产品。他需要与家具厂谈判付给该厂每个工时的价格。如果该企业家已对家具厂的经营情况有详细了解，他可以构造一个数学模型来研究如何才能既让家具厂觉得有利可图，肯把资源出租给他，又使自己付的租金最少。目标:租金最少；y-付给木工工时的租金；y-付给油漆工工时的租金12minw=120y+50y12所付租金应不低于家具厂利用这些资源所能得到的利益1）支付相当于生产一个桌子的木工、油漆工的租金应不低于生产一个桌子的收入4y+2y>50122）支付相当于生产一个椅子的木工、油漆工的租金应不低于生产一个椅子的收入3y+y>30123）付给每种工时的租金应不小于零 y>0,y>012二、 原问题与对偶问题的数学模型对称形式的对偶原问题和对偶问题只含有不等式约束时，一对对偶问题的模型是对称的，称为对称形式的对偶。原问题：minz=CX<AX>bX>0对偶问题：maxw=YbYA<CY>0非对称形式的对偶若原问题的约束条件全部是等式约束（即线性规划的标准型），即一minz=CXAX=bX>0则其对偶问题的数学模型为maxw=YbYA<CY是自由变量可把原问题写成其等价的对称形式：minz=CXAX>b

AX<bX»0minz=CXb-bX>0设Y]=（y],y2,…,ym）,Y2=（ym+1，ym+2，„,y2m）。根据对称形式的对偶模型,写出上述问题的对偶问题：maxw=(Y1maxw=(Y1,Y2)b-b（丫1，丫2）・「a]c-A.0 Y2,0maxw=(Y1-Y2)•b(Y1-Y2)A.C丫详0 Y2,0令Y=Y1-Y2,得对偶问题为：12,maxw=YbYA<CY是自由变量

原问题与对偶问题的对应关系原问题（或对偶问题）对偶问题（或原问题）目标函数minz目标函数maxwn个变量n个约束变量＞0约束＜变量＜0约束＞自由变量约束=m个约束m个变量约束＞变量＞0约束＜变量＜0约束=自由变量约束条件的限定向量目标函数的价值向量目标函数的价值向量约束条件的限定向量maxz=2x+x+3x+x1 2 3 4x+x+x+x<5原问题： 21x-+3x=-4TOC\o"1-5"\h\zV 1 2 3x一x+x>1134x,x>0,x,x无约束1 3 2 4minw=5y一4y+y1 2 3y+2y+y>21 2 3对偶问题： y1-y2=1vy+3y一y>3123y+y=11 3y>0,y无约束，y<01 2 3

minz=3x一2x一3x+4x1234原问题：x一2x+3x+4x<31234原问题：x+3x+4x>-5TOC\o"1-5"\h\zV 2 3 42x一3x一7x一4x=21 2 3 4x>0,x<0,x,x无约束1 4 2 3maxw=3y一5y+2y1 2 3y+2y<313对偶问题： 一2y1+y2-3y3=2v3y+3y一7y=-31234y+4y一4y>41 2 3y<0,y>0,y无约束1233.2对偶问题的基本性质和基本定理一、 对称性定理对称性定理：对偶问题的对偶是原问题、弱对偶性定理弱对偶性定理：若X（0）和Y（0）分别是原问题和对偶问题的可行解，则(0)>Y(0)>Y(0)b。三、 最优性定理最优性定理：若X（0）和Y（0）分别是原问题和对偶问题的可行解，且有CX（0）=Y（0）b,则X（0）和Y（0）分别是原问题和对偶问题的最优解。四、 对偶定理对偶定理：有一对对偶的线性规划问题，若其一有一个有限的最优解，则另一个也有最优解，且相应的目标函数值相等。若任一个问题具有无界解，则另一个问题无可行解。五、 单纯型乘子Y的定理单纯型乘子Y的定理：若线性规划原问题有一个对应于基B的最优基本可行解，则此时的单纯型乘子丫=CBi是相应于对偶问题的一B个最优解。六、 对称形式对偶的互补松弛定理对称形式对偶的互补松弛定理：若X（o）和Y（o）分别是原问题和对偶问题的可行解，则X（o）和Y（o）都是最优解的充要条件是，对所有i和j,下列关系式成立：如果x（o）＞O,必有Y（o）P=cjjj如果Y（o）P＜c，必有x（o）=Ojjj如果y（°）＞0,必有AX（o）=biii如果AX（o）＞b，必有y（0）=0iii其中P是A的第j列，A是A的第i行。ji互补松弛定理意味着：如果原问题最优解X（0）中第j个变量X（0）为正，j则其对偶问题中与之对应的第j个约束式在最优情况下必呈严格等式（即其松弛变量为0）；而如果对偶问题中第j个约束式在最优情况下呈严格不等式，则原问题最优解X（0）中第j个变量X（0）必为0。类似地，j如果对偶问题最优解Y（0）中第i个对偶变量y（0）为正，则其原问题中i与之对应的第i个约束在最优情况下必呈严格等式（即其剩余变量为0）；而如果原问题中第i个约束在最优情况下呈严格不等式，则对偶问题最优解Y（0）中第i个对偶变量y（°）必为0。i互补松弛性：YX=oYX=0x,Y为最优解SS对一对对偶规划的最优解而言，如果对应某一约束条件的对偶变量的值为非零，则该约束条件取严格等式；反之，如果某个约束条件取严格不等式，则其对应的对偶变量一定为零。七、 非对称形式对偶的互补松弛定理非对称形式对偶的互补松弛定理：若X（o）和Y（o）分别是原问题和对偶问题的可行解，则X（o）和Y（o）都是最优解的充要条件是，对所有j,下列关系式成立：如果x（0）>0,必有Y（o）P=cjjj如果Y（o）P<c，必有x（o）=Ojjjmaxz=x+x12例：已知线性规划问题-X1+X2+X3-2彳一2x+x—x<1123x,x,x>0123试用对偶理论证明上述线性规划问题无最优解该问题存在可行解，如x=（0,0,0）又对偶问题为minw=2y+y12-y-2y>112y+y>122y-y>012y,y>012由第一个约束条件知对偶问题无可行解,由此可知其原问题无最优解八、 最优对偶变量（影子价格）的经济解释由对偶定理可知,当达到最优解时,原问题和对偶问题的目标函数值相等。如果在得到最优解时，某种资源并未完全利用，其剩余量就是该约束中剩余变量的取值，那么该约束相对应的影子价格一定为零。因为在得到最优解时，这种资源并不紧缺，故此时再增加这种资源不会带来任何效益。反之，如果某种资源的影子价格大于零，就说明再增加这种资源的可获量，还回带来一定的经济效益，即在原问题的最优解中，这种资源必定已被全部利用，相应的约束条件必然保持等式。3.3对偶单纯形法一、 对偶单纯形法与单纯形法的区别单纯形法在整个迭代过程中，始终保持原问题的可行性，即常数列>0,而检验数C-CB-A（即C-YA）由有负分量逐步变为全部〉0（即B变为满足YA<C,Y是对偶问题的可行解），即同时得到原问题和对偶问题的最优解。对偶单纯形法在整个迭代过程中，始终保持对偶问题的可行性，即全部检验数>0，而常数列由有负分量逐步变为全部>0（即变为满足原问题的可行性），即同时得到原问题和对偶问题的最优解。二、 对偶单纯形法的求解步骤和计算举例给定一个初始对偶可行的基本解进行最优性检验若现行常数列b'>0,则停止计算。否则，转下步。确定换出变量将现行常数列b'中最小的负元素所在行的基变量换出确定换入变量最大负比值规则：在换出变量所在的第r行约束式中，找出各非基变量列中系数为负的那些元素，用相应的检验数。'分别除以这些负元j素，所得各负比值中最大者所在列即为换入列。以a'为主元素进行取主变换rk返回步骤2，继续迭代。三、 关于初始对偶可行的基本解构造扩充问题minz=CXX+XPx=bB jjjwRX>0其中R是非基变量下标的集合。再增加一个变量和一个约束条件，得到其扩充问题：minz=CXX+XPx=bB jjjWRx+乙x=Mn+1 jjwRx>0(i=1,2, ,n+1)i求扩充问题的初始对偶可行的基本解若基本解x(o)不是对偶可行的，即检验数中有负的，并假设负检验数B中最小的一个为Q，则以Q相应的变量x为换入变量，以x为换出k k k n+1变量，即以a 为主元素进行取主变换，可得到全部检验数>0，即m+1,k得到一个对偶可行的基本解。用对偶单纯形法求解扩充问题，并得到原问题的解答因为扩充问题的对偶问题有可行解，根据对偶原理可知，扩充问题或无可行解或有有限最优解。若扩充问题无可行解，则原问题也无可行解，若扩充问题得到最优解X（0=（x（0）,…,x（0）,x（O）），则X（0）=（x（0）,…,x（0））是原问题的可仃解。右扩充1 n n+1 1 n问题的目标函数最优值与M无关，则X（0）就是原问题的最优解。4.计算举例3.4灵敏度分析研究初始单纯型表上的系数变化对最优解的影响，研究这些系数在什么范围内变化时，原最优基仍是最优的；右原最优基不再是最优的如何用最简便的方法找到新的最优解。假定线性规划标准型最终表上已得到最优基B,最优结果为：-X■—B-1b—BX0N1- -1minz=CB-1bB、改变价值向量Cc'=c+Acrrr在最终表内，x是非基变量rC，z=CB-1P均不变；仅j变化。B j B j rJ'=c'一z=c+Ac一z=J+Acrrrrrrrr若j'>0，即Ac>-a，则最优解不变;若。’<0，则原最优基不再是最优的了。以x为换入变量，把最终表rr上的。换成厂，c换成C',继续用单纯形法求解。rrrr在最终表内，x是基变量rC要改变，并因此影响到各个检验数。B若max/a'Ia若max/a'Ia'<0 Ackjkjr<min/a'Ia'>。｝，则所有q'>0，kjkjj即最优解不变。若Ac超出上述允许变化范围，即有.<o，则以原最终表为基础，换rj上变化后的价值系数和检验数，继续迭代，可求出新的最优解。二、 改变限定向量bb'=b+Ab\x 〕 \x 〕max｛一册Id'>0\<Ab<min｛一 Id'<0\i〔d'irJriId'irJ

ir ir若Ab超过上述范围，则新得到的解为不可行解。但由于，的变化不rr影响检验数，故仍保持所有检验数>0，即满足对偶可行性。这时可在原最终表的基础上，换上改变后的右端常数及相应的一z值，用对偶单纯形法继续迭代，以求出新的最优解。三、 改变约束矩阵A1.非基向量列p改变为p'jj影响最终表上的第j列数据和第j个检验数。q'=c—CB-1PjjBj若q'>0，则原最优解仍是新问题的最优解。j若。’<0，则原最优基在非退化情况下不再是最优基。这时，应在原j最终表的基础上，换上改变后的第j列数据B-1P和b',把x作为换入jjj变量，用单纯形法继续迭代。2.基向量列P改变为p'jj重新计算四、 增加一个新的约束条件nXax<bm+1,jj m+1j=1AX<bm+1 m+1若原最优解满足这个新约束，则它就是新问题的最优解否则，引进松弛变量乂，有n+1(A)X+(A)X+x=b

m+1BBm+1NNn+1m+1(b-(A)B-1b)>0m+1 m+1B则现行对偶可行的基本解是新问题的可行解，亦即最优解(b-(A)B-1b)<0m+1 m+1B则在原最终表的基础上，增加新约束式的数据，通过矩阵行的初等变换，把原最终表上的各基向量列及新增列P化为单位阵，再用对偶n+1单纯形法继续求解。五、 增加一个新的变量对原问题最优解的可行性无影响。:c-CB-1Pn+1 B n+1，则原最优解就是新问题的最优解b<0n+1，须把b<0n+1n+1作为换入变量，按单纯形法继续迭代，得到新的最优解。第四章应用实例4.1产销平衡的运输问题mnminz=乙乙cxijij

i=1j=1n乙x=a(i=1,2,…・,m)ij ij=1为x=b(j=1,2,…,n)ij jx>0(i=1,2,…，m;j=1,2,…，n)ij由于产销平衡，有x111x121m乙ai=1x21x111x121m乙ai=1x21mnnmn=乙(乙x)=乙乙x=乙b

ijx22i=1xijj=1j=1i=1j=1xm2xmn较为简洁的求解方法—表上作业法不做要求）。另，可与整数规划结合而带来求解的方便。4.2套裁下料问题思路举例：某工厂要做100套钢架，每套用长为2.9m、2.1m和1.5m的元钢各一根。已知原料长7.4m,问应如何下料，可使所用原料最省。简单裁法将使料头数量增多，应使用套裁的方法。须先设计出若干种较好的套裁方案如下表,分设按各种方案下料的原料根数为x，可列写其数学模型：i长料7123452.9120102.1002211.531203合计7.47.37.27.16.6料头00.10.20.30.8minz=0x+0.1x+0.2x+0.3x+0.8xTOC\o"1-5"\h\z1 2 3 4 5x+2x+x=1001242x+2x+x=1003 4 53x+x+2x+3x=1001 2 3 5x>0且为整数(j=1,2, ,5)j汽油混合问题变量的选取，是模型设立的关键。逻辑关系的明晰，是模型设立的基础。购买汽车问题明晰乘和的关系，用数字等数学符号将文字的约束关系表达出来产品加工问题顺序理清方可使表达式明了。投资计划问题列举各可行计划，