运筹学+第四版+第二章+线性规划及单纯形法.ppt

线性规划及单纯形法,线性规划及单纯形法,线性规划问题及其数学模型图解法单纯形法原理单纯形法的计算步骤,第一节线性规划问题及其数学模型,一、问题的提出,线性规划主要解决：如何利用现有有限的资源，使得预期目标达到最优的问题。,例1某工厂在计划期内要安排生产A、B两种产品（假定产品畅销）。已知生产单位产品的利润与所需的劳动力、设备台时及原材料的消耗，如表1.1所示问该厂应如何安排生产使获利最大？,表1-1,问题要求给出一个方案(产品A生产多少；产品B生产多少),设该工厂生产A、B两种产品产量分别为,确定决策变量,表1-1,制定方案的目标是什么？,该厂获取的利润可表示为,问题的目标：,确定目标函数,利润最大化,表1-1,方案的制定受到那些现实条件制约：,人力资源（劳动力）的限制：,设备工时的限制：,原材料资源的限制：,此外，决策变量的取值不应为负值即,确定约束条件,其中,目标函数,约束条件,资源约束,非负约束,约束条件可记s.t(subjectto),意思为“以,为条件“、”假定“、”满足“之意。,综上所述，我们得到了这个问题的数学模型,建立问题的线性规划模型步骤,1确定决策变量决策变量是模型所要决定的未知量，也是模型最重要的参数它用以表明规划中的用数量表示的方案、措施，可由决策者决定和控制,2确定目标函数就是将决策者所追求的目标表示为决策变量的函数它决定了线性规划优化的方向，是线性规划的重要组成部分,3确定约束条件这些约束条件可用含有决策变量的等式或不等式来表示,例2给海狸鼠配饲料饲料中营养要求：Va每天至少700克，Vb每天至少30克，VC每天刚好200克。现有五种饲料，搭配使用，饲料成分如下表：,问：应如何搭配饲料，使费用最小？,确定决策变量：设抓取饲料Ix1kg;饲料IIx2kg;饲料IIIx3kg确定目标函数：minZ=2x1+7x2+4x3+9x4+5x5确定约束条件：3x1+2x2+x3+6x4+18x5700 x1+0.5x2+0.2x3+2x4+0.5x5300.5x1+x2+0.2x3+2x4+0.8x5=200 x150,x260,x350,x470,x540 x10,x20,x30,x40,x50,营养要求,用量要求,非负约束,综上所述，便得到如下的数学模型：,美佳公司计划制造、两种家电产品。已知各制造一件时分别占用的设备A、B的台时、调试工序及每天可用于这两种家电的能力、各售出一件时的获利情况，如表1-2所示。问该公司应制造两种家电各多少件，使获取的利润最大？,课堂练习,表1-2,其数学模型为：,例3：捷运公司在下一年度的14月份的4个月内拟租用仓库堆放物资。已知各月份所需仓库面积列于下表1-3。仓库租借费用随合同期而定，期限越长，折扣越大，具体数字见表1-4。租借仓库的合同每月初都可办理，每份合同具体规定租用面积和期限。因此该厂可根据需要，在任何一个月初办理租借合同。每次办理时可签一份合同，也可签若干份租用面积和租用期限不同的合同。试确定该公司签订租借合同的最优决策，目的是使所租借费用最少。,表1-3,表1-4,单位：100m2,单位；元/100m2,表1-2,表1-3,单位：100m2,单位；元/100m2,解：设表示捷运公司在第i(i=1,2,3,4)月初签订的租期为j(j=1,2,3,4)个月的仓库面积的合同（单位为100m2)。,15,10,20,12,经过上面的讨论，得到下面的LP模型：,目标函数,约束条件,每一个问题都有一组变量-称为决策变量，一般记为,下面从数学的角度来归纳上述三个例子的共同点。,每个问题中都有决策变量需满足的一组约束条件-线性的等式或不等式。,对决策变量每一组值：,代表了,一种决策方案。通常要求决策变量取值非负，即,二。线性规划问题的数学模型,都有一个关于决策变量的线性函数-称为目标函数。要求这个目标函数在满足约束条件下实现最大化或最小化。,我们将约束条件和目标函数都是决策变量的线性函数的规划问题称为线性规划。有时也将线性规划问题简记为LP（linearprogramming)其数学模型为：,上述模型的简写形式为：,若令,线性规划问题可记为矩阵和向量的形式：,用向量表示时，上述模型可写为：,三。线性规划问题的标准形式：,LP问题的数学模型的标准形式为：,其中常数项,LP问题标准形式的特征是：,求目标函数的最大值；约束条件为等式；决策变量非负。,下面分析如何将LP问题标准化：,若目标函数为,引进新的目标函数,则,的最小值即为,的最大值，即：,从而目标函数变换为：,（2）若约束条件为不等式，分为两种情况讨论：,加入松弛变量,加入剩余变量,（3）对于决策变量非负的要求，分为两种情况讨论：非正变量：即xk0令xk=-xk即可自由变量：即xk无约束令xk=xkxk,例1将LP问题,化为标准形。,解：引进新的目标函数,于是原LP问题化为标准形式：,例2将LP问题,化为标准形。,松弛变量,例3将LP问题,化为标准形。,剩余变量,例4将LP问题,化为标准形。,课堂练习,例4将LP问题,化为标准形。,我们得到例4的标准形为：,1.2线性规划问题的图解法,1.2线性规划图解法,所谓图解法，就是在平面直角坐标上画出各个约束条件所允许变化的范围，通过图上作业法求出最优解和目标函数值。,一个线性规划问题有解，是指能找出一组xj(j=1,2,n),满足所有约束条件，称这组xj为问题的可行解。,通常线性规划问题总是含有多个可行解，称全部可行解的集合为可行域。在用图解法求解时，可形象的看到可行域。在可行域中使目标函数值达到最优的可行解称为最优解,对不存在可行解的线性规划问题，称该问题无解,图解法背景知识,图解法背景知识,由中学知识可知：y=ax+b是一条直线。同理(如果Z值固定)Z=70 x1+120 x2,x2=-70/120 x1+Z/120也是一条直线,x2=-70/120 x1+Z/120也是一组平行的等值线,1.2.1图解法的步骤,1、建立直角坐标系；2、根据约束条件描绘可行域；3、作目标函数的等高线；4、求解最优点和最优目标函数值。,例题1生产计划问题,某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：,问题：如何安排生产计划，使得获利最多？,例1图解法,.,9080604020,020406080100,x1,x2,9x1+4x2360,4x1+5x2200,3x1+10 x2300,Z=70 x1+120 x2,maxZ=70X1+120X29X1+4X23604X1+5X22003X1+10X2300X10X20,最优解(20,24),Z=4280,可行域,课堂练习,用图解法求解下述线性规划问题。,1）,2）,3）,答案：,1）,2）,3）,x1=1,x2=1.5Z*=17.5,x1=15/4,x2=3/4Z*=33/4,x1=2,x2=6Z*=36,1.2.2求解的几种可能结局,1、无穷多最优解。2、唯一最优解。2、无界解。3、无解或无可行解。,解的可能性,多重最优解：无穷多个最优解。若在两个顶点同时得到最优解，则它们连线上的每一点都是最优解。唯一最优解：只有一个最优点。,解的可能性,无界解：线性规划问题的可行域无界，使目标函数无限增大而无界。（缺乏必要的约束条件）,解的可能性,无可行解：若约束条件相互矛盾，则可行域为空集,由图解法得到的启示,图解法虽然只能用来求解只具有两个变量的线性规划问题，但它的求解思路和几何上直观得到的一些概念判断，对于单纯形法有很大启示,1、求解线性规划问题时，解的情况有：唯一最优解；无穷多最优解；无界解；无可行解,2、若线性规划问题的可行解存在，则可行域是一个凸集,3、若线性规划问题的最优解存在，则最优解或最优解之一一定是可行域的凸集的某个顶点。,由图解法得到的启示,4、解题思路是：先找出凸集的任一顶点，计算在顶点处的目标函数值。比较周围相邻顶点的目标函数值是否比这个值大，如果为否，则该顶点就是最优解的点或最优解的点之一；否则转到比这个点的目标函数值更大的另一个顶点，重复上述过程，一直到找出使目标函数值达到最大的顶点为止。,1.3单纯形法原理,数学试验,LINDO软件包,LINDO软件包介绍,初试LINDO用LINDO求解整数规划注意事项,LINDO是一种专门用于求解数学规划问题的优化计算软件包,版权现在由美国LINDO系统公司(LindoSystemInc.)所拥有.LINDO软件包的特点是程序执行速度很快,易于输入、修改、求解和分析一个数学规划(优化问题),因此LINDO在教育、科研和工业界得到广泛应用.有关该软件的发行版本、发行价格和其他最新信息都可以从LINDO系统公司的INTERNET网络站点获取,该站点还提供部分LINDO软件的演示版本或测试版本学生版和演示版与发行版的主要区别在于对优化问题的规模(变量和约束数)有不同的限制.,LINDO是LinearInteractiveandDiscreteOptimizer字首的缩写形式,可以用来求解线性规划(LP-LinearProgramming)、整数规划(IP-IntegerProgramming)和二次规划(QP-QuadraticProgramming)问题.LINDO学生版可求解多达200个变量和100个约束的规划问题.,初试LINDO,如解如下LP问题:,LINDO中己假设所有的变量都是非负的,所以非负约束条件不必再输入到计算机中;LINDO也不区分变量中的大小写字符(实际上任何小写字符都将被转换为大写字符);约束条件中的“=”可用“”代替.上述问题用键盘输入如下:,：MAX2X+3Y?ST,(说明:也可写成S.T.,SUCHTHAT或SUBJECTTO等）,?4X+3Y10?3X+5Y12?END：,注：目标函数为第1行,两个约束条件分别为第2,3行.,直接键入运行命令(GO)就可得到解答,屏幕显示如下:,:GOLPOPTIMUMFOUNDATSTEP2OBJECTIVEFUNCTIONVALUE1）7.4545450VARIABLEVALUEREDUCEDCOSTX1.272727.000000Y1.636364.000000ROWSLACKORSURPLUSDUALPRICES.000000.090909.000000.545455NO.ITERATIDNS=2DORANGE(SENSITIVITY)ANALYSIS?,单纯形法在2次迭代后得到最优解。,最优目标值,最优解：,:GOLPOPTIMUMFOUNDATSTEP2OBJECTIVEFUNCTIONVALUE1）7.4545450VARIABLEVALUEREDUCEDCOSTX1.272727.000000Y1.636364.000000ROWSLACKORSURPLUSDUALPRICES2）.000000.0909093）.000000.545455NO.ITERATIDNS=2DORANGE(SENSITIVITY)ANALYSIS?,单纯形进行了2次迭代,带有松弛变量和剩余变量的最优解：,检验数,减少的成本,对偶价格,一个问题解答之后,LINDO会询问是否需要作灵敏度分析(DORANGE(SENSITIVITY)ANALYSIS?).如果不需要,你应回答N(No),回到提示符:之下.,如果想重新看到刚才输入的模型,可键入LOOK命令,LINDO会询问具体的行号范围(也可直接将行号范围写在LOOK后).典型的行号范围可以是3,或1-2,或ALL,而结果相应地会显示出第3行、第1-2行,或问题的所有行.如:,:LOOKROW:,3(等价于直接命令“LOOK3”),3)3X+5Y=12:,如果想修改问题,可键入ALTER命令,LINDO会询问行号,变量名及新的系数,例如:若想将上述问题中约束条件4x+3y10,修改为6x+3y10,然后再全部看一下,并求解新问题,那么键入ALTER命令后相应要键入2,X,6然后再键入:“LOOKALL”.在相应位置再键入“GO”，就会给出解答.以下是屏幕上演示过程:,：ALTERROW：2VAR：XNEWCOEFFICIENT：6(等价于直接命令“ALTER2X6”）,:LOOKALLMAX2X+3YSUBJECTTO2)6X+3Y=103）3X+5Y=12,END:GOLPOPTIMUMFOUNDATSTEPOOBJECTIVEFUNCTIONVALUE1)7.333333VARIABLEVALUEREDUCEDCOSTX.666667.000000Y2.0000.000000ROWSLACKORSURPLUSDUALPRICES.000000.047619.000000.571429,NO.ITERATIONS=0DORANGE(SENSITIVITY)ANALYSIS?N:QUIT,改动约束条件的右端项,可以将RHS(即right-handside)作为变量名.改变约束条件中的不等号方向(如,可以将DIR作为变量名.修改问题还可用EXT命令(增加新的约行),DEL命令(去掉一行)和APPC命令(增加一个新的变量),也可用EDIT全屏幕编辑器.,灵敏度分析,下面用一个具体例子来说明LINDO软件求对偶变量及进行灵敏度分析.,例有一家具制造车间,制造书桌(DESK)、桌子(TABLE)、椅子(CHAIR),所用原料及木工、漆工的数据如表1所示.,表1,若要求桌子的生产量不超过5件,问如何安排三种产品的产量可使收入最大?,用分别表示书桌、桌子、椅子的生产量.建立LP模型:,将上述模型输入LINDO并求解:,：MAX6OX1+3OX2+2OX3?S.T?2)8X1+6X2+x348?3)4XI+2X2+1.5X320?4)2XI+1.5X2+0.5X38?5)X270 x2为进基,x3=3604x20 x4=2005x20 x5=30010 x20,x290 x240 x230,(030240500),X5为出基,基变换的图形意义,枢轴元素,线性规划及单纯形法,线性规划问题及其数学模型图解法单纯形法迭代原理单纯形法的计算步骤单纯形法的进一步讨论,2.4单纯形法计算步骤,一、代数解法,二、表格单纯形法,2.4单纯形法计算步骤,一、代数解法,二、表格单纯形法,例：用代数解法求解下面LP问题,解：由于该LP问题不是标准形式，故应先将其转换为标准式,1、确定初始基可行解,非奇异子阵，做为一个基,基变量x3,x4,x5非基变量x1,x2,在确定基变量后，可立即求得基可行解：,令x1,x2等于0，x3,x4,x5的值可立即从上式读出,初始基可行解为：,一个可行解就是一个生产方案，在上述方案中两种产品都不生产，利润Z=0。,因为每个等式只有一个系数为1的基变量，并且这个基变量只出现在这个等式。,Notice:,为什么基变量的值能如此方便的读出？,在后面的过程中，当基变量成员发生变化时，我们将对其系数矩阵做初等变换（高斯消元法Gaussianelimination），将其转化为这种方便的形式。这种形式被称为properformfromGaussianelimination,2、检验其最优性,从目标函数-Z+3x1+5x2+0 x3+0 x4+0 x5=0可知：非基变量x1和x2的检验数均为正数，生产哪种产品都会增加利润。故该初始基可行解不是最优解。,3、确定进基变量（迭代的第一步）,确定进基变量对应于图解法的确定运动方向,从目标函数-Z+3x1+5x2+0 x3+0 x4+0 x5=0可知：因为x2的系数大于x1的系数，即生产单位乙产品比甲产品利润更高一些，故应优先多生产乙产品。即x2为进基,进基变量的标识,4、确定出基变量（迭代的第二步）,确定出基变量对应于图解法的确定在那里停下来,基变量由非基变量线性表示：,保持原非基变量x1=0,x2逐渐增大时应保证：,x212/2,x236/4,X4为出基变量,出基变量的标识,5、对新基可行解的求解（迭代的第三步）,枢轴元素,下面是初等变换（高斯消元法）的具体步骤：,1/2,4,5,由于x1,x4是非基变量，令x1,x4等于0。,x2,x3,x5的值能够直接从上式读出，于是得到新的基可行解：,目标函数值Z=30,重复上述步骤，直到获得最优解,小结,初始化,最优性检验,迭代（Iteration）,最优？,yes,STOP,no,初始基可行解的确定,当前的基可行解是否最优？,包括三个步骤：1、确定进基变量（进基）2、确定出基变量（出基）3、对新基可行解的求解（高斯消元）,最优性检验：由于目标函数中x1的检验数为正数（1=30），故,不是最优解,开始第二次迭代,确定出基变量（迭代的第二步）：,确定进基变量（迭代的第一步）：x1为进基变量,保持原非基变量x4=0,x1逐渐增大并保证x3、x2、x5非负。,x18/1,x112/3,X5为出基变量,对新基可行解的求解（迭代的第三步）：使用高斯消元法,1/3,-3,由于x4、x5为非基变量，令x4=0,x5=0 x1,x2,x3的值能从上式直接读出，于是得到新的基可行解：,最优性检验：在目标函数中所有检验数非正（j0），可以判定该解为最优解。即,单纯形法的几何意义,X0=(0,0,8,12,36)T,X1=(0,6,8,0,12)T,X1=(4,6,4,0,0)T,课堂练习,第一次迭代x1为入基，x4为出基,第二次迭代x2为入基，x3为出基,2.4单纯形法计算步骤,一、代数解法,二、表格单纯形法,二、表格单纯形法,上节介绍的单纯形法的代数形式也许是了解单纯形法最好的形式。但是，它不是最方便的计算形式，特别是需要手工求解问题的时候。,表格形式的单纯形法仅记录本质的信息：决策变量的系数（包括约束条件和目标函数）等式右边的常数基变量（每次迭代时）,表格单纯形法强调了运算涉及的数字并且将计算紧凑的记录下来,1、单纯形表的格式：,迭代计算中每找出一个新的基可行解时，就重画一张单纯形表。含初始基可行解的单纯形表称初始单纯形表，含最优解的单纯形表称最终单纯形表。,2、表格单纯形法的计算步骤：,将线性规划问题化成标准型。,找出或构造一个m阶单位矩阵作为初始可行基，建立初始单纯形表。,计算各非基变量xj的检验数j=Cj-CBPj，若所有j0，则问题已得到最优解，停止计算，否则转入下步。,在大于0的检验数中，若某个k所对应的系数列向量Pk0，则此问题是无界解，停止计算，否则转入下步。,根据maxjj0=k原则，确定xk为换入变量(进基变量)（进基）再按规则计算：,确定xL为换出变量。建立新的单纯形表，此时基变量中xk取代了xL的位置。(出基),以aLk为枢轴元素进行迭代，把xk所对应的列向量变为单位列向量，即aLk变为1，同列中其它元素为0，（高斯消元），转第步。,小结,初始化,最优性检验,迭代（Iteration）,最优？,yes,STOP,no,初始基可行解的确定,当前的基可行解是否最优？,包括三个步骤：1、确定进基变量（进基）2、确定出基变量（出基）3、对新基可行解的求解（高斯消元）,3、表格单纯形法举例：,035000,单纯形表对应的代数式子：,检验行说明,最优解:X*=(4,6,4,0,0)T，Z*=42,分别用图解法和表格单纯形法求解下列线性规划问题，并对照指出单纯形法迭代的每一步相当于图解法可行域中的那一个顶点。,课堂练习,035000,最优解:X*=(2,6,2,0,0)T，Z*=36,课堂练习,用表格单纯形法解例1,070120000,070120000,最优解:X*=(20,24,84,0,0)T，Z*=4280,Completesetofsimplextableauxfortheproblem:,4、最优基和最优基的逆：,最优基,一定存在B-1使得,如何求得B-1?,单位矩阵,B-1,B-1被称为最优基的逆矩阵,5、表格单纯形法下的解的情况说明：,当所有j0时，表明现有顶点（基可行解）的目标函数值比起相邻各顶点（基可行解）的目标函数值都大，根据线性规划问题的可行域是凸集的证明以及凸集的性质，可以判定现有顶点对应的基可行解即为最优解。最优解存在两种情况：,（1）唯一最优解,在最终单纯形表中所有非基变量j0,又Pj0,可以看出,不存在，无出基变量，Z的取值无限增大，该线性规划问题无界解,例解LP问题,解：由于上式不是标准式，将其标准化得：,此时，检验数2=110，还没有得到最优解。确定x2进基，但x2所在列的系数向量元素非正，无界值不存在，有进基变量但无离基变量。,线性规划及单纯形法,线性规划问题及其数学模型图解法单纯形法迭代原理单纯形法的计算步骤单纯形法的进一步讨论,2.5单纯形法进一步讨论,一、人工变量法(大M法),二、两阶段法,三、单纯形法计算中的几个问题,2.5单纯形法进一步讨论,一、人工变量法(大M法),二、两阶段法,三、单纯形法计算中的几个问题,一、人工变量法(大M法),针对标准形约束条件的系数矩阵中不含单位矩阵的处理方法。,在上面例子中，化为标准形式后约束条件的系数矩阵中含有单位矩阵，以此作初始基，使求初始基和建立初始单纯形表都十分方便。,但在下面例子中，化为标准形后的约束条件的系数矩阵中不存在单位矩阵,强行加上人工变量，使其出现单位矩阵：,但这样处理后：不易接受。因为是强行引进，称为,人工变量。它们与不一样。称为松弛变量和剩,余变量，是为了将不等式改写为等式而引进的，而改写前后,两个约束是等价的。人工变量的引入一般来说是前后不等,价的。只有当最优解中，人工变量都取值零时（此时人工,变量实质上就不存在了）才可认为它们是等价的。,处理办法：把人工变量从基变量中赶出来使其变为非基变量。为此，发明者建议把目标函数作如下处理：,其中M为任意大的实数，“-M”称为“罚因子”。用意：只要人,工变量取值大于零，目标函数就不可能实现最优。,填入单纯形表，有：,x1x2x3x4x5x6x7,-30100-M-M,41111000,1-21-10-110,90310001,0-30100-M-M,x1x2x3x4x5x6x7,-30100-M-M,41111000,1-21-10-110,90310001,10M-2M-34M10-M00,x1x2x3x4x5x6x7,-30100-M-M,41111000,1-21-10-110,90310001,10M-2M-34M10-M00,4/11/19/1,x1x2x3x4x5x6x7,-30100-M-M,330211-10,1-21-10-110,660403-31,6M6M-304M+103M-4M0,3/3-6/6,x1x2x3x4x5x6x7,-30100-M-M,330211-10,1-21-10-110,660403-31,6M6M-304M+103M-4M0,3/3-6/6,x1x2x3x4x5x6x7,-30100-M-M,00001-1/21/2-1/2,3011/30001/3,1102/301/2-1/21/6,300303/2-M-3/2-M+1/2,-93/2,x1x2x3x4x5x6x7,-30100-M-M,00001-1/21/2-1/2,3011/30001/3,1102/301/2-1/21/6,300303/2-M-3/2-M+1/2,-93/2,x1x2x3x4x5x6x7,-30100-M-M,00001-1/21/2-1/2,5/2-1/2100-1/41/41/4,3/23/20103/4-3/41/4,-3/2-9/2000-3/4-M+3/4-M-1/4,注：如若到最终表中人工变量仍没有置换出去，那么这个问题就没有可行解，当然亦无最优解。,课堂练习,使用单纯形法中的大M法求解下列线性规划问题。,按大M法构造人造基，引入人工变量x4,x5的问题如下：,2.5单纯形法进一步讨论,一、人工变量法(大M法),二、两阶段法,三、单纯形法计算中的几个问题,2.5单纯形法进一步讨论,一、人工变量法(大M法),二、两阶段法,三、单纯形法计算中的几个问题,三、单纯形法计算中的几个问题,进基变量相持：单纯形法运算过程中，同时出现多个相同的j最大。在符合要求的j(目标为max：j0，min：j0)中，选取下标最小的非基变量为换入变量；,离基变量相持：单纯形法运算过程中，同时出现多个相同的最小值。继续迭代，便有基变量为0，称这种情况为退化解。选取其中下标最大的基变量做为换出变量。,多重最优解：最优单纯形表中，存在非基变量的检验数j=0。让这个非基变量进基，继续迭代，得另一个最优解。,无界解：大于0的检验数中，若某个k所对应的系数列向量Pk0，则解无界。,无可行解：最终表中存在人工变量是基变量。,其他应用例子,应用线性规划解决经济、管理领域的实际问题，最重要的一步是建立实际问题的线性规划模型。,而建立模型是一项技巧性很强的创造性工作，既要求对研究的问题有深入了解，由要求很好掌握线性模型的结构特点，并具有对实际问题进行数学描述的较强的能力。而且在研究一些较复杂的数学模型时，需要各方面专业人员的协作配合。,一般来讲，一个经济、管理问题要满足下列条件，才能归结为线性规划的模型：要求解的问题的目标能用某种效益指标度量，并能用线性函数描述目标的要求为达到这个目标存在多种方案要达到的目标是在一定约束条件下实现的，这些条件可以用等式或不等式描述,应用举例1：某糖果厂用原料A，B，C加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中A，B，C的含量，原料成本，各种原料每月的限制用量，三种牌号糖果的单位加工费及售价如表所示。,关键：如何决策变量,分析：用i=1,2,3分别代表原料A,B,C;用j=1,2,3分别代表甲、乙、丙三种糖果，则xij为生产第j种糖果耗用的第i种原料的数量(Kg)。,确定决策变量,三种糖果的生产量x甲，x乙，x丙分别为：,该厂每月生产这三种牌号糖果各多少，使其获利最大,确定目标函数,方案的制定受到那些现实条件制约：,原料月供应量限制,含量成分的限制,确定约束条件,综上所示，我们得到如下数学模型：,应用举例2：宏银公司承诺为某建设项目从2003年起的4年中每年初分别提供以下数额贷款：2003年100万2004年150万2005年120万2006年110万以上贷款资金均需于2002年底前筹齐。但为了充分发挥这笔资金的作用，在满足每年贷款额的情况下，可将多余资金用于下列投资项目：,投资1：于2003年初购买A种债劵，期限3年，到期后本息合计为投资额的140，但限购60万元投资2：于2003年初购买B种债劵，期限2年，到期后本息合计为投资额的125，但限购90万元投资3：于2004年初购买C种债劵，期限2年，到期后本息合计为投资额的130，但限购50万元投资4：于每年初将任意数额的资金存放于银行，年息4，于每年年底取出。,问宏银公司应如何运用这笔资金，使2002年底筹集到的资金数额最少？,分析：设x为2002年底宏银公司需要筹集到的资金额，y1,y2,y3为分别于2003、2004、2005年初存放到银行的资金数，A,B,C为分别购买A、B、C债劵的数额(单位均为万元)，则可列出如下数学模型：,求解得：,即宏银公司在优化操作资金条件下，为满足承诺的贷款数，于2002年底只需筹集到420.4万元即可。,例3投资项目的组合问题兴安公司有一笔30万元的资金，考虑今后3年内用于下列项目的投资：（1）三年内的每一年年初均可投资，每年获利为投资额的20%，其本利可一起用于下一年投资；（2）只允许第一年初投入，于第二年末收回，本利合计为投资额的150%，但此类投资额不超过15万元；（3）允许于第二年初投入，于第三年末收回，本利合计为投资额的160%，但限额投资20万元；,（4）允许于第三年初投入，年末收回，可获利40%，但限额10万元。试为该公司确定一个使第三年末本利和为最大的投资组合方案。,合理下料问题从给定尺寸的材料中，按需要的尺寸截取给定数量的零件，使残余废料总量最小的问题。三维（积材）下料问题长、宽、高二维（面料）下料问题长、宽一维（线材）下料问题长例4、下料问题：有一批长度为7.4m的钢筋，需要切断成长度为2.9m的129根；2.1m的100根；1.5m的72根。现在如何下料才能使用料最省？,建模分析：首先分析每根钢筋的切断方式，,设xj为第j种下料方式所需要的钢筋根数，Z为总料头,课后练习（一）,1用图解法求下列线性规划问题，并指出问题具有唯一最优解、无穷多最优解、无界界还是无可行解。,无