一章线规划与单纯形法

第一章线性规划与单纯形法第一章线性规划与单纯形法第一节线性规划的基本概念第一节线性规划的基本概念第二节线性规划的标准形式和解的性质第二节线性规划的标准形式和解的性质第三节单纯形法第三节单纯形法第四节人工变量法第四节人工变量法第五节线性规划应用举例第五节线性规划应用举例本章学习目的和要求本章学习目的和要求通过本章的学习，要求学生掌握线性通过本章的学习，要求学生掌握线性规划的图解法，深刻理解单纯形法的解题规划的图解法，深刻理解单纯形法的解题思路，熟练掌握其运算步骤，并能在实际思路，熟练掌握其运算步骤，并能在实际问题中加以运用。问题中加以运用。主要研究目的主要研究目的1 1已有一定数量的人力、物力、财力资源，研已有一定数量的人力、物力、财力资源，研究如何充分合理地使用才能使完成的任务量最究如何充分合理地使用才能使完成的任务量最大。（如：利润、产值等最大。大。（如：利润、产值等最大。maximum）2 2当一项任务量确定以后，研究如何统筹安排，当一项任务量确定以后，研究如何统筹安排，才能使完成任务耗费的资源量为最小。（如：才能使完成任务耗费的资源量为最小。（如：成本最小。成本最小。minimum）第一节线性规划的基本概念第一节线性规划的基本概念一、线性规划的数学模型一、线性规划的数学模型【例【例1-11-1】某厂生产某厂生产P、Q两种产品，两种产品，主要消耗主要消耗A、B、C三种原料，已知单位产品三种原料，已知单位产品的原料消耗数量等资料如表的原料消耗数量等资料如表1-11-1所示。所示。产品产品单位消耗单位消耗原料原料PQ原料总量原料总量/吨吨ABC15022482012产品单价产品单价2万元万元5万元万元表表1 11 1要求确定要求确定P P、Q Q的产量，使产值最大。的产量，使产值最大。解：设解：设P、Q的产量分别为的产量分别为x1，x2，则问题的模，则问题的模型为型为121212212m a x25 28522 0 41 2,0zxxxxxxxxx产品产品单位消耗单位消耗原料原料PQ原料总量原料总量/吨吨ABC15022482012产品单价产品单价2万元万元5万元万元【例【例1-2】某公司打算利用甲、乙、丙某公司打算利用甲、乙、丙3种原料配置一种原料配置一种新型保健饮料，已知每千克原料中两种主要保健成种新型保健饮料，已知每千克原料中两种主要保健成分分A，B的含量及原料单价如表的含量及原料单价如表1-2所示。所示。甲甲乙乙丙丙AB2010400020原料单价（元原料单价（元/千克）千克）223含量含量原料原料成分成分产品质量标准规定每千克饮料中，营养成分产品质量标准规定每千克饮料中，营养成分A，B的含量不低于的含量不低于10个与个与8个单位。如何制定饮料配方，个单位。如何制定饮料配方，既满足质量标准又使成本最低？既满足质量标准又使成本最低？解：设每千克饮料中原料甲，乙，丙的投入量解：设每千克饮料中原料甲，乙，丙的投入量分为分为x1，x2，x3千克，则问题的模型为：千克，则问题的模型为：1221213123min2232040 10 10 208,0zxxxxxxxx x x甲甲乙乙丙丙AB2010400020原料单价（元原料单价（元/千克）千克）223含量含量原料原料成分成分【例【例1-3】A1，A2是两个粮库，每月分别可调出粮是两个粮库，每月分别可调出粮食食30吨与吨与40吨，三个粮店吨，三个粮店B1，B2，B3每月的需求量每月的需求量分别为分别为20吨，吨，25吨与吨与18吨。粮库与粮店之间每吨粮吨。粮库与粮店之间每吨粮食的运费如下表食的运费如下表1-3所示（单位：元所示（单位：元/吨）。吨）。B1B2B3A1A2243653粮店粮店运费运费粮库粮库要求安排粮食调运方案，在满足需求的前提下，要求安排粮食调运方案，在满足需求的前提下，使总运费最低。使总运费最低。解：设从粮库解：设从粮库Ai到粮店到粮店Bj的调运量为的调运量为xij，i=1，2，j=1，2，3，则问题的模型为：，则问题的模型为：111213212223111213212223112112221323min2354633040 20 25 180 1,2 1,2,3ijzxxxxxxxxxxxxxxxxxxxij上述三个问题属于同一类型的决策优化问题，上述三个问题属于同一类型的决策优化问题，它们具有下列共同特点：它们具有下列共同特点：（1 1）每个行动方案可用一组变量）每个行动方案可用一组变量（x1，xn）的的值表示，这些变量一般取非负值值表示，这些变量一般取非负值；（2 2）变量的变化要受某些限制，这些限制条件用一）变量的变化要受某些限制，这些限制条件用一些线性等式或不等式表示；些线性等式或不等式表示；（3 3）有一个需要优化的目标，它也是变量的线性函）有一个需要优化的目标，它也是变量的线性函数。数。具备以上三个特点的数学模型称为线性规划具备以上三个特点的数学模型称为线性规划（Linear Programming，简记为，简记为LP）。）。实际问题中线性的含义实际问题中线性的含义一是严格的比例性，如生产某产品一是严格的比例性，如生产某产品对资源的消耗量和可获取的利润，同其对资源的消耗量和可获取的利润，同其生产数量严格成比例。生产数量严格成比例。二是可叠加性，如生产多种产品时二是可叠加性，如生产多种产品时对某项资源的消耗量应等于各产品对该对某项资源的消耗量应等于各产品对该项资源的消耗量之和。项资源的消耗量之和。线性规划的一般形式为：线性规划的一般形式为：1 12211 11221121 1222221 12212max(min)(,)(,)(,),0nnnnnnmmmnnmnzc xc xc xa xa xa xba xa xa xba xaxaxbx xx 变量变量x1，x2，xn称为决策变量，目标函数中变量系数称为决策变量，目标函数中变量系数cj，称为价值系数，称为价值系数，bi称为右端常数，约束条件（称为右端常数，约束条件（1-3）称为非负）称为非负约束，（约束，（1-2）称为技术约束，系数）称为技术约束，系数aij称为技术系数。满足全部约称为技术系数。满足全部约束条件的变量值（束条件的变量值（x1，xn）称为可行解，可行解的集合称为可）称为可行解，可行解的集合称为可行域，记为行域，记为R；使目标函数取得最大（最小）值的可行解；使目标函数取得最大（最小）值的可行解（x1，xn）称为最优解。）称为最优解。（1-31-3）（1-21-2）（1-11-1）采用求和符号采用求和符号，线性规划的一般形式，线性规划的一般形式可以可以简写为：简写为：11max(min)(,)1,2,0 1,2,njjjnijjijjzc xa xbimxjn 用向量形式可表示为：用向量形式可表示为：11max(min)(,)b ,0njjjnzCXP xxx 用矩阵和向量形式用矩阵和向量形式表示为：表示为：max(min)(,)b 0zCXAXX 式中：式中：X=（x1，x2，xn）TC=（c1，c2，cn）b=（b1，b2，bm）TA=（aij）mn Pj=（a1j，a2j，amj）T 二、图解法二、图解法 当决策变量个数当决策变量个数n=2时，时，LP问题可以通过在问题可以通过在平面上作图的方法求解，称为图解法。平面上作图的方法求解，称为图解法。图解法求解的目的：图解法求解的目的：1.1.判别线性规划问题的求解结局。判别线性规划问题的求解结局。2.2.在存在最优解的条件下，把问题的最优解找出来。在存在最优解的条件下，把问题的最优解找出来。【例【例1-41-4】求下列问题的最优解。求下列问题的最优解。121212212max25 285220 412,0zxxxxxxxxx（1 1）确定问题的可行域）确定问题的可行域R R。x2x1Q4Q3Q2Q1l1l2l3123456图图1-11-11 123405可行域可行域R是凸多角形是凸多角形OQ1Q2Q3Q4121212212max25 285220 412,0zxxxxxxxxx（2 2）分析目标函数）分析目标函数Z的等值线平行移动与的等值线平行移动与Z值的关系，确定最优解的位置。值的关系，确定最优解的位置。当当z取定值时，方程取定值时，方程z=2x1+5x2或或x2=2/5x1+z/5表示一条斜率为表示一条斜率为2/5的直线的直线 l，称为称为z的等值线，它在的等值线，它在x2轴上的截距为轴上的截距为z/5。当。当l向右向右上方平行移动且保持与上方平行移动且保持与R有共同部分时，有共同部分时，z值不值不断上升，由于断上升，由于l的斜率为的斜率为2/5，因此当，因此当l向右上向右上方平移的过程中，与方平移的过程中，与R最后的公共点是最后的公共点是Q3，z在在Q3达到最大值。达到最大值。121212212max25 285220 412,0zxxxxxxxxx（3 3）计算最优解。）计算最优解。点点Q3是直线是直线l1与与l3的交点，它的坐标由方程组的交点，它的坐标由方程组124 82221xxx 决定，从中解得决定，从中解得x1=2，x2=3。这就是问题的最优。这就是问题的最优解，相应的目标函数值解，相应的目标函数值z=2253=19。最优产。最优产量计划是量计划是P，Q分别生产分别生产2个与个与3个单位，最大产值个单位，最大产值为为19万元。这时原料万元。这时原料A与与C用完，用完，B剩余剩余4吨。吨。121212212max25 285220 412,0zxxxxxxxxx线性规划问题求解的几种可能结局：线性规划问题求解的几种可能结局：1.唯一最优解：如上例。唯一最优解：如上例。2.无穷多最优解：如无穷多最优解：如Z换成换成maxZ=2X1+4X2,，此时最，此时最优解在线段优解在线段Q2Q3 上达到，有无穷多最优解。上达到，有无穷多最优解。已求得已求得Q3的坐标为（的坐标为（2，3）；）；Q2坐标由方程组坐标由方程组2025822121xxxx决定，从中解得决定，从中解得x1=3，x2=5/2。设，设，线段，线段Q2Q3上的点可用上的点可用X1+（1）X2（01）表示。因此，）表示。因此，X1+（1）X2（01）是问题的全部最优解。）是问题的全部最优解。321X2/53 2X3.3.无界解无界解如约束条件只保留第如约束条件只保留第3个，即个，即4X212，这，这时可行域无界，时可行域无界，Z值可无限上升，无最优解，值可无限上升，无最优解，简称无界解，即有可行解，但目标函数值无解。简称无界解，即有可行解，但目标函数值无解。产生原因：是由于在建立实际问题的数学产生原因：是由于在建立实际问题的数学模型中遗漏了某些必要的资源约束条件。模型中遗漏了某些必要的资源约束条件。121212212max25 285220 412,0zxxxxxxxxx4.4.无解或无可行解无解或无可行解Ox2DA24x1BCl1l2l可行域是空集，问题无可行解，当然更无最优解。可行域是空集，问题无可行解，当然更无最优解。注意：考试中如出现注意：考试中如出现3 3、4 4两种情况，一定自己两种情况，一定自己搞错了，必须重新解。搞错了，必须重新解。图解法得到的启示图解法得到的启示1.1.求解线性规划问题时，解的情况有：唯一最优求解线性规划问题时，解的情况有：唯一最优解、无穷多最优解、无界解和无可行解。解、无穷多最优解、无界解和无可行解。2.2.若线性规划问题的可行域存在，则可行域是一若线性规划问题的可行域存在，则可行域是一凸集。凸集。3.3.若线性规划问题的最优解存在，则最优解一定若线性规划问题的最优解存在，则最优解一定在某个顶点可达到。在某个顶点可达到。4.4.解题思路是：先找出凸集的任一顶点，计算解题思路是：先找出凸集的任一顶点，计算Z Z值，比较相邻顶点值，比较相邻顶点Z Z值，如大，转到相邻顶点，值，如大，转到相邻顶点，一直到找出使一直到找出使Z Z值最大的顶点为止。值最大的顶点为止。第二节第二节 线性规划的标准形式和线性规划的标准形式和解的性质解的性质 一、一、LP的标准形式的标准形式11max 1,2,0 1,2,njjjnijjijjzc xa xbimxjn称为线性规划问题的标准形式（其中右端常数称为线性规划问题的标准形式（其中右端常数b1，b2，bm0）。）。线性规划标准形式的特点：线性规划标准形式的特点：1.1.技术约束条件全部是等式约束技术约束条件全部是等式约束2.2.目标函数限定求最大值目标函数限定求最大值变换一般变换一般LPLP为标准形式的方法：为标准形式的方法：（1 1）如果原问题目标函数求极小值：）如果原问题目标函数求极小值：1minnjjjzc x令令z1=z，转化为求。，转化为求。（2）若某个右端常数）若某个右端常数bi0时，方时，方值得让值得让xj入基入基。miijijjacc12.2.单纯形表单纯形表 表1-5 jcnmmcccc11BcBXbmcc 1mxx 1mbb 1nmmxxxx 11im 1mnmmnmaaaa1,11,110010 0 ijijjacc j总结 从表中可以直接读出基可行解从表中可以直接读出基可行解X：xi=bi（i=1，m），），其它其它xj=0；相应目标函数值相应目标函数值，是是CB列与列与b列元素列元素乘积之和；乘积之和；每个变量每个变量xj（包括基变量在内）的检验数包括基变量在内）的检验数j，等于等于cj减去减去CB列元素与表中列元素与表中xj的系数列向量元素乘积之和的系数列向量元素乘积之和。单纯形法的全部分析和计算过程，可以比较方便地单纯形法的全部分析和计算过程，可以比较方便地在单纯形表中完成。在单纯形表中完成。1miiizc b3.3.单纯形法的基本法则单纯形法的基本法则 法则法则1 1 最优性判定法则最优性判定法则若对基可行解若对基可行解X1，所有检验数，所有检验数j0，则则X1为最优解。为最优解。法则法则2 2 换入变量确定法则换入变量确定法则（最大价值系数法则）（最大价值系数法则）设，则设，则xk为换入变量。为换入变量。0maxjjjk法则法则3 3 换出变量确定法则换出变量确定法则 （最小比值法则）（最小比值法则）设设xk为换入变量，并设为换入变量，并设则最小比值所在行的原基变量则最小比值所在行的原基变量xl为为换换出变量。出变量。lklikikiiabaab0min法则法则4 4 换基迭代运算法则换基迭代运算法则 对方程组的增广矩阵实施行的初等对方程组的增广矩阵实施行的初等变换，使主元变换，使主元alk化为化为1，主元列其它元素，主元列其它元素化为化为0。具体地说，第。具体地说，第l行乘以行乘以1/alk，并将，并将第第l行的行的aik/alk倍加到第倍加到第i行上去，行上去，i=1，2，m，il。例一例一求下列求下列LP问题的最优解问题的最优解 121231242512345max 25 2 852 20 4 12,0zxxxxxxxxxxx x x x x例二例二求下列求下列LP问题的最优解问题的最优解 23512352342356123456max 323 2 7 24 12 43 810,0zxxxxxxxxxxxxxxx x x x x x 三、三、关于单纯形法的补充说明关于单纯形法的补充说明 1.1.无穷多最优解与唯一最优解的判别法则无穷多最优解与唯一最优解的判别法则若对某可行解若对某可行解X1，（1）所有检验数）所有检验数j0，且有一个非基变量，且有一个非基变量xk的检验数等于的检验数等于0，则问题有无穷多最优解；，则问题有无穷多最优解；（2）所有非基变量的检验数）所有非基变量的检验数j0，但，但aik0，i=1，2，m即即xk的系数列向量无正分量，则问题无的系数列向量无正分量，则问题无最优解。最优解。如上例中，如上例中，111a 3.3.求求min min z z 的情况的情况 这时可以有两种处理方式：这时可以有两种处理方式：一种方式是令一种方式是令z1=z，转化为求，转化为求max z1，另一种是直接计算。另一种是直接计算。v最优性检验条件改为：所有最优性检验条件改为：所有j0；v换入变量确定法则改为：如果换入变量确定法则改为：如果则则xk为换入变量。为换入变量。v单纯形法的其它要点完全无须改变。单纯形法的其它要点完全无须改变。min0jjkj 例：解：解：方程组化为：方程组化为：12312413512345min2232040 10 10 20 8,0zxxxxxxxxxxxxxx52201 2141 401 21531421xxxxxx第四节第四节 初始可行基的求法初始可行基的求法人工变量法人工变量法 一、一、大大M M法法【例【例1-151-15】求下列求下列LPLP问题的最优解问题的最优解 0,1 2324112 3 max32131321321321xxxxxxxxxxxxxxz解：解：引入松弛变量引入松弛变量x4，x5，把问题化为标把问题化为标准形式的准形式的LP（简称（简称P1）123123412351312345max3 2 1142 3 2 1,0zxxxxxxxxxxxxxx x x x x给后两个方程分别添加人工变量给后两个方程分别添加人工变量x6，x7，使约束方使约束方程组化为程组化为 1 23 2411 2 731653214321xxxxxxxxxxxx11236712341235613717max3 2 1142 3 2 1,0zxxxMxMxxxxxxxxxxxxxxx123123412351312345max3 2 1142 3 2 1,0zxxxxxxxxxxxxxx x x x x（P1）（P2）设设X=(x1，x2，x3，x4，x5)T，XA=(x6，x7)T。（1）若若（P1）有最优解有最优解X*，则则X*，XA*=0是是（P2）的最优解的最优解；（2）若若（P2）有最优解有最优解X*与与XA*=0，则则X*是是（P1）的最优解的最优解；如果如果（P2）最优解中最优解中XA*0，则则（P1）无可行解无可行解。