线性规划与单纯形法.doc

1.1线性规划问题及其数学模型一、问题的提出在生产经营管理中，需要经常进行计划或者规划，虽然各行业的计划或规划千差万别，但其共同点可归纳为：在各项资源条件的限制下，如何确定方案，使预期的目标达到最优。例1.1某工厂在计划期内要安排生产、两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗如下表所示：资源限制设备128台时原材料A4016原材料B0412利润23该工厂生产一件产品、的利润分别为2元、3元，问应如何安排生产才使该工厂的获利最大？二、数学模型的建立L.P问题数学模型的三要素：1.决策变量：一般是根据所问问题假设决策变量，一组决策变量（）表示某一方案，这一组决策变量的值就代表一个具体方案。2.目标函数：通过决策变量，将要实现的目标用函数式表示出来，常见的目标函数有两种表达式。（1） 目标是求最大化：（2） 目标是求最小化：3.约束条件：主要是对变量或目标的约束，通常用未知量的线性等式或不等式来表示。例1.3：某公司经销一种产品，它下设三个生产点，每日产量分别为， ，该公司把这些产品分别运往四个销售点，各销售点每日销量分别为，已知每吨产品从各生产点到各销售点的运价如下表所示，问该公司应如何调运产品，在满足各销售点需要前提下，使总运费最少？销量运价411310192874105解：三、L.P数学模型的一般形式st.上述模型的简写形式为：st.用向量形式表达时，上述模型可写为：st.式中：；价值系数用矩阵形式来表示可写为：技术系数工艺系数资源系数st.（假定线性规划问题中含n个变量，分别用表示，在目标函数中的系数为，称为价值系数；的取值受m种资源的限制，用表示i第种资源的拥有量，用表示变量取值为1单位时所消耗或含有的第i种资源的数量，通常称为技术系数或工艺系数）1.2 图解法图解法简单直观，能帮助我们了解L.P的基本原理。一、图解法基本步骤1. 在平面上建立直角坐标系；2. 图示全部约束条件，找出可行域；3. 图示目标函数和寻找最优解。例1.4：通过例1.1来说明图解法的具体运用 s.t 二、L.P求解的几种解的情况1. 有唯一最优解。（如上例所示）2. 有无穷多最优解（多重解）如上例中，若将目标函数改为，则表示目标函数中以参数z的这族平行直线与约束条件的边界线平行。当z值由小变大时，将与线段Q2Q3重合，则点Q2与Q3之间的可行域边界上各点均为最优点，它们对应同一最优值。3.无可行解若上例中再增加一个约束条件，时，该问题的可行域为空集，即该LP模型无可行解也不存在最优解。如出现这种情况表明数学模型中存在矛盾的约束条件。4.无界解如果全部约束条件构成的可行域是无界的，则有可能出现最优解无界，产生无界解的原因是由于在建立实际问题的数学模型时，遗漏了某些必要的资源约束条件。如下述线性规划问题：三、由图解法得到的启示从LP图解法可以得出以下几点启示：1.LP的解的情况有四种：唯一最优解、无穷多最优解、无界解、无可行解。2.LP的可行域为凸集，特殊情况下为无界域或空集；3.LP若有最优解，一定可以在其可行域的顶点上得到；4.解题思路是：先找出凸集的任一顶点，计算在顶点处的目标函数值。比较周围相邻顶点的目标函数值是否比这个值大，如果否，则该顶点是最优解的点若最优解的点之一，否则，转到比这个点的目标函数值更大的另一顶点，重复上述过程，一起到找到使目标函数值最大的顶点为止。图解法虽然直观、简便，但当变量数多于三个以上时，它就无能为力，只能用另外一种代数法单纯形法来求解。作业：1.用图解法求解下列线性规划问题，并指出问题具有惟一最优解、无穷多最优解、无界解还是无可行解。（1） 4s.t (2) s.t (3) s.t (4) s.t 2.美佳公司计划制造I、II两种家电产品。已知各制造一件时分别占用的设备A,B的台时、调试时间及调试设备和调试工序每天可用于这两种家电的能力、各售出一件时的获利情况如表11所示。问该公司应制造A、B两种家电各多少件，使获取的利润为最大。表1-1项目III每天可用能力设备A(h)0515设备B(h)6224调试工序(h)115利润（元）213.(仓库租用问题)捷运公司拟在下一年度的1-4月的4个月内需租用仓库堆放物资.已知各月份所需仓库面积数列于表1.仓库租借费用随合同期而定,期限越长,折扣越大,具体数字见表2.租借仓库的合同每月初都可办理,每份合同具体规定租用面积数和期限.因此该厂可根据需要,在任何一个月初办理租借合同.每次办理时可签一份,也可签若干份租用面积和租借期限不同的合同,试确定该公司签订租借合同的最优决策,目的是使所付租借费用最小.月份1234所需仓库面积(100m2)15102012合同租借期限1个月2个月3个月4个月所需仓库面积(元/100m2)28004500600073001.3线性规划问题的标准形式一、标准形式LP的数学模型有各种不同的形式，为了便于讨论和制定统一的算法，有必要用统一的标准形式来表示。规定LP的标准形式如下：二、LP一般式转化为标准形式1.决策变量在标准形式中要求所有决策变量，但一般式中决策变量不一定才是大于等于0。（1） 若（2） 若（3） 若2.目标函数（1） 若目标函数是求极大值，则不变；（2） 若目标函数是求极小值，即：因为求，令，即可化为3.资源系数标准形式中要求，若时，只需将等式或不等式两端同乘（-1），则等式右端必大于0。4.约束条件不等式（1） 若约束条件为“”，则不变；（2） 若约束条件为“”，则在不等式左侧增加一个非负松驰变量，使其转化为“”；（3） 若约束条件为“”，则在不等式左侧减去一个非负剩余变量（也称松驰变量），使其转化为“”。松驰变量或剩余变量在实际问题中分别表示未被充分利用的资源和超出的资源数，均未转化为价值和利润，所以，引进模型后它们在目标函数中的系数均为0。例1.5，通过例1.1来说明一般形式向标准形式的转化：s.t例1.6将下列LP转化为形式：（让学生演算） st.作业习题1、将下列线性规划问题化为标准型(1) Max z = 3x1+ 5x2- 4x3+ 2x4 s.t. 2x1+ 6x2- x3+ 3x4 18 x1- 3x2+ 2x3- 2x4 13 -x1+ 4x2- 3x3- 5x4 = 9 x1, x2, x4 0(2) Min f = 3x1+ x2+ 4x3+ 2x4 1 s.t. 2x1+ 3x2- x3- 2x4 -51 3x1- 2x2+ 2x3- x4 -7 2x1+ 4x2- 3x3+ 2x4 = 15 x1 , x2 0, x4 01.4单纯形法原理一、线性规划问题的解的概念LP1.可行解：满足上述约束条件的解，称为LP的可行解。2.最优解：使目标函数达到最大值的可行解叫最优解。3.基：设A是约束方程组的阶系数矩阵（设），则矩阵A的秩为，若B是矩阵A中的一个阶的满秩子矩阵，称B为LP的一个基。也就是说，矩阵B是由m个线性独立的列向量组成的，不失一般性地设：B中的每一个列向量称为基向量，与基向量对应的变量称为基变量，LP中除基变量以外的变量称为非基变量。4.基解：在约束方程组中，令所有非基变量，又因有，根据克莱姆法则，则m个约束方程可以得出m个基变量的唯一解，将这个解加上非基变量取0的值有：，称X为LP的基解。显然在基解中变量取非零值的个数不大于方程数m，故基解的总数不超过个。5.基可行解：满足变量非负约束条件的基解称为基可行解。6.可行基：对应于基可行解的基称为可行基。7.凸集及其顶点凸集：如果集合C中任意两点，其连线上所有的点也都是集合C中的点，则称C为凸集。顶点：凸集C中满足下述条件的点称为顶点，如果C中不存在任何两个不同的点，使X成为这两个点连线上的一个点。或对任何，不存在则称X是凸集C的顶点。二、基本定理定理1：若线性规划问题存在可行解，则问题的可行域是凸集。引理：LP的可行解为基可行解的充要条件是X的正分量所对应的系数列向量是线性独立的。定理2：LP的基可行解X对应LP可行域的顶点。定理3：若LP有最优解，一定存在一个基可行解是最优解。三、单纯形法迭代原理由上述定理3可知，如果LP存在最优解，一定有一个基可行解是最优解，因此单纯形法迭代的基本思想是：行找出一个基可行解，判断其是否为最优解，如为否，则转换到相邻的基可行解，并使目标函数值不断增大，一直找到最优解为止。四、最优性检验与解的判定对LP的求解结果可能出现唯一最优解、无穷多最优解、无界解、和无可行解四种情况，因此需要建立对解的差别准则。若为一个基可行解：（1） 若对一切，有，则为最优解；（2） 若对一切，有，又存在某个非基变量检验数，则线性规划有无穷多最优解；（3） 若有一个，并且对有，那么该LP具有无界解；（4） 若在最终单纯形表中，所有，而在其中含有某非零人工变量，则表示无可行解。1.5单纯形法计算步骤一、单纯形表为了书写规范和便于计算，对单纯形法的计算设计了一种专门表格，称为单纯形表。迭代计算中每找出一个新的基可行解时，就重画一张单纯形表。初始基可行解的单纯形表称初始单纯形表，含最优解的单纯形表称最终单纯形表。单纯形表的基本结构：100。0100二、单纯形法计算步骤根据上节中讲述的原理，单纯形法的计算步骤如下：1.将一般形式转化为标准形式；2.从标准形式中求出初始基可行解，建立初始单纯形表。对标准形式的LP，在约束条件式的变量的系数矩阵中总会存在一个单位矩阵：其中：称为基向量，同其对应的变量称为基变量，模型中其他变量称为非基变量。若令所有非基变量为0，求出基变量的值，可以得到初始其可行解，将其数据代入单纯形表中，可以得到初始单纯形表。2.检验目前的基可行解是否最优：根据解的检验，是否是四种解中的一种，若是则结束运算，否则，转入下一步。3.从一个基可行解转换到相邻的目标函数值更大的基可行解，列出新的单纯形表。（1）确定换入的非基变量（换入变量）只要有检验数，对应的变量就可以作为换入的基变量，当有一个以上的检验数大于0时，一般从中找出最大一个，即，其对应的变量作为换入的非基变量，称为换入变量。（2）确定换出变量计算，确定是换出的基变量，元素决定了从一个基可行解到相邻基可行解的转移去向，称为（取名）主元素。(3)用换入变量替代换出变量，得到新的基、基可行解，并相应得到新的单纯形表。4.重复2、3两步，一直到计算结束为止。例1.7用单纯形法求解LPs.t解： 1.6单纯形法的进一步讨论我们在前面介绍中讲到用单纯形法来求解LP时，首选要得到一个初始基可行解，某些LP标准化后就有一个初始基可行解，但有一些标准化后没有初始基可行解，必须通过给约束条件中加上人工变量来得到初始基可行解。因为人工变量是后加入到原约束条件中的虚拟变量，要求将他们从基变量中逐个替换出来，基变量中不再含有非零人工变量，这表明原问题有解，若在最终单纯形表中，当时，而其中仍有某个非零人工变量，表明原LP无解。对加入人工变量的LP的解决方法有两种：大M法和两阶段法。一、大M法在一个LP的约束条件中加入人工变量后，要求人工变量对目标函数取值不受影响，为此假定人工变量在目标函数中的系数为M（M为任意大的正数）。这样，目标函数要实现最大化时，必须把人工变量从基变量换出，否则，目标不可能实现最大化。例1.8：用单纯形法求解下列LP解： 二、两阶段法用大M法求解含人工变量的LP时，用手工计算不会碰到麻烦，但用电子计算机求解时，对M就只能在计算机内输入一个机器最大字长的数字，这就可能造成一种计算上的误差，为克服这个困难，对添加人工变量后的LP分两个阶段来计算，称为两阶段法。第一阶段：不考虑原问题是否存在基可行解，给原LP加入人工变量，并构造仅含人工变量的目标函数Minw,然后用单纯形法求解，若得w=0，说明原LP存在基可行解，可进行第二阶段计算，否则，停止计算。第二阶段：将第一阶段计算得到的最终单纯形表除去人工变量，将目标函数行的系数换成原LP的目标函数，作为第二阶段计算的初始表。然后按照前面的方法进行计算。例1.9：试用两阶段法计算例1.8解： 三、单纯形法计算中的几个问题：1.目标函数极小化时解的最优性判别。有些书中规定求目标的极小化为LP的标准形式，这时只需以所有检验数作为表中解是否最优的标志。2.退化：单纯形法计算中用规则确定换出变量时，有时存在两个以上相同的最小比例，这样在下一次迭代中应有一个或几个基变量等于0，这就出现退化现象。退化现象出现的原因是模型中存在多余的约束，使多个基可行解对应同一顶点。当存在退化现象时，就可能出现循环计算。为了避免循环计算，1974年由勃兰特（Bland）提出一种简便的规则：（1） 选取中下标最小的非基变量为换入变量；（2） 当计算出值存在两个和两个以上最小比值时，选取下标最小的基变量为换出变量。1.7 应用举例一般讲，一个经济管理问题凡满足以下条件时，才能建立线性规划模型：（1） 要求解问题的目标函数能用数值指标来反映，且为线性函数；（2） 存在多种方案；（3） 要求达到的目标是在一定约束条件下实现的，这些约束条件可用线性等式或不等式来描述。例1.下料问题某工厂现要做100套钢架，每套用长2.9m、2.1m和1.5m的元钢各一根，已知原材料长7.4m，问应如何下料，使用的原材料最少。解：最简单的做法是：在每一根材料上截取2.9m、2.1m和1.5m的元钢各一根组成一套，每根原材料余下料头0.9m，为了做100套钢架，需用原材料100根，有90m料头余下。若改为套裁，可以节约原材料，假设