第2章 线规划.ppt

1、运筹学 Operational research 第一章 线性规划及单纯形法,管理学院管理科学与工程 -郝海,如果规划问题的数学模型中，决策变量的取值是连续的，目标函数是决策变量的线性函数，约束条件是含决策变量的线性等式或不等式，则该类规划问题的数学模型称为线性规划的数学模型。,一、定义,线性规划介绍,二、线性规划的重要地位 是运筹学中应用最广泛的方法之一； 是运筹学最基本的方法之一，整数规划，目标规划和多目标规划，网络规划都是以线性规划为基础的； 是解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大。,线性规划介绍,三、线性规划解决的管理问题：,合理利用线材问题； 配料问题；

2、投资问题； 产品生产计划； 劳动力安排； 运输问题。,线性规划介绍,四、研究对象,有一定的人力、财力、资源条件下，如何合理安排使用，效益最高 某项任务确定后，如何安排人、财、物，使之最省,线性规划介绍,要求达到某些数量上的最大化或最小化； 在一定的约束条件下追求其目标。,五、线性规划问题的共同点：,线性规划介绍,线性规划的数学模型,一、问题的提出 二、线性规划数学模型的一般形式 三、线性规划数学模型的标准形式,例1 美佳公司计划制造I，II两种家电产品。已知各制造一件时分别占用的设备A、B的台时、调试时间及A、B设备和调试工序每天可用于这两种家电的能力、各售出一件时的获利情况如表Il所示。问该

3、公司应制造A、B两种家电各多少件，使获取的利润为最大。,分析和表述问题,1、确定决策目标，明确主要决策什么,目标 ： 利润最大！,例1 美佳公司计划制造I，II两种家电产品。已知各制造一件时分别占用的设备A、B的台时、调试时间及A、B设备和调试工序每天可用于这两种家电的能力、各售出一件时的获利情况如表Il所示。问该公司应制造A、B两种家电各多少件，使获取的利润为最大。,分析和表述问题,假设：利润Z 家电I的数量x1 家电II的数量x2,例1 美佳公司计划制造I，II两种家电产品。已知各制造一件时分别占用的设备A、B的台时、调试时间及A、B设备和调试工序每天可用于这两种家电的能力、各售出一件时的

4、获利情况如表Il所示。问该公司每天应制造I、II两种家电各多少件，使获取的利润为最大。,分析和表述问题,目标函数：maxZ=2x1x2,例1 美佳公司计划制造I，II两种家电产品。已知各制造一件时分别占用的设备A、B的台时、调试时间及A、B设备和调试工序每天可用于这两种家电的能力、各售出一件时的获利情况如表Il所示。问该公司应制造A、B两种家电各多少件，使获取的利润为最大。,分析和表述问题,2、要辨认哪些是决策的关键影响因素，在选取这些关键因素时存在哪些资源和环境的限制,设备，调试工序时间受限制,例1 美佳公司计划制造I，II两种家电产品。已知各制造一件时分别占用的设备A、B的台时、调试时间及

5、A、B设备和调试工序每天可用于这两种家电的能力、各售出一件时的获利情况如表Il所示。问该公司应制造A、B两种家电各多少件，使获取的利润为最大。,分析和表述问题,3、列出表述问题的各种基本要素，并确定各要素之间的关系。,5x215,6x1 +2x224,x1 +x25,x1 0, x2 0,用数学语言描述,解：用变量x1和x2分别表示美佳公司制造家电I和II的数量。,例2、生产计划问题,A B 备用资源 煤 1 2 30 劳动日 3 2 60 仓库 0 2 24 利润 40 50,max Z= 40 x1 +50 x2,解:设产品A, B产量分别为变量x1 ， x2,例3,求：最低成本的原料混合

6、方案,解：设每单位添加剂中原料i的用量为xi(i =1,2,3,4),minZ= 2x1 + 5x2 +6x3+8x4,线性规划模型特点,决策变量：向量(x1 xn)T 决策人要考虑和控制的因素。非负。 约束条件：线性等式或不等式 目标函数：Z=(x1 xn) 线性式，求Z极大或极小,19,线性规划的一般式,max(min)Z=C1x1+ C2x2+Cnxn,简写为：,用向量形式表示：,线性规划的适用情况,要解决的问题的目标可以用数值指标反映 对于要实现的目标有多种方案可选择 有影响决策的若干约束条件,线性规划标准形式,线性规划的标准形式 目标函数：max 约束条件：= 变量符号：0,（一）一

7、般型,maxZ=c1x1+ c2x2+cnxn,其中 bi 0 (i=1,2,m),线性规划标准型的几种表示法,（二）矩阵型,maxZ=CX AX=b X 0 b0,C=(C1 C2 Cn ),(三) 向量型,P1 x1+ P2 x2 + +Pn xn=b,化标准型,(2)、约束条件,(4)、变量,(1)、目标函数,(3)、右端常数,（1）目标函数,目标函数为求最小值，,令Z = -Z,（2）约束条件,x3为松弛变量,x4为剩余变量,松弛变量或剩余变量在实际问题中分别表示未被充分利用的资源和超出的资源数，均未转化为价值和利润，所以引进模型后它们在目标函数中的系数均为零。,当约束条件为“”时，,

8、当约束条件为“”时，,转化为：maxZ=40 x1+ 50 x2+0 x3 +0 x4+0 x5,例：max Z= 40 x1 +50 x2,松弛变量,例:,剩余变量,（3）右端常数,右端项b0时，只需将等式或不等式两端同乘(1)，则等式右端项必大于零。,（4）变量,a、x 0的情况，,令x1= x1- x1 ,b、x取值无约束的情况。,令x -x。,令x= x-x,c、x两边有约束的情况。,-6+6 x1+6 10+6 令x1 = x1 +6 0 x1 16,将 min Z = -x1+2x2 3x3,化为标准型,例：,解： 令x3 =x4 - x5, 加松弛变量x6,加剩余变量x7, 令Z

9、= -Z,maxZ= x1 2x2 +3x4 3x5,练 习,补充作业、运输问题,从仓库到工厂运送单位原材料的成本，工厂对原材料的需求量，仓库目前库存分别如表所示，求成本最低的运输方案。,设xij为i 仓库运到 j工厂的原棉数量(i 1，2，3， j 1，2，3),minZ= 2x11 + x12+3x13+2x21 +2x22 +4x23 +3x31 +4x32 +2x33,线性规划的图解法,定义1：满足约束(1)、(2)的X=(x1 xn)T称为LP问题的可行解，全部可行解的集合称为可行域。,定义2：满足(3)的可行解称为LP问题的最优解.,1、判别线性规划问题的求解结局； 2、是在存在最

10、优解的条件下，找出问题的最优解。,1、在平面上建立直角坐标系 2、图示约束条件，找出可行域 3、图示目标函数和寻找最优解,图解法求解的目的：,图解法的步骤：,例1、maxZ=40 x1+ 50 x2,(1)、建立坐标系,x1+2x2 30 x1+2x2 =30 (0,15) (30,0),3x1+2x2 =60 (0,30) (20,0),2x2 =24,X1+2X2 30 3X1+2X2 60 2X2 24 X1 , X2 0,x1 0 x1 =0 (纵) x2 0 x2=0 (横),(2)、确定可行域,解：,maxZ=40 x1+ 50 x2,(3)、求最优解,解：x1 = 15, x2

11、= 7.5,Z=40 x1+50 x2 0=40 x1+50 x2 (0,0)， (10,-8),maxZ =975,maxZ=40 x1+ 50 x2,最优解：BC线段 B点 C点 x(1)=(6,12) x(2)=(15,7.5) x= x(1)+(1-) x(2) (0 1),求解,maxZ=1200,无界解 无有限最优解,无解 无可行解,max z=x1+3x2 x1+ x26 s.t. -x1+2x28 x1 0, x20,练 习,max z=x1+3x2 s.t. x1+ x26 -x1+2x28 x1 0, x20,可行域,目标函数等值线,最优解,6,4,-8,6,0,x1,x2

12、,练 习,由图解法得到的启示,(1)、线性规划问题的解的情况有四种：唯一最优解；无穷多最优解；无界解；无可行解。,(3)、若有最优解，定可在可行域的顶点得到。,(2)、若线性规划可行域存在，则可行域是一个凸集。,(4)、解题思路是找出凸集的各顶点的最大目标函数值。,线性规划解的情况,当目标函数的直线族与某约束条件直线平行，且该问题有解时。,线性规划解的情况,有解但可行域可伸展到无穷时,线性规划解的情况,约束条件直线无公共区域。,线性规划的单纯形法,一、线性规划的基本概念 二、单纯形法的迭代原理 三、单纯形法的计算步骤 四、单纯形法的进一步讨论 五、单纯形法小结,n阶行列式定义为n阶方阵A中所有

13、取自不同行不同列的n个元素的乘积的代数和。,线性规划的相关概念,线性规划的相关概念,矩阵的秩矩阵A中，不为零的子式的最高阶数，称为矩阵A的秩。,逆设有n阶方阵A，如果存在n阶方阵B，满足AB=BA=E，则称A阵是可逆的，且称B是A的逆矩阵。,线性规划的相关概念,矩阵的初等变换： （1）对调矩阵的两行或两列； （2）以非零数k乘矩阵的某一行（列）的所有元素； （3）以数k乘矩阵的某行（列）的所有元素加到另一行（列）的对应元素上去。,对方程组的系数矩阵A作初等行变换，得到新的方程组与原方程组同解。,基(基阵) 设A为约束方程组的mn阶系数矩阵, (nm)，设其秩为m，B是矩阵A中的一个mm阶的满秩

14、子矩阵，称B是线性规划问题的一个基。,线性规划的基本概念,如果矩阵A的满秩子矩阵不是唯一的， 则基阵也是不唯一的,基向量基阵B中的每一个列向量Pj称为基向量， 基变量与基向量对应的变量称为基变量， 非基变量基变量外的其他变量称为非基变量。,线性规划的基本概念,x1 x2 x3 x4 x5 x6,x4 x5 x6,线性规划的基本概念,可行解满足方程约束条件的解X（x1，x2，xn)T, 称为线性规划问题的可行解。全部可行解的集合称为可行域。,线性规划的基本概念,AX=b的求解,BXB +NXN=b BXB =b-NXN B-1 BXB = B-1 （b-NXN） XB = B-1 b - B-1

15、N XN,A=(B N) X=(XB XN )T,1.若XN0，,2.若同时B为单位矩阵，,则 XB = b， 即X=(b，0)为AX=b的一个解,基本解对应于基B，X= 为AX=b的一个解，则 X为线性规划问题的基本解或基解。,B-1 b 0,线性规划的基本概念,基本可行解基B，基本解X= ，若B-1 b0，称基解为基本可行解，也称基可行解。,可行基对应于基可行解的基称为可行基。,线性规划的基本概念,最优解使目标函数达到最大值的可行解， 称为最优解。,基变量x1、x2、x3，非基变量x4、x5、x6,基础解为（x1，x2，x3，x4，x5，x6）=（5，3，1，0，0，0） 是基础可行解，表

16、示可行域的一个极点。 目标函数值为：z=20,基变量x1、x2、x4，非基变量x3、x5、x6,基础解为 （x1，x2，x3，x4，x5，x6）=（27/5，12/5，0，2/5，0，0） 是基础可行解，表示可行域的一个极点。 目标函数值为：z=18,基变量x1、x2、x5，非基变量x3、x4、x6,基础解为（x1，x2，x3，x4，x5，x6）=（6，3，0，0，-3，0） 是基础解，但不是可行解，不是一个极点。,基变量x1、x2、x6，非基变量x3、x4、x5,基础解为（x1，x2，x3，x4，x5，x6）=（3，4，0，0，0，4） 是基础可行解，表示可行域的一个极点。 目标函数值为：z

17、=18,基变量x2、x3、x4，非基变量x1、x5、x6,基础解为 （x1，x2，x3，x4，x5，x6）=（0，21/2，27/2，-30，0，0） 是基础解，但不是可行解。,基变量x1、x2、x3，非基变量x4、x5、x6,基础解为（x1，x2，x3，x4，x5，x6）=（0，3，6，0，15，0） 是基础可行解，表示可行域的一个极点。 目标函数值为：z=15,基变量x1、x2、x3，非基变量x4、x5、x6,基础解为 （x1，x2，x3，x4，x5，x6）=（0，11/2，-3/2，0，0，10） 是基础解但不是可行解。, 基本解中最多有m个非零分量。,定理1：线性规划问题的可行域一定是

18、凸集。 定理2: 若线性规划问题有最优解,一定存在 一个 基可行解是最优解。 定理3: 若线性规划问题有最优解，一定存在 一个基可行解是最优解。,线性规划的基本定理,基阵B,非基阵N,求出一个基本解，并判断是不是可行解？,令X1 = X2 =0, 则 X3=30, X4=60, X5=24,求出基变量是x1 , x3 , x4的基本解，是不是可行解？,X=(1, 0, 3/2, 3/2)T 是 基本可行解,单纯形法的迭代原理,找出一个基可行解,判断是否最优,转换到相邻的基可行解,找到最优解,否,是,一、确定初始基可行解,线性规划问题的标准型总存在一个单位矩阵（P1,P2,Pm)。 当约束条件为

19、时，加上松驰变量的系数矩阵即为单位矩阵。 当约束条件为或时，可以构造人工变量，人为产生一个单位矩阵。 基向量、基变量、非基向量、非基变量 X=(x1,x2,xm,0,0)T ,即为初始基可行解。,p1 p2 pm pm+1 pj pn,二、基可行解的转换,两个基可行解相邻指的是它们之间变换且仅变换一个基变量。,对应的系数矩阵的增广矩阵为:,设X(0)=(x10,x20,xm0 , 0,0)T，则有,两边乘上一个正数0，得,因为线性规划标准型满足,存在：,令,所以X(1)是可行解。这样就实现了从X(0)到X(1)的转换。,所以得到另一个点X(1) ,有,三、最优性检验和解的判别,将基本可行解X（

20、0）和X（1）分别代入目标函数得：,当所有的j0时， 现有基可行解为最优解。 当所有的j0时，又对某个非基变量xj,有j=0， 则有无穷多最优解。 当存在某个j0，又Pj0,则有无界解。 所有j0时， 如基变量中仍含有非零的人工变量， 表明问题无可行解。,单纯形法计算步骤,单纯形表 特点： （直观.便于理解计算关系.功能与增广矩阵相似）,增广矩阵,单纯形表：,maxZ=c1x1+ c2x2+cnxn,c1 c2 cm,x1 x2 xm,b1 b2 bm,1) 找出初始基可行解，建立单纯形表。,5） 以al,k为主元素进行旋转运算， 转2 ）.,计算步骤：,例题：用单纯形法求解线性规划问题,解：

21、 1、先将上述问题化成标准形式有,找到一个初始基可行解,X=(0,0,15,24,5)T,2、列初始单纯形表：,X1进基；,X4出基；,x1,2,3、列新单纯形表：,X2进基；,X5出基；,x2,1,4、列新单纯形表：,解为：X=(7/2,3/2,15/2,0,0)。,目标函数值为: maxZ=2x1+x2+0 x3+0 x4+0 x5 =27/2+13/2+015/2+0+0=8.5,解：,练习题,原问题化为标准型,列初始单纯形表,列初始单纯形表,X2入基，,X6出基,作业：,人工变量法,当化为标准形后的约束条件的系数矩阵中不存在单位矩阵时，可以人为地增加变量，在最优解中人工变量取值必须为零

22、。为此，令目标函数中人工变量的系数为任意大的负值M。这种人为增加变量的方法称为人工变量法，亦称大M法。,例1：,Max z= 6x1 +4x2,2x1 +3x2 100 4x1 +2x2 120 x1 =14 x2 22 x1 ,x2 0,解：,化成标准型,maxZ=6x1+4x2,2x1 +3x2 +x3 =100 4x1 +2x2 +x4 =120 x1 =14 x2 - x5 = 22 x1 x7 0,加人工变量,+x6,+x7,-Mx6 -Mx7,列初始单纯形表,6 4 0 0 0 - M - M CB xB b x1 x2 x3 x4 x5 x6 x7 0 x3 100 2 3 1

23、0 0 0 0 0 x4 120 4 2 0 1 0 0 0 -M x6 14 1 0 0 0 0 1 0 -M x7 22 0 1 0 0 -1 0 1 -36 M M +6 M +4 0 0 - M 0 0,Cj,0 x3 72 0 3 1 0 0 -2 0 0 x4 64 0 2 0 1 0 -4 0 6 x1 14 1 0 0 0 0 1 0 -M x7 22 0 1 0 0 -1 0 1 84-22M 0 M+4 0 0 -M 6-M 0,Cj,0 x3 6 0 0 1 0 (3) -2 -3 0 x4 20 0 0 0 1 2 -4 -2 6 x1 14 1 0 0 0 0 1 0

24、 4 x2 22 0 1 0 0 -1 0 1 172 0 0 0 0 4 6-M 4-M 0 x5 2 0 0 1/3 0 1 -2/3 -1 0 x4 16 0 0 -2/3 1 0 -8/3 0 6 x1 14 1 0 0 0 0 1 0 x2 24 0 1 1/3 0 0 -2/3 -2 180 0 0 -4/3 0 0 -M-10/3 -M,6 4 0 0 0 - M - M CB xB b x1 x2 x3 x4 x5 x6 x7,解为：X=(14,24,0,16,2)。,目标函数值为: maxZ=6x1+4x2 =614+424=180,练 习,用大M法求解下列问题：,两阶段法,

25、对添加人工变量后的线性规划问题分两个阶段来计算，称为两阶段法。,两阶段法,第一阶段是先求解一个目标函数中只包含人工变量的线性规划问题，即令目标函数中其它变量的系数取零，人工变量的系数取某个正的常数(一般取1)，在保持原问题约束条件不变的情况下求这个目标函数极小化时的解。,作辅助问题,原问题,两阶段法,在第一阶段中，当人工变量取值为0时，目标函数值也为0。这时候的最优解就是原线性规划问题的一个基可行解。如果第一阶段求解结果最优解的目标函数值不为0，也即最优解的基变量中含有非零的人工变量，表明原线性规划问题无可行解。,解题过程：,第1阶段：解辅助问题当进行到最优表时， 若W=0, 则得到原问题的一

26、个 基本可行解，转入第2阶段。 若W0, 则判定原问题无可行解。,第2阶段：去除人工变量，求解原问题。第一阶段的最优解为原问题的初始基可行解。,maxZ= -x1 +2x2,x1 +x2 2 -x1 +x2 1 x2 3 x1 x2 0,例：,x1 +x2 -x3 =2 -x1 +x2 -x4 =1 x2 +x5 =3 x1 x5 0,1.化标准型：,maxZ= -x1 +2x2,+x6,+x7,2.增加人工变量，构造单位矩阵：,x6, x7 0,3. 建立只包含人工变量的辅助问题。,minW=x6 +x7,x1 +x2 -x3 +x6 =2 -x1 +x2 -x4 +x7 =1 x2 +x5 =3 x1 x7 0,3,0 0 0 0 0 1 1 CB xB b x1 x2 x3 x4 x5 x6 x7 1 x6 2 1 1 -1 0 0 1 0 1 x7 1 -1 (1) 0 -1 0 0 1 0 x5 3 0 1 0 0 1 0 0 3 0 -2 1 1 0 0 0,0 x1 1/2 1 0 -1/2 1/2 0 1/2 -1/2 0 x2 3/2 0 1 -1/2 -1/2 0 1/2 1/2 0 x5 3/2 0 0 -1/2 1/2 1 -1/2 -1/2 0 0 0 0 0 0 1 1,1 x6 1 2 0 -1 1 0 1 -1 0 x2 1 -1 1 0 -1