scipy linprog 单纯形问题
Trouble with scipy linprog simplex
我正在尝试解决一个零和游戏,为玩家 I 找到最佳概率分布。为此,我使用 scipy linprog 单纯形法。
看到例子了,我要改造这个游戏:
G=np.array([
[ 0 2 -3 0]
[-2 0 0 3]
[ 3 0 0 -4]
[ 0 -3 4 0]])
进入这个线性优化问题:
Maximize z
Subject to: 2*x2 - 3*x3 + z <= 0
-2*x1 + + 3*x4 + z <= 0
3*x1 + - 4*x4 + z <= 0
- 3*x2 + 4*x3 + z <= 0
with x1 + x2 + x3 + x4 = 1
这是我的实际代码:
def simplex(G):
(n,m) = np.shape(G)
A_ub = np.transpose(G)
# we add an artificial variable to maximize, present in all inequalities
A_ub = np.append(A_ub, np.ones((m,1)), axis = 1)
# all inequalities should be inferior to 0
b_ub = np.zeros(m)
# the sum of all variables except the artificial one should be equal to one
A_eq = np.ones((1,n+1))
A_eq[0][n] = 0
b_eq = np.ones(1)
c = np.zeros(n + 1)
# -1 to maximize the artificial variable we're going to add
c[n] = -1
res = linprog(c, A_ub=A_ub, b_ub=b_ub, A_eq=A_eq, b_eq=b_eq, bounds=(0,None))
return (res.x[:-1], res.fun)
这是我得到的分布:
[5.87042987e-01 1.77606350e-10 2.79082859e-10 4.12957014e-01]
总和为 1,但我希望
[0 0.6 0.4 0]
我正在尝试一个更大的游戏,有 6 或 7 条线(以及变量),它甚至加起来都不到 1..我做错了什么?
感谢您提供的任何帮助。
(我假设玩家 1(行玩家)正在最大化,玩家 2(列玩家)正在最小化。)
玩家 1 在该游戏的纳什均衡中的策略是 [0, x2, x3, 0]
和 4/7 <= x2 <= 3/5
、x2 + x3 = 1
.
在您的代码中,您缺少不等式约束 -G.T x + z <= 0
的负号。
试试下面的代码:
def simplex(G, method='simplex'):
(n,m) = np.shape(G)
A_ub = -np.transpose(G) # negative sign added
# we add an artificial variable to maximize, present in all inequalities
A_ub = np.append(A_ub, np.ones((m,1)), axis = 1)
# all inequalities should be inferior to 0
b_ub = np.zeros(m)
# the sum of all variables except the artificial one should be equal to one
A_eq = np.ones((1,n+1))
A_eq[0][n] = 0
b_eq = np.ones(1)
c = np.zeros(n + 1)
# -1 to maximize the artificial variable we're going to add
c[n] = -1
res = linprog(c, A_ub=A_ub, b_ub=b_ub, A_eq=A_eq, b_eq=b_eq, bounds=(0,None),
method=method) # `method` option added
return (res.x[:-1], res.fun)
使用单纯形法:
simplex(G, method='simplex')
(array([0. , 0.57142857, 0.42857143, 0. ]), 0.0)
# 4/7 = 0.5714285...
用内点法:
simplex(G, method='interior-point')
(array([1.77606350e-10, 5.87042987e-01, 4.12957014e-01, 2.79082859e-10]),
-9.369597151936987e-10)
# 4/7 < 5.87042987e-01 < 3/5
使用修改后的单纯形法:
simplex(G, method='revised simplex')
(array([0. , 0.6, 0.4, 0. ]), 0.0)
# 3/5 = 0.6
(运行 与 SciPy v1.3.0)
自从找到解决方案以来,我还没有更新 post。我建议不要使用 Scipy linprog 函数,如果您对线性规划了解不多,它的文档会很糟糕,而且我发现它在许多示例中不精确且不一致(当时我确实尝试添加负号,正如 oyamad 所建议的那样)。
我切换到 PuLP python 库,从一开始就获得一致的结果没有问题。
我正在尝试解决一个零和游戏,为玩家 I 找到最佳概率分布。为此,我使用 scipy linprog 单纯形法。
看到例子了,我要改造这个游戏:
G=np.array([
[ 0 2 -3 0]
[-2 0 0 3]
[ 3 0 0 -4]
[ 0 -3 4 0]])
进入这个线性优化问题:
Maximize z
Subject to: 2*x2 - 3*x3 + z <= 0
-2*x1 + + 3*x4 + z <= 0
3*x1 + - 4*x4 + z <= 0
- 3*x2 + 4*x3 + z <= 0
with x1 + x2 + x3 + x4 = 1
这是我的实际代码:
def simplex(G):
(n,m) = np.shape(G)
A_ub = np.transpose(G)
# we add an artificial variable to maximize, present in all inequalities
A_ub = np.append(A_ub, np.ones((m,1)), axis = 1)
# all inequalities should be inferior to 0
b_ub = np.zeros(m)
# the sum of all variables except the artificial one should be equal to one
A_eq = np.ones((1,n+1))
A_eq[0][n] = 0
b_eq = np.ones(1)
c = np.zeros(n + 1)
# -1 to maximize the artificial variable we're going to add
c[n] = -1
res = linprog(c, A_ub=A_ub, b_ub=b_ub, A_eq=A_eq, b_eq=b_eq, bounds=(0,None))
return (res.x[:-1], res.fun)
这是我得到的分布:
[5.87042987e-01 1.77606350e-10 2.79082859e-10 4.12957014e-01]
总和为 1,但我希望
[0 0.6 0.4 0]
我正在尝试一个更大的游戏,有 6 或 7 条线(以及变量),它甚至加起来都不到 1..我做错了什么?
感谢您提供的任何帮助。
(我假设玩家 1(行玩家)正在最大化,玩家 2(列玩家)正在最小化。)
玩家 1 在该游戏的纳什均衡中的策略是 [0, x2, x3, 0]
和 4/7 <= x2 <= 3/5
、x2 + x3 = 1
.
在您的代码中,您缺少不等式约束 -G.T x + z <= 0
的负号。
试试下面的代码:
def simplex(G, method='simplex'):
(n,m) = np.shape(G)
A_ub = -np.transpose(G) # negative sign added
# we add an artificial variable to maximize, present in all inequalities
A_ub = np.append(A_ub, np.ones((m,1)), axis = 1)
# all inequalities should be inferior to 0
b_ub = np.zeros(m)
# the sum of all variables except the artificial one should be equal to one
A_eq = np.ones((1,n+1))
A_eq[0][n] = 0
b_eq = np.ones(1)
c = np.zeros(n + 1)
# -1 to maximize the artificial variable we're going to add
c[n] = -1
res = linprog(c, A_ub=A_ub, b_ub=b_ub, A_eq=A_eq, b_eq=b_eq, bounds=(0,None),
method=method) # `method` option added
return (res.x[:-1], res.fun)
使用单纯形法:
simplex(G, method='simplex')
(array([0. , 0.57142857, 0.42857143, 0. ]), 0.0)
# 4/7 = 0.5714285...
用内点法:
simplex(G, method='interior-point')
(array([1.77606350e-10, 5.87042987e-01, 4.12957014e-01, 2.79082859e-10]),
-9.369597151936987e-10)
# 4/7 < 5.87042987e-01 < 3/5
使用修改后的单纯形法:
simplex(G, method='revised simplex')
(array([0. , 0.6, 0.4, 0. ]), 0.0)
# 3/5 = 0.6
(运行 与 SciPy v1.3.0)
自从找到解决方案以来,我还没有更新 post。我建议不要使用 Scipy linprog 函数,如果您对线性规划了解不多,它的文档会很糟糕,而且我发现它在许多示例中不精确且不一致(当时我确实尝试添加负号,正如 oyamad 所建议的那样)。
我切换到 PuLP python 库,从一开始就获得一致的结果没有问题。