线性规划和单纯形法幻灯片.ppt

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

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

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

3、析生产过程，得出：生产中档拉杆箱需要用7/10小时剪裁、5/10小时缝合、1小时定型、1/10小时检验包装；生产高档拉杆箱则需用1小时剪裁、5/6小时缝合、2/3小时定型、1/4小时检验包装。由于公司生产能力有限，3月内各部的最大生产时间为剪裁部630小时、缝合部600小时、定型部708小时、检验包装部135小时。通过市场调研部和会计部的调查核算得出结论：生产中档拉杆箱的利润是10元，高档拉杆箱的利润是9元。公司应各生产多少中档和高档拉杆箱才能使公司利润最大？可以通过线性规划求解可以通过线性规划求解！第5页，共77页，编辑于2022年，星期一线性规划模型的建立线性规划模型的建立 设生产中、高档

4、拉杆箱数量分别为：称为决策变量。目标函数目标函数约束条件约束条件第6页，共77页，编辑于2022年，星期一一般线性规划模型Maxz=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=其中c=(c1,c2,cn)，称为价值系数向量；第7页，共77页，编辑于2022年，星期一称为资源限制向量 X=(x1,x2,xn)T 称为决策变量向量

5、称为技术系数矩阵(也称消耗系数矩阵)一般线性规划模型第8页，共77页，编辑于2022年，星期一线性规划模型的标准形式线性规划模型的标准形式MaxZ=c1x1+c2x2+cnxnSubjectto(s.t.)a11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2am1x1+am2x2+amnxn=bmx x1 1 0,0,x x2 2 0,0,x xn n 0p为了讨论方便，把最大化、等式约束型的线性规划称为线性规划的标为了讨论方便，把最大化、等式约束型的线性规划称为线性规划的标准型，即准型，即第9页，共77页，编辑于2022年，星期一标准化标准化原问题原问题标准化方法

6、标准化方法目标函数目标函数Max f(x)Max f(x)Min f(x)Max f(x)约束条件约束条件引入松弛变量和人工变量引入松弛变量,不变变量变量 不变对某个对某个是任意的 第10页，共77页，编辑于2022年，星期一线性规划模型的标准化线性规划模型的标准化p例例:将如下线性规划模型标准化：将如下线性规划模型标准化：min 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-

7、3 x2+x3+x4 20 x1+2 x2+3 x3-x4 30 2x2+2 x3+3 x4-50 x1,x3,x4 0，x2取值无约束。取值无约束。目标优化标准化目标优化标准化第11页，共77页，编辑于2022年，星期一线性规划模型的标准化Maxz2=-x1-5y2+5y3+8x3+x4s.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

8、+x4 20 x1+2 x2+3 x3-x4 30 2x2+2 x3+3 x4-50 x1,x3,x4 0，x2取值无约束取值无约束 第12页，共77页，编辑于2022年，星期一线性规划模型的标准化Max z2=-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+

9、x4 20 -x1-2 y2+2y3-3 x3+x4 -30 -2y2+2y3-2 x3-3 x4 50 x1,x3,x4,y2,y3 0 第13页，共77页，编辑于2022年，星期一p可行解可行解:满足所有约束条件的解x=（x1，x2，.，xn），所有可行解的集合称为可行域可行域。p基基：设A是约束方程组的mn阶系数矩阵，秩为m，是A中阶非奇异子矩阵（即 ），则称是线性规划问题的一个基矩阵基矩阵，简称基基。B中的列向量称为基向量基向量，与基向量对应的变量x称为基变量基变量，其它变量称为非基变量非基变量。p基本解基本解：令非基变量值为0，由Ax=b可求出一个解，这个解x称为基本解基本解。p基本

10、可行解基本可行解：满足非负条件的基本解称为基本可行解基本可行解。p最优解最优解：使目标函数达到最优值的可行解称为最优解最优解。线性规划的解线性规划的解 第14页，共77页，编辑于2022年，星期一可行解、基本解、基本可行解的关系可行解可行解基本解基本解基本可行解基本可行解第15页，共77页，编辑于2022年，星期一目目 录录p线性规划实例与模型线性规划实例与模型p线性规划的图解法与基本性质线性规划的图解法与基本性质第16页，共77页，编辑于2022年，星期一线性规划的图解法线性规划的图解法 当只有两个决策变量时，当只有两个决策变量时，可用图解法求解！可用图解法求解！例例：用图解法求解以下线形规

11、划问题。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第17页，共77页，编辑于2022年，星期一解的特殊情况解的特殊情况多个最优解多个最优解第18页，共77页，编辑于2022年，星期一解的特殊情况解的特殊情况无可行解无可行解第19页，共77页，编辑于2022年，星期一解的特殊情况解的特殊情况无界解无界解第20页，共77页，编辑于2022年，星期一线性规划的基本性质线性规划的基本性质 X可行域内部的点 可行解?是是 最优解?不不 若线性规划有最若线性规

12、划有最优解，则最优解必在可行域的优解，则最优解必在可行域的顶点上达到。顶点上达到。第21页，共77页，编辑于2022年，星期一凸集的概念凸集的概念 p凸集是线性规划中一个很重要的概念，凸集的一般定义为：凸集是线性规划中一个很重要的概念，凸集的一般定义为：如果在集合如果在集合C C中任意取两个点中任意取两个点x x1 1，x x2 2，其连线上的所有点也，其连线上的所有点也都在集合都在集合C C中，则称集合中，则称集合C C为凸集合。用数学解析式表达为：为凸集合。用数学解析式表达为：对任意对任意 ，均有，均有 ，则称，则称C C是是凸集合。凸集合。非凸集非凸集非凸集非凸集凸集凸集第22页，共77

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

14、优解，则最优解必在可行域的顶点上达到。第23页，共77页，编辑于2022年，星期一目目 录录p线性规划实例与模型线性规划实例与模型p线性规划的图解法线性规划的图解法p单纯形法原理单纯形法原理第24页，共77页，编辑于2022年，星期一一、初始基本可行解的确定一、初始基本可行解的确定p考虑如下形式的线性规划问题考虑如下形式的线性规划问题max z=c1x1+c2x2+.+cnxn s.t.a11x1+a12x2+a1nxnb1 a21x1+a22x2+a2nxnb2 (2.17）.am1x1+am2x2+amnxnbm x1，x2，.，xn0 （2.18）对每个不等式约束引入一个非负松弛变量，得

15、标准形式：对每个不等式约束引入一个非负松弛变量，得标准形式：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+m0第25页，共77页，编辑于2022年，星期一是线性规划是线性规划(2.19)(2.19)的一个可行基。令的一个可行基。令 得得由此得到一个初始基本可行解为由此得到一个初始基本可行解为第26页，共77页，编辑于2022年，星期一二、最优性检验二、最优性检验 p定理定理2.42.4：在最大化问题中，对于

16、某个基本可行解，如果所有 的 ，则这个基本可行解是最优解。在最小化问题中，对于某个基本可行解，如果所有 的 ，则这个基本可行解是最优解。第27页，共77页，编辑于2022年，星期一单纯形法求解步骤单纯形法求解步骤p将所给问题化为标准形将所给问题化为标准形p找出一个初始可行基找出一个初始可行基,建立初始单纯形表建立初始单纯形表p检查所有检验数检查所有检验数(若全为非负若全为非负,则已得到最优解则已得到最优解,计算计算停止停止.否则继续下一步否则继续下一步)p考察是否无解考察是否无解(若是若是,计算停止计算停止,否则继续下一步否则继续下一步)p确定入基变量确定入基变量,出基变量出基变量p对初始单纯

17、形表进行单纯形变换对初始单纯形表进行单纯形变换第28页，共77页，编辑于2022年，星期一单纯形方法的一般步骤单纯形方法的一般步骤确定一个初始可行角点确定一个初始可行角点根据某种法则进行角点的根据某种法则进行角点的最优性判断最优性判断不是最优角点不是最优角点是最优角点是最优角点考察与当前角点相邻的考察与当前角点相邻的 “更好更好”的一个的一个角点，并置为当前角点。角点，并置为当前角点。根据某种法则进行根据某种法则进行LPLP的无界或不的无界或不可行判断可行判断无界或不可行无界或不可行还不能做出判断还不能做出判断求求解解结结束束第29页，共77页，编辑于2022年，星期一单纯形法举例单纯形法举例

18、解：引进松驰变量x3,x4，化为标准形得：第30页，共77页，编辑于2022年，星期一 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 0CBXBb 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/3第31页，共77页，编辑于2022年，星期一 4 3 0 0CBXBb x1 x2 x3 x434x2x146 0 1 3/5 -2/5 1 0

19、 -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 1/3 13 -104/3 0 1/3 0 -4/3第32页，共77页，编辑于2022年，星期一单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法p人工变量法：p前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中

20、有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为人工变量，构成的可行基称为人工基，用大M法或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量法。第33页，共77页，编辑于2022年，星期一单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法p例1.10 用大M法解下列线性规划解：首先将数学模型化为标准形式解：首先将数学模型化为标准形式系数矩阵中不存在系数矩阵中不存在单位矩阵，无法建单位矩阵，无法建立初始单纯形表。立初始单纯形表。第34页，共77页，编辑于2022年，星期一单纯形法的进一步讨论人工变

21、量法单纯形法的进一步讨论人工变量法p故人为添加两个单位向量，得到人工变量单纯形法数学模故人为添加两个单位向量，得到人工变量单纯形法数学模型：型：其其中中：M是是一一个个很很大大的的抽抽象象的的数数，不不需需要要给给出出具具体体的的数数值值，可可以以理理解解为为它它能能大大于于给给定定的的任任何何一一个个确确定定数数值值；再再用用前前面面介介绍绍的的单单纯纯形形法法求解该模型，计算结果见下表。求解该模型，计算结果见下表。第35页，共77页，编辑于2022年，星期一单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法cj32-100-M-MCBXBbx1x2x3x4x5x6x7i-Mx64

22、-431-101040 x5101-1201005-Mx712-21000113-2M2+M-1+2M-M0000 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/3第36页，共77页，编辑于2022年，星期一单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法解的判别：解的判别：1）唯一最优解判别：最优表中所有非基变量

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

24、明原线性规划无可行解。时，则表明原线性规划无可行解。5）退化解的判别：存在某个基变量为零的基本可行解。）退化解的判别：存在某个基变量为零的基本可行解。第37页，共77页，编辑于2022年，星期一大大M M法法基本思想：基本思想：在约束条件中增加人工变量，同时修改目标函数，对目标函数加上具有很大正系数M的惩罚项，为使人工变量不影响目标函数取值，在迭代过程中，应把人工变量从基变量中退出，使其成为非基变量。其中，M是很大的正数，同时增加两个人工变量。不容易找到初始可行解第38页，共77页，编辑于2022年，星期一找初始可行解找初始可行解11-300MMbi/yibx1X2x3x4x5x6x70X41

25、11-21100011MX6321-40-1103/2MX71(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第39页，共77页，编辑于2022年，星期一两阶段法原理两阶段法原理p两阶段法的第一阶段是用单纯形法 消去人工变量，即把人工变量都变为非基变量，求

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

27、7页，编辑于2022年，星期一两阶段法举例两阶段法举例例：例：第一阶段：第一阶段：第二阶段：第二阶段：用单纯形法求得第一阶段的解为：用单纯形法求得第一阶段的解为：用单纯形法求解规划问题用单纯形法求解规划问题得最优解得最优解 目标函数的最优解是目标函数的最优解是 第43页，共77页，编辑于2022年，星期一ExcelSolver（规划求解）（规划求解）nExcel采用了电子表格的形式，帮助管理者提采用了电子表格的形式，帮助管理者提高数据管理的能力，因而得以广泛应用。高数据管理的能力，因而得以广泛应用。nSolver插件专门用于求解带约束的最优化问题。插件专门用于求解带约束的最优化问题。nSolv

28、er“规划求解规划求解”，可在，可在Excel的工作的工作表中根据对话框提示调用该项功能。表中根据对话框提示调用该项功能。第44页，共77页，编辑于2022年，星期一 可可能能出出现现以以下下情情况况：进进行行进进基基、出出基基变变换换后后，虽虽然然改改变变了了基基，但但没没有有改改变变基基本本可可行行解解（极极点点），目目标标函函数数当当然然也也不不会会改改进进。进进行行若若干干次次基基变变换换后后，才才脱脱离离退退化化基基本本可可行行解解（极极点点），进进入入其其他他基基本本可可行行解解（极极点点）。这这种种情情况况会会增增加加迭迭代代次次数数，使使单单纯纯形形法法收收敛敛的的速速度度减减

29、慢慢。在在特特殊殊情情况况下下，退退化化会会出出现现基基的的循循环环，一一旦旦出出现现这这样样的的情情况况，单单纯纯形形迭迭代代将将永远停留在同一极点上，因而无法求得最优解。永远停留在同一极点上，因而无法求得最优解。3.3.单单 纯纯 形形 法法第45页，共77页，编辑于2022年，星期一 在单纯形法求解线性规划问题时，一旦出现这种因退在单纯形法求解线性规划问题时，一旦出现这种因退化而导致的基的循环，单纯形法就无法求得最优解，这化而导致的基的循环，单纯形法就无法求得最优解，这是一般单纯形法的一个缺陷。但是实际上，尽管退化的是一般单纯形法的一个缺陷。但是实际上，尽管退化的结构是经常遇到的，而循环

30、现象在实际问题中出现得较结构是经常遇到的，而循环现象在实际问题中出现得较少。尽管如此，人们还是对如何防止出现循环作了大量少。尽管如此，人们还是对如何防止出现循环作了大量研究。研究。19521952年年CharnesCharnes提出了提出了“摄动法摄动法”，19541954年年DantzigDantzig，OrdenOrden和和WolfeWolfe又提出了又提出了“字典序法字典序法”，3.3.单单 纯纯 形形 法法第46页，共77页，编辑于2022年，星期一 这些方法都比较复杂，同时也降低了迭代的速度。这些方法都比较复杂，同时也降低了迭代的速度。19761976年，年，BlandBland提

31、出了一个避免循环的新方法，其原提出了一个避免循环的新方法，其原则十分简单。仅在选择进基变量和出基变量时作了则十分简单。仅在选择进基变量和出基变量时作了以下规定：以下规定：在选择进基变量时，在所有在选择进基变量时，在所有 j j 0 0的非基变量中选取下标最小的进基；的非基变量中选取下标最小的进基；当有多个当有多个变量同时可作为出基变量时，选择下标最小的那变量同时可作为出基变量时，选择下标最小的那个变量出基。这样就可以避免出现循环个变量出基。这样就可以避免出现循环,当然，这当然，这样可能使收敛速度降低。样可能使收敛速度降低。3.3.单单 纯纯 形形 法法第47页，共77页，编辑于2022年，星期

32、一加载加载 “规划求解规划求解”如果在您的Excel中，没有在“工具”菜单中发现“规划求解”，请在下图所示的界面中点击“加载宏”。第48页，共77页，编辑于2022年，星期一加载加载 “规划求解规划求解”点击“加载宏”后，显示界面如下：如果列表中没有“规划求解”，表明您还没有安装该插件。这时，您需要插入Microsoft Office安装盘，选择“添加安装”后选择该插件的安装。第49页，共77页，编辑于2022年，星期一第第1 1步步 导入已知数据导入已知数据可采用 复制粘贴 或 直接输入 的方式导入数据。第50页，共77页，编辑于2022年，星期一第第2 2步步 确定确定 可变单元格可变单元

33、格 可变单元格存放决策变量的取值，可变单元格数目等于决策变量个数图中，规定B16、C16为可变单元格第51页，共77页，编辑于2022年，星期一第第3 3步步 确定确定 目标单元格目标单元格 在目标单元格中，需要填入计算目标函数值的公式。第52页，共77页，编辑于2022年，星期一第第4 4步步 确定确定 约束单元格约束单元格 在约束单元格中，需要填入计算约束函数值的公式。第53页，共77页，编辑于2022年，星期一第第5 5步步 调用调用 规划求解规划求解 模块模块在上图显示的界面中，需要输入目标单元格、可变单元格，添加约束条件，另外还可能需要进行选项设置。第54页，共77页，编辑于2022

34、年，星期一第第6 6步步 填写目标单元格和可变单元格填写目标单元格和可变单元格第55页，共77页，编辑于2022年，星期一第第7 7步步 添加约束添加约束第56页，共77页，编辑于2022年，星期一第第8 8步步 “选项选项”设置设置选择：采用线性模型，假定非负。如果求解过程在找到结果之前即达到最长运算时间或最大迭代 次数，则会弹出“显示中间结果”对话框。第57页，共77页，编辑于2022年，星期一第第9 9步步 保存求解结果保存求解结果第58页，共77页，编辑于2022年，星期一显示求解结果显示求解结果第59页，共77页，编辑于2022年，星期一使用使用ExcelExcel求解例求解例2.1

35、02.10第60页，共77页，编辑于2022年，星期一第61页，共77页，编辑于2022年，星期一 合理利用线材问题合理利用线材问题：如何下料使用材最如何下料使用材最少。少。配料问题：在原料供应量的限制下如何配料问题：在原料供应量的限制下如何获取最大利润。获取最大利润。投资问题：从投资项目中选取方案，投资问题：从投资项目中选取方案，使投资回报最大。使投资回报最大。4.线性规划应用 一、线性规划一、线性规划-第62页，共77页，编辑于2022年，星期一 产品生产计划：合理利用人产品生产计划：合理利用人力、物力、财力等，使获利最大。力、物力、财力等，使获利最大。劳动力安排劳动力安排：用最少的劳动用

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

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

38、应用线性规划应用第65页，共77页，编辑于2022年，星期一 建建立立线线性性规规划划模模型型的的过过程程可可以以分分为四个步骤：为四个步骤：(1)(1)设立决策变量；设立决策变量；(2)(2)明明确确约约束束条条件件并并用用决决策策变变量量的的线线性等式或不等式表示；性等式或不等式表示；(3)(3)用用决决策策变变量量的的线线性性函函数数表表示示目目标标，并确定是求极大（并确定是求极大（MaxMax）还是极小（）还是极小（MinMin）；）；(4)(4)根根据据决决策策变变量量的的物物理理性性质质研研究究变量是否有非负性。变量是否有非负性。4.4.线性规划应用线性规划应用第66页，共77页，

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

40、少件？少件？生产计划的问题第67页，共77页，编辑于2022年，星期一解：解：设设 x x1 1,x,x2 2,x,x3 3 分别为三道工序都由本公司加工分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，的甲、乙、丙三种产品的件数，x x4 4,x x5 5 分别为由外协分别为由外协铸造再由本公司机加工和装配的甲、乙两种产品的件数。铸造再由本公司机加工和装配的甲、乙两种产品的件数。生产计划的问题第68页，共77页，编辑于2022年，星期一 求求 x xi i 的利润的利润:利润利润=售价售价-各成本之和可得到各成本之和可得到 x xi i（i i=1,2,3,4,5=1,2,3,4,5）

41、的利润分别为）的利润分别为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.5 s.t.5x x1 1+10+10 x 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

42、+2+2x x5 5 10000 10000 x x1 1,x x2 2,x x3 3,x x4 4,x x5 5 0 0 生产计划的问题生产计划的问题第69页，共77页，编辑于2022年，星期一 例例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的任何规的任何规格的设备上加工；格的设备上加

43、工；可在任意规格的可在任意规格的A A设备上加工，设备上加工，但对但对B B工序工序,只能在只能在B B1 1设备上加工；设备上加工；只能在只能在A A2 2与与B B2 2设备上加工；数据如下表。问：为使该厂获得设备上加工；数据如下表。问：为使该厂获得最大利润，应如何制定产品加工方案？最大利润，应如何制定产品加工方案？生产计划的问题生产计划的问题第70页，共77页，编辑于2022年，星期一解：解：设设 x xijkijk 表示第表示第 i i 种产品，在第种产品，在第 j j 种工序种工序上的第上的第 k k 种设备上加工的数量种设备上加工的数量.利润利润=（销售单（销售单价价-原料单价）原

44、料单价）产品件数产品件数 之和之和-（每台时的设备费用（每台时的设备费用设备实际使用的总台时数）之和设备实际使用的总台时数）之和。生产计划的问题生产计划的问题第71页，共77页，编辑于2022年，星期一这样我们建立如下的数学模型这样我们建立如下的数学模型: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

45、-1.2304x322322-0.35x-0.35x123123 s.ts.t 5x 5x111111+10 x+10 x2112116000 6000 （设备设备 A A1 1 ）7x 7x112112+9x+9x212212+12x+12x3123121000010000（设备设备 A A2 2 ）6x 6x121121+8x+8x221221 4000 (4000 (设备设备 B B1 1 ）4x 4x122122+11x+11x3223227000 (7000 (设备设备 B B2 2 ）7x 7x123123 4000 4000 （设备设备 B B3 3 ）生产计划的问题生产计划的问

46、题第72页，共77页，编辑于2022年，星期一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、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 生

47、产计划的问题生产计划的问题第73页，共77页，编辑于2022年，星期一 例例2.2.：某昼夜服务的公交线路每天各时间段内所需司机和乘务人某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：员数如下：人力资源分配的问题设司机和乘务人员分别在各时间段一开始时设司机和乘务人员分别在各时间段一开始时上班，并连续工作上班，并连续工作8h8h，问该公交线路怎样安，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员配备最少司机和乘务人员?第74页，共77页，编辑于2022年，星期一 解：设解：设 x xi i 表示第表示第i i班次时

48、开始上班的司机和乘务人员数班次时开始上班的司机和乘务人员数,这样我们建立如下的数学模型这样我们建立如下的数学模型。目标函数目标函数：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+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 人力

49、资源分配的问题人力资源分配的问题第75页，共77页，编辑于2022年，星期一例例2 2:某工厂要做某工厂要做100100套钢架，每套用长为套钢架，每套用长为2.9 m,2.1m,1.5m2.9 m,2.1m,1.5m的圆钢各的圆钢各一根。已知原料每根长一根。已知原料每根长7.4 m7.4 m，问：应如何下料，可使所用原料最，问：应如何下料，可使所用原料最省？省？套裁下料问题套裁下料问题解解:考虑下列各种下料方案（按一种逻辑顺序给出）考虑下列各种下料方案（按一种逻辑顺序给出）把各种下料方案按剩余料头从小到大顺序列出把各种下料方案按剩余料头从小到大顺序列出第76页，共77页，编辑于2022年，星期

50、一假设假设 x x1 1,x x2 2,x x3 3,x x4 4,x x5 5 分别为上面前分别为上面前 5 5 种方案下料的原材料根数。我们建立如下的种方案下料的原材料根数。我们建立如下的数学模型。数学模型。目标函数：目标函数：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