运筹学-第2讲

1、2022-5-61线性规划与目标规划线性规划与目标规划2022-5-62目目 录录1.1.线性规划与单纯形法线性规划与单纯形法2.2.对偶理论和灵敏度分析对偶理论和灵敏度分析3.3.运输问题运输问题4.4.目标规划目标规划2022-5-63q线性规划(Linear Programming)是运筹学的一个重要分支。q线性规划在理论上比较成熟，在实用中的应用日益广泛与深入。它已是现代科学管理的重要手段之一。q线性规划最常用的求解方法 单纯形法单纯形法(Simplex Method) 由丹捷格(G B Dantzig)提出(1947年)。线性规划问题及其数学模型线性规划问题及其数学模型2022-5-

2、64线性规划问题及其数学模型线性规划问题及其数学模型 1.1 1.1 问题的提出问题的提出例例1 1 生产计划 某工厂在计划期内要安排生产、两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如表所示。问题：工厂应分别生产多少单位甲、乙产品才能使工厂获利最多？ 如何用数学关系式描述这个问题？如何用数学关系式描述这个问题？2022-5-65线性规划问题及其数学模型线性规划问题及其数学模型q设x1 ，x2 分别表示计划生产I，II产品的数量，称它们为决策变量决策变量。q生产x1 ，x2 的多少，受到资源拥有量的限制，即存在约约束条件束条件。 x1 +2x2 84 x1 164 x2

3、12q生产的产品不能是负值： x1 ，x2 0。q如何安排生产，使得利润最大，这是目标函数目标函数。max z = 2 x1 + 3 x22022-5-66线性规划问题及其数学模型线性规划问题及其数学模型q因此该问题的数学模型为：因此该问题的数学模型为： ( 设生产甲产品 x1 个单位、生产乙产品 x2 个单位)q目标函数目标函数: max z = 2 x1 + 3 x2q约束条件约束条件: x1 +2x2 84 x1 164 x2 12 x1 ，x2 0q这种模型实际上是一种约束限制下的最优线性数学模型，称为线性规划。2022-5-67线性规划问题及其数学模型线性规划问题及其数学模型q例例2

4、 2 简化的环境保护问题 靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万立方米，在两个工厂之间有一条流量为每天200万立方米的支流。q 第一化工厂每天排放含有某种有害物质的工业污水2万立方米，第二化工厂每天排放这种工业污水1.4万立方米。q 从第一化工厂排出的工业污水流到第二化工厂以前，有20%可自然净化。根据环保要求，河流中工业污水的含量应不大于0.2%。这两个工厂都需各自处理一部分工业污水。第一化工厂处理工业污水的成本是1000元/万立方米。第二化工厂处理工业污水的成本是800元/万立方米。q 现在问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工现在问在满足环

5、保要求的条件下，每厂各应处理多少工业污水，使这两个工厂总的处理工业污水费用最小。厂总的处理工业污水费用最小。2022-5-68线性规划问题及其数学模型线性规划问题及其数学模型q 建模型之前的分析和计算建模型之前的分析和计算q 设设：第一化工厂每天处理工业污水量为x1 万立方米，第二化工厂每天处理工业污水量为x2 万立方米。112(2)250010000.8(2)(1.4)27001000 xxx经第二工厂前的水质要求：经第二工厂后的水质要求：此问题的线性规划模型此问题的线性规划模型： 目标函数目标函数：max z = 1000 x1 + 800 x2 约束条件约束条件：s.t. x1 1 0.

6、8x1 + x2 1.6 x1 2 x2 1.4 x1 , x2 02022-5-69线性规划问题及其数学模型线性规划问题及其数学模型q 从以上两例可以看出，其共同特征：从以上两例可以看出，其共同特征：(1) 每一个线性规划问题都用一组决策变量决策变量 表示某一方案，这组决策变量的值就代表一个具体方案，一般这些变量取值是非负且连续的；(2) 存在有关的数据，同决策变量构成互不矛盾的约束条件约束条件，这些约束条件可以用一组线性等式或线性不等式来表示； (3) 存在一个要求达到的目标，它可用决策变量及其有关的价值系数构成的的线性函数(称为目标函数目标函数)来表示。按问题的不同，要求目标函数实现最大

7、化或最小化。 满足以上三个条件的数学模型称为线性规划线性规划的数学模型。nx,x ,x212022-5-610线性规划问题及其数学模型线性规划问题及其数学模型q线性规划问题是线性规划问题是在一组线性等式或不等式的约束之下，求一在一组线性等式或不等式的约束之下，求一个线性函数的最大值或最小值的问题。个线性函数的最大值或最小值的问题。q它由以下部分它由以下部分组成：组成： 目标函数目标函数 max z 或或 min f 约束条件约束条件 s. t. (subject to) 满足于满足于 决策变量决策变量 用符号用符号 xj 等来表示可控制的因素。等来表示可控制的因素。2022-5-611线性规划

8、问题及其数学模型线性规划问题及其数学模型q线性规划模型的一般形式线性规划模型的一般形式q目标函数目标函数: max（min）z = c1 x1 + c2 x2 + + cn xn q约束条件约束条件： s. t. a11 x1 + a12 x2 + + a1n xn （ =, ）b1 a21 x1 + a22 x2 + + a2n xn （ =, ）b2 am1 x1 + am2 x2 + + amn xn （ =, ）bm x1 ，x2 ， ，xn 0 cj(j=1,2, ,n)称为价值系数价值系数； aij称为技术系数技术系数； bi称为限额系限额系数数。2022-5-612线性规划问题及

9、其数学模型线性规划问题及其数学模型1.2 图解法图解法q对于含有两个决策变量含有两个决策变量的线性规划模型，可以利用图解法(Graph Method)求解。q图解法是解线性规划的一种简便、直观的方法，对于理解线性规划的基本概念和基本原理也是很有帮助的。q定义：定义：q可行解：可行解：满足所有约束条件的向量称为线性规划问题的可行解。q可行域：可行域：全体可行解的集合称为线性规划问题的可行域。q最优解：最优解：使目标函数达到最优值的可行解，称为线性规划的最优解。2022-5-613线性规划问题及其数学模型线性规划问题及其数学模型0124164223221212121x ,xxxxxxxzmaxq例

10、1中，所有约束条件作为半平面所围成的范围如图中阴影部分所示。阴影部分中的每一个点(包括边界点)都是这个线性规划问题的可行解。q对于例1，考察其约束条件所围成的范围，作图如下：可行域可行域2022-5-614线性规划问题及其数学模型线性规划问题及其数学模型q考察目标函数 max z = 2 x1 + 3 x2q将目标函数化为点斜式坐标： x2=-(2/3) x1 +z/3表示一簇平行线33212zxx最优解最优解q由于在同一条直线上的所有点的目标函数取同样的值，故称为等值线。2022-5-615q解联立方程组: x1 + 2x2 = 8 4x1 = 16 q得最优解为： x1 = 4， x2 =

11、 2， q记为: (x1 , x2)T =(4，2)T或者q最优目标值为： z = 14。 q以上最优解和最优值说明该厂的最优生产计划方案是：生以上最优解和最优值说明该厂的最优生产计划方案是：生产产4件产品件产品I，生产，生产2件产品件产品II，可得到最大利润为，可得到最大利润为14元。元。 线性规划问题及其数学模型线性规划问题及其数学模型1242xx 2022-5-616用图解法求解线性规划的基本步骤：用图解法求解线性规划的基本步骤：q画可行域：画可行域：分别取决策变量 x1 ，x2 为坐标向量建立直角坐标系。q化目标函数等值线：化目标函数等值线：对每个不等式(约束条件)，先取其等式在坐标系

12、中作直线，然后确定不等式所决定的半平面。 若各半平面交出来的公共区域存在，显然，其中的点满足所有的约束条件，称这样的点为此线性规划的可行解，全体可行解的集合称为可行集或可行域。若这样的公共区域不存在，则该线性规划问题无可行解。q找最优解：找最优解：任意给定目标函数一个确定的值，作出对应的目标函数等值线，并确定该族等值线平行移动时目标函数值增加的方向。然后平移目标函数的等值线，使其达到既与可行域有交点又不可能使值再增加的位置(有时交于无穷远处，此时称无有限最优解）。此时，目标函数等值线与可行域的交点即此线性规划的最优解（一个或多个），此目标函数的值即最优值。线性规划问题及其数学模型线性规划问题及

13、其数学模型2022-5-617线性规划问题的解可能出现的几种情况：线性规划问题的解可能出现的几种情况：q有唯一的最优解；有唯一的最优解；q存在无穷多最优解存在无穷多最优解( (多重最优解多重最优解) )；线性规划问题及其数学模型线性规划问题及其数学模型目标函数 max z=2 x1 +4 x2 q其最优解为线段Q2Q3上的所有点，即(x1 , x2)T| x1 +2 x2=8，2 x1 42022-5-618q无界解：无界解：可行域无边界，目标函数值可增大(减小)到无穷大(无穷小)，实际上这类问题无最优解；q无可行解。无可行解。线性规划问题及其数学模型线性规划问题及其数学模型12121212m

14、ax242,0zxxxxxxx xq 在目标函数等值线向右上方移动的过程中，上端无边界，取不到最大值，即无界解。2022-5-619q无可行解：无可行解：当存在矛盾的约束条件时，可行域为空集，无可行解，故无最优解。q如果在例1的数学模型中增加一个约束条件: max z = 2 x1 + 3 x2线性规划问题及其数学模型线性规划问题及其数学模型q 可行域的交集为空集，故无可行解。85 . 121xx2022-5-620线性规划问题及其数学模型线性规划问题及其数学模型q注：注：q当线性规划问题的可行域非空时，它是有界的或无界的凸当线性规划问题的可行域非空时，它是有界的或无界的凸多边形；多边形；q若

15、线性规划问题存在最优解，则一定在有界可行域的某个若线性规划问题存在最优解，则一定在有界可行域的某个顶点得到；顶点得到；q若在两个顶点同时得到最优解，则它们连线上的任意一点若在两个顶点同时得到最优解，则它们连线上的任意一点都是最优解，即有无穷多个最优解。都是最优解，即有无穷多个最优解。2022-5-621线性规划问题及其数学模型线性规划问题及其数学模型1.3 线性规划问题的标准形式线性规划问题的标准形式q以下形式的线性规划模型称为标准形以下形式的线性规划模型称为标准形(M1)：q目标函数目标函数： max z = c1 x1 + c2 x2 + + cn xn q 约束条件约束条件： s. t.

16、 a11 x1 + a12 x2 + + a1n xn = b1 a21 x1 + a22 x2 + + a2n xn = b2 am1 x1 + am2 x2 + + amn xn= bm x1 ，x2 ， ，xn 0.均为均为求最求最大值大值均为等均为等式约束式约束均为非负均为非负决策变量决策变量右端常数右端常数项项bi 02022-5-622线性规划问题及其数学模型线性规划问题及其数学模型q线性规划的标准形式有如下四个要求：线性规划的标准形式有如下四个要求：q 目标最大化目标最大化q 约束方程为等式约束方程为等式q 决策变量为非负决策变量为非负q 右端项为非负右端项为非负2022-5-6

17、23线性规划问题及其数学模型线性规划问题及其数学模型11max,1,2,0,1,2,njjjnijjijjzc xa xbimxjn目标函数：约束条件：q线性规划问题的几种表示形式：线性规划问题的几种表示形式：qM1:qM1(向量和矩阵表示向量和矩阵表示):111122212max0,1,2,;1,2,njjjjjjnjmjnmzCXP xbxjnaxbaxbCc ccXPbjnaxb目标函数：约束条件：2022-5-624线性规划问题及其数学模型线性规划问题及其数学模型m ax.0zC XA XbX目 标 函 数 ：约 束 条 件 ：q线性规划问题的几种表示形式：线性规划问题的几种表示形式：

18、q矩阵表示矩阵表示:11112112112m12,;000,0,00(,);bb,;b,.nnmmnTnTmTnaaAP PPmnm naaCc ccb bbXxxx 系数矩阵：约束条件的维矩阵( )零向量：；目标系数：价值向量资源向量：资源向量决策变量向量：2022-5-625线性规划问题及其数学模型线性规划问题及其数学模型q化线性规划标准型的方法：化线性规划标准型的方法：q对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式:q1.极小化目标函数的问题：极小化目标函数的问题：q设目标函数为设目标函数为 min f = c1x1 + c2x2 + + cnxn (可以

19、可以)令令 z - f ， 则该极小化问题与下面的极大化问题有相同的最优解，即则该极小化问题与下面的极大化问题有相同的最优解，即 max z = - c1x1 - c2x2 - - cnxn 。 但必须注意，尽管以上两个问题的最优解相同，但他们最优解但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即的目标函数值却相差一个符号，即 min f - max z 。2022-5-626线性规划问题及其数学模型线性规划问题及其数学模型q化线性规划标准型的方法：化线性规划标准型的方法：q2. 约束条件不是等式的问题约束条件不是等式的问题： 设约束条件为设约束条件为 ai

20、1 x1 + ai2 x2 + + ain xn bi 可以引进一个新的变量可以引进一个新的变量 s ，使它等于约束右边与左边之差，使它等于约束右边与左边之差 s = bi (ai1 x1 + ai2 x2 + + ain xn ) 。 显然，显然，s 也具有非负约束，即也具有非负约束，即 s0 ，这时新的约束条件成为，这时新的约束条件成为 ai1 x1 + ai2 x2 + + ain xn + s = bi 。2022-5-627线性规划问题及其数学模型线性规划问题及其数学模型q化线性规划标准型的方法：化线性规划标准型的方法：q2. 约束条件不是等式的问题约束条件不是等式的问题： 当约束条

21、件为当约束条件为 ai1 x1+ai2 x2+ +ain xn bi 时，类似地令时，类似地令 s = (ai1 x1+ai2 x2+ +ain xn) - bi 。 显然，显然，s 也具有非负约束，即也具有非负约束，即s0，这时新的约束条件成为，这时新的约束条件成为 ai1 x1+ai2 x2+ +ain xn - s = bi 。 2022-5-628线性规划问题及其数学模型线性规划问题及其数学模型q化线性规划标准型的方法：化线性规划标准型的方法：q2. 约束条件不是等式的问题约束条件不是等式的问题：q为了使约束由不等式成为等式而引进的变量为了使约束由不等式成为等式而引进的变量s： q 当

22、不等式为当不等式为“小于等于小于等于”时称为时称为“松弛变量松弛变量”；q 当不等式为当不等式为“大于等于大于等于”时称为时称为“剩余变量剩余变量”；q 如果原问题中有若干个非等式约束，则将其转化为标准形式如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的变量，有时也将它们统称为时，必须对各个约束引进不同的变量，有时也将它们统称为松弛变量松弛变量。 2022-5-629线性规划问题及其数学模型线性规划问题及其数学模型q化线性规划标准型的方法：化线性规划标准型的方法：q2. 约束条件不是等式的问题约束条件不是等式的问题：q补例：补例：将以下线性规划问题转化为标准形式

23、将以下线性规划问题转化为标准形式 min f = 3.6 x1 - 5.2 x2 + 1.8 x3 s. t. 2.3 x1 + 5.2 x2 - 6.1 x3 15.7 4.1 x1 + 3.3 x3 8.9 x1 + x2 + x3 = 38 x1，x2，x3 0 q解：首先解：首先, 将目标函数转换成极大化：令将目标函数转换成极大化：令 z = -f = -3.6x1 + 5.2x2 - 1.8x32022-5-630线性规划问题及其数学模型线性规划问题及其数学模型q化线性规划标准型的方法：化线性规划标准型的方法：q2. 约束条件不是等式的问题约束条件不是等式的问题：q其次考虑约束，有其

24、次考虑约束，有 2 个不等式约束，引进松弛变量个不等式约束，引进松弛变量 x4，x5 0。于是，我们可以得到以下标准形式的线性规划问题：于是，我们可以得到以下标准形式的线性规划问题： max z = - 3.6 x1 + 5.2 x2 - 1.8 x3 s. t. 2.3x1 + 5.2x2- 6.1x3 + x4 = 15.7 4.1x1 + 3.3x3 - x5 = 8.9 x1 + x2 + x3 = 38 x1，x2，x3，x4，x5 0 。2022-5-631线性规划问题及其数学模型线性规划问题及其数学模型q化线性规划标准型的方法：化线性规划标准型的方法：q3. 变量无符号限制的问题

25、变量无符号限制的问题： 在标准形式中，必须每一个变量均有非负约束。当某一个变在标准形式中，必须每一个变量均有非负约束。当某一个变量量 xj 没有非负约束时，可以令没有非负约束时，可以令 xj = xj - xj” 其中其中 xj0， xj”0q即用两个非负变量之差来表示一个无符号限制的变量，当然即用两个非负变量之差来表示一个无符号限制的变量，当然 xj 的符号取决于的符号取决于xj 和和 xj” 的大小的大小。2022-5-632线性规划问题及其数学模型线性规划问题及其数学模型q化线性规划标准型的方法：化线性规划标准型的方法：q4.右端项有负值的问题：右端项有负值的问题： 在标准形式中，要求右

26、端项必须每一个分量非负。当某一个在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如右端项系数为负时，如 bi0，则把该等式约束两端同时乘以，则把该等式约束两端同时乘以-1，得到：，得到： - ai1 x1 - ai2 x2 - - ain xn = -bi 2022-5-633线性规划问题及其数学模型线性规划问题及其数学模型q化线性规划标准型的方法：化线性规划标准型的方法：q补例补例 将以下线性规划问题转化为标准形式将以下线性规划问题转化为标准形式 min f = -3 x1 + 5 x2 + 8 x3 - 7 x4 s. t. 2 x1 - 3 x2 + 5 x3 +

27、6 x4 28 4 x1 + 2 x2 + 3 x3 - 9 x4 39 6 x2 + 2 x3 + 3 x4 - 58 x1，x3，x4 02022-5-634线性规划问题及其数学模型线性规划问题及其数学模型q化线性规划标准型的方法：化线性规划标准型的方法：q解：首先，解：首先，将目标函数转换成极大化将目标函数转换成极大化： 令令 z = -f = 3x15x28x3+7x4 ；q其次考虑约束，有其次考虑约束，有 3 个不等式约束，引进个不等式约束，引进 2 个松弛变量和个松弛变量和 1 个个剩余变量剩余变量 x5 , x6 , x7 0 ；q由于由于 x2 无非负限制，无非负限制，引入两个

28、非负变量引入两个非负变量，可令，可令 x2= x2- x2”, 其中其中 x20，x2”0 ；q由于第由于第 3 个约束右端项系数为个约束右端项系数为 -58，于是，于是把该式两端乘以把该式两端乘以 -1 。q于是，我们可以得到以下标准形式的线性规划问题：于是，我们可以得到以下标准形式的线性规划问题：2022-5-635线性规划问题及其数学模型线性规划问题及其数学模型q化线性规划标准型的方法：化线性规划标准型的方法：qmax z = 3x1 5x2 + 5x2” 8x3 + 7x4 s. t. 2x1 3x2 + 3x2” + 5x3 + 6x4 + x5 = 28 4x1 + 2x2 - 2

29、x2” + 3x3 - 9x4 - x6 = 39 -6x2+ 6x2” - 2x3 - 3x4 - x7 = 5 x1，x2，x2”，x3，x4，x5，x6，x7 0 2022-5-636线性规划问题及其数学模型线性规划问题及其数学模型q课堂练习：课堂练习： 某公司由于生产需要，共需要某公司由于生产需要，共需要 A，B 两种原料至少两种原料至少 350 吨吨 ( A, B 两种材料有一定替代性两种材料有一定替代性)，其中，其中 A 原料至少购进原料至少购进 125 吨。但吨。但由于由于 A，B 两种原料的规格不同，各自所需的加工时间也是不两种原料的规格不同，各自所需的加工时间也是不同的，加工

30、每吨同的，加工每吨 A 原料需要原料需要 2 个小时，加工每吨个小时，加工每吨 B 原料需要原料需要 1 小时，而公司总共有小时，而公司总共有 600 个加工小时。又知道每吨个加工小时。又知道每吨 A 原料的原料的价格为价格为 2 万元，每吨万元，每吨 B 原料的价格为原料的价格为 3 万元，试问在满足生万元，试问在满足生产需要的前提下，在公司加工能力的范围内，如何购买产需要的前提下，在公司加工能力的范围内，如何购买 A，B 两种原料，使得购进成本最低？两种原料，使得购进成本最低？2022-5-637线性规划问题及其数学模型线性规划问题及其数学模型AB总总 量量加工时间加工时间21600原料单

31、价原料单价23所需原料数所需原料数x1125x2350q求使购进成本最低的求使购进成本最低的 x1 和 x2。q解：解：问题的线性规划模型为问题的线性规划模型为 目标函数：目标函数： min f = 2 x1+3 x2 约束条件：约束条件： x1+ x2 350 x1 125 2 x1+ x2 600 x1 0 ， x2 0 。2022-5-638线性规划问题及其数学模型线性规划问题及其数学模型q用图解法解此题。用图解法解此题。x1x2600600100100300300 x1 =1252 x1+ x2 = 600 x1+ x2 =350解线性方程组解线性方程组 x1+ x2 =350 2 x

32、1+ x2 = 600得最优解得最优解 x1 = 250 x2 = 100最优值最优值 f = 800可行域可行域2022-5-639线性规划问题及其数学模型线性规划问题及其数学模型q此例此例 的线性规划标准型为的线性规划标准型为 目标函数：目标函数： max z = -2 x1 - 3 x2 - 0s1 - 0s2- 0s3 约束条件：约束条件： x1+ x2 s1 =350 x1 s2 = 125 2 x1+ x2 + s3 = 600 x1 ， x2 ，s1， s2，s3 0 。约束条件约束条件松弛变量及剩余变量的值松弛变量及剩余变量的值原料 A 与原料 B 的总量s1= 0 原料 A 的数量s2 =125加工时间s3 = 02022-5-640线性规划问题及其数学模型线性规划问题及