第1章：线性规划.ppt

《第1章：线性规划.ppt》由会员分享，可在线阅读，更多相关《第1章：线性规划.ppt（40页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第一章：线性规划第一章：线性规划1.1 1.1 线性规划线性规划(Linear(Linear ProgramingPrograming-L.P.)-L.P.)概述概述一、一、L.P.L.P.概念：概念：L.P.L.P.是目前应用最广泛的一种系统优化方法。其理论已十分成熟，广泛应用于工农业生产是目前应用最广泛的一种系统优化方法。其理论已十分成熟，广泛应用于工农业生产 和经济管理等领域。和经济管理等领域。以数学为工具，在一定资源条件下，如何合理安排，取得最大经济效果。以数学为工具，在一定资源条件下，如何合理安排，取得最大经济效果。二、发展史：二、发展史：3030年代末年代末(苏苏)康特罗维奇书康特

2、罗维奇书“生产组织与计划中的数学方法生产组织与计划中的数学方法”，为为L.P.L.P.建立数学模型和求解奠定了基础。建立数学模型和求解奠定了基础。1 1、(美美)库普曼库普曼(T.C.(T.C.KoopmansKoopmans)建立了建立了L.P.L.P.数学模型，获诺贝经济奖。数学模型，获诺贝经济奖。2 2、(美美)丹泽丹泽(G.B.(G.B.DantzigDantzig)在在19471947年年提出求解提出求解L.P.L.P.数模的通用方法数模的通用方法 -单纯形法。单纯形法。19461946年，世界上第一台计算机问世，使单纯形法处理大规模年，世界上第一台计算机问世，使单纯形法处理大规模L

3、.P.L.P.数模成为可能。数模成为可能。三、三、L.P.L.P.问题的求解过程问题的求解过程 1 1、将实际问题转化为数学模型、将实际问题转化为数学模型(数学公式数学公式)：建模。：建模。2 2、求解数学模型：、求解数学模型：图解法：图解法：适合于适合于 2 2 个变量的个变量的 L.P.L.P.数学模型。数学模型。单纯形法：适合于任意个变量的单纯形法：适合于任意个变量的 L.P.L.P.数学模型。数学模型。3 3、利用数学模型的最优解获得原问题的最优决策方案。、利用数学模型的最优解获得原问题的最优决策方案。11.2 1.2 线性规划及其数学模型线性规划及其数学模型一、L.P.问题 例：例：

4、某厂生产甲、乙两种产品，均需在A、B、C三种不同的设备上加工，产品加工所需工时、销售后能获得的利润及设备有效工时数如下表。问：如何安排生产计划，才能使该厂获 得总利润最大？解解:设设甲、乙产品产量分别为甲、乙产品产量分别为x1、x2 公斤公斤 决策变量，简称变量决策变量，简称变量 设总利润为设总利润为Z，则则 Max Z=70 x130 x2 目标函数目标函数 设备可用工时数限制设备可用工时数限制 约束条件约束条件 s.t.3x1+9x2 540 A 设备设备可用工时可用工时约束约束 5x1+5x2 450 B 设备设备可用工时可用工时约束约束 9x1+3x2 720 C 设备设备可用工时可用

5、工时约束约束 x1,x2 0 非负约束非负约束 设备设备产品产品 ABC利润利润(元元/公斤公斤)甲甲 乙乙3955937030限制工时限制工时 540450720单耗单耗2二二、L.P.L.P.数学模型的经济含义数学模型的经济含义 1、数学模型的三要素、数学模型的三要素:.有一组待确定的决策变量。如有一组待确定的决策变量。如(x1,x2)为一个具体行动方案。为一个具体行动方案。.有一个明确的目标要求有一个明确的目标要求(Max或或Min)。如要求利润最大。如要求利润最大。.存在一组约束条件。如设备存在一组约束条件。如设备A、B、C三种资源的约束。三种资源的约束。2、数学模型中系数的含义、数学

6、模型中系数的含义:.目标函数中决策变量的系数目标函数中决策变量的系数70,30 -叫价值系数，表单位产品提供的利润叫价值系数，表单位产品提供的利润(元元/件件)；.约束条件左边决策变量的系数约束条件左边决策变量的系数 -叫约束条件系数或单耗叫约束条件系数或单耗(台时、台时、kg、kg/件件)；.约束条件右边常数约束条件右边常数540,450,720 -叫限制常数，表现有的资源限量。叫限制常数，表现有的资源限量。三、线性规划数学模型的解三、线性规划数学模型的解 1、可行解：满足约束条件、可行解：满足约束条件、的所有解。的所有解。2、可行解域：所有可行解的集合，上图阴影部分。、可行解域：所有可行解

7、的集合，上图阴影部分。3、最优解：满足目标函数、最优解：满足目标函数的可行解。的可行解。4、基本解：所有约束条件直线的交点对应的解，、基本解：所有约束条件直线的交点对应的解，即上图所有的实心点和空心点对应的解。即上图所有的实心点和空心点对应的解。5、基本可行解：既是基本解又是可行解，、基本可行解：既是基本解又是可行解，即上图所有的实心点对应的解。即上图所有的实心点对应的解。它满足两个它满足两个条件：条件：其一是约束条件直线的交点对应的解；其一是约束条件直线的交点对应的解；其二是可行解，即满足所有的约束条件，其二是可行解，即满足所有的约束条件，在可行解域内。在可行解域内。oX1X2ahbkMax

8、 Z=70 x130 x2 s.t.3x1+9x2 540 5x1+5x2 450 9x1+3x2 720 x1,x2 0 3 1、线性规划模型：线性规划模型：如果以上数学模型中的方程均是线性方程，如果以上数学模型中的方程均是线性方程，则该数模称为线性规划数模。则该数模称为线性规划数模。2、非线性规划模型：如果以上数学模型中的方程至少有一个方程是非线性方程，非线性规划模型：如果以上数学模型中的方程至少有一个方程是非线性方程，则该数模称为非线性规划数模。则该数模称为非线性规划数模。四四、L.P.L.P.的一般形式的一般形式 Max(Min)Z =c1 x1 +c2 x2+-+cn xn a11

9、x1+a12 x2+-+a1n xn (,=)b1 a21 x1+a22 x2+-+a2n xn (,=)b2 s.t.-am1 x1+am2 x2+-+amn xn (,=)bm xj 0,j=1-n 41.3 1.3 线性规划问题的建模线性规划问题的建模 确定决策变量；确定目标函数；列出约束条件。确定决策变量；确定目标函数；列出约束条件。一、运输问题建模一、运输问题建模:编制最优运输计划编制最优运输计划,使总运费最少使总运费最少 例：某地有三个有色金属矿例：某地有三个有色金属矿A1A1、A2A2、A3A3，生产同一种金属矿石，生产同一种金属矿石，A1A1矿的年产量为矿的年产量为100100

10、万吨，万吨，A2A2矿为矿为8080万吨，万吨，A3A3矿为矿为5050万吨。矿石全部供应四个冶炼厂，万吨。矿石全部供应四个冶炼厂，B1B1厂的全部需求量为厂的全部需求量为5050万吨，万吨，B2B2厂厂7070为万吨，为万吨，B3B3厂为厂为8080万吨，万吨，B4B4厂为厂为3030万吨。产量恰好等于总需求量，矿石由各矿山万吨。产量恰好等于总需求量，矿石由各矿山 运到冶炼厂的单位运价已知，如下表。问如何安排运输，使各矿山的矿石运到冶炼厂，运到冶炼厂的单位运价已知，如下表。问如何安排运输，使各矿山的矿石运到冶炼厂，满足各厂的需要，且运输费用最小，满足各厂的需要，且运输费用最小，试建立该问题的

11、数学模型试建立该问题的数学模型？.确定决策变量确定决策变量:设设 xij 为从第为从第 i 个矿山到第个矿山到第 j 个冶炼厂个冶炼厂的矿石运输量的矿石运输量(万万 t).确定目标确定目标函数函数:设总运费为设总运费为Z,则则 Min Z=1.5x11+2x12+0.3x13+3x14+7x21+0.8x22+1.4x23+2x24+1.2x31 +0.3x32+2x33+2.5x34 .确定约束条件确定约束条件:x11+x12 +x13+x14 =100 s.t.x21+x22 +x23+x24 =80 x31+x32 +x33+x34 =50 x11+x21 +x31 =50 x12+x2

12、2 +x32 =70 x13+x23 +x33 =80 x14+x24 +x34 =30 xij 0 ,i=13;j=14.5 二、合理下料问题建模二、合理下料问题建模:寻求最佳下料方式寻求最佳下料方式,使余料最少使余料最少.例例 有一批长度为有一批长度为180180公分的钢管公分的钢管,需截成需截成7070、5252和和3535公分三种管料。它们的需求量应分别不少于公分三种管料。它们的需求量应分别不少于 100100、150150和和100100个。问应如何下料才能使钢管的余料为最少个。问应如何下料才能使钢管的余料为最少?解解:.确定决策变量确定决策变量:设设 xj 为第为第 j 种下料方式

13、所用种下料方式所用的钢管根数的钢管根数.确定目标确定目标函数函数:设总余料为设总余料为Z,则则 Min Z=5x1+6x2+23x3+5x4+24x5+6x6+23x7+5x8 (公分公分).确定约束条件确定约束条件:2x1+x2+x3+x4 100 s.t.2x2+x3+3x5+2x6+x7 150 x1+x3+3x4+2x6+3x7+5x8 100 xj 0 ,且为整数且为整数.6 三、人员分派问题建模三、人员分派问题建模:合理分派人员合理分派人员,使总效率最大使总效率最大.例：例：设有四件工作分派给四个人来做，每项工作只能由一人来做，每个人只能做一项工作。设有四件工作分派给四个人来做，每

14、项工作只能由一人来做，每个人只能做一项工作。希望适当安排人选，发挥各人特长又能使总的效率最大希望适当安排人选，发挥各人特长又能使总的效率最大(或完成最快或完成最快,或费用最少或费用最少)。表表1.51.5表示各人对各项工作所具有的工作效率。表示各人对各项工作所具有的工作效率。.确定决策变量确定决策变量:设设 xij 为分派第为分派第 i 个人从事第个人从事第 j 项工作项工作,xij=1,0(分派与否分派与否).确定目标确定目标函数函数:设总效率为设总效率为Z,则则 Max Z=0.6x11+0.2x12+0.3x13+0.1x14 +0.7x21+0.4x22+0.3x23+0.2x24 +

15、0.8x31+1.0 x32+0.7x33+0.3x34 +0.7x41+0.7x42+0.5x43+0.4x44 .确定约束条件确定约束条件:x11+x12 +x13+x14 =1 s.t.x21+x22 +x23+x24 =1 x31+x32 +x33+x34 =1 x41+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=14;j=14.7 四、投资方案选择问题建模四、投资方案选择问题建模:合理选择方案合理选择方案,使

16、总收益最大使总收益最大.例：例：某炼油公司为提高炼油能力和增加企业经济效益某炼油公司为提高炼油能力和增加企业经济效益,经研究有五种技术改造的投资方案可供选择，经研究有五种技术改造的投资方案可供选择，它们所需的投资费用年收益如下表所示它们所需的投资费用年收益如下表所示。其中其中:方案方案1和方案和方案2只能选择其中一种，不能兼而实现，只能选择其中一种，不能兼而实现，并且，如选择方案并且，如选择方案2，则方案，则方案3必须同时选择，或者都不选择必须同时选择，或者都不选择。现该公司可供支配的资金总额为：第一年有现该公司可供支配的资金总额为：第一年有650万元，第二年仅有万元，第二年仅有460万元万元

17、。技术改造的结果。技术改造的结果 要求至少应增加出油能力要求至少应增加出油能力500500桶桶/天，但又不得超过天，但又不得超过11001100桶桶/天，试确定该公司总经济效益最大的天，试确定该公司总经济效益最大的 投资方案。投资方案。8.确定决策变量确定决策变量:设设 xj 为第为第 j 方案的取舍，方案的取舍，xj=1,0(取舍取舍).确定目标确定目标函数函数:设总经济效率为设总经济效率为Z,则则 Max Z=100 x1+200 x2+50 x3+30 x4+20 x5(万元万元).确定约束条件确定约束条件:200 x1+300 x2 +150 x3+100 x4+50 x5 650 s

18、.t.200 x1+150 x2 +50 x3+70 x4+40 x5 460 500 x1+1000 x2 +100 x3+50 x4+20 x5 500 500 x1+1000 x2 +100 x3+50 x4+20 x5 1100 x1+x2 1 -x2 +x3 =0 xj=0,1,j=15.9 五、选点决策问题五、选点决策问题:合理选点合理选点,使总利率最大使总利率最大.例例：某某公公司司拟拟在在A A、B B、C C、D D、E E五五个个城城市市中中建建立立若若干干产产品品经经销销联联营营点点，各各处处设设点点都都需需资资金金、人人力力、设设备备等等，需需求求量量以以及及能能提提供

19、供的的利利润润各各处处不不同同，有有些些点点可可能能亏亏本本，但但却却能能获获得得贷贷款款和和人人力力等等。假假设设数数据据已已知，见下表，为使总利润最大，问厂方应作何种最优选点决策？知，见下表，为使总利润最大，问厂方应作何种最优选点决策？.确定决策变量：要求从五个城市中选择最优确定决策变量：要求从五个城市中选择最优 产品经销联营点，设决策变量产品经销联营点，设决策变量xj(j=1,2,5)表示第表示第j个城市的取舍，所以决策变量个城市的取舍，所以决策变量xj的取的取 值仅有值仅有1和和0两种值。两种值。.确定目标确定目标函数函数：要求公司总利润：要求公司总利润Z最大，则最大，则 Max Z

20、4.5x13.8x29.5x32x41.5x5 .确定约束条件确定约束条件:4x16x212x38x4x5 20 s.t.5x14x212x33x48x5 15 x1x2x3 2 xj 0、1，j=1,5 资资源源城市城市应应投投资资(百万元百万元)应应投人力投人力（人）（人）应应投投设备设备（套）（套）利利润润(万元万元)A45145B64138C1212195D-830-2E1-80-1.5资资源限量源限量20152101.4 1.4 线性规划图解法线性规划图解法 一、一、适用范围：适用范围：二个变量的数学模型。二个变量的数学模型。二、二、求解步骤：求解步骤：Max Z=70 x130 x

21、2 s.t.3x1+9x2 540 5x1+5x2 450 9x1+3x2 720 x1,x2 0 oX1X2ahbk7030(75,15)最优解最优解为：为：X*=(75，15)T Z*=5700 第二步：确定可行解域，即所有约束方程图形的公共部分；第二步：确定可行解域，即所有约束方程图形的公共部分；第三步：绘出目标函数直线，根据目标函数的要求以及与决策变量的关系，找出直线移动方向。第三步：绘出目标函数直线，根据目标函数的要求以及与决策变量的关系，找出直线移动方向。第五步：确定最优解及最优目标函数值。第五步：确定最优解及最优目标函数值。第一步：将所有约束方程用图形绘出；第一步：将所有约束方程

22、用图形绘出；第四步：第四步：目标函数直线向着可行解域的右上方平行移动，直至与可行解域相切为止，目标函数直线向着可行解域的右上方平行移动，直至与可行解域相切为止，这个切点就是最优点，对应的解就是最优解。这个切点就是最优点，对应的解就是最优解。所以，产品所以，产品甲、乙分别安排产量甲、乙分别安排产量75Kg75Kg、15Kg15Kg，可使工厂获利最大为，可使工厂获利最大为57005700元。元。11 三、三、LPLP几何意义几何意义 oX1X2ahbk 1、闭合的可行解域是凸多边形、闭合的可行解域是凸多边形(凸集凸集)。2、可行解域有若干个顶点：、可行解域有若干个顶点：O、a、h、k、b。对应的解

23、叫基本对应的解叫基本可行可行解解。3、最优解若唯一存在，则必是顶点中的某一个。、最优解若唯一存在，则必是顶点中的某一个。12 四、特殊的数学模型四、特殊的数学模型 1、有无穷多个最优解：若有两个最优解，则必有无穷多个最优解。如下例数学模型：、有无穷多个最优解：若有两个最优解，则必有无穷多个最优解。如下例数学模型：Max Z=x12x2s.t.x1+x2 6 x1+2x2 8 x2 3 x1,x2 0OX1X2Q1Q2Q3Q4 此线性规划问题的最优解在此线性规划问题的最优解在Q Q2 2Q Q3 3线段上，如上图所示，即线段线段上，如上图所示，即线段Q Q2 2Q Q3 3上任意一点都使上任意一

24、点都使Z Z取得相同的最大值，这个线性规划问题有无穷多最优解。取得相同的最大值，这个线性规划问题有无穷多最优解。因此，若有两个最优解，则必有无穷多个最优解。因此，若有两个最优解，则必有无穷多个最优解。13 四、特殊的数学模型四、特殊的数学模型 2、解无界：可行解域无界，目标值无限增大。如下例数学模型：、解无界：可行解域无界，目标值无限增大。如下例数学模型：Max Z=x1x2 s.t.-2x1+x2 4 x1-5x2 2 x1,x2 0 OX1X2用图解法求解结果见上图所示，从图中可以看到，该问题可行解域无界，目标函数值可用图解法求解结果见上图所示，从图中可以看到，该问题可行解域无界，目标函数

25、值可以增大到无究大，称这种情况为无界解或无最优解。以增大到无究大，称这种情况为无界解或无最优解。14 四、特殊的数学模型四、特殊的数学模型 3、无可行解域：约束条件相互矛盾。如下例数学模型、无可行解域：约束条件相互矛盾。如下例数学模型Max Z=3x14x2s.t.x1+x2 6 x1 2 x2 3 x1,x2 02OX1X2636该问题可行解域为空集，如上图所示，即无可行解域，当然也无最优解。该问题可行解域为空集，如上图所示，即无可行解域，当然也无最优解。151.5 1.5 线性规划单纯形法线性规划单纯形法 一、一、适用范围适用范围 任意个变量的数学模型。任意个变量的数学模型。二、原理二、原

26、理 从一初始顶点从一初始顶点(初始基本可行解初始基本可行解)出发，沿可行解域的边缘逐个验算遇到的顶点出发，沿可行解域的边缘逐个验算遇到的顶点(基本可行解基本可行解)，直至找最优点直至找最优点(最优解最优解)为止。为止。Max Z=70 x130 x2 s.t.3x1+9x2 540 5x1+5x2 450 9x1+3x2 720 x1,x2 0 oX1X2ahbk最优解最优解为：为：X*=(75，15)T Z*=5700 16 三、三、LPLP数模的标准型数模的标准型 条件一条件一:具有等式约束方程组；具有等式约束方程组；条件二条件二:右边常数非负；右边常数非负；条件三条件三:变量非负；变量非

27、负；条件四条件四:目标函数为目标函数为MaxMax型。型。Max Z=70 x130 x2 s.t.3x1+9x2 540 5x1+5x2 450 9x1+3x2 720 x1,x2 0 对设备对设备A A：3x3x1 1+9x+9x2 2 540 540，引入非负松弛变量引入非负松弛变量x x3 3，加到不等式的左边得加到不等式的左边得 3x3x1 1 +9x +9x2 2 +x x3 3 =540=540 实际使用的实际使用的 空闲工时空闲工时(0)0)限制工时限制工时 工时数工时数 (起松弛作用起松弛作用,叫松弛变量叫松弛变量)Max Z=70 x130 x2s.t.3x1+9x2+x3

28、 =540 5x1+5x2 +x4 =450 9x1+3x2 +x5=720 xj 0，j=1,5 则原数模的标准型为：则原数模的标准型为：对设备对设备B B：5x5x1 1+5x+5x2 2 450 450，引入非负松弛变量引入非负松弛变量x x4 4，加到不等式的左边得加到不等式的左边得 5x5x1 1 +5x +5x2 2 +x x4 4 =450=450 实际使用的实际使用的 空闲工时空闲工时(0)0)限制工时限制工时 工时数工时数 (起松弛作用起松弛作用,叫松弛变量叫松弛变量)对设备对设备C C：9x9x1 1+3x+3x2 2 720 720，引入非负松弛变量引入非负松弛变量x x

29、4 4，加到不等式的左边得加到不等式的左边得 9x9x1 1 +3x +3x2 2 +x x5 5 =720=720 实际使用的实际使用的 空闲工时空闲工时(0)0)限制工时限制工时 工时数工时数 (起松弛作用起松弛作用,叫松弛变量叫松弛变量)17 四、四、LPLP数模的规范型数模的规范型 条件一条件一:具有具有标准型标准型；条件二条件二:约束方程组系数矩阵中含有至少一个单位约束方程组系数矩阵中含有至少一个单位 子矩阵子矩阵(对应的变量叫基变量对应的变量叫基变量)；条件三条件三:目标函数中不含基变量。目标函数中不含基变量。Max Z=70 x130 x2s.t.3x1+9x2+x3 =540

30、5x1+5x2 +x4 =450 9x1+3x2 +x5=720 xj 0，j=1,5；x3,x4,x5为基变为基变量量 则原数模的规范型为：则原数模的规范型为：Max Z=70 x130 x2s.t.3x1+9x2+x3 =540 5x1+5x2 +x4 =450 9x1+3x2 +x5=720 xj 0，j=1,5 x3 x4 x5 3 9 1 0 0 1 0 0 3 9 1 0 0 1 0 0 A=5 5 0 1 0 A=5 5 0 1 0 中有中有 B=0 1 0 =B=0 1 0 =（3 3、4 4、5 5）=E E 9 3 0 0 1 0 0 1 9 3 0 0 1 0 0 1 一

31、组一组基基 1 1 2 2 3 3 4 4 5 5 x1 x2 x3 x4 x5 非基变量非基变量 基变量基变量 基的作用是基的作用是:可以得到初始基本可行解可以得到初始基本可行解(即初始顶点即初始顶点 -通常是原点通常是原点O),O),是单纯行迭代的基础。是单纯行迭代的基础。18五、最优解寻求步骤五、最优解寻求步骤第一步、第一步、确定初始基本可行解：利用确定初始基本可行解：利用规范型数模，令规范型数模，令非基变量非基变量 x1、x2=0，求出求出基变量基变量x3、x4、x5。得初始基本可行解为：得初始基本可行解为：X X(1)=(1)=（x1,x2,x3,x4,x5）T T=(=(0,0,5

32、40,450,720)T T 甲甲 乙乙 设备设备A A 设备设备B B 设备设备C C 空闲工时空闲工时 Z Z(1)=(1)=0，利润为利润为0 未生产未生产，资源全部闲置资源全部闲置 (对应原点对应原点O)(x1、x2 为非为非基变量，基变量，x3、x4、x5为为基变量基变量)第二步、第二步、判断判断X X(1)(1)是否最优：检查用非是否最优：检查用非基变量表达的目标函数中基变量表达的目标函数中非非基变量前的系数基变量前的系数(叫检验数叫检验数)。Max Z =70 x1 +30 x2 因为因为检验数检验数 70、30 0，所以当，所以当 x1 和和 x2从从0增大时，增大时，Z也会增

33、大。也会增大。故故当前解非最优。当前解须改进，寻求更好的解。当前解非最优。当前解须改进，寻求更好的解。oX1X2ahbkMax Z=70 x130 x2s.t.3x1+9x2+x3 =540 5x1+5x2 +x4 =450 9x1+3x2 +x5=720 xj 0，j=1,5；x3,x4,x5为基变为基变量量19第三步、第三步、确定改进的非基变量及其上界确定改进的非基变量及其上界:选择使目标选择使目标Z值改变得最快的值改变得最快的 非基变量优先改进。非基变量优先改进。(1)、确定非基变量确定非基变量 x1 优先改进：因为从目标函数优先改进：因为从目标函数 Max Z =70 x1 +30 x

34、2 可以看出可以看出 x1增加增加1，可使目标，可使目标Z增加增加70；x2增加增加1，目标，目标Z能增加能增加30。(2)、x1增加的上界是增加的上界是80：因为从约束方程组因为从约束方程组可以得出可以得出(从资源最优利用考虑，令从资源最优利用考虑，令x3、x4 、x5=0)x1 =180-3 x2-(1/3)x3 =180 -目前可用的设备目前可用的设备A台时数最多可生产甲产品台时数最多可生产甲产品180Kg。x1 =90 -x2-(1/5)x4 =90 -目前可用的设备目前可用的设备B台时数最多可生产甲产品台时数最多可生产甲产品90Kg。x1=80 -(1/3)x2-(1/9)x5 =8

35、0 -目前可用的设备目前可用的设备C台时数最多可生产甲产品台时数最多可生产甲产品80Kg。取最小值即取最小值即非基变量非基变量x1增加的上界是增加的上界是80 -最小比值规则。此时最小比值规则。此时x2=0。第四步、第四步、确定新解：将确定新解：将x1=80，x2=0 代入约束方程组中求出代入约束方程组中求出x3、x4、x5的值。的值。得新基本可行解为：得新基本可行解为：X X(2)=(2)=（x1,x2,x3,x4,x5）T T=（80,0,300,50,0）T T 甲甲 乙乙 设备设备A A 设备设备B B 设备设备C C 空闲工时空闲工时(对应点对应点a)Z Z(2)=(2)=5600，

36、利润为利润为5600 (x2、x5 为非为非基变量，基变量，x1、x3、x4为为基变量基变量)Max Z=70 x130 x2s.t.3x1+9x2+x3 =540 5x1+5x2 +x4 =450 9x1+3x2 +x5=720 xj 0，j=1,5；x3,x4,x5为基变为基变量量oX1X2ahbk20第五步、第五步、判断判断X X(2)(2)是否最优：检查用非是否最优：检查用非基变量表达的目标函数中基变量表达的目标函数中非非基变量前的系数基变量前的系数(叫检验数叫检验数)。Max Z =70 x1 +30 x2=7080-(1/3)x2-(1/9)x5 +30 x2=5600 +(20/

37、3)x2 -(70/9)x5 因为因为检验数检验数 20/3 0，所以当，所以当 x2 从从0增大时，增大时，Z也会增大。也会增大。故故当前解非最优。当前解须改进，寻求更好的解。当前解非最优。当前解须改进，寻求更好的解。第六步、第六步、确定改进的非基变量及其上界确定改进的非基变量及其上界:选择使目标选择使目标Z值改变得最快的值改变得最快的非基变量优先改进。非基变量优先改进。(1)、确定非确定非基变量基变量 x2 改进：因为目标函数改进：因为目标函数中只有一个正中只有一个正检验数检验数。(2)、x2增加的上界是增加的上界是15：因为从约束方程组因为从约束方程组可以得出可以得出(从资源最优利用考虑

38、，令从资源最优利用考虑，令x3、x4 、x5=0)x2 =60 -(1/3)x1-(1/9)x3=60-(1/3)x1 x2 =37.5 x2 =90 -x1 -x4=90 -x1 x2 =15 x2 =240-3x1 -(1/3)x5=240-3x1 x1=80-(1/3)x2代入上面二式代入上面二式 取前二式的最小值即取前二式的最小值即非基变量非基变量x2增加的上界是增加的上界是15 -最小比值规则。此时最小比值规则。此时x1=75。Max Z=70 x130 x2s.t.3x1+9x2+x3 =540 5x1+5x2 +x4 =450 9x1+3x2 +x5=720 xj 0，j=1,5

39、；x3,x4,x5为基变为基变量量oX1X2ahbk21第七步、第七步、确定新解：将确定新解：将x1=75，x2=15 代入约束方程组中求出代入约束方程组中求出x3、x4、x5的值。的值。得新基本可行解为：得新基本可行解为：X(3)=（x1,x2,x3,x4,x5）T=（75,15,180,0,0）T 甲甲 乙乙 设备设备A A 设备设备B B 设备设备C C 空闲工时空闲工时 Z(3)=5700，利润为利润为5700 (x4、x5 为非为非基变量，基变量，x1、x2、x3为为基变量基变量)(对应点对应点h)第八步、第八步、判断判断X X(3)(3)是否最优：检查用非是否最优：检查用非基变量表

40、达的目标函数中基变量表达的目标函数中非非基变量前的系数基变量前的系数(叫检验数叫检验数)。Max Z =70 x1 +30 x2=5700 -2x4 -(20/3)x5 由由 5x1+5x2 +x4 =450 9x1+3x2 +x5=720 解解得得 x1=75+(1/10)x4-(1/6)x5，x2=15-(3/10)x4+(1/6)x5，代入，代入目标函数中得目标函数中得 Max Z =70 x1 +30 x2=7075+(1/10)x4-(1/6)x5 +3015-(3/10)x4+(1/6)x5 =5700 -2x4 -(20/3)x5 因为因为检验数检验数 -2、-20/3 0，原最优解基将发生变化，原最优解基将发生变化，原最优解不再是最优解，只须在原最优表上继续用单纯形法求新的最优解。原最优解不再是最优解，只须在原最优表上继续用单纯形法求新的最优解。此时原最优表变为：此时原最优表变为：39基基x1x2x3x4x5b x3001-12/51180 x20103/10-1/615x1100-1/101/675-Z0 0001-35/3-795050 x30810-1/3300 x4010/301-5/950 x111/3001/980-Z0 0-10/300-100/9-5840原最优解变为：原最优解变为：X*=(80，0，300，50，0)T Z*=584040