线性规划和单纯形法课件.ppt

《线性规划和单纯形法课件.ppt》由会员分享，可在线阅读，更多相关《线性规划和单纯形法课件.ppt（76页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、目目 录录p线性规划实例与模型线性规划实例与模型p线性规划的图解法线性规划的图解法p单纯形法原理单纯形法原理p改进单纯形法改进单纯形法p应用应用目目 录录p线性规划实例与模型线性规划实例与模型实用举例实用举例 某公司通过市场调研，决定生产高中档新型拉杆箱。某分销商决定买进该公司3个月内的全部产品。拉杆箱生产需经过原材料剪裁、缝合、定型、检验和包装4过程。 通过分析生产过程，得出：生产中档拉杆箱需要用7/10小时剪裁、5/10小时缝合、1小时定型、1/10小时检验包装；生产高档拉杆箱则需用1小时剪裁、5/6小时缝合、2/3小时定型、1/4小时检验包装。由于公司生产能力有限，3月内各部的最大生产时

2、间为剪裁部630小时、缝合部600小时、定型部708小时、检验包装部135小时。 通过市场调研部和会计部的调查核算得出结论：生产中档拉杆箱的利润是10元，高档拉杆箱的利润是9元。公司应各生产多少中档和高档拉杆箱才能使公司利润最大？实用举例实用举例 某公司通过市场调研，决定生产高中档新型拉杆箱。某分销商决定买进该公司3个月内的全部产品。拉杆箱生产需经过原材料剪裁、缝合、定型、检验和包装4过程。 通过分析生产过程，得出：生产中档拉杆箱需要用7/10小时剪裁、5/10小时缝合、1小时定型、1/10小时检验包装；生产高档拉杆箱则需用1小时剪裁、5/6小时缝合、2/3小时定型、1/4小时检验包装。由于公

3、司生产能力有限，3月内各部的最大生产时间为剪裁部630小时、缝合部600小时、定型部708小时、检验包装部135小时。 通过市场调研部和会计部的调查核算得出结论：生产中档拉杆箱的利润是10元，高档拉杆箱的利润是9元。公司应各生产多少中档和高档拉杆箱才能使公司利润最大？可以通过线性规划求解可以通过线性规划求解！线性规划模型的建立线性规划模型的建立 设生产中、高档拉杆箱数量分别为： 称为决策变量。0, 0 135 708 600 630 . .910 max21241110123212651212110721xxxxxxxxxxtsxx目标函数目标函数约束条件约束条件21,xx一般线性规划模型Ma

4、x z = c1x1 + c2x2 + + cnxns.t. a11x1+ a12x2 + + a1nxn = b1 ( 0) a21x1+ a22x2 + + a2nxn = b2 ( 0) : am1x1+ am2x2 + + amnxn= bm( 0) x1,x2 , ,xn 0s.t. 为约束限制（Subject to）的缩写(LP)x1.xnb1.bma11 a1nam1 amnx =b =A = c =0Xb),(AXt . scxzmin)max( 或其中c=(c1,c2,cn)，称为价值系数向量；mbbbb21称为资源限制向量 X=(x1,x2,xn)T 称为决策变量向量aaa

5、aaaaaamnmmnnA212222111211称为技术系数矩阵(也称消耗系数矩阵)一般线性规划模型线性规划模型的标准形式线性规划模型的标准形式Max Z = c1x1 + c2x2 + + cnxnSubject to (s.t.)a11x1 + a12x2 + + a1nxn = b1 a21x1 + a22x2 + + a2nxn = b2 am1x1 + am2x2 + + amnxn= bm x x1 1 0, 0, x x2 2 0, 0, , , x xn n 0 为了讨论方便，把最大化、等式约束型的线性规划称为线为了讨论方便，把最大化、等式约束型的线性规划称为线性规划的标准型

6、，即性规划的标准型，即标准化标准化原问题原问题标准化方法标准化方法目标函数目标函数Max f(x)Max f(x)Min f(x)Max f(x)约束条件约束条件引入松弛变量和人工变量引入松弛变量, 不变变量变量 不变对某个njijijbxa1 i对某个njijijbxa1 i对某个njijijbxa1 人工变量松弛变量njijijbxa1 松弛变量0 iix对某个0 iix对某个0iiixxx，其中令0,iiiiixxxxx，其中令njijijbxa1 i对某个对某个ixi 是任意的 线性规划模型的标准化线性规划模型的标准化 例例: :将如下线性规划模型标准化：将如下线性规划模型标准化：mi

7、n z= x1 + 5 x2 - 8 x3 - x4s.t. 2 x1 - 3 x2 + x3 + x4 20 x1+ 2 x2 + 3 x3 - x4 30 2x2 + 2 x3 +3 x4- 50 x1 , x3 , x4 0，x2取值无约束。取值无约束。 max z1=-x1-5 x2+8 x3 +x4s.t. 2 x1 - 3 x2 + x3 + x4 20 x1+ 2 x2 + 3 x3 - x4 30 2x2 + 2 x3 +3 x4- 50 x1 , x3 , x4 0，x2取值无约束。取值无约束。 目标优化标准化目标优化标准化线性规划模型的标准化Max z2 =-x1-5y2+

8、5y3+8x3+x4 s.t. 2 x1 - 3 y2+3y3 + x3 + x4 20 -x1- 2 y2 +2y3 - 3 x3 + x4 -30 -2y2 +2y3 - 2 x3 -3 x4 50 x1 , x3 , x4 ,y2,y3 0 决策变量的标准化决策变量的标准化: y2 - y3 = x2max z1=-x1-5 x2+8 x3 +x4s.t. 2 x1 - 3 x2 + x3 + x4 20 x1+ 2 x2 + 3 x3 - x4 30 2x2 + 2 x3 +3 x4- 50 x1 , x3 , x4 0，x2取值无约束取值无约束 线性规划模型的标准化Max z2 =-

9、x1-5y2+5y3+8x3+x4 s.t. 2 x1 - 3 y2+3y3 + x3 + x4 +x5 =20 -x1- 2 y2 +2y3 - 3 x3 + x4 +x6 = -30 -2y2 +2y3 - 2 x3 -3 x4 +x7 = 50 x1 , x3 , x4 , x5, x6, x7, y2, y3 0约束关系标准化约束关系标准化Max z2 =-x1-5y2+5y3+8x3+x4 s.t. 2 x1 - 3 y2+3y3 + x3 + x4 20 -x1- 2 y2 +2y3 - 3 x3 + x4 -30 -2y2 +2y3 - 2 x3 -3 x4 50 x1 , x3

10、 , x4 ,y2,y3 0 p可行解可行解:满足所有约束条件的解x=（x1，x2，.，xn），所有可行解的集合称为可行域可行域。p基基：设A是约束方程组的mn阶系数矩阵，秩为m， 是A中阶非奇异子矩阵（即 ），则称是线性规划问题的一个基矩阵基矩阵，简称基基。B中的列向量称为基向量基向量，与基向量对应的变量x称为基变量基变量，其它变量称为非基变量非基变量。 p基本解基本解：令非基变量值为0，由Ax=b可求出一个解，这个解x称为基本解基本解。p基本可行解基本可行解：满足非负条件的基本解称为基本可行解基本可行解。p最优解最优解：使目标函数达到最优值的可行解称为最优解最优解。 线性规划的解线性规划的

11、解 ),(1mPPB| 0B 可行解、基本解、基本可行解的关系可行解可行解基本解基本解基本可行解基本可行解目目 录录p线性规划实例与模型线性规划实例与模型p线性规划的图解法与基本性质线性规划的图解法与基本性质线性规划的图解法线性规划的图解法 当只有两个决策变量当只有两个决策变量时，可用图解法求解！时，可用图解法求解！例例：用图解法求解以下线形规划问题。 max z=4x1+3x2 s.t. x16 2x28 2x1+3x218 x10，x20 x1 x2 L3：2x1+3x2=18可行域可行域L1：x1=6L2：x2=4最优解B4x1+3x2解的特殊情况解的特殊情况多个最优解多个最优解解的特殊

12、情况解的特殊情况无可行解无可行解解的特殊情况解的特殊情况无界解无界解线性规划的基本性质线性规划的基本性质 X可行域内部的点 可行解? 是是 最优解? 不不 若线性规划有最若线性规划有最优解，则最优解必在可优解，则最优解必在可行域的顶点上达到。行域的顶点上达到。凸集的概念凸集的概念 p凸集是线性规划中一个很重要的概念，凸集的一般定义为：凸集是线性规划中一个很重要的概念，凸集的一般定义为：如果在集合如果在集合C C中任意取两个点中任意取两个点x x1 1，x x2 2，其连线上的所有点也，其连线上的所有点也都在集合都在集合C C中，则称集合中，则称集合C C为凸集合。用数学解析式表达为：为凸集合。

13、用数学解析式表达为：对任意对任意 ，均有，均有 ，则称，则称C C是是凸集合。凸集合。Cxx21,Cxx21)1 () 10 (非凸集非凸集非凸集非凸集凸集凸集线性规划的基本性质 定理定理2.12.1：线性规划的可行域：线性规划的可行域： 是凸集（凸多面体）。是凸集（凸多面体）。0),(,|1nixxxxbAxxD 引理引理2.12.1：线性规划的可行解线性规划的可行解 为基本可行解的为基本可行解的充分必要条件是充分必要条件是x x的正分量所对应的系数列向量是线性无关的，的正分量所对应的系数列向量是线性无关的，即每个正分量都是一个基变量即每个正分量都是一个基变量。 Tnxxx),(1定理定理2

14、.22.2：线性规划问题的基本可行解线性规划问题的基本可行解x x对应于可行域的顶点对应于可行域的顶点 定理定理2.32.3：若线性规划有最优解，则最优解必在可行域的顶点上若线性规划有最优解，则最优解必在可行域的顶点上达到。达到。目目 录录p线性规划实例与模型线性规划实例与模型p线性规划的图解法线性规划的图解法p单纯形法原理单纯形法原理一、初始基本可行解的确定一、初始基本可行解的确定p考虑如下形式的线性规划问题考虑如下形式的线性规划问题max z=c1x1+c2x2+.+cnxn s.t. a11x1+a12x2+a1nxnb1 a21x1+a22x2+a2nxnb2 (2.17） . am1

15、x1+am2x2+ +amnxnbm x1，x2，.，xn0 （2.18）对每个不等式约束引入一个非负松弛变量，得标准形式：对每个不等式约束引入一个非负松弛变量，得标准形式：max z=c1x1+c2x2+.+cn xns.t. a11x1+a1nxn+xn+1 =b1 a21x1+a2nxn +xn+2 =b2 （2.19） . am1x1+amn xn +xn+m =bm x1，x2，.，xn，xn+1，xn+m0100010001),(1mnnPPB), 1(mibxiin是线性规划是线性规划(2.19)(2.19)的一个可行基。令的一个可行基。令 021nxxx得得由此得到一个初始基本

16、可行解为由此得到一个初始基本可行解为TmTmnnnbbxxxx), 0 , 0(), 0 , 0(121二、最优性检验二、最优性检验 p定理定理2.42.4： 在最大化问题中，对于某个基本可行解，如果所有 的 ，则这个基本可行解是最优解。 在最小化问题中，对于某个基本可行解，如果所有 的 ，则这个基本可行解是最优解。0jjzc0jjzc单纯形法求解步骤单纯形法求解步骤p将所给问题化为标准形将所给问题化为标准形p找出一个初始可行基找出一个初始可行基, ,建立初始单纯形表建立初始单纯形表p检查所有检验数检查所有检验数( (若全为非负若全为非负, ,则已得到最优解则已得到最优解, ,计计算停止算停止

17、. .否则继续下一步否则继续下一步) )p考察是否无解考察是否无解( (若是若是, ,计算停止计算停止, ,否则继续下一步否则继续下一步) )p确定入基变量确定入基变量, ,出基变量出基变量p对初始单纯形表进行单纯形变换对初始单纯形表进行单纯形变换单纯形方法的一般步骤单纯形方法的一般步骤确定一个初始可行角点确定一个初始可行角点根据某种法则进行角点根据某种法则进行角点的最优性判断的最优性判断不是最优角点不是最优角点是最优角点是最优角点考察与当前角点相邻的考察与当前角点相邻的 “ “更好更好”的的一个角点，并置为当前角点。一个角点，并置为当前角点。根据某种法则进行根据某种法则进行LPLP的无的无界

18、或不可行判断界或不可行判断无界或不可行无界或不可行还不能做出判断还不能做出判断求求解解结结束束单纯形法举例单纯形法举例0,26232432.34max21212121xxxxxxxxtsZ解：引进松驰变量x3, x4，化为标准形得：0,262324 32.0034max43214 213214321xxxxxxxxxxxxxxtsZ)26,24, 0 , 0(),(4321xxxx 4 3 0 0 CBXBb x1 x2 x3 x4 b/y00 x3x42426 2 3 1 0 24/2 3 2 0 1 26/3 0 4 3 0 04=4（03+02）；3=3（02+03） 4 3 0 0CB

19、XBb x1 x2 x3 x4 b/y04x3x120/326/3 0 5/ 3 1 -2/3 1 2/3 0 1/3 -104/3 0 1/3 0 -4/3jjzcjjzcicic 4 3 0 0CBXBb x1 x2 x3 x434x2x146 0 1 3/5 -2/5 1 0 -2/5 3/5 36 0 0 -1/5 -6/5表中最后一行的所有检验数均为非正数，表明目标函数已达到最大值，上述表为最优表。从表中可得到最优解为X=（x1,x2,x3,x4）=（6，4，0，0），最优值为Z=36icjjzc 4 3 0 0CBXBb x1 x2 x3 x4 b/y04x3x120/326/3

20、0 5/ 3 1 -2/3 4 1 2/3 0 1/3 13 -104/3 0 1/3 0 -4/3icjjzc单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法p人工变量法：p前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为人工变量，构成的可行基称为人工基，用大M法或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量法。单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法p例1.10 用大M法解下列线性规划 01

21、2210243423max321321321321321xxxxxxxxxxxxxxxZ、解：首先将数学模型化为标准形式解：首先将数学模型化为标准形式 5 , 2 , 1, 012210243423max32153214321321jxxxxxxxxxxxxxxxZj系数矩阵中不存在系数矩阵中不存在单位矩阵，无法建单位矩阵，无法建立初始单纯形表。立初始单纯形表。单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法p故人为添加两个单位向量，得到人工变量单纯形法数学模故人为添加两个单位向量，得到人工变量单纯形法数学模型：型：7 , 2 , 1, 012210243423max7321532

22、16432176321jxxxxxxxxxxxxxxMxMxxxxZj其中：其中：M是一个很大的抽象的数，不需要给出具体的数值，是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值；再用前面介可以理解为它能大于给定的任何一个确定数值；再用前面介绍的单纯形法求解该模型，计算结果见下表。绍的单纯形法求解该模型，计算结果见下表。 单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法cj32-100-M-MCBXBbx1x2x3x4x5x6x7i-Mx64-431-101040 x5101-1201005-Mx712-21000113-2M2+M-1+2M-M0

23、000 x63-650-1013/5-Mx58-3300108/3-1x312-210005-6M5M0-M002x23/56/5101/50-Mx531/53/5003/5131/3-1x311/52/5012/505 00002x213010123x131/310015/3-1x319/300102/3000-5-25/3j j j j 单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法解的判别：解的判别：1）唯一最优解判别：最优表中所有非基变量的检验数非零）唯一最优解判别：最优表中所有非基变量的检验数非零,则线则线 规划具有唯一最优解。（检验数为负数或规划具有唯一最优解。（检验

24、数为负数或0）2）多重最优解判别：最优表中存在非基变量的检验数为零）多重最优解判别：最优表中存在非基变量的检验数为零,则线则性规划具有无穷多最优解（检验数为负数或则线则性规划具有无穷多最优解（检验数为负数或0）。）。3）无界解判别：某个检验数）无界解判别：某个检验数0且且aik（i=1，2,m）则）则线性规划具有无界解。线性规划具有无界解。4）无可行解的判断：当用大）无可行解的判断：当用大M单纯形法计算得到最优解并单纯形法计算得到最优解并且存在且存在Ri0时，则表明原线性规划无可行解。时，则表明原线性规划无可行解。5）退化解的判别：）退化解的判别：存在某个基变量为零的基本可行解。存在某个基变量

25、为零的基本可行解。大大M M法法0,12 3421123min32131321321321xxxxxxxxxxxxxxz基本思想：基本思想：在约束条件中增加人工变量，同时修改目标函数，对目标函数加上具有很大正系数M的惩罚项，为使人工变量不影响目标函数取值，在迭代过程中，应把人工变量从基变量中退出，使其成为非基变量。0,1 2 3 4211 2)(3min72173165321432176321xxxxxxxxxxxxxxxxxMxxxz 其中，M是很大的正数，同时增加两个人工变量。 不容易找到初始可行解找初始可行解找初始可行解icBcBxjjzc11-300MMbi/yibx1X2x3x4x5

26、x6x70X4111-21100011MX6321-40-1103/2MX71(1)0-2000111-3M1-M-3+6M0M00 要求最后得到的基变量中不含人工变量X1进基，x7出基icBcBxjjzc11-300MMbi/yibx1x2x3x4x5x6x7-3X340011/3-2/32/3-5/31X210100-11-211X191002/3-4/34/3-7/30001/31/3M-1/3 M-2/3 可以从表中移去，然后继续求解 经过几次变换，得到基变量为x1，x2，x3两阶段法原理两阶段法原理p两阶段法的第一阶段是用单纯形法 消去人工变量，即把人工变量都变为非基变量，求出原问题

27、的一个基本可行解。p如果第一阶段求解结果表明问题有可行解时，进行第二阶段，就是从得到的基本可行解出发，用单纯形方法求原问题的最优解。5.2 退化LP问题有退化最优解 0,428493max21212121xxxxxxxxz 单纯形法计算中用规则确定换出变量时，有时存在两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于零，这就出现退化解。 这时换出变量 xl =0，迭代后目标函数值不变。这时不同基表示为同一顶点。有人构造了一个特例，当出现退化时，进行多次迭代，而基从B1,B2，又返回到B1，即出现计算过程的循环，便永远达不到最优解。两阶段法举例两阶段法举例0,1 23241123

28、min32131321321321xxxxxxxxxxxxxxz0,1 23 2411 2 min72173165321432176xxxxxxxxxxxxxxxxxz0,1 21 12 2 3 3min5213152541321xxxxxxxxxxxxxz例：例：第一阶段：第一阶段：第二阶段：第二阶段：0, 0, 0,12, 1, 1, 07654321xxxxxxx用单纯形法求得第一阶段的解为：用单纯形法求得第一阶段的解为： 用单纯形法求解规划用单纯形法求解规划问题得最优解问题得最优解 9, 1, 4321xxx目标函数的最优解是目标函数的最优解是2minf Excel Solver（规划

29、求解）（规划求解）G Excel采用了电子表格的形式，帮助管理者采用了电子表格的形式，帮助管理者提高数据管理的能力，因而得以广泛应用。提高数据管理的能力，因而得以广泛应用。GSolver插件专门用于求解带约束的最优化插件专门用于求解带约束的最优化问题。问题。G Solver“规划求解规划求解”，可在，可在Excel的工的工作表中根据对话框提示调用该项功能。作表中根据对话框提示调用该项功能。 可能出现以下情况：可能出现以下情况： 进行进基、出基变换进行进基、出基变换后，虽然改变了基，但没有改变基本可行解（极后，虽然改变了基，但没有改变基本可行解（极点），目标函数当然也不会改进。进行若干次基点），

30、目标函数当然也不会改进。进行若干次基变换后，才脱离退化基本可行解（极点），进入变换后，才脱离退化基本可行解（极点），进入其他基本可行解（极点）。这种情况会增加迭代其他基本可行解（极点）。这种情况会增加迭代次数，使单纯形法收敛的速度减慢。次数，使单纯形法收敛的速度减慢。 在特殊在特殊情况下，退化会出现基的循环，一旦出现这样的情况下，退化会出现基的循环，一旦出现这样的情况，单纯形迭代将永远停留在同一极点上，因情况，单纯形迭代将永远停留在同一极点上，因而无法求得最优解。而无法求得最优解。3.3.单单 纯纯 形形 法法 在单纯形法求解线性规划问题时，一旦出现在单纯形法求解线性规划问题时，一旦出现这种因

31、退化而导致的基的循环，单纯形法就无这种因退化而导致的基的循环，单纯形法就无法求得最优解，这是一般单纯形法的一个缺陷。法求得最优解，这是一般单纯形法的一个缺陷。但是实际上，尽管退化的结构是经常遇到的，但是实际上，尽管退化的结构是经常遇到的，而循环现象在实际问题中出现得较少。尽管如而循环现象在实际问题中出现得较少。尽管如此，人们还是对如何防止出现循环作了大量研此，人们还是对如何防止出现循环作了大量研究。究。19521952年年CharnesCharnes提出了提出了“摄动法摄动法”，19541954年年DantzigDantzig，OrdenOrden和和WolfeWolfe又提出了又提出了“字典

32、序法字典序法”，3.3.单单 纯纯 形形 法法 这些方法都比较复杂，同时也降低了迭代的这些方法都比较复杂，同时也降低了迭代的速度。速度。19761976年，年，BlandBland提出了一个避免循环的新提出了一个避免循环的新方法，其原则十分简单。仅在选择进基变量和方法，其原则十分简单。仅在选择进基变量和出基变量时作了以下规定：出基变量时作了以下规定： 在选择进基变量在选择进基变量时，在所有时，在所有 j j 0 0的非基变量中选取下标最小的非基变量中选取下标最小的进基；的进基； 当有多个变量同时可作为出基变量当有多个变量同时可作为出基变量时，选择下标最小的那个变量出基。这样就可时，选择下标最小

33、的那个变量出基。这样就可以避免出现循环以避免出现循环, ,当然，这样可能使收敛速度降当然，这样可能使收敛速度降低。低。3.3.单单 纯纯 形形 法法加载加载 “ “规划求解规划求解”如果在您的Excel中，没有在“工具”菜单中发现“规划求解”，请在下图所示的界面中点击“加载宏”。加载加载 “ “规划求解规划求解”点击“加载宏”后，显示界面如下：如果列表中没有 “规划求解”，表明您还没有安装该插件。这时，您需要插入Microsoft Office安装盘，选择“添加安装”后选择该插件的安装。第第1 1步步 导入已知数据导入已知数据可采用 复制粘贴 或 直接输入 的方式导入数据。第第2 2步步 确定

34、确定 可变单元格可变单元格 可变单元格存放决策变量的取值，可变单元格数目等于决策变量个数图中，规定B16、C16为可变单元格第第3 3步步 确定确定 目标单元目标单元格格 在目标单元格中，需要填入计算目标函数值的公式。第第4 4步步 确定确定 约束单元约束单元格格 在约束单元格中，需要填入计算约束函数值的公式。第第5 5步步 调用调用 规划求解规划求解 模模块块在上图显示的界面中，需要输入目标单元格、可变单元格，添加约束条件，另外还可能需要进行选项设置。第第6 6步步 填写目标单元格和可变单元格填写目标单元格和可变单元格第第7 7步步 添加约束添加约束第第8 8步步 “ “选项选项”设置设置选

35、择：采用线性模型，假定非负。 如果求解过程在找到结果之前即达到最长运算时间或最大迭代 次数，则会弹出 “显示中间结果” 对话框。第第9 9步步 保存求解结果保存求解结果显示求解结果显示求解结果使用使用ExcelExcel求解例求解例2.102.10 合理利用线材问题合理利用线材问题：如何下料使用如何下料使用材最少。材最少。 配料问题：在原料供应量的限制下配料问题：在原料供应量的限制下如何获取最大利润。如何获取最大利润。 投资问题：从投资项目中选取方案，投资问题：从投资项目中选取方案，使投资回报最大。使投资回报最大。4.线性规划应用 一、线性规划一、线性规划- 产品生产计划：合理利用人产品生产计

36、划：合理利用人力、物力、财力等，使获利最力、物力、财力等，使获利最大。大。 劳动力安排劳动力安排：用最少的劳动用最少的劳动力来满足工作的需要。力来满足工作的需要。 运输问题运输问题：如何制定调运方如何制定调运方案，使总运费最小。案，使总运费最小。4.4.线性规划应用线性规划应用 数学规划的建模有许多共同点，数学规划的建模有许多共同点，要遵循下列原则：要遵循下列原则： (1)(1)容易理解。建立的模型不但容易理解。建立的模型不但要求建模者理解，还应当让有关人员要求建模者理解，还应当让有关人员理解。这样便于考察实际问题与模型理解。这样便于考察实际问题与模型的关系，使得到的结论能够更好地应的关系，使

37、得到的结论能够更好地应用于解决实际问题。用于解决实际问题。 (2)(2)容易查找模型中的错误。这容易查找模型中的错误。这个原则的目的显然与个原则的目的显然与(1)(1)相关。常出相关。常出现的错误有：书写错误和公式错误。现的错误有：书写错误和公式错误。4.4.线性规划应用线性规划应用 (3)(3)容易求解。对线性规划来说，容易求解。对线性规划来说，容易求解问题主要是控制问题的规容易求解问题主要是控制问题的规模，包括决策变量的个数和约束条模，包括决策变量的个数和约束条件的个数。这条原则的实现往往会件的个数。这条原则的实现往往会与与(1)(1)发生矛盾，在实现时需要对两发生矛盾，在实现时需要对两条

38、原则进行统筹考虑。条原则进行统筹考虑。4.4.线性规划应用线性规划应用 建立线性规划模型的过程可以分建立线性规划模型的过程可以分为四个步骤：为四个步骤： (1)(1)设立决策变量；设立决策变量； (2)(2)明确约束条件并用决策变量的明确约束条件并用决策变量的线性等式或不等式表示；线性等式或不等式表示； (3)(3)用决策变量的线性函数表示目用决策变量的线性函数表示目标，并确定是求极大（标，并确定是求极大（MaxMax）还是极）还是极小（小（MinMin）；）； (4)(4)根据决策变量的物理性质研究根据决策变量的物理性质研究变量是否有非负性。变量是否有非负性。4.4.线性规划应用线性规划应用

39、 例例2.:2.:明兴公司生产甲、乙、丙三种明兴公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配产品，都需要经过铸造、机加工和装配 三个车间。甲、乙两种产品的铸件可以外三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如下表。问：本厂铸造才能保证质量。数据如下表。问：公司为了获得最大利润，甲、乙、丙三种公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多造中，由本公司铸造和由外包协作各应多少件？少件？生产计划的问

40、题甲乙丙资源限制铸造工时(小时/件)51078000机加工工时(小时/件)64812000装配工时(小时/件)32210000自产铸件成本(元/件)354外协铸件成本(元/件)56-机加工成本(元/件)213装配成本(元/件)322产品售价(元/件)231816解：解：设设 x x1 1 ,x,x2 2 ,x,x3 3 分别为三道工序都由本公司分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，加工的甲、乙、丙三种产品的件数，x x4 4, , x x5 5 分别分别为由外协铸造再由本公司机加工和装配的甲、乙为由外协铸造再由本公司机加工和装配的甲、乙两种产品的件数。两种产品的件数。 生产计

41、划的问题 求求 x xi i 的利润的利润: :利润利润 = = 售价售价 - - 各成本之和可得到各成本之和可得到 x xi i（i i=1,2,3,4,5=1,2,3,4,5）的利润分别为）的利润分别为1515、1010、7 7、1313、9 9元。元。 这样我们建立如下数学模型：这样我们建立如下数学模型： 目标函数目标函数: Max 15: Max 15x x1 1+10+10 x x2 2+7+7x x3 3+13+13x x4 4+9+9x x5 5 约束条件：约束条件： s.t. 5s.t. 5x x1 1+10+10 x x2 2+7+7x x3 3 8000 8000 6 6x

42、 x1 1+4+4x x2 2+8+8x x3 3+6+6x x4 4+4+4x x5 5 1200012000 3 3x x1 1+2+2x x2 2+2+2x x3 3+3+3x x4 4+2+2x x5 5 10000 10000 x x1 1, ,x x2 2, ,x x3 3, ,x x4 4, ,x x5 5 0 0 生产计划的问题生产计划的问题 例例2.:2.:永久机械厂生产永久机械厂生产、三种产品，三种产品，均要经过均要经过 A A、B B 两道工序加工。假设有两种两道工序加工。假设有两种规格的设备规格的设备A A1 1、A A2 2能完成能完成 A A 工序；有三种规工序；有

43、三种规格的设备格的设备B B1 1、 B B2 2 、B B3 3能完成能完成 B B 工序。工序。可可在在 A A、B B的任何规格的设备上加工；的任何规格的设备上加工； 可在可在任意规格的任意规格的A A设备上加工，但对设备上加工，但对B B工序工序, ,只能只能在在B B1 1设备上加工；设备上加工； 只能在只能在A A2 2与与B B2 2设备上加设备上加工；数据如下表。问：为使该厂获得最大利工；数据如下表。问：为使该厂获得最大利润，应如何制定产品加工方案？润，应如何制定产品加工方案？ 生产计划的问题生产计划的问题解：解：设设 x xijkijk 表示第表示第 i i 种产品，在第种产

44、品，在第 j j 种工种工序上的第序上的第 k k 种设备上加工的数量种设备上加工的数量. . 利润利润 = = （销售单价（销售单价 - - 原料单价）原料单价） 产品件数产品件数 之和之和 - - （每（每台时的设备费用台时的设备费用设备实际使用的总台时数）之和设备实际使用的总台时数）之和。 生产计划的问题生产计划的问题这样我们建立如下的数学模型这样我们建立如下的数学模型: :MaxMax 0.75x0.75x111111+0.7753x+0.7753x112112+1.15x+1.15x211211+1.3611x+1.3611x212212+1.9148x+1.9148x312312-

45、 -0.375x0.375x121121-0.5x-0.5x221221-0.4475x-0.4475x122122-1.2304x-1.2304x322322-0.35x-0.35x123123 s.ts.t 5x 5x111111+10 x+10 x2112116000 6000 （ 设备设备 A A1 1 ） 7x7x112112+9x+9x212212+12x+12x3123121000010000（ 设备设备 A A2 2 ） 6x6x121121+ 8x+ 8x221221 4000 ( 4000 ( 设备设备 B B1 1 ） 4x4x122122+11x+11x32232270

46、00 ( 7000 ( 设备设备 B B2 2 ） 7x7x123123 4000 4000 （ 设备设备 B B3 3 ）生产计划的问题生产计划的问题x x111111+ + x x112112- - x x121121- - x x122122- - x x123123 = 0 = 0 (产品在产品在A A、B B工序加工的数量相等）工序加工的数量相等）x x211211+ + x x212212- - x x221221 = 0 = 0 (产品在产品在A A、B B工序加工的数量相等）工序加工的数量相等）x x312 312 - - x x322322 = 0 = 0(产品在产品在A A

47、、B B工序加工的数量相等）工序加工的数量相等）x xijkijk0, 0, i i=1,2,3; =1,2,3; j j=1,2; =1,2; k k=1,2,3=1,2,3 生产计划的问题生产计划的问题 例例2.2.：某昼夜服务的公交线路每天各时间段内所需司某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：机和乘务人员数如下： 班次时间所需人数16：00 10：0060210：00 14：0070314：00 18：0060418：00 22：0050522： 2：002062：00 6：0030 人力资源分配的问题设司机和乘务人员分别在各时间段一开始时设司机和乘务人员分别在各时

48、间段一开始时上班，并连续工作上班，并连续工作8h8h，问该公交线路怎样安，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员配备最少司机和乘务人员? ? 解：设解：设 x xi i 表示第表示第i i班次时开始上班的司机和乘务人员数班次时开始上班的司机和乘务人员数, ,这样我们建立如下的数学模型这样我们建立如下的数学模型。目标函数目标函数：Min Min x x1 1 + + x x2 2 + + x x3 3 + + x x4 4 + + x x5 5 + + x x6 6 约束条件约束条件：s.ts.t. . x x1 1

49、+ + x x6 6 60 60 x x1 1 + + x x2 2 70 70 x x2 2 + + x x3 3 60 60 x x3 3 + + x x4 4 50 50 x x4 4 + + x x5 5 20 20 x x5 5 + + x x6 6 30 30 x x1 1, ,x x2 2, ,x x3 3, ,x x4 4, ,x x5 5, ,x x6 6 0 0 人力资源分配的问题人力资源分配的问题例例2 2: :某工厂要做某工厂要做100100套钢架，每套用长为套钢架，每套用长为2.9 m, 2.1m, 1.5m2.9 m, 2.1m, 1.5m的圆钢各一根。已知原料每根

50、长的圆钢各一根。已知原料每根长7.4 m7.4 m，问：应如何下料，问：应如何下料，可使所用原料最省？可使所用原料最省？方案 1方案 2方案 3方案 4方案 5方案 6方案 7方案 82.9 m120101002.1 m002211301.5 m31203104合计7.47.37.27.16.66.56.36.0剩余料头00.10.20.30.80.91.11.4套裁下料问题套裁下料问题解解: :考虑下列各种下料方案（按一种逻辑顺序给出）考虑下列各种下料方案（按一种逻辑顺序给出）方案 1方案 2方案 3方案 4方案 5方案 6方案 7方案 82.9 m211100002.1 m02103210