线性规划和对偶问题课件.ppt

《线性规划和对偶问题课件.ppt》由会员分享，可在线阅读，更多相关《线性规划和对偶问题课件.ppt（61页珍藏版）》请在三一办公上搜索。

1、线性规划,1、线性规划模型及标准型 如何写出线性规划模型 一般形式转化为标准型2、线性规划的图解法 如何用图解法求解线性规划问题3、线性规划解的有关概念 基变量 非基变量 基本解 基本可行解 最优解4、单纯形法 最大判别原则 最小比值原则 换入换出变量 高斯消元法 最优解的判断等,线性规划的定义和数学描述 1.定义 对于求取一组变量xj (j=1,2,n),使之满足线性约束条件，又使具有线性表达式的目标函数取得极大值或极小值的最优化问题成为线性规划问题，简称线性规划。共同特征： （1）用一组未知变量表示要求的方案，即决策变量（非负条件） （2）存在一定的约束条件，这些约束条件可以用一组线性等式

2、或线性不等式来表示。 （3）都有一个要求达到的目标，它可用决策变量的线性函数（称为目标函数）来表示。按问题的不同，要求目标函数实现最大化或最小化。,例2生产计划问题 某工厂计划期内要安排生产、两种产品，已知生产单位产品所需的设备台时和A、B两种原材料的消耗、以及可获利润如表所示，问应如何安排计划使该工厂获利最多？,设x1、x2 分别表示计划期内两种产品的产量，建立数学模型：,利润最大 目标函数 max z = 2x1+ 3x2,线性规划的标准形式 线性规划标准形式的条件： （1）目标函数约定是极大化Max （2）约束条件均用等式表示 （3）决策变量限于非负值 （4）右端常数均为非负值,将一般形

3、式标准化,将例2的数学模型标准化,标准型,所加松弛变量x3，x4，x5表示没有被利用的资源，当然也没有利润，在目标函数中其系数应为零；即c3 ，c4 ，c5 = 0。,将下述线性规划问题化为标准型 min z = x1 +2x2 3x3,解：,线性规划的图解法 图解法：就是用几何作图的方法分析并求出其最优解的过程。 求解思路：先将约束条件加以约束，求得满足约束条件的解的集合（可行域），然后结合目标函数的要求从可行域中找出最优解。 只有两个决策变量的问题可用图解法。图解法有助于理解线性规划问题的求解原理。 例8：用图解法求解线性规划问题的最优解,x1,x2,0,4,Q2(4,2),Q1,Q3,Q

4、4,4x1=16,4x2=12,x1+2x2=8,3,Q2,4.向着目标函数的优化方向平移等值线，直至得到等值线与可行域的最后交点，这种点就对应最优解。,解 法 ：,线性规划解的概念,2.2.1 线性规划的各种解（1）可行解：满足约束条件(1.2)、(1.3)的解 X=( x1，x2，xn)T（2）最优解：使目标函数（1.1）达到最优值的可行解,基 A中的m m 阶非奇异子矩阵B ；（意味着A的秩为m， |B | 0，B 的各列线性无关）基向量 B中的列向量； 用B表示非基向量 基向量之外的向量； 用N表示基变量 B中的列向量对应的变量； 用XB表示非基变量 非B中的列向量对应的变量； 用XN

5、表示,由定义可知：,若Amn，mn，则至多有 个基，每个基有m个基变量，n- m 个非基变量。,(3)基本解：设AX=b是含n个决策变量，m个约束条件的LP的约束方程组，B是LP问题的一个基，若令不与B的列相应的n-m个分量（非基变量）都等于零，所得的方程组的解称为方程组AX=b关于基B的基本解，简称LP的基本解。,(4)基本可行解：满足非负约束条件（ ）的基本解，简称基可行解。,各种解直接的关系,（2）基本定理 定理1 若线性规划问题存在可行解，则所有可行解的集合可行域D = X| AX= b，X 0 是凸集。 定理2 线性规划问题的基可行解X对应于可行域D的顶点。 定理3 若可行域有界，线

6、性规划问题的目标函数一定可以在顶点上达到最优。 定理4 线性规划问题若存在可行解则必定存在基可行解；若存在最优解则必定存在基最优解。,结论：线性规划问题的可行域是凸集（凸多面体），有有限多个顶点。顶点对应基可行解。当可行域有界时，必有顶点达到目标函数最优值。因此，下面求解线性规划问题就是求其基最优解，当存在无穷多最优解时，若能找出它的所有基最优解，这些基最优解的任一凸组合便表示它的一个最优解。,2.3 单纯形法 2.3.1 单纯形法及其计算步骤 2.3.1.1单纯形法的基本思路 对于一个标准型LP问题，从一个初始基可行解出发，判断其是否为最优解，若是则结束；否则求一个与其“相邻”的、改进的基可

7、行解。再判断这个解是否最优，若是则结束，否则再求一个“相邻”的、改进的基可行解如此迭代下去，直到找到基最优解或判定问题无解为止。,单纯形法的基本思路：顶点的逐步转移，即从可行域的一个顶点（基本可行解）开始，转移到另一个顶点（另一个基本可行解）的迭代过程，转移的条件是使目标函数值得到改善（逐步变优），当目标函数达到最优值时，问题也就得到了最优解。找出一个可行基，并得到一个基本可行解。检验该基本可行解是否是最优解，即目标函数值是否最大，或看看是否存在目标函数比它大的基本可行解。换一个目标函数值比它大的基本可行解。重复以上步骤，直至找不到更好的基本可行解。,单纯形法要解决的三方面的问题：,（1）如何

8、确定初始的基可行解？,（2）如何进行解的最优性判别？,（3）如何寻找改进的基可行解？,2.3.1.2单纯形法的计算步骤,最优性判别定理： 若基可行解对应的检验数 0 ( j=1，2，,n)，则此解是最优解，否则不是最优解。,结论:,计算步骤:,(1).找出初始可行基，确定初始基可行解，建立初始单纯形表。,(2).检验各非基变量xj的检验数，若j 0，j=m+1，n；则已得到最优解，可停止计算，否则转入下一步。,(3).在j 0，j=m+1，n中，若有某个k对应xk的系数列向量Pk 0，则此问题是无界解，停止计算。否则，转入下一步。,(4).根据max(j 0) =k，确定xk为换入变量，按 规

9、则计算,可确定第l行的基变量为换出变量。转入下一步。,2.3.2单纯形表,单纯形表 用表格法求解LP，规范的表格单纯形表如下：,例12 用单纯形法求下列线性规划问题,（1）,( ),2 3 0 0 0,1 2 1 0 0 4 0 0 1 0 0 4 0 0 1,0 2 3 0 0 0,000,81612,x3x4x5,4-3,2 3 0 0 0,2 1 0 1 0 -1/2,- 9 2 0 0 0 -3/4,003,x3x4x2,24-,( ),3 0 1 0 0 1/4,16 4 0 0 1 0,X(0)=(0，0，8，16，12)T， z0 =0,( ),2 3 0 0 0,2 1 0 1

10、 0 -1/2,-13 0 0 -2 0 1/4,203,x1x4x2,-412,3 0 1 0 0 1/4,8 0 0 -4 1 2,2 3 0 0 0,2 1 0 1 0 -1/2,-9 2 0 0 0 -3/4,003,x3x4x2,24-,3 0 1 0 0 1/4,16 4 0 0 1 0,X(1)=(0，3，2，16，0)T， z1 =9,( ),2 3 0 0 0,4 1 0 0 1/4 0,-14 0 0 -1.5 -1/8 0,203,x1x5x2,2 0 1 1/2 -1/8 0,4 0 0 -2 1/2 1,X(2)=(2，3，0，8，0)T， z2 =13,X(3)=(

11、4，2，0，0, 4)T， z3 =14,对偶理论和单纯形法,1、线性规划单纯形法的矩阵描述2、线性规划的对偶问题 对偶问题的提出 对偶问题的性质 影子价格 影子价格的意义3、灵敏度分析 市场 工艺 资源的变化,单纯形表的矩阵形式,例1某工厂计划期内要安排生产、两种产品，已知生产单位产品所需的设备台时和A、B两种原材料的消耗、以及可获利润如表所示，问应如何安排计划使该工厂获利最多？,3.2.1 对偶问题的提出,3.2 线性规划的对偶理论,目标函数 max z = 2x1+ 3x2,问题：假设该工厂的决策者决定不在生产、两种产品，而将其所有资源出租或外售，若有一个企业家有意愿租用或买入所有资源，

12、问该企业家应如何出价，才能使工厂决策者觉得有利可图肯把所以资源出租或售出，并又使自己付出的租金最小？,企业家：付出的代价最小对方能接受 厂 家 ：出让代价应不低于用同等数量的资源自己生产的利润,设出租单位设备台时的租金y1 ，转让原材料A、B的收费为y2， y3。,设备,原材A,y1,y2,原材B,y3,设x1、x2 分别表示计划期内甲乙两种产品的产量，建立数学模型：,资 源,产 品,利润最大 目标函数 Max z = 7x1+ 12x2,Max z = 7x1+ 12x2,若工厂决策者准备将所 有资源出租或转让，问应如何定价？,设转让单位煤、电、油的价格分别为y1 、y2， y3。,3.2.

13、2对偶问题的定义,标准型为：,列向量,行向量,n个变量,n个约束,例2,若原问题的目标函数为最小值，变量变号，约束条件不变号，其他相同。,例3：试求下述线性规划问题的对偶问题,（1）,解：设对偶变量为y1,y2,y3,对偶问题模型为：,解：设对偶变量为y1,y2,y3,对偶问题模型为：,（2）,3.2.3 对偶问题的基本性质,注意：(D)无可行解，(P)不一定为无界解。 此性质还说明：(P)有可行解，(D)不一定有可行解。,4、可行解是最优解时的性质 设 是(P)的可行解， 是(D)的可行解，当 时， 是最优解。,3、无界性,若（P）问题可行，但目标函数无界，则（D）问题不可行。,利用弱对偶定

14、理,5、对偶定理 若（P）有最优解，则（D）也有最优解，且目标函数最优值相等。,6互补松弛定理,例4,的最优解为X*=（0，0，4，4）T试利用互补松弛原理求对偶问题的最优解。,检验数行,(P)的最终单纯形表中松弛变量的检验数对应(D)的最优解。,当某约束条件的右端常数增加一个单位时（假设原问题的最优基不变），原问题的目标函数最优值增加的数量。,+yi*(bi+1),=Y*b+yi*=Z*+yi*,第i种资源的影子价格是第i个约束条件的右端常数增加一个单位时，目标函数增加的数量,3.3 对偶问题的经济解释影子价格,yi为原问题每个分量（约束条件）的影子价格,X(3)=(4，2，0，0, 4)T

15、， z3 =14,经济意义：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。,影子价格,例5,经济意义：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。,在这两个互为对偶的线性规划问题中，生产计划问题的对偶问题是资源定价问题，对偶问题的最优解所代表的是企业在当前面临的资源状况b，技术状况A和市场状况C已知的情况下单位资源对企业的价值。因此，y*代表着当第i个右端常数bi增加一个单位时，最优目标函数值的相应增量。在这两个互为对偶的线性规划问题中，生产计划问题的对偶问题是资源定价问题，对偶问题的最优解所代表是企业在当前面临的资源状况b，技术状况A和市场状况C

16、已知的情况下单位资源对企业的价值。,影子价格的意义,(1)影子价格客观地反映资源在系统内的稀缺程度。如果某一资源在系统内供大于求（即有剩余），其影子价格就为零。如果某一资源是稀缺的（即相应约束条件的剩余变量为零）,则其影子价格必然大零。影子价格越高，资源在系统中越稀缺。(2)影子价格是对系统资源的一种优化估价，只有当系统达到最优时才能赋予该资源这种价值，因此也称最优价格。(3)影子价格的取值与系统状态有关。系统内部资源数量、技术系数和价格的任何变化，都会引起影子价格的变化，它是一种动态价格。(4)如果考虑扩大生产能力，应该从影子价格高的设备入手。,3.4 灵敏度分析 研究线性规划模型某些参数或

17、限制量的变化对最优解的影响及其程度的分析过程称为灵敏度分析。 市场的变化 工艺的变化 资源的变化 两个问题： （1）系数在什么范围内发生变化，最优解不变 （2）系数超过上述范围，用最简便的方法求出新的最优解,3.4.1 资源数量br变化的灵敏度分析,当某一个资源系数br 发生变化，亦即br= br +br，其他系数不变。,B-1(b+b)= B-1b+ B-1b0,B-1b0,例6,X=(4，2，0，0, 4)T， z =14,在保证最优基不变的情况下，求第二个约束条件b2的变化范围,3.4.2 价值系数Cj变化的灵敏度分析,C变化，检验数可能发生变化 要保持最优解不变，必须使所以检验数都小于零，但最优值可能发生变化,在保证最优基不变的情况下，求C2的变化范围,在保证最优基不变的情况下，求C1的变化范围,3.4.3 技术系数aij变化的灵敏度分析,现有一种新产品，每件消耗资源如表所示，问该厂是否生产？,设生产产品为 ，则系数向量为,例7,