线性规划和单纯形法课件

《线性规划和单纯形法课件》由会员分享，可在线阅读，更多相关《线性规划和单纯形法课件（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元。公司应各生产多少中档和高档拉杆箱才能使公司利润最大？可以通过线性规划求解可以通过线性规划求解！线性规划模型的建立线性规划模型的建立 设生产中、高档拉杆箱数量分别为： 称为决策变量。目标函数目标函数约束条件约束条件一般线性规划模型Maxz=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxn=b1( 0)a21x1+a22x2+a2nxn=b2( 0):am1x1+

4、am2x2+amnxn=bm( 0)x1,x2,xn 0s.t. 为约束限制（Subject to）的缩写(LP)x1.xnb1.bma11 a1nam1 amnx =b =A = c =其中c=(c1,c2,cn)，称为价值系数向量；称为资源限制向量 X=(x1,x2,xn)T 称为决策变量向量称为技术系数矩阵(也称消耗系数矩阵)一般线性规划模型线性规划模型的标准形式线性规划模型的标准形式MaxZ=c1x1+c2x2+cnxnSubjectto(s.t.)a11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2am1x1+am2x2+amnxn=bmx x1 1 0,

5、 0, x x2 2 0, 0, , , x xn n 0为了讨论方便，把最大化、等式约束型的线性规划称为线为了讨论方便，把最大化、等式约束型的线性规划称为线性规划的标准型，即性规划的标准型，即标准化标准化原问题原问题标准化方法标准化方法目标函数目标函数Max f(x)Max f(x)Min f(x)Max f(x)约束条件约束条件引入松弛变量和人工变量引入松弛变量, 不变变量变量 不变对某个对某个是任意的 线性规划模型的标准化线性规划模型的标准化例例: :将如下线性规划模型标准化：将如下线性规划模型标准化：min z= x1 + 5 x2 - 8 x3 - x4s.t. 2 x1 - 3 x

6、2 + 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取值无约束。取值无约束。 目标优化标准化目标优化标准化线性规划模型的标准化Maxz2=-x1-5y2+5y3+8x3+x4s.t. 2 x1 - 3 y2+3y3 + x3 + x4 20

7、 -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 =-x1-5y2+5y3+8x3+x4 s.t. 2 x1 - 3 y2+3y3 + x3 + x4

8、+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 , x4 ,y2,y3 0 p可行解可行解:满足所有约束条件的解x=（x1，x2，.，xn），所

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

10、划实例与模型线性规划实例与模型p线性规划的图解法与基本性质线性规划的图解法与基本性质线性规划的图解法线性规划的图解法 当只有两个决策变量当只有两个决策变量时，可用图解法求解！时，可用图解法求解！例例：用图解法求解以下线形规划问题。 max z=4x1+3x2 s.t. x16 2x28 2x1+3x218 x10，x20x1 x2 L3：2x1+3x2=18可行域可行域L1：x1=6L2：x2=4最优解B4x1+3x2解的特殊情况解的特殊情况多个最优解多个最优解解的特殊情况解的特殊情况无可行解无可行解解的特殊情况解的特殊情况无界解无界解线性规划的基本性质线性规划的基本性质 X可行域内部的点 可

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

12、的基本性质 定理定理2.12.1：线性规划的可行域：线性规划的可行域： 是凸集（凸多面体）。是凸集（凸多面体）。 引理引理2.12.1：线性规划的可行解线性规划的可行解 为基本可行解的为基本可行解的充分必要条件是充分必要条件是x x的正分量所对应的系数列向量是线性无关的，的正分量所对应的系数列向量是线性无关的，即每个正分量都是一个基变量即每个正分量都是一个基变量。 定理定理2.22.2：线性规划问题的基本可行解线性规划问题的基本可行解x x对应于可行域的顶点对应于可行域的顶点 定理定理2.32.3：若线性规划有最优解，则最优解必在可行域的顶点上若线性规划有最优解，则最优解必在可行域的顶点上达到

13、。达到。目目 录录p线性规划实例与模型线性规划实例与模型p线性规划的图解法线性规划的图解法p单纯形法原理单纯形法原理一、初始基本可行解的确定一、初始基本可行解的确定p考虑如下形式的线性规划问题考虑如下形式的线性规划问题max z=c1x1+c2x2+.+cnxn s.t. a11x1+a12x2+a1nxnb1 a21x1+a22x2+a2nxnb2 (2.17） . am1x1+am2x2+ +amnxnbm x1，x2，.，xn0 （2.18）对每个不等式约束引入一个非负松弛变量，得标准形式：对每个不等式约束引入一个非负松弛变量，得标准形式：max z=c1x1+c2x2+.+cn xns

14、.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+m0是线性规划是线性规划(2.19)(2.19)的一个可行基。令的一个可行基。令 得得由此得到一个初始基本可行解为由此得到一个初始基本可行解为二、最优性检验二、最优性检验 p定理定理2.42.4： 在最大化问题中，对于某个基本可行解，如果所有 的 ，则这个基本可行解是最优解。 在最小化问题中，对于某个基本可行解，如果所有 的 ，则这个基本可行解是最优解。单纯形法求解步骤单纯形法求解步骤p将所给问题化为

15、标准形将所给问题化为标准形p找出一个初始可行基找出一个初始可行基, ,建立初始单纯形表建立初始单纯形表p检查所有检验数检查所有检验数( (若全为非负若全为非负, ,则已得到最优解则已得到最优解, ,计计算停止算停止. .否则继续下一步否则继续下一步) )p考察是否无解考察是否无解( (若是若是, ,计算停止计算停止, ,否则继续下一步否则继续下一步) )p确定入基变量确定入基变量, ,出基变量出基变量p对初始单纯形表进行单纯形变换对初始单纯形表进行单纯形变换单纯形方法的一般步骤单纯形方法的一般步骤确定一个初始可行角点确定一个初始可行角点根据某种法则进行角点根据某种法则进行角点的最优性判断的最优

16、性判断不是最优角点不是最优角点是最优角点是最优角点考察与当前角点相邻的考察与当前角点相邻的 “ “更好更好”的的一个角点，并置为当前角点。一个角点，并置为当前角点。根据某种法则进行根据某种法则进行LPLP的无的无界或不可行判断界或不可行判断无界或不可行无界或不可行还不能做出判断还不能做出判断求求解解结结束束单纯形法举例单纯形法举例解：引进松驰变量x3, x4，化为标准形得： 4 3 0 0 CBXBb x1 x2 x3 x4 b/y00x3x42426 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 0CBXBb x

17、1 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/3 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=36 4 3 0 0CBXBb x1 x2 x3 x4 b/y04x3x120/326/3 0 5/ 3 1 -2/3 4 1 2/3 0

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

19、矩阵中不存在系数矩阵中不存在单位矩阵，无法建单位矩阵，无法建立初始单纯形表。立初始单纯形表。单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法p故人为添加两个单位向量，得到人工变量单纯形法数学模故人为添加两个单位向量，得到人工变量单纯形法数学模型：型：其其中中：M是是一一个个很很大大的的抽抽象象的的数数，不不需需要要给给出出具具体体的的数数值值，可可以以理理解解为为它它能能大大于于给给定定的的任任何何一一个个确确定定数数值值；再再用用前前面面介介绍的单纯形法求解该模型，计算结果见下表。绍的单纯形法求解该模型，计算结果见下表。 单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量

20、法cj32-100-M-MCBXBbx1x2x3x4x5x6x7i-Mx64-431-101040x5101-1201005-Mx712-21000113-2M2+M-1+2M-M0000x63-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/3单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法解的判别：解的判别：1）唯一最优

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

22、并且存在且存在Ri0时，则表明原线性规划无可行解。时，则表明原线性规划无可行解。5）退化解的判别：）退化解的判别：存在某个基变量为零的基本可行解。存在某个基变量为零的基本可行解。大大M M法法基本思想：基本思想：在约束条件中增加人工变量，同时修改目标函数，对目标函数加上具有很大正系数M的惩罚项，为使人工变量不影响目标函数取值，在迭代过程中，应把人工变量从基变量中退出，使其成为非基变量。 其中，M是很大的正数，同时增加两个人工变量。 不容易找到初始可行解找初始可行解找初始可行解11-300MMbi/yibx1X2x3x4x5x6x70X4111-21100011MX6321-40-1103/2M

23、X71(1)0-2000111-3M1-M-3+6M0M00 要求最后得到的基变量中不含人工变量X1进基，x7出基11-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两阶段法的第一阶段是用单纯形法 消去人工变量，即把人工变量都变为非基变量，求出原问题的一个基本可行解。p如果第一阶段求解结果表明问题有可行解时，进行第二阶段，就是从得到的基本可

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

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

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

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

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

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

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

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

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

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

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

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

36、1 ,x,x2 2 ,x,x3 3 分别为三道工序都由本公司分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，加工的甲、乙、丙三种产品的件数，x x4 4, , x x5 5 分别分别为由外协铸造再由本公司机加工和装配的甲、乙为由外协铸造再由本公司机加工和装配的甲、乙两种产品的件数。两种产品的件数。 生产计划的问题 求求 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元。元。 这样我们建立如下数学模型：

37、这样我们建立如下数学模型： 目标函数目标函数: Max 15: Max 15x x1 1+10+10x x2 2+7+7x x3 3+13+13x x4 4+9+9x x5 5 约束条件：约束条件： s.t. 5s.t. 5x x1 1+10+10x x2 2+7+7x x3 3 8000 8000 6 6x 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,

38、,x x4 4, ,x x5 5 0 0 生产计划的问题生产计划的问题 例例2.:2.:永久机械厂生产永久机械厂生产、三种产品，三种产品，均要经过均要经过 A A、B B 两道工序加工。假设有两种两道工序加工。假设有两种规格的设备规格的设备A A1 1、A A2 2能完成能完成 A A 工序；有三种规工序；有三种规格的设备格的设备B B1 1、 B B2 2 、B B3 3能完成能完成 B B 工序。工序。可可在在 A A、B B的任何规格的设备上加工；的任何规格的设备上加工； 可在可在任意规格的任意规格的A A设备上加工，但对设备上加工，但对B B工序工序, ,只能只能在在B B1 1设备上

39、加工；设备上加工； 只能在只能在A A2 2与与B B2 2设备上加设备上加工；数据如下表。问：为使该厂获得最大利工；数据如下表。问：为使该厂获得最大利润，应如何制定产品加工方案？润，应如何制定产品加工方案？ 生产计划的问题生产计划的问题解：解：设设 x xijkijk 表示第表示第 i i 种产品，在第种产品，在第 j j 种工序种工序上的第上的第 k k 种设备上加工的数量种设备上加工的数量. . 利润利润 = = （销售（销售单价单价 - - 原料单价）原料单价） 产品件数产品件数 之和之和 - - （每台时的设（每台时的设备费用备费用设备实际使用的总台时数）之和设备实际使用的总台时数）

40、之和。 生产计划的问题生产计划的问题这样我们建立如下的数学模型这样我们建立如下的数学模型: :MaxMax 0.75x0.75x111111+0.7753x+0.7753x112112+1.15x+1.15x211211+1.3611x+1.3611x212212+1.9148x+1.9148x312312- -0.375x0.375x121121-0.5x-0.5x221221-0.4475x-0.4475x122122-1.2304x-1.2304x322322-0.35x-0.35x123123 s.ts.t 5x 5x111111+10x+10x2112116000 6000 （ 设备

41、设备 A A1 1 ） 7x7x112112+9x+9x212212+12x+12x3123121000010000（ 设备设备 A A2 2 ） 6x6x121121+ 8x+ 8x221221 4000 ( 4000 ( 设备设备 B B1 1 ） 4x4x122122+11x+11x3223227000 ( 7000 ( 设备设备 B B2 2 ） 7x7x123123 4000 4000 （ 设备设备 B B3 3 ）生产计划的问题生产计划的问题x x111111+ + x x112112- - x x121121- - x x122122- - x x123123 = 0 = 0 (

42、产品在产品在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、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.：某昼夜服务的公交线路每天各时间段内所需司某昼夜服务的公交线路每天各时间段

43、内所需司机和乘务人员数如下：机和乘务人员数如下： 人力资源分配的问题设司机和乘务人员分别在各时间段一开始时设司机和乘务人员分别在各时间段一开始时上班，并连续工作上班，并连续工作8h8h，问该公交线路怎样安问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员配备最少司机和乘务人员? ? 解：设解：设 x xi i 表示第表示第i i班次时开始上班的司机和乘务人员数班次时开始上班的司机和乘务人员数, ,这样我们建立如下的数学模型这样我们建立如下的数学模型。目标函数目标函数：Min Min x x1 1 + + x x2 2 + + x

44、 x3 3 + + x x4 4 + + x x5 5 + + x x6 6 约束条件约束条件：s.ts.t. . x x1 1 + + 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

45、套钢架，每套用长为套钢架，每套用长为2.9 m, 2.1m, 1.5m2.9 m, 2.1m, 1.5m的的圆钢各一根。已知原料每根长圆钢各一根。已知原料每根长7.4 m7.4 m，问：应如何下料，可问：应如何下料，可使所用原料最省？使所用原料最省？套裁下料问题套裁下料问题解解: :考虑下列各种下料方案（按一种逻辑顺序给出）考虑下列各种下料方案（按一种逻辑顺序给出）把各种下料方案按剩余料头从小到大顺序列出把各种下料方案按剩余料头从小到大顺序列出假设假设 x x1 1, ,x x2 2, ,x x3 3, ,x x4 4, ,x x5 5 分别为上面前分别为上面前 5 5 种方案下料的原材料根数

46、。我们建立种方案下料的原材料根数。我们建立如下的数学模型。如下的数学模型。目标函数：目标函数： Min Min x x1 1 + + x x2 2 + + x x3 3 + + x x4 4 + + x x5 5 约束条件：约束条件： s.t. s.t. x x1 1 + 2 + 2x x2 2 + + x x4 4 100 100 2 2x x3 3 + 2+ 2x x4 4 + + x x5 5 100 100 3 3x x1 1 + + x x2 2 + 2 + 2x x3 3+ 3+ 3x x5 5 100 100 x x1 1, ,x x2 2, ,x x3 3, ,x x4 4, ,x x5 5 0 0套裁下料问题