线性规划与对偶理论.ppt

1、运筹学ABC 线性规划,北京科技大学 经济管理学院,1,第二部分线 性 规 划,Linear Programming,简记 LP,运筹学ABC 线性规划,北京科技大学 经济管理学院,2,主要内容 ：,学习数学规划的建模，提高分析问题的能力 掌握线性规划的标准型、图解法 掌握线性规划的单纯形法、对偶理论 掌握影子价格的意义 了解灵敏度分析的目的/,运筹学ABC 线性规划,北京科技大学 经济管理学院,3,第一节 （LP）模型的建立及标准形式,一、由实际问题出发，建立（LP）模型,LP主要解决的问题：,例如： 产品的最优组合 生产排序 最优投资方案 人力资源分配 /,稀缺资源在竞争中如何进行最优分配

2、。,运筹学ABC 线性规划,北京科技大学 经济管理学院,4,模型的四个要点：,真实性 简明性 完整性 规范性/,运筹学ABC 线性规划,北京科技大学 经济管理学院,5,规划论模型包含的三个方面：,1、设计方案：,利用变量 x1 , x2 ,x n 表示方案，,称为设计变量或决策变量。,2、目标（方案好坏的评价标准）：,一般表示为决策变量的函数 f (x1 ,x n )，,称为目标函数，用Max ( Min ) 表示最优。,3、限制条件（客观条件对方案的限制）：,一般表示为决策变量的不等式方程，,称为约束方程。 /,运筹学ABC 线性规划,北京科技大学 经济管理学院,6,规划论模型的数学表示：,

3、x1 , x2 ,x n ，,Max ( Min ) Z = f (x1 ,x n ),LP只是规划论中的一种。 /,运筹学ABC 线性规划,北京科技大学 经济管理学院,7,规划论中不同规划的主要区别： 函数,若目标函数与约束方程中的函数均为线性函数， 线性规划 若目标函数与约束方程中的函数有非线性函数， 非线性规划 若设计变量要求取整数，, 整数规划,若设计变量要求只取 ( 0, 1 )，, 0 -1规划,若函数中引入时间参数, 动态规划,另：若目标有多个, 多目标规划/,运筹学ABC 线性规划,北京科技大学 经济管理学院,8,线性与非线性的区别：,线性函数：函数为多元一次。 表达式： a1

4、 x1 + a2 x2 + + an xn,不是线性的函数，均称为非线性函数。 例如： 2 x12 + 3 x1x2,运筹学ABC 线性规划,北京科技大学 经济管理学院,9,函数不是线性的规划问题,例：把半径为R的实心金属球熔化后， 铸成一个实心圆柱体，,问：圆柱体取什么尺寸， 才能使它的表面积最小？ /,运筹学ABC 线性规划,北京科技大学 经济管理学院,10,解：,设计变量：设圆柱体的底面半径为x1 ，高为x2,R,目标函数：M in (圆柱体表面积 ) = (两个底面积) + (侧面积) = 2x12 + 2x1x2,约束方程：V圆柱 = V 圆球,运筹学ABC 线性规划,北京科技大学

5、经济管理学院,11,二、（LP）模型的种类,（1）(引论中的例1),（2）(引论中的例2),运筹学ABC 线性规划,北京科技大学 经济管理学院,12,例3 (运输最优调配问题),某矿区有四座冶炼厂和三座选矿厂，三座选矿厂选出的精矿分别送到四座冶炼厂冶炼。 冶炼厂年处理精矿能力、选矿厂年生产精矿能力以及精矿运费如表：,1.5 2.0 0.3 3.0 1000,7.4 0.8 1.4 2.0 800,1.2 0.2 2.0 2.5 500,500 700 800 300,问：如何调配精矿，使运费最低？ /,运筹学ABC 线性规划,北京科技大学 经济管理学院,13,建模：,设计变量：,目标函数：总运

6、费 最少,M in Z = 1.5 x11 + 2.0 x12 + 0.3x13 + 3.0 x14 1.2 x31 + 0.2x32 + 2.0 x33 + 2.5x34,约束方程：,产量约束,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 =

7、1, 2, 3, 4 /,运筹学ABC 线性规划,北京科技大学 经济管理学院,14,运筹学ABC 线性规划,北京科技大学 经济管理学院,15,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 + + 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),运筹学ABC 线性

8、规划,北京科技大学 经济管理学院,16,三、 （LP）模型的标准形式,要求右端项 b j 0 j = 1m /,运筹学ABC 线性规划,北京科技大学 经济管理学院,17,模型的矩阵表示:,决策变量 X =（x1, x2 , , x n ) T (列向量) 目标系数 c = ( c1, c2 , , c n ) T (列向量) 右端项 b = ( b1 , b2 , , b m )T (列向量),约定 nm,记：,R(A) = m (满秩矩阵) ,且 b0 /,运筹学ABC 线性规划,北京科技大学 经济管理学院,18,模型的简化表示:,即：,运筹学ABC 线性规划,北京科技大学 经济管理学院,1

9、9,四、模型的标准化,1、极小化模型的改写：,即：把 Min Z = cTX 改写成 Max Z = cTX, Min Z = - Max (- Z),Max,Min, 令 Z= - Z,于是得到： Max Z= - cTX,注意： Z* = - Z* /,运筹学ABC 线性规划,北京科技大学 经济管理学院,20,2、不等式约束的改写：,(1) “”的改写：,a i 1 x1 + a i 2 x2 + + a i n xn b i,添加一个非负变量xn+1 使,a i 1 x1 + a i 2 x2 + + a i n xn + xn+1 = b i,(2) “”的改写：,a j1 x1 +

10、a j2 x2 + + a jn xn b j,减去一个非负变量xn+2 使,a j1 x1 + a j2 x2 + + a jn xn - xn+2 = b j,运筹学ABC 线性规划,北京科技大学 经济管理学院,21,3、决策变量非正的改写：,(1) “”的改写：,若 x i 0,则令：y i = - x i 并代入模型中,(2) 自由变量的改写：,若 x j 为自由变量,则令：x j = u v 且 u 0 ，v 0,并代入模型中/,运筹学ABC 线性规划,北京科技大学 经济管理学院,22,标准化的例：,（以引论中例1 为例）,非标准，通过减去剩余变量使 变 ,非标准，通过减去剩余变量使

11、 变 ,X6 , X7 为剩余变量。 这里的剩余变量有何经济解释？ 对目标函数的影响？,目标非标准,令：Z = - Z,4 x1 + 3x2 + 2x3 + x4 90,- x6 90,2x2 + 4x3 +5x4 + 7x5 70,- x7 70,x i 0 且为整数 i =15, 6, 7,+0 x6 +0 x7,运筹学ABC 线性规划,北京科技大学 经济管理学院,23,目标：余料总长 最少,这里的剩余变量对目标函数有无影响？,+ x6 + x7,Max Z = - 20 x1 - 10 x2 - 0 x3 - 30 x4 - 20 x5 - x6 - x7,运筹学ABC 线性规划,北京科

12、技大学 经济管理学院,24,（以引论中例2 为例）,Max Z = 20 x 1 + 30 x 2,目标标准,非标准，通过增加松弛变量使 变 ,非标准，通过增加松弛变量使 变 ,+ x3 120,+ x4 10,x1 4000,非标准，通过增加松弛变量使 变 ,+ x5 4000,x2 3000,非标准，通过增加松弛变量使 变 ,+ x6 3000,x1 + x2 5000,非标准，通过增加松弛变量使 变 ,+ x7 5000,x1， x2， x3， x4， x5， x6， x7 0,X3 X7 为松驰变量。 这里的松弛变量有何经济解释？ /,运筹学ABC 线性规划,北京科技大学 经济管理学院

13、,25,例,Max Z =,令： y1 = x1 x2 = y2 y3,+ 5y1, 2y1,+ 7y2 7y3,y1 ， y2 ， y3 ， y4 0,+ 5y2 5y3,+ y4,= 60,运筹学ABC 线性规划,北京科技大学 经济管理学院,26,一、可行解与最优解,满足的 X 称为 可行解,第二节 （LP）的图解法,运筹学ABC 线性规划,北京科技大学 经济管理学院,27,二、图解法举例,(1)、(2)、(3)、(4) 的边界线（直线）围成一个 凸多边形 可行域。 目标函数 Z 取不同值 Zi 形成一个,平行直线族 等高线。,运筹学ABC 线性规划,北京科技大学 经济管理学院,28,如何

14、使用图解法？,1、 画出可行域；,2、 画出等高线，确定最优方向；,3、 找出最优点；,4、 求出最优解及最优值。 /,运筹学ABC 线性规划,北京科技大学 经济管理学院,29,（1）x1 + x2 4 L1： x1 + x2 4,(0,0) 满足(1)， (1)含原点。,（2） -x1 + 2x2 2 L2： -x1 + 2x2 2,(0,0) 满足(2)， (2)含原点。,（3） x1 - x2 2 L3： x1 - x2 2,(0,0) 满足(3)， (3)含原点。,目标 Z = 2x1 + 5x2,Z1 = 2x1 + 5x2 = 1,Z2 = 2x1 + 5x2 = 2,图解法求解步

15、骤:,运筹学ABC 线性规划,北京科技大学 经济管理学院,30,图解法,计算B点坐标，B点位于L1与L2的交点处,运筹学ABC 线性规划,北京科技大学 经济管理学院,31,另一种情况1：,BC线段上的点均为最优点，即有无穷多最优解。,最优解集= (x1, x2) | x2 4- x1 2x1 3 ,(2, 2),(3, 1),运筹学ABC 线性规划,北京科技大学 经济管理学院,32,找不到最优点！即无最优解。 /,另一种情况2：,运筹学ABC 线性规划,北京科技大学 经济管理学院,33,另一种情况3：,没有可行解！,更不可能有最优解！ /,运筹学ABC 线性规划,北京科技大学 经济管理学院,3

16、4,三、图解法的启示,（LP）的最优解可能有： 唯一解； 无穷多解； 无解。 （LP）的最优解若存在， 则可能在约束域（凸多面体）的某个（些）顶点（极点）处达到。,运筹学ABC 线性规划,北京科技大学 经济管理学院,35,第三节 单纯型算法,（Simplex Method）,从图解法的启示出发，做理论建设工作， 要解决： （LP）可行域顶点的解析计算； 最优解的存在性； 建立有效的计算方法（算法）。,美国运筹学家，斯坦福大学运筹学系教授，Dantzig 于 1946 年解决了上述问题。 /,运筹学ABC 线性规划,北京科技大学 经济管理学院,36,一、基解与基可行解,先考虑（LP）中的约束方程

17、 ， 即 A X = b 由于 R(A) = m (n ) ，故有无穷多个解。 记 A =（P1 P2 P n） 其中 Pi 表示 X i 的系数列向量。,因此 A X = b 可表示为： P1 x 1 + P2 x 2 + + P n x n = b,运筹学ABC 线性规划,北京科技大学 经济管理学院,37,如果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 =

18、 b,不失一般性，记 B = ( P1 P2 P m ) 则称 B 为一个基（Basic）， B中的列称为基列， 对应的变量称为基变量 XB =（x1, , x m ) T ；,且 R ( B ) = m，,运筹学ABC 线性规划,北京科技大学 经济管理学院,38,则 AX = b 可表示为： B XB + N XN = b,令非基变量 XN = 0， 则 AX = b 可等价为： B XB = b,运筹学ABC 线性规划,北京科技大学 经济管理学院,39,（P1 P2 P n）,不一定！,运筹学ABC 线性规划,北京科技大学 经济管理学院,40,利用图解法中的例，了解基解在几何中的对应关系,

19、运筹学ABC 线性规划,北京科技大学 经济管理学院,41,X (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点，,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

20、) = (6,4,-6,0,0 ) T H5点。,非基列,( P1 P2 ),( P1 P3 ),( P1 P4 ),( P1 P5 ),( P2 P3 ),( P2 P4 ),( P2 P5 ),( P3 P4 ),( P3 P5 ),( P4 P5 ),运筹学ABC 线性规划,北京科技大学 经济管理学院,42,结论：,上例中，基可行解有： X(1)，X(3)，X(7)，X(8)，X(9) 分别与约束域顶点 O，A，D，B，C 对应。,基解不一定是可行解。,即基可行解与（LP）约束域顶点： 构成了一一对应关系。 /,运筹学ABC 线性规划,北京科技大学 经济管理学院,43,经严格的数学证明，

21、可以得出如下结果： 定理1 线性规划（LP）的基可行解 与其约束域的顶点构成一一对应。 定理2 对于线性规划（LP）问题： 1、若存在一个可行解， 则一定存在基可行解；,二、基本定理,则一定在某个（些）基可行解处达到。 /,运筹学ABC 线性规划,北京科技大学 经济管理学院,44,各解之间的关系：,不可行解,运筹学ABC 线性规划,北京科技大学 经济管理学院,45,三、寻找最优解算法的思路,是否最优? 如何判断?,2. 要可行,运筹学ABC 线性规划,北京科技大学 经济管理学院,46,例：,某厂在某计划期内要安排生产甲、乙两种产品，这些产品分别需要在A、B、C、D四种不同的设备上加工。按工艺规

22、定，每种产品在设备上所需的加工台时数，设备在计划期内的有效台时数，以及每种产品的单位产品盈利如表：,问：如何安排这两种产品的生产， 使获得的总盈利额为最多？ /,运筹学ABC 线性规划,北京科技大学 经济管理学院,47,建模、标准化：,下面利用消去法来寻找求解思路 /,运筹学ABC 线性规划,北京科技大学 经济管理学院,48,首先要找到一个(随便哪个)(初始的)基可行解：,由于 x3 , x4 , x5 , x6 的系数矩阵为单位阵，,显然满秩，可作为基，,因此 x3, x4, x5, x6可作为基变量！,该基解如何求？如何保证它是基可行解？,将上述方程进行调整，将非基变量移至等式右端：,此处

23、均 0，称为正消去系统 （保证 x i 0） /,运筹学ABC 线性规划,北京科技大学 经济管理学院,49,该基可行解是否使目标达到最优？怎样判断？,如果没有达到最优，怎样寻找下一个基可行解？,经济含义:,x1 = 0，x2 = 0，即产品甲、乙均不生产， 设备A、B、C、D均富余，此时利润为 0。,最优性判断：,未达最优！,因目标函数 Z中x1 , x2 的系数均为正。 即若其中任意一个适当生产，皆可产生利润。 （称目标系数 c1 ,c2 为检验数） /,即得初始基可行解 X ( 0 ) = ( 0,0,12,8,18,12 ) T 初始目标值 Z( 0 ) = 2 x1 + 3 x2 =

24、0,基可行解的求法： 令非基变量 x1 = 0， x2 = 0 可得基变量 x3 =12，x4 = 8，x5 = 18，x6 = 12,运筹学ABC 线性规划,北京科技大学 经济管理学院,50,目标值 Z( 0 ) = 2 x1 + 3 x2 = 0,X ( 0 ) = ( 0,0,12,8,18,12 ) T,若检验数0，目标值有上升的可能！,为使目标函数值上升，让检验数为正的变量进基！ （使其0）（为升得快，取检验数最大的！） 即让x2进基成为基变量，（其含义为：生产乙产品） 由于基变量个数固定，一个进基就应有一个离基。 所以原基变量将有一个离基，成为非基变量。 （其含义为：尽量多的生产乙

25、产品，直到使某种资源用完为止。） /,运筹学ABC 线性规划,北京科技大学 经济管理学院,51,寻找下一个基可行解 ( 使x2 进基 ) ：,先使x2的系数均为+1:,1/2 x3 6 ( x1 x2 ) 1/2 x4 4 (1/2 x1 x2 ) x5 18 ( 4 x1 ) 1/4 x6 3 ( x2 ),保留一个x2，消去其他方程的x2 。,注意：为使某一个方程的x2 移入左边进基， 在消去其他方程的x2 时，还要使该方程仍为正系统。 为了达到此目的，选右端项（比值）最小的方程。 （保证可行性！） /,运筹学ABC 线性规划,北京科技大学 经济管理学院,52,消去其他方程的x2 ：,1/

26、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 ( 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 ),运筹学ABC 线性规划,北京科技大学 经济管理学院,53,求出新的基可行解： 令非基变量 x1 = 0， x6 = 0 可得基变量 x3 = 6，x4 = 2，

27、x5 = 18，x2 = 3,即得新基可行解 X ( 1 ) = ( 0, 3, 6, 2, 18, 0 ) T 新的目标值 Z( 1 ) = 2 x1 + 3 x2 = 9,经济含义:,生产产品乙，且将资源D全部用尽。,目标值为 Z (1) = 9，效益已有提升！ 但，是否达到最优？怎样检验？,改写目标函数，利用约束方程消去 x2 ， 可得新目标函数值：,Z = 2 x1 + 3 ( 3 - 1/4 x6 ) = 9 + ( 2 x1 - 3/4 x6 ),最优性判断：,仍未达最优！,（为什么？如何办？） /,Z = 2 x1 + 3 x2,运筹学ABC 线性规划,北京科技大学 经济管理学院

28、,54,寻找下一个基可行解 ( 使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 ),保留一个x1，消去其他方程的x1 。,注意：为保证可行性， 选右端项（比值）最小的方程，保留x1 。 /,运筹学ABC 线性规划,北京科技大学 经济管理学院,55,消去其他方程的x1 ：,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 移入左

29、边进基， x4 移入右边离基：,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 ),运筹学ABC 线性规划,北京科技大学 经济管理学院,56,求出新的基可行解： 令非基变量 x4 = 0， x6 = 0 可得基变量 x3 = 2，x1 = 2，x5 = 10，x2 = 3,即得新基可行解 X ( 2 ) = ( 2, 3, 2, 0, 10, 0 ) T 新的目标值 Z( 2 ) = 2 x

30、1 + 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 ),运筹学ABC 线性规划,北京科技大学 经济管理学院,57,寻找下一个基可行解 ( 使x6 进基 ) ：,先使 x6的系数均为+1:,2x1 4 ( 2x4 x6 ),4

31、x2 12 ( x6 ),2x3 4 ( - 4 x4 x6 ),1/2 x5 5 (- 2x4 x6 ),保留一个x6，消去其他方程的x6 。,注意：为保证可行性，选右端项最小的方程，,但第二个方程不能取！为什么？,因此只能取第一个方程，保留x6 ！ /,运筹学ABC 线性规划,北京科技大学 经济管理学院,58,2x1 2x3 8 ( - 2x4 ),4x2 2x3 8 ( 4 x4 ),2x3 4 ( - 4 x4 x6 ),1/2 x5 2x3 1 ( 2x4 ),消去其他方程的x6 ：,x6 移入左边进基， x3 移入右边离基：,x6 4 ( 2x3 4 x4 ),2x1 8 ( 2x

32、3 2x4 ),x1 4 ( x3 x4 ),1/2 x5 1 ( 2x4 2x3 ),x5 2 ( 4x3 4x4 ),4x2 8 (- 2x3 4 x4 ),x2 2 (- 1/2x3x4 ),运筹学ABC 线性规划,北京科技大学 经济管理学院,59,求出新的基可行解： 令非基变量 x3 = 0， x4 = 0 可得基变量 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

33、(2) = 14，效益又有提升！ 但，是否达到最优？,改写目标函数，利用约束方程消去 x6 ， 可得新目标函数值：,Z = 13 + (- 2x4 + 1/4 x6 ),Z = 13 + (- 2x4 + 1/4 (4 - 2x3 + 4 x4 ) = 14 + (- 1/2 x3 - x4 ),最优性判断：,已达最优！,运筹学ABC 线性规划,北京科技大学 经济管理学院,60,即最优解为: X * = X ( 3 ) = ( 4, 2, 0, 0, 2, 4 ) T 最优值为: Z * = Z( 3 ) = 14,经济含义:,甲产品生产 4 件，乙产品生产 2 件， 设备 A , B 有效台

34、时数均全部用尽， 设备 C 剩余有效台时数 2， 设备 D 剩余有效台时数 4 。 此时，可获最大利润 14 。 /,运筹学ABC 线性规划,北京科技大学 经济管理学院,61,上述消去法求解的启示：,初始基可行解的确定 适当选择非基变量，使方程为正消去系统 基可行解是否达到最优的判别 利用约束方程消去目标函数中基变量后， 目标函数中非基变量的系数 检验数 寻找下一个基可行解时，进基变量的确定 检验数为正对应的列进基 确保新基可行解目标值增加 离基变量的确定 最小比值 确保新基为可行基 /,运筹学ABC 线性规划,北京科技大学 经济管理学院,62,四、单纯形法（Dantzig 1946）,单纯形

35、算法是求解 ( LP ) 的一个强有力的有效算法， 其思路是： 找到一个初始的基可行解 X (0)。,根据最优性准则，检验现行基可行解 X (K) 是否已达最优 ?,若是，则停，X (K)即为最优解 X*。,若否，则进行下一步。,转移到下一个基可行解 X (K+1)，,要求 X (K+1)处的目标函数值 Z (K+1)，优于X (K)处的函数值 Z (K)。,返回上一步。,如此循环，直至最后得出结果。 /,运筹学ABC 线性规划,北京科技大学 经济管理学院,63,单纯形算法的计算步骤：,单纯形法的实质， 就是在表上（单纯形表）实行运算。,假定：x1 x2 xm 在方程中有上述形式,运筹学ABC

36、 线性规划,北京科技大学 经济管理学院,64,c1 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+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 m,运筹学ABC 线性

37、规划,北京科技大学 经济管理学院,65,首先，列出单纯形的准备表：,设计变量（n列）,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 n,先为目标函数的系数 以后为检验数行 （n列）,c1 c2 cm cm+1 cn,约束方程的系数 （m行，n列）,约束方程的右端项 （m行）,b 1 b 2 b m,基变量 （m行）,xB,先为0 以后为目标值的负值,-z 0,运筹学ABC 线性规划,北京科技大学 经济管理学院,66,单纯形法计算步骤：,找出初始可行基，,确定初始基可行解，,x 1,x2, ,

38、x m,建立初始单纯形表。,（通过方程运算，使基变量对应的目标系数为0）,- z0 = - (c1 b1+c2 b2+ +cm bm ),r1 rm rm+1 rn 称为检验数，,初始表,转入下一步；,其中基变量对应的检验数为 0 。,第一步：,运筹学ABC 线性规划,北京科技大学 经济管理学院,67,第二步：(最优判断),检查对应于非基变量的检验数rj ，,若所有rj 0 ( j= m+1 n),则已达最优，停止运算；,此时，最优解 X * = (b 1, b 2, , b m , 0, , 0 ) T,最优值为: z * = z0,否则，若有rj 0 ，,则转入下一步；,运筹学ABC 线性

39、规划,北京科技大学 经济管理学院,68,第三步：(无解判断),在所有rj 0的检验数中，,则此LP问题无解 ( 无有限最优解 )，停止运算；,若有一个rj所对应的 列Pj的所有元素均 非正( 0)，,否则，转入下一步；,运筹学ABC 线性规划,北京科技大学 经济管理学院,69,第四步：(进基列确定),在所有rj 0的检验数中，,选最大的正检验数rq所对应的列Pq进基。,（一样大取左边的。）,（其目的是使新基解的目标值比原来的好！）,转入下一步；,运筹学ABC 线性规划,北京科技大学 经济管理学院,70,第五步：(选主元),按最小比值原则，,进基列Pq右端项与所有正元素对应元素的比值最小者：,（

40、其目的是确定离基列Pp ，并保证新基可行！）,运筹学ABC 线性规划,北京科技大学 经济管理学院,71,第六步：(换基运算),利用初等变换，,将主元变成 1，,将进基列其他元素变成 0，,将进基列对应的检验数变成 0，,这样，就得到了一个能描述新基可行解的单纯形表！,重复第二至第六步,x q,运筹学ABC 线性规划,北京科技大学 经济管理学院,72,例：利用单纯形法求解下列 LP 问题,x1 x2 x3 x4 x5,1 -2 2 -2 5,1 0 0 2 1 0 1 0 2 -1 0 0 1 -1 0,2 3 2,-z 0,运筹学ABC 线性规划,北京科技大学 经济管理学院,73,1 0 0

41、0 1 0 0 0 1,确定初始基可行解，,x 1 x 2 x 3,初始表,当前，初始基可行解： X(0) = ( 2, 3, 2, 0, 0 ) T 目标值: z(0) = 0,运筹学ABC 线性规划,北京科技大学 经济管理学院,74,由于 r4 、r5 0 ， 所以未达最优！,第三步：,在正检验数 r4 、r5 所对应的列P4 、P5中， 没有所有元素均非正( 0) 的列， 不能判断此LP问题无解 ，进入下一步,运筹学ABC 线性规划,北京科技大学 经济管理学院,75,选最大的正检验数r4所对应的列P4 进基。 (一样大取左边的。),第五步： 选主元,运筹学ABC 线性规划,北京科技大学

42、经济管理学院,76,将主元变成 1，,将进基列其他元素变成 0，,将进基列对应的 检验数变成 0，,得到新基变量 x2 x3 x4,x 4,运筹学ABC 线性规划,北京科技大学 经济管理学院,77,当前，基可行解： X(1) = ( 0, 1, 3, 1, 0 ) T 目标值: z(1) = 2,重复第二至第六步,由于 r5 0 ， 所以未达最优！,x 5,得到新基变量 x2 x3 x5,运筹学ABC 线性规划,北京科技大学 经济管理学院,78,由于所有检验数 rj 0 ，所以已达最优 ！,此时，基可行解：X(2) = X * = ( 0 , 5 , 2 , 0 , 2 ) T 为最优解；,目

43、标值: z(2) = z * = 4 为最优值。,运筹学ABC 线性规划,北京科技大学 经济管理学院,79,第四节 （LP）的对偶理论,对偶理论是LP中最重要的理论之一， 充分显示出LP理论逻辑的严谨性和结构的对称美。 对偶问题引申出来的对偶解有重要的经济意义， 是进行经济分析的重要手段。,运筹学ABC 线性规划,北京科技大学 经济管理学院,80,一、两个例子,市场上六种食品，数据如表：, ,VA VC,1 0 2 2 1 2,最低营养需求,9,0 1 3 1 3 2,19,食品单价,35 30 60 50 27 22,问题1：,如何采购，其费用最省？,药商生产VA 、VC片， 问如何定价，可

44、有竞争力且收益最高？,例1、（营养问题）,运筹学ABC 线性规划,北京科技大学 经济管理学院,81,问题1 建模 (LP) ：,设计变量：设食品的采购量分别为x1 x6，,则有：,Min Z= 35x1+30 x2+60 x3+50 x4+27x5+22x6,x1 + 2x3 + 2x4 + x5 + 2x6 9,x2 + 3x3 + x4 + 3x5 + 2x6 19,x i 0 i = 1,2,6,运筹学ABC 线性规划,北京科技大学 经济管理学院,82,问题 2 建模 (DP) ：,设计变量： VA与VC的单价分别为 y1, y2 ,则有：,Max g = 9 y1+19 y2,y1 3

45、5,y2 30,2 y1 + 3 y2 60,同理：对于食品,2 y1 + y2 50,对于食品,y1 + 3 y2 27,对于食品,2 y1 + 2 y2 22,y1 ，y2 0,运筹学ABC 线性规划,北京科技大学 经济管理学院,83,运筹学ABC 线性规划,北京科技大学 经济管理学院,84,问题1 (LP) 模型结果 ：,问题 2 (DP) 模型结果：,最优解 X * = (x1, x2, x3, x4, x5, x6 ) T = ( 0,0,0,0,5,2 ) T 最优值 Z * = 0 + 27x5 + 22x6 = 27 5 + 22 2 = 179,最优解 Y * = ( y1

46、, y2 ) T = ( 3, 8 ) T 最优值 g * = 9 y1 + 19 y2 = 9 3 + 19 8 = 179,运筹学ABC 线性规划,北京科技大学 经济管理学院,85,例2、（生产计划问题）,问题1：,如何安排生产，可使用利润最大？,若该厂考虑设备出租(或代加工）， 问：设备租价如何确定，可使收益良好， 且具有吸引力 ？（底价的确定）,技术经济指标如表：,某厂生产、两种产品，,运筹学ABC 线性规划,北京科技大学 经济管理学院,86,问题1 建模 (LP) ：,设计变量：,则有：,Max Z= 20 x1 + 30 x2 (两产品利润之和),2 x1 + 3 x2 18 (A

47、设备资源约束),x1 + 2 x2 10 (B设备资源约束),3 x1 + x2 16 (C设备资源约束),2 x1 + 2 x2 12 (D设备资源约束),x1 , x2 0,设x1，x2分别代表产品、的日产量，,运筹学ABC 线性规划,北京科技大学 经济管理学院,87,问题 2 建模 (DP) ：,设计变量：,设A, B, C, D出租时的租金价分别为y1, y2 , y3 , y4 ,则有：,Min g = 18 y1+10 y2+16 y3+12 y4 (租金越低越有竞争力),y1 , y2 , y3 , y4 0,运筹学ABC 线性规划,北京科技大学 经济管理学院,88,运筹学ABC

48、 线性规划,北京科技大学 经济管理学院,89,例题的启示：,任何一个线性规划问题（原问题 (LP)） 均有一个从其他角度出发考虑的问题 对偶问题 (DP) 。 它们既不相同，又有联系。 它们的最优值相同。 原问题与对偶问题的位置不是绝对的。 /,运筹学ABC 线性规划,北京科技大学 经济管理学院,90,二、对偶规划的定义,若（LP）为：,则（DP）为：,运筹学ABC 线性规划,北京科技大学 经济管理学院,91,Min Z = c1 x1 + c2 x2 + + cn xn,（LP）,（DP）,Max g = b1 y1 + b2 y2 + + bm ym,运筹学ABC 线性规划,北京科技大学

49、经济管理学院,92,由 ( LP ) 写出 ( DP ) 的要点,Min,Max,( Max ),( Min ),系数矩阵,A,AT,不等式约束,目标函数类型,（ ）,（ ）,运筹学ABC 线性规划,北京科技大学 经济管理学院,93,例：,令 u = -x2,Min Z= 20 x1 - 30 u,2 x1 - 3 u 18,x1 - 2 u = 10,3 x1 - u 16,x1 0， u 0,运筹学ABC 线性规划,北京科技大学 经济管理学院,94,Min Z= 20 x1 - 30 u,- 2 x1 + 3 u -18,x1 - 2 u 10,x1 - 2 u 10,- x1 + 2 u

50、 -10,3 x1 - u 16,x1 0， u 0,运筹学ABC 线性规划,北京科技大学 经济管理学院,95,(DP)： 4个变量，2个约束方程,Max g = - 18 y1 +10 y2 - 10 y3 + 16 y4,- 2 y1 + y2 - y3 + 3 y4 20,y1 0，y2 0，y3 0，y4 0,3 y1 - 2 y2 + 2 y3 - y4 - 30,运筹学ABC 线性规划,北京科技大学 经济管理学院,96,Max g = - 18 y1 +10 y2 - 10 y3 + 16 y4,- 2 y1 + y2 - y3 + 3 y4 20,y1 0，y2 0，y3 0，y

51、4 0,- 3 y1 + 2 y2 - 2 y3 + y4 30,令 u = - y1 v = y2 - y3,Max g = 18 u +10 v + 16 y4,2 u + v + 3 y4 20,u 0， v 自由，y4 0,3 u + 2 v + y4 30,运筹学ABC 线性规划,北京科技大学 经济管理学院,97,最初的 (LP) 与最终的 (DP) 相比较,运筹学ABC 线性规划,北京科技大学 经济管理学院,98,三、对偶理论的两个重要结论,1、D ( DP ) =（LP） 2、( LP ) 与 ( DP ) 若都有最优解存在， 分别为 X* 与 Y*， 则它们的最优值相等， 即

52、cT X * = bT Y* （反之，也成立。但要强调“可行解”。）,运筹学ABC 线性规划,北京科技大学 经济管理学院,99,四、对偶最优解的经济学解释 影子价格,1、定义：,对资源合理分配的（LP）模型来说， 其对偶规划（DP）的最优解 Y* 的第 i 项： y i * （ i = 1,2, m）,称为相应第 i 种资源的影子价格。 （Shadow Price）,运筹学ABC 线性规划,北京科技大学 经济管理学院,100,2、影子价格的含义：,在资源最佳分配情况下，资源整合为产品， 以产品形式获得的最佳效益为 Z* ， 而 Z* = g* ，且 g* = y1* b1+ y2* b2 +

53、+ y m* b m 以 y1*为例：令 b1 b1+1 ，而 b2 , b m 不变， 则 g = g - g* = Y*( b1+1, b2 , , bm) - Y*( b1 , b2 , , bm) = y1* 即 y1*表示第一种资源增加一个单位时，效益的相应增加值。,运筹学ABC 线性规划,北京科技大学 经济管理学院,101,影子价格的含义（续1）,y j* 0 时，表示资源 j 的增加，可增加效益， 这意味着，资源 j 为紧缺资源； y j* = 0 时，表示资源 j 的增加，不会增加效益， 这意味着资源 j 为富余资源。 会出现 y j* 0 吗？/,运筹学ABC 线性规划,北京

54、科技大学 经济管理学院,102,影子价格的含义（续2）,影子价值并非真实价格，它属于边际效益指标，企业内部分析的重要深层数据。 影子价格决定了企业内部资源调整的方向或投资方向，并可估计投资产生的效益。 /,运筹学ABC 线性规划,北京科技大学 经济管理学院,103,第五节 （LP）的灵敏度分析,灵敏度分析是 LP 中另一重要的内容， 它的主要功能是分析 LP 参数（c、A、b）的变化 对最优解的影响。 主要是考虑到实际数据的不准确性， (1) 精确度不够；(2) 不确定因素/,运筹学ABC 线性规划,北京科技大学 经济管理学院,104,灵敏度分析的主要内容：,目标函数系数变化的灵敏度分析 1、

55、非基变量的系数变化 2、基变量的系数变化 右端项发生变化的灵敏度分析 系数矩阵的元素发生变化的灵敏度分析 1、增加一个变量的分析 2、增加一个新约束的分析 主要是分析： 这些系数在什么范围变动时，最优基不变！,运筹学ABC 线性规划,北京科技大学 经济管理学院,105,例1：矿山生产计划优化P92,第六节 （LP）应用举例,运筹学ABC 线性规划,北京科技大学 经济管理学院,106,最优解：,x 1* 3272.5 T / 日， x 2* 1727.5 T / 日， x 3* = 7， x 4* = 0 ， x 5* = 727.5 T / 日， x 6* = 1272.5 T / 日， x

56、7* = 0 Z * = 11725 元 / 日,含义：,在 x 1* ，x 2* 所示的最优生产计划下， 运力，矿仓已用尽，（紧缺资源） 工人富裕 7人； 提升能力分别富余：727.5 T / 日及1272.5 T / 日。,运筹学ABC 线性规划,北京科技大学 经济管理学院,107,资源的影子价格：,y1*0（人力资源）； y2*10364（运力资源） y3*0， y4*0（提升资源）； y5*0.27（矿仓资源）,富余资源再作资源投入不产生新效益。 若增加1台运输设备，在最佳运作下， 每日产生新效益10364元。 若增加1吨仓储能力，在最佳情况下， 每日增加0.27元新效益。,含义：,x

57、 3* = 7， x 4* = 0 ， x 5* = 727.5 ，x 6* = 1272.5 x 7* = 0,运筹学ABC 线性规划,北京科技大学 经济管理学院,108,例2：昆钢产品结构优化,该公司有 6 个成材厂， 它们是：650厂，250厂，中板厂，薄板厂， 线材厂及无缝钢管厂。 每年生产各种规格的轧钢产品数百种。 该公司要求为其产品结构进行优化设计。 /,运筹学ABC 线性规划,北京科技大学 经济管理学院,109,（一）目标函数,要求以此系统的利润最大化为决策准则，即,式中： xi ：第 i 个决策变量，表示第 i 组产品的产量； Ci ：第 i 组产品的单位可变成本； Pi ：第

58、 i 组产品的销售单价； Ta ：产品销售税率（650厂产品不是最终产品， 故对其不计此税率）; n：产品组 ( 组数 i = 1，2，n ); F(M)：全系统年固定费。,运筹学ABC 线性规划,北京科技大学 经济管理学院,110,（二）决策变量,本项研究以相近规格产品并为一组，以减少变量个数，及加强模型的稳定性; 如 x8 表示10 70 mm的碳素结构钢管坯等。 为了利于模型的扩充，决策变量下标均使用双数，其分配为： x2 , x4 , x36 ， 属650厂，共18 个； x42 , x44 , x56 ， 属250厂，共 8 个； x60 , x62 , x90 ， 属中板厂，共16 个； x100 , x102 , x118 ，属薄板厂，共10 个； x122 , x124 , x130 ，属线材厂，共 5 个； x142 , x144 , x168 ，属无缝厂，共14 个。,运筹学ABC 线性规划,北京科技大学 经济管理学院,111,分别表示由本系统外 ( 但在本公司内 ) 的连铸普碳坯，连铸低合金坯，炼钢厂扁锭，普通无缝管坯和一般锅炉管坯。 综上可知： 决策变量共 71 个，外生变量 5 个。 /,又外生变量共 5 个， x1 , x3 , x5 , x141 , x143 ，,运筹学ABC 线性规划,