《第五章 线性规划.ppt》由会员分享，可在线阅读，更多相关《第五章 线性规划.ppt（134页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第五章 线性规划线性规划线性规划模型模型线性规划的线性规划的图解图解单纯形法单纯形法原理原理单纯形法单纯形法单纯形表单纯形表单纯形的理论分析单纯形的理论分析人工变量法人工变量法15.15.1线性规划的数学模型线性规划的数学模型一、问题的提出一、问题的提出例例1：生产计划问题：生产计划问题：问：甲乙各生产多少，使企业利润最大？问：甲乙各生产多少，使企业利润最大？设备产品ABC利润(元/公斤)甲35970乙95330限制工时5404507202解解:设产品甲、乙各生产设产品甲、乙各生产x1，x2公斤公斤设设总利润为总利润为Z，则：，则：设备产品ABC利润(元/公斤)甲35970乙95330限制工时
2、540450720资源约束资源约束变量非负变量非负约束约束3二、线性规划模型的一般特点二、线性规划模型的一般特点 Max(Min)z=c1x1+c2x2+cnxna11x1+a12x2+a1nxn(=或或)b1a21x1+a22x2+a2nxn(=或或)b2am1x1+am2x2+amnxn(=或或)bmxj(j=1,n)()0，或者没有限制或者没有限制s.t.cj为价值系数为价值系数反映了客观限制条件。反映了客观限制条件。明确的目标要求，极大或极小明确的目标要求，极大或极小行动方案行动方案线性规划模型的一般形式：线性规划模型的一般形式：1 1、决策变量：、决策变量：向量向量(x x1 1 x
3、 xn n)T T2 2、目标函数：、目标函数：Z=(Z=(x x1 1 x xn n)线性式，线性式，3 3、约束条件：、约束条件：线性等式或不等式线性等式或不等式变量约束变量约束约束方程约束方程4 资源资源产品产品煤（吨）煤（吨）金属材料金属材料（公斤）（公斤）电力电力（千瓦）（千瓦）产品利润产品利润（元元/吨）吨）A680506000B850105000资源供应量资源供应量54040002000表表2：例例2：资源合理利用问题：资源合理利用问题：某某厂厂生生产产A、B两两种种产产品品，都都需需用用煤煤、金金属属材材料料、电电力力等等资资源，各产品对三种资源的消耗及可供利用的资源如表源，各
4、产品对三种资源的消耗及可供利用的资源如表2示：示：问：应如何安排生产，使企业获利最大？问：应如何安排生产，使企业获利最大？三、常用的线性规划模型三、常用的线性规划模型 5解：设产品解：设产品A、B产量分别为变量产量分别为变量x1，x2（吨），则：吨），则：资源资源产品产品煤（吨）煤（吨）金属材料金属材料（公斤）（公斤）电力电力（千瓦）（千瓦）产品利润产品利润（元元/吨）吨）A680506000B850105000资源供应量资源供应量540400020006例例3、合理下料问题：、合理下料问题：有有一一批批长长度度为为180厘厘米米的的钢钢管管，需需截截成成70、52和和35厘厘米米3种种管管料
5、料。它它们们的的需需求求量量分分别别不不少少于于100、150和和100根根。问问如如何下料才能使钢管的消耗量为最少？何下料才能使钢管的消耗量为最少？先找出各种可能的下料方式：（再在各种可能的下料方案中去先找出各种可能的下料方式：（再在各种可能的下料方案中去选择）选择）设在设在180厘米长的钢管上能下出厘米长的钢管上能下出u个个70厘米管料，厘米管料，v个个52厘米厘米管料，管料，w个个35厘米，则满足约束条件：厘米，则满足约束条件：70u+52v+35w180，其中，其中，u，v，w只能是正整数。只能是正整数。从最大尺寸管料下起：从最大尺寸管料下起：7I IIIIIIIIIIIIVIVV V
6、VIVIVIIVIIVIIIVIII702111000052021032103510130235合计合计175174157175156174157175余料余料56235246235各种可能的下料方案：各种可能的下料方案：82x1+x2+x3+x41002x2+x3+3x5+2x6+x7150 x1+x3+3x4+x6+3x7+5x8100 xi 0(i=1,8)，且为整数且为整数minZ=5x1+6x223x3+5x4+24x5+6x6+23x7+5x8解：设按第解：设按第j j种方案下料的原材料为种方案下料的原材料为x xj j根根 9例例4：运输问题：运输问题问：如何安排运输，使运输费用
7、最小？问：如何安排运输，使运输费用最小？冶炼厂冶炼厂矿山矿山B1B2B3B4总产量总产量A11.520.33100A270.81.4280A31.20.322.550总需求量总需求量5070803023010解：设解：设x xij ij为第为第i i个矿山运到第个矿山运到第j j个冶炼厂的矿石量个冶炼厂的矿石量 MinZ=1.5x11+2x12+0.3x13+3x14+7x21+0.8x22+1.4x23+2x24+1.2x31+0.3x32+2x33+2.5x34(万元万元)x11+x12+x13+x14=100 x21+x22+x23+x24=80 x31+x32+x33+x34=50 x
8、11+x21+x31=50 x12+x22+x32=70 x13+x23+x33=80 x14+x24+x34=30 xij0(i=1,2,3。j=1,2,3,4)第第i个矿山的产量个矿山的产量第第j个冶炼厂的需求量个冶炼厂的需求量11方案方案序号序号技改方案内容技改方案内容决策决策变量变量投资（万元）投资（万元）年收益年收益(万元万元)第一年第一年第二年第二年1更新旧装置，提高炼更新旧装置，提高炼油能力油能力500桶桶/天天x12001001002建造新装置，提高炼建造新装置，提高炼油能力油能力1000桶桶/天天x23001502003往新厂建输油管，提往新厂建输油管，提高炼油能力高炼油能力
9、100桶桶/天天x315050504往老厂建输油管，提往老厂建输油管，提高炼油能力高炼油能力50桶桶/天天x410070305增加槽车运输能力，增加槽车运输能力，能提高出油能提高出油20桶桶/天天x5504020例例5：投资方案选择问题（：投资方案选择问题（01规划规划）12又又要要求求：方方案案1 1和和2 2只只能能选选择择其其中中一一种种，不不能能兼兼而而实实现现，并并且且，选择方案选择方案2 2，则方案，则方案3 3必须与必须与2 2同时选择，或者都不选择。同时选择，或者都不选择。现现该该公公司司可可供供支支配配的的资资金金总总额额为为：第第一一年年有有650650万万元元，第第二二年
10、年仅仅有有460460万万元元。要要求求技技改改后后，至至少少增增加加出出油油能能力力500500桶桶/天天，但但又又不不得得超超过过11001100桶桶/天天，确确定定该该公公司司总总经经济济效效益益最最大大的的投投资资方方案。案。解解：1 1）确确定定决决策策变变量量：方方案案的的选选择择只只有有两两种种状状态态，选选或或不不选，设选，设xj（j=1,5）为第为第j方案的取舍，有：方案的取舍，有：2）目标函数：）目标函数：maxZ=100 x1+200 x2+50 x3+30 x4+20 x513200 x1+300 x2+150 x3+100 x4+50 x5650（万元）万元）200
11、x1+150 x2+50 x3+70 x4+40 x5460500 x1+1000 x2+100 x3+50 x4+20 x5500500 x1+1000 x2+100 x3+50 x4+20 x51100 x1+x21-x2+x3=0 xj=1或或0(j=1,5)3)约束条件：约束条件：（投资总额约束（第一、二年），生产能（投资总额约束（第一、二年），生产能力增加约束，方案制约约束，变量的取舍限制。力增加约束，方案制约约束，变量的取舍限制。14例例6：人员分派问题数模（：人员分派问题数模（01规划规划）每项工作只能由一个人承担，每人做每项工作的工作效每项工作只能由一个人承担，每人做每项工作的
12、工作效率如上表所示，率如上表所示，现在怎样安排工作使总的效率最大。现在怎样安排工作使总的效率最大。工作工作人员人员ABCD甲0.60.20.30.1乙0.70.40.30.2丙0.81.00.70.3丁0.70.70.50.415解：设解：设xij为第为第i个人做第个人做第j项工作，（项工作，（xij=1或或0）MaxZ0.6x11+0.2x12+0.3x13+0.1x14+0.7x21+0.4x22+0.3x23+0.2x24+0.8x31+x32+0.7x33+0.3x34+0.7x41+0.7x42+0.5x43+0.4x44x11+x12+x13+x14=1x21+x22+x23+x2
13、4=1x31+x32+x33+x34=1x41+x42+x43+x44=1x11+x21+x31+x41=1x12+x22+x32+x42=1x13+x23+x33+x43=1x14+x24+x34+x44=1xij=1或或0(i=1,.,4。j=1,4）每一项每一项工作都有工作都有人做人做每个人只做一项每个人只做一项工作工作16v线性规划建立模型步骤：线性规划建立模型步骤：确定一组决策变量确定一组决策变量确定目标函数确定目标函数确定对决策变量的约束条件确定对决策变量的约束条件线性规划建模小结线性规划建模小结 v线性规划的共同点：线性规划的共同点：要解决的问题的目标可以用数值指标反映要解决的问
14、题的目标可以用数值指标反映对于要实现的目标有多种方案可选择对于要实现的目标有多种方案可选择有影响决策的若干约束条件有影响决策的若干约束条件17作业：作业：现有一家公司准备制定一个广告宣传计划来宣传开发的新产品，以现有一家公司准备制定一个广告宣传计划来宣传开发的新产品，以使尽可能多的未来顾客特别是女顾客得知。现可利用的广告渠道有电视、广使尽可能多的未来顾客特别是女顾客得知。现可利用的广告渠道有电视、广播和报纸，根据市场调查整理得到下面的数据：播和报纸，根据市场调查整理得到下面的数据：项项目目电电 视视广广播播报报纸纸一般一般时间时间黄金黄金时时间间每个广告每个广告单单元的元的费费用用(元元)每个
15、广告每个广告单单元所接触的元所接触的顾顾客数客数(万人万人)每个广告每个广告单单元所接触的女元所接触的女顾顾客数客数(万人万人)40004030700090403000502015002010 该企业计划用于此项广告宣传的经费预算是该企业计划用于此项广告宣传的经费预算是8080万元，此外要求：万元，此外要求：1.1.至少有至少有200200万人次妇女接触广告宣传；万人次妇女接触广告宣传；2.2.电视广告费用不得超过电视广告费用不得超过5050万元万元,3.3.电视广告至少占用三个单元一般时间和两个单元黄金时间电视广告至少占用三个单元一般时间和两个单元黄金时间,4.4.广播和报纸广告单元均不少于
16、广播和报纸广告单元均不少于5 5个单元而不超过个单元而不超过1010个单元。个单元。试为该企业制定广告计划，使得广告所接触的未来顾客总数尽可能多，试为该企业制定广告计划，使得广告所接触的未来顾客总数尽可能多，建立线性规划数学模型。建立线性规划数学模型。185.2线性规划的图解法一、图解法求最优解的步骤一、图解法求最优解的步骤思思路路：在在直直角角坐坐标标系系中中，描描绘绘出出约约束束条条件件和和变变量量限限制制的的公公共区域，然后通过观察确定符合目标要求的变量的取值。共区域，然后通过观察确定符合目标要求的变量的取值。求解例求解例1中的生产计划问题中的生产计划问题：对于简单的线性规划问题对于简单
17、的线性规划问题(只有两个决策变量只有两个决策变量的线性规划的线性规划问题问题),我们通过图解法可以对它进行求解。我们通过图解法可以对它进行求解。19Ox1x280603070901 1、绘出约束方程的图形、绘出约束方程的图形2 2、确定可行解域、确定可行解域3 3、绘出目标函数图形、绘出目标函数图形4 4、确定最优解及目标函数、确定最优解及目标函数值值可行解域可行解域目标函数变形得：目标函数变形得：目标函数等值线目标函数等值线最优解最优解Q2(75,15)Q1Q3Q4Q5Q6Q7Q820几个概念：几个概念：v可行解：可行解：满足线性规划所有约束条件（满足线性规划所有约束条件（含约束方程与变量含
18、约束方程与变量约束）约束）的点。的点。v可行解域：可行解域：所在可行解的集合。所在可行解的集合。v最优解：最优解：使目标函数得到极值的可行解。最优解包括：唯使目标函数得到极值的可行解。最优解包括：唯一最优解和无穷多最优解。一最优解和无穷多最优解。v等值线：等值线：具有相同目标函数值的直线。具有相同目标函数值的直线。v法向量法向量(梯度梯度):由目标函数由目标函数系数系数组成的与组成的与等值线等值线垂直的向垂直的向量。量。21二、二维线性规划问题解的形式二、二维线性规划问题解的形式1、唯一最优解、唯一最优解2、无穷多个最优解、无穷多个最优解66843x2可行解域目标函数的等值线目标函数的等值线C
19、(1,2)Q2(4,2)Q3(2,3)x1MaxZ=x1+2x2x1+x26x1+2x28x23xi0(i=1,2)223、有可行解但无最优解、有可行解但无最优解maxZ=x1+x2-2x1+x24x1-x22x1,x20 x2x1-24-22可行解域可行解域(1,1)234、无可行解、无可行解MinZx1+2x2s.t.x1+x212x1+x24x1,x20 x2x11142(1,2)可行域为空可行域为空集，无可行集，无可行解解!24线性规划的可行解域为线性规划的可行解域为凸多边形（凸多边形（凸集）凸集）。可行解域可行解域凸多边形有若干个顶点，凸多边形有若干个顶点，顶点的个数是顶点的个数是有
20、限的。有限的。三、线性规划的几何意义三、线性规划的几何意义线线性性规规划划问问题题若若存存在在最最优优解解，则则最最优优解解必必可可在在其其可可行行域域的某一顶点上得到。的某一顶点上得到。Ox1x2Q2(75,15)60最优解最优解Q1Q3Q4Q5Q6Q7Q825四、单纯形法原理四、单纯形法原理Ox1x2Q2(75,15)60最优解最优解Q1Q3Q4Q5Q6Q7Q8找可行解域顶点的计算方法，但不找可行解域顶点的计算方法，但不是计算所有的顶点，而是从凸集的一是计算所有的顶点，而是从凸集的一个个顶点顶点出发，沿着凸集的边缘逐个验出发，沿着凸集的边缘逐个验算所遇到的顶点，直到找到目标函数算所遇到的顶
21、点，直到找到目标函数为为最优的顶点最优的顶点为止。如从为止。如从OQ1Q2或从或从OQ4Q3Q2。261.31.3单纯形法原理单纯形法原理5.35.3线性规划标准型和规范型线性规划标准型和规范型一、线性规划的一、线性规划的标准型标准型 约束方程均为约束方程均为等式等式方程。方程。右边常数右边常数bi为为正数正数。所有变量均为所有变量均为非负变量非负变量。目标函数求目标函数求max1、一般形式：、一般形式：27或写成或写成累加和累加和形式：形式：标准型的一般形式标准型的一般形式28或写成或写成矩阵矩阵形式：形式：其中：其中：292、化线性规划问题为标准型、化线性规划问题为标准型约束方程为约束方程
22、为“号，号，在方程式的左端在方程式的左端“”一个变量（变量一个变量（变量0 0，称为，称为松驰变量松驰变量），原不等式化为等式约束。，原不等式化为等式约束。约束方程为约束方程为“”号号在方程式的左端在方程式的左端“”一个变量（变量一个变量（变量0 0，称为，称为剩余变量剩余变量），原不等式化为等式约束。，原不等式化为等式约束。(1)(1)约束条件为等式约束条件为等式30（2 2）变量非负约束）变量非负约束若若x xk k为为无无约约束束变变量量（即即可可0 0，也也可可0 0），引引进进两两个个变变量量x xk k,x,xk k”（均均0 0），令令xk=xkxk”。在在规规划划模模型型中中去
23、去掉掉x xk k这个变量。这个变量。（3 3）约束方程右边常数）约束方程右边常数非负非负约束约束在方程两边同时乘以（在方程两边同时乘以（-1-1）使得约束方程右边常数变为非负）使得约束方程右边常数变为非负 31标准型为：标准型为：例例1：把下面的线性规划模型化为标准型：把下面的线性规划模型化为标准型：32得到得到该问题的的标准型准型为：(1)(1)用用x x4 4x x5 5替换替换x x3 3，其中，其中x x4 4，x x5 500(2)(2)在第一个约束不等式在第一个约束不等式号左端号左端加上加上松驰变量松驰变量x x6 6(3)(3)在第二个约束不等式左边在第二个约束不等式左边减去减
24、去松驰松驰变量变量x x7 7(4)(4)令令D DZ Z,把求把求minZ化成化成maxD例例2：把下面的线性：把下面的线性规划模型化为标准规划模型化为标准型：型：33二、线性规划的二、线性规划的规范规范型型要用单纯形法求解线性规划数学模型，还需要把数学模要用单纯形法求解线性规划数学模型，还需要把数学模型化成规范型。型化成规范型。1 1基、基变量与非基变量基、基变量与非基变量基：基：设设A是约束方程组的是约束方程组的mn维系数矩阵，维系数矩阵，B是矩阵是矩阵A中中m阶方阶方阵阵（行列式的值不为行列式的值不为0 0），则称），则称B是线性规划问题的一个基。是线性规划问题的一个基。基变量与非基变
25、量：基变量与非基变量：与基与基B对应的变量为基变量。其余变量为对应的变量为基变量。其余变量为非基变量。非基变量。设线性规设线性规划模型的划模型的标准型：标准型：34请列举出其中的请列举出其中的三三个基个基及对应的及对应的基变量基变量与与非基变量。非基变量。例例1：解：从约束系数矩阵可看出，该模型的基不超过解：从约束系数矩阵可看出，该模型的基不超过个。个。对应的基变量为对应的基变量为x3,x4,x5,非基变量为非基变量为x1,x2。35对应的对应的基变量基变量为为x1,x3,x4，非非基变量基变量为为x2,x5。对应的对应的基变量基变量为为x1,x2,x3，非非基变量为基变量为x4,x5。362
26、 2基本解和基本可行解基本解和基本可行解基本解：基本解：对某一确定的基，令对某一确定的基，令非基变量等于非基变量等于0，可求出，可求出m个约个约束方程的基变量的值，则这组解称为束方程的基变量的值，则这组解称为基本解基本解。基本可行解：基本可行解：若基本解还满足若基本解还满足决策变量非负决策变量非负要求，则这组基要求，则这组基本解称为本解称为基本可行解基本可行解（也称（也称基可行解基可行解）。）。37对对基基B1来来说说，令非基，令非基变变量量，则则可以得到一个基本解可以得到一个基本解 因因为为，故，故是基可行解。是基可行解。对对基基B2来来说说，令非基，令非基变变量量，则则可以得到一个基本解可
27、以得到一个基本解因因为为，故，故也是基可行解。也是基可行解。38对对基基B3来来说说，令非基，令非基变变量量，则则可以得到一个基本解可以得到一个基本解因因为为，故，故不是基可行解。不是基可行解。对对基基B4来来说说，令非基，令非基变变量量,则则可得基本解可得基本解因因为为，故，故也不是基可行解。也不是基可行解。393 3基可行解基可行解与可行解与可行解域域顶点顶点的关系的关系Ox1x2Q2(75,15)60最优解最优解Q1Q3Q4Q5Q6Q7Q8X(1)对应原点对应原点O,X(2)对应顶点对应顶点Q1,X(3)对应对应Q7.X(4)对应对应?40Ox1x2806090最优解最优解Q2(75,1
28、5)Q1Q3Q4Q5Q6Q7Q8非基变量非基变量基变量基变量基本解基本解X(x1,x2 x3,x4,x5)T对应点对应点x1,x2x3,x4,x5(0,0,540,450,720)TOx2,x5x1,x3,x4(80,0,300,50,0)TQ1x2,x4x1,x3,x5(90,0,270,0,-90)TQ5x4,x5x1,x2,x3(75,15,180,0,0)TQ241定理定理1 1：线性规划的：线性规划的基本可行解基本可行解对应于可行解域的对应于可行解域的顶顶 点点。从定理从定理1和单纯形的几何意义知，用单纯形法寻求最优解，和单纯形的几何意义知，用单纯形法寻求最优解，就可就可从从基本可行
29、解基本可行解（顶点顶点）出发，在）出发，在基本可行解（顶点）之基本可行解（顶点）之间变换间变换，如果，如果L.P.有最优解，则有最优解，则最优解最优解一定可在一定可在某一基本可行某一基本可行解（顶点）上得到解（顶点）上得到。这个方法可用来求有任意多个变量的线。这个方法可用来求有任意多个变量的线性规划模型！性规划模型！Ox1x2Q2(75,15)60最优解最优解Q1Q3Q4Q5Q6Q7Q842已是标准型；已是标准型；得初始基本可行解：得初始基本可行解：X X(1(1）=(0,0,540,450,720)=(0,0,540,450,720)T T,Z=0,Z=0。4 4、线性规划的、线性规划的规范
30、规范型型例例1：特点特点（1）基变量的值基变量的值刚好是约束方程刚好是约束方程右边的常数右边的常数；（2）目标函数）目标函数Z的值的值就是目标函数表达式中的就是目标函数表达式中的常数常数。含单位基；含单位基；目标函数用非基变量表示。目标函数用非基变量表示。规范规范型型条件：条件：43若取基变量若取基变量x x3 3,x,x4 4,x,x1 1,则基解及则基解及目标函数值？目标函数值？可把模型化成以基变量系数矩阵为单位阵的可把模型化成以基变量系数矩阵为单位阵的规范型规范型：得到基本可行解：得到基本可行解：，44引例引例1：求解下列线性规划模型的最优解：求解下列线性规划模型的最优解解：解：1、确定
31、初始基可行解、确定初始基可行解取取B1（P3P4P5）I，令非基变量令非基变量x1,x2=0，得，得X(1)（0,0,540,450,720）T，Z(1)0；（；（解的含义？）解的含义？）从规范型出发从规范型出发5.45.4单纯形法步骤单纯形法步骤452、判定解是否最优、判定解是否最优目标函数目标函数MaxZ0+70 x1+30 x2检检验验数数：用用非非基基变变量量表表达达的的目目标标函函数数中中变变量量前前的的系系数数Rj（判判别别数或检验数）。数或检验数）。当当x1从从0 或或x2从从0，Z从从0，X(1)不是最优解不是最优解3、由一个基可行解、由一个基可行解另一个基可行解。另一个基可行
32、解。(1)确定入基变量确定入基变量可选可选Rj0的任一变量入基。（的任一变量入基。（意义意义？）？）一般地，选择一般地，选择maxRj的变量入基，选的变量入基，选x1从从0，保持，保持x2=0(2)确定出基变量确定出基变量46问题：问题：确定确定入基变量入基变量x x1 1增加的增加的上上界界：从约束方程组怎样求解？：从约束方程组怎样求解？在在中，继续令中，继续令x x2 2为非基变量，即为非基变量，即x x2 2 0 0，求出当前每个，求出当前每个基变量出基基变量出基能使能使x x1 1增大的上界值增大的上界值。即：。即：x3=5403x10 x1180=540/3x4=4505x10 x1
33、90=450/5x5=7209x10 x180=720/947min180,90,80=min540/3,450/5,720/9=80,x5出基出基(变为变为0)，即即x x1 1的取值受第三种资源的约束。的取值受第三种资源的约束。规则：规则：入基变量满足约束条件下取最大值。（大中取小）入基变量满足约束条件下取最大值。（大中取小）x3=5403x10 x1180 x4=4505x10 x190 x5=7209x10 x180新的基变量为新的基变量为x x3 3,x,x4 4,x,x1 1，怎样求出新的基可行解？，怎样求出新的基可行解？把模型变成以把模型变成以基变量的系数矩阵基变量的系数矩阵为为
34、单位阵单位阵的规范型。的规范型。(3)求出新的基可行解求出新的基可行解48 以基变量以基变量x x3 3,x,x4 4,x,x5 5的系数矩阵的系数矩阵为单位阵的规范型为单位阵的规范型:（1 1）从）从出基变量出基变量x x5 5所在的方程所在的方程开始：方程两边同时除以开始：方程两边同时除以入基变入基变量量x x1 1的的系数系数9 9，得：，得：（2 2）方程）方程中消去中消去x x1 1（入基变量入基变量）：方程）：方程两边同时两边同时乘以某个数，加到方程乘以某个数，加到方程上。上。（3 3）目标函数中消去）目标函数中消去x x1 1：从方程：从方程中解出中解出x x1 1的值代入目的值
35、代入目标函数中：标函数中：新的基变量为新的基变量为x x3 3,x,x4 4,x,x1 1本质：就是线性代数中的高斯消去法本质：就是线性代数中的高斯消去法方程组同解变形方程组同解变形.49通通过过以以上上方方程程的的变变换换，原原线线性性规规划划模模型型等等价价于于以以下下模模型型（得到得到当前基表示的规范型当前基表示的规范型）：X(2)（80,0,300,50,0）T，Z(2)5600；对应图形上的对应图形上的Q Q1 1点。点。1、确定出新的基可行解、确定出新的基可行解502、判定解是否最优、判定解是否最优3、由一个基可行解、由一个基可行解另一个基可行解另一个基可行解。(1)确定入基变量确
36、定入基变量选择选择x2入基，即入基，即x2从从0，x5仍为仍为0从约束方程组求解从约束方程组求解x x2 2的最大取值，从而确定的最大取值，从而确定出基变量出基变量。同理：在同理：在中令中令x5=0，求出求出当前解下当前解下x2取值的上界。取值的上界。当当x2从从0，Z从从5600，X(2)不是最优解不是最优解.目标函数：目标函数：，R2=20/3,R5=-70/951=min37.5，15，24015，x4出基出基(2)确定新基可行解：确定新基可行解：x x3 3=300=3008x8x2 2 x x2 237.5 37.5 x x4 4=50=5010 x10 x2 2/3 /3 x x2
37、 21515x x1 1=80 x=80 x2 2/3 /3 x x2 2240240把模型变成以把模型变成以基变量基变量x x3 3,x,x2 2,x,x1 1的系数矩阵的系数矩阵为为单位阵单位阵的规范型。的规范型。新的基变量新的基变量x x3 3,x,x2 2,x,x1 152怎样把模型变成以怎样把模型变成以基变量基变量x x3 3,x,x2 2,x,x1 1的系数矩阵的系数矩阵为为单位阵单位阵的的规范型？规范型？(1)(1)从出基变量从出基变量x x4 4所在的方程所在的方程开始：使入基变量开始：使入基变量x x2 2的系数变成的系数变成1 1。(2)(2)用消元法消去方程用消元法消去方
38、程中的中的x x2 2。53X(3)（75,15,180,0,0）T，Z(3)5700；由方程组由方程组变形变形得：得：542、判定解是否最优、判定解是否最优目标函数目标函数X(3)（75，15，180，0，0）T，Z(3)5700；非基变量的非基变量的检验系数均为负数检验系数均为负数，故不能入基，否则使目标，故不能入基，否则使目标值劣化。值劣化。当前解为当前解为最优解最优解。最优解判断标准：最优解判断标准：（1 1）若若全部检验数全部检验数R Rj j 0 0，当前基本可行解为最优解。，当前基本可行解为最优解。（2 2）若存在若存在R Rj j 0 0，则当前解非最优，解可改进，寻求，则当前
39、解非最优，解可改进，寻求 更好的解。更好的解。551、确定初始基可行解。确定初始基可行解。本题确定初始基为单位阵本题确定初始基为单位阵I，令单位阵对应的变量为基变量，令单位阵对应的变量为基变量，可得到一个基本可行解。可得到一个基本可行解。小结：小结：单纯形法求解线性规划的过程单纯形法求解线性规划的过程规范型：规范型：AXbX0，b0A中含有一单位阵。中含有一单位阵。2、最优化检验、最优化检验：用当前可行基的非基变量的用当前可行基的非基变量的检验数检验数确定。确定。3、从一个基本可行解到另一个基本可行解从一个基本可行解到另一个基本可行解入基变量：由检验数确定。入基变量：由检验数确定。出基变量：由
40、出基变量：由规则确定。规则确定。56用单纯形法从另一条路径寻优？用单纯形法从另一条路径寻优？57cj c1 c2 cnCBXB x1 x2 xnxi1xi2ximZ R1 R2 RnZ05.55.5单纯形表单纯形表目标函数行：常数目标函数行：常数Z0在右边。在右边。581、由规范型列出初始单纯形表：、由规范型列出初始单纯形表：X(1)（0,0,540,450,720）TZ(1)0主元主元cj7030000CBXBx1x2x3x4x50 x3391005401800 x455010450900 x59300172080-Z70300000592、变换到下一单纯表（、变换到下一单纯表（变成以新基为
41、单位阵的规范型变成以新基为单位阵的规范型）思考：思考：单纯形表有什么特点？单纯形表有什么特点？（1 1）基变量基变量对应的约束方程中对应的约束方程中系数矩阵系数矩阵为单位矩阵。为单位矩阵。（2 2）目标函数）目标函数基变量的检验数为基变量的检验数为0 0。（3 3）基可行解基可行解(？)不同，反映在原表中就是对应的基不同。不同，反映在原表中就是对应的基不同。新的基变量：新的基变量：x3,x4,x1cj7030000CBXBx1x2x3x4x50 x30810-1/3300 37.50 x4010/301-5/9501570 x111/3001/980240-Z020/300-70/9-5600
42、主元主元60表表一一表表二二00003070-Z8072010039x509045001055x4018054000193x30 x5x4x3x2x1XBCB0003070Cj9-5600-70/90020/30-Z240801/9001/31x11550-5/91010/30 x4037.5300-1/30180 x3070?613、重复以上过程直到得最优解：、重复以上过程直到得最优解：思考：思考：在单纯形表中，怎样判断在单纯形表中，怎样判断LP问题已取得问题已取得最优解最优解？最优解判断标准：最优解判断标准：（1 1）若若全部检验数全部检验数R Rj j 0 0，当前基本可行解为最优解。，
43、当前基本可行解为最优解。（2 2）若存在若存在R Rj j 0 0，则当前解非最优，解可改进，寻求更，则当前解非最优，解可改进，寻求更好的解。好的解。62cj7030000CBXBx1x2x3x4x5b 0X3391005401800X455010450900 x59300172080-Z703000000 x30810-1/330037.50 x4010/301-5/9501570 x111/3001/980240-Z020/300-70/9-56000 x3001-12/5118030 x20103/10-1/61570 x1100-1/101/675-Z000-2-20/3-5700X*
44、=(75,15,180,0,0)T,Z=570063例例1：求解下列线性规划模型：求解下列线性规划模型：解：解：化线性规划模型为化线性规划模型为规范型规范型，并列出初始单纯形表：，并列出初始单纯形表：按单纯法迭代，计算如下表，得最优解为按单纯法迭代，计算如下表，得最优解为:X=(1500,0,0,3500,0)T,Z=600064-6000-20-3-10-Z15001/2021/21x13500-3/21-2-1/20 x4-3750-5/400-1/43/2-Z15007501/4011/4x350005000-11001x4000514-Z750300010412x52000800001
45、413x4bx5x4x3x2x1XBCB00514Cj41/265例例2：用单纯形法求解下列线性规划数学模型用单纯形法求解下列线性规划数学模型选选x x1 1、x x3 3、x x6 6为基变量为基变量 目标函数用目标函数用非基变量非基变量表示：表示：由由 约束方程约束方程(1)(2)(3)(1)(2)(3)解出解出x x3 3=6-x=6-x2 2+x+x4 4-2x-2x5 5 x x1 1=5-2x=5-2x2 2+2x+2x4 4代入目标函数得：代入目标函数得：Min Z=11-4xMin Z=11-4x2 2+3x+3x4 4-5x-5x5 5 把把LP化成求极大的规范型：化成求极大
46、的规范型：66XBx1x2x3x4x5x6bx1120-2005x3011-12063x602013188/3-D040-3501167X(3)=(0，5/2，3/2，0，1，0)TD(3)=4，Z4-4-5/30-400-1/3-D11/31100-1/3x53/2-2/30-2101/6x35/200-1011/2x2-7/3-5/30-14/302/30-D48/31/311/302/30 x52/3-2/30-5/31-1/30 x35/2500-2021x11105-3040-D8/38131020 x63602-1110 x3500-2021x1bx6x5x4x3x2x1XB68假
47、设目标函数求极大假设目标函数求极大MAX1 1、从、从规范型规范型出发，得出一个初始基可行解。按要求填入表中。出发，得出一个初始基可行解。按要求填入表中。2 2、最优化检验：若还存在、最优化检验：若还存在R Rj j00，则当前解不是最优解。，则当前解不是最优解。3 3、解的改进：、解的改进：由由检验数检验数确定入基变量确定入基变量x xp p。(一般正系数大的变量先入基一般正系数大的变量先入基)确定出基变量确定出基变量:确定确定L L为出基行，则为出基行，则x xL L为换出变量。得到一个新的可行基。为换出变量。得到一个新的可行基。单纯形算法步骤单纯形算法步骤4 4、用、用初等行变换方法初等
48、行变换方法把把主元（主元（a aLpLp）变为变为1 1，把，把入基列入基列（含（含其检验数）中除主元的其它元素消为零。转其检验数）中除主元的其它元素消为零。转2.2.69讨论：单纯形表进行求解的特殊情况（1）若）若最大检验数有两个或两个以上并且相等最大检验数有两个或两个以上并且相等，应如何确定，应如何确定入基变量，理论上可任选一个非基变量入基，但在实际应用入基变量，理论上可任选一个非基变量入基，但在实际应用中，可采用以下法则：中，可采用以下法则：XBx1x2x3x4x5b12x33910054018060 x4550104509090 x59300172080240-Z70700000依次选
49、择依次选择X X1 1和和X X2 2入基，分别计算出两组比值入基，分别计算出两组比值 1 1和和 2 2，每组，每组比值中分别选择最小值得比值中分别选择最小值得8080和和6060，两个最小值中选择最大值，两个最小值中选择最大值8080，因此确定，因此确定X X1 1入基，此时入基，此时目标函数值改变得最快目标函数值改变得最快(?)(?)。70（2）原问题有解但无最优解）原问题有解但无最优解(无界无界)的判断：某个的判断：某个Rj0,但但aij0(i=1,2,m)。例例4 4：求解线性规划问题：求解线性规划问题：XBx1x2x3x4bx33-2101x42-1014Z1100标准化标准化71
50、一、最优决策变量的解一、最优决策变量的解最优解是单纯形法的基本目标信息，在建模参数可靠最优解是单纯形法的基本目标信息，在建模参数可靠的基础上，它提供最优决策方案的基础上，它提供最优决策方案 。如例如例2中：中：最优解：最优解：X(3)（75，15，180，0，0）T，Z(3)5700；X4=0，X5=0，表明资源，表明资源B、C没有剩余，为企业的没有剩余，为企业的关键资源关键资源；X3=180，资源，资源A还剩还剩180个单位。个单位。应设法提高关键资源的获得量。应设法提高关键资源的获得量。二、松弛变量的解二、松弛变量的解单纯形表的每一个基本可行解，还包含有松弛变量的解，单纯形表的每一个基本可