运筹学-第三章-LP对偶

《运筹学-第三章-LP对偶》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第三章线性规划对偶理论§3-1对偶问题的提出§3-2写对偶问题§3-3对偶问题的性质§3-4对偶单纯形方法制作与教学河北工业大学管理学院孔造杰kongzj@sina.comExit2003年9月13日12时20分§3-1对偶问题的提出1.从经济意义上提出对偶问题仍以第一章的例1-1为例，假若企业的决策者除了生产产品甲、乙之外，还有其它可选方案来利用其设备资源。例如，承接外加工或租赁设备，作为决策者就要考虑设备台时定价的问题，即在何种台时价格的前提下接受外加工或租赁设备以取代生产甲乙两种产品。若以y1,y2,y

2、3分别表示设备A、B、C每台时的价格（加工费或租金），这时就要与自己生产产品甲乙作一比较，因为每生产1件产品甲可得2元的利润，每生产1件产品乙可得利润3元，那么，如果用于生产一件产品甲的各设备台时用于外加工所得的收益不低于2元，同样，用于生产一件产品乙的各设备台时用于外加工所得的收益不低于3元，则将设备用于外加工（或租赁）；否则，就用于生产甲乙两种产品。根据以上分析和第一章例1-1的条件，我们得到关系式：y+4y+0y≥21232y+0y+4y≥3123河北工业大学管理学院孔造杰制作Page2of282003

3、年9月13日12时20分§3-1对偶问题的提出——从经济上提出1.从经济意义上提出对偶问题（续）∑则设备用于外加工的总收入为：w=8y1+16y2+12y3∑设备台时价格越大，总收入就越大，我们当然希望总收入越大越好。但是，价格问题不是一个企业能完全确定的，它是一种社会价格。因此，我们希望知道最低的总收入是多少，或者说，最低的设备台时价格是多少时就和自己生产产品甲乙所得的收入是一样的。因此，这个问题的数学模型为：minw=8y+16y+12y123y1+4y2+0y3≥22y1+0y2+4y3≥3y≥

4、0,i=1,2,3i∑很显然，当时minw=maxz，决策者认为设备用于外加工和用于生产产品甲乙这两种方案的效果是一样的。河北工业大学管理学院孔造杰制作Page3of282003年9月13日12时20分§3-1对偶问题的提出——从数学模型上提出2.从数学模型上提出对偶问题在上述矩阵表示的单纯形表中，若问题达到了最优解，则其检验数行均小于等于零，即：−1C−CBN≤0NB−1−CB≤0B对其讨论如下：−11)用Y=CBB，称之为单纯形乘子，对于最优解而言，显然有Y≥0。2)对于包含基变量在内的检验数，在最优解

5、的情况下可以表−1示为：C−CBA=C−YA≤0B∴有YA≥C3)因为Y≥0在约束YA≥C的条件下无上界，所以它只存在最小值，它与常向量b的乘积也只存在最小值。记作为：minw=Yb河北工业大学管理学院孔造杰制作Page4of282003年9月13日12时20分§3-1对偶问题的提出——从数学模型上提出4)定义新的LP模型为原模型的对偶模型maxz=CXminw=YbAX≤b对偶模型YA≥CX≥0Y≥0且注意到：原模型maxz=CX在约束AX≤b条件下−1的最优解为：XB=Bb所以有：−1maxz

6、=CX=CBb=Yb=minwB河北工业大学管理学院孔造杰制作ExitPage5of282003年9月13日12时20分§3-2写对偶问题∑将上一节中原问题与对偶问题的矩阵式展开：maxz=cx+cx+L+cx1122nna11a12La1nx1b1aaLaxb21222n2≤2MMMMMMaaLaxbm1m2mnnmx,x,L,x≥012nminw=yb+yb+L+yb1122mm对偶式a11a12La1naaLa()yyLy

7、21222n≥(ccLc)12m12nMMMMaaLam1m2mny,y,L,y≥012m河北工业大学管理学院孔造杰制作Page6of282003年9月13日12时20分§3-2写对偶问题——表格形式∑为便于叙述和记忆对偶问题，通常规定一个标准形式，一般规定原规划为“≤”约束，对偶规划为“≥”约束，变量均≥0的对偶问题为标准形式。把它们之间的关系用表格形式表示出来：xj原关系minwxx┅x12nyi≤y1a11a12┅a1nb1≤y2a21a22┅a2nb2┇┇┇┇┇┇≤yaa┅abmm1m2

8、mnm对偶关系≥≥┅≥maxz=minwmaxzcc┅c12n河北工业大学管理学院孔造杰制作Page7of282003年9月13日12时20分§3-2写对偶问题——非标准型的处理∑在实际问题中常常会有非标准形式，如有等式约束，或某变量无非负约束等等。如果某个约束为等式约束，可以把它变为两n个不等式约束如下：maxz=∑cjxjnj=1maxz=∑cjxjnj=1等价变换∑aijxj≤bi,i=1