第一章：线性规划基础

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

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

3、使单纯形法处理大规模年，世界上第一台计算机问世，使单纯形法处理大规模L.P.L.P.数模成为可能。数模成为可能。三、三、 L.P.L.P.问题的求解过程问题的求解过程 1 1、将实际问题转化为数学模型、将实际问题转化为数学模型( (数学公式数学公式) )：建模。：建模。 2 2、求解数学模型：、求解数学模型： 图解法：图解法： 适合于适合于 2 2 个变量的个变量的 L.P. L.P. 数学模型。数学模型。 单纯形法：适合于任意个变量的单纯形法：适合于任意个变量的 L.P. L.P. 数学模型。数学模型。 3 3、利用数学模型的最优解获得原问题的最优决策方案。、利用数学模型的最优解获得原问题的

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

5、束约束 5x1 + 5x2 450 B 设备设备可用工时可用工时约束约束 9x1 + 3x2 720 C 设备设备可用工时可用工时约束约束 x1 , x2 0 非负约束非负约束 设备设备产品产品 ABC利润利润(元元/吨吨) 甲甲 (x1吨吨)乙乙 (x2吨吨)3955937030限制工时限制工时 5404507203二二、L.P.L.P.数学模型的经济含义数学模型的经济含义1 、数学模型的三要素、数学模型的三要素: .有一组待确定的决策变量。如有一组待确定的决策变量。如(x1, x2)为一个具体行动方案。为一个具体行动方案。 .有一个明确的目标要求有一个明确的目标要求(Max或或Min)。如

6、要求利润最大。如要求利润最大。 .存在一组约束条件。如设备存在一组约束条件。如设备A、B、C三种资源的约束。三种资源的约束。 2 、数学模型中系数的含义、数学模型中系数的含义: .目标函数中决策变量的系数目标函数中决策变量的系数70,30 - 叫价值系数，表单位产品提供的利润叫价值系数，表单位产品提供的利润(元元/件件)； .约束条件左边决策变量的系数约束条件左边决策变量的系数 - 叫约束条件系数或单耗叫约束条件系数或单耗(台时、台时、kg 、kg/件件)； .约束条件右边常数约束条件右边常数540,450,720 - 叫限制常数，表现有的资源限量。叫限制常数，表现有的资源限量。 三、线性规划

7、数学模型的解三、线性规划数学模型的解 1、可行解：满足约束条件、可行解：满足约束条件、的所有解。的所有解。 2、可行解域：所有可行解的集合，上图阴影部分。、可行解域：所有可行解的集合，上图阴影部分。 3、最优解：满足目标函数、最优解：满足目标函数的可行解。的可行解。 4、基本解：所有约束条件直线的交点对应的解，、基本解：所有约束条件直线的交点对应的解， 即上图所有的实心点和空心点对应的解。即上图所有的实心点和空心点对应的解。 5、基本可行解：位于可行解域边界上的约束条件、基本可行解：位于可行解域边界上的约束条件 直线的交点对应的解，即上图所有的实心点直线的交点对应的解，即上图所有的实心点 对应

8、的解。对应的解。它满足两个它满足两个条件：条件： 其一是约束条件直线的交点对应的解；其一是约束条件直线的交点对应的解； 其二是可行解，即满足所有的约束条件，其二是可行解，即满足所有的约束条件， 在可行解域内。在可行解域内。 oX1X2ahbkMax Z = 70 x130 x2 s.t. 3x1 + 9x2 540 5x1 + 5x2 450 9x1 + 3x2 720 x1 , x2 0 4 1 、线性规划：线性规划： 如果以上数学模型中的方程均是线性方程，如果以上数学模型中的方程均是线性方程， 则该数模对应的原问题称为线性规划。则该数模对应的原问题称为线性规划。 2 、非线性规划：如果以上

9、数学模型中的方程至少有一个方程是非线性方程，非线性规划：如果以上数学模型中的方程至少有一个方程是非线性方程， 则该数模对应的原问题称为非线性规划。则该数模对应的原问题称为非线性规划。 四四、L.P. L.P. 的一般形式的一般形式 Max(Min) Z = c1 x1 + c2 x2 + - + cn xn a11 x1 + a12 x2 + - + a1n xn (, =) b1 a21 x1 + a22 x2 + - + a2n xn (, =) b2s.t. - - - am1 x1 + am2 x2 + - + amn xn (, =) bm xj 0 , j=1, , n 51.3

10、1.3 线性规划问题的建模线性规划问题的建模 确定决策变量；确定目标函数；列出约束条件。确定决策变量；确定目标函数；列出约束条件。 一、运输问题建模一、运输问题建模: : 编制最优运输计划编制最优运输计划, , 使总运费最少使总运费最少 例：某地有三个有色金属矿例：某地有三个有色金属矿A1A1、A2A2、A3A3，生产同一种金属矿石，生产同一种金属矿石，A1A1矿的年产量为矿的年产量为100100万吨，万吨， A2A2矿为矿为8080万吨，万吨，A3A3矿为矿为5050万吨。矿石全部供应四个冶炼厂，万吨。矿石全部供应四个冶炼厂，B1B1厂的全部需求量为厂的全部需求量为5050万吨，万吨， B2

11、B2厂厂7070为万吨，为万吨，B3B3厂为厂为8080万吨，万吨，B4B4厂为厂为3030万吨。产量恰好等于总需求量，矿石由各矿山万吨。产量恰好等于总需求量，矿石由各矿山 运到冶炼厂的单位运价已知，如下表。问如何安排运输，使各矿山的矿石运到冶炼厂，运到冶炼厂的单位运价已知，如下表。问如何安排运输，使各矿山的矿石运到冶炼厂， 满足各厂的需要，且运输费用最小，满足各厂的需要，且运输费用最小，试建立该问题的数学模型试建立该问题的数学模型？ 表1.3 运 价 表冶 炼 厂矿 山B1B2B3B4产 量(万 t )A 1X11 1.5X122X130.3X143100A 2X217X220.8X231.

12、4X24280A 3X311.2X320.3X332X342.550需 要 量(万 t )50708030230.确定决策变量确定决策变量: 设设 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 =

13、 100 s.t. 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 xij 0 , i=13; j=14.6 二、人员分派问题建模二、人员分派问题建模: : 合理分派人员合理分派人员, , 使总效率最大使总效率最大. . 例：例：设有四件工作分派给四个人来做，每项工作只能由一人来做，每个人只能做一项工作。设有四件工作分派给四个人来做，每项工作只能由一人来做，每个人只能做

14、一项工作。 希望适当安排人选，发挥各人特长又能使总的效率最大希望适当安排人选，发挥各人特长又能使总的效率最大( (或完成最快或完成最快, ,或费用最少或费用最少) )。 表表1.51.5表示各人对各项工作所具有的工作效率。表示各人对各项工作所具有的工作效率。 表1.5 效率表工作 人员ABCD甲X11 0.6X120.2X130.3X140.1乙X210.7X220.4X230.3X240.2丙X310.8X321.0X330.7X340.3丁X410.7X420.7X430.5X440.4.确定决策变量确定决策变量: 设设 xij 为分派第为分派第 i 个人从事第个人从事第 j 项工作项工作

15、, xij = 1, 0 (分派与否分派与否).确定目标确定目标函数函数: 设总效率为设总效率为Z, 则则 Max Z = 0.6x11 + 0.2x12 + 0.3x13 + 0.1x14 + 0.7x21 + 0.4x22 + 0.3x23 + 0.2x24 + 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 =

16、 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 三、合理下料问题建模三、合理下料问题建模: :寻求最佳下料方式寻求最佳下料方式, , 使余料最少使余料最少. . 例例 有一批长度为有一批长度为180180公分的钢管公分的钢管, ,需截成需截成7070、5252和和3535公分三种管料。它们的需求量应分别不少于公分三种管料。它们的需

17、求量应分别不少于 100100、150150和和100100个。问应如何下料才能使钢管的余料为最少个。问应如何下料才能使钢管的余料为最少? ? 解解: :.确定决策变量确定决策变量: 设设 xj 为第为第 j 种下料方式所用种下料方式所用的钢管根数的钢管根数.确定目标确定目标函数函数: 设总余料为设总余料为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

18、+ x3 + 3x4 + 2x6 + 3x7 + 5x8 100 xj 0 , 且为整数且为整数. 管料 尺寸下料 方式70公分52公分35公分余料(公分)一 (x1 根)二 (x2 根)三 (x3 根)四 (x4 根)五 (x5 根)六 (x6 根)七 (x7 根)八 (x8 根)21110000021032101013023556235246235管料需求数(个)1001501008 四、投资方案选择问题建模四、投资方案选择问题建模: : 合理选择方案合理选择方案, , 使总收益最大使总收益最大. . 例：例：某炼油公司为提高炼油能力和增加企业经济效益某炼油公司为提高炼油能力和增加企业经济

19、效益,经研究有五种技术改造的投资方案可供选择，经研究有五种技术改造的投资方案可供选择， 它们所需的投资费用年收益如下表所示它们所需的投资费用年收益如下表所示。其中其中: 方案方案1和方案和方案2只能选择其中一种，不能兼而实现，只能选择其中一种，不能兼而实现， 并且，如选择方案并且，如选择方案2，则方案，则方案3必须同时选择，或者都不选择必须同时选择，或者都不选择。 现该公司可供支配的资金总额为：第一年有现该公司可供支配的资金总额为：第一年有650万元，第二年仅有万元，第二年仅有460万元万元。技术改造的结果。技术改造的结果 要求至少应增加出油能力要求至少应增加出油能力500500桶桶/ /天，

20、但又不得超过天，但又不得超过11001100桶桶/ /天，试确定该公司总经济效益最大的天，试确定该公司总经济效益最大的 投资方案。投资方案。表 1.5 投资方案内容投资（万元）方案序号技改方案内容决策变量第一年第二年年收益（万元）1更新旧装置，提高炼油能力 500 桶/天X12002001002建 造 新 装 置 ， 提 高 炼 油 能 力1000桶/天X23001502003往新 厂建 输油 管,提高 炼油能力 100桶/天X315050504往老厂建输油管，提高炼油能力 50桶/天X410070305增加槽车运输能力，能提高出油 20桶/天X55040209投资（万元）资源方案技改后提高出

21、油能力(桶/天)第一年第二年年收益（万元）一 (x1)500200200100二 (x2)1000300150200三 (x3)1001505050四 (x4)501007030五 (x5)20504020资源限额500 1100650460.确定决策变量确定决策变量: 设设 xj 为第为第 j 方案的取舍，方案的取舍， xj = 1, 0 (取舍取舍).确定目标确定目标函数函数: 设总经济效率为设总经济效率为Z, 则则 Max Z = 100 x1 + 200 x2 + 50 x3 + 30 x4 + 20 x5 (万元万元) .确定约束条件确定约束条件: 200 x1 + 300 x2 +

22、 150 x3 + 100 x4 + 50 x5 650 s.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.101.4 1.4 线性规划图解法线性规划图解法 一、一、适用范围：适用范围： 二个变量的数学模型。二个变量的数学模型。 二、二、求解步骤：求解步骤： Max Z = 70 x13

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

24、约束方程用图形绘出；第一步：将所有约束方程用图形绘出； 第四步：第四步：目标函数直线沿着方向目标函数直线沿着方向P P向可行解域的边界平行移动，直至与可行解域第一次相切为止，向可行解域的边界平行移动，直至与可行解域第一次相切为止， 这个切点就是最优点，对应的解就是最优解。这个切点就是最优点，对应的解就是最优解。 11 三、三、LPLP几何意义几何意义 oX1X2ahbk 1、闭合的可行解域是凸多边形、闭合的可行解域是凸多边形(凸集凸集)。 2、可行解域有若干个顶点：、可行解域有若干个顶点：O、a、h、k、b。 对应的解叫基本对应的解叫基本可行可行解解。 3、最优解若唯一存在，则必是顶点中的某一

25、个。、最优解若唯一存在，则必是顶点中的某一个。 四、特殊的数学模型四、特殊的数学模型 1、有无穷多个最优解：若有两个最优解，则必有无穷多个最优解。、有无穷多个最优解：若有两个最优解，则必有无穷多个最优解。 2、解无界：可行解域无界，目标值无限增大。、解无界：可行解域无界，目标值无限增大。 3、无可行解域：约束条件相互矛盾。、无可行解域：约束条件相互矛盾。121.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 13 三、三、LPLP数模的标准型数模的标准型 条件一条件一: :具有等式约束方程组；具有等式约束方程组； 条件二条件二: :右边常数非负；右边常数非负； 条件三条件三: :变量非负；变量非负； 条件四条件四: :目标函数为目标函数为MaxMax

27、型。型。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

28、.t. 3x1 + 9x2 + x3 = 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) 限制工时限制工时 工时数工时数 ( (起松弛作用起松弛作用, ,叫松弛变量叫松弛变量) )

29、 对设备对设备C C：9x9x1 1 + 3x + 3x2 2 720 720 ，引入非负松弛变量，引入非负松弛变量x x4 4，加到不等式的左边得，加到不等式的左边得 9x9x1 1 + 3x + 3x2 2 + + x x5 5 = 720= 720 实际使用的实际使用的 空闲工时空闲工时( (0) 0) 限制工时限制工时 工时数工时数 ( (起松弛作用起松弛作用, ,叫松弛变量叫松弛变量) ) 14 四、四、LPLP数模的规范型数模的规范型 条件一条件一: : 具有具有标准型标准型； 条件二条件二: : 约束方程组系数矩阵中含有至少一个单位约束方程组系数矩阵中含有至少一个单位 子矩阵子矩

30、阵( (对应的变量叫基变量对应的变量叫基变量) ) ； 条件三条件三: : 目标函数中不含基变量。目标函数中不含基变量。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为基变量为基变量 则原数模的规范型为：则原数模的规范型为：Max Z = 70 x130 x2s.t. 3x1 + 9x2 + x3 = 540 5x1 + 5x2 + x4 = 450 9x1 + 3x2 + x5 = 720 xj 0，j=1, ,5 x

31、3 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 一组一组基基 1 1 2 2 3 3 4 4 5 5 x1 x2 x3 x4 x5 非基变量非基变量 基变量基变量 基的作用是：可得到初始基本可行解基的作用是：可得到初始基本可行解( (即初始顶点即初始顶点 - - 通常是原点通常是原点O),O),是单纯行迭代的基础。是单纯行迭代的基础。15

32、五、最优解寻求步骤五、最优解寻求步骤第一步、第一步、确定初始基本可行解：利用确定初始基本可行解：利用规范型数模，令规范型数模，令非基变量非基变量 x1 、x2 = 0，求出，求出基变量基变量x3 、 x4 、 x5。 得初始基本可行解为：得初始基本可行解为： X X(1) =(1) =（ x1 , x2 , x3 , x4 , x5 ）T T = ( = ( 0 , 0 , 540 , 450 , 720 ) )T T 甲甲 乙乙 设备设备A A 设备设备B B 设备设备C C 空闲工时空闲工时 Z Z(1) = (1) = 0 ，利润为利润为0 未生产，资源全部闲置未生产，资源全部闲置 (对

33、应原点对应原点O) (x1、 x2 为非为非基变量，基变量，x3、x4、x5为为基变量基变量) 第二步、第二步、判断判断X X(1)(1)是否最优：检查用非是否最优：检查用非基变量表达的目标函数中基变量表达的目标函数中非非基变量前的系数基变量前的系数( (叫检验数叫检验数) )。 Max Z = 70 x1 + 30 x2 因为因为检验数检验数 70、30 0，所以当，所以当 x1 和和 x2从从0增大时，增大时， Z也会增大。也会增大。 故故当前解非最优。当前解须改进，寻求更好的解。当前解非最优。当前解须改进，寻求更好的解。oX1X2ahbkMax Z = 70 x130 x2s.t. 3x

34、1 + 9x2 + x3 = 540 5x1 + 5x2 + x4 = 450 9x1 + 3x2 + x5 = 720 xj 0，j=1, ,5； x3 ,x4 , x5为基变量为基变量16第三步、第三步、确定改进的非基变量及其上界确定改进的非基变量及其上界: : 选择使目标选择使目标Z值改变得最快的值改变得最快的 非基变量优先改进。非基变量优先改进。 (1)、确定非基变量确定非基变量 x1 优先改进：因为从目标函数优先改进：因为从目标函数 Max Z = 70 x1 + 30 x2 可以看出可以看出 x1增加增加1，可使目标，可使目标Z增加增加70； x2增加增加1，目标，目标Z能增加能增

35、加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 = 80 - 目前可用的设备目前可用的设备C台时数

36、最多可生产甲产品台时数最多可生产甲产品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

37、(2) = (2) = 5600，利润为利润为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为基变量为基变量oX1X2ahbk17第五步、第五步、判断判断X X(2)(2)是否最优：检查用非是否最优：检查用非基变量表达的目标函数中基变量表达的目标函数中非非基变量前的系数基变量前的系数( (叫检验数叫检验数) )。 Max Z = 70 x

38、1 + 30 x2 = 7080-(1/3)x2-(1/9)x5 + 30 x2 = 5600 + (20/3)x2 - (70/9) x5 因为因为检验数检验数 20/3 0，所以当，所以当 x2 从从0增大时，增大时， Z也会增大。也会增大。 故故当前解非最优。当前解须改进，寻求更好的解。当前解非最优。当前解须改进，寻求更好的解。第六步、第六步、确定改进的非基变量及其上界确定改进的非基变量及其上界: :选择使目标选择使目标Z值改变得最快的值改变得最快的非基变量优先改进。非基变量优先改进。 (1)、确定非确定非基变量基变量 x2 改进：因为目标函数改进：因为目标函数中只有一个正中只有一个正检

39、验数检验数。 (2)、 x2增加的上界是增加的上界是15：因为从约束方程组因为从约束方程组可以得出可以得出 (从资源最优利用考虑，令从资源最优利用考虑，令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 - 最小比值

40、规则。此时最小比值规则。此时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； x3 ,x4 , x5为基变量为基变量oX1X2ahbk18第七步、第七步、确定新解：将确定新解：将x1=75， x2=15 代入约束方程组中求出代入约束方程组中求出x3 、 x4 、 x5的值。的值。 得新基本可行解为：得新基本可行解为： X(3) =（ x1 , x2 , x3 , x4 , x5 ）T = （75 , 15 , 180 , 0 , 0

41、）T 甲甲 乙乙 设备设备A A 设备设备B B 设备设备C C 空闲工时空闲工时 Z(3) = 5700 ，利润为利润为5700 (x4、 x5 为非为非基变量，基变量，x1、x2、x3为为基变量基变量) (对应点对应点h)第八步、第八步、判断判断X X(3)(3)是否最优：检查用非是否最优：检查用非基变量表达的目标函数中基变量表达的目标函数中非非基变量前的系数基变量前的系数( (叫检验数叫检验数) )。 Max Z = 70 x1 + 30 x2 = 5700 - 2x4 - (20/3) x5 由由 5x1 + 5x2 + x4 = 450 9x1 + 3x2 + x5 = 720 解得

42、解得 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 ， j=16解：S.T.系数矩阵 x1 x3 x6 1 2 0 -2 0 0 1 0 0 A = 0 1 1 -1 2 0 中有单位矩阵 B = 0 1 0 0 2 0 1 3 1 0 0 1所以所以x1

43、、 x3、x6 为基变量。用非基变量表达目标函数：为基变量。用非基变量表达目标函数：将将 x1 = 5 - 2x2 + 2x4 x3 = 6 - x2 + x4 - 2 x5 代入代入目标函数中得：目标函数中得：Min Z = 2 (5 - 2x2 + 2x4) - x2 - (6 - x2 + x4 - 2 x5) - 3 x5 = 11 - 4 = 11 - 4x2 + 3x4 - 5 x5 令令 Z = - D，原原目标函数等价于：目标函数等价于： Max D = - 11 + 411 + 4x2 - 3x4 + 5 x5 从而原数模的规范型数模为：从而原数模的规范型数模为：Max D

44、= - 11 + 4x2 - 3x4 + 5 x5 x1 + 2x2 - 2x4 = 5 x2 + x3 - x4 + 2 x5 = 6s.t. 2x2 + x4 + 3x5 + x6 = 8 xj =0 ， j=16， x1 、 x3、 x6 为基变量。26解：用单纯形表迭代计算如下解：用单纯形表迭代计算如下基基x1x2x3x4x5x6b x1120-2005-x3011-12063x602013188/3-D040-35011基本可行解基本可行解X(1) = (5,0,6,0,0,8)TD(1) = -11x1120-20055/2x30-1/31-5/30-2/32/3-x502/301

45、/311/38/34-D02/30-14/30-5/3-7/3X(2) = (5,0,2/3,0,8/3,0)TD(2) = 7/3x21/210-1 005/2x31/601-2 0-2/33/2x5-1/3001 11/31-D-1/300-4 0 -5/3-4X(3) = (0,5/2,3/2,0,1,0)TD(3) = 4X* = (0，5/2，3/2，0，1，0)TZ = - D(3) = - 427 八、八、单纯形的理论分析单纯形的理论分析 1 1、L.P.L.P.数模的标准型数模的标准型 一般式：一般式： 求和式：求和式： Max Z = c1 x1 + c2 x2 + - +

46、cn xn a11 x1 + a12 x2 + - + a1n xn = b1 a21 x1 + a22 x2 + - + a2n xn = b2s.t. - am1 x1 + am2 x2 + - + amn xn = bm xj 0 , j=1, , n jnjjxcZMax 1 njxmibxctsjijnjij, 1, 0, 1,.128 向量式：向量式： 矩阵式：矩阵式： C = (c1，c2，- ，cn)X = (x1，x2，- ，xn)T a1j b1j = a2j , j=1n ; b= b2 - - amj bm a11 a12 - a1nA = a21 a22 - a2n

47、= (1, 2,-, n ) - am1 am2 - amnXCZMax njxbxtsjjnjj, 1, 0.1 XCZMax 0.XbXAts292 2、L.P.L.P.数模的规范型数模的规范型 s.t. 方程组中含一组基：方程组中含一组基：XB = (x1， x2，-， xm)T x1 + a1,m+1 xm+1 + - + a1n xn = b1 x2 + a2,m+1 xm+1 + - + a2,n xn = b2 s.t. xm + am,m+1 xm+1 + - + am,n xn = bm 目标函数中不含基变量目标函数中不含基变量 x1， x2，-， xm ： mixabxjn

48、mjijii, 1,1 jnjjxcZMax 1jnmjjimiixcxc 11jnmjjjnmjijimiixcxabc 111jnmjijmiijimiixaccbc 111jnmjjjxZcZ 10jnmjjxRZ 10imiibcZ 10:其其中中 mmbbcc11),(为为目目标标初初值值bCB jjjZcR ijmiijacc 1 mjjmjaaccc11),(为为检检验验数数jBjCc 303 3、L.P.L.P.数模的单纯形表数模的单纯形表 Max Z = c1x1 + c2 x2 + +cn xn x1 + a1,m+1 xm+1 + - + a1n xn = b1 x2 +

49、 a2,m+1 xm+1 + - + a2,n xn = b2 s.t. - xm + am,m+1 xm+1 + - + am,n xn = bm xj 0 ， j=1m 基X 1X LX mX m+1X pX nbX 1100a1,m+1a1,pa1,nb11 X L010a L,m+1a L pa L,nb LLX m001am,m+1am,pam,nbmmZ000Rm+1RpRn-Z031 4 4、单纯形法求解步骤、单纯形法求解步骤 第一步：将原问题的数学模型化为规范型，列出初始单纯形表。第一步：将原问题的数学模型化为规范型，列出初始单纯形表。 第二步：确定入基变量：选择最大的正检验数

50、对应的非基变量入基。第二步：确定入基变量：选择最大的正检验数对应的非基变量入基。 第三步：确定出基变量：选择最小的正第三步：确定出基变量：选择最小的正 比值比值对应的基变量出基。对应的基变量出基。 第四步：确定主元素：入基列和出基行的交叉元素为主元素。第四步：确定主元素：入基列和出基行的交叉元素为主元素。 第五步：以元素为中心进行旋转运算第五步：以元素为中心进行旋转运算(即将入基列变为单位向量列即将入基列变为单位向量列)，得一新表。，得一新表。 第六步：重复以上步骤直至最优表。第六步：重复以上步骤直至最优表。321.6 1.6 人造基下的单纯形法人造基下的单纯形法 - - 两阶段法和大两阶段法

51、和大M M法法 一、一、什么时候会出现人造基什么时候会出现人造基 例：求解下列数模例：求解下列数模 Min Z = x12x2 s.t. x1 + x2 2 -x1 + x2 1 x2 3 x1 , x2 0 当数模的约束条件出现当数模的约束条件出现”或或”时，要将数模化为规范型，时，要将数模化为规范型， 一般情况下就需要引入人工变量形成人造基。一般情况下就需要引入人工变量形成人造基。 标准化：引入非负松弛变量标准化：引入非负松弛变量 x3、 x4、 x5 令令Z = -D , 化成标准型如下化成标准型如下 Max D = -x1 + 2 2x2 s.t. x1 + x2 - x3 = 2 -

52、x1 + x2 - x4 = 1 x2 + x5 = 3 xj 0 ，j=15 规范化：引入非负人工变量规范化：引入非负人工变量 x6、 x7 化成规范型如下化成规范型如下 Max D = -x1 + 2 2x2 s.t. x1 + x2 - x3 + x6 = 2 - x1 + x2 - x4 + x7 = 1 x2 + x5 = 3 xj 0 ，j=17， x5,x6,x7为基变量为基变量规范型解基的形成只要三种可能：规范型解基的形成只要三种可能： 由决策变量自然形成的解基：由决策变量自然形成的解基： 由具体的物理变量组成，可含在最优解里，由具体的物理变量组成，可含在最优解里， 由添加松弛

53、变量形成的解基：由添加松弛变量形成的解基： 每步迭代后的解均是可行解。每步迭代后的解均是可行解。 由由引入人工变量引入人工变量形成的解基形成的解基(人造基人造基)：由虚拟：由虚拟人工变量组成，改变了原人工变量组成，改变了原s.t. 。33 二、二、两阶段法两阶段法例：求解下列数模例：求解下列数模 Min Z = x12x2 s.t. x1 + x2 2 -x1 + x2 1 x2 3 x1 , x2 0 -1o123x1-2-1123x2 abch 规范化：引入非负松弛变量规范化：引入非负松弛变量 x3、 x4、 x5 和非负人工变量和非负人工变量 x6、 x7 化成规范型如下化成规范型如下

54、Max D = -x1 + 2 2x2 s.t. x1 + x2 - x3 + x6 = 2 - x1 + x2 - x4 + x7 = 1 x2 + x5 = 3 xj 0 ，j=17， x5,x6,x7为基变量为基变量 引入新目标函数引入新目标函数 Min W = x6 + x7 = 3 - 2x2 + x3 + x4 , ，令令 W = - G ，规范化得：规范化得： Max G = - 3 + 2x2 - x3 - x4 第一阶段：通过单纯形迭代，将第一阶段：通过单纯形迭代，将人工变量人工变量 x6、 x7从基中置换出来使其取值从基中置换出来使其取值0，并得初始基本可行解。，并得初始基

55、本可行解。 若若人工变量无法全部出基，则原问题无解；人工变量无法全部出基，则原问题无解；若若人工变量无法全部出基，但取值为人工变量无法全部出基，但取值为0，则原，则原 问题有多余约束条件，去除多余约束条件再求解。问题有多余约束条件，去除多余约束条件再求解。第二阶段：通过单纯形迭代，求出最优解。第二阶段：通过单纯形迭代，求出最优解。34不可行解不可行解 基X 1X 2X 3X 4X 5X 6X 7bX 611-1001022X 7-110-100111X 5010010033D-12000000G02-1-10003X 620-1101-111/2X 2-110-10011-X 5100110-

56、122D100200-2-2G20-1100-21X110-1/21/201/2-1/21/21X 201-1/2-1/201/21/23/2-X 5001/21/21-1/2-1/23/23D001/23/20-1/2-3/2-5/2G00000-1-10X420-1101-X 211-1002-X 5-1010111D-30200- 4X4100112X 2010013X 3-101011D-1000-2- 6X(1) = (0，0，0，0，3，2，1)TD(1) = 0 (对应对应O点点)G(1) = - 3X(2) = (0，1，0，0，2，1，0)TD(2) = 2 (对应对应a点点)G(2) = - 1 初始基本可行解初始基本可行解X(3) = (1/2，3/2，0，0，3/2，0，0)TD(3) = 5/2 (对应对应b点点)G(3) = - 0X(4) = (0，2，0，1，1)TD(4) = 4 (对应对应C点点)X(5) = (0，3，1，2，0)TD(5) = 6 (对应对应h点点)X* = (0，3，1，2，0)TZ* = -D(5) = - 635 两阶段法的作用两阶段法的作用例：求解下列数模例：