第一章-线性规划课件

武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第一讲第一讲 线性规划线性规划1武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第一章第一章 线性规划的数学模型线性规划的数学模型 线性规划线性规划 Linear Programming LP规划论中的静态规划规划论中的静态规划解决有限资源的最佳分配问题解决有限资源的最佳分配问题求解方法：求解方法：图解法图解法单纯形解法单纯形解法 2武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第一章第一章 线性规划的数学模型线性规划的数学模型3武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第一节第一节 线性规划一般模型线性规划一般模型一、线性规划问题的三个要素一、线性规划问题的三个要素 决策变量决策变量决策决策问题待定的量值称为决策变量。问题待定的量值称为决策变量。决策变量的取值要求非负。决策变量的取值要求非负。约束条件约束条件任任何何问问题题都都是是限限定定在在一一定定的的条条件件下下求求解解，把把各各种种限限制制条条件件表表示示为一组等式或不等式，称之为约束条件。为一组等式或不等式，称之为约束条件。LP的约束条件，都是决策变量的线性函数。的约束条件，都是决策变量的线性函数。目标函数目标函数衡量决策方案优劣的准则，如时间最省、利润最大、成本最低。衡量决策方案优劣的准则，如时间最省、利润最大、成本最低。目标函数是决策变量的线性函数。目标函数是决策变量的线性函数。有的目标要实现极大，有的则要求极小。有的目标要实现极大，有的则要求极小。4武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第一节第一节 线性规划一般模型线性规划一般模型例例例例1.1.生产计划问题生产计划问题生产计划问题生产计划问题 某某厂厂生生产产甲甲乙乙两两种种产产品品，各各自自的的零零部部件件分分别别在在A、B车车间间生产，最后都需在生产，最后都需在C车间装配，相关数据如表所示：车间装配，相关数据如表所示：问如何安排甲、乙两产品的产量，使利润为最大。问如何安排甲、乙两产品的产量，使利润为最大。二、线性规划模型的构建二、线性规划模型的构建 产品车间工时单耗甲 乙生产能力ABC 1 0 0 2 3 48 1236单位产品获利 3 55武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第一节第一节 线性规划一般模型线性规划一般模型(1)(1)决决决决策策策策变变变变量量量量。要要决决策策的的问问题题是是甲甲、乙乙两两种种产产品品的的产产量量，因因此此有有两两个个决决策策变变量量：设设x1为为甲甲产产品品产产量量，x2为为乙乙产产品品产产量量。(2)(2)约约约约束束束束条条条条件件件件。生生产产这这两两种种产产品品受受到到现现有有生生产产能能力力的的制制约约，用量不能突破。用量不能突破。生产单位甲产品的零部件需耗用生产单位甲产品的零部件需耗用A车间的生产能力车间的生产能力1工时，工时，生产单位乙产品不需耗用生产单位乙产品不需耗用A车间的生产能力，车间的生产能力，A车间的能力总量为车间的能力总量为8工时工时，则，则A车间能力约束条件表述为车间能力约束条件表述为 x1 8同理，同理，B和和C车间能力约束条件为车间能力约束条件为 2x2 12 3x1+4 x2 36建立模型建立模型6武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第一节第一节 线性规划一般模型线性规划一般模型(3)(3)目标函数目标函数目标函数目标函数。目标是利润最大化，用目标是利润最大化，用Z表示利润，则表示利润，则 maxZ=3x1+5 x2(4)(4)非非非非负负负负约约约约束束束束。甲甲乙乙产产品品的的产产量量不不应应是是负负数数，否否则则没没有有实实际际意义，这个要求表述为意义，这个要求表述为 x1 0，x2 0综上所述，该问题的数学模型表示为综上所述，该问题的数学模型表示为 maxZ=3x1+5 x2 x1 8 2x2 12 3x1+4 x2 36 x1 0,x2 07武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第一节第一节 线性规划一般模型线性规划一般模型 某某名名牌牌饮饮料料在在国国内内有有三三个个生生产产厂厂，分分布布在在城城市市A1、A2、A3,其其一一级级承承销销商商有有4个个，分分布布在在城城市市B1、B2、B3、B4，已已知知各各厂厂的的产产量量、各各承承销销商商的的销销售售量量及及从从Ai到到Bj的的每每吨吨饮饮料料运运费费为为Cij，为为发发挥挥集集团团优优势势，公公司司要要统统一筹划运销问题，求运费最小的调运方案。一筹划运销问题，求运费最小的调运方案。例例例例2.2.运输问题运输问题运输问题运输问题 销地产地B1 B2 B3 B4产量A1A2A3 6 3 2 5 7 5 8 4 3 2 9 7523销量 2 3 1 48武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第一节第一节 线性规划一般模型线性规划一般模型(1)(1)决策变量决策变量决策变量决策变量。设从设从Ai到到Bj的运输量为的运输量为xij，(2)(2)目标函数目标函数目标函数目标函数。运费最小的目标函数为运费最小的目标函数为minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34(3)(3)约束条件约束条件约束条件约束条件。产量之和等于销量之和产量之和等于销量之和,故要满足故要满足：供应平衡条件供应平衡条件x11+x12+x13+x14=5x21+x22+x23+x24=2x31+x32+x33+x34=3销售平衡条件销售平衡条件x11+x21+x31=2x12+x22+x32=3x13+x23+x33=1x14+x24+x34=4非负性约束非负性约束 xij0 (i=1,2,3；j=1,2,3,4)9武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE例例例例3 3 有四项工作分给有四项工作分给有四项工作分给有四项工作分给4 4个人个人个人个人 效率表如下。（整数规划之效率表如下。（整数规划之效率表如下。（整数规划之效率表如下。（整数规划之0-10-1规划）规划）规划）规划）工作工作工人工人ABCD甲甲6231乙乙7432丙丙81073丁丁775410武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE 要求合理分配，使总效率最大要求合理分配，使总效率最大要求合理分配，使总效率最大要求合理分配，使总效率最大 （i=1.2.3.4 j=1.2.3.4)2.约束条件约束条件 每个人只任一项工作每个人只任一项工作 解：1.确定决策变量11武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE 每项工作必由一人承担每项工作必由一人承担 3目标函数。目标函数。12武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE例例4：合理下料问题：合理下料问题 在在180cm材料上，需切割三种毛坯材料上，需切割三种毛坯（70cm、52cm、35cm），），其需要量其需要量分别为分别为100、150、100根，问如何切割，根，问如何切割，余料最省？余料最省？13武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE下料方式下料方式一一二二三三四四五五六六七七八八零件零件需需要要量量A 70cm21110000100B52cm02103210150C35cm10130235100余料余料5623524623514武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE 决策变量决策变量决策变量决策变量jj第第第第j j种下料方式的次数，种下料方式的次数，种下料方式的次数，种下料方式的次数，J=1.2,J=1.2,，8 8。约束条件：约束条件：A：B：C：目标函数：余料最省。目标函数：余料最省。15武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第一节第一节 线性规划一般模型线性规划一般模型用一组非负决策变量表示一个决策问题，用一组非负决策变量表示一个决策问题，存在一定的等式或不等式的线性约束条件，存在一定的等式或不等式的线性约束条件，有一个希望达到的目标，可表示成决策变量的线性有一个希望达到的目标，可表示成决策变量的线性函数。可能是最大化，也可能是最小化。函数。可能是最大化，也可能是最小化。线性规划一般模型的代数式线性规划一般模型的代数式 为：为：三、线性规划的一般模型三、线性规划的一般模型 max(min)Z=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn (,)b1a21x1+a22x2+a2nxn (,)b2 am1x1+am2x2+amnxn(,)bmx1,x2,xn()016武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第二节第二节 线性规划的图解法线性规划的图解法 图解法即是用图示的方法来求解线性规划问题。图解法即是用图示的方法来求解线性规划问题。一个二维的线性规划问题，可以在平面图上求解，一个二维的线性规划问题，可以在平面图上求解，三维的线性规划则要在立体图上求解，比较麻烦，三维的线性规划则要在立体图上求解，比较麻烦，而维数再高以后就不能图示了。而维数再高以后就不能图示了。一、图解法的基本步骤一、图解法的基本步骤17武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第二节第二节 线性规划的图解法线性规划的图解法1.可行域的确定可行域的确定例例1的数学模型为的数学模型为 maxZ=3x1+5 x2 x1 8 2x2 12 3x1+4 x2 36 x1 0,x2 0 x1=82x2=123x1+4 x2=36五边形五边形OABCD内内(含边界含边界)的任意一点的任意一点(x1，x2)都是满足所有都是满足所有约束条件的一个解，称之可行解约束条件的一个解，称之可行解。满足所有约束条件的解的集合，称之为可行域。即所有约束满足所有约束条件的解的集合，称之为可行域。即所有约束条件共同围成的区域。条件共同围成的区域。18武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第二节第二节 线性规划的图解法线性规划的图解法2.最优解的确定最优解的确定Z=30Z=42Z=15目标函数目标函数 Z=3x1+5 x2 代表以代表以Z为参数的一族平行线。为参数的一族平行线。x1=82x2=123x1+4 x2=36等值线：位于同一直线上的点的目标函数值相同。等值线：位于同一直线上的点的目标函数值相同。最优解：可行解中使目标函数最优最优解：可行解中使目标函数最优(极大或极小极大或极小)的解的解19武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第二节第二节 线性规划的图解法线性规划的图解法由由线线性性不不等等式式组组成成的的可可行行域域是是凸凸集集(凸凸集集的的定定义义是是：集合内部任意两点连线上的点都属于这个集合集合内部任意两点连线上的点都属于这个集合)。目目标标函函数数最最优优值值一一定定在在可可行行域域的的边边界界达达到到，而而不不可可能在其内部。能在其内部。二、几点说明二、几点说明20武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第二节第二节 线性规划的图解法线性规划的图解法三三、解的可能性、解的可能性x1=82x2=123x1+4 x2=36例例1的数学模型变为的数学模型变为 maxZ=3x1+4 x2 x1 8 2x2 12 3x1+4 x2 36 x1 0,x2 0Z=24Z=36Z=12唯一最优解：只有一个最优点。唯一最优解：只有一个最优点。多多重重最最优优解解：无无穷穷多多个个最最优优解解。若若在在两两个个顶顶点点同同时时得到最优解，则它们连线上的每一点都是最优解。得到最优解，则它们连线上的每一点都是最优解。21武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第二节第二节 线性规划的图解法线性规划的图解法无无界界解解：线线性性规规划划问问题题的的可可行行域域无无界界，使使目目标标函函数数无限增大而无界。（缺乏必要的约束条件）无限增大而无界。（缺乏必要的约束条件）三三、解的可能性（续）、解的可能性（续）例如例如 maxZ=3x1+2 x2 -2x1+x2 2 x1-3 x2 3 x1 0,x2 0-2x1+x2=2x1-3 x2=3Z=6Z=1222武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第二节第二节 线性规划的图解法线性规划的图解法无可行解：若约束条件相互矛盾，则可行域为空集无可行解：若约束条件相互矛盾，则可行域为空集三三、解的可能性（续）、解的可能性（续）例如例如 maxZ=3x1+2 x2 -2x1+x2 2 x1-3 x2 3 x1 0,x2 0-2x1+x2=2x1-3 x2=323武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第三节第三节 线性规划的标准型线性规划的标准型线性规划问题的数学模型有各种不同的形式，如线性规划问题的数学模型有各种不同的形式，如目标函数有极大化和极小化；目标函数有极大化和极小化；约束条件有约束条件有“”、“”和和“”三种情况；三种情况；决策变量一般有非负性要求，有的则没有。决策变量一般有非负性要求，有的则没有。为为了了求求解解方方便便，特特规规定定两两种种线线性性规规划划的的标标准准形形式式，非标准型可以转化为标准型。标准形式为：非标准型可以转化为标准型。标准形式为：目标函数极大化（或极小化），目标函数极大化（或极小化），约束条件为等式，约束条件为等式，右端常数项右端常数项bi0，决策变量非负。决策变量非负。一一、标准型、标准型24武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第三节第三节 线性规划的标准型线性规划的标准型1.代数式代数式二、标准型的表达方式二、标准型的表达方式 有代数式、矩阵式：有代数式、矩阵式：MaxZ=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxnbm x1,x2,xn 0简记maxZ=cjxj aijxjbi (i=1,2,m)xj0 (j=1,2,n)25武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第三节第三节 线性规划的标准型线性规划的标准型2.矩阵式矩阵式 26武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第三节第三节 线性规划的标准型线性规划的标准型 目标函数极小化问题目标函数极小化问题目标函数极小化问题目标函数极小化问题 minZ=CTX，只需将等式两端乘以只需将等式两端乘以-1 即变为极大化问题。即变为极大化问题。右端常数项非正右端常数项非正右端常数项非正右端常数项非正 两端同乘以两端同乘以-1 约束条件为不等式约束条件为不等式约束条件为不等式约束条件为不等式当约束方程为当约束方程为“”时，左端加入一个非负的松弛变量，就把不等式时，左端加入一个非负的松弛变量，就把不等式变成了等式；变成了等式；当约束条件为当约束条件为“”时，不等式左端减去一个非负的剩余变量时，不等式左端减去一个非负的剩余变量(也可称也可称松弛变量松弛变量)即可。即可。决策变量决策变量决策变量决策变量x xk k没有非负性要求没有非负性要求没有非负性要求没有非负性要求 令令xk=xk-x k，xk=xk，x k 0，用，用xk、x k 取代模型中取代模型中xk三、非标准型向标准型转化三、非标准型向标准型转化 27武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE 例例1 解解 为自由变量为自由变量28武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE 例例2 解：解：29武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE例例3 minZ=x1+2 x2-3 x3 x1+2 x2-x3 5 2x1+3 x2-x3 6 -x1 -x2 +x3 -2 x1 0,x3 030武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE标准化标准化1 minZ=x1+2 x2+3 x3 x1+2 x2+x35 2x1+3 x2+x36 -x1 -x2 -x3-2 x1 0,x30 第三节第三节 线性规划的标准型线性规划的标准型31武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第三节第三节 线性规划的标准型线性规划的标准型标准化标准化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 032武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第三节第三节 线性规划的标准型线性规划的标准型标准化标准化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 033武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第三节第三节 线性规划的标准型线性规划的标准型标准化标准化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+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 0 34武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第四节第四节 线性规划解的概念线性规划解的概念一、解的概念一、解的概念标准型标准型 1可行解：满足可行解：满足式的解式的解2可行域：所有可行解的集合可行域：所有可行解的集合3最优解：满足最优解：满足的可行解。的可行解。4基本解：基本解：看看式的解，式的解，AX=b35武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE几种情况：几种情况：若若m=n系数矩阵的秩系数矩阵的秩r（A）=n,即即 0，这时方程，这时方程组有维一解。组有维一解。若若mn，r(A)r(A/b)。这时方程组不相容，即无解。这时方程组不相容，即无解。若若mn，r(A)=r(A/b)=mn 这时有无穷多组解。这时有无穷多组解。线性规划的约束方程通常就是这样的，下面讨论。线性规划的约束方程通常就是这样的，下面讨论。36武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE37武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE5基本可行解。基本可行解。若基本解若基本解 中中 即即X0，满足满足式，称基本可行解。式，称基本可行解。38武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第四节第四节 线性规划解的概念线性规划解的概念 非可行解可行解基解39武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE二、凸集和极点二、凸集和极点二、凸集和极点二、凸集和极点1.线段线段设设X（1）和）和X（2）是）是n维空间的两个点，则满足条件维空间的两个点，则满足条件的点的点X的集合，叫做以的集合，叫做以X（1）和）和X（2）为端点的线段。为端点的线段。证：二维证：二维比例关系：比例关系：令令 令令40武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE 代入上式代入上式 同理同理y轴：轴：即即 41武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE 2凸集。凸集。设设K是是n维空间的一个点集，任意两点维空间的一个点集，任意两点 的连线上的一切点的连线上的一切点 则称则称K为凸集。为凸集。性质：即凸集中任意两点连线上的任一点在凸集中。性质：即凸集中任意两点连线上的任一点在凸集中。3.极点。极点。在凸集中找不到任何另外两点在凸集中找不到任何另外两点X（1）、）、X（2），），使使 成立，称成立，称X为极点。为极点。三、解的几何意义三、解的几何意义1可行解。凸集中的任一点。可行解。凸集中的任一点。2基本可行解。凸集中的极点。基本可行解。凸集中的极点。42武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第四节第四节 线性规划解的概念线性规划解的概念 定理定理定理定理1 1.若线性规划问题存在可行域，则其可行域一定是凸集。若线性规划问题存在可行域，则其可行域一定是凸集。定理定理定理定理2 2.线性规划问题的基可行解对应可行域的顶点。线性规划问题的基可行解对应可行域的顶点。定定定定理理理理3 3.若若可可行行域域有有界界，线线性性规规划划的的目目标标函函数数一一定定可可以以在在可可行行域的顶点上达到最优。域的顶点上达到最优。四、线性规划的基本定理四、线性规划的基本定理 43武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第四节第四节 线性规划解的概念线性规划解的概念五、线性规划的解题思路五、线性规划的解题思路线性规划问题可以有无数个可行解，最优解只可能线性规划问题可以有无数个可行解，最优解只可能在顶点上达到，而有限个顶点对应的是基可行解，在顶点上达到，而有限个顶点对应的是基可行解，故只要在有限个基可行解中寻求最优解即可。故只要在有限个基可行解中寻求最优解即可。从一个顶点出发找到一个可行基，得到一组基可行从一个顶点出发找到一个可行基，得到一组基可行解，拿目标函数做尺度衡量一下看是否最优。解，拿目标函数做尺度衡量一下看是否最优。如若不是，则向邻近的顶点转移，换一个基再行求如若不是，则向邻近的顶点转移，换一个基再行求解、检验，如此迭代循环目标值逐步改善，直至求解、检验，如此迭代循环目标值逐步改善，直至求得最优解。得最优解。44武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE 作业：化标准型。作业：化标准型。1.2.45武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第二章第二章 线性规划单纯形法线性规划单纯形法 单纯形法单纯形法(Simplex Method)是美国人丹捷格是美国人丹捷格(G.Dantzig)1947年创建的。年创建的。这种方法简捷、规范，是举世公认的解决线性这种方法简捷、规范，是举世公认的解决线性规划问题行之有效的方法。规划问题行之有效的方法。单纯形法的表现形式：单纯形法的表现形式：代数法代数法表格法表格法矩阵法矩阵法46武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第二章第二章 线性规划单纯形法线性规划单纯形法47武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第一节第一节 单纯形法原理单纯形法原理例例例例1.1.生产计划问题生产计划问题生产计划问题生产计划问题 某某厂厂生生产产甲甲乙乙两两种种产产品品，各各自自的的零零部部件件分分别别在在A、B车车间间生产，最后都需在生产，最后都需在C车间装配，相关数据如表所示：车间装配，相关数据如表所示：问如何安排甲、乙两产品的产量，使利润为最大。问如何安排甲、乙两产品的产量，使利润为最大。产品车间工时单耗甲 乙生产能力ABC 1 0 0 2 3 48 1236单位产品获利 3 548武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第一节第一节 单纯形法原理单纯形法原理该问题的数学模型表示为该问题的数学模型表示为 maxZ=3x1+5 x2 x1 8 2x2 12 3x1+4 x2 36 x1 0,x2 049武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第一节第一节 单纯形法原理单纯形法原理一、代数解法一、代数解法 例例1 x1 +x3 =8 2x2 +x4 =12 3x1+4 x2 +x5=36 -Z+3x1+5 x2+0 x3+0 x4+0 x5=0 x1,x2,x3,x4,x5 0非奇异子阵，做为一个基基变量基变量x3,x4,x5非基变量非基变量x1,x250武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第一节第一节 单纯形法原理单纯形法原理将基变量用非基变量线性表示，即将基变量用非基变量线性表示，即x3=8-x1 x4=12-2x2 x5=36-3x1-4 x2 令非基变量令非基变量x1=0，x2=0，找到一个初始基可行解找到一个初始基可行解：x1=0，x2=0，x3=8，x4=12，x5=36即即X0=(0,0,8,12,36)T一个可行解就是一个生产方案，在上述方案中两种产品都不一个可行解就是一个生产方案，在上述方案中两种产品都不生产，生产，利润利润Z=0。1.求初始基可行解求初始基可行解 51武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第一节第一节 单纯形法原理单纯形法原理确定进基变量确定进基变量 x1 +x3 =8 2x2 +x4 =12 3x1+4 x2 +x5=36 -Z+3x1+5 x2+0 x3+0 x4+0 x5=0 从目标函数从目标函数-Z+3x1+5 x2+0 x3+0 x4+0 x5=0可知：可知：非非基基变变量量x1和和x2的的系系数数均均为为正正数数，生生产产哪哪种种产产品品都都会会增加利润。增加利润。因因为为x2的的系系数数大大于于x1的的系系数数，即即生生产产单单位位乙乙产产品品比比甲甲产品利润更高一些，故应优先多生产乙产品。产品利润更高一些，故应优先多生产乙产品。2.第一次迭代第一次迭代 52武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第一节第一节 单纯形法原理单纯形法原理确定离基变量确定离基变量基变量用非基变量线性表示基变量用非基变量线性表示x3 =8 x1 x4=12-2x2 x5=36-3x1-4 x2保持原非基变量保持原非基变量x1=0，x2变成基变量时应保证变成基变量时应保证 x3,x4,x5非负，即有非负，即有2.第一次迭代（续）第一次迭代（续）x3 =8 0 x4=12-2x2 0 x5=36-4 x2 0 x2 12/2x2 36/4 53武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第一节第一节 单纯形法原理单纯形法原理2.第一次迭代（续）第一次迭代（续）主元主元 x1+0 x2+x3 =8 2x2 +x4 =12 3x1+4 x2 +x5=36 -Z+3x1+5 x2+0 x3+0 x4+0 x5=0进基变量所在列为主列，离基变量所在行为主行进基变量所在列为主列，离基变量所在行为主行54武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第一节第一节 单纯形法原理单纯形法原理基变换基变换进行初等变换，变主元为进行初等变换，变主元为1，主列为单位列向量。，主列为单位列向量。2.第一次迭代（续）第一次迭代（续）x1 +x3 =8 x2 +1/2 x4 =6 3x1+-2 x4+x5=12 -Z+3x1+0 x2+0 x3 5/2x4+0 x5=-30 x1 +x3 =8 x2 +1/2 x4 =6 3x1+-2 x4+x5=12 -Z+3x1+5 x2+0 x3+0 x4 +0 x5=0 x1+0 x2+x3 =8 2x2 +x4 =12 3x1+4 x2 +x5=36 -Z+3x1+5 x2+0 x3+0 x4+0 x5=0 x1 +x3 =8 x2 +1/2 x4 =6 3x1+4 x2 +x5=36 -Z+3x1+5 x2+0 x3+0 x4 +0 x5=055武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第一节第一节 单纯形法原理单纯形法原理2.第一次迭代（续）第一次迭代（续）将基变量用非基变量线性表示，即将基变量用非基变量线性表示，即x3=8 x1 x2=6-1/2x4 x5=12-3x1+4 x4令非基变量令非基变量x1=0，x4=0，找到另一个基可行解找到另一个基可行解 x1=0，x2=6，x3=8，x4=0，x5=12即即X1=(0,6,8,0,12)T目标函数目标函数Z=3056武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第一节第一节 单纯形法原理单纯形法原理确定进基变量确定进基变量3.第二次迭代第二次迭代 第一次迭代结果第一次迭代结果 x1 +x3 =8 x2 +1/2 x4 =6 3x1+-2 x4+x5=12 -Z+3x1+0 x2+0 x3 5/2x4+0 x5=-30目标函数目标函数-Z+3x1+0 x2+0 x3 5/2x4+0 x5=-30，非基非基变量变量x1的系数的系数 1=3（检验数）为正数，检验数）为正数，确定确定x1为进基变量。为进基变量。57武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第一节第一节 单纯形法原理单纯形法原理确定离基变量确定离基变量3.第二次迭代第二次迭代（续）（续）x3=8-x1 0 x2=6 0 x5=12-3x10 x1 8/1x1 12/3 基变量用非基变量线性表示基变量用非基变量线性表示 x3=8 x1 x2=6-1/2x4 x5=12-3x1+4 x4保持原非基变量保持原非基变量x4=0，x1变成基变量时应保证变成基变量时应保证 x2,x3,x5非负，即非负，即 58武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第一节第一节 单纯形法原理单纯形法原理基变换基变换变主元为变主元为1，主列为单位列向量。，主列为单位列向量。3.第二次迭代（续）第二次迭代（续）x1 +x3 =8 x2 +1/2 x4 =6 x1+-2/3 x4+1/3x5=4-Z+3x1+0 x2+0 x3 5/2x4+0 x5=-30 x3+2/3 x4-1/3x5=4 x2 +1/2 x4 =6 x1+-2/3 x4+1/3x5=4-Z+3x1+0 x2+0 x3 5/2x4+0 x5=-30 x3+2/3 x4-1/3x5=4 x2 +1/2 x4 =6 x1+-2/3 x4+1/3x5=4-Z+0 x1+0 x2+0 x3-1/2x4 -x5=-42 1 x1 +x3 =8 x2 +1/2 x4 =6 3x1+-2 x4+x5=12-Z+3x1+0 x2+0 x3 5/2x4+0 x5=-3059武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第一节第一节 单纯形法原理单纯形法原理3.第二次迭代（续）第二次迭代（续）将基变量用非基变量线性表示，即将基变量用非基变量线性表示，即x3 =4 2/3x4+1/3x5x2=6-1/4x4 x1=4+2/3x4-1/3 x5 令非基变量令非基变量x4=0，x5=0，又找到一个基可行解又找到一个基可行解 目标函数目标函数 -Z+0 x1+0 x2+0 x3-1/2x4 -x5=-42 x1=4，x2=6，x3=4，x4=0，x5=0即即 X2=(4,6,4,0,0)T Z=42 检验数检验数j非正，得最优解非正，得最优解X*=(4,6,4,0,0)T，Z*=4260武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第一节第一节 单纯形法原理单纯形法原理二、单纯形法的几何意义二、单纯形法的几何意义x1=82x2=123x1+4 x2=36X0=(0,0,8,12,36)TX1=(0,6,8,0,12)TX1=(4,6,4,0,0)T61武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第二节第二节 表格单纯形法表格单纯形法 表格单纯形法，是对上节讨论的方法步骤进行具体表格单纯形法，是对上节讨论的方法步骤进行具体化、规范化、表格化的结果。化、规范化、表格化的结果。一、单纯形法表一、单纯形法表CjC1C2CjCn比比值值CBXBbx1x2xjxnCB1xB1b1a11a12a1ja1n 1CB2xB2b2a21a22a2ja2n 2CBnxBnbmam1am2amjamn m检验数检验数 j-Z 1 2 j n62武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第二节第二节 表格单纯形法表格单纯形法将线性规划问题化成标准型。将线性规划问题化成标准型。找出或构造一个找出或构造一个m阶单位矩阵作为初始可行基，建立初始单纯形表。阶单位矩阵作为初始可行基，建立初始单纯形表。计计算算各各非非基基变变量量xj的的检检验验数数 j=Cj-CBPj，若若所所有有 j0，则则问问题题已已得得到最优解，停止计算，否则转入下步。到最优解，停止计算，否则转入下步。根根据据max j j0=k原原则则，确确定定xk为为换换入入变变量量(进进基基变变量量)，再再按按 规规则则计计算算：=minbi/aik|aik0=bl/aik 确确定定xBl为为换换出出变变量量。建立新的单纯形表，此时基变量中建立新的单纯形表，此时基变量中xk取代了取代了xBl的的位置。位置。以以aik为为主主元元素素进进行行迭迭代代，把把xk所所对对应应的的列列向向量量变变为为单单位位列列向向量量，即即aik变为变为1，同列中其它元素为，同列中其它元素为0，转第，转第 步。步。二、单纯形法的计算步骤二、单纯形法的计算步骤 63武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第二节第二节 表格单纯形法表格单纯形法 maxZ=3x1+5 x2+0 x3+0 x4+0 x5=0 x1 +x3 =8 2x2 +x4 =12 3x1+4 x2 +x5=36 三、单纯形法计算举例三、单纯形法计算举例(上例上例)Cj比比值值CBXBb检验数检验数 jx1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=964武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第二节第二节 表格单纯形法表格单纯形法检验数检验数 j81010060101/2012300-21x3x2x5050-30300-5/208-4Cj比比值值CBXBb检验数检验数 jx1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=965武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第二节第二节 表格单纯形法表格单纯形法Cj比比值值CBXBb检验数检验数 jx1x2x3x4x53500081010060101/2012300-21x3x2x5050-30300-5/208-4检验数检验数 j40012/3-1/360101/204100-2/31/3x3x2x1053-42000-1/2-1最优解最优解:X*=(4,6,4,0,0)T，Z*=4266武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE 例例2 67武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE -3-1-1-1X1X2X3X4bX3-221042X4310166Cj-ZJ-2200X2-111/202X440-1/214Cj-Zj00-1068武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE 例例3 （j=1j=1、2 2、3 3）69武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE11300X1X2X3X4X5bX43211033X52120121Cj-zj113000X423/201-1/22X311/2101/21Cj-Zj-2-1/200-3/2370武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE 例例4 71武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE72武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE例例5 x xj j0 0 （j=1j=1、2 2、3 3）73武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE74武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE75武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE76武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第三节第三节 人工变量问题人工变量问题 采用人造基的办法：采用人造基的办法：人工构造单位矩阵人工构造单位矩阵人工构造单位矩阵人工构造单位矩阵处理方法有两种：处理方法有两种：大大M 法法两阶段法两阶段法77武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第三节第三节 人工变量问题人工变量问题大大M法法 例例6 maxZ=3x1-x2-2 x3 3x1+2 x2-3 x3=6 x1 -2 x2+x3=4 x1,x2,x3 078武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第三节第三节 人工变量问题人工变量问题按大按大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 0Cj比比值值CBXBb检验数检验数 jx1x2x3x4x53-1-2-M-M632-31041-2101-10M3+4M-1-2-2M00 x4x5-M-M2479武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第三节第三节 人工变量问题人工变量问题Cj比比值值CBXBb检验数检验数 jx1x2x3x4x53-1-2-M-M632-31041-21013+4M-1-2-2M00 x4x5-M-M24检验数检验数 j212/3-11/3020-8/32-1/310-3-8M/31+2M-1-4M/30 x1x53-M-1检验数检验数 j31-2/301/61/210-4/31-1/61/20-5/30-M-5/6-M-1/2x1x33-280武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE 例例7 xj0，（j=1、2、3、）、）81武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE82武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE83武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE解解 xj0，（j=16）84武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE二、二阶段法二、二阶段法 例例9 xj0 （j=1、2、3）解：第一阶段：引入人工变量，并构造一个新的目解：第一阶段：引入人工变量，并构造一个新的目标函数为人工变量之和，并取最小值。标函数为人工变量之和，并取最小值。xj0 （j=14）85武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE二、二阶段法二、二阶段法求解中可出现以下情况：求解中可出现以下情况：在最优解中，人工变量全是非基变量，即在最优解中，人工变量全是非基变量，即minz=0。这表示得到了原问题一个基可行解（去掉人工变量这表示得到了原问题一个基可行解（去掉人工变量列）。列）。最优解中含有人工变量，即最优解中含有人工变量，即minz0，这说明原线，这说明原线性规划无可行解，这说明了性规划无可行解，这说明了“只有在采用并不存在只有在采用并不存在的人造活动时约束条件才得到满足。的人造活动时约束条件才得到满足。”86武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE87武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE88武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE89武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE90武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE91武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第四节第四节 单纯形法补遗单纯形法补遗一、无可行解：一、无可行解：最终表中存在人工变量是基变量。最终表中存在人工变量是基变量。例例 1192武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第四节第四节 单纯形法补遗单纯形法补遗93武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE二、二、无界解无界解例例12maxZ=3x1+2 x2 -2x1+x2 2 x1-3 x2 3 x1,x2 0标准化标准化 maxZ=3x1+2 x2-2x1+x2+x3 =2 x1-3 x2 +x4=3 x1,x2,x3,x4 0Cj比比值值CBXBb检验数检验数 jx1x2x3x432002-211031-301x3x40003200-3检验数检验数 j80-512x3x103-31-301-90110-394武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第四节第四节 单纯形法补遗单纯形法补遗三、多重最优解：三、多重最优解：最优单纯形表中，最优单纯形表中，存在非基变量的检验数存在非基变量的检验数 j=0。让这个让这个非基变量进基，非基变量进基，继续迭代，得另一个最优解。继续迭代，得另一个最优解。例例 1395武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE96武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE97武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE98武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第四节第四节 单纯形法补遗单纯形法补遗四、退化解。四、退化解。有基变量为有基变量为0，称这种情况为，称这种情况为退化解退化解退化解退化解。（原因，模型中存在多余的约束，使多个基可行解（原因，模型中存在多余的约束，使多个基可行解对应同一顶点）对应同一顶点）1退化是暂时的，最终得非退化解。退化是暂时的，最终得非退化解。2最后得退化最优解。最后得退化最优解。3产生循环。产生循环。99武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE如何避免循环：如何避免循环：1976年布兰德提出两法则：年布兰德提出两法则：法则法则1：若有几个正检验数，选其中下标最小的非基：若有几个正检验数，选其中下标最小的非基变量为换入变量。变量为换入变量。法则法则2：若有几个：若有几个值值同时达到最小，就选其中下标最同时达到最小，就选其中下标最小的基变量为退出变量。小的基变量为退出变量。100武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第四节第四节 单纯形法补遗单纯形法补遗101武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE102武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE103武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE104武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE105武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE106武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE107武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第五节第五节 检验数的讨论检验数的讨论 已知标准型已知标准型 设设(0)与与(1)是相邻两个顶点，由是相邻两个顶点，由(0)向向(1)转换转换 108武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第五节检验数的讨论第五节检验数的讨论将将x（0）代入约束条件得代入约束条件得得可行解得可行解X（1）109武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第五节第五节 检验数的讨论检验数的讨论则则x（1）就不可能为基本可行解，将就不可能为基本可行解，将x（1）代入目标函代入目标函数数 110武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第五节第五节 检验数的讨论检验数的讨论讨论：讨论：1若：若：2若：若：这时若把这时若把可行解可行解 x（1）不是基可行解，无界解。不是基可行解，无界解。111武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第五节第五节 检验数的讨论检验数的讨论3可行解可行解(1)的各分量就可确定出一个换出变量的各分量就可确定出一个换出变量 选选这时，这时，新解比原解大新解比原解大。112武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第五节第五节 检验数的讨论检验数的讨论4若若有无穷最优解。有无穷最优解。113武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE2.3114武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第三章第三章 对偶理论对偶理论115武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE从生产角度考虑这个问题从生产角度考虑这个问题116武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE现从另一角度考虑这个问题；假设不生产现从另一角度考虑这个问题；假设不生产、，而将所有资源出租或外售，就须给各种资源定价。而将所有资源出租或外售，就须给各种资源定价。由由y1,y2,y3表示外销单位资源利润。表示外销单位资源利润。生产一件生产一件所耗资源的外销应不低于所耗资源的外销应不低于2元。元。同理：同理：总利润：总利润：从企业出发：从企业出发：从消费者出发：从消费者出发：企业只能在满足约束条件下，使其总利润尽可能企业只能在满足约束条件下，使其总利润尽可能小，这样，才能实现外销的愿望。小，这样，才能实现外销的愿望。称这个问题为原问题的对偶问题。称这个问题为原问题的对偶问题。每一个线性规划问题，都伴随另一个线性规划问每一个线性规划问题，都伴随另一个线性规划问题，二者互为对偶。题，二者互为对偶。117武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE118武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE119武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE120武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE121武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE122武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE123武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第三章第三章 对偶理论对偶理论 3-2 对偶问题的基本性质定理1，若X是原问题的可行解，Y是对偶问题的可行解，则存在证：AXb YAC YAXYb YAXCX YbCX推理1：若Y为对偶问题的任一可行解，则Yb为原问题目标函数值的上界；若X为原问题的任一可行解。则CX为其对偶问题目标函数值的下界。推理2：若原问题有可行解，但其CX无上界，则对偶问题无可行解；若对偶问题有可行解，但目标函数值无下界，则原问题，无可行解。124武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE125武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE定理2：若原问题和对偶问题分别有可行解X*和Y*且其目标函数值相等。即CX*=bY*。则X*和Y*分别为原问题和对偶问题的最优解。定理3：若B是原问题的最优基，则最优单纯形乘子Y*=CBB-1 是其对偶问题的最优解。126武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE127武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE第三章第三章 对偶理论对偶理论12 128武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE129武汉纺织大学管理学院武汉纺织大学管理学院SHUFESHUFE约束条件类型约束条件类型 对偶变量最优值对偶变量最优值 (最优表中最优表中)等于这个约束条件等于这个约束条件松驰变量对应的对应的Zj值 等于这个约束条件等于这个约束条件剩余变量对应的对应的Zj值的相反数-Z