0

我尝试使用 GLPK来实现这个线性问题。当我针对石头剪刀布游戏（在混合策略中具有均衡性）进行测试时x=(1/3, 1/3, 1/3)，y=(1/3, 1/3, 1/3我得到了不可行的解决方案。

我回到 MathProg 来检查它是否会成功。不幸的是，它也失败了。我猜这是由于-1值的原因，因为基本的单纯形法不允许负变量，并且需要进行一些转换才能绕过它（尽管我认为它只涉及变量，而 GLPK 会自动执行此操作）。

我已经定义了这样的问题：

  • 播放器 1 的型号：

    set P1S;
set P2S;

param Payoff{P1S, P2S};

var y{P1S} >= 0;

minimize GameValue: sum{i in P1S} y[i];

s.t. Condition2{j in P2S}:
    sum{i in P1S} Payoff[i,j] * y[i] >= 1;

solve;

printf "Value: %s\n", GameValue;

printf "Player 1 strategies:\n";

for{i in P1S}
    printf "Found %s, actual %s\n", y[i], y[i]/GameValue;

end;

  • 数据：

    data;

set P1S := r p s;
set P2S := r p s;

param Payoff
    :  r  p  s :=
    r  0 -1  1
    p  1  0 -1
    s -1  1  0;

end;

我运行它：

$ glpsol --model rps.mod --data rps.dat
GLPSOL: GLPK LP/MIP Solver, v4.54
Parameter(s) specified in the command line:
 --model rps.mod --data rps.dat
Reading model section from rps.mod...
22 lines were read
Reading data section from rps.dat...
12 lines were read
Generating GameValue...
Generating Condition2...
Model has been successfully generated
GLPK Simplex Optimizer, v4.54
4 rows, 3 columns, 9 non-zeros
Preprocessing...
3 rows, 3 columns, 6 non-zeros
Scaling...
 A: min|aij| =  1.000e+00  max|aij| =  1.000e+00  ratio =  1.000e+00
Problem data seem to be well scaled
Constructing initial basis...
Size of triangular part is 3
      0: obj =   0.000000000e+00  infeas =  3.000e+00 (0)
LP HAS NO PRIMAL FEASIBLE SOLUTION
glp_simplex: unable to recover undefined or non-optimal solution
Time used:   0.0 secs
Memory used: 0.1 Mb (126428 bytes)

我的猜测是否正确，我可以应用一些简单的解决方法（例如设置一些标志）？还是我搞砸了其他事情（以错误的方式写下问题或忽略了某些事情）？

编辑：

在将矩阵的每个值增加常数1（使所有值都非负）后，我得到了正确的解决方案（GameValue也被移动了，1所以我可以通过减去它来恢复它）。它是否仅在这种情况下有效，或者如果（在运行 GLPK 之前）我将所有参数增加常数以使它们全部为非负数，它是否会中断？我可以在 GLPK 中设置一些标志来自动执行吗？

4

1 回答 1

0

我们被允许通过常数增加收益矩阵以使所有元素都为正-这将使我们的 GameValue 也增加该常数（wiki）。

因此，在将问题委托给 GLPK 之前，我们应该找到矩阵的最小元素（比如说m），然后计算m' = min(m, 0). 然后我们应该将所有元素增加abs(m')，像往常一样解决问题，并获得 GameValue 减少abs(m')。

在 MathProg 和 GLPK 中都可以手动完成（实际上 MathProg 有很好min的 abs计算参数的功能 - 请参阅手册），但显然没有标志。这种转换不会改变 NE 问题的正确性，但可能会影响其他 LP 问题的正确性，我们不能认为这是理所当然的。

于 2014-06-02T10:18:08.637 回答