第五部分线规划教学ppt课件

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

2、xx设总利润为设总利润为Z，那么：，那么： 设备产品ABC利润(元/公斤)甲35970乙95330限制工时540450720资源约束资源约束变量非负约束变量非负约束二、线性规划模型的普通特点二、线性规划模型的普通特点 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、决策变量：向量、决策变量：向量(x1 xn)T(x1 xn)T2 2、目的函数：、目的函数：Z=Z=(x1 xn)(x1 xn)线性式，线性式，3 3、约束条件：线性等式或不等式、约束条件：线性等式或不等式变量约束变量约束约束方程约束方程 资源资源产品产品煤（吨）煤（吨）金属材料金属材料（公斤）（公斤）电力电力（千瓦）（千瓦）产品利润产品利润（元（元/吨）吨）A680506000B850105000资源供应量资源供应量54040002000表表2：例例2：资源合理利用问题：资源合理利用问题： 某厂消费某厂消费A、B两

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

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

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

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

8、+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个冶炼厂的需求量个冶炼厂的需求量方案方案序号序号技改方案内容技改方案内容决策决策变量变量投资（万元）投资（万元）年收益年收益(万元

9、万元)第一年第一年第二年第二年1更新旧装置，提高炼更新旧装置，提高炼油能力油能力500桶桶/天天x12001001002建造新装置，提高炼建造新装置，提高炼油能力油能力1000桶桶/天天x23001502003往新厂建输油管，提往新厂建输油管，提高炼油能力高炼油能力100桶桶/天天x315050504往老厂建输油管，提往老厂建输油管，提高炼油能力高炼油能力50桶桶/天天x410070305增加槽车运输能力，增加槽车运输能力，能提高出油能提高出油20桶桶/天天x5504020例例5：投资方案选择问题：投资方案选择问题01规划规划 又要求：方案又要求：方案1和和2只能选择其中一种，不能兼而实现，并

10、且，选择方案只能选择其中一种，不能兼而实现，并且，选择方案2，那么方案，那么方案3必需与必需与2同时选择，或者都不选择。同时选择，或者都不选择。现该公司可供支配的资金总额为：第一年有现该公司可供支配的资金总额为：第一年有650万元，第二年仅有万元，第二年仅有460万元。万元。要求技改后，至少添加出油才干要求技改后，至少添加出油才干500桶桶/天，但又不得超越天，但又不得超越1100桶桶/天，确定天，确定该公司总经济效益最大的投资方案。该公司总经济效益最大的投资方案。解：解：1 1确定决策变量：方案的选择只需两种形状，选或不确定决策变量：方案的选择只需两种形状，选或不选，设选，设xjxjj=1,

11、5j=1,5为第为第j j方案的取舍，有：方案的取舍，有：2目的函数：目的函数：max Z=100 x1+200 x2+50 x3+30 x4+20 x5选不选 1 0jx200 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+x21-x2+x3=0 xj=1或或0 (j=1,5)3) 约束条件：投资总额约束第一、二年，消费才约束条件：投资总额约束第

12、一、二年，消费才干添加约束，方案制约约束，变量的取舍限制。干添加约束，方案制约约束，变量的取舍限制。例例6：人员分派问题数模：人员分派问题数模01规划规划 每项任务只能由一个人承当，每人做每项任务的任务效每项任务只能由一个人承当，每人做每项任务的任务效率如上表所示，如今怎样安排任务使总的效率最大。率如上表所示，如今怎样安排任务使总的效率最大。 工作工作人员人员ABCD甲0.60.20.30.1乙0.70.40.30.2丙0.81.00.70.3丁0.70.70.50.4解：设解：设xij为第为第i个人做第个人做第j项任务，项任务，xij=1或或0Max Z0.6x11+0.2x12+0.3x1

13、3+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+x34+x44=1 xij=1或或0(i=1,.,4。j=1,4每一项任务都有每一项任务都有人做人做每个人只做一项每个人只做一项任务任务v线性规划建立模型步

14、骤：线性规划建立模型步骤：v 确定一组决策变量确定一组决策变量v 确定目的函数确定目的函数v 确定对决策变量的约束条件确定对决策变量的约束条件线性规划建模小结线性规划建模小结 v线性规划的共同点：线性规划的共同点：v 要处理的问题的目的可以用数值目的反映要处理的问题的目的可以用数值目的反映v 对于要实现的目的有多种方案可选择对于要实现的目的有多种方案可选择v 有影响决策的假设干约束条件有影响决策的假设干约束条件作业：现有一家公司预备制定一个广告宣传方案来宣传开发的作业：现有一家公司预备制定一个广告宣传方案来宣传开发的新产品，以使尽能够多的未来顾客特别是女顾客得知。现可利新产品，以使尽能够多的未

15、来顾客特别是女顾客得知。现可利用的广告渠道有电视、广播和报纸，根据市场调查整理得到下用的广告渠道有电视、广播和报纸，根据市场调查整理得到下面的数据：面的数据：项目项目电电 视视广广播播报报纸纸一般一般时间时间黄金时黄金时间间每个广告单元的费用每个广告单元的费用(元元)每个广告单元所接触的顾客数每个广告单元所接触的顾客数(万人万人)每个广告单元所接触的女顾客数每个广告单元所接触的女顾客数(万人万人)40004030700090403000502015002010 该企业方案用于此项广告宣传的经费预算是该企业方案用于此项广告宣传的经费预算是8080万元，此外要求：万元，此外要求：至少有至少有200

16、200万人次妇女接触广告宣传；万人次妇女接触广告宣传；电视广告费用不得超越电视广告费用不得超越5050万元万元, ,电视广告至少占用三个单元普通时间和两个单元黄金时间电视广告至少占用三个单元普通时间和两个单元黄金时间, ,广播和报纸广告单元均不少于广播和报纸广告单元均不少于5 5个单元而不超越个单元而不超越1010个单元。个单元。 试为该企业制定广告方案，使得广告所接触的未来顾客总数尽能够多，试为该企业制定广告方案，使得广告所接触的未来顾客总数尽能够多，建立线性规划数学模型。建立线性规划数学模型。5.2线性规划的图解法一、图解法求最优解的步骤一、图解法求最优解的步骤 思绪：在直角坐标系中，描画

17、出约束条件和变量限制的公思绪：在直角坐标系中，描画出约束条件和变量限制的公共区域，然后经过察看确定符合目的要求的变量的取值。共区域，然后经过察看确定符合目的要求的变量的取值。 求解例求解例1中的消费方案问题：中的消费方案问题： 对于简单的线性规划问题对于简单的线性规划问题(只需两个决策变量的线性规划只需两个决策变量的线性规划问题问题),我们经过图解法可以对它进展求解。我们经过图解法可以对它进展求解。1212121212max70303954055450.93720,0ZxxxxxxstxxxxOx1x280603070901 1、绘出约束方程的图形、绘出约束方程的图形2 2、确定可行解域、确定

18、可行解域3 3、绘出目的函数图形、绘出目的函数图形4 4、确定最优解及目的函数、确定最优解及目的函数值值可行解域可行解域目的函数变形得：目的函数变形得：217330zxx 目的函数等值线目的函数等值线最优解最优解Q2(75,15)Q1Q3Q4Q5Q6Q7Q8几个概念：几个概念：可行解：满足线性规划一切约束条件含约可行解：满足线性规划一切约束条件含约束方程与变量约束的点。束方程与变量约束的点。可行解域：所在可行解的集合。可行解域：所在可行解的集合。最优解：使目的函数得到极值的可行解。最最优解：使目的函数得到极值的可行解。最优解包括：独一最优解和无穷多最优解。优解包括：独一最优解和无穷多最优解。v

19、等值线：具有一样目的函数值的直线。等值线：具有一样目的函数值的直线。v法向量法向量(梯度梯度):由目的函数系数组成的与等值线垂直的向由目的函数系数组成的与等值线垂直的向量。量。二、二维线性规划问题解的方式二、二维线性规划问题解的方式 1、独一最优解、独一最优解2、无穷多个最优解、无穷多个最优解66843x2可行解域目的函数的等值线目的函数的等值线C(1,2)Q2(4,2)Q3(2,3)x1Max Z=x1+2x2 x1+x26 x1+2x28 x23 xi0(i=1,2)3、有可行解但无最优解、有可行解但无最优解max Z=x1+x2 -2x1+x24 x1-x22 x1,x20 x2x1-2

20、4-22可行解域可行解域(1,1)4、无可行解、无可行解MinZx1+2x2 s.t. x1+x21 2x1+x24 x1,x20 x2x11142(1,2)可行域为空可行域为空集，无可行集，无可行解解! 线性规划的可行解域为凸多边形凸集。线性规划的可行解域为凸多边形凸集。可行解域凸多边形有假设干个顶点，顶点的个数是有限可行解域凸多边形有假设干个顶点，顶点的个数是有限的。的。三、线性规划的几何意义三、线性规划的几何意义 线性规划问题假设存在最优解，那么最优解必可在其可线性规划问题假设存在最优解，那么最优解必可在其可行域的某一顶点上得到。行域的某一顶点上得到。 Ox1x2Q2(75,15)60最

21、优解最优解Q1Q3Q4Q5Q6Q7Q8四、单纯形法原理四、单纯形法原理Ox1x2Q2(75,15)60最优解最优解Q1Q3Q4Q5Q6Q7Q8找可行解域顶点的计算方法，但不找可行解域顶点的计算方法，但不是计算一切的顶点，而是从凸集的一是计算一切的顶点，而是从凸集的一个顶点出发，沿着凸集的边缘逐个验个顶点出发，沿着凸集的边缘逐个验算所遇到的顶点，直到找到目的函数算所遇到的顶点，直到找到目的函数为最优的顶点为止。如从为最优的顶点为止。如从O Q1 Q2或从或从O Q4 Q3 Q2 。1.31.3单纯形法原理单纯形法原理5.35.3线性规划规范型和规范型线性规划规范型和规范型一、线性规划的规范型一、

22、线性规划的规范型 约束方程均为等式方程。约束方程均为等式方程。右边常数右边常数bi为正数。为正数。一切变量均为非负变量。一切变量均为非负变量。目的函数求目的函数求max1、普通方式：、普通方式：1 12211 11221121 1222221 12212max,0nnnnnnmmmnnmnZc xc xc xa xa xa xba xa xa xba xaxaxbx xxnjxmibxaxcZjnjijijnjjj, 1 , 0, 1 ,max11或写成累加和方式：或写成累加和方式：1 12211 11221121 1222221 12212max,0nnnnnnmmmnnmnZc xc xc

23、 xa xa xa xba xa xa xba xaxaxbx xx规范型的普通方式规范型的普通方式max0ZCXAXbX或写成矩阵方式：或写成矩阵方式：1 12211 11221121 1222221 12212max,0nnnnnnmmmnnmnZc xc xc xa xa xa xba xa xa xba xaxaxbx xx111212122212,nnmmmnaaaaaaAaaa12,nxxXx12,nbbbb12( ,)nCc cc12jjjmjaaPa其中：其中：12 ,nAP PP则2、化线性规划问题为规范型、化线性规划问题为规范型约束方程为约束方程为“号，号，在方程式的左端在

24、方程式的左端“一个变量变量一个变量变量00，称为松驰变量，称为松驰变量，原不等式化为等式约束。原不等式化为等式约束。约束方程为约束方程为“号号在方程式的左端在方程式的左端“一个变量变量一个变量变量00，称为剩余变量，称为剩余变量，原不等式化为等式约束。原不等式化为等式约束。 (1) (1) 约束条件为等式约束条件为等式2 2变量非负约束变量非负约束假设假设xkxk为无约束变量即可为无约束变量即可00，也可，也可00，引进两个变，引进两个变量量xkxk,xk,xk均均00，令，令xk=xkxk=xkxkxk。在规划模型中去。在规划模型中去掉掉xkxk这个变量。这个变量。3 3约束方程右边常数非负

25、约束约束方程右边常数非负约束在方程两边同时乘以在方程两边同时乘以-1-1使得约束方程右边常数变为非负使得约束方程右边常数变为非负 34531212121245max703000039 540 55 450.93 7200(1,5)jZxxxxxxxxstxxxxxxxj 规范型为：规范型为：1212121212max70303954055450.93720,0Zxxxxxxstxxxx例例1：把下面的线性规划模型化为规范型：把下面的线性规划模型化为规范型：123123123123123min2372325,0,Zxxxxxxxxxxxxx xx 无约束124512456124571245124

26、567max23()() 7() 232() 5,0Dxxxxxxxxxxxxxxxxxxx x x x x x得到该问题的规范型为：得到该问题的规范型为：(1)(1)用用x4x4x5x5交换交换x3x3，其中，其中x4x4，x50 x50(2)(2)在第一个约束不等式在第一个约束不等式号左端加上号左端加上松驰变量松驰变量x6x6(3)(3)在第二个约束不等式左边减去松驰在第二个约束不等式左边减去松驰变量变量x7x7(4)(4)令令D DZ,Z,把求把求min Zmin Z化成化成max Dmax D例例2：把下面的线性：把下面的线性规划模型化为规范规划模型化为规范型：型：二、线性规划的规范型

27、二、线性规划的规范型要用单纯形法求解线性规划数学模型，还需求把数学模要用单纯形法求解线性规划数学模型，还需求把数学模型化成规范型。型化成规范型。1 1基、基变量与非基变量基、基变量与非基变量11max, 1,0, 1,njjjnijjijjZc xa xbimxjn 基：设基：设A是约束方程组的是约束方程组的mn维系数矩阵，维系数矩阵，B是矩阵是矩阵A中中m阶方阶方阵行列式的值不为阵行列式的值不为0，那么称，那么称B是线性规划问题的一个基。是线性规划问题的一个基。基变量与非基变量：与基基变量与非基变量：与基B对应的变量为基变量。其他变量为对应的变量为基变量。其他变量为非基变量。非基变量。 12

28、123124125max703039 540 55 450.93 7200(1,5)jZxxxxxxxxstxxxxj设线性规设线性规划模型的划模型的规范型：规范型：12123124125max703039 540 55 450.93 7200(1,5)jZxxxxxxxxstxxxxj请列举出其中的三请列举出其中的三个基及对应的基变量与个基及对应的基变量与非基变量。非基变量。例例1：解：从约束系数矩阵可看出，该模型的基不超越解：从约束系数矩阵可看出，该模型的基不超越3510C 个。个。对应的基变量为对应的基变量为x3,x4,x5,非基变量为非基变量为x1,x2。110 BB为基.391005

29、501093001A1345100,010001BP P P取对应的基变量为对应的基变量为x1,x3,x4，非基变量，非基变量为为x2,x5。220 BB为基.391005501093001A2134310,501900BP P P取330 BB为基.对应的基变量为对应的基变量为x1,x2,x3，非基变量为，非基变量为x4,x5。3123391,550930BP P P取2根本解和根本可行解根本解：对某一确定的基，令非基变量等于根本解：对某一确定的基，令非基变量等于0，可求出，可求出m个约个约束方程的基变量的值，那么这组解称为根本解。束方程的基变量的值，那么这组解称为根本解。根本可行解：假设根

30、本解还满足决策变量非负要求，那么这根本可行解：假设根本解还满足决策变量非负要求，那么这组根本解称为根本可行解也称基可行解。组根本解称为根本可行解也称基可行解。11max, 1,0, 1,njjjnijjijjZc xa xbimxjn 12123124125max703039 540 55 450.93 7200(1,5)jZxxxxxxxxstxxxxj对基对基B1来说，令非基变来说，令非基变量量120,0 xx，那么可以得到一个根本解 12123124125max703039 540 55 450.93 7200(1,5)jZxxxxxxxxstxxxxj1100010001B(1)123

31、45( ,)(0,0,540,450,720)TTXx xx xx(1)0X(1)X由于由于，故，故是基可行解。是基可行解。 对基对基B2来说，令非基变来说，令非基变量量，那么可以得到一个根本解，那么可以得到一个根本解 (2)0X(2)X由于由于，故，故也是基可行解。也是基可行解。 250,0 xx(2)12345( ,)(80,0,300,50,0)TTXx xx xx2134310,501900BP P P取对基对基B3来说，令非基变来说，令非基变量量，那么可以得到一个根本解，那么可以得到一个根本解 12123124125max703039 540 55 450.93 7200(1,5)j

32、Zxxxxxxxxstxxxxj(3)0X(3)X由于由于，故，故不是基可行解。不是基可行解。 350,0 xx(3)12345(,)(67.5,37.5,0, 75,0)TTXx xx xx3124390,551930BP P P取对基对基B4来说，令非基变来说，令非基变量量, 那么可得根本解那么可得根本解 (4)0X(4)X由于由于，故，故也不是基可行解。也不是基可行解。 150,0 xx(4)12345(,)(0,240, 1620, 750,0)TTXx xx xx4234310,501900BP P P3基可行解与可行解域顶点的关系Ox1x2Q2(75,15)60最优解最优解Q1Q3

33、Q4Q5Q6Q7Q8(2)(80,0,300,50,0)TX(1)(0,0,540,450,720)TX12123124125max703039 540 55 450.93 7200(1,5)jZxxxxxxxxstxxxxjX(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) 对应对应?Ox1x2806090最优解最优解Q2(75,15)Q1Q3Q4Q5Q6Q7Q8非基变量非基变量基变量基变量基本解基本解X( x1,x2 x3,x4, x5)T对应点对应

34、点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)TQ21213212121245max703039 54055 450.93 =x720,0Zxxxxxxstxxxxxx定理定理1 1：线性规划的根本可行解对应于可行解域的顶：线性规划的根本可行解对应于可行解域的顶 点。点。从定理从定理1和单纯形的几何意义知，用单纯形法寻求最优解，和单纯形的几何意义知，用单纯形法寻求最优解，就可从根本可行解

35、顶点出发，在根本可行解顶点之就可从根本可行解顶点出发，在根本可行解顶点之间变换，假设间变换，假设L.P.有最优解，那么最优解一定可在某一根本可有最优解，那么最优解一定可在某一根本可行解顶点上得到。这个方法可用来求有恣意多个变量的行解顶点上得到。这个方法可用来求有恣意多个变量的线性规划模型！线性规划模型！Ox1x2Q2(75,15)60最优解最优解Q1Q3Q4Q5Q6Q7Q8已是规范型；已是规范型；1213212121245max703039 54055 450.93 720,0Zxxxxxxstxxxxxxx0345100,010001Bppp取基得初始根本可行解：得初始根本可行解：X(1X(

36、1=(0,0,540,450,720) T,Z=0=(0,0,540,450,720) T,Z=0。4 4、线性规划的规范型、线性规划的规范型例例1：特点特点1基变量的值刚好是约束方程右边的常数；基变量的值刚好是约束方程右边的常数；2目的函数目的函数Z的值就是目的函数表达式中的常数。的值就是目的函数表达式中的常数。 含单位基；含单位基；目的函数用非基变量表示。目的函数用非基变量表示。规范型条件：规范型条件：25235245 12520705600391 8 3003105 5039118039Zxxxxxxxxxxx 1213212121245max703039 54055 450.93 72

37、0,0Zxxxxxxstxxxxxxx假设取基变量假设取基变量x3,x4,x1,x3,x4,x1,那么那么基解及目的函数值？基解及目的函数值？可把模型化成以基变量系数矩阵为单位阵的规范型：可把模型化成以基变量系数矩阵为单位阵的规范型： (2)(80,0,300,50,0)TX(2)5600Z得到根本可行解：得到根本可行解：， 引例引例1：求解以下线性规划模型的最优解：求解以下线性规划模型的最优解解：解：1、确定初始基可行解、确定初始基可行解取取B1P3P4P5I，令非基变量令非基变量x1,x2=0，得，得X(1)0,0,540,450,720T，Z(1)0；解的含义？；解的含义？ 从规范型出发

38、从规范型出发5.45.4单纯形法步骤单纯形法步骤1213212121245max703039 54055 450.93 720,0Zxxxxxxstxxxxxxx2、断定解能否最优、断定解能否最优目的函数目的函数Max Z0+70 x1+30 x2检验数：用非基变量表达的目的函数中变量前的系数检验数：用非基变量表达的目的函数中变量前的系数Rj判判别数或检验数。别数或检验数。 当当x1从从0 或或x2从从0 ， Z从从0 ， X(1) 不是最优解不是最优解3、由一个基可行解、由一个基可行解另一个基可行解。另一个基可行解。 (1) 确定入基变量确定入基变量可选可选Rj0的任一变量入基。意义？普通地

39、，选择的任一变量入基。意义？普通地，选择maxRj的变量入基，选的变量入基，选x1从从0 ，坚持，坚持x2 =0 (2)确定出基变量确定出基变量问题：确定入基变量问题：确定入基变量x1x1添加的上添加的上界：从约束方程组怎样求解？界：从约束方程组怎样求解？在中，继续令在中，继续令x2x2为非基变量，即为非基变量，即x2 x2 0 0，求出当前每，求出当前每个基变量出基能使个基变量出基能使x1x1增大的上界值。即：增大的上界值。即：x3=5403x10 x1180=540/3x4=4505x10 x190=450/5x5=720 9x1 0 x180=720/91213212121245max7

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

41、型。把模型变成以基变量的系数矩阵为单位阵的规范型。 (3)求出新的基可行解求出新的基可行解 以基变量以基变量x3,x4,x5x3,x4,x5的系数矩阵的系数矩阵为单位阵的规范型为单位阵的规范型: : 12123124125max703039 540 55 450.93 7200(1,5)jZxxxxxxxxstxxxxj 1 1从出基变量从出基变量x5x5所在的方程所在的方程开场：方程两边同时除以入基开场：方程两边同时除以入基变量变量x1x1的系数的系数9 9，得：，得： 125(1/3) (1/9)80 xxx2 2方程中消去方程中消去x1x1入基变量：方程两边同时入基变量：方程两边同时乘以

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

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

44、0039QZxx，R2=20/3, R5=-70/9235245 1251 8 3003105 5039118039xxxxxxxxx=min 37.5，15 ，24015，x4出基出基(2) 确定新基可行解：确定新基可行解：x3=300 x3=3008x2 x237.5 8x2 x237.5 x4=50 x4=5010 x2/3 x21510 x2/3 x215x1=80 x1=80 x2/3 x2240 x2/3 x2240252525 2341520705600391 8 3003105 5039118039Zxxxxxxxxxxx 把模型变成以基变量把模型变成以基变量x3,x2,x1x

45、3,x2,x1的系数矩阵为单位阵的规范型。的系数矩阵为单位阵的规范型。 新的基变量新的基变量x3,x2,x1x3,x2,x125235245 12520705600391 8 3003105 5039118039Zxxxxxxxxxxx 怎样把模型变成以基变量怎样把模型变成以基变量x3,x2,x1x3,x2,x1的系数矩阵为单位阵的系数矩阵为单位阵的规范型？的规范型？ (1)(1)从出基变量从出基变量x4x4所在的方程所在的方程开场：使入基变量开场：使入基变量x2x2的系数变成的系数变成1 1。(2)(2)用消元法消去方程用消元法消去方程中的中的x2x2。X(3)75,15,180,0,0T，

46、Z(3)5700；由方程组变形得：由方程组变形得：(3)454545431522057002312 180531 1510611 75 1 06Zxxxxxxxxxxx2、断定解能否最优、断定解能否最优 目的函数目的函数X(3)75，15，180，0，0T，Z(3)5700；非基变量的检验系数均为负数，故不能入基，否那么使目非基变量的检验系数均为负数，故不能入基，否那么使目的值劣化。的值劣化。当前解为最优解。当前解为最优解。(3)4520570023Zxx最优解判别规范：最优解判别规范：1 1 假设全部检验数假设全部检验数Rj 0Rj 0，当前根本可行解为最优解。，当前根本可行解为最优解。2

47、2 假设存在假设存在Rj Rj 0 0，那么当前解非最优，解可改良，那么当前解非最优，解可改良，寻求寻求 更好的解。更好的解。1、 确定初始基可行解。确定初始基可行解。 此题确定初始基为单位阵此题确定初始基为单位阵I，令单位阵对应的变量为基变量，令单位阵对应的变量为基变量，可得到一个根本可行解。可得到一个根本可行解。小结：单纯形法求解线性规划的过程小结：单纯形法求解线性规划的过程 规范型：规范型： AXb X0，b0 A中含有一单位阵。中含有一单位阵。2、最优化检验：用当前可行基的非基变量的检验数确定。、最优化检验：用当前可行基的非基变量的检验数确定。 3、 从一个根本可行解到另一个根本可行解

48、从一个根本可行解到另一个根本可行解 入基变量：由检验数确定。入基变量：由检验数确定。 出基变量：由出基变量：由规那么确定。规那么确定。 12123124125max703039 540 55 450.93 7200(1,5)jZxxxxxxxxstxxxxj 25235245 12520705600391 8 3003105 5039118039Zxxxxxxxxxxx (3)453452451452057002312 180531 1510611 75 106Zxxxxxxxxxxx用单纯形法从另一条途径寻优？用单纯形法从另一条途径寻优？cj c1 c2 cnCBXB x1 x2 xnxi1

49、xi2ximZ R1 R2 RnZ01 11 212 12 2212nnmmm naaaaaaaaa 12mbbb b5.55.5单纯形表单纯形表目的函数行：常数目的函数行：常数Z0在右边。在右边。1、由规范型列出初始单纯形表：、由规范型列出初始单纯形表：X(1)0,0,540,450,720TZ(1)01213212121245max703039 54055 450.93 720,0Zxxxxxxstxxxxxxxb主元主元(0)1207030Zxx(0)1270300Zxx cj7030000CBXBx1x2x3x4x50 x3391005401800 x455010450900 x593

50、00172080-Z703000002、变换到下一单纯表变成以新基为单位阵的规范型、变换到下一单纯表变成以新基为单位阵的规范型思索：单纯形表有什么特点？思索：单纯形表有什么特点？1基变量对应的约束方程中系数矩阵为单位矩阵。基变量对应的约束方程中系数矩阵为单位矩阵。2目的函数基变量的检验数为目的函数基变量的检验数为0。3基可行解基可行解(？)不同，反映在原表中就是对应的基不同。不同，反映在原表中就是对应的基不同。 b新的基变量：新的基变量：x3 ,x4,x1 cj7030000CBXBx1x2x3x4x50 x30810-1/3300 37.50 x4010/301-5/9501570 x111

51、/3001/980240-Z020/300-70/9-5600主元主元表一表一表二表二00003070-Z8072010039x509045001055x4018054000193x30 x5x4x3x2x1XBCB0003070Cjb9-5600-70/90020/30-Z240801/9001/31x11550-5/91010/30 x4037.5300-1/30180 x307025235245 1252070max z=5600+x391 8 3003105 5039118039xxxxxxxxxx?1213212121245max703039 54055 450.93 =720,0Z

52、xxxxxxstxxxxxxx3、反复以上过程直到得最优解：、反复以上过程直到得最优解：思索：在单纯形表中，怎样判别思索：在单纯形表中，怎样判别LP问题已获得最优解？问题已获得最优解？最优解判别规范：最优解判别规范：1 1 假设全部检验数假设全部检验数Rj 0Rj 0，当前根本可行解为最优解。，当前根本可行解为最优解。2 2 假设存在假设存在Rj Rj 0 0，那么当前解非最优，解可改良，那么当前解非最优，解可改良，寻求更好的解。寻求更好的解。cj7030000CBXBx1x2x3x4x5b 0X3391005401800X455010450900 x59300172080-Z70300000

53、0 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=5700例例1：求解以下线性规划模型：求解以下线性规划模型：123123123max453480002430000,1,2,3jzxxxxxxxxxxj解：化线性规划模型为规范型，并列出初始单纯形表：解：化线性规划模型为规范型，并列出初始单纯形表：按单纯法迭代，

54、计算如下表，得最优解为按单纯法迭代，计算如下表，得最优解为:X=(1500,0,0,3500,0)T, Z=6000-6000-20-3-10-Z15001/2021/21x13500-3/21-2-1/20 x4-3750-5/400-1/43/2-Z15007501/4011/4x350005000-11001x4000514-Z750300010412x52000800001413x4bx5x4x3x2x1XBCB00514Cj41/2例例2： 用单纯形法求解以下线性规划数学模型用单纯形法求解以下线性规划数学模型123523451242456min326225(2)238 (3)0jzx

55、xxxxxxxxxxxxxxx(1)选选x1x1、x3x3、x6x6为基变量为基变量 目的函数用非基变量表示：目的函数用非基变量表示：由由 约束方程约束方程(1)(2)(3)(1)(2)(3)解出解出x3 = 6 - x2 + x4 - 2x5 x3 = 6 - x2 + x4 - 2x5 x1 = 5 - 2x2 + 2x4x1 = 5 - 2x2 + 2x4代入目的函数得：代入目的函数得：Min Z = 11 - 4x2 + 3x4 - 5x5 Min Z = 11 - 4x2 + 3x4 - 5x5 24523451242456max1143526225(2)238 (3)0jDxxxx

56、xxxxxxxxxxx (1)把把LP化成求极大的规范型：化成求极大的规范型：XBx1x2x3x4x5x6bx1120-2005x3011-12063x602013188/3-D040-3501124523451242456max1143526225(2)238 (3)0jDxxxxxxxxxxxxxxx (1)X(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

57、/30-5/31-1/30 x35/2500-2021x11105-3040-D8/38131020 x63602-1110 x3500-2021x1bx6x5x4x3x2x1XB假设目的函数求极大假设目的函数求极大MAX1、从规范型出发，得出一个初始基可行解。按要求填入表中。、从规范型出发，得出一个初始基可行解。按要求填入表中。2、最优化检验：假设还存在、最优化检验：假设还存在Rj0，那么当前解不是最优解。，那么当前解不是最优解。3 3、解的改良：、解的改良：由检验数确定入基变量由检验数确定入基变量xpxp。( (普通正系数大的变量先入基普通正系数大的变量先入基) )确定出基变量确定出基变量

58、: :,0iiipipbaa计算min|0ilipiplpbbaaa取确定确定L L为出基行，那么为出基行，那么xLxL为换出变量。得到一个新的可行基。为换出变量。得到一个新的可行基。单纯形算法步骤单纯形算法步骤4 4、用初等行变换方法把主元、用初等行变换方法把主元aLpaLp变为变为1 1，把入基列，把入基列含其检验数中除主元的其它元素消为零。转含其检验数中除主元的其它元素消为零。转2.2.讨论：单纯形表进展求解的特殊情况 1假设最大检验数有两个或两个以上并且相等，应如何确假设最大检验数有两个或两个以上并且相等，应如何确定入基变量，实际上可任选一个非基变量入基，但在实践运定入基变量，实际上可

59、任选一个非基变量入基，但在实践运用中，可采用以下法那么：用中，可采用以下法那么： XBx1x2x3x4x5b12x33910054018060 x4550104509090 x59300172080240-Z70700000依次选择依次选择X1X1和和X2X2入基，分别计算出两组比值入基，分别计算出两组比值1 1和和2 2，每组比值中分别选择最小值得每组比值中分别选择最小值得8080和和6060，两个最小值中选择最，两个最小值中选择最大值大值8080，因此确定，因此确定X1X1入基，此时目的函数值改动得最快入基，此时目的函数值改动得最快(?)(?)。2原问题有解但无最优解原问题有解但无最优解(

60、无界无界)的判别：某个的判别：某个Rj0,但但aij0(i=1,2,m)。例例4 4：求解线性规划问题：求解线性规划问题：12121212max32124,0Zxxxxxxx x 12123124max321240(1,4)jZxxxxxxxxxj XBx1x2x3x4bx33-2101x42-1014Z1100规范化规范化一、最优决策变量的解一、最优决策变量的解最优解是单纯形法的根本目的信息，在建模参最优解是单纯形法的根本目的信息，在建模参数可靠的根底上，它提供最优决策方案数可靠的根底上，它提供最优决策方案 。如例如例2中：中：最优解：最优解：X(3)75，15，180，0，0T，Z(3)5