广工管理运筹学运筹学绪论及

广工管理运筹学运筹学绪论及第1页/共113页2绪论什么是运筹学运筹学研究的基本特征和基本方法运筹学的主要分支运筹学与管理科学第2页/共113页3什么是运筹学（不同的定义）《大英百科全书》《中国大百科全书》《辞海》《中国企业管理百科全书》第3页/共113页4《大英百科全书》的定义运筹学是一门应用于管理有组织系统的科学。运筹学为掌管这类系统的人提供决策目标和数量分析的工具。第4页/共113页5《中国大百科全书》的定义运筹学用数学方法研究经济、民政和国防等部门在内外的约束条件下合理分配人力、物力、财力等资源，是实际系统有效运行的技术科学，它可以用来预测发展趋势，制订行动规划或优选可行方案。第5页/共113页6《辞海》的定义运筹学主要研究经济活动与军事活动中能用数量来表达有关运用、筹划与管理方面的问题，它根据问题的要求，通过数学的分析与运算，作出综合性的合理安排，以达到经济有效地使用人力物力。第6页/共113页7《中国企业管理百科全书》的定义运筹学应用分析、实验、量化的方法，对经济管理系统中人财物等有限资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。第7页/共113页8英国——Operationalresearch美国——Operationsresearch夫运筹帷幄之中，决胜千里之外。——史记齐王赛马丁渭修宫二战时英国的防空雷达系统第8页/共113页9运筹学的发展大致可分三个阶段:运筹学诞生的三个来源：军事、管理和经济1945---1950年代,创建时期;1950年代,成长时期;1960年代至今,普及和发展时期.第9页/共113页10运筹学的基本特征系统的整体观念多学科的综合应用模型技术第10页/共113页11运筹学能够对经济管理系统中的人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。通常以最优、最佳等作为决策目标，避开最劣的方案。第11页/共113页12运筹学的基本方法

——模型化的方法应用步骤：分析与表述问题建立模型求解模型与优化方案测试模型及对模型进行必要的修正建立对解的有效控制方案的实施第12页/共113页13决策过程（问题解决的过程）：1）认清问题；2）找出一些可供选择的方案；3）确定目标或评估方案的标准；4）评估各个方案：解的检验、灵敏性分析等；5）选出一个最优的方案：决策；6）执行此方案：回到实践中；7）进行后评估：考察问题是否得到完满解决；

1）2）3）：形成问题；

4）5）：分析问题：定性分析与定量分析。构成决策。

第13页/共113页14运筹学的主要分支线性规划(linearprogramming)非线性规划(nonlinearprogramming)动态规划(dynamicprogramming)图与网络分析(graphtheoryandnetworkanalysis)存贮论(inventorytheory)排队论(queueingtheory)对策论(gametheory)决策论(decisiontheory)第14页/共113页15第四节运筹学与管理科学国际上目前通行的说法：“运筹学”与“管理科学(managementsciences)”在许多场合实际是指同一学科，不过前者强调方法而后者强调应用。因此运筹学是现代科学管理的基础，从而在管理中有非常广泛的应用。第15页/共113页16生产计划：生产作业的计划、日程表的编排、合理下料、配料问题、物料管理等，追求利润最大化和成本最小化库存管理：多种物资库存量的管理，库存方式、库存量等运输问题：确定最小成本的运输线路、物资的调拨、运输工具的调度以及建厂地址的选择等人事管理：对人员的需求和使用的预测，确定人员编制、人员合理分配，建立人才评价体系等市场营销：广告预算、媒介选择、定价、产品开发与销售计划制定等财务和会计：预测、贷款、成本分析、定价、证券管理、现金管理等***设备维修、更新，项目选择、评价，工程优化设计与管理等第16页/共113页17运筹学方法使用情况(美1983)第17页/共113页18

运筹学方法在中国使用情况

(随机抽样)第18页/共113页19运筹学在国内或国外的推广应用前景是非常广阔的。工商企业对运筹学应用的需求是很大的。在工商企业推广运筹学方面有大量的工作要做。第19页/共113页20由国际运筹与管理科学协会（INFORMS）和它的管理科学实践学会（CollegeforthePracticeoftheManagementSciences）主持评奖的负有盛名的弗兰茨·厄德曼（FranyEdlman）奖，就是为奖励优秀的运筹学在管理中的应用的成就设立的，该奖每年举行一次，在对大量富有竞争力的入围者进行艰苦的评审后，一般有六位优胜者获奖。关于这些获奖项目的文章都在第二年发表在著名刊物Interface的第一期上，下面列表就是发表在Interface期刊的一些获奖项目。第20页/共113页21组织应用Interface期刊号

每年节支（美元）联合航空公司满足乘客需求前提下,以最低成本进行订票及安排机场工作班次1-2/1986600万Citgo石油优化炼油程序及产品供应、配送及营销1-2/19877000万荷马特发展公司（HomartDevelopmentCo.）优化商业区和办公楼销售程序1-2/19874000万AT&T优化商业用户的电话销售中心选址1-2/19904.06亿，更多销售标准品牌公司控制成品库存（制定最优再订购点和订购量，确保安全库存）12/1981380万施乐公司通过战略调整，缩短维修机器的反应时间和改进维修人员的生产率11/1975第二部分生产率提高50%以上宝洁公司重新设计北美生产和分销系统以降低成本并加快了市场进入速度1-2/19972亿法国国家铁路制定最优铁路时刻表并调整铁路日运营量1-2/19981500万更多年收入Delta航空公司进行上千个国内航线的飞机优化配置来最大化利润1-2/19941亿IBM重组全球供应链，保持最小库存的同时满足客户需求1-2/2000第一年7.5亿Merit青铜制品公司安装统计销售预测和成品库存管理系统，改进客户服务1-2/1993更优的服务第21页/共113页22第二章线性规划线性规划问题及其数学模型图解法单纯形法原理单纯形法计算步骤单纯形法的进一步讨论应用举例第22页/共113页23第一节线性规划及其数学模型问题的提出线性规划的数学模型线性规划的标准形式第23页/共113页24例1

美佳公司计划制造I、II两种家电产品，已知各制造一件分别占用的设备A、B的台时、调试时间、调试工序每天可用于这两种家电的能力、各售出一件的获利情况如下表所示。III每天可用能力设备A（h）设备B（h）调试工序（h）06152115245利润（元）21问该公司应每天制造两种家电各多少件，使获取的利润最大。第24页/共113页25例2捷运公司租借仓库的问题捷运公司在下一年度的1-4月的4个月内拟租用仓库堆放物资。已知各月份所需仓库面积如下表所示。仓库租借费用随合同期而定，期限越长，折扣越大，具体数字见表。租借仓库的合同每月初都可办理，每份合同具体规定租用面积和期限。因此，该厂可根据需要，在任何一个月初办理租借合同。每次办理时可签一份合同，也可签若干份租用面积和租期不同的合同。试确定该公司签订租借合同的最优决策，目的是使所付租借费用最小。第25页/共113页26月份1234所需仓库面积(100m2)15102012合同租借期限1个月2个月3个月4个月合同期内的租费(元/100m2)2800450060007300第26页/共113页27例1、例2的共同点

在现有各项资源条件的限制或约束下，如何确定方案，使预期目标达到最优。例1的资源限制：设备A、B与调试工序每天可用时数。目标：总利润最大例2的资源约束：租期内每月所需的仓库面积数。目标：总租金最小第27页/共113页28线性规划研究的问题大体上可归为两类：1、给出一定量的人力、物力、财力等资源，如何统筹规划这些有限资源完成最大任务；2、对于给定的任务，如何运筹规划，合理安排，以最少资源来完成它。第28页/共113页29线性规划要研究的两类问题中都包含有限制或约束条件：第一类问题的约束条件是“给出一定量的人力、物力和财务等资源”；第二类问题是“给定的任务”。在线性规划中，我们常要求这种约束条件可以用一组线性方程或线性不等式来描述。在约束满足的条件下，所要达到的结果称“目标”，第一类问题的目标是利用有限资源完成最大任务，第二类问题的目标是要用最少资源完成给定任务。在线性规划中，要求可以用一个线性函数来描述这种目标，并称这个线性函数为目标函数。线性规划研究的各种实际问题尽管约束条件与目标不相同，但规划的目的就是使这些资源发挥最大限度的作用，从而完成最多最大的任务。换句话说，也就是资源的最优利用问题。用数学的方式描述，规划的目的就是在给定的限制条件（或称约束条件）下，求目标函数的极值问题（包括极小值和极大值）。第29页/共113页30模型——数学规划问题第30页/共113页31例1的数学模型第31页/共113页32第32页/共113页33例2的数学模型第33页/共113页34例1

穗羊公司要加工两种产品I、II，需要使用两种原材料及某专用生产设备等三种资源，分别记为A、B、C。生产这两种产品的单位资源消耗、这些资源的每周可使用量及每单位产品可获利润见下表：III每周可使用量A（千克）125B（吨）214C（百工时）439单位产品利润（万元）32问该公司每周应生产产品I与产品II各多少单位，才能使每周的获利达到最大？第34页/共113页35根据问题所给数据，当产品I、II每周的产量分别是x1和x2时，总利润为因此我们的目标就是再考虑资源的限制:因此关于A原材料，我们有约束条件：关于B原材料，有约束条件：关于设备，有约束条件：此外产品I和II每周的产量不可能是负数，因此关于这两个变量，还有约束：第35页/共113页36将上述数学表达式合起来，就得到这个问题的数学模型为：其中s.t.是英文词组subjectto的缩写，表示“受限制于”的意思，有时也约去不写出来。例1中的问题常称为生产计划问题或产品组合（productmix）问题。第36页/共113页37例2

设有一批规格为10米长的圆钢筋，将它截成分别为3米，4米长的预制构件的短钢筋各100根，问怎样截取最省料。因为，10米长的钢筋截为3米或4米长，共有三种截法：截法Ⅰ：3331米截法Ⅱ：3340米截法Ⅲ：4402米假设按截法Ⅰ，Ⅱ，Ⅲ各截取10米长的钢筋分别为x1,x2,x3根则可以获得3米长的短钢筋的根数是4米长短钢筋的根数是按问题要求它们应该不小于100根。总共用料是要达到最省料的目的，就必须使总用料最小。第37页/共113页38例2的模型就是例2中的问题常称为下料问题。第38页/共113页39模型的特征模型的三个要素（1）决策变量（2）目标函数（3）约束条件线性规划模型的特征（1）目标函数是决策变量的线性函数（2）约束条件是含决策变量的线性等式或不等式第39页/共113页40线性规划模型的一般形式第40页/共113页41线性规划模型的一般形式（续1）决策变量：价值系数：资源常数：技术（工艺）系数：第41页/共113页42线性规划模型的一般形式（续2）利用和号∑简化模型的表示第42页/共113页43线性规划模型的一般形式（续3）向量形式：式中第43页/共113页44线性规划模型的一般形式（续4）矩阵形式：其中第44页/共113页45线性规划模型的一般形式（续5）注：决策变量通常是非负的，但从数学意义上决策变量可以取非正的值，或取任何实数。第45页/共113页46线性规划问题的（模型）的标准形式第46页/共113页47标准形式的特征目标函数为求最大值约束条件均为等式资源常数非负决策变量只能取非负值不具备上述所有特征的线性规划问题称为非标准形式的线性规划问题第47页/共113页48化线性规划问题为标准形式的方法（1）目标函数为求最小值的，即将目标函数用其相反数代替，得到新的目标函数，即令则求原目标函数的最小值问题等价于求新目标函数的最大值问题第48页/共113页49化线性规划问题为标准形式的方法（续1）（2）右端常数小于零，即将该约束条件两端同乘（-1）（3）约束条件为不等式“”型，左端加上一个非负的松弛变量“”型，左端减去一个非负的剩余变量松弛变量和剩余变量在目标函数中的系数为零第49页/共113页50化线性规划问题为标准形式的方法（续2）（4）取值无约束的变量。用两个非负变量的差表示该变量。（5）取非正值的变量。用其相反数代替该变量P15例3第50页/共113页51线性规划问题要处理的内容x1,x3右端常数不等式不等式最小化目标处理后第51页/共113页52第二节图解法有关概念满足所有约束条件的一组决策变量x1,x2,…,xn称为LP问题的可行解所有可行解的集合称为可行域使得目标函数值达到最大的可行解称为LP问题的最优解（对最大化问题而言）求解LP问题就是求出其最优解第52页/共113页53

图解法及其目的图解法即通过平面作图的方法求解线性规划，适用于只含两个决策变量的简单LP问题。图解法的目的有二，一是利用它来说明LP问题求解的可能结局。二是在LP问题最优解存在时，求出最优解。采用图解法时通常无须将LP问题化为标准形式第53页/共113页54图解法步骤：在平面上建立直角坐标系图示约束条件，找出可行域图示目标函数寻找最优解第54页/共113页55例1Maxz=2x1+x2s.t.5x2≤156x1+2x2

≤24

x1+x2≤5x1,x2≥0x2=33x1+x2=12x1+x2=5最优解可行域x1x2第55页/共113页56线性规划问题几种可能的结局有唯一的最优解有无穷多个最优解无界解4.无解（无可行解）第56页/共113页57由图解法得到的启示揭示了求LP问题的解的可能情况若可行域非空，则必为凸集若LP问题的最优解存在，则最优解或最优解之一是可行域的顶点LP问题的求解思路（单纯形法）先找出可行域的任一顶点，计算该顶点处的目标函数值；比较周围相邻顶点的目标函数值是否比这个值大，如果为否，则该顶点为最优解（或最优解之一）对应的点，否则转到比这个点目标函数值更大的顶点，重复上述过程，直到找出目标函数值最大的顶点为止。第57页/共113页58第三节单纯形法原理线性规划解的基本概念考虑标准形式的线性规划问题可行解——满足所有约束条件的解X=(x1,x2,…,xn)T,称为LP问题的可行解。所有可行解的集合称为可行域。最优解——使得目标函数达到最大值的可行解称为最优解。LP问题的可行域是一个凸集。第58页/共113页59基——设A为约束方程组的m╳n阶系数矩阵（通常总假定n>m，且A的秩=m），若B是A的一个m╳m阶的满秩子矩阵，则称B是LP问题的一个基。若B是LP问题的一个基，则它的每一个列向量称为基向量，与基向量对应的变量称为基变量LP问题的基本概念（续1）第59页/共113页60秩的概念如果矩阵A中有一个r阶子式Dr不等于零，而所有r+1阶子式（如果存在的话）的值全等于零，则称Dr为矩阵A的一个最高阶非零子式，其阶数r称为矩阵A的秩。注：Dr为行列式r的值。第60页/共113页61LP问题的基本概念（续2）基解在约束方程组 中令所有的非基变量xm+1=xm+2=…=xn=0,则由于剩下的变量（基变量）构成的方程组的系数行列式|B|≠0，因此约束方程组此时有唯一的解XB=（x1,x2,…,xm,0,…,0)T这个解称为LP问题的（对应基B的）基解。很明显，对应着不同的基，LP问题有不同的基解。因此LP问题的基解不是唯一的，但总数不超过 此外基解不一定是可行解。第61页/共113页62LP问题的基本概念（续3）基可行解——满足非负约束条件的基解称为基可行解可行基——对应着基可行解的基称为可行基很明显LP问题的基可行解是有限的。并且每一个基可行解对应着可行域的一个顶点。第62页/共113页63找出下述线性规划问题的全部基解，指出其中的基可行解，并确定最优解。第63页/共113页64序号x1x2x3x4x5z是否基可行解10051045是20452017是35005410是40550-120否5100-50415否652.5001.517.5是7540-3022否82430019*是第64页/共113页65凸集及其顶点凸集——如果一个非空集合中任意两点的连线段上所有点仍属于该集合，则称该集合为凸集。凸集的顶点——若凸集中的一个点不是任何另外两点连线段上的点，则称该点为这个凸集的顶点。凸集凸集不是凸集顶点第65页/共113页66几个基本定理定理1

若LP问题存在可行解，则问题的可行域为凸集定理2LP问题的基可行解对应着LP问题可行域的顶点定理3

若LP问题有最优解，一定存在一个基可行解是最优解第66页/共113页67单纯形法迭代原理单纯形法迭代步骤：找出一个基可行解是否为最优解停止（依据：LP问题的最优解若存在，则一定有一个基可行解为最优解。）转换到相邻的基可行解，并使目标函数增大开始YN第67页/共113页681.求初始基可行解基可行解求基解求解线性方程组求基B或基变量第68页/共113页69求基可行解需要考虑的问题是否便于计算目标函数值是否便于判断其目标函数值是否为最大是否便于转换到目标函数值更大的相邻基可行解第69页/共113页70初始基可行解通常都是从一种特殊的基可行解出发求解LP问题，这一特殊的基可行解称为初始基可行解。初始基可行解对应的基，也称初始可行基，它具有特定的形式，它是单位矩阵或者由单位矩阵经过交换列以后得到的矩阵。相应的基变量称为初始基变量，它是一组变量，具有特点：共有m个变量，恰好每个约束方程包含一个变量，且该变量的系数为1。第70页/共113页71已知初始基变量，求初始基可行解以例1为例说明求法。添加松弛变量后例1可标准化为其中x3,x4,x5为初始基变量，初始基可行解为第71页/共113页722.判别最优性不难发现这时每个初始基变量取的值恰好就是包含这个变量的约束方程的右端常数值，非基变量取的值为零。将这个解代入到目标函数，就可得到这个解对应的目标函数值。目标函数目前的值为零，很明显如果能使的变量x1或x2取正值的话，目标函数的值还可以增加。所以目标函数还未达到其最大值。一般地，若目标函数已经表示成了非基变量的函数，且其中非基变量的系数中还有正数，则目标函数还可能增大。这时目标函数中各变量的系数称为检验数。这时目标函数的表达式为第72页/共113页733.旋转若基可行解不是最优解，则需要转到一个相邻的基可行解，并使得目标函数值增加。所谓相邻的基可行解是指两个基可行解只有一个基变量不同而其它的基变量都相同。要从一个基可行解转到与它相邻的基可行解，意味着需要将一个非基变量变成基变量，而且将一个原来的基变量变为非基变量，前者称为换入变量，后者称为换出变量。第73页/共113页74确定换入变量目的：新的基变量换入后，会使目标函数值增大（通常还希望增加的越大越好）因此选择在目标函数中系数为正值的非基变量作为换入变量，通常取在目标函数中最大的正系数对应的非基变量为换入变量，即取最大的正检验数对应的非基变量为换入变量。换入变量为x1对例1，这时目标函数为第74页/共113页75确定换出变量由于基变量只有m个，因此将一个非基变量变为基变量后，必须将一个原来的基变量变为非基变量，这个变量就是所谓的换出变量。换出变量与换入变量是密切相关的。设xk是换入变量。若xk>0，则第i个约束条件可以写成并且由于其余的非基变量保持零值，因此第75页/共113页76由此可见为保证xi≥0，就必须从而对所有的i，若aik>0，则第76页/共113页77若确定xk为换入变量，则可估计xk的取值，使得：其余的决策变量都取非负值；并且目标函数得到尽可能的增加。对前者，只须对所有的i成立，即为了使目标函数尽可能增加，显然应该有设i=l(1ln)时，上式右端达到最小值。由于因此xl=0。第77页/共113页78这意味着xl可以是非基变量。因此取xl为换出变量。也就是取使得成立的l对应的基变量xl为换出变量。对例1由于已经确定了x1是换入变量。而因此x4是换出变量24/65/1第78页/共113页79确定换出变量等价于确定了一组新的基变量，为了方便地求出相应的基解，接下来将进行如下的运算：将这组新的基变量的系数矩阵化为单位矩阵（或单位矩阵交换列后得到的矩阵），这等价于使得这组基变量中每个变量只出现在一个方程中并且在该方程中的系数为1，这称为旋转运算。旋转运算可以利用对约束方程组进行加减消元法完成。第79页/共113页80对例1的约束方程组第2式6第3式–第2式第80页/共113页81由此可以立即得到新的基解为很明显，它是基可行解。为了判断这一新的基可行解是否为最优解，需要将原目标函数改写为新的非基变量的函数。原目标函数为但是代入目标函数，得第81页/共113页82即其中系数1/3，-1/6分别是非基变量x2，x4的检验数。因此对应于这一新的基可行解，目标函数值为z=8。问题是这一目标函数值是否为最优的目标函数值。由于x2的系数（检验数）为1/3，是正数，因此如果能使x2取正数，则目标函数还能增加。因此该基可行解仍不是最优解。一般地，对一个基可行解而言，若非基变量的检验数中存在正数，则该解不是最优解；否则它一定是最优解。第82页/共113页83单纯形法求解过程小结（1）求出初始基可行解（2）通过非基变量在目标函数中的系数（检验数）是否都小于或等于零，判别该基可行解是否为最优解。若是，结束运算；否则进行下一步。（3）确定换入变量。取最大的正检验数对应的变量为换入变量。（4）确定换出变量。用换入变量在各方程中的正的系数去除该方程的右端常数，在除得的商中取最小者，该最小商所在方程中的基变量就是换出变量。由此得到一组新的基变量。（5）旋转运算。将新的基变量在约束方程中的系数矩阵化为单位矩阵（或单位矩阵交换列后的矩阵）。回到第（2）步。第83页/共113页84单纯形表的方法单纯形法的所有运算实际上都可归结为对LP模型的目标函数系数以及约束方程组的系数（矩阵）的运算。为了简化运算过程，并使运算过程程序化。人们构造了单纯形表来进行运算第84页/共113页850611000100011524552121x3x4x5x1x2x3x4x5bXb00021000Cb初始单纯形表例1中的模型化为标准形式后为σj第85页/共113页8621000CbXbbx1x2x3x4x5000x3x4x515245051006201011001σj21000基变量目标函数系数右端常数基变量在目标函数中的系数约束方程组系数矩阵检验数基可行解：目标函数值为：z=0这个基可行解不是最优解第86页/共113页8721000CbXbbx1x2x3x4x5000x3x4x515245051006201011001σj21000换入变量24/65/1换出变量主元旋转运算的目的：通过矩阵的初等行变换，使主元变为1，主元列的其他数变为0。变换后为21000CbXbbx1x2x3x4x5020x3x1x515410510011/301/6002/30-1/61σj01/30-1/30第87页/共113页8821000CbXbbx1x2x3x4x5020x3x1x515410510011/301/6002/30-1/6101/30-1/30基可行解为：目标函数值为：z=815/54/(1/3)1/(2/3)21000CbXbbx1x2x3x4x5021x3x1x215/27/23/20015/4-5/21001/4-1/2010-1/43/2000-1/4-1/2第88页/共113页8921000CbXbbx1x2x3x4x5021x3x1x215/27/23/20015/4-15/21001/4-1/2010-1/43/2000-1/4-1/2最优解为：最优目标函数值为：z=8.58½因此对例1中的问题，最优的生产计划安排是每天生产甲家电3.5件，乙家电1.5件，每天可以得到的最大利润为8.5元。（按此计划安排生产，每天设备A可富余7.5台时）第89页/共113页9021000CbXbbx1x2x3x4x5000x3x4x51524505100620101100124/65/1σj21000021x3x1x215/27/23/20015/415/21001/4-1/2010-1/43/28½000-1/4-1/2020x3x1x515410510011/301/6002/30-1/6115/54/(1/3)1/(2/3)σj01/30-1/30初始单纯形表最终单纯形表单纯形表合并的表示第90页/共113页91无穷多个最优解检验数的实际意义：检验数是非基变量每增加一个单位，目标函数的增加值。因此如果在最终单纯形表中，当所有的检验数都小于或等于零，并且存在非基变量的检验数等于零的情况时，LP问题存在无穷多个最优解。实际上，此时可选择检验数为零的非基变量为换入变量，迭代到一个新的基可行解，它的目标函数值等于最优解的目标函数值，从而也是最优解。因此有无穷多个最优解。第91页/共113页92无界解若换入变量（或正检验数）所在列的所有系数都小于或等于零，则LP问题为无界解。例如，如果单纯形表为21000CbXbbx1x2x3x4x5000x3x4x51524505100-62010-11001σj21000则目标函数无界。第92页/共113页93实际上换入变量为x1，相应的约束方程组为由于x2仍是非基变量，因此由此可见，不管x1取什么样的正数，x3、x4、x5都保持非负，这意味着x1的取值没有任何限制，从而目标函数值可以无限增加。第93页/共113页94最小化的线性规划问题在关于LP问题模型的标准形式中，关于目标函数的要求可以降低，即不必要求目标函数是求最大值，而可以是求最小值。对最小化的LP问题，单纯形法求解过程有两处值得注意的修改。1.最优解的判别：当所有检验数大于或等于0时，单纯形表给出的解是最优解2.换入变量的确定：最小的负检验数对应的变量为换入变量第94页/共113页95例求解如下的最小化LP问题第95页/共113页96第96页/共113页97单纯形法的进一步讨论如果约束方程不存在前面所述的初始基变量，处理的方式是通过添加人工变量来得到所需要的初始基变量。添加人工变量的方法是，先化约束条件为标准形式。然后在不含初始基变量的方程的左边人为地加上一个非负变量（人工变量），作为该方程的初始基变量，不同的方程添加的人工变量也不同。原来的条件分别为“”,“”和“”型，加人工变量的方法第97页/共113页98人工变量的处理人工变量是由于应用单纯形法求解的需要人为添加的变量，因此在最终单纯形表的基变量中不应包含人工变量。因此人工变量应该逐个从基变量中换出来。为了使人工变量能从基变量中逐个换出，可采用如下两种方法：大M法和两阶段法。第98页/共113页99大M法这种方法是（对最大化的LP问题）通过将人工变量在目标函数中的系数取成绝对值充分大的负数，因而迫使其尽快从基变量中换出。这样的负数通常写成“-M”。具体的做法是对最大化的LP问题，人工变量在目标函数中的系数取为“-M”对最小化的LP问题，人工变量在目标函数中的系数取为“M”然后再用单纯形法求解。若最优解的基变量中仍含有人工变量，则LP问题为无可行解。第99页/共113页100p30例6给定LP问题化成标准形式后为不存在前面那种初始基变量，因此要添加人工变量第100页/共113页101添加人工变量，并用大M法处理人工变量，模型变为然后用单纯形法求解该问题第101页/共113页102-30100-M-MCbXbbx1x2x3x4x5x6x70-M-Mx4x6x74191111000-21-10-1100310001σj-2M-34M10-M0000-Mx4x2x731630211-10-21-10-11060403-31σj6M-304M+103M-4M0第102页/共113页103-30100-M-MCbXbbx1x2x3x4x5x6x700-3x4x2x10310001-1/2-1/2-1/2011/30001/3102/301/21/21/6σj00303/2-M-3/2-M+1/2001x4x2x305/23/20001-1/2-1/2-1/2-1/2100-1/41/41/43/20103/4-3/41/4σj-9/2000-3/4-M+3/4-M-1/4最优解为最优目标函数值为第103页/共113页104两阶段法大M法的不足。两阶段法：添加了人工变量后，分两个阶段来求解LP问题。第一阶段：求解辅助的LP问题。辅助的LP问题构造如下：约束条件就是原来的（添加了人工变量后）条件，目标函数是所有人工变量之和，对这样的目标函数求最小值。若第一阶段的目标函数的最优值不等于零，则原LP问题无可行解，否则进入第二阶段。第104页/共113页105第二阶段：将第一阶