第五章线性规划

1、1第五章 线性规划线性规划线性规划模型模型线性规划的线性规划的图解图解单纯形法单纯形法原理原理单纯形法单纯形法单纯形表单纯形表单纯形的理论分析单纯形的理论分析人工变量法人工变量法25.15.1线性规划的数学模型线性规划的数学模型一、问题的提出一、问题的提出例例1：生产计划问题：生产计划问题：问：甲乙各生产多少，使企业利润最大？问：甲乙各生产多少，使企业利润最大？ 设备产品ABC利润(元/公斤)甲35970乙95330限制工时5404507203解解:设产品甲、乙各生产设产品甲、乙各生产x1 ， x2公斤公斤12max7030Zxx121212123954055450.93720,0 xxxxs

2、txxxx设设总利润为总利润为Z，则：，则： 设备产品ABC利润(元/公斤)甲35970乙95330限制工时540450720资源约束资源约束变量非负变量非负约束约束4二、线性规划模型的一般特点二、线性规划模型的一般特点 Max(Min) z=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn(=或或)b1 a21x1+a22x2+a2nxn(=或或)b2 am1x1+am2x2+amnxn(=或或)bm xj(j=1,n) () 0，或者没有限制，或者没有限制 s.t. cj为价值系数为价值系数反映了客观限制条件。反映了客观限制条件。明确的目标要求，极大或极小明确的目标要求，极

3、大或极小行动方案行动方案线性规划模型的一般形式：线性规划模型的一般形式： 1 1、决策变量：、决策变量：向量向量( (x x1 1 x xn n) )T T2 2、目标函数：、目标函数：Z=Z=( (x x1 1 x xn n) )线性式，线性式，3 3、约束条件：、约束条件：线性等式或不等式线性等式或不等式变量约束变量约束约束方程约束方程5 资源资源产品产品煤（吨）煤（吨）金属材料金属材料（公斤）（公斤）电力电力（千瓦）（千瓦）产品利润产品利润（元（元/吨）吨）A680506000B850105000资源供应量资源供应量54040002000表表2：例例2：资源合理利用问题：资源合理利用问题

4、： 某厂生产某厂生产A、B两种产品，都需用煤、金属材料、电力等资两种产品，都需用煤、金属材料、电力等资源，各产品对三种资源的消耗及可供利用的资源如表源，各产品对三种资源的消耗及可供利用的资源如表2示：示：问：应如何安排生产，使企业获利最大？问：应如何安排生产，使企业获利最大？三、常用的线性规划模型三、常用的线性规划模型 6解：设产品解：设产品A、B产量分别为变量产量分别为变量x1 ， x2（吨），则：（吨），则： 0,200010504000508054086.56max2121212121xxxxxxxxtsxxZ 资源资源产品产品煤（吨）煤（吨）金属材料金属材料（公斤）（公斤）电力电力（千

5、瓦）（千瓦）产品利润产品利润（元（元/吨）吨）A680506000B850105000资源供应量资源供应量540400020007例例3、合理下料问题：、合理下料问题： 有一批长度为有一批长度为180厘米的钢管，需截成厘米的钢管，需截成70、52和和35厘米厘米3种管料。它们的需求量分别不少于种管料。它们的需求量分别不少于100、150和和100根。问如根。问如何下料才能使钢管的消耗量为最少？何下料才能使钢管的消耗量为最少？先找出各种可能的下料方式：（再在各种可能的下料方案中去先找出各种可能的下料方式：（再在各种可能的下料方案中去选择）选择） 设在设在180厘米长的钢管上能下出厘米长的钢管上能

6、下出u个个70厘米管料，厘米管料，v个个52厘米厘米管料，管料， w个个35厘米，则满足约束条件：厘米，则满足约束条件：70u+52v+35w180，其中，其中，u，v，w只能是正整数。只能是正整数。从最大尺寸管料下起：从最大尺寸管料下起：8I IIIIIIIIIIIIVIVV VVIVIVIIVIIVIIIVIII702111000052021032103510130235合计合计175174157175156174157175余料余料56235246235各种可能的下料方案：各种可能的下料方案：9 2x1 + x2 +x3+x4 100 2x2 +x3+ 3x5+2x6+x7 150 x1

7、 +x3+3x4+ x6+3x7+5x8100 xi 0 (i =1,8)，且为整数且为整数 minZ= 5x1 + 6x223x3+5x4+24x5+6x6+23x7+5x8解：设按第解：设按第j j种方案下料的原材料为种方案下料的原材料为x xj j根根 10例例4：运输问题：运输问题问：如何安排运输，使运输费用最小？问：如何安排运输，使运输费用最小？ 冶炼厂冶炼厂矿山矿山B1B2B3B4总产量总产量A11.520.33100A270.81.4280A31.20.322.550总需求量总需求量5070803023011解：设解：设x xij ij为第为第i i个矿山运到第个矿山运到第j j

8、个冶炼厂的矿石量个冶炼厂的矿石量 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 x11+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个冶炼厂的需求量个冶炼厂的需求量12方案方案序号序号技改方案内容技改方案内

9、容决策决策变量变量投资（万元）投资（万元）年收益年收益(万元万元)第一年第一年第二年第二年1更新旧装置，提高炼更新旧装置，提高炼油能力油能力500桶桶/天天x12001001002建造新装置，提高炼建造新装置，提高炼油能力油能力1000桶桶/天天x23001502003往新厂建输油管，提往新厂建输油管，提高炼油能力高炼油能力100桶桶/天天x315050504往老厂建输油管，提往老厂建输油管，提高炼油能力高炼油能力50桶桶/天天x410070305增加槽车运输能力，增加槽车运输能力，能提高出油能提高出油20桶桶/天天x5504020例例5：投资方案选择问题（：投资方案选择问题（01规划规划）1

10、3 又要求：又要求：方案方案1 1和和2 2只能选择其中一种，不能兼而实现，并且，只能选择其中一种，不能兼而实现，并且，选择方案选择方案2 2，则方案，则方案3 3必须与必须与2 2同时选择，或者都不选择。同时选择，或者都不选择。现该公司可供支配的资金总额为：第一年有现该公司可供支配的资金总额为：第一年有650650万元，第二年万元，第二年仅有仅有460460万元。要求技改后，至少增加出油能力万元。要求技改后，至少增加出油能力500500桶桶/ /天，天，但又不得超过但又不得超过11001100桶桶/ /天，确定该公司总经济效益最大的投资天，确定该公司总经济效益最大的投资方案。方案。解：解：1

11、 1）确定决策变量）确定决策变量：方案的选择只有方案的选择只有两种状态两种状态，选或不，选或不选，设选，设xj（j=1,5）为第）为第j方案的取舍，有：方案的取舍，有：2）目标函数：）目标函数：max Z=100 x1+200 x2+50 x3+30 x4+20 x5选不选 1 0jx14200 x1+300 x2+150 x3+100 x4+50 x5650（万元）（万元）200 x1+150 x2+50 x3+70 x4+40 x5460 500 x1+1000 x2+100 x3+50 x4+20 x5500500 x1+1000 x2+100 x3+50 x4+20 x51100 x1

12、+x21-x2+x3=0 xj=1或或0 (j=1,5)3) 约束条件：约束条件：（投资总额约束（第一、二年），生产能（投资总额约束（第一、二年），生产能力增加约束，方案制约约束，变量的取舍限制。力增加约束，方案制约约束，变量的取舍限制。15例例6：人员分派问题数模（：人员分派问题数模（01规划规划） 每项工作只能由一个人承担，每人做每项工作的工作效每项工作只能由一个人承担，每人做每项工作的工作效率如上表所示，率如上表所示，现在怎样安排工作使总的效率最大。现在怎样安排工作使总的效率最大。 工作工作人员人员ABCD甲0.60.20.30.1乙0.70.40.30.2丙0.81.00.70.3丁0

13、.70.70.50.416解：设解：设xij为第为第i个人做第个人做第j项工作，（项工作，（xij=1或或0）Max Z0.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+x24=1x31+x32+x33+x34=1x41+x42+x43+x44=1 x11+x21+x31+x41=1 x12+x22+x32+x42=1 x13+x23+x33+x43=1 x14+x24

14、+x34+x44=1 xij=1或或0(i=1,.,4。j=1,4）每一项工作都有每一项工作都有人做人做每个人只做一项每个人只做一项工作工作17v线性规划建立模型步骤：线性规划建立模型步骤： 确定一组决策变量确定一组决策变量 确定目标函数确定目标函数 确定对决策变量的约束条件确定对决策变量的约束条件线性规划建模小结线性规划建模小结 v线性规划的共同点：线性规划的共同点： 要解决的问题的目标可以用数值指标反映要解决的问题的目标可以用数值指标反映 对于要实现的目标有多种方案可选择对于要实现的目标有多种方案可选择 有影响决策的若干约束条件有影响决策的若干约束条件18作业：作业：现有一家公司准备制定一

15、个广告宣传计划来宣传开发的新产品，以现有一家公司准备制定一个广告宣传计划来宣传开发的新产品，以使尽可能多的未来顾客特别是女顾客得知。现可利用的广告渠道有电视、广使尽可能多的未来顾客特别是女顾客得知。现可利用的广告渠道有电视、广播和报纸，根据市场调查整理得到下面的数据：播和报纸，根据市场调查整理得到下面的数据：项目项目电电 视视广广播播报报纸纸一般一般时间时间黄金时黄金时间间每个广告单元的费用每个广告单元的费用(元元)每个广告单元所接触的顾客数每个广告单元所接触的顾客数(万人万人)每个广告单元所接触的女顾客数每个广告单元所接触的女顾客数(万人万人)400040307000904030005020

16、15002010 该企业计划用于此项广告宣传的经费预算是该企业计划用于此项广告宣传的经费预算是8080万元，此外要求：万元，此外要求：1.1.至少有至少有200200万人次妇女接触广告宣传；万人次妇女接触广告宣传；2.2.电视广告费用不得超过电视广告费用不得超过5050万元万元, ,3.3.电视广告至少占用三个单元一般时间和两个单元黄金时间电视广告至少占用三个单元一般时间和两个单元黄金时间, ,4.4.广播和报纸广告单元均不少于广播和报纸广告单元均不少于5 5个单元而不超过个单元而不超过1010个单元。个单元。 试为该企业制定广告计划，使得广告所接触的未来顾客总数尽可能多试为该企业制定广告计划

17、，使得广告所接触的未来顾客总数尽可能多，建立线性规划数学模型。，建立线性规划数学模型。195.2线性规划的图解法一、图解法求最优解的步骤一、图解法求最优解的步骤 思路：思路：在在直角坐标系直角坐标系中，描绘出中，描绘出约束条件约束条件和和变量变量限制的公限制的公共区域，然后通过观察确定符合目标要求的变量的取值。共区域，然后通过观察确定符合目标要求的变量的取值。 求解例求解例1中的生产计划问题中的生产计划问题： 对于简单的线性规划问题对于简单的线性规划问题(只有两个决策变量只有两个决策变量的线性规划的线性规划问题问题),我们通过图解法可以对它进行求解。我们通过图解法可以对它进行求解。201212

18、121212max70303954055450.93720,0ZxxxxxxstxxxxOx1x280603070901 1、绘出约束方程的图形、绘出约束方程的图形2 2、确定可行解域、确定可行解域3 3、绘出目标函数图形、绘出目标函数图形4 4、确定最优解及目标函数、确定最优解及目标函数值值可行解域可行解域目标函数变形得：目标函数变形得：217330zxx 目标函数等值线目标函数等值线最优解最优解Q2(75,15)Q1Q3Q4Q5Q6Q7Q821几个概念：几个概念：v可行解：可行解：满足线性规划所有约束条件（满足线性规划所有约束条件（含约束方程与变量含约束方程与变量约束）约束）的点。的点。v

19、可行解域：可行解域：所在可行解的集合。所在可行解的集合。v最优解：最优解：使目标函数得到极值的可行解。最优解包括：唯使目标函数得到极值的可行解。最优解包括：唯一最优解和无穷多最优解。一最优解和无穷多最优解。v等值线：等值线：具有相同目标函数值的直线。具有相同目标函数值的直线。v法向量法向量(梯度梯度):由目标函数由目标函数系数系数组成的与组成的与等值线等值线垂直的向垂直的向量。量。22二、二维线性规划问题解的形式二、二维线性规划问题解的形式 1、唯一最优解、唯一最优解2、无穷多个最优解、无穷多个最优解66843x2可行解域目标函数的等值线目标函数的等值线C(1,2)Q2(4,2)Q3(2,3)

20、x1Max Z=x1+2x2 x1+x26 x1+2x28 x23 xi0(i=1,2)233、有可行解但无最优解、有可行解但无最优解max Z=x1+x2 -2x1+x24 x1-x22 x1,x20 x2x1-24-22可行解域可行解域(1,1)244、无可行解、无可行解MinZx1+2x2 s.t. x1+x21 2x1+x24 x1,x20 x2x11142(1,2)可行域为空可行域为空集，无可行集，无可行解解!25 线性规划的可行解域为线性规划的可行解域为凸多边形（凸多边形（凸集）凸集）。可行解域可行解域凸多边形有若干个顶点，凸多边形有若干个顶点，顶点的个数是顶点的个数是有限的。有限

21、的。三、线性规划的几何意义三、线性规划的几何意义 线性规划问题若存在最优解线性规划问题若存在最优解，则最优解必可在其可行域则最优解必可在其可行域的某一顶点上得到。的某一顶点上得到。 Ox1x2Q2(75,15)60最优解最优解Q1Q3Q4Q5Q6Q7Q826四、单纯形法原理四、单纯形法原理Ox1x2Q2(75,15)60最优解最优解Q1Q3Q4Q5Q6Q7Q8找可行解域顶点的计算方法，但不找可行解域顶点的计算方法，但不是计算所有的顶点，而是从凸集的一是计算所有的顶点，而是从凸集的一个个顶点顶点出发，沿着凸集的边缘逐个验出发，沿着凸集的边缘逐个验算所遇到的顶点，直到找到目标函数算所遇到的顶点，直

22、到找到目标函数为为最优的顶点最优的顶点为止。如从为止。如从O Q1 Q2或从或从O Q4 Q3 Q2 。271.31.3单纯形法原理单纯形法原理5.35.3线性规划标准型和规范型线性规划标准型和规范型一、线性规划的一、线性规划的标准型标准型 约束方程均为约束方程均为等式等式方程。方程。右边常数右边常数bi为为正数正数。所有变量均为所有变量均为非负变量非负变量。目标函数求目标函数求max1、一般形式：、一般形式：1 12211 11221121 1222221 12212max,0nnnnnnmmmnnmnZc xc xc xa xa xa xba xa xa xba xaxaxbx xx28n

23、jxmibxaxcZjnjijijnjjj, 1 , 0, 1 ,max11或写成或写成累加和累加和形式：形式：1 12211 11221121 1222221 12212max,0nnnnnnmmmnnmnZc xc xc xa xa xa xba xa xa xba xaxaxbx xx标准型的一般形式标准型的一般形式29max0ZCXAXbX或写成或写成矩阵矩阵形式：形式：1 12211 11221121 1222221 12212max,0nnnnnnmmmnnmnZc xc xc xa xa xa xba xa xa xba xaxaxbx xx111212122212,nnmmmn

24、aaaaaaAaaa12,nxxXx12,nbbbb12( ,)nCc cc12jjjmjaaPa其中：其中：12 ,nAP PP则302、化线性规划问题为标准型、化线性规划问题为标准型约束方程为约束方程为“号，号，在方程式的左端在方程式的左端“”一个变量（变量一个变量（变量00，称为，称为松驰变松驰变量量），原不等式化为等式约束。），原不等式化为等式约束。约束方程为约束方程为“”号号在方程式的左端在方程式的左端“”一个变量（变量一个变量（变量00，称为，称为剩余变剩余变量量），原不等式化为等式约束。），原不等式化为等式约束。 (1) (1) 约束条件为等式约束条件为等式31（2 2）变量非负

25、约束）变量非负约束若若x xk k为无约束变量（即可为无约束变量（即可00，也可，也可00），引进两个变量），引进两个变量x xk k,x,xk k”（均（均00），令），令xk=xkxk”。在规划模型中去掉。在规划模型中去掉x xk k这个变量。这个变量。（3 3）约束方程右边常数）约束方程右边常数非负非负约束约束在方程两边同时乘以（在方程两边同时乘以（-1-1）使得约束方程右边常数变为非负）使得约束方程右边常数变为非负 3234531212121245max703000039 540 55 450.93 7200(1,5)jZxxxxxxxxstxxxxxxxj 标准型为：标准型为：121

26、2121212max70303954055450.93720,0Zxxxxxxstxxxx例例1：把下面的线性规划模型化为标准型：把下面的线性规划模型化为标准型：33123123123123123min2372325,0,Zxxxxxxxxxxxxx xx 无约束124512456124571245124567max23()() 7() 232() 5,0Dxxxxxxxxxxxxxxxxxxx x x x x x得到该问题的标准型为：得到该问题的标准型为：(1)(1)用用x x4 4x x5 5替换替换x x3 3，其中，其中x x4 4，x x5 500(2)(2)在第一个约束不等式在第一

27、个约束不等式号左端号左端加上加上松驰变量松驰变量x x6 6(3)(3)在第二个约束不等式左边在第二个约束不等式左边减去减去松驰松驰变量变量x x7 7(4)(4)令令D DZ Z, ,把求把求min Z化成化成max D例例2：把下面的线性：把下面的线性规划模型化为标准规划模型化为标准型：型：34二、线性规划的二、线性规划的规范规范型型要用单纯形法求解线性规划数学模型，还需要把数学模要用单纯形法求解线性规划数学模型，还需要把数学模型化成规范型。型化成规范型。1 1基、基变量与非基变量基、基变量与非基变量11max, 1,0, 1,njjjnijjijjZc xa xbimxjn 基：基：设设

28、A是约束方程组的是约束方程组的mn维系数矩阵，维系数矩阵，B是矩阵是矩阵A中中m阶方阶方阵阵（行列式的值不为行列式的值不为0 0），则称），则称B是线性规划问题的一个基。是线性规划问题的一个基。基变量与非基变量：基变量与非基变量：与基与基B对应的变量为基变量。其余变量为对应的变量为基变量。其余变量为非基变量。非基变量。 12123124125max703039 540 55 450.93 7200(1,5)jZxxxxxxxxstxxxxj设线性规设线性规划模型的划模型的标准型：标准型：3512123124125max703039 540 55 450.93 7200(1,5)jZxxxxxx

29、xxstxxxxj请列举出其中的请列举出其中的三三个基个基及对应的及对应的基变量基变量与与非基变量。非基变量。例例1：解：从约束系数矩阵可看出，该模型的基不超过解：从约束系数矩阵可看出，该模型的基不超过3510C 个。个。对应的基变量为对应的基变量为x3,x4,x5,非基变量为非基变量为x1,x2。110 BB为基.391005501093001A1345100,010001BP P P取36对应的对应的基变量基变量为为x1,x3,x4，非非基变量为基变量为x2,x5。220 BB为基.391005501093001A2134310,501900BP P P取330 BB为基.对应的对应的基变

30、量基变量为为x1,x2,x3，非非基变量为基变量为x4,x5。3123391,550930BP P P取372 2基本解和基本可行解基本解和基本可行解基本解：基本解：对某一确定的基，令对某一确定的基，令非基变量等于非基变量等于0，可求出，可求出m个约个约束方程的基变量的值，则这组解称为束方程的基变量的值，则这组解称为基本解基本解。基本可行解：基本可行解：若基本解还满足若基本解还满足决策变量非负决策变量非负要求，则这组基要求，则这组基本解称为本解称为基本可行解基本可行解（也称（也称基可行解基可行解）。）。11max, 1,0, 1,njjjnijjijjZc xa xbimxjn 1212312

31、4125max703039 540 55 450.93 7200(1,5)jZxxxxxxxxstxxxxj38对基对基B1来说，令非基变量来说，令非基变量120,0 xx，则可以得到一个基本解则可以得到一个基本解 12123124125max703039 540 55 450.93 7200(1,5)jZxxxxxxxxstxxxxj1100010001B(1)12345(,)(0,0,540,450,720)TTXx xx xx(1)0X(1)X因为因为，故，故是基可行解。是基可行解。 对基对基B2来说，令非基变量来说，令非基变量，则可以得到一个基本解，则可以得到一个基本解 (2)0X(2

32、)X因为因为，故，故也是基可行解。也是基可行解。 250,0 xx(2)12345(,)(80,0,300,50,0)TTXx xx xx2134310,501900BP P P取39对基对基B3来说，令非基变量来说，令非基变量，则可以得到一个基本解，则可以得到一个基本解 12123124125max703039 540 55 450.93 7200(1,5)jZxxxxxxxxstxxxxj(3)0X(3)X因为因为，故，故不是基可行解。不是基可行解。 350,0 xx(3)12345(,)(67.5,37.5,0, 75,0)TTXx xx xx3124390,551930BP P P取对

33、基对基B4来说，令非基变量来说，令非基变量, 则可得基本解则可得基本解 (4)0X(4)X因为因为，故，故也不是基可行解。也不是基可行解。 150,0 xx(4)12345( ,)(0,240, 1620, 750,0)TTXx xx xx4234310,501900BP P P403 3基可行解基可行解与可行解与可行解域域顶点顶点的关系的关系Ox1x2Q2(75,15)60最优解最优解Q1Q3Q4Q5Q6Q7Q8(2)(80,0,300,50,0)TX(1)(0,0,540,450,720)TX12123124125max703039 540 55 450.93 7200(1,5)jZxxx

34、xxxxxstxxxxjX(1)对应原点对应原点O, X(2)对应顶点对应顶点Q1, X(3) 对应对应Q7.(3)(67.5,37.5,0, 75,0)TX(4)(0,240, 1620, 750,0)TXX(4) 对应对应?41Ox1x2806090最优解最优解Q2(75,15)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)TQ5

35、x4,x5x1,x2, x3(75,15,180,0,0)TQ21213212121245max703039 54055 450.93 =x720,0Zxxxxxxstxxxxxx42定理定理1 1：线性规划的：线性规划的基本可行解基本可行解对应于可行解域的对应于可行解域的顶顶 点点。从定理从定理1和单纯形的几何意义知，用单纯形法寻求最优解，和单纯形的几何意义知，用单纯形法寻求最优解，就可就可从从基本可行解基本可行解（顶点顶点）出发，在）出发，在基本可行解（顶点）之基本可行解（顶点）之间变换间变换，如果，如果L.P.有最优解，则有最优解，则最优解最优解一定可在一定可在某一基本可行某一基本可行解

36、（顶点）上得到解（顶点）上得到。这个方法可用来求有任意多个变量的线。这个方法可用来求有任意多个变量的线性规划模型！性规划模型！Ox1x2Q2(75,15)60最优解最优解Q1Q3Q4Q5Q6Q7Q843已是标准型；已是标准型；1213212121245max703039 54055 450.93 720,0Zxxxxxxstxxxxxxx0345100,010001Bppp取基得初始基本可行解：得初始基本可行解：X X(1(1）=(0,0,540,450,720) =(0,0,540,450,720) T T,Z=0,Z=0。4 4、线性规划的、线性规划的规范规范型型例例1：特点特点（1）基变

37、量的值基变量的值刚好是约束方程刚好是约束方程右边的常数右边的常数；（2）目标函数）目标函数Z的值的值就是目标函数表达式中的就是目标函数表达式中的常数常数。 含单位基；含单位基；目标函数用非基变量表示。目标函数用非基变量表示。规范规范型型条件：条件：4425235245 12520705600391 8 3003105 5039118039Zxxxxxxxxxxx 1213212121245max703039 54055 450.93 720,0Zxxxxxxstxxxxxxx若取基变量若取基变量x x3 3,x,x4 4,x,x1 1, ,则基解及则基解及目标函数值？目标函数值？可把模型化成以

38、基变量系数矩阵为单位阵的可把模型化成以基变量系数矩阵为单位阵的规范型规范型： (2)(80,0,300,50,0)TX(2)5600Z得到基本可行解：得到基本可行解：， 45引例引例1：求解下列线性规划模型的最优解：求解下列线性规划模型的最优解解：解：1、确定初始基可行解、确定初始基可行解取取B1（P3P4P5）I，令非基变量令非基变量x1,x2=0，得，得X(1)（0,0,540,450,720）T，Z(1)0；（；（解的含义？）解的含义？） 从规范型出发从规范型出发5.45.4单纯形法步骤单纯形法步骤1213212121245max703039 54055 450.93 720,0Zxxx

39、xxxstxxxxxxx462、判定解是否最优、判定解是否最优目标函数目标函数Max Z0+70 x1+30 x2检验数检验数：用非基变量表达的目标函数中变量前的系数：用非基变量表达的目标函数中变量前的系数Rj（判（判别数或检验数）。别数或检验数）。 当当x1从从0 或或x2从从0 ， Z从从0 ， X(1) 不是最优解不是最优解3、由一个基可行解、由一个基可行解另一个基可行解。另一个基可行解。 (1) 确定入基变量确定入基变量可选可选Rj0的任一变量入基。（的任一变量入基。（意义意义？）？）一般地，选择一般地，选择maxRj的变量入基，选的变量入基，选x1从从0 ，保持，保持x2 =0 (2

40、)确定出基变量确定出基变量47问题：问题：确定确定入基变量入基变量x x1 1增加的增加的上上界界：从约束方程组怎样求解？：从约束方程组怎样求解？在在中，继续令中，继续令x x2 2为非基变量，即为非基变量，即x x2 2 0 0，求出当前每个，求出当前每个基变量出基基变量出基能使能使x x1 1增大的上界值增大的上界值。即：。即：x3=5403x10 x1180=540/3x4=4505x10 x190=450/5x5=720 9x1 0 x180=720/91213212121245max703039 54055 450.93 =x720,0Zxxxxxxstxxxxxx48min180

41、,90,80= min540/3 ,450/5,720/9= 80, x5出基出基(变为变为0)，即即x x1 1的取值受第三种资源的约束。的取值受第三种资源的约束。规则：规则：入基变量满足约束条件下取最大值。（大中取小）入基变量满足约束条件下取最大值。（大中取小） x3=5403x10 x1180 x4=4505x10 x190 x5=720 9x1 0 x180新的基变量为新的基变量为x x3 3,x,x4 4,x,x1 1，怎样求出新的基可行解？，怎样求出新的基可行解？把模型变成以把模型变成以基变量的系数矩阵基变量的系数矩阵为为单位阵单位阵的规范型。的规范型。 (3)求出新的基可行解求出

42、新的基可行解49 以基变量以基变量x x3 3,x,x4 4,x,x5 5的系数矩阵的系数矩阵为单位阵的规范型为单位阵的规范型: : 12123124125max703039 540 55 450.93 7200(1,5)jZxxxxxxxxstxxxxj （1 1）从）从出基变量出基变量x x5 5所在的方程所在的方程开始：方程两边同时除以开始：方程两边同时除以入基入基变量变量x x1 1的的系数系数9 9，得：，得： 125(1/3) (1/9)80 xxx（2 2）方程）方程中消去中消去x x1 1（入基变量入基变量）：方程）：方程两边同时两边同时乘以某个数，加到方程乘以某个数，加到方程

43、上。上。（3 3）目标函数中消去）目标函数中消去x x1 1：从方程：从方程中解出中解出x x1 1的值代入的值代入目标函数中：目标函数中：新的基变量为新的基变量为x x3 3,x,x4 4,x,x1 1本质：就是线性代数中的高斯消去本质：就是线性代数中的高斯消去法法方程组同解变形方程组同解变形. .50通过以上方程的变换，原线性规划模型等价于以下模型通过以上方程的变换，原线性规划模型等价于以下模型（得到得到当前基表示的规范型当前基表示的规范型）：X(2)（80,0,300,50,0）T，Z(2)5600； 对应图形上的对应图形上的Q Q1 1点。点。252525 23415207056003

44、91 8 3003105 5039118039Zxxxxxxxxxxx 1、确定出新的基可行解、确定出新的基可行解512、判定解是否最优、判定解是否最优3、由一个基可行解、由一个基可行解另一个基可行解另一个基可行解。(1) 确定入基变量确定入基变量选择选择x2入基，即入基，即x2从从0 ，x5 仍为仍为0从约束方程组求解从约束方程组求解x x2 2的最大取值，从而确定的最大取值，从而确定出基变量出基变量。同理：在同理：在中令中令x5=0，求出求出当前解下当前解下x2取值的上界。取值的上界。当当x2从从0 ，Z从从5600 ， X(2) 不是最优解不是最优解.目标函数：目标函数：( 1)2520

45、70560039QZxx，R2=20/3, R5=-70/9235245 1251 8 3003105 5039118039xxxxxxxxx52=min 37.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 21515x x1 1=80=80 x x2 2/3 /3 x x2 2240240252525 2341520705600391 8 3003105 5039118039Zxxxxxxxxxxx 把模型变成以把模型变

46、成以基变量基变量x x3 3,x,x2 2,x,x1 1的系数矩阵的系数矩阵为为单位阵单位阵的规范型。的规范型。 新的基变量新的基变量x x3 3,x,x2 2,x,x112520705600391 8 3003105 5039118039Zxxxxxxxxxxx 怎样把模型变成以怎样把模型变成以基变量基变量x x3 3,x,x2 2,x,x1 1的系数矩阵的系数矩阵为为单位阵单位阵的的规范型？规范型？ (1)(1)从出基变量从出基变量x x4 4所在的方程所在的方程开始：使入基变量开始：使入基变量x x2 2的系数变成的系数变成1 1。(2)(2)用消元法消去方程用

47、消元法消去方程中的中的x x2 2。54X(3)（75,15,180,0,0）T，Z(3)5700；由方程组由方程组变形变形得：得：(3)454545431522057002312 180531 1510611 75 1 06Zxxxxxxxxxxx552、判定解是否最优、判定解是否最优 目标函数目标函数X(3)（75，15，180，0，0）T，Z(3)5700；非基变量的非基变量的检验系数均为负数检验系数均为负数，故不能入基，否则使目标，故不能入基，否则使目标值劣化。值劣化。当前解为当前解为最优解最优解。(3)4520570023Zxx最优解判断标准：最优解判断标准：（1 1） 若若全部检验

48、数全部检验数R Rj j 0 0，当前基本可行解为最优解。，当前基本可行解为最优解。（2 2） 若存在若存在R Rj j 0 0，则当前解非最优，解可改进，寻求，则当前解非最优，解可改进，寻求 更好的解。更好的解。561、 确定初始基可行解。确定初始基可行解。 本题确定初始基为单位阵本题确定初始基为单位阵I，令单位阵对应的变量为基变量，令单位阵对应的变量为基变量，可得到一个基本可行解。可得到一个基本可行解。小结：小结：单纯形法求解线性规划的过程单纯形法求解线性规划的过程 规范型：规范型： AXb X0，b0 A中含有一单位阵。中含有一单位阵。2、最优化检验、最优化检验：用当前可行基的非基变量的

49、用当前可行基的非基变量的检验数检验数确定。确定。 3、 从一个基本可行解到另一个基本可行解从一个基本可行解到另一个基本可行解 入基变量：由检验数确定。入基变量：由检验数确定。 出基变量：由出基变量：由规则确定。规则确定。 5712123124125max703039 540 55 450.93 7200(1,5)jZxxxxxxxxstxxxxj 25235245 12520705600391 8 3003105 5039118039Zxxxxxxxxxxx (3)453452451452057002312 180531 1510611 75 106Zxxxxxxxxxxx用单纯形法从另一条路

50、径寻优？用单纯形法从另一条路径寻优？58cj c1 c2 cnCBXB x1 x2 xnxi1xi2ximZ R1 R2 RnZ01 11 212 12 2212nnmmm naaaaaaaaa 12mbbb b5.55.5单纯形表单纯形表目标函数行：常数目标函数行：常数Z0在右边。在右边。591、由规范型列出初始单纯形表：、由规范型列出初始单纯形表：X(1)（0,0,540,450,720）TZ(1)01213212121245max703039 54055 450.93 720,0Zxxxxxxstxxxxxxxb主元主元(0)1207030Zxx(0)1270300Zxx cj70300

51、00CBXBx1x2x3x4x50 x3391005401800 x455010450900 x59300172080-Z70300000602、变换到下一单纯表（、变换到下一单纯表（变成以新基为单位阵的规范型变成以新基为单位阵的规范型）思考：思考：单纯形表有什么特点？单纯形表有什么特点？（1 1）基变量基变量对应的约束方程中对应的约束方程中系数矩阵系数矩阵为单位矩阵。为单位矩阵。（2 2）目标函数）目标函数基变量的检验数为基变量的检验数为0 0。（3 3）基可行解基可行解( (？) )不同，反映在原表中就是对应的基不同。不同，反映在原表中就是对应的基不同。 b新的基变量：新的基变量：x3 ,

52、x4,x1 cj7030000CBXBx1x2x3x4x50 x30810-1/3300 37.50 x4010/301-5/9501570 x111/3001/980240-Z020/300-70/9-5600主元主元61表一表一表二表二00003070-Z8072010039x509045001055x4018054000193x30 x5x4x3x2x1XBCB0003070Cjb9-5600-70/90020/30-Z240801/9001/31x11550-5/91010/30 x4037.5300-1/30180 x307025235245 1252070max z=5600+x3

53、91 8 3003105 5039118039xxxxxxxxxx?1213212121245max703039 54055 450.93 =720,0Zxxxxxxstxxxxxxx623、重复以上过程直到得最优解：、重复以上过程直到得最优解：思考：思考：在单纯形表中，怎样判断在单纯形表中，怎样判断LP问题已取得问题已取得最优解最优解？最优解判断标准：最优解判断标准：（1 1） 若若全部检验数全部检验数R Rj j 0 0，当前基本可行解为最优解。，当前基本可行解为最优解。（2 2） 若存在若存在R Rj j 0 0，则当前解非最优，解可改进，寻求，则当前解非最优，解可改进，寻求更好的解。更

54、好的解。63cj7030000CBXBx1x2x3x4x5b 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*=(75,15,180, 0,0)T, Z=570064例例1：求解下列线性规划模型：求解下列线性规划模型：123123123max45348

55、0002430000,1,2,3jzxxxxxxxxxxj解：解：化线性规划模型为化线性规划模型为规范型规范型，并列出初始单纯形表：，并列出初始单纯形表：按单纯法迭代，计算如下表，得最优解为按单纯法迭代，计算如下表，得最优解为:X=(1500,0,0,3500,0)T, Z=600065-6000-20-3-10-Z15001/2021/21x13500-3/21-2-1/20 x4-3750-5/400-1/43/2-Z15007501/4011/4x350005000-11001x4000514-Z750300010412x52000800001413x4bx5x4x3x2x1XBCB00

56、514Cj41/266例例2： 用单纯形法求解下列线性规划数学模型用单纯形法求解下列线性规划数学模型123523451242456min326225(2)238 (3)0jzxxxxxxxxxxxxxxxx(1)选选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代入目标函数得：代入目标函数得：

57、Min Z = 11 - 4xMin Z = 11 - 4x2 2 + 3x+ 3x4 4 - 5x - 5x5 5 24523451242456max1143526225(2)238 (3)0jDxxxxxxxxxxxxxxx (1)把把LP化成求极大的规范型：化成求极大的规范型：67XBx1x2x3x4x5x6bx1120-2005x3011-12063x602013188/3-D040-3501124523451242456max1143526225(2)238 (3)0jDxxxxxxxxxxxxxxx (1)68X(3) = (0，5/2，3/2，0，1，0)TD(3) = 4，Z4

58、-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-2021x1bx6x5x4x3x2x1XB69假设目标函数求极大假设目标函数求极大MAX1 1、从、从规范型规范型出发，得出一个初始基可行解。按要求填入表中。出发，得出一个初始基可行解。按要求填入表中。2 2、最优化检验：若还存在、最优化检验：若还

59、存在R Rj j00，则当前解不是最优解。，则当前解不是最优解。3 3、解的改进：、解的改进：由由检验数检验数确定入基变量确定入基变量x xp p。( (一般正系数大的变量先入基一般正系数大的变量先入基) )确定出基变量确定出基变量: :,0iiipipbaa计算min|0ilipiplpbbaaa取确定确定L L为出基行，则为出基行，则x xL L为换出变量。得到一个新的可行基。为换出变量。得到一个新的可行基。单纯形算法步骤单纯形算法步骤4 4、用、用初等行变换方法初等行变换方法把把主元（主元（a aLpLp）变为变为1 1，把，把入基列入基列（含（含其检验数）中除主元的其它元素消为零。转其

60、检验数）中除主元的其它元素消为零。转2.2.70讨论：单纯形表进行求解的特殊情况 （1）若）若最大检验数有两个或两个以上并且相等最大检验数有两个或两个以上并且相等，应如何确定，应如何确定入基变量，理论上可任选一个非基变量入基，但在实际应用入基变量，理论上可任选一个非基变量入基，但在实际应用中，可采用以下法则：中，可采用以下法则： XBx1x2x3x4x5b12x33910054018060 x4550104509090 x59300172080240-Z70700000依次选择依次选择X X1 1和和X X2 2入基，分别计算出两组比值入基，分别计算出两组比值 1 1和和 2 2，每组，每组比