运筹学课程讲义

1、运筹学课程讲义第一部分 线性规划第一章 线性规划的基本性质1.1 线性规划的数学模型一、线性规划问题的特点 胜利家具厂生产桌子和椅子两种家具。桌子售价 50 元/个，椅子售价 30 元 /个。生产桌子和椅子需木工和油漆工两种工种。生产一个桌子 需要木工 4 小时，油漆工 2小时。生产一个椅子需要木工 3 小时，油 漆工 1 小时。该厂每月可用木工工时为 120 小时，油漆工工时为 50 小时。问该厂如何组织生产才能使每月的销售收入最大？ max z 50x1 30x24x1 3x2 1202x1 x2 50x1,x2 0 例：某工厂生产某一种型号的机床。每台机床上需要2.9m、 2.1m、1.

2、5m的轴，分别为1根、2根和1根。这些轴需用同一种圆钢制作， 圆钢的长度为74m。如果要生产100台机床，问应如何安排下料，才 能用料最省？二、数学模型的标准型1. 繁写形式2. 缩写形式3. 向量形式4. 矩阵形式三、任一模型如何化为标准型？1. 若原模型要求目标函数实现最大化，如何将其化为最小化问题？2. 若原模型中约束条件为不等式，如何化为等式？若原模型中变量 xj 有上下界，如何化为非负变量？3. 若原模型中变量 xk 是自由变量，如何化为非负变量？max z5x16x27x3x1 5x23x3155x1 6x210x320x1 x2x35x1 0,x20,x3无约束令 x1'

3、 x1,x3 x3' x3'',x3' ,x3''0, Z1Z'1 1min z'5x1' 6x27x3'7x3''0x5Mx61x1' 5x21113x3' 3x3'' x4x61515x1' 6x210x3'10x3''x5201x1' x21x3'IIx3''x754.Mx7x1, x2 , x3, x3, x4 , x5 ,x6, x7 01. 2 图解法该法简单直观，平面作图适于求解二维问题。

4、使用该法求解线性规划问题时，不必把原模型化为标准型。一、图解法步骤1. 由全部约束条件作图求出可行域2. 作出一条目标函数的等值线3. 平移目标函数等值线，作图求解最优点，再算出最优值从图解法看线性规划问题解的几种情况1. 有唯一最优解2. 有无穷多组最优解3. 无可行解4. 无有限最优解（无界解）min z 6x1 4x?2x X213最优解（1,0），最优值33x1 4x222x1, x20直观结论：1）线性规划问题的可行域为凸集，特殊情况下为无界域（但有有限个顶点）或空集；2）线性规划问题若有最优解，一定可以在其可行域的顶点上得到。1.3线性规划的基本概念和基本定理一、 线性规划问题的基

5、与解可行解最优解基基向量非基向量基变量非基变量 基本解基本可行解最优基本可行解退化的基本解二、几何意义上的几个基本概念1. 凸集2. 凸组合3. 顶点三、线性规划问题的基本定理定理 1： 若线性规划问题存在可行域，则其可行域是凸集。引理 1：线性规划问题的可行解 X (x1,x2, ,xn)T 为基本可行解的充要 条件是 X 的正分量对应的系数列向量是线性无关的。定理 2： 线性规划问题的基本可行解对应于可行域的顶点。引理 2：K 是有界凸集，则任何一点 X K 可表示为 K 的顶点的凸组 合。定理 3：如果线性规划问题有有限最优解，则其目标函数最优值一定 可以在可行域的顶点上达到。四、求解线

6、性规划问题的基本思路 在有限个基本可行解中寻找最优基本可行解。 找一个基本可行解( m 个线性无关的系数列向量) ，由其换到另一个基本可行解。 实质即为换基。 前提是保证新的基本可行解的目标函数 值比原来的更优而不是更劣第二章 单纯形法它是求解线性规划最为成熟的算法。 胜利家具厂生产桌子和椅子两种家具。桌子售价 50 元/个，椅子售价 30 元 /个，生产桌子和椅子需要木工和油漆工两种工种。生产一个桌 子需要木工 4 小时，油漆工 2小时。生产一个椅子需要木工 3 小时， 油漆工 1 小时。该厂每月可用木工工时为 120 小时，油漆工工时为 50 小时。问该厂如何组织生产才能使每月的销售收入最

7、大？max z 50x1 30x24x1 3x2 1202x1 x2 50x1,x2 0将其变形，得4x1 3x2 x3 1202x1 x2 x4 50x1,x2,x3,x4 0基变量。原模型变形为将X3,X4对应的单位矩阵作为初始可行基。令X3,X4为基变量，Xi,X2为非maX z 50X130X2X3 120 4X1 3X2X450 2X1 X2X1,X2,X3,X40如果令非基变量Xi,X2等于零，得一个基本可行解(0, 0, 120, 50),对应的目标函数值 z = 0最优性检验：该解是否最优？显然不是。经济意义分析：X1,X2等于零意味着家具厂不开工生产,销售收入为零,资源未得到

8、充分利用。数学角度分析：非基变量X1,X2前的系数都为正，表明目标函数值有增加的可能。 只要将系数为正的非基变量与某一基变量对换， 当换入变 量的值增加时，目标函数值就可能增加。 换基迭代：寻找下一个可行解需要进行换基迭代。 换基后需满足：（1） 新的解仍是基本可行解； （2）目标函数得到改善。选择入基变量：Xi,X2系数均为正。对求目标函数极大化的问题，我们希望目标值增加得越快越好，因此应选系数最大的 X1入基。选择出基变量：X1入基后，其值从零增加并引起其他变量取值的变化。由问题的典则表达式和变量必须取正值的条件，得下列不等式关系：X3 120 - 4X1 -3X20X4 50-2X1 -

9、X2 0因迭代后X2仍为取零值的非基变量，上式可简化为120 4X1 050 2X1 0很明显，只有选 X1 min 120/4,50/2 25时，才能使上述不等式成立， 并使基变量X4变为零，正好满足非基变量必须为零的条件，所以可令X4出基，新的典则方程变为4X1 X3 1202X1 50 X23X2X4化简后得 X1 25 0.5X20.5X4X320 X2 2X4代入目标函数可得 z2 1250 5X2 25X4得到下一个基本可行解（ 25， 0， 20， 0），并完成了第一次迭代。新解是最优解吗？需进行最优检验。由于目标函数中X2的系数仍为正，说明多生产椅子仍有利可图，该解仍不是最优解

10、。再次迭代。x2 入基， x3 出基，换基后典则形式变为z3 1350 5x3 15x4x1 15 0.5x3 1.5x4x2 20 x3 2x4第三个基本可行解为（ 15，20，0，0），松弛变量都已为零，表明 资源已得到充分利用；非基变量在目标函数中的系数全为负值， 说明目标函数已无法进一步改善，因此该解已是最优解。2.1 单纯形法原理构造初始可行基1. 引入附加变量，把数学模型化为标准型2. 若约束条件中附加变量的系数是 -1或原约束即为等式， 则必须 引入人工变量，以构成初始可行基3. 目标函数中，附加变量的系数为0,而人工变量的系数为M （很大的正数）求出一个基本可行解1. 用非基变

11、量表示基变量和目标函数式4x1 3x28x3M2x1x3x4M 5 2x22x5x54 M x13Mx283Mx3Mx 4 Mx57M2. 求出一个基本可行解及相应的 z 值三、 最优性检验1. 最优性检验的依据 检验数2. 最优解判别定理：若在极小化问题中，对于某个基本可行解，所有检验数 j 0，且人工变量为 0，则这个基本可行解是最优 解。对于极大化问题，只要把上述定理中的 j 0 改成 j 0即可 这里的检验数j即为（Cj-Zj）。3. 无穷多最优解判别定理：若在极小化问题中，对于某个基本可 行解，所有检验数 j 0，又存在某个非基变量的检验数为 0， 且人工变量为 0，则线性规划问题有

12、无穷多最优解。4. 无可行解情况 若在极小化问题中，对于某个基本可行解，所有检验数 j 0， 但人工变量 0，则该线性规划问题无可行解。四、 基变换1. 基本可行解的改进定理2. 换入变量的确定3. 换出变量的确定最小非负比值规则=b r /a rk = min b i /aik |aik >0在单纯形法迭代中， 基变换带来可行域顶点的变换， 且相邻两 次迭代所对应的顶点也是相邻的。4. 无有限最优解（无界解）判定定理：若在极小化问题中，对于某个基本可行解，有一个非基变量的检验数k<0,但Pk列中没有正元素，且人工变量为 0，则线性规划问题无有限最优解（具有无界解）。2.2 单纯形

13、法的表格形式构造初始可行基，并计算检验数 jj =cj -zj乙=(Ci,C2,Cm)?Pj=(CB)?P'j二、从表中找到基本可行解和相应目标函数值三、最优性检验四、基变换1. 换入变量的确定负检验数中最小2. 换出变量的确定最小非负比值规则3. 主元素的确定 换入元素所在列和换出元素所在行交点处 的元素4. 取主变换 通过矩阵行的初等变换，把换入向量变换为单位列向量。即基 变换，亦即单纯形法的一次迭代。2. 3大M法和两阶段法根据处理人工变量的方法不同，单纯形法的两种常见形式 大 M 法也叫罚函数法，前已介绍。 两阶段法将线性规划问题的求解分为两个阶段。 第一阶段：判断原线性规划问

14、题是否有可行解。 该阶段所要求解的线性规划问题的约束条件即原问题的约束条件， 而 目标函数取全部人工变量之和，求其最小值。若求解结果是上述目标函数的最小值为 0，则说明所有人工变量都能 退出基，原问题有可行解， 且第一阶段的最终单纯型表上的基本可行 解就是原问题的一个基本可行解。若求解的结果是上述目标函数的最小值大于 0，则说明最终人工变量 不能完全退出基，原问题无可行解，应停止计算。第二阶段：求解原线性规划问题的最优解。 以第一阶段的最终单纯型表为基础， 去掉其中的人工变量列， 把目标 函数换成原问题的目标函数，并修正因Cj改变而改变的（Cb）T、 j和 -Z。以此作为第二阶段的初始表，继续

15、迭代，得原问题的最优解。438 000迭代次数CB T基变量x1x2x3 x4x5b18x32102113x220023192.4退化问题一、什么是退化 当基本解、基本可行解、最优基本可行解中有基变量为 0 时，即出现 了退化。退化情况下，即使存在最优解，也可能出现循环现象，即迭代过程总是重复解的某一部分序列， 目标函数值总是不变， 永远达不到最优解二、摄动法1. 摄动法简介 对线性规划原问题，为了避免退化情况下发生循环， 而使向量 b 摄动。2. 确定换出变量的步骤3. 举例三、勃兰特方法法则 1：在极小化问题中，如果有几个检验数（ cj-z j ）都是负的，那 么选其中下标最小的非基变量作

16、为换入变量。法则 2：在极小化问题中，根据最小非负比值规则确定换出变量时， 如果有几个比值同时达到最小比值， 那么选其中下标最小的基变量作 为换出变量。定理：只要在迭代时，遵循上述法则，就不会出现循环。3. 5 改进单纯形法 每次迭代只计算换入列、常数列及检验数行以提高计算效率。一、单纯形法的矩阵形式1. 用矩阵（分块）形式表示线性规划标准型把矩阵 A、 C、X 分别按“基”与“非基”分成两块A=(B,N)C=(C B ,CN )XXBXN其中B=(Pl , P2，Pm)N=(Pml , Pm 2，Pn )C B =( Cl ,C2,，Cm )C N =(C m 1 ,Cm 2 , ,Cn )

17、XBx1x2xmXNxm 1 xm 2xn将分块结果代入标准型，得BX B+NX N=bX B 0, X N 0min z CB XB+ CN X N2. 用矩阵（分块）形式表示基本解、目标函数值及检验数XB=B 1b- B 1 NXN z =CBB 1 b + (CN- CBB 1 N) XNN =C N - C B B N令 X N = 0 ， 可得 X B= B 1b z =CB B 1b3. 单纯型乘子 Y 。Y= C BB 1二、改进单纯形法的求解步骤1. 完成第 0 次迭代表。1 构造初始可行基，计算 B 1 。再利用公式01N0=C N0- CB0 B 01N0= CN0- CB

18、0 N 0 ，计算第 0次迭代表中的检验 数。确定换入向量为 Pk ，换出向量为 PBr ，主元素是 ark。令i二02. 计算 Bi 111) 构造基矩阵 Bi 12) 计算 Bi 11第一种方法：已知 Bi 1，用初等变换法求其逆矩阵 Bi11。 第二种方法：已知 Bi 1和第 i 次迭代表的换入列 P'k ，主元素为 a'rk ， 通过取主变换求出 Bi 11。3. 计算第 i +1 次迭代表的常数列和检验数。常数列二Bi1i boY二Cb Bi；4. 进行最优性检验如果Nil 0,且人工变量为0,则已经得到最优解。否则，转下步5. 计算第i + 1次迭代表中的换入列Pk

19、Pk= Bi1i Pk6. 确定第i +1次迭代表中换出向量的下标 Br 最小非负比值规则令i =i +1，返回步骤2。三、逆的乘积形式Bi11=EiEi 1 EE改进单纯形法的基本思想就是给定初始基本可行解后，通过修改旧基的逆来获得现行基的逆，进而完成单纯形法的其他运算。四、计算举例求 B31 :常数列B31Y3 CB3 ?B31 8,3 12 10 2,33 B3 3 2 1N3 CN 3 Y3N3c1c4c5c6c7Y3 P1P4P5 P6 P71 1 0 1 04 0 0 M M 2 30 0 1 0 1323223M第三章 线性规划的对偶原理3.1 线性规划的对偶问题一、对偶问题的提

20、出换位思考家具厂的线性规划问题， 该问题站在家具厂管理者的角度追求销售收入最大max z 50x1 30x24x1 3x2 1202x1 x2 50x1,x2 0某企业家有一批待加工的订单， 有意利用该家具厂的木工和油漆工资 源来加工他的产品。他需要与家具厂谈判付给该厂每个工时的价格。 如果该企业家已对家具厂的经营情况有详细了解， 他可以构造一个数 学模型来研究如何才能既让家具厂觉得有利可图，肯把资源出租给 他，又使自己付的租金最少。目标:租金最少；yi -付给木工工时的租金；y2 -付给油漆工工时的租金min w 120y1 50y2所付租金应不低于家具厂利用这些资源所能得到的利益1）支付相

21、当于生产一个桌子的木工、油漆工的租金应不低于生产一个桌子的收入4y1 2y2 502）支付相当于生产一个椅子的木工、油漆工的租金应不低于生产一个椅子的收入3y1 y2 303）付给每种工时的租金应不小于零y10,y2 0原问题与对偶问题的数学模型1. 对称形式的对偶原问题和对偶问题只含有不等式约束时， 一对对偶问题的模型是对称 的，称为对称形式的对偶。原问题：min z CXAX bX0对偶问题：maxw YbYA CY02. 非对称形式的对偶 若原问题的约束条件全部是等式约束（即线性规划的标准型） ，即 min z CXAX bX0则其对偶问题的数学模型为max w YbYA C丫是自由变量

22、可把原问题写成其等价的对称形式：min z =CXAX bAX bX0即min z =CXA X b AbX0设Y 1=(yi,y2,ym), Y2 = (ym+1,ym+2,y2m)。根据对称形式的对偶模型,写出上述问题的对偶问题：max w =(Yi,Y2) bbA(Y1,丫2) A cY1 0Y2 0即max w =( Y1-Y2) b( Y1-Y2)A CY1 0Y2 0令 Y= Y 1-Y2, 得对偶问题为：max w = YbYA CY 是自由变量原问题:对偶问题:min w5yi 4y2y3yi2y2 y32yi y2 iyi3y2 y33yi y3 iXi X2 X3 X452

23、xi X2 3x3 4XiX3 X4 1Xi,X30, X2 , X4 无约束yi 0, y无约束，y 03.原问题与对偶问题的对应关系原问题（或对偶问题）对偶问题（或原问题）目标函数min z目标函数max wn个变量n个约束变量0约束变量0约束自由变量约束二m个约束m个变量约束变量0约束变量0约束二自由变量约束条件的限定向量目标函数的价值向量目标函数的价值向量约束条件的限定向量maxz 2x1 x2 3x3 x4min z 3x1 2x2 3x3 4x4 x1 2x2 3x3 4x4 3原问题：x2 3x3 4x452x1 3x2 7x3 4x4 2Xi 0, X40,X2,X3 无约束m

24、axw 3y1 5y2 2y3 y1 2y3 3对偶问题：2y1 y2 3y323y1 3y2 7y334y1 4y2 4y3 4yi 0, y 0, y3无约束3.2 对偶问题的基本性质和基本定理一、对称性定理 对称性定理：对偶问题的对偶是原问题。二、弱对偶性定理弱对偶性定理：若X和丫 (0)分别是原问题和对偶问题的可行解，则 有 C X (0) Y(0)b。三、最优性定理最优性定理：若X(0)和丫(0)分别是原问题和对偶问题的可行解，且有 C X(0)= Y(0)b,贝y X(0)和丫 (0)分别是原问题和对偶问题的最优解。四、对偶定理 对偶定理：有一对对偶的线性规划问题， 若其一有一个有

25、限的最优解， 则另一个也有最优解， 且相应的目标函数值相等。 若任一个问题具有 无界解，则另一个问题无可行解。五、单纯型乘子 Y 的定理 单纯型乘子 Y 的定理：若线性规划原问题有一个对应于基 B 的最优 基本可行解，则此时的单纯型乘子 Y= C BB 1是相应于对偶问题的一 个最优解。六、对称形式对偶的互补松弛定理对称形式对偶的互补松弛定理： 若 X (0)和 Y (0)分别是原问题和对偶问 题的可行解，则 X (0)和 Y (0)都是最优解的充要条件是，对所有 i 和 j， 下列关系式成立：1. 如果 x (j0) >0，必有 Y(0)Pj =cj2. 如果 Y(0) Pj <

26、 cj ，必有 x (j0) =03. 如果 y i(0) >0，必有 A iX (0)=bi4. 如果AiXbi，必有y(0) =0其中Pj是A的第j列，Ai是A的第i行。互补松弛定理意味着：如果原问题最优解X(0)中第j个变量x(0)为正, 则其对偶问题中与之对应的第 j 个约束式在最优情况下必呈严格等式 (即其松弛变量为 0)；而如果对偶问题中第 j 个约束式在最优情况下 呈严格不等式，则原问题最优解X(0)中第j个变量x(j0)必为0。类似地, 如果对偶问题最优解Y(0)中第i个对偶变量y(0)为正，则其原问题中 与之对应的第 i 个约束在最优情况下必呈严格等式(即其剩余变量为

27、0)；而如果原问题中第 i 个约束在最优情况下呈严格不等式，则对偶 问题最优解Y (0)中第i个对偶变量y(0)必为0。互补松弛性： YXS 0 YSX 0 X,Y 为最优解对一对对偶规划的最优解而言， 如果对应某一约束条件的对偶变量的值为非零，则该约束条件取严格等式；反之，如果某个约束条件 取严格不等式，则其对应的对偶变量一定为零。七、非对称形式对偶的互补松弛定理非对称形式对偶的互补松弛定理：若X (0)和丫 (0)分别是原问题和对偶问题的可行解，则X(0)和丫都是最优解的充要条件是，对所有 j，下列关系式成立：1. 如果 x(j0)>0，必有 丫 Pj 二Cj2. 如果丫(0) Pj

28、< Cj，必有 x(0) =0maxz x1 x2例：已知线性规划问题x1x2x32x1x2x3x1, x2 , x3试用对偶理论证明上述线性规划问题无最优解该问题存在可行解，如 X (0,0,0)又对偶问题为minw 2y1 y2 y1 2y2 1y2 y2 1y1 y2 0y1,y2 0由第一个约束条件知对偶问题无可行解， 由此可知其原问题无最优解八、最优对偶变量(影子价格)的经济解释由对偶定理可知， 当达到最优解时， 原问题和对偶问题的目标函数值相等。如果在得到最优解时， 某种资源并未完全利用， 其剩余量就是该约束 中剩余变量的取值， 那么该约束相对应的影子价格一定为零。 因为在

29、得到最优解时， 这种资源并不紧缺， 故此时再增加这种资源不会带来 任何效益。反之， 如果某种资源的影子价格大于零，就说明再增加这 种资源的可获量， 还回带来一定的经济效益， 即在原问题的最优解中， 这种资源必定已被全部利用，相应的约束条件必然保持等式。3.3 对偶单纯形法一、对偶单纯形法与单纯形法的区别 单纯形法在整个迭代过程中，始终保持原问题的可行性，即常数列0,而检验数C-CbB 1A（即C-YA）由有负分量逐步变为全部0 （即变为满足 YA C， Y 是对偶问题的可行解） ，即同时得到原问题和对 偶问题的最优解。对偶单纯形法在整个迭代过程中, 始终保持对偶问题的可行性, 即全 部检验数

30、0,而常数列由有负分量逐步变为全部 0（即变为满足原 问题的可行性）,即同时得到原问题和对偶问题的最优解。二、对偶单纯形法的求解步骤和计算举例1. 给定一个初始对偶可行的基本解2. 进行最优性检验若现行常数列 b' 0,则停止计算。否则,转下步。3. 确定换出变量 将现行常数列 b' 中最小的负元素所在行的基变量换出4. 确定换入变量 最大负比值规则：在换出变量所在的第 r 行约束式中，找出各非基变 量列中系数为负的那些元素，用相应的检验数'j 分别除以这些负元素，所得各负比值中最大者所在列即为换入列。5. 以a；k为主元素进行取主变换返回步骤 2，继续迭代。三、关于初

31、始对偶可行的基本解1. 构造扩充问题min z CXX BPj x jbjRX0其中 R 是非基变量下标的集合。 再增加一个变量和一个约束条件，得到其扩充问题：min z CXX BPj xjbjRxn 1xj MjRxi0(i 1,2, ,n 1)2. 求扩充问题的初始对偶可行的基本解若基本解 XB(0) 不是对偶可行的，即检验数中有负的，并假设负检验数中最小的一个为k，则以k相应的变量Xk为换入变量，以Xn 1为换出变量，即以ami,k为主元素进行取主变换，可得到全部检验数0,即得到一个对偶可行的基本解3. 用对偶单纯形法求解扩充问题，并得到原问题的解答因为扩充问题的对偶问题有可行解， 根

32、据对偶原理可知，扩充问题或 无可行解或有有限最优解。若扩充问题无可行解，则原问题也无可行解，若扩充问题得到最优解 x（o X0）,妒乂0）1）,则x（o）（xi0）, ,xno）是原问题的可行解。若扩充 问题的目标函数最优值与 M无关，则X（0）就是原问题的最优解。4. 计算举例3.4灵敏度分析研究初始单纯型表上的系数变化对最优解的影响，研究这些系数在什么范围内变化时，原最优基仍是最优的；若原最优基不再是最优的， 如何用最简便的方法找到新的最优解。假定线性规划标准型最终表上已得到最优基B，最优结果为：Xb = B 1bXn 01min z CB B b一、改变价值向量CC r CrCr1. 在

33、最终表内，Xr是非基变量Cb，Zj CbB 1Pj均不变；仅r变化rC rC rZ rrC r若r 0，即Crr，则最优解不变;若r 0，则原最优基不再是最优的了。以Xr为换入变量，把最终表 上的r换成；，Cr换成c；,继续用单纯形法求解。2.在最终表内，Xr是基变量Cb要改变，并因此影响到各个检验数。若 max j/akj|aq 0c； min -Ja | a'kj 0，则所有 j 0 ,即最优解不变。若Cr超出上述允许变化范围，即有j 0，则以原最终表为基础，换上变化后的价值系数和检验数，继续迭代，可求出新的最优解。二、改变限定向量bb' b bX Bi'X Bi&

34、#39;max -1 dir 0br min- | dir 0idiridir若br超过上述范围，则新得到的解为不可行解。但由于br的变化不影响检验数，故仍保持所有检验数0,即满足对偶可行性。这时可在原最终表的基础上，换上改变后的右端常数及相应的z值，用对偶单纯形法继续迭代，以求出新的最优解。三、改变约束矩阵A1.非基向量列Pj改变为Pj'影响最终表上的第j列数据和第j个检验数。 j Cj CbB 1Pj'若j 0，则原最优解仍是新问题的最优解。 若 'j 0 ，则原最优基在非退化情况下不再是最优基。这时，应在原 最终表的基础上，换上改变后的第j列数据B 1P；和j，把

35、Xj作为换入 变量，用单纯形法继续迭代。2. 基向量列 Pj 改变为 Pj'重新计算四、增加一个新的约束条件nam 1,j xj bm 1j1即Am 1X bm 1若原最优解满足这个新约束，则它就是新问题的最优解。 否则，引进松弛变量 xn 1，有(Am 1)B X B (Am 1)N X N xn 1 bm 1若仏1 (Am1)BB 1b) 0则现行对偶可行的基本解是新问题的可行解，亦即最优解。若(bm 1 (Am1)BB 1b)<0则在原最终表的基础上， 增加新约束式的数据， 通过矩阵行的初等变 换，把原最终表上的各基向量列及新增列 Pn 1化为单位阵，再用对偶 单纯形法继续

36、求解。五、增加一个新的变量对原问题最优解的可行性无影响。n 1 cn 1 CBB Pn 1若n 1 0，则原最优解就是新问题的最优解。若n 1 0 ，须把 B 1Pn 1 加入到原最终表内，并以新变量xn 1作为换入变量，按单纯形法继续迭代，得到新的最优解第四章应用实例4.1产销平衡的运输问题m nmin zq Xi 1 j 1nXijai(i 1,2,m)j 1mXijbj(j 1,2,n)i 1Xj0(i1,2,m; j 1,2, ,n)由于产销平衡，有X111X121maii 1Xm1mn(Xij )i 1 j 1n mXijj 1 i 1X2n1nbjj 1卜m行Xm1Xm2XmnX2

37、11X2211 11111111n行111较为简洁的求解方法表上作业法（不做要求）。另，可与整数规划结合而带来求解的方便。4.2套裁下料问题思路举例：某工厂要做100套钢架，每套用长为2.9m、2.1m和1.5m的元钢各一 根。已知原料长7.4m，问应如何下料，可使所用原料最省。简单裁法将使料头数量增多，应使用套裁的方法。须先设计出若干种较好的套裁方案如下表，分设按各种方案下料的原料根数为Xi，可列写其数学模型:长料方根案123452.9120102.1002211.531203合计7.47.37.27.16.6料头00.10.20.30.8min z 0x10.1x20.2x30.3x40.8x5x1 2x2 x41002x3 2x4 x51003% x2 2x3 3x5100Xj0且为整数(j 1,2, ,5)4.3汽油混合问题变量的选取，是模型设立的关键。逻辑关系的明晰，是模型设立的基础。4.4购买汽车问题明晰乘和的关系，用数字等数学符号将文字的约束关系表达出来。4.