線形計画法は、線型方程式や線形不等式で与えられる制約条件の基で、線形の目的関数を最大あるいは最小化するものです。

●正準型
  minimize     z =  c1x1 +  c2x2 +  c3x3 ....
  subject to       a11x1 + a12x2 + a13x3 ... = b1
                   a21x1 + a22x2 + a23x3 ... = b2
                   a31x1 + a32x2 + a33x3 ... = b3

例）
ある工場では、複数の原料を配合して、炉で溶かして製品を作りますが、
下記の条件の基で、原料費が最小となる配合方法を求めます。

・製品規格(重量=3,330Kg)
     　    規格　　 成分1(%)   成分2(%)   成分3(%)
          ----------------------------------------
          目標値      87.6        7.8        4.6
          上限値      90.0        9.0        5.0
          下限値      85.0        7.0        3.0

・原料
          原料名   成分1(%)   成分2(%)   成分3(%)　歩留(%)　単価　在庫数(Kg)
          ------------------------------------------------------------------
　　　　　原料A     99.5        0.5        0.0      97       415   10,000
　　　　　原料B     93.0        7.0        0.0      94       400   10,000
　　　　　原料C     91.0        9.0        0.0      98       420   10,000
　　　　　原料D      0.0      100.0        0.0      98       870   10,000
　　　　　原料E      0.0        0.0      100.0      98       243   10,000

上記条件より、下記の目的関数と制約条件を作成します。

・目的関数(原料費が最小）
      Min  WA*(415/0.97) + WB*(400/0.94) + WC*(420/0.98) + WE*(870/0.98) + WD*(243/0.98) 

・制約条件
      WA + WB + WC + WD + WE = 3300  ※製品重量は 3,330Kg
      WA < 10000*0.97                ※原料A の在庫重量（歩留り考慮）
      WB < 10000*0.94                ※原料B の在庫重量（歩留り考慮）
      WC < 10000*0.98                ※原料C の在庫重量（歩留り考慮）
      WD < 10000*0.98                ※原料D の在庫重量（歩留り考慮）
      WE < 10000*0.98                ※原料E の在庫重量（歩留り考慮）
      99.5*WA + 93*WB + 91*WC                 = 3300*87.6     ※成分1目標値
       0.5*WA +  7*WB +  9*WC + 100*WD        = 3300*7.8      ※成分2目標値
                                       100*WE = 3300*4.6      ※成分3目標値

線形計画法によって、以下の各原料の配合重量が求められます。

          原料名   実重量(Kg)   配合重量　　原料費
          ------------------------------------------
　　　　　原料A        0.0          0.0          0
　　　　　原料B     1308.7       1392.0    \556,800
　　　　　原料C     1868.1       1906.0    \800,520
　　　　　原料D        0.0          0.0          \0
　　　　　原料E      153.2        156.0     \37,908
          ------------------------------------------
          合 計     3330.0       3454.0  \1,395,228

混合整数計画法は、線形計画法における一部の変数あるいは全ての変数において、整数条件が付加された問題を解くものです。
弊社では、多くの商用ソフトウェアで使用されている分枝限定法を用いています。

●正準型
  minimize     z =  cx + dy
  subject to        Cx + Dy = b
                    x≧0, x∈Zn
                    y≧0

例）
ある工場では、鋼板を切断して製品を作ります。
いま、長さ１００ｍの鋼板を用いて、以下の５種類の製品を作りますが、余った鋼板は廃棄処分にし、
１ｍあたり５０００千円の損失が出ます。この条件で最大の利益を得る方法を考えます。


・製品
     　 規格　 長さ(M)   利益（万円）
       ------------------------------
       製品1       23        5
       製品2       32        6
       製品3       45        9
       製品4       33        7
       製品5       41        9


上記条件より、下記の目的関数と制約条件を作成します。

・目的関数(原料費が最小）
      Max  -0.5X1 + 5Y1 + 6Y2 + 9Y3 + 7Y4 + 9Y5

・制約条件
      X1 + 23Y1 + 32Y2 + 45Y3 + 33Y4 + 41Y5 = 100  ※長さ
　　　Y1 < 1   　※製品1は１つ
　　　Y2 < 1   　※製品2は１つ
　　　Y3 < 1   　※製品3は１つ
　　　Y4 < 1   　※製品4は１つ
　　　Y5 < 1   　※製品5は１つ


混合線形計画法によって、以下の結果が求められます。

     　 規格　   枚数   利益（万円） 
       ------------------------------
       製品1       1       5
       製品2       1       6
       製品3       1       9
       製品4       0       0
       製品5       0       0

       余りは０ｍで、利益は20万円になります。

線形目標計画法は、複数個の目的に対して設定された目標値に可能な限り近づけるものです。

●目標計画法の目的関数
　　目標計画法においては、目標の達成過不足を表わす補助変数ｄ＋、ｄ−の係数を（−１，０，１）の中から適当に
　　決めることにより、下の表に示すようなさまざまなタイブの意思決定方式を取り扱うことができます。

　　　di+ + di-	：　目標値を超えても、不足でもよいから、できるだけ目標値に近づけたい。	
　　　di-　　　　 ：　目標値の超過はかまわないが達成不足だけはさけたい。	
　　　di+　　　　 ：　目標値の不足はかまわないが超過だけはさけたい。	
　　　di+ - di-	：　目標値と関係なく、達成値を最小にしたい。	
　　　-di + di-	：　目標値と関係なく、達成値を最大にしたい。


例）
線形計画法の例で配合し溶解した結果、分析結果が目標値から外れました。
この状態から 100Kg以内で原料を追加し、最小重量で目標値に近づける方法を求めます。
※調整する成分の優先順位は、目標値の小さい順とします。

・製品規格(重量=3,330Kg)
     　    規格　　 成分1(%)   成分2(%)   成分3(%)
          ----------------------------------------
          目標値      87.6        7.8        4.6
          上限値      90.0        9.0        5.0
          下限値      85.0        7.0        3.0
 
　　　　　分析値      83.37       7.8        4.64

・原料
          原料名   成分1(%)   成分2(%)   成分3(%)　歩留(%)　単価　在庫数(Kg)
          ------------------------------------------------------------------
　　　　　原料A     99.5        0.5        0.0      97       415   10,000
　　　　　原料B     93.0        7.0        0.0      94       400   10,000
　　　　　原料C     91.0        9.0        0.0      98       420   10,000
　　　　　原料D      0.0      100.0        0.0      98       870   10,000
　　　　　原料E      0.0        0.0      100.0      98       243   10,000

上記条件より、下記の目的関数と制約条件を作成します。

・目的関数
　　　MIN   D3+  
　　　MIN   D2+  
　　　MIN   D1+  
　　　MIN   D3-  
　　　MIN   D2-  
　　　MIN   D1-  
　　　MIN   X1 + X2 + X3 + X4 + X5

・制約条件
     11.9*WA + 5.4*WB + 3.4*WC - 87.6*WD - 87.6*WE - D1+ + D1- = 769.12     ※成分1目標値
     -7.3*WA - 0.8*WB + 1.2*WC + 92.2*WD -  7.8*WE - D2+ + D2- = 0          ※成分2目標値
     -4.6*WA - 4.6*WB - 4.6*WC -  4.6*WD + 95.4*WE - D3+ + D3- = -133.76    ※成分3目標値
          WA +     WB +     WC +      WD +      WE             < 100        ※補正重量は 100Kg以内
          WA < 10000*0.97                ※原料A の在庫重量（歩留り考慮）
          WB < 10000*0.94                ※原料B の在庫重量（歩留り考慮）
          WC < 10000*0.98                ※原料C の在庫重量（歩留り考慮）
          WD < 10000*0.98                ※原料D の在庫重量（歩留り考慮）
          WE < 10000*0.98                ※原料E の在庫重量（歩留り考慮

線形計画法によって、以下の各原料の配合重量が求められます。

          原料名   実重量(Kg)   配合重量
          -------------------------------
　　　　　原料A        0.0          0.0 
　　　　　原料B       17.4         19.0 
　　　　　原料C       11.6         12.0 
　　　　　原料D        0.0          0.0 
　　　　　原料E        0.0          0.0 
          ------------------------------
          合 計       29.0         31.0 


   上記の加重平均値は、以下の配合値になります

     　    規格　　 成分1(%)   成分2(%)   成分3(%)
          ----------------------------------------
          目標値      87.6        7.8        4.6
          上限値      90.0        9.0        5.0
          下限値      85.0        7.0        3.0
 
　　　　　分析値      83.37       7.8        4.64
　　　　　配合値      87.41       7.8        4.6