资源描述：
《运筹学02_对偶理论与敏感性分析1》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、本章内容重点运筹学第二章w线性规划的对偶问题概念、对偶理论及灵敏度分析理论及经济意义DualTheoryandSensitivityw线性规划的对偶单纯形法Analysisw线性规划的灵敏度分析12§1.线性规划对偶问题产品甲产品乙设备能力（h）对偶问题的提出设备A3265例1.1:某工厂拥有A、B、C三种类型的设设备B2140备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产设备C0375品可以获得的利润以及三种设备可利用利润（元/件）15002500的时数如下表所示：设变量xi为第i种（
2、甲、乙）产品的生产件数（i＝1,2）34maxz=1500x+2500x12s.t.3x+2x≤65设y1,y2,y3分别为每工时设备A、B、12C的出租费。2x+x≤40123x2≤75minw=65y1+40y2+75y3x,x≥0s.t.3y1+2y2≥1500（不少于甲产品的利润）122y1+y2+3y3≥2500（不少于乙产品的利润）若该工厂的设备都用于出租，工厂收取出y1,y2,y3≥0租费。试问：设备A、B、C每工时各如何收费才最有竞争力？或者是看成另一个工厂与该工厂竞争。561maxz=150
3、0x1+2500x2原问题对偶问题的定义s.t.3x1+2x2≤65甲企业：有限资源下对称形式：互为对偶2x1+x2≤40合理安排生产计划3x2≤75使得获利最大T(LP)maxz=cx(DP)minw=byx1,x2≥0s.t.Ax≤bs.t.ATy≥cTminw=65y1+40y2+75y3对偶问题x≥0y≥0乙企业：购买甲企业的s.t.3y1+2y2≥1500有限资源、满足甲企业记号约定：c为行向量。2y1+y2+3y3≥2500对利润的要求，成本最y1,y2,y3≥0小！78一对对称形式的对偶规划之间
4、具有(2)从约束系数矩阵看：一个模型中为Ａ，则另一个模型中为AT。一个模型下面的对应关系：是m个约束，n个变量，则它的对偶模型为n个约束，m个变量。(1)若一个模型为目标求“极大”，约束为“小于等于”的不等式，则它(3)从数据b、c的位置看：在两个规划模型中，b和c的位置对换。的对偶模型为目标求“极小”，约束是“大于等于”的不等式。即“max，(4)两个规划模型中的变量皆非负。≤”和“min，≥”相对应。910非对称形式的对偶规划对称型对偶问题一般称不具有对称形式的一对线性规划为(将对偶变量写成行向量形式)非
5、对称形式的对偶规划。对于非对称形式的规划，可以按照下表的(LP)maxz=cx(DP)minw=yb对应关系直接给出其对偶规划。⎧s.t.Ax≤bs.t.yA≥C以对称形式为基础，很容易记住。⎨⎩x≥0y≥0对称形式：互为对偶(LP)maxz=cx(DP)minw=bTy此处，yyy=(,,......,y)为行向量。s.t.Ax≤bs.t.ATy≥cT12mx≥0y≥0写黑板112原问题（对偶问题）对偶问题（原问题）举例说明：maxz=cxminw=bTy设原规划中第一个约束为等式：n个变量n个约束ax+…
6、+ax=bx≥0ay+ay+…+ay≥c1111nn1j1j12j22jmjxj≤0a1jy1+a2jy2+…+a2jym≤cj那么，这个等式与下面两个不等式等价xj无约束a1jy1+a2jy2+…+a2jym=cjm个约束m个变量a11x1+…+a1nxn≥b1ai1x1+ai2x2+…+ainxn≤biyi≥0a11x1+…+a1nxn≤b1ai1x1+ai2x2+…+ainxn≥biyi≤0ai1x1+ai2x2+…+ainxn=biyi无约束1314此时已转化为对称形式，直接写出对偶规划这样，原规划模
7、型可以写成'''minwbybyby=−++...+by111122mmmaxzcx=++...cx'''11nn⎧ayayay−++...+≥ayc111111212mm11⎧ax++...axb≤⎪'''1111nn1⎪ayayay121−121++222...+≥aymm2c2⎪⎪−−ax...−≤ax−bst..⎨@⎪1111nn1⎪⎪ayayay''−'++...+≥aycst..⎨@⎪11nnn1122mnmn'''⎩⎪yyy,,,...,y≥0⎪ax++...axb≤112mmm11nnm⎪⎪x
8、≥=0,jm1,2,...,这里，把y看作是y=y’-y’’，于是y没有非负⎩j11111限制。1516§2.对偶问题的基本性质系数变成约束条件右侧值以对称形式的对偶为例例2.1写出右最小化问题：minz=x−x−x边线性规划问123⎧−x1−x2−2x3≥−25(LP)Maxz=∑j=1,2,…,ncjxj题的对偶问⎪变成目标函⎪−x1+2x2−x3≥2数的系数s.t.∑ax≤b,i=1,2,…,
