线形规划的图解法PPT学习教案

1、会计学1 线形规划的图解法线形规划的图解法 第1页/共108页 第2页/共108页 2.1 问题的提出 第3页/共108页 例1. 某工厂在计划期内要安排甲、乙两种产品的生 产，已知生产单位产品所需的设备台时及 A、B 两 种原材料的消耗以及资源的限制，工厂应分别生产 多少单位甲、乙产品才能使工厂获利最多？ 第4页/共108页 甲乙资源限制 设备11300台时 原料A21400千克 原料B01250千克 单位产品获利50元100元 p约束条件：约束条件：s.t. x1 + x2 300 p 2 x1 +x2 400 p x2 250 p x1 ， x2 0 设设生产甲产品生产甲产品 x1 个单

2、位、乙产品个单位、乙产品 x2 个单位，获利个单位，获利z z 目标函数目标函数 max max z z = 50 = 50 x x1 1 + 100 + 100 x x2 2 第5页/共108页 p线性规划问题是： p在一组线性等式或不等式的约束之下 p求一个线性函数的最大值或最小值的问题。 p组成： p 目标函数: max z 或 min f p 约束条件: s. t. (subject to) 满足于 p 决策变量: 用符号 xj 等来表示可控制的因素 第6页/共108页 目标函数: max（min）z = c1 x1 + c2 x2 + + cn xn 约束条件： s. t. a11

3、x1 + a12 x2 + + a1n xn （ =, ）b1 a21 x1 + a22 x2 + + a2n xn （ =, ）b2 am1 x1 + am2 x2 + + amn xn （ =, ）bm x1 ，x2 ， ，xn 0. 第7页/共108页 第8页/共108页 例例1. 目标函数目标函数： max z = 50 x1 + 100 x2 约束条件约束条件： s.t. x1 + x2 300 （E） 2x1 +x2 400 （F） x2 250 （G） x1 ， x2 0 （H） 第9页/共108页 x1 x2 100300 300 100 200 200 一个线性不等式确定一个

4、半平面一个线性不等式确定一个半平面 不等式 x1 + x2 300 ( E )确定的半平面为 x1 x2 100300 300 100 200 200 x1 + x2 = 300 x1 + x2 300 E 第10页/共108页 x1 x2 100300 300 100 200 200 2x1 + x2 = 400 F 400 400 x1 x2 100300 300 100 200 200 x1 + x2 = 300 E x1 x2 100300 300 100 200 200 x2 = 250 G 400 400 F ps.t. p x1 + x2 300（E） p 2x1 +x2 400

5、（F） p x2 250（G） p x1 0 （H） p x2 0 第11页/共108页 目标函数目标函数：max z = 50 x1 + 100 x2 考查目标函数等值线考查目标函数等值线 x2 = 0 x1 x2 100300 300 100 200 200400 400 2x1 + x2 = 400 x1 + x2 = 300 x2 = 250 x1 = 0 ps.t. p x1 + x2 300（E） p 2x1 +x2 400（F） p x2 250（G） p x1 0 （H） p x2 0 第12页/共108页 x1 x2 100300 300 100 200 200400 400

6、 z =20000= 50 x1+100 x2 z =27500= 50 x1+100 x2 z =10000= 50 x1+100 x2 D 目标函数目标函数：max z = 50 x1 + 100 x2 考查目标函数等值线考查目标函数等值线 第13页/共108页 x1 x2 100300 300 100 200 200400 400 2x1 + x2 = 400 x1 + x2 = 300 x2 = 250 x1 = 0 x1 x2 100300 300 100 200 200400 400 z =50 x1+100 x2 AB C D 目标函数目标函数：max z = 50 x1 + 1

7、00 x2 考查目标函数等值线考查目标函数等值线 第14页/共108页 x1 x2 100300 300 100 200 200400 400z =27500= 50 x1+100 x2 D 目标函数目标函数：max z = 50 x1 + 100 x2 考查目标函数等值线考查目标函数等值线 AB C D x1 x2 100300 300 100 200 200400 400 2x1 + x2 = 400 x1 + x2 = 300 x2 = 250 x1 = 0 第15页/共108页 p x1 + x2 = 300 (E) p x2 = 250 (G) p得最优解为： p x1 = 50，

8、x2 = 250， p最优目标值为： p z = 50 x1 + 100 x2 = 27500 第16页/共108页 对于只有两个决策变量的线性规划问题，可以在平 面直角坐标系上作图表示线性规划问题的有关概念， 并求解，其步骤如下： (1) 分别取决策变量 x1，x2为坐标向量建立直角坐标 系。 第17页/共108页 x1 x2 100300 300 100 200 200 第18页/共108页 对于只有两个决策变量的线性规划问题，可以在平 面直角坐标系上作图表示线性规划问题的有关概念， 并求解，其步骤如下： (1) 分别取决策变量 x1，x2为坐标向量建立直角坐 标系。 第19页/共108页

9、 (2) 对每个不等式(约束条件)，先取其等式在坐标系中 作直线，然后确定不等式所决定的半平面。 第20页/共108页 x1 x2 100300 300 100 200 200 x1 x2 100300 300 100 200 200 x1 + x2 = 300 x1 + x2 300 E 第21页/共108页 (2) 对每个不等式(约束条件)，先取其等式在坐标系中 作直线，然后确定不等式所决定的半平面。 若各半平面交出来的公共区域存在，显然，其中的 点满足所有的约束条件，称这样的点为此线性规 划的可行解，全体可行解的集合称为可行集或可 行域。 第22页/共108页 x2 = 0 x1 x2

10、100300 300 100 200 200400 400 2x1 + x2 = 400 x1 + x2 = 300 x2 = 250 x1 = 0 ps.t. p x1 + x2 300（E） p 2x1 +x2 400（F） p x2 250（G） p x1 0 （H） p x2 0 第23页/共108页 (2) 对每个不等式(约束条件)，先取其等式在坐标系中 作直线，然后确定不等式所决定的半平面。 若各半平面交出来的公共区域存在，显然，其中的 点满足所有的约束条件，称这样的点为此线性规 划的可行解，全体可行解的集合称为可行集或可 行域。 若这样的公共区域不存在，则该线性规划问题无可行解

11、。 第24页/共108页 (3) 任意给定目标函数一个确定的值，作出对应的 目标函数等值线，并确定该族等值线平行移动 时目标函数值增加的方向。 第25页/共108页 x1 x2 100300 300 100 200 200400 400 2x1 + x2 = 400 x1 + x2 = 300 x2 = 250 x1 = 0 x1 x2 100300 300 100 200 200400 400 z =50 x1+100 x2 AB C D 目标函数目标函数：max z = 50 x1 + 100 x2 考查目标函数等值线考查目标函数等值线 第26页/共108页 (3) 任意给定目标函数一个确

12、定的值，作出对应的 目标函数等值线，并确定该族等值线平行移动 时目标函数值增加的方向。 然后平移目标函数的等值线，使其达到既与可 行域有交点又不可能使值再增加的位置。 此时，目标函数等值线与可行域的交点即此线 性规划的最优解（一个或多个），此目标函数 的值即最优值。 第27页/共108页 x1 x2 100300 300 100 200 200400 400z =27500= 50 x1+100 x2 D 目标函数目标函数：max z = 50 x1 + 100 x2 考查目标函数等值线考查目标函数等值线 AB C D x1 x2 100300 300 100 200 200400 400 2

13、x1 + x2 = 400 x1 + x2 = 300 x2 = 250 x1 = 0 第28页/共108页 u线性规划的最优解如果存在，则必定有一个顶点 （极点）是最优解； u有的线性规划问题存在无穷多个最优解的情况； (如将例1中的目标函数变为求 max z=50 x1+50 x2) 第29页/共108页 x1 x2 100300 300 100 200 200400 400 2x1 + x2 = 400 x1 + x2 = 300 x2 = 250 x1 = 0 x1 x2 100300 300 100 200 200400 400 z =50 x1+50 x2 AB C D 目标函数目

14、标函数：max z = 50 x1 + 50 x2 考查目标函数等值线考查目标函数等值线 第30页/共108页 u线性规划的最优解如果存在，则必定有一个顶点 （极点）是最优解； u有的线性规划问题存在无穷多个最优解的情况； (如将例1中的目标函数变为求 max z=50 x1+50 x2) u有的线性规划问题存在无有限最优解的情况，也 称无解；(见 16 页2-3) 第31页/共108页 x1 x2 100300 300 100 200 200 x2 = 250 G 400 400 F ps.t. p x2 250（G） p x1 0 （H） p x2 0 z =50 x1+100 x2 第3

15、2页/共108页 u线性规划的最优解如果存在，则必定有一个顶点 （极点）是最优解； u有的线性规划问题存在无穷多个最优解的情况； (如将例1中的目标函数变为求 max z=50 x1+50 x2) u有的线性规划问题存在无有限最优解的情况，也 称无解； u有的线性规划问题存在无可行解的情况。 第33页/共108页 p x1 +x2 400 x2 = 0 x1 x2 100300 300 100 200 200400 400 2x1 + x2 = 400 x1 + x2 = 300 x2 = 250 x1 = 0 第34页/共108页 u线性规划的最优解如果存在，则必定有一个顶点 （极点）是最优

16、解； u有的线性规划问题存在无穷多个最优解的情况； (如将例1中的目标函数变为求 max z=50 x1+50 x2) u有的线性规划问题存在无有限最优解的情况，也 称无解；(见 16 页2-3) u有的线性规划问题存在无可行解的情况。( 见16页 4) 第35页/共108页 第36页/共108页 例例1. 目标函数目标函数： max z = 50 x1 + 100 x2 约束条件约束条件： s.t. x1 + x2 300 （E） 2x1 +x2 400 （F） x2 250 （G） x1 ， x2 0 （H） 第37页/共108页 由于目标函数和约束条件内容和形式上的差 别,线性规划问题可

17、以有多种表达式.为了便于 讨论和制定统一的算法,规定了线形规划问题的 标准形式。 第38页/共108页 目标函数: max z = c1 x1 + c2 x2 + + cn xn 约束条件： 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. 第39页/共108页 线性规划的标准形式有如下四个要求： u 目标最大化 第40页/共108页 目标函数: max z = c1 x1 + c2 x2 + + cn xn

18、约束条件： 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. 第41页/共108页 线性规划的标准形式有如下四个要求： u 目标最大化 u 约束方程为等式 第42页/共108页 目标函数: max z = c1 x1 + c2 x2 + + cn xn 约束条件： s. t. a11 x1 + a12 x2 + + a1n xn = b1 a21 x1 + a22 x2 + + a2n xn = b2 am1

19、x1 + am2 x2 + + amn xn = bm x1 ，x2 ， ，xn 0. 第43页/共108页 线性规划的标准形式有如下四个要求： u 目标最大化 u 约束方程为等式 u 决策变量为非负 第44页/共108页 目标函数: max z = c1 x1 + c2 x2 + + cn xn 约束条件： 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. 第45页/共108页 线性规划的标准形式有如下四个要

20、求： u 目标最大化 u 约束方程为等式 u 决策变量为非负 u 右端项为非负 第46页/共108页 目标函数: max z = c1 x1 + c2 x2 + + cn xn 约束条件： 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. 第47页/共108页 线性规划的标准形式有如下四个要求： u 目标最大化 u 约束方程为等式 u 决策变量为非负 u 右端项为非负 对于各种非标准形式的线性规划问题，我们总

21、可以通过以下变换，将其转化为标准形式: 第48页/共108页 目标函数: max（min）z = c1 x1 + c2 x2 + + cn xn 约束条件： 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. 第49页/共108页 1.极小化目标函数的问题： 设目标函数为 min f = c1x1 + c2x2 + + cnxn (可以)令 z - f ， 则该极小化问题与下面的极大化问题

22、有相同的最优 解，即 max z = - c1x1 - c2x2 - - cnxn 但必须注意，尽管以上两个问题的最优解相同，但 他们最优解的目标函数值却相差一个符号，即 min f - max z 第50页/共108页 目标函数: max（min）z = c1 x1 + c2 x2 + + cn xn 约束条件： 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. 第51页/共108页

23、2. 约束条件不是等式的问题： 设约束条件为 ai1 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 第52页/共108页 例例1.目标函数目标函数： max z = 50 x1 + 100 x2 约束条件约束条件： s.t. x1 + x2 300 （E） 2x1 +x2 400 （F） x2 250 （G） x1 ， x2

24、0 （H） p得最优解为： p x1 = 50， x2 = 250， p最优目标值为： p z = 50 x1 + 100 x2 = 27500 第53页/共108页 把最优解 x1 = 50，x2 = 250 代入约束条件可知，设 备台时数及原料B 都恰好消耗完，而原料A则还剩余 50 千克。 为此我们引入松驰变量（含义是资源的剩余量） s1，s2，s3，则例1的模型可写成 目标函数：目标函数：max z = 50 x1+100 x2+0s1+0s2+0s3 约束条件：约束条件： x1 + x2 +s1 = 300 2x1 + x2 +s2 = 400 x2 +s3 = 250 x1, x2

25、,s1, s2, s30。 求得最优解为：求得最优解为：x1= 50, x2= 250, s1= 0, s2= 50,s3= 0 第54页/共108页 s1 = 300 - x1 x2 s2 = 400 - 2x1 - x2 s3 = 250 - x2 目标函数：目标函数：max z = 50 x1+100 x2+0s1+0s2+0s3 约束条件：约束条件： x1 + x2 +s1 = 300 2x1 + x2 +s2 = 400 x2 +s3 = 250 x1, x2,s1, s2, s30。 求得最优解为：求得最优解为：x1= 50, x2= 250, s1= 0, s2= 50,s3=

26、0 第55页/共108页 2. 约束条件不是等式的问题： 设约束条件为 ai1 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 第56页/共108页 当约束条件为 ai1 x1+ai2 x2+ +ain xn bi 时，类似地令 s = (ai1 x1+ai2 x2+ +ain xn) - bi 显然，s 也具有非负约束，即s0

27、，这时新的约束 条件成为 ai1 x1+ai2 x2+ +ain xn - s = bi 第57页/共108页 为了使约束由不等式成为等式而引进的变量 s u 当不等式为“小于等于”时称为“松弛变量” u 当不等式为“大于等于”时称为“剩余变量” 如果原问题中有若干个非等式约束，则将其转化 为标准形式时，必须对各个约束引进不同的变量 ，有时也将它们统称为松弛变量。 第58页/共108页 例：将以下线性规划问题转化为标准形式 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.

28、9 x1 + x2 + x3 = 38 x1，x2，x3 0 第59页/共108页 解： 首先, 将目标函数转换成极大化：令 z = -f = -3.6x1 + 5.2x2 - 1.8x3 其次,考虑约束，有 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 min f

29、= 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 第60页/共108页 线性规划的标准形式有如下四个要求： u 目标最大化 u 约束方程为等式 u 决策变量为非负 u 右端项为非负 第61页/共108页 目标函数: max（min）z = c1 x1 + c2 x2 + + cn xn 约束条件： s. t. a11 x1 + a12 x2 + + a1n xn （ =, ）b1 a21 x1 + a22 x2 + + a2

30、n xn （ =, ）b2 am1 x1 + am2 x2 + + amn xn （ =, ）bm x1 ，x2 ， ，xn 0. 第62页/共108页 3. 变量无符号限制的问题： 在标准形式中，必须每一个变量均有非负约束。当 某一个变量 xj 没有非负约束时，可以令 xj = xj - xj” 其中 xj0， xj”0 即用两个非负变量之差来表示一个无符号限制的变 量，当然 xj 的符号取决于xj 和 xj” 的大小。 第63页/共108页 目标函数: max（min）z = c1 x1 + c2 x2 + + cn xn 约束条件： s. t. a11 x1 + a12 x2 + + a

31、1n xn （ =, ）b1 a21 x1 + a22 x2 + + a2n xn （ =, ）b2 am1 x1 + am2 x2 + + amn xn （ =, ）bm x1 ，x2 ， ，xn 0. 第64页/共108页 4.右端项有负值的问题： 在标准形式中，要求右端项必须每一个分量非负。 当某一个右端项系数为负时，如 bi0，则把该等式 约束两端同时乘以-1，得到： - ai1 x1 - ai2 x2 - - ain xn = -bi 第65页/共108页 例: 将以下线性规划问题转化为标准形式 min f = -3x1 + 5x2 + 8x3 - 7x4 s. t. 2x1 - 3

32、x2 + 5x3 + 6x4 28 4x1 + 2x2 + 3x3 - 9x4 39 6x2 + 2x3 + 3x4 -58 x1，x3，x4 0 第66页/共108页 解： 首先，将目标函数转换成极大化： 令 z = -f = 3x15x28x3+7x4 ； 第67页/共108页 min f = -3x1 + 5x2 + 8x3 - 7x4 s. t. 2x1 - 3x2 + 5x3 + 6x4 28 4x1 + 2x2 + 3x3 - 9x4 39 6x2 + 2x3 + 3x4 -58 x1，x3，x4 0 max z = 3x1 - 5x2 - 8x3 + 7x4 s. t. 2x1

33、- 3x2 + 5x3 + 6x4 28 4x1 + 2x2 + 3x3 - 9x4 39 6x2 + 2x3 + 3x4 -58 x1，x3，x4 0 第68页/共108页 解： 首先，将目标函数转换成极大化： 令 z = -f = 3x15x28x3+7x4 ； 其次，考虑约束，有 3 个不等式约束，引进 2 个松 弛变量和 1 个剩余变量 x5 , x6 , x7 0 ； 第69页/共108页 max z = 3x1 5x2 8x3 + 7x4 s. t. 2x1 3x2 + 5x3 + 6x4 + x5 = 28 4x1 + 2x2 + 3x3 - 9x4 - x6 = 39 6x2

34、+ 2x3 + 3x4 + x7 = -58 x1，x3，x4，x5，x6，x7 0 max z = 3x1 - 5x2 - 8x3 + 7x4 s. t. 2x1 - 3x2 + 5x3 + 6x4 28 4x1 + 2x2 + 3x3 - 9x4 39 6x2 + 2x3 + 3x4 -58 x1，x3，x4 0 第70页/共108页 解： 首先，将目标函数转换成极大化： 令 z = -f = 3x15x28x3+7x4 ； 其次，考虑约束，有 3 个不等式约束，引进 2 个松 弛变量和 1 个剩余变量 x5 , x6 , x7 0 ； 由于 x2 无非负限制，引入两个非负变量，可令 x2

35、= x2- x2”, 其中 x20，x2”0 ； 第71页/共108页 max z = 3x1 5x2 8x3 + 7x4 s. t. 2x1 3x2 + 5x3 + 6x4 + x5 = 28 4x1 + 2x2 + 3x3 - 9x4 - x6 = 39 6x2 + 2x3 + 3x4 + x7 = -58 x1，x3，x4，x5，x6，x7 0 max z = 3x1 5x2+ 5x2” 8x3 + 7x4 s. t. 2x1 3x2 + 3x2” + 5x3 + 6x4 + x5 = 28 4x1 + 2x2 - 2x2” + 3x - 9x4 - x6 = 39 6x2 - 6x2”

36、 + 2x3 + 3x4 + x7 = -58 x1，x2，x2”，x3，x4，x5，x6，x7 0 第72页/共108页 解： 首先，将目标函数转换成极大化： 令 z = -f = 3x15x28x3+7x4 ； 其次，考虑约束，有 3 个不等式约束，引进 2 个松 弛变量和 1 个剩余变量 x5 , x6 , x7 0 ； 由于 x2 无非负限制，引入两个非负变量，可令 x2= x2- x2”, 其中 x20，x2”0 ； 由于第 3 个约束右端项系数为 -58，于是把该式两 端乘以 -1 。 第73页/共108页 max z = 3x1 5x2+ 5x2” 8x3 + 7x4 s. t.

37、 2x1 3x2 + 3x2” + 5x3 + 6x4 + x5 = 28 4x1 + 2x2 - 2x2” + 3x - 9x4 - x6 = 39 6x2 - 6x2” + 2x3 + 3x4 + x7 = -58 x1，x2，x2”，x3，x4，x5，x6，x7 0 max z = 3x1 5x2+ 5x2” 8x3 + 7x4 s. t. 2x1 3x2 + 3x2” + 5x3 + 6x4 + x5 = 28 4x1 + 2x2 - 2x2” + 3x - 9x4 - x6 = 39 - 6x2 + 6x2” - 2x3 - 3x4 - x7 = 58 x1，x2，x2”，x3，x4

38、，x5，x6，x7 0 第74页/共108页 例2. 某公司由于生产需要，共需要 A，B 两种原料至少 350 吨 ( A, B 两种材料有一定替代性)，其中 A 原料至少购进 125 吨。但由于 A，B 两种原料的规格不同，各自所需的加工时间也是不同的，加工每吨 A 原料需要 2 个小时，加工每吨 B 原料需要 1 小时，而公司总共有 600 个加工小时。又知道每吨 A 原料的价格为 2 万元，每吨 B 原料的价格为 3 万元。试问在满足生产需要的前提下，在公司加工能力的范围内，如何购买 A，B 两种原料，使得购进成本最低？ 解：设x1为原料A的数量，x2为原料B的数量 目标函数： min

39、f = 2 x1+3 x2 约束条件： x1 + x2 350 x1 125 2 x1 + x2 600 x1 ， x2 0 第75页/共108页 o x1 100300 300 100 200 200400 400 2x1 + x2 = 600 x1 + x2 = 350 x1 = 125 500 600 500 600 Q 解：设x1为原料A的数量，x2为原料B的数量 目标函数： min f = 2 x1+3 x2 约束条件： x1 + x2 350 x1 125 2 x1 + x2 600 x1 ， x2 0 o x1 x2 100300 300 100 200 200400 400 5

40、00 600 500 600 x2 2x1 + 3x2 = 800 2x1 + 3x2 = f 解线性方程组解线性方程组 x1+ x2 =350 2 x1+ x2 = 600 得最优解得最优解 x1 = 250 x2 = 100 最优值最优值 f = 800 第76页/共108页 解：设x1为原料A的数量，x2为原料B的数量 目标函数： min f = 2 x1+3 x2 约束条件： x1 + x2 350 x1 125 2 x1 + x2 600 x1 ， x2 0 线性规划标准型为线性规划标准型为 目标函数：目标函数： max z = -2 x1 - 3 x2 - 0s1 - 0s2- 0

41、s3 约束条件：约束条件： x1+ x2 -s1 =350 x1 -s2 = 125 2 x1+ x2 + s3 = 600 x1 ， x2 ，s1，s2，s3 0 。 得最优解得最优解 x1 = 250 x2 = 100 约约束条件束条件松弛松弛变变量及剩余量及剩余变变量的量的值值 原料原料 A 与原料与原料 B 的的总总量量s1= 0 原料原料 A 的数量的数量s2 =125 加工加工时间时间s3 = 0 第77页/共108页 第78页/共108页 第79页/共108页 第80页/共108页 目标函数: max z = c1 x1 + c2 x2 + + cn xn 约束条件： s. t.

42、 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. 第81页/共108页 当然，当线性规划问题中的一个或几个参数（系 数）变化时，我们可以重新计算新问题的最优解，看 最优解有无变化。但是，这样做有时既麻烦又没有必 要。 以下只介绍图解法的灵敏度分析法： 1）对目标函数中的系数 cj 进行灵敏度分析； 2）对约束条件中的右端常数项 bi 进行灵敏度分析。 第82页/共108页 2.4 图解法的灵敏度分析 第83页/共108页

43、 甲乙资源限制 设备11300台时 原料A21400千克 原料B01250千克 单位产品获利50元100元 p约束条件：约束条件：s.t. x1 + x2 300 p 2 x1 +x2 400 p x2 250 p x1 ， x2 0 设设生产甲产品生产甲产品 x1 个单位、乙产品个单位、乙产品 x2 个单位，获利个单位，获利z z 目标函数目标函数 max max z z = 50 = 50 x x1 1 + 100 + 100 x x2 2 第84页/共108页 x1 x2 100300 300 100 200 200400 400z =27500= 50 x1+100 x2 D AB C D x1 x2 100300 300 100 200 200400 400 2x1 + x2 = 400 x1 + x2 = 300 x2 = 250 x1 = 0 第85页/共108页 x1 x2 100300 300 100 200 200400 400 z =20000= 50 x1+100 x2 z =27500= 50 x1+100 x2 z =10000= 50 x1+100 x2 第86页/共108页 2.4 图解