运筹学-线性规划-蒯圣龙.ppt

1、,线性规划经典问题,生产计划问题 某工厂拥有A、B、C三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：,线性规划问题的表示一般形式,线性规划问题的表示-矩阵形式,max (min)zCTX s.t. AX(,)b X0,线性规划问题的表示-标准形式,max zCTX s.t.AXb X0,线性规划问题的几何特征,(d)可行域无界 (e)可行域无界 (f)可行域为空集 多个最优解 目标函数无界 无可行解,(a)可行域有界 (b)可行域有界 (c)可行域无界 唯一最优解 多个最优解 唯一最优解,线性规划解的

2、基本概念,求解一般线性规划问题策略,寻找初始基本可行解 给出基本可行解为最优解的判别准则 给出从目前基本可行解转移到新基本 可行解的方法,求解流程,基的定义,定义 线性规划的基(Basis) 对于线性规划的约束条件 AX=b X0 设B是A矩阵中的一个非奇异的mm子矩阵，则称B为线性规划的一个基。,设B是线性规划的一个基，则A可以表示为 A= B, N ,X也可相应地分成,其中 XB为m1向量，称为基变量 XN为(n-m)1向量，称为非基变量,约束方程 AX=b 的分块矩阵表示,AX=b可表示为,或,BXB+NXN=b,若XN取确定的值，则XB有唯一的值与之对应 XB=B-1b-B-1NXN

3、特别，取XN=0，这时有XB=B-1b,定义 线性规划的解 称为线性规划与基B对应的基本解。 若其中B-1b0，则称以上的基本解为一基本可行解，相应的基B称为可行基。,基本解与基本可行解的定义,定理 线性规划的基本可行解就是可行域的极点,单纯形原理的矩阵描述,设标准的线性规划问题为 minz=CTX s.t.AX=b X0 矩阵A可以分块记为A=B，N 相应地，向量X和C可以记为,AX=b可以写成 BXB+NXN=b 即 XB=B-1b-B-1NXN,对于一个确定的基B，目标函数z可以写成,目标函数z用非基变量表出的形式,单纯形表的结构,求解方法 单纯形方法,标准化,信息表(单纯形表),当前基

4、本可行解：(0, 0, 150, 20, 300) , Z=0,当前基本可行解：(75/2, 0, 75/2, 20, 0) , Z=1875,当前基本可行解：(30, 12, 0, 8, 0) , Z=1980,一般问题的初始基本可行解,标准化,添加人工变量,几种特殊情况-无可行解,当前基本可行解：(0, 0, 0, 3, 4) , Z=-4M,当前基本可行解：(0, 3, 0, 0, 1) , Z=-M-3,无可行解的判别准则,最优解时，人工变量仍为基变量,可行域无界,当前基本可行解：(0, 0, 0, 0, 4, 3) , Z=-7M,当前基本可行解：(0, 3, 0, 0, 1) ,

5、Z=-M-3,当前基本可行解：(0, 4, 0, 1, 0) , Z= -4,当前基本可行解：(8, 0, 0, 5, 0) , Z= 8,可行域无界的判别准则,存在非基变量，检验数0，技术系数均0,无穷多最优解,当前基本可行解：(0, 0, 150, 20, 300) , Z=0,当前基本可行解：(75/2, 0, 75/2, 20, 0) , Z=300,当前基本可行解：(30, 12, 0, 8, 0) , Z=300,无穷多解的判别准则,存在非基变量，检验数=0,对偶线性规划,如何合理使用资源，使总利润最大？,有限资源下的利润最大化问题,线性规划模型,最优生产计划为： x1= 41.8

6、2 (件)， x2= 52.73 (件) 最大利润 z=389.09（万元）,资源的剩余量： 资源1：200-(x1+3x2)= 0 （吨） 资源2：350-(2x1+2x2)= 160.9 （吨） 资源3：220-(4x1+2x2)= 0 （吨） 资源4：400-(3x1+2x2)= 169.09 （吨）,最优解,问题： 每种资源的价值如何？ 应如何定价？ 与市场采购价关系如何？,影子价格的引入,影子价格满足的条件：,最优解 (四种资源的影子价格：万元/吨) : w1=1.55 , w2= 0, w3= 0.36, w4= 0 目标函数值 y=389.09（万元）,影子价格的经济意义,利润最

7、大化问题影子价格的经济解释,每一种资源的影子价格 = 当该资源增加一个单位时， 总利润Z的增加量,成本最小化问题影子价格的经济解释,每一种需求的影子价格 = 当该需求增加一个单位时， 总成本Z的增加量,对偶的定义,定义 设以下线性规划问题 Max z=CTX s.t.AX b (P) X0 为原始问题，则称以下问题 Min z=bTW s.t.ATW C (D) W0 为原始问题的对偶问题。,例,(P),(D),对偶的对偶,设原始问题(P)为： max z=CTX s.t.AX b X0,(P)的对偶 (D)为: min w=bTY s.t.ATY C W0,(D)的等价问题为: max w=

8、-bTY s.t. -ATY -C Y0,(D) 的对偶 为: min z=-CTX s.t. -AX - b X0,定理 对偶问题的对偶就是原始问题,一般问题的对偶-处理方法,例,与对偶有关的定理,弱对偶定理,若X、Y分别是原问题LP与其对偶问题DP的可行解，且 z=CTX、w=bTY, 则 wz,强对偶定理,若X、Y分别是原问题LP与其对偶问题DP的可行解，且 CTX=bTY, 则X、Y分别是原问题LP与其对偶问题DP的最优解。,最优解定理,若原问题LP有最优解X*，则其对偶问题DP也有最优解Y*，且 z*=CTX * =bTY *=w*,对偶解定理,若用单纯形法解原问题LP，得有最优解X

9、*，相应的最优基为B，则 Y*=CBB-1 为其对偶问题DP的最优解,互补松弛定理,互补松弛定理的应用,求解以下线性规划问题LP ：,写出对偶问题DP：,利用图解法，可以求得DP的最优解为 (y1，y2)T=(6，0)T,得到对偶问题各松弛变量的值 y3=0，y4=2，y5=3 即对偶问题的最优解和最优目标函数值为 YT=(y1，y2，y3，y4，y5)T=(6，0，0，2，3)Tw=6 根据互补松弛定理，以下的互补松弛关系成立 由y10得到x4=0 由y40得到x2=0 由y50得到x3=0,因此原始问题的约束条件,成为,由此得到 x1=1，x5=2 即原始问题的最优解为 X=(x1，x2，

10、x3，x4，x5)T=(1，0，0，0，2)Tz=6,对偶单纯形法,LP可行解,DP可行解,当LP与DP均为可行时， LP与DP均得到最优解,单纯形方法： 保持LP可行的同时， 逐步将DP变可行,对偶单纯形方法： 保持DP可行的同时， 逐步将LP变可行,灵敏度分析,灵敏度分析目的,灵敏度分析所要解决的问题： 系数在什么范围内变化，不会影响已获得的最优基。 如果系数的变化超过以上范围，如何在原来最优解的基础上求得新的最优解 当线性规划问题增加一个新的变量或新的约束，如何在原来最优解的基础上获得新的最优解。,灵敏度分析内容,目标函数系数cj的改变 常数项bi的改变 技术系数aij的改变,目标函数系

11、数cj的改变,非基变量在目标函数中系数的灵敏度分析,基变量在目标函数中系数的灵敏度分析,非基变量在目标函数中系数的灵敏度分析-例,在线性规划问题中，对c2进行灵敏度分析 。,得到以上问题的最优单纯形表：,当c2=c2+时，相应的单纯形表为：,要使原来的解仍保持最优解，就要zj-cj0（j=1,2,3,4,5），即,由此得到， ，即当c235/12时，最优解保持不变,基变量在目标函数中系数的灵敏度分析-例,在线性规划问题中，对c1进行灵敏度分析 。,得到以上问题的最优单纯形表：,当c1=c1+时，相应的单纯形表为：,要使原来的基仍保持最优基，就要zj-cj0（j=1,2,3,4,5），即,由此得到，-33，即当-2c14时，最优基保持不变,右边常数的灵敏度分析,右边常数的灵敏度分析,例,在线性规划问题中，对b1进行灵敏度分析 。,最优单纯形表,初始单纯形表,对于上述最优解，最优基为：,当b1=b1+=9+时，最后一张单纯形表中的右边常数将成为,最后一张单纯形表中的右边常数将成为：,原始可行条件为：,-1，b1=b1+8时，原来的最优基仍为原始可行基,增加一个新的变量-例,增加一个新的变量x7，它在目标函数中的系数c7=1