l****u
发帖数: 4594 | 1 数学基础不行，请教一个基本的线性规划问题；
如何判断一个linear programming problem 有 feasible solution？
有没有相对简单的定理或方法？
当然了直接用simplex method去解，根据是否有结果也可以判断，我只是希望有一个相
对直接和快速的方法； |
k**a
发帖数: 121 | 2 这个似乎和LP本身一样是NP-hard问题，也就是说除了直接解，没有更好的方法。当然
，针对具体问题，可以试试用Farkas's Lemma:
[Farkas's Lemma] Let A be an m × n matrix and b an m-dimensional vector.
Then, exactly one of the following two statements is true:
1. There exists an x ∈ R^n such that Ax = b and x ≥ 0.
2. There exists a y ∈ R^m such that A'y ≥ 0 and b'y < 0.
where ' denotes transpose.
或者试试dual。如果 optimal dual solution unbounded，那么原本的LP就是
infeasible。
求dual和Farkas's Lemma道理差不多，都是把系数矩阵转置过来，如果你的问题把系数
矩阵转置过来比较好看，可以试试。不过说来说去对于一般的LP，这些都是NP-
【在 l****u 的大作中提到】
: 数学基础不行，请教一个基本的线性规划问题；
: 如何判断一个linear programming problem 有 feasible solution？
: 有没有相对简单的定理或方法？
: 当然了直接用simplex method去解，根据是否有结果也可以判断，我只是希望有一个相
: 对直接和快速的方法；
|
k**a
发帖数: 121 | 3 对了还有，如果直接解的话不是解那个LP本身，而是把原问题变一下做成一个辅助的LP
再解。如果辅助LP的optimal solution严格 > 0，说明原问题infeasible。反之如果辅
助LP的optimal solution = 0，说明原问题feasible。
具体方法可以去任何一本LP教材上查，有个two-phase method还有个big-M method都是
干这个用的。
【在 l****u 的大作中提到】
: 数学基础不行，请教一个基本的线性规划问题；
: 如何判断一个linear programming problem 有 feasible solution？
: 有没有相对简单的定理或方法？
: 当然了直接用simplex method去解，根据是否有结果也可以判断，我只是希望有一个相
: 对直接和快速的方法；
|
l******e
发帖数: 470 | 4 LP不是NPhard.
【在 k**a 的大作中提到】
: 这个似乎和LP本身一样是NP-hard问题，也就是说除了直接解，没有更好的方法。当然
: ，针对具体问题，可以试试用Farkas's Lemma:
: [Farkas's Lemma] Let A be an m × n matrix and b an m-dimensional vector.
: Then, exactly one of the following two statements is true:
: 1. There exists an x ∈ R^n such that Ax = b and x ≥ 0.
: 2. There exists a y ∈ R^m such that A'y ≥ 0 and b'y < 0.
: where ' denotes transpose.
: 或者试试dual。如果 optimal dual solution unbounded，那么原本的LP就是
: infeasible。
: 求dual和Farkas's Lemma道理差不多，都是把系数矩阵转置过来，如果你的问题把系数
|
l****u
发帖数: 4594 | 5 thanks a lot!
【在 k**a 的大作中提到】
: 这个似乎和LP本身一样是NP-hard问题，也就是说除了直接解，没有更好的方法。当然
: ，针对具体问题，可以试试用Farkas's Lemma:
: [Farkas's Lemma] Let A be an m × n matrix and b an m-dimensional vector.
: Then, exactly one of the following two statements is true:
: 1. There exists an x ∈ R^n such that Ax = b and x ≥ 0.
: 2. There exists a y ∈ R^m such that A'y ≥ 0 and b'y < 0.
: where ' denotes transpose.
: 或者试试dual。如果 optimal dual solution unbounded，那么原本的LP就是
: infeasible。
: 求dual和Farkas's Lemma道理差不多，都是把系数矩阵转置过来，如果你的问题把系数
|
