线性规划与对偶理论

1、第二部分线 性 规 划Linear Programming LP1主要内容 ：学习数学规划的建模，提高分析问题的能力掌握线性规划的标准型、图解法掌握线性规划的单纯形法、对偶理论掌握影子价格的意义了解灵敏度分析的目的/2第一节 （LP）模型的建立及标准形式一、由实际问题出发，建立（LP）模型LP主要解决的问题：例如： 产品的最优组合 生产排序 最优投资方案 人力资源分配 /稀缺资源在竞争中如何进行最优分配。3模型的四个要点： 真实性 简明性 完整性 规范性/ 4规划论模型包含的三个方面：1、设计方案：利用变量 x1 , x2 ,x n 表示方案，称为设计变量或决策变量。2、目标（方案好坏的评价标

2、准）：一般表示为决策变量的函数 f (x1 ,x n )，称为目标函数，用Max ( Min ) 表示最优。3、限制条件（客观条件对方案的限制）：一般表示为决策变量的不等式方程，称为约束方程。 /5规划论模型的数学表示：x1 , x2 ,x n ，Max ( Min ) Z = f (x1 ,x n )g 1 (x1 ,x n ) ( , = ) b 1g m (x1 ,x n ) ( , = ) b ms.tLP只是规划论中的一种。 /6规划论中不同规划的主要区别： 函数若目标函数与约束方程中的函数均为线性函数， 线性规划若目标函数与约束方程中的函数有非线性函数， 非线性规划若设计变量要求取

3、整数， 整数规划 若设计变量要求只取 ( 0, 1 )， 0 -1规划 若函数中引入时间参数, 动态规划另：若目标有多个, 多目标规划/7线性与非线性的区别：线性函数：函数为多元一次。表达式： a1 x1 + a2 x2 + + an xn x1f(x1)2维(一元)x1f(x1 , x2)3维(二元)x2不是线性的函数，均称为非线性函数。例如： 2 x12 + 3 x1x2x1f(x1)2维(一元)x1f(x1 , x2)3维(二元)x28函数不是线性的规划问题例：把半径为R的实心金属球熔化后， 铸成一个实心圆柱体，问：圆柱体取什么尺寸， 才能使它的表面积最小？ /R9解：设计变量：设圆柱体

4、的底面半径为x1 ，高为x2Rx1x2目标函数：M in (圆柱体表面积 )= (两个底面积) + (侧面积)= 2x12 + 2x1x2约束方程：V圆柱 = V 圆球s.tx12 x2 = 4/3 R3 x1，x2 010二、（LP）模型的种类（1）(引论中的例1)2x2 + 4x3 +5x4 + 7x5 704 x1 + 3x2 + 2x3 + x4 9 0s.t x i 0 i =15Min Z = x1 + x2 + x3 + x4 + x5（2）(引论中的例2)s.tx1 + 140 156x2 120 x1 + 1600 1380 x2 10 x1 4000 x2 3000 x1

5、+ x2 5000 x1 ， x2 0Max Z = 20 x 1 + 30 x 211例3 (运输最优调配问题)某矿区有四座冶炼厂和三座选矿厂，三座选矿厂选出的精矿分别送到四座冶炼厂冶炼。冶炼厂年处理精矿能力、选矿厂年生产精矿能力以及精矿运费如表：冶炼厂选矿厂运费 (元/T)A B C D 生产量 ( T )甲乙丙处理量 ( T )1.5 2.0 0.3 3.0 10007.4 0.8 1.4 2.0 8001.2 0.2 2.0 2.5 500500 700 800 300问：如何调配精矿，使运费最低？ /2300230012建模：设计变量：设第i 选矿厂向第 j 冶炼厂调配精矿xi j

6、(T) 。 i =1, 2, 3 (甲,乙,丙)， j = 1, 2, 3, 4 (A,B,C,D) A B C D甲乙丙 x11 x12 x13 x14x21 x22 x23 x24x31 x32 x33 x34目标函数：总运费 最少A B C D甲乙丙1.5 2.0 0.3 3.07.4 0.8 1.4 2.01.2 0.2 2.0 2.5M in Z = 1.5 x11 + 2.0 x12 + 0.3x13 + 3.0 x14 1.2 x31 + 0.2x32 + 2.0 x33 + 2.5x34约束方程：s.tA B C D 生产量甲乙丙处理量 1000 800 500500 700

7、800 300 x11 x12 x13 x14x21 x22 x23 x24x31 x32 x33 x34产量约束x11 + x12 + x13 + x14 = 1000 x21 + x22 + x23 + x24 = 800 x31 + x32 + x33 + x34 = 500处理量约束x11 + x21 + x31 = 500 x12 + x22 + x32 = 700 x13 + x23 + x33 = 800 x14 + x24 + x34 = 300 xi j 0 i =1, 2, 3， j = 1, 2, 3, 4 /13Min Z = 1.5 x11 + 2.0 x12 + 0

8、.3x13 + 3.0 x14 1.2 x31 + 0.2x32 + 2.0 x33 + 2.5x34s.tx11 + x12 + x13 + x14 = 1000 x21 + x22 + x23 + x24 = 800 x31 + x32 + x33 + x34 = 500 x11 + x21 + x31 = 500 x12 + x22 + x32 = 700 x13 + x23 + x33 = 800 x14 + x24 + x34 = 300 xi j 0 i =1, 2, 3， j = 1, 2, 3, 42x2 + 4x3 +5x4 + 7x5 704 x1 + 3x2 + 2x3

9、+ x4 90s.t x i 0 i =15Min Z = x1 + x2 + x3 + x4 + x5s.tx1 + 140 156x2 120 x1 + 1600 1380 x2 10 x1 4000 x2 3000 x1 + x2 5000 x1 ， x2 0Max Z = 20 x 1 + 30 x 214s.t x i 0 i = 1n / Min ( Max ) Z = c1 x1 + c2 x2 + + cn xn（3）（LP）模型的一般形式a i 1 x1 + a i 2 x2 + + a i n xn b i ( i = 1 m1)a j1 x1 + a j2 x2 + +

10、a jn xn b j ( j = m1+1 m2)a k 1 x1 + a k 2 x2 + + a k n xn = bk ( k = m2+1 m)15三、 （LP）模型的标准形式 要求右端项 b j 0 j = 1m /（LP）s.ta 1 1 x1 + a 1 2 x2 + + a 1 n xn = b 1a 2 1 x1 + a 2 2 x2 + + a 2 n xn = b 2 a m 1 x1 + a m 2 x2 + + a m n xn = b m x i 0 i = 1nMax Z = c1 x1 + c2 x2 + + cn xn16模型的矩阵表示:决策变量 X =（x

11、1, x2 , , x n ) T (列向量)目标系数 c = ( c1, c2 , , c n ) T (列向量)右端项 b = ( b1 , b2 , , b m )T (列向量)约定 nm, 系数矩阵 A = = ( a i j ) m x n （ i = 1 m，j = 1 n ）a 1 1 a 1 2 a 1 n a 2 1 a 2 2 a 2 n a m 1 a m 2 a m n 记：R(A) = m (满秩矩阵) ,且 b0 /17模型的简化表示:（LP） AX = b X0 /Max Z = cTXMax Z = (c1 c2 cn)（LP） x1 x2 xn x1 x2 x

12、n a 1 1 a 1 2 a 1 n a 2 1 a 2 2 a 2 n a m 1 a m 2 a m nb 1b 2 b m= x1 x2 xn 0 0 0即：18四、模型的标准化1、极小化模型的改写：即：把 Min Z = cTX 改写成 Max Z = cTX Min Z = - Max (- Z) X y- ZX*Max ZMin 令 Z= - Z于是得到： Max Z= - cTX 注意： Z* = - Z* / 192、不等式约束的改写：(1) “”的改写：a i 1 x1 + a i 2 x2 + + a i n xn b i添加一个非负变量xn+1 使a i 1 x1 +

13、a i 2 x2 + + a i n xn + xn+1 = b i松驰变量(2) “”的改写：a j1 x1 + a j2 x2 + + a jn xn b j减去一个非负变量xn+2 使a j1 x1 + a j2 x2 + + a jn xn - xn+2 = b j剩余变量203、决策变量非正的改写：(1) “”的改写：若 x i 0 则令：y i = - x i 并代入模型中(2) 自由变量的改写：若 x j 为自由变量则令：x j = u v 且 u 0 ，v 0 并代入模型中/21标准化的例：（以引论中例1 为例）Min Z = x i 5i=1s.t非标准，通过减去剩余变量使

14、变 非标准，通过减去剩余变量使 变 X6 , X7 为剩余变量。这里的剩余变量有何经济解释？对目标函数的影响？目标非标准令：Z = - ZMax Z = - x i 5i=14 x1 + 3x2 + 2x3 + x4 90- x6 902x2 + 4x3 +5x4 + 7x5 70 - x7 70 x i 0 且为整数 i =15, 6, 7+0 x6 +0 x722目标：余料总长 最少s.t4 x1 + 3x2 + 2x3 + x4 902x2 + 4x3 +5x4 + 7x5 70 x i 0 且为整数 i =15Min Z = 20 x1+10 x2 + 0 x3 + 30 x4 + 2

15、0 x5 这里的剩余变量对目标函数有无影响？+ x6 + x74 x1 + 3x2 + 2x3 + x4 - x6 902x2 + 4x3 +5x4 + 7x5 - x7 70 x i 0 且为整数 i =15, 6, 7Max Z = - 20 x1 - 10 x2 - 0 x3 - 30 x4 - 20 x5 - x6 - x723s.t（以引论中例2 为例） Max Z = 20 x 1 + 30 x 2目标标准x1 + 140 156x2 120非标准，通过增加松弛变量使 变 x1 + 1600 1380 x2 10非标准，通过增加松弛变量使 变 + x3 120 + x4 10 x1

16、 4000非标准，通过增加松弛变量使 变 + x5 4000 x2 3000非标准，通过增加松弛变量使 变 + x6 3000 x1 + x2 5000非标准，通过增加松弛变量使 变 + x7 5000 x1， x2， x3， x4， x5， x6， x7 0X3 X7 为松驰变量。这里的松弛变量有何经济解释？ /24例Max Z = 5x1 + 7 x2 2x1 + 5x2 60 x1 0 ，x2 自由s.tMax Z =s.t令： y1 = x1 x2 = y2 y3+ 5y1 2y1+ 7y2 7y3y1 ， y2 ， y3 ， y4 0+ 5y2 5y3+ y4= 6025最优解满足的

17、 X 称为 最优解 。 /一、可行解与最优解满足的 X 称为 可行解第二节 （LP）的图解法在线性规划模型（LP）中： Max Z = cTX ( LP ) AX = b X0 s.t26二、图解法举例s.t Max Z = 2x1 + 5x2 x1 + x2 4 （1） -x1 + 2x2 2 （2） x1 - x2 2 （3） x1，x2 0 （4）(1)、(2)、(3)、(4) 的边界线（直线）围成一个凸多边形 可行域。目标函数 Z 取不同值 Zi 形成一个平行直线族 等高线。27如何使用图解法？1、 画出可行域；2、 画出等高线，确定最优方向；3、 找出最优点；4、 求出最优解及最优值

18、。 /28s.t Max Z = 2x1 + 5x2 x1 + x2 4 （1） -x1 + 2x2 2 （2） x1 - x2 2 （3） x1，x2 0 （4）（1）x1 + x2 4L1： x1 + x2 4(0,0) 满足(1)，(1)含原点。x1 0 4 x2 4 0（2） -x1 + 2x2 2 L2： -x1 + 2x2 2 (0,0) 满足(2)，(2)含原点。x1 0 4 x2 1 3（3） x1 - x2 2 L3： x1 - x2 2 (0,0) 满足(3)，(3)含原点。x1 2 4 x2 0 2目标 Z = 2x1 + 5x2Z1 = 2x1 + 5x2 = 1x1

19、1/2 3x2 0 -1Z2 = 2x1 + 5x2 = 2x1 1 x2 0 图解法求解步骤:29 X1 X21 2 3 4 5 6 4 3 2 1 0-1-2图解法(0,4)(4,0)L1(0,1)(4,3)L2(4,2)(2,0)L3BCDAO(1/2,0)(3,-1)Z1 = 1(1,0)Z2 = 2max Z *计算B点坐标，B点位于L1与L2的交点处 x1 + x2 = 4 -x1+ 2x2 = 2X* = ( 2, 2 ) TZ* = 22 + 52 = 14最优点30 X1 X21 2 3 4 5 6 4 3 2 1 0-1-2L1L2L3BCDA另一种情况1：Z1 = 1Z2

20、 = 2max Z *BC线段上的点均为最优点，即有无穷多最优解。最优点集最优解集= (x1, x2) | x2 4- x1 2x1 3 (2, 2)(3, 1)31 X1 X21 2 3 4 5 6 4 3 2 1 0-1-2L1L2Z1 = 1max找不到最优点！即无最优解。 /另一种情况2：Z2 = 232 X1 X21 2 3 4 5 6 4 3 2 1 0-1-2L1L2另一种情况3：没有可行解！更不可能有最优解！ /33三、图解法的启示（LP）的最优解可能有： 唯一解； 无穷多解； 无解。（LP）的最优解若存在，则可能在约束域（凸多面体）的某个（些）顶点（极点）处达到。34第三节

21、单纯型算法 （Simplex Method） 从图解法的启示出发，做理论建设工作，要解决：（LP）可行域顶点的解析计算； 最优解的存在性； 建立有效的计算方法（算法）。美国运筹学家，斯坦福大学运筹学系教授，Dantzig 于 1946 年解决了上述问题。 /35一、基解与基可行解先考虑（LP）中的约束方程 ，即 A X = b由于 R(A) = m (n ) ，故有无穷多个解。记 A =（P1 P2 P n）其中 Pi 表示 X i 的系数列向量。a 1 ia 2 i a m iP i =因此 A X = b 可表示为： P1 x 1 + P2 x 2 + + P n x n = b 36如果

22、A中存在一个 “ m阶 ” 的方阵 B，另记 N =（ P m+1 P m+2 P n ）， N中的列称为非基列， 对应的变量称为非基变量 XN =（x m+1, , x n ) T 。P1 x 1 + + P m x m + P m+1 x m +1 + + P n x n = b不失一般性，记 B = ( P1 P2 P m )则称 B 为一个基（Basic）， B中的列称为基列， 对应的变量称为基变量 XB =（x1, , x m ) T ；且 R ( B ) = m，37则 AX = b 可表示为： B XB + N XN = b 令非基变量 XN = 0，则 AX = b 可等价为：

23、 B XB = b且有唯一解 XB ，称解 X = ( XBT , XNT ) T = ( XBT, 0 ) T 为（LP）对应于基 B的 基解 (Basic Solution) 。易知，基解最多有 C m 个。 n38（P1 P2 P n）n 列取 m 列进行组合，有 C m 个取法。 n那是否就一定有 C m 个基及基解呢? n不一定！例： 1 2 1 4 3 0 2 8C m = C 2 = n 4 4 ! ( 4 - 2 ) ! 2 ! = 61 23 0B1 =1 13 2B2 =1 43 8B3 =2 10 2B4 =2 40 8B5 =1 42 8B6 =39利用图解法中的例，了

24、解基解在几何中的对应关系基解最多有 C m = C 3 n 5 5 !( 5 - 3 ) ! 3 != = 10个 x1 + x2 + x3 4 -x1 + 2x2 + x4 2 x1 - x2 + x5 2s.t40 X1 X2BCDAOH2H3H4H5H1X (1) = ( 0,0,4,2,2 ) T O 点，X (2) = ( 0,4,0,-6,6 ) T H1点，X (3) = ( 0,1,3,0,3 ) T A 点，X (4) = ( 0,-2,6,6,0 ) T H2点，X (5) = ( 4,0,0,6,-2 ) T H3点，X (6) = (-2,0 ,6,0,4 ) T H4

25、点，X ( 7) = ( 2,0,2,4,0 ) T D 点，X (8) = ( 2,2,0,0,2 ) T B 点，X (9) = ( 3,1,0,3,0 ) T C 点，X (10) = (6,4,-6,0,0 ) T H5点。B1 =（P3 P4 P5） 1 0 0 = 0 1 0 0 0 1非基列( P1 P2 )( P1 P3 )( P1 P4 )( P1 P5 )( P2 P3 )( P2 P4 )( P2 P5 )( P3 P4 )( P3 P5 )( P4 P5 )B2 =（P2 P4 P5） 1 0 0 = 2 1 0 -1 0 1B3 =（P2 P3 P5） 1 1 0 =

26、 2 0 0 -1 0 1B4 =（P2 P3 P4） 1 1 0 = 2 0 1 -1 0 0B5 =（P1 P4 P5） 1 0 0 = -1 1 0 1 0 1B6 =（P1 P3 P5） 1 1 0 = -1 0 0 1 0 1B7 =（P1 P3 P4） 1 1 0 = -1 0 1 1 0 0B8 =（P1 P2 P5） 1 1 0 = -1 2 0 1 -1 1B9 =（P1 P2 P4） 1 1 0 = -1 2 1 1 -1 0B10 =（P1 P2 P3） 1 1 1 = -1 2 0 1 -1 0A =（P1 P2 P3 P4 P5） = 1 1 1 0 0-1 2 0

27、1 0 1 -1 0 0 141结论：如果基解 X ，且满足，即 X 0，则此基解 X 称为基可行解。上例中，基可行解有： X(1)，X(3)，X(7)，X(8)，X(9)分别与约束域顶点 O，A，D，B，C 对应。基解不一定是可行解。 X1 X2BCDAOH2H3H4H5H1即基可行解与（LP）约束域顶点： 构成了一一对应关系。 /42最优解2、若 最优解 存在， 经严格的数学证明，可以得出如下结果：定理1 线性规划（LP）的基可行解与其约束域的顶点构成一一对应。定理2 对于线性规划（LP）问题：1、若存在一个可行解，则一定存在基可行解；二、基本定理则一定在某个（些）基可行解处达到。 /43

28、各解之间的关系：解集可行解不可行解基解基可行解最优解最优解（如果存在）44三、寻找最优解算法的思路基可行解基可行解基解基可行解 最优解基可行解基解基解寻找初始基可行解是否最优?如何判断?怎样寻找下个基解?1. 要比原来的好2. 要可行45例：某厂在某计划期内要安排生产甲、乙两种产品，这些产品分别需要在A、B、C、D四种不同的设备上加工。按工艺规定，每种产品在设备上所需的加工台时数，设备在计划期内的有效台时数，以及每种产品的单位产品盈利如表：单位产品需设备台时数设备A B C D单位产品盈利产品甲乙有效台时数 2 1 4 0 2 2 2 0 4 312 8 18 12问：如何安排这两种产品的生产

29、，使获得的总盈利额为最多？ /462 x1 2 x2 x3 12 x1 2 x2 x4 84 x1 x5 18 4 x2 x6 12 xi 0 i =1, 2, 3, 4, 5, 6 Max Z = 2 x1 3 x2s.t建模、标准化：下面利用消去法来寻找求解思路 /47首先要找到一个(随便哪个)(初始的)基可行解：由于 x3 , x4 , x5 , x6 的系数矩阵为单位阵，显然满秩，可作为基，因此 x3, x4, x5, x6可作为基变量！该基解如何求？如何保证它是基可行解？将上述方程进行调整，将非基变量移至等式右端：x3 12 ( 2 x1 2 x2 )x4 8 ( x1 2 x2 )

30、x5 18 ( 4 x1 )x6 12 ( 4 x2 ) 此处均 0，称为正消去系统 （保证 x i 0） /1 0 0 00 1 0 00 0 1 00 0 0 12 x1 2 x2 x3 12 x1 2 x2 x4 84 x1 x5 18 4 x2 x6 12 xi 0 i =1, 2, 3, 4, 5, 648x3 12 ( 2 x1 2 x2 )x4 8 ( x1 2 x2 )x5 18 ( 4 x1 )x6 12 ( 4 x2 )该基可行解是否使目标达到最优？怎样判断？如果没有达到最优，怎样寻找下一个基可行解？经济含义:x1 = 0，x2 = 0，即产品甲、乙均不生产，设备A、B、C

31、、D均富余，此时利润为 0。最优性判断：未达最优！ 因目标函数 Z中x1 , x2 的系数均为正。即若其中任意一个适当生产，皆可产生利润。（称目标系数 c1 ,c2 为检验数） /即得初始基可行解 X ( 0 ) = ( 0,0,12,8,18,12 ) T 初始目标值 Z( 0 ) = 2 x1 + 3 x2 = 0基可行解的求法： 令非基变量 x1 = 0， x2 = 0 可得基变量 x3 =12，x4 = 8，x5 = 18，x6 = 1249目标值 Z( 0 ) = 2 x1 + 3 x2 = 0X ( 0 ) = ( 0,0,12,8,18,12 ) T 检验数若检验数0，目标值有上

32、升的可能！为使目标函数值上升，让检验数为正的变量进基！（使其0）（为升得快，取检验数最大的！）即让x2进基成为基变量，（其含义为：生产乙产品）由于基变量个数固定，一个进基就应有一个离基。所以原基变量将有一个离基，成为非基变量。（其含义为：尽量多的生产乙产品，直到使某种资源用完为止。） /50 x3 12 ( 2 x1 2 x2 )x4 8 ( x1 2 x2 )x5 18 ( 4 x1 )x6 12 ( 4 x2 )寻找下一个基可行解 ( 使x2 进基 ) ：先使x2的系数均为+1:1/2 x3 6 ( x1 x2 )1/2 x4 4 (1/2 x1 x2 ) x5 18 ( 4 x1 )1/

33、4 x6 3 ( x2 )保留一个x2，消去其他方程的x2 。注意：为使某一个方程的x2 移入左边进基，在消去其他方程的x2 时，还要使该方程仍为正系统。为了达到此目的，选右端项（比值）最小的方程。（保证可行性！） /511/2 x3 6 ( x1 x2 )1/2 x4 4 (1/2 x1 x2 ) x5 18 ( 4 x1 )1/4 x6 3 ( x2 )消去其他方程的x2 ： 1/4 x6 3 ( x2 )x5 18 ( 4 x1 )1/2 x4 1/4 x6 1 (1/2 x1 )1/2 x3 1/4 x6 3 ( x1 )x2 移入左边进基， x6 移入右边离基：1/2 x3 3 (

34、x1 1/4 x6 )x3 6 ( 2 x1 1/2 x6 )1/2 x4 1 (1/2 x1 1/4 x6 )x4 2 ( x1 1/2 x6 )x5 18 ( 4 x1 )x2 3 ( 1/4 x6 )52求出新的基可行解： 令非基变量 x1 = 0， x6 = 0 可得基变量 x3 = 6，x4 = 2，x5 = 18，x2 = 3即得新基可行解 X ( 1 ) = ( 0, 3, 6, 2, 18, 0 ) T 新的目标值 Z( 1 ) = 2 x1 + 3 x2 = 9经济含义:生产产品乙，且将资源D全部用尽。目标值为 Z (1) = 9，效益已有提升！但，是否达到最优？怎样检验？改

35、写目标函数，利用约束方程消去 x2 ，可得新目标函数值：Z = 2 x1 + 3 ( 3 - 1/4 x6 ) = 9 + ( 2 x1 - 3/4 x6 ) 最优性判断：仍未达最优！（为什么？如何办？） /Z = 2 x1 + 3 x2x3 6 ( 2 x1 1/2 x6 )x4 2 ( x1 1/2 x6 )x5 18 ( 4 x1 )x2 3 ( 1/4 x6 )53寻找下一个基可行解 ( 使x1 进基 ) ：先使 x1的系数均为+1:1/2 x3 3 ( x1 1/4 x6 ) x4 2 ( x1 1/2 x6 )1/4 x5 9/2 ( x1 ) x2 3 ( 1/4 x6 )保留一

36、个x1，消去其他方程的x1 。注意：为保证可行性， 选右端项（比值）最小的方程，保留x1 。 /x3 6 ( 2 x1 1/2 x6 )x4 2 ( x1 1/2 x6 )x5 18 ( 4 x1 )x2 3 ( 1/4 x6 )54消去其他方程的x1 ：1/2 x3 3 ( x1 1/4 x6 ) x4 2 ( x1 1/2 x6 )1/4 x5 9/2 ( x1 ) x2 3 ( 1/4 x6 ) x2 3 ( 1/4 x6 )1/4 x5 x4 5/2 ( 1/2 x6 ) x4 2 ( x1 1/2 x6 )1/2 x3 x4 1 ( 1/4 x6 )x1 移入左边进基， x4 移入右

37、边离基：1/2 x3 1 ( - x4 1/4 x6 )x1 2 ( x4 1/2 x6 )1/4 x5 5/2 (- x4 1/2 x6 )x2 3 ( 1/4 x6 )x3 2 ( - 2 x4 1/2 x6 )x5 10 (- 4x4 2 x6 )55x1 2 ( x4 1/2 x6 )x2 3 ( 1/4 x6 )x3 2 ( - 2 x4 1/2 x6 )x5 10 (- 4x4 2 x6 )求出新的基可行解： 令非基变量 x4 = 0， x6 = 0 可得基变量 x3 = 2，x1 = 2，x5 = 10，x2 = 3即得新基可行解 X ( 2 ) = ( 2, 3, 2, 0,

38、10, 0 ) T 新的目标值 Z( 2 ) = 2 x1 + 3 x2 = 13经济含义:甲、乙均生产，且将资源B, D全部用尽。目标值为 Z (2) = 13，效益又有提升！但，是否达到最优？怎样检验？改写目标函数，利用约束方程消去 x1 ，可得新目标函数值：Z = 9+ (2 (2- (x4 - 1/2 x6 ) - 3/4 x6 ) = 13 + (- 2x4 + 1/4 x6 ) 最优性判断：仍未达最优！ /Z = 9+ (2 x1 - 3/4 x6 ) 56寻找下一个基可行解 ( 使x6 进基 ) ：先使 x6的系数均为+1: 2x1 4 ( 2x4 x6 ) 4x2 12 ( x

39、6 ) 2x3 4 ( - 4 x4 x6 )1/2 x5 5 (- 2x4 x6 )保留一个x6，消去其他方程的x6 。注意：为保证可行性，选右端项最小的方程，但第二个方程不能取！为什么？因此只能取第一个方程，保留x6 ！ /x1 2 ( x4 1/2 x6 )x2 3 ( 1/4 x6 )x3 2 ( - 2 x4 1/2 x6 )x5 10 (- 4x4 2 x6 )57 2x1 2x3 8 ( - 2x4 ) 4x2 2x3 8 ( 4 x4 ) 2x3 4 ( - 4 x4 x6 )1/2 x5 2x3 1 ( 2x4 ) 2 x1 4 ( 2x4 x6 ) 4 x2 12 ( x6

40、 ) 2 x3 4 ( - 4 x4 x6 )1/2 x5 5 ( - 2x4 x6 )消去其他方程的x6 ：x6 移入左边进基， x3 移入右边离基：x6 4 ( 2x3 4 x4 ) 2x1 8 ( 2x3 2x4 )x1 4 ( x3 x4 )1/2 x5 1 ( 2x4 2x3 )x5 2 ( 4x3 4x4 )4x2 8 (- 2x3 4 x4 )x2 2 (- 1/2x3x4 )58x6 4 ( 2x3 4 x4 )x1 4 ( x3 x4 )x5 2 ( 4x3 4x4 )x2 2 (- 1/2x3x4 )求出新的基可行解： 令非基变量 x3 = 0， x4 = 0 可得基变量

41、x6 = 4，x1 = 4，x5 = 2，x2 = 2即得新基可行解 X ( 3 ) = ( 4, 2, 0, 0, 2, 4 ) T 新的目标值 Z( 3 ) = 2 x1 + 3 x2 = 14经济含义:甲、乙均生产，且将资源A, B全部用尽。目标值为 Z (2) = 14，效益又有提升！但，是否达到最优？改写目标函数，利用约束方程消去 x6 ，可得新目标函数值：Z = 13 + (- 2x4 + 1/4 x6 ) Z = 13 + (- 2x4 + 1/4 (4 - 2x3 + 4 x4 ) = 14 + (- 1/2 x3 - x4 ) 最优性判断：已达最优！59即最优解为: X *

42、= X ( 3 ) = ( 4, 2, 0, 0, 2, 4 ) T 最优值为: Z * = Z( 3 ) = 14经济含义:甲产品生产 4 件，乙产品生产 2 件，设备 A , B 有效台时数均全部用尽，设备 C 剩余有效台时数 2，设备 D 剩余有效台时数 4 。 此时，可获最大利润 14 。 /60上述消去法求解的启示：初始基可行解的确定适当选择非基变量，使方程为正消去系统基可行解是否达到最优的判别利用约束方程消去目标函数中基变量后，目标函数中非基变量的系数 检验数寻找下一个基可行解时，进基变量的确定检验数为正对应的列进基 确保新基可行解目标值增加离基变量的确定最小比值 确保新基为可行基

43、 /61四、单纯形法（Dantzig 1946）单纯形算法是求解 ( LP ) 的一个强有力的有效算法，其思路是：找到一个初始的基可行解 X (0)。根据最优性准则，检验现行基可行解 X (K) 是否已达最优 ?若是，则停，X (K)即为最优解 X*。若否，则进行下一步。转移到下一个基可行解 X (K+1)，要求 X (K+1)处的目标函数值 Z (K+1)，优于X (K)处的函数值 Z (K)。返回上一步。如此循环，直至最后得出结果。 /62单纯形算法的计算步骤：单纯形法的实质，就是在表上（单纯形表）实行运算。 Max Z = c1 x1 + c2 x2 + + cn xns.tx1 + a

44、 1 m+1 xm+1 + + a 1 n xn = b 1 x2 + a 2 m+1 xm+1 + + a 2 n xn = b 2 xm + a m m+1 xm+1 + + a m n xn = b m x i 0 i = 1n假定：x1 x2 xm 在方程中有上述形式63c1 x1 + + cm xm + cm+1 xm+1 + + cn xn = Z - 0 x1 + a 1 m+1 xm+1 + + a 1 n xn = b 1 x2 + a 2 m+1 xm+1 + + a 2 n xn = b 2 xm + a m m+1 xm+1 + + a m n xn = b m rm+

45、1 xm+1 + + rn xn = Z - c1b1 - - cmbm Z = Z 0 = c1b1 + + cmbm令：xm+1 , , xn = 0则：x1 = b 1 x2 = b 2 xm = b m64首先，列出单纯形的准备表：单纯形准备表设计变量（n列）x1 x2 xm xm+1 xn1 0 0 a 1 m+1 a 1 n 0 1 0 a 2 m+1 a 2 n 0 0 1 a m m+1 a m n先为目标函数的系数以后为检验数行（n列）c1 c2 cm cm+1 cn约束方程的系数（m行，n列）约束方程的右端项（m行）b 1b 2 b m基变量（m行）xB先为0以后为目标值的

46、负值-z 065单纯形法计算步骤： 找出初始可行基，x1 x2 xm xm+1 xnc1 c2 cm cm+1 cnb 1b 2 b m-z 0 1 0 0 a 1 m+1 a 1 n 0 1 0 a 2 m+1 a 2 n 0 0 1 a m m+1 a m n确定初始基可行解，xBx 1x2 x m建立初始单纯形表。（通过方程运算，使基变量对应的目标系数为0）第1行乘以-c1： -c1b 1 -c1 0 0 -c1a 1 m+1 -c1a 1 n第2行乘以-c2： -c2b 2 0 -c2 0 -c2a 2 m+1 -c2a 2 n 第m行乘以-cm：-cmb m 0 0 - cm -cm

47、am m+1 -cmam n全部加到c1 c2 cn所在行0 0 0 rm+1 rn - z0- z0 = - (c1 b1+c2 b2+ +cm bm )r1 rm rm+1 rn 称为检验数，初始表转入下一步；其中基变量对应的检验数为 0 。第一步：66第二步：(最优判断)x1 x2 xm xm+1 xn 1 0 0 a 1 m+1 a 1 n 0 1 0 a 2 m+1 a 2 n 0 0 1 a m m+1 a m nb 1b 2 b mx 1x2 x m-z - z0初始表 0 0 0 rm+1 rn检查对应于非基变量的检验数rj ， 若所有rj 0 ( j= m+1 n)则已达最优

48、，停止运算；此时，最优解 X * = (b 1, b 2, , b m , 0, , 0 ) T 最优值为: z * = z0 否则，若有rj 0 ，则转入下一步； x1 x2 x3 x4 x5 -z - z0 0 0 0 -1 - 3 x 1 1 1 0 0 -2 2 x 2 3 0 1 0 0 -1 x 3 2 0 0 1 1 067第三步：(无解判断)x1 x2 xm xm+1 xn 1 0 0 a 1 m+1 a 1 n 0 1 0 a 2 m+1 a 2 n 0 0 1 a m m+1 a m nb 1b 2 b mx 1x2 x m-z - z0初始表 0 0 0 rm+1 rn在

49、所有rj 0的检验数中，则此LP问题无解 ( 无有限最优解 )，停止运算； 若有一个rj所对应的 列Pj的所有元素均 非正( 0)， 否则，转入下一步； x1 x2 x3 x4 x5 -z - z0 0 0 0 1 - 3 x 1 1 1 0 0 -2 2 x 2 3 0 1 0 0 -1 x 3 2 0 0 1 -1 0-2 0-168第四步：(进基列确定)x1 x2 xm xm+1 xn 1 0 0 a 1 m+1 a 1 n 0 1 0 a 2 m+1 a 2 n 0 0 1 a m m+1 a m nb 1b 2 b mx 1x2 x m-z - z0初始表 0 0 0 rm+1 rn

50、在所有rj 0的检验数中，选最大的正检验数rq所对应的列Pq进基。（一样大取左边的。）（其目的是使新基解的目标值比原来的好！）转入下一步； x1 x2 x3 x4 x5 -z - z0 0 0 0 2 2 x 1 2 1 0 0 2 2 x 2 3 0 1 0 2 -1 x 3 2 0 0 1 -1 069第五步：(选主元)x1 x2 xm xq 1 0 0 a 1 q 0 1 0 a 2 q 0 0 1 a m q b 1b 2 b mx 1x2 x m-z - z0初始表 0 0 0 rq 按最小比值原则，Min a i q 0 i = 1mb ia i q进基列Pq右端项与所有正元素对应

51、元素的比值最小者：b pa p q=（其目的是确定离基列Pp ，并保证新基可行！） x1 x2 x3 x4 x5 -z - z0 0 0 0 2 2 x 1 2 1 0 0 2 2 x 2 3 0 1 0 2 -1 x 3 2 0 0 1 -1 0即为主元。70第六步：(换基运算)x1 xp xm x q 1 0 0 a 1 q 0 1 0 a p q 0 0 1 a m q b 1 b p b mx 1 x p x m-z - z0 0 0 0 r q 利用初等变换， 将主元变成 1， 将进基列其他元素变成 0， 将进基列对应的检验数变成 0， 这样，就得到了一个能描述新基可行解的单纯形表！

52、重复第二至第六步bp0 ap p 0 1 b11 a1 p 0 0 bm0 amp 1 0 - z00 rp 0 0 x q71例：利用单纯形法求解下列 LP 问题Max Z = x1 - 2 x2 + 2 x3 - 2 x4 + 5 x5s.tx1 + 2 x4 + x5 = 2 x2 + 2 x4 - x5 = 3 x3 - x4 = 2 x i 0 i = 15准备表x1 x2 x3 x4 x51 -2 2 -2 51 0 0 2 1 0 1 0 2 -10 0 1 -1 02 32-z 072准备表x1 x2 x3 x4 x51 -2 2 -2 51 0 0 2 1 0 1 0 2 -

53、10 0 1 -1 0232-z 0找出初始可行基，第一步：1 0 00 1 00 0 1确定初始基可行解，x 1 x 2 x 3建立初始单纯形表。x1 x2 x3 x4 x51 -2 2 -2 51 0 0 2 1 0 1 0 2 -10 0 1 -1 0232-z 0 x 1 x 2 x 3-1 0 -2 2 - 4 4-22 0 0 2 0 2 4-2 0 0 0 2 2 0初始表当前，初始基可行解： X(0) = ( 2, 3, 2, 0, 0 ) T目标值: z(0) = 0 73检查检验数 r j ，第二步：由于 r4 、r5 0 ，所以未达最优！x1 x2 x3 x4 x50 0

54、 0 2 21 0 0 2 1 0 1 0 2 -10 0 1 -1 0232-z 0 x 1 x 2 x 3判断表1第三步：在正检验数 r4 、r5 所对应的列P4 、P5中，没有所有元素均非正( 0) 的列，不能判断此LP问题无解 ，进入下一步74进基列的确定，第四步：x1 x2 x3 x4 x50 0 0 2 21 0 0 2 1 0 1 0 2 -10 0 1 -1 0232-z 0 x 1 x 2 x 3判断表1选最大的正检验数r4所对应的列P4 进基。(一样大取左边的。)第五步： 选主元Min b 1a 14，b 2a 24=22b 1a 14=2232，即为主元。75x1 x2

55、x3 x4 x50 0 0 2 21 0 0 2 1 0 1 0 2 -10 0 1 -1 0232-z 0 x 1 x 2 x 3判断表1换基运算，第六步： 将主元变成 1， 将进基列其他元素变成 0， 将进基列对应的检验数变成 0， 迭代 1 x1 x2 x3 x4 x5 -z x 1 x 2 x 3 -1 得到新基变量 x2 x3 x4x 4-1 0 0 0 1-21/2 0 0 1 1/2 1 -1 1 0 0 -2 11/2 0 1 0 1/2 31/2-176 判断表2 x1 x2 x3 x4 x5 -z -2 -1 0 0 0 1 x 4 1 1/2 0 0 1 1/2 x 2

56、1 -1 1 0 0 - 2 x 3 3 1/2 0 1 0 1/2 当前，基可行解： X(1) = ( 0, 1, 3, 1, 0 ) T目标值: z(1) = 2 重复第二至第六步 迭代 2 x1 x2 x3 x4 x5 -z x 4 x 2 x 3 1 0 0 2 12 1 1 0 4 05 0 0 1 -1 02-2 0 0 -2 0- 4由于 r5 0 ，所以未达最优！x 5 得到新基变量 x2 x3 x577 判断表3 x1 x2 x3 x4 x5 -z - 4 -2 0 0 -2 0 x 5 2 1 0 0 2 1 x 2 5 1 1 0 4 0 x 3 2 0 0 1 -1 0

57、由于所有检验数 rj 0 ，所以已达最优 ！此时，基可行解：X(2) = X * = ( 0 , 5 , 2 , 0 , 2 ) T 为最优解； 目标值: z(2) = z * = 4 为最优值。78第四节 （LP）的对偶理论对偶理论是LP中最重要的理论之一，充分显示出LP理论逻辑的严谨性和结构的对称美。对偶问题引申出来的对偶解有重要的经济意义，是进行经济分析的重要手段。79一、两个例子市场上六种食品，数据如表：含量营养食品 VA VC1 0 2 2 1 2最低营养需求90 1 3 1 3 219食品单价35 30 60 50 27 22问题1：如何采购，其费用最省？药商生产VA 、VC片，问

58、如何定价，可有竞争力且收益最高？问题2：(对偶)例1、（营养问题）80问题1 建模 (LP) ：设计变量：设食品的采购量分别为x1 x6，则有：目标：采购各食品费用之和 最少食品 食品单价35 30 60 50 27 22Min Z= 35x1+30 x2+60 x3+50 x4+27x5+22x6(LP)s.t各食品中VA含量不低于最低营养需求量 9食品 营养VA1 0 2 2 1 2最低需求9x1 + 2x3 + 2x4 + x5 + 2x6 9食品 营养VC0 1 3 1 3 2最低需求19各食品中VC含量不低于最低营养需求量 19x2 + 3x3 + x4 + 3x5 + 2x6 19

59、x i 0 i = 1,2,681问题 2 建模 (DP) ：设计变量： VA与VC的单价分别为 y1, y2 ,则有：营养片VA VC最低营养需求919目标：营养片销量（总收益） 最大Max g = 9 y1+19 y2(DP)s.t买营养片替代食品中营养的含量，费用不能比买食品贵 具有竞争力含量营养食品VA VC10食品单价35 y1 35买营养片替代食品中营养的含量，费用不能比买食品贵含量营养食品VA VC01食品单价30 y2 30买营养片替代食品中营养的含量，费用不能比买食品贵含量营养食品VA VC23食品单价602 y1 + 3 y2 60同理：对于食品2 y1 + y2 50 对

60、于食品 y1 + 3 y2 27 对于食品2 y1 + 2 y2 22y1 ，y2 082(LP) Min Z = 35x1+ 30 x2+ 60 x3+ 50 x4+ 27x5+ 22x6s.tx1 + 2x3 + 2x4 + x5 + 2x6 9x2 + 3x3 + x4 + 3x5 + 2x6 19x i 0 i = 1,2,6(DP) Max g = 9 y1 + 19 y2s.t y1 35 y2 302 y1 + 3 y2 602 y1 + y2 50 y1 + 3 y2 272 y1 + 2 y2 22y1 ，y2 083问题1 (LP) 模型结果 ：问题 2 (DP) 模型结果