1、线性规划图解法线性规划图解法 1832和和1911年法国数学家年法国数学家 J.B.J.傅里叶和傅里叶和 C.瓦莱普瓦莱普森分都分别独立地提出线性规划的想法，但未引起注意。森分都分别独立地提出线性规划的想法，但未引起注意。1939年，前苏联数学家康托洛维奇用线性规划模型研究年，前苏联数学家康托洛维奇用线性规划模型研究提高组织和生产效率问题提高组织和生产效率问题 1947年，年，Dantzig提出求解线性规划的单纯形法提出求解线性规划的单纯形法 1950-1956年，主要研究线性规划的对偶理论年，主要研究线性规划的对偶理论 1951年美国经济学家年美国经济学家T.C.库普曼斯把线性规划应用到经济
2、库普曼斯把线性规划应用到经济领域，为此与康托罗维奇一起获领域，为此与康托罗维奇一起获1975年诺贝尔经济学奖。年诺贝尔经济学奖。1958年，发表整数规划的割平面法年，发表整数规划的割平面法 1960年，年，Dantzig和和Wolfe研究成功分解算法，奠定了大研究成功分解算法，奠定了大规模线性规划问题理论和算法的基础。规模线性规划问题理论和算法的基础。一、线性规划发展概况第1页/共44页线性规划的研究成果还直接推动了其他数学规线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划划问题包括整数规划、随机规划和非线性规划的算法研究。由于数字电子计算机的发展，出的算法研究
3、。由于数字电子计算机的发展，出现了许多线性规划软件，如现了许多线性规划软件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解几千个变量的线等，可以很方便地求解几千个变量的线性规划问题。性规划问题。1979年，年，Khachiyan，1984年，年，Karmarkaa研究成功线性规划的多项式算法。用卡马卡方研究成功线性规划的多项式算法。用卡马卡方法求解线性规划问题在变量个数为法求解线性规划问题在变量个数为5000时只要时只要单纯形法所用时间的单纯形法所用时间的1/50。第2页/共44页二、线性规划研究解决的主要问题 实际上，上述两类问题是一个问题的两个不同的方面，都实际上，上述两类问题
4、是一个问题的两个不同的方面，都是求问题的最优解（是求问题的最优解（max 或或 min）。）。另一类是当一项任务确定以后，研究如何统筹安排，才能另一类是当一项任务确定以后，研究如何统筹安排，才能使完成任务所耗费的资源量为最少。使完成任务所耗费的资源量为最少。一类是已有一定数量的资源（人力、物质、时间等），一类是已有一定数量的资源（人力、物质、时间等），研究如何充分合理地使用它们，才能使完成的任务量研究如何充分合理地使用它们，才能使完成的任务量为最大。为最大。线性规划在工商管理中应用有着广泛的用处，可以用来解决诸如：线性规划在工商管理中应用有着广泛的用处，可以用来解决诸如：人力资源分配问题、生产
5、计划问题、下料配料、投资问题（见第人力资源分配问题、生产计划问题、下料配料、投资问题（见第4章）以及运输问题（第章）以及运输问题（第7章）等。实际上远不止这些具体问题。但章）等。实际上远不止这些具体问题。但从一般意义上解决得问题有两类：从一般意义上解决得问题有两类：第3页/共44页三、三、LP解决问题的一般思路解决问题的一般思路5、模型求解与解的调适。（获得最优方案、模型求解与解的调适。（获得最优方案一组决策变量的取值）。一组决策变量的取值）。1、对问题进行系统分析,搞清决策什么和决策目标是什么？2、明确是哪些因素（人为可控的，决策变量）影响决策目标（大小、明确是哪些因素（人为可控的，决策变量
6、）影响决策目标（大小变化），确定决策变量对目标（函数）影响系数，且与目标函数是否变化），确定决策变量对目标（函数）影响系数，且与目标函数是否呈线形关系。呈线形关系。3、哪些资源约束（或需求约束）条件制约着目标（最大或最小）。、哪些资源约束（或需求约束）条件制约着目标（最大或最小）。决策变量对这些资源（或需求）的单位消耗（单位产出）是多少？，决策变量对这些资源（或需求）的单位消耗（单位产出）是多少？，即要获得资源总量和投入产出系数。即要获得资源总量和投入产出系数。4、建立线形规划数学模型。6、方案实施与调整。第4页/共44页一、例示问题提出例例2.1-1 某厂在计划期内安排生产某厂在计划期内安排
7、生产两种产品，两种产品，生产所需资源限制及单生产所需资源限制及单位产品原料消耗由位产品原料消耗由下表给给出下表给给出 利润利润 50 100问：应如何安排生产计划才能使 总利润最大？甲甲乙乙资源限制资源限制设备设备11300台时原料原料A21400kg原料原料B01250kg解：解：1.确定决策变量：确定决策变量：设产品甲乙的产量分别为设产品甲乙的产量分别为：x1、x22.建立目标函数：建立目标函数：设总利润为设总利润为z，本例是：，本例是：max z=50 x1+100 x23.考虑约束条件考虑约束条件：x1+x2 300 2x1 +x2 400 x2 250 x1，x20第5页/共44页目
8、标函数目标函数 ：max z=50 x1+100 x2x1+x2 300 2x1 +x2 400 x2 250 x1，x20满足满足 约束条件：4.得到本问题的数学模型：第6页/共44页例例2.1-2 某厂生产两种产品，下表某厂生产两种产品，下表给给出了单位产品所需资源及单位产品出了单位产品所需资源及单位产品利润利润 问：应如何安排生产计划，问：应如何安排生产计划，才能使才能使 总利润最大？总利润最大？解：解：1.决策变量：设产品决策变量：设产品I、II的产量分的产量分 别为别为 x1、x22.目标函数：设利润为目标函数：设利润为z，则有：，则有：max z=2 x1+3 x23.约束条件：约
9、束条件：x1+2x2 8 4x1 16 4x2 12 x1，x20第7页/共44页例例2.1-3 某厂生产三种药物，这些某厂生产三种药物，这些药物可从四种不同的原料中提取。药物可从四种不同的原料中提取。下表给出了单位原料可提取药物的下表给出了单位原料可提取药物的量（有效单位数）量（有效单位数）要求：生产要求：生产A种药物至少种药物至少160单位；单位；B种药物恰好种药物恰好200单位，单位，C种药物不种药物不超过超过180单位，且使原料总成本最单位，且使原料总成本最小。小。解：解：1.决策变量：设四种原料的使用决策变量：设四种原料的使用 量分别为：量分别为：x1、x2、x3、x42.目标函数：
10、设总成本为目标函数：设总成本为z，则有：，则有：min z=5 x1+6 x2+7 x3+8 x43.约束条件：约束条件：x1+2x2+x3+x4 160 2x1 +4 x3+2 x4 160 3x1 x2+x3+2 x4 180 x1、x2、x3、x40 药物原料ABC单位成本（元吨）甲1235乙2016丙1417丁1228第8页/共44页二、二、LP问题一般模型问题一般模型1.决策变量：决策变量：X=(x1,x2,.,xn)T2.目标函数：目标函数：max(minz)=c1 x1+c2 x2+.+cnxn3.约束条件：约束条件：a11x1+a12 x2+.+a1n xn(=)b1 a21x
11、1+a22 x2+.+a2n xn(=)b2 am1x1+am2 x2+.+amn xn(=)bm x1,x2,xn0第9页/共44页三、三、LP模型特点模型特点1、都用一组决策变量都用一组决策变量X=(x1,x2,xn)T表示某一方案，且决策变量表示某一方案，且决策变量 取值非负；取值非负；满足以上三个条件的数学模型称为线性规划数学模型或满足以上三个条件的数学模型称为线性规划数学模型或LP模型模型2、都有一个要达到的目标，并且目标要求可以表示成决策变量的、都有一个要达到的目标，并且目标要求可以表示成决策变量的线线 性函数性函数；3、都有一组约束条件，这些约束条件可以用决策变量的线性等式或都有
12、一组约束条件，这些约束条件可以用决策变量的线性等式或 线性不等线性不等 式来表示。式来表示。第10页/共44页LP模型的其它表达形式模型的其它表达形式),2,1(0),2,1(max(min)11njxmibxaxczjnjijijnjjj简约形式简约形式矩阵形式矩阵形式0 max(min)XbAXCXznxxxX21决策变量决策变量常数项常数项nbbbb21系数矩阵系数矩阵nmijmnmmnnaaaaaaaaaaA212222111211价值系价值系数数ncccC21其中：其中：第11页/共44页1 优化条件：问题所要达到的目标能用线型函数描述，且能够用极值 （max 或 min）来表示；2
13、 限定条件：达到目标受到一定的限制，且这些限制能够用决策变量的 线性等式或线性不等式表示；3 选择条件：有多种可选择的方案供决策者选择，以便找出最优方案。第12页/共44页（二）LP建模步骤1 确定决策变量并收集有关参数：即需要我们作出决策或选择的量。一般情况下题目问什么，就把什么设置为决策变量。2 找列出所有限定条件：即决策变量受到的所有的资源与需求等约束；3 写出目标函数：即问题所要达到的目标，并明确是max 还是 min。（三）建模案例例2.1-4 某厂生产A、B两种产品，有关参数资料如下表所示，问如何组 织生产才能使效益最大：设：总利润为设：总利润为Z；产品；产品A、B产量为产量为x1
14、、x2，产品，产品C的销量为的销量为x3，报废量为，报废量为x4，则：，则：max z=4 x1+10 x2+3 x3 2 x4 2 x1+3x2 12 3x1 +4x2 24 4x2-x3-x4 =0 x3 5 x1、x2、x3、x4 0第13页/共44页2.2 2.2 线性规划图解法线性规划图解法一、解题步骤一、解题步骤4 将最优解代入目标函数，求出最优值。将最优解代入目标函数，求出最优值。1 建立坐标系并建立坐标系并在直角平面坐标系中画出所有的约束等式，然后找出满足所在直角平面坐标系中画出所有的约束等式，然后找出满足所有约束条件的公共部分，称为可行域，可行域中的点称为可行解。有约束条件的
15、公共部分，称为可行域，可行域中的点称为可行解。2 标出目标函数值改善的方向标出目标函数值改善的方向。3 画出目标函数等值线，若求最大（小）值，则令目标函数等值线沿目标画出目标函数等值线，若求最大（小）值，则令目标函数等值线沿目标函数值增加（或减少）的方向平行移动，找与可行域最后相交的点，该点函数值增加（或减少）的方向平行移动，找与可行域最后相交的点，该点就是最优解就是最优解。第14页/共44页用图解法用图解法求解下列线性规划问题（例求解下列线性规划问题（例1）x1+2x2 8 4x1 16 4x2 12 x1，x20 max z=2 x1+3 x2最优解：X*=(2,4)T最优值：Z*=14目
16、标函数等值线Z=0 x2x1ts.第15页/共44页可行域目标函数等值线最优解64-860 x1x2第16页/共44页目标函数：2110050 xxZMax0,021xx分别取决策变量为坐标向量建立直角坐标系。在直角分别取决策变量为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一坐标系里，图上任意一点的坐标代表了决策变量的一组值，每个约束条件都代表一个半平面。图示如下：组值，每个约束条件都代表一个半平面。图示如下：用图解法求解下列线性规划问用图解法求解下列线性规划问题题t s.30021 xx400221xx2502x第17页/共44页x2x1X20X2=0 x2x
17、1X10X1=0100200300100200300 x1+x2300 x1+x2=3001001002002x1+x24002x1+x2=400300200300400100100 x2250 x2=250200300200300 x1x2x2=0 x1=0 x2=250 x1+x2=3002x1+x2=400图2-1第18页/共44页x1x2z=20000=50 x1+100 x2图2-2z=27500=50 x1+100 x2z=0=50 x1+100 x2z=10000=50 x1+100 x2CBADE 综上得到最优解：最优目标值:250,5021xx27500z第19页/共44页1
18、、凸集、凸集 若连接若连接n维点集维点集P中任意两点中任意两点x（1），），x（2），其线段仍在），其线段仍在P内，则称内，则称P为凸集。即：为凸集。即：x|x=x(1)+(1-)x(2)，0 1,x(1)P,x(2)P P,则称则称P为凸集）为凸集）2、极点极点 若点若点x,且且x不是不是P中任何线段中任何线段的内点，则称点的内点，则称点x为凸集为凸集P的极点。显然多边的极点。显然多边形的顶点都是极点，四面体的顶点也都是极形的顶点都是极点，四面体的顶点也都是极点，而圆周上、球面上的每一个点都是极点，点，而圆周上、球面上的每一个点都是极点，其它点都不是极点。其它点都不是极点。二、关于凸集、极点
19、的概念第20页/共44页三、线性规划解的性质三、线性规划解的性质定理定理1 线性规划的可行域线性规划的可行域 R 是一个凸集，且有有限个极点。是一个凸集，且有有限个极点。定理定理2 X是线性规划可行域是线性规划可行域 R 顶点的充要条件是顶点的充要条件是 X 线性规划的基本可行解。线性规划的基本可行解。定理定理3 若线性规划有最优解，则必有基本最优解。若线性规划有最优解，则必有基本最优解。定理定理4 若线性规划在可行域的两个顶点上达到最优，则在两个顶点的连线若线性规划在可行域的两个顶点上达到最优，则在两个顶点的连线 上也达到最优。上也达到最优。线性规划的每一个基本可行解对应凸集的每一个顶点。若
20、线性规划有最优解，则一定在凸集的某个（些）顶点上达到最优。若线性规划有最优解，则一定在凸集的某个（些）顶点上达到最优。若线性规划在两个顶点以上达到最优若线性规划在两个顶点以上达到最优,则一定有无穷多个最优解。则一定有无穷多个最优解。最优解一定是基本可行解，但基本可行解不一定是最优解。最优解一定是基本可行解，但基本可行解不一定是最优解。第21页/共44页四、线性规划问题求解可能出现的情况四、线性规划问题求解可能出现的情况215050 xxZMaxx1x2z=20000=50 x1+100 x2图2-2z=27500=50 x1+100 x2z=0=50 x1+100 x2z=10000=50 x
21、1+100 x2CBADE12003421 xx则可行域为空域，不存在满足约束条件的解，当然也就不存在最优解了。4、无可行解。如果例3再增加一个约束条件3、无界解。即可行域延伸到无穷远，目标函数值可以无穷大或无穷小。2、如果最优解出现在两个极点上，则会有无穷多个最优解。1、如果LP有最优解，则一定有一个可行域的极点对应这个最优解；第22页/共44页五、五、LPLP解的有关概念及其关解的有关概念及其关系系1 可行解（可行解（feasible solution）：满足线性规划约束条件的解称为可行解。：满足线性规划约束条件的解称为可行解。（一）有关概念（一）有关概念2 最优解（最优解（optimal
22、 solution）：使线性规划目标函数达到最优的可行解称：使线性规划目标函数达到最优的可行解称为为 最优解。最优解。3 基本解（基本解（basic solution）：以线性规划约束等式的系数矩阵：以线性规划约束等式的系数矩阵A中任意中任意m行行m 列组成的列组成的mm满秩子矩阵为基矩阵，与基矩阵相对应的变量称为基变满秩子矩阵为基矩阵，与基矩阵相对应的变量称为基变量（量（basic variable），其余变量称为非基变量，若令非基变量为零，则可），其余变量称为非基变量，若令非基变量为零，则可求得基变量的解（值），这个解称为基本解。求得基变量的解（值），这个解称为基本解。4 基本可行解（基本
23、可行解（basic feasible solution）：满足非负约束的基本解称为基本可行解。满足非负约束的基本解称为基本可行解。若约束等式中有n个变量，m个约束，则基本解的个数mnC第23页/共44页令非基变量 x10，x2 0则得：X (0,0,3,1)T基本解当基变量为x2、x3，则非基变量为x1、x4令非基变量 x10，x4 0则得：X (0,1,5,0)T基本解 基本可行解？是基本可行解？x1 2x2 x3 3 2x1 x2 x4 1 x1,x2,x3,x40解：解：系数矩阵为：10120121A设基变量为x3、x4，则非基变量为x1、x23）X (1/2,1/2,3/2,1/2)T
24、不是基本解可行解是基本可行解？例 讨论下述约束方程的解第24页/共44页1 可行解与最优解：可行解与最优解：最优解一定是可行解，但可行解不一定是最优解。最优解一定是可行解，但可行解不一定是最优解。（二）线性规划解之间的关系（二）线性规划解之间的关系基本解不一定是可行解，可行解也不一定是基本解。基本解不一定是可行解，可行解也不一定是基本解。2 可行解与基本解：可行解与基本解：3 可行解与基本可行解：可行解与基本可行解：基本可行解一定是可行解，但可行解不一定是基本解。基本可行解一定是可行解，但可行解不一定是基本解。基本可行解一定是基本解，基本可行解一定是基本解，但基本解不一定是基本可行解。但基本解
25、不一定是基本可行解。4 基本解与基本可行解：基本解与基本可行解：5 最优解与基本解：最优解与基本解：最优解不一定是基本解，最优解不一定是基本解，基本解也不一定是最优解。基本解也不一定是最优解。问题：最优解与基本可行解？非可行解可行解基本可行解基本解第25页/共44页六、线性规划模型的标准形式及其标准化（一）线性规划模型标准形式特点 1目标最大化；目标最大化；2约束为等式；约束为等式；3决策变量均非负；决策变量均非负；4右端项非负。右端项非负。特点Max z=c1x1+c2x2+cnxna11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2 .am1x1+am2x2+a
26、mnxn=bm x1，x2，xn 0s.t第26页/共44页 如果目标函数为 Minnnxcxcxcf.2211该极小化问题与下面的极大化问题有相同的最优解，nnxcxcxcZMax.2211但必须注意，尽管以上两个问题的最优解相同，但它们最优解的目标函数值却相差一个符号，即：（二）线性规划模型标准化问题1、极小化目标函数的问题：则令：z -f，Min f Max z第27页/共44页ininiibxaxaxa.2211 时，可以引进一个新的变量，使它等于约束右边与左边之差0isiininiibsxaxaxa.2211（2）当约束条件为ininiibxaxaxa.2211类似地令 0isiin
27、iniibsxaxaxa.2211则有：则有：（1）当约束条件为第28页/共44页3.右端项有负值的问题：右端项有负值的问题：0ib则把该等式约束两端同时乘以则把该等式约束两端同时乘以-1，得到：得到：ininiibxaxaxa.2211 为了使约束方程由不等式成为等式而引进的变量为了使约束方程由不等式成为等式而引进的变量,当不等当不等式为式为“小于等于小于等于”时称引进的变量为时称引进的变量为“松弛变量松弛变量”；当不；当不等式为等式为“大于等于大于等于”时称为时称为“剩余变量剩余变量”。如果原问题中。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对有若干个非等式约束，则将其转
28、化为标准形式时，必须对各个约束引进不同的松弛变量或剩余变量。各个约束引进不同的松弛变量或剩余变量。在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如 第29页/共44页4.变量无符号限制的问题变量无符号限制的问题 在标准形式中，必须每一个变量均有非负约束。当某一个变量xj 没有非负约束时，可以令 xj=xj-xj”其中 xj0，xj”0 即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号取决于xj和xj”的大小。总之通过上述问题的处理，线性规划模型的一般形总之通过上述问题的处理，线性规划模型的一般形式均可化为标准形式。式均可化为标准形式。第30页/共44页0,
29、124 202582 52 max212212121xxxxxxxxxz标准化例题10,2504002300.00010050max321213222112132121sssxxsxsxxsxxtssssxxz一般形式标准形式第31页/共44页无符号约束321321321321321,0,5232 7 32 minxxxxxxxxxxxxxxxz0,5 2232 7 332 max54 3321 33215 33214 3321 33211xxxxxxxxxxxxxxxxxxxxxxxxz标准化例题2第32页/共44页jijibac,目标函数中的系数目标函数中的系数的变化只影响目标函数等值线的
30、斜率，只影响目标函数等值线的斜率，不影响可行域。不影响可行域。所谓所谓C的灵敏度分析是指，研究在目标函数中其他的系数的灵敏度分析是指，研究在目标函数中其他的系数不变，只有一个系数在保持最优解不变时该系数的取值范不变，只有一个系数在保持最优解不变时该系数的取值范围。围。1目标函数中的系数“C”的灵敏度分析第33页/共44页一般情况：一般情况：2211xcxcZ21212czxccx可将其写成：目标函数等值线的斜率为：21cc有：(*)0121cc可使原最优解仍是最优解。先假设产品乙的利润100元不变，即：1002c代入（*）并整理得：10001 c2110050 xxZMax考虑例1目标函数为：
31、x1x2x2=0 x1=0 x2=250 x1+x2=3002x1+x2=400图2-1要使最优解不变，其变化必然在构成极点的相交直线的斜率之间。对C1进行灵敏度分析max z=50 x1+100 x2x1+x2 300 2x1 +x2 400 x2 250 x1，x20满足满足第34页/共44页同样：假设同样：假设C1=50不变时，代入不变时，代入：(*)0121cc有有：-1 -（50/C2）0整理后得：整理后得：50 C2+即当即当50 C2+时原最优解不变。时原最优解不变。第35页/共44页2 约束条件中右边系数的灵敏度分析约束条件中右边系数的灵敏度分析 当约束条件中右边系数变化时，线
32、性规划的可行域发生变化，可能引起的最优解的变化，进而了解当其他约束不变时，某一约束条件的右端项每变化一个单位，使目标函数值的改变量。当约束条件中右边系数变化时，线性规划的可行域发生变化，可能引起的最优解的变化，进而了解当其他约束不变时，某一约束条件的右端项每变化一个单位，使目标函数值的改变量。由讲义例1可知：（1）假设设备台时增加10个台时，即变为310台时，这时可行域扩大，但最优解所在的基点不变，得最优解为：X1=60，X2=250 x1x2x2=0 x1=0 x2=250 x1+x2=3102x1+x2=400图2-1第36页/共44页（2）假设原料）假设原料 A 增加增加10 千克时，即
33、千克时，即 变化为变化为410，这时可行域扩大，但最优解仍为，这时可行域扩大，但最优解仍为 和和 约束方程的交点约束方程的交点。此变化对总利润无影响，因此该约束条件的对偶价格为。此变化对总利润无影响，因此该约束条件的对偶价格为 0。由于原最优解没有把原料由于原最优解没有把原料 A 用尽，有用尽，有50千克的剩余，因此增加千克的剩余，因此增加10千克值增加了库存，而不会增加利润。千克值增加了库存，而不会增加利润。这时，即这时，即 变化后的总利润变化后的总利润 变化前的总利润变化前的总利润=增加的利润增加的利润 (5060+100250)(50 50+100 250)=500 元，即：每增加一个台
34、时的利润为：500/10=50 元 说明在一定范围内每增加（减少）1个台时的设备能力就可增加（减少）50元利润，称为该约束条件的对偶价格。称为该约束条件的对偶价格。图2-1x1x2x2=0 x1=0 x2=250 x1+x2=3002x1+x2=410第37页/共44页 在一定范围内，当约束条件右边常数增加在一定范围内，当约束条件右边常数增加1个单位时个单位时 （1）若约束条件的对偶价格大于）若约束条件的对偶价格大于0，则其最优目标函，则其最优目标函数值得到改善（变好）；数值得到改善（变好）；（2）若约束条件的对偶价格小于）若约束条件的对偶价格小于0，则其最优目标函，则其最优目标函数值受到影响
35、（变坏）；数值受到影响（变坏）；（3）若约束条件的对偶价格等于）若约束条件的对偶价格等于0，则最优目标函数，则最优目标函数值不变。值不变。作业布置：作业布置：1、P24 第第3（2，3），第），第4题题2、P25 第第6、7题题第38页/共44页原问题原问题LP模型模型：Max z=50 x1+100 x2 s.t.x1+x2 300 2 x1+x2 400 x2 250 x1,x2 02.4线性规划的对偶问题最优解为：x1=50 x2=250；max Z=27500对偶问题：不妨提出这样的问题，如果该厂把设备（工时）和对偶问题：不妨提出这样的问题，如果该厂把设备（工时）和A A、B B原料原
36、料租赁和转让出去，又要不比自己生产赚的少，该厂如何收取租金和转让租赁和转让出去，又要不比自己生产赚的少，该厂如何收取租金和转让费？或者说设备租赁至少多少钱一个工时，原料费？或者说设备租赁至少多少钱一个工时，原料A A、B B应收多少钱一公斤？应收多少钱一公斤？原问题：例原问题：例2.1 某厂在计划期内安排生产两种产品，某厂在计划期内安排生产两种产品，生产所需资源限生产所需资源限制及单位产品原料消耗由制及单位产品原料消耗由下表给给出下表给给出甲甲乙乙资源限制资源限制设备设备11300台时原料原料A21400kg原料原料B01250kg利润利润50100第39页/共44页定价的原则是：既要能够转让
37、出去，又不比自己生产赚的总利润少。定价的原则是：既要能够转让出去，又不比自己生产赚的总利润少。不妨设：不妨设：y y1 1 ，y y2 2 ，y y3 3 分别为每个设备工时出租和每公斤原料分别为每个设备工时出租和每公斤原料 A A、B B的转让纯利。的转让纯利。对偶问题对偶问题：Min f=300 y1+400y2+250y3s.t.y1+2y2 50 y1+y2+y3 100 y1,y2,y3 0甲甲乙乙资源限制资源限制设备设备11300台时原料原料A21400kg原料原料B01250kg利润利润501001、对偶问题数学模型的建立目标函数目标函数：转让总利润为各种资源租赁和转让利润之和转
38、让总利润为各种资源租赁和转让利润之和f.f.约束条件约束条件1 1：用于生产甲产品的原料利润之和不小于自己生产：用于生产甲产品的原料利润之和不小于自己生产约束条件约束条件2 2：用于生产乙产品的原料利润之和也不小于自己生产：用于生产乙产品的原料利润之和也不小于自己生产即 f=300y1+400y2+250y3 min第40页/共44页第41页/共44页 如果我们把求目标函数最大值的线性规划问题看成原问题，则求目标函数最小大值的线性规划问题看成对偶问题。这两个问题在数学模型上有以下关系。如果我们把求目标函数最大值的线性规划问题看成原问题，则求目标函数最小大值的线性规划问题看成对偶问题。这两个问题
39、在数学模型上有以下关系。mnmmnaaaaaa.2111211mnnnmTaaaaaaA2112111A=则 2 2、对偶问题与原问题数学模型的关系、对偶问题与原问题数学模型的关系4 对偶问题的约束条件的系数矩阵A是原问题约束矩阵的转置。设:3 3 原问题的约束条件的右边常数项为对偶问题的目标函数中的变量的系数。并且原问题的第原问题的约束条件的右边常数项为对偶问题的目标函数中的变量的系数。并且原问题的第i i个约束条件的右边常数项就等于对偶问题的目标函数中的第个约束条件的右边常数项就等于对偶问题的目标函数中的第i i个变量的系数。个变量的系数。2 2 原问题的目标函数中的变量系数为对偶问题中的
40、约束条件的右边常数项，并且原问题的目标函数中的第原问题的目标函数中的变量系数为对偶问题中的约束条件的右边常数项，并且原问题的目标函数中的第i i个变量的系数就等于对偶问题中的第个变量的系数就等于对偶问题中的第i i个约束条件的右边常数项。个约束条件的右边常数项。1 1 求目标函数最大值的线性规划问题中有求目标函数最大值的线性规划问题中有n n 个变量个变量 m m个约束条件，它的约束条件都是小于等于不等式。而其对偶则是求目标函数为最小值的线性规划问题，有个约束条件，它的约束条件都是小于等于不等式。而其对偶则是求目标函数为最小值的线性规划问题，有m m个变量个变量n n个约束条件，其约束条件都为大于等于不等式。个约束条件，其约束条件都为大于等于不等式。第42页/共44页0,maxxbAxcxz0.minycyAybfTTT其中A是 矩阵m*n，该问题有m个约束条件n个变量 对偶问题模型：).,.,(21ncccTmbbb),.,(21Tmyyy),.,(21Tnxxx,21x=b=c=y=：A的转置TATbTC：b的转置,：c的转置,原问题模型第43页/共44页
