python linprog, lp 似乎是无界的

Question

我正在尝试在Python中编写一个简单的LP来解决剪刀石头布，这是我之前的代码：

from scipy.optimize import linprog

obj = [0, 0, 0, -1]

A = [[0, 1, -1, -1], [-1, 0, 1, -1], [1, -1, 0, -1], [1, 1, 1, 0]]
b = [0, 0, 0, 1]
pb = (0.0, 1)
wb = (None, None)

res = linprog(obj, A_ub=A, b_ub=b, bounds=(pb,pb,pb,wb),options={"disp": True})
print(res)

不幸的是，当我运行执行此操作时，我收到以下消息：

    'Optimization failed. The problem appears to be unbounded.'

但考虑到我的LP如下：

f = -w

pp - ps - w = 0
-pr + -ps - w = 0
pr - pp - w = 0
pr + pp + ps = 1
0 < pr, pp, ps < 1

我不明白为什么这是无限的。如果我搞砸了我的 LP 的构造或者存在语法错误，有人可以告诉我。

Answer 1

你在通话中写到：

res = linprog(obj, <b>A_ub</b>=A, <b>b_ub=</b>b, bounds=(pb,pb,pb,wb),options={"disp": True})

所以这意味着你写一个 A_ub * x <= b_ub 而不是 A_eq * x = b_eq。结果你的程序看起来像：

minimize f = -w
wrt.
    pp - ps - w <= 0
    -pr + -ps - w <= 0
    pr - pp - w <= 0
    pr + pp + ps = 1
    0 < pr, pp, ps < 1

因为我们在最后几行 ... - w <= 0 并且我们的目标是最小化 -w，这意味着最优的是 w 正无穷大。

但是您的程序建议您需要相等边界。所以我们可以用 A_eq 和 b_eq 参数来写这个：

res = linprog(obj, <b>A_eq=</b>A, <b>b_eq=</b>b, bounds=(pb,pb,pb,wb),options={"disp": True})

然后我们得到：

>>> res = linprog(obj, A_eq=A, b_eq=b, bounds=(pb,pb,pb,wb),options={"disp": True})
Optimization terminated successfully.
         Current function value: -0.000000   
         Iterations: 4
>>> print(res)
     fun: -0.0
 message: 'Optimization terminated successfully.'
     nit: 4
   slack: array([0.66666667, 0.66666667, 0.66666667])
  status: 0
 success: True
       x: array([0.33333333, 0.33333333, 0.33333333, 0.        ])

这意味着我们有：

pr = 1/3
pp = 1/3
ps = 1/3
w = 0

python linprog, lp 似乎是无界的

python linprog, lp appears to be unbounded

python

scipy

linear-programming