定式化
典型的な（簡単な）線形計画法を掲げます。
「製品Ｘを１kg生産するには，原料Ａを４kg，原料Ｂを２kg，原料Ｃを１kg必要とし，製品Ｙを１kg生産するには，原料Ａ１kg，原料Ｂを２kg，原料Ｃを３kg必要とします。原料の在庫量は，Ａは７２kg，Ｂは４８kg，Ｃは４８kgあります。製品Ｘの売価は３万円／kg，製品Ｂの売価を２万円とするとき，利益（＝売上高。原料や生産の費用は考えないことにします）を最大にするには，製品Ｘと製品Ｙをどれだけ生産すればよいでしょうか。」
この問題文を整理すると次表になります（製品を横，原料を縦にとるのがコツです）。
製品Ｘ 製品Ｙ 原料在庫量
原料Ａ ４ １ ７２
制約条件 原料Ｂ ２ ２ ４８
原料Ｃ １ ３ ４８
目的関数 Ｚ： ３ ２ → 最大
製品Ｘをｘkg，製品Ｙをｙkg生産するには原料Ａを ４ｘ＋１ｙ kg必要とします。ところが原料Ａの在庫量は７２kgですので，
４ｘ＋１ｙ≦７２
の式が成立します。
以下同様にして，上の問題は次のように定式化することができます。
制約条件
４ｘ＋１ｙ≦７２
２ｘ＋２ｙ≦４８
１ｘ＋３ｙ≦４８
（ｘ≧０，ｙ≧０）・・・暗黙の条件
のなかで，
目的関数
Ｚ＝３ｘ＋２ｙ
を最大にする，ｘとｙの値を求める。
「線形計画法」の意味
この問題を抽象的に表現すれば，「一次不等式の制約条件の下で一次式を最大（最小）にする技法」だといえます。一次式はグラフに描くと直線，すなわち線形（リニア）になります。一次式を取り扱う数学の分野を線形数学といいます。線形数学を利用した計画法（プログラミング）という意味で線形計画法（リニア・プログラミング－ＬＰ）というのです。
一次式以外の制約条件や目的関数があるときは，非線形計画法といいます。また，制約条件の下で目的関数を最大化する技法を総称して数理計画法といいます。線形計画法は数学的計画法のなかで最もポピュラな技法で，実務的にも広く活用されています。さらに線形計画法には，特殊な条件を加えた整数計画法とか輸送問題・割当問題の解法など，多様な技法があります。
図式解法（グラフによる解法）
上の例では，変数がｘとｙの２つですから，グラフを描いて解くことができます。それを図式解法といいます。
１ｘ＋３ｙ≦４８をグラフで示すには，１ｘ＋３ｙ＝４８のグラフにより二分されたどちらか一方です。そのグラフを描くのには，ｙ＝－（１／３）ｘ＋１６と変形してもよいのですが，次のようにするほうが簡単です。
- １ｘ＋３ｙ＝４８で，１ｘの項を無視すると（すなわちｘ＝０とすると），３ｙ＝４８，すなわちｙ＝１６ですから，この直線はｙ軸上の点（０，１６）を通ります。
- こんどは３ｙの項を無視するとｘ＝４８になるので，ｘ軸上の点（４８，０）を通ります。
- この２つの点を結んだ直線が１ｘ＋３ｙ＝４８です。
- １ｘ＋３ｙにｘ＝０，ｙ＝０を代入すると０になります。０≦４８ですから，原点（０，０）は不等式１ｘ＋３ｙ≦４８を満足する側になります。すなわち，１ｘ＋３ｙ≦４８は下図のメッシュの部分になります。
同様にして，４ｘ＋１ｙ≦７２，２ｘ＋２ｙ≦４８，１ｘ＋３ｙ≦４８およびｘ≧０，ｙ≧０がすべて成立する範囲は，下図のメッシュの部分になります。これが制約条件です。すなわちメッシュされら内部（線も含む）の点は，制約条件をすべて満足しており，それ以外の点は制約条件の少なくとも１つは満足していないことになります。
例をあげて確認しましょう。メッシュの内部の点として（５，８），外部の点として（４，１６）を用います。
制約条件 （５，８）のとき （４，１６）のとき
４ｘ＋１ｙ≦７２ ４×５＋１×８＝２８ ○ ４・４×１・１６＝３２ ○
２ｘ＋２ｙ≦４８ ２×５＋２×８＝２６ ○ ２・４×２・１６＝４０ ○
１ｘ＋３ｙ≦４８ １×５＋３×８＝２９ ○ １・４×３・１６＝５２ ×
（制約条件が不成立）
目的関数Ｚ＝３ｘ＋２ｙにおいて，Ｚを２４，４８，６４，９６としたときのグラフを描くと下図のようになります。すなわち傾きが－（２／３）の平行線で，右上になるほどＺの値（目的関数の値）が大きくなることがわかります。
制約条件を満足するのはメッシュの内部であり，目的関数のグラフが右上にいくほど目的関数の値が大きくなるのですから，最大になるのは図の点Ｐ（１６,８）を通るときです。すなわち，ｘ＝１６，ｙ＝８が最適値であり，最大値はＺ＝６４となります。これを元の問題で表現するのであれば，「製品Ｘを１６kg，製品Ｙを８kg生産するのが最適であり，そのときの利益は６４万円になる」となります。
なお，ｘ＝１６，ｙ＝８のときは，４ｘ＋１ｙ＝７２，２ｘ＋２ｙ＝４８ですから原料Ａと原料Ｂは全量使用したことになりますが，１ｘ＋３ｙ＝４０≦４８なので原料Ｃは８kg在庫が残っています。原料Ａと原料Ｂには余裕がないが原料Ｃには余裕があることは上のグラフから読み取ることができます。
