运筹学概论第2章线性规划的对偶理论

《运筹学概论第2章线性规划的对偶理论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章线性规划的对偶理论线性规划的对偶问题对偶问题的基本性质影子价格第一节线性规划的对偶问题窗含西岭千秋雪，门泊东吴万里船对偶是一种普遍现象例1美佳公司计划制造甲、乙两种家电产品，已知制造一件甲需占用B设备5小时，调试工序1小时；制造一件乙需占用A设备6小时，B设备2小时，调试工序1小时；A设备每天可用15小时，B设备可用24小时，调试工序每天可用5小时。已知售出一件甲获利2元，售出一件乙获利1元，问该公司每天应制造两种家电各多少件，使获取的利润最大？例2假设某个公司想把美佳公司的资源购买过来，他至少应付多大的代价，才能使美佳公司愿意放弃生产活动，出让

2、自己的资源。对偶问题原问题一、对偶问题的提出二、对称形式下对偶问题的一般形式用矩阵形式表示：●任何线性规划问题都有其对偶问题●对偶问题有其明显的经济含义例3假设有商人要向厂方购买资源A和B，问他们谈判原料价格的模型是怎样的？●设A、B资源的出售价格分别为y1和y2●显然商人希望总的收购价越小越好(目标)●工厂希望出售资源后所得不应比生产产品所得少（约束）原问题对偶问题A约束系数矩阵其约束系数矩阵的转置b约束条件的右端项目标函数中的价值系数向量C目标函数中的价值系数向量约束条件的右端项向量目标函数Maxz=CXMinw=Y’b约束条件AXbA’YC’

3、决策变量X0Y0对偶问题的对偶即原问题。同样，可以将对偶问题当作原问题，写出其对偶问题。课堂练习：三、非对称形式的原-对偶问题关系转换为对偶问题的思路是：先将其转化成对称形式，再按对应关系来写。因例中目标函数为max，故约束条件应换为“”号，所有的变量均应“0”，-3x1+x2-6x3-1x1+x2+x34-x1-x2-x3-4x2’=-x2；x3=x3’-x3’’y2=-y2’；y3=y3’-y3’’；（3）式两端乘“-1”，（4）、（5）合并。解：设对偶变量为y1,y2,y3,对偶问题模型为：Maxw=5y1+4y2+6y3y1+2y

4、2y1+y3-3y1+2y2+y3y1-y2+y3≥2≤3≤-5=1y1≥0,y2≤0,y3无约束≤2≥课堂练习：第二章线性规划的对偶理论线性规划的对偶问题对偶问题的基本性质影子价格第二节对偶问题的基本性质为了便于讨论，下面不妨总是假设：原线性规划问题的矩阵表达式加上松弛变量后为：一、单纯形法的矩阵描述上式中Xs为松弛变量，，I为m×m单位矩阵。Cjc1c2cn000CBXBbx1x2xnxn+1xn+2xn+m0xn+1b1a11a12a1n1000xn+2b2a21a22a2n0100xn+mbmam1am2

5、amn001cj-zjc1c2cn000非基变量基变量XBXNXS0XSbBNICj-zjCBCN0单纯形法计算时，总选取I为初始基，对应基变量为Xs。设迭代若干步后，基变量为XB，在初始单纯形表中的系数矩阵为B。B将在初始单纯形表中单独列出，而A中去掉若干列后剩下的列组成矩阵N，这样初始单纯形表可列成如下形式。非基变量基变量XBXNXS0XSbBNICj-zjCBCN0当迭代若干步后，基变量为XB时，则该步的单纯形表中由XB系数组成的矩阵为I。又因单纯形法的迭代是对约束增广矩阵进行的行的初等变换，对应XS的系数矩阵在新表中应为B-1。故当基变

6、量为XB时，新的单纯形表具有如下形式。基变量非基变量XBXNXSCBXBB-1bIB-1NB-1Cj-zj0CN-CBB-1N-CBB-1当迭代后基变量为XB时，其在初始单纯形表中的系数矩阵为B，则有：（1）对应初始单纯形表中的单位矩阵I，迭代后的单纯形表中为B-1（2）初始单纯形表中基变量Xs=b，迭代后的表中XB=B-1b（3）初始单纯形表中约束系数矩阵为，迭代后的表中约束系数矩阵为(B-1左乘):非基变量基变量XBXNXS0XSbBNICj-zjCBCN0基变量非基变量XBXNXSCBXBB-1bIB-1NB-1Cj-zj0CN-CBB-1N-C

7、BB-1（4）若初始矩阵中变量Xj的系数向量为Pj，迭代后为，则有:（5）当B为最优基时，应有:这时从检验数行看出，若取其相反数恰好是其对偶问题的一个可行解。将这个解代入对偶问题的目标函数值，有：因XB的检验数可写为:则有称为单纯形乘子，若令基变量非基变量XBXNXSCBXBB-1bIB-1NB-1Cj-zj0CN-CBB-1N-CBB-1XN的检验数XS的检验数XB的检验数所以XA的检验数例1两个互为对偶的线性规划问题，两者分别加上松弛和剩余变量后为：二、原规划与对偶规划问题的变量及解之间的对应关系两个问题的最终单纯形表见下页：原问题变量松弛变量x1

8、x2x3x4x5x315/20015/4－15/2x17/21001/4－1/2x23/201