3

私はここで見つけることができる質問をしました:
最適な組み合わせの計算

と線形計画法が提案されていました。線形計画法とシンプレックス法を調べました。しかし、私が遭遇したすべての例には、スラック変数を使用して等式に変換される不等式制約があります。次に、シンプレックス法は、基本変数と非基本変数を交換して最適解を取得します。

しかし、私の問題は次のとおりです。

最小化:
x1 + x2 + ... + xn

対象:
a1*x1 + a1*x2 + a1*x3 + ... + a1*xn = c1;
a2*x1 + a2*x2 + a2*x3 + ... + a2*xn = c2;
a3*x1 + a3*x2 + a3*x3 + ... + a3*xn = c3;

ここには基本的な変数がないため、ここでシンプレックス法を適用する方法がわかりません。
また、n個の変数と3つの方程式があるため、線形方程式を解くことはできません。
誰かが私にここから抜け出す方法を提案できますか?

4

4 に答える 4

5

各方程式を 2 つの不等式に書き直すことができます。

a1*x1 + a1*x1 + a1*x3 + … + a1*xn ≤ c1
a1*x1 + a1*x1 + a1*x3 + … + a1*xn ≥ c1

a1これは、ラベル付けされた係数が実際には異なることを前提としています。そうしないと、LP 全体が相互依存性が高くなり、簡単に解決できないか、まったく解決できなくなります。次に、スラック変数を追加して、不等式を再び等式にします。

a1*x1 + a1*x1 + a1*x3 + … + a1*xn + y1a = c1    y1a ≥ 0
a1*x1 + a1*x1 + a1*x3 + … + a1*xn - y1b = c1    y1b ≥ 0

これらの y1a と y1b が初期の基本変数になり、ピボットを開始できます。初期の基本解がすでに実行可能である場合は最適解を見つけるか、そうでない場合は実行可能解を見つけるかのいずれかです。

于 2013-06-25T05:05:43.007 に答える
2

教科書には

Kenneth Steiglitz と Christos Papadimitiou による「組み合わせ最適化」

シンプレックス アルゴリズムの自己完結型の詳細な説明を見つけることができます。私の記憶が正しければ、等式制約のみが与えられ、根拠がない場合、それぞれコストがゼロの人工変数を追加した人為的基礎が導入されます。直観的には、これは制約行列の片側に恒等行列を「接着」するようなものです。次に、シンプレックス アルゴリズムが開始され、人為的な基底を「追い出す」、つまり、人為的な変数が基底に含まれなくなるまで繰り返します。これは、元の定式化の基底が見つかったことを意味します。

于 2013-06-26T13:28:08.820 に答える
0

この問題は線形計画法で解決できます。2 つの不等式を使用して制約を記述するのではなく、GLPK などのソルバーに入力するだけです。たとえば、GMPL の数行で記述できます。

param k, n;
param a{1..k}{1..n};
param c{1..k};
var x{1..n}, >= 0;

minimize cost : sum{i in 1..n} x[i];
s.t. constraints{j in 1..k} : sum{i in 1..n}(a[j][i] * x[i]) = c[j];

ただし、ここで述べたように、モデルにはおそらく最適なものはありません。非負の制約がなければ、それは未決定の線形システムであり、無限の解があります。リンクされた投稿のように、 x は非負のままでなければならず、制約はもう少し複雑であると想定しています。

于 2014-11-11T17:16:28.680 に答える