【補】シンプレックス法

　線形計画法は最小の費用の下で得られるべき利益を最大にすることを目的とした最適化の１つの方法です．商業上重要というだけでなく，数学のいろいろな分野でも使われます．

　線形計画法におけるシンプレックス法は，有限個の線形不等式

　　Ａｘ≧ｂ，　　maximize　ｃｘ

の解の集合から最適解を求めるもので，ダンツィックにより１９４７年から開発が進められました．その手順はまず実行可能な頂点を見つけ，そこから多面体の辺に沿って，線形の目的関数ｃｘが増加するように進んでいくというものです．

　ｄ次元の場合，多面体の各頂点からはｄ本の辺がでているのですが，しかし，目的関数が増加するような次の辺をどうやって選べばよいかは現在でも完全には解決されていない問題となっています（多項式時間アルゴリズムがあるか？）．

　また，一口にシンプレックス法といっても，データが得られた状況によってそれぞれに最適な手法が用意されていて，それらを適宜選択し使い分ける必要が出てきます．シンプレックス法の教科書はこれまで多数出版されていますが，たいていはｘが非負の場合のみを解説しています．変数ｘが非負の値をとるようにした制約条件の場合，非基底変数の値は０ですが，下限Ｌと上限Ｕの間の値をとるようにした制約条件の場合，非基底変数の値はＬかＵのどちらかとなります．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝