资源描述：
《第2章(1) 线性规划对偶理论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第2章线性规划的对偶理论(DualityTheory)§1对偶问题(DualProblem)的提出§2原问题与对偶问题§3对偶问题的基本性质§4影子价格(ShadowPrice)§5对偶单纯形法§6灵敏度分析§1对偶问题(DualProblem)的提出对偶问题的概念从经济意义提出的对偶问题一、对偶问题的概念内容一致但从相反角度提出的一对问题称为对偶问题原问题(PrimalProblem)对偶问题(DualProblem)内容一致角度相反二、从经济意义提出的对偶问题例1.某工厂在计划期内要生产产品I和产品II这两种产品，
2、已知生产单位产品所需的设备台时及A、B、C三种设备计划期的有效台时，如下表：问如何安排生产最有利？Nexty1y2y3生产产品的数学模型设产品I和产品II的产量分别为x1和x2件,利润为Z,则:MaxZ=2x1+3x22x1+2x2≤124x1+0x2≤160x1+5x2≤15x1,x2≥0不生产产品(出租设备)的数学模型设设备A、B、C每小时的租金分别为y1、y2、y3,则:2y1+4y2≥22y1+5y3≥3y1,y2,y3≥0W=12y1+16y2+15y3Min原问题对偶问题Backy1y2y3Minw=s.t
3、.≥cj,j=1,2,…..nyi≥0,i=1,2,….mMaxz=s.t.≤bi,i=1,2,…..mxj≥0,j=1,2,….n原问题对偶问题原问题和对偶问题的一般形式：§2原问题与对偶问题原问题（LP1）：Maxz=(23)s.t.对偶问题（LP2）：Minw=(121615)s.t.原问题与对偶问题的比较[例2]写出下列LP问题的对偶问题:MinZ=4x1+6x25x1+7x2≤13x1+2x2≥9x1,x2≥0解:原LP模型变为:MinZ=4x1+6x2-5x1-7x2≥-13x1+2x2≥9x1,x2≥0对
4、偶问题为:y1y2Maxw=-y1+9y2-5y1+3y2≤4-7y1+2y2≤6y1,y2,≥0[例3]写出下列LP问题的对偶问题:MaxZ=4x1+6x25x1+7x2≤13x1+2x2≤9x1≥0,x2取值无约束解:原LP模型变为:MaxZ=4x1+6x2’-6x2’’5x1+7x2’-7x2’’≤13x1+2x2’-2x2’’≤9x1,x2’,x2’’≥0对偶问题为:y1y2Minw=y1+9y25y1+3y2≥47y1+2y2≥6-7y1-2y2≥-6y1,y2,≥0Minw=y1+9y25y1+3y2≥47
5、y1+2y2=6y1,y2,≥0作业：P762.1(a)§3对偶问题的基本性质(P56)性质1弱对偶性性质2最优性性质3无界性性质4强对偶性性质5互补松弛性作业：P762.4性质6(P58)单纯形表中的检验数对应于对偶问题的一个基本解。原问题的松驰变量对应于对偶问题的对偶变量,原问题原来的变量对应于对偶问题的剩余变量。对偶问题基本解的值与原问题检验数的值绝对值相等符号相反。MaxZ=x1+2x22x1+2x2≤80x1+2x2≤4x1,x2≥0对偶问题为:Minw=8y1+4y22y1+0y2≥12y1+2y2≥2y1
6、,y2≥0[例4]求解下列LP问题，并给出对偶问题的最优解Cj1200CbxBbx1x2x3x40x30x42210020184cj-zj1200Θ8/2=44/2=2Minx3x20220101/24201-1cj-zj100-14/2=2/x1x2122101/2-1/220101/2cj-zj00-1/2-1/2最优解为:x1=2,x2=2,x3=0,x4=0y1=1/2,y2=1/2,y3=0,y4=0y3y4y1y2y3y4y1y2§4影子价格(ShadowPrice)经济意义:决策者对单位资源的一种估价。这
7、种估价不是这种资源的市场价格，而是根据资源在生产中做出的贡献而作的估价。当市场价格高于影子价格时，应出售(租)这种资源；当市场价格低于影子价格时,购入这种资源。作用:在公司内部，借助影子价格确定一些内部结算价格，可控制有限资源的使用和考核下属企业经营的好坏。对一些最紧缺的资源，借助影子价格规定使用这种资源一单位时必须上交的利润额，以控制一些经济效益较低的企业自觉地节约使用紧缺资源，使有限资源发挥更大的经济效益。§4对偶单纯形法对偶单纯形法的解题思路对偶单纯形法的计算步骤保持对偶问题为可行解，找出一个基本解原问题为可行解
8、?是停止计算否从一个基本解转移到另一个基本解,并使对偶问题目标函数值进一步减小对偶单纯形法的解题思路对偶单纯形法的计算步骤步骤一:化标准形----列出初始单纯形表步骤二:原问题是否为可行解：所有bi≥0？步骤三:从一个基本解转移到另一个基本解,并使对偶问题目标函数值进一步减小1、确定换出变量（存在小于零的bi时，选取绝对值最大的b
