如何证明线性规划问题的可行解域一定是凸集

发布网友发布时间：2022-05-10 02:16

共3个回答

热心网友时间：2023-10-19 15:39

所有的线性规划约束都可以化成：AX<=b
假设可行域为S,从中任意取两个点X1,X2,
则AX1<=b,AX2<=b
则A(a*X1+(1-a)*X2)=a*AX1+(1-a)*AX2<=a*b+(1-a)*b=b
其中0<=a<=1
所以A(a*X1+(1-a)*X2)<=b
所以a*X1+(1-a)*X2属于S
据凸集的定义可知：S凸集。
即线性规划问题的可靠域一定是凸集。

热心网友时间：2023-10-19 15:40

　　把前三个不等式变成等式，画出相应直线，一般情况下，它们围成的区域就是可行域。如果直线不过原点，把原点带进不等式，如果成立，那么这个不等式所表示的区域就是坐标系中原点的在一侧的区域，如果不成立，那么就是另外一侧的区域
　　如果直线过原点，则在坐标平面内任意取一个不在直线上的点，带入不等式，看看不等式是不是成立，如成立，则就是这一点所在的区域；如果不成立，则在另外一侧。
　　线性规划（Linear programming,简称LP）是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支，它是辅助人们进行科学管理的一种数学方法。研究线性约束条件下线性目标函数的极值问题的数学理论和方法。英文缩写LP。它是运筹学的一个重要分支，广泛应用于军事作战、经济分析、经营管理和工程技术等方面。为合理地利用有限的人力、物力、财力等资源作出的最优决策，提供科学的依据。