線形計画法

Fortranによるサンプルソースコード : 使用ルーチン名:e04mff

Keyword: 線形計画法

概要

本サンプルは線形計画法を行うFortranによるサンプルプログラムです。 本サンプルは以下に示される制約条件を満たす目的関数を最小化する解を求めて出力します。

線形計画法のデータ 

※本サンプルはnAG Fortranライブラリに含まれるルーチン e04mff() のExampleコードです。本サンプル及びルーチンの詳細情報は e04mff のマニュアルページをご参照ください。
ご相談やお問い合わせはこちらまで

入力データ

(本ルーチンの詳細はe04mff のマニュアルページを参照)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

このデータをダウンロード
E04MFF Example Program Data
  7  7                                             :Values of N and NCLIN
 -0.02  -0.20  -0.20  -0.20  -0.20   0.04   0.04   :End of CVEC
  1.00   1.00   1.00   1.00   1.00   1.00   1.00
  0.15   0.04   0.02   0.04   0.02   0.01   0.03
  0.03   0.05   0.08   0.02   0.06   0.01   0.00
  0.02   0.04   0.01   0.02   0.02   0.00   0.00
  0.02   0.03   0.00   0.00   0.01   0.00   0.00
  0.70   0.75   0.80   0.75   0.80   0.97   0.00
  0.02   0.06   0.08   0.12   0.02   0.01   0.97   :End of matrix A
 -0.01  -0.10     -0.01     -0.04     -0.10     -0.01     -0.01
 -0.13  -1.0D+25  -1.0D+25  -1.0D+25  -1.0D+25  -9.92D-02 -3.0D-03 :End of BL
  0.01   0.15      0.03      0.02      0.05      1.0D+25   1.0D+25
 -0.13  -4.9D-03  -6.4D-03  -3.7D-03  -1.2D-03   1.0D+25   2.0D-03 :End of BU
 -0.01  -0.03   0.00  -0.01  -0.10   0.02   0.01   :End of X 

  • 1行目はタイトル行で読み飛ばされます。
  • 2行目は変数の数(n)と一般線形制約の数(nclin)を指定しています。
  • 3行目は目的関数の係数(cvec)を指定しています。
  • 4~10行目は一般線形制約の係数(a)を指定しています。
  • 11~12行目は変数と一般線形制約の下限(bl)を指定しています。
  • 13~14行目は変数と一般線形制約の上限(bu)を指定しています。
  • 15行目は解の初期値(x)を示しています。

出力結果

(本ルーチンの詳細はe04mff のマニュアルページを参照)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

この出力例をダウンロード
 E04MFF Example Program Results

 *** E04MFF

 Parameters
 ----------

 Problem type...........        LP

 Linear constraints.....         7       Feasibility tolerance..  1.05E-08
 Variables..............         7       Optimality tolerance...  1.05E-08

 Infinite bound size....  1.00E+20       COLD start.............
 Infinite step size.....  1.00E+20       EPS (machine precision)  1.11E-16

 Check frequency........        50       Expand frequency.......         5
 Minimum sum of infeas..        NO       Crash tolerance........  1.00E-02

 Print level............        10       Iteration limit........        70
 Monitoring file........        -1

 Workspace provided is     IWORK(      17),  WORK(     182).
 To solve problem we need  IWORK(      17),  WORK(     182).


  Itn     Step Ninf Sinf/Objective  Norm Gz
    0  0.0E+00    3   1.038000E-01  0.0E+00
    1  4.1E-02    1   3.000000E-02  0.0E+00
    2  4.2E-02    0   3.500000E-02  0.0E+00
    3  1.9E-01    0   3.090243E-02  0.0E+00
    4  1.5E-01    0   2.989710E-02  0.0E+00
    5  3.7E-01    0   2.725725E-02  0.0E+00
    6  6.5E-01    0   2.403774E-02  0.0E+00
    7  4.6E+00    0   2.359648E-02  0.0E+00


 Varbl State     Value       Lower Bound   Upper Bound    Lagr Mult   Slack

 V   1    LL  -1.000000E-02 -1.000000E-02  1.000000E-02  0.3301         .
 V   2    LL  -0.100000     -0.100000      0.150000      1.4384E-02     .
 V   3    UL   3.000000E-02 -1.000000E-02  3.000000E-02 -9.0997E-02     .
 V   4    UL   2.000000E-02 -4.000000E-02  2.000000E-02 -7.6612E-02     .
 V   5    FR  -6.748534E-02 -0.100000      5.000000E-02       .      3.2515E-02
 V   6    FR  -2.280130E-03 -1.000000E-02      None           .      7.7199E-03
 V   7    FR  -2.345277E-04 -1.000000E-02      None           .      9.7655E-03


 L Con State     Value       Lower Bound   Upper Bound    Lagr Mult   Slack

 L   1    EQ  -0.130000     -0.130000     -0.130000      -1.431     -5.5511E-17
 L   2    FR  -5.479544E-03      None     -4.900000E-03       .      5.7954E-04
 L   3    FR  -6.571922E-03      None     -6.400000E-03       .      1.7192E-04
 L   4    FR  -4.849707E-03      None     -3.700000E-03       .      1.1497E-03
 L   5    FR  -3.874853E-03      None     -1.200000E-03       .      2.6749E-03
 L   6    LL  -9.920000E-02 -9.920000E-02      None       1.501     -1.3878E-17
 L   7    LL  -3.000000E-03 -3.000000E-03  2.000000E-03   1.517      1.1276E-17

 Exit E04MFF - Optimal LP solution.

 Final LP objective value =   0.2359648E-01

 Exit from LP problem after     7 iterations.

  • 8~20行目に以下に示すプログラムのオプション引数が出力されています。
    Problem type 最小化される目的関数の種類。"LP"は線形計画問題であることを意味します。
    Linear constraints 線形制約の数。
    Feasibility tolerance 実行可能解での許容可能な制約違反の最大値。
    Variables 変数の数。
    Optimality tolerance 境界値や制約に正しい符号がついているかを判断するのに使用される許容値。
    Infinite bound size 無限の境界。この値以上の上限は+∞と見なされます。またこの値を負に反転させた値以下の下限は−∞と見なされます。
    Cold start 初期のワーキングセットがどのように選ばれるかを示しています。"Cold"は変数や制約の値に基づいて初期のワーキングセットが選ばれていることを意味します。
    Infinite step size 無限解へのステップと見なされる変数の変化の大きさ。
    EPS (machine precision) マシンの精度。
    Check frequency この反復回数の時に現在の解がワーキングセットにある制約を満たしているか確認されます。
    Expand frequency 問題を解くためにこの反復数を超えた反復が必要な場合に、新たに反復が開始されます。
    Minimum sum of infeas 制約に対して実行可能解がない場合、実行不可能性を最小化すべきかを指定するフラグ。 "NO" を指定した場合、問題が実行不可能とわかり次第ルーチンは終了します。
    Crash tolerance 初期のワーキングセットに含まれる不等式制約が下限/上限のこの範囲内にあることを示しています。
    Print level 結果出力のレベル。"10"は最終解と各反復の結果を出力することを意味します。
    Iteration limit 最適化フェーズの最大反復数。
    Monitoring file モニタリング情報が出力されるファイル名。"-1"は出力されないことを意味します。
  • 22~23行目には、与えられたワークスペースの大きさと問題を解くのに必要とされたワークスペースの大きさが出力されています。
  • 26~34行目には以下が出力されています。
    Itn 反復回数。
    Step 探索方向に進んだステップ幅。
    Ninf 違反した制約の数。
    Sinf/Obj 制約違反の大きさの加重和(xが実行可能でない場合)もしくは目的関数の値(xが実行可能な場合)。
    Norm Gz 縮小勾配のユークリッド・ノルム。
  • 37~45行目には以下が出力されています。
    Varbl 変数を示す"V"、インデックス。
    State 変数の状態。LLは下限、ULは上限であることを意味し、FRは下限も上限もワーキングセットにはないことを意味します。
    Value 最後の反復での変数の値。
    Lower Bound 下限。
    Upper Bound 上限。
    Lagr Mult 関連する境界制約のラグランジュ乗数。
    Slack スラック(変数の値と上限/下限の近いほうとの差)。
  • 48~56行目には以下が出力されています。
    L Con 線形制約を示す"L"、インデックス。
    State 制約の状態。EQは固定制約を意味し、LLは下限であることを意味し、FRは下限も上限もワーキングセットにはないことを意味します。
    Value 最後の反復での制約の値。
    Lower Bound 下限。
    Upper Bound 上限。
    Lagr Mult 関連する境界制約のラグランジュ乗数。
    Slack スラック(制約の値と上限/下限の近いほうとの差)。
  • 58行目にLPの最適解が見つかったことが示されています。
  • 60行目にLPの最終的な目的関数値が出力されています。
  • 62行目に7回の反復を行ったことが示されています。

ソースコード

(本ルーチンの詳細はe04mff のマニュアルページを参照)

※本サンプルソースコードは科学技術・統計計算ライブラリである「nAG Fortranライブラリ」のルーチンを呼び出します。
サンプルのコンパイル及び実行方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

このソースコードをダウンロード
    PROGRAM e04mffe

!      E04MFF Example Program Text

!      Mark 23 Release. nAG Copyright 2011.

!      .. Use Statements ..
       USE nag_library, ONLY : e04mff, nag_wp
!      .. Implicit None Statement ..
       IMPLICIT NONE
!      .. Parameters ..
       INTEGER, PARAMETER              :: nin = 5, nout = 6
!      .. Local Scalars ..
       REAL (KIND=nag_wp)              :: obj
       INTEGER                         :: i, ifail, iter, lda, liwork, lwork,  &
                                          n, nclin, sda
!      .. Local Arrays ..
       REAL (KIND=nag_wp), ALLOCATABLE :: a(:,:), ax(:), bl(:), bu(:),         &
                                          clamda(:), cvec(:), work(:), x(:)
       INTEGER, ALLOCATABLE            :: istate(:), iwork(:)
!      .. Intrinsic Functions ..
       INTRINSIC                          max
!      .. Executable Statements ..
       WRITE (nout,*) 'E04MFF Example Program Results'
       FLUSH (nout)

!      Skip heading in data file

       READ (nin,*)
       READ (nin,*) n, nclin
       liwork = 2*n + 3

!      The minimum LWORK for an LP problem:

       IF (0<nclin .AND. nclin<n) THEN
          lwork = 2*(nclin+1)**2 + 7*n + 5*nclin
       ELSE IF (nclin>=n) THEN
          lwork = 2*n**2 + 7*n + 5*nclin
       ELSE
          lwork = 7*n + 1
       END IF

       lda = max(1,nclin)

       IF (nclin>0) THEN
          sda = n
       ELSE
          sda = 1
       END IF

       ALLOCATE (istate(n+nclin),iwork(liwork),a(lda,sda),bl(n+nclin), &
          bu(n+nclin),cvec(n),x(n),ax(max(1,nclin)),clamda(n+nclin),work(lwork &
          ))

       READ (nin,*) cvec(1:n)
       READ (nin,*) (a(i,1:sda),i=1,nclin)
       READ (nin,*) bl(1:(n+nclin))
       READ (nin,*) bu(1:(n+nclin))
       READ (nin,*) x(1:n)

!      Solve the problem

       ifail = 0
       CALL e04mff(n,nclin,a,lda,bl,bu,cvec,istate,x,iter,obj,ax,clamda,iwork, &
          liwork,work,lwork,ifail)

    END PROGRAM e04mffe


関連情報
© 日本ニューメリカルアルゴリズムズグループ株式会社 2024
Privacy Policy  /  Trademarks