線形計画法とは，次のような問題を解く方法です。
目的関数
Ｚ＝３ｘ＋２ｙ → 最大
制約条件
４ｘ＋１ｙ≦７２
２ｘ＋２ｙ≦４８
１ｘ＋３ｙ≦４８
ｘ≧０，ｙ≧０
いっけん大したことのないように感じられるかもしれませんが，非常に応用のきく手法であり，数多いオペレーションズ・リサーチの手法のなかでも，最も普及しており，実務的に最も効果がある手法の一つです。単に最適解が得られるだけでなく，同時に得られるシャドウ・プライスの概念は，会計的な原価計算や限界利益の概念よりも，利益戦略に適したものなのです。
目次
線形計画法の概念
- 線形計画法の概要（or-lp-gaiyou）
- イントロダクションとして、線形計画法とはどのようなものかを簡単に説明します。
- 線形計画法の種類（or-lp-shurui）
- 線形計画法とは、最適化を求める数理計画法の特殊なケースです。また、線形計画法には多様な派生した計画法があります。その代表的なものを示します。
線形計画法の解法
- 線形計画法の定式化と図式解法（or-lp-zushiki）
- 実務の問題を上のような数学の問題に翻訳することを定式化といいます。定式化された問題をモデルといいます。まず，この定式化の方法を理解することにより，広い分野で有効な手法であることが理解できます。
上の問題のように，変数が２つのときはグラフにより簡単に解けます。現実には２変数の問題は少ないでしょうが，線形計画法を直感的に理解するためには便利です。
- シンプレックス法（or-lp-simplex）
- 実務での線形計画法モデルは，変数や制約条件の個数が数千個にもなるのが多く，正しく迅速に解くために，多様な工夫をした専用のシステムを用います。しかし，その基本になっているのはシンプレックス法という，１次連立方程式を解くような方法です。
- 線形計画法プログラム（or-lp-program）
- 線形計画法の学習では，シンプレックス法を用いることが多いのですが，それを手計算で行っていたのでは時間がかかります。そのために簡単なモデルを解くためのプログラムを提供します。
- Ｅｘｃｅｌソルバーによる線形計画法の解法（or-lp-solver）
- Ｅｘｃｅｌにはこのような問題を解くためのソルバーという機能があります。これも小規模なモデルに限定されますが，使い慣れておくと便利な機能ですので，インストールのしかた，モデルの作り方，解くための操作方法などを説明します。
- 定式化での工夫（or-lp-kuhu）
- 実際の問題では、変数に上限値がある、制約式の不等号の向きが逆になる、数量により価格が異なるというように、上で示した例（標準形）とは異なる制約があります。それを標準形の問題に変形するための、いくつかの工夫を示します。
シャドウ・プライスの概念
- シャドウ・プライスとレンジ（or-lp-reducedcost）
- 線形計画法は，単に最適解が得られるだけでなく，条件を変えたら解がどう変化するかという情報も得ることができます。シャドウ・プライスは，制約条件の持つ価格を示すものであり，限界原価に相当するものです。またレンジは，最適解の構造を変えずに制約条件や目的関数の係数（価格）がどの範囲まで変化できるかを示します。これらを理解するためにもシンプレックス法は必要です。
- 双対問題（or-lp-dual）
- 双対問題とは、標準形を裏返しにしたような問題です。シャドウ・プライスが重要な概念として取り扱われます。実務では、双対問題として定式化することは稀ですが、シャドウ・プライスを理解するのに重要ですし、輸送問題や割当問題などの解法の基礎になる考え方です。
線形計画法の実務効果
- 線形計画法の効果（or-lp-kouka）
- ここまで線形計画法の解法や意味を学習してきましたが，ここでは実務で線形計画法を利用することの効果を理解します。制約条件に余裕があるかどうかで実際の価値は大きく変化するので，利益向上のためには通常の会計的な原価計算を用いることが危険であり，線形計画法による最適化やシャドウ・プライスの概念が適していることを理解します。
特殊な線形計画法
- 割当問題（or-lp-assign）
- ｎ個の作業とｎ人の要員があるとき、どの作業に誰を割り当てれば成果が最大になるかという問題です。これも線形計画法の特殊なケースで解法があります。
- 輸送問題（or-lp-yusou）
- 複数の供給地の供給量と、複数の需要地の需要量、供給地から需要地に輸送する費用が与えられているとき、総輸送費用を最小にするには、どこからどこへ、どれだけ輸送すればよいかを求める問題です。線形計画法での制約条件の係数がすべて１である特徴があり、シンプレックス法よりも簡単な解法があります。