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

1、线性规划线性规划1 1、线性规划模型及标准型、线性规划模型及标准型 如何写出线性规划模型如何写出线性规划模型 一般形式转化为标准型一般形式转化为标准型2 2、线性规划的图解法、线性规划的图解法 如何用图解法求解线性规划问题如何用图解法求解线性规划问题3 3、线性规划解的有关概念、线性规划解的有关概念 基变量基变量 非基变量非基变量 基本解基本解 基本可行解基本可行解 最优解最优解4 4、单纯形法、单纯形法 最大判别原则最大判别原则 最小比值原则最小比值原则 换入换出变量换入换出变量 高斯消元法高斯消元法 最优解的判最优解的判断等断等线性规划的定义和数学描述线性规划的定义和数学描述 1.1.定义

2、定义 对于求取一组变量对于求取一组变量xj (j=1,2,n),使之满足线性约束条件，又使具有线使之满足线性约束条件，又使具有线性表达式的目标函数取得极大值或极小值的最优化问题成为线性规划问题，性表达式的目标函数取得极大值或极小值的最优化问题成为线性规划问题，简称线性规划。简称线性规划。共同特征：共同特征：（1）用一组未知变量表示要求的方案，即决策变量（）用一组未知变量表示要求的方案，即决策变量（非负条件非负条件）（2）存在一定的存在一定的约束条件约束条件，这些约束条件可以用一组线性等式或线性不等式来，这些约束条件可以用一组线性等式或线性不等式来表示。表示。（3 3）都有一个要求达到的目标，它

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

4、 线性规划标准形式的条件：线性规划标准形式的条件：（1 1）目标函数约定是极大化）目标函数约定是极大化MaxMax （2 2）约束条件均用等式表示）约束条件均用等式表示 （3 3）决策变量限于非负值）决策变量限于非负值 （4 4）右端常数均为非负值）右端常数均为非负值 将将负负约约束束、无无符符号号约约束束变变量量变变为为非非负负约约束束变变量量 xj 0 xj=-xj ，xj 0 xj 为为无无符符号号约约束束变变量量 xj=xj -xj ,xj 0,xj 0 将一般形式标准化将一般形式标准化将例2的数学模型标准化 12121212232841 641 2,0M a xxxxxxxxx标准型

5、标准型123451231425123452300028416412,0Maxxxxxxxxxxxxxx x x xx 所加松弛变量x3，x4，x5表示没有被利用的资源，当然也没有利润，在目标函数中其系数应为零；即c3，c4，c5=0。将下述线性规划问题化为标准型将下述线性规划问题化为标准型 min z=x1+2x2 3x3解：解：123123123123 .xxxxxxstxxxxxx723250，为无符号约束1233451233412335123312334523()00 ()().()5,0MaxZxxxxxxxxxxxxxxxxstxxxxxx xxxx7232，线性规划的图解法线性规划

6、的图解法 图解法：就是用几何作图的方法分析并求出其最优解的过程。图解法：就是用几何作图的方法分析并求出其最优解的过程。求解思路：先将约束条件加以约束，求得满足约束条件的解的集合（可行域），求解思路：先将约束条件加以约束，求得满足约束条件的解的集合（可行域），然后结合目标函数的要求从可行域中找出最优解。然后结合目标函数的要求从可行域中找出最优解。只有两个决策变量的问题可用图解法。图解法有助于理解线性规划问题的只有两个决策变量的问题可用图解法。图解法有助于理解线性规划问题的求解原理。求解原理。例例8 8：用图解法求解线性规划问题的最优解用图解法求解线性规划问题的最优解 12121212232841

7、6.412,0Maxxxxxxstxx xx1x204Q2(4,2)Q1Q3Q44x1=164x2=12 x1+2x2=82x1+3x2=03Q24.向着目标函数的优化方向平移等值线，直至得到等值线与可行域的最后交点，这种点就对应最优解。12121212Z2328416.412,0Maxxxxxxstxx x124,214xxZ线性规划解的概念 11(1.1)1,2,(1.2).0(1.3)01,2,njjjnijjijjMaxZc xMaxZCXa xbimAXbststXxjn2.2.1 线性规划的各种解（1）可行解：满足约束条件(1.2)、(1.3)的解 X=(x1，x2，xn)T（2）

8、最优解：使目标函数（1.1）达到最优值的可行解 1112111121222212121121mmnmmnmmnmmmmmmmnaaaaaaaaaaApppppaaaaa 基 A中的m m 阶非奇异子矩阵B；（意味着A的秩为m，|B|0，B 的各列线性无关）基向量 B中的列向量；用B表示 非基向量 基向量之外的向量；用N表示 基变量 B中的列向量对应的变量；用XB表示 非基变量 非B中的列向量对应的变量；用XN表示1 1221111 112211111121 12222211221 1221112.,0mmmmnnmmmmnnmmmmnnmmmmmmmmmnnmnMaxZc xc xc xcxc

9、 xa xa xa xaxa xba xa xaxaxa xbsta xaxaxaxaxbx xx.0MaxZCXAXbstX 由定义可知：若若Amn，m 0，j=m+1，n中，若有某个k对应xk的系数列向量Pk 0，则此问题是无界解，停止计算。否则，转入下一步。(4).根据max(max(j 0)=k，确定xk为换入变量，按 规则计算可确定第l行的基变量为换出变量。转入下一步。min0ilkikiklkbbxaaa2.3.2单纯形表单纯形表单纯形表 用表格法求解LP，规范的表格单纯形表如下：例12 用单纯形法求下列线性规划问题12121212232841 641 2,0M a xxxxxxx

10、xx123451231425123452300028416412,0Maxxxxxxxxxxxxxx x x xx（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 000081612x3x4x54-3 2 3 0 0 0 2 1 0 1 0 -1/2-9 2 0 0 0 -3/4003x3x4x224-()3 0 1 0 0 1/4 16 4 0 0 1 0X(0)(0)=(0=(0，0 0，8 8，1616，12)12)T T，z z0 0=0=0()cjCB XBbx1x2x3x4x5-z 2 3 0 0 0 2 1 0 1 0

11、-1/2-13 0 0 -2 0 1/4203x1x4x2-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/4003x3x4x224-3 0 1 0 0 1/4 16 4 0 0 1 0 X X(1)(1)=(0=(0，3 3，2 2，1616，0)0)T T，z z1 1=9=9()2 3 0 0 0 2 1 0 1 0 -1/2-13 0 0 -2 0 1/4203x1x4x2-412 3 0 1 0 0 1/4 8 0 0 -4 1 2()cjCB XBbx1x2x3x4x5-z 2 3 0 0 0

12、 4 1 0 0 1/4 0-14 0 0 -1.5 -1/8 0203x1x5x2 2 0 1 1/2 -1/8 0 4 0 0 -2 1/2 1 X X(2)(2)=(2=(2，3 3，0 0，8 8，0)0)T T，z z2 2=13=13 X X(3)(3)=(4=(4，2 2，0 0，0,4)0,4)T T，z z3 3=14=14对偶理论和单纯形法对偶理论和单纯形法1 1、线性规划单纯形法的矩阵描述、线性规划单纯形法的矩阵描述2 2、线性规划的对偶问题、线性规划的对偶问题 对偶问题的提出对偶问题的提出 对偶问题的性质对偶问题的性质 影子价格影子价格 影子价格的影子价格的意义意义3

13、3、灵敏度分析、灵敏度分析 市场市场 工艺工艺 资源的变化资源的变化基变量基变量非基变量非基变量常数项常数项 XBXNXS系数矩阵系数矩阵检验数检验数I0B-1 NCN-CBB-1NB-1-CBB-1B-1b-CBB-1b单纯形表的矩阵形式单纯形表的矩阵形式 例1某工厂计划期内要安排生产、两种产品，已知生产单位产品所需的设备台时和A、B两种原材料的消耗、以及可获利润如表所示，问应如何安排计划使该工厂获利最多？3.2.1 对偶问题的提出3.2 3.2 线性规划的对偶理论线性规划的对偶理论目标函数 max z=2x1+3x212121228416412,0 xxxxxx 问题：问题：假设该工厂的决

14、策者决定不在生产假设该工厂的决策者决定不在生产、两种产品，两种产品，而将其所有资源出租或外售，若有一个企业家有意愿租用或买而将其所有资源出租或外售，若有一个企业家有意愿租用或买入所有资源，问该企业家应如何出价，才能使工厂决策者觉得入所有资源，问该企业家应如何出价，才能使工厂决策者觉得有利可图肯把所以资源出租或售出，并又使自己付出的租金最有利可图肯把所以资源出租或售出，并又使自己付出的租金最小？小？企业家企业家：付出的代价最小对方能接受付出的代价最小对方能接受 厂厂 家家：出让代价应不低于用同等数量的资源自己生产的利出让代价应不低于用同等数量的资源自己生产的利润润设出租单位设备台时的租金设出租单

15、位设备台时的租金y y1 1，转让转让原材料原材料A A、B B的收费为的收费为y2，y3。Max Z=2x1+3x2 x1+2x28 4x1 16 4x2 12 x1，x20若工厂决策者准备将所有若工厂决策者准备将所有资源出租或转让，问应如资源出租或转让，问应如何定价？何定价？设备设备原材原材Ay1y2原材原材By3 设x1、x2 分别表示计划期内甲乙两种产品的产量，建立数学模型：甲 乙 资源限制 煤（t）9 4 360 电（kw.h）4 5 200 油（t）3 10 300 单位价格（万元）利润 7 12？资 源 产 品1212121294360()45200().310300(),0 x

16、xxxs txxxx煤 资 源 约 束电 资 源 约 束油 资 源 约 束非 负 约 束利润最大利润最大 目标函数目标函数 Max Max z z=7=7x1+12+12x2 甲 乙 资源限制 煤（t）9 4 360 电（kw.h）4 5 200 油（t）3 10 300 单位价格（万元）利润 7 12？Max z=7x1+12x2121212129436045200.310300,0 xxxxstxxx x若工厂决策者准备将所若工厂决策者准备将所 有资源出租或转让，问有资源出租或转让，问应如何定价？应如何定价？设转让单位煤、电、油的价格分别为设转让单位煤、电、油的价格分别为y y1 1、y2

17、，y3。3.2.2对偶问题的定义对偶问题的定义 0XbAX.t.sCXzmax 0ssXXbXAX.t.sCXzmax，标准型为：标准型为：（P）0 21121112112211 nmnmnm2m1nnnx,x,xbbxxxaaaaaaxcxcxczMax （D）0 212111211212211 mnmnm2m1nmmmy,y,y)c,c,c(aaaaaa)y,y,y(bybybymin 互为转置互为转置列向量列向量行向量行向量n个变量个变量n个约束个约束 0,34224.12168min3213121321yyyyyyytsyyy 0,12416 482 32max21322112121x

18、xyxyxyxxxxz 0,50246032 .6080min21212121yyyyyytsyy例2 若原问题的目标函数为最小值，变量变号，约束条件不变号，其他相同。若原问题的目标函数为最小值，变量变号，约束条件不变号，其他相同。例例3 3：试求下述线性规划问题的对偶问题1231231231231235322134102250,0,Max Zxxxxxxxxxxxxxxx无约束（1）解：设对偶变量为y1,y2,y3,对偶问题模型为：123123123123123in1052252321430,0,Mwyyyyyyyyyyyyyyy 无约束解：设对偶变量为解：设对偶变量为y1,y2,y3,对偶

19、问题模型为对偶问题模型为：（2）123121312312312354622332510,0,MaxWyyyyyyyyyyyyyyyy 无约束3.2.3 3.2.3 对偶问题的基本性质对偶问题的基本性质注意：注意：(D)无可行解，无可行解，(P)不一定为无界解。不一定为无界解。此性质还说明：此性质还说明：(P)有可行解，有可行解，(D)不一定有可行解。不一定有可行解。4、可行解是最优解时的性质可行解是最优解时的性质 设设 是是(P)的可行解，的可行解，是是(D)的可行解，当的可行解，当 时，时，是最优解。是最优解。X Y bYXC YX ,3 3、无界性、无界性 若若（P）问题可行，但目标函数无

20、界，则问题可行，但目标函数无界，则（D）问题不可行问题不可行。（D）不可行）不可行（P）无界）无界 （P）不可行）不可行利用弱对偶定理利用弱对偶定理 5、对偶定理、对偶定理 若（若（P）有最优解，则（）有最优解，则（D）也有最优解，且目）也有最优解，且目标函数最优值相等。标函数最优值相等。6 6互补松弛定理互补松弛定理*jXYXYPD()01,2,()01,2,iiijjy ba XimY pcxjn若和分别是原问题和对偶问题的可行解，则和分别是（）和（）的最优解的充要条件是方程组成立。*j*j(1)0=(2)=0(3)0=(4)=0iiiijjjjya Xba XbyxY pcY pcx若有

21、某个，则必有若有某个，则必有若有某个，则必有若有某个，则必有例例4 44321422maxxxxxz1234123412341234223 20 23 220 1 ,0 xxxxxxxxxxxxx x x x的最优解为X*=（0，0，4，4）T试利用互补松弛原理求对偶问题的最优解。123123123123123 y21 2 y2 2 y33 3 y24 y,0yyyyyyyyyy3212020minyyyw320=2020=20001y232314132y3y244334yxyxyy126515yy61Y(,0)55所以最优解X XS C-CBB-1A-CBB-1-YS-Y 检验数行检验数行(

22、P)(P)的最终单纯形表中松弛变量的检验数对应的最终单纯形表中松弛变量的检验数对应(D)(D)的最优解。的最优解。当某约束条件的右端常数增加一个单位时（假设原问题的当某约束条件的右端常数增加一个单位时（假设原问题的最优基不变），原问题的目标函数最优值增加的数量。最优基不变），原问题的目标函数最优值增加的数量。Z*=CX*=Y*b =(y1*,y2*,ym*)b1b2bm=y1*b1+y2*b2+ym*bm当某个右端常数当某个右端常数bi bi+1时时bi+1yi*+yi*(bi+1)=Y*b+yi*=Z*+yi*第第i i种资源的影子种资源的影子价格是第价格是第i i个约束个约束条件的右端常数

23、增条件的右端常数增加一个单位时，目加一个单位时，目标函数增加的数量标函数增加的数量3.3 3.3 对偶问题的经济解释对偶问题的经济解释影子价格影子价格y yi i为原问题每个分量（约束条件）的影子价格为原问题每个分量（约束条件）的影子价格 X X(3)(3)=(4=(4，2 2，0 0，0,4)0,4)T T，z z3 3=14=14cj23000CBXBbx1x2 x3x4x5203x1x5x24421000010-21/21/4-1/8010-1400-3/2-1/800125051321 *,.,.yyy经济意义：经济意义：在其它条件在其它条件不变的情况不变的情况下，下，单位资源变单位资

24、源变化所引起的化所引起的目标函数的目标函数的最优值的变最优值的变化。化。影子价格影子价格例例5 5 甲 乙 资源限制 煤（t）9 4 360 电（kw.h）4 5 200 油（t）3 10 300 单位价格（万元）利润 7 12？*1230,1.36,0.52yyy经济意义：经济意义：在其它条件不变的情况下，在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值单位资源变化所引起的目标函数的最优值的变化。的变化。cj23000CBXBbx1x2 x3x4x50712x3x1x2842024010001100-3.120.4-0.121.16-0.20.16-Z000-1.36-0.52

25、在这两个互为对偶的线性规划问题中，生产计划问题的在这两个互为对偶的线性规划问题中，生产计划问题的对偶问题是资源定价问题，对偶问题的最优解所代表的对偶问题是资源定价问题，对偶问题的最优解所代表的是企业在当前面临的资源状况是企业在当前面临的资源状况b b，技术状况，技术状况A A和市场状况和市场状况C C已知的情况下单位资源对企业的价值。已知的情况下单位资源对企业的价值。因此，因此，y y*代表着当第代表着当第i i个右端常数个右端常数b bi i增加一个单位时，最增加一个单位时，最优目标函数值的相应增量。在这两个互为对偶的线性规优目标函数值的相应增量。在这两个互为对偶的线性规划问题中，生产计划问

26、题的对偶问题是资源定价问题，划问题中，生产计划问题的对偶问题是资源定价问题，对偶问题的最优解所代表是企业在当前面临的资源状况对偶问题的最优解所代表是企业在当前面临的资源状况b b，技术状况技术状况A A和市场状况和市场状况C C已知的情况下单位资源对企业的已知的情况下单位资源对企业的价值。价值。影子价格的意义影子价格的意义(1)(1)影子价格客观地反映资源在系统内的稀缺程度。影子价格客观地反映资源在系统内的稀缺程度。如果某一资源在系统内供大于求（即有剩余），其影子价格就为零。如果某如果某一资源在系统内供大于求（即有剩余），其影子价格就为零。如果某一资源是稀缺的（即相应约束条件的剩余变量为零）一

27、资源是稀缺的（即相应约束条件的剩余变量为零）,则其影子价格必然大零。则其影子价格必然大零。影子价格越高，资源在系统中越稀缺。影子价格越高，资源在系统中越稀缺。(2)(2)影子价格是对系统资源的一种优化估价，只有当系统达到最优时才能赋予影子价格是对系统资源的一种优化估价，只有当系统达到最优时才能赋予该资源这种价值，因此也称最优价格。该资源这种价值，因此也称最优价格。(3)(3)影子价格的取值与系统状态有关。系统内部资源数量、技术系数和价格的影子价格的取值与系统状态有关。系统内部资源数量、技术系数和价格的任何变化，都会引起影子价格的变化，它是一种动态价格。任何变化，都会引起影子价格的变化，它是一种

28、动态价格。(4)(4)如果考虑扩大生产能力，应该从影子价格高的设备入手。如果考虑扩大生产能力，应该从影子价格高的设备入手。3.4 3.4 灵敏度分析灵敏度分析 研究线性规划模型某些参数或限制量的变化对最优解的影响及其程度研究线性规划模型某些参数或限制量的变化对最优解的影响及其程度的分析过程称为灵敏度分析。的分析过程称为灵敏度分析。市场的变化市场的变化 工艺的变化工艺的变化 资源的变化资源的变化 两个问题：两个问题：（1 1）系数在什么范围内发生变化，最优解不变）系数在什么范围内发生变化，最优解不变 （2 2）系数超过上述范围，用最简便的方法求出新的最优解）系数超过上述范围，用最简便的方法求出新

29、的最优解ijaibjc3.4.1 3.4.1 资源数量资源数量br变化的灵敏度分析变化的灵敏度分析当某一个资源系数br 发生变化，亦即br=br+br，其他系数不变。基变量基变量非基变量非基变量常数项常数项 XBXNXS系数矩阵系数矩阵检验数检验数I0B-1 NCN-CBB-1NB-1-CBB-1B-1b-CBB-1bB-1(b+b)=B-1b+B-1b0B-1b0cj23000CBXBbx1x2 x3x4x5203x1x5x24421000010-21/21/41/2-1/8010-1400-3/2-1/80例例6 6 X X=(4=(4，2 2，0 0，0,4)0,4)T T，z z=14

30、=14在保证最优基不变的情况下，求第二个约束条件在保证最优基不变的情况下，求第二个约束条件b b2 2的变化范围的变化范围cj23000CBXBbx1x2 x3x4x5203x1x5x24421000010-21/21/41/2-1/8010-1400-3/2-1/80122211222200.25000.2520.510.50.50.125000.12540.2540.5020.125816832BbbbB bBbbbb cj712000CBXBbx1x2 x3x4x50712x3x1x2842024010001100-3.120.4-0.121.16-0.20.16-Z000-1.36-0

31、.52122211222213.121.1603.1200.40.20.400.120.1600.123603.122000.403000.125027150227BbbbB bBbbbb 3.4.2 3.4.2 价值系数价值系数Cj变化的灵敏度分析变化的灵敏度分析基变量基变量非基变量非基变量常数项常数项 XBXNXS系数矩阵系数矩阵检验数检验数I0B-1 NCN-CBB-1NB-1-CBB-1B-1b-CBB-1bC变化，检验数可能发生变化 要保持最优解不变，必须使所以检验数都小于零，但最优值可能发生变化cj23000CBXBbx1x2 x3x4x5203x1x5x24421000010-2

32、1/21/4-1/8010-1400-3/2-1/80在保证最优基不变的情况下，求在保证最优基不变的情况下，求C C2 2的变化范围的变化范围1133322114442200203201.50.500.50.2502030.500.3750.12500.125NBBNBBCC B NCC B pccCC B NCC B pcc 223104cC cj712000CBXBbx1x2 x3x4x50712x3x1x2842024010001100-3.120.4-0.121.16-0.20.16-Z000-1.36-0.52在保证最优基不变的情况下，求在保证最优基不变的情况下，求C C1 1的变化

33、范围的变化范围14111511123.12007120.41.360.400.121.16007120.20.520.200.163.42.63.69.6NBNBCC B NccCC B NcccC 3.4.3 3.4.3 技术系数技术系数aij变化的灵敏度分析变化的灵敏度分析现有一种新产品，每件消耗资源如表所示，问该厂是否生产？cj23000CBXBbx1x2 x3x4x5203x1x5x24421000010-20.50.250.5-0.12501000-1.5-0.1250设生产产品为 ，则系数向量为3x3263Tp 例例7 7133351.50.12502631.250TBcC B p

34、 1300.25021.520.51620.50.125030.25B p cj230005CBXBbx1x2 x3x4x5203x1x5x24421000010-20.50.250.5-0.1250101.520.2500-1.5-0.12501.253xcj230005CBXBbx1x2 x3x4x5253x1x2121.51000011.5-10.75-0.1250.250.18750.750.50.12501000-0.25-0.4375-0.62503x3x16.5Z cj23000CBXBbx1x2 x3x4x5203x1x5x24421000010-20.50.250.5-0.12501000-1.5-0.1250111141.50.12502520.3750TBcC B p 1100.25021.2520.5150.50.50.125020.375B p cj230004CBXBbX1x2 x3x4x5X1203x1x5x24421000010-20.50.250.5-0.1250101.250.50.37500-1.5-0.12500.375cj230004CBXBbX1x2 x3x4x5X1403X1x5x23.22.40.80.8-0.4-0.30010-20.50.20.4-0.2010100-0.30-1.5-0.20015.2Z