文档详情

管理运筹学第二章-1.ppt

发布:2025-04-07约1.57千字共25页下载文档
文本预览下载声明

第二章线性规划的对偶问题

与灵敏度分析;A

B

C;资源价格问题;LP;资源价格问题;原问题

MaxZ〔X〕=c1x1+c2x2+…+cnxn

a11x1+a12x2+…+a1nxn≤b1

a21x1+a22x2+…+a2nxn≤b2

………………….

am1x1+am2x2+…+amnxn≤bm

x1,x2,…,xn≥0;2.1.3非对称型对偶问题

例:求以下线性规划的对偶问题;MaxZ〔X〕=2x2-5x3

x1+x3≥2

2x1+x2+6x3≤6

x1-x2+3x3=0

x1,x2,x3≥0;2.1.3非对称型对偶问题

例:求以下线性规划的对偶问题;对应关系可归纳成下表:;练习:

MinZ〔X〕=x1+2x2+x3

x1+x2+x3≤2

x1-x2+x3=1

2x1+x2+x3≥1

x1≥0;一般情形:混合型对偶问题的对应关系;〔P〕与(D)的关系对应表:;练习:;2.1.4对偶问题的根本性质

以对称型为例

设原问题〔P〕为其对偶问题〔D〕为

maxZ〔X〕=CXminW(Y)=Yb

AX≤bYA≥C

X≥0Y≥0;对偶问题为:

MinW(y〕=b1y1+b2y2+…+bmym

a11y1+a21y2+…+am1ym≥c1

a12y1+a22y2+…+am2ym≥c2

…………..

a1ny1+a2ny2+…+amnym≥cn

y1,y2,…,ym≥0;根据条件有:;〔3〕假设X*,Y*分别为问题(P)和问题(D)的可行解,且CX*=Y*b

;那么,X*和Y*分别为问题(P)和问题(D)的最优解。;〔5〕对偶定理:假设问题(P)和问题〔D〕之一有最优解,那么

另一个问题也一定有最优解,且目标函数值相等。;2.1.5对偶问题的解

由对偶定理可知,从原问题的最终单纯表中

可直接得到其对偶问题的最优解。;X*=(45/2,45/2,0,25/2,0)

Y*=〔7/2,0,1/2,0,0〕;假设将资源价格问题作为原问题求解〔两阶段法〕,;假设将资源价格问题作为原问题求解〔两阶段法〕,;例:求以下线性规划的解

MaxZ〔X〕=4x1+3x2

x1≤6

x2≤8

x1+x2≤7

3x1+x2≤15

-x2≤1

x1,x2≥0;[

显示全部
相似文档