运筹学第一章ppt线性规划.ppt

《运筹学第一章ppt线性规划.ppt》由会员分享，可在线阅读，更多相关《运筹学第一章ppt线性规划.ppt（87页珍藏版）》请在三一办公上搜索。

1、1,运筹学,管理科学与工程系 关叶青,2,授课教材：党耀国等,运筹学,科学出版社绪论第一章 线性规划的数学模型与单纯形法第二章 线性规划的对偶理论与灵敏度分析第三章 运输问题第四章 整数规划第五章 动态规划第六章 图论与网络计划第七章 存储论第八章 决策分析,3,绪 论,运筹学释义与发展简史 operational research,operations research,简写O.R.运筹学研究的基本特征 系统的整体性，多学科的综合性，模型方法的应用性运筹学在工商管理中的应用运筹学的主要分支 目录,4,O.R.在工商管理中的应用,生产计划：生产作业的计划、日程表的编排、合理下料、配料问题、物料

2、管理等。库存管理：多种物资库存量的管理，库存方式、库存量等。运输问题：确定最小成本的运输线路、物资的调拨、运输工具的调度以及建厂地址的选择等。,5,人事管理：对人员的需求和使用的预测，确定人员编制、人员合理分配，建立人才评价体系等。市场营销：广告预算、媒介选择、定价、产品开发与销售计划制定等。,O.R.在工商管理中的应用,6,财务和会计：包括预测、贷款、成本分析、定价、证券管理、现金管理等。其他：设备维修、更新，项目选择、评价，工程优化设计与管理等。,O.R.在工商管理中的应用,7,一、线性规划问题的数学模型主要解决以下两类问题：1、任务确定后，如何统筹安排，做到应用尽量少的人力和物力资源来完

3、成任务；2、在一定量的人力、物力资源的条件下，如何安排、使用他们，使完成的任务最多。,第1章 线性规划的数学模型与单纯形法 1.1 线性规划问题及其数学模型,8,解:设 计划期内生产产品I、II的数量x1、x2 则该问题的数学模型为：,max S=2x1+3x2,例1.1：（计划安排问题）,9,例1.2(成本问题),某炼油厂根据每季度需供应给合同单位汽油15万吨、煤油12万吨、重油12万吨。该厂计划从A，B两处运回原油提炼，已知两处的原油成分含量见表12；又已知从A处采购的原油价格为每吨（包括运费）200元，B处采购的原油价格为每吨（包括运费）290元,问：该炼油厂该如何从A，B两处采购原油，

4、在满足供应合同的条件下，使购买成本最小。,10,线性规划模型特点:,决策变量：向量(x1 xn)T,xi非负约束条件：线性等式或不等式目标函数：Z=(x1 xn)线性式，求Z极大或极小,满足以上三个条件的数学模型称为-线性规划数学模型,11,（资源利用问题）,某食品厂主要生产I型饼干和I I型饼干。根据销售部门提供的信息可知，目前这两种饼干在市场上都很畅销，该厂能生产多少，市场就能卖出多少。但从生产部门得知，有三种关键设备即搅拌机、成型机、烘箱的生产能力限制了该厂的饼干生产。因为两种饼干的生产都要共用这三种设备，所以每种饼干究竟应该生产多少才能充分利用现有设备资源，这是一个值得认真研究的重要问

5、题。,12,（货物调度问题）,某企业是一家新鲜柑橘产品的种植商和经营商，有I、II、II块大的柑橘林及甲乙丙三个柑橘加工厂（柑橘林到加工厂的距离公里信息如红色字体数据）。现该企业与一家地方货车运输公司联系，从柑橘林向加工厂运输柑橘。运输公司按照每蒲式耳柑橘运输每公里（记为蒲式耳-公里）的统一价格收费，该企业希望确定从各个柑橘林到各个加工厂运输多少蒲式耳，以使所运输的柑橘蒲式耳-公里的总数最小。,13,max(min)Z=c1x1+c2x2+cnxn,C=(C1 C2 Cn),一般形式：,14,二、线性规划问题的标准型,目标函数 max 变量 非负 约束条件 等式 约束常数 非负,15,解：引进

6、3个新非负变量x3，x4，x5使不等式变为等式，标准型为：max Z=2x1+3x2+0 x3+0 x4+0 x5 3x2+x3=15 4x1+x4=12 2x1+2x2+x5=14 x1，x2，x3，x4，x50,例1.3将例1.1的数学模型化为标准型。,max Z=2x1+3x2 3x2 15 4x1 12 2x1+2x2 14 x1，x20,16,解：令x3=x4-x5,添加松弛变量x6,添加剩余变量x7,令S=-S,maxS=x1 2x2+3x4 3x5,例1.4,17,将 min S=x1+2x2+3x3,化为标准型。,练习：,18,max S=40 x1+50 x2,一、线性规划问

7、题的图解法,解：(1)确定可行域 x1 0 x1=0(横轴)x2 0 x2=0(纵轴),x1+2x2 30 x1+2x2=30 l1(0,15)(30,0),3x1+2x2=60 l2(0,30)(20,0),2x2=24,1.2 线性规划问题的图解法及几何意义,19,(2)求最优解“等值线法”,解：X*=(15 7.5)Smax=975,S=40 x1+50 x2=x2=0.8x10.02 S,20,max Z=2x1+3x2,例1.5,解得：最优解B点（2，5）。最优值 Z=22+35=19,唯一最优解,21,用图解法求解线性规划问题 maxZ=40 x1+80 x2 s.t.x1+2x2

8、 30 3x1+2x2 60 2x2 24 x1,x2 0,例1.6,解：最优解：BC线段B点 X(1)=(6,12)；C点 X(2)=(15,7.5)X=X(1)+(1-)X(2)(0 1)maxZ=1200 整理得：x1=15-9 x2=7.5+4.5(0 1),无穷多解,22,maxZ=2x1+4x2 s.t.2x1+x2 8-2 x1+x2 2 x1，x2 0,例1.7,若目标函数由 min Z=2 x1+4 x2,最优解 x1=4，x2=0，即(4,0)点,解：由于可行域无界 无有限最优解-无界解,23,无可行解,总结,例,24,通过以上各题图解法所得结论可以看出：（1）线性规划的所

9、有可行解构成的可行域一般是凸多边形，有些可行域可能是无界的；（2）若存在最优解，则一定在可行域的某顶点得到；（3）若在两个顶点上同时得到最优解，则在这两点的连线上的任一点都是最优解。（4）若可行域无界，则可能发生最优解无界的情况；（5）若可行域是空集，此时无最优解。上述理论具有普遍意义，对于两个以上变量的线性规划问题都是成立。,25,二、线性规划问题的解的概念,1.2 线性规划问题的图解法及几何意义,26,(m n)r(A)=m,至少有一个m 阶子式不为0不失一般性,不妨假设P1 Pm线性无关,基阵A中一个子矩阵B是可逆矩 阵，则方阵B称为LP问题的一个基阵。,Pm+1 Pn,A=B N,27

10、,定义：基向量 非基向量,=(XB XN)T,有：AX=P1 x1+P2 x2+Pn xn=b,定义：基变量 非基变量,BXB+NXN=bBXB=b-NXN,XB=B-1 b-B-1N XN,AX=b 求解过程：,A=(B N)X=(XB XN)T,目标函数：S=CX=CB B-1 b+(CN-CB B-1 N)XN,28,1.可行解:满足约束条件的解 X=(x1,x2,xn)称为线性规划问题的可行解；所有可行解的集合称为可行解集或可行域。2.最优解:满足约束条件及目标函数的可行解称为线性规划问题的最优解。最优值 3.基阵:假设 A 是约束方程组的系数矩阵，其秩数为 m，B是矩阵 A 中由 m

11、 列构成的非奇异子矩阵(B的行列式的值不为0)，则称 B 是线性规划问题的一个基。这就是说，矩阵 B 是由 m 个线性无关的列向量组成，不失一般性，可假设:称 Pj(j=1,2,m)为基向量，与基向量 Pj 相对应的变量xj(j=1,2,m)称为基变量，否则称为非基变量。,T,若令非基变量 xm+1=xn=0,用高斯消元法可求出LP标准型的一个解 X=(x1 x2 xm 0 0)T 称 X 为基本解.,29,为了进一步讨论线性规划问题的解，下面研究约束方程组(1.7)的求解问题。假设该方程组系数矩阵 A 的秩为 m，因 m n，所以它有无穷多个解。假设前 m 个变量的系数列向量是线性无关的，这

12、时(1.7)式可改写为：方程组(1.9)的一个基是B=(P1,P2,Pm),Pj=(a1j,amj),(j=1,2,m)，设 XB 是对应于这个基的基变量，即：XB=(x1,x2,xm)现若令(1.9)式中的非基变量xm+1=xn=0，并用高斯消去法求出一个解X=(x1,x2,xm,0,0)，这个解的非0分量的数目不大于方程的个数m，这时称X为基本解。,T,T,T,30,4.基本可行解:满足非负条件(1.8)的基本解称为基本可行解。由此可见，基本可行解的非0分量的数目不大于m，并且都是非负的。5.可行基阵:对应于基本可行解的基称为可行基。由此可见，满足约束方程组(1.7)的基本解的数目至多是

13、Cnm 个。一般地讲，基本可行解的数目要小于基本解的数目，至多相等。以上提到的几种解的概念，可用图14来表示：,31,1.凸集：假设K是n维欧氏空间的一个点集，若对于K中的任意两点X1、X2，其连线上的所有点X1+(1-)X2，(0 1)都在集合K中，即：X1+(1-)X2 K(0 1)则称K为凸集。从直观上讲，凸集无凹入部分，其内部没有洞。如实心圆、实心球、实心立方体等都是凸集。两个凸集的交集仍是凸集。2.凸组合：设X1，X2，Xk是n维欧氏空间En中的k个点，若存在1，2，k，且0 i 1，i=1,2,k，i=1，使X=1X1+2X2+kXk，则称X为由X1，X2，Xk所构成的凸组合。按照

14、定义，凡是由x，y的凸组合表示的点都在x，y的连线上，而且反之亦然。3.顶点：假设K是凸集，X K；X若不能用不同的两个点X1、X2 K的线性组合表示为：X=X1+(1-)X2，(0 1)则称X为凸集K的一个顶点（或称为极点）。顶点不位于凸集K中的任意不同两点的连线内。,三、基本定理,32,定理1.1 若线性规划问题存在可行域，则其可行域：D=X|AX=b,X 0，是凸集。引理1.1 线性规划问题的可行解X为基本可行解的充要条件是X的正分量所对应的系数列向量是线性无关的。定理1.2 线性规划问题的基本可行解对应于可行域的顶点。定理1.3 若可行域有界，则线性规划问题的目标函数一定可以在其可行域

15、的顶点上达到最优解。定理1.4 若线性规划问题在k个顶点上达到最优解（k2），则在这些顶点的凸组合上也达到最优解。,33,根据图解法得到如下的结论：（1）线性规划问题的所有可行解的集合一般是凸集，它可以是有界的，也可以是无界的区域；仅有有限个顶点。1(2)线性规划问题的每一个基本可行解对应于可行域的一个顶点。若线性规划问题有最优解，必定可在某顶点处取到。(3)如果一个线性规划问题存在多个最优解，那么至少有两个相邻的顶点处是线性规划的最优解。虽然可行域的顶点个数是有限的(它们不超过 Cnm 个)，采用“枚举法”可以找出所有基本可行解，然后一一比较它们的目标函数值的大小，最终可以找到最优解。但当m

16、、n的数目相当大时，这种办法实际上是行不通的。因此，我们还要继续讨论一种方法，通过逐步迭代保证能逐步改进并最终求出最优解。,34,基向量|非基向量,=(XB XN)T,约束方程组：AX=P1 x1+P2 x2+Pn xn=b,BXB+N XN=b BXB=b-NXN,XB=B-1 b-B-1N XN,约束方程：AX=b,A=(B N)X=(XB XN)T,目标函数方程：S=CX=CB B-1 b+(CN-CB B-1 N)XN,基变量 非变向量,35,单纯形算法的基本思路是：根据问题的标准型，从可行域中某个基本可行解(顶点)开始，转换到另一个基本可行解(顶点)，并使得每次的转换，目标函数值均有

17、所改善，最终达到最大值时就得到最优解。现在需要解决的问题是：(1)为了使目标函数逐步变优，应如何从可行域的一个顶点转移到可行域的另一个顶点？（2）目标函数何时达到最优值？判断标准是什么？,1.3 单纯形算法,36,1确定初始基本可行解对于标准型的线性规划问题(简写为 LP)：或（1.9）这里 A=(aij)mn，Rank(A)=m。,37,从中一般可以直接观察到存在一个初始可行基B=(P1,P2,Pm)=（1.10）当线性规划的约束条件均为“=”形式的不等式或等式时，若不存在单位矩阵，就采用构造人造基的办法，即对不等式约束减去一个非负的剩余变量后，再加上一个非负的人工变量；对于等式约束，加上一

18、个非负的人工变量。这样总可以找到一个单位矩阵，关于这个方法将在本章第四节讨论。,38,（1.10）式中的P1,P2,Pm称为基向量，其对应的变量称为基变量，模型中其它变量称为非基变量。在约束条件中把非基变量项移到等式的右边得：,（1.11）,令所有非基变量，得 X=(b1,b2,bm,0,0)又由于，故X满足约束条件，所以它是一个基可行解。式(1.11)就是基变量用非基变量表示的形式。,T,39,表13 初始单纯形表,40,利用单纯形算法求解例11的线性规划问题。Max Z=2x1+3x2+0 x3+0 x4+0 x5 3x2+x3=15 s.t.4x1+x4=12 2x1+2x2x5=14

19、x1，x2，x3，x4，x50,例18,解：（1）由标准型得到初始单纯形表：,41,假定已求得(LP)的一个基本可行解 X(0)，为叙述方便,不失一般性，假设：令所有非基变量，得 把式(1.12)代入目标函数得：式（1.14）就是目标函数用非基变量表示的形式。,(1.12),（1.13）,（1.14）,2最优性检验,42,令，于是 再令，则得：（1.15）在式（1.15）中，非基变量的系数，称为各非基变量（）的检验数。,43,若 为对应于基 B 的基本可行解，且对于一切，有 j 0，则 X 为线性规划问题的最优解。定理1.6 无穷多最优解判别定理:若 为对应于基 B 的基本可行解，且对于一切，

20、有 j 0，又存在某个非基变量的检验数，则线性规划问题有无穷多最优解。定理1.7 无有限最优解判别定理：若 为对应于基 B 的基本可行解，有一个，而对于有，则线性规划问题无有限最优解(也称为无最优解)。以上讨论的都是针对标准型的，即求目标函数极大化问题。当求目标函数极小化时，一种情况如前所述，将其化为标准型；另一种情况是将判别定理中的检验数j 0改为 即可。,（0）,定理1.5 最优解判别定理:,44,由式(1.15)可知，当某些非基变量的检验数j 0时，如果xj增加，则目标函数值还可以增加。当有两个或两个以上j 0时，那么选哪个非基变量作为换入变量呢？为了使目标函数值增加的最快，我们一般选择

21、j 0中的最大者，即：j=max ll 0 j所对应的变量xj为换入变量(就是下一个基的基变量)。,3.基变换（1）换入变量的确定,45,因为基变量个数总是为m，所以换入一个变量之后还必须换出一个变量。下面我们来考虑如何选择换出变量。确定换出变量的原则是保持解的可行性。这就是说，要使原基本可行解的某一个正分量xj变为0，同时保持其余分量均非负。具体实现是按“最小比例原则”进行，也称原则。若 则选基变量xl为换出变量。（3）旋转运算（迭代运算）在确定了换入变量xj与换出变量xl之后，要把xj和xl的位置对换，就是说，要把xj 所对应的列向量pj变成单位向量。这时只需对系数矩阵的增广矩阵进行变换即

22、可，称alj为旋转元。,（2）换出变量的确定,46,在确定了换入变量xj与换出变量xl之后，要把xj和xl的位置对换，就是说，要把xj 所对应的列向量pj变成单位向量。这时只需对系数矩阵的增广矩阵进行变换即可，称alj为旋转元。,（3）旋转运算（迭代运算）,47,表13 初始单纯形表,48,以表13中的元素alj(称为主元素或旋转元素)进行基变换：将第l行每个元素除以 alj，再将第 l行每个元素乘以 aij/alj 加到第 i 行(i=1,2,m,i l)，将第 l 行每个元素乘以 j/alj 加到检验数行，对应的新的目标函数值即为：经过基变换之后，针对于新基 B1 的基本可行解为：,49,

23、第一步：找出初始可行基，确定初始基本可行解，建立初始单纯形表；第二步：检查对应于非基变量的检验数 k，kIN，(IN为非基变量指标集)，若所有 k 0，kIN，则已得到最优解，停止计算，否则转入下一步；第三步：在所有k 0，kIN 中，若有一个j 对应的系数 列向量 aij 0，则此问题没有有限最优解，停止计算，否则转入下一步；第四步：根据 max kk 0，kIN=j，确定 xj 为换 入变量(即为新基的基变量)，再根据：确定 xl为换出变量(即为新基的非基变量)，转下一步；第五步：以 alj 为主元素进行基变换，转回第二步。,单纯形算法的计算步骤:,50,利用单纯形算法求解例11的线性规划

24、问题。Max Z=2x1+3x2+0 x3+0 x4+0 x5 3x2+x3=15 s.t.4x1+x4=12 2x1+2x2x5=14 x1，x2，x3，x4，x50,例18,解：（1）由标准型得到初始单纯形表：,51,(2)max1,2=3=2，所以x2为换入变量。(3)因为1=2，2=3都大于0，且p1,p2的坐标有正分量存在因为5与x3那一行相对应，所以x3为换出变量；故x2对应列与x3对应行的相交处的3为主元素；(4)以“3”为主元素进行旋转计算，进行行初等变换，得表15：表15,52,重复以上步骤得表16。表16这时，检验数全部小于等于0，即目标函数已不可能再增大，于是得到最优解：

25、X*=(2,5,0,4,0)目标函数的最大值为：Z*=19,T,53,利用单纯形算法求解线性规划问题。Max Z=4x1+3x2+0 x3+0 x4+0 x5 2x1+2x2+x3=1600 5x1+2.5x2+x4=2500 x1+x5=400 x1,x2,x3,x4,x50 解：（1）由标准型得到初始单纯形表17：表17,例19,54,表18,表19,55,表110,这时，检验数全部小于等于0，即目标函数已达到最大，因此得到最优解：X=(200,600,0,0,200)目标函数的最大值为：Z=2600,T,56,利用单纯形算法求解线性规划问题。Max Z=2x1+3x2+0 x3+0 x4

26、+0 x5+0 x6 2x1+2x2+x3=12 s.t.x1+2x2+x4=8 4x1+x5=16 4x2+x6=12 x1，x2，x3，x4，x5,x60解：（1）由标准型得到初始单纯形表：表111,例110,57,表112,表113,58,在相同 对应的变量中选择下标最大的那个基变量-换出变量；同时如果出现有两个或更多的检验数大于零且相同时，在相同 对应的变量中选择下标最小的那个基变量为进入变量，-避免出现“死循环”表114,最优解：X*=(4,2,0,0,0,4)目标函数的最大值为：Z*=14,T,相同的问题-退化问题-表113,59,1.4 单纯形算法的进一步讨论,(一)、大M法(二

27、)、两阶段法,初始基本可行解的求法,60,解:令S=-S 加入松弛变量x4,剩余变量x5,-M x6-M x7,再加入人工变量x6,x7,(一)、大M法 例,s.t.,61,62,63,所有 j 0，X*=(4,1,9,0,0,0,0)T S=2 S=-2,64,判定无解条件：当进行到最优表时，仍有人工变量在基中，且0，则说明原问题无可行解。,65,用两阶段法求解L.P的最优解:,解:加入松弛变量、剩余变量、人工变量：x6,x7 第一阶段的问题,min W=x6+x7=max W=-x6-x7,(二)、两阶段法-例,s.t.,s.t.,66,67,68,第二阶段的计算问题,s.t.,69,70

28、,两阶段法步骤,第一阶段：解辅助问题，当进行到最优表时,、若W=0,则得到原问题的一个基本可行 解，转入第2阶段。,第二阶段：用求出的初始基本可行解求最优解。,、若W0,则判定原问题无可行解,71,例:,s.t.,72,原问题无可行解,73,(1)、L.P数学模型及标准型,(2)、L.P问题解的性质：图解法,总结,(3)、单纯形法：,1)、标准型中有单位基。,3)、判定最优解定理：,maxS问题，检验数 j 0minS问题，检验数 j 0,74,建模有问题,5)、退化解问题,75,我们以 作为标准型，以 作为最优解的判别准则。还有其它形式，下面把几种检验数的表示方法及判别准则汇总于表126。,

29、表126,标准型,检验数,对于目标函数求极小值的问题采用上述任何一种处理方法，其单纯形法的步骤与求极大值的方法相同。这里提醒注意，在阅读其它有关线性规划的教科书时，一定要注意该书规定的标准型是目标函数求极大值还是求极小值，检验数是cj-zj还是zj-cj，不同的组合会使判别准则不同，但单纯形的计算步骤是不变的。,(三）检验数的几种表示方法,76,现要做100套钢架，每套用长为2.9m,2.1m和1.5m的圆钢各一根。已知原材料长7.4m，问应如何下料，使用的总原材料最省：,第五节 应用举例例（合理利用线材问题）,合计用料,料头,2.9m,2.1m,1.5m,77,解:设xi表示第 i项目的投资

30、额 i=1,2,3,4,5，目标是投资风险最小化，因此目标函数为：min Z=(0.1x1+0.06x2+0.18x3+0.12x4+0.04x5)约束条件为：x1+x2+x3+x4+x5=1,000,000 0.05 x1+0.08 x2+0.07 x3+0.06 x4+0.1 x5 80,000 0.1x1+0.17 x2+0.14 x3+0.22 x4+0.07 x5140,000(11 x1+8 x2+10 x3+4 x4+10 x5)/50000006 xi 0(i=1,2,3,4,5)用单纯形法可计算出结果。,78,某工厂要用三种原材料 C、P、H 混合调出三种不同格的产品 A、B

31、、D。已知产品的规格要求、产品单价、每天能供应的原材料数量及原材料单价分别见表1-28、表1-29。问该厂应如何安排生产，使利润收入为最大？,表1-28,表1-29,例114（配料问题）,79,解：依条件有：,又由于原料总限额已给定，加入到产品 A、B、D的原材料 C 总量每天不超过100kg，P 总量不超过100kg，H 总量不超过60kg。由此有：AC+BC+DC 100 AP+BP+DP 100 AH+BH+DH 60,80,我们的目的是使利润最大，即产品价格减去原材料的价格为最大。目标函数：MaxZ=50(x1+x2+x3)+35(x4+x5+x6)+25(x7+x8+x9)-65(x

32、1+x4+x7)25(x2+x5+x8)35(x3+x6+x9)=-15x1+25x2+15x3 30 x4+10 x5+0 x6 40 x7+0 x8 10 x9 约束条件：-1/2 x1+1/2x2+1/2x3 0-1/4x1+3/4x2 1/4x3 0-3/4x4+1/4x5+1/4x6 0-1/2x4+1/2x5 1/2x6 0 x1+x4+x7 100 x2+x5+x8 100 x3+x6+x9 60 x1，x9 0 上述数学模型，可用单纯形表计算，计算结果是：每天只生产产品 A 200 kg，分别需要用原料 C 100 kg；P 50 kg；H 50 kg。总利润收入是 Z=500

33、 元/天。,81,某部门在今后5年内考虑给下列项目投资，已知：项目A：从第一年到第四年每年年初需要投资，并于次年末回收本利115%；项目B：第三年年初需要投资，到第五年年末能回收本利125%，但规定最大投资额不超过4万元；项目C：第二年年初需要投资，到第五年年末能回收本利140%，但规定最大投资额不超过3万元；项目D：五年内每年年初可购买公债，于当年年末归还，并加利息6%。已知该部门现有资金10万，问它应如何确定给这些项目每年的投资额，使到第五年年末拥有资金的本利总额为最大？,例115（连续投资问题）,82,解：(1)确定变量：这是一个连续投资问题，与时间有关。但这里设法用线性规划方法静态地处

34、理。设：xiA：表示第 i 年年初给项目 A 的投资额 i=1,5；xiB：表示第 i 年年初给项目 B 的投资额 i=1,5；xiC：表示第 i 年年初给项目 C 的投资额 i=1,5；xiD：表示第 i 年年初给项目 D 的投资额 i=1,5；它们都是待定的未知变量。(2)投资额应等于手中拥有的资金额。由于项目D 每年都可以投资，并且当年末即可收回本息，所以该部门每年应把资金全部投出，手中不应当有剩余的呆滞资金。,83,因此有：,（3）目标函数：目标要求是在第五年年末该部门手中拥有的资金额达到最大。这个目标函数可表示为：Max Z=1.15x4A+1.25x3B+1.40 x2C+1.06

35、x5D,84,(4)数学模型：Max Z=1.15x4A+1.25x3B+1.40 x2C+1.06x5D,(5)用单纯形法计算结果得到：x1A=34783元，x1D=65217元，x2A=39130元，x2C=30000元，x2D=0，x3A=0，x3B=40000元，x3D=0，x4A=45000元，x4D=0，x5D=0，到第五年年末该部门拥有资金总额为143750元，即盈利43.75%。,85,某厂生产三种产品I、II、III，每种产品要经过A、B 两道工序加工。设该厂有两种规格的设备能完成 A 工序，它们以 A1、A2 表示；有三种规格的设备能完成 B 工序，它们以 B1、B2、B3

36、 表示。产品I可在A、B任何一种规格设备上加工；产品II可在任何规格的 A 设备上加工，但在完成 B 工序时，只能在 B1 设备上加工；产品III只能在 A2与 B2 设备上加工。已知在各种机床设备的单件工时，原材料费，产品销售价格，各种设备的有效台时以及满负荷操作时机床设备的费用如下表130所示，要求安排最优的生产计划，使该厂的利润为最大?,表130,例116（生产计划安排问题）,86,解：首先列出所有可能生产产品I、II、III的工序组合形式，并假设按各种工序的组合形式进行生产的产量。具体如下：按(A1，B1)组合方式生产产品I，其产量设为 x1;按(A1，B2)组合方式生产产品I，其产量

37、设为 x2;按(A1，B3)组合方式生产产品I，其产量设为 x3;按(A2，B1)组合方式生产产品I，其产量设为 x4;按(A2，B2)组合方式生产产品I，其产量设为 x5;按(A2，B3)组合方式生产产品I，其产量设为 x6;按(A1，B1)组合方式生产产品II，其产量设为 x7;按(A2，B1)组合方式生产产品II，其产量设为 x8;按(A2，B2)组合方式生产产品III，其产量设为 x9;目标函数应为：Max Z=(1.25-0.25)(x1+x6)+(2.00-0.35)(x7+x8)+(2.80-0.50)x9 300/60005(x1+x2+x3)+10 x7321/100007(x4+x5+x6)+9x8+12x9 250/40006(x1+x4)+8(x7+x8)+780/70004(x2+x5)+11x9200/4007(x3+x6),87,