線形計画法(シンプレックス法)

サイトマップホーム

制約条件を設定する事により、目的とする効果(売上・利益・原価低減・その他効果(満足度・宣伝効果・等))を最大にする最適解が簡単に得られる。

決定変数 X1       X2      X3      X4     制約量
目的関数      MAX
制約条件1     
制約条件2     
制約条件3     
制約条件4     
制約条件5     
制約条件6     
制約条件7     
最適解 X1      X2      X3      X4      最大
    

 

 
 

線形計画法(LP : Linear Programming)とは、制約式(制約条件)と呼ばれるいくつかの1次式を満たす変数の値の中で、

目的関数と呼ばれる1次関数を最大化または最小化する値を求める方法である。

この目的式の最大値、及びそれを実現する変数を求める問題が線形計画問題である。

また、線形計画問題を解く手法の一つとしてシンプレックス法がある。

解き方の説明(シンプレックス法)

問題

ある会社が、A、Bという製品を売り出している。 それらを製作するための材料はプラスチック、アルミ、ゴムである。

それぞれ1個を製作するために必要な材料の量は下の表のとおりである。

製品材料  プラスチック アルミ    ゴム     単価    
A 1kg 1kg 3kg 2万円
B 2kg 1kg 1kg 3万円
材料の量 14kg 8kg 18kg  

このとき、手持ちの材料の範囲内で売上高を最大にするためには、A、Bをそれぞれいくつ作ったらよいか?

連立法定式

最大値 :20X + 30X
制約条件:X  + 2X ≦ 800
      3X + 4X ≦ 1800
      3X + X  ≦ 1500  X、X ≧ 0

シンプレックス法を適用するための準備

与えられた線形計画問題を正規形に変形する。正規形に変形された問題の目的関数をZとおく。

最大値:Z
制約条件: X + 2X + S = 800
      3X + 4X + S = 1800
      3X +  X + S = 1500 
      Z - 20X - 30X = 0     X、X 、S、S、S ≧ 0

シンプレックス法の手順

ステップ1:シンプレックス表を作成する。

基底変数    Z   X   X   S   S   S 定数項
   0    1    2    1    0    0  800
   0    3    4    0    1    0 1800
   0    3    1    0    0    1 1500
   1  -20  -30    0    0    0    0

ステップ2:ピポットを計算する。

  1. Z行で最も小さい負の値を持つ列に対応する非基底変数を新たに基底に入れる変数に選ぶ。(X列)

  2. 各行(Zの行は除く)において(定数項の値)÷(新たに基底に入れることになった変数の係数)を計算する。

    その値を増加限界と呼ぶ。 各行の増加限界の中で非負で最小の値を取った行に対応する変数を追い出す変数に決める。(S行)

  3. 新たに基底に加える変数の列と基底から追い出す変数の行との交点の係数をピボットにする。

    ピボット(S行、X列)ピボットを中心に掃き出しを行う。

基底変数   Z   X   X   S   S   S  定数項 増加限界
   0    1    2    1    0    0   800   400
   0    3    4    0    1    0  1800   450
   0    3    1    0    0    1  1500  1500
   1  -20  -30    0    0    0     0   

ステップ3:連立方程式の解を解く

  1. ピボットが1になるように,ピボットのある行のすべての数字をピボットの数字で割る。
  2. 各行からピボットの行を何倍かして引くことにより、ピボット列の数字がピボット以外0になるようにする。
基底変数   Z   X   X   S   S   S  定数項 計算
   0  0.5    1   0.5    0    0   400 (ピポット行)÷2
   0    1    0    -2    1    0   200 行-(ピポット行)X4
   0  2.5    0  -0.5    0    1  1100 行-(ピポット行)X4
   1   -5    0    15    0    0 12000 Z行-(ピポット行)X(-30)

ステップ4:連立方程式の解を評価する。

現在の基底変数から得られた連立方程式の解が最適かどうか吟味する。

Zの行を見るとx1の列に負の値がある.よって,現在得られている解は最適ではない。

ステップ3 より良い目的関数値を持つ解を見つけるように基底変数と非基底変数の組合せを変更する。

ステップ2に戻り、ピポットを計算する。計算により、ピボットは計算により(S行、X列)として、ピボットを中心に掃き出しを行う。

基底変数   Z   X   X   S   S   S  定数項  増加限界
   0  0.5    1  0.5    0    0   400    800
   0    1    0   -2    1    0   200    200
   0  2.5    0 -0.5    0    1  1100    440
   1   -5    0   15    0    0 12000  

ステップ5:連立方程式の解を解く(ステップ3と同様に行う)

基底変数   Z   X   X   S   S   S  定数項 増加限界
   0    0  1.5 -0.5    0   300 行ー(ピポット行)X0.5
   0    1   -2    1    0   200 行÷1
   0    0  4.5 -2.5    1   600 行ー(ピポット行)X2.5
   1    0    5    5    0 13000 Z行ー(ピポット行)X(-5)

ステップ6:連立方程式の解を評価する。

Zの行を見ると負の値はない.

つまり,これ以上基底を変更してもより良い目的関数値は得られない.よって,現在得られている解が最適である。

※線形計画の問題を解く方法としてMicroSoft Excelのソルバーを使って解く方法があります。参考にして下さい。

Excelで線形計画の問題を解く方法

h51602


サイトマップホーム