对偶问题和对偶单纯形法

《对偶问题和对偶单纯形法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第七章对偶问题和对偶单纯形法一、问题的提出二、对偶问题和原问题的转换三、对偶规划的性质四、对偶单纯形法五、交替单纯形法一、问题的提出原问题：a和b产量各为多少可以使利润最大？25010C40012B30011A资源限量ba产品设备10050利润一、问题的提出原LP模型：Maxz=50x1+100x2s.t：1·x1+1·x2≤3002·x1+1·x2≤4000·x1+1·x2≤250x1≥0，x2≥0一、问题的提出若考虑将三种设备出租，如何合理确定各设备的租金y1、y2、y3（元/台时）？目标函数：minz=30

2、0y1+400y2+250y3约束条件：y1+2y2≥50y1+y2+y3≥100y1、y2、y3≥0一、问题的提出这样两个线性规划问题就是一对对偶问题。称其中一个为原问题（LP问题），另一个为对偶问题（DLP问题）。由于它们内在的联系，可以根据其中一个模型，写出其对偶问题的模型。二、对偶问题和原问题的转换LP问题和DLP问题的关系：规范形(LP)Maxz=cTxs.t.Ax≤bx≥0(DLP)Minf=bTys.t.ATy≥cy≥0二、对偶问题和原问题的转换1、对于规范型，直接按对应关系转换例：Maxz=20x1+8

3、x2+6x3s.t：8x1+3x2+2x3≤2502x1+x2≤504x1+3x3≤150x1，x2，x3≥0写出该线性规划问题的对偶问题。二、对偶问题和原问题的转换则对偶问题为：Minf=250y1+50y2+150y3s.t：8y1+2y2+4y3≥203y1+y2≥82y1+3y3≥6y1，y2，y3≥0二、对偶问题和原问题的转换2、对于非规范形式，先化为规范形式例：写出线性规划模型的对偶问题Minz=3x1+4x2+6x3s.t：x1+3x2-2x3+x4＝252x1+7x3+2x4≥602x1+2x2-

4、4x3≤30x1，x2，x4≥0，x3无非负约束二、对偶问题和原问题的转换首先转换为规范形Minz=3x1+4x2+6x3变为Max(-z)=-3x1-4x2-6x3约束条件x1+3x2-2x3+x4＝25等同于x1+3x2-2x3+x4≤25和x1+3x2-2x3+x4≥25联立二、对偶问题和原问题的转换2x1+7x3+2x4≥60可转化为-2x1-7x3-2x4≤-60x3无非负约束，则令x3＝x3’-x3’’x3’-x3’’≥0则原LP模型可以化为规范形：二、对偶问题和原问题的转换Max(-z)=-3x1-4x2

5、-6x3’+6x3’’s.t：x1+3x2-2x3’+2x3’’+x4≤25-x1-3x2+2x3’-2x3’’-x4≤-25-2x1-7x3’+7x3’’-2x4≤-602x1+2x2-4x3’+4x3’’≤30x1,x2,x3’,x3’’,x4≥0二、对偶问题和原问题的转换故DLP可写出：Minf＝25y1-25y2-60y3+30y4s.t：y1-y2-2y3+2y4≥-33y1-3y2+2y4≥-4-2y1+2y2-7y3-4y4≥-62y1-2y2+7y3+4y4≥6y1-y2-2y3≥0y1，y2，y3，y

6、4，y5≥0二、对偶问题和原问题的转换将DLP模型整理可得：Minf＝25y5+60y3+30y4s.t：y5+2y3+2y4≥-33y5+2y4≥-4-2y5+7y3-4y4＝-6y5+2y3≥0y5无非负约束，y3≤0，y4≥0LP与DLP的一般对应关系原问题LP对偶问题DLP目标函数maxzminf目标函数变量xj（j＝1，2……n）n个n个约束条件j（j＝1，2……n）≥0≥≤0≤无约束＝约束条件i（i＝1，2……m）m个m个变量yj（i＝1，2……m）≤≥0≥≤0＝无约束目标函数变量的系数cj（j＝1，2……

7、n）约束条件右端项cjT（j＝1，2……n）约束条件右端项bi（i＝1，2……m）目标函数变量的系数biT（i＝1，2……m）练习写出下面LP问题的DLP模型Minz=x1+2x2+5x3s.t：2x1+3x2+x3＝103x1+x2+x3≥50x1+x3≤20x1≥0，x2≤0，x3无非负约束三、对偶规划的性质1、对称性：对偶问题的对偶是原问题。2、弱对偶性：若X是原问题（max）的可行解，Y是对偶问题（min）的可行解，则存在CX≤bTY三、对偶规划的性质推论a：原问题任一可行解的目标函数值是其对偶问题目标函数值的

8、下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。推论b：若原问题解无界，则其对偶问题无可行解；若对偶问题解无界，则原问题无可行解。（逆命题不成立）推论c：若原问题有可行解而对偶问题无可行解，则原问题无界；反之，对偶问题有可行解而原问题无可行解，则对偶问题解无界。三、对偶规划的性质3、最优性：若x,y分别是原问题