没有对偶单纯形法课件.ppt

1、解解:1)决策变量决策变量：设设y1,y2分别表示出售单位原材料的价格（分别表示出售单位原材料的价格（含附加值）和出租设备单位工时的租金含附加值）和出租设备单位工时的租金 3)约束条件约束条件:工厂决策者考虑：工厂决策者考虑：（1）出售原材料和出租设备应不少于自己生产产品的）出售原材料和出租设备应不少于自己生产产品的获利，否则不如自己生产为好。因此有获利，否则不如自己生产为好。因此有2）目标函数：）目标函数：此时工厂的总收入为此时工厂的总收入为W=24y1+26y2,这也是这也是租赁方需要付出的成本租赁方需要付出的成本.而在这个问题中而在这个问题中,是企业不生产是企业不生产,将将自己的资源出售

2、或出租自己的资源出售或出租,因此因此,此时此时,起决定作用的是租赁方起决定作用的是租赁方,所以此时的目标函数为所以此时的目标函数为 Min W=24y1+26y2323432yyyy2121（2）价格应尽量低，否则没有竞争力（此价格可成为与客）价格应尽量低，否则没有竞争力（此价格可成为与客户谈判的底价）户谈判的底价）租赁者考虑：希望价格越低越好，否则另找他人。租赁者考虑：希望价格越低越好，否则另找他人。于是，能够使双方共同接受的是于是，能够使双方共同接受的是：上述两个上述两个LP问题的数学模型是在同一企业的资源状况问题的数学模型是在同一企业的资源状况和生产条件下产生的，且是同一个问题从不同角度

3、考虑所和生产条件下产生的，且是同一个问题从不同角度考虑所产生的，因此两者密切相关。称这两个产生的，因此两者密切相关。称这两个LP问题是互为对偶问题是互为对偶的两个的两个LP问题。其中一个是另一个问题的问题。其中一个是另一个问题的对偶问题。对偶问题。0,323432.t.s2624Wminyyyyyyyy21212121一般地对于任何一个线性规划问题都有一个与之相对应的一般地对于任何一个线性规划问题都有一个与之相对应的对偶问题。原问题与对偶问题的一般形式为：对偶问题。原问题与对偶问题的一般形式为：0.t.sZmaxxbxaxaxabxaxaxabxaxaxaxcxcxcjmnmn22m11m2n

4、n22221211nn1212111nn22110.t.sWminycyayayacyayayacyayayaybybybinmmn2n21n12m2m2221121m1m221111mm2211 原问题（原问题（P）对偶问题（对偶问题（D）相应的矩阵形式为：相应的矩阵形式为：0XbAX.t.sCXZmax0YCYA.t.sYbWmin4对称形式的对偶问题为：对称形式的对偶问题为：0XbAX.t.sCXZmax（P）0YCYA.t.sYbWmin（D）二、对偶理论二、对偶理论(Dual Theory)1.原问题与对偶问题的关系原问题与对偶问题的关系由以上两式可知，原问题与对偶问题之间具有如下关

5、系由以上两式可知，原问题与对偶问题之间具有如下关系(1)一个问题中的约束条件个数等于它的对偶问题中的变量数一个问题中的约束条件个数等于它的对偶问题中的变量数;(2)一个问题中目标函数的系数是其对偶问题中约束条件的右端项一个问题中目标函数的系数是其对偶问题中约束条件的右端项(3)约束条件在一个问题中为约束条件在一个问题中为“”,则在其对偶问题中为则在其对偶问题中为“”;(4)目标函数在一个问题中为求最大值目标函数在一个问题中为求最大值,在其对偶问题中则为求最小值在其对偶问题中则为求最小值 5非对称形式的对偶问题为：非对称形式的对偶问题为：（LP）0XbAX.t.sCXZmax（DP）无约束YCY

6、A.t.sYbWmin推导过程如下：原模型变化为推导过程如下：原模型变化为0.0.maxmaxXbAXbAXtsXbAXbAXtsCXZCXZ根据对称对偶关系，根据对称对偶关系，写出其相应的对偶问写出其相应的对偶问题题 无约束YCYAtsYYCAYYtsYYCAYAYtsYbWbYYWbYbYW.0,)(.0,.min)(minmin令令YYY 6原问题Max（对偶问题）对偶问题Min（原问题）约束条件数=m 变量个数=m第i个约束条件为“”第i个约束条件为“”第i个约束条件为“=”第i个变量0 第i个变量0 第i个变量无限制变量个数=n 约束条件个数=n第i个变量0第i个变量0第i个变量无限

7、制 第i个约束条件为“”第i个约束条件为“”第i个约束条件为“=”第i个约束条件的右端项目标函第i个变量的系数 目标函数第i个变量的系数 第i个约束条件的右端顶 归纳对称形式与非对称形式的对偶归纳对称形式与非对称形式的对偶,原问题与对偶问题原问题与对偶问题之间的关系如下表所示之间的关系如下表所示0,324222max:321321321321yyyyyyyyyyyyZLP解:0,121214232min:P2121212121xxxxxxxxxxWD例例1、写出下列线性规划问题的对偶问题、写出下列线性规划问题的对偶问题0,523554min21212121xxxxxxxxZ解:无非负限制212

8、12121,0525453maxyyyyyyyyW定理定理1 如果线性规划中第如果线性规划中第k个约束条件是等式个约束条件是等式,则它的对偶规则它的对偶规划中的第划中的第k个变量无非负限制个变量无非负限制,反之亦然反之亦然.例例2、写出下列线性规划问题的对偶问题、写出下列线性规划问题的对偶问题例例3 写出下面原规划的对偶规划写出下面原规划的对偶规划无限制21212121,0355265minxxxxxxxxz解:0652535max21212121yyyyyyyyw无限制10 2、对偶问题的基本定理、对偶问题的基本定理 MaxZ=CXMinW=Yb0XbAX设0YCYA（1）（对称性）对偶问题

9、的对偶是原问题；）（对称性）对偶问题的对偶是原问题；（2）（弱对偶定理）若）（弱对偶定理）若X(0)是原问题的可行解，是原问题的可行解，Y(0)是对偶问题的可是对偶问题的可行解行解,则有则有（3）（无界性）若原问题（对偶问题）为无界解，则其对偶问题（）（无界性）若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解；原问题）无可行解；（4）（最优性定理），若）（最优性定理），若X(0)、Y(0)分别是互为对偶问题的可行解，分别是互为对偶问题的可行解，且且C X(0)=Y(0)b，则，则X(0)、Y(0)分别是它们的最优解分别是它们的最优解（5）（强对偶定理）若互为对偶问题之一有最优解，则

10、另一问题必）（强对偶定理）若互为对偶问题之一有最优解，则另一问题必有最优解，且它们的目标函数值相等。有最优解，且它们的目标函数值相等。bYXC)0()1112思考题：已知如下线性规划问题的对偶问题的最优解为思考题：已知如下线性规划问题的对偶问题的最优解为y1*=4/5,y2*=3/5,z*=5，试用对偶理论找出原问题的最优解，试用对偶理论找出原问题的最优解5,2,1j,0332432.t.s32532Wminxxxxxxxxxxxxxxxxj543215432154321解：其对偶问题为：解：其对偶问题为：0,332532322.t.s34Zmaxyyyyyyyyyyyyyy212121212

11、12121应用互补松驰性定理，将y1*=4/5,y2*=3/5代入对偶问题的约束条件得：3243xxxx5151解得：x1=1,x5=1,x2=x3=x4=0又由于y1*,y2*0，原问题的两个 约束为紧约束，所以x10 x2=0 x3=0 x4=0 x5 0作业作业已知如下线性规划问题的对偶问题的最优解为y1*=4,y2*=1，试用对偶理论找出原问题的最优解和最优值4,2,1,0122228.652max432143143212jtsWxxxxxxxxxxxxj13三、对偶单纯形法三、对偶单纯形法1.单纯形法的重新解释单纯形法的重新解释X*是最大化LP问题最优解的充要条件是同时满足：0CAB

12、C0bB1B1（称为原始可行条件）（称为对偶可行条件）因此，单纯形法是在保持原始可行下，经过迭代，逐因此，单纯形法是在保持原始可行下，经过迭代，逐步实现对偶可行，达到求出最优解的过程。步实现对偶可行，达到求出最优解的过程。01 bB，然后从然后从01CABCB到01CABCB 根据对偶问题的对称性，根据对偶问题的对称性，也可以在保持对偶可行也可以在保持对偶可行下，经过迭代，逐步实现原始可行，以求得最优解下，经过迭代，逐步实现原始可行，以求得最优解.对偶单纯形法就是根据这种思想所设计的。对偶单纯形法就是根据这种思想所设计的。因此，对偶单纯形法是先保证现行解对对偶问题可行，即因此，对偶单纯形法是先

13、保证现行解对对偶问题可行，即01 CABCB，然后从然后从01bB到到01bB例例14 用对偶单纯形法求解下列线性规划问题：用对偶单纯形法求解下列线性规划问题：)4,3,2,1i(,03422242.t.s1216812Zminyyyyyyyyyyyi4213214321解：化为标准形后，用对偶单纯形法求解过程如下表所示解：化为标准形后，用对偶单纯形法求解过程如下表所示 cj -12 -8 -16 -12 0 0CBXBb y1 y2 y3 y4 y5 y600y5y6-2-3-2 -1 -4 0 1 0-2 -2 0 -4 0 1 w0 12 8 16 12 0 02、对偶单纯形法的计算步骤

14、：、对偶单纯形法的计算步骤：cj -12 -8 -16 -12 0 0CBXBb y1 y2 y3 y4 y5 y60-12y5y4-23/4-2 -1 -4 0 1 0 1/2 1/2 0 1 0 -1/4 w-9 6 2 16 0 0 3 cj -12 -8 -16 -12 0 0CBXBb y1 y2 y3 y4 y5 y6-8-12y2y42-1/4 2 1 4 0 -1 0-1/2 0 -2 1 1/2 -1/4 w-13 2 0 8 0 2 3 cj -12 -8 -16 -12 0 0CBXBb y1 y2 y3 y4 y5 y6-8-16y2y33/21/8 1 1 0 2 0

15、 -1/2 1/4 0 1 -1/2 -1/4 1/8 w-14 0 0 0 4 4 2 上表中常数列上表中常数列b所对应的系数均为非负，已求得问题的最优所对应的系数均为非负，已求得问题的最优解，最优解为解，最优解为y=(y1,y2,y3,y4)T=(0,3/2,1/8,0)；最优值为；最优值为z*=14注意注意：对偶单纯形法仍是求解原问题，它是适用于当原问题无：对偶单纯形法仍是求解原问题，它是适用于当原问题无可行基解，且所有检验数均大于可行基解，且所有检验数均大于0的情况。若原问题既无可行基的情况。若原问题既无可行基解，而检验数中又有小于解，而检验数中又有小于0的情况，只能用人工变量法求解。

16、在的情况，只能用人工变量法求解。在计算机求解时，只有人工变量法，没有对偶单纯形法。计算机求解时，只有人工变量法，没有对偶单纯形法。19练习：用对偶单纯形法求解下列线性规划问题练习：用对偶单纯形法求解下列线性规划问题0,52233.18124max213231321yyyyyytsyyyz解：迭代结果如下解：迭代结果如下 cj-4 -12 -18 0 0 CBXBb y1 y2 y3 y4 y5 00y4y5-3-5-1 0 -1 1 0 0 -2 -2 0 1 Z0 4 12 18 0 0 20 cj-4 -12 -18 0 0 CBXBb y1 y2 y3 y4 y5 0-12y4y2-35

17、/2-1 0 -3 1 0 0 1 1 0 -1/2 Z-30 4 0 6 0 6 cj-4 -12 -18 0 0 CBXBb y1 y2 y3 y4 y5 18-12y3y213/2 1/3 0 1 -1/3 0-1/3 1 0 1/3 -1/2 Z-36 2 0 0 2 6 因此，最优解为：因此，最优解为：y2=3/2,y3=1，最优值为：，最优值为：maxZ=-3621四、影子价格四、影子价格一、影子价格问题的提出影子价格的定义影子价格在经济管理中的应用二、边际贡献本 节 要 点资源的合理利用问题：资源的合理利用问题：使使获获得得的的总总利利润润最最大大？现现有有资资源源，产产计计划划

18、，才才能能充充分分利利用用如如下下表表，问问如如何何安安排排生生得得的的利利润润限限制制以以及及每每件件产产品品可可获获源源数数、每每种种资资源源的的数数量量所所消消费费的的资资种种资资源源，已已知知每每件件产产品品，要要消消耗耗种种产产品品，周周期期内内生生产产某某厂厂计计划划在在下下一一个个生生产产mnAAABBB2121n 影子价格影子价格1、问题的提出、问题的提出资源资源单位单位消费消费产品产品mAAA21nBBB21mnmmnnaaaaaaaaa212222111211资源资源限制限制mbbb21单位单位利润利润nccc21nnxcxcxcz 2211max mnmnmmnnnnbx

19、axaxabxaxaxabxaxaxat s22112222212111212111.0,21 nxxx的的总总利利润润最最大大？利利用用现现有有资资源源，使使获获得得排排生生产产计计划划，才才能能充充分分下下表表，问问如如何何安安件件产产品品可可获获得得的的利利润润如如资资源源的的数数量量限限制制以以及及每每所所消消费费的的资资源源数数、每每种种种种资资源源，已已知知每每件件产产品品，耗耗种种产产品品，要要消消，周周期期内内生生产产某某厂厂计计划划在在下下一一个个生生产产mnAAABBB2121),2,1njBxjj（的的产产量量表表示示产产品品解解：设设还有现金，还有现金，如何投资如何投资

20、决策依据决策依据：比较比较第第i种资源增加一个单位种资源增加一个单位，其余资源不增加时，其余资源不增加时利润的增加值利润的增加值nnxcxcxcz2211max对 mnmnmmnnnnbxaxaxabxaxaxabxaxaxat s22112222212111212111.0,21 nxxx决策依据：决策依据：在取得最优方案的前提下在取得最优方案的前提下比较第比较第i种资源增加一个单位，种资源增加一个单位，其余资源不增加时利润的增其余资源不增加时利润的增加值加值设设B是最优基，是最优基，Z*是最优值是最优值mmybybybSD 2211min)(nmmnnnmmmmcyayayacyayaya

21、cyayayats22112222211211221111.0,21 myyy设设Y*是（是（D）的最优解）的最优解则则Z*=Y*b*2211mmybybyb 其其余余不不变变时时，当当,1 iibb*)1(*11mmiiybybybZ *iyZ *iyZZZ ibZ*iy 25 1.对偶解Y*=CBB-1的经济含义 设互为对偶的LP问题 maxZ=CX minW=Yb (原)0XbAX (对)0YCYA 有 Z*=CBB-1b=W*(其中B为最优基)因此*1YBCbZB 或者说Z*=y*1b1+y*2b2+y*mbm 则*iiybZ ibZ *个分量的第）的最优解对偶问题（iYDyi*Lag

22、rangeLagrange乘子乘子边际价格边际价格2 2、影子价格的定义影子价格的定义121*),*,*,(*BCyyyYBm.*,个约束条件的影子价格称为第的改变量目标函数最优值其余不变时，所引起的增加一个单位的右端常数个约束条件）的第）中，（）和（问题（影子价格：在一对对偶iyZZbiPDPii27 其含义是：若对原问题右端常数项向量b中的某一常数项bi增加一个单位，目标函数的最优值Z*的变化将是yi*。换句话说，yi*表示当bi增加一个单位时，目标函数最优值的相应增量。实质上yi*就是第i种资源边际价值的一种表现，也是对第i种资源的一种估价。121*),*,*,(*BCyyyYBm CC

23、BCNCSbXBXNXSXBB-1bIB-1NB-1ZC BB-1b0C BB-1N-CNCB B-10,1.1max1111)(XXBXBXBXXBCXCBCBCNBSNBSBNBbNtsNNBbz最优基变量为最优基变量为 时，单纯形表时，单纯形表BX121*),*,*,(*BCyyyYBm29 cj 4 3 0 0CBXBb x1 x2 x3 x434x2x146 0 1 3/5 -2/5 1 0 -2/5 3/5 Z36 0 0 1/5 6/5用单纯形法求得最优表为：由此，它们的最优解分别是X*=(6,4)T和Y*=(1/5,6/5)最优值为：Z*=W*=36=24y1*+26y2*5/

24、6b*Z*y,5/1b*Z*y2211其中y1*=1/5表示单独对材料增加1个单位，可使Z值增加1/5个单位的利润；y2*=6/5表示单独对工时增加1个单位，可使Z值增加6/5个单位的利润。302.影子价格的定义影子价格的定义 把某一经济结构中的某种资源，在最优决策下的边际价值称把某一经济结构中的某种资源，在最优决策下的边际价值称为该资源在此经济结构中的为该资源在此经济结构中的影子价格影子价格。影子价格是在最优决策下对资源的一种估价，没有最优决策就没有影子价格，所以影子价格又称“最优计划价格”，“预测价格”等等。资源的影子价格定量的反映了单位资源在最优生产方案中为总收益所做出的贡献。313、影

25、子价格的求法影子价格的求法资源的影子价格资源的影子价格Y*=CBB-1，即为最优单纯形表中松驰变量，即为最优单纯形表中松驰变量对应的检验数。对应的检验数。例如：在生产计划问题中，最优表如下例如：在生产计划问题中，最优表如下 cj 4 3 0 0CBXBb x1 x2 x3 x434x2x146 0 1 3/5 -2/5 1 0 -2/5 3/5 Z36 0 0 1/5 6/5两种资源：材料的影子价格为两种资源：材料的影子价格为y1=1/5 工时的影子价格为工时的影子价格为y2=6/5润润最最大大？，使使获获得得的的总总利利才才能能充充分分利利用用现现有有资资源源问问如如何何安安排排生生产产计计

26、划划，得得的的利利润润如如下下表表，限限制制以以及及每每件件产产品品可可获获源源数数、每每种种资资源源的的数数量量产产品品所所消消费费的的资资时时三三种种资资源源，已已知知每每件件耗耗钢钢材材、煤煤炭炭、设设备备台台两两种种产产品品，要要消消生生产产周周期期内内生生产产甲甲、乙乙例例：某某厂厂计计划划在在下下一一个个资源资源单位单位消费消费产品产品甲甲乙乙资源资源限制限制钢材钢材52170煤炭煤炭23100设备台时设备台时15150单位利润单位利润（万元）（万元）1018211810maxxxz 求求 0,15051003217025.21212121xxxxxxxxts表表示示产产品品乙乙的

27、的产产量量表表示示产产品品甲甲的的产产量量解解：设设21xxx1x2x3x4x5x3001-23/711/7540/7x11005/7-3/750/7x2010-1/72/7200/7000-32/7-6/7Z-4100/7最优解最优解X*=(50/7，200/7)最优值最优值Z*=4100/7Y*=(0，32/7,6/7)对偶问题的最优解对偶问题的最优解 0,15051003217025.21212121xxxxxxxxts对偶问题最优解对偶问题最优解Y*=(0，32/7,6/7)211810max)(xxzP 求求钢材钢材煤炭煤炭设备台时设备台时:钢材的影子价格钢材的影子价格:煤炭的影子价

28、格煤炭的影子价格:设备台时的影子价格设备台时的影子价格即再增加即再增加1吨钢材，利润不会增加吨钢材，利润不会增加即再增加即再增加1吨煤炭，利润增加吨煤炭，利润增加32/7万元万元即再增加即再增加1个台时，利润增加个台时，利润增加6/7万元万元利润利润，0*1 y732*2 y76*3 y 0,15051003217025.21212121xxxxxxxxts原问题最优解原问题最优解X*=(50/7，200/7)对偶问题最优解对偶问题最优解Y*=(0，32/7,6/7)211810max)(xxzP 求求钢材钢材煤炭煤炭设备台时设备台时由互补松弛定理：由互补松弛定理：,076*,0723*32

29、yy由由1707650*2*521 xx约约束束：有有若若把把最最优优方方案案带带入入钢钢材材 150*5*100*3*22121xxxx现有资源中的煤炭和设备台时已经全部用完而没有现有资源中的煤炭和设备台时已经全部用完而没有剩余，因此若增加这两种资源，必然会给工厂带来剩余，因此若增加这两种资源，必然会给工厂带来新的效益。新的效益。现有资源中的钢材有剩余，因此若增加这种资源，现有资源中的钢材有剩余，因此若增加这种资源，只能造成积压，不会给工厂增加效益。只能造成积压，不会给工厂增加效益。0*1 y利润利润*影子价格的大小客观地反映了资源影子价格的大小客观地反映了资源 在系统内部的在系统内部的稀缺

30、程度稀缺程度364.影子价格的参谋作用影子价格的参谋作用 （1）指出企业挖潜革新的途径）指出企业挖潜革新的途径影价0，说明该资源已耗尽，成为短线资源。影价=0，说明该资源有剩余，成为长线资源。l 影子价格能指示企业内部挖潜的方向影子价格能指示企业内部挖潜的方向影子价格越大的资源影子价格越大的资源，表明：，表明：这种资源对目标增益的影响越大这种资源对目标增益的影响越大这种资源在该企业越稀缺、贵重这种资源在该企业越稀缺、贵重管理措施：管理措施：重视对该种资源的管理，重视对该种资源的管理，通过挖潜革新、降低消耗通过挖潜革新、降低消耗或及时补充该种资源或及时补充该种资源影价0，说明该资源已耗尽，成为短

31、线资源。影价影价=0，这种资源对该企业来说相对富裕这种资源对该企业来说相对富裕管理措施：管理措施：向别的企业转让或以市场价出售向别的企业转让或以市场价出售 通过对企业内部的改造、挖潜和增加对影子通过对企业内部的改造、挖潜和增加对影子价格大于零的资源的投入，使原有剩余资源得到价格大于零的资源的投入，使原有剩余资源得到充分利用充分利用39（3）可以预测产品的价格）可以预测产品的价格产品的机会成本为产品的机会成本为CBB-1A-C，只有当产品价格定在机会成，只有当产品价格定在机会成本之上，企业才有利可图。本之上，企业才有利可图。（4）可作为同类企业经济效益评估指标之一。）可作为同类企业经济效益评估指

32、标之一。对于资源影子价格越大的企业，资源的利用所带来的收益对于资源影子价格越大的企业，资源的利用所带来的收益就越大，经济效益就越好。就越大，经济效益就越好。（2）对市场资源的最优配置起着推进作用）对市场资源的最优配置起着推进作用即在配置资源时，对于影子价格大的企业，资源优先供给即在配置资源时，对于影子价格大的企业，资源优先供给EX:某化工厂有三种资源某化工厂有三种资源A、B、C，生产三种产品甲、乙、，生产三种产品甲、乙、丙，设甲、乙、丙的产量分别为丙，设甲、乙、丙的产量分别为x1,x2,x3,其数学模型为：其数学模型为：0,)(4204)(46023)(4302.523max321213132

33、1321xxxCxxBxxAxxxtsxxxz资源限制资源限制资源限制资源限制资源限制资源限制已解得最优单纯形表如下已解得最优单纯形表如下 已解得最优单纯形表如下已解得最优单纯形表如下 CBXBb x1 x2 x3 x4 x5 x6250 x2x3x610023020-1/4 1 0 1/2 -1/4 03/2 0 1 0 1/2 0 2 0 0 -2 1 1 Z 4 0 0 1 2 0(1)求三种资源的影子价格求三种资源的影子价格,并解释其经济含义并解释其经济含义;(2)市场看好，决定增加一种资源的供应量，问应增加哪种市场看好，决定增加一种资源的供应量，问应增加哪种资源？资源？2、影子价格是

34、在系统达到最优时对系统资源的一、影子价格是在系统达到最优时对系统资源的一 种最优估价，并假设第种最优估价，并假设第i种资源增加一个单位时种资源增加一个单位时 最优基没改变。最优基没改变。关于影子价格的关于影子价格的说明说明：1、影子价格的取值与系统的状态有关，系统中任、影子价格的取值与系统的状态有关，系统中任 一状态的改变都会引起影子价格的变化一状态的改变都会引起影子价格的变化3、影子价格是一种资源的虚拟价格、影子价格是一种资源的虚拟价格 资源的市场价格资源的市场价格影子价格是一种机会成本，在纯市场经济条件下，影子价格是一种机会成本，在纯市场经济条件下，当市场价格低于影子价格，可以买进这种资源

35、；当市场价格低于影子价格，可以买进这种资源；相反，相反，当市场价格高于影子价格，可以卖出这种当市场价格高于影子价格，可以卖出这种资源。资源。二、边际贡献生产策略问题：生产策略问题：资源资源单位单位消费消费产品产品mAAA21nBBB21mnmmnnaaaaaaaaa212222111211资源资源限制限制mbbb21单位单位价格价格nccc21nnxcxcxcz 2211max mnmnmmnnnnbxaxaxabxaxaxabxaxaxat s22112222212111212111.0,21 nxxx的的总总收收入入最最大大？利利用用现现有有资资源源，使使获获得得排排生生产产计计划划，才才

36、能能充充分分下下表表，问问如如何何安安件件产产品品可可获获得得的的利利润润如如资资源源的的数数量量限限制制以以及及每每所所消消费费的的资资源源数数、每每种种种种资资源源，已已知知每每件件产产品品，耗耗种种产产品品，要要消消，周周期期内内生生产产某某厂厂计计划划在在下下一一个个生生产产mnAAABBB2121),2,1njBxjj（的的产产量量表表示示产产品品解解：设设2P的的数数量量种种产产品品所所消消耗耗各各种种资资源源生生产产一一个个单单位位第第 jPj 问题：市场上正在热卖第问题：市场上正在热卖第j种产品，是否增加该产品种产品，是否增加该产品的产量的产量策略：若在最优方案中，第策略：若在

37、最优方案中，第j种产品的产量种产品的产量xj为非基为非基变量，不能生产该产品变量，不能生产该产品0.max XbAXtsCXz对对问问题题B取取可可行行基基NBNBXNBCCbBCZ)(max11 NBNXBbBX11 0,0 NBXX检验数检验数），（设设基基变变量量 mBxxxX,21为最优基时为最优基时当当B）（，非基变量，非基变量 nmmNxxxX,21 nmmBNNBCC ,211 NBNBXNBCCbBCZ)(11 0Znnmmmmxxx 2211),2,1(,1nmmjxxjj 其其余余变变量量不不变变时时当当 Z,j jxZj j 的的贡贡献献种种产产品品给给目目标标函函数数带

38、带来来增增加加一一个个单单位位第第 j 际际贡贡献献种种产产品品对对目目标标函函数数的的边边第第j0,1 NBCCBN，即即0 j nmmjXZj,2,1 的的减减函函数数是是 njm 1 nnmmmmPYcPYcPYc*,*,*2211 ）的的最最优优解解为为（DBCYB1*的的最最优优基基，为为若若)(,21PPPPBm NBCCBN1*),*,*,(*21myyyY 种种资资源源的的影影子子价价格格第第iyi *),(21nmmccc ),(*21nmmPPPY )(*NPPYcjmjmjmjm 即即际际贡贡献献种种产产品品对对目目标标函函数数的的边边第第jj 别人热卖的别人热卖的产品我

39、该不该生产？产品我该不该生产？njm 1)(*NPPYcjjjj 即即jPY*的的单单位位成成本本种种产产品品按按影影子子价价格格核核算算第第j 隐含成本隐含成本是是最最优优基基时时，当当B0 j 有有jjcPY*产产品品的的价价格格，种种产产品品的的隐隐含含价价格格高高于于即即第第j不不能能生生产产第第j种产品的价格种产品的价格耗量种产品对各种资源的消第j各种资源的影子价格各种资源的影子价格新产品开发决策分析新产品开发决策分析)(*NPPYcjjjj 是是非非基基变变量量，若若jx获获得得的的总总收收入入最最大大？充充分分利利用用现现有有资资源源，使使何何安安排排生生产产计计划划，才才能能价

40、价如如下下表表，问问如如限限制制以以及及每每件件产产品品的的售售源源数数、每每种种资资源源的的数数量量产产品品所所消消费费的的资资时时三三种种资资源源，已已知知每每件件耗耗钢钢材材、煤煤炭炭、设设备备台台两两种种产产品品，要要消消生生产产周周期期内内生生产产甲甲、乙乙例例：某某厂厂计计划划在在下下一一个个资源资源单位单位消费消费产品产品甲甲乙乙资源资源限制限制钢材钢材52170煤炭煤炭23100设备台时设备台时15150单位价格单位价格（万元）（万元）1018211810maxxxz 求求 0,15051003217025.21212121xxxxxxxxts表表示示产产品品乙乙的的产产量量表

41、表示示产产品品甲甲的的产产量量解解：设设21xxx1x2x3x4x5000-32/7-6/7Z-4100/7x3001-23/711/7540/7x11005/7-3/750/7x2010-1/72/7200/7，钢材的影子价格钢材的影子价格0*1 y732*2 y煤炭的影子价格煤炭的影子价格76*3 y设备台时的影子价格设备台时的影子价格现有两种新产品现有两种新产品A和和B，他们对资源的消耗额，他们对资源的消耗额以及可能获得的单位利润如表所示，试决定他以及可能获得的单位利润如表所示，试决定他们是否值得投产。们是否值得投产。资源资源单位单位消费消费产品产品AB钢材钢材12煤炭煤炭21设备台时设

42、备台时34单位价格单位价格（万元）（万元）109资源资源单位单位消费消费产品产品AB钢材钢材12煤炭煤炭21设备台时设备台时34价格价格（万元）（万元）109现有两种新产品现有两种新产品A和和B，他们对资源的消耗额，他们对资源的消耗额以及可能获得的单位利润如表所示，试决定他以及可能获得的单位利润如表所示，试决定他们是否值得投产。们是否值得投产。，钢材的影子价格钢材的影子价格0*1 y732*2 y煤炭的影子价格煤炭的影子价格76*3 y设备台时的影子价格设备台时的影子价格产品产品A的隐含成本的隐含成本=376273210 782 10不生产不生产产品产品B的隐含成本的隐含成本=47617322

43、0 756 9 可以生产可以生产APY*BPY*面对市场变化，灵敏度分析的任务是须解决以下两类问题面对市场变化，灵敏度分析的任务是须解决以下两类问题一、当系数一、当系数A、b、C中的某个发生变化时中的某个发生变化时,目前的最优基是否仍目前的最优基是否仍最优（即目前的最优生产方案是否要变化）最优（即目前的最优生产方案是否要变化）?(称为模型参数的称为模型参数的灵敏度分析灵敏度分析)二、增加一个变量或增加一个约束条件时，目前的最优基是否二、增加一个变量或增加一个约束条件时，目前的最优基是否仍最优（即目前的最优生产方案是否要变化）仍最优（即目前的最优生产方案是否要变化）(称为模型结构的称为模型结构的

44、灵敏度分析灵敏度分析)灵敏度分析的方法是在目前最优基灵敏度分析的方法是在目前最优基B下进行的。即当参数下进行的。即当参数A、b、c中的某一个或几个发生变化时，考察是否影响以下两式的中的某一个或几个发生变化时，考察是否影响以下两式的成立？成立？0CABC0bB1B1bXXBB-1b0对原问题可行对原问题可行B-1AZC BB-1bC BB-1A-C0对对偶问题可行对对偶问题可行矩阵形式的单纯形表为矩阵形式的单纯形表为优化后分析按如下方式进行优化后分析按如下方式进行原问题原问题对偶问题对偶问题结论或继续计算的步骤结论或继续计算的步骤可行解可行解可行解可行解问题的最优解或最优基不变问题的最优解或最优

45、基不变可行解可行解非可行解非可行解用单纯形法继续迭代求最优解用单纯形法继续迭代求最优解非可行解非可行解可行解可行解用对偶单纯形法继续迭代求最优解用对偶单纯形法继续迭代求最优解非可行解非可行解非可行解非可行解引进人工变量引进人工变量,编制新的单纯形表重新编制新的单纯形表重新计算计算1、对于参数、对于参数b的灵敏度分析的灵敏度分析从矩阵形式的单纯形表中可以看出，从矩阵形式的单纯形表中可以看出，b的变化只影响最优解的的变化只影响最优解的变化和最优值的变化。变化和最优值的变化。XXBB-1bB-1AZC BB-1bC BB-1A-C因此，当因此，当 时，最优基不变（即生产产品的品种时，最优基不变（即生

46、产产品的品种不变，但数量及最优值会变化）。不变，但数量及最优值会变化）。0bB1 0bB1 是一个不等式组，从中可以解得是一个不等式组，从中可以解得b的变化范围的变化范围若若B-1b中有小于中有小于0的分量，则需用对偶单纯形法迭代，以的分量，则需用对偶单纯形法迭代，以求出新的最优方案。求出新的最优方案。b53P137 例题4-12 对于生产计划问题，为使最优方案不变，试讨论第二个约束条件b2的变化范围。0,)(2623)(2432.t.s34Zmaxxxxxxxxx21212121工时约束材料约束 cj 4 3 0 0 CBXBb x1 x2 x3 x4 34x2x146 0 1 3/5 -2

47、/5 1 0 -2/5 3/5 Z36 0 0 1/5 6/5 解：生产计划问题的数学模型和最优单纯形表为：54 从矩阵形式的单纯形表中可知，从矩阵形式的单纯形表中可知，b2的变化只影响解的变化只影响解的可行性的可行性B-1b0,因此，为使最优解不变，只需变化以后的因此，为使最优解不变，只需变化以后的 B-1b0即可。即可。05354852572245/35/25/25/3bbbbB2221053548052572bb22由解得：3616b255若若b2变化超过范围，则需用对偶单纯形法进行求解。如变化超过范围，则需用对偶单纯形法进行求解。如b2=6，则，则06126245/35/25/25/3

48、bB11261243bBC1B cj 4 3 0 0 CBXBb x1 x2 x3 x4 34x2x112-6 0 1 3/5 -2/5 1 0 -2/5 3/5 Z12 0 0 1/5 6/5 将上述数字替换最优单纯形表中相应位置的数据得：56 cj 4 3 0 0 CBXBb x1 x2 x3 x4 30 x2x3315 3/2 1 0 1/2-5/2 0 1 -3/2 Z9 1/2 0 0 3/2 用对偶单纯形法迭代，求出的最优单纯形表如下：得到新的最优解为：x1=0,x2=3;maxz=9572、对价值系数、对价值系数Cj变化的分析变化的分析（1）当）当CN（非基变量的目标函数系数非基

49、变量的目标函数系数）中某个）中某个Cj发生变发生变化时，只影响到非基变量化时，只影响到非基变量xj的检验数的检验数1()()jBjjjjjC BPCCC 由于由于所以所以,当当0j 即当即当 jjC时时,最优解不变最优解不变反之反之,当当 时时,最优解改变最优解改变,需要用单纯形法重新进需要用单纯形法重新进行迭代行迭代,以求得新的最优解以求得新的最优解.0j P133例例4-10：对于下列线性规划模型,为使最优解不变，讨论非基变量y1的目标函数系数c3的变化范围。0,)(26223)(2432.t.s234Zmaxxxyxxyxxyxx21121121121工时约束材料约束用单纯形法求得其最优

50、表为：cj 4 3 2 0 0 CBXBb x1 x2 y1 x3 x4 34x2x146 0 1 -1/5 3/5 -2/5 1 0 4/5 -2/5 3/5 Z36 0 0 3/5 1/5 6/5 59解：因为解：因为y1为非基变量，其目标函数系数为非基变量，其目标函数系数c3的变化只会影的变化只会影响到响到y1的检验数，因此为使最优解不变，只需的检验数，因此为使最优解不变，只需03即5/135/32C3若C3=3,则523代入最优单纯形表中相应位置继续迭代以求出新的最优解。cj 4 3 3 0 0 CBXBb x1 x2 y1 x3 x4 34x2x146 0 1 -1/5 3/5 -2