Dual値が意味するもの

OR理論を駆使して問題を解くときの基礎です。

 

DUAL値 = 制約を 1 単位だけ緩めたとき、目的関数がどれだけ改善するかを示す感度係数。

• 最大化問題なら：制約を緩めると目的値が どれだけ増えるか

• 最小化問題なら：制約を緩めると目的値が どれだけ減るか

つまり、DUAL値は 制約の価値 を表します。

📌 1. DUAL値の直感的な意味（影の価格）

DUAL値は、経済学では shadow price（影の価格） と呼ばれます。

• ある制約が「資源の上限」を表す場合

→ DUAL値は「その資源を 1 単位追加できたら、目的関数がどれだけ良くなるか」を示す。

例：

制約Aを緩めると、目的関数が△減少する

その減少量が DUAL値。

📌 2. 数学的な意味（双対問題の最適解）

LPには必ず 双対問題（DUAL problem） が存在し、

DUAL値はその双対問題の最適解の変数値です。

• primal：変数 x

• dual：変数 y（これが DUAL値）

双対問題は「制約の重み付けによって目的値を評価する問題」で、

DUAL値はその最適な重み付けを表します。

📌 3. 実務での解釈（制約の重要度）

DUAL値は、制約がどれだけ「効いているか」を示します。

● DUAL値 ≠ 0

→ その制約は binding（効いている）

→ 制約を緩めると目的値が改善する

→ 資源が不足している状態

● DUAL値 = 0

→ 制約は 余裕がある（非binding）

→ 緩めても目的値は変わらない

→ 資源が余っている状態

📌 6. 注意点

• DUAL値は「制約の右辺を微小に変化させたとき」の効果

→ 大きく変えると線形性が崩れ、DUAL値は使えない

• 整数計画（MILP）では DUAL値は一般に意味を持たない

→ LP緩和でのみ有効