3

私は、次のタイプの線形方程式を 3 つの変数で解かなければならないプログラミング (Python を使用) の問題に取り組んでいます。

x、y、z はすべて整数です。

式の例: 2x + 5y + 8z = 14

調子：Minimize x + y + z

最適な方法で、これに対する解決策を見つけるためのアルゴリズムを検索しようとしています。誰かがアイデアを持っている場合は、アルゴリズムまたはコードソースを案内してください。

この問題が n 変数に外挿された場合、何ができるのでしょうか?

値をチェックし続けるために、ヒット & トライアル ループを使用したくありません。また、方程式が解を持たないというシナリオもあるかもしれません。

アップデート

下限条件の追加:

x, y, z >= 0
x, y, z are natural
4

5 に答える 5

3

ちょうど 3 次元に等式制約付き整数計画法(IP) があります。等式制約2 x + 5 y + 8 z = 14は、3 次元空間で平面を定義します。それをパラメータ化すると、

x = 7 - 2.5 u - 4 v
y = u
z = v

2 次元で制約のないIPを取得します。完全性の制約が与えられると、 と が得られu <- {0,2}ますv <- {0,1}。4 つの ペアすべてを列挙すると、最小値は であり、およびで達成され、それぞれおよびに対応すると(u,v)結論付けます。4(u,v) = (2,0)(u,v) = (0,1)(x,y,z) = (2,2,0)(x,y,z) = (3,0,1)

PuLPを使用して整数計画法を解く:

from pulp import *

# decision variables
x = LpVariable("x", 0, None, LpInteger)
y = LpVariable("y", 0, None, LpInteger)
z = LpVariable("z", 0, None, LpInteger)

# define integer program (IP)
prob = LpProblem("problem", LpMinimize)
prob += x+y+z                   # objective function
prob += 2*x + 5*y + 8*z == 14   # equality constraint

# solve IP
prob.solve()

# print results
print LpStatus[prob.status]
print value(x)
print value(y)
print value(z)

x = 3、y = 0およびを生成しz = 1ます。

于 2016-10-06T01:48:34.193 に答える
3

z = (14 - 2x - 5y) / 8の任意のトリプル(x, y, z)は、制約を満たします。

x + y + (14 - 2x - 5y) / 8は下から無制限であることに注意してください。この関数は、xとyのそれぞれが減少すると減少し、有限の最小値はありません。

于 2016-10-05T08:20:05.800 に答える
1

この種の問題を解決する別のツールはSCIPです。GitHub で利用できる使いやすい Python インターフェイスもあります: PySCIPOpt。

一般に、(混合) 整数計画問題は解くのが非常に難しく (NP の複雑さ)、多くの場合、少数の変数と制約しかない単純に見えるインスタンスでさえ、最適な解を証明するのに何時間もかかることがあります。

于 2016-10-06T05:38:45.443 に答える
0

最初の方程式から:

x = (14 - 5 歳 - 8 歳) / 2

したがって、最小化するだけで済みます

(14 - 5y - 8z) / 2 + y + z

これは

(14 - 3歳 - 6歳) / 2

ただし、最小化のために「/ 2」の部分は無視できます。

おそらく、解決策は y と z の両方が際限なく成長する可能性があるため、問題には他の制約が必要です。

于 2016-10-05T08:33:03.553 に答える
0

n 変数の一般的な高速ソリューションを知らない、またはヒット & トレイル ループを使用していない。しかし、与えられた特定の方程式については、 2x + 5y + 8z = 14観察に基づいた近道があるかもしれません。

考えられる解の範囲が非常に小さいことに注意してください。

0<=x<=7、 0<=y<=2、 0<=z<=1

また、x = 7 以外では、少なくとも 2 つの変数を使用する必要があります。 (この場合 x+y+z = 7)

2 つの変数のみを使用した場合の結果を見てみましょう。

(x,z) または (y,z) を使用することを選択した場合、aszは 1 しかないxか、y自明です。

(x+y+z = 4 for (x,z), no solution for (y,z))

(x,y) の使用を選択した場合、xのy係数は偶数であり、 の係数は奇数であるyため、偶数の RHS (14) を実現するには、 の偶数を選択する必要があります。これはy2 でなければならないことを意味しx、自明です。

(この場合 x+y+z = 4)

3 つの変数すべてを使用した場合の結果を見てみましょう。

同様に、z1 でなければならないので、基本的には 2 つの変数 (x,y) を使用して 14-8 = 6 を達成します。これは偶数です。

ここでも同様の引数を使用するため、偶数のy2 を選択する必要がありますが、この時点ですでに 2y + 1z > 14 であり、3 つの変数すべてを使用した解がないことを意味します。

したがって、論理的に単純に、1 つまたは 2 つの変数を使用して式を簡約すると、14 (x=3、y=0、z=1 または x=2、y=2)を達成するための最小 x+y+z は 4であることがわかります。 ,z=0)

于 2016-10-05T09:00:03.060 に答える