如何編寫檢查不平等的制度有一個解決方案

Question

我需要找到的算法，可以檢查系統這樣

X1 * K + B> Y1， X2 * K + B> Y2， ...，XN * K + b <炔

具有將（S） 其中，i代入x [i]和Y [i]和未知varialbes是K，b。

Answer 1

你的問題等同於詢問點是否線性可分（一類點對應於不等式>，其他點與<）。

如果存在分隔線，則可以使用Perceptron Algorithm查找分隔線。該wikipedia頁面也提供了一些替代算法。

Answer 2

如果只有最後一個不等式是「<」，並且所有其他的都是「>」。下面是如何檢查：

系統變換爲：b> Y1 - X1 * K，B> Y2 - X2 * K，...，B < YN - xn的* K

而且很容易查看原始系統是否有解相當於系統yn-xn * k> y1-x1 * k，yn-xn * k> y2-x2 * k，...已解決

而且它是相當於yn - y1>（xn - x1）* k，yn - y2>（xn - x2）* k，...有解或不存在。

然後，您需要討論xn - xk的符號，無論它們是零，正還是負，並且可以進一步將系統轉換爲更簡單的形式。例如，如果xn-x1> 0和xn-x2 = 0，則它將如下所示：k（yn-y1）/（xn-x1），k>（yn-y2）/（xn-x2）， ...

然後很容易檢查新的簡單系統是否有解決方案，是否相當於原有系統有解決方案。