第二章 线性规划的对偶理论3-影子价格对偶单纯形法

第二章线性规划的对偶理论与灵敏度分析补充材料影子价格当线性规划问题求得最优解xj*(j=1,2,n)时，其对偶问题也得到最优解yi*(i=1,2,m)，且代入各自的目标函数有最优性：设是原问题的可行解，是对偶问题的可行解，当时，和是最优解。XˆXˆYˆYˆbYXC/ˆˆwybxczimiinjjj11bi代表:第i种资源的拥有量；yi*代表:在资源最优利用条件下对单位第i种资源的估价。这种估价不是资源的市场价格，而是根据资源在生产中的作用而作的估价，因此称为影子价格。资源影子价格的性质1资源的市场价格是已知数，相对比较稳定，而它的影子价格则依赖于资源的利用情况，是未知数。企业生产任务、产品结构等情况发生变化，资源的影子价格也随之发生变化。2资源的影子价格是一种边际价格。在中对z求bi的偏导数得wybxczimiinjjj11iiybz说明yi*的值相当于在资源得到最优利用条件下，bi每增加一个单位时目标函数z的增量。影子价格(shadowprice)是反映资源最优使用效果的价格。用微积分描述资源的影子价格，即当资源增加一个数量而得到目标函数新的最大值时，目标函数最大值的增量与资源的增量的比值，就是目标函数对约束条件（即资源）的一阶偏导数。用线性规划方法求解资源最优利用时，即在解决如何使有限资源的总产出最大的过程中，得出相应的极小值，其解就是对偶解，极小值作为对资源的经济评价，表现为影子价格。这种影子价格反映劳动产品、自然资源、劳动力的最优使用效果。影子价格(shadowprice)影子价格广泛地被用于投资项目和进出口活动的经济评价。例如，把投资的影子价格理解为资本的边际生产率与社会贴现率的比值时，用来评价一笔钱用于投资还是用于消费的利亏；把外汇的影子价格理解为使市场供求均衡价格与官方到岸价格的比率，用来评价用外汇购买商品的利亏，使有限外汇进口值最大。因此，这种影子价格含有机会成本即替代比较的意思，一般人们称之为广义的影子价格。边际成本指在一定产量水平下，增加或减少一个单位产量所引起成本总额的变动数。用以判断增减产量在经济上是否合算它是在管理会计和经营决策中常用的名词。例如，生产某种产品100个单位时，总成本为5000元，单位产品成本为50元。若生产101个时，其总成本5040元，则所增加一个产品的成本为40元，边际成本即为40元。生产该产品的边际成本是指，每多生产一个单位的产品所增加的成本--原料和劳动力，但并不包括管理费用--租金和管理人员的工资。边际成本在经济学中，边际收入如果大于边际成本，那么，增加产出被认为是值得的。当产量未达到一定限度时，边际成本随产量的扩大而递减，但当产量超越一定限度时，就转而递增。当增加一个单位产量所增加的收入高于边际成本时，是合算的；反之，是不合算的。计算边际成本对制订产品决策具有重要的作用。微观经济学理论认为，产量增至边际成本等于边际收入时，为企业获得其最大利润的产量。通过确定边际成本来提供经营决策所需资料的成本决策，称为边际成本计算。在实际工作中，边际成本计算常只按变动成本计算。■影子价格越大，说明这种资源越是相对紧缺■影子价格越小，说明这种资源相对不紧缺■如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于0种资源的边际利润第种资源的增量第最大利润的增量iibzyiimmiiybybybybwz2211mmiiiybybbybybzz)(2211iiybzy1y2ym3影子价格是产品的机会成本机会成本表示减少一件产品所节省的资源可以增加的利润mmjiijjjyayayaya2211增加单位资源可以增加的利润减少一件产品可以节省的资源0xxxxbxaxaxaxabxaxaxaxabxaxaxaxas.t.xcxcxcxczmaxnj21mnmnjmj2m21m12n2nj2j2221211n1nj1j212111nnjj2211机会成本又称“择一成本”。指把已放弃的方案可能获取的收益，作为评价优选方案即被选取方案所付出的代价。它是在管理会计或投资决策中常用的名词。它是指1笔投资在专注于某一方面后所失去的在另外其它方面的投资获利机会。例如，某企业在甲、乙两个生产方案中优选一个方案。甲方案预计收入为100万元，成本为70万元，利润为30万元；乙方案预计收入为120万元，成本为80万元，利润为40万元。当只能选择其中一个方案并优选乙方案时，甲方案的利润30万元，即构成乙方案的机会成本。机会成本计算机会成本是为在若干可行方案中优选方案提供信息。对优选方案的经济效益作出全面正确评价。由于机会成本并没有实际发生，在会计记录中不作任何反映。机会成本利润差额成本0..min212122112222221121112211112211nmmmmnnmmmnnnmmmmmmmmyyyyyycyyayayacyyayayacyyayayatsybybybw4产品的差额成本差额成本=机会成本-利润jjTjmjmjjjmcPycayayayy)(22115影子价格与资源的关系根据对偶问题的互补松弛性质：时，yi*=0；当yi*0时，有。injjijbxa1injjijbxa1说明生产过程中如果某种资源未得到充分利用时，该种资源的影子价格为零；当资源的影子价格不为零时，表明该种资源在生产中已经消耗完毕。6互补松弛关系的经济解释0000000000jjmjmjjmjiininiinixyyxyxyxxyxy在利润最大化的生产计划中（1）边际利润大于0的资源没有剩余（2）有剩余的资源边际利润等于0（3）安排生产的产品机会成本等于利润（4）机会成本大于利润的产品不安排生产miiijjjBjjyacPBCc117一般说对线性规划问题的求解是确定资源的最优分配方案；而对于对偶问题的求解则是确定对资源的恰当估价，这种估价直接涉及资源的最有效利用。（内部核算用）2.3对偶单纯形法单纯形法的计算步骤如下：第一步：求初始基可行解，列出初始单纯形表。找出一个基可行解第一步结束是，且基变量中无人工变量判断其是否最优第二步否转换到相邻的基可行解，并使目标函数值增大第三步第四步第二步：最优性检验。第三步：从一个基可行解转换到相邻的目标函数值更大的基可行解，列出新的单纯形表。第四步：重复第二、三步，直到计算结束为止。根据对偶原理，当原问题有最优解时，对偶问题也有最优解。反之，也成立。因此，首先找对偶问题的可行解，如果这时有XB=CBB-10即原问题的解也为可行解，则两者均为最优解。否则，保持对偶问题为可行解，找出原问题的相邻基解，再判别是否有XB=CBB-10，循环进行，直到原问题也为可行解为止。cjc1…cm…cj…cnCB基bx1…xm…xj…xnc1c2…cmx1x2…xmb*1b*2…b*m10…0………00…1………a1ja2j…amj………a1na2n…amncj-zj0…0…cj-ciaij…cn-ciaij第一步：求对偶问题的可行基B，列出单纯形表。njjjxcz1max),,1(0),,1(1njxmibxajnjijij表中cj-zj0，b*i的值不要求为正。第二步：确定换出基变量。因为总有0的b*i，令b*r=min{b*i}，其对应变量xr为换出基变量。第三步：确定换入基变量。1为使下一个表中第r行基变量为正值，选择arj0(j=m+1,n)之一为换入基变量；2为使下一个表中对偶问题的解仍为可行解，令rsssrjrjjjjazcaazc}0|{min第四步：用换入的变量xs替换基变量中的换出变量xr，得到一个新的基。对应这个新基，再检查是否所有的b*i0。如是，找到两者的最优解；如为否，回到第二步再循环进行。32152415minyyyw0125263132132yyyyyy化标准形012526515321432yyyyyyyy543210052415maxyyyyyw例用对偶单纯形法求解下述线性规划问题。012526515321432yyyyyyyy543210052415maxyyyyywcj-15-24-500CB基by1y2y3y4y50y4-20-6-1100y5-1-5-2-101cj-zj-15-24-500[]012526515321432yyyyyyyy543210052415maxyyyyywcj-15-24-500CB基by1y2y3y4y50y4-20-6-1100y5-1-5-2-101cj-zj-15-24-500-24y20y5[]012526515321432yyyyyyyy543210052415maxyyyyywcj-15-24-500CB基by1y2y3y4y50y4-20-6-1100y5-1-5-2-101cj-zj-15-24-500-24y21/3011/6-1/600y5-1/3-50-2/3-1/31[]012526515321432yyyyyyyy543210052415maxyyyyywcj-15-24-500CB基by1y2y3y4y50y4-20-6-1100y5-1-5-2-101cj-zj-15-24-500-24y21/3011/6-1/600y5-1/3-50-2/3-1/31cj-zj-150-1-40[][]012526515321432yyyyyyyy543210052415maxyyyyywcj-15-24-500CB基by1y2y3y4y50y4-20-6-1100y5-1-5-2-101cj-zj-15-24-500-24y21/3011/6-1/600y5-1/3-50-2/3-1/31cj-zj-150-1-40-24y2-5y3[][]012526515321432yyyyyyyy543210052415maxyyyyywcj-15-24-500CB基by1y2y3y4y50y4-20-6-1100y5-1-5-2-101cj-zj-15-24-500-24y21/3011/6-1/600y5-1/3-50-2/3-1/31cj-zj-150-1-40-24y21/4-5/410-1/41/4-5y31/215/2011/2-3/2cj-zj-15/200-7/2-3/2[][]加工奶制品的生产计划1桶牛奶3公斤A112小时8小时4公斤A2或获利24元/公斤获利16元/公斤50桶牛奶时间480小时至多加工100公斤A1制订生产计划，使每天获利最大•35元可买到1桶牛奶，买吗？若买，每天最多买多少?•可聘用临时工人，付出的工资最多是每小时几元?•A1的获利增加到30元/公斤，应否改变生产计划？每天：1桶牛奶3公斤A112小时8小时4公斤A2或获利24元/公斤获利16元/公斤x1桶牛奶生产A1x2桶牛奶生产A2获利24×3x1获利16×4x2原料供应5021xx劳动时间48081221xx加工能力10031x决策变量目标函数216472xxzMax每天获利约束条件非负约束0,21xx线性规划模型(LP)时间480小时至多加工100公斤A150桶牛奶每天模型求解图解法x1x20ABC