3.シンプレックス表(シンプレックスタブロー)を利用して解く

 前述したシンプレックス法をより簡単に効率的に行うためにシンプレックス表というものがよく利用される。まず、さきほどの線形計画問題の不等号を等号化するために非負のスラック変数を導入する。


この形を線形計画問題の標準形という。

この標準形の線形計画問題の係数を下のような表にする。

基底変数
x1
x2
x3
x4
x5
定数項

定数項/列要素
Z
-2
-3
0
0
0
0

x3
1
2
1
0
0
14

x4
1
1
0
1
0
8

x5
3
1
0
0
1
18


この表のことをシンプレックス表(シンプレックスタブロー)という。
この表を最適解に近づけながら更新していく。その更新するアルゴリズムは以下のとおりである。

STEP1
[列選択]

最上行(目的関数の係数)の中から最小なもの(負のデータなので絶対値が最大)がある列qを探す。
STEP2
[終了判断]

最上行の係数がすべて正になったら終了。これ以上掃き出しを行っても目的関数の値は増加しないことを意味する。
STEP3
[行選択]
STEP1で求めたq列にある各行の要素で各行の右端要素を割ったものが最小となる行pを探す。
STEP4
[掃き出し]
p行q列をピボットにして掃き出し演算を行う。
STEP1に戻り繰り返す。

 では実際にやってみよう。
@最上段の目的関数の中で最小なもの-3があるx2の列を列選択し、その列の各行要素2、1、1で各行の定数項14、8、18を割り、最小なもの14/2=7がある行を行選択する。

基底変数
x1
x2
x3
x4
x5
定数項

定数項/列要素
Z
-2
-3
0
0
0
0

x3
1
2
1
0
0
14
14/2
x4
1
1
0
1
0
8
8/1
x5
3
1
0
0
1
18
18/1

Aその交差する要素2をピボットとして掃き出しを行う。その後同様に最上段の最小なもの-1/2があるx1の列を列選択し、最小な1/(1/2)=2がある行を行選択する。

基底変数
x1
x2
x3
x4
x5
定数項

定数項/列要素
Z
-1/2
0
3/2
0
0
21

x2
1/2
1
1/2
0
0
7
7/(1/2)
x4
1/2
0
-1/2
1
0
1
1/(1/2)
x5
5/2
0
-1/2
0
1
11
11/(5/2)

B交差した要素1/2をピボットとして掃き出す。そうすると最上段の行には負の項がなくなるので、ここで終了。定数項の所に最適解が現れる。

基底変数
x1
x2
x3
x4
x5
定数項

定数項/列要素
Z
0
0
1
1
0
22
←Zの最適解
x2
0
1
1/2
-1
0
6
←x2の最適解
x1
1
0
-1
2
0
2
←x1の最適解
x5
0
0
2
5
1
6
←x5の最適解

Next⇒2段階シンプレックス法とは・・