【理论】运筹学-线性规划及标准形式

 我来答
青柠姑娘17
2022-06-08 · TA获得超过1.2万个赞
知道大有可为答主
回答量:6575
采纳率:100%
帮助的人:37.5万
展开全部
那么某一个顶点其实就是某组超平面的交点,这一组超平面对应的约束就是在某一个顶点取到“=”号的约束(也就是基)。顶点对应到代数意义就是一组方程(取到等号的约束)的解

线性规划里面的约束(等式或不等式可以看作是超平面Hyperplane或者半空间Half space)。可行域可以看作是被这组约束,或者超平面和半空间定义(围起来)的区域。

那么某一个顶点其实就是某组超平面的交点,这一组超平面对应的约束就是在某一个顶点取到“=”号的约束(也就是基)。顶点对应到代数意义就是一组方程(取到等号的约束)的解。

用矩阵去理解运筹学

线性规划 (Linear Programming)-- 最简单和基础的优化问题,如上图, 目标函数 (max)和 约束条件 (s.t.)都是线性的,自变量x是实数变量,P问题(多项式时间可解);或许有些读者没有学过线性代数,更简单的例子: min x1+x2  s.t. 3x1-4x2> 5,  x1,x2>=0。

特点:

(1) 目标函数求最大值(有时求最小值)

(2) 约束条件都为等式方程,且右端常数项bi都大于或等于零.

约束条件都为等式方程,需要解除松弛变量和剩余 变量

(3) 决策变量xj为非负。

对于无约束的变量,如(X3 无约束)可以用类似 X3=X4-X5替换,且 X4>=0,X5>=0

即每一个线性规划问题(称为原始问题)有一个与它对应的对偶线性规划问题

对偶问题与原始问题之间存在着下列关系:

①目标函数对原始问题是极大化,对对偶问题则是极小化。

②原始问题目标函数中的收益系数是对偶问题约束不等式中的右端常数,而原始问题约束不等式中的右端常数则是对偶问题中目标函数的收益系数。

③原始问题和对偶问题的约束不等式的符号方向相反。

④原始问题约束不等式系数矩阵转置后即为对偶问题的约束不等式的系数矩阵。

⑤原始问题的约束方程数对应于对偶问题的变量数,而原始问题的变量数对应于对偶问题的约束方程数。

⑥对偶问题的对偶问题是原始问题,这一性质被称为原始和对偶问题的对称性。

1 若原问题及其对偶问题都具有可行解,则两者都具有最优解。且他们的最优解的目标函数值相等

2对于线性规划的原问题和对偶问题,若其中有一个有最优解,则另一个也一定有最优解

3如果一个线性规划问题有两个不同的最优解,则它有无穷多个最优解

线性规划中的唯一最优解是指最优表中非基检验数全部为0

其变量均具有非负约束,其约束条件当目标函数求极大值时均取《号,当目标函数求极小值时均取>=号
已赞过 已踩过<
你对这个回答的评价是?
评论 收起
迈杰
2024-11-30 广告
多组学联合分析是我们迈杰转化医学研究(苏州)有限公司的重要研究领域。该技术通过整合基因组、转录组、蛋白质组及代谢组等多层次数据,提供对生物系统更全面、深入的理解。我们利用先进的生物信息学工具和方法,实现多组学数据的整合与挖掘,从而揭示疾病发... 点击进入详情页
本回答由迈杰提供
推荐律师服务: 若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询

为你推荐:

下载百度知道APP,抢鲜体验
使用百度知道APP,立即抢鲜体验。你的手机镜头里或许有别人想知道的答案。
扫描二维码下载
×

类别

我们会通过消息、邮箱等方式尽快将举报结果通知您。

说明

0/200

提交
取消

辅 助

模 式