2线性规划图解法.ppt

《2线性规划图解法.ppt》由会员分享，可在线阅读，更多相关《2线性规划图解法.ppt（44页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、2.0 线性规划简介线性规划简介 第二章第二章 线性规划及其图解法线性规划及其图解法（Linear Programming，简称，简称LP）本章结合了第五章的一些概念本章结合了第五章的一些概念线性规划是运筹学中研究较早、应用广泛、线性规划是运筹学中研究较早、应用广泛、发展较快、发展较快、方法较成熟的一个重要分支方法较成熟的一个重要分支,是辅助人们进行科学管理是辅助人们进行科学管理的一种数学方法。是研究线性约束条件下线性目标函数的一种数学方法。是研究线性约束条件下线性目标函数的极值问题的数学理论和方法，英文缩写的极值问题的数学理论和方法，英文缩写LP。LP是运筹学的一个重要分支，广泛应用于军事作

2、战、经是运筹学的一个重要分支，广泛应用于军事作战、经济分析、经营管理和工程技术等方面。为合理地利用有济分析、经营管理和工程技术等方面。为合理地利用有限的人力、物力、财力等资源作出的最优决策，提供科限的人力、物力、财力等资源作出的最优决策，提供科学的依据。学的依据。1832和和1911年法国数学家年法国数学家 J.B.J.傅里叶和傅里叶和 C.瓦莱普森瓦莱普森分都分别独立地提出线性规划的想法，但未引起注意。分都分别独立地提出线性规划的想法，但未引起注意。1939年，前苏联数学家康托洛维奇用线性规划模型研究提年，前苏联数学家康托洛维奇用线性规划模型研究提高组织和生产效率问题高组织和生产效率问题 1

3、947年，年，Dantzig提出求解线性规划的单纯形法提出求解线性规划的单纯形法 1950-1956年，主要研究线性规划的对偶理论年，主要研究线性规划的对偶理论 1951年美国经济学家年美国经济学家T.C.库普曼斯把线性规划应用到经济库普曼斯把线性规划应用到经济领域，为此与康托罗维奇一起获领域，为此与康托罗维奇一起获1975年诺贝尔经济学奖。年诺贝尔经济学奖。1958年，发表整数规划的割平面法年，发表整数规划的割平面法 1960年，年，Dantzig和和Wolfe研究成功分解算法，奠定了大研究成功分解算法，奠定了大规模线性规划问题理论和算法的基础。规模线性规划问题理论和算法的基础。一、线性规划

4、发展概况一、线性规划发展概况线性规划的研究成果还直接推动了其他数学规划线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算问题包括整数规划、随机规划和非线性规划的算法研究。由于数字电子计算机的发展，出现了许法研究。由于数字电子计算机的发展，出现了许多线性规划软件，如多线性规划软件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解几千个变量的线等，可以很方便地求解几千个变量的线性规划问题。性规划问题。1979年，年，Khachiyan，1984年，年，Karmarkaa研研究成功线性规划的多项式算法。用卡马卡方法求究成功线性规划的多项式算法。用卡马卡方法

5、求解线性规划问题在变量个数为解线性规划问题在变量个数为5000时只要单纯时只要单纯形法所用时间的形法所用时间的1/50。二、线性规划研究解决的主要问题二、线性规划研究解决的主要问题 实际上，上述两类问题是一个问题的两个不同的方面，都是实际上，上述两类问题是一个问题的两个不同的方面，都是求问题的最优解（求问题的最优解（max 或或 min）。）。另一类是当一项任务确定以后，研究如何统筹安排，才能另一类是当一项任务确定以后，研究如何统筹安排，才能使完成任务所耗费的资源量为最少。使完成任务所耗费的资源量为最少。一类是已有一定数量的资源（人力、物质、时间等），一类是已有一定数量的资源（人力、物质、时间

6、等），研究如何充分合理地使用它们，才能使完成的任务量为研究如何充分合理地使用它们，才能使完成的任务量为最大。最大。线性规划在工商管理中应用有着广泛的用处，可以用来解决诸如：线性规划在工商管理中应用有着广泛的用处，可以用来解决诸如：人力资源分配问题、生产计划问题、下料配料、投资问题（见第人力资源分配问题、生产计划问题、下料配料、投资问题（见第4章）章）以及运输问题（第以及运输问题（第7章）等。实际上远不止这些具体问题。但从一般章）等。实际上远不止这些具体问题。但从一般意义上解决得问题有两类：意义上解决得问题有两类：三、三、LP解决问题的一般思路解决问题的一般思路5、模型求解与解的调适。（获得最优

7、方案、模型求解与解的调适。（获得最优方案一组决策变量的取值）。一组决策变量的取值）。1、对问题进行系统分析、对问题进行系统分析,搞清决策什么和决策目标是什么？搞清决策什么和决策目标是什么？2、明确是哪些因素（人为可控的，决策变量）影响决策目标（大小、明确是哪些因素（人为可控的，决策变量）影响决策目标（大小变化），确定决策变量对目标（函数）影响系数，且与目标函数是否变化），确定决策变量对目标（函数）影响系数，且与目标函数是否呈线形关系。呈线形关系。3、哪些资源约束（或需求约束）条件制约着目标（最大或最小）。决、哪些资源约束（或需求约束）条件制约着目标（最大或最小）。决策变量对这些资源（或需求）的

8、单位消耗（单位产出）是多少？，即策变量对这些资源（或需求）的单位消耗（单位产出）是多少？，即要获得资源总量和投入产出系数。要获得资源总量和投入产出系数。4、建立线形规划数学模型。、建立线形规划数学模型。6、方案实施与调整。、方案实施与调整。2.1 LP问题的提出及其数学模型问题的提出及其数学模型一、例示一、例示问题提出问题提出例例2.1-1 某厂在计划期内安排生产两某厂在计划期内安排生产两种产品，种产品，生产所需资源限制及单位生产所需资源限制及单位产品原料消耗由产品原料消耗由下表给给出下表给给出 利润利润 50 100问：应如何安排生产计划才能使 总利润最大？甲甲乙乙资源限制资源限制设备设备1

9、1300台时原料原料A21400kg原料原料B01250kg解：解：1.确定决策变量：确定决策变量：设产品甲乙的产量分别为设产品甲乙的产量分别为：x1、x22.建立目标函数：建立目标函数：设总利润为设总利润为z，本例是：，本例是：max z=50 x1+100 x23.考虑约束条件考虑约束条件：x1+x2 300 2x1 +x2 400 x2 250 x1，x20目标函数目标函数 ：max z=50 x1+100 x2x1+x2 300 2x1 +x2 400 x2 250 x1，x20满足满足 约束条件：约束条件：4.得到本问题的数学模型：得到本问题的数学模型：例例2.1-2 某厂生产两种产

10、品，下表给某厂生产两种产品，下表给出了单位产品所需资源及单位产品出了单位产品所需资源及单位产品利润利润 问：应如何安排生产计划，才问：应如何安排生产计划，才能使能使 总利润最大？总利润最大？解：解：1.决策变量：设产品决策变量：设产品I、II的产量分的产量分 别为别为 x1、x22.目标函数：设利润为目标函数：设利润为z，则有：，则有：max z=2 x1+3 x23.约束条件：约束条件：x1+2x2 8 4x1 16 4x2 12 x1，x20例例2.1-3 某厂生产三种药物，这些某厂生产三种药物，这些药物可从四种不同的原料中提取。药物可从四种不同的原料中提取。下表给出了单位原料可提取药物的

11、下表给出了单位原料可提取药物的量（有效单位数）量（有效单位数）要求：生产要求：生产A种药物至少种药物至少160单位；单位；B种药物恰好种药物恰好200单位，单位，C种药物不种药物不超过超过180单位，且使原料总成本最单位，且使原料总成本最小。小。解：解：1.决策变量：设四种原料的使用决策变量：设四种原料的使用 量分别为：量分别为：x1、x2、x3、x42.目标函数：设总成本为目标函数：设总成本为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

12、x1、x2、x3、x40 药物原料ABC单位成本（元吨）甲1235乙2016丙1417丁1228二、二、LP问题一般模型问题一般模型1.决策变量：决策变量：X=(x1,x2,.,xn)T2.目标函数：目标函数：max(minz)=c1 x1+c2 x2+.+cnxn3.约束条件：约束条件：a11x1+a12 x2+.+a1n xn(=)b1 a21x1+a22 x2+.+a2n xn(=)b2 am1x1+am2 x2+.+amn xn(=)bm x1,x2,xn0三、三、LP模型特点模型特点1、都用一组决策变量都用一组决策变量X=(x1,x2,xn)T表示某一方案，且决策变量表示某一方案，且

13、决策变量 取值非负；取值非负；满足以上三个条件的数学模型称为线性规划数学模型或满足以上三个条件的数学模型称为线性规划数学模型或LP模型模型2、都有一个要达到的目标，并且目标要求可以表示成决策变量的线、都有一个要达到的目标，并且目标要求可以表示成决策变量的线 性函数性函数；3、都有一组约束条件，这些约束条件可以用决策变量的线性等式或都有一组约束条件，这些约束条件可以用决策变量的线性等式或 线性不等线性不等 式来表示。式来表示。LP模型的其它表达形式模型的其它表达形式简约形式简约形式矩阵形式矩阵形式决策变量决策变量常数项常数项系数矩阵系数矩阵价值系数价值系数其中：其中：四、线性规划数学模型的建立四

14、、线性规划数学模型的建立（一）建模条件（一）建模条件1 优化条件优化条件：问题所要达到的目标能用线型函数描述，且能够用极值：问题所要达到的目标能用线型函数描述，且能够用极值 （max 或或 min）来表示；）来表示；2 限定条件限定条件：达到目标受到一定的限制，且这些限制能够用决策变量的：达到目标受到一定的限制，且这些限制能够用决策变量的 线性等式或线性不等式表示；线性等式或线性不等式表示；3 选择条件选择条件：有多种可选择的方案供决策者选择，以便找出最优方案。：有多种可选择的方案供决策者选择，以便找出最优方案。（二）（二）LP建模步骤建模步骤1 确定决策变量并收集有关参数确定决策变量并收集有

15、关参数：即需要我们作出决策或选择的量。：即需要我们作出决策或选择的量。一般情况下题目问什么，就把什么设置为决策变量。一般情况下题目问什么，就把什么设置为决策变量。2 找列出所有限定条件找列出所有限定条件：即决策变量受到的所有的资源与需求等约束；：即决策变量受到的所有的资源与需求等约束；3 写出目标函数写出目标函数：即问题所要达到的目标，并明确是：即问题所要达到的目标，并明确是max 还是还是 min。（三）建模案例（三）建模案例例例2.1-4 某厂生产某厂生产A、B两种产品，有关参数资料如下表所示，问如何组两种产品，有关参数资料如下表所示，问如何组 织生产才能使效益最大：织生产才能使效益最大：

16、设：总利润为设：总利润为Z；产品；产品A、B产量为产量为x1、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 02.2 2.2 线性规划图解法线性规划图解法一、解题步骤一、解题步骤4 将最优解代入目标函数，求出最优值。将最优解代入目标函数，求出最优值。1 建立坐标系并建立坐标系并在直角平面坐标系中画出所有的约束等式，然后找出满足所在直角平面坐标系中画出所有的约束等式，然后找出满足所有约束条件的公共部分，称为可

17、行域，可行域中的点称为可行解。有约束条件的公共部分，称为可行域，可行域中的点称为可行解。2 标出目标函数值改善的方向标出目标函数值改善的方向。3 画出目标函数等值线，若求最大（小）值，则令目标函数等值线沿目标函画出目标函数等值线，若求最大（小）值，则令目标函数等值线沿目标函数值增加（或减少）的方向平行移动，找与可行域最后相交的点，该点就是数值增加（或减少）的方向平行移动，找与可行域最后相交的点，该点就是最优解最优解。用图解法用图解法求解下列线性规划问题（例求解下列线性规划问题（例1）x1+2x2 8 4x1 16 4x2 12 x1，x20 max z=2 x1+3 x2最优解：X*=(2,4

18、)T最优值：Z*=14目标函数等值线Z=0 x2x1线性规划的图解（例2）max z=x1+3x2s.t.x1+x26-x1+2x28x1 0,x20可行域可行域目标函数等值线目标函数等值线最优解最优解64-860 x1x2目标函数：分别取决策变量为坐标向量建立直角坐标系。在直角分别取决策变量为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一坐标系里，图上任意一点的坐标代表了决策变量的一组值，每个约束条件都代表一个半平面。图示如下：组值，每个约束条件都代表一个半平面。图示如下：用图解法求解下列线性规划问题用图解法求解下列线性规划问题x2x1X20X2=0 x2x1X

19、10X1=0100200300100200300 x1+x2300 x1+x2=3001001002002x1+x24002x1+x2=400300200300400100100 x2250 x2=250200300200300 x1x2x2=0 x1=0 x2=250 x1+x2=3002x1+x2=400图2-1x1x2z=20000=50 x1+100 x2图2-2z=27500=50 x1+100 x2z=0=50 x1+100 x2z=10000=50 x1+100 x2CBADE 综上得到最优解：最优目标值:1、凸集、凸集 若连接若连接n维点集维点集P中任意两点中任意两点x（1），

20、），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的极点。显然多边形的的极点。显然多边形的顶点都是极点，四面体的顶点也都是极点，而顶点都是极点，四面体的顶点也都是极点，而圆周上、球面上的每一个点都是极点，其它点圆周上、球面上的每一个点都是极点，其它点都不是极点。都不是极点。二、关于凸集、极点的概念二、关于凸集、极点的概念三、线性规划解的性质三、线性规划解的性质定

21、理定理1 线性规划的可行域线性规划的可行域 R 是一个凸集，且有有限个极点。是一个凸集，且有有限个极点。定理定理2 X是线性规划可行域是线性规划可行域 R 顶点的充要条件是顶点的充要条件是 X 线性规划的基本可行解。线性规划的基本可行解。定理定理3 若线性规划有最优解，则必有基本最优解。若线性规划有最优解，则必有基本最优解。定理定理4 若线性规划在可行域的两个顶点上达到最优，则在两个顶点的连线若线性规划在可行域的两个顶点上达到最优，则在两个顶点的连线 上也达到最优。上也达到最优。线性规划的每一个基本可行解对应凸集的每一个顶点。若线性规划有最优解，则一定在凸集的某个（些）顶点上达到最优。若线性规

22、划有最优解，则一定在凸集的某个（些）顶点上达到最优。若线性规划在两个顶点以上达到最优若线性规划在两个顶点以上达到最优,则一定有无穷多个最优解。则一定有无穷多个最优解。最优解一定是基本可行解，但基本可行解不一定是最优解。最优解一定是基本可行解，但基本可行解不一定是最优解。四、线性规划问题求解可能出现的情况四、线性规划问题求解可能出现的情况x1x2z=20000=50 x1+100 x2图2-2z=27500=50 x1+100 x2z=0=50 x1+100 x2z=10000=50 x1+100 x2CBADE则可行域为空域，不存在满足约束条件的解，当然也就不存在最优解了。则可行域为空域，不存

23、在满足约束条件的解，当然也就不存在最优解了。4、无可行解。如果例、无可行解。如果例3再增加一个约束条件再增加一个约束条件3、无界解。即可行域延伸到无穷远，目标函数值可以无穷大或无穷小。、无界解。即可行域延伸到无穷远，目标函数值可以无穷大或无穷小。2、如果最优解出现在两个极点上，则会有无穷多个最优解。、如果最优解出现在两个极点上，则会有无穷多个最优解。1、如果、如果LP有最优解，则一定有一个可行域的极点对应这个最优解；有最优解，则一定有一个可行域的极点对应这个最优解；五、五、LPLP解的有关概念及其关系解的有关概念及其关系1 可行解（可行解（feasible solution）：满足线性规划约束

24、条件的解称为可行解。：满足线性规划约束条件的解称为可行解。（一）有关概念（一）有关概念2 最优解（最优解（optimal solution）：使线性规划目标函数达到最优的可行解称为：使线性规划目标函数达到最优的可行解称为 最优解。最优解。3 基本解（基本解（basic solution）：以线性规划约束等式的系数矩阵：以线性规划约束等式的系数矩阵A中任意中任意m行行m 列组成的列组成的mm满秩子矩阵为基矩阵，与基矩阵相对应的变量称为基变量满秩子矩阵为基矩阵，与基矩阵相对应的变量称为基变量（basic variable），其余变量称为非基变量，若令非基变量为零，则可求），其余变量称为非基变量，若

25、令非基变量为零，则可求得基变量的解（值），这个解称为基本解。得基变量的解（值），这个解称为基本解。4 基本可行解（基本可行解（basic feasible solution）：满足非负约束的基本解称为基本可行解。满足非负约束的基本解称为基本可行解。若约束等式中有n个变量，m个约束，则基本解的个数令非基变量 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解：解：系数矩阵为：设基变量为x

26、3、x4，则非基变量为x1、x23）X (1/2,1/2,3/2,1/2)T不是基本解可行解是基本可行解？例例 讨论下述约束方程的解1 可行解与最优解：可行解与最优解：最优解一定是可行解，但可行解不一定是最优解。最优解一定是可行解，但可行解不一定是最优解。（二）线性规划解之间的关系（二）线性规划解之间的关系基本解不一定是可行解，可行解也不一定是基本解。基本解不一定是可行解，可行解也不一定是基本解。2 可行解与基本解：可行解与基本解：3 可行解与基本可行解：可行解与基本可行解：基本可行解一定是可行解，但可行解不一定是基本解。基本可行解一定是可行解，但可行解不一定是基本解。基本可行解一定是基本解，

27、基本可行解一定是基本解，但基本解不一定是基本可行解。但基本解不一定是基本可行解。4 基本解与基本可行解：基本解与基本可行解：5 最优解与基本解：最优解与基本解：最优解不一定是基本解，最优解不一定是基本解，基本解也不一定是最优解。基本解也不一定是最优解。问题：最优解与基本可行解？非可行解可行解基本可行解基本解六、线性规划模型的标准形式及其标准化六、线性规划模型的标准形式及其标准化（一）线性规划模型标准形式特点（一）线性规划模型标准形式特点 1目标最大化；目标最大化；2约束为等式；约束为等式；3决策变量均非负；决策变量均非负；4右端项非负。右端项非负。特点特点Max z=c1x1+c2x2+cnx

28、na11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2 .am1x1+am2x2+amnxn=bm x1，x2，xn 0s.t 如果目标函数为 Min该极小化问题与下面的极大化问题有相同的最优解，但必须注意，尽管以上两个问题的最优解相同，但它们最优解的目标函数值却相差一个符号，即：（二）线性规划模型标准化问题（二）线性规划模型标准化问题1、极小化目标函数的问题、极小化目标函数的问题：则令：z -f，Min f Max z2、约束条件不是等式的问题：时，可以引进一个新的变量，使它等于约束右边与左边之差（2）当约束条件为类似地令 则有：则有：（1）当约束条件为3.右端项

29、有负值的问题：右端项有负值的问题：则把该等式约束两端同时乘以则把该等式约束两端同时乘以-1，得到：得到：为了使约束方程由不等式成为等式而引进的变量为了使约束方程由不等式成为等式而引进的变量,当不等当不等式为式为“小于等于小于等于”时称引进的变量为时称引进的变量为“松弛变量松弛变量”；当不；当不等式为等式为“大于等于大于等于”时称为时称为“剩余变量剩余变量”。如果原问题中。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量或剩余变量。各个约束引进不同的松弛变量或剩余变量。在标准形式中，要求右端项必须每一个分量

30、非负。当某一个右端项系数为负时，如在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如 4.变量无符号限制的问题变量无符号限制的问题 在标准形式中，必须每一个变量均有非负约束。当某一个变量xj 没有非负约束时，可以令 xj=xj-xj”其中 xj0，xj”0 即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号取决于xj和xj”的大小。总之通过上述问题的处理，线性规划模型的一般形总之通过上述问题的处理，线性规划模型的一般形式均可化为标准形式。式均可化为标准形式。标准化例题1一般形式标准形式标准化例题22.3灵敏度分析灵敏度分析 灵敏度分析是建立数学模型和求得最优解

31、后，研究灵敏度分析是建立数学模型和求得最优解后，研究线性规划的一个或多个参数线性规划的一个或多个参数 ()变化变化时，对最优解产生的影响时，对最优解产生的影响，或者这些参数在或者这些参数在 一个多一个多大范围内变化时，原大范围内变化时，原LP问题的最优解不变的问题。问题的最优解不变的问题。目标函数中的系数目标函数中的系数的变化只影响目标函数等值线的斜率，只影响目标函数等值线的斜率，不影响可行域。不影响可行域。所谓所谓C的灵敏度分析是指，研究在目标函数中其他的系数的灵敏度分析是指，研究在目标函数中其他的系数不变，只有一个系数在保持最优解不变时该系数的取值范不变，只有一个系数在保持最优解不变时该系

32、数的取值范围。围。1目标函数中的系数目标函数中的系数“C”的灵敏度分析的灵敏度分析一般情况：一般情况：可将其写成：目标函数等值线的斜率为：有：可使原最优解仍是最优解。先假设产品乙的利润100元不变，即：代入（*）并整理得：考虑例1目标函数为：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满足满足同样：假设同样：假设C1=50不变时，代入不变时，代入：有有：-1 -（50/

33、C2）0整理后得：整理后得：50 C2+即当即当50 C2+时原最优解不变。时原最优解不变。2 约束条件中右边系数的灵敏度分析约束条件中右边系数的灵敏度分析 当约束条件中右边系数变化时，线性规划的可行域发生变化，可能引当约束条件中右边系数变化时，线性规划的可行域发生变化，可能引起的最优解的变化，进而了解当其他约束不变时，某一约束条件的右端项起的最优解的变化，进而了解当其他约束不变时，某一约束条件的右端项每变化一个单位，使目标函数值的改变量。每变化一个单位，使目标函数值的改变量。由讲义例1可知：（1）假设设备台时增加10个台时，即变为310台时，这时可行域扩大，但最优解所在的基点不变，得最优解为

34、：X1=60，X2=250 x1x2x2=0 x1=0 x2=250 x1+x2=3102x1+x2=400图2-1（2）假设原料）假设原料 A 增加增加10 千克时，即千克时，即 变化为变化为410，这时可行域扩大，但最，这时可行域扩大，但最优解仍为优解仍为 和和 约束方程的交点约束方程的交点。此变化对总利润无影响，因此该约束。此变化对总利润无影响，因此该约束条件的对偶价格为条件的对偶价格为 0。由于原最优解没有把原料由于原最优解没有把原料 A 用尽，有用尽，有50千克的剩余，因此增加千克的剩余，因此增加10千克值增千克值增加了库存，而不会增加利润。加了库存，而不会增加利润。这时，即这时，即

35、 变化后的总利润变化后的总利润 变化前的总利润变化前的总利润=增加的利润增加的利润 (5060+100250)(50 50+100 250)=500 元，即：每增加一个台时的利润为：500/10=50 元 说明在一定范围内每增加（减少）1个台时的设备能力就可增加（减少）50元利润，称为该约束条件的对偶价格。称为该约束条件的对偶价格。图2-1x1x2x2=0 x1=0 x2=250 x1+x2=3002x1+x2=410 在一定范围内，当约束条件右边常数增加在一定范围内，当约束条件右边常数增加1个单位时个单位时 （1）若约束条件的对偶价格大于）若约束条件的对偶价格大于0，则其最优目标函数，则其最

36、优目标函数值得到改善（变好）；值得到改善（变好）；（2）若约束条件的对偶价格小于）若约束条件的对偶价格小于0，则其最优目标函数，则其最优目标函数值受到影响（变坏）；值受到影响（变坏）；（3）若约束条件的对偶价格等于）若约束条件的对偶价格等于0，则最优目标函数值，则最优目标函数值不变。不变。作业布置：作业布置：1、P24 第第3（2，3），第），第4题题2、P25 第第6、7题题原问题原问题LP模型模型：Max z=50 x1+100 x2 s.t.x1+x2 300 2 x1+x2 400 x2 250 x1,x2 02.42.4线性规划的对偶问题线性规划的对偶问题最优解为：x x1 1=50

37、 x=50 x2 2=250=250；max Z=27500对偶问题：不妨提出这样的问题，如果该厂把设备（工时）和对偶问题：不妨提出这样的问题，如果该厂把设备（工时）和A A、B B原料租原料租赁和转让出去，又要不比自己生产赚的少，该厂如何收取租金和转让费？赁和转让出去，又要不比自己生产赚的少，该厂如何收取租金和转让费？或者说设备租赁至少多少钱一个工时，原料或者说设备租赁至少多少钱一个工时，原料A A、B B应收多少钱一公斤？应收多少钱一公斤？原问题：例原问题：例2.1 某厂在计划期内安排生产两种产品，某厂在计划期内安排生产两种产品，生产所需资源限制生产所需资源限制及单位产品原料消耗由及单位产

38、品原料消耗由下表给给出下表给给出甲甲乙乙资源限制资源限制设备设备11300台时原料原料A21400kg原料原料B01250kg利润利润50100定价的原则是：既要能够转让出去，又不比自己生产赚的总利润少。定价的原则是：既要能够转让出去，又不比自己生产赚的总利润少。不妨设：不妨设：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甲甲乙乙资源限制资源限制设

39、备设备11300台时原料原料A21400kg原料原料B01250kg利润利润501001 1、对偶问题数学模型的建立、对偶问题数学模型的建立目标函数目标函数：转让总利润为各种资源租赁和转让利润之和转让总利润为各种资源租赁和转让利润之和f.f.约束条件约束条件1 1：用于生产甲产品的原料利润之和不小于自己生产：用于生产甲产品的原料利润之和不小于自己生产约束条件约束条件2 2：用于生产乙产品的原料利润之和也不小于自己生产：用于生产乙产品的原料利润之和也不小于自己生产即 f=300y1+400y2+250y3 min 对偶问题最优解：对偶问题最优解：y1=50 y2=0 y3 =50 minf=27

40、500（P114）即两种决策结果相同，这样一对互为对偶的LP问题无论是外在还是内在都有密切的关系。见113。如果我们把求目标函数最大值的线性规划问题看成原问题，则求目标函数最小大如果我们把求目标函数最大值的线性规划问题看成原问题，则求目标函数最小大值的线性规划问题看成对偶问题。这两个问题在数学模型上有以下关系。值的线性规划问题看成对偶问题。这两个问题在数学模型上有以下关系。A=则 2 2、对偶问题与原问题数学模型的关系、对偶问题与原问题数学模型的关系4 4 对偶问题的约束条件的系数矩阵对偶问题的约束条件的系数矩阵A A是原问题约束矩阵的转置。是原问题约束矩阵的转置。设设:3 3 原问题的约束条

41、件的右边常数项为对偶问题的目标函数中的变量的系数。并且原问题的约束条件的右边常数项为对偶问题的目标函数中的变量的系数。并且原问题的第原问题的第i i个约束条件的右边常数项就等于对偶问题的目标函数中的第个约束条件的右边常数项就等于对偶问题的目标函数中的第i i个变量个变量的系数。的系数。2 2 原问题的目标函数中的变量系数为对偶问题中的约束条件的右边常数项，并且原问题的目标函数中的变量系数为对偶问题中的约束条件的右边常数项，并且原问题的目标函数中的第原问题的目标函数中的第i i个变量的系数就等于对偶问题中的第个变量的系数就等于对偶问题中的第i i个约束条件的右个约束条件的右边常数项。边常数项。1 1 求目标函数最大值的线性规划问题中有求目标函数最大值的线性规划问题中有n n 个变量个变量 m m个约束条件，它的约束条个约束条件，它的约束条件都是小于等于不等式。而其对偶则是求目标函数为最小值的线性规划问题，件都是小于等于不等式。而其对偶则是求目标函数为最小值的线性规划问题，有有m m个变量个变量n n个约束条件，其约束条件都为大于等于不等式。个约束条件，其约束条件都为大于等于不等式。其中其中A A是是 矩阵矩阵m m*n n，该问题有，该问题有m m个约束条件个约束条件n n个变量个变量 对偶问题模型：x=b=c=y=：A的转置：b的转置,：c的转置,原问题模型