《管理运筹学》第3章--线性规划的对偶问题.ppt
《《管理运筹学》第3章--线性规划的对偶问题.ppt》由会员分享,可在线阅读,更多相关《《管理运筹学》第3章--线性规划的对偶问题.ppt(37页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、OR:SM2第一节第一节 线性规划的对偶理论线性规划的对偶理论第二节第二节 对偶单纯形法对偶单纯形法OR:SM3 每一个线性规划问题都有一个与之相伴随的另一个问题。每一个线性规划问题都有一个与之相伴随的另一个问题。这两个问题:一是,在数学模型上有着对应关系;二是,从这两个问题:一是,在数学模型上有着对应关系;二是,从一个问题的最优解完全可以得出另一个问题最优解的全部信一个问题的最优解完全可以得出另一个问题最优解的全部信息。息。 3.1.1 3.1.1 问题的提出问题的提出 例例1 引入一个资源价格问题。引入一个资源价格问题。OR:SM4某企业生产甲、乙两种某企业生产甲、乙两种产品,需消耗产品,
2、需消耗A A、B B、C C三种材料。据市场分析,单位甲、乙三种材料。据市场分析,单位甲、乙产品的销售收益分别为产品的销售收益分别为4 4万元和万元和5 5万元。单位甲、乙产品对万元。单位甲、乙产品对材料的消耗量及材料的供应量如表材料的消耗量及材料的供应量如表3.13.1所示。所示。 原问题:原问题:应如何制定生产计划,使总收益为最大。应如何制定生产计划,使总收益为最大。 表表3.13.1 产品材料 甲乙供应量供应量A1145B2180C1390收益收益4万元万元/单甲单甲5万元万元/单乙单乙OR:SM51212121212max( )4545280s.t.(31)390,0Z xxxxxxx
3、xxxx设计划安排:设计划安排:x x1 1为甲产品的产量,为甲产品的产量, x x2 2为乙产品的产量。(决策变量)为乙产品的产量。(决策变量)则,该问题的数学模型为:则,该问题的数学模型为:1245/ 2,45/ 2( )405/ 2xxZ xOR:SM6 新问题:新问题:现在从另一角度来讨论这个问题。现在从另一角度来讨论这个问题。 假设该企业经过市场预测,准备进行转产,且把现有三假设该企业经过市场预测,准备进行转产,且把现有三种材料进行转让,也恰好有一个制造商急需这批材料。于是种材料进行转让,也恰好有一个制造商急需这批材料。于是买卖双方开始对资源的出让价格问题进行磋商,希望寻找一买卖双方
4、开始对资源的出让价格问题进行磋商,希望寻找一个双方都认为比较满意的合理价格。个双方都认为比较满意的合理价格。 分析:分析:设设A、B、C三种材料的单价分别为三种材料的单价分别为y1、y2、y3. 对于卖方来说,对于卖方来说,生产单位甲产品所获收益为生产单位甲产品所获收益为4万元,为万元,为保证其总收入不少于保证其总收入不少于405/2万元,则将生产单位甲产品所需资万元,则将生产单位甲产品所需资源转让出去,该企业的收入不能少于源转让出去,该企业的收入不能少于4万元。故万元。故y1、y2、y3必必须满足约束条件:须满足约束条件: y1+2y2+y34 同样,将生产单位乙产品所需的资源转让出去,其收
5、入同样,将生产单位乙产品所需的资源转让出去,其收入不能少于生产单位乙产品的收益不能少于生产单位乙产品的收益5万元,所以万元,所以y1、y2、y3还必还必须满足约束条件:须满足约束条件: y1+y2+3y35OR:SM7 对于买方来说,对于买方来说,他希望在满足上述约束条件下使总的他希望在满足上述约束条件下使总的支出支出 W(y) =45y1+80y2+90y3 达到最小。达到最小。 综上所述,资源价格问题的数学模型可描述为:综上所述,资源价格问题的数学模型可描述为: 123123123123min( )45809024s.t.35(32),0W yyyyyyyyyyyyy 上述两个模型(上述两
6、个模型(3-1)和()和(3-2)是对同一问题的两种不)是对同一问题的两种不同考虑的数学描述,其间有着一定的内在联系,将逐一剖同考虑的数学描述,其间有着一定的内在联系,将逐一剖析。析。OR:SM8 首先,分析这两个模型之间的对应关系:首先,分析这两个模型之间的对应关系: (1 1)一个问题的目标函数为极大化,约束条件为)一个问题的目标函数为极大化,约束条件为“”类类型,另一个问题的目标为极小化,约束条件为型,另一个问题的目标为极小化,约束条件为“”类型;类型; (2 2)一个问题的变量个数等于另一个问题的约束条件个)一个问题的变量个数等于另一个问题的约束条件个数;数; (3 3)一个问题的右端
7、常数(约束系数)是另一个问题的)一个问题的右端常数(约束系数)是另一个问题的目标函数的系数(成本系数);目标函数的系数(成本系数); (4 4)两个问题的系数矩阵互为转置。)两个问题的系数矩阵互为转置。 我们把这种对应关系称为我们把这种对应关系称为对偶关系对偶关系。如果把(。如果把(3-13-1)称为)称为原始问题,则(原始问题,则(3-23-2)称为对偶问题。)称为对偶问题。OR:SM9 3.1.2 3.1.2 对称型线性规划问题对称型线性规划问题对称型对偶问题对称型对偶问题 每一个线性规划问题都必然有与之相伴随的对偶问每一个线性规划问题都必然有与之相伴随的对偶问题存在。先讨论对称型对偶问题
8、;对于非对称型对偶问题存在。先讨论对称型对偶问题;对于非对称型对偶问题,可以先转化为对称型,然后再进行分析,也可以直题,可以先转化为对称型,然后再进行分析,也可以直接从非对称型进行分析。接从非对称型进行分析。 对称型线性规划问题对称型线性规划问题数学模型的一般形式为数学模型的一般形式为11221111221121122222112212max( )s.t.(33),0nnnnnnmmmnnmnZ xc xc xc xa xa xa xba xa xaxbaxaxaxbx xxY1Y2ymOR:SM10 这种模型的特点是:这种模型的特点是: (1 1)目标函数是最大化类型)目标函数是最大化类型(
9、 (或是最小化类型或是最小化类型) ); (2 2)所有约束条件都是)所有约束条件都是“”型(或都是型(或都是“”型);型); (3 3)所有决策变量都是非负的。)所有决策变量都是非负的。 如果把(如果把(3-33-3)作为原始问题,根据原始与对偶问题)作为原始问题,根据原始与对偶问题的对应关系可得(的对应关系可得(3-33-3)的对偶问题为)的对偶问题为11221112121112122222112212min( )s.t.(34),0mmmmmmnnmnmnmW yb yb yb ya ya ya yca ya yayca ya yaycy yyOR:SM11 用矩阵表示的原始问题(用矩阵
10、表示的原始问题(3-33-3)和对偶问题()和对偶问题(3-43-4)为)为 其中其中Y=Y=(y y1 1,y,y2 2,y,ym m), ,其它同前其它同前。 3.1.3 3.1.3 一般问题的对偶问题一般问题的对偶问题非对称型对偶问题非对称型对偶问题 线性规划有时以非对称型出现,那么如何从原始问题写线性规划有时以非对称型出现,那么如何从原始问题写出它的对偶问题呢?出它的对偶问题呢?max( )s.t.0Z xCXAXbXmin( )s.t.0WyYbYACYOR:SM12 例例1 写出下列线性规划的对偶问题写出下列线性规划的对偶问题2313123123123m ax()252266s.t
11、.30,0ZxxxxxxxxxxxxxxOR:SM13 转换成转换成对称型对称型123123123123123123m ax()02502266s.t.3030,0Zxxxxxxxxxxxxxxxxxxx Y1Y2Y/3y/333/1233/1233/123/1233/123min( )26002002s.t.6335,0Wyyyyyyyyyyyyyyyyyyyyy OR:SM14 再设再设y y/ /3 3-y-y/3 3=y=y3 3,代入上述模型得,代入上述模型得:123123123123123min( )2602002s.t.635,0;?Wyyyyyyyyyyyyyyyy OR:SM
12、15 例例2 2 将例将例1 1模型中的模型中的x x2 2改为无非负约束变量,即模型为改为无非负约束变量,即模型为 写出其对偶问题写出其对偶问题2313123123132m ax( )252266s.t.30,0;?ZxxxxxxxxxxxxxxOR:SM16 令令x2=x2-x2. .其中其中x2,x20 转换成转换成对称型对称型222/ /123/ /123/ /1223/ /1223/ /1223/ /123m ax()0225002266s.t.3030,0Zxxxxxxxxxxxxxxxxxxxxxxxxx Y1Y2Y/3y/3OR:SM1733/1233/1233/123/123
13、3/1233/123min( )26002002s.t. 026335,0W yyyyyyyyyyyyyyyyyyyyyyyyy 123123123123123min( )2602002s.t.635,0,?Wyyyyyyyyyyyyyyyy OR:SM18 综合上述两个例子,可以看出,线性规划与其对偶模型综合上述两个例子,可以看出,线性规划与其对偶模型的关系有了新的拓展:的关系有了新的拓展: (1 1)一个问题的目标函数为极大化,约束条件为)一个问题的目标函数为极大化,约束条件为“”或或“=”=”类型,另一个问题的目标为极小化,约束条件为类型,另一个问题的目标为极小化,约束条件为“”或或“=
14、”=”类型;类型; (2 2)一个问题的变量个数等于另一个问题的约束条件个)一个问题的变量个数等于另一个问题的约束条件个数;数; (3 3)一个问题的右端常数(约束系数)是另一个问题的)一个问题的右端常数(约束系数)是另一个问题的目标函数的系数(成本系数);目标函数的系数(成本系数); (4 4)两个问题的系数矩阵互为转置)两个问题的系数矩阵互为转置; ; (5 5)一个问题的第)一个问题的第i i个约束为个约束为“=”=”,则另一个问题的第,则另一个问题的第i i个变量为个变量为“无非负约束变量无非负约束变量”(自由变量)。反之,一个问(自由变量)。反之,一个问题的第题的第i i个变量为个变
15、量为“无非负约束变量无非负约束变量”,则另一个问题的第,则另一个问题的第i i个约束为个约束为“=”=”(方程)。(方程)。OR:SM19原始问题原始问题(或对偶问题或对偶问题)对偶问题对偶问题(或原问题或原问题) 目标目标 max 目标目标 min 变量变量 n个个 约束约束 n个个 变量变量 0 0 无非负约束无非负约束 约束约束 =(方程)(方程) 约束约束 m个个 变量变量 m个个 约束约束 = (方程)(方程) 变量变量 0 0 无非负约束无非负约束系数矩阵系数矩阵bc转置转置cbOR:SM20 这样对于任意给定的一个线性规划问题,均可依据上述这样对于任意给定的一个线性规划问题,均可
16、依据上述对应关系对应关系直接写出其对偶问题模型直接写出其对偶问题模型,而无须先化成对称型。,而无须先化成对称型。 例例3 3 写出下列线性规划的对偶问题写出下列线性规划的对偶问题123123123123123m ax()221s.t.220;,?Zxxxxxxxxxxxxxxxx解:解:因目标函数为因目标函数为“max”max”类型,则约束条件应为类型,则约束条件应为“”和和“=”=”类型,故只需改变第三个约束条件的不等号方向,类型,故只需改变第三个约束条件的不等号方向,即有:即有:12322xxx OR:SM21 这样所有的约束条件均为这样所有的约束条件均为“”和和“=”类型,按前述对类型,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 管理运筹学 管理 运筹学 线性规划 对偶 问题
限制150内