线性规划与单纯形法(1-4节).ppt

第1页,第二章,线性规划与单纯形法,第2页,在生产管理和经营活动中经常提出以下两类问题： 1.如何利用有限的人力、物力、财力等资源安排生产，使产值最大或利润最高。 2.对给定的任务，如何统筹安排，以便用最少的人力、物力、财力等资源消耗去完成任务。,第3页,对于这种从生产的计划与组织中提出的达到最大收益或最小支付为目的的问题研究，构成了运筹学的一个重要分支数学规划论。,第4页,第一节 线性规划问题及其数学模型 第二节 线性规划问题的图解法 第三节 线性规划问题的标准型 第四节 线性规划问题的解 第五节 线性规划问题的几何意义 第六节 单纯形法的基本原理 第七节 单纯形法的应用 第八节 线性规划在管理方面的应用 第九节 数据包络分析,第5页,第一节 线性规划问题及其数学模型,一、问题的提出,例1 某工厂在计划内要生产I、II两种产品，已知生产单位产品所需的设备台时数、原材料A的消耗量、原材料B的消耗量，具体数据如表所示。,第6页,又知道，每生产一件产品 I 可获利2元，每生产一件产品 II 可获得3元，问应如何安排生产计划才能够使得工厂获利最多？,解：生产计划就是要确定生产产品 I 和 II 各多少件。 故问题的决策变量为需要生产产品I的数量、生产产品II的数量。 设需要生产产品I的数量：x1 设需要生产产品II的数量：x2,第7页,对生产计划（即产品 I 和 II 的生产数量）造成影响的制约因素有三个，分别为： （1）设备台时数限制： x1 + 2x2 8 （2）原材料A的数量限制：4x1 16 （3）原材料B的数量限制： 4x2 12,问题的目标是使得创造的利润达到最大，用 z 表示所创造的利润值，则可表示为： max z = 2x1 + 3x2,第8页,综上所述，建立问题的数学模型为： 目标函数： max z = 2x1 + 3x2,约束条件：,第9页,例2 河流旁建有两个化工厂，两条河流的流量分别为500万立方米/天、200万立方米/天。,工厂 I 排污：2 万立方米/天。 工厂 II 排污：1.4万立方米/天。,第10页,根据环保要求，河流中污水含量不应大于0.2%。 为了达到环保要求，需要进行污水处理。处理方式有两种： （1）河流自然净化：工厂1排出的污水流到工厂2时，20%得到自然净化。 （2）工厂自己进行污水处理： 工厂I 污水处理成本：1000 元/万立方米 工厂II 污水处理成本：800 元/万立方米 问如何制定污水处理计划才能使工厂总污水处理成本最小。,第11页,解：污水处理计划就是要确定工厂 I 和工厂 II 各处理污水多少。 故问题的决策变量为工厂 I 处理的污水、工厂 II 处理的污水。 设工厂I 需处理的污水：x1 万立方米 设工厂II 需处理的污水：x2 万立方米,第12页,对污水处理计划（即工厂I和II的污水处理量）造成影响的制约因素有四个，分别为： （1）工厂I 污水处理量的上限：x1 2 （2）工厂II 污水处理量的上限：x2 1.4 （3）工厂I和II之间河流污水含量的0.2%限制： （2-x1 ）/ 500 0.002,x1 1,第13页,问题的目标是使得污水处理成本最小，用 z 表示污水处理成本，则可表示为： min z = 1000x1 + 800x2,（4）工厂II之后河流污水含量的0.2%限制： 0.8（2-x1）+（1.4 - x2） / 700 0.002,0.8x1 + x2 1.6,第14页,综上所述，建立问题的数学模型为： 目标函数： min z = 1000x1 + 800x2,约束条件：,第15页,二、线性规划问题的特征,从以上两个例子可以看出，它们都属于一类优化问题，它们的共同特征为：,每个问题都用一组决策变量（x1,x2,xn）表示某一方案。这组决策变量的值代表一个具体方案，这些变量一般取值都是非负的。,第16页,存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。 都有一个要求表达的目标，它可用决策变量的线性函数来表示（称为目标函数），按问题的不同，要求目标函数实现最大化或最小化。,第17页,三、线性规划问题的数学模型,满足以上三个条件的数学模型称为线性规划的数学模型：,目标函数 max(min) z=c1x1 + c2x2 + cnxn 约束条件 a11x1 + a12x2 + a1nxn (=,) b1 a21x1 + a22x2 + a2nxn (=,) b2 am1x1 + am2x2 + amnxn (=,) bm x1, x2, , xn 0,第18页,四、线性规划问题数学模型的特点,1. 决策变量正负不限。 2. 约束条件可以为=，即约束条件为决策变量的线性等式或不等式。 3. 每一约束条件右端的常数可为正、负。 4. 目标函数可以要求极大，也可以极小。 5. 目标函数为决策变量的线性函数。,第19页,第二节 线性规划问题的图解法,一、图解法的步骤,对于两个或三个变量的线性规划问题可以用图解法来求解。,在直角坐标系中画出由所有约束条件不等式所组成的公共取值范围。,第20页,该公共取值范围中的每一点都满足所有约束条件，称为线性规划的可行域。 可行域边界上改变方向的点称为可行域的顶点。 可行域中的每一点都满足所有约束条件，称可行域中的每一点为线性规划的可行解。 可行域中使目标函数极大或极小的那个可行解称为最优解。 最优解必然在可行域的顶点上取得。,定 义,第21页,如目标函数为最大化：则把目标函数在直角坐标系中所代表的直线沿法线方向向右上方或左上方平移，直到同图中可行域（公共取值范围）的边界点相交为止，停止平移；,第22页,如目标函数为最小化：则把目标函数在直角坐标系中所代表的直线沿法线方向向右下方或左下方，直到同图中可行域（公共取值范围）的边界点相交为止，停止平移。,定义：位于同一条目标函数所代表的直线上的点具有相同的目标函数值，因而称它为“等值线”。,第23页,求出目标函数直线同可行域相交的边界点坐标值。 该边界值即为问题的最优解，并代入目标函数，求出问题的最优解。,第24页,例：目标函数： max z = 2x1 + 3x2,约束条件：,第25页,解：（1）绘制公共取值范围： x1 + 2x2 8：直线 x1+ 2x2 = 8 的左下方 4x1 16：直线 4x1 = 16 的左方 4x2 12：直线 4x2 = 12 的下方 x10、x20：第1象限,第26页,（2）绘制等值线、并向右上方平移。,x1,x2,4x2 =12,x1 + 2x2=8,4x1 =16,2x1 + 3x2=z,Q,第27页,（3）求出交点坐标 Q（4,2）。,（4）最优解为：x1=4，x2=2。 最优值为：z = 14,第28页,确定约束条件围成的区域； 求出该区域边界点，列表求出目标函数的最优值。,二、图解法的改进步骤,依据线性规划问题的最优解在其可行域的顶点上取得。,第29页,x1,x2,4x2 =12,x1 + 2x2=8,4x1 =16,2x1 + 3x2=z,0,Q1,Q2,Q3,Q4,解：0=(0,0) ；Q1=(4,0)； Q2=(4,2)； Q3=(2,3)；Q4=(0,3),第30页,三、求解结果分析,最优解是唯一的。 无穷多最优解：目标函数直线同某一约束条件直线平行。 无界解：可行域无界。 无可行解：无可行域。,第31页,最优解是唯一的。,目标函数： max z = 2x1 + 3x2,约束条件：,第32页,目标函数： max z = 2x1 + 4x2,约束条件：,无穷多最优解：目标函数直线同某一约束条件直线平行。,第33页,x1,x2,4x2 =12,x1 + 2x2=8,4x1 =16,2x1 + 4x2=z,Q3,Q2,位于线段 Q2Q3 上任意一点都使目标函数 z 取得相同的最大值。,分析：目标函数直线和约束条件x1+2x28的边界线平行。,第34页,目标函数： max z = 2x1 + 3x2,约束条件：,无界解：可行域无界。,第35页,x1,x2,4x2 =12,4x1 =16,x1 + 2x2=8,可行域无界，故最优解无界。,注：可行域无界，可能无最优解，也可能存在最优解，但此时最优解一定在顶点上取得。,第36页,无可行解：无可行域。,目标函数： max z = 2x1 + 3x2,约束条件：,第37页,x1,x2,4x2 =12,x1 + 2x216,4x1 =16,(4,3),无可行域，所以无可行解。,第38页,分 析： 当求解结果出现3、4两种情况时，一般说明线性规划问题的数学模型有错误。 情况 3 可能是因为建模时缺少了某些必要的约束条件。 情况 4 可能是因为建模时出现了矛盾的约束条件。 图解法虽然直观、简便，但当变量数多于 3 个以上时，它就无能为力了。需要借助于后面章节所介绍的一种代数法单纯形法。,第39页,第三节 线性规划问题的标准型,鉴于线性规划问题模型形式的多样性，为了便于求解和讨论，对于一般线性规划问题总是先将它化为标准形式的线性规划问题，然后再予以分析或求解。,第40页,一、线性规划问题的标准型,具有 m 个约束条件和 n 个决策变量的线性规划问题的标准型定义为：,max z=c1x1 + c2x2 + cnxn s.t. a11x1 + a12x2 + a1nxn = b1 a21x1 + a22x2 + a2nxn = b2 am1x1 + am2x2 + amnxn = bm 其中：x1, x2, , xn 0，b1,b2,bm0,形式一（完整形式）,第41页,形式二（简化形式）,第42页,形式三（向量形式）,Max z = CX s.t. AX=b X0 其中：C = (c1,cn) A = ( aij )m n,，i =1, m，j =1, n X= (x1, xn) T b= (b1, bm) T,第43页,目标函数为极大化。 所有约束条件为等式。 所有决策变量限于非负值。 每一约束条件右端的常数为非负值。,实际碰到的各种线性规划问题的数学模型都应变换为标准型后才求解。,二、线性规划问题标准型的四大特点,第44页,三、线性规划问题的非标准型转化为标准型,1、目标函数为极小化：将目标函数乘以 -1 即可化为等价的极大化问题。,Min z = c x,Max z = -c x,第45页,min z = - 2x1 - 3x2,max z = 2x1+ 3x2,解：线性规划模型的标准型为：,第46页,2、约束条件为不等式： （1）约束条件为：在不等式左端加上一个非负的新变量即可化为等式。新增的非负变量称为松弛变量。 （2）约束条件为：在不等式左端减去一个非负的新变量即可化为等式。新增的非负变量称为剩余变量。,第47页,max z = 2x1 + 3x2,max z = 2x1+ 3x2,解：引入松弛变量 x3和 x4，剩余变量 x5。,从而线性规划模型的标准型为：,第48页,3、决策变量不是非负值： （1）决策变量有非正约束：用一新变量（该变量为决策变量的相反数）来代替。,xj 0,引入新变量 xj 0 ，令 xj = -xj； 将 xj 表达式代入线性规划模型，用 xj 替代 xj 。,第49页,max z = 2x1 + 3x2,max z = 2x1 - 3x2,解：引入新变量 x2 0，令 x2 = -x2 。,从而线性规划模型的标准型为：,第50页,（2）决策变量符号不受限制（为自由变量）：用两个非负新变量来代替。,xj 正负不限,引入新变量 xj 0 和 xj 0 ，令 xj = xj- xj ； 将 xj 表达式代入线性规划模型，用 xj 、 xj替代 xj 。,第51页,max z = 2x1 + 3x2,max z = 2x1 + 3x2 3x2”,解：引入新变量 x2 0， x2” 0 ，令 x2 = x2 x2”。,从而线性规划模型的标准型为：,第52页,（3）决策变量有上、下界： 引进新变量使其等于原变量减去下限值，并用新变量替换模型中原变量； 将新变量的上限约束转化为新的约束条件，并化为等式。,a xj b,引入新变量xj，令 xj= xj -a，0 xj b-a； 将 xj 表达式（xj = xj+ a）代入线性规划模型，用 xj 替换 xj ； 将 xj b-a 转为约束，再化为等式。,第53页,max z = 2x1 + 3x2,解：引入新变量 x2 ，令 x2 =x2 2， x2 2,将 x2 = x2 + 2代入模型，用 x2 替代 x2 ：,将 x2 2 转化为约束,第54页,max z = 2x1 3 ( x2 + 2 ),第55页,max z = 2x1 3 x2 + 9,第56页,max z = 2x1 3 x2 + 9,第57页,4、约束条件右端的常数为负：约束两端乘以 -1。,max z = 2x1 + 3x2,解：将第三个约束两端分别乘以 - 1。,从而线性规划模型的标准型为：,max z = 2x1 + 3x2,第58页,第四节 线性规划问题的解,在讨论线性规划问题的求解之前，先要了解线性规划问题的解的概念。,（1）,（2）,（3）,第59页,一、基本定义,可行解满足约束条件（2）和（3）的解X=( x1 , xn) T 称为线性规划问题的可行解。 可行域所有可行解的集合称为可行域。 最优解使目标函数（1）达到最优（最大化问题是使目标函数值最大，最小化问题是使目标函数最小）的可行解称为最优解。,第60页,二、约束方程组系数矩阵 A 的讨论,Max z = C X s.t. A X = b X 0 其中：C = (c1,cn) A = ( aij )m n,，i =1, m，j =1, n X= (x1, xn) T b= (b1, bm) T,第61页,1. 几个概念,（1）向量 由数 a1, a2, , an 组成的有序数组，称为 n 维向量。,a = ( a1, a2, , an ),n 维行向量,n 维列向量,第62页,（2）矩阵的列向量 (m, n) 矩阵 A 的每一列由竖直排列的 m 个变量组成，把它叫做矩阵 A 的一个列向量。,第63页,（3）线性相关,给定向量组 A =(P1, P2, , Pn),则称向量组 A 是线性相关的。,使 k1P1+ k2P2 + + knPn =0,如果存在 n 个不全为零的数 k1, k2, , kn,第64页,（4）线性无关,给定向量组 A =(P1, P2, , Pn),则称向量组 A 是线性无关的。,使 k1P1+ k2P2 + + knPn =0,如果不存在 n 个不全为零的数 k1, k2, , kn,第65页,设向量 (, P1, P2, , Pn),则称可由向量 (P1, P2, , Pn) 线性表示。,如果存在 一组数 k1, k2, , kn,使 =k1P1+ k2P2 + + knPn,（5）向量的线性表示,第66页,定 理：,设向量组 (P1, P2, , Pn) 线性无关,设向量组 (, P1, P2, , Pn) 线性相关,则可由 (P1, P2, , Pn) 线性表示且表达式唯一。,第67页,（6）矩阵的秩,从 (m, n) 矩阵 A 中选取 r 个行 r 个列，这 r 个行 r 个列相关处的元素构成一个 r 阶方阵，它的行列式叫做A 的 r 阶子式。 当 A 的各 r 阶子式中至少有一个不为 0，而 r + 1 阶子式全为0，就说矩阵 A 的秩为 r ，记为 r(A)。,显然 r(A) min m, n。,第68页,（7）矩阵秩和向量线性无关,若矩阵 A 的秩等于 r ，则在列向量（或行向量）中必然有 r 个列向量（或行向量）构成线性无关组，而任意 r+1 个列向量（或行向量）都是线性相关的。,r(A) = A 中最大线性无关列数 = A 中最大线性无关行数,第69页,2. 约束条件方程组系数矩阵 A 的讨论,第70页,约定： (1) m n，即约束条件数少于决策变量数。 (2) r(A) = m，约束条件系数矩阵的秩等于约束方程数。,第71页,下面来论证上述两条约定： (1) m n，即约束条件数少于决策变量数。 (2) r(A) = m，约束条件系数矩阵的秩等于约束方程数。,第72页,m n 的论证 如果m n，约束条件变为了由 m 个相互独立的方程组成的线性方程组，从而可直接求出。故在线性规划问题模型中，约定 m n 。,第73页,r(A)= m 的论证 因为r(A) minm, n = m，所以存在两种情况： r(A) m r(A) = m,第74页,下面来论证 r(A) m 是不正确的。 若 r(A) m，则线性无关的约束条件只有 r(A) 个，其余的 m - r(A) 个约束必然可以由这 r(A) 个线性无关的约束线性表示，所以这 m - r(A)个约束方程为多余的，它们根本起不到约束作用，不应当作为问题的约束条件而存在于模型中，故应将其删去。,第75页,综上所述，对于线性规划问题，均约定： 约束条件数 决策变量数（ m n ） 所有约束条件之间必须线性无关，即约束条件系数矩阵的秩 = 约束条件数（ r ( A ) = m ）,第76页,三、引申定义,设 ( A )m n 是线性规划问题的约束条件系数矩阵，r(A) = m。将 A 表示成列向量的形式，即 A = (P1, P2, ,Pn)，则约束方程可写成：,第77页,又因为 r(A) = m，故 ( P1,P2, Pn) 中有 m 个列向量线性无关，设 B=(P1,P2,Pm) 为 A 中 m 个线性无关的列向量。,1、基 由 ( P1, P2, Pm) 此 m 个线性无关的列向量所构成的矩阵称为线性规划问题的一个基。,基的个数最多为 Cnm 个,第78页,例： max z = x1+x2 s.t. 2x1 + 6x2 + 2x3 + x4 = 10 3x1 + x2 + 2x3 + x4 = 8 x1, x2, x3, x4 0,、,、,、,、,解：系统矩阵中存在的基有：,不构成基,第79页,基变量 基( P1,P2,Pm) 所对应的 m 个变量 (x1, x2, xm ) 称为基变量。 3. 非基变量 其余 n-m 个变量称为非基变量。,第80页,例： max z = x1+x2 s.t. 2x1 + 6x2 + 2x3 + x4 = 10 3x1 + x2 + 2x3 + x4 = 8 x1, x2, x3, x4 0,解：,x1 和 x2,x3 和 x4,选择基,基变量,非基变量,第81页,x1 和 x3,x2 和 x4,选择基,基变量,非基变量,x3 和 x4,x1 和 x2,不构成基,不是基变量,不是非基变量,第82页,由此可知 基变量所对应的系数列向量必须线性无关,第83页,4. 基解 令 (n-m) 个非基变量等于0，并对余下的 m 个基变量求解，所得的解称为基解。 基解中非零分量的数目 m 基解的个数最多为 Cnm 个,第84页,例： max z = x1+x2 s.t. 2x1 + 6x2 + 2x3 + x4 = 10 3x1 + x2 + 2x3 + x4 = 8 x1, x2, x3, x4 0,、,、,、,、,解：,基变量：x1 和 x2,非基变量：x3 和 x4,令 x3= x4=0（非基变量），求得： x =（ 19/8，7/8