线性规划与对偶理论.ppt

《线性规划与对偶理论.ppt》由会员分享，可在线阅读，更多相关《线性规划与对偶理论.ppt（141页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二部分第二部分线线 性性 规规 划划Linear Programming 简记简记 LP北京科技大学北京科技大学 经济管理学院经济管理学院1运筹学运筹学ABC 线性规划线性规划主要内容主要内容：学习数学规划的建模，学习数学规划的建模，提高分析问题的能力提高分析问题的能力掌握线性规划的标准型、图解法掌握线性规划的标准型、图解法掌握掌握线性规划的单纯形法、对偶理论线性规划的单纯形法、对偶理论掌握掌握影子价格的意义影子价格的意义了解灵敏度分析的目的了解灵敏度分析的目的/北京科技大学北京科技大学 经济管理学院经济管理学院2运筹学运筹学ABC 线性规划线性规划第一节第一节 （LP）模型的建立及标准形式

2、模型的建立及标准形式一、由实际问题出发，建立（一、由实际问题出发，建立（LP）模型模型LP主要解决的问题：主要解决的问题：例如：例如：产品的最优组合产品的最优组合 生产排序生产排序 最优投资方案最优投资方案 人力资源分配人力资源分配 /稀缺资源在竞争中如何进行最优分配。稀缺资源在竞争中如何进行最优分配。北京科技大学北京科技大学 经济管理学院经济管理学院3运筹学运筹学ABC 线性规划线性规划模型的四个要点：模型的四个要点：真实性真实性 简明性简明性 完整性完整性 规范性规范性/北京科技大学北京科技大学 经济管理学院经济管理学院4运筹学运筹学ABC 线性规划线性规划规划论模型包含的三个方面：规划论

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

4、性规划规划论模型的数学表示：规划论模型的数学表示：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运筹学运筹学ABC 线性规划线性规划规划论中不同规划的主要区别：规划论中不同规划的主要区别：函数函数若目标函数与约束方程中的函数均为线性函数，若目标函数与约束方程中的函数均为线性函数，线性规划线性规划若目标函数与约束方程中的函数有非线性函数，若目标函数与约束方程中的函数有非线性函数，非线性规划非线性规划若设计变量要

5、求取整数，若设计变量要求取整数，整数规划整数规划 若设计变量要求只取若设计变量要求只取(0,1)，0-1规划规划 若函数中引入时间参数若函数中引入时间参数,动态规划动态规划另：若目标有多个另：若目标有多个,多目标规划多目标规划/北京科技大学北京科技大学 经济管理学院经济管理学院7运筹学运筹学ABC 线性规划线性规划线性与非线性的区别：线性与非线性的区别：线性函数：函数为多元一次。线性函数：函数为多元一次。表达式：表达式：a1 x1+a2 x2+an xn x1f(x1)2维维(一元一元)x1f(x1,x2)3维维(二元二元)x2不是线性的函数，均称为非线性函数。不是线性的函数，均称为非线性函数

6、。例如：例如：2 x12+3 x1x2x1f(x1)2维维(一元一元)x1f(x1,x2)3维维(二元二元)x2北京科技大学北京科技大学 经济管理学院经济管理学院8运筹学运筹学ABC 线性规划线性规划函数不是线性的规划问题函数不是线性的规划问题例：把半径为例：把半径为R的实心金属球熔化后，的实心金属球熔化后，铸成一个实心圆柱体，铸成一个实心圆柱体，问：圆柱体取什么尺寸，问：圆柱体取什么尺寸，才能使它的表面积最小？才能使它的表面积最小？/R北京科技大学北京科技大学 经济管理学院经济管理学院9运筹学运筹学ABC 线性规划线性规划解：解：设计变量：设设计变量：设圆柱体的底面半径为圆柱体的底面半径为x

7、1，高为高为x2Rx1x2目标函数：目标函数：M in(圆柱体表面积圆柱体表面积)=(两个底面积两个底面积)+(侧面积侧面积)=2x12+2x1x2约束方程：约束方程：V圆柱圆柱=V 圆球圆球s.tx12 x2=4/3 R3 x1，x2 0北京科技大学北京科技大学 经济管理学院经济管理学院10运筹学运筹学ABC 线性规划线性规划二、（二、（LP）模型的种类模型的种类（1）(引论中的引论中的例例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 2)s.tx1+140

8、 156x2 120 x1+1600 1380 x2 10 x1 4000 x2 3000 x1 +x2 5000 x1，x2 0Max Z=20 x 1+30 x 2北京科技大学北京科技大学 经济管理学院经济管理学院11运筹学运筹学ABC 线性规划线性规划例例3 3(运输最优调配问题运输最优调配问题)某矿区有四座冶炼厂和三座选矿厂，三座选某矿区有四座冶炼厂和三座选矿厂，三座选矿厂选出的精矿分别送到四座冶炼厂冶炼。矿厂选出的精矿分别送到四座冶炼厂冶炼。冶炼厂年处理精矿能力、选矿厂年生产精矿冶炼厂年处理精矿能力、选矿厂年生产精矿能力以及精矿运费如表：能力以及精矿运费如表：冶炼厂冶炼厂选矿厂选矿厂

9、运费运费 (元元/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问：如何调配问：如何调配精矿，使运费最低？精矿，使运费最低？/23002300北京科技大学北京科技大学 经济管理学院经济管理学院12运筹学运筹学ABC 线性规划线性规划建模：建模：设计变量：设计变量：设第设第i 选矿厂向第选矿厂向第 j 冶炼厂冶炼厂调配精矿调配精矿xi j(T)。i=1,2,3(甲甲,乙乙,丙丙)，j=1,2,3,4(A,B,C,D)A B C

10、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 800 300 x11 x12 x13 x14x21 x22 x23 x24x31

11、 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 /北京科技大学北京科技大学 经济管理学院经济管理学院13运筹学运筹学ABC 线性规划线性规划Min Z=1.5 x11+2.0 x12+0.3x13+3.0 x14 1.2 x31+0.2x32+2.0 x33+2.5x34s.tx1

12、1+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+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

13、=20 x 1+30 x 2北京科技大学北京科技大学 经济管理学院经济管理学院14运筹学运筹学ABC 线性规划线性规划s.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+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运筹学运筹学ABC 线性规划线性规划三、三、（LP）模型的标准形

14、式模型的标准形式 要求右端项要求右端项 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 xn北京科技大学北京科技大学 经济管理学院经济管理学院16运筹学运筹学ABC 线性规划线性规划模型的矩阵表示模型的矩阵表示:决策变量决策变量 X=（x1,x2,x n )T (列向量列向量)目标系数目标系数 c=(c1,c2,c n )T (列向量列向量)右端项右端项 b=(

15、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运筹学运筹学ABC 线性规划线性规划模型的简化表示模型的简化表示:（LP）AX=b X0 /Max Z=cTXMax Z=(c1 c2 cn)（LP）x1 x2 xn x1 x2 xn a 1 1 a 1 2 a 1 n a 2 1 a 2 2 a

16、2 n a m 1 a m 2 a m nb 1b 2 b m=x1 x2 xn 0 0 0即：即：北京科技大学北京科技大学 经济管理学院经济管理学院18运筹学运筹学ABC 线性规划线性规划四、四、模型的模型的标准化标准化1、极小化模型的改写：、极小化模型的改写：即：把即：把 Min Z=cTX 改写成改写成 Max Z=cTX Min Z=-Max(-Z)X y-ZX*Max ZMin 令令 Z=-Z于是得到于是得到：Max Z=-cTX 注意注意：Z*=-Z*/北京科技大学北京科技大学 经济管理学院经济管理学院19运筹学运筹学ABC 线性规划线性规划2、不等式约束的改写：、不等式约束的改写

17、：(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+a j2 x2+a jn xn b j减去一个非负变量减去一个非负变量xn+2 使使a j1 x1+a j2 x2+a jn xn-xn+2 =b j剩余变量剩余变量北京科技大学北京科技大学 经济管理学院经济管理学院20运筹学运筹学ABC 线性规划线性规划3、决策变量非正的改写：、决策变量非正的改写：(1)“”的改写：的改写：若若 x

18、 i 0 则令：则令：y i =-x i 并代入模型中并代入模型中(2)自由变量的改写：自由变量的改写：若若 x j 为自由变量为自由变量则令：则令：x j =u v 且且 u 0，v 0 并代入模型中并代入模型中/北京科技大学北京科技大学 经济管理学院经济管理学院21运筹学运筹学ABC 线性规划线性规划标准化的例：标准化的例：（以引论中（以引论中例例1 为例）为例）Min Z=x i 5i=1s.t非标准，通过减去剩余变量使非标准，通过减去剩余变量使 变变 非标准，通过减去剩余变量使非标准，通过减去剩余变量使 变变 X6,X7 为剩余变量。为剩余变量。这里的剩余变量有何经济解释？这里的剩余变

19、量有何经济解释？对目标函数的影响？对目标函数的影响？目标非标准目标非标准令：令：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 x7北京科技大学北京科技大学 经济管理学院经济管理学院22运筹学运筹学ABC 线性规划线性规划目标：目标：余料总长余料总长 最少最少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+20 x5

20、这里的剩余变量对目标函数有无影响？这里的剩余变量对目标函数有无影响？+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-x7北京科技大学北京科技大学 经济管理学院经济管理学院23运筹学运筹学ABC 线性规划线性规划s.t（以引论中（以引论中例例2 为例）为例）Max Z=20 x 1+30 x 2目标标准目标标准x1+140 156x2 120非标准，通过增加松弛变量使非标准，通过增加松弛变量使 变变 x1+1600 1

21、380 x2 10非标准，通过增加松弛变量使非标准，通过增加松弛变量使 变变+x3 120 +x4 10 x1 4000非标准，通过增加松弛变量使非标准，通过增加松弛变量使 变变 +x5 4000 x2 3000非标准，通过增加松弛变量使非标准，通过增加松弛变量使 变变 +x6 3000 x1 +x2 5000非标准，通过增加松弛变量使非标准，通过增加松弛变量使 变变 +x7 5000 x1，x2，x3，x4，x5，x6，x7 0X3 X7 为松驰变量。为松驰变量。这里的松弛变量有何经济解释？这里的松弛变量有何经济解释？/北京科技大学北京科技大学 经济管理学院经济管理学院24运筹学运筹学ABC

22、 线性规划线性规划例例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=60北京科技大学北京科技大学 经济管理学院经济管理学院25运筹学运筹学ABC 线性规划线性规划最优解最优解满足满足的的 X 称为称为 最优解最优解。/一、一、可行解与最优解可行解与最优解满足满足的的 X 称为称为 可行解可行解第二节第二节 （LP）的的图解法图解法在线性规划模型（在线性规划模型（LP）中：中：Max Z=cTX (LP)AX=b X0 s.

23、t北京科技大学北京科技大学 经济管理学院经济管理学院26运筹学运筹学ABC 线性规划线性规划二二、图解法举例图解法举例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运筹学运筹学ABC 线性规划线性规划如何使用图解法？如何使用图

24、解法？1、画出可行域；画出可行域；2、画出等高线，确定最优方向；画出等高线，确定最优方向；3、找出最优点；找出最优点；4、求出求出最优解最优解及及最优值最优值。/北京科技大学北京科技大学 经济管理学院经济管理学院28运筹学运筹学ABC 线性规划线性规划s.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)含原点。含原点。x

25、1 0 4 x2 1 3（3）x1-x2 2 L3：x1-x2 2(0,0)满足满足(3)，(3)含原点。含原点。x1 2 4 x2 0 2目标目标目标目标 Z=2xZ=2x1 1+5x5x22Z1=2x1+5x2=1x1 1/2 3x2 0 -1Z2=2x1+5x2=2x1 1 x2 0 图解法求解步骤图解法求解步骤:北京科技大学北京科技大学 经济管理学院经济管理学院29运筹学运筹学ABC 线性规划线性规划 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=

26、1(1,0)Z2=2max Z*计算计算B点坐标，点坐标，B点位于点位于L1与与L2的交点处的交点处 x1+x2=4-x1+2x2=2X*=(2,2)TZ*=22+52=14最优点最优点北京科技大学北京科技大学 经济管理学院经济管理学院30运筹学运筹学ABC 线性规划线性规划 X1 X21 2 3 4 5 6 4 3 2 1 0-1-2L1L2L3BCDA另一种另一种情况情况1：Z1=1Z2=2max Z*BC线段上的点均为最优点，即有无穷多最优解。线段上的点均为最优点，即有无穷多最优解。最优点集最优点集最优解集最优解集=(x1,x2)|x2 4-x1 2x1 3(2,2)(3,1)北京科技大

27、学北京科技大学 经济管理学院经济管理学院31运筹学运筹学ABC 线性规划线性规划 X1 X21 2 3 4 5 6 4 3 2 1 0-1-2L1L2Z1=1max找不到最优点！即无最优解。找不到最优点！即无最优解。/另一种另一种情况情况2：Z2=2北京科技大学北京科技大学 经济管理学院经济管理学院32运筹学运筹学ABC 线性规划线性规划 X1 X21 2 3 4 5 6 4 3 2 1 0-1-2L1L2另一种另一种情况情况3：没有可行解！没有可行解！更不可能有最优解！更不可能有最优解！/北京科技大学北京科技大学 经济管理学院经济管理学院33运筹学运筹学ABC 线性规划线性规划三、三、图解法

28、的启示图解法的启示（LP）的最优解可能有：的最优解可能有：唯一解；唯一解；无穷多解；无穷多解；无解。无解。（LP）的最优解若存在，的最优解若存在，则可能在约束域（凸多面体）的某个（些）顶点则可能在约束域（凸多面体）的某个（些）顶点（极点）处达到。（极点）处达到。北京科技大学北京科技大学 经济管理学院经济管理学院34运筹学运筹学ABC 线性规划线性规划第三节第三节 单纯型算法单纯型算法 （Simplex Method）从图解法的启示出发，做理论建设工作，从图解法的启示出发，做理论建设工作，要解决：要解决：（LP）可行域顶点的解析计算；可行域顶点的解析计算；最优解的存在性；最优解的存在性；建立有效

29、的计算方法（算法）。建立有效的计算方法（算法）。美国运筹学家，斯坦福大学运筹学系教授，美国运筹学家，斯坦福大学运筹学系教授，Dantzig 于于 1946 年解决了上述问题。年解决了上述问题。/北京科技大学北京科技大学 经济管理学院经济管理学院35运筹学运筹学ABC 线性规划线性规划一、一、基解与基可行解基解与基可行解先考虑（先考虑（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=

30、b 可表示为：可表示为：P1 x 1+P2 x 2+P n x n=b 北京科技大学北京科技大学 经济管理学院经济管理学院36运筹学运筹学ABC 线性规划线性规划如果如果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中的列称为中的列称为基列基列，

31、对应的变量称为对应的变量称为基变量基变量 XB=（x1,x m )T；且且 R(B)=m，北京科技大学北京科技大学 经济管理学院经济管理学院37运筹学运筹学ABC 线性规划线性规划则则 AX=b 可表示为：可表示为：B XB+N XN =b 令非基变量令非基变量 XN=0，则则 AX=b 可等价为：可等价为：B XB=b且有唯一解且有唯一解 XB，称解称解 X=(XBT,XNT)T=(XBT,0)T 为为（LP）对应于基对应于基 B的的 基基解解(Basic Solution)。易知，基解最多有易知，基解最多有 C m 个。个。n北京科技大学北京科技大学 经济管理学院经济管理学院38运筹学运筹

32、学ABC 线性规划线性规划（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运筹学运筹学ABC 线性规划线性规划利用图解法中的例利用图解法中的例，了解基解在几何中的对应关系了解基解在几何中的对应关系基解最多有基解最多有 C

33、m =C 3 n 5 5!(5-3)!3!=10个个 x1 +x2+x3 4 -x1 +2x2 +x4 2 x1-x2 +x5 2s.t北京科技大学北京科技大学 经济管理学院经济管理学院40运筹学运筹学ABC 线性规划线性规划 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点，X(7)=(2,0,2,4,0)T D 点，X(8)=(2,

34、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 =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

35、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 1 0 1 -1 0 0 1北京科技大学北京科技大学 经济管理学院经济管理学院41运筹学运筹学ABC 线性规划线性规划结论：结论：如果基如果基解解 X ，且满足且满足，即，即 X 0，则此基解

36、则此基解 X 称为称为基可行解基可行解。上例中，基可行解有：上例中，基可行解有：X(1)，X(3)，X(7)，X(8)，X(9)分别与约束域顶点分别与约束域顶点 O，A，D，B，C 对应。对应。基解不一定是可行解。基解不一定是可行解。X1 X2BCDAOH2H3H4H5H1即基可行解与（即基可行解与（LP）约束域约束域顶点顶点：构成了构成了一一对应一一对应关系。关系。/北京科技大学北京科技大学 经济管理学院经济管理学院42运筹学运筹学ABC 线性规划线性规划最优解最优解2 2、若、若 最优解最优解 存在，存在，经严格的数学证明，可以得出如下结果：经严格的数学证明，可以得出如下结果：定理定理11

37、 线性规划线性规划（LP）的的基可行解基可行解与其约束域的与其约束域的顶点顶点构成构成一一对应一一对应。定理定理2 2 对于线性规划（对于线性规划（LP）问题：问题：1 1、若存在一个若存在一个可行解可行解，则一定存在则一定存在基可行解基可行解；二、二、基本定理基本定理则一定在某个（些）则一定在某个（些）基可行解基可行解处达到。处达到。/北京科技大学北京科技大学 经济管理学院经济管理学院43运筹学运筹学ABC 线性规划线性规划各解之间的关系：各解之间的关系：解集解集可行解可行解不可行解不可行解基解基解基可行解基可行解最优解最优解最优解最优解（如果存在）（如果存在）北京科技大学北京科技大学 经济

38、管理学院经济管理学院44运筹学运筹学ABC 线性规划线性规划三、寻找最优解算法的思路三、寻找最优解算法的思路基可行解基可行解基可行解基可行解基解基解基可行解基可行解 最优解最优解基可行解基可行解基解基解基解基解寻找初始寻找初始基可行解基可行解是否最优是否最优?如何判断如何判断?怎样寻找怎样寻找下个基解下个基解?1.要比原来的好要比原来的好2.要可行要可行北京科技大学北京科技大学 经济管理学院经济管理学院45运筹学运筹学ABC 线性规划线性规划例：例：某厂在某计划期内要安排生产甲、乙两种产品，某厂在某计划期内要安排生产甲、乙两种产品，这些产品分别需要在这些产品分别需要在A、B、C、D四种不同的设

39、四种不同的设备上加工。按工艺规定，每种产品在设备上所需备上加工。按工艺规定，每种产品在设备上所需的加工台时数，设备在计划期内的有效台时数，的加工台时数，设备在计划期内的有效台时数，以及每种产品的单位产品盈利如表：以及每种产品的单位产品盈利如表：单位产品需单位产品需设备台时数设备台时数设备设备A B C D单位产单位产品盈利品盈利产产品品甲甲乙乙有效台时数有效台时数 2 1 4 0 2 2 2 0 4 312 8 18 12问：如何安排这两种产品的生产，问：如何安排这两种产品的生产，使获得的总盈利额为最多？使获得的总盈利额为最多？/北京科技大学北京科技大学 经济管理学院经济管理学院46运筹学运筹

40、学ABC 线性规划线性规划2 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运筹学运筹学ABC 线性规划线性规划首先要找到一个首先要找到一个(随便哪个随便哪个)(初始的初始的)基可行解：基可行解：由于由于 x3,x4,x5,x6 的的系数矩阵为单位阵，系数矩阵为单位阵，显然满秩，可作为基，显然满秩，可作为基，因此因此 x3,x4,x

41、5,x6可作为基变量可作为基变量！该基解如何求？如何保证它是基可行解？该基解如何求？如何保证它是基可行解？将上述方程进行调整，将非基变量移至等式右端：将上述方程进行调整，将非基变量移至等式右端：x3 12 (2 x1 2 x2 )x4 8 (x1 2 x2 )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,6北京科技大学北京科技

42、大学 经济管理学院经济管理学院48运筹学运筹学ABC 线性规划线性规划x3 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、D均富余，此时利润为均富余，此时利润为 0。最优性判断：最优性判断：未达最优未达最优！因目标函数因目标函数 Z中中x1,x2 的系数均为正。的系数

43、均为正。即若其中任意一个适当生产，皆可产生利润。即若其中任意一个适当生产，皆可产生利润。（称目标系数（称目标系数 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=12北京科技大学北京科技大学 经济管理学院经济管理学院49运筹学运筹学ABC 线性规划线性规划目标值目标值 Z(0 )=2 x1+3 x2=0X(0)=(0,0,12,8,18,1

44、2)T 检验数检验数若检验数若检验数0，目标值有上升的可能！，目标值有上升的可能！为使目标函数值上升，让检验数为正的变量进基！为使目标函数值上升，让检验数为正的变量进基！（使其（使其0）（为升得快，取检验数最大的！）（为升得快，取检验数最大的！）即让即让x2进基进基成为基变量，（其含义为：成为基变量，（其含义为：生产生产乙乙产品）产品）由于由于基变量个数固定，一个进基就应有一个离基。基变量个数固定，一个进基就应有一个离基。所以原基变量将有一个离基，成为非基变量。所以原基变量将有一个离基，成为非基变量。（其含义为：尽量多的（其含义为：尽量多的生产生产乙乙产品，直到使某种资源产品，直到使某种资源用

45、完为止。）用完为止。）/北京科技大学北京科技大学 经济管理学院经济管理学院50运筹学运筹学ABC 线性规划线性规划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/4 x6 3 (x2 )保留一个保留一个x2，消去其他方程的消去其他方程的x2。注意：注意：为使某一个方程的为使某一个方程的x2 移入左边进基，移入左边进基，在消

46、去其他方程的在消去其他方程的x2 时，还要使该方程仍为正系统。时，还要使该方程仍为正系统。为了达到此目的，选右端项为了达到此目的，选右端项（比值）（比值）最小的方程。最小的方程。（保证可行性！）（保证可行性！）/北京科技大学北京科技大学 经济管理学院经济管理学院51运筹学运筹学ABC 线性规划线性规划1/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

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

48、标值目标值 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 x2x3 6 (2 x1 1/2 x6)x4 2 (x1 1/2 x6)x5 18

49、(4 x1 )x2 3 (1/4 x6)北京科技大学北京科技大学 经济管理学院经济管理学院53运筹学运筹学ABC 线性规划线性规划寻找下一个基可行解寻找下一个基可行解 (使使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。/x3 6 (2 x1 1/2 x6)x4 2 (x1 1/2 x6

50、)x5 18 (4 x1 )x2 3 (1/4 x6)北京科技大学北京科技大学 经济管理学院经济管理学院54运筹学运筹学ABC 线性规划线性规划消去其他方程的消去其他方程的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 移入右边离基：移入右边离基：1/2 x3 1 (-x4 1/4 x6)x1 2 (x4 1/2 x6)1