管理运筹学线性规划.ppt

管理运筹学,线性规划,2,第一讲 线性规划,第一章 线性规划的数学模型 第一节 线性规划一般模型 第二节 线性规划的图解法 第三节 线性规划的标准型 第四节 线性规划解的概念 第二章 线性规划的单纯形法 第一节 单纯形法原理 第二节 表格单纯形法 第三节 人工变量问题 第四节 单纯形法补遗 第三章 线性规划的对偶理论 第四章 线性规划灵敏性分析,3,第一章 线性规划的数学模型,线性规划 Linear Programming LP 规划论中的静态规划 解决有限资源的最佳分配问题 求解方法： 图解法 单纯形解法,4,第一章 线性规划的数学模型,第一节 线性规划一般模型 第二节 线性规划的图解法 第三节 线性规划的标准型 第四节 线性规划解的概念,5,第一节 线性规划一般模型,一、线性规划问题的三个要素,决策变量 决策问题待定的量值称为决策变量。 决策变量的取值要求非负。 约束条件 任何问题都是限定在一定的条件下求解，把各种限制条件表示为一组等式或不等式，称之为约束条件。 约束条件是决策方案可行的保障。 LP的约束条件，都是决策变量的线性函数。 目标函数 衡量决策方案优劣的准则，如时间最省、利润最大、成本最低。 目标函数是决策变量的线性函数。 有的目标要实现极大，有的则要求极小。,6,第一节 线性规划一般模型,例1. 生产计划问题 某厂生产、两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，以及资源的限制，相关数据如表所示： 问如何安排、两产品的产量，使利润为最大。,二、线性规划模型的构建,7,第一节 线性规划一般模型,(1)决策变量。要决策的问题是、两种产品的产量，因此有两个决策变量：设x1为产品产量，x2为产品产量。 (2)约束条件。生产这两种产品受到现有生产能力的制约，原料用量也受限制。 设备的生产能力总量为300台时，则约束条件表述为 x1 +x2 300 A、B两种原材料约束条件为 2x1 + x2 400 x2 250,建立模型,8,第一节 线性规划一般模型,(3)目标函数。目标是利润最大化，用Z表示利润，则 maxZ= 50x1 +100 x2 (4)非负约束。 、产品的产量不应是负数，否则没有实际意义，这个要求表述为 x1 0， x2 0,9,第一节 线性规划一般模型,某名牌饮料在国内有三个生产厂，分布在城市A1、A2、A3,其一级承销商有4个，分布在城市B1、B2、B3、B4，已知各厂的产量、各承销商的销售量及从Ai到Bj的每吨饮料运费为Cij，为发挥集团优势，公司要统一筹划运销问题，求运费最小的调运方案。,例2. 运输问题,10,第一节 线性规划一般模型,(1)决策变量。设从Ai到Bj的运输量为xij， (2)目标函数。运费最小的目标函数为 minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34 (3)约束条件。产量之和等于销量之和,故要满足： 供应平衡条件,x11+x12+x13+x14=5 x21+x22+x23+x24=2 x31+x32+x33+x34 =3,销售平衡条件,x11+x21+x31=2 x12+x22+x32=3 x13+x23+x33=1 x14+x24+x34=4,非负性约束 xij0 (i=1,2,3；j=1,2,3,4),11,第一节 线性规划一般模型,用一组非负决策变量表示一个决策问题， 存在一定的等式或不等式的线性约束条件， 有一个希望达到的目标，可表示成决策变量的线性函数。可能是最大化，也可能是最小化。 线性规划一般模型的代数式 为：,三、线性规划的一般模型,max(min)Z=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn (,)b1 a21x1+a22x2+a2nxn (,)b2 am1x1+am2x2+amnxn(,)bm x1,x2,xn ()0,12,第二节 线性规划的图解法,图解法即是用图示的方法来求解线性规划问题。 一个二维的线性规划问题，可以在平面图上求解，三维的线性规划则要在立体图上求解，这就比较麻烦，而维数再高以后就不能图示了。,一、图解法的基本步骤,13,第二节 线性规划的图解法,1. 可行域的确定,x1,x2,100,200,300,100,200,300,五边形ABCDO内(含边界)的任意一点 (x1，x2) 都是满足所有约束条件的一个解，称之可行解 。,满足所有约束条件的解的集合，称之为可行域。即所有约束条件共同围城的区域。,400,400,A,B,C,D,O,z=0= 50x1 +100 x2,Z=27500=50x1 +100 x2,14,第二节 线性规划的图解法,2. 最优解的确定,目标函数 Z= 50x1 +100 x2 代表以Z为参数的一族平行线。,等值线：位于同一直线上的点的目标函数值相同。 最优解：可行解中使目标函数最优(极大或极小)的解。 最优值: 取最优解时对应的目标函数值,15,第二节 线性规划的图解法,由线性不等式组成的可行域是凸集(凸集的定义是：集合内部任意两点连线上的点都属于这个集合)。 可行域有有限个顶点。设规划问题有n个变量，m个约束，则顶点的个数不多于Cnm个。 目标函数最优值一定在可行域的边界达到，而不可能在其内部。,二、几点说明,16,第二节 线性规划的图解法,三 、解的可能性,唯一最优解：只有一个最优点。 多重最优解：无穷多个最优解。若在两个顶点同时得到最优解，则它们连线上的每一点都是最优解。,17,第二节 线性规划的图解法,无界解：线性规划问题的可行域无界，使目标函数无限增大而无界。（缺乏必要的约束条件）,三 、解的可能性（续）,18,第二节 线性规划的图解法,无可行解：若约束条件相互矛盾，则可行域为空集,三 、解的可能性（续）,19,第三节 线性规划的标准型,线性规划问题的数学模型有各种不同的形式，如 目标函数有极大化和极小化； 约束条件有“”、“”和“”三种情况； 决策变量一般有非负性要求，有的则没有。 为了求解方便，特规定一种线性规划的标准形式，非标准型可以转化为标准型。标准形式为： 目标函数极大化， 约束条件为等式， 右端常数项bi0， 决策变量非负。,一 、标准型,20,第三节 线性规划的标准型,1. 代数式,二、标准型的表达方式 有代数式、矩阵式：,简记,21,第三节 线性规划的标准型,2. 矩阵式,22,第三节 线性规划的标准型,目标函数极小化问题 minZ=CTX，只需将等式两端乘以 -1 即变为极大化问题。 因为minZ=-max (-Z)=CTX，令Z= -Z，则maxZ=-CX 右端常数项非正 两端同乘以 -1 约束条件为不等式 当约束方程为“”时，左端加入一个非负的松弛变量，就把不等式变成了等式； 当约束条件为“”时，不等式左端减去一个非负的剩余变量(也可称松弛变量)即可。 决策变量xk没有非负性要求 令xk=xk-x k， xk=xk，x k 0，用xk、x k 取代模型中xk,三、非标准型向标准型转化,23,第三节 线性规划的标准型,例1 的标准型,x1 +x3 =8 2x2 +x4 = 12 3x1 +4 x2 +x5= 36 x1, x2 , x3 , x4 , x5 0,maxZ= 3x1 +5 x2 +0x3 +0x4+0x5,24,minZ= x1 +2 x2 +3 x3 x1 +2 x2 + x35 2x1 +3 x2 + x36 -x1 - x2 - x3 -2 x1 0, x30,第三节 线性规划的标准型,25,第三节 线性规划的标准型,标准化2 minZ= x1 +2 (x2-x 2) +3 x3 x1 +2 (x2-x 2) + x35 2x1 +3 (x2-x 2) + x36 - x1 - (x2-x 2) - x3 -2 x1, x2,x 2 , x3 0 标准化3 minZ= x1 +2 (x2-x 2 ) +3 x3 x1 +2 (x2-x 2 ) + x35 2x1 +3 (x2-x 2 ) + x36 x1 + (x2-x 2 ) + x3 2 x1, x2, x 2, x3 0,26,第三节 线性规划的标准型,标准化4 minZ= x1 +2 (x2-x 2) +3 x3 x1 +2 (x2-x 2) + x3+ x4 =5 2x1 +3 (x2-x 2) + x36 x1 + (x2-x 2 ) + x3 2 x1, x2, x 2, x3, x4 0 标准化5 minZ= x1 +2 (x2-x 2) +3 x3 x1 +2 (x2-x 2) + x3+ x4 =5 2x1 +3 (x2-x 2) + x3 - x5 = 6 x1 + (x2-x 2 ) + x3 2 x1, x2, x 2, x3, x4 , x5 0,27,第三节 线性规划的标准型,标准化6 minZ= x1 +2 (x2-x 2) +3 x3 x1 +2 (x2-x 2) + x3+ x4 =5 2x1 +3 (x2-x 2) + x3 - x5 = 6 x1 + (x2-x 2 ) - x3 + x6= 2 x1, x2, x 2, x3, x4 , x5 , x6 0 标准化7 maxZ= -x1 -2 (x2-x 2) - 3x3+0x4+0x5+0x6 x1 +2 (x2-x 2) + x3+ x4 =5 2x1 +3 (x2-x 2) + x3 - x5 = 6 x1 + (x2-x 2 ) - x3 + x6 = 2 x1, x2, x 2, x3, x4 , x5 , x6 0,28,第四节 线性规划解的概念,可行解： 满足约束条件AX=b, X0的解。 最优解： 使目标函数最优的可行解，称为最优解。 基 mn，且m个方程线性无关，即矩阵A的秩为m；根据线性代数定理可知，nm，则方程组有多个解，这也正是线性规划寻求最优解的余地所在。,一、线性规划解的概念,29,第四节 线性规划解的概念,线性方程组的增广矩阵,例1 的标准型 maxZ= 50x1 +100 x2 +0x3 +0x4+0x5 x1 +x2 +x3 =300 2 x1 +2x2 +x4 = 400 x2 +x5= 250 x1, x2 , x3 , x4 , x5 0,x1,x2,x3,x4,x5,单位矩阵,30,第四节 线性规划解的概念,基矩阵： 系数矩阵A中任意m列所组成的m阶非奇异子矩阵，称为该线性规划问题的一个基矩阵。 或称为一个基，用B表示。 称基矩阵的列为基向量，用Pj表示(j=1,2,m) 。不在B中的向量称为非基向量,的基矩阵B最多为C53=10个,P1 P2 P3 P4 P5,31,第四节 线性规划解的概念,基变量： 与基向量Pj相对应的m个变量xj称为基变量， 其余的m-n个变量为非基变量。 基解： 令所有非基变量等于零，对m个基变量所求的解， 对应一个特定的基矩阵能求得一组唯一解，这个对应于基的解称为基解。 结合图解来看，基解是各约束方程及坐标轴之间交点的坐标。,基变量是x3, x4, x5 非基变量是x1, x2 令非基变量x1=x2=0，得到一个基解 x3=300，x4=400， x5=250,32,第四节 线性规划解的概念,基可行解：满足非负性约束的基解称为基可行解。 可行基：对应于基可行解的基，称为可行基。 最优基：最优解对应的基矩阵，称为最优基。,非 可 行 解,可 行 解,基 解,33,第四节 线性规划解的概念,定理1.若线性规划问题存在可行域，则其可行域一定是凸集。 定理2.线性规划问题的基可行解对应可行域的顶点。 定理3.若可行域有界，线性规划的目标函数一定可以在可行域的顶点上达到最优。,二、线性规划的基本定理,线性规划问题可以有无数个可行解，最优解只可能在顶点上达到，而有限个顶点对应的是基可行解，故只要在有限个基可行解中寻求最优解即可。 从一个顶点出发找到一个可行基，得到一组基可行解，拿目标函数做尺度衡量一下看是否最优。 如若不是，则向邻近的顶点转移，换一个基再行求解、检验，如此迭代循环目标值逐步改善，直至求得最优解。,三、线性规划的解题思路,34,第二章 线性规划单纯形法,单纯形法(Simplex Method)是美国人丹捷格 (G.Dantzig)1947年创建的 这种方法简捷、规范，是举世公认的解决线性规划问题行之有效的方法。 单纯形法的表现形式： 代数法 表格法 矩阵法,35,第二章 线性规划单纯形法,第一节 单纯形法原理 第二节 表格单纯形法 第三节 人工变量问题 第四节 单纯形法补遗,36,第一节 单纯形法原理,一、代数解法,x1,x2,x3,x4,x5,非奇异子阵，做为一个基,基变量 x3, x4, x5 非基变量 x1, x2,maxZ= 50x1 +100 x2 +0x3 +0x4+0x5 x1 +x2 +x3 =300 2 x1 +x2 +x4 = 400 x2 +x5= 250 x1, x2 , x3 , x4 , x5 0,37,第一节 单纯形法原理,将基变量用非基变量线性表示，即 x3= 300 - x1 - x2 x4 =400 - 2x1 -x2 x5=250 - x2 令非基变量x1=0，x2=0，找到一个初始基可行解： x1=0， x2 =0，x3 =300，x4 =400， x5 =250 即X0=(0,0,300,400,250) T 一个可行解就是一个生产方案，在上述方案中两种产品都不生产，利润Z=0 。,1. 求初始基可行解,38,第一节 单纯形法原理,确定入基变量 maxZ= 50x1 +100 x2 +0x3 +0x4+0x5 x1 +x2 +x3 =300 2 x1 +x2 +x4 = 400 x2 +x5= 250 从目标函数maxZ= 50x1 +100 x2 +0x3 +0x4+0x5可知： 非基变量x1和x2的系数均为正数，生产哪种产品都会增加利润。 因为x2的系数大于x1的系数，即生产单位乙产品比甲产品利润更高一些，故应优先多生产乙产品，即优先把x2作为入基变量。,2. 第一次迭代,39,第一节 单纯形法原理,确定离基变量 基变量用非基变量线性表示 x3= 300 - x1 - x2 x4 =400 - 2x1 -x2 x5=250 - x2 保持原非基变量x1 =0， x2变成基变量时应保证 x3 , x4, x5非负，即有,2. 第一次迭代（续）,x3 =300- x2 0 x4 = 400 -x2 0 x5=250 - x2 0,则离基变量为x5,40,第一节 单纯形法原理,2. 第一次迭代（续）,主行,主元,进基变量所在列为主列，离基变量所在行为主行,maxZ= 50x1 +100 x2 +0x3 +0x4+0x5 x1 +x2 +x3 =300 2 x1 +x2 +x4 = 400 x2 +x5= 250,41,第一节 单纯形法原理,基变换 进行初等变换，变主元为1，主列为单位列向量。,2. 第一次迭代（续）,-Z+ 50x1 +100 x2 +0x3 +0x4+0x5 = 0 x1 +x2 +x3 =300 2 x1 +x2 +x4 =400 x2 +x5=250,-Z+ 50x1 + 0 x2 +0x3 +0x4-100x5 + 25000 =0 x1 +x3 - x5 =50 2 x1 +x4 - x5 =150 x2 +x5 =250,此时x2 ，x3 ，x4为基变量,初等行变换,42,第一节 单纯形法原理,2. 第一次迭代（续）,将基变量用非基变量线性表示，即 x2=250- x5 x3=50 x1 + x5 x4=150 -2x1+ x5 令非基变量x1=0，x5=0，找到另一个基可行解 x1=0， x2 =250，x3 =50，x4 =150， x5 =0 即X1=(0,250,50,150,0) T 目标函数Z=25000,43,第一节 单纯形法原理,确定入基变量,3. 第二次迭代,目标函数，Z= 50x1 + 0 x2 +0x3 +0x4-100x5 + 25000 非基变量x1的系数1=50（检验数）为正数， 确定x1为入基变量。,-Z+ 50x1 + 0 x2 +0x3 +0x4-100x5 + 25000 =0 x1 +x3 - x5 =50 2 x1 +x4 - x5 =150 x2 +x5 =250,第一次迭代结果,44,第一节 单纯形法原理,确定出基变量,3. 第二次迭代 （续）,x3 = 50 +x5 -x1 0 x2 = 150- 2x1+ x5 0 x4=250 x5 0,基变量用非基变量线性表示 x1=50 +x5 -x1 x2=150- 2x1 + x5 x4=250 x5,保持原非基变量x5 =0， x1变成基变量时应保证 x2 , x3, x5非负，即,对应的x3定为出基变量,45,第一节 单纯形法原理,基变换 变主元为1，主列为单位列向量。,3. 第二次迭代（续）,-Z+ 50x1 + 0 x2 +0x3 +0x4-100x5 + 25000 =0 x1 +x3 - x5 =50 2 x1 +x4 - x5 =150 x2 +x5 =250,-Z+ 0x1 + 0 x2 -50x3 +0x4-50x5 + 27500 =0 x1 +x3 - x5 =50 -2x3 +x4 + x5 =50 x2 +x5 =250,基变量为x1 x2 ， x4,46,第一节 单纯形法原理,3. 第二次迭代（续）,将基变量用非基变量线性表示，即,x1 =50 x3+x5 x2=250- x5 x4=50 +2x3-x5,令非基变量x3=0，x5=0，又找到一个基可行解,目标函数-Z+ 0x1 + 0 x2 -50x3 +0x4-50x5 + 27500 =0,x1=50， x2 =250，x3 =0，x4 =50， x5 =0 即 X2=(50,250,0,50,0)T Z=27500,检验数j非正，得最优解X*=(4,6,4,0,0)T，Z*=42,47,第一节 单纯形法原理,二、单纯形法的几何意义,X0=(0,0,300,400,250)T,X1=(0,250，50，150,0)T,X1=(50,250,0,50,0)T,x1,x2,100,200,300,100,200,300,400,400,A,B,C,D,O,48,第二节 表格单纯形法,表格单纯形法，是对上节讨论的方法步骤进行具体化、规范化、表格化的结果。,一、单纯形法表,49,第二节 表格单纯形法,将线性规划问题化成标准型。 找出或构造一个m阶单位矩阵作为初始可行基，建立初始单纯形表。 计算各非基变量xj的检验数j=Cj-CBPj ，若所有j0，则问题已得到最优解，停止计算，否则转入下步。 在大于0的检验数中，若某个k所对应的系数列向量Pk0，则此问题是无界解，停止计算，否则转入下步。 根据maxjj0=k原则，确定xk为换入变量(进基变量)，再按规则计算：=minbi/aik| aik0=bl/ aik 确定xBl为换出变量。建立新的单纯形表，此时基变量中xk取代了xBl的位置。 以aik为主元素进行迭代，把xk所对应的列向量变为单位列向量，即aik变为1，同列中其它元素为0，转第 步。,二、单纯形法的计算步骤,50,第二节 表格单纯形法,maxZ=3x1 +5 x2 +0x3 +0x4+0x5 =0 x1 + x3 =8 2x2 + x4 =12 3x1 +4 x2 + x5=36,三、单纯形法计算举例,51,第二节 表格单纯形法,52,第二节 表格单纯形法,最优解 :X*=(4,6,4,0,0)T，Z*=42,53,第二节 表格单纯形法,最优基,最优基的逆,最优基和最优基的逆,54,第二节 表格单纯形法,标准化 maxZ= 3x1 +2 x2 -2x1 + x2 + x3 =2 x1 -3 x2 + x4 =3 x1 , x2 , x3, x4 0,此时，检验数2=11 0，还没有得到最优解。 确定x2进基，但x2所在列的系数向量元素非正，无界 值不存在，有进基变量但无离基变量。,55,第三节 人工变量问题,用单纯形法解题时，需要有一个单位阵作为初始基。 当约束条件都是“”时，加入松弛变量就形成了初始基。 但实际存在“”或“”型的约束，没有现成的单位矩阵。,一、人工变量,采用人造基的办法：人工构造单位矩阵 在没有单位列向量的等式约束中加入人工变量，构成原线性规划问题的伴随问题，从而得到一个初始基。 人工变量是在等式中人为加进的，只有它等于0时，约束条件才是它本来的意义。,处理方法有两种： 大M 法 两阶段法,56,第三节 人工变量问题,没有单位矩阵，不符合构造初始基的条件，需加入人工变量 。 人工变量最终必须等于0才能保持原问题性质不变。 为保证人工变量为0，在目标函数中令其系数为-M。 M为无限大的正数，这是一个惩罚项，倘若人工变量不为零，则目标函数就永远达不到最优，所以必须将人工变量逐步从基变量中替换出去。 如若到最终表中人工变量仍没有置换出去，那么这个问题就没有可行解，当然亦无最优解。,大M法,57,第三节 人工变量问题,按大M法构造人造基，引入人工变量x4 , x5 的辅助问题如下： maxZ= 3x1 - x2 -2 x3 -M x4 -M x5 3x1 + 2 x2 -3 x3 + x4 =6 x1 - 2 x2 + x3 + x5 =4 x1 , x2 , x3 , x4 , x5 0,58,第三节 人工变量问题,59,第四节 单纯形法补遗,进基变量相持： 单纯形法运算过程中，同时出现多个相同的j最大。 在符合要求的j(目标为max：j0，min：j0)中，选取下标最小的非基变量为换入变量； 离基变量相持： 单纯形法运算过程中，同时出现多个相同的最小值。 继续迭代，便有基变量为0，称这种情况为退化解。 选取其中下标最大的基变量做为换出变量。 多重最优解： 最优单纯形表中，存在非基变量的检验数j=0。 让这个非基变量进基，继续迭代，得另一个最优解。 无界解： 大于0的检验数中，若某个k所对应的系数列向量Pk0，则解无界。 无可行解： 最终表中存在人工变量是基变量。,60,第三章 对偶理论,若例1中该厂的产品平销，现有另一企业想租赁其设备。厂方为了在谈判时心中有数，需掌握设备台时费用的最低价码，以便衡量对方出价，对出租与否做出抉择。 在这个问题上厂长面临着两种选择：自行生产或出租设备。首先要弄清两个问题： 合理安排生产能取得多大利润? 为保持利润水平不降低，资源转让的最低价格是多少？ 问题 的最优解：x1=4，x2=6，Z*=42。,一、对偶问题 ,61,第三章 对偶理论,第二个问题：出让定价,假设出让A、B、C设备所得利润分别为y1、y2、y3 原本用于生产甲产品的设备台时，如若出让，不应低于自行生产带来的利润，否则宁愿自己生产。于是有 y1+0y2+3y3 3 同理，对乙产品而言，则有 0y1+2y2+4y3 5 设备台时出让的收益（希望出让的收益最少值） min=8y1+12y2+36y3 显然还有 y1，y2，y30,62,第三章 对偶理论,对偶问题的最优解： y1=0，y2=1/2，y3=1，W* =42 两个问题的目标函数值相等，这不是偶然的，上述两个问题实际上是一个问题的两个方面，如果把前者称为线性规划原问题，则后者便是它的对偶问