第二章线性规划

1、1第二章第二章 线性规划线性规划12LPLPLPMkarmark ？条件（）数学模型（ ）各种解的概念：可行解（重点）基本概念 基本解（难点）基本可行解（重点）最优解基本最优解解的基本性质：四个主要定理图解法实际问题模型大法基本方法 单纯形法（原始单纯形法、人工变量法）两阶段法对偶单纯形法（求解）前提？步骤？修正单纯形法对偶理论进一步讨论灵敏度分析参数规划算法复杂性问题哈奇扬算法、arLPLPLP算法整数运输问题特殊多目标2第二章第二章 线性规划的数学模型线性规划的数学模型 线性规划 Linear Programming LP 规划论中的静态规划 在有限资源的条件下，合理分配和利用资源，以期取

2、得最佳效益的优化方法。 求解方法： 图解法 单纯形解法 3第一部分第一部分 线性规划的数学模型线性规划的数学模型第二章第二章 线性规划线性规划第一节第一节 线性规划一般模型线性规划一般模型第二节第二节 线性规划的图解法线性规划的图解法第三节第三节 线性规划的标准型线性规划的标准型第四节第四节 线性规划解的概念线性规划解的概念第二部分第二部分 线性规划的单纯形法线性规划的单纯形法Homework4 工厂工厂 1 工厂工厂 2 工厂工厂 3 工厂工厂 4 库存库存 仓库仓库 A 2 1 3 5 50 仓库仓库 B 2 2 4 1 30 仓库仓库 C 1 4 3 2 70 需求量需求量 40 50

3、25 35 现有三个仓库（A,B,C）的产品运往四个纺织厂。运费情况如下： 问应当怎样调运使运费最省？问应当怎样调运使运费最省？5一、线性规划问题的三要素一、线性规划问题的三要素 决策变量决策变量 决策问题待定的量值称为决策变量。 决策变量的取值要求非负非负。 约束条件约束条件 任何问题都是限定在一定的条件下求解，把各种限制条件表示为一组等式或不等式，称之为约束条件约束条件。 约束条件是决策方案可行的保障。 LP的约束条件，都是决策变量的线性函数线性函数。 目标函数目标函数 衡量决策方案优劣的准则，如时间最省、利润最大、成本最低。 有的目标要实现极大极大，有的则要求极小极小。 目标函数是决策变

4、量的线性函数线性函数。第一节第一节 线性规划一般模型线性规划一般模型6二、线性规划的定义二、线性规划的定义第一节第一节 线性规划一般模型线性规划一般模型7 某饮料公司在国内有三个生产厂，分布在城市某饮料公司在国内有三个生产厂，分布在城市A1、A2、A3,其一级承销商有其一级承销商有4个，分布在城市个，分布在城市B1、B2、B3、B4，已知各厂的产量、各承销商的销售量及从已知各厂的产量、各承销商的销售量及从Ai到到Bj的每的每吨饮料运费为吨饮料运费为Cij，为发挥集团优势，公司要统一筹划，为发挥集团优势，公司要统一筹划运销问题，求运费最小的调运方案。运销问题，求运费最小的调运方案。 销地销地产地

5、产地B1 B2 B3 B4产量产量A1A2A3 6 3 2 5 7 5 8 4 3 2 9 7523销量销量 2 3 1 4第一节第一节 线性规划一般模型线性规划一般模型二、线性规划模型的构建二、线性规划模型的构建8。 决策的是调运量，因此决策变量为：从Ai到Bj的运输量为xij，。运费最小的目标函数为minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34 。产量之和等于销量之和,故要满足：x11+x12+x13+x14=5x21+x22+x23+x24=2x31+x32+x33+x34 =3 销售平衡条件销售平衡条件x

6、11+x21+x31=2x12+x22+x32=3x13+x23+x33=1x14+x24+x34=4 供应平衡条件供应平衡条件 非负性约束非负性约束 xij0 (i=1,2,3；j=1,2,3,4) 第一节第一节 线性规划一般模型线性规划一般模型9minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34 综上所述，该问题的数学模型表示为综上所述，该问题的数学模型表示为 x11+x12+x13+x14=5x21+x22+x23+x24=2x31+x32+x33+x34 =3x11+x21+x31=2x12+x22+x32=

7、3x13+x23+x33=1x14+x24+x34=4xij0 (i=1,2,3；j=1,2,3,4) s.t.第一节第一节 线性规划一般模型线性规划一般模型subject to10 某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：产品A产品B资源限量劳动力设 备原材料9434510360200300利润元/kg70120第一节第一节 线性规划一般模型线性规划一般模型11 问题：如何安排生产计划，使得获利最多？ 步骤：1、确定决策变量：设生产A产品x1 kg；B产品x2 kg2、确定目标函数：maxZ=70X1+120X23、确定约束条件：劳动力约束

8、 9X1+4X2360 设备约束 4X1+5X2 200 原材料约束3X1+10X2 300 非负性约束X10 X20第一节第一节 线性规划一般模型线性规划一般模型12 用一组用一组非负决策变量非负决策变量表示一个决策问题，表示一个决策问题， 存在一定的等式或不等式的存在一定的等式或不等式的线性约束条件线性约束条件， 有一个希望达到的目标，可表示成决策变量的有一个希望达到的目标，可表示成决策变量的线线性函数性函数。可能是最大化，也可能是最小化。可能是最大化，也可能是最小化。 线性规划一般模型的代数式线性规划一般模型的代数式 为：为：四、线性规划的一般模型四、线性规划的一般模型 max(min)

9、Z=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn (,)b1a21x1+a22x2+a2nxn (,)b2 am1x1+am2x2+amnxn(,)bmx1,x2,xn ()0第一节第一节 线性规划一般模型线性规划一般模型13 用图示的方法来求解线性规划问题。 一个二维的线性规划问题，可以在平面图上求解，三维的线性规划则要在立体图上求解，而维数再高以后就不能图示了。一、图解法的基本步骤一、图解法的基本步骤第二节第二节 LP问题的图解法问题的图解法(1) 可行域的确定可行解(2) 最优解141. 可行域的确定可行域的确定 例例3的数学模型为的数学模型为 maxZ= 3x1 +

10、5 x2 x1 8 2x2 12 3x1 +4 x2 36 x1 0, x2 0S.t.x1 =82x2 =123x1 +4 x2 =36x1x24812369 五边形五边形OABCD内内(含边界含边界)的任意一点的任意一点 (x1，x2) 都是满足所有都是满足所有约束条件的一个解，称之可行解约束条件的一个解，称之可行解 。 满足所有约束条件的解的集合，称之为可行域。即所有约束满足所有约束条件的解的集合，称之为可行域。即所有约束条件共同围城的区域。条件共同围城的区域。第二节第二节 LP问题的图解法问题的图解法152. 最优解的确定最优解的确定Z=30Z=42Z=15 目标函数目标函数 Z= 3

11、x1 +5 x2 代表以代表以Z为参数的一族为参数的一族平行线平行线。x1 =82x2 =123x1 +4 x2 =36x1x24812369 等值线：位于同一直线上的点的目标函数值相同。等值线：位于同一直线上的点的目标函数值相同。 最优解：可行解中使目标函数最优最优解：可行解中使目标函数最优(极大或极小极大或极小)的解的解第二节第二节 LP问题的图解法问题的图解法?16 由线性不等式组成的可行域是凸集(凸集的定义是：集合内部任意两点连线上的点都属于这个集合)。 可行域有有限个顶点。设规划问题有n个变量，m个约束，则顶点的个数不多于Cnm个。 目标函数最优值（如果存在）一定在可行域的边界达到，

12、而不可能在其内部。二、说明二、说明第二节第二节 LP问题的图解法问题的图解法17 例: 求解下列线性规划问题 MaxZ=4X1-3X2 S.T. X1+2X210 X16 X24 X11 X1,X20第二节第二节 LP问题的图解法问题的图解法18X1X1=1X1=6X2=4X2X1+2X2=10ABCDE4X1-3X2=0 MAXZ=4X1-3X2 S.T. X1+2X210 X16 X24 X11 X1,X20X2 0X1 019第二节第二节 LP问题的图解法问题的图解法 唯一最优解唯一最优解：只有一个最优点。 多重最优解多重最优解：无穷多个最优解。若在两个相邻顶点相邻顶点同时得到最优解，则

13、它们连线上的每一点都是最优解。 无界解无界解：线性规划问题的可行域无界，使目标函数无限增大而无界。（缺乏必要的约束条件）。 无可行解无可行解：若约束条件相互矛盾，则可行域为空集。二、解的可能性二、解的可能性20X1X1=1X1=6X2=4X2X1+2X2=10ABCDE4X1-3X2=0 MAXZ=4X1-3X2 S.T. X1+2X210 X16 X24 X11 X1,X20唯一的最优解唯一的最优解X1 0X2 021X1X1=1X1=6X2=4X2X1+2X2=10ABCDE MAXZ=2X1+4X2 S.T. X1+2X210 X16 X24 X11 X1,X202X1+4X2=存在无穷

14、多解存在无穷多解 MAXZ=4X1-3X2 S.T. X1+2X210 X16 X24 X11 X1,X20X1 0X2 022X1X1=1X1=6X2=4X2X1+2X2=0ADE4X1-3X2=0 MAXZ=4X1-3X2 S.T. X1+2X20 X16 X24 X11 X1,X20可行域无界可行域无界 MAXZ=4X1-3X2 S.T. X1+2X210 X16 X24 X11 X1,X20X1 0X2 023X1X1=1X2X1+2X2=104X1-3X2=0 MAXZ=4X1-3X2 S.T. X1+2X2 10 X11 X1,X20 MAXZ=4X1-3X2 S.T. X1+2X

15、210 X16 X24 X11 X1,X20可行域无界可行域无界X1 0X2 024 线性规划问题的数学模型有各种不同的形式，如线性规划问题的数学模型有各种不同的形式，如 目标函数有极大化和极小化；目标函数有极大化和极小化； 约束条件有约束条件有“”、“”和和“”三种情况；三种情况； 决策变量一般有非负性要求，有的则没有。决策变量一般有非负性要求，有的则没有。 为了求解方便，特规定一种线性规划的标准形式，非为了求解方便，特规定一种线性规划的标准形式，非标准型可以转化为标准型。标准形式为：标准型可以转化为标准型。标准形式为： 目标函数极大化，目标函数极大化， 约束条件为等式，约束条件为等式， 右

16、端常数项右端常数项bi0， 决策变量非负。决策变量非负。一一 、标准型、标准型第三节第三节 线性规划的标准型线性规划的标准型251. 标准形式的特点 2. 非标准型向标准型的转化 （1）.目标函数：MAX （1）.MIN （2）.约束方程右端常数：非负 （2）.约束方程右端常数为负值 （3）.变量符号：非负 （3）.变量符号不确定 自由变量 （4）.约束条件：等号 （4）.不等式约束 第三节第三节 线性规划的标准型线性规划的标准型26minZ=X1+3X2 S.T. 6X1+7X28 -X1+3X2-6 X1-X2=3 X10不符合线性规划的标准形式目标函数“极小值”约束方程右端存在负数约束方

17、程还不是等式约束 存在自由变量X2第三节第三节 线性规划的标准型线性规划的标准型271. 代数式代数式二、标准型的表达方式（二、标准型的表达方式（代数式、矩阵式）代数式、矩阵式）maxZ=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxnbm x1,x2,xn 0maxZ= cjxj aijxjbi ( i=1,2,m) xj0 ( j=1,2,n)nj1nj1简记第三节第三节 线性规划的标准型线性规划的标准型282. 矩阵式矩阵式 0. .maxXbAXtsXCZ),(21ncccC价值向量mn

18、mmnnaaaaaaaaaA212222111211技术矩阵mbbbb21资源向量nxxxX21决策向量第三节第三节 线性规划的标准型线性规划的标准型29 minZ=CX，只需将等式两端乘以 -1 即变为极大化问题。 因为minZ=-max (-Z)=CX，令Z= -Z，则maxZ=-CX 两端同乘以 -1 当约束方程为“”时，左端加入一个非负的松弛变量，就把不等式变成了等式； 当约束条件为“”时，不等式左端减去一个非负的剩余变量(也可称松弛变量)即可。 k 令xk=xk-x k，xk 0，x k 0，用xk-x k 取代模型中xk三、非标准型向标准型转化三、非标准型向标准型转化 第三节第三节

19、 线性规划的标准型线性规划的标准型30 y 3 y=f (x) 1 0 2 5 x -1 y = -f (x) -3 kkkxxx转化规则简要：转化规则简要：第三节第三节 线性规划的标准型线性规划的标准型31 例例3 minZ= x1 +2 x2 -3 x3 x1 +2 x2 - x3 5 2x1 +3 x2 - x3 6 -x1 - x2 + x3 -2 x1 0, x3 0S.t.第三节第三节 线性规划的标准型线性规划的标准型 Step-1 minZ= x1 +2 x2 +3 x3 x1 +2 x2 + x35 2x1 +3 x2 + x36 -x1 - x2 - x3 -2 x1 0,

20、x30 S.t.32 Step-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 Step-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第三节第三节 线性规划的标准型线性规划的标准型S.t.S.t.33 Step-4 minZ= x1 +

21、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 Step-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第三节第三节 线性规划的标准型线性规划的标准型S.t.S.t.34 Step-6 minZ= x1 +

22、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 Step-7 maxZ= -x1 -2 (x2-x 2) - 3x3+0 x4+0 x5+0 x6 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

23、0 第三节第三节 线性规划的标准型线性规划的标准型S.t.S.t.35 例例4 maxZ= 3x1 +5 x2 x1 8 2x2 12 3x1 +4 x2 36 x1 0, x2 0S.t.第三节第三节 线性规划的标准型线性规划的标准型 x1 +x3 =8 2x2 +x4 = 12 3x1 +4 x2 +x5= 36 x1, x2 , x3 , x4 , x5 0 maxZ= 3x1 +5 x2 +0 x3 +0 x4+0 x5 S.t.标准型标准型作作 业业 ： 1、教材后作业9（建立数学模型） 2、教材后作业1（化标准型） 3、教材后作业2的（图解法）37第四节第四节 LP问题的基本性质问

24、题的基本性质一一LP解的基本概念解的基本概念 可行解：可行解： 满足约束条件AX=b, X0的解。 最优解最优解： 使目标函数最优的可行解，称为最优解。 基基 n元线性约束方程组，m个方程线性无关； 即矩阵A的秩R(A)=m；根据线性代数定理可知，nm，则方程组有多个解，这也正是线性规划寻求最优解的余地所在。 ?秩的定义秩的定义n元线性方程组元线性方程组Ax=b解的讨论解的讨论X1X1=1X1=6X2=4X2X1+2X2=10ABCDE MAXZ=4X1-3X2 S.T. X1+2X210 X16 X24 X11 X1,X20X2 0X1 0可行域可行解39 线性方程组的增广矩阵 例例1 的标

25、准型的标准型 maxZ= 3x1 +5 x2 +0 x3 +0 x4+0 x5 x1 +x3 =8 2x2 +x4 = 12 3x1 +4 x2 +x5= 36 x1, x2 , x3 , x4 , x5 036101201800043020101Ax1x2x3x4x5第四节第四节 LP问题的基本性质问题的基本性质40 基（基矩阵）基（基矩阵）： 系数矩阵系数矩阵A中任意中任意m列所组成的列所组成的m阶非奇异子矩阵，称为该线性阶非奇异子矩阵，称为该线性规划问题的一个基矩阵。规划问题的一个基矩阵。 或称为一个基，用或称为一个基，用B表示。表示。 称基矩阵的列为基向量，用称基矩阵的列为基向量，用P

26、j表示表示(j=1,2,m) 。100100043020101A的基矩阵的基矩阵B最多最多C53=10，如下：，如下：100010001x3x4x5103010001x1x4x5104012000 x2x4x5130000011x3x1x5140020001x3x2x5300010101x3x4x1400210001x3x4x2043020101x1x2x5x1x2x4043120001x1x2x5143020001第四节第四节 LP问题的基本性质问题的基本性质?41 基变量：基变量： 与基向量Pj相对应的m个变量xj称为基变量， 其余的m-n个变量为非基变量。 基解：基解： 令所有非基变量等

27、于零，对m个基变量所求的解， 对应一个特定的基矩阵能求得一组唯一解，这个对应于基的解称为基解。 结合图解来看，基解是各约束方程及坐标轴之间交点的坐标。 100010001Bx3x4x5基变量是基变量是x3, x4, x5非基变量是非基变量是x1, x2令非基变量令非基变量x1=x2=0，得到一个基解，得到一个基解 x3=8，x4=12， x5=36第四节第四节 LP问题的基本性质问题的基本性质42 基可行解：基可行解：满足非负性约束的基解称为基可行解。 可行基：可行基：对应于基可行解的基，称为可行基。 最优基：最优基：最优解对应的基矩阵，称为最优基。 非可行解可行解基解基可行解第四节第四节 LP问题的基本性质问题的基本性质43例2-2 某线性规划问题的约束方程为 X1+3X2+4X3+X4=8 2X1+2X2+X3+X5=1 Xj0, j=1,2,3,4,5nmnmmnPPPaaaaaaA, 212111211A为为m n矩阵（矩阵（ m为约束方程个