资源描述：
《运筹学第二章线性规划的对偶理论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、运筹学基础1第二章线性规划对偶问题的提出原问题与对偶问题的关系对偶问题的基本性质对偶单纯形法灵敏度分析2运筹学基础解：设生产x1的产品I，x2的产品II，则目标函数maxz＝2x1+3x2约束条件x1+2x2≤84x1≤164x2≤12x1﹑x2≥0线性规划的对偶理论例1某厂可生产产品Ⅰ和Ⅱ，生产I需1台设备，4单位原料A，生产II需2台设备，4单位原料B。该厂每生产一件产品Ⅰ获利2元﹐每生产一件产品Ⅱ获利3元。现有8台设备，16单位原料A，12单位原料B，问如何安排计划使获利最多?运筹学基础3第二章线性规划对
2、偶问题的提出原问题与对偶问题的关系对偶问题的基本性质对偶单纯形法灵敏度分析44.1对偶问题的提出运筹学基础我们从另一个角度来讨论这个问题：假设不生产产品Ⅰ﹑Ⅱ，而将所有资源出租或外售。问题：考虑每种资源如何定价。54.1对偶问题的提出运筹学基础例1产品Ⅰ：1台设备，4单位原料A，获利2元；产品Ⅱ：2台设备，4单位原料B，获利3元。现有：8台设备，16单位原料A，12单位原料B设y1，y2，y3分别表示出售单位设备台时的租金和出让原材料A，B的附加额。根据题意可得：y1+4y2≥2，2y1+4y3≥3，ω=8y1
3、+16y2+12y3要实现出租的愿望，只能在满足≥所有产品的利润条件下，必须使ω尽可能的小。64.1对偶问题的提出运筹学基础为此需解决如下的线性规划问题：y1+4y2≥22y1+4y3≥3minω=8y1+16y2+12y2y1，y2，y3≥0maxz＝2x1+3x2x1＋2x2≤84x1≤164x2≤12x1﹐x2≥0与关系？对原模型设：124004A=C=(2，3)b=(8,16,12)TX=（x1，x2）TY=（y1，y2，y3）则可得:74.1对偶问题的提出运筹学基础maxz=CXAX≤b（5.1）X≥
4、0y1+4y2≥22y1+4y3≥3minω=8y1+16y2+12y3y1，y2，y3≥0maxz＝2x1+3x2x1＋2x2≤84x1≤164x2≤12x1﹐x2≥0与有何关系？对愿模型设：124004A=C=(2，3)b=(8,16,12)TX=（x1，x2）TY=（y1，y2，y3）则可得:minω=YbYA≥C（5.2）Y≥0和我们把（5.2）式的问题称为（5.1）式问题的对偶线性规划问题。运筹学基础8第二章线性规划对偶问题的提出原问题与对偶问题的关系对偶问题的基本性质对偶单纯形法灵敏度分析94.2原
5、问题与对偶问题的关系运筹学基础1﹒对称式的对偶“≤”不等式约束条件的原问题与“≥”不等式约束条件的对偶问题，称为对称式的一对对偶问题。原问题：maxz=c1x1+c2x2+…+cnxna11a12…a1nam1am2…amn·········x1xn···b1bm···≤x1，x2，…，xn≥0对偶问题：minω=b1y1+b2y2+…+bmyma11a12…a1nam1am2…amn·········≥y1，y2，…，ym≥0(y1,y2,…,ym)(c1,c2,…,cn)n个变量，m个约束条件m个变量，n个
6、约束条件10运筹学基础2﹒约束条件全部为“=”的对偶maxz=CXAX＝bX≥0原问题：maxz=CXAX≤bX≥0AX≥b等价maxz=CXAX≤bX≥0－AX≤－bmaxz=CXX≥0A－AX≤b－bminω=(Y1,Y2)Y1,Y2≥0A－A≥Cb－b(Y1,Y2)其中Y1=(y1,y2,…ym)，Y2=(ym+1,ym+2,…y2m)等价等价minω=YbY为无约束YA≥Cminω=(Y1－Y2)bY1,Y2≥0(Y1－Y2)A≥C令Y=(Y1－Y2)对偶问题对偶问题114.2原问题与对偶问题的关系运筹
7、学基础3﹒约束条件为“≥”的对偶maxz=CXAX≥bX≥0原问题：maxz=CX－AX≤－bX≥0minω=Y1(－b)Y1(－A)≥CY1≥0minω=YbYA≥CY≤0等价对偶问题令Y=－Y1对偶问题12运筹学基础4﹒变量≤0的对偶maxz=CXAX≤bX≤0原问题：令X=－X1maxz=C(－X1)A(－X1)≤bX1≥0maxz=(－C)X1(－A)X1≤bX1≥0minω=YbY(－A)≥－CY≥0minω=YbYA≤CY≥0对偶问题对偶问题等价13运筹学基础5﹒变量无约束的对偶maxz=CXAX≤
8、bX无约束原问题：令X=X1－X2X1，X2≥0maxz=CX1－CX2X1,X2≥0AX1－AX2≤bmaxz=(C,－C)X1,X2≥0≤bX1X2(A,－A)X1X2等价minω=YbY≥0Y(A,－A)≥(C,－C)对偶minω=YbYA≥CY≥0－YA≥－Cminω=YbYA＝CY≥0minω=YbYA≥CY≥0YA≤C等价等价等价对偶问题14运筹学基础6﹒原问题与对偶问题的
