运筹学线性规划

1、1 经济与管理学院经济与管理学院 - -张凤林张凤林2授课内容授课内容第一章第一章 线性规划线性规划第二章第二章 对偶单纯形法与灵敏度分析对偶单纯形法与灵敏度分析第三章第三章 运输问题运输问题第四章第四章 整数规划整数规划第五章第五章 动态规划动态规划第六章第六章 图论与网络计划图论与网络计划第七章第七章 存储论存储论第八章第八章 决策分析决策分析第九章第九章 排队论排队论3格尼斯堡7桥问题4一、线性规划问题的数学模型一、线性规划问题的数学模型主要解决以下两类问题：1、任务确定后，如何统筹安排，做到应用尽量少的人力和物力资源来完成任务；2、在一定量的人力、物力资源的条件下，如何安排、使用他们，

2、使完成的任务最多。 第一章第一章 线性规划线性规划 第第 一一 节节 线性规划问题及其数学模型线性规划问题及其数学模型5 I II 资源总量资源总量 设备设备A(h) 0 3 15 设备设备B(h) 4 0 12原材料原材料(公斤公斤) 2 2 14 利润利润(万元）万元） 2 3I,II生产多少生产多少, 可获最大利润可获最大利润?解解:设设 计划期内生产产品计划期内生产产品I、II的数量的数量x1、x2 则该问题的数学模型为：则该问题的数学模型为： 3x2 15 s.t. 4x1 12 2x1+2x2 14 x1，x2 0 max Z= 2x1 +3x2例例1.1：（计划安排问题）：（计划

3、安排问题）6例例1.2 成本问题成本问题油品来源油品来源成分成分AB汽油汽油15%50%煤油煤油20%30%重油重油50%15%其它其它15%5%1212121212min S200 x290 x0.15x0.50 x150.20 x0.30 x12s.t.0.50 x0.15x12x0,x0 某炼油厂根据每季度需供应给合同单位汽油某炼油厂根据每季度需供应给合同单位汽油15万吨、煤油万吨、煤油12万吨、重油万吨、重油12万吨。该厂计划从万吨。该厂计划从A，B两处运回原油提两处运回原油提炼，已知两处的原油成分含量见表炼，已知两处的原油成分含量见表12；又已知从；又已知从A处处采购的原油价格为每吨

4、（包括运费）采购的原油价格为每吨（包括运费）200元，元，B处采购的处采购的原油价格为每吨（包括运费）原油价格为每吨（包括运费）290元元, 问：该炼油厂该如问：该炼油厂该如何从何从A，B两处采购原油，在满足供应合同的条件下，使两处采购原油，在满足供应合同的条件下，使购买成本最小。购买成本最小。 7线性规划模型特点线性规划模型特点 决策变量：向量决策变量：向量(x1 xn)T , xi非负非负 约束条件：线性等式或不等式约束条件：线性等式或不等式 目标函数：目标函数：Z=(x1 xn) 线性式，线性式， 求求Z极大或极小极大或极小 满足以上三个条件的数学模型称为满足以上三个条件的数学模型称为

5、-线性规划数学模型线性规划数学模型一般形式：一般形式：12211212max Z23315412. .2214,0 xxxxs txxxx 12031540 ,12 ,232214xAXbCx令令 9矩阵形式：矩阵形式： 1212m a x Z23031 540. .1 2221 40 xxxs txX m a x ZC XA Xb. .0s tX 10二、线性规划问题的标准型二、线性规划问题的标准型 目标函数目标函数 max 变量变量 非负非负 约束条件约束条件 等式等式 约束常数约束常数 非负非负11解：引进3个新非负变量x3，x4，x5使不等式变为等式，标准型为：例1.3将例1.1的数学

6、模型化为标准型。 12211212max Z23315412. .2214,0 xxxxs txxxx 123452314125125max Z23000315412. .2214,0 xxxxxxxxxs txxxxxx 12解：解： 令令x3 =x4 - x5 添加松弛变量添加松弛变量x6 添加剩余变量添加剩余变量x7 令令S= -SmaxS= x1 2x2 +3x4 3x5 x1 +x2 +x4 -x5 +x6=7 s.t. x1 -x2 +x4 -x5 -x7 =2 x1 , x2 , x4 , , x7 0 0 将将 min S = -x1+2x2 3x3 x1+x2 +x3 7s.

7、t. x1 -x2 +x3 2 2 x1，x2 0 0，x3无限制无限制化为标准型化为标准型例例1.4 第二节第二节 线性规划问题的图解法及几何意义线性规划问题的图解法及几何意义14 一、线性规划问题的解的概念一、线性规划问题的解的概念03 1001540010 X= 1222 00114 0 3 10 3 14 0 04 0 0=802 2 02 2 0其其行行列列式式，是是可可逆逆矩矩阵阵 1 0 00 1 0=100 0 1其其行行列列式式值值，是是可可逆逆矩矩阵阵 15(m x2 = 0.8x10.02 S0=40 x1+50 x2 过原点过原点C点：使点：使截距最大截距最大 x1+2

8、x2 =30 3x1+2x2 =6022 max Z = 2x1 +3x22112123154122214,0 xxxxxx例15解得：最优解（2，5）T。 最优值 Z=22+35=1923用图解法求解线性规划问题 maxZ=40 x1+ 80 x2 s.t. x1+2x2 30 3x1+2x2 60 2x2 24 x1 , x2 0例16解：最优解：BC线段B点 X(1)= (6,12)；C点 X(2)= (15,7.5) X= X(1)+(1-) X(2) (0 1) maxZ=1200 整理得：x1 =15-9 x2 =7.5+4.5 (0 1)0203010102030 x1x2DAB

9、C24maxZ=2x1+ 4x2 s.t. 2x1+x2 8 -2 x1+ x2 2 x1，x2 0例17若目标函数由 min Z =2 x1 +4 x2 ,最优解 x1 = 4，x2 = 0 ，即 (4,0)点无界解无界解=可行域无界可行域无界 =解：由于可行域无界 无有限最优解-无界解2x1+ x2=8-2x1+ x2=28246x240 x125max S=3x1+2x2 -x1 -x2 1 1x1 , x2 0 0无可行解无可行解-1x2-1x10总结总结 唯一解唯一解 无穷多解无穷多解 无有限最优解无有限最优解 无可行解无可行解有解有解无解无解例例26通过以上各题图解法所得结论可以看

10、出： （1）线性规划的所有可行解构成的可行域一般是凸多边形，有些可行域可能是无界的； （2）若存在最优解，则一定在可行域的某顶点得到； （3）若在两个顶点上同时得到最优解，则在这两点的连线上的任一点都是最优解。 （4）若可行域无界，则可能发生最优解无界的情况； （5）若可行域是空集，此时无最优解。 上述理论具有普遍意义，对于两个以上变量的线性规划问题都是成立。 27 1. 凸集：假设凸集：假设K是是n维欧氏空间的一个点集，若对于维欧氏空间的一个点集，若对于K中的任意中的任意两点两点X1、X2，其连线上的所有点，其连线上的所有点 X1+(1- )X2，( 0 1)都在集合都在集合K中，即：中，即

11、： X1+(1- )X2 K ( 0 1) 则称则称K为凸集。为凸集。从直观上讲，凸集无凹入部分，其内部没有洞。从直观上讲，凸集无凹入部分，其内部没有洞。如实心圆、实心球、实心立方体等都是凸集。两个凸集的交集仍是如实心圆、实心球、实心立方体等都是凸集。两个凸集的交集仍是凸集。凸集。 2. 凸组合：设凸组合：设X1，X2，Xk是是n维欧氏空间维欧氏空间En中的中的k个点，个点，若存在若存在 1， 2， k，且，且0 i 1，i = 1,2, , k， i = 1，使，使X = 1X1 + 2X2 + + kXk，则称，则称X为由为由X1，X2，Xk所构成的凸所构成的凸组合。组合。按照定义，凡是由

12、按照定义，凡是由x，y的凸组合表示的点都在的凸组合表示的点都在x，y的连线上，而且的连线上，而且反之亦然。反之亦然。 3. 顶点：顶点： 假设假设K是凸集，是凸集，X K；X若不能用不同的两个点若不能用不同的两个点X1、X2 K的线性组合表示为：的线性组合表示为： X = X1+(1- )X2 ， ( 0 0中的最大者，即：中的最大者，即： j = max l l 0 j所对应的变量所对应的变量xj为换入变量为换入变量(就是下一个基的基变量就是下一个基的基变量)。 3. 基变换基变换 （1）换入变量的确定）换入变量的确定33 利用单纯形算法求解例利用单纯形算法求解例11的线性规划问题。的线性规

13、划问题。cj23000iXBbx1x2x3x4x5x315031005x41240010 x514220017-Z023000例例1.8解：解： （1）由标准型得到初始单纯形表：）由标准型得到初始单纯形表：123452314125125max Z23000315412. .2214,0 xxxxxxxxxs txxxxxx cj23000iXBbx1x2x3x4x5x315031005x41240010 x514220017-Z023000 x25011/300 x412400103x5420-2/3012-Z-1520-100 x25011/300 x44004/31-2x1210-1/30

14、1/2-Z-1900-1/30-135表16这时，检验数全部小于等于0，即目标函数已不可能再增大，于是得到最优解：X*=(2,5,0,4,0)目标函数的最大值为： Z*=19cj23000iXBBx1x2x3x4x5x25011/300 x44004/31-2x1210-1/301/2-Z-1900-1/30-1T36 利用单纯形算法求解线性规划问题。 max Z=4x1+3x2+0 x3+0 x4+0 x5 2x1+2x2+ x3=1600 s.t. 5x1+2.5x2+x4=2500 x1+x5 =400 x1, x2, x3, x4, x50 解： （1）由标准型得到初始单纯形表17：表

15、表17 cj43000iXBbx1x2x3x4x5x3160022100800 x4250052.5010500 x540010001400-Z043000例例1.937 表18cj43000iXBbx1x2x3x4x5x38000210-2400 x450002.501-5200 x140010001-Z-16000300-4 表19cj43000iXBbx1x2x3x4x5x3400001-0.82200 x22000100.4-2-x140010001400-Z-2200000-1.2238表110cj43000iXBbx1x2x3x4x5x5200000.5-0.41x2600011-

16、0.40-x120010-0.50.40-Z-260000-1-0.40这时，检验数全部小于等于0，即目标函数已达到最大，因此得到最优解： X=(200,600,0,0,200)目标函数的最大值为： Z=2600T39 利用单纯形算法求解线性规划问题。 max Z=2x1+3x2+0 x3+0 x4+0 x5+0 x6 2x1+2x2+x3=12 x1+2x2+x4=8 s.t. 4x1+x5=16 4x2+x6=12 x1，x2，x3，x4，x5, x60解： （1）由标准型得到初始单纯形表：表111cj230000iXBbx1x2x3x4x5x6x3122210006x481201004x

17、516400010 x6120400013-Z0230000例例1.1040表112cj230000iXBbx1x2x3x4x5x6x3620100-1/23x4210010-1/22x5164000104x23010001/4-Z-920000-3/4 表113cj230000iXBbx1x2x3x4x5x6x32001-201/24x1210010-1/2x58000-4124x23010001/412-Z-13000-201/441在相同 对应的变量中选择下标最大的那个基变量-换出变量；同时如果出现有两个或更多的检验数大于零且相同时，在相同 对应的变量中选择下标最小的那个基变量为进入变量

18、，-避免出现“死循环” 表114cj230000iXBbx1x2x3x4x5x6x30001-1-1/40 x1410011/40 x64000-21/21x220101/2-1/80-Z-14000-3/2 -1/80最优解： X*=(4,2,0,0,0,4)目标函数的最大值为： Z*=14T 相同的问题相同的问题-退化问题退化问题-表表11342 第四节第四节 单纯形算法的进一步讨论单纯形算法的进一步讨论 二、人工变量法二、人工变量法(大大M法法) 例例1.11 三、三、 两阶段法两阶段法 例例1.12 43第一阶段是先求出基本可行解 (或判断出原线性规划问题无解)第二阶段利用已求出的初始基本可行解来求最优解。定理定理1.8 设原线性规划问题记成(LP)，由它而引入的新的线性规划问题记成(LP)*。分别表示如下：*1():()*:00,0(,) ,(1,1)TTmTTnn mLPMaxZC XLPMinWe XAXbAXIXbXXXXxxe个441) 若(LP)*具有最优基本可行解 则(LP)是可行的，而 即为(LP)的一个基可行解。2) 若(LP)*的最优基本可行解 则(LP) 必不可行。*,0,XXX且X*,0,XXX使得 定理1.8的具体应用过程是：由(LP)*判断原线性规划