资源描述：
《《修正对偶》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、3.9线性规划的对偶问题第三章线性规划1对偶问题的提出4对偶单纯形法2对偶规划的形式3.8修正单纯形法3对偶定理MaxZ=CXs.t.AX=bX≥0σj=CBTB-1pj-cj3.8修正单纯形法（1）检验数：（2）基变量值：（3）主列元素：定理3.8.1设在单纯形法某次迭代中的可行基为B，作了{r,s}旋转基变换后，则下一个新基的逆为,其中改进单纯形法的计算步骤（1）求单纯形乘子：（2）计算：若则停，得最优解否则转（3）σj=CBTB-1pj-cj（3）计算向量：若所有，则停，无最优解；否则转（4）
2、（4）计算：（5）形成变换矩阵：Ers（6）计算：以代，以代，转（1）例MaxZ=x1＋2x2-x3S.t.x1＋x2+x3≤4-x1+2x2-2x3≤62x1+x2≤5x1,x2,x3≥0解MaxZ=x1＋2x2-x3S.t.x1＋x2+x3+x4＝4-x1+2x2-2x3+x5＝62x1+x2+x6＝5x1,x2,x3x4,x5,x6≥0111100-12-2010210001（1）（2）S=2（3）第一次迭代（4）（5）（6）令转(1)第二次迭代（1）（2）S=1,转(3)（3）计算（4）（5
3、）（6）令转(1)第三次迭代（1）（2）例:某工厂要安排生产甲、乙两种产品.生产单位产品所需设备台时及A,B两种原材料的消耗量，每件产品可以获得的利润以及设备可利用的时数,可用的原材料如下表所示：1、对偶问题的提出：产品甲产品乙设备能力设备128台时原材料A4016kg原材料B0412kg利润（百元/件）233.9线性规划的对偶问题若有一公司有一订单要生产甲、乙两种产品,需要向工厂租用设备.公司决策者就要考虑给每种设备如何定价,才最有竞争力？Maxz=2x1+3x2s.t.x1+2x2≤84x1≤1
4、64x2≤12x1,x2≥0x1x2Ox1+2x2=8x1=4x2=82x1+3x2=CA(4,2)Minf=8y1+16y2+12y3设y1，y2，y3分别为出租单位设备台时和出让原材料A、B的费用。Maxz=2x1+3x2s.t.x1+2x2≤84x1≤164x2≤12原问题x1,x2≥0s.t.y1+4y2≥2（不少于甲产品的利润）2y1+4y3≥3（不少于乙产品的利润）y1,y2,y3≥0对偶问题Maxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn≤b1a
5、21x1+a22x2+…+a2nxn≤b2…………am1x1+am2x2+…+amnxn≤bmx1，x2，…，xn≥02、对偶规划的形式(1)对称形式的对偶关系(规范型的线性规划)Minf=b1y1+b2y2+…+bnyms.t.a11y1+a21y2+…+am1ym≥c1a12y1+a22y2+…+am2ym≥c2…………a1ny1+a2ny2+…+amnym≥cny1，y2，…，ym≥0一对对称形式的对偶规划之间具有下面的对应关系。原问题记为LP,对偶问题记为DPLP问题为目标最大化，DP问题为
6、最小化;LP问题的约束为“≤”,DP问题的约束为“≥”;LP的价值系数ci,在DP问题中恰好为约束右端项;LP的约束右端项bi,在DP问题中恰好为价值系数;LP中的每个约束条件对应着DP问题中的一个变量,而LP中的每个决策变量对应着DP问题中的一个约束;Maxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn≤b1a21x1+a22x2+…+a2nxn≤b2…………am1x1+am2x2+…+amnxn≤bmx1，x2，…，xn≥0Minf=b1y1+b2y2+…+b
7、nyms.t.a11y1+a21y2+…+am1ym≥c1a12y1+a22y2+…+am2ym≥c2…………a1ny1+a2ny2+…+amnym≥cny1，y2，…，ym≥01)2)3)4)5)(LP)Maxz=CTXs.t.AX≤bX≥0Maxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn≤b1a21x1+a22x2+…+a2nxn≤b2…………am1x1+am2x2+…+amnxn≤bmx1，x2，…，xn≥0Maxf=b1y1+b2y2+…+bmyms.
8、t.a11y1+a21y2+…+am1ym≥c1a12y1+a22y2+…+am2ym≥c2…………a1ny1+a2ny2+…+amnym≥cmy1，y2，…，ym≥0LP与DP的矩阵的形式(DP)Minf=bTys.t.ATy≥Cy≥0(2)非对称形式的对偶关系Maxz=2x1+4x2s.t.x1+x2=1-3x1+2x2≤3x1,x2≥0Maxz=2x1+4x2s.t.x1+x2≤1-x1-x2≤1-3x1+2x2≤3Miny1-y2+3y3s.t.y1-y2-3
