GLPS操作ガイド



[目標計画法メンページへ]

Copyright(C)1998 M.Shiimori , All Rights Reserved.






第一章目標計画法の概要

一. GLPS機能と特徴

GLPSは Goal Programming System を略したもので目標計画法専用のパッケージである。

  1. GLPSはJAVAとC++言語で開発され、インターネット技術を利用して、企業イントラネットのインフラを構築できます。
  2. 絶対順数のインプリメンテーション目標計画法を採用。
  3. 人工変数は解法論理の中に取り扱ってない。
  4. 解法は有界変数法による改定シンプレックス法である。
  5. 計算精度を上げるために逆行列計算の再逆転(REINVERSION)を取入れます。
  6. Multiple Pricing 法を用いている。
  7. 使用言語は、すべてC++である。
  8. 最適解をもとめることができる。

二. 多重目標の目標分析

満足基準による意志決定が立った上で多重目標を扱えることが目標計画法の大きな特徴である。いまm個の上位目標があり、その目標値がB1、B2、……Bmまたはそれらを成分とする列ベクトルをBで表わすとする。ここでそれらの下位目標を成分とする列ベクトルをXで表わし。さらにm×n行列、Aを下位目標と上位目標とをつなぐ関係を表わすものとすると、この目標分析の問題は次のように表現される。

      AX = B
       X ≧ 0

これに解がある場合、それは次のような目標計画法の解として求めることができる。

  目的関数:
       eY + eY → 最小化
  制約条件:
       AX − IY + IY = 0
        X, Y , Y ≧ 0

ここで e は、その成分が全部1からなるm次元ベクトルであり、YとYはそれぞれ目標の超過達成値と達成不足値を表わすm次元ベクトルである。さらに I はm×mの単位行列である。

三. 目標のタイプ

目標計画法においては、目標の達成過不足を表わす補助変数Y+、Y−の係数を(−1,0,1)の中から適当に決めることにより、下の表に示すようなさまざまなタイブの意思決定方式を取り扱うことができる。

意思決定のタイプ 目的関数
目標値を超えても、不足でもよいから、できるだけ目標値を丁度達成するようにしたい。 + + Y-
目標値の超過はかまわないが達成不足だけはさけたい。 -
目標値の不足はかまわないが超過だけはさけたい。 +
目標値と関係なく、達成値を最小にしたい。 + − Y-
目標値と関係なく、達成値を最大にしたい。 −Y+ + Y-

この取り扱い得る意思決定のタイプの多さが目標計画法の特徴の一つである。なおこの五つの意思決定のタイプと付順の考え方を使うと、意思決定の際の目標と環境制約の違いは、単なる付順の絶対的な違いにすぎず、この点以外は全く同様に扱えるという面白さがある。すなわち環境制約はいかなる目標にも先だって満足させなければならない最も重用な目標であるということである。

[GLPS操作ガイドTOPへ]




第二章インプット・データの与え方

インプット・データとは、目標計画法システムにユーザが予め用意したデータ・ファイルによる計算に必要なデータ情報を与えることをいう。新規データはGLPSのメニューのファイル → 新規 あとはテキスト エリアで入力すれば良い。応用例はファイル → 開く を経て、Sampl01 〜 Sample99ファイル名のファイルを開くことによって計算することができます。

GLPS(Ver2.7.7版)の与え方


LINDO用のLPモデルファイルの拡張子をGPDに変更するだけで、GLPSで再利用できます。
例 test1.ltx を test1.gpd に拡張子変換

インプットデータ各項目の書き方

モデルには、モデル名(省略可)と目的関数、制約条件式、変数型宣言(省略可)の四つが必要です。 入力順序はモデル名、目的関数、制約条件式、変数型宣言の順で記述します。

モデル名(省略可)

TITLEを書き一つ以上の半角スペースを入力後にアルファベット、 漢字または英数字から成る文字列のモデル名を書きます。

変数

変数名はアルファベット文字(A〜Z)で始まらなくてはならなりません。 最大半角英数8文字。また目標計画法のモデル+-記号も使えます。変数名の + - と 区別するため、制約条件式の演算子加算と減算には前後必ず半角スペースを挿入して下さい。 GLPSは大文字小文字の違いを識別しません。

目的関数

行の始めには最大化問題の時 max、最小化問題の時 min、その後に目的関数の式を入力します。

制約条件式

制約条件式の始めには ST(subject to)を書き、最後に END を書きます。 制約条件式の記入の際、不等号は <= または >= で記述するか、または < や > のみで記述しても等号があると自動的に解釈されます。制約条件式の演算子加算 と減算には前後必ず半角スペースを挿入します。 制約式に名前をつけることができます。 制約式の名前の最後には' )'を必ずつけます。 制約式の名前は最大半角英数16文字、漢字8文字です。' )'の後に制約条件式が入ります。 勿論制約条件式の名前を省略してもかまいません。
例として、次の制約条件式の名前は'P2'
P2) 8X12 + 8X14 + 5X22 + 5X24 + Y2- - Y2+ = 75

変数型(type)宣言

変数のとりうる値の範囲として、つぎの五つの場合が考えられます。
(1) -∞ < 変数 < ∞
(2) a < 変数 < ∞ (a は定数)
(3) -∞ < 変数 < b (b は定数)
(4) a < 変数 < b (a,b は定数)
(5) 変数 = C (C は定数)
上限、下限の両方を指定してもよいし、いずれか一方のみを指定してもよい。 片方だけが指定されているとき、もう一方は +∞ または 0 となります。 上限の+∞は、自動的ジェネレートされるので、指定しても意味がありません。 変数型(type)の指定が省略した場合、自動的正値変数( 0 < 変数 < +∞ )になります。
FREE <変数名>    (-∞ < 変数 < ∞)
SLB <変数名> (Value < 変数 < ∞)
SUB <変数名> (0 < 変数 < Value)
FIX <数値>       固定値変数指定 (変数 = C)
GIN <変数名>,<変数名> X1,X2,‥一般整数タイプに指定
INT <変数名>,<変数名> X1,X2,‥01整数タイプに指定
INT <数値>       先頭から変数の数を01整数タイプに指定
変数型宣言例
例1: −∞ < X2 < 4 を変数型宣言する
FREE X2
SUB X2 4
例2: X1、X2、X3、X4、X5五つの変数がある場合
X1、X2、X3だけを01整数タイプに宣言する
方法1 INT X1, X2, X3
方法2 INT 3

コメント行

GLPSのデータファイルの中にはコメントを書くことができます。
! から行末までがコメントとして扱われます。

インプットデータの例

生産管理応用例の数学モデル。
Minimize Y1-
Minimize Y2-
Minimize X23 + X24
Minimize X13 + X14
Subject to
200X11+160X21+80X12+50X22+150X13+120X23+56X14+35X24 + Y1- - Y1+ = 3500
8X12 + 8X14 + 5X22 + 5X24 + Y2- - Y2+ = 75
4 ≦ X11 + X12 ≦ 8
4 ≦ X11 + X12 ≦ 8
0 ≦ X11 + X12 ≦ 4
0 ≦ X11 + X12 ≦ 4
すべての変数 ≧ 0
変数 X11, X12, X13. X14, X21, X22, X23, X24 は整数

下図はGLPS(Ver2.7.7)に生産管理応用例を編集画面に入力した状態。

GLPS(Ver2.7.4以前版)の与え方

インプットデータ各項目の書き方

モデルには、モデル名(省略可)と目的関数、変数、制約条件式の三つが必要です。入力順序はモデル名、目的関数、制約条件式の順で記述します。目的関数、制約条件式、各行の入力は、一行の終わりまでは、改行キー(Enter)を挿入しない、即ち式の行での自動改行はOKですか、途中での強制改行はしないでください。

モデル名(省略可)

NAMEを書き一つ以上の半角スペースを入力後にアルファベット、漢字または数字から成る文字列のモデル名を書きます。

変数

アルファベット、半角英数字から成る文字列(最大半角8字)なら何を使っても良く、また目標計画法のモデル+-記号も使えます。但し変数名の + - と区別するため、制約条件式の演算子加算と減算には前後必ず半角スペースを挿入して下さい。

目的関数

行の始めには最大化問題の時 max、最小化問題の時 min、その後に目的関数の式を入力します。

制約条件式

制約条件式の始めには st (subject toの略)を書き、最後に end を書き、制約条件式の記入の際、 不等号は <= または >= で記述するか、または < や > のみで記述しても等号があると自動的に解釈されます。 制約条件式の演算子加算と減算には前後必ず半角スペースを挿入します。変数のBOUND指定は、 制約条件式で直接指定します。無限大値は半角 @ 記号で記述します。例:自由変数 -@ < x < @ 負値変数 -@ < x < 0

下図はGLPSに生産管理応用例を編集画面に入力した状態。

GLPS(Ver2.77M)版MPSフォーマットの与え方

インプット・データは、見出し部分とデータ部分より構成される。見出し部分は、その後にデータの種類を示すもので一語より構成される。データファイルの最初に必ず NAME 、最後に必ず END が置かれる。NAMEの見出しはこのデータファイルにユーザが指定する名前を与えるものであり、つぎの様な一般形で与えられる。

フィールドとフィールドの間は全て半角空白或いは Tab で区切る。
フィールド 1 フィールド 2
NAME ユーザの指定する名前

ENDはデータファィルの終了を知らせるもので、つぎの様な一般形で与えられる。
フィールド 1
END

NAMEとENDの間はつぎの五種類のデータより構成される。

  1. ROWS(行情報)
  2. COLUMNS(列情報)
  3. RHS(右辺情報)
  4. RANGES(レンジ情報)
  5. BOUNDS(バウンド情報)

1〜3は、必ず与えなければならず、またこの順序で与えなければならない。 4と5は、必要に応じて与えればよい。以下に、これらの各機能毎に詳しい説明を加える

一 ROWS(行情報)

ROWSはモデル行列の各行に名前をつけると同時に、その制約行の符号の向きを規定する。

見出し部分
フィールド 1
ROWS

データ部分
フィールド 1 フィールド 2
制約種類 行の名前

フィールド1 制約条件の種類を指定する。
フィールド2 行の名前を定義する。

二 COLUMNS(列情報)

COLUMNSはモデル行列の各列に名前を与え、その列をベクトルとして、 マトリックス要素に値をあたえてゆく。

見出し部分
フィールド 1
COLUMNS

データ部分
フィールド 1 フィールド 2 フィールド 3 フィールド 4 フィールド 5
列名 行名 要素値 行名 要素値

三 RHS(右辺情報)


RHS(Right Hand Side)は、右辺の制約ベクトルに名前を与え、対応する要素に値をあたえる。

見出し部分
フィールド 1
RHS

データ部分
フィールド 1 フィールド 2 フィールド 3 フィールド 4
行名 要素値 行名 要素値

四 RANGES(レンジ情報)

一般に制約条件は、( 行 ) ≦ A  或いは( 行 ) ≧ A で与えるが、場合によって

          A ≧ ( 行 ) ≦ B  のように与えたいことがある。

このような制約条件を、RANGEという。このときいずれか一方、例えばAをRHS値で与える。RANGESは残った一方の値、ここではBを与えるために用いられる。このときRANGESに与える値は、RHSで前に指定されている値からの変化の大きさで指定する。前の例ではBそのものを与えるのではなく、B=A + d としてdの値を指定することになる。

見出し部分
フィールド 1
RANGES

データ部分
フィールド 1 フィールド 2 フィールド 3 フィールド 4
行名1 d1 行名2 d2

五 BOUNDS(バウンド情報)

一般に変数は 0 〜 +∞の値をとることができるが、場合によってはこれに制限を加えたい場合がある。このような制限は制約式としてインプットすることもできるが、いろいろの点からこのBOUNDの機能を用いると便利なことが多い。BOUNDの指定の ない変数は自動的 0 〜 +∞ にセットされる。

見出し部分
フィールド 1
BOUNDS

 データ部分
フィールド 1 フィールド 2 フィールド 3
バウンドの型 列名 バウンド値

注意!

上限、下限の両バウンドを指定してもよいし、いずれか一方のみ指定してもよい。片方のバウンドだけが、指定されているとき、もう一方のバウンドは+∞ または0となる。一つの変数に上限、下限の両バウンドを指定したい場合には、おのおの別にしてインプットしなくてはならない。可能な組み合せ(LO と UP) , (LO と PL) , (MI と UP)がある。上限の+∞は、自動的にジェネレーションされるのでPL型合わせとしては、指定しても意味がない。

六 インプットデータの例

生産管理応用例の数学モデルに変数名をつけて表にすると、つきのようになる。
  X11 X12 X13 X14 X21 X22 X23 X24 Y- Y1+ Y2- Y2+   RHS
Z1                 1 1        
Z2                     1      
Z3             1 1            
Z4     1 1                    
P 200 80 150 56 160 50 120 35 1 1     3500
P2   8   8   5   5     1 -1 75
T1 1 1                     8
T2         1 1             8
T3     1 1                 4
T4             1 1         4
インプットの仕方の一例を示すと、つきのようになる。

NAME  SAMPLE01
ROWS
N Z1
N Z2
N Z3
N Z4
E P
E P2
L T1
L T2
L T3
L T4
COLUMNS
INTORG
X11  P  200  T1 1
X12  P  80   P2 8
X12  T1 1
X13  T3 1
X13  Z4 1   P  150
X14  Z4 1   P  56
X14  P2 8   T3 1
X21  P  160  T2 1
X22  P  50   P2 5
X22  T2 1
X23  Z3 1   P  120
X23  T4 1
X24  Z3 1   P  35
X24  P2 5   T4 1
INTEND
Y1-  Z1 1   P  1
Y1+  Z1 1   P  1
Y2-  Z2 1   P2 1
Y2+  P2 -1
RHS
P   3500  P2  75
T1   8    T2  8
T3   4    T4  4
RANGES
T1   4    T2  4
T3   4    T4  4
END









第三章 初期値設定

初期値を必要とする標準値を改定するための機能である。このモジュールが呼び出されない限りは標準値を使う。標準値および意味については、次表にまとめられている。

操作はホームページのメニューから

  GLPS実行 → 実行 → 初期値設定
順番 意味 入力方法 標準値
有界変数複合法、フェイズ1において、単体判定基準は実行不能度と本来の目的関数に 重みを掛けて考慮する。0〜9の数値を選択できる。1は両者の比重は同じになる。 コンボボクッス 0
解が求まった時点でリインバージョンを行う チェックボックス 行う
出力有効数字桁数 コンボボクッス 10
右辺に感度分析(Sensitivity Analysis)を行います チェックボックス しない
計算中に許されるイタレーションの最大回数 テキストフィールド 90000回
再逆転を行うイタレーシ間隔 テキストフィールド 200回
逆行列ピボットをゼロとみなすべき許容誤差 テキストフィールド 5.0E-13
計算解ゼロ判定のための許容誤差 テキストフィールド 5.0E-12
負の判定のための許容誤差 テキストフィールド -5.0E-11
10 混合整数分枝限定計算の最大回数。モデルの規模と計算時間の制限、なかなか最適解に 到達しない場合許容最大回数になった時、計算を止め、その時の値を最適解とみなす テキストフィールド 8192









第四章 最適化計算

操作:メニューバーのGLPS最適化計算 をクリックします
最適化計算は先ずモデルの解析を行います。モデルの入力データが正しく行われていると、 ステータス ダイアログが現れます。数理計画問題は、現実全て解けるわけではなく、 特に大規模なモデルには計算時間が掛ります。ステータスダイアログは 問題の解かれ具合を報告しているリアルデータです。最適化を行う計算は2段階に分けます。 まず可能解をもとめ、それから最適解をもとめます

下図はGLPSに生産管理応用例のステータスダイアログ

計算結果コード
Code 意味
  1  最適解が求められた ( SOLUTION IS OPTIMAL )
  2  実行可能解がない ( THE PROBLEM HAS NO FEASIBLE BASIC SOLUTION )
  3  無限解 ( THE PROBLEM HAS NO FINITE SOLUTION )
  4  イタレーションが許される限界回数を超えた( ITERATION NUMBER IS OVER THE LIMIT )
実行可能性状態
 実行不可能 : 現時点実行不可能(但し第一段階計算中です)。
 実行可能 : 実行可能な解が得られました、最適化まで計算が続けられます。
第一目標値
 最優先目標関数現時点の目標値。
イタレーション回数
 現時点のリアル反復回数。最適解に到達するまでの反復回数は、総イタレーション回数と言います。
分岐回数
 整数変数branch and bound法計算中、現時点のリアルブランチ回数。
実行時間
 GLPS最適化計算開始から現時点のリアル経過時間。
強制終了
 大規模なモデルには計算時間が掛りすぎますが、途中強制終了ボタンを押すと強制終了はできます。そして実行可能な状態であれば、現時点の最も良い解を得ることはできます。

最適解が得られたとき、メッセージボックスが現れます。OKを返すとステータスダイアログも一緒に閉じます。







第五章計算結果出力

最適解が得られたとき、COLUMNセクションとROWセクションに分けて出力される。
COLUMNセクションでは、その変数のとる値、レデューストコストなどが表示される。
操作はメニューバーからGLPS計算結果をクリックします。

1 計算経過一覧

最適化計算の各ステップ進入タイムと処理結果の表示。
//***** 最適化計算経過一覧表 *****
G L P S (Goal Programming System) Data Input 02-01-14 15:13:42
THIS PROBLEM HAS 10 ROWS, 12 VARIABLES DATA ERROR = 0
G L P S (Goal Programming System) Data File Setup 02-01-14 15:13:42
FILE SETUP ERROR = 0
G L P S (Goal Programming System) Primal 02-01-14 15:13:42
*** PHASE 1 BEGIN ***
G L P S (Goal Programming System) Primal 02-01-14 15:13:42
** PHASE 1 END ** SOLUTION IS FEASIBLE
G L P S (Goal Programming System) Primal 02-01-14 15:13:42
*** PHASE 2 BEGIN ***
G L P S (Goal Programming System) Primal 02-01-14 15:13:42
** PHASE 2 END ** SOLUTION IS OPTIMAL
Iterations = 7
Elapsed Time = 00:00:00

2 列変数最適化解

列(Columns)変数の値、REDUCED COST(既約費用)などが表示される。
At フィールドは変数値の性質(BS,BDの値は変数の解です)
BS :基底解(basic solution)
BD :変数解は有界(bound)変数値の範囲の上界を示す。
空白:非基底解、変数値は0。
REDUCED COST(既約費用)は、該当変数を基底解に入れた場合の目標関数に対しての影響値、単なる参考数値。

生産管理(Sample01)の出力例

DATA NAME = SAMPLE01

* COLUMNS SECTION *
NumberColNameAtActivity ReducedCost
1X11BS7.3 0
2X12BS0.7 0
3X13 0 0
4X14BS4 0
5X21BS8 0
6X22 0 0
7X23BS4 0
8X24 0 0
9Y1- 0 1
10Y1+ 0 1
11Y2-BS37.4 0
12Y2+ 0 0


3 行変数最適化解

その行のスラック値と双対変数の値(いわゆる限界価値、Shadow Price)が表示されます。
感度分析機能指定がありでかつ整数変数なしのモデルのみは、右辺値に関する分析結果、 いわゆる該当制約行右辺値の増加可能上限値と減少可能下限値が表示されます。
最後に目標達成がどうかを評価します。

生産管理(Sample01)の出力例

DATA NAME = SAMPLE01

* ROW SECTION *
RowNameAtSlackActivity DualPrice
目標行1BS00
目標行2BS-37.40
目標行3BS-40
目標行4BS-40
利益EQ00
P2EQ00
T1 00
T2 00
T3 00
T4 00

*** 右辺値(RHS)に関する感度分析 ***

RowName現在の右辺値増加可能の上限 減少可能の下限
利益350084561
P275無限37.4
T1 82.8050.42
T2 83.5062480.525
T3 43.18751.5
T4 44.6750.7

4 目標分析

  1 目標行1 目標達成
  2 目標行2 目標値 37.4
  3 目標行3 目標値 4
  4 目標行4 目標値 4.

最後に二種類の誤差値が参考のため出力される。
操作はGLPS実行メーニュから
  結果出力 → 最適化計算誤差情報

 @ A × X − B
   誤差合計 = XXXXXX      最大誤差 = XXXXXX
 A 潜在価額(Shadow Price)
   誤差合計 = XXXXXX      最大誤差 = XXXXXX

生産管理(Sample01)の出力例


** TOLERANCE **
TOLERANCE = A * X - B TOTAL = 2.220446e-016     MAX = -2.220446e-016
* CALCULATE SHADOW PRIC *
TOTAL = 0            MAX = 0