微笑如一
首页 分解查字 摄影图片 JAR包信息 网址收藏 技术文章

日期:2017-12-28
浏览:613
标签: 数学,
内容:
任何一个求极大化的线性规划问题都有一个求极小化的线性规划问题与之对应,反之亦然,如果我们把其中一个叫原问题,则另一个就叫做它的对偶问题,并称这一对互相联系的两个问题为一对对偶问题。


对偶理论是研究线性规划中原始问题与对偶问题之间关系的理论。在线性规划早期发展中最重要的发现是对偶问题,即每一个线性规划问题(称为原始问题)有一个与它对应的对偶线性规划问题(称为对偶问题)。

##########

原始问题和对偶问题的标准形式如下:

设原始问题为:

min z=cx

s.t. Ax <= b

x>= 0

则对偶问题为:

max w=yb

s.t. yA >= c

y>=0

式中max表示求极大值,min表示求极小值,s.t.表示“约束条件为”;z为原始问题的目标函数,w为对偶问题的目标函数;x为原始问题的决策变量列向量(n×1),y为对偶问题的决策变量行向量(1×m);A为原始问题的系数矩阵(m×n),b为原始问题的右端常数列向量(m×1),c为原始问题的目标函数系数行向量(1×n)。在原始问题与对偶问题之间存在着一系列深刻的关系,现已得到严格数学证明的有如下一些定理。

(摘)



联系: web@xiaoruyi.cn