线性规划模型最新版本ppt课件

.,1,第1节线性规划问题与模型,一、线性规划模型从招聘总经理谈起,.,2,泰山工厂生产状况,泰山工厂可以生产两种产品出售，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：目前生产现状：不生产产品A，生产产品B每天30，获利3600,.,3,招聘总经理！,约翰：我应聘！在现有资源状况下，我可以使利润达到4280！方案是：生产A产品20，生产B产品24可行性：9*20+4*24=2760X(2)不是。,(3)选X1从0，X5=0,X1=min(6/1,36/3,1)=6X1进基，X3出基。,.,47,B3=(P1P4P2),令X3=X5=0X(3)=(6,12,0,18,0)TZ(3)=840,.,48,(2)150X(3)不是,(3)选X5从0，X3=0,X5=min(18/2,12/1/2)=9X5进基，X4出基。,.,49,B4=(P1P5P2),令X3=X4=0X(4)=(15,15/2,0,0,9)TZ(4)=975,.,50,0,(0,0),X2,X1,.,51,两个重要公式：,.,52,当LP的数学模型为一般型时,两个重要公式形如：,.,53,B=(P1P2Pm)=I,.,54,当Xj=0(j=m+1,n)时,.,55,1.5.2单纯形法原理,.,56,此时，B=(P1P2Pm),对应的基本可行解为,.,57,定理1：对解X(1)，若检验数j(j=m+1,n)全部0，则X(1)为最优解。,定理2：对X(1)，若有某个非基变量Xm+km+k0且相应的Pm+k=(a1m+k,amm+k)T0，则原问题无有限最优解。,.,58,定理2证明,X(2)=(b1-a1m+k,bm-amm+k,0,0)T,AX(2)=bX(2)0,Z=Z0+m+k,当时Z,.,59,初始基B1=(P3P4),X(1)=(0,0,10,15)TZ(1)=0,.,60,选中X1从0，X2=0,求X1，X1+,Z+,.,61,换基迭代公式：,(1)、决定换入变量：,(2)、决定换出变量：,bi-aim+kXm+k0(i=1,2,m),.,62,则Xr为换出变量。,.,63,定理3：经单纯形法得到的,.,64,若否，因为P1,Pm线性无关,.,65,X(2)是基本解，且是可行解,.,66,单纯形法基本步骤,(1)、定初始基，初始基本可行解,(3)、若有k0，Pk全0，停，没有有限最优解；否则转(4),(2)、对应于非基变量检验数j全0。若是，停，得到最优解；若否，转(3)。,.,67,定Xr为换出变量，arm+k为主元。,由最小比值法求：,.,68,转(2),(5)、以arm+k为中心，换基迭代,.,69,证明可用归纳法（略）,X在边界上,X在内部,(01),.,70,证明：设X(1),X(k)为可行域顶点，若X*不是顶点，但maxZ=CX*X*=,定理2：可行域有界，最优值必可在顶点得到,iX(i),i=1,0i1,CX*=,iCX(i),iCX(m),=CX(m),设CX(m)Max(CX(i),1ik,.,71,Z(2)-Z(1)=(Cm+k-Zm+k)=m+k0,.,72,1.5.3单纯形表,.,73,.,74,本问题的最优解X=(15,15/2,0,0,9)TZ=975,.,75,几点说明：,(1)、例maxZ=X1+2X2,.,76,.,77,.,78,X(1)=(2,3)Z(1)=8,X(2)=(4,2)Z(2)=8,无穷多解,.,79,.,80,.,81,判定定理1：基本可行解X，当全部j0时，X为最优解。,判定定理2：对可行基B，当某k0，且Pk=(a1kamk)T0，则原问题无有限最优解。,.,82,.,83,.,84,退化解,X*=(0,3/2,0,1/2,0)T,Zmax=18,.,85,(P1P2P3)(P4P2P3)(P4P5P3)(P6P5P3)(P6P7P3)(P1P7P3)(P1P2P3),.,86,(4)例：,.,87,.,88,.,89,本问题无界。,.,90,1.5.4初始基本可行解的求法,(一)、大M法：判定无解条件：当进行到最优表时，仍有人工变量在基中，且0，则说明原问题无可行解。,.,91,例1：,.,92,.,93,.,94,.,95,.,96,.,97,解题过程：,.,98,两阶段法原理：,(1)、辅助问题的基本可行解X(0)为最优解，对应最小值=0则X(0)的前n个分量是原问题的基本可行解。,.,99,证明：,.,100,(2)、原问题有可行解时，辅助问题最优值=0。,.,101,maxZ=-X1+2X2,X1+X22-X1+X21X23X1X20,例2：,.,102,第(1)阶段：,.,103,.,104,.,105,例3：,.,106,第(1)阶段：,.,107,.,108,.,109,第1阶段最优基B*min=*,(1)、*0,.,110,1)arj全=0()式多余方程,2)arj有0元，设为ars0,以ars为主元，换基迭代，最后得到,.,111,例4、求,.,112,一,二,.,113,CBXB000005/205/40X21011/4-2/31/20-1/21y200000-3/21-1/40X12101/20101/6,第一阶段,三,-40-30X1X2X3X4CBXB-800-100X21011/4-2/3-4X42101/20,第二阶段,.,114,的特殊情况:第1阶段结束时,有人工变量在基中取0,但Xi系数全为0,此方程为多余方程。,.,115,例5、求,.,116,一,二,.,117,.,118,-40-30X1X2X3X4CBXB-800000X21010-2/3-3X300010-4X121000,第二阶段,的特殊情况，可将人工变量换出,.,119,单纯形法小结：,1)、标准型中有单位基。,.,120,建模有问题,5)、退化解问题,.,121,.,122,第三章运筹学优化模型,大连海事大学刘巍,.,123,第3节对偶线性规划与影子价格,一、对偶问题再谈招聘总经理,.,124,泰山工厂生产状况,泰山工厂可以生产两种产品出售，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：目前生产现状：不生产产品A，生产产品B每天30，获利3600,.,125,招聘总经理！,约翰：我应聘！在现有资源状况下，我可以使利润达到4280！方案是：生产A产品20，生产B产品24可行性：9*20+4*24=2763604*20+5*24=2003*20+10*24=300,.,126,怎么达到的？,约翰使用了运筹学中的线性规划模型问题：如何安排生产计划，使得获利最多？步骤：1、确定决策变量：设生产A产品x1kg,B产品x2kg2、确定目标函数：maxZ=70X1+120X23、确定约束条件：设备约束9X1+4X2360人力约束4X1+5X2200原材料约束3X1+10X2300非负性约束X10X20,.,127,例1图示,.,9080604020,020406080100,x1,x2,9x1+4x2360,4x1+5x2200,3x1+10 x2300,A,B,C,D,E,F,G,H,I,Z=70 x1+120 x2,.,128,X1=20,x2=24对应的生产方案：生产A产品20生产B产品24获利：70*20+120*24=4280,.,129,问题的最优解,*最优解如下*目标函数最优值为:4280变量最优解相差值-x1200 x2240约束松弛/剩余变量对偶价格-18402013.6305.2目标函数系数范围:变量下限当前值上限-x1367096x287.5120233.333常数项数范围:约束下限当前值上限-1276360无上限2150200226.9233227.586300400,.,130,再谈招聘总经理,约翰作为总经理将泰山工厂经营的很好了！汤姆来竞争了！竞争口号：不裁员！不减薪！不加班！提高利润5%！,.,131,可能吗？,目前约翰的经营已经是资源的最佳利用了！汤姆还有什么绝招增加利润呢？,.,132,这个问题涉及到：（1）线性规划的对偶问题（2）影子价格概念,.,133,原来问题的最优解,*最优解如下*目标函数最优值为:4280变量最优解相差值-x1200 x2240约束松弛/剩余变量对偶价格-18402013.6305.2目标函数系数范围:变量下限当前值上限-x1367096x287.5120233.333常数项数范围:约束下限当前值上限-1276360无上限2150200226.9233227.586300400,.,134,对偶性是线性规划问题的最重要的内容之一。每一个线性规划（LP）必然有与之相伴而生的另一个线性规划问题，即任何一个求maxZ的LP都有一个求minZ的LP。其中的一个问题叫“原问题”，记为“P”，另一个称为“对偶问题”，记为“D”。,例：资源的合理利用问题已知资料如表所示，问应如何安排生产计划使得既能充分利用现有资源有使总利润最大？,对偶问题的提出,.,135,下面从另一个角度来讨论这个问题：,假定：该厂的决策者不是考虑自己生产甲、乙两种产品，而是将厂里的现有资源用于接受外来加工任务，只收取加工费。试问该决策者应制定怎样的收费标准（合理的）？,.,136,分析问题：1、每种资源收回的费用不能低于自己生产时的可获利润；2、定价又不能太高，要使对方能够接受。,.,137,一般而言，W越大越好，但因需双方满意，故,为最好。,该问题的数学模型为：,.,138,模型对比：,.,139,对称形式：互为对偶(LP)Maxz=cTx(DP)Minf=bTys.t.Axbs.t.ATycx0y0“Max-”“Min-”一般形式：若一个问题的某约束为等式，那么对应的对偶问题的相应变量无非负限制；反之，若一个问题的某变量无非负限制，那么对应的对偶问题的相应约束为等式。,对偶定义,.,140,对偶问题,令y1=y1-y1,.,141,解：,.,142,(3)、原问题第k个约束为等式，对偶问题第k个变量是自由变量。原问题第k个变量是自由变量，则对偶问题第k个约束为等式约束。,.,143,对偶关系对应表,.,144,例2、写对偶规划,minZ=4X1+2X2-3X3,-X1+2X262X1+3X39X1+5X2-2X3=4X2,X30,.,145,maxW=6y1+9y2+4y3,-y1+2y2+y3=42y1+5y323y2-2y3-3y10,y20,y3自由,.,146,minZ=4X1+2X2-3X3,X1-2X2-62X1+3X39X1+5X2-2X3=4X2,X30,或将原问题变形为,.,147,maxW=-6y1+9y2+4y3,y1+2y2+y3=4-2y1+5y323y2-2y3-3y1,y20,y3自由,对偶规划,.,148,产品A，B产量X1，X2，Z为利润,例1、,.,149,X=(8,24)TZ=184,.,150,.,151,y=(2/9,13/9),Z=184,.,152,观察结论:,一对对偶问题都有最优解，且目标函数值相等。,最优表中有两个问题的最优解。,.,153,1.7.2对偶问题解的性质,.,154,定理1、(弱对偶定理),.,155,推论2、(P)有可行解,但无有限最优解，则(D)无可行解。,推论1、(P),(D)都有可行解，则必都有最优解。,.,156,.,157,.,158,.,159,定理4(松紧定理)互补松弛性,原问题,.,160,对偶问题,.,161,.,162,.,163,.,164,.,165,例：,min=5y1+y2,.,166,(P)最优解(0,9,0,4,64),=9,.,167,.,168,.,169,解：(D)为,.,170,将y1，y2代入，知,为严格不等式,x2=x3=x4=0,x=(1,0,0,0,1)TZ=5,.,171,小结：原问题与对偶问题的关系,互为对偶最优解的存在性相同。目标函数值相等。解互为影子价格。,.,172,影子价格在管理决策中的作用,.,173,原来问题的最优解,*最优解如下*目标函数最优值为:4280变量最优解相差值-x1200 x2240约束松弛/剩余变量对偶价格-18402013.6305.2目标函数系数范围:变量下限当前值上限-x1367096x287.5120233.333常数项数范围:约束下限当前值上限-1276360无上限2150200226.9233227.586300400,.,174,4.影子价格可以告诉决策者，用多大的代价增加资源才是合算的。如：第二种资源增加1单位能使收益增加13.6，如果增加这种资源的代价大于13.6就不划算了。,3.影子价格可以告诉决策者，增加哪一种资源对增加经济效益最有利。如：本例中三种资源的价格为0，13.6，5.2，说明首先应增加第二种资源，因为相比之下，它能使收益增加得更多。,.,175,5.影子价格可以告诉决策者应如何考虑新产品的价格。如：企业要生产一种新产品时，如果每件新产品耗用的这三种资源数量是1，2，3单位，则新产品的定价一定要大于才能增加公司的收益，如售价低于42.8的话，生产是不划算的。,.,176,汤姆的决策,设备资源的影子价格为0，不需要添加！人力资源的影子价格为13.6，而在市场上人力资源的价格是5，因此，招聘人力26人！原材料的影子价格为5.2，可是市场上这种材料价格是5.9，买入不上算！不增加！,.,177,新的线型规划模型,1、确定决策变量：设生产A产品x1kg,B产品x2kg2、确定目标函数：maxZ=70X1+120X23、确定约束条件：设备约束9X1+4X2360人力约束4X1+5X2226原材料约束3X1+10X2300非负性约束X10X20,.,178,*最优解如下*目标函数最优值为:4633.6变量最优解相差值-x130.40 x220.880约束松弛/剩余变量对偶价格-12.8802013.6305.2目标函数系数范围:变量下限当前值上限-x1367096x287.5120233.333常数项数范围:约束下限当前值上限-1357.12360无上限2150226226.9233297.517300452,.,179,新的生产计划：生产A产品30.4生产B产品20.88获利4633.6相比约翰的经营增加纯利润353.6-130=223！提高5.2%！,.,180,热烈祝贺汤姆竞聘泰山工厂总经理成功！,.,181,问题,可不可以再进一步增加人力资源？从而能否用这种方式使利润进一步提高？,.,182,将人力资源增加到250人！,1、确定决策变量：设生产A产品x1kg,B产品x2kg2、确定目标函数：maxZ=70X1+120X23、确定约束条件：设备约束9X1+4X2360人力约束4X1+5X2250原材料约束3X1+10X2300非负性约束X10X20,.,183,计算结果,*最优解如下*目标函数最优值为:4646.11变量最优解相差值-x130.7690 x220.7690约束松弛/剩余变量对偶价格-104.359223.07703010.256目标函数系数范围:变量下限当前值上限-x13670270 x231.111120233.333常数项数范围:约束下限当前值上限-11203604322226.923250无上限3120300362.069,.,184,效益分析,利润4646.11增加4646.11-5*50=4391.11相比人力资源为226时的利润4391.11-4633.6=-142.49,.,185,注意！将人力资源增加到227人时,1、确定决策变量：设生产A产品x1kg,B产品x2kg2、确定目标函数：maxZ=70X1+120X23、确定约束条件：设备约束9X1+4X2360人力约束4X1+5X2227原材料约束3X1+10X2300非负性约束X10X20,.,186,人力资源为227时最优解,*最优解如下*目标函数最优值为:4646.11变量最优解相差值-x130.7690 x220.7690约束松弛/剩余变量对偶价格-104.3592.07703010.256目标函数系数范围:变量下限当前值上限-x13670270 x231.111120233.333常数项数范围:约束下限当前值上限-1120360360.242226.923227无上限3120300300.207,.,187,原来是这样啊！,此时人力资源的影子价格为0！再增加也不会带来新的利润！,.,188,新的问题,灵敏度分析且听下回分解,.,189,.,190,第三章运筹学优化模型,大连海事大学刘巍,.,191,第3节对偶线性规划与影子价格(续）,灵敏度分析汤姆总经理的失误,.,192,泰山工厂生产状况,泰山工厂可以生产两种产品出售，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：目前生产现状：不生产产品A，生产产品B每天30，获利3600,.,193,招聘总经理！,约翰：我应聘！在现有资源状况下，我可以使利润达到4280！方案是：生产A产品20，生产B产品24可行性：9*20+4*24=2760csMinj/asjasj0brMin-bi/airair0,灵敏度分析（续）,.,222,例、上例最优单纯形表如下00.250这里B-1=-20.51各列分别对应b1、b2、b3的单一0.5-0.1250变化。因此，设b1增加4，则x1,x5,x2分别变为：4+0*4=4，4+(-2)*4=-40，2+0.5*4=4用对偶单纯形法进一步求解，可得：x*=(4,3,2,0,0)Tf*=17,灵敏度分析（续）,.,223,增加一个变量增加变量xn+1则有相应的pn+1，cn+1。那么，计算出B-1pn+1n+1=cn+1-criarin+1填入最优单纯形表，若n+10则最优解不变；否则，进一步用单纯形法求解。例、前例增加x6，p6=(2,6,3)T，c6=5。计算得到,灵敏度分析（续）,用单纯形法进一步求解，可得：x*=(1,1.5,0,0,0,2)Tf*=16.5,.,224,增加一个约束增加约束一个之后，应把最优解带入新的约束，若满足则最优解不变，否则填入最优单纯形表作为新的一行，引入1个新的非负变量（原约束若是小于等于形式可引入非负松弛变量，否则引入非负人工变量），并通过矩阵行变换把对应基变量的元素变为0，进一步用单纯形法或对偶单纯形法求解。例、前例增加3x1+2x215，原最优解不满足这个约束。于是,灵敏度分析（续）,.,225,A中元素发生变化（只讨论N中某一列变化情况）与增加变量xn+1的情况类似，假设pj变化。那么，重新计算出B-1pjj=cj-criarij填入最优单纯形表，若j0则最优解不变；否则，进一步用单纯形法求解。,灵敏度分析（续）,可得最优解：x*=(3.2,0.8,0,0,2.4)Tf*=15.2,.,226,灵敏度分析（续）,灵敏度分析小结：1Ci发生变化2Bj发生变化3增加一个变量4增加一个约束5A中元素发生变化,返回目录,.,227,.,228,第三章运筹学优化模型,大连海事大学刘巍,.,229,第4节线性规划应用,学以致用，培养学生“用数学的意识是本节的重要目的学习线性规划的有关知识其最终目的就是运用它们去解决一些生产、生活中问题,.,230,线性规划的应用,1人力资源分配的问题2生产计划的问题3套裁下料问题4配料问题5投资问题,.,231,人力资源分配的问题,例1某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?,.,232,人力资源分配的问题,解：设xi表示第i班次时开始上班的司机和乘务人员数,这样我们建立如下的数学模型。目标函数：Minx1+x2+x3+x4+x5+x6约束条件：s.t.x1+x660 x1+x270 x2+x360 x3+x450 x4+x520 x5+x630 x1,x2,x3,x4,x5,x60,.,233,人力资源分配的问题,例2一家中型的百货商场，它对售货员的需求经过统计分析如下表所示。为了保证售货人员充分休息，售货人员每周工作5天，休息两天，并要求休息的两天是连续的。问应该如何安排售货人员的作息，既满足工作需要，又使配备的售货人员的人数最少？,.,234,人力资源分配的问题,解：设xi(i=1,2,7)表示星期一至日开始休息的人数,这样我们建立如下的数学模型。目标函数：Minx1+x2+x3+x4+x5+x6+x7约束条件：s.t.x1+x2+x3+x4+x528x2+x3+x4+x5+x615x3+x4+x5+x6+x724x4+x5+x6+x7+x125x5+x6+x7+x1+x219x6+x7+x1+x2+x331x7+x1+x2+x3+x428x1,x2,x3,x4,x5,x6,x70,.,235,2生产计划的问题,例3某公司面临一个是外包协作还是自行生产的问题。该公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？,.,236,生产计划的问题,解：设x1,x2,x3分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，x4,x5分别为由外协铸造再由本公司加工和装配的甲、乙两种产品的件数。求xi的利润：利润=售价-各成本之和产品甲全部自制的利润=23-(3+2+3)=15产品甲铸造外协，其余自制的利润=23-(5+2+3)=13产品乙全部自制的利润=18-(5+1+2)=10产品乙铸造外协，其余自制的利润=18-(6+1+2)=9产品丙的利润=16-(4+3+2)=7可得到xi（i=1,2,3,4,5）的利润分别为15、10、7、13、9元。,.,237,生产计划的问题,通过以上分析,可建立如下的数学模型:目标函数：Max15x1+10 x2+7x3+13x4+9x5约束条件：5x1+10 x2+7x380006x1+4x2+8x3+6x4+4x5120003x1+2x2+2x3+3x4+2x510000 x1,x2,x3,x4,x50,.,238,生产计划的问题,例4永久机械厂生产、三种产品，均要经过A、B两道工序加工。设有两种规格的设备A1、A2能完成A工序；有三种规格的设备B1、B2、B3能完成B工序。可在A、B的任何规格的设备上加工；可在任意规格的A设备上加工，但对B工序，只能在B1设备上加工；只能在A2与B2设备上加工。数据如表。问：为使该厂获得最大利润，应如何制定产品加工方案？,.,239,生产计划的问题,解：设xijk表示第i种产品，在第j种工序上的第k种设备上加工的数量。建立如下的数学模型:s.t.5x111+10 x2116000（设备A1）7x112+9x212+12x31210000（设备A2）6x121+8x2214000（设备B1）4x122+11x3227000（设备B2）7x1234000（设备B3）x111+x112-x121-x122-x123=0（产品在A、B工序加工的数量相等）x211+x212-x221=0（产品在A、B工序加工的数量相等）x312-x322=0（产品在A、B工序加工的数量相等）xijk0,i=1,2,3;j=1,2;k=1,2,3,.,240,生产计划的问题,目标函数为计算利润最大化，利润的计算公式为：利润=（销售单价-原料单价）*产品件数之和-（每台时的设备费用*设备实际使用的总台时数）之和。这样得到目标函数：Max(1.25-0.25)(x111+x112)+(2-0.35)x221+(2.80-0.5)x312300/6000(5x111+10 x211)-321/10000(7x112+9x212+12x312)-250/4000(6x121+8x221)-783/7000(4x122+11x322)-200/4000(7x123).经整理可得：Max0.75x111+0.7753x112+1.15x211+1.3611x212+1.9148x312-0.375x121-0.5x221-0.4475x122-1.2304x322-0.35x123,.,241,3套裁下料问题,例5某工厂要做100套钢架，每套用长为2.9m,2.1m,1.5m的圆钢各一根。已知原料每根长7.4m，问：应如何下料，可使所用原料最省？解：共可设计下列5种下料方案，见下表,设x1,x2,x3,x4,x5分别为上面5种方案下料的原材料根数。这样我们建立如下的数学模型。目标函数：Minx1+x2+x3+x4+x5约束条件：s.t.x1+2x2+x41002x3+2x4+x51003x1+x2+2x3+3x5100 x1,x2,x3,x4,x50,.,242,用计算软件计算得出最优下料方案：按方案1下料30根；按方案2下料10根；按方案4下料50根。即x1=30;x2=10；x3=0；x4=50；x5=0；只需90根原材料就可制造出100套钢架。注意：在建立此类型数学模型时，约束条件用大于等于号比用等于号要好。因为有时在套用一些下料方案时可能会多出一根某种规格的圆钢，但它可能是最优方案。如果用等于号，这一方案就不是可行解了。,套裁下料问题,.,243,4配料问题,例6某工厂要用三种原料1、2、3混合调配出三种不同规格的产品甲、乙、丙，数据如右表。问：该厂应如何安排生产，使利润收入为最大？,解：设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个。,.,244,配料问题,利润=总收入-总成本=甲乙丙三种产品的销售单价*产品数量-甲乙丙使用的原料单价*原料数量，故有目标函数Max50（x11+x12+x13）+35（x21+x22+x23）+25（x31+x32+x33）-65（x11+x21+x31）-25（x12+x22+x32）-35（x13+x23+x33）=-15x11+25x12+15x13-30 x21+10 x22-40 x31-10 x33约束条件：从第1个表中有：x110.5(x11+x12+x13)x120.25(x11+x12+x13)x210.25(x21+x22+x23)x220.5(x21+x22+x23),.,245,配料问题,从第2个表中，生产甲乙丙的原材料不能超过原材料的供应限额，故有(x11+x21+x31)100(x12+x22+x32)100(x13+x23+x33)60通过整理，得到以下模型：,.,246,配料问题,例6（续）目标函数：Maxz=-15x11+25x12+15x13-30 x21+10 x22-40 x31-10 x33约束条件：s.t.0.5x11-0.5x12-0.5x130（原材料1不少于50%）-0.25x11+0.75x12-0.25x130（原材料2不超过25%）0.75x21-0.25x22-0.25x230（原材料1不少于25%）-0.5x21+0.5x22-0.5x230（原材料2不超过50%）x11+x21+x31100(供应量限制）x12+x22+x32100(供应量限制）x13+x23+x3360(供应量限制）xij0,i=1,2,3;j=1,2,3,.,247,配料问题,例7.汽油混合问题。一种汽油的特性可用两种指标描述，用“辛烷数”来定量描述其点火特性，用“蒸汽压力”来定量描述其挥发性。某炼油厂有1、2、3、4种标准汽油，其特性和库存量列于表4-6中，将这四种标准汽油混合，可得到标号为1，2的两种飞机汽油，这两种汽油的性能指标及产量需求列于表4-7中。问应如何根据库存情况适量混合各种标准汽油，既满足飞机汽油的性能指标，又使2号汽油满足需求，并使得1号汽油产量最高？,表4-6,表4-7,.,248,配料问题,解：设xij为飞机汽油i中所用标准汽油j的数量(L)。目标函数为飞机汽油1的总产量：,库存量约束为：,产量约束为飞机汽油2的产量：,由物理中的分压定律，可得有关蒸汽压力的约束条件：,同样可得有关辛烷数的约束条件为：,.,249,配料问题,综上所述，得该问题的数学模型为：,.,250,配料问题,由管理运筹学软件求解得：,.,251,5投资问题,例8某部门现有资金200万元，今后五年内考虑给以下的项