0

線形計画問題を自動的に実行可能にするアルゴリズムが必要です。具体的には、アルゴリズムは、その入力が実行可能な解を持たない可能性のある線形計画問題であり、その出力が実行可能な解を持つようにバインドされている同様のプログラミング（パラメーターが最小で変更されている）であるようなものです。私はアルゴリズムの初心者であり、そのような問題に関する既存の研究/作業があるかどうかを尋ねますか？任意の提案やコメントをいただければ幸いです。ありがとう、リチャード

4

2 に答える 2

1

制約にスラック変数を追加して、値の2乗の合計を最小化することができます。

于 2010-10-25T18:53:12.530 に答える
0

方程式ごとに1つずつ、「人工変数」のセットを追加します。その方程式には単位重量があり、それ以外の場所にはゼロの重みがあります。次に、そのセットを最初の基準として選択し、最初の目標として「人工変数を排除する」を追加できます。すべての人工変数を排除できれば、それらを破棄することができ、最初の問題の実行可能な基礎が得られます。人工変数を排除できない場合、実行可能な解決策はありません。

元の問題（標準形-LP問題はこれに変換できます！）：

minimize c.x, given: [A]x = b, x_i>=0
  (but first, need feasible solution)

実行可能な解決策を見つけるには（すべてを想定します。そうでない場合は、行に）b_j>=0を掛けます。-1

minimize sum(y), given:  y + [A]x = b, x_i>=0, y_j>=0
  with initial, feasible solution: x_i=0, y_j=b_j

この種のスキームにはバリエーションと最適化があります。たとえば、この種のことを行うために、必ずしもすべてを標準形に変換する必要はありません（ただし、説明を簡単にするために役立ちます）。線形計画法のテキストで詳細を見つけることができるはずです。

これは「スラック変数」の他の答えと似ていることに注意してください。ただし、何も二乗する意味がありません（これにより、問題が非線形になり、線形計画法のフレームワーク内で解決するのがより困難になります...）

于 2010-10-25T23:19:23.390 に答える