运筹学OR1-Ch1-LP原理课件.ppt

1、第一章第一章 线性规划原理线性规划原理Chapter1 the Principle ofLiner Programming1-1 LP问题的提出问题的提出1-2 LP模型及其解的概念模型及其解的概念1-3 LP图解法图解法1-4 LP的求解原理的求解原理1-5 LP在工商管理中的应用在工商管理中的应用1-1 LP问题的提出问题的提出例1：某工厂在计划期内要安排生产甲、乙两种产品，这两种产品分别需要在A、B、C三种不同的设备上加工。按工艺规定，产品甲、乙在各设备上所需的加工台时如表1-1。已知各设备在计划期内有效台时分别是8、16和12，该工厂每生产一件产品甲、乙可分别获得利润2元、3元。问应如

2、何安排生产计划，才能得到利润最多？设备 产品 A B C 单件利润 甲 1 4 0 2 乙 2 0 4 3 有效台时 8 16 12 2022年7月28日7时46分Page 2 of 43 LP问题的提出问题的提出此问题用数学语言描述为：v假设x1,x2分别表示在计划期内产品甲、乙的产量，则该企业的目标为利润z最大：z=2x1+3x2 v这个方程是实际问题追求的目标，因此称之为问题的目标方程。在此方程中，利润Z是x1,x2的单增函数，x1,x2越大，利润Z就越大。但是，由于受到有限资源的限制（此题中为设备台时的限制），x1,x2不可能任意增大，它要受到资源量的制约。比如，对于设备A而言，其总有

3、效台时为8，生产产品甲乙所需要的A设备的总台时不能超过8，即：x1+2x28v同样地，对于设备资源B、C，我们可以得到不等式：4x1164x212 2022年7月28日7时46分Page 3 of 43 LP问题的提出问题的提出v除了这些设备有效台时的限制条件之外，还有一个隐含的限制条件，就是产量x1,x2都必须是大于等于零的。v综上所述，得到问题的数学模型如下：Max z=2x1+3x2 x1+2x28 4x1 16 4x212 x1,x20例2：靠近某河流有两个化工厂（如图1-1），流经第一化工厂的河流流量为每天500万m3，在两个工厂之间有一条流量为每天200万m3的支流，第一化工厂每天

4、排放含有某种有害物质的工业污水2万m3，第二化工厂每天排放这种污水1.4万m3。从第一化工厂排出的工业污水流到第二化工厂以前有20%可自然2022年7月28日7时46分Page 4 of 43 LP问题的提出问题的提出净化。根据环保要求，河流中工业污水的含量应不大于0.2%。为此这两个工厂都需各自处理一部分工业污水以满足环保要求。第一化工厂处理工业污水的成本是1000元/万m3，第二化工厂是800元/万m3。现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂总的处理工业污水的费用最少。500 万3m 200 万3m O 工厂 1 O 工厂 2 例 2 示意图 设第一和第二化

5、工厂每天处理工业污水量分别为x1、x2万，则问题追求的目标为：费用 Min w=1000 x1+800 x2 且要满足环保条件：污水含量0.2%。2022年7月28日7时46分Page 5 of 43 LP问题的提出问题的提出为此，将河流分成两段考虑，第一段：工厂1工厂2之间，只有工厂1的排放污水，应满足的约束条件：(2x1)/5002/1000第二段：工厂2之后的河段，除了有工厂2的排放污水外，还有工厂1的残留污水，同时，水流量也是两个河流的流量和，即：0.8(2x1)+(1.4x2)/7002/1000除此之外，还应满足处理量不超过最大污水量和非负条件。综合以上分析得问题的数学模型为：21

6、8001000minxxz10002500)2(1 x10002700)4.1()2(8.021xx21x4.12x0,21xx2022年7月28日7时46分Page 6 of 43 1-2 LP模型及其解的概念模型及其解的概念1.线性规划模型的三要素：1)定义决策变量集合：x1,x2,xn，这组决策变量的每一组可能的值就代表问题的一个具体解决方案；2)定义目标函数：用决策变量的线性函数形势写出所要追求的目标，称之为目标函数：z=f(x1,x2,xn)，根据问题的不同，要求目标函数实现最大化或最小化；3)定义约束条件集合：用一组决策变量的等式或不等式来表示在决策问题过程中所必须遵循的约束条件。

7、2.线性规划的一般模型 目标函数：约束条件：nnxcxcxcz2211max(min)11212111),(bxaxaxann22222121),(bxaxaxannmnmnmmbxaxaxa),(22110,21nxxx2022年7月28日7时46分Page 7 of 43 LP模型及其解的概念模型及其解的概念3.线性规划模型的矩阵描述形式0XbAXCXzmaxmn2m1mn22221n11211Tm21n21Tn21aaaaaaaaaAbbbbcccCxxxX约束系数矩阵资源列向量目标价值系数其中：决策变量集合),(),(),(n21j0 xm21ibxaxczjn1jijijn1jjj,

8、max还可以表示为：2022年7月28日7时46分Page 8 of 43 LP模型及其解的概念模型及其解的概念4.LP模型的标准型v概括线性规划在工农业生产方面的应用有两大类：第一类为在资源限制条件下使利益最大，第二类为在产出一定的前提下使费用最小。v从实际问题产生的线性规划模型，其目标函数可能要求最大或最小，约束条件可能是、或兼而有之，为探讨一种通用的解法，有必要将其标准化。vLP模型的标准型定义为：nnxcxcxcz2211max11212111bxaxaxann22222121bxaxaxannmnmnmmbxaxaxa22110,21nxxx2022年7月28日7时46分Page 9

9、 of 43 LP模型及其解的概念模型及其解的概念5。化一般LP模型为标准型v若问题的目标函数为最小化 ，则令 ,问题变成 ，得到最终结果 后反求 。v若约束条件为不等式，分两种情况，一种是约束，则将该不等式的左端加上一个非负的变量，使其变为等式，该变量称为松弛变量；另一种是约束，则将该不等式的左端减去一个非负的变量，使其变为等式，该变量称为剩余变量（也可统称为松弛变量）。v若某一决策变量 无非负约束，则用 代替，其中 。CXZ minCXZZCXZmaxZZZkxkkxx0,kkxx2022年7月28日7时46分Page 10 of 43 LP模型及其解的概念模型及其解的概念v例3：试将下面

10、线性规划问题化成标准型。32132minxxxz7321xxx2321xxx523321xxx321,0,xxx无符号要求 解：通过以下步骤：1.用 替代 ，其中 ；2.在第一个约束条件的号左端加入松弛变量 ；3.在第二个约束条件的号左端减去剩余变量 ；4.令 ，变求 为求 。)(33xx 3x0,33xx4x5xZZZminZmax54 332100)(32maxxxxxxxZ7)(4 3321xxxxx2)(5 3321xxxxx5)(23 3321xxxx71,0jxj2022年7月28日7时46分Page 11 of 43 LP模型及其解的概念模型及其解的概念6 LP解的概念v针对LP

11、的标准型.bAX .0X 可行解：满足所有约束条件包括非负条件的解 X=(x1,x2,xn)T 称为该问题的可行解。所有可行解的集合构成可行域。最优解：使目标函数达到最大值的可行解称为最优解。基：A是约束方程组的 mn 阶系数矩阵，设其秩为m，B矩阵是矩阵A中mm阶非奇异子矩阵（|B|0），则称B是线性规划问题的一个基。就是说，B是由m个线性独立的列向量组成。不失一般性，可以设：),(21212222111211mmmmmmmpppaaaaaaaaaBCXz max2022年7月28日7时46分Page 12 of 43 LP模型及其解的概念模型及其解的概念v称pj(j=1,2,m)为基向量，

12、与基向量pj对应的变量xj(j=1,2,m)为基变量，否则为非基变量。基本解：对于上述基B，其秩为m，一般mn有无数多个解，则上述式可变为：设XB 是对应于这个基B的基变量向量：若令 ，则可用高斯消元法，求出上式的一个解：，这个解非零分量的数目不大于方程数m，则称X为基本解。nnmmmmxpxpbxpxpxp112211TmBxxxX),(21021nmmxxxTmxxxX)0,0,(21基本可行解：满足非负条件的基本解称之为基本可行解。可行基：对应于基本可行解的基称为可行基。2022年7月28日7时46分Page 13 of 43 LP模型及其解的概念模型及其解的概念由上面分析可知，约束方程

13、组基本解的数目是有限的，最多为 个，一般情况下基本可行解的数目要小于基本解的数目，最多相等。另外，在基本解中，若非零分量的数目小于m，则称之为退化解。我们暂不讨论这种情况。非可行解 基本解 可行解 基本可行解 图 1-3：解的关系示意图 mnC2022年7月28日7时46分Page 14 of 43 1-3 LP的图解法现对上述例1进行图解，在以x1 x2 为坐标轴的直角坐标系中，原题中的每一个约束条件为一条直线（如图所示）。再来分析目标函数，把它反映在直角坐标系下，可以表示为以Z为参数的一族平行线：33212zxxx1x2152431234R*),(24Q16x41 12x42 8x2x21

14、 3zx32x12 图中粗线所围区域部分中（含边界）中每一点都满足约束条件，都是该问题的解，这个区域就是该问题的解集合，又称之为可行域。2022年7月28日7时46分Page 15 of 43 线性规划的图解法v注意：几种特殊情况：1.当目标方程直线与某一约束直线平行时，最优值不唯一。如，本例中若将目标函数改为max z=2x1+4x2。则其直线与约束x1+2x28的直线平行，则直线x1+2x28在可行域中的部分，其每一点都是问题的最优解。21maxxxz0 xx2xx4xx2212121 ,x1x2152431234R16x41 12x42 8x2x21 21x4x2z 2xx21 4xx2

15、21 2.有可行域，但无最优解。即目标函数的值z+如：2022年7月28日7时46分Page 16 of 43 线性规划的图解法3.无可行解。当约束条件出现相互矛盾时，则没有可行域。在实际问题中，当数学模型有错误时，才可能发生2、3种情况 通过以上图解，较直观地看到了线性规划模型的求解过程。对于复杂的问题是不可能用图解法求解的，它只能求解两个决策变量的情况。因此，还需要找到一种线性规划问题的一般的、通用的求解方法。线性规划的实用解法有：单纯形法；计算机软件求解。2022年7月28日7时46分Page 17 of 43 线性规划的图解法vLP图解法得到的启示1.若LP问题有最优解，则该解一定在可

16、行域的边界上（由目标求max或min)；2.若LP问题有最优解，则一定在其可行域的某个顶点上达到最优；3.最优解一定存在于基本可行解中(理论定理证明P.1619)1)凸集定义:n维空间一个点集中的任意两点连线上的点都属于这个点集。2)顶点定义：凸集中不能用不同两点线性表示的点称为。3)定理1：LP问题的可行域是凸集。4)定理2：LP问题的基本可行解对应于其可行域的顶点。5)定理3：可行域有界的LP问题，其目标函数一定可以在其可行域的顶点上达到最优。2022年7月28日7时46分Page 18 of 43 1-4 LP的求解原理的求解原理1.解法思想：采用迭代的办法。首先找一个初始基本可行解，然

17、后判断是否是最优解，若是，则停止迭代；若不是，则以此解为基础，找比它更好的基本可行解。如此循环，直至找到最优解。其框图描述如图1-4。确定初始基本可行解 是最优解？寻找更好的基本可行解 停 是 否 图 1-4：LP 解法思想示意图 2022年7月28日7时46分Page 19 of 43 LP的求解原理的求解原理2.初始基本可行解的确定 1)若线性规划问题的约束方程均为“=”约束，即且从其系数列向量 中能观察到存在m个线性独立的单位向量，则由这些列向量构成初始基：，其对应的决策变量为初始基变量，其余变量为非基变量，且令非基变量等于零，则构成初始基本可行解。mibxpijnjj1,1)(n1jp

18、j100010001),(210mpppB2022年7月28日7时46分Page 20 of 43 LP的求解原理的求解原理2.初始基本可行解的确定 2)若原问题的约束条件均为“”约束，则给每一个约束条件的左端分别加上一个非负的松弛变量变成为等式约束。这m个松弛变量所对应的系数列向量必构成单位阵I，以此作为初始基：即以m个松弛变量为初始基变量，其余变量为非基变量并令其等于零，则得原问题的初始基本可行解。100010001),(210mnnnpppB2022年7月28日7时46分Page 21 of 43 LP的求解原理的求解原理2.初始基本可行解的确定 3)若原问题均为“=”约束，且观察不到存

19、在相互独立的m个单位列向量，则给每个约束左端加上一个非负的人工变量构成初始基，以此确定初始基本可行解。4)若原问题的约束条件均为“”约束，则按标准化的步骤给每个约束减去一个非负剩余变量，使其变为“=”；然后，再给每个约束的左端加上一个非负的人工变量，这m个人工变量所对应的系数列向量必构成单位阵，以此单位阵为初始基所形成的解为初始基本可行解。5)若约束条件中混合出现“”、“”、“=”，则综合运用上述原则，总可以得到m个相互独立的单位列向量构成为m阶单位阵，以此为初始基，求得初始基本可行解。注意：人工变量是为解决问题人为硬加入的不存在的量。因此，最终的解中这些人工变量必须成为非基变量，否则问题无解

20、。2022年7月28日7时46分Page 22 of 43 LP的求解原理的求解原理2.初始基本可行解的确定 例1初始解的确定51j0 x12xx416xx48xx2xx0 x0 x0 x3x2zj524132154321,max0 xx12x416x48x2xx3x2z21212121,max标准化100400100400121pppA521),(系数矩阵为：),(5430pppB基矩阵：）基向量：（543xxx,2514213x412xx416xx2x8x则有：0 x3x20Z0 xx2121得：令T01216800X),()(得到初始解：2022年7月28日7时46分Page 23 of

21、 43 LP的求解原理的求解原理3.最优性检验 按照线性规划的求解思路，在得到其初始可行解之后，就要检查一下，它是否是最优解，若是，则算法停止；若不是，继续迭代求解下一个基本可行解，并且每求得一个基本可行解都要检验它是否是最优解。那么，如何来检验呢？一般而言，经过迭代可得原问题的一个基，对于所有的约束，基变量留在等式的左端，所有非基变量移到右端，得到：m21ixabxjn1mjijii,jijm1iin1mjjim1iixaccbcz)(带入目标方程得：im1ii0bcz令：ijm1iijacz令：jjn1mjj0 xzczz)(得到：2022年7月28日7时46分Page 24 of 43

22、LP的求解原理的求解原理3.最优性检验 n1mjzcjjj,再令：jn1mjj0 xzz则得：从此式可以作出判断：若当前基所形成的j，对于所有的 j()都有j0，根据变量的非负性 （），有jxj0，所以只有当 所有 时，目标函数才能取得最大值。因此，称 为检验数。nmj1njxj1,0)(n1mj0 xjj2022年7月28日7时46分Page 25 of 43 LP的求解原理的求解原理3.最优性检验 1)最优性判定：若对应于基B的基本可行解为：且对于一切非基变量 ，有j0，则 为最优解。TmlbbbX)0,0,(21)(jxnmj1)(lX2)无穷多最优解判定：若对应于基B的基本可行解 ，均

23、有j0，（），且至少存在一个非基变量的检验数m+k=0，则判定线性规划问题有无穷多最优解。nmj1)(lX3)无最优解判定：若对应于基B的基本可行解中，某一非基变量的检验数m+k0，而该非基变量所对应的变化后的系数列向量 中的每个分量 ，则该问题无最优解。TkmmkmkmkmaaaP),(,2,10,kmia2022年7月28日7时46分Page 26 of 43 LP的求解原理的求解原理4.基变换 当判定某一个基所对应的基本可行解不是最优解，而且存在最优解时，就需要进行基变换。即在非基变量中选择一个入基，在基变量中选择一个出基，从而构成新的基，相应地得到新的基本可行解。1)换入变量的确定：若

24、当前基对应的基本可行解为非最优解，则必然有某一个或几个非基变量的检验数大于零，它们中的任何一个变成为基变量，都可以使目标函数值增大。I.若只有一个非基变量的检验数大于零，则别无选择，它所对应的非基变量就是进基变量；II.若有两个或两个以上的非基变量的检验数大于零，一般选择其中最大的所对应的变量为进基变量。这样可以使目标函数值增长较快。2022年7月28日7时46分Page 27 of 43 LP的求解原理的求解原理4.基变换2)换出变量的确定 若对应于现行基的基变量为 ，基向量 ，其约束方程可表示为：),(21mBxxxX),(21mpppnn1tm11m1m111xaaxabx,nn2tm2

25、1m1m222xaaxabx,nnltml1m1mlllxaaxabx,nnmtmm1m1mmmmxaaxabx,2022年7月28日7时46分Page 28 of 43 LP的求解原理的求解原理4.基变换2)换出变量的确定v假定确定的进基变量为 ，将该列移到等号左端：nn11m1m11tm1xaxabxx,tm1,a tmxnn21m1m22tmtm22xaxabxax,nnl1m1mlltmtmllxaxabxax,nnm1m1mmmtmtmmmxaxabxax,2022年7月28日7时46分Page 29 of 43 LP的求解原理的求解原理4.基变换v换出变量的确定 在 进基之后，必须

26、在原来的m个基变量中选择一个出基，变成为非基变量。为了使变化后的基所对应的基本解仍为可行解，必须保证当等号左端变成为新基的m阶单位阵后，右端的常数项大于等于零。假定 出基，对上式进行加减消元，以恢复基矩阵的单位阵特征，并令所有非基变量等于零，得到各基变量的值为：tmxlx,tmltm1l11aabbx,tmltm2l22aabbx,/tmlltmabx,tmltmmlmmaabbx2022年7月28日7时46分Page 30 of 43 LP的求解原理的求解原理4.基变换v换出变量的确定根据变量的非负要求，上式右端项均应0，其中第k行应为 :0/,tmltmklkaabb0ababtmlltm

27、kk,即：),oa0bbxtmklktm限制，（由k的任意性可知，应是所有约束行中最小的正数。,tmllab规则称为令：),(,m21labtmlll由规则知道，xl为出基变量，有了进出基变量，则基的变换得以实现，从而求得新的基本可行解。2022年7月28日7时46分Page 31 of 43 1-5 LP在工商管理中的应用在工商管理中的应用一、人力资源分配的问题 例1某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?班 次时 间所 需 人 数

28、16：00 10：0060210：00 14：0070314：00 18：0060418：00 22：0050522：2：002062：00 6：0030 解：设 xi 表示第i班次时开始上班的司机和乘务人员数,这样我们建立如下的数学模型。目标函数：Min x1+x2+x3+x4+x5+x6 约束条件：s.t.x1+x6 60 x1+x2 70 x2+x3 60 x3+x4 50 x4+x5 20 x5+x6 30 x1,x2,x3,x4,x5,x6 02022年7月28日7时46分Page 32 of 43 线性规划在工商管理中的应用线性规划在工商管理中的应用一、人力资源分配的问题 例2福安

29、商场是个中型的百货商场，它对售货员的需求经过统计分析如右表：为了保证售货人员充分休息，售货人员每周工作 5天，休息两天，并要求休息的两天是连续的。问应该如何安排售货人员的作息，既满足工作需要，又使配备的售货人员的人数最少？时间所需售货员人数星期日28星期一15星期二24星期三25星期四19星期五31星期六28 解：设 xi(i=1-7)表示星期一至日开始休息的人数,这样我们建立如下的数学模型。目标函数：Min x1+x2+x3+x4+x5+x6+x7 约束条件：s.t.x1+x2+x3+x4+x5 28 x2+x3+x4+x5+x6 15 x3+x4+x5+x6+x7 24 x4+x5+x6+

30、x7+x1 25 x5+x6+x7+x1+x2 19 x6+x7+x1+x2+x3 31 x7+x1+x2+x3+x4 28 x1,x2,x3,x4,x5,x6,x7 02022年7月28日7时46分Page 33 of 43 线性规划在工商管理中的应用线性规划在工商管理中的应用二、生产计划的问题 例3明兴公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如右表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？甲乙丙资源限

31、制铸造工时(小时/件)51078000机加工工时(小时/件)64812000装配工时(小时/件)32210000自产铸件成本(元/件)354外协铸件成本(元/件)56-机加工成本(元/件)213装配成本(元/件)322产品售价(元/件)231816 解：设 x1,x2,x3 分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，x4,x5 分别为由外协铸造再由本公司机加工和装配的甲、乙两种产品的件数。求 xi 的利润：利润=售价-各成本之和 可得到 xi（i=1,2,3,4,5）的利润分别为 15、10、7、13、9 元。这样我们建立如下的数学模型。目标函数：Max 15x1+10 x2+7

32、x3+13x4+9x5 约束条件：s.t.5x1+10 x2+7x3 8000 6x1+4x2+8x3+6x4+4x5 12000 3x1+2x2+2x3+3x4+2x5 10000 x1,x2,x3,x4,x5 02022年7月28日7时46分Page 34 of 43 线性规划在工商管理中的应用线性规划在工商管理中的应用二、生产计划的问题 例4永久机械厂生产、三种产品，均要经过A、B两道工序加工。设有两种规格的设备A1、A2能完成 A 工序；有三种规格的设备B1、B2、B3能完成 B 工序。可在A、B的任何规格的设备上加工；可在任意规格的A设备上加工，但对B工序，只能在B1设备上加工；只能

33、在A2与B2设备上加工；数据如右上表。问：为使该厂获得最大利润，应如何制定产品加工方案？产品单件工时 设备设备的有效台时满负荷时的设备费用A15106000300A2791210000321B168400050B24117000783B374000200原料（元/件）0.250.350.50售价（元/件）1.252.002.802022年7月28日7时46分Page 35 of 43 线性规划在工商管理中的应用线性规划在工商管理中的应用解：设 xijk 表示第 i 种产品，在第 j 种工序上的第 k 种设备上加工的数量。利润=（销售单价-原料单价）*产品件数之和-（每台时的设备费用*设备实际使

34、用的总台时数）之和。这样我们建立如下的数学模型:Max 0.75x111+0.7753x112+1.15x211+1.3611x212+1.9148x312-0.375x121-0.5x221-0.4475x122-1.2304x322-0.35x123 s.t.5x111+10 x211 6000 （设备 A1）7x112+9x212+12x312 10000 （设备 A2）6x121+8x221 4000 （设备 B1）4x122 +11x322 7000 （设备 B2）7x123 4000 （设备 B3）x111+x112-x121-x122-x123=0（产品在A、B工序加工的数量相等

35、）x211+x212-x221 =0（产品在A、B工序加工的数量相等）x312 -x322 =0（产品在A、B工序加工的数量相等）xijk 0 ,i=1,2,3;j=1,2;k=1,2,32022年7月28日7时46分Page 36 of 43 线性规划在工商管理中的应用线性规划在工商管理中的应用三、套裁下料问题 例5某工厂要做100套钢架，每套用长为2.9 m,2.1 m,1.5 m的圆钢各一根。已知原料每根长7.4 m，问：应如何下料，可使所用原料最省？解：写出所有可能的下料方案（从剪裁的一种思路考虑）整理为剩余料头从小到大的方案顺序方案 1方案 2方案 3方案 4方案 5方案 6方案 7

36、方案 82.9 m211100002.1 m021032101.5 m10130234合计7.37.16.57.46.37.26.66.0剩余料头0.10.30.901.10.20.81.4方案 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.42022年7月28日7时46分Page 37 of 43 线性规划在工商管理中的应用线性规划在工商管理中的应用考虑下列 5 种下料方案方案 1方案 2方案 3方案

37、4方案 52.9 m120102.1 m002211.5 m31203合计7.47.37.27.16.6剩余料头00.10.20.30.8 设x1,x2,x3,x4,x5分别为上面前 5 种方案下料的原材料根数。这样我们建立如下的数学模型。目标函数：Min x1+x2+x3+x4+x5 约束条件：s.t.x1+2x2 +x4 100 2x3 +2x4+x5 100 3x1+x2+2x3 +3x5 100 x1,x2,x3,x4,x5 02022年7月28日7时46分Page 38 of 43 线性规划在工商管理中的应用线性规划在工商管理中的应用产品名称规格要求单价（元/kg）甲原材料1不少于5

38、0%，原材料2不超过25%50乙原材料1不少于25%，原材料2不超过50%35丙不限25原材料名称每天最多供应量单价（元/kg）11006521002536035 解：设 xij 表示第 i 种（甲、乙、丙）产品中原料 j 的含量。这样我们建立数学模型时，要考虑：对于甲：x11，x12，x13；对于乙：x21，x22，x23；对于丙：x31，x32，x33；对于原料1：x11，x21，x31；对于原料2：x12，x22，x32；对于原料3：x13，x23，x33；目标函数：利润最大，利润=收入-原料支出 约束条件：规格要求 4 个；供应量限制 3 个。四、配料问题 例6某工厂要用三种原料1、2

39、、3混合调配出三种不同规格的产品甲、乙、丙，数据如右表。问：该厂应如何安排生产，使利润收入为最大？2022年7月28日7时46分Page 39 of 43 线性规划在工商管理中的应用线性规划在工商管理中的应用例6（续）目标函数：Max z=-15x11+25x12+15x13-30 x21+10 x22-40 x31-10 x33 约束条件：s.t.0.5 x11-0.5 x12-0.5 x13 0（原材料1不少于50%）-0.25x11+0.75x12-0.25x13 0（原材料2不超过25%）0.75x21-0.25x22-0.25x23 0（原材料1不少于25%）-0.5 x21+0.5

40、 x22-0.5 x23 0（原材料2不超过50%）x11+x21+x31 100 (供应量限制）x12+x22+x32 100 (供应量限制）x13+x23+x33 60 (供应量限制）xij 0 ,i=1,2,3;j=1,2,32022年7月28日7时46分Page 40 of 43 线性规划在工商管理中的应用线性规划在工商管理中的应用五、投资问题 例8某部门现有资金200万元，今后五年内考虑给以下的项目投资。已知：项目A：从第一年到第五年每年年初都可投资，当年末能收回本利110%；项目B：从第一年到第四年每年年初都可投资，次年末能收回本利125%，但规定每年最大投资额不能超过30万元；项

41、目C：需在第三年年初投资，第五年末能收回本利140%，但规定最大投资额不能超过80万元；项目D：需在第二年年初投资，第五年末能收回本利155%，但规定最大投资额不能超过100万元；据测定每万元每次投资的风险指数如右表：问：问：a）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？b）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小？项 目风 险 指 数（次/万 元）A1B3C4D5.5 解：解：1 1）确定决策变量：连续投资问题 设 xij(i=1-5，j=1、2、3、4)表示第 i 年初投资于A(j=1)、B(

42、j=2)、C(j=3)、D(j=4)项目的金额。这样我们建立如下的决策变量：A x11 x21 x31 x41 x51 B x12 x22 x32 x42 C x33 D x242022年7月28日7时46分Page 41 of 43 线性规划在工商管理中的应用线性规划在工商管理中的应用2 2）约束条件：）约束条件：第一年：A当年末可收回投资，故第一年年初应把全部资金投出去，于是 x11+x12=200；第二年：B次年末才可收回投资故第二年年初的资金为1.1x11，于是 x21+x22+x24=1.1x11；第三年：年初的资金为1.1x21+1.25x12，于是 x31+x32+x33=1.1

43、x21+1.25x12；第四年：年初的资金为1.1x31+1.25x22，于是 x41+x42=1.1x31+1.25x22；第五年：年初的资金为1.1x41+1.25x32，于是 x51=1.1x41+1.25x32；B、C、D的投资限制：xi2 30(I=1、2、3、4)，x33 80，x24 100 3 3）目标函数及模型：）目标函数及模型：a)a)Max z=1.1x51+1.25x42+1.4x33+1.55x24 s.t.x11+x12=200 x21+x22+x24=1.1x11；x31+x32+x33=1.1x21+1.25x12；x41+x42=1.1x31+1.25x22；

44、x51=1.1x41+1.25x32；xi2 30(I=1、2、3、4)，x33 80，x24 100 xij 0 (i=1、2、3、4、5；j=1、2、3、4）b)b)Min f=(x11+x21+x31+x41+x51)+3(x12+x22+x32+x42)+4x33+5.5x24 s.t.x11+x12 200 x21+x22+x24 1.1x11；x31+x32+x33 1.1x21+1.25x12；x41+x42 1.1x31+1.25x22；x51 1.1x41+1.25x32；xi2 30(I=1、2、3、4)，x33 80，x24 100 1.1x51+1.25x42+1.4x33+1.55x24 330 xij 0 (i=1、2、3、4、5；j=1、2、3、4）2022年7月28日7时46分Page 42 of 43 本章结束本章结束谢谢谢谢