1 基本概念
線形計画法は、目的を一次式で表し、複数の制約も一次式で与える最適化の枠組みである。限られた資源をどのように配分すれば、利益を増やし、費用や時間を抑えられるかを定式化するために用いられる。数学的には、変数の値に条件を課しながら、許される範囲の中で最良の解を探す問題として扱われる。
1.1 線形計画問題の定義
線形計画問題は、ある変数集合について、線形な目的関数を最大化または最小化し、同じく線形な制約条件を満たすように解を求める問題である。代表的には、変数が非負であることを前提に、資源配分、製造計画、輸送計画などを扱う。定式化が明確で、理論と計算の両面で扱いやすい点が特徴である。
1.2 目的関数
目的関数は、最適化の目標を数式で表したもので、利益、コスト、距離、時間などを反映する。線形計画では、各変数に係数を掛けて足し合わせる形をとり、解の良し悪しを比較する基準となる。最大化では成果を増やす方向を、最小化では損失や負担を減らす方向を表現する。
1.3 制約条件
制約条件は、利用可能な資源や守るべき条件を表す。一次式として与えられるため、問題の構造が保たれ、解法の適用がしやすい。制約は、資材量、労働時間、予算、容量などの上限や必要量を示すことが多い。
1.3.1 等式制約
等式制約は、左辺と右辺が等しくなる条件である。ある量をちょうど使い切る場合や、収支が一致しなければならない場合に現れる。モデルによっては、フロー保存のように、流入と流出を一致させる役割を担う。
1.3.2 不等式制約
不等式制約は、ある量が上限以下、下限以上であることを指定する。多くの実問題では、資源の不足を避けるために「以下」、必要条件を満たすために「以上」の形が使われる。これにより、実現可能な範囲が限定される。
1.4 実行可能解
実行可能解は、すべての制約を満たす変数の組である。目的関数の値がどれほど良くても、制約を破る解は候補にならない。したがって、まず実行可能性が確保され、その中から比較が行われる。
1.5 最適解
最適解は、実行可能解の中で目的関数を最も良くする解である。最大化なら値が最大、最小化なら値が最小のものを指す。最適解が複数存在する場合もあり、そのときは同じ最適値を与える解が連続的に並ぶことがある。
2 幾何学的性質
線形計画法は、代数的な問題であると同時に、幾何学的にも理解できる。制約条件は空間の一部を切り取って領域を形成し、目的関数はその領域上で等値面を動かす。こうした見方により、解がどこに現れやすいかが直感的に把握できる。
2.1 実行可能領域
実行可能領域は、すべての制約を満たす点全体の集合である。平面では多角形、より高次元では多面体として表されることが多い。問題が解けるかどうかは、この領域が空でないかに左右される。
2.2 頂点と極点
頂点は、多面体の角にあたる点であり、線形計画では重要な候補となる。極点は、集合の内部の凸結合として表せない点を指し、実行可能領域の端に位置する。多くの場合、最適解はこれらの境界上、とくに頂点に現れる。
2.3 凸集合としての性質
実行可能領域は凸集合である。つまり、領域内の任意の2点を結ぶ線分は、すべて領域内に含まれる。この性質により、局所的に良い点がそのまま全体でも良い解になりやすく、線形計画の理論的な扱いが簡潔になる。
2.4 可解性と無限解
可解性は、少なくとも1つの実行可能解が存在するかどうかを指す。さらに、最適値が有限であれば、問題は有界であるといえる。一方、制約が不十分だと目的関数をいくらでも改善できることがあり、その場合は最適解が存在せず、無限に増大または減少する。
3 解法
線形計画問題には複数の解法があり、問題の規模や構造に応じて使い分けられる。小規模な場合は図形的に理解しやすく、大規模な場合は計算機向けの手法が有効である。代表的には単体法と内点法が広く知られている。
3.1 図式解法
図式解法は、変数が2変数程度のときに用いられる視覚的手法である。制約を平面上に描き、実行可能領域を確認したうえで、目的関数の等値線を動かして最適点を探す。教育的には分かりやすいが、次元が高い問題には直接適用しにくい。
3.2 単体法
単体法は、実行可能領域の頂点を順に移動しながら最適解を探す古典的手法である。各ステップで目的関数を改善する方向へ基底を更新し、有限回の操作で解に到達することを目指す。実用上、長く重要な位置を占めてきた。
3.2.1 基底解
基底解は、制約式の一部を選んで変数を決めることで得られる代表的な解である。実行可能であれば基底実行可能解と呼ばれる。単体法では、この基底解を出発点として隣接する基底へ移り、目的値を改善していく。
3.2.2 ピボット操作
ピボット操作は、ある変数を基底に入れ、別の変数を基底から外す更新手順である。これにより、新しい頂点へ移動し、解の値を変化させる。表形式の計算では、行列の変形を通じて制約の表現を更新する。
3.2.3 退化と循環
退化は、複数の基底解が同じ頂点を表す現象である。このとき、目的関数の値が改善されないまま基底だけが変わることがある。さらに、選択規則が不適切だと循環が生じ、同じ状態を繰り返す危険があるため、回避策が必要になる。
3.3 内点法
内点法は、実行可能領域の内部を通りながら最適解に近づく手法である。境界上をたどる単体法と対照的で、大規模な問題で高い効率を示すことがある。障壁関数や経路追跡の考え方を用い、数値計算との相性がよい。
3.4 双対単体法
双対単体法は、双対側の条件を保ちながら解を改善する方法である。元の問題が扱いにくい場合でも、双対可行性を利用して計算を進められる。特定の制約の変更後に再計算する場面で、実務上便利なことが多い。
4 理論と応用
線形計画法は、計算手法だけでなく、理論的な構造と応用上の広がりを備えている。双対性によって問題を別の視点から見ることができ、感度分析で条件変化への影響を調べられる。また、輸送や割当などの特殊問題に対する標準的な道具でもある。
4.1 双対性
双対性は、ある線形計画問題に対して対応する別の問題を作り、両者の関係を調べる考え方である。主問題と双対問題は、目的関数と制約の役割が入れ替わる形で結びつく。これにより、最適値の比較や経済的解釈が可能になる。
4.1.1 双対問題の構成
双対問題は、主問題の制約から変数を、主問題の変数から制約を導くように組み立てられる。最大化問題に対して最小化問題が対応するなど、対称的な形を持つことが多い。構成規則を用いれば、機械的に作成できる。
4.1.2 双対定理
双対定理は、主問題と双対問題の最適値が一致することを述べる中心的結果である。適切な条件のもとで、片方の最適解が得られれば、もう一方の値も確定する。これは理論面でも計算面でも大きな意味を持つ。
4.1.3 補完スラックネス条件
補完スラックネス条件は、主問題と双対問題の各制約や変数の間に成り立つ関係である。ある制約が余裕を持つなら対応する双対変数は0になり、逆に双対変数が正なら対応制約は等号になる。最適性判定にも役立つ。
4.2 感度分析
感度分析は、係数や右辺値の変化が最適解にどう影響するかを調べる手法である。実際の応用では、データはしばしば変動するため、1回の計算結果だけでなく、どの程度の変化に耐えられるかを知ることが重要である。運用計画の安定性評価にも使われる。
4.2.1 目的係数の変化
目的係数の変化は、利益率やコスト単価が変わった場合の影響を見るものである。係数が少し変化しても最適基底が維持される範囲があり、その範囲内では解の構造が変わらないことが多い。これにより、モデルの頑健性を評価できる。
4.2.2 制約定数の変化
制約定数の変化は、資源量や需要量が増減したときの影響を扱う。右辺値の変化によって実行可能領域が移動し、最適値も変わりうる。許容範囲を把握すれば、追加資源の投入や削減の効果を見積もれる。
4.2.3 シャドープライス
シャドープライスは、制約定数をわずかに変えたときの最適値の変化率を表す。資源1単位の価値に相当する解釈ができ、経済学や運用管理で重要である。どの制約が特に重要かを示す指標として用いられる。
4.3 特殊問題
線形計画法は、特定の構造を持つ問題群にも適用される。標準形に書き直すことで、一般の線形計画として解けるものが多い。こうした特殊問題は、計算効率の工夫やアルゴリズム設計の面でも重要である。
4.3.1 輸送問題
輸送問題は、複数の供給地から複数の需要地へ商品を運ぶときの費用最小化を扱う。供給量と需要量の制約があり、どの経路にどれだけ配るかを決める。物流計画や在庫管理で広く利用される。
4.3.2 割当問題
割当問題は、作業者と仕事、機械と作業などを1対1で対応させる問題である。総費用の最小化や総効率の最大化を目的とする。構造が整っているため、専用手法による高速な解法が知られている。
4.3.3 ネットワーク流問題
ネットワーク流問題は、頂点と辺からなる網目構造上で流量を最適化する問題である。流入と流出の保存則や容量制約が組み合わさり、輸送、通信、交通などに応用される。線形計画の枠内で表現できる代表例の一つである。
4.4 拡張と関連分野
線形計画法は、より複雑な最適化分野への入口でもある。変数に離散条件を加えたり、目的や制約が線形でなくなったり、複数の目標を同時に扱ったりすることで、応用範囲はさらに広がる。基礎理論の理解は、これらの発展分野の土台となる。
4.4.1 整数計画法
整数計画法は、変数の一部または全部に整数条件を課す拡張である。0か1の選択を表す場合や、個数を扱う場面で重要になる。線形計画より難しいが、枝刈り法などの発展的手法が使われる。
4.4.2 非線形計画法
非線形計画法は、目的関数または制約が線形でない最適化問題を扱う。線形計画より一般的で、現実の複雑な現象を表しやすい一方、解析と計算が難しくなる。線形計画はその特別な場合として基礎を与える。
4.4.3 多目的最適化
多目的最適化は、複数の目的を同時に考える問題である。たとえば、費用を下げながら品質や公平性も保つといった状況がある。線形計画の枠組みを拡張して扱うことができ、妥協解やパレート最適性の概念が用いられる。