资源描述：
《ch2线性规划对偶理论与灵敏度分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章线性规划对偶理论与灵敏度分析教学时数：6学时教学目的与要求：理解线性规划对偶问题理论与影子价格概念,掌握对偶单纯形法及灵敏度分析技巧教学内容：1.线性规划对偶问题及相关理论2.影子价格3.对偶单纯形法4.灵敏度分析及参数规划教学重点：影子价格及灵敏度分析教学难点：对偶理论第六节参数线性规划（简介）第一节线性规划的对偶问题第二节对偶问题的基本性质第三节影子价格第四节对偶单纯形法第五节灵敏度分析第二章讲授内容和知识第一节线性规划的对偶问题一、对偶问题的提出二、对称形式的原始-对偶关系三、非对称形式的原始-对偶问题四、
2、原始-对偶关系一览表例2.1.1生产计划问题。某企业生产A、B、C三种畅销产品，每一件产品所需要的资源和收益列于表中：表1资源甲资源乙资源丙资源丁每件收益（元）产品A32112000产品B41324000产品C2234资源限量600400300200问：如何安排生产，可以使总利润最大？解：利用第一章的知识，设三种产品的生产量分别为x1，x2和x3，可以建立线性规划模型如下:一、对偶问题的提出3000maxz=2000x1+4000x2+3000x33x1+4x2+2x3≤6002x1+x2+2x3≤400x1+3x2+
3、3x3≤300x1+2x2+4x3≤200x1,x2,x3≥0假如企业不进行生产，而是把全部可利用的资源转让给其他企业。此时，企业必须考虑一个合适的资源价格，使得：1.有企业愿意接受转让；2.企业自身没有经济损失。设四种资源的价格确定为y1,y2,y3,y4。y1y2y3y4而企业自身没有经济损失的要求可做如下思考：生产一件产品，比如A，需要四种资源的量分别为3，2，1，1个单位。由于要把生产A产品的这些资源卖出去，所以，单件总卖值不应比企业自己生产时的收益（2000）低，即，3y1+2y2+y3+y4≥2000对产品
4、B：4y1+y2+3y3+2y4≥4000对产品C：2y1+2y2+3y3+4y4≥3000则有企业愿意接受转让的条件是极小化资源总价，即w=600y1+400y2+300y3+200y4minw=600y1+400y2+300y3+200y43y1+2y2+y3+y4≥20004y1+y2+3y3+2y4≥40002y1+2y2+3y3+4y4≥3000y1,y2,y3,y4≥0maxz=2000x1+4000x2+3000x33x1+4x2+2x3≤6002x1+x2+2x3≤400x1+3x2+3x3≤300x1
5、+2x2+4x3≤200x1≥0,x2≥0,x3≥0原问题对偶问题两个线性规划问题的比较中，可以初步发现：原问题的目标函数求极大，对偶问题的目标函数求极小；原问题目标函数中的系数在对偶问题中变为约束条件的右端常数项；约束条件的不等式方向改变了；约束方程的系数矩阵发生了转置；原问题约束数目与对偶问题的变量数相等。对称形式的条件：（1）变量全部具有非负约束；（2）目标函数求极大值时，约束不等式符号全部为≤；目标函数为求极小值时，约束不等式的符号全部为≥。……maxz=c1x1+c2x2+…+cnxnst.a11x1+a12
6、x2+…+a1nxn≤b1a21x1+a22x2+…+a2nxn≤b2am1x1+am2x2+…+amnxn≤bmx1,x2,…,xn≥0(2-1)对偶问题的一般形式为：二、对称形式的原始-对偶关系minw=b1y1+b2y2+…+bmyma11y1+a21y2+…+am1ym≥c1a12y1+a22y2+…+am2ym≥c2……a1ny1+a2ny2+…+amnym≥cny1,y2,…,ym≥0……maxz=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn≤b1a21x1+a22x2+…+a2n
7、xn≤b2am1x1+am2x2+…+amnxn≤bmx1,x2,…,xn≥0原问题：maxz=CXAX≤bX≥0对偶问题：minw=YbYA≥CY≥0Y=(y1,y2,…,ym)x1x2…xnxjy1y2：ymyia11a12…a1na21a22…a2n：：am1am2…amn原始约束≤≤：≤对偶：极小化w对偶约束原始极大化z≥≥…≥b1b2：bmc1c2…cn说明：表2的变量行与参数行相乘组成原始问题的约束条件和目标函数；表2的变量列与参数列相乘组成对偶问题的约束条件和目标函数。maxz=2000x1+4000x2
8、+3000x33x1+4x2+2x3≤6002x1+x2+2x3≤400x1+3x2+3x3≤300x1+2x2+4x3≤200x1≥0,x2≥0,x3≥0y1y2y3y4Minw=y1+y2+y3+y4y1+y2+y3+y4y1,y2,y3,y4y1+y2+y3+y4y1+y2+y3+y460040030020020004000
